（粒子物理与原子核物理专业论文）海量空间数据点四边形网格优化算法的设计.pdf

海量空间数据点四边形网格优化算法的设计 摘要 由于计算机技术的发展，计算机存储技术的进步，使得计算机能够处理更多的数据； 同时，许多c a d 造型系统和快速原型制造系统的数据输入输出也逐步采用多边形表示模型， 以d f x 和s t l 格式文件来进行，另一方面网格曲面也更加有利于计算机进行曲面的存储、 分析、计算和绘制。因此在曲面重建中，越来越多的人采用网格曲面作为重建曲面。基于 海量数据的计算机模型重建，在许多应用中具有重要意义。 文中首先对海量空间数据点的四边形网格划分算法进行了总体概述，给出了四边形网 格划分过程中使用的数据结构，详细介绍了算法的基本思想，总结了算法的特点；并对四 边形网格生成中的关键技术做了深入地研究，给出了算法的运行实例。 其次，基于四边形网格生成算法的特点，设计了四边形网格生成后的综合优化算法， 并对简单的拓扑优化算法进行了编程调试。该算法分为两部分：l 、拓扑优化操作，2 、几 何优化操作。 1 拓扑优化操作：最大限度的满足节点的度为4 ，以便后续的曲面拟合； 1 ) 基本操作：改变节点的连接、合并节点、删除节点，改善局部网格拓扑； 2 ) 高级操作：移动指定的网格拓扑系列，改善全局网格的拓扑关系。 2 几何优化操作：改变网格顶点的位置，调整网格的质量，使网格均匀。 再次，文中对网格光顺常用的方法做了简单的分类，详细的介绍了四边形网格光顺算 法，网格光顺算法仅仅改动网格顶点的空间位置，不改变网格顶点的个数，为后续的四边 形网格的表面光顺提供了理论基础。 实验结果表明：海量空间数据点四边形网格划分算法所得的网格具有网格质量较好， 边界点数不受限制，边界拟合精确等特点。论文所设计的四边形网格综合优化算法提高了 网格生成的质量和拓扑结构，也使算法更加稳定可靠，为曲面拟合奠定了基础，具有一定 的实际应用价值。 关键词：海量数据，网格化分，网格优化，四边形网格，光顺 t h e d e s i g no ft h eo p t i m i z a t i o na l g o r i t h mo fq u a d r i l a t e r a l m e s h e sb a s e do nc i o u dd a t a a b s t r a c t b e c a u s eo ft h ec o m p u t e rt e c h n o l o g yd e v e l o p m e n ta n dt h ep r o g r e s so fc o m p u t e rs t o r e s t e c h n o l o g y , c o m p u t e rw a sa b l et op r o c e s sm o r ed a t a ta tt h es a m et i m e d a t a si m p o r t i n ga n d o u t p u t t i n go fal o to fc a dm o d e ls y s t e ma n dt h ef a s tp r o t o t y p em a n u f a c t u r es y s t e ma l s o g r a d u a l l ya d o p t t op o l y g o ne x p r e s s i o nm o d e l ，c a r r y i n go nt h ef o r md o c u m e n to f d f xa n d s t l o nt h eo t h e rh a n d , t h ec u r v e ds u r f a c ew a sa l s om o r em v a n t a g e dt ot h ec o m p u t e rc a r r i e do nt h e m e m o r y , t h ea n a l y s i s , t h ec o m p u t a t i o na n dt h ed r a w i n go fc u r v e ds u r f a c e t h e r e f o r ei nt h e c u r v e ds u r f a c er e c o n s t r u c t i o n , m o r ea n dm o r ep e o p l eu s e dt h ec u r v e ds u r f a c 2t ob et h e r e c o n s t r u c t i o ns u r f a c e c o m p u t e rr e c o n s t r u c t i o no fc l o u dd a t aw a sv e r ys i g n i f i c a n ti nm a n y a p p l i c a t i o n s f i r s to fa l l ，q u a d r i l a t e r a lm e s h e sg e n e r a t i o na l g o r i t h mb a s e do nc l o u dd a t aw a sp r o p o s e da s aw h o l e ，a n dt h ed a t ab m l l c t b r e sw e r eg i v e ni nt h i sp a p e r t h ei d e aa n dc h a r a c t e r i s t i c so ft h e a l g o r i t h mw e r ei n t r o d u c e di nd e t a i l t h ei n v e s t i g a t i o n sa b o u tt h ek e yt e c h n i q u e so f q u a d r a n g u l a r m e s h e sg e n e r a t i o nw e r eg i v e nd e e p l y ，a n dt h ee x a m p l e sw e r es h o w ni nt h ep a p e r t h es e c o n d ，b a s e do nc h a r a c t e r i s t i c so fq u a d r i l a t e r a lm e s h e sg e n e r a t i o na l g o r i t h m ，t h e o p t i m i z a t i o na l g o r i t h mo fq u a d r i l a t e r a lm e s h e sw a sd e s i g n e d a n dt h ep r o c e d u r ed e b u g g i n go f s i m p l et o p o l o g i co p t i m i z a t i o na l g o r i t h mw a sg i v e n t h eo p t i m i z a t i o na l g o r i t h mo fq u a d r i l a t e r a l m e s hw a si n t r o d u c e di nt w oa s p e c t s o n ew a st h et o p o l o g i co p t i m i z a t i o no p e r a t o r s ，a n dt h eo t h e r w a st h eg e o m e t r i co p t i m i z a t i o no p e r a t o r s 1 t o p o l o g i co p t i m i z a t i o no p e r a t o r s ：d e g r e eo fn o d es h o u l db e t t e rb ef o u r i no r d e rt o f o l l o w i n gc u r v e ds u r f a e ef i t t i n g 1 ) b a s i co p e r a t o r s ：c h a n g e dn o d e sc o n n e c t i o n , m e r g e dn o d e s ，d e l e t e dn o d e s ，p a r t i a lm e s h t o p o l o g yw a si m p r o v e d 2 ) a d v a n c e do p e r a t o r s ：m e s ht o p o l o g yw a sm o v e di no r d e rt oi m p r o v et o p o l o g i cs t r a c t u r e o f a l lm e s h e s t o p o l o g i cr e l a t i o n so f a l lo f t h em e s h e sw e r ei m p r o v e d 2 g e o m e t r i co p t i m i z a t i o no p e r a t o r s ：t h i so p e r a t o ri su s e dt om o v en o d e so nt h es u r f a c ei n o r d e rt oi m p r o v et h es h a p eo f t h ee l e m e n t s t h et h i r d , t h en o r m a lw a y so fm e s h e ss m o o t h i n gw e r ec l a s s i f i e d ，a n dt h ea l g o r i t h mo f q u a d r i l a t e r a lm e s h e ss m o o t h i n gw a si n t r o d u c e di nd e t a i l t h es p a c ep o s i t i o no fm e s hn o d e sw a s c h a n g e d ，b u tt h en u m b e ro fm e s hn o d e sw a sn o tc h a n g e d t h et h e o r yf u n c t i o n so fs u r f a c e s m o o t h i n go f q u a d r i l a t e r a lm e s h e sw e r ep r o v i d e d i t t h er e s u l t so f t h ee x p e r i m e n t si n d i c a t e dt h a tt h eq u a l i t yo f m e s h e si si m p r o v e d ，t h ep a r i t yo f n u m b e ro fp o i n t so nb o u n d a r i e sw a sn o tl i m i t e d ，e d g e si n t e r s e c t i o nw a sp r e c i s e ，a n ds oo n t h e m e s h e sq u a l i t ya n dt o p o l o g i cs t r u c t u r ew e l em v a i l c e db yu s i n gt h eo p t i m i z a t i o na l g o r i t h mo f q u a d r i l a t e r a lm e s h e sw h i c hd e s i g n e di nt h i sp a p e r , t h ea l g o r i t h mw a ss t a b l e t h ef u n c t i o n so f s u r f a c ei n t e r s e c t i o nw c r ep r o v i d e d s oi tw a ss i g n i f i c a n c ei np r a c t i c e k e y w o r d s ：c l o u dd a t a ，q u a d r i l a t e r a lm e s h ，m e s hp a r t i t i o n , m e s h i 海量空间数据点四边形网格优化算法的设计 一、引言 第一章引言 由于计算机技术的发展，计算机存储技术的进步，使得计算机能够处理更多的数据； 同时，许多c a d 造型系统和快速原型制造系统的数据输入输出也逐步采用多边形表示模 型，以d f x 和s t l 格式文件来进行，另一方面网格曲面也更加有利于计算机进行曲面的存 储、分析、计算和绘制。因此在曲面重建中，越来越多的人采用网格曲面作为重建曲面， 它有效的克服了用参数曲面进行曲面重建所遇到的算法复杂、存在冗余等问题。国内浙江 大学，华中理工大学和南京航空航天大学等单位在海量数据处理上也做了很好的工作。最 近，浙江大学提出了由点云数据的自适应网格重建算法，算法有效克服了传统重建算法需 要用户确定参数的缺陷，具有很好的稳定性和普遍的适用性。 在早期的四边形网格【1 q 划分算法一般是应用在2 d 区域中，如子域划分法【n 】、三角形 合并法【、铺设法【1 3 1 1 2 0 1 、l o o pin g 单元法五5 1 、基于栅格算法 2 6 - 2 7 等。近年来，随着3 d 建模技术的发展及应用，任意三维曲面的四边形网格划分的算法得到高度重视，划分算法 不断发展；在文献 2 8 中将二维的四边形网格划分的铺设算法延伸到三维任意曲面。 网格优化也是网格划分中的关键技术，一般是在网格化分的同时基于优化准则进行网 格优化，也有划分后再进行网格优化。1 9 9 1 年d eh a m e r 利用自适应递归方法，提出了规 则四边形网格表示物体的简化多边形网格方法。1 9 9 3 年，h o p p e r l 2 9 1 提出了一种整体网格的 优化方法，它包括网格匹配过程和网格优化过程。h o p p e r 能量函数法的特点是用能量函数 的变化指导网格优化，针对三维扫描仪测量的数据模型进行简化效果十分理想，但算法的 执行效率偏低。1 9 9 7 年，h o p p e ，川对累进网格进行扩展，形成对任何网格都适用的且与视 点有关的累进网格。 国内外学者近几年也对四边形网格划分技术、优化技术开展了一些卓有成效的研究工 作，提出许多四边形网格划分算法，但是真正适合于任意三维曲面的四边形网格优化算法 和准则却较少，尤其是算法的通用性、稳定性、自动化程度有待进一步提高，因此研究良 好的网格划分算法及优化方法将提高基于海量空间数据点曲面重建的速度和执行的效果。 二、四边形网格划分 ( 一) 网格划分算法的进展和现状 三维物体的散乱点重建技术是指对散乱点进行处理，使其能够在计算机中还原为其原 始的几何形状。随着检测技术的快速发展，从物体上获得散乱数据的精度和数量也有很大 l 海量空间数据点四边形网格优化算法的设计 的提高。因此，在三维空间中，把这些从物体表面取样的散乱点集，重新恢复成原来的曲 面，并保持正确的拓扑和尽可能精确的曲面，是目前计算机图形学领域的热门话题。它的 研究可以应用于许多领域，如计算机辅助几何设计、逆向工程、虚拟现实、数字人、医学 图像处理、机械工业制造等。目前，国内外专家学者在这方面做了大量的理论研究和实际 探索，并取得丰硕成果。该领域的发展为工业设计、科学发现、医疗诊断等提供依据，已 成为重大的挑战性问题。 ( - - ) 海量空间数据点四边形网格划分算法 海量空间数据点四边形网格的生成算法是从数据模型的任意一点开始，选择一个初始 的四边形，采用动态边界边扩展的方法在三维空间直接进行四边形网格划分，直至完成所 有的数据点的划分；提出了曲面边界点的提取算法和满足一定优化条件的二次网格优化策 略；在文献 3 1 3 3 中要求边界点必须是偶数，而该算法对边界点的奇偶性没有限制，提高 了边界处理的灵活性；冲突处理的简化和两次的优化处理，提高了网格生成的质量，保证了 算法的运行速度。 三、四边形网格优化 网格的质量直接影响曲面拟合结果的精度，而网格的优化是为了进一步提高网格质 量，以满足后续分析计算的需要。本文设计开发的海量空间数据点四边形网格生成算法， 在网格生成中，为了网格划分的继续进行，一些内部节点的度可能多于4 个或少于4 ，即 为2 、3 、5 个，即一个内部节点拥有2 、3 或5 个邻近单元；网格单元可能退化为三角网 格单元；基于本网格生成特点，设计开发了空间曲面四边形网格的综合优化算法。算法分 为两部分：1 、四边形网格拓扑优化操作，2 、四边形网格几何优化操作。 四、本文研究目的、内容及意义 ( 一) 目的 随着三维空间测量技术的快速发展和广泛应用，空间数据获取的能力、精度和速度有 了空前的提高，由此产生的需要处理的数据量与日俱增。近年来，海量空间数据处理已经 引起了国内外学术界的极大重视，在很多方面已经取得了重要的进展。要实现对海量空间 数据点四边形网格的优化划分，理论和技术上需要解决的关键问题包括： 1 ) 、海量空间数据点四边形网格划分算法； 2 ) 、四边形网格边界冲突检测与处理策略； 2 海量空间数据点四边形网格优化算法的设计 3 ) 、四边形网格综合优化策略； 4 ) 、四边形网格的光滑与整合技术。 ( 二) 内容 基于海量空间数据点三维任意曲面四边形网格优化划分的关键技术，解决曲面重建 【1 9 j 3 ，3 4 】过程中的关键问题，发展和创新三维任意曲面的四边形网格优化划分算法，使之具 有较高的边界灵敏度、网格形状好、过渡平滑、稳定可靠的四边形网格自动生成算法。实 现海量空间数据点间的网格划分提供可行的、稳定的新技术；具体研究内容：将网格生成 较好的铺设算法进行改进，提出一种海量空间数据点全四边形网格生成算法；提出了边界 冲突检测策略，简化了冲突问题的处理；并设计了四边形网格优化的综合算法，四边形网 格综合优化算法分为两部分：1 、网格拓扑优化操作，2 、网格拓扑优化操作。 ( 三) 意义 论文所研究的海量空间数据点四边形网格划分算法所得到的网格具有网格质量较 好，拓扑结构合理，边界拟合比较精确，边界点数不受限制，无残留三角形单元 等特点，为海量空问数据点的曲面拟合奠定了基础。 论文所研究的四边形网格优化划分算法，是目前网格划分的前沿问题，为该研究 方向提供新的理论，为四边形网格优化划分奠定基础。 论文所研究的四边形网格优化算法提高了网格生成的质量，也使算法更加稳定可 靠，提高基于海量空间数据点曲面重建的速度和执行的效果。 为基于海量空间数据点三维任意曲面四边形网格优化划分提供自动的、稳定的、 可行的新技术。并将一系列先进算法和技术编成程序模块，形成具有特色的基于 海量数据点的任意曲面四边形网格划分子系统，对三维曲面重建具有重要的理论 意义和实际意义。 海量空间数据点四边形网格优化算法的设计 第二章四边形网格划分算法的理论基础 目前，海量空间数据点的处理已涉及到各个领域，如计算机辅助几何设计、航空航天 探测、生物学、数字人和医学图像处理和工业无损探伤等。本文是基于三维散乱数据点的 三维散乱点网格优化划分技术，所研发的软件或模块能够应用于大型图形处理软件中。 一、基本概念的定义 边界边：四边形划分过程中，位于已划分区域和 未划分区域之间的四边形网格的边称为边界边，如图 2 1 所示1 2 、2 3 等。 边界点：位于四边形网格边界边上的点，称为边 界点，如图2 1 所示1 、2 、3 、4 等。 固定边界边：非封闭曲面的边界点构成的边界边 称为固定边界边； 边界环：四边形划分过程中，由边界边按逆时针 或顺时针方向首尾相连构成边界环。起始边界边与终 止边界边共结点。即边界环是一条闭环，如图2 1 所 示，边1 2 2 3 3 4 一1 0 1 按逆时针方向构成边 界环。 四边形网格的最优顶点：设点p 1 为未划分区域测 量点集中的任意一点，若点p l 与某边界边顶点p f 、p 、 p 2 构成的四边形最接近正方形，并且生成的四边形不 与已划分区域重叠，则称点p 1 为边界边顶点p f 、p 、 p 2 的最优顶点。如图2 2 所示。 图2 - 2 边界点与边界边 四边形网格的内部点：沿四边形法矢方向向四边形所在平面投影，如其投影点落在 四边形内部，且到该四边形的距离不超过某个范围的测量点称为该四边形网格的内部点。 内角：在三维曲面上，一个环上节点的内角定义为此 节点与上一节点及与下一节点的连线在此节点处的曲面的 切平面上投影之间的夹角【3 l 】。 两条固定边界边的夹角：两条固定边界边所属网格单元 在共同顶点处的夹角之和，如图2 3 所示，固定边界边a b 与a c 的夹角a = a l + c t2 。 4 b 图2 - 3 固定边界边的夹角 海量空间数据点四边形网格优化算法的设计 二、算法的基本思想 ( 一) 算法的结构图 ( 二) 实现步骤 图2 - 4 算法的结构图 新网格生成是基于空间数据点集，因此需根据空间点集的坐标值计算采集点间的距离 来估算网格单元的尺寸，非封闭曲面需要找出固定边界点作为网格划分的终止边界点。曲 面网格划分的步骤： 龠一步：在点集中任意寻找4 个或6 个边界点，使它们构成较优的一个或两个四边形 网格作为初始网格，选择其中一点为初始边界点，该边界点与相邻的两个边界点相连构成 两条起始边界边； 第二步：计算该边界点的切平面，将与该点相连的边界边投影到切平面，计算两个矢 海量空间数据点四边形网格优化算法的设计 量在该点的内角； 第三步：根据该边界点的内角类型，用不同的算法生成新网格顶点； 第四步：进行网格边界的冲突检测和网格顶点的优化处理，更新边界点，把新生成的边 界点加入边界边列表中，转到第二步操作，处理下一个边界点，直至完成对整个目标区域的 划分； 第五步：对四边形网格进行二次优化。 三、数据结构的设计 ( 一) 数据结构 1 、图元的数据结构 t y p e d e f s t r u e tt a g o b j e c t i n tn o h s u m ： d w o r d l o e l e m e n t s u m ； h - n d l eh o e l e m e n t ； d w o r dl o c u b e s u r n ； h a n d l eh o c u b e ： d w o r d l o p o l y l i n e s u m ； h a n d l e h o p o l y l i n e ； c h a rc 0 u s e ： c h a rc o d e l e t e ； j0 b j e c t ； 2 、点的数据结构 t y p e d e f s t r u c tt a g e l e m e n t i n tn e h s 岫： d o u b l ef e l ，也2 ，m 3 ，t e 4 ，t e 5 ，f e 6 ： i n tc e d e l e t e f l a g ； i m c e t y p e f l a g ； h a tc e e d g e f l a g ； h a tc e p r o c f l a g ； i n tc e c u b e l n d e x n o ； h 心d l eh p k n e i h a n d l e ： ，结构中具有的句柄个数 图形元素结构数目 ，图形元素块头句柄 ，立方体结构数目 立方体内存块头句柄 多边形结构数目 多边形内存块头句柄 使用标记 删除标记 结构中具有的旬柄个数 | | 坚椿 删除标记 ，点，边标记 边界点、边标志 ，处理标记 点所属的立方体编号 ，点的k 近邻内存块的头句柄 6 海量空间数据点四边形网格优化算法的设计 t a tn k p c o u n t ； ) e l e m e n t ； 3 、边的数据结构 t y p e d e f s t r u c tt a g f a g e s z m p o s e t z mp o i n t ； h a tp o i n t ； p o s e t z mp f r o n t ： i n tp f r o n t ； p o s e t z mp b e h n 呵d ： i n tp b e h i n d ； i n tp r o e e s s f l a g ； e d g e s z m ： 4 、网格的数据结构 t y p e d e f s t r u e tt a g q u a d m e s h p o i n t s 一3 dp l ； p o i n t s _ 3 dp 2 ： p o i n t s _ 3 dp 3 ： p o n t s _ 3 dp 4 ； h a t p n o l ； i n tp n 0 2 ； h a tp n 0 3 ； h a tp n 0 4 ： i n tp r o c e s s f l a g ； ) q u a d m e s h s ； 5 、立方体的数据结构 t y p e d e f s t r u c tt a g c u b e h a tc u b e n o ： p o i n t s e tc o v e x 2 ； h a tp o i n t c o u n t ： i n td e l e t e f ： k n c u b e k n c u b e s 【2 7 】； h a n d l eh p h a n d l e ： ，点的近邻数 ，当前点的坐标 ，当前点的点的编号 前一点的坐标 ，前一点的 后一点的坐标 后一点故编号 ，是否查找过或处理过 ，p 1 点的信息( 坐标、是否处理过等) l i p 2 点的信息( 坐标、是否处理过等) p 3 点的信息( 坐标、是否处理过等) l p 4 点的信息( 坐标、是否处理过等) p l 点的编号 p 2 点的编号 p 3 点的编号 l p 4 点的编号 ，是否查找过或处理过 元素编号 立方体左下角、右上角坐标 ，立方体中点的数量 删除标记 ，立方体的2 7 个近邻( 包括自身) 立方体中包含的点的内存块的头句柄 7 海量空间数据点四边形网格优化算法的设计 c u b e ； ( 二) 多层次的数据结构 数据存储采用多层次的 图2 - 5 多层次的数据结构 3 海量空间数据点四边形网格优化算法的设计 第三章四边形网格划分算法的设计与实现 一、网格划分 ( 一) 内角的计算 在三维曲面上，一个环上节点的内角定义为此节点与上一节点及与下一节点的连线在 此节点处的曲面的切平面上投影之间的夹角。在三维曲面上，两个矢量p ，q 间的夹角用 公式( 3 1 ) 计算，如图3 - l 和图3 - 2 所示。 e _ a r c t g = p x q ： 9 p q 图3 - 1 两个矢量间的夹角 ( 二) 网格质量因子的确定 ( 3 - 1 ) 定义四边形网格的质量因子的方法比较多，本文根据四边形的4 条边所夹的4 个内角、 边长、凸凹性来定义四边形的质量因子y 值： ，= k l 。 + k 2 。7 2 + 屯儿 ( 3 - 2 ) 其中t 1 、住、丫3 是t 的分量因子，k l 、k 2 、k 3 是权因子。 将空间四边形的四条边投影到不在一条直线的3 个点所构 成的平面内，构成平面四边形，如图3 3 所示。设四边形的四 个内角分别为a l 、啦、哟、0 4 ，对其进行降序排列，即f f 1 _ a 立a 3 e 4 ， 则四边形的质量因子月r l 定义为： 。圈b 图3 - 3 四边形的四个内角 t l = 坦 ( 3 3 ) qx 吒 四边形的四条边长分别为，1 、f 2 、f 3 和f 4 ，对四条边进行排序，即，l 弛三厶，得到： 9 海量空间数据点四边形网格优化算法的设计 v f 等 ( 3 - 4 ) 四边形退化为三角形时t l = 0 托：o ；y 1 7 2 值越大，表明四边形的质量越好，越接近于 正方形： 凹四边形是在网格划分中最不理想的情况，应避免发生。 因此当四边形为凹四边形时，t 3 = 0 ；当四边形为凸四边形时， 1 ：r 1 b 怕：l 。如图3 - 4 所示，对于四边形a b c d ，连接对角线b 、d 匙堂岛夕 或a 、c ，得到四边形的4 条边与此对角线所形成的四个夹角 辟= ，i 分别为p l 、艮、艮和艮，若p l + p 空1 8 0 。或助+ 艮兰1 8 0 。，则该四 边形是凹四边形。 r 四边形的质量因子丫值介于0 和1 之间，t 值越大，表明 图3 - 4 画四边形的判断 四边形的质量越好，越接近于正方形；本算法中k l 、k 2 、k 3 的 取值分别为o 3 、0 2 、0 5 ，以保证划分的四边形是接近于正方形的凸四边形。 ( 三) 网格边长的计算 设空间数据点集的总数：n ：点集的密度：d 。 首先计算包含所有数据的最，j 、长方体空间的体积屹。 。= 魄。一j 眈。咒j 一j 将最小长方体空间进行指定边长的划分，计算出有效立方体的体积v 。： v = v 埘喈一v 峨 1 1 其中n 为空子立方体数。 d = v f n 利用式( 3 7 ) 可以估算出测点间的距离d ，取新单元的边界长度为川。 ( 四) 节点类型确定及生成 根据内角a 的大小可将节点分为： 终止节点：a51 2 0 0 ； 边节点：1 2 0 0 a 曼2 4 0 。； 角节点：2 4 0 0 旺s3 6 0 。： 不同类型节点在切平面上生成新节点的算法如下： 1 0 ( 3 5 ) ( 3 6 ) ( 3 7 ) 海量空间数据点四边形网格优化算法的设计 1 、以终止节点为基点的算法 如图3 - 5 所示，由三个边界点n 1 、n i 、n l + 1 生成一个新边界点n j ，连接新旧边界点， 组成一个新单元，v ，与n 、n ，的夹角为0 2 。 m i = d s i n ( 0 2 ) ( 3 8 ) 其中d 为根据式( 3 8 ) 估算的单元边界长度。 2 、以边节点为基点的算法 如图3 - 6 所示，由三个边界点n 卜n j 、n f + 生 成三个新边界点n ，、n i 、n ，连接新旧边界点， 组成两个新单元，v ，、v ，与n ，n ，的夹角为0 4 、 0 2 、2 们。 其中 i v d = d ( 3 - 9 ) i i = d s i n ( 0 4 ) ( 3 1 0 ) i v d = l i ( 3 1 1 ) 3 、以角节点为基点的算法 如图3 7 所示，由三个边界点n mh ，n f + 1 生 成五个新边界点m 、n ，、n 。、m 连接 新旧边界点，组成三个新单元，m 、m 、n ，、 n 。n 。与n f 1 n i 的夹角分别为0 6 、0 3 、 “2 、2 0 3 、5 0 6 ，则有： l v 女同 i v j | - d s i n ( 0 6 ) f v “2 i i f v _ f - f v 硝 v p m ( 3 1 2 ) ( 3 1 3 ) ( 3 1 4 ) ( 3 1 5 ) ( 3 - 1 6 ) ( 2 k ) k 近邻的计算 n i 图3 - 5 终止节点 图3 - 6 边节点 如图( 3 - 8 ) 所示，设x = z x 2 , 。) 是未知曲 面m 上的空间采样点集，点集工中与某一测点而的直 线距离最短的k 个点，称为而的k 近邻，记为n b h d ( x ) ，k 近邻中的每个测点称为勋的邻近点。 本文提出一种新的海量空间数据k 近邻的快速搜索 算法。本算法综合考虑了空间数据的范围、数据的总数、 近邻点数目肫_ 及数据的密度，给出了一种新的估算子立 图3 7 角节点 图3 - 8 两个矢量的投影 海量空间数据点四边形网格优化算法的设计 方体边长的方法，然后采用空间分块策略，把数据空问划分成多个子立方体，子立方体的 大小决定k 近邻的搜索速度；最后记录每个子立方体所包含的数据点及每个点所属的子立 方体编号，搜索测点的k 近邻。公式( 3 一1 7 ) 给出接近于最佳搜索速度的分块大小，并且改 进了搜索终止准则，提高了五近邻的搜索速度。 v y x ：包含点集的立方体的有效体积，由公式( 3 - 6 ) 得到； n ：是点集的总数； b ：是系数； k ：是近邻点数； l ：子产方体边长。 图3 - 9 兔模型s o 近邻的计算结果 三= ( v 。| i y 3 ( 3 1 7 ) 通过调整系数b ，可以得到接近于最佳搜索速度的子立方体边长。算法的处理结果如图3 9 所示。 ( 六) 边界点的搜索 鉴于边界点的复杂性，本文设计出两种方案来确定平面上散乱点的边界点。并针对点集 中出现的孔洞进行了处理。 如图3 - l o ( a ) 所示，把测点“”检测区内的点集分成四个区，如果有一个区没有散乱 点，就认为当前点“”为边界点。图3 - l o ( b ) 把测点“”检测区内的点集分成伞形八个区， rr ( a ) 四分方案 ( b ) 八分方案 图3 1 0 边界点提取方案 如果其中有2 个相邻区没有散乱点，就认为当前点“”为边界点。方案中虚线圆的内部 区域为检测区，称为当前点“”的邻域，r 为检测半径。指定 值r 应小于真实空洞的最小值，否则将无法识别孔洞上的边界 点。 最小半径r 与点集的密度p 及边界的复杂程度等因素有关。 r = r o + 4 e 一9 ( 3 1 8 ) r 随p 的指数衰减形式，因此可以根据该公式估算出r 的值。 图3 - 1 1 龙边界点查找结果 图( 3 一1 1 ) 是龙的边界点查找结果。 海量空间数据点四边形网格优化算法的设计 二、冲突检测与边界点的优化处理 鬟黛燃燃燕3 - 1 2 妒妒 行缝合处理，以生成规则的四边形网格。如图p f 弋焉k p f 弋= k 所示，这种情况下将前边界点与后边界点合并成 盖戮募差淼雾淼凳詈裟赢篙。黔此需要及时进行优化处理，将前点p f 与后点p b b 连接形成网。髟、 o ， o ( 保证网格是凸四边形，其中y m l 、y m 2 是网格的质量 ，) 当新生成的网格边与后边界边所属的网格相交时，处理方法 图3 1 4 相交处理 3 爨1 一囊瘦蕊 的边界点处于窄小的区域内，找到的新网格，墨；么 7 z y 气i 疋y 点，与后点或前点所属的网格相交，如图：柃，。檎弼) 1 ，弋眇 5 ( a ) 所示，需要对新的网格点进行优化处l ”7 l ”7 海量空间数据点四边形网格优化算法的设计 三、边界处理 本算法对曲面的四边形网格的划分是从初始的四边形网格开始，通过边界环的扩展、 分裂、融合、边界的拟合、封闭处理实现网格的划分。四边形网格的扩展是将边界环列表 中未处理的边界点作为当前点，如果当前点为固定边界点时，将跳过该点将下一个未处理 的边界点作为当前点继续网格划分。 1 、边界的拟合 在对有边界的曲面进行网格划分到边界附近 时，如果找不到符合优化条件的四边形网格点 时，用最近的固定边界点替代；如果用该固定 边界点替代网格的顶点构成的四边形是凹四边 形时，那么将当前点用最近的固定边界点替代， 调整当前点所属的网格顶点。边界点拟合的结 果如图3 1 6 所示。 2 、边界点跳跃的处理 黔岛黔 边界点 边界点 图3 - 1 6 边界的拟合 由于固定边界点的存在，会出现当前点、前点与后点不连续的情 况，称为边界点跳跃，如图3 1 7 所示，需要在固定边界点或未处理的 边界点中，寻找与p 点连续的、同属于一个网格的前点或后点，以便 继续进行网格划分，如图3 1 7 所示，p b 为原后点，p b 为边界跳跃处 理后的p 的后点，p 为下一个将处理的边界点。 3 、边界的分裂 图3 1 7 固定边界 在为当前点p 寻找到最优顶点时，考察该边界点所在的边界环中除相邻的p f 和p b 外， 是否还有其它的未处理的边界点在p 点的包围合内，如果在包围盒内，也会形成新的网格， 出现边界环的分裂，将一个边界环分裂成二个边界环，如图3 1 8 所示。 嗡嗡 图a 分裂前 图b 分裂后 图3 - 1 8 边界环的分裂 图( a )融合前 图( b ) 融合后 4 、边界的融合 图3 一1 9 边界环的融合 在为当前边界点寻找到了最优网格顶点p l 、p 2 、p 3 时，如图3 - 1 9 所示，并按照网格 1 4 海域空间数据点四边形网格优化算法的设计 扩展的方法生成了新的网格后，此时p 1 、p 2 、p 3 又在另一个边界环的边界点的包围盒内， 而且可以构成四边形网格，这时需要进行边界融合处理，将两个边界坏融合成一个边界环。 四、算法实现 图3 2 0 是兔模型部分数据的处理结果。图3 2 1 是彩陶壶的空间数据点模型，共计7 7 6 4 个点，图3 2 2 、3 2 3 、3 2 4 、3 2 5 是采用本算法实现的网格划分的实例，共划分2 8 2 9 个网 格。 图3 - 2 0 本算法生成的兔模删底部数据四边形网格实例 图3 - 2 1 彩陶壶数据模型 图3 2 2 小角度缝合 1 5 海苗空间数据点四边形网格优化算法的殴计 幽3 2 3 小区域l 的处理 图3 - 2 4 嘲格交义处理结果 图3 - 2 5 本算法生成的彩陶壶模型的四边形网格的实例 1 6 海量空间数据点四边形网格优化算法的设计 第四章四边形网格综合优化算法的设计 在网格的生成过程中，由于原数据模型的数据点分布不是均匀的，或者边界点寻找的不 准确，而且通常网格生成算法的着眼点在于如何生成网格，因此尽管网格生成过程中是依 据优化因子生成的网格，但是也难以很好的控制网格单元的形状和单元密度，有时也会产 生凹四边形或退化为三角形，因此未经优化的网格很难保证单元具有良好的形状，对网格 的拓扑结构的合理性就更难保证了。所以网格优化已成为网格划分不可缺少的重要部分。 一、网格质量的定义 目前，大体上有两类定义网格质量的方法，一类是以网格中最差的一个网格的质量来 表示整个网格的质量，另一类是将网格质量定义为所有单元质量的总和或某种平均值。前 一类存在两个方面的问题，一是由于所采用的单元质量量度是连续的合格单元的质量量度 值夜根据形状的好坏而有所不同，所有单元求和或求平均的结果，可能导致由全部合格单 元和部分特别差的不合格单元组成的网格，这显然是不合理的。其次，这种定义方式忽略 了网格中质量特别差的一批单元对网格质量起着决定性的影响，而实际上，在一些计算模 型中，由于边界几何形状的限制，在个别拐角点单元会有很小的内角，这个拐角点单元往 往是整个网格中最差的单元，而结构内部有可能产生大量不合格单元的情况，显然不能有 这个最差单元表示出来。从网格结构角度分析网格的质量，可以用网格的平均度偏差来衡 量网格的拓扑结构的好坏。一旦理顺网格的拓扑结构之后，网格的形状也将直接影响到网 格质量。网格的形状的优化需要体调节内部节点的位置来改善网格单元的形状。 因此，网格的质量评价应该综合考虑节点的度和网格的形状，所以需要网格的拓扑结 构优化与几何优化相结合。本文设计开发的海量空间数据点四边形网格生成算法，在网格 生成中，为了网格划分的继续进行，一些内部节点的度可能多于4 或少于4 ，即为2 、3 、 5 ；网格单元形状可能退化为三角形网格；基于本网格生成特点，设计开发了空间曲面四 边形网格的综合优化算法。该算法分为两部分：i 、拓扑优化操作，2 、几何优化操作。 1 拓扑优化操作：最大极限的满足节点的度为4 ，以便后续的曲面拟合； 1 ) 基本操作：改变节点的连接、合并节点、删除节点，改善局部网格拓扑； 2 ) 高级操作：移动指定的网格拓扑系列，改善全局网格的拓扑关系。 优化算子： 边交换：交换四边形网格单元的边界边的顶点的连接关系； 边删除：将四边形网格单元的边界边删除； 单元合并：将两个或多个四边形网格单元合并成一个网格单元； 单元分裂：将一个网格单元分裂成两个网格单元。 2 几何优化操作：改变网格顶点的位置，调整网格的质量，使网格均匀。 1 7 海量空间数据点四边形网格优化算法的设计 二、基本拓扑优化操作 拓扑关系是指网格节点的连接关系，拓扑关系的调整是指改变节点之间的连接关系， 也包含增加或删除网格中的节点。拓扑关系的调整是基于节点的度进行的。三角形单元的 最佳形状是等边三角形，其内角为6 0 度，因而三角形网格中，一个非边界节点所连接的 相邻节点数目以6 最为理想，这样可以使得这一节点的周围单元在此点的平均内角为6 0 度。同理，四边形单元的最佳形状是正方形，其内角为9 0 度，因而四边形网格中，一个 非固定边界节点所连接的相邻节点数目以4 最为理想，这样可以使得这一节点的周围单元 在此点的平均内角为9 0 度。对于边界节点则可以根据节点的两条边线的内夹角计算决定。 在对四边形网格进行拓扑优化时，我们首先考察网格单元的边数，处理残留的三角形 网格单元；然后考察节点的度，进行边交换操作，最大限度地使每个节点的度调整为4 ； 最后进行固定边界边的优化处理。 ( 一) 边界处网格的优化处理 1 、边界角优化处理 对于有边界的非封闭曲面，边界处的四边形网格的质量是非常重要的，它直接影响到 曲面边界的拟和精度。如果两个边界边的夹角小于1 2 0 。时，寻找一个较优的新边界点，形 成一个新的四边形网格单元，大于1 2 0 0 小于2 4 0 。时，该角属于两个网格单元，在2 4 0 0 - 3 6 0 。 之间