Sign in to follow this  

Oriented Bounding Boxes

This topic is 4490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I've been developing a class for Obb and ObbTrees, I recently changed the way the covarience matrix is calculated to a method outlined here because of some alignment issues I was having. Prior to this I was simply calculating the mean of the vertices and subtracting that from all the points to calculate the matrix and it did a fairly good job of aligning the box except when the convex hull contained some dense patches of vertices. However, now in cases where there were no problems I am having some. The box does bound the object, however the rotation of the box does not properly bound using the smallest volume. I feel that the problem may lie somewhere in this code but I'm not sure, it feels like i've been staring at it forever so I'd appreciate any assistance anyone can give me.
void CObb::Construct(CPolygon *pPolygon)
{
	CVector vec0, vec1, vec2, Mi;
	float *fvec0 , *fvec1  , *fvec2, 
	       *fMi   , *fMHull , *fCovariance, 
	       fATotal, fAi;

	CHull->CreateConvexHull(pPolygon->GetPoints(), pPolygon->GetNumPoints());
	CPolygon *pPoly = CHull->GetPolygon();
	
	Matrix3X3 Covariance, Eigen; 
	Covariance.Zero();
		
	CVector   MHull   = vCenter = CentroidHull(pPoly);     // the centroid of the convex hull
	CVector * pPoints = pPoly->GetPoints();		// pointer to the points of the convex hull
	UINT    * pIndis  = pPoly->GetIndices();		// pointer to the indis ""

	fMHull		= &MHull.x;
	fATotal		= SumA(pPoly);
	fCovariance	= &Covariance._11;
	
	for(int j = 0; j < 3; j++)
	{
		for(int k = 0; k < 3; k++)
		{
			for(int i = 0; i < pPoly->GetNumIndis(); i+= 3)
			{
				vec0  = pPoints[pIndis[i+0]];	// the first point of the ith triangle
				vec1  = pPoints[pIndis[i+1]];	// the second point of the ith triangle
				vec2  = pPoints[pIndis[i+2]];	// the third point of the ith triangle
				Mi    = M(i/3, pPoly);			// the centroid of the ith triangle
				fAi   = A(i/3, pPoly);			// the area of the ith triangle

				// store the vectors as float arrays for simple component access
				fvec0  = &vec0.x;
				fvec1  = &vec1.x;
				fvec2  = &vec2.x;
				fMi    = &Mi.x;
				
				// add this to the matrix
				fCovariance[j*3 + k] += fAi*(fMi[j]*fMi[k]*9 + fvec0[j]*fvec0[k] + fvec1[j]*fvec1[k] + fvec2[j]*fvec2[k])/12 - fMHull[j]*fMHull[k]*fATotal;
			}
		}
	}

	// get the Covariance's eigenvector matrix
	// and extract the column vectors from it
	Eigen = Covariance.GetEigenMatrix();
	vA0   = Eigen.GetColumnVector(0);
	vA1   = Eigen.GetColumnVector(1);
	vA2   = Eigen.GetColumnVector(2);

	CalcAxisExtents(pPoly);
}

void CObb::CalcAxisExtents(CPolygon * pPolygon)
{
	// create 3 planes each using an axis vector as its normal
	CPlane plane0;
	plane0.Set(vA0, vCenter);
	
	CPlane plane1;
	plane1.Set(vA1, vCenter);
	
	CPlane plane2;
	plane2.Set(vA2, vCenter);

	// find the point furthest from each of the planes
	for(int i = 0; i < pPolygon->GetNumPoints(); i++)
	{
		float dist0 = fabs(plane0.Distance(pPolygon->GetPoints()[i]));
		float dist1 = fabs(plane1.Distance(pPolygon->GetPoints()[i]));
		float dist2 = fabs(plane2.Distance(pPolygon->GetPoints()[i]));

		if(dist0 > fA0)
			fA0 = dist0;

		if(dist1 > fA1)
			fA1 = dist1;

		if(dist2 > fA2)
			fA2 = dist2;
	}
	fA0 /= 2.0f;
	fA1 /= 2.0f;
	fA2 /= 2.0f;
}

// calculates the centroid of the entire hull
CVector CObb::CentroidHull(CPolygon * pPoly)
{
	float SumofA = SumA(pPoly);
	CVector Centroid(0,0,0);
	for(int i = 0; i < pPoly->GetNumIndis()/3; i++)
	{
		Centroid += M(i, pPoly) * A(i, pPoly);
	}
	return Centroid/SumofA;
}

// calculates the centroid of the ith triangle of the mesh
CVector CObb::M(int i, CPolygon * pPoly)
{
	CVector *pPoints = pPoly->GetPoints();
	UINT	*pIndis  = pPoly->GetIndices();
	CVector  Vec[]   = { pPoints[pIndis[i*3 + 0]], 
			     pPoints[pIndis[i*3 + 1]],
			     pPoints[pIndis[i*3 + 2]]};


	return (Vec[0] + Vec[1] + Vec[2])/3;
}

// calculates the area of the ith triangle
float CObb::A(int i, CPolygon * pPoly)
{
	CVector v01, v02, Cross;
	CVector *pPoints = pPoly->GetPoints();
	UINT	*pIndis  = pPoly->GetIndices();
	CVector  Vec[]   = { pPoints[pIndis[i*3 + 0]], 
			     pPoints[pIndis[i*3 + 1]],
			     pPoints[pIndis[i*3 + 2]]};

	v01 = Vec[0] - Vec[1];
	v02 = Vec[0] - Vec[2];

	Cross.Cross(v01, v02);

	return Cross.GetLength()/2;
}

// calculates the total area of the polygon
float CObb::SumA(CPolygon * pPoly)
{
	float Sum = 0;
	for(int i = 0; i < pPoly->GetNumIndis()/3; i++)
	{
		Sum += A(i, pPoly);
	}
	return Sum;
}


Share this post


Link to post
Share on other sites

This topic is 4490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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