home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1995 August / NEBULA.mdf / SourceCode / GameKit / gamekit-1 / GKCollider.m < prev    next >
Encoding:
Text File  |  1994-06-07  |  12.4 KB  |  336 lines
  1.  
  2. #import <gamekit/gamekit.h>
  3. #import <math.h>
  4.  
  5. // Note:  There are plenty of nice ways to do all this.  What I'm going
  6. // for here is blinding speed.  Therefore, I have a lot of special cases
  7. // and other things that take advantage of 2-d geometry.  The tradeoff is
  8. // that I don't care how much code it takes if it is _fast_.  I have defined
  9. // a few geometric functions here to make the code easier to read...and I
  10. // realize that sacrifices speed, my my sanity is more important that
  11. // ultimate speed...
  12.  
  13. double GKDistanceBetweenPoints(NXPoint *point1, NXPoint *point2)
  14. {    // using standard 2-d distance formula:  d=sqrt(x^2+y^2)
  15.     float x = point1->x - point2->x;
  16.     float y = point1->y - point2->y;
  17.     // it might make sense to do a fast approx. of sqrt() here instead...
  18.     return sqrt(GK_SQUARE(x) + GK_SQUARE(y));
  19. }
  20.  
  21. BOOL GKOuterLineSegmentIntersectsRect(NXPoint *point1, NXPoint *point2, NXRect *rect)
  22. {    // assumes neither point lies inside rect; if that's true, you have
  23.     // intersection already, so don't call here!
  24.     double slope, intercept1, intercept2;
  25.     NXPoint max = {    NX_MAXX(rect), NX_MAXY(rect) };
  26.     // is line completely to one side of the rect?
  27.     if (((point1->x < NX_X(rect)) && (point2->x < NX_X(rect))) ||
  28.         ((point1->y < NX_Y(rect)) && (point2->y < NX_Y(rect))) ||
  29.         ((point1->x > max.x) && (point2->x > max.x)) ||
  30.         ((point1->y > max.y) && (point2->y > max.y))) return NO;
  31.     // find y-coord of line when it crosses max.x and min.x...if
  32.     // one of these points is min.y<point<max.y have intersect on sides
  33.     // of rect.  Have intersect on top or bottom if one is above max.y
  34.     // while the other is below min.y...
  35.     slope = (point1->y - point2->y) / (point1->x - point2->x);
  36.     intercept1 = slope * (NX_X(rect) - point1->x) + point1->y;
  37.     intercept2 = slope * (max.x - point1->x) + point1->y;
  38.     if (((intercept1 > max.y) && (intercept2 < NX_Y(rect))) ||
  39.         ((intercept2 > max.y) && (intercept1 < NX_Y(rect))) ||
  40.         ((intercept1 < max.y) && (intercept1 > NX_Y(rect))) ||
  41.         ((intercept2 < max.y) && (intercept2 > NX_Y(rect)))) return YES;
  42.     return NO;
  43. }
  44.  
  45. // I should probably make this an inline procedure...
  46. double GKSegmentAngle(NXPoint *point1, NXPoint *point2)
  47. {    // for speed I assume point1 is left of point2
  48.     double deltaY = GK_VECTOR_Y(point2) - GK_VECTOR_Y(point1);
  49.     double deltaX = GK_VECTOR_X(point2) - GK_VECTOR_X(point1);
  50.     return (asin(deltaY/sqrt(GK_SQUARE(deltaX)+GK_SQUARE(deltaY))));
  51. }
  52.  
  53. // this should probably be inline...
  54. BOOL GKPointAboveLine(NXPoint *point, NXPoint *start, NXPoint *end)
  55. {    // YES if point is above the line defined by start and end
  56.     // if the end points of the line form a vertical line (unlikely but
  57.     // possible) then points to the left of the line are considered to
  58.     // be "above" the line. 
  59.     double x1 = GK_VECTOR_X(start);
  60.     double diff = GK_VECTOR_X(end) - x1; // only calc it once...
  61.     if (ABS(diff) < 0.00001) { // if x1 and x2 are too close together,
  62.         // we may still encounter problems with overflow/underflow...
  63.         // so I'm using a small delta; if the slope is more than 100000,
  64.         // we figure that the line is vertical for all intents and purposes.
  65.         // We check the point's y coord against y-coord of line
  66.         // interpolated/extrapolated to same x-coord (I did a little
  67.         // algebra to y=mx+b to make it faster)
  68.         if (GK_VECTOR_Y(point) > (((GK_VECTOR_X(point) - x1) *
  69.                 ((GK_VECTOR_Y(end) - GK_VECTOR_Y(start)) / diff)) +
  70.                 GK_VECTOR_Y(start)))
  71.             return YES;
  72.     } else { // vertical line case -- need to avoid divide by zero!
  73.         if (GK_VECTOR_X(point) < x1) return YES;
  74.     }
  75.     return NO;
  76. }
  77.  
  78. // this should probably be inline...
  79. BOOL GKPointsOnSameSideOfLine(NXPoint *point1, NXPoint *point2, NXPoint *start, NXPoint *end)
  80. {    // YES if point1 and point2 are on same side of line
  81.     // defined by start and end
  82.     if (GKPointAboveLine(point1, start, end) ==
  83.         GKPointAboveLine(point2, start, end)) return YES;
  84.     return NO;
  85. }
  86.  
  87. BOOL GKPointInTriangle(NXPoint *point, GKTriangle *tri)
  88. {
  89.     int left, first, second, x[3];
  90.     x[0] = GK_VECTOR_X(GK_VERTEX(tri, 0));
  91.     x[1] = GK_VECTOR_X(GK_VERTEX(tri, 1));
  92.     x[2] = GK_VECTOR_X(GK_VERTEX(tri, 2));
  93.     // sort vertices.  need to know leftmost point and then which point
  94.     // is next going counter clockwise ("first")
  95.     if (x[0] < x[1]) {
  96.         if (x[0] < x[2]) {
  97.             left = 0; first = 1; second = 2;
  98.         } else {
  99.             left = 2; first = 1; second = 0;
  100.         }
  101.     } else {
  102.         if (x[1] < x[2]) {
  103.             left = 1; first = 0; second = 2;
  104.         } else { // this code is repeated from above...I did this for speed
  105.             left = 2; first = 1; second = 0;
  106.         }
  107.     }
  108.     
  109.     if ( ((!GKPointAboveLine(point, GK_VERTEX(tri, left),
  110.                 GK_VERTEX(tri, second)) &&
  111.             GKPointAboveLine(point, GK_VERTEX(tri, left),
  112.                 GK_VERTEX(tri, first))) ||
  113.           (!GKPointAboveLine(point, GK_VERTEX(tri, left),
  114.                 GK_VERTEX(tri, first)) &&
  115.             GKPointAboveLine(point, GK_VERTEX(tri, left),
  116.                 GK_VERTEX(tri, second)))) &&
  117.             GKPointsOnSameSideOfLine(point, GK_VERTEX(tri, left),
  118.                 GK_VERTEX(tri, first), GK_VERTEX(tri, second)))
  119.                 
  120.                 return YES;
  121.     return NO;
  122. }
  123.  
  124. static id theGKColliderInstance = nil;
  125.  
  126. @implementation GKCollider
  127.  
  128. + new
  129. {
  130.     if (!theGKColliderInstance)
  131.         theGKColliderInstance = [[[self alloc] init] buildHashTable];
  132.     return theGKColliderInstance;
  133. }
  134.  
  135. - buildHashTable
  136. {    // set up the method hash table
  137.     collisionHash = [[HashTable alloc]
  138.             initKeyDesc:"i" valueDesc:"!" capacity:10];
  139.     // ***** I assume that casting to void * is OK for all these -*key:
  140.     // methods; ie. I don't need a pointer to an int...the docs are unclear
  141.     [collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_RECTANGLE_SHAPE)
  142.             value:@selector(rect:intersectsRect:)];
  143.     [collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_CIRCLE_SHAPE)
  144.             value:@selector(rect:intersectsCircle:)];
  145.     [collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_TRIANGLE_SHAPE)
  146.             value:@selector(rect:intersectsTriangle:)];
  147.     [collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_COMPOSITE_SHAPE)
  148.             value:@selector(rect:intersectsComposite:)];
  149.     [collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_CIRCLE_SHAPE)
  150.             value:@selector(circle:intersectsCircle:)];
  151.     [collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_TRIANGLE_SHAPE)
  152.             value:@selector(circle:intersectsTriangle:)];
  153.     [collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_COMPOSITE_SHAPE)
  154.             value:@selector(circle:intersectsComposite:)];
  155.     [collisionHash insertKey:(void *)(GK_TRIANGLE_SHAPE * GK_TRIANGLE_SHAPE)
  156.             value:@selector(triangle:intersectsTriangle:)];
  157.     [collisionHash insertKey:(void *)(GK_TRIANGLE_SHAPE * GK_COMPOSITE_SHAPE)
  158.             value:@selector(triangle:intersectsComposite:)];
  159.     [collisionHash insertKey:(void *)(GK_COMPOSITE_SHAPE * GK_COMPOSITE_SHAPE)
  160.             value:@selector(composite:intersectsComposite:)];
  161.     return self;
  162. }
  163.  
  164. - (BOOL)object:actor1 collidesWith:actor2
  165. {
  166.     NXRect bounds[2];
  167.     int ret, swap, type[3];
  168.     SEL method;
  169.     
  170.     // first, check the bounding boxes.  If they don't intersect,
  171.     // then it is pointless to go any further.
  172.     [actor1 getBoundingBox:&bounds[0]];
  173.     [actor2 getBoundingBox:&bounds[1]];
  174.     // Note:  intersection is still NO if edges shared... have to have
  175.     // true intersection to get a YES.  This leniency shouldn't pose
  176.     // a problem, but you should understand the limits of NXIntersectsRect.
  177.     if (!NXIntersectsRect(&bounds[0], &bounds[1])) return NO;
  178.  
  179.     // get the collision method's selector and whether or not
  180.     // to reverse the arguments:
  181.     type[1] = [actor1 collisionType];
  182.     type[2] = [actor2 collisionType];
  183.     type[0] = type[1] * type[2];
  184.     // a shortcut to speed up rectangle/rectangle intersections
  185.     if (type[0] == GK_RECTANGLE_SHAPE * GK_RECTANGLE_SHAPE) return YES;
  186.     // note we return a YES if couldn't find collision method; we're
  187.     // reverting to the bounding box intersection
  188.     if (!(method = (SEL)[collisionHash valueForKey:(void *)type[0]]))
  189.         return YES;
  190.     
  191.     // call the collision method
  192.     swap = (type[1] > type[2]);
  193.     if (swap) ret = (int)[self perform:method
  194.             with:(id)[actor2 shapeStruct] with:(id)[actor1 shapeStruct]];
  195.     else ret = (int)[self perform:method
  196.             with:(id)[actor1 shapeStruct] with:(id)[actor2 shapeStruct]];
  197.     // using ret as an int avoids trouble with machine dependencies
  198.     // (a BOOL is defined as a char; docs say that this would be dangerous,
  199.     // presumably due to byte-ordering difficulties.)
  200.     if (ret) return YES;
  201.     return NO;
  202. }
  203.  
  204. - (int)rect:(NXRect *)rect1 intersectsRect:(NXRect *)rect2
  205. {    // we never call it, but it is here for completeness.
  206.     return NXIntersectsRect(rect1, rect2);
  207. }
  208.  
  209. - (int)rect:(NXRect *)rect intersectsCircle:(GKCircle *)circ
  210. {    // This code is derived from the book Graphics Gems, ed. Andrew Glassner.
  211.     // algorithm reported by Clifford A. Shaffer; it's really rather obvious
  212.     // when you think about it.
  213.     // NXRect origin should be min point, width/height positive.
  214.     double radiusSquared = GK_SQUARE(GK_RADIUS(circ));
  215.     // translate to circle's center is the origin.
  216.     // and the rect looks like this: (max, min are points)
  217.     //  +========MAX
  218.     //  |         |
  219.     // MIN========+
  220.     NXPoint max = {    NX_MAXX(rect) - ((circ)->center.x),
  221.                     NX_MAXY(rect) - circ->center.y };
  222.     NXPoint min = {    NX_X(rect) - GK_CENTER_X(circ),
  223.                     NX_Y(rect) - GK_CENTER_Y(circ) };
  224.     if (max.x < 0) // Rect is to the left of center
  225.         if (max.y < 0)    // in lower left corner
  226.             return ((GK_SQUARE(max.x) + GK_SQUARE(max.y)) < radiusSquared);
  227.         else if (min.y > 0) // in upper left corner
  228.             return ((GK_SQUARE(max.x) + GK_SQUARE(min.y)) < radiusSquared);
  229.         else return (-(max.x) < GK_RADIUS(circ));    // to west of circle
  230.     else if (min.x > 0)    // Rect is to the right of center
  231.         if (max.y < 0)    // in lower right corner
  232.             return ((GK_SQUARE(min.x) + GK_SQUARE(max.y)) < radiusSquared);
  233.         else if (min.y > 0) // in upper right corner
  234.             return ((GK_SQUARE(min.x) + GK_SQUARE(min.y)) < radiusSquared);
  235.         else return (min.x < GK_RADIUS(circ));    // to east of circle
  236.     else if (max.y < 0)    // to south of circle
  237.         return (-(max.y) < GK_RADIUS(circ));
  238.     else if (min.y > 0) // to north of circle
  239.         return (min.y < GK_RADIUS(circ));
  240.     return YES;    // rect surrounds circle
  241. }
  242.  
  243. - (int)rect:(NXRect *)rect intersectsTriangle:(GKTriangle *)tri
  244. {    // This one is my algorithm...
  245.     int i;
  246.     for (i=0; i<3; i++) // if any point is in the rect, we have intersection.
  247.         if (NXMouseInRect(&(tri->points[i]), rect, NO)) return YES;
  248.     // Now it gets hairy... we need to see if the triangle (1) encloses rect,
  249.     // (2) clips a rect corner, (3) slices rect, or (4) misses the rect.
  250.     // can check for (2) and (3) with line-rect intersections:
  251.     if (GKOuterLineSegmentIntersectsRect(&(tri->points[0]),
  252.             &(tri->points[1]), rect) ||
  253.         GKOuterLineSegmentIntersectsRect(&(tri->points[1]),
  254.             &(tri->points[2]), rect) ||
  255.         GKOuterLineSegmentIntersectsRect(&(tri->points[2]),
  256.             &(tri->points[0]), rect)) return YES;    
  257.     // check for (1)... triangle enclosing rect?  Yes if any point in
  258.     // rect is in the triangle.
  259.     {
  260.          NXPoint corner1 = { NX_X(rect), NX_Y(rect) + NX_HEIGHT(rect) };
  261.          NXPoint corner2 = { NX_X(rect) + NX_WIDTH(rect), NX_Y(rect) };
  262.          NXPoint corner3 = { NX_X(rect) + NX_WIDTH(rect),
  263.                                 NX_Y(rect) + NX_HEIGHT(rect) };
  264.          if (GKPointInTriangle(&(rect->origin), tri) ||
  265.              GKPointInTriangle(&corner1, tri) ||
  266.             GKPointInTriangle(&corner2, tri) ||
  267.             GKPointInTriangle(&corner3, tri)) return YES;
  268.     }
  269.     // none of the above, so we assume a miss.
  270.     return NO;
  271. }
  272.  
  273. - (int)rect:(NXRect *)rect intersectsComposite:comp
  274. {
  275.     
  276.     // ***** need to write this part *****
  277.     
  278.     return NO;
  279. }
  280.  
  281. - (int)circle:(GKCircle *)circ1 intersectsCircle:(GKCircle *)circ2
  282. {    // if the dist. between centers is less than the two radii added
  283.     // together, then we have an intersection.  Proof is obvious.
  284.     float d = GKDistanceBetweenPoints(GK_CENTER(circ1), GK_CENTER(circ2));
  285.     if (d < GK_RADIUS(circ1) + GK_RADIUS(circ2)) return YES;
  286.     return NO;
  287. }
  288.  
  289. - (int)circle:(GKCircle *)circ intersectsTriangle:(GKTriangle *)tri
  290. {
  291.     // Three checks:  (1) YES if any triangle vertices are in the circle
  292.     // (2) YES if Triangle encloses circle, and (3) YES if a triangle edge
  293.     // (line segment) intersects the circle.
  294.  
  295.     // ***** need to write this part *****
  296.  
  297.     return NO;
  298. }
  299.  
  300. - (int)circle:(GKCircle *)circ intersectsComposite:comp
  301. {
  302.     
  303.     // ***** need to write this part *****
  304.     
  305.     return NO;
  306. }
  307.  
  308. - (int)triangle:(GKTriangle *)tri1 intersectsTriangle:(GKTriangle *)tri2
  309. {
  310.     // YES if any points of one triangle are inside the other triangle
  311.     // also need to check if any of the sides intersect each other to
  312.     // take care of overlapping triangles
  313.     
  314.     // ***** need to write this part *****
  315.     
  316.     return NO;
  317. }
  318.  
  319. - (int)triangle:(GKTriangle *)tri intersectsComposite:comp
  320. {
  321.     
  322.     // ***** need to write this part *****
  323.     
  324.     return NO;
  325. }
  326.  
  327. - (int)composite:(GKTriangle *)comp1 intersectsComposite:comp2
  328. {
  329.     
  330.     // ***** need to write this part *****
  331.     
  332.     return NO;
  333. }
  334.  
  335. @end
  336.