What is polygon filling? And what is a polygon for that matter?

Polygon Filling

References:

1. Andy Johnson's CS 488 Course Notes, Lecture 2 and 3
2. Foley, Van Dam, Feiner, and Hughes, "Computer Graphics - Principles and Practice", Sections 3.5 to 3.7

Filling a Polygon

want to avoid drawing pixels twice (not a problem with frame buffers but can be with other display technologies.)

pixels within the boundary of a polygon belong to the polygon
pixels on the left and bottom edges belong to a polygon, but not the pixels on the top and right edges

Want a polygon filling routine that handles convex, concave, intersecting polygons and polygons with interior holes.

overall algorithm:

moving from bottom to top up the polygon

starting at a left edge, fill pixels in spans until you come to a right edge

specific algorithm:

moving from bottom to top up the polygon

1. find intersections of the current scan line with all edges of polygon
2. sort intersections by increasing x coordinate
3. moving through list of increasing x intersections
   parity bit = even (0)
   each intersection inverts the parity bit
   draw pixels when parity is odd (1)

Why do it horizontally, why not vertically?

Algorithm for step 1: scan-line algorithm

as usual there is the straightforward easy way and the convoluted efficient way.

an easy way:

• given that each line segment can be described using x = y/m + B
• each scan line covering the polygon has a unique integer Y value from ymin to ymax
• plugging each of these Y values into the equation gives the corresponding fractional X value
• these values could then be sorted and stored

From above, the specific polygon filling algorithm:

moving from bottom to top up the polygon

1. find intersections of the scan line with all edges of polygon
2. sort intersections by increasing x coordinate
3. moving through list of increasing x intersections
   parity bit = even (0)
   each intersection inverts the parity bit
   draw pixels when parity is odd (1)

---

efficient way:

makes use of the fact that, similar to the midpoint algorithm, once we have an intersection we incrementally compute the next intersection from the current one. Xi+1 = Xi + 1/m

Create a global Edge Table (ET)

• contains all edges sorted by Ymin
• array of buckets - one bucket for each scan line in the polygon
• each bucket has a list of entries stored in increasing X coordinate order (where X is the X value at the Ymin of the line)
• each entry contains Ymax, Xmin (again X at Ymin), 1/m

1. y = minimum Y value in ET (index of first non empty bucket)
2. set Active Edge Table (AET) to be empty
3. repeat until AET and ET are empty
   1. move edges in ET with Ymin = y into AET (new edges)
   2. sort AET on x (AET will eventually include new and old values)
   3. use list of x coordinates to fill spans
   4. remove entries in AET with ymax = y (edges you are finished with)
   5. add 1 to y (to go to the next scan line)
   6. update X values of remaining entries in AET (add 1/m to account for new y value)

Lots of nagging little details for step 3:

- if intersection is at an integer value (say 4.0)

if we are at a left edge then that pixel is interior
if we are at a right edge then that pixel is not interior

- if intersection is at a non integer value (say 4.6) is pixel 4 interior? is pixel 5 interior?

if we are outside the polygon (parity is even) then we round up (pixel 5 is interior)
if we are inside the polygon (parity is odd) then we round down (pixel 4 is interior)

- what if more than one vertex shares the same location? (this also handles the situation where you may end up with an odd number of edges in the AET)

bottom vertex of a line segment counts in parity calculation
top vertex of a line segment does not count in parity calculation

- what if 2 vertices define a horizontal edge?

imperfect, but easy, solution is to ignore this edge.

Example:

So the global ET starts out being ...

------     ----------------     --------------- 
| 20 | --> | 50 | 40 | -1 | --> | 40 | 40 |  0 | 
------     ----------------     ---------------- 
------     ----------------     ---------------- 
| 10 | --> | 50 | 10 |  0 | --> | 40 | 70 | -1 | 
------     ----------------     ----------------

and the horizontal line from (10,10) to (70,10) is ignored.

Now the active edge table starts out with the minimum Y in the global edge table, i.e.:

         ----------------     ---------------- 
Head --> | 50 | 10 |  0 | --> | 40 | 70 | -1 | 
         ----------------     ----------------

Using this edge table for Y=10, parity turns on at X=10 and turns off at X=70, so the pixels from 10 to 69 inclusive would be drawn. Then as Y is increased to 11 for the next line, the active edge table would adjust the X values using the 1/m values, to yield:

         ----------------     ---------------- 
Head --> | 50 | 10 |  0 | --> | 40 | 69 | -1 | 
         ----------------     ----------------

Note that the X in the first entry did not change, because that edge is vertical, but the X in the second entry was changed by 1/m, i.e. it changed from 70 to 69. There are no edges to be added or removed, so the pixels from 10 to 68 inclusive would be drawn for Y=11.

The algorithm will continue this way until Y=20, at which point two new edges get added, and so the active edge table becomes:

         ----------------     ----------------     ---------------     ---------------- 
Head --> | 50 | 10 |  0 | --> | 50 | 40 | -1 | --> | 40 | 40 |  0 |--> | 40 | 60 | -1 | 
         ----------------     ----------------     ---------------     ----------------

Traversing this line there are two parity changes at X=40, so all pixels are drawn from X=10 to 59. Then when Y is incremented to 21, the active edge table becomes:

         ----------------     ----------------     ---------------     ---------------- 
Head --> | 50 | 10 |  0 | --> | 50 | 39 | -1 | --> | 40 | 40 |  0 |--> | 40 | 59 | -1 | 
         ----------------     ----------------     ---------------     ----------------

Now pixels are drawn from 10 to 38 and from 40 to 58. This continues until Y reaches 40, at which point the rightmost two edges drop out and the active edge table becomes:

         ----------------     ---------------- 
Head --> | 50 | 10 |  0 | --> | 50 | 20 | -1 |  
         ----------------     ----------------

and so on, until Y reaches 50 and the remaining two edges are removed from the active edge table.

Why would this algorithm be much simpler if the polygon were guaranteed to be convex with no intersecting edges?

Additional Issues

The above discussion only covers the means of determining the inside versus outside pixels of a polygon defined by straight line segments.

It does not cover polygons whose borders are defined by curves such as circles, ellipses, parabolic functions, or splines. ( Of course these can all be approximated by a series of small straight lines, and given enough, the approximations can be quite good. )

We also haven't addressed what to fill the polygon with. The presence of different lighting models, textures, or bump maps may cause each pixel within the polygons to be colored differently from any of its neighbors. Those issues will come up in later lectures.

DDA line algorithm

Heh Friends here i give a short program for DDA algorithm in C language hope you will enjoy.

#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<ctype.h>
#include<math.h>
#include<stdlib.h>
void draw(int x1,int y1,int x2,int y2);
void main()
{
int x1,y1,x2,y2;
int gdriver=DETECT,gmode,gerror;
clrscr();
initgraph(&gdriver,&gmode,"c:\\tc\\bgi:");
printf("\n Enter the x and y value for starting point:\n");
scanf("%d%d",&x1,&y1);
printf("\n Enter the x and y value for ending point:\n");
scanf("%d%d",&x2,&y2);
printf("\n The Line is shown below: \n");
draw(x1,y1,x2,y2);
getch();
}
void draw(int x1,int y1,int x2,int y2)
{
float x,y,xinc,yinc,dx,dy;
int k;
int step;
dx=x2-x1;
dy=y2-y1;
if(abs(dx)>abs(dy))
step=abs(dx);
else
step=abs(dy);
xinc=dx/step;
yinc=dy/step;
x=x1;
y=y1;
putpixel(x,y,1);
for(k=1;k<=step;k++)
{
x=x+xinc;
y=y+yinc;
putpixel(x,y,2);
}
}

Odd-even rule for polygon

When is a Point Inside a Polygon?

In many applications, it is important to be able to determine whether a certain point is located inside a given polygon. A well-known algorithm to answer this question for general polygons (with possible holes or self-intersections) is the half-line algorithm (also see Figure 1):

1. From the point P in question, shoot a ray (half-line) in any direction, such that the ray does not directly hit any vertices of the polygon Q.
2. Initialize a counter intersectionCount to zero.
3. For each edge e of Q, determine whether the ray intersects that edge. If it does, increase intersectionCount.
4. After all edges of Q have been checked, P is inside Q, if and only if intersectionCount is odd.

Figure 1: Determining whether a point is inside a polygon Q using the half-line algorithm and the even-odd rule. Point P1 is inside the polygon, because its ray intersects Q three times; point P2 is not inside the polygon, because its ray intersects Q four times.

This algorithm, simple as it is, has one major problem: Its stability, or more precisely, its lack thereof. The first step of the algorithm says: "... such that the ray does not directly hit any vertices..." What happens if the ray doeshit any vertices?
In the case of the ray intersecting a line segment exactly at one of the endpoints, should the algorithm consider this a "valid" intersection, or not? The problem is, that each vertex of a polygon is shared by two adjacent polygon edges. This means, if one edge is intersected at an endpoint, the adjacent edge is also intersected at an endpoint. If the algorithm doesn't count a vertex intersection, a ray can exit a polygon without intersecting any edge; on the other hand, if vertex intersections are counted, they are counted twice, having the same effect. This problem can lead to vertices inside the polygon being classified as "outside," and it can also cause points far outside the polygon to be counted as inside.
A simple way to fix the algorithm doesn't really work: We could workaround the problem by shooting another ray if the first one hit a vertex. This leads to another problem: How to determine whether a ray hit a vertex. Due to the limited precision of computer arithmetics, this is not always possible.

To solve this problem once and for all, we have to change the definition of a valid edge intersection. To do this, we agree on always shooting rays in the positive x-direction; in that case, each ray shot from a point (P_x, P_y) separates the (x, y) plane into two regions: The region R₁ containing all the points (p_x, p_y) such that p_y < P_y; and the region R₂ containing all the points (p_x, p_y) such that p_y >= P_y. Then, we only increment the intersection counter, if the two endpoints of an edge lie in different regions, and if the intersection points of the edge with the line y = P_y lies to the right of P, see Figure 2.

Figure 2: Region changes of edges ei with respect to a ray r. e1 does not intersect, because the intersection point is to the left of P; e2 does intersect, e3 does not intersect, because both endpoints are in region R2; e4 does intersect, because the endpoints are in different regions; e5 does not intersect, because both endpoints are in region R2.

This is the modified version of the algorithm to determine whether a point P is inside a polygon Q:

1. Initialize intersectionCount to zero.
2. For each edge e of Q, defined by p1 and p2, check the following:
   1. If p1_y < P_y and p2_y < P_y, do nothing (both points are in region R₁).
   2. If p1_y >= P_y and p2_y >= P_y, do nothing (both points are in region R₂).
   3. Otherwise, calculate the intersection point S of edge e and the line y = P_y. If S_x >= P_x, increment intersectionCount.
3. After all edges have been checked, P is inside Q, if and only if intersectionCount is odd.

The major difference between this algorithm and the previous one is, that this one increments intersectionCount by exactly one when the ray hits a vertex: Only one of the two edges sharing that vertex will change the region and be counted. This solves the stability problem of the original algorithm - now, the only reason a point could be wrongly classified is that it could be lying very close to an edge; in that case, numerical imprecision would make a correct classification impossible. But this is not a problem, since only points very close to edges would be affected; for those, a wrong classification would not matter. Figure 3 shows the "degenerate" case of an axis-aligned polygon. The standard algorithm would typically fail for polygons exhibiting horizontal edges; the improved algorithm always classifies correctly.

Figure 3: Even in a polygon with horizontal edges, the improved algorithm always classifies correctly: Point P2's ray has exactly one region change. Edge e3 counts as a region change, since its endpoints are in different regions and it intersects P2's ray to the right; edge e4 does not count as a region change, since both endpoints are in the same region; edge e5 does not count as a region change for the same reason.

Another benefit of the improved algorithm is its higher performance. Let us consider a polygon having a lot of, say 1000, edges; in the original algorithm, each of the edges would have to be intersected with the ray, which involves lots of expensive arithmetic operations per edge. But only a few of these edges will ever change the region (typically two to six), and the improved algorithm rejects all others by just comparing floating point values, which does not involve any costly operations. It will only do the actual intersection calculation when there is a high chance (50%) that the edge will intersect the ray.
As far as I know, this algorithm has been invented by Prof. Alfred Schmitt (Universität Karlsruhe (TH), Karlsruhe, Germany) in the mid-70s; I have no idea why every graphics book out there doesn't seem to know it. I was lucky, Prof. Schmitt happened to teach the "Introduction to Computer Graphics" course at Karlsruhe.