第1章计算理论基础1

1.1集合的基本概念1

1.1.1集合的定义1

1.1.2集合的表示1

1.1.3集合间的关系1

1.1.4集合的运算2

1.2关系3

1.2.1二元关系3

1.2.2二元关系的性质3

1.2.3等价关系3

1.2.4递归定义与归纳证明4

1.3图与树6

1.3.1无向图7

1.3.2有向图7

1.3.3树8

1.3.4二叉树8

1.4三个重要概念9

习题10

第2章文法与语言13

2.1启示13

2.2文法的形式定义14

2.3文法的构造15

2.4文法的Chomsky体系16

习题18

第3章上下文无关文法及其语言20

3.1上下文无关文法20

3.1.1派生与派生树20

3.1.2文法的二义性23

3.2文法和语言的讨论24

3.3句法分析27

3.3.1最左派生和不确定性27

3.3.2文法图28

3.3.3广度优先自顶向下句法分析29

3.3.4深度优先自顶向下分析30

3.3.5自底向上分析32

目录形式语言与自动机3.4上下文无关文法的化简38

3.4.1无用符号38

3.4.2消除ε产生式38

3.4.3消除单一产生式39

3.4.4消除左递归40

3.5Chomsky范式44

3.6Greibach范式46

习题48

第4章有穷状态自动机54

4.1语言的识别54

4.2有穷状态自动机的形式定义55

4.3确定的有穷自动机55

4.4状态转换图57

4.5不确定的有穷自动机58

4.6NFA与DFA的等价60

4.7带空转移的NFA63

4.8εNFA的确定化65

4.9DFA最小化66

习题70

第5章正则语言和正则文法73

5.1正则表达式73

5.1.1正则表达式的定义73

5.1.2正则语言73

5.2有穷自动机和正则语言74

5.2.1正则表达式到有穷自动机74

5.2.2有穷自动机到正则表达式76

5.3正则文法和有穷自动机78

5.3.1正则文法78

5.3.2正则文法与NFA81

习题85

第6章正则语言的性质87

6.1正则语言的封闭性87

6.1.1简单运算的封闭性87

6.1.2其他运算的封闭性88

6.2非正则语言的识别91

6.2.1鸽巢原理92

6.2.2泵引理92

6.3Myhill Nerode定理94

6.4正则语言的判定算法99

习题100

第7章下推自动机与上下文无关文法101

7.1非确定型下推自动机101

7.1.1下推自动机的定义101

7.1.2下推自动机接受的语言102

7.2下推自动机与上下文无关文法104

7.2.1上下文无关语言相应的下推自动机104

7.2.2下推自动机与相应的上下文无关文法106

7.3确定型下推自动机109

7.4双栈自动机110

习题111

第8章上下文无关语言的性质114

8.1上下文无关文法的泵引理114

8.2上下文无关语言的封闭性116

8.3上下文无关语言的可判定性118

习题118

第9章图灵机120

9.1标准图灵机120

9.1.1图灵机的形式定义120

9.1.2图灵机识别器122

9.1.3图灵机转换器124

9.2完成复杂任务的图灵机126

习题128

第10章图灵机的其他模型130

10.1带不动选择图灵机130

10.2多道图灵机131

10.3单向无穷带图灵机132

10.4离线图灵机133

10.5多带图灵机134

10.6多头图灵机137

10.7非确定型图灵机138

10.8线性界限自动机140

习题141

第11章其他计算模型143

11.1递归函数143

11.1.1递归函数143

11.1.2递归函数的扩展理解146

11.2波斯特系统148

11.3重写系统149

11.3.1矩阵文法149

11.3.2马尔可夫算法150

习题151

参考文献152

第1章绪论1

1.13D数字几何处理1

1.23D模型数据获取2

1.33D数字模型的表示3

1.3.1三角网格模型3

1.3.2点模型4

1.43D数字模型的预处理5

1.4.1光顺去噪5

1.4.2模型配准6

1.4.3模型修复6

1.53D数字模型建模7

1.5.1曲面重构7

1.5.2表面几何属性分析8

1.5.3重采样8

1.5.4特征提取9

1.5.5骨架提取10

1.5.6模型分片11

1.5.7参数化11

1.63D数字模型编辑12

1.6.1几何造型12

1.6.2融合13

1.6.3变形14

1.6.4渐变15

1.7本书的组织结构15

第2章曲面重建和微分属性求解17

2.1网格曲面重构17

2.1.1基于点邻域平坦度的网格重构算法18

2.1.2基于点邻域几何形态的网格重构算法25目录数字几何处理的若干问题研究进展2.2隐式曲面重构34

2.2.1MLS曲面重构35

2.2.2RBF曲面重构37

2.3网格模型微分属性求解39

2.3.1法向量投票算法40

2.3.2基于简化网格的曲率计算40

2.4点模型微分属性求解42

2.4.1PCA法42

2.4.2MLS法42

2.5本章小结45

第3章3D数字模型的预处理46

3.1光顺去噪46

3.1.1典型的光顺去噪方法46

3.1.2基于相似性的点模型去噪47

3.2配准53

3.2.1引言54

3.2.2基于ICP算法的点云配准54

3.3几何修复59

3.3.1引言59

3.3.2网格模型孔洞修补的基本算法60

3.3.3基于边扩展的网格复杂孔洞修补61

3.3.4基于顶点聚类的网格任意孔洞修补64

3.3.5点模型纹理和几何修复的统一方法68

3.4本章小结75

第4章3D数字模型建模77

4.1曲面重采样77

4.1.1引言77

4.1.2自适应分片点模型简化78

4.1.3基于相似性的点模型简化86

4.1.4点模型的采样点加密92

4.2模型骨架提取93

4.2.1引言93

4.2.2基于可见反力场的点模型骨架提取94

4.3模型参数化100

4.3.1引言100

4.3.2应用边收缩的网格参数化102

4.4模型分片112

4.4.1引言112

4.4.2基于参数化的网格分割112

4.4.3网格模型结构部件的分割119

4.4.4网格模型四边形区域的划分126

4.4.5多分辨率层次点模型分片136

4.5本章小结144

第5章3D数字模型编辑146

5.1模型变形146

5.1.1引言146

5.1.2网格变形的理论基础155

5.1.3保持几何特征的均值骨架子空间网格变形160

5.1.4基于动态轮廓模型的微分域网格变形166

5.1.5特征保持的大规模点模型自由变形173

5.1.6骨架驱动的点模型皮肤局部变形186

5.2形状插值194

5.2.1引言195

5.2.2基于球面参数化的点模型渐变196

5.2.3基于顶点变形梯度的点模型形状插值202

5.3基于顶点变形梯度的点模型变形传输213

5.3.1引言213

5.3.2相关工作215

5.3.3变形传输的整体框架216

5.3.4点模型的变形传输216

5.3.5实验结果221

5.4拖曳式点模型融合224

5.4.1引言224

5.4.2点模型融合处理框架225

5.4.3两种交互方式226

5.4.4构建融合过渡区域228

5.4.5融合后处理228

5.4.6实验结果及讨论229

5.5本章小结231

第6章数字几何处理技术方法总结234

6.1数字几何处理234

6.2曲面重建和微分属性求解235

6.2.1网格曲面重构235

6.2.2隐式曲面重构236

6.2.3微分属性求解236

6.33D数字模型的预处理237

6.3.1光顺去噪237

6.3.2配准237

6.3.3模型修复237

6.43D数字模型建模238

6.4.1曲面重采样238

6.4.2骨架提取239

6.4.3参数化239

6.4.4模型分片239

6.53D数字模型编辑240

6.5.1模型变形240

6.5.2形状插值241

6.5.3变形传输242

6.5.4模型融合242

6.6发展趋势242

参考文献244