Skip to content

Instantly share code, notes, and snippets.

@johngirvin
Created September 1, 2020 10:31
Show Gist options
  • Save johngirvin/9eb0a48517dece99c28bfc3ca53b2971 to your computer and use it in GitHub Desktop.
Save johngirvin/9eb0a48517dece99c28bfc3ca53b2971 to your computer and use it in GitHub Desktop.
Render an n-sided convex polygon into an 8-bit chunky buffer (Amiga, 68000)
;
; Part of StarCrusaderPatch
; StarCrusaderPatch is (c) 1999 John Girvin, All Rights Reserved
; http://aminet.net/package/game/patch/StarCrusaderPa
;
;--------------------------------------------------------------------------------
_draw_poly:
; Render an n-sided convex polygon into an 8-bit chunky buffer
; Requires 68020+
; Entry:
; a2 =pointer to list of edge definitions x1,y1,x2,y2.w
; vertices assumed to lie within FB_WIDTH and FB_HEIGHT
; d4.w=colour pattern to fill poly with
; d5.w=number of edges-1
movem.l d0-7/a0-6,-(a7)
move.w d4,.dp_pattern ;Store pattern to fill poly with
; Determine X and Y bounds of polygon
; Y bounds are determined for whole polygon
; X bounds are determined for each Y coord within the Y-bounds
lea .dp_ymin(pc),a0 ;a0=y bounds buffer (ymin,ymax)
lea .dp_xbounds(pc),a1 ;a1=x bounds buffer
movem.w (a2)+,d0-3 ;d0=x1 d1=y1 d2=x2 d3=y2 of first edge
move.w d1,d6 ;ymin=y1
move.w d3,d7 ;ymax=y2
cmp.w d1,d3 ;Adjust order of ymin,ymax if required
bge.s .dpbl_start
exg d6,d7
bra.s .dpbl_start
.dp_boundsloop:
movem.w (a2)+,d0-3 ;d0=x1 d1=y1 d2=x2 d3=y2
; Determine if the either of the ends of this
; edge lie outside the current Y bounds
movem.w (a0),d6-7 ;d6=current ymin, d7=current ymax
; Check y1 against current Y bounds
cmp.w d1,d6 ;y1<ymin ?
ble.s .dpbl_y1ymin_done ;Skip if not
move.w d1,d6 ;Set new ymin=y1
bra.s .dpbl_y1done
.dpbl_y1ymin_done:
cmp.w d1,d7 ;y1>ymax ?
bge.s .dpbl_y1ymax_done ;Skip if not
move.w d1,d7 ;Set new ymax=y1
.dpbl_y1ymax_done:
.dpbl_y1done:
; Check y2 against current Y bounds
cmp.w d3,d6 ;y2<ymin ?
ble.s .dpbl_y2ymin_done ;Skip if not
move.w d3,d6 ;Set new ymin=y2
bra.s .dpbl_y2done
.dpbl_y2ymin_done:
cmp.w d3,d7 ;y2>ymax ?
bge.s .dpbl_y2ymax_done ;Skip if not
move.w d3,d7 ;Set new ymax=y2
.dpbl_y2ymax_done:
.dpbl_y2done:
.dpbl_start:
movem.w d6-7,(a0) ;Store updated ymin & ymax
; Determine the X bounds of the polygon for each
; Y coordinate affected by it. Do this by tracing
; along the current edge using the Bresenham 2D
; line algorithm and comparing each x coordinate
; to the currently stored xmin and xmax for the
; corresponding y coordinate, adjusting xmin/xmax
; as required
; Initialse values required for Bresenham
moveq #1,d6 ;d6=xstep
sub.w d0,d2 ;d2=x2-x1=dx
bpl.s .dpbl_gotdx ;Skip if dx>0 => x2>x1
neg.w d6 ;d6=xstep=-1
neg.w d2 ;d2=abs(dx)
.dpbl_gotdx:
moveq #1,d7 ;d7=ystep
sub.w d1,d3 ;d3=y2-y1=dy
bpl.s .dpbl_gotdy ;Skip if dy>0 => y2>y1
neg.w d7 ;d7=ystep=-1
neg.w d3 ;d3=abs(dy)
.dpbl_gotdy:
; We now have:
; d0=x d1=y d2=abs(dx) d3=abs(dy) d6=xstep d7=ystep a1=xbounds buffer
cmp.w d3,d2 ;X-major line?
ble.s .dpbl_ymajor ;Skip if no (dy>dx)
;---------- X-major line ie: dx>dy
tst.w d3 ;Horizontal line?
bne.s .dpblxm_not_horizontal ;Skip if not
;---------- Special x-major line: totally horizontal (dy=0)
; Compare x coords of either end of line with current
; x bounds for this y coord, and update the boundary
; coordinates if either x is outside
muls d6,d2 ;d2=sgn(dx)*abs(dx)=dx
add.w d0,d2 ;d2=x2 (once more!)
move.l 0(a1,d1.w*4),d3 ;d3=xmin[y],xmax[y]
cmp.w d3,d0 ;x1>xmax[y] ?
ble.s .dpblh_x1xmax_done ;Skip if not
move.w d0,d3 ;Set new xmax[y]=x1
.dpblh_x1xmax_done:
cmp.w d3,d2 ;x2>xmax[y] ?
ble.s .dpblh_x2xmax_done ;Skip if not
move.w d0,d3 ;Set new xmax[y]=x2
.dpblh_x2xmax_done:
swap d3 ;d3=xmax[y],xmin[y]
cmp.w d3,d0 ;x1<xmin[y] ?
bge.s .dpblh_x1xmin_done ;Skip if not
move.w d0,d3 ;Set new xmin[y]=x1
.dpblh_x1xmin_done:
cmp.w d3,d2 ;x2<xmin[y] ?
bge.s .dpblh_x2xmin_done ;Skip if not
move.w d0,d3 ;Set new xmin[y]=x2
.dpblh_x2xmin_done:
swap d3 ;d3=xmin[y],xmax[y]
move.l d3,0(a1,d1.w*4) ;Store new xmin[y],xmax[y]
dbf d5,.dp_boundsloop ;Loop for next edge
bra .dpbl_got_xbounds
;---------- Regular x-major line (dx>dy>0)
.dpblxm_not_horizontal:
move.w d2,d4 ;d4=dx=length of major axis
swap d5 ;Save boundsloop counter
move.w d2,d5 ;d5=dx/2=e (error variable)
lsr.w #1,d5
.dpblxm_loop:
; Compare x coord with current x bounds for this y coord,
; and update the boundary coordinates if x is outside
cmp.w 0(a1,d1.w*4),d0 ;x<xmin[y] ?
bge.s .dpblxm_xmin_done ;Skip if not
move.w d0,0(a1,d1.w*4) ;Set new xmin[y]=x
.dpblxm_xmin_done:
cmp.w 2(a1,d1.w*4),d0 ;x>xmax[y] ?
ble.s .dpblxm_xcmp_done ;Skip if not
move.w d0,2(a1,d1.w*4) ;Set new xmax[y]=x
.dpblxm_xcmp_done:
; Generate next x,y on line according
add.w d6,d0 ;d0=x=x+xstep
sub.w d3,d5 ;d5=e=e-2*dy
bge.s .dpblxm_next
add.w d4,d5 ;d5=e=e+2*dx
add.w d7,d1 ;d1=y=y+ystep
.dpblxm_next:
dbf d2,.dpblxm_loop
swap d5 ;Restore boundsloop counter
dbf d5,.dp_boundsloop ;Loop for next edge
bra.s .dpbl_got_xbounds
;---------- Y-major line ie: dy>dx
.dpbl_ymajor:
tst.w d2 ;Vertical line?
bne.s .dpblym_not_vertical ;Skip if not
;---------- Special y-major line: totally vertical (dx=0)
.dpblv_loop:
; Compare x coord with current x bounds for each y coord
; and update the boundary coordinates if x is outside
cmp.w 0(a1,d1.w*4),d0 ;x<xmin[y] ?
bge.s .dpblv_xmin_done ;Skip if not
move.w d0,0(a1,d1.w*4) ;Set new xmin[y]=x
.dpblv_xmin_done:
cmp.w 2(a1,d1.w*4),d0 ;x>xmax[y] ?
ble.s .dpblv_xcmp_done ;Skip if not
move.w d0,2(a1,d1.w*4) ;Set new xmax[y]=x
.dpblv_xcmp_done:
add.w d7,d1 ;d1=y=y+ystep
dbf d3,.dpblv_loop
dbf d5,.dp_boundsloop ;Loop for next edge
bra.s .dpbl_got_xbounds
;---------- Regular y-major line (dy>dx>0)
.dpblym_not_vertical:
move.w d3,d4 ;d4=dy=length of major axis
swap d5 ;Save boundsloop counter
move.w d3,d5 ;d5=dy/2=e (error variable)
lsr.w #1,d5
.dpblym_loop:
; Compare x coord with current x bounds for this y coord,
; and update the boundary coordinates if x is outside
cmp.w 0(a1,d1.w*4),d0 ;x<xmin[y] ?
bge.s .dpblym_xmin_done ;Skip if not
move.w d0,0(a1,d1.w*4) ;Set new xmin[y]=x
.dpblym_xmin_done:
cmp.w 2(a1,d1.w*4),d0 ;x>xmax[y] ?
ble.s .dpblym_xcmp_done ;Skip if not
move.w d0,2(a1,d1.w*4) ;Set new xmax[y]=x
.dpblym_xcmp_done:
; Generate next x,y on line according
add.w d7,d1 ;d1=y=y+ystep
sub.w d2,d5 ;d5=e=e-dx
bge.s .dpblym_next
add.w d4,d5 ;d5=e=e+dy
add.w d6,d0 ;d0=x=x+xstep
.dpblym_next:
dbf d3,.dpblym_loop
swap d5 ;Restore boundsloop counter
dbf d5,.dp_boundsloop ;Loop for next edge
;----------
.dpbl_got_xbounds:
; We now know the leftmost and rightmost x coordinate that
; the polygon will cover for every y coordinate that it covers.
; We loop for y between ymin and ymax, drawing a horizontal line
; between xmin[y],y and xmax[y],y and so rendering our polygon!
movem.w (a0),d6-7 ;d6=ymin d7=ymax
move.l #FB_WIDTH,d5 ;d5=constant=width of framebuffer in bytes
sub.w d6,d7 ;d7=ymax-ymin=height of polygon (no. of horiz lines to draw-1)
lea _framebuffer,a2 ;a2=address in framebuffer of (0,0)
lea 0(a1,d6.w*4),a0 ; a0=address in xbounds buffer of xmin[ymin],xmax[ymin]
mulu.w d5,d6 ;d6=offset in framebuffer of (0,ymin)
add.l d6,a2 ;a2=address in framebuffer of (0,ymin)
move.w .dp_pattern(pc),d4
ror.w #8,d4
.dp_render_yloop:
movem.w (a0),d0-1 ;d0=xmin[y], d1=xmax[y], a0=addr of xmin[y+1],xmax[y+1]
lea 0(a2,d0.w),a1 ;a1=address in framebuffer of LH end of line
sub.w d0,d1 ;d1=xmax-xmin=length of line-1
.dpry_render_xloop:
move.b d4,(a1)+
ror.w #8,d4
dbf d1,.dpry_render_xloop
move.l #FB_WIDTH<<16,(a0)+ ;Reset xmin[y] and xmax[y] for next poly
add.l d5,a2 ;a2=address in framebuffer of (0,y+1)
dbf d7,.dp_render_yloop ;Loop to draw next horizontal line
movem.l (a7)+,d0-7/a0-6
rts
;----------
CNOP 0,4
; Y bounds of polygon
.dp_ymin: dc.w 0
.dp_ymax: dc.w 0
; X bounds of polygon for every y coordinate
; Order is xmin,xmax.w
.dp_xbounds:
REPT FB_HEIGHT
dc.w FB_WIDTH,0
ENDR
.dp_pattern: dc.w 0
;--------------------------------------------------------------------------------
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment