Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) 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 3354 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

« JGO Overlord »

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

« JGO Overlord »

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

« JGO Overlord »

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

 EgonOlsen (60 views) 2018-06-10 19:43:48 EgonOlsen (42 views) 2018-06-10 19:43:44 EgonOlsen (61 views) 2018-06-10 19:43:20 DesertCoockie (241 views) 2018-05-13 18:23:11 nelsongames (142 views) 2018-04-24 18:15:36 nelsongames (141 views) 2018-04-24 18:14:32 ivj94 (883 views) 2018-03-24 14:47:39 ivj94 (144 views) 2018-03-24 14:46:31 ivj94 (795 views) 2018-03-24 14:43:53 Solater (159 views) 2018-03-17 05:04:08
 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