[boost] Re: A preliminary proposal: AGG project

From: Maxim Shemanarev (mcseem_at_[hidden])
Date: 2002-05-04 12:55:23

Hi Mika,

You seem to be the most interested and the most active person in this
field. Thanks a lot and please abide my graphomania :-)

>   Any library to be added to the C++ standard library should not
>   concern itself by considering how to directly support a given
>   API on a given platform. In the particular case of rendering 2D
>   vector graphics onto a pixel device, this approach is doomed to
>   fail, since the least common denominator of any such platform
>   specific API is the representation of the pixel data itself.
>   Anything higher level, and we're already talking about rendering
>   itself, which the library is supposed to do itself.

Agree. That's what I'm trying to propose.

>   1. A singleton registry for registering various image formats such
>      as png, jpeg and gif for both import, export and import type
>      matching purposes. The last one involves querying whether some
>      iostream contains image data of some specific type or not, filename
>      suffixes are not to be trusted, magick numbers and image library
specific
>      queries are the only reasonably reliable way to do it. This may
involve
>      proxy classes or some similar pattern, but atleast the three methods
>      mentioned above should be supported.

Well, IMO it should be a separate library/concept. I myself extremally
need this, but I cannot afford to work on so many things simultaneously.
And if somebody (you?) could think about it (or maybe try to organize some
development process) it would be just perfect.
There's a number of free libraries of reading/writing different graphic
formats, but they're not sutable for BOOST, because they're
usually GPLed, but most of all, BOOST requires a C++ concept, compatible
with STL (or at least STL-friendly) leaving the implementation of concrete
formats to "coders" :-)
I've never seen such kind of concept and I believe it's time to work on it.

I consider myself equally as a designer and as a coder, you will see below
why I think so.

> The proof of concept would then consist of for example implementing
> PNG and JPEG image formats. The quality of the exported images alone
> is sufficient to prove the quality of the 2D graphics rendering engine.

It would be the easiest way to provide the proof. Besides, it'd open the
door to a variety of applications, such as high quality web-based GIS
systems (see maps.yahoo.com for example).

Still, I do not refuse using SDL for demo examples (but not for the
library!) to show its abilities in dynamic - generating and writing
images from a command-line utility is not impressive enough :-)

> I believe, but cannot verify right now due to a poor terminal
> interface, that Java2D provides two kinds of iterators:
>
>   1. An iterator to traverse the elements of the path. These include
>      line segments, bezier segments and so on.
>
>   2. An iterator to traverse the elements of the path *in reduced form*.
>      Such an iterator converts Bezier curves etc on the fly based on the
>      active flatness parameters. Hence the user only sees moveto and
>      lineto segments.

Well, it's time to explain my concept more thoroughly.
I've been thinking a lot about SVG, Java2D, GDI+, OpenGL and other
concepts and I found them too restrictive and outdated. AGG concept is
much more flexible and BOOST-friendly in its spirit than all existing
ones. I'm trying to propose some innovations even if they look ridiculous.
I'm not afraid to look funny, not everybody can afford it :-)

What is the main thing I don't like in most developed graphic
interfaces and concepts? They all use a single object, implicitely, like
OpenGL or explicitely, like Java2D or GDI+. This object is called
Graphics2D in Java, for example. It has a number of functions of
rendering, transforming, filtering and so on. As you mentioned, it's
a concentrated experience of many intelligent people. The number
of possibilities of the rendering is great, but still it's restrictive,
because you cannot easily add your own unique algorithms
to this object in such a way that it would be natively embedded in it.
The analogy is that I wanted once to replace the PolyPolyFill function
in MFC class CDC. The only way do this was to inherit my own class
from CDC with overridden PolyPolyFill method (hopefully it's virtual).
But there's a number of classes, such as ClientCD, ScreenDC and so
on that are already derived from CDC, thus, I cannot derive them from
my own MyCDC class - it's out of my control. Sorry about that I use
MFC as an example (I really hate it), it's just an illustration of
disadvantages of hardcoded hierachies of classes - you can never
embed or replace anything in the middle of the hierarchy.

The very same thing persists in classical graphic interfaces.
For example, one of your suggestions is the ability to render a polyline
with different kinds of joins - miter, round, beveled. Fine, I agree, I
accept
it, and it's not implemented in AGG yet (there's only beveled join).
But what if you need your own type of join, say, "flowered" one? The only
way to do this is to calculate your own polygon "manually" and to ask
Graphics object to render it. Here the information about your initial
polyline is lost.

More realistic example. You can ask the Graphics object to
render a polyline of a certain width. Good. Then you want to apply
affine transformations, say, scaling. What will happen to the width of the
polyline? It depends on the order in which calcualtions inside the Graphics
object are performed. What is first - calculation of the outline or affine
transformations? The result will depend on this order. When calculation
of the outline is performed first, the visual thickness will change with
changing the scale, otherways it will remain the same. if the scaling
coefficients are different by X and Y the order becomes even more
important. In real life there're both cases are needed. Here's the
illustration of what I mean: http://www.antigrain.com/img/conv_order.gif

Usually the calculation of the outline is applied first and then the affine
transformations. What I want to stress is that you cannot control it, it's
given
by a group of extremally experienced people but still, it's given. You
cannot change the order of calculations. And in general, this is why
the conventional graphic interfaces are so complex (usually hundreds
of functions in a single class). I want to propose some innovations
in graphics field :-)

Boost approach as far as I understand is completely different and
actually the idea of conversion pipelines in AGG came from Boost.

AGG concept allows you to apply indefinite number of graphical
conversions in any order you want and to replace any algorithm
you want. The idea is really simple, I will demonstrate it with
classical virtual functions mechanism. The only difference in using
templates in AGG converters is that the templetized classes provide
you more freedom and less overhead. The following is just an illustration
of pipelines. A similar approach is (or will be) used in render classes
for filtering, applying color stencils, image transformations, texturing
and so on. Let us only focus on pipelines for now.

Suppose you have a very simple abstract class:

class vertex_source
{
public:
   virtual void reset_iterator() = 0;
   virtual pathflag next_vertex(double* x, double* y) = 0;
};

I will use the names and the concepts that exist in currect version
of AGG, although it probably will be changed in future.

Here pathflag is an enum of certain values, particulary, move_to and
line_to.

Then suppose we have an abstract renderer that accepts a pointer
to this class:

renderer::renderer(vertex_source* vs);

When you create a renderer class it starts retrieving the vertices
(or it can do that on request) in the following way:

double x, y;
pathflag f;
vs->reset_iterator();
while((f = vs->next_vertex(&x, &y)) != pathflag_stop)
{
    if(f == pathflag_move_to) { start_new_polygon(x, y); }
    else { add_new_edge_to_existing_polygon(x, y); }
}

That's it! With this abstract class and the renderer we can create any
converters. The only thing we have to obey is to inherit our converter
classes from vertex_source and to override only two methods.

In terms of template meta-programming it means that you don't have
to derive your classes from anything, all you need is to provide
an interface with this exact signature. The word "interface" is
very important.

Let's start from a container that is simply an array of vertices and
overrides
these two methods.

class vertex_array : public vertex_source
{
public:
    virtual void reset_iterator() { idx = 0; }
    virtual pathflag next_vertex(double* x, double* y)
    {
         if(idx >= nvertices) return pathflag_stop;
         pathflag p = pathflag_move_to;
         if(idx > 0) p = pathflag_line_to;
         *x = vertex_x[idx];
         *y = vertex_y[idx];
         ++idx;
         return p;
    }
. . . methods of adding vertices, member variables and so on.
};

This class can be used directly for rendering, but it also can be passed
through a number of converters.

The simplest one is affine transformer. This class calculates new
coordinates according to its affine matrix. It's simplest and straight
because it does not change the semantics of vertices.

class affine_transformer : public vertex_source
{
public:
    affine_transformer(vertex_source* vs) : source(vs) {}
    virtual void reset_iterator() { source->reset_iterator(); }
    virtual pathflag next_vertex(double* x, double* y)
    {
        pathflag p = source->next_vertex(x, y);
        register double tx = *x;
        *x = tx * m0 + *y * m2 + m4;
        *y = tx * m1 + *y * m3 + m5;
        return p;
    }
    // . . .
};

Another one, curve converter is more complex. It accepts a vertex source
that is supposed to contain Bezier segments and then generates a number
of line segments. This class produces what you mean "the path *in reduced
form*".
And every such kind of a class is an iterator in its essence.

And how to use them:

vertex_array va;
va.move_to(x1, y1);
va.line_to(. . .);
va.curve_to(. . .);
. . .
//-------- start pipeline
affine_transformer tr(&va);
curve_converter cc(&tr);
//-------- end pipeline

renderer r(&cc);

Note, that creation of a converter costs nothing or very little - exactly
like creation an iterator in STL. The whole pipeline starts "piping" only
when you call cc.reset_iterator() / cc.next_vertex().

The order of the converters is important and you can cnahge
it if you need. In this exmple affine transformations are applied
first. In this example it'll produce good result because affine
transformations
applied to Bezier control points do not change the shape of the curve.
But, the order can affect the overall performance in this case. For example,
if the transformer was declared after the curve converter it would have
to process much greater number of points. Again, there're no hardcoded
two type of iterators that you mentioned in Java2D. But if you iterate
object
"tr" from the previous example you will obtain the path in its source
form. Object "cc" will produce the simplified path.

You can say "what a big deal?". Yes it is a big deal. Because it does not
restrict your abilities in creating applications. Converters can be very
simple
and can be very complicated. One more example:

Suppose you're working on a GIS system. Here scaling is essntial and very
important. And although AGG renderers have low-level clipping, it can fail
when
you try to enlarge your map because of integer overflow. Besides it'll take
much
more time and memory if you render privitives whose coordinates are far
outside of the rendering framework. What is the solution? Very simple - you
just
include a clipping converter in the proper place of your pipeline. This
converter
clips *polygons* (it's going to be implemented in AGG soon). On the other
hand, there's a number of applications where this high-level clipping can be
omited.

Another example is the constructive area geometry converter. It accepts
two any vertex sources and produces a number of polygons according
to operations "and", "or", "sub", "xor". It's a very complicated converter
(it also will be implemented in AGG).

The point is that if I had a traditional object such as Graphics I would
have to implement a lot at the very beginning and it would take years.
Otherways I would have to change the class constantly from one version
to another and finally it would look as fancy as, say, CDC.

In AGG a very simple interface once provided is not to be changed in future.
You can easily write and add your own converters and use existing ones only
when you need.

Now, what is the major difficulty I have when proposing it in BOOST?
Jens Maurer says:

> An interface using "reset_iterator" and "next_vertex"
> is exactly not STL-like, because it does not allow two
> iterators on the same underlying container-like object.
> The STL uses separate iterator classes and a begin() / end()
> interface on the container, and operator++() on the iterator.
> This allows dealing with subranges."

I agree with it, and to make it more STL-like the idea must be adjusted.
But how? It's not easy.
Graphics is a very scpecific area and often general approaches simply don't
work here. For example. Suppose we have a completely STL-like interface for
a very complicated class of constructive area geometry. It's supposed to
have
iterator, reverse_iterator and the ability to assing iterators to each other
and
start from, say, the middle of the sets of vertices. This interface is much
harder
to implement than the simplest one that produces a number of vertices
consecutively. But the real necessity of this complexity is very very
little.

The major difference between STL containers and AGG converters is that
STL containers have as much developed interface as possible, but the number
of them is restricted. They all have a common iterating mechanism and can
be used in a number of algorithms. AGG has one (or a few) vertex containers
(that can be STL ones) and potencially endless number of iterators
(converters) which will work in a pipeline. They cannot have very complex
interface because it'll be a real pain to implement custom converters.

So, now it's time to ask for suggestions how to adjust the idea in order
make
it more corresponding with STL and BOOST. For now I cannot invent anything
appropriate without affecting the efficiency or without increasing the
complexity
and the amount of code twice of more.
It's not a big deal to change names, return a sort of vertex object instead
of using pointers double* and so on, but still it'll be only cosmetic
changes.
Please help :-)

McSeem
http://www.antigrain.com