齐次坐标下的OpenGL sutherland-hodgman多边形裁剪算法（4D，CCS）

Question

我有两个问题。（我在下面标出了1、2）

在 OpenGl 中，裁剪由 sutherland-hodgman 完成。但是，我想知道如何在齐次系统 (4D)

中使用 sutherland-hodgman 算法

我做了一个情况。在VCS中，有一条线，R= (0, 3, -2, 1), S = (0, 0, 1, 1)（线的终点）平截头体是 right = 1, left = -1, near = 1, far = 3, top = 4, bottom = -4 因此投影矩阵P为

1    0    0   0
0   1/4   0   0
0    0   -2  -3
0    0   -1   0

如果我们用P计算直线，那么每个端点都是这样

R' = (0, 3/4, 1, 2), S' = (0, 0, -5, -1)

我知道现在不应该做透视分割，因为如果做透视分割，裁剪结果是不正确的。

这里我很好奇。什么是正确的裁剪，因为我们不只是做透视分割。这里有什么数学性质？
以上情况如何计算裁剪结果？

（两个交点出现在w-y坐标系，搞得我一头雾水，我以为结果线是一条，不是分两部分）

Answer 1

你说的是齐次系统（4D）中的多边形裁剪，但从你的问题来看，我认为你实际上是指齐次坐标，这更有意义。（有许多可能的同质系统。）

好的，所以你想使用“4D”坐标，它实际上是“3D 坐标和一个 w 项”。 w 项表示（投影变换）将 screen-space 坐标与原始世界 space 位置部分关联的投影项。假设您对 projective space clipping 不感兴趣，这个术语不相关。

我这样假设是因为您描述的裁剪框 axis-aligned 在 3D 平面上。即使在 3D 中旋转或缩放 space，每个平面仍然是 3D 平面，第 4 个坐标始终为“1”。

那么如何剪辑：

在裁剪框的每个平面上裁剪线段L，即总共6个裁剪平面（每个裁剪平面的法线你描述的很贴切），看看是否有交点v被直线和测试平面 P 使得

v 位于线段上（即 t 介于 0 和 1 之间）
v 位于平面 P 的边界内（即坐标不应超出任何相邻平面。由于您使用的是 axis-aligned 裁剪平面，因此很容易检查。）

(3D + w) 线和其中一个 3D 平面之间的任何交点都以 3D 形式出现，并且交点必须是 3D 坐标。您可以使用第 4 个 w 坐标将这些坐标中的每一个扩展为“4D”坐标，以便您可以使用 4x4 矩阵进一步转换它们以进行视图和投影处理。

Answer 2

我不太确定您是否正确理解了 sutherland-hodgman 算法（或者至少我没有理解您的示例）。因此，我将在这里证明，裁剪发生在透视划分之前还是之后没有任何区别。证明仅针对一个平面显示（必须对所有 6 个平面进行裁剪），因为在彼此之后应用多个此类裁剪操作在这里没有区别。

假设剪辑 space 中有两个点（如您所述）R' 和 S'。我们有一个以 hessian 范式 [n, p] 给出的裁剪平面 P（如果我们采用左侧平面，则为 [1,0,0,1]）。

如果我们在纯 3d 中计算 space (R^3)，那么检查一条线是否穿过这个平面将通过计算两个点到平面的符号距离并检查是否符号不同。点 X = [x/w,y/w,z/w] 的符号距离由

给出

D = dot(n, X) + p

让我们写下实际方程式（包括透视除法）：

d = n_x * x/w + n_y * y/w + n_z * z/w + p

为了找到确切的交点，我们将再次在 R^3 space 中计算两个点 (A = R'/R'w, B = S'/S'w ) 到平面的距离 (da, db) 并执行线性插值（我只会在这里写 x-coordinate 的方程式，因为 y 和 z 的工作方式相似）：

x = A_x * (1 - da/(da - db)) + A_y * (da/(da-db))
x = R'x/R'w * (1 - da/(da - db)) + S'x/S'w * (da/(da-db))

并且 w = 1（因为我们在两个 w = 1 的点之间进行插值）

现在我们已经从中知道裁剪必须在透视划分之前发生，因此我们必须调整这个等式。这意味着，对于每个点，裁剪立方体具有不同的缩放比例 w。让我们看看当我们尝试在 P^3 中执行相同的操作时会发生什么（在透视划分之前）：

首先，我们 "revert" 透视除以得到 X=[x,y,z,w] 到平面的距离由

给出

d = n_x * x/w + n_y * y/w + n_z * z/w + p
d = (n_x * x + n_y * y + n_z * z) / w + p
d * w = n_x * x + n_y * y + n_z * z + p * w
d * w = dot([n, p], [x,y,z,w])
d * w = dot(P, X)

因为我们只对整个计算的符号感兴趣，我们没有通过操作改变它，我们可以比较 D*ws 并得到相同的 inside-out 结果R^3.

对于R'和S'这两个点，P^3中的计算距离为dr = da * R'w和ds = db * S'w。当我们现在使用与上述相同的插值方程时，但对于 R' 和 S'，我们得到 x:

x' = R'x * (1 - (da * R'w)/(da * R'w - db * S'w)) + S'x * (da * R'w)/(da * R'w - db * S'w)

在第一个视图中，这看起来与我们在 R^3 中得到的结果有很大不同，但由于我们仍在 P^3（因此 x'）中，我们仍然需要对结果进行透视划分（这是允许的，因为插值点将始终位于 view-frustum 的边界，因此除以 w 不会引入任何问题）。内插的 w 分量给出为：

w' = R'w * (1 - (da * R'w)/(da * R'w - db * S'w)) + S'w * (da * R'w)/(da * R'w - db * S'w)

并且在计算 x/w 时我们得到

x = x' / w';
x = R'x/R'w * (1 - da/(da - db)) + S'x/S'w * (da/(da-db))

这与在 R^3 中计算所有内容时的结果完全相同。

结论：无论先透视分割后插值还是先插值后分割，插值得到的结果都是一样的。但是对于第二种变体，我们避免了点从观察者后面翻转到前面的问题，因为我们只划分保证在视锥体内部（或边界上）的点。

齐次坐标下的OpenGL sutherland-hodgman多边形裁剪算法（4D，CCS）

OpenGL sutherland-hodgman polygon clipping algorithm in homogeneous coordinates (4D, CCS)

opengl

graphics

directx

perspective

clipping