Anti-Grain Geometry |
In
this article I would like to introduce my work called |
Scalable 2D vector graphics is widely used in all kinds of applications and now the performance of modern processors makes it affordable to use high quality vector graphics. |
High quality means multilevel Anti-Aliasing and subpixel accuracy. Subpixel accuracy is often underestimated, but in general it's very important to have a possibility of subpixel positioning. It's especially important to be able to set fractional line width that can be even less than one pixel. I would say that Anti-Aliased rendering is practically useless without subpixel accuracy. |
The first question that can arise is “What is this needed for?” or even “Is there a need of yet another reinvention of the wheel?” |
The short answer is as follows. Yes, there are many graphic standards, protocols and libraries, but nothing that fits all my needs. It was my main motivation to start AGG, namely, my exclusive requirements. Later other people found it very interesting too. |
You can think of AGG as of a rendering library that creates raster images in memory from some vectorial representation. But this definition is just the first approximation. In general, you can use any part of the library, not obligatory as a rasterizer or renderer. AGG can be used in many applications where there is a need for high quality and fast 2D graphics. It can be GIS/cartography applications, fancy looking graphic user interfaces, different kinds of charts and diagrams, CAD/CAM, and so on. Besides, AGG is platform independent, lightweight, compact, and robust It also can be perfectly used in embedded systems and mobile devices. |
First, let me briefly describe the existing tools and libraries that can be used as 2D rendering engines. The fastest software 2D renderer that produces images of appropriate quality is well known Macromedia Flash viewer. |
The other one is SVG standard from W3C committee, http://www.w3.org/Graphics/SVG/ for which we can find a number of viewers (the most advanced one is Adobe SVG, http://www.adobe.com/svg/). But they both are “end-user” applications and cannot be used as rendering libraries available from C++. SVG would be the best 2D standard if there were available implementations that support the whole SVG specification and provide appropriate quality, performance, and consume reasonable amount of memory. |
The most widely used industrial libraries available from many languages are OpenGL, Apple Quartz and GDI+. |
OpenGL is good and standard, but the quality of 2D graphics is very poor. It's perfectly “hardware accelerated”, but there are no available accelerators that produce any valuable quality of 2D graphics. Alex Eddy has performed a research that clearly shows the lack of the quality in most popular OpenGL accelerators. http://homepage.mac.com/arekkusu/bugs/invariance/ |
GDI+ has also very poor quality of rendering, it's slow and has too many bugs to be used in practice, not to mention that it's available only on Microsoft Windows platform. |
Apple Quartz has the most advanced API and quality, but it's available only on Apple computers. |
There are two Open Source libraries, LibArt by Raph Levien http://www.levien.com/libart/ and Cairo Graphics, http://cairographics.org/. LibArt development was abandoned some time ago, and the problems with numerical stability don't allow you to use it in practice. |
Cairo Graphics is in active development and it is definitely worth considering. Still, Cairo Graphics has certain limitations, mostly because of its hardcoded rendering model. |
Besides, LibArt and Cairo Graphics are released under LGPL license which is too restrictive in many cases. |
Another very good library is called ImageMagick (http://www.imagemagick.org), but its primary purpose is image processing. |
The general problem of all existing graphic libraries and tools is that they are too restrictive. They all are “black boxes”, even open source ones. I feel I need to explain this statement. Theoretically you can modify an open source library in any way you want (assuming that it doesn't contradict the license). But as soon as you modify a single byte you create another branch of the library and have to take care of merging your modifications with new versions from the authors. After some point it becomes a nightmare. In my opinion the real “openness” of the library appears when you can extend its functionality without having to modify a single character in the distributed code. C++ allows us to do that. |
AGG uses C++ class and function templates very actively. The same functionality can be achieved using dynamic polymorphism, that is, classes with overridden virtual functions. But the templates allow you to optimize the code having very flexible and convenient design. Polymorphic classes work quite well until a certain level of detailization. A typical task in vector graphics is to have a vertex conversion pipeline. For example, it can be some source of vectorial commands like MoveTo/LineTo/CurveTo, then there is a converter that “flattens” curves, then a stroke generator, then affine transformer and so on. In most graphic libraries the pipelines are hardcoded. If we want it to be more flexible, that is, if we want to construct custom pipelines, you will have to use polymorphism. It's appropriate to have one virtual call per vertex but can be too expensive to have a virtual call per vertex per pipeline element. Another approach is to have “static” polymorphism, that is, to use class templates. It does not directly allow you to construct pipelines dynamically, at run time, but in most cases you don't really need it. Most probably you only want to have a possibility to construct pipelines at compile time, and if you really need dynamic polymorphism it's very easy to write polymorphic wrappers whose interfaces are compatible with what the templates expect. So that, in AGG it's you who has full control upon the functionality and performance. The very same approach is used in the raster part of the rendering pipeline. You can write your own low level renderers that work with different color spaces, your own gradient functions, your own span generators, and so on. An implementation based on classical polymorphic classes would cost you several virtual calls per each pixel, while templates allow you to do so for no extra overhead. |
Below I just enumerate the key features of the library, so that you could have a general idea of where it can be useful for you. |
|
The library and examples were successfully compiled and tested on the following platforms: |
|
AGG doesn't have any predefined rendering model, it's like "a tool to create other tools". The architecture and the philosophy of the library is determined by the main goal of its creation. The goal is to have a set of 2D tools united with a common idea. You and only you define the resulting architecture and rendering model. AGG is open and flexible but not that obvious and easy to use as other "conventional" libraries like GDI+ or Quartz. Besides, it makes sense to mention that AGG has some restrictions too, but it's only because some algorithms and design solutions are not yet implemented. In particular, AGG currently supports only path-based model, and there is no straight way to render graphics from Macromedia Flash format. Flash is edge-based, so, you can render a multi-color scene in one pass. In some cases it's better, but in general it's more restrictive and more difficult in use. Currently we can say that AGG is more SVG centric rather than Flash centric. |
The following picture represents a typical architecture of a rendering engine based on AGG. |
Pixel format renderers perform basic alpha-blending operations in the resulting frame buffer. They do not perform any clipping, thus, it's unsafe to use them directly, so, if the coordinates are out of range it can result in undefined behaviour, most probably segmentation fault. It doesn't mean that the design is bad, it means that you can write your own color space and pixel format renderers, and you don't need to worry about clipping because it is already provided on a higher level. It's quite possible to write a renderer to work in another color space, say, XYZ or Lab, and define your own color type. These additions will not affect anyhow the other parts of AGG. |
Currently AGG provides 15, 16, 24, and 32 bits RGB and RGBA pixel formats. |
Alpha-mask adaptor allows you to use an additional transparency channel when rendering. Strictly speaking there can be any kind of an adaptor. Alpha-mask is just an example of it. |
The basic renderer (renderer_base) accepts a pixel format renderer as its template argument and it's main purpose is level clipping. It provides essentially the same interface as pixel format renderers. Also, there is renderer_mclip which is the same in use but it can perform clipping to a number of arbitrary rectangles. |
One of the key concepts in AGG is the scanline. The scanline is a container that consist of a number of horizontal spans that can carry Anti-Aliasing information. The scanline renderer decomposes provided scanline into a number of spans and in simple cases (like solid fill) calls basic renderer. In more complex cases it can call span generator. |
Span Generator is used in all cases that are more difficult than solid fill. It's a common mechanism that can produce any kind of color spans, such as gradients, Gouraud shading, image transformations, pattern fill, and so on. Particularly this mechanism allows you to transform a part of the image bounded with an arbitrary shape with Anti-Aliased edges. The span generator can consist of the whole pipeline, for example, there can be an image transformer plus alpha (transparency) gradient. |
The scanline rasterizer accepts a number of arbitrary polygons as its input and produces anti-aliased scanlines. This is the primary rendering technique in AGG. It means that the only shape that can be rasterized is a polygon (poly-polygon to be exact). If you need to draw a line you need to calculate at least four points that define its outline. At the first sight it can seem like an overkill, but it isn't. The main point is that the algorithm uses subpixel accuracy and correctly rasterizes any shapes, even when a single pixel is crossed by the edges many times. It allows the result to remain consistent regardless of the scale and the algorithm guarantees that there will be no defects. |
The initial idea was taken from the rasterizer of FreeType font engine by David Turner (http://www.freetype.org). David kindly allowed me to rewrite the rasterizer in C++ and release the code independently. |
Such kind of the design (rasterizer → scanline_renderer → base_renderer → pixel_format) allows us to implement very interesting algorithms, for example, renderers optimized for LCD color triplets (like Microsoft ClearType) and it will be applicable to all primitives, not only for text. |
This is yet another algorithm of drawing Anti-Aliased lines. The use of the algorithm is more limited than the scanline rasterizer, but it also has many advantages.
|
The outline rasterizer is just an adaptor that unifies the use of the solid outline rasterizer and the one with image patterns. |
The vertex pipeline consists of a number of converters. Each converter accepts an abstract Vertex Source as the input and works as another Vertex Source. Usually graphic libraries have hardcoded pipelines, typically they consist of a curve decomposer (that converts curves to a number of short line segments), affine transformer, dash generator, stroke generator, and polygon clipper. |
In AGG you can construct custom pipelines and there can be as many pipelines as you need. Besides, the pipelines can have branches, in other words you can extract vertices from any point of the pipeline. The most important thing is you can combine the converters as you want and get quite different results. |
The example below demonstrates how to create basic types needed for rendering and the effect of the pipelines. To keep the things as simple as possible it will be a console application that produces a raster file (result.ppm) that has a very simple format. You can display this files with many kinds of viewers, for example, IrfanView (http://www.irfanview.com/). |
Also I'd like to mention that it's not necessary for AGG to have any building environment. It has automake/autoconfig files, but you can do without them. Since AGG doesn't depend on any platform-specific tools you can just include all necessary source files into your project/makefile and they will perfectly compile and work. |
AGG is written according to the “Just Compile It” principle. |
Type
(or take from the CD) the following code and name the file
|
#include <stdio.h> #include <string.h> #include "agg_pixfmt_rgb24.h" #include "agg_renderer_base.h" #include "agg_renderer_scanline.h" #include "agg_scanline_u.h" #include "agg_rasterizer_scanline_aa.h" #include "agg_path_storage.h" enum { frame_width = 200, frame_height = 200 }; // Writing the buffer to a .PPM file, assuming it has // RGB-structure, one byte per color component //-------------------------------------------------- bool write_ppm(const unsigned char* buf, unsigned width, unsigned height, const char* file_name) { FILE* fd = fopen(file_name, "wb"); if(fd) { fprintf(fd, "P6 %d %d 255 ", width, height); fwrite(buf, 1, width * height * 3, fd); fclose(fd); return true; } return false; } int main() { // Allocate the frame buffer (in this case "manually") // and create the rendering buffer object unsigned char* buffer = new unsigned char[frame_width * frame_height * 3]; agg::rendering_buffer rbuf(buffer, frame_width, frame_height, frame_width * 3); // Create Pixel Format and Basic renderers //-------------------- agg::pixfmt_rgb24 pixf(rbuf); agg::renderer_base<agg::pixfmt_rgb24> ren_base(pixf); // At last we do some very simple things, like clear //-------------------- ren_base.clear(agg::rgba8(255, 250, 230)); // Create Scanline Container, Scanline Rasterizer, // and Scanline Renderer for solid fill. //-------------------- agg::scanline_u8 sl; agg::rasterizer_scanline_aa<> ras; agg::renderer_scanline_aa_solid< agg::renderer_base<agg::pixfmt_rgb24> > ren_sl(ren_base); // Create Vertex Source (path) object, in our case it's // path_storage and form the path. //-------------------- agg::path_storage path; path.remove_all(); // Not obligatory in this case path.move_to(10, 10); path.line_to(frame_width-10, 10); path.line_to(frame_width-10, frame_height-10); path.line_to(10, frame_height-10); path.line_to(10, frame_height-20); path.curve4(frame_width-20, frame_height-20, frame_width-20, 20, 10, 20); // The vectorial pipeline //----------------------- ras.add_path(path); //----------------------- // Set the color and render the scanlines //----------------------- ren_sl.color(agg::rgba8(120, 60, 0)); agg::render_scanlines(ras, sl, ren_sl); // Write the buffer to result.ppm and liberate memory. //----------------------- write_ppm(buffer, frame_width, frame_height, "result.ppm"); delete [] buffer; return 0; } |
Then you can compile and link this code with AGG: using GNU C++: |
g++ -I/agg2/include example_pipeline1.cpp /agg2/src/agg_rasterizer_scanline_aa.cpp /agg2/src/agg_path_storage.cpp /agg2/src/agg_bezier_arc.cpp /agg2/src/agg_trans_affine.cpp |
or Microsoft C++, v6 or later: |
cl -I/agg2/include example_pipeline1.cpp /agg2/src/agg_rasterizer_scanline_aa.cpp /agg2/src/agg_path_storage.cpp /agg2/src/agg_bezier_arc.cpp /agg2/src/agg_trans_affine.cpp |
Of
course, you will need
to replace |
The result.ppm should be as follows: |
You can think that this code is too complex to produce this simplest figure, but let us look at the following changes. |
Currently
we have a null-pipeline, that is an empty one. In this case
all the points are interpreted like move-to/line-to commands. This is
why the call of |
The
first modification is to add the curve converter
(curve flattener in other words), that is, the one that decomposes
Bezier
curves to a number of short line segments ( |
Add |
// The vectorial pipeline //----------------------- agg::conv_curve<agg::path_storage> curve(path); ras.add_path(curve); //----------------------- |
Also add /agg2/src/agg_curves.cpp to the compile list and see the result: |
Then
let as draw a stroke ( |
Add |
// The vectorial pipeline //----------------------- agg::conv_curve<agg::path_storage> curve(path); agg::conv_stroke<agg::conv_curve<agg::path_storage> > stroke(curve); stroke.width(6.0); ras.add_path(stroke); //----------------------- |
Add /agg2/src/agg_vcgen_stroke.cpp to the compile list. The result is: |
Of course, you can set line width, line cap, and line join. Our polygon is not closed, to close it just call: |
path.close_polygon(); |
I hope you get the idea of how to draw a filled polygon with a stroke. Just in case let us see this code: |
// The vectorial pipeline //----------------------- agg::conv_curve<agg::path_storage> curve(path); agg::conv_stroke<agg::conv_curve<agg::path_storage> > stroke(curve); stroke.width(6.0); // Set the fill color and render the polygon: //----------------------- ras.add_path(curve); ren_sl.color(agg::rgba8(160, 180, 80)); agg::render_scanlines(ras, sl, ren_sl); // Set the stroke color and render the stroke: //----------------------- ras.add_path(stroke); ren_sl.color(agg::rgba8(120, 100, 0)); agg::render_scanlines(ras, sl, ren_sl); //----------------------- |
Here we can see that the pipeline consists of two consecutive converters (curve and stroke) and we can use both of them in the very same way. |
The
next step is adding affine transformations and the main
question is where to add them. The answer is it depends.
You can add the affine transformer before the curve converter,
so that it will process very few points, but the stroke converter
will generate a stroke as if it were the original shape.
Let us see ( |
The pipeline is: |
// The vectorial pipeline //----------------------- agg::trans_affine matrix; matrix *= agg::trans_affine_translation(-frame_width/2, -frame_height/2); matrix *= agg::trans_affine_rotation(agg::deg2rad(35.0)); matrix *= agg::trans_affine_scaling(0.4, 0.75); matrix *= agg::trans_affine_translation(frame_width/2, frame_height/2); agg::conv_transform<agg::path_storage, agg::trans_affine> trans(path, matrix); agg::conv_curve< agg::conv_transform< agg::path_storage, agg::trans_affine> > curve(trans); agg::conv_stroke< agg::conv_curve< agg::conv_transform<agg::path_storage, agg::trans_affine> > > stroke(curve); stroke.width(6.0); // Set the fill color and render the polygon: //----------------------- ras.add_path(curve); ren_sl.color(agg::rgba8(160, 180, 80)); agg::render_scanlines(ras, sl, ren_sl); // Set the stroke color and render the stroke: //----------------------- ras.add_path(stroke); ren_sl.color(agg::rgba8(120, 100, 0)); agg::render_scanlines(ras, sl, ren_sl); //----------------------- |
And the result: |
Now
let us modify the pipeline in such a way that the affine
transformer would be after the stroke generator ( |
// The vectorial pipeline //----------------------- agg::trans_affine matrix; matrix *= agg::trans_affine_translation(-frame_width/2, -frame_height/2); matrix *= agg::trans_affine_rotation(agg::deg2rad(35.0)); matrix *= agg::trans_affine_scaling(0.4, 0.75); matrix *= agg::trans_affine_translation(frame_width/2, frame_height/2); agg::conv_curve<agg::path_storage> curve(path); agg::conv_transform< agg::conv_curve<agg::path_storage>, agg::trans_affine> trans_curve(curve, matrix); agg::conv_stroke<agg::conv_curve<agg::path_storage> > stroke(curve); agg::conv_transform< agg::conv_stroke<agg::conv_curve<agg::path_storage> >, agg::trans_affine> trans_stroke(stroke, matrix); stroke.width(6.0); // Set the fill color and render the polygon: //----------------------- ras.add_path(trans_curve); ren_sl.color(agg::rgba8(160, 180, 80)); agg::render_scanlines(ras, sl, ren_sl); // Set the stroke color and render the stroke: //----------------------- ras.add_path(trans_stroke); ren_sl.color(agg::rgba8(120, 100, 0)); agg::render_scanlines(ras, sl, ren_sl); //----------------------- |
Here we actually have two pipelines, path→conv_curve→conv_transform, the other one is path→conv_curve→conv_stroke→conv_transform. At the first sight it looks like now the stroke is thinner. But it's more complex than that. Note that the width of the stroke is not uniform. I intentionally set different scaling coefficients by X and Y to demonstrate that you can control the result by changing the order of the converters. |
Note that the pipeline branches after conv_curve. For the sake of efficiency it would be better to keep the fill pipeline as it was in the previous example (path→conv_transform→conv_curve). This code just demonstrates a possibility to have complex pipelines. |
In the last example let us demonstrate some non-linear transformation effects. It will be a circular warp magnifier. But since the transformation is non-linear, we can't just transform vertices, we need to prepare the initial path in such a way that the initial vectors would consist of many short line segments. Of course, we could do that when adding vertices to the path storage, but there is a better way. We use an additional intermediate converter that segments long vectors. It's conv_segmentator. |
We also need to add two include files: |
#include "agg_conv_segmentator.h" #include "agg_trans_warp_magnifier.h" |
And
the pipelines look as follows ( |
// The vectorial pipeline //----------------------- agg::trans_affine matrix; matrix *= agg::trans_affine_translation(-frame_width/2, -frame_height/2); matrix *= agg::trans_affine_rotation(agg::deg2rad(35.0)); matrix *= agg::trans_affine_scaling(0.3, 0.45); matrix *= agg::trans_affine_translation(frame_width/2, frame_height/2); agg::trans_warp_magnifier lens; lens.center(120, 100); lens.magnification(3.0); lens.radius(18); agg::conv_curve<agg::path_storage> curve(path); agg::conv_segmentator<agg::conv_curve<agg::path_storage> > segm(curve); agg::conv_transform< agg::conv_segmentator< agg::conv_curve< agg::path_storage> >, agg::trans_affine> trans_curve(segm, matrix); agg::conv_transform< agg::conv_transform< agg::conv_segmentator< agg::conv_curve< agg::path_storage> >, agg::trans_affine>, agg::trans_warp_magnifier> trans_warp(trans_curve, lens); agg::conv_stroke< agg::conv_segmentator< agg::conv_curve< agg::path_storage> > > stroke(segm); agg::conv_transform< agg::conv_stroke< agg::conv_segmentator< agg::conv_curve< agg::path_storage> > >, agg::trans_affine> trans_stroke(stroke, matrix); agg::conv_transform< agg::conv_transform< agg::conv_stroke< agg::conv_segmentator< agg::conv_curve< agg::path_storage> > >, agg::trans_affine>, agg::trans_warp_magnifier> trans_warp_stroke(trans_stroke, lens); stroke.width(6.0); // Set the fill color and render the polygon: //----------------------- ras.add_path(trans_warp); ren_sl.color(agg::rgba8(160, 180, 80)); agg::render_scanlines(ras, sl, ren_sl); // Set the stroke color and render the stroke: //----------------------- ras.add_path(trans_warp_stroke); ren_sl.color(agg::rgba8(120, 100, 0)); agg::render_scanlines(ras, sl, ren_sl); //----------------------- |
The compilation command line is: |
g++ -I/agg2/include example_pipeline7.cpp /agg2/src/agg_rasterizer_scanline_aa.cpp /agg2/src/agg_path_storage.cpp /agg2/src/agg_bezier_arc.cpp /agg2/src/agg_trans_affine.cpp /agg2/src/agg_curves.cpp /agg2/src/agg_vcgen_stroke.cpp /agg2/src/agg_vpgen_segmentator.cpp /agg2/src/agg_trans_warp_magnifier.cpp |
The result: |
These
examples demonstrate the main principle of AGG design, that is
that you have full control upon your rendering model and required
capabilities. The declarations can look too complex, but first,
they can be simplified with the use of |
The raster pipelines are organized in a similar way, but they are usually much simpler. After the vectorial shape is rasterized you can do the following: |
|
The number of possibilities is practically endless, and the point is that you can always write your own algorithms and span generators and insert them into the pipeline. |
AGG has many other interesting algorithms, in particular, using raster images as line patterns. This is a very powerful mechanism for cartography and similar applications and I haven't seen any valuable implementation of it so far. |
Currently AGG is in active development, but its main interfaces are pretty much stabilized. |
You can find many other examples, including multi-platform interactive ones on the Antigrain.com web site http://antigrain.com. |