Depth Sorting

no-reply@allegro.cc (ngiacomelli) — Wed, 28 Dec 2005 04:43:27 +0000

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!

no-reply@allegro.cc (amarillion) — Wed, 28 Dec 2005 05:10:45 +0000

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

no-reply@allegro.cc (Zaphos) — Wed, 28 Dec 2005 05:13:16 +0000

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.

no-reply@allegro.cc (Krzysztof Kluczek) — Wed, 28 Dec 2005 06:51:55 +0000

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.

no-reply@allegro.cc (ngiacomelli) — Wed, 28 Dec 2005 07:07:55 +0000

Can anyone give me the name of the method I'm talking about?

no-reply@allegro.cc (Thomas Harte) — Wed, 28 Dec 2005 08:21:40 +0000

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

no-reply@allegro.cc (ngiacomelli) — Wed, 28 Dec 2005 16:18:44 +0000

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}

no-reply@allegro.cc (GullRaDriel) — Wed, 28 Dec 2005 16:44:40 +0000

hmmm why not just swap the pointer instead of swapping all those members ?

no-reply@allegro.cc (HoHo) — Wed, 28 Dec 2005 17:00:57 +0000

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.

no-reply@allegro.cc (Thomas Harte) — Wed, 28 Dec 2005 19:09:15 +0000

Quote:

Bubble sort is not really a bad algorithm

Bubble Sort is just a dense version of Insertion Sort!

no-reply@allegro.cc (Krzysztof Kluczek) — Wed, 28 Dec 2005 19:59:07 +0000

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
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}

no-reply@allegro.cc (Arthur Kalliokoski) — Thu, 29 Dec 2005 03:29:34 +0000

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

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	}

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	}

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
5	// but we need reverse order
6	}
7	};
8
9	void 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	}