Lab 2. 2-D Graphics Primitives

M. Stone and A. Pshenichkin. 9.15.04.

Backbone: Matrix, Pixel, Vector, Point

The Matrix and Pixel classes from the last lab were reused. More information is available in the appropriate section.

Both went through substantial modification, however. We now supplement our Pixel wrapper with direct data through RawPixel and RawChannel, and the Matrix is used to create our Points and Vectors (both simple 3-vectors).

Logging

Given the volume and complexity of the code involved in Graphics, we decided to implement a logging system. Our LogManager, inspired by Ogre's, is a singleton object that creates a uniform interface for multiple logs. The Log class handles log messages. Four log detail levels exist:

  1. LDL_TRACE: A cornucopia of log information, mostly of the useless variety. Sometimes it's good to have an actual trace, though, especially in concert with the gprof profiler.
  2. LDL_DEBUG: Generally useful debugging information. The typical log level for testing our programs.
  3. LDL_WARN: No quotidian data, but still with error logging that smacks of hypochondria.
  4. LDL_ERROR: The code stands mute, resolute in the face of all but the greatest catastrophe. Running something at this level should ideally result in performance indistinguishable from not running any logger at all.

The LogManager shall probably be further expanded as we get into future projects. At the moment, logs can output data to text files or the screen using either cout- or printf-style commands.

The Image Interface and the Graphical Environment

To increase the portability and versatility of our code, we created an Image interface. It defines the standard functions for interacting with an image, such as loadImageFromFile, getWidth, and getImageData. Currently it interacts with ILImage, a wrapper for DevIL, but it will allow us to shift to our own image manipulation library with minimal effort if we so desire.

Image information can be accessed through the interface, which fills an ImageInfo structure on demand. This structure contains information on the image: height and width, default depth, the number of pixels in the image, the number of bytes per pixel, and the image size.

For more information on our Image interface, see our API documentation.

Line Anti-Aliasing Algorithm

We implemented anti-aliasing using virtual convolution to render graphics directly from the object space (wherein objects are described in terms of geometric primitives such as lines, polygons, and splines) to the final image space, using an algorithm based on perpendicular point-line distance, as suggested by Turkowski[*]. Unlike supersampling-based methods, there is no higher-resolution image space that is then shrunk down to the display image. Anti-aliasing occurs as an object is being drawn rather than during output.

The general idea is that we can decide how much a given line contributes to a pixel by measuring the distance from the pixel center to the closest point on that segment. An alpha value is then assigned based on the distance and object type.

The algorithm is based on convolution, using numerical integration of the expression

Where h(r) = exp(-r^2 / (2 * sigma^2)), with the standard deviation sigma setting the width of the line. See Turkowski's paper for more information on the technique.

The lines it creates are very nicely antialiased, as this magnification reveals:

The object above is a set of lines combined to resemble a polygon, but differently colored to demonstrate how our blending is applied (they were part of a figure drawn in counterclockwise order).

While calculating distances and doing numerical integration takes time, it does free us from using a super-high-resolution working image space, and is more flexible than Bresenham's various algorithms: it is possible to adapt this method to any shape for which an appropriate distance-calculating algorithm exists.

Anti-Aliasing for Non-linear Primitives

By expressing an ellipse as a point and two vectors denoting the axes, we can apply the three basic transformations (scaling, translation, rotation) to the ellipse object without destroying it. Circles are treated as a special case of the ellipse. Adapting Turkowski's algorithm to ellipses is rather simple, requiring only an alteration of the method for distance calculation. Implementing said functions is painful, but possible[**]. Both Numerical Recipes in C and the MathWorld website presented algorithms that we couldn't manage to implement successfully. It was only after we found a paper on the subject by David Eberly that we managed to make it all work.

Sample Images


References

* - Turkowski, Kenneth. Anti-Aliasing through the Use of Coordinate Transformations. ACM Transactions on Graphics, Vol 1, No 3, July 1982, Pages 215-234.

** - Eberly, David. Distance from a Point to an Ellipse in 2D. Magic Software, Inc.

Eberly, David. 3D Game Engine Design. 2000, Morgan Kaufmann.

M. Stone and A. Pshenichkin.