|
Depth Sorting |
ngiacomelli
Member #5,114
October 2004
|
I'm looking into what I think people call 'depth sorting'. In that, I want to make sure that objects closer to the camera are drawn last so that they overlap objects further away. I'm using some code that I have adjusted from amarillion's mode 7 tutorial:
Now, as far as I know, there are a few techniques to 'depth sort' objects. One popular one is the Z-Buffer, if I'm not mistaken. And that is where all objects that are visible are ordered by Z-Buffer and then pushed to render in that order. Now, my problem is that the code above will take the Z coordinate, but uses it to adjust height, rather than 'distance'. If I set a Z value of 1500 the objects will hover above the ground. So I assume that I need to adjust the 'Y' axis, instead. But I thought it best to ask before embarking on a guessing game!
|
amarillion
Member #940
January 2001
|
When I wrote that article, I thought it would be logical to use space_x and space_y to refer to the mode 7 plane, and space_z for the height above the plane. What you want is to sort by space_x (after you've done the rotation transformation). -- |
Zaphos
Member #1,468
August 2001
|
amarillion's mode 7 tutorial said: Here is the code (circ11.c). To test your intelligence, I use not space_y but space_z to represent the upward direction. You sort by depth, which may be represented by whatever variable you choose. As a side note, your method is fine, but is not z-buffering.
|
Krzysztof Kluczek
Member #4,191
January 2004
|
Quote: Now, as far as I know, there are a few techniques to 'depth sort' objects. One popular one is the Z-Buffer, if I'm not mistaken. And that is where all objects that are visible are ordered by Z-Buffer and then pushed to render in that order. Z-buffer is something completely different. In this method every pixel in addition to its RGB values has its depth stored. If you draw new pixel new depth is compared with the old one and if new pixel is closer then RGB and Z values are updated (if new pixel is behind the old one nothing happens). This way you don't have to care about in which order you draw. Also intersecting shapes are handled correctly (you can't draw them correctly by just sorting them). Z-buffer technique is used by all modern GPUs (at least these widely available) and it's extremely fast. Z-buffer values of nearby pixels are usually almost the same, so GPUs use compression and other algorithms to fully exploit this fact. ________ |
ngiacomelli
Member #5,114
October 2004
|
Can anyone give me the name of the method I'm talking about?
|
Thomas Harte
Member #33
April 2000
|
"Depth sorting" is a generic term used to describe this method - "painter's algorithm" is another one commonly seen. So, you basically have the right idea - create a list of the objects that need drawing, sort it, and draw them in that order. The standard C libraries provide qsort which is a suitable sorting algorithm, I'm sure STL has lots of similar things so really all you have to think about is how you're going to represent your list and what factor you're going to sort by. Of course, Amarillion has already answered the latter. [My site] [Tetrominoes] |
ngiacomelli
Member #5,114
October 2004
|
EDIT: Wrong! Bubble sort suffers terrible slow-down when there are too many objects. Shall try something else. I've written a bubble sort routine which works out quite nicely. I'll mark this as answered but if anyone has any objections to using a bubble sort with a linked-list... or for this method in general. Don't be afraid to say so
|
GullRaDriel
Member #3,861
September 2003
|
hmmm why not just swap the pointer instead of swapping all those members ? "Code is like shit - it only smells if it is not yours" |
HoHo
Member #4,534
April 2004
|
Bubble sort is not really a bad algorithm if array members don't swich places too often and is mostly sorted. Of cource I would use the standard STL std::vector of pointers (with preallocated space so no reallocations take place) and std::sort with custom comparator. __________ |
Thomas Harte
Member #33
April 2000
|
Quote: Bubble sort is not really a bad algorithm Bubble Sort is just a dense version of Insertion Sort! [My site] [Tetrominoes] |
Krzysztof Kluczek
Member #4,191
January 2004
|
I suggest using std::sort for this - it uses one of O(n log n) algorithms and because it's template everything is inlined (unlike qsort, which has to call a function for each comparison), so it's really fast. It worked quite nice for me in Snake (my TINS/SpeedHack entry, I don't remember exactly which one).
________ |
Arthur Kalliokoski
Second in Command
February 2005
|
try "grep -r qsort /allegro/examples/*.c" They all watch too much MSNBC... they get ideas. |
|