确定非凸多面体的凹度

Question

假设有一个非凸的3D多面体P，表示为网格。确定其所有凹面的集合的最佳算法是什么？

第一个，也许微不足道的答案，我认为可能是计算多面体 C 的凸包 P，然后除以同轴差C - P 成连通分量。我可以在正确的方向吗？如果是，如何计算网格之间的 "difference"？是否有一些 CGAL 函数可以用于 "subtracting" 网格并获取连接的组件。

Answer 1

可以，你应该查看 Nef_polyhedron_3 : https://doc.cgal.org/latest/Nef_3/classCGAL_1_1Nef__polyhedron__3.html

基本上，您将网格及其 convex_hull 网格转换为 nef。从那里您可以访问布尔运算，包括差异。所以你可以得到你想要的，然后将它转换回 Polyhedron。