[mmakrzem]

I'm creating my own physics engine and I'm a little confused how to imlement a proper collision detection and response algorithm that will allow me to stack boxes one on top of another.

Can someone point me in the right direction to do this?

My initial thoughts were to use each of the 8 corners on the box to figure out if one box collides with another, however if I have two boxes of the same size and I rotate one 45 degree wrt to the other and then stack them, neither box's vertices are touches any faces. Instead I am getting a pure face to face collision.

What is the method used to perform rigid body box stacking?

This post has been edited by mmakrzem: 18 January 2008 - 05:10 AM

[TheMagnitude]

You would check is any of the vertices of other bodies lie inside any other bodies. This can be done with a formula, I can't find the formula at the moment but I'll report back to you when I build a formula.

When you know how to check if any collisions are happening as stated above, you would use the velocity (of each object) to work out how much the reaction force is (again not sure how). You would then apply the reaction forces to the boxes and sandbox it up. You may also need to find out things about areal velocity.

[Tom9729]

Google for "bounding boxes" or "bounding spheres". I'm working on the same thing and I went with bounding spheres just because it's easier.

My code generates bounding spheres from triangles (models are typically made up of lots of triangles).

#include <stdlib.h>
#include <memory.h>
#include <math.h>

/* A 3d vector. */
typedef double vec3_t[3];

/* A 3d triangle. */
typedef vec3_t triangle3_t[3];

/* A bounding sphere. */
typedef struct
{
		vec3_t cc; /* Circumcenter of the sphere. */
		float rad; /* Radius of the sphere. */
} b_sphere_t;

/*
 * Get a bounding sphere from a 3d triangle.
 *
 * Params:
 * tri : The triangle.
 *
 * Return:
 * A bounding sphere.
 */
b_sphere_t* get_b_sphere(triangle3_t tri)
{
		b_sphere_t* bsp;
		vec3_t midpts[2];
		vec3_t temp;
		float side_len[3];
		float rad;

		bsp = malloc(sizeof(b_sphere));

		/* Calculate the length of each side of the triangle. */
		temp[0] = tri[0][0] - tri[1][0];
		temp[1] = tri[0][1] - tri[1][1];
		temp[2] = tri[0][2] - tri[1][2];

		side_len[0] = sqrt(pow(temp[0], 2) + pow(temp[1], 2) + pow(temp[2], 2));
		temp[0] = tri[0][0] - tri[2][0];
		temp[1] = tri[0][1] - tri[2][1];
		temp[2] = tri[0][2] - tri[2][2];

		side_len[1] = sqrt(pow(temp[0], 2) + pow(temp[1], 2) + pow(temp[2], 2));
		temp[0] = tri[1][0] - tri[2][0];
		temp[1] = tri[1][1] - tri[2][1];
		temp[2] = tri[1][2] - tri[2][2];

		side_len[2] = sqrt(pow(temp[0], 2) + pow(temp[1], 2) + pow(temp[2], 2));
		/* Calculate the radius of the circumcircle. */
		rad = 2 * side_len[0] * side_len[1] * side_len[2];
		rad /= sqrt((side_len[0] + side_len[1] + side_len[2]) * (side_len[0]
						- side_len[1] + side_len[2]) * (side_len[1] - side_len[2]
						+ side_len[0]) * (side_len[2] - side_len[0] + side_len[1]));
		rad /= 2;

		/* Midpoint of the line between vertices 1 & 2. */
		midpts[0][0] = (tri[0][0] + tri[1][0]) / 2;
		midpts[0][1] = (tri[0][1] + tri[1][1]) / 2;
		midpts[0][2] = (tri[0][2] + tri[1][2]) / 2;

		/* Midpoint of the line between the above midpoint, and vertex 3. */
		midpts[1][0] = (midpts[0][0] + tri[2][0]) / 2;
		midpts[1][1] = (midpts[0][1] + tri[2][1]) / 2;
		midpts[1][2] = (midpts[0][2] + tri[2][2]) / 2;

		/* Set the circumcenter. */
		bsp->cc[0] = midpts[1][0];
		bsp->cc[1] = midpts[1][1];
		bsp->cc[2] = midpts[1][2];

		/* Set the radius. */
		bsp->rad = rad;

		return bsp;
}

/*
 * Test if two bounding spheres are in a collision.
 *
 * Params:
 * b1 : The first sphere.
 * b2 : The second sphere.
 * loc1 : Location of the first sphere.
 * loc2 : Location of the second sphere.
 *
 * Return:
 * 1 if there is a collision.
 */
int b_sphere_collision(b_sphere_t b1, b_sphere_t b2, vec3_t loc1, vec3_t loc2)
{
		float temp[3];
		float dist;
		float sum;

		/* Translate both bounding spheres to their real locations. */
		for (int i = 0; i < 3; i++)
		{
				b1.cc[i] += loc1[i];
				b2.cc[i] += loc2[i];
		}

		/* Find the distance between the two circumcenters. */
		for (int i = 0; i < 3; i++)
		{
				temp[i] = b1.cc[i] - b2.cc[i];
		}

		dist = sqrt(pow(temp[0], 2) + pow(temp[1], 2) + pow(temp[2], 2));

		/* Find the sum of the radii. */
		sum = b1.rad + b2.rad;

		/* If the distance is less than or equal to the sum of the radii,
		 * the two spheres are colliding. */
		if (dist <= sum)
		{
				return 1;
		}

		/* Or not. */
		else
		{
				return 0;
		}
}

I do not guarantee that the above is the best way of doing that, and my methods haven't really been refined yet. This is probably overkill for what you want to do, but I figure it might help nonetheless.

[mmakrzem]

TheMagnitude, on 18 Jan, 2008 - 10:23 AM, said:

You would check is any of the vertices of other bodies lie inside any other bodies. This can be done with a formula, I can't find the formula at the moment but I'll report back to you when I build a formula.

When you know how to check if any collisions are happening as stated above, you would use the velocity (of each object) to work out how much the reaction force is (again not sure how). You would then apply the reaction forces to the boxes and sandbox it up. You may also need to find out things about areal velocity.

Checking to see if the vertices are inside the other body is not sufficient for stacking, as I mentioned in my original post. Picture two boxes of the same size. stacked one on top of the other. Ie box1 is below box2 and box 2 is 1 unit in the Y axis above box 1. Now if you rotate box 2 about the y axis by 45 degrees, none of box 2's vertices will now touch box 1. as a result, all vertices will appear to be outside of box1 even though there supposed to be a collision between box 2's bottom face and box 1's top face.

[TheMagnitude]

mmakrzem, on 21 Jan, 2008 - 08:19 PM, said:

TheMagnitude, on 18 Jan, 2008 - 10:23 AM, said:

You would check is any of the vertices of other bodies lie inside any other bodies. This can be done with a formula, I can't find the formula at the moment but I'll report back to you when I build a formula.

When you know how to check if any collisions are happening as stated above, you would use the velocity (of each object) to work out how much the reaction force is (again not sure how). You would then apply the reaction forces to the boxes and sandbox it up. You may also need to find out things about areal velocity.

Checking to see if the vertices are inside the other body is not sufficient for stacking, as I mentioned in my original post. Picture two boxes of the same size. stacked one on top of the other. Ie box1 is below box2 and box 2 is 1 unit in the Y axis above box 1. Now if you rotate box 2 about the y axis by 45 degrees, none of box 2's vertices will now touch box 1. as a result, all vertices will appear to be outside of box1 even though there supposed to be a collision between box 2's bottom face and box 1's top face.

Update the vertices when it rotates, then a collision would occur. Check for collisions all the time (i know thats slow but its all i can think off at the moment) , and apply correct reaction forces to each box etc when a collision is detected.

[mmakrzem]

TheMagnitude, on 29 Jan, 2008 - 03:02 PM, said:

Update the vertices when it rotates, then a collision would occur. Check for collisions all the time (i know thats slow but its all i can think off at the moment) , and apply correct reaction forces to each box etc when a collision is detected.

Hmmm, I don't think I'm making myself clear. Imaging two triangles laying parallel to one another. One triangle has vertices at
(0.707, 0.707, 0), (-0.707, 0.707, 0), (0, -1, 0)

the other at
(0.707,-0.707, 1), (-0.707,-0.707, 1), (0, 1, 1)

If we take the triangle at z=0 and start sliding it along the +ve Z direction it will go right through the other triangle. In the process, no vertices from one triangle will lie inside the other triangle.

The same thing can happen when stacking boxes. Any idea how to best handle this case?