그림 6 : 검사용 구체

So why use a bounding sphere? Well, testing to see if a collision has occurred is really fast. If you measure the distance between two objects, and the distance is less than the radius of either bounding sphere, then there is a collision. This is a very quick test, so it’s easy to see why many games use spheres as at least a first line of defense. But if you need to determine exactly where two objects made contact, this won’t be enough.

IF ( (point.x >= box.minX 
and point.x <= box.maxX) 
and (point.y >= box.minY
and point.y <= box.maxY) 
and (point.z >= box.minZ 
and point.z <= box.maxZ)
)then a collision occurred.

// FIGURE OUT WHICH QUADRANT THE VERTEX IS RELATIVE TO THE HIT POINT

#define WHICH_QUAD(vertex,hitPos) \
   ( (vertex.x > hitPos->x) ? ((vertex.y > hitPos->y) 
  ? 1 : 4) :( (vertex.y > hitPos->y) ? 2 : 3) )

// GET THE X INTERCEPT OF THE LINE FROM THE CURRENT VERTEX TO THE NEXT
#define X_INTERCEPT(point1, point2, hitY) \
  (point2.x - ( ((point2.y - hitY) * (point1.x - point2.x)) 
  / (point1.y - point2.y) ) )

/////////////////////////////////////////////////////////////
// Procedure: PointInPoly (SUM OF ANGLES CROSSING VERSION)
// Purpose: Check if a point is inside a polygon
// Returns: TRUE if Point is inside polygon, else FALSE
/////////////////////////////////////////////////////////////

BOOL CFateView::PointInPoly(tSector *sector, tPoint2D *hitPos)
{

/// Local Variables /////////////////////////////////////////
   short edge, first, next;
   short quad, next_quad, delta, total;

/////////////////////////////////////////////////////////////
   edge = first = sector->edge; 
   quad = WHICH_QUAD(m_edgelist[edge].pos, hitPos);
   total = 0; // COUNT OF ABSOLUTE SECTORS CROSSED
   /* LOOP THROUGH THE VERTICES IN A SECTOR */
   do {
     next = m_edgelist[edge].nextedge; 
     next_quad = WHICH_QUAD(m_edgelist[next].pos, hitPos);
     delta = next_quad - quad; // HOW MANY QUADS HAVE I MOVED
    
// SPECIAL CASES TO HANDLE CROSSINGS OF MORE THEN ONE         
//QUAD

    switch (delta) { 
    case 2:  // IF WE CROSSED THE MIDDLE, FIGURE OUT IF IT 
             //WAS CLOCKWISE OR COUNTER
    case -2: // US THE X POSITION AT THE HIT POINT TO 
             // DETERMINE WHICH WAY AROUND
     if (X_INTERCEPT(m_edgelist[edge].pos,
     m_edgelist[next].pos, hitPos->y) > hitPos->x)
      delta = - (delta); 
         break; 
     case 3: // MOVING 3 QUADS IS LIKE MOVING BACK 1
       delta = -1; 
         break; 
     case -3: // MOVING BACK 3 IS LIKE MOVING FORWARD 1
       delta = 1;
         break; 
     }
   /* ADD IN THE DELTA */
   total += delta;
   quad = next_quad; // RESET FOR NEXT STEP
   edge = next;
  } while (edge != first);

   /* AFTER ALL IS DONE IF THE TOTAL IS 4 THEN WE ARE INSIDE */
  if ((total == +4) || (total == -4)) return TRUE; else return FALSE; 
}

// Procedure: PointInPoly (EDGE CROSSING VERSION)
// Purpose: Check if a point is inside a polygon
// Returns: TRUE if Point is inside polygon, else FALSE

BOOL CFateView::PointInPoly(tSector *sector, tPoint2D *hitPos)
{
// Local Variables 
    short edge, first, next;
    tPoint2D *pnt1,*pnt2;
    BOOL inside = FALSE; // INITIAL TEST CONDITION
    BOOL flag1,flag2;

    edge = first = sector->edge; // SET UP INITIAL CONDITIONS
    pnt1 = &m_edgelist[edge].pos;
    flag1 = ( hitPos->y >= pnt1->y ) ; // IS THE FIRST                                         VERTEX OVER OR                                         UNDER THE LINE

     /* LOOP THROUGH THE VERTICES IN A SECTOR */
    do {
      next = m_edgelist[edge].nextedge; // CHECK THE NEXT VERTEX
      pnt2 = &m_edgelist[next].pos;
      flag2 = ( hitPos->y >= pnt2->y ); // IS IT OVER OR UNDER
      if (flag1 != flag2) // MAKE SURE THE EDGE ACTUALLY                        // CROSSES THE TEST X AXIS
       {
     // CALCULATE WHETHER THE SEGMENT ACTUALLY CROSSES THE X TEST AXIS
    // A TRICK FROM GRAPHIC GEMS IV TO GET RID OF THE X INTERCEPT DIVIDE
    if (((pnt2->y - hitPos->y) * (pnt1->x - pnt2->x) >=
      (pnt2->x - hitPos->x) * (pnt1->y - pnt2->y)) == flag2 )
      inside = !inside; // IF IT CROSSES TOGGLE THE INSIDE                      // FLAG (ODD IS IN, EVEN OUT)
      }
    pnt1 = pnt2; // RESET FOR NEXT STEP
    edge = next;
    flag1 = flag2;
    } while (edge != first);
    return inside;
}