（计算机应用技术专业论文）基于点云的三维建模技术及其应用研究.pdf

西南科技大学硕士研究生学位论文第j 页 摘要 目前，计算机图形学和虚拟现实技术已经广泛应用于逆向工程、计算 机动画、虚拟手术等各个方面，三维建模技术是其中的核心工作。本文主 要研究三角网格建模、点云建模及其应用。 提出了基于点云的三维三角网格划分算法，它不需同二维划分方法一 样，对点云对应的自由曲面分片投影，而利用网格扩展、边界环分裂和封 闭，能生成非封闭曲面等各种复杂曲面。 提出了一种动态l o d 算法，增加了边界点的处理，并规定边界点只能 合并到边界点，内部点可以合并到内部点或边界点。 提出了一种动画共享的方法。给人物的各个关节指定一个位置，所存 各关节的位移都针对此起始位置，需共享的动画数据单独存储。 为了实现不同逆向工程系统之问数据的共享，采用x m l 语言实现了三 角网格的存贮和调用。 发展了一种油彩飞戳法曲面重建中的子采样算法，采样数据具有法向 矢量和空间信息。用贪婪法选择曲面，用整体优化法消除漏洞，用分段线 性f 7 持续逼近输入数据重建益面。 建立了一种利用点采样对高弹性、高塑性物体进行动面模拟的新方 式。使用采样分裂和聚合以适应动画中采样密度的变化，并将弹性力学中 的理论应用到三维动画中。 最后，建立了数个模块，对上述算法进行了验证。 关键词：虚拟现实建模动画l o d 西南科技大学硕士研究生学位论文第f j 页 a b s tr a c t t h et e c h n o l o g yo f c o m p u t e rg r a p h i ca n dv i r t u a lr e a l i t yh a sb e e nw i d e l y u s e di n r e v e r s i n ge n g i n e e r i n g 、c o m p u t e rc a r t o o n 、v i r t u a lo p e r a t i o n t h e t e c h n i q u e o fm o d e l i n gi st h eh a r d p a r t o fv r t h ep a p e ri s f o c u s e do n m o d e l i n g b a s e do nt r i a n g l em e s ha n d p o i n tc l o u d a ne f f e c t i v e t r i a n g u l a t i o na l g o r i t h m f o rs c a t t e r e dd a t a p o i n t s i s p u t f o r w a r di nt h i sp a p e r t h i sa l g o r i t h ms o l v e st h ep r o b l e mt h a td a t ap o i n t sm u s t b e p a r t i t i o n e d f o r m u l t i p r o j e c t i o nr e a l i z e db yt r a d i t i o n a l 2 dt r i a n g u l a t i o n m e t h o d s b yb o u n d a r yl o o pe x t e n d i n g ，s p l i t t i n g ，c l o s i n ga r es u m m a r i z e d ，t h e a l g o r i t h mc a nd e a lw i t hs c a t t e r e dd a t ao fd i v e r s i f i e ds u r f a c e an e wd y n a m i cl o da l g o r i t h mi s g i v e na l s o i nt h e n e wa l g o r i t h m ， b o u n d a r yp o i n t sc a no n l yb ec o m b i n e dt ob o u n d a r yp o i n t s ，i n s i d ep o i n t sc a n b ec o m b i n e dt oi n s i d ep o i n t so rb o u n d a r y p o i n t s an e wm e t h o df o rs h a r i n g3 ds k e l e t o na n i m a t i o n si s a c h i e v e d e v e r y j o i n to f t h er o l ei sm a r kp o s i t i o n ，t h ed i s p l a c e m e n ta m o u n ti so n l yd e t e r m i n e d b yt h ep o s i t i o n t h ea n i m a t i o nn e e d e dt ob es h a r e di ss t o r e di n d e p e n d e n t l y c o n s i d e r i n g t h e m u l t i p l ea p p l i c a t i o n s o f t r i a n g l e m e s hi nr e v e r s e e n g i n e e r i n g ，at r i a n g l em e s hs t o r a g ef o r m a tu s i n gx m l i sp u tf o r w a r d i nt h i s p a p e r ，a n e wr e s a m p l i n g t e c h n i q u ef o r d e n s ep o i n tc l o u d si s p r e s e n t e d i nt h ea l g o r i t h m ，s p l a t sc a nb es e l e c t e df r o mt h ei n i t i a ls p l a t sb ya g r e e d ym e t h o d ag l o b a lo p t i m i z a d o nm e t h o dc o m p u t e sa nm i n i m u ms e to f s p l a t s t h a tc o v e r st h ee n t i r es u r f a c e t h es u r f a c eo fm o d e l c a nb e r e c o n s t r u c t e df r o mt h e i n p u tp o i n t c l o u d sw i t hf l p i e c e w i s e l i n e a r c 1 c o n t i n u o u sa p p r o x i m a t i o n am e t h o di sp r e s e n t e df o ra n i m a t i n go b j e c t sw i t hs t i f fe l a s t i ca n dh i g h l y p l a s t i c t h e s u r f a c eb a s e do n p o i n t s a m p l e d c a nb e s p l i t a n d m e r g e dt o d y n a m i c a l l ya d a p tt h es u r f a c es a m p l i n gd e n s i t yd u r i n gs i m u l a t i o n t h et h e o r y o f e l a s t i c i t yi su s e di nt h es i m u l a t i o n a tl a s t ，s e v e r a lm o d u l e sa r ec r e a t e dt ov e r i f yt h e s ea l g o r i t h m s k e y w o r d s ：v i r t u a lr e a l i t y ；m o d e l i n g ；c a r t o o n ；l o d 独创性声明 本人声明所呈交的论文是找个 在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 已经发表或撰 写过的研究成果，也不包含为获得西南科技大学或其它教育机构的学位或证书丽使用过 的材料。与我一同工作的同志对本研究所傲的任何贡献均已在论文中作了明确韵说明并 表示了谢意。 签名：考虹鞍僻 日期：川占 关于论文使用和授权的说明 本人完全了解西南利教苷鸹匀器揉留、使用学位论文的规定，即：学校有权保留学 位论文的复印件，允许该论文被套阕和借圈；学校可以公布该论文的全部或部分内容， 可以采用影印、缩印或其他复制手段保存论文。 签名嘭铲彳导师签名：涤箩噍川t 州 西南科技大学硕士研究生学位论文第1 页 1绪论 1 1 课题来源 本论文的课题来源是中国工程物理研究院院外基金项目“交互式三维建 模及物理仿真研究”和“三维场景真实感技术研究”和四川省科技厅青年软 件创新工程资助项目“基于点云的交互式曲面编辑系统”和“基于p 2 p 模式 的网络游戏开发平台研究与实现”。 1 2 研究内容 项目“交互式三维建模及物理仿真研究”、“三维场景真实感技术研究” 的目标是采用虚拟现实技术，丌发出一套基于p c 的交互式建模工具和图形 引擎。 在此项目中，主要是对三维建模方式及其在动画中的应用进行了探讨。 主要研究内容有： ( 1 ) 为了对有复杂曲面的物体建模，对点云的三维三角网格划分进行 了研究： ( 2 ) 为了使实验平台可导入不同格式的三维网格模型，采用x m l 语言对 三角网格的存贮和调用进行了研究； ( 3 ) 为了实现引擎中对场景显示的要求，在h o p p e 可逆递进网格算法的 基础上，对l o d 算法进行了研究： ( 4 ) 将项目中的三维引擎应用于三维动画，以验证其有效性。为提高 动画显示速度，对骨骼动画进行了研究。 项目“基于点云的交互式曲面编辑系统”是将三维激光扫描仪扫描形成 的三维稠密点云数据，经过采样形成流形曲面，并可在曲面上自由绘画，使 其具有绘画般的纹理效果，同时三维曲面可以自由变形，但没有失真。本系 统包括有效的层次表示、高质量的纹理过滤、精确的可视化计算及可灵活平 衡速度和质量的模型重构，并且系统在渲染复杂物体时，可用硬件加速。 在此项目中，主要对基于点云的三维建模技术及其在逆向工程和动画中 的应用做了一定探讨，所做的主要工作有： ( 1 ) 因为基于点云的曲面重构在逆向工程中占有重要地位，所以对基 于点云的优化子采样算法进行了研究，可在项目“基于点云的交互式曲面编 西南科技大学硕士研究生学位论文第2 页 辑系统”中使用新的建模方式； ( 2 ) 为了证明实验平台有效性，对点采样表面的动面模拟进行了研究。 1 3 国内外现状 目f i ，计算机图形学和虚拟现实技术已经广泛应用子科学、社会生活的 各个方面，如逆向工程、虚拟制造、娱乐、计算机动画、虚拟手术等各个方 面。它的主要工作是将现实生活中的物体转变成可在计算机上显示的三维虚 拟物体模型，并可用各种方式与人交互，给人一种直观感觉。其中，三维建 模技术是其中的核心工作。 目前主要的三维建模方式，有图像建模、多边形建模( 包括三角网格建 模) 、点云建模等。 图像建模： 此方式建模快捷且能很好地保留物体的可视化特性，但算法较复杂。 早期三维图像建模是采集图像上的点形成点云，然后将点云形成网格， 再处理三维模型。为此彦生不少建模方式，如内含曲面、n u r b s 、再分曲面 等，都可以产生复杂形状的三维模型。t a l is m a n 的可视化渲染系统中使用 了相似的方式，但在多边形上映射物体常常会产生可视化错误，且不允许有 视觉误差。 为鳃决这个问题，一些方式增加图像象索的深度信息，称为层次替代或 层次深度图像。所有这些方式都没提供一种完整的建模方式，可以从任意视 点对模型进行光照和渲染。 许多图像建模方式不需要几何和深度信息。例如视点插入方式， q u ic k t i m ev r 可以从一系列二维图像中形成视点。光域方式通过四维或更 高维的位置函数，描述物体或场景的光线情况，但要提前存储大量数掘。所 有这些方式通过视点方式来建立物体模型，但视点方式建模方式有时并不有 效，尤其表现有运动物体的动态场景、材质变化、光源的强度和方向变化时 效率更低。 多边形建模( 包括三角网格建模) ： 通过三角网格建模可用较少的计算量获得较好的建模效果，所以在逆向 工程、计算机动画、电影特效中都有较好的应用。 但该方法也有缺点： ( 1 ) 建立生物体模型需要的三角形比较多。如a l v yr a ys m i t h 的生物 西南科技大学硕士研究生学位论文第3 页 体模型需要8 千力1 个多边形。处理许多小三角形也产生了带宽瓶颈和过多的 浮点运算。 ( 2 ) 将模型上的点形成网格，必须存储各点之问的拓扑关系，这在一 定程度上降低了效率。 ( 3 ) 网格建模将曲面表示和纹理操作用两种方法实现，在表现模型时 叉需将二者结合起来，由于精度原因，会造成信息缺失，影响模型效果。 ( 4 ) 网格建模在表现不同细节时，需用l o d 技术及多层次存储，但局部 参数化表面片无法达到最优化的曲面片设计和纹理帖图，且不连续的曲面片 边缘很难处理。用单一分辨率的纹理来表现不同细节时，难以达到较好效果。 点云建模： 摄近几年，随着三维激光扫描仪的发展，已经可以通过点云建立真实物 体的三维模型，这种三维模型主要应用在电子商务和游戏中。目前基于点的 三维建模方式还比较复杂，相关的去噪、绘图、随机变形等的研究也不多。 l e v o ya n d 舳i t t e d ”1 将点做为三维建模和渲染的原始数据。他们定义 了基于点的渲染流程，研究了用点采样建立三维模型的方式。s z e l is k i 和 t o n n e s e n ”1 使用定向粒子来建模。单独的点采样与交互粒子相联系，并在交 互时定义它们的运动路径。w i t k i n 和h e c k b e r t 。”的动态采样用来处理分布 不均的采样分布。实验表明，这种方式适用于表面平滑、填补小孔洞，但粒 子模拟的计算价值比较太。l ir i s e n 使用af a nc l o u d “3 来表示基于点采样 的建模和渲染。这种方式通过三角扇( t r i a n g l ef a n ) 表示点采样的局部邻 接点，三角扇通过计算特定的邻接联系得到。这种方式的动态重采样较难执 行。许多研究人员已经使用m l s ( m o v in gl e a s ts q u a r e ) 表面用于点云建模。 a 1e x a 等”1 使用过采样和欠采样基于点的模型表面，建立了一套高效的渲染 系统。f l e i s h m a n 等”3 扩展了他们压缩和编码的工作。文献 7 中介绍了一种 在m l s 表面使用光线跟踪的高效渲染算法。 1 4 课题意义 1 4 1 课题的理论意义 目前曲面表示从最抽象的层次讲主要有两种方法：隐含式表示和参数化 表示。 隐含式表示( 如层次集和光线函数) 有比较简单的代数结构，表面被定 义为三维梯度场的零集，它可通过加权累加函数得出。用这种方式，可容易 西南科技大学硕士研究生学位论文第4 页 表示较复杂拓扑结构的表面，并可通过重构保证表面的全局一致性。模型变 形或者拓扑变化可通过改变函数的权重因子很容易得实现。然而，此种方式 用柬有效渲染和精确建模单独的点则有一定问题，因为单独的点仅能通过光 线跟踪得到。 参数化表示( 如三角网格法、样条曲线法、再分曲面) 的理论基础是从 二维域向三维域投影，它的代数结构非常复杂且和表面复杂度有关。因为点 采样可以通过评估参数表面函数获得，渲染效率比较高，也可以通过调整参 数空间的表面函数很容易得纠j 下曲线上的折痕。但当有较大的变形或拓扑变 化时，则需要改变定义域，以防出现失真或不连续的现象。n u r b s 曲面因为 每个样条片可高质量估计曲面，可使用较少的图元表现较复杂的形状。n u r b s 要实现严格的全局一致性约束，但将不同的曲面片统一在一致的曲面中比较 困难。多边形网格法重构曲面可通过一系列具有一致性邻接图的顶点来定 义，重构过程比较简单，但需要较多的图元来保证几何精度。三角网格模型 可通过改变顶点位置在一定程度内改变模型形状。但如果失真太大或表面拓 扑结构被改变，必须更新网格间的联系，同时要严格保持表面整体一致性以 保证表面结构，这使表面操作效率非常低。 随着扫描设备分辨率的提高，用于三维建模的几何数据越来越复杂，最 近一个模型可以有数十亿个扫描点”1 。然而目静的建模算法运算效率较低， 如d e l a u n a y 三角化的复杂度就为d 【旷) ，n 是扫描点的个数。基于点的建模不 需要全局统一结构，且每个图元上花费的运算代价较少，所以用基于点的渲 染算法来显示复杂表面效率就非常高。 与传统的网格建模方式不同，本文建立的p o i n t 3 d 系统采用的是点云建 模。它充分利用了参数化表示和隐含表示的长处，将三维模型的形状用点云 表示。因为点云的一致性要求最小，重构变形曲面也非常简单有效。点云不 是表面固定、静态的表示，而是当曲面变形时因时面异的动态采样。另外引 入隐含表示中的有向距离函数，可使点云模型的布尔操作和碰撞检测变得比 较简单。它将三维激光扫描仪形成的稠密点云经过采样，形成一定面积的投 影圆形或椭圆形曲面片，再由表面泼溅法形成三维表面。 此方法主要的优点是： ( 1 ) 点云建模一致性要求最小，重构变形衄丽也非常简单有效。它 可经采样、投影形成曲面，曲面单元中包括点的空间位置、纹理、阴影等 信息。点云建模不需全局统一结构，不需建立三角网格那样的拓扑关系， 从而大大降低运算量，提高了效率。 西南科技大学硕士研究生学位论文第5 页 ( 2 ) 曲面表示和纹理都是通过采样实现，能非常好的表现二者的细 节，防止产生网格建模的纹理扭曲、失真等现象。 ( 3 ) 对不同层次的细节只需要增加采样数量，不需多层次存储结构。 1 4 2 课题的实际意义 最近几年，随着三维激光扫描技术的发展，生成的三维模型越来越复杂， 模型生成、存储、传输、处理和更改所需的代价越来越大。因此迫切需要发 展一套有效的算法，来解决这些问题。 p o i n t 3 d 系统所使用的是基于点的建模，它介于几何建模和图像建模之 间，运算速度高，渲染效果好。 基于点的建模模块可生成各种软组织的精确模型，如人脸、完整的人体 模型、人的骨骼等其它建模方式难以生成的模型，还可生成各种具有流型表 面的复杂构件的精确模型，如车辆的覆盖件、复杂模具、艺术品等。其渲染 模块可在模型上进行绘画级的渲染。这使该系统非常适用于产品设计( 尤其 是外观设计) 、电子商务、艺术品和文物的虚拟展览等场合。随着研究的深 入，该项目也将提供模型塑性变化模块，可用于生成活动的人体、溶化的物 体等，这将使该系统在实时交互式游戏、虚拟外科手术、电影特技、仿真领 域也会有广阔的应用前景。 尤其其中的噪声数据去除模块可直接应用在三维扫描仪的模型后续处 理中。 该系统可在微机上运行，系统配置要求不高，是一个低成本的三维模型 生成平台。 1 5 文章结构 本文共分四大部分，第一部分是第二章，主要对各种建模方式进行综述， 从而选择基于点云的三角网格剖分法和面素法，做为本文主要的建模方式； 第二部分包含二至六章，是基于九院的项目，研究三角网格建模及其应用： 第三部分是七、八章，它是基于青创项目，研究利用点云采用油彩飞溅法建 模及其应用。第四部分是第九章，对所建立的p o i n t 3 d 系统进行介绍，并验 证前几章的理论。 西南科技大学硕士研究生学位论文 第6 页 2 虚拟现实中的三维建模技术综述 2 1 建模的定义 虚拟现实( v i r t u a lr e a l i t y ，简称v r ) ，是以计算机技术为核心，生 成逼真的视、听、触觉一体化的特定范围的虚拟环境。用户借助必要的设备 以自然的方式与虚拟环境中的对象进行交互作用、相互影响，从而产生身临 其境的体验。所谓建模，就是利用真实物体的几何特性，利用点、线、面或 图像将其在计算机上显示出来，并达到与真实物体相似的感观效果。 由上章可知，两个项目主要需要解决的就是虚拟现实中三维建模技术。 本章对各种建模方式进行了比较，并指出各种方式的不足，从而选出适用于 两个项目的建模方式。 2 2 数据建模 数据建模可细分为连续建模和离散建模两种形式。 2 2 1连续建模 连续建模主要用于机械制造中非流形体的建模，用于建立曲线、曲面。 主要形式有：l 、线框表示；2 、表面表示；3 、实体表示；4 、特征表 示：( 1 ) 空间分割表示：( 2 ) s w e e p 表示：( 3 ) 边界表示；( 4 ) 构造实体几何表 示；5 、有限元分析。下面主要介绍有限元特征建模。 面向有限元分析的特征建模技术主要是用于建立分析模型，其模型主要 由节点、单元本体数据和荷载、边界条件、材料性质、截面特性等属性数据 组成。 分类：主要是几何造型技术和非几何建模技术。几何造型技术主要是非 流形几何造型技术：非几何建模技术主要是指与有限元分析相关的材料、载 荷、边界条件等非几何信息在特征造型系统中的表示和操作。 优缺点：利用有限元方法进行几何形体计算非常方便，但在真实感( 如 光照、纹理) 方面表现效果较差。 目前，实用化的几何造型系统有s p a t i a lt e c h n o l o g y 公司的a c i s 系统 和清华大学的g e m s 4 0 系统，这两种几何造型系统所采用的非流形表示法都 是放射边数据结构的变形，共同特点是实现了线框、表面、实体和自由曲面 西南科技大学硕士研究生学位论文第7 贞 模型的统一。 2 2 2 离散建模 主要有四点法：插值法：点云( 散乱点) 法。 利用点云进行曲面重建是国际上的研究热点之一，其基本方法是利用三 维测量工具，获得三维物体上点的三维坐标，并利用这些点形成物体益面。 h o p p e 等人将点云曲面重建问题概括为：输入未知曲面f 的采样点坐标集，输 出f 的网格表达”。m z w i c k e r 在2 0 0 2 和2 0 0 4 年提出了s u r f a c es p l a t t i n g 方法，不需形成网格，即可形成曲面”“。 优点：( 1 ) 不需如图形、图像、混合建模等方式进行手工建模，直接获 取真实物体的三维形状，方便快捷，模型精度高，在逆向工程等领域应用广 泛。( 2 ) 不需将空间点连成网格，不需计算各点的空间关系，减少计算量。 缺点：( 1 ) 由于形成物体的点云较多，需要进行有效简化：( 2 ) 扫描过 程中产生一定的噪声数据，需要有效除嗓。 点云建模主要方法： 一是近似法。其中h o p p e 提出的分片线性和分片光滑的曲面模型“”最有 代表性。其边界的拓扑关系和曲面的几何特性不可知，所有曲面由数据点自 动生成。 二是基于计算几何中的v o r o n o i 图和d e l a u n a y 三角剖分。通过计算找 到数据点的拓扑连接( 即三角形网格) 。此类算法的代表有e d e ls b r ur l n e f 在 提出的基于凸壳的三维曲面重建算法( a s h a p e ) ”1 1 ，以及a m e n t a 等人提出 的c r u s t 算法1 。相对其他算法而言，c r u s t 算法较简单，尤其是与前一类算 法相比，重建效果精细。但是，c r u s t 算法对数据的采样密度具有一定的要求， 计算量太大。就目前处理器的运算速度来看，c r u s t 算法在处理几力1 个点时 效果不错，但当点的数目达到十万以上时，就难以胜任了。 三是s u r f e ls ( s u r f a c ee l e m e n t s ) 法。此法由m z w i c k e r 于2 0 0 2 年提 出。与网格法不同，它由点云直接生成曲面，不需要点之白j 的几何关系， s u r f e l s 中包括点深度、纹理颜色、点的三维坐标等信息。这种方法可用硬 件加速，真实感表现效果好，且克服了h o p p e 法层次细节难以表示的问题， 经过一定的点采样简化后1 ，可在微机上实现良好的真实感显示。 西南科技大学硕士研究生学位论文第8 页 2 3 过程建模 主要方式：分形建模；图像建模；图形建模；混合建模。 2 3 1 分形建模 分形建模是基于分形几何理论，面分形理论是非线性科学的一部分。分 形几何为表示自然物体和景物提供了有效的手段，并在纹理分割、图像压缩、 自然景物绘制和识别等领域得到了应用。分形建模是a l a i n f o u r n i e r ，d o n f u s s e l 和l o r e nc a r p e n t e r 于1 9 8 2 年提出的。他们的方法不是事先决定各 种图表和尺度，而是用一个随机过程的采样路径作为构造模型的手段，能有 效地模拟沿线海岸线和山等自然景象。主要方式有细片、破碎、分数。 优点：分形建模对于自然景物的模拟非常逼真，是当前生念环境模拟最 有效的方法。 缺点：分形描述在统计意义上具有自相似性的物体，无法达到几何模型 的精确度。由于分形细节的无限性，绘制时相交检测、可视点的测定算法较 复杂，执行速度较慢。町此，在虚拟现实中般仅用于静态远景建模。 2 3 2 物理建模 物理建模用基于物理规律的过程模拟物体的外观，表现运动行为，能准 确或近似真实地描述由物理特性决定的物体，主要应用是粒子系统。 粒子系统是w t r e e v e s 在1 9 8 3 年提出的随机模型，它用大量的粒子图 元来完成复杂运动的建模。每个粒子具有位置、速度、颜色和生命期等属性， 这些属性可根据动力学计算和随机过程得到。在虚拟现实中，粒子系统常用 于描述火焰、水流、喷泉等现象及运动物体建模。a n d r e ww i t k in 和d a y i d b a r a f f 在动态粒子系统和刚体运动的模拟方面取得了逼真的效果。 缺点：建模过程特别困难，需要复杂的数学物理知识，而且绘制速度慢， 不适用于场景的实时交互绘制。 2 3 3行为建模 行为建模不仅赋予模型外形、质感等表观特征，同时也赋予物理属性和 行为和反应能力，且服从一定的客观规律。行为建模是多学科协同的产物。 例如，对山体滑坡现象建模，就需要综合岩土力学、工程地质、数学、计算 机图形学、专家系统等学科知识，利用面向对象方法、动力学计算和动画技 西南科技大学硕士研究生学位论文第9 页 术实现。它要能分析滑坡体构造、水位对库岸边坡稳定性的影响、气候、地 下水位、滑坡体饱水程度、地震烈度以及人类活动等诸多因素，并反应出其 对各种初始条件和边界条件的响应。文献 7 对行为建模方法进行了探讨， 并提出了一种基于行为建模工具的“行为一特征建模方法”。 2 3 4 图像建模 图像建模( i b r ) 是通过一组图像柬建立场景，并适当组合这些图像来产 生场景的新视图，完成绘制工作。i b r 的产生主要是因为动画设计师、电影 制作需要照片级真实的模型，而传统的建模方法建模速度慢且工作繁琐，不 适应要求。 要解决的主要问题：( 1 ) 找到一种简便有效的表示模式，能精确完整地对 场景进行编码：( 2 ) 利用合理的图像采样数量、采样模式及样本均匀性提高建 模精度，降低难度：( 3 ) 解决因采样引起的走样和空洞问题：( 4 ) 有效的图像压 缩机制：( 5 ) 实现基于表示模式的完全实时漫游。包括模拟相机旋转、对象旋 转、相机移动及缩放等相机运动方式。 优点：( 1 ) 计算量适电：( 2 ) 独立于场景复杂度。交互显示的丌销与场景的 复杂度无关，只与分辨率有关，可用于表现非常复杂的场景：( 3 ) 满意的绘制 质量。 缺点：( 1 ) 缺少成熟算法，目前的算法比较复杂；( 2 ) 无法表示现实世界 中不存在的物体。( 3 ) 由于图像模型事先建立，给编辑、裁剪等交互性操作 带来较大难度，交互性差。 主要方法： ( 1 ) 基于立体视觉的视图合成方法。它利用立体视觉技术从图像中合成 相对于新视点的视图。关键问题是找出每对已知图像刘的对应关系，即解决 立体匹配问题。由对应关系可导出偏差映射，并能进一步估计出场景中可见 点的深度信息。利用深度信息可以对图像进行变形来合成新视点的图像。 l e v e a u 和f a n g e r a s 描述了一种从弱校正图像中构造新图像的方法”“，但该 方法靠人工选择四对对应点。m c m i l l a r l 和b i s h o p 的p l e l lo p t icm o d e l i n g 系统“7 是一个基于柱面全景图像的系统。利用偏振约束的柱面偏差计算出相 邻两个柱面全景图的偏差映射，然后依掘该偏差变形已知的全景图像，从而 得到新视点的柱面全景图。 缺点： 由于场景有可能被遮挡，只能掌握场景有限信息，导致新图中应可见 西南科技大学硕士研究生学位论文第10 页 的区域出现空洞，填补空洞是较难的问题：只产生有限的深度分辨率，使 得匹配处理出现误差。 ( 2 ) 基于视图插值l 的方法。这种方法要求新视点位于两参考图视点所决 定的直线( 称基线) 上，新视图可由参考图线性插值产生。c h e n 和w 儿l i a m s 所介绍的图像插值方法着重提高绘制速度”。另外，他们还讨论了一种简单 的空洞填补方法，但未给出深度不连续的处理办法。s e i t z 和d y e r 提出的基 于仿射投影模型，使用m o t o t o n ic i t y 规则可使图像插值产生正确的合成图 】g ( 3 ) 基于图像拼合的方法。将同一场景的多张有重叠的图像组合成一幅 较大图像叫做拼台( m o s a i c ) 。图像拼合技术被用于全景图的生成、增大图像 分辨率、图像压缩及视频扩展等方面。 ( 4 ) 基于分层表示的方法。分层表示与图像拼合征好相反，它针对视频 系列将三维场景分成运动独立的、由仿射运动模型描述的不同层次。每一层 都产生一个2 d 图像流和一个2 d 变换流( 统称脚本) ，并最终组合到屏幕上。 l e n g y e l 和s n y d e r 发展了将分层技术用于实时绘制的方法一一连贯层次的 绘制”0 1 。他们充分利用l 桢与帧之间的连贯性，不仅可分解动态的几何对象， 而且能分解光照模型中不同的光照效果( 如阴影、高光、反射等) 。每一层都 可单独控制其刷新频率、空间分辨率及绘制质量参数等，并根据它可用的资 源权衡其逼真度。 ( 5 ) 基于全视函数的方法。从一些有向的离散样本中重构连续的全视函 数，然后通过在新的视点位置重新取样来绘制新视图。p 1 e l io p t i cm o d e li n g 是第一个基于全视函数的系统“”。 2 3 5 几何建模 几何建模是在虚拟现实建模技术中最先得到发展的。它处理物体的几何 表示，研究图形数据结构等基本问题。研究对象是物体几何信息的表示与处 理，涉及表示几何信息的数据结构，及操纵该数据结构的算法。 优点：该方法具有精度高、支持功能复杂、模型描述完备等优点。而且 它本质上是使用模型的内表物体( 通常是轮廓多边形) ，几何拓扑关系的调 整较为容易，因此具有很好的交互性。可建立一些在真实世界中根本就不存 在的模型。 缺点：其绘制时阃与几何模型的复杂度密切相关，随着模型复杂度的提 高，其绘制时间将呈几何级数提高。人机交互工作量大，高逼真度绘制仍然 西南科技大学硕士研究生学位论文第11 页 是个复杂课题。仅能建立对象外观，不能反映对象的物理特征，更不能表现 对象的行为。 主要形式：有层次建模法和属主建模法。其建模过程可分为体素和结构 两个方面。体素用来构造物体的原子单位。结构用来决定体素如何组合以构 成新的对象。 ( 1 ) 层次建模法。它是利用树形结构来表示物体的各个组成部分，对描述 运动继承关系比较有利。例如：手臂可描述成由肩关节、大臂、肘关节、小 臂、腕关节、手掌、手指构成的层次结构，而各手指又可以进一步细分。在 层次模型中，较高层次构件的运动势必改变较低层次构件的空间位置，例如： 肘关节转动势必改变小臂、手掌的位置，而肩关节的转动又影响到大臂、小 臂等。 ( 2 ) 属主建模法。它是让同一种对象拥有同一个属主，属主包含了该类对 象的详细结构。当要建立某个属主的一个实例时，只要复制指向属主的指针 即可。每一个对象实例是个独立的节点，拥有自己独立的方位变换矩阵。 以汽车建模为例，汽车的4 个轮子有相同的结构，可建立一个轮子属主，每次 需要轮子实例时，只要创建一个指向轮子属主的指针即可。通过独立的方位 变换矩阵，便可得到各个轮子的方位。这样做的好处是简单高效、易于修改、 一致性好。 2 3 6 图形图像混合建模与绘制 它主要针对几何领域内的相关技术”“，如网格与b 样条的混合、2 d 3 d 的关联、多边形与纹理图像的混合或将传统的线框、表面、体造型与参数化 技术融合为一体，使所有的模型基于同的数学模型等，纹理映射技术是浚 技术的熏要基础之一。目前该技术是计算机图形学的一个研究热点，对该技 术的研究，美国斯坦福大学b e r k e l e y 分院、北卡罗来那大学( u n c ) 和普林斯 顿大学( p r in c e t o n ) 处于领先地位。 优点：吸取了图像建模和图形建模的优点，并克服了它们的某些缺点， 以较少的人机交互和图像需求，产生精度较高的三维模型，且容易实现真实 感渲染，是比较有前途的三维建模方法。 要解决的主要问题：几何模型的图像建模、几何模型的图像绘制、图像 的几何信息提取( 几何坐标与拓扑关系等) 、图像模型的几何建模与绘制、几 何与图像模型的融合等。 西南科技大学硕士研究生学位论文第12 页 2 4 本牵小结 根据两个项目的要求，结合在虚拟现实与计算机仿真研究中的一些体会 对虚拟现实中的建模方法进行了一些探讨，对各种建模方式进行了系统比 较。为了使项目中模型更加逼真，可以对有复杂曲面的物体建模，并考虑效 率，决定在两个项目中分别使用基于点云的三角剖分法和面素法两种方式建 模。 西南科技大学硕士研究生学位论文第1 3 页 3 基于点云的三维三角划分算法 3 1三角划分的定义 点云的三角划分是根据空剧散乱数掘点集，构造出单元之间不相互重 叠、与点集的占有空间相容、精确逼近点集所表示的物体表面的三角网格， 而且网格形状和密度分布合理、相邻单元的边界相容。 项目“交互式三维建模及物理仿真研究”、“三维场景真实感技术研究” 要求模型逼真而且可以和用户实时交互。由前一章可知，为了保证模型的逼 真性，且有较高的运算速率，采用基于点云的三角划分法建模比较合适。 3 2 三角划分目前的问题及解决办法 主要问题： ( 1 ) 三角划分结果只能是一个三角形单元集合的凸包，对有复杂边界( 如 带有凹边界或内孔) 的曲面数据，若不将原区域分解成若干凸区域，划分结 果中将有大量冗余三角形。如d e l a u n a y 三角划分”“、l a w s o n 、 c l i n e r e n k a “。“”1 、b kc h o i 等算法都存在这一问题。 ( 2 ) 现有的三角划分方法都只能解决三维测量数据点与二维投影点一一 对应的情况，对于单向投影有重叠的数据点集，都是通过分片向合适的方向 投影，分别处理后进行拼接的方法来实现。这种方式往往需要大量的人工干 预，降低了三角划分算法的效率。”。尽管b k c h o i算法采用在三维空间 直接划分，但因其实施条件的限制，仍然无法根本解决这一问题。 ( 3 ) 由于在三维空间不易寻找数据点之间的邻接关系，虽有许多简化算 法“2 ”，但三维三角划分算法的研究一直没有取得突破性进展。 目前与网格扩展有关的算法主要有： ( 1 ) c a v e n d is hj c 提出的波前法。波前法是一种二维的结点连元法，其 算法思想是网格划分由边界丌始，逐步向里推进。如果将波前法扩展至三维 空间，凹边界或内孔问题及分片问题都应该可以得到解决。但是在三维空问， 数据点之间空间邻接关系不好确定，会给三维三角划分算法带来很大困难。 它的优点是：从边界向内扩展的思想，使得具有任意凹边界或内孔的 曲面数据，可以同样处理。 ( 2 ) l o s h 引入了网格生成前沿。随着网格从边界向内扩展，生成前沿也 西南科技大学硕士研究生学位论文第1 4 页 在不断变化，直到网格全部生成，网格生成前沿集合和内部结点集合全部为 空。虽然l o s h 在一定程度上简化了算法，但是与c a v e n d i s h 的方法一样， 它适用于内部结点分布比较均匀的单值曲面，对于数据分布散乱、形状复杂 的多值衄面的处理困难。 本章提出了一种新的三维三角网格划分方法，适用于一般非封闭曲面、 剪裁曲面、空间多连通曲面等各种类型的曲面数据。由于直接在三维空间划 分，不需要将益面分片，能够简单地处理凹边界和内孔问题。 3 3 三角网格划分算法 3 3 1 三角网格初始化 非封闭曲面有曲面边界，而封闭曲面无边界，因此它们的初始化过程稍 有不同。 封闭曲面由于没有边界，三角划分可以从曲面的任意部分开始，其初始 化过程如下： ( 1 ) 从点表中取出厂数据点v 1 ，并从点表中另找出一点v 2 ，与v 1 相 距定步长。步长是根据与数据点集所占的空问范围大小的比例来确定，比 例可由程序缺省设置，也可出程序用户手工设置。然后由v 1 、v 2 生成边v l v 2 。 ( 2 ) 从点表中寻找边v 1 v 2 的最优顶点v 3 ，与顶点v 1 、v 2 连接生成边 v 2 v 3 、v 3 v 1 。由生成的三边构造初始三角形t 。 ( 3 ) 点类的成员变量t r e a t e d 初始值都为0 ，将点v 1 、v 2 、v 3 的t r e a t e d 值置为8 ，表示它们为网格结点：将三角形t 的所有内部点的t r e a t e d 置为 l ，标记它们是已处理点。 ( 4 ) 将当前边表中的三条边放入边界边表。 ( 5 ) 将当前边界边表所构成的边界环放入边界环表。 3 3 2三角切分 点云的三角切分是网格扩展、边界环分裂和边界环封闭的过程。 3 3 2 1网格扩展 在三角划分过程中，网格扩展实际上是通过为边界边寻找最优顶点，构 成新三角形来实现的。如图3 一l ( a ) 所示，边b e d g e 是一条边界边，在临时 边界边表中它前面的边界边是p r e e d g e l 、p r e e d g e 2 、后面的边界边是 西南科技大学硕士研究生学位论文第15 页 n x t e d g e l 、n x t e d g e 2 图中阴影区域是未划分区域，粗线代表边界边，已 划分区域内部的边用细线表示。图3 1 ( a ) 中的几条边界边是一个边界环的 局部，根据它们的前后关系可知该边界坏中边界边的排列是按逆时针方向旋 转，在新三角形生成过程中边界环的转向应始终保持不变。 a ) 砉u 始幽b ) 扩胜幽1 c ) 扩瓞图2d ) 扩艘蹦3 圉3 - 1网格扩展 将己划分区域内的点的t r e a t e d 成员变量值置为l ，网格结点的 t r e a t e d 值置为8 ，而未划分区域中的点的t r e a t e d 值为0 ，由此可以区分 已划分区域和未划分区域内的数据点。从未划分区域的点中找到一点p ，连 接该点与边界边b g d g e 的两个端点所形成的三角形t 1 最接近正三角形，如 图3 1 ( b ) 。此时原边界边b e d g e 所指向的边不再是边界边，点p 与原边界 边b e d g e 的两个端点连接生成的两条边成为了新的边界边。此时的未划分区 域与已划分区域之间的边界如图3 1 ( b ) 所示。 点p 与边界边p r e e d g e l 可能构成较好的三角形，即点p 是边界边 p r e g d g e l 的可见顶点，如图3 1 ( c ) ，连接点p 与p r e e d g e l 中与边b e d g e 不 相关的端点，就可以生成一个新三角形t 2 。 西南科技大学硕士研究生学位论文第16 页 点p 与边界边n x t e d g e l 也可能构成较好的三角形，即点是边界边 n x t e d g e l 的可见顶点，如图3 一l ( d ) ，连接点p 与n x t e d g e l 中与边t e d g e e 不相关的端点，就可以生成一个新三角形t 3 。 对每一条边界边都做如上的操作，随着新三角形的不断形成，已划分区 域逐渐扩展。 为边界边寻找最优顶点要以初始化过程中设定的平均步长l 和该边界 边所在三角形平面为依据。设需要寻找最优顶点的边界边为b e d g e ，确定一 个宽为1 5 l 、长为1 o l 、高为0 8 l 的包围盒。该包围盒的长与b e d g e 平行 并相距0 5 l ，高与b e d g e 所在三角形平面的法矢平行并被该平面平分。在 包围盒所包围的数据点中寻找h e d g e 的最优顶点，大大缩减了最优顶点的选 择范围，减少计算量，提高划分速度。 由于是从包围盒范围内的数据点中优选，很多情况下会出现寻找到的最 优顶点与其他顶点或边界边过于接近，使得后续要生成三角形状很差。为了 镬生成的网格形状优良，应避免选择这样的点作为最优顶点。因此可在三角 形内部点标记过程中，将未划分区域中( 即t r e a t e d = o 的点中) 的符合以下 两个条件的数据点t r e a p d 值设为2 ： ( 1 ) 以边界边的端点为球心，半径为0 5 l 的球范围内的点： ( 2 ) 距离边界边0 0 5 5 l ，高为0 8 l 的包围盒内的点。 由于最优顶点的选择是在t r e a t e d = o 的点中进行优选的，因此 t r e a t e d = 2 的点，将不会被列入选择，从而可以保证