In this chapter, we are going to cover linear intersections with 3D primitives. A linear intersection is a Raycast or line segment test. We will be covering the following tests:
Raycast Sphere
Raycast Axis Aligned Bounding Box
Raycast Oriented Bounding Box
Raycast plane
Linetest Sphere
Linetest Axis Aligned Bounding Box
Linetest Oriented Bounding Box
Linetest plane
In this chapter, we are going to test if rays or line segments intersect primitives. The primitives that we are going to test against are Sphere, Axis Aligned Bounding Box (AABB), Oriented Bounding Box (OBB), and plane. Raycast intersections will return the distance along the ray that the intersection has happened. Line segment intersections will simply return a Boolean value.
Raycasting is one of the most powerful tools we have. Let's assume for example that you want to make sure a character always stands on the ground. You could cast a ray down on the negative Y axis, where the ray hits the ground you place the character. This technique is often referred to as ground clamping.
Given a ray with origin o, indirection d and a sphere with origin c and radius r; we want to check if the ray ever intersects the sphere:
If the ray intersects the sphere, this intersection will happen at some distance along the ray. Within the context of ray casting, we often assume it takes one second to travel one unit along the ray. Because of this, distance and time are often used interchangeably.
Because of this ambiguity with the vocabulary, many resources might say that the ray intersects the sphere at some time, t. If the ray does not intersect the sphere, t is undefined.
We are going to implement a function to check if a ray and a sphere intersect. This function will return t, the time along the ray at which the intersection takes place. If there is no intersection, we will set t to be a negative number.
Any ray that intersects an AABB will do so twice. The first intersection is where the ray enters the AABB; the second is where the ray exists. If we know both intersection points, the point closest to the origin of the ray is the intersection point.
We can simplify finding the intersections points by visualizing the problem top down. Looking only at the X and Y axis. In this example, the AABB is represented by two slabs. The intersections of the slabs form four planes. These planes represent the faces of the AABB. We cast a ray and check if it's intersecting the X slab:
We found two points as a result of testing the ray intersection against the X slab. We call the near point 
and the far point 
. We repeat the same intersection against the Y slab:
We now have two more points, 
and 
. The ray enters the Y slab, and then leaves the Y slab. Next, the ray enters the X slab, and then leaves the X slab. There is no intersection. We can prove this, the greatest minimum...
We can extend the same slab method used for raycasting against an AABB to also work with an OBB. The key difference is how we find the values of 
and 
.
We are going to implement a function that finds the entry and exit points of a Raycast against an OBB. This function will only return the entry point. The function returns a scalar value t. This scalar value is the time along the ray at which the intersection happened. If the intersection is invalid, a negative number is returned.
Follow these steps to implement raycasting against an OBB:
Declare the Raycast function in Geometry3D.h:
float Raycast(const OBB& obb, const Ray& ray);
Start implementing the Raycast function in Geometry3D.cpp by declaring a few local variables to keep the code readable. We want to store the half extents of the box as a linear array, and each axis of the OBBs rotation frame as a vector:
float Raycast(const OBB& obb, const Ray& ray) {
const float...To Raycast against a plane we must find a point which is on the plane being cast against and also along the normal of the ray. We know a point is on the surface of a plane if it satisfies the plane equation. If no point along the ray satisfies the plane equation, the ray and plane do not intersect:
We are going to implement a function that performs a Raycast against a plane. This function will return t, the time along the ray at which it intersects the plane. If there is no intersection, the value of t will be negative.
Follow these steps to implement raycasting against a plane:
Declare the Raycast function in Geometry3D.h:
float Raycast(const Plane& plane, const Ray& ray);
Implement the Raycast function in Geometry3D.cpp:
float Raycast(const Plane& plane, const Ray& ray) {
float nd = Dot(ray.direction, plane.normal);
float pn = Dot(ray.origin, plane.normal);The nd variable must be less than zero for the ray to intersect the plane....
Unlike a Raycast, when we perform a linetest we only care about a Boolean result. To check if a Line and Sphere are intersecting, we need to find the closest point to the center of the Sphere on the Line. If the distance between the closest point and the center of the Sphere is less than the radius of the Sphere, the shapes intersect:
We are going to implement a function to check if a Line and a Sphere intersect. This function will return a Boolean result. We will avoid the square root involved in finding the distance between the two points by checking the squared distance.
Follow these steps to implement line testing against a sphere:
Declare the Linetest function in Geometry3D.h:
bool Linetest(const Sphere& sphere, const Line& line);
Implement the Linetest function in Geometry3D.h:
bool Linetest(const Sphere& sphere, const Line& line) {
Point closest = ClosestPoint(line, sphere.position);
float distSq = MagnitudeSq(sphere.position...We can use the existing Raycast against the AABB function to check if a line intersects an AABB. Given a line segment with end points A and B, we can create a ray out of the line:
ray.origin = A ray.direcion = Normalized(B - A);
With this ray, we can perform a Raycast. If the ray intersects the AABB, we check to make sure that the value of t is less than the length of the line. If it is, the segment intersects the Bounding Box:
Rays and Line segments are similar. The slab test for raycasting and the slap test to see if a Line and OBB intersect are almost the same. The only thing a linetest does different from a Raycast is it normalizes the result of the t value to the length of the line segment.
Because the two tests are so similar, we are going to build the linetest using the existing Raycast against the OBB function. Comparing the squared value of t against the squared length of the line segment is more efficient than normalizing t to the length of the Line.
We are going to implement a function to check if a Line segment and an OBB intersect. This function will return a Boolean result. The linetest function is going to build a ray out of the line and use the existing Raycast against the OBB function.
A Line segment represented by end points A and B can be parametrically expressed as follows:
S(t) = A + t(B-A) where 
We can check if a line segment intersects a Plane by substituting the parametric equation of the Line into the Plane equation. If any point along the line at time t exists that satisfies the Plane equation, the Line segment and Plane intersect:
We are going to implement a function to test if a Line segment and a Plane intersect. This function will return a Boolean result.
Follow these steps to implement line testing against a plane:
Declare the Linetest function in Geometry3D.h:
bool Linetest(const Plane& plane, const Line& line);
Implement the Linetest function in Geometry3D.cpp:
bool Linetest(const Plane& plane, const Line& line) {
vec3 ab = line.end - line.start;
float nA = Dot(plane.normal, line.start);
float nAB = Dot(plane.normal, ab);
// If the line and plane are parallel, nAB will be 0
// This will...
© 2017 Packt Publishing Limited All Rights Reserved
