Jump to content

  • Log In with Google      Sign In   
  • Create Account





- - - - -

DevLog #9 - Blended objects sorting

Posted by KaRei, 23 September 2011 · 380 views

Finally done. The blended objects are rendered in proper order. Or at least in most cases they are.

I think that everywhere where is a word about rendering blended objects is said that you must draw solid objects (faces) first and only after that draw the translucent/transparent objects (faces). And yes, don't forget that the blended objects must be drawn from back to front. Polygon sorting wasn't something I would be happy to go into.

I tried two variants of polygon sorting, both having some positives and negatives, and both being relatively easy. They are not perfect (for example they don't perform spliting of overlapping polygons), but they appear satisfactory for my needs, so I go with them. But for a case I rather turn off write to depth-buffer for blended objects. Sometimes this may reduce the damage if something goes bad.

glDepthMask( GL_FALSE );


STL map

This is easiest implementation of polygon sorting I think, but the easiness cost some performance.

// Pseudo-code
void draw()
{
   if ( camera_moved )
   {
  	map.clear();
  	for each ( polygon )
  	{
 		distance = polygonLocation - cameraLocation;
 		// The STL map stores its elements sorted by the key in ascending order
 		map.put( distance, polygon );
  	}
   }
   
   for ( iterator = map.rbegin(); iterator != map.rend(); ++iterator )
   {
  	(*iterator)->drawPolygon();
   }
}

The largest negative here is a need to recalculate distance of polygon everytime camera moves. On the other hand the map may be easily expanded by adding new polygons, and moving polygons are easy to update.


BSP tree

BSP (Binary-Space Partitioning) is a performance improvement for polygon sorting. I used it to reduce calculations of distance to simple comparison ( < > ). The drawback of this method is time needed to create the tree. The BSP tree can be used for objects that are static. Dynamically moving objects would take too much time to reconstruct the tree.

Tree construction:
- Always compare polygons just by coordinates of only one axis (by X on 1st level of tree, by Y on 2nd, by Z on 3rd, again by X on 4th level of tree, etc.)
- Find median by which to split set of polygons to two sub-sets
- Median makes a node, sub-set of polygons with coordinate < median goes to left sub-tree, sub-set of polygons with coordinate >= median goes to right sub-tree

Drawing the tree:
void draw()
{
   root_node.draw();
}



void node::draw()
{
   if ( is_leaf )
   {
  	draw_polygon();
   }


   // AXIS represents either X, Y, or Z dependent on the level the node is in
   else if ( camera.AXIS < median.AXIS )
   {
  	draw_right_subtree();
  	draw_left_subtree();
   }

   else
   {
  	draw_left_subtree();
  	draw_right_subtree();
   }
}

On the picture is shown BSP tree construction (in 2D, using only X & Y axes) and the order of nodes visited when drawing.
On left is a scene with objects and camera placement, on right is a tree created from the scene.
Numbers in the tree represents the order of traversing the tree if drawn for the current camera location.
In a case camera moves, the tree does not change, only the order in which the left and right sub-tree are traversed on draw may change.

Posted Image







Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

Recent Comments

PARTNERS