interpolation between 2 normal vectors

[phu004]

Hi guys is there any way to  interpolate between 2 normal vectors and keep unit length for interpolated vectors
without normalizing each vector?

Cheers

[Abuse]

Rotate from 1 vector to the other, using the cross product of the 2 vectors as the rotation axis?

[phu004]

Mmm, that would work.  I forgot to mention that my goal is to interpolate nomral vectors as fast as possible.
I doubt rotating a vector along an arbitrary axis would be faster than normalizing it...

Games published by our own members! Check 'em out!

[Roquen]

There are a number of options that depend on usage:

Do you want to parameterize (a) the angle?  So a constantly changing 'a' results in a constant angular velocity?  If so, how much do you care about errors in the angular velocity?

Can you make any statements about how many times (on average) a given pair will be used?

Will the angles between the two be within a given range?

Some example options (from cheapest to most expensive):
1) If the max angle is smallish - LERP and a renormalizing step (no sqrt or divide). Not quite constant angular velocity.
2) Larger angle, same as above with some divide-and-conquer steps.
3) SLERP (or faking). Quat set-up per pair = 1 cross, 1 dot, 1 sqrt, 1 div & 4 mul.  Rotation = 18 mul, 15 adds + cost of faking slerp.

[Riven]

you can make a lookup table.



double[] table = new double[1000]; // ought to be enough

Normal a = new Normal(...);
Normal b = new Normal(...);
Normal c = ... linear lerp ...;
int index = (int)(c.squaredLength() * table.length);
c.mul(table[index]);

[Riven]

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25

private static final int     NORMALIZE_LOOKUP_FACTOR = 1024;    private static final float[] NORMALIZE_LOOKUP_TABLE  = new float[NORMALIZE_LOOKUP_FACTOR + 1];    static    {       for (int i = 0; i < NORMALIZE_LOOKUP_TABLE.length; i++)       {          NORMALIZE_LOOKUP_TABLE[i] = 1.0f / (float) Math.sqrt(i / (float) NORMALIZE_LOOKUP_FACTOR);       }    }    /**     * IMPORTANT: the normal must have a length of 1.0 or less, which is     * always the case when lerping between two unit-length normals    **/    public static void normalize(float[] v)    {       float square = (v[0] * v[0]) + (v[1] * v[1]) + (v[2] * v[2]);       float factor = NORMALIZE_LOOKUP_TABLE[(int) (square * NORMALIZE_LOOKUP_FACTOR)];       v[0] *= factor;       v[1] *= factor;       v[2] *= factor;    }

The above code is over 3 times faster than using Math.sqrt().


normalizeSqrt: 91us
normalizeFast: 28us

1   2   3   4   5   6   7   8

public static void lerpNormals(float t, float[] n1, float[] n2, float[] nDst)    {       nDst[0] = n1[0] + t * (n2[0] - n1[0]);       nDst[1] = n1[1] + t * (n2[1] - n1[1]);       nDst[2] = n1[2] + t * (n2[2] - n1[2]);       normalize(nDst);    }

[DzzD]

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25

private static final int     NORMALIZE_LOOKUP_FACTOR = 1024;    private static final float[] NORMALIZE_LOOKUP_TABLE  = new float[NORMALIZE_LOOKUP_FACTOR + 1];    static    {       for (int i = 0; i < NORMALIZE_LOOKUP_TABLE.length; i++)       {          NORMALIZE_LOOKUP_TABLE[i] = 1.0f / (float) Math.sqrt(i / (float) NORMALIZE_LOOKUP_FACTOR);       }    }    /**     * IMPORTANT: the normal must have a length of 1.0 or less, which is     * always the case when lerping between two unit-length normals    **/    public static void normalize(float[] v)    {       float square = (v[0] * v[0]) + (v[1] * v[1]) + (v[2] * v[2]);       float factor = NORMALIZE_LOOKUP_TABLE[(int) (square * NORMALIZE_LOOKUP_FACTOR)];       v[0] *= factor;       v[1] *= factor;       v[2] *= factor;    }

The above code is over 3 times faster than using Math.sqrt().


normalizeSqrt: 91us
normalizeFast: 28us

1   2   3   4   5   6   7   8

public static void lerpNormals(float t, float[] n1, float[] n2, float[] nDst)    {       nDst[0] = n1[0] + t * (n2[0] - n1[0]);       nDst[1] = n1[1] + t * (n2[1] - n1[1]);       nDst[2] = n1[2] + t * (n2[2] - n1[2]);       normalize(nDst);    }

this is what I use in 3DzzD to interpolate vector while drawing each pixel.

But I am very suprise that in your case it is so slow and only three time faster, in my case it is just hundreds time faster ?

but maybe it is because I compute using only integer with something like

1	iNormal[i]= (int) (2147483648.0 / sqrt(i+1));

so I have no cast and only integer computation (with 65536 meaning 1.0)

EDIT:
typos

[Riven]

Yup, float <-> int cast on x86 is rather slow, as it switches from the FPU to the CPU.

Maybe the benchmark isn't perfect either, and the usage of float[] might be yet another problem.

[phu004]

Sweet, the lookup table solution looks very efficient.

Thanks guys

[Roquen]

Large table look-ups can kill performance on modern desktops.

Here are a couple examples, assuming the max angle between vectors is within Pi/2 degrees:

max error (abs & rel) ~= 4e-4

1	2.04574f + x * (0.569019f * x  - 1.61435f)

max error (abs & rel) ~= 3e-5

1	2.38647f + x *(-2.82967f + (2.00305f - 0.559885f * x) * x)

Both of these are faster on Core2.