A Vector Graphics Renderer — part 2

This is the second part to my series of posts describing a 2D vector graphics system that I wrote to make graphical user interface applications. This one will focus on the triangulation of polygons, an essential operation when filling user-defined paths.

As we saw in the previous post, the user can describe a path using line segments and cubic Bezier curves. But as we can approximate those curves with series of line segments, the paths we have to fill are really polygons.

Currently, my implementation of the fill function imposes the constraint that those polygons must not self-intersect and don't have holes. That's a reasonable assumption for a GUI, and if we ever needed a self intersecting polygon it could be achieved by splitting the path at the intersections to create a set of non intersecting polygons. Except for this limitation, paths can represent any polygon, convex or concave, in any winding convention.

We want to split the polygon into a set of non-overlapping triangles, that can then be sent to the GPU for rendering. Such a triangulation always exists and the number of triangles for n-gon is n − 2. This theorem can be proved by a simple induction:

• Base case: n  =  3. Obviously we can triangulate a triangle and the number of triangles in that triangulation is one, ie. n − 2.
• Now consider a n-gon P and suppose we know the theorem holds for all m < n. We chose a convex vertex p of P and q and r the previous and next vertices in a given winding order.
• If [q;r] is an inside diagonal, split P along [q;r]. It gives us a triangle and a (n − 1)-gon. We now have a triangulation of P with (n − 1) − 2 + 1  =  n − 2 triangles.
• If [q;r] is not an inside diagonal, let s be the concave vertex inside triangle (p,q,r) which is farthest form (q;r). [p;s] is a diagonal, so we can split P in two polygons with j and k vertices, and we know they can be triangulated with j − 2 and k − 2 triangles. Furthermore, we now that n  =  j  +  k  −  2. So P can be triangulated with j − 2 + k − 2  =  n − 2 triangles.

This demonstration also gives us a first approach to implement the triangulation, which is called ear-clipping (at each step we can find a diagonal and clip one “ear”, i.e. one triangle). This approach is in O(n²) time, because we recursively find diagonals in O(n) time. But there are better approaches performance-wise, one good compromise in terms of simplicity vs. performance being in O(n.log(n)), which I will describe here.

Simple case: monotone polygons

A polygonal chain is a connected series of line segments. We say that a polygonal chain is monotone with respect to a line L if every line orthogonal to L crosses the chain at most once. A monotone polygon with respect to a line L is a polygon composed of two monotone chains with respect to L.
In other words, the polygon's vertices can be traversed such that their coordinates along L first monotonically increase, then monotonically decrease.

Such a polygon can be triangulated in O(n) time by a sweep-line algorithm. The idea is to sweep the polygon by a line perpendicular to L, storing the traversed vertices on a stack, popping them when we can create a valid diagonal from the current vertex to a vertex on the stack (Fig. 1).

Let P be a polygon which is monotone with respect to the y-axis.
Let v₁, v₂, ..., v_n be a list of polygon vertices sorted from top to bottom.

• We first push v₁ and v₂ on the stack.
• Each time a vertex v_i is encountered,
  • If it is on the same polygonal chain as the top of the stack, we can pop each vertex v_j that produces a valid diagonal [v_i;v_j], stopping at the first invalid vertex. Then we push v_i.
  • If v_i is not on the same chain as v_top, all diagonals from v_i to any vertex v_j on the stack is valid, so we add all [v_i;v_j] and pop all elements of the stack. Then we push v_top and v_i.

The vertices on the stack always form a continguous concave chain of the polygon (otherwise, they would have been popped to form valid diagonals). So, when we add a vertex on the same chain, we can add the diagonals from that vertex to vertices from the stack and assume that there is no more valid diagonal after we encounter the first invalid one. When we add a vertex from the other chain, since the polygon is monotone we can assume that all diagonals form that vertex to the vertices on the stack are valid.

As we only add a vertex once to the stack, and we create only one diagonal from it before removing it from the stack, it can be seen the total time of this algorithm is O(n). This doesn't account for the time required to sort the list though, but we'll see below that we already generate it when decomposing simple polygons into monotone polygons.

Simple polygons

Any simple (ie non self-intersecting) polygon can be split in monotone parts. Indeed, we already proved that it can be triangulated, and triangles are obviously monotone. (That's just the proof that it can be done, but of course we would like to split it in fewer monotone parts that the full triangulation !).

Let's first distinguish between different types of vertices:

• A vertex is called convex if the angle formed by the two edges at the vertex, with the polygon inside the angle, is less than π radians.
• A vertex is called concave or reflex vertex if the angle formed by the two edges at the vertex, with the polygon inside the angle, is more than π radians.

• A start vertex is a convex vertex with both edges below it.
• A stop vertex is a convex vertex with both edges above it.
• A split vertex is a reflex vertex with both edges below it.
• A merge vertex is a reflex vertex with both edges above it.
• A regular vertex is a vertex with one edge below and one edge above.

The non monotonicity with respect to the y-axis is caused by merge and split vertices. So for each merge or split vertex, we want to find a valid diagonal from that vertex to some other vertex, in order to split the polygon in monotone parts.

So we have a list C of “cuts”, ie diagonals that we will use to split the polygon in monotone parts. C is initially empty.

For an edge e that has the polygon on its right, and a line L parallel to the x-axis, we define the helper h of e to be the lowest vertex above L for wich we can draw an horizontal line from h to e that is contained in the polygon (Fig. 3).
When sweeping a line across the polygon, the helper of an edge may change each time we encounter a new vertex. We call “the pending merge of e” for a position of a sweep line L the last helper of e that was a merge vertex and that has not already been used to create a cut.

We assume we have a structure S (a list or a tree or whatever) that can store edges that have the polygon on their right, along with their helper and their pending merge relative to a given scanline L, sorted from left to right. S is initialy empty.

Let v₁, v₂, ..., v_n be a list of polygon vertices sorted form top to bottom

For each vertex v_i from 1 to n,

• If v_i is a start vertex, we add the left incident edge with v_i as its helper.
• If v_i is an end vertex,
  • remove the left incident edge e from S.
  • If e has a pending merge m, we create a cut from v_i to m and add it to C. Then we remove m from e.
• If v_i is a regular vertex that has the polygon on its right,
  • remove the upper edge from S and add the lower edge to S with v_i as its helper.
  • If e has a pending merge m, we create a cut from v_i to m and add it to C. Then we remove m from e.
• If v_i is a regular vertex that has the polygon on its left,
  • find the closest edge e on the left of v_i in S, and replace its helper with v_i.
  • If e has a pending merge m, we create a cut from v_i to m and add it to C. Then we remove m from e.
• If v_i is a merge vertex,
  • find its left incident edge e₁ in S.
  • If e₁ has a pending merge m, we create a cut from v_i to m and add it to C.
  • remove e₁ from S.
    − find the closest edge e₂ on the left of v_i in S and replace its helper and its pending merge with v_i.
• If v_i is a split vertex,
  • find the closest edge e on the left of v_i in S and create a cut from v_i to the helper of e and add it to C.
  • replace the helper of e with v_i.
  • add the right edge from v_i to S with v_i as its helper.
  • If e has a pending merge m, we create a cut from v_i to m and add it to C. Then we remove m from e.

In the above algorithm, we create a cut for each merge or split vertex. A cut can be from a vertex v_i to its left edge's helper h, which is a valid diagonal, because otherwise their should exist a reflex vertex between h and v_i, and it would itself be the helper.
It can also be from a vertex v_i to the pending merge m of its left edge, which is also a valid diagonal, because otherwise their should exist a reflex vertex r between v_i and m and m would already have been used to create a cut from r to m.
Hence the algorithms splits the polygon along a valid diagonal for each merge or split vertex, thus replacing them with regular vertices and removing the non monotonicity.

There is one edge case to consider though: what if two consecutive vertices have the same y-coordinate ? We can avoid having to deal with three consecutive vertices with same y by removing the middle vertex, but we must adopt a consistent way of categorizing vertices that have their previous or next vertex on the same scan line.
The solution we adopted is that given two vertices with the same y-coordinate, the first one in the path's winding order is considered “higher” than the second one. Also note that as the path is closed, the last vertex of the path should be considered first when compared to the path's starting point. There's two places were we need to account for that edge-case: in the sorting comparison, and in the code that determines a given vertex's type.

Sorting vertices along the y-axis can be done in O(n.log(n)) time.
Each step involves searching, inserting or removing from S, which can be done in O(log(n)), and creating one, two or three cuts which can be done in constant time.

The total number of vertices of all monotone parts is something in O(n), because each cut adds only two vertices to the total. Hence the time to triangulate all monotone parts is O(n) (again, we reuse the sorted list that we already generated so we don't need to account for that). The triangulation of a simple polygon can thus be done in O(n.log(n)) time.

Implementation

As a reminder from the previous post, here's our graphics_path structure that represents the path to be filled:

Instead of directly manipulating the path in our triangulation algorithms, we use a polygon_vertex_info structure that represents a vertex and points to the corresponding path element. It allows to sort the vertices in a polygon_sorted_info structure, but retain an easy access to the order in which they appear in the path. It also stores an index, allowing for drawing the final triangles with calls like glDrawElements() etc...

The left edges along with their helpers an possibly pending merge, are represented by the polygon_edge_info structure:

The function DecomposeInMonotonePolygon() is where we implement the first phase of the triangulation:

After some boilerplate code initializing our edges structure and cuts list, and creating a sorted list of polygon_vertex_info structs from the path, we determine the winding orientation of the path, and cache it in our polygon_sorted_info structure:

where TriangleNormalMagnitude() is a function that takes three Point2 arguments p₁, p₂, p₃ and optimizes the computation of ((p₂  −  p₁) ∗ (p₃  −  p₁)) · k). The operation  ∗  is the cross-product of two vectors,  ·  is the dot product, and k is the unit vector pointing along the z-axis.

Then we enter our loop through each polygon_vertex_info structure in decreasing y-order, which is broken down in two parts. The first part of the loop determines the type of the current vertex:

In the code above, we check if the next and previous points in the path are above, below, or on both sides of the current point, then check the magnitude of the normal of triangle (p_prev, p, p_next) against the path winding order to further discriminate between end/merge and start/split vertices. For regular vertices we only need to check the order in which the previous and next points are distributed along the y-axis against the path winding order to determine if the vertex has the polygon on its right or on its left.

The second part of the loop take the appropriate action for the type of the current vertex:

Then we can apply the cuts that we gathered in the above loop, subdividing our polygon in monotone parts, and storing them in a list of polygon_sorted_info structures.

The triangulation of a monotone polygon is implemented in the function TriangulateMonotonePolygon(). We pass it an already sorted list of vertices from a monotone sub-polygon of the path, and a result and indexCount return parameters in which it will store a buffer of indices describing the triangles to render, and the size of this buffer:

For each vertex vi in decreasing y-order, we pop elements from the vertex stack as long as they are valid diagonals, before the current vertex on the stack. There's two cases to consider, depending on wether or not vi is in the same chain as the element on top of the stack (before starting to pop elements).

• In the case it is not on the same chain, we know that all diagonals are valid.
• Otherwise, we must additionally check diagonals and break at the first invalid one. A diagonal is valid if the current top of the stack is not a reflex vertex, so check the normal of triangle (vjm1, vj, vi) against the winding order.

Now that we can decompose a path in monotone polygons and triangulate them, we can write our path-filling function. As in the stroking function, we start by approximating curves from the path with line segments, calling our GraphicsPathToPolyLine() function. We then decompose the resulting path in monotone polygons, triangulate each of these, and draw the triangles:

Note that there's a bit of trouble here with “flattening” the path into an array of points for easy indexing, but we ended up not using indexed drawing, for two reasons: it appears to be a bit slower on my machine, and it's more cumbersome to use when constructing large batches of triangles chunk by chunk, as we will see on a later post. You can also remark that we take care of computing uv coordinates to fill our path with a gradient (or possibly any texture) instead of a solid color. That's why we compute the extents of the path and use them to map path elements to uv coordinates in a texture atlas. Again, this will be covered later.

Finally we push all our vertex data to our renderer, to be rendered later in one large batch. After having pushed all the monotone parts of our path we clear it and also clear our scratch buffer, which simply rewinds an offset to the begining of the memory block that the graphics context owns for scratch computations, thus “freeing” the buffer for the next drawing call.

Here you can see two shapes being filled with a solid color and a gradient:

That's all for now ! In a next post I will discuss about the ways we can actually send data to the GPU more efficiently, how we reduce the number of draw calls to issue, and some other optimizations, in order to achieve an acceptable performance.

Thanks for reading, and have great Holidays and a happy new year !