本書詳細闡述了與計算機動畫算法相關的高效解決方案及相應的數據結構和算法，主要包括技術背景知識、插值技術、插值動畫技術、運動鏈接、運動捕捉、物理動畫、流體、人物角色的建模和動畫、面部動畫、建模行為以及特殊動畫模型等內容。此外，本書還提供了相應的算法、代碼以及偽代碼，以幫助讀者進一步理解相關方案的實現過程。
本書適合作為高等院校計算機及相關專業的教材和教學參考書，也可作為相關開發人員的自學教材和參考手冊。
前 言
總述
針對定義和生成圖形對象，即計算機動畫，本書主要講述對應的計算機算法以及程序設計技術，且集中講解三維（3D）領域中的計算機動畫內容。因此，本書適用于計算機科學與技術方向的高年級本科生以及研究生。而對于那些期望學習計算機動畫程序設計的程序員、使用軟件工具生成計算機動畫（并嘗試理解動畫制作軟件中的底層計算問題）的制作人員，本書也將大有裨益。
本書的出版應是意料之中的事情近年來，計算機動畫獲得了長足的發展，且廣泛地出現于科研領域、學術領域，并帶來了一定的就業機會，甚至一些人還將其視為一項終生愛好。
目前，影片大多采用數字方式存儲，并引入了數字特效（通常稱作計算機圖像合成，簡稱為CGI）。來自互聯網電影數據庫（網址為www.imdb.com）2007年6月的一份資料顯示，前10名的美國影片（數據源于北美電影票房排行榜）均廣泛地采用了CGI技術。
不難發現，計算機動畫影片已具有相當的票房號召力，根據不完全統計，每5部上榜電影中就有1部為計算機動畫電影。20012006年，數字圖像技術領域出現了27位科技成就獎與科學和工程獎獲得者。每年，計算機動畫還為游戲產業創造了不低于70億美金的收益。當前，功能強大的動畫軟件、低廉的CPU價格以及高存儲量的家庭數字視頻錄像設備均使得桌面級計算機動畫成為可能。大多數教育部門（如計算機科學系）均開設了與計算機動畫相關的課程（以及相關的藝術課程，進而培養數字藝術家熟練地使用現有的計算機動畫軟件）。在計算機動畫算法方面，學術會議以及相關期刊也記錄了業界的發展現況。
本書對于實際操作過程中的相關問題均有所描述，并提供了可行性技術以及相對直觀的實現方案。除了某些研究方向之外，本書盡量避免純理論方式的討論。本書中的部分示例程序為完整的可執行代碼，此類代碼采用C語言編寫，復制、編譯以及運行之后，即可生成算法結果；其他程序設計示例則采用類C偽代碼加以編寫，并可在適當的時候轉換為可執行工作代碼。這里，采用C語言編寫代碼的主要原因是，該語言包含了其他語言（如C 語言和Java語言）的基礎特性，并可彰顯算法的逐步操作過程。本書附錄包含了與此相關的基礎內容，初學者可獲取其中的有用內容以及實現過程中的特定算法。
本書并不打算詳細介紹當今流行的動畫軟件包的使用方法（當然，也不排除針對某一類特定技術討論軟件的使用，這將有助于深入理解底層計算過程），也不會具體闡述計算機動畫理論、計算機動畫美學知識、動畫設計過程中的美學問題、動畫作品制作過程中的細節問題以及計算機輔助動畫（此類問題是指傳統手繪動畫的計算機化操作，多數時候，該問題包含一套自身的規則集，參見結尾處參考文獻1、2），而是主要討論全三維計算機動畫及其算法技術，動畫制作人員和程序員可藉此以有趣的方式移動對象。盡管本書重點闡述3D技術，但2D技術依然十分重要。
計算機動畫程序設計的基本目標是選擇適當的技術和設計工具，以使動畫設計人員表達豐富的細節，進而確定期望的內容；同時，相關技術和工具還應具備強大的功能，以使動畫設計人員從枯燥的細節設定中解脫出來。然而，針對每一位動畫設計人員、每一部動畫作品，甚至是一部動畫作品中的各個場景，通常不存在一類全功能的軟件工具。這里，特定的動畫工具往往取決于期望中的制作效果以及制作人員的控制過程。根據不同的模擬內容，動畫藝術作品常需要使用不同的軟件工具，因此，各類處理方案也層出不窮。
本書組織方式
第1章綜合探討了與計算機動畫相關的問題，包括感知、手繪動畫技術發展史、動畫作品的測算方式以及計算機動畫發展簡史，相關內容提供了動畫藝術與制作的廣闊視角。
第2章講述了必要的背景知識以及與動畫相關的計算機圖形學內容，并對計算機圖形學中的計算問題進行了回顧，為后續學習打下堅實的基礎，其中包括對渲染管線的回顧以及對轉換順序的討論，以降低一系列計算所產生的舍入誤差。另外，本章還講解了基于方向表達的四元數形式。如果讀者具有豐富的計算機圖形學知識，則可跳過相關知識點，甚至整章內容。
第3章和第4章重點介紹插值技術。其中，第3章介紹與插值技術相關的基礎知識，包括時間-空間曲線、曲線的弧長參數化操作以及曲線上的速度控制，隨后還討論了基于四元數的方向插值計算，且各類方案均與路徑結合使用。第4章闡述了基于插值方案的動畫技術，包括關鍵幀插值、動畫語言以及形狀插值。
第5章和第6章主要涉及關節型角色的動力學控制問題。其中，第5章討論鏈接附肢的動力學方案，且同時涉及正向動力學和逆向動力學，并對正向動力學專門加以介紹。第6章討論與運動捕捉（mocap）相關的基礎內容，包括標記的處理方式以及運動捕捉結果數據的調校過程。
第7章和第8章討論與動畫相關的、真實世界的建模處理過程。其中，第7章探討基于物理的動畫、彈簧-阻尼系統、粒子系統、剛體動力學以及強制型約束條件。第8章介紹流體建模和動畫技術，且分別論述了流體宏觀特征處理模型以及計算流體動力學。
第9~11章討論人類和其他動物的動畫行為。其中，第9章主要介紹角色動畫，包括建模操作、抵達行為、行走行為、布料以及頭發。第10章則探討面部動畫，包括面部建模、表情以及口型動畫。第11章討論行為動畫，包括群集行為、捕食者模型以及群體行為。
第12章闡述了某些特定模型，包括隱式表面、L系統以及表面細分操作。
附錄A展示了與計算機動畫相關的、圖像生成過程中所涉及的渲染問題，如雙緩沖機制、合成操作、運動模糊以及陰影效果。這里，假設讀者已了解幀緩沖區、z緩沖顯示算法以及抗鋸齒操作等內容。
附錄B講述了原理型知識點，包括插值計算和逼近技術、向量代數和矩陣、四元數演示代碼、物理學第一定律、數值技術以及電影、視頻、圖像格式屬性。
目 錄
第1章 概述 1
1.1 運動感知 2
1.2 動畫發展簡史 3
1.2.1
早期設備 4
1.2.2
早期傳統動畫 5
1.2.3
迪士尼 7
1.2.4
其他技術 8
1.2.5
其他動畫媒介 8
1.3 動畫制作 8
1.3.1
動畫原理 11
1.3.2
電影制作原理 12
1.3.3
聲音 14
1.4 計算機動畫制作 15
1.4.1
計算機動畫制作任務 16
1.4.2
數字編輯 17
1.4.3
數字視頻 20
1.4.4
數字音頻 20
1.5 計算機動畫簡史 21
1.5.1
早期行為（1980年之前） 21
1.5.2
中期階段（20世紀80年代） 24
1.5.3
新紀元（20世紀80年代以后） 25
1.6 本章小結 29
參考文獻 29
第2章 技術背景知識 33
2.1 空間與轉換 33
2.1.1
顯示管線 34
2.1.2
齊次坐標和轉換矩陣 38
2.1.3
復合轉換：轉換矩陣的累積操作 39
2.1.4
基本的轉換操作 39
2.1.5
描述任意方向 41
2.1.6
從矩陣中獲取轉換操作 44
2.1.7
顯示管線中的轉換描述 44
2.1.8
誤差 46
2.2 方向表達 49
2.2.1
定角表達 50
2.2.2
歐拉角表達 51
2.2.3
軸角表達 52
2.2.4
四元數表達 53
2.2.5
指數映射表達 55
2.3 本章小結 55
參考文獻 55
第3章 插值技術 57
3.1 插值計算 57
3.1.1
生成函數 57
3.1.2
綜述 60
3.2 曲線頂點的移動控制 60
3.2.1
計算弧長 61
3.2.2
速度控制 73
3.2.3
易入/易出 74
3.2.4
通用距離-時間函數 80
3.2.5
匹配于位置-時間對的曲線 82
3.3 方向插值 83
3.4 與路徑協同工作 87
3.4.1
路徑移動 87
3.4.2
基于路徑的方向 88
3.4.3
基于路徑平滑操作 91
3.4.4
沿表面確定路徑 96
3.4.5
路徑計算 97
3.4.6
綜述 98
3.5 本章小結 98
參考文獻 98
第4章 插值動畫技術 101
4.1 關鍵幀系統 101
4.2 動畫語言 104
4.2.1
面向設計人員的動畫語言 105
4.2.2
基于動畫設計的全功能程序語言 106
4.2.3
關聯變量 106
4.2.4
圖形語言 107
4.2.5
基于角色的動畫語言 107
4.3 對象的變形操作 108
4.3.1
拾取和拖曳 108
4.3.2
嵌入空間的變形 110
4.4 三維形狀插值方案 120
4.4.1
匹配拓撲結構 121
4.4.2
星形多面體 122
4.4.3
軸向切面 123
4.4.4
球體映射 125
4.4.5
遞歸細分 128
4.5 變形效果（二維） 130
4.5.1
坐標網格方案 130
4.5.2
特征變形 135
4.6 本章小結 140
參考文獻 140
第5章 運動鏈接 143
5.1 層次結構建模 144
5.1.1
基于層次建模的數據結構 145
5.1.2
局部坐標框架 149
5.2 前向動力學 150
5.3 逆向動力學 151
5.3.1
通過解析法求解簡單系統 152
5.3.2
Jacobian方案 153
5.3.3
逆向動力學的數值方案 157
5.3.4
綜述 163
5.4 本章小結 163
參考文獻 163
第6章 運動捕捉 165
6.1 運動捕捉技術 165
6.2 圖像處理 166
6.3 相機校正 168
6.4 三維位置重構 169
6.4.1
多標記 170
6.4.2
多相機 171
6.5 骨骼匹配 171
6.6 從運動捕捉系統中輸出內容
172
6.7 操控運動捕捉數據 174
6.7.1
信號處理 174
6.7.2
運動重定位 174
6.7.3
運動組合 175
6.8 本章小結 175
參考文獻 176
第7章 物理動畫 177
7.1 基本物理學知識 177
7.2 彈性動畫示例 180
7.2.1
彈性對象 180
7.2.2
虛擬彈簧 182
7.3 粒子系統 183
7.3.1
生成粒子 183
7.3.2
粒子屬性 184
7.3.3
粒子消亡 184
7.3.4
粒子動畫 184
7.3.5
粒子渲染 185
7.3.6
粒子系統表達 185
7.3.7
粒子受力狀態 186
7.3.8
粒子生命周期 186
7.4 剛體模擬 186
7.4.1
自由落體 187
7.4.2
碰撞體 195
7.4.3
基于鏈接層次結構的動力學 206
7.5 布料 208
7.5.1
褶皺的直接建模 209
7.5.2
物理建模 212
7.6 軟約束條件和硬約束條件
215
7.6.1
能量最小化 216
7.6.2
空間-時間約束條件 218
7.7 本章小結 220
參考文獻 220
第8章 流體：液體和氣體 223
8.1 特定流體模型 223
8.1.1
水流模型 223
8.1.2
云彩模型和動畫 232
8.1.3
火焰建模和動畫 237
8.1.4
綜述 239
8.2 計算流體動力學 239
8.2.1
流體建模的通用解決方案 240
8.2.2
CFD方程 241
8.2.3
網格方案 244
8.2.4
包含均勻粒子流體動力學的粒子方案 245
8.3 本章小結 247
參考文獻 248
第9章 人物角色的建模和動畫
251
9.1 虛擬人物表現方式 251
9.1.1
軀體幾何體的表達方式 252
9.1.2
幾何體數據采集 253
9.1.3
幾何體變形 254
9.1.4
表面細節 254
9.1.5
人物角色建模過程中的層次方案 255
9.2 搜索和抓取行為 258
9.2.1
手臂建模 259
9.2.2
肩部關節 261
9.2.3
手部 261
9.2.4
協調的運動行為 263
9.2.5
回避障礙物 263
9.2.6
受力狀態 264
9.3 行走效果 265
9.3.1
運動機制 266
9.3.2
行進過程中的動力學 269
9.3.3
基于動力學的真實運動行為 272
9.3.4
前向動力學控制 273
9.3.5
綜述 273
9.4 覆蓋特征 274
9.4.1
布料和服裝 274
9.4.2
頭發 274
9.5 本章小結 276
參考文獻 277
第10章 面部動畫 283
10.1
面部結構 283
10.1.1
解剖學結構 283
10.1.2
面部行為編碼系統 285
10.2
面部模型 286
10.2.1
創建連續的表面模型 287
10.2.2
紋理 292
10.3
臉部的動畫效果 293
10.3.1
參數化模型 293
10.3.2
彎曲形狀 294
10.3.3
肌肉模型 295
10.3.4
面部表情 297
10.3.5
綜述 298
10.4
口型動畫 298
10.4.1
語音發聲 298
10.4.2
音素 299
10.4.3
協同發音 300
10.4.4
韻律學 301
10.5
本章小結 301
參考文獻 301
第11章 建模行為 305
11.1
原始行為 307
11.1.1
群集行為 307
11.1.2
捕食行為 316
11.2
環境認知 316
11.2.1
視覺 317
11.2.2
記憶 318
11.3
智能行為建模 318
11.3.1
自主行為 319
11.3.2
表達方式和姿態 320
11.3.3
個性化建模：個性和情感狀態 321
11.4
群體管理 322
11.4.1
群體行為 323
11.4.2
內部結構 323
11.4.3
群體控制 324
11.4.4
n2復雜度管理 324
11.4.5
外觀效果 325
11.5
本章小結
325
參考文獻 325
第12章 特殊動畫模型 329
12.1
隱式表面 329
12.1.1
基本的隱式表面方程 329
12.1.2
基于隱式定義對象的動畫效果 331
12.1.3
碰撞檢測 332
12.1.4
基于碰撞的隱式表面變形 332
12.1.5
Level Set法 334
12.1.6
綜述 335
12.2
植物 335
12.2.1
植物學簡介 336
12.2.2
L系統 337
12.2.3
綜述 343
12.3
表面細分 344
12.4
本章小結 345
參考文獻 345
附錄A 渲染技術 349
A.1 雙緩沖區機制 349
A.2 合成機制 350
A.2.1
忽略像素深度信息的合成技術 351
A.2.2
基于像素深度信息的合成技術 355
A.3 顯示運動對象：運動模糊
357
A.4 投影式陰影 359
A.5 廣告牌和替身圖技術 363
A.6 小結 364
參考文獻 364
附錄B 背景知識和技術 367
B.1 向量和矩陣 367
B.1.1
逆矩陣和線性方程求解 368
B.1.2
奇值分解法 374
B.2 幾何計算 374
B.2.1
向量分量 375
B.2.2
向量長度 375
B.2.3
兩向量的點和計算 375
B.2.4
兩向量的叉積計算 376
B.2.5
向量和矩陣計算法則 377
B.2.6
三維空間內兩直線間的最近點 380
B.2.7
面積計算 381
B.2.8
余弦定理 382
B.2.9
質心坐標 383
B.2.10
計算包圍邊界形狀 383
B.3 變換操作 396
B.3.1
基于向量-矩陣乘法的頂點變換 396
B.3.2
基于向量-矩陣乘法的向量變換 397
B.3.3
軸-角旋轉 398
B.3.4
四元數 398
B.4 基于鏈接附肢的Denavit-Hartenberg
表現形式 400
B.4.1
Denavit-Hartenberg表示法 400
B.4.2
簡單示例 403
B.4.3
添加球狀關節 403
B.4.4
構建坐標系 405
B.5 插值計算和近似曲線 405
B.5.1
方程：基本術語 405
B.5.2
簡單的線性插值計算：幾何體和代數形式 407
B.5.3
基于弧長的參數化操作 408
B.5.4
導數計算 408
B.5.5
Hermite插值計算 408
B.5.6
Catmull-Rom樣條 409
B.5.7
4頂點形式 412
B.5.8
混合拋物線 412
B.5.9
Bezier插值/逼近方案 413
B.5.10
基于De Casteljau構造方案的Bezier曲線 414
B.5.11
張力、連續性以及偏移控制 414
B.5.12
B樣條 417
B.5.13
曲線與頂點集合之間的匹配 417
B.6 隨機性 418
B.6.1
噪聲 419
B.6.2
擾動效果 421
B.6.3
隨機數生成器 422
B.7 物理初探 423
B.7.1
位置、速度和加速度 423
B.7.2
圓周運動 424
B.7.3
牛頓運動定律 425
B.7.4
慣性和慣性參考坐標系 425
B.7.5
質心 426
B.7.6
轉矩 426
B.7.7
平衡狀態：平衡作用力 426
B.7.8
重力 427
B.7.9
向心力 427
B.7.10
接觸力 427
B.7.11
離心力 429
B.7.12
功和勢能 429
B.7.13
動能 429
B.7.14
能量守恒 430
B.7.15
動量守恒 430
B.7.16
振蕩運動 430
B.7.17
阻尼機制 431
B.7.18
角動量 431
B.7.19
慣性張量 431
B.8 數值積分 432
B.8.1
基于弧長的函數積分計算 433
B.8.2
更新函數值 434
B.8.3
更新位置數據 437
B.9 優化技術 438
B.9.1
解析法 439
B.9.2
數值法 439
B.10
電影技術標準 441
B.10.1
模擬技術 441
B.10.2
數字世界 445
B.11
相機校正 448
參考文獻 451
新書資訊