Skip to content

Convert CubicBez::nearest to the poly-cool quintic solver #493

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
jneem merged 1 commit into from
Nov 27, 2025
Merged

Convert CubicBez::nearest to the poly-cool quintic solver #493

jneem merged 1 commit into from
Nov 27, 2025

Conversation

@jneem
Copy link
Member

@jneem jneem commented Aug 29, 2025 •
edited
Loading

Currently CubicBez::nearest uses subdivision to QuadBez and then a cubic solver. This converts it to the quintic solver in poly-cool for a nice speedup (3000x for high accuracy!) and better robustness.

Fixes #446

Maybe it would make sense to propose moving poly-cool to linebender first? I wasn't sure...

cubic nearest point/0.001
                        time:   [126.51 ns 126.90 ns 127.31 ns]
                        change: [-78.774% -78.673% -78.577%] (p = 0.00 < 0.05)
                        Performance has improved.

cubic nearest point/0.000001
                        time:   [143.92 ns 144.16 ns 144.46 ns]
                        change: [-97.476% -97.469% -97.463%] (p = 0.00 < 0.05)
                        Performance has improved.

cubic nearest point/0.000000000001
                        time:   [162.17 ns 162.51 ns 162.88 ns]
                        change: [-99.971% -99.971% -99.971%] (p = 0.00 < 0.05)
                        Performance has improved.

This bumps MSRV from 1.82 to 1.85, which has more f64 methods in core and also supports edition 2024.

@Keavon
Copy link

Keavon commented Sep 12, 2025 •
edited
Loading

Once poly-cool is used by Kurbo, I would recommend making a quick PR to finish up the tangent/normal to point family of functions, which would supersede #417 and add support for normals as well. Since that is low-hanging fruit to fill in some of Bezier-rs's extra functionality back in Kurbo where it seems noticeably missing.

@jneem
Copy link
Member Author

jneem commented Oct 24, 2025

Ok, I've updated this to use the newly-in-repo polycool.

nicoburns
nicoburns approved these changes Nov 27, 2025
View reviewed changes
Copy link

@nicoburns nicoburns left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I have no real insight into the math here. But this has been discussed several times and the consensus always seems to have been in favour of merging.

@jneem jneem enabled auto-merge November 27, 2025 21:09
@jneem jneem added this pull request to the merge queue Nov 27, 2025
Merged via the queue into linebender:main with commit 21bd988 Nov 27, 2025
15 checks passed
@jneem jneem deleted the poly-cool branch November 27, 2025 21:13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@nicoburns nicoburns nicoburns approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Bad case for CubicBez::nearest

3 participants

@jneem @Keavon @nicoburns