（计算机软件与理论专业论文）三维点云模型轮廓线的绘制.pdf

山东大学硕士学位论文 摘要 轮廓线在计算机图形学、计算机视觉和模式识别中占有重要地位，它是表示 物体形状最重要的因素之一。在非真实感绘制中，能够用轮廓表达出艺术的效果； 在计算机视觉和模式识别中，轮廓是识别物体的非常重要的特征之一。因此，如 何提取物体的轮廓线，一直是计算机图形学研究的热点问题之一。 物体点云模型是利用三维扫描仪对物体进行扫描得到的物体表面的直接采 样点，是对物体表面的几何属性最真实地记录。由于点云模型不需要存储和保持 物体表面的连接信息，与三角网格点模型相比，点云模型在表示比较复杂或动态 变化的形状时有着更多的灵活性。近年来，基于点云模型的数字几何处理技术越 来越受到人们的关注。 本文主要研究如何快速获取点云模型上的轮廓点，并将获得的离散的轮廓点 连接成为一条连续的3 d 轮廓线。本文的主要贡献有： 1 、提出了利用高斯球获取点云模型轮廓点的方法。由于点云数据是无结构 的数据，如何快速判断哪些点落在物体轮廓上是获取轮廓线的首要问题。本文根 据平行投影和透视投影两种不同情况，将物体表面顶点的法向向量分别向三维、 四维空间高斯球上映射，利用层次划分快速判断三维点云模型上的轮廓点，从而 实时获取物体表面轮廓上的点。 2 、提出了一个基于图结构的点云模型上轮廓线的获取算法。在获取轮廓点 的基础上，利用点的原始位置信息，将邻近点连线形成图表示的初始轮廓线，利 用最小生成树、短边剪枝、光滑等几个步骤进行处理，形成最终的光滑轮廓线。 实时获取三维点云模型上光滑的轮廓线，对物体的实时非真实感绘制，物体 的识别等提供了基础，下步工作将利用具有艺术效果的笔划重描轮廓线，得到 山东大学硕士学位论文 i i 山东大学硕士学位论文 a b s t r a c t s il h o u e t t ep l a y sa ni m p o r t a n tr o l ei nt h er e s e a r c ho fc o m p u t e r g r a p h i c s ，c o m p u t e rv i s i o na n dp a t t e r nr e c o g n i t i o n i ti s a ni m p o r t a n t f a c t o rt od e p i c tt h es h a p eo fo b j e c t i ti sn o to n l yr e l a t e dt ot h er e s u l t o ft h ef i n a lr e n d e r i n g ，b u ta l s ot h ek e yt os p e e du pt h er e n d e r i n gp r o c e s s i nt h eg r a p h i c sa p p li c a ti o n t h e r ea r es om a n yk i n d so fli n e st oe x p r e s s t h eo b j e c ts h a p e s ，s u c ha ss il h o u e t t e s ，c o n t o u r s ，c r e a s e se t c ，a n d s i l h o u e t t ei st h em o s ti m p o r t a n ta n de f f e c t i v ei ne x p r e s s i n gt h eo b j e c t s h a p e f o rp a i n t e r s ，t h e yc a nu s es i l h o u e t t e st oe x p r e s sa r t i s t i ce f f e c t t h u st h ee x t r a c t i o no fs il h o u e t t e so fo b j e c t si sas p o tt o p i ci ns u c h r e s e a r c hf i e l d sa sc o m p u t e rg r a p h i c sa n dc o m p u t e rv i s i o ne t c w i t ht h ed e v e l o p m e n to f 3 ds c a n n e r st e c h n o l o g y ，o n ec a ng e tt h e p o i n t sd i r e c t l yf r o m3 ds u r f a c e sa n dt h ep o i n t sc a ne x p r e s st h er e a l g e o m e t r yp r o p e r t i e so ft h es u r f a c e so fo b j e c t s d u et ot h ea d v a n t a g eo f n o ts t o r i n ga n dm a i n t a i n i n gt h ec o n n e c t i v i t yo ft h es a m p li n gp o i n t s ，t h e p o i n tc l o u d m o d e lh a sm u c hm o r ef l e x i b i l i t i e s o n r e p r e s e n t i n ga n d p r o c e s s i n gt h ec o m p li c a t eo rd y n a m i cs h a p e sc o m p a r e dw i t ht h em e s hm o d e l t h e r e f o r e ，t h ep o i n tc l o u dm o d e lb e c o m e sm o r ep o p u l a ri nt h er e l a t e d r e s e a r c ha r e a sa sw e lla st h ei n d u s t r y i nt h i sp a p e r ，w ef o c u so nh o wt oe x t r a c ts i l h o u e t t e sf r o mp o i n t sc l o u d m o d e la sq u i c k l ya sp o s s i b l e t h em a i nc o n t r i b u t i o n so ft h ew o r ka r e ： 1 、w ep r o p o s e dam e t h o dt oe x t r a c ts i l h o u e t t ep o i n t sf r o mp o i n t sc l o u d i i i 山东大学硕士学位论文 m o d e lb yu s i n gg a u s s i a ns p h e r e d u et ot h ep o i n tc l o u dm o d e lh a v i n gn o c o n n e c t i v i t yi n f o r m a t i o n ，i ti sd i f f i c u l tt od e t e c ts i l h o u e t t ep o i n t s q u i c k l y w ep r o p o s e dac o n c e p to fh i e r a r c h i c a lg a u s s i a ns p h e r e b a s e do n t h eh i e r a r c h i c a ls t r u c t u r e ，w ed e t e c tt h es il h o u e t t ep o i n t si nt h ep o i n t c l o u dm o d e l sw h i c ha r eu n d e rp e r s p e c t i v ea sw e l la sp a r a l l e lp r o j e c t i o n 2 、w ep r o p o s e da na l g o r i t h mf o rc o n n e c t i n gt h es i l h o u e t t ep o i n t st o b et h es il h o u e t t eli n e si nt h em o d e l u s i n gt h eo r i g i n a lp o s i t i o n so ft h e s il h o u e t t ep o i n t s ，w ec o n s t r u c tac r u d es il h o u e t t e1i n er e p r e s e n t e db y ag r a p hs t r u c t u r e t h e n ，b yt h emi ni m u ms p a n n i n gt r e e ，t r e ep r u n i n g ，a n d t r e es m o o t h i n g ，w eh a v et h e3 dr e f i n e ds il h o u e t t e1i n e s t h es i l h o u e t t el i n e sp r o v i d eas o l i df o u n d a t i o nf o rr e n d e r i n g so fl i n e d r a w i n g s ，a sw e l l a sp a t t e r nr e c o g n i t i o n si nr e s e a r c ha sw e l la si n i n d u s t r y k e yw o r d s ：s ；i h o u e t t e ：p o i n t sc i o u d ：g a u s ss p h e r e ：o u a dt r e e ；n p r 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 缸重 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：越导师签名：期：螋 山东大学硕士学位论文 第一章绪论 1 1 研究背景 随着三维扫描技术的发展，人们可以很容易地得到物体表面稠密均匀的采样 点。直接用这些点来表示物体表面几何形状，这样的模型我们称之为物体的点云 模型。较之其它表示模型，如多边形网格模型、参数化表示模型等，点云模型是 对物体表面几何属性的最真实地记录；另外，对物体表面采样点进行网格化并不 是数字几何处理的必需过程，且对于庞大的采样点集的网格化操作，时间和空间 代价都是非常大的。因此，直接基于采样点的三维数据处理是数字几何处理研究 中不可或缺的一部分。 点云模型作为三维建模的一种基本表示在图形学中已有二十年的历史。早在 1 9 8 3 年，r e e v e s 采用粒子作为数据处理的基本元素来模拟火和爆炸的状态。系 统中的每个粒子均具有如下的属性：位置、速度及方向、颜色、生命期、目前生 命段、形状、大小、透明度等等信息。2 0 0 0 年，随着斯坦福大学计算机图形学 实验室的数字化米开朗基罗项目的进展，出现了大规模点云数据表示的复杂物体 和场景，点云模型得到更加广泛应用。点云模型相关的研究工作逐渐成为了计算 机图形学、计算机视觉等领域一个新的研究热点。 基于点云模型的三维模型的数字几何处理技术涵盖的内容非常广泛，主要 包括数据获取，几何建模，表面参数化，光顺去噪，局部几何性质估计，特征检 测，传输压缩，绘制以及变形等。基于点云模型的轮廓线获取也是数字几何处理 需要研究的重要问题之一。 轮廓线在计算机图形学、计算机视觉和模式识别中占有重要地位。它是表示 山东大学硕士学位论文 物体形状最重要的因素之一。在非真实感绘制中，常常用轮廓突出物体的外形( 如 图1 1 ) ；在计算机视觉和模式识别中，轮廓线是识别物体的非常重要的特征之 一。因此，如何提取物体的轮廓线，一直是计算机图形学研究的热点问题之一。 1 2 非真实感绘制技术 作为轮廓线的最重要的应用领域，下面简要介绍一些非真实感绘制技的背 景。自2 0 世纪6 0 年代计算机图形学诞生以来，其主要目标即为生成能仿效传 统相机效果的图像，即真实感图形学。经过4 0 余年的研究与发展，许多与具有 光滑规则外形物体的造型和绘制相关的问题已经得到解决，甚至可以生成非常复 杂的包含自然界场景。真实感达到了“象照片一样真实的效果”。从心理学的 观点来看，真实感图形暗示着精确性和完美性，强调模拟场景对于显示的保真度。 1 9 9 0 年，h a e l b e r i 发表了著名的开创性的论文一 ( p a i n tb yn u m b e r s ： a b s t r a c ti m a g er e p r e s e n t a t i o n s ，标志着计算机图形学非真实感绘制技术的 比较项目真实感绘制技术非真实感绘制技术 基本趋向模拟物理世界模拟艺术家的风格 评价方式客观主观 基本方法模拟物理过程研究人类的感知、模拟艺术家的创作手法 准确性 精确 近似 细节水平相同的细节等级可以突出表达重点部分 表1 1 真实感绘制技术与非真实感绘制技术比较 正式诞生。2 0 世纪9 0 年代中期开始，非真实感绘制逐渐成为计算机图形学的研 究焦点之一。顾名思义，非真实感绘制指的是利用计算机生成不具有照片真实效 2 山东大学硕士学位论文 果而具有手绘风格的图形技术。其目标不在于图形的真实性，而主要在于表现图 形的艺术特质、模拟艺术作品( 甚至包括作品中的缺陷) ，或者作为真实感图形 的有效补充。 由于非真实感绘制技术是一个新兴的学科领域，并没有统一的定义。我们可 以通过与真实感绘制技术的比较来理解非真实感绘制技术。表1 1 给出了真实感 绘制和非真实感绘制的比较。 则唧骣 圈1 1 左囤为真实感绘制，中图与右图加强轮廓边缘的绘制 圈12 利用物体轮廓线进行艺术效果的绘制 基于物体空间的非真实蹲绘制技术是非真实感研究的一个重要领域。它注重 的是人们对三维物体形状的感知与表达，通常以轮廓线勾勒出物体形状，以主曲 率方向来表达光滑曲面的形状。根多手工绘制的3 d 场景经常通过简化某些不是 特别有意义的细节和增强轮廓线来突出设计者的意图。此外，轮廓线还可以作为 山东大学硕士学位论文 卡通风格绘制的基础，在三维画在表现模型的时候，通常用轮廓线来勾勒形状， 并用粗线来表现模型的重要特征，如图1 1 的表示利用轮廓增强物体的形状。图 1 2 表示了利用轮廓来表示卡通效果的角色。 1 3 相关研究 轮廓线作为一种表示物体形状最有效的方法，有很多获取物体轮廓线的方 法。前人的工作中大部分基于三角面片模型确定物体的轮廓线 1 ，以及基于 三角面片模型进行线条的非真实感的绘制 2 ，3 ，4 ，5 ，6 ，7 。有时为了获得更好的 表达效果，也有在轮廓的基础上再添加其他的线条，如折缝 3 ，5 ，6 ，7 ，8 、启发 式轮廓线 9 ，1 0 等。 针对点云模型，文献 1 1 中提出了一种基于图像空间点云模型的轮廓交互绘 制算法，通过绘制点云模型上轮廓处的点画处物体轮廓线，得不到轮廓的空间结 构信息。文献 1 2 中提出了点云模型上基于图像和物体空间的混合算法，首先逐 点判断模型上哪些点是轮廓点，然后将轮廓点投影到平面，利用颜色缓存标记不 同轮廓点，然后通过连接平面上的点得到三维模型上的轮廓。算法针对小规模的 模型可以达到实时绘制，但针对大规模模型，逐点判断轮廓点的算法效率达不到 实时要求。另外，由于是物体空间和图像空间的混合方法，算法的扩展性不好， 比如针对一些提示性轮廓，由于投影到二维平面后轮廓线交叉比较多，提取轮廓 线时带来很大局限。 本文提出了一种直接在物体空间获取轮廓的快速方法。首先将点云模型上每 点的法向映射到一个高斯参考球上；然后将映射后的点组织成四叉树结构，利用 此结构快速计算出模型上的轮廓点：最后通过三维空间点的相邻关系，利用图和 最小生成树，追踪得到三维空间中点云模型的轮廓线。算法无需对点云模型进行 4 山东大学硕士学位论文 三角化或曲面重建，且无需逐点判断模型上的点是否为轮廓点，因此适合大规模 点云数据模型上轮廓的计算。 1 4 论文结构及工作安排 本文第二章介绍轮廓线定义及已有轮廓线的检测算法。第三章介绍点云模型 数据定义、轮廓点的获取算法。提出基于点的法向高斯球，建立点云的法向矢量 世界坐标与矢量球的局部坐标一一对应。利用球面上的层次划分，来获得点云模 型数据的索引。针对平行投影及透视投影两种情况，提出获取轮廓点的加速算法。 第四章介绍如何将获取的轮廓点连成光滑的曲线，提出了一种基于物体空间的获 取轮廓线的方法。第五章对本文的工作做出总结，并对以后的工作提出展望。 1 5 本章小结 本章讲述了论文的研究背景、意义、研究的现状；阐述了研究目标；最后给 出了本文的结构框架。 山东大学硕士学位论文 第二章轮廓线检测技术概述 表达物体形状的线有许多，其中轮廓线是一种重要的表示物体形状有效的方 法。轮廓线是与视点相关的，当视点变化时，我们需要重新计算轮廓线。快速绘 制轮廓线是非真实感线条画中的关键技术。轮廓线的绘制技术主要包括轮廓的检 测、可见性判断等问题。轮廓线检测算法主要是从三维物体中获取它的轮廓线， 包括物体的边缘，以及褶皱等。算法目前主要有基于物体空间的算法，基于图像 空间的算法以及两者混合的算法。 2 1 轮廓线的定义 表达物体形状特征的线有许多。根据各自的特点可分为以下四类： 第一类：轮廓线( c o n t o u rs i l h o u e t t ee d g e ) ，是指物体的前向面和物体 的后向面的公共边形成的轮廓。这类轮廓线包括物体的边缘和物体内部的不连续 位置。前者表现了物体的空间轮廓，将物体与背景分离开：后者刻画了物体的形 体特征。 第二类：褶皱( c r e a s ee d g e ) ，指物体的两个相邻面共有的边。根据其夹 角小于或大于某个阀值时，它们的公共边就分别称为凸边( r i d g ee d g e ) 或凹边 ( v a l l e ye d g e ) ( 又称为谷或脊) 。二者作为物体固有的特征线，是不随视点 的变化而变化的。只要可见就可以绘制。 第三类：边界( b o u n d a r ye d g e ) 。它是一个只有相邻面的边。比如一个打 开的盒子，盒盖上的边。对于封闭的物体如正方体不存在这种线。 第四类：阴影轮廓线和材质边界轮廓线( m a t e r i a le d g e ) 。不同材质的两 个面的公共边界。光照产生的阴影和不同的材质在绘制过程中虽然不会产生不连 6 山东大学硕士学位论文 续，但是会形成明显的过渡而产生的线条。这些线可以增强物体的非真实感绘制 效果，是艺术家希望总是显示的线条。 本文中讨论的只是第一类轮廓线，如图2 1 所示，我们在一个盒子上来描述 各类轮廓线的位置，用上述各种线首字母标记出了每条线的类型，如c s 表示 c o n t o u rs il h o u e t t e s 。 图2 1 各类边界线 2 2 图像空间轮廓线的检测算法 在图像空间检测轮廓线是一种简单而且高效的方法。它通过处理已经绘制的 基于视点的场景图像，在图像缓存中检测物体的边界以及其他特征线，这个方法 会受到图像精度的影响，但可以满足一般的应用。 最直接的方法是利用颜色缓存，从三维场景绘制得到的图像缓存中根据颜色 的不连续检测到物体的轮廓。这个方法显然存在严重不足，检测不仅受到图像分 辨率的限制，而且出于纹理贴图等原因，通过检测得到的结果往往存在非表现物 体轮廓的多余的线。由于绘制的原因，互相覆盖而且颜色相同的两个物体检测不 到轮廓线。 目前比较有效的方法是利用三维场景的信息，采用特殊的绘制手段，得到比 较特殊的绘制图像，在这些绘制结果中检测到物体的轮廓线。流行的技术可以分 为两类： 山东大学砸：卜学位论文 第类方法足分别在椿度驶像和向量映像中检测物体的轮廓然后结合两青 的结果，最后得到的效果令人满意 深度映像通过打开渲染叫的深度检测，u r 以在深度缓存中得到最终绘制图 像上每象紊的椿度值，即得到深度耿像。这个方法假殴，对于相邻的两点属 于同一个物体上的潦度变化小，属于不同物体的点深度变化太，通过深度的不连 续性来分析面的不连续性。见图22 ( a ) 圈22 图像空间的轮廓线榆测，深度映像与向量映像相结合的方法 ( a ) 环度映像( b ) 深度映像检测到的边( c ) 向量映像( d ) 向量映像检测到的边 ( e ) 综台闰( b ) 和( d ) 得到的结果( f ) 折叠的纸( g ) 深度检测( 检测不到折痕) s a i t o ，c u r t i s 和d e c a u d i n 8 ，1 3 ，1 4 都提出，类似的算法。s a i t o 和 _ _ a k a h a s h i 8 的做法是对深度映像的每个点计算深度的变化梯度，把变化大的 标记为轮廓上的点。 第。类方法通过利用硬件的绘制技术米实现，这些方法都相当简单而且容易 实现。这此方泣小直接对图像缓存操作而是通过对三维场景的多遍绘制达到 轮廓加强的效果。有人把这类方法称为混合算法，因为它即不在图像缓存中操作， 也小在物体卒间中柃剽轮廓，我们认为这类算法主要还是利用了图像空间的算 0 嘞0 山东大学硕士学位论文 法，所以把它归类为图像空间的算法。这类算法的代表有g o o c h 2 ，1 5 3 和r a s k a r 与c o h e n 1 6 提出的方法。g o o c h 提出了两种方法，分别基于环境映射和镂空缓 存。环境映射( 也称为球体映射) 是通过物体上的点的表面法向量和它到视点向 量的点积来决定轮廓线的粗细，具体的实现见 2 1 5 ，效果见图2 3 ，可以看 出效果不是很好。r a s k a r 1 6 提出的具有图像精度的轮廓线绘制方法效果更好， 他们的方法是打开深度缓存，先用普通渲染模式绘制所有前向面，再用线框模式 绘制所有后向面，这样就可以得到所有朝前面和朝后面形成的轮廓线。通过对朝 后面沿着它的面法向平移小段距离可以突出显示轮廓线，通过控制平移的距离， 可以控制轮廓线的粗细( 见图2 4 ) 。这类方法的局限是只能找到第一类轮廓线， 不能找到物体的第二、三类轮廓线。虽然也可以控制轮廓的粗细，但不是很灵活。 o 辫o 图2 3 用球映射技术绘制的轮廓线，加粗球的边缘可以加粗轮廓线。 c y e 一 = 0 时，点p 是可见的： 山东大学硕士学位论文 否则点p 是不可见的。特别地，当no v = 0 时，点p 是物体轮廓上一点。我们将 模型上所有点的法向正则化，然后将正则化的法向投射到高斯球上。高斯球沿经 线和纬线进行分割，形成层次化的结构单元。如图3 1 所示，每一个单元都是具 有四个角点的凸的球状区域，每个单元又可以进一步划分为四个子单元。对于这 样划分得到的每个单元，如果它的四个角点都是可见或者不可见的，那么通过法 向映射到这个单元中的所有模型上的点都是可见或者不可见的，这些点肯定不是 轮廓点，我们称这样的单元为e c ；如果单元的四个角点有不同的可见状态，那 么映射到这个单元中的模型上的点肯定存在一些轮廓点，我们称这样的单元为 s c 。对于给定投影方向，我们通过判断层次划分的高斯球的单元类型，可以避免 对模型上每个点进行计算，从而加速轮廓点的计算过程。从最粗略的划分开始， 如果一个单元类型为e c ，则不做任何计算；如果一个单元类型为s c ，则进一步 判断其子单元，直到最细一层划分，如果单元仍为s c ，则逐一判断此s c 单元中 对应的模型上的点是否为轮廓点，将满足条件的点标记为轮廓点。 对于透视投影，相对于模型上不同的点，投影方向不再是常量，视点与模型 上点的位置决定了该点的投影方向。我们通过建立四维空间的三维高斯球来达到 以类似平行投影的方式计算模型上的轮廓点。 假设v = ( ，0 ，t ) 为视点，p ( o ，y p ，z p ) 7 为点云模型上一点， n = ( n ；，n ，n ；) 为其法向量。又假设f ( x ，p ) 是过点p ，且以点p 的外法向为法 向的平面，即f 是点p 处点云模型表面的切平面，则t r ( x ，p ) 毫n e ( x p ) = 0 ， 其中x = ( 五y ，z ) 丁。平面f 将整个三维空间分为两个半空间，其中点p 的外法向 指向的一侧我们称为平面f 的上面，另外一侧为平面f 的下面。我们有如下观察： 若视点v 在平面f 的上面，那么点p 定是可见的；若视点v 在平面f 的下 1 9 山东大学硕士学位论文 面，那么点p 则是不可见的；若视点v 恰好在平面f 上，那么点p 一定是在该模 i 型在此视点v 下透视投影轮廓上的点。 由此可以通过检测视点是否在平面f ( x ，p ) 上来判断点p 是否在轮廓线上。 判断点v 是否在平面f 上，即 v ( v ，p ) 兰n ( v - p ) = 0 即：f ( v ，p ) = 圪眠+ 0 m + 圪：一( ，x + m y + ：z ) - v 。p ， 其中：v = ( 圪，圪，1 ) ，p = ( ；，n y ，n ：，- ( n 。x + n y y + ：z ) ) 是四 维空间矢量，而y7 相对于模型上的不同点，是个常向量。对模型上一点p ，我 们可以计算得到p 。通过上述变换，我们得到一个常向量v 和基于模型上每个 点p 变化的p 向量，而通过矿7 和p7 的点积可以决定p 7 对应的模型上的点p 是轮 廓点。因此我们可以利用与平行投影相似的办法，建立一个四维空问的高斯球， 把模型上所有点计算其尸7 ，然后映射到四维空间的高斯球上，同时采取分层分 割高斯球的方法，同样通过判断分割单元是e c 还是r c ，加速轮廓点的计算。过 程与上述平行投影处理过程类似，这里不再赘述。 3 2 点云模型轮廓点的计算算法 3 2 1 算法描述 根据以上的分析，算法综述如下： 1 、计算点云模型上点的法向量。通过分析点云模型上点p 的k 近邻的协方 差矩阵来计算点的法向量。 2 、构建高斯球，建立分层数据结构进行数据存储。我们将点云模型中的点 的法向映射到单位矢量球上，建立分层数据结构组织点云数据。在数据处理过程 中只保留点的坐标与法向，树中节点保留点的索引。完成点云模型的数据存储。 山东大学硕士学位论文 3 、获取轮廓点 基于平行投影和透视投影两种不同的情况，递归处理分层结构高斯球上的 各数据单元相应节点的可见性状态判断要求，标记所有符合要求的点，快速获取 轮廓点。 3 2 2 算法实现 i 一、计算点云模型中点的法向量 我们通过分析点云模型上点p 的k 近邻的协方差矩阵来计算点的法向。对于 点p 我们先找出它的邻域点的集合n p ，计算出邻域重心，这样我们就可以建立 起一个协方差矩阵c 如下 2 7 ： 气一芦 r c = lk & 一p i k n p c = ( z f ) ( 只- p ) r 双3 其中，歹= 只“七+ 1 ) 。矩阵c 是实对称、半正定的，有三个不等的实特征 i 值。对于协方差矩阵的最小特征值对应的特征向量就是该点的法向量。 二、构建高斯球，建立分层数据结构进行数据存储。 在点云模型中，我们将点云模型中点的法向映射到高斯球上，然后在高斯球 上进行单元划分，利用四叉树存储这个层次划分。具体做法如下： 对于一个3 d 数据点集合为d p = p 。，p ：，p 。) ，其中点p i 记录了点的坐 标与法向。 1 获取点p 的映射位置 设= ( 札，n ，n ：) 是点云模型上点p 的正则化法向量，通过下面公式可以 2 1 10j p p 一 一 气k & 山东大学硕士学位论文 获得点p 在高斯球上的映射位置。 f u d = a r c s i n ( n y ) 1 d = a r c t g ( n ：，：) 其中，由于点云模型上的每个点的法向都会和高斯球上的一个点相对应。这 样建立以高斯球球心为坐标系原点的球坐标系，建立与点云模型上点的法向相对 应的高斯球： 在高斯球坐标中，我们用两个参数来表示一个法向的法矢：经度1 d 和纬度 u d ( 如图3 2 所示) 。p 为p 在x y ( z = o 平面上的投影。 i y 厂 、 p ( ，沁，n z ) l l d7， z 哭 弋 罗7 p 一一 么 x 图3 2 球坐标与直角坐标的映射关系。 纬度u d 的范围 一，么 ，经度l d 的范围卜羁万】。因为最终还是要通 过法向的直角坐标来计算该点的法向是否与视线向量垂直，所以我们还需要用到 从球坐标到直角坐标的映射，其转换公式如下： f 工删= c o s ( u d ) c o s ( d ) 少。= c o s ( u d ) s i n ( m ) 【z 。= s i n ( u d ) 通过上述公式我们就把直角坐标的法向点的坐标与法矢球的经度和纬度一 山东大学硕士学位论文 一对应起来，并且视线变化时，该高斯球是不变的。可以想象，点云模型中法向 方向相同的某些点会映射在高斯球的同一个点。 2 对高斯球进行层次划分和存储。 对高斯球沿经纬线进行层次划分，得到层次划的四边区域，我们称之为单元。 我们利用四叉树来存储这个层次划分，四叉树的根节点对应包含整个球的最高层 次的单元。对单元逐层划分，如果单元内的点小于一个设定的阈值或者单元的四 个角点经纬度差另j l d , 于一个设定的阈值，则不再划分，不再做继续划分的单元对 应四叉树的叶结点。对于四叉树的中间节点，我们只记录其四个儿子节点及其四 个角点的信息，以及投射到此节点对应单元的模型上点的个数，而对于四叉树的 叶节点，除了上述信息，我们还记录了所有投射到此叶节点内的对应的模型上的 点索引序号以及点的个数。 四叉树的数据结构如下： s t r u c tr i n t l n o d e ( i n ti n u m p o i n t ：记录树节点实际点的个数( 作为判断依据) i n t * p o i n t l n d e x ：该节点内点的索引( 非叶节点，此指针为空) r i n t l n o d e * c h i l d l ：第一个孩子 r i n tl n o d e * c h il d 2 ：第二个孩子 l r i n t l n o d e , c h i l d 3 ；第三个孩子 r i n t l n o d e * c h i l d 4 ；第四个孩子 f l o a ti p o i n t r a n g e 4 ；记录该节点的经纬度最大值最小值 f l o a tn o r m 4 3 ：该节点四个角点对应的法向值 ) ： 山东大学硕士学位论文 其中i p o i n t r a n g e 4 与n o r m 4 3 属于冗余记录，我们此处保留它是为了 加快后面的交互绘制。不需要反向再求，预先求好记录下来。 3 。获取轮廓点 为了叙述方便，我们以平行投影下的高斯球的处理为例。透视投影下的数据 处理，只是需要加上一些对于映射在高斯球上的两个矢量进行数学处理，即 v = ( 圪，t ，1 ) 算法过程如下： p = ( n ，n ，：，一( ；o x + y y + n ：z ) ) 。 1 ) 首先求出当前视向量v 2 ) 获取轮廓点。 从根节点开始检测，如果节点的四个角点的法向与投影向量点积同号，表示 它们的可见性状态一致，即都可见或者都不可见，该节点内不会有轮廓点。把该 节点扔掉，它所包含的子节点也全部扔掉，返回父节点。如果不符合上述条件则 继续检测其子节点。做同样的判断，直到叶节点，记录该节点内点云数据轮廓点 的索引，去掉非轮廓点。继续同样处理其它子节点，直到最后一个子节点。 根据记录的节点内的索引计算出三维轮廓点。 在算法中，我们对落在边界上的点，进行了冗余存储，防止在进行轮廓点判 断时漏掉点。由于在点云模型和高斯球映射过程中的数据结构记录了所有点在原 模型中的索引，这样在利用加速算法得到轮廓点集后，我们可以得到该模型中所 有点对应于原有模型中的索引，以此可以得到轮廓点集中所有点的原有的信息。 这样，在下一章中，我们可以利用所有轮廓点的信息进行轮廓点的连线操作。 2 4 山东大学硕士学位论文 3 3 本章小结 本章主要介绍了点云模型的轮廓点的获取方法及相关预备工作。首先介绍点 云模型的特点及点的法向量获取方法。接着提出了构建基于点的法向的法向矢量 球的方法；然后对平行投影和透视射影两种情况论述了点云模型获取轮廓点的方 法，尤其是提出在四维空间三维高斯球的概念；最后以平行投影为例解释了如何 加速轮廓点的检测速度，并给出7 j j u 速算法。 山东大学硕士学位论文 第四章轮廓线的获取 通过上述轮廓点检测算法我们可以得到一个三维点云模型在某个视点下的 轮廓点集。不过这些点是散乱的，彼此之间没有联系，本章介绍如何将这样一些 离散的点连接起来，形成3 d 轮廓线。由于点云模型上法向计算的不稳定性，模 型上计算得到的轮廓点可能是非常密集的，也可能是非常稀疏的，如图4 2 中( b ) 列所示。文献【2 8 】中根据图的最小生成树进行了点云模型上特征点的提取计算， 受此启发，为了获取光滑的且线宽均匀的轮廓线，我们基于图的最小生成树设计 了轮廓线的提取算法。 在本章中，我们将利用已经得到的轮廓点集进行相邻近点的连线，同时利用 最小生成树、短边剪枝及光滑技术等方法获取可靠的光滑的轮廓线。 4 1 算法综述 原始的点云模型在经过上述轮廓点的获取算法后得到轮廓点的点集合，根据 轮廓点及其在原点云模型中的索引，可以得到一个具有原有点的位置信息的轮廓 点云模型，如轮廓点模型p p l ，p 2 ，p 3 ，p n ) 。那么，如何根据已有的信息将 轮廓点连接成轮廓线呢? 本章的算法基于这样的思路： 首先，利用点与点之间的距离关系将相近的点连接起来。 其次，由于点的获取连接过程中不可避免地会出现误差噪声等因素，再加上 连接的距离限定也会决定连线的结果。所以相邻近点的连接会出现很多的小的循 环、分支、处理过程中的间断等，影响了轮廓线的准确性。由此，我们在以后的 算法中加入了最小生成树方法减少小的循环；短边剪枝方法减少多余的短分支； 最后还利用光滑技术得到光滑的轮廓线。 山东大学硕士学位论文 下面用算法4 1 给出在此章算法的不同步骤。 算法4 1 轮廓线获取算法伪代码描述 1 、利用点的位置信息创建图g , m 2 、创建图锄l 的最小生成树构造图g i 肌n 。岫t 3 、在图q 懈吐删t 中剪除短边构造图q 眦吐c h 4 、使用光滑技术处理图g 砷。m 。h 礴构造图g s m 。o 血 4 2 创建图g | 距离相近的点有可能是连接在一起的。关键是看如何来确定这个决定能否连 接的距离。本算法首先在点集中确定一个起始点，根据距离决定其它的点是否连 接；然后，再在与该点连接的点中寻找也它距离相近的点进行连接。当一次连接 出现终点时，即这次连接参与的所有点没有其它的连接对象。再确定一个起始点， 重复进行连接步骤，直到所有的点结束。 需要注意的是不同的三维模型点的相对位置情况是不同的，所以根据不同的 情况来定义距离闽值是本算法成功与否的关键。本节算法4 。2 描述如下： 算法4 2 构造图g 缸1 l 、定义d m 找 2 、s o 赋初值( 算法开始时，该点可以是轮廓点集上的任一点，作为g a 的 起点。为了方便，我们以索引顺序为依据。) 3 、计算集合中的点集p 中的点p 与s 。的距离d 4 、i f 存在点p i ，使d = l 。雕t h e n 将所有深度小于l m 馘的分支除去 e n d i f i f 只有一个分支的深度 - - l m 畎并且至少有两个 分支的深度 l m 戤t h e n 保留该分支并在较短的分支中选择最长的一条 e n di f e n df o r 由上述算法4 3 可以得到图。d _ b r a n 。h 。 4 5 光滑处理构造轮廓线g 一 对轮廓线的平滑采用文献【3 0 】中平面曲线演化的做法。文献【3 0 】中方法的主 要思想是：假设曲线c 用一个参数化方程c 妒) = b ( p ) ，y ( p ) y 表示，为了描述 曲线演化的过程，增加一个时间变量f ，用c ( e d 表示t 时刻的曲线，曲线演化 方法是使曲线上每个点沿局部法线方向，以与曲率成正比的速度移动，演化的趋 势是使曲线形状趋向平滑。 具体做法是； 将。e a _ b r 蛐。h 。上的点投影到平面，得到由折线表示的初始轮廓线，计算折 线顶点处的两折线的角度大小及角平分线。根据折线顶点处的角度移动该顶点的 位置，角度越小的顶点，表示该处局部曲率越大，顶点移动的距离越大；角度越 大的顶点，表示该处局部曲率越小，顶点移动的距离越小。重复上述移动过程， 直到折线上每个顶点的角度大于某个阀值，表示曲线达到了要求的光滑程度。上 出垄查兰罂圭耋堡墼耋 述过程用下列公式表示： 只舯”= 只“f ( kc , ”) j 4 其中，p l l 为顶点尸第n 次移动的结果；k , 为n a p 处的角度大小，代表 曲率：m 为顶点r 角平分线方向，代表法向 由上述光滑处理唏m “一h “一后生成光滑的轮廓线g m 。m 。 46 实验结果 由图4 1 、国4 2 、图43 及图44 给出实验的结果。其中在图42 ( a ) 、图 4 3 ( a ) 及图4 4 ( a ) 中分别给出马、兔及龙模型的真实感显示；在图42 ( b ) 、图 4 3 ( b ) 及刚44 ( b ) 中分别给出马、兔及虎模型经过计算得到的轮廓点构造的轮 廓线图示：图42 ( c ) 、图4 3 ( c ) 及陶44 ( c ) 中分别给h 5 、兔及龙模型经过进 步处理后得到的轮廓线图示。通过对比，可以看出奉章算法的有效性 圉4 1 ( a ) 球的模型巾) 计算得到的轮廓线 轧 ( a )m )0 ) 罔4 2 马模型及轮廓线脚示 =幛 i f 末大学硕士学位论文 ( a 】 m ) 图43 兔模型及轮廓线圈示 f 眨l 、l 建p b ， 锄鬣勃 ( 砷西)( c ) 圉4 , 4 龙模型厦轮廓线图示 4 7 本章小结 本章从已经获取的轮廓点集开始，对轮廓点集中的点进行连接，分别经过了 选点连线创建图岛，、创建图g u 的最小生成树图g 舯。d 叫、通过剪枝构建图 g e db r mh 、通过光滑处理形成轮廓线g i 。m 等几个步骤，最后获取已有轮廓 点的轮廓线。 山东大学硕士学位论文 第五章结论与进一步工作的讨论 本文主要提出了一种在点云模型上快速计算3 d 轮廓的算法：通过构建高斯 球，建立分层数据结构进行数据存储：针对平行投影和透视投影两种情况论述了 点云模型加速获取轮廓点的方法；尤其是针对透视投影提出在四维空间三维高斯 球的概念。同时通过三维空间点的相邻关系，利用图、最小生成树及光滑技术， 追踪得到三维空间中点云模型的轮廓线。算法无需对点云模型进行三角化或曲面 重建，且无需逐点判断模型上的点是否为轮廓点，从而适合大规模点云模型3 d 轮廓线的计算。 轮廓线是基于视线的绘制，它是随视线的变化而变化的。虽然我们可以快速 的获取到点云模型上的轮廓点，并且由此得到轮廓线，但由于不同点云模型中的 点的构成各有特点，生成的轮廓线也不尽是符合实际。下一步研究有许多问题可 以做。例如如何更加精确快速地绘制不同点云模型的轮廓线，如何实现更加快速 的实时绘制结果，快速准确地判断可见性以及对其进一步风格化等等。 3 2 山东大学硕士学位论文 参考文献 【1 k o e n d e r i n kj j w h a td o e st h eo c c l u d i n gc o n t o u rt e l lu sa b o u ts o li d s h a p e ? ，p e r c e pt i o n ，1 9 8 4 ，1 3 ：3 21 3 3 0 2 g o o c hb ，s l o a np ，g o o c ha ，s h i r l e y ，a n dp r i e s e n f e l d r i n t e r a c t i v e t e c h n i c a li l l u s t r a t i o n ，p r o e o ft h e1 9 9 9s y m p o s i u m 0 1 1i n t e r a c t i v e 3 dg r a p h i c s ，1 9 9 9 ，3 1 3 8 3 k a l n i n sr d ，m a r k o s i a nl ， a n dm n u g h e s ，d r a w i n gs t r o k e s 2 0 0 2 ，7 5 5 7 6 2 4 h e r t z m a n n