加载中...

images

大名鼎鼎的《虎书》,顺便也是读点东西磨一磨自己惨淡的英语水平。

§ 1 - § 8

§ 1 Introduction

计算机图形学是研究使用计算机来创建(create)和操作(manipulate)图像的学科。

计算机图形学可以大致分为如下领域:Modeling,Rendering,Animation。

图形学所用到的 API 大抵可以分为两类,一类是依托 Java 语言的特性,封装成 Package;另一类是像 Direct3D 和 OpenGL 一样提供相关库,供如 C++ 语言实现的相关程序调用。

图形管线是将 3D 空间中的图元高效地透视到二维平面上的系统。这里可能会用到深度缓冲的算法。并且,图形管线中对于模型的所有操作均可以在引入齐次坐标的意义下,用四维坐标系统来表示。

IEEE 浮点数标准中引入了 $+ \infin, -\infin, \text{NaN}$ 三种特殊记号。三者在计算中的结果均与其取极限意义下的结果相同。此外,如果 $\text{NaN}$ 参与了浮点数大小比较,结果总返回 false

此外,在设计图形学相关程序时,我们还应该注重程序运行的效率和精度的平衡。以 floatdouble 二者的使用为例,对于几何计算相关的数据,我们建议采用 double 类型;对于颜色的计算,我们建议采用 float 类型;而对于需要占用一定内存的数据,比如三角形面,建议数据存储类型为 float,而在参与计算时通过成员函数转换为 double 类型。

而对于图形学相关程序的 Debug,传统技巧可能不再十分适用。这里可能需要一些特殊的技巧。

  • 类科学的方法:之所以称呼其为“类科学”,是因为其过程和科学研究的过程类似。首先我们需要仔细观察我们的问题,然后针对我们发现的问题提出一定的假说,然后再验证其是否正确。
  • 使用 Debug 数据生成图像的方法:比如我们直接生成表面单位法向量 $255 (x,y,z)$ 所代表的图像,来查看模型导入的法向量是否存在问题。
  • 在程序中添加额外的代码来达到断点调试的效果。注意,这里最好采用单线程,随机种子固定的方式。
  • 如果程序遇到了类似于 segmentation fault 的问题,我们可以在程序中加入一些 assert 语句来方便我们进行问题的定位。
  • 将 Debug 相关数据绘制成图或表以将其可视化。

§ 2 Miscellaneous Math

  • 集合与映射(Mapping, 输入为同一类型的参数, 输出一个对象)
    • 逆映射
    • 区间及其运算
    • 对数与换底公式,对数的求导
  • 二次方程的求解
  • 三角学
    • 角的定义(两条边与单位圆交的弧长),弧度制与角度值的转换
    • 三角函数及相关公式
    • 极坐标
  • 向量及其运算,获取某个分量直接与该方向的单位向量进行点积
    • 从一个向量 $a$ 获取一组单位正交基:$w = \dfrac a {||a||}$,选择不平行与 $w$ 的 $t$ 使得 $u = \dfrac {t \times w} { || t \times w ||}$,然后令 $v = w \times u$,那么 $w,u,v$​ 便是一组单位正交基。这里选择 $t$ 需要有一些要求,因为 $t \times w$ 的值为二者围成的平行四边形的面积,所以如果该值不够大的话,会产生精度问题。于是,我们提供下列选取 $t$ 的方法。首先令 $t \leftarrow w$,然后选择 $t$ 绝对值最小的分量,将其变成 1。在做表面着色时我们时常需要用到这种构造方法,我们需要一个与表面法向量平行的坐标轴,而对于另外两个坐标轴的方位无任何要求。
    • 从两个向量 $a, b$ 获得一组单位正交基:$w = \dfrac a { ||a ||}, u = \dfrac{b \times w}{ || b \times w||}, v = w \times u$​。这种构造方法常常用于换基到某个摄像机的位置,摄像机看向的方位是固定的,而摄像机旋转的角度也是给定的。这时,$w$ 为摄像机看向的方向,$v$ 为摄像机的正上方。
    • 有时由于舍入误差或是存储精度误差,某个基为程序的运行带来了错误。我们当然可以用现有的 $w$ 和 $v$ 再构造一组新基,但是这却不是最佳的选择。我们可以用 SVD 分解的方法来求出一组和原有正交基相距最近的基。
  • 曲线和曲面
    • 使用隐函数方法来定义,$f(x,y) = 0$
    • 2D 梯度,梯度向量即法向量指向 $f(x,y) > 0$​ 方向
    • 参数形式的曲线与曲面
  • 线性插值
  • 三角形与重心坐标

§ 3 Raster Images

  • Intro

基于扫描的光栅设备在生活中应用广泛。与之相联系地,点阵图(Raster Images)是存储和处理图像最常用的方式。我们可以将点阵图考虑为是,不随设备而变化的二维数组,其中存储了这张图片中的颜色信息。此外,还有一种图叫做向量图,概括来说其存储的是如何显示这种图的“指令”,并不包含每个像素的具体内容,其在显示之前也要先经过点阵化。

  • 光栅设备:输出设备有显示器与打印机,输入设备为传感器
  • Raster Images 与其显示

我们可以将 Raster Images 视为是 $I(x,y) : R \rightarrow V$,其中 $R \subset \mathbb {R}^2$​,对于灰度图 $V=\mathbb R^+$,而对于 RGB 图像 $V=\mathbb{R^+}^3$​. 一般的,采用课上定义屏幕平面的方式,我们有 $R = [-0.5, n_x-0.5] \times [-0.5, n_y-0.5]$.

像素值存储为浮点数的图片我们一般称为 HDR 图片,这是相比使用 int 存储像素值的 LDR 图片来说的。

使用后者这种存储方式会导致两种现象:一种是大于最大可记录值的像素值被强制设为最大可记录值(clipping);一种是原始像素值都需要向可以被表示的最近的可记录值舍入(banding, quantization artifects)

由于人类对光强的感知并不是线性变化的,显示器对于输入值也不是线性变化的,因此我们需要进行一定程度的校正。对于后者是说,显示器的 $\text{displayed intensity} = \text{maximum intensity} \cdot \text{(input)}^\gamma$,于是我们便可以校正我们的输入值,这里 $\gamma$ 由显示器的材料特性决定。

  • RGB 色系与加色系统,24-bit 颜色表示
  • Alpha 合成:设前景颜色为 $c_f$,背景颜色为 $c_b$,Alpha 通道值为 $\alpha$(不透明度),则输出结果为 $c = \alpha c_f + (1-\alpha) c_b$​,32-bit 颜色表示
  • 图片的存储格式:可以分为 Lossless 和 Lossy 两种系统,前者保留了几乎所有的信息,而后者不可避免地丢失了一定程度的信息
    • jpeg(Lossy),根据人类视觉信息压缩图片
    • tiff
    • ppm(Lossless,简洁)
    • png(Lossless)

§ 4 Ray Tracing

图形学的基本任务之一便是渲染,输入一系列 3D 空间中的模型,输出其在某个视角下的 2D 投影。

渲染有两种方式:

  • Object-order rendering:遍历场景中所有的模型,考虑其对目前已计算的图像的影响并更新
  • Image-order rendering:考虑图像中的每一个像素,针对某个像素找到所有可能影响该像素的模型,然后对该像素的值进行计算

Basic RT

由光路可逆性,由摄像机发出 Viewing Ray,一旦这个 Viewing Ray 与某个物体相交,就在这个相交点计算其着色。

基本的 RT 算法包含以下部分:

  • 生成光线:考虑视角原点和像平面每个像素连线的方向,生成光线
  • 光线与场景求交:找到与光线相交的最近的物体
  • 着色:计算交点的颜色

投影

// 区分:平行投影与透视投影,正交投影与斜投影,正交透视投影与斜透视投影

最简单的投影方法是平行投影:我们只需要将物体沿着投影方向移动,直到与平面得到交点就可以。平行投影使得原来平行的线在投影后仍然平行。

如果投影方向恰好与像平面垂直,这就变成了正交投影(第一张图);不然我们称之为斜投影(第二张图右图)。

Figure showing when projection lines are parallel and perpendicular to the image plane, the resulting views are called orthographic.

Figure showing a parallel projection that has the image plane at an angle to the projection direction is called oblique (right). In perspective projection, the projection lines all pass through the viewpoint, rather than being parallel (left). The illustrated perspective view is non-oblique because a projection line drawn through the center of the image would be perpendicular to the image plane.

但是我们发现我们所观察到的世界并不能完全用平行投影来解释,比如平行的铁轨越远看起来离得越近。

而透视投影却能解决这个问题。透视投影是说我们要将模型投影到 Viewpoint 和模型对应点的连线与像平面的交点上(第二幅图左图)。仿照上述平行投影的概念,我们可以引入正交透视投影和斜透视投影两个概念,区别在与 ViewPoint 和像平面中心点的连线与像平面是否垂直。

计算 Viewing Ray

  • 定义光线:3D 含参射线
  • 换基:$e$ 为相机所在处,$u$, $v$ 分别指向相机看向方向的右方与上方

Figure showing the sample points on the screen are mapped to a similar array on the 3D window. A viewing ray is sent to each of these locations.

  • 计算(略去课上结果 $M_{perspective \rightarrow ortho}$, $M_{ortho}$)

光线与物体求交

  • 与球求交
  • 与三角形求交
  • 与多个物体求交:To intersect a ray with a group, you simply intersect the ray with the objects in the group and return the intersection with the smallest t value.
for each pixel do
	Compute viewing ray
	if ( ray hits an object with t \in [0, inf) ) then
		Compute n
		Evaluate shading model and set pixel to the shading color
	else
		Set pixel color to background color

Shading

着色模型:计算某个像素处的颜色值;基本的着色模型:

  • Lambertian Shading Model
  • Blinn Phong Shading Model

Shadows

假设我们在着色表面的 $p$ 处看向光源 $l$​,这束“光线”称为 Shadow Ray,如果这条试探光线在中间被物体遮挡,那么这里就应该有阴影。

function raycolor(ray e+td, real t0, real t1)
	hit_record rec, srec
	if ( scene->hit(e+td, t0, t1, rec) ) then
		p = e + (rec.t) d
		color c = rec.ka * Ia // Ambition
		if ( not scene->hit(p+sl, epsilon, inf, srec) ) then
			c += Specular_term + Diffuse_term
			return c
		
	else
		return background_color

Ideal Specular Reflection

这种镜面效果的材质只需要:

r = d - 2 * dotProduct(d, n) * n
color c = c + km * raycolor(p + sr, epsilon, inf)

Figure showing when looking into a perfect mirror, the viewer looking in direction d will see whatever the viewer “below” the surface would see in direction r.

Figure showing a simple scene rendered with diffuse and Blinn-Phong shading, shadows from three light sources, and specular reflection from the floor.

BP Shading Model with Shadows + Specular Reflection

§ 5 Linear Algebra

  • 行列式,顺序主子式
  • 矩阵
  • 矩阵求逆
  • 特征值与矩阵对角化
  • 奇异值分解

§ 6 Transformation Matrices

  • 2D Linear Transformations
    • Scaling
    • Shearing
    • Rotation
    • Reflection
    • Composition and decomposition
  • 3D Linear Transformations
    • Arbitrary 3D Rotations
    • Transforming Normal Vectors: If a surface is transformed by matrix $M$, then $Mt$ remains to be the tangent vector of the transformed surface if its tangent vector is denoted with $t$. However, $Mn$ may not be the normal vector of the new surface if $n$ is the normal vector of the former surface.
      • $(n’)^TMt = 0 \ \and \ n^Tt = 0 \ \Rightarrow (n’)^TMt = 0 \ \and \ n^TM^{-1}Mt=0$,于是我们取 $n’ = (M^{-1})^Tn$.
      • 即 $M’ = (M^{-1})^T$.
  • Translation and Affine Transformations
    • 平移与仿射变换
  • 引入齐次坐标表示仿射变换

§ 7 Viewing

What is Viewing? Use linear algebra tools to move objects their 3D locations and their positions in the 2D view. This 3D to 2D mapping is called viewing transformation.

  • Viewing Transformations: The viewing transformation has the job of mapping 3D locations, represented as (x, y, z) coordinates in the canonical coordinate system, to coordinates in the image, expressed in units of pixels. It could break into a sequence of these transformations:
    • Camera transformation / Eye transformation: Places the camera on the right position and orientation. Depending on the camera only. World space (Canonical coordinates) -> Camera space.
    • Projection transformation: Projects visible points from camera space to $[-1, 1]^3$​​​. Depending on the projection type. Camera space -> canonical view volume.
    • Viewport transformation / Windowing transformation: Map $[-1, 1]^3$​​ to pixel coordinates. Depending on the output image. Canonical view volume -> screen space.

Figure showing the sequence of spaces and transformations that gets objects from their original coordinates into screen space.

这里略去各个矩阵的推导过程,结论详见 GAMES101 笔记。

§ 8 The Graphics Pipeline

Now consider using object-order rendering.

The process of finding all the pixels in an image that are occupied by a geometric primitive is called rasterization, so object-order rendering can also be called rendering by rasterization.

The sequence of operations that is required, starting with objects and ending by updating pixels in the image, is known as the graphics pipeline.

Any graphics system has one or more types of “primitive object” that it can handle directly, and more complex objects are converted into these “primitives.” Triangles are the most often used primitive.

Figure showing the stages of a graphics pipeline.

For the purposes of this chapter, we’ll discuss the graphics pipeline in terms of four stages.

  • Vertex processing stage
  • Rasterization stage
  • Fragment processing stage
  • Fragment blending stage

Rasterization

  • Rasterizer
    • For each primitive coming in, the rasterizer enumerates the pixels it covers, and then interpolates its attribute values.
    • Its output is a set of fragments, one for each pixel covered by the primitive.
  • Triangle
    • 重心坐标插值计算属性值