RE: [Algorithms] H-Grids vs. Loose Octrees (was R-Trees)

[<Chr...@Pl...>]

Charles Bloom wrote:
>Thanks for the educational response!
>
>At 01:30 AM 10/12/2000 -0700, you wrote:
>> Phrased differently, the hgrid is just the last
>>K plies of the octree, for some K. This is the important distiction.
>
>Ok, this is a good point.  Whether you see it as a key distinction,
>or just an optimization to the octtree, traversing from the bottom and
>leaving the top un-allocated is a good idea (which level you can use as
>the "top" depends on the largest object in your game).

Note that with my hashed hgrid scheme there is no fixed top level. You
only have as many levels as you need (up to your largest object), and
no more. When you allow it to infinitely tile the world, there is no
largest cell, so you can handle any size objects, by dynamically
incrementing and decrementing the number of levels that you have
to search through.

The only parameter that you are setting for this type of hgrid is
the cell size at the lowest level (and possibly a magnification
factor, if you're not happy with the rather typical x2 one).


>[...]
>Hmm.. I hadn't realized this; I thought you were wrapping like Reinhard
>et.al.  Anyway, this presumably means that when you look in a bucket,
>you get objects from the cell you want, and some from the cell you don't.
>For collision detection, you can just send all these objects at a
bbox-bbox
>test (or something) and the wrong ones will get tossed out correctly.

Yes, this is correct. Depending on your application you either have to
deal with this or its something that you can completely ignore.


>[...]
>The only disadvantage of hashing seems to be poor cache performance.  In
>a normal grid, when you look at the neighbors, they're usually right there
>in cache because of the linear organization of the grid.  In a hash, the
>neighbors could be anywhere, so you generally have to do memory fetches.
>Probably not a big deal.

Again you're correct. But, no, it's not a big deal. As the linked lists
inside the grid cells are likely to be pointing all over memory anyway,
the cell hashing roughly amounts to one extra link traversal (memory
fetch) per cell. It's not something I lose sleep over!


>>>In reality, this is only a problem if your number of objects (N)
>>>gets very large and very irregularly distributed.
>>
>>I can only assume that you are assuming the grid size somehow corresponds
>>to the number of objects here.
>
>Yeah, let me go through the whole argument. [...]

I figured that was what you were trying to say. It was just the "waste
memory in empty nodes" comment that I objected to. Wasted space is only
an issue of you allocate the grids as arrays (like in the Reinhard paper).
My hashing scheme doesn't have "empty nodes" in this sense.

You still need to make sure that you keep the contents of the hash
buckets at some constant level, of course, but the memory for this is
such a small fraction of keeping the grids as arrays that it never
becomes an issue.



Christer Ericson
SCEA, Santa Monica