計(jì)算機(jī)圖形學(xué)幾何工具算法詳解

第1章  緒論
 1. 1  如何使用本書
 1. 2  關(guān)于數(shù)值計(jì)算的若干問題
 1. 2. 1  低層問題
 1. 2. 2  高層問題
 1. 3  各章內(nèi)容概要
 第2章  矩陣和線性系統(tǒng)
 2. 1  導(dǎo)言
 2. 1. 1  動(dòng)機(jī)
 2. 1. 2  組織
 2. 1. 3  符號(hào)約定
 2. 2  多元組
 2. 2. 1  定義
 2. 2. 2  算術(shù)運(yùn)算
 2. 3  矩陣
 2. 3. 1  符號(hào)與術(shù)語
 2. 3. 2  轉(zhuǎn)置
 2. 3. 3  算術(shù)運(yùn)算
 2. 3. 4  矩陣乘法
 2. 4  線性系統(tǒng)
 2. 4. 1  線性方程
 2. 4. 2  兩個(gè)未知數(shù)的線性系統(tǒng)
 2. 4. 3  一般線性系統(tǒng)
 2. 4. 4  減行. 階梯形和秩
 2. 5  方陣
 2. 5. 1  對(duì)角矩陣
 2. 5. 2  三角形矩陣
 2. 5. 3  行列式
 2. 5. 4  逆矩陣
 2. 6  線性空間
 2. 6. 1  數(shù)域
 2. 6. 2  定義和性質(zhì)
 2. 6. 3  子空間
 2. 6. 4  線性組合和生成空間
 2. 6. 5  線性無關(guān). 維數(shù)和基底
 2. 7  線性映射
 2. 7. 1  映射基礎(chǔ)
 2. 7. 2  線性映射
 2. 7. 3  線性映射的矩陣表示
 2. 7. 4  克萊姆定理
 2. 8  特征值和特征向量
 2. 9  歐幾里得空間
 2. 9. 1  內(nèi)積空間
 2. 9. 2  正交和標(biāo)準(zhǔn)正交集
 2. 10  最小二乘法
 2. 11  推薦的閱讀材料
 第3章  向量代數(shù)
 3. 1  向量基礎(chǔ)
 3. 1. 1  向量等價(jià)
 3. 1. 2  向量加法
 3. 1. 3  向量減法
 3. 1. 4  向量數(shù)乘
 3. 1. 5  向量加法和數(shù)乘的性質(zhì)
 3. 2  向量空間
 3. 2. 1  生成空間
 3. 2. 2  線性無關(guān)
 3. 2. 3  基底. 子空間和維數(shù)
 3. 2. 4  方向
 3. 2. 5  基底變化
 3. 2. 6  線性變換
 3. 3  仿射空間
 3. 3. 1  歐幾里得幾何
 3. 3. 2  體積. 行列式和數(shù)量三重積
 3. 3. 3  坐標(biāo)系
 3. 4  仿射變換
 3. 4. 1  仿射映射的類型
 3. 4. 2  仿射映射的合成
 3. 5  重心坐標(biāo)和單形
 3. 5. 1  重心坐標(biāo)和子空間
 3. 5. 2  仿射無關(guān)
 第4章  矩陣. 向量代數(shù)和變換
 4. 1  導(dǎo)言
 4. 2  點(diǎn)和向量的矩陣表示
 4. 3  加法. 減法和乘法
 4. 3. 1  向量加法和減法
 4. 3. 2  點(diǎn)與向量的加法和減法
 4. 3. 3  點(diǎn)的減法
 4. 3. 4  數(shù)乘
 4. 4  向量乘積
 4. 4. 1  點(diǎn)積
 4. 4. 2  叉積
 4. 4. 3  張量積
 4. 4. 4  正交運(yùn)算符和正交點(diǎn)積
 4. 5  仿射變換的矩陣表示
 4. 6  基底變化／幀／坐標(biāo)系統(tǒng)
 4. 7  向量幾何和仿射變換
 4. 7. 1  標(biāo)記法
 4. 7. 2  平移
 4. 7. 3  旋轉(zhuǎn)
 4. 7. 4  縮放
 4. 7. 5  反射
 4. 7. 6  剪切
 4. 8  投影
 4. 8. 1  正射投影
 4. 8. 2  斜軸投影
 4. 8. 3  透視投影
 4. 9  變換法線向量
 推薦的閱讀材料
 第5章  二維幾何圖元
 5. 1  線形對(duì)象
 5. 1. 1  隱含形式
 5. 1. 2  參數(shù)形式
 5. 1. 3  表示法之間的轉(zhuǎn)換
 5. 2  三角形
 5. 3  矩形
 5. 4  折線和多邊形
 5. 5  二次曲線
 5. 5. 1  圓
 5. 5. 2  橢圓
 5. 6  多項(xiàng)式曲線
 5. 6. 1  貝塞爾曲線
 5. 6. 2  B樣條曲線
 5. 6. 3  非均勻有理B樣條曲線
 第6章  二維距離
 6. 1  點(diǎn)到線形對(duì)象的距離
 6. 1. 1  點(diǎn)到直線的距離
 6. 1. 2  點(diǎn)到射線的距離
 6. 1. 3  點(diǎn)到線段的距離
 6. 2  點(diǎn)到折線的距離
 6. 3  點(diǎn)到多邊形的距離
 6. 3. 1  點(diǎn)到三角形的距離
 6. 3. 2  點(diǎn)到矩形的距離
 6. 3. 3  點(diǎn)到正交平截面的距離
 6. 3. 4  點(diǎn)到凸多邊形的距離
 6. 4  點(diǎn)到二次曲線的距離
 6. 5  點(diǎn)到多項(xiàng)式曲線的距離
 6. 6  線形對(duì)象之間的距離
 6. 6. 1  直線到直線的距離
 6. 6. 2  直線到射線的距離
 6. 6. 3  直線到線段的距離
 6. 6. 4  射線到射線的距離
 6. 6. 5  射線到線段的距離
 6. 6. 6  線段到線段的距離
 6. 7  線形對(duì)象到折線或多邊形的距離
 6. 8  線形對(duì)象到二次曲線的距離
 6. 9  線形對(duì)象到多項(xiàng)式曲線的距離
 6. 10  GJK算法
 6. 10. 1  集合運(yùn)算
 6. 10. 2  算法概述
 6. 10. 3  其他算法
 第7章  二維相交
 7. 1  線形對(duì)象之間的相交
 7. 2  線形對(duì)象與折線的相交
 7. 3  線形對(duì)象與二次曲線的相交
 7. 3. 1  線形對(duì)象與一般二次曲線的相交
 7. 3. 2  線形對(duì)象與圓形曲線的相交
 7. 4  線形對(duì)象與多項(xiàng)式曲線的相交
 7. 4. 1  代數(shù)方法
 7. 4. 2  折線逼近
 7. 4. 3  分級(jí)包圍
 7. 4. 4  單調(diào)分解
 7. 4. 5  柵格方法
 7. 5  二次曲線之間的相交
 7. 5. 1  一般二次曲線之間的相交
 7. 5. 2  圓形二次曲線之間的相交
 7. 5. 3  橢圓之間的相交
 7. 6  多項(xiàng)式曲線之間的相交
 7. 6. 1  代數(shù)方法
 7. 6. 2  折線逼近
 7. 6. 3  分級(jí)包圍
 7. 6. 4  柵格方法
 7. 7  軸分離方法
 7. 7. 1  投影到直線上的分離
 7. 7. 2  固定凸多邊形的分離
 7. 7. 3  運(yùn)動(dòng)凸多邊形的分離
 7. 7. 4  固定凸多邊形的交集
 7. 7. 5  運(yùn)動(dòng)凸多邊形的接觸點(diǎn)集
 第8章  其他二維問題
 8. 1  三點(diǎn)確定的圓
 8. 2  與三條直線相切的圓
 8. 3  與圓相切于給定點(diǎn)的直線
 8. 4  通過給定點(diǎn)并與圓相切的直線
 8. 5  與兩圓相切的直線
 8. 6  兩點(diǎn)和給定半徑?jīng)Q定的圓
 8. 7  通過一點(diǎn)并與一條直線相切且具有給定半徑的圓
 8. 8  與兩條直線相切且具有給定半徑的圓
 8. 9  經(jīng)過一點(diǎn)并與一個(gè)圓相切且具有給定半徑的圓
 8. 10  具有給定半徑并與一條直線和一個(gè)圓相切的圓
 8. 11  具有給定半徑并與兩圓相切的圓
 8. 12  與一條給定直線垂直并通過一個(gè)給定點(diǎn)的直線
 8. 13  位于兩點(diǎn)之間并與該兩點(diǎn)等距的直線
 8. 14  與一條給定直線平行且相距指定值的直線
 8. 15  與給定直線平行且垂直(水平)距離為指定值的直線
 8. 16  與給定圓相切并與給定直線垂直的直線
 第9章  三維幾何圖元
 9. 1  線形對(duì)象
 9. 2  平面對(duì)象
 9. 2. 1  平面
 9. 2. 2  相對(duì)于一個(gè)平面的坐標(biāo)系統(tǒng)
 9. 2. 3  平面上的二維對(duì)象
 9. 3  多邊形網(wǎng)格. 多面體和有限多面體
 9. 3. 1  頂點(diǎn)一邊一面表
 9. 3. 2  互連網(wǎng)格
 9. 3. 3  復(fù)式網(wǎng)格
 9. 3. 4  閉合網(wǎng)格
 9. 3. 5  一致次序
 9. 3. 6  柏拉圖立體
 9. 4  二次曲面
 9. 4. 1  三個(gè)非零特征值
 9. 4. 2  兩個(gè)非零特征值
 9. 4. 3  一個(gè)非零特征值
 9. 5  環(huán)面
 9. 6  多項(xiàng)式曲線
 9. 6. 1  貝塞爾曲線
 9. 6. 2  B樣條曲線
 9. 6. 3  非均勻有理B樣條曲線
 9. 7  多項(xiàng)式曲面
 9. 7. 1  貝塞爾曲面
 9. 7. 2  B樣條曲面
 9. 7. 3  非均勻有理B樣條曲面
 第10章  三維距離
 10. 1  導(dǎo)言
 10. 2  點(diǎn)到線形對(duì)象的距離
 10. 2. 1  點(diǎn)到直線或射線的距離
 10. 2. 2  點(diǎn)到折線的距離
 10. 3  點(diǎn)到平面對(duì)象的距離
 10. 3. 1  點(diǎn)到平面的距離
 10. 3. 2  點(diǎn)到三角形的距離
 10. 3. 3  點(diǎn)到矩形的距離
 10. 3. 4  點(diǎn)到多邊形的距離
 10. 3. 5  點(diǎn)到圓或圓盤的距離
 10. 4  點(diǎn)到多面體的距離
 10. 4. 1  一般問題
 10. 4. 2  點(diǎn)到有向有界箱的距離
 10. 4. 3  點(diǎn)到正交平截體的距離
 10. 5  點(diǎn)到二次曲面的距離
 10. 5. 1  點(diǎn)到一般二次曲面的距離
 10. 5. 2  點(diǎn)到橢球面的距離
 10. 6  點(diǎn)到多項(xiàng)式曲線的距離
 10. 7  點(diǎn)到多項(xiàng)式曲面的距離
 10. 8  線形對(duì)象之間的距離
 10. 8. 1  直線與直線之間的距離
 10. 8. 2  線段／線段. 直線／射線. 直線／線段. 射線／射線. 射線／線段之間的距離
 10. 8. 3  計(jì)算線段到線段的距離的另一種方法
 10. 9  線形對(duì)象與三角形. 矩形. 四面體和有向有界箱之間的距離
 10. 9. 1  線形對(duì)象到三角形的距離
 10. 9. 2  線形對(duì)象到矩形的距離
 10. 9. 3  線形對(duì)象到四面體的距離
 10. 9. 4  線形對(duì)象到有向有界箱的距離
 10. 10  直線到二次曲面的距離
 10. 11  直線到多項(xiàng)式曲面的距離
 10. 12  GJK算法
 10. 13  雜項(xiàng)
 10. 13. 1  直線與平面曲線之間的距離
 10. 13. 2  直線與平面實(shí)心物體之間的距離
 10. 13. 3  平面曲線之間的距離
 10. 13. 4  曲面上的測(cè)地距離
 第11章  三維相交
 11. 1  線形對(duì)象與平面對(duì)象的相交
 11. 1. 1  線形對(duì)象與平面的相交
 11. 1. 2  線形對(duì)象與三角形的相交
 11. 1. 3  線形對(duì)象與多邊形的相交
 11. 1. 4  線形對(duì)象與圓盤的相交
 11. 2  線形對(duì)象與多面體的相交
 11. 3  線形對(duì)象與二次曲面的相交
 11. 3. 1  線形對(duì)象與一般二次曲面的相交
 11. 3. 2  線形對(duì)象與球面的相交
 11. 3. 3  線形對(duì)象與橢球面的相交
 11. 3. 4  線形對(duì)象與圓柱面的相交
 11. 3. 5  線形對(duì)象與圓錐面的相交
 11. 4  線形對(duì)象與多項(xiàng)式曲面的相交
 11. 4. 1  代數(shù)曲面
 11. 4. 2  自由形態(tài)曲面
 11. 5  平面對(duì)象之間的相交
 11. 5. 1  兩個(gè)平面之間的相交
 11. 5. 2  三個(gè)平面之間的相交
 11. 5. 3  三角形與平面的相交
 11. 5. 4  三角形與三角形的相交
 11. 6  平面對(duì)象與多面體的相交
 11. 6. 1  三角網(wǎng)格
 11. 6. 2  一般多面體
 11. 7  平面對(duì)象與二次曲面的相交
 11. 7. 1  平面與一般二次曲面的相交
 11. 7. 2  平面與球面的相交
 11. 7. 3  平面與圓柱面的相交
 11. 7. 4  平面與圓錐面的相交
 11. 7. 5  三角形與圓錐面的相交
 11. 8  平面對(duì)象與多項(xiàng)式曲面的相交
 11. 8. 1  埃爾米特曲線
 11. 8. 2  幾何定義
 11. 8. 3  計(jì)算曲線
 11. 8. 4  算法
 11. 8. 5  實(shí)現(xiàn)要點(diǎn)
 11. 9  二次曲面之間的相交
 11. 9. 1  一般相交問題
 11. 9. 2  橢球面
 11. 10  多項(xiàng)式曲面之間的相交
 11. 10. 1  細(xì)分方法
 11. 10. 2  格子評(píng)測(cè)
 11. 10. 3  解析方法
 11. 10. 4  步進(jìn)方法
 11. 11  軸分離方法
 11. 11. 1  固定凸多面體的分離
 11. 11. 2  運(yùn)動(dòng)凸多面體的分離
 11. 11. 3  固定凸多面體的交集
 11. 11. 4  固定凸多面體的接觸集
 11. 12  雜項(xiàng)
 11. 12. 1  有向有界箱與正交平截體的相交
 11. 12. 2  線形對(duì)象與軸對(duì)齊有界箱的相交
 11. 12. 3  線形對(duì)象與有向有界箱的相交
 11. 12. 4  平面與軸對(duì)齊有界箱的相交
 11. 12. 5  平面對(duì)象與有向有界箱的相交
 11. 12. 6  軸對(duì)齊有界箱之間的相交
 11. 12. 7  有向有界箱之間的相交
 11. 12. 8  球面與軸對(duì)齊有界箱的相交
 11. 12. 9  圓柱面之間的相交
 11. 12. 10  線形對(duì)象與環(huán)面的相交
 第12章  其他三維問題
 12. 1  點(diǎn)在平面上的投影
 12. 2  向量在平面上的投影
 12. 3  直線與平面的夾角
 12. 4  兩平面之間的夾角
 12. 5  以一條直線為法線并通過一給定點(diǎn)的平面
 12. 6  三點(diǎn)決定的平面
 12. 7  兩條直線之間的夾角
 第13章  關(guān)于計(jì)算幾何學(xué)的話題
 13. 1  二維空間分區(qū)二叉樹
 13. 1. 1  多邊形的空間分區(qū)二叉樹表示
 13. 1. 2  最小分解與平衡樹
 13. 1. 3  用空間分區(qū)二叉樹進(jìn)行點(diǎn)在多邊形內(nèi)的檢測(cè)
 13. 1. 4  用空間分區(qū)二叉樹分解線段
 13. 2  三維空間分區(qū)二叉樹
 13. 2. 1  多面體的空間分區(qū)二叉樹表示
 13. 2. 2  最小分解與平衡樹
 13. 2. 3  用空間分區(qū)二叉樹進(jìn)行點(diǎn)在多面體內(nèi)的檢測(cè)
 13. 2. 4  用空間分區(qū)二叉樹分解線段
 13. 2. 5  用空間分區(qū)二叉樹分解凸多邊形
 13. 3  點(diǎn)在多邊形內(nèi)的檢測(cè)
 13. 3. 1  點(diǎn)在三角形內(nèi)的檢測(cè)
 13. 3. 2  點(diǎn)在凸多邊形內(nèi)的檢測(cè)
 13. 3. 3  點(diǎn)在一般多邊形內(nèi)的檢測(cè)
 13. 3. 4  點(diǎn)在多邊形內(nèi)的快速檢測(cè)法
 13. 3. 5  柵格方法
 13. 4  點(diǎn)在多面體內(nèi)的檢測(cè)
 13. 4. 1  點(diǎn)在四面體內(nèi)的檢測(cè)
 13. 4. 2  點(diǎn)在凸多面體內(nèi)的檢測(cè)
 13. 4. 3  點(diǎn)在一般多面體內(nèi)的檢測(cè)
 13. 5  與多邊形有關(guān)的布爾運(yùn)算
 13. 5. 1  抽象運(yùn)算
 13. 5. 2  兩種基礎(chǔ)運(yùn)算
 13. 5. 3  使用空間分區(qū)二叉樹的布爾運(yùn)算
 13. 5. 4  其他算法
 13. 6  與多面體有關(guān)的布爾運(yùn)算
 13. 6. 1  抽象運(yùn)算
 13. 6. 2  使用空間分區(qū)二叉樹的布爾運(yùn)算
 13. 7  凸包
 13. 7. 1  二維凸包
 13. 7. 2  三維凸包
 13. 7. 3  高維凸包
 13. 8  德洛奈三角剖分
 13. 8. 1  維增量構(gòu)建
 13. 8. 2  一般維度增量構(gòu)建
 13. 8. 3  用凸包實(shí)現(xiàn)構(gòu)建
 13. 9  多邊形分解
 13. 9. 1  一個(gè)簡(jiǎn)單多邊形的可見性圖
 13. 9. 2  三角剖分
 13. 9. 3  水平分解三角剖分
 13. 9. 4  凸分解
 13. 10  外接球與內(nèi)切球
 13. 10. 1  外接球
 13. 10. 2  內(nèi)切球
 13. 11  點(diǎn)集的最小區(qū)域
 13. 11. 1  最小面積矩形
 13. 11. 2  最小體積箱體
 13. 11. 3  最小面積的圓
 13. 11. 4  最小體積的球
 13. 11. 5  雜項(xiàng)
 13. 12  面積和體積測(cè)量
 13. 12. 1  二維多邊形的面積
 13. 12. 2  三維多邊形的面積
 13. 12. 3  多面體的體積
 附錄A  數(shù)值方法
 附錄B  三角幾何
 附錄C  幾何圖元基礎(chǔ)公式
 參考文獻(xiàn)
 圖索引
 表索引