Oriented Bounding Boxes

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;
}



Create an account

Register a new account

• Forum Statistics

• Total Topics
627708
• Total Posts
2978732

• 21
• 14
• 12
• 22
• 35