Octree - what cells does moving object affect?

Question

I want to use an octree as an OGL scene representation and I have some moving object in there. I would also like to use this octree to accelerate the collision detection. Is there any good algorithm that gives you the path in octree (all cells/nodes of such path) that a moving object would penetrate?

Assume I have one moving object where I know velocity (so two positions, start of the movement and end of the movement in one frame).

My idea is to simply go through the whole tree and perform collision detection of the cell containing the moving object and the rest of the cells. That would give me all of them but isn't it an overkill? Thanks!

Answer 1

If you have start and end positions of your moving object, then you have a ray defining your object's motion. A node in your octree is a cuboid, which is a rather simple polyhedron. You can think of collision/intersection tests as ray-cuboid intersection tests.

Check out the object-object intersection algorithms on this page:

http://www.realtimerendering.com/intersections.html#II247

That page points to code on Github for ray-polyhedron intersection:

https://github.com/erich666/GraphicsGems/blob/master/gemsii/RayCPhdron.c

To start with a simple example, assume your object is simply a point traveling along that ray of motion. Then you could find the object's path using ray-cuboid intersection. If a node of the octree doesn't contain the ray, then there's no point in searching deeper into that node's child nodes. (Searching through the entire octree from top to bottom defeats the purpose of creating the octree in the first place.) Even if your objects is a complex thing with numerous vertices, writing the code to do simple ray/cuboid intersection for one point in motion will be instructive.

The computational geometry book Geometric Tools for Computer Graphics by Schneider and Eberly has a nice treatment of line-in-polyhedron intersection, including a page of pseudocode that's easy to understand. If you're going to spend much time coding up 3D geometry, you'll want a copy of that book on your shelf. Eberly also has a number of helpful PDFs on his website:

https://www.geometrictools.com/

If you create your octree such that each node has a pointer to its immediate neighbors, then this may speed up the search a bit. I wouldn't suggest implementing at the start, though--create something simple first rather than tackle multiple implementation tasks at once.

To take a slightly more complicated example, if you have a triangle of 3 vertices oriented so that the triangle's surface normal is parallel to the direction of motion, then intersection tests of the triangle with the cuboid nodes of your octree would be straightforward; test ray-cuboid intersection for rays starting at each vertex and parallel to the direction of motion.

From there your approach may vary depending on the complexity of your moving object and your needs for "collision" detection. For example, you might allow not only an intersection to be considered a collision, but also a very near pass of one object to another. I don't know what your application is, how complex your object may be, whether the object is approximately convex, etc., but you could consider testing collision with the convex hull of the object, or perhaps with a sphere/cube that encompasses all the points in the object.