Drawing a line...

[Lonewolf10]

Hi folks,

A year or so back I managed to write a small program to draw a line using Bresenhams algorithm in AMOS Basic.

Is it possible to do it in 68000 assembler with the CPU without dealing with floating point numbers (e.g. for calculating the slope) and using lots of cycles, or can it only be done with the blitter?


Regards,
Lonewolf10

[StingRay]

Originally Posted by Lonewolf10

Is it possible to do it in 68000 assembler with the CPU without dealing with floating point numbers (e.g. for calculating the slope) and using lots of cycles, or can it only be done with the blitter?

Of course it is possible to code a Bresenham line drawer using the CPU only. And one of the advantages of the Bresenham algo is that it doesn't use any floating point operations. Just port your AMOS routine to 68000 and you're done.

[Lonewolf10]

Originally Posted by StingRay

Of course it is possible to code a Bresenham line drawer using the CPU only. And one of the advantages of the Bresenham algo is that it doesn't use any floating point operations. Just port your AMOS routine to 68000 and you're done.

That won't work, because the original routine I wrote (based on the example in the wiki article here) uses division to get the delta error value. That requires floating point maths to atleast 2 decimal places for it to work properly.


However, since I last saw the page some optimized example code has been added to it, including this example:

 function line(x0, y0, x1, y1)
   dx := abs(x1-x0)
   dy := abs(y1-y0) 
   if x0 < x1 then sx := 1 else sx := -1
   if y0 < y1 then sy := 1 else sy := -1
   err := dx-dy
 
   loop
     setPixel(x0,y0)
     if x0 = x1 and y0 = y1 exit loop
     e2 := 2*err
     if e2 > -dy then 
       err := err - dy
       x0 := x0 + sx
     end if
     if e2 <  dx then 
       err := err + dx
       y0 := y0 + sy 
     end if
   end loop

What does := mean?

If I can get that code working in AMOS, then I can port it to assembler


For those who are interested, I like having 2 methods for most things (e.g. blitter and CPU) as they can be used at the same time, with careful planning
As for why I need the line drawing routine? I am going to rotate 2 (2D) objects on screen, move them about and... you'll have to wait and see


Thanks Stingray, if not for your reply I would never have looked at the wiki article again


Regards,
Lonewolf10

[Samurai_Crow]

@Lonewolf10

The := is used in some languages to differentiate an assignment from a comparison.

The equivalent in AMOS would be to always use the optional LET keyword at the beginning of each assignment. The tokenizer always strips them away when you hit enter though, so there's no point in typing them. Just use a regular equals.

[Lonewolf10]

Originally Posted by Samurai_Crow

The := is used in some languages to differentiate an assignment from a comparison.

The equivalent in AMOS would be to always use the optional LET keyword at the beginning of each assignment. The tokenizer always strips them away when you hit enter though, so there's no point in typing them. Just use a regular equals.

Thanks.

It works perfectly in AMOS

The new routine also uses no divisions which has made it easy for me to convert it to asm, but I still have yet to test it out (will do that tomorrow).


Regards,
Lonewolf10

[Lonewolf10]

Urgh.

I tried converting the code from BASIC to assembler, but I am missing something. I managed to fix a few things (I think), but it still isn't working as desired. It plots the start and end of the line, but nothing inbetween and gets stuck in an infinite loop!

After spending a few days trying to work it out, I am now asking for some help. Can someone please point out what i am missing.

drawline:				;INPUT: d0=x1, d1=y1, d2=x2, d3=y2
					;	d4=width, a0=aptr	
	move.w	d0,coord_x1		;store start and end coords
	move.w	d1,coord_y1
	move.w	d2,coord_x2
	move.w	d3,coord_y2
.get_DX
	sub.w	d0,d2			;x2 - x1
	bmi	.neg_DX
.get_DY
	sub.w	d1,d3			;y2 - y1	
	bmi	.neg_DY
	bra	.get_SX
.neg_DX
	neg.w	d2			;-DX  ->  DX
	add.l	#65536,d2
	bra	.get_DY
.neg_DY
	neg.w	d3			;-DY  ->  DY
	add.l	#65536,d3
.get_SX
	move.w	d2,delta_x		;store X & Y delta
	move.w	d3,delta_y

	move.w	coord_x1,d0		;get X1 and X2
	move.w	coord_x2,d1
	cmp.w	d0,d1			;Is X1 < X2?
	blt	.SX_plus
	move.w	#-1,shift_x		;shift_X=-1
	bra	.get_SY
.SX_plus
	move.w	#1,shift_x		;shift_X=1	
.get_SY
	move.w	coord_y1,d0		;get Y1 and Y2
	move.w	coord_y2,d1
	cmp.w	d0,d1			;Is Y1 < Y2?
	blt	.SY_plus
	move.w	#-1,shift_y		;shift_Y=-1
	bra	.get_ERR
.SY_plus
	move.w	#1,shift_y		;shift_Y=1
.get_ERR
	sub.w	d3,d2			;ERR=DX-DY
	move.w	d2,err			;store ERR
.mainloop
	jsr	plot			;plot a pixel
	move.w	coord_x1,d0		;get current & ending coords
	move.w	coord_y1,d1
	move.w	coord_x2,d2
	move.w	coord_y2,d3
	cmp.w	d0,d2			;does x1 equal x2?
	beq	.exit1
.no_exit
	move.w	err,d4
	asl.w	#1,d4			;d4 * 2
	move.w	d4,e2
	move.w	delta_y,d5
	neg.w	d5			;\ delta_y  ->  -delta_y
	sub.l	#65536,d5		;/
	cmp.w	d4,d5
	bgt	.dec_ERR
.dec_ERR_return
	move.w	delta_x,d5
	move.w	e2,d6
	cmp	d6,d5		;was d5,d6
	blt	.add_ERR
*.add_ERR_return
	bra.s	.mainloop

.dec_ERR
	neg.w	d5
	add.l	#65536,d5		; -delta_y  ->  delta_y
	move.w	err,d4
	sub.w	d5,d4			;ERR=ERR-delta_Y
	move.w	d4,err			;store new ERR
	move.w	shift_x,d4	
	add.w	d4,d0			;X1=X1+shift_X
	move.w	d0,coord_x1		;store new coord_x1
	bra	.dec_ERR_return
.add_ERR
	move.w	err,d4
	move.w	delta_x,d5
	add.w	d5,d4			;ERR=ERR+delta_X
	move.w	d4,err			;store new ERR
	move.w	shift_y,d4
	add.w	d4,d1			;Y1=Y1+SY
	move.w	d1,coord_y1		;store new y1
	bra	.mainloop
.exit1
*	move.w	coord_y1,d1
*	move.w	coord_y2,d3
	cmp.w	d1,d3			;exit if y1 equals y2
	bne	.no_exit
.exit
	rts

coord_x1:	dc.w	0	;coords
coord_x2:	dc.w	0
coord_y1:	dc.w	0
coord_y2:	dc.w	0
delta_x:	dc.w	0	;deltas X & Y
delta_y:	dc.w	0
shift_x:	dc.w	0	;shifts X & Y
shift_y:	dc.w	0
err:		dc.w	0	;error values
e2:		dc.w	0


plot:					;INPUT: d0=X, d1=Y

*	mulu		#40,d1		;d1 (y-pos) x40 (as screen width=320,
*					;		 320 / 8 = 40)

	move.w		d1,d2		;\
	lsl.w		#3,d1		; | replaces mulu instruction
	lsl.w		#5,d2		; | for speed increase :)
	add.w		d2,d1		;/

	move.w		d0,d2		;d0 (x-pos) -> d2
	lsr.w		#3,d0		;d0 / 8 (get byte position for x-pos)
	not.b		d2		;invert bits 0-7 in d2
	andi.w		#7,d2		;mask out bits 3-7 (get bit position)
	add.w		d1,d0		;get complete offset in bytes
					;d0=byte position on screen
	lea.l		screen,a1	;bitplane address -> a1
	bset		d2,(a1,d0.w)	;set pixel
	rts

Regards,
Lonewolf10

[Thorham]

Here are a few pointers:

If you count the number of variables in the pseudo code, then you'll see that you can actually keep all the values in registers, which is much more convenient than storing and rereading them all the time. Some values do have to be stored, but you can calculate them in a register and keep them there, then just move/add/sub as needed.

Another thing to keep in mind is that you can use address registers for calculations in the same way as data registers when you're only adding or subtracting. For example, you can multiply a0 by 2 by doing add a0,a0.

Also, program flow is very important in assembly language. Try to keep it going down as much as possible, or things can become complicated. Try to write a line of the pseudo code in as few instructions as you can and without jumping back. Here's an example using the pseudo code:

;
;  dx := abs(x1-x0)
;  if x0 < x1 then sx := 1 else sx := -1
;

;
; d0=x0
; d2=x1
; d4=dx
; d6=sx
; 
.deltax_and_sx
	moveq	#1,d6
	move.l	d2,d4
	sub.l	d0,d4
	bgt	.l1
	neg.l	d4
	moveq	#-1,d6
.l1

[Leffmann]

Originally Posted by Lonewolf10

Urgh.

I tried converting the code from BASIC to assembler, but I am missing something. I managed to fix a few things (I think), but it still isn't working as desired. It plots the start and end of the line, but nothing inbetween and gets stuck in an infinite loop!

After spending a few days trying to work it out, I am now asking for some help. Can someone please point out what i am missing.

It's just a couple of logical errors: you've switched the operands around when you're comparing X0<X1, Y0<Y1, E2>-DY and E2<DX, and you're forgetting to put the X and Y coordinates in D0 and D1 before calling Plot.

[Lonewolf10]

Originally Posted by Leffmann

It's just a couple of logical errors: you've switched the operands around when you're comparing X0<X1, Y0<Y1, E2>-DY and E2<DX, and you're forgetting to put the X and Y coordinates in D0 and D1 before calling Plot.

Thanks, it worked perfectly after I sorted out the logical errors. Though I was getting a random first pixel drawn onto the screen, until I restored the X and Y coordinates into D0 and D1 before calling the plot routine

Originally Posted by Thorham

If you count the number of variables in the pseudo code, then you'll see that you can actually keep all the values in registers, which is much more convenient than storing and rereading them all the time. Some values do have to be stored, but you can calculate them in a register and keep them there, then just move/add/sub as needed.

I translated the BASIC routine as I went along, which resulted in the hard-to-follow code.

Originally Posted by Thorham

Another thing to keep in mind is that you can use address registers for calculations in the same way as data registers when you're only adding or subtracting. For example, you can multiply a0 by 2 by doing add a0,a0.

Also, program flow is very important in assembly language. Try to keep it going down as much as possible, or things can become complicated. Try to write a line of the pseudo code in as few instructions as you can and without jumping back.

Thanks for the tips. Now I have a working drawline routine, I'll try to write an optimized one based on your example


Regards,
Lonewolf10

[Lonewolf10]

I now have an optimized line routine, but it is slightly buggy. It would be hard to describe, so I have attached 2 pictures - "drawline" is working normally, and "drawline2_bug" is drawn using the optimized routine (below). Any ideas what is causing this? (other than my dodgy code )

drawline2:				;INPUT: d0=x1, d1=y1, d2=x2, d3=y2
					;	d4=width, a0=aptr	

.deltax_and_sx
	moveq	#1,d6			;sx = 1
	move.w	d2,d4			;d4 = x2
	sub.w	d0,d4			;delta_x = x2 - x1
	bgt.b	.deltay_and_sy
	neg.w	d4			;-delta_x  -> delta_x
	moveq	#-1,d6			;sx = -1
.deltay_and_sy
	moveq	#1,d7			;sy = 1
	move.w	d3,d5			;d5 = y2
	sub.w	d1,d5			;delta_y = y2 - y1
	bgt.b	.get_ERR
	neg.w	d5			;-delta_y  -> delta_y
	moveq	#-1,d7			;sy = -1
.get_ERR
	move.w	d4,a1			;a1 = delta_x
	sub.w	d5,a1			;a1 = delta_x - delta_y
					;a1=ERR
.mainloop
	movem.l	d0-d2/a1,-(sp)
	jsr	plot			;plot a pixel
	movem.l	(sp)+,d0-d2/a1
	cmp.w	d2,d0			;does x1 equal x2?
	beq	.exit1
.no_exit
	move.w	a1,a2			;\ a2 = ERR * 2
	add.w	a1,a2			;/
	neg.w	d5			;delta_y  ->  -delta_y
	cmp.w	d5,a2			;E2 > -delta_Y ?
	bgt.b	.dec_ERR
.dec_ERR_return
	cmp.w	d4,a2
	blt.b	.add_ERR		;E2 < delta_x ?
	bra.s	.mainloop

.dec_ERR
	neg.w	d5			;-delta_y  ->  delta_y
	sub.w	d5,a1			;ERR=ERR-delta_Y
	add.w	d6,d0			;X1=X1+shift_X
	bra.s	.dec_ERR_return

.add_ERR
	add.w	d4,a1			;ERR=ERR+delta_X
	add.w	d7,d1			;Y1=Y1+SY
	bra	.mainloop
.exit1
	cmp.w	d1,d3			;exit if y1 equals y2
	bne	.no_exit
.exit
	rts

Regards,
Lonewolf10

[pmc]

Have you tried putting routines like this into a debugger and single stepping them...? In my experience little errors can be found pretty quickly like that.

Oh, and for your optimised routine - it would be worth inlining the jsr plot. Would save the time of the jsr and rts for every pixel plotted...

[Leffmann]

Originally Posted by Lonewolf10

I now have an optimized line routine, but it is slightly buggy. It would be hard to describe, so I have attached 2 pictures - "drawline" is working normally, and "drawline2_bug" is drawn using the optimized routine (below). Any ideas what is causing this? (other than my dodgy code )

You're forgetting to restore delta_Y after you've negated it to compare E2 > -delta_Y, that's all.

This one is much faster than the first version

If I were to optimize this from here I would inline the plot routine like PMC said, then do away with the X and Y coordinates and instead keep track of a memory address and a bit value so you can plot the pixel right away without converting every time, and then split it into two smaller and faster routines, one for the wide lines with one pixel per column and one for the tall lines with one pixel per line, this way when you f.ex draw tall lines you can optimize away the calculation of SY and just increase or decrease the pixel address by 40.

[Thorham]

Lonewolf10, your new routine is much better and easier to follow as well

Another optimization you can do is making the loop a dbra loop. It's not hard, but I'll leave it up to you to figure it out Also, you don't have to save registers at all for calling pset, just free up some data registers. You can also neg delta-y once outside of the loop and be done with it. Just make sure to add delta-y instead of subbing it when you do.

There are some more optimization opportunities which have to do with program flow, but I'll leave it to you to figure out how.

[Lonewolf10]

Originally Posted by pmc

Have you tried putting routines like this into a debugger and single stepping them...? In my experience little errors can be found pretty quickly like that.

I spent most of the afternoon (I am off work this week ) trying to use Devpac's debugger. It's pretty neat, but once it stopped at the desired point I couldn't get back to workbench!!! I guess it's down to way my demo is written.
I did try using the WinUAE (2.0.1) debugger (shift+F12), but after stepping multiple times, it gave me exception errors (27 and 30) and lost comms with the main WinUAE screen causing the demo to carry on instead of being paused

Originally Posted by pmc

Oh, and for your optimised routine - it would be worth inlining the jsr plot. Would save the time of the jsr and rts for every pixel plotted...

Yup, I have now done that

Originally Posted by Leffmann

You're forgetting to restore delta_Y after you've negated it to compare E2 > -delta_Y, that's all.

Ahhh. Thanks for the pointer

Originally Posted by Leffmann

This one is much faster than the first version

Thanks

Originally Posted by Leffmann

If I were to optimize this from here I would inline the plot routine like PMC said, then do away with the X and Y coordinates and instead keep track of a memory address and a bit value so you can plot the pixel right away without converting every time, and then split it into two smaller and faster routines, one for the wide lines with one pixel per column and one for the tall lines with one pixel per line, this way when you f.ex draw tall lines you can optimize away the calculation of SY and just increase or decrease the pixel address by 40.

That sounds like a neat idea, I'll give that a try.

Originally Posted by Thorham

Lonewolf10, your new routine is much better and easier to follow as well

Thanks

Originally Posted by Thorham

Another optimization you can do is making the loop a dbra loop. It's not hard, but I'll leave it up to you to figure it out

I think I see how to do that (work out the length of the line and dbra until length is 0?).

Originally Posted by Thorham

Also, you don't have to save registers at all for calling pset, just free up some data registers.

I just did that as it was a quick and easy fix.

Originally Posted by Thorham

You can also neg delta-y once outside of the loop and be done with it. Just make sure to add delta-y instead of subbing it when you do.

Ok, will try that too.

Originally Posted by Thorham

There are some more optimization opportunities which have to do with program flow, but I'll leave it to you to figure out how

Yeah I know... avoid branching to and from .add_ERR and .dec_ERR


Regards,
Lonewolf10

[BuZz]

Originally Posted by Lonewolf10

I spent most of the afternoon (I am off work this week ) trying to use Devpac's debugger. It's pretty neat, but once it stopped at the desired point I couldn't get back to workbench!!! I guess it's down to way my demo is written.

for debugging non system stuff, the devpac debugger may not be the best suited. asmone/asmpro's debugger should do you much better, or a debugger like simbug2/beermon/hrtmon

[pmc]

Originally Posted by Lonewolf10

I spent most of the afternoon (I am off work this week ) trying to use Devpac's debugger. It's pretty neat, but once it stopped at the desired point I couldn't get back to workbench!!! I guess it's down to way my demo is written.

You'll have problems if you debug your demo code "as is" cos anything it does in terms of taking over the system or poking at registers that are probably best left alone when the system isn't taken over completely can give problems.

What I do in that situation is run only the piece of code I want to debug through the debugger. For your debugging here you would copy out your line draw routine and any data it needs into its own separate source code file and run that through the debugger. That way you don't get system problems but can still see what the code you're interested in is doing.

Hope that helps.

[pmc]

I had a little time today so just for fun (and the chance to learn something new too ) I knocked up my own version of a software (ie. no blitter) Bresenham line draw routine:

.draw_line:         move.w              d1,d4
                    move.w              d3,d6
                    sub.w               d4,d6
                    beq.b               .horizontal
                    bpl.b               .drw_ln_upwards
                    exg.l               d1,d3
                    exg.l               d0,d2
                    neg.w               d6

.drw_ln_upwards:    move.w              d0,d4
                    move.w              d2,d5
                    sub.w               d4,d5
                    beq.b               .vertical
                    bpl.b               .inc_x
                    movea.w             #-1,a3
                    subq.w              #1,d2
                    neg.w               d5
                    bra.b               .chk_deltas
.inc_x:             movea.w             #1,a3
                    addq.w              #1,d2

.chk_deltas:        cmp.w               d5,d6
                    bls.b               .dx_larger

                    move.w              d5,d4
                    add.w               d5,d5
                    move.w              d5,d7
                    sub.w               d6,d7
                    sub.w               d6,d4
                    add.w               d4,d4
                    move.b              #1,d6
                    bra.b               .plot_line

.dx_larger:         add.w               d6,d6
                    move.w              d6,d7
                    sub.w               d5,d7
                    add.w               d5,d5
                    move.w              d6,d4
                    sub.w               d5,d4
                    move.w              d6,d5
                    move.b              #0,d6
                    bra.b               .plot_line

.horizontal:        movea.l             screentwo_ptr(a5),a0
                    add.w               d1,d1
                    adda.w              0(a1,d1.w),a0
                    cmp.w               d2,d0
                    blt.b               .lft_to_rt
                    exg.l               d0,d2
.lft_to_rt:         movea.l             a0,a1
                    move.w              d0,d4
                    add.w               d4,d4
                    add.w               d4,d4
                    adda.w              0(a2,d4.w),a1
                    move.w              2(a2,d4.w),d4
                    or.w                d4,(a1)
                    addq.w              #1,d0
                    cmp.w               d2,d0
                    ble.b               .lft_to_rt
                    rts

.vertical:          movea.l             screentwo_ptr(a5),a0
                    add.w               d0,d0
                    add.w               d0,d0
                    adda.w              0(a2,d0.w),a0
                    cmp.w               d3,d1
                    blt.b               .dwn_to_up
                    exg.l               d1,d3
.dwn_to_up:         movea.l             a0,a3
                    move.w              d1,d4
                    add.w               d4,d4
                    adda.w              0(a1,d4.w),a3
                    move.w              2(a2,d0.w),d4
                    or.w                d4,(a3)
                    addq.w              #1,d1
                    cmp.w               d3,d1
                    ble.b               .dwn_to_up
                    rts

.plot_line:         movea.l             screentwo_ptr(a5),a0
                    move.w              d1,a4
                    add.w               d1,d1
                    adda.w              0(a1,d1.w),a0
                    move.w              d0,a6
                    add.w               d0,d0
                    add.w               d0,d0
                    adda.w              0(a2,d0.w),a0
                    move.w              2(a2,d0.w),d0
                    or.w                d0,(a0)
                    move.w              a4,d1
                    move.w              a6,d0
                    tst.w               d7
                    bmi.b               .error_neg
                    add.w               a3,d0
                    addq.w              #1,d1
                    add.w               d4,d7
                    bra.b               .check_eol
.error_neg:         tst.b               d6
                    bne.b               .adjust_y
                    add.w               a3,d0
                    bra.b               .update_error
.adjust_y:          addq.w              #1,d1
.update_error:      add.w               d5,d7
.check_eol:         tst.b               d6
                    bne.b               .check_y_eol
                    cmp.w               d0,d2
                    bne.b               .plot_line
                    bra.b               .line_drawn
.check_y_eol:       cmp.w               d1,d3
                    bne.b               .plot_line
.line_drawn:        rts

This code seems bug free in that all the lines I tested got drawn correctly.

It draws a worst case line (one corner of the screen to the other) in 127 raster lines on 68000. Doesn't matter from which corner to which corner the line's drawn, the performance is about the same.

The shorter the line, the quicker it's drawn (obviously) and horizontal and vertical lines are drawn quicker still.

Anyone got any suggestions as to whether there're obvious ways for the speed of the above to be improved further?

EDIT: did some testing and used this routine to draw the lines for a spinning wireframe 3d cube. It works but is slooooooow, as would be expected in comparison to the blitter. Also, there must be a problem with the horizontal and vertical shortcut routines. Although they worked OK in my pre-testing, they didn't work OK in my test wireframe cube routine. If I commented out the checks for horizontal and vertical lines though the routine still drew those lines OK under the normal plot_line routine.

[jman]

Originally Posted by pmc

You'll have problems if you debug your demo code "as is" cos anything it does in terms of taking over the system or poking at registers that are probably best left alone when the system isn't taken over completely can give problems.

What I do in that situation is run only the piece of code I want to debug through the debugger. For your debugging here you would copy out your line draw routine and any data it needs into its own separate source code file and run that through the debugger. That way you don't get system problems but can still see what the code you're interested in is doing.

Hi,

I'm slightly hijacking the thread as I have the same issue. Once you want to test-run some code that shuts down the system, of course I don't expect the DevPac debugger to be able to do anything once I 0wnz the system.

Duplicating the code in need of debugging on a separate file often can be cumbersome and not practical, example when you're debugging custom copperlists: the relevant piece of code is not debuggable per se, you have already shut down the system, you see what I mean?

I often end up blindly debugging the code reading over and over the same piece of code trying to figure out the issue, trial and error ... which sometimes is driving me crazy with 400 lines of ASM (include files excluded), I cannot figure out someone doing the same on bigger programs!

What is the correct approach to this issue?
Change IDE? I'd rather not to, I got accustomed to DevPac. Moreover, back in the day, DevPac developers must have sorted it out somehow.

Thanks :-)

[pmc]

Yes, you're right - debugging by single stepping pieces of code often is cumbersome (and tiresome too) but ultimately it's very productive. I've had times where, like you, I've stared at code thinking I know exactly how it works and not being able to spot any problems with it. However, on taking that same bit of code and single stepping it I've immediately seen, usually in under five minutes - sometimes even in thirty seconds - where the problem is and fixed it.

Blindly debugging code, in my opinion, is much more of a waste of time. It leads to frustration and after an hour of looking and finding nothing you'll begin to think it would've been quicker to spend the annoying ten minutes it would've taken to separate the code off and get it running in the debugger. At least that way you get to see what's *actually* happening and not just what you *think* is happening.

I've never done a routine and not been able to debug it and get it working by using Monam (the Devpac debugger) and *all* the code I do takes over the system. In my experience, it's just a question of thinking carefully about the correct ways to do your testing and testing smaller pieces of code separately. Use logic, think about what you're doing and narrow down where a bug can be and where it can't be by process of elimination - that's my best advice.

Of course, if you can't avoid letting your code take over the system before debugging, you can also use cartridges like Action Replay or HRTMon or even, under WinUAE, the built in debugger but personally I've never had to resort to those to fix my code.

[Leffmann]

Originally Posted by pmc

I had a little time today so just for fun (and the chance to learn something new too ) I knocked up my own version of a software (ie. no blitter) Bresenham line draw routine:

This code seems bug free in that all the lines I tested got drawn correctly.

It draws a worst case line (one corner of the screen to the other) in 127 raster lines on 68000. Doesn't matter from which corner to which corner the line's drawn, the performance is about the same.

The shorter the line, the quicker it's drawn (obviously) and horizontal and vertical lines are drawn quicker still.

Anyone got any suggestions as to whether there're obvious ways for the speed of the above to be improved further?

What I do is normalize all lines to draw from left to right, and keep the bit-number of the current pixel to set in a register and use BSET to plot each pixel, and use DX and DY as loop counters since they always say the exact number of pixels to plot. This way I can reduce all loop logic to a single DBF instruction.

My inner loops are just this:

.xloop    bset      d0, (a1)

          sub.w     d3, d1
          if_negative
           add.w    d6, d1
           add.w    d5, a1
          end_if

          dbf       d0, .nextx

          moveq     #7, d0
          add       #1, a1

.nextx    dbf       d2, .xloop

This is pretty quick on an A500, though the Blitter is still many times faster.