;-------------------------------------------------------------------------;
;				   TIGA 				  ;
;        Copyright (c) 1989-1990  Texas Instruments Incorporated.         ;
;			   All Rights Reserved				  ;
;-------------------------------------------------------------------------;
;   TIGA - Graphics Manager Extension					  ;
;-------------------------------------------------------------------------;
; fill_polygon and patnfill_polygon functions				  ;
;									  ;
;   Fill a polygon specified as an ordered list of vertices.  The	  ;
;   fill_polygon function fills a polygon with a solid color (the	  ;
;   foreground color stored in COLOR1), while the patnfill_polygon	  ;
;   function fills a polygon with an area-fill pattern (in a combination  ;
;   of the foreground and background colors).  The polygon can be of any  ;
;   shape, and is permitted to contain concavities and self-intersecting  ;
;   edges.								  ;
;									  ;
;   Argument n is an integer specifying the number of vertices in the	  ;
;   polygon.								  ;
;									  ;
;   Argument points is an n-element array containing the xy-coordinate	  ;
;   pairs for the n vertices of the polygon.  Each element of the points  ;
;   array is of type POINT2D, which is a structure consisting of a 16-bit ;
;   integer x value followed by an 16-bit integer y value:		  ;
;		typedef struct { short x, y; } POINT2D; 		  ;
;   Beginning with the first vertex in the points array, each vertex in   ;
;   the array is connected to (and forms a polygon edge with) the next	  ;
;   successive vertex in the array.  The last vertex in the points array  ;
;   is assumed to form an edge with the first vertex in the array.	  ;
;   Polygons having a very large number of vertices may cause the TIGA	  ;
;   command buffer to overflow, as described in the TIGA-340 Interface	  ;
;   User's Guide.                                                         ;
;									  ;
;   In the implementation below, the algorithm partitions the polygon	  ;
;   into a series of trapezoids whose two parallel sides are aligned to   ;
;   the y axis.  Within the routine, y coordinates are represented as	  ;
;   16-bit integers, while x coordinates are represented as 32-bit	  ;
;   fixed-point values with 16 bits of fraction:			  ;
;	      typedef long FIX16;  /* fixed-point value */		  ;
;									  ;
;   Within the routine, each edge of the polygon is represented by a	  ;
;   16-byte data structure:						  ;
;     typedef struct edge_type {       /* structure size = 16 bytes */	  ;
;	short ytop;	/* integer y coord at top end of edge */	  ;
;	short ybot;	/* integer y coord at bottom end of edge */	  ;
;	FIX16 xtop;	/* fixed point x coord at top end of edge */	  ;
;	FIX16 dx;	/* 1/slope = change in x per unit step in y */	  ;
;	struct edge_type *next;  /* pointer to next item in edge list */  ;
;     } PGON_EDGE;							  ;
;   Memory is allocated on top of the GSP's system stack for storing edge ;
;   information.  The total storage required is n*sizeof(PGON_EDGE)	  ;
;   bytes, where n is the number of vertices.  Polygons having a very	  ;
;   large number of vertices may cause the system stack to overflow.
;									  ;
;   An earlier implementation of the fill_polygon and patnfill_polygon	  ;
;   functions required allocation of an offscreen workspace:  a one-bit-  ;
;   per-pixel bitmap with the same x and y dimensions as the screen.	  ;
;   The current implementation has NO SUCH REQUIREMENT. 		  ;
;									  ;
;   In the future, changes may be made to the fillpoly function to	  ;
;   improve its performance.  The algorithm maintains two linked lists	  ;
;   containing items of type EDGE.  A y-sorted edge list is ordered in	  ;
;   terms of increasing ytop values.  An x-sorted edge list is ordered	  ;
;   in terms of increasing xtop values.  The xtop and ytop values are	  ;
;   the xy coordinates at the top (i.e., minimum y) vertex of the edge.   ;
;   The ordering of each list is maintained by the local subroutines	  ;
;   X_INSERT_LIST and Y_INSERT_LIST.  The time required to sort a list	  ;
;   of N items using these insertion routines is proportional to N**2.	  ;
;   Hence, the polyfill function tends to become inefficient when N	  ;
;   becomes large.  A better implementation of the algorithm would	  ;
;   replace these insertion routines with a more efficient sorting	  ;
;   method, such as quicksort, for which the overhead increases merely as ;
;   a linear function of N.  For small N, however, the performance of the ;
;   current function seems pretty good. 				  ;
;-------------------------------------------------------------------------;
; Usage:  fill_polygon(n, points);					  ;
;	  patnfill_polygon(n, points);					  ;
;									  ;
; Stack parameters:							  ;
;	  short n;	       { number of vertices in polygon }	  ;
;	  POINT2D *points;     { x-y coordinates of vertices }		  ;
;									  ;
; Return in A8:  void (undefined)					  ;
;									  ;
; Registers altered:  A8						  ;
;-------------------------------------------------------------------------;
; Revision History:							  ;
;   07/31/89...Original Version written..................Jerry Van Aken   ;
;   08/03/89...34020 support.............................Al Sharp         ;
;   03/20/90...First argument changed from n+1 to n......Jerry Van Aken   ;
;-------------------------------------------------------------------------;
;                                                                       
        .title    'fill polygon'
        .file     'polyfill.asm'
;
;   INCLUDE FILES
;
        .nolist
        .include  gsptypes.inc      ;offsets into environment structure
        .include  gspglobs.inc      ;TIGA global variables
        .include  gspreg.inc        ;GSP register names
        .include  oem.inc
        .list
;
;     DEFINE AS A GLOBAL SUBROUTINE
;
        .globl    _fill_polygon,_dm_fill_polygon
        .globl    _patnfill_polygon,_dm_patnfill_polygon
;
;
;
;     DEFINE CONSTANTS
;
NULL    .set      -1                  ;null edge index
INFINITY .set     04000h              ;largest legal integer coordinate
LOG2SIZE .set     7                   ;log2 of size of EDGE struct
; Define offsets into EDGE struct.
YTOP    .set      0                   ;integer y coord at top end of edge
YBOT    .set      16                  ;integer y coord at bottom end of edge
XTOP    .set      32                  ;fixed point x coord at top end of edge
DX      .set      64                  ;1/slope: change in x per unit step in y
NEXT    .set      96                  ;pointer to next item in edge list
; Define symbolic names for A-file registers.
SIZEOF  .set      A0                  ;size of EDGE struct (16 bytes)
XLIST   .set      A0                  ;pointer to x-sorted list
YLIST   .set      A1                  ;pointer to y-sorted list
E1      .set      A2                  ;pointer to edge 1
P_XY    .set      A2                  ;pointer xy coordinates of vertices
E2      .set      A3                  ;pointer to edge 2
N       .set      A3                  ;number of vertices in polygon
P       .set      A4                  ;edge pointer p
EBUF    .set      A4                  ;pointer to edge buffer
X1      .set      A5                  ;x where edge 1 crosses y=yscan
V1      .set      A5                  ;xy coordinates for vertex 1
VTOP    .set      A5                  ;xy coordinates for top vertex
Q       .set      A5                  ;edge pointer q
X2      .set      A6                  ;x where edge 2 crosses y=yscan
VBOT    .set      A6                  ;xy coordinates for bottom vertex
R       .set      A6                  ;edge pointer r
DX1     .set      A7                  ;inverse slope of edge 1
V2      .set      A7                  ;xy coordinates for vertex 2
ROUND   .set      A8                  ;fixed-pt rounding constant = 1/2-e
DX2     .set      A8                  ;inverse slope of edge 2
XSTOP   .set      A9                  ;x where edge crosses y=yscan
SP_INC  .set      A9                  ;increment to restore original SP
YSTOP   .set      A10                 ;scan line (y) at which fill stops
Y       .set      A10                 ;integer y coordinate
TMP0    .set      A12                 ;temporary register 0
TMP1    .set      A13                 ;temporary register 0
DY      .set      A13                 ;integer displacement in y
COUNT   .set      A13                 ;loop count
YSCAN   .set      A14                 ;current scan line (y coordinate)
XYORG   .set      A14                 ;screen coord's of drawing origin
; Define symbolic names for B-file registers.
FILLSRV .set      B0                  ;pointer to pattern-fill service
BTMP    .set      B14                 ;temporary B-file register
;
;
;     C-PACKET ENTRY POINT:  fill_polygon
;
_fill_polygon:

        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A12,A13
        MMTM      SP,B0,B2,B3,B7,B10,B11,B12,B13,B14
        CLR       FILLSRV             ;fillsrv=0: solid filled polygon
	JR	  CP_POLYFILL	      ;
;
;
;     C-PACKET ENTRY POINT:  patnfill_polygon
;
_patnfill_polygon:

        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A12,A13
        MMTM      SP,B0,B2,B3,B7,B10,B11,B12,B13,B14
        MOVE      @_pattern+PATTERN_HSRV,FILLSRV,1 ;pattern fill routine
* Pop parameters for C-packet calls.
CP_POLYFILL:
        SETF      16,1,1              ;set up for 16-bit moves and mults
        SETF      32,0,0              ;set up for 32-bit moves
        MOVE      *-STK,N,0           ;get argument 'nlines'
	JRLE	  DONE		      ;done if npts <= 0
        MOVE      *-STK,P_XY,0        ;get argument 'ptlist'
        JR        common_ep           ;
;
;
;    DIRECT-MODE ENTRY POINT:  fill_polygon
;
_dm_fill_polygon:

        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A12,A13
        MMTM      SP,B0,B2,B3,B7,B10,B11,B12,B13,B14
        CLR       FILLSRV             ;fillsrv=0: solid filled polygon
        JR        DM_POLYFILL         ;
;
;
;     DIRCT-MODE ENTRY POINT:  patnfill_polygon
;
_dm_patnfill_polygon:

        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A12,A13
        MMTM      SP,B0,B2,B3,B7,B10,B11,B12,B13,B14
        MOVE      @_pattern+PATTERN_HSRV,FILLSRV,1 ;pattern fill routine
* Pop parameters for direct-mode calls.
DM_POLYFILL:
        SETF      16,1,1              ;set up for 16-bit moves and mults
        SETF      32,0,0              ;set up for 32-bit moves
        MOVE      -*STK,P_XY,0        ;will be address of ptlist
        MOVE      *P_XY+,N,1          ;1st word is array size in bytes
	SRA	  2,N		      ;convert from bytes to npts
	JRLE	  DONE		      ;done if npts <= 0
;
;
;    ENTRY POINTS JOIN UP HERE
;
common_ep:

        MOVE      @(_env+ENVIRONMENT_XYORIGIN),XYORG,0 ;viewport origin
        MOVK      1,DYDX              ;
        SLL       16,DYDX             ;set constant span height = 1
        MOVI      1<<LOG2SIZE,SIZEOF  ;constant = size of EDGE struct
        MOVI      07FFFh,ROUND        ;fixed-pt rounding constant = 1/2-e
;
; Allocate space on system stack for array of edges.
        MOVE      N,SP_INC            ;get vertex count
        SLL       LOG2SIZE,SP_INC     ;convert to edge array length
        SUB       SP_INC,SP           ;allocate stack space for buffer
        MOVE      SP,EBUF             ;now ebuf is a valid pointer
        MOVE      SP_INC,-*SP,0       ;save stack displacement for later
;
; Sort edges in order of ascending y:  For each edge of polygon,
; insert edge into ysort_list in order of increasing minimum y.
        CLR       YLIST               ;ysort_list = NULL
        MOVE      N,V1                ;copy vertex count n
        SLL       5,V1                ;convert to offset into array of long
        ADD       P_XY,V1             ;add xy array base address
        MOVE      -*V1,V1,0           ;v1 = xy[n - 1] (x and y values)
        ADDXY     XYORG,V1            ;convert to screen coordinates
;---	MOVE	  EBUF,P	      ;point to first element in edge array

INIT_LOOP:
        MOVE      *P_XY+,V2,0         ;v2 = *xy++ (get pair of xy coordinates)
        ADDXY     XYORG,V2            ;convert to screen coordinates
;---	MOVE	  V1,VTOP	      ;assume (for now) v1 is top vertex
        MOVE      V2,VBOT             ;assume that v2 is bottom vertex

        CMPXY     VTOP,VBOT           ;v1.y == v2.y? (horizontal edge?)
        JRYZ      SKIP1               ;jump to discard horizontal edge
;
; Edge is not horizontal.  Identify top and bottom vertices of edge.
        JRYNN     GOT_VTOP            ;jump if v1 is top, v2 is bottom

        MOVE      V1,VBOT             ;else v1 is bottom vertex
        MOVE      V2,VTOP             ;and v2 is top vertex
GOT_VTOP:
;
; Initialize elements of next EDGE struct in edge array.
        MOVE      VBOT,TMP0           ;copy vertex vbot's xy coordinates
        SUBXY     VTOP,TMP0           ;(vbot.x-vtop.x, vbot.y-vtop.y)
        MOVX      TMP0,TMP1           ;copy vbot.x - vtop.x
        SLL       16,TMP1             ;(vbot.x - vtop.x) << 16
        SRA       16,TMP0             ;right justify (vbot.y - vtop.y)
        DIVS      TMP0,TMP1           ;dx=((vbot.x-vtop.x)<<16)/(vbot.y-vtop.y)
        MOVE      TMP1,*P(DX),0       ;edge->dx = dx
        MOVX      VTOP,TMP0           ;copy vtop.x
        SLL       16,TMP0             ;
        MOVX      ROUND,TMP0          ;(vtop.x << 16) + 0x7FFF;
        SRA       1,TMP1              ;dx/2
        ADD       TMP1,TMP0           ;xtop = (vtop.x << 16) + dx/2 + 0x7FFF
        MOVE      TMP0,*P(XTOP),0     ;save xtop in EDGE struct
        SRL       16,VTOP             ;right justify ytop = vtop.y
        MOVE      VTOP,*P(YTOP),1     ;save ytop in EDGE struct
        SRL       16,VBOT             ;right justify ybot = vbot.y
        MOVE      VBOT,*P(YBOT),1     ;save ybot in EDGE struct

        CALLR     Y_INSERT_LIST       ;insert edge *p into ysort_list

        ADD       SIZEOF,P            ;++p (point to next edge array item)
SKIP1:
        MOVE      V2,V1               ;v1 = v2 (save vertex for next loop)
        DSJ       N,INIT_LOOP         ;loop while --n != 0

; End of edge array initialization loop.
*-----------------------------------------------------------------------
; Outer loop below fills all trapezoids in ysort_list.
        CLR       XLIST               ;xsort_list = NULL
        MOVE      YLIST,YLIST         ;ysort_list == NULL pointer?
        JRZ       EXIT_OUTER          ;skip outer loop if ysort_list == N ULL

OUTER_LOOP:
        MOVE      *YLIST(YTOP),YSCAN,1 ;yscan = ysort_list->ytop
;
; Build xsort_list (list of edges active on current scan line).
BUILD_XLIST:
        MOVE      YLIST,YLIST         ;ysort_list == NULL pointer?
        JRZ       XLIST_BUILT         ;jump if ysort_list == NULL

        MOVE      *YLIST(YTOP),TMP0,1 ;get ysort_list->ytop
        CMP       TMP0,YSCAN          ;yscan == ysort_list->ytop?
        JRNE      XLIST_BUILT         ;jump if yscan != ysort_list->ytop?

        MOVE      YLIST,P             ;p = ysort_list
        MOVE      *P(NEXT),YLIST,0    ;ylist = p->next

        CALLR     X_INSERT_LIST       ;insert edge *p into xsort_list

        JR        BUILD_XLIST         ;loop again, insert next edge
XLIST_BUILT:
;
; Set initial y stop value to top of next edge in ysort_list.
        MOVI      INFINITY,YSTOP      ;default ystop = "+infinity"
        MOVE      YLIST,YLIST         ;ysort_list == NULL pointer?
        JRZ       GOT_YSTOP           ;jump if ysort_list == NULL

        MOVE      *YLIST(YTOP),YSTOP,1 ;ystop = ysort_list->ytop
GOT_YSTOP:
;
*-----------------------------------------------------------------------
; Each iteration below takes the next pair of edges, e1 and e2,
; from the x-sorted list (sorted in xtop-increasing order) and
; fills the trapezoid bounded by e1, e2, yscan and ystop:
        MOVE      XLIST,XLIST         ;xsort_list == NULL pointer?
	JRZ	  EXIT_MIDDLE	      ;jump if xsort_list == NULL
MIDDLE_LOOP:
;
; Remove the next two edges, e1 and e2, from the x-sorted list, where e1
; is the left edge of the trapezoid, and e2 is the right edge.
        MOVE      XLIST,E1            ;e1 = xsort_list
        MOVE      *E1(NEXT),E2,0      ;e2 = e1->next
        MOVE      *E2(NEXT),XLIST,0   ;xsort_list = e2->next
;
; Get xtop and inverse slope dx values for edges e1 and e2.
        MOVE      *E1(XTOP),X1,0      ;get fixed point x1
        MOVE      *E1(DX),DX1,0       ;get fixed point dx1
        MOVE      *E2(XTOP),X2,0      ;get fixed point x2
        MOVE      *E2(DX),DX2,0       ;get fixed point dx2
;
; If e1->ybot (y value at bottom of edge e1) is less than ystop, set
; ystop to e1->ybot.
        MOVE      *E1(YBOT),TMP0,1    ;get e1->ybot
        CMP       YSTOP,TMP0          ;e1->ybot < ystop?
        JRNN      YCOMP1              ;jump if e1->ybot >= ystop

        MOVE      TMP0,YSTOP          ;ystop = e1->ybot.
YCOMP1:
;
; If e2->ybot (y value at bottom of edge e2) is less than ystop, set
; ystop to e2->ybot.
        MOVE      *E2(YBOT),TMP0,1    ;get e2->ybot
        CMP       YSTOP,TMP0          ;e2->ybot < ystop?
        JRNN      YCOMP2              ;jump if e2->ybot >= ystop

        MOVE      TMP0,YSTOP          ;ystop = e2->ybot.
YCOMP2:
        MOVE      XLIST,XLIST         ;xsort_list = valid pointer?
        JRZ       EXIT_CHECK          ;jump if xsort_list = NULL
;
; The X_INTERCEPT routine called below sets TMP1 to the fixed-point x
; coordinate value at the intersection of edge p with y = ystop.
        MOVE      E2,P                ;load 1st arg for x_intercept
        CALLR     X_INTERCEPT         ;TMP1 = fixed-point x value

        MOVE      TMP1,XSTOP          ;save result in xstop
;
; For each edge p in xsort_list:
;   If point (xstop,ystop) falls on right side of edge p:
;     Set (xstop,ystop) = point where edge p intersects e2.
;     (But constrain ystop to nearest integer y coordinate.)
        MOVE      XLIST,P             ;p = xsort_list
        JRZ       EXIT_CHECK          ;break if p == NULL

CHECK_EDGE:
        MOVE      *P(DX),DX1,0        ;dx = p->dx
        SUB       DX2,DX1             ;dx - dx2
        JRNN      NO_INTERSECT        ;jump if dx2 <= dx
; The X_INTERCEPT routine called below sets TMP1 to the fixed-point x
; coordinate value at the intersection of edge p with y = ystop.
;---	MOVE	  P,P		      ;load arg for x_intercept routine
        CALLR     X_INTERCEPT         ;TMP1 = fixed-point x value

        CMP       XSTOP,TMP1          ;compare x intercept with e2's xstop value
        JRNN      NO_INTERSECT        ;jump if xstop <= x_intercept(p, ystop)
;
; Have confirmed that edge p intersects edge e2.  Calculate x and y
; coordinates at point of intersection.
        MOVE      *P(XTOP),DY,0       ;get x = p->xtop
        SUB       X2,DY               ;x - x2
        NEG       DX1                 ;dx2 - dx
        DIVS      DX1,DY              ;(x - x2)/(dx2 - dx)
        INC       DY                  ;dy = 1 + (x - x2)/(dx2 - dx)
        MOVE      YSCAN,YSTOP         ;
        ADD       DY,YSTOP            ;ystop = yscan + dy
        MOVE      DX2,XSTOP           ;
        MPYS      DY,XSTOP            ;
        ADD       X2,XSTOP            ;xstop = x2 + dy*dx2
NO_INTERSECT:
        MOVE      *P(NEXT),P,0        ;p = p->next
        JRNZ      CHECK_EDGE          ;loop while p != NULL
        MOVE      *E1(DX),DX1,0       ;restore dx1 for edge e1
EXIT_CHECK:
; End edge intersection check loop.
*-----------------------------------------------------------------------
; Fill trapezoid defined by yscan, ystop, e1 and e2.
        MOVE      YSTOP,COUNT         ;loop count = height of trapezoid
        SUB       YSCAN,COUNT         ;trapezoid height = ystop - yscan
        MOVE      YSCAN,Y             ;y = yscan
;
; Fill trapezoid with solid color or with pattern?
	MOVE	  FILLSRV,FILLSRV     ;pattern fill or solid fill?
	JRNZ	  PATN_FILL	      ;jump if pattern fill
;
; Use this version of inner loop to fill trapezoid with solid color.
SOLID_FILL:
        MOVY      X2,TMP0             ;copy integer part of x2
        SUBXY     X1,TMP0             ;subtract integer part of x1
        JRYN      END_FILL            ;jump if width = int(x2)-int(x1) < 0
;
        .if     GSP_34010 ; Code used if the processor is a 34010
        SRL       16,TMP0             ;right justify span width w
        MOVE      TMP0,BTMP           ;
        MOVX      BTMP,DYDX           ;set fill width = w
        MOVY      X1,Y                ;concatenate y with int(x1)
        MOVE      Y,DADDR             ;set fill address = (int(x1),y)
        RL        16,DADDR            ;swap x and y halves of register
        FILL      XY                  ;fill one horizontal span
        ADD       DX1,X1              ;x1 += dx1
        ADD       DX2,X2              ;x2 += dx2
        INC       Y                   ;++y
        DSJ       COUNT,SOLID_FILL    ;do inner loop while --count > 0
        .endif
;
        .if     GSP_34020 ; Code used if the processor is a 34020
        move      B0,TMP0
        move      X1,B0               ;set x1
        move      DX1,B1              ;set dx1
        move      X2,B7               ;set x2
        move      DX2,B10             ;set dx2
        move      Y,B11               ;set y coordinate
        sll       16,B11              ;make fixed point
TUF:
        cmp       B0,B7
        jrlt      tfill_done
        tfill XY
        dsj       COUNT,TUF
tfill_done:
        move      B0,X1
        move      B7,X2
        move      B11,Y
        srl       16,Y
        move      TMP0,B0
        .endif
        JR        END_FILL            ;otherwise, trapezoid complete
;
; Use this version of inner loop to fill trapezoid with pattern.
PATN_FILL:
	SETF	  32,0,1	      ;restore default field 1 size
PATN_FILL1:
        MOVY      X2,TMP0             ;copy integer part of x2
        SUBXY     X1,TMP0             ;subtract integer part of x1
	JRYN	  EXIT_PFILL	      ;jump if width = int(x2)-int(x1) < 0

        SRL       16,TMP0             ;right justify span width w
        MOVE      TMP0,BTMP           ;
        MOVX      BTMP,DYDX           ;set fill width = w
        MOVY      X1,Y                ;concatenate y with int(x1)
        MOVE      Y,DADDR             ;set fill address = (int(x1),y)
        RL        16,DADDR            ;swap x and y halves of register

        CALL      FILLSRV             ;pattern-fill one horizontal line

        ADD       DX1,X1              ;x1 += dx1
        ADD       DX2,X2              ;x2 += dx2
        INC       Y                   ;++y
	DSJ	  COUNT,PATN_FILL1    ;do inner loop while --count > 0
EXIT_PFILL:
        SETF      16,1,1              ;set up for 16-bit moves and mults
        SETF      32,0,0              ;set up for 32-bit moves
END_FILL:
        SEXT      Y,1                 ;remove garbage from 16 MSBs
        MOVE      X1,*E1(XTOP),0      ;e1->xtop = x1
        MOVE      Y,*E1(YTOP),1       ;e1->ytop = y
        MOVE      X2,*E2(XTOP),0      ;e2->xtop = x2
        MOVE      Y,*E2(YTOP),1       ;e2->ytop = y
;---	MOVE	  Y,YSTOP	      ;ystop = y (bottom of trapezoid)
; End trapezoid fill.
*-----------------------------------------------------------------------
; If ystop < e1->ybot, insert portion of edge e1 beneath
; filled region into ysort_list in order of increasing y.
        MOVE      *E1(YBOT),TMP0,1    ;get e1->ybot
        CMP       TMP0,YSTOP          ;compare e1->ybot to ystop
        JRNN      SKIP2               ;jump if ystop >= e1->ybot

        MOVE      E1,P                ;copy arg to y_insert_list function
        CALLR     Y_INSERT_LIST       ;insert edge *e1 into ysort_list
SKIP2:
;
; If ystop < e2->ybot, insert portion of edge e2 beneath
; filled region into ysort_list in order of increasing y.
        MOVE      *E2(YBOT),TMP0,1    ;get e2->ybot
        CMP       TMP0,YSTOP          ;compare e2->ybot to ystop
        JRNN      SKIP3               ;jump if ystop >= e2->ybot

        MOVE      E2,P                ;copy arg to y_insert_list function
        CALLR     Y_INSERT_LIST       ;insert edge *e2 into ysort_list
SKIP3:
;
; Middle loop test:  Loop while more edges begin on this scan line.
        MOVE      XLIST,XLIST         ;test xsort_list pointer
	JRNZ	  MIDDLE_LOOP	      ;loop while xsort_list != NULL
EXIT_MIDDLE:
; Exit middle loop.
*-----------------------------------------------------------------------
; Outer loop test.  Loop while more edges begin at lower scan lines.
        MOVE      YLIST,YLIST         ;test ysort_list pointer
        JRNZ      OUTER_LOOP          ;loop while ysort_list != NULL
EXIT_OUTER:
; Exit outer loop.
*-----------------------------------------------------------------------
; Restore registers and return.
        MOVE      *SP+,SP_INC         ;get system stack displacement
        ADD       SP_INC,SP           ;restore original SP
DONE:
        SETF      32,0,1              ;restore default field 1 size
        MMFM      SP,B0,B2,B3,B7,B10,B11,B12,B13,B14
	MMFM	  SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A12,A13
        MOVE      *SP(32),STK,1       ;restore program stack pointer
        RETS      2                   ;


*-----------------------------------------------------------------------
* LOCAL SUBROUTINE:
*
*      Find x intercept of edge *p with horizontal line y = ystop.
*
*-----------------------------------------------------------------------

X_INTERCEPT:

        MOVE      *P(YTOP),TMP0,1     ;get p->ytop
        MOVE      YSTOP,DY            ;get ystop
        SUB       TMP0,DY             ;dy = ystop - p->ytop;
        MOVE      *P(DX),TMP0,0       ;dx = p->dx
        MPYS      DY,TMP0             ;dy*dx
;
; No overflow.  Return x intercept value = p->xtop + dy*dx.
        MOVE      *P(XTOP),TMP0,0     ;get p->xtop
        ADD       TMP0,TMP1           ;set x = p->xtop + dy*dx
        RETS      0                   ;result x is in TMP1


*-----------------------------------------------------------------------
*  LOCAL SUBROUTINE:
*
*     Insert new edge *p into list sorted in xtop-ascending order.
*
*------------------------------------------------------------------------

X_INSERT_LIST:

        MOVE      XLIST,XLIST         ;xsort_list == NULL pointer?
        JRZ       XFIRST              ;jump if xsort_list == NULL
        MOVE      *P(XTOP),TMP0,0     ;get xsort_list->xtop
        MOVE      *XLIST(XTOP),TMP1,0 ;get xsort_list->xtop
        CMP       TMP0,TMP1           ;compare p->xtop to xsort_list->xtop
        JRN       XNOTFIRST           ;jump if p->xtop > xsort_list->xtop
;
; Insert new edge as first item in xsort_list.
XFIRST:
        MOVE      XLIST,*P(NEXT),0    ;p->next = xsort_list
        MOVE      P,XLIST             ;xsort_list = p
        RETS      0                   ;
;
; Insert new edge into xsort_list following first item in list.
XNOTFIRST:
        MOVE      XLIST,Q             ;q = xsort_list
XLOOP:
        MOVE      *Q(NEXT),R,0        ;r = q->next
        JRZ       XEXIT               ;exit loop if r == NULL
        MOVE      *R(XTOP),TMP1,0     ;get r->xtop
        CMP       TMP0,TMP1           ;compare p->xtop to r->xtop
        JRNN      XEXIT               ;exit loop if p->xtop >= r->xtop
        MOVE      R,Q                 ;q = r
        JR        XLOOP               ;examine next item in xsort_list
;
; Ready to insert new edge in xsort_list.
XEXIT:
        MOVE      R,*P(NEXT),0        ;p->next = r
        MOVE      P,*Q(NEXT),0        ;q->next = p
        RETS      0                   ;


*-----------------------------------------------------------------------
*  LOCAL SUBROUTINE:
*
*     Insert new edge *p into list sorted in ytop-ascending order.
*
*------------------------------------------------------------------------

Y_INSERT_LIST:

        MOVE      YLIST,YLIST         ;ysort_list == NULL pointer?
        JRZ       YFIRST              ;jump if ysort_list == NULL
        MOVE      *P(YTOP),TMP0,1     ;get ysort_list->ytop
        MOVE      *YLIST(YTOP),TMP1,1 ;get ysort_list->ytop
        CMP       TMP0,TMP1           ;compare p->ytop to ysort_list->ytop
        JRN       YNOTFIRST           ;jump if p->ytop > ysort_list->ytop
;
; Insert new edge as first item in ysort_list.
YFIRST:
        MOVE      YLIST,*P(NEXT),0    ;p->next = ysort_list
        MOVE      P,YLIST             ;ysort_list = p
        RETS      0                   ;
;
; Insert new edge into ysort_list following first item in list.
YNOTFIRST:
        MOVE      YLIST,Q             ;q = ysort_list
YLOOP:
        MOVE      *Q(NEXT),R,0        ;r = q->next
        JRZ       YEXIT               ;exit loop if r == NULL
        MOVE      *R(YTOP),TMP1,1     ;get r->ytop
        CMP       TMP0,TMP1           ;compare p->ytop to r->ytop
        JRNN      YEXIT               ;exit loop if p->ytop >= r->ytop
        MOVE      R,Q                 ;q = r
        JR        YLOOP               ;examine next item in ysort_list
;
; Ready to insert new edge in ysort_list.
YEXIT:
        MOVE      R,*P(NEXT),0        ;p->next = r
        MOVE      P,*Q(NEXT),0        ;q->next = p
        RETS      0                   ;

        .end

