CSCE 441 Lecture 3
« previous | Friday, January 17, 2014 | next »
Drawing Lines
Line between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_L, y_L)} and .
Midpoint Algorithm
(assume drawing is from left-to-right and slope is in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \le m \le 1} .
To determine E vs. NE, we need to decide whether the intersection of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = m \, x + b} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = y_i} for this iteration is above or below Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = x_i + \frac{1}{2}} (i.e. the midpoint between pixels)
Take slope-intercept equation and put all terms on one side:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} y &= m \, x + b \\ 0 &= y - m \,x - b \end{align}}
The RHS of this equation is the implicit form of a line.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x,y) = y - m \, x - b}
If a point is above the line, the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} will be positive. If a point is below the line, the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} will be negative
Hence if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \left( x_i + 1, y_i + \frac{1}{2} \right) < 0} , we go NE, and if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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++
}