A Rust implementation of Approximate Convex Decomposition for 3D Meshes with Collision-Aware Concavity and Tree Search by Xinyue Wei, Minghua Liu, Zhan Ling, and Hao Su.
This is a work-in-progress! The core algorithm has been implemented and is functional, but some pre- and postprocessing options may be broken, APIs and documentation are not finished, and there are optimizations to be made.
Many efficient geometry processing algorithms require convex shapes, for example in collision detection. Concave shapes are thus typically decomposed into convex parts using a convex decomposition algorithm. Exact convex decomposition is slow and tends to produce too many small parts for real-time applications, so approximate convex decomposition (ACD) is used instead.
CoACD is an approximate convex decomposition algorithm that uses a "collision-aware" concavity metric and a multi-step tree search to decompose a mesh by recursively cutting it into smaller pieces. It preserves collision conditions of the input shape better and with fewer components than methods such as V-HACD, making it a great fit for games and other applications that require delicate and efficient object interactions.
- Approximate convex decomposition for 3D meshes
- Mesh clipping using planes
- Mesh boundary sampling
- Haussdorff distance computation for meshes
- Principal Component Analysis (PCA) for point clouds
The /examples directory contains some examples that can be run using the following command:
cargo run --example <EXAMPLE_NAME>These examples use Bevy for rendering and interactivity, and are primarily intended to showcase the capabilities of the library, not how to use the APIs.
- Input meshes must be manifold. No preprocessing is provided for this yet.
- Convex hull merging is not yet fully functional, and should be disabled. This can be seen in the earlier image with the rectangular ring. It will be fixed in the future.
- Currently, non-deterministic RNG is used. This will be made deterministic in the future.
- Results are not identical to the C++ implementation. This is expected, as many implementation details are different.
- Unlike the C++ implementation, we don't provide a runnable binary application yet. Instead, you must use this as a library.
- Xinyue Wei, Minghua Liu, et al. 2022. Approximate Convex Decomposition for 3D Meshes with Collision-Aware Concavity and Tree Search. ACM Transactions on Graphics (TOG) 41, 4 (2022), 1–18.
- The CoACD C++ implementation by SarahWeii.
The coacd crate is free and open source. All code in this repository is dual-licensed under either:
- MIT License (LICENSE-MIT or http://opensource.org/licenses/MIT)
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
at your option.