第1章 Minkowski和的国内外研究现状 1
1.1 Minkowski和定义 1
1.2 Minkowski和算法研究现状 1
1.3 碰撞检测算法研究现状 4
1.4 本章小结 5
参考文献 5
第2章 Minkowski和算法基础知识 12
2.1 数学基础 12
2.1.1 几何定义 12
2.1.2 空间解析几何基础知识 15
2.1.3 线性代数基础 15
2.1.4 群论基础 16
2.2 Minkowski和的性质 16
2.3 工作空间和参数空间 17
2.3.1 工作空间的概念 17
2.3.2 参数空间的概念 17
2.3.3 禁止C空间与自由C空间 17
2.3.4 几何对称镜像的概念 18
2.4 三维物体常用的描述方法 19
2.4.1 八叉树表示法 19
2.4.2 扫描表示法 19
2.4.3 边界表示法 19
2.4.4 半空间表示法 20
2.4.5 CSG表示法 20
2.4.6 高斯映射方法 20
2.5 双向链接边表 21
2.5.1 相关概念 21
2.5.2 顶点记录 21
2.5.3 半边记录 22
2.5.4 面记录 23
2.5.5 应用举例 23
2.5.6 扩展的邻接表 25
2.6 Voronoi图 25
2.6.1 平面点的Voronoi多边形 25
2.6.2 Voronoi图 26
2.6.3 Voronoi图的对偶图 26
2.6.4 Voronoi图的性质 26
2.6.5 Delaunay三角形 27
2.7 算法的预备知识 27
2.7.1 算法的时间复杂度 28
2.7.2 算法的空间复杂度 28
2.8 本章小结 29
参考文献 29
第3章 基于正四面体高斯映射的凸多面体Minkowski和算法 31
3.1 引言 31
3.2 相关定义 32
3.3 正四面体高斯映射 32
3.3.1 正四面体高斯映射的定义 32
3.3.2 空间坐标转换关系 33
3.4 基于正四面体高斯映射的Minkowski和计算方法 35
3.4.1 数据结构及相关信息 35
3.4.2 算法思想 38
3.4.3 算法描述 39
3.4.4 算法分析 42
3.5 三角形内简单平面凸划分的叠置算法 42
3.5.1 基本概念 43
3.5.2 数据结构 44
3.5.3 叠置算法 44
3.5.4 算法分析 50
3.6 本章小结 50
参考文献 51
第4章 直接映射的凸多面体Minkowski和算法 52
4.1 引言 52
4.2 相关定义及理论 53
4.3 直接映射方法 55
4.3.1 空间参数坐标系的建立 56
4.3.2 菱形多面体高斯映射方法 56
4.3.3 正三角形垂直映射方法 60
4.3.4 算法正确性验证 61
4.3.5 正三角形平面划分叠置遍历算法 62
4.3.6 平移映射的凸多边形Minkowski和算法 67
4.3.7 算法描述 70
4.3.8 算法分析 71
4.4 本章小结 72
参考文献 73
第5章 基于分裂点的Minkowski和算法 74
5.1 引言 74
5.2 基于分裂点的平面凸多边形Minkowski和算法 74
5.2.1 基于分裂点的凸多边形Minkowski和算法理论基础 74
5.2.2 基于分裂点的凸多边形Minkowski和算法分析 78
5.3 基于分裂点的空间凸多面体Minkowski和算法 81
5.3.1 基于分裂点的凸多面体Minkowski和算法理论基础 81
5.3.2 基于分裂点的Minkowski和算法分析 85
5.4 本章小结 88
参考文献 88
第6章 基于几何体代数结构的凸多面体Minkowski和计算方法 91
6.1 引言 91
6.2 多面体的代数结构 91
6.2.1 多面体代数结构的构建 91
6.2.2 多面体代数结构的性质 92
6.2.3 多面体各顶点极点区域结构 94
6.3 基于凸多面体代数结构的Minkowski和计算方法建模 96
6.3.1 符号说明 96
6.3.2 计算方法建模理论分析 96
6.4 凸多面体的Minkowski和算法分析 101
6.4.1 数据结构 101
6.4.2 算法伪代码 104
6.4.3 算法时间复杂度分析 105
6.5 本章小结 107
参考文献 107
第7章 凹多面体的Minkowski和算法 109
7.1 引言 109
7.2 凹多面体的四面体剖分算法 110
7.2.1 算法数据结构 111
7.2.2 算法思想 111
7.2.3 多面体顶点凹凸性判断算法 112
7.2.4 Delaunay三角剖分的算法 113
7.2.5 凸剖分算法复杂度分析 114
7.3 基于成功回路的凹多面体凸剖分算法 114
7.3.1 相关定义与定理 114
7.3.2 算法思想 116
7.3.3 最优回路生成算法 116
7.3.4 算法描述 117
7.3.5 算法分析 118
7.4 基于距离场的Minkowski子和合并算法 118
7.4.1 相关定义 120
7.4.2 网格点到三角面片的最短距离算法 121
7.4.3 距离场符号生成算法 124
7.4.4 改进的距离场生成算法 125
7.5 基于改进的移动立方体Minkowski子和合并算法 126
7.5.1 相关定义 126
7.5.2 传统的移动立方体法 127
7.5.3 改进的移动立方体算法 129
7.5.4 改进的移动立方体算法描述 136
7.5.5 改进的移动立方体算法分析 138
7.6 本章小结 139
参考文献 139
第8章 涉及凹多面体及凹多边形的Minkowski和计算方法建模与分析 143
8.1 引言 143
8.2 基于几何体代数结构的凹多面体与凸多面体Minkowski和计算方法建模与分析 144
8.2.1 简单凹多面体 145
8.2.2 基于几何体代数结构的凹多面体与凸多面体Minkowski和计算方法建模 145
8.2.3 算法描述与算法分析 152
8.3 基于多边形代数结构的凹多边形Minkowski和计算方法 159
8.3.1 平面多边形代数结构 159
8.3.2 基于多边形代数结构的凹多边形Minkowski和计算方法建模理论 160
8.3.3 算法描述与分析 163
8.4 本章小结 166
参考文献 167
第9章 基于Minkowski和的飞机大部件自动对接 169
9.1 概述 169
9.2 自动对接技术设计 170
9.2.1 设计简述 170
9.2.2 坐标系建立 171
9.2.3 构造新的Minkowski和且分类 171
9.2.4 原点与Minkowski和的位置关系简述 171
9.2.5 精确位置关系的算法描述 172
9.2.6 自动对接详细设计 175
9.3 机翼自动对接虚拟仿真 177
9.3.1 Minkowski和算法实验分析 177
9.3.2 OpenGL的框架搭建和环境配置 180
9.3.3 三维建模及装配仿真 181
9.4 本章小结 188
参考文献 188
第10章 基于Minkowski和的机械零件自动装配技术研究 190
10.1 引言 190
10.2 自动装配技术理论基础 191
10.2.1 齿轮状凹多面体的凸分解算法 191
10.2.2 类齿轮状凹多面体的补形算法 194
10.3 基于Minkowski和的零件装配设计 197
10.3.1 指导装配理论基础 197
10.3.2 装配空间建立 199
10.3.3 最小距离矢量算法 201
10.3.4 自动装配设计流程 204
10.4 零件自动装配虚拟仿真实验 206
10.4.1 实验对象简介 206
10.4.2 算法实验环境 207
10.4.3 仿真数据的精度问题 209
10.4.4 装配仿真实验 210
10.5 本章小结 216
参考文献 217