Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have an STL file with thousands of triangular planes with different orientations. What is the best way to calculate the direction in which the normal vectors of the triangles are least aligned?

I calculated the ‘average orientation of the normal vectors’ in MATLAB by taking the average of the absolute value of each component (Is it acceptable to take the absolute value?):

xcomp = sum(abs(normal(1,1:numberoftriangles)))/numberoftriangles;
ycomp = sum(abs(normal(2,1:numberoftriangles)))/numberoftriangles;
zcomp = sum(abs(normal(3,1:numberoftriangles)))/numberoftriangles;

And I normalise the length of this ‘average vector’:

wronglength = sqrt(xcomp^2+ycomp^2+zcomp^2);
xcomp = xcomp/wronglength;
ycomp = ycomp/wronglength;
zcomp = zcomp/wronglength;

Can I then just calculate the direction in which the normal vectors of the triangles are least aligned as:

x = 1-xcomp
y = 1-ycomp
z = 1-zcomp

and normalise again?

I am looking for a more accurate algorithm.

share|improve this question
    
"direction in which the normal vectors of the triangles are least aligned" -- What does this mean? Can you explain with an example? –  Rahul Oct 13 '12 at 20:14
    
Ideally my vector would be orthogonal to all the normals (as joriki described it). For example: If I have a slender cylindrical shape described/approximated by a lot of these triangles, the direction in which the set of normal vectors are least oriented, would be the orientation of the axis of this cylinder. –  Joren Oct 13 '12 at 20:30
1  
Ah, yes, then @joriki's answer is the natural solution. I would also recommend weighting the sums there by the areas of the triangles, so that (for example) subdividing a triangle does not change the answer. –  Rahul Oct 13 '12 at 20:39
    
@Rahul: That’s an excellent suggestion, but I will first try to work it out without weighting each normal vector by the area of the triangle as it will increase calculation time. Afterwards I can still refine the code. :-) –  Joren Oct 13 '12 at 20:59

1 Answer 1

up vote 1 down vote accepted

Taking the absolute values is probably not a good idea, and the $x\to1-x$ transform at the end also doesn't look promising.

I'll assume that by "least aligned" you mean that ideally your vector would be orthogonal to all the normals (and thus in the planes of all the triangles), not that it should be opposite to the normals (and thus pointing into the planes); in the latter case you should just add up all the normals and use the direction opposite to the sum.

A first attempt might be to add up the normals and then take a vector orthogonal to the sum, but then you'd have to arbitrarily choose one of the vectors in the plane orthogonal to the sum, and any information which of these might be best would be lost.

Here's a systematic way of doing this. You want your vector $x$ to be orthogonal to the normals $n_i$, so you want the absolute value of the dot product $x\cdot n_i$ to be as small as possible. A natural ansatz would then be to minimize the sum of the squares of the dot products:

$$ \sum_i(x\cdot n_i)^2\to\min\;, $$

subject to the constraint that $x$ is a unit vector. We can write this more suggestively:

$$ \sum_ix^\top n_in_i^\top x=x^\top\left(\sum_i n_in_i^\top \right)x\to\min\;. $$

Adding a Lagrange multiplier term for the normalization constraint yields the objective function

$$ x^\top\left(\sum_i n_in_i^\top \right)x-\lambda x^\top x\;, $$

and requiring the gradient with respect to $x$ to vanish yields

$$ \left(\sum_i n_in_i^\top \right)x-\lambda x=0\;. $$

This is the eigenvalue problem for the positive semidefinite matrix $\sum_in_in_i^\top$. That's just a $3\times3$ matrix, so you can readily find its eigensystem. The direction you want is the eigenvector corresponding to its least eigenvalue.

share|improve this answer
    
This explanation helps a lot! Thank you very much! –  Joren Oct 13 '12 at 20:34
    
@Joren: You're welcome! –  joriki Oct 13 '12 at 20:35
    
You might also consider weighting each term in the sum by the area of it's triangle. –  Nick Alger Oct 23 '12 at 23:46
    
Each term is now weighted by the area of it’s triangle. –  Joren Oct 29 '12 at 13:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.