CSCE 441 Lecture 3

« previous | Friday, January 17, 2014 | next »

Drawing Lines

Line between $(x_{L},y_{L})$ and $(x_{H},y_{H})$.

Midpoint Algorithm

(assume drawing is from left-to-right and slope is in $[0,1]$, but similar abstractions can be made for all directions)

At each step, we determine whether the next pixel should be to the east (E) or the northeast (NE) due to restrictions on slope: $0\leq m\leq 1$.

To determine E vs. NE, we need to decide whether the intersection of $y=m\,x+b$ and $y=y_{i}$ for this iteration is above or below $x=x_{i}+{\frac {1}{2}}$ (i.e. the midpoint between pixels)

Take slope-intercept equation and put all terms on one side:

${\begin{aligned}y&=m\,x+b\\0&=y-m\,x-b\end{aligned}}$

The RHS of this equation is the implicit form of a line.

$f(x,y)=y-m\,x-b$

If a point is above the line, the value of $f$ will be positive. If a point is below the line, the value of $f$ will be negative

Hence if $f\left(x_{i}+1,y_{i}+{\frac {1}{2}}\right)<0$, we go NE, and if $f\left(x_{i}+1,y_{i}+{\frac {1}{2}}\right)>0$, we go E

int x = xL;
int y = yL;
int d = xH - xL;
int c = yL - yH;
int sum = 2c + d; // initial value
draw(x,y);
while (x < xH ) {
    if (sum < 0) {
        sum += 2d;
        y++;
    }

    x++;
    sum += 2c;
    draw(x,y);
}

• Only integer operations
• need implicit forms

Scan Conversion of Polygons

Generally, Pixels that touch (or are within) polygon bounding box are considered part of a polygon, but we encounter an issue of ownership: if multiple polygons touch at a line, those pixels could be drawn multiple times (overdraw).

To prevent overdraw, we do not fill in top or right pixels that "belong" to the polygon.

• intersect scan lines (rows of pixels) with edges of polygon
• Find ranges along $x$ of scan-line
• Fill interior of those ranges
• use information about adjacent lines to speed up drawing

Data Structures

Edges

struct Edge
{
    maxY;
    currentX;
    xIncr;
};

struct Edge e;
e.maxY = max(y[i], y[i+1]);
e.currentX = y[i] == min(y[i], y[i+1]) ? x[i] : x[i+1];
e.xIncr = (x[i+1] - x[i]) / (y[i+1] - y[i]);   // throw out horizontal lines (!)

Active Edge Table

Map from scan line to Linked List of Edges

Insert edges at scan-line associated with lowest endpoint

Edge in table[y] if min(edge.y) == y

Active Edge List

List of edges intersecting current scan-line sorted by current $x$-values

Number of elements in list should always be even.

Algorithm

int line = 0; // optimization: minimum y-value in edges
int height = // difference between minimum and maximum y-values in edges.
while (line < height) {
    add edges to activeEdgeList from activeEdgeTable that start at line
    Remove edges that end at line (i.e. where maxY == line)
    Fill pixels between currentX values of consecutive pairs: ABCD -> AB, CD this is why the list is sorted.
    Increment x-values (i.e. currentX += xIncr)
    line++
}