|
Splitting Plane Heuristics Question submitted by (23 August 2001)  |
Return to The Archives |
 |
 |
|
|
In my last (indoor / outdoor) engine, I have grouped the polys in objects. Then
these objects are organized in a spatial hierarchical structure. At this point
I'm really still undecided between Adaptive Oct-Tree and KD-Tree. So, finally, I
decide to implement both to evaluate their efficiency. Noting that I need this structure to do view frustum culling and occlusion culling (of both nodes and bounding box of the objects), what are the best heuristics to choose the "splitting point" for Oct-Tree and the splitting plane for KD-Tree? And also, what are good termination criteria? |
||
 |
 |
 |
|
|
|
The answer depends on what you want to do with the octree. Let's tackle this
from the theoretical point of view... consider what happens when you build your
octree: If, during recursion, you move your splitting planes away from the center of a node, you can balance your tree based on content (i.e. trying to get an equal number of polygons per node) but you lose spatial balancing. If you keep your splitting planes in the center of the node, you maintain a spatial balance, but you lose the balance of polygon count. So, since visibility determination is a spatially-based ("spatial domain?") problem, you'll want a spatial balance. However, if you plan to use your octree for collision detection and other complexity domain issues, you'll want to balance your polygon count. There's one other thing to note about spatial balancing. If you simply take your bounding volume and use that as the root node for your octree, you still won't get perfect spatial balancing unless your bounding volume dimensions are all equal (i.e. a perfect cube.) So when I was playing with octrees, I found it advantageous to define the root node as a perfect cube (smallest bounding cube) with the data-set centered within. This results in perfect spatial balancing. This made a noticeable difference. When building the tree, I tend to use a threshold of polygon count as my subdivision criterial. Specifically, I use the count of polygons that intersects the volume of a node. If, at a node, the number of polygons intersecting that node's volume exceeds the threshold, I subdivide. Others suggest using the number of polygons that intersect any of the three bisection planes, but I've never found that useful. Sometimes, a tree can get out of control. Consider the case when you have 200 polygons, all defined by the same three vertices (i.e. 200 identical polygons that share the same plane as well as the same space.) If this data exists in your data set and your threshold is set lower than 200 polygons, your tree will never stop building. This is where the termination criteria is necessary. My termination criteria is two-fold. I have a maximum depth limiter that prevents the tree from getting too deep, regardless of the content. I also have a minimum node size. This works hand-in-hand with the maxiumum depth (you really only need one of the two) but sometimes it helps to specify the maxium depth in terms of the size of the smallest node. Response provided by Paul Nettle |
||
|
|
|
This article was originally an entry in flipCode's Ask Midnight, a Question and Answer column with Paul Nettle that's no longer active. |