图形学笔记（十）几何2 —— 曲面细分（Loop细分、Catmull-Clark细分）、曲面简化（边坍缩、二次度量误差）、曲面正则化
1 Shadow Mapping与光线追踪
1.1 Shadow Mapping
1.1.1 概览
Shadow Mapping本质是一种图像空间的算法。
关键思想
不在阴影中的点必须可以同时被摄像机和光源看到。
1.1.2 Shadow Mapping步骤
1> 从光源渲染
从光源看场景，获得深度图（z-buffer）。
2> 从摄像机渲染
从摄像机看场景，对于每一个看到的点，将其映射回光源渲染的深度图上， 比较从光源到这个看到的点的深度和其在深度图上对应的深度，若深度一致，说明这个点可以同时被光源和摄像机看到。
1.1.3 Shadow Mapping结果
如下图非绿色的是阴影应该在的地方。
1.1.4 Shadow Mapping的问题
- 生成的是硬阴影（只对点光源）。
- 阴影的效果取决于shadow map的分辨率。
- 涉及浮点精度比较的问题。
1.2 软阴影和硬阴影
1.2.1 概览
如下图，左边是硬阴影（界限比较清晰），右边是软阴影。
1.2.2 软阴影的原理
由于点光源有大小，会形成如图所示的（Umbra）本影区域和半影（Penumbra）区域。所以会形成阴影的过渡。
1.3 进行光线追踪（Ray Tracing）的原因
光栅化不能很好的处理全局效果（如下图所示）。
-
难以做软阴影。
-
难以表现光线多次弹射，比如间接光照。
-
光栅化很快但是质量较低
-
光线追踪很准确，但是很慢
光栅化：实时（游戏），光线追踪：离线（动画）。
光线追踪一帧就要花10K个计算机小时
2 光线追踪算法
2.1 光线（图形学角度做的假设）
- 光线沿直线传播。
- 光线和光线不会发生碰撞。
- 光线会从光源发出，打到场景中，经过反射折射等最终进入人眼（光线具有可逆性）。
2.2 光线投射（Ray Casting）
光线投射是光线追踪中用于生成初始光线的第一步。
- 通过从每一个像素发射光线来生成图像。
- 通过从光源发射光线来检测阴影。
从视点开始经过像素获得与场景中物体最近的交点。
和光源连线，判断是否对光源可见从而确定该点是否在阴影中。
然后计算着色，写回像素结果。
2.3 Recursive（Whitted- Style） Ray Tracing
此算法在79年渲染1帧用了74min、06年PC需要6s、12年的GPU需要1/30s。
此算法要考虑反射和折射的光线，如下图所示。
对每一个弹射点都要计算着色的值，然后把所有着色的值都加到像素的值里面去。
光线有不同的分类：primary ray、secondary ray、shadow ray。
3 光线与物体的交点 Ray-Object intersections
3.1 基本概念
3.1.1 光线
光线在数学上是有起点和方向的射线，表达式如下，t代表时间。
3.1.2 平面
通过一个法向量和一个平面上的点来进行定义。
平面的表达式 平面是满足下面条件所有p点的集合。
p
:
(
p
?
p
′
)
?
N
=
0
p:(p-p')·N=0
p:(p?p′)?N=0
3.2 光线与球求交
光线与球的交点p，必须要满足p既在光线上也在球上。
球的表达式如下：
将光线方程代入，获得如下等式：
最后求得（解的的t代入参数方程就是交点）：
3.3 光线和隐式表面求交
如果隐式表面的表达式
P
:
f
(
p
)
=
0
P:f(p)=0
P:f(p)=0
则把这个式子代入光线等式，得到
f
(
o
+
t
d
)
=
0
f(o+td)=0
f(o+td)=0
解出来结果t，即可得到交点（t必须是实数，也要是正数）。
3.4 光线和三角形面求交
3.4.1 原因
光线和三角形求交有如下作用：
- 渲染：可见性、阴影、光照…
- 几何：可以判断点是再物体内还是物体外。
对任何一个封闭的曲面，在内部找一个点，如果点在形状内，那么从这个点发出的任意方向的射线与此物体的交点数量一定是奇数。
3.4.2 算法（与平面求交再判断是否在三角形内）
简单的办法是让场景中的每个三角形与光线进行求交计算，但是有如下严重问题。
- 简单但是运算量大。
- 可以有0或1个交点。
如果想要计算光线和三角形面的交点，因为三角形在平面内，所以可以把光线和三角形求交拆成两个问题：
- 让光线与平面求交（目前与平面求交比与三角形求交容易）。
- 判断与平面的交点是否在三角形内。
让光线与平面求交 将
p
=
r
(
t
)
p=r(t)
p=r(t)代入平面的表达式（t是正实数），结果如下。
t
=
(
p
′
?
o
)
?
N
d
?
N
t=\frac{(p'-o)·N}{d·N}
t=d?N(p′?o)?N?
判断与平面的交点是否在三角形内 上一步通过参数t可以获得交点，然后通过向量叉乘可以获得交点是否在三角形内。
3.4.3 Moller Trumbore算法
Moller Trumbore算法是一种使用重心坐标计算的一种更快的方法。在下面的式子中，左边是光线的表达式，右边是三角形上一点的重心坐标形式。
O
?
+
t
d
?
=
(
1
?
b
1
?
b
2
)
P
?
0
+
b
1
P
?
1
+
b
2
P
?
2
\vec O+t\vec d=(1-b_1-b_2)\vec P_0+b_1\vec P_1+b_2\vec P_2
O+td=(1?b1??b2?)P0?+b1?P1?+b2?P2?
根据上面的等式解出来
t
b
1
b
2
t b_1 b_2
tb1?b2?（三个方程，三个未知数，也可以使用克莱默法则）。
如果解出来的
b
1
、
b
2
、
1
?
b
1
?
b
2
b_1、b_2、1-b_1-b_2
b1?、b2?、1?b1??b2?都大于0且t大于0，则说明解是有意义的。
4 包围盒（Bounding Volumes）
原始的做法是让每个像素的光线要和所有三角形面求交点，计算量太大，那么如何让这个过程加速呢？如果我们圈定包围盒，连与包围盒都不相交的三角形就不用接着算了，那么就可以很大的减少计算量。
4.1 概览
基本思想 使用一个简单的几何体来包围一个复杂的物体，如果光线不饿能碰到包围盒，那么就不用再计算其与里面物体的交点。
4.2 求光线与长方体的交点
3D物体通常的包围盒是长方体。
一个重要理解：长方体是三对不同的面形成的交集。
我们使用的包围盒通常是轴对齐（AABB）包围盒。Axis-Aligned Bounding Box(AABB)
经过以上分析，现在问题就i变成了求光线和轴对齐包围盒的交点
4.3 求光线和轴对齐包围盒的交点
4.3.1 2维的情况
首先从简单的问题开始分析，先计算二维的长方形。由于前面提到的光线方程是参数方程，所以只要我们计算光线什么时候会和一对平行的边有交点（计算 t m i n t m a x t_{min} t_{max} tmin?tmax?），就可以求出光线进入和离开这个边的时间。
因为一个长方形有两对边，所以会得到两对解，然后求这两对解的交集，此时 t m i n t m a x t_{min} t_{max} tmin?tmax?就分别代表着光线进入和离开长方体的时间。
简单理解就是进入了所有的边才叫进入，出去了一个边就离开了，下面三维的情况也是同样如此。
4.3.2 3维的情况
1> 根据2维的结果，我们观察发现
- 只有当光线进入了所有的对面，才能说光线进入了盒子。
- 只要光线离开任意一个对面，光线就离开了盒子。
2> 计算 t e n t e r t_{enter} tenter?(光线进入物体时的t)与 t e x i t t_{exit} texit?(光线离开物体时的t)：
- 对于每一对面，计算 t m i n t m a x t_{min} t_{max} tmin?tmax?。
- 对于3D盒子，得到光线进入盒子和离开盒子的时间， t e n t e r = m a x { t m i n } , t e x i t = m i n { t m a x } t_{enter}=max\{t_{min}\},t_{exit}=min\{t_{max}\} tenter?=max{tmin?},texit?=min{tmax?}（t为负也有意义，下面说明）。
- 如果 t e n t e r < t e x i t t_{enter}<t_{exit} tenter?<texit?,就说明光线与盒子有交点。
3> t为负时的意义
- 如果 t e x i t < 0 t_{exit}<0 texit?<0，说明盒子在光线背后，说明没有交点。
- 如果 t e x i t > = 0 t_{exit}>=0 texit?>=0并且 t e n t e r < 0 t_{enter}<0 tenter?<0，说明光线的起点在盒子里，一定有交点。
4> 结论
如果满足
t
e
n
t
e
r
<
t
e
x
i
t
&
&
t
e
x
i
t
>
=
0
t_{enter}<t_{exit} \&\&t_{exit}>=0
tenter?<texit?&&texit?>=0，则说明光线与AABB包围盒有交点。
4.4 使用轴对齐(AABB)概念的原因
主要目的是简化计算。
普通情况计算t：
轴对齐的情况下计算t（只需要考虑各方向的分量即可）：
