|
Author Topic:   fanning
brianl
Member
posted November 29, 1999 04:17 AM            
well, i'm in the optimization stages of quasi-roam now, and obviously one such optimization is batching up triangles, whether through stripping, fanning, cvas, display lists (??), etc.

my first approach is with fanning, only because i've seen something vaguely intuitive pop out at me. as i recurse through the bintritrees, i think that if you can pass the test of "if i am split, and my children are split, and their children AREN'T split (ie, are leaves)", then you can render a fan of 4 triangles, emanating from your hypoteneuse and stop recursing. (this may be a bit awkward to visualize). somehow i get the feeling this should be more generalizable, though -- like i am only seeing one very obvious case of a more general truth.

i also see a way to fit this into a tail recursive scheme, but i don't really see what the benefits would be... (assuming vc is actually heeding my request to really inline recursive inline calls up to a depth of 255 -- hmm, wonder if this is bad for the cache?).

of course, you can have even more explicit cases that look deeper ahead (these all assume maximum symmetrical tessellation of your children) - if i am split, and if my children are split, and if their children are split, and if their children are split, and if their children AREN'T split, or in other words, if i have great-great-great-grand-children that don't have children themselves, then i can make a 3 fans, two of 4 tris, and one of 6 tris. (subdivide a triangle 4 times to see this - the fans are two tris and a square).

incidentally, the case of great-great-grand-children without children is no better for fanning than the case of great-grand-children without children. you get a fan of 4 tris in the shape of square, and two triangles on the top and right of the square which are probably more expensive to fan than to just render one by one. it's not until great-great-great-grand-children do you get the next level of "fanning bonus".

the tail recursive implementation involves bubbling back the maximum level of recursion reached, rather than asking downwards if certain conditions are met. although there is some hairiness since leaf tris would no longer render themselves (they would get rendered by their parents or grandparents, or... ? -- i haven't totally though it out yet).

any thoughts?

brian

IP:

brianl
Member
posted November 29, 1999 11:54 AM            
hrmm. it dawned on me in the shower this morning what it means to ask those "do my children's children's children" type questions -- this is somewhat expensive, given that by the time you are asking about you great-great-great-grand-children, you are examining 16 triangles... just seems like the cost might outweigh the benefits. although, it really seems, and i wish i could think it through, that a tail recursive method could somehow solve this problem of having to probe so much at every level of recursion.

oh yeah, there was a type-o in my previous post. i said that if you subdivide a triangle 4 times, you get 3 fans -- two 4 triangle fans, and one 6 triangle square. i was wrong. it's actually an 8 triangle square.

seumas, are you fanning/stripping across tri roots? are you fanning/strippin the root tris (that aren't getting subdidived at all) themselves?

hmm...

IP:

MarkBatten
Member
posted December 01, 1999 08:58 AM            
You may already have read it, but the Graphix3D site (www.grafix3d.tzo.com) has a paper by Stefan Roettger and others that describes a very elegant and simple algorithm that relies heavily on fanning. It's much simpler than either ROAM or the Lindstrom algorithm that others are using, but produces pretty effective results. It fans up to ten triangles and avoids the "generational" problems you describe. Unless you're wedded to your current approach, you ought to check it out.

IP:

LDA Seumas
unregistered
posted December 01, 1999 10:43 AM           
Brian,

I'm fanning using a small fan-buffer, which I start filling with triangles as the first leaf node is encountered during rendering, and continue filling it until the current leaf can't be made part of the fan, at which point the fan buffer is flushed out to OpenGL and the current leaf triangle becomes the start of the buffer again. By alternating child descent orders (left first then right, and at the next level down, right first then left, alternating at each level of the tree) I get triangles in an order that's very conducive to fanning.

Mark,

That looks like a great site, but I can't print out any of the papers there. We don't have a PostScript printer, and no software I have tried will load multi-page PostScript documents for high quality display or printing. If someone could point me to software that would let me print out PostScript documents on our non-PS printer under Windows, I would be very grateful.

Thanks,

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

brianl
Member
posted December 01, 1999 11:29 AM            
seumas,

check out:
http://www.cs.wisc.edu/~ghost/gsview/index.html

(not sure about printing capabilities, but it can certainly display...)

IP:

bdiscoe
Member
posted January 02, 2000 07:01 PM            
> a paper by Stefan Roettger and others that
> describes a very elegant and simple
> algorithm that relies heavily on fanning.
> It's much simpler than either ROAM or the
> Lindstrom algorithm that others are using,
> but produces pretty effective results.

Unfortunately, it doesn't explain how it produces its fans. Since it may descend into up to 4 sub-nodes, i presume there are 16 different cases, some involving drawing 2 strips (e.g. NW and SE). This would be rather complicated, not simple, but there's no way to know if that's what they do since the paper doesn't describe it. They also don't explain how to reference the "neighboring" nodes to know whether to draw edges as 1 or 2 faces... in short, there are big gaps in their explanation preventing implementation. I tried to email the address on the paper, but the email bounced.

Has anyone been able to guess the missing steps in the Roettger paper?

Thanks,
Ben

IP:

LDA Seumas
unregistered
posted January 03, 2000 05:06 AM           
As luck would have it, I got a PostScript printer for Christmas, so I should be able to print out that paper (among others) and give it a look real soon now...

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

MarkBatten
Member
posted January 03, 2000 09:16 AM            
It's actually simpler than what Ben describes, though I can't remember at the moment how it works. As I recall, though, you dig down as deeply as you're going to go before building the fan. I've written an implementation based on the paper that works well; I'll try to remember to look at the code (it's on my other machine) and describe how it works.

IP:

Sam K
Member
posted February 18, 2000 10:09 PM            
we had a representative of nVidia come round the other day (Ge-force.. what a card)
and he mentioned a stripping technique that I hadn't thought of before. It may be that you guys can use it in your (rapid) search for landscape perfection...

Now, you lot are talking about fans with 3 1/2 polygons in them on average... that's not good at all for modern 3d graphics cards which love huge strips & fans (Especially ge-force PSXII etc).

The technique goes as follows:

You can render as many small strips as you like AS ONE STRIP! (i.e one call to "RenderStrip" in whatever API you happen to like.

Lots of small strips can be stitched together to form one strip using "Invisible polygons".

The technique works due to the fact that 3d graphics cards *completely ignore* triangles that have two of their vertices at the same screen location (zero area triangles)

So basically you tack the small strips together by introducing a couple of "zero area triangles" between them.

Its like taking a pen off the paper and putting it back somewhere else and continuing the line.. with only a few extra (invisible) vertices in the list.

This technique is also very cool for rendering leaves on trees, grass etc where otherwise you would have to call a render function once per blade (ouch).

However, I don't know if the technique works with fans or not.
If not, maybe its more apt to being used for a more regular quadtree based implementation than a ROAM based one.

Maybe the render pass of a bintree could somehow use strips instead of fans and stitch them..

Ither way, its usefull for other things than terrain.

Let me know if you have any ideas or results..

regards,

sam

IP:

Sam K
Member
posted February 18, 2000 10:09 PM            
We had a representative of nVidia come round the other day (Ge-force.. what a card)
and he mentioned a stripping technique that I hadn't thought of before. It may be that you guys can use it in your (rapid) search for landscape perfection...

Now, you lot are talking about fans with 3 1/2 polygons in them on average... that's not good at all for modern 3d graphics cards which love huge strips & fans (Especially ge-force PSXII etc).

The technique goes as follows:

You can render as many small strips as you like AS ONE STRIP! (i.e one call to "RenderStrip" in whatever API you happen to like.

Lots of small strips can be stitched together to form one strip using "Invisible polygons".

The technique works due to the fact that 3d graphics cards *completely ignore* triangles that have two of their vertices at the same screen location (zero area triangles)

So basically you tack the small strips together by introducing a couple of "zero area triangles" between them.

Its like taking a pen off the paper and putting it back somewhere else and continuing the line.. with only a few extra (invisible) vertices in the list.

This technique is also very cool for rendering leaves on trees, grass etc where otherwise you would have to call a render function once per blade (ouch).

However, I don't know if the technique works with fans or not.
If not, maybe its more apt to being used for a more regular quadtree based implementation than a ROAM based one.

Maybe the render pass of a bintree could somehow use strips instead of fans and stitch them..

Ither way, its usefull for other things than terrain.

Let me know if you have any ideas or results..

regards,

sam

IP:

Sam K
Member
posted February 18, 2000 10:09 PM            
we had a representative of nVidia come round the other day (Ge-force.. what a card)
and he mentioned a stripping technique that I hadn't thought of before. It may be that you guys can use it in your (rapid) search for landscape perfection...

Now, you lot are talking about fans with 3 1/2 polygons in them on average... that's not good at all for modern 3d graphics cards which love huge strips & fans (Especially ge-force PSXII etc).

The technique goes as follows:

You can render as many small strips as you like AS ONE STRIP! (i.e one call to "RenderStrip" in whatever API you happen to like.

Lots of small strips can be stitched together to form one strip using "Invisible polygons".

The technique works due to the fact that 3d graphics cards *completely ignore* triangles that have two of their vertices at the same screen location (zero area triangles)

So basically you tack the small strips together by introducing a couple of "zero area triangles" between them.

Its like taking a pen off the paper and putting it back somewhere else and continuing the line.. with only a few extra (invisible) vertices in the list.

This technique is also very cool for rendering leaves on trees, grass etc where otherwise you would have to call a render function once per blade (ouch).

However, I don't know if the technique works with fans or not.
If not, maybe its more apt to being used for a more regular quadtree based implementation than a ROAM based one.

Maybe the render pass of a bintree could somehow use strips instead of fans and stitch them..

Ither way, its usefull for other things than terrain.

Let me know if you have any ideas or results..

regards,

sam

IP:

Sam K
Member
posted February 18, 2000 10:16 PM            
Sorry about the two posts, My finger spasmed on the post button..

I thought I'd sent you another to let you know

sam

IP:

Klaus Hartmann
Member
posted February 20, 2000 02:33 PM            
Seumas,

Regarding your Postscript problem. The best program I found to read and print Postscript files is Adobe Acrobat. Of course it costs money, but I wouldn't want to miss it anymore.
If you have Acrobat installed, and double-click a .ps file, then the Acrobat Distiller will automatically convert it into a .pdf file. Sometimes, though, you'll have the effect, that Acrobat cannot translate all charsets/fonts. For example, this is the problem with Röttger's paper. But... this problem will disappear as soon as you print the .pdf file.
I cannot recommend a tool like this enough, because the most interesting papers on the net are usually postscript papers.

IP: