GaryStanton414
asked on
A small problem with a line algorithm
Hi. Im sure this is a simple mathematical error, since I just jiggled around with a formula which worked for one type of line direction to get it to work with all line directions.
I know that this could be optimised with assembler code, but that is not my objective. Although some other optimisations for that pascal coding would be extremely welcome.
Anyway, enouth waffle...onto the problem :)
When I draw lines in the following ways this is what happens:
What is meant to happen What acctually happens
========================== ========== ========== =====
: :
: :
: : (same for mirror images of these)
: :
: :
: :
========================== ========== ========== =====
: :
: :
: : (same for mirror images of these)
: :
: :
: :
========================== ========== ========== ======
Here is the code:
procedure drawline (x1,y1,x2,y2 : word);
var
Count : word;
Error : integer;
dytimes2,dxtimes2 : Integer;
Begin
if (x1 > x2) and (y1 < y2) then
Begin
dxtimes2 := (x1-x2) SHL 1;
dytimes2 := (y2-y1) SHL 1;
Error := x2-x1;
if dxtimes2 > dytimes2 then
Begin
for count := x1 downto x2 do
Begin
putpixel(count,y1,15);
Error := Error + dytimes2;
if Error > 0 then
Begin
Error := Error - dxtimes2;
y1 := y1 + 1;
End
End;
End
Else
Begin
for count := y1 to y2 do {ONE PROBLEM IS IN THIS LOOP********************** ********** ***}
Begin {************************* ********** ********** ********** ****}
putpixel(x1,count,15); {************************* ********** ********** ********** ****}
Error := Error + dxtimes2; {************************* ********** ********** ********** ****}
if Error > 0 then {************************* ********** ********** ********** ****}
Begin {************************* ********** ********** ********** ****}
Error := Error - dytimes2; {************************* ********** ********** ********** ****}
x1 := x1 - 1; {************************* ********** ********** ********** ****}
End {************************* ********** ********** ********** ****}
End; {************************* ********** ********** ********** ****}
End;
End
Else
Begin
if (x1 > x2) and (y1 > y2) then
Begin
dxtimes2 := (x1-x2) SHL 1;
dytimes2 := (y1-y2) SHL 1;
Error := x2-x1;
if dxtimes2 > dytimes2 then
Begin
for count := x1 downto x2 do
Begin
putpixel(count,y1,15);
Error := Error + dytimes2;
if Error > 0 then
Begin
Error := Error - dxtimes2;
y1 := y1 - 1;
End
End;
End
Else
Begin
for count := y1 downto y2 do {ONE PROBLEM IS IN THIS LOOP********************** ********** ***}
Begin {************************* ********** ********** ********** **}
putpixel(x1,count,15); {************************* ********** ********** ********** **}
Error := Error + dxtimes2; {************************* ********** ********** ********** **}
if Error > 0 then {************************* ********** ********** ********** **}
Begin {************************* ********** ********** ********** **}
Error := Error - dytimes2; {************************* ********** ********** ********** **}
x1 := x1 - 1; {************************* ********** ********** ********** **}
End {************************* ********** ********** ********** **}
End; {************************* ********** ********** ********** **}
End;
End
Else
Begin
if (x1 < x2) and (y1 < y2) then
Begin
dxtimes2 := (x2-x1) SHL 1;
dytimes2 := (y2-y1) SHL 1;
Error := x1-x2;
if dxtimes2 > dytimes2 then
Begin
for count := x1 to x2 do
Begin
putpixel(count,y1,15);
Error := Error + dytimes2;
if Error > 0 then
Begin
Error := Error - dxtimes2;
y1 := y1 + 1;
End
End;
End
Else
Begin
for count := y1 to y2 do {ONE PROBLEM IS IN THIS LOOP********************** ********** ***}
Begin {************************* ********** ********** ********** **}
putpixel(x1,count,15); {************************* ********** ********** ********** **}
Error := Error + dxtimes2; {************************* ********** ********** ********** **}
if Error > 0 then {************************* ********** ********** ********** **}
Begin {************************* ********** ********** ********** **}
Error := Error - dytimes2; {************************* ********** ********** ********** **}
x1 := x1 + 1; {************************* ********** ********** ********** **}
End {************************* ********** ********** ********** **}
End; {************************* ********** ********** ********** **}
End;
End
Else
Begin
if (x1 < x2) and (y1 > y2) then
Begin
dxtimes2 := (x2-x1) SHL 1;
dytimes2 := (y1-y2) SHL 1;
Error := x1-x2;
if dxtimes2 > dytimes2 then
Begin
for count := x1 to x2 do
Begin
putpixel(count,y1,15);
Error := Error + dytimes2;
if Error > 0 then
Begin
Error := Error - dxtimes2;
y1 := y1 - 1;
End
End;
End
Else
Begin
for count := y1 downto y2 do {ONE PROBLEM IS IN THIS LOOP********************** ********** ***}
Begin {************************* ********** ********** ********** **}
putpixel(x1,count,15); {************************* ********** ********** ********** **}
Error := Error + dxtimes2; {************************* ********** ********** ********** **}
if Error > 0 then {************************* ********** ********** ********** **}
Begin {************************* ********** ********** ********** **}
Error := Error - dytimes2; {************************* ********** ********** ********** **}
x1 := x1 + 1; {************************* ********** ********** ********** **}
End {************************* ********** ********** ********** **}
End; {************************* ********** ********** ********** **}
End;
End;
End;
End;
End;
End;
I know it is long :) But after a few if statments are executed there are just plotting to get on with. I have marked the problem parts.
Thanks for any help
I know that this could be optimised with assembler code, but that is not my objective. Although some other optimisations for that pascal coding would be extremely welcome.
Anyway, enouth waffle...onto the problem :)
When I draw lines in the following ways this is what happens:
What is meant to happen What acctually happens
==========================
: :
: :
: : (same for mirror images of these)
: :
: :
: :
==========================
: :
: :
: : (same for mirror images of these)
: :
: :
: :
==========================
Here is the code:
procedure drawline (x1,y1,x2,y2 : word);
var
Count : word;
Error : integer;
dytimes2,dxtimes2 : Integer;
Begin
if (x1 > x2) and (y1 < y2) then
Begin
dxtimes2 := (x1-x2) SHL 1;
dytimes2 := (y2-y1) SHL 1;
Error := x2-x1;
if dxtimes2 > dytimes2 then
Begin
for count := x1 downto x2 do
Begin
putpixel(count,y1,15);
Error := Error + dytimes2;
if Error > 0 then
Begin
Error := Error - dxtimes2;
y1 := y1 + 1;
End
End;
End
Else
Begin
for count := y1 to y2 do {ONE PROBLEM IS IN THIS LOOP**********************
Begin {*************************
putpixel(x1,count,15); {*************************
Error := Error + dxtimes2; {*************************
if Error > 0 then {*************************
Begin {*************************
Error := Error - dytimes2; {*************************
x1 := x1 - 1; {*************************
End {*************************
End; {*************************
End;
End
Else
Begin
if (x1 > x2) and (y1 > y2) then
Begin
dxtimes2 := (x1-x2) SHL 1;
dytimes2 := (y1-y2) SHL 1;
Error := x2-x1;
if dxtimes2 > dytimes2 then
Begin
for count := x1 downto x2 do
Begin
putpixel(count,y1,15);
Error := Error + dytimes2;
if Error > 0 then
Begin
Error := Error - dxtimes2;
y1 := y1 - 1;
End
End;
End
Else
Begin
for count := y1 downto y2 do {ONE PROBLEM IS IN THIS LOOP**********************
Begin {*************************
putpixel(x1,count,15); {*************************
Error := Error + dxtimes2; {*************************
if Error > 0 then {*************************
Begin {*************************
Error := Error - dytimes2; {*************************
x1 := x1 - 1; {*************************
End {*************************
End; {*************************
End;
End
Else
Begin
if (x1 < x2) and (y1 < y2) then
Begin
dxtimes2 := (x2-x1) SHL 1;
dytimes2 := (y2-y1) SHL 1;
Error := x1-x2;
if dxtimes2 > dytimes2 then
Begin
for count := x1 to x2 do
Begin
putpixel(count,y1,15);
Error := Error + dytimes2;
if Error > 0 then
Begin
Error := Error - dxtimes2;
y1 := y1 + 1;
End
End;
End
Else
Begin
for count := y1 to y2 do {ONE PROBLEM IS IN THIS LOOP**********************
Begin {*************************
putpixel(x1,count,15); {*************************
Error := Error + dxtimes2; {*************************
if Error > 0 then {*************************
Begin {*************************
Error := Error - dytimes2; {*************************
x1 := x1 + 1; {*************************
End {*************************
End; {*************************
End;
End
Else
Begin
if (x1 < x2) and (y1 > y2) then
Begin
dxtimes2 := (x2-x1) SHL 1;
dytimes2 := (y1-y2) SHL 1;
Error := x1-x2;
if dxtimes2 > dytimes2 then
Begin
for count := x1 to x2 do
Begin
putpixel(count,y1,15);
Error := Error + dytimes2;
if Error > 0 then
Begin
Error := Error - dxtimes2;
y1 := y1 - 1;
End
End;
End
Else
Begin
for count := y1 downto y2 do {ONE PROBLEM IS IN THIS LOOP**********************
Begin {*************************
putpixel(x1,count,15); {*************************
Error := Error + dxtimes2; {*************************
if Error > 0 then {*************************
Begin {*************************
Error := Error - dytimes2; {*************************
x1 := x1 + 1; {*************************
End {*************************
End; {*************************
End;
End;
End;
End;
End;
End;
I know it is long :) But after a few if statments are executed there are just plotting to get on with. I have marked the problem parts.
Thanks for any help
ASKER
No. This is an efficient algorithm. Using real numbers for calcualtions is slow and inefficient. Then add rounding on top of that and it becomes more inefficient. This algorithm is designed for speed. Notice it also only uses addition and subtraction and a bit shift which are fast. There is no slow division or multiplicatio involved.
So I am looking for why this algorithm has the slight problem. Any optimisations which use the same technique are welcome but I am not looking for another method. Using the same method with for example less code but no loss in efficientcy is very welcome indeed.
Thanks
So I am looking for why this algorithm has the slight problem. Any optimisations which use the same technique are welcome but I am not looking for another method. Using the same method with for example less code but no loss in efficientcy is very welcome indeed.
Thanks
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Brilliant Thanks
Instead of using the Error variable, you can calculate the point position using Real type. Then you can round the result. So there is no need for additional Error variable.
dx and dy could be calculated more precisely if declared as Real.
This will give you far more powerful control over point positions.