（应用数学专业论文）基于点表示几何体的造型技术.pdf

浙江大学硕士学位论文 摘要 近年来，以点作为造型与绘制的基本元素的方法，在计算机图形学领域内受 到研究者越来越多的关注。本文回顾了基于点元表示的图形学的发展历史，并提 出了两个在点造型方面的新算法。 针对一般点云模型，本文提出了一个新的交互式布尔运算算法。在实施布尔 运算时，利用自适应三色八叉树结构来加速内外测试。对于局部采样密度不一致 的相交区域或曲率太大容易导致较大求交误差的地方，实行了自适应细分加密采 样。最后重采样相交的部分获得精确的结果。此算法适用于一般的实测点云数据， 包括含有少量噪声的点模型、非均匀采样的点模型以及不同分辨率的点模型之问 的布尔运算。 此外本文还从统计的观点出发，提出了一个基于邻域重心约束的光顺算法， 通过极小化邻域重心约束的局部邻域目标函数达到局部光顺的目的。此方法有效 地克服了拉普拉斯算子所造成的过度收缩与聚集现象。实验表明此方法不仅计算 稳定、速度快，而且简便易用。 最后，上述方法都被集成到一个基于点表示的交互造型系统中。 关键词：基于点的造型，布尔运算，光顺。 浙江大学硕士学位论文 a b s t r a c t r e c e n t l y , m o d e l i n ga n dr e n d e r i n gu s i n gp o i n t s b a s i ca n de f f i c i e n tp r i m i t i v e s h a v eb e e np a i d m u c ha t t e n t i o ni nc o m p u t o rg r a p h i c sc o m m u n i t y t h i st h e s i sr e v i e w st h eh i s t o r yo fp o i n tb a s e d g r a p h i c sa n dp r a s e n t st w on o wa l g o r i t h m so i ls h 印em o d e l i n go f p o i n t - s a m p l e dg e o m e t r y an o v e l a l g o r i t h m i s p r o p o s e df o r j l r o r a o f i v eb o o l e a no p e r a t i o n sb c t w ng e n e r a l p o i n t - s a m p l e dg e o m s 。a y t h eb o o l e a no p e r a t i o n sa g oa c c o m p l i s h e db ym e a a so fa ne d a p t i v e t h r e e - c o l o ro c t r e ea c c e l e r a t e dm s i d a l o u t s i d ct e s t i n g f o rt h ei n t e r s t i o nr e g i w i 也d j 瑶艚砒l o c a l s a m p l i n g d e n s i t i e s 0 1 l a r g ec u r v a t u r e s ，a d d i t i o n a la d a p t i v es u p e r - s a m p l i n gi sa p p l i e d t h e i n t e r s e c t i o np o i n t sa r cf u r t h e rr e s a m p l e df o ra o c u r a t er e s u l t s t h i sa l g o r i t h mi ss u i t a b l ef o rg e n e r a l p o i n t - s a m p l e dg e o m e t l yw h i c hm i g h tb en o i s y , n o n - u n i f o r ms a m p l e d i nd i f f e r a n ts a m p l i n g r e s o l u t i o n s s e c o n d l y , ae e n l r o i dc o n s t r a i n e df a i r i n ga i g o r i t h mi sp r e s e n t e df o rp o i n t - s a m p l e dg e o m e t r y b yo p t i m i z i n ga l o c a l f l m c f i o n b a s e d m l t h e c o n t r o i dc o n s t r a i n t s o f n 商g h b o r h o n d , l o c a ls m o o t h i n g i sa c h i e v e d t h i sm e t h o do v e r c o m e st h ew o b l e m so f c a l r e m os h r i n l 讯g ea n de x t r e m ec o n v e r g e n c e a r i s c mf l o ml a p l a c i a ns m o o t h i n go p e r a t o r o u re x p e r i m e n t s 呻t h a ti ti ss t a b l e , f a s ta n d e a s y 。t o - u s c f i i l a l l y ，a ni n t o r a o t i v es y s t e mf o rp o i n t - b a s e ds h a p em o d e l i n gi si m p l e m e n t e di n t e g r a t i n go u r n e wa l g o r i t h m s k e yw o r d s ：p o i n tb a s e dm o d a t i n g ，b o o l e a no p e r a t i o n ，f a i r i n g 4 浙江大学硕士学位论文 a p i c s g d g p d i d o f d p e 、砚 g b r ；m m r 田r l d c l d l s l o d 匝s n b h d n u r b s p b m p b r p c a r b f s r l s p g 缩写表 a p p l i c a t i o np r o g r a m m i n g i n t e r f a c e c o n s t r u c t i v es o f i dg e o m e t r y d i g i t a lg e o m e t r yp r o c e s s i n g d e p t hi m a g e d e p t h o f f i e i d d i f f e r e n t i a lp o i n t e l l i p t i c a w e i g h t e da v e r a g e g e o m e t r yb a s e dr e n d e r i n g i m a g eb a s e dm o d e l i n g i m a g eb a s e dm o d e l i n ga n dr e n d e r i n g i m a g eb a s e dr e n d e r i n g l a y e r e dd e p t hc u b e l a y e r e dd e p t hi m a g e s l e v e lo f d e t a i l m o v i n gl e a s ts q u a r e n e i g h b o r h o o d n o n u n i f o r mr a t i o n a lb - s p l i n e s p o i n tb a s e dm o d e l i n g p o i n tb a s e dr e n d e r i n g p r i n c i p a lc o m p o n e n ta n a l y s i s r a d i a lb a s i sf u n c t i o n s r a n g ei m a g e s t a t i s t i c a lp o i n tg e o m e t r y 7 应用程序界面 构造实体几何 数字几何处理 深度图象 场景深度 微分点 椭圆加权平均 基于几何的绘制 基于图象的造型 基于图象的造型与绘制 基于图象的绘制 层次深度立方体 层次深度图象 细节层次 移动最小二乘 邻域 非均匀有理b 样条 基于点的造型 基于点的绘制 主元分析 径向基函数 深度图象 统计点几何 浙江大学硕士学位论文 第一章绪论 本文主要研究基于点表示的三维实体的造型技术。本章将回顾基于点的实体 的表示、处理以及绘制技术的历史起源与发展现状。 1 1 基本概念 点云( p o i n tc l o u d ) ： 密集三维点集，或称为密集离散点集。 基于点的造型： 基于点云的表面表示、处理及编辑。 基于点的绘制： 计算机绘制基于点表示实体的技术。 点元( s u r f e l s ) = 一个带形状因子与光照属性的0 维刀元组( a z e r od i m e n s i o n a ln - t u p l e ) ，用来局 部近似物体表面 p f i s t e r o o 。点元映射到屏幕后在图象空间内重构物体表面。 1 2 促动因素 在计算机图形学领域内已经提出了很多成熟的曲面表示方法，包括多边形、 样条睹面、隐式曲面以及各种各样的混合表示方法。所有这些表示的目的在于能 简便地生成不同形状的物体表面。多年来，基于多边形，三角面片的绘制技术一 直受到高度重视。其他曲面表示，诸如隐式曲面、n u r b s 、子分曲面等，最终 都被转化为三角形表示以便采用常规图形绘制硬件进行绘制。图形硬件的高速发 展以及对几何表面三角化算法的深入研究进一步巩固了三角网格在图形绘制以 及造型中的地位 g r o s s 0 1 。 然而，随着研究以及应用的不断深入，人们对场景绘制的真实感与速度要求 8 浙江大学硕士学位论文 越来越高，几何场景变得越来越复杂。特别是在虚拟现实中，为达到逼真的显示 效果，用于构造场景的三角形数目往往数以亿计。尽管硬件性能不断发展，如 n v i d i a 公司的f x 5 8 0 0 、f x 5 9 0 0 ，a t ! 公司的r a d e o n 9 7 0 0p r o 、r a d e o n 9 8 0 0p r o 等 显卡已经达到每秒上亿个三角形的绘制速率，但仍然不能满足场景实时绘制的需 求。海量数据场景、更高的真实感实时动态交互仍然是当今图形技术所面幅的巨 大挑战。 从造型的角度上看，基于几何面片的场景造型方法往往需用大量的多边形来 描述场景细节，不仅造型工作量巨大，而且给实时绘制带来极大的阻难。事实上， 处理大量微小的三角面片已经成为高性能图形绘制的瓶颈。 学术界已经针对性地提出了多种不同的解决方案试图解决这个瓶颈问题，但 这些方案都不能彻底解决造型与绘制方面所面临的压力： 众多研究者采用场景表面的多分辨率模型c l o d ) 来解决计算负担过重的问题 ( h o p p e 9 7 】【l u e b k e 9 7 】【c o h e n 9 8 等) 。多分辨率模型利用人类视觉的特性，在视 觉效果等同的条件下对复杂场景作多层次的简化以降低场景绘制的计算量。多分 辨率模型通常基于三角蟊片的表示方式，在简化计算时常涉及几何误差估计、表 面重采样以及三角网格拓扑一致性维护等一系列复杂的问题。这种方法不仅预处 理时计算量巨大，在显示时也难以实现不同分辨率之间的平滑过渡。 快速消隐类算法( g - r e e n e 9 3 z h a n 9 9 7 等) 通过剔除场景中的不可见景物来减 少画面绘制的计算量，但这类算法对遮挡率较高的场景较为有效，且算法效率与 场景的复杂度有关。 c a n n u l l 引入纹理映射 c a t m u l l 7 4 增加物体表面的视觉复杂度。纹理映射后 的多边形可以承载更多的细节，因此用较少数目的三角面片就可以达到相似的显 示效果，这可以在一定程度上减轻绘制方面的压力。然而基于硬件的纹理映射目 前只适用于多边形几何体。表现一幅复杂的场景往往需要很多纹理，占用较多的 纹理内存和传输带宽。许多自然场景如火焰、烟雾等，用纹理映射尚难以达到逼 真的显示效果。 基于图象的造型与绘制技术( i b m r ) 被普遍应用于虚拟现实中，具有绘制速度 快、真实感强的优点。基于图象的绘制( i b r ) 并不依赖于场景复杂性，而仅仅跟 浙江大学硕士学位论文 象索分辨率有关。但 b r 技术与视点相关，需要存储大量的图象才能合成新的图 象。高度的冗余消耗了大量宝贵的存储空间和传输带宽。 从空间存储的角度看，基于多边形表示的实体的基本信息包括几何信息与拓 扑信息，通常采用一个顶点表和一个三角形表来分别存储，三角形数目是顶点数 目的两倍。绘制时不仅要传输顶点表，而且还要传输三角形表。在对基于多边形 表示的大规模场景绘制时，三角形表不但占用了大量的存储空间，而且占用了大 量的传输带宽。场景复杂度越高，效率问题就越突出。 再者，从绘制体系的角度看，场景规模的不断增大对图形绘制体系也提出了 新的要求。传统的多边形绘制采用扫描线算法，扫描线算法充分利用了扫描线的 连贯性，采用增量方式实现快速绘制，且只需要存储顶点的基本信息即可。在绘 制简单实体时这种算法效率非常高，而且非常适合硬件实现。但实体复杂度很高 的时候，这类算法无明显的优势。l e v o y 在研究复杂度与连贯性的关系时 l e v o y 8 5 发现随着多边形个数的增加，扫描线算法的绘制效率快速下降。当多边形个数超 过象素个数时，这种连贯性的优势几乎丧失殆尽。 图llt h ed i g i t a lm i c h e l a n g e | op r o j a c t p i c t u = r e s l l 左图：3 d 实物扫描示意圈；右图：计算机 绘制的米开朗基罗的大卫雕像。整个工程动用了2 2 人和4 8 0 个扫描仪，完成1 , 0 8 0 人时的 1 _ 程量，最终结果为2 g 多边形及7 , 0 0 0 图片的模型，总数据量为3 2 g 。主扫描仪高75 米， 重达8 0 0 千克，最高扫描精度为0 2 9 r a m 。 l o 浙江大学硕士学位论文 此外，随着近年来3 d 数码扫描仪的日益普及与应用( 见图11 ) ，扫描获取 的几何体的细节以及外形更加丰富，迫切需要新的能有效表示、处理以及绘制超 大规模、高度复杂的几何模型的方法。3 d 扫描仪输出目标物体的大量密集采样 点，这些点相互之间没有任何连接关系。传统方法需将扫描获得的离散采样点转 化成多边形模型再作进一步的处理及绘制，但随着采样数据规模的不断扩大，多 边形模型转化或重构的方法变得越来越低效，多边形表示方法的局限性交得更为 明显。 综上所述，随着应用规模的不断扩大以及新技术新设备的投入使用，图形学 的发展迫切需要解决以下问题： 高效率绘制高度复杂的物体及场景； 减少冗余，节约存储空间； 新的绘制体系结构的需求； 直接绘制由3 d 扫描设备生成密集点云。 基于以上几个因素的推动，基于点的表示及绘制技术重新引起了人们的关 注。相对于传统的基于多边形的绘制体系，基于点的绘制具有以下优势： 基于点的绘制可避免传统多边形模型绘制时的大量时间开销。点能非常快速 地绘制，无需进行复杂的多边形裁剪、扫描转换等中间处理过程。正因为点模型 拓扑结构简单，因此能更方便地进行视点相关的表面重采样。只要根据硬件条件 控制绘制点的数目，点绘制可以很容易地实现固定的绘制速率。 基于二点的造型与绘制特别适合于袭示表面几何高度复杂或具有复杂表面光 照细节的模型，如雕塑与石刻，也能用于火焰、流云、落叶、草地、树木等自然 场景的模拟，点作为基本元素能很好地表示过程几何 e b e r t 9 s 。此外基于点的绘 制能很方便地与传统的几何模型( 多边形模型、样条面片模型等) 混合绘制。 与基于图象的表示不同，基于点的表示方法很少冗余，能显著地节约存储空 问。由予点之间相互独立，无拓扑关系以及邻接关系，也无需存储多边形网格表。 现在的图形硬件无一例外地支持直接点绘制，可以利用多边形硬件加速点模 新江大学硕士学位论文 型绘制【r e n 0 2 】并达到理想的绘制效果。另外还有非常重要的一点，由于表示模 型的点的独立性，基于点的绘制允许高度的并行处理。 概括地讲，点离散地表示几何而无需存储任何拓扑信息。因此，点云简化了 实体表示方法而只保留最重要的信息，尽管无拓扑使得数据结构变得非常简单， 它同时会给图形处理带来很大的困难与挑战。高性能绘制、光影计算、各向异性 的纹理映射以及迸一步的信号处理将是其最大的特点 g r o s s 0 1 。 1 3 历史回顾 本节我们将回顾基于点的图形学的历史发展，以时间顺序排列： 点作为基本的图形绘制元素已经有很长的历史了。早在1 9 7 4 年， c a t m u l l c a t m u l l 7 4 注意到任何几何剖分最终都将显示为一个个离散点。不幸的是 点作为基本图形元素在很长一段时间内不受重视，尽管很多系统都将其集成到应 用程序界面( a p i ) 中。 随后r e e v e s 在1 9 8 3 年提出在计算机图形绘制时用3 d 离散采样点一粒子 r e e v e s 8 3 一作为基本绘制元素。一个粒子是三维欧氏空间内的一个点，附属一 些如颜色、密度、光照反射系数等附加信息。粒子系统的最大的优点在于筒便快 捷的绘制：将每个粒子投影到屏幕上，利用z - b u f f e r 消隐，并用粒子的颜色给相 应象素着色。粒子系统主要应用于一些用传统造型方法很难表示和绘制的自然场 景：如火焰与爆炸场面 r e e v e s 8 3 ，流水m d l e r 8 9 与瀑布 s i m s g o 。 l e v o y 与w i h t t e d l e v o y 8 5 在1 9 8 5 年首先提出将点作为基本绘制元素的思 想。他们分析出复杂物体用连续的扫描线方法绘制时的缺陷，并指出点虽然简单 却足以表示任何物体：只要三维点云足够致密，将一个个点投影到屏幕上后仍然 能得到逼真的显示效果。其核心思想是在绘制前将任何物体转化成一系列离散点 表示并用一个新的通用算法绘制。他们用圆形s p l a t 来绘制点，并设定s p l a t 的最 小尺寸为一个象素以保证绘制质量，同时采用a - b u f f e r c a r p e n t e r 8 4 技术进行反 走样，论文中还详细地考虑了纹理问题。 浙江大学硕士学位论文 1 9 9 2 年s z e l i s k i 与t o n n e s o n s z e l i s k i 9 2 在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 。 1 9 9 4 年w i t k i n 与h e e k b e r t w i t k i n 9 4 将有向粒子应用于隐式曲面的采样以及 交互编辑，并采用同样的绘制方法 s z e l i s k i 9 2 来显示有向粒子。 受基于图象的绘制技术( m r ) 的启发，1 9 9 8 年g o s s m a n 与d a l l y g r o s s m a n 9 8 - 1 】 f g - r o s s m a n 9 8 2 1 重新开展了点绘制方面的研究工作，其目标是在避免昂贵图形硬 件的条件下实时绘制复杂物体。同一时期美国m e r l ( m i t s u b i s h ie l e c t r i cr e s e a r c h l a b o r a t o r i e s ) 拓展了s u r f e l s ( s u r f a c ee l e m e n t s ) 的概念 o o s t e r b a a n 9 9 b a a r 9 9 1 ，其思 路与g r o s s m a n d a l l y 的点采样绘制方法( p o i r ns a m p l er e n d e r i n ga p p r o a e h ) 非常相 似。 随后，1 9 9 9 年第一篇有关s u r f e l s 的表示、压缩及动力特性的技术考察报告 发表 z w i c k e r 9 9 1 。 2 0 0 0 年随着p f i s t e r 等人的s u r f e l s p f i s t e r 0 0 1 与r u s i n k i e w i c z 等人的 q s p l a t r u s i n k i e w i e z 0 0 绘制系统出现，点绘制技术有了重要突破。 p f i s t e r 等i f f i s t e r o o 在g r o s s m a l l 和d a l l y 工作【g f 嘲m 曲8 一l 】的基础上加上层次 l o d 控制以圾层次可见性剔除，他们采用了、，i s j b j j i 修s p l a r d n g 技术来检测可见 s u r f e l s 以及z - b u f f e r 内的空洞，并采用p u l l p u s h 算法 g o r t l e r 9 6 g r o s s m a n 9 8 一1 填补空洞。灵活权衡速度与质量的超采样技术被应用于反走样，达到了类似于三 线性m i p m a p p i n g 方法的图象质量。由于s u r f e l s 采用l d i 结构，点云分布在一个 规则的空间网格中，因此从三维扫描设备获取的数据不能直接应用这个方法。 s u r f e l s 绘制技术介于基于几何绘制( g b r ) 及基于图象绘制( m r ) 之间。 同期，r u s i n k i e w i c z 和l e v o y 给q s p l a t r u s i n k i e w i c z 0 0 系统设计了一种全新 的数据结构，高效地压缩了数据并实现了层次l o d 控制和基于法向聚类的可见 性剔除。在预处理阶段，采样点存储在层次包围球内。在绘制时层次遍历数据结 浙江大学硕士学位论文 构，根据当前视点视角、屏幕分辨率以及计算条件等情况选择绘制的层次。q s p l a t 的算法设计允许使用硬件加速绘制，能实时地绘制上亿个点的超大模型。其缺点 是没有考虑透明度以及反走样问题，因此绘制质量一般。 t o b o r 等 t o b o r 0 0 也提出一种类似于g r o s s m a n 与d a l l y g r o s s m a n 9 8 点采样 绘制技术的s u r 嗣s 绘制系统，充分利用硬件来处理s u r f e l s 。g e r n o ts c h a u f l e r 与 h e n r i kw a n nj e n s e n s c h a u f l e r 0 0 提出了一种针对点云表示曲两的光线跟踪算法。 所有的s u r f e l s 均位于八叉树结点内并用光线跟踪算法绘制。 在q s p l a t 的相同应用背景下，同年d i g i t a lm i c h e l a n g e l o l e v o y 0 0 的项目报告 发布。新的扫描技术的发展以及几何实体复杂度的日益增长对基于点的图形技术 发展提出了更高的要求。 2 0 0 1 年出现t e w a s u r f a c es p l a t t h a g 技术 z w i c k e r 0 1 1 】、动态采样绘制技术 s t a m m i n g e r 0 1 w a n d 0 1 、多边形与点的混合绘制系统 c h e n 0 1 c o h e n 0 1 、微分 点绘制技术噼a l a i a h 0 1 】、点采样曲面的频谱处理 p a u l y 0 1 、基于点的多分辨率造 型 l i n s e n 0 1 、m l s 曲面 a l e x a 0 1 以径向基函数 c a r r 0 1 等一大批基于点云表示 的处理方面的研究工作。 z w i c k e r 等 z w i c k e r 0 1 一l 】结合了l e v o y 等人皿e v o y 8 5 的想法以及h e e k b e r t 的 纹理映射中的反走样理论 i - i e e k b e r t 8 9 ，提出了e w as u i f a c 把s p l a t t i n g 技术，将 e w a 技术应用于不规则空间采样点的绘制。e w a ( 椭圆加权平均滤波) s u r f a c e s p l a t t i n g 是一种高质量的物体空间的绘制技术，从信号处理角度考虑各向异性的 纹理过滤、消隐、边界反走样和象素精度的a - b u f f e r 处理。e w as p l a u i n g 技术也 可以应用于体绘制 z w i c k e r 0 1 2 1 。 纯粹用点云来构建场景有其应用缺陷：首先，点云的密集分布造成了大量的 数据冗余，极大地消耗了存储、传输以及绘制资源；其次，在当前的凡何绘制引 擎中，点云在绘制时最终采用三角形或圆面表示，而拓扑关系的缺失使得在视点 靠近时无法保证无空洞的绘制效果。因此许多研究者采用多边形与点混合表示场 景f c h e n 0 1 】 c o h e n 0 1 】，这种混合表示方式结合了点与多边形两种表示方式的优 点：当绘制元素在屏幕上投影区域很小时用点绘制效率高一些，反过来投影区域 较大时用多边形绘制效果更好。 浙江大学硕士学位论文 动态重采样绘制是一类与视点相关的绘制算法，点云的重采样在绘制时进 行，没有预处理过程。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 m i n g e r 0 1 使用固定采样模式从复 杂场景中动态采样。同时，他们还提出一套可用硬件加速点绘制的l o d 技术。 k a l a i a h 与v a r s h n e y k a l a i a h 0 1 使用d i f f e r e m i a lp o i n t ( d p , 微分点) 作为新的绘 制元素。与传统的采样点不同，每个d p 采样点保留了局部微分几何信息，用以 高效高质量地刻画其局部邻域。d p 模型比一般的点模型的采样点要少，因此非 常节省空间，但又不影响绘制效果。d p 可以从n u r b s 曲面上采样得到，也可 以从任何微分曲面上采样得到。它的一个限制是只能表达光滑表面。 r u s i n k i e w i c z 与l e v o y r u s i n k i e w i c z 0 1 改进了q s p l a t ，将其扩展到网络传输 的应用。l u e b k e 与h e l l e n l u e b k e 0 1 采用感知度量作为点绘制时l o d 的选择标 准。w i m m e r 等 w 伽e r o l 】在城市漫游时采用点来绘制远处场景。 a l e x a 等【a l e x a 0 1 】使用移动最小二乘法( m l s ) 逼近点模型表面的点云得到局 部逼近的多项式曲面，并以此定义光滑的二维流形表面来表示点云。m l s 瞌面 被用来进行加密采样以及简化采样，并可在绘制时采用动态加密采样技术以得到 光滑的表面显示效果。 c a r r 等人 c a r t 0 1 采用多重调和的径向基函数0 珀f s ) 从非均匀分布点云中重 构出光滑的流形表面，并将其应用于c s g 框架来实现一种新的造型方法。 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 提出了一种针对点采样曲颟的傅立叶变换以及频谱分 析框架。他们将模型分解为近似为平面的一系列小块，在每个小块上傲傅立叶变 换以及频谱分析，然后将各个小块拼接起来实现对点采样曲面的处理。 2 0 0 2 年国际学术界在这以领域的工作主要集中于高效的点绘制算法，基于点 的造型以及点绘制技术的应用。 b o r s c h 等人 b o s t s e h 0 2 提出用一种非常节省空间的混合数据结构表示点模型 并快速绘翎。c o c o n u 和h e g e c o e o n u 0 2 使用硬件加速e w as p l a t t i n g ，三角面片 浙江大学硕士学位论文 与转化成l d i 的采样点均存储在八叉树内。他们的算法采用八叉树来做l o d 以 及可见性预计算，拓展并应用了m c m i l l a n 算法。同时，对e w a 反走样滤波则 用一系列查找表来估计。与此不同的是，r e n 等人 r e n 0 2 】采用带a l p h a 位的四 边形表示并绘制s p l a t ，并采用两步绘制流程来解决可见性问题及混合问题。w a n d 和s t r a b e r w a n d 0 2 提出一种点一多边形混合绘制技术来实现固定帧的动画绘制。 d e u s s e n 等人 d e u s s e n 0 2 用s t a m m i n g e r 的方；法 s t a m m i n g e r 0 1 交互式绘制大规模 生态场景。g a s l n e n r a s a n e n 0 2 系统地讨论了e w a8 u l f a p 七s p l a t t i n g 并作了些改进， 他用随机采样来实现高质量的e w a s p l a t t i n g 。d e y 和h u d s o n d e y 0 2 发展了另外 一种基于v o m n o i 表面重构技术 a m e n t a 9 8 的点一多边形混合绘制系统。与其他点 一多边形混合绘制系统不同的是，他们的绘制系统可根据局部几何特征的大小来 决定采用点还是多边形绘制。 w 0 r m l i n 等j k w t i r m l i n 0 2 设计了一套应用点绘制技术的3 d 视频系统，他们 还提出一种高效的点模型压缩技术。点绘制的另一个应用实例是g r i g o r y a n 和 r h e i n g a n s 的p r o b a b i l i s t i cs u r f a c e s g r i g o r y a n 0 2 。 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 1 ) 象索编辑方法，p o i n t s h o p3 d 能支持多种变 形、编辑技术如清理、纹理映射、雕刻、过滤以及熏采样等，其最大的特性是点 云模型集成了参数化表示。 f l e i s h m a n 等人 f l e i s h m a n 0 2 使用m l s 面作为他们的基于点采样的多分辨率 曲面表示的基础。他们主要的工作是对基于点云表示的表面作有效的渐进式编 码，但在多分辨率编辑上没有很大的改进。k a l a i a h 和v a r n s h e y k a l a i a h 0 3 1 1 继续 f l e i s h m a n 等人的工作 f l c i s h m a n 0 2 并加入d p ，使得曲面表示拥有了更多的细节。 z w i c k e r 等 z w i c k e r 0 2 2 】提出了e w a 表面以及体绘制的统一绘制框架。 1 6 浙江大学硕士学位论文 e u r o g r a p h i c s2 0 0 2 的基于点的计算机图形学教程 c r r o s s o g 总结了近几年来基 于点的图形学的发展状况，并讨论了以下几个论题：包括e w as p l a t t i n g 在内的 点绘制技术、从图象中获取几何以及外观信息、动态重采样以及实时生态系统可 视化、点模型的表示( m l ss u r f a c e s ) 、点模型的频谱处理、点模型简化以及 p o i a t s h o p3 d 系统。 在2 0 0 3 年s i g g r a p h 会议上，a l e x a 等人 a l e x a 0 3 1 】在原来的基础上进一 步拓展了m l ss u f f a e e s a l e x a 0 1 。a d a m s o n 和a l e r a t a d a m s o n 0 3 使用m l s 投影 运算实现点采样表面的光线跟踪算法。a l e x a 等 a l e x a 0 3 - 2 通过对点模型表面建 立方向场来实现表面参数化、纹理合成以及表面间的映射。 p a u l y 等 p a u l y 0 3 - l 】在以前的工作基础上 p a u l y 0 2 2 】提出了一个完整通用的 点模型自由造型框架。结合无约束点云及m l s 近似得到的隐式曲面，他们构造 出混合表示的实体模型。该造型系统同时利用了隐式曲面以及参数化曲面的优 点，允许对任意形状的点模型作大规模的变形以及布尔运算。 o h t a k e 等人 o h t a k c 0 3 提出了种新的隐式外形表示方式：整体多层分割 ( m u l t i - l e v e lp a r t i t i o no f u n i t y , m 默睐构造大规模点云的表面模型。通过八叉树剖 分点模型成若干区域块，并用分段二次函数来摇述局部形状再用加权函数混合局 部形状函数达到整体光顺的表示效果。 a d a m s 和d u t r 6 实现了基于s u r f e l s 表示实体的交互式布尔运算 a d a m s 0 3 1 1 。 八又树结构被用来加速布尔运算时的内外测试，相交边界处s u r f e l s 被细分重采 样以达到锐利的边界表示结果。同时他们还提供了一个相交边界的磨光算法 【a d a m s 0 3 2 1 a k f i v 盘n c k k f i v f i n e k 0 3 l 】在e w as u r f a c es p l a t t i n g 的基础上创建了一种新的快 速深度场景o f ) 绘制算法。通过深度模糊以及视觉聚焦选择适当的l o d 绘制 达到图象合成效果。b a l a 等 b a l a 0 3 提出了颞的一种带阴影计算的复杂场景绘制 技术，结合点与边生成商质量图象。 用图形芯片( g p u ) 加速图形绘制已经成为热潮，d a c h s b a c h e r 等 【d a e h s b a c h e r 0 3 设计了一个连续结构树并用可编程图形硬件绘制，使得c p u 的 计算负担大大减轻。 1 7 浙江大学硕士学位论文 1 4 基本流程 基于点的图形学分成三个主要部分：获取、处理以及绘制。 毒鞠酝点模型的主要来源为3 d 扫描仪生成的原始数据，包括深度相机生成 的深度图与激光三维扫描仪或者接触式机械探头等设备得到的大量三维空 间点位置。三维点云再配合光学照片可以得到带颜色或纹理色彩的三维实物模 型。点模型的另外一个来源是现存的几何模型。所有几何模型( 多边形网格模型、 样条面片模型、隐式曲面、c s g 树、粒子系统等) 均能方便地转化成点模型， 不同的采样精度能得到不同分辨率的点模型。 蹙堡点模型的处理分前期处理( o b j e c tr e p r e s e n t a t i o n ) 以及后期处理( o b j e c t m o d e l i n g ) 。扫描得到的原始数据具有噪声、拼接错位、空洞、不确定性和过度 采样的问题，需要经过前期处理才能使用。前期处理的目标是从原始点云中构造 出一个连续的表面模型，后期处理则在前期处理的结果上再作进步的造型处理 如重采样、磨光、多分辨率简化、编辑、变形、布尔运算等操作，得到各种各样 的点模型。对点模型的数字几何处理( d g p ) 也在后期处理阶段进行，其目标是在 点模型的流形表面领域内拓展基本的信号处理概念。 尝名麸点绘制的目标是在屏幕上输出一系列的点并构成连续的表面。从三维 离散点采样直接重建出三维空间的连续信号，对连续信号进行滤波后重新采样并 投影至二维屏幕进行光照计算。由予点模型没有拓扑关系，利于重新采样和投影 计算，因此点绘制的可以加快大规模数据构成场景的绘制过程。点模型的绘制同 样需要解决面绘制所含的基础问题，如光照计算、可见性计算、阴影计算、纹理 映射、反走样等。另一方面，点模型的离散性使得在视点靠近物体的时候，需要 考虑点模型和面模型的混合绘制。基于点的绘制技术的一个特点是离散点集映射 到屏幕后需要在图象空间内作图象重构处理来填补空洞并重构物体表面。 整个流程如图1 2 所示。 1 3 辑江大学硕士学位论文 图1 2 基于点表示实体的获取、处理及绘制全流程图。 浙江大学硕士学位论文 1 。5 论文范围 本文主要讨论点模型的表面表示以及在此基础上的造型技术，基于点的绘制 方面的内容也将涉及到一点。些其它方面相关的内容也在论文中有所提及，包 括：m m ，m r ，d g p 等。 本文不讨论如何从实物扫描获取点模型，也不讨论如何将其他方法表示的模 型转化成点模型。造型时用到的点模型均是前期处理过的，不是原始扫描获得的 数据。 1 6 主要贡献 本文的部分工作建立在a d a m s 和d u r r a a d a m s 0 3 、p a u l y 等人【p a u l y 0 2 - 2 】的 ：f 作基础上。他们的论文中已经提到了部分重要内容，但还有许多工作没有提及 或者还未完成。本文主要贡献如下： 拓展了a d a m s 和d u t r d 的框架并将其应用于不同分辨率点模型以及非均 匀采样点模型的布尔运算。本文应用自适应八叉树割分实体来加速 i n s i d e o u t s i d e 测试，并在相交边界处采用动态重采样技术以保持锐利的 边界表示。 从统计的角度分析点云模型的光顾除噪，并提出了一个针对随机噪声的 邻域重心约束光顺算法。此方法不需要表面重构并保证迭代过程中主体 形状不变。 通过原点约束将邻域重心约束光顺算法推广为局部光顺算法。 1 7 论文组织 第一章回顾基于点的造型与绘制的历史起源与发展状况；第二章将系统介绍 前人在基于点的模型表示与造型方面的工作；第三章介绍了一种不同分辨率点模 型以及非均匀采样点模型的布尔运算框架，此框架是对a d a m s 和d u t r d 提供的算 法 a d a m s 0 3 】的一个拓展；第四章讨论点模型的光顺造型。第五章总结全文并介 2 0 浙江大学硕士学位论文 绍了。一些未来工作。 1 8 约定习惯 如果没有特别说明，每个采样点均表示一个带有法向的微小局部区域。通常 用一个带一定半径的圆盘简化表示此区域。 本文在绘制时采用直接几何绘制方法：用带位的纹理绘制四边形，这个四 边形垂直于其法向( 在一些特殊场合默认采样点形状为球，采用正交投影到屏幕 的方法绘制) 。这种绘制方法可利用图形硬件绘制多边形并用硬件z 由曲h 消隐。 尽管局部放大绘制结果在一些区域内存在严重的空洞与走样现象，但这种方法能 很好地表示局部几何信息，并且能快速地绘制，因此它特别适合于本文所研究的 造型阶段的交互式显示。要得到更好的绘制效果，可以采用更好更复杂的绘制方 法( 如e w as u r f a c , es p l a t t i n g ) ，但这不在本文的研究范围之内。 如果不做特殊说明，文中所提及的空间为欧氏空间。造型所依赖的座标系为 右手座标系，_ x 轴正向向右，y 轴正向向上，z 轴正向指向观察者( 图13 ) 。