Author Topic:   Removing BinTriTrees from the priority queue
posted November 11, 1999 01:31 PM            
Hey folks,

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...



LDA Seumas
posted November 14, 1999 01:58 AM           
What about writing your own priority queue that does exactly what you want? I think if you're really concerned about performance, that would be the best way to go anyway, rather than using a generic implementation.

-- Seumas McNally, Lead Programmer, Longbow Digital Arts


posted November 14, 1999 07:11 PM            
jeez... i just assumed STL would be faster. 62 lines of code later, i have a heap/priority queue that is 10x faster than the STL. :^) that will help a lot.