我正在尝试使用Cand DirectX绘制多边形

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

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

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

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

谁能指出我要遵循的简单易懂的资源，教程，算法，对我有帮助？

解决方案

Direct3D只能绘制三角形(当然，它也可以绘制线和点，但是那一点除外)。因此，如果要绘制比三角形更复杂的任何形状，则必须绘制一堆等于该形状的接触三角形。

在情况下，这是一个凹面多边形三角剖分问题。给定一堆顶点，我们可以保持它们不变，只需要计算"索引缓冲区"(在最简单的情况下，每个三角形三个索引，说明该三角形使用哪个顶点)。然后通过放入顶点/索引缓冲区或者使用DrawUserPrimitives进行绘制。

VTerrain站点上有一些用于对简单(凸形或者凹形，但没有自相交或者孔)多边形进行三角剖分的算法。

我过去曾经使用过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参考实现中剥离三角测量代码。我做了一次，只花了几个小时。

到目前为止进行三角剖分。也有另一种方式：我们可以使用模具技巧。

通用算法如下：

• 禁用颜色和深度写入。启用模具写操作并设置模具缓冲区，它将反转当前的模具值。一张模板就足够了。哦-模板缓冲区也应该清除。
• 在屏幕上随机选择一个点。任何都会做。将此点称为锚点。
• 对于多边形的每条边，从构建边和锚点的两个顶点构建一个三角形。画那个三角形。
• 绘制完所有这些三角形后，请关闭模具写操作，打开模具测试并进行颜色写操作，然后以我们选择的颜色绘制一个全屏方形。这将仅填充凸多边形内的像素。

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

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

希望能帮助到你，
尼尔斯

如果我们能够使用模板缓冲区，则应该很容易做到。这是一个通用算法：

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

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

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