I'm using the STL priority queue for managing my splits in ROAM. After I force-split a bintritree, I am supposed to remove every bintritree that was split due to the force-split, including the original bintritree. A simple criteria for determing whether or not a bintritree has been split is simply whether or not it has a child (it should either have 0 or 2). However, I don't really have any way (to my knowledge) to get in the STL priority queue and start pulling arbitrary elements out. So, my temporary solution has been to just leave the split bintritrees in the queue, and every time I pull out the highest priority bintritree, I just check to see if it's split, and if so, throw it away. This has worked well for very small triangulations, however I am worried that it is not going to scale to 1000's of polys very well, for the following reasons. First, leaving these split polys in the pqueue until their priority comes up will obviously increase the cost of manipulating the tree in general. Secondly, if I simply measure the number of bintritrees in the split queue to determine when to stop rendering, I will stop prematurely, because there will be several bintritrees in there that shouldn't be rendered (because they have children). I think this is probably easy to get around, by keeping other counters (ie, increasing the counter every time i create a child, and decreasing the counter every time i split). So I guess my main concern is pretty much with the first one only, performance.

But, the only way I see to remove bintritrees from the pqueue "right then and there" is to linearly search with every removal, which has got to be more expensive than having a small extra percentage of extra bintritrees in the queue at all times.

As a test, when I subdivide two root triangles (a diamond) up to a maximum of 8 levels of subdivision, I should be able to cover the resulting square with 256 uniformly sized triangles. However, when the split queue has grown to 256 bintritrees and I stop splitting, there are actually only 244 unsplit bintritrees in the queue. So that's about a 5% "error" for a pretty damn small number of triangles.

Wisdom, opinions, etc, are eagerly anticipated...