        .width    132
        .title    'inside bounding box'

*----------------------------------------------------------------------
*                                    TIGA
*          Copyright (C) 1989-1990  Texas Instruments Incorporated.
*                            All Rights Reserved
*----------------------------------------------------------------------
* inbbox function
*
*    This function determines whether the specified point in 3D space is
*    inside or outside the bounding for a 3D object.  Collision
*    detection is based on bounding boxes in object space.  To simplify
*    comparisons, box edges are constrained to be parallel to the x, y
*    and z axes.
*
*    Argument xyz is a pointer to an array containing the x, y and z
*    coordinates (in that order) of the 3D point.  Coordinates are
*    specified as 32-bit fixed-point values with 8 bits of fraction.
*    Argument rootnode is a pointer to the root node of the hierarchical
*    object database.
*
*    The value returned is the status code (specified within the
*    database) associated with the bounding box containing the
*    designated position.  A value of 0 is returned if the position lies
*    outside all bounding boxes specified in the database.
*
*    Each bounding box in the database is specified according to the
*    following format:
*
*       Bounding box format:
*                 bounding box test mode                     16 (below)
*                 status value                               16
*                 Xmin, Ymin, Zmin and scale factor F        4*8
*                 Xmax, Ymax, Zmax and scale factor F        4*8
*
*    A 16-bit status value is specified in the database; its meaning is
*    assigned by the application writer.  This status value is returned
*    as the result of the bounding box test in the event that the
*    bounding box test yields positive.
*
*    Three bounding box test modes are available:  outside box, inside
*    box, and unconditional.  The test mode is specified by the TM field
*    in bits 14-15 of the test mode word. If desired, the bounding box
*    can be padded by an amount equal to the z value (relative to the
*    viewpoint) at the "near" clipping plane.  Padding can be used, for
*    example, to prevent the viewer from penetrating (i.e., clipping in
*    the z dimension) polygons representing the faces of solid objects.
*    Positive, negative or zero padding is specified by the PM field in
*    bits 12-13 of the test mode word.
*
*     15 14 13 12 11                                0
*    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+    TEST MODE
*    | TM  | PM  |                0                  |      WORD
*    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
*       |     |
*       |     |
*       |     +------ PAD MODE:  00 = no padding of bounding box
*       |                        10 = add padding to bounding box
*       |                        11 = subtract padding from bounding box
*       |                        01 = undefined
*       |
*       +------ TEST MODE:  00 = return status value unconditionally
*                           10 = if INSIDE bounding box, return status
*                                value; else continue to next test
*                           11 = if OUTSIDE bounding box, return status
*                                value; else continue to next test
*                           01 = undefined
*
*    The dimensions of each bounding box are specified in two 32-bit
*    longwords.  The first longword specifies the minimum x, y and z
*    values, and the second specifies the maximum x, y and z values.
*    Each longword contains 8-bit X, Y and Z values, and an 8-bit
*    scaling factor (actually, log2 of the scaling factor), F.  The x, y
*    and z values are calculated as X<<F, Y<<F and Z<<F, where "<<" is
*    the C left-shift operator.
*-----------------------------------------------------------------------
*  Usage:  int inbbox(xyz, rootnode);
*
*  Stack parameters:
*      typedef long FIX8;     /* fixed-point with 8-bit fraction */
*      FIX8 xyz[3];           /* xyz coordinates */
*      GRAPHNODE *rootnode;   /* pointer to root node of tree */
*-----------------------------------------------------------------------
*  History:
*      01/31/89...Original version written...................J. Van Aken
*-----------------------------------------------------------------------
;
;
;   DECLARE GLOBAL FUNCTION NAME
;
        .globl    _inbbox
;
;
;   DECLARE EXTERNAL VARIABLES
;
        .globl    _vpclip             ;viewport clipping parameters
;
;
;   DEFINE CONSTANTS
;
        .nolist
        .copy     "fly3d.inc"         ;define flight sim. structures
        .list
; Number of bits of fraction in fixed-point numbers
FSIZE   .set      8                   ;32-bit no. with 8-bit fraction
; Define symbolic register names.
P       .set      A0                  ;database pointer
NODE    .set      A1                  ;binary tree node pointer
Q       .set      A1                  ;next pointer value
ZC      .set      A2                  ;object centroid z coordinate
YC      .set      A3                  ;object centroid y coordinate
XC      .set      A4                  ;object centroid x coordinate
LFSON   .set      A8                  ;pointer to node's left son
STAT    .set      A8                  ;bounding box's status code
TMP0    .set      A10                 ;temporary register 0 (even)
TMP1    .set      A11                 ;temporary register 1 (odd)
TMP2    .set      A12                 ;temporary register 2 (even)
TMP3    .set      A13                 ;temporary register 3 (odd)
RTSON   .set      A14                 ;pointer to node's right son
PAD     .set      A14                 ;padding for bounding box x,y,z
STK     .set      A14                 ;program stack pointer
;
;
;   ENTRY POINT
;
_inbbox:

        SETF      16,1,0              ;set up for 16-bit memory moves
        MMTM      SP,A0,A1,A2,A3,A4,A10,A11,A12,A13

; Pop both arguments off program stack.
        MOVE      -*STK,P,1           ;get argument xyz (pointer)
        MOVE      -*STK,NODE,1        ;get argument rootnode (pointer)

; Get coordinates of world xyz origin relative to viewpoint.
        CLR       TMP0                ;constant 0
        MMFM      P,XC,YC,ZC          ;get position coordinates
        SRA       8,XC                ;convert from FIX8 to integer
        ADDC      TMP0,XC             ;round up
        NEG       XC                  ;convert to viewpoint-relative
        SRA       8,YC                ;convert from FIX8 to integer
        ADDC      TMP0,YC             ;round up
        NEG       YC                  ;convert to viewpoint-relative
        SRA       8,ZC                ;convert from FIX8 to integer
        ADDC      TMP0,ZC             ;round up
        NEG       ZC                  ;convert to viewpoint-relative

; Each loop descends one level in tree by stepping to lson or rson.
LOOP1:
        MOVE      *NODE,TMP0,0        ;get object radius and node type
        BTST      13,TMP0             ;check node type
        JRNZ      ISLEAF              ;jump if terminal (leaf) node
      move      NODE,TMP0           ;copy node base address
      addi      LSON,TMP0           ;point to LSON offset value
      move      *TMP0,LFSON,1       ;fetch offset
      add       TMP0,LFSON          ;convert offset to abs address
      addi      RSON-LSON,TMP0      ;point to RSON offset value
      move      *TMP0,RTSON,1       ;fetch offset
      jrz       GOLEFT              ;jump if RSON offset is NIL
      add       TMP0,RTSON          ;convert offset to abs address

;       MOVE      *NODE(LSON),LFSON,1 ;get pointer to left son of node
;       MOVE      *NODE(RSON),RTSON,1 ;get pointer to right son of node
;       JRZ       GOLEFT              ;if rson == NIL, descend to lson

; On which side of plane separating lson and rson is viewpoint?
        MOVE      *NODE(BPP),TMP0,0   ;get binary partitioning plane
        SETF      4,0,1               ;set up for 4-bit multipliers
        MOVE      XC,TMP1             ;copy centroid x coordinate
        MPYS      TMP0,TMP1           ;A*xc
        SRA       4,TMP0              ;right justify coefficient B
        JRZ       ZERO                ;jump if B = C = D = 0
        MOVE      YC,TMP3             ;copy centroid y coordinate
        MPYS      TMP0,TMP3           ;B*yc
        ADD       TMP3,TMP1           ;A*xc+B*yc
        SRA       4,TMP0              ;right justify coefficient C
        JRZ       ZERO                ;jump if C = D = 0
        MOVE      ZC,TMP3             ;copy centroid z coordinate
        MPYS      TMP0,TMP3           ;C*zc
        ADD       TMP3,TMP1           ;A*xc+B*yc+C*zc
        SRA       4,TMP0              ;right justify coefficient D
ZERO:
        ADD       TMP0,TMP1           ;f(xc,yc,zc) = A*xc+B*yc+C*zc+D
        JRLT      GOLEFT              ;jump if f(xc,yc,zc) > 0

; Get ready to descend to right son of current node.
        MOVE      RTSON,P             ;get ready to descend to rson
        ADDI      RDISP,NODE          ;point to rson's xyz displacements
        JRUC      DESCEND             ;

; Get ready to descend to left son of current node.
GOLEFT:
        MOVE      LFSON,P             ;get ready to descend to lson
        ADDI      LDISP,NODE          ;point to lson's xyz displacements
; Descend to next lower level in tree. Get node centroid coordinates.
DESCEND:
        SETF      8,1,1               ;set up for 8-bit memory moves
        MOVE      *NODE+,TMP0,1       ;x displacement to son's center
        MOVE      *NODE+,TMP1,1       ;y displacement to son's center
        MOVE      *NODE+,TMP2,1       ;z displacement to son's center
        MOVE      *NODE+,TMP3,1       ;log2(scaling factor) for xyz vals

        SLL       TMP3,TMP0           ;"multiply" x by scaling factor
        ADD       TMP0,XC             ;add x displacement to x coord.

        SLL       TMP3,TMP1           ;"multiply" y by scaling factor
        ADD       TMP1,YC             ;add y displacement to y coord.

        SLL       TMP3,TMP2           ;"multiply" z by scaling factor
        ADD       TMP2,ZC             ;add z displacement to z coord.

        SETF      32,0,1              ;restore default field 1 size
        MOVE      P,NODE              ;descend to left or right son
        JRUC      LOOP1               ;loop again

; Exit loop. Terminal node has been found. Find bounding box data.
ISLEAF:
        CLR       STAT                ;set default return value = 0
        ADDK      32,NODE             ;increment pointer to bbox offset
        MOVE      *NODE,P,0           ;get word offset value
        JRZ       CLRST               ;done if bd box offset is NIL (0)
        SLL       4,P                 ;convert from word to bit offset
        ADD       NODE,P              ;add pointer to offset
; Get coordinates of viewpoint relative to centroid of object.
        NEG       XC                  ;x distance from object center
        NEG       YC                  ;y distance from object center
        NEG       ZC                  ;z distance from object center

; Determine whether xyz coordinates fall within bounding box.
LOOP2:
        MOVE      *P+,STAT,1          ;get test mode word & status word
        BTST      15,STAT             ;test mode?
        JRZ       CLRST               ;done if MSB of test mode == 0

; Does point lie inside or outside the specified bounding box?
        CLR       PAD                 ;bd box's default pad = 0
        BTST      13,STAT             ;is nonzero padding specified?
        JRZ       PADSET              ;jump if no padding required
        MOVE      @_vpclip+ZNEAR,PAD,0 ;pad = distance to Znear plane
        INC       PAD                 ;increment padding depth by 1
        BTST      12,STAT             ;is negative padding specified?
        JRZ       PADSET              ;jump if positive padding req'd
        NEG       PAD                 ;make pad negative
PADSET:
        MOVE      *P+,TMP3,1          ;get XMIN, YMIN, ZMIN and factor F
        MOVE      P,Q                 ;save pointer to bounding box
        MOVE      TMP3,TMP0           ;copy XMIN
        SRL       8,TMP3              ;right justify 8-bit YMIN value
        MOVE      TMP3,TMP1           ;copy YMIN
        SRL       8,TMP3              ;right justify 8-bit ZMIN value
        MOVE      TMP3,TMP2           ;copy ZMIN
        SRL       8,TMP3              ;right justify 8-bit factor F
        SUBK      24,TMP3             ;shift byte by 24 to right justify

        SLL       24,TMP0             ;left justify 8-bit XMIN value
        SRA       TMP3,TMP0           ;shift XMIN right by 24-F bits
        SUB       PAD,TMP0            ;pad out bounding box by Znear+1
        CMP       TMP0,XC             ;x >= xmin ?
        JRLT      ISOUT               ;jump if x < xmin (outside bd box)

        SLL       24,TMP1             ;left justify 8-bit YMIN value
        SRA       TMP3,TMP1           ;shift YMIN right by 24-F bits
        SUB       PAD,TMP1            ;pad out bounding box by Znear+1
        CMP       TMP1,YC             ;y >= ymin ?
        JRLT      ISOUT               ;jump if y < ymin (outside bd box)

        SLL       24,TMP2             ;left justify 8-bit ZMIN value
        SRA       TMP3,TMP2           ;shift ZMIN right by 24-F bits
        SUB       PAD,TMP2            ;pad out bounding box by Znear+1
        CMP       TMP2,ZC             ;z >= zmin ?
        JRLT      ISOUT               ;jump if z < zmin (outside bd box)

        MOVE      *P+,TMP3,1          ;get XMAX, YMAX, ZMAX and factor F
        MOVE      TMP3,TMP0           ;copy XMAX
        SRL       8,TMP3              ;right justify 8-bit YMAX value
        MOVE      TMP3,TMP1           ;copy YMAX
        SRL       8,TMP3              ;right justify 8-bit ZMAX value
        MOVE      TMP3,TMP2           ;copy ZMAX
        SRL       8,TMP3              ;right justify 8-bit factor F
        SUBK      24,TMP3             ;shift byte by 24 to right justify

        SLL       24,TMP0             ;left justify 8-bit XMAX value
        SRA       TMP3,TMP0           ;shift XMAX right by 24-F bits
        ADD       PAD,TMP0            ;pad out bounding box by Znear+1
        CMP       TMP0,XC             ;x <= xmax ?
        JRGT      ISOUT               ;jump if x > xmax (outside bd box)

        SLL       24,TMP1             ;left justify 8-bit YMAX value
        SRA       TMP3,TMP1           ;shift YMAX right by 24-F bits
        ADD       PAD,TMP1            ;pad out bounding box by Znear+1
        CMP       TMP1,YC             ;y <= ymax ?
        JRGT      ISOUT               ;jump if y > ymax (outside bd box)

        SLL       24,TMP2             ;left justify 8-bit ZMAX value
        SRA       TMP3,TMP2           ;shift ZMAX right by 24-F bits
        ADD       PAD,TMP2            ;pad out bounding box by Znear+1
        CMP       TMP2,ZC             ;z <= zmax ?
        JRGT      ISOUT               ;jump if z > zmax (outside bd box)

; Point is INside bounding box. Check test mode to see what this means.
        BTST      14,STAT             ;test for INSIDE or OUTSIDE box?
        JRZ       DONE                ;all done if this is INSIDE test
        JRUC      LOOP2               ;look at next bounding box in list

; Point is OUTside bounding box. Check test mode to see what this means.
ISOUT:
        BTST      14,STAT             ;test for INSIDE or OUTSIDE box?
        JRNZ      DONE                ;all done if this is OUTSIDE test
        MOVE      Q,P                 ;restore pointer
        ADDK      32,P                ;point to next bounding box entry
        JRUC      LOOP2               ;look at next bounding box in list

; Return status value of 0.
CLRST:
        CLR       STAT                ;

; All done. Restore registers and return.
DONE:
        SRL       16,STAT             ;right justify return status word
        MMFM      SP,A0,A1,A2,A3,A4,A10,A11,A12,A13
        MOVE      *SP(32),STK,1       ;restore program stack pointer
        RETS      2                   ;

        .end

