Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

KramerPath

By: a guest on May 18th, 2013  |  syntax: Java  |  size: 6.59 KB  |  views: 31  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. package com.axe.path;
  2.  
  3. import com.axe.core.Attribute;
  4. import com.axe.io.InputModel;
  5. import com.axe.io.OutputModel;
  6. import com.axe.math.Numbers;
  7. import com.axe.math.Scalari;
  8.  
  9. /**
  10.  * http://www.reddit.com/r/gamedev/comments/1ei88i/very_fast_2d_interpolation/
  11.  *
  12.  * @author Philip Diffenderfer
  13.  *
  14.  * @param <T>
  15.  */
  16. public class KramerPath<T> implements Path<T>
  17. {
  18.        
  19.         public static final float DEFAULT_LOOSENESS = 0.0575f;
  20.        
  21.         protected Attribute<T>[] points;
  22.         protected Attribute<T> temp0;
  23.         protected Attribute<T> temp1;
  24.         protected int depth;
  25.         protected float looseness;
  26.         protected boolean loops;
  27.         protected float roughness;
  28.        
  29.         public KramerPath()
  30.         {
  31.         }
  32.        
  33.         public KramerPath( int depth, boolean loops, Attribute<T> ... points )
  34.         {
  35.                 this( depth, loops, DEFAULT_LOOSENESS, 0.0f, points );
  36.         }
  37.        
  38.         public KramerPath( int depth, boolean loops, float looseness, Attribute<T> ... points )
  39.         {
  40.                 this( depth, loops, looseness, 0.0f, points );
  41.         }
  42.        
  43.         public KramerPath( float roughness, boolean loops, Attribute<T> ... points )
  44.         {
  45.                 this( 0, loops, DEFAULT_LOOSENESS, roughness, points );
  46.         }
  47.        
  48.         public KramerPath( float roughness, boolean loops, float looseness, Attribute<T> ... points )
  49.         {
  50.                 this( 0, loops, looseness, roughness, points );
  51.         }
  52.        
  53.         protected KramerPath( int depth, boolean loops, float looseness, float roughness, Attribute<T> ... points )
  54.         {
  55.                 this.depth = depth;
  56.                 this.loops = loops;
  57.                 this.looseness = looseness;
  58.                 this.roughness = roughness;
  59.                 this.points = points;
  60.                 this.temp0 = points[0].create();
  61.                 this.temp1 = points[0].create();
  62.         }
  63.        
  64.         @Override
  65.         public T set(Attribute<T> subject, float delta)
  66.         {
  67.                 final int n = points.length;
  68.                 final float a = delta * n;
  69.                 final int i = Scalari.clamp( (int)a, 0, n - 1 );
  70.                 float d = a - i;
  71.                
  72.                 if (depth != 0)
  73.                 {
  74.                         getPointWithExactDepth( i, d, subject );
  75.                 }
  76.                 else
  77.                 {
  78.                         getPointWithRoughness( i, d, subject );
  79.                 }
  80.                
  81.                 return subject.get();
  82.         }
  83.        
  84.         public void getPointWithExactDepth( int i, float d, Attribute<T> subject )
  85.         {
  86.                 // v0 and v5 are used to calculate the next v1 or v4, at the next level.
  87.                 T v0 = points[ getActualIndex( i - 2 ) ].get();
  88.                 T v1 = points[ getActualIndex( i - 1 ) ].get();
  89.                 T v2 = points[ getActualIndex( i ) ].get();
  90.                 T v3 = points[ getActualIndex( i + 1 ) ].get();
  91.                 T v4 = points[ getActualIndex( i + 2 ) ].get();
  92.                 T v5 = points[ getActualIndex( i + 3 ) ].get();
  93.                
  94.                 int k = depth;
  95.  
  96.                 while (--k >= 0)
  97.                 {
  98.                         // Get mid point
  99.                         T mid = getPoint( v1, v2, v3, v4 );
  100.                        
  101.                         // If the desired point is closer to v2...
  102.                         if (d < 0.5f)
  103.                         {
  104.                                 // shift all surrounding points one-level closer to v2
  105.                                 if (k == 0)
  106.                                 {
  107.                                         v3 = mid;
  108.                                 }
  109.                                 else
  110.                                 {
  111.                                         T newEnd = v1;
  112.                                         v5 = v4;
  113.                                         v4 = v3;
  114.                                         v3 = mid;
  115.                                         v1 = getPoint( v0, v1, v2, v3 );
  116.                                         v0 = newEnd;
  117.                                 }
  118.                                 // adjust d so it's between 0.0 an 1.0
  119.                                 d = d * 2.0f;
  120.                         }
  121.                         // else, the desired point is closer to v3...
  122.                         else
  123.                         {
  124.                                 // shift all surrounding points one-level closer to v3
  125.                                 if (k == 0)
  126.                                 {
  127.                                         v2 = mid;
  128.                                 }
  129.                                 else
  130.                                 {
  131.                                         T newEnd = v4;
  132.                                         v0 = v1;
  133.                                         v1 = v2;
  134.                                         v2 = mid;
  135.                                         v4 = getPoint( v2, v3, v4, v5 );
  136.                                         v5 = newEnd;
  137.                                 }
  138.                                 // adjust d so it's between 0.0 an 1.0
  139.                                 d = (d - 0.5f) * 2.0f;
  140.                         }
  141.                 }
  142.                
  143.                 // subject = (v3 - v2) * d + v2
  144.                 subject.interpolate( v2, v3, d );
  145.         }
  146.        
  147.         public void getPointWithRoughness( int i, float d, Attribute<T> subject )
  148.         {
  149.                 // v0 and v5 are used to calculate the next v1 or v4, at the next level.
  150.                 T v0 = points[ getActualIndex( i - 2 ) ].get();
  151.                 T v1 = points[ getActualIndex( i - 1 ) ].get();
  152.                 T v2 = points[ getActualIndex( i ) ].get();
  153.                 T v3 = points[ getActualIndex( i + 1 ) ].get();
  154.                 T v4 = points[ getActualIndex( i + 2 ) ].get();
  155.                 T v5 = points[ getActualIndex( i + 3 ) ].get();
  156.  
  157.                 for (;;)
  158.                 {
  159.                         // Get mid point
  160.                         T mid = getPoint( v1, v2, v3, v4 );
  161.                        
  162.                         // if distance from mid to (v2->v3) is <= roughness, break
  163.                         // calculate the distance between all three points to form a triangle,
  164.                         // with the distances determine the perimeter then area. Use the
  165.                         //      area = 0.5 * b * h formula to calculate height.
  166.                         float a = getDistance( v2, v3 );
  167.                         float b = getDistance( mid, v2 );
  168.                         float c = getDistance( mid, v3 );
  169.                         float p = (a + b + c) * 0.5f;
  170.                         float area = Numbers.sqrt( p * (p - a) * (p - b) * (p - c) );
  171.                         float height = area * 2.0f / a;
  172.                        
  173.                         if (height <= roughness)
  174.                         {
  175.                                 break;
  176.                         }
  177.                        
  178.                         // If the desired point is closer to v2...
  179.                         if (d < 0.5f)
  180.                         {
  181.                                 // shift all surrounding points one-level closer to v2
  182.                                 T newEnd = v1;
  183.                                 v5 = v4;
  184.                                 v4 = v3;
  185.                                 v3 = mid;
  186.                                 v1 = getPoint( v0, v1, v2, v3 );
  187.                                 v0 = newEnd;
  188.                                 // adjust d so it's between 0.0 an 1.0
  189.                                 d = d * 2.0f;
  190.                         }
  191.                         // else, the desired point is closer to v3...
  192.                         else
  193.                         {
  194.                                 // shift all surrounding points one-level closer to v3
  195.                                 T newEnd = v4;
  196.                                 v0 = v1;
  197.                                 v1 = v2;
  198.                                 v2 = mid;
  199.                                 v4 = getPoint( v2, v3, v4, v5 );
  200.                                 v5 = newEnd;
  201.                                 // adjust d so it's between 0.0 an 1.0
  202.                                 d = (d - 0.5f) * 2.0f;
  203.                         }
  204.                 }
  205.                
  206.                 // subject = (v3 - v2) * d + v2
  207.                 subject.interpolate( v2, v3, d );
  208.         }
  209.        
  210.         public float getDistance( T a, T b )
  211.         {
  212.                 temp0.set( a );
  213.        
  214.                 return temp0.distance( b );
  215.         }
  216.        
  217.         public T getPoint( T v1, T v2, T v3, T v4 )
  218.         {
  219.                 // p = (0.5f + looseness) * (v2 + v3) - looseness * (v1 + v4)
  220.                
  221.                 temp0.set( v2 );
  222.                 temp0.add( v3, 1f );
  223.                 temp0.scale( 0.5f + looseness );
  224.                
  225.                 temp1.set( v1 );
  226.                 temp1.add( v4, 1f );
  227.                 temp0.add( temp1.get(), -looseness );
  228.                
  229.                 return temp0.clone();
  230.         }
  231.        
  232.         public int getActualIndex( int index )
  233.         {
  234.                 final int n = points.length;
  235.                
  236.                 return ( loops ? (index + n) % n : Scalari.clamp( index, 0, n - 1 ) );
  237.         }
  238.  
  239.         @Override
  240.         public int getAttributeCount()
  241.         {
  242.                 return points.length;
  243.         }
  244.  
  245.         @Override
  246.         public Attribute<T> getAttribute(int index)
  247.         {
  248.                 return points[ index ];
  249.         }
  250.  
  251.         @Override
  252.         public T get(int index)
  253.         {
  254.                 return points[ index ].get();
  255.         }
  256.        
  257.         public Attribute<T>[] points()
  258.         {
  259.                 return points;
  260.         }
  261.  
  262.         @Override
  263.         public void read( InputModel input )
  264.         {
  265.                 depth = input.readInt( "depth" );
  266.                 loops = input.readBoolean( "loops" );
  267.                 looseness = input.readFloat( "looseness" );
  268.                 points = input.readModelArray( "point", "point-type" );
  269.                 temp0 = points[0].create();
  270.                 temp1 = points[0].create();
  271.         }
  272.  
  273.         @Override
  274.         public void write( OutputModel output )
  275.         {
  276.                 output.write( "depth", depth );
  277.                 output.write( "loops", loops );
  278.                 output.write( "looseness", looseness );
  279.                 output.writeModelArray( "point", points, "point-type" );
  280.         }
  281.        
  282. }