Distorted Android

///////////////////////////////////////////////////////////////////////////////////////////////////

// Copyright 2016 Leszek Koltunski                                                               //

//                                                                                               //

// This file is part of Distorted.                                                               //

//                                                                                               //

// Distorted is free software: you can redistribute it and/or modify                             //

// it under the terms of the GNU General Public License as published by                          //

// the Free Software Foundation, either version 2 of the License, or                             //

// (at your option) any later version.                                                           //

//                                                                                               //

// Distorted is distributed in the hope that it will be useful,                                  //

// but WITHOUT ANY WARRANTY; without even the implied warranty of                                //

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the                                 //

// GNU General Public License for more details.                                                  //

//                                                                                               //

// You should have received a copy of the GNU General Public License                             //

// along with Distorted.  If not, see <http://www.gnu.org/licenses/>.                            //

///////////////////////////////////////////////////////////////////////////////////////////////////

package org.distorted.library.type;

import java.util.Random;

import java.util.Vector;

///////////////////////////////////////////////////////////////////////////////////////////////////

/** A class to interpolate between a List of Static{1,2,3,4}Ds.

* <p><ul>

* <li>if there is only one Point, just jump to it.

* <li>if there are two Points, linearly bounce between them

* <li>if there are more, interpolate a loop (or a path!) between them.

* </ul>

*/

// The way Interpolation between more than 2 Points is done:

// 

// Def: let w[i] = (w[i](x), w[i](y), w[i](z)) be the direction and speed we have to be flying at Point P[i]

//

// time it takes to fly though one segment v[i] --> v[i+1] : 0.0 --> 1.0

// w[i] should be parallel to v[i+1] - v[i-1]   (cyclic notation)

// |w[i]| proportional to | P[i]-P[i+1] |

//

// Given that the flight route (X(t), Y(t), Z(t)) from P(i) to P(i+1)  (0<=t<=1) has to satisfy

// X(0) = P[i  ](x), Y(0)=P[i  ](y), Z(0)=P[i  ](z), X'(0) = w[i  ](x), Y'(0) = w[i  ](y), Z'(0) = w[i  ](z)

// X(1) = P[i+1](x), Y(1)=P[i+1](y), Z(1)=P[i+1](z), X'(1) = w[i+1](x), Y'(1) = w[i+1](y), Z'(1) = w[i+1](z)

//

// we have the solution:  X(t) = at^3 + bt^2 + ct + d where

// a =  2*P[i](x) +   w[i](x) - 2*P[i+1](x) + w[i+1](x)

// b = -3*P[i](x) - 2*w[i](x) + 3*P[i+1](x) - w[i+1](x)

// c = w[i](x)<br>

// d = P[i](x)

//

// and similarly Y(t) and Z(t).

public abstract class Dynamic

  {

  /**

   * One revolution takes us from the first vector to the last and back to first through the shortest path. 

   */

  public static final int MODE_LOOP = 0; 

  /**

   * We come back from the last to the first vector through the same way we got there.

   */

  public static final int MODE_PATH = 1; 

  /**

   * We just jump back from the last point to the first.

   */

  public static final int MODE_JUMP = 2; 

  protected static Random mRnd = new Random();

  protected static final int NUM_NOISE = 5; // used iff mNoise>0.0. Number of intermediary points between each pair of adjacent vectors

                                            // where we randomize noise factors to make the way between the two vectors not so smooth.

  protected int mDimension;

  protected int numPoints;

  protected int mVecCurr;    

  protected boolean cacheDirty; // VectorCache not up to date

  protected int mMode;          // LOOP, PATH or JUMP

  protected long mDuration;     // number of milliseconds it takes to do a full loop/path from first vector to the last and back to the first

  protected float mCount;       // number of loops/paths we will do; mCount = 1.5 means we go from the first vector to the last, back to first, and to the last again. 

  protected float mNoise;       // how 'smooth' our path form each vector to the next is. mNoise = 0.0 (min) --> completely smooth; mNoise==1.0 (max) --> very uneven

  protected class VectorNoise

    {

    float[][] n;

    VectorNoise(int dim)

      {

      n = new float[dim][NUM_NOISE];

      n[0][0] = mRnd.nextFloat();

      for(int i=1; i<NUM_NOISE; i++) n[0][i] = n[0][i-1]+mRnd.nextFloat();

      float sum = n[0][NUM_NOISE-1] + mRnd.nextFloat();

      for(int i=0; i<NUM_NOISE; i++) n[0][i] /=sum;

      for(int j=1; j<dim; j++)

        {

        for(int i=0; i<NUM_NOISE; i++) n[j][i] = mRnd.nextFloat()-0.5f;

        }

      }

    }

  protected Vector<VectorNoise> vn;

  protected float[] mFactor;

  protected float[][] baseV;

  private float[] buffer;

  ///////////////////////////////////////////////////////////////////////////////////////////////////

  // the coefficients of the X(t), Y(t) and Z(t) polynomials: X(t) = ax*T^3 + bx*T^2 + cx*t + dx  etc.

  // (tangent) is the vector tangent to the path.

  // (cached) is the original vector from vv (copied here so when interpolating we can see if it is

  // still valid and if not - rebuild the Cache

  protected class VectorCache

    {

    float[] a;

    float[] b;

    float[] c;

    float[] d;

    float[] tangent;

    float[] cached;

    VectorCache(int dim)

      {

      a = new float[dim];

      b = new float[dim];

      c = new float[dim];

      d = new float[dim];

      tangent = new float[dim];

      cached = new float[dim];

      }

    }

  protected Vector<VectorCache> vc;

  protected VectorCache tmp1, tmp2;

///////////////////////////////////////////////////////////////////////////////////////////////////

// hide this from Javadoc

  protected Dynamic()

    {

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

  protected Dynamic(int duration, float count, int dimension)

    {

    vc = new Vector<>();

    vn = null;

    numPoints = 0;

    cacheDirty = false;

    mMode = MODE_LOOP;

    mDuration = duration;

    mCount = count;

    mDimension = dimension;

    baseV = new float[mDimension][mDimension];

    buffer= new float[mDimension];

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

  public void interpolateMain(float[] buffer, int offset, long currentDuration)

    {

    if( mDuration<=0.0f ) 

      {

      interpolate(buffer,offset,mCount-(int)mCount);  

      }

    else

      {

      float x = (float)currentDuration/mDuration;

      if( x<=mCount || mCount<=0.0f )

        {

        interpolate(buffer,offset,x-(int)x);

        }

      }

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

  public boolean interpolateMain(float[] buffer, int offset, long currentDuration, long step)

    {

    if( mDuration<=0.0f ) 

      {

      interpolate(buffer,offset,mCount-(int)mCount);

      return false;

      }

    float x = (float)currentDuration/mDuration;

    if( x<=mCount || mCount<=0.0f )

      {

      interpolate(buffer,offset,x-(int)x);

      if( currentDuration+step > mDuration*mCount && mCount>0.0f )

        {

        interpolate(buffer,offset,mCount-(int)mCount);

        return true;

        }

      }

    return false;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

  protected float noise(float time,int vecNum)

    {

    float lower, upper, len;

    float d = time*(NUM_NOISE+1);

    int index = (int)d;

    if( index>=NUM_NOISE+1 ) index=NUM_NOISE;

    VectorNoise tmpN = vn.elementAt(vecNum);

    float t = d-index;

    t = t*t*(3-2*t);

    switch(index)

      {

      case 0        : for(int i=0;i<mDimension-1;i++) mFactor[i] = mNoise*tmpN.n[i+1][0]*t;

                      return time + mNoise*(d*tmpN.n[0][0]-time);

      case NUM_NOISE: for(int i=0;i<mDimension-1;i++) mFactor[i] = mNoise*tmpN.n[i+1][NUM_NOISE-1]*(1-t);

                      len = ((float)NUM_NOISE)/(NUM_NOISE+1);

                      lower = len + mNoise*(tmpN.n[0][NUM_NOISE-1]-len);

                      return (1.0f-lower)*(d-NUM_NOISE) + lower;

      default       : float ya,yb;

                      for(int i=0;i<mDimension-1;i++)

                        {

                        yb = tmpN.n[i+1][index  ];

                        ya = tmpN.n[i+1][index-1];

                        mFactor[i] = mNoise*((yb-ya)*t+ya);

                        }

                      len = ((float)index)/(NUM_NOISE+1);

                      lower = len + mNoise*(tmpN.n[0][index-1]-len);

                      len = ((float)index+1)/(NUM_NOISE+1);

                      upper = len + mNoise*(tmpN.n[0][index  ]-len);

                      return (upper-lower)*(d-index) + lower;

      }

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// debugging only

  private void printBase(String str)

    {

    String s;

    float t;

    for(int i=0; i<mDimension; i++)

      {

      s = "";

      for(int j=0; j<mDimension; j++)

        {

        t = ((int)(1000*baseV[i][j]))/(1000.0f);

        s+=(" "+t);

        }

      android.util.Log.e("dynamic", str+" base "+i+" : " + s);

      }

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// debugging only

  private void checkBase()

    {

    float tmp;

    for(int i=0; i<mDimension; i++)

      for(int j=i+1; j<mDimension; j++)

        {

        tmp = 0.0f;

        for(int k=0; k<mDimension; k++)

          {

          tmp += baseV[i][k]*baseV[j][k];

          }

        android.util.Log.e("dynamic", "vectors "+i+" and "+j+" : "+tmp);

        }

    for(int i=0; i<mDimension; i++)

      {

      tmp = 0.0f;

      for(int k=0; k<mDimension; k++)

        {

        tmp += baseV[i][k]*baseV[i][k];

        }

      android.util.Log.e("dynamic", "length of vector "+i+" : "+Math.sqrt(tmp));

      }

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// helper function in case we are interpolating through exactly 2 points

  protected void computeOrthonormalBase2(Static1D curr, Static1D next)

    {

    switch(mDimension)

      {

      case 1: baseV[0][0] = (next.x-curr.x);

              break;

      case 2: Static2D curr2 = (Static2D)curr;

              Static2D next2 = (Static2D)next;

              baseV[0][0] = (next2.x-curr2.x);

              baseV[0][1] = (next2.y-curr2.y);

              break;

      case 3: Static3D curr3 = (Static3D)curr;

              Static3D next3 = (Static3D)next;

              baseV[0][0] = (next3.x-curr3.x);

              baseV[0][1] = (next3.y-curr3.y);

              baseV[0][2] = (next3.z-curr3.z);

              break;

      case 4: Static4D curr4 = (Static4D)curr;

              Static4D next4 = (Static4D)next;

              baseV[0][0] = (next4.x-curr4.x);

              baseV[0][1] = (next4.y-curr4.y);

              baseV[0][2] = (next4.z-curr4.z);

              baseV[0][3] = (next4.w-curr4.w);

              break;

      case 5: Static5D curr5 = (Static5D)curr;

              Static5D next5 = (Static5D)next;

              baseV[0][0] = (next5.x-curr5.x);

              baseV[0][1] = (next5.y-curr5.y);

              baseV[0][2] = (next5.z-curr5.z);

              baseV[0][3] = (next5.w-curr5.w);

              baseV[0][4] = (next5.v-curr5.v);

              break;

      default: throw new RuntimeException("Unsupported dimension");

      }

    if( baseV[0][0] == 0.0f )

      {

      baseV[1][0] = 1.0f;

      baseV[1][1] = 0.0f;

      }

    else

      {

      baseV[1][0] = 0.0f;

      baseV[1][1] = 1.0f;

      }

    for(int i=2; i<mDimension; i++)

      {

      baseV[1][i] = 0.0f;

      }

    computeOrthonormalBase();

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// helper function in case we are interpolating through more than 2 points

  protected void computeOrthonormalBaseMore(float time,VectorCache vc)

    {

    for(int i=0; i<mDimension; i++)

      {

      baseV[0][i] = (3*vc.a[i]*time+2*vc.b[i])*time+vc.c[i];

      baseV[1][i] =  6*vc.a[i]*time+2*vc.b[i];

      }

    computeOrthonormalBase();

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// When this function gets called, baseV[0] and baseV[1] should have been filled with two mDimension-al

// vectors. This function then fills the rest of the baseV array with a mDimension-al Orthonormal base.

// (mDimension-2 vectors, pairwise orthogonal to each other and to the original 2). The function always

// leaves base[0] alone but generally speaking must adjust base[1] to make it orthogonal to base[0]!

// The whole baseV is then used to compute Noise.

//

// When computing noise of a point travelling along a N-dimensional path, there are three cases:

// a) we may be interpolating through 1 point, i.e. standing in place - nothing to do in this case

// b) we may be interpolating through 2 points, i.e. travelling along a straight line between them -

//    then pass the velocity vector in baseV[0] and anything linearly independent in base[1].

//    The output will then be discontinuous in dimensions>2 (sad corollary from the Hairy Ball Theorem)

//    but we don't care - we are travelling along a straight line, so velocity (aka baseV[0]!) does

//    not change.

// c) we may be interpolating through more than 2 points. Then interpolation formulas ensure the path

//    will never be a straight line, even locally -> we can pass in baseV[0] and baseV[1] the velocity

//    and the acceleration (first and second derivatives of the path) which are then guaranteed to be

//    linearly independent. Then we can ensure this is continuous in dimensions <=4. This leaves

//    dimension 5 (ATM WAVE is 5-dimensional) discontinuous -> WAVE will suffer from chaotic noise.

//

// Bear in mind here the 'normal' in 'orthonormal' means 'length equal to the length of the original

// velocity vector' (rather than the standard 1)

  protected void computeOrthonormalBase()

    {

    int non_zeros=0;

    int last_non_zero=-1;

    float value;

    for(int i=0; i<mDimension; i++)

      {

      value = baseV[0][i];

      if( value != 0.0f )

        {

        non_zeros++;

        last_non_zero=i;

        }

      }

                         // velocity is the 0 vector -> two consecutive points we are interpolating

    if( non_zeros==0 )   // through are identical -> no noise, set the base to 0 vectors.

      {

      for(int i=0; i<mDimension-1; i++)

        for(int j=0; j<mDimension; j++)

          baseV[i+1][j]= 0.0f;

      }

    else

      {

      for(int i=0; i<mDimension-1; i++)

        for(int j=0; j<mDimension; j++)

          {

          if( (i<last_non_zero && j==i) || (i>=last_non_zero && j==i+1) )

            baseV[i+1][j]= baseV[0][last_non_zero];

          else

            baseV[i+1][j]= 0.0f;

          }

      // That's it if velocity vector is already one of the standard orthonormal

      // vectors. Otherwise (i.e. non_zeros>1) velocity is linearly independent

      // to what's in baseV right now and we can use (modified!) Gram-Schmidt.

      //

      // b[0] = b[0]

      // b[1] = b[1] - (<b[1],b[0]>/<b[0],b[0]>)*b[0]

      // b[2] = b[2] - (<b[2],b[0]>/<b[0],b[0]>)*b[0] - (<b[2],b[1]>/<b[1],b[1]>)*b[1]

      // b[3] = b[3] - (<b[3],b[0]>/<b[0],b[0]>)*b[0] - (<b[3],b[1]>/<b[1],b[1]>)*b[1] - (<b[3],b[2]>/<b[2],b[2]>)*b[2]

      //

      // then b[i] = b[i] / |b[i]|

      if( non_zeros>1 )

        {

        float tmp;

        for(int i=1; i<mDimension; i++)

          {

          buffer[i-1]=0.0f;

          for(int k=0; k<mDimension; k++)

            {

            value = baseV[i-1][k];

            buffer[i-1] += value*value;

            }

          for(int j=0; j<i; j++)

            {

            tmp = 0.0f;

            for(int k=0;k<mDimension; k++)

              {

              tmp += baseV[i][k]*baseV[j][k];

              }

            tmp /= buffer[j];

            for(int k=0;k<mDimension; k++)

              {

              baseV[i][k] -= tmp*baseV[j][k];

              }

            }

          }

        buffer[mDimension-1]=0.0f;

        for(int k=0; k<mDimension; k++)

          {

          value = baseV[mDimension-1][k];

          buffer[mDimension-1] += value*value;

          }

        for(int i=1; i<mDimension; i++)

          {

          tmp = (float)Math.sqrt(buffer[0]/buffer[i]);

          for(int k=0;k<mDimension; k++)

            {

            baseV[i][k] *= tmp;

            }

          }

        }

      }

    //printBase("end");

    //checkBase();

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// internal debugging only!

  public String print()

    {

    return "duration="+mDuration+" count="+mCount+" Noise="+mNoise+" numVectors="+numPoints+" mMode="+mMode;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

  abstract void interpolate(float[] buffer, int offset, float time);

///////////////////////////////////////////////////////////////////////////////////////////////////

// PUBLIC API

///////////////////////////////////////////////////////////////////////////////////////////////////

/**

 * Sets the mode of the interpolation to Loop, Path or Jump.

 * <ul>

 * <li>Loop is when we go from the first point all the way to the last, and the back to the first through 

 * the shortest way.

 * <li>Path is when we come back from the last point back to the first the same way we got there.

 * <li>Jump is when we go from first to last and then jump back to the first.

 * </ul>

 * 

 * @param mode {@link Dynamic#MODE_LOOP}, {@link Dynamic#MODE_PATH} or {@link Dynamic#MODE_JUMP}.

 */

  public void setMode(int mode)

    {

    mMode = mode;  

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

/**

 * Returns the number of Static{1,2,3,4}Ds this Dynamic has been fed with.

 *   

 * @return the number of Static{1,2,3,4}Ds we are currently interpolating through.

 */

  public synchronized int getNumPoints()

    {

    return numPoints;  

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

/**

 * Controls how many times we want to interpolate.

 * <p>

 * Count equal to 1 means 'go from the first Static{1,2,3,4}D to the last and back'. Does not have to be an

 * integer - i.e. count=1.5 would mean 'start at the first Point, go to the last, come back to the first, 

 * go to the last again and stop'.

 * Count<=0 means 'go on interpolating indefinitely'.

 * 

 * @param count the number of times we want to interpolate between our collection of Static{1,2,3,4}Ds.

 */

  public void setCount(float count)

    {

    mCount = count;  

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

/**

 * Sets the time it takes to do one full interpolation.

 * 

 * @param duration Time, in milliseconds, it takes to do one full interpolation, i.e. go from the first 

 *                 Point to the last and back. 

 */

  public void setDuration(long duration)

    {

    mDuration = duration;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

/**

 * Sets the 'smoothness' of interpolation. 

 * <p>

 * When Noise=0 (the default), we interpolate between our Points through the most smooth path possible. 

 * Increasing noise makes the Dynamic increasingly deviate from this path, pseudo-randomly speeding

 * up and slowing down, etc.

 * 

 * @param noise The noise level. Permitted range: 0 <= noise <= 1.

 */

  public synchronized void setNoise(float noise)

    {

    if( mNoise==0.0f && noise != 0.0f && vn==null )

      {

      vn = new Vector<>();

      for(int i=0; i<numPoints; i++) vn.add(new VectorNoise(mDimension));

      if( mDimension>=2 )

        {

        mFactor = new float[mDimension-1];

        }

      }

    if( mNoise<0.0f ) mNoise = 0.0f;

    if( mNoise>1.0f ) mNoise = 1.0f;

    mNoise = noise;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// end of DistortedInterpolator

  }