Re: [Algorithms] VIPM, VDPM, ROAM questions

[Alex P. <res...@gt...>]

Maybe I will have time someday to write a paper on the wonderful
properties of bintrees, but I dont think that day will be soon.
So in the mean time here are a couple useful features that help get an
efficient Bintree based CLOD scheme:

Implicit iteration:

To answer Joe's question:
Iterating over all the triangles in a crack free bintree is easy if you
index
your tree correctly, assuming you use implicit bintrees and the array index
is your triangle index.   Each level N of the bintree starts at index 2^N.

Eg. lets start from the top you have a signle triangle with index
 1
if it gets split you have
(2 3)
if 2 gets split you have
((4 5) 3)
If 5 gets split you have
((4 (10 11)) 3)
Note that this is impossible since you can only have one of
difference between neighbouring triangles.  So to avoid a crack
you will have split 3 as well to produce:
((4 (10 11)) (6 7))
To render this bintree you simply descend from 1 until you
find the 1st 'active' triangle, then increment the index until
the neighbour is not 'active' in which case you need to either
descend one level (index *=2) or ascend one level
(index /= 2) and continue until you reach the other end of the bintree.
Draw it on paper (as I did) and you will see it works, it took me a while to
come
up with. I didn't know others had already discovered this neat property
of bintrees, sadly it is not possible to render as a tri strip (unless you
include
degenerate triangles).  I used a little MRU cache to track the last 10
vertices
and got about as many triangles as vertices which I found acceptable.

High Level LOD or Free detail:

There is another useful property of bintrees.  If you have a mesh M which
is a crack free bintree, you can split every triangle in M and produce M'
which
will have twice as many triangles, but is not crack free.  However if you
split
M' to get M", you will have 4 times the original number of triangles and M"
is also guaranteed to be crack free.
This means you can do you LOD at the level of M and over render by a factor
4 or 16 or 64 etc.  This is what DDG does, when I render 16000 triangles I
only
perform LOD on 1000 of them.  I am trading off extra LOD calculations on the
CPU for extra triangles on the GPU.   A trade that is well worth it.

Alex Pfaffe

----- Original Message -----
From: "Joe Ante" <Jo...@Ti...>
To: <gda...@li...>; "Mark Duchaineau"
<duc...@ll...>
Sent: Tuesday, March 06, 2001 6:11 AM
Subject: Re: [Algorithms] VIPM, VDPM, ROAM questions


> Mark,
> > 2) The triangle bintree hierachy has a very easy way to walk
> > the tree to get one generalized strip, which is ideal for
> > maximizing vertex-cache coherence on a GPU.
> I am highly interested in how to create this one strip, specifically how
to
> create this one generalized strip incrementally ?
>
> Thanks in advance
> bye joe
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list