 # 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;
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