Jump to content

  • Log In with Google      Sign In   
  • Create Account


Octrees


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
15 replies to this topic

#1 daniel_i_l   Members   -  Reputation: 295

Like
0Likes
Like

Posted 06 January 2007 - 06:30 AM

I'm thinking about using octrees for collision detection. my question is: what do i do to bodies that are moving? do i take them out of the tree and put them back in every frame? or do i give the body a pointer to the cell it's in so that it can check if it's still inside and only remove itself when it has to? what's the best way? Thanks.

Sponsor:

#2 krum   Members   -  Reputation: 255

Like
0Likes
Like

Posted 06 January 2007 - 06:37 AM

You can do it either way. Checking to see if you can move the object without changing the tree around is an optimization - but usually it's a simple one, so get it working first by removing the object from the tree and adding it back in, then optimize it.

#3 Raghar   Members   -  Reputation: 92

Like
0Likes
Like

Posted 07 January 2007 - 01:28 AM

If body will not move, it will stay in the cell of the tree. If you meant something like a creation of an octree in every frame, then it's waste of resources.

In fact object doesn't need a reference at the octree cell, it might be actually dangerous if you'd implement merging of octree cells, it knows in what cell it's because it knows its own position, so the only requirement is a test if the object crossed cell boundary.

Actually octree have few bad properties.

  • They are wasting memory.
  • Quad tree is often sufficient.
  • Spanish moss is often better.
  • Clutter in the middle.

  • #4 Rockoon1   Members   -  Reputation: 104

    Like
    0Likes
    Like

    Posted 07 January 2007 - 03:52 PM

    Quote:
    Original post by Raghar
  • They are wasting memory.


  • Tree's don't necessarily require any parent or child pointers if you do not plan on using tree rotation/reordering techniques. If memory is a concern consider how much can be saved with an implicit tree structure - 16 or more bytes per node can be eliminated from a quad-tree and 32 or more bytes per node from an oct-tree. Granted that an implicit tree reserves space for empty nodes, this is still often a reasonable tradeoff.

    Implicit tree structures additionally offer operations that are not computationally feasable with explicit structures. You basically get all the linear O(1) and O(n) benefits of uniform grids while additionally getting many of the O(log n) and O(n log n) walking benefits of a tree.

    I do agree that for most 3D games quad-tree's are a lot more efficient memory-wise than oct-tree's since the gaming field is often a pancake.

    #5 Christer Ericson   Members   -  Reputation: 819

    Like
    0Likes
    Like

    Posted 07 January 2007 - 07:50 PM

    Quote:
    Original post by Rockoon1
    Tree's don't necessarily require any parent or child pointers if you do not plan on using tree rotation/reordering techniques. If memory is a concern consider how much can be saved with an implicit tree structure - 16 or more bytes per node can be eliminated from a quad-tree and 32 or more bytes per node from an oct-tree. Granted that an implicit tree reserves space for empty nodes, this is still often a reasonable tradeoff.
    Implicit trees do not require dense storage. You can have sparse implicit trees by hashing on the location key of a node. Not surprisingly, we called this the hashed storage method for (implicit) trees.

    Quote:
    Implicit tree structures additionally offer operations that are not computationally feasable with explicit structures. You basically get all the linear O(1) and O(n) benefits of uniform grids while additionally getting many of the O(log n) and O(n log n) walking benefits of a tree.
    Correct. But it's worth noting that hierarchical grids practically have additional benefits on top of implicit trees, most notably that you're not wasting search effort on an often-empty top of a tree.


    #6 Rockoon1   Members   -  Reputation: 104

    Like
    0Likes
    Like

    Posted 08 January 2007 - 07:13 AM

    Quote:
    Original post by Christer Ericson
    Implicit trees do not require dense storage. You can have sparse implicit trees by hashing on the location key of a node. Not surprisingly, we called this the hashed storage method for (implicit) trees.


    Ah. Good idea. Had not considered this strategy.

    My first instinct when implimenting an implicit tree with a large node structure is for the tree to hold pointers to the node structure (overhead of 4 bytes per node) which is no better than anti-collision overhead with your hashing strategy.

    Obviously the hashing method only has overhead for populated nodes so its a big footprint win vs my instincts. I am wondering about cache performance however. Do you use a hash function which maintains locality?

    [Edited by - Rockoon1 on January 8, 2007 1:13:31 PM]

    #7 playmesumch00ns   Members   -  Reputation: 190

    Like
    0Likes
    Like

    Posted 09 January 2007 - 10:12 PM

    Quote:
    Original post by Christer Ericson
    Quote:
    Original post by Rockoon1
    Tree's don't necessarily require any parent or child pointers if you do not plan on using tree rotation/reordering techniques. If memory is a concern consider how much can be saved with an implicit tree structure - 16 or more bytes per node can be eliminated from a quad-tree and 32 or more bytes per node from an oct-tree. Granted that an implicit tree reserves space for empty nodes, this is still often a reasonable tradeoff.
    Implicit trees do not require dense storage. You can have sparse implicit trees by hashing on the location key of a node. Not surprisingly, we called this the hashed storage method for (implicit) trees.

    Quote:
    Implicit tree structures additionally offer operations that are not computationally feasable with explicit structures. You basically get all the linear O(1) and O(n) benefits of uniform grids while additionally getting many of the O(log n) and O(n log n) walking benefits of a tree.
    Correct. But it's worth noting that hierarchical grids practically have additional benefits on top of implicit trees, most notably that you're not wasting search effort on an often-empty top of a tree.


    Can you describe the hashed-storage implicit tree structure in more detail? I'm very interested in using this in some code I have already that relies on an octree...


    #8 Christer Ericson   Members   -  Reputation: 819

    Like
    0Likes
    Like

    Posted 10 January 2007 - 06:10 AM

    Quote:
    Original post by playmesumch00ns
    Can you describe the hashed-storage implicit tree structure in more detail? I'm very interested in using this in some code I have already that relies on an octree...
    You should just search for "location code" but, in short, a location code is a "street address" of a node in an octree/quadtree. You can form the location code in several different ways, but a simple one (for this particular purpose) is to concatenate, each time you move to an octree cublet, three bits representing which cubelet you moved to (000, 001, through 111). These are concatenated into a bitstring that's initially 1, so as not to lose leading zero bits if your first move is to e.g. 010. (This is not the most sophisticated location code but it's easy to explain, so do search for info on other variants.)

    Once you have the location code of the leaf cell, you treat it as a normal hash key into a hash table, wherein you store the leaf node contents. Nothing more complicated than that.

    To rockoon1: it's hard to find a hash mapping that's both cache-coherent and has a good distribution to avoid worst-case behavior, thus I just use a "normal" hash mapping. So, yes, there's an extra indirection for each leaf-node lookup for the hashed-storage vs. the complete-storage linear octree, likely causing one extra cacheline miss. That's pretty much the usual time/space tradeoff though. It's still vastly superior to a traditional pointer-based tree, which can have a cache miss every time you go down a level of the tree (in the most naive implementation).



    #9 playmesumch00ns   Members   -  Reputation: 190

    Like
    0Likes
    Like

    Posted 10 January 2007 - 09:48 PM

    OK gotcha. So you just use the location code to lookup the hash table to get the actual memory address of the node contents in the sparse tree?

    #10 Christer Ericson   Members   -  Reputation: 819

    Like
    0Likes
    Like

    Posted 11 January 2007 - 05:03 AM

    Quote:
    Original post by playmesumch00ns
    OK gotcha. So you just use the location code to lookup the hash table to get the actual memory address of the node contents in the sparse tree?
    Yes, if I follow you correctly. Restated: you have a linear octree. You traverse it to a leaf, forming a location code. At this point you hash the location code into a hash key, said hash key you use to look up an array entry in your hash table where you'll find the leaf node contents stored.



    #11 Tachikoma   Members   -  Reputation: 548

    Like
    0Likes
    Like

    Posted 11 January 2007 - 01:56 PM

    Quote:
    Original post by Raghar
    Spanish moss is often better.

    I never heard of that one. Could you elaborate?



    #12 Christer Ericson   Members   -  Reputation: 819

    Like
    0Likes
    Like

    Posted 11 January 2007 - 06:05 PM

    Quote:
    Original post by Tachikoma
    Quote:
    Original post by Raghar
    Spanish moss is often better.

    I never heard of that one.
    Don't feel bad, no one else has either!

    Quote:
    Could you elaborate?
    Apparently it refers to what's described here: http://mindprod.com/jgloss/hangingmoss.html

    What's described therein is just a uniform grid and a not particularly clever algorithm for finding the point in a set of points closest to a given query point.

    The "hanging/Spanish moss algorithm" is likely to work okay for point sets that are reasonably uniform, but will fail miserably on others. For nearest-point queries of this kind, a k-d tree is generally the data structure of choice and the nearest-neighbor algorithm on a k-d tree is described in e.g. the original paper on k-d trees (link is not quite to the original paper, but a tech report version of same). Of course, you don't need to use the algorithm on a k-d tree; you could equally well use it on e.g. a uniform grid (or an octree, perhaps linear), and it would perform much better than that mossy algorithm.

    Edit: added missing quote in URL, thus fixing funny formatting.


    [Edited by - Christer Ericson on January 12, 2007 2:05:29 AM]

    #13 Tachikoma   Members   -  Reputation: 548

    Like
    0Likes
    Like

    Posted 11 January 2007 - 08:57 PM

    Thank you, that makes more sense now! :)

    (I'm also investigating various space partitioning methods for my future implementation.)



    #14 Raghar   Members   -  Reputation: 92

    Like
    0Likes
    Like

    Posted 12 January 2007 - 07:17 AM

    Quote:
    Original post by Christer EricsonApparently it refers to what's described here: http://mindprod.com/jgloss/hangingmoss.html

    What's described therein is just a uniform grid and a not particularly clever algorithm for finding the point in a set of points closest to a given query point.

    Actually it's an implicit grid, it doesn't need to be uniform. (as long as there is a working mapping function) Inside of each node of the grid is a structure with real objects, or whatever programmer wants. In fact it could have a different structure in each node, like quadtree, BSP tree, patricia trie, arrays of sorted objects.

    Now the main advantage is: loading data from HD into RAM is straightforward and nice for cache. In fact it works wonders for continuous worlds.

    Have you ever tried to create a destructible terrain?

    #15 Christer Ericson   Members   -  Reputation: 819

    Like
    0Likes
    Like

    Posted 12 January 2007 - 06:27 PM

    Quote:
    Original post by Raghar
    Actually it's an implicit grid, it doesn't need to be uniform.
    No, what is described on that page is exactly what I said: a uniform grid. Furthermore, each grid cell contains a linked list of the objects mapped to that cell. These two observations follow immediately from the statement "The heads of each of the grid chains live in a matrix" (as well as from other statements on that page).

    An implicit grid has no explicitly dedicated per-cell storage. Therefore, what is described on that webpage could not possibly be an implicit grid as the use of the word "matrix" ascertains he's talking about explicit storage.

    #16 Rockoon1   Members   -  Reputation: 104

    Like
    0Likes
    Like

    Posted 12 January 2007 - 07:47 PM

    Quote:
    Original post by Christer Ericson
    You should just search for "location code" but, in short, a location code is a "street address" of a node in an octree/quadtree. You can form the location code in several different ways, but a simple one (for this particular purpose) is to concatenate, each time you move to an octree cublet, three bits representing which cubelet you moved to (000, 001, through 111). These are concatenated into a bitstring that's initially 1, so as not to lose leading zero bits if your first move is to e.g. 010.


    I've done some experimenting.

    A slight variation on this removes the need for the root '1' prefix

    childNodeKey = (thisNodeKey << 3) + i;

    where i = 1..8

    In your method, i = 0..7, creating the need for a that root stop bit.

    This matches my previous array-based implicit tree methodology.

    The advantage is that without the root stop bit, you can move between a hash-based strategy and an array-based strategy without changing the key.

    The upshot is that for the nodes near the root (say up to depth 6) you can work directly off an array, avoiding any hashing. Since the nodes near the root are accessed the most when doing queries, it might make sense to avoid both the hashing and random memory accesses involved at the top levels.

    It certainly seemed to have a performance impact on my test algorithm (nearest neighbor query) which was seeded with a uniform distribution of random points in 3-space. This was with managed code under .NET 2.0 using the generic hash table so milage may vary.

    Probably premature optmisation on my part.. but thats more or less what I do! :)





    Old topic!
    Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



    PARTNERS