gdalgorithms-list

Re: [Algorithms] Octree leaf neighbours

[<SHA...@ao...>]

In a message dated 15/07/00 20:59:35 !!!First Boot!!!, sa...@ip... writes:

<< 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.

Surely you mean 7 neighbours?

 
<< 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.
>>

Looks like you need to provide a 'pointer to parent node' member in your 
structure to allow you to go back up a step and access the current nodes 
neighbours.

In my original octree implimentation I had such a pointer but later found I 
didn't need it so I took it out.

Why do you need access a parent nodes neighbours at this point?

Your code should have dealt with that node when it was 'in play' during the 
recursive traversal procedure.

You must know of course that when you are looking at a particular node you 
have access to all of it's children or as you call them, neighbours.

Maybe I am missing something here, but isn't your octree traversal recursive?

Each node that you subdivide, are you subdividing it into 8 equal parts?


And yes you are right, if you use a linear octree you will be creating many 
more nodes than you need.

Regards,

John. 

Re: [Algorithms] Octree leaf neighbours

[Martin G. <bz...@wi...>]

And in addition you can save much time if you hold the tree in an array. This
saves the parent links, too :)

-----Original Message-----
From: Thatcher Ulrich <tu...@tu...>
To: gda...@li...
<gda...@li...>
Date: 16 Þëè 2000 ã. 16:49
Subject: Re: [Algorithms] Octree leaf neighbours


>
>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
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Octree leaf neighbours

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

John,

I'm sure I mean six. Above,Below,Left,Right,Forward and Back. (Don't care
about diagonals).

Yes I am recursing through the tree, and yes each node is "in play" during
the traversal. But I'm doing a "marching cubes" type of thing, I need to
share vertices between nodes. To do that I need to look at my neighbours,
see if they have been processed, and if so use their vertex instead of
generating a new one.

Yeah, If I store a pointer to parent I can traverse "up and round" to find
my neighbour. But whether this will save me any time over just generating
new vertices and not sharing. Time to suck it and see.

Thanks,

Sam.





-----Original Message-----
From: SHA...@ao... <SHA...@ao...>
To: gda...@li...
<gda...@li...>
Date: 16 July 2000 9:47 AM
Subject: Re: [Algorithms] Octree leaf neighbours


>In a message dated 15/07/00 20:59:35 !!!First Boot!!!, sa...@ip...
writes:
>
><< 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.
>
>Surely you mean 7 neighbours?
>
>
><< 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.
>>>
>
>Looks like you need to provide a 'pointer to parent node' member in your
>structure to allow you to go back up a step and access the current nodes
>neighbours.
>
>In my original octree implimentation I had such a pointer but later found I
>didn't need it so I took it out.
>
>Why do you need access a parent nodes neighbours at this point?
>
>Your code should have dealt with that node when it was 'in play' during the
>recursive traversal procedure.
>
>You must know of course that when you are looking at a particular node you
>have access to all of it's children or as you call them, neighbours.
>
>Maybe I am missing something here, but isn't your octree traversal
recursive?
>
>Each node that you subdivide, are you subdividing it into 8 equal parts?
>
>
>And yes you are right, if you use a linear octree you will be creating many
>more nodes than you need.
>
>Regards,
>
>John.
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Octree leaf neighbours

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

Thatcher,

Ta for the reasurance, I'll give it a go and see what kind of speed I get.

The thing is, at the moment I'm not actually "storing the tree". I'm just
traversing it.  I need to share vertices between neighbouring leaves, and if
the only way to do this is by physically storing the tree and "jumping
around" to find the neighbour, so be it.

Thanks,

Sam.



>
>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
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Octree leaf neighbours

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

>Martin Gladnishki wrote:
>And in addition you can save much time if you hold the tree in an array.
This
>saves the parent links, too :)

Erm, I mentioned this in my origional post... dont you have to store a 3d
(i.e. *big*) hash table so you can hash to the neighbours in the array using
the coordinates of the node you are in?
How does it save the parent links then?

sam

Re: [Algorithms] Octree leaf neighbours

[Michael K. <neg...@ea...>]

Sam,

 Array traversal is actually just simple math using indexes.

 let me illustrate with a 3x3x3 array that is squashed down into a one
dimensional array.

bottom     middle            top
0 1 2   |    9 10 11    |   18 19 20
3 4 5   |   12 13 14   |   21 22 23
6 7 8   |   15 16 17   |   24 25 26


to get from the bottom layer to the middle layer you just have to add 9 to
the index, to go the right neighbor add 1, bottom neighbor add 3, left
neighbor subtract 1, etc.. I've used this in a quadtree terrain algorithm to
traverse from the top node all the way down to the lowest layer all within a
single array that was logically 256x256 and only using simple math. I'm sure
you can extend it into 3 dimensions, but it may not work for an octree very
well since it would require the octree to be fully divided, depending on
your reason for using an octree of course. You can also test if an index is
negative to traverse into neighboring arrays, usefull for patching terrain
together.


----- Original Message -----
From: Sam Kuhn <sa...@ip...>
To: <gda...@li...>
Sent: Sunday, July 16, 2000 12:29 PM
Subject: Re: [Algorithms] Octree leaf neighbours


> >Martin Gladnishki wrote:
> >And in addition you can save much time if you hold the tree in an array.
> This
> >saves the parent links, too :)
>
> Erm, I mentioned this in my origional post... dont you have to store a 3d
> (i.e. *big*) hash table so you can hash to the neighbours in the array
using
> the coordinates of the node you are in?
> How does it save the parent links then?
>
> sam
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Octree leaf neighbours

[Martin G. <bz...@wi...>]

Sorry, it's my fault. I was addressing regular octrees and my point was that
implicit representation lets you avoid the parent links. Of course this does
not apply yo your case. Apologies :)

-----Original Message-----
From: Sam Kuhn <sa...@ip...>
To: gda...@li...
<gda...@li...>
Date: 16 Þëè 2000 ã. 22:40
Subject: Re: [Algorithms] Octree leaf neighbours


>>Martin Gladnishki wrote:
>>And in addition you can save much time if you hold the tree in an array.
>This
>>saves the parent links, too :)
>
>Erm, I mentioned this in my origional post... dont you have to store a 3d
>(i.e. *big*) hash table so you can hash to the neighbours in the array using
>the coordinates of the node you are in?
>How does it save the parent links then?
>
>sam
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Octree leaf neighbours

[<SHA...@ao...>]

In a message dated 16/07/00 19:19:50 !!!First Boot!!!, sa...@ip... writes:

<< John,
 
 I'm sure I mean six. Above,Below,Left,Right,Forward and Back. (Don't care
 about diagonals).
 
 Yes I am recursing through the tree, and yes each node is "in play" during
 the traversal. But I'm doing a "marching cubes" type of thing, I need to
 share vertices between nodes. To do that I need to look at my neighbours,
 see if they have been processed, and if so use their vertex instead of
 generating a new one.
 
 Yeah, If I store a pointer to parent I can traverse "up and round" to find
 my neighbour. But whether this will save me any time over just generating
 new vertices and not sharing. Time to suck it and see.
 
 Thanks,
 
 Sam.
  >>

Sorry about that, I obviously misunderstood your question.

Currently what I do is give every triangle an index number, I don't store the 
actual vertices in the octree.
I then create an array of boolean variables, one for each tri, and set them 
all to false.
When I do the visibility check, if a tri is in a visible node then I flag 
that boolean element to true.
This is done, what I will do next....
Finally when the visibility test is finished, for every tri that has a true 
flag it's 3 verts are copied to a vertex buffer.
The triangles are all random except for one important thing, they are in 
texture order.
This means I will be able to do the minumum amount of settexture renderstates 
since they will all be in order in the vertex buffer, and I will draw them 
with DIPVB.

that's when I get some spare time! :)

Regards,

John.