Skip navigation

Monthly Archives: July 2006

Started in late 2002, OOo’s module basegfx
is now a pretty mature collection of data structures and algorithms
for graphics processing. The set of exported headers sport abstract
data types such as:

  • points, vectors, boxes, ranges, bezier curves
  • matrices
  • polygons and collections of polygons (“poly-polygons”)
  • </ul

    Those are (where sensible) provided in the flavors

    • 1D, 2D, 3D
    • integer and double-precision floating point

    In addition, especially the polygon ADTs are shipped with a set of associated algorithms (provided as free functions, instead of
    member functions):

    • a poly-polygon clipper (comparable to what
      gpc is doing)
    • a poly-polygon triangulator (convert a polygon to triangles, which
      can be fed to a GPU)
    • a function to generate stroked paths from a given polygon
    • plus a lot of basic, but very useful stuff (like svg im/export, scan
      conversion, arc and circle generation, etc.)

    What’s missing, though, is everything related to bitmaps. That’s where
    comes into play, started a few weeks ago and set to provide for pixel
    processing, what basegfx provides for the symbolic graphics

    I’ve initially started this work by using AGG, but quickly found out that
    adding pixel formats other than integer true color ones is pretty hard
    (Because the code is largely undocumented. Because the assumption that
    pixel values can be modified by shift left and right operations, and
    are PODs (i.e. non-class types) is all over the place. And because
    basically, a way to somehow get a hold to the famous extra level of indirection is
    missing. Which, as usual, would have solved this software engineering
    problem). Instead of starting from scratch, we’ve based this on vigra, a framework for generic image processing, which provides an elegant way to add ‘special processing’ before an actual pixel gets assigned a value.

    In order to really get to the point here, I first need to sketch the
    way generic bitmap processing works: it’s the idea of separating data
    access and the actual bitmap manipulation algorithm, using C++
    templates. The concept is borrowed from the STL – bitmap pixel can be
    accessed by (two-dimensional) iterators, which in a very basic sense
    behave like a pointer:

    while( i!=end )
        *i++ = rand();

    If i is a bitmap iterator, the pixel will be set to
    random values with this algorithm. The type of i can be chosen freely,
    and so can the actual pixel format of the bitmap. If one wants to
    e.g. add palette lookup to this algorithm (or scale the random values
    into the appropriate color range) without changing the algorithm’s code, either extremely ugly hacks
    involving proxy objects are necessary (because operator*() is expected
    to return an lvalue, which gets assigned the new value directly), or
    one needs a direct way to ‘see’ both the iterator and the new value
    prior to assignment:

    while( i!=end )
        acc.set(i++, rand());

    The acc variable is a pixel accessor in vigra lingo,
    which takes the iterator and the new value, and accesses the
    corresponding pixel. Now, adding palette lookup, scaling, blending,
    mask operations and much more is as easy as providing a different
    accessor to the algorithms is. Plus, it’s completely orthogonal to
    both the iterator implementation, and the algorithm used. That means,
    you define a set of iterators (for packed-pixel images, for r8g8b8
    images, for r5g6r5 images), a set of accessors (for true color pixel,
    for palette lookup, for blitting through a binary mask), and a set of
    algorithms. And you combine all those freely, i.e. you have the
    cartesian product of variations to choose from.