Collision detection
In a 3d engine, the collision detection techniques are a very broad subject, which covers a range from the simple bounding box collisions to Binary Space Partitioning (BSP) trees, passing by the polygon intersection techniques.
As CompactStar is a tiny engine, I experienced some that were useful to me, but by far not all of them.
However I'll expose below the common techniques I know and I implemented in the CompactStar source code, which may be found in huge majority in the csrIntersect3() function, located in the CSR_Geometry.c and CSR_Geometry.h files.
The bounding boxes are the simpler and faster way to evaluate a collision. The principle consists in enclosing a complex mesh in a mathematical shape, which encompasses approximately, but as much as possible, the shape of the mesh. The closer the shape is to the mesh, the more precise the detection will be.
Of course, a such test is not enough to resolve a complex collision detection system, however it's a very important technique, because due to its speed, it is commonly used as a preliminary test to determine if a further and more precise collision detection is required on the involved meshes.
The bounding box collision detection tests are often simple algorithms to apply, and there are many mathematical shapes which may be used, so I'll briefly expose below the 3 most commonly used in the 3d engines.
The box-box collision is simply an extension of the rectangle to rectangle algorithm in 2d, but including the 3rd dimension. It consists to calculate if the space of the first box intersects the space of the second.
return !(pBox1->m_Min.m_X <= pBox2->m_Max.m_X &&
pBox1->m_Max.m_X >= pBox2->m_Min.m_X &&
pBox1->m_Min.m_Y <= pBox2->m_Max.m_Y &&
pBox1->m_Max.m_Y >= pBox2->m_Min.m_Y &&
pBox1->m_Min.m_Z <= pBox2->m_Max.m_Z &&
pBox1->m_Max.m_Z >= pBox2->m_Min.m_Z);The sphere-sphere collision is the simplest algorithm of all, just need to calculate the distance between the 2 sphere centers. If this distance is lower than the sum of the both sphere radius, then the spheres are in collision.
CSR_Vector3 dist;
float length;
// calculate the distance between the both sphere centers
dist.m_X = fabs(pSphere1->m_Center.m_X - pSphere2->m_Center.m_X);
dist.m_Y = fabs(pSphere1->m_Center.m_Y - pSphere2->m_Center.m_Y);
dist.m_Z = fabs(pSphere1->m_Center.m_Z - pSphere2->m_Center.m_Z);
// calculate the length between the both sphere centers
csrVec3Length(&dist, &length);
// the spheres are in collision if the length between their centers is lower than or equal to
// the sum of the both sphere radius
return (length <= (pSphere1->m_Radius + pSphere2->m_Radius));This shape is a little particular, because capsules are often used to simulate a body, e.g. in a game with a first person view, and not just to determine if a more complex collision test should be performed.
Contrary to the previous one, this test is one of the more complex to perform, because a capsule is composed by several simpler shapes, i.e 2 spheres and a cylinder. For that reason several scenarios may happen and should be considered.
The following article explains in details how a capsule collision detection works and how to implement it.
Anyway, below is the code I use:
CSR_Vector3 firstLineDir;
CSR_Vector3 firstLineEndOffset;
CSR_Vector3 firstTop;
CSR_Vector3 firstBottom;
CSR_Vector3 secondLineDir;
CSR_Vector3 secondLineEndOffset;
CSR_Vector3 secondTop;
CSR_Vector3 secondBottom;
CSR_Vector3 v0;
CSR_Vector3 v1;
CSR_Vector3 v2;
CSR_Vector3 v3;
CSR_Vector3 bestCandidate;
CSR_Vector3 secondBestCandidate;
CSR_Vector3 penetrationNormal;
CSR_Segment3 line;
CSR_Segment3 secondLine;
float d0;
float d1;
float d2;
float d3;
float len;
float penetrationDepth;
// perfect collision (rare, but may happen)
if ((pCapsule1->m_Top.m_X == pCapsule2->m_Top.m_X &&
pCapsule1->m_Top.m_Y == pCapsule2->m_Top.m_Y &&
pCapsule1->m_Top.m_Z == pCapsule2->m_Top.m_Z) ||
(pCapsule1->m_Bottom.m_X == pCapsule2->m_Bottom.m_X &&
pCapsule1->m_Bottom.m_Y == pCapsule2->m_Bottom.m_Y &&
pCapsule1->m_Bottom.m_Z == pCapsule2->m_Bottom.m_Z))
return 1;
// this capsule
csrVec3Sub (&pCapsule1->m_Top, &pCapsule1->m_Bottom, &firstLineDir);
csrVec3Normalize(&firstLineDir, &firstLineDir);
csrVec3MulVal (&firstLineDir, pCapsule1->m_Radius, &firstLineEndOffset);
csrVec3Sub (&pCapsule1->m_Top, &firstLineEndOffset, &firstTop);
csrVec3Add (&pCapsule1->m_Bottom, &firstLineEndOffset, &firstBottom);
// second capsule
csrVec3Sub (&pCapsule2->m_Top, &pCapsule2->m_Bottom, &secondLineDir);
csrVec3Normalize(&secondLineDir, &secondLineDir);
csrVec3MulVal (&secondLineDir, pCapsule2->m_Radius, &secondLineEndOffset);
csrVec3Sub (&pCapsule2->m_Top, &secondLineEndOffset, &secondTop);
csrVec3Add (&pCapsule2->m_Bottom, &secondLineEndOffset, &secondBottom);
// vectors between line endpoints
csrVec3Sub(&secondBottom, &firstBottom, &v0);
csrVec3Sub(&secondTop, &firstBottom, &v1);
csrVec3Sub(&secondBottom, &firstTop, &v2);
csrVec3Sub(&secondTop, &firstTop, &v3);
// squared distances
csrVec3Dot(&v0, &v0, &d0);
csrVec3Dot(&v1, &v1, &d1);
csrVec3Dot(&v2, &v2, &d2);
csrVec3Dot(&v3, &v3, &d3);
// select best candidate for endpoint on first capsule
if (d2 < d0 || d2 < d1 || d3 < d0 || d3 < d1)
bestCandidate = firstTop;
else
bestCandidate = firstBottom;
line.m_Start = firstBottom;
line.m_End = firstTop;
secondLine.m_Start = secondBottom;
secondLine.m_End = secondTop;
// select best candidate for point on second capsule line segment nearest to best potential endpoint on first capsule
csrSeg3ClosestPoint(&secondLine, &bestCandidate, &secondBestCandidate);
// do the same for first capsule segment
csrSeg3ClosestPoint(&line, &secondBestCandidate, &bestCandidate);
// calculate penetration normal and length
csrVec3Sub (&bestCandidate, &secondBestCandidate, &penetrationNormal);
csrVec3Length(&penetrationNormal, &len);
if (len == 0.0f)
return 0;
// normalize
csrVec3DivVal(&penetrationNormal, len, &penetrationNormal);
// calculate the penetration depth
penetrationDepth = (pCapsule1->m_Radius + pCapsule2->m_Radius) - len;
return (penetrationDepth > 0.0f);The polygon-ray intersection is, from my point of view, one of the most useful collision detection technique. I use it for example to detect if the mouse hovers an object in the 3d world, or to follow the contours of the ground. But it may be also used in several situations, e.g. to detect where exactly a bullet hits a model, ...
Contrary to the majority of bounding box collisions, this technique is more an algorithm than a formula, it involves indeed several steps to get the final result, as you can see on the below animation:
The first step to detect if a ray intersects a polygon is to get the polygon plane from its vertices. This may be achieved in the following manner:
void csrPlaneFromPointNormal(const CSR_Vector3* pP, const CSR_Vector3* pN, CSR_Plane* pR)
{
float d;
// the a, b, and c components are only the normal of the plane
pR->m_A = pN->m_X;
pR->m_B = pN->m_Y;
pR->m_C = pN->m_Z;
// calculate plane d component using the aX + bY + cZ + d = 0 formula
csrVec3Dot(pN, pP, &d);
pR->m_D = -d;
}
void csrPlaneFromPoints(const CSR_Vector3* pV1,
const CSR_Vector3* pV2,
const CSR_Vector3* pV3,
CSR_Plane* pR)
{
CSR_Vector3 e1;
CSR_Vector3 e2;
CSR_Vector3 normal;
// calculate edge vectors
csrVec3Sub(pV2, pV1, &e1);
csrVec3Sub(pV3, pV1, &e2);
// calculate the normal of the plane
csrVec3Cross(&e1, &e2, &normal);
csrVec3Normalize(&normal, &normal);
// calculate and return the plane
csrPlaneFromPointNormal(pV1, &normal, pR);
}The second step is to find the point where the ray intersects the plane. This may be achieved in the following manner:
CSR_Vector3 n;
float dot;
float nDot;
float temp;
// get the figures to check
const CSR_Ray3* pRay = (CSR_Ray3*)pFirst;
const CSR_Plane* pPlane = (CSR_Plane*)pSecond;
// get the normal of the plane
n.m_X = pPlane->m_A;
n.m_Y = pPlane->m_B;
n.m_Z = pPlane->m_C;
// calculate the angle between the line and the normal to the plane
csrVec3Dot(&n, &pRay->m_Dir, &dot);
// if normal to the plane is perpendicular to the line, then the line is either parallel
// to the plane and there are no solutions or the line is on the plane in which case
// there are an infinite number of solutions
if (!dot)
return 0;
csrVec3Dot(&n, &pRay->m_Pos, &nDot);
temp = ((pPlane->m_D + nDot) / dot);
// calculate the intersection point
if (pR1)
{
pR1->m_X = (pRay->m_Pos.m_X - (temp * pRay->m_Dir.m_X));
pR1->m_Y = (pRay->m_Pos.m_Y - (temp * pRay->m_Dir.m_Y));
pR1->m_Z = (pRay->m_Pos.m_Z - (temp * pRay->m_Dir.m_Z));
}
return 1;Once the intersection point between the ray and the plane composed by the 3 vertices of the polygon was found, the only remaining step is to determine if this point is inside or outside the polygon.
To achieve that, we need to calculate the segment between the point and each polygon vertices, then to calculate the angle between each of these segments, and sum them.
If the sum is equals to 2 * π, then the angle is inside the polygon, in this case the ray hits the polygon, otherwise it is outside, in this case the ray misses the polygon.
int csrInsidePolygon3(const CSR_Vector3* pP, const CSR_Polygon3* pPo)
{
CSR_Vector3 nPToV1;
CSR_Vector3 nPToV2;
CSR_Vector3 nPToV3;
float a1;
float a2;
float a3;
float angleResult;
/*
* check if the point p is inside the polygon in the following manner:
*
* V1 V1
* /\ /\
* / \ / \
* / *p \ *P / \
* / \ / \
* V2 -------- V3 V2 -------- V3
*
* calculate the vectors between the point p and each polygon vertex, then calculate the angle
* formed by each of these vectors. If the sum of the angles is equal to a complete circle, i.e.
* 2 * PI in radians, then the point p is inside the polygon limits, otherwise the point is
* outside. It is assumed that the point to check belongs to the polygon's plane
*/
csrVec3Sub(&pPo->m_Vertex[0], pP, &nPToV1);
csrVec3Sub(&pPo->m_Vertex[1], pP, &nPToV2);
csrVec3Sub(&pPo->m_Vertex[2], pP, &nPToV3);
csrVec3Normalize(&nPToV1, &nPToV1);
csrVec3Normalize(&nPToV2, &nPToV2);
csrVec3Normalize(&nPToV3, &nPToV3);
// calculate the angles using the scalar product of each vectors with the following formulas:
// A1 = NPToV1.x * NPToV2.x + NPToV1.y * NPToV2.y + NPToV1.z * NPToV2.z
// A2 = NPToV2.x * NPToV3.x + NPToV2.y * NPToV3.y + NPToV2.z * NPToV3.z
// A3 = NPToV3.x * NPToV1.x + NPToV3.y * NPToV1.y + NPToV3.z * NPToV1.z
csrVec3Dot(&nPToV1, &nPToV2, &a1);
csrVec3Dot(&nPToV2, &nPToV3, &a2);
csrVec3Dot(&nPToV3, &nPToV1, &a3);
// limit a1 to avoid rounding errors
if (a1 > 1.0f)
a1 = 1.0f;
else
if (a1 < -1.0f)
a1 = -1.0f;
// limit a2 to avoid rounding errors
if (a2 > 1.0f)
a2 = 1.0f;
else
if (a2 < -1.0f)
a2 = -1.0f;
// limit a3 to avoid rounding errors
if (a3 > 1.0f)
a3 = 1.0f;
else
if (a3 < -1.0f)
a3 = -1.0f;
// calculate the sum of all angles
angleResult = acos(a1) + acos(a2) + acos(a3);
// if sum is equal or higher to 6.28 radians then point P is inside polygon
if (angleResult >= 6.28f)
return 1;
return 0;
}An aligned-axis bounding box tree (often summarized in AABB tree), is a technique allowing to simplify a complex collision system, like a mesh, by dividing it in smaller group of polygons, bounded by a collision box aligned on the x, y and z axis.
Depending on which bounding box is hit, it's easy to find which polygons may potentially be in collision, and to test them further with a more complex algorithm.
In CompactStar a such algorithm is implemented in the CSR_Collision.c and CSR_Collision.h files.
Take a look to the CSR_AABBNode structure:
/**
* Aligned-axis bounding box tree node
*/
typedef struct CSR_tagAABBNode
{
struct CSR_tagAABBNode* m_pParent;
struct CSR_tagAABBNode* m_pLeft;
struct CSR_tagAABBNode* m_pRight;
CSR_Box* m_pBox;
CSR_IndexedPolygonBuffer* m_pPolygonBuffer;
} CSR_AABBNode;The m_pBox member contains the bounding box owning the node. The m_pParent represents the parent node in which this node is contained, meaning that the bounding box is a sub-division of the parent box. The m_pLeft and m_pRight members contain the sub-divided nodes, meaning that their bounding boxes fit in the current node bounding box. Finally the m_pPolygonBuffer contains all the polygons owned by the node bounding box.
In CompactStar, an AABB tree may be built using the following function:
int csrAABBTreeFromIndexedPolygonBuffer(const CSR_IndexedPolygonBuffer* pIPB,
CSR_AABBNode* pNode)
{
size_t i;
size_t j;
CSR_Box leftBox;
CSR_Box rightBox;
CSR_Polygon3 polygon;
CSR_IndexedPolygon* pNewPolygons = 0;
CSR_IndexedPolygonBuffer* pLeftPolygons = 0;
CSR_IndexedPolygonBuffer* pRightPolygons = 0;
int boxEmpty = 1;
int insideLeft = 0;
int insideRight = 0;
int canResolveLeft = 0;
int canResolveRight = 0;
int result = 0;
// no indexed polygon buffer?
if (!pIPB)
return 0;
// no node?
if (!pNode)
return 0;
// initialize node content
pNode->m_pParent = 0;
pNode->m_pLeft = 0;
pNode->m_pRight = 0;
pNode->m_pBox = (CSR_Box*)malloc(sizeof(CSR_Box));
pNode->m_pPolygonBuffer = csrIndexedPolygonBufferCreate();
// succeeded?
if (!pNode->m_pBox || !pNode->m_pPolygonBuffer)
{
csrAABBTreeNodeContentRelease(pNode);
return 0;
}
// create the polygon buffers that will contain the divided polygons
pLeftPolygons = csrIndexedPolygonBufferCreate();
pRightPolygons = csrIndexedPolygonBufferCreate();
// succeeded?
if (!pLeftPolygons || !pRightPolygons)
{
csrIndexedPolygonBufferRelease(pLeftPolygons);
csrIndexedPolygonBufferRelease(pRightPolygons);
csrAABBTreeNodeContentRelease(pNode);
return 0;
}
// iterate through polygons to divide
for (i = 0; i < pIPB->m_Count; ++i)
{
// using its index, extract the polygon from its vertex buffer
csrIndexedPolygonToPolygon(&pIPB->m_pIndexedPolygon[i], &polygon);
// extend the bounding box to include the polygon
csrBoxExtendToPolygon(&polygon, pNode->m_pBox, &boxEmpty);
}
// divide the bounding box in 2 sub-boxes
csrBoxCut(pNode->m_pBox, &leftBox, &rightBox);
// iterate again through polygons to divide
for (i = 0; i < pIPB->m_Count; ++i)
{
// get the concrete polygon (i.e. with physical coordinates, not indexes)
csrIndexedPolygonToPolygon(&pIPB->m_pIndexedPolygon[i], &polygon);
insideLeft = 0;
insideRight = 0;
// check which box contains the most vertices
for (j = 0; j < 3; ++j)
// is vertex inside left or right sub-box?
if (csrInsideBox(&polygon.m_Vertex[j], &leftBox))
++insideLeft;
else
++insideRight;
// check at which sub-box the polygon belongs (and thus to which buffer it should be added)
if (insideLeft >= insideRight)
{
// allocate the memory to add a new polygon in the left polygon buffer
pNewPolygons = (CSR_IndexedPolygon*)csrMemoryAlloc(pLeftPolygons->m_pIndexedPolygon,
sizeof(CSR_IndexedPolygon),
pLeftPolygons->m_Count + 1);
// succeeded?
if (!pNewPolygons)
{
csrIndexedPolygonBufferRelease(pLeftPolygons);
csrIndexedPolygonBufferRelease(pRightPolygons);
csrAABBTreeNodeContentRelease(pNode);
return 0;
}
// update the buffer content
pLeftPolygons->m_pIndexedPolygon = pNewPolygons;
++pLeftPolygons->m_Count;
// copy the polygon index content in the left buffer
pLeftPolygons->m_pIndexedPolygon[pLeftPolygons->m_Count - 1] = pIPB->m_pIndexedPolygon[i];
}
else
{
// allocate the memory to add a new polygon in the left polygon buffer
pNewPolygons = (CSR_IndexedPolygon*)csrMemoryAlloc(pRightPolygons->m_pIndexedPolygon,
sizeof(CSR_IndexedPolygon),
pRightPolygons->m_Count + 1);
// succeeded?
if (!pNewPolygons)
{
csrIndexedPolygonBufferRelease(pLeftPolygons);
csrIndexedPolygonBufferRelease(pRightPolygons);
csrAABBTreeNodeContentRelease(pNode);
return 0;
}
// update the buffer content
pRightPolygons->m_pIndexedPolygon = pNewPolygons;
++pRightPolygons->m_Count;
// copy the polygon content inside its buffer
pRightPolygons->m_pIndexedPolygon[pRightPolygons->m_Count - 1] = pIPB->m_pIndexedPolygon[i];
}
}
canResolveLeft = (pLeftPolygons->m_Count && pLeftPolygons->m_Count < pIPB->m_Count);
canResolveRight = (pRightPolygons->m_Count && pRightPolygons->m_Count < pIPB->m_Count);
// leaf reached?
if (!canResolveLeft && !canResolveRight)
{
// iterate through left polygons to copy to the leaf polygon buffer
for (i = 0; i < pLeftPolygons->m_Count; ++i)
{
// allocate the memory to add a new polygon in the leaf node
pNewPolygons = (CSR_IndexedPolygon*)csrMemoryAlloc(pNode->m_pPolygonBuffer->m_pIndexedPolygon,
sizeof(CSR_IndexedPolygon),
pNode->m_pPolygonBuffer->m_Count + 1);
// succeeded?
if (!pNewPolygons)
{
csrIndexedPolygonBufferRelease(pLeftPolygons);
csrIndexedPolygonBufferRelease(pRightPolygons);
csrAABBTreeNodeContentRelease(pNode);
return 0;
}
// update the buffer content
pNode->m_pPolygonBuffer->m_pIndexedPolygon = pNewPolygons;
++pNode->m_pPolygonBuffer->m_Count;
// copy the polygon content inside the polygon buffer
pNode->m_pPolygonBuffer->m_pIndexedPolygon[pNode->m_pPolygonBuffer->m_Count - 1] =
pLeftPolygons->m_pIndexedPolygon[i];
}
// iterate through right polygons to copy to the leaf polygon buffer
for (i = 0; i < pRightPolygons->m_Count; ++i)
{
// allocate the memory to add a new polygon in the leaf node
pNewPolygons = (CSR_IndexedPolygon*)csrMemoryAlloc(pNode->m_pPolygonBuffer->m_pIndexedPolygon,
sizeof(CSR_IndexedPolygon),
pNode->m_pPolygonBuffer->m_Count + 1);
// succeeded?
if (!pNewPolygons)
{
csrIndexedPolygonBufferRelease(pLeftPolygons);
csrIndexedPolygonBufferRelease(pRightPolygons);
csrAABBTreeNodeContentRelease(pNode);
return 0;
}
// update the buffer content
pNode->m_pPolygonBuffer->m_pIndexedPolygon = pNewPolygons;
++pNode->m_pPolygonBuffer->m_Count;
// copy the polygon content inside the polygon buffer
pNode->m_pPolygonBuffer->m_pIndexedPolygon[pNode->m_pPolygonBuffer->m_Count - 1] =
pRightPolygons->m_pIndexedPolygon[i];
}
// release the left and right polygon buffers, as they will no longer be used
csrIndexedPolygonBufferRelease(pLeftPolygons);
csrIndexedPolygonBufferRelease(pRightPolygons);
return 1;
}
// do create left node?
if (canResolveLeft)
{
// create the left node
pNode->m_pLeft = (CSR_AABBNode*)malloc(sizeof(CSR_AABBNode));
// populate it
result |= csrAABBTreeFromIndexedPolygonBuffer(pLeftPolygons, pNode->m_pLeft);
// set node parent. IMPORTANT must be done after the node is populated (because this value
// will be reseted while the node is filled by csrAABBTreeFromIndexedPolygonBuffer())
pNode->m_pLeft->m_pParent = pNode;
// delete left polygon buffer, as it will no longer be used
csrIndexedPolygonBufferRelease(pLeftPolygons);
}
// do create right node?
if (canResolveRight)
{
// create the right node
pNode->m_pRight = (CSR_AABBNode*)malloc(sizeof(CSR_AABBNode));
// populate it
result |= csrAABBTreeFromIndexedPolygonBuffer(pRightPolygons, pNode->m_pRight);
// set node parent. IMPORTANT must be done after the node is populated (because this value
// will be reseted while the node is filled by csrAABBTreeFromIndexedPolygonBuffer())
pNode->m_pRight->m_pParent = pNode;
// delete right polygon buffer, as it will no longer be used
csrIndexedPolygonBufferRelease(pRightPolygons);
}
return result;
}This function will calculate the closest bounding box surrounding the polygons, then it will divide the box on the longest axis and distribute the polygons between the left and right subdivided boxes according to which space they occupies. Then the function will executes itself recursively on each sub-divided box and polygons, until reaching a region which can no longer be sub-divided.
To resolve the AABB tree, the following function may be used:
int csrAABBTreeResolve(const CSR_Ray3* pRay,
const CSR_AABBNode* pNode,
size_t deep,
CSR_Polygon3Buffer* pPolygons)
{
#ifdef _MSC_VER
unsigned i;
int leftResolved = 0;
int rightResolved = 0;
CSR_Polygon3* pPolygonBuffer = 0;
CSR_Figure3 ray = {0};
CSR_Figure3 box = {0};
#else
unsigned i;
int leftResolved = 0;
int rightResolved = 0;
CSR_Polygon3* pPolygonBuffer;
CSR_Figure3 ray;
CSR_Figure3 box;
#endif
// no ray?
if (!pRay)
return 0;
// no node to resolve?
if (!pNode)
return 0;
// no polygon buffer to contain the result?
if (!pPolygons)
return 0;
// is the first iteration?
if (!deep)
{
// ensure the polygon buffer is initialized, otherwise this may cause hard-to-debug bugs
pPolygons->m_pPolygon = 0;
pPolygons->m_Count = 0;
}
// is leaf?
if (!pNode->m_pLeft && !pNode->m_pRight)
{
// iterate through polygons contained in leaf
for (i = 0; i < pNode->m_pPolygonBuffer->m_Count; ++i)
{
// allocate memory for a new polygon in the buffer
pPolygonBuffer = (CSR_Polygon3*)csrMemoryAlloc(pPolygons->m_pPolygon,
sizeof(CSR_Polygon3),
pPolygons->m_Count + 1);
// succeeded?
if (!pPolygonBuffer)
return 0;
// update the polygon buffer
pPolygons->m_pPolygon = pPolygonBuffer;
++pPolygons->m_Count;
// copy the polygon content
if (!csrIndexedPolygonToPolygon(&pNode->m_pPolygonBuffer->m_pIndexedPolygon[i],
&pPolygons->m_pPolygon[pPolygons->m_Count - 1]))
return 0;
}
return 1;
}
// convert ray to geometric figure
ray.m_Type = CSR_F3_Ray;
ray.m_pFigure = pRay;
// node contains a left child?
if (pNode->m_pLeft)
{
// convert left box to geometric figure
box.m_Type = CSR_F3_Box;
box.m_pFigure = pNode->m_pLeft->m_pBox;
// check if ray intersects the left box
if (csrIntersect3(&ray, &box, 0, 0, 0))
// resolve left node
leftResolved = csrAABBTreeResolve(pRay, pNode->m_pLeft, deep + 1, pPolygons);
}
// node contains a right child?
if (pNode->m_pRight)
{
// convert right box to geometric figure
box.m_Type = CSR_F3_Box;
box.m_pFigure = pNode->m_pRight->m_pBox;
// check if ray intersects the right box
if (csrIntersect3(&ray, &box, 0, 0, 0))
// resolve right node
rightResolved = csrAABBTreeResolve(pRay, pNode->m_pRight, deep + 1, pPolygons);
}
return (leftResolved || rightResolved);
}This function will test which box the ray hits. It will repeat the test until find a leaf, in other words the smallest possible region hit by the ray. If several boxes are hit, their polygons will be added to the result. The function will returns a polygon list to test, which contains the polygons with which a collision with the ray is possible. The other polygons composing the mesh may be discarded.
There are many ways to react to a collision, but one of the most common (especially for games like FPS) is to calculate a new position for the model which would give the impression that the model slides against the obstacle it collides.
In a commercial game engine, the sliding may be a very complex task to perform, but a such effect may be not so complex to reach if simple objects like a sphere and a plane are used. It's this approach wich is retained when a sliding should be implemented with the CompactStar engine.
Consider the following situation:
On the above image, a sphere collider hits a wall after the player has moved forward. The current position is known, as well as the bounding sphere and the wall plane.
From there, a ray starting from the center of the bounding sphere (which should match with the current position), and oriented in the direction of the wall, may be calculated.
The point where the ray crosses the plane may be calculated.
Finally, the new position can be calculated by finding the point along the inverted center-to-plane ray located at the distance equals to the bounding sphere radius, from the calculated point on the plane.
Below is the implementation of this algorithm, available in the CSR_Collision.c and CSR_Collision.h files.
void csrSlidingPoint(const CSR_Plane* pSlidingPlane,
const CSR_Vector3* pPosition,
float radius,
CSR_Vector3* pR)
{
float distanceToPlane;
CSR_Plane plane;
CSR_Vector3 planeRatio;
CSR_Vector3 pointBeyondPlane;
CSR_Vector3 pointOnPlane;
CSR_Segment3 segment;
CSR_Figure3 segmentFigure;
CSR_Figure3 planeFigure;
plane = *pSlidingPlane;
// calculate the distance between the center of the sphere and the plane
csrPlaneDistanceTo(pPosition, &plane, &distanceToPlane);
// check if value is negative
if (distanceToPlane < 0.0f)
{
// invert the plane
plane.m_A = -plane.m_A;
plane.m_B = -plane.m_B;
plane.m_C = -plane.m_C;
plane.m_D = -plane.m_D;
}
// calculate the direction of the line segment position - plane
planeRatio.m_X = radius * plane.m_A;
planeRatio.m_Y = radius * plane.m_B;
planeRatio.m_Z = radius * plane.m_C;
// calculate who the line segment perpendicular to the plane, from the center
// of the sphere, cross the collision sphere. Normally this point is beyond
// the plane
pointBeyondPlane.m_X = pPosition->m_X - planeRatio.m_X;
pointBeyondPlane.m_Y = pPosition->m_Y - planeRatio.m_Y;
pointBeyondPlane.m_Z = pPosition->m_Z - planeRatio.m_Z;
// configure the line segment to test
segment.m_Start = *pPosition;
segment.m_End = pointBeyondPlane;
// build a figure containing the line segment
segmentFigure.m_Type = CSR_F3_Segment;
segmentFigure.m_pFigure = &segment;
// build a figure containing the plane
planeFigure.m_Type = CSR_F3_Plane;
planeFigure.m_pFigure = pSlidingPlane;
// calculate the point where the segment "center of the sphere - point beyond
// the plane" cross the collision plane
csrIntersect3(&segmentFigure, &planeFigure, &pointOnPlane, 0, 0);
// from point calculated above, add the sphere radius and return the value
pR->m_X = pointOnPlane.m_X + planeRatio.m_X;
pR->m_Y = pointOnPlane.m_Y + planeRatio.m_Y;
pR->m_Z = pointOnPlane.m_Z + planeRatio.m_Z;
}