Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (120)
games submitted by our members
Games in WIP (577)
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 4779 times)
0 Members and 1 Guest are viewing this topic.
Offline 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
Offline Abuse

JGO Knight


Medals: 13


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
Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
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
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
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
Offline 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

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
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
Offline 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
Offline 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.

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (42 views)
2014-10-16 15:22:06

Norakomi (32 views)
2014-10-16 15:20:20

lcass (37 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (66 views)
2014-10-14 00:35:47

TehJavaDev (59 views)
2014-10-14 00:32:37

BurntPizza (73 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45

BurntPizza (85 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!