c++ - 按逆时针方向对 3D 多边形顶点进行排序

Question

我必须找到多边形的法线，但为了做到这一点，我首先必须按逆时针方向对顶点 (x,y,z) 进行排序。假设我得到了用户输入的 n 个顶点点，我如何按逆时针方向排列顶点以将它们变成多边形？

Answer 1

您不能在不知道正常值的情况下订购您的积分，反之亦然。如果你说“从前面逆时针”那么你需要知道前面是哪一侧，因此你需要知道法线。所以你的问题没有答案，就目前而言，因为它有点循环:你没有足够的信息来确定你在寻找什么。

您需要更多信息。例如，如果此多边形是凸曲面的一部分，您可以计算该曲面的几何中心。然后在多边形上选择任意 3 个非共线点 a, b, c，计算法线 (norm((a - b) cross (c - b))) ，计算从质心到你的点之一的 vector (例如 b - 质心)，然后检查法线是否与该 vector ( 的符号)面向相同(或相反，无论)方向正常点(b - 质心))，如果方向错误则将其翻转。本质上，您只需计算一个垂直单位 vector (记住，有两个)，然后确保它指向对象的内部/外部。

如果您的脸是凹面的一部分，您可以通过将您的法线与相邻面的法线的点积相乘并翻转它(如果为负数)来使所有法线指向相同的大致方向。您仍然需要确定一种方法来确定脸部的哪一侧在表面的内侧还是外侧，但至少所有法线都会指向一侧。

如果您没有关于法线应朝向的大致方向的信息，则必须从其他地方获取逆时针信息。您可以对多边形中心周围的点进行排序以使它们按顺序排列，但要确定该顺序是顺时针还是逆时针需要其他信息(例如询问用户等)。

请注意，基于 atan 的 2D 解决方案隐含地依赖于一些额外的信息:依赖于法线面朝屏幕外/纸面外并朝向您，观众，以及因此，您可以围绕该法线在已知方向上进行排序。这种假设通常是在没有任何人真正谈论它的情况下做出的。然而，实际上，您需要决定哪一侧是正面和背面——对于 3D 来说并不总是那么容易(如果您正在渲染到屏幕并且设置了视点，您可以将其用作额外信息——比如法线面向相机，然后围绕法线排列)。

---

用另一种方式表达上述内容，一般来说，我们有 3 个未知数:

1. 从“正面”看，缠绕顺序是什么？
2. 两个与平面垂直的单位 vector 中的哪一个我们选择在“前面”或“哪一边是前面”？
3. 对应于缠绕顺序的给定点的排序顺序是什么？

我们需要其中两个来确定第三个。

回应 Andon 在下面的评论:对于光栅化器，它定义了 #1 本身(或从配置中获取)，而 #3 由 API 要求假设，因此可以推断出 #2。

在你经常看到描述的2D案例中(我上面提到的)，#1被指定为要求，#2假设是“面向观察者的一面是正面”，所以#3可以是用 atan 确定并按递增/递减顺序排序。

在你原来的问题中，你知道#1(你已经定义了它)，但你不知道#2(哪一边是前面？)，因此你无法确定#3。您需要一些方法来确定 #2(例如，背对质心、面向观察者等等)。