In this chapter, we are going to cover how to check whether 3D shapes are intersecting. The following intersection tests will be covered:
Sphere to sphere
Sphere to AABB
Sphere to OBB
Sphere to plane
AABB to AABB
AABB to OBB
AABB to plane
OBB to OBB
OBB to plane
Plane to plane
In the last chapter, we covered how to test if a given point is intersecting any of the 3D primitives we have implemented so far. In this chapter, we take these intersections tests one step further by checking if any of the 3D primitives have intersected any other primitive. We will implement collision checks for all primitives.
The collision tests we write in this chapter can be used later to check if two objects intersect. Once we know objects intersect, we can respond to that intersection. Determining if objects intersect is very important to any physics engine.
To check if two spheres overlap, we check if the distance between them is less than the sum of their radii. We can avoid an expensive square root operation by checking the square distance between the spheres against the squared sum of their radii:
Checking if two 3D spheres intersect is very similar to checking if two 2D circles intersect. We are going to implement a new function to check if two spheres intersect. This is the simplest 3D intersection function we are going to write.
Follow the given steps to implement sphere-to-sphere intersection testing:
Declare the SphereSphere function in Geometry3D.h:
bool SphereSphere(const Sphere& s1, const Sphere& s2);
Implement the SphereSphere function in Geometry3D.cpp:
bool SphereSphere(const Sphere& s1, const Sphere& s2) {First find the sum of the radius of the two spheres:
float radiiSum = s1.radius + s2.radius;
Next find the squared distance between the two spheres:
float sqDistance =...
To check if a Sphere and an Axis Aligned Bounding Box (AABB) intercept, we must first find the closest point on the AABB to the Sphere. Once we have this point, we can figure out the distance between the Sphere and the closest point. Finally, we can compare this distance to the radius of the Sphere. If the distance between the closest point and the Sphere is less than the radius of the Sphere, the point is inside the Sphere:
Checking if a Sphere and an Oriented Bounding Box (OBB) intersect is very similar to checking if a Sphere and an AABB intersect. First, we find the closest point on the OBB to the Sphere. Next, we must find the distance between the center of the Sphere and the closest point. Finally, we compare the distance against the radius of the sphere. If the distance is less than the radius, we have an intersection:
We are going to implement a function to test if a Sphere and an OBB are intersecting. We will also create a #define macro to test the opposite. This new macro just switches the function name and argument order.
Follow the given steps to implement sphere to OBB intersection testing:
Declare SphereOBB in Geometry3D.h:
bool SphereOBB(const Sphere& sphere, const OBB& obb);
Declare OBBSphere in Geometry3D.h:
#define OBBSphere(obb, sphere) \ SphereOBB(sphere, obb)
Implement SphereOBB in Geometry3D.h:
bool SphereOBB(const Sphere& sphere, const OBB&...
To check if a sphere intersects anything you follow a simple formula. Find the closest point to the sphere on the shape and use this point to find the distance between the sphere and the shape. Compare the resulting distance to the radius of the sphere. If the distance is less than the radius, there is a collision. Checking if a sphere and plane intersect follows this same formula:
We are going to implement a function to test if a sphere and a plane are intersecting. We will also use a #define macro to implement convenience functions to see if a plane intersects a sphere. This macro just switches the function name and arguments around.
Follow the given steps to implement a sphere to plane intersection test:
Declare SpherePlane in Geometry3D.h:
bool SpherePlane(const Sphere& sphere, const Plane& plane);
Declare the PlaneSphere macro in Geometry3D.h:
#define PlaneSphere(plane, sphere) \ SpherePlane(sphere, plane)
Implement SpherePlane in Geometry3D...
Testing if two AABBs overlap involves performing an interval test on each of the world axes. To visualize this problem, let's consider what an interval test looks like on just one axis:
Given shapes A and B, we have an overlap only if the minimum of A is less than the maximum of B and the maximum of A is greater than the minimum of B. The actual overlap test would look something like this:
A.min <= B.max && a.max >= b.min
We can determine if two AABBs overlap by performing this test on the global X, Y, and Z axes.
We are going to implement a function to test if two AABBs are overlapping or not. This function will test for interval overlap on the global X, Y, and Z axis.
Testing if an AABB and an OBB overlap can be done using the Separating Axis Theorem (SAT). This test will require a total of 15 axes to be tested. Chapter 5, 2D Collisions, provides an in-depth explanation of how the SAT works. The 15 axes of potential separation are:
The three axes of the AABB (world X, Y, and Z)
The three axes of the OBB (the OBB's orientation matrix)
9 axes come from the cross-products of the three axes of the AABB and the three axes of the OBB. We take the cross product of every combination of these axes. Lists these nine combinations:
|
AABB.XAxis x OBB.XAxis |
AABB.YAxis x OBB.XAxis |
AABB.ZAxis x OBB.XAxis |
|
AABB.XAxis x OBB.YAxis |
AABB.YAxis x OBB.YAxis |
AABB.ZAxis x OBB.YAxis |
|
AABB.XAxis x OBB.ZAxis |
AABB.YAxis x OBB.ZAxis |
AABB.ZAxis x OBB.ZAxis |
Remember, the two shapes only overlap if all 15 axes overlap. If there is a single axis of separation, no intersection can happen.
An AABB does not intersect a plane if all four corners of the box are on the same side of the plane. A naive solution to this problem would be to get all eight corners of the plane as points, and then perform a half space test with every corner against the plane.
A better solution would be to use the GetInterval function we wrote in the AABB to OBB section of this chapter to get the interval of the box along the normal of the plane. Then, we just have to make sure that the min and max intervals of the AABB are both greater than 0, or less than 0. If the signs of the min and max are different, we have an intersection.
We are going to take a third, more optimal approach. We will project the half extents of the box onto the plane. Then, we will find the distance between the box and the plane. We find the distance between the box and the plane by measuring how far the projected box interval is from the origin along the normal. If the distance of the box from the plane is less than...
Like the AABB to OBB test, checking if two OBBs overlap is best done using the separating axis theorem. The actual SAT function will be very similar to the AABB to OBB test. Like AABB to OBB, there are 15 axes of potential separation to test. The 15 axes that we need to test are similar to AABB to OBB, except the first three axis are the orientation of the first OBB.
If we have two OBBs, A and B, we can find the 15 axes of potential separation between them as follows:
The first three axes of separation are the basis vectors of the orientation of the first OBB:
|
AABB.XAxis |
AABB.YAxis |
AABB.ZAxis |
The next three axes of separation are the basis vectors of the orientation of the second OBB:
|
B.XAxis |
B.YAxis |
B.ZAxis |
The last nine axes of separation are the cross products of every basis axis from both OBBs:
|
A.XAxis x B.XAxis |
A.YAxis x B.XAxis |
A.ZAxis x B.XAxis |
|
A.XAxis x B.YAxis |
A.YAxis x B.YAxis |
A.ZAxis x B.YAxis |
|
A.XAxis X B.ZAxis |
A.YAxis x B.ZAxis |
A.ZAxis x B.ZAxis |
Just like with the AABB, we know that an OBB does not intersect a plane if all of the OBB vertices are on the same side of the plane. The actual test to check if an OBB and plane intersect will be very similar to the AABB-to-Plane test:
We are going to implement a function to test if an OBB and a Plane intersect. This function will be similar to how we checked if an AABB and Plane intersected. We will project the OBB onto the normal of the plane and find the interval of this projection. If the interval contains the origin of the plane, we know we have an intersection.
Follow the given steps to find intersections between an OBB and a plane:
Declare OBBPlane in Geometry3D.h:
bool OBBPlane(const OBB&obb, const Plane& plane);
Dclare the PlaneOBB macro in Geometry3D.h:
#define PlaneOBB(plane, obb) \ OBBPlane(obb, plane)
Implement OBBPlane in Geometry3D.cpp:
bool OBBPlane(const OBB& obb, const Plane& plane) {
// Local variables for readability...Two planes intersecting results in an infinite line between the two planes:
We don't actually care about this line. We just want a true or false Boolean to know if the planes intersect. Two planes intersect if they are not parallel. If the normals of the plane point in different directions, the planes intersect. If the normals of the plane point in the same direction, they do not intersect.
We are going to implement a function to test if two planes intersect. This function will only return a Boolean result, not the line of intersection.
Follow the given steps to determine if two planes are intersecting:
Declare the PlanePlane function in Geometry3D.h:
bool PlanePlane(const Plane& plane1, const Plane& plane2);
Implement the PlanePlane function in Geometry3D.cpp:
bool PlanePlane(const Plane& plane1, const Plane& plane2) {Compute the direction of the intersection line
// Cross product returns 0 when used on parallel lines vec3 d = Cross(plane1...
© 2017 Packt Publishing Limited All Rights Reserved
