gdalgorithms-list

[Algorithms] Octree leaf neighbours

[Sam K. <sa...@ip...>]

Hi,

I'm creating an octree, and need to maintain pointers between neighbouring
*leaves*, and do it quick. The only way I can think of is to skip back up
the tree and down the neighbouring branches to locate each of the 6
neighbours. This doesn't seem very fast.

There is a method called "linear octrees" which supposedly let you use the
so called "morton number" to directly hash a neighbour from is location in 3
space. But I believe you *have to subdivide the whole octree evenly* so
every leaf is stored and can be hashed properly. (i.e. a 3d array!). Fat use
since the reason i'm using an octree is to avoid a memory hungry grid in the
first place, or am I missing the point?

Any insights would be appriciated!

Sam.

Re: [Algorithms] Octree leaf neighbours

[Thatcher U. <tu...@tu...>]

On Sat, 15 Jul 2000, Sam Kuhn wrote:

> I'm creating an octree, and need to maintain pointers between neighbouring
> *leaves*, and do it quick. The only way I can think of is to skip back up
> the tree and down the neighbouring branches to locate each of the 6
> neighbours. This doesn't seem very fast.

It's an O(1) operation on average according to something I read somewhere
(I think Hanan Samet proved this in one of his books but I don't have a
reference handy).  The outline of the proof would be something like: half
of the time, the neighbor is a child of the immediate parent (i.e. one
generation from a common ancestor); a quarter of the time the neighbor is
two generations from a common ancestor; an eighth of the time it's three
generations away, etc.  So over a large number of random queries (N), the
cost is proportional to N * sum(i=1 --> N: 1/(2^i)).  Divide out the N to
compute the average cost, and the sum approaches 1 as N approaches
infinity.

So while the traversal may *seem* slow when looking at the code, it
probably isn't as slow as you think.

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] Octree leaf neighbours

[Thatcher U. <tu...@tu...>]

From: Thatcher Ulrich <tu...@tu...>
> [re finding a neighbor in an octree]
> It's an O(1) operation on average according to something I read somewhere
> (I think Hanan Samet proved this in one of his books but I don't have a
> reference handy).  The outline of the proof would be something like: half
> of the time, the neighbor is a child of the immediate parent (i.e. one
> generation from a common ancestor); a quarter of the time the neighbor is
> two generations from a common ancestor; an eighth of the time it's three
> generations away, etc.  So over a large number of random queries (N), the
> cost is proportional to N * sum(i=1 --> N: 1/(2^i)).  Divide out the N to
> compute the average cost, and the sum approaches 1 as N approaches
> infinity.

Woah, I made a mess of the math there.  The expected number of pointer
dereferences in a recursive neighbor-finding query should be, on average:

sum(i=1-->infinity : 2*i / (2^i))

which works out to 4, not 1.  Still O(1), fortunately.

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] Octree leaf neighbours

[jason w. <jas...@po...>]

use a string of bits to name octree nodes: each bit indicates one halfspace
of a splitting plane in sequence, x, y z, somewhat like a kd-tree. So 3 bits
can name each child of an octree node. An int lets you name up to a 10 level
octree, 3 ints a 30 level tree. I'm sure you can see how you can use some
simple logical functions to generate the names of any adjacent cell of
interest.

then you can store a look up table that links named cells to a pointer, so
you'll only have 1 dereference. Somehow, I don't think any speed increase
would be worth the complication.