（计算机应用技术专业论文）实时图形处理关键技术研究.pdf

摘要 摘要 二维折线集、三角网格和点是几何模型表示中的基本元素，分别被广泛用于 二维矢量地图和三维物体模型的表示。如何快速地传输和操作由它们表示的几何 模型是实时图形处理的主要任务。本文以几何压缩理论与方法为基础，分别分析 了矢量地图和三维几何模型中的拓扑数据和几何数据的特点，首先，提出了基于 折线简化和单纯复形的矢量地图多分辨率表示和渐进式传输方法，该方法在保持 视觉一致性的条件下，将较小分辨率地图的数据量降低为最大分辨率地图的数据 量的1 1 0 ，提高了矢量地图渐进传输的效率。其次，提出了基于扇形带的三角网 格拓扑关系表示方法，该方法在不考虑顶点分裂与融合的情况下，可以保证连接 关系的最低压缩率为1 0 9 ：( z ) 比特顶点。第三，提出了基于广义三角形带的三角网 格数据压缩和多分辨率表示方法，该方法可以充分发挥图形处理器的功能，统一 了单分辨率和多分辨率三角网格的表示方法。最后，提出了基于k d 树的点模型 各向异性量化方法。对k d 一树广度优先的遍历可以构造出多分辨率点模型。该方 法可以将点与多边形相结合混合表示几何模型，克服了点模型在表示大平面时效 率低的缺点。以上方法有效地提高了图形在存储、传输以及绘制等方面的效率， 增强了图形处理的实时性。 关键词：实时图形几何压缩矢量地图三角网格点模型多分辨率表示渐进式 传输 摘要 a b s t r a c t t h et w o d i m e n s i o np o l y l i n es e t ，t r i a n g l em e s ha n dp o i n ts a m p l e dm o d e la r e p r i m a r ym e t h o d so fg e o m e t r i cm o d e lr e p r e s e n t a t i o n a n da r ew i d e l ye m p l o y e dt o r e p r e s e n tt h ev e c t o rm a pa n dt h r e e d i m e n s i o ng e o m e t r i cm o d e lc o r r e s p o n s i v e l y h o wt o t r a n s m i ta n do p e r a t et h e s eg e o m e t r i cm o d e l si st h ei m p o r t a n tt a s ko f r e a l t i m eg r a p h i c s b a s i n go nt h ep r i n c i p l ea n dm e t h o d o l o g i e so fg e o m e t r i cc o m p r e s s i o n , w ea n a l y z e dt h e p r o p e r t i e so ft h et o p o l o g i c a la n dg e o m e t r i cd a t ac o n t a i n e di nv e c t o rm a pa n dp r o p o s e d n e ws t r a t e g i e sf o rs a v i n g , t r a n s m i t t i n ga n dr e n d e r i n gt h e s ed a t aa sw e l la st r i a n g l em e s h a n dp o i n ts a m p l e dm o d e l t h ef i r s ts t r a t e g i e sp r e s e n t e di nt h i sd i s s e r t a t i o ni st h e 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 na n dp r o g r e s s i v et r a n s m i s s i o no fv e c t o rm a pb a s e do n p o l y l i n es i m p l i f i c a t i o na n ds i m p l i c i a lm u l t i c o m p l e xb yw h i c ht h ev o l u m eo fc o a r s e r l e v e ld a t ac a ng e n e r a l l yb er e d u c e dt oo n et e n t ho ft h a to ft h ef i n e s tl e v e lw h i l e p r e s e r v i n gt h ev i s u a lc o n s i s t e n c yb e t w e e nt h e ma n dt h ep r o g r e s s i v et r a n s m i s s i o no f v e c t o rm a pd a t ai ss p e e d e du p t h es e c o n di st h ef a ns t r i pb a s e dt o p o l o g i c a ld a t a r e p r e s e n t a t i o nf o rs i m p l et r i a n g l em e s hb yw h i c ht h ec o n n e c t i v i t yb e t w e e nv e r t i c ec a n b ee n c o d e dl e s st h a nl 0 9 2 ( 弼) b i g v e r t e xw h e nt h es p l i tv e r t e xa n dm e r g ev e r t e xi s i g n o r e d t h et h i r di s t h eg e n e r a l i z e dt r i a n g l e s t r i p b a s e dd a t ac o m p r e s s i o na n d 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 nf o rs i m p l et r i a n g l em e s h t h es i n g l ea n dm u l t ir e s o l u t i o n r e p r e s e n t a t i o n sh a v es a m ec o d e cs t r a t e g i e si n t h i sm e t h o dw h i c hi sa p p r o p r i a t et ot h e a r c h i t e c t u r eo f m o d e mg r a p h i cp r o c e s su n i ti np e r s o n a lc o m p u t e r a tl a s t ，k d - t r e eb a s e d a n i s o t r o p i cq u a n t i z a t i o nw a sd e v e l o p e dt or e d u c et h ev o l u m eo fg e o m e t r i cd a t a , i e c o o r d i n a t e so fp o i n ts a m p l e ，f o ra2 - m a n i f o l dp o i n ts a m p l e dm o d e l t h eb r e a d t h f i r s t t r a v e r s a lo fk d t r e ew a su s e dt oc o n s t r u c tt h em u l t i r e s o l u t i o np r e s e n t a t i o n i nt h i s m e t h o d ，t h eh y b r i dp o i n ta n dp o l y g o nr e n d e r i n gs u r m o u n t st h eo b s t a c l eo fl a r g ef i a t s u r f a c er e p r e s e n t a t i o nb yp o i n ts a m p l es e t a l lt h e s es t r a t e g i e si n c r e a s et h ee f f i c i e n c yo f r e a l t i m eg r a p h i c sp r o c e s s i n g k e y w o r d s ：r e a l t i m eg r a p h i c s ；g e o g r a p h i cc o m p r e s s i o n ；v e c t o rm a p ；t r i a n g l em e s h ； p o i n ts a m p l e dm o d e l ；m u l t i r e s o h i t i o nr e p r e s e n t a t i o n ；p r o g r e s s i v et r a n s m i s s i o n 创新性( 或独创性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名： 导师签名： 日期 日期 第一章绪论 第一章绪论 自从十九世纪6 0 年代，美国麻省理工学院的i v e ns u t h e r l a n d 首先提出交互式计 算机图形学( c o m p u t e rg r a p h i c s ) 的概念以来，经过近半个世纪的发展，交互式计 算机图形学逐渐从一个有生命力、有前途和振奋人心的研究领域，发展成为一个 崭新的科学分支，并且已经在许多领域发挥着越来越重要的作用。其应用领域涵 盖了科学计算可视化、仿真和虚拟现实、工程设计、医学图像分析、机械制造、 城市规划、环境保护、文物保护、计算机游戏、教育培i j l i 以及艺术创作等许多方 面。 计算机图形学的特点之一是广泛地使用二维和三维几何数据来描述几何模型。 在实际应用中，随着计算机图形学及其相关理论与技术的发展，模型的复杂程度 不断提高，所使用的几何数据的规模急剧增长，迫切需要一些高效的算法来处理 它们。另外，随着互联网的出现、发展和普及，如何在互联网中发布和操纵几何 模型及其组成的场景也逐渐成为一个急需解决的问题，并且需要一些与传统计算 机图形学不同的算法。本文主要研究了面向实时图形处理的几何数据压缩方法以 及相关理论，并将它们用于处理这些规模不断增大的几何数据，满足随着计算机 和互联网中图形应用系统的需求。 1 1 图形处理系统 本文的研究工作适用于计算机和网络中的图形处理系统。图形处理系统的主 要任务可以分为建模、传输和绘制三部分，而图形的传输受到计算机接口带宽和 网络带宽的影响，是整个图形处理系统的瓶颈。本文的工作从计算机和网络的特 点出发，利用仔细设计的压缩编码策略，尽量减少数据传输量，而获得较高的图 形处理效率。本节主要介绍计算机和网络中图形处理系统及其特点。流计算模型 已经成为现代图形处理器的理论基础，因此本节还简要介绍了流计算模型的基本 概念和原理。 1 1 1 计算机中的图形处理系统 在传统的计算机结构中，虽然计算机的中央处理器( c e n t r a lp r o c e s s i n gu n i t ： c p u ) 可以进行与图形相关的计算，但是在计算机的结构中仍然将图形处理负载 从c p u 分离出来，由独立的图形处理单元来完成，这主要是因为图形处理任务是 2实时图形处理关键技术研究 一个运算量和数据量都非常巨大的任务，完全由c p u 完成将增加c p u 的负载，并且 很难保证图形处理的实时性。图形处理任务是由单独的图形处理器( g r a p h i c p r o c e s s i n gu n i t ：g p u ) 来完成的。图1 1 【lj 说明了图形处理器与计算机的其他部分 之间的关系以及不同部分之间数据传输带宽。为了实现图形处理的实时性，图形 处理器将图形处理中的主要步骤划分成相对独立的部分，并且根据每个部分的特 点分别进行处理，例如在顶点处理阶段和象素的渲染绘制阶段引入并行处理技术， 从而获得较高的图形处理效率。 妒l 三竺厂 o t h e rp e n p i h e r a l s f i g ，i 1t h eo v e r a l ls y s t e ma r c h i t e c t u r eo f ap c 图1 1 个人计算机的系统结构简图( 前端总线频率8 0 0 m h z ) 计算机图形处理的流程主要包括：应用系统产生几何数据、几何数据输入g p u 、 坐标变换、光栅化处理、渲染绘制、直到最后输出合成图像，如图1 2 所耐”。几 何数据的产生由c p u 完成，其它任务由g p u 中的相应单元完成。除了产生几何数 据，c p u 还要产生一些状态数据，如观察者的位置。根据这些数据图形处理单元 完成后续的所有任务。在g p u 的任务中，坐标变换单元完成将三维几何数据从三 维世界坐标系n - 维图像坐标系的变换，同时完成光照模型的处理，得到每个顶 点的亮度值。光栅化处理单元将变换到二维图像空间的顶点的几何表示变成图像 表示，计算每个顶点所占图像单元，并对相邻顶点所占据图像单元进行插值，计 算出未被顶点覆盖的图像单元。渲染绘制单元完成象素颜色的计算并将结果输出 到显存，也可以直接从显存中的纹理图像获取颜色数值。 f i g 1 2as i m p l i f i e dg r a p h i c sp i p e l i n e 图1 2 图形处理流程简图 为了统一图形处理的流程，使图形处理器适用于处理不同几何表示方法表示 型扣 第一章绪论 的几何模型，目前图形处理器只直接支持以三角形为基本元素组成的面模型的处 理，因此无论图形应用系统采用哪种几何表示方式，最终都要把产生的几何模型 分割成三角形集合，才可以充分利用图形处理器的功能。这样，对于复杂的模型 和大规模场景将会产生由数以万记甚至百万记的三角形组成的数据，传统串行处 理模式已经不能胜任这些数据的处理任务，为了能够实时地处理这些数据，图形 处理器的数据传输能力和计算能力就成了两个关键。从图1 1 和图1 2 可以看出，在 计算机系统中，数据从主存到图形处理器之间的传输带宽相对于图形处理器内部 的数据传输带宽仍然是一个瓶颈，并且相对图形处理器的计算能力发展相对缓慢。 图形处理器中设置显示缓存的目的就是将各个单元产生的l 临时数据进行本地保存， 减轻数据传输的负载。另外，几何数据压缩也是减少从主存到图形处理器的数据 传输量的有效方法，本文的主要工作就是解决不同的几何数据的压缩与传输问题， 从而提高图形处理的实时性。 在计算能力方面，随着微电子技术的快速发展，图形处理芯片的运算速度获 得了快速提高，以g e f o r c e 系列的图形处理芯片为例，浮点运算速度已经从2 0 0 2 年 的每秒8 0 亿次提高至1 2 0 0 4 年的每秒5 4 0 亿次，并且还在继续提高。另外，根据图形 处理任务的运算密度高、数据并行和操作独立的特性，图形处理器采用流水线式 的结构，将任务分解为相对独立单元，每个单元接收上一个单元数据并产生下一 个单元需要的所有数据，同一个单元对数据的操作一致，并且不同单元之间的数 据操作相对独立，这些特点使得可以根据各个单元承担的任务的特点设计专门的 硬件进行计算，获得较高的效率。 与计算机的中央处理器不同，现代图形处理器的设计中大量采用了并行处理 机制【1 1 。并行处理机制分为任务并行、数据并行和指令并行三种类型，其中任务并 行是指同时对多个数据单元进行不同操作，数据并行指同时对多个数据单元进行 相同的操作，指令并行指同时对单个数据单元进行多个不同的操作。在图形处理 器的设计中，根据各个单元承担的任务的特性分别应用了不同的并行机制，如整 个流水线式的结构就采用了任务并行的机制，变换单元和渲染绘制单元采用了数 据并行机制。 流水线式的结构和并行计算的特性使图形处理器具备了高效的图形处理能力， 为了使图形处理器的功能具有更大的灵活性，现代图形处理器开始引入可编程功 能，该功能使开发者可以开发出运行自己的算法的图形渲染引擎。目i j i ，图形处 理流水线中的变换单元和渲染单元分别具备了顶点编程和象素编程的功能。 总之，图形处理器无论是所承担的任务还是对任务执行效率的要求，都与计 算机中的中央处理器不同，因此需要不同方式的计算和数据传输模型，而流计算 模型是适用于现代图形处理器并且被广泛采用的计算模型。 4 实时图形处理关键技术研究 1 1 2 流计算模型 k a p a s i 等人提出的流式程序设计模型【2 q # 常适合于对计算效率和数据传输效 率要求较高的应用，因此该模型成为现代图形处理器的计算模型的基础。流式程 序设计模型应用到图形处理器中称为流计算模型。在流计算模型中，相同类型的 数据被组成一个有序的数据集合称为流。流中的数据类型可是简单的，如整数或 者实数，也可以是复杂的，如顶点、三角形或者变换矩阵等。流中的数据根据表 示内容的不同组合成多个数据单元，如顶点数据流中，表示顶点坐标的四元数组 组成一个数据单元。流可以是任意长度，并且流的长度越长，即流中的数据越多， 对流的操作效率越高。对流中的数据单元施加的操作称为核操作，核操作可以是 对流中数据的复制、分割、索引以及计算。典型的核操作就是求解以流中的数据 为输入参数的函数值，如变换单元中坐标变换核操作可以计算出顶点在不同坐标 系中的坐标值。 核操作的输出只与输入有关，并且对同一个数据流中的不同数据单元进行同 一个核操作时，不同数据单元互相不影响。这个特点保证了对数据单元进行核操 作前已知所有输入数据，通过仔细处理核操作过程中产生的临时数据，可以获得 较高的执行效率，同时核操作的这个特点也便于硬件实现。 基于流式程序设计模型的应用通常将多个核操作串行地组织到一起完成一项 复杂的任务，图形处理器的流水线式的结构和单元之间数据相对独立的特点，使 得图形处理流程非常适合用流式程序设计模型描述。在图形处理器的流计算模型 中，每个单元的任务被划分成不同的核操作，如顶点输入核、三角形装配核、裁 减核等，如图1 3 所示。 f i g 1 3m a p p i n gt h eg r a p h i c sp i p e l i n et ot h es t r e a mm o d e l 图1 3 用流计算模掣表爪的图形处理流水线 图形处理器利用流计算模型获得了高效的计算和数据传输能力，流计算模型的 最大优点就是充分利用了并行处理机制中的数据并行和任务并行来完成不同任务。 另外，将复杂的计算任务划分多个核操作，而每个核操作都可以由专门的硬件完 成，这样可以获得更高的执行效率。在数据传输能力方面，将多个数据单元合成 第一章绪论 为一个数据流减少了数据传输过程中初始化的次数，提高了从计算机主存向图形 处理器传输数据的效率。多个核操作链接在一起的工作方式，使各个核操作产生 的数据不用传输到存储单元，直接转交下一个核操作进行处理，提高了图形处理 器中的数据传输效率。 本文的部分工作以可编程图形处理器为基础，通过将图形处理中的一些任务 分配到图形处理器一端，并通过可编程单元执行所需算法，充分利用图形处理器 高效的计算和数据传输能力，实现一些对实时性要求较高的应用。 1 1 3 互联网中的图形处理系统 互连网中图形处理系统的关键是传输子系统的设计，如果解决了传输问题， 剩余的任务与计算机图形处理系统的流程相同。图1 4 所示为互连网中图形处理系 统的结构简图。如图1 4 所示，互联网中的图形处理系统分为两种类型，即b s 结构 的应用和c s 结构的应用。基于b s 结构的应用系统中的图形数据通常需要表示成 标准的格式，如v r m l 或者j a v a 3 d 等，相关技术称为w e b 3 d 技术。基于c s 结构的 应用则不受此限制，可以选择适合应用特点的图形表示形式，甚至将一些通用的 数据保存在客户端，对于大型的网络三维图形系统，通常采用c s 结构。 d i t e e t x _ 竺坚， d 卸l a y f i g 1 4 as i m p l i f i e dg r a p h i c sa p p l i c a t i o np i p e l i n ei ni n t e m e t 图1 4 且联网中的图形应用系统流程简图 由于互联网中数据传输带宽从每秒几个字节到几兆字节不等，并且随着在线 人数的增加不断变化，为了适应互连网带宽的特点，基于互联网的图形应用系统 中通常引入渐进式传输技术，所谓渐进式传输是指将图形数据按分辨率从低到高 依次传输，并且不重复传输低分辨率图形中的数据，高分辨率的图形由最低分辨 率图形加上多个模型细节数据组成。 本文在网络图形处理系统方面的工作主要解决几何数据的渐进式传输问题， 包括二维矢量地图数据的传输和三维几何模型数据的传输。 1 2 几何模型 计算机图形学中的几何模型由点、线、面等基本几何元素和属性信息组成， 其中由几何元素表示的部分称为几何模型的形状，由属性信息表示的部分称为几 6 实时图形处理关键技术研究 何模型的外观。几何模型根据几何元素的维数分为二维和三维几何模型， 何模型主要用于二维图形应用系统，如工程制图和矢量地图相关的应用， 何模型的应用更广。 二维几 三维几 几何模型的形状描述了物体所占据的空间。二维几何模型的形状通常由参数 曲线、隐函数曲线、代数曲线和多段线表示，在工程制图相关的应用中为了精确 描述形状，常常采用直线段、参数曲线和隐函数曲线。在与矢量地图相关的应用 中，由于地图对象的形状多样性和复杂性，常常采用多段线来表示地图中的对象， 因此一幅高精度的矢量地图中含有大量的线段，矢量地图的多分辨率多尺度表示 就成为需要解决的问题，本文第二章的工作就是研究了这个问题。 三维几何模型相对二维几何模型更加复杂数据量更加巨大，其描述形状方法 也很多，如体素表示法( v o x e lr e p r e s e n t a t i o n ) 、c s g ( c o n s t r u cs o l i dg e o m e t r y ： c s g ) 树表示法以及边界表示法( b o u n d a r yr e p r e s e n t a t i o n ：b r e p ) 等等。其中 边界表示法是应用最为广泛的一种方法，这也是本文所研究的一个主要对象。在 边界表示法中，物体的形状信息是通过它的表面来描述的。而物体的表面又可以 有各种各样的表示方法，如参数曲面、代数曲面、隐函数曲面以及多边形网格等 等。本文的研究对象为多边形网格。 点模型是近几年才被深入研究的一种新的三维几何模型表示方法，由于这种 模型表示方法与基于三角网格的表示方法不同，不用记录基本几何元素之间的拓 扑关系，从而降低了几何模型数据的存储空问，又因为该方法省略了光栅化的过 程，从而提高了处理效率，目前出现了很多相关的研究工作。点模型也是本文的 一个研究对象。 几何模型的外观则描述了物体上的入射光线和出射光线之间的相互作用关系。 本质上它是物体本身固有的一种物理性质。但是在计算机图形学中，我们常用一 些易于理解的光照模型来描述颜色、光泽度以及透明度等属性。在真实世界中， 有的物体表面细节极为丰富，光照特性极其复杂。为了描述这些复杂的物体表面， 针对不同类型的物体，人们研究了多种更复杂的外观表示方法，如双向反射函数、 纹理映射、凹凸纹理映射、双向纹理函数等等。本文工作未涉及此方面的内容。 1 2 1 二维折线模型 设平面上n 个点p ，p ：，p 。顺序排列，又设巳= a 仍，p 2 = p 2 p 3 ， e 。= p - i p 。是连接点的n 一1 条线段，那么这些线段当且仅当， ( 1 ) 排序中相邻线段对的交是它们之问共有的单个点，即e ，ne i + 。= p 。： ( 2 ) 不相邻线段不相交，即e ， h e ，= 中，f 0 时，子多段线以，珞l ，一，矿， 才可简化为线段 矿。矿。，多段线的简化算法就是在一定的误差数值s ，0 的条件下，获得尽可能少 的简化线段。由于矢量地图的应用特点，简化集合中的顶点均由原子分集合的顶 点组成。 2 1 3 单纯形与单纯复形 单纯形是拓扑代数中的概念，最早被f l o r i a n i 6 i 用来描述三维几何压缩问题，本 文以之为基础描述了矢量地图中的多段线简化问题。 定义2 1 设a o , a j ，胡。是欧氏空间中几何不相关的点组，集合 吒= ：。 n ，i 五o ，：。 = 1 给于r 。的子空间拓扑称为n 维单纯形。若6 0 b 1 ，k 是单纯形o n 的顶点组a i ，吒的子集，9 l u b o ，b l ，k 仍是几何不相关的点，它们所 展成的单纯形称为a 的面。口 显然，0 维单纯形( ) 为一个点，一维单纯( a o ，q ) 为线段，二维单纯形( ，q ，口：) 为三角形，三维单纯形( a o ，a ，a ：，吒) 为四面体，疗维单纯形是三角形，四面体在高维 情况下的推广。三角形可由三个不共线的点展成，四面体可由四个不共面的点展 成。 定义2 2 单纯复形k 是有限个欧氏空间中的单纯形的集合，其中的单纯形满 足： ( 1 ) 若吒k ，则d 。的任何一个面k ： ( 2 ) 若吒，2 r k ，则吒nz r 或是空集或是公共面。 口 矢量地图主要由多段线集合构成，多段线是多个l 维单纯形( 也就是线段) 组成的 实时图形处理关键技术研究 单纯复形。为了用单纯复形进行多段线集合的多分辨率表示，我们在单纯复形的 基础上定义了修改和非冗余修改两个概念。 定义2 3 设k 是一条多段线，吒和盯，是它的顶点集合的一个子集，即以，i rck ， 如果二者边界相同，则用其中一个替换另一个的过程称为修改，可以表示为 m = ( ，) 或者m = ( o ，a n ) 。口 定义2 4 对于修改m = ( ，0 ) ( 或者m = ( f ，吒) ) 来说，如果o n 和c r r 中不含除边 界之外的相同单纯形，则该修改称为非冗余修改。也就是说对一个多段线应用非 冗余修改肘后不会重新生成被删除的线段。 口 图2 2 中所示的是两个修改肘。和肘：，其中修改m 。为非冗余修改，修改m ：则是 冗余修改，因为在修改m ，中多段线一含有多段线一：中的线段。 修改是可逆的，修改m = ( 0 - 1 盯2 ) 的逆可以表示为m 一= ( o - 2o - 1 ) 。如果# o r l # 口2 ， 修改m = ( d j ，盯2 ) 称为简化修改，它的逆称m 。= ( 0 - 2o j ) 为复原修改。 为了方便， 一般用m 一表示修改m 中线段数少的多段线，而用m + 表示修改肘中线段数多的多段 线。 f i g 2 2n o n - r e d u n d a n tm o d i f i c m i o na n dr e d u n d a n tm o d i f i c a t i o n 幽2 2 非冗余修改与冗余修改 多段线是组成矢量地图的子分集合的主要元素，它由一维单纯形线段组成，而 线段的顶点为0 维单纯形，因此矢量地图可以看作一个由大量0 维单纯形和一维单 纯形组成的集合，对矢量地图的多分辨率表示就是对这些单纯形的处理。 2 1 4 矢量地图的渐进式传输 f i g23s e l e c t i o n ：g r e yp a r t so f s m a l l e rs i z ei n i e f tm a pd i s a p p e a ri nr i g h to n e 图2 3 地图对象的选择，灰色区域所小的小尺寸对象在右边的地图中小出现 与多分辨率表示一样，在矢量地图的渐进式传输中，首要的问题是保持不同尺 第二章单纯复形与矢量地图的多尺度表示 度的地图中的元素之问空问关系的一致性。其次就是地图对象的选择问题，即一 些小尺寸的地图对象在高分辨率的地图中出现，而在低分辨率的地图中不出现， 如图2 3 所示。渐进式传输的最后一个要求是尽量减少传输过程中的冗余数据。 2 2 相关工作 本节回顾已经出现的与矢量地图的简化、多分辨率表示以及渐进式传输相关的 主要研究工作。 2 2 1 矢量地图的传输 在互连网中对矢量地图进行渐进式传输的最直接的方法就是在服务器一端保 存不同分辨率的地图数据，对于在每个分辨率的地图中都出现的数据都是单独存 储，而不是在每个分辨率的地图数据中重复存储。b e r t o l o t t o 和e g e n h o f e r 在他们工 作【7 】【8 1 1 9 1 1 0 i 中提出了一个矢量地图渐进式传输的策略，在他们的方法中主要使用归 纳操作修改地图元素的拓扑关系而进行地图简化与多分辨率表示，由于多段线的 简化比较费时并且可能导致空间关系的不一致问题，他们的方法中没有使用多段 线简化算法。 f i g ，2 4g e n e r a l i z a t i o no p e r a t o r s 图2 4 修改拓扑关系的归纳操作 修改拓扑关系的归纳操作如图2 4 所示，图2 4 中( a ) ( b ) ( e ) ( f x g ) 的情况实际为地图 多分辨率表示中的选择操作，即地图对象由于尺寸较小而在低分辨率的表示中不 出现，而图2 4 ( c ) ( d ) 所示的操作并不能较大地减少数据量。 多段线简化可以很大程度地减少较低分辨率表示中的数据量，如图2 5 所示。 本文将多段线简化技术应用到矢量地图的多分辨率表示，同时用r e a c t i v e - t r e e l 4 1 表 示选择操作。 实时图形处理关键技术研究 ( a )( b )( c ) f i g 2 5 t h r e ep o l y l i n e sw i t h3 7 8v e r t i c e s ( a ) ，1 8 6v e r t i c e s ( b ) a n dw i t h9 5v e r t i c e s ( c ) 图2 5 三个不同分辨率的多段线及其顶点数星 2 2 2 多段线简化 在g i s 、计算机视觉以及计算几何的研究工作中均涉及多段线简化问题，在与 应用相关的多段线简化算法中总是希望在线性或者近似线性时间内获得问题的解， 而计算几何中，多段线简化的研究目的大多是获得一定条件下的最优解，这些条 件可能是给定简化线段的数量获得最小的误差，或者给定误差获得最少线段数， 计算几何中这类算法的时间复杂度通常为o ( n 2 ) 或者o ( n 3 ) 。e s t k o w s k i h 】【”1 的工作 证明在多项式时间内获得多段线简化的最优解是困难的。 d o u g l a s 与p e u k e r i b 】在1 9 7 3 年首先提出了多段线简化算法d o u g l a s p e u k e r 算法， 该算法在多段线简化过程中可以保持多段线的重要特征，因此在矢量地图的简化 中得到广泛的应用。但是，d o u g l a s p e u k e r 多段线算法不能保证地图简化过程中的 拓扑一致性，即存在简化的多段线自相交相交、相交和相对位置改变等现象，如 图2 6 所示。 ( a )( b )( c ) f i g 26i n c o m p a t i b l et o p o l o g i c a lr e l m i o n s h i p sa c c r u i n gi np o l y g o n a lc h a i ns i m p l i f i c a t i o n 图2 6 折线简化算法中拓扑不。致现象 为了克服多段线简化过程中出现的拓扑不一致现象，d e b e r g 等j k i 1 通过计算 一些特殊点并在多段线简化过程把它们简化掉而保证了多段线简化过程中的拓扑 一致性，其时间复杂度为o ( n 2 ) 。m u s t a f a 等) k 1 1 5 1 提出了一种基于v o r o n o i 图的方法， 该方法利用图形硬件进行v o r o n o i 的计算，其计算效率较高。然而这两种方法仍 然不能很好地处理自相交的情况。为了解决这个问题，m a n t l e r 等人【1 6 l 也提出了一 第二章单纯复形与欠量地图的多尺度表示 种基于v o r o n o i 图的多段线安全集简化算法，该方法可以有效地避免多段线简化过 程中的自相交情况的出现，它首先计算组成矢量地图某个子分中所有多段线的顶 点集合的v o r o n o i 图，再计算多段线的安全集，最后对安全集应用d o u g l a s ，p e u k e r 算法而获得整个矢量地图的简化表示。该算法中计算点集v o r o n o i 图的算法的时间 复杂度为0 n l o g n ) ，计算多段线的安全集的算法的时问复杂度为d ( n ) ， d o u g l a s p e u k e r 算法的时间复杂度为o ( n 2 ) 。由于多段线简化算法的时间复杂度较 高，如果由大比例尺矢量地图实时生成小比例尺的矢量地图其效率必然降低，因 此本文的方法没有采用实时矢量地图的多分辨率表示方法，而是使用多分辨率模 型，通过一个预处理将不同分辨率的局部模型区域保存在一个集合中，运行时根 据需要快速地选择不同分辨率的模型数据。 2 2 3 地图对象的选择 在较早的g i s 应用中，大量采用空间索引技术【1 7 】解决范围或者空间查询问题， 除 o o s t e f o m f 4 l 提出的r - t r e e 结构和h u t f e s z 等人【1 8 l 提出的p r - f i l e 结构，其他空间索 引技术可以有效地获得给定区间的地图对象，但是不适用于地图的多尺度表示。 在o o s t e r o m 4 】提出的r t r e e 结构中每个地图对象被分配了一个重要性系数，具有 相同重要性系数的地图对象被保存在r t r e e 结构中的同一层，r - t r e e 是一种非平衡 树结构，根据不同的重要性系数，就可以获得不同比例尺下的地图对象，该结构 解决了地图对象的选择问题，但是没有考虑地图的简化问题。在r t r e e 的基础上 e d w a r d 等人f 5 】提出了多比例r t r e e 结构并引入多段线简化算法，在他们的算法中， 一个改进的d o u g l a s p e u k e r 算法被用来计算每个多段线顶点的重要系数，重要系数 相同的顶点和它们的重要系数一起保存在r t r e e 的相应层中。与多比例尺r - t r e e 类似，h u f f e s z 等人【1 8 】提出了p r - f i l e 结构，该结构中也用到了多段线简化算法，与 多比例尺r - t r e e 不同之处是p r f i l e 结构中的最小存储单元是多个地图对象的集合， 而r t r e e 中的最小存储单元为单个地图对象。然而在这些方法中部未考虑简化过程 中的拓扑改变问题。 本文算法首先根据地图对象的不同尺寸将他们划分成多个不同重要性的组，每 个地图对象分配一个重要性数值，每个重要性数值对应r e a c t i v e t r e e 结构中不同的 分辨率等级。同时采用改进的m a n t l e r 安全集方法作为多段线简化算法，避免了多 段线简化过程中的拓扑不一致问题。多段线简化的结果被保存在一个以单纯复形 原理设计的数据结构中，该数据结构作为基本的存储单元与它的重要性系数一起 保存在r e a c t i v e t r e e 结构中。 实时图形处理关键技术研究 2 3 矢量地图渐进式传输的c s 结构 图2 7 所示为矢量地图渐进式传输的结构，该结构的设计原则为首先传输低分 辨率地图数据，然后传输高分辨率的地图数据，在同一个分辨率的地图数据中， 首先传输重要性高的地图对象。因此图2 7 所示的服务器一端的地图数据库示意图 中，从上到下分辨率降低，从左到右重要性降低。服务器一端负责响应客户端请 求，产生不同分辨率和重要性的数据并将这些数据发送到客户端。客户端接收数 据并进行显示更新。 q 、 ( 够) ( 、 - ph 硎3 p n 订门 f i g 2 7r e p r e s e n t a t i o n sa td i f f e r e n ts c a l e sa r em a i n t a i n e do nt h es e r v e ra n d t r a n s m i t t e d t o t h ec l i e n t i no r d e r o f i n c r e a s i n g d e t a i l 图2 7 服务器端保存的小同尺度的地图数据被渐进地传输到客户端 2 4 矢量地图的多尺度表示 单纯复形最早用在三维网格模型的多分辨率表示中【1 9 】，后来f l o r i a n i 等人【6 】【2 0 】 系统地分析了单纯复形在三维几何模型多分辨率表示中的应用。矢量地图可以看 作二维多段线的集合，它可以看作多段线和非冗余修改的集合，它不但包含每个 多段线的多分辨率表示，还包含这些不同分辨率多段线之问的相应关系，利用这 些关系我们可以构造出所需分辨率的矢量地图。 在多段线的简化过程中，它的一个予多段线被拥有公共端点但是更少内部顶点 的简化多段线代替，该过程可以看作对原始多段线的一个修改，由于修改是可逆 的，可以从简化多段线重构出原始的多段线。假设一个简化多段线c r o 和一个由修 改组成的集合 m ，m ：，m 。) 为矢量地图中一个多段线p 的多分辨率表示，对于其中 任意一个线段r m i ，i = l ，h ，要么，c r 0 ，要么y 肘j ，i j ，且仅存在一个肘j 满足该条件。两个修改之间的关系可以用基于拓扑的依赖关系表示，如果修改m ， 第二章单纯复形与灭鼙地图的多尺度表示 去除了由修改肛产生的一个或多个线段，则称修改肘，依赖于m i ，如图2 8 所示。 也是说，如果一个或多个线段同时属于多段线m j 和m 7 ，则m j 依赖于m 。图2 8 旦一， 迫气届与厂 f i g 2 8m 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 no f ap o l y l i n e 图2 8 折线的多分辨率表示 中的修改m 依赖于肘，。 如果依赖关系的传递闭包 是偏序的，则三元组肘= ( 矿， 膨l 一m 。) ，q 为多分 辨率多段线，其中c r o 为最简多段线，集合 肘l ，m 。 中的修改可以提高其分辨率。 且原始多段线可表示为仃o u m ? i i = 1 9 - h 。整个矢量地图的多分辨率表示就是由 这样的多分辨率多段线的集合组成。 单个多分辨率多段线可用偏序关系的h e s s e 图表示成一个有向非循环图，其中 节点表示修改，弧线表示修改间的直接依赖关系。图2 8 中的修改可表示成图2 9 中 所示的有向非循环图。 一一 l 一 眦 一= 一- 一- 一，- 。_ 一一， f i g 2 9t h ed a go f ap a r t i a lo r d e rd i r e c td e p e n d e n c yr e l a t i o nb e t w e e nm o d i f i c a t i o n s l 玺| 2 9 修改之问偏序关系的有向非循环图 将修改集合 肘l m 。 中的修改按与全序扩展相对应的次序应用到最简多段 线a o 上，可以获得原始多段线。而中问产生的一些线段的集合就是原始多段线的 不同分辨率表示。对于修改集合 m i ，肘。 的一个真子集s ，如果其中的每个修改 m 。s ，它所依赖的修改m ，s ，( f ，) ，则称s 为闭合的。将闭合真子集应用于 最简多段线c r 0 上，可以获得不同分辨率的多段线。 多段线的多分辨率表示中必须明确修改和偏序关系的数据结构，由于最简多段 线的数据量较小，可以使用一些标准数据结构，如数组表示。下面的内容主要介 绍获得最简多段线的方法、修改的数据结构以及偏序关系的数据结构。 为了计算数据结构的空间复杂度和查询操作的计算量，需要明确多段线多分辨 o 实时图形处理关键技术研究 率表示肼= ( 盯o ， m ，m ， ) 中的以下几个参数， ( i ) 修改的数量h ： ( 2 ) 全部修改中线段的总数c ，即一维单纯复形集合的基数u h ：( ，i u ，? ) (