（计算机软件与理论专业论文）三维网格细分与对等网络渐进传输.pdf

三维网格细分与对等网络渐进传输 摘要 论文题目：三维网彰知缝对等网络渐进传输 专业；计算机软件与理论 博士生：史卓 指导教师：罗笑南教授 摘要 三维几何数据已成为继声音、图像和视频之后的第四种多媒体数据类型，近 二十年来，随着三维数据采样设备的长足进步与复杂拓扑结构的曲面造型日益普 及，细分方法已成为近年来图形学领域较活跃的研究热点之一。对三维网格进行 细分之后，可以使用渐进传输中的逆细分方法对复杂的三角网格数据进行分级、 简化，应用于渐进传输中。 对等网络( p 2 p ) 技术在网络性能以及系统扩展性的优势适合媒体数据传输。 由于各类网络终端在c p u 处理能力、存储能力、可接入带宽等方面存在很大的 差异，用户要求实时性较强，等待完整的图形数据传输后再显示已经不能满足需 求，因此媒体质量分级要求逐渐被用户提出，可分级编码( s v c ) 技术和渐进网 格( p m ) 提供这种可分级媒体服务的可能性。 针对网络性能的差异性和媒体质量分级的需求，本文对适用于分级媒体的三 维网格细分方法和p 2 p 渐进传输两方面进行了研究，主要研究内容和贡献体现在 以下几方面- 首先，给出插值l o o p 细分曲线和混合l o o p 细分曲线，并证明曲线均是处 处c 1 连续。混合l o o p 细分方法通过添加插值逼近融合参数，可以在同一张曲面 上实现l o o p 细分与新的插值细分模式共存，不需要反求控制顶点或者解方程就 直接得到局部插值细分网格。解决三角形细分网格在多分辨率显示存在的“扩张 或者“收缩 的跳跃问题。此外提出在网壳结构建筑设计的细分造型设计方法， 可以简单明确的给出曲面造型公式，对比需要反复推算、实验的复杂经验曲线的 传统方法，本方法简单实用，对指导网壳建筑结构设计具有定的意义。 第二，针对渐进网格、可分级视频的分层特性，提出三种基于可分级媒体的 三维网格细分与对等网络渐进传输摘要 覆盖网络评估策略，以此做为各种分级媒体传输算法的对比评价标准。分别提出 基于覆盖树和基于i p 多播的p 2 p 渐进传输策略，前者利用多重隐含覆盖树策略 来构建流媒体传输覆盖树，以此保证可分级编码视频各子码流的同步性和切换低 延时性，后者可以有效的降低系统链路负载。 第三，提出基于媒体层次分类的多重覆盖树算法和分层多播岛建立和维护算 法，以及节点选择连续性优先策略。结合上述算法，提出一种适用于分级媒体服 务的p 2 p 渐进传输算法s p m ，通过网络模拟的实验结果可以看出，该算法能够 在保证低延时、低网络负载的s i m 算法优势下，实现可分级媒体服务。相比s i m 的最大优势在于服务质量类别低的主机比例越大，则整个网络的链路负载越低。 此外，本论文还探讨s p m i p t v 系统设计，以及该系统与机顶盒设备的结合方式。 ，综上所述，为适应网络上分级媒体服务的需求，本文对三维网格曲面的细分 方法，分级媒体数据的渐进传输等关键问题提出了一些新方法，大量实验证明这 些方法具有较好的实验结果和应用前景。 关键词：网格编辑、细分模式、细分融合、对等网络、渐进传输、可分级视频编 码、岛式多播 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： r e s e a r c ho n3 dm e s hs u b d i v i s 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 nb a s e d o np e e r - t o p e e rn e t w o r k c o m p u t e rs o f t w a r ea n dt h e o r y z h u o s h i p r o f x i a o n a nl u 0 a b s t r a c t 3 - d i m e n s i o n a lm e s hh a sb e i ：o m et h ef o u r t ht y p eo fm u l t i m e d i ad a t aa f t e rt h e a u d i o ，i m a g ea n dv i d e o r e c e n t l y , w i t ht h ei m p r o v e m e n to f3 dm e s hg a t h e r i n g f a c i l i t ya n dt h ep o p u l a r i t yo fc o m p l i c a t e dt o p o l o g ys u r f a c em o d e l i n g ，s u b d i v i s i o n m e t h o db e c o m e so n eo ft h eh o t t e s tr e s e a r c h e di s s u e s t h e r ei sc o n s i d e r a b l ei n t e r e s ti n t h eu n i f i c a t i o no fs u b d i v i s i o ns c h e m e s c o m p l e x3 dm e s hd a t ai ss i m p l i f i c a t e da n d s t r a t i f i e d b yr e v e r s es u b d i v i s i o nt op r o g r e s s i v et r a n s m i t b yp 2 pn e t w o r k , a f t e r s u b d i v i s i o ns t e p so f3 dm e s h p e e r - t o - p e e rn e t w o r k sa r ew i d e l yu s e di nm e d i at r a n s m i s s i o nb e c a u s eo fi t s e x c e l l e n tn e t w o r ks c a l a b i l i t y b u tt h e r ea r ed i v e r s i t yo ft e r m i n a l sw h i c hh a v ev e r y d i f f e r e n tc p u p r o c e s s i n ga b i l i t i e s ，m e m o r i e sa n dn e t w o r kb a n d w i d t h si nn e t w o r k t o d a y b e s i d e su s e r sc a n n o tw a i tu n t i lt h ew h o l ed a t aa r ed o w n l o a d e da n dr e q u i r ei e a l t i m ea p p l i c a t i o n s os c a l a b l em e d i as e r v i c ei s p r o p o s e dr e c e n t l y s c a l a b l ev i d e o c o d i n g ( s v c ) t e c h n o l o g ya n dp r o g r e s s i v em e s h e s ( p m ) a r ep r o p o s e dt om e e tt h i s n e e d f o rt h en e e do fd i f f e r e n tn e t w o r ka b i l i t i e sa n ds c a l a b l em e d i as e r v i c e ，t h i st h e s i s d i s c u s s e st h e3 dm e s hs u b d i v i s i o nm e t h o da n dp r o g r e s s i v et r a n s m i s s i o nt ob es a m e w i t hs c a l a b l em e d i a t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa l e p r e s e n t e da sf o l l o w s ： f i r s to fa l l ，w ed e s c r i b et h e i n t r i n s i c r e l a t i o n s h i p o f i n t e r p o l a t i o n a n d a p p r o x i m a t i o ns u b d i v i s i o n s ；p r o p o s et h ei n t e r p o l a t o r yl o o ps c h e m ea n dt h em i x e d l o o ps c h e m e t h e s el i m i ts u r f a c e sa r ep r o v e dt ob ec 1c o n t i n u o u se v e r y w h e r e t h e i i i 三维网格细分与对等网络渐进传输 a b s t r a c t p a r a m e t e rs u b d i v i s i o ns c h e m e c a nr e a l i z et h ep o s s i b i l i t yt o l o c a l l yc h o o s e a n i n t e r p o l a t i n gv a r i a n to ft h ec o n v e n t i o n a l l ya p p r o x i m a t i n gs u b d i v i s i o ns c h e m e u n l i k e t h ee x i s t i n gm e t h o d s ，i tn e e d sn o tc o n s t r u c ta n ds o l v ee q u a t i o n s t h es c h e m ea l s oc a n b eu s e dt os o l v et h e “p o p p i n ge f f e c t ”p r o b l e mw h e ns w i t c h i n gb e t w e e nm e s h e sa t d i f f e r e n tl e v e l so fr e s o l u t i o n s b e s i d e s ，w eg i v et h es u b d i v i s i o nd e s i g nm e t h o do ft h e s h e l la r c h i t e c t u r a ld e s i g n c o m p a r e dw i t ht h ec o m p l e x e x p e r i e n c ec u r v eo ft r a d i t i o n a l m e t h o d s ，t h i sm e t h o di ss i m p l ea n dp r a c t i c a l s e c o n d l y , f o rs t r a t i f i e dc h a r a c t e r i s t i c so fp r o g r e s s i v em e s h e s ，s c a l a b l ev i d e o ，a n d t h i st h e s i sp r o p o s et h r e ec o v e rn e t w o r k sa s s e s s m e n ts t r a t e g i e sa sac l a s s i f i c a t i o nt o v a r i e t yv a r i o u sp r o g r e s s i v et r a n s m i s s i o nm e t h o d s t w ok i n d so fp 2 pp r o g r e s s i v e t r a n s m i s s i o nb a s e do nt r e ec o v e ra n di pm u l t i c a s ta r ep r o p o s e d t h ef o r m e rm a k e su s e o fs e v e r a li m p l i e dt r e ec o v e rs c h e m ea n de n s u r et h es y n c h r o n i z a t i o na n d l o w - l a t e n c y s w i t c ho ft h es u b - v i d e os t r e a mo ft h es c a l a b l ev i d e o c o d i n g t h el a t t e rc a ne f f e c t i v e l y r e d u c es y s t e ml o a dl i n k 。 t h i r d l y , b ya n a l y z i n gt h ea d v a n t a g eo fp 2 po v e r l a yt r e em o d e li nr e a l t i m e s t r e a m i n g ，t h i st h e s i sp r o p o s e sam u l t i p l ec o n n o t a t i v eo v e r l a yt r e es c h e m et ob u i l du p ad e l i v e r yo v e r l a yt r e et om a k es u r et h es y n c h r o n i z a t i o no fe a c hs u bs t r e a mi nt h e v i d e oa n dt h el o wl a t e n c yf o rs w i t c h i n g t h i st h e s i sp r o p o s e sad e l a m i n a t e dm u l t i c a s t i s l a n ds c h e m eu s i n gi pm u l t i c a s tt e c h n o l o g y t h ei n t e g r a t i o no ft h et w os c h e m e sc a l l a c h i e v eb o t ht h e i ra d v a n t a g e s w ec a l lt h i ss v cv i d e op 2 p d e l i v e r ya l g o r i t h m 硒t h e s p ma l g o r i t h m b e s i d e si n i t i a lb u i l d i n gu pa n dt r a n s m i t t i n gp r o c e s s ，s p ma l g o r i t h m a l s oi n c l u d e sas e r i e so fs t r a t e g i e st og u a r a n t e et h ec o n t i n u i t yo fu s e re x p e r i e n c e i ns u m m a r y , f o rt h en e e do fs c a l a b l em e d i as e r v i c eo fn e t w o r k ，t h i st h e s i s d e s c r i b e st h ek e yi s s u e so ft h es u b d i v i s i o ns c h e m e ，p r o g r e s s i v et r a n s m i s s i o no f s c a l a b l em u l t i m e d i ad a t ab a s eo np e e r - t o - p e e rn e t w o r k s ，a n dp u tf o r w a r ds o m en e w m e t h o d s al a r g en u m b e ro fe x a m p l e sp r o v et h a tt h em e t h o dh a sg o o de x p e r i m e n t a l r e s u l t sa n da p p l y i n gp r o s p e c t s i v 三维网格细分与对等网络渐进传输 a b s t r a c t k e yw o r d s ：m e s he d i t i n g , s u b d i v i s i o ns c h e m e ，m i x e ds c h e m e ，p e e rt op e e r , p r o g r e s s i v et r a n s m i s s i o n ，s c a l a b l ev i d e oc o d i n g ，i s l a n dm u l t i c a s t v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： e t 翌：皇哗卫一 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行杠：索，可以采用复印、缩印或其他方法保存学位论文。 学譬：学年新龇 吼1 年6 月r r 日 。纺彰 l 日期渤户阳r f 日 三维网格细分与对等网络渐进传输第1 章综述 第1 章综述 本章首先针对三维几何数据处理、对等网络传输的研究历史背景、研究内容 ，t， 和特点进行系统的回顾，针对网络性能差异和媒体质量分级的需求，对各种三维 网格处理技术，尤其针对离散几何造型技术中的细分方法，对等网络技术以及可 分级渐进传输等研究进行详细的阐述。最后扼要地介绍本文的研究内容和主要研 究成果。 1 1 研究背景 随着3 d 扫描技术的发展，三维几何数据正逐渐成为继声音、图像和视频之 后的第四种多媒体数据类型。这种媒体在互联网、娱乐和制造等其它工业的日益 广泛应用对三维网格处理算法提出了很高的要求。这一趋势推动了学术界对数字 几何处理( d g p ：d i g i t a lg e o m e t r yp r o c e s s i n g ) 的研究。顾名思义，数字几何处 理即用计算机对三维几何数据进行处理，这门从9 0 年代中后期发展起来的学科 属于计算机图形学和数字信号处理的交叉学科 1 1 1 2 1 3 。 尽管近几年这一方向的研究取得了激动人心的进展，但与大家熟悉的数字图 像处理和传统曲线曲面处理等处理传统媒体的学科相比，数字几何处理还显得非 常年轻。现有的数字几何处理研究成果还无法为大多数几何处理应用提供一个统 一的、理论上完备的框架，还无法满足工业界r 益增长的需求。正如一些学者指 出的那样，数字几何处理还是计算机图形学研究领域的一个公开问题【3 】。 数字几何处理技术在计算机工业建模和计算机动画中应用广泛。现有的许多 技术己经被用于造型工作和三维人物变形，帮助人们设计更真实、更复杂的几何 体，提高设计质量，并大大减少设计的工作量。最常见的是影视行业。为了给观 众带来真实世界中无法体验的场景，大量的三维模型造型技术应用于影视制作 中。 数字几何处理技术中，网格的细分与简化【5 】是一个研究的重点。目前几何模 型变得越来越细节化，不利于存储、传输和绘制。为了解决这个矛盾，人们直接 1 三维网格细分与对等网络渐进传输第1 章综述 利用简化后的近似网格代替原始网格进行操作；粗略地讲，细分相当于简化的逆 过程，其基本思想就是对初始的分段线性表面进行不断精化以产生一个光滑的极 限表面。因此网格的细分和简化可以作为三维几何数据传输的前期数据处理步 骤。 像三维导航、产品展示、手语三维显示、虚拟城市、大型三维网络游戏等这 些应用往往需要通过从服务器下载的方式把三维模型或三维场景从服务器端传 输到各种客户端上进行显示，但现实网络环境具有带宽、终端处理能力差别大、 可靠性相对较差的特点，因此针对三维几何数据传输与显示方式的研究也是十分 有必要的。 目前对等网络技术( p e e rt op e e r ，简称p 2 p ) 主要用于数据下载、视频传输， 提供实时直播业务。p 2 p 的模式大大减轻了网站服务器这一“瓶颈 的吞吐量， 但却导致互联网上流量的激增。p 2 p 系统往往对所有用户都提供相同质量的媒体 服务，但是网络带宽的不确定性和终端设备性能指标的差异性都要求系统能提供 与用户实际需求相匹配的视频质量服务。三维网格模型的简化、逆向细分技术以 及可分级视频恰好可以提供这种可分级的质量传输可能性。在对等传输网中对三 维网格模型、可分级视频进行传输，不但能根据网络带宽和设备性能进行合理传 输，也能支持按网格模型质量收费模式的实现，因此具有广泛的应用前景。 可分级视频编码技术( s c a l a b l ev i d e oc o d i n g ，简称s v c ) ，可以将视频编码 成多个层次的数据流，包括一个基础层数据流和一个或者多个增强层的数据流。 而通过基础层和不同数目增强层的融合，可以产生不同分辨率，不同质量的视频 图象。对s v c 视频流的研究逐渐成为热点，特别是在s v c 成为h 2 6 4 a v c 视频 编码标准的一个扩展之后，这方面的研究工作得到更多研究人员的关注。 由此可见，研究适用于分级媒体传输需求的三维网格细分技术，以及对等网 络的渐进传输方法对于提高网络传输效率来说有着十分重要的意义。 1 2 三维网格细分方法 相对于传统的计算机图形造型方法而言，细分方法是一种新的几何型体表示 2 三维网格细分与对等网络渐进传输第1 章综述 思路。传统图形是以参数形式和隐函数形式表示型体的计算机处理方法，总要将 用户给定的离散控制顶点和其他信息输入计算机，通过插值、逼近或者拟合的方 法转化为连续表示，在显示和处理环节中再次转化为离散形式，它是一个离散到 连续，再到离散的过程；而细分方法是一个直接的过程，直接由离散到离散的过 程。 传统曲面造型方法遇到复杂物体造型时往往面临很大的困难，因为其控制顶 点往往具有复杂的网格拓扑，这对于利用张量积方法构造的参数曲面而言，拼接 和剪裁都较难实现。而细分方法具备了可以处理任意复杂网格拓扑的能力，这是 细分方法较之传统曲面造型方法的一个重大突破。同时细分方法将参数曲面片和 多面体表示统了起来【6 】。 细分作为种有效的曲线、曲面造型方法出现至今已有数十年。但在之前较 长的一段时间里，细分方法的发展十分缓慢。只有在最近十年，细分理论才真正 进入高速发展阶段。细分模式的构造、细分曲面性质分析及其在多分辨率表示中 的应用等研究都取得了很多成果，细分方法已经成为计算机图形学的一个标准造 型技术，并被工业界广泛接受，例如，国际上众多3 d 造型系统都加入了细分造 型的功能。本节将简要介绍细分模式构造、连续性分析、细分融合的概念和相关 工作。 1 2 1 研究背景及对象 细分方法起源于对多边形割角( c o r n e rc u t t i n g ) 来生成离散形式曲线的方法， 可以追溯至t j s o 年代g d er h a m 的通过对折线角点进行切割来生成光滑曲线，1 9 7 4 年c h a i k i n 生成曲线的细分方法1 7 t 是这种角切割思想的具体实现。曲面细分模 式发展的发展可以分为以下三阶段： 7 0 年代后期，c a t m u l l 和c l a r k 提出了著名i 拘c a t m u l l c l a r k 细分模式【8 】，分析 了3 次均匀b 样条曲面的离散方法，标志着细分方法正式成为曲面建模手段。很 快，d o o 和s a b i n 采用离散傅立叶变换的方法【9 】，对c a t m u l l c l a r k 细分等收敛性进 行了分析，开创了细分算法收敛性矩阵特征分析的先河。 8 0 年代末到9 0 年代初，产生了一些著名的细分方法，如四点插值细分曲线 【l o l ，b u t t e r f l y 细分【1 1 1 ，l o o p 细分【1 2 】等。规则情形的细分曲线曲面的收敛性和 二l 三维网格细分与对等网络渐进传输第1 章综述 连续性分析理论也逐渐完善，但是各种模式之间仍然缺乏联系，一般情况的收敛 性分析方法也是“度身定做 ，缺乏普遍性的理论指导。 9 0 年代中期至今是细分理论的高速发展期，这得益于u r e i f 在c o m p u t e r a i d e dg e o m e t r yd e s i g n 上发表的一篇论文 1 3 1 ，系统地阐述了细分曲面的连续性 问题，从而为细分理论的快速发展打下坚实的基础，这些理论反过来指导细分算 法的构造。随后z o r i n 在1 9 9 6 年提出b u t t e r f l y 细分曲面的改进方法【1 4 】，把经典的 b u t t e r f l y 曲面 1 1 1 推广到任意拓扑网格上。在这段时期还涌现了大量的细分模式 以适应不同的应用需求：西细分 1 5 1 、插值、亏细分 1 6 1 、收细分 1 7 1 、插值1 j 细 分 1 8 1 、k o b b e l t 细5 - 1 9 、四边形网格三段细分【2 0 】等等。更为重要的是，在这 一时期，细分方法得到了广泛应用，尤其是复杂网格曲面的多分辨率分析取得了 大量研究成果。 细分曲面一般可以分为逼近曲面和插值曲面两种。对于逼近模式，其生成的 曲面不经过初始控制网格。对于插值模式则不同，初始网格的每一个控制顶点都 存在于生成曲面当中。因此曲面造型应用中，插值曲面具有容易控制生成曲面外 形的特点。插值细分曲面应用最广的算法包括：运用于三角形网格上的b u t t e r f l y 细分 1 1 2 1 1 和运用于四边形网格上的k o b b e l t 细分 1 9 2 2 1 。 一般来说，逼近细分曲面可以看成是b o x 样条的推广，对于正则区域的网格， 逼近曲面都能达到和b o x 样条同样的连续阶，因而逼近细分容易得到高阶连续的 曲面。但是对于插值细分，就目前已经应用到实际c a d 应用中的方法而言，只能 达n c l 连续。其中的困难部分来自于构造和分析插值细分曲面上的理论仍未完 善。因为插值细分曲面往往不能归结到已知的参数曲面上，所以给进一步研究带 来了很大的理论障碍。最近h a s s a n 于2 0 0 2 年提出了曲线的三段插值细分方法【2 3 】， 第一次生成了具有c 2 连续的细分曲线。受到该细分模式的启发，李桂清提出了四 边形网格三段插值细分 2 0 1 。其方法突破点在于在正则区域上它能够达到c 2 连 续，这是插值细分曲面的第一次能够生成高于c 1 连续的曲面。但是目前对于高阶 连续的插值曲面，无论是构造还是连续性分析理论还有待完善，因而成熟的高阶 连续的插值细分曲面仍非常少见。 尽管细分还存在着许多未解决的问题，但是就实际应用来说，细分经过几十 4 三维网格细分与对等网络渐进传输 第1 章综述 年的发展，细分方法已经成为图形学的一个标准造型技术。不但被学术界所理解 同时也被工业界所接受。例如像3 d sm a x 、w a v e f r o n t 、m a y a 、s o f l i m a g e 等一些 著名的3 d 造型系统都加入了支持细分造型的功能。因而对于细分的研究的不仅 仅局限于理论意义上，对工业生产、计算机图形学的发展都有着非常重要的影响。 1 2 2 细分曲面的构造方法 细分曲面模式的构造主要有两个部分组成：( 1 ) 正则规则的构造，使细分模 式能够适用正则网格，对正则网格进行细化；( 2 ) 非正则规则的构造，细分模式 比传统c a d 方法的主要优势就在于对于任意拓扑网格的处理能力，因而非正则 模式的构造对于整个细分有着非常重要的意义【2 3 】。 表1 1 主要细分模式及其来源 应崩对象细分模式网格类型特性起源 b 样条曲线逼近b 样条 曲线四点法曲线插值 l a g r a n g e 插值 割角法曲线逼近b 样条 l o o p 三角形逼近b o x 样条 b u t t e r f l y 三角形插值 l a g r a n g e 插值 曲面c c四边形逼近b 样条 根号3 三角形逼近 l a g r a n g e 插值 根号2四边形逼近 l a g r a n g e 插值 对于插值细分曲面，正则规则构造的灵感通常来自于细分曲线的进步。d y n 于1 9 8 7 年提出了四点法曲线细分模式【1 0 】，受到该方法的启发，d y n 于1 9 9 0 年 又提出了b u t t e r f l y 曲面细分模式【1 1 】。当一个正则三角形网格沿着三角形任意一 条边的方向压缩为一条曲线的时候，b u t t e r f l y 方法和四点法是等价的，因而可以 把b u t t e r f l y 方法看成是四点法在三角形网格上的推广。同样来源于四点法， k o b b e l t 也提出了基于四边形网格的细分模式【1 9 】。插值锸细分细分【1 6 】、讵细分 细分【1 8 】同理也可以看成是四点法在相应类型网格的拓展。 中山大学计算机应用研究所c a g d 研究组凌若天硕士提供。 5 三维网格细分与对等网络渐进传输第1 章综述 下面以b u t t e r f l y 细分为例，介绍曲线到曲面的推广法则。 已知四点法的掩膜中四个顶点的系数分别为a o 、口l 、a 2 、a 3 ，若在曲面上的 推广四点，则b u t t e r l f y 掩膜( 图1 1 ) 中的系数应满足如下约束： 莲 ；y = 8 + 仪+ y1 0 = 2 y + p 墨p + 口+ ) ，1 1 驾2 a 。 = y ，7，7蕊，j，7。趱。- ( 1 1 ) ( a )【b ) 图1 - 1b u t t e r f l y 细分与四点法细分之间的推广关系 这样当正则网格沿着图1 - 1 ( a ) 中虚线方向压缩时，新顶点生成的位置和四 点法是一致的；当正则网格沿着图1 - 1 ( b ) 中虚线的方向压缩时，新顶点的生成 不影响曲线( 一个压缩成曲线的曲面) 原有的形状。 1 2 3 细分连续性分析理论 由于细分曲面没有解析形式，因此曲面的连续性和光滑性分析无论从理论上 还是应用角度都显得非常重要，并且相对比较困难。由于细分曲线控制多边形的 拓扑结构相对简单的多，因此单变元细分模式的收敛性和连续性分析已形成比较 完整的体系 2 5 1 1 2 6 1 。d y n 在文献【2 5 】中推导出了细分模式产连续的充分条件。 d y n 把复杂的细分曲面连续性问题归结到探讨差分细分模式( d i f f e r e n c e s u b d i v i s i o ns c h e m e ) 的收敛性上。通过研究细分模式及差分细分模式对应的 l a u r e n t 多项式，她推导出了一组十分简洁的连续性证明充分条件。由于证明步 骤的简洁，此证明方法被多次运用到不同的细分模式连续性证明上【2 3 】【2 0 】。在 d y n 的方法基础上，k o b b e l t 在文献 1 5 1 x 推导出了一个更为普遍的证明手段，使 复杂的细分模式也能通过研究差分细分模式的收敛性问题来证明原细分模式的 6 三维网格细分与对等网络渐进传输第1 章综述 连续度。同样k o b b e l t 给出的也是一个充分条件。但是他们的方法都存在着一个 非常重要的不足，就是只能证明正则网格的连续性问题，对于非正则网格的连续 性证明，则无能为力。 突破性的工作来源于r e i f 于1 9 9 5 年在c a g d 上的论文【1 3 】。这篇论文给出 了细分曲面c 1 连续的充分必要条件：当且仅当细分矩阵对应的特征映射为单射 ( i n j e c t i v i t y ) 和正则( r e g u l a r i t y ) 时，细分矩阵满足c 1 连续。同时r e i f 也指 出了一个验证细分曲面c 1 连续的简单的必要条件：若细分模式为c 1 连续，则该 细分矩阵的模最大的4 个特征值满足如下结构： 1 = 1 i 入1 1 1 1 l 入5 1 1 - 1 i 入3 1 1 1 i 入4 1 i ( 1 2 ) 在c 1 连续的基础上，若要使细分曲面拥有曲率有界的性质，那么其6 个模 最大的特征值应进一步满足如下结构，l o o p 把此结构称为b o u n d e dc u r v a t u r e s p e c t r u m 2 6 ： 1 ，入，入，入2 ， 入2入2 ( 1 3 ) 无论是r e i f 的理论还是l d o p 的进一步探讨，此套理论体系都只能数值地证 明细分曲面的连续性问题。若已知一个曲面中心是一个度数为n 的顶点，那么 r e i f 他们的理论能够验证此细分极限曲面c 1 连续性以及曲率有界问题。但无法 一般地证明所有度数的情况都能满足c 1 连续和曲率有界条件，只能分别地验证 单个度数的连续性。不过一般来说，验证度数1 0 0 以下的连续性已经能够满足工 业及计算机动画需求。 z o r i n 在1 9 9 8 年提出了能够分析任意网格的c 。连续性理论1 2 8 。z o r i n 的突 出贡献在于成功地解决了分析奇异点的高次连续性问题。z o r i n 的分析理论主要 基于细分矩阵、特征基函数( e i g e nb a s i sf u n c t i o n ) 和参数映射( p a r a m e t r i cm a p ) 。 但是该方法的推导和应用都十分复杂繁琐，鲜见于用其作为细分模式的分析手段 的文献。 1 2 4 细分方法的分类 细分可以分为插值型细分和逼近型细分。插值型细分类似与传统曲线、曲面 设计的放样方法，计算简单，预期结果直观，但是约束多，要求生成的细分网格 必须通过给定的控制网格。逼近型细分生成的细分网格位于初始控制网格的凸包 7 三维网格细分与对等网络渐进传输第1 章综述 内，便于求交等网格操作，并且其结果比插值型细分光滑度高。 实现插值细分曲面有两种方法：一种是利用已有模式通过构造适当的初始控 制网格使极限曲面满足插值条件，实质是反求控制顶点。n a s f i 的法向插值技术 【2 9 利用控制顶点的局部性，把插值条件分离，再对网格做局部修改，巧妙的解 决了顶点和法向的插值问题，但插值顶点数很多时，反求控制顶点的大型方程十 分费时。h a l s t e a d 3 0 与n a s r i 方法类似，但利用最小能量约束给出了光顺解；另 一种是构造新的模式或者修改已有模式的几何规则使极限曲面经过初始控制网 格的顶点。典型的细分插值算法包括：d y n 、i z v i n 和g r e g o r y 提出的四点、六 点插值细分曲线【1 0 】和插值三角形控制网格的细分模式一蝶形细分( b u t t e r f l y s c h e m e ) 【1 1 ，k o b b e l t 提出的插值四边形控制网格的细分模式 1 9 1 。 1 2 5 细分模式的融合 如1 2 4 节所述，细分的种类繁多，应用广泛，但是大多数细分模式都是孤 立的提出来的，虽然研究人员掌握了一些基本性质，但对彼此之间的联系却了解 不多。近年来很多文章致力于融合各种细分方法，如三角网格细分的融合 3 1 1 ， 四边形网格细分的融合【3 2 】，三角网格、四边形网格细分的融合1 3 3 1 1 3 4 1 1 3 5 ，点 分裂型细分、面分裂行细分的融合，即主对偶细分方法的融合【3 6 】【3 7 】，有任意 次数的b 样条细分的融合【3 8 】【3 9 】【4 0 】等等，然而没有一种统一形式来表示插值 型细分和逼近型细分的融合【6 】。 c o h e n 等人提出了b 样条曲线离散生成技术，方便的将任意阶b 样条曲线 的细分模式融合在一起。z o r i n 和s c h r s d e r 基于这种思想建立了主对偶 ( p r i m a l d u a l ) 四边形细分模式的统一框架【3 7 1 。s t a m 也提出了类似算法以实现 任意阶张量积b 样条曲面 3 8 1 ，并且推广到了三角形网格。上述2 种细分模式是 经典b 样条曲面的推广，而o s w a l d 和s c h r s d e r 建立了新的合成主对偶根号3 细分模式【3 6 】，对b 样条的分裂与平均方法进行了修改，提出了基元平均规则 ( e l e m e n t a r ya v e r a g i n gr u l e s ) 的概念，通过对基元规则进行组合，可以得到一系 列新算法。 m a i l l o t 和s t a m 在细分中引入了回插补偿操作【4 0 】，通过对每一次细分后的 顶点进行回插补偿来实现插值功能，在某种程度上将插值和逼近细分融合在一 起。作者的意图在于生成介于逼近与插值之间的网格，用于解决在多分辨率分解 r 三维网格细分与对等网络渐进传输第1 章综述 时，逼近网格收缩与插值网格扩张的不平滑过渡问题“p o p p i n ge f f e c t 。但作者 并未意识到插值与逼近细分之间的关系，因而采用了回插方法导致生成网格并非 、处处c 1 连续，需要采用补偿的方法实现光顺问题【6 】。张宏鑫【4 1 】改进了他们的 方法，将回插补偿操作程序化，分步骤实现，但并未解决连续性问题。闼此如何 处理“p o p p i n ge f f e c t 问题成为本论文的课题之一。 1 3 对等网络技术( p 2 p ) 对等网络技术( p e e rt op e e r ，以下简称p 2 p ) 是一种用于在不同p c 用户之 间、不经过中继设备直接交换数据或服务的技术。p 2 p 技术在加强网络上人的 交流、文件交换、分布计算等方面大有前途。而在视频数据、网格数据等的传输 方法研究中，渐进传输方法由于可分级、适应能力强的特点得到了广泛的应用。 对等网络是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资 源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由网 络提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体。 在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ，又是资源( 服务 和内容) 获取者( c l i e n t ) 。 德国互联网调研机构i p o q u e 称，p 2 p 已经彻底统治了当今的互联网，其中 5 0 9 0 的总流量都来自p 2 p 程序。简单的说，p 2 p 直接将人们联系起来，让人 们通过互联网直接交互。p 2 p 使得网络上的沟通变得容易、更直接共享和交互， 真正地消除中间商。p 2 p 就是人可以直接连接到其他用户的计算机、交换文件， 而不是像过去那样连接到服务器去浏览与下载。p 2 p 另一个重要特点是改变互联 网现在的以大网站为中心的状态、重返“非中心化”，并把权力交还给用户。 因为p 2 p 技术可以充分利用网络带宽，在大规模用户环境下可以显著提升传 ， 输速度，在多媒体视频应用领域突飞猛进。融合了多媒体内容和p 2 p 技术的 i l y l v ，由于其便捷性，用户自主性和资源的丰富性而备受用户青睐，已经逐渐 百启芝百科，鱼! ! p ；也鱼i k 曼：坠璺i 查丛：q ! 业i 曼鹭丛兰2 壁q ：b ! 班。 9 ! 堆同捂绷分与对等日终渐进传输第1 章综述 成为全球下一个极具前景、全新的宽带撮务模式。由互联网实验室。提供资料显 示( 图1 2 ) ，单纯网络电视业务预计到2 0 0 9 年全球用户将达到3 6 9 0 万。在中国， 该业务的普及范围并不广，但是也正因为如此，其潜力也是巨大的。 目前，许多i p t v 系统都开始调整原有的c l i e n t s e r v e r 模式以对等网传输 技术来解决中心服务器带来的“服务器瓶颈”、规模受限、窖错性不高等问题。 利用对等网络技术f 2 p 网络中的节点主机既扮演服务器，又扮演客户端的角色， 使对带宽、处理能力的需求分配到整个网络，从而达到更快获取服务的效果。 圈1 - 2i p t v 全球用户规模及发展趋势。 同时随着技术的发展和市场的逐步扩大，用户的多媒体服务消费观念和接入 终端的种类也在不断多变化。传统的流媒体消费大多都是通过对视频服务的点播 内容或者包月模式柬做为收费标准。因此只需要针对不同的节日指定不同的收 费标准就可以统计用户的消费情况。但是随着用广消费观念的改变，依据q o s 收费的模式已成为一种趋势。用户在享受网络视频流服务的同时，应该可以能根 据自己的消费水平选择不同q o s 质量的视频。同时，移动终端的普及，也使接 收流