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

StackOverflow https://stackoverflow.com/questions/91202

  •  01-07-2019
  •  | 
  •  

题

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

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

我可以加载点并使用三角形扇和绘制用户基元绘制凸形状。

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

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

谁能给我指出一个简单易懂的资源\教程\算法来帮助我？

有帮助吗？

解决方案

Direct3D 只能绘制三角形（当然，它也可以绘制直线和点，但这不是重点）。因此，如果您想绘制任何比三角形更复杂的形状，则必须绘制一堆等于该形状的相接三角形。

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

一些用于对简单（凸或凹，但没有自相交或孔）多边形进行三角测量的算法位于 V地形站点.

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

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

其他提示

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

有一些代码可以帮助您：

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. 绘制完所有这些三角形后，关闭模板写入，打开模板测试和颜色写入，并以您选择的颜色绘制全屏四边形。这将仅填充凸多边形内的像素。

最好将锚点放置在多边形的中间，然后绘制一个与多边形边界框一样大的矩形。这节省了一点填充率。

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

希望它有帮助，尼尔

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

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

我只需要为一个项目这样做。我发现的最简单的算法称为“Ear Clipping”。关于它的一篇很棒的论文在这里： 通过耳朵裁剪进行三角测量.pdf

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top