This is GKCollider.m in view mode; [Download] [Up]
#import <gamekit/gamekit.h>
#import <math.h>
// Note: There are plenty of nice ways to do all this. What I'm going
// for here is blinding speed. Therefore, I have a lot of special cases
// and other things that take advantage of 2-d geometry. The tradeoff is
// that I don't care how much code it takes if it is _fast_. I have defined
// a few geometric functions here to make the code easier to read...and I
// realize that sacrifices speed, my my sanity is more important that
// ultimate speed...
double GKDistanceBetweenPoints(NXPoint *point1, NXPoint *point2)
{ // using standard 2-d distance formula: d=sqrt(x^2+y^2)
float x = point1->x - point2->x;
float y = point1->y - point2->y;
// it might make sense to do a fast approx. of sqrt() here instead...
return sqrt(GK_SQUARE(x) + GK_SQUARE(y));
}
BOOL GKOuterLineSegmentIntersectsRect(NXPoint *point1, NXPoint *point2, NXRect *rect)
{ // assumes neither point lies inside rect; if that's true, you have
// intersection already, so don't call here!
double slope, intercept1, intercept2;
NXPoint max = { NX_MAXX(rect), NX_MAXY(rect) };
// is line completely to one side of the rect?
if (((point1->x < NX_X(rect)) && (point2->x < NX_X(rect))) ||
((point1->y < NX_Y(rect)) && (point2->y < NX_Y(rect))) ||
((point1->x > max.x) && (point2->x > max.x)) ||
((point1->y > max.y) && (point2->y > max.y))) return NO;
// find y-coord of line when it crosses max.x and min.x...if
// one of these points is min.y<point<max.y have intersect on sides
// of rect. Have intersect on top or bottom if one is above max.y
// while the other is below min.y...
slope = (point1->y - point2->y) / (point1->x - point2->x);
intercept1 = slope * (NX_X(rect) - point1->x) + point1->y;
intercept2 = slope * (max.x - point1->x) + point1->y;
if (((intercept1 > max.y) && (intercept2 < NX_Y(rect))) ||
((intercept2 > max.y) && (intercept1 < NX_Y(rect))) ||
((intercept1 < max.y) && (intercept1 > NX_Y(rect))) ||
((intercept2 < max.y) && (intercept2 > NX_Y(rect)))) return YES;
return NO;
}
// I should probably make this an inline procedure...
double GKSegmentAngle(NXPoint *point1, NXPoint *point2)
{ // for speed I assume point1 is left of point2
double deltaY = GK_VECTOR_Y(point2) - GK_VECTOR_Y(point1);
double deltaX = GK_VECTOR_X(point2) - GK_VECTOR_X(point1);
return (asin(deltaY/sqrt(GK_SQUARE(deltaX)+GK_SQUARE(deltaY))));
}
// this should probably be inline...
BOOL GKPointAboveLine(NXPoint *point, NXPoint *start, NXPoint *end)
{ // YES if point is above the line defined by start and end
// if the end points of the line form a vertical line (unlikely but
// possible) then points to the left of the line are considered to
// be "above" the line.
double x1 = GK_VECTOR_X(start);
double diff = GK_VECTOR_X(end) - x1; // only calc it once...
if (ABS(diff) < 0.00001) { // if x1 and x2 are too close together,
// we may still encounter problems with overflow/underflow...
// so I'm using a small delta; if the slope is more than 100000,
// we figure that the line is vertical for all intents and purposes.
// We check the point's y coord against y-coord of line
// interpolated/extrapolated to same x-coord (I did a little
// algebra to y=mx+b to make it faster)
if (GK_VECTOR_Y(point) > (((GK_VECTOR_X(point) - x1) *
((GK_VECTOR_Y(end) - GK_VECTOR_Y(start)) / diff)) +
GK_VECTOR_Y(start)))
return YES;
} else { // vertical line case -- need to avoid divide by zero!
if (GK_VECTOR_X(point) < x1) return YES;
}
return NO;
}
// this should probably be inline...
BOOL GKPointsOnSameSideOfLine(NXPoint *point1, NXPoint *point2, NXPoint *start, NXPoint *end)
{ // YES if point1 and point2 are on same side of line
// defined by start and end
if (GKPointAboveLine(point1, start, end) ==
GKPointAboveLine(point2, start, end)) return YES;
return NO;
}
BOOL GKPointInTriangle(NXPoint *point, GKTriangle *tri)
{
int left, first, second, x[3];
x[0] = GK_VECTOR_X(GK_VERTEX(tri, 0));
x[1] = GK_VECTOR_X(GK_VERTEX(tri, 1));
x[2] = GK_VECTOR_X(GK_VERTEX(tri, 2));
// sort vertices. need to know leftmost point and then which point
// is next going counter clockwise ("first")
if (x[0] < x[1]) {
if (x[0] < x[2]) {
left = 0; first = 1; second = 2;
} else {
left = 2; first = 1; second = 0;
}
} else {
if (x[1] < x[2]) {
left = 1; first = 0; second = 2;
} else { // this code is repeated from above...I did this for speed
left = 2; first = 1; second = 0;
}
}
if ( ((!GKPointAboveLine(point, GK_VERTEX(tri, left),
GK_VERTEX(tri, second)) &&
GKPointAboveLine(point, GK_VERTEX(tri, left),
GK_VERTEX(tri, first))) ||
(!GKPointAboveLine(point, GK_VERTEX(tri, left),
GK_VERTEX(tri, first)) &&
GKPointAboveLine(point, GK_VERTEX(tri, left),
GK_VERTEX(tri, second)))) &&
GKPointsOnSameSideOfLine(point, GK_VERTEX(tri, left),
GK_VERTEX(tri, first), GK_VERTEX(tri, second)))
return YES;
return NO;
}
static id theGKColliderInstance = nil;
@implementation GKCollider
+ new
{
if (!theGKColliderInstance)
theGKColliderInstance = [[[self alloc] init] buildHashTable];
return theGKColliderInstance;
}
- buildHashTable
{ // set up the method hash table
collisionHash = [[HashTable alloc]
initKeyDesc:"i" valueDesc:"!" capacity:10];
// ***** I assume that casting to void * is OK for all these -*key:
// methods; ie. I don't need a pointer to an int...the docs are unclear
[collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_RECTANGLE_SHAPE)
value:@selector(rect:intersectsRect:)];
[collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_CIRCLE_SHAPE)
value:@selector(rect:intersectsCircle:)];
[collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_TRIANGLE_SHAPE)
value:@selector(rect:intersectsTriangle:)];
[collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_COMPOSITE_SHAPE)
value:@selector(rect:intersectsComposite:)];
[collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_CIRCLE_SHAPE)
value:@selector(circle:intersectsCircle:)];
[collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_TRIANGLE_SHAPE)
value:@selector(circle:intersectsTriangle:)];
[collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_COMPOSITE_SHAPE)
value:@selector(circle:intersectsComposite:)];
[collisionHash insertKey:(void *)(GK_TRIANGLE_SHAPE * GK_TRIANGLE_SHAPE)
value:@selector(triangle:intersectsTriangle:)];
[collisionHash insertKey:(void *)(GK_TRIANGLE_SHAPE * GK_COMPOSITE_SHAPE)
value:@selector(triangle:intersectsComposite:)];
[collisionHash insertKey:(void *)(GK_COMPOSITE_SHAPE * GK_COMPOSITE_SHAPE)
value:@selector(composite:intersectsComposite:)];
return self;
}
- (BOOL)object:actor1 collidesWith:actor2
{
NXRect bounds[2];
int ret, swap, type[3];
SEL method;
// first, check the bounding boxes. If they don't intersect,
// then it is pointless to go any further.
[actor1 getBoundingBox:&bounds[0]];
[actor2 getBoundingBox:&bounds[1]];
// Note: intersection is still NO if edges shared... have to have
// true intersection to get a YES. This leniency shouldn't pose
// a problem, but you should understand the limits of NXIntersectsRect.
if (!NXIntersectsRect(&bounds[0], &bounds[1])) return NO;
// get the collision method's selector and whether or not
// to reverse the arguments:
type[1] = [actor1 collisionType];
type[2] = [actor2 collisionType];
type[0] = type[1] * type[2];
// a shortcut to speed up rectangle/rectangle intersections
if (type[0] == GK_RECTANGLE_SHAPE * GK_RECTANGLE_SHAPE) return YES;
// note we return a YES if couldn't find collision method; we're
// reverting to the bounding box intersection
if (!(method = (SEL)[collisionHash valueForKey:(void *)type[0]]))
return YES;
// call the collision method
swap = (type[1] > type[2]);
if (swap) ret = (int)[self perform:method
with:(id)[actor2 shapeStruct] with:(id)[actor1 shapeStruct]];
else ret = (int)[self perform:method
with:(id)[actor1 shapeStruct] with:(id)[actor2 shapeStruct]];
// using ret as an int avoids trouble with machine dependencies
// (a BOOL is defined as a char; docs say that this would be dangerous,
// presumably due to byte-ordering difficulties.)
if (ret) return YES;
return NO;
}
- (int)rect:(NXRect *)rect1 intersectsRect:(NXRect *)rect2
{ // we never call it, but it is here for completeness.
return NXIntersectsRect(rect1, rect2);
}
- (int)rect:(NXRect *)rect intersectsCircle:(GKCircle *)circ
{ // This code is derived from the book Graphics Gems, ed. Andrew Glassner.
// algorithm reported by Clifford A. Shaffer; it's really rather obvious
// when you think about it.
// NXRect origin should be min point, width/height positive.
double radiusSquared = GK_SQUARE(GK_RADIUS(circ));
// translate to circle's center is the origin.
// and the rect looks like this: (max, min are points)
// +========MAX
// | |
// MIN========+
NXPoint max = { NX_MAXX(rect) - ((circ)->center.x),
NX_MAXY(rect) - circ->center.y };
NXPoint min = { NX_X(rect) - GK_CENTER_X(circ),
NX_Y(rect) - GK_CENTER_Y(circ) };
if (max.x < 0) // Rect is to the left of center
if (max.y < 0) // in lower left corner
return ((GK_SQUARE(max.x) + GK_SQUARE(max.y)) < radiusSquared);
else if (min.y > 0) // in upper left corner
return ((GK_SQUARE(max.x) + GK_SQUARE(min.y)) < radiusSquared);
else return (-(max.x) < GK_RADIUS(circ)); // to west of circle
else if (min.x > 0) // Rect is to the right of center
if (max.y < 0) // in lower right corner
return ((GK_SQUARE(min.x) + GK_SQUARE(max.y)) < radiusSquared);
else if (min.y > 0) // in upper right corner
return ((GK_SQUARE(min.x) + GK_SQUARE(min.y)) < radiusSquared);
else return (min.x < GK_RADIUS(circ)); // to east of circle
else if (max.y < 0) // to south of circle
return (-(max.y) < GK_RADIUS(circ));
else if (min.y > 0) // to north of circle
return (min.y < GK_RADIUS(circ));
return YES; // rect surrounds circle
}
- (int)rect:(NXRect *)rect intersectsTriangle:(GKTriangle *)tri
{ // This one is my algorithm...
int i;
for (i=0; i<3; i++) // if any point is in the rect, we have intersection.
if (NXMouseInRect(&(tri->points[i]), rect, NO)) return YES;
// Now it gets hairy... we need to see if the triangle (1) encloses rect,
// (2) clips a rect corner, (3) slices rect, or (4) misses the rect.
// can check for (2) and (3) with line-rect intersections:
if (GKOuterLineSegmentIntersectsRect(&(tri->points[0]),
&(tri->points[1]), rect) ||
GKOuterLineSegmentIntersectsRect(&(tri->points[1]),
&(tri->points[2]), rect) ||
GKOuterLineSegmentIntersectsRect(&(tri->points[2]),
&(tri->points[0]), rect)) return YES;
// check for (1)... triangle enclosing rect? Yes if any point in
// rect is in the triangle.
{
NXPoint corner1 = { NX_X(rect), NX_Y(rect) + NX_HEIGHT(rect) };
NXPoint corner2 = { NX_X(rect) + NX_WIDTH(rect), NX_Y(rect) };
NXPoint corner3 = { NX_X(rect) + NX_WIDTH(rect),
NX_Y(rect) + NX_HEIGHT(rect) };
if (GKPointInTriangle(&(rect->origin), tri) ||
GKPointInTriangle(&corner1, tri) ||
GKPointInTriangle(&corner2, tri) ||
GKPointInTriangle(&corner3, tri)) return YES;
}
// none of the above, so we assume a miss.
return NO;
}
- (int)rect:(NXRect *)rect intersectsComposite:comp
{
// ***** need to write this part *****
return NO;
}
- (int)circle:(GKCircle *)circ1 intersectsCircle:(GKCircle *)circ2
{ // if the dist. between centers is less than the two radii added
// together, then we have an intersection. Proof is obvious.
float d = GKDistanceBetweenPoints(GK_CENTER(circ1), GK_CENTER(circ2));
if (d < GK_RADIUS(circ1) + GK_RADIUS(circ2)) return YES;
return NO;
}
- (int)circle:(GKCircle *)circ intersectsTriangle:(GKTriangle *)tri
{
// Three checks: (1) YES if any triangle vertices are in the circle
// (2) YES if Triangle encloses circle, and (3) YES if a triangle edge
// (line segment) intersects the circle.
// ***** need to write this part *****
return NO;
}
- (int)circle:(GKCircle *)circ intersectsComposite:comp
{
// ***** need to write this part *****
return NO;
}
- (int)triangle:(GKTriangle *)tri1 intersectsTriangle:(GKTriangle *)tri2
{
// YES if any points of one triangle are inside the other triangle
// also need to check if any of the sides intersect each other to
// take care of overlapping triangles
// ***** need to write this part *****
return NO;
}
- (int)triangle:(GKTriangle *)tri intersectsComposite:comp
{
// ***** need to write this part *****
return NO;
}
- (int)composite:(GKTriangle *)comp1 intersectsComposite:comp2
{
// ***** need to write this part *****
return NO;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.