（计算机软件与理论专业论文）点云模型阴影线条画的绘制.pdf

山东大学硕士学位论文 摘要 随着计算机图形学的发展，用点云模型作为三维物体在计算机内的表示形式 越来越受到人们的重视。一方面点云模型获取简单方便。另一方面，点云模型相 比网格模型所占的存储空间少，但同样可以表现物体表面丰富的细节。目前对点 云模型的研究已经涉及到从重建、绘制到应用的各个方面，点云模型已经成为一 个热点研究领域。 阴影线条画是非真实感绘制的一种风格，它用各种不同类型的阴影线来表现 物体表面的形状、纹理和亮度等信息。阴影线在物体表面的走向表现了物体的形 状，不同宽度和密度的阴影线表现了物体表面的亮度，不同风格的阴影线表现了 物体表面的纹理。阴影线条画被广泛应用于动画、科技文献插图、工业和建筑设 计以及修理手册等。 目前已有很多在网格模型或光滑曲面上绘制阴影线条画的方法，但还没有在 点云模型上绘制阴影线条画的系统工作。目前已有的方法主要有三大类：一类是 基于图像空间的，先得到三维物体在某一视点下的二维图像，再在二维图像中绘 制模型的阴影线条画；一类是基于物体空间的，直接在三维模型上绘制；最后一 类是混合空间的，一部分操作在物体上进行，另一部分操作在图像上进行。每种 方法基本都三个步骤组成：( 1 ) 提取模型的轮廓线；( 2 ) 计算模型表面的方向 场，方向场要反映物体表面的形状信息；( 3 ) 根据亮度确定表面上的单阴影线 和交叉阴影线区域，在这些区的方向场中进行流线跟踪，绘制阴影线。不同的方 法在每个步骤的具体处理过程不同。 本文在前人工作的基础上，系统研究了在点云模型上绘制阴影线条画的工 作。在点云模型上绘制阴影线条画的基本步骤与网格模型相似，也分为三步。但 因为点云模型离散性的特点，每个步骤的具体处理过程与网格模型有很大不同。 本文的阴影线条画生成采用的是混合的方法，主要是在物体空间操作，同时参照 了图像空间的信息。本文的研究内容主要有：对点云模型进行高斯球映射，快速 计算轮廓点；计算轮廓点的可见性；将轮廓点连成轮廓线；计算点云模型的方向 场；优化方向场：计算可见点的光亮度；在方向场中进行流线跟踪来绘制阴影线。 本文的主要贡献： 山东大学硕士学位论文 1 ) 系统研究了在点云模型上绘制阴影线条画的具体操作，总结了目前已有 的工作，对目前的工作进行改进，提出适合本文的算法。 2 ) 提出了在点云模型上判段点的可见性的方法。在利用高斯球进行点的可 见性判断后，仍有少数不可见点被判定为可见点。根据点间的距离特性， 提出了快速去掉这部分不可见点的算法。 3 ) 改进了在点云模型上计算方向场的方法。在计算时，为保证主方向场具 有光滑性，要确定点的主方向的计算顺序。对计算顺序的确定进行了改 进，提高了效率。 4 ) 提出适合在点云模型上进行流线跟踪的算法。包括判断阴影线是否到达 轮廓线或超出绘制范围的方法和阴影线影响范围的概念。要绘制的阴影 线区域可能是不连续的，阴影线影响范围的概念就是为了保证所以的阴 影区域都画上线。 关键字：点云模型；阴影线条画；方向场；阴影线影响范围 i i 山东大学硕士学位论文 a b s tr a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rg r a p h i c s ，i t sg e t t i n gm o r ea n dm o r ea t t e n t i o n t h a tu s i n gp o i n tc l o u dg e o m e t r ya st h ed e p i c t i o no f3 dm o d e l si nc o m p u t e r o no n e s i d e ，i t sv e r ye a s yt oa c q u i r ep o i n tc l o u d o na n o t h e rs i d e ，c o m p a r e dt om e s h m o d e l s ，t h es t o r a g ef o rp o i n tc l o u dm o d e l si sm u c hs m a l l e r n o w a d a y s ，t h ea r e a st h a t s t u d yp o i n tc l o u dr a n g ef r o mr e c o n s t r u c t i o n ，r e n d e r i n ga n da p p l i c a t i o n p o i n tc l o u d h a sb e e na h o ta r e a l i n e a r td r a w i n go fh a t c h i n gi sak i n do fs t y l eo fn o n p h o t o r e a l i s t i cr e n d e r i n g w h i c hu s e sd i f f e r e n tk i n do fh a t c h i n gt oe x p r e s st h es h a p e ，t e x t u r ea n di n t e n s i t yo n t h es u r f a c eo fa3 dm o d e l t h ed i r e c t i o n so fh a t c h i n g e x p r e s st h es h a p eo ft h e s u r f a c e t h ew i d t ha n dd e n s i t yo fh a t c h i n ge x p r e s si n t e n s i t yo nt h es u r f a c e d i f f e r e n t s t y l e so fh a t c h i n ge x p r e s st h et e x t u r eo nt h es u r f a c e l i n e - a r td r a w i n go fh a t c h i n gi s w i d e l yu s e di nc a r t o o n s ，i l l u s t r a t i o n sf o rt e c h n i q u el i t e r a t u r e ，d e s i g ns k e t c ho f i n d u s t r ya n da r c h i t e c t u r ea n dr e p a i rm a n u a l t i l ln o w , t h e r ea r ea l r e a d ym a n ym e t h o d st or e n d e rt h el i n e a r td r a w i n go f h a t c h i n gf o rm e s ha n ds m o o t hs u r f a c e ，b u tt h e r ei sn oi n t e g r i t yw o r kt or e n d e rt h e l i n e a r td r a w i n go fh a t c h i n gf o rp o i n tc l o u dg e o m e t r y e x i t i n gm e t h o d sc a nb e d i v i d e dt ot h r e ec a t a l o g s o n ei si m a g e - s p a c eb a s e d f i r s t ，g e ta2 di m a g eo ft h e m o d e lu n d e rc e r t a i nv i e w p o i n t t h e nr e n d e rt h el i n e a r td r a w i n go fh a t c h i n gi nt h e 2 di m a g e a n o t h e ri so b j e c t - s p a c eb a s e dw h i c hd i r e c t l yu s e s3 dm o d e lt or e n d e rt h e d r a w i n g t h el a s to n e i sh y b r i d ，w h i c hu s e sb o t h3 dm o d e la n d2 di m a g et or e n d e r o nt h ew h o l e ，t h e r ea r et h r e es t e p st of i n i s hah a t c h i n gd r a w i n g ：( 1 ) f i n dt h e s i l h o u e t t eo ft h em o d e l ( 2 ) c o m p u t ead i r e c t i o nf i e l do nt h es u r f a c et h a te x p r e s s e s t h es h a p eo fs u r f a c e ( 3 ) d i s c o v e ra r e a so fs i n g l e - h a t c h i n ga n dc r o s s h a t c h i n go nt h e s u r f a c ea c c o r d i n gt oi n t e n s i t y t h e nt r a c es t r e a m l i n e si nt h ed i r e c t i o nf i e l do ft h o s e a r e a st or e n d e rh a t c h i n g d i f f e r e n tm e t h o dd i f f e r si nt h o s et h r e es t e p s b a s e do nt h ee x i s t i n gw o r k ，t h i sp a p e rs t u d i e dt h ew o r kt or e n d e rl i n e a r t d r a w i n go fh a t c h i n gf o rp o i n tc l o u dg e o m e t r ys y s t e m a t i c a l l y t h em e t h o df o r i i i 山东大学硕士学位论文 r e n d e r i n gf o rp o i n tc l o u di ss i m i l a r 、j v i t l lm e s h h o w e v e r , b e c a u s eo ft h ed i s c r e t e p r o p e r t yo fp o i n tc l o u d ，t h es p e c i f i cp r o c e s so fe a c hs t e pd i f f e r sg r e a t l yw i t hm e s h t h em e t h o du s e di nt h i sp a p e ri sh y b r i d o p e r a t i o n sa r em a i n l yi no b j e c ts p a c ew h i l e a tt h es a m et i m ea c c o r d i n gt ot h ei n f o r m a t i o ni ni m a g es p a c e t h er e s e a r c hc o n t e n t s o ft h i sp a p e ra r e ；g a u s s i a nm a p p i n gb e t w e e np o i n tc l o u da n dg a u s s i a ns p h e r e ；r a p i d c o m p u t a t i o no fs i l h o u e t t ep o i n t s ；v i s i b i l i t yc o m p u t a t i o no fs i l h o u e t t ep o i n t s ；l i n k i n g s i l h o u e t t ep o i n t st os i l h o u e t t el i n e s ；c o m p u t a t i o no fd i r e c t i o nf i e l d sf o rp o i n tc l o u d ； o p t i m i z a t i o no ft h ed i r e c t i o nf i e l d ；c o m p u t i n gt h ei n t e n s i t yo fv i s i b l ep o i n t s ；t r a c i n g s t r e a m l i n e si nt h ed i r e c t i o nf i e l dt or e n d e rh a t c h i n g t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r e s t u d y i n gs y s t e m a t i c a l l y t h es p e c i f i co p e r a t i o n st or e n d e rt ol i n e - a r t d r a w i n go fh a t c h i n gf o rp o i n tc l o u dg e o m e t r y , s u m m a r i z i n ge x i s t i n gw o r k a n di m p r o v i n gs o m e ，a d v a n c i n ga l g o r i t h ms u i t a b l ef o rt h i sp a p e r 2 )a d v a n c i n gar a p i dm e t h o df o rc o m p u t i n gt h ev i s i b i l i t yo fp o i n t s a f t e r c o m p u t et h ev i s i b i l i t yo fp o i n t so fp o i n tc l o u du s i n gg a u s s i a ns p h e r e ， t h e r ea r es t i l laf e wp o i n t st h a ta r en o tv i s i b l ea r ef l a g g e d “v i s i b l e ” a c c o r d i n gt ot h ed i s t a n c eb e t w e e np o i n t s ，w ea d v a n c eaf a s tm e t h o dt o f i n dt h e s en o tv i s i b l ep o i n t s 3 1 i m p r o v i n gt h em e t h o do fc o m p u t i n gd i r e c t i o nf i e l do np o i n tc l o u d g e o m e t r y w h i l ec o m p u t i n g ，t oe n s u r et h er e s u l td i r e c t i o nf i e l d sh a v e s m o o t h n e s s ，w em u s tm a k eac o m p u t a t i o no r d e rf o rp o i n t s w ei m p r o v e t h em e t h o do fm a k et h eo r d e r , w h i c hi n c r e a s e se f f i c i e n t 4 ) a d v a n c i n gam e t h o do ft r a c i n gs t r e a m l i n e ss u i t a b l ef o rp o i n tc l o u d ， i n c l u d i n gd e t e r m i n i n gw h e t h e rh a t c h i n ga r r i v e st h eb o r d e ro f s i l h o u e t t eo r g o e so v e rt h eh a t c h i n ga r e a sa n da d v a n c i n gt h ec o n c e p to f h a t c h i n g i n c i d e n c e ”t h ec o n c e p to f “h a t c h i n gi n c i d e n c e i su s e dt om a k es u r ea l l h a t c h i n ga r e a sh a v e b e e nr e n d e r e d k e y w o r d s ：p o i n tc l o u dg e o m e t r y ；l i n e - a r td r a w i n go fh a t c h i n g ； d i r e c t i o nf i e l d s ；h a t c h i n gi n c i d e n c e i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：吕蓬基 日 期：丝! ! 垒塑 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：墨痊态导师签名：么盈互日 1 1 研究意义 当奎銮兰罂圭兰簦鎏兰 第1 章绪论 近年来，随着计算机图形学的不断发展，计算机显卡处理速度的不断提高和 缓存容量的不断增加，计算机所表示的三维物体越来越复杂，其表面细节越来越 丰富。在这种情况f ，用网格模型作为三维物体在计算机内的表示遇到了一些困 难。首先是数量庞大的多边形占用了非常多的存储空间，在网格模型中，不但要 保存点的三维坐标，还要把点间的线、面关系表示清楚i 其次，网格模型的获取 过程日趋复杂。目前对物体表面进行采样时采样率高，得到的采样点数量庞大， 通常是几十万近百万个点。对于这样数量级的点进行网格化操作，无论在时间上 还是空间上的代价都是非常大的。网格中的多边形数量多而面积小在显示时一 个多边形对屏幕的贡献还不足一个像素。于是人们想到了直接用三维物体表面的 采样点构成的点云模型作为三维物体在计算机内的表示。通过三维扫描设备测量 得到物体表面的三维坐标点集称为点云或点云数据，用点云数据所表示的模型就 称为点云模型。图1 显不了兔子的网格模型和点云模型。 幽l 兔子的两种表示方法。a ：剐格模型；b ：点云模型 早在1 9 7 4 年，c a t m u l l “”就提出模型细分的最终结果就是点表示，点是表示 物体最直接的元素。近年来，点云模型受到了越来越多的重视。与网格模型相比， 点云模型有很多优点。首先其数据存储量小，仅需要保存点的三维坐标，数据结 构简单。其次，点云模型的数据获取简单。随着三维扫描设备技术的革新，扫描 得到的三维数据可靠性大大增加用三维扫描仪获取的模型与场景的三维信息简 单而可靠。第三，对于某些物体及现象的表示，比如火、烟雾、头发、羽毛等， 相对于网格数据而言，用点元素建模不但速度快，而且可以得到更逼真的效果。 山东大学硕士学位论文 对点云模型进行处理时，无需维护拓扑一致性，对某些应削，采用点云模型比m 格模型代价小。目前对点云模型的研究已经涉及到从重建、绘制、性质研究i 0 应 用的各个方面：”l s l l z 0 3 , 点云模型已经成为个热点研究领域。 从2 0 世 2 , 9 0 年代开始，非真实感绘制作为图形学的另外一个分支，飞速发展 起来。真实感强调的是“像”，“和照片一样”，它追求的是物体的精确表不和 场景中光照教果的逼真的物理描述1 。而非真实感强调是人的理解，模拟手绘画 的风格。它是用艺术式的绘制风格来生成物体的艺术或卡通化图像。图2 显示了 大卫头像的真实感和非真实感绘制效果。非真实感绘制有多种小同的风格，阴影 线条画就是其中一种风格之一。它用阴影线来表现物体表面的形状、纹理和亮度 等。图3 显示了克莱因瓶的阴影线条画。阴影线在物体表面的走向表现了物体的 形状。不同粗细和密度的阴影线表现丁物体表面的亮度。物体表面的高光区没有 线条，稍暗的区域是单阴影线，最暗的区域是交叉阴影线。亮度越小，阴影线就 越密。阴影线有不同的宽度，通常用宽而省的阴影线来表示物体上最暗的区域。 小同风格的阴影线表现了物体表面的纹理。阴影线条厕被广泛应用于动画、科技 文献插剖、_ l = 业和建筑设计以及修理 册等。 图2 大卫头像的两种绘制方法。左图：真实感绘制；右图：非真实感绘制 国3 克菜园瓶的阴影线条面 山东大学硕士学位论文 目前已有很多在网格模型或光滑曲面上绘制阴影线条画的方法，但还没有在 点云模型上绘制阴影线条画的系统工作。本文就是基于上述两点考虑，绘制点云 模型的阴影线条画。 在点云模型上绘制阴影线条画与网格模型的过程相似，但由于点云模型缺少 点间的拓扑关系，具体的处理操作要比网格模型复杂，也有很多的不同。点云模 型阴影线条画的绘制要经过以下几个步骤：( 1 ) 生成模型的轮廓线，包括轮廓 点的提取，去掉不可见的轮廓点，将轮廓点连成线；( 2 ) 计算模型表面的方向 场，方向场要反映物体表面的形状信息；( 3 ) 根据点云模型上点的亮度确定单阴 影线和交叉阴影线区域，在这些区域的方向场中进行流线跟踪，绘制阴影线。 1 2 相关研究介绍 自从2 0 世纪9 0 年代“非真实感绘制”这个词被首次提出以来【5 1 1 ，非真实 感绘制因为其独特的艺术表现力受到了越来越多的关注。在诸多非真实感的风 格中，线条画因为其广泛的应用成为最为活跃的领域1 儿2 】【3 1 ，而针对阴影线条画， 无论是静态绘制还是实时绘制都有很多的研究工作。 目前绘制阴影线条画工作多在网格模型上进行，基本分为三种方法：基于 图像空间的 制、基于物体空间的随3 和混合空间的1 。基于图像空间的方法首先在 生成三维模型在视点下的二维图像。s a i t o t 等人h 3 使用g - b u f f e r 己录每个像素 的微分性质，包括像素的深度值和法向量等，像素的每种微分性质都被记录在 一幅图像中。阴影线并不是通过流线跟踪而得到的，而是通过将记录像素的不 同微分性质的图像组合计算得到的。h e r t z m a n n 等人口1 系统介绍了在网格模型生 成阴影线条画的过程，并指出由于网格模型的离散性而造成的与光滑曲面的不 同。首先根据网格中共享一条边的两个面的朝向确定位于轮廓线上的边，将轮 廓线分段并判断各段的可见性；然后计算用来做流线跟踪以生成阴影线的方向 场，这步是通过对主方向场的修正完成的；最后在方向场中做流线跟踪生成阴 影线。混合空间的算法是在处理时用到了原始模型本身及其在某视点下的二维 图像。r s s s l 等人1 首先在原始网格中计算点的主方向，然后生成在视点下的二 维图像，图像中的每个像素中记录着点的微分信息，阴影线是通过在二维图像 中做流线跟踪生成的。 3 山东大学硕士学位论文 阴影线可以表现物体表面的纹理信息，这是通过使用不同风格的阴影线实 现的。所谓不同风格，是指阴影线的走向、长短、粗细和交叉等，用“笔触纹 理这个概念来描述。纹理是表现物体表面特性的一个非常重要的信息，如何 用不同的笔触纹理来生成不同的阴影线以满足用户表达纹理信息的需要也成了 一个研究热点。s a li s b u r y 等人口1 生成了一个交互系统，以协助用户生成自己想 要的风格的阴影画。输入一幅灰度图像，系统首先根据灰度值得到图像中物体 的轮廓线：然后用户在系统存有的笔触纹理中选择自己需要的风格，系统会根 据图像的灰度值自动生成阴影画。 生成阴影线条画的过程可以是自动的3 ，也可以是半自动的陆1 。自动的绘制 方法完全不需要用户的参与，给系统输入一个模型，系统会根据目前视点的位 置和光照生成一幅线条画。因为非真感绘制主要是将人对三维物体的理解绘制 成二维图像，所以在某些时候用户的参与也是必要的。r s s s l 等人嘧1 先将三维物 体的二维图像根据主方向场的走向来分区，在不同的分区中分别绘制阴影线。 这个分区的过程没有一个统一的标准，纯粹是一个艺术的过程，所以用户的参 与是必要的。 为了满足游戏、交互式技术插图和艺术虚拟环境等的需要，实时阴影线条 画绘制的研究也已经开始阳引。要随着视点变化实时生成阴影线条画，不让人感 觉到画与画之间有明显的跳跃，必须满足两个条件：是每分钟生成的画数必 须达到人眼感觉到画面连续的最小帧数；二是画面颜色必须是连续、渐变的， 人眼不能感觉到画面颜色的突然变化，这两个方面分别是时间连续性和空间连 续性。针对三角网格模型，为了满足同实时性的要求，p r a u n 等人h 3 提出“t a m ” ( t o n a la r tm a p ) 的概念。它是指同一风格的阴影线组成的图的集合，每个图 中阴影线的密度不同，在物体表面上时可以表现不同的亮度。从第一幅图到最 后一幅，其中的阴影线越来越密，并且后一幅图中的阴影线完全包含前一幅图 中的阴影线。在实时绘制时，以三角形为单位处理，先在网格的三个顶点根据 两幅相邻的阴影线图混合出顶点的颜色，然后对顶点的颜色进行插值得到三角 形面的颜色，这样保证空间的连续性。这是一个纹理混合的过程，可以通过计 算机硬件快速完成，从而保证了时间的连续性。 近年来，随着点云模型研究领域的扩大和深入n o m l m 2 m 副，针对点云模型的 4 山东大学硕士学位论文 非真实感研究也已经开始n 4 1 5 1 。x u 等人钔和z a k a r i a 等人n 础都介绍了点云模型轮 廓线的提取。对于点云模型轮廓线的提取，由于点云模型缺少拓扑连接关系， 从而与传统的网格模型有很大区别。x u 等人n 钔基于绘制点云模型的传统q s p l a t 方法n 制，通过对模型的两遍绘制提取轮廓线，这是一个物体空间的算法，并可 以与目前的绘制机制相结合。z a k a r i a 等人n 5 1 提出了一个物体空间与图像空间相 结合的算法，根据图像中相邻的像素判断可能与一点连接的候选点，再根据候 选点与该点的空间距离选择最佳的点连线。 1 3 本文的工作和组织结构 本文研究了在点云模型上绘制阴影线条画的过程，其过程分为三步：提取 轮廓线、计算方向场和绘制阴影线。本文的算法是一个物体空间和图像空间相 结合的自动算法。本文对每个步骤现有的主要方法进行了研究，包括针对网格 模型的方法，在快速提取轮廓点、优化方向场和绘制阴影线的算法中提出了自 己的见解。 阴影线条画是一幅灰度图像，所以只需要知道点云模型中点的三维坐标即 可绘制阴影线条画。点的法向信息是必需的，本文不要求点云模型带有法向信 息，所以先给出计算法向的方法。由于点云模型中点的个数多，提取轮廓点时 必须有加速算法。仅仅通过法向判断出的轮廓点中会有一些“伪轮廓点”，也就 是不可见的点被判断为轮廓点，所以还要有进一步的可见性判断来剔除不可见 的轮廓点。本文使用高斯球来加速轮廓点的判断，同时找出单阴影线和交叉阴 影线区域内的点。去掉不可见的轮廓点后将点连成线。然后计算主方向场，为 保证方向场的局部光滑性和全局光滑性，要确定计算方向场时点的计算顺序以 及平滑方向场。为减少计算量，只计算阴影线区域内的点。最后在主方向场中 进行流线跟踪绘制阴影线路。通过一系列的参数来控制阴影线的绘制过程，因 为需要画阴影线区域不一定是连续的，所以提出阴影线影响范围的概念以保证 在所有的阴影区域内画出线。 第二章介绍提取轮廓线的方法。因为点的法向信息是提取轮廓点的基本， 本章首先介绍了如何计算点云模型中点的法向量，然后介绍提取轮廓线的方法， 包括利用高斯球快速计算轮廓点、可见性判断及将点连成线。第三章中介绍主 山东大学硕士学位论文 方向场的计算，包括主方向场的定义及相关的优化方法。第五章介绍阴影线的 绘制，首先介绍控制阴影线的各种参数及计算方法，然后介绍如何在点云模型 上进行流线跟踪。第五章总结本文的工作，并提出下一步的工作。 6 山东大学硕士学位论文 第2 章点云模型上点的可见性判断及轮廓线生成 本章将给出点云模型与高斯球映射的方法，建立高斯球的八叉树层次结构， 根据八叉树结点的可见性通过一次遍历高斯球八叉树得到轮廓点、单阴影线和交 叉阴影线区域的点，判断点的可见性，将轮廓点连成轮廓线。 2 1 轮廓点的定义 轮廓线是物体上可见部分与不可见部分的分界线。从轮廓线出发，朝背对视 点的方向走，到达的点都是不可见的；朝面向视点的方向走，到达的点是可见的。 轮廓点就是点云模型上处于轮廓线位置的点。 设视点为c ，点云上一点p 的法向为，根据视点与法向的关系，可以得 到： 若( c p ) n 0 ，则p 是可见点； 若( c 一尸) n 2 0 ) t r e e h e i g h t + + ： 平均一个叶结点内点的个数不多于2 0 。角点的坐标由经度、纬度及“厚度” 计算，分别用l o n g 、肠f 及，表示这三个值，角点坐标( z ，y ，z ，w ) 的计算公 式为： z = c o s a t c o s l o n g c o s r y = c o s a t s i n l o n g z = c o s 励a t c o s l o n g s i nr w = s i n a t ( 2 ) 根据点云模型上点的法向计算其高斯映射点所在的八叉树叶结点。因 为是在透视投影下计算，所以要将点云模型上点的法向n = ( ，n ，n z ) 变换为 ( ，y ，：，一( 只札+ 0 n y + e ；) ) 并规范化后再计算其高斯映射对应点的经 度、纬度及“厚度”值。根据上面的由经度、纬度及“厚度”值计算角点坐标的 公式，利用反三角函数公式，很容易得出经度、纬度及“厚度”值，从而确定高 斯映射对应点所在的八叉树结点，也就是确定了点云模型上的点所在的八叉树结 点，算法在八叉树的叶结点内存储点在点云模型存储文件中的顺序索引。 ( 3 ) 从八叉树的根结点开始，在视点( c ，c y ，e ，1 ) 下，计算结点的八个角点 的坐标与视点( q ，c y ，c ：，1 ) 的点乘积，判断该结点的可见性。若所有的点乘积都 大于零，则该结点是完全可见的，定义该结点的可见性为0 ，该结点内所有的点 云模型上的点都是可见点：若点乘积有正有负，则该结点是部分可见的，定义该 结点的可见性为1 ，该结点中存在轮廓点：若所有的点乘积都小于零，则该结点 1 2 山东大学硕士学位论文 是完全不可见的，定义该结点的可见性为2 ，该结点内所有的点云模型上的点都 是不可见点。 ( 4 ) 利用广度优先算法搜索整个八叉树，在可见性为l 的结点中寻找轮廓点。 在可见性为o 和l 的结点中寻找交叉和单阴影线区域内的点。具体搜索过程如下： 4 1 生成一个队列的对象，将八叉树根结点放入队列中 4 2w h i l e ( 队列不为空) 4 2 1 取出队头结点，判断该结点的可见性； 4 2 2 若可见性为2 ，则跳出本次循环，开始下一次循环。否则，判断该结 点是否是叶结点。 4 2 3 若不是，将该结点的八个子结点放入队列中，跳出本次循环，开始下 一次循环。否则，判断叶结点的可见性。 4 2 4 若叶结点的可见性为2 ，则跳出本次循环，开始下一次循环。 4 2 5 若叶结点的可见性为1 ，则逐个取出其中的点，用点的法向 ( ，z ) 与视点( c 。，c ，c ：) 作点乘积。若积等于零，则这个点是 轮廓点；若不等于零，则判断是否大于零，若大于零，再判断与区间 ( 办m i n , h 。) 的关系，来确定是不是单或交叉阴影线区域内的点。 4 2 6 若叶结点的可见性为o ，则逐个取出其中的点，用点的法向 ( ，z ) 与视点( c ，c ，c ；) 作点乘积。若大于零，再判断与区间 ( h m i n , h 。瓠) 的关系，来确定是不是单或交叉阴影线区域内的点。 整个算法的第( 1 ) 和( 2 ) 步可以读入点云模型时处理，点所在八叉树叶 结点位置不随视点而变化。每一次视点变化都要重新执行第( 3 ) 和( 4 ) 步。因 此，可以将第( 1 ) 和( 2 ) 步作为一个预处理过程，一次执行就可以保证以后所 有绘制过程的应用，这对于实时阴影线条画的绘制有很大意义。 2 5 可见性计算 在2 1 节中，我们用点到视点的向量与点的法向的点乘积来判断点可见性， 这种方法会将从视点实际上看不到的点判断为可见的，这在轮廓点的检测中最为 明显。例如在物体的背面，也可能存在点乘积等于零的点，这些点由于物体的自 遮挡，应该是看不到的；若模型中存在平面，而平面上点的法向恰好与视点垂直， 则平面上所有的点都被判断为是轮廓点。如图6 的兔子模型就显示了这两种情况。 些耋查兰至圭兰堡鎏圣 图6 在一视点下，单纯用法向点乘积判断轮廓点的方法使兔子上本 来看不到的点也被检测为轮廓点 在兔子右耳朵的下部被头部遮了，但下部的点仍然被检测为轮廓点，这部分 点其实是看不到的。兔子的底座是个平面，此平面上的点都被捡钡0 成是轮廓点， 其实只有最外圈的点才是可见的轮廓点。所以必须进一步判断点的可见性，去掉 根据法向点乘积认为是可见但实际上由于物体的自遮挡而看不到的点。 2 51 光线跟踪算法 光线跟踪算法是计算机图形学中应用最广泛的可见性判断算法。它的原理 是，对于要判定的一点，从视点发出一条到该点的射线，计算从该点到视点的线 段与模型的交点著存在交点，说明模型上有其它的点比该点离视点更近从视 点是看小到该点的。反之，若没有交点，该点对于视点来说就是可见的。在网格 模型上应用该算法最方便网为网格模型是由一个个面组成的封闭结构，很容易 判断线段与面的交点。但对于点云模型来说，使用光线f h 踪算法遇到了困难。 点云模型是由离散点组成的，点不可能完全覆盖整个表面点之间是有空隙 的，从而使模型表面存在很多的空洞。在做光线跟踪时，若从视点到某个不可见 点的射线恰好穿过面上的空洞，这样在求交时就得不到交点，从而误认为该点是 可见的。为了解决空洞问题，通常有两种解决方法，一是将光线变“粗”，相当 于用一个圆柱与点云上的点求交，圆柱的底面半径必须大到可以覆盖点间的空洞 ；二是将点扩大，以填补表面上的空洞，有将点扩大为圆盘1 和球两个方法。 这样的方法对点的采样率有较大的要求，要求达到一定的密度或者符台尼奎斯特 定理；将点扩大成圆盘或球时确定点的半径也是一个复杂的过程。将点扩大为圆 山东大学硕士学位论文 盘后，相邻点的圆盘会有覆盖，可能会将可见的点判断为不可见的。将点云进行 曲面重建后再求交也是一种填补空洞的方法。最近经常用的还有s p l a t g 撇， 这些方法通常用在点云模型的真实感绘制中，也可以用在点的可见性计算中。 2 5 2 利用反演变换判断可见性 k a t z 等人啪3 提出了利用反演变换判断可见性的方法，这种方法不需要曲面重 建、对点的采样率也没有任何要求。其原理可用图7 表示。 图7 利用反演变换判断可见性的原理示意图 图7 是用二维物体来演示算法的原理，三维物体的判断原理与二维物体 相似。图7 中要判断圆内的猫在位于圆心位置的视点下的可见点，圆是猫的包围 圆。首先通过反演变换将圆内的猫上的点变换到圆外，然后求圆外的点与视点组 成的点集的凸包。在位于凸包上的点中去掉视点得到的点集就是可见点集。判断 三维物体的可见性时，只要将包围圆换成包围球即可。利用反演变换求点云模型 可见点集的算法过程如下： ( 1 ) 将点云模型上的点做如下的反演变换： p t 诌+ 2 ( r - p i 胁南 尺是以视点为球心的模型的包围球，这个变换叫做球形变换( s p h e r i c a l f l i p p i n g ) ，直观的理解就是将包围球内的点变换到视点与该点的连线上球外的 一点，点与视点的距离越近，变换后的点与视点的距离越远。 ( 2 ) 计算变换后的点p ，与视点组成的点集的凸包，视点一定是凸包上的 山东大学硕士学位论文 点，除视点外其余凸包的上的点对应的变换前的点云模型上的点就是可见点。 这种反演变换后利用凸包计算点的可见性的方法对点的采样率没有特殊的 要求，没有将点扩大为圆盘或球时计算半径的复杂过程，也不用对点云模型进行 曲面重建，这是纯粹地以离散的观点来解决离散问题的方法。这个方法最复杂的 计算过程是凸包的求解，b a r b e r 等人m 1 的经典o u c i c k h u l l 算法可以在o ( n l o g n ) 时间内完成凸包的求解。 在图7 中，圆恰好完全包围住物体，实际应用中，包围圆或球的半径要大于 恰好包围的半径。不同的半径影响判断的准确性。较小的半径会将实际的可以看 到的点判断为看不到，而较大的半径会将实际的看不到的点判断为可以看到。 k a t z 等人乜7 1 根据一个点不可能同时在两个相反的视点下可见的原理，自动计算半 径。首先确定另外一个视点，这个视点位于原来视点与模型中心连线上并且与原 来视点相对。然后计算半径，半径要使在这两个视点下的可见点集合的不相交点 数达到最大。 2 5 3 本文的可见性判断算法 在本文中，通过遍历高斯球的八叉树已经将大部分不可见点去掉，只有一少 部分的不可见点被判断成为可见的了。传统的点云光线跟踪算法对点的采样率要 求高；利用反演变换判断可见性的方法需要计算大量点的凸包，因为已经去掉了 大部分可见点，只为了去掉少量不可见的点而计算点云模型中所有点的凸包，这 个代价是非常大的。本文对点的可见性判断采取的是光线跟踪的办法，与将光线 “变粗”相似，只是本文中不计算点与光线的交点，是通过点到光线的距离来代 替求交计算的。算法的原理是：从要判断的点到视点连成一条线段，在该线段不 断变粗的过程中，若该点是可见点，则碰到的点都是该点附近的点；若该点是不 可见点，则会碰到距离该点很远的点。算法的分为如下的步骤。 ( 1 ) 建立点云模型的空间网格剖分结构。就是将点云模型的空间包围盒进 行x ，j ，z 三个方向的剖分，三个方向上的步长是相同的，也就是均匀剖分，形 成的每个小盒子三个边长相等。每个盒子中记录着点云模型中位于该盒子内的 点。 ( 2 ) 对于通过高斯球八叉树遍历得到的轮廓点、单阴影线区域和交叉阴影 1 6 山东大学硕士学位论文 线区域内的点( 用只表示) 执行以下步骤： ( 2 1 ) 从视点出发发出一条经过点只的射线。 ( 2 2 ) 求线段与点云模型包围盒的交点，若没有交点，则该点是可见 点，取一个点，转到( 2 1 ) 。若有交点，则计算与线段相交的所有小盒子。 通过下面的方法得到与线段相交的所有的小盒子：首先根据光线与包围盒 的交点p 得到第一个小盒子：沿着光线的前进方向将p 移动小盒子的边长 的距离，得到新点尸，计算p 。所在的小盒子；然后再从p 出发沿光线的 前进方向前进同样的长度，判断新点所在的小盒子；如此继续，直到到达只 所在的小盒子。 ( 2 3 ) 与线段相交的每个小盒子及其周围2 6 个小盒子中的点到线段的 距离，记录距离小于幽的点。 ( 2 4 ) 对( 2 3 ) 中计算的所有与光线距离小于咖。的点，计算到只的 距离，若存在距离大于d v 2 的点，则说明有一个距离只较远的一个点，也 就是说与只不在同一个区域内的点距离光线比较近，从而说明是不可见 的；若不存在这样的点，则说明只是可见的。 在对点云模型进行网格化剖分时，要使网格的边长大于等于以，这样 才能保证与光线距离小于幽的点都在光线相交的小盒子及其相邻的2 6 个 小盒子中。咖，的大小要至少可以使光线填补点云模型上的空洞，即使穿过 可见点的光线和周围的点有交点也是允许的。她的确定对算法的准确性很 大影响，特别是对于扁平的模型来说。设吐是点云模型中相邻点间的最大 距离，即便对于扁平的模型来说，为了从视觉上区分点云上的两个相邻的 面，不同面上点间的距离相对于西来说也是非常大的，对于稠密的点云模 型，d l 非常小，可以取咖：= k z d l ，k ：可以取一个一位或两位的较大的正 整数。 1 7 山东大学硕士学位论文 2 6 轮廓线的提取 在网格模型中，轮廓线是通过检查每一条边得到的馏们口刨。在网格中，每条边 都由两个面共有，若其中的一个面是前向面，即面的法向量与视点向量的点乘积 大于零，另一个面是后向面，这条边就是轮廓线。在前面第3 1 节中，定义轮廓 点是视点到点连线与该点法向量垂直的点，通过前向面和后向面得到的边的两个 端点并不一定是轮廓点，于是便有了通过点的可见性在边上插值得轮廓点、然后 再将一个多边形内的轮廓点连成线的方法3 。这些方法都是基于边关系的。在点 云模型中，点之间是没有边关系的，其轮廓线的提取通常是在得到轮廓点的基础 上再通过一定的方法将点连成线5 3 。基于点云的绘制过程，通过两次绘制而得 到轮廓线的方法也不需要先计算轮廓点n 制，在本文中，点云模型的绘制并不是必 须的，点云模型的显示只是为了让用户确定一个要绘制的画面，在这种情