>Silver Surfer: Added category

2009-05-02T17:06:37Z

Added category

← Older revision		Revision as of 13:06, 2 May 2009
Line 194:		Line 194:

	-------------------------------------==================== EarX/fUn =========		-------------------------------------==================== EarX/fUn =========
			[[Category:Programming]]

>Simonsunnyboy at 09:13, 26 July 2008

2008-07-26T09:13:20Z

>Simonsunnyboy at 09:12, 26 July 2008

2008-07-26T09:12:06Z

New page

Wikified by Simon Sunnyboy / Paradize

== Fast line drawing algorithm ==
by Earx/Lienout

'''FUCK BRESENHAM!'''

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===
<pre>
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;
</pre>

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===
<pre>
* 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
</pre>

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 =========

← Older revision		Revision as of 05:13, 26 July 2008
Line 73:		Line 73:
	the initializing part.		the initializing part.

	The big difference with bresenham algo is that this uses floating-point		''The big difference with bresenham algo is that this uses floating-point
	numbers whereas bresenham only uses integers....		numbers whereas bresenham only uses integers....''

	...What's that??......I hear a voice screaming from far away....		...What's that??......I hear a voice screaming from far away....
Line 85:		Line 85:
	cheap fixed point numbers! HARHAR!		cheap fixed point numbers! HARHAR!

	The ~~ï¿½~~< Trunc(d) >~~ï¿½~~ statement from the Pascal-source can easily be translated		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		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		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		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		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!		the upper part with lower part so you can use the integer part of the number!

Line 95:		Line 95:
	technique as the Pascal algorithm, but only now with a bit of fixed point		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		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		division instruction, but we can make a < divu.w > out of this with some
	effort.		effort.

Line 188:		Line 188:
	The future: This routine is almost as fast as it gets. There is only two		The future: This routine is almost as fast as it gets. There is only two
	things you could do to make it even faster:		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% (!)		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% (!)

Earx fast line algorithm - Revision history

>Silver Surfer: Added category

>Simonsunnyboy at 09:13, 26 July 2008

>Simonsunnyboy at 09:12, 26 July 2008