TKWNT+5
=v
#1
:n
m
:v
.4166666666666667
:s
o
:c
slope of line
#2
:n
x1
:v
0
:s
i
:c
end point coordinates of the line
#3
:n
y1
:v
0
:s
i
:c
"
#4
:n
x2
:v
12
:s
i
:c
"
#5
:n
y2
:v
5
:s
i
:c
"
=u
=l
#1
:n
x
:v
E
#2
:n
y
:v
E
#3
:n
e
:v
E
#4
:n
@x
:v
E
#5
:n
@y
:v
E
#6
:n
@yy
:v
E
=f
#1
:n
bresenham
:c
slope must be +ive and <= 1
:t
Procedure
:i
x1,y1,x2,y2
:o
m
#2
:n
box
:c
draw boxes to represent pixels
:t
Procedure
#3
:n
CleanUp
:c
Blank calculated lists
:t
Rule
#1
:n
bresenham
:z
m = (y2 - y1)/(x2 - x1)
call blank('x)
call blank('e)
call blank('y)
for i = 1 to (x2 - x1) + 1 ; create a list of x steps
'x[i] = x1 + i - 1
next i
(e, y) = (0, y1)
('y[1], 'e[1]) = (y1, e)
for i = 2 to length('x)
e = e + m ; if the slope from the current position to the next >=0.5
if e >= 0.5 then (y, e) = (y + 1, e - 1) ; increment y by 1 and reset e.
('e[i], 'y[i]) = (e, y)
next i
/E
E
#2
:n
box
:z
call blank('@x)
call blank('@y)
call blank('@yy)
k = 1
for i = 1 to length('x)
('@x[k], '@y[k]) = ('x[i]-.5, 'y[i]-.5)
('@x[k+1], '@y[k+1]) = ('x[i]-.5, 'y[i]+.5)
('@x[k+2], '@y[k+2]) = ('x[i]+.5, 'y[i]+.5)
('@x[k+3], '@y[k+3]) = ('x[i]+.5, 'y[i]-.5)
('@x[k+4], '@y[k+4]) = ('x[i]-.5, 'y[i]-.5)
k = k + 6
next i
('@x[k], '@yy[k]) = ('x[1], 'y[1])
('@x[k+1], '@yy[k+1]) = ('x[length('x)], 'y[length('x)])
/E
E
#3
:n
CleanUp
:z
call blankm('x,'y,'e,'@x,'@y,'@yy)
/E
E
=r
#1
:r
call bresenham(x1,y1,x2,y2 ; m)
#2
:r
call box()
=p
#1
:n
plot
:t
Line chart
:i
"Demonstration of Bresenham's Algorithm"
:s
Yes
:z
Both
:g
No
:q
No
:l
Isotropic
:w
"for lines where 0 =< slope =< 1"
:h
"X"
:v
"Y"
:x
@x
:e
,0,0,0,0,0
:p
0
:q
0
:c
0
:b
0
:o
0
:u
#1
:y
@y
:f
1
:p
Lines
:c
"*"
:m
0
:k
0
:r
1
:n
0
#2
:y
@yy
:f
1
:p
Lines
:c
"*"
:m
0
:k
1
:r
1
:n
0
E
:m
E
:k
E
=t
#1
:n
data
:v
Vertical
:t
""
:u
#1
:l
x
:w
10
:h
""
#2
:l
y
:w
10
:h
""
E
=n
#1
:n
global
:d
4
:f
:^
General
:e
"."
:m
""
:p
None
:i
No
:j
Left
:y
Single quotes preferred
:s
- Only
:q
0
:x
0
:l
""
:t
""
:v
"0"
=c
#1
:n
Documentation
:z
15
To solve the model press F9.
Bresenham's algorithm is an efficient way of deciding which pixels to illuminate
to trace a line on a computer screen. In the model, small squares 1 unit x 1 unit represent pixels.
You can experiment with the algorithm by changing the slope of the line or the length.
Try the following examples:
(1) (x, y) = (12, 5) this pair is saved with the model, line is very jagged.
(2) (x, y) = (12, 12) line is better because slope = 45 degrees
(3) (x, y) = (60, 25) line is five times longer and hence the pixels, which are always 1 unit by 1 unit,
are relatively smaller and thus are a better representation of the line.
(4) Keep doubling the number of pixels and the individual pixels will eventually disappear
Ref: Hearn & Baker, Computer Graphics, Prentice Hall 1986
rjferg49 at sympatico.ca 01 Nov 00, 01 Jun 05
=g
#1
:c
.000001
:i
10
:g
global
:t
1
:y
No
=d
:c
E
:f
0
:v
E
:g
0.000001
:i
1000
:t
100
:p
0.000100
:r
5.00
:e
0
:d
1
:s
0
:n
0
:a
0
=s
:r
0
:v
%Tv,f,4,1,0,1,0
%Or,f,1,1,0,1,0
%Xl,f,0,0,0,2,0,88,88,871,583,160,713,-1,-1,0,0,4,-1,0,0,2,-16,400,34,0,0,0,161,Arial,4,10,21,31,98
%Xf,f,2,0,0,2,0,44,44,638,348,320,689,0,0,0,0,2,-1,0,0,2,-16,400,34,0,0,0,161,Arial,4,16,26,38,98
%Xp,f,0,0,0,2,0,110,110,893,605,0,689,-1,-1,0,0,5,-1,0,0,2,-16,400,34,0,0,0,161,Arial,3,13,25,99
%Xt,f,0,0,0,2,0,132,132,915,627,800,713,-1,-1,0,0,6,-1,0,0,2,-16,400,34,0,0,0,161,Arial,2,15,100
%Xn,f,0,0,0,2,0,154,154,937,649,480,713,-1,-1,0,0,7,-1,0,0,2,-16,400,34,0,0,0,161,Arial,2,15,100
%Xc,f,0,0,0,2,0,176,176,959,671,160,689,-1,-1,0,0,8,-1,0,0,2,-16,400,34,0,0,0,161,Arial,3,15,22,99
%Xr,f,1,1,0,2,0,22,22,616,326,320,713,0,0,0,0,1,-1,0,0,2,-16,400,34,0,0,0,161,Arial,2,6,100
%Xu,f,0,0,0,2,0,66,66,660,370,640,713,0,0,0,0,3,-1,0,0,2,-16,400,34,0,0,0,161,Arial,5,10,20,34,48,96
%Xm,f,0,0,0,0,0,44,44,638,348,0,713,0,0,0,0,9,-1,0,0,2,0,0,0,0,0,0,0,,0
%X ,f,0,0,0,0,0,0,0,805,493,-1,-1,-1,-1,0,5,5,0,0,0,1,-13,400,34,0,0,0,161,Arial,0
%Xv,f,4,1,0,2,0,22,22,827,515,-1,-1,0,0,0,0,0,-1,0,0,1,-16,400,34,0,0,0,161,Arial,6,6,16,24,34,44,95
%X ,f,10,0,0,2,0,44,44,849,537,-1,-1,0,0,0,1,8,0,0,0,1,-16,400,34,0,0,0,161,Arial,1,100
\G,0,1023,1566,1,-1,-1
\G,0,1023,1566,5,-1,-1
\G,0,2046,1566,1,-1,-1
\G,0,2046,1566,5,-1,-1
\C,0,2046,0,0,3