__________________________________________
you just think i''m here. i''m really not.
sorting transparent objects by screen depth..
Author
here''s what i have.
i have a list of all opaque objects.
i have a list of all objects that use any kind of transparency (alpha, masked textures whatever).
i have the transparent objects'' depths in the screen.
i know i have to draw all opaque obejcts first, then the transparent objects in back-to-front order.
what i need to know is how to most efficiently sort the transparent objects.
right now i''ve thought of 3 different methods to sort the objects, but i''m not sure which way to go (option 2 or 3).
option 1: brute force sorting. pass through the list of objects, each time rendering the next-nearest object. this is really not even an option; the amount of depth comparisons goes up exponentially (plus a little overhead for the first pass to determine the furthest object), so with 10 objects you have 110 checks (10 passes through 10 objects plus the initial pass through the 10 objects. this is modeled by x^2+x).
option 2: semi-brute force. using a vector to hold the objects to be sorted, i can remove any objects from the vector after they are drawn. supposing that one object is drawn and removed per pass through the vector, this approaches being 50% faster than option 1. with 10 objects you have 65 checks (10+9+8+7+6+5+4+3+2+1 plus the initial pass through the 10 objects.. this is only 35% faster but with, say, 50 objects, it is 47% faster.. this function approaches being 50% faster. this is modeled by 0.5x^2+1.5x) i still don''t know if this will be fast enough tho.
option 3: quicksort. i have no idea how fast this is as i have no data as to how fast quicksort is. it has been running through my mind, though.
what would you suggest? i figured there would be people here who have the answer
__________________________________________
you just think i''m here. i''m really not.
__________________________________________
you just think i''m here. i''m really not.
how bout a priority queue( binary heap )? when setting the scene up, push down all alpha objects on the queue with associated weight( O( log n) time ). During rendering, do a delete_min( O( 1 ) time ) and you'll end up with an empty queue at the end which you can fill up again during the next scene.
-Marv
[edited by - Wicked Ewok on February 22, 2004 10:38:53 PM]
-Marv
[edited by - Wicked Ewok on February 22, 2004 10:38:53 PM]
The worst-case time for quicksort is n*n, but its average time is faster than an n*log(n) algorithm. (In practice, quicksort is almost always faster.)
However, the best sorting method for a game usually involves space partitioning. The easiest way to do this is to break up your game world into a fixed set of blocks, and keep track of which block each game object is in. Sort the blocks, then sort the objects inside each block. More complex algorithms use a hierarchical tree of blocks (BSP tree, quadtree, octree, etc.)
Here''s some simple math for it:
If n is 1000, an n*n sort algorithm requires 1M comparisons. But 10 blocks with 100 objects each requires 10K comparisons for each block, or 100K comparisons. With 100 blocks of 10, the total number of comparisons drops to 10K.
Tip #1:
If a block is behind the camera (or outside its field of view), then no objects in the block need to be drawn (or sorted). You also don''t need to bother checking the objects individually to see if they''re behind the camera.
Tip #2:
Space partitioning also helps you minimize the number of collision detection checks you need to make. For each object, just check other objects in the same block.
Tip #3:
Although common sense would tell you that you need to sort the blocks for rendering, it''s not always true. If block 1 is closer than block 2, you can still render block 1 first if it doesn''t obscure block 2 (i.e. if it''s over to the side). So if you have a fixed 2D or 3D array of blocks, you can just pick the corner that''s closest to the view vector, then loop from that corner to the opposite corner. It won''t be a true depth sort, but it is close enough for everything to be rendered correctly. If you have a tree, you can traverse the branches of the tree in reverse depth order. This also won''t give a true depth sort, but again it will be close enough.
Warning:
The main problem with this is that an object can be in more than one block at a time. The center point of an object often defines "where" that object is, but its bounding radius (or bounding box) may cross into other blocks. For collision detection purposes, moving objects will often cross over block edges between frames.
One way to handle this would be to keep a list of "shadows" in each block. Think of a shadow as an object that exists in a neighboring block that casts its shadow into this one. Instead of a shadow that is cast by light, this shadow is cast by the object''s area of influence. Shadows need to be checked for collision detection and rendering order issues.
However, the best sorting method for a game usually involves space partitioning. The easiest way to do this is to break up your game world into a fixed set of blocks, and keep track of which block each game object is in. Sort the blocks, then sort the objects inside each block. More complex algorithms use a hierarchical tree of blocks (BSP tree, quadtree, octree, etc.)
Here''s some simple math for it:
If n is 1000, an n*n sort algorithm requires 1M comparisons. But 10 blocks with 100 objects each requires 10K comparisons for each block, or 100K comparisons. With 100 blocks of 10, the total number of comparisons drops to 10K.
Tip #1:
If a block is behind the camera (or outside its field of view), then no objects in the block need to be drawn (or sorted). You also don''t need to bother checking the objects individually to see if they''re behind the camera.
Tip #2:
Space partitioning also helps you minimize the number of collision detection checks you need to make. For each object, just check other objects in the same block.
Tip #3:
Although common sense would tell you that you need to sort the blocks for rendering, it''s not always true. If block 1 is closer than block 2, you can still render block 1 first if it doesn''t obscure block 2 (i.e. if it''s over to the side). So if you have a fixed 2D or 3D array of blocks, you can just pick the corner that''s closest to the view vector, then loop from that corner to the opposite corner. It won''t be a true depth sort, but it is close enough for everything to be rendered correctly. If you have a tree, you can traverse the branches of the tree in reverse depth order. This also won''t give a true depth sort, but again it will be close enough.
Warning:
The main problem with this is that an object can be in more than one block at a time. The center point of an object often defines "where" that object is, but its bounding radius (or bounding box) may cross into other blocks. For collision detection purposes, moving objects will often cross over block edges between frames.
One way to handle this would be to keep a list of "shadows" in each block. Think of a shadow as an object that exists in a neighboring block that casts its shadow into this one. Instead of a shadow that is cast by light, this shadow is cast by the object''s area of influence. Shadows need to be checked for collision detection and rendering order issues.
look up Radix Sort. This performs in, I believe, O(n) time all the time. Make sure you either a) modify the sourt to support IEEE floating point numbers or b) make your z-cordinate an integer (by multiplying by 2^8, 2^16, etc...) and the radix sort will work normally.
Chris Pergrossi
My Realm | "Good Morning, Dave"
Chris Pergrossi
My Realm | "Good Morning, Dave"
Having wondered about this myself, and played Warcraft 3 a lot, and hence spent hours staring at shadowmelded huntresses trying to figure out how they do it, I''ve come to the following conclusion: They depth-sort the objects, and then depth-sort tris within each object, but they don''t globally sort tris, as that would make performance suck bigtime, what with switching texture nearly every tri and so forth. I think. I''ve never actually written a 3D RTS, though, so I can''t say.
Seeing as you''ll never have more than a few hundred objects (assuming) and each object shouldn''t have more than a few hundred polys (unless you''re hardcore enough to know better than me) it doesn''t really matter what sort you use - with those numbers I think bubblesort will hold it''s own (low setup cost eclipses higher-order runtime).
...Just my AU2C+GST.
Heh, I like that, I think I''ll make it my signature.
Seeing as you''ll never have more than a few hundred objects (assuming) and each object shouldn''t have more than a few hundred polys (unless you''re hardcore enough to know better than me) it doesn''t really matter what sort you use - with those numbers I think bubblesort will hold it''s own (low setup cost eclipses higher-order runtime).
...Just my AU2C+GST.
Heh, I like that, I think I''ll make it my signature.
Author
thanks for all the responses guys
wicked ewok - i won''t lie to you, i don''t really understand that at all..
s_p_oneil - i do plan on having some kind of portal (probably octree) system in my engine, and that''s all good stuff to know, thanks. also thanks for the info on quicksort!
ctoan - that sounds like a pretty good idea i''ll probably try that.
fractoid - well umm no offense but bubble sort? thanks for the suggestion though you did make me think about it, and you''re right - i probably never will have TONS of transparent objects that need to be sorted.
i think i''ll try the quicksort and modified radix sort methods, and then see which one works better and implement it into a space partitioning system.
thanks guys!
__________________________________________
you just think i''m here. i''m really not.
wicked ewok - i won''t lie to you, i don''t really understand that at all..
s_p_oneil - i do plan on having some kind of portal (probably octree) system in my engine, and that''s all good stuff to know, thanks. also thanks for the info on quicksort!
ctoan - that sounds like a pretty good idea
i''ll probably try that.fractoid - well umm no offense but bubble sort? thanks for the suggestion
though you did make me think about it, and you''re right - i probably never will have TONS of transparent objects that need to be sorted.i think i''ll try the quicksort and modified radix sort methods, and then see which one works better and implement it into a space partitioning system.
thanks guys!
__________________________________________
you just think i''m here. i''m really not.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
