        .width    132
        .title    '3D database interpreter'

*----------------------------------------------------------------------
*                                    TIGA
*          Copyright (C) 1989-1990  Texas Instruments Incorporated.
*                            All Rights Reserved
*----------------------------------------------------------------------
* dbinterp function
*
*    Interpret hierarchical database containing 3D objects for flight
*    simulator.  The output from this function is a list of polygons and
*    dots to be transformed and drawn to the screen.  This function is
*    designed to trivially reject 3D objects which are not visible on
*    the screen.  To this end, the function performs hidden surface
*    removal, clipping based on bounding spheres, elimination of
*    unnecessary detail from distant objects, and checking for objects
*    distant enough to permit perspective approximations to be used.
*
*    The two arguments are pointers rootnode and q.  Argument rootnode
*    points to the root node of the binary tree hierarchical 3D
*    database.  Argument q points to the output array, which is a list
*    of the polygons and points in 3D space that need to be transformed,
*    projected, and drawn to the screen.
*
*    The return value is a pointer to the end of the output list (that
*    is, a pointer to the first word BEYOND the end of the list).
*
*    Each iteration considers one node in the binary tree.  Each node
*    represents a cluster of polygons.  Included with each node is a
*    bounding sphere for the cluster characterized in terms of its
*    radius and center coordinates.  Each node is either a terminal
*    (leaf) or an intermediate (nonleaf) node.  A terminal node contains
*    the description of a 3D object composed of some number of polygons.
*    The left and right sons of a intermediate node represent the
*    division of the polygon cluster contained in that node into two
*    subclusters.  By convention, if an intermediate node has only one
*    descendant, that descendant is the left son; the pointer to the
*    right son is a nil pointer.
*
*    The hidden surface problem is solved by drawing objects in back-
*    to-front order (relative to the viewpoint).  This is known as the
*    Painter's Algorithm.  In the case in which an intermediate node in
*    the tree has two descendants, the more distant node (that is, the
*    objects contained in this node) is drawn before the closer node.
*    To facilitate this ordering, a binary partitioning plane (BPP) is
*    specified as a means of determining the order in which the two
*    nodes are drawn.  The BPP lies between the objects in the two
*    nodes.  If the viewpoint lies on the left son's side of the plane,
*    the right son is drawn first, and the left son second; otherwise,
*    the left son is drawn first.  The BPP is specified in terms of the
*    A, B, C and D coefficients of its plane equation,
*                        f(x,y,z) = Ax+By+Cz+D,
*    where the viewpoint is located at coordinates (x,y,z) relative to
*    the centroid of the current node.
*
*
*                     Intermediate Node Structure
*                     ---------------------------
*    The structure of an intermediate node in the binary tree database
*    is as follows:
*
*             field description                          field size
*            -------------------                        ------------
*             bounding sphere radius                          8
*             log2(scaling factor) for b.s. radius            5
*             node type = 0 (intermediate node)               3
*             color of distant, dot-sized node               16
*             pointer to leftson node                        32
*             xyz displacements to leftson's centroid        4*8
*             pointer to rightson node                       32
*             xyz displacements to rightson's centroid       4*8
*             partitioning plane coeff's A,B,C,D             4*4
*
*    The first 16 bits in the node stucture contain an 8-bit unsigned
*    bounding sphere radius R, a 5-bit log2(scaling factor) F, and a
*    3-bit node type specifier, N.  An intermediate node is identified
*    by N = 0.  The radius of the bounding sphere is calculated as
*    r = R << F, where "<<" is the C left-shift operator.
*
*    The second 16 bits specify the color of the node when it is so
*    distant that it occupies only a single pixel (a dot) on the screen.
*
*    Specified along with the pointers to the two descendant nodes, LSON
*    and RSON, are the xyz displacements of these nodes from the current
*    (FATHER) node.  These displacements are stored as 8-bit signed X, Y
*    and Z fields, followed by an 8-bit F field that specifies scaling
*    factor for X, Y and Z.  These four 8-bit values are packed into a
*    single 32-bit long word.  If the current node is centered at
*    coordinates (Xc, Yc, Zc), the descendant's center coordinates are
*    calculated as follows:  Xc' = Xc + (X << F), Yc' = Yc + (Y << F),
*    and Zc' = Zc + (Z << F).
*
*    The last word in the structure contains binary partitioning plane
*    coefficients A, B, C and D.  The objects or composite objects
*    represented by the leftson and rightson nodes are separated by a
*    plane whose equation is f(x,y,z) = A*x + B*y + C*z + D, where x, y
*    and z are the coordinates of the parent node's centroid in object
*    space relative to the viewpoint.  The plane equation is evaluated
*    to determine the proper order in which to draw the left and right
*    sons, based on the Painter's Algorithm.  If f(x,y,z) < 0, the
*    viewpoint is located on the left son's side of the partitioning
*    plane; the right son is drawn first, and the left son second.
*    Otherwise, the left son is drawn first.  The plane equation
*    coefficients are stored in a 16-bit longword containing 4-bit A, B,
*    C and D fields, each of which specifies a value in the range -128
*    to +127:
*
*                     15   12 11    8 7     4 3     0
*                    +-------+-------+-------+-------+
*                    |   D   |   C   |   B   |   A   |
*                    +-------+-------+-------+-------+
*
*
*                       Terminal Node Structure
*                       -----------------------
*    The structure of a terminal node in the binary tree database is as
*    follows:
*
*             field description                          field size
*            -------------------                        ------------
*             bounding sphere radius (unsigned)               8
*             log2(scaling factor) for b.s. radius            5
*             node type = -1 (terminal node)                  3
*             color of distant, dot-sized node               16
*             word displacement to bounding box data         16
*             <3D object model database>                  variable
*             <bounding box specification>                variable
*
*    The first 32 bits of the data structure are similar to that for the
*    intermediate node, except that the 3-bit node type field is set to
*    -1.
*
*    The second 16 bits contain a word displacement to the bounding box
*    specification.  Assuming that the 3D object model database begins
*    at address MODEL, and the bounding box specification begins at
*    address BBOX, the word displacement is stored as (BBOX-MODEL)/16.
*
*
*                          Output List Format
*                          ------------------
*   Argument p is a pointer to the output list, or transform list, which
*   is a list of polygons and dots to be transformed.  The specification
*   for each polygon or dot begins on an even 16-bit boundary in memory,
*   and the first item in each specification is a function code
*   indicating the type of graphics primitive.
*
*   The transform list is terminated by a function code of -1.
*
*   Two types of polygon may be specified in the input list:  "near" and
*   "far" polygons.  Near polygons must be preclipped; that is, they are
*   clipped to the viewport limits before being drawn.  Far polygons, on
*   the other hand, are postclipped; that is, they are clipped on a
*   line-by-line basis as they are drawn.  The division of polygons into
*   near and far types are for the purpose of computational efficiency.
*
*   Postclipping is used for small polygons.  Because preclipping
*   polygons involves some overhead, postclipping the smaller ones
*   avoids this overhead, allowing the GSP's built-in clipping hardware
*   to do the clipping automatically as each horizontal fill line is
*   drawn.
*
*   Larger polygons, however, are more efficiently dealt with by
*   preclipping, which cuts off parts of each polygon lying outside the
*   viewport which would otherwise consume considerable time during the
*   drawing phase.
*
*   Near and far polygons are specified in the tranform list by function
*   codes of 1 and 2, respectively.  The transform list specification
*   for a polygon is as follows:
*
*         16-bit function code:          1 (near) or 2 (far)
*         16-bit constant:               0
*         32-bit FIX8 x centroid coord:  xv
*         32-bit FIX8 y centroid coord:  yv
*         32-bit FIX8 z centroid coord:  zv
*         32-bit pointer to model data:  obj
*
*   Parameters xv, yv and zv are the object's centroid coordinates in
*   viewing space.  Each is represented as a 32-bit fixed-point number
*   with 8 bits of fraction.  The obj parameter is a 32-bit pointer to
*   the object model database.  The database begins with a 16-bit count
*   indicating the number of 3D points to follow.  Each point is
*   specified as a 32-bit value containing 8-bit X, Y, Z and F fields.
*   The F field specifies the logarithm to the base 2 of the scaling
*   constant for the X, Y and Z values, and is restricted to the range 0
*   to 7.  The X, Y and Z values are restricted to the range -128 to
*   +127, and after being read from the database are scaled by being
*   shifted left by F bits:  x = X << F, y = Y << F, and z = Z << F.
*
*   A "dot" is a single pixel, and is specified in the transform list by
*   a function code of 0.  The transform list format specifying a dot is
*   as follows:
*
*             16-bit function code:    0
*             16-bit dot color:        color
*             16-bit x coordinate:     xs
*             16-bit y coordinate:     ys
*
*   The second item in the specification is a 16-bit value specifying
*   the dot color.  The last two items are the x and y coordinates of
*   the dot, specified as 16-bit integers.  Note that these are the x
*   and y coordinates of the dot on the screen; in other words they have
*   been transformed and projected onto the screen before being placed
*   into the transform list.
*
*-----------------------------------------------------------------------
*  Usage:  short *p;
*          p = dbinterp(rootnode, q);
*
*  Stack parameters:
*      GRAPHNODE *rootnode;  /* root node in 3D object tree */
*      short *q;             /* pointer to output (transform) list */
*
*  Returned in A8:  pointer to end of output list
*
*  Registers altered:  A8
*-----------------------------------------------------------------------
*  Revision History:
*    01/31/89...Original version written..................Jerry Van Aken
*-----------------------------------------------------------------------
*
*
*   DECLARE GLOBAL FUNCTION NAME
*
        .globl    _dbinterp           ;global function entry point
*
*
*   DECLARE EXTERNAL VARIABLES AND SUBROUTINES
*
        .globl    _view               ;viewpoint parameters
        .globl    _vpclip             ;viewport clipping parameters
        .globl    _ztest              ;z distance check parameters
*
*
*   DEFINE CONSTANTS
*
        .nolist
        .copy     "fly3d.inc"         ;define flight sim. structures
        .list
; Symbolic A-file register names
TMP0    .set      A0                  ;temporary register 0
TMP1    .set      A1                  ;temporary register 1
TMP2    .set      A2                  ;temporary register 2
TMP3    .set      A3                  ;temporary register 3
FACT    .set      A4                  ;log2(scale factor) :: node type
RTDISP  .set      A4                  ;RSON xyz displacement coord's
RTSON   .set      A5                  ;pointer to RSON of this node
ZDIVR   .set      A5                  ;ratio of z distance over radius
ZVTMP   .set      A5                  ;temporary storage for zv
R       .set      A6                  ;radius of bounding sphere
LFDISP  .set      A6                  ;LSON xyz displacement coord's
LFSON   .set      A7                  ;pointer to LSON of this node
ZVPR    .set      A7                  ;ZV+R (max. z depth of bd. sphere)
NODE    .set      A8                  ;pointer to current node
DCBA    .set      A8                  ;binary partitioning plane coeff's
ZC      .set      A9                  ;object centoid z coordinate
YC      .set      A10                 ;object centoid y coordinate
XC      .set      A11                 ;object centoid x coordinate
VDIST   .set      A12                 ;viewer's distance to screen
NEAR    .set      A13                 ;Znear ("hither") clipping plane
STK     .set      A14                 ;program stack pointer
; Symbolic B-file register names
T       .set      B0                  ;pointer to output (transf'm) list
BTMP0   .set      B1                  ;temporary B-file register 0
ZVIEW   .set      B1                  ;centroid z in viewing space
YVIEW   .set      B2                  ;centroid y in viewing space
XVIEW   .set      B3                  ;centroid x in viewing space
BTMP1   .set      B4                  ;temporary B-file register 1
XS      .set      B4                  ;screen x coordinate
BTMP2   .set      B5                  ;temporary B-file register 2
YS      .set      B5                  ;screen y coordinate
WZZ     .set      B6                  ;z component of unit vector W
WYY     .set      B7                  ;y component of unit vector W
WXX     .set      B8                  ;x component of unit vector W
VZZ     .set      B9                  ;z component of unit vector V
VYY     .set      B10                 ;y component of unit vector V
VXX     .set      B11                 ;x component of unit vector V
UZZ     .set      B12                 ;z component of unit vector U
UYY     .set      B13                 ;y component of unit vector U
UXX     .set      B14                 ;x component of unit vector U
*
*
*   ENTRY POINT
*
_dbinterp:

        SETF      16,1,0              ;set up for 16-bit memory moves
        MMTM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
        MMTM      SP,B0,B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14
; Get pointers to viewpoint orientation and position in object space.
        MOVI      _view,T             ;get ptr to UVW orientation vectors
        MMFM      T,UXX,UYY,UZZ,VXX,VYY,VZZ,WXX,WYY,WZZ ;UVW vectors
        MOVE      T,TMP0              ;copy ptr to viewpoint xyz coord's
        MMFM      TMP0,XC,YC,ZC       ;fetch viewpoint position coord's
; Calculate coordinates of object space origin relative to viewpoint.
        NEG       XC                  ;Xc' = -Xc
        NEG       YC                  ;Yc' = -Yc
        NEG       ZC                  ;Zc' = -Zc
; Get z value at Znear (or "hither") clipping plane in viewing space.
        MOVE      @_vpclip+ZNEAR,NEAR,0 ;get z "near" clipping plane
        SLL       6,NEAR              ;convert to FIX6
; Get viewer's assumed distance from screen for perspective calculations
        MOVE      @_vpclip+D,VDIST,0  ;get viewer's dist. d from screen
        SLL       6,VDIST             ;convert d to FIX6
; Pop 2 arguments off the program stack.
        MOVE      *-STK,NODE,1        ;get root node of hierarchical database
        MOVE      *-STK,TMP0,1        ;get ptr to output transform list
        MOVE      TMP0,T              ;save copy of output pointer
; Initialize stack to be used for node pointers and xyz coord's.
        CLR       TMP0                ;NIL node pointer at stack bottom
        MOVE      TMP0,*STK+,1        ;push NIL onto stack
; Root node == NIL?  If so, done.
        MOVE      NODE,NODE           ;check pointer to root node
        JRNZ      NEXTNODE            ;jump if node != NIL


*-----------------------------------------------------------------------
*               All done; restore registers and return.
*-----------------------------------------------------------------------
DONE:
        MOVI      -1,BTMP0            ;terminate draw list with EOD code
        MOVE      BTMP0,*T+,0         ;push EOD code onto top of heap
        MOVE      T,A8                ;return ptr to end of output list
        MMFM      SP,B0,B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14
        MMFM      SP,A0,A1,A2,A3,A4,A5,A6,A7,A9,A10,A11,A12,A13
        MOVE      *SP(32),STK,1       ;update program stack pointer
        RETS      2                   ;

        .align                        ;align start loop with cache

*-----------------------------------------------------------------------
* Each iteration of the loop below evaluates one node in the
* hierarchical 3D object database.
*-----------------------------------------------------------------------
POPNODE:
        MOVE      *-STK,NODE,1        ;get pointer to next node
        JRZ       DONE                ;done if node == NIL
        MOVE      *-STK,XC,1          ;pop centroid coordinate Xc (FIX8)
        MOVE      *-STK,YC,1          ;pop centroid coordinate Yc (FIX8)
        MOVE      *-STK,ZC,1          ;pop centroid coordinate Zc (FIX8)
NEXTNODE:
; Transform node's z center coordinate to viewing space.
        MOVE      WXX,TMP0            ;get x component, Wx (FIX30)
        MPYS      XC,TMP0             ;Xc * Wx (FIX8 times FIX30)
        MOVE      WYY,TMP2            ;get y component, Wy (FIX30)
        MPYS      YC,TMP2             ;Yc * Wy (FIX8 times FIX30)
        ADD       TMP3,TMP1           ;
        ADDC      TMP2,TMP0           ;Xc * Wx + Yc * Wy
        MOVE      WZZ,TMP2            ;get z component, Wz (FIX30)
        MPYS      ZC,TMP2             ;Zc * Wz (FIX8 times FIX30)
        ADD       TMP3,TMP1           ;
        ADDC      TMP2,TMP0           ;
        MOVE      TMP0,ZVIEW          ;zv = Xc*Wx + Yc*Wy + Zc*Wz (FIX6)
; Get radius of bounding sphere enclosing all objects in this node.
        MOVB      *NODE,R             ;get bounding sphere radius, BSRAD
        MOVE      *NODE+,FACT,0       ;get log2(scale factor) for BSRAD
        SRL       8,FACT              ;right justify scale factor F
        SLL       FACT,R              ;multiply radius by scale factor
        SLL       6,R                 ;convert radius to FIX6 format
; Is object 100% behind viewer (and therefore not visible)?
        MOVE      NEAR,TMP2           ;get z "near" clip plane
        SUB       TMP0,TMP2           ;subtract zv
        SUB       R,TMP2              ;is znear < zv + r ?
        JRNN      POPNODE             ;jump if znear >= zv + r
; Calculate ratio zv/r = z distance to bounding sphere over radius.
        MOVE      ZVIEW,ZDIVR         ;get z center coord. in view space
        DIVS      R,ZDIVR             ;zv/r (integer result)
*---    JRV       POPNODE             ;jump if zv much larger than r
; Is object too distant to be visible (zv/r > ztest.kvis)?
        MOVE      @_ztest+KVIS,TMP2,0 ;get ztest.kvis
        CMP       ZDIVR,TMP2          ;zv/r <= ztest.kmax ?
        JRN       POPNODE             ;jump if zv/r > ztest.kmax
; Calculate z depth at most distant point of bounding sphere.
        MOVE      ZVIEW,ZVPR          ;copy center z
        ADD       R,ZVPR              ;zv+r (FIX6)
; Calculate perspective-scaled radius r (as projected onto screen).
        MOVE      R,TMP0              ;copy r (FIX6)
        MPYS      VDIST,TMP0          ;d * r (FIX6 times FIX6)
        DIVS      ZVPR,TMP0           ;r' = d * r / (zv + r)
        MOVE      TMP0,R              ;save scaled r' (FIX6)
; Transform node's x center coordinate to viewing space.
        MOVE      UXX,TMP0            ;get Ux (FIX30)
        MPYS      XC,TMP0             ;Xc * Ux (FIX8 times FIX30)
        MOVE      UYY,TMP2            ;get Uy (FIX30)
        MPYS      YC,TMP2             ;Yc * Uy (FIX8 times FIX30)
        ADD       TMP3,TMP1           ;
        ADDC      TMP2,TMP0           ;Xc * Ux + Yc * Uy
        MOVE      UZZ,TMP2            ;get Uz (FIX30)
        MPYS      ZC,TMP2             ;Zc * Uz (FIX8 times FIX30)
        ADD       TMP3,TMP1           ;
        ADDC      TMP2,TMP0           ;
        MOVE      TMP0,XVIEW          ;xv = Xc*Ux + Yc*Uy + Zc*Uz (FIX6)
; Calculate perspective-scaled x center coordinate xs (screen coord.)
        MPYS      VDIST,TMP0          ;d * xv (FIX6 times FIX6)
        DIVS      ZVPR,TMP0           ;xs = d * xv / (zv + r)
        MOVE      TMP0,XS             ;save scaled xs (FIX6)
; Does object lie 100% to left or right of viewport?
        MOVE      @_vpclip+SX,TMP2,0  ;get viewport half width Sx
        SLL       6,TMP2              ;convert Sx from integer to FIX6
        ADD       R,TMP2              ;Sx + r
        ADD       TMP0,TMP2           ;Sx + r + xs >= 0 (inside left edge) ?
        JRN       POPNODE             ;jump if object to left of viewport
        SUB       TMP0,TMP2           ;subtract xs
        SUB       TMP0,TMP2           ;Sx + r - xs >= 0 (inside right edge) ?
        JRN       POPNODE             ;jump if object to right of viewport
; Transform node's y center coordinate to viewing space.
        MOVE      VXX,TMP0            ;get Vx (FIX30)
        MPYS      XC,TMP0             ;Xc * Vx (FIX8 times FIX30)
        MOVE      VYY,TMP2            ;get Vy (FIX30)
        MPYS      YC,TMP2             ;Yc * Vy (FIX8 times FIX30)
        ADD       TMP3,TMP1           ;
        ADDC      TMP2,TMP0           ;Xc * Vx + Yc * Vy
        MOVE      VZZ,TMP2            ;get Vz (FIX30)
        MPYS      ZC,TMP2             ;Zc * Vz (FIX8 times FIX30)
        ADD       TMP3,TMP1           ;
        ADDC      TMP2,TMP0           ;
        MOVE      TMP0,YVIEW          ;yv = Xc*Vx + Yc*Vy + Zc*Vz (FIX6)
; Calculate perspective-scaled x center coordinate ys (screen coord.)
        MPYS      VDIST,TMP0          ;d * yv (FIX6 times FIX6)
        DIVS      ZVPR,TMP0           ;ys = d * yv / (zv + r)
        MOVE      TMP0,YS             ;save scaled ys (FIX6)
; Does object lie 100% above or below viewport?
        MOVE      @_vpclip+SY,TMP2,0  ;get viewport half height Sy
        SLL       6,TMP2              ;convert Sy from integer to FIX6
        ADD       R,TMP2              ;Sy + r
        ADD       TMP0,TMP2           ;Sy + r + ys >= 0 (inside top edge) ?
        JRN       POPNODE             ;jump if object above viewport
        SUB       TMP0,TMP2           ;subtract ys
        SUB       TMP0,TMP2           ;Sy + r - ys >= 0 (inside bottom edge) ?
        JRN       POPNODE             ;jump if object below viewport
; Is object small enough to be represented as a single pixel?
        MOVE      @_ztest+KDOT,TMP0,0 ;get ztest.kdot
        CMP       ZDIVR,TMP0          ;zv/r > ztest.kdot (single pixel) ?
        JRNN      NOTADOT             ;jump if object is not just a dot
; Yes, append command to draw a dot to the output (transform) list.
        MOVE      *NODE+,TMP0,0       ;get dot COLOR code
        MOVE      TMP0,BTMP0          ;copy COLOR
        SLL       16,BTMP0            ;set 16 LSBs to DRAWCODE=0 (dot)
        MOVE      BTMP0,*T+,1         ;copy DRAWCODE and COLOR to list
        ADDK      32,XS               ;add 1/2 to FIX6 x value
        SRA       6,XS                ;round off x to nearest integer coord.
        ADDK      32,YS               ;add 1/2 to FIX6 y value
        SLL       10,YS               ;round off y to nearest integer coord.
        MOVY      YS,XS               ;concatenate x and y coordinates
        MOVE      @_vpclip+CX,BTMP0,1 ;get viewport center coord's Cx, Cy
        ADDXY     BTMP0,XS            ;convert x and y to absolute coord's
        MOVE      XS,*T+,1            ;copy dot x and y coord's to list
        JR        POPNODE             ;more 3D object nodes to process?

; Is current node is terminal (leaf) or intermediate (nonleaf) node?  If
; terminal node, specify the object to be drawn in the output
; (transform) list.  Otherwise, descend to next level in binary tree.
NOTADOT:
        BTST      5,FACT              ;is this a terminal (leaf) node?
        JRZ       NONLEAF             ;jump if intermed. (nonleaf) node
; This is a leaf node.  Append description of 3D object to output list.
; Also specify whether the object's projection on the screen is so large
; as to require preclipping of all polygons in the object.
        ADDK      32,NODE             ;increment pointer past bbox disp.
        MOVE      NODE,BTMP1          ;copy ptr to object model database
        SLL       2,XVIEW             ;convert xv from FIX6 to FIX8
        SLL       2,YVIEW             ;convert yv from FIX6 to FIX8
        SLL       2,ZVIEW             ;convert zv from FIX6 to FIX8
        MOVK      2,BTMP2             ;DRAWCODE=2: POSTclipped "far" object
        MOVE      @_ztest+KNPC,TMP0,0 ;get preclip threshold value
        CMP       ZDIVR,TMP0          ;zv/r > ztest.knpc (avoid preclipping)?
        JRN       ISFAR               ;jump if preclip NOT necessary
        MOVK      1,BTMP2             ;DRAWCODE=1: PREclipped "near" object
ISFAR:
        MOVE      BTMP2,*T+,1         ;append DRAWCODE to list
        MOVE      XVIEW,*T+,1         ;append xv to output list
        MOVE      YVIEW,*T+,1         ;append yv to output list
        MOVE      ZVIEW,*T+,1         ;append zv to output list
        MOVE      BTMP1,*T+,1         ;append pointer to output list
        JR        POPNODE             ;more 3D nodes to process?

; (----- 34010 instruction cache miss occurs beyond this point. -------)

; Painter's algorithm is used to solve the hidden surface problem.  Does
; this node have two descendant nodes (left and right sons)?  If so,
; schedule the objects in the more distant node to be drawn before the
; objects in the nearer one.  To this end, the database specifies a
; binary partitioning plane (BPP) between each pair of descendants.  The
; viewpoint coordinates are plugged into the BPP equation to determine
; which of the two descendants to draw first.
NONLEAF:
        ADDK      16,NODE             ;increment pointer past dot color
        MOVE      NODE,TMP0           ;copy pointer to LSON offset
        MMFM      NODE,LFSON,LFDISP,RTSON,RTDISP ;get info on 2 sons
        ADD       TMP0,LFSON          ;convert offset to abs address
        MOVE      RTSON,RTSON         ;is RSON pointer==NIL ? (2 sons?)
        JRZ       ONESON              ;jump if RSON == NIL (just 1 son)
        ADDI      RSON-LSON,TMP0      ;point to right son offset
        ADD       TMP0,RTSON          ;convert offset to abs address

; This node has two descendants.  Determine which to draw first by
; plugging viewpoint coordinates into equation for plane that separates
; the left and right sons.  Equation has form F(x,y,z) = Ax+By+Cz+D.
; The four 4-bit coefficients A, B, C and D are packed into one word.
        MOVE      *NODE,DCBA,0        ;get plane eq'n coeff's A,B,C,D
        SETF      4,0,1               ;set up for 4-bit multipliers
        MOVE      XC,TMP1             ;copy centroid x coordinate
        SRA       4,TMP1              ;convert xc from FIX8 to FIX4
        MPYS      DCBA,TMP1           ;A*xc
        SRA       4,DCBA              ;right justify coefficient B
        JRZ       ZERO                ;jump if B = C = D = 0
        MOVE      YC,TMP3             ;copy centroid y coordinate
        SRA       4,TMP3              ;convert yc from FIX8 to FIX4
        MPYS      DCBA,TMP3           ;B*yc
        ADD       TMP3,TMP1           ;A*xc+B*yc
        SRA       4,DCBA              ;right justify coefficient C
        JRZ       ZERO                ;jump if C = D = 0
        MOVE      ZC,TMP3             ;copy centroid z coordinate
        SRA       4,TMP3              ;convert zc from FIX8 to FIX4
        MPYS      DCBA,TMP3           ;C*zc
        ADD       TMP3,TMP1           ;A*xc+B*yc+C*zc
        SRA       4,DCBA              ;right justify coefficient D
ZERO:
        SETF      32,0,1              ;restore field size 1 to default
        ADD       DCBA,TMP1           ;f(xc,yc,zc) = A*xc+B*yc+C*zc+D
        JRN       PUSHLSON            ;push LSON if f(xc,yc,zc) < 0

; RSON has higher priority, so push it onto stack; draw LSON first.
        MOVE      LFSON,TMP0          ;
        MOVE      RTSON,LFSON         ;swap LSON and RSON pointers
        MOVE      TMP0,RTSON          ;
        MOVE      LFDISP,TMP0         ;
        MOVE      RTDISP,LFDISP       ;swap LDISP and RDISP values
        MOVE      TMP0,RTDISP         ;

; Push nearer descendant onto stack so it can be drawn second.
PUSHLSON:
        MOVE      LFDISP,TMP0         ;copy x displacement (in 8 LSBs)
        SLL       24,TMP0             ;left justify 8-bit x displacement
        SRL       8,LFDISP            ;right justify 8-bit y displacem't
        MOVE      LFDISP,TMP1         ;copy y displacement (in 8 LSBs)
        SLL       24,TMP1             ;left justify 8-bit y displacement
        SRL       8,LFDISP            ;right justify 8-bit z displacem't
        MOVE      LFDISP,TMP2         ;copy z displacement (in 8 LSBs)
        SLL       24,TMP2             ;left justify 8-bit z displacement
        SRL       8,LFDISP            ;right justify log2(scale factor)
        SUBK      16,LFDISP           ;add factor for conversion to FIX8
        SRA       LFDISP,TMP0         ;scale x displacement (FIX8)
        SRA       LFDISP,TMP1         ;scale y displacement (FIX8)
        SRA       LFDISP,TMP2         ;scale z displacement (FIX8)
        ADD       XC,TMP0             ;add displacement to x coordinate
        ADD       YC,TMP1             ;add displacement to y coordinate
        ADD       ZC,TMP2             ;add displacement to z coordinate
        MOVE      TMP2,*STK+,1        ;push Zc + z displacement onto stack
        MOVE      TMP1,*STK+,1        ;push Yc + y displacement onto stack
        MOVE      TMP0,*STK+,1        ;push Xc + x displacement onto stack
        MOVE      LFSON,*STK+,1       ;push pointer to nearer descendant
; Prepare to process farther descendant node so it can be drawn first.
ONESON:
        MOVE      RTDISP,TMP0         ;copy x displacement (in 8 LSBs)
        SLL       24,TMP0             ;left justify 8-bit x displacement
        SRL       8,RTDISP            ;right justify 8-bit y displacem't
        MOVE      RTDISP,TMP1         ;copy y displacement (in 8 LSBs)
        SLL       24,TMP1             ;left justify 8-bit y displacement
        SRL       8,RTDISP            ;right justify 8-bit z displacem't
        MOVE      RTDISP,TMP2         ;copy z displacement (in 8 LSBs)
        SLL       24,TMP2             ;left justify 8-bit z displacement
        SRL       8,RTDISP            ;right justify log2(scale factor)
        SUBK      16,RTDISP           ;add factor for conversion to FIX8
        SRA       RTDISP,TMP0         ;scale x displacement (FIX8)
        SRA       RTDISP,TMP1         ;scale y displacement (FIX8)
        SRA       RTDISP,TMP2         ;scale z displacement (FIX8)
        ADD       TMP0,XC             ;add displacement to x coordinate
        ADD       TMP1,YC             ;add displacement to y coordinate
        ADD       TMP2,ZC             ;add displacement to z coordinate
        MOVE      RTSON,NODE          ;update ptr to farther descendant
        JR        NEXTNODE            ;process farther descendant node

        .end

