Efficient way to (not) draw pixels underneath of other pixels?

Question

When drawing multiple sprites to the screen (especially when these sprites have different depths (ie. above or below other sprites) there is the problem that you might end up drawing many pixels on-top of other pixels.

This is inefficient as there is no point to set a pixel if another pixel from another sprite just draws on-top of that one. When there are more sprites, and bigger sprites the problem of inefficiency only gets worse.

I can only think of the two traditional ways of doing it though:

1) Just draw everything, bottom to top and ignore the problem (not efficient)

2) Check if a higher-level pixel hasn't already been drawn there, and then draw. (also not efficient because you have to check for every pixel in every layer)

Any thoughts or comments?

PS: This question is about drawing pixels in general.

Answer 1

The two "traditional" ways of doing it are actually quite efficient:

• Drawing everything lets you use blocktransfers (i.e. your data is transferred as large chunk, e.g. one transfer per pixelrow), which are very fast.
• The second method you mention is typically implemented in hardware in form of the stencil and/or depthbuffer. This also makes things rather fast.

Anyhow: In order to be efficient if you want to avoid overdraw you'd typically draw your layers/sprites front to back and use a second buffer coupled with some smart logic operators, to figure out which color to draw.

e.g:

// This buffer contains a byte for each pixel. Either the byte is 0x00 for a free pixel
// or 0xFF for a colored pixel.
byte* overDrawBuffer;
// The colorbuffer is our rendertarget
byte* colorBuffer;
// The spritesource is where the pixeldata of our sprite resides
byte* spriteSource

for (int i = 0; i < numPixels; i++)
{
   // will choose either the existing color or the new color depending on
   // the value of the overDrawBuffer. 
   byte theColor = (*colorBuffer & *overDrawBuffer) | (*spriteSource & !*overDrawBuffer);
   *colorBuffer = theColor;
   // Mark the pixel
   *overDrawBuffer = 0xFF;

   //Move to the next pixel
   *overdrawBuffer++;
   *colorBuffer++;
   *spriteSource++;
}

Note: This code will most definitely not work properly - it's just meant to be an illustration of the idea. Code like this, without branches and very few ops should produce very fast machine code.