+DZ-Jay Posted May 10, 2012 Share Posted May 10, 2012 I posted this as a joke reply to a Rev post, but I was meaning to publish it anyway. It is an adaptation of the Bresenham Algorithm to drawing circles, translated to CP-1610 Assembly Language to draw a circle on the BACKTAB. I implemented it to draw sequentially concentric circles and create a "fade-in" transition for Christmas Carol, which resulted in a rather effective effect. I'm posting it freely here for anybody to use if they find value in it. There are two routines, DRAW_CIRCLE() and GET_BTAB_ADDRS(). The second one converts column and row coordinates into a pointer to the corresponding BACKTAB cell. It also checks for boundaries and returns an error in the Carry flag if the coordinates are out of bounds. This is useful to "clip" circles larger than the screen or positioned off center. This code will not win any awards for efficiency and style, but it works. Any suggestions to improve it are welcomed! I've attached a copy of the source in a the file "draw_circle.asm" but it is reproduced below in full. -dZ. draw_circle.asm ;* ======================================================================== *; ;* These routines are placed into the public domain by their author. All *; ;* copyright rights are hereby relinquished on the routines and data in *; ;* this file. -- James Pujals (DZ-Jay), 2012 *; ;* ======================================================================== *; ;; ======================================================================== ;; ;; DRAW_CIRCLE: ;; ;; Procedure to draw a circle on the BACKTAB by painting background cards ;; ;; with a solid colour. ;; ;; ;; ;; There are two entry points to this procedure: ;; ;; DRAW_CIRCLE: Draws a circle on the screen. ;; ;; ;; ;; DRAW_CIRCLE.1: Same as DRAW_CIRCLE, but expects the data record ;; ;; to be initiated. ;; ;; ;; ;; NOTE: The procedure uses a data record to store its state. This ;; ;; record must be defined in contiguous memory and has the ;; ;; following format: ;; ;; ;; ;; --------------------------------------------------- ;; ;; Origin X coordinate. 1 BYTE ;; ;; Origin Y coordinate. 1 BYTE ;; ;; Formatted word for background card. 2 BYTES ;; ;; --------------------------------------------------- ;; ;; ;; ;; Example: ;; ;; CIRCLE STRUCT 0 ;; ;; @@originX SCRATCH 1 ;; ;; @@originY SCRATCH 1 ;; ;; @@card SCRATCH 2 ;; ;; ENDS ;; ;; --------------------------------------------------- ;; ;; ;; ;; The algorithm used is a variation of Bresanham's Line Algorithm, often ;; ;; called the Mid-Point Circle Algorithm. ;; ;; ;; ;; This version was adapted from a compact implementation in C I found at: ;; ;; ;; ;; http://free.pages.at/easyfilter/bresenham.html ;; ;; http://members.chello.at/easyfilter/bresenham.html ;; ;; ;; ;; That page is attributed to and copyrighted by: ;; ;; Alosi Zingl, Vienna, Austria <easyfilter@free.pages.at> ;; ;; ------------------------------------------------------------------------ ;; ;; Bresenham's Algorithm applied to circles: ;; ;; Copyright © Alosi Zingl, Vienna, Austria ;; ;; ------------------------------------------------------------------------ ;; ;; ;; ;; void plotCircle(int xm, int ym, int r) ;; ;; { ;; ;; int x = -r, y = 0, err = 2-2*r; /* II. Quadrant */ ;; ;; do { ;; ;; setPixel(xm-x, ym+y); /* I. Quadrant */ ;; ;; setPixel(xm-y, ym-x); /* II. Quadrant */ ;; ;; setPixel(xm+x, ym-y); /* III. Quadrant */ ;; ;; setPixel(xm+y, ym+x); /* IV. Quadrant */ ;; ;; r = err; ;; ;; if (r > x) err += ++x*2+1; /* e_xy+e_x > 0 */ ;; ;; if (r <= y) err += ++y*2+1; /* e_xy+e_y < 0 */ ;; ;; } while (x < 0); ;; ;; } ;; ;; ;; ;; ------------------------------------------------------------------------ ;; ;; Translated to CP-1610 Assembly Language by: ;; ;; James Pujals (DZ-Jay) <dz-game@techunlimited.net> ;; ;; ------------------------------------------------------------------------ ;; ;; ;; ;; INPUT for DRAW_CIRCLE ;; ;; R5 Pointer to invocation record, followed by return address. ;; ;; Pointer to data record. 1 DECLE ;; ;; Circle origin (packed). 1 DECLE ;; ;; Card formatted word. 1 DECLE ;; ;; Radius (in cards). 1 BYTE ;; ;; ;; ;; INPUT for DRAW_CIRCLE.1 ;; ;; R0 Radius (in cards). ;; ;; R4 Pointer to data record. ;; ;; R5 Pointer to return address. ;; ;; ;; ;; OUTPUT ;; ;; R0 Trashed. ;; ;; R1 Trashed. ;; ;; R2 Trashed (zero). ;; ;; R3 Trashed. ;; ;; R4 Trashed. ;; ;; ======================================================================== ;; DRAW_CIRCLE PROC ;--------------------------------------- ; Retrieve arguments ;--------------------------------------- MVI@ R5, R4 ; Get pointer to data record REPEAT(2) MVI@ R5, R0 ; Get argument MVO@ R0, R4 ; \ SWAP R0 ; > Save in data record (double-byte data) MVO@ R0, R4 ; / ENDR MVI@ R5, R0 ; Get radius SUBI #4, R4 ; Reset pointer to data record @@1: BEGIN NEGR R0 ; \_ R2: x = -r MOVR R0, R2 ; / CLRR R3 ; R3: y = 0 SLL R0, 1 ; \_ R0: err = 2 - (2 * r) ADDI #2, R0 ; / ;--------------------------------------- ; Draw circle quadrants ;--------------------------------------- @@__next: PSHR R0 ; Save current err value ; I. Quadrant ;--------------------------------------- @@__quad1: MVI@ R4, R0 ; \_ R0: (xm - x) SUBR R2, R0 ; / MVI@ R4, R1 ; \_ R1: (ym + y) ADDR R3, R1 ; / ; Put tile in Q-I ;--------------------------------------- CALL GET_BTAB_ADDRS.TileCheck ; \ BC @@__quad2 ; | MVI@ R1, R0 ; | ANDI #STIC.cs_advance, R0 ; > put_tile(xm-x, ym+y, color) MOVR R4, R5 ; | SDBD ; | ADD@ R5, R0 ; | MVO@ R0, R1 ; / ; II. Quadrant ;--------------------------------------- @@__quad2: SUBI #2, R4 ; Reset pointer to data record MVI@ R4, R0 ; \_ R0: (xm - y) SUBR R3, R0 ; / MVI@ R4, R1 ; \ R1: (ym - x) SUBR R2, R1 ; / ; Put tile in Q-II ;--------------------------------------- CALL GET_BTAB_ADDRS.TileCheck ; \ BC @@__quad3 ; | MVI@ R1, R0 ; | ANDI #STIC.cs_advance, R0 ; > put_tile(xm-y, ym-x, color) MOVR R4, R5 ; | SDBD ; | ADD@ R5, R0 ; | MVO@ R0, R1 ; / ; III. Quadrant ;--------------------------------------- @@__quad3: SUBI #2, R4 ; Reset pointer to data record MVI@ R4, R0 ; \_ R0: (xm + x) ADDR R2, R0 ; / MVI@ R4, R1 ; \ R1: (ym - y) SUBR R3, R1 ; / ; Put tile in Q-III ;--------------------------------------- CALL GET_BTAB_ADDRS.TileCheck ; \ BC @@__quad4 ; | MVI@ R1, R0 ; | ANDI #STIC.cs_advance, R0 ; > put_tile(xm+x, ym-y, color) MOVR R4, R5 ; | SDBD ; | ADD@ R5, R0 ; | MVO@ R0, R1 ; / ; IV. Quadrant ;--------------------------------------- @@__quad4: SUBI #2, R4 ; Reset pointer to data record MVI@ R4, R0 ; \_ R0: (xm + y) ADDR R3, R0 ; / MVI@ R4, R1 ; \ R1: (ym + x) ADDR R2, R1 ; / ; Put tile in Q-IV ;--------------------------------------- CALL GET_BTAB_ADDRS.TileCheck ; \ BC @@__upd_xy ; | MVI@ R1, R0 ; | ANDI #STIC.cs_advance, R0 ; > put_tile(xm+y, ym+x, color) MOVR R4, R5 ; | SDBD ; | ADD@ R5, R0 ; | MVO@ R0, R1 ; / ; Update coordinates ;--------------------------------------- @@__upd_xy: SUBI #2, R4 ; Reset pointer to data record PULR R0 ; Get last known value for error MOVR R0, R5 ; r = err ;--------------------------------------- ; R0: err ; R2: x ; R3: y ; R5: r ;--------------------------------------- @@__chk_ex: CMPR R2, R5 ; if (r > x) // (e_xy + e_x) > 0 BLE @@__chk_ey ; INCR R2 ; \ MOVR R2, R1 ; | SLL R1, 1 ; > err += (++x * 2) + 1 INCR R1 ; | ADDR R1, R0 ; / @@__chk_ey: CMPR R3, R5 ; if (r <= y) // (e_xy + e_y) > 0 BGT @@__upd_err ; INCR R3 ; \ MOVR R3, R1 ; | SLL R1, 1 ; > err += (++y * 2) + 1 INCR R1 ; | ADDR R1, R0 ; / ; Updated error value and loop ;--------------------------------------- @@__upd_err: TSTR R2 ; \_ while (x < 0) BMI @@__next ; / RETURN ENDP The GET_BTAB_ADDRS() procedure uses the following constants to compute the address: BACKTAB STRUCT 0 @@Cols EQU 20 @@Rows EQU 12 @@Length EQU (@@Cols * @@Rows) ; Word cound (20 x 12 = 240 = $F0) @@Addrs EQU $0200 ; Base address ENDS ;; ======================================================================== ;; ;; GET_BTAB_ADDRS: ;; ;; Function to convert a coordinates to BACKTAB addresses. ;; ;; Formula: [(y / 8) * 20] + (x / 8) + BACKTAB.Addrs ;; ;; ;; ;; The function has three entry points: ;; ;; Screen : Converts MOB screen coordinates to BACKTAB address. ;; ;; Tile : Converts background tile coordinates to BACKTAB address.;; ;; TileCheck: Same as GET_BTAB_ADDRS.Tile, but with bounds-checks. ;; ;; ;; ;; INPUT for GET_BTAB_ADDRS.Screen ;; ;; R0 MOB X coordinate. ;; ;; R1 MOB Y coordinate. ;; ;; ;; ;; INPUT for GET_BTAB_ADDRS.Tile ;; ;; R0 Tile X coordinate. ;; ;; R1 Tile Y coordinate. ;; ;; ;; ;; INPUT for GET_BTAB_ADDRS.TileCheck ;; ;; R0 Tile X coordinate (X: 0 <= X < BACKTAB.Cols). ;; ;; R1 Tile Y coordinate (Y: 0 <= Y < BACKTAB.Rows). ;; ;; ;; ;; OUTPUT ;; ;; Carry 1: Out-of-bounds; 0: Success ;; ;; ;; ;; R0 Trashed. ;; ;; R1 Pointer to BACKTAB word (or zero on failed check). ;; ;; ======================================================================== ;; GET_BTAB_ADDRS PROC @@TileCheck: CMPI #BACKTAB.Cols, R0 ; BC @@__break ; if (x < 0) || (x >= Cols) break; CMPI #BACKTAB.Rows, R1 ; BNC @@Tile ; if (y >= 0) && (y <= Rows) pass; @@__break: CLRR R1 ; Return 0 on failure JR R5 ; ------------------------------------------------- ; NOTE: This look-up algorithm was adapted from one ; provided by Arnauld Chevallier, from the ; IntvProg mailing list, to convert screen ; coordinate into BACKTAB addresses. ; ------------------------------------------------- @@Screen: SLR R0, 2 ; \_ Convert X to BACKTAB column SLR R0, 1 ; / NOP ; Let the STIC assert BUSQ! SLR R1, 2 ; \_ Convert Y to BACKTAB row SLR R1, 1 ; / @@Tile: ADDI #@@__row_tbl, R1 MVI@ R1, R1 ADDR R0, R1 ; Adjust BACKTAB pointer by adding column number @@return: JR R5 ; ------------------------------------------------------------- ; Look-Up table to convert Y row number to BACKTAB pointer. ; ------------------------------------------------------------- @@__row_tbl: DECLE (BACKTAB.Addrs + 000), (BACKTAB.Addrs + 020), (BACKTAB.Addrs + 040) DECLE (BACKTAB.Addrs + 060), (BACKTAB.Addrs + 080), (BACKTAB.Addrs + 100) DECLE (BACKTAB.Addrs + 120), (BACKTAB.Addrs + 140), (BACKTAB.Addrs + 160) DECLE (BACKTAB.Addrs + 180), (BACKTAB.Addrs + 200), (BACKTAB.Addrs + 220) ENDP 3 Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 10, 2012 Author Share Posted May 10, 2012 And here's a screen test video of the "fade-in" effect in action, using only the DRAW_CIRCLE() routine called in a loop, decrementing the radius on each iteration. Two-tone Fade-In, in two passes: Fade-In 2 Pass Fast - Test 2.mov Fade-In with Halo effect: Fade-In 2 Halo - Test.mov 2 Quote Link to comment Share on other sites More sharing options...
catsfolly Posted May 10, 2012 Share Posted May 10, 2012 Seems like a well rounded piece of code. My head is spinning. Kind of a roundabout way to erase a screen... You sir, are guilty of circular logic. What goes around comes around. Those are all the circular comments I can think of right now. Thanks for posting more well commented sample code. (The only way my code will ever be this neat and clean looking will be if Joe disassembles and comments the rom...) Thanks, Catsfolly Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 10, 2012 Author Share Posted May 10, 2012 (edited) Seems like a well rounded piece of code. My head is spinning. Kind of a roundabout way to erase a screen... You sir, are guilty of circular logic. What goes around comes around. Those are all the circular comments I can think of right now. Thanks for posting more well commented sample code. (The only way my code will ever be this neat and clean looking will be if Joe disassembles and comments the rom...) Thanks, Catsfolly LOL! I'm very obsessive in my coding style and commenting, in any language. Sometimes I catch myself re-formatting something like a look-up table, over and over until the spacing and layout is just right. I'm just as obsessive with any of my creative works, including writing, drawing, and music editing. I don't mean to, but it just happens. I'd like to say it's Perfectionism, and sometimes it leads to some very good things of which I'm immensely proud; but other times I think it just borders on some sort of mania. Regarding the comments, I kind of need those. Some of these things do not come natural to me, so whenever I figure out how to do something, I need to leave all sort of cribs and hints around to explain to Future Me what the heck I was doing, especially in low-level code. -dZ. Edited May 10, 2012 by DZ-Jay Quote Link to comment Share on other sites More sharing options...
Rev Posted May 11, 2012 Share Posted May 11, 2012 Awesome wall of code!!!!!!!! That is all you got? Quote Link to comment Share on other sites More sharing options...
intvnut Posted May 12, 2012 Share Posted May 12, 2012 Seems like a well rounded piece of code. My head is spinning. Kind of a roundabout way to erase a screen... You sir, are guilty of circular logic. What goes around comes around. Tangentially, there's no sin in putting your own angle on things. It certainly puts the conversation on a different arc that might strike a chord with some. (The only way my code will ever be this neat and clean looking will be if Joe disassembles and comments the rom...) *chuckle* Quote Link to comment Share on other sites More sharing options...
catsfolly Posted May 22, 2012 Share Posted May 22, 2012 I made a colored square version of this program, because I thought it might be useful for explosion effects. Since Joe has already made some nice colored square routines, I just had to glue things together. Here is the code so far: [font=arial,helvetica,sans-serif][font=georgia,serif];; ======================================================================== ;; ;; DRAW_CS_CIRCLE: ;; ;; Procedure to draw a circle on the BACKTAB by drawing colored squares ;; ;; with a solid colour. ;; ;; ;; ;; There are two entry points to this procedure: ;; ;; DRAW_CIRCLE: Draws a circle on the screen. ;; ;; ;; ;; DRAW_CIRCLE.1: Same as DRAW_CIRCLE, but expects the data record ;; ;; to be initiated. ;; ;; ;; ;; NOTE: The procedure uses a data record to store its state. This ;; ;; record must be defined in contiguous memory and has the ;; ;; following format: ;; ;; ;; ;; --------------------------------------------------- ;; ;; Origin X coordinate. 1 BYTE ;; ;; Origin Y coordinate. 1 BYTE ;; ;; Formatted word for background card. 2 BYTES ;; ;; --------------------------------------------------- ;; ;; ;; ;; Example: ;; ;; CIRCLE STRUCT 0 ;; ;; @@originX SCRATCH 1 ;; ;; @@originY SCRATCH 1 ;; ;; @@card SCRATCH 2 ;; ;; ENDS ;; ;; --------------------------------------------------- ;; ;; ;; ;; The algorithm used is a variation of Bresanham's Line Algorithm, often ;; ;; called the Mid-Point Circle Algorithm. ;; ;; ;; ;; This version was adapted from a compact implementation in C I found at: ;; ;; ;; ;; http://free.pages.at/easyfilter/bresenham.html ;; ;; ;; ;; That page is attributed to and copyrighted by: ;; ;; Alosi Zingl, Vienna, Austria <easyfilter@free.pages.at> ;; ;; ------------------------------------------------------------------------ ;; ;; Bresenham's Algorithm applied to circles: ;; ;; Copyright © Alosi Zingl, Vienna, Austria ;; ;; ------------------------------------------------------------------------ ;; ;; ;; ;; void plotCircle(int xm, int ym, int r) ;; ;; { ;; ;; int x = -r, y = 0, err = 2-2*r; /* II. Quadrant */ ;; ;; do { ;; ;; setPixel(xm-x, ym+y); /* I. Quadrant */ ;; ;; setPixel(xm-y, ym-x); /* II. Quadrant */ ;; ;; setPixel(xm+x, ym-y); /* III. Quadrant */ ;; ;; setPixel(xm+y, ym+x); /* IV. Quadrant */ ;; ;; r = err; ;; ;; if (r > x) err += ++x*2+1; /* e_xy+e_x > 0 */ ;; ;; if (r <= y) err += ++y*2+1; /* e_xy+e_y < 0 */ ;; ;; } while (x < 0); ;; ;; } ;; ;; ;; ;; ------------------------------------------------------------------------ ;; ;; Translated to CP-1610 Assembly Language by: ;; ;; James Pujals (DZ-Jay) <dz-game@techunlimited.net> ;; ;; ------------------------------------------------------------------------ ;; ;; ;; ;; INPUT for DRAW_CIRCLE ;; ;; R5 Pointer to invocation record, followed by return address. ;; ;; Pointer to data record. 1 DECLE ;; ;; Circle origin (packed). 1 DECLE ;; ;; Card formatted word. 1 DECLE ;; ;; Radius (in cards). 1 BYTE ;; ;; ;; ;; INPUT for DRAW_CIRCLE.1 ;; ;; R0 Radius (in cards). ;; ;; R4 Pointer to data record. ;; ;; R5 Pointer to return address. ;; ;; ;; ;; OUTPUT ;; ;; R0 Trashed. ;; ;; R1 Trashed. ;; ;; R2 Trashed (zero). ;; ;; R3 Trashed. ;; ;; R4 Trashed. ;; ;; ======================================================================== ;; DRAW_CS_CIRCLE PROC ;--------------------------------------- ; Retrieve arguments ;--------------------------------------- MVI@ R5, R4 ; Get pointer to data record REPEAT(2) MVI@ R5, R0 ; Get argument MVO@ R0, R4 ; \ SWAP R0 ; > Save in data record (double-byte data) MVO@ R0, R4 ; / ENDR MVI@ R5, R0 ; Get radius SUBI #4, R4 ; Reset pointer to data record @@1: BEGIN NEGR R0 ; \_ R2: x = -r MOVR R0, R2 ; / CLRR R3 ; R3: y = 0 SLL R0, 1 ; \_ R0: err = 2 - (2 * r) ADDI #2, R0 ; / ;--------------------------------------- ; Draw circle quadrants ;--------------------------------------- @@__next: PSHR R0 ; Save current err value ; I. Quadrant ;--------------------------------------- @@__quad1: MVI@ R4, R0 ; \_ R0: (xm - x) SUBR R2, R0 ; / MVI@ R4, R1 ; \_ R1: (ym + y) ADDR R3, R1 ; / ; draw a colored square i Q-1 pshr r5 call PLOT_CS pulr r5 ; II. Quadrant ;--------------------------------------- @@__quad2: SUBI #2, R4 ; Reset pointer to data record MVI@ R4, R0 ; \_ R0: (xm - y) SUBR R3, R0 ; / MVI@ R4, R1 ; \ R1: (ym - x) SUBR R2, R1 ; / ; Put tile in Q-II ;--------------------------------------- ; draw a colored square i Q-1 pshr r5 call PLOT_CS pulr r5 ; III. Quadrant ;--------------------------------------- @@__quad3: SUBI #2, R4 ; Reset pointer to data record MVI@ R4, R0 ; \_ R0: (xm + x) ADDR R2, R0 ; / MVI@ R4, R1 ; \ R1: (ym - y) SUBR R3, R1 ; / ; Put tile in Q-III ;--------------------------------------- ; draw a colored square i Q-iii pshr r5 call PLOT_CS pulr r5 ; IV. Quadrant ;--------------------------------------- @@__quad4: SUBI #2, R4 ; Reset pointer to data record MVI@ R4, R0 ; \_ R0: (xm + y) ADDR R3, R0 ; / MVI@ R4, R1 ; \ R1: (ym + x) ADDR R2, R1 ; / ; Put tile in Q-IV ;--------------------------------------- pshr r5 call PLOT_CS pulr r5 ; Update coordinates ;--------------------------------------- @@__upd_xy: SUBI #2, R4 ; Reset pointer to data record PULR R0 ; Get last known value for error MOVR R0, R5 ; r = err ;--------------------------------------- ; R0: err ; R2: x ; R3: y ; R5: r ;--------------------------------------- @@__chk_ex: CMPR R2, R5 ; if (r > x) // (e_xy + e_x) > 0 BLE @@__chk_ey ; INCR R2 ; \ MOVR R2, R1 ; | SLL R1, 1 ; > err += (++x * 2) + 1 INCR R1 ; | ADDR R1, R0 ; / @@__chk_ey: CMPR R3, R5 ; if (r <= y) // (e_xy + e_y) > 0 BGT @@__upd_err ; INCR R3 ; \ MOVR R3, R1 ; | SLL R1, 1 ; > err += (++y * 2) + 1 INCR R1 ; | ADDR R1, R0 ; / ; Updated error value and loop ;--------------------------------------- @@__upd_err: TSTR R2 ; \_ while (x < 0) BMI @@__next ; / RETURN ENDP ;; ======================================================================== ;; ;; PLOT_CS: ;; ;; Procedure to plot a colored square - saves some registers and ;; ;; rearranges others, then calls Joe's PUTPIXELSC routine ;; PLOT_CS proc pshr r5 pshr r2 pshr r3 pshr r4 movr r1,r2 ; x coord movr r0,r1 ; y coord mvi@ r4,r0 ; color call PUTPIXELSC movr r1,r0 ; y coord movr r2,r1 ; x coord pulr r4 pulr r3 pulr r2 pulr pc endp[/font][/font] It looks like some pixels (in my blue background), never get touched.... Catsfolly 1 Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 22, 2012 Author Share Posted May 22, 2012 (edited) It looks like some pixels (in my blue background), never get touched.... Catsfolly Ah, yes, the concentric circle problem. I encountered that when I made my Fade-In effect. I solved it by doing the following: // (x, y) = origin. for r in (max..0) { // erase the previous circle by // drawing two circles around it. draw_circle(x-1, y, r+1); draw_circle(x+1, y, r+1); // draw new circle: draw_circle(x, y, r); } Since you're going inside-out, you'll need to draw the extra circles at "r-1". -dZ. Edited May 22, 2012 by DZ-Jay Quote Link to comment Share on other sites More sharing options...
intvnut Posted May 22, 2012 Share Posted May 22, 2012 It looks like some pixels (in my blue background), never get touched.... Yeah, that's a pretty common 'feature' of Bresenham circle drawing when you step through all of the integer radii. I remember encountering that in GW-BASIC (or BASICA, depending on the computer I was using at the time) eons ago. I believe what happens is that certain points along the circle get rounded up at some radii, and down for others, leaving a gap between two successive circle sizes. It's certainly annoying. And here's some fun for you: There's even a patent that describes this problem! http://www.google.com/patents/US5860925 Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 22, 2012 Author Share Posted May 22, 2012 (edited) It looks like some pixels (in my blue background), never get touched.... Yeah, that's a pretty common 'feature' of Bresenham circle drawing when you step through all of the integer radii. I remember encountering that in GW-BASIC (or BASICA, depending on the computer I was using at the time) eons ago. I believe what happens is that certain points along the circle get rounded up at some radii, and down for others, leaving a gap between two successive circle sizes. It's certainly annoying. Wouldn't it be that the error accumulation is different at varying radii, due to loss of precision? And here's some fun for you: There's even a patent that describes this problem! http://www.google.co...tents/US5860925 Oh sure, you can use a "gap interpolation method" to solve it. In my case, there's absolutely no other processing going on, so I thought I could take the hit of just re-drawing multiple circles. Edited May 22, 2012 by DZ-Jay Quote Link to comment Share on other sites More sharing options...
intvnut Posted May 22, 2012 Share Posted May 22, 2012 (edited) It looks like some pixels (in my blue background), never get touched.... Yeah, that's a pretty common 'feature' of Bresenham circle drawing when you step through all of the integer radii. I remember encountering that in GW-BASIC (or BASICA, depending on the computer I was using at the time) eons ago. I believe what happens is that certain points along the circle get rounded up at some radii, and down for others, leaving a gap between two successive circle sizes. It's certainly annoying. Wouldn't it be that the error accumulation is different at varying radii, due to loss of precision? It's an exact integer algorithm. There is no precision to lose. The algorithm plots the pixels that are under the midpoints of each arc between steps. Actually, I believe this image on Wikipedia illustrates, though, where the gaps come from nicely, and it's a slightly different explanation than I offered earlier. (I had worked this out years ago, but then forgot it.) The bright green "1st octant" arc is the primary arc -- others are just mirrors of it. the algorithm always steps by 1 in the y direction, and with each y step, optionally steps by 1 in the x direction. This follows the curve optimally, but only allows for one pixel in each horizontal slice. As you can see in the image above, though, there are horizontal slices for which the arc passes through two pixels. (In this case, that's just before the 45° point.) I believe that's the crux of the problem. Note that Bresenham's line draw algorithm has a similar property -- you step along the primary axis by equal steps every time, optionally stepping along the secondary axis to track the midpoints of the line segments. On a given 1px wide slice perpendicular to the primary axis, though, the ideal line may pass through two pixels, but Bresenham will only light up one -- the one that the midpoint of that line segment is over. Edited May 22, 2012 by intvnut Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 22, 2012 Author Share Posted May 22, 2012 It looks like some pixels (in my blue background), never get touched.... Yeah, that's a pretty common 'feature' of Bresenham circle drawing when you step through all of the integer radii. I remember encountering that in GW-BASIC (or BASICA, depending on the computer I was using at the time) eons ago. I believe what happens is that certain points along the circle get rounded up at some radii, and down for others, leaving a gap between two successive circle sizes. It's certainly annoying. Wouldn't it be that the error accumulation is different at varying radii, due to loss of precision? It's an exact integer algorithm. There is no precision to lose. The algorithm plots the pixels that are under the midpoints of each arc between steps. Actually, I believe this image on Wikipedia illustrates, though, where the gaps come from nicely, and it's a slightly different explanation than I offered earlier. (I had worked this out years ago, but then forgot it.) The bright green "1st octant" arc is the primary arc -- others are just mirrors of it. the algorithm always steps by 1 in the y direction, and with each y step, optionally steps by 1 in the x direction. This follows the curve optimally, but only allows for one pixel in each horizontal slice. As you can see in the image above, though, there are horizontal slices for which the arc passes through two pixels. (In this case, that's just before the 45° point.) I believe that's the crux of the problem. Note that Bresenham's line draw algorithm has a similar property -- you step along the primary axis by equal steps every time, optionally stepping along the secondary axis to track the midpoints of the line segments. On a given 1px wide slice perpendicular to the primary axis, though, the ideal line may pass through two pixels, but Bresenham will only light up one -- the one that the midpoint of that line segment is over. That was very helpful, indeed. Thank you! -dZ. Quote Link to comment Share on other sites More sharing options...
catsfolly Posted May 22, 2012 Share Posted May 22, 2012 It looks like some pixels (in my blue background), never get touched.... Catsfolly Ah, yes, the concentric circle problem. I encountered that when I made my Fade-In effect. I solved it by doing the following: // (x, y) = origin. for r in (max..0) { // erase the previous circle by // drawing two circles around it. draw_circle(x-1, y, r+1); draw_circle(x+1, y, r+1); // draw new circle: draw_circle(x, y, r); } Since you're going inside-out, you'll need to draw the extra circles at "r-1". -dZ. dZ - I tried this approach, and it works, but I didn't like the idea of recalculating the complete circle many times. So, I modified my plot_cs routine to plot 2 pixels, one in the original position, and one shifted to the right one pixel. It means my circles aren't completely round, but there are close enough for my explosive purposes... ;; ======================================================================== ;; ;; PLOT_CS: ;; ;; Procedure to plot a colored square - saves some registers and ;; ;; rearranges others, then calls Joe's PUTPIXELSC routine ;; PLOT_CS proc pshr r5 pshr r2 pshr r3 pshr r4 movr r1,r2 ; y coord movr r0,r1 ; x coord mvi@ r4,r0 ; color call PUTPIXELSC incr r1 ; draw again shifted one pixel right call PUTPIXELSC decr r1 ; restore r1 movr r1,r0 ; x coord movr r2,r1 ; y coord pulr r4 pulr r3 pulr r2 pulr pc endp This filled in the gaps: By drawing a trailing circle in black at r-1 radius, I can create expanding rings... Catsfolly 1 Quote Link to comment Share on other sites More sharing options...
catsfolly Posted May 22, 2012 Share Posted May 22, 2012 It looks like some pixels (in my blue background), never get touched.... Yeah, that's a pretty common 'feature' of Bresenham circle drawing when you step through all of the integer radii. I remember encountering that in GW-BASIC (or BASICA, depending on the computer I was using at the time) eons ago. I believe what happens is that certain points along the circle get rounded up at some radii, and down for others, leaving a gap between two successive circle sizes. It's certainly annoying. Wouldn't it be that the error accumulation is different at varying radii, due to loss of precision? It's an exact integer algorithm. There is no precision to lose. The algorithm plots the pixels that are under the midpoints of each arc between steps. Actually, I believe this image on Wikipedia illustrates, though, where the gaps come from nicely, and it's a slightly different explanation than I offered earlier. (I had worked this out years ago, but then forgot it.) The bright green "1st octant" arc is the primary arc -- others are just mirrors of it. the algorithm always steps by 1 in the y direction, and with each y step, optionally steps by 1 in the x direction. This follows the curve optimally, but only allows for one pixel in each horizontal slice. As you can see in the image above, though, there are horizontal slices for which the arc passes through two pixels. (In this case, that's just before the 45° point.) I believe that's the crux of the problem. Note that Bresenham's line draw algorithm has a similar property -- you step along the primary axis by equal steps every time, optionally stepping along the secondary axis to track the midpoints of the line segments. On a given 1px wide slice perpendicular to the primary axis, though, the ideal line may pass through two pixels, but Bresenham will only light up one -- the one that the midpoint of that line segment is over. Thanks for the clear explanation. Ideally, in Bresenham's line drawing, the program choses the most rapidly changing access as the "primary axis" which changes every time, and the line can pass through multiple pixels in a row along the other axis.... Catsfolly Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 22, 2012 Author Share Posted May 22, 2012 It looks like some pixels (in my blue background), never get touched.... Catsfolly Ah, yes, the concentric circle problem. I encountered that when I made my Fade-In effect. I solved it by doing the following: // (x, y) = origin. for r in (max..0) { // erase the previous circle by // drawing two circles around it. draw_circle(x-1, y, r+1); draw_circle(x+1, y, r+1); // draw new circle: draw_circle(x, y, r); } Since you're going inside-out, you'll need to draw the extra circles at "r-1". -dZ. dZ - I tried this approach, and it works, but I didn't like the idea of recalculating the complete circle many times. So, I modified my plot_cs routine to plot 2 pixels, one in the original position, and one shifted to the right one pixel. It means my circles aren't completely round, but there are close enough for my explosive purposes... ;; ======================================================================== ;; ;; PLOT_CS: ;; ;; Procedure to plot a colored square - saves some registers and ;; ;; rearranges others, then calls Joe's PUTPIXELSC routine ;; PLOT_CS proc pshr r5 pshr r2 pshr r3 pshr r4 movr r1,r2 ; y coord movr r0,r1 ; x coord mvi@ r4,r0 ; color call PUTPIXELSC incr r1 ; draw again shifted one pixel right call PUTPIXELSC decr r1 ; restore r1 movr r1,r0 ; x coord movr r2,r1 ; y coord pulr r4 pulr r3 pulr r2 pulr pc endp This filled in the gaps: By drawing a trailing circle in black at r-1 radius, I can create expanding rings... Catsfolly You know, I may just use that in P-Machinery. I like the increased resolution afforded by the Colored Squares mode. -dZ. Quote Link to comment Share on other sites More sharing options...
intvnut Posted May 22, 2012 Share Posted May 22, 2012 Thanks for the clear explanation. Ideally, in Bresenham's line drawing, the program choses the most rapidly changing access as the "primary axis" which changes every time, and the line can pass through multiple pixels in a row along the other axis.... That's exactly what Bresenham's line draw does. To get a line w/out gaps, it limits the effective slope to 1 or less by swapping X and Y axes if necessary so that you never move more than 1 unit on the secondary axis for every unit you move along the primary axis. If you remove some of the restrictions, you end up with a slightly more general algorithm known as an integer Digital Differential Analyzer. Throw in floating point, and you can be even more general. DDAs have all sorts of other applications, such as resampling a signal at a different sampling rate, for example, or implementing object velocities that aren't pure integer multiples of, say, the vertical retrace frequency. Fun fact: The guy that hired me into Texas Instruments (Karl Guttag) was actually friends with Jack Bresenham back in the late 70s/early 80s. One time, he was at a conference (SIGGRAPH or something like it) and Karl played a prank on someone else he knew. He asked them to explain how their code drew lines (that is, explain the Bresenham line draw algorithm).... to Bresenham himself. Once they got part way in, Karl interrupted the explanation and introduced Jack. :-) Quote Link to comment Share on other sites More sharing options...
intvnut Posted May 22, 2012 Share Posted May 22, 2012 This filled in the gaps: By drawing a trailing circle in black at r-1 radius, I can create expanding rings... Catsfolly Mesmerizing and cool! Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 22, 2012 Author Share Posted May 22, 2012 (edited) This filled in the gaps: By drawing a trailing circle in black at r-1 radius, I can create expanding rings... Catsfolly Mesmerizing and cool! And don't forget that the routine allows for shifting origin! (just make sure to ignore out-of-bounds coordinates in PLOT_CS() to clip at the edges.) -dZ. Edited May 22, 2012 by DZ-Jay Quote Link to comment Share on other sites More sharing options...
catsfolly Posted May 23, 2012 Share Posted May 23, 2012 This filled in the gaps: By drawing a trailing circle in black at r-1 radius, I can create expanding rings... Catsfolly Mesmerizing and cool! And don't forget that the routine allows for shifting origin! (just make sure to ignore out-of-bounds coordinates in PLOT_CS() to clip at the edges.) -dZ. Thanks for the reminder. Like this? Catsfolly Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 23, 2012 Author Share Posted May 23, 2012 Exactly! That looks very cool! Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted May 23, 2012 Author Share Posted May 23, 2012 Is it time to consider... Missile Command? With your routine and Joe's ray-drawing code, seems like it could work! Quote Link to comment Share on other sites More sharing options...
Rev Posted May 23, 2012 Share Posted May 23, 2012 Is it time to consider... Missile Command? With your routine and Joe's ray-drawing code, seems like it could work! Yeah, you guys stop messing around and start programming INTV Missile Command! I bet between all of you guys, you could port over the whole 'Atari' (2600) line up in less than a year. Quote Link to comment Share on other sites More sharing options...
+cmart604 Posted May 24, 2012 Share Posted May 24, 2012 This filled in the gaps: By drawing a trailing circle in black at r-1 radius, I can create expanding rings... Catsfolly Mesmerizing and cool! And don't forget that the routine allows for shifting origin! (just make sure to ignore out-of-bounds coordinates in PLOT_CS() to clip at the edges.) -dZ. Thanks for the reminder. Like this? Catsfolly Wow! Is that ever cool looking. Funny I instantly thought of Missile Command too. Quote Link to comment Share on other sites More sharing options...
intvnut Posted May 24, 2012 Share Posted May 24, 2012 This filled in the gaps: By drawing a trailing circle in black at r-1 radius, I can create expanding rings... Catsfolly Mesmerizing and cool! And don't forget that the routine allows for shifting origin! (just make sure to ignore out-of-bounds coordinates in PLOT_CS() to clip at the edges.) -dZ. Thanks for the reminder. Like this? Catsfolly Wow! Is that ever cool looking. Funny I instantly thought of Missile Command too. Imagine how much more it might look that way if you combined it with this... lines.asm Quote Link to comment Share on other sites More sharing options...
catsfolly Posted May 24, 2012 Share Posted May 24, 2012 Is it time to consider... Missile Command? With your routine and Joe's ray-drawing code, seems like it could work! First, It's YOUR circle drawing routine. I just wrote about 20 lines of "glue" code so the pixel drawing part of the code could call Joe's colored square routines. Second, it might be difficult to mix colored square graphics and normal color stack graphics seamlessly. When you set one pixel in a backtab card to colored square mode, the whole card is then in "colored squares" mode. It might be hard to confine all the explosions to backtab boundaries... Probably the most straightforward way to do Missile Command would be to do the whole thing in colored squares. The result would be a low res, "Fisher -Price" kind of version. Purists would be offended. But it might be fun... Catsfolly Quote Link to comment Share on other sites More sharing options...
Like us on Facebook
Follow us on Twitter
AtariAge on Instagram
Watch us on YouTube
Chat on Discord
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.