二次贝塞尔有限元动画综述

一、引言我们研究了可变形体的图形动画对二次贝赛尔有限元素的使用。我们认为，结合二次元素与传统线性元件实现的计算效率，其自适应度仿真框架与完全只有二次非线性仿真模型一样好。在这两种情况下，我们采用Bezier基本函数和有限旋转线性公式。与线性元素比较，共同旋转公式，使我们能够预先计算每个单元的刚性矩阵，从而节省大量的计算。我们提出了几个例子，说明在一般二次元素和在特定情况下我们的系统适应程度都有很有优势。在过去的十年中,在计算机可变形体动画上使用有限元的方法呈现爆炸式增长。这些方法已被用于电影中许多特殊场景的绘制，同时也常用于动画视频游戏中的可变形体；由于其简单性和计算效率，计算机图形学已经普遍青睐线性仿真元素，包括它的几何学定义以及场变量。相反，计算机图形学以外的方法往往是首选高阶的方法。高阶元素方法与线性元素的方法比确实提供了几种重要的优势方法，但在计算机图形学中我们不必关心传统的精度和收敛的概念，特别是高阶的元素方法允许我们绘制非线性几何动画和提供一种自然的方式去为仿真网格添加自由度，可以让低分辨率的网格提供更高分辨率的动画。在这篇文章中，我们开发了一个基于Bezier基的二次四面体单元。然后我们将这一线性进行整合从而实现适应仿真系统，采用有限旋转线性公式，使我们能够预先计算每个单元的刚性矩阵和速度，从而促进计算，同时我们也通过非线性的其他模型元素来适应这种共同旋转的公式。其结果是一个模拟系统，相比线性有限元仿真，在一个适度的开销可以绘制非线性几何图形，从而能够在局部增加自由度而无需使用网格的策略二、相关工作由于OBrien和Hodgins工作上的创举，四面体有限元方法已在可变形体上成为一个非常受欢迎的方法。Muller和他的同事使用了一个共同旋转有限元法的公式，这种方法在计算机图形环境下是特别有吸引力的，因为线性应变刚性矩阵变得恒定而且可以预先计算。为此，我们采用这一方法。在这种方法的基础上，欧文和他的同事开发了一个非常强大的技术，这种技术能处理退化和倒置的元素。帕克和奥布来恩在实时视频游戏环境中使用的有限旋转方程模拟变形和断裂。最近，研究人员指出，传统共同旋转模型的实现在计算刚性矩阵忽略了旋转的衍生物，有这些衍生品存在可能会有稳定性问题。我们不是第一个在计算机图形学中使用高阶元素去仿真的研究人员，罗斯和他的同事们在十年前就使用基于Bezier的四面体有限元仿真。他们通过整合力分析避免了数值积分，就和我们在线性模型上做的一样。最近，Mezger和他的同事采用二次弹塑性旋转有限元仿真编辑模型。韦伯和他的同事还用二次Bezier旋转有限元进行交互式仿真并创造了GPU的实现。这些方法都没有考虑到适应度元素。Remion和他的同事对一维物体用样条函数进行高阶仿真。类似的，Kaldor和他的同事们用三次样条函数模拟针织布。Grinspun和他的同事们进行了几次模拟高阶基函数。Kaufmann和他的同事们使用无节点的二次多项式基函数以间断Galerkin方法定义任意多面体。其他一些研究人员着重于使用任意多面体元素。这些元素需要更复杂的基函数。Wicke和同事认为基础功能来自均值坐标,Martin和他的同事们使用的基础功能来自动调节的坐标。同理，veinKaufmann（考夫曼）和同事提出了一个扩展有限元法（XFEM），通过更新基础功能存储为高分辨率纹理模型裂缝的方法。Bickel及其同事使用径向基函数模型的异构性，非线性材料。径向基函数拟合了变形，被认为是一个局部线性应力-应变关系的样本。当然，高阶分析在工程和其他领域是常规的数值分析。我们的有限元法是更为一般的hp-FEM方法，由Babuska和他的同事们在固体力学领域开创的一个实例。这种方法既承认层次（H），即元素的几何划分，和多项式（P），即增量多项式，以及改进。工作在流体力学上的Orszag，他利用高阶基开创了光谱方法。常用的全局支持功能就使用了这种方法，虽然光谱元素法由有限元和光谱技术相结合，但它采用本地支持高阶分段多项式基。当我们的元素包含线性和二次边缘时，他们可能会认为这是过渡元素。近年来，人们的兴趣转为通过几何分析来寻求几何表示和有限元基函数的统一。Debunne及其同事利用一个非嵌套的四面体网格的多分辨率层次介绍了计算机图形学中的空间适应性。由Grinspun和他的同事们提出了另一个适应性的方法。他们提炼的基础功能不同于使用几何细化，他们在感兴趣的领域建立规模较小的四面体。这个方法与我们的方法精神上有点类似，然而，他们是在影响越来越有限的地区增加的基础功能，而我们增加我们的基础功能的度。他们的方法的优点是，它可以允许在网格细化任意的差异，而我们只限于两种不同程度的多项式。如果需要更高的分辨率，他们的方法可以用来补充我们的。三、方法一、BarycentricCoordinatesandBernsteinPolynomials（重心坐标和伯恩斯坦多项式）重心坐标允许我们在顶点一个单一的值表达数量。四面体内部的点的重心坐标α=[a0,a1,a2,a3]，其中aj=0,∑aj=1。第二个特性说明重心点坐标不独立。去除冗余的a0=1-a1-a2-a3,在一个经典的四面体V0=[0,0,0],V1=[1,0,0],V2=[0,1,0],V3=[0,0,1],上来看重心坐标。如下图在下面的部分中，我们将定义这个规范的四面体映射世界和物质空间。注意的是因为V0位于原点，Vj-Vo=Vj，我们接下来利用这种公式中的符号。我们使用伯恩斯坦多项式给出的Bezier（贝塞尔）基，推广通用的线性基函数在每个元素的使用。在这里，多项式的次数为n，点α表示重心坐标，i=[i0，i1，i2，i3]是一个多指标这样，|i|=∑ij=n，所有的ij=0我们选择Bezier（贝塞尔曲线）基于几个原因。首先，基于Bezier的方法非常直观，控制点很自然的与顶点和四面体的边缘联系起来。第二，基础函数都是非负的。第三，由于基函数和为一且非负，Bezier曲线有凸包性质。虽然在我们当前的实现中没有采取它的优势，这种特性对于精确的碰撞检测是特别有用的。最后，Bezier（贝塞尔曲线）在计算机图形领域非常适用。贝塞尔曲线相比其他有一个缺陷：他们没有层次感，跨越二次多项式空间的功能设置不包括用于跨度线性多项式函数。这意味着当我们改变我们元素的顺序的时候，我们不能简单地增加基函数；我们需要移动到一个不同的函数集上。二、Precomputation（预先计算）我们的实现能够使用几个显式或者隐式的方式集成。隐式集成需要建立一个矩阵系统，幸运的是，因为我们使用了一个旋转的线性模型，每个元素的刚性和阻尼是恒定的。因此，在仿真初期，我们预先计算了每个元素的线性和二次方程式的刚度和阻尼矩阵。刚度和阻尼矩阵包括不同旋转，然而它就不能预先计算。刚性矩阵的线性元素只有78独立的入口。然而，一个二次元素刚性矩阵是一个30*30的对称矩阵和包括465个入口。我们同样为每一个元素（另一个30元数）预先计算“forceoffsets（力补偿）”并为每个元素总计594个储存β矩阵和面积加权法线（在线性元素力的计算），每个元素的存储估计超过4.5kb，这可能会有大量的内存占用，但当考虑到将一个线性四面体的边缘中心分为8个四面体，这会产生624个独立的矩阵入口和72个力补偿，很明显二次四面体需要的内存在每个自由度上比线性四面体少。此外，我们现代的电脑内存需求是微不足道--即使我们最大的实验的内存需求也小于150MB。三、Adaptivity（适应性）在一个典型的仿真中，一般而言，大量的元素是非常接近其他配置的，如果其余的模型是线性的，进行补充计算这些四面体二次元素不能有效利用计算资源。因为这个原因，我们的系统采用线性和二次元素。为此，我们必须特殊对待边缘的那些易发生线性的二次四面体。从二次四面体的角度来看，沿边缘有一定程度的自由度，但线性四面体的角度就没有。我们通过在终点的平均值上沿边缘约束控制点位置和速度来处理这个实例。任何他们会加入到全局系统矩阵的值都会重新分配至终点。在这种情况下，在一个二次四面体的两边缘都受到约束，它们之间的相互作用入口可分为四个终点。在决定哪些元素应该是线性的，哪些应该是二次的时，通过看边缘的中心点能很便捷的决定边缘的自由度，各种规则可以用来确定一个边缘的自由度。我们通过下面的简单方法。每个四面体都有二次弹性力和阻尼计算。然后，对边缘中点的位置进行预测假设线性和二次状态并对结果进行比较。一种自适应度元素的后果是，全局系统矩阵的非零结构是不断变化的。在仿真开始的时候我们实现分配内存来存储整个刚性矩阵和二次四面体。我们存储矩阵以3*3为一个块并且只有矩阵的下三角部分存储。当边缘成为二次，控制点沿边缘变得活跃。如前所述，无效的控制点刚性值分配到边缘的端点。除了给刚性矩阵增加自由度，我们同时移除每个时步的自由度。在移除自由度时我们必须增加边缘终点的聚合度并调整它们的速度从而保持增长的势头。如果预测位置的差值大于阈值，边缘就是二次的。如果差值小于另一个（小点的）阈值，然后边缘是线性的。我们还需要边缘保持一个相同的状态，一个最小的时间步数来避免震荡。这种方法需要我们为每个元素增加矩阵维数，使用30*30的矩阵而不是12*12的矩阵，并且在线性元素和二次元素间体现了开销上很大的不同。在这种方式中，我们选择了一个减少坐标公式来制定约束条件的处理方法。另一个选择是拉格朗日乘子，这将允许用特别简洁的方法选择基于其相应的拉格朗日乘子的大小的边缘的自由度。四、相关讨论我们所有的四面体网格的生成与处理都是通过NETGEN[Schoberl1997]产生。碰撞检测和处理使用ElTopo[BrochuandBridson]。所有我们使用的例子每帧使用两到三步时（慢动作）。很不幸的是，ElTopo没有真正被设计用在这样大的时间步长。Linearvs.Quadraticvs.AdaptiveElements为了评估在选择线性和二次元素之间时的权衡因素，我们设置了几个非常简单的测试，包括一个一端固定的线条，可以在重力作用下摆动（见图）我们发现低自由度系统的二次元素表现非常好，但随着自由度数量的增加，差异变得难以辨别，回想起来，这个结果并不特别令人惊讶，在时间维度上我们关心计算机图形，体积弹性效应分辨率相当低的。这个事实已被众多研究者用于模型简化工作，或者嵌入在低分辨率的几何仿真网格中。相反，我们发现，随着分辨率的提高自适应单元二次元的优点变得更加重要。这一趋势是不足为奇的，在高分辨率下的变形比线性元更好。非常粗糙的模型适应性可以节省约10%的运行时间，而在“VeryFine”的例子适应性比二次示例减少了近四分之一的运行时间，大部分的节约来自矩阵求解，计算力需要更长的时间在自适应上。在包括的例子中，我们无法看到适应性和二次例子的不同，适应性的进步促进了高质量的结果产生，从而有了更低的消耗，却又区别于完全得二次仿真。当然，在挂杆的例子是显而易见的，过度激励适应性产生了令人印象深刻的运行时间，但会降低动画质量。螺旋线的例子包含其他非线性模型的元素，模型则通过使用二次元将静止姿态置于先前仿真结果中。25个橡皮小鸡的例子（参见下图）演示了将高分辨率界面网格嵌入到粗糙的自适应有限元网格中。在这个例子中鸡的碰撞是基于坐标系的，但是它们之间的相互碰撞以及内部对象间的碰撞就不能够保持稳定以及合理的步时。我们也希望通过使用我们的自适应框架来探索其他一些类型的变形体模拟，比如说断裂和弹塑性。在断裂的情况下，创造新的元素的需要不会允许我们在模拟的开始去预分配系统矩阵，也可能会丧失一些我们从每个单元刚度矩阵的预计算中获得的优势。在弹塑性的情况下，塑性变形会改变矩阵中的项数，也会使我们的预计算缺乏优势。然而，伯恩斯坦多项式的积分被限制于规范四面体中，并且所有的元素都是相同的。因此，我们能够避免存储每个单元刚度矩阵从而能够及时地对他们进行计算。尽管这肯定会增加每个时间步触发器的数量，这也将极大地减少储存。我们实行的一个限制是缺乏自适应时间步进，这也是我们有意识地决定不