Depth Sorting

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:

1void 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 | Food Chain Farm | TINS 2023 is Jun 2-5

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:

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
2void calculate_object_render_order() {
   
   obj_list *tmp, *next;
   int tmpx, tmpy, tmpz, tmpv, tmpd;
   
   tmp = next = head; 
   
   while (tmp != NULL) {
         next = tmp;
         while(next != NULL) {
                    if(tmp->x < next->x) { 
                              
                       tmpx = tmp->x;
                       tmpy = tmp->y;
                       tmpz = tmp->z;
                       tmpv = tmp->visible;
                       tmpd = tmp->distance;
                       
                       tmp->x = next->x;
                       tmp->y = next->y;
                       tmp->z = next->z;
                       tmp->visible = next->visible;
                       tmp->distance = next->distance;
                       
                       next->x = tmpx;
                       next->y = tmpy;
                       next->z = tmpz;
                       next->visible = tmpv;
                       next->distance = tmpd;
                       
                    }
                    next = next->next;                      
         }
         tmp = tmp->next;
   }
   
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 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

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

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  }
7};
8 
9void draw_all()
10{
11  std::vector<tObject*> 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<tObject*>::iterator p;
19  for(p=objects.begin();p!=objects.end();++p)
20    (*p)->draw();
21}

________
[ My LD48 entry ] [ My SpeedHack`04 entry ] [ TEAM ALLEGRO ] [ My TINS'05 entry - Snake ]

Arthur Kalliokoski

Second in Command

February 2005

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

They all watch too much MSNBC... they get ideas.