        .width    132
;-------------------------------------------------------------------------;
;                                  TIGA                                   ;
;        Copyright (c) 1987-1990  Texas Instruments Incorporated.         ;
;			   All Rights Reserved				  ;
;-------------------------------------------------------------------------;
;   TIGA - Graphics Manager Extension                                     ;
;-------------------------------------------------------------------------;
;                                                                         ;
; fill_convex and patnfill_convex functions                               ;
;                                                                         ;
;   The fill_convex function draws a solid-filled polygon given a list    ;
;   of vertices defining the polygon.  The patnfill_convex function is    ;
;   similar, but draws a pattern-filled polygon.  In order to be drawn    ;
;   correctly, the polygon must be convex (no concavities).  The routine  ;
;   will draw the polygon only if (1) it has at least three vertices,	  ;
;   and (2) the vertices are ordered in the clockwise direction.  The	  ;
;   meaning of the term "clockwise" in this context is based on the       ;
;   convention that x increases from left to right and y increases from   ;
;   top to bottom.  The routine always assumes that an edge connects the  ;
;   first and last vertices specified.					  ;
;									  ;
;   The function requires two input arguments.  The number of vertices    ;
;   (really the number of x-y coordinate pairs) defining the polygon is   ;
;   specified in the first argument, n.  The second argument is a         ;
;   pointer to the array ptlist[], which contains the x and y coordinates ;
;   of the polygon's vertices.  Each 32-bit array element consists of an  ;
;   16-bit integer x value followed by a 16-bit integer y value, both of  ;
;   which are specified relative to the drawing origin. 		  ;
;                                                                         ;
;   The polygon is drawn only if its front side is visible (facing        ;
;   toward the screen).  If the back side of the polygon is facing the    ;
;   screen, the polygon is not drawn.  The back face test is done by	  ;
;   comparing vertices n-2, n-1 and 0 to determine whether the polygon	  ;
;   vertices are specified in clockwise (visible) or counterclockwise	  ;
;   (back face) order.	Should the three vertices be collinear, the back  ;
;   face test will be made using vertices n-1, 0 and 1, and so on.  If	  ;
;   all the vertices are collinear, the polygon is invisible.		  ;
;                                                                         ;
;   In 3D applications, rounding off real x and y coordinates to the	  ;
;   nearest integer values may occasionally cause long, thin polygons to  ;
;   become twisted such that they are partially forward-facing, and	  ;
;   partially back-facing.  The routine contains an inner loop test to	  ;
;   detect this condition and return immediately.			  ;
;-------------------------------------------------------------------------;
; Usage:  fill_convex(n, ptlist)                                          ;
;         patnfill_convex(n, ptlist)                                      ;
;                                                                         ;
; Description of stack arguments:                                         ;
;   typedef struct { short x, y; } POINT;  /* point in 2D space */	  ;
;   short n;		    /* number of vertices in polygon */ 	  ;
;   POINT ptlist[];	    /* x-y coordinates of vertices */		  ;
;                                                                         ;
; Returned in register A8:  void (nothing)				  ;
;                                                                         ;
; Registers altered:  A8                                                  ;
;-------------------------------------------------------------------------;
; Revision history:                                                       ;
;   06/24/87...Original version written.....................J.R. Van Aken ;
;   09/18/88...Removed polygon list and backface test.			  ;
;	       Globals accessed thru env struct.			  ;
;	       Added TIGA direct-mode support.....................W.S.Egr ;
;   09/26/88...Removed connectivity assumption....................W.S.Egr ;
;   12/02/88...Replaced backface test........................Graham Short ;
;   07/24/89...Added 34020 support...............................A. Sharp ;
;   09/21/89...Fixed bug in pattern reg usage on 34010...........A. Sharp ;
;   03/20/90...First argument changed from n+1 to n.........J.R. Van Aken ;
;   05/14/90...Added check for x1>x2 to 34020 TFILL loop....J.R. Van Aken ;
;-------------------------------------------------------------------------;
        .title    'fill convex polygon'
        .file     'convex.asm'
	.include  gsptypes.inc	      ;structure type definitions
	.include  gspglobs.inc	      ;global variable definitions
	.include  oem.inc	      ;34010/34020 code switch
;
;  DECLARE GLOBAL FUNCTION NAME
;
        .globl    _fill_convex,_patnfill_convex ;C-packet entry points
        .globl    _dm_fill_convex,_dm_patnfill_convex ;direct-mode entry points
;
;   Register definitions
;
StartPL .set      A11                 ;start of ptlist[]
xyOrg   .set      A12                 ;drawing origin x-y displacements
EndPL   .set      A13                 ;end of ptlist[]
;
;   C-Packet SUBROUTINE ENTRY POINTS (_fill_convex and _patnfill_convex)
;
_fill_convex:
        MMTM      SP,B0,B1,B2,B7,B10,B11,B12,B13,B14
        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
	CLR	  B0		      ;0 ==> solid fill
        JRUC      CP_ARGS             ;

_patnfill_convex:
        MMTM      SP,B0,B1,B2,B7,B10,B11,B12,B13,B14
        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
	MOVE	  @_pattern+PATTERN_HSRV,B0,1 ;subroutine for pattern fill
;
; Pop the arguments off the C program stack.
CP_ARGS:
        MOVE      *-A14,A0,1          ;get n (the number of vertices)
        MOVE      *-A14,StartPL,1     ;get pointer to ptlist[] array
	JRUC	  common_ep
;
;   Direct-mode SUBROUTINE ENTRY POINTS (_fill_convex and _patnfill_convex)
;
_dm_fill_convex:
        MMTM      SP,B0,B1,B2,B7,B10,B11,B12,B13,B14
        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
	CLR	  B0		      ;0 ==> solid fill
        JRUC      DM_ARGS             ;

_dm_patnfill_convex:
        MMTM      SP,B0,B1,B2,B7,B10,B11,B12,B13,B14
        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
	MOVE	  @_pattern+PATTERN_HSRV,B0,1 ;subroutine for pattern fill
;
; Get the arguments from the direct-mode data packet.
DM_ARGS:
	SETF	  16,0,0	      ;
        MOVE      *-A14,StartPL,1     ;argument points to dm-data area
        MOVE      *StartPL+,A0,0      ;1st arg is # bytes
	SRL	  2,A0		      ;Convert from # bytes to # vertices
;
;
;  ALL 4 ENTRY POINTS JOIN UP HERE
;
common_ep:
;
	MOVK	  3,A8		      ;min. no. of vertices in polygon
	CMP	  A8,A0 	      ;verify that n >= 3
	JRLT	  DONE		      ;if n < 3, return immediately
; Verify that the destination bitmap is set to the screen.
	MOVE	  @(_env+ENVIRONMENT_DSTBM),A8,1 ;destination bitmap
        JRNZ      DONE                ;if dstbm != screen, return immediately
; Set up some constants.
        SETF      16,1,0              ;
        MOVI      010000h,B7          ;DY = 1
	MOVE	  @(_env+ENVIRONMENT_XYORIGIN),xyOrg,1 ;drawing origin (x,y)
; Set up pointer to first word beyond end of ptlist[] array.
        MOVE      A0,EndPL            ;copy vertex count n
        SLL       5,EndPL             ;array offset = 32*n
        ADD       StartPL,EndPL       ;set pointer = &ptlist[n]
; Back face elimination--don't draw polygon that faces away from screen.
        MOVE      EndPL,A9            
        MOVE      *-A9,A6,0           ;read y coordinate j2 (ptlist[n-1].y)
        MOVE      *-A9,A5,0           ;read x coordinate i2 (ptlist[n-1].x)
        MOVE      *-A9,A2,0           ;read y coordinate j1 (ptlist[n-2].y)
        MOVE      *-A9,A1,0           ;read x coordinate i1 (ptlist[n-2].x)
        MOVE      StartPL,A9          ;base address of ptlist[] array
        MOVE      A0,A10              ;set up loop count
        SETF      16,1,1              ;(set up for 16-bit multiplies)
LOOP1:
        MOVE      *A9+,A7,0           ;read x coordinate i3
        MOVE      *A9+,A8,0           ;read y coordinate j3
        MOVE      A1,A3               ;copy i1
        MOVE      A2,A4               ;copy j1
        SUB       A7,A1               ;(i1 - i3)
        SUB       A6,A2               ;(j1 - j2)
        SUB       A5,A3               ;(i1 - i2)
        SUB       A8,A4               ;(j1 - j3)
        MPYS      A2,A1               ;(i1 - i3)*(j1 - j2)
        MPYS      A4,A3               ;(i1 - i2)*(j1 - j3)
        SUB       A3,A1               ;XP=(i1-i3)*(j1-j2)-(j1-j3)*(i1-i3)
        JRNZ      BREAK1              ;jump out of loop if XP != 0
        MOVE      A5,A1               ;i1 = i2
        MOVE      A6,A2               ;j1 = j2
        MOVE      A7,A5               ;i2 = i3
        MOVE      A8,A6               ;j2 = j3
        DSJ       A10,LOOP1           ;loop again
BACK:
        SETF      32,0,1              ;(restore field size 1 to 32 bits)
        JRUC      DONE                ;all done; return
BREAK1:
        JRNN      BACK                ;jump if XP >= 0 (if back face)
        SETF      32,0,1              ;(restore field size 1 to 32 bits)
;
; Find topmost vertex (minimum y) in polygon.
	MOVE	  StartPL,A8	      ;copy ptlist array base address
	ADDK	  16,A8 	      ;point to y at first vertex
	MOVI	  03FFFh,A7	      ;initial Ymin = +infinity
	MOVE	  A0,A10	      ;count = number n of vertices
FINDTOP:
	MOVE	  *A8,A9,0	      ;get y value at next vertex
	CMP	  A9,A7 	      ;is y < ymin ?
	JREQ	  SKIP		      ;skip if y == ymin
	MOVX	  A10,A6	      ;copy loop count
	JRLT	  SKIP		      ;jump if y > ymin
	MOVE	  A9,A7 	      ;set ymin = y
	MOVE	  A8,A4 	      ;save pointer to y
SKIP:
	ADDK	  32,A8 	      ;point to next y in array
	DSJ	  A10,FINDTOP	      ;loop if more vertices

	CMPXY	  A0,A6 	      ;do all vertices have same y ?
	JRXZ	  DONE		      ;yes--trivially reject polygon
	SUBK	  16,A4 	      ;point to x at top vertex
;
; Initialize parameters for main loop.
BREAK2:
	MOVE	  A4,A9 	      ;vertex pointer p1 = top vertex
	MOVE	  A4,A10	      ;vertex pointer p3 = top vertex

	MOVE	  *A4,A7,1	      ;set j1::x1 to top vertex
        ADDXY     xyOrg,A7            ;convert j1::x1 to screen coord's
	MOVE	  A7,A8 	      ;set j3::x3 to top vertex
	MOVY	  A7,A0 	      ;set j::?? to top vertex
        SRL       16,A0               ;move j into 16 LSBs of register
;
; Partition convex polygon into trapezoids, and fill them.  The left
; edge of each trapezoid is the line from (i2,j) to (i3,j3), and the
; right edge is the line from (i0,j) to (i1,j1).  Initialize vertical
; distances b1 and b3 to next vertices on right and left sides to 0.
	CLR	  A4		      ;b1 = 0
	CLR	  A6		      ;b3 = 0
LOOP3:
        SLL       16,A0               ;move j to 16 MSBs of register
;
; Have we reached the next vertex on the left side of the polygon?
	MOVE	  A4,A4 	      ;check distance b1 to next vertex
	JRNZ	  OVER3 	      ;jump if not yet at next vertex
WHILE1:
        ADDK      32,A9               ;++p1
        CMP       A9,EndPL            ;p1 == &polygon[n] ?
        JRNZ      OVER2               ;jump if p1 != &polygon[n]
        MOVE      StartPL,A9          ;otherwise, p1 = &polygon[0]
OVER2:
        MOVE      A7,A1               ;i0 = i1
	MOVE	  *A9,A7,1	      ;get x coord. i1 and y coord. j1
        ADDXY     xyOrg,A7            ;convert j1::x1 to screen coord's
        CMPXY     A0,A7               ;j1 != j ?
        JRZ       WHILE1              ;loop again if j1 == j

	MOVE	  A7,A4 	      ;copy j1::i1
;;;;;	MOVY	  A0,A1 	      ;concatenate current j with i0
        SUBXY     A1,A4               ;a1 = i1-i0, b1 = j1-j
	JRYN	  DONE		      ;done if j1 < j (reached bottom)
        MOVE      A4,A3               ;
        SLL       16,A3               ;isolate a1 in 16 MSBs
        SRA       16,A4               ;isolate b1 in 16 LSBs
        DIVS      A4,A3               ;dx0 = (a1 << 16) / b1
        SLL       16,A1               ;
	ADDI	  07FFFh,A1	      ;add rounding bias
        MOVE      A3,A14              ;
        SRA       1,A14               ;
        ADD       A14,A1              ;x0 = (i0 << 16) + 0x7FFF + (dx0/2)
;
; Have we reached the next vertex on the right side of the polygon?
OVER3:
	MOVE	  A6,A6 	      ;check distance b3 to next vertex
	JRNZ	  OVER5 	      ;jump if not yet at next vertex
WHILE2:
        CMP       A10,StartPL         ;p3 == &polygon[0] ?
        JRNE      OVER4               ;if not, jump
        MOVE      EndPL,A10           ;otherwise, p3 = &polygon[n]
OVER4:
        SUBK      32,A10              ;--p3
        MOVE      A8,A2               ;i2 = i3

	MOVE	  *A10,A8,1	      ;get x coord. i3 and y coord. j3
        ADDXY     xyOrg,A8            ;convert j3::x3 to screen coord's
        CMPXY     A0,A8               ;j3 != j ?
        JRZ       WHILE2              ;loop again if j3 == j

	MOVE	  A8,A6 	      ;copy j3::i3
;;;;;	MOVY	  A0,A2 	      ;concatenate current j with i2
        SUBXY     A2,A6               ;a3 = i3-i2, b3 = j3-j
	JRYN	  DONE		      ;done if j3 < j (reached bottom)
	MOVE	  A6,A5 	      ;
        SLL       16,A5               ;isolate a3 in 16 MSBs
        SRA       16,A6               ;isolate b3 in 16 LSBs
        DIVS      A6,A5               ;dx2 = (a3 << 16) / b3
        SLL       16,A2               ;
	ADDI	  07FFFh,A2	      ;add rounding bias
        MOVE      A5,A14              ;
        SRA       1,A14               ;
        ADD       A14,A2              ;x2 = (i2 << 16) + 0x7FFF + (dx2/2)
OVER5:
        MOVE      A4,A14              ;set count = the smaller of b1, b3
        CMP       A4,A6               ;
        JRNN      OVER6               ;
        MOVE      A6,A14              ;
OVER6:
        MOVE      A14,A14             ;is count negative?
        JRNN      OVER7               ;jump if count positive
	JRUC	  DONE		      ;all done, exit routine

        .if       GSP_34010           ;Code used if the processor is a 34010
OVER7:
        SUB       A14,A4              ;b1 -= count
        SUB       A14,A6              ;b3 -= count
        MOVE      A14,B1              ;make working copy of count
        SRL       16,A0               ;move j to 16 LSBs of register
	MOVE	  B0,B0 	      ;solid (0) or pattern (!0) fill?
	JRNZ	  PAT1		      ;jump if pattern fill

; Use this version of inner loop to fill trapezoid with solid color.
SOLID:
        MOVY      A1,A14              ;
        SUBXY     A2,A14              ;
	JRC	  DONE		      ;if (w = i0-i2) < 0, exit now
        SRL       16,A14              ;
        MOVE      A14,B14             ;
        MOVX      B14,B7              ;set fill width = w
        MOVY      A2,A0               ;i2 = integer part of x2
        MOVE      A0,B2               ;set fill address = (i2,j)
        RL        16,B2               ;move i2 to 16 LSBs, j2 to 16 MSBs
        FILL      XY                  ;fill one horizontal line
        ADD       A3,A1               ;x0 += dx0
        ADD       A5,A2               ;x2 += dx2
        INC       A0                  ;++j
        DSJ       B1,SOLID            ;do inner loop while --count > 0
        JRUC      LOOP3               ;otherwise, repeat outer loop

; Use this version of inner loop to fill trapezoid with pattern.

PAT1:
        .endif
        .if       GSP_34020           ;Code used if the processor is a 34020
OVER7:
        SUB       A14,A4              ;b1 -= count
        SUB       A14,A6              ;b3 -= count
        MOVE      A14,B12             ;make working copy of count
	SRL	  16,A0 	      ;move j to 16 LSBs of register
	MOVE	  B0,B0 	      ;solid (0) or pattern (!0) fill?
        JRNZ      PAT1                ;if not, do pattern fill instead

; Use this version of inner loop to fill trapezoid with solid color.
SOLID:
	MOVE	  A2,B0 	      ;set X1 for TFILL
	MOVE	  A5,B1 	      ;set DX1 for TFILL
	MOVE	  A1,B7 	      ;set X2 for TFILL
	MOVE	  A3,B10	      ;set DX2 for TFILL
	MOVE	  A0,B11	      ;copy Y
	SLL	  16,B11	      ;shift Y left for TFILL
TUF:
	CMP	  B0,B7 	      ;verify that x1 < x2
	JRLT	  DONE		      ;if x1 >= x2, return immediately
        TFILL     XY                  ;fill next span
        DSJ       B12,TUF             ;do inner loop while --count > 0
;
; Trapezoid fill completed.  Are there more trapezoids to fill?
        MOVE      B0,A2               ;save updated x2
        MOVE      B7,A1               ;save updated x1
        MOVE      B11,A0              ;save updated j
        SRL       16,A0               ;right justify j
	CLR	  B0		      ;restore solid-fill flag
        JRUC      LOOP3               ;otherwise, repeat outer loop
;
; Use this version of inner loop to fill trapezoid with pattern.

PAT1:
        MOVE      B12,B1              ;PATNLINE wants count in B1
        .endif

PATTERN:
        MOVY      A1,A14              ;
        SUBXY     A2,A14              ;
	JRC	  DONE		      ;if (w = i0-i2) < 0, exit now
        SRL       16,A14              ;
        MOVE      A14,B14             ;
        MOVX      B14,B7              ;set fill width = w
        MOVY      A2,A0               ;
        MOVE      A0,B2               ;set fill address = (i2,j)
        RL        16,B2               ;move i2 to 16 LSBs, j2 to 16 MSBs
        CALL      B0                  ;fill one horizontal line
        ADD       A3,A1               ;x0 += dx0
        ADD       A5,A2               ;x2 += dx2
        INC       A0                  ;++j
        DSJ       B1,PATTERN          ;do inner loop while --count > 0
        JRUC      LOOP3               ;otherwise, repeat outer loop

; Restore registers and return to calling routine.
DONE:
        MMFM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
        MMFM      SP,B0,B1,B2,B7,B10,B11,B12,B13,B14
        MOVE      *SP(32),A14,1       ;restore program stack pointer
        RETS      2                   ;
        .end

