39 replies to this topic

[lejno]

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...

[Reedbeta]

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.

[Nils Pipenbrinck]

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.

[lejno]

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?

[Reedbeta]

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.

[lejno]

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.

[Reedbeta]

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).

[Nils Pipenbrinck]

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).

[lejno]

Reedbeta said:

...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 said:

...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?

[Reedbeta]

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

[lejno]

Nils Pipenbrinck said:

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).

[lejno]

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.

[Reedbeta]

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.

[lejno]

Reedbeta said:

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 said:

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.

[lejno]

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.

[Reedbeta]

lejno said:

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.

[lejno]

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

[Reedbeta]

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

[lejno]

Reedbeta said:

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?

[Reedbeta]

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.