现代计算机图形学入门-闫令琪，课程笔记。

Lecture 2 线性代数基础知识复习 (Review of Linear Algebra)



为什么要学线性代数？因为计算机图形学依赖很多基础知识，包括数学上的线性代数、微积分、统计；物理上的光学、力学等等。这些知识点都会穿插在这门课中进行讲解。

今天的课程，主要是讲线性代数中的向量、矩阵，包括向量的表示、点乘、叉乘，矩阵的变幻等等，属于是应用在计算机图形学中比较多且基础的一些知识点。

## 向量 Vectors

向量：同时具有**大小**和**方向**的几何对象。

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/vectors.png" style="max-height: 300px">

- 如何表示：$\vec{a}$ 或者 $\boldsymbol{a}$
- 另一种表示方法： $\vec{AB}=B-A$
- 不需要关心向量的起点和位置，只关心大小和方向。比如 $\vec{a}$ 平移之后得到 $\vec{a'}$ ，两个向量位置不同，但大小和方向相同，所以是同一个向量。

向量长度/单位向量

- 向量大小（长度）这样表示： $||\vec{a}||$
- 单位向量 (Unit vector)
  - 长度为 1 的向量
  - 表示方法：$\hat{a}$
  - 如何计算：向量除以自身的长度 $\hat{a}=\vec{a}/||\vec{a}||$
  - 常用来表示方向

### 向量求和 Vector Addition

几何学的方法，两个法则：

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/vector-addition.png" style="max-height: 240px">

- 平行四边形法则：两个向量放在同一起点，平移两个使其首尾相连形成平行四边形，连接四边形的对角即是向量的和。
- 三角形法则：向量首尾相接，向量的最开始点和结束点相连。

代数的方法：使用笛卡尔坐标系。

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/cartesian-coordinates.png" style="max-height: 240px">

如图，使用 X、Y 可以表示任意的向量。而且这种方式计算比较方便计算向量的长度：

$$ ||A||=\sqrt{x^2+y^2} $$

### 向量求积 Vector Multiplication

向量由于有方向，所以与数字的求积不太一样。

**点乘 Dot product**

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/vector-dot-product.png" style="max-height: 240px">

- 定义：两个向量的长度相乘，再乘以他们之间夹角的余弦。$\vec{a}·\vec{b} = ||\vec{a}||||\vec{b}||cos\theta$
- 上面公式可以推导出：$cos\theta=\frac{\vec{a}·\vec{b}}{||\vec{a}||||\vec{b}||}$
- 如果 a、b 是单位向量的话，那么分母是 1，即：$cos\theta=\hat{a}·\hat{b}$
- 交换律：$\vec{a}·\vec{b} = \vec{b}·\vec{a}$
- 分配律：$\vec{a}·(\vec{b}+\vec{c}) = \vec{a}·\vec{b}+\vec{a}·\vec{c}$
- 结合律：$(k\vec{a})·\vec{b} = \vec{a}·(k\vec{b}) = k(\vec{a}·\vec{b})$

直角坐标系下向量的点乘计算方式：

- 2D: $\vec{a}·\vec{b} = \begin{pmatrix} x_a \\ y_a \end{pmatrix} · \begin{pmatrix} x_b \\ y_b \\ \end{pmatrix} = x_ax_b + y_ay_b$

- 3D: $\vec{a}·\vec{b} = \begin{pmatrix} x_a \\ y_a \\ z_a \\ \end{pmatrix} · \begin{pmatrix} x_b \\ y_b \\ z_b \\ \end{pmatrix} = x_ax_b + y_ay_b + z_az_b$

向量点乘在计算机图形学中的应用：

- 找到两个向量/方向之间的夹角
- 找到夹角基于可以计算向量的投影
- 有投影就可以对向量进行分解（点乘的逆运算）
- 如下图：比较 $\vec{a}·\vec{b}$ 和  $\vec{a}·\vec{c}$ 可以判断哪个向量离 b 更近。判断点乘的结果是大于/小于 0，可以判断方向是向上/向下。

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/vector-dot-product-2.png" style="max-height: 300px">

**叉乘 Cross product**

<p style="display: flex">
  <img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/cross-product.png">
  <img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/Right_hand_rule_cross_product.jpg">
</p>

- 如图所示，叉乘与点乘完全不同
- 叉乘的结果 c 与 ab 都垂直（即垂直于 ab 所在的平面）
- 可以使用右手螺旋定则来确定 c 的方向
  - a x b, 四指沿着 a 方向，弯曲到 b 方向，大拇指的指向即是 c 的方向
  - b x a 则相反（不满足交换律）
- 叉乘常用于建立三维空间的直角坐标系

直角坐标系下向量的叉乘计算方式：

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/cross-product-formula.png" style="max-height: 140px">

向量叉乘在计算机图形学中的应用：

<p style="display: flex">
  
  <img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/cross-product-4.png" style="max-height: 200px">
  <img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/cross-product-5.png" style="max-height: 200px">
</p>

- 判断向量 b 在 a 的哪一侧（左/右）
  - 如左图，使用 a x b，叉乘结果是**正数**说明在左侧
- 判断一个点与三角形的位置关系（内/外）
  - 如右图，先判断 p 点与三个向量 abc 的关系，如果 p 均在三个向量的左侧，那就是在三角形内部，反之则是外部。

## 矩阵 Matrices

数学上，一个 (M x N) 的矩阵是一个由 M 行 N 列元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。

### 矩阵的乘积

- 相乘的条件
	- 第一个矩阵的列数等于第二个矩阵的行数，(M x N) (N x P) = (M x P)。
- 如何计算
	- 比如下图的结果 26，位于矩阵的2行4列，去第一个矩阵找对应的行，第二个矩阵找对应列，然后作为向量进行点乘。5x4+2x3=26.

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/5f575c749d320945d4a1fb223f7b5850.png" style="max-height: 200px">

### 矩阵的性质

- **没有**交换律：AB ≠ BA
- 结合律：(AB)C = A(BC)
- 分配律：A(B+C) = AB + AC，(A+B)C = AC + BC

### 矩阵的转置

行列互换，行变成列，列变成行。

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/1cdf84874069ad154d3b65d3fa1d3614.png" style="max-height: 200px">

如果两个矩阵相乘之后做转置，等于把两个矩阵调换位置之后分别做转置。

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/c588db538bb4600a39dd2a6ec361c972.png" style="max-height: 70px">

### 以矩阵表示向量乘积

- 点乘

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/e790405b909c28d78c6fcae2a51b698c.png" style="max-height: 160px">

- 叉乘

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/63f9919645c986e7966768f11baf7c46.png" style="max-height: 120px">

GAMES101-Lecture 2 线性代数

现代计算机图形学入门-闫令琪，课程笔记。

第一讲：计算机图形学概述 (Overview of Computer Graphics)



## What is Computer Graphics?

计算机科学的一个分支领域，主要关注**数字合成**与**操作视觉的图形内容**。虽然这个词通常被认为是指三维图形，事实上同时包括了二维图形以及影像处理。

## Why study Computer Graphics?

### Applications

计算机图形学在生活中实际应用很多，以下都属于图形学的范畴：

- Video Games：只狼、无主之地
- Movies：黑客帝国（特效）、阿凡达（面部表情特效）
- Animations：疯狂动物城、冰雪女王
- Design：建模设计、家装设计
- Visualization（可视化）：人体、地理、医学、科研
- VR/AR
- 数字作图
- Simulation：气象、光、黑洞
- Graphical User Interfaces：图形用户界面
- Typography：字体设计

### Fundamental Intellectual Challenges

计算机图形学学习起来相对困难，主要在以下几个方面：

- 虚拟世界的创建与交互
- 需要对现实世界的一些物理知识有所了解
- 计算机方面的一些计算方法、显示技术

### Technical Challenges

书接上文，简单说了一下可能会遇到哪些难点，这些后面都会详细讲，这里不展开。

注意最后一项：**本课程的重点是讲解计算机图形学涉及的原理**，所以并不会讲解一些实际编程的方法。

- Math of (perspective) projections, curves, surfaces
- Physics of lighting and shading
- Representing / operating shapes in 3D
- Animation / simulation
- ~~3D graphics software programming and hardware~~

### Computer Graphics is AWESOME!

当然，也可以仅仅是觉得计算机图形学很酷炫所以要学他！

好之者不如乐之者~

## Course Topics

课程概要，本课所讲内容大概分为四个方面：

### Rasterization（光栅化）

这一块主要讲的就是如何将 3D 的图形、几何体正确的投影到屏幕上，且能实时（每秒至少渲染 30 帧）显示。

- Project geometry primitives (3D triangles / polygons) onto the screen
- Break projected primitives into fragments (pixels)
- Gold standard in Video Games (Real-time Applications)

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/Rasterization.png" style="max-height: 300px">

### Curves and Meshes（曲线和曲面）

如何表达光滑的曲线/曲面，如何通过细分的方法实现曲线/曲面，如何在物体运动的时候保持拓扑结构等等 ...

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/Curves.png" style="max-height: 300px">

### Ray Tracing（光线追踪）

- Shoot rays from the camera though each pixel
  - Calculate intersection and shading
  - Continue to bounce the rays till they hit light sources
- Gold standard in Animations / Movies (Offline Applications)

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/Ray-Tracing.png" style="max-height: 300px">

### Animation / Simulation（动画/模拟）

- Key frame Animation

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/si_motion_keyframes.gif" style="max-height: 300px">

- Mass-spring System

主要是对真实世界中事物状态的模拟。

<img src="https://picgo-1254029119.cos.ap-beijing.myqcloud.com/blog/images/GAMES101/Simulation.png" style="max-height: 300px">

## References

本课程没有教材，但是强烈推荐阅读一本书：《Fundamentals of Computer Graphics》—— Steve Marschner and Peter Shirley.

因为封面是一只老虎，所以又称“虎书”，推荐第三版或第四版。

END

GAMES101-Lecture 1 概述

[harp.gl](https://www.harp.gl/) 是 HERE 公司开发的一个开源的 Web 端的三维地图渲染引擎，基于 three.js，使用 typescript 编写。



## 关键概念

- **MapView**：地图本身
	- 有多个图层组成，图层和图层中的对象由不同的矢量元素组成，且可以设置不同的样式。
	- 可以在上面添加新图层或自定义样式。
- **Data source**：用来渲染地图的数据源，一般有两种方式
	- Static data source：静态数据源，通常是 geojson 格式（全量加载）
	- Tiled data source：瓦片数据，按地图上的不同位置和缩放级别进行划分的一块一块的数据，地图上仅会显示当前视图内的数据（部分加载）
	- harp.gl 本身提供了几种开箱即用的 Tiled data source，见下文。
- **Technique**：图层中可存在的矢量元素类型，比如点、线、面、文字等等。图层中的对象都是由 technique 来表示的，比如道路就是有一定宽度的线。
- **Style sheets and syntax**：样式表和语法
	- 使用 [Style Expressions](https://github.com/heremaps/harp.gl/blob/master/@here/harp-datasource-protocol/StyleExpressions.md) （样式表达式）来筛选要添加样式的 technique，然后赋值宽度、颜色等样式属性。
	- renderOrder 字段表示图层呈现顺序的 z-index 值
- **Projections**：投影方式
	- 从技术上讲，球形的地图无法完美的投影到一个矩形上。harp.gl 提供了两种常见的投影方式。
	- mercator：墨卡托投影，将地图投影到一个矩形上。会变形，适合小范围。
	- globe：球投影。顾名思义，就是地球仪。不会变形，适合大范围。

## 官方文档-命名空间

以下为 [官方文档](https://www.harp.gl/docs/master/doc/globals.html) 中包含的各个命名空间的简单介绍，每个命名空间也是单独的 npm 包，一共 27 个。

### datasource 相关

- **harp-datasource-protocol**
	- 包含一些组件，用于解码数据源、自定义图层样式，使用了 web-worker 并行解码数据源
	- 定义了可以在地图画布上绘制的几种矢量元素类型 (technique)，点、线、面、文字、填充等等。图层中的对象都是由 technique 来表现的，比如道路就是有宽度的线。
	- 定义了一套规则（[Style Expressions](https://github.com/heremaps/harp.gl/blob/master/@here/harp-datasource-protocol/StyleExpressions.md)）来筛选 technique 然后添加样式
- **harp-debug-datasource**
	- 用来调试 datasource
- **harp-features-datasource**
	- 用来实现用户自定义功能
- **harp-geojson-datasource**
	- 提供一个支持 GeoJSON 的数据源
- **harp-omv-datasource**
	- HERE 提供的 OMV 数据源，JSON 格式。该数据源遵循 [vector tile 标准](https://github.com/mapbox/vector-tile-spec/)，每个 tile 以 [protobuf](https://github.com/protocolbuffers/protobuf) 方式编码。
- **harp-vectortile-datasource**
	- HERE 提供的 OMV 数据源，JSON 格式。该数据源遵循 [vector tile 标准](https://github.com/mapbox/vector-tile-spec/)，每个 tile 以 [protobuf](https://github.com/protocolbuffers/protobuf) 方式编码。
	- 使用的话需要提供秘钥
- **harp-webtile-datasource**
	- 提供了调用 [HERE Map Tile API 2.1](https://developer.here.com/documentation/map-tile/dev_guide/topics/quick-start-map-tile.html) 的功能。
	- 使用的话需要提供秘钥

### map 相关

- **harp-mapview**
	- 提供了创建地图时所需要的大部分功能
	- 包括但不限于：处理数据源、雾渲染、选择元素、天空、加载主题等
- **harp-map-controls**
	- 提供地图控制、交互和相机动画相关的功能
- **harp-map-theme**
	- 主题文件，json 格式，全部放在 resources 目录下
- **harp-mapview-decoder**
	- 使用 web worker 解码 harp-mapview 中使用的 datasource、theme
- **harp-materials**
	- 提供了 harp.gl 中所能使用的材质 (material)，基于 three.js 中的材质，用来改变图层中对象的外貌。

### 工具集

- **harp-atlas-tools**
  - 图标相关的工具集，包含两个命令行工具
  - harp-atlas-generator：精灵图生成（多个小图片集合到一个图片上）。
  - harp-sprites-generator：将每个精灵图单独的拷贝到指定的目录。
  - 除此之外还可以自行创建图标集。
- **harp-fetch**
	- 兼容 fetch API 的一个包，可在 Node.js 中使用
- **harp-geometry**
	- harp 创建 geometry 时所需要使用的算法和数据结构
- **harp-geoutils**
	- 提供了处理地空间数据 (geospatial data) 的一些工具类。关于 geospatial data 可参考 IBM 的 [这篇文章](https://www.ibm.com/topics/geospatial-data)。
	- WGS 84 坐标处理、tile 方式、投影方式、处理弧度和度数的一些数学函数
- **harp-lines**
	- 提供了为宽线 (wide line) 创建 three.js 几何体所需的功能
- **harp-lrucache**
	- 缓存相关
- **harp-olp-utils**
	- 工具集，用来处理 [HERE Open Location Platform](https://platform.here.com/) 提供的数据。
- **harp-test-utils**
	- 测试工具集
- **harp-text-canvas**
	- 一个第三方库，用于在 three.js 中渲染 [SDF](https://en.wikipedia.org/wiki/Signed_distance_function) 文字。
- **harp-theme-tools**
	- 主题编辑、调试工具，命令行工具。
- **harp-transfer-manager**
	- 下载管理器
- **harp-utils**
	- 工具类集合。包括但不限于：logging、caching、URL resolving、Simple Math

### 其他

- **@docs/fallback**
	- 文档相关
- **@docs/label-rendering**
	- 文档相关
- **harp-examples**
	- 官方示例：[网址](http://harp.gl.s3-website-us-east-1.amazonaws.com/docs/master/examples/#getting-started_hello-world_js-bundle.html)

harp.gl 入门

置身事内

学习程序设计语言主要是为了学习程序设计语言提供的编程模型。



## 编程语言发展史

- 最开始人们使用汇编语言进行编程，汇编语言可以编译为机器语言，机器语言也可以反编译为汇编语言。很繁琐，效率也很低。
- 随着计算机技术的不断发展，人们开始寻求与机器无关且面向用户的高级语言。无论何种机型的计算机，只要配备上相应高级语言的编译器，则用该高级语言编写的程序就可以运行。比如 Fortran、C 语言。
- 高级语言出现之后，人们开发的程序规模逐渐膨胀，如何组织程序成了新的挑战。这之后又出现了 C++、Java 等高级语言。
- 程序设计语言的发展就是一个“逐步远离计算机硬件，向着待解决的领域问题靠近”的过程。所以，编程语言后续的发展方向就是探索怎么更好的解决领域问题。

## 模型

**我们学习程序设计语言主要是为了学习程序设计语言提供的编程模型**。

比如：不同的程序组织方式，不同的控制结构等等。因为不同的编程模型会带给你不同的思考方式。

一切语言都是语法糖：

- C 语言提供了对汇编指令直接的封装。
- C++ 先是提供了面向对象，后来又提供了泛型编程。
- Java 把内存管理从开发者面前去掉了，后来引入的 Annotation 可以进行声明式编程。
- Ruby 提供了动态类型，以及由 Ruby on Rails 引导出的 DSL 风格。
- Scala 和 Clojure 提供了函数式编程。
- Rust 提供了新的内存管理方式，而 Libra 提供的 Move 语言则把它进一步抽象成了资源的概念。

学习新的程序设计语言是为了学习新的编程模型，反过来也可以说，不提供新编程模型的语言是不值得刻意学习的。如果你已经学会了一两门程序设计语言，学习一门新的语言其实并不困难，因为每种语言提供的新模型是有限的，基本的元素是类似的，无非是用了不同的关键字。

所以，学习新语言，只是在做增量的学习，思维负担并没有那么沉重。一旦对于程序设计语言的模型有了新的认识，你就能理解一件事：一切语法都是语法糖。

## 接口

- 包含**语法**和**程序库**两部分。
- 程序库就是为了消除重复而出现的，而消除重复，也是软件设计的初衷。
- 常用的程序库会随语言一起发布，成为标准库，除此之外大量的第三方库，进而发展出包管理器。（更大范围上消除重复）
- 学习一种程序设计语言提供的模型时，不仅仅要看语法本身有什么，还要了解有语言特性的一些程序库。
- 语法和程序库是在解决同一个问题，二者之间是相互促进的关系。一些经过大量实践验证过的程序库会变成语言的语法；如果语法不够好，新的程序库就会出现，新一轮的编程模型就开始孵化。

## 实现

做设计真正的地基，并不是程序设计语言，而是运行时，有了对于运行时的理解，我们甚至可以做出语言本身不支持的设计。

理解运行时，可以将“程序如何运行”作为主线，将相关的知识贯穿起来。我们从了解可执行文件的结构开始，然后了解程序加载机制，知道加载器的运作和内存布局。然后，程序开始运行，我们要知道程序的运行机制，了解字节码，形成一个整体认识。最后，还可以根据需要展开各种细节，做深入的了解。