You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
196 lines
8.0 KiB
Plaintext
196 lines
8.0 KiB
Plaintext
:EARchaeopteryx says:
|
|
|
|
ÿÿf1!FUCK BRESENHAM!ÿÿf0
|
|
|
|
After that powerful title that could start world war III, you probably expect
|
|
something mindboggling... something cunning.... something like:
|
|
|
|
A replacement for the bresenham algorithm?!?!
|
|
|
|
For those of you that don't know what the hell that is, I should say: "And
|
|
you call yourself a coder!" ;-)
|
|
The bresenham algo relies on first calculating a few simple discriminants. In
|
|
the main loop these discriminants added to/subtracted from eachother. This is
|
|
quite effecient, because the loop only consists of some simple and fast
|
|
instructions.
|
|
|
|
Let's cut the crap and get to it. I found out a quite simple algorithm that
|
|
beats the old bresenham to it. It is based on the following incredibly simple
|
|
math >>>> steepness = dX/dY >>>> Where dX is the difference between the
|
|
x-coordinate of point 1 and point 2 of the line and dY is the same for the
|
|
y-coordinate.
|
|
|
|
OK, let's get to the code then, shall we? Here is it in dumb Pascal. And all
|
|
you speedfreaks: don't worry, I know this isn't neccessarily faster than
|
|
Bresenham, but the assembler version is!!
|
|
|
|
------------------------------ òsourcecode 1 ð---------------------------------
|
|
|
|
Procedure DrawLine(integer: X1, X2, Y1, Y2)
|
|
var
|
|
X, Y, dX, dY: integer;
|
|
steepness, d: real;
|
|
begin
|
|
dX:=X2-X1;
|
|
dY:=Y2-Y1;
|
|
if dX > dY then
|
|
{The loop for the situation where dX > dY}
|
|
begin
|
|
steepness:=dY/dX
|
|
d:=Y1;
|
|
for X:=X1 to X2 do
|
|
begin
|
|
PutPixel(X, Trunc(d), 1); {plot the pixel by using the integer part}
|
|
d:=d+steepness; {add steepness to get the new Y}
|
|
end;
|
|
end;
|
|
else
|
|
{The same loop for the situation where dX =< DY}
|
|
begin
|
|
steepness:=dX/dY;
|
|
d:=X1;
|
|
for Y:=Y1 to Y2 do
|
|
begin
|
|
PutPixel(Trunc(d), Y, 1) {plot the pixel by using the integer part}
|
|
d:=d+steepness; {add steepness to get the new X}
|
|
end;
|
|
end;
|
|
end;
|
|
|
|
--------------------------- òend of sourcecode 1 ð-----------------------------
|
|
|
|
There it was in Pascal. Ofcourse this still is slow. And I'm not talking
|
|
about the normal Pascal compilers that are crap, but about the instructions
|
|
used. There is a floating-point division at the initilializing part of the
|
|
procedure, so this is quite slow when the line we want to draw is short (i.e.
|
|
the main loop is done only a few times).
|
|
|
|
The good thing however, is that only very simple instructions are used in the
|
|
main loop (for..do statement). And ofcourse the main loop is executed
|
|
everytime a pixel is drawn so that mostly outweights the executing time of
|
|
the initializing part.
|
|
|
|
The big difference with bresenham algo is that this uses floating-point
|
|
numbers whereas bresenham only uses integers....
|
|
|
|
...What's that??......I hear a voice screaming from far away....
|
|
|
|
Y0u S0d!! th@t'5 th3 wh0le p0inT: N0t us1nG 3xpeNs1vE floating-point
|
|
op3raTi0n5!
|
|
|
|
Now that might be true, but in the assembler version for the beautiful 680x0
|
|
series of processors, we don't need that shit!! We can do it with fairly
|
|
cheap fixed point numbers! HARHAR!
|
|
|
|
The ñ< Trunc(d) >ð statement from the Pascal-source can easily be translated
|
|
into: ñ< swap d0 >ð on the 68000 :-) Comprendez? Non? Well.. Let's say you have
|
|
a 68000 register like d0. This contains 32 bits. Now you can divide this up
|
|
into two spaces: the upper 16 bits for the integer part and the lower 16 bits
|
|
for the fractational part. What the ñ< swap >ð instruction does is only swap
|
|
the upper part with lower part so you can use the integer part of the number!
|
|
|
|
This is more or less the principle my new routine relies on. It uses the same
|
|
technique as the Pascal algorithm, but only now with a bit of fixed point
|
|
techniques and further optimisations. Ofcourse we can't get rid of the
|
|
division instruction, but we can make a ñ< divu.w >ð out of this with some
|
|
effort.
|
|
|
|
The routine I'm about to show here has NO CLIPPING so don't do anything weird
|
|
with it and uses Falcon truecolor mode. (320 pixels wide!) It is a subroutine
|
|
that is called by putting some values in the data-/address-registers.
|
|
|
|
------------------------------- òSourcecode 2ð --------------------------------
|
|
|
|
* INPUT: d0.w: X1
|
|
* d1.w: Y1
|
|
* d2.w: X2
|
|
* d3.w: Y2
|
|
* d6.w: highcolor word (color of line)
|
|
* a0: start of screenaddress
|
|
DRAW_TRUELINE
|
|
move.l d2,d4
|
|
move.l d3,d5
|
|
sub.w d0,d2 ; / calculate the absolute
|
|
bpl.s .ok ; | value of the difference
|
|
neg.w d2 ; \ between X1 and X2
|
|
.ok sub.w d1,d3 ; / calculate the absolute
|
|
bpl.s .ok2 ; | value of the difference
|
|
neg.w d3 ; \ between Y1 and Y2
|
|
.ok2 cmp.w d2,d3
|
|
bhi.s .ver
|
|
* Part for dX > dY
|
|
cmp.w d0,d4 ; / Get the
|
|
bhs.s .do2 ; | heighest
|
|
exg d0,d4 ; | X and Y
|
|
exg d1,d5 ; \ in d4.w and d5.w
|
|
.do2 moveq #10,d2 ; \put #640
|
|
lsl.l #6,d2 ; /in d2.l (bytes in scanline)
|
|
sub.w d0,d4
|
|
sub.w d1,d5
|
|
add.l d0,d0
|
|
adda.l d0,a0
|
|
mulu.w d2,d1
|
|
adda.l d1,a0
|
|
tst.w d5
|
|
bpl.s .shit
|
|
neg.w d5 ; / make the
|
|
neg.l d2 ; | dX absolute
|
|
.shit swap d5 ; | and negate the scanline-
|
|
addq.w #1,d4 ; \ offset if needed
|
|
divu.w d4,d5 ; d5.w: steepness
|
|
moveq #0,d0
|
|
subq.w #1,d4 ; d4.w: number of times to loop
|
|
|
|
.lp2 add.w d5,d0 ; / check if you need to jump to
|
|
bcc.s .mov ; \ the next scanline
|
|
adda.l d2,a0 ; jump to the next scanline
|
|
.mov move.w d6,(a0)+ ; plot and go to next pixel
|
|
dbra d4,.lp2
|
|
rts
|
|
|
|
* Part for dX =< dY
|
|
.ver cmp.w d0,d4
|
|
bhs.s .do
|
|
exg d0,d4
|
|
exg d1,d5
|
|
.do moveq #10,d2 ; \put #640
|
|
lsl.l #6,d2 ; /in d2.l (bytes in scanline)
|
|
sub.w d0,d4
|
|
sub.w d1,d5
|
|
add.l d0,d0
|
|
adda.l d0,a0
|
|
mulu.w d2,d1
|
|
adda.l d1,a0 ; a0: address of first pixel
|
|
tst.w d5 ; / make the
|
|
bpl.s .shitt ; | dY absolute
|
|
neg.w d5 ; | and negate the scanline-
|
|
neg.l d2 ; \ offset if needed
|
|
.shitt swap d4
|
|
addq.w #1,d5
|
|
divu.w d5,d4 ; d4.w: steepness
|
|
moveq #0,d0
|
|
subq.w #1,d5 ; d5.w: number of times to loop
|
|
|
|
.lp add.w d4,d0 ; / check if you need to jump to
|
|
bcc.s .movie ; \ the next pixel in the scanline
|
|
addq.l #2,a0 ; go to next pixel in scanline
|
|
.movie move.w d6,(a0) ; plot the pixel
|
|
adda.l d2,a0 ; go to next scanline
|
|
dbra d5,.lp
|
|
rts
|
|
|
|
---------------------------- òend of sourcecode 2 ð----------------------------
|
|
|
|
Well.. There you have it then. I tried this and put it up against some of the
|
|
best versions of bresenham linerouts I had and it still came out victorious!
|
|
|
|
The future: This routine is almost as fast as it gets. There is only two
|
|
things you could do to make it even faster:
|
|
ó1) ðCode specific main loops for special steepnesses. ( steepness<1/8 ,
|
|
steepness<1/4, etc..) I really want to do this. This could boost the speed
|
|
by 20-30% (!)
|
|
ó2) ðDraw the line from both ends, so you decrease the number of loops by 50%!
|
|
But this looks a bit awkward if you ask me: you get a little knot in the
|
|
middle of the line. So this is fast, but not always pretty.
|
|
|
|
-------------------------------------==================== EarX/fUn ========= |