（计算机软件与理论专业论文）基于点的复杂模型快速绘制.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名：整国堑!日期：塑：! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在 论文作者签名：日期： 母。s 。 山东大学硕士学位论文 基于点的复杂模型快速绘制 硕士研究生：荣国栋 指导教师：孟祥旭教授 摘要 随着计算机图形学的飞速发展，三维计算机图形已经渗透到计算机应用的方 方面面。随着三维模型逼真程度的增加，三维模型的复杂程度也迅速增加。尤其 是近几年，三维扫描技术的广泛应用更是生成了大量的顶点数目在几十万、几百 万的复杂模型。对于如此复杂的三维模型，采用传统的基于三角片的绘制方法， 现有的计算机硬件难以达到实时绘制的要求，绘制环节成了瓶颈。因此，寻找新 的三维模型的绘制方法就成了亟待解决的问题之一。近几年，一种新的绘制三维 模型的方法一“基于点的绘制”开始逐渐被人们所重视，随着对其研究的不断 发展，逐渐发展成了基于点的计算机图形学。 本文首先介绍了两种相关的绘制方法基于图像的绘制( m r ) 和体绘制 ( v o l u m er e n d e r i n g ) ，以及基于点的绘制与他们的关系。进而分析了当前基于点 的绘制的几种主流技术以及基于点的计算机图形学的其他方面的研究现状。通过 对前人技术的研究以及与计算机图形学领域相关技术的结合，本文实现了一个基 于点的绘制系统，采用“顶点”而不是三角片作为基本元素对复杂三维模型进行 快速的实时绘制。本文的主要工作包括： ( 1 ) 读入原始的三维模型数据，并将其转换成基于点表示的模型。文中针对 两类不同的原始数据来源，提出不同的算法计算每个顶点所需的参数。文中首先 对实际使用的两种原始数据格式p 【y 和n e t 的文件格式进行了详细地介绍， 然后对两种格式转换到基于点表示的模型时的参数计算加以分析，并给出了相应 的伪代码。 ( 2 ) 提出采用正方形、圆形、椭圆形等不同元素作为顶点在屏幕上的投影的 方法。文中详细分析了采用正方形、圆形、椭圆形作为顶点在屏幕上的投影的优 缺点以及具体实现时的技术细节。同时文中提出了用绘制带有预先计算好的纹理 的三角片来模拟圆和椭圆，以避免采用多边形逼近等方法所带来的时间消耗。 山东大学硕士学位论文 ( 3 ) 提出了离散的l o d 技术与基于点的绘制相结合。由原始的顶点数据构 造多个不同精度的模型表示。在实时绘制时，根据不同的需要，采用适当精度的 模型来进行绘制，而不必每次都以最精确的数据来绘制，这就在许多时候大大加 速了绘制的速度。离散的l o d 技术可以仅在绘制前进行一次判断，大大减少了 判断消耗的时间，提高绘制速度。 ( 4 ) 提出利用顶点法向量偏离程度与顶点间的距离共同作为标准来合并顶 点。法向量标准的引入能够避免合并顶点时错误的发生，同时能够更好的适应模 型的特征，在模型曲率大的地方简化较少，曲率小的地方简化较多，从而更好的 保留模型的细节。 通过对比文中的绘制方法和传统的基于三角片的绘制方法，可以看出生成的 图像质量没有明显的差别。但是在绘制速度上，基于点的绘制要明显优于基于三 角片的绘制。另外，由于离散l o d 技术的引入，在许多情况下，本文的方法在 与目前其他主流基于点的绘制技术相比时，速度也有提高。随着对基于点的绘制 的研究的不断加深，各种技术相互结合，对复杂的三维模型的实时绘制技术将越 来越完善，越来越适应各种领域的需求。 关键词：基于点的绘制、基于图像的绘制、体绘制、l o d 技术 山东大学硕士学位论文 fn 趴p 0in t b a s e dr e n d e r in go fo o m p l e xm o d e l s g r a d u a t e s t u d e n t ：r o n g ，g u o d o n g a d v i s o r ：p r o f m e n g ，x i a n g x u a b s t r a c t w j t rt h er a p i d d e v e l o p i n go fc o m p u t e rg r a p h i c s 3 dc o m p u t e ri m a g e sh a v e e n t e r e dm a n y a p p l i c a t i o n s w i t i lt h ei n c r e a s i n gf i d e l i t yo f3 d m o d e l s t h ec o m p l e x i t y o f3 dm o d e l s g r o w sf a s t d u r i n gr e c e n ty e a r s ，t h ew i d e l yu s e o f3 ds c a n n i n g t e c h n i q u e sg e n e r a t e sm o r ea n dm o r el a r g em o d e l s ，w h i c hh a v eo v e rm i l l i o n sv e r t i c e s i fu s i n gt r a d i t i o n a l t r i a n g l e b a s e dr e n d e r i n gm e t h o d ，c u r r e n th a r d w a r ec a n n o tr e a c h t h er e q u i r e m e n to fi n t i m er e n d e r i n go fs u c hc o m p l e xm o d e l s t h er e n d e r i n gs t e p b e c o m e st h eb o t t l e n e c ko f w h o l e s y s t e m s o ，f i n d i n ga n b = wt e c h n i q u eo f r e n d e r i n g3 d m o d e l sb e c o m e sa l li m p o r t a n tp r o b l e mt ob er e s o l v e d r e c e n t l y , an o v e lt e c h n i q u e p o i n t - b a s e dr e n d e r i n gb e c o m em o r ea n dm o r eh o t w i t ht h ei n c r e a s i n gr e s e a r c ho n p o i n t - b a s e dr e n d e r i n g ，an e wf i e l d ，p o i n t b a s e dc o m p u t e rg r a p h i c s ，a p p e a r s t h i sp a p e rf i r s ti n t r o d u c e st w on o n t r a d i t i o n a lr e n d i n g m a h o d s ，i m a g e b a s e d r e n d e r i n g ( i b r ) a n dv o l u m er e o d e r i n 蜀a n dp o i n t b a s e dr e n d e r i n g sr e l a t i o nw i t h t h e m t h e nw ea n a l y s i ss e v e r a lp r e v a l e n tp o i n t - b a s e dr e n d e r i n gt e c h n i q u e sa n dd i s c o v e r o t h e rr e s e a r c h e si np o i n t - b a s e dc o m p u t e rg r a p h i c s c o m b i n i n gw i t hf o r m e rw o r k sa n d t e c h n i q u e s i no t h e rf i e l d so fc o m p u t e rg r a p h i c s ，w e p r e s e n t a n di m p l e m e n ta p o i n t - b a s e dr e n d e r i n gs y s t e m t h i ss y s t e m u s e v e r t i c e s a st h er e n d e r i n gp r i m i t i v e s t or e n d e rc o m p l e xm o d e l si n - t i m e t h em a i n w o r ko f t h i sp a p e ri sa st h ef o l l o w i n g ： ( 1 ) r c a d t h e o r i g i n a l 3 dm o d e l s ，a n dc o n v e r tt h e m i n t o p o i n t - b a s e d r e p r e s e n t a t i o n b yd i f f e r e n to r i g i n a t i o n o fd a t a , t h i s p a p e rp r o m p t s d i f f e r e n t a l g o r i t h m st oc a l c u l a t et h ep a r a m e t e r so f e v e r yv c n c x f i r s t , t h et w oo r i g i n a l d a t a f o r m a t ，p l ya n dn e t , a r ed e s c r i b e d t h e nw ea n a l y s i st h ea l g o r i t h m so fc o n v e r t i n g t h ef o r m a t sa n dc a l c u l a t i n gp a r a m e t e r s ，a n dg i v et h ec o r r e s p o n d i n g c o d es e g m e n t ( 2 ) t h em e t h o d o f u s i n gd i f f e r e n te l e m e n t s ，s u c ha ss q u a r e ，c i r c l e ，e l l i p s e ，a st h e 3 山东大学硕士学位论文 p r o j e c t i o n o fv e r t i c e s i s p r e s e n t e d i nt h i sp a p e r , w ed e s c r i b et h em e r i t sa n d s h o r t c o m i n g s o fu s i n g s q u a r e ，c i r c l ea n de l l i p s e a st h e p r o j e c t i o nr e s p e c t i v e l y m e a n w h i l e ，w ed e s c r i b et h ed e t a i l so f i m p l e m e n t a t i o no fe v e r ys c h e m e w ep r e s e n ta m e t h o do f s i m u l a t i n gc i r c l ea n de l l i p s eb yu s i n gt r i a n g l ew i t ht e x t u r em a p p e d t h i s m e t h o da v o i d st h eg r e a tt i m ec o n s u m i n gw h e n u s i n gp o l y g o nt os i m u l a t ec i r c l ea n d e l l i p s e ， ( 3 ) an o v e l m e t h o d c o m b i n i n g d i s c r e t el o dt e c h n i q u ea n d p o i n t b a s e d r e n d e r i n gi sp r e s e n t e d m o d e l so fd i f f e r e n tp r e c i s i o n sa r eb u i l tf r o mo r i g i n a ld a t a d u r i n gi n t i m er e n d e r i n g ，t h em o d e lo fp r o p e rp r e c i s i o ni s s e l e c t e da c c o r d i n gt o d i f f e r e n tn e e d s s ow en e e dn o tt ou s et h ep r i c i e s td a t ae v e r yt i m e t h i st e c h n i q u e g r e a t l y a c c e l e r a t e st h e s p e e do fr e n d e r i n g d i s c r e t el o dt e c h n i q u eo n l y m a k e s j u d g m e n to n c ee v e r yf l a m e s oi tg r e a t l yd e c r e a s e st h et i m eo f j u d g i n ga n di n c r e a s e s t h er e n d e r i n g s p e e d ( 4 ) t h em e t h o do fu s i n gt h ed e v i a t i o no fn o r m a l s ，a sw e l l a st h ed i s t a n c e b e t w e e nv e r t i c e s ，a st h ec r i t e r i o no f m e r g ev e r t i c e si sp r e s e n t e d b yu s i n gt h ec r i t e r i o n o f n o r m a l ，t h em o d e l sc a nf i tt h ef e a t u r e so fo r i g i n a ld a t ab e t t e r i nt h er e g i o nw h e r e t h ec u r v a t u r ec h a n g e sg r e a t e r , t h e r ei sl e s ss i m p l i f y ；i nt h er e g i o nw h e r et h ec u r v a t u r e c h a n g e sl e s s ，t h e r ei sg r e a t e rs i m p l i f y s ot h e d e t a i l so f t h em o d e la r ew e l lr e s e r v e d b yc o m p a r i n g t h em e t h o do f t h i sp a p e ra n dt h et r i a n g l e b a s e dr e n d e r i n gm e t h o d ， w ec a l lf i n dt h a tt h e r ei sn oo b v i o u sd i f f e r e n c ei ni m a g eq u a l i t y b u tt h es p e e do f p o i n t - b a s e dr e n d e r i n gi s m u c hf a s t e rt h a nt r i a n g l e b a s e dr e n d e r i n g b e c a u s eo ft h e i n t r o d u c i n g o f d i s c r e t el o d t e c h n i q u e ，i nm a n y c a s e s ，t h es p e e do f t h em e t h o di nt h i s p a p e ri sh i g h e rt h a nt h a to f o t h e rm a i np o i n t - b a s e dr e n d e r i n gt e c h n i q u e s w i t ht h e r e s e a r c ho fp o i n t - b a s e d r e n d e r i n gg o i n gd e e p e r , a n db yc o m b i n i n g w i t ho t h e r t e c h n i q u e s ，t h ei n - t i m er e n d e r i n go fc o m p l e x3 d m o d e l st e c h n i q u ew i l lb em o r ea n d m o r e p e r f e c t i tw i l lf i tt h er e q u i r e m e n to f e v e r y f i e l do n e d a y k e y w o r d s ：p o i n t b a s e dr e n d e r i n g ，i m a g e b a s e dr e n d e r i n g ，v o l u m er e n d e r i n g ， l o d t e c h n i q u e 4 山东大学硕士学位论文 1 1 引言 第一章简介 三维计算机图形现在已经越来越普及。从高端p c 工作站到普通的家用电脑， 对高档图形硬件加速器的需求越来越高。其中最主要的一个需求来自越来越复 杂、越来越逼真的三维游戏。但是现在的交互式三维图形还远未达到能以假乱真 的程度，大多数游戏中的人物都是由为数不多的多边形构成的，尤其是在边缘处， 很容易看出人工的痕迹。 在创建三维模型的过程中，各种各样的建模技术，如隐式曲面、n u r b s 曲 面、细分曲面等的应用，使得模型中可以包含越来越复杂的形状。但是用以表示 这些复杂形状的高层次建模元素如曲面等在送往图形子系统进行绘制之前，都需 要分解为三角片。虽然使用三角片作为绘制元素看起来能满足描述能力和计算负 担之间的平衡要求，但是随着达到真实感场景绘制所需生成的物体模型复杂度的 不断提高，三角片的数量也增加很快，正如a l v yr a ys m i t h 所说：“真实就是 8 0 0 ，0 0 0 个多边形”【l 】。对大量三角片的处理造成了带宽瓶颈和过度的浮点计算 量。即使在计算机的g p u ( g r a p h i c s p r o c e s su n i t ) 高速发展的今天基于三角片的 绘制方法也已经无法适应各种应用的需求。比如，今天最新的n v i d i a 公司的 g e f o r c ef x 显卡据称每秒能产生2 0 亿个三角片，但是在运行最新的三维电脑游 戏( 如d o o m ) 仍显得力不从心。 另一方面，近年来，使用物体的采样表示方法是目前计算机图形学领域一个 重要的趋势，一个例证就是三维扫描仪被大量用于生成物体的三维采样数据。三 维扫描仪同样面临如何处理所生成的大量数据的问题。传统的处理方法是根据采 样点先生成三角片网格再进行绘制，而随着三维扫描技术的高速发展，扫描所得 到的网格点的数目达到了十亿的数量级【2 】。将如此大规模的离散点进行三角化 就是一项耗时很大的任务。另外，由于传统的三角片网格表示不仅记录了点的信 息，而且记录了点和点之间的连接关系，即边的信息，传统的技术更多的关注于 每个的边、点的放置，在每个点上耗费的工作相对过多。这就使得现有的图形工 作站无法实时绘制这种规模的网格。而且由于时间和空间的需求限制，传统的网 格简化方法和渐进显示方法对规模超过几百万的网格也已不实用。 由于三角片来自于点，最终又是以一个一个点( 像素) 的形式绘制到屏幕上 的。所以直接将点作为一种更简单、更高效的基本单元进行绘制就是一种很自然 的思路。基于点的绘制技术( p o i n t b a s e d r e n d e r i n g ，p b r ) 就抛弃了传统的三角 片表示方法，只记录点的信息，由这些点的信息直接重构出最终的图像，从而为 解决大量三维采样数据的快速绘制处理提供了一条新的途径。直接使用点作为基 本绘制单元，一方面省去了对离散点进行三角化的工作，另一方面也大大节省了 存储空间。图1 - 1 是基于三角片的绘制流程和基于点的绘制流程的比较。 圃斗团一圈 i 原始采样点l l 三角片 l 卜l 绘制单元 l 回一固 图1 - 1 两种绘制流程的比较 由于现在的三维模型越来越复杂，数据量越来越大，基于点的绘制同基于三 角片的绘制同样面临着大存储量的问题。但是由于基于点的绘制只记录顶点处的 信息。而不用记录顶点之间的关联信息，因此在存储空间的消耗上也要低于传统 绘制方法。 1 2 背景简介 对基于点的复杂模型快速绘制的研究，一个很直接的原因就是我们所从事的 考古数字博物馆项目。 为了用数字化手段对大学博物馆进行数字化改造，建成数字化的博物馆系 统，实现资源共享，保护珍贵的博物馆资源，教育部面向2 1 世纪教育振兴行 动计划“现代远程教育工程”2 0 0 1 年专门设立了“现代远程教育网上公共资源 建设一大学数字博物馆建设工程”项目，拟重点支持8 1 0 个有特色的大学博物馆 数字化改造。山东大学考古数字博物馆项目被列为首批立项的项目，获准启动建 设。 大学数字化博物馆作为一项重要的网络应用，正逐渐从最初保存文物的简单 文字信息发展到对馆藏文物进行包括图像资料、声音解说、电影录像、三维模型 山东人学硕士学位论文 j = = e ! = = l - l = = = ! = = = | _ = = ! = = 一 等多媒体信息内容的全功能数字博物馆发展。这其中三维文物模型是所有展示的 信息中很重要的一部分。在构建三维文物模型过程中，我们采用的是现在虚拟现 实领域研究比较多的三维扫描技术，该技术直接获取三维数据信息并进行模型的 重建，与传统的二维扫描相比，能够最大限度的避免扫描过程中引起的信息丢失。 在扫描技术的选择上，我们选择了三维扫描技术中非接触式主动技术中的结构光 技术，使用加拿大i n s p e c k 公司的i n s p e c k3 d d f 三维扫描仪来对文物进行三维 扫描。 由于三维扫描得到的数据量很大，尤其是对复杂的文物，所产生的文物模型 往往顶点、面片数目都很大。在进行大规模文物模型的实时绘制时，传统的基于 三角片的绘制方法就显得有些力不从心，因而本文对基于点的绘制技术进行研究 探讨，希望利用该技术达到更快的绘制速度。 1 3 几种相关绘制技术 因为传统的基于三角片的绘制无法适应迅速发展的模型复杂度，许多非传统 的绘制技术早已被提出，其中包括基于图像的建模和绘制( i b m r ) 和体绘制 ( v o l u m er e n d e r i n g ) 。基于点的绘制技术同他们有着相似之处，又有其独特的特 点。下面分别介绍一下这几种绘制技术： 1 3 1 基于图像的绘制 基于图像的绘制( i m a g e b a s e dr e n d e r i n g ，i b r ) 和基于图像的建模 f i m a g e b a s e dm o d e l i n g ，i b m ) 技术是近年来计算机图形学领域的热点之一，二者 统称基于图像的建模和绘制( i m a g e b a s e dm o d e l i n g a n dr e n d e r i n g ，i b m r ) 。i b m r 的中心思想是使用一组采样图像来描述虚拟环境的模型，而不是使用传统的基于 几何建模所用的几何图元( 如三角片) 。当绘制新视图时，i b r 是由i b m 所建立 的模型直接生成新视图，不必绘制几何图元和模拟光照效果。新图像的合成是通 过适当的组合原有的图像来实现的。i b r 的最大优点就是绘制时间只与输入及输 出图像像素的数目成比例，与场景的复杂度无关a 基于图像的技术最早的尝试可追溯到电影映像系统( m o v i e m a ps y s t e m ) j 3 】， 而i b m r 作为一种场景表示和绘制的新方法还是最近几年的事a 近几年i b r 技 山东大学硕士学位论文 术发展很迅速，涌现出许多种不同的方法，这些方法大体上可以归纳为以下几类 【4 ： 基于立体视赏的方法 基于视图插值的方法 基于拱强和分层的方法 基于全视函数0 t 翱0 p t i c 豇n c t i o n ) 的方法 基于全视函数的方法是目前i b m r 中最常用的一类方法。全视函数 5 是被 用来描述空间中任意点( x ，y z ) 在任意时刻( t ) 、任意视角 ，日) 、任意波长( n 范围 内所看到的全部光线集合。基于全视函数的方法试图捕获空间任意区域内的完全 光流以重建该函数。但是同时考虑所有7 个参数比较困难，故目前所有的方法都 通过增加约束来简化全视函数，如固定视点、固定时刻，或者约束环境等。该方 法典型的技术包括：q u i c k t i m e v r 系统【6 】、l u m i g r a p h 7 、l i g h t f i e l d 8 、p l e n o p t i c m o d e l i n g 9 和c o n c e n t r i cm o s a i c s 1 0 等。 i b r 虽然有绘制时间与场景模型的复杂度无关的巨大优点，但是一般需要占 用海量的存储空间，同时由于所有这些技术使用的都是与视点相关的采样来表示 场景或物体，所以在视点移动时会产生明显的人工痕迹，而且大部分技术无法处 理动态光照效果。另外，i b r 在处理场景中物体位置的移动、材质属性的改变等 问题时，效率都不高。 1 3 2 体绘制 体绘韦1 ( v o l u r n e r e n d e r i n g ) 1 1 是科学计算可视化中的一项重要绘制技术。现 实世界中的许多物体、自然现象及一些计算模型只能用三维体数据表示，和传统 的计算机图形学相比，对象体不再是用几何曲面或曲线表示的三维实体，而是以 体素( v o x e l ) 作为基本造型单元。对于每一体素，其表面和内部都包含了对象信息， 这是仅用曲线或曲而等几何造型方法所无法表示的。体绘制的目的就在于提供一 种基于体素的绘制技术，它有别于传统的基于面的绘制，能显示出对象体的丰富 的内部细节，体绘制技术包括体数据的表示、操作和绘制三部分内容。 图l 一2 展示了体绘制同传统的面绘制的各自的流程。 山东大学硕士学位论义 图l - 2 两种绘制流程的比较 虽然两种绘制方法都是对三维数据场的绘制，但是由于基本方法的不同，因 而在绘制效果、算法时间、交互性能等多方面都存在着很大的差别。从结果图像 的质量上讲，体绘制要优于面绘制。但从交互性能和算法效率上讲，至少在目前 的硬件平台上，面绘制还是要优于体绘制的。 根据不同的绘制次序，体绘制方法目前主要分两类 1 2 】： 以图像空间为序的体绘制算法( 如体光线跟踪法) 以对象空间为序的体绘制算法( 如体单元投影法) 。 这两类方法各有特点，光线跟踪对内存要求高。单元投影生成的图像精度高， 但是计算时间相对要大得多。光线跟踪难以并行化，而单元投影的并行处理要相 对容易得多。 1 3 3 基于点的绘制 与上面介绍的基于图像的绘制技术相比，基于点的绘制技术采用的是与视点 无关的而不是与视点相关的、以物体为中心而不是以图像为中心的采样表示方 法。可以说该技术介于传统的几何绘制和i b r 之间。 上面介绍的体绘制技术可以说是与p b r 技术最为接近的技术之一a 在体绘 制中，物体就是由一个个采样点，即体素，来表示的。但是体绘制表示的是物体 所占据的整个空间，是一个三维的数据场，这使得体绘制需要极大的存储空间， 绘制速度较慢。与体绘制技术相比，基于点的绘制技术仅使用采样点来表示物体 的表面，是一个二维曲面数据场维数的降低极大的减少了对存储空间的需求， 9 山东大学硕士学位论文 同时在速度方面也有很大的提高。如果说体绘制是用一个三维的空间数据场来重 构图像的话，点绘制方法就是用这个数据场的边界表面来重构图像。当然，基于 点的绘制在生成图像时也借鉴了体绘制中的许多成果，其中包括用于滤波的 s p l a t t i n g 方法 1 3 】。图1 3 显示了基于点的绘制同其他绘制方法的关系。 图】3 基于点的绘制的地位 1 4 基于点的绘制的研究现状 使用点作为绘制元素已有很长的历史了，早在1 9 7 4 年，c a t m u l l 就注意到几 何细分的极限就是点 1 4 1 。随后，点被用来绘制几何难以描述的“软”物体，如 烟、云、尘、火、水、树等 1 5 1 1 6 1 1 7 。基于点的绘制技术这一提法最初是由 l e v o y 和w h i t t e a 在1 9 8 5 年提出的 1 8 】，但是该技术直到最近才逐渐被人们所关 注。 随着基于点的绘制技术研究的逐渐深入，许多学者提出了相应的p b r 绘制 算法，相关的文献也逐渐增多。其中j p g m s s m a n 的硕士论文“p o i n ts a m p l e r e n d e r i n g ” 1 9 1 是关于p b r 的一篇较全面的论述，该文提出了一种采用等边三 角形网格对需要绘制的物体进行重采样得到物体的基于点的表示，然后再采用基 于点的绘制技术绘制出来的方法。 目前应用的比较成熟的p b r 技术则主要有q s p l a t 方法 2 0 1 和s u r f c l 方法 f 2 1 1 。阻下本文将对这两种方法分别加以介绍： 1 a 1q s l a t q s p l a t 方法使用一个树状层次包围球数据结构来进行基于点的绘制，树中每 个节点包含： 球的位置和半径 0 山东大学硕士学位论文 每点处的法向量 法锥面的宽度 颜色值( 可选) 每个节点用4 个字节( 无颜色信息时) 或6 个字节( 有颜色信息时) 表示， 如图1 4 所示： p o s i d 。i n d ，d i u ss ：r en o r m a l n 。w r m i d d t h c o b f n e o p c i 。眦ic o l 。f 1 3h i t s3 b i t 51 4b i t s2b i t s1 6b i t s 图1 - 4q s p l a t 节点布局 该层次结构由输入的多边形网格生成，每个节点对应多边形网格的一个顶 点。原始网格中顶点之间的关联信息被丢弃，但是为了保证生成的图像没有空洞， 每个叶结点的球半径都选的足够大，以保证同周围节点的球相交。 在进行绘制时，层次树按深度优先方法进行遍历。对每个中间节点，将该节 点在屏幕上的投影大小同一个阙值进行比较，如果大于阈值，则继续向下递归： 如果小于阈值或者已经到达叶结点则按该节点的球位置和半径确定的屏幕上的 位置和大小绘制一个“s p l a t ”。其中阈值的大小可由上一帧图像绘制的时间动态 确定，以达到满足用户指定的每秒绘制帧数的要求。一旦用户停止移动鼠标，则 逐渐使用更小的阈值进行绘制，直到达到叶结点或者s p l a t 的大小为一个像素点 为止。 高度压缩的数据结构是q s p l a t 方法的一大特点，在该方法中，每个节点的 球的位置和半径都是相对于父节点进行编码的，而且将它们离散化为1 3 级离散 值，即每个节点的球半径是它的父节点的球半径的1 1 3 至1 3 1 3 之间的一个值- 球心相对于父节点球心的距离是父节点球半径的1 1 1 3 的倍数。每个节点的法向 量也采用离散化表示，用以该点为中心的每个面划分为5 2 x 5 2 网格的立方体上的 网格点来近似记录向量的方向。法锥面的宽度仅用2 位来表示，四个离散值分别 表示该法锥面的半顶角的正弦值为1 1 1 6 、4 1 6 、9 1 1 6 和1 6 1 6 的情况。颜色值离 散化为1 6 位表示。经过上述压缩表示，最大程度的减少了每个节点所占用的字 节数同时误差控制在可以接受的范围内。这样q s p l a t 在内存和外存中数据表 示方式是一样的，绘制时不必先进行解压缩的工作，只需直接将数据调入内存即 山米大学硕士学位论文 可，因而进一步加快了绘制的速度。 由于q s p l a t 主要面向大数据量的模型的快速绘制，因而，尽管采用了相当 大的压缩率，但是每个模型的所需的数据文件仍然很大，尤其是当数据通过网络 远程调入时，则很可能会出现数据传输跟不上绘制速度的情况。为了解决这一问 题，s t r e a m i n gq s p l a t 2 2 方法对q s p l a t 方法进行了修改。因为q s p l a t 可以在递 归过程中的任意层次中止，所以s t r e a m i n g q s p l a t 方法的修改采用了一种非常简 单、直接的方法一旦所需数据尚未传到，则中止递归。这样就可以先行绘制 一个较粗糙的图像，等数据传到后再逐步求精。 1 4 2s u r f e j 另一种主要的p b r 方法是采用“面元( s u r f e l ) ”为基本元素进行绘制的。 该方法采用一种被称为l d c ( l a y e r e dd e p t hc u b e ) 2 3 】的数据结构来存储采样点。 采样时，从互相垂直的三个方向投射光线，沿每条光线记录下与物体的交点，每 个交点均记录法向量、颜色值和材质信息。图1 5 是该采样方法在二维空间情形 的示意。 一燃丰 澎段i 一 il i、卜、 礴 一 、l jjj 一一1 k 、 、 气 一 一 iii 群13 一 - l d l ls u r l ；e i s _1il i - l d l2s u r l e l s 1鞯 一 lti l d l l 图1 - 5l d c 采样( 二维情形) 该方法采用一种类似m i p 图的方法来记录不同分辨率下s u r f e l 的颜色值，称 为“s u r f e lm i p m a p ”。同时，类似于八叉树的表示方法，l d c 被进一步划分为许 多块( b l o c k ) ”，相邻的8 个块合成一个大块，构成上一级父节点，这样就形成 了一个l d c 树( 图l 6 ) 。 1 2 山东大学硕士学位论文 ! = = = d = = = 自 = = = ! l _ e e = = ! = 目= = = 一 图1 - 6l d c 树中的两层( 二维情形) 最后，为了进一步压缩数据量，将采样点的位置向网格点取整，使三个方向 的采样点都落在网格点上，这样，整个l d c 就可以用一个l d i ( l a y e r e dd e p t h i m a g e ) j 2 4 来表示了( 图1 7 ) 。 口l d l1s m 他i s ol d i2s u r f e i s or e s a m p l e ds u r f e l s 0 ng r i dl o c a t i o n s i 璺| 1 - 73 - t o 一1 压缩采样( 二维情形) 具体的绘制过程类似于q s p l a t ，l d c 树从上至下遍历。在前向投影( f o r w a r d w a r p i n g ) ”步骤中，估计每个像素里投影了多少个s u r f e l ，根据需要选择l d c 树相应层次上的节点进行投影。然后s u r f e l 采用z b u f f e r 的方法来进行可见性判 断来完成遮挡选择，不过由于p b r 主要针对大数据量的单个模型进行快速绘制， 遮挡选择的效率提高并不明显。纹理滤波过程同m i p 图类似，根据投影的大小 选择相邻两级颜色值进行插值，再根据每点记录的法向量用p h o n g 模型计算光 照，最后重构出要输出的图像。 s u r f e l 方法使用的记录采样点的方法同i b r 技术中的浮雕纹理贴 ( r e l i e f t e x t u r e m a p p i n g , r t m ) 方法【2 5 】有异曲同工之处，但r t m 只记录了采样点的位置 并没有记录采样点处的其他几何信息( 如法向量等) ，而且，最重要的是，r t m 在生成最终图像时采用的仍然是对几幅预先采集的图像进行变换、拼接的方法， 所以r t m 最多只能算是介于m r 和p b r 之间的一种方法。 山东大学硕士学位论文 s u r f a c es p l a t t i n g 方法 2 6 在s u r f e l 方法上进一步对基于点的纹理表示和反混 淆等问题进行数学上的系统的分析论证，对各向异性的纹理采用了椭圆加权平均 ( e w a ) 的方法 2 7 】进行滤波。 1 5 其他相关工作 基于点的绘制近几年成为已经成为计算机图形学领域的研究热点之一，与之 相关的各种工作也越来越多，已经发展成为一个新的领域基于点的计算机图 形学( p o i n tb a s e dg r a p h i c s ) 。 基于点的绘制的前提是要对需要绘制的物体进行基于点的表示，与i b m r 中 的m 相对应，该步骤可以称为基于点的建模( p b m ) 。在本文的系统中，这一 步骤是通过读入其他格式的原始数据，对其进行加工而完成的。现在已经有一些 专门的基于点的建模的工作。s t a m m i n g e r 等人提出一种新的基于点的采样方法 【2 8 ，对不同的复杂场景可以迅速生成对象空间中的点集。生成的点集的密度足 够在屏幕上生成无空洞的图像。该方法还被用于动态的生成并绘制地形，对某一 地形进行空中浏览。尽管作者在最终绘制时，是采用硬件加速直接绘制点的方法， 但是该方法生成的点集可以适用于各种基于点的绘制方法。m a t u s i k 等人 2 9 1 贝0 第一次尝试对高镜面反射、透明的、半透明的物体进行采样，对这些物体的采样 是十分困难的，该工作以前极少有人涉足。 a l e x a 等人 3 0 】从物体的基于点的表示出发，定义了一种平滑的流形表面 ( s m o o t h m a n i f o l ds u r f a c e ) ，该定义基于微分几何中的局部映射，使用了移动最小 二乘法( m o v i n gl e a s ts q u a r e s ，m l s ) 。作者通过这个表面作为工具，来增加或减 少表示物体的点集的密度，即调整点和点之间的空隙大小，以达到对物体不同精 度表示的要求。 与a l e x a 的工作类似，p a u l y 等人研究了对基于点的表示的模型进行化简的 问题 3 l 】。与传统的三角片表示的模型有大量的网格简化算法类似，基于点的表 示也需要相应的算法来对其进行不同程度的简化，即寻找一个较低密度的点集来 代替原来的点集，而又不至于产生过大的误差。p a u l y 在文中提出了聚类法 ( c l u s t e r i n gm e t h o d ) 、迭代简( i t e r a t i v es i m p l i f i c a t i o n ) 以及粒子模 ! ；j , ( p a r t i c l e s i m u l a t i o i l ) 三种算法对点集进行简化。其中聚类法又分为渐增聚类和层次聚类两 山东大学硕上学位论文 种。 瑞士苏黎世的e t h 大学( e i d g e n 6 s s i s c h et e c h n i s c h eh o c h s c h u l e ) 的计算机图 形学实验室在基于点的图形学方面作了大量的研究工作，他们开发了一个交互式 的基于点的模型编辑系统p o i n t s h o p3 d 3 2 。该系统扩展了传统的二维像素 编辑系统，能够对三维的基于点表示的物体的形状和外观进行交互的编辑，可完 成包括去除噪声、增加纹理、造型、雕刻、滤波、重采样等一些列工作。 1 6 论文安排 论文第二章介绍了原始数据的格式，提出从不同的原始格式到基于点的表示 转换的相应算法。第三章介绍了实际绘制时顶点投影形状的选取，并比较了几种 投影形状的优缺点。该章最后对比了基于三角片的绘制和基于点的绘制两种不同 方法的绘制速度。第四章介绍了l o d 技术的引入及利用顶点间的距离和顶点法 向量偏离程度两个标准，建立不同精度的模型的算法。该章最后给出了引