Fog-Framework Blog

Quadratic Bézier Curves Stroker

2011-08-08T22:19:00.008+02:00

Introduction

Stroking is a common task of every graphics library. When I started writing Fog-Framework, I used algorithms from antigrain to work with vector geometry. However, the antigrain can only stroke polygons, so quadratic and cubic Bézier curves must be first approximated into the line segments. When a graphics path is stroked, the information about curves is definitely lost, and very acute angles are not stroked properly unless very large value is used for property called approximation-scale (it's called flatness in other graphics libraries).

This inaccuracy can lead into problems. For example to stroke a path twice the curve must be approximated into many line segments. More line segments means more vertices, which means more cpu power to transform them, for example.

The purpose of this article is to demonstrate the work to replace the old polygon stroker with a new curve-to-curve stroker. The actual limitation is that current version (2011-08-08) can stroke quadratic Bézier curves only.

Background and Implementation Notes

The new curve-to-curve stroker is highly inspired by the work of Mike "Pomax" Kamermans, see his excellent resource A primer on Bézier curves, section How to scale curves. Please try the interactive example provided in the linked article. The quadratic Bézier curve scaling is definitely the way to go. This method is precise for "safe" curves, which are defined as curves where the angle between the two lines which define the curve is not acute. I found that this condition is not the best one and I adjusted the angle to 100 degrees.

If the "safe" curve criteria is not met, then the curve must be subdivided into smaller ones. There are several ways how the subdivision criteria are created. The author of Bézier primer used subdivision based on curve extremas (curve is first rotated so extrema is always found, if curve is not degenerate), but I noticed that the offset of commonly used curves is not precise, so I adjusted the mechanism how the curve is subdivided and I added some conditions for subdivision. This means that Fog-Framework generates more curves, but I found it more precise (for me it's perfect).

Results

The results of new curve-to-curve stroker (left) vs the antigrain stroker (right). The number of resulting curve segments generated by new curve-to-curve stroker depends on the curvature of the original curve, the number of line segments generated by antigrain stroker depends on the curve length and the flatness which was set to 0.25 (the default value).

As can be seen, the degenerate cases are handled more precisely by curve-to-curve stroker, because the corners are approximated using curves, instead of lines. I think that the curve-to-curve stroker generates a lot of curves in this case, but the resulting shape looks better than shape approximated by using line segments only.

Conclusion

This is only the beginning of my stroker implementation. I'd like to post another article related to the stroking of cubic Bézier curves after finished. The final implementation will be part of Fog-Framework, so everyone can use it without restrictions.

News

2011-02-25T00:19:00.004+01:00

News

Some people are interested about the news in Fog-Framework, because the last commit is more than two months old. It's simple, I'm working on something really new that took me all the free time. I'd like to summarize my goals, my work and the future of Fog-Framework in this post.

First of all, I'd like to highlight my primary goal - make the library usable for consumers! This is really my primary goal and all my work is focused on it. It means that API must be stabilized, conventions must be finished and long-time incomplete features completed. My second goal is to make the library really fast and full-featured. The speed is very important and the incoming changes increase the performance of the library a bit. I think that Fog-Framework is going to be the fastest open-source 2d graphics library available.

The summary of incoming features:

Support for 32-bit integer, 32-bit/64-bit floating point geometry (integer geometry is limited and only used for basic shapes like rect/box).
Support for high-quality image formats (16-bit per component) including high-quality rasterizer, compositing and image-filtering.
Support for 24-bit RGB image format and 16-bit 555/565 image formats.
Support for LCD anti-aliasing and rasterization.
Increased number of compositing functions for SRC and SRC_OVER operators, reduced number of all other compositing operators (these are not so used).
Remove non-premultiplied ARGB format. It always caused problems.

Of course not everything is completed, but I did really progress to support all of these features and to allow creating additions in the future. The number of image formats will probably not grow, because I think that all (A)RGB formats are included. Only exceptions are HSV/CMYK and others, but do we need these?

The summary of extensions which will be implemented this year:

Shaders - shader language which can be used as a source pattern generator, pixel compositor and image filter.
C/C++ plugins - custom pattern generator and compositor extensions written in C++.
JIT compiler - my long-time dream.

It's now really easy to think about shaders and C/C++ extensions, because I can simply use floating-point based mathematics for this purpose. The AHSV conversion will be possible on-the-fly so custom shaders / compositing can bring really cool effects for UI and other graphics.

Summary

I know that these changes are huge. It took me a lot of time to refactor the library, create new API conventions and helper libraries (Fog-Face), but I'm sure that these steps were needed to make library more usable for various consumers and various demands. How many libraries support 64-bit image formats? How many libraries allow to use C++/Shader extensions? This all is going to be available in Fog - optimized to the death, portable and easy to use.

Other thinking

I saw many graphics libraries and it's interesting that Qt and Cairo is using division by 255 with floating-point precision (there is trick to do it fast). I used that division in old code too, but now I changed everything to scale to 256, adding 1 to the component or alpha to make it 0...256. The main reason why the div255 is used is the fact, that image formats are based on BYTEs and only value from 0 to 255 can be stored in it.

But the main problem is that when using fixed-point rasterizer, bilinear filter and all other effects/mathematics, the resulting scale is always from 0 to 256, inclusive. For example AGG rasterizer produces values from 0 to 256, but the 256 is saturated to 255 by sweep_scanline(). So I introduced some new span formats to use 0...256 scale (using WORD) and 0...65536 scale (using DWORD) and rasterizer is now able to create mask using non-saturated values. More memory impact is not visible, because each scanline produced by rasterizer is discarded after use. The positive thing is that blending is a bit faster, because division by 256 is really simple compared to optimized division by 255.

Update: Now only mask is scaled, alpha-blending uses div255.

I'd like to add specialized solid-color rasterizer that will be able to fill image directly without producing a scanline for some pixel formats. This should be faster and it's the upper limit where I can go keeping high-quality AGG rasterizer.

And when the code will be ready? I hope that early. I need to integrate Fog-Framework with one commercial product I'm working on so I really need it to be stable and fast:)

Vector geometry resources

2010-10-22T00:59:00.014+02:00

Introduction

Small post about resources I found useful when working on Fog-Framework. Mainly about geometry - transforms, bezier curves, etc...

Code

Graphics Gems - Graphics Gems is not only about theory, but also about the code. You can found there bezier curve approximation, length and helpers, arc approximation and various algorithms that describes collision detection and intersection. The code is old, but the algorithms not.
Computing the Arc Length of Quadratic Bezier Curves
Computing the Arc Length of Cubic Bezier Curves
AntiGrain - Everybody already knows.
FreeType - Bézier curve approximation using fixed point, text hinting, ...
Degrafa - Graphics Framework for Flex

Papers, Materials

Computer Aided Geometric Design (http://cagd.cs.byu.edu/~557/)

Wiki:

Interactive

Introduction to cubic and quadratic Bezier curves

More...

If you need more just google for them. If you think that I'm missing something just leave a note;-)

News, Class Naming Schema, Transforms

2010-09-20T22:52:00.010+02:00

Introduction

Class naming schema describes how classes are named according to their features. Fog-Framework contains many version of classes describing the same problem. The main difference between them is, however, the data-type used to store class members. The main goal of this post is to introduce new class naming schema.

History

There were used several schemas in history, but it was never consistent in all library modules. For example Point and PointF were initial versions of vertex-based classes. Point was integer version and PointF was double-precision floating point version.

This way was changed when I introduced classes to also work with points based on 32-bit float data type. The reason to add also this version is simple - OpenGL support and improving performance of Fog-Framework running by hardware without double-precision floating point unit.

New scheme was to prefix class using the data-type. So Point was changed to IntPoint and PointF was changed to DoublePoint, introducing new class named FloatPoint. This scheme was better, because you are always looking at the data-type, but it's longer and the prefix doesn't look good.

There are several classes where schema was never applied. For example Argb class describes color using scalar 32-bit number (8-bit per component), but how to name that if I want two versions, floating-point based and integer-based? FloatArgb looks really weird to me so I started thinking about a good replacement.

Class Naming Schema

After some hours of work I decided to use suffix-form. Each class starts with its name and if there are several versions of it the suffix is added. Suffix always starts using Capitalized letter and can be only one character long. For example there are PointI, PointF and PointD classes that represents point now.

Argb class was renamed to ArgbI and ArgbF class was introduced. I added more classes related to color management so there are also AhsvF and AcmykF classes.

List of classes used for color management

ArgbI - ARGB color using 8-bit per entity (packed to 32-bit scalar).
ArgbF - ARGB color using 32-bit float per entity.
AhsvF - AHSV color using 32-bit float per entity.
AcmykF - ACMYK color using 32-bit float per entity.
Color - Class that can hold ArgbI, ArgbF, AhsvF or AcmykF.

List of geometric classes:

PointI - Point (X, Y) using 32-bit integers.
PointF - Point (X, Y) using 32-bit single-precision floats.
PointD - Point (X, Y) using 64-bit double-precision floats.
SizeI - Size (W, H) using 32-bit integers.
SizeF - Size (W, H) using 32-bit single-precision floats.
SizeD - Size (W, H) using 64-bit double-precision floats.
BoxI - Box (X1, Y1, X2, Y2) using 32-bit integers.
BoxF - Box (X1, Y1, X2, Y2) using 32-bit single-precision floats.
BoxD - Box (X1, Y1, X2, Y2) using 64-bit double-precision floats.
RectI - Rect (X, Y, W, H) using 32-bit integers.
RectF - Rect (X, Y, W, H) using 32-bit single-precision floats.
RectD - Rect (X, Y, W, H) using 64-bit double-precision floats.
TransformF - 3x3 matrix using 32-bit single-precision elements.
TransformD - 3x3 matrix using 64-bit double-precision elements.
PathF - Path using 32-bit single-precision vertices.
PathD - Path using 64-bit double-precision vertices.
PathBuilderF - Path-builder using 32-bit single-precision vertices.
PathBuilderD - Path-builder using 64-bit double-precision vertices.

Goals

The main reason to change the naming schema of classes was the future. Any class can be extended without worrying about syntax from now. For example 64-bit ARGB color can be added in the future (ArgbD), without breaking the API and binary compatibility.

News - Transform

I'd sucessfully implemented new matrix classes called Transform[F|D] which replaced [Float|Double]Matrix. I used similar technique which can be found in Qt/Skia - optimizing matrix transformation / point transformation using a matrix type. The matrix types are identity, translation, scaling, rotation, affine and projection.

As you noticed there is new transform not available before - Projection. The Transform class is 3x3 matrix that allows to produce nice transformations in perspective. This kind of transformation is available nearly in all other libraries

News - Color Management

There is also new Color class that allows to store into it ARGB, AHSV or ACMYK color. The class remembers which color model was used to store a color so it should be suitable to planned PDF/PS support (CMYK enabled output files). This feature will be also used by Fog-Svg library.

Other Plans

Because I added some exciting features (3x3 transform) I need to rewrite some things to match and coöperate with the new API. The first candidate for rewriting is curve flattening code. It's still mainly original code from AntiGrain and it has some disadvantages:

No clipping in the algorithm, must be clipped later.
There are several papers that describe better algorithms (BezierFlattening).
Curve flattening + stroke generator should be done ideally together.
Stroking to curves should be possible.

The next big thing is to refactor a Painter and to improve a multithreaded rasterizer (after I removed rasterizer-pool there is extra cost to create/destroy rasterizer per paint command).

Conclusion

Refactorization is good and I'm making it often, but the class naming schema breaks source/binary compatibility so it shouldn't be changed so often. I hope that I found the schema that will be used long time and that will be sufficient for all possible features which can be implemented later.

~~NOTE: These changes haven't been committed yet.~~

Analytic Rasterizer Improvements

2010-08-31T23:57:00.009+02:00

Introduction

This article covers possibilities to improve the analytic rasterizer implemented by AntiGrain (originally by freetype or libart). It's some time ago I posted a question in an antigrain mailing list, but it's probably very specific so nobody responded. It's all about compressing cell structures generated by the analytic rasterizer.

Explanation

Before I start I'd like to explain how antigrain rasterizer works. Please never cite this explanation, because it's not detailed and it can be crippled by my level of English.

Imagine that you need to paint a triangle. Triangle is basic primitive and for each rasterizer it's a minimum. These steps are needed to rasterize it using an analytic method:

Serialize the input coordinates (this is your call to fillTriangle() for example)
Clip incoming vertices
Iterate over edges and create cells
Sort cells
Sweep and composite each scanline

Bunch of cells are generated for each rasterized edge. The count of cells is relative to the length of the edge. Please read this article that covers the details.

For us is important that original cell structure in antigrain looks like this:

struct Cell
{
  int x;
  int y;
  int cover;
  int area;
};

This structure takes 16 bytes for x86/x64/Arm/... platforms. It's needed to sort generated cells by Y and then by X. Antigrain solves this problem using this technique:

Sort first by Y using histogram. This is fastest than qsort and it's about two loops.
Sort by X using bubble sort or qsort (if there are many cells).

You have choice to store pointers into sorted array or to copy generated cells into it. It seems that pointers are better in 32-bit mode and to copy whole structure without Y member in 64-bit one. No proof for this, just my testing before I rewrote the rasterizer.

Improvements

The first improvement I made is structure compression. At this time I have two variants of Cell structure - CellD and CellQ. CellD is 32-bit DWORD and CellQ is 64-bit QWORD. I compressed the structures by the following way:

DWORD (32-bit):

X - 13 bits (up to 8192 pixels in horizontal)
Cover - 10 bits
Area - 9 bits

QWORD (64-bit):

X - 32 bits
Cover - 16 bits
Area - 16 bits

There is stored 'area' member in the original antigrain cell which is calculated by 'cover * weight'. The result can take more than 16 bits so I'm storing the 'weight' instead, making the multiplication later in sweepScanline(). This trick allows to store one cell per 32-bit DWORD. This saves 75% space needed for a cell.

Careful reader should notice that there is no 'y' member in the cells used by Fog. The reason is that the Fog rasterizer don't need it, because cells are immediately stored in a space reserved for each scanline. I'm using single linked lists of small chunks of cells (14-15). The linked list is allocated using 64-byte alignment to not disturb when fetching cells by a multi-threaded painter.

Summary

Fog rasterizer is not sorting in Y direction, cells are already sorted.
Fog contains two cell structures - CellD and CellQ. CellD is expected to be used nearly by all paint calls.
Fog allocates cells per chunks. This means that if only two cells are needed for some scanline 14 or 15 cells are allocated.
The cell chunks overhead is about 7%. The cell compression rate is 74% for CellD and 47% for CellQ (including cell chunks overhead).

Conclusion

The Fog performance is better than before and memory overhead per rasterizer was reduced. This is only the beginning, I have another ideas how to improve multi-threaded rasterizer performance and to reduce memory overhead when using it. Currently Fog is using new rasterizer per each shape rendered using multi-threaded painter engine, the ideal solution will be to use one rasterizer per multi-threaded worker.

Another great improvement are rasterizers specialized for known shapes. I committed analytic rasterizer to fill rectangle (not axis aligned, sub-pixels are visible) some time ago. The performance of this rasterizer is really great, it's only about 50% slower than rasterizer used to fill axis-aligned rectangle, which is limited only by memory access speed.

How to say more? I'm making improvements and I hope that my work will be actively used some day. I read about two core Arm processor so maybe high-quality multi-threaded painting engine is future also for embedded devices.

Back in the School

2010-08-31T23:38:00.005+02:00

Back in the School

It sounds unbelievable, but I'm back in the education system. After one year of working (I'm still working, this is just bonus) I decided to go back to school and to study. The reason is very simple - Fog-Framework. Yeah I'm going to work on Fog at school time and I really wonder about progress I can do.

I have some plans with Fog, but my biggest effort is to complete Fog-Core and Fog-Graphics. These parts are important to me and are important to make library usable. I started some design and implementation notes in the wiki:

The first thing I'd like to do is to switch into JIT compilation. I started writing Fog with this idea and I think that it's time to demonstrate the power of JIT in 2d graphics. The AsmJit tool is getting better and better and with 1.0 version I feel that it's the time to use it.

The second thing I'd like to do is to redesign painter and complete all unfinished stuff:

Painter
Font support
Image and Path effects

It seems that it's just three points, but it will be hard work and I'm looking forward to it!

Fog - Performance of kiia rasterizer

2010-08-06T11:57:00.005+02:00

Introduction

My long-time TODO item was to implement KIIA rasterizer described here. If you download binaries pre-compiled for 32-bit Windows you should notice that the presented rasterizer is about 3 times faster than analytic rasterizer implemented in antigrain. The rasterizer uses classical approach - edges and AET (active edge table). Unlike the analytic rasterizer it needs scanlines to be rasterized from top-to-bottom direction (because of AET).

The biggest problem that stopped me many times from adding implementation into Fog was that there are too many source files, macros and I hadn't time to make basic working implementation. Last three days I was without internet so I tried to port code into Fog-Framework. I created Rasterizer_Kiia.cpp/.h files, implemented even-odd filler for simple clipping and started testing.

Performance

I must really say that performance of KIIA rasterizer was not as expected. I expected at least 50% performance gain, but in many tests the results are nearly equal to Fog analytic rasterizer and in about half tests the results are worse. Only area where KIIA rasterizer performance was better is polygon rasterization test.

Some FogBench results for comparison:

FogBench - Fog-Framework performance suite (version 0.3)

Surface  : 640x480
Quantity : 1000

Processor:  Intel(R) Pentium(R) M processor 1.70GHz
Features1: MMX=yes, MMXExt=yes, 3dNow=no, 3dNowExt=no, SSE=yes
Features2: SSE2=yes, SSE3=no, SSSE3=no
CPU count: 1

Test                    |Size      |KIIA-8x         |Analytic
------------------------+----------+----------------+---------------
FillRect-Argb-Copy      |256x256   |    40.817 [ms] |    40.881 [ms]
FillRect-Argb-Over      |256x256   |   198.905 [ms] |   197.983 [ms]
FillRect-Grad-Copy      |256x256   |   209.977 [ms] |   210.027 [ms]
FillRect-Grad-Over      |256x256   |   647.795 [ms] |   631.185 [ms]
FillRectSubPX-Argb-Copy |256x256   |   189.941 [ms] |   110.987 [ms]
FillRectSubPX-Argb-Over |256x256   |   345.159 [ms] |   268.764 [ms]
FillRectSubPX-Grad-Copy |256x256   |   418.936 [ms] |   336.705 [ms]
FillRectSubPX-Grad-Over |256x256   |   774.359 [ms] |   696.499 [ms]
FillRectAffine-Argb-Copy|256x256   |   206.611 [ms] |   190.822 [ms]
FillRectAffine-Argb-Over|256x256   |   360.999 [ms] |   342.187 [ms]
FillRectAffine-Grad-Copy|256x256   |   431.458 [ms] |   414.006 [ms]
FillRectAffine-Grad-Over|256x256   |   781.907 [ms] |   766.389 [ms]
FillRound-Argb-Copy     |256x256   |   178.653 [ms] |   100.603 [ms]
FillRound-Argb-Over     |256x256   |   328.033 [ms] |   255.203 [ms]
FillRound-Grad-Copy     |256x256   |   394.408 [ms] |   333.215 [ms]
FillRound-Grad-Over     |256x256   |   755.879 [ms] |   691.855 [ms]
FillPolygon-Argb-Copy   |256x256   |   156.355 [ms] |   230.961 [ms]
FillPolygon-Argb-Over   |256x256   |   195.185 [ms] |   268.732 [ms]
FillPolygon-Grad-Copy   |256x256   |   220.645 [ms] |   293.397 [ms]
FillPolygon-Grad-Over   |256x256   |   283.699 [ms] |   358.786 [ms]
Image-Copy              |256x256   |    83.364 [ms] |    82.404 [ms]
Image-Over              |256x256   |   249.658 [ms] |   249.129 [ms]
ImageAffine-Copy        |256x256   |  1838.421 [ms] |  1844.663 [ms]
ImageAffine-Over        |256x256   |  2037.941 [ms] |  2015.771 [ms]

Notes

You should notice that only polygon test is faster when using the KIIA rasterizer. The polygon test consists of rendering 10 vertex polygons. Here the overhead to create edges and AET is minimal. Now look at the round benchmark results. Round shape is always divided into poly-line segments before rendering. Here the KIIA rasterizer should outperform the analytic rasterizer, but it didn't. The reason is that the poly-line segments representing flattened path are very small and there are a lot of them.

The KIIA rasterizer is really better when generating polygon-only shapes. Bézier curves which are divided into several small poly-lines are not so efficient. The reason is that when using analytic rasterizer there is not so much difference between rasterizing a line or a bézier curve - the difference is only mathematics needed to divide a bézier curve into poly-line segments.

Conclusion

My efforts to implement other rasterizers into Fog-Framework are probably over. I'm sure that I can more optimize the analytic one (I really hope I can increase the performance about another 30%) and the pipeline can stay as is. Also I think that there could be a problem in Fog-Framework itself - the rasterization is two-pass process. It's needed to rasterize and sweep-scanlines - adding support for another rasterizer means that I need to sweep result into scanline container first. After you have scanline you can do pixel-level compositing.

So instead of providing more various quality rasterizers I'd like to optimize the current one. The output quality and performance of analytic rasterizer is excellent and optimizing some simple cases can outperform others.

FogScript - Scripting with AngelScript

2010-07-22T22:39:00.009+02:00

Introduction

In previous post I introduced some type-safe scripting languages. I picked one and tried to connect Fog-Graphics into it. If I succeed or failed is summarized in next paragraphs.

I started with angelscript, because it has interface to directly connect C/C++ functions with the scripting engine. To create bindings I wrote about 1500 lines in C++ without any other tool. The tooling is somewhat I don't like when talking about scripting languages, because some languages have really awful bindings API (Python is candidate here).

Fast introduction to AngelScript

When registering class with AngelScript you have three choices of class type:

Value type.
Reference type.
Reference type, garbage collected.

Value type is type always passed as a value (like integer), reference type is dynamically allocated object controlled by the addRef/release methods (increasing/decreasing reference count) and garbage collected type is similar, but you are telling the engine that circular-references can happen.

The most interesting is fact that your classes are controlled by references and garbage collector shouldn't run so often. This is because they are usually destroyed on end of their scope and there is nothing to collect.

The differences between value and reference types in AngelScript:

Value type - The memory for an object is allocated by scripting engine, maybe on the stack like in C++ code. You can assign constructor, copy constructor, destructor and assign operator. Like in C++ if you don't provide them then the value content will be just uninitialized. One big thing to note is that you can't convert value type to reference type!
Reference type - The memory for an object is allocated by you, scripting engine cares only about the pointer you return. You must provide two methods (addRef / release) to manage reference count of an object. If reference is decreased to zero you have to destroy it. Scripting engine will throw an exception if you try to access null object.

In Fog-Framework there are many types 'value' based - String, ByteArray, Stream, Image, and others are not references, but values (data internally shared by reference counts). In C++ it's without problem to work with these types, but when scripting many of these 'value' base types are mapped to 'reference' types. So Image is reference-based type in AngelScript. List of classes and their mappings is discussed in the Mapped classes section. There is advantage that all reference-based types uses internally implicit data sharing and cow offered by Fog. This means that you can create an image in the scripting environment and get the instance without data-copy back into your application. Everything is transparent and atomic (like all containers in Fog).

FogScript == Fog-Framework + AngelScript

I decided to call my experiment as 'FogScript'. File extension used by scripts is '.fs', but of course there is no problem to execute any string or any other file extension. Using files is just convenient way for me to test more scripts.

I created wrappers around AngelScript that will create AngelScript scripting engine and register Fog-Framework classes, there are some macros for registering types, classes and their methods, etc...

Mapped classes

All mapped classes to FogScript are without 'Fog' namespace. As a convenience I added a '@' symbol to each reference-based class type.

List of mapped classes:

Fog-Core
- ByteArray - value.
- Math - global functions.
- String - value, mapped to script string object.
- Stream@ - reference.
Fog-Graphics
- Argb - value.
- ArgbStop - value.
- DoubleMatrix - value.
- DoublePath@ - reference.
- DoublePoint - value.
- DoubleRect - value.
- DoubleSize - value.
- Font@ - reference.
- Image@ - reference.
- IntPoint - value.
- IntRect - value.
- IntSize - value.
- Painter@ - reference.
- Pattern@ - reference.
- Region@ - reference.

Security (Unfinished)

Since it's possible to create and work with many classes introduced by Fog-Framework, it's needed to add some security restrictions. When scripting a part of your application you probably don't want to allow the script to access the filesystem, network, etc...

I think that these security models will be enough for scripting purposes:

Sand-boxed - Script can access nothing, filesystem, network, ...
Restricted - Script has limited access to filesystem (list of directories to read, write, ...) and network.
Full - no limitation - any class available in Fog-Framework may be used.

Example

Ready to see FogScript in action? The example below demonstrates how to paint something and save it to file using FogScript:

// Create a linear gradient pattern for a given bounding box.
Pattern@ makePattern(DoubleRect bb)
{
  Pattern@ p = Pattern();

  p.type = PATTERN_LINEAR_GRADIENT;
  p.setPoints(DoublePoint(bb.x, bb.y), DoublePoint(bb.x, bb.x+bb.h));
  p.addStop(ArgbStop(0.0, 0xFF7F0000));
  p.addStop(ArgbStop(0.5, 0xFFFF0000));
  p.addStop(ArgbStop(1.0, 0xFFFFFF00));

  return p;
}

// Create path that contains simple wheel.
DoublePath@ makeWheel(int points, double outerSize, double innerSize)
{
  DoublePath path;

  for (int i = 0; i <= points; i++)
  {
    double val = 3.141 * 2.0 * (double(i) / double(points));

    double xx = sin(val);
    double yy = cos(val);

    double x0 = 160 + xx * innerSize;
    double y0 = 160 + yy * innerSize;

    double x1 = 160 + xx * outerSize;
    double y1 = 160 + yy * outerSize;

    if (i == 0)
      path.moveTo(x1, y1);
    else
      path.curveTo(x0, y0, x1, y1);
  }

  return path;
}

// Script entry-point.
void main()
{
  Image@ image = Image(320, 320, IMAGE_FORMAT_PRGB32);

  Painter@ p = Painter(image);
  p.setSource(Argb(0xFFFFFFFF));
  p.fillAll();

  DoublePath@ path = DoublePath();

  path.addPath(makeWheel(6, 100, 50));
  path.addPath(makeWheel(6, 60, 30));
  path.close();

  p.setSource(makePattern(path.boundingRect));
  p.fillPath(path);

  p.setLineWidth(1.5);
  p.setSource(Argb(0xFF000000));
  p.drawPath(path);

  p.end();

  image.writeToFile("test.png");
}

When running script using 'FogScript test.fs' it creates the test.png shown below:

Conclusion

FogScript is currently unfinished work. It's not project I want to publish at this time, but if there will be interest then I can commit it into Fog-SVN I'd like to see some feedback if this could be useful or not. The scripts look like the Fog-C++ code, but it's generally safe.

The differences to other scripting languages / environments are that FogScript is integrated with Fog-Framework and it's purpose is to use it through it. I also think that adding security restrictions to scripting environment (and maybe Fog itself) is good idea. Of course you can map your own classes which can break it, but this is something I can't preclude.

Type-safe scripting engines for C++

2010-07-18T02:56:00.003+02:00

Intoduction

Looking for type-safe scripting engine easy embeddable in your C++ project? I did some research in this area and this post is summarization. There are many dynamically typed scripting engines that may be easily integrated into C/C++ projects including EcmaScript style languages (several implementations available) and languages with different syntax like Python, Ruby or Lua. Today I'd like to introduce some non-mainstream languages that are quite underestimated.

Theory

Dynamically scripting languages are common, because the implementation is quite simple. Dynamic scripting language is usually only hash table, array and primitive types. There is no storage problem, because the data-length is normally platform pointer size (32-bit, 64-bit). There is no need for performance so this is usually enough. Binding to these languages are created through wrappers. Wrapper is a function that wraps your C/C++ function/member method into function that can be called by the scripting engine. There is also interface for registering classes - class consists of a name, constructor and destructor.

It's simple, yeah, but the price is ... Price for what? Performance!

I wrote that performance is usually not a problem when choosing scripting language, but de-facto it is. Look at the browser wars and impossible mission to improve javascript performance. There are large teams thats solving very complicated problems like static code-analysis, run-time code tracing, jit-compilation / patching, etc... Everything I'm talking about can be found in V8 scripting engine and SpiderMonkey.

Why I'm talking about this? Simply because when performance matters then there is no simple implementation anymore! Compiled V8 scripting engine is about 1MB (binary) while LUA is for example tens of KB only. Source code complexity is in similar ratio. I'm talking about the engine itself, not standard/ support libraries which can be written in C/C++ or using scripting language itself (for example Python contains standard library where the most of code is in Python itself).

I'd like to summize static vs. dynamic typing in a following table

	Type-safe scripting language:	Dynamic scripting language:
Type safety:	Strong, errors are checked at compile-time.	None, errors are checked by the run-time.
Performance:	Execution speed can be improved by using jit-compilation to make it close to C/C++.	Jit-compilation can never help to make the language as fast as C, but helps a lot.
Memory footprint:	Smaller, maybe bigger than C/C++, but should be close.	Larger. Each variable contains type-id which must be stored with it. There are several workarounds, but it helps only for integer types and strings (used by all major ecmascript engines).
Extensibility:	Depends to language implementation, the initial list of features is usually small. Multiple inheritance is problem (not available even in enterprise languages like Java/C#). Features like anonymous delegates and dynamic method invokation are not easy to implement. My experiences are that single-inheritance model is enough for all kind of projects.	Strong! This is area where dynamically typed languages win.
Portability:	Calling user functions without wrappers need portability layers for each platform. Using wrappers is portable.	All user C/C++ functions are wrapped through functions which can be called by the scripting engine (defined calling convention and function prototype).
Initial development effort:	Large - language is not a hash-table, each new feature needs carefully designed virtual machine. Problem when compiling+running against different versions of modules can be hard to solve.	Small - look at LUA, it's simple and small.

Theory Summary

Let's summarize the differences. Type-safe languages should be generally faster with smaller memory footprint while dynamically typed languages should be slower, but more extensible. Usually the performance not matters when writing scripts in case that you making the bridge between application written in C/C++ and scriptable environment. But is really truth that performance isn't important? Maybe, problem solved? No!

It's a matter of time until you write huge script code which needs architectural changes or refactorization, but refactorizing dynamically typed code without tools (and tell me which IDE can correctly refactor LUA/Python for example) could be initiation of troubles. In this area type-safe languages simply wins - you can refactor code, you can change architecture, but you can't compile wrong code which references non-existing classes/methods. This is addition to the performance reasons I talked about in the Introduction section.

Type-safe Scripting Languages

AngelScript

The AngelScript scripting language is type-safe scripting language similar to C/C++. It is written in C++ and contains some key features:

Binding C/C++ functions/class methods without wrappers - scripting engine can call C/C++ function directly, several calling conventions are supported.
Scripting engine can work with UTF-8 and UTF-16 strings without recompilation, you must register your own string type (this is really useful).
There is no standard library, you must implement the functionality you need (good for embedding / sandboxing).
Project is maintained, there are new version each 3-6 months (mainly bugfixes).
Good license (MIT).

Disadvantages:

No inheritance for C/C++ classes. This makes the scripting engine totally unuseful for GUI programming. It's planned for a long time, but not implemented. Single-inheritance model could be enough.
No jit-compiler. There is simple architecture for plugging some, but it's so simple to be useful and totally non-connected with the rest of the engine.
Only text exceptions, no try-catch blocks in the code. Exception is something that shouldn't happen and it's handled by the your C/C++ code.
Some useful things like including other scripts or metadata are handled by preprocessing original scripts. I think this should be part of core-api.

Links:

JewelScript

JewelScript is similar to AngelScript. The syntax is similar to C/C++, but there are some differences when defining functions and methods (class member function). Also the script engine is written in pure C.

Advantages:

The language seems to be very complete and useful. New version (1.0) is really different to previous ones and features are amazing (JewelScript feature overview).
Exposing native inheritance into scripting environment is possible.
Ability to use dynamic typing.
Anonymous delegates implemented in core language.
Project is maintained, but it's not so used as AngelScript. I found small message from the author (called Jewe). He would like to increase popularity of the scripting engine.
Class based exception handling.
Good license (zlib/libpng).

Disadvantages:

Unable to call native function/class method directly, need wrappers.
No jit-compiler.
String type can't be customized (I really like the idea from AngelScript).
Some built-in classes start with lowercase letter (scripting languages usually use capitalized class names and camelCase for function/method names).
There is standard library.

Links:

Home
Forum (Outdated, Moved)
Documentation

NullC

NullC is quite new project. It's type-safe scripting engine and language similar to C/C++, there are only few differences. NullC is conceptually amazing project that contains jit-compiler for x86 platform and small IDE where simple scripts can be tested (including work with raster graphics and timers). Project is in the progress and it's not finished yet. When using JIT compiled code the code-execution is about 20 times faster than byte-code interpreter.

Personally I think that when finished this project can compete with many scripting languages.

Advantages:

Language is complete and contains advanced features (for example auto type based on r-value).
Ability to use jit-compiler (32-bit x86 only at this time).
Exposing native inheritance into scripting environment is possible.
Author is active, new commits each week.
Good license (MIT).

Disadvantages:

Unable to call native function/class method directly, need wrappers.
Jit compiler is only for x86, but architectur is defined (matter of time).
No documentation at this time.
New project, needs some time to evolve.
Comes with standard library and some windows / gui classes. It's optional, but currently it's everything in one source-tree. I hope that this will be split from the project into additions.

Links:

Home

Conclusion

Too early to write an objective conclusion. I think that each scripting language mentioned here have use-cases. Each have also some marginal disadvantages - AngelScript and native-class inheritance, JewelScript and wrappers/string customization and NullC is too young project.

I tried to connect Fog-Framework with AngelScript and it was quite easy. The only disadvantage that is limiting me is the no-inheritance model for native classes. I'd like to try JewelScript this week so I can compare these two engines.

If you are looking for type-safe scripting engine, you should try all mentioned here and simply pick the best one.

Using graphviz to visualize expression

2010-07-14T03:12:00.010+02:00

Introduction

I hacked MathPresso to generate output in a 'dot' language today. The 'dot' is part of a graphviz package. It's a language and a tool (can be run from command line for example) which can generate graphics representation of the 'dot' input.

Mathpresso is a mathematical expression parser, evaluator and jit-compiler. Visual representation of an expression is excellent for debugging purposes. It reveals how an expression was parsed and possibilities how an expression can be improved. Adding support for generating 'dot' output was 30-minutes action.

Expression Representation

Imagine the following expression:

(x + y + z*2 + (x*z + z*1.5))

When using MathPresso the expression is parsed to an abstract-syntax-tree (AST). The AST is a hierarchic structure that can be manipulated and transformed. The MathPresso is currently only able to merge constants - for example expression '1+1' can be merged simply to '2'. Jit compilation is transformation of AST into a machine-code. Generating the 'dot' output is similar, but that the AST is transformed into the 'dot' language.

The 'dot' representation of the expression:

digraph G {
  node [shape=record];
  N_14 [label="<L>|<F0>+|<R>"];
  N_14:L -> N_6:F0;
  N_14:R -> N_13:F0;
  N_6 [label="<L>|<F0>+|<R>"];
  N_6:L -> N_2:F0;
  N_6:R -> N_5:F0;
  N_2 [label="<L>|<F0>+|<R>"];
  N_2:L -> N_0:F0;
  N_2:R -> N_1:F0;
  N_0 [label="<F0>x"];
  N_1 [label="<F0>y"];
  N_5 [label="<L>|<F0>*|<R>"];
  N_5:L -> N_3:F0;
  N_5:R -> N_4:F0;
  N_3 [label="<F0>z"];
  N_4 [label="<F0>2.000000"];
  N_13 [label="<L>|<F0>+|<R>"];
  N_13:L -> N_9:F0;
  N_13:R -> N_12:F0;
  N_9 [label="<L>|<F0>*|<R>"];
  N_9:L -> N_7:F0;
  N_9:R -> N_8:F0;
  N_7 [label="<F0>x"];
  N_8 [label="<F0>z"];
  N_12 [label="<L>|<F0>*|<R>"];
  N_12:L -> N_10:F0;
  N_12:R -> N_11:F0;
  N_10 [label="<F0>z"];
  N_11 [label="<F0>1.500000"];
}

Executing dot -T png -o ${FILE}.png ${FILE}.dot command will convert the .dot file into a .png:

Conclusion

Graphviz is really strong tool. The 'dot' language syntax is quite simple and generating dot file from application is very easy (I did it using simple counter for IDs and string builder).

AsmJit - Function calling finally supported

2010-07-12T13:03:00.010+02:00

Introduction

I spend some time by adding support for calling functions through AsmJit::Compiler yesterday. The implementation is initial, but my first tests are showing that it's working. The biggest effort was to make the implementation correct and optimized.

It was needed to address these problems:

Save all preserved registers (variables).
Move register parameters into correct location (spill+load or exchange).
Reserve stack needed to call a function. I'm using convention from 64-bit development, allocating stack for all functions in EFunction prolog/epilog.
Make implementation smart and generic - allowing to write custom calling conventions.

Example

I wrote simple test-case which was tested under 32-bit Windows and 64-bit Linux. Both works very well.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <AsmJit/Compiler.h>
#include <AsmJit/Logger.h>
#include <AsmJit/MemoryManager.h>

// Type of generated function.
typedef int (*MyFn)(int, int, int);

// Function that is called inside the generated one.
static int calledFn(int a, int b, int c) { return (a + b) * c; }

int main(int argc, char* argv[])
{
  using namespace AsmJit;

  Compiler c;

  // Log compiler output.
  FileLogger logger(stderr);
  c.setLogger(&logger);

  c.newFunction(CALL_CONV_DEFAULT, FunctionBuilder3<int, int, int, int>());
  GPVar v0(c.argGP(0));
  GPVar v1(c.argGP(1));
  GPVar v2(c.argGP(2));

  // Just do something;)
  c.shl(v0, imm(1));
  c.shl(v1, imm(1));
  c.shl(v2, imm(1));

  // Call a function.
  GPVar address(c.newGP());
  c.mov(address, imm((sysint_t)(void*)calledFn));

  ECall* ctx = c.call(address);
  ctx->setPrototype(CALL_CONV_DEFAULT, FunctionBuilder3<int, int, int, int>());
  ctx->setArgument(0, v2);
  ctx->setArgument(1, v1);
  ctx->setArgument(2, v0);
  ctx->setReturn(v0);

  c.ret(v0);
  c.endFunction();

  // Make the function.
  MyFn fn = function_cast(c.make());

  printf("Result %u (expected 36)\n", fn(3, 2, 1));

  // Free the generated function if it's not needed anymore.
  MemoryManager::getGlobal()->free((void*)fn);

  return 0;
}

The function call is generated and controlled using ECall emittable. You get a context by calling Compiler::call(const Operand& dst) which can be used to assign function calling convention, prototype, arguments and return value. Function builder is shared between EFunction (creating a function) and ECall (calling a function).

Generated Assembler

32-bit Windows-XP:

; Prolog
push ebp
mov ebp, esp
push ebx
push esi
sub esp, 16
; Body
mov ecx, [ebp + 8]              ; Alloc arg_0
shl ecx, 1
mov edx, [ebp + 12]             ; Alloc arg_1
shl edx, 1
mov ebx, [ebp + 16]             ; Alloc arg_2
shl ebx, 1
mov esi, 4199552
; Function Call
mov [esp], ebx
mov [esp + 4], edx
mov [esp + 8], ecx
call esi
; Epilog
add esp, 16
pop esi
pop ebx
mov esp, ebp
pop ebp
ret
*** COMPILER SUCCESS (wrote 50 bytes).

64-bit Gentoo-Linux:

; Prolog
push rbp
mov rbp, rsp
; Body
shl edi, 1
shl esi, 1
shl edx, 1
mov rcx, 4199268
; Function Call
xchg rdi, edx
call rcx
; Epilog
mov rsp, rbp
pop rbp
ret
*** COMPILER SUCCESS (wrote 26 bytes).

Conclusion

I think that initial implementation is very good and helpful for AsmJit users. Calling functions through AsmJit is long-time demanded feature which was finally implemented!

Only the thing I'm not sure is the API, I think that FunctionPrototype (AsmJit class) and function builder should contain also return value, currently only ECall contains it. This is main reason why there is no beta release yet, API will be probably changed.

Solved: First argument for function builder is function return value.

Fog-Graphics and JIT compilation

2010-07-11T20:42:00.005+02:00

Introduction

About one and half-year ago I wrote tool called AsmJit and released it to the public. It took me about one week to write the initial implementation which was completely rewritten two times. Currently I'm working on AsmJit-1.0-beta that will be the first Fog-Framework dependency. The reason is very simple - I want to remove all templates from rendering backend and replace them with BlitJit. BlitJit is experimental project which will be merged into Fog-Framework.

All operators except CLEAR, SRC and SRC_OVER will be removed from run-time. These tree will remain, because these are the most common ones and compiling them using JIT compiler over and over is not good idea for application startup. All others will be JIT compiled.

Architecture

The Fog-Graphics pixel renderer architecture can be shown in list below:

Source generator/fetcher (Solid, Gradient or Texture).
Destination fetcher.
Compositor (With mask, Without mask).
Destination store.

If source color is solid these steps are all merged into single function. If source is gradient or texture then pipeline is split to fetch source and then do the rest.

But if you understand mathematics then you can found one issue, to make this possible (merging the pipeline) you have to write many functions, because Fog-Framework supports 5 pixel formats and about 20 compositing operator. Also the gradient and texture fetchers are optimized and there are specialized versions (nearest neighbour filtering, bilinear filtering, downscale, upscale, vertical gradient, horizontal gradient and many others...). This simply means you it's not possible to merge everything into single monstrous function.

Currently the Fog-Framework is about 1.5MB library when compiled by GCC. I think that for simple library it's a lot, but when you try to remove all compositing operators, the size is highly decreased! So the Fog is currently bloated by code that will run 0.001% times (SVG compositing operators are cool, but the most used operator is SRC_OVER, forever).

The Initial Idea Is Back!

When the Fog-Framework was in designing state, I planned to include JIT compiler that would be used to generate/optimize inner loops for pixel manipulation. Because I hadn't time to implement JIT compiler I used templates, but I'm not satisfied with the performance and I'm now thinking about JIT. This idea is also connected with shaders - JIT compiler will be used by Fog-Framework, it's only matter of time how many inner loops will be optimized.

I'd like to summarize what everything will be possible with JIT compiler:

Introduce more pixel formats, planned are ARGB16_1555, RGB16_555, RGB16_565, RGB24, RGB48 and ARGB64/PRGB64.
Introduce more compositing operators, the rest of SVG is needed, custom operators would be possible.
Merge all steps of a pipeline into one single function, maximizing the performance.
About 50% smaller library, because redundant code will be removed.

AsmJit is the future!

Developing with CMake under Windows

2010-07-07T14:28:00.006+02:00

Introduction

This post is not related to the Fog-Framework, but I found always hard to work with open-source libraries under Windows OS. I'm talking about C/C++ development. If you want to use some open-source library, you have to build it yourself and install to some location where it can be found by your IDE/Compiler/Build-Tools.

Fog-Framework is nearly zero-dependent library so I never go into troubles when configuring, building and running it. But yesterday I worked a bit on the AsmJit and Mathpresso and I found that the development is not so easy, notice that I'm talking about only two libraries and one dependency!

CMake

The first tool I used for cross-platform development is CMake. I think that the CMake syntax is awful (I blogged about two years ago about an idea of creating new cross-platform build tool based on V8 for project files in Czech, but this post is not about syntax). Although the syntax is awful and I really dislike it, the CMake is probably the best tool for cross-platform development I found.

My Solution

So here my solution I'm using to develop libraries / applications under Windows:

Create directory in the filesystem that will be used for installed libraries and binaries. Because I'm confortable with Linux and I'm using it for development I found the C:\Opt directory very useful (naming and it's also short).
Create basic directory structure in your folder, you need 'bin', 'lib' and 'include' subdirectories. If you created directory C:\Opt then your file-system structure should look like this:
```
C:\Opt\bin
C:\Opt\lib
C:\Opt\include
```
Now setup your PATH environment variable to C:\Opt\bin and C:\Opt\lib so Windows can find your libraries and binaries. If you never worked with environment variables before, go to START -> Settings -> Control Panel -> System -> Details -> Environment Variables -> PATH (the dialog to add the path is really small and can't be resized, urggggh)
Now add environment variable called CMAKE_LIBRARY_PATH and set it to C:\Opt. If you don't want to pollute your environment variables too much, you can call set CMAKE_LIBRARY_PATH=C:\Opt from command line to set it for current session. You could also set CMAKE_INCLUDE_PATH to C:\Opt\include, but I think that this is not needed.
Now close all explorers and file managers, because new environment variable will be visible only for applications run after the change. So if you have for example CMD running, close it.
Now CMake should find and use all compiled libraries added to C:\Opt. You can install all libraries to this location by running cmake script with CMAKE_INSTALL_PREFIX=C:\Opt.

Conclusion

I hope that there is better way how to do this. Personally I'm a little bit lazy and I really dislike to setup environment variables before each script invocation so I added all to environment variables.

Fog-SL - Fog and shaders

2010-07-03T21:07:00.005+02:00

Introduction

I know, no posts for a long time, but I can't stop a time! I'd like to present some news about Fog-Framework today. It's few weeks that Mike suggested very simple mechanism to enable writing extensions for Fog-Framework painter. The idea is that compositing operators are not designed to solve everything and when creating graphics you can simply get to situation that no operator can do what you need.

There is one very simple solution to this problem - assigning functions where you can implement the functionality. This approach has advantage that it's nearly unlimited use-case, but it has also some disadvantages. The main disadvantage is that the function must match predefined pixel format(s) and must be written in C/C++. This is problem, because there is no way how to write shader in C/C++ that can be executed by a GPU. I'd like to add OpenGP/D3D backands early so I don't want to close that door.

Shaders

Yeah, the heading is correct! When talking with Mike I suggested that we can solve everything using some shader language. Currently we agreed that the language should be compatible to an OpenGL, so we choose subset of GLSL as the base for Fog shading language (FOG-SL, sounds good?;), but at this time I don't know if we end purely with this or we extend this language much more. The idea is simple, graphics hardware is powerful and some calculations (matrix multiplication) is really fast compared to CPU. This means that FOG-SL will be mainly designed to work with pixels (not vertex shaders at this time) and to generate source (pattern fetchers). I don't know if something like vertex shaders will be added into it.

AsmJit

The key part of any shading language is tokenizer, parser, optimizer and code-generator (very simplified). The AsmJit was choosen as a tool to generate machine code that can be run by a processor. The reason is simple - in computer graphics everything is run through inner-loops. Painting 100x100 rectangle means 10.000 pixel operations in total - 100 inner loops and 100 outer loops. The most optimized loop must be the inner one (SPAN structures are used for these, see FOG raster engine for mor edetails).

Using AsmJit means also one big thing - First dependency that is not part of standard packages of target operating system. This is not problem for me, but may be for others. I'd like to highlight one thing here - Fog is currently very big library, because it contains many optimized compositing functions that were designed using templates. Each new compositing function or pixel-format means bigger binary size of Fog-Framework. Introducing shaders and JIT compilation I can shrink library size about 50% - just try to compile Fog using only SRC, SRC_OVER and CLEAR operators.

Advantages / Disadvantages

FOG-SL advantages:

One shader code is compatible with all pixel formats (compiler can premultiply / demultiply pixels on-the-fly). This means that in future the 16-bit and 32-bit pixel formats can be added without breaking old code. We can also introduce high-quality flag to run shader using floating-point math.
Shaders should be fast, because shader code is compiled into assembler and run directly by the CPU. The inner loops are inlined so simple shaders can run in hundreds frames per second (like code compiled by C++ compiler). JIT compilation also means that we can compile many compositing / shading functions on-the-fly so they don't have to be part of compiled Fog library
Shaders should support subset of features available by GLSL so they would run on GPU in the future.

FOG-SL disadvantages

Portability - this is only disadvantage known to me. Shader requires to write code-generator for each supported processor which is very time-consuming.

Thanks

Currently only Mike is working on shader branch, but I'd like to help with it when I get some free time. If you are integested about shaders and implementation in fog (FOG-SL) read Fog-dev mailing list.

Visual Studio - MOVD impossible

2010-05-12T02:50:00.004+02:00

Introduction

Today I looked at disassembly, the assembler code generated by Visual Studio 2005 and I'm quite frustrated how bad the code is. Currently the Visual Studio C++ Compiler can generate one of the most compact code, but SSE2 code generated using SSE2 intrinsics is really not good as expected.

The problem is that there is not direct intrinsic to generate:

MOVD [mem], xmm
MOVD xmm, [mem]

But this instruction exists and it's very common to use it to load 4 bytes into a XMM register clearing all higher DWORDs. The code generated by Visual Studio looks like this:

  MOV ecx, [eax]
  MOVD xmm, ecx
Instead of:
  MOVD xmm, [eax]

This is very inefficient code. I have two problems with it - it uses general purpose register that can be used by other variable and it expands into two instructions that can't execute in parallel.

Fog - Rethinking span structures (internal)

2010-04-24T04:38:00.011+02:00

Introduction

My recent work on Fog-Graphics is about anti-aliased clipping. The work is slowly getting done and I'd like to share some knowledge about the refactorized span structures.

Span, what?

Span is very small structure (about 16 bytes) that holds information about:

X position - in code / literature it's usually X or X1 member.
Length - in code / literature it's usually Length or X2 member.
Mask - mask can be const or variant.
Additional data - depends to library, engine, etc...

Fog-Graphics span structure currently contains next member - It's pointer to the next span or NULL if the span is last. You can see this member probably only in Fog, but I have strong reasons to include this member instead of using span[] arrays (statically or dynamically allocated). These reasons are:

Spans can be chained and implementation details (how chaining is done) is hidden to a consumer. Consumer is simply function or set of functions that use spans to do something, but given spans are not modified (In C/C++ the const keyword is used to mark data as const).
Customized memory management. When designing the API it took me a lot of time and thinking to make it this way. The reasons are that it's possible to combine spans used for clipping and spans used to sweep rasterized scanline. Currently rasterizer is using different memory management to sweep scanlines than clipper.
Possibility to create another class based on span that holds additional information.

The structure

So what span looks like? Look at code section below:

struct SpanA8
{
  // ... Getters / Setters omitted ...

  int x1;
  int x2;
  uint8_t* mask;
  SpanA8* next;
};

The position and length is encoded using x1 and x2 members. As everything in Fog and other graphics libraries, x1 is begin position that is inclusive, but x2 is end position that is excluded from the span. This is standard in computer graphics I will never break. The length can be simply calculated by x2 - x1.

Another interesting member is a mask. Here I'd like to talk more about it, because I created schema that allows me to encode constant mask in this pointer without referencing other memory location. If the pointer is smaller than 256 (0xFF) then the value means const mask value (In Fog this is called CMask). All other values are pointers to memory location containing the mask sequence. Because this can be error-prone and annoying to work with, I created getters and setters, so you never access members directly. There are assertions and incorrectly used span in debug mode will kill your application.

And the last member is next pointer. I don't know how much to say about it, it's simple single-linked list solution.

Differences to AntiGrain

AntiGrain rendering engine contains spans too, but encoded using different schema:

struct SpanAgg
{
  int x;
  int len;
  uint8_t* mask;
};

You can see that it's different to Fog span, and there are some quirks too:

The x member is same as x1 member.
The len member is length of span, but it can be negative! Negative length is encoding for constant mask. So to get length of span you need to check if it's negative first.
The mask member always points to memory location. If span is const mask then there is only one record at mask[0], if span is variant mask is sequence as in Fog.
There is no something like next. Spans in AntiGrain are continuous so you need to know how many spans you have and then you are simply using span++ to get another one.

You can see that there are design and algorithmic differences. I think that my way performs better in Fog, because I'm not using templates for core classes and I need to use different memory allocators in specific sections. However, the scanline sweep mechanism need to do some extra work to set the next member, but this is nothing compared to rasterization pipeline (I didn't notice slowdown or speed-up, it's simply different way that is better in Fog).

Memory Management

I talked about memory management, but I didn't summarize the goals and reasons why I need it.

The rasterizer span allocator produces very short-life data used only once by a blitter. It's very inefficient to alloc/free (using dynamic memory allocator) the storage for each blit or for each scanline fetch. Instead there is a scanline container that is used together with rasterizer. The purpose of the scanline container is to allocate memory once and reuse it for the life of the container itself. Each multi-threaded painter context contains per thread scanline container.

The oppossite is span allocator used by clipper. The clipper needs ability to allocate spans which life-time could be more than one graphics command. The clipper also needs to modify allocated spans (when doing intersections) with other clip requests (for example you can clip to circle and then to other circle again).

Conclusion

This is all tonight. I hope that the new span architecture will increase code readability and robustness. I'm also planning to simplify and improve blitter performance when using patterns and rendering anti-aliased shapes.

Using Fog with SDL

2010-04-15T04:09:00.011+02:00

Introduction

SDL is very popular library for the game development that allows direct access to the screen content. SDL is low-level library that is able to prepare window, allocate double-buffer, surfaces, create timers and much more. When it comes to painting, it contains only few low-level functions to blit one surface into another or to fill a rectangle with a single color.

If you need to do more, you need to use additional libraries (SDL_image, SDL_gfx, SDL_ttf...) that were designed to solve exactly one problem (load or write images, draw primitives, draw text, etc...). The biggest problem is if you need more than only simple raster graphics or text rendering. Another problem can be many dependencies, for example SDL_ttf depends to freetype which depends to zlib, SDL_image needs libpng (which needs zlib) and libjpeg (if you want to use PNG or JPEGs), and so on...

Fog-Framework tries to use operating-system libraries instead (you don't need FreeType under Windows, nor libpng, etc...), and one unified API. The Fog-G2d library is designed to be extensible, so you can use any other library that can provide you pixels buffer (and I didn't see library that not allows it). Only the requirement is that the pixel format of the buffer is compatible with the Fog (but Fog-G2d is designed to work with the most hardware pixel formats, so this really shouldn't be an issue).

Embedding

Lets talk about the embedding. Fog-Framework contains own windowing system and UI components, but you don't need to use them, you can use only Fog-G2d library without complications. Lets describe two ways for using other graphics libraries with Fog:

Adopting other data into Fog-Framework containers - Described in this article, see Fog::Image::adopt() and Fog::Painter::begin() methods for more. The Fog::ImageBits structure is always used to do the connection.
Adopting Fog owned data into other libraries - Very easy if other library allows to use custom pointers. It's possible to use for example Fog::Image in Cairo or GdiPlus, and vice-versa.

This article covers adopting other data (pixel buffers) into the Fog-Framework.

The Code

Here is working, heavily commented application that will setup SDL and use Fog::Painter and other classes / functions to paint into the buffer managed by the SDL library. The Fog::ImageBits structure was used to pass raw-data buffer into Fog::Painter.

// ============================================================================
// [Include Section]
// ============================================================================

#include <Fog/Core.h>
#include <Fog/G2d.h>

#include <SDL.h>

// ============================================================================
// [Tools]
// ============================================================================

static Fog::TransformF createRotationMatrix(Fog::PointF center, float rotation)
{
  Fog::TransformF m;
  
  m.translate(-center, Fog::MATRIX_APPEND);
  m.rotate(rotation, Fog::MATRIX_APPEND);
  m.translate(center, Fog::MATRIX_APPEND);

  return m;
}

// ============================================================================
// [SdlApplication]
// ============================================================================

// SdlApplication is nothing more than thin wrapper to SDL library. You need
// just to instantiate it and call run() to enter the SDL event loop.
struct SdlApplication
{
  SdlApplication();
  ~SdlApplication();

  // Application state (just convenience instead of 0, 1, ...).
  enum APP_STATE
  {
    APP_OK = 0,
    APP_FAILED = 1
  };

  // Initialize application, called by run(), don't call manually.
  int init(int width, int height);

  // Destroy application, called by destructor, don't call manually.
  void destroy();

  // Run application, called by your code.
  int run(int width, int height);

  // Called to process SDL event.
  void onEvent(SDL_Event* ev);

  // Called on timer event.
  static Uint32 _onTimerCb(Uint32 interval, void* param);
  void onTimer();

  // Called to render content into buffer.
  void onRender();

  // Called to render content using Fog::Painter, called by onRender().
  void onPaint(Fog::Painter& p);

  // SDL screen surface, the surface we will paint to.
  SDL_Surface* _screen;

  // SDL timer.
  SDL_TimerID _timer;

  // Delay between frames.
  int _interval;

  // Some stuff we work with.
  double _rotate;

  // Whether the application is in event loop.
  bool _running;
};

SdlApplication::SdlApplication() :
  _screen(NULL),
  _timer(0),
  _interval(25),
  _rotate(0.0),
  _running(false)
{
}

SdlApplication::~SdlApplication()
{
  destroy();
}

int SdlApplication::init(int width, int height)
{
  // Initialize the SDL library.
  if (SDL_Init(SDL_INIT_VIDEO | SDL_INIT_TIMER) < 0)
  {
    fprintf(stderr, "SDL_Init() failed: %s\n", SDL_GetError());
    return APP_FAILED;
  }

  // Create main surface.
  if ((_screen = SDL_SetVideoMode(width, height, 32, SDL_HWSURFACE | SDL_DOUBLEBUF)) == NULL)
  {
    fprintf(stderr, "SDL_SetVideoMode() failed: %s\n", SDL_GetError());
    return APP_FAILED;
  }

  // Create timer
  _timer = SDL_AddTimer(_interval, SdlApplication::_onTimerCb, reinterpret_cast<void*>(this));

  // Success.
  return APP_OK;
}

void SdlApplication::destroy()
{
  if (_screen)
  {
    SDL_RemoveTimer(_timer);
    SDL_FreeSurface(_screen);
    SDL_Quit();

    _screen = NULL;
  }
}

int SdlApplication::run(int width, int height)
{
  // Initialize application.
  int state = init(width, height);
  if (state != APP_OK) return state;

  // Enter to the SDL event loop.
  SDL_Event ev;
  _running = true;

  while (SDL_WaitEvent(&ev))
  {
    onEvent(&ev);
    if (_running == false) break;
  }

  return APP_OK;
}

void SdlApplication::onEvent(SDL_Event* ev)
{
  switch (ev->type)
  {
    case SDL_QUIT:
      _running = false;
      break;

    case SDL_USEREVENT:
      // This is our timer event.
      onTimer();
      break;
  }
}

Uint32 SdlApplication::_onTimerCb(Uint32 interval, void* param)
{
  // On timer callback is called from different thread, we just send custom event
  // back to the main one.
  SdlApplication* app = reinterpret_cast<SdlApplication*>(param);

  SDL_UserEvent e;
  memset(&e, 0, sizeof(e));
  e.type = SDL_USEREVENT;
  SDL_PushEvent(reinterpret_cast<SDL_Event*>(&e));

  return interval;
}

void SdlApplication::onTimer()
{
  // Do some stuff...
  _rotate += 0.01;

  // Render new frame.
  onRender();
}

void SdlApplication::onRender()
{
  // Lock surface pixels.
  SDL_LockSurface(_screen);

  // Create Fog::Painter instance mapped to the SDL surface data.
  Fog::Painter p;

  // Setup image buffer for painter.
  Fog::ImageBits buf;

  buf.setRaw(reinterpret_cast<uint8_t*>(_screen->pixels),
    Fog::SizeI(_screen->w, _screen->h),
    Fog::IMAGE_FORMAT_XRGB32, 
    _screen->pitch);

  // Call our paint handler.
  if (p.begin(buf) == Fog::ERR_OK) onPaint(p);

  // Never forget to call p.end(). Painting can be asynchronous and
  // SDL_UnlockSurface() can invalidate the surface->pixels pointer.
  p.end();

  // Unlock surface pixels.
  SDL_UnlockSurface(_screen);

  // Flip buffer.
  SDL_Flip(_screen);
}

void SdlApplication::onPaint(Fog::Painter& p)
{
  // Just use the Fog-Framework ;-)

  // Create some variable we will work with.
  float w = float(_screen->w);
  float h = float(_screen->h);

  float roundw = 100.0f;
  float roundh = 100.0f;

  Fog::PointF cp(w / 2.0f, h / 2.0f);

  // Clear the entire screen.
  p.setSource(Fog::Argb(0xFF000000));
  p.fillAll();

  p.save();

  // Rotate across the screen center point.
  p.transform(createRotationMatrix(cp, _rotate));

  // And draw something...
  Fog::LinearGradientF gradient;

  gradient.setPoints(
    Fog::DoublePoint(cp.x - roundw / 2.0f, cp.y - roundh / 2.0f),
    Fog::DoublePoint(cp.x + roundw / 2.0f, cp.y + roundh / 2.0f));
  gradient.addStop(Fog::ArgbStop(0.0f, Fog::Argb32(0xFFFFFFFF)));
  gradient.addStop(Fog::ArgbStop(0.5f, Fog::Argb32(0xFFFFFF00)));
  gradient.addStop(Fog::ArgbStop(1.0f, Fog::Argb32(0xFFFF0000)));

  p.setSource(pattern);
  p.fillRound(Fog::RoundF(
    Fog::RectF(cp.x - roundw / 2.0f, cp.y - roundh / 2.0f, roundw, roundh),
    Fog::PointF(20.0f, 20.0f))
  );

  p.restore();
}

// ============================================================================
// [Entry-Point]
// ============================================================================

// SDL may redeclare main to something else, cut it.
#undef main

int main(int argc, char* argv[])
{
  SdlApplication app;
  return app.run(640, 480);
}

Conclusion

Fog-Framework isn't the only library you can use with SDL. There are many libraries that can do the job, but Fog-Framework is single library that covers various problems without extra dependencies. Another reason to use Fog is that it's one of the fastest open-source libraries available, so give it a try;-)

The presented example should work and will be updated to work with current Fog-trunk.

Using the MMX extensions without -msse (GCC)

2010-04-12T14:51:00.005+02:00

Introduction

Yesterday I ported the Fog-Framework to the MinGW. The biggest problem was with porting current pure MMX-EXT code to GCC without using a -msse parameter (this means you can't include xmmintrin.h).

Problem is that if you not enable SSE then you can't use MMX extensions in the code. Fog-Framework contains MMX, MMX+SSE, MMX+3dNow and SSE2 stack so I really needed to take advantage of one intrinsic in the MMX+3dNow code - _mm_movemask_pi8() (PMOVMSKB in assembler).

Solution

I created new IntrinMMXExt.h header file that is included only if SSE is not used. This header currently defines only the missing function I needed, but it can be extended in the future. The function is here, it's written using GCC assembly (GAS) and it should fit into your code without any changes:

static inline int _mm_movemask_pi8(__m64 a)
{
  int result;
  __asm__("pmovmskb %1, %0\n\t" : "=r"(result) : "y"(a));
  return result;
}

The most interesting part of code is :"y"(a) that tells GCC that a must be in MMX register. If you want to use XMM register then it will be "x". I never expected that it will be so easy to write such function, enjoy:)

Letters explanation used in asm block

"abcd" - AX, BX, CX or DX register.
"q" - AX, BX, CX or DX register, low-byte when using 8-bit register (AL, BL, CL, DL).
"Q" - AX, BX, CX or DX register, high-byte when using 8-bit register (AH, BH, CH, DH).
"SD" - SI or DI registers.
"A" - EDX:EAX registers (64-bit value in two registers).
"y" - MM register.
"x" - XMM register.
"t" - ST(0) register (floating point).
"r" - General purpose register.
"m" - Memory.
"i" - Immediate.
"g" - Memory, general purpose register or immediate.

Fog - Layers and clipping to paths

2010-04-11T23:26:00.012+02:00

Introduction

There is one rule I broke today - "never write more than one post per day". But I hope that people that's following my blog will forgive me :-). Currently I'm working on layers and clipping to paths (painter related) and I'm getting troubles to finish this stuff. I'd like to expand more about clipping, the design I'm preparing and multithreading issues, or features?

Abstract

Let's summarize the goals in a few points:

Define clipping API, clipping will be part of Fog::Painter.
Allow to clip to rectangles or a path, the API should be similar as the current painting API.
Allow these clipping operations - COPY, UNION, INTERSECT, XOR and SUBTRACT.
Allow using the actual opacity when clipping paths.
Allow save() / restore(), make it very efficient.
Clipping API inside rendering routines must be very efficient.

API Proposal

The API proposal (it can change, it's only what I'm working with):

struct FOG_API PaintEngine
{
  // Only additions, not the whole PaintEngine.

  // Clip parameters.
  virtual uint32_t getClipRule() const = 0;
  virtual err_t setClipRule(uint32_t clipRule) = 0;

  virtual float getClipAlpha() const = 0;
  virtual err_t setClipAlpha(float alpha) = 0;

  // Raster clipping.
  virtual err_t clipRect(
    const IntRect& rect,
    uint32_t clipOp) = 0;

  virtual err_t clipMask(
    const IntPoint& pt,
    const Image& mask,
    uint32_t clipOp) = 0;

  virtual err_t clipRegion(
    const Region& region,
    uint32_t clipOp) = 0;

  // Vector clipping.
  virtual err_t clipRect(
    const DoubleRect& rect,
    uint32_t clipOp) = 0;

  virtual err_t clipMask(
    const DoublePoint& pt,
    const Image& mask,
    uint32_t clipOp) = 0;

  virtual err_t clipRects(
    const DoubleRect* r,
    sysuint_t count,
    uint32_t clipOp) = 0;

  virtual err_t clipRound(
    const DoubleRect& r,
    const DoublePoint& radius,
    uint32_t clipOp) = 0;

  virtual err_t clipEllipse(
    const DoublePoint& cp,
    const DoublePoint& r,
    uint32_t clipOp) = 0;

  virtual err_t clipArc(
    const DoublePoint& cp, 
    const DoublePoint& r, 
    double start,
    double sweep,
    uint32_t clipOp) = 0;

  virtual err_t clipPath(
    const DoublePath& path,
    uint32_t clipOp) = 0;

  virtual err_t resetClip() = 0;
};

Clipping operators and flags are defined in the Fog/Graphics/Constants.h:

enum CLIP_OP
{
  CLIP_OP_MASK = 0xFFFF,

  CLIP_OP_COPY = 0,
  CLIP_OP_UNION = 1,
  CLIP_OP_INTERSECT = 2,
  CLIP_OP_XOR = 3,
  CLIP_OP_SUBTRACT = 4,

  CLIP_OP_COUNT = 5
};

enum CLIP_FLAGS
{
  CLIP_FLAG_MASK = 0x0000FF00,

  CLIP_FLAG_STROKE = 0x00000100,
  CLIP_FLAG_INVERT = 0x00000200
};

Discussion

You should imagine that goals are very rich, if everything will be completed then Fog::Painter will be one of most featured painting class in 2d graphics libraries today. The biggest problem with this all stuff is to make clipping memory and performance efficient. For example examine this scenario:

void paintSomething(Painter& p)
{
  // Save state.

  p.save();

  // Reset the clipping region to our rectangle. The resulting 
  // clip region will be one rectangle at:
  //
  //   [100, 100] -> [200, 200].

  p.clipRect(
    IntRect(100, 100, 100, 100),
    CLIP_OP_COPY);

  // Unite the current clipping rectangle with a new rectangle,
  // using Fog::Region API, the resulting clipping region will
  // be three rectangles at: 
  //
  //   [100, 100, 200, 150]
  //   [100, 150, 250, 200]
  //   [150, 200, 250, 250]
  //
  // Good is that painter can clip to more than one rectangle and
  // it's well optimized already.

  p.clipRect(
    IntRect(150, 150, 100, 100),
    CLIP_OP_UNION);

  // We should do something more exacting, we will intersect current
  // clipping region with circle. Generally this will result to making
  // clip-mask from current clipping region, rasterizing ellipse, and
  // doing intersect operation with the clip-mask.

  p.clipEllipse(
    DoublePoint(125.0, 125.0),
    DoublePoint(100.0, 80.0),
    CLIP_OP_INTERSECT);

  // Now I'm sure that we have clipping-mask created, so each painter
  // command will be blit using this clip-mask. This is also optimized,
  // but generally slower than using simple clip region.
  //
  // If we can fill everything we should see the region we created.
  // The ellipse corners must be anti-aliased.

  p.setSource(Argb(0xFFFFFFFF));
  p.fillAll();

  // And the now we enter to the interesting problem. We want to save
  // state and intersect our region with something else. The painter
  // engine must be able to optimize such thing, because we don't want
  // to copy data to new clip mask that will be never rewritten.

  p.save();

  // So clip to smaller ellipse using XOR operator.

  p.clipEllipse(
    DoublePoint(125.0, 125.0),
    DoublePoint(50.0, 50.0),
    CLIP_OP_XOR);

  // And fill all using 50% opacity to see what happened.

  p.setSource(Argb(0x7F0000FF));
  p.fillAll();

  // Restore the saved state (including clipping).

  p.restore();

  // Restore the master state (to the state used before 
  // this function was called).
  p.restore();
}

The example should be very explanatory how the paint engine works. If clipping area can be described by one or more rectangles aligned to pixel grid, then Fog::Region is used. This is the most optimized clipping and I expect that it will be the most used one. If it's needed to clip to text, shape or to set another image as a clip-mask then paint engine must create temporary buffer where the clipping bits will be set. We are talking about mask, but this mask must be smarter than common image container. I solved clip-mask inside painter using these techniques:

Clip-mask state ID - Each painter state has ID that is incremented or decremented calling the Painter::save() or Painter::restore() methods, respectively. This state is also saved to clip-mask. This all prevents against modification clip-mask that has lower clip-state than the current state is. Note that when used multithreaded renderer the context states can be totally different at some time (for example thread-#1 can work with clip-mask-#4 and thread-#2 can work with clip-mask-#8).
Clip spans - Each paint context (main or worker one) contains special memory allocator that is responsible for allocating data used by the clipping engine. Each row contains pointer to the header. If the pointer is NULL then this row is fully clipped, otherwise it's pointer to small data structure that contains linked list of clip-spans. Clip span can be mask or single-value container (so handling semi-transparent clip spans is as fast as handling full opaque ones). The last problem were to solve data ownership. I solved it by using one bit in pointer (which is never used by pointer itself, hackery, mostly used by scripting languages and VMs) that is ORed with the pointer to header. If the bit is set then you can't modify the clip-spans, copy must be made instead. Although the design seems to be complicated it's not too much complicated as it may be looking.
Multithreaded design using existing concepts in RasterPaintEngine - Using delta and offset to work on raster buffer and clip-buffer too. Simple clip operations (rectangles based) are performed by main-thread, but mask-clip operations are performed by workers (if multithreading is used) asynchronously.

Conclusion

You can see that it's not simple so expect some weeks until this all will be ready, but when finished I'm expecting really great API and performance.

Fog and MinGW

2010-04-11T17:56:00.009+02:00

Introduction

It's few days I wanted to measure performance using GCC 4.4 compiler under Windows (MinGW project) and MS compiler that comes with Visual Studio 2005. I know that GCC 3.X that comes with classic MinGW distribution is not usable, because the SSE2 code will crash (variables that must be aligned to 16-bytes aren't actually aligned). But I found TDM's builds here that comes with GCC 4.4 so I wanted to try it. It's classic MinGW distribution that contains everything you need to compile Fog under Windows.

Problems

Porting to different compilers can be sometimes problem, but Fog-Framework can be already compiled under Linux by GCC so this should not be issue there, but it was! See next list for summary:

SEH (Structured Exception Handling) support (currently the support is half or none). I disabled setting thread name which required SEH under Windows.
__uuidof keyword is not supported. I added the declaration to Fog/Core/WinCom_p.h file.
SSE2 aligned variables (GCC 3.X is unsupported by Fog-Framework).
Some MMX issues (for example _mm_movemask_pi8() isn't declared by mmintrin, but only by xmmintrin.h). This is ugly, because you can't use this instruction in 3dNow code (or code that is not using SSE and xmmintrin.h header at all).

Status

Currently I ~~failed~~, but there is only little work getting it working. The MMX issue killed my efforts and I haven't more time to port Fog-Framework to MinGW. I think that MSVC builds will be always preferred so MinGW support is not too important at this stage.

Tried it again, solved all remaining issues and get Fog-Framework working with MinGW. The SSE2 code seems to work.

Benchmarks

Fog compiled by MSVC from Visual Studio 2005:

Fog-st                |Size      |Time
----------------------+----------+---------------
Create-Destroy        |          |     8.556 [ms]
FillRect              |8x8       |   114.737 [ms]
FillRectAffine        |8x8       |   661.535 [ms]
FillRound             |8x8       |  1255.336 [ms]
FillPolygon           |8x8       |   849.288 [ms]
LinearGradient        |8x8       |   123.087 [ms]
Image                 |8x8       |    73.623 [ms]
ImageAffine           |8x8       |   690.516 [ms]
FillRect              |16x16     |   147.333 [ms]
FillRectAffine        |16x16     |  1206.372 [ms]
FillRound             |16x16     |  1762.231 [ms]
FillPolygon           |16x16     |  1605.876 [ms]
LinearGradient        |16x16     |   348.908 [ms]
Image                 |16x16     |   192.550 [ms]
ImageAffine           |16x16     |  1605.280 [ms]
FillRect              |32x32     |   426.969 [ms]
FillRectAffine        |32x32     |  2390.545 [ms]
FillRound             |32x32     |  2384.321 [ms]
FillPolygon           |32x32     |  3225.605 [ms]
LinearGradient        |32x32     |  1142.196 [ms]
Image                 |32x32     |   605.737 [ms]
ImageAffine           |32x32     |  4589.409 [ms]
FillRect              |64x64     |  1442.734 [ms]
FillRectAffine        |64x64     |  5319.678 [ms]
FillRound             |64x64     |  4051.782 [ms]
FillPolygon           |64x64     |  6466.598 [ms]
LinearGradient        |64x64     |  4109.335 [ms]
Image                 |64x64     |  2114.683 [ms]
ImageAffine           |64x64     | 15363.219 [ms]
FillRect              |128x128   |  5248.772 [ms]
FillRectAffine        |128x128   | 13056.322 [ms]
FillRound             |128x128   |  8969.170 [ms]
FillPolygon           |128x128   | 13303.179 [ms]
LinearGradient        |128x128   | 15219.043 [ms]
Image                 |128x128   |  6686.566 [ms]
ImageAffine           |128x128   | 57204.439 [ms]
---------------------------------+---------------
Summary                          |183965.512 [ms]

Fog compiled by MinGW, GCC 4.4:

Fog-st                |Size      |Time
----------------------+----------+---------------
Create-Destroy        |          |     9.704 [ms]
FillRect              |8x8       |   177.904 [ms]
FillRectAffine        |8x8       |   783.850 [ms]
FillRound             |8x8       |  1648.189 [ms]
FillPolygon           |8x8       |  1000.516 [ms]
LinearGradient        |8x8       |   147.183 [ms]
Image                 |8x8       |    78.658 [ms]
ImageAffine           |8x8       |   802.412 [ms]
FillRect              |16x16     |   151.563 [ms]
FillRectAffine        |16x16     |  1358.739 [ms]
FillRound             |16x16     |  2178.581 [ms]
FillPolygon           |16x16     |  1832.505 [ms]
LinearGradient        |16x16     |   379.035 [ms]
Image                 |16x16     |   201.049 [ms]
ImageAffine           |16x16     |  1670.730 [ms]
FillRect              |32x32     |   432.374 [ms]
FillRectAffine        |32x32     |  2622.023 [ms]
FillRound             |32x32     |  2822.627 [ms]
FillPolygon           |32x32     |  3563.021 [ms]
LinearGradient        |32x32     |  1142.975 [ms]
Image                 |32x32     |   620.877 [ms]
ImageAffine           |32x32     |  4416.297 [ms]
FillRect              |64x64     |  1430.939 [ms]
FillRectAffine        |64x64     |  5707.836 [ms]
FillRound             |64x64     |  4540.674 [ms]
FillPolygon           |64x64     |  7114.262 [ms]
LinearGradient        |64x64     |  3832.149 [ms]
Image                 |64x64     |  2167.543 [ms]
ImageAffine           |64x64     | 14033.499 [ms]
FillRect              |128x128   |  5177.839 [ms]
FillRectAffine        |128x128   | 13816.561 [ms]
FillRound             |128x128   |  9868.423 [ms]
FillPolygon           |128x128   | 14507.163 [ms]
LinearGradient        |128x128   | 13908.575 [ms]
Image                 |128x128   |  6668.388 [ms]
ImageAffine           |128x128   | 50864.119 [ms]
---------------------------------+---------------
Summary                          |181678.674 [ms]

The results are pretty interesting, the LinearGradient and ImageAffine tests are significantly better compiled by GCC.

Fog and C++ exceptions

2010-03-06T18:17:00.013+01:00

Introduction

Last few weeks I'm thinking about something I rejected a many years ago - C++ exceptions and RTTI. The reason I rejected these features is that it makes resulting binary code bigger and writing exception safe code is a bit different. I think that the major part of Fog code is exception safe, but I can't assure that all the code really is.

The most interesting question is why? I'm asking yourself, why? Fog-Framework contains error codes for almost everything. It's quite simple to add new ones, it's simple to use operating system ones and it's simple to propagate error codes to the caller (just return them).

Code bloat

Fog is currently always compiled without exceptions and RTTI, because it makes resulting binary compiled by GCC smaller (about 10-15%, more for 64-bit). The most interesting thing is that MSVC can compile code with exceptions much better (resulting code grows only by few kilobytes). Personally I'm calling this as a true code-bloat and it's sometimes a very good argument from hardcore-C lovers against C++. Unfortunately for them - it can be turned off!

Let me show the pros and cons of current Fog-Framework code base.

Pros (code without exceptions)

Exceptions, STL and RTTI features are not used/needed.
Resulting binary code is smaller (15% is very good).
It's not needed to write exception-safe code.
Error codes are lightweight and enough.

Cons (code without exceptions)

Exception enabled code can be more readable.
Checking for errors is sometimes annoying, because in most cases there are checks for memory allocation failure.

Model cases

I'd like to show some model cases where I think that exceptions are good and where don't. The first example demonstrates Fog::StringW and checking for error codes. I think that here the exception enabled code could be more readable (Here only memory allocation failure can happen).

err_t test(Fog::StringW& result)
{
  // Error can be only be returned in case that there is not enough
  // memory to allocate the array of characters needed for the string.
  err_t err;

  err = result.set(Fog::Ascii8("Hello World"));
  if (FOG_IS_ERROR(err)) return err;

  err = result.append(Fog::CharW('!'));
  if (FOG_IS_ERROR(err)) return err;

  return Fog::ERR_OK;
}

In next example I think that error codes make sense and I like them very much:

err_t test(const Fog::StringW& fileName)
{
  Fog::Stream stream;
  err_t err;

  // Here I think that error code is better. It must be processed by caller 
  // in all cases (opening a file seems to be an important task). The most
  // expected error should be related to a filesystem (file not found) or to 
  // user permissions (can't read).
  err = stream.openFile(fileName, Fog::STREAM_OPEN_READ);
  if (FOG_IS_ERROR(err)) return err;

  // And history repeats itself :)
  err = stream.truncate(0);
  if (FOG_IS_ERROR(err)) return err;

  // ...

  return Fog::ERR_OK;
}

Conclusion

I'm staying with exception-free code (no exceptions, RTTI and STL) and I will probably never use them in my libraries in the future. I forget to mention one important reason in the PROS section - any application or library can use Fog-Framework as a third-party product without switching to exceptions or RTTI. If you like exceptions, just use them;)

Suggestions

Error codes can be simply turned to exceptions by using macros. For example following macro will test result of the expression inside and throw an Exception on error condition:

// Define our macro.
#define FOG_THROW_ON_ERROR(expression) \
  do { \
    err_t __err_inside = (expression); \
    if (FOG_IS_ERROR(__err_inside)) \
      throw new Exception(__err_inside); \
  } while (0)

// Use our macro.
Fog::Stream stream;
FOG_THROW_ON_ERROR( stream.openFile(fileName, Fog::STREAM_OPEN_WRITE) );

Our macro can be rewritten to the more robust form allowing you to do more than only throw exception (for example you can log it):

void error_handler(err_t err)
{
  throw new Exception(err);
}

#define FOG_THROW_ON_ERROR(expression) \
  do { \
    err_t __err_inside = (expression); \
    if (FOG_IS_ERROR(__err_inside)) \
      error_handler(__err_inside); \
  } while (0)

Also the similar macro can be written for current code-base. I added following macro to help with readability of the code:

#define FOG_RETURN_ON_ERROR(expression) \
  do { \
    err_t __err_inside = (expression); \
    if (FOG_IS_ERROR(__err_inside)) \
      return __err_inside; \
  } while (0)

The comparison between the first example with and without the macro is here:

// Old (without macro).
err_t test(Fog::StringW& result)
{
  // Error can be only be returned in case that there is not enough
  // memory to allocate the array of characters needed for the string.
  err_t err;

  err = result.set(Fog::Ascii8("Hello World"));
  if (FOG_IS_ERROR(err)) return err;

  err = result.append(Fog::CharW('!'));
  if (FOG_IS_ERROR(err)) return err;

  return Fog::ERR_OK;
}

// New (with macro).
err_t test(Fog::StringW& result)
{
  FOG_RETURN_ON_ERROR( result.set(Fog::Ascii8("Hello World")) );
  FOG_RETURN_ON_ERROR( result.append(Fog::CharW('!')) );

  return Fog::ERR_OK;
}

Conclusion 2

The FOG_RETURN_ON_ERROR() is now a standard way of how to propagate errors to the called. It's suitable in most of cases, but there are still some cases where standard err = ...; if (err) ... code needs to be processed, because on error condition additional cleanup code needs to be run.

ImageIO::GdiPlus work continues

2010-02-27T09:09:00.004+01:00

Finally

It's weekend and I get some time to work on Fog again. Today I finished basic support for writing images through GDI+ ImageIO backend (Fog::ImageIO::GdiPlusEncoderDevice class). The idea of proxy providers (and proxy encoders / decoders) is gone (also the related constants are away), because it was too complex to implement it correctly. Instead there is provider for each supported image file type (at this time there are only three - jpeg, png and tiff).

The API is fully integrated with rest of Fog-Framework, but I found that I'm not able to use progress indication (I didn't find the API in GdiPlus). Currently also properties are not supported (so for example you can't set jpeg compression), but I will fix this very soon.

What's next?

Next thing I want to improve in Fog library is raster engine. I want to implement all remaining stuff needed to make Fog fully usable:

Allow painting to ARGB32 and A8 images, currently Fog can crash:-).
Improve image filtering, allow to use filters by painter and take advantage of multithreading.
Allow to set global painter opacity.
Fix font backends to support kerning and hinting.
Write pure MMX backend (the machine where I'm currently sitting is not SSE2 capable and Fog performance is very close to Gdi+).

I don't know which point I implement first, but I want to first finish raster engine stuff and then move to vectors. After all of this will be finished I'm looking forward to write widgets in Fog/Gui.

That's all, enjoy my work!

ImageIO::GdiPlus Support

2010-02-14T22:41:00.001+01:00

Recently I haven't time to write status of Fog library. Of course there are some news, but I thing that everything is moving so slow. This weekend I worked on windows-only machine so I tried to make Gdi+ support in Fog::ImageIO. The reason is that this is native library under Windows (like libpng and libjpeg under unix). It wasn't easy.

IStream

Firstly I needed to create IStream <-> Fog::Stream bridge. The default IStream implementation from MSDN helped me a lot to complete Fog::WinIStream class that implements some methods from IStream and ISequentalStream interface. Fog::WinIStream is used internally and it's not exported.

GdiPlusProvider

Secondly the Fog::ImageIO::GdiPlusProvider was needed. The design goal was to create provider that will be able to use Fog::Stream API (like all other providers do). The Fog::Stream is used to create Fog::WinIStream instance that implements IStream interface. GdiPlus supports IStream interface for Input/Output so image reading and writing using native Fog::Stream is now supported.

Dependencies

GdiPlus provider is runtime loading dependency and I wrote it in way that no GdiPlus header files are needed to compile Fog with GdiPlus support. Fog is using runtime loaded GdiPlus Flat API.

Status

Currently only a Fog::ImageIO::GdiPlusDecoderDevice is functional, encoder needs still some work.

Fog vs BlitJit - Benchmarking SrcOver

2009-10-19T03:09:00.001+02:00

Introduction

It's some time ago I wanted to know BlitJit library possibilities. BlitJit library is library that allows to jit compile graphics functions so they can be called from C/C++ code. But question is how good is the code this library produces compared to SSE2 code in Fog? The SSE2 code in Fog library is written using inline SSE2 intrinsics, BlitJit code generator can generate code only using SSE2 intrinsics, so we are talking about comparing SSE2 code generated by different code generators - gcc vs BlitJit that's using AsmJit.

Static vs Dynamic code

Before I show code generator example I'd like to explain differences in static and dynamic assembler. Static assembler is used by Fog library (through C++ intrinsics) and it's compiled by C++ compiler into shared library (machine code). After the shared library is loaded the code can run (this means that code is interpreted by host processor). Dynamic code generation is concept used to dynamically compile code (usually on-the-fly). This is usually done for performance (compiling inner loops, graphics, sound effects) or as a cross-platform solution for some programming languages (Java, LLVM, etc).

Summary of basic differences:

	Static code	Dynamic code
CPU:	Compiled for host compatible CPU	Dynamic compiler can compile to any supported CPU on-the-fly
Code storage:	Shared libraries, executables	Process virtual memory
Optimizations:	Compiler (C/C++/...) or hand written (Asm), architecture and CPU features must be set before compilation	Hand written, JIT compiler can optimize better for current CPU (SSE2, SSE3) and take adventage of embedding constants, drastically expanding inner loops, etc...
Code sharing:	Static code is usually shared between processes (shared libraries)	Dynamic code is normally not shared between processes, but can be (Java, .NET)
Complexity:	Normal	Very complex, need time to study asm and to write good code
Performance:	Very good	Best (you can recompile loops, embed constants, etc...)

Benchmark suite

So you should now know basic differences in theory, let's look into practice. The function that was benchmarked is SrcOver for 32-bit premultiplied ARGB source and destination. I'm benchmarked span blitter (one row per time) in Fog library and two span blitters generated by BlitJit (JITed). First generated function is using four pixels in inner loop, second eight pixels in inner loop. My machine contains Core Quad Q6600@2.4GHz and I'm running Gentoo Linux (64-bit), kernel 2.6.30, gcc 4.4.1. I think that other information are not important, because we are talking all the time about software rendering.

Benchmarking function makes 500x blit of source image (128x128) into destination image (400x400) using provided blitter. Main function and helper are here:

static void _blitImage(Fog::Image& dst, int x, int y, const Fog::Image& src, BlitterFn blitter)
{
  sysint_t i;

  sysint_t w = src.getWidth();
  sysint_t h = src.getHeight();

  sysint_t dstStride = dst.getStride();
  sysint_t srcStride = src.getStride();

  uint8_t* dstData = const_cast<uint8_t*>(dst.cFirst()) + y * dstStride + (x << 2);
  const uint8_t* srcData = src.cFirst();

  for (i = h; i; i--, dstData += dstStride, srcData += srcStride)
  {
    blitter(dstData, srcData, w, NULL);
  }
}

static double _blitBench(Fog::Image& dst, const Fog::Image* images, BlitterFn blitter)
{
  // Move images to the cache.
  dst.drawImage(Fog::IntPoint(0, 0), images[0], Fog::CompositeSrcOver);
  dst.drawImage(Fog::IntPoint(0, 0), images[1], Fog::CompositeSrcOver);
  dst.drawImage(Fog::IntPoint(0, 0), images[2], Fog::CompositeSrcOver);
  dst.drawImage(Fog::IntPoint(0, 0), images[3], Fog::CompositeSrcOver);
  dst.clear(0x00000000);

  srand(10);

  Fog::TimeTicks time = Fog::TimeTicks::highResNow();

  for (int i = 0; i < 500; i++)
  {
    int x = rand() % (400 - 128);
    int y = rand() % (400 - 128);
    int z = rand() % 4;

    _blitImage(dst, x, y, images[z], blitter);
  }

  return (Fog::TimeTicks::highResNow() - time).inMillisecondsF();
}

Blitters were generated by this initializer:

typedef void (FOG_FASTCALL *BlitterFn)(uint8_t* dst, const uint8_t* src, sysint_t w, const void* closure);

static BlitterFn blitterFog;
static BlitterFn blitterExperimental;

static void _blitInit()
{
  // Get Fog blitter from Fog::Raster module.
  blitterFog = (BlitterFn)(
    Fog::Raster::functionMap->raster
      [Fog::CompositeSrcOver]
      [Fog::Image::FormatPRGB32]
        .span_composite[Fog::Image::FormatPRGB32]);

  // Generate blitter using BlitJit library
  BlitJit::Generator gen;

  AsmJit::FileLogger logger(stderr);
  gen.c->setLogger(&logger);

  gen.setPrefetch(true);
  gen.setClosure(true);

  gen.experimentalBlitSpan(
    &BlitJit::Api::pixelFormats[BlitJit::PixelFormat::PRGB32],
    &BlitJit::Api::pixelFormats[BlitJit::PixelFormat::PRGB32],
    &BlitJit::Api::operators[BlitJit::Operator::CompositeOver]);
  blitterExperimental = AsmJit::function_cast<BlitterFn>(gen.c->make());
}

Destination buffer and source images were prepared using this code:

  Image dst;
  Image src[4];

  dst.create(400, 400, Fog::Image::FormatPRGB32);

  src[0].readFile(Fog::Ascii8("babelfish.png"));
  src[0].convert(Fog::Image::FormatPRGB32);
  src[1].readFile(Fog::Ascii8("blockdevice.png"));
  src[1].convert(Fog::Image::FormatPRGB32);
  src[2].readFile(Fog::Ascii8("drop.png"));
  src[2].convert(Fog::Image::FormatPRGB32);
  src[3].readFile(Fog::Ascii8("kweather.png"));
  src[3].convert(Fog::Image::FormatPRGB32);

Results

Here are benchmarked results:

Function	Best time [ms]	Average time [ms]	Average [FPS]
Fog (SSE2, GCC 4.4.1)	20.200	22.800	43.85
BlitJit (SSE2, 4 pixels at time)	17.500	18.400	54.35
BlitJit (SSE2, 8 pixels at time)	15.000	15.800	63.30

Screenshot of the benchmarking application:

Conclusion

You can see that nearly equal Fog and BlitJit code (Fog uses 4 pixels at a time in inner loops) needs only 86% of CPU time to run. When using 8 pixels per loop BlitJit needs only 75% CPU time to run compared to Fog. I think that results are promising, you probably never beat BlitJit using C/C++ code and when using assembler you probably never write faster code than BlitJit is able to generate.

Fog - First Multithreaded SVG Renderer?

2009-08-16T00:53:00.003+02:00

Introduction

Last two weeks there are few things that happen in Fog library. The first one is that Fog/Xml library was improved, it's now better and it should be also faster. The second, most interesting thing is new Fog/Svg library that is able to render basic SVG documents. Currently there are many things that's not supported, but API is written to be extensible (classes and virtual methods). Main problems are CSS selectors (that's not supported) and style attributes (currently only style="something=value;..." is supported).

Status

The SVG format is quite complicated and I think that it's impossible to make full support of this format based on the official specification (I used official specification). But on the other side, there are many tools that exports SVG documents only by using limited set of features, and I want to support these documents.

What is working:

All SVG painting commands - circle, ellipse, g, line, path, polygon, polyline, rect.
Affine transformations - transform attribute.
Definitions - linearGradient and radialGradient, link attribute xlink:href is also supported.
Fill rule and pattern (color or url to gradient), Stroke width, stroke styles and pattern (color or url).
DPI conversion (currently not for all elements, added yesterday).

What is not working:

Filter effects - not supported.
Text - there is basic support but it's broken at the moment.
Scripting and animations are not supported.

Although the implementation in Fog library is currently very basic, it's first open-source (MIT) SVG rendering engine that is able to use multithreading (through Fog painting engine).

And here is popular SVG tiger rendered by Fog/Svg:

Fog - Introduction

2009-06-25T04:42:00.008+02:00

Some time ago I started writing new graphics library that I want to use as a drawing backend for my windowing system and GUI toolkit. Its name is Fog, which stands for 'Fair Object Graphics'. Currently Fog library contains many classes and like other libraries it's divided into sections. My intention when I started writing the Fog library was performance and easy-to-use API. I think that I have succeed except that the library is not finished yet (like many others).

Fog library is currently pure software based library (so no GPU, only CPU is used for rasterization and rendering), but main advantage is that architecture of the library allows to replace blitters and renderers. Currently there is quite efficient SSE2 backend, your CPU will like it;). Optimized are also gradient fills and benchmarks show that Fog library can fill gradients or tile images in unbelivable time compared to others.

So why I'm talking about Fog? The Fog library is getting better day by day and I think that next year the library will be able to compete with others in number of features and speed. There are graphic libraries used in both Windows and Linux/BSD world, but each library has advantages and disadvantages. For example, GDI+ is quite fast and full-featured (you can find really interesting graphics effects and possibilities in it), but it's closed-source and it can't be ported to other operating systems. There is also Cairo, which is really mature library, but compared to GDI+ it's slower and doesn't contain as many features as GDI+ (I think that Mono developers have really hard times getting Cairo to work as Graphics2d API). So for cross-platform development is Cairo the only choice, except you are a more experienced developer that can wrap for example AntiGrain.

So I think it's time to introduce a new library - Fog, that can be used as a solution for cross-platform development for applications with graphic output. Fog library also comes with platform layer, so you can use for example Fog::StringW to work with unicode strings, Fog::DirIterator to iterate over objects in a directory, and various other classes.

Small example on how to render something with Fog-Framework:

  using namespace Fog;

  Image image(SizeI(320, 320), IMAGE_FORMAT_PRGB32);
  Painter p(image);

  p.setSource(Argb(0xFFFFFFFF));
  p.fillAll();

  float x = 10.5f;
  float y = 10.5f;
  float w = 300.0f;
  float h = 300.0f;

  PathF path;
  path.addRound(RectF(x, y, w, h), PointF(50.0f, 50.0f));

  LinearGradient gradient(PointF(x, y), PointF(x + w, y + h));
  gradient.addStop(0.0f, Argb32(0xFFFFFF00));
  gradient.addStop(1.0f, Argb32(0xFFFF0000));

  p.setSource(gradient);
  p.fillPath(path);

  p.setSource(Argb32(0xFF000000));
  p.drawPath(path);
  p.end();

  image.writeToFile(StringW::fromAscii8("./output.png"));

And here is the resulting image 'output.png':

I thing that this example is self-explanatory. Fog-Framework is strongly object-oriented and there are classes with related members and methods for everything. You can also see that Fog painting engine is state based, so it's closer to Cairo than to GDI+, but on the other hand, Fog also contains very strong raster manipulation methods, so it's not pure vector graphics library, it's just yet another graphics library where design and preformance are important properties.

For more info about Fog-Framework please visit Fog project page. The library is MIT licensed, so you can use it for what you want without restrictions.

List of other graphics libraries:

Cairo - Cross-platform 2d vector graphics library.
Qt - If you are Qt developer, just use built-in Qt painting, it's well integrated with rest of Qt API.
Skia - Interesting library, the design is very friendly for embedded systems, possibility to use only fixed point math.

Thanks to Kralik for corrections!