Although you could grab any priority queue implementation
from a general algorithms book or standard library, that
would be overkill (and slow!) for what you need in a
ROAM implementation (typically requiring walking and
modifying log(N) branches of some kind of tree, where
N is the number of items queued). Instead you can
*approximately* sort the triangles using (e.g. 2048)
buckets, hence the iq index. Each bucket contains
an otherwise unsorted, doubly-linked list of triangles
with the same iq index. Insert adds to the head of the
bucket, delete just adjusts links to the triangle before
and after in the bucket list. Both these take a tiny
amount of time. What's left is maintaining the index
iqmax (or iqmin for the merge queue) of the highest-index
non-empty bucket. When an insert occurs, if iq>iqmax
then set iqmax=iq. For deletes, if the bucket becomes
empty and iq==iqmax, then scan iq-1, iq-2 etc until the
first non-empty bucket, which becomes the new iqmax.
This may *occasionally* take dozens of steps, but these
steps are extremely fast and, more important, there are
only a tiny number of them *on average*. Try it and
instrument your code to get some stats--I think you'll be
pleased.
Updated Dec 22, 1999