Pet*_*uza 5 geometry polygons unity-game-engine computational-geometry
我正在使用Unity,但解决方案应该是通用的.我将通过鼠标点击获得用户输入,鼠标点击定义了封闭的不规则多边形的顶点列表.该顶点将定义平面3D网格的外边缘.
要在Unity中以程序方式生成网格,我必须指定所有顶点以及它们如何连接以形成三角形.
因此,对于凸多边形而言,它是微不足道的,我只是制作具有顶点1,2,3然后1,3,4等的三角形,形成类似孔雀尾巴的东西.
但对于凹多边形而言,并非如此简单.是否有一种有效的算法来查找内部三角形？
您可以使用受约束的Delaunay三角剖分(实现起来并非易事!).Triangle和CGAL中提供了良好的库实现,提供了高效的O(n*log(n))实现.
如果顶点集很小,那么耳剪裁算法也是可能的,尽管它不一定会给你一个Delaunay三角剖分(它通常会产生次优三角形)并运行O(n^2).虽然这很容易实现.
由于输入顶点存在于3d空间中的平面上,因此可以通过投影到平面上来获得2d问题,在2d中计算三角剖分,然后将相同的网格拓扑应用于3d顶点集.