（计算机应用技术专业论文）基于点的绘制技术的研究与实现.pdf

基于点的绘制技术的研究与实现 中文摘要 基于点的绘制技术的研究与实现 中文摘要 继以三角网格模型为研究对象的几何处理技术发展成熟后，一种新的基于点的 点的数字几何模型处理技术越来越受到研究人员的关注。点绘制技术是数字几何处 理领域的一个新的研究方向，该技术是在点的基础上直接进行造型、绘制以及其他 一些图形处理，抛弃了传统的三角片表示及处理方法，从而为海量点云数据模型的 快速绘制处理提供了一种新的方法。 论文对点绘制技术进行了研究和实现，在对已有研究成果中传统算法进行广泛 和深入分析的基础上设计了一种针对散乱点云数据的点绘制技术路线和方法。论文 的主要研究内容和取得的成果概括如下： ( 1 )设计了一种自适应圆片造型建模算法。该方法建立在对点云数据栅格化、 建立k 邻域和估算法矢的基础上，自适应地确立圆片半径。该方法不仅适合点云分 布均匀的模型，而且有利于提高点云分布不均匀模型绘制的真实感。 ( 2 )引入了基于滤波和空洞修补的图像重建方法。由于点绘制建模算法本身 的特性，点绘制结果中可能存在图像中像素点灰度值出现陡变现象和由于点云数据 局部数据点异常缺失而造成生成图像中出现空洞现象的问题。该方法旨在解决这些 问题，以进一步增强点绘制结果的真实感。 在上述算法研究的基础上，作者开发了一个基于点的建模与绘制原型系统，在 此原型系统上给出的算例结果很好地验证了本文研究方法的正确性和有效性。 关键词：数字几何处理，点绘制，点云，真实感，k 邻域，图像重建 作者郝传刚 指导教师姜晓峰 a b s t r a c tr e s e a r c ha n di m p l e m e n to f p o i n t - b a s e dr e n d e r i n gt e c h n o l o g y r e s e a r c ha n di m p l e m e n to fp o i n t - b a s e dr e n d e r i n g t e c h n o l o g y a b s t r a c t f o l l o w e db yat r i a n g u l a rm e s hm o d e lf o rt h es t u d yo fg e o m e t r yp r o c e s s i n g t e c h n o l o g y ，an e wp o i n t - b a s e dg e o m e t r i cm o d e lf o rg e o m e t r yp r o c e s s i n gi sn o wb e i n g m o r ea n dm o r ec o n c e r n e dt or e s e a r c h e r s p o i n t - b a s e dr e n d e r i n g ( p b r ) i so n eo fn e w r e s e a r c hd i r e c t i o ni nt h ef i e l do fd i g i t a lg e o m e t r yp r o c e s s i n g i ti st or e n d e ra ni m a g e b a s e do np o i n t si n s t e a do fu s i n gt h et r a d i t i o n a lm e t h o do ft r i a n g u l a rm e s ha n do n l y r e c o r d st h ei n f o r m a t i o no np o i n t s ，w h i c hl e a d st oan e w w a yo ff a s tr e n d e r i n gf o rh u g e s a m p l e dd a t a t h i sp a p e rd o e sar e s e a r c ha n di m p l e m e n to np b ra n da l s oh a v ed e s i g n e da w a y f o r p o i n tc l o u d sb a s e do nt h eb r o a dr e s e a r c ha n di n d e p t ha n a l y s i st ot h er e s u l t sw h i c hh a v e b e e ni nt h et r a d i t i o n a la l g o r i t h m t h em a i nr e s e a r c ha n da c h i e v e m e n ta sf o l l o w s ： 1 a a d a p t i v ea l g o r i t h mf o rp o i n t b a s e dm o d e l i n gi sd e s i g n e d t h ea l g o r i t h mi s b a s e do np o i n tc l o u d sd a t ag r i d ，a n dt h ee s t a b l i s h m e n to fk - n e a r e s tn e i g h b o r sa n d c a l c u l a t et h en o r m a l ，a n di tc a ne s t a b l i s ha d a p t i v er a d i u s t h i sa l g o r i t h mi sn o to n l y s u i t a b l ef o ru n i f o r md i s t r i b u t i o no f p o i n tc l o u d sm o d e l s ，b u ta l s ow i l lh e l pt oi m p r o v et h e u n e v e nd i s t r i b u t i o no fp o i n tc l o u dm o d e l s r e a l i s t i ce f f e c t s 2 t h e i m a g er e c o n s t r u c t i o n m e t h o db a s e do n f i l t e r i n g a n di n p a t i n t i n gw a s i n t r o d u c e d a st h eo w nc h a r a c t e r i s t i c so fm o d e l i n ga l g o r i t h m s ，t h er e n d e r i n gr e s u l t sm a y e x i s tt w o p h e n o m e n o n s f i r s t ，t h ei m a g ep i x e l 铲a yv a l u ea b r u p tc h a n g e d s e c o n d ，a sp a r t i a l s a m p l e dd a t ai sa b n o r m a ll o s s e d ，t h eg e n e r m i o no fi m a g e sw i l lh a v es o m eh o l e s t h i s m e t h o di sd e s i g n e dt os o l v e t h e s ep r o b l e m s ，a n dm a k e st h ev i s u a le f f e c tm o r er e a l i s t i c b e s i d e s ，ap r o t o t y p i c a ls y s t e mb a s e do nt h e s ea l g o r i t h m si si m p l e m e n t e di nt h i s p a p e r ，a n ds e v e r a lt y p i c a le x a m p l e sa r eg i v e na sw e l l t h er e s u l t so ft h e s ee x a m p l e s i n d i c a t et h ea v a i l a b i l i t yo ft h ea l g o r i t h m sa b o v e k e y w o r d s ：d i g i t a lg e o m e t r yp r o c e s s i n g ，p o i n t - b a s e dr e n d e r i n g ，p o i n tc l o u d s ，r e a l i s t i c ， k - n e a r e s tn e i g h b o r s ，i m a g er e c o n s t r u c t i o n w r i t t e nb yh a oc h u a n - g a n g s u p e r v i s e db y j i a n gx i a o f e n g i i 图表目录 图2 1 基于点的绘制流程图13 图3 1 点云数据栅格化示意图1 6 图3 2 相邻切平面的法矢调整示意图1 8 图3 3 米老鼠点云数据法矢调整前后的效果对比。2 4 图3 4 圆片造型方法基本思想2 5 图3 5 不同半径绘制出的效果对比2 6 图3 - 6 绘制空间圆片2 7 图3 7 通过z 值消隐2 8 图3 8b u n n y 模型点绘制中光照处理前后效果对比2 9 图4 1 米老鼠点云模型点绘制图形中的走样问题3 1 图4 2 邻域点的集合3 2 图4 - 3 米老鼠模型中值滤波平滑处理前后的效果对比一3 5 图4 - 4f m m 修补原理示意图3 6 图4 5 边界扩散原理3 9 图4 - 6 球体模型点绘制结果中空洞图像修补处理效果4 0 图5 1 原型系统界面4 1 图5 2 原型系统模块划分4 2 图5 3 原型系统设计分层模型4 3 图5 _ 4 三维场景投影n - 维图像4 5 图5 5 基于网格和基于点的绘制效果对比4 6 图5 _ 6 车头模型点云4 8 图5 7 车头模型建模后效果4 8 图5 8 车头模型光照后效果4 9 图5 9 车头模型平滑后效果4 9 图5 1 0 带孔洞海豚模型点云5 0 图5 1 1 带孔洞海豚模型建模后效果5 0 图5 1 2 带孔洞海豚模型光照后效果5 1 图5 1 3 带孔洞海豚模型平滑后效果5 1 图5 1 4 交互选定修补范围5 2 图5 1 5 空洞修补后效果5 2 表5 1 图元基类的主要属性和方法4 4 表5 2 两种绘制方法的计算和显示速度比较4 7 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：主蚪日 期：型! l 尘_ 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：匈焦亟! j 日 导师签名：羔 期 期 基于点的绘制技术的研究与实现 第一章绪论 1 1 数字几何处理技术 1 1 1 数字几何处理技术简介 第一章绪论 数字媒体技术在2 0 世纪后期得到了空前的发展，对人类生活方式产生了巨大的 影响。2 0 世纪数字媒体技术的三个高峰是声音( 1 d ) 、图像( 2 d ) 和视频( 2 d + 时间) 。 声音技术的发展催生了电话、广播和电视等行业的繁荣，使人类远距离获取信息成为 现实。但是人类对声音信息总是将信将疑，更信奉眼见为实，图像技术的发展和广泛 应用满足了人类的这一心理要求，也培育了数码摄影、电脑图片和平面媒体等行业。 图像技术满足了人类对静态的细节、特征和纹理的欣赏要求，但是它们不能准确地描 述和记录现实世界中已经存在的动态画面，满足不了人类对实时和动感的追求，视频 技术的发展和应用，能够使人类多姿多彩的生活得以再现。图像和视频只能从一个侧 面将物体和环境展示给人类，但是人类的追求永无止境，希望从全方位、浸入式和交 互式地与环境交流，就必须发展新的媒体技术，数字几何媒体就应运而生。它是数字 媒体领域内继前三次浪潮之后即将到来的重要的数字媒体载体，将对多媒体技术及产 业甚至人类生活带来根本性的变化【l j 。 数字几何媒体又称为3 d 媒体，其主要载体称为点云，是由物体模型表面上一系 列空间采样点构成的、对模型描述的边界表示【2 】。构成点云曲面最基本单位点以 及与之关联的表面属性，称为“面素 ( 相对于像素、体素) ，也可以称为表面体烈3 1 。 每一个面素既包含有几何信息，如位置和法向量等，又包含有它的表面属性，如材料、 纹理、光照参数和透明度等，用户还可以附加其它有用的表面属性。从模型表示的角 度看，点云曲面提供了一种三维几何体的完整、离散的表示方式，这一方面降低了绘 制过程对模型表示方式的依赖程度，丢掉了对绘制无关的拓扑关系，从而有利于快速 的绘制；另一方面为基于完全离散几何数据空间处理方法和变换域内的信号处理技术 开辟了新的研究方向。 第一章绪论基于点的绘制技术的研究与实现 1 , 1 2 数字几何处理技术的应用 数字几何处理技术有着非常广泛的应用，与人类很多科研活动及日常生活息息相 关。 ( 1 ) 产品设计领域。目前该领域面临的主要问题之一是如何有效地设计复杂的曲 面及进行曲面数据的交换，人类对新产品的追求是无止境的，而传统的参数曲面设计 方法满足不了这种要求。不同的曲面设计系统中的曲面基元及数据组织有自己特有的 数据表示方式，这就使组成不同的系统之间的数据无缝交换出现困难，而当曲面模型 都是用点云来表示时，这个问题就能比较好地得到解决。 ( 2 ) 动画制作领域。现代动画形象对外部造型要求越来越高，特别是对媒体角色 的逼真度提出了苛刻的要求。在一部动画片中，动画及环境角色可能成千上万，数字 几何处理提供了直接从现实模型得到数字模型的方法，这样一个直观高效、稳定可靠 的造型工具将推动动画制作技术迈向新的台阶。 ( 3 ) 反求工程领域。反求工程是从已有的实体模型重建曲面模型，现行的处理方 法是通过三维扫描仪输入实体数据，然后用解析曲面模型来拟合或逼近这些数据。但 实际上，利用点云曲面模型表示曲面，研究直接从点云到后续加工处理的方法，无须 引入中间连续曲面。 ( 4 ) g i s 领域应用。大规模g i s 的数据通常是卫星深度图像，数据量巨大，应用 数字几何处理技术能够大幅简化模型，缩小数据量，复原真实三维地貌。在城市g i s 系统中，要得到比较真实的建筑物模型，一种快捷的方法是用高速三维测量仪获得数 据，进行三维合成。 ( 5 ) 自然文物的保护。出于文物保护的需要，一般不能用接触式方式获取它们的 三维数据，只能用非接触式的三维扫描仪定期获取数据，从而通过比较来判断毁损程 度，并决定是否需要进行修复。对于已经毁损的文物，可通过数字几何处理技术得到 它的三维模型，首先在电脑里进行复原，最后确定实际复原方案。 1 1 3 数字几何处理技术研究现状 数字几何处理技术开辟新研究方向的同时也提出了新的挑战。目前面临的主要难 2 基于点的绘制技术的研究与实现第一章绪论 题在于，与前三次浪潮相比，不能依赖现有的理论、经典方法和成熟的算法来解决其 中的难题，必须从理论基础到实现方法都重建新的体系。自2 0 世纪9 0 年代以来，国 际上许多著名研究机构在这方面已经开展了研究工作，并取得了巨大的进展，但是离 广泛应用还有较大的距离。近几年，我国学者开始介入这个具有巨大前景的新媒体领 域。国家自然科学基金委对这个研究主题进行了重点项目立项，在进行了一系列基础 研究工作以后，以北京大学查红彬教授为组长的跨高校课题组承担了国家自然基金重 点项目数字几何处理的理论框架与关键技术研究，将对数字几何处理的研究和应 用做出新的贡献，推动数字几乎媒体在我国的广泛应用i l j 。 1 2 基于点的绘制技术 1 2 1 起源 基于点的绘制技术是数字几何处理技术研究领域的最新进展之一。该技术是在点 的基础上直接进行造型、绘制以及其他一些图形处理。点作为三维建模的一种基本表 示元素在图形学中已有近二十年的历史。早在1 9 8 3 年，r e e v e s 采用粒子作为数据处 理的基本元素来模拟火和爆炸的状态【4 】。但是此后学术反响一直不明显，直到2 0 0 0 年，随着斯坦福大学计算机形学实验室的数字化米开朗基罗项卧5 】的进展，出现了大 规模点云数据以及相关的研究工作，在随后几年，基于点的绘制研究成为了一个新的 研究热点。 1 2 2 与传统方法的比较 在计算机图形学领域内已经提出了很多成熟的曲面表示方法，包括多边形、样条 曲面、隐式曲面以及各种各样的混合表示方法。这些曲面表示最终都被转化为三角形 表示以便采用常规图形绘制硬件进行绘制。图形硬件的高速发展以及对几何表面三角 化算法的深入研究进一步巩固了三角网格在图形绘制以及造型中的地位【6 j 。然而，随 着研究以及应用的不断深入，人们对场景绘制的真实感与速度要求越来越高，几何场 景变得越来越复杂。特别是在虚拟现实中，为达到逼真的显示效果，用于构造场景的 三角片数量往往数以亿计。尽管硬件性能不断发展，但仍然不能满足场景实时绘制的 第一章绪论基于点的绘制技术的研究与实现 需求。海量数据场景、更高的真实感实时动态交互仍然是当今图形技术所面临的巨大 挑战。从造型的角度上看，基于几何面片的场景造型方法往往需用大量的多边形来描 述场景细节，不仅造型工作量巨大，而且给实时绘制带来极大的困难。从空间存储的 角度看，基于多边形表示的实体的基本信息包括几何信息与拓扑信息，通常采用一个 顶点表和一个三角形表来分别存储，三角形数量约是顶点数目的两倍。绘制时不仅要 传输顶点表，而且还要传输三角形表。场景复杂度越高，效率问题就越突出。此外， 随着近年来3 d 数字扫描仪的日益普及与应用，扫描获取的几何体的细节以及外形更 加丰富，迫切需要新的能有效表示、处理以及绘制超大规模、高度复杂的几何模型的 方法。3 d 扫描仪输出目标物体的大量密集采样点，这些点相互之间没有任何拓扑关 系。传统方法需将扫描获得的离散采样点转化成多边形模型再作进一步的处理及绘 制，但随着采样数据规模的不断扩大，多边形模型转化或重构的方法变得越来越低效， 多边形表示方法的局限性变得更为明显。综合以上几个因素，基于点的绘制技术相对 于传统的基于多边形的绘制技术具有以下优势： ( 1 ) 基于点的绘制特别适合于表示表面几何高度复杂或具有复杂表面光照细节 的模型，如雕塑与石刻，也能用于火焰、流云、落叶、树木等自然场景的模 拟。 ( 2 ) 基于点的表示方法很少冗余，能显著地节约存储空间。由于点之间相互独立， 无拓扑关系以及邻接关系，也无需存储多边形网格表。 ( 3 ) 现在的图形硬件无一例外地支持直接点绘制，可以利用多边形硬件加速点模 型绘制1 7 j 并达到理想的绘制效果。另外还有非常重要的一点，由于表示模型 的点的独立性，基于点的绘制允许高度的并行处理。 ( 4 ) 可以直接应用于扫描所获取庞大均匀的采样点集，回避了复杂的网格生成过 程；同时模型绘制平面的投影结果很可能小于一个像素，没有必要绘制三角 网格。 概括地讲，点云简化了实体表示方法而只保留最重要的信息。尽管其中不存在拓 扑信息而使得数据结构变得非常简单，但它同时也给传统图形处理技术和方法带来了 很大的困难与挑战。 4 基于点的绘制技术的研究与实现 第一章绪论 1 2 3 研究现状 近年来由于一些学者和研究人员的不懈努力，在基于点的计算机图形绘制技术领 域取得了很大的进步。尤其近几年取得了一系列重要进展，在一些方面形成了相对较 成熟的理论和方法。基于点的计算机图形学的一般流程可概括为点云的获取、点云的 处理与建模以及点云的绘制三个阶段。首先利用3 d 扫描设备将目标实体进行数字化 采样，得到原始的粗糙数据；然后转化为适当的表示形式，以便适合于后期处理与造 型；最后，采用合适的绘制方法将模型显示出来。随着获取点云数据规模的迅速增大， 速度和质量问题成为基于点的计算机图形学的研究热点。下面简要回顾和总结一下研 究人员在点绘制技术的速度和质量方面已经取得的成果。 在提高方法速度的研究方面，2 0 0 0 年的s i g g r a p h 大会上展示出的q s p l a t 技术 【8 】是点绘制技术的重要突破。与传统层次结构的最大的不同在于，每个节点自身可以 被看作是在一定分辨率下的一个表面重采样点，而这个点代表了其局部区域所有采样 点的信息。当不影响绘制精度、或者是绘制实时性相对更为重要的时候，可通过绘制 该点来代替对它下属的所有子节点的绘制，从而提高绘制效率。2 0 0 1 年，r u s i n k i e w i c z 等人提出s t r e 锄i n gq s p l a t 的概念【9 1 ，将模型序列化为线性结构，从而能在网络中快 速传输点模型。由于其绘制仍通过层次树遍历来完成，因此只能由软件实现。以上算 法侧重于绘制的效率，这类算法虽然高效，但会产生严重的图形走样问题【l o j 。因此点 绘制技术中另一部分重要的研究工作是着眼于如何提高点绘制的质量。2 0 0 0 年， p f i s t e r 等人率先提出用面元( s 诚1 ) 来代表一个采样剧3 1 。在绘制时，首先通过可见性 预处理去除被遮挡的点，然后将可见点投影到屏幕空间，并在屏幕空间进行二维图像 重建而得到光滑图像。2 0 0 2 年r e n 等人【_ 7 】推导出物体空间的e w a 滤波算子，并基于 可编程图形硬件获得了每秒约1 5 0 万个点的绘制效率。2 0 0 3 年，k o b b e l t 等人提出了 一种基于高斯滤波的点模型图形硬件加速方法【1 1 1 ，取得了更高的效率。他们的算法在 绘制效果上逊色于e w a ，并且没有考虑点模型的层次结构，从而缺乏处理大规模的 点模型场景的能力。此外，在绘制元素的定义中充分结合局部区域的曲率特性，也可 以很有效地改善表面绘制中的走样现象【1 2 1 。根据点的采样密度确定采样点坐标和法向 量的量化尺度，可以实现点云数据的高效绘制【】引。物体的绘制是在二维平面上生成三 维视觉效果的真实感图形，但有时我们不需要生成真实感图形，而要得到可简单表现 第一章绪论基于点的绘制技术的研究与实现 物体的二维非真实感图形。此时研究的重点转向了如何用少量的点来表现物体，满足 人的视觉识别需要。物体的特征轮廓在图形绘制过程中起着关键作用，掌握特征轮廓 成为人们快速识别物体的关键。由于特征轮廓只需要使用点云中一少部分点来表现物 体，所以对于大规模点云表示的物体的快速非真实感显示具有重要意义。目前在特征 轮廓的检测方面，人们已经做了大量工作，提出了很多检测算法。归纳起来，这些算 法可归为三个范畴：图像空间、物体空间以及混合图像和物体空间【1 4 1 。早期有代表性 的图像空间算法是由s t a i t o 和t a k a h a s h i 1 5 j 提出的，他们采用图像增强技术，用 g b u f f e r s 计算阴影线和边缘线。图像空间算法的好处是可将现有的图形硬件和绘图 软件用于算法使用的缓存，算法相对简单和易于实现。而且该算法复杂度依赖于图像 的屏幕分辨率，而不依赖于模型的基元数量。当然它也存在一些问题，即在模拟轮廓 线时需曲线拟合，速度慢，且不适于交互和实时应用。物体空间算法【1 6 】【1 7 】【1 8 】直接在 物体空间提取特征轮廓线，这种算法要解决可视化问题，即只绘制那些未被遮挡的特 征轮廓线。它的复杂性依赖于输入数据的量的大小。混合图像和物体空间算法以非传 统方法绘制物体，结果在图像空间显示。r u s t a g i 讨论了用于检测物体外轮廓的基于 模板的算法【l 踟；r a s k a r 和c o h e n 描述了在图像空间中计算面向用户和背向用户的邻 接面的交线算法【2 0 1 ；r o s s i g n a c 和e m m e r i k 提出了一个双通道算法，可计算边缘轮廓 和特征线2 1 】；g o o c h 等人提出了使用模板缓冲器的简便方法【2 2 】。混合算法和图像空 间算法一样可获得硬件加速，但主要问题仍然是需进行曲线拟合生成逼真的特征轮廓 线。在特征轮廓点的检测方面，虽然已经有一些研究人员做了大量的工作，但根据视 点和实时交互的要求来决定显示哪部分特征及显示哪一级别特征的研究工作和成果 还很少。 1 3 论文选题依据、研究内容、目的及意义 三维图形绘制技术是计算机图形学的一个重要的研究领域，它旨在根据给定的视 点和视线方向，快速和逼真地生成三维场景的二维图像。长期以来，对图形绘制技术 的研究一直围绕着绘制速度和真实感这两个方面展开。一般情况下，图形显示结果的 真实感愈强，需要的计算量和计算时间就愈多，其绘制的速度也将降低。相反的情况 下，如果减少绘制时间，则绘制结果的真实感亦将相应地降低。 6 基于点的绘制技术的研究与实现第一章绪论 相应地在实际应用中也通常将绘制技术分成实时绘制技术和离线绘制技术两类。 前者侧重于绘制的速度，其真实感允许在一定程度上降低；后者则研究如何尽可能地 保证绘制结果的高度真实感。 近年来随着大规模测量和扫描设备的广泛应用，可获取模型数据量在飞速增长， 表面复杂度也在不断提升，因此基于采样点的模型表示在近几年的三维数据处理技术 的研究和应用中占据了一定的地位。这种模型表示方法最大的特点是不需要记录和保 存采样点间的拓扑关系。这种新的处理方法不但可以大大降低模型的存储需求，并且 在计算过程中具有很高的灵活性，特别是在模型的绘制操作中。然而该处理方法也存 在固有的弊端，一些测量过程中由于测量方法和误差等种种原因将导致点云结果出现 稀疏密度不均的缺陷，这样的点云在现有的基于点的绘制技术下将出现局部空隙或空 洞现象，由此将大大降低显示结果的真实感。 基于上述分析，在对数字几何处理技术相关领域、特别是点绘制技术已有研究成 果进行充分调研的基础上，作者选择了“基于点的绘制技术”作为论文研究课题。论 文研究内容简要概括如下： ( 1 ) 在深入研究与分析原始点云数据特征的基础上，设计了一种基于自适应圆片 造型的点绘制建模算法。该算法不仅在真实感效果上得到了明显的提高，而 且降低了后续二维图像处理环节的计算复杂度。 ( 2 ) 为了弥补由于点云数据不完整和稀疏密度不均等原因造成三维建模不足并 从而使得生成的二维图像中可能产生空洞现象的缺陷，设计了一种交互式的 图像重建方法。 ( 3 ) 在上述基础上，设计了相关数据结构与算法程序，实现了一个原型系统。 论文课题的研究将在一定程度上推进国内在基于点的绘制领域的研究深度，并对 促进数字几何处理技术在国内的研究和应用进程贡献微薄的积极作用。 1 4 论文结构 结合作者的实际工作，论文总结和阐述了作者在研究过程中采用的技术方法和取 得的初步成果。论文结构如下： 第一章，绪论。该章概述了数字几何处理及基于点的绘制相关技术的概念、应用 第一章绪论 基于点的绘制技术的研究与实现 与研究现状，并据此引出本文的选题与研究内容。 第二章，基于点的绘制技术路线分析。该章系统概括了点绘制技术的研究动态， 并给出了作者在研究过程中所采取的技术路线。 第三章，基于自适应圆片造型建模算法。该章阐述了点云邻接关系建立、点云法 矢估算算法以及在此基础上的基于自适应圆片造型的建模算法。 第四章，二维图像重建。该章引入了基于滤波和空洞修补的图像处理方法重建二 维图像。 第五章，原型系统的实现。该章总结了原型系统的设计与开发过程，并给出了在 此原型系统上的典型算例结果，验证了作者研究算法的正确性。 第六章，总结与展望。该章在总结全文工作的基础上，对今后进一步研究与工作 的方向进行了展望。 8 基于点的绘制技术的研究与实现 第二章基于点的绘制技术路线分析 2 1 引言 第二章基于点的绘制技术路线分析 点云是建模和图形绘制的最基础的数据来源，而点云数据既可以从真实的物体表 面上通过测量获得，也可以从已有几何模型( 多边形网格模型、样条曲面模型、隐式 曲面和实体模型等) 中直接获得。在点云获取的基础上，无论采用何种图形绘制技术 路线，首先是要基于离散点云集合对物体进行几何造型，建立该物体的几何模型。 基于点的绘制方法在造型处理环节的基本思想是在点的基础上将点通过某种策 略直接扩展为一个区域，该区域常见的形式为四边形、圆或椭圆等。虽然一般情况下 通过现有测量技术手段能够获取具有足够密度的点集，但由于实际测量工艺和物体表 面形状缺陷等原因经常会发生点云数据分布密度不均匀，模型表面会出现空洞现象。 因此，如何在造型环节中引入合理和优化的点区域扩展策略以及对图形绘制结果在图 像空间进行重建处理来解决和避免空洞现象是点绘制技术研究过程中的重点。 近年来国内外很多学者和研究人员在点绘制技术方面进行了一定的研究工作，并 取得了一些成果。作者在对这些研究成果进行深入调研和分析的基础上开展了论文研 究工作，通过采用“自适应圆片”和“基于滤波和空洞修补的图像重建”技术和方法， 有效地解决了点绘制技术在显示结果中存在的空洞问题，并获得了较好的真实感效 果。 2 2 已有点绘制典型算法 点绘制技术中最关键的处理环节是由离散点在屏幕上快速重建没有空洞的连续 表面。根据表面重建采用的不同方法，基于点的绘制算法可以分为两大类：图像空间 的点绘制算法和物体空间的点绘制算法，以下就分别从这两类算法对已有研究成果进 行分析和总结。 9 第二章基于点的绘制技术路线分析 基于点的绘制技术的研究与实现 2 2 1 图像空间的点绘制算法 基于图像空间的点绘制技术是以面元( s 毗1 ) 作为基本的绘制图元【3 j ，类似于光栅 化多边形网格的方法。 g r o s s m a n 和d a l l y 2 3 】在互相垂直的三个方向的等边三角形网格上对物体进行采 样，并记录点的法向量、颜色值和深度信息，采样点被分成8 8 的块进行存储。绘 制过程中，先通过视景体和可见锥进行块的可见性测试，再将可见块中的点转换成屏 幕空间的像素。算法使用低分辨率层次深度缓冲区结构存储数据和探测裂痕，这种方 法在将采样点投影转换到目标图像的同时，使物体的每一部分能够以足够低的分辨率 显示，对图像可能出现的裂痕，通过比较图像深度值和层次缓冲器中的深度值进行探 测和弥补。在探测裂痕时，算法对每一个像素赋予一个值在 0 ，1 之间的权重。该权重 表示其可见颜色的信任度，对第k 层深度缓冲器的像素，将其看作是覆盖4 。个屏幕像 素的不透明正方形，经过比较正方形角点深度与屏幕像素深度，再通过双线性插值， 得到当前层像素的权重。表面重建时，对于权重小于1 的像素( 即空洞) ，对离它最 近的三个低分辨率像素，分别赋予1 2 ，1 4 和1 4 的权重进行插值，用低分辨率图像 填充高分辨率图像。这种方法生成的显示结果含有较为明显的块状人工痕迹。 p f i s t e r ：】提出了面元( s u f f e l ) 的概念，在图形生成中增加了纹理滤波处理。算法主 要思想是从互相垂直的三个方向投射光线进行采样，沿每条光线记录与物体的交点， 每个交点均记录法向量、颜色值和材质信息。采样点存储在一种被称为l d c ( l a y e r e d d e p t hc u b e ) 的数据结构中，类似于八叉树的表示方法，l d c 被进一步划分为许多块， 相邻的8 个块合成一个大块，构成上一级父结点，进而形成一个l d c 树：同时，采 用一种类似m i p m a p 图的方法来记录不同分辨率下面元的颜色值。绘制时，首先进行 块选择，从上至下遍历l d c 树，对每个结点均作可见性选择和背向选择，抛弃不可 见的结点和它的子结点。在投影转换中，估计每个像素里投影面元的数量，根据需要 选择l d c 树相应层次上的结点进行投影，然后采用z - b u f f e r 的方法对面元进行可见 性判断来完成遮挡选择。纹理滤波过程同m i p m a p 图类似，根据投影的大小选择相邻 两级颜色值进行插值，再根据每点记录的法向量用p h o n g 模型计算光照，最后重建出 要输出的图像。 l o 基于点的绘制技术的研究与实现第二章基于点的绘制技术路线分析 p f i s t e r 方法绘制的图像质量有了明显的改进，但仍然存在着色不连续性问题， z w i e k e r i i o 】在p f i s t e r 方法上进一步对基于点的纹理表示和反走样等问题上进行了一定 的改进，对各向异性的纹理采用了椭圆加权平均( e w a ) 的方法进行滤波，提出了 表面足迹法( s u r f a c es p l a t t i n g ) 。算法对每个足迹赋予一个半径对称的高斯滤波内核， 通过各足迹数据( 颜色和法向量等) 的加权平均重建连续表面，绘制图像的品质好。 但由于算法全部基于软件实现，当绘制高度复杂的模型时运行效率较低。 b o t s c h 1 1 】等通过图形硬件实现基于高斯滤波的表面足迹法，该方法中存在的问题 是当两个足迹投影到同一像素时，只有紧紧覆盖的足迹可以融合，而当足迹间z 值的 差值超过某个阈值时，最前面的足迹应覆盖后面的足迹，即需要进行模糊深度检测。 当前图形硬件的图形处理单元( g p u ) 无法完成这些任务，故采用两步绘制过程。首先 以偏移视点s 的距离对所有物体绘制，填充z b u f f e r ，然后以高斯融合绘制所有足迹， 而不改变z b u f f e r 值，因此融合只对z 差值小于f 的足迹进行。使用当前图形硬件的 像素着色器，将每个足迹绘制为一个顶点，通过计算顶点着色器内投影区域的大小绘 制屏幕上一个正方形。基于高斯滤波的硬件处理方法，绘制速度有了明显提高。由于 当前图形硬件是专门针对基于三角形绘制的优化，因此在绘制性能上，基于点或足迹 的方法不如基于三角形绘制方法。 大部分图像空间的点绘制方法将每个足迹的法向量作为常量对足迹进行光照处 理，这相当于对三角片网格进行平面明暗着色处理。基于高斯重构内核的滤波方法相 当于三角片的u 1 1 d 明暗着色处理，虽然着色光滑，但图像模糊不清。使用变化的 法向量和单像素光照处理可大大改进图像质量，三角片网格的p h o n g 光照模型就是利 用三角形顶点法向量插值计算三角形内各像素法向量，对每个像素进行光照处理，从 而能够得到更好的图像质量。由于基于点绘制过程中缺少点之间的连接信息，为了得 到每个像素的法向量，b o t s c h 对每个足迹赋予线性法向量，得到了具有类似p h o n g 光照模型效果的图像【l 。 2 2 2 物体空间的点绘制算法 r u s i k i e w i z f 8 】的q s p l a t 方法是物体空间的点绘制算法的代表。该算法的基本思想 是，使用一个树状层次包围球数据结构存储数据，树中每个结点包含球的位置和半径、 第二章基于点的绘制技术路线分析基于点的绘制技术的研究与实现 每点处的法向量、法锥面的宽度以及颜色值。在进行绘制时，层次树按深度优先方法 递归遍历。对每个中间结点，首先判断该球是否完全在屏幕之外或者是完全背向以进 行可见性选择。如果该结点至少有一部分子结点是可见的，则将该结点在屏幕上的投 影大小与一个阈值进行比较。如果大于阈值，则继续向下递归；如果小于阈值或者已 经到达叶结点，则按该结点的球位置和半径确定的屏幕上的位置和大小绘制一个小区 域。其中阈值的大小可由上一帧图像绘制的时间动态确定以达到满足用户指定的每秒 绘制帧数的要求。 数据结构的高度压缩是q s p l a t 方法的一大特点，在该方法中每个结点的球的位 置和半径都是相对于父结点进行编码的，而且将它们离散化为1 3 级离散值，即每个 结点的球半径是它的父结点的球半径的1 1 3 至1 3 1 3 之间的一个值，球心相对于父结 点球心的距离是父结点球半径的1 1 3 的倍数。每个结点的法向量也采用离散化表示， 用以该点为中心的每个面划分为5 2 x 5 2 网格的立方体上的网格点来近似记录向量的 方向。法锥面的宽度仅用2 位来表示，四个离散值分别表示该法锥面的半项角的正弦 值为1 1 6 、4 1 6 、9 1 6 和1 6 1 6 的情况，颜色值离散化为1 6 位表示。经过上述压缩表 示，最大程度减少了每个结点所占用的字节数，同时误差控制在可以接受的范围内。 这样q s p l a t 方法在内存和外部存储器中数据表示方式是一样的，绘制时不必事先进 行解压缩处理，只需直接将数据调入内存即可，因而进一步加快了绘制的速度。 由于q s p l a t 方法主要面向大数据量模型的快速显示，因而尽管采用了相当大的 压缩率，每个模型所需的数据文件仍然很大，尤其是当数据通过网络远程调入时，则 很可能会出现数据传输速度低于显示速度的情况。为了解决这一问题，r u s i k i e w i z t 9 】 对q s p l a t 方法进行了修改，当所需数据尚未传输到位时则中止递归。这样就可以先 显示一个较粗糙的图像，等数据传到后再逐步求精显示。 深度优先递归遍历树的方法不能有效利用当前的图形硬件图形处理单元( g p u ) ， 为此d a c h s b a c h e r 等提出了顺序l o d 树结构，在绘制某个细节的模型时，直接由图 形处理单元处理连续的线性点列表，g p u 将点列表送入视频存储器并进行层次细节 选择，因而降低了对c p u 的压力。这种方法的不足之处是，作为绘制基本元素的小 区域是没有经过滤波的正方形，因此有待结合其它方法以提高图形显示结果的品质。 1 2 基于点的绘制技术的研究与实现第二章基于点的绘制技术路线分析 2 3 本文技术路线分析 通过对上述两类点绘制算法的深入分析，可以发现这两类方法的工作重点是在丰 富点云属性( 如法向和颜色等) 的基础上提高真实感效果。而论文研究过程中所基于 的点云数据是只包含基本三维坐标的散乱点云，因此只能在上述已有研究成果所给出 方法基本思想的基础上独立地设计本文研究的技术路线，并以此深入研究其中的关键 技术环节。 本文结合了图像空间绘制方法的基本思想，设计了一种自适应的基于点的建模算 法。为了提高真实感效果，引入了一种交互式的二维空间图像处理方法。 本章前面引言部分已经述及，由于原始点云分布密度不均匀将导致点绘制在建模 阶段的空洞现象。在论文研究过程中，设计和采用了两种处理方法：( 1 ) 自适应确定 面元大小。将每一点扩展成一个区域，使得这些区域互相交叉并覆盖物体表面，这样 就可以在一定程度上避免由于点云密度问题导致的表面空洞。( 2 ) 图像重建。这种处 理方法对前面处理环节的补充，是在图像空间中对所生成的图像进行滤波和空洞修补 处理，以获得更强的真实感效果。 点云栅格化 0 创建i d 匠邻 0 计算法矢 上 求解面元半径 0 基于点的建模 二维图像重建 图2 1 基于点的绘制流程图 1 3 第二章基于点的绘制技术路线分析基于点的绘制技术的研究与实现 如图2 1 所示，论文研究技术路线概括如下： ( 1 ) 首先将点云数据进行栅格化，通过遍历邻接栅格内的点，建立点云中相邻点 之间的邻接关系； ( 2 ) 在邻接关系建立的基础上对点云中的点进行局部曲面特征信息估算，估算出 曲面在该点的法矢信息； ( 3 ) 利用点的邻接关系，自适应计算每个面元的半径大小； ( 4 ) 使用点的坐标、法矢方向和面元半径属性进行基于点的自适应圆片建模； ( 5 ) 将建模结果投影到二维图像空间，进行消隐和光照处理； ( 6 ) 在第5 步生成的图形结果的基础上，结合交互操作进行二维图像重建工作， 以生成最终点绘制结果。 2 4 本章小结 点绘制技术是近年来在数字几何处理和真实感图形生成技术研究领域中新的研 究方向和热点之一。本章在对已有两类点绘制算法的