使用三角库对凹多边形进行三角剖分

Question

我正在使用 a C++ wrapper of the Triangle library，但无法去除多边形之外的三角形。

这是我想要得到的：

这是我用 Triangle 得到的结果：

（我故意不填三角形是为了表示有一些三角形不在多边形内）

我尝试使用光线投射算法去除外部三角形（找到三角形边缘的中心并查看它是否在多边形中。如果至少有一个不存在则不绘制此三角形）但它是对我来说非常慢（多边形每帧更新一次）。我错过了什么？我应该将哪些参数传递给 Triangle 以对凹多边形进行三角剖分？

如果不能用三角形做我想做的事，有人可以建议我一个快速绘制多边形的方法（我的程序使用 Qt Quick Scene Graph，我只能在三角形或凸多边形中绘制，因为OpenGL 需要）？目前我想尝试 GLU 的曲面细分方法和使用模板缓冲区的绘图。我也打算试试 this library.

Answer 1

GLU 细分解决了这个问题。它显示出高性能和良好的三角测量质量，在我的笔记本电脑和 Android 平板电脑 Nexus 7 上运行良好。您可以找到独立版本的 GLU libtess here。

Answer 2

您可以尝试使用命中测试隐藏位图，但它仅对输出有效。我为等高线图做了这个：https://cntm.codeplex.com/。或者您可以尝试 alpha 形状。它被定义为删除超过 alpha 的边缘。

Answer 3

一般凹多边形的绘制方法至少有两种：

应用三角算法。这就是你一直在尝试的。应该有很多关于该主题的文献，以及您可以使用的源代码。
使用模板缓冲区。这在我对这些较旧问题的回答中得到了说明：Black out everything outside a polygon, How to force openGL to draw a non-convex filled polygon.

但是，如果您只需要绘制您在示例中使用的半月型形状，而不是任意的凹多边形，这一切似乎比必要的要复杂得多。你可以很容易地构建一个三角形带来表示这个形状。

你当前的半月可能是用一个看起来像这样的顶点序列渲染的，它按照（凹）多边形所需的顺序定义顶点：

0                                              9
  17                                        10
  1   16                                11   8
            15                    12
      2             14    13             7

            3                      6
                    4      5

您可以直接使用原始类型 GL_TRIANGLE_STRIP 渲染此形状，方法是对顶点进行不同排序，以便底部圆弧的顶点与顶部圆弧的顶点交替出现：

0                                             17
   2                                        16
  1    4                                14   15
             6                    12
      3              8    10             13

            5                      11
                    7      9

使用三角库对凹多边形进行三角剖分

Triangulation of concave polygon using Triangle library

c++

opengl

graphics

qt

triangulation