张姝瑶
网络教育毕业论文
论文题目：基于C#的三维几何模型的算法与实现
学生姓名：张姝瑶
指导教师：张文艺
学科专业：计算机科学与技术
学号：14095210914002
学习中心：山西运城学院稷山师范分院奥鹏学习中心[28]
东北师范大学远程与继续教学育院
2016年5月
独创性声明
本人对本文有以下声明：
1.本人所呈交的论文是在指导教师指导下进行的研究工作及取得的研究成果，已按相关要求及时提交论文提纲、初稿，最终形成本文；
2.在撰写过程中主动与导师保持密切联系，及时接受导师的指导；
3.本文符合相关格式要求，除文中特别加以标注的地方外，论文中单篇引用他人已经发表或撰写过的研究成果不超过800字；
4.本人本文成稿过程中不存在他人代写、抄袭或和他人论文雷同的现象；
论文作者签名：张姝瑶
日期：2016 年05 月
论文版权使用授权书
本论文作者完全了解东北师范大学有关保留、使用论文的规定，即：东北师范大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权东北师范大学可以将论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编论文。
论文作者签名：张姝瑶指导教师签名：
日期：2016 年05 月日期：年月
摘要
目前，随着影视动画、3D网络游戏、虚拟现实等技术正在高速发展，三维几何模型在这些领域里应用得越来越广泛，构造和处理的三维几何模型也越来越复杂。为了解决模型复杂度，同时减轻建模的工作量，提高工作效率以及制作成本，三维几何模型的细化技术应运而生。
本课题使用的三维模型的细化是基于网格离散曲面的一种表示方法，它可以从任意拓扑网格构造光滑曲面。细化方法的基本思想是：定义一个网格序列的极限，网格序列是采用一定的细分规则（一般是加权平均），在给定的初始网格中插入新的顶点，从而不断细化出新的网格，重复运用细分规则，在极限时，该网格即收敛于一个光滑的曲线或者曲面。
本论文分别探讨研究了Loop、Sqrt3、Modified Butterfly三种不同的细分模式。并对这三种算法做了分析，研究和对比。
关键词：三维几何模型；细分；算法；
目录
一、三维几何模型概述 (2)
1.1 三维几何模型的基本概念 (5)
1.2 三维几何模型的应用 (6)
二、三维几何模型细化技术 (8)
2.1 网格细分算法的产生与发展 (9)
2.2 三维几何模型细化概念 (9)
2.3 三维几何模型细化意义 (10)
2.4 三维几何模型细化算法 (10)
2.5 程序设计 (11)
三、结论 (11)
致谢 (12)
主要参考资料 (12)
一、三维几何模型概述
1.1 三维几何模型的基本概念
三维几何模型是指使用计算机和特殊三维软件创造出来的，使用几何概念描述物理或者数学物体形状，是使立体像对同名光线对相交所构成的与实地相似的三维模型。它是物体的三维多边形表示，通常用计算机或者其它视频设备进行显示。显示的物体是可以是现实世界的实体，也可以是虚构的东西，既可以小到原子，也可以大到很大的尺寸。任何物理自然界存在的东西都可以用三维几何模型表示。三维几何模型可以手工生成，也可以按照一定的算法生成。
三维几何模型本身是不可见的，可以根据简单的线框在不同细节层次渲染的或者用不同方法进行明暗描绘。但是，许多三维几何模型使用纹理进行覆盖。纹理就是一个图像，但是它可以让模型更加细致并且看起来更加真实。例如，一个人的三维几何模型如果带有皮肤与服装的纹理那么看起来就比简单的单色模型或者是线框模型更加真实。
除了纹理之外，其它一些效果也可以用于三维模型以增加真实感。例如可以调整曲面法线以实现它们的照亮效果，一些曲面可以使用凸凹纹理映射方法以及其它一些立体渲染的技巧。
三维几何模型广泛用于计算机图形学、计算机辅助设计、计算机辅助制造以及医疗图像处理等许多应用领域。
1.2 三维几何模型的应用
随着计算机三维影像技术的不断发展，三维图形技术越来越被人们所看重，三维几何模型的应用范围也越来越广。从简单到复杂，从静态到动态。比如说在工程设计和仿真,产品原型和生产,外科手术规划、假肢的设计、架构、地质、艺术、电影、动漫和视频游戏等领域都得到了广泛的应用。比如说，在医疗行业使用它们制作器官的精确模型；电影行业将它们用于活动的人物、物体以及现实电影；视频游戏产业将它们作为计算机与视频游戏中的资源；在科学领域将它们作为化合物的精确模型；建筑业将它们用来展示提议的建筑物或者风景表现；工程界将它们用于设计新设备、交通工具、结构以及其它应用领域；在最近几十年，地球科学领域开始构建三维地质模型。下面将介绍三维几何模型的典型应用。
1.3、三维几何模型在影视动画中的应用
三维动画又称3D动画，是近年来随着计算机软硬件技术的发展而产生的一新兴技术。三维动画软件在计算机中首先建立一个虚拟的世界，设计师在这个虚拟的三维世界中按照要表现的对象的形状尺寸建立模型以及场景，再根据要求设定模型的运动轨迹、虚拟摄影机的运动和其它动画参数，最后按要求为模型赋上特定的材质，并打上灯光。当这一切完成后就可以让计算机自动运算，生成最后的画面。
说起三维几何模型在影视动画中的应用，不得不说就是以三维几何模型为基础的3D
动画片，3D动画片中的所有场景及人物都是由三维几何模型构成的。三维动画从简单的几何体模型到复杂的人物模型，单个的模型展示，到复杂的场景如道路、桥梁、隧道、市政、小区等线型工程和场地工程的景观设计表现的淋漓尽致。由于三维几何模型在动画片中的使用越来越多，动画片的制作也由传统的2D向3D迅猛的发展。由于3D动画的出现，使得动画行业又进入了一个新的历史时期。《极地快车》、《冰河世纪》、《功夫熊猫》、《怪物史瑞克》等3D动画都取得了巨大的成功。
在中国，第一部3D动画片《秦时明月》，是中国首部武侠动漫系列剧，于2007年春节期间在全国各地同步播映。作为中国第一部大型武侠CG/3D（电脑三维动画）动漫系列剧，《秦时明月》融武侠、奇幻、历史于一体，引领观众亲历两千年前风起云涌、瑰丽多姿的古中国世界，在浓郁的“中国风”中注入了鲜明的时代感。
随着影像技术的不断发展，三维几何模型不但在动画领域得到了广泛的应用，在影视作品中也得到越来越多人的肯定，比如说在《阿凡达》、《泰坦尼克号》等电影中的一些场景都是由三维几何模型构成的。
相对于实拍，利用三维几何模型拥有以下几点优势：
1、利用三维几何模型制作的三维动画能够完成实拍不能完成的镜头；
2、拍摄与制作不受天气季节等因素影响；
3、可修改性较强，质量要求更易受到控制；
4、实拍成本过高的镜头可通过三维几何模型制作三维动画实现以降低成本；
5、实拍有危险性的镜头可通过三维几何模型制作动画完成；
6、无法重现的镜头可通过三维几何模型制作三维动画来模拟完成；
7、能够对所表现的产品起到美化作用；
从近几年电影行业的发展趋势来看，制作人在注重故事性的同时，也越来越注重观众的体验，因此电影也在逐步向3D立体电影方向发展。所以，三维几何模型在影视动画领域中所扮演的角色也越来越重要。
1.4、三维几何模型在游戏中的应用
随着人们越来越注重游戏体验，游戏的自由度、趣味性和真实度越来越受到游戏玩家的重视，游戏行业也逐渐向3D游戏方向发展。
从概念上来讲，3D游戏就是三维游戏，游戏中的场景、人物模型都是由三维几何模型组成的，既是在游戏中使用3D模型来制作人物、场景等物体。使玩家可以在游戏中体会到长宽高三种度量，让玩家可以360度旋转视角，从各个角度来进行游戏。这大大增加的游戏的自由度、趣味度及真实性。目前3D游戏已经成为了当今游戏行业的主流游戏类型。
目前国内已经有许多自己制作的出色的3D游戏，例如《3D环游中国》，这是一款赛车类的3D街机游戏，选取北京，山西，杭州，上海，广州，香港六大城市赛道，让玩家尽情体验中国风的3D赛车游戏。：
另外，经典的3D游戏还有很多，比如魔兽世界、永恒之塔、指环王、天下2、完美国际、龙之谷、神兵传奇、流星蝴蝶剑等等很多。他是3D游戏的代表之作，取得了巨大的成功，是三维几何模型在游戏领域应用得典范。
3D游戏虽然可以说是近几年游戏领域的一大飞跃，但是也有自己的不足，最主要的一点是3D游戏画面越好对设备的配置要求就越高，还有就是目前3D技术着实有限，不能够完美的将3D效果表达出来，所以画面难免还是会有一些瑕疵，这也使许多追求完美的玩家不能够满意。但是毕竟这是游戏产业的一大进步。
1.5、在其他领域的应用
1、建筑领域
现在阶段在中国，三维几何模型在建筑领域得到了最广泛的应用。建筑漫游、房地产漫游、、小区浏览、楼盘漫游、三维虚拟样板房、楼盘3D动画宣传片、地产工程投标、建筑概念动画、房地产电子楼书、房地产虚拟现实等制作。
2、规划领域
道路、桥梁、隧道、立交桥、街景、夜景、景点、市政规划、城市规划、城市形象展示、数字化城市、三维城市规划虚拟城市、城市数字化工程、园区规划、场馆建设、机场、车站、公园、广场、报亭、邮局、银行、医院、数字校园建设、学校等制作。
3、产品演示
三维几何模型在产品演示上涉及:工业产品如汽车、飞机、轮船、火车、舰艇、飞船等；电子产品如手机、医疗器械、监测仪器仪表、治安防盗设备；三维汽车设计机械产品动画如机械零部件、油田开采设备、钻井设备、发动机；产品生产过程如产品生产流程、生产工艺等三维制作。
4、模拟动画
模拟动画制作,是使用三维几何模型，通过动画模拟一切过程如制作生产过程、交通安全演示动画(模拟交通事故过程)、煤矿生产安全演示动画(模拟煤矿事故过程)、能源转换利用过程、水处理过程、水利生产输送过程、电力生产输送过程、矿产金属冶炼过程、化学反应过程、植物生长过程、施工过程等演示动画制作。
二、三维几何模型细化技术
2.1 网格细分算法的产生与发展
细分思想最早可以追溯的50 多年前G.de Rham 用于生成二维光滑曲线的“砍角算法”。1974 年, Chaikin 在研究曲线的快速绘制时把离散细分的概念引入到图形学界; 1978 年Catmull 和Clark 以及Doo 和Sabin 分别发表了一篇在图形学领域具有里程碑意义的论文, 也就是图形学界推崇的Catmull-Clark 算法和Doo- Sabin 算法, 标志着网格细分方法研究的真正开始; 1987 年, 美国犹他大学的Loop 在他的硕士论文中提出了Loop 细分策略; 1990 年Dyn, Gregory 和Levin 提出了蝶型细分算法, 其后Denis Zorin 对其提出了一种改进策略———改进的蝶型细分算法; Leif Kobbelt 在1996 年提出了一种基于四角网格的插值策略。另外, 3细分算法、4-k 细分算法以及hexagon-by- three 算法等对网格细分算法的发展也起到了一定的推进作用。随着六边形在其他领域的成功运用以及六边形固有的特性, 使得对六边形网格的研究成为细分算法研究领域的另一个热点。
2.2 三维几何模型细化概念
三维几何模型是由许多网格构成，加上材质和贴图得到的。三维几何模型的精度实际上是由网格的大小所决定的。本文中的三维几何模型细化指的是三维模型的网格细分，它是一种基于网格离散曲面的表示方法，它可以从任意拓扑网格构造光滑曲面。细分方法的基本思想是：定义一个网格序列的极限，其中网格序列是采用一定的细分规则，在给定的初始网格中插入新的顶点，从而不断细化出新的网格，重复运用细化规则，在极限时，该网格即收敛于一个光滑的曲线或者曲面。三维模型网格的细分是图形学算法以及游戏领域中一个较为常用且有代价值的算法。
网格细分是由细分规则作用在初始网格得到的。细分规则可以分为两个部分：一是拓扑分裂规则，主要用来描述网格每次细分之后所有顶点之间的连接关系，该过程也称为分裂；另一个是几何规则，用来计算新顶点的几何位置信息，这一过程也称为平均。
通常有两种基本的分裂方法：顶点分裂和面分裂，其区别主要在于所作用的基本几何体元。
顶点分裂是对于给定度为n的顶点i（顶点的度表示顶点所关联的边的个数），将其分裂成n个新顶点，每个顶点对应着它的一个邻面，使用该方式的细分方法称为对偶型。如果i为内部顶点，则把这些复制顶点依次相边开成一个新的n边形，称此n边形为新网格的V-面；对于控制网格中的每条边，两个端点分裂时在两个相邻面产生对应的四个新顶点，连接这四个顶点构成的面称为E-面，旧网格多边形每个顶点分裂构成的新网格面与原来的网格具有相同的拓扑结构，称之为F-面。
2.3 三维几何模型细化意义
由于三维几何模型的应用领域越来越广泛，要求构建的三维几何模型精度越来越大，
这给建模工作带来了更大的工作量。在现在的很多实时系统中，例如电脑游戏、计算机动画，模型通常用三角网格表示的。但是粗糙的网格却难以取得好的显示效果，在轮廓、阴影显示、细节特征上很多时候是不尽如人意的。如果采用过于精细的网格会在数据存储和交换、多分辨率显示、网格变形等方面造成不必要的开销。但是如果改用较次的多项式曲面插值网格，在计算复杂性、数据表示和交换上都会有很多困难。而细分通过反复细化初始的多边形网格，可以产生一系列网格趋向于最终的细分曲面。每个新的子分步骤产生一个新的有更多多边形元素并且更光滑的网格。也就是说，在建立了一个简单的模型后，使用细化操作，能够得到更为精细的三维几何模型，这将为构建三维几何模型带来了许多的便利之处。三维几何模型细化不仅解决模型复杂度，同时减轻建模的工作量，提高建模工作的工作效率以及制作成本。因此细分曲面造型技术非常适合在这些领域应用。
2.4 三维几何模型细化算法
按照细分规则不同，每一种细化方案对应着一套相应的细化算法，比如说Doo-Sabin
算法，Catmull-Clark算法，Loop算法，Sqrt3算法、Interpolating Sqrt3算法、Modified Butterfly算法等。
在实践中经常使用的及种细化模式主要有以下几种：Catmull-Clark细化模式，
Doo-Sabin细化模式，Loop细化模式，Sqrt3细化模式，Modified Butterfly细化模式，这及种方法的主要区别即在于它们的细分规则不同。下面将对这几种细化模式分别作介绍。
2.5 程序设计
2.5.1功能设计
本毕业设计是一款基础C#编写的能够实现三维几何模型细化操作的软件，他的主要功能是能够对导入软件的obj格式的三维几何模型文件按既定的细化模式进行细化操作。
本程序只要功能为：
1、能够正确的导入和读取obj格式的三维几何模型文件。
2、能够按按选择的细化模式和步骤完成对三维几何模型的细化操作，主要包括：
（1）、选择细分步骤，即要分多少次完成细分操作，也就是将按选择的细化模式要执行多少次细化操作。
（2）、能够以Loop细化模式实现对三维几何模型的细化操作；
（3）、能够以Sqrt3细化模式实现对三维几何模型的细化操作；
（4）、能够实现以Modified Butterfly细化模式实现对三维几何模型的细化操作；
3、对进行细化操作后的obj文件，能够执行导入操作。
2.5.2 流程设计
1、读取obj格式的三维几何模型文件
2、在软件界面中显示该obj文件
3、根据界面选择，确定执行细化操作的步骤
4、按照选择的细化模式，对三维几何模型执行细化操作
三、结论
本文以三维几何模型细化算法与实现作为研究对象，针对三维几何模型的应用范围和未来发展趋势进行分析，提出细化这一技术。再根据对三维几何模型细化模式的分析，设计算法，并使用C#语言进行实践。主要成果如下：
一、分析了三维几何模型细化技术的国内外现状，分析了三维几何模型的应用领域和未来发展趋势：随着计算机三维影像技术的不断发展，三维几何模型的应用范围也越来越广，三维几何模型从简单到复杂，从静态到动态，三维几何模型细化技术越来越被人们所看重,研究三维几何模型细化的人和组织也越来越多，这将推动整个行业大快速发展。
二、对三维几何模型的细化模型进行研究，总结了分析了当今行业内的细化模式。对典型的三维几何模型细化模式进行分析和研究。每一种细化模式代表的是一种对三维几何模型细化操作的方式和原理，他们有着不同的算法和细化方案。随着从事三维几何模型细化研究的人和组织越来越多，细化模式也将越来越多。从算法和实现上进行分析，为在实践中使用这些细化模式打下了坚实的理论基础，为接下来在VC#平台上开发完成三维几何模型细化功能的实现做好了准备。
三、对三维几何模型细化技术进行了实践，在Microsoft Visual Studio 2008平台上之用C#语言，结合OpenGL等方面的知识，开发实现了基于C#的三维几何模型细化功能。对导入的obj格式文件能够使用细化功能进行细化操作，达到了课题的预期目标。
总的来说，国内在三维几何模型细化研究上只是刚刚起步，但随着三维几何模型在实际生活中所扮演的角色越来越重要，细分技术提供了一种简单高效的方法来构造具有任意拓扑结构的自由曲面, 同时还能满足一定的光滑性要求。三维几何模型细化技术在未来的时间里将会成为人们专研的课题之一，它将会成为一个更为成熟的技术领域。
同时，近几年, 随着细分理论的日趋完善, 对细分曲线、曲面算法的研究成了图形学领域的一个热点。就三维几何模型细化算法而言, 现有的算法大部分都是针对三角网格和四角网格的, 并且都纯粹是逼近或插值型的。逼近算法收敛速度快而且光滑性好, 但对初始网格的形状和体积改变很大；插值算法可以很好地控制模型, 但曲面的光滑性一般。因此, 能够有效地将逼近算法和插值算法结合起来发挥两者的优势是一个不错的选择,这也将是人们今后的一个研究重点。
主要参考资料
1、Christian Nagel、bill Evjen 、Jay Glynn 等《C#高级编程(第6版)(Professional C# 2008)》清华大学出版社 2008年10月
2、Juditb Bisbop 《C#3.0设计模式》机械工业出版社 2011年1月
3、伍逸《C#二维三维图形绘制工程实例宝典》电子工业出版社 2012年12月
4、McMillan 《数据结构与算法：C#语言描述》人民邮电出版社 2013年8月
5、Donald Hearn、M.Pauline Baker 《计算机图形学(第3版)》电子工业出版社 2010年7月。
6、OpenFlipper官方网站：https://www.wendangku.net/doc/2c2753332.html,/
7、王金生, 韩臻, 施寅, 等《几种经典网格细分算法的比较》计算机应用研究2004年。
8、维基百科（英语）：https://www.wendangku.net/doc/2c2753332.html,/wiki/Subdivision_surface
9、MeshLab官方网站：https://www.wendangku.net/doc/2c2753332.html,/
致谢
通过撰写本文和完成毕业设计是我受益匪浅，它综合了我学习的数字图像处理、动画、程序设计、软件测试等知识，并将这些知识运用到了实践中。
在此，我要非常诚挚的感谢指导老师张文艺。在我撰写论文和完成毕业设计期间，老师一直给予了我非常耐心和悉心的指导，并且为我的课题提供了许多建设性的意见。张老师创新和严谨的治学态度感染着我，必将使我受益终身。与此同时，我也认识到了自己的诸多不足，这主要体现在技术和经验上的欠缺，但是这也使得我明确了自己的努力方向。