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!

Alex,

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

Updated Dec 22, 1999