← Back to index
2017-12-17

Hi,

This month I have been pretty busy replacing the whole rendering system of Top's user interface, which was based on Cairo Graphics , with my own handmade vector graphics renderer, using OpenGL. I discussed in a previous post the reasons why I wanted to drop Cairo, but in short : it's adding a bunch of dependencies we don't fully use, it complexifies the building and bundling of the application, and it's quite slow using either the software or the Quartz backend.

I'm pretty happy with the new renderer, and I will put a new build online after tightening the few last bolts, probably in the first week of January. It's currently supporting all features that we needed from Cairo, with only a slightly better performance, but there's a lot more room for optimization and I now have complete control over what's going on. Hopefully we will be able to redirect all the CPU horsepower freed in the process to a nice DSP engine !
In the meantime I'm going to make a few posts about that vector graphics system, covering how I handle path stroking, filling, text rendering, and performance issues.

Much like other 2D vector graphics libraries, Top's renderer is built around the concept of a graphics context, which holds some properties such as the current color, the line width, the font size, etc. and paints into a surface, typically a window. It also exposes an API to build a path consisting of connected segments and curves, and some drawing functions that draw the outline of the path or fill the area contained by it.

So the goal here is to take a path as input, and output a set of triangles to be sent to the GPU. Later, we could try to push more work load into the shaders, but for now that part is done in the CPU. In this post I will give an overview of the path construction and the stroking mechanism.

Constructing Paths

The path is defined as a list of path elements. I'm using a list_info structure much similar to linux linked lists, and I just embed a list_info member inside the structures I want to put in a list.

A path element can be of type MOVE_TO, which is used for the starting point, LINE_TO, which describes a straight line from the current point to the next point p, and CURVE_TO, which describe a cubic Bezier curve from the current point to the next point p using the two control points c1 and c2.

The points p, c1 and c2 are of type Point3H, which represent a 3D vector in homogeneous coordinates. Although our paths are really 2D, I kept it 3D internally in the event of me feeling the need to have a full 3D vector graphics system. That's rather unlikely for now, but it doesn't incur such a hit and operations can be nicely optimized with SIMD.

struct graphics_path { typedef enum { MOVE_TO, LINE_TO, CURVE_TO} element_type; struct element { list_info list; element_type type; Point3H p; Point3H c1, c2; }; list_info elements; uint32 count; bool closed; };

The graphics context is a structure that, among other properties, hold a graphics_path. You can use the following functions to sequentially build a path :

void GraphicsMoveTo(GraphicsContext* context, const Point2& point); void GraphicsLineTo(GraphicsContext* context, const Point2& point); void GraphicsCurveTo(GraphicsContext* context, const Point2& c1, const Point2& c2, const Point2& p); void GraphicsClosePath(GraphicsContext* context);

Those functions create a path element and append it to the path's elements list :

void GraphicsCurveTo(GraphicsContext* context, const Point2& c1, const Point2& c2, const Point2& p) { graphics_path::element* elt; elt = (graphics_path::element*)GraphicsContextScratchAlloc(context, sizeof(graphics_path::element)); elt->type = graphics_path::CURVE_TO; elt->c1 = Point3H(c1.x, c1.y, 0, 1); elt->c2 = Point3H(c2.x, c2.y, 0, 1); elt->p = Point3H(p.x, p.y, 0, 1); ListAppend(&path->elements, &element->list); path->count++; }

It's pretty straightforward, the only particularity here being the use of GraphicsContextScratchAlloc(), which gives us a bloc of memory from a “scratch buffer” owned by the graphics context to hold transient state and perform temporary calculations, avoiding a frequent use of malloc/free.
Now we introduce three other functions that sets the current color, line width, and curve tolerance. That last parameter determines the precision needed when approximating Bezier curves.

void GraphicsSetColor(GraphicsContext* context, const Color& color); void GraphicsSetLineWidth(GraphicsContext* context, float32 lineWidth); void GraphicsSetCurveTolerance(GraphicsContext* context, float32 tolerance);

Finally we have a functions which is used to stroke the path with the currents properties :

void GraphicsStroke(GraphicsContext* context);

Path Stroking

Converting curves to series of lines

The first step involves evaluating the Bezier curves elements of the path to replace them with line elements. Along the way we also eliminate duplicated points, which saves us unnecessary calculation and edge-cases special handling.

A cubic Bezier curve is a parametric curve defined by the equation :

P(t) = C0(13)3 + 3C1t(1t)2 + 3C2t2(1t) + C3t3

Where C0, C1, C2, C3 are the control points and t varies from 0 to 1. Practically, when we encounter a CURVE_TO element, we replace it by a series of LINE_TO elements by calling GraphicsPathBezierToLines(), whose prototype is the following :

void GraphicsPathBezierToLines(GraphicsGLContext* context, graphics_path* path, Point3H c0, Point3H c1, Point3H c2, Point3H c3, float32 tolerance);

This function takes the four control points of a cubic Bezier curve and a tolerance value, and fills a path with an estimate of that curve composed of line segments. It actually calls GraphicsPathBezierToLinesRecursive(), which recursively evaluates the curve portion starting at an element elt for t = tmin and ending at the next element, with parameter t = tmax :

void GraphicsPathBezierToLinesRecursive(GraphicsContext* context, graphics_path* path, graphics_path::element* elt, Point3H c0, Point3H c1, Point3H c2, Point3H c3, float32 tmin, float32 tmax, float32 tolerance) { float32 t = (tmax+tmin)*0.5f; Point3H p = GetBezierPoint(t, c0, c1, c2, c3); graphics_path::element* next = ListEntry(elt->list.next, graphics_path::element, list); Point3H middle = (elt->p + next->p)*0.5f; float32 d = (middle-p).Norm2(); if(d >= tolerance) { if(p==c0) { return(GraphicsPathBezierToLinesRecursive(context, path, elt, c0, c1, c2, c3, t, tmax, tolerance)); } if(p==c3) { return(GraphicsPathBezierToLinesRecursive(context, path, elt, c0, c1, c2, c3, tmin, t, tolerance)); } graphics_path::element* newElt = (graphics_path::element*)GraphicsContextScratchAlloc(context, sizeof(graphics_path::element)); newElt->type = graphics_path::LINE_TO; newElt->p = p; ListInsert(&elt->list, &newElt->list); path->count++; GraphicsPathBezierToLinesRecursive(context, path, elt, c0, c1, c2, c3, tmin, t, tolerance); GraphicsPathBezierToLinesRecursive(context, path, newElt, c0, c1, c2, c3, t, tmax, tolerance); } }

In that function we evaluate the point on the curve which is “halfway” between our two end-points, using the equation of the cubic Bezier curve. If the distance from this point to the middle of the segment between our two end-points exceeds the tolerance value, we break our current segment in two, joining our end-points to the point we just evaluated. We then repeat the operation for both segments.

Generating triangles for the renderer

We now proceed to stroke the path. For each path element, we have three points to consider :

  • S, which is the middle of the segment joining the destination points of the last-processed and the current elements. When processing the first element of the path, we define the last-processed element to be the last element of the path if the path is closed, otherwise we set S to be the destination point of the first element.
  • B, which is the destination point of the currently processed element.
  • E, which is the middle of the segment joining the destination points of the current and the next elements.

From these points we compute n1 and n2, the normals to [S;B] and [B;E], as shown on the figure. If the cross-product of these normals points along negative z, the normals are pointing to the outside of the angle formed by S, B, E. Otherwise, they are pointing inside, and we multiply them by 1 to always have them pointing outside. We now compute S0, S1, B01, B02, E0, E1, Q and M as shown on the figure below :

Which leads us to the following computation :

S0 = S + halfW*n1 S1 = S - halfW*n1 B01 = B + halfW*n1 B02 = B + halfW*n2 E0 = E + halfW*n2 E1 = E - halfW*n2

where halfW is half the current line width. M is the intersection between (S0;B01) and (E0;B02), so

M = S0 + mu*(B01-S0)

where

mu = ((Xb02-Xe0)*(Ys0-Ye0) - (Yb02-Ye0)*(Xs0-Xe0))/((Yb02-Ye0)*(Xb01-Xs0) - (Xb02-Xe0)*(Yb01-Ys0))

and finally,

Q = 2*B - M

Join types

If we want to render mitter joins, we can send the following triangles to our OpenGL renderer (details on how we implement that will appear in a next post) :

(Q, S0, S1) (Q, E1, E0) (Q, E0, B02) (Q, B02, B01) (Q, B01, S0) (B02, M, B01)

Otherwise we render a bevel join by sending the following triangles to our OpenGL renderer :

(Q, S0, S1) (Q, E1, E0) (Q, E0, B02) (Q, B02, B01) (Q, B01, S0)

When the angle between the two segments of the join is very small, the distance between M and B, aka the mitter excursion, grows towards infinity. We thus define a mitter excursion threshold : when the mitter excursion is higher than the threshold, we falback to the bevel join case.

Finally, if there is no next element and the path is not closed, ie. E == B we draw a butt cap :

(S0, S1, E1) (S0, E1, E0)

The screenshot below shows the stroke in action :

This wraps up the overview of our first drawing function. In the next post I will show how we triangulate any (non intersecting) polygon in order to fill the area inside our path.


See you !

Martin