Procedural Modelling

A Framework-Agnostic Procedural Modelling Library.

Uses a data structure based on half-edge meshes to represent (open) manifold meshes with optional non-manifold vertices. Our goal is to implement operations like Boolean Operations, Subdivisions, Curved Surfaces, and Stitching. The library aims to support the triangulation of 2d surfaces in a modular way that can be used without any of the 3d features.

Currently there are quite a few crates that implement boolean operations and triangulation to achieve some other goal. We want to provide a common implementation to satisfy these very similar requirements and improve code-reuse among these projects so they can focus on their original goal.

WARNING

This crate is still in a very early stage of development. Expect frequent API modifications, bugs, and missing features. Feel free to contribute by opening issues, pull requests or sharing your ideas in GitHub Discussion.

Usage

Install using cargo add procedural_modelling.

let mut mesh = MeshVec3::regular_star(1.0, 0.8, 30);
mesh.transform(
    &Transform::from_translation(Vec3::new(0.0, -0.99, 0.0))
               .with_rotation(Quat::from_rotation_z(PI)),
);
let trans = Transform::from_rotation(Quat::from_rotation_y(0.3))
                      .with_translation(Vec3::new(0.4, 0.3, 0.0));
let mut f = mesh.extrude_ex(mesh.edge_between(1, 0).unwrap().id(), trans, true, true);
for _ in 0..5 {
    f = mesh.extrude_face_ex(f, trans, true, true);
}
mesh.to_bevy(RenderAssetUsages::default())

Examples

Or run the examples on your computer like, e.g., cargo run --features="bevy bevy/bevy_pbr" --profile fast-dev --example box.

For package development, we recommend using the editor-subcrate. This example has a little egui-editor. Run it using cargo watch -w editor/src -w src -x "run -p editor --profile fast-dev". The fast-dev profile will enable optimizations for the dependencies, but not for the package itself. This will slow down the first build significantly, but incremental builds are slightly faster and bevy's performance (bevy is used as the renderer in the examples) improves a lot.

When developing tests, we recommend cargo watch -w editor/src -w src -x "test --profile fast-dev".

Feature Progress

• Attributes
  • Positions
  • Normals
  • Crease Weights
  • Smooth Surface Groups
  • Tangents
  • UV Coordinates
  • Custom Attributes
• Triangulation
  • Montone Sweep-Line
  • Constrained Delaunay (using Spade)
  • Steiner Points
• Primitives
  • Polygon, Star
  • Cuboid
  • Cylinder, Cone, Frustum, Tetrahedron, Octahedron
  • Dodecahedron, Icosahedron
  • UV Sphere
  • Cube Sphere
  • Icosphere
  • Torus
• Builder Primitives
  • Lines
  • Quadratic Bezier Curves
  • Cubic Bezier Curves
  • Curved Surfaces (Bezier Surfaces / Parametric Surfaces / NURBS / Spline Networks...?)
• Operations
  • Extrude
  • Loft
  • Inset
  • Plane Intersection
  • Union
  • Intersection
  • Difference
  • Symmetric Difference
  • (Anisotropic) Simplification / LODs
  • Stitching
  • Subdivision
  • Morphing
  • Voxelization
• Tools
  • Geodesic Pathfinding
  • Raycasting
  • Topology Analysis
  • Spatial Data Structures
• Debug Visualizations
  • Indices
  • Normals
  • Tangents
  • Topology
• Backends
  • Bevy
  • wgpu

Features

The following features are available:

• meshopt -- Use Meshopt to optimize the performance of generated meshes.
• bevy -- Compiles with support for bevy. Necessary for the examples and the editor.
• benchmarks -- Enable criterion for the benchmarks.

For development only:

• sweep_debug -- Collect debug information during the sweepline triangulation and enable visualizations in the bevy backend.
• sweep_debug_print -- Print debug information for the sweepline triangulation.

Triangulation algorithms

The package supports different triangulation algorithms. The robustness and rendering speed of the produced triangulations varies significantly. These performance differences usually only matter for meshes with extremely large flat surfaces. In the table below, we compare the performance of the different algorithms for a circle with 100, 1000, and 10000 vertices. The "ZigZag" mesh has 10000 vertices and is designed to demonstrate the worst-case for the Sweep algorithm.

• Fan Extremely fast, but only works for convex polygons. And even then, results are usually numerically unstable. Runs in O(n) time.
• EarClipping Simple but slow textbook-algorithm for reference. Runs in O(n^2) time. When the input provokes numerical instabilities, e.g., a very large circle, the algorithm switches to recovery mode running in up to O(n^3) time.
• Sweep Very fast sweep-line algorithm that might produces triangulations with unnecessarily long edges. Works for arbitrary polygons (yes, they don't have to be simple). Runs in O(n log n) time. See CMSC 754.
• Delaunay Slow, but large flat surfaces might render faster. Currently uses Spade. Runs in O(n log n) time.
• EdgeFlip Same output as Delaunay, but without external dependencies and using a very slow edge-flipping algorithm. Runs in O(n^3) time. EdgeFlip,
• MinWeight Minimizes the overall edge length of the triangulation. Very slow, but produces the theoretically fastest rendering triangulations for large flat surfaces. Runs in O(2^n) time.
• Heuristic Heuristic algorithm that tries to find a compromise between the speed of Sweep and the quality of EdgeMin.
• Auto (default) Automatically choose the "best" algorithm based on the input, i.e., with the given ratio of numerical stability and performance. Currently, it uses specialized implementations for the smallest polygons, then uses Delaunay, then Heuristic, and finally falls back to Sweep for the largest polygons.

Algorithm	Requirements	Worst Case	Circle 10	Circle 100	Circle 1000	Circle 10000	ZigZag 1000	ZigZag 10000
Fan	Convex	n	0.258µs (151fps)	1.781µs¹ (118fps)²	17.19µs (52.4fps)	172.4µs (12.5fps)	-	-
EarClipping	Simple	n^2	0.792µs (150fps)	35.32µs (118fps)	3.164ms (52.1fps)	3.402s (11.4fps)	48.05ms (35.6fps)	46.03s (9.51fps)
Sweep	None	n log n	1.582µs (151fps)	13.22µs (118fps)	139.0µs (44.2fps)	1.552ms (9.87fps)	403.1µs (42.8fps)	4.292ms (9.87fps)
Delaunay	Simple	n log n	3.037µs (151fps)	34.00µs (134fps)	339.5µs (132fps)	3.725ms (129fps)	1.796ms (42.1fps)	166.0ms (9.33fps)
EdgeFlip	Simple	n^3
MinWeight	Simple	2^n
Heuristic	Simple	n log n
Auto	Simple	n log n

• ¹) Time for the triangulation on a Intel i7-12700K (single threaded). Run the benchmarks using cargo bench --features benchmarks.
• ²) FPS when rendering 100 large, transparent instances with the bevy 0.14.2 pbr shader on a Nvidia GeForce RTX 4060 Ti in Full HD. See cargo run --example fps_bench --profile release --features="bevy bevy/bevy_pbr bevy/bevy_winit bevy/tonemapping_luts". For the non-Delaunay algorithms, the rendering time deteriorates for the larger circles since the edge length is not minimized causing significant overdraw.

Supported Bevy Versions

The following table shows the compatibility of procedural_modelling with certain versions of Bevy:

bevy	bevy_procedural_meshes
0.14	0.2.*, main
0.13	0.1.*

License

Except where noted (below and/or in individual files), all code in this repository is dual-licensed, allowing you the flexibility to choose between:

• The MIT License (LICENSE-MIT or http://opensource.org/licenses/MIT)
• The Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0).

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

How to Contribute

We welcome contributions from the community! Here are some ways you can help:

1. Report Bugs:

   • If you find a bug, please open an issue on GitHub with detailed information on how to reproduce it.

2. Suggest Features:

   • Have an idea for a new feature? Open an issue to discuss it. We appreciate feedback and suggestions.

3. Submit Pull Requests:

   • Fork the repository and create a new branch for your feature or bug fix.
   • Assign an issue to yourself or open a new issue to work on.
   • Make your changes, ensuring that your code adheres to the project's coding standards.
   • Write tests for your changes, if applicable.
   • Submit a pull request with a clear description of your changes and the problem they solve.

4. Improve Documentation:

   • Help us improve our documentation by fixing typos, clarifying instructions, or adding new sections.