Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (595) Games in Android Showcase (169) games submitted by our members Games in WIP (648) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Optimized Interpolation Set?  (Read 1482 times) 0 Members and 1 Guest are viewing this topic.
tusaki

Junior Devvie

Medals: 1

 « Posted 2006-01-29 12:09:30 »

Hia, for various purposes I've created an Interpolation Set class. A picture explains better than words, so let met start with that:

The Interpolation set contains a series of key/value floats. What I want to be able to do is to query the set for any key-value in the interpolation and get a corresponding result. So, in the example above, the data set contains the following key-value pairs:
 Key Value 0 160 0.4 160 0.625 98 1.0 55

When I query this set for key-value 0.5, I want the set to return the interpolated value.
• In this case, 0.5 is in between keys 0.4 and 0.625. To calculate the interpolated value
• First I determine the distance between the keys. The distance between the keys in the set is (0.625-0.4) = 0.225.
• The distance between the queried key and the lowest-nearest key (the first key to the left of the queried key...) is 0.5 - 0.4 = 0.1.
• 0.1 is 44.44% (0.1 / 0.255) of the way of the distance between the two known keys.
• So finally we have to calculate what 44.44% of the way of the distance between the values is.  The distance between the values is 98-160 = -62
• .... 44% of -62 = -27.55.
• The final value and the value I wanted to get from the set is the leftmost value (160) plus the interpolated value (-27.55) so finally : 160 + -27.55 = 132.45.

Now the question for this forum is: what would be an (the most?) optimized way of approaching this problem? attached to this message is one way of doing this. But I have the gut feeling that it can be done in a better way.

When quering for a key lower than the lowest key in the set, the set should just return the first value. In case you query for a key higher than the highest key in the set, just return the last value.

Junior Devvie

Java games rock!

 « Reply #1 - Posted 2006-01-29 13:44:08 »

So, if the nearest key/value to the left is (x1,y1) and the nearest key/value to the right is (x2,y2) you want to calculate the weighted average, i.e.

 1  2  3 y1 * (x2-x) + y2 * (x - x1)--------------------------------          x2 - x1

Something like that?

EDIT: where x is the query value
tusaki

Junior Devvie

Medals: 1

 « Reply #2 - Posted 2006-01-29 15:10:17 »

Yes, indeed.

 1  2  3 160 * (0.625-0.5) + 98 * (0.5 - 0.4)----------------------------------------------   = 132.450.625-0.4

Now the main problem is not actually this final step. The main problem is finding x1 and x2, when given x, in the set. It is not actually a problem per-se, but I need the most optimized way of setting up the data structure to contain the interpolation and to quickly find x1/x2.
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1002
Projects: 4
Exp: 16 years

 « Reply #3 - Posted 2006-01-29 16:40:03 »

Well  you are already finding the right index by recursion. That method will be the bottleneck here. I have the feeling there are a too much checks. Then you enter the recursive method, your are checking if the values are between v[0] and v[v.length-1]. You do this check every recursion. That is not needed, as you've checked this before, and are only calling the method *if* you have valid input. So IMHO, without running the code, I'd say you can get rid of 2 if-statements.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1002
Projects: 4
Exp: 16 years

 « Reply #4 - Posted 2006-01-29 16:46:26 »

And ehm... your normalize-methods don't make much sense

You have to find the min/max values, then
 1  2 foreach(value)   value = (value-min) / (max-min);

Your current code just scales them, not transforming them into the range 0..1 like the documentation says.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
tusaki

Junior Devvie

Medals: 1

 « Reply #5 - Posted 2006-01-29 16:59:14 »

And ehm... your normalize-methods don't make much sense

You have to find the min/max values, then
 1  2 foreach(value)   value = (value-min) / (max-min);

Your current code just scales them, not transforming them into the range 0..1 like the documentation says.

that's on purpose. but perhaps I shouldn't call it 'normalize'... ;-)
basically I use it to scale things like color information. so, I might have an interpolation containing the values 124,2,54,230 for example. I scale them to 0.0f - 1.0f , knowing that the maximum value is 255.0f (which is not in the set). A true normalize method would pick 230 as the maximum value (and take into account the minumum value, 2), because that is the maximum value present in the set.
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1002
Projects: 4
Exp: 16 years

 « Reply #6 - Posted 2006-01-29 17:05:20 »

Ah, you're working on that particle-engine.

You know, when you have less than like 8 keys/values (I don't know the threshold), it's actually much faster to do everything in a plain loop.

 1  2  3  4  5 int index = -1;for(...)   if(searchVal >= v[i])      index = i;      break;

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
tusaki

Junior Devvie

Medals: 1

 « Reply #7 - Posted 2006-01-29 17:48:37 »

However, I've been researching Binary Search Trees today as an alternative to the arrays of floats. And my new version has a 600% increase in speed.

To be specific, I've implemented Splay Trees .

Quote
A splay tree is a self-balancing binary search tree with the additional unusual property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log(n)) amortized time. For many non-uniform sequences of operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Sleator and Robert Tarjan.
http://en.wikipedia.org/wiki/Splay_tree

When I've finalized my testing and cleaned up & commented the code a bit, I will post the splaying version to this thread.
Pages: [1]
 ignore  |  Print

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

 KaiHH (25 views) 2015-07-07 11:39:58 deepthought (55 views) 2015-06-30 15:39:44 deepthought (58 views) 2015-06-30 15:39:09 deepthought (67 views) 2015-06-30 15:36:52 Za\'Anzabar (45 views) 2015-06-29 05:44:54 TritonDreyja (51 views) 2015-06-24 17:10:40 CopyableCougar4 (53 views) 2015-06-23 00:34:45 BurntPizza (59 views) 2015-06-21 20:36:46 cookiecompiler (100 views) 2015-06-11 15:42:53 cookiecompiler (58 views) 2015-06-11 15:41:14
 princec 31x orangepascal 22x wessles 19x CopyableCougar4 19x EgonOlsen 18x opiop65 18x theagentd 18x BurntPizza 17x ags1 16x nsigma 15x Riven 14x KaiHH 13x KevinWorkman 11x sunburn 11x Jesse 11x SauronWatchesYou 10x
 How 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:21Resources for WIP gamesby kpars2014-12-18 10:26:14
 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