TMap pwnz

TMap is so cool once you understand how to use it. I implemented it for any string-searching routines I have, as well as for an object linking routine.

I'm not sure how you would use this with 3D geometry. You could create a vector object from each entity's position and sort them based on their value on each axis, but I don't see how that is useful.

Let's say I had 1000 entities, each with a known center and dimensions. I want to retrieve all the entities within an arbitrary bounding box. How would I use TMap to do this?

Well TMap is cool, but that's nothing more than a binary tree.
If your sort criteria involves 3 independant values, the best is to have the 3-dimensional version of a binary tree: an octree. Obviously, that means writing the structure yourself, but given how common octrees are in 3D and how involved in 3D you are, that really seems like the logical thing to do.

Well, I did implement an octree but I found that it didn't make much of a difference in the test I was running. It had to have some pretty specific circumstances to get results faster than a linear search.

I was wondering if there was a way to use TMap for this, since it is such a simple and fast routine. It would certainly be nicer than doing all those plane or box tests.

Oct trees are pretty sensitive to input data being nicely 'spread' around.

Instead, you could try a 'k-d tree':

* It's a binary tree - each node has 2 kids.

* Given a 'polgon soup', you do the following:

1) Create a bounding box around the polygons. This bounding box becomes a node in the tree.

2) Work out the maximal axis of the bounding box: x,y or z.

3) Sort the polygons along this axis. This can be done by working out the centroid of each polygon and using the x,y or z component (depending on the maximal axis) as your sorting key.

4) The first half of the sorted list becomes the left hand child of this node, the rest is the right hand child.

5) Repeat recusively, terminating at some minimal polygon count threshold. At these 'leaf nodes', you store the actual polygons in addition to the bounding box.

As far as I can work out, this pretty much beats an oct-tree for most situations - even rendering.

It's not sensitive to 'polygon density' in any particular location, tends to produce regular sized boxes that contain a useful number of polygons, and is very simple to traverse in realtime.

Thanks for the tips.