Re: [Algorithms] PVA hierarchies (was: Terrain performance etc)

[Mark D. <duc...@ll...>]

Hi Tom,

Erhm, this really needs a whole paper to explain (which I'm working
on), but here's an outline of the ideas...

I should first note that what I'm about to describe is for the
"wacky general geometry" case...terrain with triangle
bintrees is much simpler.

The progressive vertex array implementation I'm putting together is
based on many of the ideas you and Charles Bloom and others on this
list have tossed around about VIPMs with sliding windows, dealing
with vertex cache coherence, and dealing with seams nicely when
chunking.  My first implementation assumes a completely static set
of geometry and takes a long time to make really coherenct and high
quality progressions into a single vertex+index array per chunk.
I use queue-based edge collapse ala memoryless simplification
(Lindstrom's work) but allowing edge collapses that create
non-manifold geometry (in effect allowing arbitrary amounts of
collapse, not limited by the genus of the surface).

Collapses are organized into some kind of spatial 3D (volumetric)
hierarchy (specifically the 3D extension of ROAM "diamonds"),
where the collapses can affect only the triangles/vertices/edges
on the interior of the 3D cells.  To avoid problems like in 
Hoppe's vis98 terrain paper, which keeps the mesh on cell
boundaries at fullest resolution,  the cells don't nest like
octrees but rather alternate as with ROAM diamonds.  In 3D there
are three phases of diamond cells, so you get collapses for any
edge in at least two out of three phases of collapses, thus you
end up with no edges getting "stuck" at full resolution.  For 2D
cell hierarchies that are not too deep (e.g. Hoppe's terrain
examples), keeping edges at full resolution sort-of works okay.
But in 3D for general geometry you are hosed (I tried it...).
The alternating boundaries are critical.

Within each 3D diamond you get a progression that is put
into a single vertex+index array (not stripped, but
very vertex-cache coherent).  There is a kind of priority
queue to order the triangles in cache coherent order,
while at the same time re-ordering the progression a
bit (in essence clustering some of the collapses into
a single neighborhood collapse involving a user-specified
maximum number of triangles, and also walking these "clusters"
in vertex cache coherent order).  The collapse dependencies
are used to figure out the clustering.  Lots more details
here.  At this point you have a hierarchy of sliding-window
vertex arrays (PVAs), with ROAM-like continuity at the
diamond boundaries with no crack fixups/flanges/etc needed.
I generally have thousands to tens of thousands of vertices
per 3D diamond at the moment (haven't really tuned this yet).
Vertex counts are reduced by a modest factor at each
phase (dividing the count by the cube root of four is a good
theoretical choice for smooth geometry).

On the macro scale, ROAM split-merge is performed on the
diamonds.  Frustum culling is done ala the ROAM paper
but only on the octree cell phases, where you have
proper nesting.  The interesting details here are how
to quickly get the slider (progression window start/end
indices) in the split-merge process quickly.

I use OpenGL ATI object buffer extensions under linux
on the radeon 9700 pro.  For a huge computational
fluid dynamics isosurface representing the mixing boundary
of two gases undergoing violent (explosion-induced)
turbulence, i.e. a REALLY nasty surface, I am getting
a solid 100M tri/sec with essentially no CPU work
per frame (from the app anyway -- I can't speak for
the drivers).  This surface has depth complexity 50
on average, so I really need to minimize the window size
to get this performance (we haven't gotten the
occlusion culling for this finished yet -- that's
another big project!).

My goal is to get this written up by the end of the year
with a full demo.  The code is largely all there,
enough to get numbers and show early demos.

Cheers,

--Mark D.

Tom Forsyth wrote:
> 
> >   -- progressive vertex arrays are way cool as replacements for
> >      ROAM "triangles".  I'm getting 100M tri/sec with PVAs as the
> >      primitives in my latest experimental ROAM-like renderer with
> >      sliding progression on a radeon 9700 pro.
> 
> If anyone can hear me over the noise :-), I'd love to hear the gritty
> details of this.
> 
> TomF