G3D::CollisionDetection Class Reference

#include <CollisionDetection.h>

Static Public Member Functions
static Vector3	separatingAxisForSolidBoxSolidBox (const int separatingAxisIndex, const Box &box1, const Box &box2)
static bool	parallelAxisForSolidBoxSolidBox (const double *ca, const double epsilon, int &axis1, int &axis2)
static float	projectedDistanceForSolidBoxSolidBox (const int separatingAxisIndex, const Vector3 &a, const Vector3 &b, const Vector3 &D, const double *c, const double *ca, const double *ad, const double *bd)
static void	fillSolidBoxSolidBoxInfo (const Box &box1, const Box &box2, Vector3 &a, Vector3 &b, Vector3 &D, double *c, double *ca, double *ad, double *bd)
static bool	conservativeBoxBoxTest (const Vector3 &a, const Vector3 &b, const Vector3 &D)
static bool	fixedSolidBoxIntersectsFixedSolidBox (const Box &box1, const Box &box2, const int lastSeparatingAxis=-1)
static void	closestPointsBetweenLineAndLine (const Line &line1, const Line &line2, Vector3 &closest1, Vector3 &closest2)
static float	penetrationDepthForFixedBoxFixedBox (const Box &box1, const Box &box2, Array< Vector3 > &contactPoints, Array< Vector3 > &contactNormals, const int lastSeparatingAxis=-1)
static float	penetrationDepthForFixedSphereFixedSphere (const class Sphere &sphereA, const Sphere &sphereB, Array< Vector3 > &contactPoints, Array< Vector3 > &contactNormals=ignoreArray)
static float	penetrationDepthForFixedSphereFixedBox (const Sphere &sphere, const Box &box, Array< Vector3 > &contactPoints, Array< Vector3 > &contactNormals=ignoreArray)
static float	penetrationDepthForFixedSphereFixedPlane (const Sphere &sphereA, const class Plane &planeB, Array< Vector3 > &contactPoints, Array< Vector3 > &contactNormals=ignoreArray)
static float	penetrationDepthForFixedBoxFixedPlane (const Box &box, const Plane &plane, Array< Vector3 > &contactPoints, Array< Vector3 > &contactNormals=ignoreArray)
static float	collisionTimeForMovingPointFixedPlane (const Vector3 &point, const Vector3 &velocity, const class Plane &plane, Vector3 &outLocation, Vector3 &outNormal=ignore)
static float	collisionTimeForMovingPointFixedTriangle (const Vector3 &orig, const Vector3 &dir, const Vector3 &v0, const Vector3 &v1, const Vector3 &v2)
static float	collisionTimeForMovingPointFixedTriangle (const Vector3 &orig, const Vector3 &dir, const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, Vector3 &location)
static float	collisionTimeForMovingPointFixedTriangle (const Vector3 &orig, const Vector3 &dir, const Triangle &tri, Vector3 &location=ignore, Vector3 &normal=ignore)
static float	collisionTimeForMovingPointFixedTriangle (const Vector3 &orig, const Vector3 &dir, const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, Vector3 &location, Vector3 &normal)
static float	collisionTimeForMovingPointFixedAABox (const Vector3 &point, const Vector3 &velocity, const class AABox &box, Vector3 &outLocation, bool &inside=ignoreBool, Vector3 &outNormal=ignore)
static bool	collisionLocationForMovingPointFixedAABox (const Vector3 &point, const Vector3 &velocity, const class AABox &box, Vector3 &outLocation, bool &inside=ignoreBool, Vector3 &normal=ignore)
static bool __fastcall	rayAABox (const Ray &ray, const Vector3 &invDir, const AABox &box, const Vector3 &boxCenter, float boundingRadiusSquared, Vector3 &location, bool &inside)
	Calculates intersection of a ray and a static Axis-Aligned Box (AABox). More...
static float	collisionTimeForMovingPointFixedSphere (const Vector3 &point, const Vector3 &velocity, const class Sphere &sphere, Vector3 &outLocation, Vector3 &outNormal=ignore, bool solid=false)
static float	collisionTimeForMovingPointFixedBox (const Vector3 &point, const Vector3 &velocity, const class Box &box, Vector3 &outLocation, Vector3 &outNormal=ignore)
static float	collisionTimeForMovingPointFixedRectangle (const Vector3 &point, const Vector3 &velocity, const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, const Vector3 &v3, Vector3 &outLocation, Vector3 &outNormal=ignore)
static float	collisionTimeForMovingPointFixedCapsule (const Vector3 &point, const Vector3 &velocity, const class Capsule &capsule, Vector3 &outLocation, Vector3 &outNormal=ignore)
static float	collisionTimeForMovingSphereFixedPlane (const class Sphere &sphere, const Vector3 &velocity, const class Plane &plane, Vector3 &outLocation, Vector3 &outNormal=ignore)
static float	collisionTimeForMovingSphereFixedTriangle (const class Sphere &sphere, const Vector3 &velocity, const Triangle &triangle, Vector3 &outLocation, float b[3]=(float *)&ignore)
static float	collisionTimeForMovingSphereFixedRectangle (const class Sphere &sphere, const Vector3 &velocity, const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, const Vector3 &v3, Vector3 &outLocation, Vector3 &outNormal=ignore)
static float	collisionTimeForMovingSphereFixedBox (const class Sphere &sphere, const Vector3 &velocity, const class Box &box, Vector3 &outLocation, Vector3 &outNormal=ignore)
static float	collisionTimeForMovingSphereFixedSphere (const Sphere &sphere, const Vector3 &velocity, const Sphere &fixedSphere, Vector3 &outLocation, Vector3 &outNormal=ignore)
static float	collisionTimeForMovingSphereFixedCapsule (const class Sphere &sphere, const Vector3 &velocity, const class Capsule &capsule, Vector3 &outLocation, Vector3 &outNormal=ignore)
static Vector3	bounceDirection (const class Sphere &sphere, const Vector3 &velocity, const float collisionTime, const Vector3 &collisionLocation, const Vector3 &collisionNormal)
static Vector3	slideDirection (const class Sphere &sphere, const Vector3 &velocity, const float collisionTime, const Vector3 &collisionLocation)
static Vector3	closestPointOnLineSegment (const Vector3 &v0, const Vector3 &v1, const Vector3 &point)
static Vector3	closestPointOnLineSegment (const Vector3 &v0, const Vector3 &v1, const Vector3 &edgeDirection, float edgeLength, const Vector3 &point)
static Vector3	closestPointOnTrianglePerimeter (const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, const Vector3 &point)
static Vector3	closestPointOnTrianglePerimeter (const Vector3 v[3], const Vector3 edgeDirection[3], const float edgeLength[3], const Vector3 &point, int &edgeIndex)
static bool	isPointInsideTriangle (const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, const Vector3 &normal, const Vector3 &point, float b[3], Vector3::Axis primaryAxis=Vector3::DETECT_AXIS)
static bool	isPointInsideTriangle (const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, const Vector3 &normal, const Vector3 &point, Vector3::Axis primaryAxis=Vector3::DETECT_AXIS)
static bool	movingSpherePassesThroughFixedBox (const Sphere &sphere, const Vector3 &velocity, const Box &box, double timeLimit=inf())
static bool	movingSpherePassesThroughFixedSphere (const Sphere &sphere, const Vector3 &velocity, const Sphere &fixedSphere, double timeLimit=inf())
static bool	fixedSolidSphereIntersectsFixedSolidSphere (const Sphere &sphere1, const Sphere &sphere2)
static bool	fixedSolidSphereIntersectsFixedSolidBox (const Sphere &sphere, const Box &box)
static bool	fixedSolidSphereIntersectsFixedTriangle (const Sphere &sphere, const Triangle &triangle)
static bool	fixedSolidBoxIntersectsFixedTriangle (const AABox &box, const Triangle &triangle)
static bool	isPointInsideRectangle (const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, const Vector3 &v3, const Vector3 &normal, const Vector3 &point)
static Vector3	closestPointToRectanglePerimeter (const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, const Vector3 &v3, const Vector3 &point)
static Vector3	closestPointToRectangle (const Vector3 &v0, const Vector3 &v1, const Vector3 &v2, const Vector3 &v3, const Vector3 &point)

Private Member Functions
	CollisionDetection ()
virtual	~CollisionDetection ()

Static Private Attributes
static Vector3	ignore
static bool	ignoreBool
static Array< Vector3 >	ignoreArray

Detailed Description

Collision detection primitives and tools for building higher order collision detection schemes.

These routines provide moving and static collision detection. Moving collision detection allows the calculation of collisions that occur during a period of time – as opposed to the intersection of two static bodies.

Moving collision detection routines detect collisions between only static primitives and moving spheres or points. Since the reference frame can be user defined, these functions can be used to detect the collision between two moving bodies by subtracting the velocity vector of one object from the velocity vector of the sphere or point the detection is to occur with. This unified velocity vector will act as if both objects are moving simultaneously.

Collisions are detected for single-sided objects only. That is, no collision is detected when leaving a primitive or passing through a plane or triangle opposite the normal... except for the point-sphere calculation or when otherwise noted.

For a sphere, the collision location returned is the point in world space where the surface of the sphere and the fixed object meet. It is not the position of the center of the sphere at the time of the collision.

The collision normal returned is the surface normal to the fixed object at the collision location.

Static Collision Detection: (Neither object is moving)

	Point3	LineSegment	Ray *	Line	Plane	Triangle	Sphere	Cylinder	Capsule	AABox	Box
Point3	P3::== V3::fuzzy distance
LineSegment	LS::closestPoint LS::distance CD
Ray *	Ray::closestPoint Ray::distance
Line	Line::closestPoint Line::distance		CD
Plane
Triangle
Sphere	Sphere::contains		CD , R::time			CD	CD
Cylinder	Cylinder::contains
Capsule	Capsule::contains					CD
AABox	AABox::contains					CD
Box	Box::contains	(treat as Ray)	CD	(treat as Ray)	CD	CD	CD	None (use OPCODE)	CD	CD	CD

Moving Collision Detection:

* Note: Moving collision detection against certain primitives is equivalent to static collision detection against a bigger primitive. Ray, Line Segment == moving Point''; Capsule ==moving Sphere''; Plane == ``moving Line''

Deprecated:

Routines moving to the G3D::Intersect class in G3D 9.0

Constructor & Destructor Documentation

G3D::CollisionDetection::CollisionDetection ( )

inlineprivate

{}

virtual G3D::CollisionDetection::~CollisionDetection ( )

inlineprivatevirtual

{}

Member Function Documentation

Vector3 G3D::CollisionDetection::bounceDirection ( const class Sphere &  sphere, const Vector3 &  velocity, const float  collisionTime, const Vector3 &  collisionLocation, const Vector3 &  collisionNormal  )

static

Finds the direction of bounce that a sphere would have when it intersects an object with the given time of collision, the collision location and the collision normal.

Note

This function works like a pong style ball bounce.

Parameters

sphere	Moving sphere.
velocity	Sphere's velocity.
collisionTime	Time of collision.
collisionLocation	Collision location.
collisionNormal	Surface collision normal.

Returns

Direction of bounce.

 {

 // Location when the collision occurs
 Vector3 sphereLocation = sphere.center + velocity * collisionTime;

 Vector3 normal = (sphereLocation - collisionLocation);
 if (fuzzyEq(normal.squaredMagnitude(), 0)) {
 normal = collisionNormal;
 } else {
 normal = normal.direction();
 }

 Vector3 direction = velocity.direction();

 // Reflect direction about the normal
 return direction - 2.0 * normal * normal.dot(direction);
}

Here is the call graph for this function:

Vector3 G3D::CollisionDetection::closestPointOnLineSegment ( const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  point  )

static

Finds the closest point on a line segment to a given point.

Parameters

v0	line vertex 1.
v1	line vertex 2.
point	External point.

Returns

Closests point to point on the line segment.

 {

 const Vector3& edge = (v1 - v0);
 float edgeLength = edge.magnitude();

 if (edgeLength == 0) {
 // The line segment is a point
 return v0;
 }

 return closestPointOnLineSegment(v0, v1, edge / edgeLength, edgeLength, point);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Vector3 G3D::CollisionDetection::closestPointOnLineSegment ( const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  edgeDirection, float  edgeLength, const Vector3 &  point  )

static

Finds the closest point on a line segment to a given point.

Note

This is an optimization to closestPointOnLineSegment. Edge length and direction can be used in this function if already pre-calculated. This prevents doing the same work twice.

Parameters

v0	line vertex 0.
v1	line vertex 1.
edgeDirection	The direction of the segment (unit length).
edgeLength	The length of the segment.
point	External point.

Returns

Closests point to point on the line segment.

 {

 debugAssert((v1 - v0).direction().fuzzyEq(edgeDirection));
 debugAssert(fuzzyEq((v1 - v0).magnitude(), edgeLength));

 // Vector towards the point
 const Vector3& c = point - v0;

 // Projected onto the edge itself
 float t = edgeDirection.dot(c);

 if (t <= 0) {
 // Before the start
 return v0;
 } else if (t >= edgeLength) {
 // After the end
 return v1;
 } else {
 // At distance t along the edge
 return v0 + edgeDirection * t;
 }
}

Here is the call graph for this function:

Vector3 G3D::CollisionDetection::closestPointOnTrianglePerimeter ( const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, const Vector3 &  point  )

static

Finds the closest point on the perimeter of the triangle to an external point; given a triangle defined by three points v0, v1, & v2, and the external point.

Parameters

v0	Triangle vertex 0.
v1	Triangle vertex 1.
v2	Triangle vertex 2.
point	External point.

Returns

Closests point to point on the perimeter of the triangle.

 {
 
 Vector3 v[3] = {v0, v1, v2};
 Vector3 edgeDirection[3] = {(v1 - v0), (v2 - v1), (v0 - v2)};
 float edgeLength[3];
 
 for (int i = 0; i < 3; ++i) {
 edgeLength[i] = edgeDirection[i].magnitude();
 edgeDirection[i] /= edgeLength[i];
 }

 int edgeIndex;
 return closestPointOnTrianglePerimeter(v, edgeDirection, edgeLength, point, edgeIndex);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Vector3 G3D::CollisionDetection::closestPointOnTrianglePerimeter ( const Vector3  v[3], const Vector3  edgeDirection[3], const float  edgeLength[3], const Vector3 &  point, int &  edgeIndex  )

static

Finds the closest point on the perimeter of the triangle to an external point; given a triangle defined by the array of points v, its edge directions and their lengths, as well as the external point.

Note

This is an optimization to closestPointToTrianglePerimeter. Edge length and direction can be used in this function if already pre-calculated. This prevents doing the same work twice.

Parameters

v	Triangle vertices.
point	External point.
edgeIndex	The point lies on the edge between v[edgeIndex] and v[(edgeIndex + 1) % 3]

Returns

Closest point to point on the perimeter of the triangle.

 {

 // Closest point on segment from v[i] to v[i + 1]
 Vector3 r[3];

 // Distance squared from r[i] to point
 float d[3];

 // Index of the next point
 static const int next[] = {1, 2, 0};

 for (int i = 0; i < 3; ++i) {
 r[i] = closestPointOnLineSegment(v[i], v[next[i]], edgeDirection[i], edgeLength[i], point);
 d[i] = (r[i] - point).squaredMagnitude();
 }

 if (d[0] < d[1]) {
 if (d[0] < d[2]) {
 // Between v0 and v1
 edgeIndex = 0;
 } else {
 // Between v2 and v0
 edgeIndex = 2;
 }
 } else {
 if (d[1] < d[2]) {
 // Between v1 and v2
 edgeIndex = 1;
 } else {
 // Between v2 and v0
 edgeIndex = 2;
 }
 }

# ifdef G3D_DEBUG
 {
 Vector3 diff = r[edgeIndex] - v[edgeIndex];
 debugAssertM(fuzzyEq(diff.direction().dot(edgeDirection[edgeIndex]), 1.0f) ||
 diff.fuzzyEq(Vector3::zero()), "Point not on correct triangle edge");
 float frac = diff.dot(edgeDirection[edgeIndex])/edgeLength[edgeIndex];
 debugAssertM(frac >= -0.000001, "Point off low side of edge.");
 debugAssertM(frac <= 1.000001, "Point off high side of edge.");
 }
# endif

 return r[edgeIndex];
}

Here is the call graph for this function:

void G3D::CollisionDetection::closestPointsBetweenLineAndLine ( const Line &  line1, const Line &  line2, Vector3 &  closest1, Vector3 &  closest2  )

static

Calculates the closest points on two lines with each other. If the lines are parallel then using the starting point, else calculate the closest point on each line to the other.

Note

This is very similiar to calculating the intersection of two lines. Logically then, the two points calculated would be identical if calculated with inifinite precision, but with the finite precision of floating point calculations, these values could (will) differ as the line slope approaches zero or inifinity.

[variables] and algorithm based on derivation at the following website: http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm

Parameters

line1	Line 1.
line2	Line 2.
closest1	Closest point on line 1.
closest2	Closest point on line 2.

 {
 // TODO make accessors for Line that don't make a copy of data
 Vector3 P0 = line1.point();
 Vector3 u = line1.direction();
 Vector3 Q0 = line2.point();
 Vector3 v = line2.direction();
 Vector3 w0 = P0 - Q0;

 // a = 1.0, c = 1.0
 double b = dot(u, v);
 double d = dot(u, w0);
 double e = dot(v, w0);
 double D = 1.0 - b * b;
 double sc, tc;

 static const double epsilon = 0.00001;

 if (D < epsilon) {
 // lines are parallel, choose P0 as one point, find the point
 // on line2 that is closest to P0
 sc = 0.0;
 tc = (b > 1.0) ? (d / b) : (e / 1.0);
 } else {
 // lines are not parallel
 sc = (b * e - 1.0 * d) / D;
 tc = (1.0 * e - b * d) / D;
 }

 closest1 = P0 + (sc * u);
 closest2 = Q0 + (tc * v);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Vector3 G3D::CollisionDetection::closestPointToRectangle ( const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, const Vector3 &  v3, const Vector3 &  point  )

static

Finds the closest point in the rectangle to an external point; Given a rectangle defined by four points v0, v1, v2, & v3, and the external point.

Parameters

v0	Rectangle vertex 1.
v1	Rectangle vertex 2.
v2	Rectangle vertex 3
v3	Rectangle vertex 4.
point	External point.

Returns

Closet point in the rectangle to the external point.

 {

 Plane plane(v0, v1, v2);

 // Project the point into the plane
 double a, b, c, d;
 plane.getEquation(a, b, c, d);
 
 double distance = a*point.x + b*point.y + c*point.z + d;
 Vector3 planePoint = point - distance * plane.normal();

 if (isPointInsideRectangle(v0, v1, v2, v3, plane.normal(), planePoint)) {
 return planePoint;
 } else {
 return closestPointToRectanglePerimeter(v0, v1, v2, v3, planePoint);
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Vector3 G3D::CollisionDetection::closestPointToRectanglePerimeter ( const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, const Vector3 &  v3, const Vector3 &  point  )

static

Finds the closest point on the perimeter of the rectangle to an external point; given a rectangle defined by four points v0, v1, v2, & v3, and the external point.

Parameters

v0	Rectangle vertex 1.
v1	Rectangle vertex 2.
v2	Rectangle vertex 3.
v3	Rectangle vertex 4.
point	External point.

Returns

Closests point to point on the perimeter of the rectangle.

 {

 Vector3 r0 = closestPointOnLineSegment(v0, v1, point);
 Vector3 r1 = closestPointOnLineSegment(v1, v2, point);
 Vector3 r2 = closestPointOnLineSegment(v2, v3, point);
 Vector3 r3 = closestPointOnLineSegment(v3, v0, point);

 double d0 = (r0 - point).squaredMagnitude();
 double d1 = (r1 - point).squaredMagnitude();
 double d2 = (r2 - point).squaredMagnitude();
 double d3 = (r3 - point).squaredMagnitude();

 if (d0 < d1) {
 if (d0 < d2) {
 if (d0 < d3) {
 return r0;
 } else {
 return r3;
 }
 } else {
 if (d2 < d3) {
 return r2;
 } else {
 return r3;
 }
 }
 } else {
 if (d1 < d2) {
 if (d1 < d3) {
 return r1;
 } else {
 return r3;
 }
 } else {
 if (d2 < d3) {
 return r2;
 } else {
 return r3;
 }
 }
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool G3D::CollisionDetection::collisionLocationForMovingPointFixedAABox ( const Vector3 &  point, const Vector3 &  velocity, const class AABox &  box, Vector3 &  outLocation, bool &  inside = ignoreBool, Vector3 &  normal = ignore  )

static

Calculates time between the intersection of a moving point and a fixed Axis-Aligned Box (AABox).

Note

Avoids the sqrt from collisionTimeForMovingPointFixedAABox.

Parameters

point	Moving point.
velocity	Sphere's velocity.
box	Fixed AAbox.
outLocation	Location of collision. [Post Condition]
inside	Does the ray originate inside the box? [Post Condition]
normal	Box's surface normal to collision [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 // Integer representation of a floating-point value.
 #define IR(x) ((uint32&)x)

 Inside = true;
 const Vector3& MinB = box.low();
 const Vector3& MaxB = box.high();
 Vector3 MaxT(-1.0f, -1.0f, -1.0f);

 // Find candidate planes.
 for (int i = 0; i < 3; ++i) {
 if (origin[i] < MinB[i]) {
 location[i] = MinB[i];
 Inside = false;

 // Calculate T distances to candidate planes
 if (IR(dir[i])) {
 MaxT[i] = (MinB[i] - origin[i]) / dir[i];
 }
 } else if (origin[i] > MaxB[i]) {
 location[i] = MaxB[i];
 Inside = false;

 // Calculate T distances to candidate planes
 if (IR(dir[i])) {
 MaxT[i] = (MaxB[i] - origin[i]) / dir[i];
 }
 }
 }

 if (Inside) {
 // Ray origin inside bounding box
 location = origin;
 return false;
 }

 // Get largest of the maxT's for final choice of intersection
 int WhichPlane = 0;
 if (MaxT[1] > MaxT[WhichPlane]) {
 WhichPlane = 1;
 }

 if (MaxT[2] > MaxT[WhichPlane]) {
 WhichPlane = 2;
 }

 // Check final candidate actually inside box
 if (IR(MaxT[WhichPlane]) & 0x80000000) {
 // Miss the box
 return false;
 }

 for (int i = 0; i < 3; ++i) {
 if (i != WhichPlane) {
 location[i] = origin[i] + MaxT[WhichPlane] * dir[i];
 if ((location[i] < MinB[i]) ||
 (location[i] > MaxB[i])) {
 // On this plane we're outside the box extents, so
 // we miss the box
 return false;
 }
 }
 }

 // Choose the normal to be the plane normal facing into the ray
 normal = Vector3::zero();
 normal[WhichPlane] = (dir[WhichPlane] > 0) ? -1.0 : 1.0;

 return true;

 #undef IR
}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingPointFixedAABox ( const Vector3 &  point, const Vector3 &  velocity, const class AABox &  box, Vector3 &  outLocation, bool &  inside = ignoreBool, Vector3 &  outNormal = ignore  )

static

If the ray origin is inside the box, returns inf() but inside is set to true. Beta API

[Andrew] Woo, from "Graphics Gems", Academic Press, 1990 [Optimized] code by Pierre Terdiman, 2000 (~20-30% faster on Celeron 500) [Epsilon] value added by Klaus Hartmann [http://www.codercorner.com/RayAABB.cpp]

 {

 if (collisionLocationForMovingPointFixedAABox(origin, dir, box, location, Inside, normal)) {
 return (location - origin).magnitude();
 } else {
 return (float)finf();
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingPointFixedBox ( const Vector3 &  point, const Vector3 &  velocity, const class Box &  box, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving point and a fixed box.

Note

If the point is already inside the box, no collision: inf is returned.

Parameters

point	Moving point.
velocity	Sphere's velocity.
box	Fixed box.
outLocation	Position of collision. [Post Condition]
outNormal	Box's surface normal to collision [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 double bestTime;

 Vector3 normal;
 Vector3 v[4];

 // Prime the loop
 int f = 0;
 box.getFaceCorners(f, v[0], v[1], v[2], v[3]);
 bestTime = collisionTimeForMovingPointFixedRectangle(point, velocity, v[0], v[1], v[2], v[3], location, normal);
 outNormal = normal;

 // Check other faces
 for (f = 1; f < 6; ++f) {
 Vector3 pos;
 box.getFaceCorners(f, v[0], v[1], v[2], v[3]);
 float time = collisionTimeForMovingPointFixedRectangle(point, velocity, v[0], v[1], v[2], v[3], pos, normal);
 if (time < bestTime) {
 bestTime = time;
 outNormal = normal;
 location = pos;
 }
 }

 return bestTime;
}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingPointFixedCapsule ( const Vector3 &  point, const Vector3 &  velocity, const class Capsule &  capsule, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving point and a fixed capsule.

Parameters

point	Moving point.
velocity	Point's velocity.
capsule	Fixed capsule.
outLocation	Location of collision. [Post Condition]
outNormal	Capsule's surface normal to collision [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 float timeScale = velocity.magnitude();

 if (timeScale == 0.0f) {
 timeScale = 1;
 }

 Vector3 direction = velocity / timeScale;
 int numIntersections;
 Vector3 intersection[2];
 findRayCapsuleIntersection(Ray::fromOriginAndDirection(_point, direction), capsule, numIntersections, intersection);

 if (numIntersections == 2) {
 // A collision can only occur if there are two intersections. If there is one
 // intersection, that one is exiting the capsule. 

 // Find the entering intersection (the first one that occurs).
 float d0 = (intersection[0] - _point).squaredMagnitude();
 float d1 = (intersection[1] - _point).squaredMagnitude();

 // Compute the surface normal (if we aren't ignoring the result)
 if (&outNormal != &ignore) {
 Vector3 p2 = LineSegment::fromTwoPoints(capsule.point(0), capsule.point(1)).closestPoint(_point);
 outNormal = (_point - p2).direction();
 }

 if (d0 > d1) {
 location = intersection[1];
 return sqrt(d1) / timeScale;
 } else {
 location = intersection[0];
 return sqrt(d0) / timeScale;
 }
 } else {
 // No entering intersection discovered; return no intersection.
 location = Vector3::inf();
 return finf();
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingPointFixedPlane ( const Vector3 &  point, const Vector3 &  velocity, const class Plane &  plane, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving point and a fixed plane.

Note

This is only a one sided collision test. The side defined by the plane's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal.

Parameters

point	Moving point.
velocity	Point's velocity.
plane	Fixed plane.
outLocation	Location of collision. [Post Condition] (Infinite vector on no collision)
outNormal	Plane's surface normal. [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 // Solve for the time at which normal.dot(point + velocity) + d == 0.
 float d;
 Vector3 normal;
 plane.getEquation(normal, d);
 
 const float vdotN = velocity.dot(normal);
 const float pdotN = point.dot(normal);

 if (fuzzyEq(pdotN + d, 0.0f)) {
 // The point is *in* the plane.
 location = point;
 outNormal = normal;
 return 0;
 }

 if (vdotN >= 0.0f) {
 // no collision will occur
 location = Vector3::inf();
 return finf();
 }

 const float t = -(pdotN + d) / vdotN;
 if (t < 0) {
 location = Vector3::inf();
 return finf();
 } else {
 location = point + velocity * t;
 outNormal = normal;
 return t;
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingPointFixedRectangle ( const Vector3 &  point, const Vector3 &  velocity, const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, const Vector3 &  v3, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving point and a fixed rectangle defined by the points v0, v1, v2, & v3.

Note

This is only a one sided collision test. The side defined by the rectangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal.

Parameters

point	Moving point.
velocity	Sphere's velocity.
v0	Rectangle vertex 1.
v1	Rectangle vertex 2.
v2	Rectangle vertex 3
v3	Rectangle vertex 4.
outLocation	Location of collision [Post Condition]
outNormal	Rectangle's surface normal. [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 Plane plane = Plane(v0, v1, v2);

 float time = collisionTimeForMovingPointFixedPlane(point, velocity, plane, location, outNormal);

 if (time == finf()) {
 // No collision is ever going to happen
 return time;
 }

 if (isPointInsideRectangle(v0, v1, v2, v3, plane.normal(), location)) {
 // The intersection point is inside the rectangle; that is the location where
 // the point hits the rectangle.
 return time;
 } else {
 return finf();
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingPointFixedSphere ( const Vector3 &  point, const Vector3 &  velocity, const class Sphere &  sphere, Vector3 &  outLocation, Vector3 &  outNormal = ignore, bool  solid = false  )

static

Calculates time between the intersection of a moving point and a fixed sphere.

Note

When ray is starts inside the rectangle, the exiting intersection is detected.

Parameters

point	Moving point.
velocity	Point's velocity.
sphere	Fixed Sphere.
outLocation	Location of collision. [Post Condition]
outNormal	Sphere's surface normal to collision [Post Condition]
solid	If true, rays inside the sphere immediately intersect (good for collision detection). If false, they hit the opposite side of the sphere (good for ray tracing).

Returns

Time until collision. If there is no collision then the return value will be inf().

 {

 if (solid && sphere.contains(point)) {
 location = point;
 outNormal = (point - sphere.center).direction();
 return 0.0f;
 }

 float speed = velocity.magnitude();
 const Vector3& direction = velocity / speed;

 // length of the axis between the start and the sphere
 const Vector3& L = sphere.center - point;
 float d = L.dot(direction);

 float L2 = L.dot(L);
 float R2 = square(sphere.radius);
 float D2 = square(d);

 if ((d < 0.0f) && (L2 > R2)) {
 location = Vector3::inf();
 return finf();
 }

 const float M2 = L2 - D2;

 if (M2 > R2) {
 location = Vector3::inf();
 return finf();
 }

 float q = sqrt(R2 - M2);
 float time;

 if (L2 > R2) {
 time = d - q;
 } else {
 time = d + q;
 }

 time /= speed;

 location = point + velocity * time;
 outNormal = (location - sphere.center).direction();

 return time;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static float G3D::CollisionDetection::collisionTimeForMovingPointFixedTriangle ( const Vector3 &  orig, const Vector3 &  dir, const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2  )

inlinestatic

Calculates time between the intersection of a moving point and a fixed triangle.

Note

This is only a one sided collision test. The side defined by the triangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal.

Parameters

orig	Moving point.
dir	Point's velocity.
v0	Triangle vertex 1.
v1	Triangle vertex 2.
v2	Triangle vertex 3

Returns

Time til collision. If there is no collision then the return value will be inf().

 {
 return Ray::fromOriginAndDirection(orig, dir).intersectionTime(v0, v1, v2);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

static float G3D::CollisionDetection::collisionTimeForMovingPointFixedTriangle ( const Vector3 &  orig, const Vector3 &  dir, const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, Vector3 &  location  )

inlinestatic

Calculates time between the intersection of a moving point and a fixed triangle.

Note

This is only a one sided collision test. The side defined by the triangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal.

Parameters

orig	Moving point.
dir	Point's velocity.
v0	Triangle vertex 1.
v1	Triangle vertex 2.
v2	Triangle vertex 3
location	Location of collision. [Post Condition] (Infinite vector on no collision)

Returns

Time til collision. If there is no collision then the return value will be inf().

 {
 float t = collisionTimeForMovingPointFixedTriangle(orig, dir, v0, v1, v2);
 if (t < finf()) {
 location = orig + dir * t;
 }
 return t;
 }

Here is the call graph for this function:

static float G3D::CollisionDetection::collisionTimeForMovingPointFixedTriangle ( const Vector3 &  orig, const Vector3 &  dir, const Triangle &  tri, Vector3 &  location = ignore, Vector3 &  normal = ignore  )

inlinestatic

Calculates time between the intersection of a moving point and a fixed triangle.

Note

This is only a one sided collision test. The side defined by the triangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal.

Parameters

orig	Moving point.
dir	Point's velocity.
tri	Fixed triangle.
location	Location of collision. [Post Condition] (Infinite vector on no collision)
normal	Triangle's surface normal. [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 float t = collisionTimeForMovingPointFixedTriangle(
 orig, dir, tri.vertex(0), tri.vertex(1), tri.vertex(2));
 
 if ((t < finf()) && (&location != &ignore)) {
 location = orig + dir * t;
 normal = tri.normal();
 }
 return t;
 }

Here is the call graph for this function:

static float G3D::CollisionDetection::collisionTimeForMovingPointFixedTriangle ( const Vector3 &  orig, const Vector3 &  dir, const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, Vector3 &  location, Vector3 &  normal  )

inlinestatic

Calculates time between the intersection of a moving point and a fixed triangle.

Note

This is only a one sided collision test. The side defined by the triangle's surface normal is the only one tested. For a two sided collision, call the function once for each side's surface normal.

Parameters

orig	Moving point.
dir	Point's velocity.
v0	Triangle vertex 1.
v1	Triangle vertex 2.
v2	Triangle vertex 3
location	Location of collision. [Post Condition] (Infinite vector on no collision)
normal	Triangle's surface normal. [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {
 float t = collisionTimeForMovingPointFixedTriangle(orig, dir, v0, v1, v2);
 if (t < finf()) {
 location = orig + dir * t;
 normal = (v1 - v0).cross(v2 - v0).direction();
 }
 return t;
 }

Here is the call graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingSphereFixedBox ( const class Sphere &  sphere, const Vector3 &  velocity, const class Box &  box, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving sphere and a fixed box.

Note

This function will not detect an intersection between a moving object that is already interpenetrating the fixed object.

Parameters

sphere	Moving sphere.
velocity	Sphere's velocity.
box	Fixed box.
outLocation	Location of collision – not center position of sphere at the collision time. [Post Condition]
outNormal	Box's surface normal to collision [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 if (fixedSolidSphereIntersectsFixedSolidBox(sphere, box)) {
 // TODO: Compute more useful location and normal?
 location = sphere.center;
 outNormal = Vector3::zero();
 return 0;
 }

 float bestTime;

 Vector3 v[4];
 int f = 0;
 box.getFaceCorners(f, v[0], v[1], v[2], v[3]);
 bestTime = collisionTimeForMovingSphereFixedRectangle(sphere, velocity, v[0], v[1], v[2], v[3], location, outNormal);

 for (f = 1; f < 6; ++f) {
 Vector3 pos, normal;
 box.getFaceCorners(f, v[0], v[1], v[2], v[3]);
 float time = collisionTimeForMovingSphereFixedRectangle(sphere, velocity, v[0], v[1], v[2], v[3], pos, normal);
 if (time < bestTime) {
 bestTime = time;
 location = pos;
 outNormal = normal;
 }
 }

 return bestTime;
}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingSphereFixedCapsule ( const class Sphere &  sphere, const Vector3 &  velocity, const class Capsule &  capsule, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving sphere and a fixed capsule.

Note

This won't detect a collision if the sphere is already interpenetrating the capsule.

Parameters

sphere	Moving sphere.
velocity	Sphere's velocity.
capsule	Fixed capsule.
outLocation	Location of collision – not center position of sphere at the collision time. [Post Condition]
outNormal	Capsule's surface normal to the collision [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 (void)outNormal;

 Capsule _capsule(capsule.point(0), capsule.point(1), capsule.radius() + sphere.radius);

 Vector3 normal;
 double time = collisionTimeForMovingPointFixedCapsule(sphere.center, velocity, _capsule, location, normal);
 
 if (time < finf()) {
 // Location is now the position of the center of the sphere at the time of collision.
 // We have to adjust the collision location for the size of the sphere.
 location -= sphere.radius * normal;
 }

 return time;
}

Here is the call graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingSphereFixedPlane ( const class Sphere &  sphere, const Vector3 &  velocity, const class Plane &  plane, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving sphere and a fixed triangle.

Parameters

sphere	Moving sphere.
velocity	Sphere's velocity.
plane	Fixed Plane.
outLocation	Location of collision – not center position of sphere at the collision time. [Post Condition]
outNormal	Box's surface normal to collision [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 if (sphere.radius == 0) {
 // Optimization for zero radius sphere
 return collisionTimeForMovingPointFixedPlane(sphere.center, velocity, plane, location, outNormal);
 }

 // The world-space collision point, which lies on the surface of the sphere, will be the point at
 // center + velocity * time - (radius * planeNormal). Collisions only occur when
 // the sphere is travelling into the plane.

 float d;
 plane.getEquation(outNormal, d);
 
 // Rate at which the sphere is approaching the plane
 const float vdotN = velocity.dot(outNormal);

 if (fuzzyGt(vdotN, 0)) {
 // No collision when the sphere is moving towards a backface.
 location = Vector3::inf();
 return (float)finf();
 }

 // Initial distance from the sphere center to the plane
 const float distance = sphere.center.dot(outNormal) + d;

 if (fuzzyLe(G3D::abs(distance), sphere.radius)) {
 // Already interpenetrating
 location = sphere.center - distance * outNormal;
 return 0;
 } else {
 // The point on the sphere (in world space) that will eventually first contact the plane
 const Point3& point = sphere.center - (sphere.radius * outNormal);

 // The problem is now reduced to finding when the point hits the plane
 return collisionTimeForMovingPointFixedPlane(point, velocity, plane, location, outNormal);
 }

}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingSphereFixedRectangle ( const class Sphere &  sphere, const Vector3 &  velocity, const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, const Vector3 &  v3, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving sphere and a fixed rectangle defined by the points v0, v1, v2, & v3.

Parameters

sphere	Moving sphere.
velocity	Sphere's velocity.
v0	Rectangle vertex 1.
v1	Rectangle vertex 2.
v2	Rectangle vertex 3
v3	Rectangle vertex 4.
outLocation	Location of collision – not center position of sphere at the collision time. [Post Condition]
outNormal	Box's surface normal to collision [Post Condition]

Returns

Time til collision. If there is no collision then the return value will be inf().

 {

 Plane plane(v0, v1, v2);

 float time = collisionTimeForMovingSphereFixedPlane(sphere, velocity, plane, location, outNormal);

 if (time == finf()) {
 // No collision is ever going to happen
 return time;
 }

 if (isPointInsideRectangle(v0, v1, v2, v3, plane.normal(), location)) {
        // The intersection point is inside the rectangle; that is the location where
        // the sphere hits the rectangle.
        return time;
    }

    // Switch over to moving the rectangle towards a fixed sphere and see at what time
    // they will hit.

    Vector3 point = closestPointToRectanglePerimeter(v0, v1, v2, v3, sphere.center);

    Vector3 dummy;
    double t = collisionTimeForMovingPointFixedSphere(point, -velocity, sphere, location, dummy);

    // Normal is the plane normal, location is the original location of the point.
    location = point;

    return t;
}

Here is the call graph for this function:

Here is the caller graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingSphereFixedSphere ( const Sphere &  sphere, const Vector3 &  velocity, const Sphere &  fixedSphere, Vector3 &  outLocation, Vector3 &  outNormal = ignore  )

static

Calculates time between the intersection of a moving sphere and a fixed sphere.

If they are already interpenetrating, returns 0 and location is the closest point on the surface of the fixed sphere to the center of the moving sphere.

Parameters

sphere	Moving sphere.
velocity	Sphere's velocity.
fixedSphere	Fixed Sphere.
outLocation	Location of collision – not center position of sphere at the collision time. [Post Condition]
outNormal	Moving sphere's surface normal to collision [Post Condition]

Returns

Time until collision. If there is no collision then the return value will be inf().

                               {

    const Vector3& sep = (fixedSphere.center - movingSphere.center);
    float sepLen = sep.squaredLength();
    if (sepLen < square(movingSphere.radius + fixedSphere.radius)) {
        // Interpenetrating
        outNormal   = sep.directionOrZero();
        location = fixedSphere.center - outNormal * fixedSphere.radius;
        return 0;
    }

    float time = collisionTimeForMovingPointFixedSphere
        (movingSphere.center, velocity, 
         Sphere(fixedSphere.center, fixedSphere.radius + movingSphere.radius), 
         location, outNormal);

    if (time < finf()) {
        // Location is now the center of the moving sphere at the collision time.
        // Adjust for the size of the moving sphere.  Two spheres always collide
        // along a line between their centers.
        location += (location - fixedSphere.center) * movingSphere.radius / fixedSphere.radius;
    }

    return time;
}

Here is the call graph for this function:

float G3D::CollisionDetection::collisionTimeForMovingSphereFixedTriangle ( const class Sphere &  sphere, const Vector3 &  velocity, const Triangle &  triangle, Vector3 &  outLocation, float  b[3] = (float*)&ignore  )

static

Calculates time between the intersection of a moving sphere and a fixed triangle.

Parameters

sphere	The moving sphere.
velocity	The sphere's velocity.
triangle	Single-sided fixed triangle.
outLocation	Location of collision, if collision occurs – not center position of sphere at the collision time. If there is interpenetration at the start, this point may be inside the sphere.
b	Barycentric coordinates. These are not valid unless collision occurs.

Returns

Time until collision. If there is no collision then the return value will be finf().

                                   {

    if (velocity.dot(triangle.normal()) > 0.0f) {
        // No collision if moving towards a backface
        return finf();
    }
    Vector3 dummy;
    const float time = collisionTimeForMovingSphereFixedPlane(sphere, velocity, triangle.plane(), 
                                                        outLocation, dummy);

    if (time == finf()) {
        // No collision is ever going to happen
        return time;
    }

    // We will hit the plane of the triangle at *time*. See if
    // the intersection point actually is within the triangle.

    if (isPointInsideTriangle(triangle.vertex(0), triangle.vertex(1), triangle.vertex(2), triangle.normal(), 
        outLocation, b, triangle.primaryAxis())) {

        // The intersection point is inside the triangle; that is the location where
        // the sphere hits the triangle.

#       ifdef G3D_DEBUG
        {
            // Internal consistency checks
            debugAssertM(b[0] >= 0.0 && b[0] <= 1.0f, "Intersection is outside triangle.");
            debugAssertM(b[1] >= 0.0 && b[1] <= 1.0f, "Intersection is outside triangle.");
            debugAssertM(b[2] >= 0.0 && b[2] <= 1.0f, "Intersection is outside triangle.");
            const Vector3& blend = 
                b[0] * triangle.vertex(0) + 
                b[1] * triangle.vertex(1) + 
                b[2] * triangle.vertex(2);
            debugAssertM(blend.fuzzyEq(outLocation), "Barycentric coords don't match intersection.");
            // Call again so that we can debug the problem
            // isPointInsideTriangle(triangle.vertex(0), triangle.vertex(1), triangle.vertex(2), triangle.normal(), 
            // outLocation, b, triangle.primaryAxis());
        }
#       endif

        return time;
    }

    // The collision (if it exists) is with a point on the triangle perimeter.
    // Switch over to moving the triangle towards a fixed sphere and see at what time
    // they will hit.

    // Closest point on the triangle to the sphere intersection with the plane.
    int edgeIndex;
    const Vector3& point = closestPointOnTrianglePerimeter(triangle._vertex, triangle.edgeDirection,
                                                           triangle.edgeMagnitude, outLocation, edgeIndex);

    float t = 0;
    if (! sphere.contains(point)) {
        // The point is outside the sphere--see when it will hit
        t = collisionTimeForMovingPointFixedSphere(point, -velocity, sphere, dummy, dummy);
    }

    if (t < finf()) {
        outLocation = point;
        // Compute Barycentric coords

        // Index of the next vertex
        static const int next[] = {1, 2, 0};

        // Project along the edge in question.
        // Avoid sqrt by taking advantage of the existing edgeDirection unit vector.
        b[next[edgeIndex]] = (outLocation - triangle._vertex[edgeIndex]).dot
            (triangle.edgeDirection[edgeIndex]) / triangle.edgeMagnitude[edgeIndex];

        b[edgeIndex] = 1.0f - b[next[edgeIndex]];

        b[next[next[edgeIndex]]] = 0.0f;

#       ifdef G3D_DEBUG
        {
            // Internal consistency checks
            for (int i = 0; i < 3; ++i) {
                debugAssertM(fuzzyGe(b[i], 0.0f) && fuzzyLe(b[i], 1.0f), "Intersection is outside triangle.");
            }
            Vector3 blend = 
                b[0] * triangle.vertex(0) + 
                b[1] * triangle.vertex(1) + 
                b[2] * triangle.vertex(2);
            debugAssertM(blend.fuzzyEq(outLocation), 
                format("Barycentric coords don't match intersection. %s != %s", 
                    blend.toString().c_str(), 
                    outLocation.toString().c_str()));    

            // Call again so that we can debug the problem
            collisionTimeForMovingPointFixedSphere(point, -velocity, sphere, dummy, dummy);
        }
#       endif

        // Due to tiny roundoffs, these values might be slightly out of bounds.
        // Ensure that they are legal.  Note that the above debugging code
        // verifies that we are not clamping truly illegal values.
        for (int i = 0; i < 3; ++i) {
            b[i] = clamp(b[i], 0.0f, 1.0f);
        }
    }

    // The collision occured at the point, if it occured.  The normal
    // was the plane normal, computed above.

    return t;
}

Here is the call graph for this function:

bool G3D::CollisionDetection::conservativeBoxBoxTest ( const Vector3 &  a, const Vector3 &  b, const Vector3 &  D  )

static

Performs a simple bounding sphere check between two boxes to determine whether these boxes could possibly intersect. This is a very cheap operation (three dot products, two sqrts and a few others). If it returns true, an intersection is possible, but not necessarily guaranteed.

Parameters

a	Vector from box A's center to an outer vertex
b	Vector from box B's center to an outer vertex
D	Distance between the centers of the two boxes

Returns

true - if possible intersection

false - otherwise (This does not guarantee an intersection)

                                                                 {
    // do a quick bounding sphere test because it is relatively
    // cheap, (three dot products, two sqrts, and a few others)
    double boxRadius1 = a.magnitude();
    double boxRadius2 = b.magnitude();
    return (D.squaredMagnitude() < square(boxRadius1 + boxRadius2));
}

Here is the call graph for this function:

void G3D::CollisionDetection::fillSolidBoxSolidBoxInfo ( const Box &  box1, const Box &  box2, Vector3 &  a, Vector3 &  b, Vector3 &  D, double *  c, double *  ca, double *  ad, double *  bd  )

static

Creates a set of standard information about two boxes in order to solve for their collision. This information includes a vector to the radius of the bounding sphere for each box, the vector between each boxes' center and a series of dot products between differing important vectors. These dot products include those between the axes of both boxes (signed and unsigned values), and the dot products between all the axes of box1 and the boxes' center vector and box2 and the boxes' center vector.

Precondition

The following space requirements must be met:

• c[] 9 elements
• ca[] 9 elements
• ad[] 3 elements
• bd[] 3 elements

[dobted] from David Eberly's papers, variables used in this function correspond to variables used in pages 6 and 7 in the pdf http://www.magic-software.com/Intersection.html http://www.magic-software.com/Documentation/DynamicCollisionDetection.pdf

Note

Links are out-dated. (Kept to preserve origin and authorship)

Parameters

box1	Box 1
box2	Box 2
a	Box 1's bounding sphere vector
b	Box 2's bounding sphere vector
D	Vector between Box 1 and Box 2's center points
c	Pointer to array of dot products of the axes of Box 1 and Box 2.
ca	Pointer to array of unsigned dot products of the axes of Box 1 and Box 2.
ad	Pointer to array of dot products of Box 1 axes and D.
bd	Pointer to array of dot products of Box 2 axes and D.

                    {
    // length between center and each side of box1 and box2
    a = box1.extent() * 0.5;
    b = box2.extent() * 0.5;

    // difference between centers of box1 and box2
    D = box2.center() - box1.center();

    // store the value of all possible dot products between the
    // axes of box1 and box2, c_{row, col} in the Eberly paper
    // corresponds to c[row * 3 + col] for this 9 element array.
    //
    // c[] holds signed values, ca[] hold absolute values
    for (int i = 0; i < 9; ++i) {
        c[i] = dot(box1.axis(i / 3), box2.axis(i % 3));
        ca[i] = fabs(c[i]);
    }

    // store all possible dot products between the axes of box1 and D,
    // as well as the axes of box2 and D
    for (int i = 0; i < 3; ++i) {
        ad[i] = dot(box1.axis(i), D);
        bd[i] = dot(box2.axis(i), D);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool G3D::CollisionDetection::fixedSolidBoxIntersectsFixedSolidBox ( const Box &  box1, const Box &  box2, const int  lastSeparatingAxis = -1  )

static

Determines whether two fixed solid boxes intersect.

Note

To speed up collision detection, the lastSeparatingAxis from the previous time step can be passed in and that plane can be checked first. If the separating axis was not saved, or if the two boxes intersected then lastSeparatingAxis should equal -1.

[Adobted] from David Eberly's papers, variables used in this function correspond to variables used in pages 6 and 7 in the pdf http://www.magic-software.com/Intersection.html http://www.magic-software.com/Documentation/DynamicCollisionDetection.pdf

Parameters

box1	Box 1.
box2	Box 2.
lastSeparatingAxis	Last separating axis. (optimization - see note)

Returns

true - Intersection.

false - otherwise.

                                         {
    // for explanations of the variable please refer to the
    // paper and fillSolidBoxSolidBoxInfo()
    Vector3 a;
    Vector3 b;
    Vector3 D;
    double c[9];
    double ca[9];
    double ad[3];
    double bd[3];

    fillSolidBoxSolidBoxInfo(box1, box2, a, b, D, c, ca, ad, bd);

    int dummy1, dummy2;
    bool parallelAxes = parallelAxisForSolidBoxSolidBox(ca, 0.00001,
            dummy1, dummy2);

    // check the separating axis from the last time step
    if (lastSeparatingAxis != -1 &&
            (lastSeparatingAxis < 6 || !parallelAxes)) {
        double projectedDistance = projectedDistanceForSolidBoxSolidBox(
                lastSeparatingAxis, a, b, D, c, ca, ad, bd);

        // the separating axis from the last time step is still
        // valid, the boxes do not intersect
        if (projectedDistance > 0.0) {
            return false;
        }
    }

    // test if the boxes can be separated by a plane normal to
    // any of the three axes of box1, any of the three axes of box2,
    // or any of the 9 possible cross products of axes from box1
    // and box2
    for (int i = 0; i < 15; ++i) {
        // do not need to check edge-edge cases if any two of
        // the axes are parallel
        if (parallelAxes && i == 6) {
            return true;
        }

        double projectedDistance =
            projectedDistanceForSolidBoxSolidBox(i, a, b, D, c, ca, ad, bd);

        // found a separating axis, the boxes do not intersect
        if (projectedDistance > 0.0) {
            return false;
        }
    }

    return true;
}

Here is the call graph for this function:

bool G3D::CollisionDetection::fixedSolidBoxIntersectsFixedTriangle ( const AABox &  box, const Triangle &  triangle  )

static

                                          {

    //    use separating axis theorem to test overlap between triangle and box 
    //    need to test for overlap in these directions: 
    //    1) the {x,y,z}-directions (actually, since we use the AABB of the triangle 
    //       we do not even need to test these) 
    //    2) normal of the triangle 
    //    3) crossproduct(edge from tri, {x,y,z}-direction) 
    //       this gives 3x3=9 more tests 

    // This is the fastest branch (on Sun).
    // Move the triangle to the object space of the box
    // Triangle vertices in box object space

    const Vector3& boxcenter = box.center();
    const Vector3& boxhalfsize = box.extent() * 0.5f;

    const Vector3& v0 = tri.vertex(0) - boxcenter;
    const Vector3& v1 = tri.vertex(1) - boxcenter;
    const Vector3& v2 = tri.vertex(2) - boxcenter;

    // Compute triangle edges in object space
    const Vector3& e0 = v1 - v0;
    const Vector3& e1 = v2 - v1;
    const Vector3& e2 = v0 - v2;

    // Bullet 3: 
    //  test the 9 tests first (this was faster) 
    float min,max,p0,p1,p2,rad;
    Vector3 fe;

    fe = abs(e0);
    AXISTEST_X01(e0[Z], e0[Y], fe[Z], fe[Y]);
    AXISTEST_Y02(e0[Z], e0[X], fe[Z], fe[X]);
    AXISTEST_Z12(e0[Y], e0[X], fe[Y], fe[X]);
    
    fe = abs(e1);
    AXISTEST_X01(e1[Z], e1[Y], fe[Z], fe[Y]);
    AXISTEST_Y02(e1[Z], e1[X], fe[Z], fe[X]);
    AXISTEST_Z0 (e1[Y], e1[X], fe[Y], fe[X]);

    fe = abs(e2);
    AXISTEST_X2 (e2[Z], e2[Y], fe[Z], fe[Y]);
    AXISTEST_Y1 (e2[Z], e2[X], fe[Z], fe[X]);
    AXISTEST_Z12(e2[Y], e2[X], fe[Y], fe[X]);

    // Bullet 1: 
    //  first test overlap in the {x,y,z}-directions 
    //  find min, max of the triangle each direction, and test for overlap in 
    //  that direction -- this is equivalent to testing a minimal AABB around
    //  the triangle against the AABB 

    // test in X-direction 
    FINDMINMAX(v0[X],v1[X],v2[X],min,max);
    if (min > boxhalfsize[X] || max < -boxhalfsize[X]) {
        return false;
    }

    // test in Y-direction
    FINDMINMAX(v0[Y],v1[Y],v2[Y],min,max);
    if (min > boxhalfsize[Y] || max < -boxhalfsize[Y]) {
        return false;
    }

    // test in Z-direction 
    FINDMINMAX(v0[Z],v1[Z],v2[Z],min,max);
    if (min > boxhalfsize[Z] || max < -boxhalfsize[Z]) {
        return false;
    }

    // Bullet 2: 
    //  test if the box intersects the plane of the triangle 
    //  compute plane equation of triangle: normal*x+d=0 

    if (! planeBoxOverlap(tri.normal(), v0, boxhalfsize)) {
        return false;
    }

    // box and triangle overlap
    return true;
}

Here is the call graph for this function:

bool G3D::CollisionDetection::fixedSolidSphereIntersectsFixedSolidBox ( const Sphere &  sphere, const Box &  box  )

static

Tests for the intersection of a fixed sphere and a fixed box.

Parameters

sphere	Fixed sphere.
box	Fixed box.

Returns

true - if the two objects touch.

false - if there is no intersection.

                                 {

    // If the center of the sphere is within the box, the whole
    // sphere is within the box.
    if (box.contains(sphere.center)) {
        return true;
    }

    float r2 = square(sphere.radius);

    // Find the closest point on the surface of the box to the sphere.  If
    // this point is within the sphere's radius, they intersect.
    int f;
    for (f = 0; f < 6; ++f) {
        Vector3 v0, v1, v2, v3;
        box.getFaceCorners(f, v0, v1, v2, v3);
        if ((closestPointToRectangle(v0, v1, v2, v3, sphere.center) - sphere.center).squaredMagnitude() <= r2) {
            return true;
        }
    }

    return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool G3D::CollisionDetection::fixedSolidSphereIntersectsFixedSolidSphere ( const Sphere &  sphere1, const Sphere &  sphere2  )

static

Tests for the intersection of two fixed spheres.

Parameters

sphere1	Fixed sphere 1.
sphere2	Fixed sphere 2.

Returns

true - if the two spheres touch.

false - if there is no intersection.

                                     {
    
    return (sphere1.center - sphere2.center).squaredMagnitude() < square(sphere1.radius + sphere2.radius);
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool G3D::CollisionDetection::fixedSolidSphereIntersectsFixedTriangle ( const Sphere &  sphere, const Triangle &  triangle  )

static

                                      {

    // How far is the sphere from the plane of the triangle
    const Plane& plane = triangle.plane();

    // Does the closest point to the sphere center lie within the triangle?
    Vector3 v = plane.closestPoint(sphere.center);

    // Is the closest point to the plane within the sphere?
    if ((v - sphere.center).squaredLength() <= square(sphere.radius)) {
        // Is it also within the triangle?
        float b[3];
        if (isPointInsideTriangle(triangle.vertex(0), triangle.vertex(1), triangle.vertex(2), triangle.normal(), 
                v, b, triangle.primaryAxis())){
            // The closest point is inside the triangle
            return true;
        }
    }

    // ignored
    int edgeIndex;

    v = closestPointOnTrianglePerimeter(triangle._vertex, triangle.edgeDirection, triangle.edgeMagnitude, sphere.center, edgeIndex);

    // Is the closest point within the sphere?
    return ((v - sphere.center).squaredLength() <= square(sphere.radius));
}

Here is the call graph for this function:

bool G3D::CollisionDetection::isPointInsideRectangle ( const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, const Vector3 &  v3, const Vector3 &  normal, const Vector3 &  point  )

static

Tests whether a point is inside a rectangle defined by the vertexes v0, v1, v2, & v3, and the rectangle's plane normal.

Parameters

v0	Rectangle vertex 1.
v1	Rectangle vertex 2.
v2	Rectangle vertex 3.
v3	Rectangle vertex 4.
normal	Normal to rectangle's plane.
point	The point in question.

Returns

true - if point is inside the rectangle.

false - otherwise

                          {

    return isPointInsideTriangle(v0, v1, v2, normal, point) ||
           isPointInsideTriangle(v2, v3, v0, normal, point);  
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool G3D::CollisionDetection::isPointInsideTriangle ( const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, const Vector3 &  normal, const Vector3 &  point, float  b[3], Vector3::Axis  primaryAxis = Vector3::DETECT_AXIS  )

static

Tests whether a point is contained within the triangle defined by v0, v1, and v2 and its plane's normal.

Parameters

v0	Triangle vertex 0.
v1	Triangle vertex 1.
v2	Triangle vertex 2.
normal	Normal to triangle's plane.
point	The point in question.
primaryAxis	Primary axis of triangle. This will be detected if not given. This parameter is provided as an optimization.
b	Barycentric coordinates; b[i] is the weight on v[i]

Returns

true - if point is inside the triangle.

false - otherwise

                                       {
    
    if (primaryAxis == Vector3::DETECT_AXIS) {
        primaryAxis = normal.primaryAxis();
    }

    // Check that the point is within the triangle using a Barycentric
    // coordinate test on a two dimensional plane.
    int i, j;

    switch (primaryAxis) {
    case Vector3::X_AXIS:
        i = Vector3::Y_AXIS;
        j = Vector3::Z_AXIS;
        break;

    case Vector3::Y_AXIS:
        i = Vector3::Z_AXIS;
        j = Vector3::X_AXIS;
        break;

    case Vector3::Z_AXIS:
        i = Vector3::X_AXIS;
        j = Vector3::Y_AXIS;
        break;

    default:
        // This case is here to supress a warning on Linux
        i = j = 0;
        debugAssertM(false, "Should not get here.");
        break;
    }

    // See if all barycentric coordinates are non-negative

    // 2D area via cross product
#   define AREA2(d, e, f)  (((e)[i] - (d)[i]) * ((f)[j] - (d)[j]) - ((f)[i] - (d)[i]) * ((e)[j] - (d)[j]))

    // Area of the polygon
    float area = AREA2(v0, v1, v2);
    if (area == 0) {
        // This triangle has zero area, so the point must not
        // be in it unless the triangle point is the test point.
        return (v0 == point);
    }

    debugAssert(area != 0);

    float invArea = 1.0f / area;

    // (avoid normalization until absolutely necessary)
    b[0] = AREA2(point, v1, v2) * invArea;

    if ((b[0] < 0.0f) || (b[0] > 1.0f)) {
        return false;
    }

    b[1] = AREA2(v0,  point, v2) * invArea;
    if ((b[1] < 0.0f) || (b[1] > 1.0f)) {
        return false;
    }

    b[2] = 1.0f - b[0] - b[1];

#   undef AREA2

    return (b[2] >= 0.0f) && (b[2] <= 1.0f);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static bool G3D::CollisionDetection::isPointInsideTriangle ( const Vector3 &  v0, const Vector3 &  v1, const Vector3 &  v2, const Vector3 &  normal, const Vector3 &  point, Vector3::Axis  primaryAxis = Vector3::DETECT_AXIS  )

inlinestatic

                                                                {

        float b[3];
        return isPointInsideTriangle(v0, v1, v2, normal, point, b, primaryAxis);
    }

Here is the call graph for this function:

bool G3D::CollisionDetection::movingSpherePassesThroughFixedBox ( const Sphere &  sphere, const Vector3 &  velocity, const Box &  box, double  timeLimit = inf()  )

static

Tests for the intersection of a moving sphere and a fixed box in a given time limit.

Note

Returns true if any part of the sphere is inside the box during the time period (inf means "ever"). Useful for performing bounding-box collision detection.

Parameters

sphere	Moving sphere.
velocity	Velocity of moving sphere.
box	Fixed box.
timeLimit	Time limit for intersection test.

Returns

true - if the two objects will touch.

false - if there is no intersection.

                                       {

    // If they intersect originally, they definitely pass through each other.
    if (fixedSolidSphereIntersectsFixedSolidBox(sphere, box)) {
        return true;
    }

    // See if the sphere hits the box during the time period.
    Vector3 dummy1, dummy2;

    return (collisionTimeForMovingSphereFixedBox(sphere, velocity, box, dummy1, dummy2) < timeLimit);
}

Here is the call graph for this function:

bool G3D::CollisionDetection::movingSpherePassesThroughFixedSphere ( const Sphere &  sphere, const Vector3 &  velocity, const Sphere &  fixedSphere, double  timeLimit = inf()  )

static

Tests for the intersection of a moving sphere and a fixed sphere in a given time limit.

Note

This function will not detect an intersection between a moving object that is already interpenetrating the fixed object.

Parameters

sphere	Moving sphere.
velocity	Velocity of moving sphere.
fixedSphere	Fixed sphere.
timeLimit	Time limit for intersection test.

Returns

true - if the two spheres will touch.

false - if there is no intersection.

                                       {

    if (fixedSolidSphereIntersectsFixedSolidSphere(sphere, fixedSphere)) {
        return true;
    }

    // Extend the fixed sphere by the radius of the moving sphere
    Sphere bigFixed(fixedSphere.center, fixedSphere.radius + sphere.radius);
    Vector3 dummy1, dummy2;

    // If the sphere collides with the other sphere during the time limit, it passes through
    return (collisionTimeForMovingPointFixedSphere(sphere.center, velocity, bigFixed, dummy1, dummy2) < timeLimit);
}

Here is the call graph for this function:

bool G3D::CollisionDetection::parallelAxisForSolidBoxSolidBox ( const double *  ca, const double  epsilon, int &  axis1, int &  axis2  )

static

Tests whether two boxes have axes that are parallel to each other. If they are, axis1 and axis2 are set to be the parallel axes for both box1 and box2 respectively.

Parameters

ca	Dot products of each of the boxes axes
epsilon	Fudge factor (small unit by which the dot products may vary and still be considered zero).
axis1	Parallel Axis 1. [Post Condition]
axis2	Parallel Axis 2. [Post Condition]

Returns

true - If boxes have a parallel axis

false - otherwise.

                     {
    const double parallelDot = 1.0 - epsilon;
    for (int i = 0; i < 9; ++i) {
        if (ca[i] >= parallelDot) {
            axis1 = i / 3;
            axis2 = i % 3;
            return true;
        }
    }
    return false;
}

Here is the caller graph for this function:

float G3D::CollisionDetection::penetrationDepthForFixedBoxFixedBox ( const Box &  box1, const Box &  box2, Array< Vector3 > &  contactPoints, Array< Vector3 > &  contactNormals, const int  lastSeparatingAxis = -1  )

static

Calculates the depth of penetration between two fixed boxes. Contact normal faces away from box1 and into box2. If there is contact, only one contact point is returned. The minimally violated separating plane is computed

• if the separating axis corresponds to a face the contact point is half way between the deepest vertex and the face
• if the separating axis corresponds to two edges the contact point is the midpoint of the smallest line segment between the two edge lines

Note

This is very similiar to calculating the intersection of two lines. Logically then, the two points calculated would be identical if calculated with inifinite precision, but with the finite precision of floating point calculations, these values could (will) differ as the line slope approaches zero or inifinity.

[adobted] from David Eberly's papers, variables used in this function correspond to variables used in pages 6 and 7 in the pdf http://www.magic-software.com/Intersection.html http://www.magic-software.com/Documentation/DynamicCollisionDetection.pdf

Parameters

box1	Box 1
box2	Box 2
contactPoints	Contact point between boxes. [Post Condition]
contactNormals	Surface normal at contact point. [Post Condition]
lastSeparatingAxis	Last separating axis. (Used for optimization)

Returns

Depth of penetration between the two boxes. If there is no intersection between the boxes, then a negative value is returned.

                                  {

    contactPoints.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);
    contactNormals.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);

    Vector3 a;
    Vector3 b;
    Vector3 D;
    double c[9];
    double ca[9];
    double ad[3];
    double bd[3];

    debugAssert(lastSeparatingAxis >= -1);
    debugAssert(lastSeparatingAxis < 15);

    fillSolidBoxSolidBoxInfo(box1, box2, a, b, D, c, ca, ad, bd);

    int axis1, axis2;
    bool parallelAxes = parallelAxisForSolidBoxSolidBox(ca, 0.00001,
            axis1, axis2);


    // check the separating axis from the last time step
    if (lastSeparatingAxis != -1 &&
            (lastSeparatingAxis < 6 || !parallelAxes)) {
        float projectedDistance = projectedDistanceForSolidBoxSolidBox(
                lastSeparatingAxis, a, b, D, c, ca, ad, bd);

        // the separating axis from the last time step is still
        // valid, the boxes do not intersect
        if (projectedDistance > 0.0) {
            return -projectedDistance;
        }
    }

    // test if the boxes can be separated by a plane normal to
    // any of the three axes of box1, any of the three axes of box2,
    // (test 9 possible cross products later)
    float penetration = -finf();
    int penetrationAxisIndex = -1;

    for (int i = 0; i < 6; ++i) {
        float projectedDistance =
            projectedDistanceForSolidBoxSolidBox(i, a, b, D, c, ca, ad, bd);

        // found a separating axis, the boxes do not intersect
        if (projectedDistance > 0.0) {
            return -projectedDistance;
        }

        // keep track of the axis that is least violated
        if (projectedDistance > penetration) {
            penetration = projectedDistance;
            penetrationAxisIndex = i;
        }
    }


    // for each edge-edge case we have to adjust the magnitude of
    // penetration since we did not include the dot(L, L) denominator
    // that can be smaller than 1.0 for the edge-edge cases.

    if (!parallelAxes) {
        double edgeDistances[9];

        // run through edge-edge cases to see if we can find a separating axis
        for (int i = 6; i < 15; ++i) {
            float projectedDistance =
                projectedDistanceForSolidBoxSolidBox(i, a, b, D, c, ca, ad, bd);

            // found a separating axis, the boxes do not intersect,
            // correct magnitude and return projected distance
            if (projectedDistance > 0.0) {
                Vector3 L = separatingAxisForSolidBoxSolidBox(i, box1, box2);
                projectedDistance /= dot(L, L);
                return -projectedDistance;
            }

            edgeDistances[i - 6] = projectedDistance;
        }

        // no separating axis found, the boxes do intersect,
        // correct the magnitudes of the projectedDistance values
        for (int i = 6; i < 15; ++i) {
            // find the negative penetration value with the smallest magnitude,
            // the adjustment done for the edge-edge cases only increases
            // magnitude by dividing by a number smaller than 1 and greater than 0
            float projectedDistance = (float)edgeDistances[i - 6];
            if (projectedDistance > penetration) {
                Vector3 L = separatingAxisForSolidBoxSolidBox(i, box1, box2);
                projectedDistance /= dot(L, L);
                if (projectedDistance > penetration) {
                    penetration = projectedDistance;
                    penetrationAxisIndex = i;
                }
            }
        }
    }

    // get final separating axis vector
    Vector3 L = separatingAxisForSolidBoxSolidBox(penetrationAxisIndex,
            box1, box2);

    // set L to be the normal that faces away from box1
    if (dot(L, D) < 0) {
        L = -L;
    }

    Vector3 contactPoint;

    if (penetrationAxisIndex < 6) {
        // vertex to face collision, find deepest colliding vertex
        const Box* vertexBox;
        Vector3 faceNormal = L;

        // L will be the outward facing normal for the faceBox
        if (penetrationAxisIndex < 3) {
            vertexBox = & box2;
            if (dot(L, D) < 0) {
                faceNormal = -L;
            }
        } else {
            vertexBox = & box1;
            if (dot(L, D) > 0) {
                faceNormal = -L;
            }
        }

        // find the vertex that is farthest away in the direction
        // face normal direction
        int deepestPointIndex = 0;
        float deepestPointDot = dot(faceNormal, vertexBox->corner(0));
        for (int i = 1; i < 8; ++i) {
            float dotProduct = dot(faceNormal, vertexBox->corner(i));
            if (dotProduct < deepestPointDot) {
                deepestPointDot = dotProduct;
                deepestPointIndex = i;
            }
        }
        
        // return the point half way between the deepest point and the
        // contacting face
        contactPoint = vertexBox->corner(deepestPointIndex) +
            (-penetration * 0.5 * faceNormal);
    } else {
        // edge-edge case, find the two ege lines
        int edge1 = (penetrationAxisIndex - 6) / 3;
        int edge2 = (penetrationAxisIndex - 6) % 3;
        Vector3 linePoint1 = box1.center();
        Vector3 linePoint2 = box2.center();
        Vector3 lineDir1;
        Vector3 lineDir2;

        // find edge line by finding the edge axis, and the
        // other two axes that are closest to the other box
        for (int i = 0; i < 3; ++i) {
            if (i == edge1) {
                lineDir1 = box1.axis(i);
            } else {
                Vector3 axis = box1.axis(i);
                if (dot(axis, L) < 0) {
                    axis = -axis;
                }
                linePoint1 += axis * a[i];
            }

            if (i == edge2) {
                lineDir2 = box2.axis(i);
            } else {
                Vector3 axis = box2.axis(i);
                if (dot(axis, L) > 0) {
                    axis = -axis;
                }
                linePoint2 += axis * b[i];
            }
        }

        // make lines from the two closest edges, and find
        // the points that on each line that are closest to the other
        Line line1 = Line::fromPointAndDirection(linePoint1, lineDir1);
        Line line2 = Line::fromPointAndDirection(linePoint2, lineDir2);
        Vector3 closest1;
        Vector3 closest2;

        closestPointsBetweenLineAndLine(line1, line2, closest1, closest2);
        
        // take the average of the two closest edge points for the final
        // contact point
        contactPoint = (closest1 + closest2) * 0.5;
    }

    contactPoints.push(contactPoint);
    contactNormals.push(L);

    return -penetration;

}

Here is the call graph for this function:

float G3D::CollisionDetection::penetrationDepthForFixedBoxFixedPlane ( const Box &  box, const Plane &  plane, Array< Vector3 > &  contactPoints, Array< Vector3 > &  contactNormals = ignoreArray  )

static

Calculates the depth of penetration between a fixed box and a fixed plane as well as the vertexes of the box that penetrate the plane and the plane normals at those intersections.

Parameters

box	Fixed Box.
plane	Fixed Plane.
contactPoints	Box points that penetrate the plane. [Post Condition]
contactNormals	Normals at penetration points [Post Condition]

Returns

Depth of penetration. If there is no intersection between the objects then the depth will be a negative value.

                                        {

    Vector3 N;
    double d;
    
    plane.getEquation(N, d);

    contactPoints.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);
    contactNormals.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);

    float lowest = finf();
    for (int i = 0; i < 8; ++i) {
        const Vector3 vertex = box.corner(i);
        
        float x = vertex.dot(N) + (float)d;
        
        if (x <= 0) {
            // All vertices below the plane should be contact points.
            contactPoints.append(vertex);
            contactNormals.append(-N);
        }

        lowest = min(lowest, x);
    }

    // Depth should be a positive number
    return -lowest;
}

Here is the call graph for this function:

float G3D::CollisionDetection::penetrationDepthForFixedSphereFixedBox ( const Sphere &  sphere, const Box &  box, Array< Vector3 > &  contactPoints, Array< Vector3 > &  contactNormals = ignoreArray  )

static

Calculates the depth of penetration between a fixed sphere and a fixed box as well as the deepest point of the sphere that penetrates the box and the normal at that intersection.

Note

There are three possible intersections between a sphere and box.

• Sphere completely contained in the box
• Sphere intersects one edge
• Sphere intersects one vertex

The contact point and contact normal vary for each of these situations.

• Sphere contained in Box:
  • Normal is based on side of least penetration (as is the depth calculation).
  • Point is based on center of sphere
• Sphere intersects one edge
  • Normal is based on vector from the box center to the point of depth.
  • Point is closest point to the sphere on the line
• Sphere intersects one vertex
  • Normal is based on vector from the box center to the vertex of penetration.
  • Point is vertex of penetration.

[Adapted] from Jim Arvo's method in Graphics Gems See also http://www.win.tue.nl/~gino/solid/gdc2001depth.pdf

Parameters

sphere	Fixed Sphere.
box	Fixed Box.
contactPoints	Sphere point that penetrates the box. [Post Condition]
contactNormals	Normal at the penetration point. [Post Condition]

Returns

Depth of penetration. If there is no intersection between the objects then the depth will be a negative value.

                                    {

    contactPoints.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);
    contactNormals.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);

    // In its local coordinate frame, the box measures
    // 2 * halfExtent[a] along dimesion a.
    Vector3 halfExtent(box.extent(0), box.extent(1), box.extent(2));
    halfExtent *= 0.5f;

    CoordinateFrame boxFrame;
    box.getLocalFrame(boxFrame);

    // Transform the sphere to the box's coordinate frame.
    Vector3 center = boxFrame.pointToObjectSpace(sphere.center);

    // Find the square of the distance from the sphere to the box


    // Distance along each axis from the closest side of the box
    // to the sphere center.  Negative values are *inside* the box.
    Vector3 distOutsideBox;

    // Divide space up into the 27 regions corresponding
    // to {+|-|0}X, {+|-|0}Y, {+|-|0}Z and classify the
    // sphere center into one of them.
    Vector3 centerRegion;

    // In the edge collision case, the edge is between vertices
    // (constant + variable) and (constant - variable).
    Vector3 constant, variable;

    int numNonZero = 0;

    // Iterate over axes
    for (int a = 0; a < 3; ++a) { 
        // For each (box side), see which direction the sphere
        // is outside the box (positive or negative).  Add the
        // square of that distance to the total distance from 
        // the box.

        float distanceFromLow  = -halfExtent[a] - center[a];
        float distanceFromHigh = center[a] - halfExtent[a];

        if (fabsf(distanceFromLow) < fabsf(distanceFromHigh)) {
            distOutsideBox[a] = distanceFromLow;
        } else {
            distOutsideBox[a] = distanceFromHigh;
        }

        if (distanceFromLow < 0.0) {
            if (distanceFromHigh < 0.0) {
                // Inside the box
                centerRegion[a] = 0.0;
                variable[a]     = 1.0;
            } else {
                // Off the high side
                centerRegion[a] = 1.0;
                constant[a]     = halfExtent[a];
                ++numNonZero;
            }
        } else if (distanceFromHigh < 0.0) {
            // Off the low side
            centerRegion[a] = -1.0;
            constant[a]     = -halfExtent[a];
            ++numNonZero;
        } else {
            debugAssertM(false, 
                "distanceFromLow and distanceFromHigh cannot both be positive");
        }
    }

    // Squared distance between the outside of the box and the
    // sphere center.
    float d2 = Vector3::zero().max(distOutsideBox).squaredMagnitude();

    if (d2 > square(sphere.radius)) {
        // There is no penetration because the distance is greater
        // than the radius of the sphere.  This is the common case
        // and we quickly exit.
        return -1;
    }

    // We know there is some penetration but need to classify it.
    //
    // Examine the region that contains the center of the sphere. If
    // there is exactly one non-zero axis, the collision is with a 
    // plane.  If there are exactly two non-zero axes, the collision
    // is with an edge.  If all three axes are non-zero, the collision is
    // with a vertex.  If there are no non-zero axes, the center is inside
    // the box.

    double depth = -1;
    switch (numNonZero) {
    case 3: // Vertex collision
        // The collision point is the vertex at constant, the normal
        // is the vector from there to the sphere center.
        contactNormals.append(boxFrame.normalToWorldSpace(constant - center));
        contactPoints.append(boxFrame.pointToWorldSpace(constant));
        depth = sphere.radius - sqrt(d2);
        break;

    case 2: // Edge collision
        {
            // TODO: unwrapping the edge constructor and closest point
            // code will probably make it faster.

            // Determine the edge
            Line line = Line::fromPointAndDirection(constant, variable);

            // Penetration depth:
            depth = sphere.radius - sqrt(d2);

            // The contact point is the closes point to the sphere on the line 
            Vector3 X = line.closestPoint(center);
            contactNormals.append(boxFrame.normalToWorldSpace(X - center).direction());
            contactPoints.append(boxFrame.pointToWorldSpace(X));
        }
        break;

    case 1: // Plane collision
        {
            // The plane normal is the centerRegion vector,
            // so the sphere normal is the negative.  Take
            // it to world space from box-space.

            // Center region doesn't need to be normalized because
            // it is known to contain only one non-zero value
            // and that value is +/- 1.
            Vector3 N = boxFrame.normalToWorldSpace(-centerRegion);
            contactNormals.append(N);

            // Penetration depth:
            depth = sphere.radius - sqrtf(d2);

            // Compute the contact point from the penetration depth
            contactPoints.append(sphere.center + N * (sphere.radius - depth));
        }
        break;

    case 0: // Volume collision

        // The sphere center is inside the box.  This is an easy case
        // to handle.  Note that all axes of distOutsideBox must
        // be negative.  
    
        // Arbitratily choose the sphere center as a contact point
        contactPoints.append(sphere.center);

        // Find the least-negative penetration axis.
        //
        // We could have computed this during the loop over the axes,
        // but since volume collisions are rare (they only occur with
        // large time steps), this case will seldom be executed and
        // should not be optimized at the expense of the others.
        if (distOutsideBox.x > distOutsideBox.y) {
            if (distOutsideBox.x > distOutsideBox.z) {
                // Smallest penetration on x-axis
                // Chose normal based on which side we're closest to.
                // Keep in mind that this is a normal to the sphere,
                // so it is the inverse of the box normal.
                if (center.x > 0) {
                    contactNormals.append(boxFrame.normalToWorldSpace(-Vector3::unitX()));
                } else {
                    contactNormals.append(boxFrame.normalToWorldSpace(Vector3::unitX()));
                }
                depth = -distOutsideBox.x;
            } else {
                // Smallest penetration on z-axis
                goto ZAXIS;
            }
        } else if (distOutsideBox.y > distOutsideBox.z) {
            // Smallest penetration on y-axis
            // Chose normal based on which side we're closest to.
            // Keep in mind that this is a normal to the sphere,
            // so it is the inverse of the box normal.
            if (center.y > 0) {
                contactNormals.append(boxFrame.normalToWorldSpace(-Vector3::unitY()));
            } else {
                contactNormals.append(boxFrame.normalToWorldSpace(Vector3::unitY()));
            }
            depth = -distOutsideBox.y;
        } else {
            // Smallest on z-axis
ZAXIS:
            // Chose normal based on which side we're closest to.
            // Keep in mind that this is a normal to the sphere,
            // so it is the inverse of the box normal.
            if (center.z > 0) {
                contactNormals.append(boxFrame.normalToWorldSpace(-Vector3::unitZ()));
            } else {
                contactNormals.append(boxFrame.normalToWorldSpace(Vector3::unitZ()));
            }
            depth = -distOutsideBox.z;
        }
        break;

    default:
        debugAssertM(false, "Fell through switch");
        break;
    }

    return depth;
}

Here is the call graph for this function:

float G3D::CollisionDetection::penetrationDepthForFixedSphereFixedPlane ( const Sphere &  sphereA, const class Plane &  planeB, Array< Vector3 > &  contactPoints, Array< Vector3 > &  contactNormals = ignoreArray  )

static

Calculates the depth of penetration between a Fixed Sphere and a Fixed Plane as well as the deepest point of the sphere that penetrates the plane and the plane normal at that intersection.

Parameters

sphereA	Fixed Sphere.
planeB	Fixed Plane.
contactPoints	Sphere point that penetrates the plane. [Post Condition]
contactNormals	Normal at penetration point. [Post Condition]

Returns

Depth of penetration. If there is no intersection between the objects then the depth will be a negative value.

                                            {

    Vector3 N;
    double d;

    planeB.getEquation(N, d);
    
    double depth = -(sphereA.center.dot(N) + d - sphereA.radius);

    contactPoints.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);
    contactNormals.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);

    if (depth >= 0) {
        contactPoints.append(N * (depth - sphereA.radius) + sphereA.center);
        contactNormals.append(N);
    }

    return depth;
}

Here is the call graph for this function:

float G3D::CollisionDetection::penetrationDepthForFixedSphereFixedSphere ( const class Sphere &  sphereA, const Sphere &  sphereB, Array< Vector3 > &  contactPoints, Array< Vector3 > &  contactNormals = ignoreArray  )

static

Calculates the depth of penetration between two fixed spheres as well as the deepest point of Sphere A that penetrates Sphere B. The normal returned points away from the object A, although it may represent a perpendicular to either the faces of object B or object A depending on their relative orientations.

Parameters

sphereA	Fixed Sphere A.
sphereB	Fixed Sphere B.
contactPoints	Sphere A's deepest point that penetrates Sphere B. [Post Condition]
contactNormals	Normal at penetration point. [Post Condition]

Returns

Depth of penetration. If there is no intersection between the objects then the depth will be a negative value.

                                            {

    Vector3 axis = sphereB.center - sphereA.center;
    double radius = sphereA.radius + sphereB.radius;
    double mag = axis.magnitude();
    axis /= mag;
    double depth = -(mag - radius);

    contactPoints.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);
    contactNormals.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);

    if (depth >= 0) {
        contactPoints.append(sphereA.center + axis * (sphereA.radius - depth / 2));
        contactNormals.append(axis);
    }

    return depth;
}

Here is the call graph for this function:

float G3D::CollisionDetection::projectedDistanceForSolidBoxSolidBox ( const int  separatingAxisIndex, const Vector3 &  a, const Vector3 &  b, const Vector3 &  D, const double *  c, const double *  ca, const double *  ad, const double *  bd  )

static

Calculates the projected distance between the two boxes along the specified separating axis, negative distances correspond to an overlap along that separating axis. The distance is not divided by denominator dot(L, L), see penetrationDepthForFixedSphereFixedBox() for more details

Parameters

separatingAxisIndex
a	Box 1's bounding sphere vector
b	Box 2's bounding sphere vector
D	Vector between Box 1 and Box 2's center points
c	Pointer to array of dot products of the axes of Box 1 and Box 2.
ca	Pointer to array of unsigned dot products of the axes of Box 1 and Box 2.
ad	Pointer to array of dot products of Box 1 axes and D.
bd	Pointer to array of dot products of Box 2 axes and D.

Returns

Projected distance between the two boxes along the specified separating axis.

{
    (void)D;

    float R0 = 0.0f;
    float R1 = 0.0f;
    float R = 0.0f;
    switch (separatingAxisIndex) {
    case 0:
        // A0
        R0 = a[0];
        R1 = b[0] * ca[0] + b[1] * ca[1] + b[2] * ca[2];
        R = fabs(ad[0]);
        break;
    case 1:
        // A1
        R0 = a[1];
        R1 = b[0] * ca[3] + b[1] * ca[4] + b[2] * ca[5];
        R = fabs(ad[1]);
        break;
    case 2:
        // A2
        R0 = a[2];
        R1 = b[0] * ca[6] + b[1] * ca[7] + b[2] * ca[8];
        R = fabs(ad[2]);
        break;
    case 3:
        // B0
        R0 = a[0] * ca[0] + a[1] * ca[3] + a[2] * ca[6];
        R1 = b[0];
        R = fabs(bd[0]);
        break;
    case 4:
        // B1
        R0 = a[0] * ca[1] + a[1] * ca[4] + a[2] * ca[7];
        R1 = b[1];
        R = fabs(bd[1]);
        break;
    case 5:
        // B2
        R0 = a[0] * ca[2] + a[1] * ca[5] + a[2] * ca[8];
        R1 = b[2];
        R = fabs(bd[2]);
        break;
    case 6:
        // A0 x B0
        R0 = a[1] * ca[6] + a[2] * ca[3];
        R1 = b[1] * ca[2] + b[2] * ca[1];
        R = fabs(c[3] * ad[2] - c[6] * ad[1]);
        break;
    case 7:
        // A0 x B1
        R0 = a[1] * ca[7] + a[2] * ca[4];
        R1 = b[0] * ca[2] + b[2] * ca[0];
        R = fabs(c[4] * ad[2] - c[7] * ad[1]);
        break;
    case 8:
        // A0 x B2
        R0 = a[1] * ca[8] + a[2] * ca[5];
        R1 = b[0] * ca[1] + b[1] * ca[0];
        R = fabs(c[5] * ad[2] - c[8] * ad[1]);
        break;
    case 9:
        // A1 x B0
        R0 = a[0] * ca[6] + a[2] * ca[0];
        R1 = b[1] * ca[5] + b[2] * ca[4];
        R = fabs(c[6] * ad[0] - c[0] * ad[2]);
        break;
    case 10:
        // A1 x B1
        R0 = a[0] * ca[7] + a[2] * ca[1];
        R1 = b[0] * ca[5] + b[2] * ca[3];
        R = fabs(c[7] * ad[0] - c[1] * ad[2]);
        break;
    case 11:
        // A1 x B2
        R0 = a[0] * ca[8] + a[2] * ca[2];
        R1 = b[0] * ca[4] + b[1] * ca[3];
        R = fabs(c[8] * ad[0] - c[2] * ad[2]);
        break;
    case 12:
        // A2 x B0
        R0 = a[0] * ca[3] + a[1] * ca[0];
        R1 = b[1] * ca[8] + b[2] * ca[7];
        R = fabs(c[0] * ad[1] - c[3] * ad[0]);
        break;
    case 13:
        // A2 x B1
        R0 = a[0] * ca[4] + a[1] * ca[1];
        R1 = b[0] * ca[8] + b[2] * ca[6];
        R = fabs(c[1] * ad[1] - c[4] * ad[0]);
        break;
    case 14:
        // A2 x B2
        R0 = a[0] * ca[5] + a[1] * ca[2];
        R1 = b[0] * ca[7] + b[1] * ca[6];
        R = fabs(c[2] * ad[1] - c[5] * ad[0]);
        break;
    default:
        debugAssertM(false, "fell through switch statement");
    }

    return (R - (R0 + R1));
}

Here is the caller graph for this function:

bool __fastcall G3D::CollisionDetection::rayAABox ( const Ray &  ray, const Vector3 &  invDir, const AABox &  box, const Vector3 &  boxCenter, float  boundingRadiusSquared, Vector3 &  location, bool &  inside  )

static

Calculates intersection of a ray and a static Axis-Aligned Box (AABox).

Note

Avoids the sqrt from collisionTimeForMovingPointFixedAABox; early-out branches and operations optimized for Intel Core2 architecture.

Parameters

invDir	1/dir
location	Location of collision. [Post Condition]
inside	Does the ray originate inside the box? [Post Condition]

Returns

True if the ray hits the box

                                    {

    debugAssertM(fabs(ray.direction().squaredLength() - 1.0f) < 0.01f, format("Length = %f", ray.direction().length()));
    {
        // Pre-emptive partial bounding sphere test
        const Vector3 L(boxCenter - ray.origin());
        float d = L.dot(ray.direction());

        float L2 = L.dot(L);
        float D2 = square(d);
        float M2 = L2 - D2;

        if (((d < 0) && (L2 > boundingRadiusSquared)) || (M2 > boundingRadiusSquared)) {
            inside = false;
            return false;
        }
        // Passing here does not mean that the ray hits the bounding sphere;
        // we would still have to perform more expensive tests to determine
        // that.
    }

    inside = true;
    const Vector3& MinB = box.low();
    const Vector3& MaxB = box.high();
    Vector3 MaxT(-1.0f, -1.0f, -1.0f);

    // Find candidate planes.
    for (int i = 0; i < 3; ++i) {
        if (ray.origin()[i] < MinB[i]) {
            location[i]    = MinB[i];
            inside      = false;
            
            // Calculate T distances to candidate planes
            if (ray.direction()[i] != 0) {
                MaxT[i] = (MinB[i] - ray.origin()[i]) * invDir[i];
            }
        } else if (ray.origin()[i] > MaxB[i]) {
            location[i]    = MaxB[i];
            inside      = false;

            // Calculate T distances to candidate planes
            if (ray.direction()[i] != 0) {
                MaxT[i] = (MaxB[i] - ray.origin()[i]) * invDir[i];
            }
        }
    }

    if (inside) {
        // Ray origin inside bounding box
        location = ray.origin();
        return true;
    }
    
    // Get largest of the maxT's for final choice of intersection
    int WhichPlane = 0;
    if (MaxT[1] > MaxT[WhichPlane]) {
        WhichPlane = 1;
    }

    if (MaxT[2] > MaxT[WhichPlane]) {
        WhichPlane = 2;
    }

    // Check final candidate actually inside box
    if (MaxT[WhichPlane] < 0.0f) {
        // Miss the box
        return false;
    }

    for (int i = 0; i < 3; ++i) {
        if (i != WhichPlane) {
            location[i] = ray.origin()[i] + MaxT[WhichPlane] * ray.direction()[i];
            if ((location[i] < MinB[i]) ||
                (location[i] > MaxB[i])) {
                // On this plane we're outside the box extents, so
                // we miss the box
                return false;
            }
        }
    }
    
    return true;
}

Here is the call graph for this function:

Vector3 G3D::CollisionDetection::separatingAxisForSolidBoxSolidBox ( const int  separatingAxisIndex, const Box &  box1, const Box &  box2  )

static

Converts an index [0, 15] to the corresponding separating axis. Does not return normalized vector in the edge-edge case (indices 6 through 15).

Parameters

separatingAxisIndex	Separating axis.
box1	Box 1.
box2	Box 2.

Returns

Axis that separates the two boxes.

                          {
    debugAssert(separatingAxisIndex >= 0);
    debugAssert(separatingAxisIndex < 15);
    Vector3 axis;
    if (separatingAxisIndex < 3) {
        axis = box1.axis(separatingAxisIndex);
    } else if (separatingAxisIndex < 6) {
        axis = box2.axis(separatingAxisIndex - 3);
    } else {
        int box1Index = (separatingAxisIndex - 6) / 3;
        int box2Index = (separatingAxisIndex - 6) % 3;
        axis = cross(box1.axis(box1Index), box2.axis(box2Index));
    }
    return axis;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Vector3 G3D::CollisionDetection::slideDirection ( const class Sphere &  sphere, const Vector3 &  velocity, const float  collisionTime, const Vector3 &  collisionLocation  )

static

Finds the direction of slide given a moving sphere, its velocity, the time of collision and the collision location. This function works as if the sphere intersects the surface and continues to hug it.

Note

The result will work well for calculating the movement of a player who collides with an object and continues moving along the object instead of just bouncing off it.

Parameters

sphere	Moving sphere.
velocity	Sphere's velocity.
collisionTime	Time of collision
collisionLocation	Collision location.

Returns

Direction of slide.

                                       {

    Vector3 sphereLocation  = sphere.center + velocity * collisionTime;
    Vector3 normal          = (sphereLocation - collisionLocation).direction();
    Vector3 direction       = velocity.direction();

    // subtract off the part in the direction away from the normal.
    return direction - normal * normal.dot(direction);
}

Here is the call graph for this function:

Member Data Documentation

Vector3 G3D::CollisionDetection::ignore

staticprivate

Default parameter if value passed to a function as reference is not to be calculated. Must be explicitly supported by function.

Array< Vector3 > G3D::CollisionDetection::ignoreArray

staticprivate

Default parameter if value passed to a function as reference is not to be calculated. Must be explicitly supported by function.

bool G3D::CollisionDetection::ignoreBool

staticprivate

Default parameter if value passed to a function as reference is not to be calculated. Must be explicitly supported by function.

---

The documentation for this class was generated from the following files:

• dep/g3dlite/include/G3D/CollisionDetection.h
• dep/g3dlite/source/CollisionDetection.cpp