3 ms·

Do you have any insight whether these reparameterizations are better (faster, more accurate) than just applying a standard solver (I'm now a huge fan of the ITP

Do you have any insight whether these reparameterizations are better (faster, more accurate) than just applying a standard solver (I'm now a huge fan of the ITP method) over numerical integration to compute arc length (Lagrange-Gauss quadrature is pretty magical)? I'm particularly interested in how it deals with cusps, which are always the most difficult cases with these numerical approaches.

ttd 5y ago
Well, the reparameterization idea is quite convenient if the operations you want to perform are more naturally expressed in the new parameter domain. Path dashing is a good example: in arc-length domain, simply take fixed steps in u (say 0.05), perform some fairly simple arithmetic to convert that u to regular old t, and then evaluate your curve at t. The new domain gives you a new space to live in, that for some things is pretty nice. For accuracy/precision, my [non-peer-reviewed] sense is that numerical methods will probably always get you more accuracy/precision. For the case I was experimenting with (path dashing, and some other related things like placement of text glyphs along the path), extreme precision didn't seem necessary. The method I ended up with (Costantini's piecewise-linear solution with K=5 pieces) meant that for each Bezier in my path, I performed some preprocessing to determine the reparameterization coefficients. With that preprocessing done, I now had an O(K) evaluation algorithm to convert the arc-length parameter u (in [0,1]) to t. Another surprisingly big bonus: there exists an equally simple O(K) inverse, i.e. given a t, return u. This allows you to easily compute the distance you've traveled along the arc, if you know where you are in the original parametric domain. To your other question, unfortunately I don't know how these techniques tend to handle cusps. I didn't get that far in my experimentation.

ttd 5y ago

Well, the reparameterization idea is quite convenient if the operations you want to perform are more naturally expressed in the new parameter domain. Path dashing is a good example: in arc-length domain, simply take fixed steps in u (say 0.05), perform some fairly simple arithmetic to convert that u to regular old t, and then evaluate your curve at t. The new domain gives you a new space to live in, that for some things is pretty nice. For accuracy/precision, my [non-peer-reviewed] sense is that numerical methods will probably always get you more accuracy/precision. For the case I was experimenting with (path dashing, and some other related things like placement of text glyphs along the path), extreme precision didn't seem necessary. The method I ended up with (Costantini's piecewise-linear solution with K=5 pieces) meant that for each Bezier in my path, I performed some preprocessing to determine the reparameterization coefficients. With that preprocessing done, I now had an O(K) evaluation algorithm to convert the arc-length parameter u (in [0,1]) to t. Another surprisingly big bonus: there exists an equally simple O(K) inverse, i.e. given a t, return u. This allows you to easily compute the distance you've traveled along the arc, if you know where you are in the original parametric domain. To your other question, unfortunately I don't know how these techniques tend to handle cusps. I didn't get that far in my experimentation.