Delaunay方法三维建模

摘要

3维建模技术在建筑，地质地形勘测，医学图像建模，动画设计等各方面都有广泛的应用. 1个3维模型的建立过程包括3维原始数据的获取、去除噪声、曲面拼接、修补“洞”，最终得到1个可以在计算机上显示的具有3维特征的网格. 3维可视化技术包括表面绘制技术和体绘制技术。由于将已有的3维模型显示在计算机上的技术已经很成熟，所以可视化技术的主要问题在于3维建模.

使用Delaunay方法来建模，由于Delaunay3角是尽量接近于等边3角形的，所以用这种方法建的网格会比较均匀，显示图像的时候视觉效果就是整个图像很匀称，不会出现粗细不均或者漏洞百出的情况。关键词：Delaunay ；3维建模；4面体网格；局部搜索。

Abstract

Three-dimension modeling technology is widely applied in the fields of architecture, geology and topography survey, medicine picture modeling, and cartoon design etc. The process of three-dimension modeling includes the following steps: first, obtaining three-dimension original data; second, removing yawp; third, putting curve surface together; fourth, mending “hole”; at last, reseau characterized by three-dimension will appear in PC. Three-dimension videotechnology consists of surface protracting technology and body protracting technology.Since the technology that making three-dimension model show in PC is proficient, the main problem of videotechnology lies in three-dimension modeling

Because Delaunay triangle is nearly equilateral triangle, modeling reseau with the method of Delaunay will be relatively well-proportioned. The whole image will looks shapely, not snatchy and inaccurate.

This paper includes five chapters. First chapter is Introduction, which introduce the background , recent development and the potential development.Chapter two gives a brief introduction of establishing triangle meshwork in two-dimension space. Chapter three explains every step to establish four-dimension reseau specifically, including demonstration and flow chart. Chapter Four lists the results with series of charts to test the method. Furthermore, nine dots are chosen. In the process of establishing meshwork with those nine dots, some special problems arise from Tsung-Pao Fang. That is to say , even if more dots are chosen, there are only the repetition of the above problems. The meshwork results are obtained from the later pictures. They clearly show the structure of four-dimension reseau and some meshwork results of shell data. The reason why the whole results are not achieved is that there are too many circumstances in which five or more dots share the same orb. In this case, the principle Delaunay is not in point any more, then the process of establishing meshwork will be intermitted. Chapter Five discusses some problems arising from the program and some difficulties in my thesis.

Keywords: Delaunay;three-dimension modeling; four-dimension reseau;partly search;

目录

1 前言................................................................................................................................................... 1

2 Delaunay 3角剖分的基本原理...................................................................................................... 2

2.1 相关知识…….......................................................................…………….……………………….... 2

2.1.1 Voronoi 图............................................................................................................................... 22.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的。

目前国际上对立体仿真建模的研究最为关注的是医学方面的应用。但是用于医学仿真操作的模型，必须具有和人体组织完全相同的形状和结构，在手术刀切割等外界条件下，才能够做出完全类似于真实人体的反应和形变，因为其模拟的结果可以说是性命攸关的大事，所以要求有相当高的精度。

这项工作有着良好的发展和应用的前景。如果立体建网的技术成熟起来，基于真实物体的仿真模型将会被应用到生活的各个方面。不仅可以做工程和医学仿真，随着网上购物越来越走入人们的生活，我们可以某些商品建成可视又可“触”的模型，人们在选购的时候不仅可以看到商品的样子，还可以用鼠标和键盘对商品模型进行各种操作，看它的弹性、柔软度等性质，从而用更直观，更便捷的方法来了解商品的性能，而不是对着大篇幅的数字指标发呆。这种技术还可以同大型场景相结合，让人们能够在风景胜地、灾难现场、文物古迹等的虚拟现实世界漫游，足不出户就可以有身临其境的感受，甚至去“接触”物体。如果我们能够建立仿真的地理模型，就可以做地震、暴雨等的灾难模拟实验，用来做灾难预测和为维修提供理论依据，从而节省大量不必要的开支。3维仿真模型的应用领域10分广阔，伴随着计算机走进千家万户的脚步，网络将在我们的生活扮演越来越重要的角色，也许有1天，你会说：断网了可让我怎么活，电脑和网络就像今天的“电”1样重要，到那个时候网络上的模型都能很好的模拟真实世界的物体，3维仿真建模的技术才真正有了用武之地。

2 Delaunay3角剖分的基本原理

3角剖分的定义：若对平面剖分的所有边界区域都是3角形，则这种平面剖分称为3角剖分。3角剖分是计算

[1]