The general problem of scan conversion is which pixels to turn on. For example, assume a line with positive slope in the first octant, i.e., 0.0 <= m <= 1.0.
and drawn from left to right: (X1, Y1) to (X2, Y2):
The problem is that as we increment xi to xi+1, do we turn on xi+1, yi or xi+1, yi+1?
The general goal is to minimize the stair-step effect (jaggies), have a uniform line density, and require the minimum drawing time. Remember, we must always round or truncate to integers since pixels are at integer positions.
Digital Differential Analyzer (DDA) method
Bresenham (Decision Variable) method
Point and Line Drawing Commands
Demonstration Program for scan
converting lines
The equation for a straight line: y = m * x + b, where m is the slope (m = dy/dx) and b is the y intercept. So for a given x interval (dx) we can compute dy = m * dx, but this is a brute force real number computation and is very slow.
For a line segment x1, y1 -> x2, y2:
x = x1 + t*dx with dx = x2 - x1 and 0.0 <= t <= 1.0
So start with t = 0 and increment to t = 1.0, e.g. t= .05, .10,.15, etc. This is still too slow but parametric equations are used for clipping, curve fitting, and ray tracing.
The basis of the DDA method is to take unit steps along one coordinate and compute the corresponding values along the other coordinate. The unit steps are always along the coordinate of greatest change, e.g. if dx = 10 and dy = 5, then we would take unit steps along x and compute the steps along y.
Let us assume a line of positive slope and draw from x1, y1 to x2, y2.
{slope = m = dy/dx}
if m <= 1.0 then
let x_step = 1 {dx = 1, dy = 0 or 1}
else {m > 1.0}
let y_step = 1 {dy = 1, x_step = 0 or 1 }
Remember: always step along the longest delta.
{m <= 1.0} for x_step = 1, dy = m = yi+1 - yi -> yi+1 = yi + m
{m > 1} for y_step = 1 m = 1/dx => dx = 1/m => xi+1 = xi + 1/m
If, instead, we draw from x2 , y2 to x1, y1 then:
a.) dx = -1 yi+1 = yi -m or
b.) dy = -1 xi+1 = xi - 1/m
For a line with slopeslope < 0.0 and drawing from x1, y1 to x2, y2, i.e., left to right then:
if |m| < 1 then
let dx = 1 and yi+1 = yi + m
else {|m| ³ 1}
let dy = -1 and xi+1 = xi -1/m
if draw from x2, y2 to x1, y1 (right to left) then:
if |m| < 1 then let dx = -1 yi+1 = yi -m
else {|m| ³ 1} dy = 1 xi+1 = xi + 1/m
Complete DDA Algorithm
procedure DDA( x1, y1, x2, y2: integer);
var
dx, dy, steps: integer;
x_inc, y_inc, x, y: real;
begin
dx := x2 - x1; dy := y2 - y1;
if abs(dx) > abs(dy) then
steps := abs(dx); {steps is larger of dx, dy}
else
steps := abs(dy);
x_inc := dx/steps; y_inc := dy/steps;
{either x_inc or y_inc = 1.0, the other is the slope}
x:=x1; y:=y1;
set_pixel(round(x), round(y));
for i := 1 to steps do
begin
x := x + x_inc;
y := y + y_inc;
set_pixel(round(x), round(y));
end;
end; {DDA}
In this method, developed by Jack Bresenham, we look at just the center of the pixels. We determine d1 and d2 which is the "error", i.e., the difference from the " true line."
Steps in the Bresenham algorithm:
now: y = m(xi+1) + b so
d1 = y - yi = m(xi+1) + b - yi
d2 = (yi+1) - y = yi+1 -m(xi+1) - b
then d1 - d2 = 2m(xi+1) - 2y + 2b -1
now define pi = dx(d1 - d2) = relative error of the two pixels.
note: pi < 0 if yi pixel is closer, pi >= 0 if yi+1 pixel is closer ( = 0 is our choice). Therefore we only need to know the sign of pi .
With m = dy/dx and substituting in for (d1 - d2) we get
(1) pi = 2 * dy * xi - 2 * dx * yi + 2 * dy + dx * (2 * b - 1), let C = 2 * dy + dx * (2 * b - 1)
Now look at the relation of p's for successive x terms.
pi+1 = 2dy * xi+1 - 2 * dx * y i+1 + C
pi+1 - pi = 2 * dy * (xi+1 - xi) - 2 * dx * ( yi+1 - yi)
with xi+1 = xi + 1 and yi+1= yi + 1 or yi
(2) pi+1 = pi + 2 * dy - 2 * dx(yi+1 -yi) Note: b = y - dy / dx * x
Now compute p1 (x1,y1) from (1)
p1 = 2dy * x1 - 2dx * y1 + 2dy + dx(2y1 - 2dy / dx * x1 - 1)
= 2dy * x1 - 2dx * y1 + 2dy + 2dx * y1 - 2dyx1 - dx
= 2dy - dx
if pi < 0 choose yi and pi+1 = pi + 2dy
else {pi ³ 0} and choose yi+1 so pi+1 = pi + 2dy - 2dx
Bresenham Algorithm for 1st octant:
Note: Only integer Addition and Multiplication by 2. Notice we always increment x by 1.
For a generalized Bresenham Algorithm must look at behavior in different octants.
Standard Point and Line Drawing Commands
Polyline (n, x, y)
where n = # end points
x = array of x endpoints y = array of y endpoints
So for a single point: n := 1; x(1) := 300; y (1) = 100; polyline(n, x, y);
For a line segment: n := 2; x(1) := 300; y(1) := 100; x(2) := 400; y(2) := 150; polyline(n,x,y);
For a wireframe polygon (closed) the total number of points is the number of vertices plus 1 with the last point equal to the first. So for a triangle:
n := 4;
x(3) := 300; y(3) := 150;
x(4) := 300; y(4) := 100;
polyline(n, x, y);
Output Primitives menu
HyperGraph
Table of Contents.
HyperGraph Home
page.
