08 August 2011, 20:57 | #1 |
AMOS Extensions Developer
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 44
Posts: 1,924
|
Drawing a line...
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 |
08 August 2011, 22:35 | #2 |
move.l #$c0ff33,throat
Join Date: Dec 2005
Location: Berlin/Joymoney
Posts: 6,865
|
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.
|
09 August 2011, 00:04 | #3 | |
AMOS Extensions Developer
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 44
Posts: 1,924
|
Quote:
However, since I last saw the page some optimized example code has been added to it, including this example: Code:
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 |
|
09 August 2011, 20:50 | #4 |
Total Chaos forever!
Join Date: Aug 2007
Location: Waterville, MN, USA
Age: 49
Posts: 2,200
|
@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. |
10 August 2011, 00:00 | #5 | |
AMOS Extensions Developer
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 44
Posts: 1,924
|
Quote:
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 |
|
16 August 2011, 17:08 | #6 |
AMOS Extensions Developer
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 44
Posts: 1,924
|
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. Code:
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 |
16 August 2011, 22:25 | #7 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,856
|
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: 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 |
17 August 2011, 00:08 | #8 | |
Join Date: Jul 2008
Location: Sweden
Posts: 2,269
|
Quote:
|
|
17 August 2011, 19:05 | #9 | |||
AMOS Extensions Developer
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 44
Posts: 1,924
|
Quote:
Quote:
Quote:
Regards, Lonewolf10 |
|||
17 August 2011, 23:02 | #10 |
AMOS Extensions Developer
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 44
Posts: 1,924
|
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 )
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 |
18 August 2011, 08:06 | #11 |
gone
Join Date: Apr 2007
Location: completely gone
Posts: 1,596
|
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... |
18 August 2011, 19:40 | #12 | |
Join Date: Jul 2008
Location: Sweden
Posts: 2,269
|
Quote:
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. |
|
18 August 2011, 23:10 | #13 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,856
|
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. Last edited by Thorham; 18 August 2011 at 23:20. |
19 August 2011, 01:07 | #14 | |||||||||
AMOS Extensions Developer
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 44
Posts: 1,924
|
Quote:
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 Quote:
Quote:
Thanks Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Regards, Lonewolf10 |
|||||||||
19 August 2011, 01:29 | #15 |
Registered User
|
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
|
19 August 2011, 09:01 | #16 | |
gone
Join Date: Apr 2007
Location: completely gone
Posts: 1,596
|
Quote:
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. |
|
02 September 2011, 12:22 | #17 |
gone
Join Date: Apr 2007
Location: completely gone
Posts: 1,596
|
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:
Code:
.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 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. Last edited by pmc; 02 September 2011 at 15:44. Reason: Spotted a speedup myself :D |
02 September 2011, 17:40 | #18 | |
Registered User
Join Date: Nov 2010
Location: .
Posts: 380
|
Quote:
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 :-) |
|
02 September 2011, 18:14 | #19 |
gone
Join Date: Apr 2007
Location: completely gone
Posts: 1,596
|
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. |
02 September 2011, 20:19 | #20 | |
Join Date: Jul 2008
Location: Sweden
Posts: 2,269
|
Quote:
My inner loops are just this: Code:
.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 Last edited by Leffmann; 02 September 2011 at 20:25. |
|
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Old drawing of a book | absence | request.Other | 8 | 04 June 2012 17:19 |
Drawing circles | h0ffman | Coders. Asm / Hardware | 4 | 31 January 2012 22:25 |
Some questions about blitting and ordering of drawing | neoman | Coders. General | 23 | 29 October 2010 18:03 |
drawing tablet improvements | pbareges | request.UAE Wishlist | 2 | 10 April 2009 14:06 |
USB Drawing tablet support. | oldpx | request.UAE Wishlist | 3 | 28 July 2004 13:24 |
|
|