Sign in to follow this  
Enrico

Using PCA for OBB construction gives wrong plane distances, but correct normals

Recommended Posts

Enrico    316
Hi, I am currently trying to implement OBB construction with the method described in Eric Lengyel's book. This method uses PCA to calculate the natural axes R, S and T. This set of natural axes seems to be correct: The average extents in each three directions are calculated with:
extentR = (minPDotR + maxPDotR) / 2.0;
extentS = (minPDotS + maxPDotS) / 2.0;
extentT = (minPDotT + maxPDotT) / 2.0;
minPDotR and maxPDotR are the maximum and minimum values between the axis R and all points in the mesh. Finally the obb's center is calculated with:
center = extentR * R + extentS * S + extentT * T;
This gives: As you can see, the axes have the wrong lengths (and the length values are used as distance for the obb planes).
Vec3 maxD(-FLT_MAX, -FLT_MAX, -FLT_MAX), minD(FLT_MAX, FLT_MAX, FLT_MAX);

for(Uint32 v=0; v < shape->nVertices(); v++)
{
	const Point &p = shape->getPosition(v);
	float dot1 = R.x*p.x + R.y*p.y + R.z*p.z;
	float dot2 = S.x*p.x + S.y*p.y + S.z*p.z;
	float dot3 = T.x*p.x + T.y*p.y + T.z*p.z;

	maxD.x = max(dot1, maxD.x);
	maxD.y = max(dot2, maxD.y);
	maxD.z = max(dot3, maxD.z);

	minD.x = min(dot1, minD.x);
	minD.y = min(dot2, minD.y);
	minD.z = min(dot3, minD.z);
}
maxD should hold the maximum dot product between all points and R,S and T and the same for minD. I have no idea what might be wrong :-( Any ideas? Thanks, Enrico

Share this post


Link to post
Share on other sites
Dave Eberly    1173
Quote:
Original post by Enrico

center = extentR * R + extentS * S + extentT * T;

[/code]


I have not looked at Eric's book on this topic. What caught my attention in your post is that the left-hand side "center" is a point and the right-hand side is a vector (a linear combination of vectors). The "units" do not match :)

It seems to me that the average of the input points is an initial guess for the center of the OBB, and then you have to update this average based on the extents and the eigenvectors.

Share this post


Link to post
Share on other sites
Enrico    316
Quote:
Original post by Dave Eberly
Quote:
Original post by Enrico

center = extentR * R + extentS * S + extentT * T;

[/code]


I have not looked at Eric's book on this topic. What caught my attention in your post is that the left-hand side "center" is a point and the right-hand side is a vector (a linear combination of vectors). The "units" do not match :)

Actually, I am multiplying and adding the single components of the vectors to get the center point. I just did not want to post the complete code here, so I simplified it ;-)

Quote:
It seems to me that the average of the input points is an initial guess for the center of the OBB, and then you have to update this average based on the extents and the eigenvectors.

I am using the mean of the given points to calculate the covariance matrix. This matrix is then used to calculate the eigen values and - vectors.

Any further ideas?

Thanks, Enrico

Share this post


Link to post
Share on other sites
oliii    2196
I'd start again, and look at the Min and Max points (in the local space : Max.x = max(P[] . R), Max.y = max(P[] . S), ...).

if you have min / max, then centre is

C_local = (Max + Min) * 0.5f;
E_local = (Max - Min) * 0.5f;

C = C_local.x * R + C_local.y * S + C_local.z * T; // in world space
extentR = E_local.x;
extentS = E_local.y;
extentT = E_local.z;

Share this post


Link to post
Share on other sites
Dave Eberly    1173
Quote:
Original post by Enrico
Any further ideas?


Look at my implementation? The Containment page at my geometrictools.com site has a file Wm4ContBox3.cpp and a function ContOrientedBox that computes the mean, the covariance matrix, and finally the OBB.

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