章4-场景建模.doc

第四章 场景建模4.1前言三维场景建模，即在计算机中构建逼真的虚拟三维场景，是计算机工作者长久以来的追求，一直以来都是计算机图形图像处理中最活跃的研究领域之一。虚拟现实、增强现实、计算机动画、影视特技、计算机艺术、CAD/CAM、科学计算可视化及计算机视觉等都把场景建模技术作为核心和基础。比如在虚拟现实中，其核心内容就是虚拟环境的建立、即三维场景建模，也就是根据应用的需要，利用获取的三维数据建立相应的虚拟环境模型。近年来，虚拟现实、三维可视化技术及整个图形图像学科的发展，更是使得在计算机中构建各种复杂逼真的三维场景成为可能。三维场景建模在工业设计与制造、娱乐、教育、医学、视听艺术及军事等方面都有广泛的应用。三维场景建模最传统的方法是采用基于几何的场景建模方法。该方法通常使用已有的三维建模软件进行人工建模，其构建的场景精度较高、模型描述完备、具有良好的交互性、视点自由，但人机交互工作量大、建模效率低、真实感不强。该方法基于三维几何模型合成场景，几何模型加上每个元素的表面反射特性就可以表示出景色，建模期间要用各种测量手段对场景对象进行量测，生成大量的数据，绘制时在场景模型的基础上通过消隐、光照计算等生成最终的三维场景。传统的基于几何的场景建模方法目前已能用于较复杂场景的建模及相关的真实感图形绘制。但随着应用领域的不断扩展，三维场景复杂度越来越高，建模效率和精度要求也越来越高。这对传统的基于几何的场景建模及其绘制提出了严重的挑战。一方面，采用该方法进行复杂的场景建模甚至大规模场景建模时，如果使用手工建模，工作量将很大，很难完成，并且由于很难准确获取真实物体表面的复杂属性因而很难生成非常逼真的场景。另一方面，较为复杂的三维场景模型构建完之后，最终绘制时需要耗费大量的计算和海量的存储，由此使得方法对计算机硬件的性能依赖程度非常高，特别在虚拟现实、互联网等要求实时绘制的应用领域，基于几何的场景建模及其绘制面临着巨大的挑战。针对包括采用三维软件在内的基于几何的场景建模方法的不足，研究人员对三维场景建模进一步做了很多的探索，在这些工作中如下的两方面非常具有代表性。一方面，上世纪 90 年代中期，研究人员提出了基于图像的三维场景建模方法，在国际上兴起了一股研究热潮。这种方法试图从根本上打破传统的基于几何的建模及其绘制方法的限制，它不使用几何模型，而是使用从真实场景中获取的图像（照片或者视频）作为输入。这些图像内含丰富的三维场景信息，这些信息也比较容易提取。这种方法的目标是直接从图像提取这些三维信息，重建出虚拟的三维场景。由于它直接以从真实场景获得的图像为基础生成虚拟场景，因而它产生的场景更加逼真、自然。基于图像的场景建模利用已获得的场景图像信息，综合运用计算机图形图像处理、 计算机视觉等技术，来构建场景的模型。这种模型主要包括了场景的外观、场景的几何结构等。其中三维数据的获取主要是利用非接触式的视觉技术。人类感知外界信息，80%是通过视觉得到的1。人类视觉的成像过程说明人类视觉所直接接收到的外界信息是二维信息，人类视觉的立体感知过程可以被认为是通过接收到的二维信息恢复场景三维信息的过程，实际上就是一个真实三维场景在人脑中的重新建模过程。基于图像的场景建模的主要过程与人类视觉的立体感知过程非常类似，通常包括图像获取、特征提取与匹配、相机（或摄像机）标定、立体匹配、深度恢复和深度插值等部分。在一定程度上，可以认为基于图像的场景建模是传统的基于几何的场景建模方法的延续，因为它用投影几何和解析几何来描述物体的形状，可以方便地运用传统的投影变换、裁剪和消隐算法。但与基于几何的建模及其绘制相比，基于图像的建模具有以下突出的优点：它避免了复杂的几何曲面造型、避免了繁冗的人工操作、建模方便高效、构建的模型真实感效果好、绘制时计算量和存储量相比而言要小得多，因而绘制速度快、对计算机硬件的性能要求不高、适合于实时建模和绘制。基于图像的建模是三维场景建模的一个重要发展方向，对其研究具有重要的学术意义和应用价值。目前，它已经广泛应用到虚拟现实、三维测量与遥感、计算机动画与游戏、电影特效等很多领域。另一方面，使用三维软件手工创建三维场景确实是一个耗时、繁琐、低效的过程， 研究人员考虑是否可以融入人工智能领域的相应知识到三维场景创建过程中，提高场景的智能化创建程度，最终能做到场景的自动创建。自然语言是人们最为熟悉的常用描述工具，因为它让人们可以以一种非常直接的方式描述场景。于是，使用文本描述甚至语音作为输入自动创建三维场景提供了一种非常有效快速的场景创建方式。自然语言对三维场景的描述大多是定性的描述，描述出场景对象及对象间的空间关系，为此，要创建好场景，还需要通过空间推理推算出每个对象在三维坐标系中准确的位置坐标和放置方向，并将推断结果通过场景描述模型存储下来，最后绘图程序根据各对象的方位自动绘制三维场景。这样，也就形成了三维场景创建的另一条思路，即含空间推理的三维场景的自动创建。本章定位为三维场景建模关键技术研究，其中的场景建模涉及两方面的研究：基于图像的三维场景构建和含空间推理的三维场景自动构建，拟对这两种建模方法其中的关键技术进行研究。4.2三维空间中的定性空间描述和推理定性空间推理（Qualitative spatial reasoning，QSR）是人工智能、智能计算领域中一个非常重要的方向。它可广泛应用在许多实际领域中，这些领域比如有机器人导航、高层机器视觉、地理信息系统以及有关物理系统的常识推理等。定性空间推理也是含空间推理的三维场景构建的一个关键基础。现有的研究基本上集中在面向二维空间的定性空间表示和推理方面129130131，而很少有工作直接针对三维空间的定性空间推理进行研究132。很显然，面向三维空间的定性空间推理要比在二维空间中的情况更为复杂，但在实际应用中与二维空间下的情况同样甚至比它更重要。这样，对三维空间情况下的定性空间推理进一步进行研究就具有十分重大的意义。正是在这样的背景下，本章对面向三维空间的定性空间推理进行了研究。我们首先定性描述了三维空间，然后探究了基于三维空间定性表示的空间推理。4.2.1 三维方位关系我们主要根据对象相互之间的三维方位和拓扑关系来定性表示三维空间。这里的对象指三维体对象。对象之间的方位关系规定了一个对象相对另一个对象位置的可行定位范围。这里， 面向三维空间的方位关系包括全局方位关系和局部方位关系两种。4.2.2 全局方位关系全局方位关系给出了基于东南西北这些基本方位的位置及其关系。通常来讲，面向三维空间的全局方位关系集合与在二维空间的情况下相同，共包括八个方位关系，如图2-1所示。这些关系也与人们平常对它们的理解与使用是一致的，相对局部方位关系而言，由于它们与所涉对象所处的上下文关联较少，因而它们比较简单。图4-1 八个全局方位关系4.2.3 局部方位关系局部方位关系给出了基于对象的面、边、角等部位进行定位的位置及其关系。这些关系与全局方位关系相似，但比它们更为复杂，因为不同的特定对象所包含的面、边、 角等特征部位都不尽相同。此外，在三维空间情形下还需要考虑上（above 或 on）和下（below）等方位关系。图 2-2 中演示了这些关系，为了使该图看起来不至于太杂乱无章，图中只给出了六个关系前、后、左、右、上和下（或 Front、Back、Left、Right、Above 和 Below）。实际上，图 2-2 应该包含三个相互垂直的平面，每个平面上包含八个局部方位关系，这八个局部方位关系之间的布局结构和全局方位关系的正好相似。图4-2三维空间情况下的局部方位关系4.2.4 局部方位关系在描述空间关系时，使用拓扑关系也是非常重要的，因为对象之间的拓扑关系在包含旋转、缩放、平移等在内的拓扑变换下是保持不变的。在探寻一种用户友好的空间拓扑关系表示方法时，我们应该使所采用的拓扑关系总的数量尽可能少。正如我们所知，如果所采用的拓扑关系总的数量太多，它们相互之间很容易产生混淆，以至于很难让用户在使用时记住。当然，与此同时，这些关系应该使空间拓扑关系的描述尽可能完备。Clementini等133给出了一个拓扑关系的最小集，包含五种关系：touch、in、cross、overlap 和 disjoint，这些关系适用于描述点、线和区域等空间基本元素之间的拓扑关系。根据他们的这一基本思想，我们设计了一个三维拓扑关系的最小集，也包括五种拓扑关系： disjoint、contact、overlap、contain和in，它们的定义演示于图 2-3之中。该集合中并 没有包含关系 cross，因为该关系仅仅适用于描述线与线、线与区域之间的关系，并不适合于描述三维体对象之间的关系。此外，为使用方便之故，该集合中加入了关系contain。这些拓扑关系与人们平常对它们的理解与使用几乎一致，它们共同强力有效的表达了对象之间的三维拓扑结构。图2-3 五种三维拓扑关系Fig.2-3 Five kinds of 3D topological relationships4.3定性三维空间推理在根据对象之间的方位和拓扑关系定性地描述了三维空间之后，我们探寻了基于此的三维空间推理。借助于组合表进行定性空间推理是最常采用的方法。本节中，我们首先给出了定性三维空间关系的组合表，然后提出了一个不确定性模型描述了每一个定性空间关系的置信水平（或者说确定性程度），并且以此为基础构建了所有对象的一个带权约束图，根据该带权约束图，确定了在推理计算场景对象的位置时各对象的处理顺序。4.3.1 三维空间关系的组合定性空间推理中一个很关键的操作是关系的组合，即给定对象 A和对象 B之间的关系，以及对象 B和对象 C之间的关系，推断对象 A和对象 C之间的关系。这里，通过组合表进行的定性空间推理涉及到三维空间情形下方位关系之间的组合以及拓扑关系之间的组合。Hernndez 134给出了前（Front）、后（Back）、左（Left）、右（Right）等八种二维局部方位关系的组合表。基于这一结果，根据全局方位关系和二维局部方位关系之间的结构相似性，我们给出了三维空间中的全局方位关系的组合表，如表 4-1 所示。表 4-1 全局方位关系的组合表oB CA BESESSWWNWNNEEEE,SEE,SE,SE,SE,S,SWallE,NE,N,NWE,NE,NE,NESESE,ESESE,SSE,S,SWSE,S,SW,WallSE,E,NE,NSE,E,NESS,SE,ES,SESS,SWS,SW,WS,SW,W,NWallS,SE,E,NESWSW,S,SE,ESW,S,SESW,SSWSW,WSW,W,NWSW,W,NW,NallWallW,SW,S,SEW,SW,SW,SWWW,NWW,NW,NW,NW,N,NENWNW,N,NE,EAllNW,W,SW,SNW,W,SWNW,WNWNW,NNW,N,NENN,NE,EN,NE,E,SEallN,NW,W,SN,NW,WN,NWNN,NENENE,ENE,E,SENE,E,SE,SallNE,N,NW,WNE,N,NWNE,NNE对于三维空间中的局部方位关系之间的组合情形，我们可以将其分解为三个正交投影平面上的局部方位关系之间的组合情形。由于每一个正交投影平面上的情形都与二维空间中的情形结构相似，因此每一个都可以应用二维空间下的局部方位关系之间的组合推理。这样的做法的好处在于几乎不需要作什么修改就可以使用二维空间情形下的组合表。4.3.2 三维拓扑关系的组合三维拓扑关系的组合可以根据各关系的定义直观地进行直接推导。表 2-2 展示了五种基本拓扑关系的各种组合推理结果。表 4-2 五种基本拓扑关系的组合表oB CA Bdisjointtouchoverlapcontainindisjointalldisjointtouch overlap indisjointtouch overlap Indisjointdisjointtouch overlap intouchdisjointtouch overlap containalldisjointtouch overlap indisjoint touchtouch overlap inoverlapdisjointtouch overlap containdisjointtouch overlap containalldisjointtouch overlap containoverlap incontaindisjointtouch overlap containtouch overlap containoverlap containcontainoverlap contain inindisjointdisjoint touchdisjointtouch overlap inallin4.3.3 带权约束图对象之间的定性空间关系限制了有关对象的可行位置。也就是说，这些关系实际上是施加在对象上的约束。依据初始的关系，借助于组合表我们能得到更多的关系或约束，于是可以通过下一章中的有关算法或通过求解约束满足问题来推断和计算各对象的位置135136。在确定三维场景各对象位置的过程中，通常来讲，对象的位置不确定性程度越低，或者说位置确定性程度（或位置置信程度）越高，该位置就越容易确定，该对象位置越应该被优先推理计算。可以根据与对象有关的约束，包括方位和拓扑关系约束等，来计算对象的位置确定性程度。估算对象位置的确定性程度的最简单方法是计数与对象相关的约束的数目。然而， 这一方法并未考虑在确定对象位置时不同约束所做的不同贡献，而只是简单地给每一个约束相同的权重。这将导致出现如下类似的情形：约束“A R1 B”和约束“A R2 B”被 同样对待，其中 R1 = Front并且 R2 = Left, Front, Right。而事实上，第一个约束 R1显然要比第二个约束 R2强，在确定对象A或B位置时第一个约束R1的贡献显然要比第二个约束R2大，因为R2由三个可能的关系构成，具体是哪一个并不确定，对象的位置确定性程度（或位置置信程度）很低，相比而言，R1 仅仅包含一个关系，其体现的约束十分确定、位置确定性程度高。这样，我们需要给出一个更为有效的方法来度量对象的位置确定性程度。4.3.4空间关系约束的不确定性模型对于每一个约束，我们使用一个不确定性模型来描述该约束的置信水平，该置信水平体现了在确定有关对象的位置时该约束所作的贡献大小。不同种类的约束使用了不同的不确定性模型。在下面的段落中我们将构建这些模型。我们采用了一些符号以便使下面的表达更为精炼。对于某一个约束“A R B”，即在对象A和B之间存在约束 R，“Card (R)”表示R的基数，即R中包含的关系的数目；而“Conf (A R B)”表示约束的置信水平。下面依次构建了方位和拓扑约束的不确定模型。1）全局方位约束对于一个由初始给定或者经推理产生的全局方位约束 A GDR B，GDR 涉及到八种全局方位关系，是八种全局方位关系组成的全集的子集。约束 A GDR B 的置信水平 Conf (A GDR B)的计算模型由公式（2-1）给出。（2-1）正如我们所知，如果 Card (GDR)是 8，这意味着对象 A和 B之间的全局方位关系 完全不确定，可能是八种方位关系中的任何一种。实际上，在这种情况下，全局方位约束 A GDR B 对确定 A或 B的位置根本没什么作用，于是将其置信水平 Conf (A GDR B) 赋值为 0是很合适的。GDR的基数 Card (GDR)越小，包含的可能关系越少，在确定 A或 B的位置时约束 A GDR B也越强，由此它的置信水平 Conf (A GDR B)也就越高。特别是，如果 GDR 仅仅包含一种全局方位关系，Conf (A GDR B)的值将被设置为 1。2）局部方位约束对于三维空间情形下的局部方位约束 A LDR B，我们分别考虑其在三个正交投影平面上的投影约束 A LDRFL B、A LDRAL B 和 A LDRBA B。每一个投影约束都涉及八种局部方位关系。它们各自的置信水平的计算模型都与全局方位约束的模型极为相似。局部方位约束 A LDR B 的置信水平 Conf (A LDR B)是三个投影约束的置信水平之和，如公式（2-2）所示。（2-2）3）拓扑约束假定A和B之间存在一个拓扑关系约束 A TR B，这一约束可能由初始给定或者是经推理产生的结果。TR 与五种拓扑关系相关，是五种拓扑关系组成的全集的子集。约束A TR B的置信水平Conf (A TR B)的估算如下面的公式（2-3）所示，由此也就构建了拓扑约束的不确定性模型。（2-3）4.3.5基于带权约束图的推理在为各约束的置信水平建模之后，我们可以估算各有关对象的位置确定性程度。这可以借助于带权约束图来实现。在带权约束图中，结点表示对象，带权边表示约束，也即对象之间的空间关系。对于每一条带权边，它的权重是对应约束的置信水平。对于带权约束图中的每一个结点（比如说对象 A），我们定义了它的权重，该权重是与该结点（或对象）关联的所有边的权重的加权和。结点的权重即作为相应对象的位置确定性程度，比如针对对象 A，其位置确定性程度表示为“Conf (A)”。假设对象 Bi 是与 A有全局方位关系约束的对象，对象 Cj 是与 A 有局部方位关系约束的对象，对象 Dk 是与 A 有拓扑关系约束的对象，则我们可以使用公式（2-4）计算对象 A的位置确定性程度 Conf (A)，其中 wGDR、wLDR 和 wTR 分别是全局方位约束、局部方位约束和拓扑约束的权重。通常而言，可以使 wGDR=wLDR=wTR=1/3，但我们也可以根据不同的应用情况给 wGDR、wLDR 和 wTR 赋不同的权重。（2-4）此外，我们从公式（5-4）中也注意到 Conf (A)包含了其它带权约束。比如，“对象A正对北方”这一约束对于从全局整体角度确定对象A的位置提供了非常有用的信息，尽管这一约束并不是一个两对象之间的关系。我们这里使用“GCO”来表示类似这样的约束，这意指对象的全局约束，它也可能作为对象的一个属性而出现。对于全局约束 GCO 的置信水平 Conf (GCO)，可以像公式（2-1）那样建模计算。如果对象 A 确定地正 对一个方向，Conf (GCO)的值取 1；如果对象 A 可能正对八个方向中的任何一个，则 Conf (GCO)的值取 0。相比前面通常的两对象之间的全局或局部方位约束而言，GCO 约束给对象A提供了更强的限制，于是在公式（2-4）中可以给它赋以比 wGDR 或 wLDR 更大的权重，比如 w=1/2。根据带权约束图，我们能看出，结点的权重越大，其相应对象的位置确定性程度越高，在计算推理各对象的位置时该对象越应该优先处理。于是我们首先确定了具有最大权重的对象的位置，然后是确定具有次大权重的对象的位置，依此类推，按照对象权重的从大到小顺序，依次确定各对象的位置。对于每一个对象，我们根据与它相关的约束，通过下一章中的有关算法或通过求解约束满足问题来求解确定它的位置135136。4.4场景的集成和调度管理和优化4.4.1场景模型的集成场景环境实体模型的构建是按照本章前面所提到的虚拟场景层次结构的划分来进行的，各层次结构实体景观模型构建完以后需要进行组合与集成，最终形成宗祠虚拟场景的整体模型。拿祭祀宗祠场景来打个比方，在祭祀宗祠场景建模过程中，首先把单独建好的实体模型按其在虚拟场景中的结构位置逐个添加到整体宗祠场景模型里，在祭祀宗祠场景模型中主要包括供桌、香炉、蜡烛、贡品等实体模型，石阶、楼牌、松柏、荷花池等环境景观模型。按照结构层次建模的思想，由于天空、白云、远山等远景模型与其它模型关联不大，因此可以单独生成、存储为一个文件。而环境景观模型(如花草、树木、乱石、石柱、楼梯等)位于地面模型之上，可以将它们组合为一个总体模型，单独存储，以备场景调用时的实时显示。每个实体模型单独创建，按照实际情况分别成组，存储为不同的文件。然后将所有实体模型的文件整合到一个文件中，按照确定好的位置逐一添加到指定位置，形成一个整体模型。这样做的优点是可以形成一个视觉效果非常好、真实感十分强的、气势壮观的场景。缺点是当场景中的模型比较复杂时，所生成的文件相应地就会很大，这样会极大地降低导入及实时响应速度。本系统中使用了外部引用技术来进行场景模型的集成。外部弓用(又称外部调用， ExternalReference)是指在一个模型中可以调用另一模型的部分或者全部，并可以重新定义被调用模型的空间位置。在本系统中的应用是:将在外部环境(如AutocAD)创建的模型通过外部引用技术导入到3dsmax环境中来，以实现场景模型的集成。4.4.2场景调度管理在实现一个具有通用性的漫游系统时，通常需要完成从一般模型到复杂场景的调度与管理的过程。对于局部区域、规模较小的模型可以一次性、直接导入到内存，对多边形进行绘制渲染，输出图像;而对于内容丰富、庞大复杂的场景来说，模型在装载、调用、输出视景图像时必须采用一定的场景调度技术，如分块调用等，才能充分保证系统的实时性。1、场景地形的分块调度对于多边形较多的复杂场景来说，一般都要进行分块调度。先将整个地形分割成若干个多边形数较少的小单元地形，并存成不同的地形模型文件，再以外部引用的方式分别调用(包括地形上的地物)，重新构成一个完整的地形模型29。这样可以根据视点所看到的区域，动态地选择小单元地形模型进行调用，不需要调用整个地形模型，能有效地提高系统输出视景的实时性。(l)静态导入，动态调用如果计算机内存容量充足，而地形数据文件不是很大，则可以将其一次性导入内存，调用时则可以分块进行。如某一地形由多块小地形组成，由于每一块地形的坐标范围已知，所以可根据视点所在的位置坐标知道当前实体在哪一个地形数据库中，从而可以确定调用的是哪一块地形。(2)动态导入，动态调用如果复杂场景所对应的地形数据文件很大，受计算机内存容量的限制，在实时系统中，必须动态地导入实体周围的若干地形模块。可以将地形区域划分为若干适当大小的装载模块。在三维地形环境绘制时，通常只处理观察者视线范围内的装载模块。2、场景模型的动态调度对于场景复杂的系统而言，有时仅仅采用场景地形分块调度技术并不能保证达到良好的效果，当实体密集时，如果一小块地形上的地物模型都要同时绘制的话，也会极大地影响系统的实时性22，。所以，对场景模型也必须实行动态调度，以减少一帧渲染的多边形数量。通过采用基于视点视域的场景渲染与调度方式，系统每帧只需绘制落在视域体内的场景模型，大大减少了实时渲染的工作量，能够有效地提高绘制速度。本系统中场景的调度和管理是通过Virtools开发工具来实现的，遵循的大原则是:静态导入，动态调用。在系统实时运行时，采取的是动态导入，动态调用。例如:祭祀大殿、游客休息室、会客室、祭祀物品、环境景观，在系统运行前，将它们一次性地加载到Virtools中，等待系统调用，即静态导入，动态调用。在系统运行时，根据用户需求在系统菜单中选择不同的子系统(如祭祀大殿)，进行实时显示和操作，即动态导入，动态调用。图3一4为祭祀物品与宗祠大殿集成后的效果图。图3-4祭祀物品与宗祠大殿集成后的效果图4.4.3结构优化在建立庞大的场景模型之前，应该根据虚拟场景中每个实体的几何空间位置，以及模型之间和模型内部的结构关系，来确定整个虚拟场景的结构及场景中所有实体模型的结构，这里的结构通常采用的是层次结构。对场景进行层次结构划分后，可以方便场景建模的分块、分工和实体模型的组织和管理，明确模型构建目标，大大减轻建模的工作量23。即使是最简单的模型也需要调整模型的层次结构，来达到优化的目的。除此之外，按照层次建模思想进行结构优化的结果也将制约着后续优化的结果。虚拟场景构建中的结构优化可以分为场景结构优化和模型结构优化两个方面，即结构优化的宏观方向和微观方向。结构优化的基本思想是先进行场景分块(或模型分割)，再进行层次建模，然后进行集成。1、结构优化中场景分块(或模型分割)的基本原则总结如下:(l)原则上单个物体可以独立分块，如宗祠大殿、会客室等;(2)同类物体可以分为一块，如香炉、蜡烛、祭祀物品等;(3)视觉上相邻的物体可以分为一块，如花草和树木、荷花和(4)有关联关系的物体(如:运动关系、制约关系)的物体可以阶和楼牌;(5)完全没有关联的物体可以分为一块，如天空、草地和远山2、结构调整属于结构优化的一部分，尤其体现在调整层次结构介绍调整层次结构建模的原则和方法:(l)构建有层次结构的模型。一个复杂物体可能由多个简单物每个形体都放入其自身的组节点中，可以根据每个物体的结构然后将它们组合在一个组里。组合的顺序和原则可以综合权衡物的位置、重要性、可操作的程度、视点所覆盖的范围等因素。(2)尽量避免创建在空间上跨度较大的物体。通常，落在我们(即空间中的可视化部分)称为有效物体，但是只要在可视化范，都要对物体进行计算，尽管我们只看见部分物体，但却不得的物体进行计算。所以在建模时，如果发现分块不合理，要及时街道两侧的房屋，属于一类物体，按原则可以分为一块，但是涉及的范围很大，从而造成了巨大的运算量，既耗时、_占据系统重影响物体的显示速度。(3)视觉上相邻的物体的层次结构建模的调整。同一等级的数至右排列，当节点存在而物体不可见时，调整显示节点位置;时，可对不可见物体进行节点或多边形等的删除。(4)规则物体的层次建模。在不影响真实感的前提条件下，只围部分进行建模，内部、底部和连接面等部分可以省略。(5)不规则物体的层次建模。根据物体不规则部分的重要程度、可视、有操作的部分可以考虑建模重点，其他部分可用简单、长方体等)来代替。3、结构优化的关键技术(1)单元分割1241(cellsegmentatfon)是将虚拟场景(或模型单元，只有在当前场景(或模型)中的实体才被渲染，因此极场景(或模型)的复杂度。这种分割法对于地形模型和大型建的，因为在人的视野中所见的物体只是整个虚拟环境中的很小武汉理工大学硕士学位论文理当前所见的物体大大提高了系统的速度。地形模型分成若干时可以只输出其中的几个单元区块，而不必导入所有的模型。(2)层次细节技术(LevelOfDetail，LOD)空间的细节层次节点(LOD)控制原理是通过空间距离的远近来展现空间造型的各个细节。细节层次控制和现实世界中的感观是极为相似的。在现实生活中人们都会有如下的体验:在离一个建筑物很远时，只能隐约地看到一座建筑物的轮廓、形状和大小等，但是当你走近时，就会看清楚整个建筑物的门窗，再走近些会看到门窗上的雕花等更加清晰的内容。静态LOD:在预处理过程中产生一个物体的几个离散的不同细节层次模型，实时绘制时根据特定的标准选择合适的细节层次模型来表示物体。此方法的优点是:易编程实现;简化算法不受实时绘制的约束;现代的图形硬件更有利于静态算法的实现。存在的问题:由于每个细节层次模型分别存储，需要较大的存储空间。由于存储空间的限制，决定了只能存储很有限的几个细节层次，因而造成不同的细节层次之间的过渡不平滑，显示时会出现明显的跳跃和突变。动态LOD:在动态LOD算法中生成一个数据结构，在实时绘制时可以从这个数据结构中抽取出所需要的细节层次模型，从这个数据结构中可以得到大量不同分辨率的细节层次模型，而且分辨率是可以连续变化的。优点:各个细节层次之间的变化尺度更合适。没有使用不必要的多边形;给定多边形数目的情况下有更好的逼真度;支持多边形模型的增量传输。层次细节 LOD(LevelofDetail)技术用一组复杂程度(常常以多边形数来衡量)各不相同的实体细节等级模型来描述对象，并在仿真过程中根据一些客观标准在这些LOD模型间进行切换，从而能够实时改变场景的复杂度。视点变化时，所选取的细节等级模型各不相同。例如，当采用视点与物体的距离作为选择标准，视点离物体较远时，调用较粗略的模型，当视点离物体较近时，则选用描绘细致的模型。在传统的图形系统中，三角面片是最通用的绘图元语。随着描述场景中几何模型的三角形数目的增多，所绘制的图象质量越来越高，但是绘制速度也越来越慢，从而形成了一对矛盾。一般来说，图形渲染速度与模型中的三角形数目成反比。尽管图形渲染系统的性能在近几年有明显提高，但总有一些场景过于复杂，不能实时渲染。而实时渲染是虚拟现实系统的一项基本要求，LOD就是用来解决这个矛盾较实用的方法。本文采用改进的基于边折叠的LOD算法对宗祠场景模型进行简化处理，并取得了满意的效果。4.4.4模型优化(l)去除冗余几何元素模型构建中如果能够利用最少的多边形数量获得相同的真实感，那是最成功的模型。去除系统中不可见的多边形可以减少系统数据库多边形数量。因为，在构建好的模型中，往往存在不必要的几何元素，这是经常出现的问题，它们时刻处于不可见的位置，去除它们并不影响实体本身的视觉效果，去除冗余几何元素可以在很大程度上降低整个场景模型的复杂度，提高显示速度。这里的冗余多边形主要是指在实体外部观察模型时不可见的部分。例如:建筑物的底座面、内墙面及楼层面间的连接面等。由于场景浏览时，它们处于不可见的位置，因此并不会影响场景模型的整体效果。下面以祭祀大殿前方的台阶为例来说明面的删除和合并。如图3-5所示，此台阶模型本身都是和建筑物连接在一起的，因此台阶背面以及每个长方体的下表面都是不可见面，对于这些不可见面应直接将其删除。这样经过简化后，模型的面片数可减少20%一30%。图3-5为简化后的台阶模型4.5基于四叉树和BSP树的虚拟场景管理的实现4.5.1四叉树场景剖分原理四叉树的生成过程，是一个由根结点开始分解，最终迭代创建整个树结构，从而实现对虚拟场景进行剖分的过程。首先选取整个场景的最大包围空间(即空间内长、宽、高的最大值)创建一个场景的最大包围立方体模型作为 rootnode(根节点)，然后基于这个立方体模型的基础上对场景进行多次循环分割，最终生成四叉树结构。经典的四叉树式的数据结构在每一非叶子节点上保存指向其四个子节点的指针(或引用)。此外，对于每个节点而言，应该设置这个节点所表示的虚拟场景或模型的空间区域范围。这个过程并不是要将虚拟场景构成的栅格中实际的顶点置入四叉树中，而只是在四叉树中指明这个节点所包含的虚拟场景的相应区域。四叉树本质上是对空间及空间内几何体的几何剖分，通过使用该方法，可以解决场景在渲染时如何快速的寻找需要绘制显示的节点。当漫游者在复杂的三维建筑场景中行走漫游时，系统并不需要将场景内全部模型对象都实时的绘制显示，可以基于 viewpoint的可见度计算，由场景管理器根据计算进行场景内隐藏模型对象的消除处理，这样就实现了在不影响展现效果的前提下减少了需要渲染处理的多边形的数量和范围。四叉树通过对应每个父节点引用其四个子节点，在进行场景渲染时， rootnode将会表达为这个围绕场景的正方形区域集，子节点表示为“左上”，“右上”，“左下”和“右下”四个象限，这些象限由根节点首先创建，然后每一个象限都是由父节点与四个子节点迭代或递归地分解定义。基于四叉树的场景划分步骤包括以下4步:步骤一:将虚拟三维空间等价转换为二维平面。前提是高度相对于广度可以忽略，或者研究问题对象允许简化三维参数变量。步骤二:遍历场景中的所有模型区域，选取合适的分割平面。由于虚拟三维建筑多数属于规则图形，因此，在逐层分割的过程中，我们没有必要逐个去分解每个多边形，只需要选取经过象限顶点且与X轴或Z轴垂直的平面作为分割面即可。步骤三:分割完成后，分别创建“左上”，“左下”、“右上”以及“右下”四个象限的子节点。判断对应象限内包含的多边形数量是否超过设定的阀值。若超过，该象限区域继续分割，同时四叉树的叶子节点继续分解。若未超过，则该节点就作为叶子节点，保存当前各层场景的相关属性。步骤四:重复步骤二三两步处理，直至不存在可以分割的节点为止本文提出的VRML中利用模型语言提供的原型节点，对基于四叉树划分后的节点进行自定义类型，得到的四叉树数据结构的形式为: PROTOQuadTNode#自定义的节点的基本场景属性 exPoseFieldSFRotationrotate exPoseFieldSFVec3fseale0.01.00.0 exPoseFieldSFColorcolor1.00.01.0 coordDEFPlaneol一 COORDCoordinatePoini00，10，11，01以下定义非叶子节点的四个子节点(children)，每个children对应一个子节点定义，每个子节点也是QuadTNode节点类型。GrouPChildren geometry cylinderchildrengeometryeylinder.childrengeometryeylinder.childrengometryeylinder.对四叉树中的每个节点(包括叶子节点和非叶子节点)，应该定义此节点所表示的场景空间的包围范围，定义这个节点所覆盖的场景空间的区域。对应于上述VRML四叉树定义中的 coordDEFPlane01一COORD，指定这个节点的四个顶点所表示的坐标索引。通过这四个顶点的坐标也就可以计算出此节点所覆盖的平面区域的大小。如下图3.2所示。图中节点的四个顶点的坐标为(4，4)、(4，一4)、(一4，一4)、(一4，4)。图3-2四叉树剖分采用该数据结构的四叉树实现场景模型的空间剖分后，在场景渲染的时候，可以以LOD方式高效的实现场景图绘制。可以通过计算包围球或包围长方体的方法，实现对可见体的裁剪处理。利用上述步骤，通过检查和计算场景模型的平面图是否与包围球或包围长方体相交，对于不相交的部分即为不可见集，对其进行场景模型消除处理，节省了系统资源的消耗，提高了场景渲染的执行效率。4.5.2基于VRML的四叉树的实现(l)LOD(Level Of Detail)LOD是指在构建组成虚拟场景的几何体模型时，分别构建不同的细节详细程度的模型(可能面数不同)，场景渲染引擎会依据漫游者的视点与该物体的距离按照预先设置的各临界值自动装入相应的模型数据。由于随着视点与物体的距离变化，所能看到的物体细节详细程度也是随着变化的。因此，在虚拟场景中构造物体模型时，可以根据物体与视点的距离远近决定对该物体构建的模型的细节详细程度。这样既保证了不损失场景的逼真度，又节省了虚拟系统的计算资源。在VRML中，LOD用LOD节点定义: LodlLOD center0.00.00.0level#引入不同的细节文件inlineurl“one.wrl”inlineurl“two.wrl”inlineurl“three.wrl”center7.5，12.0，20.0#确定引入细节文件的临界值其中的level域是代表相同物理所具有不同细节层次的模型节点的列表。LOD能够提高构建虚拟场景的效率，但由于模型节点的增加导致场景定义文件变大，一方面下载模型文件耗时变大，同时在运行时需要更多的计算机内存支持。另外，只是在视点远离物体时LOD的优点才一会体现出来。(2)分割场景分割场景是指将复杂的三维场景分割成几个较小和较简单的场景，实现分阶段下载和装入，以提高执行的效率。可使用hihne节点、Anchor节点装入在其它WRL文件中定义的场景或模型。节点定义如下:Inline exposedField MFstring url field SFVee3f bboxCenter 0 0 0 field SFVee3f bboxsize -1 -l -1url指定了引入外部场景文件的路径，bboxCenter是场景模型装入的坐标原点，bboxsize为场景的范围大小。由于Inline节点会在视点与物体的距离达到指定值时才被装入，所以利用hihne分割较复杂的场景可以提高初始场景的绘制显示效率。4.5.3基于二叉树的分层次的场景组织管理分层次的方法在场景管理的过程中非常有用, 也就是说将场景分解成多个物体。把物体分解成部件, 再把部件分解成多边形。场景组织是整个场景驱动的灵魂, 而且到目前为止没有适用于任何场