- Online Community Forums » Programming Questions » Depth Sorting

Credits go to amarillion, Krzysztof Kluczek, Thomas Harte, and Zaphos for helping out!
This thread is locked; no one can reply to it. rss feed Print
Depth Sorting
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:

1void render_object (BITMAP *bmp, BITMAP *obj, fixed angle, fixed cx, fixed cy, fixed cz, CAMERA_PARAMS camera)
4 int width, height;
5 int screen_y, screen_x;
7 fixed obj_x = itofix(160) - cx;
8 fixed obj_y = itofix(100) - cy;
10 fixed space_x = fmul (obj_x, fcos (angle)) + fmul (obj_y, fsin (angle));
11 fixed space_y = -fmul (obj_x, fsin (angle)) + fmul (obj_y, fcos (angle));
13 screen_x = bmp->w/2 + fixtoi (fmul (fdiv (camera.s_x, space_x), space_y));
14 screen_y = fixtoi (fdiv (fmul (cz, camera.s_y), space_x)) - camera.horizon;
16 height = fixtoi (obj->h * fdiv(camera.obj_s_y, space_x));
17 width = fixtoi (obj->w * fdiv(camera.obj_s_x, space_x));
19 stretch_sprite (bmp, obj, screen_x - width / 2, screen_y - height, width, height);

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! ???

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

Martijn van Iersel | My Blog | Sin & Cos | Tegel tilemap editor | TINS 2017

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


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.

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.

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 :)

1// bubble sort
2void calculate_object_render_order() {
4 obj_list *tmp, *next;
5 int tmpx, tmpy, tmpz, tmpv, tmpd;
7 tmp = next = head;
9 while (tmp != NULL) {
10 next = tmp;
11 while(next != NULL) {
12 if(tmp->x < next->x) {
14 tmpx = tmp->x;
15 tmpy = tmp->y;
16 tmpz = tmp->z;
17 tmpv = tmp->visible;
18 tmpd = tmp->distance;
20 tmp->x = next->x;
21 tmp->y = next->y;
22 tmp->z = next->z;
23 tmp->visible = next->visible;
24 tmp->distance = next->distance;
26 next->x = tmpx;
27 next->y = tmpy;
28 next->z = tmpz;
29 next->visible = tmpv;
30 next->distance = tmpd;
32 }
33 next = next->next;
34 }
35 tmp = tmp->next;
36 }

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"
Allegro Wiki, full of examples and articles !!

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.

In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

Thomas Harte
Member #33
April 2000


Bubble sort is not really a bad algorithm

Bubble Sort is just a dense version of Insertion Sort!

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

1struct tCompareFun {
2 bool operator ()(const tObject *a,const tObject *b) const
3 {
4 return a->z > b->z; // this operator should return a<b
5 // but we need reverse order
6 }
9void draw_all()
11 std::vector<tObject*> objects;
13 for(o=first_object;o is an object;move o to next object)
14 objects.push_back(o);
16 std::sort(objects.first(),objects.last(),tCompareFun);
18 std::vector<tObject*>::iterator p;
19 for(p=objects.begin();p!=objects.end();++p)
20 (*p)->draw();

Arthur Kalliokoski
Second in Command
February 2005

try "grep -r qsort /allegro/examples/*.c"

“Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”

― Robert A. Heinlein

Go to: