linebender / linebender/spline
Even more optimized rendering
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 128
- Forks
- 9
- PR merge metrics
- No merged PRs in 30d
Description
This is a followon to #15 and also a brain dump of things I thoughts while working on #21. I chose to make that a checkpoint with reasonably good results, rather than proceeding to a highly optimized solution.
First, it would be possible to solve this problem using numerical optimization techniques, much as chapter 9 of [my thesis]. That would be suitable when generating fonts, but is not at all a workable approach for interactive techniques - it would take way too long to produce the optimized representation. Yet, implementing that is probably a good stepping stone, partly because it is useful in batch contexts, and partly to provide a reference for more heuristic techniques.
One of the lessons of that chapter is that making the arclength of the rendered cubic segment match the arclength of the original curve is important. That leaves a single parameter remaining, which is the ratio of the two control arms. My feeling is that if you leave this ratio the same as it is now (ie the `dt` calculation derived from mapping `u` to `t`) but tweak the control arms to make the arclength match better, it will be a big improvement.
Obviously this could be solved by actually measuring the arclength and iterating a solver, but performance is probably unappealing for interactive use. I propose the following heuristic, though it would need to be validated. Assuming a flat parametrization (`t` = `u`), the length of a control arm is 2/(3 + 3 cos θ), where θ is the deflection from the chord to the control point. Note that this formula gives a very good approximation to circular arcs when the deflection is symmetrical (it is equivalent to the standard one, for example in the [circles and cubics] section of the Bézier primer). I suspect it will also work pretty well in cases other than the symmetrical one, but that would have to be validated. For other parametrizations, it should probably scale by dt/du, but that's also something that would need to be validated.
The parametrization (`calc_t()`) also hasn't been carefully tuned. It's flat for low tensions (bias < 1), but it should probably have a higher derivative near the endpoints, especially for bias near 0. Note that this should improve the rendering of low-tension segments, as the arclength is longer and thus they need longer control arms.
Lastly, `render_subdivisions` should be carefully tuned to produce a minimum number of subdivisions that meet some error criterion (and the error criterion should probably be tunable as well). I think special care is needed for low bias values - a value of 1 is reasonable when bias=1 (for low deflections), and possibly higher, but cubic Béziers don't do a good job modeling cases where the curvature is zero at one endpoint. The only reasonable way to tune this is to have a test framework that reports the end-to-end error, and then add terms to make it fit better. I suspect there may be a `k0 - k1` term, as well as obviously some effect of bias.
[my thesis]: https://www.levien.com/phd/phd.html
[circles and cubics]: https://pomax.github.io/bezierinfo/#circles_cubic
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reviewing the checkpoint work in #21 and the existing calc_t() and render_subdivisions logic. The proposal requires validating arclength heuristics, tuning parametrization and subdivision counts, and building a framework that measures end-to-end rendering error; done means a validated, faster representation with an appropriate error criterion.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- computer-graphics, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 18/100