interpolation between 2 normal vectors

Performance Tuning
#1

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

Cheers

#2

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

#3

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…

#4

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

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]);
`

#6 

   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


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

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

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

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

EDIT:
typos

#8

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.

#9

Sweet, the lookup table solution looks very efficient.

Thanks guys

#10

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


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

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


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

Both of these are faster on Core2.