Where do I store shapes in an octree?

Question

A little background on design decisions thus far... I have developed an octree structure that can store points. I have chosen to limit the recursion of "generations" based on a certain base voxel size. Child nodes are only created when points are added to that node. This is not a dynamic graphics application - this octree and the objects in it are static, so pre-processing to improve performance is not a concern.

Now, I would like to add "shapes" to my octree - specifically, a surface mesh composed of triangles. The vertices of these triangles do not correspond to the points stored in the octree. How does one store these shapes in the octree? I see two options...

Grey nodes are "empty" in that they have no shapes. In alternative 1, shapes are stored in every node that they intersect - i.e., node 1a contains shape1 and 4c & 4d share shape2. In alternative 2, shapes are stored only in the smallest node that they intersect - i.e., node 1a contains shape1 and node 4 contains shape2.

Most posts on octrees that I've seen assume Alt1, but they never explain why. Alt2 makes more sense to me and will only create extra work for those shapes that reside on node boundaries. Why is Alt1 preferable?

Edit: To clarify, my implementation language used is C++ so I'd prefer sample implementations in that language, but the question is language-independent. Sorry if that's incorrect tag usage.

Edit2: Although not directly related to the question of shape storage, this link has a good discussion on octree traversal that is behind the question. I thought it might help anyone interested in working on this question.

---

Update: Four years later, Alt2 ended up being easier to implement but very slow because large triangles stored at higher octree levels got tested every traversal of the octree - in my case, that meant hundreds to thousands of unnecessary tests. I ended up revising my code to use a R*-Tree variant instead, which was easy to implement and substantially faster.

Answer 1

ALT1 is correct. Given that you want to limit the maximum number of objects (triangles) in a node, you will need to subdivide nodes that will contain many triangles. This inevitably leads to having a single triangle in multiple nodes, unless you want to subdivide triangles so that they fit the octree nodes perfectly (that depends on your application, I would generally not recommend that and e.g. for raytracing it is indeed usually not done).

As a counterexample, imagine ALT2 containing a detailed model of Stanford bunny, standing on a large triangle. The large triangle would prevent subdivision of the root node to subnodes and thus your octree would be as good as if you had no octree.

Alternately, you would have to keep the large triangle in the root node and subdivide it to subnodes that would contain the rest of the smaller bunny triangles. Having triangles not only in leaf nodes but also in the other nodes will likely complicate octree traversal (but that also depends on your application). If we stick with the raytracing scenario, to find the nearest intersection of a ray and a triangle, you would have to check a node and all the subnodes in order to find the closest intersection and you would have to track movement of the ray to the next node, on all of the tree levels simultaneously. On the other hand, if your geometry is only in the leaves, you test triangles in the leaves in the order the ray visits them (while keeping track of triangles that were already tested to avoid testing the same triangle twice).

Answer 2

This is more in reference to quadtrees which I am more familiar with but they are the 2D equivalent of an octree; so it may be applicable.

The general approaches to insertion: Each internal node of the a quadtree has a capacity which is the max number of "objects" a quadtree quadrant can hold. If you reach the capacity, you subdivide and then insert all the "objects" into their appropriate child quadrant. You will also have a point where you subdivide and one or more of your "objects" straddles multiple child quadrants; be careful of that case when inserting/querying. Generally, the node capacity is chosen to either favor faster insertion or querying.

So, taking that into consideration, I see nothing wrong with the ALT2 image you are presenting. But my assumption on why you always see ALT1 image is the default approach when inserting into an unoccupied cell is to subdivide and then insert.