Catmull-Clark算法细分曲面研究
Catmull-Clark算法细分曲面研究
随着信息技术的迅速发展，数字化的现代多媒体信息己应用到社会的每个角落，原有的造型方法已不能满足人们的需要。曲线曲面的离散化造型方法的细分方法，是多边形网格和参数表示方法的结合，并凭着原有方法难以比及的优处成为了计算机图形学的一个研究重点。本论文介绍了曲面细分的有关基础知识和曲面细分在现实生活中的应用，并描述了三种经典曲面细分的算法——Doo-Sabin细分算法、Catmull-Clark细分算法和Loop细分算法，简单介绍了这三种细分算法的几何规则和拓扑规则，用Catmull-Clark细分算法建立了模型并通过Matlab软件程序实现了对模型的细分。
关键字 曲面细分， Catmull-Clark算法，Matlab
1 绪论 6
1.1国内外研究现状和发展趋势 6
1.1.1以细分为基础的多分辨率分析 6
1.1.2三维动画造型 6
1.1.3重建与模拟医学图像 7
1.1.4工程曲面造型 7
2 曲面细分的综述 8
2.1曲面细分简介 8
2.2曲面细分的发展历史 8
2.3曲面细分的概念 9
2.4细分方法分类 9
2.4.1细分规则的类型(和四角网格点分裂和面分裂) 9
2.4.2生成网格的类型（三角网格） 9
2.4.3算法是逼近型还是插值型 9
2.4.4 规则曲面的极限曲面光滑性 9
2.5细分方法的特点 10
2.5.1任意拓扑性 10
2.5.2高效性 10
2.5.3表示的一致性 10
2.5.4数值稳定性 10
2.5.5可伸缩性 10
2.5.6算法的简便性 11
2.6应用曲面细分的关键性问题 11
2.6.1面片的增长速度 11
2.6.2尖锐特征处理 11
2.6.3边界控制 11
2.6.4曲面的修改和编辑 11
2.6.5等距面 12
2.6.6曲面求交 12
3 曲面细分三种经典算法 12
3.1Doo-Sabin细分算法 12
3.2Catmull-Clark细分算法 15
3.3 Loop细分算法 17
3.4Catmull-Clark细分算法的具体模型实现 19
结 论 23
致 谢 24
参 考 文 献 25
附 录 26
1.1国内外研究现状和发展趋势
在细分曲面的造型方法中，网络拓扑的结构无法对曲面产生影响，并且拥有很强大的曲面造型能力，因此备受大家的关注，并且已成为计算机图形学领域的一个研究热点。不少国家对细分造型的方法展开了研究，其中美国的Utah大学在这一方面研究的比较早一些，并提出了像Loop细分、Catmull-Clark细分这些十分著名的细分方法；美国纽约大学的Zorin与 Prautzsch完整地剖析了静态细分方法的收敛性及连续性；其中美国Pixar公司的DeRose等人将Catmull-Clark细分成功的应用于三维动画造型中[1]。
一直到2000年国内才开始发表与细分曲面相关的文章。在近几年，国内少数几所大学开始了对细分曲面的研究，并且研究的主要方向集中在一些简单的算法以及图形学和工程学领域的应用，清华大学的秦开怀等人对非均匀细分曲面的连续性进行了研究[2]；半静态细分方法和非均匀递归细分方法、以C-B样条为基础的Catmull-Clark细分方法分别被浙江大学的张纪文、郑建民和张宏鑫等人提出；以稀疏数据为基础的细分曲面拟合方法则被南京航空航天大学的王占东等人提出和研究[3]。
由于细分曲面的理论还在研究中，就现在已经有的成果来看主要还是集中在理论方面。如果想要真正将曲面细分的应用技术在实际领域使用，还要研究很多问题。综合各种客观情况，细分曲面的发展趋势主要有以下几个方面；
1.1.1以细分为基础的多分辨率分析
如果将信号表示为低分辨率的信号，并且同时产生的一些细节能够在不同的尺度上反映出该信号，这个过程也就是多分辨率分析的基本思想。多分辨率的模型它能够重新构造物体的表面从粗糙到精细的每一个层次模型，这也是曲面表示的一种方法。把计算机网络技术与曲面细分方法结合，是多分辨率曲面的一个主要的研究方向。
1.1.2三维动画造型
作为一种曲面表示方法被提出的细分曲面，并且被运用到不少三维造型软件中，如Animation Master、Maya、Animation Master、LightWave等。生成特点、保持原有的形状以及纹理的映射是在动画造型领域需要被解决的主要问题。这个方面的研究重点是以细分为基础的变形，同时也包含了地形地貌的生成过程和绘制。细分曲面在三维动画中的应用主要依靠了一些可用于编程图形的硬件对细分的速度更进一步的提高获得了很好的技术支持。
1.1.3重建与模拟医学图像
由于动态细分曲面造型方法拥有其独特的优点，秦宏等学者提出了将它应用到模拟医学图像重建与受力变形的想法。第一个步骤是，获得三维核磁共振切片的具体数据，并且利用这些数据作出一条曲面使其成为对小脑进行细分的初始控制网格；第二个步骤是，在形成的拉格朗日动态力学模型上的某一个部位施加上合适的外力，并且根据施加的不同外力对其进行计算由此得到脑组织的变形分析结果。曲面细分可以方便地再建任意拓扑结构的形状和非常直观地模拟动态曲面的变形这两个优点在这种方式中得到了具体完整地体现。同时，秦开怀也用细分曲面图像的方式研究了相关的其它医学方面的模拟和重建。
1.1.4工程曲面造型
在动画造型系统中细分曲面已经得到了广泛的应用，而其在工程曲面造型方面的运用却才是刚刚起步的阶段，形成这种情况的主要因素是这两个方面对于目标曲面的要求有很大区别。工程曲面造型更倾向于模型几何精度和连续性等方面的研究，对细分质量方面的要求比较高。而模型光的顺性等方面的视觉效果却是动画造型需求的重点；这个方面包含了以下一些的主要研究方面：布尔运算、细分曲面的拟合以及用细分方法解决参数曲面造型问题。
1.2论文研究的主要内容
本文系统的介绍了曲面细分的有关基本理论知识，简单叙述了三种比较经典的曲面细分方法—Doo-Sabin细分方法、Catmull-Clark细分方法和Loop细分方法的基本原理并就Loop细分方法进行了深入的研究。本文的主要研究内容如下：
第一章，绪论。阐述了曲面细分的研究意义以及背景，并给出了现今这个领域的国内外研究现状和发展趋势。
第二章，曲面细分的综述。简单介绍了细分曲面的发展历史，并就曲面细分的一些重要概念进行了解释。提出了曲面细分方法的一般分类的规则，说明了细分方法的特点。简单介绍了曲面细分的主要应用领域和曲面细分在其应用过程中会遇到的一些重要问题。
第三章，曲面细分的三种经典算法。分别列出了Doo-Sabin细分算法、Catmull-Clark细分算法和Loop细分算法，并且简单的说明了三种算法的几何规则和拓扑规则。
2 曲面细分的综述
2.1曲面细分简介
根据基本面元的不同，曲面表示的方法有借助参数表示、多边形网格曲面的表示、隐式的表示曲面以及其它表示的方法等。
隐式曲面具有可以方便地表示封闭光滑形体、简便地计算几何求交等优点。它由函数定义，在表现云、水滴、人体的肌肉等物体的动画和造型方面有很大的优势。但是它并不擅长于表示尖锐特征和丰富细节。
如果采用连续的基函数，与此同时形体连续性的形容是利用一组具有线性组合的初始控制向量，这种表示方法就是参数曲面。它的优点为易于离散、赋值计算简便和显示方便等。参数曲面因为与国防建设的密切相关，较早就得到了许多关注，至今已经形成了主要依靠逼近、插值和拟合处理手段的几何理论体系，它的主要代表为Bezier和B样条方法。但是它在处理拼接和高亏格(注l：亏格是代数几何和代数拓扑中最基本的概念之一。其定义为：若曲面中最多可画出n条闭合曲线同时不将曲面分开，则称该曲面亏格为n。以实的闭曲面为例，亏格g就是曲面上洞眼的个数。比如球面没有洞，故；又如环面有一个洞，故。)曲面时非常繁琐。
多边形网格表示三维形体的数学原理非常简单，并且便于理解而且适合绘制，如果想达到极富有真实感的绘制特效可同时配合纹理映射等。网格曲面不但可以表现丰富的细节而且适用于复杂形体的模型，因而它已经被广泛地应用于三维的几何媒体[4]。
2.2曲面细分的发展历史
50年代G.Rham提出的对折线角点进行切割来生成光滑曲线的思想可以算是细分方法的起源。在70年代中后期，Chaikin将这种角切割的思想具体实现，提出生成曲线的细分方法[Chaikin，1974]。随后，Catmull-Clark细分方法[Catmull 1978]横空出世，这意味着曲面建模已经主要依靠细分方法来实现。Catmull-Clark方法生成的是三次B样条曲面，但是当网格有奇异顶点时，曲面中有限个点会具有二阶光滑性；反之，若网格没有奇异顶点时，就是一个标准的三次B样条曲。以下三个过程是根据细分方法的历史发展过程划分的：
70年代中期，细分方法凭借Doo-Sabin的对于奇异点处行为的分析理论和已经产生的Catmull-Clark细分方法正式成为曲面曲线造型的重要手段。
80年代到90年代初是起步期，很多极具名气的细分方法就产生于这一时间段。为了适应不同的发展要求，在这一时期对旧方法进行了重大改动，并将连续分析理论和规则情形的收敛性改动的更加完善。
90年代中期至今为发展期。收敛性理论在这一阶段过程中逐渐建立系统，引入很多著名的理论框架结构进行收敛性分析[Warren 1995，Reif 1995，Zorin 1998]。在这些著名的理论的指导下，细分方法进行了改进，在构造二阶以上的连续曲面方面表现的尤为突出。除此之外，各种细分方法的关联也渐渐浮出水面，为人们所掌握。
2.3曲面细分的概念
所谓曲面细分是指以一定的规则对多边形网格进行逐层精化，形成一个收敛的网格序列，取序列极限的曲面造型方式，细分曲面就是这个的极限结果[5]。不断的重复采用自己定义的规则向初始网格中插入新节点这一过程就可以获得一个网格序列。这种方法主要是解决了参数曲面在处理拓扑网络结构时遇到的困难。
在实现时细分曲面只把多边形网格当做某一个细分层次的多面体来进行处理和分析，因此在一定程度上多边形网格就是细分方法的处理对象[6]。
2.4细分方法分类
多边形网格在有了上述的网格的概念基础，我们就可以进一步考虑细分方法。通常情况下，可以分解成两次主要的操作来完成细分方法的每次加细或细分。第一算出所有节点的结果位置，相应的方法则称之为几何规则。第二通过不断增加新顶点形成一个新的网格拓扑，我们称之为网格分裂，其中所用到的方法我们称之为拓扑规则。拓扑分裂规则和几何平均规则的集合称为细分方法[8]。
随着信息技术的迅速发展，数字化的现代多媒体信息己应用到社会的每个角落，原有的造型方法已不能满足人们的需要。曲线曲面的离散化造型方法的细分方法，是多边形网格和参数表示方法的结合，并凭着原有方法难以比及的优处成为了计算机图形学的一个研究重点。本论文介绍了曲面细分的有关基础知识和曲面细分在现实生活中的应用，并描述了三种经典曲面细分的算法——Doo-Sabin细分算法、Catmull-Clark细分算法和Loop细分算法，简单介绍了这三种细分算法的几何规则和拓扑规则，用Catmull-Clark细分算法建立了模型并通过Matlab软件程序实现了对模型的细分。
关键字 曲面细分， Catmull-Clark算法，Matlab
1 绪论 6
1.1国内外研究现状和发展趋势 6
1.1.1以细分为基础的多分辨率分析 6
1.1.2三维动画造型 6
1.1.3重建与模拟医学图像 7
1.1.4工程曲面造型 7
2 曲面细分的综述 8
2.1曲面细分简介 8
2.2曲面细分的发展历史 8
2.3曲面细分的概念 9
2.4细分方法分类 9
2.4.1细分规则的类型(和四角网格点分裂和面分裂) 9
2.4.2生成网格的类型（三角网格） 9
2.4.3算法是逼近型还是插值型 9
2.4.4 规则曲面的极限曲面光滑性 9
2.5细分方法的特点 10
2.5.1任意拓扑性 10
2.5.2高效性 10
2.5.3表示的一致性 10
2.5.4数值稳定性 10
2.5.5可伸缩性 10
2.5.6算法的简便性 11
2.6应用曲面细分的关键性问题 11
2.6.1面片的增长速度 11
2.6.2尖锐特征处理 11
2.6.3边界控制 11
2.6.4曲面的修改和编辑 11
2.6.5等距面 12
2.6.6曲面求交 12
3 曲面细分三种经典算法 12
3.1Doo-Sabin细分算法 12
3.2Catmull-Clark细分算法 15
3.3 Loop细分算法 17
3.4Catmull-Clark细分算法的具体模型实现 19
结 论 23
致 谢 24
参 考 文 献 25
附 录 26
1.1国内外研究现状和发展趋势
在细分曲面的造型方法中，网络拓扑的结构无法对曲面产生影响，并且拥有很强大的曲面造型能力，因此备受大家的关注，并且已成为计算机图形学领域的一个研究热点。不少国家对细分造型的方法展开了研究，其中美国的Utah大学在这一方面研究的比较早一些，并提出了像Loop细分、Catmull-Clark细分这些十分著名的细分方法；美国纽约大学的Zorin与 Prautzsch完整地剖析了静态细分方法的收敛性及连续性；其中美国Pixar公司的DeRose等人将Catmull-Clark细分成功的应用于三维动画造型中[1]。
一直到2000年国内才开始发表与细分曲面相关的文章。在近几年，国内少数几所大学开始了对细分曲面的研究，并且研究的主要方向集中在一些简单的算法以及图形学和工程学领域的应用，清华大学的秦开怀等人对非均匀细分曲面的连续性进行了研究[2]；半静态细分方法和非均匀递归细分方法、以C-B样条为基础的Catmull-Clark细分方法分别被浙江大学的张纪文、郑建民和张宏鑫等人提出；以稀疏数据为基础的细分曲面拟合方法则被南京航空航天大学的王占东等人提出和研究[3]。
由于细分曲面的理论还在研究中，就现在已经有的成果来看主要还是集中在理论方面。如果想要真正将曲面细分的应用技术在实际领域使用，还要研究很多问题。综合各种客观情况，细分曲面的发展趋势主要有以下几个方面；
1.1.1以细分为基础的多分辨率分析
如果将信号表示为低分辨率的信号，并且同时产生的一些细节能够在不同的尺度上反映出该信号，这个过程也就是多分辨率分析的基本思想。多分辨率的模型它能够重新构造物体的表面从粗糙到精细的每一个层次模型，这也是曲面表示的一种方法。把计算机网络技术与曲面细分方法结合，是多分辨率曲面的一个主要的研究方向。
1.1.2三维动画造型
作为一种曲面表示方法被提出的细分曲面，并且被运用到不少三维造型软件中，如Animation Master、Maya、Animation Master、LightWave等。生成特点、保持原有的形状以及纹理的映射是在动画造型领域需要被解决的主要问题。这个方面的研究重点是以细分为基础的变形，同时也包含了地形地貌的生成过程和绘制。细分曲面在三维动画中的应用主要依靠了一些可用于编程图形的硬件对细分的速度更进一步的提高获得了很好的技术支持。
1.1.3重建与模拟医学图像
由于动态细分曲面造型方法拥有其独特的优点，秦宏等学者提出了将它应用到模拟医学图像重建与受力变形的想法。第一个步骤是，获得三维核磁共振切片的具体数据，并且利用这些数据作出一条曲面使其成为对小脑进行细分的初始控制网格；第二个步骤是，在形成的拉格朗日动态力学模型上的某一个部位施加上合适的外力，并且根据施加的不同外力对其进行计算由此得到脑组织的变形分析结果。曲面细分可以方便地再建任意拓扑结构的形状和非常直观地模拟动态曲面的变形这两个优点在这种方式中得到了具体完整地体现。同时，秦开怀也用细分曲面图像的方式研究了相关的其它医学方面的模拟和重建。
1.1.4工程曲面造型
在动画造型系统中细分曲面已经得到了广泛的应用，而其在工程曲面造型方面的运用却才是刚刚起步的阶段，形成这种情况的主要因素是这两个方面对于目标曲面的要求有很大区别。工程曲面造型更倾向于模型几何精度和连续性等方面的研究，对细分质量方面的要求比较高。而模型光的顺性等方面的视觉效果却是动画造型需求的重点；这个方面包含了以下一些的主要研究方面：布尔运算、细分曲面的拟合以及用细分方法解决参数曲面造型问题。
1.2论文研究的主要内容
本文系统的介绍了曲面细分的有关基本理论知识，简单叙述了三种比较经典的曲面细分方法—Doo-Sabin细分方法、Catmull-Clark细分方法和Loop细分方法的基本原理并就Loop细分方法进行了深入的研究。本文的主要研究内容如下：
第一章，绪论。阐述了曲面细分的研究意义以及背景，并给出了现今这个领域的国内外研究现状和发展趋势。
第二章，曲面细分的综述。简单介绍了细分曲面的发展历史，并就曲面细分的一些重要概念进行了解释。提出了曲面细分方法的一般分类的规则，说明了细分方法的特点。简单介绍了曲面细分的主要应用领域和曲面细分在其应用过程中会遇到的一些重要问题。
第三章，曲面细分的三种经典算法。分别列出了Doo-Sabin细分算法、Catmull-Clark细分算法和Loop细分算法，并且简单的说明了三种算法的几何规则和拓扑规则。
2 曲面细分的综述
2.1曲面细分简介
根据基本面元的不同，曲面表示的方法有借助参数表示、多边形网格曲面的表示、隐式的表示曲面以及其它表示的方法等。
隐式曲面具有可以方便地表示封闭光滑形体、简便地计算几何求交等优点。它由函数定义，在表现云、水滴、人体的肌肉等物体的动画和造型方面有很大的优势。但是它并不擅长于表示尖锐特征和丰富细节。
如果采用连续的基函数，与此同时形体连续性的形容是利用一组具有线性组合的初始控制向量，这种表示方法就是参数曲面。它的优点为易于离散、赋值计算简便和显示方便等。参数曲面因为与国防建设的密切相关，较早就得到了许多关注，至今已经形成了主要依靠逼近、插值和拟合处理手段的几何理论体系，它的主要代表为Bezier和B样条方法。但是它在处理拼接和高亏格(注l：亏格是代数几何和代数拓扑中最基本的概念之一。其定义为：若曲面中最多可画出n条闭合曲线同时不将曲面分开，则称该曲面亏格为n。以实的闭曲面为例，亏格g就是曲面上洞眼的个数。比如球面没有洞，故；又如环面有一个洞，故。)曲面时非常繁琐。
多边形网格表示三维形体的数学原理非常简单，并且便于理解而且适合绘制，如果想达到极富有真实感的绘制特效可同时配合纹理映射等。网格曲面不但可以表现丰富的细节而且适用于复杂形体的模型，因而它已经被广泛地应用于三维的几何媒体[4]。
2.2曲面细分的发展历史
50年代G.Rham提出的对折线角点进行切割来生成光滑曲线的思想可以算是细分方法的起源。在70年代中后期，Chaikin将这种角切割的思想具体实现，提出生成曲线的细分方法[Chaikin，1974]。随后，Catmull-Clark细分方法[Catmull 1978]横空出世，这意味着曲面建模已经主要依靠细分方法来实现。Catmull-Clark方法生成的是三次B样条曲面，但是当网格有奇异顶点时，曲面中有限个点会具有二阶光滑性；反之，若网格没有奇异顶点时，就是一个标准的三次B样条曲。以下三个过程是根据细分方法的历史发展过程划分的：
70年代中期，细分方法凭借Doo-Sabin的对于奇异点处行为的分析理论和已经产生的Catmull-Clark细分方法正式成为曲面曲线造型的重要手段。
80年代到90年代初是起步期，很多极具名气的细分方法就产生于这一时间段。为了适应不同的发展要求，在这一时期对旧方法进行了重大改动，并将连续分析理论和规则情形的收敛性改动的更加完善。
90年代中期至今为发展期。收敛性理论在这一阶段过程中逐渐建立系统，引入很多著名的理论框架结构进行收敛性分析[Warren 1995，Reif 1995，Zorin 1998]。在这些著名的理论的指导下，细分方法进行了改进，在构造二阶以上的连续曲面方面表现的尤为突出。除此之外，各种细分方法的关联也渐渐浮出水面，为人们所掌握。
2.3曲面细分的概念
所谓曲面细分是指以一定的规则对多边形网格进行逐层精化，形成一个收敛的网格序列，取序列极限的曲面造型方式，细分曲面就是这个的极限结果[5]。不断的重复采用自己定义的规则向初始网格中插入新节点这一过程就可以获得一个网格序列。这种方法主要是解决了参数曲面在处理拓扑网络结构时遇到的困难。
在实现时细分曲面只把多边形网格当做某一个细分层次的多面体来进行处理和分析，因此在一定程度上多边形网格就是细分方法的处理对象[6]。
2.4细分方法分类
多边形网格在有了上述的网格的概念基础，我们就可以进一步考虑细分方法。通常情况下，可以分解成两次主要的操作来完成细分方法的每次加细或细分。第一算出所有节点的结果位置，相应的方法则称之为几何规则。第二通过不断增加新顶点形成一个新的网格拓扑，我们称之为网格分裂，其中所用到的方法我们称之为拓扑规则。拓扑分裂规则和几何平均规则的集合称为细分方法[8]。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/3108.html
