英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
引言
场景的可视化裁剪是交互式图形应用的关键阶段，当场景里具有数千个对象时显得尤为重要。裁剪的时间必须少，算法才能高效。场景的分层表示常用于高效的裁剪测试。然而，当存在较多的视锥体时（比如一个平铺显示墙），可视化裁剪的时间变得至关重要，并且不能通过将其与其他渲染阶段进行并行处理来隐藏它的影响。本文中，我们论述了将物体裁剪到分层组织的视锥体集合，例如在平铺显示和阴影体积计算中的对象。我们提出了一种自适应算法用以在裁剪过程中的每个阶段展开成双的层次。我们的算法从点的可见性开始进行计算，并且该算法是保守的。所需的预先计算是非常小的，这允许我们的方法也同样适用于动态场景。我们通过不同物体变量从一个场景裁剪成多个层次来展示算法的技术表现。我们还展示了动态场景的结果。
1.介绍
任何交互式图形应用程序都必须对场景进行可见性裁剪。我们的想法是将发送到渲染管道的几何图形限制为只有最终会成像的几何图形。剔除阶段最重要的是要快，才能有效；否则，裁剪算法取得的效率优化将被掩盖。层次场景结构是常被用来加快进程。 在大多数应用程序中，将包围盒分层裁剪到视锥体是快速和高效的。 Assarsson 等人.[1]描述了视锥体裁剪的数种优化调整方法。Bittner 等人.[2]利用时间相干性来最小化遮挡裁剪到视图中的遮挡查询的数量。
快速的视锥体裁剪对于同时渲染到多个视锥体尤为关键。（1）CAVE[3]是一个多显示的虚拟现实环境，它需要可见性裁剪到多个视锥体。（2）Hudson等人提出另一种使用多个视锥体的应用，它通过消除所有位于的视锥体阴影中由主要封堵器形成的物体来实现场景遮挡裁剪。（3)基于集群的平铺显示器需要对显示器中每个平铺块对应的多个视锥体进行快速剔除（图7）。（4）多投影显示系统[5]使用多个重叠视锥体对应于每个投影仪。（5）计算建筑环境的可见性还需要多个视锥体[6-8]。
任何真实世界的交互可视化应用程序通常都会处理数百万个三角形的场景。 场景图的空间层次结构大大减少了对可见性裁剪的检查次数。同样的，当视锥体的数量巨大时，很自然地会对它们进行分层处理。在最一般的情况下，我们想要将任何一般对象的层次结构裁剪到任何一般的视锥体分层结构。
在本文中，我们使用一种视锥体的分层表示法将场景连贯的裁剪到所有的视锥体中。我们的方法适应性地合并了两个层次结构——场景层次结构和视锥体层次结构——为可见性裁剪服务。 为此，我们提出了一种算法，它确定要遍历哪个层次结构和何时遍历。我们知道，明确这个决定对连贯的裁剪场景至多个视锥体重要而有效是第一项工作。在此，我们解决了将对象层次结构裁剪到平铺显示墙的的具体问题（图7）。我们的平铺显示墙使用了一定数量的商业系统至一个集群中，每个集群为其中一块供电。该系统使用场景图像（开放场景图像[10]）来表示大量的场景。网络带宽限制了可以传输的数据量，因此研究高效可视化裁剪方法是一个重大需求。平铺显示墙上的个别视锥体彼此有固定的排列，并且它们有一个共同的视点。 如此紧密的视锥体排列激发了我们的可视化裁剪算法执行既快速又具有弹性的连贯计算。 我们可以减少对UNC发电厂模型的分层版本的裁剪时间，在一块4times;4平铺显示器墙上，使用我们的自适应算法处理可以将使用传统方法约14ms的时间降低为约5ms。
我们的可见性裁剪算法执行基于点的可见性，而不同于其他几种剔除技术，它们的执行基于区域可见性[11，12]。 此外，我们的裁剪方法是保守的，而不同于其他概率或近似剔除技术[13-15]，它们可能会导致严重的渲染伪影。 这对于使用多个视锥体的应用程序至关重要。 例如，对于基于集群的平铺显示墙，需要最小化网络上的负载，而且其交互性需要被保留。裁剪决定了将要被缓存至渲染节点的几何体。近似剔除技术则导致概率预取，常常会导致渲染过程中的冻结。
我们展示了我们的可视化剔除算法的FatehpurSikri模型和UNC发电厂模型的实验结果。我们只关注对多个视锥体折的快速剔除，因此没有讨论渲染管道的后期阶段。 我们将不同的变体裁剪到多个视锥体的结果进行了比较。 我们还调查了我们的裁剪技术用于会有许多对象改变位置的动态场景时的性能。 这与在执行剔除之前更新许多节点的包围框的额外开销有关。
2.相关准备
可见性确定一直是计算机图形学[16]中的一个基本问题，因为场景的大小通常超过图形渲染能力。 Claudio等人.[17]和Durand 等人. [18]提出了全面的可视化评估方法。 视锥体裁剪算法避免渲染在视锥体以外的几何体。 层次化技术已经开始发展[19]，其他的相关优化也在进行[1，14]。Funkhouser等人.[20]介绍了第一个已发布了的可支持大于主存的模型的系统，该系统构筑于Tellerand Sequia[6]基于区域的可视化算法之上。Aliagaetnl.[12]描述了MMR，这是第一个以交互帧速率处理数千万个几何体模型的已发布系统，然而它却需要昂贵的高速多核心图形处理工作站。
Assarsson等人.[1]提出了几个优化的快速视锥体剔除方法，使用不同类型的包围盒和包围球。 为了进行八度的测试，他们把视锥体分成沿着每个坐标轴的一半，产生八个部分，就像八叉树的第一个细分。 对于物体使用包围球，就足以测试剔除包围球中心所在八度的外部三个平面外的物体。 这也可以扩展到一般的包围区[21]。 我们的锥体层次划分方法是由这种将视锥体细分为八度的想法引起的灵感。 然而Assarsson等人只对视锥体进行一次划分，而我们将这个过程完成用以构建一个完整的锥体层次结构。Bittner等人.[2]采用硬件遮挡查询技术，利用时间相干性，减少用于遮挡裁剪的CPU-GPU的档位。由于遮挡剔除信息对我们的平铺显示墙的特定情况下的所有锥体都有好处，因此不需要对每个锥体进行单独的遮挡剔除。
另一种观察遮挡关系的方法基于这样一个理论，即如果一个查看器在封堵器产生的阴影内，则无法看到封堵器。Hudson等人.[4]提出了一种办法 动态选择一组封堵器，并计算它们的阴影部分，用于剔除对象层次结构的包围盒。 Bittner等人.[22]改进了这种方法，他们将封堵器的阴影部分嵌入到遮挡树中。 这种方法比Hudson等人有优势。 因为后者的比较是在一棵树上进行的，而不是m个锥体上分别进行，从而将时间复杂度从O(Rn)优化到O(Logm)。我们的方法构建了一个视锥体树，类似于这种处理锥体的技术。 我们更进一步地将锥体层次结构与对象层次结构结合起来。
3.对象层次结构和锥体层次结构
在我们的剔除技术中，我们使用两个层次结构。 第一种是场景的空间层次结构，用场景图表示(OpenGL Per^rmes [23]，开放场景图[10])。 在对象层次结构（OH）中，每个节点都有一个包围区，使得内部节点的包围区完全包围其所有子节点的包围区。 只有叶节点包含实际的几何体。一个组织良好的场景图将有紧凑的几何体节点，以便包围区可以用来提供准确的可见性测试。
我们处理的第二个层次结构是视锥体（图1）。 我们的视锥体层次结构(FH)类似于BSP样的划分。在最普遍的情况下，一些独立的3D视锥体被分层次地分组在一起。 每个内部节点的包围区都包含它的子节点。 一个平面将每个内部节点的体积平分为包含其子节点的半个空间。 层次结构中的叶节点对应于单个视锥体。 根节点在锥体层次结构中对应于主要视锥体（见图1）。视锥体重叠的情况常被见于多投影显示，解决它的简单方法是将重叠区域作为额外的独立锥体。
4.对象层次结构和锥体层次结构的自适应遍历
理想的遍历OH和FH是优化性能的关键。 所需的预处理步骤在4.1节中讨论。 在第4.2节中，我们首先讨论了几种层次结构的便利方法，然后提出我们的自适应算法。
4.1预处理
定向包围盒(OBB)给出了空间中几何体和方向的紧凑表示。 最好只对OBB进行裁剪，而不是整个几何体，因为它既快又保守。在预处理阶段，场景图被加载到主存储器中。对于一组三维点，它们的特征向量表示它们的方向。 因此，在OH的叶节点，几何点的特征向量提供定向包围盒。但是在内部节点，我们只使用子节点的包围盒顶点来计算特征向量。 这是内部节点定向包围盒的快速近似计算。
一个锥体层次结构（FH）由内部节点构成。每个内部节点都有一个平分平面。由此计算的包围盒信息与场景图中的每个节点一起存储。
4.2锥体裁剪方法
我们的裁剪过程涉及到对主视锥体的第一级裁剪，以便完全消除视图之外的对象。 下一步是将这些n个对象分类为m个视锥体。一种简单的方法是用所有视锥体测试这些对象。 该方法的预期时间复杂度为O(rnn)。 我们现在来讨论其他几个分层方法与这种方法不同，然后是我们的自适应算法。
OH（不带FH）：这是一种常用的方法，其中场景图像分别被一个一个裁剪至所有的视锥体。它不利用任何锥体的层次排列结构。因此，在有大量的视锥体时该方法显得捉襟见肘。其平均时间复杂度为O(mlogn)
FH（不带OH）：如果只利用了锥体层次结构，每个物体都必须对它进行测试，并且要从根节点的物体开始。对于FH中的每个内部节点，如果一个物体完全存在于它的平分平面一侧，它的能见度可以被安全地从位于平分平面另一侧的空间的所有锥体中剔除。因此，我们可以在层次结构的每个节点上消除一半数量的锥体。因此，平均情况时间复杂度为O(nlogm)。
自适应OH和FH：在上述两种情况下，两种层次结构(OH和FH)相互独立使用，即。 当OH被遍历时，锥体是被非分层次处理，而当FH被遍历时，对象被非分层处理。因此，两个层次的自适应合并会导致计算量大大减少。考虑下列不同的情况：
在OH的叶节点处，只有FH遍历保留。
在FH的叶节点处，只有OH遍历保留。
在所有内部节点上，决定是否进一步遍历FH或OH。
利用预处理阶段（第4.1节）存储的预先计算数据以达成上述决策判断。 如果OH-节点不与FH-节点的平分平面相交，锥体层次结构应进一步展开，保持OH不变。在这展开OH会导致在下一次迭代时需要处理大量的OH节点。在下一次迭代中。 如果FH节点的平分平面与OH-节点的包围盒相交，则应该展开OH-节点，从而使物体裁剪成它的部分。我们把子节点分为三组(L=Left，C=Cuts，R=Right)取决于其分别位于FH节点的平分平面的位置。 L组包含所有完全位于负半空间中的子节点，R组包含位于正半空间的子节点，C组包含其余的子节点（被平分平面切割的对象）。
对于每个确定在主节点中是可见的节点OH_Node，算法adaptive_OHandFH_Cull(OH_Node，FH_root)（算法2）是其调用，其中FH_root是FH的根。ClassifyLCR()是可选功能，它将OH_Node的子节点按照它们分别相对于FH节点的平分平面的位置，将他们的子节点分为L、C和R。 算法将L和R中的成员恢复到相应的子锥体（算法2：第11，14行），而C的成员被恢复到两个子锥体中（算法2：第7-8行）。 当FH遍历完成时， 剩余对象被标记为在相应的视锥体中可见。 在集合C中的物体，需要用两个半空间分别进行检查。但是，对于集合L和R中的对象，需要考虑的锥体已经减少一半，从而有可能使计算量减半。要处理的子节点数可能会增加，因为classifyLCR() 分解一个OH节点到它的子节点。在这个阶段，有两种选择。我们可以独立地把每个物体都搬进来，或者可以将集合L和R中的对象重新组合为伪组。 这将涉及重新计算伪组的包围盒。 伪群在场景图中不存在，但可以减少更进一步阶段的计算量。我们的实验表明这种重组只对具有很高分支因子的场景图有利。否则，形成伪组的开销会掩盖所获得的增益。注意，伪组在算法2中没有涉及。
图2. 对象的层次结构如图可见为2times;2平铺排列的视锥体。对象被分组显示。 F1、F2、F3和F4表示视锥体。 他们的自适应裁剪在图3中显示。
图3. 图2中场景结构的自适应剔除。 物体和锥体层次结构与已经确定的可见性列表一起显示。 工作节点显示为光灰色。暗灰色的对象 CTS是需要进一步研究的。(a)OH的根节点按FH根节点的平分平面分类。 L，C，R的分类显示在图中。(b)继续对C几何进行裁剪。(c)继续对L集合进行裁剪。(d)继续对R集合进行裁剪。
该算法也可以很容易地处理动态场景，因为预处理阶段只涉及开销较低的特征向量计算。 可见性决策保持不变。 另外，算法执行时存储的额外数据很少。 请注意，在算法2中可以使用平面进行二分用于应用程序，如平铺显示墙，因为平铺块的大小是统一的，并且锥体空间最终会被分割成独立的平铺锥体。
这可能不适用于不均匀的平铺块。 然而，仍然可以建立锥体层次结构。 只是在这种情况下，在算法2第2行的末端锥体还将在标记对象可见之前检查其可见性。
5.实验结果
最坏的情况；典型的演练效果更好。 我们的自适应算法（算法2）在整个演练过程中花费的时间最少。 随后是不带OH的FH方法。不带FH的OH方法比这两种方法都差。
图4. 各种方法的计算性能。 时间越低越好。在整个演练过程中，我们的自适应算法几乎优于其他算法
图4(B)显示了在发电厂模型上演练的剔除时间。 图4(A)中不带FH的OH方法和不带OH的FH方法的图解是一致的，而不是不带FH的OH的性能滞后。这是因为OH中的高分支因子使不带FH的OH方法效果更显著。 但是， 自适应算法性能显著比所有其他方法都要好。
图 5. Fatehpur Sikri模型的裁剪测量性表现
我们分别对平铺显示墙的不同配置的平铺块尺寸进行了可伸缩性测试。 图5显示了我们的自适应算法对11000帧的Fatehpur Sikri模型的演练。该算法平均需要11ms才能裁剪到8x8配置中，从而使裁剪适用于设置此类配置的显示墙。 然而裁剪时间限制了在服务器管理的显示墙（如我们的(图7，[9]）上可以达到的总体帧速率，其中渲染是由客户端机器完成的，数据传输可以与下一帧的裁剪平
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235603]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
