《3D数学基础：图形和游戏开发》第九章笔记

9.1节 关于图形的表示法分类

9.2节 介绍了射线

9.3节 介绍了球和圆

9.4节 介绍了边界盒

9.5节 介绍了平面

9.6节 介绍了三角形

9.7节 介绍了多边形

Chapter 9 Geometric Primitives

Representation Techniques

这一节介绍不同的用来表达基本图形的方法：

第一种是隐式表达（Implicit form），即用一个等式或不等式来描述关系，如下式是描述球的，当为等号时，说明点在球面上，如果小于则说明点在球内，大于说明点在球外。

x2+y2+z2=1

第二种表达式为参数化表达（Parametric form），如下式为参数化表达圆，其中t为的参数，通常来说参数的数值为[0,1]

x(t)=cos⁡2πt,y(t)=sin⁡2πt

参数化表达圆的示意图如下：

参数化表达可以进一步细分为一元表达（univariate）， 即只有一个参数，和二元表达（bivariate），即有两个参数。一元表达描述的是一个曲线，二元表达描述的是一个曲面。

第三种表达方式是直接表达，但这种表达没有统一的形式。如使用两个点来描述一条直线，用半径和圆心来描述一个圆。

Lines and Rays

从数学角度来说，关于线条有三个定义：

1. 直线是用来描述一个朝正反方向都无限延伸的线
2. 线段是用来描述由确切两个点构成的有限长度的线。这两个点并没有起点和终点之分，即不存在方向。
3. 射线是用来描述有一个起点，和朝一个方向无限延伸的线。

从几何角度来说

1. 直线描述与数学角度相同
2. 线段描述与数学角度相同
3. 射线是用来描述一个有方向的线段，即存在起点和终点的概念。

在电子游戏中，通常只使用射线，直线和线段的概念很少出现。

1. 如果用直接方法定义射线，直接给定终点和起点即可，Porg和Pend

2. 用参数化表达射线，表达式如下 p(t)=p0+td 其中，P0为起点，d为射线的有向长度，参数t的取值范围是[0,1]

   射线的参数化表达也可以进一步拆分为两部分，即分别描述x分量和y分量 x(t)=x0+tΔx,y(t)=y0+tΔy

   可以看出这个表达存在四个自由度，分别是x0和y0表示起点和Δx和Δy表示一个分量上的有向长度。

Special 2D Representation of Lines

这一节介绍一些二维射线的特殊表达

1. 截距形式（Slope-interpret form）

   y=mx+y0

   其中m表示射线的斜率(rise/run)，y0表示截距（y-intercept），如下图所示

   

   截距形式的问题在于，它无法表达沿着Y轴向上的射线。

2. 隐式表达（Implicit definition）

   射线的隐式表达实际上相当于截距形式的变形

   ax+by=d

   而且隐式表达可以进一步使用向量的点乘表达，

   p⋅n=d

   其中n=[a,b]表示射线的法线方向，且是一个单位向量。

   p=[x,y]表示射线上的点。

   d表示射线沿着n方向上离原点的距离。

   如下所示：

   

3. 垂直线等分法： 该方法定义两个点q,r，射线用来描述距离这两个点距离相等的点的几何。如下图所示：

   

Converting between Representations

直接表达法：

和Pend和Porg

y=mx+y0

隐式表达法：

ax+by=d

向量表达法：

p⋅n=d

垂直线等分法法：

与点和点距离相同的点的合集与点q和点r距离相同的点的合集

上述相互之间的转换方法为：

1. 直接表达法与隐式表达法的转换

   直接表达即为通过两个点Pend和Porg来描述一条射线，为了将其转换为隐式表达法首先需要计算出两点之间的有向距离

   d=pend −porg 

   d不仅表示两点间的距离还表示两点间的方向

   因此如果表示为截距法，那么射线的斜率为m=dy/dx，将点Porg代入式子中，可以求得y0=yorg−dydxxorg

   转换为隐式表达法则有：

   a=dy,b=−dx,d=xorg dy−yorg dx

2. 隐式表达法和截距法的转换

   使用隐式表达法中的a,b,d来描述截距法，则有 y=−abx+db

3. 隐式表达法求射线的法线和距离

   隐式表达法可以直接转换为向量形式的表达，即

   ax+by=p⋅n=[xy]⋅[ab]=d

   即nt[ab]，如果将其转换为单位向量，即

   n^=[ab]/a2+b2

   如果用n^作为表达式，则原表达式两边都要等除a2+b2，即

   [xy]⋅[ab]a2+b2=da2+b2

   [xy]⋅n^=distance

   其中n^为射线的法线，distance为射线沿着法线方向与原点的距离。

4. 垂直线等分法转换为隐式表达法

   有两个点和点q和点r，其中r是x轴分量更大的点。

   可以得到由这两个点构成的线段的斜率为ry−qr/rx−qx，因为所求的射线，即这两个点中间的垂直线斜率相反，所以可以得到所求射线的斜率m=qr−ry/rx−qx

   转换为隐形表达式，则可得：

   a=qy−ryb=rx−qx

   点和点q和点r的中点在所求射线上，且该中点为q+r−q2=q+r2，将该点带入隐形表达式，可得

   d=q+r2⋅[ab]

   进一步化简得：

   d=q+r2⋅[ab]=q+r2⋅[qy−ryrx−qx]=(qx+rx)(qy−ry)+(qy+ry)(rx−qx)2=(qxqy−qxry+rxqy−rxry)+(qyrx−qyqx+ryrx−ryqx)2=rxqy−qxry

Sphere and Circles

球常用来作为物体的边框，一是用球作为边框比较简单，二是因为当用球来作为边框时，物体的旋转并不会造成任何的影响，因此物体旋转后的再次计算边框。

球的隐式定义如下：

‖p−c‖=r

其中p表示球上的点,c表示球心，两者都是向量。非向量形式的隐式表达如下：

(x−cx)2+(y−cy)2=r2(x−cx)2+(y−cy)2+(z−cz)2=r2

球的其他计算数学计算如下：

1. 直径 D=2r
2. 周长 C=2πr=πD
3. 圆的面积 A=πr2
4. 球的表面积 S=4πr2
5. 球的体积 V=43πr3

Bounding Boxes

AABB（Axially aligned bounding box）通常用来表示立方体形状的边框，而且立方体的边必须与当前坐标系下坐标轴相平行。

另一种不太常用的立方体边框为OBB（Oriented bounding box），这里立方体的边与坐标系的轴没有任何约束。相对来说，AABB更容易创建，而且OBB仅仅是AABB在一个坐标系下旋转，所以这一节只会讨论AABB。

OBB和AABB的区别并不在于边框本身，而是在于坐标系。如果一个边框用于在世界坐标中旋转了的物体，那么这个边框从物体坐标系角度看是AABB，但是从世界坐标系角度看是OBB

Representing AABBs

一种表达方式是限定三个坐标系的范围，即

xmin≤x≤xmax,ymin≤y≤ymax,zmin≤z≤zmax

也可以通过两个对角线的点来进行表达，即

pmin=[xminyminzmin],pmax=[xmaxymaxzmax]

其中边框的中点可以表示为：

c=(pmin+pmax)/2

边框的尺寸向量（Size vector）用s表示，值为对角线两个点间的有向距离：

s=pmax−pmin

同样也可以计算半径向量，如下所示：

r=pmax−c=s/2

关于边框的值和Pmin,Pmax,c,s,和r，除了和s和r这两个值的搭配，通过其他任意搭配都可以求出边框的其他值。

Computing AABBs

//TODO

// 书中给出了关于AABB的类

AABBs versus Bounding Spheres

AABB对于球边框的优势：

1. 计算由一系列的点构成的AABB面只需要线性时间（比较出最小的点和最大的点即可），而计算出由一系列的点构成的球相对复杂。
2. 通常来说，对于同一个物体AABB边框会更小，最坏的情况下，AABB也只比球边框大不到两倍（当物体本身是一个球时），而最坏情况下球边框可能会比AABB大很多。 如下所示，蓝色为球边框，红色为AABB

球边框对于AABB边框的优势：

1. 物体的变换不会造成球边框的变化，如下图所示：

Transforming AABBs

如之前所述，AABB边框在物体变换后也会发生变化，这一节介绍如何计算变换后的AABB边框。

通常有两种思路，一种是对变换后的物体再次求解AABB边框，第二种是直接对AABB边框进行同样的变换。通常第二种方法比第一种计算更快，因为无论物体本身多复杂，计算AABB的变换只需要计算8个顶点，所以通常第二种方法用的较多。

第二种方法中直接将AABB变换后的结果作为新的AABB是不行的，因为可能旋转会导致原先的Pmax变得比Pmin更小。所以直接对AABB边框进行同样的变换后，根据变换后的8个顶点，得出新AABB框，如下图所示：

上图的右半部分是旋转后的物体和ABBB，图中蓝色的部分是直接对AABB进行了旋转，此时在世界坐标系下，它已经变成了OBB。 内部的红色边框为第一种方法，是根据旋转后的图形再次求解AABB。该方法准确但效率较低。 外部的红色边框为第二种方法，它是由旋转后的原AABB（蓝色部分）计算得到的，它比理想上的AABB框要更大。该方法迅速，只需要计算AABB的顶点，但通常会造成计算出的边框更大。

第二种方法的计算如下，假设[xyz]是原先AABB的顶点，变换后的顶点为[x′y′z′]，则转换果然如下：

[x′y′z′]=[xyz][m11m12m13m21m22m23m31m32m33]x′=m11x+m21y+m31zy′=m12x+m22y+m32zz′=m13x+m23y+m33z

其中矩阵表示进行的变换。

通常的的方式是将八个顶点分别通过上式进行计算，然后找出最小点和最大点。

但是观察后发现，可以直接通过矩阵中的元素正负号来直接求出最大点和最小点，下面以二维平面的变换作为例子，即变换为：

[x′y′]=[xy][m11m12m21m22]x′=m11x+m21yy′=m12x+m22y

在二维平面下中，AABB有四个顶点，[xmin,ymin],[xmin,ymax],[xmax,ymin],[xmax,ymax]

所以x′也相对有四种可能，即m11xmin+m21ymin，m11xmin+m21ymax，m11xmax+m21ymin，m11xmax+m21ymax，

如果将x′拆分成两部分来看，即m11x和m21y，如果m11是正数，那么要求得更小的x′，x是xmin时更合适，反之xmax更合适。对于m21也是同理，ymin适合m21是正数的情况，ymax适合m21是负数的情况

因此求xmin′，只需要判断m11和m21的大小，然后直接选取对应的x和y分量，进行累加就行，不需要求出所有的x′可能进行比较。

//TODO //书中有对应的求新AABB算法

Planes

3D中的平面对应2D中的射线，其定义也与在2D中的射线类似：与给定的两个点距离相同的所有的点的集合。

The Plane Equation：An Implicit Definnition of a plane

隐式表达法： 1. 用标量 ax+by+cz=d 2. 用向量 p⋅n=d 其中p为在平面上的点，n=[abc]为垂直平面的线。 证明如下，假设平面上还有一个点q：

n⋅p=dn⋅q=dn⋅p=n⋅qn⋅p−n⋅q=0n⋅(p−q)=0

如果要求平面的法线，对n进行归一化即可 n^=[abc]a2+b2+c2

用法线表示平面为：

p⋅n^=da2+b2+c2=distance

其中distance为平面距离原点的距离

平面分正反面，沿着法线方向看，看到的是背面，法线指向的方向是正面，如下图所示：

Defining a Plane by Using Three Points

假设有三个在平面上的点p1,p2和p3，且他们按顺时针方向排列，如下图所示：

可以按照下式，求出法线：

e3=p2−p1,e1=p3−p2,n^=e3×e1‖e3×e1‖

将任意一个点带入法线表达式，既能求出distance ，如distance=n^⋅p1

即最终表达式为

P⋅n^=n^⋅p1

"Best Fit" Plane for More than Three Points

当给定了多个点，要根据多个点求平面时，不能简单的从多个点中任意选取出三个点，因为：

1. 选取的三个点可能在一条线上
2. 多个点构成的多边形可能是凹的，即虽然按顺时针在多边形上取了三个点，但实际上它们是逆时针的
3. 由于精度或各种原因，三个点可能实际上并不在一个平面上。

所以解法是用所有的点来计算，如有以下点：

p1=[x1y1z1]p2=[x2y2z2]⋮pn−1=[xn−1yn−1zn−1]pn=[xnynzn]

则法线为：

nx=(z1+z2)(y1−y2)+(z2+z3)(y2−y3)+⋯⋯+(zn−1+zn)(yn−1−yn)+(zn+z1)(yn−y1)ny=(x1+x2)(z1−z2)+(x2+x3)(z2−z3)+⋯⋯+(xn−1+xn)(zn−1−zn)+(xn+x1)(zn−z1)nz=(y1+y2)(x1−x2)+(y2+y3)(x2−x3)+⋯⋯+(yn−1+yn)(xn−1−xn)+(yn+y1)(xn−x1)

nx=∑i=1n(zi+zi+1)(yi−yi+1)ny=∑i=1n(xi+xi+1)(zi−zi+1)nz=∑i=1n(yi+yi+1)(xi−xi+1)

//TODO: 推导该公式

在求出了n后，将所有的点都带入公式，然后求出平均的d，如下：

d=1n∑i=1n(pi⋅n)=1n(∑i=1npi)⋅n

Distance from Point to Plane

要求平面外点q距离平面的距离，可找出平面上离该点最近的点p，有向距离pq即为距离，当q处于平面的正方向，则距离为正数，否则为负数，如下图所示：

如果n是单位向量法线，即n^，那么a即是有向距离。

在实际求解的过程中，实际上并不需要算出p的位置，如下所示：

p+an^=q(p+an^)⋅n^=q⋅n^p⋅n^+(an^)⋅n^=q⋅n^d+a=q⋅n^a=q⋅n^−d

Triangles

Notation

三角形是通过三个顶点定义的。通常在左手坐标系下，三个顶点的顺序为顺时针。

三角形的边和顶点的定义如下图所示：

e1=v3−v2,e2=v1−v3,e3=v2−v1l1=‖e1‖,l2=‖e2‖,l3=‖e3‖

根据顶点，边，角的关系，有正弦和余弦定理，如下所示：

正弦定理为：

sin⁡θ1l1=sin⁡θ2l2=sin⁡θ3l3

余弦定理为：

l12=l22+l32−2l2l3cos⁡θ1l22=l12+l32−2l1l3cos⁡θ2l32=l12+l22−2l1l2cos⁡θ3

Area of a Triangle

最普通的求三角形面积为通过底和高，即

A=bh/2

海拉公式，可以通过三角形的三边长度来求得三角形面积：

s=l1+l2+l32=p2A=s(s−l1)(s−l2)(s−l3)

还可以通过三角形的顶点本身来求得三角形面积，首先需要对三个顶点相减，获得三条边的向量e1,e2,e3，然后再任意取其中两条求面积如下所示：

A=‖e1×e2‖2

该公式推导如下：

首先三角形的三条边都与X轴形成了一个梯形，如下图所示：

对该梯形的面积定义正负，如果边的顶点是由左到右，则梯形面积为正，否则面积为负，三边构成的梯形面积如下：

A(e1)=(y3+y2)(x3−x2)2A(e2)=(y1+y3)(x1−x3)2A(e3)=(y2+y1)(x2−x1)2

三角形的面积为三个梯形的累加，如下所示：

A=A(e1)+A(e2)+A(e3)=(y3+y2)(x3−x2)+(y1+y3)(x1−x3)+(y2+y1)(x2−x1)2=((y3x3−y3x2+y2x3−y2x2)+(y1x1−y1x3+y3x1−y3x3)+(y2x2−y2x1+y1x2−y1x1))2=−y3x2+y2x3−y1x3+y3x1−y2x1+y1x22=y1(x2−x3)+y2(x3−x1)+y3(x1−x2)2

将上式中的y1,y2,y3都减去y3，相当于三角形向下平移了一部分，所以结果不会变，即如下所示：

A=y1(x2−x3)+y2(x3−x1)+y3(x1−x2)2=(y1−y3)(x2−x3)+(y2−y3)(x3−x1)+(y3−y3)(x1−x2)2=(y1−y3)(x2−x3)+(y2−y3)(x3−x1)2

上述结果即为点乘，即

A=‖e1×e2‖2

Barycentric Space

重心系统（Barycentric Space）是用三角形的三个顶点来描述三角形的位置，表达式为：

(b1,b2,b3)≡b1v1+b2v2+b3v3

b1+b2+b3=1

重心系统实例如下：

注意其中三个顶点的数值，即

(1,0,0)≡v1,(0,1,0)≡v2,(0,0,1)≡v3

三角形内的点，数值会在[0,1]之间，三角形外的点最少会有一个负数。

下图是重心系统的镶嵌，可以看出重心系统中值的运算规律：

如第一个数值表示顶点V1对面的边所平行的部分，即V2和V3构成的边。因此可以看到该边上的点，值都为(0,x,x)，而平行于该边且经过v1的边上面的点都为(1,x,x)，v1点为(1,0,0)。同理顶点v2对面，由v1和v3构成的边，表示第二个参数，即(x,0,x)。第三个参数的数值也同理可得。

重心系统的维度不是由参考点的维度决定的，而是由参考点的数量决定的。如三角形的重心系统，无论三角形的点是二维还是三维的，只要是三角形就需要三个参考点，所以该重心系统是二维的。

在图形学中，重心系统常应用在在计算顶点插值时，如计算片段的颜色。还被应用在计算相交问题时，一根射线可以根据与各个三角形片元的重心值判断是与哪个片元相交。

Calculating Barycentric Coordinates

如果通过重心系统计算笛卡尔坐标系，可以通过上述公式：

(b1,b2,b3)≡b1v1+b2v2+b3v3

由笛卡尔坐标系计算重心表达如下：

已知三个点和所求点的笛卡尔坐标系，如下图所示：

对于二维空间中的三角形，根据三角形重心的定义，可得：

b1x1+b2x2+b3x3=pxb1y1+b2y2+b3y3=pyb1+b2+b3=1

三个表达式对应三个未知数b1,b2,b3，因此这是一个三元一次方程的求解，结果为：

b1=(py−y3)(x2−x3)+(y2−y3)(x3−px)(y1−y3)(x2−x3)+(y2−y3)(x3−x1)b2=(py−y1)(x3−x1)+(y3−y1)(x1−px)(y1−y3)(x2−x3)+(y2−y3)(x3−x1)b3=(py−y2)(x1−x2)+(y1−y2)(x2−px)(y1−y3)(x2−x3)+(y2−y3)(x3−x1)

根据上节中，通过顶点求三角形面积的方法，可以看出上式的分子和分母都是面积公式的两倍，因此也可以化简为：

b1=A(T1)/A(T),b2=A(T2)/A(T),b3=A(T3)/A(T)

对于三维空间中的三角形，也可以通过类似的方法求得结果。但是因为是三维空间，所以可以列出四个表达式（x,y,z三个表达式+一个和为1的限制），但是未知数还是三个（b1,b2,b3）。因此需要删除一个表达式。

但是不能随便删除一个表达式，因为删去一个表达式的操作相当于将三维空间中的三角形投影至一个平面上，而如果三角形是垂直或者接近垂直于该平面，那么就会有问题。因此要选择投影面积最大的平面。

可以根据法线判断出投影面积最大的平面，如果法线为[0,1,0]，那么法线垂直于xz平面，即xz平面最大，即删除y，也因此法线上哪个分量最大，删除哪个表达式。

上述已经求得重心可以通过三角形的面积得到：

b1=A(T1)/A(T),b2=A(T2)/A(T),b3=A(T3)/A(T)

同时由之前公式可知，面积可以通过叉乘求得，即：

A=‖e1×e2‖2

因此理论上可以通过用顶点获取三角形的各边，再通过边的叉乘的得到结果。但存在的问题是，上述公式中的求模永远返回的是正数，因此这样就无法计算三角形外的点。

解决方法是再通过一个点积，如下所示：

c⋅n^=‖c‖‖n^‖cos⁡θ=‖c‖(1)(±1)=±‖c‖

其中c为叉乘的结果，n^为法线，因此c必然平行于n^。如果两者同向则返回正数，否则返回负数。

整个计算如下图所示：

e1=v3−v2,e2=v1−v3,e3=v2−v1d1=p−v1,d2=p−v2,d3=p−v3

n^=e1×e2‖e1×e2‖

b1=A(T1)/A(T)=(e1×d3)⋅n^(e1×e2)⋅n^b2=A(T2)/A(T)=(e2×d1)⋅n^(e1×e2)⋅n^b3=A(T3)/A(T)=(e3×d2)⋅n^(e1×e2)⋅n^

Special Points

1. 质心（center of gravity） 质心为三角形三个顶点位置的平均值，即：

   cGrav=v1+v2+v33

   其重心坐标值为： (13,13,13)

2. 内心（incenter） 内心距离三角形三条边的距离相等，也因此是三角形内切圆的圆心，如下图所示：

   

   计算方法如下：

   cIn=l1v1+l2v2+l3v3p

   其重心坐标值为：

   (l1p,l2p,l3p)

   内心与三角形边的距离为：

   rIn=2Ap

3. 外心（circumcenter） 外心是距离三角形三个顶点距离相同的点，如下图所示：

   

   计算过程如下：

   先根据上图中的标识算出如下的中间变量：

   d1=−e2⋅e3d2=−e3⋅e1d3=−e1⋅e2c1=d2d3c2=d3d1c3=d1d2c=c1+c2+c3

   其中外心的点为：

   cCirc=(c2+c3)v1+(c3+c1)v2+(c1+c2)v32c

   重心坐标值为：

   (c2+c32c,c3+c12c,c1+c22c)

   距离三角形三个顶点的值为：

   rCirc=(d1+d2)(d2+d3)(d3+d1)/c2

Polygons

通常来说，多边形是一个由顶点和边组成的平面图形。

Simple versus Complex Polygons

简单多边形不存在洞，复杂多边形存在洞，如下所示：

可以通过加上一对缝合边将简单多边形转换为复杂多边形，如下所示：

还有一种自相交多边形（Self-intersecting polygon），如下所示：

Convex versus Concava Polygons

关于凹多边形(Concave)和凸多边形(Convex)有多种区分方法：

1. 凹多边形至少有一个凹点（concavity），如下所示：

   

2. 凹多边形至少有一对顶点的连线是在多边形外的。

3. 凹多边形沿着所有顶点走，顶点的旋转顺序会发生变化（顺逆时针）。 这个可以通过对每两边进行叉乘来判断，如果叉乘的结果与法线方向不一致，说明顺序为逆时针，否则为顺时针。如果按顺时针顺序来取两边进行叉乘，突然出现了结果与法线相反的情况，则该两边中间为凹点。

4. 无论是凸多边形还是凹多边形，其内角和都是(n−2)360∘。但是通过点积求得的是较小角的角度。如果对凸多边形的每两边都点积，则结果和为(n−2)360∘，而凹多边形不是。 如下图所示：

Triangulation and Fanning

每一个n条边的凸多边形都能分为n−2个三角形。如下图所示：

但这样切分的问题在于，可能会切出一条非常细的三角形。

解决方法为每次切分前，先找出能使内角最大的切割方法，然后切一刀，将图形分为两部分。再对每一个部分迭代使用上述方法，直到只剩下三角形。这样可以一定程度避免出现细长三角形，但效率不如直接切分高。