ROAM infinite loop
Author
I'm getting an infinite loop in my ROAM implementation:
-First I'm at my target triangle count, but the maximum split queue priority is greater than the minimum merge queue priority, so it does a split.
-That brings me two over the target triangle count, so a merge is done.
Trouble is, the one being merged is the same one that was just split, and so it goes around again ad infinitum, until the frame time limiter kicks in. It means that I can't use any 'spare' frame time to do other stuff.
Any ideas? Does that sound like a bug in my code, or have other people experienced this with ROAM?
I am not very familiar with ROAM, but off the top of my head it seems like it would make more sense to use a fuzzy target triangle count. In other words, if you are within, say, 50 triangles of your target just go ahead and stop.
Author
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.)
Author
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?
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
