Bitmap pixel iterators?

From: Michael D. Crawford (crawford_at_[hidden])
Date: 2001-03-23 22:17:02

I'm about to design a set of iterators to ease direct access into offscreen
graphics buffers.  I would like something with the utility and ease of use of
STL iterators, with the difference that the containers will all have the same
type but contain different data formats depending on different flags.  Also
the pixels will in general iterate over rectangular regions.

You boost folks are more familiar than I about the design issues with
iterators so I thought I'd ask for tips on what I should try to achieve and
what I would best avoid.

You may not know anything about graphics programming, but perhaps you'd have
something to say about iterators in general.  If you had to design a set of
iterators to serve any particular purpose at all, what would you want them to
have in common?  What can you say about the strengths and weaknesses of
different iterators that you've encountered, both their abstract API and how
they've actually been implemented in real systems?

I'll be addressing the ZDCPixmaps from the ZooLib cross-platform application
framework, but on the different platforms these are wrappers around such
things as Macintosh GWorlds and Windows DIBs and the like.  Potentially this
work could be generalized to other graphics APIs by making them templates and
adding traits parameters.

ZooLib is open source under the MIT License and is available at

http://zoolib.sourceforge.net/

I wrote a graphics editor in ZooLib last year and needed to do a lot of direct
access to pixels through raw pointers to read and write graphics files, apply
paint and vectors and do alpha blending as well as scaling the images.  

Each time I did this I would need to ask the ZDCPixmap such questions as its
base address, its dimensions, its pixel bit depth, the number of bytes in an
image row (sometimes there are pad bytes to align the rows to make access
faster at the cost of a little memory), whether the image was inverted (it
would be on Windows but not on Mac), whether it had an alpha channel as well
as its byte order.

Then when I twiddled the pixels the operations would all be based on this
information in complicated ways, for example I ran into the case of scaling a
24-bit packed bitmap into a 32 bit unpacked bitmap and having to add in an
extra byte in the alpha channel to make up the 32 bits.

In the course of this work I went from hard-wiring everything into local
variables to putting some of the functions into library routines and making it
reasonably efficient.  I never went beyond 8 bits per color channel, either 24
bit or 32 bits per pixel.

I feel I gained a good understanding of the problem but never felt my
solutions were as clean or as general as I would like, nor did I feel they
were something I'd want someone else to use.  I'd like to write something new
that would be of more general use, at first in my own application but
eventually to be folded into the ZooLib library for everyone to use.

ZooLib provides easy-to-use GetPixel and SetPixel calls that will access on
pixel at a time and set or fetch a 24-bit RGB value.  But it's quite slow for
large data sets because it needs to make a lot of complicated decisions
regarding the pixel format each time a pixel is accessed; one might have 8-bit
indexed, 24-bit RGB packed pixels or 32-bit aligned RGB pixels, and one might
have to use a color table to convert between RGB values and an index.  With
all the platforms it supports there are many formats it might encounter.  

The most basic purpose of the iterator is to cache this format information and
provide routines that are directly optimized for whatever the result of a
particular caching instance happens to be.  

I found pointers to member functions to be helpful in an earlier try at this,
but as I traced in the debugger through the pointer to member code, I saw that
in one development system at least, dereferencing one actually takes a
significant number of assembler opcodes.

Here's what I envision I'll have when I'm done, I know it's a pretty tall order:

- I want them to be extremely fast - the main objective of writing these
things is speed.  With my first, primitive shot at this I had interactively
animated alpha blending of semitransparent objects a couple hundred pixels
across working responsively on a 150 MHz PowerPC 604 Macintosh.  It would be
great if one could use them in a video game.

- They also need to be quite platform independent; in my case this is aided by
the encapsulation of platform-specific details in the implementation member of
the ZDCPixmap class.

- They must be easy to use.  I would like someone to feel comfortable moving
from GetPixel/SetPixel to using my iterators.  Someone who is not as good a
programmer as me must be able to pick them up quickly and readily learn how to
use them correctly.

- They will be used in a multithreaded environment (ZooLib provides
cross-platform locking and thread classes), although I'm not clear to what
extent you'd want multiple threads hitting the same iterator.  One possible
use would be to create an iterator to a rectangular area, than have an
algorithm that would spawn threads that would divide the operation it carried
out on that iterator among two or more CPUs.

- The iterator could range over an entire image or a rectangular part of one

- You can have const iterators for reading from bitmaps

- You can have non-const ones for writing into them

- You can have iterators that are optimized for sequential access or random
access.  Sequential access may potentially be faster.

- One can use these to support masking operations, where the mask may be an
entirely separate image or an alpha layer, and may be on or off, or an alpha blend

- There are also Region data objects, which aren't strictly bitmaps, but
logically are more like lists of rectangles that the graphics system supports
boolean operations with as well as scaling.  One can convert a bitmap into a
region and vice-versa.  

I'd want to iterate over the pixels that are contained in the part of a bitmap
specified by a region.  One some platforms like Macintosh Quickdraw the
regions use clever algorithms and data structures for speed and efficient use
of memory, but because Apple has patented its region algorithm most other
platforms use much less sophisticated representations.

- I'll have algorithms that take the boundary points of iterators as their
inputs.  One such algorithm, possibly complicated, would scale a rectangular
area from one bitmap into a differently sized and proportioned are into
another, which might be the same bitmap.

- One would have the option of using iterators that give you native access to
raw pixel data, say 16 bits with 5 bits of RGB and 1 bit of alpha, or one
might have automatic conversion to comfortable common formats, like instances
of color value classes that would then have helpful member functions to
operate on the color.

- One could also use iterators from two different bitmaps that had distinctly
different formats and combine them together in a graphics operation, for
example to blend a 16 bit 5,5,5,1 RGBA graphic into a 4-bit indexed graphic.

- It would be extremely helpful if new pixel or bitmap formats could be added
without ripping into the guts of the thing.  This is likely to occur as the
overall ZooLib library is bound to new OS and GUI systems.

Well I guess that's enough to stimulate some conversation.

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.