Render an n-sided convex polygon into an 8-bit chunky buffer (Amiga, 68000)

draw_poly.s

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

;--------------------------------------------------------------------------------