变形网格上的非多项式Galerkin投影.doc

变形网格上的非多项式伽辽金投影 图一：我们的方法可以减少飞鸟周围的流体模拟，比相应的全模拟快2000倍以上。减少在该建筑场景的辐射计算，比相应的全辐射快113倍以上。 摘要：本文将伽辽金投影扩展到图形中常见的大量非多项式位函数。我们通过在两个截然不同的问题上的应用证明方法的广泛适用性，即流体模拟和辐射渲染都采用变形网格。标准的伽辽金投影不能有效地近似这些现象。我们的方法与此不同，能使这些复杂的非多项式系统紧凑表示和逼近，其中包括商数及多项式的根。我们依靠表示各函数的模型缩减作为张量积，矩阵求逆和矩阵根的组成部分。一旦某函数在该形式中表示出来，它就可以很容易的模型缩减，并且它的降阶形式能够随时进行评估，存储器成本只依赖于降维空间的维数。 CR种类：I.3.7[计算机图形]:三维图像和现实动画，辐射算法；I.6.8[模拟和建模]模拟的种类——动画； 关键字：缩减模型，流体模拟，固流耦合，辐射。 1、简介 伽辽金投影在图形加速上令人吃惊。然而，尽管其有广泛的应用——从全局照明到流体——该方法的关键限制是底层现象必须是多项式，这种约束限制了其在计算机图形上的适用性。 本文提出伽辽金投影在组成任何初等代数运算函数的有效延伸——在算术加有理根的四则运算——从而在图形中贯穿这种模式缩减方法的适用性。为了证明我们的方法的广泛适用性，我们将其用于两个显著不同的问题上：辐射渲染和流体模拟。尽管这两种现象都可以通过固定网格法用多项式格式表示，但是我们认为实现几何畸变需要非多项式计算，以表现动力和外观的改变。理论上可以在这些函数中应用标准的伽辽金投影，但是这不会提高任何的运行速度。我们的技术与此不同，能够高效地模拟这些复杂的非多项式系统。与标准伽辽金投影相似，我们的方法不仅保留关键的最优保证，而且保证在缩减空间方面有着紧凑和易分析的模型。 我们的方法有广泛的应用范围。环境交互方面，如在视频游戏和建筑设计应用上逐渐地融入物理模拟。我们的技术可以围绕包括人物角色和动物在内的操纵对象加入流动效果。我们也可以计算含有这些元素场景的实时辐射，正确地描绘他们的运动，形变和外观。甚至，本论文首次对伽辽金投影在非多项式系统方面的应用做出示范，并有可能使得在许多新的现象中开放交互式的模拟。 2、相关工作 伽辽金投影在交互式图形的应用中提升线性和非线性形变，声音，渲染，流体的速度。这些应用程序有一个共同的思路，即其控制方程是多项式。我们的方法建立在这些之前努力地通过扩展伽辽金投影到非多项式的函数上，以覆盖更广的现象。 非多项式函数的模型缩减。在数值分析中，伽辽金投影一直主要用于线性函数和有理函数。有理Krylov法近似于使在频域的一个有理传递函数使用矩匹配来找到线性时不变（LTI）系统的良好基和扩展。替代选择包括有理函数拟合法（也称多点方法）和平衡截断。这些工作和我们之间的主要区别是，他们的目标是为了减少线性时不变系统（LTIs）通过分析他们的有理传递函数，而我们只对非多项式函数还原感兴趣。 由于LTIs的约束性质，针对线性和多线性的扩展已经提出了时变系统。Farhood和Dullerud与我们所做的工作相同，他们采用有理Krylov方法使线性系统合理的依靠时变参数。然而，和我们工作不同的是他们不保证保留多项式阶的基本代数运算的任意组合，因此在复杂现象中难以进行计算。对于概率动力学使用类似于 Debusschere等人的代数方法，我们修改了伽辽金投影使得基本代数运算的任意组合保序减免。据我们了解，我们的研究结果是普通框架下基本代数运算任意组合伽辽金投影的第一部作品，同时保留了多项式阶这一实时图形的本质属性。并且也是变形网格上模拟变形网络流体流动或辐射的第一部作品。 伽辽金投影以外的技术能够对非多项式系统模型缩减。An等人证明了非线性弹性动力学模型缩减使用数值积分，它通过采样原始函数和在样本中使用装配模型近似于低维非线性函数。这种方法也可用于Chadwick等人提出的薄壳动力学的缩减。Kim等人也将这项技术用于流体模拟。和我们的工作相似，该工作也对逆矩阵模型缩减，并为动态的每一步建立独立的基质。一般情况，该模拟动力学的采样中数值积分的精确度取决于选择良好的基和良好的点集合，与我们工作不同，这里的精确度取决于基的选择。 降阶流体模型。先前的图形中流体减少模型和高度严格边界条件数值分析。一个简单的解决方案是为每个可能的边界构造建立单独的基。然而，这种方法不能扩展到连续变形边界。对于具有周期性边界，并与流体动力学中固有对称性的流动，可能会除去统一的转换模式。对于单一旋转对象，基可以建立在参考对象框架上，然后在各种角度进行模拟。Treuille等人采用刚性运动边界的插入，Wicke等人允许在运行时离散边界重新配置。也许Fogleman等人的工作最与我们接近。他