ROAM infinite loop

Well, it is ever so slightly fuzzy in the sense that it is allowed to be one either side (since otherwise there's no hope of avoiding an infinite loop - if it were one under and it split then you'd be one over, etc. etc.)

I've done a few more tests just to explore the issue, and the majority of the times you can immediately detect that a loop is beginning and break out a.s.a.p. just by checking if the triangle about to be split was the last one to be merged.

However, every now and again, there is a loop of a more complicated route. So is this something wrong with my implementation, or have other people experienced loops like this?

This is a known issue that results from implementations using non-monotonic priority computation (a very common tradeoff). Please read Mark Duchaineau's ROAM Homepage site http://www.cognigraph.com/ROAM_homepage/ for relevant information.

My ideal fix is to use 2 additional "insertion-pending" queue caches, s.t. element splitting and merging does not immediately make the inverse possible during the same frame. The pending queues are merged with the actual work queues before starting a new frame, but not during the optimization/convergence stage. Thus repeated merging AND splitting of an element during a single frame is made impossible, and such loops cannot occur. Alas, I never perfected this version, as it some mysterious performance degredations (quite possibly specific to my code), so I can't completely recommend it.

Mark has a different approach, where you track the up/down priority convergence direction, and only allow a single "loop", always ending in the same direction (with merges, iirc). This allows you to consistently hit the same triangle number target each frame, if that's your goal.

This can also be fixed by marking elements with a "last operated frame" label, and not processing the same element twice (since it would already have the "current" label).

-Lucas

That's really helpful, thankyou!