自适应视相关LOD模型的动态构建及其更新.pdf

第3 7 卷第5 期中国矿业大学学报 V 0 1 ．3 7N o ．5 2 0 0 8 年9 月J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g yS e p ．2 0 0 8 自适应视相关L O D 模型的动态构建及其更新 王永波1 ’2 ，盛业华3 ，闾国年3 1 ．中国矿业大学环境与测绘学院，江苏徐州 2 2 1 1 1 6 ，2 ．江苏省资源环境信息工程重点实验室，江苏徐州2 2 1 0 0 8 ， 3 ．南京师范大学虚拟地理环境教育部重点实验室，江苏南京 2 1 0 0 4 6 摘要在三维表面模型的渐进格网表示法的基础上，提出了一种具有拓扑保持特性的自适应视 相关L O D 模型的实时动态构建及其更新方法．算法利用渐进格网对原始高分辨率模型进行表 示，并根据边折叠的先后顺序构建相应的层次二叉树，在视相关L O D 模型的实时动态构建及其 更新过程中，顾及包括视点、视方向、视场角、表面法向以及顶点影响范围等几乎所有与视觉效果 相关的参数对结果模型的影响，进而构建相应的视相关L O D 模型．与传统的静态L O D 表示法 相比，本文算法可以根据需要有选择地对局部格网进行简化或加密，结果L O D 模型中允许多种 不同的分辨率共存，在保证渲染效果的同时，有效地减小了模型表达的数据量、加快了模型的渲 染速度．通过实例验证了该算法的有效性和实用性． 关键词三维表面模型；有选择加密；模型简化；渐进格网；层次细节模型；多分辨率表示 中图分类号T P7 5 1文献标识码A文章编号1 0 0 0 - 1 9 6 4 2 0 0 8 0 5 0 6 5 8 0 6 D y n a m i cC o n s t r u c t i o na n dR e a l - T i m eU p d a t eo f S e l f - - A d a p t i v eV i e w - D e p e n d e n tL O DM o d e l s W A N GY o n g b 0 1 ．- 。S H E N GY e - h u a 3 ，L UG u o - n i a n 3 1 ．S c h o o lo fE n v i r o n m e n t ＆S p a t i a lI n f o r m a t i c s ，C h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y ， X u z h o u ，J i a n g s u2 2 1 1 1 6 ，C h i n a ；2 ．J i a n g s uK e yL a b o r a t o r yo fR e s o u r c e sa n d E n v i r o n m e n t a lI n f o r m a t i o nE n g i n e e r i n g ，X u z h o u ，J i a n g s u2 2 1 0 0 8 ，C h i n a ； 3 ．K e yL a bo fV i r t u a lG e o g r a p h i cE n v i r o n m e n t ，M O E ，N a n j i n gN o r m a lU n i v e r s i t y N a n j i n g ，J i a n g s u2 1 0 0 4 6 ，C h i n a A b s t r a c t B a s e do np r o g r e s s i v em e s hr e p r e s e n t a t i o no f3 Ds u r f a c em o d e l s ，a na d a p t i v e ，v i e w d e p e n d e n ta n dt o p o l o g y - p r e s e r v i n gm e s hs i m p l i f i c a t i o na l g o r i t h mw a sp r e s e n t e d ．P r o g r e s s i v e m e s h e sa r eu s e dt or e p r e s e n to r i g i n a lh i g h r e s o l u t i o nm o d e l sa n dh i e r a r c h i c a lb i n a r yt r e e sa r e c o n s t r u c t e db a s e do nt u r no fe d g ec o l l a p s eo p e r a t i o n s ．I nt h ep r o c e s so fr e a l t i m ec r e a t i o no f v i e w - d e p e n d e n tL O Dm o d e l s 。s e v e r a lp a r a m e t e r sr e l a t e dt ov i s u a le f f e c t sa r ec o n s i d e r e d ，i ．e ．， v i e wp o i n t ，v i e wd i r e c t i o n ，f i e l do fv i e w ，n o r m a lo fs u r f a c e ，i n c i d e n c eo fac e r t a i nv e r t e xa n d o t h e rp a r a m e t e r s ．I nc o n t r a s tt ot r a d i t i o n a ls t a t i cL O Dr e p r e s e n t a t i o nm e t h o d s ，t h ea p p r o a c h p r e s e n t e dc a nb eu s e ds e l e c t i v e l yt or e f i n eo rc o a r s e nac e r t a i na r e ao fam o d e l ．A sar e s u l t ， s e v e r a ld i f f e r e n tl e v e l so fd e t a i lm a yC O e x i s ta c r o s sv a r i o u sr e g i o n si nt h er e s u l t o fas p e c i f i c m o d e l ．U n d e rt h ep r e c o n d i t i o no fe n s u r i n gt h a te f f e c t sw i l lb er e n d e r e d ，t h ea p p r o a c hp r e s e n - t e dg r e a t l yr e d u c e st h ea m o u n to fd a t ar e q u i r e dt oa p p r o x i m a t eo r i g i n a lh i g h r e s o l u t i o nm o d e l s 收稿日期2 0 0 7 0 9 1 5 基金项目国家自然科学基金项目 4 0 6 7 1 1 4 7 ；高等学校博士学科点专项科研基金项目 2 0 0 6 0 3 1 9 0 0 4 ；江苏省高校自然科学重大基础 研究项目 0 7 K J A 4 2 0 0 5 作者简介王永波 1 9 8 2 一 ，男，江苏省泗阳县人，博士研究生，从事三维地理信息系统原理与应用、三维建模及可视化等方面的研究． E - m a i l y b w a n g S l 6 1 6 3 ．c o r n T e l 1 3 6 5 5 2 0 8 8 2 3 万方数据 第5 期王永波等自适应视相关L O D 模型的动态构建及其更新 a n dt h u st h es p e e do fr e n d e r i n gr e s u l tf r o mm o d e l si s r a p i d l ya c c e l e r a t e d ．A tt h ee n d ，c a s e s t u d i e sa r eg i v e nt ot e s tt h ee f f e c t i v e n e s sa n dp r a c t i c a b i l i t yo ft h em e t h o d ． K e yw o r d s 3 Ds u r f a c em o d e l ；s e l e c t i v er e f i n e m e n t ；m e s hs i m p l i f i c a t i o n ；p r o g r e s s i v em e s h ； l e v e lo fd e t a i l ；m u l t i r e s o l u t i o nr e p r e s e n t a t i o n 基于多边形格网的三维表面描述方法凭借其 数学表达的简洁性及易操作性在3 DG I S 、计算机 图形学、虚拟现实、交互式可视化等领域赢得了普 遍青睐，并相继出现了一系列基于多边形渲染的图 形硬件．当前，几乎所有的基于表面描述的三维模 型表达 如样条曲面、隐式曲面等 均可实现其向多 边形格网的转换[ 1 ] ．而不规则三角形格网又是应用 最广泛的多边形格网． 三维数据采集技术如三维激光扫描的快速进 步导致了空间数据呈现出“海量”增长的趋势，使得 现有的图形硬件很难满足实时编辑、渲染等要求． 针对这一问题，文献[ 2 ] 提出了L O D 1 e v e l - o f - d e t a i l 的概念，之后，国内外学者致力于相应的算法 研究以期尽可能提高构建L O D 模型的自动化程 度及其效率，为了实现对象表面模型的L O D 表 示，通常需要预先生成并存储5 ～6 个不同分辨率 的模型供渲染时调用，渲染过程中，仅有一个与要 求最接近的L O D 模型被调入内存进行渲染．这种 方法虽然在一定程度上解决了“海量”数据的渲染 问题，但通常是以牺牲较多的存储空间为代价的， 且一旦涉及到内外存模型的交换时，视觉上的跳变 及不连续现象仍然无法完全避免． 文献[ 3 ] 提出了渐进格网 p r o g r e s s i v em e s h ， 简称P M 的概念，并给出了多边形格网模型的渐 进格网表示方法．与传统的L O D 表示法相比，P M 表示方法仅需要存储一个具有最低分辨率的基模 型及相关的边折叠记录，即可根据要求实时生成一 系列具有任意分辨率的L O D 模型，极大地降低了 对存储空间的需求，除此之外，P M 表示方法还具 有易于网络传输等优点． 然而，无论是传统的L O D 表示法，还是P M 表 示法，结果模型中位于不同区域的分辨率是一致 的，这在遭遇超大规模数据的时候，很难应付自如， 取得流畅的渲染效果，从而出现诸如视觉跳变、画 面不连续等现象．能否根据视觉要求，对视觉重要 度比较高的区域利用较高分辨率进行表示，而视觉 重要度比较低的区域则利用较低分辨率进行表示， 即同一L O D 模型中，允许多种不同的分辨率共 存．针对这一问题，文献i - 4 ] 提出了视相关L O D 模 型生成算法的设想，并在P M 表示方法的基础上进 行了初步实现，证明了该想法的可行性及其有效 性．随后，文献I - 5 - 1 2 ] 针对这一问题展开了一系列 的研究，并取得了很多有用的成果． 针对三维表面模型的P M 表示方法，本文在前 人的研究基础之上提出了一种新的、具有拓扑保持 特性的自适应视相关L O D 模型的高效构建算法， 可以根据需要有选择地对局部格网区域进行简化 或加密，算法顾及了包括视点、视方向、视场角、表 面法向以及顶点影响范围等几乎所有与视觉效果 相关的参数对结果模型的影响． 1 三维表面模型的渐进格网表示法 渐进格网的构造过程与传统静态L O D 模型 的创建过程非常类似，差别仅在于存储理念的不同 而已．传统的L O D 表示法是将预先生成的一系列 具有不同分辨率的L O D 模型存储起来供实时调 用，而P M 则不然，通过存储一个最简基模型肝 和一系列边折叠记录{ ％，c ，，⋯，c ，卜。 ，不但节约 了存储空间，还能够实现任意分辨率L O D 模型的 构建以及高效的网络传输．本文中，首先采用一种 基于二次误差标准及边折叠操作算子的表面模型 数据压缩算法[ 1 3 3 对原始高分辨率格网模型M n 进 行压缩，在经过行次连续的边折叠操作之后，得到 一个最简基模型M 和一系列边折叠操作记录{ f 。， f 。，⋯，O r , - - ，} ，这一过程可用下式进行描述 c p lc 1c o M “ 一⋯一脚一肝． 1 可逆性是边折叠的一个重要特性，称顶点分裂 乳 i 一1 ，2 ，⋯，竹 为边折叠的逆操作．如图1 所示， 边折叠操作将顶点口t ～折叠到口。。，不难看出，当所 有相邻顶点让“’ i 一1 ，2 ，⋯，1 0 的状态以及所形 成的格网结构与口“。折叠到‰之后完全相同时， 即可对‰顶点进行分裂，并且这一过程完全不会 破坏原始模型的拓扑结构．如果按照边折叠操作的 逆序实施顶点分裂操作，则可以重建出与原始模型 完全相同的模型，这一过程可用下式进行描述 ％‘1’n - - 1 “ 一肝一⋯一 “ 一蚴． 2 因此，利用表面模型的渐进格网表示方法，可 以将模型“ 表示为{ 肝，s 。，s l ．．．，s ，卜1 ． 万方数据 6 6 0中国矿业大学学报第3 7 卷 图1 边折叠与顶点分裂 F i g ．1E d g ec o l l a p s ea n dv e r t e xs p l i t 2 可见性判别 在视相关L O D 模型的实时动态构建及其更 新过程中，通过视椎、法向椎及顶点的包络球等有 效地模拟了视点、视方向、视场角、表面法向以及顶 点影响范围等与视觉效果相关的参数对结果模型 的影响．本文首先给出视椎、法向椎及包络球的定 义视椎[ 1 6 ] 可以简单地描述为一个半无限的金字 塔，通过视点、视方向以及沿着z ，Y 方向的视场角 即可定义，这里的视椎定义是根据计算机屏幕的有 效观察范围来定义的，根据该定义，可以有效地模 拟人眼的视觉范围；法向可以看作是单位球S 2 { P ∈R 3 I IpJ I 一1 的一个子集，通过法向、视场 角等2 个参数即可定义，法向椎的定义顾及了其相 邻顶点以及父顶点 被折叠顶点 的影响，通过法 向椎与视锥的相交性判断来实现顶点的可见性判 别；包络球的实质，是定义了顶点的影响范围，为判 断当前顶点是否满足分裂条件提供了重要依据，包 络球的定义利用圆心及半径即可实现，与法向椎 j ，一一，蕊贫． 么，，’一、口f玢 r ＼＼、过／’N 乡。 一样，包络球的定义顾及了其相邻顶点以及父顶点 的影响，通过包络球与视锥的相交性判断，即可有 效判断当前顶点是否满足分裂条件． 可见性判别包含2 个步骤1 判定当前视椎 与当前顶点的法向椎的交集是否不为空；2 判断 当前顶点的影响范围 包络球 与当前视椎的交集 是否不为空．仅当上述2 个条件同时被满足时，认 为有必要对顶点实施分裂操作．如图2 a 所示，顶点 法向可以定义为单位球球心至其表面上任意一点 连线的方向，口代表当前视椎的半视场角，卢表示法 向椎的半视场角，9 表示法向椎方向与视方向之间 的夹角．不难得知，当9 ≥9 0 。时，可以确信当前顶 点法向椎与当前视椎的交集不为空；当妒 9 0 。时， 根据三角形边角关系定理可知，9 卢 y 1 8 0 。且 口 占 y 一1 8 0 。，在口，妒和p 已知的情况下，艿可以 表示为8 一口 p 垆，如果占≥9 0 。，仍然可以判定 当前顶点法向椎与当前视椎的交集不为空，其它任 何情况均认为当前顶点的法向椎与视椎的交集为 空． 如图2 b 所示，判断一个顶点的影响区域是否 与当前视椎相交，首先根据当前视点及顶点掣的包 络球中心定义法向量邑，法向量的方向定义为当 前视点到包络球中心的方向；设叫为视方向与法向 量k 之间的夹角，并定义盯一a s i n r 。川x 。I f ； 如果c c ， 口或者c c ，一叮 口时，则认为当前顶点口的 影响范围 包络球 与当前视椎的交集不为空． 扩／’i 蕊给． I ‘姒。／、、、j ’ a 基于法向椎的可见性判别 b 基于包络球的可见性判别 图2 可见性判别 F i g ．2V i s i b i l i t yc u l l i n g 3 算法描述 ’ 本文的算法主要包括2 个阶段预处理与视相 关L O D 模型的实时动态生成及其更新．针对实现 中所涉及的关键技术问题，在此进行逐一论述． 3 ．1 预处理 预处理阶段的主要任务是利用渐进格网表示 法对原始表面模型进行表示，并构建相应的层次二 叉树．算法首先利用作者提出的一种基于二次误差 标准与边折叠操作算子的表面模型数据压缩算 法[ 1 3 ] 对原始模型进行压缩处理，并利用前面介绍 的渐进格网表示法来表示原始高分辨率模型，为了 满足渲染过程中视相关L O D 模型的实时动态生 成及其更新，在P M 表示法的基础之上构建层次二 万方数据 第5 期王永波等自适应视相关L O D 模型的动态构建及其更新6 6 1 叉树．且将原始模型的P M 表示和层次二叉树同时 存储于边折叠记录之中． 3 ．1 ．1 边折叠算子 边折叠c 臼‰，‰ 过程中，顶点口h 。被删除， 所有和口f 一相邻的三角面片中的％。顶点均被改 变为‰顶点 退化三角面片除外 ．如图1 所示，顶 点口‰被折叠到口。。，边折叠之后，顶点勘。一被删 除，与口f 一，口。。相邻的2 个三角面片 讪“’，‰， 臼。。 ， 口。㈨，口础h 。 退化为一条直线，因此，将其 删除，与口t 一相邻的其它三角面片中的口h o m 顶点均 被相应地改变为钞。，即从 功‘n ’，功‘n ’，口f 一 变为 耽㈤，口，h ’，口。。 ，并且，顶点‰的新法向椎、新包 络球均被重新计算． 在生成多分辨率模型的过程中，结果模型的所 有顶点及三角面片均是原始高分辨率表面模型的 一个子集，因此，不需要另外开辟空间存储边折叠 之后生成的新顶点以及新产生的三角面片，仅仅是 将那些不属于结果L O D 模型的顶点和三角面片 标记为非活动状态 n o n - a c t i v e ．如在一个具体的 边折叠c 铆t 一，‰ 过程中，仅需要将折叠顶点 口‰以及在折叠过程中退化三角面片的状态设置 为n o n - a c t i v e ．如图l 所示，边折叠之后，只要将顶 点口f 一以及三角面片 口1 h ’，砂f 一，口。 与 饥‘n ’， 臼。。，“ ／．／i t o 。 的状态设置为n o n - a c t i v e 即可．与之类 似，在边折叠的对偶操作顶点分裂s 口‰， 口。 过程中，再将顶点口‰以及三角面片 口，㈨， 口f 一，刀。。 与 口6 “’，口。，口‰ 的状态恢复为活动 状态 a c t i v e 即可．与G a r l a n d 算法[ 1 4 0 和H o p p e 算 法[ 1 5 ] 相比，节省了用于存储新产生的顶点和三角 面片的额外存储空间． a 顶点层次树 边折叠过程中受影响的顶点仅仅包含所有和 ‰相邻的顶点 如图1 中圆圈所包含的顶点 ，这 里将它们标记为S 7 ，因此，在视相关L O D 的生成过 程中，当位于S 7 中的所有顶点其状态标记为a c t i v e 时，即可对顶点口。。实施分裂操作． 三角网格曲面有着流形与非流形之分，定义折 叠前后能够保持原有曲面类型不变的这一性质为 拓扑保持特性．为了保证算法的拓扑保持特性，预 处理阶段，执行边折叠操作之前，首先记录与边折 叠相关的参数信息，并考察折叠前后曲面类型是否 一致，遇到不一致的情况则取消当前的边折叠操 作，从而保证结果L O D 模型与原始高分辨率模型 保持拓扑一致；视相关L O D 模型的实时构建阶 段，首先对待分裂顶点的状态信息进行检验，仅当 其状态信息与边折叠过程中完全相同时，才允许该 顶点分裂操作被执行，如图1 所示，如果需要对顶 点‰实施分裂操作，仅当所有位于圆圈中的相邻 顶点仇‘n ’，砚“’，口3 ‘n ’，仇‘n ’，刁5 ㈨，口6 h ’其状态为 a c t i v e 时，该分裂操作才允许被执行． 3 ．1 ．2“边折叠树”的构建 算法利用层次二叉树来实现视相关L O D 模 型的实时动态构建及其更新．其中，二叉树节点并 非和某个具体的顶点相对应，而是对应于某个特定 的边折叠记录，因此，将文中构建的层次二叉树称 为边折叠树 e d g ec o l l a p s et r e e ，简称E C T ．E C T 具有如下两个优点1 E C T 隐式存储在边折叠记 录之中，不需要额外的空间对其进行存储，节约了 内存的消耗；2 相对于简化层次树与顶点层次树 而言，E C T 的深度至少要降低1 甚至更多 如图3 所示 ，因此，对树的遍历速度更快． 图3 顶点层次结构与边折叠树 F i g ．3 V e r t e xh i e r a r c h ya n di t sc o r r e s p o n d i n gE C T E C T 的构建通过自下而上的方式进行，且是 伴随着表面模型数据压缩的过程一起完成．在边折 叠c 口‰，口。 过程中，如果顶点口‰具有相关的 b 边折叠树 边折叠记录 即以前曾经有某个顶点口7 ‰折叠到 钞t 一之上，将该边折叠记作c v 7 ‰。“ O l r o m ，那么当 前的边折叠记录中P 妇K - a 成员变量将指向最近一 万方数据 中国矿业大学学报 第3 7 卷 次与顶点v f f 帆相关的边折叠记录c v 7r 。。，口胁 ， 且c v 7 f 。。，口f 。。 的P 。。成员指向c 口f r 。，可。 ；类 似，如果顶点u ，。具有相关的边折叠记录 即以前曾 经有某个顶点口7 。折叠到u ，。之上，将该边折叠记 作c v 7 刚口。。 ，那么当前的边折叠记录中P 岫渊- d 成 员将指向最近一次与顶点‰相关的边折叠记录 c v 7 t o 口。。 ，且c v 7 t o ，秽。。 的P 。。。成员指向 c 口h o m ，u 。 ；P 。。I f 则始终指向其自身，即c v 胁， 砂t 。 ． 3 ．2 视相关L O D 模型的实时动态构建 在生成了表面模型的P M 表示及构建了E C T 后，即可实现视相关L O D 模型的实时动态构建及 其更新．判断一个顶点口是否满足分裂条件，首先 利用E C T 定义的边折叠记录之间的层次关系，找 到和待分裂顶点相对应的边折叠记录，根据第2 部 分所讨论的可见性判别算法来判断该顶点是否满 足分裂条件，如满足，则对顶点u 实施分裂操作． 视相关L O D 模型的实时动态构建过程中，定 义堆栈S 。。用于存储待分裂的边折叠记录 每一个 边折叠记录对应于表面模型的一个特定顶点饥 集 合，整个过程可以分为如下几个步骤 1 遍历基模型胛中的所有顶点，寻找每个顶 点可。。。相对应的边折叠记录f 。⋯并调用可见性判别 函数q r e f i n e c 。。， ，如果该函数返回t r u e ，则将f 。。 压人堆栈S 。。的尾部． 2 如果堆栈S 。。为空，视相关L O D 模型的构 建过程结束；否则，弹出堆栈的第一个元素，并且判 断是否所有受影响顶点的状态均为a c t i v e ，如果条 件满足，则转步骤3 ，否则，转步骤4 ； 3 对当前顶点‰，实施分裂操作，分别寻找与 顶点口f r m ，‰相对应的边折叠记录f 蛔，f I o ，并调 用可见性判别函数q r e f i n e c 测试口f r o mm 。是否满 足分裂条件，如果该函数返回t r u e ，则将f 锄／f 。压 入堆栈S 。。的尾部； 4 将当前的边折叠记录重新压入堆栈顶部， 并寻找所有状态为n o n a c t i v e 的相邻顶点对应的 边折叠记录，将其压入堆栈的顶部，转步骤2 ． 3 ．3 视相关L o D 模型的实时动态更新 一般来讲，交互式可视化及飞行模拟过程中， 视参数的变化通常很小，相应地视相关L O D 模型 的变化也很小．源于E C T 结构的灵活性，不需要每 次变化视参数之后都重新构建相应的L O D 模型， 而是直接对已有的L O D 模型进行修改，从而满足 不变的高质量视觉效果．与H o p p e 算法[ 4 3 相比，模 型的实时更新算法思路基本类似，不同之处在于实 现过程中所基于的层次树不同．视相关L O D 模型 的动态更新其实质就是通过将层次树中的一条顶 点链 如图4 中的边界顶点 上下移动来实现的，表 现在算法中则是一系列的边折叠和顶点分裂操作． 图4 二叉树、活动树与边界节点 F i g ．4 B i n a r yt r e e ，a c t i v et r e ea n db o u n d a r yn o d e s 对于顶点分裂操作，只要用户需要，算法将会 强制执行，而简化操作则仅当条件完全满足时才会 被执行． 4 实验与分析 利用C 语言对本文的算法进行编程实现， 并以南京师范大学随园校区孔子雕像的三维激光 扫描表面建模模型作为实例，在P C 机 W i n d o w s X P 操作系统，内存5 1 2 M ，P e n t i u m4 处理器，主频 2 ．6 6G H z 上对其进行验证．图5 给出了原始模型 以及在特定视参数情况下的视相关L O D 模型在 F l a t 渲染模式下的渲染效果，其中，图5 a 中的四棱 椎即根据当前视参数定义得到的视椎，沿z ，Y 方 向的视场角分别为5 ．5 。；图6 给出了视相关L O D 模型的格网显示效果、当前视参数条件下视相关 L O D 模型的实时渲染效果以及分辨率跃变区域的 局部放大效果．不难看出，位于视觉范围内的孔子 雕像模型 如图6 a 所示的头部以下至分辨率跃变 部位 其分辨率较高，位于视觉范围之外的部分则 利用较低分辨率对其进行表达 如图6 a 所示的分 辨率跃变部位至雕像底部 ，从而实现了以较小的 数据量来实现较高渲染质量的效果 如图6 b 所 示 ，这与本文的预期目标完全吻合，加之位于高分 辨率与低分辨率之间的过渡区域其跃变幅度较大 如图6 c 所示 ，在保证较高渲染质量的同时，进一 步减小了结果L O D 模型的数据量． 为了进一步验证本文算法的可行性和实用性， 对算法运行时的相关参数进行了统计分析．在如图 5 a 所示的视参数条件下，当利用原始高分辨率模 型对孔子雕像进行表达时，所需的三角面片数目为 5 9 91 5 2 个，渲染时的平均帧频为9 ．8 帧／s ；而在当 前的视参数条件下利用本文算法构建的视相关 L O D 模型来近似表达原始模型时，渲染模型的三 万方数据 第5 期王永波等自适应视相关L O D 模型的动态构建及其更新 6 6 3 角面片数目减少到6 58 1 3 个，实时渲染的平均帧 频达到2 2 ．6 帧／s ，不难看出，视相关L O D 模型的 高质量构建对提高模刑的渲染效率有较大的影响． 【a J 脒始梭倒‘j 说锥 兰角面片数日5 9 9 1 5 2 个； F P S 9 ．8 帧，s b J 视辑1 天L O D 模型的 整体效果 三角面片数日6 58 1 3 个； F P S 2 26 帧，s 图5 孔子像的视相关I 。0 D 模型 构建时间2 ．2 8 2s F i g ．5V i e w d e p e n d e n tL O Dm o d e lo fK o n g z iS t a t u e c o n s t r u e t i n g t i m ei sa b o u d2 ．2 8 2S 【a 视相关L O D 模型 c J 视相关L O D 模型 三角面片数目6 58 1 3 个；F P S 2 2 ．6 帧／s的局部显示效果 图6 视相关L O D 模型及其局部显示效果 F i g ．6V i e w d e p e n d e n tL O Dm o d e lo fK o n g z i S t a t u ea n di t sl o c a le f f e c t s 5 结 论 立足于三维表面模型的渐进格网表示法的基 础上，提出了一种具有拓扑保持特性的自适应视相 关L O D 模型的实时动态构建及其更新方法，可以 根据需要，有选择地对模型的局部区域进行加密与 简化．与传统的静态L O D 表示法相比，算法顾及 了包括视点、视方向、视场角、表面法向以及顶点影 响范围等几乎所有与视觉效果相关的参数对结果 模型的影响，通过定义视觉重要度表征了不同区域 对视觉效果的影响，从而使得视觉重要度大的区域 拥有较高的分辨率，反之则拥有较低的分辨率，在 保证L O D 模型的高质量渲染效果的同时，有效地 提高了实时编辑与渲染的效率． 然而，本文的算法虽然在一定程度上解决了 “海量”数据的编辑与渲染效率问题，但在遭遇超大 规模数据的时候，需要借助基于外存的算法来解决 这一问题，是本文今后的一个重点研究方向；此外， 在当前的大部分可视化应用中，需要借助于纹理来 加强图形的真实感，在视相关L O D 的模型构建过 程中，将纹理信息一并进行处理，将是本文的另一 重要研究方向． 参考文献 [ 1 3L E U B K ED ，E R I K S O NC ．V i e w - d e p e n d e n ts i m p l i f i c a t i o no fa r b i t r a r yp o l y g o n a le n v i r o n m e n t s [ C ] ／I W H I T T E DT ．S I G G R A P H9 7C o n f e r e n c eP r o c e e d i n g s ．N e wY o r k A d d i s o nW e s l e y ，1 9 9 7 1 9 9 2 0 8 ． [ 2 ] C I 。A R KJ ．H i e r a r c h i c a lg e o m e t r i cm o d e l sf o rv i s i b l e s u r f a c ea l g o r i t h m s [ J ] ．C o m m u n i c a t i o n so ft h eA C M ． 1 9 7 6 ，1 9 1 0 5 4 7 - 5 5 4 ． [ 3 ] H O P P EH ．P r o g r e s s i v em e s h e s [ C ] ／／R U S H M E I E R H ．S l G G R A P H9 6C o n f e r e n c eP r o c e e d i n g s ．N e w Y o r k A d d i s o nW e s l e y ，1 9 9 6 9 9 一1 0 8 ． [ 4 ] H O P P EH ．v i e w - d e p e n d e n tr e f i n e m e n to fp r o g r e s s i v em e s h e s [ C ] ／／W H I T T E DT ．S I G G R A P H9 7 C o n f e r e n c eP r o c e e d i n g s ．N e wY o r k A d d i s o nW e s - l e y 。1 9 9 7 1 8 9 1 9 8 ． [ 5 ]E L - S A N AJ ，V A R S H N E YA ．G e n e r a l i z e dv i e w - d e p e n d e n ts i m p l i f i c a t i o n [ J ] ．C o m p u t e rG r a p h i c sF o r u m ，1 9 9 9 ，1 8 3 8 3 9 4 ． [ 6 ]J A N GJ ，R I B A R S K YW ，S H A wc ，w 0 N K AP ． A p p e a r a n c e - p r e s e r v i n gv i e w - d e p e n d e n tv i s u a l i z a t i o n [ C ] ／／T U R KG ，W I J KJ ，M O O R H E A DK ．P r o - c e e d i n g so fI E E EV i s u a l i z a t i o n2 0 0 3 ．A t l a n t a G e o r - g i aI n s t i t u t eo fT e c h n o l o g y ，2 0 0 3 4 7 3 4 8 0 ． [ 7 ] L E U B K ED ．H i e r a r c h i c a ls t r u c t u r e sf o rd y n a m i cp o l y g o n a ls i m p l i f i c a t i o n [ R ] ．U n i v e r s i t yo fN o r t hC a r o - l i n a - C h a p e lH i l lC o m p u t e rS c i e n c e 。T e c h n i c a l R e p o r t ，1 9 9 6 T R 9 6 0 0 6 ． [ 8 ] L I N D s ，r R O MP ，K O L L E RD ，R I B A R S K YW ，e t a 1 ．R e a l - T i m e 。c o n t i n u o u sl e v e lo fd e t a i lr e n d e r i n go f h e i g h tf i e l d s [ J ] ．A C MC o m p u t e rG r a p h i c s S I G G R A P H ’9 6 ，1 9 9 6 ，3 0 3 1 0 9 1 1 8 ． [ 9 ] P A J A R O L AR ，D E C O R oC ．E f f i c i e n ti m p l e m e n t a t i o no fr e a l t i m ev i e w -