“Trece años dedicò a esas heterogéneas fatigas, pero la mano de un forastero lo asesinò y su novela era insensata y nadie encontrò el laberinto.”

J.L. Borges, *El jardìn de senderos que se bifurcan.*

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^{ 2}) 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.

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_{1}, v_{2}, ..., v_{n} be a list of polygon vertices sorted from top to bottom.

- We first push v
_{1}and v_{2}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}.

- If it is on the same polygonal chain as the top of the stack, we can pop each vertex v

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.

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 v_{1}, v_{2}, ..., 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.

- remove the left incident edge e from
- 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.

- remove the upper edge from
- 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.

- find the closest edge e on the left of v
- If v
_{i}is a merge vertex,- find its left incident edge e
_{1}in**S**. - If e
_{1}has a pending merge m, we create a cut from v_{i}to m and add it to**C**. - remove e
_{1}from**S**.

− find the closest edge e_{2}on the left of v_{i}in**S**and replace its helper and its pending merge with v_{i}.

- find its left incident edge e
- 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.

- find the closest edge e on the left of v

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

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

struct graphics_path
{
typedef enum { MOVE_TO, LINE_TO, CURVE_TO} element_type;
struct element
{
list_info list;
element_type type;
Point2 p;
Point2 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...

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:

struct polygon_edge_info
{
polygon_edge_info* parent;
polygon_edge_info* left;
polygon_edge_info* right;
Point2 from;
Point2 to;
Point2 helper;
Point2 merge;
bool pendingMerge;
};

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

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:

//(...)
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 Point2 arguments p_{1}, p_{2}, p_{3} and optimizes the computation of ((p_{2} − p_{1}) ∗ (p_{3} − p_{1})) · **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:

//(...)
for_each_in_list(vertexList, vertexInfo, polygon_vertex_info, list)
{
polygon_vertex_info* vprev = vertexInfo->prev;
polygon_vertex_info* vnext = vertexInfo->next;
Point2 p = vertexInfo->elt->p;
Point2 pprev = vprev->elt;
Point2 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 (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:

//(...)
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:

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:

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