Writing a custom vector graphics renderer - part 1

Martin Fouilleul  —  8 months ago
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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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 :

1
2
3
4
5
6
7
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 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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.

1
2
3
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 :

1
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*(1-3)^3 + 3*C1*t*(1-t)^2 + 3*C2*t^2*(1-t) + C3*t^3

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 :

1
2
3
4
5
6
7
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 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 [[b]S;B][/b] and [[b]B;E][/b], 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 :

1
2
3
4
5
6
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

1
M = S0 + mu*(B01-S0)

where

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

and finally,

1
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) :

1
(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 :

1
(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 :

1
(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
#13814
Felix Schütt  —  7 months, 3 weeks ago
There is a faster way to draw lines: instead of calculating extra triangles, just duplicate the points of the line, calculate the normals and do the actual calculation of the final points in a vertex shader.

See here: https://blog.mapbox.com/drawing-a...ed-lines-with-opengl-8766f34192dc
#13815
Martin Fouilleul  —  7 months, 3 weeks ago
Yes, that's a fair point ! although I guess you would have to create a new line segment for each bevel join ?

Furthermore, I suspect it would force the renderer to issue separate GL calls for strokes and fills (because it would have to switch shaders and use a different set of vertex attributes). As the GUI system issue lots of interleaved strokes and fills, this would prevent us to draw large batches of data at once, which is a big performance hit.

But of course, if it was possible to draw all lines separately from the rest of the geometry (as it would be for a map drawing application), that would absolutely be the way to go.
#13816
Felix Schütt  —  7 months, 3 weeks ago
Yes, you have to write two seperate shaders for strokes and fills, however you basically only need two draw calls: one for strokes and one for fills. If you have access to OpenGL 3.1 and beyond, you can use GL_RESTART_INDEX to "restart" lines, i.e. render lots of lines in one draw call. I am using this technique to render streets in a mapping application (i.e. I can render 100000 lines in one draw call and only have to calculate the line width once on startup, while having the ability to zoom in and out of the map).

Bevel joins are tricky, but you can just duplicate the edge points and calculate the extruding normals once on startup (i.e. adding "fake" points when submitting the line to the renderer). Same thing for rounded joins, but they'd have to be re-generated based on your zoom level.

The "efficency" with this system comes when you want to zoom in on the lines. Because you have the normals on the GPU, all you have to do is to send a uniform value (the line thickness) to the GPU, then multiply it in the vertex shader. If you have lots and lots of lines, it can be more efficent to switch shaders, than to calculate the normals on the CPU.

But yes, it doesn't quite fit your usecase. I just wanted to add this if anyone visits this site via Google in the future.

--

That said, I have found some other interesting graphics programming websites, not sure if you know about them:

- Your algorithm for recursively dividing the bezier curve can be (theoretically) optimized even more if you take into account the angles: http://antigrain.com/research/adaptive_bezier/

- Not sure if you need it, but maybe you'll need to handle intersections of polygons, I found this interesting: http://www4.ujaen.es/~fmartin/bool_op.html

#13865
Martin Fouilleul  —  7 months, 3 weeks ago [Edited 0 minutes later]
Oh ok, that zoom thing is a smart one (especially for a map application !!)

In my use case there's an immediate mode gui on top of all that, and each widget can use strokes, fills and/or font rendering. It could be possible to defer those calls and send only three different batches, but it would also imply somehow keeping track of the z-order. I will have to give it a thought, but I don't know yet if it's worth the extra machinery.

Anyway thanks for your comments and for the links, I will check this out !

Happy Holidays,

Martin
Log in to comment