        .width    132
        .title    'fill polygon'

*----------------------------------------------------------------------
*                                    TIGA
*          Copyright (C) 1988-1990  Texas Instruments Incorporated.
*                            All Rights Reserved
*----------------------------------------------------------------------
* polygon function
*
*   The polygon function draws a solid-filled polygon given a list
*   of vertices defining the polygon.  In order to be drawn correctly,
*   the polygon must be convex (no concavities).
*
*   The function requires two input arguments.  The first, nverts,
*   specifies the number of vertices in the polygon.  The second
*   argument, ptlist, is a pointer to an array of x and y coordinates.
*   Each vertex is represented in the list as a 16-bit x coordinate
*   followed by a 16-bit y coordinate.  Each 16-bit coordinate is a
*   fixed-point number with 2 bits of fraction.  If the vertices are
*   listed in clockwise order (the convention is that x increases to the
*   right, and y increases downward), the polygon is assumed to be
*   facing forward, and is filled.  If the vertices are specified in
*   counterclockwise order, the polygon is assumed to be facing away
*   from the screen and is not drawn.  An edge of the polygon is assumed
*   between the first and last vertices specified.
*----------------------------------------------------------------------
*  Usage:  polygon(nverts, ptlist)
*
*  Description of stack arguments:
*    int nverts;             /* number of vertices in polygon */
*    short *ptlist;          /* array of x-y coordinate pairs */
*
*  Returned in register A8:  undefined
*
*  Registers altered:  A8
*----------------------------------------------------------------------
* Revision history:
*   06/08/88...Original version written..................Jerry Van Aken
*----------------------------------------------------------------------
;
        .title    'polygon'
        .file     'polygon.asm'
;
;
;  DECLARE GLOBAL FUNCTION NAME
;
        .globl    _polygon

;
;
;   DECLARE EXTERNAL VARIABLES
;
        .globl    _xyorigin           ;viewport xy origin displacement
;
;
;   DEFINE CONSTANTS
;
YLINE   .set      A0                  ;y value at current scan line
NVERTS  .set      A0                  ;number of vertices in polygon
ATEMP   .set      A1                  ;A-file temporary register
X1REAL  .set      A2                  ;fixed-pt x1 at left side of fill
DX1     .set      A3                  ;change in x1 per unit step in y
X2REAL  .set      A4                  ;fixed-pt x2 at right side of fill
DX2     .set      A5                  ;change in x2 per unit step in y
XY1END  .set      A6                  ;x,y at end of edge on left side
XY2END  .set      A7                  ;x,y at end of edge on right side
H1      .set      A8                  ;height of edge on left side
H2      .set      A9                  ;height of edge on right side
P1      .set      A10                 ;pointer to next vertex on left side
P2      .set      A11                 ;pointer to next vertex on right side
PMIN    .set      A12                 ;pointer to bottom of ptlist array
PMAX    .set      A13                 ;pointer to top of ptlist array
XYSTART .set      A14                 ;starting vertex of current edge
STK     .set      A14                 ;C parameter stack pointer
XYORG   .set      B0                  ;viewport xy origin displacement
COUNT   .set      B1                  ;loop counter
DADDR   .set      B2                  ;destination xy address for fills
DYDX    .set      B7                  ;width and height of fill area
BTEMP   .set      B14                 ;B-file temporary register
;
;
;   ENTRY POINT
;
_polygon:

        SETF      4,1,1               ;set up for 4-bit multiplies
        SETF      32,0,0              ;set up for 32-bit data moves
        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
        MMTM      SP,B0,B1,B2,B7,B10,B11,B12,B13,B14
; Fetch both arguments from parameter stack.
        MOVE      -*STK,NVERTS,0      ;get argument nverts
        MOVE      -*STK,PMIN,0        ;get argument ptlist
*------------------------------------------------------------------------------
; Search for topmost vertex (minimum y) in polygon.
        MOVE      PMIN,P1             ;copy pointer to ptlist array
        MOVI      03FFF0000h,XY1END   ;initialize ymin = max y value
        MOVE      NVERTS,COUNT        ;initialize loop counter
FINDTOP:
        MOVE      *P1+,XYSTART,0      ;fetch xy coord's for next vertex
        CMPXY     XYSTART,XY1END      ;is y < ymin ?
        JRYZ      SKIP                ;jump if y == ymin
        MOVE      COUNT,ATEMP         ;make copy of current loop count
        JRYN      SKIP                ;jump if y > ymin
        MOVE      XYSTART,XY1END      ;set ymin = y
        MOVE      P1,P2               ;copy pointer (autoincremented)
SKIP:
        DSJ       COUNT,FINDTOP       ;loop if more vertices
; Coordinates of topmost vertex in polygon have been found.
        CMP       NVERTS,ATEMP        ;are all vertices at same y?
        JREQ      DONE                ;yes, trivially reject polygon
        MOVE      P2,P1               ;set p1 = p2
        SUBK      32,P1               ;undo last increment to pointer
        MOVE      @_xyorigin,XYORG,0  ;get viewport origin displacements
        ADDXY     XYORG,XYORG         ;
        ADDXY     XYORG,XYORG         ;convert to FIX2 format
        MOVE      XYORG,ATEMP         ;
        ADDXY     ATEMP,XY1END        ;convert to screen coordinates
        MOVE      XY1END,XY2END       ;left, right sides begin at top
; Set up pointer to end of last vertex in ptlist array.
        MOVE      NVERTS,PMAX         ;copy nverts
        SLL       5,PMAX              ;offset = 2 * 16 * nverts
        ADD       PMIN,PMAX           ;add ptlist base address
; Find y value along pixel centers of topmost scan line to be filled.
        MOVE      XY1END,YLINE        ;copy initial y value
        SRA       16,YLINE            ;convert to FIX2 format
        ADDK      1,YLINE             ;round up by 1/2 - 1/4
        SRA       2,YLINE             ;truncate to integer

*------------------------------------------------------------------------------
* Main Loop:  Each iteration fills a trapezoidal region of the polygon.
*------------------------------------------------------------------------------
        MOVI      010000h,DYDX        ;set fill height = 1
; Initialize heights of edge segments on left and right sides.
        CLR       H1                  ;left edge height = 0
        CLR       H2                  ;right edge height = 0

        .align                        ;keep main loop in cache
MAINLOOP:
; Calculate y value along pixel centers of next scan line to be filled.
        SLL       2,YLINE             ;convert yline to FIX2
        ADDK      2,YLINE             ;y at pixel centers = yline + 1/2
        SLL       16,YLINE            ;shift yline+1/2 into 16 MSBs

*------------------------------------------------------------------------------
; Have we reached the next vertex on the left side of the polygon?
        MOVE      H1,H1               ;check y distance to next vertex
        JRNZ      NOTYET1             ;jump if not yet at next vertex
; Arrived at starting vertex for next edge.  Need to get ending vertex.
; Update pointer to point to next vertex (the ending vertex) in list.
WHILE1:
        CMP       P1,PMIN             ;p = pmin ?
        JRNZ      OVER1               ;jump if p > pmin
        MOVE      PMAX,P1             ;next vertex is last one in list
OVER1:
; Advance to next edge segment along side of polygon.
        MOVE      XY1END,XYSTART      ;save start vertex coord's (xs,ys)
        MOVE      -*P1,XY1END,0       ;get end vertex coord's (xe,ye)
        MOVE      XYORG,ATEMP         ;
        ADDXY     ATEMP,XY1END        ;convert to screen coordinates
; If we have finally reached the bottom of the polygon, we are done.
        MOVE      XY1END,ATEMP        ;
        SUBXY     XYSTART,ATEMP       ;a = xe-xs, b = ye-ys
        JRYN      DONE                ;done if ye < ys (reached bottom)
; If edge is too short to reach to next scan line, go to next edge.
        MOVE      XY1END,H1           ;make copy of end vertex
        SUBXY     YLINE,H1            ;subtract y of next scan line
        JRYN      WHILE1              ;too short--go to next edge
        SRL       16+2,H1             ;truncate to integer
        INC       H1                  ;no. scan lines covered by edge
; Get edge's inverse slope:  deltax = change in x per unit step in y.
        MOVE      ATEMP,DX1           ;copy width a of edge
        SLL       16,DX1              ;a << 16
        SRL       16,ATEMP            ;right justify b (is positive)
        DIVS      ATEMP,DX1           ;deltax = (a << 16) / b
; Calculate initial fixed-point x where edge meets next scan line.
        MOVE      YLINE,X1REAL        ;
        SUBXY     XYSTART,X1REAL      ;(yline + 1/2 - ys) in 16 MSBs
        SRL       16,X1REAL           ;right justify fractional part
        MOVE      DX1,ATEMP           ;copy deltax
        MPYS      X1REAL,ATEMP        ;(yline + 1/2 - ys) * deltax
        MOVE      XYSTART,X1REAL      ;
        SLL       16,X1REAL           ;left justify starting x value
        ADD       ATEMP,X1REAL        ;adjust starting x value
        SRA       2,X1REAL            ;integer part of x in 16 MSBs
        ADDI      07FFFh,X1REAL       ;add in rounding constant
NOTYET1:

*------------------------------------------------------------------------------
; Have we reached the next vertex on the right side of the polygon?
        MOVE      H2,H2               ;check y distance to next vertex
        JRNZ      NOTYET2             ;jump if not yet at next vertex
; Arrived at starting vertex for next edge.  Need to get ending vertex.
; Update pointer to point to next vertex (the ending vertex) in list.
WHILE2:
        CMP       P2,PMAX             ;p = pmax ?
        JRNZ      OVER2               ;jump if p < pmax
        MOVE      PMIN,P2             ;next vertex is first one in list
OVER2:
; Advance to next edge segment along side of polygon.
        MOVE      XY2END,XYSTART      ;save start vertex coord's (xs,ys)
        MOVE      *P2+,XY2END,0       ;get end vertex coord's (xe,ye)
        MOVE      XYORG,ATEMP         ;
        ADDXY     ATEMP,XY2END        ;convert to screen coordinates
; If we have finally reached the bottom of the polygon, we are done.
        MOVE      XY2END,ATEMP        ;
        SUBXY     XYSTART,ATEMP       ;a = xe-xs, b = ye-ys
        JRYN      DONE                ;done if ye < ys (reached bottom)
; If edge is too short to reach to next scan line, go to next edge.
        MOVE      XY2END,H2           ;make copy of end vertex
        SUBXY     YLINE,H2            ;subtract y of next scan line
        JRYN      WHILE2              ;too short--go to next edge
        SRL       16+2,H2             ;truncate to integer
        INC       H2                  ;no. scan lines covered by edge
; Get edge's inverse slope:  deltax = change in x per unit step in y.
        MOVE      ATEMP,DX2           ;copy width a of edge
        SLL       16,DX2              ;a << 16
        SRL       16,ATEMP            ;right justify b (is positive)
        DIVS      ATEMP,DX2           ;deltax = (a << 16) / b
; Calculate initial fixed-point x where edge meets next scan line.
        MOVE      YLINE,X2REAL        ;
        SUBXY     XYSTART,X2REAL      ;(yline + 1/2 - ys) in 16 MSBs
        SRL       16,X2REAL           ;right justify fractional part
        MOVE      DX2,ATEMP           ;copy deltax
        MPYS      X2REAL,ATEMP        ;(yline + 1/2 - ys) * deltax
        MOVE      XYSTART,X2REAL      ;
        SLL       16,X2REAL           ;left justify starting x value
        ADD       ATEMP,X2REAL        ;adjust starting x value
        SRA       2,X2REAL            ;integer part of x in 16 MSBs
        ADDI      07FFFh,X2REAL       ;add in rounding constant
NOTYET2:

*------------------------------------------------------------------------------
; Determine height of next trapezoidal area to be filled.
        MOVE      H1,ATEMP            ;copy height of left edge segment
        CMP       H1,H2               ;compare with right edge height
        JRNN      OKAY                ;jump if left edge shorter
        MOVE      H2,ATEMP            ;right edge is shorter
OKAY:
        SUB       ATEMP,H1            ;h1 -= count
        SUB       ATEMP,H2            ;h2 -= count
        MOVE      ATEMP,COUNT         ;initial loop count = trap. height
        SRA       16+2,YLINE          ;right justify yline integer part

*------------------------------------------------------------------------------
; Inner loop:  Fill trapezoidal area of specified height.
TFILL:
        MOVE      X2REAL,ATEMP        ;copy x coord. along right side
        SUBXY     X1REAL,ATEMP        ;fill width = int(x2) - int(x1)
        JRC       NEGWIDE             ;jump if width < 0
        SRL       16,ATEMP            ;move width into 16 LSBs
        MOVE      ATEMP,BTEMP         ;copy to B-file
        MOVX      BTEMP,DYDX          ;move width into 16 LSBs of DYDX
        MOVY      X1REAL,YLINE        ;concat. int(x1) with scan line y
        MOVE      YLINE,DADDR         ;copy to dest'n address register
        RL        16,DADDR            ;move x1 to LSBs, yline to MSBs
        FILL      XY                  ;fill one horizontal line segment
NEGWIDE:
        ADD       DX1,X1REAL          ;increment fixed-point x1
        ADD       DX2,X2REAL          ;increment fixed-point x2
        INC       YLINE               ;increment integer scan line y
        DSJ       COUNT,TFILL         ;loop 'til bottom of trapezoid
; Done filling current trapezoidal region of polygon.  Are there more?
        JRUC      MAINLOOP            ;go get next trapezoid to fill

; All done.  Restore registers and return to calling routine.
DONE:
        MMFM      SP,B0,B1,B2,B7,B10,B11,B12,B13,B14
        MMFM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
        SETF      32,0,1              ;restore default field size 1
        MOVE      *SP(32),STK,1       ;restore parameter stack ptr
        RETS      2
        .end

