c# - 有没有一种在 Direct3d 中绘制凹多边形的有效\简单方法

Question

我正在尝试使用 c# 和 directx 绘制多边形

我得到的只是文件中点的有序列表，我需要在 3d 世界中绘制平面多边形。

我可以使用三角扇和drawuserprimitives加载点并绘制凸形。

当多边形非常凹（可能是）时，这显然会导致错误的结果。

我无法想象我是唯一一个解决这个问题的人（虽然我是 gfx/directx 新手——我的背景是 gui\windows 应用程序开发）。

任何人都可以指出一个简单的资源\教程\算法可以帮助我吗？

Answer 1

Direct3D 只能绘制三角形（好吧，它也可以绘制线和点，但除了点之外）。所以如果你想画任何比三角形更复杂的形状，你必须画一堆与那个形状相等的三角形。

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

VTerrain 站点上提供了一些用于对简单（凸面或凹面，但没有自相交或孔）多边形进行三角剖分的算法。

我过去使用过 Ratcliff 的代码；非常简单并且效果很好。VTerrain 有一个死链接；代码可以在这里找到。它是 C++，但将其移植到 C# 应该很简单。

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

Answer 2

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

有几个代码可以帮助你：

GPC 库。非常易于使用，但您可能不喜欢它的许可证：

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

还有三角形：

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

和拳头：

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

另一个（也是我更喜欢的）选项是使用 GLU tesselator。您可以很好地从 DirectX 程序加载和使用 GLU 库。它不需要 OpenGL 上下文来使用它，它预装在所有 Windows 机器上。如果您想要源代码，您可以从 SGI 参考实现中提取三角测量代码。我做过一次，只花了我几个小时。

到目前为止三角测量。还有一种不同的方法：您可以使用模板技巧。

一般算法是这样的：

1. 禁用颜色和深度写入。启用模板写入并设置模板缓冲区，它将反转当前模板值。一点模具就足够了。哦 - 你的模板缓冲区也应该被清除。

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

3. 对于多边形的每条边，从构建边和锚点的两个顶点构建一个三角形。画出那个三角形。

4. 绘制完所有这些三角形后，关闭模板写入，打开模板测试和颜色写入，然后以您选择的颜色绘制全屏四边形。这将只填充凸多边形内的像素。

将锚点放置在多边形的中间并绘制一个与多边形的边界框一样大的矩形是个好主意。这样可以节省一点填充率。

顺便说一句 - 模板技术也适用于自相交多边形。

希望它有帮助，尼尔斯

Answer 3

如果您能够使用模板缓冲区，则应该不难做到。这是一个通用算法：

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 s, v[i], v[i+1] that adds 1 to the stencil buffer
    else
        draw a triangle defined by s, 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] 的人的角度。这可以通过使用叉积来测试：

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

Answer 4

我只需要为一个项目做这个。我发现的最简单的算法称为“Ear Clipping”。一篇很棒的论文在这里：TriangulationByEarClipping.pdf

我花了大约 250 行 c++ 代码和 4 个小时来实现它的蛮力版本。其他算法具有更好的性能，但这很容易实现和理解。