diff options
Diffstat (limited to 'dep/include/g3dlite/G3D/CollisionDetection.h')
| -rw-r--r-- | dep/include/g3dlite/G3D/CollisionDetection.h | 1157 |
1 files changed, 1157 insertions, 0 deletions
diff --git a/dep/include/g3dlite/G3D/CollisionDetection.h b/dep/include/g3dlite/G3D/CollisionDetection.h new file mode 100644 index 00000000000..4dc8b26538d --- /dev/null +++ b/dep/include/g3dlite/G3D/CollisionDetection.h @@ -0,0 +1,1157 @@ +/** + @file CollisionDetection.h + + + Moving collision detection for simple primitives. + + @author Morgan McGuire, matrix@graphics3d.com + @cite Spherical collision based on Paul Nettle's + ftp://ftp.3dmaileffects.com/pub/FluidStudios/CollisionDetection/Fluid_Studios_Generic_Collision_Detection_for_Games_Using_Ellipsoids.pdf + and comments by Max McGuire. Ray-sphere intersection by Eric Haines. + Box-Box intersection written by Kevin Egan. + Thanks to Max McGuire of Iron Lore for various bug fixes. + + @created 2001-11-19 + @edited 2006-01-10 + + Copyright 2000-2006, Morgan McGuire. + All rights reserved. + */ + +#ifndef G3D_COLLISIONDETECTION_H +#define G3D_COLLISIONDETECTION_H + +#include "G3D/platform.h" +#include "G3D/Vector3.h" +#include "G3D/Plane.h" +#include "G3D/Box.h" +#include "G3D/Triangle.h" +#include "G3D/Array.h" +#include "G3D/Ray.h" +#include "G3D/Line.h" + +namespace G3D { + + +/** + Collision detection primitives and tools for building + higher order collision detection schemes. + + These routines provide <I>moving</I> 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 + <I>only</I> 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 <I>leaving</I> 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 <B>not</B> 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. + + <p> + <b>Static Collision Detection:</b> (Neither object is moving) + + <table> + <tr><td></td><td><b>Vector3</b></td><td><b>LineSegment</b></td><td><b>Ray *</b></td><td><b>Line</b></td><td><b>Plane</b></td><td><b>Triangle</b></td><td><b>Sphere</b></td><td><b>Cylinder</b></td><td><b>Capsule</b></td><td><b>AABox</b></td><td><b>Box</b></td></tr> + <tr><td><b>Vector3</b></td><td>Vector3::operator== Vector3::fuzzyEq G3D::distance</td><td bgcolor=#C0C0C0 colspan=10 ></td></tr> + <tr><td><b>LineSegment</b></td><td>LineSegment::closestPoint LineSegment::distance CollisionDetection::closestPointOnLineSegment</td><td></td><td bgcolor=#C0C0C0 colspan=9 ></td></tr> + <tr><td><b>Ray *</b></td><td>Ray::closestPoint Ray::distance</td><td></td><td></td><td bgcolor=#C0C0C0 colspan=8 ></td></tr> + <tr><td><b>Line</b></td><td>Line::closestPoint Line::distance</td><td></td><td>CollisionDetection::closestPointsBetweenLineAndLine</td><td></td><td bgcolor=#C0C0C0 colspan=7 ></td></tr> + <tr><td><b>Plane</b></td><td></td><td></td><td></td><td></td><td></td><td bgcolor=#C0C0C0 colspan=6 ></td></tr> + <tr><td><b>Triangle</b></td><td></td><td></td><td></td><td></td><td></td><td></td><td bgcolor=#C0C0C0 colspan=5 ></td></tr> + <tr><td><b>Sphere</b></td><td>Sphere::contains</td><td></td><td></td><td></td><td></td><td></td><td></td><td bgcolor=#C0C0C0 colspan=4 ></td></tr> + <tr><td><b>Cylinder</b></td><td>Cylinder::contains</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td bgcolor=#C0C0C0 colspan=3 ></td></tr> + <tr><td><b>Capsule</b></td><td>Capsule::contains</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td bgcolor=#C0C0C0 colspan=2 ></td></tr> + <tr><td><b>AABox</b></td><td>AABox::contains</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td bgcolor=#C0C0C0 colspan=1 ></td></tr> + <tr><td><b>Box</b></td><td>Box::contains</td><td>(treat as Ray)</td><td>CollisionDetection::collisionTimeForMovingPointFixedBox</td><td>(treat as Ray)</td><td>CollisionDetection::penetrationDepthForFixedBoxFixedPlane</td><td>CollisionDetection::penetrationDepthForFixedBoxFixedPlane</td><td>CollisionDetection::penetrationDepthForFixedSphereFixedBox</td><td>None (use OPCODE)</td><td>CollisionDetection::movingSpherePassesThroughFixedBox</td><td>CollisionDetection::penetrationDepthForFixedBoxFixedBox</td><td>CollisionDetection::penetrationDepthForFixedBoxFixedBox</td></tr> + </table> + + <p> + <b>Moving Collision Detection:</b> + + <i>* 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''</i> + */ +class CollisionDetection { +private: + + /** + Default parameter if value passed to a function as reference is + not to be calculated. Must be explicitly supported by function. + */ + static Vector3 ignore; + + /** + Default parameter if value passed to a function as reference is + not to be calculated. Must be explicitly supported by function. + */ + static bool ignoreBool; + + /** + Default parameter if value passed to a function as reference is + not to be calculated. Must be explicitly supported by function. + */ + static Array<Vector3> ignoreArray; + + + // Static class! + CollisionDetection() {} + virtual ~CollisionDetection() {} + +public: + + /** + Converts an index [0, 15] to the corresponding separating axis. + Does not return normalized vector in the edge-edge case + (indices 6 through 15). + + @param separatingAxisIndex Separating axis. + @param box1 Box 1. + @param box2 Box 2. + + @return Axis that separates the two boxes. + */ + static Vector3 separatingAxisForSolidBoxSolidBox( + const int separatingAxisIndex, + const Box & box1, + const Box & box2); + + /** + 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. + + @param ca Dot products of each of the boxes axes + @param epsilon Fudge factor (small unit by which the dot + products may vary and still be considered + zero). + @param axis1 Parallel Axis 1. [Post Condition] + @param axis2 Parallel Axis 2. [Post Condition] + + @return true - If boxes have a parallel axis + @return false - otherwise. + */ + static bool parallelAxisForSolidBoxSolidBox( + const double* ca, + const double epsilon, + int & axis1, + int & axis2); + + /** + 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 + + @param separatingAxisIndex + @param a Box 1's bounding sphere vector + @param b Box 2's bounding sphere vector + @param D Vector between Box 1 and Box 2's center points + @param c Pointer to array of dot products of the axes of Box 1 + and Box 2. + @param ca Pointer to array of unsigned dot products of the axes + of Box 1 and Box 2. + @param ad Pointer to array of dot products of Box 1 axes and D. + @param bd Pointer to array of dot products of Box 2 axes and D. + + @return Projected distance between the two boxes along the + specified separating axis. + */ + 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); + + + /** + 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. + + @pre The following space requirements must be met: + - c[] 9 elements + - ca[] 9 elements + - ad[] 3 elements + - bd[] 3 elements + + @cite 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) + + @param box1 Box 1 + @param box2 Box 2 + @param a Box 1's bounding sphere vector + @param b Box 2's bounding sphere vector + @param D Vector between Box 1 and Box 2's center points + @param c Pointer to array of dot products of the axes of Box 1 + and Box 2. + @param ca Pointer to array of unsigned dot products of the axes + of Box 1 and Box 2. + @param ad Pointer to array of dot products of Box 1 axes and D. + @param bd Pointer to array of dot products of Box 2 axes and D. + */ + static void fillSolidBoxSolidBoxInfo( + const Box & box1, + const Box & box2, + Vector3 & a, + Vector3 & b, + Vector3 & D, + double* c, + double* ca, + double* ad, + double* bd); + + /** + Performs a simple bounding sphere check between two boxes to determine + whether these boxes could <i>possibly</i> 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. + + @param a Vector from box A's center to an outer vertex + @param b Vector from box B's center to an outer vertex + @param D Distance between the centers of the two boxes + + @return true - if possible intersection + @return false - otherwise (This does not guarantee an intersection) + */ + static bool conservativeBoxBoxTest( + const Vector3 & a, + const Vector3 & b, + const Vector3 & D); + + /** + 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. + + @cite 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 + + @param box1 Box 1. + @param box2 Box 2. + @param lastSeparatingAxis Last separating axis. + (optimization - see note) + + @return true - Intersection. + @return false - otherwise. + */ + static bool fixedSolidBoxIntersectsFixedSolidBox( + const Box& box1, + const Box& box2, + const int lastSeparatingAxis = -1); + + /** + 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. + + @cite variables and algorithm based on derivation at the following website: + http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm + + @param line1 Line 1. + @param line2 Line 2. + @param closest1 Closest point on line 1. + @param closest2 Closest point on line 2. + */ + static void closestPointsBetweenLineAndLine( + const Line & line1, + const Line & line2, + Vector3 & closest1, + Vector3 & closest2); + + /** + 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. + + @cite 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 + + @param box1 Box 1 + @param box2 Box 2 + @param contactPoints Contact point between boxes. [Post Condition] + @param contactNormals Surface normal at contact point. [Post Condition] + @param lastSeparatingAxis Last separating axis. (Used for optimization) + + @return Depth of penetration between the two boxes. If there is no + intersection between the boxes, then a negative value is returned. + */ + static float penetrationDepthForFixedBoxFixedBox( + const Box& box1, + const Box& box2, + Array<Vector3>& contactPoints, + Array<Vector3>& contactNormals, + const int lastSeparatingAxis = -1); + + /** + 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 <B>away</B> 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. + + @param sphereA Fixed Sphere A. + @param sphereB Fixed Sphere B. + @param contactPoints Sphere A's deepest point that penetrates Sphere B. + [Post Condition] + @param contactNormals Normal at penetration point. [Post Condition] + + @return Depth of penetration. If there is no intersection between the + objects then the depth will be a negative value. + */ + static float penetrationDepthForFixedSphereFixedSphere( + const class Sphere& sphereA, + const Sphere& sphereB, + Array<Vector3>& contactPoints, + Array<Vector3>& contactNormals = ignoreArray); + + /** + 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. + + @cite Adapted from Jim Arvo's method in Graphics Gems + See also http://www.win.tue.nl/~gino/solid/gdc2001depth.pdf + + @param sphere Fixed Sphere. + @param box Fixed Box. + @param contactPoints Sphere point that penetrates the box. [Post Condition] + @param contactNormals Normal at the penetration point. [Post Condition] + + @return Depth of penetration. If there is no intersection between the + objects then the depth will be a negative value. + */ + static float penetrationDepthForFixedSphereFixedBox( + const Sphere& sphere, + const Box& box, + Array<Vector3>& contactPoints, + Array<Vector3>& contactNormals = ignoreArray); + + /** + 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. + + @param sphere Fixed Sphere. + @param plane Fixed Plane. + @param contactPoints Sphere point that penetrates the plane. + [Post Condition] + @param contactNormals Normal at penetration point. [Post Condition] + + @return Depth of penetration. If there is no intersection between the + objects then the depth will be a negative value. + */ + static float penetrationDepthForFixedSphereFixedPlane( + const Sphere& sphereA, + const class Plane& planeB, + Array<Vector3>& contactPoints, + Array<Vector3>& contactNormals = ignoreArray); + + /** + 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. + + @param box Fixed Box. + @param plane Fixed Plane. + @param contactPoints Box points that penetrate the plane. + [Post Condition] + @param contactNormals Normals at penetration points [Post Condition] + + @return Depth of penetration. If there is no intersection between the + objects then the depth will be a negative value. + */ + static float penetrationDepthForFixedBoxFixedPlane( + const Box& box, + const Plane& plane, + Array<Vector3>& contactPoints, + Array<Vector3>& contactNormals = ignoreArray); + + /** + 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. + + @param point Moving point. + @param velocity Point's velocity. + @param plane Fixed plane. + @param location Location of collision. [Post Condition] + (Infinite vector on no collision) + @param outNormal Plane's surface normal. [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingPointFixedPlane( + const Vector3& point, + const Vector3& velocity, + const class Plane& plane, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + 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. + + @param orig Moving point. + @param dir Point's velocity. + @param v0 Triangle vertex 1. + @param v1 Triangle vertex 2. + @param v2 Triangle vertex 3 + @param location Location of collision. [Post Condition] + (Infinite vector on no collision) + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + inline static float collisionTimeForMovingPointFixedTriangle( + const Vector3& orig, + const Vector3& dir, + const Vector3& v0, + const Vector3& v1, + const Vector3& v2) { + return Ray::fromOriginAndDirection(orig, dir).intersectionTime(v0, v1, v2); + } + + /** + 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. + + @param orig Moving point. + @param dir Point's velocity. + @param v0 Triangle vertex 1. + @param v1 Triangle vertex 2. + @param v2 Triangle vertex 3 + @param location Location of collision. [Post Condition] + (Infinite vector on no collision) + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + inline static float collisionTimeForMovingPointFixedTriangle( + const Vector3& orig, + const Vector3& dir, + const Vector3& v0, + const Vector3& v1, + const Vector3& v2, + Vector3& location) { + float t = collisionTimeForMovingPointFixedTriangle(orig, dir, v0, v1, v2); + if (t < inf()) { + location = orig + dir * t; + } + return t; + } + + /** + 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. + + @param orig Moving point. + @param dir Point's velocity. + @param tri Fixed triangle. + @param location Location of collision. [Post Condition] + (Infinite vector on no collision) + @param normal Triangle's surface normal. [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + inline static float collisionTimeForMovingPointFixedTriangle( + const Vector3& orig, + const Vector3& dir, + const Triangle& tri, + Vector3& location = ignore, + Vector3& normal = ignore) { + + float t = collisionTimeForMovingPointFixedTriangle( + orig, dir, tri.vertex(0), tri.vertex(1), tri.vertex(2)); + + if ((t < inf()) && (&location != &ignore)) { + location = orig + dir * t; + normal = tri.normal(); + } + return t; + } + + /** + 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. + + @param orig Moving point. + @param dir Point's velocity. + @param v0 Triangle vertex 1. + @param v1 Triangle vertex 2. + @param v2 Triangle vertex 3 + @param location Location of collision. [Post Condition] + (Infinite vector on no collision) + @param normal Triangle's surface normal. [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + inline static float collisionTimeForMovingPointFixedTriangle( + const Vector3& orig, + const Vector3& dir, + const Vector3& v0, + const Vector3& v1, + const Vector3& v2, + Vector3& location, + Vector3& normal) { + float t = collisionTimeForMovingPointFixedTriangle(orig, dir, v0, v1, v2); + if (t < inf()) { + location = orig + dir * t; + normal = (v2 - v0).cross(v1 - v0).direction(); + } + return t; + } + + /** + Unlike other methods, does not support an output normal. + If the ray origin is inside the box, returns inf() but inside + is set to true. + <B>Beta API</B> + + @cite Andrew Woo, from "Graphics Gems", Academic Press, 1990 + @cite Optimized code by Pierre Terdiman, 2000 (~20-30% faster on my Celeron 500) + @cite Epsilon value added by Klaus Hartmann + @cite http://www.codercorner.com/RayAABB.cpp + */ + static float collisionTimeForMovingPointFixedAABox( + const Vector3& point, + const Vector3& velocity, + const class AABox& box, + Vector3& outLocation, + bool& inside = ignoreBool, + Vector3& outNormal = ignore); + + /** + Calculates time between the intersection of a moving point and a fixed + Axis-Aligned Box (AABox). + + @note Avoids the sqrt from collisionTimeForMovingPointFixedAABox. + + @param point Moving point. + @param velocity Sphere's velocity. + @param box Fixed AAbox. + @param location Location of collision. [Post Condition] + @param Inside Does the ray originate inside the box? [Post Condition] + @param normal Box's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static bool collisionLocationForMovingPointFixedAABox( + const Vector3& point, + const Vector3& velocity, + const class AABox& box, + Vector3& outLocation, + bool& inside = ignoreBool, + Vector3& normal = ignore); + + /** + 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. + + @param point Moving point. + @param velocity Point's velocity. + @param Sphere Fixed Sphere. + @param location Location of collision. [Post Condition] + @param outNormal Sphere's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingPointFixedSphere( + const Vector3& point, + const Vector3& velocity, + const class Sphere& sphere, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + 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. + + @param point Moving point. + @param velocity Sphere's velocity. + @param box Fixed box. + @param location Position of collision. [Post Condition] + @param outNormal Box's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingPointFixedBox( + const Vector3& point, + const Vector3& velocity, + const class Box& box, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + 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. + + @param point Moving point. + @param velocity Sphere's velocity. + @param v0 Rectangle vertex 1. + @param v1 Rectangle vertex 2. + @param v2 Rectangle vertex 3 + @param v3 Rectangle vertex 4. + @param location Location of collision [Post Condition] + @param outNormal Rectangle's surface normal. [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + 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); + + /** + Calculates time between the intersection of a moving point and a fixed + capsule. + + @param point Moving point. + @param velocity Point's velocity. + @param capsule Fixed capsule. + @param location Location of collision. [Post Condition] + @param outNormal Capsule's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingPointFixedCapsule( + const Vector3& point, + const Vector3& velocity, + const class Capsule& capsule, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + Calculates time between the intersection of a moving sphere and a fixed + triangle. + + @param sphere Moving sphere. + @param velocity Sphere's velocity. + @param plane Fixed Plane. + @param location Location of collision -- not center position of sphere + at the collision time. [Post Condition] + @param outNormal Box's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingSphereFixedPlane( + const class Sphere& sphere, + const Vector3& velocity, + const class Plane& plane, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + Calculates time between the intersection of a moving sphere and a fixed + triangle. + + @param sphere Moving sphere. + @param velocity Sphere's velocity. + @param triangle Fixed Triangle. + @param location Location of collision -- not center position of sphere + at the collision time. [Post Condition] + @param outNormal Box's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingSphereFixedTriangle( + const class Sphere& sphere, + const Vector3& velocity, + const Triangle& triangle, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + Calculates time between the intersection of a moving sphere and a fixed + rectangle defined by the points v0, v1, v2, & v3. + + @param sphere Moving sphere. + @param velocity Sphere's velocity. + @param v0 Rectangle vertex 1. + @param v1 Rectangle vertex 2. + @param v2 Rectangle vertex 3 + @param v3 Rectangle vertex 4. + @param location Location of collision -- not center position of sphere + at the collision time. [Post Condition] + @param outNormal Box's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + 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); + + /** + 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. + + @param sphere Moving sphere. + @param velocity Sphere's velocity. + @param box Fixed box. + @param location Location of collision -- not center position of sphere + at the collision time. [Post Condition] + @param outNormal Box's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingSphereFixedBox( + const class Sphere& sphere, + const Vector3& velocity, + const class Box& box, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + Calculates time between the intersection of a moving sphere and a fixed + sphere. + + @note This won't detect a collision if the sphere is already interpenetrating + the fixed sphere. + + @param movingSphere Moving sphere. + @param velocity Sphere's velocity. + @param fixedSphere Fixed Sphere. + @param location Location of collision -- not center position of sphere + at the collision time. [Post Condition] + @param outNormal Sphere's surface normal to collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingSphereFixedSphere( + const class Sphere& sphere, + const Vector3& velocity, + const class Sphere& fixedSphere, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + 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. + + @param sphere Moving sphere. + @param velocity Sphere's velocity. + @param capsule Fixed capsule. + @param location Location of collision -- not center position of sphere + at the collision time. [Post Condition] + @param outNormal Capsule's surface normal to the collision [Post Condition] + + @return Time til collision. If there is no collision then the return + value will be inf(). + */ + static float collisionTimeForMovingSphereFixedCapsule( + const class Sphere& sphere, + const Vector3& velocity, + const class Capsule& capsule, + Vector3& outLocation, + Vector3& outNormal = ignore); + + /** + 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. + + @param sphere Moving sphere. + @param velocity Sphere's velocity. + @param collisionTime Time of collision. + @param collisionLocation Collision location. + @param collisionNormal Surface collision normal. + + @return Direction of bounce. + */ + static Vector3 bounceDirection( + const class Sphere& sphere, + const Vector3& velocity, + const float collisionTime, + const Vector3& collisionLocation, + const Vector3& collisionNormal); + + /** + 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. + + @param sphere Moving sphere. + @param velocity Sphere's velocity. + @param collisionTime Time of collision + @param collisionLocation Collision location. + + @return Direction of slide. + */ + static Vector3 slideDirection( + const class Sphere& sphere, + const Vector3& velocity, + const float collisionTime, + const Vector3& collisionLocation); + + /** + Finds the closest point on a line segment to a given point. + + @param v0 line vertex 1. + @param v1 line vertex 2. + @param point External point. + + @return Closests point to <code>point</code> on the line segment. + */ + static Vector3 closestPointOnLineSegment( + const Vector3& v0, + const Vector3& v1, + const Vector3& point); + + /** + 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. + + @param v0 line vertex 1. + @param v1 line vertex 2. + @param edgeDirection The direction of the segment (unit length). + @param edgeLength The length of the segment. + @param point External point. + + @return Closests point to <code>point</code> on the line segment. + */ + static Vector3 closestPointOnLineSegment( + const Vector3& v0, + const Vector3& v1, + const Vector3& edgeDirection, + float edgeLength, + const Vector3& point); + + /** + 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. + + @param v0 Triangle vertex 1. + @param v1 Triangle vertex 2. + @param v2 Triangle vertex 3. + @param point External point. + + @return Closests point to <code>point</code> on the perimeter of the + triangle. + */ + static Vector3 closestPointToTrianglePerimeter( + const Vector3& v0, + const Vector3& v1, + const Vector3& v2, + const Vector3& point); + + /** + 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. + + @param v0 Triangle vertex 1. + @param v1 Triangle vertex 2. + @param v2 Triangle vertex 3. + @param point External point. + + @return Closests point to <code>point</code> on the perimeter of the + triangle. + */ + static Vector3 closestPointToTrianglePerimeter( + const Vector3 v[3], + const Vector3 edgeDirection[3], + const double edgeLength[3], + const Vector3& point); + + /** + Tests whether a point is contained within the triangle defined by + v0, v1, & v2 and its plane's normal. + + @param v0 Triangle vertex 1. + @param v1 Triangle vertex 2. + @param v2 Triangle vertex 3. + @param normal Normal to triangle's plane. + @param point The point in question. + @param primaryAxis Primary axis of triangle. This will be detected + if not given. This parameter is provided as an optimization. + + @return true - if point is inside the triangle. + @return false - otherwise + */ + static bool isPointInsideTriangle( + const Vector3& v0, + const Vector3& v1, + const Vector3& v2, + const Vector3& normal, + const Vector3& point, + Vector3::Axis primaryAxis = Vector3::DETECT_AXIS); + + /** + 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. + + @param sphere Moving sphere. + @param velocity Velocity of moving sphere. + @param box Fixed box. + @param timeLimit Time limit for intersection test. + + @return true - if the two objects will touch. + @return false - if there is no intersection. + */ + static bool movingSpherePassesThroughFixedBox( + const Sphere& sphere, + const Vector3& velocity, + const Box& box, + double timeLimit = inf()); + + /** + 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. + + @param sphere Moving sphere. + @param velocity Velocity of moving sphere. + @param fixedSphere Fixed sphere. + @param timeLimit Time limit for intersection test. + + @return true - if the two spheres will touch. + @return false - if there is no intersection. + */ + static bool movingSpherePassesThroughFixedSphere( + const Sphere& sphere, + const Vector3& velocity, + const Sphere& fixedSphere, + double timeLimit = inf()); + + /** + Tests for the intersection of two fixed spheres. + + @param sphere1 Fixed sphere 1. + @param sphere2 Fixed sphere 2. + + @return true - if the two spheres touch. + @return false - if there is no intersection. + */ + static bool fixedSolidSphereIntersectsFixedSolidSphere( + const Sphere& sphere1, + const Sphere& sphere2); + + /** + Tests for the intersection of a fixed sphere and a fixed box. + + @param sphere Fixed sphere. + @param box Fixed box. + + @return true - if the two objects touch. + @return false - if there is no intersection. + */ + static bool fixedSolidSphereIntersectsFixedSolidBox( + const Sphere& sphere, + const Box& box); + + /** + Tests whether a point is inside a rectangle defined by the vertexes + v0, v1, v2, & v3, and the rectangle's plane normal. + + @param v0 Rectangle vertex 1. + @param v1 Rectangle vertex 2. + @param v2 Rectangle vertex 3. + @param v3 Rectangle vertex 4. + @param normal Normal to rectangle's plane. + @param point The point in question. + + @return true - if point is inside the rectangle. + @return false - otherwise + */ + static bool isPointInsideRectangle( + const Vector3& v0, + const Vector3& v1, + const Vector3& v2, + const Vector3& v3, + const Vector3& normal, + const Vector3& point); + + /** + 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. + + @param v0 Rectangle vertex 1. + @param v1 Rectangle vertex 2. + @param v2 Rectangle vertex 3. + @param v3 Rectangle vertex 4. + @param point External point. + + @return Closests point to <code>point</code> on the perimeter of the + rectangle. + */ + static Vector3 closestPointToRectanglePerimeter( + const Vector3& v0, + const Vector3& v1, + const Vector3& v2, + const Vector3& v3, + const Vector3& point); + + /** + 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. + + @param v0 Rectangle vertex 1. + @param v1 Rectangle vertex 2. + @param v2 Rectangle vertex 3 + @param v3 Rectangle vertex 4. + @param point External point. + + @return Closet point in the rectangle to the external point. + */ + static Vector3 closestPointToRectangle( + const Vector3& v0, + const Vector3& v1, + const Vector3& v2, + const Vector3& v3, + const Vector3& point); +}; + +} // namespace + +#endif // G3D_COLLISIONDETECTION_H |