Java-Gaming.org Java4K winners: [ by our judges | by the community ]         
Featured games (67)
games approved by the League of Dukes 		Games in Showcase (∞)
games submitted by our members



News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Java-Gaming.org > Game Development > Performance Tuning > interpolation between 2 normal vectors
Pages: [1]
  Print  
  interpolation between 2 normal vectors  (Read 2457 times)
0 Members and 1 Guest are viewing this topic.
Offline phu004

Full Member
**

Posts: 109


NoSuchPersonException
« on: 2009-10-27 20:34:29 »
Hi guys is there any way to  interpolate between 2 normal vectors and keep unit length for interpolated vectors
without normalizing each vector?

Cheers
Offline Abuse

JGO Kernel
*****

Posts: 1866
Medals: 5


falling into the abyss of reality
« Reply #1 on: 2009-10-27 21:59:43 »
Rotate from 1 vector to the other, using the cross product of the 2 vectors as the rotation axis?
Offline phu004

Full Member
**

Posts: 109


NoSuchPersonException
« Reply #2 on: 2009-10-27 22:55:02 »
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! Go get 'em!
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« Reply #3 on: 2009-10-28 03:05:48 »
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.
Online Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5869
Medals: 255


Hand over your head.
« Reply #4 on: 2009-10-28 03:15:59 »
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]);
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Online Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5869
Medals: 255


Hand over your head.
« Reply #5 on: 2009-10-28 13:32:26 »
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);
   }
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline DzzD

JGO Kernel
*****

Posts: 2134
Medals: 16
« Reply #6 on: 2009-10-28 13:47:18 »
Quote from: Riven on 2009-10-28 13:32:26
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
Web 3D Engine - Racer3D Web - Viewer3D - Panorama 3D - VOR2
Online Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5869
Medals: 255


Hand over your head.
« Reply #7 on: 2009-10-28 13:58:06 »
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.
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline phu004

Full Member
**

Posts: 109


NoSuchPersonException
« Reply #8 on: 2009-10-28 17:24:58 »
Sweet, the lookup table solution looks very efficient.

Thanks guys
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« Reply #9 on: 2009-10-29 10:49:19 »

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.
Pages: [1]
  Print  
 
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.16 | SMF © 2011, Simple Machines Valid XHTML 1.0! Valid CSS!
Page created in 0.09 seconds with 20 queries.