11 计算几何在图形学中的应用

在前一篇教程中，我们探讨了“凸包算法”，这是计算几何中的一个基础算法，广泛应用于各种领域。从凸包算法出发，我们可以进一步了解计算几何在计算机图形学中的重要性。图形学作为一个技术密集型行业，充分利用了计算几何中的许多算法来处理图形、模型和渲染等问题。在这一篇中，我们将通过实际案例，讨论计算几何在图形学中的应用。

1. 三维模型的碰撞检测

碰撞检测是计算机图形学和游戏开发中的核心问题之一。使用计算几何中的算法可以高效地检测三维模型之间的碰撞。最常用的几何体是“包围盒”，这可以是轴对齐包围盒（AABB）或球体包围盒。

应用实例：AABB碰撞检测

设想我们有两个物体A和B，每个物体可以用一个AABB表示。判断这两个物体是否相撞的条件非常简单：

• 对于物体A，它的AABB范围由(x_{min}^A, x_{max}^A)和(y_{min}^A, y_{max}^A)表示。
• 对于物体B，范围由(x_{min}^B, x_{max}^B)和(y_{min}^B, y_{max}^B)表示。

两个物体相撞的条件是：

$$
x_{max}^A \geq x_{min}^B \quad \text{and} \quad x_{min}^A \leq x_{max}^B \quad \text{and} \quad y_{max}^A \geq y_{min}^B \quad \text{and} \quad y_{min}^A \leq y_{max}^B
$$

可以用下面的Python代码来实现这一逻辑：

def aabb_collision(aabb1, aabb2):
    """
    检测两个AABB是否碰撞
    aabb1: [x_min, x_max, y_min, y_max]
    aabb2: [x_min, x_max, y_min, y_max]
    """
    return not (aabb1[1] < aabb2[0] or
                aabb1[0] > aabb2[1] or
                aabb1[3] < aabb2[2] or
                aabb1[2] > aabb2[3])

# 示例
aabb1 = [0, 1, 0, 1]
aabb2 = [0.5, 1.5, 0.5, 1.5]
print(aabb_collision(aabb1, aabb2))  # 输出: True

2. 曲面光滑与细分

另一个计算几何在图形学应用的领域是曲面细分与光滑处理。细分曲面技术广泛应用于现代建模和渲染管线中，允许艺术家和设计师创建复杂且光滑的模型。

细分算法，如 De Casteljau 算法或 Catmull-Clark 算法，依赖于计算几何中的点插值技术。通过不断细分平面图形，我们可以实现非常平滑的曲面效果。

应用实例：Catmull-Clark细分算法

Catmull-Clark 算法通过在每个多边形中引入新点来细分原始网格。具体步骤如下：

1. 计算每个边的中点。
2. 计算每个面中心点。
3. 创建新顶点，这些顶点由原始点、边中点及面中心点位置决定。
4. 重排列顶点。

下面是使用 Python 伪代码实现的细分算法：

def catmull_clark_subdivision(vertices, faces):
    new_vertices = []
    edge_midpoints = {}
    face_points = []

    # 计算边中点和面中心
    for face in faces:
        face_point = [0, 0, 0]
        for v in face:
            face_point = [face_point[i] + vertices[v][i] for i in range(3)]
        face_point = [p / len(face) for p in face_point]
        face_points.append(face_point)

    # 处理边
    for face in faces:
        for i in range(len(face)):
            v1 = face[i]
            v2 = face[(i + 1) % len(face)]
            key = tuple(sorted([v1, v2]))
            if key not in edge_midpoints:
                mid_point = [(vertices[v1][j] + vertices[v2][j]) / 2 for j in range(3)]
                edge_midpoints[key] = mid_point

    # 创建新顶点和细分面
    # 这里省略了细分面生成的具体细节
    return new_vertices, face_points

3. 曲线与曲面的描绘

计算几何在图形学中也用于确定和渲染曲线与曲面。贝塞尔曲线和 B-Spline 曲线是最常用的工具。它们依赖点的位置和控制点，以创建平滑的曲线和表面。

应用实例：贝塞尔曲线

贝塞尔曲线可以通过控制点进行线性插值。定义一个贝塞尔曲线的简单公式如下：

$$
B(t) = \sum_{i=0}^{n} P_i \cdot b_{i,n}(t)
$$

其中，$b_{i,n}(t)$ 是贝塞尔基函数，$P_i$ 是控制点。

可以使用下面的代码生成二次贝塞尔曲线：

def bezier_curve(P0, P1, P2, t):
    """
    计算二次贝塞尔曲线
    P0, P1, P2: 控制点
    t: 从0到1的参数
    """
    return [(1 - t) ** 2 * P0[i] + 2 * (1 - t) * t * P1[i] + t ** 2 * P2[i] for i in range(3)]

# 示例
P0 = [0, 0, 0]
P1 = [1, 2, 0]
P2 = [2, 0, 0]
t = 0.5
point_on_curve = bezier_curve(P0, P1, P2, t)
print(point_on_curve)  # 输出: [1.