2.1.2 Delaunay 3角剖分................................................................................................................. 3
2.2 2维空间建Delaunay 3角网的基本思想....................................................................................... 4
2.2.1 数据点的预处理..................................................................................................................... 4
2.2.2 建立起始的3角形................................................................................................................. 6
2.2.3 建立3角网........................................................................................................................... 7
3 Delaunay 4面体网格的构建.......................................................................................................... 8
3.1 与算法相适应的数据结构.............................................................................................................. 8
3.2 3维平面构建Delaunay 4面体网格的算法................................................................................. 13
3.2.1 数据的输入和预处理........................................................................................................... 13
3.2.2 整个算法的'起始点 .......................................................................................................... 14
3.2.3 搜索与 距离最近的点 .................................. ............................................................. 14
3.2.4 寻找满足Delaynay法则的第3个点 ............................... .............................................. 15
3.2.5 已知1个3角面片，搜索第4个点..................................................................................... 16
3.2.6 构建Delaunay4面体网格.................................................................................................... 17
4  实验结论.....................................................................................................................20
5  讨论........................................................................................................................................................ 22
6  参考文献..........................................................................................................................................24
7  致谢..................................................................................................................................................24
附录............................................................................................................................................................25

1  前 言

3维建模技术在建筑，地质地形勘测，医学图像建模，动画设计等各方面都有广泛的应用。在进行某项工程设计，或者医疗操作时，如果能建立计算机仿真平台，通过这个平台的仿真实验来验证设计方案的可行性及对此操作的成功率指标进行评估的话，不仅可以提高设计计划的成功率，而且可以节省设计的时间和资金。通过仿真还可以对设计方案和有关参数进行验证和修正，对于医疗方案的仿真，更是提高了手术治疗的成功率，维护了病人的生命财产。
1个3维模型的建立过程包括：3维原始数据的获取、去除噪声、曲面拼接、修补“洞”，最终得到1个可以在计算机上显示的具有3维特征的网格。3维可视化技术包括表面绘制技术和体绘制技术。由于将已建好的3维模型显示在计算机上的技术已经很成熟，所以可视化技术的主要问题在于3维建模。表面绘制是抽取出3维原始数据中的表面数据，然后将模型的表面信息显示在计算机上；体绘制不需要对3维原始数据作太多处理，由于这种方法建立的模型不仅有物体表面的信息，还包含图形内部点的信息，甚至各点之间的相互作用或者连接关系，所以用体绘制方法得到的模型可以用来模拟物体的受力形变过程。目前国际上表面绘制技术已经很成熟了，随之出现的各种软件，如3d studio max等，都可以作图像的表面建模，既方便快捷，效果也不错。但是，在许多作仿真用途的模型中，特别是医用模型，往往需要模型能够真实地模仿实际物体受到外界干扰时会如何发生形变，这就需要把扫描对象物体得到的3维数据点云用立体网格（区别于3角网或者多边形网格这种表面建网得到的网格）来连接建网。建网的目的是要把3维图形无论表面还是内部的点连接起来，用有限的连接关系建立起包括所有点的网络，没有任何点被遗漏也尽量没有冗余。当物体受外界作用发生形变的时候，因为数据点之间的联系是确定的，所以作用范围内的点及其相邻点的受力情况和运动过程是可以通过简单的力学计算得到的，因此我们可以应用这样的模型来做各种力学和医学等仿真。截止到目前为止，还没有现成的软件能够做这件事情。国际上也还没有成熟的算法。我在毕业设计中所做的事情属于体绘制的1部分，即基于3维数据点云建立立体网格，所用的方法是基于Delaunay3角剖分原理建立Delaunay4面体网格。这种方法的优点是所建立的4面体与其他方法相比最接近正4面体，形状最规则，且剖分的结果是唯1的。