高质量可控四边风格生成技术

摘要

四边网格在有限元模拟仿真、样条曲面、参数化以及纹理贴图等领域有着非常广泛的应用。相比常用的三角网格,四边网格不仅天然具有张量积性质,而且在有限元计算中提供了更好的计算精度和收敛速度。近年来,四边网格生成技术已经成为计算机图形学的研究热点之一。然而,生成符合应用需求的高质量四边网格依然非常困难,主要原因如下:
　　 (1)不同的应用对四边网格提出了复杂多样的控制需求,如面片形状、采样密度、边方向、特征对齐等,同时这些需求之间还相互关联和影响,甚至存在矛盾。因此算法需要综合考虑所有的因素,自动协调优化,最大程度满足需求。
　　 (2)四边网格的拓扑结构对网格质量起着至关重要的作用。用户期望生成完全四边网格,网格中奇异点应当分布合理,基网格结构要尽量简单。因此算法需要在满足上述需求的同时对网格拓扑进行全局优化。
　　 已有的四边网格生成技术普遍存在缺少控制手段、自动化程度不高、过度依赖方向场、难以对拓扑进行优化等问题。因此,研究新的四边网格生成技术有着非常重要的意义。本文主要研究在复杂多样的控制需求下生成高质量完全四边网格的技术,主要贡献包括:
　　 1.提出了一种基于谱分析的可控四边网格生成技术。该技术能够对四边网格的面片形状、密度、边方向和特征对齐进行灵活有效的控制,生成高质量的完全四边网格。一方面,算法继承了传统谱分析技术的优点,从理论上保证能够生成均匀且奇异点少的完全四边网格。另一方面,算法使用离散余弦变换近似,建立了特征函数与莫尔斯复形之间的内在联系,从而能够对莫尔斯复形及生成网格进行有效控制。所有的控制和需求都被统一成一个带约束的广义特征问题加以优化求解,生成网格具有奇异点少、网格均匀、对噪音不敏感等特点。
　　 2.提出了一种基于驻波构造的各向异性四边网格生成技术。如何在复杂的控制需求下对网格结构进行全局优化是当前四边网格生成领域中的主要难点。该技术在深入挖掘四边网格和驻波内在关系的基础上,由驻波构造这一全新角度给出了解决方案。算法的基本思路是将四边网格的生成问题转化为模型表面上二维驻波的构造问题,而所有的控制需求则相应转化为驻波中的各种物理属性约束,在构造过程中自动获得全局优化。同时,算法还提供了各向异性的采样密度控制,进一步扩大了优化空间,提高了算法的适应性。实验表明,该技术能够很好地处理各种用户需求及复杂模型,自动优化奇异点分布,生成高质量网格。
　　 3.提出了一种分而治之的四边网格生成技术。现实应用中的许多模型里都存在着高层的语义结构信患:如相似或重复、全局或局部对称等,这些高层信息应该被用来更好地指导网格生成。同时,为了保证结果质量,目前主流算法均需通过全局优化的方式进行求解,随着模型规模的增大,计算代价将急速上升。针对这些问题,本文提出一种分而治之的策略,首先将输入模型分割为一系列有语义的子模型,然后分别为每个子模型独立生成四边网格,最后将它们拼接起来获得最终结果。为了保证所有子模型的四边网格能够无缝拼接,算法将各种情况下的边界拼接条件统一为一个混合整数规划问题,并设计了一个启发式的分步优化策略快速求解。同时,算法还根据模型的语义信息,通过四边网格模板和对称性保持技术对网格整体结构进行指导和控制。分而治之的求解框架一方面降低了计算代价和优化问题的复杂度,另一方面还提供了高层的语义结构控制,因此能够鲁棒且高效地处理复杂大模型,获得高质量的结果。