RE: [Algorithms] VIPM With T&L - what about roam

[Tom F. <to...@mu...>]

Cool. I'll have a look at the second one of those. The first one
(skipstrips) was discussed here a while back, and led to me burbling this,
which bears repeating for those who recently joined us (especially as
someone asked for it):

<<
Hmmmm... interesting. And got me thinking.

I have a bit of a knee-jerk response to strips, because of their
worse-than-list vertex caching (up to twice as bad). However, since normal
VIPM pretty much destroys the vertex cache anyway, this argument doesn't
hold much water!

I think the fundamental difference this approach takes is abandoning the
attempt to ditch collapsed tris as early as possible, which is what forces
the re-ordering of the tris that destroys the vertex cache performance of
"standard" VIPM. And thinking about it, that's fair enough. This still bins
tris, but by making them degenerate, rather than have them fall off the end
of the list and not feeding them to the chip at all. So you still incur the
cost of sending the indices, but not the clipping, setup costs, etc
associated with a triangle.

But of course the bandwidth cost of the indices is tiny compared to the
bandwidth of the vertices, and if by sending (say) double the number of
indices, you can reduce the number of vertex resends (i.e. how well the
vertex cache is working) by even a small amount, you win! The rejection of
degenerate tris is lightning-fast (done right at the front-end I would
assume - three 16-bit compares), and in parallel with all the "expensive"
stuff, so doubling the number of times it does that is not going to affect
performance in any measurable way I would guess.

So having stated that I dislike strips, I see no reason not to switch the
algorithm back to using indexed lists. Arrange your lists optimally for
cache use, and do as the algorithm below says - make the binned ones
degenerate, and move the others, just like a normal VIPM rout. The only
difference from the routine that Charles has in his tutorial is that you
don't reduce the number of tris, and when generating the change list, you
need to include an index change that makes the binned triangle degenerate.
Wow - that's pretty easy, and vertex cache efficiency is nicely maintained
all the way through the collapses.

A few points that need mulling over:

(1) Using indexed lists, you need to make more index changes per collapse
than for strips. Three times as many, I think - not 100% sure. This means
slightly larger collapse information, slightly more of a cache hit. However,
the collapse info is linear, and so very cache-friendly, and since the aim
is to be vertex-cache friendly with our tris, the indices that need changing
are likely to be close together as well, or at least in just two parts of
the index list, so again fairly cache-friendly (remember - it's stepping
outside the cache _once_ that hurts - subsequent accesses to that area are
very cheap). So actually not much more expensive than strips I think. And
better vertex cache performance (using the "fractal gasket" traversal method
that I still can't figure out for arbitrary meshes).

(2) Once a tri has been made degenerate, does it need to be involved in
further collapses? For example, once a tri 1,2,3 has been made into 1,1,3,
do we need to update it when a subsequent collapse bins vertex 3? On some
hardware, the degenerate rejection may be done right up-front on the
indices, and that triangle never makes it any further, so even though it
references vertex 3, because no non-degenerate tri ever references it,
vertex 3 is never loaded. However, some hardware may not do the rejection
until after the vertex cache fetch, which means that vertex 3 gets fetched,
and possible T&L'd, even though it is then never used. If the latter, then
you may be better off doing slightly more index edits to "fix"
already-degenerate tris so that they only reference used vertices, and
having more collapse info. Tricky - I can't decide which option has the
worse worst-case performance. Maybe having both versions and runtime testing
at load time would be the best option.

Compared to "my" two-part method, I think it's a lot simpler. The more I
think about the two-part scheme, the more I spot gotchas, and tris that need
including in the "slow" pool, the more fragmented the remaining "static"
tris get (more fragmentation = less vertex-cache coherency).

The advantage that my two-part method retains is the ability to share lots
of the index data between instances of objects, which will be a definate
advantage in some cases. But it is more complex, and my feeling is that it
will achieve poorer vertex caching than this new method.
>>

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Brian Marshall [mailto:bma...@ra...]
> Sent: 12 September 2000 18:28
> To: gda...@li...
> Subject: RE: [Algorithms] VIPM With T&L - what about roam
> 
> 
> I've come across 2 papers recently that are worth thinking about with
> regards VIPM.
> 
> Efficiently Computing and Updating Triangle Strips for 
> Real-Time Rendering
> 	Jihad El-Sana, Francine Evans, Amitabh Varshney, Steven 
> Skiena, Elvir
> Azanli
> 
> (Get it from this link, under publications.)
> http://www.cs.bgu.ac.il/~el-sana/
> 
> 	This is more work like strip, including 'Issues in 
> Integrating Triangle
> Strips with Multiresolution Hierarchies' which introduces 
> Skip-Strips for
> maintaining triangle strips as you do edge collapses. Not 
> specific to VIPM
> as it deals with VDPM and Merge Trees, but well worth a look.
> 
> Coarse View-Dependant Levels of Detail for Hierarchical and Deformable
> Models
> 	Dieter Schmalsteig, Anton Fuhrmann
> (Get it from this link, under publications some way down...)
> http://www.cg.tuwien.ac.at/staff/DieterSchmalstieg.html
> 
> 	This includes a neat way of producing chunked VIPM like 
> Charles Bloom
> demonstrates on his web site (and the discussion here.) The 
> interesting bit
> is that the authors assign vertices to VIPM clumps and not 
> triangles which
> allows for some simplification on the boundary. I won't go 
> into details here
> as the authors do a much better job of explaining it than I can.
> 
> 	Hopefully everyone interested in the VIPM discussions 
> will find these of
> interest.
> 
> -Brian.
> 
> [snip]
> 
> > There were some thinking-out-loud discussions between 
> myself and Charles
> > Bloom a few weeks ago on a similar subject (doing VIPM with 
> strips rather
> > than lists). If the archives don't work, and you don't have the old
> messages
> > to search through, I could probably dig them up and repost them.
> >
> > Tom Forsyth - Muckyfoot bloke.
> > Whizzing and pasting and pooting through the day.
> 
> [snip]
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>