（应用数学专业论文）细分曲面重建.pdf

浙江大学硕士学位论文 摘要 细分曲面重建是一种重要的曲面重建方法，它可以应用在任意拓扑结构的网格 上，并且重建出的曲面能进行快速绘制和具有多分辨显示等特点。本文在前人的工 作基础上，但未采用以往的参数化思想，提出了一种应用在闭合曲面上基于几何的 细分曲面重建方法。算法思想简洁，可自动重建也可人机交互进行优化等为本文算 法的优点。 第一章，本文在介绍相关的基础知识的同时对以往的工作简要回顾，扼要的说 明了本文算法思想所在。 第二章，详尽的阐述了本文所提出的细分曲面重建方法。介绍了重建方法的两 部分工作：重新网格化( r e m e s h ) 和重建。重新网格化是为进行重建作初期的准备 工作，建立重建所需要的具有细分结构( s u b d i v i s i o nc o n n e c t i v i t y ) 的网格，并为后 面的重建工作保存了和细分有关的信息。重建时，先是根据前面工作保存下来的细 分矩阵的信息用最小二乘的方法反求出控制网格的顶点，然后在根据保存的网格拓 扑结构等信息，建立控制网格的拓扑结构。最后给出了整个算法的流程图。 第三章，详细介绍了重新网格化的具体步骤，结合实例讨论了如何将已有的简 化工作结合到我们的工作中来，对特殊的奇异情况进行了初步研究并给出了一定的 解决方法。 第四章，详细介绍了重建的具体步骤，结合c a t m u l l c l a r k 细分规则介绍了如何 进行信息的保存和读取，以及如何反求出顶点和建立相应的拓扑结构。 第五章，以图例的形式给出了实验结果，示例了人工交互的优越性。 第六章，对本文工作进行了总结并探讨了以后工作的展开方向。 浙江大学硕士学位论文 a b s t r a c t t h er e c o n s t r u c t i o nf o rs u b d i v i s i o ns t a r f a c e si sa ni m p o r t a n tm e t h o do fs u r f a c e s r e c o n s t r u c t i o n i tn o to n l yc a nb ea p p l i e do na r b i t r a r yt o p o l o g i c a lm e s h e s ，b u ta l s oh a st h e a d v a n t a g e so ff a s t s p e e dr e n d e r i n ga n dm u l t i - r e s o l u t i o nv i s u a l i z a t i o n t h i st h e s i sp r e s e n t s an e wr e c o n s t r u c t i o na l g o r i t h mf o rs u b d i v i s i o ns u r f a c e sb a s e do ng e o m e t r y ，w h i c hc a l lb e a p p l i e d o nc l o s es u r f a c e s c o m p a r e dw i t he x i s t i n gm e t h o d s ，t h i sa l g o r i t h mi ss u p e r i o ro n i t ss i m p l i c i t ya n de a s e o f - i n t e r a c t i o n i nt h ef i r s tc h a p t e r , w ef i r s ti n t r o d u c ec o r r e l a t i v eb a s i cc o n c e p t sa n dr e v i e we x i s t i n g m e t h o d s f u r t h e r m o r e ，t h e c o r eo f o u r a l g o r i t h mi ss i m p l yi n v e s t i g a t e d i nt h es e c o n d c h a p t e r , w e e l a b o r a t e o u rm e t h o df o rs u b d i v i s i o n s u r f a c e s r e c o n s t r u c t i o n t h i sm e t h o di sc o n s i s t i n go ft w os t e p s ：r e m e s ha n dr e c o n s t r u c t i o n a st h e f o u n d a t i o no fr e c o n s t r u c t i o n ，r e m e s hi st oe s t a b l i s ht h es t j b d i v i s i o nc o n n e c t i v i t ym e s l l e s ， w h i c ha r er e q u i r e di nr e c o n s t r u c t i o n ，a n dt oc o n s e r v es u b d i v i s i o ni n f o r m a t i o nf o rf u r t h e r r e c o n s t r u c t i o n i nt h ep r o c e d u r eo fr e c o n s t r u c t i o n ，c o n t r o lm e s hi sg a i n e db yl e a s t s q u a r e m e t h o db a s e do nt h es u b d i v i s i o nm a r x m e a n w h i l e ，t h et o p o l o g i c a ls t r u c t u r eo fc o n t r o l m e s hi so b t a i n e db yf o r m e rm e s hi n f o r m a t i o n f i n a l l y , w ec o n c l u d et h i sc h a p t e rw i t h f l o wc h a r to f t h ew h o l e a l g o r i t h m i nt i l et h i r dc h a p t e r , r e m e s hi sd e s c r i b e di nd e t a i l c o m b i n gw i t hc o n c r e t ee x a m p l e s ， w ed i s c u s sh o wt o s i m p l i f yt h i ss t e p b e s i d e s ，w ei n v e s t i g a t er e s o l u t i o nf o rs i n g u l a r i t y i n s t a n c e s i nt h ef o u r t h c h a p t e r , r e c o n s t r u c t i o n i sd e s c r i b e di n d e t a i l c o m b i n g w i t h c a t m u l l c l a r ks u b d i v i s i o n r e g u l a t i o n ，w e d i s c u s sh o wt oc o n s e r v e a n de x t r a c t i n f o r m a t i o na n dh o w t og e tc o n t r o lp o i n t sa n df o r m c o r r e s p o n d i n gt o p o l o g i c a ls t r u c t u r e i nt h ef i f t h c h a p t e r , a l o to f e x a m p l e s d e m o n s t r a t et h e f e a s i b i l i t y o f e a s e o f - i n t e r a c t i o n i nt h el a s tc h a p t e r , t h et h e s i si sc o n c l u d e dw i t ht h ed i s c u s s i o no f f u r t h e rr e s e a r c h - i l - 浙江大学硕士学位论文 第一章绪论 细分曲面重建是曲面蘑建的一个分支，而曲面重建是图形学中的一个重要内 容，它是给仅有实物模型而没有曲面模型的实物或是有曲面模型但不是我们所要求 的曲面建立相应的曲面模型，解决了计算机辅助设计与制造技术( c a d c a m ) 应 用到现实生产生活中的曲面建模问题。给实物建立曲面模型既可以给重要实物建立 计算机外形档案，也可以应用到抽取已有实物的外形轮廓来进行新的产品的外形设 计，提高开发效率和缩短反馈时间。因而，曲面重建被广泛应用到三维自然景物模 拟( 虚拟现实) ，珍贵文物的数据档案建立，快速原型制造等实际问题中，在其中发 挥了重要的作用。 曲面重建是在已有的实物表面或曲面的基础上建立曲面模型，忠实的再现原 有的实物表面或是曲面。因而曲面重建的基础就是这张实物表面或曲面，我们可以 报据所需在其上任意采集数据，当然如果在实物上采集的话还要受现有的采样工具 的限制。而重建的最关键的要求就是重建出来的曲面与实物表面或曲面之间的误差 在我们要求的范围之内，因而，不象自由曲面造型，我们必须检验最终的曲面，判 定它是否有效，或者说它是否忠实的再现了原有模型( 实物或曲面) 。 工程上习惯称曲面重建为逆向工程( r e v e r s ee n g i n e e r i n g ) ，这是因为工程中常常 是根据需要来设计一张曲面，两曲面重建则刚好进行的是相反的工作，它是根据已 经存在的但不知道曲面模型的曲面去建立其曲面模型。 1 。1 现实背景 快速原型制造( 又称r p m 技术) 是诞生于8 0 年代后期、基于材料累加法的 一种新的产品设计与制造技术，为产品的快速和创新设计提供了一种切实可行的技 术途径。r p m 综合了计算机、机械工程、c a d 、数控技术、激光技术以及材料科学 等高新技术，通过r p m 可以自动、直接、快速、精确地将设计思想转变为具有一 定功能的原型，或直接制造产品，从而可以对产品设计进行快速评估、修改以及功 能试验，大大缩短产品的研制周期。以r p m 系统为基础发展起来并已成熟的快速 工装模具制造( q u i c k t o o l i n g m o l d i n g ) 、快速精铸技术( q u i c k c a s t i n g ) ，可以实 现零件的快速制造( q u i c km a n u f a c t u r i n g ) 。 而曲面重建( 逆向工程) 能从一个已有的物理模型或实物零件产生出相应的 浙江大学硕士学位论文 曲面模型，因而重建是是实现r p m 的核心技术之一。将r p m 与曲面重建结合起来， 一方面为提高工程设计、加工、分析的质量和效率提供充足的信息，另一方面可为 充分利用先进的c a d c a m 技术对已有的产品原型进行再创新工程服务。 1 2 曲面重建的基本概念 将物体的表面抽象成具体的数学表达式的方法称为建立曲面模型，而该数学表 达式就是物体的几何模型。只有给物体建立相应的曲面模型，我们才可以对其进行 分析、比较、存储和重现。可见，这是我们对物体外形进行研究的基础，是曲面性 质的研究工具。 数学中的曲面是某些满足某种条件的点的集合，从理论上说，任何一张曲面都 有自己的约束条件( 数学表达式) 。然而，曲面与实物表面是不同的两件事物，因此 需要一种方法将实物表面抽象成数学中的曲面。此外，有时候尽管已有实物的曲面 模型，但需要的是另一种曲面模型，因此给没有曲面模型的实物或是不适合的曲面 模型重新建立曲面模型的过程成为曲面重建( s u r f a c e r e c o n s t r u c t i o n ) 。到目前为止， 我们建立起来的曲面模型在自然界中还是很小的一部分，因而，寻找新的有效的曲 面重建的方法还是具有很大的应用前景。 需要重建的曲面，其形状有时候很复杂。曲面重建工作需要采集大量的数据并 进行大量的计算，以前设备条件不够，仅有少数的大公司有能力研究。近十年来， 计算机的高速发展，得大容量、高速度的计算机为越来越多的用户所拥有，甚至于 现在的家用电脑性能可以与以前的小型机相比，再加上各种先进的采样设备的出现， 才为开展曲面重建工作提供了必要的工具，使得进行曲面重建成为种真正实用的 技术。 曲面重建的首要前提是准确，要求建立起来的数学模型比较精确地反映原来曲 面的形状，或者说能较好地逼近原来的曲面。另外，根据应用有时也有其他附加的 要求。比如说要求重建的模型结构简单，易于进行各种操作，或者说较方便地适合 计算机进行曲面的存储、分析、计算和绘制等；或是要求在一定的精度下尽可能的 减少数据量，以方便存储和传输；或是对特殊的几何构造予以重现，保持边角等等。 1 3 曲面重建的方法概述 曲面重建的方法有很多，依据曲面模型的表示方法不同，我们习惯上将曲面重 建分成主要的五类：参数曲面重建、隐式曲面重建、变形曲面重建、分片线性曲面 浙江大学硕士学位论文 重建和细分曲面重建。 1 3 1 参数曲面重建方法 参数曲线曲面是作为描述几何形状的主要工具，由c o o n s 、b 6 z i e r 等大师于上世 纪6 0 年代奠定其理论基础( 1 ) 。c o o n s 曲面、b 6 z i e r 曲面、n u r b s 曲面等不仅成 为几何设计的主要工具，而且n u r b s 已被作为工业产品数据交换的s t e p 标准， 也作为描述工业产品几何形状的唯一数学方法。 1 9 9 6 年e c k 等人在 2 w 提出了用b 样条曲面来对任意给定拓扑网格进行重建的 方法。同年，h a s t e a d 等利用b 样条曲面研究了高精度地逼近初始曲面法向的方法， 不能重建出有尖点和棱角的曲面，但由于它是以b 样条为工具，这就为包括b 6 z i e r 在内的各种参数曲面参与曲面重建的工作开辟了道路。1 9 9 7 年，l e e 等人在 3 1 9 给 出了一种用多阶b 样条曲面重建算法。1 9 9 9 年y a n g 和l e e 提出了一种基于边数据 分割的二次参数曲面重建方法( 【4 】) 。2 0 0 0 年p i e g l 和t i l l e r 在【5 】中提出了用b 一样 条曲面逼近离散采样点的方法。同年，f l o a t e r 在 6 】中提出一种新的b 一样条曲面曲 面重建的方法。它通过将原始数据点投影到平面参数域上进行参数化后，用b 一样 条曲面对原始数据点进行最小平方逼近，所得到的曲面就是重建曲面。 1 3 2 隐式曲面重建方法 虽然参数化表示具有许多优点，如计算曲线曲面的几何量简单，曲线曲面的显 示方便，可离散等优良性质等。但在另外的一些几何操作，如判断一个点是否在曲 线或曲面上以及在哪一侧时，参数表示曲面极为不便，与之相反，隐式化表示给这 些操作带来了极大的方便，同时，隐式化表示在曲线曲面求交方面也有极其重要的 应用。 1 9 9 1 年，m u r a k i 在【7 】进行的人头曲面重建中，提出了用分片隐式曲面作为工具 进行曲面重建的方法。1 9 9 2 年b 旬a j 等给出了插值给定网格的分片代数曲线片的 构造方法，并于1 9 9 6 年将分片代数曲面用于曲面重建( 【8 】、【9 】) 。1 9 9 5 年，s a p i d i s 等人在【1 0 】一文中提出了一基于区域增长的多项式曲面重建方法。2 0 0 0 年，z h a o 等 人在【1 1 一文中提出了基于类极小曲面模型( m i n i m a l s t 1 r f a c e l i k em o d e ) 和 p d e ( p a r t i a ld i f f e r e n t i a e q u a t i o n ) 方法的隐式曲面重建方法。2 0 0 1 年，c a r r 等人在【1 2 】 一文中提出了用多项式径向基函数( r b f , r a d i a lb a s i sf u n c t i o n ) 重建曲面的方法。同 年，z h o u 等人提出了一种用带指数函数的超二次曲面进行曲面重建的方法( 【1 3 】) 。 浙江大学硕士学位论文 1 3 3 变形曲面重建方法 近年来有人提出通过将事先确定初始拓扑结构构造的初始曲面，沿着一定的方 向进行形变，最终得到的曲面作为最终的重建曲面。它往往可以得到比较复杂的曲 面，但相对来说不容易控制曲面外形。 m i l l e r 等于1 9 9 1 年在文 1 4 忡提出了一种几何变形模型进行闭曲面重建。先将 一种小模型放入需要重建的闭曲面内部，然后让其膨胀变形，同时以要重建的曲面 上的采样点作为对膨胀变形的约束条件。当几何模型的变形达到某平衡点时，就 得到该曲面的数学模型。r u p r e c h t 和w i t k i n 等人在文 1 5 1 、 1 6 中则是通过赋予曲面 一定的物理属性，曲面的物理属性和外力的综合作用，使得曲面最终变形为所求的 重建曲面。t u r k 和o b r i e n 在文 1 7 1 提出了一类利用二维物体隐式形变技术对切片 数据进行曲面重建的方法。w h i t a k e r 和b r e e n 将l e v e ls e t 方法引入曲面重建当中， 提出了一类基于l e v e ls e t 模型的曲线重建方法( 1 8 】、【1 9 、【2 0 】) 。 1 3 4 分片线性曲面重建方法 分片线性曲面也称网格曲面。网格曲面作为一种曲面表示形式由于具有简单、 统一的优点，已成为一种重要的曲面表示方法。 1 9 9 2 年，h o p p e 在 2 1 1 0 0 提出。该文先通过采样点的切平面逼近待重建曲面的 局部模型，然后再得到它的三角片逼近曲面作为所需的重建曲面。1 9 9 8 年，a m e n t a 等在 2 2 1 中提出了一种基于v o r o n o i 图的网格曲面重建算法。2 0 0 1 年，b r a d l e y 在【2 3 中提出了一种依赖种子点增长的网格曲面重建算法。同年，f l o a t e r 提出了无网格参 数化地曲面重建算法( 【2 4 】) 。 1 4 细分曲面重建 为了解决曲面拼合的问题，人们提出并发展了细分曲面重建方法。细分曲面是 从初始的控制网格开始，按照某种细分规则，递归地计算新生成的网格上的每个顶 点和拓扑结构，而这些顶点都是原网格上的顶点的一个组合。随着细分的不断进行， 控制网格被逐渐磨光加密，对大多数的细分规则，这样细分无穷多次之后控制网格 将收敛到一张光滑曲面。细分最大的好处就是不受初始控制网格拓扑结构限制，可 应用到任意的网格上，而且细分是一种快速曲面绘制方法，特别适合计算机图形显 示，此外，细分曲面自然的拥有多分辩表示和显示的能力。因而广受人们的重视， 4 - 浙江大学硕士学位论文 不断发展和完善了细分曲面重建的方法。 最初期并不是从重建开始的，1 9 9 0 年，l o o p 和d e r o s e 在【2 5 】中研究了从多个 多边形的控制网格面片来构造b 样条曲面的方法，但没有应用到曲面重建中来。 1 9 9 4 年，h o p p e 等人在文 2 6 q a 提出了用细分曲面进行曲面重建的方法。该方法 分为三个步骤，首先，从初始的点集或几张独立的网格面片构造出初始三角网格， 也就是建立的初始的拓扑结构。然后，对优化该三角网格，减少三角网格的数目和 提高拟合的精度，这是可以省略的一步工作，但保留它的目的是它可以提高重建的 效率并且经过这个步骤的初始网格能有效避免奇异情况。最后这个步骤是其算法重 心，应用定义能量函数的方法并使用一些算子来调整网格，去构造一张细分网格， 最终输出控制网格的顶点数目、位置与连接关系。 1 9 9 4 年，l o u n s b e r y 等在 2 7 1 中研究了具有细分结构的网格的多分辨表示的问题， 1 9 9 5 年e c k 在【2 8 】去掉了这个限制( 细分结构) ，研究了任意网格的多分辨表示， 虽然他们的工作没有直接和细分重建相关，但其中的参数化的方法被广泛的应用在 以后的工作之中。 真正比较完善的工作是在1 9 9 6 年，e c k 和h o p p e 在 2 9 1 q h 提出了一种从三维扫 描点重建出张量积b 样条曲面的方法，这种方法可以应用到任意的拓扑结构上，并 且在内部拼台的地方达n tc 或是g 1 连续。其中的主要步骤有：最初和其他方法 一样也是要从扫描点中建立初始的三角网格，以此建立起初始的拓扑结构，在e e k 的工作 2 8 1 的基础上参数化初始三角网格，再将其转换到四边形网格，这是因为本 文要用b 样条来进行重建工作。由于原来的参数是建立在三角网格上的，因而随后 进行的工作是重新参数化四边彤网格。然后在每个小的参数域里构造张量积b 样条 曲面，最后进行误差计算，如果精度不够则将每个小参数域细分得更小，返回上一 个步骤( 重新构造b 样条曲面) 。 1 9 9 9 年，f f s a r n a v a t i 和r h b a r r e l s 3 0 开展进行了用最小二乘来反求细分规则 的研究，用细分矩阵写出了反求的误差表示，两后采用了类似小波的写法统一了细 分 次之后的误差表达式。因为细分矩阵不是方阵，所以这里的反求实际上通过计 算广义逆，或者说是用最小二乘的方法来计算的。但他们的工作仅限于曲线和棋盘 网格。 2 0 0 0 年，w , m a 和n z h a o 3 1 1 研究了c a t m u l l c l a r k 细分规则在逆向工程的应用。 他们把通过c t 扫描的数据建立起初始的拓扑结构，然后分割成几块基本的面片进 行参数化，最后也是用最小二乘来反求出c a t m u l l c l a r k 的控制顶点。 另外，还有人对如何用细分曲面拟台或插值散乱点进行了研究，用这种方法进行 浙江大学硕士学位论文 曲面重建的问题 3 2 。 由于计算机技术的进步和人们对细分曲面研究的进展，细分曲面重建因其造型的 任意性和丰富的表现能力受到越来越多的研究者的关注。 1 5 曲面简化 本文中结合了已有的c a d 中的一些方法来完成某些步骤，如用曲面简化 ( s i m p l i f i c a t i o n ) 方法来进行初始网格的轮廓抽取。曲面简化，是指对复杂的曲面 模型进行化简，减少曲面的数据量和数据模型的复杂程度。在保证定的精度下去 除网格中的不太重要的信息，以利于图形显示的实时性，数据存储的经济性和数据 传输的快速性。这几年来，结合曲面的多分辨表示而研究得比较多了。在现有的模 型简化方法中，比较有代表性的有以下几类方法： a 去点法。此法依据一定的判别准则来删除一些的采样点，同时删除了与点相连的 边和面，从而达到减少数据量的目的。s c h r o e d e r 3 3 在1 9 9 2 年提出平面准则， 即在局部范围内拟合一张平面，删除到该平面的距离小于指定精度的点，并对保 留的点重新三角化。类似地，h a m a n n 3 4 在1 9 9 4 年提出曲率准则，即删除曲率 小于指定误差的点。 b 去边法。该方法按一定的标准删除由曲面重建方法建立起来的网格中的一条边， 其做法是将要删除的边的两个端点合并为一个点，同时保持原来网格点之间的连 接关系不变。g a r l a n d 3 5 在1 9 9 7 年设计了一种二次误差矩阵，用作去除网格边 的准则。 c 优化法。t u r k 3 6 在1 9 9 2 年提出，在自由曲面重建方法建立起来的网格上重新 采样，并根据某种优化的准则，使采样点在网格面分布均匀，逼近误差减小。最 后对新的采样点进行三角化以形成简化的数学模型。 d 最大多边形法。k a l v i n 3 7 于1 9 9 6 年提出，在由重建方法建立起来的网格面上， 将在指定精度范围内可以近似地认为共面的相邻的三角形( 或多边形) 拼接起来， 形成一个最大的多边形，用每个最大的多边形构成曲面的数学模型。同年， c o h e n 3 8 x 将这种平面最大的多边形推广到曲面多边形的形式。 e 多分辨方法 2 8 1 。该方法也可称为多层次方法，它在逻辑上可以认为是替要重建 的曲面建立了一个从简单到复杂的数学模型的序列，人们可以根据需要选用序列 中的某一个元素表示的模型作为曲面的数学模型进行分析显示。模型序列中的各 元素之间具有递推关系。 - 6 - 浙江大学硕士学位论文 1 6 本文主要工作 从前面的介绍中可以看到，目前的细分曲面工作1 2 9 ，3 l 】大部分是围绕参数化展 开的，但这类方法大多是重建出b 样条曲面，不适合推广到任意的细分方法中去， 【3 0 】中提出的基于细分矩阵的方法却是可以推广到任意细分，但它又要求初始的网 格具有细分结构。为了对任意细分来研究其的细分曲面重建，本文在前人的工作基 础上，没有采用参数化的思想来调整网格顶点，而是基于细分矩阵来进行的曲面重 建的工作。因此本文所要解决的一个主要问题就是将初始的网格结构转换到具有细 分结构的网格结构，为此直接采用细分规则来生成细分结构，并对其进行调整以保 证和初始网格的近似性。 本文结合了c a d 中的成熟的一些方法来完成算法中的某些步骤，因而这也提供 了给用户更多的选择的机会，用户可以选择更新更好的方法来进行工作。为结合实 际的应用，本文提供的算法既可以由计算机自动完成也可以采用人机交互的方法来 优化算法，这一点可以在后面的实验结果中看到。 当然目前的工作还不够完善，现阶段的工作还只是应用在闭合的曲线、曲面上。 而且所针对的细分也是有所限制的，如果细分后顶点不能表示为细分前网格的顶点 的线性组合也不能应用本文的方法。 在第二章里，详尽的阐述了本文所提出的细分曲面重建方法的算法思想。围绕 着用细分矩阵来反求控制顶点这个问题，着重解决了具有细分结构的网格的生成， 介绍了反求时拓扑结构的建立方法。同时也定义了两张曲面之间的距离，用以后面 的误差控制。 从第三章开始，开始详细介绍算法中的各个步骤。这一章中介绍了重新网格化 的具体步骤，结合实例讨论了如何将已有的简化工作结合到本文的工作中来，并对 其做了一定的改进，然后重点介绍了重新采样的方法以及所需要注意的问题，最后 对特殊的奇异情况进行了初步研究给出了一定的解决方法。 第四章中，详细介绍了重建网格的具体步骤，结合c a t m u l l c l a r k 细分规刚介绍 了如何进行信息的保存和读取，以及如何反求出网格顶点和建立相应的拓扑结构。 在第五章里，以图例的形式给出了实验结果。对比了不同反求层次对重建精度 的影响，显示了重建出的网格与简化后的网格不同之处，示例了人工交互对细节保 护的优化。 第六章对工作进行了总结并探讨了以后工作的展开方向。 浙江大学硕士学位论文 第二章重建原理及算法流程 2 1 细分重建的相关概念 在建立自然物体的曲面模型的时候，要选择一种好的曲面模型来进行重建。细 分作为一种快速曲面绘制的方法和具有简单的网格表示在曲面表现形式上为我们所 看中，而且细分不受网格的拓扑结构的限制，可以应用到任意的拓扑结构上，是 种较理想的曲面造型方法。因此，我们选取细分曲面来做我们的造型工具，也就是 说，细分重建的目的是产生一张细分蓝面m 。b 来拟合通过对自然物体采样而得来的 网格曲面m 。通过检验两张曲面之间的距离是否小于我们事先给定的误差上限e ， 以此来衡量重建出的曲面是否真实再现了初始网格。 2 1 1 研究范围 本文研究的曲面为一个或是多个闭合的曲面，原因有两点：第一，细分的优势 就是可以作用在整个网格上，而不需要去考虑拼接问题，所以闭合曲面能极大发挥 细分的长处；第二，细分后的网格大多会有点收缩现象，如果不是闭合曲面还要考 虑修正边界等问题，为减少问题的复杂度，最终选择了闭合曲面作为细分重建的研 究对象。 此外对所研究的细分法则则要求细分后的网格的顶点是由原始网格的顶点的 线性组合而成的，显然的新的网格顶点仅仅由原网格的顶点坐标信息加上拓扑结构 信息就可以生成。其他的细分规则不在本文讨论范围之内，这主要是为了避免求解 非线性方程组。 2 1 2c a t m u l l c l a r k 细分 本文中的例子采用的细分规则为c a t m u l l c l a r k 细分规则，在这里简单的叙述这 个细分规则。 c a m m l l c l a r k 细分规则生成的顶点可以分成三类：新面点、新边点和新顶点。 对原网格中的面，新面点由该面的所有顶点平均而成；对原网格中的边( 非边界上 的边) ，新边点由该边的两端点和与该边相邻的两张面产生的新面点平均而成；对原 浙江大学硕士学位论文 网格中的顶点( 非边界上的点) ，新顶点定义为 ( ”一3 ) s 十2 e + f，其中n 为该 几 顶点的度数，s 为该顶点，e 为所有以s 为顶点的边对应的新边点的平均，f 为所有 以s 为一个顶点的面所对应的新面点的平均。 c a t m u l l c l a r k 细分规则生成的边有两类：一是连接莱一条边对应的新边点和与 其相邻的一张面的新面点，二是连接某一个顶点对应的新顶点和与其相邻的一条边 的新边点。 c a t m u l l c l a r k 细分规则将一张面对应的新面点和这张面中的一个顶点对应的新 顶点再加上这个顶点相邻的两条边对应的新边点组成新的面的顶点，它们之间的边 成为新的面的边。 以下是一张网格细分一次和四次之后的例子：( 黑线：原网格，灰色线：细分后 网格) 2 1 3 细分矩阵 所谓细分矩阵是指这么一个事实： 设原网格的顶点v ( o = b ，膨”，最；只o r 3 ) ，细分后的网格的 顶点v ( ) = ( 鼻”，碍”，碟1 ；只”r 3 ) ，般的；m n 。存在矩阵m + ( s u b d i v i s i o n m a t r i x 细分矩阵) 使得如下等式成立： ( 只。曩”，砭) = m + ( 只”，巧“，。爿。) t - 1 0 浙江大学硕士学位论文 2 1 4 网格曲面 这里所指的网格曲面是指一张网格所对应的某张曲面。网格最主要的元素是其 点、边和面，其中的点和边与平时所说的边点没什么区别，但其中的面则不同，比 方说，细分后的网格中的面，它其中的各个顶点是不一定共面的。网格中的面仅仅 是由网格中的顶点和边组成，构成它的边要求首尾相连，而构成它的顶点则是这些 边的两端的端点。如果网格中所有的面，它其中的所有顶点都是共面的话，网格曲 面则很好定义，可以看做是这些平面片拼合而成的曲面。如果不是的话，则需要先 将网格剖分成三角网格，因为三角形的顶点肯定是共面的，这样就可以用先前的方 法来定义网格曲面了。网格曲面：将网格剖分成三角网格，由这些三角网格中的三 角面片拼合而成的曲面称为原网格的网格曲面。需要注意的有两点，第；剖分成 三角网格后对原网格顶点还是插值的，这样避免了信息的失真；第二；由于剖分的 方法有很多，所以一个网格的网格曲面也不是唯一的，在我们的研究中，任何一个 都可以作为代表。 2 1 5 具有相同的拓扑结构的网格 假设有两张网格m l 和m 2 ，如果存在映射中使得m l 和m 2 中的 页点、边和面 能一一对应，则称m l 和m 2 有相同的拓扑结构，具体的定义是： 如果 对任意的顶点只属于m l ，存在m 2 中的顶点q ：使得：异= 中1 ( d ) ； 对任意的顶点q 属于m 2 ，存在m l 中的顶点只。使得：q i = e p ( 只) ； 对任意的m j 中的边( 只，只) ，存在m 2 “o 的g l ( q i ，q j ) 使得： 只= m 。1 ( q j ) ，只= m ( q ：) ； 对任意的m 2 中的边( q f ，q ，) ，存在m i 中的边( e ，爿) 使得： q 2 0 ( # 。) ，92 0 ( 巧) ； 对任意的m l 中的面( 置 ，i k e n ，存在m 2 中的面 或) ，i k e n 使得； 丘= o 。( q ) ，i k e n 浙江大学硕士学位论文 对任意的m 2 中的面 q ) ，i k e n ，存在m i 中的面 最 ，i k e n 使得 g = m ( 最) ，i k e n 则称m l 和m 2 有相同的拓扑机构。 下图中的两张网格就是具有相同的拓扑结构的。 2 1 。6 具有细分结构的网格 严格的来说，应当称之为对某种细分来说具有细分结构，因为在整篇文章中都 假定事先已经选好了某一种细分法则，所以就简单说某张网格是( 对特殊已经选定 好的细分) 具有细分结构的。那到底什么叫具有细分结构，假设m 。是某一张网格， 如果存在网格m b 使得，m b 依据细分法则细分后生成的网格与m 。有相同的拓扑结构， 则我们称m 。( 对这种细分) 具有细分结构。举个例子来说，我们知道c m m u l l - c l a r k 细分作用到任意的拓扑网格上后，所有的面均变为四边形，也就是说，如果网格m 。， 它其中的只要有一个面不是四边形的话，就不可能找到网格m b 使得m b 作用 c a t n l u l l 。c l a r k 细分一次后能和原来的网格m 。有相同的拓扑结构。如下图。 浙江大学硕士学位论文 9 对 无 细分结构是和特定的细分有关系的，也就是说，一张网格对某种细分是具有细 分结构的，但可能对另一种细分不具有细分结构。为此，介绍另一种中点细分方法， 具体规则是对每个顶点，在以该点为一个顶点的面内连接以该顶点为端点的两条边 的中点。如果该顶点在边界上，则还要连接在边界上的两条边( 只有一张面与其相 连) 的中点，对每个点和面，将与其相连的边产生的新边首尾相连产生新的面。下 圈中右边的网格对c a t m u i l c l a r k 细分可以找到作用前的网格，但对中点细分就不能 找到作用前的网格了。 9 对中点 作用前 来简单证明这个事实，先看一张中点细分的例图( 下图中( 1 ) ) ，看看中点细分 网格是怎么来构造的。 浙江大学硕士学位论文 为了检验所得到的细分曲面m 。b 与网格曲面m 。，。之间的近似程度，需要定义一 个距离来描述两张曲面之间的近似程度。 首先定义点到曲线( 曲面) 的距离； 点到曲线( 曲面) 的距离是它和曲线( 曲面) 上任意一点的距离的最小值。 再来定义距离函数d ，它有两个变量，但必须同时是曲线或曲面，具体定义见 下： 先说曲线吧，假设f ，g 是两条曲线，则这两条曲线之间的距离d ( f ，g ) 定义为； d ( f ，g ) = m a x ( 、m 。盯a x 留阶一p g l ，磐物l p f p s i ) 换句话，也可以说是一条曲线上的点到另一条曲线的距离的最大值。 浙江大学硕士学位论文 因为一般来说学字m 咚e g i n p r pg | 并不一定会等于翟亭考守i p r p g i ，所以 要在前面加个m a x 。具体例子可以参看下图。 这时，上面那条直线上的点到下面那条折线的距离的最大值是li ，而其实它们 之间的距离最大应该是2 。 有了曲线的例子，就比较容易想象曲面的定义了，形式上和曲线一样： 假设f ，g 是两张曲面，s 是它们的定义域，则这两条曲面之间的距离d ( f , g ) 定义为： d ( f ，g 1 2 m a x ( p m f 。a x 馏盼p 。j ，惨静p f i ) 同样可以成说是一张曲面上的点到另一张曲面的距离的最大值。 用d 来刻画曲线和曲面之间的距离是因为，如果曲线f 和g 之间的距离小于a m i 。 则g 被包含在f 的等距距离为的两条等距线之间。否则，如下图，如果有点在 等距线之外，则这点到f 的距离大于m 。与假设矛盾。曲面的情形类似。 s o m ep o i n t0 u t 2 2 细分重建的原理 细分曲面重建的主要思想是将细分的过程反转，反求出细分的控制网格，以控 制网格细分出的曲面作为原始网格的逼近。 本来细分是从初始的比较粗略的网格结构通过逐步的细分，每一次都是对上一 次产生的网格细分加密，最终产生了细致精密的网格结构用以表现三维物体。相反 的，反求的过程是从初始已经比较细致精密的网格结构出发，通过寻求其上一次细 浙江大学硕士学位论文 分时的网格结构，最终得到一个比较粗略的控制网格。显然的，数据量的减少必定 会带来一定的误差，用反求出的控制网格去细分生成的曲面肯定会与初始网格有着 一定的误差，但只要初始的网格比较好( 比方说原本就是细分产生的网格) ，这个误 差是比较小或者说是可以容忍的。 重建的一个目的也是为了减少原始的数据量，这点没问题，反求后的网格数据 要比反求前的少。衡量重建的唯一标准是拟合的精度，这点也可以解决，在最坏的 情况下，特别是当要求误差很小近乎于零时，只能输出初始网格，这时候没有反求 过控制顶点，这时候误差也为零，否则通过次次的反求计算误差，一旦发现超出 就停止，以此来确保的拟合精度。 重建后的网格不光光是数据量减少了，而且重建后的网格结构要简单得多。对 重建后的简单网格的操作或编辑可以直接影响到重建出来的细分网格，很适合用做 人机交互时物体的外形轮廓，通过简单操作重建后的网格来影响最终生成的曲面。 而且，用细分重建出来的模型先天就具有了多分辨表示的能力，最初的重建出来的 网格是最粗略的网格轮廓，每细分一次就使网格细致了一些，可以看做是分辨率的 增高，如果无限细分下去得到的是一张光滑的细分曲面。 2 2 1 前期准备工作 在进行曲面重建之前，得先对自然物体进行扫描，以获得要重建的网格的原始 顶点数据，还得建立其初始的网格拓扑结构，一般是将其连接成为三角网格，这里 有许多前人的工作，大体上分成这么三类；基于面的方法 3 9 1 1 4 0 ，基于体方法 2 2 ， 4 l ，4 2 ，4 3 】和轮廓跟踪法 2 1 。因而，本文的基础是已经有了初始的网格结构，记 为初始网格m 。 在取得了初始网格结构之后，我们就要寻找一张细分曲面m 。b 去重建出初始网 格m s 。前面我们提到过，重建的过程中要寻求上一次细分时的网格结构，然而， 不是所有的网格都可以找得到的，具有这样性质的网格称为具有细分结构的网格。 因为细分曲面重建需要初始网格具有细分结构，一般来说，对某张网格去判定 是否具有细分结构也是很困难的，4 4 g t a u b i n 就1 4 的细分做了判断工作。更难去 寻找其细分的上一层网格结构了，因而本文选择了在重建之前得先把采样后的初始 网格m s 。转换成具有细分结构的网格。这也将是本文着重要解决的问题。而这个过 程在图形学中称为重新网格化( r e m e s h ) 。 浙江大学硕士学位论文 2 2 2 重新网格化 重新网格化的工作是将一张网格转换到另一张网格，同时要求转换后的网格具有 一定的拓扑结构或性质。在这里的要求就是要转换后的网格m 。具有细分结构同时 保持和初始网格m s ，。的足够近似。 e c k 4 5 、k o b b e l t 4 6 】、l e e 4 7 等人在讨论了在参数域内对曲面网格的重新网格 化。本文所提出的方法从一个初始的轮廓网格出发，通过逐步细分投影的方法生成 一张细分网格，因为它本身就是通过细分产生的网格，自然而然的具有细分结构， 面将其投影到初始网格上只是改变了顶点的位置，不会改变网格的拓扑结构，投影 的目的是为了保证了与初始网格的近似性。这样就形成了所需要的具有细分结构的 网格m 。 初始的网格 轮廓网格 细分后的网格投影后的网格 孕矿 应该说，这样的想法很简单但也很自然。既然重建的时候是不断反求出上一层的 网格，那么总会有一次到头的，也就是说，总有反求到不具有细分结构的网格或是 保持拓扑结构不变的网格，那么事先假定已经知道了这么一个网格( 轮廓网格) 。 轮廓网格是对原始网格m s ，。的一种近似，它体现了原始网格的外貌的大体影象， 可以人为给定也可以通过一定的算法由计算机自动完成。有关内容将在以后详细说 明。 因为这个轮廓网格是事先假定的，而且也是通过其他途径给出来的，所以它细分 出来的细分网格一般不会是所要求的那个细分网格m 。，考虑到m 。的两大主要特 征：细分结构，与原始曲面的距离小于给定的e 。细分结构好说，细分后的网格本 身就是通过一步步细分出来的，自然的具有细分结构。要使得和原始曲面近似，所 采取的方法是不断将其投影到原始曲面上，需要注意的是细分一次投影一次。这样 才可以不断逼近原始网格，看下图。 浙江大学硕士学位论文 细分虽然可以不断的加密网格，但一般细分后的顶点不会跑动太远( 有一个范 围) ，如果只投影一次，则有些死角永远也无法投影得到，所以需要多次投影。 这个过程中还要记录下细分矩阵和网格的拓扑结构信息，为的是在后面重建的时 候准备必要的资料。 这个过程什么时候结束昵? 当投影后的网格产生的细分曲面与原始网格曲面的 距离小于给定e + 的时候就可以结束了，这里要说明的是e + 一般会取得比e 小，这 样给我们优化结果留有一定的空间。这个过程一定会结束吗? 答案是和投影时的法 向的取法有关，这个问题我们将在后面做进一步解释。 9 2 3 重建网格 作为细分网格重建，最后输出的网格应该是细分曲面的控制网格，它细分后产生 的细分曲面在一定精度e 内来拟合初始网格m s 。的网格曲面。