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

首都师范大学硕士学位论文基于点的造型与绘制技术的研究 摘要 随着计算机图形学的飞速发展，三维计算机图形学已经渗透到计算机应用的 方方面面。人们对计算机造型与绘制技术的要求不断提高，计算机模拟场景的规 模越来越大，景物的细节也越来越丰富。特别随着三维数码扫描仪的大规模普及 与应用，扫描所得到的网格点的数目达到了十亿的数量级，扫描获取的几何体的 细节以及外形的目渐丰富，对有效生成、处理超大规模几何模型的新方法的需求 也日渐增长。采用传统的基于三角面片的绘制方法，现有的计算机硬件难以达到 实时绘制的要求，绘制环节成为了瓶颈。近年来，一种新的绘制三维模型方法一 “基于点的绘制”开始逐渐被人们所重视，随着对其研究的不断发展，逐渐成为 计算机图形学中研究热点。 本文首先介绍了基于点的获取、处理以及绘制的全流程，基于点表示曲面的 性质和基于点表示曲面的方法，以及目前常见的几种基于点的造型技术。本文主 要工作： ( 1 ) 基于k o h o n e n 神经网络能够保持拓扑结构的自组织映射的特性，对散 乱数据点进行曲面重构，建立了基于自组织特征映射神经网络的矩形网格重构模 型。所建模型利用神经元对曲面散乱数据点的学习和训练来模拟曲面上点与点之 间的内在关系，节点连接权向量集作为对散乱数据点集的近似化并重构曲面样本 点的内在拓扑关系。通过该方法得到的曲面可以对原始的散乱数据点集逼近，可 以作为后继曲面重构的初始曲面，而且还可以对密集散乱数据点自组织压缩，并 构建保持原数据点集的拓扑形状，这样降低原始数据点的数量，扩大了神经网络 曲面重构方法的应用领域。 ( 2 ) 主要根据径向基函数神经网络( r b f n n ) 具有很强的非线性逼近能力， 以及强大的抗噪、修复能力等优点，提出将径向基函数神经网络应用于带有噪声 数据散乱数据点自由曲面的重构方法，并对该方法理论上的可行性和实践上的 实用性进行了讨论和验证。结果表明：该模型不仅能够有效地逼近不完善的、带 有噪声的曲面，而且学习速度很快，提高了对破损、不完全曲面重建的效率和精 度，得到的曲面光顺性好。 本文最后部分主要介绍了基于点绘制的技术，以及基于点的绘制方法、基于 点绘制技术存在问题和基于点的绘制技术的进一步研究方向。 关键词：基于点的绘制，基于点的造型，k o h o n e n 神经网络，b 样条曲面，径向 基函数神经网络，非均匀有理b 样条 首都师范大学_ 顷士学位论文基于点的造型与绘制技术的研究 a b s t r a c t w i t ht h er a p i dd 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 p e n e t r a t e dm a n ya p p l i c a t i o n w i t hc o n t i n u o u s l yd e v e l o p i n go fc o m p u t e rm o d e l i n g a n dr e n d e r i n gt e c h n o l o g yo fr e q u i r e m e n t ，t h ec o m p u t e rm o d e l st h es i z eo fw a x t d i n g s c e n eb e c o m i n gb i g g e r , t h ed e t a i l so f s c e n e r yb e c o m em o l ea b u n d a n t e s p u c i a l l y , w i t h l a r g e - s c a l ep o p u l a r i z a t i o na n da p # i c = i o no f3 dd i g i t a l 龋锄氆c t h em m a l m ro f 毋! i d p o i n t sw h i c ha r eg o tb ys c a n n i n gi sr e a c h i n ga tb i l l i o n ，t h ed e t a i l sa n df o r mw h i c ha r c g o tb ys c a n n i n ga r cb e c o m i n gm o r ea b u n d a n t ，t h er e q u i r e m e n to f e f f i c i e n ta n d t r e a t i n g 、v i l l lt h eb i gm o d e lo ft h en e wm e t h o di si n c r e a s i n g i fu s i n gt r a d i t i o n a l t r 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 a r ec a n n o tr e a c ht h er e q u i r e m e n to f i 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 r e c e n t l y , an o v e lt e c h n i q u ep o i n t - b a s e d r 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 np o i n t - b a s e d r e n d e r i n g , p o i n t - b a s e dr e n d e r i n gw i l lb e c o m et h er e s e a r c hh o tp o i n to fc o m p u t e r g r a p h i c s t h i sp a p e rf i r s ti n t r o d u c e st h ew h o l ef l o w so fp o i n t - b a s e do b t a i n i n g , d i s p o s i n g a n dr e n d e r i n g ，t h ep r o p e r t i e so fp o i n t - b a s ed e n o t i n gs u r f a c e ，a n dt h ep r e s e n tp o p u l a r s e v e r a lp o i n t - b a s e dm o d e l i n gm e t h o d s ( 1 ) b a s i n go nk o h o n e nn e u r a ln e t w o r k ss e l f - o r g a n i z i n gf e a t u r em a po f b e i n g c a p a b l eo fk e e p i n gt o p o l o g i cs t r u c t u r e , s u r f a c ei sr e c o n s t r u c t e df r o ms c a t t e r e dd a t a p o i n t s ar e c t a n g l em e s hr e c o n s t r u c t i o na p p r o a c hb a s e do nt h es e l f - o r g a n i z i n gf e a t u r e m a pn e u r a ln e t w o r ki sd e v e l o p e d 。t h ei n h e r e n tt o p o l o g i cr e l a t i o n sb e t w e e nt h e s c a t t e r e dp o i n t so nt h es u r f a c ea r el e a r n e db yt h es e l f - o r g a n i z i n gf e a t u r em a pn e u r a l n e t w o r k t h ew e i g h tv e c t o r so ft h en e u r o n so nt h eo u t p u tl a y e ro ft h en e u r a ln e t w o r k a r eu s e dt oa p p r o x i m a t et h es c a t t e r e dd a t ap o i n t s b yt h i sa p p r o a c h ，i ti sn o to n l yt o a p p r o x i m a t et h es c a t t e r e dd a t ap o i n t sa n dt h es u r f a c ew h i c hi sr e c o n s t r u c t e db yt h i s m e t h o dc a l lb ea sb a s es u r f a c ef o rf u r t h e rp r o c e s s ，b u ta l s ot h ed e n s es c a t t e r e dd a t a p o i n t sc a nb er e d u c e dt ot h er e a s o n a b l es c a l e a n dc o n s t r u c t i n gt o p o l o g ys h a p ew h i c h k e e p so r i g i n a ld a t ac o l l e c t i o n s ，t h i sr e d u c e st h en u m b e ro f6 r i g l n a ld a t ac o l l e c t i o n s a n de n l a r g e sa p p l i c a t i o nf i e l do f n e u r a ln e t w o r ks u r f a c er e c o n s t r u c t i o n ( 2 ) b a s i n go nr b f n n st h ea p p r o a c h i n ga n yn o l i n e a rf u n c t i o nb ya r b i t r a r y p r e c i s i o n ，p o w e r f u la n t i n o i s ea n dt h ec a p a b i l i t yo fr e p a i ra n d , s oo n ，a d o p t i n gr b f n n m o d e lt or e c o n s t r u c tf r e e - f o r ms u r f a c e w ec o n s t i t u t er b f n nm o d e lf i r i n gt os u r f a c e i i 首都师范大学硕士学位论文 基于点的造型与绘制技术的研究 r e c o n s t r u c t i o n w em a k et h e o r e t i c a la n a l y s i sa n dm a k ee x p e r i m e n to nt h en u r b s s u r f a c e ，t h er e s u l ti n d i c a t e st h a t t h i sm o d e ln o to n l yc a l le f f i c i e n t l ya p p r o a c ht h e s u r f a c ew h i c hi sn o tp e r f e c ta n d h a sn o i s e ，b u ta l s ot h es p e e do f l e a r n i n gi sv e r yq u i c k t h i s c a l l i m p r o v ee f f i c i e n c y a n d p r e c i s i o n o fd i r t y , i m p e r f e c t i o ns u r f a c e r e c o n s t r u c t i o n , a n dt h es m o o t ho f s u r f a c ew h i c hw eg e ti sw e l l i nt h i sp a p e rl a s ti n t r o d u c e st h et e c h n o l o g yo fp o i n t b a s e dr e n d e r i n g ，t h e m e t h o d so fp o i n t - b a s e dr e n d e r i n g , t h eq u e s t i o n so fp o i n t - b a s e dr e n d e r i n g ，a n dt h e m o r er e s e a r c hw a y o f p o i n t b a s e dr e n d e r i n g k e yw o r d s ：p o i n t - b a s e dr e n d e r i n g , p o i n t - b a s e dm o d e l i n g , k o h o n e nn e u r a ln e t w o r k ； b s p l i n es u r f a c e ，r a d i u sb a s i sf u n c t i o nn e u r a ln e t w o r k ，n o n - u n i f o r mr a t i o n a l b s p l i n e ( n u r b s ) 1 1 1 首都师范大学硕士学位论文 基于点的造型与绘制技术的研究 1 1 课题的研究背景 第一章绪论 在计算机图形学中，对图形的所有处理都要以图形基本信息的保存为前提。 只有在图形基本信息的基础上，我们才能对图形进行变化、缩放、显示等处理。 而这里的基本信息指的是几何信息和拓扑信息。传统方法，例如计算机图形学领 域内已经提出了很多成熟的曲面表示方法，包括多边形、样条曲面、隐式曲面以 及各种各样的混合表示方法，这些方法是利用一个顶点表和一个多边形表来分别 存储的。所有这些表示的目的在于能简便地生成不同形状的物体表面。多年来， 基于多边形尤其是三角面片一直受到高度重视。基于三角网格的绘制因其具有绘 制基元简单、表现力强以及良好的硬件支持等许多优点而成为当前交互式图形绘 制中最流行的方法。创建三维模型的过程中，各种各样的建模技术如隐式曲面、 n u r b s 曲面、细分曲面等的应用，使得模型中可以包含越来越复杂的形状。用以 表示这些复杂形状的高层次建模元素如曲面等在送往图形子系统进行绘制之前， 需要分解为三角面片。虽然使用三角面片作为显示元素看起来能满足描述能力和 计算负担之间的平衡要求，但是随着达到真实感场景绘制所需生成的物体模型复 杂度的不断提高，三角面片的数量也增加很快，正如a l v yr a ys m i t h 所说：“真 实就是8 0 0 ，0 0 0 个多边形” a l v y 9 9 。对大量三角面片的处理造成了带宽瓶颈和 过度的浮点计算量。 另一方面，近年来，使用物体的采样表示方法是目前计算机图形学领域一个 重要的趋势，一个例证就是三维扫描仪被大量用于生成物体的三维采样数据。三 维扫描仪同样面l 临如何处理所生成的大量数据的问题。传统的处理方法是根据采 样点生成三角面片网格进行绘制，而随着三维扫描技术的高速发展，扫描所得到 的网格点的数目达到了十亿的数量级 l e v o y 0 0 。由于传统的三角面片网格表示 不仅记录了点的信息，而且记录了点和点之间的连接关系，即边的信息，传统的 技术更多的关注于每个的边、点的放置，在每个点上耗费的工作相对过多。这就 使得现有的图形工作站无法实时显示这种规模的网格。而由于时间和空间的需求 限制，传统的网格简化方法和渐进显示方法对规模超过几百万的网格也已不实 用。 此外，随着近年来3 d 数码扫描仪的日益普及与应用，扫描获取的几何体的 细节以及外形更加丰富，迫切需要新的能有效表示、处理以及绘制超大规模、高 度复杂的几何模型的方法。 随着几何扫描仪应用的范围越来越广泛，相应的扫描实物模型的数量和复杂 首都师范大学硕士学位论文基于点的造型与绘制技术的研究 性也随着增长，稳健的和有效的几何处理方法引起了人们的兴趣。即使高保真度 扫描仪，所获得的3 d 模型也不可避免的带有噪声 b r a d l e y 9 3 ，因此需要对获取 的数据进行预处理以进行后序操作。 综上所述，随着应用规模的不断扩大以及新技术新设备的投入使用，图形学 的发展迫切需要解决以下问题： ( 1 ) 减少冗余，节约存储空间； ( 2 ) 直接绘制从三维扫描设备生成的无规则点云数据； ( 3 ) 高效率绘制高度复杂的物体模型和场景新的绘锚体系结构的需要； ( 4 ) 需要对获取的无规则点云数据进行预处理以进行后续操作。 1 2 课题的研究意义 基于以上几个因素的推动，基于点的表示及绘铝技术重新引起了人们的关 注。相对于传统的基于多边形的绘制体系，基于点的绘制具有以下优势： ( 1 ) 与基于网格的表示不同，基于点的表示方法很少冗余，能显著地节约 存储空问。 ( 2 ) 基于点的绘制技术( p o i n t b a s e dr e n d e r i n g ，p b r ) 就抛弃了传统的 三角面片表示方法，只记录点的信息，由这些点的信息直接重构出最终的图像， 从而为解决大量三维采样数据的快速绘制处理提供了一条新的途径。如图1 1 所 示三角面片模型和点模型的区别。 ( a ) 实物原模型( b ) 三角面片模型( c ) 点模型 图1 1 三角面片模型和点模型的区别 ( 3 ) 点能非常快速地绘制，无需进行复杂的多边形裁剪、扫描转换等中间 处理过程。所以绘制体系简单。基于点的绘制可避免传统多边形模型绘制时的大 量时间开销。正因为是点模型拓扑结构简单，因此能更方便地进行视点相关的表 面熏采样。只要根据硬件条件控制绘制点的数目，点绘制可以很容易地实现固定 的绘制速率。 ( 4 ) 点模型的拓扑简单。由于点与点之间相互独立，无拓扑关系以及邻接 首都师范大学硕士学位论文基于点的造型与绘制技术的研究 关系，因此拓扑结构简单。正因为点模型拓扑结构简单，因此能更方便地进行视 点相关的表面重采样。只要根据硬件条件控制绘制点的数目，点绘制可以很容易 地实现固定的绘制速率。 ( 5 ) 基于点的造型与绘制特别适合于表面高度复杂模型或具有复杂表面光 照细节模型，如雕塑与石刻，火焰、落叶、草地、树木等自然场景的模拟。 ( 6 ) 经过预处理的数据点，更加准确的逼近原始模型，并且为后续操作奠 定基础。 ( 7 ) 基于点的绘制能很方便地与传统的几何模型( 多边形模型、样条面片 模型等) 混合绘制。 ( 8 ) 与基于图像的表示不同，基于点的表示方法很少冗余，能显著地节约 存储空间。由于点与点相互独立，无拓扑关心以及邻接关系，也无需存储多边形 网格表。 现在的图形硬件无一傍j 外地支持直接点绘制，另外还有非常重要的一点，由 于点的独立性，基于点的绘制允许高度的并行处理。 综上所述，点离散地表示几何而无需存储任何拓扑信息。因此，点云简化了 实体表示方法而只保留最重要的信息，尽管无拓扑使得数据结构变得非常简单， 它同时会给图形处理带来很大的困难与挑战。 基于点的造型和基于点的绘制就是在点的基础上进行造型和绘制以及其他 的一些图形学上的处理。早在8 0 年代，基于点的绘制就在图形学中提出了。但 是一直发展很慢，没有得到广大图形学学者的注意和重视。现在，在数据量的急 剧增大和对网络传输要求越来越高的情况下。基于点的造型和基于点的绘制在图 形学中成为一个新的研究热点。 1 3 国内外研究现状 在计算机图形学的研究中，使用点作为图形绘制元素已经有很长的历史了。 早在1 9 7 4 年，c a t m u l l 注意至4 任何几何细分的极限就是点 c a t m u l l 7 4 。不幸的 是点作为基本图形元素在很长一段时间内不受重视，尽管很多系统都将其集成到 应用程序界面中。 随后在1 9 8 3 年，r e e v e s 提出在计算机图形绘制时用3 d 离散采样点粒 子作为基本绘制元素 r e e v e s 8 3 s m it h 8 4 r e e v e s 8 5 。一个粒子是三维欧 氏空间内的一个点，附属一些如颜色、密度、光照反射系数等附加信息。粒子系 统的最大的优点在于简便快捷的绘制，将每个粒子投影到屏幕上，利用z - b u f f e r 消隐，并用粒子的颜色给相应象素着色。粒子系统主要应用于一些用传统造型方 法很难表示和绘制的自然场景，如火焰与爆炸场面，流水与瀑布。点被用来绘制 首都师范大学硕士学位论文基于点的造型与绘制技术的研究 几何难以描述的“软”物体，如烟、云、尘、火、水、树等。 基于点的绘制技术这一提法最初是由l e v o y 和w h i t t e d 在1 9 8 5 年提出的 l e v o y 8 5 ，他们分析出复杂物体用连续的扫描线方法绘制的缺陷，弗指出点虽 然简单却足以表示物体：只要三维点云足够致密，将一个个点投影到屏幕上后仍 然能得到逼真的显示效果。在该算法中，l e v o y 讨论了基于点的绘制技术中的一 些基本问题。例如，如何将三维模型转换为点模型，如何根据点进行物体表面的 重建等等。然而，他们提出的方法并不是很纯粹的基于点的绘制，数据量是通过 多边形来统计的，说明他们的系统中还是有多边形。但是该搜术直到最近才逐渐 被人们所关注。 随着基于点的绘制技术研究的逐渐深入，许多学者提出了相应的基于点的绘 制算法，相关的文献也逐渐增多。 1 9 9 2 年s z e l i s k i 与t o n n e s o n 在r e y n o l d s 的工作基础上改进了粒子系统 r e y n o l d s 8 7 ，给原本各向同性的粒子确定了一个法向，并将这个有向粒子系统 应用于模型的表面造型以及交互编辑。每个有向粒子是一个具有局部构架的点， 相互间通过远距离引力和近距离斥力发生关联。在绘制有向粒子时他们并没有使 用基于点的绘制技术，而是用椭圆来显示粒子，最终实体也是三角化的曲面。这 种有向粒子被他们首先命名为“s u r f e l s ” s z e l i s k i 9 2 。 1 9 9 4 年，w i t k i n 与h e c k b e r t 将有向粒子应用于隐式曲面的采样以及交互编 辑 w i t k i n 9 4 3 ，并采用同样的绘制方法 s z e l i s k i 9 2 来显示有向粒子。 基于图像的绘制技术( i m a g e b a s e dr e n d e r f n g ，i b r ) ，是指绘制时间只与 输入及输出图像像素的数目成比例，与场景的复杂度无关。该技术不使用传统的 几何元素来建立模型，而是使用一组采样图像来描述虚拟环境的模型。受此启发， 1 9 9 8 年g r o s s m a n 与d a l l y 重新开展了点绘制方面的研究工作 g r o s s m a n 9 8 1 g r o s s m a n 9 8 2 ，其目标是在避免昂贵图形硬件条件下实时绘制 复杂物体。 2 0 0 0 年的s i g g r a p h 大会上展示的q s p l a t 技术 r u s i n k i e w i c z 0 0 巧妙地利用 点模型的灵活性，建立了一种层次包围球的结构。与传统层次结构的最大的不同 在于，每个结点自身可以被看作是在一定分辨率下的一个表面重采样点，而这个 点代表了其局部区域所有采样点的信息。当不影响绘制精度，或是绘制实时性更 为重要的时候，可通过绘制该点米代替对它下属的所有子结点的绘制，从而提高 绘制效率。此外，q s p l a t 可通过从上至下遍历层次树的方式对各结点所代表的 曲面局部区域进行视域裁剪和背面剔除，如果上层结点被确定位于视域外或背向 视点，则无需对子树中的每一个结点分别进行判断。然而，由于绘制算法基于层 次结构的遍历，因此无法利用可编程图形硬件基于流的工作模式进行加速。尽管 4 首都师范大学硕士学位论文 基于点的造型与绘制技术的研究 该方法采用了相当大的压缩率，但是每个模型的所需的数据文件仍然很大，尤其 是当数据通过网络远程调入时，则很可能会出现数据传输跟不上显示速度的情 况。 2 0 0 1 年，r u s i n k i e w i c z 等人提出s t r e a m i n gq s p l a t 的概念 r u s i n k i e w i c z 0 1 ，将模型序列化为线性结构，从而能在网络中快速传输点模型。 由于其绘制方法仍需要通过层次树遍历来完成，因此只能由软件来实现。 2 0 0 3 年，s t a m n i n g e r 研究小组 d a c h s b a c h e r 0 3 提出了一种将点模型的层次 结构序列化为一个线性数组的方法，并在此基础上将绘制算法由层次树的遍历转 化为线性数组的遍历，从而巧妙地实现了q s p l a t 的g p u 硬件力速，极大地提高 了绘制效率。他们报告的效率为每秒绘制约5 千万个点。 以上算法都着眼于绘制的效率，而不考虑绘制的质量。它们在绘制的时候把 每个点用一个不透明的正方形衷示，能用g l _ p o i n t 简单实现。这类算法虽然高 效，但常会产生严重的图形走样 z w i c k e r o l - 1 。 基于点的绘制中的另一部分重要工作着眼于提高点模型绘制的质量。 2 0 0 0 年，p f i s t e r 等人率先提出用点面元( s u r f e d 来代表一个采样点 p f i s t e r 0 0 。这个点被表示为位于点切向上的一个圆盘，各点的圆盘相互重叠 并形成紧密( w a t e r t i g h t ) 的物体表面。在绘制时，首先通过可见性预处理去 除被遮挡的点，然后将可见点投影到屏幕空间，并在屏幕空间进行二维图像重建 而得到光滑图像。由于基于点绘制主要针对大数据量的单个模型进行快速显示， 该方法遮挡选择的效率提高并不明显。 z w i c k e r 等人结合了l e v o y 等人的想法 l e v o y 8 5 以及 h e c k b e r t 8 9 的纹理映 射中的反走样理论，提出了e w as u r f a c es p l a t t i n g 技术 z w i c k e r o l - 1 ，将e w a 技术应用于不规则空间采样点的绘制。e w a ( e l l i p s ew e i g h ta v e r a g e ，椭圆加权 平均滤波) s u r f a c es p l a t t i n g 是一种高质量的物体空间的绘制技术，从信号处理 角度考虑各向异性的纹理过滤、消隐、边界反走样和象素精度的a b u f f e r 处理。 e w as p l a t t i n g 技术也可以应用于体绘制。然而，该方法纯粹基于软件执行，当 显示高度复杂模型时计算量非常大，因为在当前硬件基础上获取s p l a t 速率低。 2 0 0 3 年，k o b b e l t 等人提出了一种基于高斯滤波的点模型图形硬件加速方法 k o b b e l t 0 3 ，取得了更高的效率。他们的算法在绘制效果上稍逊e w a ，并且没 有考虑点模型的层次结构，从而缺乏处理大规模的点模型场景的手段。 纯粹用点云来构建场景有其应用缺陷：首先，点云的密集分布造成了大量的 数据冗余，极大地消耗了存储、传输以及绘制资源；其次，在当前的几何绘制引 擎中，点云在绘制时最终采用三角形或圆面表示，而拓扑关系的缺失使得在视点 靠近时无法保证无空洞的绘制效果。因此许多研究者采用多边形与点混合表示场 首都师范大学硕士学位论文基于点的造型与绘制技术的研究 景 c o h e n 0 1 ，这种混合表示方式结合了点与多边形两种表示方式的优点：当绘 制元素在屏幕上投影区域很小时用点绘常5 效率商一些，反过来投影区域较大时用 多边形绘制效果更好。 动态重采样绘制是一类与视点相关的绘制算法，点云的重采样在绘锚时进 行，没有预处理过程。w a n d 等人使用三角面片集的随机采样点来达到交互显示 的效果 w a n d 0 1 ；s t a m m i n g e r 与d r e t t a k i s 使用固定采样模式从复杂场景中动 态采样 s t a m i n g e r 0 1 。同时，他们还提出一套可用硬件加速点绘制的l o d ( l e v e l o f g e t a il 。细节层次) 援泰 k a l a i s h 与v a r s h n e y 使用d i f f e r e n t i a lp o i n t ( d p ，微分点) 作为新的绘制 元素 k a l a i a h 0 1 。与传统的采样点不同，每个d p 采样点保留了局部微分几何信 息，用以高效高质量地刻画其局部邻域。d p 模型比一般的点模型的采样点要少， 因此非常节省空间，但又不影响绘制效果。d p 可以从n u r b s 曲面上采样得到， 也可以从任何微分曲面上采样得到。它盼一个限制是只能表达光滑表面。 c a r r 等人采用多重调和的径向基函数( r b f s ) 从非均匀分布点云中重构出光 滑的流形表面，并将其应用于c s g 框架来实现一种新的造型方法 c a r r 0 1 。 l i n s e n 在其报告中提出一种点模型表面的多分辨率造型框架 l i n s e n 0 1 。 他提出了简化采样算子、加密采样算子、磨光算子与点模型的多分辨率分解表示， 并拓展了c s g 表示方法使之适用于点模型。 p a u l y 和g r o s s 提出了一种针对点采样曲面的傅立叶变化以及频谱分析框架 p a u l y 0 1 。他们将模型分解为近似为平面的一系列小块，在每个小块上做傅立 叶变换以及频谱分析，然后将各个小块拼接起来实现对点采样曲面的处理。 p a u l y 等人比较了几种不同的点模型简化算法，包括区域增量聚类算法、层 次聚类算法、迭代简化算法以及粒子模拟算法来得到与原模型相近的简化点模 型。他们还提出了一种简化模型的误差计量方法 p a u l y 0 2 - 1 。同年p a u l y 等设 计了一个多分辨率点模型造型框架 p a u l y 0 2 2 。这个框架集成了当时不少多分 辨率造型理念如几何光顺、简化以及偏移量计算，包括了 l i n s e n 0 1 的一些特色。 动态重采样是其一大特点，可保证编辑时点模型表面具有足够的采样密度。 z w i c k e r 等人的编辑系统p o i n t s h o p3 d z w i c k e r 0 2 - 1 允许交互编辑显示表 面为采样点的几何体。结合传统的2 d 象素编辑方法，p o i n t s h o p3 d 能支持多种 变形、编辑技术如清理、纹理映射、雕刻、过滤以及重采样等，其最大的特性是 点云模型集成了参数化表示。 浙江大学的彭群生、华炜、杨学辉等人也提出一种基于点的绘制方法 p e n 9 0 1 。该方法在每个采样点处用一个圆面来逼近物体的表面，绘制时直接将 圆进行投影得到一个个椭圆，不是采用常见的s p l a t t i n g 方法，而是提出一种 首都师范大学硕士学位论文 基于点的造型与绘制技术的研究 d e l t a - z - b u f f e r 的方法来进行邻近点的颜色融合。 缪永伟等人，利用调和映射的平面和球面中值性质，提出了确定点模型曲面 参数化映射中有关权因子的新方法，设计了能够达到内在变形较小的相应参数化 方法 缪永伟0 4 。 2 0 0 5 年，浙江大学大学得张龙提出了一个针对大规模点模型得实时高质量 绘制算法 张龙0 5 ，该算法采用距离相关得自适应绘制策略，在不损失绘制质 量的前提下简化了计算。此外为了减少存储空间的消耗，该文还提出了一种面向 保留模式图形硬件加速的点模型压缩和解压缩算法。 1 4 课题支持及研究内容 1 4 1 课题支持 本课题在北京市教委2 0 0 4 项目( 1 0 i 2 0 0 4 1 0 0 2 8 0 1 3 ) ：“空闻蓝面造型算法与 应用技术研究”基础上来进行相关研究。 1 4 2 课题的研究内容 本课题不讨论如何从实物扫描获取点模型，也不讨论如何将其它方法表示的 模型转化成点模型。处理和绘制时用到的点模型是从原始扫描获得或者从其它方 法表示的模型转化的数据。本课题的主要内容： ( 1 ) 基于点的曲面表示 在计算机图形学领域内，自由曲面造型一直是研究者关注的核心问题之一。 点模型的表示首先是一种表面表示方法，基于点的几何表示的目标是从离散点集 中构造出连续的表面。h o p p e 将此问题一般化并提出了一个统一性的陈述 【h o p p e 9 2 。 表面重构的目标是用一个采样集p 以及采样处理的一些信息( 如误差大小6 和采样密度p ) 来确定一个近似表示未知表面m 的表面m 。 基于点的表示的原始输入为点云。每个采样点上可以附加多种属性，如色彩、 材料属性、法向和表面曲率等。针对输入点模型的表示形式，众多研究者们提出 了不同的输出方案。 根据在重构时所采用的是参数曲面还是隐式曲面来分，基于点的曲面重构可 以分为：参数曲面重构和隐式曲面重构。本课题主要利用现有基于三角形曲面重 构的方法，进行基于点的曲面重构方面的研究。 ( 2 ) 基于k o h o n e n 神经网络的无规则散乱数据点的曲面重构研究 在逆向工程中，型值点数据具有大规模、散乱的特点。此外，在曲面重构问 题中，已知的都是无规则散乱数据点，因此曲面的次数、节点值和控制点都是未 首都师范大学硕士学位论文基于点的造型与绘制技术的研究 知的。 基于上述的问题，本课题中主要采用神经网络方法来对散乱数据点进行拟 合。通过迭代方法k o h o n e n 神经网络可以产生对原曲面不同逼近精度的b 样条曲 面。通过该方法得到的曲面可以对原始的散乱数据点集逼近，可以作为后继曲面 重构的初始曲面，而且还可以对密集散乱数据点自组织压缩，并构建保持原数据 点集的拓扑形状，这样降低原始数据点的数量，扩大了神经网络曲面重构方法的 应用领域。 ( 3 ) 基于径向基函数神经罔终无援则教魏数据点的磷缝瑷 随着几何扫描仪应用的范围越来越广泛，相应的扫描实物模型的数量和复杂 性也随着增长，稳健的和有效的几何处理方法引起了人们的兴趣。即使高保真度 扫描仪，所获得的3 d 模型也不可避免的带有噪声 b r a d l e y 9 3 ，因此需要对获取 的数据进行预处理以进行后序操作。 本课题主要采用r b f 神经网络强大的抗噪、修复能力性质通过自身的学习来 对输入的坏点自动地剔除和修复。 ( 4 ) 基于点的绘制 本课题中主要介绍了基于点绘制的一些主流技术及基于点的绘制技术的进 一步研究方向。 1 5 基于点技术的基本内容 基于点的图形学分成三个主要部分：获取、处理以及绘制，如图1 2 所示 ( 1 ) 获取：点模型的主要来源为3 d 扫描仪生成的原始数据，包括深度相机 生成的深度图( r i ) 与激光三维扫描仪或者接触式机械探头等设备得到的大量三 维空间点位置。三维点云再配合光学照片可以得到带颜色或者纹理色彩的三维实 物模型。点模型的另外一个来源是现存的几何模型。所有几何模型( 多边形网格 模型、样条面片模型、隐式曲面、g s g 树和粒子系统等) 均能方便地转化成点模 型，不同的采样精度能得到不同的分辨率的点模型。 ( 2 ) 处理：点模型的处理分前期处理( o b j e c tr e p r e s e n t a t i o n ) 以及后期 处理( o b j e c tm o d e l i n g ) 。扫描得到的原始数据具有噪声、拼接错位、空洞、不 确定性和过度采样的问题，需要经过前期处理才能使用。前期处理的目标是从原 始点云中构造出一个连续的表面模型，后期处理则在前期处理的结果上再作进一 步的造型处理如重采样、磨光、多分辨率简化、编辑、变形、布尔运算等操作， 得到各种各样的点模型。对点模型的数字几何处理( d g p ) 也在后期处理阶段进 行，其目标是在点模型的流行表面领域内拓展基本的信号处理概念。 ( 3 ) 绘制：点绘制的目标是在屏幕上输出一系列的点并构成连续的表面。 首都师范大学硕士学位论文基于点的造型与绘制技术的研究 从三维离散点采样直接重建出三维空间的连续信号，对连续信号进行滤波后重采 样并投影至二维屏幕进行光照计算。由于点模型没有拓扑关系，利于重新采样和 投影计算。因此点绘制的可以加快大规模数据构成场景的绘制过程。点绘制同样 需要解决面绘制所含有的基础问题，如关照计算、可见性计算、阴影计算、纹理 映射、反走样等。基于点的绘制技术的一个特点是离散点集映射到屏幕后需要在 图像空间内作图像重构处理来填补空洞并重构物体表面。 图12 基于点表示实体的获取、处理及绘制全流程图 杨振羽0 4 首都师范大学硕士学位论文基于点的造型与绘制技术的研究 1 6 论文的组织结构 本文的第一部分是绪论部分，主要介绍一下该课题的背景、国内外研究现状 以及课题研究的目的、意义。第二章介绍了基于点的曲面表示的局部特性以及相 关技术。第三章概述了基于点的造型处理技术和神经网络的相关知识。第四章主 要探讨了三维散乱数据点的自由曲面重构方法。提出了基于k o h o n e n 神经网络来 对散乱数据点进行拟合的方法。第五章主要探讨了无规则散乱数据点的预处理的 方法。提出将径向基函数神经网络应用于带有嗓声数据敖乱数据点自由曲面的重 构。第六章主要介绍了基于点的绘制相关技术。第七章是对全文的总结及以后工 作的展望。 0 首都师范大学硕士学位论文 基于点的造型与绘制技术的研究 第二章基于点的曲面表示 基于点的曲面表示主要目的是对流行曲面的处理，该流行曲面是由有限采样 点来表示的。目标是直接对点云进行相关操作，在需要时计算( 局部) 曲面逼近。 当设计新的不依赖于内在曲面表示的全局连接结构时，点采样曲面提供了更为灵 活性的方法。 输出数据为点云p = p 点钏川，且p ，1 r 3 。可以通过一些3 d 扫描设备如， 激光深度扫描仪来产生采样点，或者通过对特定曲面表示如隐式曲面采样处理来 产生采样点。任意属性如颜色、材料特性等都可以支配给每个采样点，但是，一 般的对于定义曲面的额外信息如法线向量，曲率等不是已知的。 本章介绍用于定义更为复杂处理算法的最基本技术。详细地描述了用于估计 局部曲面属性如法线向量、曲率的方法。这些计算是基于满足某些领域关系的p 的子集所定义的采样点的领域。 2 1 局部曲面分析 对于本文中所提出的算法来说内含在3 维空间中的2 维流行曲面的概念是非 常重要的。下面为流行曲面的定义 m p 7 6 。 定义2 1 ：子集s i r 3 为2 维流行曲面，如果对于每个x s ，在侬3 中存在 领域v 和开集u i r 2 到矿n s c i r 3 上的映射：x ：u 呻v n s ，因此： x 是微分的，即如果对于，v ) u 来说，x ( u ，v ) = ( x ( u ，v ) ，y ( u ，v ) ，z ( “，v ) ) ， 那么函数j ，y ，z 具有u 中所有阶的连续偏导数。 x 是同拓扑的，即存在转置x 。1 ：v n s 呻u 并且该转置连续。 对于u e u 来说，微分d x 。i r 2 斗1 r 3 是一对一的。 需要注意的是曲面的定义是基于局部邻域的。根据邻域来定义曲面内在的特 性，如切面、高斯曲率。 2 1 1 局部邻域 在离散情况下，可以通过采样点的空间关系来定义局部邻域。已知点p e p ， 定义局部邻域作为索引集n ，即对于每个点p 。，i n ，满足特定邻域条件。该邻 域条件应该以方法：n 。的点应该充分地代表围绕点p 的小面积、局部曲面片来 进行设置。对于下面要描述计算方法来说，局部领域仅仅依赖于空问采样点的几 何位置，而不是某些与点云有关的额外连接结构，这种情形是非常重要的。特别 地，点p 的邻域应该独立于它邻域点p ，i n ，的邻域。 ( 1 ) k 一最近邻 首都师范丈学硕士学位论文基于点的造型与绘制技术的研究 k 一最近邻：的定义是基于按照p 中所有点到点的欧式距离的次序。丌代表 排列，那么憎r t ( 1 ) - p i | 0 并且0 p n ( j ) 一p i 图i p n f + 1 ) 一p i 1 ，l 一1 】。 采样点p 的k 一最近邻索引集：为： 畔= 1 ( 1 ) ，y i ( 2 ) ，f i ( 七) ) ( 2 1 ) 索引集啡定义了一个中心为p 半径为= | l p 附) 一p | f 的球体s ；，因此，如 果i e 孵，那么p j 位于s ；之内。 下面两个邻域关系是基于k 一最近邻到位于点p 处的切平面露上的映射。已 知；，吼代表p ，；到耳上的映射。 ( 2 ) 二元空间划分邻域( b s p 邻域)