Re: [boost] Bitmap pixel iterators?

From: Michael D. Crawford (crawford_at_[hidden])
Date: 2001-03-24 02:44:48

David Abrahams said:
> I think it would help if you could be a bit more specific about how you
> might use the iterators. For example, what would you iterate over? Pixels,
> bytes, scanlines, or something else?

Of course!  In fact writing down a variety of ways one might use them would
help me
to understand how the API should go.

Dereferencing an iterator would usually return an RGB value for a single
pixel.  Sequencing through a range would take you through a rectangular area
of an image, from right to left across the top scanline of the area, then top
to bottom.

When a graphics programmer writes code to directly address pixel values,
they're usually addressing bytes directly through pointers to unsigned char,
and they may be doing a lot of shifting and masking and complex address
calculations.  If you do this right you can get very efficient code but the
code tends to be hard to write correctly and to maintain.  I hope to enable
this kind of efficiency with the pleasantness and maintainability of iterating
over a range inside an STL container.

Let me start with a couple examples of how one uses ZooLib's existing
ZDCPixmap class.  A ZRGBColor is a class whose members are 16 bit RGB values.

   // Create a pixmap 100 pixels wide, 200 pixels high, with 32-bit pixels
   ZDCPixmap myPix( 100, 200, 32 );

   // I omit initializing its pixels; one might unpack a JPEG into it

   // Find the color of the tenth pixel down by twentieth over (0-based indexing)

   ZRGBColor color( myPix.GetPixel( ZPoint( 9, 19 ) );

   // Now set it to blue

   color.blue = 0xff00;
   color.red = 0x0000;
   color.green = 0x0000;

   myPix.SetPixel( 9, 19, color );

GetPixel and SetPixel are very convenient functions, quick to code to but they
hide  a lot of work that's done for each pixel access.  One always deals with
convenient RGB values and X & Y coordinates, but a lot of work is done in each
call to convert between the raw pixel format and the RGB value and vice versa.

Now to do the same thing with an iterator, suppose we call it a PixelIterator.
 We cannot yet initialize one of these from a member function of ZDCPixmap
because it doesn't have a member that returns any iterators, but ZooLib's
creator Andy Green is open to adding explicit support for iterators.

    // Construct an iterator that points at the top-left pixel, and has all the
    // decisions regarding format cached in it

    PixelIterator iter( myPix, ZPoint( 0, 0 ) );

    // Alternatively, if iterator support is built into ZDCPixmap then we can
    // initialize from a member function that returns an iterator:
    //
    // PixelIterator iter( myPix.TopLeft() );

    // Move the iterator to point at the tenth by twentieth pixel

    iter += ZPoint( 9, 19 );

    // Get the pixel value there

    ZRGBColor color( *iter );

    // Set that pixel value to blue

    *iter = ZRGBColor( 0xff00, 0x0000, 0x0000 );

This might be extra effort to go to to access a single pixel, but the power
lies in using them repeatedly, because you don't have to keep figuring out how
convert the pixel format, accessing them in a loop is more powerful.  

But there's a problem - how can they be used two-dimensionally in a loop?  One
can only loop over one index at a time.  One possible solution although a
little ugly is to put inner loop iterators inside to limit loops

    // a possible solution clear a bitmap to white

    PixelIterator from( myPix, ZPoint( 5, 5 ) );
    PixelIterator to( myPix, ZPoint( 10, 10 ) );

    ZRGBColor white( 0xFF00, 0xFF00, 0xFF00 );

    for ( PixelIterator iter( from ); iter.GetV() < to.GetV(); ++iter.GetV() ){

        // Reset will set the loop counter back to the beginning
        for ( iter.GetH().Reset(); iter.GetH() < to.GetH(); ++iter.GetH() ){
            *iter = white;
        }
    }

That may look a little clumsy but it beats the pants off some of the grungy
code I've written in the past for direct pixel access, with lots of
special-case code for big-endian vs. little-endian pixels, whether there's an
alpha channel, and handling indexed vs. direct pixels.  All the nastiness of
that code is supposed to be hidden in the iterators and all the decisions are
just supposed to be made once.

But we can create graphics algorithms to take advantage of the power of these
things in a way that will be really clean to the user:

    SetColor( PixelIterator( myPix, ZPoint( 5, 5 ),
              PixelIterator( myPix, ZPoint( 10, 10 ),
              ZRGBColor( 0xff00, 0xff00, 0xff00 ) );

I've been saying that the PixelIterators will always return ZRGBColors.  But
for efficiency, we may want to always stay withing a single graphics format. 
Suppose we define a type "VideoGameColor" that is 5 bits each of R, G and B,
and 1 bit of alpha, for a 16 bit value with a simple masking for overlays.  We
could make PixelIterator a template:

    // These should both work regardless of myPix' underlying format
    PixelIterator< ZRGBColor > rgbIter( myPix, ZPoint( 0, 0 ) );
    PixelIterator< VideoGameColor > vidIter( myPix, ZPoint( 0, 0 ) );

    ZRGBColor rgbColor( *rgbIter );
    VideoGameColor vidColor( *vidIter );

In general color space transformation is a complicated subject - really a
black art and the subject of many software patents.  

You can use conversion functions but you probably don't want to use a simple
cast to convert the color formats even for a single pixel.  But it would
probably help to define casting templates that could have private
implementations to tune color transformations right:

   vidColor = color_conversion_cast< VideoGameColor, ZRGBColor >( rgbColor );

To composite two pixmaps of different underlying pixel formats, one would have
the choice of hiding the conversion to RGB inside the iterator, or getting the
raw pixel data out in some canonical, unpacked format such as as a class instance.

So one might have:

  // Copy a rectangle of pixels in 5,5,5,1 format into 8,8,8 format
  PixelIterator< VideoGameColor > sourceStart( vidPix, ZPoint( 0, 0 ) );
  PixelIterator< VideoGameColor > sourceEnd( vidPix, ZPoint( 5, 5 ) );
  PixelIterator< ZRGBColor > dest( rgbPix, ZPoint( 10, 10 ) );

  InsertPixels( sourceStart, sourceEnd, dest );

One would generally want to do fancier things than going to all this labor
just to fill rectangular regions with solid colors or copy in rectangular
images.  The more interesting stuff involves masking with a region, and doing
shaded masks either with an alpha channel or using a grayscale image as an
alpha channel.

To get really whacky you can use images as distortion maps, where one image
contains the source pixels and another image contains two-component values
(which might be floating point), and one offsets a copied pixel by the x and y
displacement as you go.

Mike
-- 
Michael D. Crawford
GoingWare Inc. - Expert Software Development and Consulting
http://www.goingware.com/
crawford_at_[hidden]
   Tilting at Windmills for a Better Tomorrow.