Average direction vector

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 10, 2006 at 22:59

Ok, I’m “stuck” on a very basic problem: A couple of triangle’s share a vertex, what normal vector should I set for it. That is; what do I call the “average direction vector”?.

Everyone seems to just normalize the vectors, and then simply find the average of the resulting cartesian components. Alternatively, the result of this could be normalized.

For only two vectors, the average direction vector should of course lie in their plane, and it should bisect the angle between them.

Normalize the two vectors to get an isosceles triangle. Their directions, and hence the average direction vector, does not change as a result of this. Now the vector vb - va is the base of the triangle. And because the triangle is isosceles:

va + (vb - va) / 2

lies on the line bisecting the angle between them.
This can be rewritten as:

va + (vb - va) / 2 = vb / 2 + 2*va / 2 - va / 2 = vb / 2 + (2*va - va) / 2 = (vb + va) / 2

Wich is just the average of the cartesian components of the vectors, so for two vectors, what everyone seems to use works.

But what is the definition of the “average direction” of more than two vectors?

My best bet thus far is the vector wich minimizes the sum of the “errors”. Where an error is the angle measured from the average to the different vectors, but I’m not sure…

39 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 10, 2006 at 23:11

The ordinary (arithmetic) average of the works fine for multiple vectors. What people usually do is add up the unnormalized normals for each of the triangles sharing a vertex, and normalize the result. This gives the effect that triangles with a larger area contribute more to the vertex normal, which is a nice heuristic.

But all this is just a heuristic. If you want to be mathematically rigorous about it, a triangle mesh isn’t differentiable along edges or at vertices so one can’t define a meaningful tangent or normal there. However, if the triangle mesh is an approximation to some ideal curved surface that is differentiable (for instance a Bezier patch or NURBS surface), then the vertex normals ought to be calculated based on the tangent vectors to that surface (its parametric derivatives). On the other hand, sometimes you deal with something like a subdivision surface where the definition is too complicated to differentiate explicitly, or you just have the triangles and you don’t have a description of the original Bezier or NURBS patches. Then falling back to this kind of heuristic is about the best one can do.

Feel free to come up with your own ‘average direction’ heuristics, if you’re uncomfortable with the standard ones - but realistically, the arithmetic average works just fine for most situations.

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Aug 10, 2006 at 23:51

for meshes, where you need vertex normals, the method reedbeta described worked pretty good. I’ve also blended another, artificial vector into the equation: The direction vector from the center of the mesh. This gave a much smoother appearence to environment mappings. Sucked for some meshes, did wonders to others..

Imho the most correct way to calculate them would be to weight each normal by it’s contributing face area. That’s a bit more to calculate, but for a preprocessing step it shouldn’t be much of a problem.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 11, 2006 at 00:16

Fair enough, Reed. Nice reply, but I should have been clearer about this:
My question wasn’t really concerning the problem I mentioned at the start of the post.

I just wrote that bit to introduce the problem of having a bunch of normals (normalized), and somehow finding the average direction. So the problem I was trying to describe really has nothing to do with differentiability or NURBS.

I know there is no mathematical definition of “best” (or is there…).
It’s just that when thinking of a unit sphere with the unit vectors marked as dots on it’s surface, it seems there should be some nice analogy in wich the barycenter of a bunch of points in a plane is the “average direction vector”.

But when trying to find this point, wich seems so easy to find, I run into problems when trying to find a decent parameterisation of the surface.
I “can’t” really use the angular components of spherical coordinates; this doesn’t yield the expected result for the case of two vectors (the result wouldn’t lie on “the line along wich the crow flies” in general, as it “should” shouldn’t it).

There is also wierdness because angular coordinates must have a discontinuity, like the one at 360 and 0 degrees, or the one at -180 and 180 degrees and so on.
I mean, how do you average parameters that are cyclic instead of linear in this sense?

Not having read must about them; “This sounds like a job for the quaternions”.
Does it?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 11, 2006 at 04:21

Hmm, I’m not sure if quaternions would be helpful. Quats are really just points on a 3-sphere (which is isomorphic to the set of rotations in 3-space, hence the use of quats for rotations) while your problem involves points on a 2-sphere.

I know it’s possible to perform an arithmetic average of several numbers by a weighted averages of two numbers at a time. For instance, the average of n1, n2, and n3 is (n1 + n2 + n3)/3, which is the same as (2*(n1 + n2)/2 + n3)/3. That is, you can average n1 and n2 first, and then average the result with n3, weighting n3 only half as much. Maybe you could do something similiar with the points on a sphere. Averaging two points is just a matter of calculating the geodesic between them, which is an arc of the circle lying in the plane formed by the two points and the sphere’s center, and finding the midpoint (or other point for a weighted average) along that geodesic.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 11, 2006 at 13:26

Even though you’re only measuring a difference, the geodesics would have to be measured from some common point because you have the element of direction as well. Else the results will be sensitive to sequence.

I am now quite sure that any kind of “arithmetic average” will not be a solution, because then you will have to have a fixed coodrdinate system.
The coordinate system would also have to be orthogonal, and in this case I belive it will have to be a spherical coordinate system.

I’m now even more convinced that some (“coordinate free”) algorithm finding the vector wich minimizes the collective area of the geodesics measured from it would do best.
Although it cannot simply be the area, but some function of the area with an increasing rate of change, like the square of the area, or the choice would be arbitrary for two vectors.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 11, 2006 at 17:40

lejno, don’t be so quick to write off coordinate-based methods. The arithmetic average of a set of vectors is an invariant: no matter what coordinate system you choose (Cartesian coordinate systems, not curvilinear ones like spherical), the average calculated will always be the same vector. (Interesting linear algebra exercise: prove it!) The coordinate system does not have to be orthogonal either.

The method I described in my previous post is also invariant of the specific coordinate system (since it’s geometrical) and I would be willing to bet that it’s actually invariant of sequence too under some appropriate conditions (all the vectors lying within a hemisphere, for instance).

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Aug 11, 2006 at 18:20

Hm… Idea:

3 normals emit from a common point. These form a triangle. Calculate the center of mass for this triangle. The average normal vector will be | center_of_mass - common_point|.

This obviously works for two and tree vectors, and for all combinations where the normals spawn a convex n-gon.. For non-convex n-gons I have no idea, but it’s a start, isn’t it?

(Highy interesting topic… I never really thought about it in detail).

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 11, 2006 at 18:41

@Reedbeta

…don’t be so quick to write off coordinate-based methods.

Oh, I wouldn’t. Especially not the standard method, I think I was referring to any klind of angular coordinates.
@Reedbeta

…I would be willing to bet that it’s actually invariant of sequence too under some appropriate conditions (all the vectors lying within a hemisphere, for instance).

If I understood you correctly, the method would be equivalent to:

“For the current average vector, measure the angle (in their plane) to the next one in the sequence, and add to the current average vector the vector pointing to the point on the arch 1/N’th of the measured angle from the current average vector. Where N is the total number of vectors to be averaged”

Is this what you meant?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 11, 2006 at 21:33

Not exactly…let me be a bit clearer:

weight = 1;
average = vec[0];
for (i = 1; i < n; ++i)
{
    find angle between average and vec[i];
    angle *= weight / (weight + 1);
    average = rotate vec[i] towards average by angle;
    ++weight;
}
8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 11, 2006 at 21:48

@Nils Pipenbrinck

3 normals emit from a common point. These form a triangle. Calculate the center of mass for this triangle. The average normal vector will be | center_of_mass - common_point|.

Ah, yes. This is an analogy of what I said about two normals.
And because of what Reedbeta said about the average of the cartesian components (same as center of mass) being invariant at least for “linear” coordinate systems, the standard method will yield the analogous result for three vectors as well.

It seem that my hangup stems from some kind of misconception on my part that angles must play a major role in the definition of “average direction”.

I mean, if we reduce the problem to two-space, and attempt to define average direction there, we will still get into trouble when using angles because what if we place two vectors symmetrically just above and just below the unavoidable discontinuity? The average will be 180 degrees off that’s what!

I think the more reasonable definiton would be; “The average direction vector is the vector with the maximum sum of the scalar products (dot products) with the normal vectors” or “The normal to the lawn wich has the most grass on it” ;)…. (normal vectors are grass… duh)

This seems reasonable in two and three dimensions as well as in the fourth dimension (kidding).

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 11, 2006 at 22:55

I think I understand why you suggested this method, Reedbeta.
It is because one gets into trouble with the “choice of coordinate system” when adding together the angles of more than two vectors.

Your method of counting and computing an average in the same loop works, of course, and I get the point of this in other applications…

Your algorithm would make sense to me only if all of the vectors where on the same disc (plane intersecting the sphere). They also need to be on only one half of the disc. Because then, the coordinates will mean the same thing at every step. If they do not, then the vectors pull the average in a sense depending on where it happens to be at the moment, which depend on the previous sequence.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 11, 2006 at 23:00

I’m not sure but I think you’re misunderstanding the method. It’s geometric - it doesn’t depend on the choice of coordinate system, and I never add together the angles of any vectors at all, I only rotate vectors through certain angles about certain axes. Try to picture it in your head. It is just the same way that one can compute an average on the plane by drawing lines connecting the points - we’re simply doing that on the surface of a sphere instead, where the geodesics are the “straight lines” of the sphere.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 11, 2006 at 23:53

@Reedbeta

It’s geometric - it doesn’t depend on the choice of coordinate system.

Yes, if you read my post again. You’ll see that I referred to the fact that fixing a coordinate system and thus aiming for an arithmetic solution gets us into trouble as the only point of your obviously coordinate-free solution I understand.
@Reedbeta

It is just the same way that one can compute an average on the plane by drawing lines connecting the points - we’re simply doing that on the surface of a sphere instead, where the geodesics are the “straight lines” of the sphere.

This is the part of your method I dont understand. You’re saying that doing this on a set of points in the plane, in any sequence, yields the center of mass?

If this is true, I find it amazing that you can use the same trick (to incorporate the counting into the same loop) as when you are calculating the average of points along a *fixed* coordinate axis and *fixed* reference point (zero), to weigh vectors in the plane with *different directions* and *uncimparable* (even the directions will be different) reference points, and yet arrive at the same geometric point. It seems like a mix of an arithmetic method and a geometric method.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 12, 2006 at 00:56

I feel I need to motivate this thread a bit more at this point.
From the start, I felt intuitively that there had to be some obvious true average direction vector.

I wanted to compare this true average vector with whatever vector the “standard method” (arithmetic average of cartesian components) spits out (perhaps remarkably they would turn out to be the same).
And then I wanted to compare the visual impact this difference had on the lighting on a model.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 12, 2006 at 01:22

@lejno

This is the part of your method I dont understand. You’re saying that doing this on a set of points in the plane, in any sequence, yields the center of mass?

Yes.

Let me explain in a bit more detail. To take an example, the average of 3 elements (numbers, vectors, whatever) is calculated as (n1 + n2 + n3)/3. However, suppose we are only able to calculate the average of two at a time (but we can do weighted averages). We are still able to calculate the average of three elements. We can do this by first averaging the first two: average1 = (n1 + n2)/2. Then, the result can be averaged with the third element: average2 = (2*average1 + n3)/3. This computation is a weighted average, which weights the first average twice as much as the third component. To add a fourth component, we would calculate average3 = (3*average2 + n4)/4, and so forth. You can see algebraically that this reduces to the same result as doing the average the ordinary way - but it allows us to compute the average by using only two elements at a time. And it’s invariant of the sequence you put the elements in, coordinate system used, et cetera.

For vectors in 3-space, averaging their Cartesian coordinate components is equivalent to drawing a line between them and picking a point on that line that is closer or further to each endpoint depending on that endpoint’s weight. I am proposing simply replacing the line with a spherical geodesic (arc of a circle). The operation of taking the ‘average’ of two directions is therefore mostly well-defined (the exception being that two antiparallel directions aren’t connected by a unique geodesic, so they don’t have a well-defined average). Then one can apply the procedure I illustrated above to recover the average of N directions even though we are only able to directly compute the average of two.

However, I’m thinking now that this is pretty much too complicated and that Nil’s way is better and just as likely to be “correct” as mine. You just take the arithmetic average of all the directions (as unit vectors), and normalize the result to recover a unit vector again. This gives you trouble if the average happens to be very close to zero. But in that case your directions were spread out all over the sphere and there’s unlikely to be a well-defined average direction anyway.

But then, given your stated goal of comparing the standard heuristic for vertex normals to other methods, I’d have to say that I doubt very much the difference will be at all noticeable in most cases.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 12, 2006 at 14:06

I understand how you’d apply the method (on numbers or vectors) given a fixed point from wich you measure them all.

Say we have these vectors in sequence:

v1 = (-1, 1)
v2 = (1, 1)
v3 = (-1, -1)
v4 = (1, -1)

Now the common point is the origin and we could do:

avg1 = v1
avg2 = (avg1*1 + v2) / 2 = (v1 + v2) / 2
avg3 = (avg2*2 + v3) / 3 = (v1 + v2 + v3) / 3
avg4 = (avg3*3 + v4) / 4 = (v1 + v2 + v3 + v4) / 4

But this is not what you suggested as I understood it.
What you suggested was:

avg1 = v1
avg2 = (v2 - avg1) / 2 = (v2 - v1) / 2
avg3 = (v3 - avg2*2) / 3 = (v3 - (v2 - v1)) / 3 = (v3 - v2 + v1) / 3
avg4 = (v4 - avg3*3) / 4 = (v4 - v3 + v2 - v1) / 4

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 12, 2006 at 16:02

I don’t know where you got that last bit from, but that’s definitely not what I was suggesting. ;)

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 12, 2006 at 16:27

@Reedbeta

I don’t know where you got that last bit from, but that’s definitely not what I was suggesting. :)

Ok, so from wich vector are you measuring all of the angles?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 12, 2006 at 18:17

It’s just the angle between two directions (unit vectors). You know, the arc-cosine of their dot product. There is no common point from which all angles are being measured. It’s just that instead of moving along a line between two points to calculate an average, you’re moving along an arc between two unit vectors on the surface of the unit sphere.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 12, 2006 at 18:50

@Reedbeta

…It’s just that instead of moving along a line between two points to calculate an average, you’re moving along an arc between two unit vectors on the surface of the unit sphere.

And when you measure the angle of this arc from the current average to the next vector in the sequence, this operation becomes subtraction (difference) in the analogy, and the second bit I wrote is the analog of this:

avg1 = v1
avg2 = {v2 - avg1} / 2
avg3 = {v3 - avg2*2} / 3
avg4 = {v4 - avg3*3} / 4

The parts in curly bracets correspond to the measuring of the angle from the current average to the next vector in the sequence.

820ce9018b365a6aeba6e23847f17eda
0
geon 101 Aug 12, 2006 at 19:42

@lejno

And when you measure the angle of this arc from the current average to the next vector in the sequence, this operation becomes subtraction (difference) in the analogy, and the second bit I wrote is the analog of this:

avg1 = v1
avg2 = {v2 - avg1} / 2
avg3 = {v3 - avg2*2} / 3
avg4 = {v4 - avg3*3} / 4

The parts in curly bracets correspond to the measuring of the angle from the current average to the next vector in the sequence.

You don’t need to try to find an analogy to the rotation. It’s simply a weighted average on the arc.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 12, 2006 at 20:23

Suppose p(t) is the parametric function of that arc, with t ranging from a to b, p(a) being the first vector and p(;) being the second vector. You do the weighted average simply by taking p(a*weight1 + b*weight2), where weight1 + weight2 = 1.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 12, 2006 at 23:01

This is the correct recurrence for finding the average in regular two-space:

avg_1 = v_1
avg_i = { avg_(i-1)*(i-1) + v_i } / i

Focus on the addition in curly brackets.
It is an addition of two vectors.
We can only add two vectors wich are in the same space.
Two vectors are not in the same space if they do not share an origin, for our purpose (calculating the barycenter), it doesn’t matter which origin, but it does have to stay the same.

Now we get back to the sphere.
Here we use the notation Avg_i and V_i to denote the usual normalized vectors measured from the center of the sphere.

Here comes my point:

*Adding* to Avg_i a vector representing a rotation (rotating it) *from* Avg_i *towards* V_(i+1)

is the analog of:

*Adding* to avg_i a vector *from* avg_i *towards* v_(i+1)
(that is, the vector we add is v_(i+1) - avg_i)

And is not the analog of:

*Adding* to avg_i a vector v_(i+1)

The “true” vector v_(i+1) needs to be measured from the same origin as avg_i is measured from, and not from avg_i itself.

So all of the vectors v_i are the geodesics measured from a common origin, say the z axis, to the vectors V_i.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 12, 2006 at 23:51

I’m sorry. You’re wrong, there is no subtraction of vectors involved. Reread my previous post. A geodesic is just a parametric curve. The weighted average along that curve between its endpoints is just the function applied to the weighted average of the appropriate parameter values. For averaging vectors, the function is the parametric equation of the line between the vectors. For averaging directions, the function is the parametric representation of the geodesic. That’s really all there is to it - nothing fancy going on. Forget for a moment that averaging vectors involves addition. What I am proposing does not involve adding or subtracting the vectors representing those directions, only *rotating* them.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 13, 2006 at 09:52

@Reedbeta

…You’re wrong, there is no subtraction of vectors involved.

No, not explicitly in the three-space, but analogously in the two-space.

In the sense of picturing the vectors on the shell as vectors on a surface, what operation do you think rotation from a vector A toward (by some amount) a vector B would represent (in the surface-space)?

Is it not supposed to _represent_ a vector addition (in the two space of the surface)?

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 13, 2006 at 17:59

Anyway, I am quite sure that my variation of your method is what I was looking for from the beginning; It would yield the same result regardless of what “origin” (vector from which I measure all of the angles) I use and it would handle distributions of vectors over the entire spherical surface.

So thank you for the inspiration, maybe I’ll implement it and invoke this thread with the “results” (if any) of the comparison with the standard method.

Here is the “psuedo-c-code”:

vector v[n]; // Normalized vectors, to be blended
vector pole(0, 0, 1); // This is the "origin", it can be any unit vector
float theta;
vector blend = pole; // Start at "zero"
vector omega;

for(int i = 0; i < n; i++)
{
    // The weighted magnitude of the curved vector, analogous to 1/n
    theta = arcsin(cross_prod(pole, v[i])) / n;

    // Rotate the vector blend theta radians about the vector cross(pole, v[i])
    // This is analogous to adding the weighted vector
    omega = theta * cross_prod(pole, v[i]); // Instantaneous rotation vector
    blend = cross_prod(omega, blend); // Perform the instantaneous rotation
}
A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 13, 2006 at 20:16

@lejno

In the sense of picturing the vectors on the shell as vectors on a surface, what operation do you think rotation from a vector A toward (by some amount) a vector B would represent (in the surface-space)? Is it not supposed to _represent_ a vector addition (in the two space of the surface)?

I’m not sure why you think it’s necessary to make this analogy, or why you seem to think there has to be an ‘origin’ of sorts within the 2-space of the surface itself. After all, you can average (ordinary average) several vectors that lie in a plane, without needing the origin to lie within the plane. All it involves is drawing lines between the vectors and moving along them. There is no necessity for an origin, and the same is true if instead of a plane you use a sphere. All it involves is drawing geodesics between the vectors and moving along them. It shouldn’t even be thought of as vector arithmetic.

Anyway, I don’t think your method is correct because it places an inherent bias toward the pole. Consider the simple case of averaging the two vectors [1, 0, 0] and [0, 1, 0]. First of all the code you posted doesn’t even generate a normalized vector because you do the rotation incorrectly. But even fixing that bug, one doesn’t come out with [0.71, 0.71, 0] which would clearly be the correct answer - instead, the answer is biased upwards, towards the pole. The reason is finite rotations don’t add like vectors, so you can’t apply ordinary laws of vector arithmetic to them.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 13, 2006 at 23:16

@Reedbeta

…All it involves is drawing lines between the vectors and moving along them. There is no necessity for an origin…

I know this thread has gone on long enough, but I think it’s because of the lack of concrete examples.
Would you mind giving me a concrete motivation of this method of finding the average in a regular plane? I mean; show that it is equal to sum(v*) / n.
*

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 14, 2006 at 00:35

Okay. Suppose the three points we want to average are:
v1 = [0, 0, 1]
v2 = [1, 0, 1]
v3 = [0, 1, 1]
You’ll notice they’re all in the z = 1 plane.

First, construct the line from v1 to v2. This has the parametric equation:
x(t) = [0, 0, 1] + t[1, 0, 0].
Note that x(0) = v1, while x(1) = v2. Thus, take the weighted average of the parameter values 0 and 1. This gives 0.5. So the average of v1 and v2 is x(0.5), or [0.5, 0, 1].

Then, suppose we want to include the third vector. We find the line connecting the [0.5, 0, 1] to v3. That is:
x(t) = [0.5, 0, 1] + t[-0.5, 1, 0]
As before, x(0) = [0.5, 0, 1] (our previous average), and x(1) = v3. This time we weight the previous average twice as much, so the desired parameter value is (2*0 + 1*1)/3 = 1/3. And the average is
x(1/3) = [0.5 - 1/6, 1/3, 1] = [1/3, 1/3, 1]. And I think you’ll agree that is the correct average of those three vectors.

Doing this on a sphere is the same overall, but instead of having x(t) be the parametric function of a line on a plane, it’s the parametric function of a geodesic on a sphere.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 14, 2006 at 15:47

I know I don’t need to remind you of this but you can only disprove assertions numerically.

What you’re doing amounts to:

a[1] = v[1]
a = a[i-1]*i + (v - a[i-1]) / (i+1), for i=1…n

And the average is:

m[1] = v[1]
m = (m[i-1]*i + v) / i+1, for i=1…n

Isn’t this what you meant?

25bbd22b0b17f557748f601922880554
0
bramz 101 Aug 14, 2006 at 16:41

Far more interesting to get your “average” right than this theoretical mumbo jumbo on “true” averages (for which I’m in Reedbeta’s camp), is the following: what weights will you attribute to the normals of the faces sharing the vertex?

Example: consider a axis aligned cube of size 2 around the origin (cubes aren’t the best examples to apply vertex normals too, but hey =). Suppose we want to determine the vertex normal in vertex (1, 1, 1). This vertex is shared by three faces (quads) with normals (1, 0, 0), (0, 1, 0) and (0, 0, 1). Averaging these normals gives us the correct vertex normal (0.58, 0.58, 0.58).

However, in real life (*ahum*), cubes aren’t built from quads but triangles. Each quad is two triangles. Some of the vertex/quad pairs, will now be replaced by TWO vertex/triangle pairs, while other will still have only ONE vertex/triangle pair. Now suppose for vertex (1, 1, 1), the connection to the (1, 0, 0) face is replaced by two (1, 0, 0) triangle connections, while for the others it remains only one. If we again naively average all normals, we get to the result (0.82, 0.41, 0.41), which is clearly wrong. The reason is that the (1, 0, 0) is counted twice.

How do we solve that? We use the triangle inner angles in that vertex as a measurement for the weights. How does it work? Well, for the (1, 0, 0) side, there will be two triangles sharing that vertex. For both of them, the inner angle in that vertex will be 45°. For the other two sides, we only have one triangle sharing the vertex and they will have both an inner angle of 90°. That’s a total of 270°. Now we can make the weighted average:

(45*(1, 0, 0) + 45*(1,0,0) + 90*(0,1,0) + 90*(0,0,1)) / 270 = (0.33, 0.33, 0.33), which leads to (0.58, 0.58, 0.58) after normalisation. So we get the correct result.

How to determine that angle in a live numerical way, is left as an exercise to the reader =)

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 14, 2006 at 17:11

@lejno

I know I don’t need to remind you of this but you can only disprove assertions numerically.

This wasn’t a formal proof, just a demonstration of how it works (I thought that’s what you were asking for).

What I’m doing amounts to:
m[1] = v[1]
m = u_i(1/(i+1))
where u_i is a geodesic (whatever that means in the manifold we are considering, in a plane it’s a straight line, in a sphere it’s a great circle) connecting m and v, parameterized such that u_i(0) = m, and u_i(1) = v.

In Euclidean space this amounts to:
u_i(t) = m + t*(v - m)
And so:
m = u_i(1/(i+1)) = m + 1/(i+1)*(v - m)
= i/(i+1)*m + 1/(i+1)*v
= (by arguments made previously) 1/i*(v[1] + v[2] + … + v).

Now, I can’t prove to you that this approach, which matches the average formula in a plane, also works in a sphere (when you change the u_i from lines to great circles), since there isn’t any handy formula for the average there. I’m just trying to appeal to intuition to convince you of what I believe is true, that this gives you a sane average direction as long as all your directions are within a hemisphere (otherwise, it’s possible for things to get messy).

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 14, 2006 at 19:45

@Reedbeta

This wasn’t a formal proof, just a demonstration of how it works (I thought that’s what you were asking for).

What I’m doing amounts to:
m[1] = v[1]
m = u_i(1/(i+1))

where u_i is a geodesic (whatever that means in the manifold we are considering, in a plane it’s a straight line, in a sphere it’s a great circle) connecting mand v
**

Up until this point, I agree totally.
@Reedbeta

…parameterized such that u_i(0) = m, and u_i(1) = v.
**

To nitpick (I’m sure you’ll agree, and that this is what you meant), u_i(t) has be linear (a line) and increase linearly (linear tracing speed) in the sense in the manifold. Not sure if I can argue mathematically here, but intuitively this means to me that radians / t = const.
If the “speed” is not linear, I don’t think it makes any sense to scale it by 1/(i + 1).
It’s harder to see what is supposed to make it linear. To get around this, you measure it from a “point” in the manifold to a differnt “point” in the manifold, and then of course, it is a line.
End of nitpicking on what I thought you mean.
@Reedbeta

In Euclidean space this amounts to:
m= u_i(1/(i+1)) = m+ 1/(i+1)*(v- m)
= i/(i+1)*m+ 1/(i+1)*v
= (by arguments made previously) 1/i*(v[1] + v[2] + … + v).
**

OH! See this is where I went wrong. I though “Well, I cannot just add m, I have to get rid of it’s denominator by multiplying with i and add that in the nominator of v / (i + 1)”

At this point I was so sure you already whent wrong that I din’t bother manipulating it further.
I didn’t notice this would resolve itself when putting the expression on the equal denominator (i + 1).
For which I apologize big-time because it is a simple manipulation.

Ok, so that settles it. We agree on that what you do is analogous to what is correct in Euclidean space… The reason this thread went on so long is that I wasn’t convinced due to the fact that we should have written down formulas earlier, otherwise the manipulation I missed is hard to “see”.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 14, 2006 at 20:02

On the note of avoiding becoming so unsure about a problem in the future: what branch of math (if any) would have allowed me to study the abstract generalization of the concept of “arithmetic average” to see if there is an “analog” on the space of the surface of a sphere, or some other “directional” space.

Does anyone know? Hurry! Before I go and by an abstract algebra book.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 14, 2006 at 20:13

@bramz

…mumbo jumbo…

Yes it was :)

I was kind of hoping someone like Per Vognsen (psycotic at the old Flipcode, I know you were a member, as were Reedbeta and Nils) would step in an tell me abstractly either why it doesn’t make sense to look for it, or, if there is some abstract meaning of ‘average’, tell me abstractly what it means on the surface of a sphere.

In either case, I would have asked for tips on reading materials wich might help me provide myself with the same ‘quick’ basis of desicion as his post. Even if the answer would have been “Everything you can get your hands on”.

Ac83bb2f9b48b454fe2f51b3027363f5
0
mzeo77 101 Aug 14, 2006 at 21:30

The above method is dependent on the order in which the normals is avaraged. Try to apply the algorithm to three normals, all close to 120 degrees appart, almost forming a plane through origo. Then you will see that the order in which the pairs are avaraged are definately order sensitive.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 14, 2006 at 21:56

@mzeo77

…The above method…

Wich one?

The last actual implementation was my code, wich we already saw was wrong.
Any other complete implementation is not available, however I can modify mine a little bit:

vector v[n]; // _Normalized_ vectors, to be blended
float theta;
vector blend = v[0];
vector omega;

for(int i = 1; i < n; i++)
{
    theta = arcsin(length(cross_prod(blend, v[i]))) / (i+1); // Weighted amount to rotate
    omega = theta * cross_prod(blend, v[i]); // Instantaneous rotation vector
    blend = cross_prod(omega, blend); // Perform the instantaneous rotation
}

The way the discussion turned out, this is what me and Reedbeta seems to agree on I believe. Let me know if you test this. (I haven’t got the vector operations handy right now)

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Aug 14, 2006 at 22:13

@lejno

To nitpick (I’m sure you’ll agree, and that this is what you meant), u_i(t) has be linear (a line) and increase linearly (linear tracing speed) in the sense in the manifold. Not sure if I can argue mathematically here, but intuitively this means to me that radians / t = const.
If the “speed” is not linear, I don’t think it makes any sense to scale it by 1/(i + 1).

Yep, I assumed that went without saying. There is a well-defined notion of the geodesic having been parameterized with respect to arc-length, which makes its parameter precisely equal to the length along the curve, and I’ll let my parameter be affinely related to that (linear scale, plus a constant offset if necessary).

As for other areas of math, I think analysis and differential geometry may be what you’re looking for. Analysis deals with geometry in generalized metric and normed spaces (other than ordinary Euclidean space), and differential geometry specializes in geometry on curved manifolds (like spheres). I haven’t come across material specifically related to averaging in either of those areas, but that doesn’t mean it isn’t there.

Oh, and just a note:

omega = theta * cross_prod(blend, v[i]); // Instantaneous rotation vector
blend = cross_prod(omega, blend); // Perform the instantaneous rotation

I’m afraid this doesn’t perform the rotation that the comments indicate. I’m not sure where you got these expressions from, but multiplying the angle by the vector doesn’t really make sense. Instead, a rotation matrix should be generated (see this page, scroll down to the heading “Axis Angle Rotations”), and multiplied by the vector to be rotated. Or quats could also be used.

8563c4b89241071d63ff06043477f3b2
0
lejno 101 Aug 14, 2006 at 23:32

@Reedbeta

As for other areas of math, I think analysis and differential geometry may be what you’re looking for.

I’ve skimmed trhough the description of this topic on Wikipedia…
I thought it might be what I was looking for. Either that or “abstract algebra” with symmetry and rotation groups and rings and all that…
@Reedbeta

Oh, and just a note:

omega = theta * cross_prod(blend, v[i]); // Instantaneous rotation vector
blend = cross_prod(omega, blend); // Perform the instantaneous rotation

I’m afraid this doesn’t perform the rotation that the comments indicate. I’m not sure where you got these expressions from. Instead, a rotation matrix should be generated…

Argh! I messed up again. The instantaneous rotation vector (omega) is a concept from dynamics. The cross_prod(omega, blend) vector is only tangent to the path along wich to rotate, so adding this times an infinitesimal would be an “instantaneous” or “infinitesimal” rotation.
But this can be fixed for finite rotations with some trigonometry and a normalization because the angle of rotation is never larger than 90 degrees in this application… So you don’t need a matrix.
This is the next version:

vector v[n]; // _Normalized_ vectors, to be blended
vector blend = v[0];

for(int i = 1; i < n; i++)
{
    vector omega = cross_prod(blend, v[i]);
    float arc_sine = length(omega);
    float weighted_arc_length = arcsin(alpha_sine) / (i+1);
    float tangent_vector_length = tan(weighted_arc_length); // Determine the length that a vector tangent to the rotation arc has to have to yield a rotation of weighted_arc_length radians upon addition and normalization of the result
    

    blend += tangent_vector_length * cross_prod(omega, blend); // Add the tangent  vector
    blend *= 1/length(blend); // Normalize the new blend to complete the rotation
}

Quite different…
I apologize for the mixup. It was intended as psuedocode and the operations I did was mixed up in my head as rotations because that’s what my ‘representation’ of them was when I thought about stuff in dynamics. Of course, that mess shouldn’t have been released on you to figure out, that was disrespectful of me.