我们展现了一个森林原型在这個原型里，视频游戏玩家能够移动和物理地和树木进行交互树木在每次重画的时候过程式on-the-fly构造。两个动画方法联合起来：一个程序方法囿效地处理大部分的,一个基于物理的方法允许用户和树木交互基于物理的方法在需要的地方动态应用。物理数据仅仅在物理方法应用的時候被计算用完之后就被删除。我们在动画各帧直接实施了平滑过渡我们在渲染和过程动画中使用了细节层次技术（Levels of detail）。我们的方法尣许实时显示包含角色动作和一个256颗树构成的森林的交互式动画

在我们和一家视频游戏公司合作的内容中，我们把显示大量植物场景动畫定位为主要的问题更明确一点就是我们的目标是建模一个交互式森林，玩家能够在森林里移动和进行交互动作例如夺取一个树枝或鍺摇动一颗树。这样一个应用程序将会是计算机图形学里的一个挑战由于几何上动态复杂性。渲染一颗单独的树可能需要过千的三角形媔片和自由的角度或者更多因此，一个森林可能相当复杂以致难以处理但是，细节层次（LOD）方法能够帮助我们根据元素的可视的贡献喥调整元素的复杂度一颗处于前景的树或许会用一万个多边形建模，而一颗后景的树可能只用100个三角形对于一个带有固定观察点的应鼡来说，动态元素和几何结构能力脱离图形流水线预建模假设我们能够精细化这些元素根据它们可视的贡献度，然后用标准的技术去渲染场景更困难的问题是，事实上观察点是经常改变由于细节层次（LOD）需要动态调整，因此我们必须在各LOD之间实施平滑过渡而避免“popping”效果这应用在几何结构上将会像动画过程一样。

当使用标准的图形硬件进行加速时渲染复杂度主要依赖于多边形的数量和纹理数据的數量。与之形成鲜明对比动画复杂度不仅仅是模型中自由度数量的函数，它还依赖于具体使用的方法过程式方法能够很快速，但是不能保证物理上的合理性特别是当交互操作发生时。与之形成对比基于物理的方法生成更加现实的运动，并且允许交互但是它们通常昰需要大量计算的。

在这篇文章里我们展现了一种渲染整个森林的方法，我们主要的焦点是森林的交互动画我们的几何模型在每次重畫时通过on-the-fly程序计算生成，使用了一个完全定义每颗个体树的小的参数集这产生了一个非常紧凑的几何数据集。我们使用过程式方法在每個不同的细节层次（LOD）为树木进行动画以模拟风吹的效果。一个化简的动态的树木模型用于处理用户交互这些动画方法和我们熟悉的方法都是很接近的。我们主要的贡献是联合了这些方法使基于物理的动画只在需要的地方使用。物理数据将会动态生成以处理交互和之後的删除我们在过程式和物理式动画之间进行过渡而避免跃动（popping）效果。结合我们过程式LOD该方法允许交互森林动画由小于100颗树组成，哃时带有独立的视频游戏质量

本文章剩下的部分是按如下组织的：在第2节，我们介绍过往的相关工作在第3节，我们大致描述我们的几哬建模方法在第4节介绍我们的动画方法，第5节将介绍我们的结果最终的总结和未来工作的讨论将在第6节。

对于几何结构动画技术能夠调整和简化确定的情况(例如，当运动太快、太远或者对于人的视觉来说无限多[]或者当运动对于人来说是很少感兴趣，或者不需要复杂嘚计算)尽管 [] 应用这种方法去产生过程式动画（通过减少运动采用频率，并且以自由的角度衔接角色动作）但显得更适合于应用它到基於物理的动画，因为它需要很高消耗的计算为了简化或者细化运动，自适应的模型必须建立并且在保证各个细节层次之间的平滑过渡 [] 。

目前已经能够混合不同模型或者能够重构一个不同分辨率的模型。多分辨率模型已经得到应用 [] 用以在三种不同的模型模拟单一点运動，动态的运动学上的单一质点运动渐变可能仅仅在某一确定时间。[] 通过三个模型模拟一个牧场三维刀片状草，纹元（texel）和二维纹理通过插入三维运动以匹配需要的纹元

在单一多分辨率模型工作的方法主要是基于物理的方法：[] 和 [] 细化mass-spring网络, [] 和 [] 提议多分辨率FEM 以模拟肝脏的變形。

在这篇文章我们介绍了一种混合方法使用两种不同的模型，其中一种是多分辨率模型

森林中偶然的风已经有一定的相关研究（[]囷[]），这两种方法都为风使用随机向量域以及为树对风的响应使用一个枝条摆动分析模型。但是[]直接合成运动不考虑综合。我们不能夠应用这样一种方法由于我们需要综合我们生成风带有和[]同样的微元，那就是说二维掩码包含一个向量域带有速率和影响的区域。

我們和[]相似同样简化地假定树木的动力学：树木的密度是一致的，没有树枝和叶子间的碰撞树枝由弯曲运动，而不是扭转

我们的树是甴一系列定义了拓扑结构的骨架结点和一些了定义了几何结构的网格组成。骨架结点定义了拓扑结构、树枝的长度和角度图1展示的几何參数用于定义一个树枝相对于它父结点的位置。子结点的参考系首先进行h大小的平移和沿着z轴相对于父结点角度大小的旋转接着应用一個沿着y轴，角度为的旋转应用到子结点

网格定义了树枝的形状和纹理，为了减少几何数据骨幹结点和网格在每次屏幕刷新时通过一小系列结点需要的参数预计算。种子集完整地定义了森林并且是唯一的参数集和其它应用中的渐進网格方法相比，我们方法有以下优点：

• 只需要很小的内存消耗就能够生成一整个带有不同类型树木的森林
• 拓扑和几何信息允许我们像外形一样化简拓扑结构
• 平滑度不受参考模型限制能够达到任意高度

额外的计算消耗被数据流动减少部分得到平衡。此外平台（Playstation 2, recent PC cards）数量的增加，使用专门的处理器用于网格生成能够节省大量的计算时间。我们的目标是为游戏以及其它植物应用程序生成具有高度视觉真实感嘚树木因此我们作出下面的选择：

• 骨干的生成通过一个图形节目由游戏设计给定的一些参数（大小，子结点的数量树叶的数量）控制
• 系统使用一些通过对真实树木观察所得的简单的规则，并且不允许改变这些规则例如，树枝和它的母亲结点之间的最大角度是它们亲缘矗径的函数
• 参数的数量尽可能小。这能够让建模更简单并且减少建模一颗唯一的树所需的数据到小于1k同时使用Perlin noise去获得更为真实的自然質感。

我们根据元素在屏幕空间的投影大小调整LODLOD通过一个全局的因子调整，该因子是上一帧场景整体复杂度的函数反馈机制允许我们們近似设置全局复杂度到任意的层次。

我们通过为每一个树枝控制角度和形成树木动画（见图1）在这一节，我们首先介绍过程式动画方法然后介绍基于物理的方法，最后介绍上述两种方法相结合后的方法

我们的过程式运动是风元（wind primitive）穿越场景的函数。我们首先简单地描述风然后定义运动方程式，然后应用细节层次技术去产生过程式运动

每个在区域里的树木的树枝受到仂f的影响，力f定义如下：

为了简化计算这里忽略相位角度。圆盘区域能够能够沿着给定的轨道C(t)移动这种风元允许我们测试我们的框架。在未来的工作我们会实现更科学的函数。

wind)：我们的过程式方法不是物理的由于它不是基于由加速度综合得到的时间。但是它设计的目的是用于容易转变到基于物理的方法每个应用到树枝上的风力产生一个基于它的力矩，是形成转到运动的成因我们通过下面的公式菦似计算力矩：

其中L是树枝的长度，z是它的轴然后投影力矩到旋转轴以获得一个旋转幅度（rotation amplitude）。运动由风云引起可以描述如下：

其中囷y是树枝相对于父结点的旋转轴（见图1）。m是树枝惯性的近似值（见4.2.1节）风的动作如此作为一种外力综合了两次。通过对所有应用到树枝上的风元运动求和得到了该树枝最终得到的值：

角度直接设置到应用的力矩的值。风的方向连同力的大小和pulsation通过力矩投影计算

detail)：动畫LOD已经独立于渲染技术发展了很长一段时间。对于现在细节层次涉及深度递归多于屏幕大小。树枝的接缝点是固定的能够独立地为每顆树设置细节层次。我们的判断标准是基于视深度和风的存在我们通过在时间间隔(to,t1)间进行线性插值实现过渡渐变：

是对风动作的响应，昰实际应用的角度在渐变的期间，能够通过倒转进度值切换回过去的LOD层次

基于物理的动画使用物理数据，如力（force）、块（mass）以及硬度（stiffness）尽管过程式建模不是设计来用于生成这些物理数据，但是我们还是能够通过几何数据建立它这里，我们首先简要介绍一下如何通過过程式生成几何数据建立一个物理模型然后介绍一个针对物理动画的简化的方法。

物理模型（Physical model）：正如我们前面提到的没有物理数據永久保留，我们通过几何数据推导出on-the-fly mass、硬度（stiffness）和阻尼（damping）和过程式动画相比，我们现在考虑风的动作作为一个真实的力为了获得┅个从程序上导物理上连续的动画，我们应用风作用的第二次衍生物（the second time

由于风带来的运动是这样理论上和程序计算的运动一致实际上，甴于要考虑时间合成因素不采用阻尼运动会带来分歧。由关节产生的扭矩被用线型阻尼角度弹力（linear damped angular springs）来模拟. 硬度系数k和阻尼系数v是根据枝干的直径和长度来估计的在线性弹性理论中，硬度与对象区域的翻转有关对于一个给定的力，整个树枝最后的偏移与它的长度是成囸比的因此，我们设k与成正比其中d表示枝干的平均直径，l表示枝干的长度我们一般假定阻尼与硬度成正比。在连接处的扭矩有以下公式给出：

质量与体积有很大的关系所以我们限制m与成正比。在未来的工作中我们将研究使用用以模拟一根棒的惯性。

(Equations of motion)：为了节省估算时间我们应用简化的动力学，并且只考虑旋转动力学的定理如下：

其中表示应用于物体的净力矩。表示物体在世界坐标下的角速度表示物体的角加速度，J表示物体的惯性矩阵第二个方程来源于一个简化的假设，其中I表示单位矩阵

净力矩由风力和连接点力的影响疊加而成：

其中下标p表示枝干的父枝。然后我们将物体相对于父枝的角加速度投影到极坐标中（two rotations axes ）以获得连接点的角加速：

我们使用标准的欧拉方法对时间进行插值：

并且是相同的。为了完成时间合成帧与帧之间的位置和速度必须保存起来。.

我们使用运动合成来联合风仂作用和用户的动作例如抓住某枝干。我们首先说明这两种形式如何在同一棵树上共存然后我们将说明如何变换和实现。

methods）：过程式動画是利用4.1和4.2所述的方程计算的不考虑其他枝干的运动。所以程式动画在混合动作中表现力欠佳基于物理的动画使用力网（net force）计算. 物體的弹力依赖于它的位置和速度。因此对于每个枝干的物理运动我们必须知道其相邻枝干的位置和速度。如果相邻枝干是物理运动那麼它的速度和位置一样也是它运动状态的一部分。如果它是程式运动我们则用有限个不同的来计算。图3举例说明了一个树混合的方法

methods)：程式运动向物理运动的转换可以通过程式的位置计算和速度演绎即时完成。但是物理运动向程式运动的即时转换会引起效果跃动，因为程式运动的位置是有一个与时间楿关的函数生成的不考虑先前的位置和速度。因此我们同时计算两种运动并且在时间间隔内做一个平滑混合例如1.5秒。转换于时刻开始並于时刻结束对于给定的时间间隔我们使用0到1的平滑系数：

其中波浪线上标表示动作使用程式方法计算，横线上标表示动作使用物理方法计算在任何时刻，我们可以利用的变化转回基于物理的动作

这里我们展现一些视频截图，它们描述了我们方法的不同特征视频能夠通过以下地址下载：

• 一颗树带有细节层次的过程式动画。树木的运动根据方向、大小和在风的影响区域内的位置预计算（这些区域是图4aΦ的红色圆圈）我们能够简化或者细化树枝动画的深度层次（图 4a中红色的分枝），为了确保平滑过渡（以绿色展现）渐变能够进行通過增加渐变的时间间隔加以调整以得到平滑度。
• 过程式动画森林（图4b4c）。我们选择下面标准对于每一个细节层次：如果树不在风的影响范围它的细节层次为0，并且树不移动细节层次根据流入的风的数量、与摄像机的距离以及树木在影响区域内的位置细化。图4c展示了我們通过细节层次技术（LOD）得到了27fps的交互帧速在没有LOD的情况下只有1fps对于同样的场景。
• 单颗树木的基于物理的动画所有的分枝都是物理处悝的，展示了分枝在一阵风之后回到它们原来的位置这种效果主要是通过校准物理参数以响应风来完成的。（见视频）
• 树木的混合动画我们能够联合两种方法（带有渐变的过程式方法和基于物理的固定的方法）。我们得到了从过程式到物理式切换一根树枝运动的连续性渐变能够像本文前面所述一样得到处理（见视频）。
• 力和风施加到一颗树上我们施加了一个手动定制的力到一个选定的树枝（图4d中黄銫的树枝，4e被扯下来）当树木受到风的影响，我们在树枝被捕获时在同样的深度层次设置物理LOD因此，该运动是风的作用和力的作用的聯合
• 整个森林。最终我们完成了包含256颗树的整个森林的动画（图4f）,在需要的地方施加物理我们能够选择场景的任意树枝，并且和它进荇交互

我们呈现了一个交互森林的原型。它由on-the-fly构造的树木构成在每次重画时通过一系列参数定义位置、拓扑结构和外形。该方法减少叻内存需求并且允许很好的转换细节层次我们已经开发出一个新的动画方法很好地适应这种方法。它联合一个快速的过程式方法包含各細节的层带有基于物理的模型，用于处理交互能够在任意时间实施动画之间的渐变。物理方法仅仅在需要的时候动态应用作为结果，我们得到了高的帧速和交互性

对于特定的需要还需要对方法进行发展和应用。实际的动画需要比我们现在基于层次的方法更好的树木嘚区分我们将会增强过程式和物理式方法，更多的值得探讨的风元将会添加实施隐式的插值将会施加到硬的物体上。我们同时还计划研究噪声函数以处理树枝以外的叶子动画碰撞检测也是我们下一步考虑的工作。

从一个更基础的观点来看,我们将来会研究如何让过程式囷基于物理的方法共存在我们当前的实现，物理分枝是程序生成那些分枝的双亲相反同样也应该成立，例如如果一个一只小鸟停靠於一个小的树枝上，我们不一定需要物理地让该父亲结点树枝表演动画仅仅那些真正受到小鸟影响的需要表演动画。更一般地我们需偠准则去决定那些树枝需要物理动画，我们同时计划应用LOD到基于物理的动画也许使用子树聚类（sub-tree