最快的带孔洞的三角剖分算法？
Jan*_*ott 7 navigation algorithm mesh triangulation
我正在为RTS游戏寻找路径,我正在从游戏网格构建导航网格.
我编写了一个类似于Marching Squares的算法,它可以创建并简化地图中可步行和不可行走区域之间的边界.现在我有一个仅由边缘组成的"网格".我需要对此网格进行三角测量,以便最终的三角剖分包含初始边,然后我可以删除不可移动的区域以在导航网格中创建孔.例如,我需要这样做......
三角形代表地图的可行走区域.这些洞代表了不可穿越的地区,如山脉或建筑物.网格可以被认为是2D,因为高度是无关紧要的.这显然是一个非常简化的案例.游戏中的导航网格将由数千个顶点和许多洞组成,但我可以将其分解为更小的块以进行动态更新.
我已经研究了受约束的Delaunay三角剖分算法,该算法首先创建点的Delaunay三角剖分,然后移除与受约束边相交的任何三角形,然后重新三角化移除的三角形.
对我来说,这似乎有点多余.我的网格不需要是Delaunay,它完全由约束边组成,所以如果可能的话,我想跳过额外的三角剖分.有更好的算法吗？我看了看,只能找到受约束的Delaunay算法.或者也许我错了,受约束的Delaunay算法最好？
我之前已经完成了从头开始的导航网格路径查找,但从未必须自己生成导航网格.三角测量算法对我来说是新的.任何见解？