Splits/merges and queue updates

Although I admit there is a *lot* of book-keeping in a ROAM
implementation, I don't think the split/merge effects on the split
and merge queues are so complicated.  In my implementation I do the

    Simple (leaf diamond) Split:
        1) the split diamond is put on the merge queue
        2) the four new leaves are put on the split queue
        3) the parents of the split diamond and their base neighbors
           are taken off the merge queue (if they are still there)

    Simple Merge:
        1) the four old leaves are removed from the split queue
        2) the two diamond tris (newly leaves) are put on the split queue
        3) the parents (say A,B) of the these two new leaves are checked.
           If A and its base neighbor have only leaves for kids,
           the (A/base neighbor) diamond is put on the merge queue.
           Same for B.  Note that checking for leafhood is easy:
           its a leaf if there is no left child (there is a right
           child if and only if there is a left child).

There *are* some more complications having to do with the frustum
OUT labels.  When triangles transition from OUT to not OUT or
back this requires some checking for merge/split queue updates
for the tris that transition and their parents/kids/neighbors.
This is because I don't waste effort splitting/merging tris
outside the frustum unless continuity dictates.  Mergable diamonds
with one or more OUT labels in the two tris are still on the merge
queue, but with the lowest possible priority (so they get merged first).
Any leaf tri with an OUT label is taken off the split queue.
Another minor boundary condition is that finest-resolution leaves
are not put on the split queue.  These cases are dealt with by (1)
avoiding putting any OUT or finest-res leaf on the split queue (just
check right before inserting); (2) any split-queue member that
goes OUT gets removed from the split queue; (3) any non-finest
leaf that transitions to not OUT gets put on the split queue.

Kirk Hammond asks:

> 1) How does frustrum culling affect the action of the queues?  I.e. if I
> yank a visible tri off the split queue and force split it to a point
> where the nodes I throw on the split queue are no longer in the
> frustrum, what do I do?  Right now I just throw them in the split queue
> anyway and when I dequeue split nodes I need to check if they are
> visible that frame before I split them.  What metric do I use to
> calculate an OUT tri's priority (or do I even need to since they won't
> be yanked from the split queue the same frame since they will be flagged
> as OUT)?.

In the original ROAM implementation I took any OUT tris off thesplit queue,
but kept mergable OUT diamonds on the merge queue
with the lowest possible priority.  This has the effect that regions
outside the view frustum get coarsened first before anything in the
frustum, and it takes a while before the triangles you actually render
(and the triangle count) are affected.  The saving grace here is that
(typically!) only a handful of triangles are moving out of the frustum
from one frame to the next.  As you note, it is possible to put off this
merge work till later, but that can chew up memory.  Perhaps
there is a clever way to avoid the usual merging of the OUT diamonds
with a more stream-lined process...  Worst case is looking straight down
at low altitudes while traveling at high speed.  If things get too bad
just trash your entire active bintree and do pure splits for as much
time as you alot yourself.  I describe in the paper how this case can
be easily detected (you will see a huge overlap in the merge
and split queues from one frame to the next).

> 2)  This also goes to merging - do I merge nodes that are not in my
> frustrum?  I.e. if I fly the camera forward in a line and I don't merge
> nodes outside my frustrum, the nodes behind me will pile up and start
> slowing down frustrum per-frame calculations, etc.  Not to mention that
> when I turn around I will have a bazillion tris in my frustrum and will
> lag while everything is remerged...  However, these merges will not
> affect my visible tri count (since they will be outside my frustrum) and
> could cause a slow down...

Contact Information

Mark A. Duchaineau -- duchaineau1@llnl.gov



Updated Dec 22, 1999