Advice on how to add arc length parameterization, and exponential interpolation to offset.

[MatthewBlanchard]

I'm going to be adding these features in a fork soon.

As far as arc length parameterization goes I've got an approach in my own code that does things very naively. It takes anything that returns x, y pairs, a number of iterations and creates a table of lengths. This works perfectly fine, but I often find with fixed values for iterations you either go way underkill or way overkill. I was thinking that I could do an iterative approach where it first measures the distance between start and end, then adds the midpoint checks again, adds 2 midpoints checks again. Does this until the total length changed by less than SMALL_DISTANCE.

As far as exponential interpolation goes would just changing the mid_offset calculation in subdivide_offset function work?

Would changing the highlighted line to use exponential interpolation be enough? Are there issues with this approach I'm not seeing?

I would appreciate any advice on how you would want these things done in such a way that they could make it back upstream.

[Logicalshift]

An arc length function is definitely something I've been meaning to add. I think a subdivision algorithm is a fine place to start, as it'll likely be fairly straightforward.

For subdivision algorithms, a handy trick that you can use to reduce the errors is to use the curve characteristics function to find the inflection points and perform the initial subdivisions there: the resulting curves are arches and have fewer corner cases to deal with (inflection points close to the start or end of the curve seems to be what breaks a lot of numerical algorithms for curves). The offset algorithm does this as a first step too, so there's potential for just re-using the sections generated at that point. I can't find any place where anyone has tried this in association with an arc length algorithm, which is interesting because everywhere mentions the problems with the algorithm breaking down for more complex curves.

I think the most similar code I have to this is in find_intersection_point_in_loop (which I spot has an unimplemented case I forgot to think about: agh). That uses curve.subsection for the actual subdividing, which might be best for this use case too: it's faster if you're not intending to keep the curve subsection around.

I would probably use an accuracy parameter rather than SMALL_DISTANCE in this case, as that's how many of the other similar functions work when there's a possible trade-off between accuracy and speed to be made.

I think I'd start with a simpler algorithm and work out ways to compare them: I think number of subdivisions vs accuracy is probably a good thing to look at, but I'd also be looking at the 'better' algorithms to see what can be done.

Funnily enough I thought I remembered reading an algorithm I thought would be good to use in Graphics Gems and it's literally where the book falls open for me now: Graphic Gems V Chapter IV.7, The Length of Bezier Curves: I think it's the same algorithm as described here: https://www.sciencedirect.com/science/article/pii/0925772195000542 (the version in Graphics Gems has a good discussion on how to select an error function, which I think is missing from this academic version)

https://raphlinus.github.io/curves/2018/12/28/bezier-arclength.html briefly mentions the same algorithm and suggests it's worse than Legendre-Gauss quadrature, but in Graphics Gems the author of the algorithm says it was made to improve on that technique in his introduction. (The claim is an error of 0.1% after 4 subdivisions for cubic beziers)

[Logicalshift]

Do you want a way to specify a length and determine a section of the curve that is that long, or a way to measure the length of a curve?

If it's just measuring the length of a curve, the curve_length() function implements the algorithm you cite from Graphics Gems.

I've never had any use for it, but a similar technique could be used to find the section of a curve that has a certain length if that's what you're after, and that could also be another way to 'walk' the curve (the walk_curve_evenly algorithm uses the chord length rather than the arc length as the distance between points)

[ripytide]

I ended up finding what I was looking for in another crate: inv_arclen the ability to map from ArcLength to t.