给定一个不规则多边形的顶点列表，如何创建内部三角形来有效地构建平面 3D 网格? [英] Given an irregular polygon's vertex list, how to create internal triangles to build a flat 3D mesh efficiently?

问题描述

我正在使用 Unity，但解决方案应该是通用的.我将从鼠标点击中获得用户输入，它定义了一个封闭的不规则多边形的顶点列表.该顶点将定义平面 3D 网格的外边缘.

I'm using Unity, but the solution should be generic. I will get user input from mouse clicks, which define the vertex list of a closed irregular polygon. That vertices will define the outer edges of a flat 3D mesh.

要在 Unity 中按程序生成网格，我必须指定所有顶点以及它们如何连接以形成三角形.

To procedurally generate a mesh in Unity, I have to specify all the vertices and how they are connected to form triangles.

所以，对于凸多边形来说，这是微不足道的，我只是制作顶点为 1,2,3 然后 1,3,4 等的三角形，形成像孔雀尾巴一样的东西.

So, for convex polygons it's trivial, I'd just make triangles with vertices 1,2,3 then 1,3,4 etc. forming something like a Peacock tail.

但是对于凹多边形来说，它并不是那么简单.有没有找到内部三角形的有效算法?

But for concave polygons it's not so simple. Is there an efficient algorithm to find the internal triangles?

推荐答案

您可以使用受约束的 Delaunay三角剖分(实现起来并不容易！).Triangle 和 CGAL，提供高效的O(n*log(n)) 实现.

You could make use of a constrained Delaunay triangulation (which is not trivial to implement!). Good library implementations are available within Triangle and CGAL, providing efficient O(n*log(n)) implementations.

如果顶点集很小，剪耳算法也是一种可能，尽管它不一定会给你一个 Delaunay 三角剖分(它通常会产生次优三角形)并在 O(n^2) 中运行.不过，实现自己很容易.

If the vertex set is small, the ear-clipping algorithm is also a possibility, although it wont necessarily give you a Delaunay triangulation (it will typically produce sub-optimal triangles) and runs in O(n^2). It is pretty easy to implement yourself though.

由于输入顶点存在于 3d 空间中的平面上，您可以通过投影到平面上，计算 2d 中的三角剖分，然后将相同的网格拓扑应用于 3d 顶点集来获得 2d 问题.

Since the input vertices exist on a flat plane in 3d space, you could obtain a 2d problem by projecting onto the plane, computing the triangulation in 2d and then applying the same mesh topology to your 3d vertex set.

这篇关于给定一个不规则多边形的顶点列表，如何创建内部三角形来有效地构建平面 3D 网格?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！