Jump to content
  • Advertisement
Sign in to follow this  

Evaluators (polynomial & graph)

This topic is 2108 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to design (and hopefully implement later on) an evaluator system which would work either with polynomial based data or either with point based graph data ( list of [x,y] pairs from which interpolated values are calculated). So, for quick and dirty fade-in/out one can use simple polynomial data to quickly generate linear/exponential/... curves, while graph data points can be used for complex "animations". Evaluators are used by particle and audio system and based on profiling, they take a healthy chunk of the update time.


I already have a working point based evaluator:

- supports arbitrary number of points (data ptr + count)

- basic logic is that based on input relative x value, I have to find corresponding x-1 and x+1 pairs, and interpolate y between them

- float points are compressed into words to reduce data size and to speed up look-up

- constant / linear / step / bezier 


What I don't like about it:

- data layout; even though data for multiple evaluators is packed together, it is still in two places (eval object + data*)

- the "find neighboring  points" is currently a for loop, but as points can be unequally spread out, I don't have any other sane way to find them and since number of points is actually low (4-16) I didn't bother with anything but linear search

- logic & data layout; no sensible way to simd optimize this


Initially I had a static array of points but with a large number of evaluators the data grew fast. The data* + count solved that by a large factor. All in all, this is an ok-ish solution, I'm just wondering if there is a better way to handle it (for simd). Regarding the simd optimization, it seems that optimizing one evaluator is not really practical (or even "possible"). It seems more logical to try to run multiple evaluators at once, but to be honest I'm kinda stuck here...


The new polynomial part would be easy to add, the number of constants (degree) would be low, probably 4 or so, so a float vector would be enough to store data (c0 + c1*x + c2*xx + c3*xxx). The data would be used exclusively (its either polynomial or point list).  So, the big question is how to combine/structure both parts of data and how to make the logic simd-able?

Edited by zfvesoljc

Share this post

Link to post
Share on other sites

Optimizing polynomial evaluator seems possible only in a way to solve multiple evaluators at once, as mentioned before. Second "downer"  is that lookup value x has to be same for all evaluators. So, something as:

class QuadPolynomEvaluator {
   vec4 PolyConst[4]; // vec4 for polynomial of degree 4, array of 4 for 4 evaluators (e0, e1, e2, e3)
   // @ either build time or load time
   void SetEvalData(uint idx, float c0, float c1, float c2, float c3)
      // quick and dirty way of filling components; or use "proper" store/splat/swizzle
      float* data= (float*)&PolyConst;
      data[ 0*4 + idx ] = c0;
      data[ 1*4 + idx ] = c1;
      data[ 2*4 + idx ] = c2;
      data[ 3*4 + idx ] = c3;
      // PolyConst[0] = e0.c0, e1.c0, e2.c0, e3.c0
      // PolyConst[1] = e0.c1, e1.c1, e2.c1, e3.c1
      // PolyConst[2] = e0.c2, e1.c2, e2.c2, e3.c2
      // PolyConst[3] = e0.c3, e1.c3, e2.c3, e3.c3
   vec4 Evaluate(float x)
      vec4 vx = vec4(x);
      // result.x = (e0.c0) + (e0.c1 * x) + (e0.c2 * pow(x, 2.0f)) + (e0.c2 * pow(x, 3.0f));
      vec4 result = PolyConst[0];
      result = vec4add( result, vec4mul( PolyConst[1], vx ) );
      result = vec4add( result, vec4mul( PolyConst[2], vec4pow( vx, vec4(2.0f) ) ) );
      result = vec4add( result, vec4mul( PolyConst[3], vec4pow( vx, vec4(3.0f) ) ) );
      return result;

Makes sense?

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!