Octree implementation for triangular mesh and particles

Question

I am currently working in an efficient calculation engine for particle simulation both in CPU and GPU. I have been working lately in octrees and I managed to write a working version of octree for particles in space and also efficiently handled their collisions. Now I have to insert the triangular mesh(STL object) in my octree so that I can handle collision between particles and triangles of object too. I am confused how shall I insert the triangles to my already created octree in an efficient way? Please suggest methods to achieve this. If this helps, I am working with C++. Thanks already.

Endospore

Answer 1

Inserting triangles into an existing Octree should not be too different than creating a new Octree and inserting them into it. The only thing which is critical here is to make sure that your existing Octree covers a 3D space which is guaranteed to include all the triangles.

Other than that, regarding the insertion itself, basically I would recommend implementing a two-step insertion where in the first step you use some quick test to see whether a triangle may be contained in a certain cube, and in the second phase (in case the first has passed) you actually do a proper calculation to see this.

One such of quick test is getting the bounding box of the triangle (from the minimum x,y,z of all points to the maximum x,y,z of all the points) and comparing that box with the one of the octree (if both coordinates of the triangle box on the same axis are not inside the range defined by the octree box and are both on the same side (both below or both above), then it's definitely outside).

Obviously, once you discovered an intersection between a triangle and an Octree box, you should repeat this test for all of it's child boxes.

There are also other places in the algorithm to make this more efficient (such as sorting boxes and triangles by x,y,z and then doing a check which only considers relelvant boxes), but it depends on the level in which you wish to optimize.

Kendrick

And here is some example code I wrote for the bounding box intersection test that I mentioned: code.google.com/p/raytracer-azbi-tau-2010/source/browse/trunk/… – Kendrick

Answer 2

If your particles are uniform-sized and your triangles are not, that tends to call for a very different kind of data structure. With particles of uniform sizes, you can just treat them as points and just store one particle in one leaf node in the tree as a single point in space (doesn't matter if it has a big radius/size as long as all particles are uniformly-sized since your search queries, provided they are expanded by the size of a particle, will always pick up their center points).

For triangles, they can vary wildly in size and can intersect multiple of the 8 child octants. As a result you can do several things that I know of:

1. Simply insert a pointer/index to the triangle in multiple leaves with some redundancy, or simply duplicate the entire triangle data in all the leaves (can be explosive in memory use if you're not careful with this in terms of adjusting the parameters for the tree against the content, but it can make searching more cache-friendly).
2. Split the triangle so that if it intersects two or more octants, it becomes two or more split triangles. This tends to be a bit expensive for builds/updates but it can be fast for queries if you're storing the triangle data directly in the leaves in a cache-friendly way.
3. Use a loose representation, like a loose octree. In this case you only treat the triangle as a single point upon insertion. However, you expand the AABBs of all the octree nodes you traverse during the insertion to encompass the triangle.

#1 tends to be decent for dynamic content as long as you minimize memory use and processing involved in building the tree and put some sane limits like a maximum depth for the octree so that it doesn't want to split indefinitely.

#2 tends to be quite good for static content and tends to be well-suited for fast searches, since it can result in a shallower and better-balanced tree than #1 because you don't have overlapping data stored in the leaves which will tend to want them to split more than they ideally should. If your data is static, then you might only need to store one copy in the octree directly itself, and the octree is free to modify that data all it wishes to provide the fastest searches.

#3 tends to be very good for dynamic content since it balances the overhead well between building/updating the tree and searching it. However, the loose octree comes at a big hit to the performance of search queries because what was formerly a simple check against a center point to determine which octant(s) to traverse now requires inspecting the AABB of all 8 octants to determine which children to traverse during a search. However, it significantly reduces the overhead of building and updating the tree, making it well-balanced for dynamic content where, say, a mesh is deforming every single frame in an interactive realtime context.

It helps with these types of questions to specify your needs exactly, like whether your meshes are static or not, whether you need fast updates/builds/searches or a balance (you generally can't make all three of these things super fast: to make one super fast generally means making the other one slower).

Raytracers, for example, often use reps that are very well-suited for extremely static content, since they can often afford to take some extra time building the structure since they might perform a billion ray/triangle intersection tests against it afterwards. It's not necessarily a big deal for a raytracer to take a hundred milliseconds to build/update its spatial index since it might take many seconds or sometimes even minutes or hours to render the full scene at production quality. 100ms by offline rendering standards is minuscule time, by realtime standards it's an epic amount of time. On the other hand, the fastest search times are so, so important for a raytracer, so loose octrees would generally be a horrible choice and most raytracers will often want to deep copy the data required to do intersection tests into the leaves so that they don't require sporadic memory access patterns to access the data stored in the leaves.

However, a physics engine dealing with collision detection of many things moving around in a realtime context would want a very different representation suited for dynamic content. And game engines which deal with a wide mixture of both static and dynamic content in fully interactive realtime contexts might use multiple data structures: each one tailored for the type of content they store.

If your particles are, indeed, uniform-sized, then I recommend using a different data structure (a different type of octree, e.g.) for storing the triangle meshes. Same case if your particles are very dynamic while your meshes are fairly static. In that case, if you're searching to see whether a particle collides with a mesh or a particle, you might first check the octree storing the meshes that is optimized for triangles. If you don't find an intersecting triangle, then search the other octree suitable for storing dynamic, uniform-sized particles to check for particle-particle collisions. You could still abstract this to the point where it looks like a single data structure, but ideally you should use two different implementations for this.

For meshes that transform, it can also be useful to store two octrees: an outer octree for the whole meshes just for coarse intersection tests against their AABBs, e.g. Then if the coarse intersection test passes, search an octree stored per mesh to find which triangle(s) intersect. This allows you to avoid updating the octree storing triangles when meshes transform (ex: when they rotate).

Embouchure