Java-Gaming.org
 Featured games (81) games approved by the League of Dukes Games in Showcase (497) Games in Android Showcase (114) games submitted by our members Games in WIP (563) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 interpolation between 2 normal vectors  (Read 4699 times) 0 Members and 1 Guest are viewing this topic.
phu004

JGO Coder

Medals: 4
Projects: 9
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: 12

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 Coder

Medals: 4
Projects: 9
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...
 Games published by our own members! Check 'em out!
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: 799
Projects: 4
Exp: 16 years

Hand over your head.

 « 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: 799
Projects: 4
Exp: 16 years

Hand over your head.

 « 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: 799
Projects: 4
Exp: 16 years

Hand over your head.

 « 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 Coder

Medals: 4
Projects: 9
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.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 BurntPizza (16 views) 2014-09-19 03:14:18 Dwinin (34 views) 2014-09-12 09:08:26 Norakomi (61 views) 2014-09-10 13:57:51 TehJavaDev (84 views) 2014-09-10 06:39:09 Tekkerue (42 views) 2014-09-09 02:24:56 mitcheeb (64 views) 2014-09-08 06:06:29 BurntPizza (47 views) 2014-09-07 01:13:42 Longarmx (35 views) 2014-09-07 01:12:14 Longarmx (39 views) 2014-09-07 01:11:22 Longarmx (36 views) 2014-09-07 01:10:19
 BurntPizza 38x Riven 18x Rayvolution 17x princec 17x basil_ 16x ags1 16x KevinWorkman 15x kevglass 12x LiquidNitrogen 11x nsigma 11x theagentd 11x HeroesGraveDev 9x The Lion King 7x SHC 6x Gibbo3771 6x cylab 6x
 List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50List of Learning Resources2014-07-31 16:26:06List of Learning Resources2014-07-31 11:54:12HotSpot Optionsby dleskov2014-07-08 01:59:08
 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