Dóra Gavló

Collision detection III: Box-box collision

Published April 2nd, 2023
image

In the previous article, we covered the EPA method to obtain a single contact point. In this final installment of the series, we will explore a technique to obtain all contact points in one go, focusing exclusively on boxes. For those interested in other shapes, additional resources will be provided at the end of the article.

Overview

  1. What are boxes?
  2. The algorithm
  3. References & the complete code

What are boxes?

Before we start looking at algorithms it's worth to properly describe what shape we are working with. A box can refer to a shape both in 2D and 3D. In 3D it has 8 vertices and 6 faces that are at right angles with each other. Therefore, the minimum data we'd need for our calculations are the box's extents in all 3 dimensions and its position. However, to make our life easier we will also define the 8 vertices and the 6 face normals. 


	CVector3 position = GetTransform().getOrigin();
	CVector3 dimensions = GetDimensions();
	vertices[0] = GetTransform().getRotation() * 
		CVector3(position.getX() - dimensions.getX(), position.getY() - dimensions.getY(), position.getZ() - dimensions.getZ());
	vertices[1] = GetTransform().getRotation() * 
		CVector3(position.getX() - dimensions.getX(), position.getY() - dimensions.getY(), position.getZ() + dimensions.getZ());
	vertices[2] = GetTransform().getRotation() * 
		CVector3(position.getX() - dimensions.getX(), position.getY() + dimensions.getY(), position.getZ() + dimensions.getZ());
	vertices[3] = GetTransform().getRotation() * 
		CVector3(position.getX() - dimensions.getX(), position.getY() + dimensions.getY(), position.getZ() - dimensions.getZ());
	vertices[4] = GetTransform().getRotation() * 
		CVector3(position.getX() + dimensions.getX(), position.getY() + dimensions.getY(), position.getZ() + dimensions.getZ());
	vertices[5] = GetTransform().getRotation() * 
		CVector3(position.getX() + dimensions.getX(), position.getY() + dimensions.getY(), position.getZ() - dimensions.getZ());
	vertices[6] = GetTransform().getRotation() * 
		CVector3(position.getX() + dimensions.getX(), position.getY() - dimensions.getY(), position.getZ() + dimensions.getZ());
	vertices[7] = GetTransform().getRotation() * 
		CVector3(position.getX() + dimensions.getX(), position.getY() - dimensions.getY(), position.getZ() - dimensions.getZ());
	
	normals.push_back(GetTransform().getRotation() * CVector3(1.f, 0.f, 0.f)));
	normals.push_back(GetTransform().getRotation() * CVector3(0.f, 1.f, 0.f)));
	normals.push_back(GetTransform().getRotation() * CVector3(0.f, 0.f, 1.f)));
	normals.push_back(GetTransform().getRotation() * CVector3(-1.f, 0.f, 0.f)));
	normals.push_back(GetTransform().getRotation() * CVector3(0.f, -1.f, 0.f)));
	normals.push_back(GetTransform().getRotation() * CVector3(0.f, 0.f, -1.f)));

Planes
At the end of the algorithm we will also be working with planes. These can be defined by a single point and a normal vector. Aside from these values, we'll need two other functions: checking its distance from a point and its intersection with a line/edge.


Here's what the plane class looks like: 

	struct CPlane {
		CPlane() = default;
		CPlane(const CVector3& a_Normal, CVector3 a_Point) 
		{
			point = std::move(a_Point);
			normal = a_Normal;
		}

		CScalar DistanceToPoint(CVector3 a_Point) const { return normal.Dot(a_Point - point); }

		CVector3 Intersection(CVector3 p1, CVector3 p2) const {
			//Return the intersection point of a line passing two points and this plane
			return p1 + (p2 - p1) * (-DistanceToPoint(p1) / normal.Dot((p2 - p1)));
		};
		CVector3 normal;
		CVector3 point;

The algorithm

While in this section we're going to work with boxes, the same principle can also be applied to any convex hull. Thanks to EPA, by the time we start the algorithm we already have the contact normal. In this case, the penetration depth is not needed.

To summarize, in this algorithm we are going to find the two faces or edges (or in rare cases vertices) that are colliding. These are called the reference and incident faces. Then you take every side plane of the reference face and clip it against the incident face. The clipped points are your contact points.

Now let's take a closer look:

  1. Finding the incident and reference faces

    At the beginning of the algorithm, we should already have all vertices and face normals as outlined above. The easiest way to find the correct faces is simply by a dot product. If the dot product between the contact normal and a vertex is > 0 (at least in the case of a box) that means that that vertex is part of the face that constructs it Here, you can end up with 1, 2 or 4 points. These mean that you have either a vertex, edge or face contact respectively. We can retrieve the face normal either by calculating it on the spot using the cross product or by looking it up from your box class.


    Here's how it looks in code: 
    2. 
for (int i = 0; i < 8; i++)
	{
		dots[i] = local.Dot(m_ReferenceBox[i]);
	}
	CScalar max = *std::max_element(dots, dots + 7);
	for (int i = 0; i < 8; i++)
	{
		CScalar base = max - dots[i];
		if (base < static_cast(0.001) && base > -static_cast(0.001))
		{
			m_ReferenceFace.vertices.push_back(i);
		}
	}

  2. Select the side planes of the reference face

    These are the 4 sides you are going to clip against. Since we are already storing the face normals, we can easily find the ones that are perpendicular to it.



    
// Calculate the top point of the reference face by getting the transform origin of the first object in the collision and adding the reference face normal multiplied by the box dimensions
CVector3 top = m_Info->m_First->GetTransform().getOrigin() + (static_cast(m_Info->m_First->GetCollisionShape().get())->GetDimensions() * m_ReferenceFace.normal);

// Get the indices of the vertices of the reference face
std::vector& ref = m_ReferenceFace.vertices;

// Create a vector to store pairs of vertex indices
std::vector> pairs;

// For each combination of two vertices of the reference face, add the pair to the pairs vector
for(size_t i = 0; i < ref.size(); i++)
{
	for(size_t j = 0; j < ref.size();j++)
	{
		if(i != j)
		{
			pairs.emplace_back(ref[i], ref[j]);
		}
	}
}

// For each pair of vertices, calculate the middle point and the normal vector of the corresponding side plane
for (size_t i = 0; i < pairs.size(); i++) {
	// Calculate the middle point of the current pair of vertices
	CVector3 middle = (m_ReferenceBox[pairs[i].first] + m_ReferenceBox[pairs[i].second]) / 2;
	
	// Calculate the normal vector of the current side plane by subtracting the top point from the middle point
	CVector3 normal = middle - top;
	
	// Calculate the squared length of the normal vector
	CScalar length = normal.Length2();
	
	// If the length of the normal vector is greater than or equal to a small constant, add the side plane to the list of reference side planes
	if (length >= CEPSILON) {
		// Remove the pair from the pairs vector to prevent it from being used again
		pairs.erase(std::find(pairs.begin(), pairs.end(), std::pair(pairs[i].second, pairs[i].first)));
		
		// Normalize the normal vector
		normal.Normalize();
		
		// Add the side plane to the list of reference side planes
		m_RefSidePlanes.emplace_back();
		m_RefSidePlanes[m_RefSidePlanes.size() - 1].normal = normal;
		m_RefSidePlanes[m_RefSidePlanes.size() - 1].point = middle;
	}
}
    Code:
  3. Clip the side planes against the incident face

    This is the most important part. Here, you can use any clipping algoritm you'd like, but generally the Sutherland-Hodgeman one is used. Here, you should get 4, 2 or 1 contact point depending on the type of collision you're working with (face, edge or vertex). If the number is higher, for example you found 8 contact points for a face contact, you need to also clip against the reference face.

    Code: 
    4. CScalar distance[2]
CVector3 vertex[2];
std::vector input;
for(auto& verts : a_Face.vertices)
{
    input.push_back(a_Box[verts]);
}
// Create a vector to hold the vertices of the new face after clipping
std::vector new_face;

// Loop over all clipping planes
for (auto& plane : a_Planes)
{
    // Initialize the first vertex and its distance to the clipping plane
    vertex[0] = input[0];
    distance[0] = plane.DistanceToPoint(vertex[0]);

    // Loop over all input vertices
    for (size_t j = 1; j <= input.size(); j++) {
        // Compute the index of the next vertex (wrap around if at end)
        size_t next = j % input.size();

        // Get the next vertex and its distance to the clipping plane
        vertex[1] = input[next];
        distance[1] = plane.DistanceToPoint(vertex[1]);

        // Case 1: Both vertices are inside the clipping plane
        if (distance[0] <= 0.0f && distance[1] <= 0.0f || distance[0] > 0.0f && distance[1] > -CEPSILON && distance[1] < CEPSILON) {
            // Add the next vertex to the new face
            new_face.push_back(vertex[1]);
        }
        // Case 2: First vertex is inside and second vertex is outside
        else if (distance[0] > 0.0f && distance[1] < CEPSILON) {
            // Compute the intersection point between the plane and the edge
            // and add it to the new face, followed by the next vertex
            new_face.push_back(plane.Intersection(vertex[0], vertex[1]));
            new_face.push_back(vertex[1]);
        }
        // Case 3: First vertex is outside and second vertex is inside
        else if (distance[0] < CEPSILON && distance[1] > 0.0f) {
            // Compute the intersection point between the plane and the edge
            // and add it to the new face
            new_face.push_back(plane.Intersection(vertex[0], vertex[1]));
        }
        // Update the first vertex and its distance to the clipping plane
        vertex[0] = vertex[1];
        distance[0] = distance[1];
    }

    // If the new face is empty, it means the original face was entirely clipped
    // and there is nothing left to clip, so break out of the loop
    if (new_face.empty()) { break; }

    // Set the input vertices to the new vertices and clear the new face
    input = new_face;
    new_face.clear();
}
Wait, won't this only give me contact points on one body?

Yes. If you want contact points on the other body, you can simply switch up the reference and incident faces.

There are several ways to optimize this , for example by caching the results, however that's outside the scope of this article

References