Guest User

KramerPath

a guest
May 18th, 2013
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.59 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment