有没有一种在Direct3d中绘制凹多边形的高效\简便方法？

Question

我正在尝试使用C#和DirectX绘制多边形。我从文件中获取到的是一系列有序的点，我需要在3D世界中绘制出这个多边形。我可以加载这些点并使用三角扇和drawuserprimitives绘制一个凸形状。但是当多边形非常凹时，这会导致错误的结果。我不认为我是唯一遇到这个问题的人（尽管我是一个图形/ DirectX新手，我的背景是GUI / Windows应用程序开发）。是否有人能指向一个简单易懂的资源/教程/算法，可以帮助我解决这个问题？

- NotJarvis

Answer 1

如果您能使用模板缓冲区，那么做起来应该并不难。以下是一个通用算法：

Clear the stencil buffer to 1.
Pick an arbitrary vertex v0, probably somewhere near the polygon to reduce floating-point errors.
For each vertex v[i] of the polygon in clockwise order:
    let s be the segment v[i]->v[i+1] (where i+1 will wrap to 0 when the last vertex is reached)
    if v0 is to the "right" of s:
        draw a triangle defined by v0, v[i], v[i+1] that adds 1 to the stencil buffer
    else
        draw a triangle defined by v0, v[i], v[i+1] that subtracts 1 from the stencil buffer
end for
fill the screen with the desired color/texture, testing for stencil buffer values >= 2.

在“s的权利”方面，我指的是从站在v[i]上并面向v[i+1]的人的视角。这可以通过使用叉积来测试：

cross(v0 - v[i], v[i+1] - v[i]) > 0

- Walt D

---

已经过去了14年，但我想你的意思是“绘制由v0、v[i]、v[i+1]定义的三角形”。感谢您的帮助，它有效！ - thedemons

Answer 2

Direct3D只能绘制三角形（好吧，它也可以绘制线段和点，但那不是重点）。所以如果你想要绘制任何比三角形更复杂的形状，你必须画一堆接触的三角形，这些三角形等于该形状。

在您的情况下，这是一个凹多边形三角剖分问题。给定一堆顶点，你可以保持它们不变，你只需要计算“索引缓冲区”（最简单的情况下，每个三角形用哪些顶点表示的三个索引）。然后把它放入顶点/索引缓冲区或使用DrawUserPrimitives进行绘制。

一些用于三角剖分简单（凸或凹，但没有自相交或孔）多边形的算法在VTerrain网站上。

我过去用过Ratcliff的代码；非常简单，运行良好。VTerrain对它有一个已经失效的链接；该代码可以在这里找到。它是C++的，但将其移植到C#应该很简单。

哦，不要使用三角形扇区。它们的用途非常有限，效率低下，而且即将消失（例如，Direct3D 10不再支持它们）。只需使用三角形列表。

- NeARAZ

Answer 3

三角剖分是显而易见的答案，但编写一个稳定的三角剖分器很难。除非你有两个月的时间浪费，否则不要尝试。

有几个代码可能会对你有帮助：

GPC库。非常容易使用，但您可能不喜欢其许可证：

http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

还有一个三角形：

http://www.cs.cmu.edu/~quake/triangle.html

还有FIST：

http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

另一个（也是我喜欢的）选项是使用GLU tesselator。您可以从DirectX程序中加载和使用GLU库。它不需要OpenGL上下文即可使用，并且已预安装在所有Windows机器上。如果您想要源代码，可以从SGI参考实现中提取三角剖分代码。我曾经这样做过，只花了几个小时。

到目前为止都是关于三角剖分的内容。还有一种不同的方法：您可以使用模板技巧。

通用算法如下：

1.禁用颜色和深度写入。启用模板写入并设置模板缓冲区以反转当前模板值。一个模板位就足够了。噢 - 您的模板缓冲区也应该被清除。

2.在屏幕上随机选择一个点。任何一个都可以。将此点称为您的锚点。

3.对于多边形的每条边，从构成边的两个顶点和锚点构建一个三角形。绘制该三角形。

4.一旦绘制了所有这些三角形，关闭模板写入，打开模板测试和颜色写入，并在所选择的颜色中绘制全屏四边形。这将仅填充凸多边形内的像素。

将锚点放置在多边形的中心，只需绘制一个尽可能大的矩形作为多边形的边界框，这是一个好主意。这样可以节省一些填充速率。

顺便说一下，模板技术也适用于自相交的多边形。

希望有所帮助， Nils

- Nils

Answer 4

我刚为一个项目做了这个。我发现最简单的算法叫做“剪耳朵”。这里有一篇很好的论文：TriangulationByEarClipping.pdf

我用了大约250行C++代码和4个小时来实现它的暴力版本。其他算法性能更好，但这个算法实现和理解都比较简单。

- Tod

---

值得一提的是：https://github.com/libgdx/libgdx/blob/master/gdx/src/com/badlogic/gdx/math/EarClippingTriangulator.java 但它不处理自相交的多边形或孔。 - NateS