PDA

View Full Version : bucket-based priority queues



zen
05-11-2001, 05:28 AM
Has anyone come across any info on bucket-based priority queues?I wan't to use them in my Roam implementation but the only piece of info I've found is this:
www.cognigraph.com/ROAM_homepage/bucketqueues.html (http://www.cognigraph.com/ROAM_homepage/bucketqueues.html)

and it isn't very specific.If you can figure it out let me know.I mean queue priorities are supposed to be arbitary floats.So using e.g. 2048 buckets holding tris with the same priority I cannot sort tris with arbitary priorities(I'd need infinite buckets and I don't have the memory for that.

Leo
05-11-2001, 07:53 AM
Bucket sorts are a variation of radix sort. Can't you convert the float into an int? Even if you must use a float, radix sorts are still possible. It doesn't need an infinate bucket array, there are only 32 bits thus 4gig array http://www.opengl.org/discussion_boards/ubb/smile.gif. You can break it down into smaller chunks! Radix sorts are O(n) time compared to O log(n) for most other good sorts.

Look for info on radix sorts. Robert sedgewick wrote a good book called 'algorithms in c++', adison wesley.

Zeno
05-11-2001, 08:38 AM
Leo, I think you mean O(nlog(n)) for most other good sorts like quicksort.

-- Zeno

zen
05-11-2001, 08:50 AM
I suppose I could convert the priority into an int(would save on memory as well)but still.According to that link each bucket contains a doubly linked list of triangles with the *same* priority.If I would break it into chunks the each bucket woudl have to hold tris with priorites that belong to a range like [a,b].If you read the info in that link you'll get what I mean(it's not much).

Leo
05-12-2001, 05:33 AM
Zeno. Well spotted!

BryanNC
05-14-2001, 07:03 PM
zen,

You should look up references to "bucket sort", it will describe the generalized algorithm used here. Bucket sorts are paired with the Radix algorithm to give linear sort times.

In the case of ROAM triangle sorting you are NOT sorting the triangles by priority. You are placing them into 'buckets' of similar prioirity. This is where the term 'bucket sorting' comes from.

Mr. Duchaineau is describing a technique where you create 2048 priority levels out of the (0..infinity) of possible priorities. Thus, you might cap priorities at 16384 for instance. Your first bucket would contain all triangles with a priority of 0..8, and the next from 9..16, etc..

Locating the proper bucket requires only a simple maping function. Thus to find the bucket to put a priority 87 triangle: bucket = (87 * 2048) / 16384 => bucket # 10. If you are using INTs, this can be done purely with shift operations.

You'll need an array of bucket structures, and each bucket structure is a double linked list of BinTriTree structures. When you refine the mesh, use the highest-priority bucket, and just take the first triangle off it's list until it's empty. Then move to the next bucket, etc.


Hope that helps,
--Bryan

witcomb
05-15-2001, 03:41 AM
The intention of the using bucket sort with ROAM is to improve the performace of the per frame calculations. With ROAM each triangle/diamond has a priority and there are 2 queues, the merge and split queues. These queues are intended to be in sorted order so that when you have to merge you merge the diamond that best suited for the merge. However, you don't want your ROAM engine spending all it's time sorting your queue's, but rather maintianing a correct LOD for your terrain.

So, bucket queue's are used. Anytime we need to split or merge, we are ALWAYS taking from the front of the queue. So, the time to insert is in O(n), where n is the number of buckets. The time to remove is O(1) (in general). The time to sort is actually O(n*x), where x is the number of triangles in the queue. The reasoning, is you will have to reinstert all of the triangles in to the queue.

Now, the reason bucket queue's are used for ROAM is the obvious fast insert/remove which is done alot. And the sorting is actually not that bad, and can be done every 10 frames or so due to the frame-coherence.

I hope this all makes sense.

zen
05-15-2001, 06:58 AM
Bryan an witcomb:
thanks for the replies.You're both right(mostly).Each bucket holds tris with the same priority.So you first cap your prioirties within a range [1e-6...1e4] and then map this range to range of [0...2048] of integers using a logscale.So you're not even actually supposed to sort the buckets as witcomb said cause the tris in the bucket's have the same prioirity.Of course(as it is also stated in the link above) the tris are *almost* sorted but I guess the speed gain makes it worth the while.I currently use a normal heap implemntation like the ones you can find in any book but I'll certainly give it a try.Thanx again for all the help.

BTW what I said above is according to an email from Mr Duchaineau or at least the part of it I understood http://www.opengl.org/discussion_boards/ubb/smile.gif.