I am working on Octrees in C++ and need to know weather a triangle intersects a cube. Can someone help me with this problem? My current approach is rather slow. I copied the code from the 'pick' SDK sample and used a plane to find the actual point of intersection. generates lines joining each vertex of the cube and checks if it intersects the triangle. it works, but takes 20 seconds! [edited by - Cybertron on July 13, 2002 1:44:58 PM]

i think octrees are computed by intersecting with one plane at a time. Dont think of the intersection as cube with a triangle (its slower, because the work is repetitive, planes are shared by more than one cube). Think of it as intersection of triangle with xz-plane , xy-plane, and yz-plane, one at a time, and the final broken up triangles have to be put in the correct box. Regardless of how you computer, IMHO octree is computed ONLY once for Fustrum culling and collision with fixed geometry, and may be once every frame for collision with moving geometry.

Maybe I am not using octrees properly, I am just using them for collision detection to replace the manually defined bounding boxes. Octrees are fast for this because it only has to check one box if there is no collision. The tree only needs to be computed once because the geometry is static, and all collision tests are transformed into model space for testing

I never thought of frustum culling, each end node could have a list of contained triangles and an index buffer could be generated at runtime

What is the best way to test if a line goes through a cube? I chould get a plane for each axis or each face and get the intersection point of the line and check if it is inside the cube

I had this idea in the middle of the night, and it works perfectly! It takes 101 seconds for my old method, now it is 32! I also found a REALLY bad logic bug, so that may be one reason!

I generate a plane for each face of the cube, and get the point of intersection of a line segment for each edge of the triangle. It tests if the point is inside the triangle and the cube. if all the points are outside the cube, tests if a line that joins all the valid ones goes through the cube (cube is inside triangle)

Well thats my rather simplistic implementation of an octree

You are definitely testing too much. As i said before, planes are between cubes, so every plane is shared by 2 cubes. You are losing some of the advantage of Octree by intersecting with each cube. Rather, think of the problem as that of spacial partitioning. You divide the space occupied by the root node into 2, and then 4 and then 8...For each dividing planes, intersect 2 edges of the triangle (you have to locate the "isolated" point, and edges going to that point are used). The result is upto 3 triangles generated from intersection of one triangle to a plane.

and then the resulting triangles are stored in its children. and then the process is repeated recursively. Secondly, the amount of time it takes for an octree to generate is always large (thats why its not computed every frame). (although, i dont expect a collision tree to take this much time, since its only dealing with bounding boxes). My octree (used for frustum culling) takes several seconds to generate, but it processes EVERY polygon in the terrain (which is about 202,400 polygons).

I hope the above helps. btw. how many bounding boxes are there?

Thanks for your input! Being a beginner at 3D math I decided to take a logical approach rather than a mathematical one.

The problem with my program was it was checking EVERY triangle against EVERY node, so no wonder it took 32 seconds! I was not following the main principal of Octrees. For each node it saves a list of triangles that intersect it, which the children use. They only check the geometry that the parent node has. Now it is 0.5 seconds