📄 collisiondetection.h
字号:
/**
@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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -