Writing a custom vector graphics renderer - part 2

Martin Fouilleul  —  6 months ago [Edited 3 days, 20 hours later]
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.

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


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
#13837 Simon Anciaux  —  5 months, 4 weeks ago
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.


- 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.
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" ?
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.
#13838 Martin Fouilleul  —  5 months, 4 weeks ago [Edited 2 days, 16 hours later]
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 !
#13849 Simon Anciaux  —  5 months, 3 weeks ago
Thanks, et oui je parle français.
Log in to comment