home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch3_5 / bspcollide.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-22  |  5.6 KB  |  138 lines
  1. /* bspCollide.c: module to detect collisions between the viewer and static
  2.  * objects in an environment represented as a BSP tree.
  3.  * Copyright (c) Norman Chin 
  4.  */
  5. #include "bsp.h"
  6.  
  7. /* flags to indicate if any piece of a line segment is inside any polyhedron
  8.  *     or outside all polyhedra
  9.  */
  10. static boolean anyPieceOfLineIn, anyPieceOfLineOut;
  11.  
  12. /* local functions - see function definition */
  13. static int BSPclassifyPoint(const POINT *point, const BSPNODE *bspNode);
  14. static void BSPclassifyLineInterior(const POINT *from, const POINT *to,
  15.                     const BSPNODE *bspNode);
  16.                     
  17. /* Returns a boolean to indicate whether or not a collision had occurred 
  18.  * between the viewer and any static objects in an environment represented as 
  19.  * a BSP tree.
  20.  * 
  21.  * from    - start position of viewer 
  22.  * to      - end position of viewer
  23.  * bspTree - BSP tree of scene
  24.  */
  25. boolean BSPdidViewerCollideWithScene(const POINT *from, const POINT *to,
  26.                      const BSPNODE *bspTree)
  27. {
  28.    /* first classify the endpoints */ 
  29.    int sign1= BSPclassifyPoint(from,bspTree);
  30.    int sign2= BSPclassifyPoint(to,bspTree);
  31.  
  32.    /* collision occurs iff there's a state change between endpoints or
  33.     * either endpoint is on an object 
  34.     */
  35.    if (sign1 == 0 || sign2 == 0 || sign1 != sign2) return(1);
  36.    else {
  37.       anyPieceOfLineIn= anyPieceOfLineOut= 0; /* clear flags */
  38.       /* since we already classified the endpoints, try interior of line */ 
  39.       /*    this routine will set the flags to appropriate values */
  40.       BSPclassifyLineInterior(from,to,bspTree);
  41.  
  42.       /* if line interior is inside and outside an object, collision detected*/
  43.       /* else no collision detected */
  44.       return( (anyPieceOfLineIn && anyPieceOfLineOut) ? 1 : 0 );
  45.    }
  46. } /*  BSPdidViewerCollideWithScene() */
  47.  
  48. /* Classifies point as to whether or not it is inside, outside or on an object
  49.  * represented as a BSP tree, where inside is -1, outside is 1, on is 0.
  50.  * 
  51.  * point   - position of point
  52.  * bspNode - a node in BSP tree
  53.  */
  54. static int BSPclassifyPoint(const POINT *point,const BSPNODE *bspNode)
  55. {
  56.    if (bspNode == NULL_BSPNODE) return(1); /* point is out since no tree */
  57.  
  58.    if (bspNode->kind == PARTITION_NODE) { /* compare point with plane */
  59.       const PLANE *plane= &bspNode->node->sameDir->plane;
  60.       float dp= plane->aa*point->xx + plane->bb*point->yy + 
  61.                 plane->cc*point->zz + plane->dd;
  62.       if (dp < -TOLER)        /* point on "-" side, filter down "-" branch */
  63.      return(BSPclassifyPoint(point,bspNode->node->negativeSide));
  64.       else if (dp > TOLER)    /* point on "+" side, filter down "+" branch */
  65.      return(BSPclassifyPoint(point,bspNode->node->positiveSide));
  66.       else {            
  67.      /* point is on plane, so classify the neighborhood of point by 
  68.       * filtering the same point down both branches.  
  69.       */
  70.      int sign1= BSPclassifyPoint(point,bspNode->node->negativeSide);
  71.      int sign2= BSPclassifyPoint(point,bspNode->node->positiveSide);
  72.      /* if classification is same then return it otherwise it's on */
  73.      return( (sign1 == sign2) ? sign1 : 0 );
  74.       }
  75.    }
  76.    else if (bspNode->kind == OUT_NODE) return(1); /* point is outside */
  77.    else { assert(bspNode->kind == IN_NODE); return(-1); } /* point is inside */
  78. } /* BSPclassifyPoint() */
  79.  
  80. /* Classifies interior of line segment (not including endpoints) as to whether
  81.  * or not any piece is inside or outside an object represented as a BSP tree.
  82.  * If it's on, it's recursively called on both half-spaces to set the flags.
  83.  * There is no explicit on condition like we have with BSPclassifyPoint().
  84.  * 
  85.  * from    - endpoint of line segment
  86.  * to      - other endpoint of line segment
  87.  * bspNode - a node in BSP tree     
  88.  */
  89. static void BSPclassifyLineInterior(const POINT *from,const POINT *to,
  90.                     const BSPNODE *bspNode)
  91.                     
  92. {
  93.    if (bspNode->kind == PARTITION_NODE) { /* compare line segment with plane */
  94.       float ixx,iyy,izz;
  95.       const PLANE *plane= &bspNode->node->sameDir->plane;
  96.       float dp1= plane->aa*from->xx + plane->bb*from->yy +
  97.              plane->cc*from->zz + plane->dd;
  98.       float dp2= plane->aa*to->xx + plane->bb*to->yy +
  99.              plane->cc*to->zz + plane->dd;
  100.       SIGN sign1= FSIGN(dp1); SIGN sign2= FSIGN(dp2);
  101.  
  102.       if ( (sign1 == NEGATIVE && sign2 == POSITIVE) || 
  103.        (sign1 == POSITIVE && sign2 == NEGATIVE) ) {    /* split! */
  104.      SIGN check= anyEdgeIntersectWithPlane(from->xx,from->yy,from->zz,
  105.                            to->xx,to->yy,to->zz,
  106.                            plane,&ixx,&iyy,&izz);
  107.      POINT iPoint;
  108.      assert(check != ZERO);
  109.      
  110.      /* filter split line segments down appropriate branches */
  111.      iPoint.xx= ixx; iPoint.yy= iyy; iPoint.zz= izz;
  112.      if (sign1 == NEGATIVE) { assert(sign2 == POSITIVE);
  113.         BSPclassifyLineInterior(from,&iPoint,bspNode->node->negativeSide);
  114.         BSPclassifyLineInterior(to,&iPoint,bspNode->node->positiveSide);
  115.      }
  116.      else { assert(sign1 == POSITIVE && sign2 == NEGATIVE); 
  117.         BSPclassifyLineInterior(from,&iPoint,bspNode->node->positiveSide);
  118.         BSPclassifyLineInterior(to,&iPoint,bspNode->node->negativeSide);
  119.      }
  120.       }
  121.       else {            /* no split,so on same side */
  122.      if (sign1 == ZERO && sign2 == ZERO) {
  123.         BSPclassifyLineInterior(from,to,bspNode->node->negativeSide);
  124.         BSPclassifyLineInterior(from,to,bspNode->node->positiveSide);
  125.      }
  126.      else if (sign1 == NEGATIVE || sign2 == NEGATIVE) {
  127.         BSPclassifyLineInterior(from,to,bspNode->node->negativeSide);
  128.      }
  129.      else { assert(sign1 == POSITIVE || sign2 == POSITIVE);
  130.         BSPclassifyLineInterior(from,to,bspNode->node->positiveSide);
  131.      }
  132.       }
  133.    }
  134.    else if (bspNode->kind == IN_NODE) anyPieceOfLineIn= 1; /* line inside */
  135.    else { assert(bspNode->kind == OUT_NODE); anyPieceOfLineOut= 1; }
  136. } /* BSPclassifyLineInterior() */
  137. /*** bspCollide.c ***/
  138.