Hey all,

So I'm working on a rigid-body physics engine, it's supposed to be easily compatible with Ogre and fairly straightforward to use, for beginning game programmers.

I'm working on collision detection and contact resolution, and have gotten stuck at checking to see if two cubes (rectangular prisms, strictly speaking) are colliding.

The approach I'm taking is to check for point-face collision (when a corner point of the cube is inside the other cube) and edge-edge collision (when two edges are touching), as the other types are negligible and will likely become another type of contact in the next frame anyways.

Point-face collision is easy, but edge-edge collision is tricky. How do I check to see if two of the edges of a cube are colliding?

My cube data structure is something like this:

// Vect3 is a struct containing an x, y, and z elements, also equipped with normal vector operations like
//  getMagnitude, Normalize, scalar and vector products, etc.

class Box : public Geometry {
private:
	Vect3 m_halfSize; // Half-size in x, y, z coordinates
        // The Geometry class is equipped with a transform matrix to transform
        //  world coordinates into the object's local coordinates.

public:
	// ...

	// Returns true if this box is touching the given sphere.
	virtual bool isTouching(Sphere* s) const;

	// Returns true if this box is touching the given box.
	virtual bool isTouching(Box* b) const;

	// virtual unsigned int GenerateContacts(Sphere* s) = 0;
	// virtual unsigned int GenerateContacts(Box* b) = 0;
};

Really I just need the math behind this, I've looked online but can't find anything useful.

In the past I used the separating axis theorem to partition space in 9 pieces.

By ranking all the points of the cube you could easily tell if a collision NOT happened. Extracting the collision data was a bit more involved but doable as a narrowphase.

I am concerned however you want to "a rigid-body physics engine, it's supposed to be easily compatible with Ogre and fairly straightforward to use, for beginning game programmers". Please. Please. Please, do not write yet another physics middleware. For your own amusement I could let you go but for serious use, your embarking on a seriously difficult project. If you plan to go ahead, I suggest to look at Bullet implementation.

Precise edge-to-edge collision can be done by forming vectors for each edge (endpoint1 - endpoint2). Determine if there is a solution for a common point for any 2 lines (one from each object). If there is a solution, determine if that point is bounded by the endpoints. However, with moving objects and floating point variables, it's very unlikely that process will ever yield results. Further, applying an epsilon to that algorithm can be tricky.

A better approach (probably your point-face collision) may be to calculate the intersection of a vector (formed by the edge of one object) with the planes of the other object (the old "point in a plane" calc). Determine if the intersection point is bounded by the plane. You don't mention whether you use culling in your point-face collision, but that can be done by dotting the vector with the plane normal and discarding anti-parallel vectors. That can cause misses depending on the speed and size of the objects.

That's for edge-collision detections. You can also look at swept-volumes for both objects.

If make the vectors functions of time, you can also determine the time of intersection and determine if the time is within the current frame (assuming your engine takes object speed into account). That's a more common approach for collisions, in any case, as fixed-time calcs (though easier to perform) don't provide adequate collision detection in a dynamic environment.

EDIT: As a learning exercise, looking at the source code for some collision engines would probably provide you with a lot of information. I don't know if Bullet is open source, but I have used ODE.

Cool, thanks all.

Also, yeah, this isn't for end-use - it's more of a pet project than anything else. I'm planning to tailor it for individual games down the road, but it definitely isn't meant to compete with Bullet, PhysX and all the other major engines out there. I do want to be able to point other new game programmers to it to show how to do simple things, which is why I'm trying to make it agree with Ogre. It's pretty much done, except for contact detection and resolution - which I know is like saying a building is finished, except the interior.

It's pretty much done, except for contact detection and resolution - which I know is like saying a building is finished, except the interior.

Actually... that's all there is in a physics engine. I assume you mean you have a broadphase method, and are now working on a narrowphase/exact detection, followed by responses. It's tricky to do right, and checking edge-Edge collisions is going to get unwieldy very quickly. I'd strongly suggest you look at either the Seperating Axis Test, or the GJK algorithm. Note that once you get a boolean collision response, you need to know the collision points and penetration depth. Dealing with multiple colliding bodies is another pain, as is friction. You are only scratching the surface of this.

Well, to all future readers, I solved my problem. It's definitely not optimized, but I at least have the math down. Thought I'd post this in case anybody else had the same question.

Given two cubes with properties (a) position in world space (b) orientation in world space (c) length, width, and height (not necessarily all the same length), identify vertices which can be potentially colliding.

The basic idea: to test two edges for collision: $\alpha$

Vertices of first edge (in world coordinates):

Vertices of second edge (in world coordinates):

Vector representing length of first edge (in local edge coordinates):

Vector representing length of second edge (in local edge coordinates):

If you can find the point on the two edges closest to each other, you can then find if they are interpenetrating, in contact, or not interpenetrating. The closest points on each edge can be represented as a vector representing length of edge (in local edge coordinates): and , where the alpha values are unknowns that we will be solving for. If the edges are candidate for collision at all, the alpha values must both be in the range [0, 1].

The condition that you're looking for is:

and , pretty much saying that the line between the two closest points selected must be orthogonal to both edges.

Anyways, do a lot of shifting things around, as Gil Strang says, solving this problem is just a matter of moving parenthesis around. Eventually you get this:

You can solve that using any variety of methods, Gauss-Jordan elimination, or as I'm going to end up doing it, just a closed-form formula.

So, now you have two alpha values. You can then form a distance vector . Also, one last thing, I'll call the vector pointing from the center of the first box to the center of the second box .

Conditions of no contact:

In the case that the final condition is false, there is a contact generated, with the contact normal being the unit vector of negative c, and the magnitude being the magnitude of c.

OPTIMIZATIONS:

--Separating axis theorem can check to see if we can guarantee the boxes are not colliding. Make a coarse check that can cut out doing all the math if we can easily prove the boxes as not touching.

--Watch out for the case of infinite solutions, where the two edges are parallel. In that case, arbitrarily pick the alpha values to be 0.5.

--Only consider edges that are formed by vertices which are in the direction of the other cube from the center of the first cube. This can easily be tested using the scalar product of the positions of the vertices in local coordinates of the first cube compared to the difference between the world origin of the second cube and the world origin of the first cube.

Goodness me, I thought the LaTeX stuff would work here. My apologies, all. I guess I'll try again tomorrow, when it's not the middle of the night and I'm tired.