Cuboids

Discussion in 'Plugin Development' started by \\slashies, Feb 12, 2011.

Thread Status:
Not open for further replies.
  1. Offline

    \\slashies

    Many plugins make use of cuboids (3d rectangles) as the basis for deciding where special behaviors take effect. Many also use a brute force search to find the cuboid(s) that an action falls within. Thats terrible, but understandable considering the complexities of 2d indexing.​
    I present to you an alternative:
    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" (comprised of the overhangs and the remainder) we perform the same sort of insert algorithm on them too. If no shards were generated on that loop then it is both minimal and bounded correctly by the node it's in. add that node to the list of targets.

    Generating shards can generate more shards itself. Keep going until every shard has a target node (we avoid a huge list and recursion here with a stack, for the curious). 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.

    [[UPDATE]]

    After a long time away I've updated! I fixed a bug that was in the original release that could cause a cuboid to be counted twice and added a much request feature. Okay two people requested it, but I thank them!

    You may now test a cuboid's intersection with existing nodes in the tree, get a list of all the nodes in the tree that a cuboid intersects, and insert only if the cuboid does not intersect, returning a boolean indicating success (faster than testing then inserting because it uses the same data structures).

    The way that it tests for intersection is that it does a dummy insert. It will not attach newly created nodes to the tree but it does perform the sharding algorithm. Once it knows what nodes it is in it then finds list of cuboids above and below all of it's nodes and performs an explicit intersection test on those cuboids. The algorithm is very simple, it tests the highs vs the lows of both cuboids in each dimension vs the opposite of the other. If A's low in any axis is higher than B's high or vice versa then the cuboids do not intersect. Very simple and fast test made faster by the fact that it only has to test nodes that have any chance of intersecting with it.

    get the latest version at github: http://github.com/doublebackslash/CuboidLocale

    Thanks,
    \\​
     
    deleted_70790 and Asharad like this.
  2. Offline

    Jonbas

    Well done. Thank you very much.

    Perhaps a stupid question on my part: What happens to this if cuboids overlap?
     
  3. Offline

    \\slashies

    It handles this case very well. Each node in the tree keeps a list of all it's involved cuboids. When matching a point it will return all of the appropriate ones.

    If you need priority (because it returns them in no particular order) then when you extend the primitive cuboid class include a field for the priority and sort on the return. Doubtless, lists will be short enough that the sort will only be dealing with a few items and won't add significantly to the overhead.

    Good question!
     
  4. Hm, now I don't really understand how you would go about checking *if* two cuboids overlap.
    I mean, you can't simply search for cuboids overlapping a single point, since they could be overlapping anywhere else of course. But you also can't search for all points inside a cuboid and see if there's another one overlapping it, can you?

    Would be interesting to know ;)
     
  5. Offline

    Jonbas

    I used this code in LocalShops. I wanted to prevent any shops from overlapping, so what I ended up doing was checking every block in the new region to see if it was already inside another cuboid. If everything returned with no overlap, then I created the second cuboid.

    It was extremely fast. Even with checking a couple thousand points against the tree, it took maybe a second or two.
     
  6. Offline

    \\slashies

    Bumped for the update
     
Thread Status:
Not open for further replies.

Share This Page