Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) 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 8128 times) 0 Members and 1 Guest are viewing this topic.
phu004

JGO Knight

Medals: 14
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 Ninja

Medals: 64

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

JGO Knight

Medals: 14
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

JGO Kernel

Medals: 517

 « 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

« JGO Overlord »

Medals: 1336
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

« JGO Overlord »

Medals: 1336
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

« JGO Overlord »

Medals: 1336
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: 14
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

JGO Kernel

Medals: 517

 « 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

 ivj94 (585 views) 2018-03-24 14:47:39 ivj94 (49 views) 2018-03-24 14:46:31 ivj94 (383 views) 2018-03-24 14:43:53 Solater (63 views) 2018-03-17 05:04:08 nelsongames (109 views) 2018-03-05 17:56:34 Gornova (159 views) 2018-03-02 22:15:33 buddyBro (704 views) 2018-02-28 16:59:18 buddyBro (92 views) 2018-02-28 16:45:17 xxMrPHDxx (494 views) 2017-12-31 17:17:51 xxMrPHDxx (734 views) 2017-12-31 17:15:51
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 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