Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (602) Games in Android Showcase (171) games submitted by our members Games in WIP (649) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 interpolation between 2 normal vectors  (Read 5273 times) 0 Members and 1 Guest are viewing this topic.
phu004

JGO Knight

Medals: 13
Projects: 10
Exp: 10 years

NoSuchPersonException

 « Posted 2009-10-28 00: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
Abuse

JGO Knight

Medals: 28

falling into the abyss of reality

 « Reply #1 - Posted 2009-10-28 01:59:43 »

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

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
phu004

JGO Knight

Medals: 13
Projects: 10
Exp: 10 years

NoSuchPersonException

 « Reply #2 - Posted 2009-10-28 02: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...
Roquen
 « Reply #3 - Posted 2009-10-28 07: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.
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1019
Projects: 4
Exp: 16 years

 « Reply #4 - Posted 2009-10-28 07: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!
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1019
Projects: 4
Exp: 16 years

 « Reply #5 - Posted 2009-10-28 17: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!
DzzD
 « Reply #6 - Posted 2009-10-28 17:47:18 »

 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
« League of Dukes »

« JGO Overlord »

Medals: 1019
Projects: 4
Exp: 16 years

 « Reply #7 - Posted 2009-10-28 17: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!
phu004

JGO Knight

Medals: 13
Projects: 10
Exp: 10 years

NoSuchPersonException

 « Reply #8 - Posted 2009-10-28 21:24:58 »

Sweet, the lookup table solution looks very efficient.

Thanks guys
Roquen
 « Reply #9 - Posted 2009-10-29 14: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]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Jesse (15 views) 2015-07-29 04:35:27 Riven (37 views) 2015-07-27 16:38:00 Riven (18 views) 2015-07-27 15:35:20 Riven (21 views) 2015-07-27 12:26:13 Riven (12 views) 2015-07-27 12:23:39 BurntPizza (30 views) 2015-07-25 00:14:37 BurntPizza (41 views) 2015-07-24 22:06:39 BurntPizza (24 views) 2015-07-24 06:06:53 NoxInc (31 views) 2015-07-22 22:16:53 NoxInc (18 views) 2015-07-22 22:13:39
 theagentd 48x wessles 46x basil_ 35x orangepascal 28x KaiHH 26x Riven 19x ags1 17x mooman219 17x KudoDEV 13x bornander 13x Jesse 11x princec 11x CelestialCreator 11x klaus 11x Zaneris 9x philfrei 8x
 List of Learning Resourcesby gouessej2015-07-09 11:29:36How Do I Expand My Game?by bashfrog2015-06-14 11:34:43List of Learning Resources2015-05-31 05:37:30Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org