绘制顺时针三角形：重新排序点

Question

我正在用C++制作光线追踪器，当我下载对象时遇到了一个问题，因为它只渲染了一些三角形，因为它们是逆时针绘制的。

我查找了这个问题，因为它会是背向的。但我对如何通过顶点知道实际情况感到困惑。如果有人能帮助我编写一个函数，接受每个点的三个向量并重新排序，以便可以按顺时针绘制它们。

谢谢。

- Mr Anonymous

---

@TedLyngmo 请帮忙！ - Mr Anonymous

在3D、4D、...、ND中，要查看多边形的绕向，只需检查dot(normal,ray_direction)的符号即可。还可以参考“确定面法线方向一致性”的文章（链接为https://dev59.com/xrXna4cB1Zd3GeqPOKCP#57440487）。此外，这个“通过3D网格进行光线追踪”的问题（链接为https://dev59.com/IKDha4cB1Zd3GeqP-h8S#45140313）也可能对您有所帮助。 - Spektre

@Spektre 谢谢，这正是我在寻找的。 - Mr Anonymous

Answer 1

您可以计算由三个点定义的三角形所形成的带符号面积 - 这相当于代表边缘的向量的2D“叉积”（有时称为perp product）：

以下是一个简单的Python实现，显示了计算过程；您可以在适当的时候将其转写成C++。

从那里开始，交换三角形中两个点的位置将会颠倒从ccw到cw的方向，反之亦然。

class CollinearpointsError(ValueError):
    pass


def ccw(triangle):
    """returns True if the triangle points are counter clock wise,
    False otherwise, and raises a CollinearpointsError when the 
    three points are collinear 
    """
    A, B, C = triangle
    ax, ay = A
    bx, by = B
    cx, cy = C
    
    AB = (bx - ax, by - ay)
    AC = (cx - ax, cy - ay)

    a, b = AB
    c, d = AC
    
    signed_area_x2 = a * d - b * c
    if signed_area == 0:
        raise CollinearpointsError('the three points are collinear')

    return (a * d - b * c) > 0


def cw(triangle):
    """returns True if the triangle points are clock wise,
    False otherwise, and raises a CollinearpointsError when the 
    three points are collinear 
    """
    return not ccw(triangle)


A = (0, 0)
B = (0, 1)
C = (1, 0)

triangle = (A, B, C)
print(cw(triangle))

triangle = (A, C, B)
print(cw(triangle))

triangle = (A, B, (0, 2))
print(cw(triangle))

输出:

True
False
CollinearpointsError: the three points are collinear

- Reblochon Masque