Started by Sep 30 2001 10:53 AM

,
5 replies to this topic

Posted 30 September 2001 - 10:53 AM

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??

Posted 30 September 2001 - 12:45 PM

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.

Posted 01 October 2001 - 01:16 AM

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...

Posted 01 October 2001 - 01:42 AM

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

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

Posted 01 October 2001 - 06:06 AM

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.

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.

Posted 01 October 2001 - 10:54 AM

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.

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.