使用HLOD对大型静态和动态环境进行快速显示
我们提出了一种算法和系统，用于使用层次化简化来加速显示大量静态和动态环境。给定一个几何数据集，我们使用场景图和图中每个节点的计算详细程度（LOD）表示它。我们对具有自动生成的详细层次（HLOD）层次的LOD进行了增强，以更高程度地简化了场景的整个分支的保真度。当对象移动时，我们通过逐步重新计算HLOD的子集来扩展算法，以处理一类动态环境。我们利用它们在系统中的HLOD场景图的属性，使用它们在指定的图像质量或目标帧速率模式下渲染环境。结果算法已作为名为SHAPE的系统的一部分实现。我们将在由数以百万计的多边形组成的复杂CAD环境中演示其性能。总体，
SHAPE可以在帧速率上实现相当大的加速，而图像质量的损失很小。
关键字：交互式显示，图形系统，空间数据结构，详细程度算法，CAD
计算机辅助设计和科学可视化应用程序会定期生成超出当前图形系统交互式可视化功能的复杂模型。如今，大型几何数据库包含数十个或数百个基元，而典型的高端硬件目前只能以交互帧率显示几百万个。已经提出了几种减少渲染多边形数量的加速技术。一种是预先计算给定对象或环境部分的不同详细程度（LOD）。在运行时，在渲染每个帧之前，先选择要显示的合适的LOD，以便将较粗的近似值用于距离更远或对场景贡献较小的对象。除了静态环境之外，我们还对处理大型动态场景感兴趣，这在大型组件的设计评估中很常见，其中设计者会移动，添加，删除零件。
动态环境的其他示例包括带有动画人物的动画场景，基于仿真的设计，驾驶模拟器，战场可视化，城市环境可视化以及娱乐软件。所有这些应用程序都需要通过编程的行为或交互操作来移动对象。因此，希望渲染系统能够显示动态环境以及静态环境，
以交互式帧速率。
在过去的几年中，计算LOD一直处于活跃的研究领域。 大多数较早的算法都集中在场景中对象的单独LOD的计算上。
许多研究人员还提出了一些技术来加速使用潜在可见集的大型环境的渲染。
（PVS），基于图像的表示形式（例如纹理贴图基元，基于点的采样），或基于视图的简化。 这些技术很少解决动态环境。
1.1 Main Results
这项研究的主要目标是设计一种高效且实用的方法，以分层的方式使用LOD，以实现大型环境的交互式可视化。在本文中，我们提出了一种基于层次化详细信息（HLOD）的新方法以及由此产生的系统，称为SHAPE，用于渲染大量数据集。 HLOD是对对象的层次聚合的详细程度概念的概括。与常规对象的LOD相比，HLOD是通过简化场景的单独部分来生成的，从而共同创建了更高的保真度和戏剧性的近似值。
对于动态环境，我们将增量HLOD重新计算为场景中的对象。我们描述了一种在共享内存多处理器图形系统上并行并行执行此计算的方法。在实践中，我们的方法可以有效地处理大型环境，并限制对象运动的数量，即从场景中移动，插入或删除相对较少的对象的场景。
使用详细级别的层次结构的概念不是新的。
Clark引入了对象的抽象概念和详细级别的层次结构[Clar76]。 Maciel和Shirley提出了使用冒名顶替者和元对象的建议，并使用基于图像的层次表示法渲染大型静态环境[Maci95]。 Erikson和Manocha [Erik98]用于简化的分层详细级别。 Hoppe展示了一个分层视图-
依赖的LOD方法适用于地形渲染[Hopp98]。
我们的贡献包括多种技术组合，可针对大型静态和动态场景自动创建和渲染几何LOD以及HLOD。一些关键功能包括：
·保真度：通过将对象分组以创建HLOD，我们在简化过程中合并了来自不同对象的多边形。这种合并提高了视觉效果的高，低，低
多边形数，近似值。
·自动生成：给定一个很大的环境，我们的算法可以自动计算场景图的HLOD，而无需用户干预。
·通用性：我们的方法适用于所有多边形环境，并且没有对拓扑信息或表示进行任何假设。
·效率：我们使用显示列表来渲染LOD和HLOD，
充分利用当前高端图形系统的性能。 HLOD重新计算算法还可以在高端图形计算机上使用多个处理器。
·灵活性：我们的HLOD场景图结构允许我们的系统以恒定的帧速率模式或图像保真度模式渲染。
对于静态环境，此方法所需的内存通常仅为原始模型的两倍，但对于动态场景而言，该内存可能是其中的六分之一。
1.2 Main Advantages of HLODs
传统的LOD生成方法只能一次在单个对象上运行，因此只能将特定对象的本地错误最小化。这些局部近似值的总误差通常比一次考虑所有所有对象产生的近似值大。 HLOD的生成是通过简化场景的各个单独部分来实现的，因此对于一组对象而言，其保真度通常要比由相同的主数字组成的一组LOD具有更高的保真度。必须渲染的原语数量与帧速率直接相关，因此可以通过以下两种方式来利用这种高品质的HLOD：通过相同的数量渲染相同的数量，并且只通过相同的数量和系统数量。在不降低帧率的情况下提高图像质量。 SHAPE以上述两种显示模式的形式将选择权提供给用户：
·图像质量模式：渲染为多个多边形，以达到指定的图像质量，无需花费多长时间。
·目标帧速率模式：对于给定的目标帧速率，
尽可能多地渲染多边形。
这些模式的组合使用户可以轻松地快速导航到感兴趣的点并查看高细节区域。
HLOD已作为SHAPE的一部分实施，并用于渲染数个巨大的环境，例如由1300万个三角形和一个三角形组成的功率工厂。
1.3 Organization
在本文的其余部分安排如下。 我们在第2节中对大型模型的对象简化和交互式显示进行了相关的工作。第3节介绍了我们的方法概述。 我们在第4节中介绍了我们的HLOD生成算法的详细信息，并在第5节中介绍了动态环境的扩展。第6节介绍了各种算法，性能，使用方法和使用情况。 我们总结了我们的结果和重点领域，以供将来在第8节中进行研究。
2 RELATED WORK
在本节中，我们简短地调查了与大型静态环境的对象简化和交互显示有关的先前工作。
2.1 Object Simplification
在最近的几年里，单个对象的生成LOD受到了极大的关注。 可以基于多个属性对不同的算法进行分类：是否保留拓扑，是否保留句柄的外观，是否假定输入模型是有效的网格，是否是近似的。 在计算LOD中使用的基础抽取操作包括顶点移除，边缘塌陷，面部塌陷，顶点聚类和顶点合并[Cohe96，Garl97，Hopp96，Ross93]。 由于篇幅所限，我们在这里不审查所有这些算法。 取而代之的是，我们请读者参考主题上其他现有的调查报告[例如Heck97，Lueb97，Erik00]。
2.2 Interactive Display of Large Static
Environments
还提出了许多用于在大型静态环境中进行交互式显示的技术。对象简化算法可以与适当的场景图层次结构结合起来[Clar76]。作为预计算的一部分，将为每个对象生成静态LOD。
然后在可视化期间，将视点用于剔除视锥中的层次结构的一部分，并为每个可见对象绘制合适的LOD。 [Schn94]在BRUSH中使用[Ross93]的顶点聚类算法来简化大量的大型CAD模型。 [Cohe96]通过在Performer场景图中的简化包络生成的LOD来渲染大型CAD模型。
Aliaga等[Ali99a]用于在MMR系统中由GAPS [Erik99]生成的静态LOD。
许多研究人员[例如，Hopp97，LE97，Xia97]都建议使用基于视图的简化来渲染大型单个对象或整个场景。这些算法可以在对象的各个表面上进行简化。它们将简化信息存储在折叠操作生成的顶点的分层树中，并在渲染时遍历此树。基于运行时使用的不同类型的选择性优化标准基于表面方向和屏幕空间投影误差[Hopp96，Hopp97]。
在[Erik98]中提出了用于大型静态和动态环境的交互式显示的使用详细层次结构层次的思想。其他类似的策略包括[Hopp98]，它描述了一种构建方法以及使用分层渐进式网格来显示大型地形数据集的方法，以及由TerraVista在多个系统中使用的经过专门设计的系统。用于更粗略表示法的地形图块[TERR]。用于渲染大型环境的其他技术包括遮挡剔除[Tell91，Gree93，Zhan97，Dura00]可以加速深度复杂环境的渲染。
许多研究人员已经提出了使用基于图像的表示[Maci95，Shad96，Scha96，Alia99b]来代替与纹理映射的原语或点样基于图像[Alia99a]组合遮挡剔除，多边形简化技术，和表示用于快速遥远几何显示大型静态数据集。
2.3 Frame Rate Regulation
在渲染时已经开发了几种技术来目标帧速率。 [Funk93]描述了一种交互式帧速率的自适应显示算法，该算法通过将其作为受限的优化问题来解决。 [Rohl94]用于保持目标帧速率的反馈循环。 [Maci95]将[Funk93]的预测框架扩展为分层版本，并用作纹理映射原语作为对象簇的冒名顶替者。
2.4 Dynamic Environments
尚未进行大量简化和显示大规模动态环境的研究。 IRIS Performer [Rohl94]使用传统的LOD技术，并且能够更改场景图的结构以反映运动。 许多研究人员提出了在对象进行运动时更新边界体积，层次结构，空间分区和场景图的技术[Torr90，Chry92，Suda96]。 [Dret97]提出了一种算法，可为带有移动对象的场景提供全局照明的交互式更新率。 [Zhan97]提出了一种适用于动态场景的遮挡剔除算法。 [Jeps95]描述了一种实时城市模拟的环境，该环境允许将动态对象包含在场景中。
3 OVERVIEW
在本节中，我们对HLOD方法进行了概述，并讨论了与SHAPE的设计和实现有关的问题。
我们讨论了视图依赖和静态LOD方法，场景表示以及在静态和动态环境中使用HLOD之间的权衡取舍。
3.1 Static LODs Versus View-Dependent
Simplification
几何详细级别已用于两种形式，以快速显示大环境：静态LOD和与视图相关的简化。这两种方法在不同情况下都可以使用。尽管依赖于视图的算法很优雅并且提供了有用的功能，但是它们在可视化过程中会带来大量的内存和处理器开销。代替选择每个可见对象的LOD，可以根据视图相关的算法查询每个可见对象的每个活动顶点[Hopp97，LE97，Xia97]。
此外，对象实例昂贵，因为每个实例必须包含其自己的活动顶点列表。另一个问题是，当前的高端图形计算机比即时模式的原语可以更快地渲染显示列表[OGL98]。现有的依赖于视图的算法是固有的立即模式，因此无法利用显示列表的优势。
给定我们对性能的重视，我们使用静态LOD和HLOD，并使用显示列表来渲染它们。当我们在不同的简化级别之间进行切换时，我们接受其在潜在的``爆裂''伪像方面的限制。在第4节中，我们描述了如何结合HLOD进行分区以有效地以离散的近似方式有效地实现视点相关的简化。
3.2 Scene Representation
我们用传统的场景图[Clar76，Rohl94，Cohe96]表示多边形环境，扩展为包括使用HLOD进行对象间简化。
图2显示了一个简单的2D场景图示例。包含文本的框表示节点，而黑色箭头表示转换。灰色箭头表示每个节点中包含的多边形表示形式。请注意，场景图中的几何不需要全部位于叶节点中。即使Torso是根根节点，也并非是叶子，它都包含多边形表示形式。 ``Arm''节点显示实例化：在两个模型中，Arm的单一表示在该模型中被实例化了两次。弧使用不同的变换以适合人体上不同位置的武器实例。同样适用于Hand模型，该模型也被实例化了两次。
3.3 Hierarchical Levels of Detail
传统的LOD代表环境场景图中单个节点的几何形状。 HLOD代表场景图的分支，或代表多个节点的多边形。 传统的LOD渲染系统会为场景中的每个对象或节点提供适当级别的详细信息。 由于场景图中的一个节点的HLOD值是该节点及其后代的近似值，因此，如果我们在场景图中遍历一个节点的HLOD，则无需查看其图2即可。
3.4 Dynamic Environments
我们假定场景图中每个节点内的多边形模型是静态的并且不可变形。我们的方法是根据场景中刚移动的物体在刚性环境中进行处理的。动态环境以场景图中的操作表示，例如添加节点和弧，删除节点以及弧，以及改变转换。对于由移动物体组成的场景，此最后操作是最常见的操作。
除了模型的复杂性之外，还通过场景中动态变化的数量来表征动态环境。我们重点介绍三种动态环境类别：
·全局连续运动：在这些环境中，几乎每个对象都处于运动状态。一些计算机游戏或地震模拟就是例子。
·局部连续运动：在某些环境中显示连续运动，但仅在场景的局部区域内。一个示例是在固定环境中摆动的摆锤。
·不常见的运动：这些环境通常是静态的，并根据动态活动的简短周期进行标点。一种设计和审查方案就是这种场景的一个例子。用户与对象进行交互，然后需要一些时间来检查结果，然后才能继续进行操作。
由于我们的环境是由刚性主体组成的，因此我们预计将对节点的LOD进行预先计算。该算法还可以为场景图中的中间节点预先计算所有的HLOD。
在动态环境中，场景图的结构发生变化。结果，某些HLOD可能不再有效，因此我们需要对其进行有效的重新计算。我们的算法以自下而上的方式递增地重新计算这些HLOD。
在以下情况下，我们的方法是目前最有效的方法
由于重新计算HLOD所需的时间通常为``不频繁运动''，因此其渲染场景的时间通常更大。结果是，
算法会异步执行这些计算。我们还并行处理了共享内存中的计算步骤
处理器图形系统。
4 HLOD GENERATION
在本节中，我们介绍了生成HLOD的详细方法。 HLOD是通过在场景图中的节点进行分层分组来生成的，并将它们简化在一起。 该算法还按空间对大型对象进行分区，以获取这些对象的有限的依赖于视图的渲染功能。 它在场景图中计算并存储每个节点的LOD和HLOD。
4.1 Basic Algorithm
我们将更细的多边形称为LOD或HLOD，更粗的多边形被称为LOD或HLOD。例如，在图2中，标记为HLOD 0的形状是最好的HLOD，而标记为HLOD 2的形状是最粗的。 HLOD生成算法使用LOD计算算法和分层聚类的组合。基本的LOD算法必须能够进行拓扑简化并组合不重叠或不相交的对象的集合。许多已知的拓扑简化算法都具有这些功能[Ross93，Schr97，Garl97，Popo97]。在SHAPE中，我们使用GAPS简化算法[Erik99]，因为它在一般性，保真度和运行时间之间提供了良好的平衡。在为场景图中的每个单个节点计算LOD之后，我们的算法将以层次，自底向上的方式计算HLOD。场景的HLOD计算如下：
·叶节点的HLOD与其LOD等效。
·通过简化其子节点中最粗的HLOD来计算其内部最粗的LOD，从而计算出内部节点的最佳HLOD。
·作为其最佳HLOD的连续简化，生成了一个内部节点的更粗HLOD。例如，在图2中，躯干中的HLOD由躯干的LOD 2和头部，手臂（左）和手臂（右）的HLOD 2组成。由于Head没有子节点，因此其HLOD与其LOD相同，但手臂的HLOD（未显示）是手臂和手的合并组合。
可能还有其他选择方式来计算HLOD。例如，可以通过直接简化HLOD表示的子树的所有原始几何形状来生成初始HLOD。在某些情况下，这会导致更高质量的HLOD;但是，从现有的LOD开始可以大大降低计算成本-这对于动态环境尤其重要-并且仍然可以带来高质量的大幅简化。
最后，每个HLOD都是完整的，简化的节点及其后代的表示。
4.2 Grouping Nodes
我们的方法需要每个环境的分层场景图表示。如果未提供，则SHAPE会使用分区创建一个（请参阅第4.3节）。相反，有时忽略忽略提供的场景图是有利的，因为并非所有场景图都针对渲染性能进行了优化。例如，
CAD模型通常通过功能而非接近来对对象进行分组。平面场景图存在类似的问题。两者都倾向于视锥平顶和HLOD创建效率低下。为了解决这些问题，我们使用分组来创建更多空间上一致的场景图。如果一个节点的孩子数超过两个，我们将使用八叉树空间分区来查找最近的邻居，并使用这些配对来创建具有更好空间一致性的层次结构。
这不仅有助于查看视锥，还可以产生更高质量的HLOD。
4.3 Partitioning Spatially Large Objects
由于我们使用静态LOD，因此在空间上较大的对象可能会引起问题。当查看器靠近空间较大的对象的任何区域时，必须以高细节渲染整个对象，即使部分对象可能离查看器很远也是如此。为了缓解此问题，我们对模型进行了分区以获取有限的视图依赖的渲染功能。我们简化了每个分区，同时通过对简化施加限制来保证我们不会在分区之间产生裂纹。最后，我们将这些分区的不受限制的多边形分层分组，并生成它们的HLOD近似值。最初在[Erik98]中描述了对大型几何对象的分区过程。
[Hopp98]描述了用于地形模型的类似方法。 [Avil97]还通过使用OBB边界体积层次结构对大型模型进行了分区以简化操作。
通过在大对象上放置统一的三维网格并确定每个分区内完全相同的多边形来进行分区简化。位于分区边界上的多边形被标记为受限制的（图3a）。下一个，
SHAPE分别简化了每个分区内不受限制的多边形（图3b）。我们不允许简化算法将在抽取操作（例如边缘折叠）过程中移动到限制多边形的任何顶点移动。
此限制保证算法不会在任何两个分区之间产生裂缝。我们简化了不受限制的几何结构，直到无法执行更多的抽取操作或算法超过了与LOD和HLOD相关的阈值偏差阈值为止。
当所有分区都被分别简化后，
SHAPE对其进行分层分组。将分区分组后，一些曾经标记为受限的多边形将变为非受限（图3c）。这样可以释放多边形，从而简化算法以执行更多的抽取操作，从而为此新的分区分层分组创建HLOD（图3d）。重复应用此分组和简化过程，直到只有一个分区包含所有剩余的多边形。由于该分区中包含所有剩余的多边形，因此没有更多限制，简化算法可以将这些多边形简化为任何目标数量。
一个人可以查看通过分区过程生成的HLOD，这表示与视图相关的简化的离散近似值。这样一来，它们在一个完全独立的，与视图相关的简化算法之间以及在与另一个与视图无关的静态LOD的一组集合之间占据了一个实用的位置。图4和5显示了分区结果。
使用HLOD可以使我们的算法从许多离散的样本中进行选择，以达到渲染速度和图像质量之间的平衡。由于每个分区均独立于其他分区进行了简化，因此可以在较低的详细信息中显示远距查看器的分区，而在靠近查看器的分区中则可以显示较高的细节（图4、5）。当距离查看器很近的几个分区距离很近时，它们会使用HLOD一起呈现。分区的另一个好处是，它允许我们对位于视锥范围之外的对象的部分进行视锥平视。此功能如图5所示。
5 DYNAMIC ENVIRONMENTS
在本节中，我们介绍了动态环境的方法。
我们的算法会根据环境中的动态变化来更新HLOD。它首先更新与受对象运动影响的HLOD相关的错误范围。然后，根据其空间接近程度在场景图中重新组合节点。最后，它以增量方式更新场景图的边界体积层次结构。修改场景图后，我们将需要重新计算其HLOD的节点插入到队列中。我们使用一个或多个简化过程从渲染过程中异步运行以计算HLOD。如果对象的运动相对较小，则可以接受使用先前创建的HLOD的渲染过程，同时等待简化过程以完成重新计算。
5.1 Updating the Scene Graph
我们的算法寻求在任何节点插入，删除或对象运动之后最小化必要的计算量。
幸运的是，在进行插入和删除操作时，要求重新计算的次数多于运动次数，通常很少。 我们首先介绍SHAPE方法，该方法用于在物体运动后更新HLOD，然后描述如何处理插入和删除。
5.1.1 Motion
我们的算法确定节点运动对HLOD准确性，节点重新分组的影响是基于对象的新位置，并更新边界卷的层次结构图。
5.1.1.1 Updating Error Bounds of HLODs
SHAPE测量对象的旧位置与新位置之间的距离，并将此距离添加到节点的HLOD的误差范围内。 由于此运动也会影响祖先节点的HLOD的误差范围，因此我们在场景图中传播距离误差。 HLOD的错误界限并不会自动消失，因为如果从更远的角度来看它们可能仍然是可接受的质量。
5.1.1.2 Regrouping Nodes
如第4.2节所述，当父节点的孩子数超过两个孩子时，我们会按层次对节点进行分组。通过根据这些孩子的空间接近程度对其进行分组，我们可以更高效地创建HLOD和查看视锥。随着对象在场景中移动，这些节点的相对位置也会发生变化。因此，以前有效的节点分组可能不再有效。
SHAPE通过重新组合这些节点来更新场景图。运动的程度会影响场景的工作量。如果节点移动的距离很小，则有时可能会在不更改场景图结构的情况下更新边界层级。如果节点移动的距离更大，则场景图的结构也会发生变化。该重组过程的示例如图6所示。
物体的移动导致HLOD的近似质量降低。但是，当重新组合节点时，某些HLOD会全部失效。由于重组场景图中节点的后代可能已更改，因此其HLOD不再是有效的近似值。我们将包含无效的HLOD的节点添加到简化队列中。它们仍然无效，直到简化过程可以重新计算HLOD。
在此期间，显示算法将为这些节点及其子节点提供非分层的LOD。
5.1.2 Insertion and Deletion
场景中节点的插入和删除无法有效地作为对象运动来处理。 如果插入或删除了一个节点，则我们使所有其祖先的HLOD失效。 此外，对于插入，我们还必须根据新场景中对象的位置重新组合节点。 插入和删除都可能导致绑定的层次结构也发生变化。 将具有无效HLOD的节点插入简化队列，以便重新计算其HLOD。
5.2 Asynchronous Simplification
场景中的节点移动会导致许多HLOD变为无效，因此必须重新计算。所需的多边形简化比渲染场景要花费更长的时间。为了防止渲染延迟，SHAPE可以在后台线程中异步运行简化过程。
SHAPE可以在多处理器计算机上使用多个异步简化过程以提高简化率。
简化过程的任务是将节点出队并为该节点重新计算一组HLOD。我们在运行时使用拓扑简化算法来更新在预处理中使用的这些HLOD。完成为节点创建一组HLOD后，将其复制到场景图中。渲染过程和简化过程之间的交互如图7所示。
我们通过使用三个信号量的组合来防止损坏场景图数据的多个过程。一根信号灯保护场景图;另一个保护节点上的HLOD，以及最终的信号灯控件控制对简化队列的访问。设计了简化过程以在很短的时间内锁定场景图和HLOD信号灯，从而优先考虑渲染过程。我们的算法适用于``不频繁运动''的环境，例如设计和审查场景。对象很少在这种情况下移动，因此通常可以在几秒钟内更新HLOD的简化过程。
通常情况下，用户只会操作当前观看位置附近的对象。由于渲染算法仅使用HLOD进行粗略近似，因此用户必须在与渲染算法保持一定距离的情况下使用渲染算法才能使用新的HLOD。在大多数情况下，简化过程将能够在这段时间内重新计算HLOD。
5.3 Analysis
在本节中，我们得出了一个粗略的衡量标准，以证明我们的算法可以以多少互动率处理动态变化。算法的性能由场景的复杂性，场景的高度，场景选择的简单性，
及其性能我们为我们的分析做出了一些假设并提出了一个模型：
·场景图：场景图中的每个父节点都有子级。场景图的高度为h，所有对象均位于叶节点处。因此，对于每个移动的对象，我们需要在场景图中重新计算h-1套HLOD。
最后，一个节点的多边形表示由v个顶点组成。
·运营成本：计算步骤的成本主要由简化算法执行的抽取操作决定。结果，我们忽略了更新HLOD错误边界，重新组合节点以及更新边界量层次结构的成本。
·简化算法：我们将顶点合并为抽取操作，并且可以每秒执行一次这样的操作。对于LOD以及HLOD计算，简化算法可以简化节点的多边形，直到保留v / r顶点为止。
·交互模式：算法无需经过几秒钟即可呈现新创建的HLOD。
让我们假设c≠r，并且我们使用单个简化过程。对于每个移动的对象，需要执行顶点合并的算法。此方程式是使用涉及合并的顶点数的几何级数导出的，以创建每个HLOD和在场景图中向上传播的顶点数。如果M≤ms，则能够在需要渲染之前重新计算受影响的HLOD的算法。
对于一个更具体的示例，假设我们尝试重新计算针对鱼雷式房间模型（如图10所示）的HLOD，该对象由356个对象，883、545个多边形，多边形，949个多边形组成。场景图每个节点平均有3.1个孩子，
它的HLOD降低比约为8.3，高度为7。
假设必须在10秒内重新计算HLOD，并且简化后的算法平均要按平均每秒650个顶点的合并次数执行650次顶点合并操作。然后，Torpedo Room模型的常数为：m≈650，s = 10，
c≈3.1，h = 7，v = 545949/356≈1534，和r≈8.3。将这些常量替换为上面的表达式会产生M≈803.由于803 = M≤ms = 6500，所以我们的算法应该可以在给定的时间限制内处理这种情况。
假设我们在场景中移动了n个对象。只要nM≤ms，我们的算法仍应在时间限制内重新计算HLOD。因此，我们的分析建议我们当前的实现方式应能够在移动8个对象后10秒内更新鱼雷式房间HLOD
（8×803 = 6424≤6500）。在实践中，我们的算法在移动了鱼雷室模型的8个零件之后，使用一个简化的过程花费了大约13秒来更新场景的HLOD。请注意，我们的估计依赖于m，c，v和r的近似值，并且忽略了更新场景图和访问信号量的成本。在[Erik00]中提供了更多有关分析的详细信息。
6 RENDERING MODES
在本节中，我们讨论了用于渲染包含LOD和HLOD的场景图的算法。 我们将首先介绍如何使用HLOD排除场景中的全部部分，然后详细说明图像质量和帧率目标模式。
6.1 Simplification Culling
我们假设使用多边形简化算法来生成LOD，并且能够生成LOOD，并且这些近似值必定会产生距离误差。此误差的度量是基于与原始对象的偏差近似的质量，并将其投影到视平面上以确定LOD或HLOD的屏幕空间误差。
使用仅包含LOD的传统场景图形，渲染节点涉及确定要用于该节点中包含的几何的LOD。如果屏幕空间错误小于用户指定的错误容忍度，则LOD可以充分代表节点的几何形状。呈现通过屏幕空间错误标准的最低LOD。对于节点的每个子节点，场景图的遍历是递归的。
将HLOD添加到场景图遍历的每个节点中。当遍历到达一个节点时，它首先确定是否可以呈现HLOD。像LOD一样，每个HLOD都有相关的最大距离误差。如果HLOD的预计屏幕空间误差小于当前的当前误差容限，则可以呈现该误差。该算法将提供满足屏幕空间错误标准且不遍历节点子级的任何子级的最低HLOD。这实际上是简化了筛选，因为通过替换一个更简单的表示法来淘汰了根植于节点的场景图。如果没有HLOD满足错误容忍度，我们选择一个LOD来重新发送该节点，然后递归遍历每个子节点。
6.2 Image Quality Mode
在此模式下，允许用户以最大屏幕空间偏差的方式指定所需的图像质量。 在渲染时，与每个LOD和HLOD关联的预计屏幕空间错误用于确定可接受的图像质量表示。 这是大多数LOD渲染算法的典型代表。 主要区别在于，如果HLOD的图像质量可以接受，则不需要遍历整个场景图的分支。
6.3 Target Frame Rate Mode
目标帧速率系统具有在用户指定的帧速率约束内呈现最佳图像的目标。 [Funk93，
Maci95]显示使用预测技术确定目标框架的速率是背包问题的各种变量。这两种算法都基于预先计算的系统性能，这些性能可能在运行期间不准确。 [Rohl94，Muel95]描述了对目标帧速率的反应性反馈循环，这意味着用来绘制先前帧的时间用于计算下一个图像的质量。由于存在潜在的振动和迟滞问题，因此必须采取对策来应对反馈循环。 HLOD使SHAPE能够结合预测性和反应性技术来实现目标帧速率。
像预测方案一样，SHAPE使用目标面部数量。此数字是对系统可以根据用户指定的帧速率约束渲染许多多边形的最佳猜测。但是，此数字会自动更新：如果我们无法在帧速率约束内渲染面部数量，
下一帧的目标面部数量减少了。该方法与以前的反馈方法之间的主要区别在于，以前的方法用于调整LOD质量设置的框架时间，而我们使用框架时间来调整预算。具有基于HLOD的场景图可以轻松地使用贪心的方案来满足任何这样的多边形预算，而无需重新分配场景的部分。仅使用质量设置可能会导致过度补偿并因此导致帧频振荡。
我们搜索场景图以确定将要渲染的面孔。我们的贪婪方法在每个步骤中使用最大的预计像素误差来优化节点。我们会重复执行此程序，直到进行任何细化为止，否则面孔总数将超过目标数目。具体来说，该算法从整个场景的根节点的最粗HLOD开始。它试图通过替换其子节点来优化具有最大屏幕空间错误的节点。如果替换节点将导致我们的算法要渲染的多边形数量多于目标对象的面孔数量，则不允许执行此操作。我们优化节点，直到无法替换更多节点为止。
在动态物体的情况下，某些HLOD可能会变得不准确。但是，这些近似值仍可以用于目标帧速率。较大的运动会导致某些HLOD失效。我们忽略场景图遍历期间的无效HLOD。在这种情况下，SHAPE可以渲染节点的LOD或停止遍历和渲染场景的不完全近似。
7 IMPLEMENTATION AND RESULTS
我们已经在包括两个大型CAD环境的不同模型上测试了我们的方法。第一个是13百万多边形的发电厂，第二个是82百万多边形的双鹰油轮。我们还显示了福特Bronco的一个模型，以证明HLOD的有效性。 Bunny和Sierra Terrain模型显示了分区的好处（请参阅第4.3节）。
兔子和地形模型都没有场景图层次结构。
SHAPE使用GAPS简化算法[Erik99]计算LOD以及HLOD。它基于[Garl97]提出的二次误差度量标准，并且在大型模型上运行良好。
其他候选人是基于顶点聚类[Ross93]和渐进式简单复合体[Popo97]的算法。根据我们的经验，GAPS在近似质量和执行速度之间提供了良好的平衡。平均而言，GAPS在具有300 MHz R12000处理器和16GB主内存的SGI Reality Monster上每秒执行650个顶点合并操作。
我们使用C ++，GLUT，GLUI和OpenGL实现了我们的系统。该代码当前可跨PC和SGI平台移植。
7.1 Preprocessing Time
表1显示了用于预处理选定测试模型的时间量。场景图中的对象或叶节点数量以及构成模型的三角形数量均显示在表中。请注意，在对对象进行分组并简化创建HLOD的过程中涉及一定量的开销。开销的数量取决于场景图的复杂度和组合的多边形数量以计算每个HLOD。还请注意，在Sierra Terrain模型上，HLOD创建花费的时间少于LOD创建时间。这种性能差异的原因是通过对地形模型进行划分，
简化算法最初可以独立地在地形模型的本地部分上工作。由于我们使用算法的性能表现，简化多边形的子集比简化所有多边形的子集要快。
7.2 Targeting Frame Rate
图8显示了在两种测试环境下目标帧速率模式的有效性，可接受的帧速率范围设置为每秒17到23帧之间。请注意，该算法对正在运行的计算机的规格一无所知。对于大多数时间，我们在每个模型中给出的方法都在可接受的范围内。但是，对于每个模型的每个查看路径，在多边形几何形状中都有尖锐的过渡，导致在这些区域中的尖峰变小或变高。我们的算法可以对这些变化做出快速反应，并在可接受的范围内带来帧速率。有时我们渲染的速度比目标帧速率快得多。在这种情况下，我们正在渲染模型的原始多边形，但是在视锥中，它们没有足够的形状来保持恒定的帧率。由于可以很容易地限制帧速率，因此不会出现此问题。
7.3 Memory Usage
对于静态场景，我们预先计算了一系列LOD或HLOD，它们分别由前一个LOD或HLOD的多边形数量的一半组成。这样，我们将算法的内存需求限制为原始环境的内存需求的两倍。使用显示列表表示所有LOD和HLOD。对于动态环境，我们在运行时通过合并来自不同节点的多边形几何来重新计算HLOD。无法从OpenGL显示列表访问此数据，因此，我们需要存储多边形几何表示的单独副本。除了这种额外的多边形几何，我们还存储了简化算法使用的所有数据结构。这包括GAPS算法[Erik99]使用的误差平方和网格连接。该数据通常是原始模型大小的3到4倍。总之，这意味着动态场景可能需要多达原始多边形几何图形六倍的内存。选择不同的简化算法以及由此产生的数据结构将影响我们系统的内存需求。
7.4 Visual Comparison
使用HLOD的主要好处是，它们为对象组提供了更高质量的急剧逼近。 仅使用LOD，对象组趋于以粗略近似分解或分解。 但是，通过结合使用LOD和HLOD，我们可以生成看起来更立体的逼真近似。 因为HLOD可以促进物体的紧密融合，所以它们在物体间距很小的场景中最有效。 大多数CAD环境都属于此类。 我们显示了Bronco（板1），电厂（板3），Double Eagle（板4）和鱼雷室（图10）环境的逼近度LOD和HLOD之间的视觉差异。 请注意，仅使用LOD时，这些场景的实体形状往往会受到影响。 通过将几个对象的几何形状合并为HLOD，我们可以在简化过程中更好地保留这些环境的总体形状和表面积。
7.5 Asynchronous Simplification
我们测试了并行算法的性能，以确定其可以有效处理的运动量。 为了执行测试，我们创建了一个简单的场景，该场景由一个根节点组成，该根节点具有多个多维数据集对象实例作为其子对象（如视频所示）。 我们使用不同数量的简化处理器测试了多个场景。 最初将多维数据集排列在3D网格中，然后将每个多维数据集从其原始位置移动随机距离（小于整个网格的边）。 移动完成后，简化处理器会重新计算场景的HLOD。 我们在具有31个300 MHz R12000处理器和16GB主内存的SGI Reality Monster上进行了这些测试。
这些时序测试的图形如图9所示。该数据表明，由于场景由更多移动的物体组成，因此使用更多简化处理器的好处增加了。理想情况下，随着使用更多处理器，我们期望线性加速。但是，测试案例表明SHAPE实现了亚线性加速。我们推测，应该归咎于开销成本，例如争用场景图中的数据，再加上相对较小的被测试场景。随着场景的变大，我们期望使用多个简化处理器的速度将接近线性。这些结果表明，当场景中移动大量对象时，使用多个处理器进行简化是最有益的。但是，在许多情况下，立方网格场景的HLOD的重新计算并不是实时发生的。对于中等动态复杂性的场景，例如具有512个移动多维数据集的环境，即使使用31个处理器，更新受影响的HLOD也要花费半分钟以上的时间。这种性能表明，我们的动态系统最适用于“不频繁运动”的环境，例如设计和审查场景。为了模拟现实环境中的设计和审查场景，我们允许用户选择和移动视图中的任何对象。在各种模型的可视化会话期间，我们更改了一些对象的位置（请参见图2和视频）。对于每个测试运行，我们使用4个简化过程。这些示例的HLOD重新计算的执行速度如表2所示。
7.6 Display Lists
我们发现使用显示列表的能力在许多情况下是SHAPE的优势。 但是，当场景图中的节点数量变得非常大时，显示列表所需的内存量可能会超过可用的显示列表缓存量。 此时，显示列表可能不再提高渲染速度。 在这些情况下，渲染程序可能会直接从管理显示缓存中受益。
8 CONCLUSION AND FUTURE WORK
我们提供了一个简单有效的系统，仅使用几何LOD和HLOD即可渲染非常大的静态和动态环境。 HLOD对场景图的整个分支起着较高保真度的逼近作用。生成HLOD的过程是完全自动的，这在处理大规模模型时很重要。对于动态环境，我们能够即时动态地重新计算HLOD，我们展示的这种方法在显示“不频繁运动”的场景中效果很好。我们的系统SHAPE提供了经验证据，表明HLOD方法可用于交互式显示大量几何图形。环境。我们的动态场景方法是迈向大规模模型演练中交互式处理任意对象运动的第一步。它不对物体运动做任何假设，并且对一类动态场景有效。此外，它可以自动使用图形系统上的多个处理器。广义上讲，大型模型显示系统需要解决三个问题：1.对太小或覆盖屏幕上像素太少的多边形使用近似值； 2.不渲染被遮挡的多边形； 3.确保生成的多边形位于主内存。 SHAPE仅处理这些问题中的第一个，并且似乎在大型环境中运行良好。在未来的工作中，我们希望解决其余两个问题。我们对将SHAPE的结果与遮挡剔除方法结合以解决第二个问题非常感兴趣。一种可能性是将HLOD用作分层封堵器。最后，我们想将它们与数据库和内存管理技术结合起来。对于大型模型，这还将缩短加载时间。在模型简化方面，我们希望探索HLOD重新计算并行化的其他方法，并探索减少内存和动态场景的核外运行时简化的途径。
9 ACKNOWLEDGEMENTS
电厂环境由James Close和Combustion Engineering，Inc.提供。Sierra地形模型由Herman Towles和Sun Microsystems提供。 Viewpoint and Division，Inc.允许我们使用Ford Bronco数据集。 Double Eagle车型由NNS的Rob Lisle，Bryan Marz和Jack Kanakaris提供。 我们也感谢UNC演练小组的成员进行了许多有益的讨论和支持。 我们的工作部分得到了ARO合同DAAD19-99-1-0162，NSF奖9876914，DOE ASCI资助，NIH国家研究资源中心奖2P41RR02170-13分子研究和显微镜交互图形学，ONR青年研究者奖， 以及NCAA毕业生，NSF毕业生和英特尔奖学金。
10 REFERENCES
[Alia99a] Aliaga, D., Cohen, J., Wilson, A., Baker, E., Zhang, H., Erikson, C., Hoff, K.,
Hudson, T., Stuerzlinger, W., Bastos, R., Whitton, M., Brooks, F., and Manocha, D.
"MMR: An Interactive Massive Model Rendering System Using Geometric and
Image-Based Acceleration," Symposium on Interactive 3D Graphics '99
Proceedings, 199-206, 237, 1999.
[Alia99b] Aliaga, D. and Lastra, A., “Automatic Image Placement to Provide a
Guaranteed Frame Rate,” Computer Graphics (SIGGRAPH 99 Proceedings), 307-
316, 1999.
[Avil97] Avila, L.S., and Schroeder, W., “Interactive Visualization of Aircraft and
Power Generation Engines,” IEEE Visualization ’97 Proceedings, 483-486, 1997.
[Chry92] Chrysanthou, Y., and Slater, M., “Computing Dynamic Changes to BSP
Trees,” Computer Graphics Forum (Eurographics ’92 Proceedings), 321-332, 1992.
[Clar76] Clark, J., “Hierarchical Geometric Models for Visible Surface Algorithms,”
Communications of the ACM, 547-554, 1976.
[Cohe96] Cohen, J., Varshney, A., Manocha, D., Turk, G., Weber, H., Agarwal, P.,
Brooks, F., and Wright, W., “Simplification Envelopes,” Computer Graphics
(SIGGRAPH 96 Proceedings), 119-128, 1996.
[Cohe98] Cohen, J., Olano, M. and Manocha, D., “Appearance Preserving
Simplification”, Computer Graphics (SIGGRAPH 98 Proceedings), pp. 115-122,
1998.
[Dret97] Drettakis, G. and Sillion, F., “Interactive Update of Global Illumination Using
a Line-Space Hierarchy”, Computer Graphics (SIGGRAPH 97 Proceedings), pp. 57-
64, 1997.
[Dura00] Durand, F., Drettakis, G., Thollot, J., Puech, C., “Conservative Visibility
Preprocessing using Extended Projections,” Computer Graphics (SIGGRAPH 00
Proceedings), 239-248, 2000.
[ElSa97] El-Sana, J., and Varshney, A., “Controlled Simplification of Genus for
Polygonal Models,” IEEE Visualization ’97 Proceedings, 403-410, 1997.
[Erik98] Erikson, C. and Manocha, D., “Simplification Culling of Large Static and
Dynamic Environments”, Technical Report TR98-009, Univeristy of North Carolina
at Chapel Hill, 1998.
[Erik99] Erikson, C., and Manocha, D. "GAPS: General and Automatic Polygonal
Simplification," Symposium on Interactive 3D Graphics '99 Proceedings, 79-88,
225, 1999.
[Erik00] Erikson, C., "Hierarchical Levels of Detail to Accelerate the Rendering of
Large Static and Dynamic Polygonal Environmants," PhD Dissertation, Department
of Computer Science, UNC Chapel Hil,, 2000.
[Funk93] Funkhouser, T., and Séquin, C., “Adaptive Display Algorithm for Interactive
Frame Rates During Visualization of Complex Virtual Environments,” Computer
Graphics (SIGGRAPH 93 Proceedings), 247-254, 1993.
[Garl97] Garland, M., and Heckbert, P., “Surface Simplification Using Quadric Error
Metrics,” Computer Graphics (SIGGRAPH 97 Proceedings), 209-216, 1997.
[Gree93] Greene, N., Kass, M., and Miller, G., “Hierarchical Z-Buffer Visibility,”
Computer Graphics (SIGGRAPH 93 Proceedings), 231-238, 1993.
[Heck97] Heckbert, P., and Garland, M., “Survey of Polygonal Surface Simplification
Algorithms,” Technical Report, Department of Computer Science, Carnegie Mellon
University 1997.
[Hopp96] Hoppe, H., “Progressive Meshes,” Computer Graphics (SIGGRAPH 96
Proceedings), 99-108, 1996.
[Hopp97] Hoppe, H., “View-Dependent Refinement of Progressive Meshes,”
Computer Graphics (SIGGRAPH 97 Proceedings), 189-198, 1997.
[Hopp98] Hoppe, H., “Smooth View-Dependent Level-of-Detail Control and its
Application to Terrain Rendering,” Proceedings IEEE Visualization ’98, 35-42,
1998.
[Jeps95] Jepson, W., Liggett, R and Friedman, S., “An Environment for Real-time
Urban Simulation”, ACM Symposium on Interactive 3D Graphics, pp. 165-166,
1995.
[Lind98] Lindstrom, P., and Turk,G., “Fast and Memory Efficient Polygonal
Simplification,” IEEE Visualization ’98 Proceedings, 279-286, 1998.
[Lind00] Lindstrom, P., “Out-of-core Simplification of Large Polygonal Models,”
Computer Graphics (SIGGRAPH 00 Proceedings), 259-262, July 2000.
[Low97] Low, K., and Tan, T., “Model Simplification Using Vertex-Clustering,”
Symposium on Interactive 3D Graphics ’97 Proceedings, 75-82, 1997.
[Lueb97] Luebke, D., “A Survey of Polygonal Simplification Algorithms,” UNC
Chapel Hill Computer Science Technical Report TR97-045, 1997.
[LE97] Luebke, D., and Erikson, C., “View-Dependent Simplification of Arbitrary
Polygonal Environments,” Computer Graphics (SIGGRAPH 97 Proceedings), 199-
208, 1997.
[Maci95] Maciel, P., and Shirley, P., “Visual Navigation of Large Environments Using
Textured Clusters,” Symposium on Interactive 3D Graphics ’95 Proceedings, 95-
102, 1995.
[Muel95] Mueller, C., “Architectures of Image Generators for Flight Simulators,” UNC
Chapel Hill Computer Science Technical Report TR95-015, 1995.
[OGL98] Advanced Graphics Programming Techniques Using OpenGL, ACM
SIGGRAPH Course Notes, Course #17, 1998.
[Popo97] Popovic, J., and Hoppe, H., “Progressive Simplicial Complexes,” Computer
Graphics (SIGGRAPH 97 Proceedings), 217-224, 1997.
[Rohl94] Rohlf, J., and Helman, J., “IRIS Performer: A High Performance
Multiprocessing Toolkit for Real-Time 3D Graphics,” Computer Graphics
(SIGGRAPH 94 Proceedings), 381-394, 1994
Ronf96] Ronfard, R., and Rossignac, J., “Full-range Approximation of Triangulated
Polyhedra,” Computer Graphics Forum (Eurographics ’96 Proceedings), 67-76,
1996.
[Ross93] Rossignac, J., and Borrel, P., “Multi-Resolution 3D Approximations for
Rendering Complex Scenes,” Geometric Modeling in Computer Graphics, 455-465,
1993.
[Scha96] Schaufler, G., and Stuerzlinger, W. “Three Dimensional Image Cache for
Virtual Reality,” Computer Graphics Forum (Eurographics ’96 Proceedings), 227-
235, 1996.
[Schn94] Schneider, B., Borrel, P., Menon, J., Mittleman, J., and Rossignac, J., “Brush
as a Walkthrough System for Architectural Models,” Fifth Eurographics Workshop
on Rendering, 389-399, 1994.
[Schr97] Schroeder, W., “A Topology Modifying Progressive Decimation Algorithm,”
IEEE Visualization ’97 Proceedings, 205-212, 1997.
[Shad96] Shade, J., Lischinski, D., Salesin, D., DeRose, T., and Snyder, J.,
“Hierarchical Image Caching for Accelerated Walkthroughs of Complex
Environments,” Computer Graphics (SIGGRAPH 96 Proceedings), 75-82, 1996.
[Suda96] Sudarsky, O., and Gotsman, C., “Output-Sensitive Visibility Algorithms for
Dynamic Scenes with Applications to Virtual Reality,” Computer Graphics Forum
(Eurographics ’96 Proceedings), 249-258, 1996.
[Tell91] Teller, S., and Séquin, C., “Visibility Preprocessing for Interactive
Walkthroughs,” Computer Graphics (SIGGRAPH 91 Proceedings), 61-69, 1991.
[TERR] Terrain Experts, Inc. http://www.terrex.com.
[Torr90] Torres, E., “Optimization of the Binary Space Partitioning Algorithm (BSP)
for the Visualization of Dynamic Scenes,” Computer Graphics Forum (Eurographics
’90 Proceedings), 507-518, 1990.
[Xia97] Xia, J., El-Sana, J., Varshney, A., “Adaptive Real-Time Level-of-DetailBased-Rendering for Polygonal Models,” IEEE Transactions on Visualization and
Computer Graphics, 171-183, 1997.
[Zhan97] Zhang, H., Manocha, D., Hudson, T. and Hoff, K., “Visibility Culling using
Hierarchical Occlusion Maps,” Computer Graphics (SIGGRAPH 97 Proceedings),
77-88, 1997.