Jump to content

  • Log In with Google      Sign In   
  • Create Account

Evaluators (polynomial & graph)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
1 reply to this topic

#1   Members   -  Reputation: 522


Posted 07 January 2014 - 09:49 AM

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, 07 January 2014 - 05:29 PM.

#2   Members   -  Reputation: 522


Posted 07 January 2014 - 05:48 PM

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?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.