一种大规模三维场景的新型可见性生成方法

摘要

本发明公开了一种大规模三维场景的新型可见性生成方法。本方法为：1)构建待处理三维场景的层次包围盒结构；2)将包含该三维场景的三维空间按照空间特征剖分成若干互不重叠的单元view？cell，得到一层次树；3)对该三维空间中采样射线计算出每个单元对应的PVS和QPVS；4)并开始三维场景的漫游，根据当前视点的位置，找到层次树中所在单元；将该单元的PVS和QPVS分别处理，判断出利用QPVS所构建出队列中的物体的可见性，并相应地更新PVS信息，自底向上更新三维空间层次树中所有层次view？cell的PVS和QPVS信息，直至漫游过程结束。

说明书

技术领域

本发明涉及一种大规模三维场景的新型可见性计算方法。属于虚拟现实、三维计算 机图形与可视化、计算机软件技术领域。

背景技术

大规模三维场景的可见性(visibility)分析是海量三维场景管理、组织与绘制的重要组成部 分。通过相关可见性的分析与计算可以裁减掉场景中绝大多数不可见的部分，避免场景内部 完全暴力的可见性计算方法。可见性分析算法通常会计算得到一个潜在可见集合(Potential VisibleSet,PVS)，PVS是三维场景中所有物体集合的一个子集，是用算法估算出的一个可见 物体及其可见表面的集合。实际在线漫游浏览三维场景时，需要绘制的并不是三维场景中的 所有物体，而是出现在该PVS集合中的物体及其表面。如此，可以大大减少需要进行三维场 景仿真与绘制的数据总量。

因此，如何更加快速地计算得到PVS，并且使PVS尽可能地接近实际精确的可见物体的 集合，是可见性分析与计算的根本任务。

可见性分析与计算得到的结果分为两种类型：保守可见性(conservative)和近似可见性 (approximate)。如果通过可见性计算得到的是保守可见集合，则它至少包含了所有的可见物 体，同时还会保留一些多余的但实际并不可见的物体。利用该类型可见性信息进行绘制时可 以保证绘制结果的准确性，但会牺牲一定的绘制速度；如果得到的是近似可见集合 (approximatevisibilityset)，则该集合只是精确可见集合(exactvisibleset)的一个部分，它不能 保证包含所有的可见物体，利用该类型可见性信息进行绘制时不能保证绘制的结果的准确性。 为了能够计算获得近似可见集合，两种类型的方法常被采用:采样方法(sampling)和激进方法 (aggressivemethod)。采样方法利用随机的或者制定好的采样策略来估算可见集合，期望得到 的结果尽量不错过可见物体，此方法牺牲了结果的准确性，换来了实施方法的速度和方便性。 而激进方法(aggressivemethod)则基于与计算保守可见性类似的方法，只是在处理可见性的过 程中，对于那些被评估具有可见的可能性不大的物体或对图像贡献较小的物体，则直接忽略 并被视为不可见。只有在对三维场景计算与图像质量的要求较低的情况下，才能够使用上述 近似可见性(approximate)的计算算法。

可见性计算的算法按照计算空间的划分主要分为两大类：基于点的方法(from-point)和基 于区域的方法(from-region)。from-point类型的算法是基于当前视点的某个精确位置进行可见 性的计算，而from-region的算法则是为视点所处的空间区域范围计算在该范围内可能看见物 体的集合。from-region算法优点在于其区域的有效性和方便预取，由于计算出的PVS对于一 个区域范围之内(即观察单元，viewcell)都是有效的，也就是对三维场景进行虚拟漫游时视点 位于该区域范围之内的连续帧都使用这个PVS进行绘制而无需更换待绘制的内容；与此同时， 当视点处于某一个viewcell中时，可以很方便的将相邻的viewcell的可见集合提前取到内存 中做好数据准备以便于后续绘制使用。

from-point的代表性算法中如下文所述。

可见性计算的核心是遮挡的判断，为了加快判断某个物体是否被遮挡的速度，hierarchical occlusionmap通过在线层次遮挡关系的构建(HansongZhang,DineshManocha,ThomasHudson, andKennethE.HoffIII.Visibilitycullingusinghierarchicalocclusionmaps.InSIGGRAPH’97, pages77–88,August1997.)，加快遮挡判断的速度。尔后，显卡也为用户提供了进行遮挡查询 的接口(API)，判断一个物体是否被遮挡变得非常简单，不需要动手编写程序建立buffer，只 需要通过API发送查询的命令即可。Coherenthierarchicalculling(Bittner,J.,M.Wimmer,H. Piringer,andW.Purgathofer.2004."CoherentHierarchicalCulling:HardwareOcclusionQueries MadeUseful."ComputerGraphicsForum(ProceedingsofEurographics2004)23(3),pp.615–624.) 和nearoptimalhierarchicalculling(MichaelGuthe,Balázs,andReinhardKlein.Near OptimalHierarchicalCulling:PerformanceDrivenUseofHardwareOcclusionQueries.In proceedingsofEurographicsSymposiumonRendering2006,TheEurographicsAssociation,June 2006)两篇文献讨论了如何有效的利用这一接口，加快可见性剔除(visibilityculling)速度。

除此之外，FastV:From-pointVisibilityCullingonComplexModels(A.Chandak,L.Antani,M. Taylor,andD.Manocha.Fastv:From-pointvisibilitycullingoncomplexmodels.Eurographics SymposiumonRendering,2009.)提出一种较新颖的方法。它将空间切分成小块的观察视域体 (viewfrustum)，然后为每块空间找到最近的遮挡面片，接着进行遮挡融合(occlusionfusion), 该方法可并行度高。

From-point类的场景可见性计算算法按照前述可见性结果为依据分为三类，激进策略 aggressive、保守策略conservative和准确exact的算法。激进Aggressive的算法得到的PVS 是EVS(exactvisibleset)的子集，会造成一定的误差，因此在误差比较小或者对于图像质量要 求不高的情况下该算法适用。

关于conservative算法，在ASurveyofVisibilityforWalkthroughApplications(D.Cohen-Or, Y.Chrysanthou,andC.Silva.Asurveyofvisibilityforwalkthroughapplications.SIGGRAPH CourseNotes#30,2001.)中论述了利用occlusionfusion实现的算法，或者利用extended projection，即扩大物体的投影面积进行裁剪而实现的算法，还有利用虚拟遮挡物(virtual occluder,对于某个viewcell中的任何一点，该物体都被完全遮挡，因此可以利用它作为遮挡 物)进行裁剪的方法。

Exact算法是指通过算法直接得到最精确的可见物体的集合，这个问题处理起来极为复杂， 理论上的精确可见性采用aspectgraph理论和方法，其计算复杂度最坏情况为O(n⁹)，其中n 为三维场景中面片的复杂度，这几乎是不可能实现的任务。因此Exact类算法只具有理论分 析意义，而不具备任何实用价值。

from-region类可见性方法对三维场景最具有实用价值。该方法有一个重要问题需要解决， 即观察空间单元(viewcell)所对应三维空间中区域的切分问题。一般方法均采用均匀切分的办 法，但是在(MATTAUSCH,O.,BITTNER,J.,ANDWIMMER,M.2006.Adaptivevisibility-driven viewcellconstruction.InRenderingTechniques’06,195–206.)中提出了另外一种方法，先粗略估 计三维场景中物体的分布，然后根据场景中物体可见密度来进行viewcell的切分。

该方法另外一个重要的问题就是在观察空间单元所在区域内发射射线进行采样的方法。 首先，空间会被切分成许多观察单元(viewcell)，然后，在观察单元中找到足够多的采样点， 从每个采样点发射一条射线到整个场景中，每条射线则对应于与它相交的最近的物体。最终， 将所有射线所对应的物体合起来得到的物体集合就是希望求解的PVS。AdaptiveBorder sampling(PeterWonka,MichaelWimmer,KaichiZhou,StefanMaierhofer,GerdHesina, AlexanderReshetov,Guidedvisibilitysampling,ACMTransactionsonGraphics(TOG),v.25n.3, July2006)和Adaptiveglobalvisibilitysampling(BittnerJ.,MattauschO.,WonkaP.,HavranV., WimmerM.:Adaptiveglobalvisibilitysampling.InProceedingsofACMSIGGRAPH2009(New Orleans,LA,USA,August2009).)等论文中都提出了非常详细的采样策略，以获取更合适的采 样射线，从而获得更加精确地可见物体集合。

综上所述，from-point和from-region这两类算法都可以求解可见性(visibility)问题的策略， 但是，两种方法的区别很大，各自的适用范围以及优劣都有所区别。from-point的方法得到的 结果往往是精确的，也比较灵活，但是该类型方法往往只能适合于处理较小规模场景和较少 数量的三维模型图元(含几何信息以及纹理材质信息等)，当面对大规模场景以及千万以上数 量级(如面片数)的模型进行绘制时，该类型方法进行可见性处理将会占用较长的时间，影 响在线绘制的速度，使得模型或者场景难以达到实时绘制的要求；from-region类型的方法可 能无法得到最精确的结果，适用于对于误差有一定容忍度的情况，并且也不适用于动态三维 环境，但是from-region的可见性整个计算过程由于属于预处理过程并可以在离线中完成，因 此可以大大地节省在线绘制时所消耗的时间。同时，由于可以在离线预处理中提前生成可见 性信息，所以能够处理的场景和模型的规模以及数量都是几乎没有限制的，可以处理非常大 规模的场景和数据。

但是以往的from-region方法在进行预处理时所进行剖分的可见性基本单元(viewcell)往 往是规则的，而与三维场景内容所占据的三维空间没有任何关联，由此也会破坏三维空间的 连通性完整性等，也就是一个viewcell内包含的并不一定是一个完整的具有相同属性信息的 空间或者三维几何的组合，这样往往会形成与一个viewcell对应的可见性信息(保存在PVS 中)的支离破碎和冗余。针对该问题，本发明提出一种大规模三维场景的新型可见性生成方 法。

此外，为了克服from-region类方法生成的可见性不够精确的问题，本发明还设计了可见 性信息补充完善的方法，通过预计算生成的查询潜在可见集合(QueryPotentialVisibleSet, QPVS)作为可见性信息补充完善的候选，在在线漫游绘制阶段进行在线可见性判断，并把确 定可见的信息补充到PVS中，从而提高了PVS可见性信息的精度和准确性。

发明内容

本发明针对大规模三维场景尤其是城市建筑场景，提出一种大规模三维场景的新型 可见性生成方法。三维场景往往指由多个物体构成的占据一定三维空间的数据集合，每 个物体由一个或者多个三维模型表示。而大规模三维场景往往包含物体(模型)数目巨 大，占据的三维空间的尺度范围大，并且包含海量的数据元素。本发明首先从大规模三 维场景的内容出发，分析其所蕴含的三维空间特征，然后据此进行合理的空间剖分并形 成viewcell以及层次viewcell，由此生成该viewcell的可见性信息。由于viewcell所对 应空间剖分的完整性和一致性，该可见性信息冗余小，存储量少。

本方案思路主要由两个部分组成，预处理可见性计算以及实时在线绘制的可见性信息使 用与动态完善的过程。预处理过程中，首先对三维场景采用k-means聚类的方法进行准确的 三维场景层次树结构，并基于采样的方法计算出每个viewcell的PVS；实时绘制的时候，利 用GPU硬件提供的遮挡查询命令查询一些不确定是否可见的物体的状态，如果可见，则添加 到对应viewcell的PVS中，从而动态修补和完善PVS。

与现有技术相比，本发明的积极效果在于：

我们采用基于k-means聚类的方法对三维场景所占据空间进行层次的划分，该划分能够 准确反映出组成三维场景的各个三维物体之间的结构和组合关系，由该空间划分所表示的观 察单元(viewcell)可以形成该单元之内较为统一的潜在可见集合PVS，利用该划分的空间 进行采样(sampling)可以提高PVS的精确程度，在实时绘制的过程中，利用硬件的遮挡查 询命令动态修补PVS，使得PVS的精确度进一步提高。

附图说明

图1为本发明可见性生成系统完整流程图；

图2为基于层次k-means聚类的三维空间层次viewcell构造流程图；

图3为层次k-means聚类示意图；

图4为原始三维城市场景图

(a)顶视图，(b)斜视图；

图5为初始聚类之后的场景分割示意图(k＝3)，以粗线条表示分割边界；

图6为经过二次聚类所形成场景分割图(k＝3)，以虚线表示分割边界；

图7为经过三次聚类所形成场景分割图(k＝3)，以细线条表示分割边界。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整 地描述，可以理解的是，所描述的实例仅仅是本发明的一部分实施例，而不是全部的实 施例。基于本发明中的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得 的所有其他实施例，都属于本发明保护的范围。

一、预处理过程，预处理部分也分为两个部分。

第一部分预处理：就是分别执行构建三维场景层次包围盒、构建三维空间层次viewcell、 生成三维空间大量随机采样射线三个重要的步骤，为后续的可见性生成做准备。

第1，构建整个三维场景的层次包围盒结构(BoundingVolumeHierarchy,BVH)，BVH是 一层次树结构(用其它类似的树结构，例如kd-tree，二叉树，八叉树都可以)，并将BVH的 相关信息，包括树的层次，父子结点兄弟结点信息，结点包围盒信息(包括包围盒大小，包 围盒原点坐标等)，写入存储结构中，以便后面进行查询与射线相交的场景中的模型以及几何 面片时读取并使用。为整个模型创建空间结构的目的是希望能够加快后面的搜索速度，即为 了快速计算射线与场景中物体进行求交。

第2，对包含该三维场景的三维空间构建一棵层次树，这棵层次树实际上是将三维空间 剖分成了若干个互不重叠的小单元，而这样的每个单元就是一个所谓的viewcell，为每个 viewcell求出它对应的PVS。在本过程中，我们提出了基于层次k-means聚类方法进行三维 空间中层次viewcell的构建，该构建方法使得空间的划分与三维场景的内容密切相关，所划 分的三维场景的不同部分具有不同的模型的属性，例如大量密集的三维建筑群会被划分为一 个整体，而道路等模型稀疏的部分被划分为一个整体。利用上述方法和规则所获得的空间划 分能够获得更加准确的可见性PVS信息，所划分的层次空间节点的数目更少，树的层数(深 度)更少。也就是用更合理的(即能够体现三维场景中模型的分布特性的)空间层次划分组 织代替传统的与三维场景本身内容无关的空间层次划分组织形式。

1、利用k-means进行三维场景的聚类和剖分的基本原理(实质是对三维场景的聚类获得 对应三维空间的剖分)

对于一个表示三维场景的网格或者三角面片的模型取其顶点(或者代表性顶点)，用每个 顶点的三维坐标构成的向量(x,y,z)，或者加上顶点的颜色或者纹理信息形成向量(x,y,z,r,g,b) 甚至其它顶点的属性信息(如材质，语义属性等)来表示需要聚类的顶点，得到顶点对应的 复合向量。对于这个顶点的向量集合运行k-means聚类，又称k-均值聚类方法，其中k代表 希望得到的类别的数目。得到的聚类结果应当是若干个向量的集合，其中每一个向量都属于 且仅属于一个集合。这样针对表示每个顶点的向量进行分类，就可以得到顶点的分类信息。 因此对于三维空间的点集运行k-means聚类的结果应当是所有的点都被赋予了一个类别，也就 是对空间场景进行了划分，而且根据k-means的原理，在空间位置或者色彩纹理或者某些属性 更加接近的点，被归为一类的可能性也是越大的。k-means聚类方法的优点在于算法简单、速 度快。如果有n个点，k个类，迭代了t次，那么算法的时间复杂度就是O(nkt)，时间复杂度 趋近于线性，因此对于大样本具有较高的效率。

2、k-means聚类方法流程

1)随机指定k个顶点，该顶点的含义既可以指三维场景中的一个物体(使用其几何中心 坐标)，或者一块网格(使用其几何中心坐标)，也可以指单个三角面片，取其中某个顶点(或 者代表性顶点或者其几何重心坐标),用所选每一顶点的三维坐标构成的向量(x,y,z)，还可以 附加加上顶点的颜色或者纹理信息(r,g,b)(如果顶点本身是一个物体或者一块网格，则可以 使用该其的颜色或纹理的均值，或者使用其代表性颜色或纹理)，此外还可以对每个顶点附加 其它辅助属信息如材质等等，以此k个顶点作为k个类的初始的中心点；

2)计算每个顶点到k个初始中心点的矢量距离，离哪个中心点距离最近就认为这个顶点 属于哪一类。具体的计算并非完全依赖于三维空间的欧式距离，还可以附加色彩空间中的距 离，以及附加属性空间中的向量距离，这些距离可以通过加权的方式综合起来作为一个统一 的度量。

3)计算每一类中所有点的均值，作为该类的新的中心点；

4)得到了新的中心点，跳转到(2)。算法的终止条件是新的中心点集合和老的中心点集合 的距离小于设定阈值(阈值需要自己手动设置)或者迭代的次数大于了设定上限。每一聚类 结果对应一个子空间，最终将三维空间聚类为k个子空间。

3、基于三维场景的聚类得到场景的层次树结构

在步骤2(k-means聚类方法流程)中已经形成的聚类所对应的空间剖分基础之上，对其 每一个子空间再次使用k-means聚类方法进行子空间内模型或者面片的聚类，对应形成三维空 间的子剖分，即viewcell单元。层次k-means的算法流程如下：

1)在输入的顶点集合上运行k-means聚类方法。

2)对于得到的每一类点集上继续重复上述聚类及剖分过程直到到达指定的空间剖分精 度或者指定的层数，从而获得足够的类别数目。通过层次k-means聚类的方法，当k很大时聚 类的速度可以大幅度提高并且避免了不必要的计算。图3是层次k-means方法的一个示意图， 在图中k＝3。

最终，根据得到的三维空间的多层次单元viewcell的逻辑关系得到该三维空间的层次 树。

通过上述聚类及对应空间剖分方法的运行，如果我们将k-means聚类的k值也就是类 别的数目设的比较小，那么得到的结果可能是代表一个楼群或者几栋相邻楼房的点云被分为 了一类。在这一类中对所有点继续运行k-means聚类，可能得到的结果就是每一栋楼的点被 分为了一类。这实际上就是空间的树形层次结构，每个父节点的所有子节点对于父节点所表 示的点云进行了进一步的细分，得到了更加精细的结构。在这样的层次树结构当中，离根节 点越远，深度越深的类别所包含的点的个数越少，代表的结构面积或者体积也越小。

第3，利用合理的空间采样(sampling)策略，生成大量的三维空间中的采样射线。进行 采样时候，所采用的取样策略是随机采样，也就是在空间中均匀分布的顶点，然后在每个点 随机的生成方向，从而得到随机的射线。该采样射线生成方法参考文献(BittnerJ.,Mattausch O.,WonkaP.,HavranV.,WimmerM.:Adaptiveglobalvisibilitysampling.InProceedingsof ACMSIGGRAPH2009(NewOrleans,LA,USA,August2009).)。

第二部分的预处理：就是为每个viewcell生成它对应的PVS，从而达到生成可见性信 息的目的。步骤如下：

第一步，将每条采样射线逐一地在BVH中搜索，找到在整个场景中距离射线起始点最 近的相交物体。这个过程其实类似于基于BVH的光线跟踪(raytracing)，过程描述如下：射 线自顶向下、逐层的与BVH的包围盒求交，如果与某一层的结点包围盒是相交的，则接着 向下，与该层结点的子结点的包围盒求交，直到叶节点为止。

如果射线与某叶结点相交，则将射线与该叶节点所包含物体的每个三角面片求交。只 要它与其中任何一个三角面片相交，则射线是真正与该物体相交的，此时，更新当前的最短 距离。将最短的距离记录下来的同时，把该最短距离所对应的物体记录下来。最终，遍历完 整个BVH后，得到与采样每条射线相交的最近物体及其最近距离。

第二步，将每条采样射线逐一地在层次树(即层次viewcell空间)中搜索，找到所有 与当前射线相交的viewcell，进而，将上一步中计算所得的与当前射线相交的物体(可能存 在0/1/2个)加入到当前viewcell的PVS中。也就是说，从该viewcell中一定能看到与该射 线相交的最近的物体。

基于层次树的光线跟踪采样的基本思路如下：

(1)先用整个层次树所对应的三维空间包围盒更新每一射线的最近距离和最远距离；

(2)求出射线和当前viewcell所对应的结点的切分面的距离，如果这个距离小于最近距离 或者大于最远距离，说明射线只与当前结点的一部分相交，就可以裁掉一个子结点。如果这 个距离刚好在二者之间，说明射线与结点的两个子结点都是相交的。

第三步，对于每个viewcell所计算出的PVS中的每一个物体T，将物体T三维空间中相 邻某一个设定距离内的所有物体T’找出来，如果物体T’并不在当前viewcell的PVS中，则 将其加入另一个命名为QPVS(QueryPotentialVisibleSet)的集合中，一个viewcell仅对应 生成唯一QPVS，但是一个QPVS中可能有多个物体。由于随机采样的策略所采样的结果毕 竟有限，所以很有可能某些实际可见的物体没有能够采样到从而被遗漏掉，所以这个QPVS 中的物体就是预测的有很大可能是属于该viewcell的exactvisibleset里的物体。于是将QPVS 作为能够补齐PVS的候选物体的集合，在线浏览或者漫游时通过实时遮挡查询确定在候选集 合中的这些物体的真正可见性。

如何选择合适的物体加入QPVS中作为候选，我们采用下述的策略。对于某个viewcell 的PVS中的每一个物体T，根据viewcell和物体T周围采样射线的数目情况，计算出一个适 当的距离阈值d。接着，判断场景中的所有物体，与这个物体T的距离小于d的其他物体如 果不在当前viewcell的PVS中就将其加入QPVS，作为后续遮挡查询的候选。该方法的合理 处理策略如下：当一个物体周围采样数目比较大的时候，错过了可见物体的可能性会比较小， 这个时候，就确定一个较小的距离d，只有比较少的物体会添加到QPVS中进行后续过程中 的额外查询；但是如果采样数目比较小的话，则要确定一个比较大的d，就可以添加较多的 物体到QPVS中。如此就可以保证错过的物体会比较少，而QPVS中的物体实际是可见物体 的可能性也比较大。

第四步，在所有射线都已经与BVH及层次树执行完遍历，并且其相关信息与对应viewcell 整合好以后，将viewcell的所有可见性信息(即PVS，QPVS)写入外存储结构中。

以上就是整个预处理过程，它得到了以层次树为形式存储的viewcell的信息以及每个 viewcell所对应的PVS以及QPVS。这些信息将在实时绘制中被用到。上述可见性信息的构 建过程中，BVH的构建复杂度为O(nlog(n)),层次树的构建复杂度也是O(nlog(n))，而BVH和 层次树的遍历复杂度皆为O(log(n))。

二、实时在线绘制时可见性信息的使用和更新

在进行完预处理的过程以后，接下来是三维场景的漫游及其对应实时绘制。三维场景的漫 游的过程描述如下：

首先，加载三维空间层次树的所有viewcell和层次viewcell的信息。viewcell的信息被 作为一棵层次树来组织，包含viewcell的包围盒边界。

第二步，确定当前视点的位置，找到当前视点所在viewcell，该步骤可以通过在层次树的 每个层次使用视点位置与切分平面比较其所处半空间即可。

第三步：根据当前视点所在viewcell(实质是自根结点至叶结点的一系列结点及其对应的 viewcell)，加载所有viewcell所对应的PVS和QPVS。

第四步，将该叶结点对应的即最精细的viewcell的PVS和QPVS中的物体分别放入不同 的队列，即将PVS放入内存队列Q1，将QPVS放入内存队列Q2。先对Q1和Q2中的物体 分别进行视域体裁剪(viewfrustumculling)，如果物体在视域体(viewfrustum)之外，则将该物 体从Q1和Q2中分别删除；针对Q1和Q2中剩余的物体，按照距离视点的远近分别排序得 到优先级队列Q1和Q2，这两个优先队列都保证距离视点最近的物体放在最前端。

第五步，构建好优先队列以后，按照先处理PVS信息后处理QPVS的顺序对这两个优先 级队列进行处理。先将Q1中的物体依次取出，设取出的物体为T，T是明确可见的，则直接 取得T的网格或者面片信息，发送给显卡进行绘制；然后处理Q2中所包含的物体，按照优 先级顺序依次取出的物体为T，则发送遮挡查询命令(一般通过硬件遮挡查询方式实现)，在 Q1队列绘制结果的基础上对该物体T的包围盒进行遮挡查询，查询比较的对象就是绘制Q1 中物体所形成的遮挡缓冲。为了进一步加快速度，可以在Q1队列中物体进行绘制的同时可 进行Q2中物体的遮挡查询，而不需要每次发送完查询命令后等待查询结果，也就是无需等 待而继续处理后面的物体。而在每次处理一个新物体之前，先查看是否有查询结果返回，如 果Q2中的某个物体的返回结果为该物体可见，则将该物体的从Q2对应的QPVS中删除，加 入到Q1所对应的PVS中。自底向上更新所有层次viewcell中的PVS和QPVS信息。同时， 将上述信息更新至外存储对应viewcell的PVS和QPVS信息。

第六步，继续漫游，视点更新，转至第二步，循环第二至第六步的过程。通过对整个三维 场景进行连续不断地漫游(上述步骤中的第二步至第五步皆发生在场景漫游阶段)，同时在 viewcell中反复进行QPVS查询，相应地更新PVS，便可以得到一个非常接近于EVS(exact visibleset)的PVS。当PVS在相当长一段时间之内不再进行更新，说明PVS已经非常接近 EVS，当前算法和漫游过程结束。