I've implemented a basic Octree, which should for now only store primitive collision shapes like boxes and spheres to raypick for my level editor. For now I've two methods to stop child creation:
- Eighter if the node only contains one children
- or if it goes beyond a certain depth.
Works pretty well, except for one corner case. Consider this picture (its a quad-tree, but since octree and quadtrees are conceptually similar its easier for me to draw):
See how the green and blue rectangle take up nearly the same space. Obviously now none of the above condition is triggered, so the lower left tree-child gets subdevided (I only marked this one, but same would applie to the other too). Now the red marked child is where things get really ugly. Since each of those childs would contain both rectangles, they would subdevide further and further and so on until the maximum depth is reached.
This doesn't make any sense, from a performance viewpoint. Since each of those children contain exactly the same bounding volumes, they shouldn't exist. It should look like this:
The middle child as well as the two yellow marked childs, since all containing the same two bounding volumes, don't get subdevided further - I subdevided those where it would make sense.
Now, my question: what is the common approch for that case? It wasn't talked about in any tutorial about oct/quadtrees I've read. The only way I can think about is to first create all eight child-nodes, and then check if they contain exactly the same volumes (or the data they are connected too). But since this is a performance critical task, I wouldn't want to do this if there is a way around it. First of all with this approach I'd have to first create all eight children, then check their content (consider if more then two shapes overlap that way), then destroy them - on top of that I'd need to give away the convinient recursive nature of the octree, sinse I'd have to split the node creation and node subdivision in two methods, in order for the nodes not to subdevide until max depth before I can destroy them.
Is there any fast algorythm for this problem?