a4ec50d8ba
* Improve perf of path bool lib * Use swap remove * Use outer/inner bounding box for inclusion testing * Reuse allocations for hit testing * Use direct root finding for inclusion testing * Reuse bounding box * Use faster hash and specify capacities * Use hashmap based approach for find vertices * Unroll find_vertecies loop and use 32 bit positions * Tune initial vec capacities * Remove unused bounding boxes * Use smallvec for storing outgoing edges * Improve allocations for compute_minor * Use approximate bounding box for edge finding * Transition aabb to use glam vecs * Make find vertecies use 64 bit again this is slower but less likely to cause issues * Improve intersection candidate finding * Remove loop check in bit vec iter * Special case cubic line intersections * Optimize grid rounding and add debug output * Remove file write * Remove faulty line intersection * Fix grid rounding * Improve robustness and cleanaup code * Make elided lifetime explicit * Fix tests * Fix a boolean ops crash * Add comment --------- Co-authored-by: Keavon Chambers <keavon@keavon.com> |
||
|---|---|---|
| .. | ||
| benches | ||
| src | ||
| visual-tests | ||
| .gitignore | ||
| Cargo.toml | ||
| flake.nix | ||
| LICENSE-APACHE | ||
| LICENSE-MIT | ||
| NOTICE | ||
| README.md | ||
| shell.nix | ||
Path Bool
A Rust library for performing boolean operations on SVG paths.
Path Bool is a port of PathBool.js, providing low-level functionality for boolean operations on complex 2D paths. It handles paths with multiple subpaths, self-intersections, and different fill rules.
Features
- Supports multiple boolean operations: Union, Intersection, Difference, Exclusion, Division, and Fracture.
- Handles both
NonZeroandEvenOddfill rules. - Works with paths containing lines, cubic Bézier curves, quadratic Bézier curves, and elliptical arcs.
- Provides utilities for parsing and generating SVG path data.
Installation
Add this to your Cargo.toml:
[dependencies]
path-bool = "0.1.0"
Usage
Here's a basic example of performing an intersection operation on two paths:
use path_bool::{path_boolean, FillRule, PathBooleanOperation, path_from_path_data, path_to_path_data};
fn main() {
let path_a = path_from_path_data("M 10 10 L 50 10 L 30 40 Z").unwrap();
let path_b = path_from_path_data("M 20 30 L 60 30 L 60 50 L 20 50 Z").unwrap();
let result = path_boolean(
&path_a,
FillRule::NonZero,
&path_b,
FillRule::NonZero,
PathBooleanOperation::Intersection
).unwrap();
let result_data = path_to_path_data(&result[0], 0.001);
println!("Result: {}", result_data);
}
Algorithm
The boolean operations are implemented using a graph-based approach. After the parsing the input, self-intersecting cubic beziers curves are simplified. Then the intersection points between all edges are calculated. These are then turned into a graph representation where every intersection becomes a new vertex. We then apply edge contractions to remove vertices with a degree of 2 to compute the graph minor. At this stage, identical edges are deduplicated. Because we are ultimately interested in the faces of the graph to decide if they should be included in the final output, we then compute the dual graph in which the faces become vertices and vertices become the new faces. That dual structure is then used to determine which faces (dual vertices) should be included in the final output.
Development status
This project is a port of PathBool.js which is still in early stages of development. Contributions, bug reports, and feedback are welcome.
Future work includes:
- Comprehensive test suite
- Performance optimizations
- Additional examples and documentation
- Support for path builder tool features
License and acknowledgements
This library is a Rust port of PathBool.js by Adam Platkevič.
It is dual-licensed under the MIT License or Apache-2.0 License. You may opt to comply with either license.
Copyright © 2024 Adam Platkevič Copyright © 2024 Graphite Authors