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
following:
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...
Updated Dec 22, 1999