英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
大型遮挡体模型的实时遮挡剔除
SATYAN COORG，SETH TELLER
计算机图形组
MIT计算机实验室
摘要
有效识别动态合成视图中可见的多边形是计算机图形学中的一个重要问题。通常，能见度测定使用z-buffer算法进行。由于该算法必须检查输入的场景中的每个三角形，z缓冲占用图形处理过程中巨大的部分，特别是在性能较低的架构上或者软件z-buffer。
避免不必要地处理场景中不可见部分的一种方法是使用遮挡剔除算法在图形管道中早期丢弃不可见的多边形。在本文中，我们利用在城市和建筑模型存在大的遮挡体设计实时的遮挡剔除算法。我们的算法具有以下特点：它是保守的，即，它高估的可见多边形的集合；它利用空间的连贯性通过使用分层数据结构；并利用时间相干性，通过重用以前的视角计算能见度信息。新算法显著加速了几个复杂测试模型的呈现。
CR分类和主题描述：1.3.3 [计算机图形学]：三维图形和现实可见的线/面算法；1.3.7 [图形]：计算几何和对象建模–对象层次结构。
附加关键字：保守可见性、时间相干性、空间相干性、KD树
1 介绍
识别可见多边形或消除隐藏多边形是高效场景绘制算法的一个重要组成部分。尽管高性能缓冲硬件的可用性，图形的机器有一个显着部分较小或没有硬件Z-缓冲能力。软件缓冲（例如，个人电脑），可以看作是渲染瓶颈。此外，在许多架构，测试时其他图形处理后（例如，阴影，纹理映射），浪费计算在看不见的部分。
解决这个问题的一种方法是开发的遮挡剔除算法，有效地识别，然后渲染，只有可见光部分的模型或一个紧密界超集方法。在本文中，我们利用典型的建筑或城市模型的大型遮挡体下设计了一个实时的遮挡剔除算法。
我们的算法是基于几个想法。首先，我们提出了一个简单的（快速）能见度测试确定该模型的一些地区完全或部分遮挡的一组遮挡体。第二，我们描述了一个便宜的预处理步骤，确定所有视角附近大遮挡体。最后，层次可见性算法反复应用可见性测试来确定空间层次中树节点的状态。
相关工作
给定一个三维模型和视点，精确可见性算法[ 12, 14 ]用可见多边形片段计算图像的描述。一旦有这样的描述，进一步的处理CM被限制只涉及场景的可见部分。然而，这些技术往往是复杂的，因此很难在交互式应用程序中使用。相反，Z-Buffer算法[ 4 ]，通常在硬件实现[ 2 ]，应用广泛。
给出了硬件Z-的可用性，它似乎有前途的高估可见的多边形，然后使用Z-缓冲渲染最终图像。这种高估或保守的能见度已利用快速设计建筑漫游系统[ 1, 6, 10，15 ]，在[ 15 ]的思想是把输入模式进入细胞，大致对应的房间在一楼，并用细胞/眼细胞可见结合精确能见度从上面，虽然这方法消除了大部分不可见的多边形建筑模型，对模型的泛化与不太明显的细胞结构（例如，城市模型）出现困难。
使用基于八叉树的空间细分方法[7]只渲染位于视锥内的多边形。然而，该算法不利用模型的任何遮挡特性。
层次Z-Buffer算法[ 9 ]挑选一个八叉树层次结构节点采用z-pyramid解决可见性查询。虽然这是一种很有前途的实现遮挡剔除与硬件支持的方法，很难实现对当前的图形架构这一算法，可见性查询中不支持的硬件和软件模拟顶向下的Z金字塔需要很大的开销。由于它依赖于图像空间查询，所以该算法也容易受到混叠伪影（虽然伴随着复杂性的增加，可以避免混叠（8））。
动态时间一致性保守可见性算法，在[ 5 ]中描述，标识相关可见性事件，即，在不久的将来将发生的可见性变化。该算法的一个缺点是，它必须重建连续的序列之间的连续的序列的可见性信息之间的每一对离散的假设由移动观察员假定。
最后，[ 11, 13, 16 ]提出的最近算法通过纹理映射逼近多边形集合加速绘制。只有在计算与一组多边形相对应的纹理近似时，可见性才能得到解决。这些纹理用于渲染许多帧，从而减少了进一步的可见性处理。纹理近似通常是最有效的遥远的多边形，因为他们的图像从一个角度到下一个变化不大。相反，遮挡剔除可以消除邻近的（不可见的）多边形。
算法概述
我们假设输入模型是一个凸多边形的静态集合，每个多边形中的顶点数是由一定的常数所限定的。我们的系统使用一个预处理步骤合并相同的输入顶点。这对于识别共享边缘的多边形非常有用。我们不假设观测器运动的先验知识。
我们的算法选择一个小的遮挡体，稍后将用于剔除。这种策略的动机是观察到在许多有趣的模型中，大多数遮挡是由几个多边形引起的（从任何瞬时的视角）。最重要的是，遮挡体的动态选择，随着角度的变化，使多边形通常作为遮挡物附近的视角，但作为非遮挡体（被剔除对象）远程或斜角度（图1）。通常，这非遮挡体不仅仅是一个单一的多边形，但凸空间区域（例如，一个层次包围盒）包含许多多边形。
图1: 遮挡体多边形和非遮挡体在一个瞬间的视角
论文的其余部分组织如下。2节描述了一个确定的一组一个非遮挡体保守的可见性状态算法。此测试是第3节中的动态算法中可见性Oracle的基础。第4节介绍了我们的算法的性能特点，第5节得出结论。
保守型可见性测试
本节讨论了以下问题：给定一个视角，一组凸遮挡体和凸非遮挡体，非遮挡体是否可见？就是说，不存在一个线段从视角上不符合遮挡体非遮挡体一点吗？我们回答这个问题，以支撑和分离平面的方法（图2）。两个凸多面体物体的分离面是由一个物体的边缘和另一个物体的顶点形成的平面，使得物体位于平面的相对侧。支撑面是相似的，除了两个物体位于平面的同一侧。
图2 : 这个图显示了两个维度的遮挡（三维的平面横截面）。
遮挡体A和非遮挡体T的支撑和分离面，是一个综合的视角。
考虑一个单一的遮挡体 A 和非遮挡体 T之间的相互作用（通常是一个包围盒）。这可以在遮挡体的支撑和分离平面的遮挡体和非遮挡体完全描述。首先，一个可以遮挡T只有视角在于一种不含T区可划分为三定性不同的区域如图所示的半空间。在区域1中，T不被A遮挡；在区域2中，T被A部分遮挡；在第3区域，T被A完全遮挡。
A和T的支撑和分离面可以用来检测这些箱子中的哪一个。首先，平面朝向遮挡体形成半空间。我们说，一个视角满足一个平面，它是在平面的正半空间内，这种关系可以用平面方程的视角来实现。当所有支撑平面满足时，即在支撑半空间的交叉处（区域3）相交时发生完全遮挡。当所有定向分离平面满足时，部分遮挡发生，但某些支撑平面不存在（区域2）。否则，没有遮挡（区域1）。
图3显示了由两连接遮挡体，即造成遮挡，两遮挡体共享一个边缘。如果这个视角是在阴影区域，T是由A和B共同作用的遮挡，即使独自遮挡。本例是由忽略支撑平面轮廓边缘通过非共享（例如，边缘E），两多边形相邻的E部分遮挡T.
图3:：连接遮挡体A,B的遮挡
请注意，只有当A和B位于E的对边时，才会发生遮挡现象，从视点上看，直观地说，只有当从视点看到遮挡体的轮廓边缘时，E才是相关的。图4显示了一个忽略E支撑平面（虚线）的情况，它会导致T被完全不正确地分类为完全遮挡。
图4: 这个图显示了支撑面穿过公共边不能被忽略
总的来说,如果一个遮挡体集合A1,hellip;,Ak共同遮挡了T:
- A1,hellip;,Ak 部分遮挡体了T,并且没有完全遮挡T
- 如果两个遮挡体Ai和Aj共同拥有一条边E,他们靠在边E的对面
- 所有平面的视角的符号距离，除了那些支持公共边的，都是正的。
上述算法实现简单给予支持和分离平面对应于一个单一的遮挡体和非遮挡体。第2.1节描述了一种有效的计算方法。
图5: 这个图显示了3D中的遮挡，从视图中可以看到。部分（一）显示遮挡体的轮廓连接在图像是凸的遮挡。（b）显示部分由连接遮挡体具有非凸轮廓遮挡。（C）显示部分由一组分离的遮挡体遮挡。
考虑图5，它描述了三种不同的遮挡情况。上述试验检测图5 （a）遮挡，作为支撑架通过“内部”的边缘被忽略，和非遮挡体完全依赖于图像中的凸轮廓。如果轮廓边缘形成非凸多边形，则保守可见性测试不能检测遮挡图5（b）。在这种情况下，测试失败的非遮挡体似乎“十字”线支撑在图像边缘E。最后，试验没有检测到由一组断开的遮挡体遮挡图5（c）。在实践中，我们发现这是建筑和城市模型的合理权衡，大部分遮挡是由于大遮挡体单独或作为一个组成部分。请注意，我们的能见度测试是保守的，即，它不会错误的将可见实体分类为被遮挡的。
计算支撑和分离平面
原则上，可以预先计算所有遮挡由遮挡体/ 非遮挡体对。然而，这将是浪费，因为只有一小部分这样的遮挡将被使用。相反，我们使用一种混合的方法，结合预处理和运行时的查表计算支持分离平面由（任意）遮挡器和轴向包围盒（一个遮挡）
图6: 切平面穿过一个多边形边E
我们限制分隔并支撑平面的遮光板/ 非遮挡体双切面的集合形成的非遮挡体遮挡体边缘和顶点（图6），而忽略那些由顶点和边非遮挡体遮挡体。仅装配这些平面提供完全遮挡的精确测试，以及部分遮挡的保守测试。用以下步骤计算每个遮挡边缘的切线顶点（并因此相切平面）：
- 平移非遮挡体的包围盒，原点是一个顶点的边缘。
- 确定从原点看见的包围盒的轮廓，使用基于盒子顶点的查表，如图7所示。
- 在原点的二维投影（沿着盒子的方向），遮挡体边缘投射到一个点上。从这一点到盒子的轮廓确定切线（图8）。作为切线保留在二维投影，2D中确定切点是3D的切点。
在2D中计算切线顶点是基于边缘投影相对于轮廓边缘位置的表查找。由于轮廓边缘的特殊性质（即，相对于原点的轴向边缘的投影），这种计算可以很容易地执行。
图8: 盒子相对于原点的投影（2D）。
相切顶点是由遮挡体边缘投影的位置决定的。
这种方法加快了支持和分离平面的计算，这是可见性测试的一个关键组成部分，比单纯的计算方法和通过包围盒的每一个顶点检查平面的方法要大一个数量级。
图9: 可见性算法
3 可见性算法
将可见性测试应用于所有可能的视觉交互（这可能消耗0（n2）资源，对于n个多边形）是昂贵的。相反，我们使用两种技术来减少执行的可见性测试的数量。首先，算法在一个分层的数据结构上运行：一个KD树[ 3 ]组织所有的模型多边形。其次，动态维护近处遮挡体用于确定遮挡（3.1节）。
给定一个KD树，可见性算法（图9）展现在KD树是不是由指定的遮挡物遮挡那些多边形。在该算法中，集合（T，OS）简单地收集从KD树节点T到达的所有多边形，并将它们合并到集合操作系统。TestOcclusion（S，T，P）决定不可见性状态在集合S，P看时就使用遮挡体，在2节中描述的算法。
可见性算法递归地应用保守可见性测试来确定每个KD树节点的可见性状态。首先，应用保守可见性测试来确定当前节点是否不可见。如果是这样的话，该算法将返回而不执行任何进一步的工作——扎根于当前节点的整个子树是遮挡的。如果失败，该算法递归的封堵器，部分遮挡的KD树的节点，因为只有这些遮挡体遮挡任何后代KD树节点。
复杂度
该算法的复杂度为O（kv），其中v是KD树访问节点的数量，k是遮挡物的数量。在最坏的情况下，这种复杂性是O（kn）如果算法测试所有KD树的节点对所有遮挡体。在实践中，复杂度较低，因为只有一小部分KD树节点对每个遮挡体进行测试（详见第4节）。
图10: 针对单个遮挡体（0）和两个连续视点分类的KD树节点。
为了清晰起见，假定KD树中的细分发生在每个KD树节点的中心。
空间相干性
图10显示了在对单个遮挡体和两个连续视图进行分级可见性分级时访问的KD树节点。注意，使用层次结构通过避免对完全遮挡的节点（例如，节点1）或完全可见的节点（如节点2）的进一步测试来利用空间相干性。
时间相干性
对于移动观察者，该算法在每次访问的KD树节点缓存遮挡关系——支持和分离平面列表。当视点发生变化时，该算法只需检查已有的遮挡关系，更新那些可视属性改变的KD树节点。例如，在图10中，在黑暗的区域节点（例如，节点3）反对的遍历检查遮挡体。对于这样的节点，只需要在第一个视点上计算和确定其可见性状态所需的分离和支持平面，然后再重用。对应于节点的缓存条目保持到节点不再参与可见性计算（即，直到一个祖先节点完全遮挡或完全可见）为止。
视锥剔除
可以在直接调用可见性算法之前先检查KD树节点是否在视锥体内，从而可以直接将视锥剔除纳入算法中。然而，计算视野之外的节点的任何支持和分离平面仍然保留在缓存中，以便以后可以重用它们。
动态遮挡体挑选
该算法的描述保持每个树节点相对于固定设置遮挡物的状态。当视点移动时，它是以更新该遮挡体将包含这些多边形是“大”的形象至关重要，因此可能遮挡的模型中的很大一部分。同样，在外观尺寸上变小的多边形也应该从集合中弹出。
对于一个给定的位置的多边形遮挡潜在的一个简单的指标，它包含在那个位置的立体角。对立体角的合理估计量是
其中一个代表遮挡体的面积，N代表法向量，V代表观察方向，D代表从视点到遮挡体中心的向量（图11）。这种“区角”度量捕捉圆心的立体角的多边形的一些性质，使它成为一个有用的近似。首先，较大的多边形具有较大的面积角。其次，从视点的距离的平方面积的角落，如圆心角。第三，当视线方向D与遮挡体呈“正面”关系时，最大区域角出现，并与点积一起降低，因为遮挡体被倾斜地观察。而这个指标不同于立体角，它不考虑遮挡体的实际形状，这是很简单的计算，并作为识别大遮挡体附近的视角有用的启式。
lt;
全文共9997字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11943]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
