Basis
Frame
Change of Coordinate Systems
Projection
[0,a]x[0,b] -> {0,1, ..., n}x{0, 1, ..., m}
Point scanning: (x,y) -> (round(x), round(y)),
round(w) = int(w + 0.5), closest integer to the real number
|
|
|
|
Line scanning
General equation: y = mx + b, m is the slope of
the line.
Horizontal lines: y=b (m
= 0)
Vertical lines: x
= c (m = oo)
Diagonal:
x = y + b (m = 1)Line segment: defined by 2 points: (x1, y1) to (x2, y2).
x = y + b (m = -1)
m = (y2 - y1) / (x2 - x1)Line Properties
b = y1 - m x1
Direct Conversion Pick the coordinate with the longest projection of the segment
if m < 1 : horizontalHorizontal case: if x1 < x2
if m > 1 : vertical
compute m = (y2 - y1) / (x2 - x1)Vertical case: switch x and y.
for each x, x1 <= x <= x2
compute y = round (m x + b)
draw pixel (x,y)
Bresenham's algorithm
For the case x1 < x2, 0 < m < 1.
x = x1; y = y1;
dx = x2 - x1; dy = y2 - y1;
dT = 2 (dy - dx); dS = 2dy;
d = 2dy - dx;
setPixel(x, y);
while (x<x2) {
x++;
if (d < 0)
d = d + dS;
else {
y++;
d = d + dT;
}
setPixel(x, y);
}
Region: an area enclosed by a boundary in which all of the pixels
are connected.
Connectivity modes: 4-connected or 8-connected.
An algorithm for a 4-connected area.
FloodFill (x0, y0, fill_color,
original_color)
{
int color, x, y;
x = x0; y = y0;
getPixel(x, y, color);
if (color == original_color) {
while (color == original_color) {
setPixel(x, y, fill_color);
FloodFill(x, y+1, fill_color, original_color);
FloodFill(x, y-1, fill_color, original_color);
x = x - 1;
getPixel(x, y, color);
}
x = x0 + 1; y = y0;
getPixel(x, y, color);
while (color == original_color) {
setPixel(x, y, fill_color);
FloodFill(x, y+1, fill_color, original_color);
FloodFill(x, y-1, fill_color, original_color);
x = x + 1;
getPixel(x, y, color);
}
}
}
Original color c0
New color c1 0.67*c0+0.33*c1 0.67*c1+0.33*c0 |
Flood-fill with anti-aliasing:
replace the check for color == original_color
withabs(color - original_color) < 0.33
do not use anti-aliasing for setPixel while flood-filling a region.