Hi, I''m trying to implement an octree, in order to do so I need to find out if a triangle is in a cube. In game programming gems, specifically octree construction, they mention an algorithm used in "Real-Time Rendering" I do not own that book. I understand all of the sample code given in the Polygon Overlap section, except I don''t know what I would write for the function TriInVoxel. So basically my question is how do I find out if a triangle is an a voxel??

If you want to test if a triangle is in a cube, you can probably do so by testing if all verticies of the triangle is in the cube. If your cube is axis-aligned, that''ll make it pretty easy. Just do a test one vertex at a time.

That will not work properly. A triangle can have all of it''s vertices "around" the cube, so the triangle is in the cube but the vertices are not. A way to test this is when you test the tree vertices against the planes of the cube, remember wich side each vertice was, if two vertices is on different sides of a plane, you''ll have to test where the line between the vertices intersect with the plane, and test that point as if it were a vertice...

Ok, there are two steps to do in order
first: check if the points of the triangles are all inside
the cube and set it to ''inside''
second: check for ray/plane intersection for each segment
building up the triangle do it for every plane of the cube
if one of this intersects the plane ( you don''t have to rewrite the entire forumla, remember that the planes are aligned each other )then set the triangle to ''intersecting'' if this condition
is not met, then the triangle is ''outside''
hope it helps, i did so in my engine and it works perfectly

FYI,

There is a web site for the book "Real-time Rendering."

Here it is:

www.realtimerendering.com

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

joke_dst

mah bad...I misinterpreted the question. I thought he was asking whether the triangle is completely contained by a cube. Yes, my algorithm would most definitely not work in this case.