有什麼演算法能把任意凹多面體分割為多個凸多面體？

12-29

示意如圖：

將這個凹多面體從中間的面分離為兩個三稜錐（多個凸多面體）

這類演算法的關鍵字應該是 convex decomposition，如[1]。也有一些近似化的演算法，如[2]。

可以考慮使用一些現成的庫，如 https://github.com/kmammou/v-hacd。

[1] Chazelle, Bernard M. "Convex decompositions of polyhedra." Proceedings of the thirteenth annual ACM symposium on Theory of computing. ACM, 1981.

[2] Lien, Jyh-Ming, and Nancy M. Amato. "Approximate convex decomposition of polyhedra." Proceedings of the 2007 ACM symposium on Solid and physical modeling. ACM, 2007.

如果要比較多的凸多面體的話……做一個3D Delaunay Triangulation

生成opengl三角形時寫過一個演算法。

1. 找凹點

2. 然後再找這個凹角的角等分線，然後在剩下的非臨近點中，找距離這個等分線最近的點，以這個點和上面的凹點為分割，將凹多邊形分割。

3. 剩下的多邊形一個變兩，如此遞歸。

這裡的思想就是，凹點最優的分割一定是對半分，這樣凹點內角一定小於180，分割後，這個凹點就不是凹點了。但這個點在多邊形內未必存在，就找距離這個最近的那個，最大程度分減少凹點的內角。

構建一個bsp樹就可以了

首先你要知道每一個表面向外的法向量是什麼方向的，然後你只要不斷地找凹邊（根據外法向量的角度很容易就算出來了），隨便用哪一邊的面把自己切成兩邊，然後二叉遞歸下去直到不存在這樣的邊為止。

試試這個 http://www.cgal.org

非常強大的網格演算法庫，以前用它做過二維多邊形分割成三角形的功能

google convex decomposition

好像有個什麼ear clip演算法，多邊形切三角形出來的，你可能用的上。我也不懂。

我寫過把凹多邊形切成一堆凸多邊形的

有啊。試試gpc庫，支持把多邊形切割成三角形。