搜索
变形网格上的非多项式伽辽金投影图一：我们的方法可以减少飞鸟周围的流体模拟，比相应的全模拟快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等人的工作最与我们接近。他们对模型缩减活塞和燃烧模拟能够线性变形沿单轴进行。我们通过嵌入在流体能连续边界运动的四面体网格，类似于Elcott的等人，使得能够连续边界运动。这需要一个适用于四面体网格的全维流体解算器。我们认为有几类求解法，包括有限元法，基于离散外部演算法，和ALE法。我们选择残差分配方案，它是一个有限差分流体的近似，但是推广到四面体网格，由于其顺从于我们的非多项式伽辽金投影，它能够稳定的整合在一个缩减空间里。降阶全局照明。现有的降阶全局照明技术，如预计算辐射传递，不能准确模拟在非本地辐射传递的一般连续大规模场景变形的效果。James和Fatahalian允许变形对象，但是只针对一组特定的基于物理的变形。Sloan等人说明本地光传输的改变产生于普通的一套变形。最近的模型允许离散场景无需额外的预先计算，但不允许一般连续的外形变化。在本论文中，我们专注于模拟低频照明效果和使用辐射作为全局照明算法。许多方法已经被提出用于加快动力场景的辐射计算速度。然而，大多数之前的方法在刚性变换上有限，诸如，插入，删除，以及在现场移动物体。辐射的实时计算对于可变现的场景来说仍是一个挑战。（我们标记不同场景下所使用的术语“伽辽金”描述使用平面补丁的弯曲几何近似，这与我们的加速标准辐射的目标不符）。3、多项式伽辽金投影许多领域的图形需要耗费时间的高维函数计算，例如光传输和流体方程。在核心中，模型缩减近似于这些更低维的函数。假设我们希望估计函数y=f(x)，这里输入的nRx和输出的mRy是非常高维的。我们寻求一个缩减的逼近)ˆ(ˆˆxqy，这里缩减输入nRxˆˆ和输出)ˆ(ˆˆxqy在一个低很多维的空间：nnˆ和mmˆ。第一步是线性维度缩减状态向量，这意味着找到了一对正交基xB，yB，转化为降低全矢量载体：xBxxˆ和yByyˆ。我们能够通过乘以转置从全投影到缩减的空间：xBxTxˆ和yByTyˆ。第二步是模型缩减变换f，这个f意味着找到一个有效的缩减近似qˆ：mnRRˆˆ在缩减的空间完整运行。标准的做法是伽辽金投影，如果f是多项式但其他方面不够时，其效果很好。以下各节在高效模型缩减方程的形式方面介绍我们技术y=f(x)这里的f(x)可仅使用四个基本的算术运算和分数幂写入。我们首先描述标准的伽辽金投影，它允许我们模型缩减多项式，形成我们其他剩余部分方法的基础。然后，我们介绍此技术可以与少量的基础的矩阵运算进行组合，以便减少多种非多项式函数。5-9节应用此方法来模拟辐射和流体。符号。在本文的其余部分，更低的例子中出现的标量：x，粗体小写矢量：x，矩阵和张量：X。我们写MQa表示张量乘法，张量Q沿着索引a的轴乘以随着指数轴矩阵或矢量M。MQba...表示反复的张量积，MMMQbaa...1。我从0开始计数张量轴。为了清楚起见，我们有时采用矩阵表示法QBT来表示沿着0轴的乘法，BQ0，和符号QB表示沿着1轴的乘法，BQ1。我们指的是张量乘以一个向量作为张量收缩，这是一个降低的张量顺序的操作。一个d阶多项式q(x)能够被表示为一个d+1th顺序张量Q。例如，如果某些多项式p(x)具有3度和x是长度n，那么我就可以写p（x）作为组成部分。这里ijklc是多项式p(x)的系数。第四阶张量P只由多项式系数：ijklijklcP，我们可以写下p（x）=xP3...1。同样地，我们可以通过收缩相应的d+1th顺序张量来估计d阶多项式q（x）：算出多项式伽辽金投影：我们开始用缩减变量：（我们用≈提醒yˆ具有较少的自由度，以确保这个方程的精确解。）然后我们乘上TyB：我们可以在运行时计算yˆ的值，xQydˆˆˆ...1，其中积QBTy表示Q与yB的积沿着张量轴对应结果向量yˆ。Qˆ被叫做伽辽金投影的Q。直观的说，Qˆ在全空间使用TyB变换缩减输入xˆ，使用Q，然后用TyB将投影返回缩减空间。最后的投影会带来一些精度上的成本，但它明确规定yˆ，所以我们能写Eq。2和等号。投影很快：评估Qˆ采用与评估Q相同数目的收缩，虽然现在每个收缩采用的是长度向量nˆ而不是长度n。4、非多项式伽辽金投影更困难的是，如何观察我们对非多项式函数高效地应用伽辽金投影。例如，决定有理函数y=f(x),这里Txxx],[21，Tyyy],[21，和：我们可以计算该函数的伽辽金投影，通过在全空间进行转化缩减载体，采用全空间方程，和突出返回缩减空间的结果，但这不会产生任何速度上的优势。相反，我们使用两个张量表示f(x)，改写为矩阵矢量乘积：向量和矩阵在x中都是多项式（具体为二次）。因此我们能够用第四序列张量Q1评估矩阵，采用第三序列张量Q2评估向量：这里Q1和Q2是（通过相关联的多项式术语标记各张量片）：为了评估f（x），如上所示我们将Q1和Q2联系起来，然后逆矩阵xxQ321，最后计算矩阵向量积。单一形式的方程：更一般地，我们通过依据张量kQQ...1集减少非多项式函数f(x)，并采用一系列张量收缩和矩阵运算。我们可以仅使用下列运算减少函数表达：这里的Q是（ii）和（iii）中的矩阵，Q是additionallysymmetric和半正定，21Q是唯一被标识为半正定的矩阵，如QQnn)(1。正如我们在§3所看到，多项式函数只需要一个张量，以反复应用的操作（i）进行评估。然而，如我们在方程3中所示，有许多情况，其中可能必须使用多个张量，和超越（i）的操作对f（x）评估。一旦我们已经表达了函数f(x)的张量kQQ...1，且允许矩阵运算，我们可以减少它。这就要求我们首先要为每个张量iQ的每个轴找到基质。例如，对于一个多项式),...,(diixxqy我们要求给y，dxx...1独立的基质。一旦我们发现这些基质，我们可以通过其相关基质预先乘以每个张量，因为我们在方程式2计算)ˆ(ˆxf，然后遵循完全用于计算的顺序操作计算f(x)，除了我们取代每个张量iQ与其对应的减少数iQˆ。也就是说，每一个操作的变换如下：如表中最后一列所示，每次减少很明确，这些减少确实影响到了基础选择。因为我们需要减少沿着其各轴的每一个张量，需要每个张量的各轴上的基础。操作(ii)和(iii)要求Q使用沿两个轴相同的基础上减少。4.2节解释了这个约束，Qˆ通常足够小，我们能使用特征分解进行有效的计算nQ1。4.1减少样例从之前的章节减少我们的示例函数（方程3），我们考察张量形式（方程4）来观察我们所需的基质。从右往左看，可见我们对于x需要一个xB基质，xxQ212需要一个nB基质，y需要一个yB基质。根据约束，一个倒置矩阵必须由沿着两个相同基质的轴来进行缩减，nyBB，并且我们都将参照yB。1Q和2Q的减少：为了在运行时评估函数)ˆ(ˆxf我们执行：我们需要执行此计算的唯一数据是两个缩减张量1ˆQ和2ˆQ。如果我们希望显示运行时计算的完整空间结果，那么我们还需要yB来计算yByyˆ。4.2性能我们对于缩减的选择并非是所能用于非多项式函数的唯一选择。我们本可以选择替换每个全空间操作，用某些比在执行缩减张量的相同操作更为复杂的操作。我们的方法就是这样，然后，它有三个主要的有点。第一，它很简单：一旦一个函数在张量方面被表达，减少由仅在用相应的降低维张量替换为全维张量中。第二，它很有效：张量序列由减少