（计算机应用技术专业论文）基于细分策略的三维模型多分辨率分析.pdf

萋子细分策略的三维模型多分辨事分析 摘要 随着三维模型数据采集工具的不断发展，我们所能采集的模型数据也日益精 细，伴随而来的就是模型数据量和复杂程度的急剧增加如何使用育效的算法来 表示三维模型，从而降低三维数据的存储量，减轻三维模型的网络传输负荷，提 高三维模型的可视化效率，就成为了计算机图形学领域中一个重要的研究方向。 通常情况下，三维模型般采用多边形网格来描述，其中，三角面片在任意 拓扑益面的表示中有着广泛的应用。对一个粗糙的三角西片曲面，我们可以使用 l o o p 细分算法使其逐步逼近光滑的极限曲面，这个过程类似于多分辨率分析理 论中的合成操作。多分辨率分析是近年来提出的三维网格图形处理的新方法，它 可以把复杂的三维图形分解成轮廓信息和图形细节，进而给出三维图形在不同分 辨率下的表示方式。多分辨率分析的个重要工具是小波，将小波和细分算法相 结台，构造细分小波，用予细分曲面的多分辨率分析是一个崭新的研究方向。它 根据不同细分算法的固有特征，对应于曲面简化和细化的双向处理，构造出多分 辨率分析中的分析与合成过程。细分小波的出现，为三维曲面多分辨率分析开辟 了新道路，一些经典细分算法的细分小波也进入了研究阶段。 本论文主要针对具有细分连通性的三角曲面进行研究，给出了完整的l o o p 细分曲面多分辨率分析的方法和实现。首先，论文对曲面细分算法和三维曲面多 分辨率分析的研究背景进行了系统的回顾，介绍了l o o p 等经典的曲面细分算法， 概述了多分辨率分析的基本原理和应用背景同时也就近年来三维曲面多分辨率 分析领域的发展和前景进行了讨论。在缭合l o o p 细分算法和小波提升算法的基 础上，本文构造了一种完楚的三维曲面多分辨率分拆方法( l o o p 细分小波) ，不 仅包括了三维几何数据的分析与合成，更对曲面的拓扑信息进行了相应的处理， 并提供了开放曲面边界上的解决策略。本论文除了对该多分辨率分析方法进行详 细阐述外，也给出了它在具有l o o p 细分连通性曲面上的实现算法和误差度量。 本论文的主要贡献包括：应用局部细分矩阵替代完整的细分矩阵进行分析处 理，在局部的细分掩模上进行计算，有效邀避免了求解大型线性方程纽而带来的 庞大运算量；使用了基于顶点度数的简易策略，去解决曲面多分辨率分析过程中 的拓扑信息重建问题，增强了多分辨率分析方法的实用性；本论文的多分辨率分 析方法的应用对象不局限于翅合三维曲蕊，更使用于开放的三维曲面，它对开放 曲面的边界进行了特殊处瑷，有较强的通用性。 本论文描述的多分辨率分析方法，适用于具有细分连通性的三角曲面。这不 仅为三维曲面可视化和压缩提供了新的思路。而且也扩展了窄带信道下三维图形 传输的研究方法。为了更好地观察该研究方法的效果，我们在计算机上实现了 l o o p 细分曲藤的多分辨率分析算法。算法程序对v r m l 格式的三维数据进行处 理，生成了可视化的实验样例。通过对实验结果的数据分析，我们得出了算法的 定量评估和定性分析。而这些实验数据对今后曲面多分辨率分析方法的研究也具 有一定的参考价值。 关键词：l o o p 细分曲面，多分辨率分析，提升算法，细分小波，拓扑重建 基于细分策略的三维模型多分辨率分析a b s l r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fs a m p l i n gt o o l sf o r3 dm o d e l ，w cc a l lo b t a i n3 dm o d e ld a t ai n i n c r e a s i n gd e t a i li n f o r m a t i o n i ta e e o m p 枷e sw i t hag r t td e m a n do i ls t o r a g ea n dc o m p l e x i t y h a n d l i n g l h e r e f m - e ，i th a sb e e o m oas i g n i f i c a n ti s s t ki nc o m p u t 口g l 砷b i ct h a th o wt op r e s e n t3 d m o d e ii n e 伍c i e r 吐w a y bt or e d u c es t o r a g es i z e , l a w b u r d e nf o rn e t w k t r a m m i s s i o n , a n d i m p r d v ee f f i c i e n c yo f v i s m l i z a t i o n i ng e n e r a l 3 dm o d e lc a nb ep r e s e n t e di np o l y g o n a lm e s h a n d t r l a n e , l cm e s h i so t o f t h e m o s ti m p o r t a n tp o l y g o n a lm e s h e s ，w h i c hh a sb e e n w i d e l yu s e di nm e s h e s w i t ha r b i t r a r yt o p o l o g y w ec a ne m p l o yl o o p $ t l b d i v i s i o nm e t h o dt or e f i n eac o e u s em e s ht oi t sl i m i ts 响w i t h s a t i s f a c t o r y s m o o t h n e s s t h i s p r o c i s s i m i l a rt o s y n t h e s i s i nm u l t i t e s o l u t i o a a n a l y s i s m u l t i r 既o l u t i o na n a l y s i si san o v e l 印芦o a c hi nm e s hp r o e e s s i 蟮i tc 田lp r o v i d em e s hi nw i r i o u s r e s o l u t i o nb yc l t , o m p o s em e s hd a t ai n t oo u t l i n ei n f o r m a t l a aa 耐d e t a i l s s i n w a v e l e ti sa 弘i m r yt o o lf o rm u l t i r e s o l u t i o na n a l y s i s , w e 髓l ic o n s t r u c ts u b d i v i s i o nw a v e l e tf o rs u b d i v i s i o n s u r f a c ea n a l y s i s t h ea p p e a r a n c eo fs u b d i v i s i o nw a v e l e t 删y “i v m t h ed e v e l o p m e n to f m u l t i r e s o l u t i o na n a l y s i sr e s e s r c hf o r 日白a n di ti l a sb e e ng e n e r a l i z h lt os p i t l es u b d i v i s i o n m e t h o d s i nt h i st h e s i s mp r e s e n tf i l li r t t a e tm u l t i r e s o l u t i o na n a l y s i sa p p r “t c ho fl o o ps u b d i v i s i o n b a s e do i lm h w i t hs u b d i v i s i o n e o n a e c t i v i t y f i r s t , t h e 删p l o a n d b a e k g r o u n d o f m u l t i r e s o l u t i o nm i y s i sa n ds u b d i v i s i m amr o v i e w e d t h 呱md i s c u s s e ds o h i i c l l l f l 血 s u b d i v i s i o nm e t h o d ga n dt h ed e v d o p m l m to fm u l t 矗e s u l o t i o na n n l y s i s b yc o m b l n l n 8l o o p s u b d i v i s i o na n d l i l t i n gs c l l e l m e ，w eb r m g f o r t h 姐i n t a c tm e t t l o d , i n c l u 曲唱s e o m e t r yd a t aa n a l y s i s a n d t o p o l o 科p r o c e s s i n g , f b r m u l t i r e s o l u t i o n a n a i y s i s o n l o 叩s u b d i v i s i o n s u r f a t o h n n d l c o p m e s h , o v t ：c o n c e i v eas t r a t c g yf o rb o l m c l a r y 芦u 路缸孚l 垴i d e sd l 吐a i l e di l l m t r t a i o no f t l 曹a b o v e a p p r m l e h , t h i sa r t i c l ea l s op r o v i d e s t h e i ri m p l e m o n t a t i o no ns u 由w i t hlo o ps u b d i v i s i o n e o n n e c t i v i t y , a n da - t o rm e to f e x p e r l m e n t r u l t s n m a i nc o n t r i b u t i o n so f t h i sa r d e l ea r e f o l l o w s w es u b s t i t u t el o a ds u l x l i v i s i m a t r i x 妇g l o b a ls u b d i v i s i o nm a t r i xi nd a t au l y s i s u s 啦l o e s lc o m p u t a t i o n o ns u b d i v i s i o nm a s km e e t i v e l yd e c r e a s e t h ec o m p u t a t i o nc o s tb r o u 出b ys o l v i n ga b i gl i n c 口s y s t e m o t ra p p r o a c h 妇 t o p o l o g yr e c o n s t r u c t i o ni sb a s e d v a t v a l e n c e , w l a i c hm 妇i t 1 1 1 1 1j n l 枷v oa n d 掣t o i m p l e m e n t t h em u l t i r e s o l u t i o na n a l y s i sm e t h o dm m t i o n o di nt h i sa f t i e l ei sn o tr e s t r i e t m lt oc l o s e m e s h e s ，i t 啪b eg e n e r a l i z e d 协m e s h e sw i t hb o u n d a r y l l a cs l r a t 啊f o rb 日l 血r yl h o e e s s i n g b r i n g se o m p a t i b i l i t y t ot h i sm e t h o d t h om u l t i r o l u l i o na n a l y s i sa p p r o a c hp r e s e n t e di nt h i sl r t i e l e 咖b ei i 】p l i e dt ot r i a n g l e m e s hw i t hs u l x l i v i s i o nc o n n e c t i v i t y i tn e to n b ，s l m d sl i e , h t 蚰t h er e a r e hf o rm e s hv i s u a l i z a t i o n a n dc o m p r e s s i o n , b u ta l s ob r o a d e n sl l l t e e l m i q u e sf o rm e s ht r a m m i s s i o no v e r - n a l t o wb a n d n e t w o r k t oo b t a i n i n t u i t i v er e s u l to fo u ra p p r o a c h , w ci 唧l e n tm u l t i r e l o l u t i o na n a l y s i sf o r l o o ps u b d i v i s i o ns u r f a c ei nc o m p u t e t h es o t l m t r ep r o c e s sv r m li n p ma n dd i s p l a yv i s u a l p r e s e n t a t i o no fm e s h e si nv a r i o u sr e s o l u t i o n w ea l s oe v a l u a t et h ea p p r o a c hb ya n a l y z i n gt h e o l d p u td a t a t h i sd a t aw o u l dp r o v i d e v a l u a b l ei n f o r m a t i o n 蛔t h ef u t l nl - i t r c hi nm e s h a n a l y s i s k e yw o r d s ；l o o ps u b d i v i s i o ns u r f a c e , m u l t i r e s o l u t i o na n a l y s i s , i i e d r l ss c h e m e ，s u b d i v i s o n w a v e l e t , t o p o l o g y r e c o n s t r u c t i o n 一 基于纲钟点略嚣三雏模型多分辨事分析 第1 章缝论 1 。 研究背景 第1 章绪论 随着计算机软件硬件技术的发展，在兰维图形学、计算机辅助设计、地理信 息系统和医学影像系统中所能构造与应用的几何模型越来越精细和复杂。我们可 以使用三维扫描仪( 3 ds c a m e r ) s nc t 等设备获取逼真的几何数据。然丽。在精 确表示模型的同时，用来描述这些几何模型的数据量也越来越庞大，动辄就有数 以百万计的曲面片。最著名的例子是s t a n f o r d 大学d i g i t a lm i c h e l a n g e l op r o j e c t 该项目借助三维扫描硬件和三维重建软件完成了整座d a v i d 雕像的数字化过程， 单是生成的三角西片就离达2 0 亿个i l 】一方面，这些大规模复杂的三维几何模 望f 对计算机的存储容量、图形处理能力都提出了更高的要求另一方面，三维可 视化系统正逐渐向互联网平台发展，而目前的网络传输速度远远不能满足大规模 三维几何模型实时传输的需求因此对数字几何中大规模三维几何数据的表示 和传输的研究，就成为了目前计算机图形学中的熟点。 秭( c ) 图1 1 ( a ) 三维扫箍( b ) 头像熙琦( c ) 头像几何模型 基于细分案略的三维模型多分辨率分析第l 章绪论 近年来，曼维几何模型计算领域的研究有了长足的进步，也取得了许多有实 用价值的研究成果，但仍有相当大的研究空间，如：几何模型的多分辨率表示和 存储，凡何模型简亿，几何模型编码，几何模型的颤进传输等。这些方面的研究， 为解决三维图形学应用中的关键问题指引了方向 1 1 1 几何压缩和存储 新的造型工具和模型重建技术为我们带来了更加精细的三维几何模型，同时 也产生了急剧增长的数据量和模型的复杂程度利用这些工具得到的模型通常非 常复杂，包含的三角形数目巨大，绘制如此复杂的网格模型通常是十分困难的， 现有的图形硬件处理能力也往往无法满足绘制实时性的要求，而高性能的图形工 作站价格十分昂贵，并非广大用户所能承受翔何在计算机中有效地存锗几何模 型，优化模型的处理和显示，是计算机图形学中一个极具实用意义的课题 三维几何数据量的日益增长，应用计算机进行图形处理会遇到许多方面的难 点：一个较为复杂的三维模型，其数据量可从几硼b 到效酉m b ，模型数量的增 加就带来了海惫的数据，它对外存设备的存储容量是一个严峻的挑战；图形适配 器的内存有限，尽管可以使用a g p 技术和其它存储交换技术来扩展适琵器的处 理能力。然而现有的三维图形处理能力还远远未能满足复杂三维模型的处理要 求，难以加载和处理完整的三维模型数据；高级的三维图形处理如；曲面交互 编辑，三维动孺显示，造理信息系统，模瑟动态仿真等，在计算机辅助设计与多 媒体领域都有着广泛的应用，而这些应用很大程度上受獭 于模型的数据靓模。模 型的一个简单的变动也可能带来数据量的成倍递增并且影响模型的实时显示效 粱。 考虑这些实际的目题，人们针对凡何模羹的存穰方式进行了深入研究，尝试 通过有效地处理存储瓶颈，来改善实时绘铡的效率与效果在众多解决方案中， 实际应用意义较大的主流方法有三种z 几何模型编码与压缩；几何模型简化t 几 何模型的多分辨率分析与存储 众所周知，缀过数千年的研究和发展，= 维图像的编码与压缩已经逐渐走向 成熟小波分析工具在图像处理领域的应用，令图像压缩技术有了历史性的飞跃， 从j p e g 到j p e g 2 0 0 0 。- - 维多媒体数据的表示方式正在不断完善相比之下， 尽管几何压缩的研究学者在近几年来取得了激动人心的进展，但其理论和应用框 架还显得非常年轻，无法满足工业界日益增长的蠢求几何编码的最终目的是， 通过对几何模塑执行与图像压缩类似的处理，来降低用于表示模型的数据量。从 而解决存储方面和显示方面的性能要求其中，比较关键的技术问题燕如何对三 维几何模型进行编码与传统的二维数字豳像不同，几何模型的数据一般采用描 述几何特征的图元( 顶点，边，面片) 来定义，因此不能像图像压缩那样使用矩 阵方式去处理。另一方面，除了坐标数据，几何模型还包含了拓扑信息来描述几 何实体之间的关联，这又为几何编码的实现增添了难度。数字图像压缩可以提供 有损的方式和无损的方式，灵活地满足用户的需求，但是在几何压缩领域，被压 缩的几何实体和拓扑信息的重要性可能不相等，同样的压缩策略在几何压缩中未 基于细分策略的三维模型多分辨率分析第l 章绪论 必能带来理想的压缩比和压缩效果，而有损压缩如果处理不当，极可能导致整个 三维模型的走样，因此有必要为三维几何数据研究专用的压缩算法。这些方面， 是几何编码和压缩过程中的关键问题。 几何模型简化是另一个提高模型处理性能的有效方法。它在保持模型的几何 外型不变的前提下，通过牺牲细节信息来换取高效的图形处理性能。目前，高精 度的扫描测绘手段，为复杂物体基于多边形网格表示的三维几何建模提供了高效 的手段。由于采样精度高，由此建立起的三维模型的复杂程度，也远远超过了当 前计算机图形工作站的实时处理能力。不过在很多情况下，人们并不需要对物体 的每个细节都刻画得非常详细。因此，我们可以在保证模型完整性的基础上，有 选择地放弃部分的几何信息来减少模型的接体数据量，降低模型处理的性能要 求。这就是几何模型简化研究的出发点，采用适当的算法来减少模型显示所需的 数据量，如：面片数，边数，顶点数等。常见的简化方法包括：网格顶点删除法， 边折叠法，和网格优化法等。几何简化是一个已经研究得相当广泛和深入的课题 有些算法速度非常快，但是简化后的模型并不理想；相反有些算法的简化结果很 好，然而速度又太慢。无论何种算法，模型简化在平衡模型精确度与图形处理速 度方面，都给出了折衷的解决方案。 尽管p c 机图形显示卡的数据处理能力和网络带宽都已经取得长足的进步， 但与三维模型日益精细所带来的数据量和复杂程度的急剧增长相比，仍显得捉襟 见肘。在这样的背景下，寻找新的算法来更有效地表达三维模型，从而减少三维 几何数据的存储量 相应地降低其在网上传输的带宽要求，具有重要的意义。对于 同一个三维几何模型，如果把具有较多细节信息的模型称为高分辨率下的模型 那么它在省去部分细节信息后所得到的，就称为较低分辨率下的模型。几何模型 的多分辨率分析和存储，是从另外一个角度来改善数字几何处理性能的方法。利 用这种方法，人们可以把三维几何模型表示成分辨率从高到低的一系列近似的模 型。然后，我们就能够根据不同用户对模型的复杂程度的要求。给出相应分辨率 下的模型。显然。用于表示高分辨率模型的数据量高于低分辨率模型的数据量。 因此，不同的分辨率就意昧着模型数据量的差异。几何模型的多分辨率分析技术 能满足不同层次的模型细节需求，有效地改善了用户端的图形绘制效率。常见的 多分辨模型有离散和连续两种方式，其处理的数据类型包括了几何性质、表面性 质、和纹理等。 由于存储分辨率从高到低的一系列模型会带来庞大的存储开销，多分辨率分 析的研究还需要处理模型的存储问题。l o d ( k v e lo f i ) e t a i l ) 技术就是顺应这一情 况而发展起来的一种图形存储和绘制技术。它把描述几何模型的数据进行分裂， 得到表示模型粗糙轮廓的一组数据，以及表示模型细节信息的一系列数据，将两 类数据分别存储，就得到了具有多分辨率特征的几何模型。按照应用环境对模型 精确性的要求，l o d 先给出模型的粗糙轮廓，继而逐步通过添加细节信息来获 取所需的分辨率。l o d 技术从另一个角度，把复杂的三维模型表示成了分辨率 从高到低的一系列模型，而且有效她解决了存储方面的问题。l o d 是实现多分 辨率模型的重要工具，它将复杂对象预先表示为分辨率由低到高的一系列模型。 有了l o d ，就可以应用各种显示策略来满足不同场合渐进传输的需求。当从远 程访问几何模型时，最初到达的少量信息给出了一个粗糙的模型，后续到达的信 基于细分策略的三维模型多分辨率分析第1 章绪论 息会不断地细化该模型并逼近原始模型。按照这种思想，假如传输的比特流在任 意地方被截断，根据先前到达信息所构造的模型仍然能保持原来模型的几何特 征。这种性质特别适用于低比特率和不稳定的信道传输( 如无线网络等) 。 1 1 2 几何对象的渐进传输 近年来，因特网的发展速度和规模远远超出人们的预期，互联网已经深入到 人们日常工作、生活的方方面面，通过网络远程获取和访问大规模的数据已经习 以为常。此外，随着网络图形学的发展。越来越多地需要通过网络，特别是国际 互联网，来存取异地的三维几何数据这使得本来已经十分有限的网络带宽变得 更加紧张。要解决这些由于三维几何数据规模和复杂度的急剧增长所带来的问 题，仅仅依靠提高三维图形引擎的处理速度和能力，以及增加网络带宽等硬件方 面的措施是还远远不够。尽管通讯技术的发展使网络带宽有了较大的提高。但海 量的模型数据全分辨率的下载，对于任何带宽的网络来说，还是难以承受的因 此，提出新的占用空间小、绘制速度快，适合于计算机网络传输的三维几何数据 表示方法是模型传输研究的焦点。 除了多分辨率分析等基于模型存储的解决方案外，另外一种用于三维图形传 输和显示的辅助技术就是几何对象的渐进传输其基本思想是通过一定的传输策 略，先传送粗糙的模型到客户端显示，再不断补充细节信息来完善客户端的模型， 最终完成模型整体的传输何绘制渐进传输减小了传输的总数据量和客户端等待 的时间，提高了显示效果的真实性在传输的开始，客户端就可以看到模型的 基本形状，绘制过程和传输过程的同步进行，使客户端的显示效果逐步精细，最 终得到完整的三维几何模型渐进传输。能够部分地缓解低带宽与大数据集实时 传输之间的矛盾，所以设计三维嘲格模型的渐进传输算法，就成了充分利用有限 网络带宽和减少等特时间的迫切需要 1 1 3 移动图形表示技术 p d a 、移动电话类手持式设备的迅猛发展，使嵌入式操作系统成为当前r r 产业的焦点之一。越来越多的生产长家倾向于发展新一代的移动电话和掌上电脑 的一体化产品( s m a r tp h o n e ) ，随之而来的一系列移动计算方面的问题，逐渐引 起了众多科研学者的注意，而移动终端上的三维图形计算便是其中一个具有挑战 性的课题。 从市场上手持式设备的发展趋势来看，已经具备了支持三维图形绘制的硬件 条件。这是由于，现在出现了不少每秒钟能执行上百次指令的嵌入式微处理器， 而其所消耗的功率却并不甚高，出乎人们的意料，当前功耗鲺医不再是主要的障 碍了。尽管手持式电子产品拥有足够的能力，可以满足三维图形处理的要求，但 设计人员仍需要花费一些精力来处理其他问题，诸如存储器不足，以及c p u 运 算速度有限等问题。存储容量的不足是增加三维图形支持的主要问题，它决定了 用户能在手持式产品中存储的三维图形的规模，这时就需要在图形数据量和图形 精度方面进行折衷。 基于细分镱略的三维模型多分辨率分析第1 章绪论 将三维图形可视化从桌面p c 移植到资源受限的移动终端设备的研究仍处于 起步阶段。如何结合三维图形显示技术和无线网络，实现三维几何模型的下载与 显示，将是一个值得研究的课题。这方面的技术突破，能为移动终端上的三维地 理信息系统、三维动画、和三维游戏等应用带来全新的解决方案。 图l - 2 手持式设备上的三维模型 众所周知，现今许多三维图形的应用都是构筑于特定操作平台的图形处理库 的基础之上。在图形图像领域里，p c 平台的三维图形的a p i ( a p p l i c a t i o np r o g r a m i m e r f a c e ) 为数众多。这几年，有3 种常用的a f i 格式逐渐确立了它们在图形领 域的地位，它们是：微软公司推出的d i r e c t 3 d ；s i l i c o ng r a p h i c s ( s g i ) 公司开 发的o p e n g l ；a u t o d e s k 公司的h e i d i 。 对比起p c 上成熟的三维图形接口，在手持式产品的操作平台上支持三维图 形的软件工具包还是寥寥可数。其中原因是，许多处理器都针对便携式电脑及移 动电话作了相应改动，这些改动带来的缺陷包括缺少浮点运算、除法运算、方根 运算以及三角函数运算，它们都制约了手持式设备像桌面型电脑处理器那样适用 于三维应用。另外，三维图形绘制所需的一些高级效果，如转换、照明和剪辑等， 要求高度精确的浮点运算，而大部分嵌入式平台的图形处理能力仍未达到该水 平。虽然如此，移动领域的科研组织还是在三维图形显示方面取得了激动人心的 进展。d i g i t a ls a n d b o x 公司为p a t m o s 移植了m i n i g l 图形库，令部分的o p e n g l 图形函数在p a l l n 平台上得到了支持，开发者可以使用有限的o p e n g l 函数开发 三维图形应用。英特尔公司为了克服x s c a l e 处理器( 处理器核心来自英国的a r m 芯片设计公司) 及其他芯片的一些缺陷，设计了g p p ( 图形性能基元) 三维图形工 具包，该工具包能用于开发手持式设备上的3 d 游戏引擎；p a r a l l e lg r a p h i c s 发布 了用于p o c k e tp c 平台的p o c k e tc o r o n a3 d 浏览器，此p o c k e tc o r t o n a 是世界上 首款可以在无线设备上浏览v r m l 屏幕的3 d 浏览器不过目前，从软件角度 设计有效的算法，在内存和处理能力受限的手持式设备上实现实时三维图形的显 示，仍然是众多科研人员所关注的问题 基于细分簧略的三缝模型多分辨率分柝第1 章绪论 1 2 研究现状 1 2 1 三维曲面的缨分算法 相对于传统的计算机图形表示方法，细分算法是一种离散的几何模型构造方 法，它的基本思想是：对给定的离散几何数据，递归地调用细分规则，从而逐步 加密几何数据使其收敛于一个极限的几何模型。在三维曲面的表示方法中，多边 形网格是一个最常用的数学工具，将细分算法应用于多边形网格便得捌了睦面的 细分算法。对多边形网格的递归细分，将使它收敛于一个极限曲面其原理是从 粗糙的控制网格出发，通过细分策略产生新的顶点，并得到更加细化和光顺的网 格，该过程的迭代就能使网格，收敛于一个极限曲面由于曲面细分算法有良好 的数值稳定性，运算效率高和易于实现，所以它具有广泛的应用价值，众多学者 对此进行了深入的理论研究 根据不同的细分规则类型，曲面的细分算法可以分为逼近型和插值型两种 对于逼近型细分算法，控制多边形的顶点在细分过程中将被去掉，不会出现在细 化后多边形的顶点集合中逼近型细分的过稷可以形象地理解为“钠角”，朝通 过不断地磨平两格的拐角，得判更加光滑的网格来逼近最终的曲面。觅圈l - 3 逼近型的细分规则能带来较好的光顺性。但原始的控制网格和极限曲面在视觉上 有较大差异相比之下，对于插值型细分算法，粗糙多边形的顶点在细分过程中 不会被删除，会出现在细化后多边形和极限曲线的顶点集合中插值羹细分规则 保留了控制瞬隆约顶点，它使控制网格可以近似造反映出极限曲面的几何外形 然而代价是牺牲了光顾性不过。无论是逼近型的细分还燕箍值型的细分，都具 有一个共同特征就是细分过程中始终保持几何对象的拓扑结构 图1 3 细分方法比较 此外，细分算法又可以划分为静态的细分算法与动态的细分算法。一种细分 算法称作静态的，如果在每一步细分都使用相同的规则细分过程中按照某种策 略不断调整细分规则的方法称作动态的细分方法。同时，我们还会考虑细分算法 基于细分策略的三维模型多分辨率分析第l 章绪论 的一致性问题。所谓一致性，即同一个细分规则应用于整个控制网格。不一致的 细分方法会对控制网格的不同部分采取不同的细分规则。细分算法的发展历程 中，出现了许多经典的曲面细分算法，其中三角细分和四边形细分得到了众多学 者的重用。 图1 4 对b u n n y 的三角细分 三角细分方法只适用于由三角面片所构成的曲面，它的原理是对任意一个三 角面片，为每条边新增顶点( 这些新增顶点的几何信息和旧三角面片的边相关) ， 通过调整三角面片的顶点( 三个旧顶点和三个新增的边点) ，得到四个新的三角 面片以取代旧的三角面片( 即1 - 4 拆分) ，见图l - 5 。 图1 5l - 4 拆分 1 9 8 7 年，l o o p 在其硕士论文中提出了一种基于三角网格的逼近型细分算法 【2 】。l o o p 细分算法是一种己知的最简单的逼近型的三角细分算法，它是产连续 的四次三角b 样条函数的推广，能产生正切平面光滑的曲面。 另外一个经典的三角细分算法是1 ) y n , g r e g o r y 和l e v i n 在1 9 9 0 年提出的蝴 蝶细分【3 】，它是一种插值型的三角细分方法，即细分后旧网格上的顶点仍然会 出现在新网格的顶点集合中，细分过程只引入新的边点。蝴蝶细分可以达到c 1 连续，其掩模如图1 - 6 。 基于细分燕略的三维模型多分辨率分析第1 章绪论 图1 - 6 蝴蝶细分掩模 四边形细分适用于任意拓扑结构的曲面，核心思想是用四边形面片替代原始 的多边形面片。对任意一个n 边形面片，按照一定的法则( 如：加权平均) ，计 算1 1 个边点( 与边相关) 和1 个面点( 和面相关) 作为新加入的顶点，然后将各 边点连接到面点，再调整原始n 边形的顶点就能得到新的四边形面片来取代旧的 i i 边形面片。面点的引入是四边形细分区别于三角细分的明显标志。 图1 7 四边形细分原理 1 9 7 8 年，c a t m u l l 和c l a r k 首先提出了著名的c a t m u l l c l a r k 细分算法 4 】，简 称c c 细分方法。c 。c 方法是一种逼近型的四边形细分方法，一般包括三个步骤： ( 1 ) 对面片的顶点进行加权平均计算新的面点( 和面相关的顶点) 。 ( 2 ) 对于面片的某一条边，计算边的顶点与从( 1 ) 中所得的相邻面点的加权平 均，得到新的边点( 和边相关的顶点) 。 ( 3 ) 对于原来的顶点，使用其相邻顶点和面点的加权平均进行调整。 上述三步所得顶点( 顶点，边点，面点) 替代原来网格的项点便得到一个细 基于细分策略的三维模型多分辨率分析第1 章绪论 化的网格。重复该细分过程可最终得到一个极限曲面。 1 2 2 曲面多分辨率分析 图1 - 8c - c 细分掩模 随着科学技术的进步，用于描述几何模型的数据越来越精细和庞大，一些复 杂的模型动辄就产生数以百万计的面片。在网络传输的环境下，如果用户要等模 型所有的精细数据到达后才进行绘制。势必造成时间上的极大浪费。高分辨率的 模型并不总是必需的，丰富的冗余细节需要一个折衷的方案。一种解决方法是使 用几何压缩减少模型数据量，如k h o d a k o v s k y 等人描述的通用三角网格压缩算法 f 5 1 。另一方面，在很多情况下，高分辨率的模型并不总是必要的，需要在模型 的准确度和处理时间之间进行折衷，通过牺牲部分模型的真实性，来获取系统交 互的实时性。多分辨率模型对大型数据集来说是必要的，基于多分辨率模型的渐 进编码可有效地解决这类型大数据集的传输与存储问题。 多分辨率模型是指几何实体的多个层次细节网格的表示形式，相当于该实体 多个不同分辨率模型的集合。多分辨率模型又可分为离散多分辨率模型和连续多 分辨率模型。对复杂网格的简化，得到不同细节层次的多个网格模型，称为离散 多分辨率模型；而连续多分辨率模型则是一种紧凑的模型表示方法，可生成任意 多个不同分辨率的模型。前者由于分辨率的不连续，在切换不同分辨率模型的时 候会造成视觉上的不连贯。后者虽然能彻底解决视觉上不连续的问题，但模型表 示的复杂性却又影响了绘制的速度。在网络传输的场合，视觉上的连续性与交互 实时性相比，将显得相对不重要。所以离散多分辨率模型更加适用于远程几何对 象的访问。 图1 = 9 分辨率逐渐升高的h o r s e 模型 基于细分簟略的三箍模型多分辨率分折第1 章绪论 所谓三维曲面的多分辨率模型是一种曲面表示方法，该方法支持曲面从粗糙 到精细的各分辨率层次下的重新构造【6 】。多分辨率分析可理解为获取和应用曲 面多分辨率模型的过程。比较经典的曲面多分辨率模型有l o d 和渐进网格 【5 ，7 8 】。其本质是对几何模型数据的分析和化篱。模型化简是指在保持原来模型 集会形状不变的前提下，采用适当的算法来减少模型描述信息的数据纛。著名的 模型化简算法有s c h r o e d e r 的顶点删除法，h o p p e 的边折叠法和p r o g r e s s i v em e s h 法等。模型化简技术是一种由复杂高分辨率模型生成较低分辨率模型的关键技 术。由于基于顶点、边和面的几何简化的表示方法，未能很好她支持数值控制和 复杂的多分辨率编辑【9 】，所以人们逐渐转向基于小波和细分曲面的多分辨率分 析研究。 将小波和细分曲面结合用于多分辨率分析的研究方式，有着坚实的理论依 据。在众多的曲面网格表示方法中，一种特殊的网格是那些具有细分连通性的网 格，又简称为细分网格，它们隐含了层次型的结构【1 0 】，因此与多分辨率分析有 着紧密的联系，成为了多分辨率分析的常用工具将细分算法逆转。从网格中提 取细节信息作为小波系数，同时得到一系列的粗糙网格，该过程称为曲面的小波 分析【1 1 】。曲面的小波分析中，小波系数是细节的量度基于细分小波压缩的基 本思路是利用人眼视觉冗余，舍弃部分小的系数，在保证一定图形质蠡的同时， 减少图形的顶点和三角形面数，从而达烈数据压缩的目的 ( a ) 3 3 5 9 1 个顶点4 1 9 8 个顶点( c ) 1 0 4 9 个顶点 图1 1 0v e n u s 的细节舍弃 第一个细分曲面的小波构造方法由l o u n s b 日y 等人提出【1 2 】，他们建立了定 义在任意拓 类型曲面上的小波分析框架，成功邋为分段线性细分和蝴蝶细分丰奄 造了满足正交性质的小波【1 3 】。对于类似l o o p 的逼近型细分曲面，他们结合全 局的线性方程组求解和最j 、- - 乘拟合，给出了准正交小波的构造这种方法虽然 满足了小波和尺度函数的正交性但不一定能得到线性的运算时间。为了满足运 基于细分镱略的三维模型多分辨率分析第l 章绪论 算时间的要求，s a m a v a t i 等人建议在局部的最小二乘拟合中使用离散范式【1 4 】， 他们还给出了6 度顶点网格下的局部l o o p 细分掩模的逆运算。与l o u s b e r y 的细 分曲面多分辨率分析相对，k o b b e l t 和s c h r o d e r 构造了另外一种多分辨率分析框 架用于变分细分【1 5 】。l o u n s b e r y 等人的研究为任意拓扑网格的多分辨率分析奠 定了理论基础。 为了构造双正交小波用于细分曲面的分析，s w e l d e n s 提出了使用提升算法来 构造小波的新颖思路 1 6 】。提升算法是一种局部运算，只需要局部的逆操作，它 是一种高效的小波构造方式，也是小波分析和合成的重要工具。另外，s c h r o d e r 和s w e l d e n s 还描述了球形曲面拓扑下的双正交小波【1 7 】。 上述研究方法的前提是，用于多分辨率分析的曲面满足细分曲面的性质。这 类型的曲面简称为细分曲面，细分曲面可以理解为对一般曲面应用细分算法所产 生的曲面，它常用于表示任意拓扑结构的三维曲面。当然，一般情况下的曲面网 格数据不具有细分曲面的细分连通性，需要先对网格进行再网格化( r e m e s h ) ，如 m a p s 1 s 等方法，得到带细分连通性的曲面。重新网格化是使任意拓扑的网格 适用于多分辨率分析的重要环节。为了得到曲面的细分连通性，e c k 等人基于多 分辨率分析理论对多边形网格作重新采样【9 】，通过v o m n o i 分片与调和映射，先 求出原网格的最粗近似基网格，在此基础上加密采样来获取精细的网格。同样， 为了构造基网格，我们还可以使用h o p p e 渐进网格【7 】中的边折叠算法w o o d 等 人提出了一种从体数据提取准正规网格的方法0 9 ，由于提取的网格具有细分连 通性，所以无需网格的后置处理。 如果睦面具有某种细分连通的性质，我们就能很方便地应用以上方法进行分 析。对给定的曲面，判断其是否具有细分连通性有着广泛的实用意义，t a u b i n 研究了一种基于代数拓扑的检测细分连通性的算法【2 0 】。它首先构造三角网格的 覆盖网格然后判断覆盖网格是否等同于更低分辨的三角网格，以此判断原来三 角网格是否具有细分连通性。至于不具备细分连通性的曲面分析。g u s k o v 等人 也给出了非规则网格在不同分辨率下的信号处理算法 2 1 1 1 , 3 论文概要 1 3 。1 研究意义 三维几何模型多分辨率分析的研究仍处于起步阶段，虽然在模型简化、渐进 传输、模型重构方面已经出现了不少经典的理论和工具，但是其实用性还有待更 深入的考究。本课题的研究基础是国内外近十年所建立起来的多分辨率分析理论 和细分算法理论，这些理论的综合运用尚未达到相当成熟的程度，因此，从方法 和实现工具方面都可能存在不稳定因索。而且，该研究领域的工作在国内还相对 空白。所以，本次课题研究是一次大胆的尝试，旨在充分理解细分曲面多分辨率 分析的原理，应用小波分解等工具，在实践中构造出切实可行的多分辨率分析策 略。 从实际应用层面的角度分析，对无线场合的三维几何模型传输与显示，不可 基于细分策略的三维模型多分捞事分折 第】章绪论 避免地要讨论到手持式设备的性能。通常，嵌入式操作系统的浮点数运算能力都 较差，然而浮点运算往往是几何模型绘制时的必要工具如果降低三维模型显示 的运算规模。则系统的实时性将会大大提高。使用小波分解构造的多分辨率模型 可以实现定制盼显示策略，自适应地省略部分细节，满足特定的网络传输和模型 绘制的需求。按照这些策略。模型的部分细节和属性信怠会被牺牲由予手持式 设备在几何模型的细节方面并没有太高的鬻求，相比而吉，它更强调系统交互的 实时性。因此，曼维几何模型的精度要求可以相对放宽本文的细分小波算法可 以简易地移植到移动计算平台，用作产生多分辨事模型的工具 本课题的研究实用性较强，其中的突破有助于推动复杂三维几何模型的应 用。由于方法使用的研究工具( 小波，细分算法) 具有通用性，因此可以很容易 地推广到其他细分连通性曲面的多分辨事分析中 1 3 2 课题重点 本研究课题围绕曲面的多分辨率分析，对带l o o p 细分连通性的几何模型。 构造l o o p 细分小波，进行分