Allegro.cc Forums » Programming Questions » Depth Sorting

Credits go to amarillion, Krzysztof Kluczek, Thomas Harte, and Zaphos for helping out!
 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:

 1 void render_object (BITMAP *bmp, BITMAP *obj, fixed angle, fixed cx, fixed cy, fixed cz, CAMERA_PARAMS camera) 2 { 3 4 int width, height; 5 int screen_y, screen_x; 6 7 fixed obj_x = itofix(160) - cx; 8 fixed obj_y = itofix(100) - cy; 9 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)); 12 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; 15 16 height = fixtoi (obj->h * fdiv(camera.obj_s_y, space_x)); 17 width = fixtoi (obj->w * fdiv(camera.obj_s_x, space_x)); 18 19 stretch_sprite (bmp, obj, screen_x - width / 2, screen_y - height, width, height); 20 21 }

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). --Martijn van Iersel | My Blog | Sin & Cos | Tegel tilemap editor | TINS 2017
 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. ________[ My LD48 entry ] [ My SpeedHack`04 entry ] [ TEAM ALLEGRO ] [ My TINS'05 entry - Snake ]
 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

 1 // bubble sort 2 void calculate_object_render_order() { 3 4 obj_list *tmp, *next; 5 int tmpx, tmpy, tmpz, tmpv, tmpd; 6 7 tmp = next = head; 8 9 while (tmp != NULL) { 10 next = tmp; 11 while(next != NULL) { 12 if(tmp->x < next->x) { 13 14 tmpx = tmp->x; 15 tmpy = tmp->y; 16 tmpz = tmp->z; 17 tmpv = tmp->visible; 18 tmpd = tmp->distance; 19 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; 25 26 next->x = tmpx; 27 next->y = tmpy; 28 next->z = tmpz; 29 next->visible = tmpv; 30 next->distance = tmpd; 31 32 } 33 next = next->next; 34 } 35 tmp = tmp->next; 36 } 37 38 }

 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"Allegro Wiki, full of examples and articles !!
 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. __________In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de SnepscheutMMORPG'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 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).

 1 struct tCompareFun { 2 bool operator ()(const tObject *a,const tObject *b) const 3 { 4 return a->z > b->z; // this operator should return a objects; 12 13 for(o=first_object;o is an object;move o to next object) 14 objects.push_back(o); 15 16 std::sort(objects.first(),objects.last(),tCompareFun); 17 18 std::vector::iterator p; 19 for(p=objects.begin();p!=objects.end();++p) 20 (*p)->draw(); 21 }

 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: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads