Hello !

This is the second part to my series of posts describing the 2D vector graphics system behind Top's user interface. 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 triangulate said polygon, which means split it in no overlapping triangles to 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 :

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

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

Let v1, v2, ..., vn be a list of polygon vertices sorted from top to bottom.

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.

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 :

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

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

Let v1, v2, ..., vn be a list of polygon vertices sorted form top to bottom

For each vertex vi from 1 to n,

In the above algorithm, we create a cut for each merge or split vertex. A cut can be from a vertex vi to its left edge's helper h, which is a valid diagonal, because otherwise their should exist a reflex vertex between h and vi, and it would itself be the helper.

It can also be from a vertex vi 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 vi 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

The total number of vertices of all monotone parts is 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.

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 Point3H arguments p1, p2, p3 and optimizes the computation of ((p2 - p1)

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 (pprev, p, pnext) 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).

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 rewind 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 !

Martin

This is the second part to my series of posts describing the 2D vector graphics system behind Top's user interface. This one will focus on the triangulation of polygons, an essential operation when filling user-defined paths.

*Note : if you find notations (especially mathematical ones) hard to read, this post is also available here with (hopefully) better formatting. I couldn't achieve the same formatting here with BBCode.*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 triangulate said polygon, which means split it in no overlapping triangles to 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 an inside 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 an inside diagonal and clip one "ear", ie one triangle). This approach is in O(n^2) time, because we recursively find diagonals in O(n) time. But there are better approach 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 v1, v2, ..., vn be a list of polygon vertices sorted from top to bottom.

- We first push v1 and v2 on the stack.
- Each time a vertex vi is encountered,
- If it is on the same polygonal chain as the top of the stack, we can pop each vertex vj that produces a valid diagonal [vi;vj], stopping at the first invalid vertex. Then we push vi.
- If vi is not on the same chain as vtop, all diagonals from vi to any vertex vj on the stack is valid, so we add all [vi;vj] and pop all elements of the stack. Then we push vtop and vi.

*Fig. 1 : Triangulating a monotone polygon. Green lines are valid diagonals. Red dotted lines are invalid diagonals. Red dots are vertices on the stack.*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.

*Fig. 2 : Classification of polygon vertices.*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.

*Fig. 3 : The helper vertex of a left edge.*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 v1, v2, ..., vn be a list of polygon vertices sorted form top to bottom

For each vertex vi from 1 to n,

- If vi is a start vertex, we add the left incident edge with vi as its helper.
- If vi is an end vertex,

- remove the left incident edge e from
**S**. - If e has a pending merge m, we create a cut from vi to m and add it to
**C**. Then we remove m from e.

- remove the left incident edge e from
- If vi 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 vi as its helper. - If e has a pending merge m, we create a cut from vi to m and add it to
**C**. Then we remove m from e.

- remove the upper edge from
- If vi is a regular vertex that has the polygon on its left,

- find the closest edge e on the left of vi in
**S**, and replace its helper with vi. - If e has a pending merge m, we create a cut from vi to m and add it to
**C**. Then we remove m from e.

- find the closest edge e on the left of vi in
- If vi is a merge vertex,

- find its left incident edge e1 in
**S**. - If e1 has a pending merge m, we create a cut from vi to m and add it to
**C**. - remove e1 from
**S**. - find the closest edge e2 on the left of vi in
**S**and replace its helper and its pending merge with vi.

- find its left incident edge e1 in
- If vi is a split vertex,

- find the closest edge e on the left of vi in
**S**and create a cut from vi to the helper of e and add it to**C**. - replace the helper of e with vi.
- add the right edge from vi to
**S**with vi as its helper. - If e has a pending merge m, we create a cut from vi to m and add it to
**C**. Then we remove m from e.

- find the closest edge e on the left of vi in

*Fig. 4 : Actions corresponding to each vertex type. Black is for removal, red for insertion, blue for search and/or modification, and pink denotes a possible cut to a merge vertex.*In the above algorithm, we create a cut for each merge or split vertex. A cut can be from a vertex vi to its left edge's helper h, which is a valid diagonal, because otherwise their should exist a reflex vertex between h and vi, and it would itself be the helper.

It can also be from a vertex vi 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 vi 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 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 :

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; }; |

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...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | struct polygon_vertex_info { list_info list; // polygon_vertex_info structs are chained in polygon_sorted_info::vertexList graphics_path::element* elt; // path element corresponding to this vertex polygon_vertex_info* prev; // polygon_vertex_info struct holding the previous element in path polygon_vertex_info* next; // polygon_vertex_info struct holding the next element in path uint32 eltIndex; // index of the element in path }; struct polygon_sorted_info { list_info list; // polygon_sorted_info structs are chained together when decomposing a poly into monotonous polys list_info vertexList; // list holding the polygon_vertex_info elements uint32 count; // number of vertices bool counterClockWiseWinding; // we cache the winding order here }; |

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

1 2 3 4 5 6 7 8 9 10 11 12 | struct polygon_edge_info { polygon_edge_info* parent; polygon_edge_info* left; polygon_edge_info* right; Point3H from; Point3H to; Point3H helper; Point3H merge; bool pendingMerge; }; |

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

1 2 3 4 | void DecomposeInMonotonousPolygons(GraphicsContext* context, graphics_path* path, list_info* polygons, uint32* polyCount); |

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 :

1 2 3 4 5 6 7 8 9 10 | (...) graphics_path::element* t = (ListEntry(ListBegin(vertexList), polygon_vertex_info, list))->elt; graphics_path::element* tm1 = GraphicsPathGetPreviousElement(path, t); graphics_path::element* tp1 = GraphicsPathGetNextElement(path, t); bool counterClockWiseWinding = (TriangleNormalMagnitude(tm1->p, t->p, tp1->p) > 0); sortedInfo->counterClockWiseWinding = counterClockWiseWinding; (...) |

where TriangleNormalMagnitude() is a function that takes three Point3H arguments p1, p2, p3 and optimizes the computation of ((p2 - p1)

*****(p3 - p1))**.****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 :

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | (...) for_each_in_list(vertexList, vertexInfo, polygon_vertex_info, list) { polygon_vertex_info* vprev = vertexInfo->prev; polygon_vertex_info* vnext = vertexInfo->next; Point3H p = vertexInfo->elt->p; Point3H pprev = vprev->elt; Point3H pnext = vnext->elt; polygon_vertex_type vertexType; if(pprev.y >= p.y && pnext.y > p.y) { //NOTE(martin): this is a merge point or an end point float32 f = TriangleNormalMagnitude(pprev, p, pnext); if(counterClockWiseWinding == (f > 0)) { vertexType = VT_END; } else { vertexType = VT_MERGE; } } else if(pprev.y < p.y && pnext.y <= p.y) { //NOTE(martin): this is a split vertex or a start vertex float32 f = TriangleNormalMagnitude(pprev, p, pnext); if(counterClockWiseWinding == (f > 0)) { vertexType = VT_START; } else { vertexType = VT_SPLIT; } } else { //NOTE(martin): this is a regular vertex if(counterClockWiseWinding == ((p.y-pprev.y) > 0 || (pnext.y-p.y) > 0)) { vertexType = VT_REGULAR_RIGHT; } else { vertexType = VT_REGULAR_LEFT; } } (...) |

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 (pprev, p, pnext) 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 :

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | (...) switch(vertexType) { case VT_START: { //NOTE(martin): this is a start vertex // we add the conter clockwise incident edge to it polygon_edge_info* info = (polygon_edge_info*)GraphicsScratchAlloc(context, sizeof(polygon_edge_info)); info->from = p; info->to = counterClockWiseWinding ? pnext : pprev; info->helper = p; info->pendingMerge = false; InsertEdge(&edgeList, info); } break; case VT_END: { //NOTE(martin): this is an end vertex // we remove the incident edge from the status list polygon_edge_info* edge = counterClockWiseWinding ? FindEdge(&edgeList, pprev, p) : edge = FindEdge(&edgeList, pnext, p); if(edge->pendingMerge) { polygon_cut* cut = (polygon_cut*)GraphicsScratchAlloc(context, sizeof(polygon_cut)); cut->from = edge->merge; cut->to = p; ListAppend(&pendingCuts, &cut->list); } RemoveEdge(edge); } break; case VT_MERGE: { //NOTE(martin): this is a merge vertex // we replace the helper of the edge directly left of v by v. // we make the pending merge of that edge be v // we remove the edge clockwise from this vertex from the status list polygon_edge_info* removed; if(counterClockWiseWinding) { removed = FindEdge(&edgeList, pprev, p); } else { removed = FindEdge(&edgeList, pnext, p); } if(removed->pendingMerge) { polygon_cut* cut = (polygon_cut*)GraphicsScratchAlloc(context, sizeof(polygon_cut)); cut->from = removed->merge; cut->to = p; ListAppend(&pendingCuts, &cut->list); } RemoveEdge(removed); polygon_edge_info* edge = GetCloserLeftEdge(&edgeList, p); if(edge->pendingMerge) { polygon_cut* cut = (polygon_cut*)GraphicsScratchAlloc(context, sizeof(polygon_cut)); cut->from = edge->merge; cut->to = p; ListAppend(&pendingCuts, &cut->list); } edge->helper = p; edge->merge = p; edge->pendingMerge = true; } break; case VT_SPLIT: { //NOTE(martin): this is a split vertex // we find the edge directly left from v, and add a cut from its helper to v // replace the helper of that edge by v // insert the edge counter clockwise from v into the status polygon_edge_info* edge = GetCloserLeftEdge(&edgeList, p); polygon_cut* cut = (polygon_cut*)GraphicsScratchAlloc(context, sizeof(polygon_cut)); cut->from = p; cut->to = edge->helper; ListAppend(&pendingCuts, &cut->list); edge->helper = p; if(edge->pendingMerge && !(edge->merge == cut->to)) { cut = (polygon_cut*)GraphicsScratchAlloc(context, sizeof(polygon_cut)); cut->from = edge->merge; cut->to = p; ListAppend(&pendingCuts, &cut->list); } edge->pendingMerge = false; polygon_edge_info* info = (polygon_edge_info*)GraphicsScratchAlloc(context, sizeof(polygon_edge_info)); info->from = p; info->to = counterClockWiseWinding ? pnext : pprev; info->helper = p; info->pendingMerge = false; InsertEdge(&edgeList, info); } break; case VT_REGULAR_LEFT: { //NOTE(martin): the vertex is on the left side of the polygon (ie the polygon is right of the incident edge) // replace the upper edge with the lower edge in the status list, // and make v the helper polygon_edge_info* edge = counterClockWiseWinding ? FindEdge(&edgeList, pprev, p) : FindEdge(&edgeList, pnext, p); edge->from = p; edge->to = counterClockWiseWinding ? pnext : pprev; if(edge->pendingMerge) { polygon_cut* cut = (polygon_cut*)GraphicsScratchAlloc(context, sizeof(polygon_cut)); cut->from = edge->merge; cut->to = p; ListInsert(&pendingCuts, &cut->list); edge->pendingMerge = false; } } break; case VT_REGULAR_RIGHT: { //NOTE(martin): the vertex is on the right side of the polygon (ie the polygon is left of the incident edge) // find the edge directly left of v and replace its helper by v polygon_edge_info* edge = GetCloserLeftEdge(&edgeList, p); edge->helper = p; if(edge->pendingMerge) { polygon_cut* cut = (polygon_cut*)GraphicsScratchAlloc(context, sizeof(polygon_cut)); cut->from = edge->merge; cut->to = p; ListInsert(&pendingCuts, &cut->list); edge->pendingMerge = false; } } break; } } |

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 :

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | void TriangulateMonotonePolygon(GraphicsContext* context, polygon_sorted_info* poly, uint32** result, uint32* indexCount) { *indexCount = (poly->count - 2)*3; *result = (uint32*)GraphicsScratchAlloc(context, sizeof(uint32)*(*indexCount)); uint32* indices = *result; list_info* vertexList = &poly->vertexList; bool counterClockWiseWinding = poly->counterClockWiseWinding; //NOTE(martin): initialize the vertex stack by pushing the first two vertices of the polygon list_info vertexStack; ListInit(&vertexStack); list_info* it = ListBegin(vertexList); polygon_vertex_info vi = *(ListEntry(it, polygon_vertex_info, list)); polygon_vertex_info* cpy = (polygon_vertex_info*)GraphicsScratchAlloc(context, sizeof(polygon_vertex_info)); *cpy = vi; ListPush(&vertexStack, &cpy->list); it = it->next; vi = *(ListEntry(it, polygon_vertex_info, list)); cpy = (polygon_vertex_info*)GraphicsScratchAlloc(context, sizeof(polygon_vertex_info)); *cpy = vi; ListPush(&vertexStack, &cpy->list); it = it->next; vi = *(ListEntry(it, polygon_vertex_info, list)); uint32 count = 0; for(int i = 2 ; i < poly->count ; i++) { polygon_vertex_info* tmp = ListEntry(ListPop(&vertexStack), polygon_vertex_info, list); polygon_vertex_info vj = *tmp; polygon_vertex_info top = vj; polygon_vertex_info lastPopped; bool sameChain = (top.next->elt == vi.elt) || (top.prev->elt == vi.elt); while(!ListEmpty(&vertexStack)) { polygon_vertex_info vjm1 = *(ListEntry(ListBegin(&vertexStack), polygon_vertex_info, list)); //NOTE(martin): top of the stack if(sameChain) { float signedArea = TriangleNormalMagnitude(vjm1.elt->p, vj.elt->p, vi.elt->p); bool validDiagonal; if(vi.elt == top.next->elt) { validDiagonal = (counterClockWiseWinding == (signedArea > 0)); } else { validDiagonal = (counterClockWiseWinding == (signedArea < 0)); } if(validDiagonal) { indices[count] = vi.eltIndex; indices[count+1] = vj.eltIndex; indices[count+2] = vjm1.eltIndex; count += 3; } else { break; } } else { //NOTE(martin): we add the triangle (vi, vjm1, vj) indices[count] = vi.eltIndex; indices[count+1] = vj.eltIndex; indices[count+2] = vjm1.eltIndex; count += 3; } lastPopped = vj; polygon_vertex_info* tmp = ListEntry(ListPop(&vertexStack), polygon_vertex_info, list); vj = vjm1; } if(sameChain) { polygon_vertex_info* tmp = (polygon_vertex_info*)GraphicsScratchAlloc(context, sizeof(polygon_vertex_info)); *tmp = vj; ListPush(&vertexStack, &tmp->list); tmp = (polygon_vertex_info*)GraphicsScratchAlloc(context, sizeof(polygon_vertex_info)); *tmp = vi; ListPush(&vertexStack, &tmp->list); } else { polygon_vertex_info* tmp = (polygon_vertex_info*)GraphicsScratchAlloc(context, sizeof(polygon_vertex_info)); *tmp = top; ListPush(&vertexStack, &tmp->list); tmp = (polygon_vertex_info*)GraphicsScratchAlloc(context, sizeof(polygon_vertex_info)); *tmp = vi; ListPush(&vertexStack, &tmp->list); } it = it->next; vi = *(ListEntry(it, polygon_vertex_info, list)); } } |

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 :

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | void GraphicsFillPath(GraphicsContext* context, graphics_path* inputPath) { graphics_path* tesselatedPath = GraphicsPathToPolyLine(context, inputPath, context->curveTolerance); uint32 color = PackColor(context->color); Vector3H* points = (Vector3H*)GraphicsScratchAlloc(context, sizeof(Vector3H)*tesselatedPath->count); uint32* colors = (uint32*)GraphicsScratchAlloc(context, sizeof(uint32)*tesselatedPath->count); uint32* uv = (uint32*)GraphicsScratchAlloc(context, sizeof(Vector2)*tesselatedPath->count); uint32 i = 0; float32 minX = FLT_MAX, maxX = -FLT_MAX, minY = FLT_MAX, maxY = -FLT_MAX; for_each_in_list(&tesselatedPath->elements, elt, graphics_path::element, list) { points[i] = elt->p; colors[i] = color; maxX = maximum(maxX, points[i].x); minX = minimum(minX, points[i].x); maxY = maximum(maxY, points[i].y); minY = minimum(minY, points[i].y); i++; } float32 boxW = maxX - minX; float32 boxH = maxY - minY; i = 0; if(context->gradient) { graphics_rect area = ((GraphicsGradient*)context->gradient)->area; for_each_in_list(&tesselatedPath->elements, elt, graphics_path::element, list) { Point2 p(((elt->p.x - minX)/boxW*area.w + area.x)/GRAPHICS_TEXTURE_ATLAS_WIDTH, ((elt->p.y - minY)/boxH*area.h + area.y)/GRAPHICS_TEXTURE_ATLAS_HEIGHT); uv[i] = PackUV(p); i++; } } uint32 polyCount = 0; list_info polygons; DecomposeInMonotonousPolygons(context, tesselatedPath, &polygons, &polyCount); uint8 mode = (context->gradient)? SHADER_MODE_TEXTURE : SHADER_MODE_COLOR; for_each_in_list(&polygons, poly, polygon_sorted_info, list) { uint32* indices = 0; uint32 indexCount; TriangulateMonotonousPolygon(context, poly, &indices, &indexCount); vertex_attributes* attr = (vertex_attributes*)GraphicsScratchAlloc(context, sizeof(vertex_attributes)*indexCount); for(int i=0;i<indexCount;i++) { attr[i].position = points[indices[i]]; attr[i].packedColor = color; attr[i].packedUV = uv[indices[i]]; attr[i].mode = mode; } GraphicsPushVertexData(context, indexCount, attr); } GraphicsScratchClear(context); GraphicsPathClear(&context->path); } |

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 rewind 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 !

Martin

The post contains useful informations but I found it somewhat hard to read. I'll try to give you some feedback. But my mother tongue is not English so it maybe just me.

It also took me some time to understand where the -2 and +1 were coming from. It was not clear to me that it was 3 points make one triangle so with N vertex you get N - 2 triangles.

You also use letters to name points (q,r,s) and than you use letters to name vertex count (n,j,k) which is a bit confusing.

A small image would make those explanations more obvious.

On fig. 1: having the legend on the image ("Green lines are valid diagonals. Red dotted lines are invalid diagonals. Red dots are vertices on the stack.") would be a good idea, and also having more steps.

Simple polygons: define convex vertex and reflex vertex ? I knew what they were, just not the name in English.

Fig 4. Add the legend in the image ("Black is for removal, red for insertion, blue for search and/or modification, and pink denotes a possible cut to a merge vertex.").

Also a step by step example could be clearer.

As far as I know a diagonal is just a line between two points that are not "next to each other". So there is always a diagonal between those 3 points. Maybe you need to precise "inside diagonal" ?

- If [q;r] is a 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 a 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.

It also took me some time to understand where the -2 and +1 were coming from. It was not clear to me that it was 3 points make one triangle so with N vertex you get N - 2 triangles.

You also use letters to name points (q,r,s) and than you use letters to name vertex count (n,j,k) which is a bit confusing.

A small image would make those explanations more obvious.

A polygonal chain is called monotone with respect to a line L if every line orthogonal to L crosses the chain at most once.I didn't knew what a polygon chain was, so a small definition would help.

On fig. 1: having the legend on the image ("Green lines are valid diagonals. Red dotted lines are invalid diagonals. Red dots are vertices on the stack.") would be a good idea, and also having more steps.

So, when we add a vertex on the same chain, we can add the diagonals from that vertex to vertices on the stack and assume that there is no more valid diagonal after we encounter the first invalid one.Maybe it's just me but the "on" in "vertices on the sack" caused me to read the sentence as "add things on the stack" which made the sentence non-sensible. Would "vertices from the stack" work ?

Simple polygons: define convex vertex and reflex vertex ? I knew what they were, just not the name in English.

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.Would be clearer as

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.

Fig 4. Add the legend in the image ("Black is for removal, red for insertion, blue for search and/or modification, and pink denotes a possible cut to a merge vertex.").

Also a step by step example could be clearer.

The number of vertices of all monotone parts is something in O(n), because each cut only adds only two vertices to the total.The first part of that sentence seems to be missing something, the second part contains the word "only" twice.

Hi Simon ! Thanks for your feedback !

I edited the post with some of your suggestions, I will also try to get more figures to illustrate the parts that seem unclear/ambiguous.

English is not my native language either (je crois deviner qu'on parle la même langue ?), so that induces a little bit of friction when trying to explain maths/technical stuff. Any comment to make it clearer is of course much appreciated !

Happy Holidays !

I edited the post with some of your suggestions, I will also try to get more figures to illustrate the parts that seem unclear/ambiguous.

English is not my native language either (je crois deviner qu'on parle la même langue ?), so that induces a little bit of friction when trying to explain maths/technical stuff. Any comment to make it clearer is of course much appreciated !

Happy Holidays !

Thanks, et oui je parle français.