Depth Sorting algorithm

Member
Posts: 105
Joined: 2007.03
Post: #1
My game is a 2d sprite based game drawn in the upper right hand quadrant of opengl entirely. The depth sorting algorithm I use works fine but I am concerned over it's efficiency, perhaps some of you could let me know if it's absurdly inneficient or not.

By the way, the reason I keep a 2d array is because I first sort by the y coordinate of the quad / the base tile height(16). And then I get the pixel remainder(quad.y % 16) and use that as an index to the y array element ( depth_list[ROUNDED_DEPTH][REMAINDER_PIXEL_DEPTH].


depth_record_type depth_list[SIZE_X][SIZE_Y];

void add_tiles_to_dl(void)
{
for (x = visible_tile.x; x < visible_tile.x + NUM_COLUMNS; x++)
{
for (y = visible_tile.y; y < visible_tile.y + NUM_ROWS; y++)
{
add_tile_to_dl(tile[x][y]);
}
}


// add_enemies, add npcs, etc.....
}




void draw_dl(void)
{
for (x = 0; x < SIZE_X; x++)
for (y = 0; y < SIZE_Y; y++)
draw_dl_quad()

}

repeated EVERY FRAME.
Quote this message in a reply
Member
Posts: 28
Joined: 2003.10
Post: #2
When I've needed depth sorting for objects in the past I've done so by keeping two pointers for each object (one to the next closer and one to the next further object) and used them as a list when drawing.

That way, once the initial sort has been done, and assuming object only change depth order occasionally, each object need only be checked once, against the next closer object during the drawing process - which is extremely efficient.

-- Giles Williams
Oolite - retro space-sim agogo
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Die-hard vertex-sorting function not accepting input values! mikey 6 3,870 Oct 31, 2009 03:36 AM
Last Post: mikey
  squares[] and sorting vertices into arrays... mikey 3 3,015 Sep 11, 2009 11:21 AM
Last Post: mikey
  Requesting Help: Smooth keyframe interpolation algorithm whogben 4 4,684 Jan 5, 2009 11:15 PM
Last Post: whogben
  Algorithm for moving between two points on a plane... WhatMeWorry 4 4,730 Aug 23, 2005 11:36 AM
Last Post: unknown
  Minesweeper algorithm Coin 3 5,339 Jul 29, 2005 09:48 AM
Last Post: Coin