hi, I have a set of points and 3 normal vectors(n1,n2,n3) which can be anything but parallel. These 3 normal vectors represent 3 planes containing the origin. The min and max distances of all points to the 3 planes are evaluated and used as offsets for the 3 planes from the origin which gives me 6 planes: 0 = (n1*x) - min1; 0 = (n1*x) - max1; ... 0 = (n3*x) - max3; These 6 planes form a parallelepiped that encloses all points. What I'm looking for is the midpoint of this parallelepiped. My attempt is the following (which is apparently wrong): o = 0.5*(min1+max1)*n1 + 0.5*(min2+max2)*n2 + 0.5*(min3+max3)*n3 It seems this equation only gives me the right midpoint if the normal vectors are orthogonal. Do you know how to calculate the midpoint of such a parallelepiped ? thanks, quak [Edited by - Quak on October 3, 2006 10:34:54 AM]

Quote:Original post by Quak
hi,

I have a set of points and 3 normal vectors(n1,n2,n3) which can be anything but parallel. These 3 normal vectors represent 3 planes containing the origin.
The min and max distances of all points to the 3 planes are evaluated and used as offsets for the 3 planes from the origin which gives me 6 planes:

d = n1 + min1;
d = n1 + max1;
...
d = n3 + max3;

What are those equations? I don't know what d is, and "n1 + min1" seems to be a vector plus a number, which makes no sense to me.

Sorry, my mistake. I corrected the plane equations.

Quote:Original post by Quak
My attempt is the following (which is apparently wrong):

o = 0.5*(min1+max1)*n1 + 0.5*(min2+max2)*n2 + 0.5*(min3+max3)*n3

It seems this equation only gives me the right midpoint if the normal vectors are orthogonal.

How do you know it isn't giving the right midpoint for the non-orthogonal cases? For what it's worth, the equation feels intuitively correct to me (I'm not very good at picturing 3D parallelepipeds but it seems to work on 2D parallelograms, of which the former are just a dimensional extension).

The brute force approach is to calculate the corners of the parallelepiped and find the center of mass (same as the midpoint when the weights are equal). You could then use this to verify the equation.

Your formula is correct. Nothing in this problem involves a metric at all. Baricenters are an affine concept, so the orthogonality of the three vectors doesn't matter.

Despite the claim otherwise, your formula is not correct as you noted. To motivate the solution, look at the 2D problem with a parallelogram. You have four edges defined by the lines n1*x = min1, n1*x = max1, n2*x = min2, and n2*x = max2, where n1 and n2 are unit-length vectors but not necessarily perpendicular. The two lines passing through the center c are n1*x = (min1+max1)/2 and n2*x = (min2+max2)/2. The center c must satisfy both equations.

Write c = y1*n1 + y2*n2. Substitute this into the two line equations. The first produces y1 + (n1*n2)*y2 = (min1+max1)/2. The second produces (n1*n2)*y1 + y2 = (min2+max2)/2. Define d = n1*n2, a1 = (min1+max1)/2, and a2 = (min2+max2)/2. The solution to the equations is y1 = (a1-d*a2)/(1-d*d) and y2 = (a2-d*a1)/(1-d*d). In the event that n1 and n2 are perpendicular, d = 0 and y1 = a1 and y2 = a2, which produces your posted equation (that you noted only worked for perpendicular n1 and n2).

I know the formular doesn't give me the correct midpoint because I draw the parallelepiped and the set of points and see that the points are not contained within the parallelepiped. There might be an error e.g. with the drawing code but
I've just tried another method to calculate the midpoint by finding the intersetion of three planes [ 0=n1*x-(min1+max1)*0.5; 0=n2*x-(min2+max2)*0.5; 0=n3*x-(min3+max3)*0.5 ] which gives me the right midpoint.
However I wonder why my first solution doesn't work properly.

EDIT: Now I know thanks to Wasting Time :)
Thanks to you all for your effort.

Oh, I guess I was wrong. Actually, you did say that you were using distances to determine min and max. I assumed what you were doing was find the coordinates of each point using n1, n2, n3 as a base (and the same origin that the original reference had), and then taking the minimum and maximum of each coordinate. In the case of orthogonal vectors, these things are equivalent.

My Math is getting rusty... :(

Unfortunatly the parallelepiped still doesn't contain all points when visualized.
I didn't notice at first, but again as the normal vectors get "less orthogonal" the same effect happens like before, just not so drastically. The midpoint can be caclulated correctly as I discribed in my last post, right ?
alvaro: what is the exact difference between these two methods ? I thought they were equivalent, maybe this is where I have made another error.

This is how I compute the distances:

float min1,min2,min3,max1,max2,max3;
for( i=0; i<num_points; i++ ){

float dist1 = DOT(n1,points);
MIN( min1, dist1 );
MAX( max1, dist1 );

float dist2 = DOT(n2,points);
MIN( min2, dist2 );
MAX( max2, dist2 );

float dist3 = DOT(n3,points);
MIN( min3, dist3 );
MAX( max3, dist3 );
}

And the parallelepiped origin:

origin = ((min1+max1)*0.5*Cross(n1, n2)+(min1+max1)*0.5*Cross(n2, n0)+(min2+max2)*0.5*Cross(n0,n1)) / (n0*Cross(n1,n2));

[Edited by - Quak on October 3, 2006 2:00:51 PM]

Quote:Original post by Quak
I've just tried another method to calculate the midpoint by finding the intersetion of three planes [ 0=n1*x-(min1+max1)*0.5; 0=n2*x-(min2+max2)*0.5; 0=n3*x-(min3+max3)*0.5 ] which gives me the right midpoint.
However I wonder why my first solution doesn't work properly.

Yes, the plane intersection method works for sure. It's actually the same intuition you used to arrive at your original equation. I didn't mention it because I thought it was equivalent to your original equation. But I just realized that we overlooked one important fact when the vectors aren't orthogonal - moving a certain distance along one vector also moves you a certain distance along the other vectors. So if we travel (min1+max1)/2 along n1, and that vector isn't perpendicular to n2, then we're also moving an implicit distance along n2 that we need to rectify in order to reach the midpoint.

The process can be done one vector at a time, if you indeed choose to do it this way instead of using plane intersection. Let's set the distance traveled along n1 to (min1+max1)/2. We now have to figure out the impact on n2 and n3. For every unit we move along n1, we move dot(n1,n2) units along n2 and dot(n1,n3) units along n3. We need to "undo" that when we calculate the distances for those vectors. So the distance traveled along n2 should be (min2+max2)/2 - dot(n1,n2)*(min1+max1)/2, the second term being the correction. Now n3 is going to be screwy because we need to correct against both n1 and n2 :) The distance is (min3+max3)/2 - dot(n1,n3)*(min1+max1)/2 - dot(n2,n3)*((min2+max2)/2 - dot(n1,n2)*(min1+max1)/2). As the number of vectors increases, the equations become burdensome, and hyperplane intersection is clearly the cleaner approach. I can only hope I got those above equations correct the first time

EDIT: Actually I just realized I'm completely wrong, simply by virtue of the fact that the intersection of your three planes is going to have a unique solution, while my construction clearly produces a set of possible solutions depending on which vector you start with. And I just tried to draw it out on paper, and it didn't work, and the reason is plain as day. Turns out you can't process each vertex independently of the others, hence the notion of simultaneous equations! I guess we all have our moments of memory loss [smile] In conclusion, ignore intuition and stick with matrices!

[Edited by - Zipster on October 3, 2006 8:54:33 PM]