Octrees/collision detection

dj_ 101 Feb 09, 2003 at 08:52

I’ve made an octree class, and I am testing it out with a height map. I was thinking that you could check collision faster, by only checking the triangles in the frustum. Problem with this is, that what if you are walking backwards or sideways? What is generally the best way of using an octree to cut down on the number of triangles you check for collision with?

EDIT: On a side note, I’ve read other methods for spatial subdivision. Quadtrees, octrees, bsp, AABB trees. The author that writes about these particular trees always seems to prefer his method best. I read on the flipcode site that octrees have the weakness that they draw overlapped geometry. This is not necissarily true, it you put a polygon splitter function in there, but that increases your triangle count. What would the people of gamedev recommend to someone learning, wishing to find the most elegant way of subdividing their scenes? Maybe someone with a little more experience in this area could enlighten me with a highlight of the strengths and weaknesses of each. Am I wasting my time with octrees, being that there is a method I don’t yet know of or what?

2 Replies

Please log in or register to post a reply.

shezan 101 Feb 10, 2003 at 09:07

rather than checking with triangles in the view frustum, i think it would be better to only check in the octree where your camera is located, and also the octrees that are directly next to it… so whenever the camera moves, you need to update the “current octree”… this has 2 advantages

  • you can still check triangles on the side or behind
  • you dontneed to check with triangles that are far away (but still in the view frustum)
shezan 101 Feb 10, 2003 at 09:17

i also had the same problem when i was rendering my heightmap (ie, i had overlapping triangles in different octrees), but i didnt bother splitting them since my octrees were quite small

however, to prevent them from overlapping, i added a variable called “nRenderCycle” for each triangle. inside my draw function, i increment a global RenderCycle and for each triangle:

if (tri->nRenderCycle != global_render_cycle)
  // Render the triangle

  tri->nRenderCycle = global_render_cycle;

This way, whenever the renderer sees the same triangle in another octree, it will not render it…