【计算机网络】传输层安全协议 现在广泛使用的有两个协议： 安全套接字层 SSL (Secure Socket Layer) 运输层安全 TLS (Transport Layer Security) SSL作用在端系统应用层的HTTP和运输层之间，在TCP之上建立起一个安全通道，为通过TCP传输的应用层数据提供安全保障。 在SSL 3.0的基础上设计了TLS协议，为所有基于TCP的网络应用提供安全数据传输服务。 在未使用SSL时，应用层的应用程序的数据是通过TCP套接字与运输层进行交互的。 在使用SSL时： 因为SSL增强了TCP服务，因此SSL应该是运输层协议。然而实际上，需要使用安全运输的应用程序(如HTTP)却把SSL驻留在应用层。 在应用程序下面多了一个SSL子层，而在应用程序和SSL子层之间，还有一个SSL套接字，其作用和以前讲过的TCP套接字相似，是应用程序和SSL子层的应用编程接口API。 SSL提供的安全服务： SSL服务器鉴别：允许用户证实服务器的身份。支持SSL的客户端通过验证来自服务器的证书，来鉴别服务器的真实身份并获得服务器的公钥。 SSL客户鉴别：允许服务器正式客户身份 加密的SSL会话：对报文进行加密，并检测报文是否被篡改 简要过程如下： 协商加密算法 第①步：$A \to B$，发送SSL版本号和可选加密算法； 第②步：$B \to A$，选择算法并告知A。 服务器鉴别 第③步：$B \to A$，发送包含其RSA公钥的数字证书。 第④步：A使用认证机构CA公开发布的RSA公钥对证书进行验证。 会话密钥计算 第⑤步：$A \to B$，随机生成一个秘密数，用B的RSA公钥进行加密后发送给B。 第⑥步：双方根据算法产生共享的对称会话密钥。 安全数据传输 第⑦步：双方用会话密钥加密和解密它们之间传送的数据并验证其完整性。

【计算机网络】网络层安全协议 IPsec 协议族 VPN中传送的信息是加密的，提供这种加密服务的是IPsec IPsec(IP security)是能够在IP层提供互联网通信安全的协议族。 它允许通信双方选择合适的算法和参数，为保证互操作性，IPsec还包含了一套加密算法，所有IPsec的实现都必须使用。 IPsec协议族中的协议可划分为： IP安全数据包格式的两个协议 鉴别首部AH协议：提供源点鉴别和数据完整性，但不能保密 封装安全有效载荷ESP协议：提供源点鉴别、数据完整性和保密 有关加密算法的三个协议 互联网密钥交换IKE协议 （AH协议的功能都已包含在ESP协议中） 所谓“安全数据报”是指数据报的数据部分是经过加密的，并能够被鉴别的。 使用ESP或者AH协议的IP数据报称为IP安全数据报（或IPsec数据报），工作方式有两种： 运输方式(transport mode)。运输方式实在整个运输层报文前后分别添加若干控制信息，再加上IP首部，构成IP安全数据报。 隧道方式(tunnel mode)。隧道方式实在原始的IP数据报前后分别添加若干控制信息，再加上新的IP首部，构成IP安全数据报。 目前使用最多的就是隧道方式。 通常把数据报的数据部分称为数据报的有效载荷(payload)。 安全关联 安全关联SA(Security Association)：在发送IP安全数据报之前，在源实体和目的实体之间建立的一条网络层的逻辑链接 建立安全关联后，传统的无连接的网络层就变成了一个具有逻辑链接的一个层。 安全关联是源点到终点的单向连接。 建立安全关联SA的路由器或者主机，必须维护这条SA的状态信息： 一个32位的连接标识符，称为安全参数索引SPI(Decurity Parameter Index) 安全关联SA的源点和终点的IP地址 所使用的加密类型（例如，DES或者AES） 加密的密钥 完整性检查的类型（例如：使用MD5或者SHA-1的报文鉴别码MAC） 鉴别使用的密钥 IP安全数据包的格式 ESP尾部。用0填充，填充原因：数据加密时一般要求数据块长度是若干字节的整数倍。“下一个首部”字段的值表明在接收端，ESP的有效载荷应该交给什么样的协议来处理。 加密的部分。按照SA声明的加密算法和密钥，对ESP的有效载荷和ESP尾部进行加密。 ESP首部。ESP首部有两个32位字段： 第一个字段存放安全参数索引SPI，通过同一个SA的所有IP安全数据报都使用同样的SPI值。 第二个字段是序号，鉴别要用到这个序号，它用来防止重放攻击。 鉴别的部分。按照SA声明的算法和密钥，对ESP首部和加密的部分生成报文鉴别码MAC。 报文鉴别码MAC。所生成的报文鉴别码MAC添加在ESP尾部的后面，和ESP首部、ESP的有效载荷、ESP尾部一起，构成IP安全数据报的有效载荷。 新的IP首部。通常为20字节长，和普通的IP数据报的首部的格式是一样的。需要注意的是，首部中的协议字段的值是50，表明在接收端，首部后面的有效载荷应交给ESP协议来处理。 收到IP安全数据报后，先检查首部中的目的地址。发现目的地址正确，继续处理这个IP安全数据报： 找到IP首部的协议字段值（现在是50），把IP首部后面的所有字段（即IP安全数据报的有效载荷）都用ESP协议进行处理。先检查ESP首部中的安全参数索引SPI，以确定收到的数据报属于哪一个安全关联SA （因为可能有多个安全关联）。 接着计算报文鉴别码MAC，看是否和ESP尾部后面添加的报文鉴别码MAC相符。 再检验ESP首部中的序号，以证实有无被入侵者重放。 接着用这个安全关联SA对应的加密算法和密钥，对已加密的部分进行解密。 再根据ESP尾部中的填充长度，去除发送端填充的所有0，还原出加密前的ESP有效载荷，也就是发送的原始IP数据报。 IPsec的其他构件 安全关联数据库SAD(Security Association Database) 存放安全关联SA 安全策略数据库SPD(Security Policy Database) 指明什么样的数据报需要进行IPsec处理 互联网密钥交换IKE (Internet Key Exchange)协议 用于大型的、地理位置分散的系统 是为IP安全数据报创建安全关联SA IKEv2以另外三个协议为基础 Oakley— 是个密钥生成协议［RFC 2412］。 安全密钥交换机制SKEME (Secure Key Exchange Mechanism)是用于密钥交换的协议。它利用公钥加密来实现密钥交换协议中的实体鉴别。 互联网安全关联和密钥管理协议ISAKMP (Internet Secure Association and KeyManagement Protocol) — 用于实现IK E中定义的密钥交换，使IKE的交换能够以标准化、格式化的报文创建安全关联SA。

【编译原理】词法分析 1. 词法分析的简介 2. 词法分析器 3. 词法分析 ——手工构造法 比较符 标识符 关键字 4、词法分析——正则表达式 5、词法分析——有限状态自动机 确定状态有限自动机（DFA） 非确定的有限状态自动机（NFA） 转换过程 6、RE到NFA：Thompson算法 7、NFA到DFA：子集构造算法 算法思想 子集构造算法（工作表算法） ε-闭包的计算 8、DFA的最小化：Hopcroft算法 9、DFA的代码表示 转移表 跳转表 1. 词法分析的简介 编译器的阶段： graph LR A(源程序) --> B[front end] B --> C(IR) C --> D[back end] D --> E[target program] 前端 2. 词法分析器 词法分析器将字符流转化为记号流 字符流：和被编译的语言密切相关 (ASCII, Unicode, or …) 记号流：编译器内部定义的数据结构，编码所识别出的词法单元 例子： if (x > 5) y = "hello"; else z = 1; 词法分析后： IF LPAREN IDENT(x) GT INT(5) RPAREN IDENT(y) ASSIGN STRING(“hello”) SEMICOLON ELSE IDENT(z) ASSIGN INT(1) SEMICOLON EOF 记号的数据结构定义： enum kind{IF, LPAREN, ID, INTLIT, ...}; struct token{ enum kind k; // 关键词 char *lexeme; // 值 }; 词法分析器的实现方法 手工编码实现法 相对复杂、且容易出错 但是目前非常流行的实现方法：GCC, LLVM, … 词法分析器的生成器 可快速原型、代码量较少 但较难控制细节 3. 词法分析 ——手工构造法 比较符 状态转移图： token nextToken () c = getChar (); switch (c) case ‘<’: c = getChar (); switch (c) case ‘=’: return LE; case ‘>’: return NE; default: rollback(); return LT; case ‘=’: return EQ; case ‘>’: c = nextChar (); switch (c): // similar ... 标识符 状态转移图 token nextToken () c = getChar(); switch (c) // continued from above cases… case ‘a’, …, ‘z’, ‘A’, …, ‘Z’, ‘_’: c = getChar (); while (c==‘a’ || c==‘b’|| … || c==‘_’) c = getChar(); 标识符和关键字 很多语言中的标识符和关键字有交集 从词法分析的角度看，关键字是标识符的一 部分 以C语言为例： 标识符：以字母或下划线开头，后跟零个或 多个字母、下划线、或数字 关键字：if, while, else, … 关键字 两种方案 第一种：在状态转移图上扩展新的边 第二种：关键字表算法 对给定语言中所有的关键字，构造关键字构成的哈希表H 对所有的标识符和关键字，先统一按标识符的转移图进行识别 识别完成后，进一步查表H看是否是关键字 通过合理的构造哈希表H（完美哈希）， 可以 $O(1)$ 时间完成 4、词法分析——正则表达式 对于给定的字符集 $\sum=\left \{ c_{1}, c_{2}, …, c_{n} \right \}$，归纳定义： 空串 $\varepsilon$ 是正则表达式 对于任意的 $c \in \sum$，$c$ 是正则表达式 如果 $M$ 和 $N$ 是正则表达式，那么以下也是正则表达式 选择： $M|N=\left \{ M\cup N \right \}$ 连接：$MN = \left \{ mn | m\in M, n \in N \right \}$ 闭包：$M^*=\left \{ \varepsilon,M,MM,MMM,...\right \}$（Kleene闭包） 语法糖：可以引入更多的语法糖，来简化构造 语法糖 意义 $[c_{1}-c_{n}]$ $c_{1} $e+$ 一个或多个 $e$ $e?$ 零个或一个 $e$ $“a_{*}”$ $a*$ 自身, 不是 $a$ 的Kleen闭包 $e \left \{i, j\right \}$ $i$ 到 $j$ 个 $e$ 的连接 . 除‘\n’外的任意字符 5、词法分析——有限状态自动机 graph LR subgraph 有限状态自动机 A("输入的字符串") ==> B["FA"] B ==> C("{Yes, No}") end 自动机：$M = (\sum, S, q_{0}, F, \delta)$ $\sum$：字母表，不同的语言不一样 $S$：状态集，指的是有限自动机的状态 $q_{0}$：初始状态 $F$：终结状态集，注意为状态集 $\delta$：转移函数 确定状态有限自动机（DFA） 对任意的字符，最多有一个状态可以转移 串读完的时候为最终状态即为可接受 graph LR O( ) --> A A((0)) --a--> B((1)) B --a--> C[2] A --b--> A B --b--> B C --a,b--> C $\sum = \left \{a, b \right \}$ $S = \left \{0,1,2 \right \}$ $q_{0} = \left \{ 0 \right \}$ $F = \left \{ 2 \right \}$ $\delta =$ $ \left \{ (q0,a) \to q1, (q0, b) \to q0,\right \}$ $\left \{(q1,a) \to q2,(q1,b) \to q1, \right \}$ $\left \{ (q2,a) \to q2, (q2, b) \to q2\right \}$ 非确定的有限状态自动机（NFA） 对任意的字符，有多于一个状态可以转移 graph LR O( ) --> A A((0)) --a,b--> B[1] A --a--> A B --b--> B B --b--> A $\sum = \left \{a, b \right \}$ $S = \left \{0,1 \right \}$ $q_{0} = \left \{ 0 \right \}$ $F = \left \{ 1 \right \}$ $\delta =$ $ \left \{ (q0,a) \to \left \{ q0, q1 \right \} \right \}$ $\left \{(q1,a) \to q1 \right \}$ $\left \{ (q2,a) \to \left \{ q0,q1\right \} \right \}$ 转换过程 graph LR A(RE) --Thompson<br>算法--> B(NFA) B --子集构造算法--> C(DFA) C --Hopcroft<br>最小化算法--> D>词法分析器代码] 6、RE到NFA：Thompson算法 正则表达式到非确定有限状态自动机: Thompson算法 基于对RE的结构做归纳（数学归纳法） 对基本的RE直接构造（2种） 对复合的RE递归构造（3种） 递归算法，容易实现 在我们的实现里，不到100行的C代码 【例】$a(b|c)*$ graph LR Begin( ) --> A A(0) --a--> B((1)) B --ε--> C((2)) C --ε--> D((3)) D --ε--> E((4)) E --b--> G((5)) D --ε--> F((6)) F --c--> H((7)) G --ε--> Y((8)) H --ε--> Y Y --ε--> D Y --ε--> Z(9) C --ε--> Z 7、NFA到DFA：子集构造算法 NFA->DFA：子集构造算法 算法思想 【例】$a(b|c)*$ 使用Thompson算法构造的NFA： graph LR Begin( ) --> A A(n0) --a--> B((n1)) B --ε--> C((n2)) C --ε--> D((n3)) D --ε--> E((n4)) E --b--> G((n5)) D --ε--> F((n6)) F --c--> H((n7)) G --ε--> Y((n8)) H --ε--> Y Y --ε--> D Y --ε--> Z(n9) C --ε--> Z 此时边上转移包含 $\varepsilon$（代价为0），即转移是不确定的，现在要转换成等价的DFA： $n0\overset{a}{\rightarrow} n1$ $n1 \to n2$代价为0，以此推算 $n0$ 可以无代价走到 $n1,n2,n3,n4,n6,n9$； 此时令集合 $q1 = \left \{n1,n2,n3,n4,n6,n9\right \}$，即 $n0\overset{a}{\rightarrow} q1$； 下面再从 $q1$ 出发： $q1\overset{b}{\rightarrow} \left \{ n5,n8,n9,n3,n4,n6 \right \}:q2$ $q1\overset{c}{\rightarrow} \left \{ n7,n8,n9,n3,n4,n6 \right \}:q3$ 从 $q2$ 出发：$q2\overset{...}{\rightarrow} \left \{ ... \right \}$ 依次类推求出所有子集，构造出 $n0 \overset{a}{\rightarrow} q1 \overset{b}{\rightarrow} q2 ......$，实现从NFA转化为DFA 在新的DFA里面，$q1,q2$ 其实都是接收状态 两个重要操作，称为ε-闭包 状态转换 对每个集合求边界 子集构造算法（工作表算法） q0 <- eps_closure(n0) // 计算n0能到达的地方 Q <- {q0} // 构造状态集 workList <- q0 // 队列 while (workList != []) // BFS remove q from workList foreach (character c) t <- eps_closure(delta(q, c)) D[q, c] <- t if (t \not\in Q) add t to Q and workList 对于上述例子来说： $q0= \left \{ n0 \right \}$； $q1 =t= \left \{ n1,n2,n3,n4,n6,n9\right \}$； $q2 = \left \{ n5.n8,n9,n3,n4,n6 \right \}$； $q3 = \left \{ n7,n8,n9,n3,n4,n6 \right \}$； $Q = \left \{ q0,q1,q2,q3 \right \}$ graph LR A((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C 接受状态为：$q1,q2,q3$。 不动点算法 算法为什么能够运行终止 时间复杂度 最坏情况$O(2^n)$ 但在实际中不常发生 因为并不是每个子集都会出现 ε-闭包的计算 深度优先方法 set closure = {}; void eps_closure (x) closure += {x} foreach (y: x--ε--> y) if (!visited(y)) eps_closure (y) 广度优先方法 set closure = {}; Q = []; // queue void eps_closure (x) = Q = [x]; while (Q not empty) q <- deQueue (Q) closure += q foreach (y: q----> y) if (!visited(y)) enQueue (Q, y) 8、DFA的最小化：Hopcroft算法 【例】DFA的$a(b|c)*$ graph LR A((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C 现在考虑合并：同样为接受状态/非接受状态 合并$q2,q3$： graph LR A((q0)) --a--> B(q1) B --b--> C(q4) B --c--> C C --b,c--> C 合并$q1,q4$，此时结构图正好诠释了$a(b|c)*$： graph LR A((q0)) --a--> B(q5) B --b,c--> B 这样的话可以占用更少的计算机资源 Hopcroft算法：基于等价类的思想 split(S) foreach (character c) if (c can split S) split S into T1, …, Tk hopcroft () split all nodes into N, A // 两个等价类：接受状态和非接受状态 while (set is still changes) split(S) 如图，split 相当于将 $s1$ 切分成 $s2$ 和 $s3$ graph LR subgraph s1 A B C end subgraph s2 D E end subgraph s3 F end A --a--> D B --a--> E C --a--> F 【例1】对于DFA的$a(b|c)*$，根据Hopcroft的思想： 首先我们分出两个集合：$N $ 和 $A$ graph LR subgraph N Aa end subgraph A B C D end Aa((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C 对于集合 $N$，不可再分；对于集合 $A$：可以接受 $b, c$ 两种不同字符，但总的来看不管怎么转换都是 $A$，即无法再分 graph LR A((q0)) --a--> B(q4) B --b,c--> B 【例2】如图 graph LR q0((q0)) --f--> q1((q1)) q1 --e--> q2((q2)) q1 --i--> q4((q4)) q2 --e--> q3(q3) q4 --e--> q5(q5) 则其对应的正则表达式为：$fee|fie = f(ee|ie)$ 首先切分成两个集合： graph LR subgraph N q0 q1 q2 q4 end subgraph A q3 q5 end q0((q0)) --f--> q1((q1)) q1 --e--> q2((q2)) q1 --i--> q4((q4)) q2 --e--> q3(q3) q4 --e--> q5(q5) 对于集合$A$，$q3,q5$ 无法区分，此集合不可分裂 对于集合$N$，到第三个字符 $e$ 时，$q2,q4$到$A$，但$q0, q1$还在内部，划分集合： $S1=\left \{ q0,q1 \right \},S2=\left \{ q2,q4 \right \},A=\left \{ q3,q5 \right \}$ 对于$S1$：都能接受$e$，且都可转换到$A$，不可再分 再看$S2$：$q0$不接受$e$，$q1$接受$e$后会转换到$S2$，拆分 最后得： graph LR q0((q0)) --f--> q1((q1)) q1 --e--> S((q2,q4)) q1 --i--> S S --e--> A(q3,q5) 9、DFA的代码表示 概念上讲，DFA是一个有向图 实际上，有不同的DFA的代码表示 转移表 (类似于邻接矩阵) 哈希表 跳转表 ...... 取决于在实际实现中，对时间空间的权衡 转移表 对于$a(b|c)*$ graph LR A((q0)) --a--> B(q1) B --b,c--> B 状态/字符 a b c 0 1 1 1 1 int table[M][N]; table[0]['a'] = 1; table[1]['b'] = 1; table[1]['c'] = 1; // other table entries are ERROR graph LR A[转移表] <--> B[词法分析驱动代码] 驱动代码： nextToken() state = 0 // 自动机目前走到的状态 stack = [] // 用于实现最长匹配 while (state != ERROR) c = getChar() if (state is ACCEPT) clear(stack) push(state) state = table[state][c] while(state is not ACCEPT) state = pop(); rollback(); 跳转表 nextToken() state = 0 stack = [] goto q0 q0: c = getChar() if (state is ACCEPT) clear (stack) push (state) if (c==‘a’) goto q1: q1: c = getChar() if (state is ACCEPT) clear (stack) push (state) if (c==‘b’||c==‘c’) goto q1

【计算机图形学】简单光照明模型 目录： Phong光照明模型 理想漫发射 镜面反射光 环境光（环境反射） Phong光照明模型 Phong光照明模型的不足 增量式光照明模型 Gouraud双线性光强插值 算法步骤的基本描述 在光的反射和折射现象中的能量分布：$I_{i}=I_{d}+I_{s}+I_{t}+I_{v}$ 分别表示为: $I_{i}$ 入射光强，$I_{d}$ 漫反射光强，$I_{s}$ 镜面反射光强，$I_{t}$ 透射光强，$I_{v}$吸收光强 立体角：面元ds向点光源P所张的立体角为 $dw=\frac{dS}{r^2}$ 点发光强度 单位时间内通过面元$ds$的光能量为光通量 $dF$ 点发光强度为某个方向上单位立体角内的光通量 $I=\frac{dF}{dw}=\frac{dF}{dS}r^2$ Phong光照明模型 简单光照明模型模拟物体表面对光的反射作用 光源为点光源 反射作用分为 镜面反射(Specular Reflection) 漫反射(Diffuse Reflection) 物体间作用用环境光(Ambient Light)表示 理想漫发射 由Lambert余弦定律，漫反射光强为$I_{d}=I_{p}K_{d}cos\theta =I_{p}K_{d}(L,N)$ $K_{d}$是与物体有关的漫反射系数，$0<K_{d}<1$ 漫发射系数$K_{d}$有三个分量$K_{dr}$，$K_{dg}$，$K_{db}$分别代表RGB三原色的漫反射系数，通过调整它们来设定物体的颜色 漫反射强度=材质的漫反射系数×光源强度×(法线方向向量·入射光方向向量) 例如：0.5（反射一半）×1（最强，白色）×cos0（入射光垂直于法线，夹角0）=0.5（半减，灰色） “·”是点乘，也就是说最后两向量的点积表示的就是它们夹角的cos值 镜面反射光 对一般的光滑表面，反射光集中在一个范围内，且由反射定律决定的反射方向光强最大 镜面反射光强可表示为$I_{s}=I_{p}K_{s}cos\alpha=I_{p}K_{s}(R,V)^n$ $K_{s}$是与物体有关的镜面反射系数，$n$为反射指数，反映物体表面的光泽程度，数目越大物体表面越光滑 反射方向计算$R=2Ncos\theta-L=2N(N·L)-L$ 镜面反射光将会在反射方向附近形成很亮的光斑，称为高光现象 镜面反射光产生的高光区域只反映光源的颜色 镜面反射系数是一个与物体的颜色无关的参数 镜面反射强度=材质镜面反射系数×光源强度×(法线方向向量·入射光与视点夹角一半的方向向量)^光泽度 例如：0.5（反射一半）×1（最强，白色）×cos0（视点位于反射光方向上，夹角0）^1（加权1）=0.5 （半减，灰色） * ^光泽度”是“光泽度次方”，光泽度越大，高光的亮斑越小 环境光（环境反射） 环境光是一种经过多次反射平衡的光，它的强度是均匀的，并且分布是一样的，即： 环境光没有位置或方向上的特征，只有一个颜色亮度值，而且不会衰减，所以在所有方向和所有物体表面上投射的环境光的数量是恒定不变的。 环境光是光源间接对物体的影响 光在物体和环境之间多次反射，最终达到平衡 同一环境下的环境光光强分布均匀 环境反射强度=材质环境反射系数×环境光强度 例如：0.5（反射一半）×1（最强，白色）=0.5（半减，灰色） Phong光照明模型 PHONG模型就是漫反射、镜面反射与环境反射的和，即：  像素颜色 = 环境反射色 + 漫反射色 + 镜面反射色 $I=I_{a}K_{a}+I_{p}K_{d}(L,N)+I_{p}K_{s}(R,V)^n$ 对物体表面上的每个点P，均需计算光线的反射方向。 为了减少计算量，假设： 光源在无穷远处，L为常向量 视点在无穷远处，V为常向量 （H•N）近似（R•V），H为L与V的平分向量 $H=(L+V)/|L+V|$ 对所有的点总共只需计算一次H的值，节省了计算时间 Phong光照明模型是真实感图形学中提出的第一个有影响的光照明模型 Phong光照明模型的不足 显示出的物体象塑料，无质感变化 没有考虑物体间相互反射光 镜面反射颜色与材质无关 镜面反射大入射角失真现象 增量式光照明模型 多边形内部的象素颜色相同 不同法向的多边形邻接处有光强突变及马赫带效应 保证多边形之间的颜色光滑过渡－增量式光照明模型 在每个多边形顶点处计算光照明强度或参数，然后在各个多边形内部进行双线性插值，得到多边形光滑均匀颜色分布 两个主要算法 双线性光强插值、Gouraud明暗处理 双线性法向插值、Phong明暗处理 Gouraud双线性光强插值 Gouraud于1971年提出，又被称为Gouraud明暗处理 计算多边形各顶点的光强，再用双线性插值，求出多边形内部各点的光强 算法步骤的基本描述 计算多边形顶点的平均法向 用简单光照明模型计算顶点的平均光强 插值计算离散多边形边上的各点光强 插值计算多边形内域中各点的光强

【计算机图形学】扫描转换、区域填充、剪裁、走样、消隐 目录： 多边形的扫描转换与区域填充 多边形的扫描转换 扫描线算法 边界标志算法 二者比较 区域填充算法 多边形的扫描转换与区域填充算法小结 剪裁 直线段裁剪 Cohen-Sutherland裁剪 中点分割算法 梁友栋－Barskey算法 Cohen-Sutherland与Liang-Barsky算法的比较 多边形裁剪 字符裁剪 反走样 提高分辨率 区域采样 过程 非加权区域采样方法有两个缺点： 加权区域取样 消隐 消隐的分类 Southerland按消隐空间分类 画家算法（列表优先算法） Z缓冲区算法 多边形的扫描转换与区域填充 多边形有两种重要的表示方法：顶点表示和点阵表示 多边形的扫描转换：把多边形的顶点表示转换为点阵表示 为什么研究图形的扫描转换和区域填充？ 与单纯由线条所构成的线画图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强 面着色可以是光栅图形的画面明暗自然，色彩丰富，形象逼真，且有真实感 多边形的扫描转换 扫描线算法 对于一条扫描线填充过程可以分为四个步骤：（1）求交（2）排序（3）配对（4）填色 边界标志算法 帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。 然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。 使用一个布尔量inside来指示当前点是否在多边形内的状态。 二者比较 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同 但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。 区域填充算法 区域指已经表示成点阵形式的填充图形，它是象素的集合。 区域可采用内点表示和边界表示两种表示形式。 区域可分为4向连通区域和8向连通区域。 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 区域填充算法要求区域是连通的。 顶点表示：也称为几何表示，是用区域的顶点序列来表示区域。 点阵表示：也称为像素表示，是用位于多边形内的像素集合来刻画多边形。 内点表示：区域内的所有像素着同一颜色，而区域外的所有像素具有另一种颜色； 边界表示：区域边界上的所有像素点具有特定的颜色（可以是填充色），在区域内的所有像素均不能具有这一特定色，而且边界外的像素不能 具有与边界相同的颜色。 算法基本思想： 给定区域G一种子点（x, y）,首先判断该点是否是区域内的一点，如果是，则将该点填充为新的颜色，然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充。 多边形的扫描转换与区域填充算法小结 多边形扫描转换是指将多边形的顶点表示转化为点阵表示 区域填充改变填充颜色 在区域填充算法中，要求给定区域内的一点作为种子点，然后从这一点根据连通性将新的颜色扩展到整个区域。 扫描转换多边形是从多边形的边界（顶点）信息出发，利用多种形式的连贯性进行填充的。 扫描转换区域填充的核心是知道多边形的边界。 区域填充条件更强一些，不但要知道边界，而且要知道区域内的一点，可以利用四连通或八连通区域不断向外扩展。 剪裁 裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以 便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。 直线段裁剪 直线段裁剪算法是复杂图元裁剪的基础。 复杂的曲线可以通过折线段来近似，裁剪问题可以化为直线段的裁剪问题。 Cohen-Sutherland 中点分割算法 梁友栋－barskey算法 Cohen-Sutherland裁剪 基本思想： 对于每条线段P1P2分为三种情况处理分为三种情况处理:  若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。  若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。 若线段不满足“取”或“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 中点分割算法 与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况: 全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。 对于第三种情况，用中点分割的方法求出线段与窗口的交点。 梁友栋－Barskey算法 --见笔记-- Cohen-Sutherland与Liang-Barsky算法的比较 Cohen-Sutherland算法的核心思想是编码 如果被裁剪的图形大部分线段要么在窗口内或者要么完全在窗口外，很少有贯穿窗口的。Cohen-Sutherland算法 效果非常好 在一般情况下，Liang-Barsky裁剪算法的效率则优于Cohen-Sutherland算法 Cohen-Sutherland和Liang-Barsky只能应用于矩形窗口 多边形裁剪 基本思想是一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧 多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种 对于情况（1）仅输出顶点P；情况（2）输出0个顶点； 情况（3）输出线段SP与裁剪线的交点I； 情况（4）输出线段SP与裁剪线的交点I和终点P 上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。 对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。 字符裁剪 串精度: 将包围字串的外接矩形对窗口作裁剪 (字符串的所有字符都在窗口内则保留，否则舍弃) 字符精度: 将包围字的外接矩形对窗口作裁剪 (对窗口有重叠或者落在外面的裁掉) 以及笔画\象素精度: 将笔划分解成直线段对窗口作裁剪 (像素、比划裁剪) 反走样 用离散量表示连续量引起的失真现象称之为走样(aliasing) 用于减少或消除这种效果的技术称为反走样(antialiasing) 提高分辨率 把分辨率提高一倍 直线经过两倍的象素，锯齿也增加一倍， 但同时每个阶梯的宽度也减小了一倍， 所以显示出的直线段看起来就平直光滑了一些。 增加分辨率虽然简单，但是不经济的方法——会引起扫描转换时间、帧缓存容量等一系列问题。 而且它也只能减轻而不能消除锯齿问题 区域采样 走样原因：由于在实际中，像素是由实际面积大小不为0，同时直线段的宽度是至少为1个像素。而我们假设是像素面积为0，亮度由覆盖该点的亮度决定，同时线段宽度为0。二者的矛盾是导致走样原因。 基本思想： 每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。 过程 首先将屏幕象素均分成n个子象素 然后计算中心点落在直线段内的子象素的个数k。 将屏幕该象素的亮度置为相交区域面积的近似值可k/n。 非加权区域采样方法有两个缺点： 象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应。 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。 加权区域取样 消隐 投影变换失去了深度信息，往往导致图形的二义性 要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面，简称为消隐。 经过消隐得到的投影图称为物体的真实图形。 消隐的对象是三维实体模型。三维实体模型的表示主要有边界表示法和实体构造法(CSG)等。 消隐的分类 按消隐对象分类 线消隐(线框图)：消隐对象是物体上的边，消除的是物体上不可见的边。 面消隐(填色图)：消隐对象是物体上的面，消除的是物体上不可见的面。 Southerland按消隐空间分类 物体空间的消隐算法: 将场景中每一个面与其他每个面比较，求出所有点、边、面遮挡关系。 光线投射 Roberts 图像空间的消隐算法: 对屏幕上每个象素进行判断，决定哪个多边形在该象素可见。 Z－buffer 扫描线 Warnock 物体空间和图像空间的消隐算法: 在物体空间中预先计算面的可见性优先级，再在图像空间中生成消隐图。 画家算法 画家算法（列表优先算法） 先把屏幕置成背景色 再把物体的各个面按其离视点的远近进行排序，排序结果存在一张深度优先级表中。 然后按照从远到近的顺序逐个绘制各个面。 Z缓冲区算法 帧缓存来存放每个象素的颜色值: 初值取成对应背景颜色的值 深度缓存来存放每个象素的深度值: 初值可放z的极小值 算法过程： 在把显示对象的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器相应单元前，要把这点的z坐标值和z缓冲器中相应单元的值进行比较。只有前者大于后者时才改变帧缓冲器的那一单元的值，同时z缓冲器中相应单元的值也要改成这点的z坐标值。 如果这点的z坐标值小于z缓冲器中的值，则说明对应象素已经显示了对象上一个点的属性，该点要比考虑的点更接近观察点。 对显示对象的每个面上的每个点都做了上述处理后，便可得到消除了隐藏面的图

【计算机图形学】扫描转换算法 目录： 直线的扫描转换算法 数值微分法（DDA） 中点画线法 Bresenham算法 圆弧的扫描转换算法 中点画圆法 直线的扫描转换算法 数值微分法（DDA） 步长=1(个象素)，计算相应的y坐标y=kx+b；取象素点(x, round(y))作为当前点的坐标。 当x每递增1，y递增k(即直线斜率)； 注意上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1, y最多增加1。 当 |k| > 1时，必须把x，y地位互换 x round(y+0.4) y+0.4 0 0 0 1 0 0+0.4 2 1 0.4+0.4 3 1 0.8+0.4 4 2 1.2+0.4 5 2 1.6+0.4 中点画线法 当前象素点为(xp, yp) ，下一个象素点可取为P1或P2。 设M=(xp+1, yp+0.5)，为P1与P2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。 当M在Q的下方，则P2应为下一个象素点； M在Q的上方，应取P1为下一点. $a=y_{0}-y_{1}$   $b=x_{1}-x_{0}$ $c=x_{0}y_{1}-x_{1}y_{0}$ $d_{0}=2a+b$ $d_{i}=2a(x_{i}+1)+2b(y_{i}+0.5)+2c$ 例：用中点画线法P0(0,0)—— P1(5,2) $a=y_{0}-y_{1}=-2, b=x_{1}-x_{0}=5, c=0$ $d_{0}=2a+b=1,(> 0)$ i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5 Bresenham算法 设直线方程为：$y_{i+1}=y_{i}+k(x_{i+1}-x_{i})=y_{i}+k$, 其中$k=dy/dx$。 因为直线的起始点在象素中心，所以误差项d的初值$d_{0}＝0$。 X下标每增加1，d的值相应递增直线的斜率值k，即$d＝d＋k$。一旦d≥1，就把它减去1，这样保证d在0、1之间 为方便计算，令$e＝d-0.5$，e的初值为-0.5，增量为k。 当$e≥0$时，取当前象素$(x_{i}，y_{i})$的右上方象素$(x_{i}＋1，y_{i}＋1)$; 而当$e<0$时，更接近于右方象素$(x_{i}＋1，y_{i})$。 可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作替换 例：$Line$: $P_{0}(0, 0), P_{1}(5,2)$， $d＝d＋k$， $e$的初值为-0.5，增量为$k$, $k=\frac{dy}{dx}=0.4$ x y e 0 0 - 0.1 1 0 0.3 2 1 - 0.3 3 1 0.1 4 2 - 0.5 5 2 - 0.1 圆弧的扫描转换算法 圆的特征: 八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集 中点画圆法 考虑中心在原点，半径为R的第二个8分圆 构造判别式（圆方程）： $d=F(M)=F(x_{p}+1,y_{p}-0.5)$ $=(x_{p}+1)^2+(y_{p}-0.5)^2-R^2$ 若$d<0$，则取$P_{1}$为下一象素，而且再下一象素的判别式为 $d'=F(x_{p}+2,y_{p}-0.5)=d+2x_{p}+3$ 若$d≥0$，则取$P_{2}$为下一象素，而且再下一象素的判别式为 $d'=F(x_{p}+2,y_{p}-1.5)=d=2(x_{p}-y_{p})+5$ 第一个像素是(0, R)，判别式d的初始值为： $d_{0}=F(1,R-0.5)=1.25-R$ 为了进一步提高算法的效率，可以将上面的算法中的 浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法 使用 $e=d-0.25$ 代替$d$，则 $e_{0}=1-R$

【计算机图形学】NURBS曲线和NURBS曲面 目录： NURBS曲线 NURBS曲线的性质 圆锥曲线的NURBS表示 NURBS曲线的修改 NURBS曲面 定义 性质 NURBS曲线 NURBS曲线（非均匀有理B样条）是由分段有理B样条多项式基函数定义的，k阶NURBS曲线的定义如下： $P(t)=\frac{\sum_{i=0}^{n}w_{i}P_{i}N_{i,k}(t)}{\sum_{i=0}^{n}w_{i}N_{i,k}(t)}=\sum_{i=0}^{n}P_{i}R_{i,k}(t)$ $R_{i,k}(t)=\frac{w_{i}N_{i,k}(t)}{\sum_{j=0}^{n}w_{j}N_{j,k}(t)}$ NURBS曲线的性质 $R_{i,k}(t)$具有k阶B样条基函数类似的性质 局部支撑性：$R_{i,k}(t)=0$, $t\notin [t_{i},t_{i+k}]$ 权性：$\sum_{i=0}^{n}R_{i,k}(u)=1$ 可微性：如果分母不为零，在节点区间内是无限次连续可微的，在节点处(k-1-r)次连续可导，r是该节点的重复度 NURBS曲线与B样条曲线具有类似的几何性质 局部性质 局变差减小性质 凸包性 在仿射与透射变换下的不变性 在曲线定义域内有与有理基函数同样的可微性 如果某个权因子为零，那么相应控制顶点对曲线没有影响 圆锥曲线的NURBS表示 取节点向量$T=[0,0,0,1,1,1]$，为则NURBS曲线退化为二次Bézier曲线，且可以证明，这是圆锥曲线弧方程。 $P(t)=\frac{(1-t^2)w_{0}P_{0}+2t(1-t)w_{1}P_{1}+t^2w_{2}P_{2}}{(1-t^2)w_{0}+2t(1-t)w_{1}+t^2w_{2}}$ 其中，$C_{sf}=\frac{w_{1}^2}{w_{0}w_{2}}$ 称为形状因子，$C_{sf}$ 的值确定了圆锥曲线的类型 $C_{sf}=1$ 时，上式是抛物线弧 $C_{sf}\in(1,\infty)$ 时，上式是双曲线弧 $C_{sf}\in(0，1)$ 时，上式是椭圆弧 $C_{sf}=0$ 时，上式退化为一对直线段P0P1和P1P2 $C_{sf}\rightarrow+\infty$ 时，上式退化为连接两点P0P2的直线段 NURBS曲线的修改 常用的方法有修改权因子、控制点和反插节点 修改权因子: 当保持控制顶点和其它权因子不变，减少或增加某权因子时，曲线被推离或拉向相应顶点 修改控制顶点: 修改控制顶点的位置，曲线随之变形 反插节点法 NURBS曲面 定义 $P(u,v)=\frac{\sum_{i=0}^{m}\sum_{j=0}^{n}w_{ij}P_{ij}N_{i,p}(u)N_{j,q}(v)}{\sum_{i=0}^{m}\sum_{j=0}^{n}w_{ij}N_{i,p}(u)N_{j,q}(v)}=\sum_{i=0}^{m}\sum_{j=0}^{n}P_{ij}R_{i,p;j,q}(u,v)$, $u,v\in[0,1]$ $R_{i,p;j,q}(u,v)=\frac{w_{ij}N_{i,p}(u)N_{j,q}(v)}{\sum_{r=0}^{m}\sum_{s=0}^{n}w_{rs}N_{r,p}(u)N_{s,q}(v)}$ 规定四角点处用正权因子，即$w_{00},w_{m0},w_{0n},w_{mn}>0$，其余$w_{ij}≥0$ 性质 与非有理B样条基函数相类似的性质： 局部支承性质 权性 可微性：在重复度为 $r$ 的 $u$ 节点处沿 $u$ 向是 $p-r-1$ 次连续可微，在重复度为 $r$ 的 $v$ 节点处沿 $v$ 向是 $q-r-1$ 次连续可微 极值.若 $p,q>1$，恒有一个极大值存在 是双变量B样条基函数的推广

【计算机图形学】B样条曲线及B样条曲面 目录： B样条曲线 定义 类型的划分 B样条曲线的性质 B样条曲面 B样条曲线 在保留Bézie优点的同时，克服了他的弱点：采用样条——分段连续多项式 例如，现在有n+1个点，在每两点之间构造一条多项式，则有n个小区间。每个小区间构造一条三次多项式，变成了n段的三次多项式拼接在一起，段与段之间要C²连续，这就是三次样条 定义  $P(t)=\sum_{i=0}^{n}P_{i}N_{i,k}(t)$ 其中，Pi是控制点，$N_{i,k}(t)$是调和函数，被称为k阶(k-1次)B样条基函数  B样条基函数是一个称为节点矢量的非递减的参数t的序列所决定的k阶分段多项式，也即为k阶（k-1次)多项式样条。 类型的划分 曲线按其端点是否重合，分为闭曲线和开曲线 B样条曲线按其节点矢量中节点的分布情况，可划分为四种类型： 均匀B样条曲线 节点矢量中节点为沿参数轴均匀或等距分布，所有节点区间长度为常数。这样的节点矢量定义了均匀的B样条基。 准均匀B样条曲线 与均匀B样条曲线的差别在于两端节点具有重复度k，这样的节点矢量定义了准均匀的B样条基。均匀B样条曲线没有保留Bézier曲线端点的几何性质，即样条曲线的首末端点不再是控制多边形的首末端点。采用准均匀的B样条曲线解决了这个问题 分段Bézier曲线 节点矢量中两端节点具有重复度k，所有内节点重复度为k-1，这样的节点矢量定义了分段的Bernstein基。 B样条曲线用分段Bézier曲线表示后，各曲线段就具有了相对的独立性，移动曲线段内的一个控制顶点只影响该曲线段的形状，对其它曲线段的形状没有影响。并且Bézier曲线一整套简单有效的算法都可以原封不动地采用。缺点是增加了定义曲线的数据，控制顶点数及节点数。 非均匀B样条曲线 任意分布的节点矢量，只要在数学上成立（节点序列非递减，两端节点重复度≤k，内节点重复度≤k-1）都可选取。这样的节点矢量定义了非均匀B样条基 B样条曲线的性质 局部性：k阶B样条曲线上参数为 $t\in[t_{i},t_{i+1}]$ 的一点至多与k个控制顶点 $P_{j}(j=i-k+1,...,i)$ 有关，与其他控制顶点无关；移动该曲线的第i个控制顶点Pi至多影响到定义在区间 $(t_{i},t_{i+k})$ 上那部分曲线的形状，对曲线的其余部分不发生影响。 连续性：P(t)在r重节点处的连续阶不低于$k-1-r$，整条曲线上的连续性不低于$k-1-r_{max}$ 凸包性：P(t)在区间 $(t_{i},t_{i+1}), k-1≤i≤n$ 上的部分位于k个点 $P_{i-k+1},...,P_{i}$ 的凸包$C_{i}$内，整条曲线则位于各凸包$C_{i}$的并集之内。这个性质被称为强凸包性。 分段参数多项式：P(t)在每一区间上都是次数不高于k-1的参数t的多项式 导数公式 $P'(t)=\left ( \sum_{i=0}^{n}P_{i}N_{i,k}(t) \right )'=\sum_{i=0}^{n}P_{i}N_{i,k}'(t)$ $=(k-1)\sum_{i=1}^{n}\left ( \frac{P_{i}-P_{i-1}}{t_{i+k-1}-t_{i}} \right )N_{i,k-1}(t), t \in[t_{k-1},t_{n+1}]$ 变差缩减性：设平面内n+1个控制顶点构成B样条曲线P(t)的特征多边形。在该平面内的任意一条直线与P(t)的交点个数不多于该直线和特征多边形的交点个数 几何不变性：B样条曲线的形状和位置与坐标系的选择无关 仿射不变性：在仿射变化下，表达式具有形式不变性 $A[P(t)]=\sum_{i=0}^{n}A[p_{i}]N_{i,k}(t)$, $t\in[t_{k-1},t_{n+1}]$ 直线保持性：控制多边形退化为一条直线时，曲线也退化为一条直线 造型的灵活性：用B样条曲线可以构造直线段、尖点、切线等特殊情况 B样条曲面 给定参数轴u和v的节点矢量 $U=[u_{0},u_{1},...,u_{m+p}]$ 和 $V=[v_{0}, v_{1}, ..., v_{n+q}]$, p×q阶B样条曲面定义如下：  $P(u,v)=\sum_{i=0}^{m}\sum_{j=0}^{n}P_{ij}N_{i,p}(u)N_{j,q}(v)$ 其中, $P_{i,j}$构成一张控制网络，称为B样条曲线的特征网络 $N_{i,p}(u)$ 和 $N_{j,q}(v)$ 是B样条基，分别用节点矢量U和V按照deBoor-Cox递推公式决定

【计算机图形学】Bézier曲线和Bézier曲面 ( 贝塞尔曲线和贝塞尔曲面 ) 目录： Bézier曲线 定义 Bernstein基函数的性质 Bezier曲线的性质 Bézier曲线的生成 Bézier曲线的拼接 Bézier曲面 矩阵表示式 Bézier曲面的性质 Bézier曲面的拼接 Bézier不足 Bézier曲线 定义 给定空间n+1个点的位置矢量Pi(i=0,1,2...)，则Bezier参数曲线上各点坐标的插值公式是：$P(t)=\sum_{i=0}^{n}P_{i}B_{i,n}(t), t\in [0,1]$ 其中，Pi构成该贝塞尔曲线的特征多边形，$B_{i,n}(t)$是n次Bernstein基函数： $B_{i,n}(t) = C_{i}^{n}t^{i}(1-t)^{n-i} = \frac{n!}{i!(n-i)!}t^{i}\cdot (1-t)^{n-i} (i=0,1,...,n)$ Bernstein基函数的性质 非负性：$B_{i,n}(t)≥0, t\in [0,1]$ 端点性质 $B_{i,n}(0) = \begin{cases} 1 & (i=0) \\ 0 & otherwise \end{cases}$    $B_{i,n}(1) = \begin{cases} 1 & (i=n) \\ 0 & otherwise \end{cases}$ 权性 $\sum_{i=0}^{n}B_{i,n}(0) = \sum_{i=0}^{n}C_{n}^{i}t^{i}(1-t)^{n-i}=[(1-t)+t]^{n}\equiv 1$ 对称性 $B_{i,n}(t) = B_{n-i,n}(1-t)$ 因为 $B_{n-i,n}(1-t) = C{n}^{i}$ 递推性 $B_{i,n}(t) = (1-t)B_{i,n-1}(t) + tB_{i-1,n-1}(t) (i=0,1,...,n)$ 即高一次的Bernstein基函数可由两个低一次的Bernstein调和函数线性组合而成, 因为$C_{n}^{i} = C_{n-1}^{i} + C_{n-1}^{i-1}$ 导函数 $B'n(t) = n[B_{i-1,n-1}(t)-B_{i,n-1}(t)] (i=0,1,...,n)$ 最大值 $B_{i,n}(t)$在 $t = \frac{i}{n}$ 处达到最大值 升阶公式 $(1-t)B_{i,n}(t)=(1-\frac{i}{n+1})B_{i,n+1}(t)$ $tB_{i,n}(t)=\frac{i+1}{n+1}B_{i+1,n+1}(t)$ $B_{i,n}(t)=(1-\frac{i}{n+1})B_{i,n+1}(t)+\frac{i+1}{n+1}B_{i+1,n+1}(t)$ 积分 $\int_{0}^{1}B_{i,n}(t) = \frac{1}{n+1}$ Bezier曲线的性质 端点性质 曲线端点位置矢量 由Bernstein基函数的端点性质可以推得，当t=0时，P(0)=P0 ；当t=1时，P(1)=Pn。由此可见，Bézier曲线的起点、终点与相应的特征多边形的起点、终点重合。 切矢量 因为$P'(t) = n\sum_{i=0}^{n-1}P_{i}[B_{i-1,n-1}(t) - B_{i,n-1}(t)]$ 所以当t=0时，P'(0)=n(P1-P0)，当t=1时，P'(1)=n(Pn-Pn-1)，这说明Bézier曲线的起点和终点处的切线方向和特征多边形的第一条边及最后一条边的走向一致。 对称性：由控制顶点构造出的新Bézier曲线，与原Bézier曲线形状相同，走向相反。 这个性质说明Bézier曲线在起点处有什么几何性质，在终点处也有相同的性质。 几何不变性：是指某些几何特性不随坐标变换而变化的特性 变差缩减性：若Bézier曲线的特征多边形是一个平面图形，则平面内任意直线与C(t)的交点个数不多于该 直线与其特征多边形的交点个数，这一性质叫变差缩减性质。 此性质反映了Bézier曲线比其特征多边形的波动还小，也就是说Bézier曲线比特征多边形的折线更光顺。 仿射不变性：在仿射变换下，Bézier曲线的形式不变。 Bézier曲线的生成 根据定义直接生成Bézier曲线(计算量较大) $B_{i,n}(t) = C_{i}^{n}t^{i}(1-t)^{n-i} = \frac{n!}{i!(n-i)!}t^{i}\cdot (1-t)^{n-i} (i=0,1,...,n)$ 给出$C_{n}^{i}$的递归计算式$C_{n}^{i}=\frac{n!}{i!(n-1)!}=\frac{n-i+1}{i}C_{n}^{i-1}$, 其中n ≥ i 将p(t)表示成分量坐标形式 Bézier曲线的递推算法 Bézier曲线上的任一个点(t)，都是其它相邻线段的同等比例(t)点处的连线，再取同等比例(t)的点再连线，一直取到最后那条线段的同等比例(t)处，该点就是Bézier曲线上的点(t) de Casteljau算法几何作图 Bézier曲线的拼接 Bézier曲线次数的提高，而高次多项式又会带来计算上的困难，实际使用中，一般不超过10次。采用分段设计，然后将各段曲线相互连接起来，并在接合处保持一定的连续条件。 给定两条Bézier曲线P(t)和Q(t)，相应控制点为Pi(i=0, 1, ..., n)和Qj(j=0,1,..., m) 要使它们达到G0连续，则：Pn= Q0 要使它们达到G1连续(平面)，只要保证Pn-1，Pn=Q，Q1三点共线就行了(因为Bezier曲线的起点和终点处的切线方向和特征多边形的第一条边及最后一条边的走向一致) 要使它们达到G2连续(空间)，则保证密切平面重合，副法线向量同向且曲率连续，更准确的说是曲率矢连续 Bézier曲面 定义 设$P_{i,j}$(i=0,1,...,m; j=0,1,...,n)为(m+1)(n+1)个空间点列，则m×n次张量积形式的Bézier曲面定义为：  $P(u,v)=\sum_{i=0}^{m}\sum_{j=0}^{n}P_{ij}B_{i,m}(u)B_{j,n}(v)$   $u,v\in [0,1]$ 其中$B_{i,m}(u)=C_{m}^{i}u^{i}(1-u)^{m-i}$, $B_{j,n}(v)=C_{n}^{j}u^{i}(1-v)^{n-j}$是Bernstein基函数。依次用线段连接点列中相邻两点所形成的空间网格，称之为特征网格。 矩阵表示式 在一般应用中，n和m不大于4 Bézier曲面的性质 角点位置：Bézier曲面特征网格的四个角点正好是Bézier曲面的四个角点，即 $P(0,0)=P_{0,0}$   $P(0,1)=P_{0,n}$ $P(1,0)=P_{m,0}$   $P(1,1)=P_{m,n}$ 边界线：四条边界线也是Bézier曲线 $P(u,0)=\sum_{j=0}^{m}P_{j,0}BEZ_{j,m}(u)$   $P(v,0)=\sum_{k=0}^{n}P_{k,0}BEZ_{k,n}(v)$ $P(u,1)=\sum_{j=0}^{m}P_{j,0}BEZ_{j,m}(u)$   $P(v,1)=\sum_{j=0}^{n}P_{k,0}BEZ_{k,n}(v)$ 几何不变性 对称性 凸包性 Bézier曲面的拼接 设两张m×n次Bézier曲面片 $P(u,v)=\sum_{i=0}^{m}\sum_{j=0}^{n}P_{ij}B_{i,m}(u)B_{j,n}(v)$ $Q(u,v)=\sum_{i=0}^{m}\sum_{j=0}^{n}Q_{ij}B_{i,m}(u)B_{j,n}(v)$ 如果要求两曲面片达到$G^{0}$连续，则它们有公共的边界，即：$P(1,v)=Q(0,v)$  于是有$P_{ni}=Q_{0i}$, (i = 0, 1,..., m) 如果又要求沿该公共边界达到$G^{1}$连续，则两曲面片在该边界上有公共的切平面，因此曲面的法向应当是跨界连续的，即：  $Q_{u}(0,v)×Q_{v}(0,v)=\alpha(v)P_{u}(1,v)×P_{v}(1,v)$ Bézier不足 Bézier曲线或曲面不能作局部修改 Bézier曲线或曲面的拼接比较复杂

【计算机图形学】WebGL光栅化流水线 目录： 三种图元 WebGL绘制流程 顶点提取器 顶点着色器 图元组装 光栅化 片元着色 顶点着色器和片元着色器的区别 三种图元 Point Line Triangle WebGL绘制流程 准备数据阶段：提供顶点坐标、索引（三角形绘制顺序）、uv（决定贴图坐标）、法线（决定光照效果），以及各种矩阵（比如投影矩阵） 生成顶点着色器 图元装配：坐标转换 生成片元着色器：模型是什么颜色，看起来是什么质地，光照效果，阴影（流程较复杂，需要先渲染到纹理，可以先不关注），都在这个阶段处理。 光栅化 顶点提取器 获取顶点坐标, 并写入缓存区 由于顶点数据往往成千上万，在获取到顶点坐标后，我们通常会将它存储在显存，即缓存区内，方便GPU更快读取。 顶点着色器 顶点着色器需要完成的工作主要有：坐标变换和逐顶点光照。除此之外，顶点着色器还可以输出后续阶段所需的数据。 图元组装 画三角形 把顶点组装成三角形组 光栅化 计算机的图像的都是用像素表示的，无论是点、直线、圆或其他图形最终都会以点的形式显示。人们看到屏幕的直线只不过是模拟出来的，人眼不能分辨出来而已。 光栅化其实是一种将几何图元变为二维图像的过程。 该过程包含了两部分的工作： 第一部分工作：决定窗口坐标中的哪些整型栅格区域被基本图元占用； 第二部分工作：分配一个颜色值和一个深度值到各个区域。 光栅化过程产生的是片元。 片元着色 光栅化阶段并不影响屏幕上每个像素的颜色值，而是产生一系列的数据信息，用来表述一个三角网格是怎么覆盖每个像素的。而每个片元就是负责存储这一系列数据。真正会对像素产生影响的阶段是下一个流水线阶段--逐片元操作 片元着色器的输入是上一个阶段对顶点信息插值得到的结果，具体来说，是根据那些从顶点着色器中输出的数据插值得到的。而它的输出是一个或者多个颜色值。 这一阶段可以完成很多重要的渲染技术，最重要的技术之一就是纹理采样。为了在片元着色器中进行纹理采样。通常在顶点着色器阶段输出每个顶点的纹理坐标，然后经过光栅化阶段对三角形网格的3个顶点的纹理坐标进行插值后，就可以得到其覆盖的片元的纹理坐标了。 顶点着色器和片元着色器的区别 Fragment Shader是在光栅化之后。在Vertex Shader阶段，我们要处理的数据只是顶点，而在Fragment Shader阶段，我们要处理的则是（大 致上）被这三个顶点围住的所有像素对应的Fragments。