A Little Math

Discussion in 'Resources' started by \\slashies, Jan 6, 2011.

Not open for further replies.
1. Offline

\\slashies

This is something that I see come up a lot.
Problem: You need to determine if a point in question lies within a specified rectangular prism (cuboid).
The plugin which shares the the name with the construct does this by brute force. Unsatisfactory.

I don't know the best method, since the cuboids can overlap, but here is the general outline of the algorithm I'm working on:

• Take your collection of cuboids. For each define the bounding sphere.
• Define two widely separated points, lets call them A and B (I'm using 0,0,0 and 100K,100K, 1K just for nice round numbers. In practice they could be chosen more cleverly, but first the problem at hand)
• Find the point closest to each point lying on each sphere (two points per sphere)
• Find the distance to those points for their respective sphere and sort the spheres into two lists based on their distance to each point.
• Each sphere stores two sorted lists of "peers", one per base point. This is the list of spheres which "overlap" with this one. By this I mean that the maximum distance and the minimum distance of the two sphere from the point (near and far side if you drew a line from the point through each sphere's center) overlap.
That is the setup, and every new cuboid added needs to be inserted into the list at the proper point. Considering that sorting algorithms are O(nlog(n)) and determining peers is just a little slower than that with some clever optimizations that is fast enough for such rare events (compared to lookups)

To determine if you are in a cuboid at a give point:
• Perform a binary search on each list of spheres, finding the two spheres that the point is closest to on each list. O(log2(n))
• Since we used the near points when sorting the list we only care about the one that we are bigger than.
• Check if the point is even within the near / far range of the sphere. If not, then we are certainly not within any cuboid. Return a negative match. This gives the algorithm a best case run time of O(log(n)) even if we don't do any clever caching of results (which we can, but that is another discussion)
• If we DO fall within the range of a sphere on both lists then we have to compare these two points (and their lists or peers)
• Perform an intersection of the two lists of peers to produce a list of potentials. On two sorted lists this is linear.
You now have a much smaller list of potential matches than the whole. The slowest part is the merge of the two lists, but each list comparison takes less cpu power than the six tests require to determine if you are within a cuboid (3 axisis, a <= testPoint <= b). Test each one individually and if you like do a clever cache of your results. I'd prefer to return the list of matches (if more than one) sorted by volume (specific gets first dibs) but at this point that is left to the individual need of the plugin.

For the clever cache I suggest finding a cuboid that encompasses as much empty space as possible (for non matches), the matches cuboid(s), or a cuboid that encompasses all the matches. This way while a player is in a known area their results will return in O(1) runtime or slightly moer if you have to further test a short list of cuboids.

Any thoughts? Is this algorithmically correct? Is there a faster method that I'm not seeing or finding?

Let me know.

#1
2. Offline

#2
3. Offline

\\slashies

Hard to be sure, but it looks like a good r tree implementation (like you provided) is faster than anything I can come up with. Might have about the same worst case, but better average run times. Thanks 10**6 for the github link. I'll put it use use immediately.

If I come up with anything good and useful I'll put the link to it in this thread.

Back to the day job for the moment!

#3
4. Offline

Raphfrk

An R-tree looks like the best plan.

A binary R-tree would just have to pick a plane (axis aligned) to do the split.

Cuboids could be placed on one side or another based on which side their midpoints were.

Something like

- pick a cuboid at random
- pick a cutting plane that goes through the cuboid's midpoint
- partition the cuboids into 2 groups based on which side of the plane their midpoints fall on
- store the bounding box of paritiion
- recursively apply the algorithm on each sub-group using alternating planes

Adding and removing shouldn't be to hard. Keeping the tree balanced would require some effort.

An easy solution would be to keep track of the tree depth and if it gets larger than 2-3 times the optimal depth, re-balance that node by breaking it up into a single group of starting again.

I don't think self-balancing works very well in 2d (and worse in 3d).

Also, it is likely worth spending more time up front to create the tree, since testing if a point is in a cuboid happens much more often than new cuboids being added and removed.

#4
5. Offline

\\slashies

I present to you this:
https://github.com/doublebackslash/CuboidLocale

Here is how it works:
Its a quadtree. Know what that is before continuing.

Nodes are sized by powers of two.

Cuboids (for which there is a base class suitable for extending included in the source) are inserted based on their lower left hand corner (in the x (left-right) and z (up-down) axis. we ignore the y axis for the tree since it is so short and therefore including it would only complicate things for very little gain) AND the size of the largest axis (in the x-z plane).

Starting at root we test if the root is large enough to hold the cuboid, if not we re-pot the tree to the next largest node (deciding which quadrant of the new root that the old root will be based on the direction that we need to grow in).

Once we've got a suitable root we begin a proper insert:
• Test if the node is minimal for the cuboid. That is, test if the largest dimension of the cuboid could fit in the next size down node.
• If not, we have our target, end the loop.
• If so, pick the quadrant that the lower left hand corner of the cuboid falls in and set that as our current target
Note that isn't recursive, it's a loop. No recursive functions in this at all.

Now that we have our node we must see if the whole thing actually falls into this minimal node. Since we placed by the lower left corner we only have to test if anything overhands the top, right, and top-right. Once we have the list of "shards" we perform the same sort of insert algorithm on them too.

This can generate more shards itself. Keep going until every shard has a target node. We then add the original cuboid to the list of cuboids for each node AND create links in each one's children to that node as the next list holder.

On creation of a node the children either recieve the node as it's next list holder (if it holds any cuboids) or the parent's link. This lets us skip empty lists and terminate quickly on search.

The cuboid is now in the most specific set of nodes it can be.

Deletion is almost the same except that instead of adding the cuboid to the lists we delete it and instead of making the children link to the parent we make it link to the parent (if it still holds cuboids) OR to the parent's link.

Notice that this creates a terribly unbalanced tree and uses more memory than if we inserted the cuboid into the smallest node that it already happened to be inside. First: it does not use much more memory (for the number of cuboids seen on the largest servers you will barely notice the memory bump) and the memory used gains speed, delicious speed.

The search algorithm will shed light on why a horribly unbalanced tree is no big deal.

To search for cuboids that a point falls within first do a simple search on the tree, ending on the lowest node that already exists. Then look at the list of cuboids for that node. Perform an explicit test on them and add them to the return list. Then look at the next list holder, if it isn't null go to that one and check those to. Repeat until you are out of list holders. Return the list AND the node that you landed in.

Next time you do a search for that character you will likely be nearby (or in the case of actions that have to test this a lot, you won't have moved). Instead of starting at root, start at the previous node and test if the point falls within the scope of the node. If not, move up till you are in scope and then perform a normal search from there. This gives locality to the searches. With 100,000 nodes in a 1000x1000 area a random walk of 1,000,000 steps with each step changing the point by -64-64 in each dimension (and then testing at each step) returns in about 3 seconds on my desktop machine (Core 2 processor at 2.4Ghz, DDR2 memory. Forget the memory speed, but it's not great)

Since we insert each cuboid into it's minimal node (and each shard into it's minimal node) we limit the cuboids tested to only those that have a good chance to contain this point. On non-overlapping similarly sized cuboids this number will be very very small or zero.

The break even point for the processing power to search the tree and find only the needed cuboids to test is around 16 or less depending on their geometry.

I hope that many will find this useful. Let me know what you think.

Thanks,
\\

#5