CGAL
[PMP] Approximate convex decomposition
Summary of Changes
Reimplementation of https://github.com/kmammou/v-hacd Performs approximate convex decomposition of an input mesh based on a voxelization and hierarchical decomposition.
~~Although it could have added to the package Convex Decomposition of Polyhedra it was decided to add it to the package Polygon Mesh Processing.~~ Finally we decided that it gets added to Convex Decomposition of Polyhedra
Release Management
- Affected package(s): PMP
- Feature/Small Feature (if any): Approximate_Convex_Decomposition
- Link to compiled documentation: v0
TODO
- [x] cite: Khaled Mamou. “Volumetric Hierarchical Approximate Convex Decomposition”. In Game Engine Gems 3, A K Peters, 2016, pp. 141–158. (It would be usefull if you find a pdf of it)
- [ ] Eventually cite: https://arxiv.org/pdf/2205.02961 (optional, it's a possible improvement)
- [x] Produce a plugin for the demo
- [x] Produce a postprocess to refine the convex hull to avoid an offset compare to the original mesh (optional)
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8935/v0/Manual/index.html
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8935/v0/Manual/index.html
Review on the feature results:
- cite: Khaled Mamou. “Volumetric Hierarchical Approximate Convex Decomposition”. In Game Engine Gems 3, A K Peters, 2016, pp. 141–158. (It would be usefull if you find a pdf of it)
- Eventually cite: https://arxiv.org/pdf/2205.02961
- Produce a plugin for the demo
- Produce a postprocess to refine the convex hull to avoid an offset compare to the original mesh. Example:
- Some components are mostly outside of the original mesh and lead to bad approximation. An example of the decomposition in 100 convexes:
Input mesh:
The decomposition:
-Another example of a component mostly outisde the mesh.
The input mesh
The decomposition in 8 parts:
The outside part alone:
-The decomposition are done with axis-aligned plane leading to unsatisfying result on feature non-axis aligned (This default is shared by all existing methods):
Three beams at 45°:
Decompose in 3 parts:
This pull-request was previously marked with the label Tested, but has been modified with new commits. That label has been removed.
There was an error while building the doc:
/home/runner/work/cgal/cgal/Polygon_mesh_processing/doc/Polygon_mesh_processing/examples.txt:60: warning: included file Polygon_mesh_processing/approximate_convex_decomposition.cpp is not found. Check your EXAMPLE_PATH
https://github.com/CGAL/cgal/actions/runs/19538932467
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8935/v0/Manual/index.html
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8935/v0/Manual/index.html
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8935/v0/Manual/index.html
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8935/v0/Manual/index.html
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8935/v0/Manual/index.html
I had thought that the vertices of the decomposition are all input vertices. Is the current solution (intersection points between voxels and triangles) also what is done in the original paper?
The voxels are entirely from the voxel grid or optionally from vertices or mesh with box intersections when the refitting option is chosen. In the reference implementation, they do optionally a shrink wrap at the end. If this is not done, the vertices are entirely from the voxel grid.
So when using Epick things can go wrong with intersection points computed. Do you make sanity checks, .e.g. the intersection point is inside the dilated voxel ?
I use the AABB_tree for collecting all intersections inside an Iso_cuboid_3. I do some simple checks for which corners of the voxel grid I also have to include for the ch3.