我们提供了从辐射度方程进行即时渲染的基本步骤。直接在纹理化场景描述上操作，非常高效且简单的算法可以生成照片级真实图像，而无需任何有限元核心或对基础积分方程进行离散化处理。通过利用图形硬件，利用用于解决全局光照问题的准随机游走确定性技术以及抖动低差异采样的新方法获得仅需数秒钟的渲染速率。分类和学科描述：I.3.3 [计算机图形学]：图片/图像生成 - 抗锯齿| 位图和帧缓冲操作| 显示算法| 查看算法;I.3.7 [计算机图形学]：三维图形和现实 - 动画|颜色，阴影，阴影和纹理|光能传递关键词：辐射方程，辐射率，阴影，蒙特卡罗积分，准蒙特卡罗积分，准随机游走，抖动低差异采样，硬件，累积缓冲区，实时渲染算法，照片写实。1 介绍提供一个写实场景描述，这个场景由辐射度积分方程[Kaj86]渲染而产生写实图像。在漫反射的前提下，得到弗雷德霍姆积分方程近似解的最常用方法是辐射度算法。 在经典算法[CW93]中，辐射度积分方程的核心是通过投影到某些有限基上，得到为场景元素数量的二次方的形状因子矩阵。 对于它的稀疏表示，已经引入了具有阶梯型基函数的阶梯型方法。 尽管如此，这些Galerkin算法需要存储积分方程的内核和离散解。除了用于高度复杂精确网格生成的阴影表示[LTG92]外，这样的投影还引入了离散化误差。在蒙特卡罗仿真领域中，不需要内核离散化的算法也是可行的，使用仅需要把解投影到有限基上的随机积分方案。与随机渐进法相似，在[Kerl96b]中，渐进性粒子仿真方案基于导入低差异采样。这个渐进性方案在略微优越的速率下平滑收敛，而且与随机算法相比没有变化。在双向路径追踪算法[LW93, VG94]中，尽管辐射度方程解的离散情况已经被避免，但其渲染时间远没有实时性。另外一个方面，图形学硬件能够实时通过扩展光源[HA 90, Hei 91, SKvW 92]照亮和遮蔽贴图场景。在我们新方法中，我们将光线确定性粒子仿真（即准随机游走原理）的优点与可用硬件功能结合，始终由辐射度方程进行渲染，既不使用核心也不使用积分方程解的中间解的投影，导致过程非常快速，健壮和直接。在介绍之后，论文的第二节中，我们简要的阐述全局光照问题的数学模型。第三节解释新的渲染过程及的准蒙特卡罗积分、准随机游走原理的基本技术。第四节，我们支持基本算法的一些扩展，包括基于抖动低差异采样的抗锯齿，镜面反射以及实时应用程序的改进，第五节讨论了该算法。最后一节得出结论，并指出未来研究的方向。2 全局光照我们的眼睛能感受到来自每单位角每单位面积功率的辐射。在真空中，辐射度$L$满足辐射方程[Kaj86]：$$L(y,\vec{w}_{r})=L_{e}(y,\vec{w}_{r})+\int_{\Omega}f_{r}(\vec{w}_{i},y, \vec{w}_{r})L(h(y,\vec{w}_{i}),-\vec{w}_{i})cos\theta_{i}dw_{i}\qquad$$其中$\Omega$是单位半球上垂直于$y$点表面的所有方向$\vec{w}=(\Omega,\phi)$的集合。$S$是作为边界表示而建模的场景表面。$h$函数返回当从$y$点出发向$\vec{\omega}_{i}$方向发射一条射线击中的第一个点。术语$cos\theta_{i}$表示将入射光线垂直投射到表面，$\theta_{i}$是$y$表面法线与入射光线$\vec{\omega}_{i}$之间的夹角。点$y$朝$\vec{w}_{r}$的辐射度$L$就是源辐射度$L_{e}$与反射辐射度之和。我们可以使用符号简写为：$$ L=L_{e}+T_{f_{r}}L $$双向反射分布函数$f_{r}$考虑了颜色和光泽度等表面特性。在一般设置中，这个函数取决于辐射的入射方向$\vec{w_{i}}$和反射方向$\vec{w_{r}}$以及基准点$y$。在辐射度设置中，$f_{r}=f_{d}(y):=\frac{\rho_{d}(y)}{\pi}$仅限于漫反射，然后辐射也会变得各向同性：$$L(y)=L_{\omega}(y)+\frac{\rho_{d}(y)}{\pi}\int_{\Omega}L(h(y,\vec{\omega}_{i})) cos\theta_{i}d\omega_{i}\qquad $$$\rho_{d}(y)$是漫反射贴图的反射性。给定一个四元组，全局光照问题由以下计算函数得到：$$<L,\Psi>:=\int_{S}\int_{\Omega}L(y,\vec{\omega})\Psi(y,\vec{\omega})cos\theta d\omega dy$$与辐射度设置相关，也与全辐射等式相关。检测器功能有多种选择，例如，在经典或分层辐射度方法[CW93]中使用的有限向量空间的正交基向量之和。我们不离散化积分方程的解，而是必须将其渲染到一个单独的通道中，我们直接选择下面这个方程来检测穿过焦点针孔摄像机看到的图像矩阵的像素点$P_{mn}$的平均辐射。 $$\Psi_{mn}(y,\vec{\omega}):=\frac{\delta(\vec{\omega}-\vec{\omega}_{y_{f}})}{cos\theta}\frac{1}{|P_{mn}|}\chi_{P_{mn}}(h(y,\vec{\omega}))$$ $y_{f}\cdot\vec{\omega}_{y_{f}}:=P-y_{f}$是在$P_{mn}$穿过$y_{f}$情况下点$P$的方向。$\chi_{P_{mn}}$是像素对应的特征函数，$\delta$则是克罗内克函数。
1 游戏CG技术的挑战写实的CG影像表现对于增强模拟现实世界的游戏环境中的沉浸感是必不可少的。特别是在高品质游戏制作中，改进图形表现使之成为成为大吸引力点的机会很多，如何做出让玩家第一眼看到就惊讶无比的影像已经成为了一个重要的技术课题。图1 Agni's Philosophy例如，SQUARE ENIX在2012年举办的E3这个世界上最大的游戏展上，公开的《Agni's Philosophy》实时CG技术演示。如图1的截图所示，实时计算影像已经接近电影质量，各公司和各研究机构正在进行各种研究和开发，以进一步提高性能。在游戏中开发CG技术的困难在于，它必须在每个游戏场景中实现健壮的计算，同时确保有限的计算资源之间的响应。与电影等影视产品不同的是，在游戏中，不仅仅是角色操作和相机操作，包括故事的速度和顺序之类的掌控权通常都留在玩家手中。出于这个原因，无论玩家视角如何，无论玩家进行了什么操作，都必须要能立即显示高品质的图像。此外，游戏制作所需的金钱和时间成本随着每一代硬件产品而呈指数级增长，尤其是处理60fps全高清视频的高品质游戏时， 为了避免在屏幕上出现锯齿，必须要生成高精度的多边形模型，纹理，动画等，这是造成开发周期延长和成本增加的原因之一。减少数据制作所需成本是各公司的共同课题， 给予依赖于设计经验的传统工作流程以技术支持，或是能够全自动生成一些数据的系统也已经被开发出来。本文介绍了几种应用于游戏的CG技术。首先，我们描述被称为实时全局光照（Global Illumination）的渲染技术。接下来，我将从物理模拟开始到统计分析方法的引入为止，总结CG动画技术的最新发展趋势。最后，我们介绍一种称为程序技术（Procedural Technologies），可动态生成游戏实时处理的数据的最新技术，并总结今后的展望。2 写实渲染的挑战2.1 图形硬件的应用在当前的游戏图像表示中，通过利用称为GPU（图形处理单元）专用于3D图形处理的并行计算单元已经开发了用于实时可编程地渲染CG场景的技术。在传统的CG系统 ，CG是利用硬件固有机能计算出来的，但是在GPU中，开发人员可以自由地编程控制绘图功能。尤其3D对象的质感表现依靠着GPU的登场得到了飞速发展。例如，为了再现人体皮肤的纹理，也在使用诸如在皮肤内模拟漫反射光的技术。2.2 基于即时辐射度技术（Instant Radiosity）的实时全局光照在此之前的技术中，确定对象颜色的时候，只处理从光源直接入射的光线。即不考虑来自其它物体的反射光和物体内部的透射光的影响。而用于模拟这些对象之间的光的相互反射和传播的技术被称为全局光照（GI）。为了实现精确的GI，需要模拟光传播的各种路径，其计算量通常很大。例如，以追踪方法和光子映射方法为代表的典型算法，为了得到物理上精确的结果，渲染一张静态画需要几秒到几个小时的计算时间。因此，GI限于应用于诸如电影等视频作品。然而，在近年来的高品质游戏中，GI和类似技术的引入变得不可或缺。出于这个原因，适合于游戏机的有限计算资源，特别是GPU计算体系结构的近似算法的正在持续不断的开发。图3 使用立即辐射度的实时全局照明在这种情况下，即时辐射度技术作为一种可以在游戏中得到实际应用的技术而受到关注。在即时辐射度技术中，如图2所示，在场景中放置一个接近物体表面反射间接光的颜色和强度的虚拟点光源，并且在渲染计算时，除了实际光源以外，还需要来自所有虚拟点光源的直接入射光进行对象的颜色计算。例如，通过在红色物体附近放置发射红光的虚拟点光源，近似模拟来自对象的反射光。一旦确定了虚拟点光源的亮度，颜色和排列，剩下的渲染过程就可以在一般的GPU计算管线上执行，因此它与现有的硬件兼容。而且，通过调整虚拟点光源的数量，可以容易地权衡计算速度和质量进行优化。图3显示了基于立即辐射度技术在GPU中实装的实时GI渲染结果，这表明即使使用现有的硬件配置，也可以获得足够高质量的影像。如上所述，即时辐射度技术具有优良的特性，因此预计可应用于次时代游戏。3 动画技术的发展伴随着纹理表现对GPU的使用和GI技术的发展，背景影像和场景纹理变得难以与现实区分。但是，如果角色像机器人或玩偶一样移动，整个影像的质量反而会使游戏的世界观崩塌。因此近年来，游戏场景的构成对象，特别是模仿人类模型角色的动画控制技术成了瞩目的焦点。3.1 使用数据交换和转换的经典技术在游戏中的传统动画技术中，通过在短时间切换数据进行回放，生成对应玩家操作的一系列动画。在许多高品质游戏中，会通过动作捕捉设备进行三维测量，以创建高度逼真的动画数据。然而，在简单地再现记录数据的技术中，可以在游戏中呈现的动画变化是有限的。在游戏中，多次重复显示相同的动作，重复播放相同的动画，会降低玩家的兴致。此外，影像要展示足够的说服力，显示与地形和环境相适应的动画是不可或缺的。简而言之，我们需要一种技术，它能高速生成与游戏进行时对应而且变化丰富的动画。3.2 物理仿真的应用物理仿真技术正在被广泛使用于具有表现力的动画计算技术中。例如，基于物理定律来模拟包括毛发和衣服等物件、水和烟等流体、物体破坏等行为在内的对象，可以在不预先准备动画数据的情况下再现真实对象的行为。除了提高视频质量外，物理仿真还有诸多与游戏设计直接相关的作品发布，展示了其广泛的适用性。另一方面，由设计师指导物理仿真往往是一项非常困难的任务，例如，当制作长发在风中卷起的动画时，需要考虑如何指导诸如控制头发剪影形状等细节来反映角色的感觉和场景的意图。虽然为了在物理仿真中获得所需的结果，不可能改变头发的运动方程，但是许多参数，例如头发的材料和风的强度等，必须以反复试验的方式进行调整。而且，利用当前的技术，几乎不可能模拟角色的活跃行为。例如，角色丧失心智倒下的样子确实可以根据诸如重力的物理定律来计算得到，但即使在最单纯的行走运动中，也无法建立能够完全描述主动人体运动的数学模型。此外，如果将性别，个性，情感等不确定因素包含进去，则人体运动仿真将会是一个完全未知的领域。针对这些问题，引入人体运动的测量数据以便提高物理仿真质量，以及通过先进的优化，使设计师得以进行仿真设计的技术都在研究中。这其中许多仍处于学术研究的阶段，但如果实现更强大和更有效的算法，它将可以很好地应用于游戏中。3.3 应用统计处理的动画合成随着动作捕捉技术的普及，可以轻松测量大量的三维人体运动数据。通过对大量运动数据进行统计分析，实时生成自然的动画的技术得到了广泛的发展。例如，应用贝叶斯统计量在保持动画的统计性质的同时进行数据压缩，高速搜索相似动作自动生成满足任意约束条件数据等等，这些方法已经得到了广泛的应用。特别地，作为近年来游戏产品中实用化程度不断提高的技术，运用散射数据插值方法的动画生成技术不断得到发展。在该技术中，通过使用表示运动特性的少量控制参数，达到计算多个动画数据加权插值的目的。例如，对以不同的速度和行进方向行走动画进行插值时，不必直接操纵加权百分比，而是在满足指定速度和指定方向的前提下进行最优化统计，来间接控制动画。图4 使用散射数据插值生成非平坦地形行走动画在图4的示例中，使用在不同高度的台阶上的行走动画简单数据，基于在角色的行进路线上检测到的地形来应用散射数据插值，可以做到实时计算任意非平坦地形上的行走动画。4 对程序技术的期望为了减少用人工制作数据的成本，统称为程序技术的技术群被给予了很高的期待。它指的是基于一些程序计算算法，动态计算游戏场景构成数据的一般方法。例如，被称为程序噪音的技术，是通过操作二维傅立叶级数参数，生成各种类噪声纹理图像。此外，傅立叶级数在合成周期性物体动画合成和效果音合成等领域得到了广泛利用。另外，植物的枝条分叉形态已知可以通过被称为L-系统的简单语法规则来记述，该技术已被应用于动态生成森林和草原场景。这样，经典的程序技术方法，通过调整相对简单的数学模型参数，获可以得生成无穷变化对象的方法。近年来，已经开发了一种从对象数据上获取特有背景知识和少许简单数据，就能够在保持计算自由度的同时进行更高质量数据合成的方法。举一个形状建模的例子，最新的GPU都配备了被称为镶嵌单元的功能，他可以程序化地操控多边形的位置和数量，而这些多边形构成了3D对象。通过使用镶嵌单元，设计者不需要事先制作所有对象的形状数据，根据给定的算法动态计算，通过操作少许参数，就可以生成出丰富的变化。如图5所示怪兽角色，设计者在制作过程中事先合成少许几乎没有波动的、低分辨率的模型，在游戏实时运行时增删多边形数量的同时，通过程序将详细的凹凸形状添加到物体表面。此外，仅在角色放缩的时候对多边形进行细致分割等，可以实时优化计算量与质量之间的权衡。目前的技术，很多的详细的形状信息仍然由高级设计师手动设定，但我们认为它会向前发展，变成可以基于任何数学模型和规则的自动生成机制。5 技术元素和游戏引擎的进步如以上所述，游戏CG的技术要素组成是非常复杂的，每个技术都需要相关的深度专业知识。事实上，在海外的游戏制作现场，活跃着很多获得计算机科学博士学位的计算机人才，技术的精锐化变得越来越受欢迎。在另一方面，一般的制作者学习技术变得越来越困难，即便对于与游戏的基本乐趣无关的部分也是如此，被迫付出巨大成本的情况时有发生。基于这些情况，人们开发出了许多称为游戏中间件和游戏引擎的制作平台。游戏引擎是一个集成开发环境，可以轻松处理复杂的游戏技术，通过充分利用它们，制作人可以专注于游戏设计和故事等内容制作。6 将来的展望直到目前为，大多数游戏CG技术都被几年前的离线技术所主导，它们通过硬件的进化和高速化近似手法实现实时计算。因此，通过观看当前的CG视频作品，将能够在一定程度上预测未来游戏CG的姿态。另一方面，游戏是一个直到最后都由玩家操作进行干预的交互式应用程序，即使在游戏CG中，玩家的操作体验也是很重要的。例如，考虑角色全身浸在水中，衣服被浸湿而变得难以移动的游戏设计。这个时候，如果能适当的表现出湿润的头发和衣服的质感，那么游戏设计将给与人很强的说服力。换句话说，游戏CG是支持游戏设计的一个要素，也被认为是今后制作者扩展自由度，进一步激发新的游戏设计的发展方向。其中，特别是以程序技术为代表的实时数据生成技术和物理仿真技术，可以成为游戏空间和玩家达到高度交互的基础，有待今后的进一步研究和开发。
[译]QSplat:大型网格的多分辨率点渲染系统
3D扫描技术的进步使数亿多边形网格的实际创建得以实现。用于显示、简化渐进式网格传输的传统算法对于这种尺寸的数据集而言是不切实际的。我们定义了一个用于表示和逐步显示这些网格的系统，这些网格将基于边界球体的多分辨率层次结构与基于点的渲染系统结合在一起。专门使用一个数据结构用于视锥截取，背面剔除，细节层次选择和渲染。这种表示方法非常紧凑，可以快速计算，适用于大型数据集。我们是为了用于大型3D数字化项目而编写的，它可以快速启动，保持用户可设置的交互式帧速率，而不管对象的复杂程度或相机位置如何，在运动过程中产生合理的图像质量，并在空闲时逐渐细化为高的最终图像质量。我们已经在包含数亿样本的扫描模型上演示了该系统。分类和学科描述：I.3.3 [计算机图形]：图片/图像生成 - 显示算法;I.3.5 [计算机图形]：计算几何和对象建模 - 曲线，曲面，实体和对象表示;I.3.6 [计算机图形]：方法和技术 - 图形数据结构和数据类型。关键词：渲染系统，空间数据结构，细节层次算法，压缩算法1 简介计算机图形学最近的一个重大趋势是在渲染过程中向着使用实时对象采样表现方式转变。这种趋势的一个例子是越来越多地使用三维扫描系统，它可以生成物理对象三维采样模型。然而，3D扫描仪的一个问题是如何处理他们生产的大量数据。在过去几年中，3D扫描系统的硬件和软件组件的改进已经将实际可获得的扫描网格大小增加到数亿个样本。当前工作站不能实时显示这种尺寸的网格，传统网格简化和逐步显示算法的运行时间和空间需求使得这些方法对于包含超过几百万个样本的扫描网格来说不切实际。而且，许多这样的技术着重于优化单个边和顶点的布局，每个顶点将会消耗大量精力。然而，扫描的数据通常具有大量的顶点，并且由于噪声的原因，它们的位置往往不够精确。这揭示存在一种替代方法，这种方法将个别点视为相对不重要，这样对原始网格而言实际上降低了消耗。最近采用这种范式的研究包括Krishnamurthy和Levoy的样条拟合系统[Krishnamurthy 96]，Curless和Levoy[的距离图像合并系统Curless 96]，以及基于八叉树粒子的Yemez和Schmitt渲染系统[Yemez 99]。这些算法不会精确处理范围数据，实际上也不会保留原始网格的任何样本的3D位置。遵循这种低基本成本算法的趋势，我们开发了一种用于大型网格交互式显示的新算法。这个被称为QSplat的算法是在一个大型3D数字化项目[Levoy 00]的过程中设计的。由于它使用基于遍历边界球体层次结构的简单渲染算法，因此适合浏览此项目中生成的模型，该模型包含1亿至10亿个样本。此外，QSplat不保持输入网格的连通性（在扫描固有数据时仅能用于解决深度不连续性而没有其他意义），而是依赖于基于点的表示和图示渲染(splat rendering)。因此，我们的系统比类似的基于多边形的系统具有更低的预处理和渲染成本。在本文中，我们将介绍QSplat数据结构和渲染算法，并讨论一些权衡和设计决策，以使其适用于大型网格。我们描述系统的渲染性能，并讨论它的预处理成本。最后，我们考虑它与以前用于显示大型网格的算法的关系，并描述用于渲染其他类型大型几何数据集的一些未来扩展。2 QSplat数据结构和算法QSplat使用层次结构的边界球体[Rubin 80，Arvo 89]进行可见性剔除，细节层次控制和渲染。树的每个节点都包含球体中心和半径，法线，普通锥体的宽度[Shirman 93]以及可选的颜色。可以从多边形，体素或点云中生成这样的边界球体层次结构，但对于我们的应用程序，我们只需要一种用于从三角形网格生成层次结构的算法。层次结构被进行预处理，然后写入磁盘。2.1 渲染算法一旦构建了层次结构，将使用以下算法进行显示：TraverseHierarchy(node) { if (node not visible) skip this branch of the tree else if (node is a leaf node) draw a splat else if (benefit of recursing further is too low) draw a splat else for each child in children(node) TraverseHierarchy(child) }我们现在详细研究这个基本算法的几个阶段。可见性剔除: 当我们递归边界球体层次时，我们剔除不可见的节点。通过测试每个球体相对视锥体的位面来进行视锥剔除。如果球体位于外部，则它和其子树将被丢弃并且不会被进一步处理。如果球体完全位于平截头体的内部，不会尝试对该节点的子节点进行进一步的视锥体剔除。我们还将在渲染过程中使用存储在每个节点的法线和法线锥来进行执行背面剔除。如果锥面完全离开观察者，则丢弃该节点及其子树。我们还将检测锥体完全指向观察者的情况，并将其子树标记为不适合进行背面剔除。确定何时进行递归: QSplat使用启发式算法，递归次数取决于屏幕上的投影大小。也就是说，如果投影到观察面上的球体的面积超过阈值，则对节点进行细分。递归的中值可以调整帧与帧之间的间隔来保持用户选择的帧速率。我们目前使用一个简单的反馈方案，通过前一帧中从实际到预期的渲染时间的比率来调整阈值区域。Funkhouser和Séquin已经展示了一种预测性的LOD控制算法[Funkhouser 93]，可以缩短渲染时间的帧间变化。但是，我们没有实现这一点。我们还没有导入任何平滑过渡算法用于做过模型细节层次改变，例如Hoppe渐进网格系统[Hoppe 98]中的地形。鉴于我们为应用程序中经典快速变化和提炼选择了最适度变化方案，我们尚未发现光滑视觉效果的缺失;但是，其他应用程序或许会从平滑过渡中受益。尽管屏幕空间区域是LOD控制最流行的指标，其他启发式算法[Duchaineau 97，Hoppe 97]已经用于确定递归的深度。在我们系统的框架内，可以在高曲率区域（使用标准锥体宽度）或在屏幕的中央“中心凹”区域中结合围绕边（使用每个节点的法线）进一步制定递归的规则（只使用投影位置）。上述帧率控制的实现将会在模型的交互操作期间使用。一旦用户停止移动鼠标，我们相继用较小的阈值重绘场景，直到达到一个像素的大小为止。 图1显示了QSplat在几个细化层次上呈现的示例场景。绘制Splats: 一旦我们已经到达叶节点或者决定停止递归，我们绘制一个代表当前球体的图示[Westover 89]。图示的大小基于当前球体的投影直径，其颜色是根据基于当前每球法线和颜色的光照计算获得的。使用启用Z缓冲来绘制Splats以解决遮挡问题。我们在3.3节讨论每个图示的形状。2.2 预处理算法我们的预处理算法从待编码模型的三角形网格的表现开始。尽管可以直接从点云建立QSplat层次结构，但从网格开始，可以轻松计算每个节点的法线。如果我们没有网格，我们将不得不通过将平面拟合到每个点周围小邻域中的顶点来计算法线。从网格开始，还可以将球体大小分配给输入顶点（它们成为我们的边界球体层次结构中的叶节点），以便在渲染过程中不留下任何空洞。为了保证这一点，必须选择尺寸，使得如果两个顶点通过原始网格的边连接，那么放置在这些顶点处的球体的大小足以相交。我们当前的算法使得球体的大小等于接触该顶点的所有三角形的边界球体的最大尺寸。这是一种保守的方法 - 它可能会导致球体太大，但保证不留下任何空隙。一旦我们分配了叶球大小，我们使用以下算法来构建树的其余部分：BuildTree(vertices[begin..end]) { if (begin == end) return Sphere(vertices[begin]) else midpoint = PartitionAlongLongestAxis(vertices[begin..end]) leftsubtree = BuildTree(vertices[begin..midpoint]) rightsubtree = BuildTree(vertices[midpoint+1..end]) return BoundingSphere(leftsubtree, rightsubtree) }该算法沿着其边界框的最长轴分割顶点集合，递归计算两个子树并找到两个子球体的边界球来构建树。随着树的建立，内部节点上的每个顶点属性（例如法线和颜色）被预设为子树中这些属性的平均值。当递归到达单个顶点时，我们只需创建一个球体，其中心是顶点的位置。由于树的总大小取决于每个节点的分支因子，因此我们组合树中的节点将平均分支因子增加到大约4。这减少了内部节点的数量，从而减少了树的存储需求。如3.1节所述，预处理的最后一步是量化每个节点的所有属性。3 设计决策和权衡现在让我们考虑一下在进行QSplat时做出的一些决定，这些决定将使算法适用于大型扫描数据集的可视化应用。我们将描述如何权衡量化文件布局，图示形状以及那些受到快速渲染和紧凑表现额外影响的选择。3.1 节点布局和量化图2c中显示了边界层次结构中每个节点的布局。节点包含球体相对于其父体的位置和大小，法线，法线锥体的宽度，可选颜色以及用于表示树结构的几个比特位。我们在3.2节讨论树的结构和文件内节点的布局。位置和半径:每个球体在边界球体层级中的位置和半径以其父节点为参考系进行编码（使用相对值）。为了节省空间，这些量被量化为13个值。也就是说，一个球体的半径可以在其父部的半径的1/13至13/13范围内，并且球体的中心相对于其父体的中心的偏移量（在X，Y和Z）是父球面的直径的1/ 13的倍数。量化从上到下进行，子球体的位置和大小相对于其父体的量化位置进行编码; 因此，量化误差不会沿着网格传播。为了保证量化过程不会引入任何空洞，量化半径总是四舍五入到最接近的可表示值，以确保量化球体完全包围真实球体。请注意，并非所有的$13^{4}$的可能的组合(x, y, z)中心偏移和半径比都是有效的，因为许多结果的子球体并不被父球体包住。实际上，只有7621个可能的组合是有效的，这意味着我们可以仅使用13位（使用查找表）对量化的位置和半径进行编码。对于半径为1的父球体，这种编码方案组成的子球体中,（x，y和z）会有0.04平均量化误差，半径会有0.15的平均误差。半径误差之所以大于位置误差，是因为半径首先根据球体位置的量化误差来增加（以确保量化球体包围真实球体），而且总是向上取表示值。当然我们可以通过不要求量化的球体完全包围原始图像来获得较低的半径量化误差。但是，这样做会导致量化后球体不再相交的可能性。这可能会在我们的渲染中产生空洞。通过增量编码来表示诸如球体位置等几何量的想法，实质上扩展了层次结构中各个层次之间的数量位，这意味着与传统的网格压缩方法不同，它依赖于沿网格边缘的某些路径编码时的顶点位置[Taubin 98]。实际上，这种“分层三角形编码”更接近用于Eck等人的多分辨率分析[Eck 95]中的几何形状的小波表示。我们每个节点13比特位的空间需求比state-of-the-art传统压缩方法更有竞争力。依靠顶点位置的初始量化优势，它们平均每个节点有9-15比特。然而，这并不是一个完全有效的比较，因为传统的几何压缩方法也表示网格连通性（我们不需要表示），并且我们每个节点的13位还包含球体半径。渲染过程中，每个节点的位置和半径都可以实时解码。因此，我们的数据结构不仅在磁盘上紧凑，而且在渲染过程中需要的内存少于在渲染前必须解压缩数据的方法。法线: 每个节点的法线量化存储为14位。可表示法线在立方体6个面的每个面上，各对应5252网格上的点，这样可以更均匀的弯曲向样品空间。在渲染过程中使用查找表来解码可表示法线。在实践中只使用5252*6 =16224种不同的法线（导致大约0.01弧度的平均量化误差）在漫反射组成中不产生可见的伪影，但是在低曲率的宽广区域内的镜面反射周围可见一些带状伪影。通过移动到每一条相对于父球体进行增量编码的法线上，可以消除这些伪影，并且实现更好的压缩。当然，这会增加算法内部循环的计算复杂度，这是一种时间-空间的权衡。与节点位置范围不同，法线空间是有界的，因此固定的量化表就足以编码任意场景的正则表达式。因此，此时我们选择了对法线使用固定量化，这只需要在运行时查找单个表。随着处理器速度的增加，我们预计增量量化方案将变得更具吸引力。颜色: 当前存储的颜色量化为5-6-5共16位。正常情况下，颜色使用增量编码会节省空间，但在运行时会更加昂贵。法线锥体: 经过一些实验后，我们决定将每个节点的法向锥体的宽度量化为2比特位。四个表示的值对应于锥体，其半角具有正弦1/16，4/16，9/16，和16/16。在典型的数据集上，使用这种量化的正常圆锥体进行背面剔除时丢弃的节点中，超过90％是使用精确的正常圆锥体宽度也会被剔除的节点。请注意，我们在表示法线锥体宽度时总是保守的，所以我们从未丢弃应该显示的几何体。与法线和颜色一样，标准锥体宽度可以相对于父节点处的宽度来表示，但这会降低渲染速度。3.2 文件布局和指针边界球体层次的节点以宽度优先的顺序排列（内存和磁盘）。这样做的主要结果是文件的第一部分包含低分辨率的整个网格。因此，我们只需要读取文件的第一部分便足以使用低分辨率来可视化模型; 随着从磁盘读取文件的更多信息，我们将能看到更多细节。我们目前使用操作系统提供的内存映射作为工作集管理的基础，因此当用户查看时，模型的给定部分的高分辨率数据将从磁盘读取。这种渐进式加载对于大型模型的可用性而言有非常重要的意义，因为从磁盘加载整个数据集的时间可能需要几分钟。不过由于数据是根据需要加载的，当用户首次放大模型的某个区域时，渲染性能会降低 – 帧速率控制方法基于反馈导致帧速率出现问题。然而，接触模型相同区域的后续帧会全速渲染。[Funkhouser 92，Funkhouser 96，Aliaga 99]提出了一种推测预取方法来减少这种变动，但是我们目前没有实现这一点。已经提出了几种无指针方案用于树编码，包括线性八叉树和基于完全树的方法[Samet 90]。但是，这些数据结构对我们的应用来说不合适。线性八叉树和相关想法需要遍历整个树来恢复其结构，这在我们的系统中是不切实际的。基于完整树的数据结构可以用于部分遍历，但是因为我们用来生成树的算法是基于轴对齐的二等分，所以我们不能保证结果树会完整和平衡。此外，修改预处理算法生成完整的树并不是必需的，因为在每个子树中放入相同数量的顶点可能会使分裂平面偏离中心。尽管我们不能为我们的树使用无指针编码，但我们至少应该尽量减少所需指针的数量。考虑到我们按照广度优先顺序存储树，树中的每个兄弟组（即，单个父球体的子节点）都有一个指针指向这些节点的子节点就足够了。而且，如果这些球体都没有子节点（即它们都是叶节点），那么该指针就不是必需的。使用这种方案，大约总存储成本的8％到10％用于指针，我们认为这些指针足够小，以至于我们没有寻求更复杂的方法来进一步降低指针成本。为了能够遍历树，我们在每个节点上存储两位编码节点的子节点数的位（0,2,3或4个子节点 - 不允许有单个子节点），同时使用一个比特位来指示该节点的左右子节点是否是叶节点。现在可以将树的总存储需求计算为树中的节点数乘以每个节点的成本，再加上由于指针引起的开销。对于平均分支因子为3.5的树，节点总数将是叶节点数量的1.4倍，从而使整个树的净存储需求大约为9字节*叶节点数，如果不存储颜色则为6字节。3.3 图示形状用于表示渲染点样本的内核选择可能会对最终图像的质量产生重大影响。最简单，最快的选项是非抗锯齿OpenGL点，它被视为一个正方形。第二种选择是一个不透明的圆，它可以作为一组小三角形呈现，或者作为在大多数OpenGL实现中成本较低，作为单个纹理映射的多边形。另一种选择模糊点，拥有以高斯或某种近似值进行径向衰弱的透明通道。我们使用的特定近似值是在图示的标准半径中不透明度下降到1/2的样条函数。后两个选项绘制速度较慢，因为它们需要向图形管道发送更多数据。此外，由于混合和Z缓冲之间的相互作用，绘制高斯图示需要特别注意绘制图示的顺序。Levoy和Whited在纯软件的渲染器[Levoy 85]中讨论了这个问题；他们提出了一种基于桶的方法，以确保遮挡和混合均正确发生。在OpenGL中，我们可以使用多通道渲染来实现正确的行为。在第一通道中，通过$z_{0}值$来描述与观察者相距的偏离深度，我们只渲染深度缓冲区。对于第二通道，我们关闭深度偏移并将其叠加渲染到颜色缓冲区中，并且不进行深度更新。这将具有在表面深度范围$z_{0}内将所有图示混合在一起的效果，同时保持正确的遮挡。图3比较了图示内核的这三种选择。由于每个内核的每个图示绘图时间对于每个内核都不相同，因此我们在不同的图示大小和不变的运行时间下进行比较。关于图示形状另外一个需要决定的选项，图示总为圆形（或OpenGL点的平方）或是总为椭圆形。在后一种情况下，每个节点处的法线用于确定椭圆的偏心率和方向。当法线指向观察者时，图示将是圆形的。否则，每个椭圆的短轴将沿着法线的投影指向观察平面，并且短轴与长轴的比率将等于n v，其中n是图示法线，v是指向观察者的向量。与圆形图示相比，这提高了轮廓边缘的质量，减少了噪音和增厚。我们在图4中比较了圆形和椭圆形图示的使用。因为我们构造了我们的边界球体层次结构，使得沿着连续表面放置的球体永远不会留下空洞，所以我们可以保证正方形和圆形内核总是会可以无空洞再构造。我们对高斯内核的近似也保证在起始于连续曲面的区域产生完全不透明度。当我们移动到椭圆内核时，我们不能再保证无空洞的再构造，因为法线不需要沿着表面连续。实际上，当使用椭圆形内核时，我们偶尔会看到空洞，特别是在轮廓边缘附近。我们发现，限制椭圆的最大缩短率（例如，将主轴与次轴的最大比率限制为10）实际上填充了所有这些空洞。3.4 基于点的系统的结果点渲染对于具有统一尺寸几何细节的物体，以及在不需要以比样本间距更高的分辨率观察模型的应用中，对于具有均匀尺寸几何细节的物体最为有效。如果模型具有大的，平坦的或巧妙的曲面，那么多边形模型可以更紧凑和更快地绘制。同样，如果需要放大以使样本间距比像素大小更大，多边形可提供更高的视觉质量，特别是在尖锐的边缘和角落附近。图5显示了基于点和多边形的渲染之间的比较。QSplat的开发旨在将扫描模型可视化，其中包含大量精细细节，并且接近扫描分辨率。我们使用体积范围图像处理（VRIP）系统[Curless 96]将原始扫描合并到我们的最终模型中，并使用行进立方体算法[Cline 88]提取多边形网格。由于后者生成的样本具有均匀的空间，所以点渲染非常适合我们的应用领域。对于具有较大平滑区域的场景，我们预计相对于基于多边形的系统，QSplat效果会较差。但是，如果大型多边形被切块，那么所得模型的视觉质量仍然很好，就像在REYES架构中一样[Cook 87]。对于包含高频细节和大平坦区域的应用，混合点/多边形方案可能是合适的选择。4 性能如第3节所述，交互性的目标决定了我们系统的许多设计决策。除此之外，我们还通过多种方式优化了实施，以增加可视化模型的大小。4.1 渲染性能我们系统中的大部分渲染时间都花费在遍历层次结构的内部循环中，计算每个节点的位置和半径，执行可见性剔除，并决定是绘制点还是进一步递归。这个内部循环被调整来消除昂贵的操作，特别是在树的较低级别时。例如，我们不在树的低层执行精确的透视分割，当节点的屏幕空间大小达到几个像素时切换到近似值。因此，一旦从磁盘读取数据，平均而言，我们的算法可以在SGI Onyx2上每秒渲染1.5至2.5百万点。确切的速率取决于缓存效果（例如，我们发现当工作在L2高速缓存环境下，速度会有提升）以及树中哪些级别的数据被剔除。我们的显示速率可以与Hoppe报道的每秒48万个多边形（在相同的硬件上）进行比较，因为他为ROAM系统实现了渐进网格[Hoppe 98]或每秒18万个多边形[Duchaineau 97]。对于我们的应用，我们通常使用5-10赫兹的帧速率，这意味着我们在交互式渲染过程中每帧画出200到30万点。请注意，与上述两个系统不同，QSplat没有明确使用帧到帧的一致性，例如缓存可能可见的初始化列表。图6总结了QSplat的渲染性能。我们算法的简单性使其非常适合在低端机器上实施。作为一个极端的例子，我们在没有3D图形硬件（366 MHz Intel Pentium II处理器，128 MB内存）的笔记本电脑上实现了QSplat。由于渲染是用软件来执行的，系统是有限制的。对于500x500的典型窗口大小和5 Hz的帧速率，实现可以每秒钟运行250到400千点，每秒填充速率为4000万像素，并且通常每帧可以绘制50到70个splats 。在这个情况下，这个实现仍然很好用。尽管目前大多数桌面系统都具有3D图形硬件，但对于便携式和手持式系统以及数字电视机顶盒等应用来说，情况并非如此。4.2 预处理性能虽然预处理时间并不像渲染时间那么重要，但对于非常大的网格的实际可视化仍然很重要。Hoppe报告10个小时作为20万个顶点渐进网格的预处理时间[Hoppe 97]。Luebke和Erikson报告121秒作为实施分层动态简化的281,000个版本的预处理时间[Luebke 97]。相比之下，我们对20万顶点的预处理时间在5秒以内（在同一硬件上）。图6给出了本文数字中所用模型的预处理时间和空间需求的一些统计数据。我们可以比较预处理时间的另一类算法是用于网格简化和抽取的算法。 尽管这些算法与QSplat的目标不同，但它们通常也用于生成多分辨率表示或简化网格以进行显示。 Lindstrom和Turk发表了几个最近的网格简化方法的比较[Lindstrom 98]。 他们报告30秒到45分钟之间的时间，以简化35000个顶点的兔子网格。 文件没有考虑的一种方法是基于体素的简化Rossignac和Borrel [Rossignac 93]，它在与Lindstrom和Turk使用的硬件相同的硬件上花费了一秒钟时间。 我们对这个网格的预处理时间是0.6秒。 因此，我们的算法比大多数当前网格抽取算法快得多，并且与Rossignac和Borrel方法相比具有竞争性。5 前期工作以前用于表示和显示大型模型的方法可以分为点渲染，可见性剔除，细节层级控制和几何压缩。5.1 点渲染传统上计算机图形系统使用三角形作为渲染原语。为了减少包含大量几何图形场景的三角形的设置和光栅化成本，已经提出了许多更简单的基元。使用点作为连续曲面的显示基元由Levoy和Whitted [Levoy 85]引入，最近又由Grossman和Dally [Grossman 98]重新研究。点渲染已被纳入到商业产品中 - 例如，Animatek鱼子酱系统在视频游戏[Animatek]中将点渲染用于动画角色。粒子也被用于更特殊的环境中，如渲染火焰，烟雾和树木[Csuri 79，Reeves 83，Max 95]。数据结构来实现空间空间区域的压缩，Laur和Hanrahan已经研究了使用八分音符表示的音量的等级划分[Laur 91]。 尽管splatting最适合在投影体素大小在像素大小的情况下使用，但也已经检验过在其他体系中的有效性。 Cline等人提出的微分立方体算法适用于体素大于像素的情况。对于小于像素的体素，Swan等人[Cline 88]已经提出了正确生成反锯齿结果的算法[Swan 97]。5.2 可见性剔除大量计算机图形系统中出现了诸如QSplat所使用的视锥和背面剔除算法。基于数据结构（如oc树）的层次平截体剔除一直是大多数渲染大型场景系统的标准功能[Samet 90]。基元的背面剔除通常在硬件中实现，Kumar和Manocha提出了基于法线圆锥的分层背面剔除算法[Kumar 96]。另一类可见性剔除算法包括用于遮挡剔除的方法。Greene等人描述一种通用算法，用于丢弃被更紧密的几何体使用分层Z缓冲区阻塞的基元[Greene 93]。如果场景高度结构化，也可以使用其他更专用的遮挡算法。例如，建筑飞行系统通常使用单元和门户的概念来剔除整个不可见的房间[Teller 91]。 QSplat目前不执行任何种类的遮挡剔除，它将为查看我们正在考虑的扫描模型提供最小的益处。 然而，遮挡剔除对于更复杂深度的场景是一个有用的补充。5.3 细节控制的级别在低倍率下渲染大型数据集通常会导致原始像素小于输出设备像素。为了尽量减少这些情况下的渲染时间，最好切换到更低分辨率的数据集，并使用更接近输出显示分辨率的基元。在LOD算法中，可以将那些以离散细节层次存储整个对象的算法与执行更细粒度LOD控制的方法区分开来。后一类中的算法可以连续控制图元的数量，最大限度地减少“弹出”伪影，并且通常会改变整个场景中的细节水平，以补偿透视投影的变化放大率。多分辨率分析将一个对象表示为“基本网格”，并将一系列校正值存储为小波系数[Eck 95]。Certain等人已经实现了基于多分辨率网格的实时查看器，该网格可以选择任意数量的要使用的小波系数，因此可以绘制任意数量的多边形网格[Certain 96]。他们的观察对象还包括诸如逐行传输和几何和颜色的小波系数分离集等功能。渐进网格使用基础网格和一系列顶点拆分操作[Hoppe 96]。渐进网格已被纳入实时查看器中，该查看器对数百万个多边形场景的实时飞行进行视点相关改进[Hoppe 97，Hoppe 98]。观察者不仅可以选择任意数量的多边形进行绘制，还可以将对象的不同部分细化为不同的分辨率。其他最近允许在整个场景中改变水平的系统包括ROAM 地形渲染系统[Duchaineau 97]和LDI树[Chang 99]。QSplat中LOD控制的实现与这些系统具有相同的目标，允许根据投影的屏幕尺寸在整个场景中细节级别平滑地变化。5.4 几何压缩几何压缩的目标是减少大网格的存储和内存要求以及传输成本。Deering提出了一个压缩网格连通性，顶点位置，颜色和法线的系统，后来在硬件中实现[Deering 95]。最近的研究，如Taubin和Rossignac 的拓扑外科方案，已经集中在降低表示网格连通性和改善顶点位置压缩的成本[Taubin 98]。Pajarola和Rossignac对渐进网格进行了压缩，产生了一种将细节层次控制和渐进式细化与紧凑表示相结合的方案[Pajarola 99]。然而，他们的算法比QSplat具有更高的预处理和解码成本。6 结论和未来工作QSplat系统演示了大型模型的实时渐进渲染。QSplat的体系结构与最先进的逐行显示算法的渲染速度相匹配，预处理时间可与当前最快的网格化抽取器相媲美，实现了接近当前几何压缩技术的压缩比。由于QSplat查看器非常轻便，可以在低成本硬件上实现，因此我们认为它有可能允许在以前不实用的应用程序中使用3D渲染，例如在博物馆中内置自助服务终端。1999年5月6日，我们在佛罗伦萨Medici教堂的一台计算机上安装了QSplat，显示我们部分完成的Dawn雕像计算机模型，并让游客玩耍（见图7）。先前介绍的几种技术可以纳入当前的QSplat框架中，以使其更加节省时间和空间：霍夫曼编码[Huffman 52]或其他无损压缩方案可用于使当前表示更加紧凑。这对于通过低带宽通信链路进行离线存储或传输非常有用，但是需要在渲染之前对模型进行解压缩。对于渲染速度比紧密表示更重要的情况，可以通过消除球体位置和大小的压缩和增量编码（如3.1节所述）来加速算法，并将这些数量简单地存储为彩车。此外，正常的口罩和能见度掩模（如Grossman和Dally使用的口罩和能见度掩模）可以在有大量大面积封闭的情况下加速渲染[Zhang 97，Grossman 98]。速度的进一步提高可以通过并行渲染算法来实现，将树的一部分分配给不同的处理器。虽然我们在本文中报告了单处理器的结果，但我们已经可以通过将网格分解为多个tile来并行化我们的预处理算法。进一步的分析对于理解QSplat的时间一致性和缓存行为是必要的。对地形渲染和建筑漫游系统[Funkhouser 96]中的帧速率控制和工作集管理技术进行了大量的系统研究，这些算法将提高用户与QSplat交互的平滑度。以下是帕特COM的图形中结合了不同种类的算法QSplat方法未来研究的潜在领域：QSplat使用的边界球体层次结构非常适合作为光线追踪的加速度数据结构。潜在地，这可以用于高质量渲染，并具有以QSplat格式存储的模型的高级渲染效果。实例化将很容易融入我们的基于树的数据结构和渲染算法，大大减少了许多程序化定义场景的内存需求。这可以被认为是一种依赖视图的精灵的新形式，允许在场景中的多个位置有效地包含几何图形。除法线和颜色以外的项目可以存储在每个节点。透明度（alpha），BRDF和BTDF将是明显的候选对象，这会增加QSplat可以表现的视觉复杂度，使其具有与现代体积渲染器相似的功能[Kajiya 89]。更复杂的对象，如光场，依赖视图的纹理，空间变化的BRDF以及分层深度图像也可能存储在每个节点上，从而创建点渲染系统和当代基于图像的渲染器的混合。
[译]数据驱动下的游戏角色细腻头发动画
我们提出了一种数据驱动的方法，以在诸如游戏等交互式应用程序中实现高质量的细腻头发动画。通过设计评估头发动态相似性的误差度量方法，我们尽可能考虑头发特征。我们还提出了一种基于二次动作图（SMG）的新型数据库构造算法。我们的算法可以提高这些图形的效率，减少冗余数据，并且在考虑将来动作的同时实现两个可视化剪辑的视觉平滑连接。使用我们的SMG的运行过程的成本相对较低，允许实时交互操作。关键字：数据驱动，交互式应用，头发动画，游戏角色，次级动作图1 介绍数十年前，在视频游戏等交互式应用程序中，角色的头发通常被表示为具有α映射的三维曲面（例如NURBS），这看起来非常不自然。 头发之间摩擦，碰撞和静电力非常复杂，头发的粗糙表面或小而不规则的半径[1]特征使得真实的头发模拟成为一项非常艰巨的任务。 而且，游戏中有限的资源使得当时的头发动画几乎无法表现出来。提出了许多方法来解决这个问题，如圆柱体或带状结构[2]。这些方法可以加快线头发模拟的计算时间并获得更好的结果。 然而，由此产生的动作仍然过于粗糙并且不令人满意。 为了达到视觉上令人满意的效果，独立模拟每条链的方法[3，4]是目前的主要趋势。 这些方法的成本非常高，因此实时交互式应用程序非常耗时。在本文中，我们提出了一种数据驱动的方法来在交互式应用程序（如游戏）中近似详细的头发动画（如图1所示）。 仅考虑游戏人物的特定特征，只需要操作有限的动作（走路，左转，右转，跳跃等），我们可以说实际出现的动画是可以预测的。 使用数据驱动和子空间技术[5,6,7]，提前构建一个包含头发动画片段的数据库，以非常低的成本使用这种预先计算的数据库加速运行时过程。这种方法的一些具体问题包括：如果细节被寻找，数据库的大小往往会很大，并且惯性力等连续动作的影响不能被忽略，以避免视觉上的不兼容。为了解决这些问题，我们提出了一种基于次级活动图的新型数据库构建算法。我们的算法可以提高这些图形的效率以减少冗余数据，并且在考虑到它们的未来动作的同时实现两个动画片段的视觉平滑连接。2 相关工作目前，尽管电子游戏图形的质量很高，但为了解决头发模拟的高成本问题，提出了各种方法。最常用的方法是将几根线作为引导线，并对其余部分进行插值，如[8]所示。柴等。提出了一种简化的头发模型方法[9]，通过从训练数据中选择有效的引导头发和插值权重来加速运行时间模拟。但是，由此产生的速度在引导头发的数量和模拟方法上是不同的。此外，模拟的运行时成本对于游戏等应用来说仍然过高。我们的方法与Chai等人的方法不同，我们主要关注于降低计算成本并且在运行时过程中不依赖模拟器。Han等人提出的其他方法，如GPU上的并行计算。 [10]加快模拟时间。然而，并行计算方法和插值方法都不能很好地处理头发碰撞，这在动画头发的外观中起着非常重要的作用。数据驱动和子空间方法被用于许多地方，以解决运行时计算成本问题（例如流体[11]，变形[12]）。 数据驱动方法的主要概念是建立一个数据库来支持实时计算。 James和 Fatahalian [5]提出了一种方法来处理交互式应用的可预测动作。 脉冲响应函数（IRF）和脉冲调色板可以表示特定的动作序列，通过组合多个动作并回顾所选动作的预计算数据，可以实现交互式的实现和复杂的变形。 但是，这种方法主要针对单瞬时脉冲的动作，并且不能实现复杂的动作。 从一种冲动转换到另一种冲动也缺乏准确性，并且不能很好地证明先前行动留下的惯性。Guan等人[6]提出了一种方法，通过使用多线性代数将头发参数（长度，柔软度等）从学习数据库中分解出头发外观。该方法可以在调整头发参数的同时实时实现头发动画。然而，与James等人的方法一样，Guan等人的方法并不重视动作之间的惯性力。Kim等人[7]将IRF与动作图结合在一起（在第3.1节中解释），作为James处理复杂动作序列的实时布阵方法的扩展。布料沿着身体的动作存储在次动作图（SMG）中，其中每个节点对应于人体的动画片段。通过从最大布料状态的连接错误发生的位置扩大图形，可以在一定程度上保留先前动作留下的惯性效果。这种方法可以实现比[5]中James的方法更复杂的动作，并且在交互式应用中实现令人满意的布料动画。Kim等人的方法是有希望的，但是考虑到非常大的数据库，构建的数据库的质量变得重要。Stanton等人。在[13]中将Kim等人的方法应用于流体。通过检测玩家往往采取的最常见的行为，Stanton等人的方法着重于如何提高含有重要数据的构建的SMG的效率。考虑到头发也是角色身体上的附属物，Kim等人的方法为交互式应用中如何处理头发动画提供了新的思路。但是，头发的特殊性使得直接应用这种方法变得困难。因此，我们试图找到一种方法来提高数据库的质量（基于SMG）。3 动作图和二次动作图在本节中，我们将动作图形描述为输入，将次动作图形描述为我们的输出。 我们还简要描述了我们方法中使用的脉冲响应函数。3.1 动作图在我们的方法中，使用主动作图（MG）作为输入。 它可以通过像[14]这样的方法构建，其动作可以通过Blender或Maya等软件工具手动调整。 角色的身体动作序列包含在该图中（图2）。 每个节点代表由许多身体姿势构成的特定动作（行走，跳跃等）。 转换限制被添加为图形的边。 我们在这里从MG获取的信息是头部沿着身体的动作。3.2 次级动作图次级动作图（SMG）是存储与动作图节点相对应的头发动作数据的图形。 用户想要采取的下一个动作通常是未知和不可预测的。 尽管不必考虑身体动作的惯性或碰撞力，但如果以与身体相同的方式处理头发的动画，由于缺乏这些力的效果，它们将变得非常不自然。为了表现自然附着于身体的其他部位，我们需要构建SMG（参见图3）以存储这些部分的相应头发动作。 SMG节点包含，对应的MG节点ID（MGID），具有与其动作图节点相同数量的帧的动作序列数据（IRF）父节点的ID（与之相对应的前一个动作，即从它哪里转换而来），子节点的ID。构建的SMG包含比原始动作图更多的节点。这意味着，身体的动作可能对应于几个不同的头发动作节点，这取决于之前采取的动作。 特别是在游戏中，当没有给出命令时，放松状态（例如空闲动作）被认为是默认状态。相比于其他，这种放松的动作可能与多的SMG节点有关联。一个转换是两个SMG节点之间的定向链路。 两个动作序列从转换的开始到结束SMG节点连接。 请注意，一个转换和一个反向的转换可能有完全不同的动作顺序。还有从节点到同一节点的自循环转换。3.3 动作序列的表示每个SMG节点中的动作序列数据存储在类似于IRF（脉冲响应函数）数据库[5]的结构中。 构建一个包含整个动作序列数据的矩阵。矩阵的行是帧，列是预先定位的发丝的顶点坐标。对于这样的矩阵，可以使用奇异值分解来进行压缩。然后将压缩的动作序列表示为一组基向量，其维数远小于帧。4 构建头发的次级动作图当用户给出命令时，为了获得平滑和自然的头发动画效果，我们必须沿着主动作图构建次级动作图（SMG）。此外，为了表示先前动作传递的细节惯性力，我们需要将SMG扩展到满意的水平以包含所需的细节。例如，如果角色从空闲状态开始，则进行步行动作并再次返回到空闲状态，由于惯性力，后面空闲状态的头发动作将与起始动作不同。图中还将存储两个与同一MG节点（空闲）相关的SMG节点。我们需要注意的是如何选择和保存所需的重要动作片段，以使图形更加充分（即包含更重要的数据，同时尺寸更小）。4.1 头发的形状直方图为了选择足够的动作数据，我们必须找到彼此接近的动作。详细的头发模型包含数千条单独运动的发丝。一次剧烈的动作可能导致不同的发丝彼此交替，这使得发丝顶点之间的距离与其他状态相差非常大，但是头发的形状似乎是相似的（如图5所示）。偏差值度量方法Kim等人在[7]中使用的只是顶点之间的L0或L1欧几里德距离。对于头发，这种方法无法正确识别相似的状态或动作。考虑到顶点的数量要比布料多得多，并且少量偏差不应该影响整个外观，所以需要一种评估两种头发动作相似性的好方法。在这里，我们介绍形状直方图（类似于[15]），如图4a所示，以评估头发状态之间的相似性。首先，当构建IRF时，通过将头部动作的逆（从MG已知）相乘，头发状态全部局限于中心。局部头发模型周围的空间被分成许多网格，并且每个网格中的顶点数被计算为每个直条中的直方图值。两个头发状态的直方图中的非零直条被用作计算偏差值的有效直条（如图4c所示）。两个直条的直方图之间的绝对差的平均值被用作两个当前头发状态之间的偏差值。为了评估整个序列，我们还使用每个帧的偏差值的平均值作为SMG的两个节点a，b的合并误差ε（a，b）ε（A，B）= Haj（i）-Hj（i），（1）1N 1nj N njj = 1 i = 1 b其中N是帧的数量，nj是帧j的有效直条的数量，Haj（i）是节点a，第i直条，第j帧的直方图值。 请注意，对于SMG中的一对节点，N是一个常数值，但nj可能会每帧都会改变。所计算的合并偏差值用于确定当前两个动作是否足够相似以便合并，或者将从哪个节点开始应用下一个扩展，这将在稍后的小节中进行描述。4.2. 为头发构建SMG与Kim等人的方法[7]不同，它只考虑当一个动作发生切换时的即时状态偏差值，我们想要考虑未来动作的整个序列。 为了考虑这样一个未来的动作序列，我们在这里提出了一种新的构造算法，以便能够建立两个动作序列之间更加平滑的连接。 构建SMG的过程包括以下步骤：1.初始化，2.扩展，3.合并（和扩展）以及4.添加响应序列节点。 我们将逐步描述我们的算法。 在附录A中，我们还展示了我们完整算法的伪代码。为了帮助理解我们的算法，我们将使用图2中的MG作为示例。 在该图中有五个节点（待机，行走，左转，右转和跳跃）以及18个转换，包括自循环（橙色允许，例如待机到待机）。初始化.首先，选择起始节点（例如待机），并且MG中的所有转换以广度优先的方式遍历以构建如图6a所示的SMG的初始树。 在此树中，相同颜色的节点具有相同的MG节点标识（MGID）。该树中包含两种节点。 一个是正式的SMG节点，另一个是所谓的鬼节点。正式的SMG节点是在实时过程中实际使用的节点。 相比之下，鬼节点是SMG的潜在节点。 它们被存储来确定SMG的准确性是否足够，同时是否需要添加为正式SMG节点。 引入鬼节点是我们算法的关键，因为它们被认为是可以实际采用的未来动作的候选对象。在初始树结构中，MG节点模拟得到的结果里，我们将初次访问到的设置为SMG节点，而已经被计算过的设置为鬼节点。扩张.接下来，我们应用来自鬼节点的图形扩展，以减少两个动作序列之间的偏差值。对于每个鬼节点g，使用等式（1）计算满足以下三个准则的节点的偏差值：来自同一转换的节点，同时有相同的MGID。祖先节点有相同MGID。两节点具有相同MGID，且没有节点满足条件1和2。然后，我们在上面计算出的偏差值之间选择最小误差εmin（这里称之为合并误差），而对应的节点h（这里称为合并节点）则是g最相似的动作。如图7所示，对于一个鬼节点No.6，No.4（来自条件1）和No.0（来自条件2）被选为候选者，而No.4最终作为合并偏差值节点。我们现在处理扩展步骤如下：我们首先准备一个堆E，并为每个鬼节点存储一个三元组（g，h，εmin）。然后，我们使用delete-max操作从E中取出具有最大键值的鬼节点，并将其设置为正式的SMG节点。然后，我们遍历新的SMG节点的转换，创建鬼点，计算合并偏差值并将它们存储到E.重复此过程直到最大键值小于阈值λ。图7显示了扩展过程的工作原理。合并（+扩展）.* 扩展过程完成后，堆中所有键值的合并偏差值应小于阈值λ。 接下来，我们合并每对偏差值εmin的两个节点g和h以减小SMG的尺寸。两个要合并的节点具有相似的动作。为了执行合并操作，我们继续使用在扩展过程中创建的堆E. 对于堆中的每个鬼节点g，如果待合并节点h是正式的SMG节点，则进行合并。也就是说，g被丢弃并且其父节点的转换指向h。 如果h是鬼节点，则不能应用合并操作，因为两个节点都是鬼节点。 在这种情况下，我们首先将h设置为正式的SMG节点，并将扩展操作应用于新的SMG节点。 然后，我们将合并操作应用于上述的g。当这个过程完成时，剩下的鬼节点全部被丢弃。 图8显示了合并操作完成后的SMG。添加响应序列节点. 在扩展步骤中，使用阈值。用户给出的这个阈值将直接决定图形的大小。较大的值会导致更详细的动作丢失，而较小的值会导致图形过于庞大。为了将图形缩小到合理的大小并同时获得平滑的结果，我们考虑引入IRF的思想[5]，并保留最容易注意的细节。例如，MG节点“待机”是角色最常见的状态，动作保留了最多的SMG节点，并添加了额外的细节以扩展这些动作。如图9所示，我们在图中添加了一个更长的循环“待机”动作序列作为响应序列节点（RS节点）。 RS节点与SMG节点有如下不同：1.节点长度，2.与其他节点的关系，3.它们如何显示。这里，1.指向自循环节点的“待机”，2.指向“待机”节点，3.是自循环节点的SMG节点将考虑进行合并。然后，我们将每个节点合并到相应的RS节点中的适当位置。这个位置是最相似的动作序列结束的地方，所以节点可以转向具有较少不兼容性的响应序列。为了在相应的RS节点中确定适当的位置，我们准备了一个矩阵形式的偏差值（偏差值矩阵），如图10所示。在该图中，行表示RS节点的帧，列表示合并后SMG节点的帧。 然后，将RS节点和SMG节点中的每个帧之间的不相似性存储为矩阵的每个元素中的灰度颜色，其中较亮的颜色具有较大的形状直方图误差，如等式（1）中所述。在误差矩阵中，要选择的动作序列表示为右下行（图10中的红线）。 在这些行中，我们选择一条线上形状直方图误差最小的方差。 这确保了两个动作以类似的方式移动，并且通常也具有小的错误。 上述方法的一个优点是与阈值无关，即，在不使用阈值的情况下确定RS节点中的适当位置。5 运行时过程在构建SMG之后，我们将其用作支持运行时过程的数据库。由于SMG基于动作图，因此只能显示图中包含的动作。当头部位置发生变化时，我们通过基础向量和权重的线性组合来计算当前SMG节点及其当前帧中头发的顶点坐标。包含在IRF中的头发动作数据不包括位移信息，并且仅包含局部坐标中头发的变形数据。随着头发与头皮（或头部）一起移动，我们只需要将头发模型与头部关节位移信息一起转移。我们现在设置一个关于从当前节点到下一个节点的变化的动作图的约束：尽管在移动过程中用户给出了一个动作命令，但角色继续移动直到它到达可切换点（当前节点的结尾） 。然后，正在执行的动作发生变化，字符从当前节点移动到下一个节点（请参见图11中的运行时进程）。同时，SMG中的头发节点将根据下一个动作的ID切换到子节点。当转换约束被添加到动作图中时，不会发生非法切换，并且相应的节点也不会在子节点列表中。由于SMG是无限循环图，MG中的交换机总是可以找到相应的SMG节点。然而，如果响应序列节点存在，当动作切换到空闲状态并保持循环（当SMG节点切换到响应序列节点时），则选择节点并且动画将从开始帧开始，其中前一个SMG节点是指点。因为合并SMG之前的响应节点的子节点已经合并到空闲节点，所以下一个动作的响应节点和节点之间的错误可以被忽略。5.1 连接惩罚由于我们使用鬼节点而不是即时状态错误，因此从一个节点切换到另一个节点时发生的失真大于Kim等人的方法[7]。然而，通过混合两个节点，即使它们的开始和结束状态完全不同，我们也可以实现从一个节点到另一个节点的转移，而在几个帧内没有不明显的误差。我们只是使用线性混合来连接两个节点。随着动作图节点继续其结束，误差必须发生在第一个节点的末尾和下一个节点的开始之间。我们将前一个节点的结束状态保存为转换时发生的惩罚，作为这两个节点的顶点位置之间的距离，并将该惩罚加回到下一帧的开始序列（对于某个混合长度），如图12.注意混合长度必须小于节点长度，所以惩罚不会传递到下一个动作。6 结果和讨论在我们的实验中，使用18个转换的CMU动作捕捉数据库[16]中包含待机，行走，左转，右转和跳跃的五个动作捕捉动作用于主动图。我们使用包含4134个指甲毛发和41340个顶点的头发模型，并将Maya的nHair系统作为黑箱模拟器来计算头发动作。计算头发碰撞和头发皱纹，但没进行头发身体碰撞。对于合理的阈值5.5，模拟10662帧有效动作序列（约5.1GB）。根据这些原始数据，最终的SMG中包含2220帧动作序列（SVD后约460MB）。表1显示了构建具有多个阈值的SMG组的统计结果。随着阈值的增加，图形尺寸变小（阈值为6.5时为1576帧，阈值为8.0时为1251帧），但我们仍然可以通过添加RS节点获得视觉上满意的结果。与Kim等人的方法相比，我们的图的大小在阈值降低时更有效地增加，并且可以获得具有相同图形尺寸的更自然的结果，因为由惯性力（或未来误差）会被考虑在内（请参阅附件中的视频）。使用我们的方法，图中包含的冗余数据较少。在运行过程中，我们使用AMD的TressFX头发系统作为渲染器。在CPU使用率低于20％，内存使用量约为512MB的情况下，可以达到超过100 fps（CPU Intel Core i7-4770和GPU NVIDIA GeForce GTX TITAN），而无需任何GPU加速或并行计算。局限性.由于SVD矩阵的列/行速率很大，所以数据压缩比不能满足要求。要获得详细的头发动画，我们必须使用大量的头发顶点。虽然在运行时流程中，渲染时间得以节省，但内存成本是不可避免的。对于交互式应用，单链插值可以结合使用以实现低内存成本。可以应用Chai等人 [9]减少头发的方法，以获得每个IRF的最具代表性的引导毛发（只要每个IRF的引导发股的数量是相同的），并通过内插恢复详细的结果。7 结论我们提出了一种新颖的数据驱动方法，可以为游戏等实时应用程序实现详细的头发动画，在运行时过程中计算成本非常低。顶点对之间的L0或L1误差度量对于头发来说是无意义的，因为详细的头发动画需要大量头发，并且即使头发的总体形状非常相似，每个线的误差也可能非常大。我们提出一种使用头发形状图来识别重要（有意义）的数据的方法。通过存储最重要的数据，我们可以构造一个冗余较少的辅助动作图。如果考虑顶点对之间的关系，阈值会有很大的变化，但是，通过使用我们的形状直方图的误差准则，我们可以获得一个比较稳定的阈值，当发丝数或主动作图的数量发生变化时，这个阈值会略有变化。由于在从一个节点切换到另一个节点时使用了混合，所以连接偏差值对头发动画来说不如布料重要。考虑到总序列误差而不是即时连接误差，由于考虑到惯性力，我们可以在动作之间切换时获得更自然的结果。
[译]准完全预计算下的辅助布料效果
图1计算机图形学中针对数据驱动方法的中心论点取决于维度的咒语：对复杂空间的“一切”进行预计算是棘手的。在本文中，我们通过使用数千的CPU运行时间来挑战这一假设，以便通过大型运动图，对辅助服装空间（the space of secondary clothing）在动画角色上的影响进行大规模探索。我们的系统将不断探索布料动力学的拓扑空间，逐步构建一个可以捕捉动力学系统的辅助布料运动图（secondary cloth motion graph）。我们发现有可能将动态空间采样到低视觉容错，并且包含数十千兆字节原始网格数据的辅助运动图可以被压缩到仅几十兆字节。 这些结果使我们能够捕捉高分辨率及离线布料仿真对丰富的角色动作空间的影响，并将其作为交互式应用程序的一部分进行高效传送。关键词: 布料模拟，数据驱动动画，视频游戏1 简介数据驱动技术已经实现了有着惊人复杂现象的实时动画，这些现象原本要么过于昂贵而难以实时模拟（例如高分辨率布料的褶皱 [Kavan等人 2011; Wang等人 2010] ）或是缺乏优异的模型（例如人体动作）。然而，反对这些基于预计算的方法的中心论点取决于维度的诅咒：不可能捕捉到“一切”，因为每个额外模拟条件下的动态空间都在指数性爆炸增长。基于此原因，之前几乎所有的数据驱动动画都工作在很少的激励模式下，在严格控制的环境中研究现象，并且严格假设现象会周期性地返回到单一静止配置[James和Pai 2002; James和Fatahalian 2003; de Aguiar等人 2010; Guan等人 2012]。鉴于低成本，大规模计算能力的快速增长，我们认为现在是重新审视这一假设的时候了。尽管捕捉复杂动力学系统的所有内容并不容易，但是捕捉几乎所有重要的内容却是可能的。这反映了计算机科学的发展趋势：研究人员在理论上研究机器翻译等无限空间时，已经捕获了翻译的“几乎所有内容”。例如，仅需使用足够大的数据语料库[Halevy等人 2009]即可完成。在本论文中，我们将重点放在通过有限运动图进行动画角色辅助布料效果的预计算上。我们引入了辅助运动图的概念：对于主运动图中的每个状态（在本例中为角色的姿态），辅助运动图中可能有许多相应的状态（在本例中为身体上的衣服配饰）。因为布料是一种动力学系统，布料的状态而不仅取决于身体的姿态，还取决于之前的布料状态，所以辅助运动图可能比主动作图复杂得多。我们通过对辅助运动图空间进行大规模的探索来报告我们的发现。与之前关于预计算的工作相比，我们模拟了更多的数据以构建动力学相位空间的大型图像。我们的主要示例使用超过55分钟的模拟布料动画以及超过4500个CPU小时的计算来表现。我们探索的规模使我们能够观察动力学中的分枝现象，即布料配置的持续变化会产生新的子图，这些子图与计算过的状态大部分保持不相交。我们证明，即使对于大型动作图形，也可以探索辅助动态空间以降低视觉容错 - 基本上，预计算几乎所有重要的 - 可以将结果数据压缩到相当小的内存占用。在实际应用中，这些结果使我们能够捕捉到高分辨率离线布料模拟对角色动作丰富空间的影响，并将其作为交互式应用程序的一部分在适度的硬件上进行实时传送。与许多数据驱动技术相比，我们的模型保证了预计算模型中近似误差的范围。由于采样不足导致的误差仅在数据库中稀疏的一组帧中出现。因此可以完全验证误差，甚至可以手动检查这些误差帧。此外，与之前的预计算方法通常需要详细设置预计算确切场景相反，我们的系统旨在支持动态空间的“持续探索”，在相位空间的不断扩大的空间中构建动态空间。2 相关工作使用计算机模拟生成布料动作已成为一个长达四分之一世纪的活跃研究课题[Terzopoulos等人 1987]。在那段时间里，有关布料动力学和碰撞处理的关键问题已经得到解决[Baraff和Witkin 1998; Bridson等人 2002; Choi和Ko 2002; Bridson等人 2003]。 有关布料模拟方法发展的总结可以在Nealen等人[2006] 和Thomaszewski等人[2007]的调查文章中找到。目前许多模拟布料的方法可以产生非常逼真的结果，甚至可以以假乱真[Mu ̈ller和Chentanez 2010; Narain等人 2012]。这些方法的逼真程度可以通过使用测量材料特性来增强[Wang等人 2010; Miguel等人 2012]，甚至模拟独特纱线层次物理学来增强[Kaldor等人 2010]。然而不幸的是，目前逼真高分辨率布料仿真的计算成本导致了它在交互式应用中难以使用。图形研究人员使用各种方法解决了这个问题，其中许多方法也使用预计算的数据。一种常见的方法是进行低分辨率仿真，然后使用基于预计算的高分辨率仿真来添加额外的褶皱细节[Wang等人 2010; Kavan等人 2011; Feng等人 2010]，记录真实布料[Popa等人 2009; Hilsmann和Eisert 2012]或简化的物理模型[Mu ̈ller和Chentanez 2010; Rohmer等人 2010]。 尽管这些方法能以最小计算开销来显着提高布料真实性，但结果运动仍然会反映出低分辨率的底层模拟网格。研究人员还研究了减少模型的方法，以求在一个降阶模型中充分捕获流体[Treuille等人 2006; Barbicˇ和Popovic 2008; Wicke等人 2009]、可变形对象[James和Pai 2002; Barbicˇ和James 2005; An等人 2008]等复杂系统。这种方法可以显着地加速，但是很难捕捉不连续物体，并且会对底层动力学产生其他限制。 此外，这种数据驱动的方法通常要求模拟运动与预计算的数据密切相关，如果被捕获的模型数据偏离系统预期太远，将会出现不可预知的错误。本文探讨了一种不同的方法，使用更简单的基于图表的模型来进行动力学统计，同时强调大量的预计算以捕捉大部分布料相位空间。de Aguiar等人 [2010]的稳定空间技术完全避开了运行模拟，选择从黑箱模拟数据中学习准线性模型，而不是减少人物角色上的服装动力学。这个学习模型基于身体姿态（数据驱动反馈的蒙皮方法）和近期布料状态来拟合布料动作。与de Aguiar的工作相反，James和Fatahalian [2003]明确列出了可变形系统的（任意非线性）动力学。 通过导航驻留在预计算子空间中的布料轨迹数据库来实现实时布料动画。我们的工作在精髓上与他们相似，但在两个关键方面有所不同。首先，我们不使用简单脉冲的小调色板来驱动系统，而是通过使用角色运动图来表现更加丰富的外部布料空间。其次，我们的状态空间抽样过程的规模允许我们统计更复杂的布料行为，包括展示行为分枝和布料的空间，而并不会返回单独的休息状态。我们的工作致力于将大量预计算的数据提取为一种表示形式，从而在交互式系统中提供高质量的布料动画，以实现子空间采样和数据压缩挑战。我们的方法的一个关键优点是，它自然地模拟了相位空间中的分枝，这是预计算方法的一个关键挑战。Twigg和James利用动力学分枝（来自碰撞）控制图形。他们的方法之一探讨了接触不确定性来创建动画，并聚合到期望的最终状态[Twigg和James 2008]。另一个将碰撞物体的分枝动力学形象化为控制的交互范式[Twigg和James 2007]。我们的工作同样研究包括分枝在内的大规模相位空间，但是我们的目标是不同的：我们将分枝视为数据驱动的交互式仿真过程中不断修复建模的方式，而不是寻求控制它们。3 辅助运动图我们追求一个完全数据驱动的系统，用于综合人性化服装的实时、高分辨率动作。我们的方法依赖于模拟布料运动的大量抽样，这是通过大型运动图对角色进行动画处理而产生的。随着新的布料动作的产生，它们被分析并压缩成一个紧凑的表示形式，从而实现低成本的运行时使用。我们接下来描述我们的布料动作表示方法，以及用于采样，压缩和交互式回放预计算布料运动的技术。3.1 辅助图定义图3我们用两个运动图[Kovar等人 2002; Arikan和Forsyth 2002]表示人物动作及其相关的辅助布料动力学。第一张图，我们称之为主图，是描述角色移动的标准运动图。我们图表规范中使用图节点$p_{i}$代表个人角色姿势（而不是运动剪辑）。那么，图中$p_{i}$到$p_{j}$的边代表在动画中可以由$p_{i}$状态直接变成$p_{j}$状态。 图3中以黑色标识了具有七种状态的主运动图的一个小例子。我们用一个辅助布料运动图来附加到主运动图，这个图表将布料运动的巨大（可能是无限的）空间制成表格。 辅助图中的每个节点（图3中的13个红色状态）表示一个布料姿态$c_{i}$，并且它与现有的一个主图节点$P(c_{i})$相关联。 也就是说，当布料呈现姿态$c_{i}$时，角色处于状态$P(c_{i})$。 布料相位空间的大量采样将导致辅助动作图明显大于主图。因此，如图3所示，主图形中的每个节点都可以跟许多辅助图状态相关联。在播放过程中，主图的遍历由应用程序的角色控制器控制，这在当今的交互式应用程序中很常见。为了生成布料运动，从$p_{j}$到$p_{k}$的每个主图转换也触发从当前布料状态$c_{i}$到$C(ci,p_{j}\to{p_{k}})$的相应辅助图转变。在图中提供了一个枚举布料状态$c_{0}$和$c_{5}$的辅助图转换的表格。辅助图及其相关的转换表$C(ci,p_{j}\to{p_{k}})$描述了布料在角色施加外力下响应的运动。总之，它们的功能类似于James和Fatahalian [2003]描述的脉冲响应函数数据库。 通过将外力表示为主运动图中的转换，我们可以编写比James和Fatahalian的脉冲调色板更加丰富的力空间。3.2 图探索由于其动态动作，服装可以通过主图从角色连续动画获取任意量的配置信息。因此，整体制定辅助运动图很可能是棘手的。 相反，我们通过重复遍历主图的片段并使用黑盒离线布料模拟器计算相应的布料运动，从而逐步建立辅助运动图[Narain等人 2012]。 我们的系统专门设计为能够“永远取样”，探索未发现的动作，同时持续保持有效的辅助运动图，以便立即交互使用。图初始化。图初始化。我们通过从任意选择的初始角色姿态开始，进行宽度优先遍历来探索每个主图边，初始化辅助图。衣服置于该初始姿势上，角色进行完姿态以后，穿过该姿势对应正面模拟衣服的图。图4左边展示了在初始布料状态为$c_{0}$的情况下从节点$p_{0}$开始的探索。得到的结果是由仿真产生的布料轨迹树（以红色显示）。（为了清晰起见，在图的左下角重新绘制该树。）从树的根$c_{0}$到叶$c_{i}$的每条路径表示从初始姿势$P(c_{0})=p_{0}$到$P(c_{i})$。RemoveDeadend(c_end): (c_similar, err) = FindMostSimilar(c_end) // merge cend into c_similar foreach edge e incoming to c_end do: modify e to point to c_similar remove c_end from graph workQueue.AddJob(err, (c_end, c_similar))ExpandGraph(): do forever: (c_end , c_similar) = workQueue.LargestErrorJob() // revert the merge of c_end into c_similar re-insert c_end into graph foreach edge e incoming to csimilar do: if e resulted from prior merge with c_end: modify e to point to c_end newSubtree = SimulateCloth(c_end) foreach new dead-end cnew in newSubtree do: RemoveDeadend(c_new)此时，树的叶子在辅助运动图中是末端点。我们找出与它共享相同主图状态同时具有最相似的内部布料状态的节点，通过合并他们来删除每个末端点状态（参见函数RemoveDeadend()）。请注意，在图4的中间面板中，末端节点$c_{5}$和$c_{9}$已分别合并为$c_{0}$和$c_{2}$。 （删除的节点$c_{5}$和$c_{9}$在辅助图中以灰色显示。）先前通向末端节点的边现在通向合并的目标（以蓝色显示）。一旦所有末端点都被删除，图表初始化就完成了。现在，辅助图为任意角色动作序列提供布料动画结果，因此可以粗略地近似布料动力学的整个空间。图中的红色边与实际模拟轨迹相对应，蓝色边则构成了过渡到真实布料动力学的转换。当近似值较差时（即图中没有内部节点与末端状态相似），需要进一步采样布料相位空间以减少此误差并避免播放期间的低质量运动。无穷图扩展。 在每个末端合并操作之后，我们将（合并前）末端布料图状态及其相关联的（合并后）边近似误差值存储在优先工作队列中以供进一步采样。为了减少布料的动作误差，我们使用函数ExpandGraph()给出的步骤来大幅优化辅助运动图。在每个扩展步骤中，我们从优先级队列中取出含有最大的误差值的末端$c_{max}$，并通过恢复先前的图，也就是撤销合并操作来将$c_{max}$重新插入图中。然后，我们模拟从$c_{max}$（和角色姿势$P(c_{max})$）开始的布料运动。进一步模拟取样布料相位空间之前未探测的区域，并在辅助图中产生另外的新的末端。 如前所述，通过添加合并消除这些新的末端。图4右图显示了从入队的末端状态$c_{5}$开始执行图探索的一个步骤的结果。额外的仿真会导致两个新的末端，这两个末端都被合并到$c_{2}$中。辅助图细化的过程不断重复后，消除了在探索布料相位空间时遇到的最大物理误差值，同时始终保持无末端的辅助运动图。虽然在每个新扩展步骤中执行的仿真都依赖于先前的结果，但是在工作队列中每个末端扩展图是独立的，使图扩展得以并行。3.3 细化服装定制的误差指标。 某些布料过渡误差值比其他布料过渡误差值更令人反感。为了给系统提供最劣误差值的概念，我们可以为特定的服装或动作领域定制布料-姿势相似性度量。例如，对于长袍服装（在第5节中讨论），特别令人反感的是，布料图包含将头巾从角色肩膀上的一个位置向上抬起的反向链接。我们发现简单的误差度量（例如，顶点位置和速度的$L_{1}$或$L_{∞}$误差）并不能将这样的过渡标识为恶劣的，所以我们采用一种度量方法来将布制品的姿势分类为向上或向下，并分配高误差来合并这些会导致难以置信的从下到上的过渡。这些过渡会升至优先队列的顶部，系统通过从这些高误差末端开始探索动态，从而得到快速消除偏差值的结果。图形混合。 二次图中的运动误差会在末端合并（图4中的蓝色边缘）所生成的边处发生。为了减少由这些不连续性引起的视觉伪影，我们通过在合并状态之前和之后线性混合轨迹来将它们的误差值分散在一系列帧（我们实现使用十个）上。4 压缩在任意辅助图拓展步骤之后，我们可以压缩和打包数据以进行交互式可视化或集成到游戏引擎中。压缩对于交互式播放至关重要，因为我们原始的辅助图数据由成千上万个需要数百GB存储空间的布料网格构成。但是，正如其他人以前所观察到的[Wang等人 2010]，服装往往形成几乎重复的模式，而且这些数据存在大量冗余。我们发现原始的辅助图数据可以压缩的非常好，而压缩后的结果体积小，可以实时有效地解压缩。这种压缩对于现代游戏这些通常具有有限内存预算的程序而言至关重要，特别是对于辅助效果。我们首先通过执行James和Fatahalian [2003]描述的核心外SVD来降低数据集的维数。该步骤将布料数据矩阵$D\in{R^{3v\times{n}}}$（包含v个顶点位置的n个帧）分解成b维布料基础$B\in{R^{3v\times{b}}}$和轨迹系数矩阵$C\in{R^{b\times{n}}}$，使得$D\thickapprox{BC}$。我们通过实验确定，使用200个基（$b=200$），重建的布料网格在视觉上与原始模型非常相似。但是，在布料与底层人体模型接触的地方，即使小的压缩误差也会导致深度顺序颠倒，从而导致清晰的渲染伪影。我们在渲染过程中使用深度偏移技术[de Aguiar等人 2010]，并通过非常轻微缩小身体模型来消除这些伪影。我们进一步观察到，尽管较少的基向量不足以保持良好的视觉保真度，但个别基向量在其几何影响方面差别很大。我们使用$m_{i}=max_{j}|C_{ij}|$表示每个基的最大绝对贡献，发现$m_{i}$可以在整个基上以数量级变化（图5）。我们通过用较少的位表示对几何影响较小的基向量来实现进一步压缩。我们用{$m_{i}$}重新缩放布料基，得到$B'=BM$和$C=M^{-1}C$，其中$M=diag(m_{1},...,m_{b})$。缩放$B'$可以解释为长度单位最大顶点位移，现在可以进行量化。我们发现在视觉效果变得明显之前，最可能的量化是300微米的量子。在这个容错下，使用16位比特和8位比特可以很容易地表示基向量。就我们的便装demo场景而言（第5节），使用8位比特可以表示82％的基本矢量。生成的压缩基础只需要22MB的存储空间。 对轨迹系数也执行类似量化为16位比特。这种使用两位宽度的简单压缩方案实现了高压缩，同时在运行时能够高效地对矩阵$C'$中的轨迹数据进行解码。5 结果为了评估我们的方法，我们通过由HDM05动作捕捉数据集构建的运动图对角色进行动画制作，从而对布料进行了大规模的探索[Mülleret等人 2007]。我们的主运动图包含12个独特的动作剪辑（总计3115帧）。我们选择了包括跑步，投掷，踢球，跳跃和执行车轮在内的各种有力动作的剪辑，以引发高度动态的布料动作，并将服装引入各种配置。从这张主图中，我们为两个布料配置设置生成了辅助运动图：长袍，单件连帽长袍和便装，其中包括三件衣服（包括宽松的裤子和宽松的背心）。我们使用高质量的离线布料模拟器ARCSim1来计算布料运动[Narai等人 2012; Wang等人2011]。为了适应我们的压缩方案，我们禁用自适应重新网格划分并使用固定的网格拓扑。平均来说，我们两个演示的离线帧模拟时间分别为165秒和243秒。虽然这两个演示都具有类似分辨率的服装，但便装中多个布层之间的复杂碰撞处理会导致较长的执行时间。5.1 大规模探索使用超过6,400个CPU小时计算（在英特尔提供的一组机器上），我们生成了超过99,000帧长袍布料动画（大约55分钟的模拟动作，可以直接在图2和图6看到），和27,000帧便装动画（15分钟）。 两个辅助图都比角色运动图大了将近一个数量级。 为了简洁起见，我们将重点放在本节的长袍探索中的发现，读者可以转到随附的视频中查看便装的结果。简而言之，我们发现我们的大量计算已经充分地将布料动力学的相位空间采样为拥有良好的视觉容错。我们能够为主图的任意遍历生成令人愉快的布料动画。 正如随附的视频所显示的那样，即使在剧烈的角色动作（例如侧手翻（图1））之后，通过辅助图也能产生高度细致平滑的布料运动，使布料明显不同于其起始状态。尽管我们的最终辅助图确实变现了高质量的运动，但在探索的早期阶段，情况并非如此。紧随着图形初始化，辅助图对于每个主要角色姿态仅包含一个布料姿态，类似于布料运动的动作学近似。正如预期的那样，这种近似不足以为我们的服装产生逼真的动作，从而证实辅助布料图必须比主图更加复杂。在这些早期阶段，当布料从复杂结构转变回接近初始起始状态的配置时，可以清楚地看到大的误差。进一步的探索逐渐消除了令人震惊的动作误差，更重要的是，揭示了辅助运动空间中的有趣结构，如分枝。虽然我们最初的长袍配置的特点是头罩罩住了角色的头部，但我们发现一些动作序列（例如走路→跳跃→走路，或走路→慢跑→走后→右跑）导致头罩落下。图6显示了根据头罩状态进行着色的完整长袍辅助图。（红色表示头罩保留在角色的头部，而蓝色表示头罩已经掉落。）我们的探索发现五个独特的角色动作序列，导致头罩落下。然后它并行探索相位空间的这些不同区域。当第一次遇到分枝时，头罩落下的次数很少。因此，末端的合并往往会形成将头罩从下往上掉的过渡（没有类似的头罩摘下合并的姿势）。但是，我们的误差（将机器状态分类）会以高误差标记这些不合理的过渡，因此系统会立即将计算资源用于探索图形的这些部分。一旦辅助图达到99,000帧尺寸，就不存在从头罩落下到头罩戴着状态的合并转换。该图基于头罩状态大致分为两个子图。连接这些子图的边缘全都对应于正确的模拟动作，其中头罩在翻转时自然落下或罩在角色的头部上。图7绘制了辅助图中最劣过渡的$L_{∞}$误差（从包含顶点位置和时间标度速度的向量）的演变。在粗尺度下，当我们详细探索相位空间时，图中的误差会减小。然而，误差有重要的细微差异，我们归因于两个原因。首先，一个简单的距离度量可能是相位空间未来误差的一个不好的预测器。 （改进误差度量以考虑未来可能出现的误差，以便早期发现高误差区域，这是未来工作的一个重要领域。）其次，探索揭示了需要进一步采样的空间新部分（例如，头罩落下）将最大误差降低到先前的水平。我们选择了长袍的例子，因为它包含大量的流动区域，它们具有相对较高的滞后性。这种行为会为每个主状态产生很多辅助状态，但是我们最终会得到合理大小的压缩数据库。便装示例的滞后性较差，因此需要较少的预计算并生成较小的压缩数据库。5.2 交互式播放我们可以在Apple MacBook Pro笔记本电脑（Core i7 CPU）上以每秒70帧以上的速度从压缩的辅助图播放布料动画。使用一个简单的基于CPU的实现（使用OpenMP进行并行化），可以执行解压缩以及计算矩阵向量乘积以合成每个布料相位姿态（可以使用定点算法执行）。6 讨论在这项工作中，我们利用大量计算资源将数据驱动的动画推向前所未有的规模。尽管之前的数据驱动方法仅限于简单的受控设置，但我们使用了数千小时的CPU时间来彻底探索辅助布料运动的巨大相位空间。我们相信我们大规模探索的结果是惊人的。我们不仅捕捉到丰富的具有足够密度的布料细节，消除了广泛的人物动作的回放伪影，还能够发现相位空间中的分枝并继续在每个不同区域中对布样动态进行采样。我们演示中的衣服不会简单地返回到单独的休息状态：头罩落下，衣服以各种方式环绕角色。许多技术对于进行大规模的探测和随后的实时播放都是必要的。最重要的是，我们引入了辅助运动图的概念来指导阶段空间探索过程，并实现对运行时用户输入的高效响应。分析布料基减少导出一个简单的自适应量化方案，进一步压缩数据集。我们还创建了一个布匹相似度函数，专门考虑了长袍头罩的位置，以强有力地识别最严重的辅助图转换误差。总之，我们的系统生成了超过43GB的布料数据，将这些数据压缩为34MB和66MB大小的辅助布料图，并在70多个笔记本电脑上响应用户输入提供了高质量的辅助布料动画FPS。关于数据驱动技术的可行性的一个常见问题集中在运行时内存占用。虽然我们的大约70MB的要求对于以现代控制台系统为目标的游戏来说可能太大了（例如，Xbox360只有512MB的RAM），但我们认为它的成本在当今现代PC（和即将到来的次时代游戏机），它们目前拥有多GB的内存。 此外，我们还没有完全探索布料基或辅助图压缩策略的各个方面，所以更好的压缩以及运行时解决方案都会使辅助图的区域流（仅留下基本表示形式）变得很有可能。我们对辅助运动图表示的许多潜在好处感到兴奋。例如，在创作游戏的情况下，能查看布料运动的整个数据库可能是一个显着的优势。作为游戏制作检查的常规任务的一部分，预先计算的辅助布料动画云可以被手动查看，标记为重新模拟，甚至编辑。可以识别不良的辅助图形转换，而将人体组件添加到当前的工作则完全只需程序性的姿态相似性度量。这项检查工作的结果将是高质量的，计算代价低廉的交互式服装，这种服装已知不存在令人反感的人为因素。更一般地说，尽管将图形探索视为预计算是很自然的事情，但我们认为相空间采样是一个正在进行的过程，其改进结果可以不断被压缩并提供给交互系统。因此，相位空间探索不仅需要像数据驱动方法那样进行交互式回放，还可能由它触发并影响它自身。未来的在线虚拟世界可以在发现新行为时为客户提供新的辅助图。相反，玩家在虚拟环境中的行为可以指示相位空间中最重要的样本区域。我们相信通过大规模计算来增加互动环境有许多令人兴奋的可能性。