Polygon -- is a graphics primitive that consists of an area that is bounded by straight or curved lines. Polygons can also be filled with different patterns and different colors. For the purposes of the following discussion, we will limit the definition to straight lines only.
Specifically, polygons can be defined in one of two ways:
1) as a finite set of ordered edges (edge - is simply a straight
boundary)
2) as an ordered sequence of vertices (in this case the edges
are found by traversing the vertices in a certain order)
List three possible choices of data structures for polygons. Discuss advantages and disadvantages of each.
What operations might we want to perform on polygons? Why?
When considering polygon filling, a couple of facts are obvious:
1) Considering a horizontal scan line through a polygon, the scan
line intersects the polygon either an even or odd number of times
2) If the number of intersections is odd, what must be the case?
Also,
1) When filling a polygon, it is not necessary to traverse those
scan lines above the highest vertex of the polygon or those scan
lines below the lowest vertex of the polygon
2) If we have some arbitrary fill pattern for a polygon that we
are currently scanning, we can compute the intersection points
of the polygon with the scan line and fill between the intersection
points as follows:
3) Consider an arbitrary scan line, for each edge we can check the y-coordinate of each vertex to determine if there is an intersection. We then have a situation as follows:
The larger y-coordinate is ymax and the smaller is ymin. The logic
is then:
if(ymin <= scan line <= ymax) then
there is an intersection, compute it
else
no intersection exists
4) Once we have the intersection pairs calculated, we can then fill between the pairs
5) (Not so obvious) Vertex intersections can be avoided by replacing the y-values (at the vertices) with trunc(y) + 0.5
Problem: Give an example pictorially of how trunc(y) + 0.5 avoids the vertex problem and explain why.
Two other examples will be discussed in class.
We can now talk about the description of a final algorithm for
polygon filling as follows:
1) Choose some data structure that contains a list of only the
edges that intersect with the current scan line. We denote this
at the "current edges".
2) For every new scan line we must do two things: (a) exclude
the edges we just passed (b) include the new edges we've just
met
3) We begin the scan at the greatest y-value of the image (or
polygon) and go from top to bottom one scan line at a time.
Problem: Let's scan convert the following polygon:
1) List the edges that are intersected by scan line b.
2) Consider a data structure that holds the edges of the above polygon. Now let's sort these edges according to their max y-value. Sort from ymax to ymin and list the edges as they would appear in the edge table.
3) Assume we have two temporary pointers (L= leftmost edge; R = rightmost edge) to the edge list such that the leftmost pointer points to the leftmost edge at a given scan line and the rightmost pointer points to the rightmost edge at the same scan line. Show what the edge list with the two temporary pointers looks like at: (a) scan line b (b) scan line c.
4) An edge is included into the active edge list if the current scan line is less than ymax for the edges to the right of R. Zero, one, or more edges might be included in the active edge list. Assume the current scan line becomes the y-value equivalent to the y-value at vertex 3. What does the current edge list with the two pointers L and R look like?
5) Edges between L and R are not necessarily in order. Why not? What needs to be done and how often?
6) Exclusion of edges from the active edge list is based on the y-min value of each active edge with the current scan line. What is the process of checking and removing edges from the current edge list?
Answers to the above questions show that we know how to maintain the current edge list, but scan converting a polygon also requires the computation of intersection points. That is, intersection points of the current scan line and all active edges must be computed accurately and inexpensively. Since polygons are bounded by straight lines, the computation expense of calculating intersection points should be relatively cheap and that is the case.
Consider the following:
As we mentioned earlier, scanning takes place from the maximum y-value of the polygon to the minimum y-value of the polygon. When we hit an initial vertex of an edge, the (x,y) coordinate of that vertex is known. Let's assume that in the above picture that this corresponds to the point (x1,y1). So the problem is given the point (x1,y1), how do we compute the intersection of the next scan line and the edge or the point (x2,y2) in the above picture?
We know that the scan line is decreasing by 1 at each step. This suggests that dy=-1. Further, algebra tells us that slope=dy/dx. If dy=-1 then we have that slope=-1/dx ==> slope(dx)=-1==> dx=-1/slope. But we know that slope is dy/dx and therefore, dx=-(x1-x2)/(y1-y2). Remember, we are going from (x1,y1) to (x2,y2) and thus dx is the negative inverse slope of the edge. Wow!! Great stuff!!
So we know that the y-value decrease by one for each scan line scanned and that the x-coordinate changes by dx for each new scan line. Further, the value of dx is a constant amount and thus only needs to be calculated one time for each edge introduced into the active edge list.
A final data structure for the edge list is a table with the same number of rows as there are edges. Each edge has four entries as follows:
edge#1: ymax, ymin, Dx(negative inverse slope), updated x
........
edge#n: ymax, ymin, Dx, updated x
ymax = the distorted maximum y-value of the edge
ymin = the distorted minimum y-value of the edge
Dx = the change in x for a given scan line
x = intersection point of the scan line and the edge
Problem: Let's do an actual scan conversion of the following polygon:
Create an edge table and for each edge fill in the values for ymax, ymin, Dx, and x.