08. Filled Area Primitive - 1

Dated: 22-04-2025

There are two approaches

Scan-line Polygon Fill

Polygon

A polygon can be defined as a shape that is formed by line segments¹ that are placed end to end, creating a continuous closed path.

Types

Convex

These are simplest to fill.
Convex polygon edges do not intersect each other, meaning if we were to draw a line¹ connecting two internal points, the line¹ won't intersect any edge.

A convex shape

Concave

These are superset² of convex polygons.
They may have points, which when connected by a line¹ segment, cross edges of the polygon.

A concave polygon

Complex

These are self intersecting concave polygons.
Complexity arises from the fact that we cannot tell which side is the above or below during filling process.

A complex polygon

Difference between Filled and Unfilled Polygon

For the unfilled polygons, we only have to consider the perimeter but for the filled polygons, we also have to consider the pixels³ within its boundaries.

To determine which pixels³ are inside the polygon, we use the odd parity rule within the scan line polygon fill algorithm.

Parity

Take a point \(O\) outside of the polygon, then draw a line¹ to another point \(P\) which needs to be determined if it lies within the polygon or not.
If this line¹ intersects odd number of edges then the point is inside the polygon, otherwise it is outside.

Using the Odd Parity Test in the Polygon Fill Algorithm

This introduces the problem that how do we determine if our starting point \(O\) is outside or inside the polygon to begin with.
Therefore, at the start of our scan line, we will start with even parity.
As we cross the edges, this parity alternates between odd and even.
Depending on that, we can turn on the filling mode.

Polygon Filling

Our target is to develop an algorithm which is general and works for all 3 types of polygons.
Since complex polygon is a superset² of other two, if our algorithm works for complex polygons then the problem is solved.

Scan line

A scan line is a line¹ of the form \(y = c\) where \(c\) lies within our drawing region, which is our window.

Algorithm

To start with, we will most likely be given a set² of vertices of the polygons in Cartesian coordinates.

Initializing All of the Edges

The all_edges table will hold information regarding which vertices are related to which edges.

An edge is a pair of successive vertices such as \((1, 2)\) and \((2, 3)\) etc.
The information for each edge that is stored in the table is following

• The maximum \(y\) value of both vertices.
• The minimum \(y\) value of both vertices.
• The \(x\) value associated with minimum \(y\) value.
• The slope¹ of the edge.

The slope¹ can be calculated by

• \(y_0 =\) maximum \(y\) value
• \(y_1 =\) minimum \(y\) value
• \(x_0 =\) maximum \(x\) value
• \(x_1 =\) minimum \(x\) value

\[m = \text{slope} = \frac{y_0 - y_1}{x_0 - x_1}\]

Edge Index	Y min	Y max	X val	1/m
0	10	16	10	0
1	16	20	10	1.5
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
N	10	16	28	0

Initializing the Global Edge Table

Since we are filling from bottom to top, the global edge table has to keep the edges with Y min in ascending order.
Also, since we are filling from left to right, the index increases when Y min was same (same height) but X val is increasing (suggesting this edge is on the right side in comparison to other edge).
Ignore the horizontal edges with \(m = 0\).

Edge Index	Y min	Y max	X val	1/m
0	10	16	10	0
1	10	16	28	0
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
N	16	20	10	1.5

Initializing Parity

The initial parity is even since no edges have been crossed yet.

Initializing the Scan-line

Due to the fact that global edges table is sorted, the scan line is initialized with Y min of first entry, as it is the lowest point.

Initializing the Active Edge Table

This keeps track of edges which are intersected by the current scan line.
We will keep adding the edges with same Y min value until we reach a Y min value that is greater than the scan line value.

Edge Index	Y max	X val	1/m
0	16	10	0
1	16	28	0
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
N	16	10	1.5

Filling the Polygon

• Draw all pixels³ as long as parity is odd, for all \(x\) values.
• Increase the scan line by \(1\).
• Remove any edge from the active edge table which has Y max value, equal to the scan line value, implying that this edge has been drawn.
• Update the \(x\) value for each edge in the table using formula \(x_1 = x_0 + \frac 1 m\).
• If the scan line value is equal to Y min of any edge then move that edge from global edge table to active edge table.
• Reorder the edges according to their increasing \(x\) value.

Special Cases

Horizontal Edges

As we know, these lines are excluded from the global edge table.
We will still have the vertices and the algorithm will have to allow to draw this edge connecting both of the vertices.

Bottom and Left Edges vs. top and Right Edges

Blue shows conflicted pixels³

Solution is to remove the top horizontal edges and right vertical edges of both polygons.

The top left of the white polygon (in this figure) was originally in conflict with the bottom right of the black polygon from this figure.
This corner from the black polygon is removed to reveal the white one from beneath.

There are 3 cases where 2 edges meet at a vertex.
These affect both whether a pixel³ is drawn and how parity is counted.

1. Both edges meet at Y min (the vertex is the minimum point for both edges)
   • We draw only the left edge, since right edges are not drawn in the scan-line fill.
   • The pixel³ at the vertex is drawn.
   • Parity is counted twice, once for each edge.
2. Both edges meet at Y max (the vertex is the maximum point for both edges)
   • We don't draw any edge at the vertex, since max Y points aren't drawn in scan-line fill.
   • The pixel³ at the vertex is not drawn.
   • Parity is still counted twice, once for each edge.
3. One edge has the vertex as Y min, the other as Y max (a "bent edge" situation)
   • If both edges are on the left side, the pixel³ is drawn.
     • It's drawn for the edge where the vertex is the minimum point (since left edges are drawn).
     • Parity is counted once.
   • If both edges are on the right side, the pixel³ is not drawn.
     • Right edges are never drawn.
     • Parity is still counted once.

Example

Ordered Vertices

Index	Vertices
0	\((10, 10)\)
1	\((10, 16)\)
2	\((16, 20)\)
3	\((28, 10)\)
4	\((28, 16)\)
5	\((22, 10)\)

Unfilled

edges of the unfilled version

Initializing All of the Edges

	Y-min	Y-max	X-val	1/m
0	\(10\)	\(16\)	\(10\)	\(0\)
1	\(16\)	\(20\)	\(10\)	\(1.5\)
2	\(10\)	\(20\)	\(28\)	\(-1.2\)
3	\(10\)	\(16\)	\(28\)	\(0\)
4	\(10\)	\(16\)	\(22\)	\(1\)
5	\(10\)	\(10\)	\(10\)	\(\infty\)

Initializing the Global Edge Table

	Y-min	Y-max	X-val	1/m
0	\(10\)	\(16\)	\(10\)	\(0\)
1	\(10\)	\(16\)	\(22\)	\(1\)
2	\(10\)	\(16\)	\(28\)	\(0\)
3	\(10\)	\(20\)	\(28\)	\(-1.2\)
4	\(16\)	\(20\)	\(10\)	\(1.5\)

Initializing Parity

Parity is initially set to even.

Initializing the Scan-line

Scan-line is initialized to \(10\) as it is the lowest Y min.

Initializing the Active Edge Table

Global Edges Table

	Y-min	Y-max	X-val	1/m
4	\(16\)	\(20\)	\(10\)	\(1.5\)

Active Edges Table

Index	Y-max	X-val	1/m
0	\(16\)	\(10\)	\(0\)
1	\(16\)	\(22\)	\(1\)
2	\(16\)	\(28\)	\(0\)
3	\(20\)	\(28\)	\(-1.2\)

Filling the Polygon

1. Scan-line = 10

At \(x = 10\), parity becomes odd and points are drawn until \(x = 22\), where parity switches to even.
At \(x = 28\), a point is drawn once due to a special parity case.
The scan-line is complete.
Then, update the active edge table using \(x_1 = x_0 + \frac{1}{m}\).

Index	Y-max	X-val	1/m
0	\(16\)	\(10\)	\(0\)
1	\(16\)	\(23\)	\(1\)
2	\(16\)	\(28\)	\(0\)
3	\(20\)	\(26.8\)	\(-1.2\)

Reorder the edges, as edge 3 has a smaller \(x\) value than edge 2. After reordering, we get:

Index	Y-max	X-val	1/m
0	\(16\)	\(10\)	\(0\)
1	\(16\)	\(23\)	\(1\)
2	\(20\)	\(26.8\)	\(-1.2\)
3	\(16\)	\(28\)	\(0\)

2. Scan-line = 11

Reorder the edges, as edge 3 has a smaller \(x\) value than edge 2.
After reordering, we get

Index	Y-max	X-val	1/m
0	\(16\)	\(10\)	\(0\)
1	\(16\)	\(24\)	\(1\)
2	\(20\)	\(25.6\)	\(-1.2\)
3	\(16\)	\(28\)	\(0\)

3. Scan-line = 12

At \(x = 10\), parity becomes odd and drawing begins.
At \(x = 24\), parity switches to even.
At \(x = 26\), parity becomes odd again, and drawing continues until \(x = 28\).
The scan-line is complete.
Now update the \(x\) values in the active edge table

Index	Y-max	X-val	1/m
0	\(16\)	\(10\)	\(0\)
1	\(16\)	\(25\)	\(1\)
2	\(20\)	\(24.4\)	\(-1.2\)
3	\(16\)	\(28\)	\(0\)

Reorder the active edges, as \(x = 24.4\) (index 2) is less than \(x = 25\) (index 1). This gives:

Index	Y-max	X-val	1/m
0	\(16\)	\(10\)	\(0\)
1	\(20\)	\(24.4\)	\(-1.2\)
2	\(16\)	\(25\)	\(1\)
3	\(16\)	\(28\)	\(0\)

4. Scan-line = 13

At \(x = 10\), parity becomes odd and drawing starts.
At \(x = 25\), parity switches to even, then immediately back to odd.
Drawing continues until \(x = 28\).
The scan-line is complete.
Now update the \(x\) values in the active edge table

Index	Y-max	X-val	1/m
0	\(16\)	\(10\)	\(0\)
1	\(20\)	\(23.2\)	\(-1.2\)
2	\(16\)	\(26\)	\(1\)
3	\(16\)	\(28\)	\(0\)

5. Scan-line = 14

At \(x = 10\), parity becomes odd and drawing begins.
At \(x = 24\), parity switches to even, then to odd at \(x = 26\).
Drawing continues until \(x = 28\).
The scan-line is complete.
Now update the \(x\) values in the active edge table

Index	Y-max	X-val	1/m
0	\(16\)	\(10\)	\(0\)
1	\(20\)	\(22\)	\(-1.2\)
2	\(16\)	\(27\)	\(1\)
3	\(16\)	\(28\)	\(0\)

6. Scan-line = 15

At \(x = 10\), parity becomes odd and drawing starts.
At \(x = 22\), parity switches to even, then to odd at \(x = 27\).
Drawing continues until \(x = 28\).
The scan-line is complete.
Edges at indices 0, 2, and 3 reach their max y and are removed from the active edge table, leaving:

Index	Y-max	X-val	1/m
0	\(20\)	\(22\)	\(-1.2\)

We then need to update the \(x\) values for all remaining edges.

Index	Y-max	X-val	1/m
0	\(20\)	\(20.8\)	\(-1.2\)

Add the last edge from the global edge table to the active edge table, as its min y matches the next scan-line.
The active edge table now becomes: (global edge table is empty).

Index	Y-max	X-val	1/m
0	\(20\)	\(20.8\)	\(-1.2\)
1	\(20\)	\(10\)	\(1.5\)

After reordering:

Index	Y-max	X-val	1/m
0	\(20\)	\(10\)	\(1.5\)
1	\(20\)	\(20.8\)	\(-1.2\)

7. Scan-line = 16

At \(x = 10\), parity becomes odd and drawing begins until \(x = 21\).
The scan-line is complete.
After updating x values, we get:

Index	Y-max	X-val	1/m
0	\(20\)	\(11.5\)	\(1.5\)
1	\(20\)	\(19.6\)	\(-1.2\)

8. Scan-line = 17

At \(x = 12\), parity becomes odd and drawing continues until \(x = 20\).
The scan-line is complete.
After updating x values, we get:

Index	Y-max	X-val	1/m
0	\(20\)	\(13\)	\(1.5\)
1	\(20\)	\(18.4\)	\(-1.2\)

9. Scan-line = 18

At \(x = 13\), parity becomes odd and drawing continues until \(x = 19\).
The scan-line is complete.
After updating x values, we get:

Index	Y-max	X-val	1/m
0	\(20\)	\(14.5\)	\(1.5\)
1	\(20\)	\(17.2\)	\(-1.2\)

10. Scan-line = 19

At \(x = 15\), parity becomes odd and drawing continues until \(x = 18\).
The scan-line is complete.
Both edges reach their max y at the next scan-line and are removed.
The active edge table is now empty, and the process is complete.

References

---

1. Read more about lines and slopes. ↩↩↩↩↩↩↩↩↩

2. Read more about sets. ↩↩↩

3. Read more about pixels. ↩↩↩↩↩↩↩↩↩