Mathematics for 3D Game Programming and Computer Graphics 笔记 Chapter 4

Chapter4 3D Engine Geometry

4.1 Lines in 3D Space

P1 P2 是3D空间中两点,则经过这两点的直线可表示为

P(t) = (1 – t) P1 + tP2         (4.1)

t的范围是所有实数.t在0-1之间时表示 P1 到 P2 的线段.

一个端点S和一个方向V可以表示一条射线:

P(t) = S + tV         (4.2)

t的范围是[0,+∞),若t为整个实数范围,上式也可以表示直线,若令 S = P1, V = P2 – P1, 则等同于 4.1 式.

4.1.1 点到线的距离

line

 

点Q到直线的距离d的计算:

d² = (Q – S)² – [proj(Q – S)]² = (Q – S)² -{ [(Q – S)V/V²]V

4.1.2 两条直线间的距离

二维空间中的两条直线可能平行或相交,三维空间中的两条直线则可能平行,相交或异面.

两条异面直线之间的最短距离计算:

P1(t1) = S1 + t1V1

P2(t2) = S2 + t2V2

f(t1, t2) = ||P1(t1) – P2(t2)||²

求使 f 最小的一组 t1 t2 的值, 方法是求偏导数为0的t值:

∂f / ∂t1 = 2t1V1² + 2S1V1 – 2V1S2 – 2t2V1V2 = 0

∂f / ∂t2 = 2t2V2² + 2S2V2 – 2V2S1 – 2t1V1V2 = 0

上面两式解得:

┌  ┐        1        ┌          ┐┌         ┐
│t1│= -------------- │-V1²  V1V2││(S2-S1)V1│
│t2│  (V1V2)²-V1²V2² │-V1V2  V1²││(S2-S1)V2│
└  ┘                 └          ┘└         ┘

将t1 t2 带入 f 就能得到最短距离d². 若 (V1V2)²-V1²V2² = 0, 则两直线平行.若V1V2为单位向量,上式可以简化,因为 V1² = 1 , V2² = 1

4.2 Planes in 3D Space

知平面上一点P和其法向量N,一个平面上的点Q可表示为 N(Q – P) = 0,一个平面通常表示为:

Ax + By + Cz +D = 0

其中 A B C 是 N 的 x,y,z 分量, D = -NP, |D|/||N|| 的值为该平面到过原点的与其平行的平面的距离.

通常使N为单位向量,这样下式

d = NQ + D

可表示为任一点Q到平面的距离,若 d = 0,则Q在平面上,若d>0,则Q在法线方向指向的半空间中.

可以很方便的使用四维向量<N,D>来表示平面 NQ+D=0

4.2.1 线与面的相交

线: P(t) = S + tV, 于平面相交:

NP(t) + D = 0

t = -(NS+D) / NV            (4.16)

t带入P(t), 得交点. 若NV=0,则线与面平行,在此前提下,若 NS+D = 0,则线在面内,否则无交点.

在四维空间, L = (N, D) , t = -LS/LV, 其中S为点, w坐标为1,V是方向向量,w坐标为0,与4.16式是相同的.

4.2.2 三个平面相交

设三个平面为 L1 = (N1,D1), L2 = (N2,D2), L3 = (N3,D3), 交点为Q,则 L1Q = L2Q = L3Q = 0, 即:

┌           ┐       ┌   ┐
│N1x N1y N1z│       │-D1│
│N2x N2y N2z│Q= MQ =│-D2│
│N3x N3y N3z│       │-D3│
└           ┘       └   ┘

若M不可逆,3个法线的在同一平面上,没有交点(可能有共同交线).

对于两个不平行的平面,两者存在交线,由于交线垂直于两个平面的法线,因此可以表示为V = N1×N2,若要得到交线上一点,可以构造平面(V,0),与两个平面求交点

    ┌           ┐┌   ┐
    │N1x N1y N1z││-D1│
Q = │N2x N2y N2z││-D2│
    │Vx  Vy  Vz ││ 0 │
    └           ┘└   ┘

4.2.3 Transforming Planes

平面 L = (N, D), F为变换矩阵,则

L’ = (F-1)TL

4.3 View Frustum 视锥体

frustum

视锥体(frustum)由6个面组成,包含了所有相机可见的物体,处于相机空间中,原点是相机的位置,x轴指向右,y轴指向上,z轴的方向跟渲染库有关,OpenGL向后,D3D向前,上图标明的是OpenGL中的坐标系.

4.3.1 Field of View

top

图中α为水平视角,视角越大,焦距越短,减小视角可增大焦距,造成镜头拉近的效果.

纵横比/屏幕高宽比(aspect ratio) = 高/宽,例如640*480的纵横比为0.75,由于投影面通常不是正方形,长宽不同,垂直视角和水平视角通常不相同.

right

 

将投影面缩放n/e倍可以得到近剪裁面near plane的边界 x = ± n/e, y = ± an/e.

4.3.2 Frustum Planes

6个平面的计算如下:

planes in OpenGL

planes in OpenGL

4.4 Perspective-Correct Interpolation

一个三角形在光栅化时一次一条扫描线,顶点中的信息都要进行插值,当进行一条扫描线的处理时,每个像素的信息是根据两个顶点的信息插值的,正确的插值是非线性的,因为离相机越远的地方间隔越大,显卡处理纹理坐标时的插值都是非线性的,只有这样才能防止变形,而在许多旧显卡中,处理光照等其他信息是线性的来提高速度,在纹理的影响下差别不是很明显.

非线性插值

非线性插值

4.4.1 Depth Interpolation

在光栅化时,通过在投影面上等距离的点(代表屏幕上的像素)发出一条条射线,对射线与物体的交点进行取样.

对于一个在xz平面上的线段,我们假设它不通过原点(这样的话相机就无法看到这条线),这条线可以表示为

ax + bz = c     (c≠0)                              (4.29)

 

三角形的一条扫描线的取样

三角形的一条扫描线的取样

对于线段上的一点(x,z),我们连接它和原点,可以计算和投影面的交点,投影面上的点的z坐标总是-e,交点的x坐标p可以通过相似三角形计算:

p / x = -e / z

把上式的x解带入 4.29 式中, 得到如下结果:

 1       ap     b
--- = - ---- + ---          (4.32)
 z       ce     c

设线段的两个端点坐标是(x1,z1),(x2,z2),它们在投影面的像是(p1, -e), (p2, -e), 令 p3 = (1-t)p1+tp2, t在[0,1]的范围均匀变化时, p3可以表示在投影面上x的均匀插值, 计算通过(p3, -e)射线与线段的交点z坐标,把p3 = (1-t) p1 + tp2 代入4.32式中,得到:

z

(4.33)
这个结果表明z坐标的倒数可以以线性的方式插值.

4.4.2 Vertex Attribute Interpolation

假设一条线段的两个端点的z坐标为z1和z2,携带的另一个顶点信息值(例如缩放信息)是b1和b2,那么b1和b2也应该用与z坐标同样的形态进行插值.也就是满足:

(b3 – b1) / (b2 – b1) = (z3 – z1) / (z2 – z1)

将4.33式的z3带入上式,可以得到如下结果:

b3 = z3[ (1-t) b1/z1 + t b2/z2]

这表明 b/z 可以进行线性插值. 在光栅化一条扫描线时,GPU首先计算 1/z 的线性插值结果,然后计算它的倒数 z ,最后用 z 乘以线性插值后的 b/z 来得到正确插值后的 b 值.

4.5 Projections

将3D空间中的一点P投影到投影面上,连接P和原点,与投影面的交点可以用如下公式:

x = -e Px / Pz

y = -e Py / Pz

但是如此计算的话,得到的z坐标永远是-e,我们需要保留深度信息来进行可见性检测等操作,因此3D图形系统采用四维空间的齐次坐标来投影顶点.

4.5.1

解决上面问题的方法是把视锥体投影到齐次裁剪空间(homogeneous clip space),它是一个正方体,xyz坐标的范围都是[-1,1], 投影采用4×4矩阵,把投影后的z信息保存在w坐标中,之后除以w坐标后得到标准设备坐标(normalized device coordinates).

设P = (Px, Py, Py, 1) 是视锥体中的一点,near plane的左边 x = l, 右边 x = r, 下边 y = b, 上边 y = t, near plane 的 z = -n, P在near plane 上的坐标为:

x = -nPx/Pz   y = -nPy/Pz

在near plane上的点都满足 l<=x<=r, b<=y<=t, 我们要把它对应到[-1,1]范围:

x’ = 2(x-l)/(r-l) – 1 = [2n/(r-l)](-Px/Pz) – (r+l)/(r-l)

y’ = 2(y-b)/(t-b) – 1 = [2n/(t-b)](-Py/Pz) – (t+b)/(t-b)

由于齐次裁剪空间是左手的,对于z坐标,要把 -f< = Pz <= -n 的 -f 对应到1, -n 对应-1 .

由于1/z是线性插值的,我们把方程写成 1/Px 的函数,经过计算后:

z’ = [-2nf/(f-n)](-1/Pz) + (f+n)/(f-n)

把计算x’y’z’的三个式子都乘以 -Pz:

P’ = (-x’Pz, -y’Pz, -z’Pz, -Pz)

-x’Pz = [2n/(r-l)] Px + (r+l)/(r-l) Pz

-y’Pz = [2n/(t-b)] Py + (t+b)/(t-b) Pz

-z’Pz = [-(f+n)/(f-n)] Pz – 2nf / (f-n)

写成矩阵形式M:

          ┌                                       ┐┌  ┐
          │2n/(r-l)   0     (r+l)/(r-l)       0   ││Px│
P' = MP = │0       2n/(t-b) (t+b)/(t-b)       0   ││Py│
          │0          0    -(f+n)/(f-n) -2nf/(f-n)││Pz│
          │0          0         -1            0   ││1 │
          └                                       ┘└  ┘

经过上面的变换,Pz被保存在w坐标中,GPU就是拿这个值的倒数来进行插值的.

z值的对应关系

z值的对应关系

f值也可以是无穷,这样M33 = -1, M34 = -2n,依然可以得到正确结果.

4.5.2 正交投影

          ┌                                       ┐┌  ┐
          │2/(r-l)   0         0    -(r+l)/(r-l)  ││Px│
P' = MP = │0       2/(t-b)     0    -(t+b)/(t-b)  ││Py│
          │0          0    -2/(f-n) -2(f+n)/(f-n) ││Pz│
          │0          0         0            1    ││1 │
          └                                       ┘└  ┘