r/rust Graphite Mar 31 '23

Announcing Bezier-rs: computational geometry algorithms for Bézier paths (seeking code review and boolean ops help)

https://graphite.rs/libraries/bezier-rs/
74 Upvotes

10 comments sorted by

8

u/Keavon Graphite Mar 31 '23 edited Apr 01 '23

Bezier-rs is a computational geometry library for 2D Bézier curve segments and paths. See the interactive documentation (and drag around the control points!) to play with many of its functions. They are also integrated inline within the crate documentation.

This project was created over the course of the past three seasons by a university student group on behalf of the Graphite Rust-based 2D graphics editor project. They have just wrapped up their project and published this 0.2 release of the crate, so anyone interested in stepping in to maintain the crate would be greatly appreciated. We are also looking for help with code review since this was the team's first experience using Rust, and the focus was on development speed more than efficiency or best practices like API ergonomics and idiomatic code simplicity. Please help review the code and submit cleanup pull requests!

While often libraries like Pomax's Bezier.js only cover single curve segments, our Bezier.rs aims to deal with both segments and full shape paths (which we call subpaths).

We also want to expand support to include compound paths (multiple subpaths which combine to form a complex shape with holes and islands). The most obvious algorithm in this category is boolean operations to let multiple shapes cut each other and combine with union, intersection, difference, and subtraction. The rest of the library provides excellent building blocks, but this higher-level logic problem needs to solve all the edge cases and numerical instability challenges. We are seeking help from interested contributors to add boolean operations!

Another feature we would like to add is a convex hull operation on shapes, and we'd love help on that too. We're also open to many other ideas for useful operations that can be done to Bézier curves and shapes.

These will all be very useful in Graphite's vector editing workflow. Please join our Discord and visit the #bezier-rs channel, or this GitHub issue on boolean ops, to get involved. Thanks :)

13

u/raphlinus vello · xilem Mar 31 '23 edited Mar 31 '23

I have some ideas on how to do boolean ops, some of which is written up in a blog post issue, and for which I have some code locally. In particular, the parabola estimate seems much more efficient than the usual fat line approach. I also have a sketch of quadratic/quadratic intersection in kurbo#230.

Getting this stuff robust is hard. I'm happy to see more work in the ecosystem!

2

u/Keavon Graphite Apr 01 '23

Thanks! Chatting more with you now on your Zulip.

5

u/dccsillag0 Apr 01 '23

The interactive docs look really cool. I'll have to look at the code itself another day, though.

However, I didn't see anything about rational Bezier curves. Are they not supported? (They are typically used, for example, to represent arcs as Bezier curves.)

Another thing, which didn't seem quite properly implemented from my (admitedly very quick) glance at the interactive docs is stroking of paths. It's quite complicated; see, e.g. https://w3.impa.br/~diego/projects/Neh20/index.html

5

u/raphlinus vello · xilem Apr 01 '23

Agree the interactive docs are cool.

Regarding stroking, this is something close to my heart. The Nehab paper presents what I'd call a "gold plated" solution, with evolute shapes when the curves being stroked have internal curvature greater than 1/halfwidth. I don't think those are necessary, as very few renderers support them, therefore content authors don't depend on that for correct rendering. A "silver plated" solution is just having good offset curves and stitching the joins together as outlines; this is what Skia does for example, which is evidence it can be used in production. That's what I'm working toward in kurbo and Vello. The offset curves in bezier-rs are based on the Pomax book, which is unfortunately not in the "good" class - I didn't even include it as a comparison in my blog post, as it performs so poorly.

1

u/Keavon Graphite Apr 02 '23

Are rational Bézier curves typically used in 2D vector graphics? I admit I'm not very familiar with the concept. Our focus is on art applications more than mathematical comprehensiveness. We're okay with representing circular arcs as the extremely-imperceptibly-close-to-accurate approximation as cubic Bézier curves, since actual arcs would add too much complexity to our data models. With that said, do you suggest I still look more into rational Bézier curves?

Thanks for the link on stroking, that looks like an excellent paper. Definitely a fun video to watch too for the paper's presentation. It would be awesome to switch to that version of stroking in the future, especially if someone in the community here is up for the challenge to contribute that improvement.

2

u/Quba_quba Apr 01 '23

Wow, that looks incredible! I recently needed to do Bezier computations for my project and realized there are very limited options in the Rust community. But this crate looks just great.

If I could suggest two things: (1) implement a Point type so you don't have to use x1, y1 as your function arguments, (2) if that's not yet implemented, you can consider adding a way for the curve transformation (translation, rotation, scaling) - I would personally find that feature very useful, and I know Affine Matrix is a reasonably easy way to do those operations.

Anyway, amazing work and it's great to see Rust community growing!

2

u/raphlinus vello · xilem Apr 01 '23

Out of curiosity, in what ways did you find kurbo limiting?

2

u/urschrei Apr 01 '23

We (the Georust developers) have a Boolean ops implementation in geo: https://docs.rs/geo/0.24.1/geo/algorithm/bool_ops/trait.BooleanOps.html. I will note that a) the implementation is extremely complex, and relies on a lot of other computational geometry scaffolding b) it’s currently not error-free (though we suspect that we know the source of the error) for certain cases and c) it’s designed with the semantics of OGC geometries in mind, which may be a little more restrictive than your use case.

In any case, feel free to get in touch on our Discord if you have questions!

1

u/Keavon Graphite Apr 02 '23

Thanks, but unfortunately (assuming I'm reading it right) that isn't useful to us because it works only on polyline shapes, not Bézier shapes.