matrefeytontias

Reverse arc-length parameterization implementation

Sep 20th, 2017
599
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // This could have as many coordinates as you want, but make sure
  2. // to change the distance function accordingly
  3. typedef Position = { x:Float, y:Float };
  4.  
  5. typedef Parametric = Float -> Position;
  6.  
  7. // Computes a reverse arc-length parameterization to solve the
  8. // travel speed problem and give samples with O(1) complexity.
  9. // For the sake of simplicity, the code is somewhat unoptimized.
  10. // The initialization stage is O(n^2) but could be brought to
  11. // O(n log(n)).
  12. class ArcSampler
  13. {
  14.     private var samples:Array<Position> = new Array<Position>();
  15.     private var indices:Array<Int> = new Array<Int>();
  16.    
  17.     // Distance between two 2D points
  18.     static private function distance(a:Position, b:Position) : Float
  19.     {
  20.         var x = a.x - b.x, y = a.y - b.y;
  21.         return Math.sqrt(x * x + y * y);
  22.     }
  23.    
  24.     // f is the parametrisation of the curve, ie a function of time
  25.     // steps is the amount of steps, ie the number of samples - 1
  26.     // t will be in the closed interval [lowt, hight]
  27.     public function new(f:Parametric, steps:Int, ?lowt = 0., ?hight = 1.)
  28.     {
  29.         var lengths = new Array<Float>();
  30.         // Convenience function to map [0, 1] to [lowt, hight] linearly
  31.         var range = function (t:Float) return lowt + t * (hight - lowt);
  32.  
  33.         // Direct application of the reverse arc-length parameterization algorithm
  34.         lengths.push(0);
  35.         samples.push(f(range(0)));
  36.         if(steps < 1)
  37.             throw "ArcSampler : must use at least one step";
  38.         for(i in 1 ... steps + 1)
  39.         {
  40.             samples.push(f(range(i / steps)));
  41.             lengths.push(distance(samples[i], samples[i-1]) + lengths[i-1]);
  42.         }
  43.         for(i in 1 ... steps + 1)
  44.             lengths[i] /= lengths[steps];
  45.  
  46.         indices[0] = 0;
  47.         for(i in 1 ... steps + 1)
  48.         {
  49.             var s = i / steps;
  50.             // Index of the highest length that is less or equal to s
  51.             // Can be optimized with a binary search instead
  52.             var j = lengths.filter(function(l) return l <= s).length - 1;
  53.             indices.push(j);
  54.         }
  55.     }
  56.  
  57.     // Linear interpolation with factor t between a and b
  58.     static private function lerp(a:Position, b:Position, t:Float) : Position
  59.     {
  60.         return { x:(1 - t) * a.x + t * b.x, y:(1 - t) * a.y + t * b.y};
  61.     }
  62.  
  63.     // Returns the point at length s% of the total length of the curve
  64.     // using the reverse arc-length parameterization
  65.     public function curve(s:Float) : Position
  66.     {
  67.         if(s < 0 || s > 1)
  68.             throw "Invalid s parameter : must be in [0, 1]";
  69.         if(s == 1)
  70.             return samples[samples.length - 1];
  71.         var i = Std.int(s * indices.length);
  72.         var t = indices[i];
  73.         return lerp(samples[t], samples[t+1], s * indices.length - i);
  74.     }
  75. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×