Splits/Merges and Queue Updates

Given the priorities and queues, the remaining major
implementation question is the outer-loop processing
to hit the target triangle count as closely as possible.
Keep doing the following until there are no diamonds to
merge with lower priority than some triangle you want
to split.  If you have too few triangles, then split
the highest-priority triangle on the split queue.
If you have the target triangle count or higher, then
merge the lowest-priority diamond on the merge queue.
This will stop when you have achieved an optimum,
although you may not have the target triangle count
(although you *were* heading in the right direction,
count-wise).  Now keep performing the same steps
(splitting the max or merging the min) until you
get just above or below the target count.  Now as
a final fix for stability, merge the mins until you
are just under the target count.

This gets you to your target count quickly but makes
the big assumption that the kids of a triangle don't
have bigger priorities than it does.  Unfortunately
with approximate priorities this can happen.  Fortunately
this happens in only a handful of triangles per frame
and is easily patched up.  What I do is mark a triangle
that has been split or merged during a frame, and if
I see that mark for the opposite operation later, e.g.
merged after split in the same frame, then I flag the
optimizer that it should stop to avoid cycling forever.
Just in case, I also limit the total number of optimization
outer loops to some sane number.  If anyone has a better
way to handle this I'd love to hear it!


I can think of two likely reasons your mesh is not
stable when the eyepoint isn't moving.  First, you
might have children whose priorities are larger than
their parent's, which I described how to detect and
fix previously (and apparently you have also).  The
second has to do with carefully defining how many
triangles you get each frame, since you can't get
*exactly* a desired triangle count in general.  What
happens is this: on one frame you end up splitting at
the last step that balances the split and merge queues,
leading to slightly more triangles than you need.  On
the next frame the opposite happens, you get a merge
and slightly less triangles than you need.  This will
bounce back and forth.  The solution here is to always
perform extra splits at the end until you get the
minimum number of triangles that is at least the target
count and that balances the split and merge queues.
Similarly you can perform just enough extra merges to
get the maximum number of triangles that is less than
or equal the target count and balances the queues.

Note also that if you are using coherence at all, you
certainly have the opportunity to record the frustum
from the current frame, so you can check whether you
can skip optimization all together on the next frame
by checking whether the frustum is identical or not.
I'm not advocating this as the desired solution but it
is possible.

--Mark D.

Alex Pfaffe (Exchange) wrote:

>  Mark, and other implementer of ROAMIn my implementation the ROAM mesh
> does not seem to ever reach a stablestate.  Even when I am not moving,
> the rebalance operation will make changesto the mesh.  The reason, I
> believe, is because the mesh cannot crack, sometimea split will
> reintroduce triangles into the queue which a subsequent operation
> willtry to merge again, basically undoing the split.I have added flags
> to avoid these cycles within a single frame.However from frame to
> frame this becomes a pain.Is this problem inherent in the ROAM
> algorithm or do I have a bug?If it is not a bug, can anyone recommend
> some ways to stop this?In my own implementation I can detect if the
> use has not moved and donothing, however in the Crystal Space engine
> where the terrain is alsoused, I cannot.Alex

Contact Information

Mark A. Duchaineau -- duchaineau1@llnl.gov



Updated Dec 22, 1999