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

1、变形网格上的非多项式伽辽金投影图一：我们的方法可以减少飞鸟周围的流体模拟，比相应的全模拟快2000倍以上。减少在该建筑场景的辐射计算，比相应的全辐射快113倍以上。摘要：本文将伽辽金投影扩展到图形中常见的大量非多项式位函数。我们通过在两个截然不同的问题上的应用证明方法的广泛适用性，即流体模拟和辐射渲染都采用变形网格。标准的伽辽金投影不能有效地近似这些现象。我们的方法与此不同，能使这些复杂的非多项式系统紧凑表示和逼近，其中包括商数及多项式的根。我们依靠表示各函数的模型缩减作为张量积，矩阵求逆和矩阵根的组成部分。一旦某函数在该形式中表示出来，它就可以很容易的模型缩减，并且它的降阶形式能够随时进行评

2、估，存储器成本只依赖于降维空间的维数。CR种类：I.3.7计算机图形:三维图像和现实动画，辐射算法；I.6.8模拟和建模模拟的种类动画；关键字：缩减模型，流体模拟，固流耦合，辐射。1、简介伽辽金投影在图形加速上令人吃惊。然而，尽管其有广泛的应用从全局照明到流体该方法的关键限制是底层现象必须是多项式，这种约束限制了其在计算机图形上的适用性。本文提出伽辽金投影在组成任何初等代数运算函数的有效延伸在算术加有理根的四则运算从而在图形中贯穿这种模式缩减方法的适用性。为了证明我们的方法的广泛适用性，我们将其用于两个显著不同的问题上：辐射渲染和流体模拟。尽管这两种现象都可以通过固定网格法用多项式格式表示，但

3、是我们认为实现几何畸变需要非多项式计算，以表现动力和外观的改变。理论上可以在这些函数中应用标准的伽辽金投影，但是这不会提高任何的运行速度。我们的技术与此不同，能够高效地模拟这些复杂的非多项式系统。与标准伽辽金投影相似，我们的方法不仅保留关键的最优保证，而且保证在缩减空间方面有着紧凑和易分析的模型。我们的方法有广泛的应用范围。环境交互方面，如在视频游戏和建筑设计应用上逐渐地融入物理模拟。我们的技术可以围绕包括人物角色和动物在内的操纵对象加入流动效果。我们也可以计算含有这些元素场景的实时辐射，正确地描绘他们的运动，形变和外观。甚至，本论文首次对伽辽金投影在非多项式系统方面的应用做出示范，并有可能使

4、得在许多新的现象中开放交互式的模拟。2、相关工作伽辽金投影在交互式图形的应用中提升线性和非线性形变，声音，渲染，流体的速度。这些应用程序有一个共同的思路，即其控制方程是多项式。我们的方法建立在这些之前努力地通过扩展伽辽金投影到非多项式的函数上，以覆盖更广的现象。非多项式函数的模型缩减。在数值分析中，伽辽金投影一直主要用于线性函数和有理函数。有理Krylov法近似于使在频域的一个有理传递函数使用矩匹配来找到线性时不变（LTI）系统的良好基和扩展。替代选择包括有理函数拟合法（也称多点方法）和平衡截断。这些工作和我们之间的主要区别是，他们的目标是为了减少线性时不变系统（LTIs）通过分析他们的有理传

5、递函数，而我们只对非多项式函数还原感兴趣。由于LTIs的约束性质，针对线性和多线性的扩展已经提出了时变系统。Farhood和Dullerud与我们所做的工作相同，他们采用有理Krylov方法使线性系统合理的依靠时变参数。然而，和我们工作不同的是他们不保证保留多项式阶的基本代数运算的任意组合，因此在复杂现象中难以进行计算。对于概率动力学使用类似于 Debusschere等人的代数方法，我们修改了伽辽金投影使得基本代数运算的任意组合保序减免。据我们了解，我们的研究结果是普通框架下基本代数运算任意组合伽辽金投影的第一部作品，同时保留了多项式阶这一实时图形的本质属性。并且也是变形网格上模拟变形网络流体

6、流动或辐射的第一部作品。伽辽金投影以外的技术能够对非多项式系统模型缩减。An等人证明了非线性弹性动力学模型缩减使用数值积分，它通过采样原始函数和在样本中使用装配模型近似于低维非线性函数。这种方法也可用于Chadwick等人提出的薄壳动力学的缩减。Kim等人也将这项技术用于流体模拟。和我们的工作相似，该工作也对逆矩阵模型缩减，并为动态的每一步建立独立的基质。一般情况，该模拟动力学的采样中数值积分的精确度取决于选择良好的基和良好的点集合，与我们工作不同，这里的精确度取决于基的选择。降阶流体模型。先前的图形中流体减少模型和高度严格边界条件数值分析。一个简单的解决方案是为每个可能的边界构造建立单独的基

7、。然而，这种方法不能扩展到连续变形边界。对于具有周期性边界，并与流体动力学中固有对称性的流动，可能会除去统一的转换模式。对于单一旋转对象，基可以建立在参考对象框架上，然后在各种角度进行模拟。Treuille等人采用刚性运动边界的插入，Wicke等人允许在运行时离散边界重新配置。也许Fogleman等人的工作最与我们接近。他们对模型缩减活塞和燃烧模拟能够线性变形沿单轴进行。我们通过嵌入在流体能连续边界运动的四面体网格，类似于Elcott的等人，使得能够连续边界运动。这需要一个适用于四面体网格的全维流体解算器。我们认为有几类求解法，包括有限元法，基于离散外部演算法，和ALE法。我们选择残差分配方案

8、，它是一个有限差分流体的近似，但是推广到四面体网格，由于其顺从于我们的非多项式伽辽金投影，它能够稳定的整合在一个缩减空间里。降阶全局照明。现有的降阶全局照明技术，如预计算辐射传递，不能准确模拟在非本地辐射传递的一般连续大规模场景变形的效果。James和Fatahalian允许变形对象，但是只针对一组特定的基于物理的变形。Sloan等人说明本地光传输的改变产生于普通的一套变形。最近的模型允许离散场景无需额外的预先计算，但不允许一般连续的外形变化。在本论文中，我们专注于模拟低频照明效果和使用辐射作为全局照明算法。许多方法已经被提出用于加快动力场景的辐射计算速度。然而，大多数之前的方法在刚性变换上有

9、限，诸如，插入，删除，以及在现场移动物体。辐射的实时计算对于可变现的场景来说仍是一个挑战。（我们标记不同场景下所使用的术语“伽辽金”描述使用平面补丁的弯曲几何近似，这与我们的加速标准辐射的目标不符）。3、多项式伽辽金投影许多领域的图形需要耗费时间的高维函数计算，例如光传输和流体方程。在核心中，模型缩减近似于这些更低维的函数。假设我们希望估计函数y=f(x)，这里输入的和输出的是非常高维的。我们寻求一个缩减的逼近，这里缩减输入和输出在一个低很多维的空间：和。第一步是线性维度缩减状态向量，这意味着找到了一对正交基，转化为降低全矢量载体：和。我们能够通过乘以转置从全投影到缩减的空间：和。第二步是模型

10、缩减变换f，这个f意味着找到一个有效的缩减近似：在缩减的空间完整运行。标准的做法是伽辽金投影，如果f是多项式但其他方面不够时，其效果很好。以下各节在高效模型缩减方程的形式方面介绍我们技术y=f(x)这里的f(x)可仅使用四个基本的算术运算和分数幂写入。我们首先描述标准的伽辽金投影，它允许我们模型缩减多项式，形成我们其他剩余部分方法的基础。然后，我们介绍此技术可以与少量的基础的矩阵运算进行组合，以便减少多种非多项式函数。5-9节应用此方法来模拟辐射和流体。符号。在本文的其余部分，更低的例子中出现的标量：x，粗体小写矢量：x，矩阵和张量：X。我们写表示张量乘法，张量Q沿着索引a的轴乘以随着指数轴矩

11、阵或矢量M。表示反复的张量积，。我从0开始计数张量轴。为了清楚起见，我们有时采用矩阵表示法 来表示沿着0轴的乘法，和符号QB表示沿着1轴的乘法，。我们指的是张量乘以一个向量作为张量收缩，这是一个降低的张量顺序的操作。一个d阶多项式q(x)能够被表示为一个d+1th顺序张量Q。例如，如果某些多项式p(x)具有3度和x是长度n，那么我就可以写p（x）作为组成部分。这里是多项式p(x)的系数。第四阶张量P只由多项式系数：，我们可以写下p（x）=。同样地，我们可以通过收缩相应的d+1th顺序张量来估计d阶多项式q（x）：算出多项式伽辽金投影：我们开始用缩减变量：（我们用提醒具有较少的自由度，以确保这个

12、方程的精确解。）然后我们乘上： 我们可以在运行时计算的值，其中积表示Q与的积沿着张量轴对应结果向量。被叫做伽辽金投影的Q。直观的说，在全空间使用变换缩减输入，使用Q，然后用将投影返回缩减空间。最后的投影会带来一些精度上的成本，但它明确规定，所以我们能写Eq。2和等号。投影很快：评估采用与评估Q相同数目的收缩，虽然现在每个收缩采用的是长度向量而不是长度n。4、非多项式伽辽金投影更困难的是，如何观察我们对非多项式函数高效地应用伽辽金投影。例如，决定有理函数y=f(x),这里，和：我们可以计算该函数的伽辽金投影，通过在全空间进行转化缩减载体，采用全空间方程，和突出返回缩减空间的结果，但这不会产生任何

13、速度上的优势。相反，我们使用两个张量表示f(x)，改写为矩阵矢量乘积：向量和矩阵在x中都是多项式（具体为二次）。因此我们能够用第四序列张量Q1评估矩阵，采用第三序列张量Q2评估向量：这里Q1和Q2是（通过相关联的多项式术语标记各张量片）：为了评估f（x），如上所示我们将Q1和Q2联系起来，然后逆矩阵，最后计算矩阵向量积。单一形式的方程：更一般地，我们通过依据张量集减少非多项式函数f(x)，并采用一系列张量收缩和矩阵运算。我们可以仅使用下列运算减少函数表达：这里的Q是（ii）和（iii）中的矩阵，Q是additionally symmetric和半正定，是唯一被标识为半正定的矩阵，如。正如我们在

14、§3所看到，多项式函数只需要一个张量，以反复应用的操作（i）进行评估。然而，如我们在方程3中所示，有许多情况，其中可能必须使用多个张量，和超越（i）的操作对f（x）评估。一旦我们已经表达了函数f(x)的张量，且允许矩阵运算，我们可以减少它。这就要求我们首先要为每个张量的每个轴找到基质。例如，对于一个多项式我们要求给y，独立的基质。一旦我们发现这些基质，我们可以通过其相关基质预先乘以每个张量，因为我们在方程式2计算，然后遵循完全用于计算的顺序操作计算f(x)，除了我们取代每个张量与其对应的减少数。也就是说，每一个操作的变换如下：如表中最后一列所示，每次减少很明确，这些减少确实影响到了基

15、础选择。因为我们需要减少沿着其各轴的每一个张量，需要每个张量的各轴上的基础。操作(ii)和(iii)要求Q使用沿两个轴相同的基础上减少。4.2节解释了这个约束，通常足够小，我们能使用特征分解进行有效的计算。4.1减少样例从之前的章节减少我们的示例函数（方程3），我们考察张量形式（方程4）来观察我们所需的基质。从右往左看，可见我们对于x需要一个基质，需要一个基质，y需要一个基质。根据约束，一个倒置矩阵必须由沿着两个相同基质的轴来进行缩减，并且我们都将参照。和的减少：为了在运行时评估函数我们执行：我们需要执行此计算的唯一数据是两个缩减张量和。如果我们希望显示运行时计算的完整空间结果，那么我们还需要

16、来计算。4.2性能我们对于缩减的选择并非是所能用于非多项式函数的唯一选择。我们本可以选择替换每个全空间操作，用某些比在执行缩减张量的相同操作更为复杂的操作。我们的方法就是这样，然后，它有三个主要的有点。第一，它很简单：一旦一个函数在张量方面被表达，减少由仅在用相应的降低维张量替换为全维张量中。第二，它很有效：张量序列由减少维持，这很重要，因为这两个张量的存储成本和评估时间复杂度在张量序列中指数表示。第三，它是最佳的：每个缩减规则被建立来最小化一些错误措施，对目标函数给张量一个特定分解。我们讨论每一个我们能依次操作的最佳性能。张量积。如果我们有一个d+1阶的单一张量，我们通过一个固定向量收缩d次

17、，然后最小为，正如方程1所示。逆矩阵。对于逆矩阵，操作(ii)中，使。在最小化。注意，这与普通的伽辽金投影不同，它是。我们也可以让和的基质不同，在这种情况下，误差将在最小化。然而我们发现设置在实践中有显著的益处，比如我们在流体应用 (§A.2)的节能。矩阵根。矩阵根，操作（iii），首先找到逼近的减少矩阵，其最佳逼近，计算。这个缩减矩阵是是，然后我们使用它逼近的n次方根。沿两轴相同的基础乘法Q确保同样是对称和半正定，我们再次减少不同于的普通伽辽金投影。最优速度权衡。在我们最优化讨论的操作（i）中，我们用一个单独的张量代表函数f(x)，我们在这种情况下限制自己。然而，在许多情况下我们能

18、够选择使用多个张量来表示一个多项式。这允许我们通过组合多项式来改变速度的最优化。假设，这里的q有阶d=ab，有阶a，有阶b。我们可以选择表达为或者（）。在全空间，该表述是一致的。但是，当降低时，这些表达式成为和。我们可以写出第二种情况：这相当于：请注意，该组合引入了一个额外的投影，这降低了缩减结果的准确性。在另一方面，该缩减组合比缩减的普通多项式计算得更快：该组合用两个小得多的缩减张量替代含个元素的缩减张量，一个包含个元素，而另一个包含个元素。4.3总结在这一节中，我们已证明，使用我们的非多项式伽辽金投影方法任何函数的构建从张量收缩，矩阵求逆和矩阵根能容易地模型缩减。为了缩减这样一个函数f(x

19、)，我们用一系列的张量构造它，其中我们应用我们的张量和矩阵运算。减少应对，然后可以通过简单地用张量替代张量，精确地保持相同的操作序列。如同4.2节描述的那样，我们的方法很简单有效，并且最佳。在本章的其余部分，我们证明应用这种技术到两个不同的问题：围绕变形对象的流体，对已存在的变形物体全局照明。 5、流体作为我们的非多项式伽辽金投影的第一个例子，我们描述在变形四面体网格上的流体流动的缩减。在这个系统中，网格运动对流体施加了力，但是流体运动的力不会引起网格移动。模拟状态由流体速度u和流体动量p，位于每个元素质心并通过每个面的流体通量f组成。（通常，人们只会用所描述的流体流动中的一种。如我们所见，非

20、多项式伽辽金投影要求分别处理这些工程量）我们要求网格拓扑保持不变，但是允许网格顶点的位置连续变换表示为g。（图3）我们从不可压缩的Navier-Stokes动量方程开始：其中p表示压力，v为粘度，e为外力。我们用 Dobes, Deconinck, and Ricchiuto的剩余分配方案离散处理该方程，这基本上是施加在四面体网格的一个有限差分法。我们用算子分裂在平流期分裂速度，对投影步骤进行扩散和增压。图二总结了该算法，在此我们用一个四阶Runge-Kutta积分方程整合了全空间方程，我们详细介绍了每个步骤。图2：全维和减少时间步骤算法总结。注意密切的对应关系。图3：一个四面体元件上的模拟变

21、量的几何布局5.1平流平流步通过网格传输量。我们对待分离速度的每个组成部分x，y，z，根据流量f将他们传输到网格元件之间。此传输由平流张量A描述，且说明了插值速度上的网格面，用f乘以速度插值以找到动量传输在每个面上的速率，最后对区域面上的动量传输求和，在区域找到动量导数，对区域i，有一个计算：其中对运行在四个面相邻区域到i的索引求和，表示i和e间（定向）面的索引。然而，我们并不主要对动量感兴趣，而是对速度。我们假定一个恒定密度（不可压缩的）流体，u和p受到5阶体积张量V影响，对V我们用来计算一个矩阵值顶点的三次多项式：其中，是区域k的体积并作为顶点函数。为清楚起见，我们将写下V（g）代替g。给

22、定V，我们可以计算动量：。这给我们平流方程：注意，该方程依赖几何g如果g不变，V将简单地作为一个常数矩阵，我们可以预先计算并将absorb it into A。因为我们要模拟的流体行为是存在几何改变中，我们必须明确表示V作为一个张量，可以收缩和逆化一个矩阵。这就要用到我们的非多项式伽辽金投影技术。5.2扩散我们的离散粘度如下：，其中是粘性系数，是graph Laplacian，是（通常是四个）四面体相邻四面体i,V是体积张量。我们已经发现很简单，几何近似到扩散足以在完整和缩减的空间。经过计算对于的平流和扩散的贡献，我们使用一个显式时间积分方案更新该速度。5.3投影给定一个速度u，投影步骤首先产

23、生一个流量f，接近u和满足不可压缩约束。然后，我们可以转换f回完全对应不可压缩流量。从通量速度进行转换，我们引入张量P，其将指向区域流量的加权量求和以获得区域的动量：。因此，对应f的的速度由给出的。需要注意的是这种关系只在流量f为流量到速度时有效。使用 flux-to-velocity转化和速度场u，我们可以找到通量场f，以满足我们不可压缩的约束。f=0，同时最小化相应速度和u之间的能量差别。要最小化的能量时：其中，我们使用Uzawas法中所描述的的最小化解决它。同样，因为我们需要执行流量到速度转换，我们必须通过区域体积V(g)来进行划分。在这种情况下，这些划分出现在我们的优化目标。图4：在我

24、们流体仿真应用中的四面体网格视图。5.4流体几何耦合要允许变形物体施加力到他们周围的流体，我们同时修改我们模拟中的平流和投影步骤。为了模拟在平流移动网格的影响，我们计算然后通过网格运动减去流动h。这保证了速度不会简单地转化，因为他们的离散元件在空间中运行。我们还修改了投影步骤以确保我们从来没有通过跨越移动域边界平流输送流体。面i的运动包括一个通量通过面等于 其中是面的区域， its normal，是质心的速度。为了补偿网格运动，我们可以在任何使用f的地方简单地减去。特别地，在平流步骤中由于流体通量的平流影响，我们减去流体通量的平流效果：。在投影步骤中，在投影中通过增加约束Df+Dh=0，我们执

25、行没有跨边界的流动。这里的D是一个选择边界面的算子。这些修改确保了流域的内部是独立的网格运动，并且这里跨越边界无流动（可能移动）。6、 缩减流体我们通过应用我们非多项式减少规则（第四节）对前面章节的流体模型建立减少模型。为了减少控制方程，我们不得不减少张量V，P，A，和D。因为我们要求每个张量（4.1节最后一段）的各轴的基质，我们会需要通量基质，速度基质，动量基质。因为V和P依赖几何结构，我们需要一个几何基质。我们还需要一个基质用于网格运动，一个基质用于边界通量。6.1基础建设运行时间的模拟质量很大程度取决于我们对基质的选择。我们使用类似于 Treuille et al. 2006的方法构建，

26、和。我们运行一组全维模拟和收集大矩阵模拟量快照，其中每一列表示一个仿真框架。我们通过运行核外奇异值分解创造基质在这些使用James and Fatahalian方法的矩阵上。在独立计算动量和速度基质后，我们可以将基质和re-orthonomalize连接。此过程确保，确保能够在缩减空间中能量保护和符合要求的矩阵求逆缩减。创建几何基质比较困难。我们从一系列的三角形网格动画开始，改变边界条件。例如鸟的翅膀拍打。我们选择一个中间姿势的边界网格，构建一个四面体基网格的离散模拟域。对于每个表面模型的变形状态，我们使用拉普拉斯变形转变改变基本网格，一遍嵌入式表面与变形表面模型相匹配。不幸地是，这一步会导致

27、颠倒元件，这对模拟来说是致命的打击。为了解决颠倒，我们将一下两步进行交错。首先，我们增加颠倒元件周围的权重，在拉普拉斯变形期间增加刚性，以避免颠倒。第二。我们通过运行Stellar 提高网格的质量，使我们修改留下表面定顶点而不发生改变。不幸的是，后一步骤课导致动画序列不连续，其中内部顶点的结构迅速地在模拟框架间发生改变。该popping artifact可以在我们的样例视频中看出，不是很糟糕，但是去掉它会可能提高模拟质量，这是未来研究待解决的问题。一旦我们有一个四面体网格动画，我们运行SVD去创造。6.2张量减少利用这些基地，我们按照第四节介绍的过程，将全空间张量转入减少方程式：压缩空间模拟过

28、程几乎与全空间（图二）完全相同，虽然我们做出几个小的改变。首先，我们记录下的值以及变形轨迹，以便我们将在运行时使用和重演这些轨迹来寻找，而不是从中计算h。第二，我们通过矩阵幂整合平流和扩散，而非像在全空间中那么明确。在全空间中，通过整合幂将确保该模拟在任何步骤中都很稳定。确保这个稳定结果可以被带入缩减空间。6.3约束流体模拟要求我们在缩减维模拟中保持全维精确约束。特别是，我们在缩减模拟中必须保持一个严格不可压缩的约束。如 Treuille et al. 2006，所有的基向量构造为免发散。他们在几何变形下保持无散度，由于通量单位出现在ACM TOG 32（4）中为volume 6。每单位时间都

29、是独立的几何形状。然而，与之前的工作不同，我们有多个基质，其关系与网格几何一起改变。特别是，速度和动量基质不一定无散度。因此缩减投影步骤是有必要的。缩减全维投影（公式10）我们得到：由于通量基质保证，我们可以省略在缩减投影中的约束。6.4流体几何耦合为了使几何结构的流动独立改变，我们像在全空间一样进行。计算平流时我们减去通量中的感应通量，因为和不同，要求我们产生两个缩减平流张量和；边界约束被添加到投影。当这个约束被用于缩减空间，我们应用约束缩减来确保履行缩减约束承担履行相应的全空间精确约束；这个过程也给我们的边界通量基质。6.5运行时可视化对于可视化的流场，我们用流动平流输送无质量的标志微粒。

30、每个粒子可以单独平流输送。由于速度状态不一定自由发散，我们从磁通场重建平流速度。我们假设在每个区域速度是恒定的。无论如何我们需要评估区域i的速度，局部计算：使用该技术，我们从不需要扩大几何结构或通量的充分代表性。相反，对于每个粒子，我们记得目前面i包含它。然后，我们只评估几何结构的部分，必需计算。我们只需要计算顶点入射到当前元件的位置和它的相邻位置，以及跨越当前元件的面的通量。然后。我们可以平流输送所计算速度的微粒。微粒可能离开当前所处区域，或者是因为颗粒是平流移动，又或是因为网格变形。在那种情况下，我们移动穿越开始于微粒的最后已经位置的网格，并朝着微粒新位置的方向移动。我们评估网格几何结构只

31、能在本地进行，并且在我们能够找到一个包含微粒的元件前只能继续移动。对于平流，我们使用显式欧拉积分，并在附属的视频示例展示中每帧分为十个子步。7、 流体结果我们通过两个方法评估我们的缩减流体模拟：从一个包含一个简单障碍的2D风洞域评估它的数字错误，并通过两个有复杂边界运动的不同3D域展示它的定性行为。7.1数值误差分析为了评估我们方法的准确度，我们对于一个简单的两维例子从全维范围实况模拟测量偏差。我们在含有单一三角形障碍物的二维周期性隧道形域中运行全模拟，使用模拟帧来计算不同尺寸的基质。在图5（a-c）中我们展示了一些示例帧和基础向量图。图5：我们的流体应用错误分析结果。（a）两个训练仿真帧：一

32、个具有大的障碍，一个具有小的障碍。（b）一个中等障碍的领域中一个缩减测试模拟的相应帧。（c）从（a）训练中得到的速度基质的选择矢量用于（b）。（d）超过1000帧进程的相对一步法误差用于缩减不同尺寸基质的模型。（e）不同尺寸基质的模型的综合一步法误差。时间平均积分误差随着基质尺寸单调减少。图6：我们的方法以每秒70帧模拟此变形混合室（每秒3帧的渲染）。为了给出缩减模型在一系列状态中如何精确地用速度基质捕获模拟动力学的清晰图片，我们使用单步误差测量。为找到单步误差，我们以一系列速度快照开始，从全维模拟和将它们投影到，使用一个节能投影来找到缩减坐标。从每个缩减坐标，我们采取一个完整的时间步长来获得

33、，我们采取缩减时间步长来获得。使速度场u的能量。一步法误差为。图5（d）绘出了对于一定范围大小基质的一步法误差的演变模拟。图5（e）绘出整个完整的模拟中相同误差。图5（d）和（e）中，我们可以看到，随着我们增加更多的基质向量，误差趋势开始降低。这肯定了我们的方法，随着基础向量的数量发展到全模拟的维度，我们的方法收敛到地面实况。而基质尺寸误差下降是单调时随着时间（e）误差达到平均值，它并不一定如(d)瞬时。我们一步误差处理确保尽可能每个模拟开始每一步接近于一个相似的完全状态，然而，由于基础表现力的差异，不同基质尺寸上的模拟会从略有不同初始状态开始。因此，在误差单调减少的一些偏差在某个时间步应该被

34、提前考虑。7.2 3D结果在这些结果中，我们使用一个110个节点集群与2.2GHz的SMT四核AMD皓龙处理器做预计算，以及2.6GHz的8核英特尔至强处理器，24GB内存用于实时模拟，渲染和计时比较。我们预计算挂钟计时结果包括PCA和自左乘张量时间。我们使用串行PCA执行计算每个基质，因此，只有该自左乘张量被整个集群完全并行。我们的运行时序结果（表1）包括模拟和粒子平流运行时间。变形腔体。腔体模型（图6）包括一个大的中央腔和三个相邻较小的腔，由细小的隧道连接。各个小腔可以单独压缩，使它们的内部的流体可以流入中央腔，这相应地改变了中央腔的体积。我们使用简单的级组建基元设计腔体，然后使用CGAL

35、将内部等值面tetrahedralized。我们通过解析压缩外腔产生一系列变形序列的例子，一或两个小腔每次捕捉的压缩和再填充，重整体积和使用这些变形来产生14个全空间的模拟。并非所有在视频中看到的变形都是原始集的一部分（例如，训练集不包含如一个腔体膨胀而另一个保持压缩的任何例子）。预计算这个例子用了挂钟时间的12个小时，其中大约最后半小时用于张量自左乘。在运行时间，我们可以以每秒70帧模拟，然而由于模拟中的粒子的密集覆盖，平流传输粒子和渲染粒子的帧率减小到每秒三帧。我们已没有继续进行的各种形式的优化，例如并行化，可以进一步增加帧率。鹰。我们的鹰样例（图1，图4）展示出了不同的用例。在此我们以6

36、01帧三角网格动画的飞鹰山东翅膀和左右翱翔开始。我们如6.1节描述所述，建立了一个变形的四面体网格，使用Tetgen Si 2007的方法产生了一个基础网格来tetrahedralize 完全伸展翅膀的鹰的周围空间。我们为使用快照计算出一个单独266帧全维模拟。预计算在这个例子中花了大约四个小时的时钟时间，其中最后半小时也用于张量的自左乘。注意，该特定变形序列不需要被预定；原则上，这种方法可以用一个完整的运动图扩展到模型变形，它在运行时决定实际的字符运动。伴随视频呈现了这些模拟，这些交互模拟，但是与全模拟比较对于Pbrt呈现离线Pharr and Humphreys 2004。8、缩减辐射我们

37、现在根据不同的照明，应用我们的模型缩减技术到扩散变形物的全局照明（辐射）实时计算。和之前一样，我们首先用张量收缩和矩阵运算改写辐射方程，然后应用第4节的投影规则获得一个缩减模型。我们用此缩减模型以交互式探索建筑环境的照明设计。以下是Goral等人的方法，我们将场景划分为离散补丁，如下计算辐射：其中b是所有面的辐射的一个向量，是反照率的对焦矩阵，e是入射照明强度的矢量，F是形式因素的矩阵：描述光从入射面J反射到面i的分数。注意，不同于流体模拟，辐射需要在场景组成部分间密集的交互建模，这增加了n到个面场景下计算的复杂性。表1：运行时为我们的例子进行统计：该表显示全维变形的定时，平流和投影，以及缩减

38、模拟和粒子平流传输。它还包括区域的数目，面和边缘确定全模拟的维数。流量的缩减基质维数，速度和几何基质，分别为，和。8.1 张量的辐射公式通常，公式14描述了直接光照和辐射间的一个简单的线性关系。然而，如果场景中的物体移动或变形，该等式会变得高度非线性。图14中重要的一项为形式因素矩阵F，这是我们从每个面的质心采样以获得：其中是1，如果面i和j相互可见，和0，否则，是面i的区域，是三角形i的质心，作为两个i的边缘的向量叉积而被计算。为了使用我们的非多项式伽辽金投影法模拟减少该等式，我们需要代表它作为张量积，逆矩阵，矩阵根的组成。此组合物需要比我们的流体应用更多的张量，然而，每个张量的使用趋于简单

39、。我们的张量表示需要我们能够通过重新索引：展开到矢量，这里，n是网格中面的数量。我们还需要颠倒指数，以便。我们在表2中总结了必须的基质和张量；感兴趣的读者可以在补充材料参考B节完成一个完整的推导。然后我们可以通过按序评估表2中的每一行来评估b。辐射方程（等式14）的张量形式在表格的最后一行给出。其中E是三阶张量，变换所述展开的形式因素向量p返回形式因素矩阵F，并用面反射率左乘F。8.2 缩减辐射方程我们首先用一组网格变形，并为每个变形计算在表2中2、3列描述的中间向量数量。我们在这些向量数量上运行PCA以获得相应的10个基质（列4）。使用这些基质，我们应用我们的非多项式伽辽金投影技术（4节）来

40、计算减少形式因素。这个减少包含表2中3列的每一个张量被第5列的相同减少替换。8.3缩减可见度目前还不清楚怎么写一个二元连续函数，如可见度使用我们的张量公式，所以我们要分开处理。需要注意的是在运行时计算一个可见度的新变形会太慢，会破坏模型缩减的目的。相反，我们使用以下策略：首先，我们计算可见度相应的变形集合G，并在上面运行PCA来形成可见度基质。然后确定新的变形的缩减可见度作为训练集中可见度的凸组合。我们发现训练变形的凸组合x，预测：是缩减可见度向量的凸组合，且具有相同的系数。需要注意的是和能够被预计算并且他们的大小不依赖于网格中顶点的数量。这是一个合理的策略，由于两个相似的缩减几何结构变形将会

41、类似于全空间的几何结构，并因此会有相似的可见度，我们主要关心在照明区域下的低频interreflections。9、 辐射结果我们通过证明一个交互式方法证明我们的缩减辐射方法，探索建筑设计的空间以达到某种所需的照明条件，类似于 Dorsey et al. 1991。创建一个令人愉悦的照明空间需要仔细选择房间的布置，房间大小，窗户位置，相对于自然光源的空间方位，等等。我们模拟一个有一个客厅和卧室的场景，由5012个面组成。客厅明亮且为浅色墙壁，卧室光线昏暗且墙壁颜色较深。在现场，天窗，窗户和门的尺寸可以交互式的改变，客厅的天花板可以倾斜。我们对这个场景的训练集由540个样本组成，包括沿结构空间轴

42、的极值位置和从空间内部抽取的样本。我们在样本上运行PCA选择基质向量捕捉每个中间量（表2，第4列）99%的方差，最多为60向量。可见度基质，area-free形式因素基质，以及外形因素基质达到60向量帽；所有的其他方法能够捕捉99.9%的方差并比60向量花费更少。与流体模拟相比，我们合并和正交基质对来遵守我们逆矩阵和矩阵根的要求。我们合并的基质对是，和。我们为和使用相同的120向量基质。我们在一个8节点Amazon EC2集群组成的8核2.67GHz的英特尔处理器和67.5GB的RAM上的运行基质选择和预计算。（下转图8下面）表2：基质，运算符和伽辽金投影被用于我们的缩减形式的实现。辐射渲染由

43、从顶部到底部计算该表，要么在全空间（2、3列）或缩减空间（5列）。注意，虽然流体应用需要只需要4个碱基，计算辐射形式因素需要9个基质（这里也列出了12个基质，但我们约束）。有关详细推导和符号说明请见补充材料的B节。图7：我们建筑渲染例子的结果。环境有两个房间，有浅色墙的明亮客厅由一道门与暗色墙的昏暗卧室连接起来。这个场景被阴暗的天空透过两扇窗口和一个天窗照亮。场景网格由5012个面组成，天窗，窗户，和门的尺寸能够被交互式改变。此外，客厅的天花板可以倾斜。（a）我们的模型缩减辐射的实现产生的结果。（b）由全空间辐射的实现产生的结果。注意地面实况和模型缩减渲染之间的性质相似。注意立方体附近的亮点和

44、床脚，以及窗口下面。有缩减和全空间的工件，效果由近边缘的粗糙网格决定。图8：模型缩减过程中包含和排除的直接照明，在此过程中相对误差的两种辐射动画传递。我们的辐射基质计算采样明亮场景比昏暗场景更重，所以明亮场景在最后的结果中表示的更精确。然而，这两个阶段分别主要由集群I/O带宽限制。预计算花费5小时1分钟的挂钟时间用于PCA，1小时36分的挂钟时间用于张量预计算。我们展示了两个模拟序列，420和500帧，用我们的缩减模型，并用全空间渲染和他们比较（图7）。每个序列两次用两种不同的方法来计算直接照明。第一种方法是在运行时使用基于物理的天空模型，在我们的缩减辐射外计算直接照明。第二种，是通过在窗口放

45、置区域灯光在我们的模型内计算直接照明。图8展示了这些结果的相对误差，这两种方法的测试动画中误差在3%到11%间变化。空间的综合分析和全空间的时间需求以及辐射的缩减方法都取决于特定算法和执行。我们只讨论在交互式应用关于传统辐射的相对效益。我们的全空间辐射实施不需要预计算时间，其运行在每秒0.2帧且需要200MB的内存。我们的缩减辐射实施需要6小时37分钟的预计算时间，运行在每秒22.7帧，且仅需要50MB的内存。在这种设置下，我们的方法在其实现了113倍的运行加速。如果我们预计算形式因素，我们可以以每秒0.4帧从磁盘加载他们，减少加速至57倍。但是在大量预计算的花费和所需存储时，它和我们的缩减方法不同，将与帧视野的数量一同增长。