（计算数学专业论文）离散曲面四边形剖分的组合优化及实现.pdf

大连理工大学硕士学位论文 摘要 计算机科学的迅速发展使得网格技术越来越广泛的应用于解决实际问题，因此网格 生成技术逐渐成为人们关注的课题。开始时人们把大量的工作放在了三角形网格上，但 是三角网格有其自身难以克服的缺陷。事实证明四边形网格可以有效的减少数据量，另 外四边形网格在p d e 方面，特别是流体力学方面也更加受欢迎，所以对于高质量的四边形 网格需求是迫切的。然而一般情况下，传统的四边形网格生成算法所生成的网格并不是 最优的，因此需要对网格进行优化改善。 在本文中我们首先对网格质量的评价标准做了简单的说明，接着我们对比较经典的 的四边形网格生成技术做了一下较为简略的陈述，随后我们按照重网格化方法的最终目 的对它们进行了较为详细的介绍，最后我们通过本文引入了一种新的四边形网格优化算 法。该算法主要是利用四边形本身的形状来对顶点施加一定的能量，并反过来利用这个 能量来改善四边形的形状，并且排序之后迭代若干次，以便达到局部的改善四边形剖分 的目的。 关键词：四边形网格；重网格化；图形图像；网格优化；离散曲面 离散曲面四边形剖分的组合优化及实现 t h er e s e a r c ha n dr e a l i z a t i o no ft h ec o m b i n a t i o no p t i m i z a t i o nf o r q u a d r i l a t e r a lm e s h o nd i s c r e t es u r f a c e s a b s t r a c t a sar e s u l to ft h er a p i dd e v e l o p m e n to ft h ec o m p u t e rs c i e n c e ，t h er e l a t e dt e c h n o l o g i e s a b o u tt h em e s hb e c o m em o r ea n dm o r ew i d e l yu s e dt or e s o l v ep r a c t i c a lq u e s t i o n s ，s ot h e m e s hg e n e r a t i o nt e c h n o l o g i e sr u mi n t oah o tt o p i cg r a d u a l l y a tt h eb e g i n n i n gp e o p l eu s e dt o p a yt h e i rm u c ha t t e n t i o na tt h et r i a n g u l a t i o no ft h es u r f a c e ，b u t i th a sb e e np r o v e dt h a t t r i a n g u l a t i o nh a ss o m ei n t r i n s i cd i s a d v a n t a g e st h a tc a n n o tb ec o n q u e r e d o nt h ec o n t r a r y q u a d r i l a t e r a lm e s hc a nn o to n l yr e d u c et h ea m o u n to fd a t a , b u ti ti sm o r ep r e f e r r e da tt h e s u r f a c ep d ep r o b l e m s ，e s p e c i a l l yf l u i dd y n a m i c s ，s ot h er e q u i r e m e n to fh i g h q u a l i t y q u a d r i l a t e r a lm e s hb e c o m e su r g e n t b u tu s u a l l yt h eq u a d r i l a t e r a l m e s h e sg e n e r a t e db y t r a d i t i o n a lm e t h o da r en o tq u a l i f i e df o rt h e i rp u r p o s e ，s ot h e yn e e dt ob eo p t i m i z e d a tt h eb e g i n n i n go ft h i sp a p e rw eg i v eab r i e fd e s c r i p t i o na b o u tt h ee v a l u a t i o nc r i t e r i a a b o u tt h eq u a l i t yo ft h em e s h t h e nw eg i v eac o n c i s ei n t r o d u c t i o na b o u tt h ec l a s s i c a lm e s h g e n e r a t i o nt e c h n o l o g y ，s u b s e q u e n t l yw eg i v eaq u i t et h o r o u g hs t a t e m e n ta b o u tt h er e m e s h i n g m e t h o da c c o r d i n gt ot h e i rp u r p o s e ，a n da tl a s ti n t r o d u c e dan e wo p t i m i z i n ga l g o r i t h mb yt h i s p a p e r 1 1 1 ea l g o r i t h ma i m st oe n d o wt h ev e r t e xa ne n e r g y t h a tc r e a t e db yt h ea d j a c e n t q u a d r i l a t e r a l s ，a n dt h e nc o n v e r s e l ym o v et h ev e r t e xt o am o r ea p p r o p r i a t ep l a c eb yt h e o b t a i n e de n e r g y 1 1 1 el a s ts t e po ft h ea l g o r i t h mi sa ni t e r a t i v ep r o c e d u r ea f t e rt h es o r t i n go ft h e v e r t e x e s ，a n dt h e nw ec a na c h i e v et h eg o a lo fo p t i m i z i n gt h eq u a d r i l a t e r a lm e s hl o c a l l y k 锣w o r d s ：q u a d r i l a t e r a lm e s h ；r e m e s h i n g ；g r a p h i ci m a g e ；m e s ho p t i m i z a t i o n ；d i s c r e t e s u r f a c e 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所敛的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目差塑塑血叟壁基塑1 幺至渔虹堡堡圣型 作者签名： 矗墨缸日期：二讼4 年上月兰翌日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 引言 近几年来，随着激光测距扫描等三维数据获取硬件技术的日趋完善，人们可以得到 精度和密度都越来越高的物体表面三维数据，与此同时利用从物体表面三维数据( 点云) 来建立真实的物体数字模型，也就是反向工程成为近年来国际图形学界的一种发展趋 势。 这里所谓的点云是一种形象的说法，点云直观的说明了有关样本点的数据是海量 的，像一团云彩一样稠密。显然这种数据形式是无序的，即点与点之间的邻接关系并不 清楚，因此既不便于保存又不便于处理。而要在三维空间中重现物体，把这些从物体表 面取样所得的散乱点集重新恢复成原来的曲面，需要在点云的基础上生成网格。开始时 人们把大量的工作放在了三角形网格上，目前为止三角形网格的生成算法也已比较成 熟，但是由于三角网格包含的数据量较大，因此它具有存储空间大，数据传输较为困难， 不方便处理等缺点。而利用四边形网格可以有效的减少数据量，另外四边形网格在面p d e 方面，特别是流体力学方面也更加受欢迎，所以对于比较成熟的四边形网格的生成算法 的要求是迫切的。四边形网格生成技术的研究从2 0 世纪8 0 年代以后越来越受到人们的 重视，并且逐渐成为研究的热点。经过国内外无数学者合工程技术人员的共同努力，涌 现出了很多的算法，然而一般情况下，传统的四边形网格生成算法所生成的网格并不是 理想的，并且其中往往包含一些质量较差的单元，因此需要一些优化算法对网格进行优 化改善。 离散曲面四边形剖分的组合优化及实现 1网格相关信息简述 随着激光测距扫描等三维数据获取硬件技术的日趋完善，人们可以得到精度和密度 都越来越高的物体表面三维数据，而要在三维空间中重现物体，把这些从物体表面取样的 散乱点集重新恢复成原来的曲面，需要在点云的基础上生成网格。这里首先对网格的相关 知识点进行一下简单的论述。 1 1网格的分类 工程应用中，有限元网格主要有两种：一种是结构化网格，另一种是非结构化网格。 从严格意义上讲，在结构化网格中，所有内部结点都有相同数量的邻近结点和相同数量 的邻近单元，即所有的内部结点都具有相同的度。在平面和空间曲面网格生成中，有代 表性的结构化有限元网格是由四边形单元构成的网格：在三维实体网格生成中，有代表 性的结构化网格是由六面体单元构成的网格。在结构化有限元网格生成方法中，映射法 是典型和通用的方法，它既可以被用来生成结构化的四边形单元网格，也可以被用来生 成结构化的六面体单元网格。结构化网格的优点是：它可以很容易地实现区域的边界拟 合；网格生成的速度快，质量好；数据结构简单。它的最大的缺点是适用的范围比较窄， 对于比较复杂的区域或者物体表面很难生成高质量的计算网格。目前高效的全自动结构 化网格生成方法还正在研究当中。在非结构化网格中，对结点放松了要求，允许任意数 量的单元在一个结点处交汇，即所有内部结点的度都可能不同。在平面和空间曲面的有 限元网格生成中，非结构化有限元网格的典型代表是三角形网格：在三维实体有限网格 生成中，非结构化有限网格的典型代表是四面体网格。非结构化网格生成方法的一个突 出的优点是它可以适应任意复杂的几何形体，与几何形体的形状关系不大。结合一定的 控制方法，可以生成质量很高的单元，而且利用非结构化网格生成算法可以实现区域网 格生成的自动化。值得一提的是，三角形单元和四面体单元并不是非结构化有限元网格 的唯一选择，由四边形单元或六面体单元构成的有限元网格只要结点的度有所不同，此 时的有限元网格仍然是非结构化网格。 1 2 网格的质量评价准则 网格的质量是指网格几何形状的合理性，它的好坏将影响到计算精度，质量太差的 网格甚至会中止计算。直观上看，网格各边或各个内角相差不大、网格面不过分扭曲、 边结点位于边界等分点附近的网格质量较好。网格质量可用细长比、锥度比、内角、翘 大连理工大学硕士学位论文 曲量、拉伸值、边结点位置偏差等指标度量。上述规则既适用于基于特征的四边形网格 生成三角形网格，也适用于四边形网格。下面我们仅对四边形网格的质量评价准则加以 简单介绍。 1 2 1 拓扑准则 拓扑准则可以用下面的度量来表示： 毛= 专舢v 删i ( 1 1 ) 其中d ( v ) 表示结点的度( 相邻结点的数目) ，n 表示网格结点的总数。如果v 为内 部结点，则d = 4 ；若e 为边界结点d = 3 。如果一个网格其拓扑结构比较规则，则度量 值接近于0 。然而那只是理想的情况，实际应用中它一般为一个正值，表示实际网格拓 扑结构和理想拓扑结构之间的差距。很显然，在网格结点数一定时，该值越小，则表明 网格越规则。 1 2 2 几何准则 1 三角形的口因子 三角形a b c 的o g 因子定义如下： 口c 彳占c ，= 2 ；i = 五萄产 赫 c1 2 ) 其中二是这个三角形的单位法向量，系数2 ；是为了使正三角形的口值取最大值1 ， 口因子的直观意义就是三角形面积与边长平方和之比，0 口1 。口越大，表明三角形 的质量越好。 2 四边形的因子 四边形单元的形状质量评价准则通常使用系数。四边形a b c d 的两条对角线将其 分割成四个三角形a , 4 b d 。& 4 b c ，a c d b ，a c d a ，令 口，鸭，) = 口( 彳丑d ) ，a ( a b c ) ，o t ( c d b ) ，a ( c d a ) ) ( 1 3 ) 假设有q 口2 a 4 ，则四边形a b c d 的系数定义为 口：竺 ( 1 4 ) 口1 口2 其中，凸四边形的值在0 和1 2 _ 间，矩形的值有最大值1 。当四边形退化为三角 形时，值为0 ，凹四边形的值小于0 。 3 网格的评价标准 离散曲面四边形剖分的组合优化及实现 基于三角形的口因子和四边形的因子，l e e 和l o 给出了三角形和四边形网格的质 量评价因子 云：淌口 万：( n n o 屈) 面i 其中a r t 和分别为三角形和四边形的数量。 ( 1 5 ) ( 1 6 ) 大连理工大学硕士学位论文 2 四边形网格生成方法简介 四边形网格生成技术的研究从2 0 世纪8 0 年代以后越来越受到人们的重视，并且逐 渐成为研究的热点。经过国内外无数学者合工程技术人员的共同努力，涌现出了很多的 算法，这些算法按照生成原理可分为直接方法和间接方法。 直接方法就是在给定的几何区域上直接生成四边形网格，直接方法按照网格的生成 过程又可以分成两大类：几何分解法与利用推进前沿技术的方法。 所谓几何分解法即把一个区域分解成一些简单的凸子区域或者是可映射的子区域， 然后在这些子区域上生成四边形网格。b a u m a n n 等人首先把四叉树方法应用于区域分 解，在经过初始分解后根据区域局部的情况将二维空间分解成一棵四叉树。四边形网格 在各叶子结点生成，调整结点位置使其可以更好地拟和边界。t a l b e r t 和p a r k i n s o 等人随 后又引入了另外的一种分解技术：将区域递归地分解为简单的多边形区域，当这些多边 形满足一定的模板时，就可以通过剖分这些模板来实现整个区域的四边形网格生成，即 l o o p i n g 方法。国内刘阳借用p a v i n g 算法的边界拟和好的优点在边界处生成一圈单元来 改善l o o p i n g 方法生成网格在边界处的质量。郭晓霞等人【2 】对该方法生成四边形网格 中的边界偏移、最优分割线确定等关键技术做了改进。t a m 等人则引入了中轴技术，这 类方法可以生成全四边形网格，网格质量也比较高，但是需要更多的人工干预，自动化 程度不高。 e h i n t o n e t a l 等人最先把推进前沿技术( a d v a n c i n gf r o n tt e c h n i q u e l 应用到了四边 形网格的生成方法中，从边界开始向内部逐个或逐层生成四边形网格。该方法首先在边 界上布点，然后利用边界向内部投影的方法生成三角形网格，每生成两个三角形网格就 将其合并，从而得到一个四边形网格，但是该方法得到的四边形质量缺乏保证，因为两 个高质量三角形单元合并以后得到的四边形单元合并以后得到的四边形单元质量并不 一定好。b l a c k e r 等人在方法的基础上提出了改进，从而提出了著名的p a v i n g 方法。p a v i n g 方法从区域边界向内部逐个生成四边形单元，在网格生成过程中要不断进行冲突检测， 交叉和特殊情况的处理直至生成全四边形网格。该方法生成的网格具有边界敏感性和方 位不敏感性的优点，并且能极大地减少网格中的不规则点。p a v i n g 方法目前已经被应用 在一些商用软件中，如m s c p a t r a n 等，但是该方法也有不容易克服的缺点，例如当目标 区域边界非常复杂时，很容易出现大量交叉，而交叉判断和处理既复杂又耗时，处理不 好还会造成算法的不稳定。基于栅格方法( g r i d b a s e da p p r o a c h ) 也是一种比较经典的 直接生成四边形的方法。该方法又被称为反p a v i n g 方法，该方法首先将一完全包含目标 区域的正则栅格( 一般为矩形区域) 放置在目标区域上面，除去落在目标区域之外的栅 离散曲面四边形剖分的组合优化及实现 格单元，并对与物体边界相交的栅格单元进行调整或剪裁以便更准确的逼近目标区域。 然后将这些栅格但愿按一定的样式分成一定数量的网格单元，之后通过光滑技术处理即 得到最后的网格。对于生成大量网格其效率一般要高于其他方法，如p a v i n g 方法等，但 是其不足之处在于所生成的网格与所选择的初始栅格及取向有关，另外网格边界单元的 质量较差。 间接方法就是首先在给定的几何区域上生成三角网格，然后再将该三角网格转化为 四边形网格。生成三角网格时可以采用任何一种己经很成熟的三角形网格生成方法，如 d e l a n e yt r i a n g u l a t i o n a d v a n c i n gf r o n tt e c h n i q u e 等，然后再将该三角网格转化为四边形 网格。此类方法主要有简单拆分方法和合并法。所谓拆分方法，就是取每个三角形的重 心和三边中点的连线把每个三角形分成三个四边形。该方法虽然实现了全四边形网格的 自动生成，但是由于产生了大量度为三的不规则结点，因此最终得到的网格质量很差。 合并法就是两个或多个相邻的三角形合并成一个四边形。l o 首先给出了一个简单的合 并方法，得到了一个既有三角形网格又有四边形网格的混合网格。j o h n s o n 等人通过引 入局部网格的拆分( s p l i t t i n 9 1 和交换( s w a p p i n g ) 策略来进一步提高四边形的数量和质 量。l o 和l e 则通过引入系统合并技术( s y s t e m a t i c a lm e r g i n gt e c h n i q u e ) 来生成全四边 形网格。结合s m t 和p a v i n g 方法m l s t a t e n 等人提出了全四边形网格自动生成的 q m o r p h 方法，该方法时目前间接方法中比较好的一个，因此被应用在很多的商用软件 中，如e f a 等。l e a k y 和l a c k 给出了各向异性四边形网格的生成方法。顾元宪【5 等 人通过改进网格生成的布点方法，首先生成三角形网格，然后再将其转化为四边形网格。 由于该方法在生成三角形网格时就考虑到了将来得到的四边形的质量，因此可以提高生 成四边形网格的质量，但网格质量仍然有待提高。 间接方法的有点是由于所有操作都是局部的，不像有些直接方法那样需要进行全局 交叉检测，因此网格生成速度很快，此外结合比较成熟的三角网格生成方法，可以实现 对任意复杂区域的四边形网格生成，缺点是有很多不规则结点产生，而且即使不规则结 点很少时也不能保证具有很好的边界拟和性，而这在有些应用中是很重要的。 总之，通过上述简单的综述我们可以看出：直接方法和间接方法各有优缺点，因此 用上述算法生成的网格一般并不是最优的，其中往往包含一些质量较差的单元，因此网 格优化技术就显得尤为必要。 大连理工大学硕士学位论文 3 重网格化技术简介 重网格化技术不仅对于显现过程是有价值的对于编辑动画处理存储以及传 辅过程同样也存在价值。由于以上这些原因，近几年来面重网格化技术越来越受到人们 的广泛关注。 事实上重网格化没有一个严格的定义，这是因为按照不同的目的和应用它的含义 不尽相同。虽然如此我们还是可以给它一个简单的陈述：给定一个3 d 呵格，计算出另 外的一个网格，新网格必须满足一定的质量要求，同时和输入匹配电好。这里的“质量” 有几种含义，它租暇样，梯度，正规性，大小，以及网格巾元素的形状都有关系。现实 应用中的标准通常是这几种指标之间的组台。一部分重网格化技术是通过调整输入实现 的，还有一些是通过派生出一个新的网格实现的。 罔3l 几i 可模型的均匀重阿格化( 图片参考文献1 4 ) 开g3l u , l i f o r mr e m e s h 吨o f t l - , e g m “c m o d e l ( r e f e r l 4 ) 仅凭以上蛤出的定义很难使得读者对重网格化技术有深层的了解为了使读者对堑 网格化技术的意义了解的更加透彻这里对重网格化过程所精要考虑的问题做一个简单 的陈述。 ( i ) 合法性：网格必须是一个合法的网格这意味着它必须是一个简单的流形。 此外通常情况下它所处理的阿格必须是封闭的即不能含有边界。 ( 2 ) 质盈：同格单位元的质量对于鲁棒性阻及数值稳定性是相当重錾的，而这两 点性质对于数值模拟以及几何处理都足必要的。数值计算例如有限元分析需要在几 何和连接关系方面都相当规则的网格。这些同格被闩j 米计算机械压力或者被用来解热最 和其它的微分方程。要求高质量的回格能够尽可能的减少数值误差和奇异性。 离散曲面四边形剖分的组合优化及实现 ( 3 ) 保真性：新产生的网格必须能够很好的逼近原始的几何形状，同时在给定的 预算下保持网格的复杂性。理想状况下，对于待解决的问题有“恰好足够”的解。这包 括误差度量的选择，以及在插值和逼近之间的选择。 ( 4 ) 离散输入：输入是按照离散网格的形式给出的，这些网格通常是一些( 未知) 连续形状的近似。当离散化不理想的时候，通过这种离散的近似去做一些原始形状的探 究工作( 法线、切平面、曲率估计等) 是相当困难的。除此之外，通过重构算法从点云 派生出来的网格可能很难区分形状近似的物体并且往往缺少原始形状所包含的重要信 息。 ( 5 ) 巨大的数据集合：在使用现代的3 d 扫描仪的时候，为了不遗失重要的信息 往往会提高取样的比率，而这会产生巨大的数据集合。这样取样和分割相对原始形状来 说就会变的不敏感，并且数据集合中会有大量的冗余数据。 ( 6 ) 不可预测性：通过各种手段获得数据的过程往往会受到其它的因素影响，比 如通过激光扫描仪扫描的过程就容易受到扫描过程中产生的电子的，机械的，甚至是视 觉的噪声影响。 ( 7 ) 对应性：对所有的重网格化技术来说一个普遍的核心问题就是在输入的网格 表面上寻找到一个新点的对应位置。这种对应通常是通过计算一个输入网格的参数化来 寻找到的。这种计算一个非常复杂的问题，因为它或者使得计算所付出的代价很大，或 者准确度不够高，或者需要对网格加上很多的限制。这个问题在在2 d 参数化区域进行 重网格化工作的时候尤为突出，因为从3 d 结构( 有可能是带有任意个数的亏格和洞) 到2 d 区域的映射往往会使得很多的测度变的扭曲，并且有可能会遗失很多重要的信息。 更进一步说，如果参数化和网格划分结合在一起，在片的边界处很有可能会遇到困难。 其它的无参方法直接的在原始表面上做工作，在网格的局部做一些调整( 比如增加、减 少或者重定位一些点) 。通过这些调整，网格的顶点被保留在原始的输入网格上，这种 类型的方法可以在很多不同的技术中找到。这些优化工作或者在3 d 上进行( 此时计算 复杂度很高) ，或者在切平面上进行( 此时计算会较快，但是准确度不够高) 。通过采 用局部操作，这种方法可以避免在整体操作上的缺陷；2 d 上的重网格化技术也要比3 d 上的优化算法快很多。由3 d 网格到2 d 参数化区域的映射所产生的扭曲也可以通过重 叠片技术有效的减少：误差累计( 通常是由局部操作引起的) 也可以通过时常与原始几 何图形的一个参考光滑近似或连续片比较有效减少。 下面就对目前比较成熟的重网格化技术做一些陈述，为了使报告的结构尽可能的清 晰，我们这里并没有按照重网格化技术所采用的方法进行分类，而是按照它们的最终目 大连理工大学硕士学位论文 的进行了分类。我们把它们归为5 类：有结构的重网格化、兼容性重网格化、高质量重 网格化、特征保留重网格化、误差驱动重同格化。部分重网格化技术可能由于他们目的 的多重性在几部分重复出现。 3 1 有结构的重网格化 定义；有结构的蕈网格化就是用一个有结构网格代替原先输入的无结构阿格。在一 个有结构的网格( 有时被称作正规网格) 中。所有的位于内部的点都被一定数量的单元 所包围。一个半正规的网格是通过对一个非正规的网格的细分得到的。在一个半正规的 网格中除了少数奇异点之外所有的点都是正规的。一个高度正规的网格中绝大部分点都 是正规的，但是这种网格不一定是通过细分得到的。 动机：与无结构网格相比有结构韵网格有某些优点。它们的连通图像相对简单，这 就使得可以在算法中有效的进行传输以及定位。半正规网格( 必须是分片正规同格) 提 供了在结构化网格的简化以及无结构网格的灵活性之问的一个过渡性的平衡。 9g9 非正规网格半正规网格正规同捂 r r e g a l a r m e t , ；1s e m i - m g u l a r m e s hr e g u l a r m e s h 圈32 ( 图片参考文献l 神 f i 9 32 ( r e f e rx s ) ( 1 ) 半正规：半正规网格是通过对原始网格递归的细分得到的。它们分层次的结 构使得它们对于多分辨率的分析( 通过减少样本点以及光滑化简化) 和综合( 细分以及 增加细节) 是相当理想的。已经证明它们在模型光滑、表面分片光滑、反向工程、多分 辨率分析以及建模、编辑和可视化方面是很有价值的。 o 龄蛰蛰0 离散曲面四边形剖分的组合优化及实现 图3 3 通过对原始网格正规细分得到的半正规网格( 图片参考文献1 5 ) f i g 3 3s e m i r e g u l a rm e s ho b t a i n e db yr e c u r s i v es u b d i v i s i o no f a ni n i t i a lb a s em e s h ( r e f e r15 ) 几何处理领域的兴起使用了大量的半正规网格。对于正规的均匀结构有一些经典的 数字信号处理方法( 比如离散傅立叶变换) ，几何处理方面有一个基础性的问题就是是 否能够在非正规非均匀的环境下应用这些方法。到目前为止这个问题仍然没有彻底解 决，并且现有的解决办法都是将原有的形状进行半正规重网格化。这样就可以把几何的 “信号”分割成正规的均匀的片。其中一个几何处理方法就是给出一组用来均衡化和光 滑化的离散算子，而这些算子仅适用于正规并且均衡的环境。 按照寻找输入和输出网格之间如何对应的方式，主要的半正规重网格化技术可以被 划分为两类。第一类技术是通过参数化的方式寻找它们之间的一个互相对应。这类技术 之间的不同主要体现在参数化的方式的不同上。 第一种参数化的方式就是把整个的输入网格映射到一个全局的平面区域上。然后在 参数化区域上进行重网格化，最后把新生成的网格映射到原先的3 d 空间，通过这种方 式就可以改善原先输入的网格。这种方式最大的缺点就是它对参数化的方式很敏感，并 且很容易扭曲度量( 这主要是因为3 d 结构被强行映射到了参数化平面上) 。还有，应 用这种技术的过程中需要解大量的方程，这使得计算量相当大。s a n d e r 等人采用一种基 于重网格的分等级方法可以把计算的复杂度降到接近于线性，这种方法甚至对于大网格 都是有效的，但是这种方法在用到极端等周扭曲的网格上时有精确度的问题。 第二种参数化的方法就是把原始的模型映射到基于三角形的网格上。三角网格一般 是通过简化获得或者是通过对原始网格的区域划分获得。m a t t h i a se c k 等人采用过这种 方法并且获得了很好的结果。但是这种方法对于片的结构很敏感，样点的选取也很难控 制。 第二类半正规重网格化技术并不依赖于任何参数化方法，它采用了一种基于射线扫 描的方式寻找一种把新网格收缩包围到输入网格上的对应。 用半正规重网格化实现的形状压缩技术是目前已知技术中比较成功的。这类技术最 主要的就是注意到了网格的实现主要有三个因素构成：几何特征，连通性和参数化的方 式，并且后两者对于几何特征的展现是不重要的。于是目标就很明确了，那就是尽量通 过半正规重网格化尽量减少后两者的影响。 讨论：在所有基于映射的方法中，参数化扮演着至关重要的角色，它的任何缺陷将 会在输出中被放大。特别的，建立一个全局的光滑参数化是相当困难的。细分连通性对 于多分辨率分析仍然是必要的，而多分辨率分析则是很多几何建模和加工应用的强有力 大连理工大学硕士学位论文 工具。挑战仍然在于处理非正规的网格。虽然目前的几何加工方法都是针对它们的连续 对偶的，但是还是相当困难的。 j ，0 7 0 。o 篓_ o - _ | ， ，+ 。、一i i ! 1 、 。一j 。 一 。i f 一 饕 图34 四边形重网格化( 图片参考文献1 时 f i g3 q “i a l m lr m 嚣h m g ( r e f e r l 6 ) 简 锄篇 周35 面的多分辨率适应性参数化( 图片参考文献l ) f i g35m u l t i r e s o l u t i o n a d a p t i v ep a r a m e t e r i z a t i o no f s u r f a c e s ( r e f e r 】7 1 l 离敏曲面四边形剖分的组合优化及实现 蜷 图36 通过收耋| 茜包襄完成的重网格化( 图片参考文献1 8 ) f g36r e m e s l i i n gb ys h r i n k w r a p p i n g ( r e f e r l 8 ) ( 2 ) 全正规：在一个正规的网格( 栅格、三角或者是六边形剖分的) 中连通性是 固有的，并且紧性和数据结构的规则性有利于效率的提高，同时这也方便了很多算法的 应用。已经证明正规重网格化技术对于有效的松弛、质地或者其它调制映射( 如正投影 或仿射映射) 都是相当成功的。 g u 等人曾用一个正规的四边形栅格对一个非正规的三角网格进行重同格化。开始 时输入的任意亏格的网格部被切割威一个拓扑圆盘，接下来通过参数化将它映射到一个 2 d 的单位正方形上。同时最小化一个几何拉伸测度。然后这将被描述成一个所谓的几 何映像，这个几何映像包含了几何特征以及其它的所有与可视化相关的调制映射。这样 一个紧的栅格结构极大的简化了松弛方法，因为此时消除了通常隐藏在非正规网格中的 无方向性。尽管这种方 击对于有效的松弛是很重要的它还是有很多缺点的。它的缺点 主饕是由于它不可避免的对所有的面进行分割。每一个几何映像必须同胚于一个圆盘， 因此任何封闭的或者是亏格大于0 的几何模型都要被分割。特别的对于高亏格的模型 或者高等周比率的面它将带来不可接受的参数化扭曲。为了缓解这些缺陷，s a n d e r 等人 用一个地图集结构将输入的网格映射到任意形状的图表上。然后这些图表将被封装到存 在于参数化空间的几何映像里，接下来使用拉链算法将这些表格在不连续的地方弥合起 来，最终形成封闭的曲面。另外一种缓解这些由切割带来的缺陷的方法就是首先将网格 映射到球上，然后再将其映射到一个具有高级结构的正俯形上。 国 大连理工大学碗士学位论文 髑3i 儿刊瑚像帕田矬【图片参考z 献1 9 ) f i g37 c o n s l r u c t i o no f g e o m e t r y 】m a g e ( r e a r 9 】 讨论：几何映像的概念符合图形学中近来的趋势这种趋势就是将所有的面调制信 号描述成“纹理映射”( 正投影，仿射映射，颜色映射，光照映射，反射映射) ，而不 是采用每个点都有一定特征的好的网格。在与用复杂的多重纹理加工“修饰”网格所付 出的代价相比3 d 变换所付出的代价可以忽略的情况下，最核心的理念就是用正规的网 格去展现几何体本身。几何映像的研究主要是有h o p p e 和他的合作者推动的，现在所需 要做的主要工作就是点和映像缓冲的统一。 ( 3 ) 高度正规：【文献2 8 】中摘述了一种创建分段正规网格的重网格化方法。基于 他们的方向，这种算法把所有的三角形归为六类。法线接近于，正方向的三角形的所形 成的集合用一个y 一：面上的正规网格取样，剩下的五个集合采用相类似的方法取样，最 后这些重阿格化的片被连接成个合法的网格。通常这样所形成的网格会含有大片的正 规点，特别的，通过构建后每一片的所有内点都将是正规的在一些接缝的地方可能会 出现一些非正规的点。 s u r a z h s k y 与g o t s m a n 为获得一个高度正规的网格直接在网格表面上做了一些调整。 他们的工作最重要的前景就是通过利用重叠片实现表面的局部参数化( 小仅克服了全局 参数化所带来的问题，同时也克服了进行基于网格划分的参数化时在边界处容易产生的 重网格化问题) 。另外一个非常重要的前景就是系列边界消隐和边界抖动算法，这些 算法可以与基于面积的增进正规性的优化方法以及与产生良好三角形的优化方法相结 合( 此时避免了在三角形区域生成网格时容易产生狭长三角形以及膜状三角形的缺蛸) 。 由于重叠参数化可以将2 d 的网格优化算法用到3 d 网格上，这种算法的计算速度是相 当快的。 离散曲面四边形剖分的组合优化及实现 图38 高度正规重网格化( 圈片参考文献2 0 f i g38h i g l l l yr e g u l a r r e m e s h i n g ( r c 衙2 0 ) 讨论：高度正规的流形一般是通过对一个正规的网格进行剖分得到的。s u 袖s k y 和g o t s m a n 已经证明高度正规的网格是不能通过局部网格调整得到的，除非进行一些类 似于移动边的半全局操作。目前的挑战就是如何通过半全局调整而不是细分在固定数量 的不规则点上获得半正规网格。 32 兼容性重网格化 定义：给定一个彼此之间局部相符3 d 网格的集合，兼容性重网格化就是在通过对 这些网格进行重同格化之后得到这样的一个新的网格集合：里面的网格有着共同的连通 性结构良好的多边形，最大程度的逼近输入，并且保留他们之问的相符性。 动机：动机就是应用到形态和特征之间的过渡上、多重模型形状融合、同步模型编 辑、模板模型和多重数据集台匹配基础组件分析等等。在这些应用中共同的联通性通 常比阿格单元质量更加重要。 公共的参数化：兼容性网格上所做的工作主要是以变形为最终日标的。首先这需要 计算一个满足某种限制的公共参数化【有时称十字参数化) ，即两个网格之间的一个双 射。a l e x a 给出了一个非常好的公共参数化方法以及一个以变形为目的的兼容性重网格 化方法。计算公共参数化时通常把模型映射到一个共同的基区域上最通常的选择就是 球，而对于球形参数化已经有根多比较典型的算法。在这些算法中只有a l e x a 的算法提 到了特征相符，然而它并不能保证一定是职射，同时在特征匹配时也并不总是有效的。 球形映射的一个固有缺陷就是它只适用于封闭的0 亏格时的情形。 大连理工大学硕士学位论文 7 0 = 。 。：t 。二孝 j 罾黪f歹一 - 一? 二? 。7 ：盐 譬二童：? 一 圈39 共同球形参数化( 图片参考立献2 1 ) f i g39 j o i n ts p h e r i c a lp a r a m e t e r i z a t i o n ( r e f i t 2 一个更加通用的方法就是把模型都映射到一个共同的基网格上，这种方法按照共同 的内部片莲通性把所有的网格分割成匹配片。分割之后，每一个片的集台都被参数化到 一个共同的凸平面区域上。由于这种方法可以将特征点作为匹配片的拐角，所以它的一 个好处就是天然的支持特征匹配。将模型映射到一个摹阿格的最大挑战在于构建共同的 内部片连通性。这类方j 击中的绝大部分都采用仅在模型相似的情况下才起作用的启发式 的技术。p r a u n 等人给出了一种非常有效的算法，该算法可以将两个网格都按照用户给 定的连通性划分成片。现存技术中的一个共同的缺陷就是片的结构严格的限制了参数化 的自由度，这样映射扭曲的程度就在很大的程度上依赖于片的形状。 给出一个共同的参数化以后，很多的方法都是通过把网格覆盖到这个参数化区域上 并计算一个共同的交集网格给出共同的连通性的。新网格拥有模型的几何特征，但是它 一般比原先的输入网格要大并含有相当形状极不理想的三角形，同时覆盖算法也很难应 用，因为它需要多重交集以及映射运算。一种改善就是用在基阿格上派生的一个正规细 分连通性来对模型进行重网格化。由于严格的连通性结构，网格三角形的结构反映了基 网格的形状。这样，如果三角形的形状很不理想( 例如用户选择的特征点在空间中是不 均匀分布的) 网格中的三角形形状将会反应这一点。更重要的是，一个吉有基网格中三 角形内部特征的模型将需要在整个模型上做密度很大的细分。 内面映射：k r a e v o y 和s h e f f e r 提出了一项用于公共参数化和对两个局部相符的、0 亏格的网格进行兼容性重网格化的技术。该算法的输入是两个三角网格和一个特征相符 点的集合，其第步是通过不断的成对增加匹配的最短边缘路径构建一个共同的基区 域，此时需要注意避免相交和阻滞，同时也要注意保留循环的阶数以便得到匹配的片布 离散曲面四边形剖分的组合优化及实现 局。然后该算法不断的添加面路径直到所有片完成三角剖分，然后通过一个捌动程序改 善片布局的连通性。该算法的第二步是通过片之间的一个光滑转化训算个形状保留参 数化，该转化是通过中值参数化和一个紧跟着的比邻保留光滑程序实现的。该算法的最 后一步是通过不断的交换点的位置将点吸引到高误差率区域和误差驱动网格改善程序 构建一个兼容性网格。法线逼近是通过一个额外的虚假边界抖动程序实现的。与简单的 覆盖算法相比通过这种算法实现的网格在逼近原始的几何体以及输入模型的同时大量 的减少了网格的元素。 s c h r c i n e r 等人提供了一个与k r a e v o y 和s h e f f c r 的算法相似的构建基网格的算法， 该算法可以处理任意亏格的模型。为了得到光滑公共参数化他们采用丁一个对称的、 基于舒展的松弛算法，该算法试图在网格的质量和计算的复杂度之间取得一个平衡。如 上所述公共的网格是通过输入网格的重叠得到，为了避免极端情况的出现，这种方法必 须在某些情况下松弛特征点相符性。 译繇 昏臻。 眵禽 罔31 0 为两个0 亏格同格的共同参数化和坍调重网格化所做的基础嘲格( 罔片参考文献2 2 ) f i g31 0 b e s s d o m a i n sc o n s t r u c t i o nf o r j o i mp a r a m e t c r l z a t i o na n dc o m p a t i b l er m e s h l n go f t w o g m u s - 0 m e s h e s ( r e f e r 2 2 ) 讨论：虽然兼容性重网格化在计算机图形动画方面变得越来越重要( 此时一个网格 列是可用的) ，但是它还存在很多的问题。例如i 成对相符特征点的选择仍然是手工的 现存的方法中几乎没有能很轻松的处理任意丐格的表面和动画序列的，最后实验的结果 仍然在很大的程度上依赖于公共参数化的参数化方式。 大连理工大学硕士学位论文 3 3 高质量重网格化 定义：按照我们的分类，高质量重网格化意味着利用一个网格对原始几何体进行一 个新的离散化。新的网格必须能够展现如下的三个特征：很好的元素，均衡或等方性的 取样以及光滑的梯度取样。一个好的三角形的面比率要尽可能的接近1 ，一个好的四边 形位于相交边两侧的角度要尽可能的接近兰。等方性采样意味着样本点在各个方向上是 2 均匀分布的，这甚至比要求样本点均匀的分布在整个网格上更加的严格。光滑梯度意味 着如果样本点的密度不是均匀的，那么应该光滑的过渡。 动机：高质量重网格化是以数值稳定性和仿真计算的可靠性为动机的。当然，有效 补偿，交互式自由形状建模，还有很多几何处理算法( 压缩，展示，光滑处理) 也从中 获益颇多。网格元素的形状对有限元分析计算的数值稳定性以及有效补偿有着直接的影 响。对于广泛应用的三角网格来讲，根据最终的计算不能有大角或小角。 虽然一些其它的原始的方法( 例如起泡包装，方胞腔包装，流线型布局) 也可以很 容易的应用到网格上，但是在这里我们把我们的描述限制到基于点的取样技术上。以重 网格化为目的的均匀点采样技术努力做的是全局上( 分别局部) 尽可能均匀的将一个点 集合分布到原始的输入模型上。该技术有两种实现方式，其一是每次在网格上插入一个 点来改善刚刚生成的网格，其二是用基于松弛的算法通过局部或者是全局的调整点的位 置来改善初始网格的布局。 最远点取样技术：最远点取样技术每次插入一个新的样点，并且使得它离原先已经 放置的点尽量的远，即让它位于最大空旷处的核心。该策略最大的好处就是保持了点的 均匀程度，并且增加了点的密度。与随机的方法相比，它可以通过绑定样本点之间的距 离来保持一定的均匀性。这种方法( 也被成为d e l a u n a y 修正法或者下沉插入法) 已经 被证明对于生成均匀的和等方性的网格格外