16

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...

Alt 1: store triangles in every leaf node it crosses. Alt 2: store triangles in the smallest node that can hold every vertex.

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.

Phlucious
  • 3,704
  • 28
  • 61
  • 1
    +1 I find this question interesting and well-presented (and have absolutely no clue on an answer, just saying up-front). Is it correct to assume the reason for the C++ tag is your preference to viable addressing scheme proposals to be presented with? If so, you may want to clarify that in the question, though I'm guessing someone could foster an answer in Forth and you would probably dissect it with ease. As written, it would stand nicely independent of language tag. – WhozCraig Apr 29 '14 at 19:32
  • The reason for Alt1 is it's implied precision. The octree aabb-tests are executed more rapidly than per triangle tests. Thus a finer grained octree with multiple registrations of the same mesh will allow more rapid queries. As in log n compared to n, in terms of complexity. But on the other side it is more memory intensive than alt2. Additionally for non static geometry, the updates are more expensive than in alt2. Overall the choice on what kind of subdivision you choose depends on the type of scene you are dealing with. Amount of objects & variability play equal roles (and memory). – meandbug Apr 29 '14 at 19:45
  • @WhozCraig: The C++ flag was included just because that's my implementation language and any sample code would be best understood in that language. You're right that the question itself is language-independent. – Phlucious Apr 29 '14 at 19:58
  • @meandbug: Thanks for the information. Because my environment is static (point cloud LiDAR data, to be specific), scene updates are not a design constraint, but it's good to know that that consideration influences the widespread preference for alt1. Most octree articles I've seen are gaming-related. – Phlucious Apr 29 '14 at 19:58
  • 1
    @Phlucious, why then not go for a K-D-Tree? It seems more optimal for such an application. http://en.wikipedia.org/wiki/K-d_tree – meandbug Apr 29 '14 at 20:13
  • @meandbug: Good question. My original task required some voxel-based computations that required a regular grid, so I overlaid an octree on top of that to speed up search and ray-tracing algorithms. I also simply liked the simplicity of an octree. – Phlucious Apr 29 '14 at 20:25
  • You mentioned that `a R*-Tree variant ... was easy to implement and substantially faster`. I wonder about memory usage. How is `R*-Tree` compared to Octree regarding memory usage? Thanks =) – Megidd Jun 22 '20 at 13:21
  • 1
    @user3405291 I did a sparse octree implementation, instantiating nodes only when they were needed, so I didn't notice a significant change in memory usage between the two. My data is also static, so I can spatially optimize the R*-tree in a way that a dynamic environment couldn't maintain. I can't speak to the general case. – Phlucious Jun 23 '20 at 16:40

2 Answers2

5

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).

the swine
  • 10,713
  • 7
  • 58
  • 100
  • Thanks for the interesting response. In your scenario, are all leaf nodes at the same depth level? If so, then it would seem to me that the ray tracing algorithm would want to traverse every level anyway in order to skip empty high-level nodes (and their children) in the tree. If not, then wouldn't you have to traverse every level, regardless? – Phlucious May 28 '14 at 15:44
  • 1
    @Phlucious they can be at different levels, otherwise the octree would degenerate to a regular grid and it would be possible to use 3DDDA rasterization to traverse the nodes. As for visiting the higher nodes, it is not quite true, you always know which side of a node the ray exits and you can prepare pointers leading to the neighbor node sharing the given side (initialize pointers once, use many times). Then the octree structure is used only to find the ray origin and then all the traversal is simple jumps to neighbor. – the swine May 28 '14 at 17:34
  • Makes sense. When storing leaf nodes at multiple levels, how exactly do you determine the leaf nodes intersected by a shape when the vertices are several nodes apart (e.g., in your bunny-on-a-large-triangle example)? I don't follow how a large node would store a pointer to its "west" neighbor when there are two smaller "west" nodes. – Phlucious May 28 '14 at 21:40
  • @Phlucious Node-triangle intersection is easily done using the separating axis theorem (SAT). For axis-aligned nodes, it is easy to implement and quite fast. As for the "west" pointer it either stores a pointer to the "west" node at the same level and after passing there, the next leaf node is found, or alternately it stores a "bitmap" of pointers, mapped to its wall, and based on which "pixel" the ray shoots, the traversal continues. – the swine May 29 '14 at 07:32
1

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.

Justin
  • 4,196
  • 4
  • 24
  • 48