Sign in to follow this  
Michael Lojkovic

How to Update OBB with MinAreaRect Algorithm

Recommended Posts

I've got an OBB implemented, and it works for calculating collisions.  The only issue I'm having with it is drawing the debug lines, so they give a correct visual representation of the box bounded by it.   Currently I'm calculating a 3 x 3 array based on a quaternion, saving it to a single dimension array of Vector3s and using that to figure out rotations.  


The array at the identity position ends up looking like:


[1, 0, 0]

[0, 1, 0]

[0, 0, 1]


I'm pretty sure my original matrix is correct, but I don't know how to use it for just updating my Debug lines indivisually.


A snippet for how I'm modifying the debug lines is this:

var xOrientation = orientationMatrix[0].x + orientationMatrix[1].x + orientationMatrix[2].x;
var yOrientation = orientationMatrix[0].y + orientationMatrix[1].y + orientationMatrix[2].y;
var zOrientation = orientationMatrix[0].z + orientationMatrix[1].z + orientationMatrix[2].z;

		new Vector3((center.x - HalfWidths.x) * xOrientation, (center.y + HalfWidths.y) * yOrientation,
			(center.z + HalfWidths.z) * zOrientation),
		new Vector3((center.x + HalfWidths.x) * xOrientation, (center.y + HalfWidths.y) * yOrientation,
			(center.z + HalfWidths.z) * zOrientation), Color.magenta);

How should I multiply the center values and / or halfwidths to rotate the lines with the box?  Would the MinAreaRect algorithm, discussed in Real Time Collision Detection accomplish the same thing?  I'm not sure what to do with the float returned from MinAreaRect.


Here's the code in MinAreaRect.

// Compute the center point 'c' and axis orientation oM[0] and oM[1], of
// the minimum area rectanble to the xy plane containing the points pt[]
float MinAreaRect(Vector2[] point, int numPoints, ref Vector2 c, ref Vector2[] oM)
	float minArea = float.MaxValue;

	// Loop through all edges; j trails i by 1, modulo numpts
	for (int i = 0, j = numPoints - 1; i < numPoints; j = i, i++)
		// Get current edge e0 (e0x, e0y), normalized
		Vector2 e0 = point[i] - point[j];

		// Get an axis e1 orthogonal to edge e0
		Vector2 e1 = new Vector2(-e0.y, e0.x); // = Perp2D(e0)

		// Loop through all point to get maximum extents
		float min0 = 0.0f, min1 = 0.0f, max0 = 0.0f, max1 = 0.0f;
		for (int k = 0; k < numPoints; k++)
			// Project points onto axes e0 and e1 and keep track
			// of minimum and maximum values along both axes
			Vector2 distance = point[k] - point[j];
			float dot = Vector2.Dot(distance, e0);
			if (dot < min0)
				min0 = dot;
			if (dot > max0)
				max0 = dot;
			dot = Vector2.Dot(distance, e1);
			if (dot < min1)
				min1 = dot;
			if (dot > max1)
				max1 = dot;
		float area = (max0 - min0)*(max1 - min1);

		// if best so far, remember area, center, and axes
		if (area < minArea)
			minArea = area;
			c = point[j] + 0.5f*((min0 + max0)*e0 + (min1 + max1)*e1);
			oM[0] = e0;
			oM[1] = e1;
	return minArea;

I was mainly trying to get the debug lines working with rotations, before seeing how MinAreaRect should work with my OBB class.

Share this post

Link to post
Share on other sites
Randy Gaul    2762

It looks to me like you just don't quite understand how rotation matrices can be used. Given memory for an array of 8 vertices you can place an OBB's verts into the array in the reference frame of the OBB. This means to take your half-extent vectors and form an AABB centered at the origin. Then you can take the model to world space transformation of your OBB and apply it to your 8 model space points.


Here's what this code might look like:

modelSpaceVerts[ 8 ]; // initialize as an AABB with half-extent vector from given OBB

for ( int i = 0; i < 8; ++i )
    modelSpaceVerts[ i ] = rotationMatrix * modelSpaceVerts[ i ] + centerOfOBB;

Then it's just a matter of drawing lines between each vertex. In my example I assumed the vertices are 3 component vectors, rotationMatrix is a 3x3 rotation matrix, and centerOfOBB is another 3 component vector. Be sure to look up how to multiply a vector by a matrix so you can properly apply your rotation.


Edit: I actually have this code written down here in a real example (q3Box::Render)

Edited by Randy Gaul

Share this post

Link to post
Share on other sites

Ok so, I just run MinAreaRect on two opposing faces, Update the center points, and adjust the matrix with it. Then the points would just fit where they've been rotated / moved to.  But, what would I do with the minimum Area of the rect, and how would i calculate the z coordinate / 3rd dimension?  

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this