[boost] Re: Re: A preliminary proposal: AGG project

From: Maxim Shemanarev (mcseem_at_[hidden])
Date: 2002-05-05 15:02:56

Thanks Douglas. It's what I expected in addition to criticism :-)

I actually was thinking adout the iterator_adapter concept, but still
there're
two concerns.

1. Inclusion any non-trivial algorithm into the pipeline (that supports
only InputIterator for some reason) will degenerate the whole
pipeline to InputIterator. Since any pipeline will most probably
contain at least one such an algorithm, the only type of iterators
available will be Input one. So, in general there's no need to
implemen other types, such as RandomAccessIterator.

2. I told you not all the truth :-)
The thing is actually the interface VertexSource supports a sort
of two-dimensional storage. It requires more explanations.
Path (read VertexSource interface) contains a number of polygons
of a number of vertices (it can have several vertices with move_to
flag). But this kind of a path can be rendered with only one attribute,
such as color, type of a stencil, and so on. This is is not enough to
render full-color images, so we will have to use
a vector of paths with different attributes that can be of a polymorhic
type.
Using a vector of paths is often not convenient and sometimes
not possible (remember, the initial source of vertices, does not
have to be a storage, it can generate verices on demand). Besides
even if it's a storage, it can have a great overhead when using a
vector of storages.
So, I used a very simple solution that seems to be satisfactory
enough:
Any VertexSource is a multi-path, which consists of a number of
paths, separated with flag pathflag_stop. It's not quite a vector
of paths, because in case of a storage it uses only one memory
pool for all the paths. It allows to reduce the memory overhead and
to avoid reallocations (class path_storage never reallocs memory).
The reset_iterator method has an integer argument which has a
sematics of an abstract ID. When we form the path somehow,
we in parallel create a vector of attributes and then, when rendering,
use this argument as an ID to associate a particular path with its
attribute. I'll illustrate this idea with the SVG syntax:

  <g style="fill: #ffffff; stroke:#000000; stroke-width:0.172">
     <path d="...vertices..."/>
  </g>
  <g style="fill: none; stroke:#007faa; stroke-width:0.5">
     <path d="...vertices..."/>
  </g>
  <g style="fill: #ffffff; stroke:none" transform="rortate(30)">
     <path d="...vertices..."/>
  </g>

I omited vertices themselves to make the example more clear.
Here we see three paths:
1. Filled with white color (#ffffff) and with a thin black border (#000000).
2. Path with no filling, with a border of  #007faa color and witdth 0.5.
3. Filled path with white color, without border and rotated by 30 degrees.

I tried to create as simple interface as possible with keeping
good flexibility. The example looks very simple, however, it's not
easy to render it. The basic renderer can draw only polygons and does
not have a possibility to render strokes, so, we have to use more than
one pipeline to process it.

struct path_attr
{
   bool fill;
   bool stroke;
   agg::color fill_color;
   agg::color stroke_color;
   double stroke_width;
   agg::affine_matrix transform;
   unsigned path_id;  // This is that very ID mentioned above
};

This path can be completely represented with two objects:

std::vector<path_attr> attrs;
agg::path_storage paths;

The code that forms the paths can look as follows:

while(!path_parser.end_of_paths())
{
    path_attr a;
    a.fill = path_parser.fill_flag();
    a.stroke = path_parser.stroke_flag();
    a.fill_color = path_parser.fill_color();
    a.stroke_color = path_parser.stroke_color();
    a.stroke_width = path_parser.stroke_width();
    a.transform = path_parser.transform();
    a.path_id = paths.add_new_path();  //Assign an ID which is generated by
path_storage
    attrs.push_back(a);
    while(!path_parser.end_of_vertices())
    {
        paths.add_vertex(path_parser.vertex());
    }
}

Then we create a pipeline (actually two of them):

agg::affine_matrix mtx; // Common transformation matrix

// Pipeline1. Consists of an affine transformer only
agg::conv_transform trans_fill(&paths, &mtx);

// Pipeline2. Converts the path into its outline
// and then applies affine transformations.
agg::conv_stroke stroke(&paths);
agg::conv_transform trans_stroke(&stroke, &mtx);

I still use polymorphic classes with a common base class
and virtual functions, but the template variant works in the same way.

And the rendering function:

for(std::vector<path_attr>::iterator i = attrs.begin(); i != attrs.end; ++i)
{
    double x, y;
    agg::pathflag f;
    path_attr& a = *i;

    mtx = a.transform;      // apply affine transformations

    // Render the filled polygon if exists
    if(a.fill)
    {
        trans_fill.reset_iterator(a.path_id);
        while((f = trans_fill.next_vertex(&x, &y)) != pathflag_stop)
        {
            renderer.add_vertex(x, y, f);
        }
        renderer.color(a.fill_color);
        renderer.sweep();
    }

    // Render the stroke if exists
    if(a.stroke)
    {
        stroke.width(a.stroke_width);
        trans_stroke.reset_iterator(a.path_id);
        while((f = trans_stroke.next_vertex(&x, &y)) != pathflag_stop)
        {
            renderer.add_vertex(x, y, f);
        }
        renderer.color(a.stroke_color);
        renderer.sweep();
    }
}

The key moment is that we can easily afford to use a generic container to
store the attributes while using it for vertices can seriously affect the
performance and/or result in great memory overhead with endless
reallocations. So, I used a custom container with custom access
mechanism and custom memory allocation strategy.

But it's just a detail. After all, path_storage is just a class that
can be replaced with any STL container. I  general, using this ID
makes it very easy to create any custom VertexSources that do
not use storages at all. An example of it is a whole visual control-
element based on AGG only and so, platform independent. I used it
in experiments with gamma correction:
http://www.antigrain.com/agg_research/gamma_correction.html

The control generates a lot of polygons with different colors
(read attributes), particulary a B-spline curve and  text, but all it
provides is a simple VertexSource interface. This mechanism seems to
be quite satisfactory for most applications.

There're no ideal solutions, we always have to choose a reasonable
comporomise between genericity and efficiency, memory usage
and speed and so on. For example, embedded software programmers
do not like very much to use STL because of binary code overhead
(it's not a secret using STL results in extra binary code and sometimes the
amount of it is great). I try to design AGG with embedded systems in
mind.

Maybe graphics is too specific area for BOOST to be generalized in a
way all other parts are.

I admit I'm not very experienced in BOOST libraries and this is why I'm
looking for help from BOOST gurus, because it'll take a lot of time
for me to completely integrate AGG with BOOST. Besides, I wouldn't
like to restrict AGG with BOOST only, and so, I'd like the low level of
AGG to be independent on BOOST.

On the other hand, I have a feeling that some BOOST people could be
definitely interested in having a high quality graphic renderer,
that can be used, for example, as an addition to Phyton - just my fantasy.

I'd like to be realistic and I understand I won't be able handle all of it.
I have
a lot of things to implement, especially in the algorithmic part of the
library.
Maybe I'm not a very good designer and I do not claim to be a good one.
But what I can do well is to produce nice graphic algorithms and approaches
and finally I would like to break that petrified as mammoth's crap tradition
in graphics that makes you have a sort of object with hundreds of functions
(see my replies to Mika Heiskanen).

So, I'd like to adjust my suggestion: I remain focusing on the algothithmic
part of the library, but I change my design pattern in such a way that:
1. It could be still independent on BOOST
2. Could be easily "wrapped up" in Boostified interfaces with minimal
   or no overhead.
Before doing that I provide a full set of documentation for the
existing version of the library and then ask people who is most
interested in graphics for some suggestions, cooperation and so on.
If there're no people, interested in "boostified" version, nevermind,
AGG will still be usable and I intend to work on it further.

It also would be perfect to extend the concepts with graphical I/O, as
file one (popular graphical formats) as well as displaying/printing
and so on.

McSeem
http://www.antigrain.com