[Adonthell-devel] Re: New map structure in the making

[Kai Sterker]

Am 01.05.2008 um 22:42 schrieb Kai Sterker:

Sorry for the double-post last time. Didn't notice that the first  
mail went through ...

> There isn't a lot to see yet. Basically, I just have a method for  
> inserting objects, which runs in parallel to the current map  
> generation.

After introducing minimum node sizes and splits that are better  
aligned to our object sizes, I now get something that doesn't looks  
too bad to me:

I've committed the code, in case somebody wants to have a look.

Next on the list would be object deletion and actual object  
retrieval. This needs different approaches for the map view and  
collision code. In case of the collision code, we have an axis  
aligned bounding box (= AABB) that makes it very easy to find objects  
that are worth testing for actual collisions. But for the map view,  
we have a rectangle (the view area) that makes a diagonal cut through  
the octree. Not sure yet how an efficient traversal strategy for this  
could look like.

With retrieval and deletion in place, rebalancing should be fairly  
simple. I imagine that it requires a recalculation of the splitting  
planes. This gives us a couple of AABB denoting the areas that have  
to be moved from one child to the other. For each of those (up to  
seven, depending on how many of the splitting planes we change!), we  
retrieve the enclosed objects, delete them at their old node and  
insert them into the node we've just rebalanced.


More over the next couple weeks. Comments welcome!

Kai