（计算机应用技术专业论文）离散点云模型曲面重构三种方式的研究及扩展.pdf

浙江大学硕士学位论文 摘要 摘要 在工业设计和制造中，经常需要对已有的物体或部件进行数字化，并建立相 应的数学模型：首先通过扫描设备对物体模型进行信息采集，得到一系列包含各 种信息的空间数据点，即点云模型。点云模型是以离散采样点为基元的几何模型， 具有数据结构简单、存储空间紧凑，表达复杂表面细节的能力等优点。然而，点 云模型一般不能被直接应用，通常针对不同需要，采用不同的曲面表示方法对它 们表示的模型进行曲面重构，这种处理方式也被称为逆向工程。随着科技的发展， 具有高处理性能的三维扫描设备不断涌现，因此点云模型也越来越多，并且逐渐 拥有大规模，高密度等特点。进而对点云模型曲目重构算法的效率和性能提出了 更高的要求。 本文以点云模型曲面重构为研究对象，研究并扩展了三种常用曲面重构方 法：最小移动二乘法( m l s ：m o v i n gl e a s ts q u a r e sm e t h o d ) 法，径向基函数( r b f ： r a d i a lb a s i sf u n c t i o n sm e t h o d ) 法和多层次单元分割( m p u ：m u l t i 1 e v e lp a r t i t i o no f u n i t ym e t h o d ) 法。这三种方法的处理方式不一样，运用的范围和所获得结果曲面 也不一样。本文的研究成果主要分为以下三部分： ( 1 ) 三种曲面重构法的分析及优化：分别研究讨论三种方法的核心思想和数学模 型，对某些方法性能和结果上的缺陷，给出优化方案加以弥补。 ( 2 ) 扩展三种方法的曲面编辑操作功能：对前面所述方法进行扩展，提出对结果 曲面编辑的处理方法，如基于m p u 的布尔操作，基于r b f 的融合操作等。 ( 3 ) 三种方法的研究比较：着重分析了三种方法在性能和生成结果上的差异，更 清晰地阐明三种方法的优缺点。 关键词：点云模型，逆向工程，曲面重构，最小移动二乘法，径向基函数法， 多层次单元分割法，布尔操作，融合操作 浙江大学硕士学位论文 a b s t r a c t i ni n d u s t r i a ld e s i g na n dm a n u f a c t u r ef i e l d , i ta l w a y sn e e d st od i g i t a l i z et h e e x i s t i n go b j e c t so rp a r t s , a n db u i l dt h e i rm a t h e m a t i c a lm o d e l s ：f i r s t l y ，u s i n gt h e3 d s c a n n e l - t os a m p l et h eo b j e c t , a n do b t a i nal a r g en u m b e ro fp o i n t sw i t hv a r i e t i e st y p e s o fd a t a , n a m e l yp o nc l o u dm o d e l i ti sag e o m e t r i cm o d e lu s i n gap o n a sa p r i m i t i v e a n dh a sm a n ye x c e l l e n tp r o p e r t i e ss u c ha ss i m p l es t r u c t u r e , c o m p a c ti ns p a c ea n d e f f i c i e n ti nr e p r e s e n t i n gl a r g es c a l eg e o m e t r ym o d e l sw i t hr i c hd e t a i l s h o w e v e r , p o i n t c l o u dm o d e lu s u a l l yc a nn o tb eu s e dd i r e c t l y ；d e s i g n e r su s ed i f f e r e n tm e t h o d st o r e c o n s t r u c ts u r f a c em o d e l sf o rd i f f e r e n tp u r p o s e s t h i sp r o c e s si sw e l lk n o w na s r e v e r s ee n g i n e e r i n g w i t ht h ed e v e l o p m e n to ft h et e c h n o l o g y , m o r ea n dm o r e3 d s c s n n e r sw i t hh i 曲c a p a c i t yc o m eo u t , a l lt h e s el e a dt om a n yn e wp 0 砒c l o u dm o d e l s , s o m eo fw h i c hh a v el a r g ea m o u n to fd a t aa n dh i g hd e n s i t y a l lt h e s er e q u i r em o r e r o b u s ta n de f f i c i e n ts u r f a c er e c o n s t r u c t i o na l g o r i t h m t h i st h e s i sf o c u s e so ns u r f a c er e c o n s t r u c t i o nf i o mp o i n tc l o u dm o d e l ，a n dh a v e d i s c u s s e da n de x t e n d e dt h r e ec o m m o nm e t h o d s ：m o v i n gl e a s ts q u a r e sm e t h o d ( m l s ) ， r a d i a lb a s i sf u n c t i o n sm e t h o d ( r b f ) a n dm u l t i - l e v e lp a r t i t i o no fu n i t ym e t h o d o v n , t d a l lt h e s em e t h o d sh a v ed i f f e r e n ta p p l i e da r e a sa n dr e s u l t i n gs u r f a c e ，s i n c et h e y u s ed i f f e r e n ta p p r o a c h e st op r o c e s st h ep o i n tc l o u dm o d e l c o n t r i b u t i o n so ft h i st h e s i s m a i n l yi n c l u d ef o l l o w i n ga s p o e t s ： 1 i l l u s t r a t i n ga n do p t i m i z i n gt h r e em e t h o d s ：t h ep a p e rh a si l l u s t r a t e dt h eb a s i c i d e a sa n dm a t h e m a t i c a lm o d e l so ft h et h r e em e t h o d s ，a n da l s og i v e ns o m e o p t i m i z a t i o na p p r o a c h e sf o rt h e m 2 e x t e n d e dr e s u l t i n gs u r f a c eg a i n e df i o mt h ea b o v em e t h o d st oe d i to p e r a t i o n s ： h a v i n ga d v a n c ed i s c u s s i o no ft h et h r e em e t h o d sa b o u te d i to p e r a t i o n so n s u r f a c es u c ha sb o o l e a nb a s e do i lm p um e t h o da n db l e n do p e r a t i o nb a s e d o nr b fm e t h o d 3 c o m p a r i n gt h et h r e em e t h o d s ：a n a l y z i n gt h ep e r f o r m a n c ea n dc o m p a r i n gt h e i i 浙江大学硕士学位论文 a b s t r a c t r e s u l t so ft h et h r e em e t h o d s ，a l lt h e s em a k et h ed e s i g n e r sm o r ec l e a r l ya b o u t t h es t r e n g t h sa n ds h o r t c o m i n g sa m o n gt h e m k e y w o r d s ： p o i n tc l o u dm o d e l ，r e v e r s ee n g i n e e r i n g ，s u r f a c er e c o n s t r u c t i o n , m l sm e t h o d , r b fm e t h o d , m p um e t h o d , b o o l e a no p e r a t i o n ，b l e n do p e r a t i o n 浙江大学硕士学位论文图目录 图目录 图1 1 激光雷达( l i d a r ) 扫描仪2 图1 2 坐标测量方法分类4 图1 3 论文组织框架图8 图2 1m l s 基本思想示意图1 0 图2 2m l s 方法投影原理示意图1 2 图2 3 参数h 对m l s 方法的影响1 3 图2 4 点云模型去冗余处理1 6 图2 5 向上采样处理过程。1 7 图2 6 兔子模型的向上采样1 7 图2 7 圆盘在空间投影中投影成椭圆形状1 9 图2 8 马模型的三种图形渲染方式的对比2 0 图3 1 曲面偏移点集获取方式2 2 图3 2 快速拟合参数和评估精度参数图解2 5 图3 3 中心点点集的重采样方式2 6 图3 4 隐式曲面的多变形网格处理过程2 8 图3 5 凸单元参数对网格化影响2 8 图3 6 中心点数对r b f 函数的影响：2 9 图4 1 自适应分解图示3 3 图4 2 两类局部函数拟合方式3 5 图4 3 辅助点和尖锐特征的判断3 5 图4 4 未优化的2 t o r u s 曲面显示3 8 图4 5 生成网格的优化处理3 9 图5 1 点的内外判定4 l 图5 2 相交曲线的采样过程4 3 图5 3 自适应完善处理过程。4 3 图5 4m l s 布尔操作模型显示4 4 图5 5 框选参与融合的区域4 6 图5 6 融合区域生成和显示过程4 7 图5 7 参与布尔操作的点云模型4 9 图5 8 两模型布尔操作运算结果5 0 图5 9 布尔操作网格优化处理5 l 图5 1 0 采用三种方法对点云模型重构的曲面5 3 图5 1 lr b f 与m p u 方法生成网格对比0 5 4 图6 1 基于m p u 的o f f s e t 处理过程5 7 图6 2 错误的o f f s e t 处理结果5 8 i n 浙江大学硕士学位论文表目录 表目录 表5 1 基于谓词q p 的分类规则4 2 表5 2 点归属判断规则4 8 表5 3 基于m p u 方法的布尔操作生成网格信息4 9 表5 4 布尔操作优化结果5 2 表5 5m l s ，r b f 和m p u 方法对松鼠点云模型的处理结果5 3 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝姿盘茎或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学雠文作者签名层宇当壳签字喻乡口移s 年月s 日 学位论文版权使用授权书 本学位论文作者完全了解逝姿态堂 有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝望本堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：钟白花 签字日期：知迟年月g 日 翩繇吲气 签字日期：莎矽孑年月g 日 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 课题背景和意义 随着计算机图形学理论和技术的快速发展，其应用已遍及工业设计，机械制 造，模拟仿真，地质探索，游戏娱乐等多个领域。计算机图形学所研究的三维几 何模型是继一维的声音数据、二维的图像数据以及视频数据之后的一种创新的数 字多媒体数据。与传统的多媒体数据相比较，三维几何模型以其强烈的真实感更 符合人类对自然世界直观认识，受到了工业界和学术界的广泛关注。在三维几何 模型快速发展与应用的几十年里，三维几何模型的表现形式一直处于发展之中。 三维几何模型的主要表现形式包括非均匀有理b 样条曲面( n u r a s ) 、隐式曲面、 网格模型。不同的表现形式在不同的应用领域各具优势，使得三维几何模型的几 种表现形式长期并存。通常在如汽车，机械零件等工业制造领域使用的是有理b 样条曲面；在医学c t 方面，主要采用的是隐式曲面的方式；而在数字娱乐，3 d 动画采用的却是网格模型。 点云模型是一种新兴的三维几何模型表现形式。它是三维坐标系统中点的集 合，有时这些点包括相应的法向量，这些点通常由三维坐标值来表示。大多数的 点云由三维扫描设备来获得，这些设备能够测量物体表面的大量的点，并将它们 输出到一个文件。如图1 1 所示是一台三维扫描仪，可用于扫描建筑物或岩石结 构，获取点云模型。该模型是被扫描或数字化物体的可视表面的采样点集。点云 模型在包括制造部件，度量检测，视觉动画，三维c a d 模型重构等方向得到了 广泛的应用。 通常，点云模型不能直接用于三维几何模型。应用中，常将点云模型转化为 网格模型，有理b 样条曲面模型，或使用逆向工程技术进行曲面重构，以满足不 同的应用需要。点云模型的一个直接应用是工业度量或工业检测。制造部件的点 云模型也可以直接用来与c a d 模型相对比，通过颜色标明制造部件和c a d 模型 的偏差，并且几何尺寸和公差可以直接从点云中抽取出来。 塑垩奎兰堡兰兰竺堡壅 笙! 皇竺坠 。_ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ - _ _ - - _ _ _ _ - - _ _ - - _ _ _ _ _ _ - _ _ _ - _ - - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ 。_ _ - 。1 。1 。一 近年来，国内外学者提出了许多点云模型显示和处理及操作方法。在点云模 型中，点基元被称为采样点。研究以点为基元的点云模型的表示、处理、渲染、 以及几何造型技术的学科被称为基于点的图形学( p b g ：p o i n tb a s e dg r a p h i c s ) 。 自2 0 0 2 年以来，每年的欧洲计算机图学年会( e u r o g r a p h i c s ) 都有一个专门的p b g 研讨会，基于点的图形学引起了国内外众多研究学者的研究兴趣。 图i 1 激光雷达( l i d a r ) l 描仪 1 2 点云模型的数据采集 点云模型的坐标信息是数据处理、模型重建的基础。高效率、高精度地采集 物体的曲面特征是一项重要研究内容【1 1 。测量技术随着新的物理原理、新的技术 突破而获得长足发展。光波干涉技术特别是激光技术的实用化使得测量精度提高 了1 2 个数量级。近年来，激光扫描技术取得了重大进展，3 d 激光扫描设备的 浙江大学硕士学位论文第l 章绪论 精度已达到亚毫米级；数字显示技术在测量上得到了充分的应用，提高了读数精 度和可靠性。目前常用的三维物体扫描仪通常大致可以分为下列几类【2 1 ： 机械接触式坐标测量机 该类测量机通过测量头与实物的接触获得其坐标点的数据。 光学坐标测量机 该类测量机使用光源照射实物，再用干涉条纹技术测出实物的形状。 激光坐标测量机 该类测量机采用激光扫描实物，同时由摄像机录下光束与实物接触部位。 它又可以根据接触部分的形状，进一步分为点激光测量机、线激光测量 机和面激光测量机。 机械接触式坐标测量机的最大优点是成本低，所以目前运用较为广泛；缺点 是测量速度比较慢，并且因为测量时会产生接触压力，所以不能对软质材料或超 薄形物体进行测量。除此之外，当测量头直径大于间隙宽度时，扫描采样就会受 到限制，同时球头半径的存在也给后续的数据处理增加难度。与机械接触式坐标 测量机相比，光学和激光测量机具有速度快、精度高的优点。因为在进行测量时 不需要与物体接触，所以对被测物体的材质和形状没有特殊限制。 利用先进的坐标测量机实物测量就不必特别的选取能描述型面的特征曲线 进行测量，而是可以一次或多次在不同方向上对被测量物体进行整体或局部的大 量密集点采集，从而获得更加完整的数据信息一 上面简要的介绍了三种测量机的优劣。下面针对三维物体表面采样的常用方 法【3 】，如图1 2 所示，本文进行更详细分类，并做了详细的说明与对比。 坐标测量方式可以分为接触式和非接触式这两个大类。接触式测量方法通过 传感测量头与被测物体接触，记录物体表面坐标位置数据，因此接触式测量的精 度相对较高。它又可以进一步细分为点触发式和连续式两个数据采集方法。点触 发式测量的缺点是测量效率相对较低，优点是可以通过手动的规划，在大曲率或 曲率变化剧烈的区域获得更多的采样点，而在相对平坦的区域测量较少的点。它 也可以结合造型方法，手动的对被测物体进行区域规划，测量对物体形状表达起 浙江大学硕士学位论文+ 第1 章绪论 关键作用的特征线和曲线网格，并且也可以根据需要将数据点组织成模型重建软 件所需要的形式，根据特征线及曲线网格重建物体的c a d 模型，减少数据处理 的难度。 图i 2 坐标测量方法分类 非接触式测量法主要采用了光学、声学、磁学等领域中的基本原理，它通过 将一定的物理模拟量，采用适当算法转化为被测物体表面的坐标点信息，例如： 声纳测量方式就利用声音遇到被测物体所产生回声的时间间隔来计算点与声源 间的距离，进行计算点坐标信息；激光测距法则是计算激光束的飞行时间得出被 测点与参考平面间的距离；图象分析法通过利用点在多副图像中的相对位置，采 用视差来计算距离，从而得到点的空间坐标；激光三角形法则利用光源与影像感 应装置( 摄影机) 问的位置与角度来推算出点的空间坐标；结构光法则将一定模式 的光，像条形光、栅格状光等，投射到被测物体表面，然后捕获被曲面反射后的 光所形成图像，对它们进行分析最后获得三维点坐标信息。结构光法与图象分析 法主要不同之处是结构光法还需要投射具有一定模式的人工光源，这种方法中最 典型的是m o 干涉条纹法。非接触式测量使测量效率得到了极大提高，某些光 学测量机可以在数秒钟内获得几十万个数据点信息，因而在测量过程中可以大大 减少人工测量规划工作，在整个被测物体表面快速采集大量的密集点。这样既简 化了测量过程，又减轻了测量人员的负担，而且可以获取被测物体的更多细节的 海量数据。通常，海量数据的非常庞大，经常有几十万、上百万甚至更多的测量 点。过于庞大的测量点集，会严重影响曲面重建算法的效率，给数据处理和模型 4 浙江大学硕士学位论文第l 章绪论 重建带来很大的困难，这时往往需要通过特定算法对经过采样获得的点云模型进 行简化处理。另外，整体测量得到的数据一般是散乱的，而且并不显式地包含特 征信息如尖角、棱边，这样就需要通过相应的软件进行数据分片和特征提取。 随着科技的进步，越来越多的新型三维扫描设备被研发出来。它们不仅可以 获取被测物体表面的坐标信息，还能获取相应点的纹理和颜色信息，从而使最后 的点云模型能够更加准确的描述被测物体。 1 3 点云模型的预处理技术 通过对被测物体曲面进行采样而获得的点云模型一般不能直接用于数字几 何处理，因为它可能包括空洞区域，冗余数据，噪声点等错误信息。因此，为了 进行几何处理，首先必须对获得的点云模型做必要的预处理，这些处理手段包括 配准、去噪、以及压缩等。 1 3 1 点云模型配准 由于光线性传播特性，通常在一个视角下，扫描设备只能采集到被测物体部 分表面的数据，获取整个表面数据则需要在不同视角下，对被测物体进行多次测 量才能获得。因为对每次的扫描操作都是在不同坐标系下进行，所以为获得被测 物体的完整数据信息，就需要建立合适的坐标变换，将从各个视角得到的采样点 数据信息转换到一个统一的坐标系中，这步操作就叫做配准。 当前，点云模型配准技术主要分为两大类： 1 ) 机器配准：采用高精度定标仪器得到的多视点数据以及它们之间的原始 变换关系，来进行数据间的配准计算； 2 ) 自动配准：通过数据中的变换信息或在数据获取的同时引入其它信息， 对三维数据进行配准计算。其中自动配准技术与硬件设备无关。 其中，自动配准技术通常又可以分为初始配准和精确配准两步。 初始配准的方法有：标签法【4 】，即在测量时手动贴上一些特征点，然后使用 它们进行定位，然而该方法仍旧依赖于测量仪器；特征提取法【5 1 ，则通过提取轮 廓曲线作为对齐的标准，该方法要求点云模型具有比较明显的特征。 5 浙江大学硕士学位论文第l 章绪论 最近点迭代算法嘲( i c p ：i t e r a t i v ec l o s e s tp 0 i n t ) 是经典的精确配准算法，但该计 算效率不高。国内外众多研究学者都对改进这一算法做出了努力，如b l a b 【刀等提 出结合逆向定标法和随机搜寻法来提高速度，但这却对配准精度带来一定的影 响。l i t 8 】等提出迭代最近线( i c l ：i t e r a t i v ec l o s e s tl i n e ) 算法，通过直接对两个点集 中的点进行连线并寻找对应线段进行配准。 1 3 2 点云模型去噪 点云模型获取过程中难免会产生噪声，因此去噪处理是预处理操作的一个非 常重要步骤。去噪的困难在于在将无规则的噪声数据剔出的同时，还需要有效地 维持模型的原有特征。p a u l y l 9 等采用将点云模型先分块，然后对每一块采用局部 高度场逼近进行重采样，从而把图像处理中基于f o u r i e r 的谱分析方法运用于点云 模型。最近，s c h a l t l o 】等将图像处理中的非局部邻域过滤( n o n 1 0 c a ln e i g h b o r h o o d f i l t e r i n g ) 算法用于点云模型去噪，获得理想的去噪效果，该算法同样具有修复点 云模型几何特征的能力。 1 3 3 点云模型压缩 随着三维扫描设备的扫描精度的不断提高，能够轻易地获取具有海量数据的 点云模型。因此针对点云模型的压缩处理已成为高效的点云模型表示、传输、渲 染和处理的必要手段。与网格模型压缩类似，点云模型压缩也可分为两类：单精 度压缩编码【1 1 ( s i n g l e - r a t ec 0 d e 船) 和渐进压缩编码【1 2 1 ( p r o g r e s s i v ec o d e r s ) 。与单精 度压缩编码相比，渐进压缩编码允许模型以渐进的方式传输和重构模型，因此更 适用于网络领域。k r u g e 1 3 j 等提出的处理方法不能简单地划分单精度或渐进压缩 编码，该方法虽然对点云模型采用渐进的方式编码，但粗糙层次的字节流并没有 嵌入到模型精细的层次表示中。 大部分的点云模型压缩算法都是建立在八叉树上的。给定要压缩的点云模型 尸的包围盒，以此为点云模型构建叶节点层数为三的八叉树d ，然后将p 中所有 点存入d 中。尸在叶节点内的点由叶节点的中心表示，从而完成简化编码。 6 浙江大学硕士学位论文 第l 章绪论 1 4 点云模型的国内外研究现状 目前在计算机图形学的应用领域中，有着丰富的曲面模型的表达形式：样条 曲面、隐式曲面、参数曲面。然而实际应用时，往往根据其特点予以选择。模型 表面的不同表达形式之间通常可以相互转换，将点云模型转换为其它曲面表达形 式也是近几年来国内外研究领域中的热点。 点云模型的常用的处理方法是建立其三角网格曲面模型。迄今为止，已经提 出多种有效的三角网格算法【1 4 l f l 5 1 。即便如此，这些方法依旧没能解决点云模型三 角化的一个主要缺陷，即构建的模型表面相当粗糙，存在隆起凸包和其它不良特 征，如空洞或涡旋孔，甚至可能生成非流型曲面。因此对点云模型三角化后所建 立的网格模型进行光滑处理【16 】或二维流型的转化【1 7 】就显的非常必要。这些处理相 当复杂，但其中最大困难是点云模型没有真正插值成一个光滑曲面。为此，需要 将点云模型中的点推进到曲面，该操作称为“巩固”( c o n s o l i d a t i o n ) 。 通过在点云模型上采用加权平均可以实现“巩固”。t u r k 1 8 】等提出先执行模 型的三角化，随后对重叠的区域进行权值平均化处理。而在s o u c y 1 9 】等提出的方 法中，对点云模型先进行加权和平均化处理，再执行三角化操作。 另外一种对点云模型曲面重构方法是执行某种形式的曲面拟合，如l e i 【2 0 】等 提出一种拟合多项式曲面方法。总的来说，了解数据的内部拓扑结构和在曲面拟 合之前进行参数化是有必要的。 在1 9 8 5 年，随着l e v o y 1 】等开创性论文的提出，使用点基元进行曲面建模受 到越来越多研究学者的关注，并付出了各式各样的努力。最近，p a u l y 2 1 】等提出基 于点云模型的曲面编辑建模方法，并建立了一个系统p o i n t s h o p 3 d , 该系统具有较 强大的点云模型编辑功能。 1 5 本文的研究内容和结构 本文研究内容主要包括三种常用点云模型曲面重构方法：移动最小二乘法1 2 2 】 ( m l s ：m o v i n gl e a s ts q u a r e s ) ，径向基函数法【2 3 】( i m f ：r a d i a lb a s ef u n c t i o n ) ，多层次 单元分解法【2 4 1 ( m p u ：m u l t i p a r t i t i o nu n i t ) ，除分别对它们讨论外，还研究了对这 7 浙江大学硕士学位论文第1 章绪论 些方法所构建曲面的编辑操作，并对三种方法的优劣进行详细的分析。最后是对 全文探讨的内容做了总结，给出下一步研究的方向。如图1 3 所示，该图清晰地 描述了各章之间的关系和各章的主要内容。 图1 3 论文组织框架图 本文内容由六章内容构成。主要研究工作在第二章，第三章，第四章和第五 章阐述。其中第二，三，四章呈并列关系，依次讨论研究了m l s 方法，r b f 方 法，m p u 方法。在这三章中除讨论了方法的原理和数学模型外，还用本文系统实 现出的例子进行更加形象的说明。其中在第三章，对r b f 方法提出改进的插值点 约减方法，不仅提高了r b f 方法的效率，也获得了准确的曲面。而对第四章的 m p u 方法，则对所得曲面进行优化处理，曲面的尖锐特征得以恢复。在第五章， 对以上三章讨论的方法进行分析对比，总结了它们的优劣，并将三种方法扩展到 曲面编辑上，提出了基于r b f 的融合操作和基于m p u 的布尔操作，获得了良好 的效果。在第六章，对全文所做研究进行总结，并对将来工作进行了简要说明。 本文对点云模型的显示在p o i n t m o d e l i n g 实验平台上实现，它在v c 6 0 编译 环境开发、图形显示采用o p e n g l 实现。如无特殊说明，本文实验数据均在硬件 配置为a m d3 2 0 0 + 、内存1 g b ，操作系统为w i n d o w s x p 的p c 机上获得。 8 浙江大学硕士学位论文第2 章点云模型的移动最小二乘曲面重构法 第2 章点云模型的移动最小二乘曲面重构法 移动最小二乘( m l s ：m o v i n gl e a s ts q u a r e s ) 点云模型曲面重构法阎是基于点 的图形学中最重要的曲面重构方法，它包括平面投影和局部高阶多项式拟合两个 步骤。该方法基于严格的数学推导，能够较好地解决点云模型曲面重构过程中的 去噪与特征保留之间的矛盾；还可用于点云模型重采样和基于点的渲染。除此之 外，该方法具有较好的性能，能比较准确的求出点云模型相应的法向量集，它们 可以结合别的方法一起运用。以下将对该方法展开讨论研究。 2 1 移动最小二乘法的引入 进行曲面重构时，建立于点云模型上的表达方式应该尽可能的简洁，这在某 种程度就要求点云模型应该尽量降低噪声和冗余数据。m l s 方法就是按照这些标 准，从微分几何中获得灵感而提出的，它的目标就是最小化曲面重构时产生的几 何误差。该方法的本质是：采用移动最d , - - - 乘法建立一系列多项式，它们局部逼 近原有曲面，将它们混合从而完成整个曲面重构。 曲面的点云模型生成是一个采样过程，而点云模型规模由对曲面进行向上还 是向下的采样决定。假设有一初始点云模型尸= 肼，相应的定义了一个光滑曲 面昂。随后在数目更少的点云模型r = n 上定义m l s 光滑曲面，并用它来代 替在点云模型尸上定义的曲面品。 如图2 1 所示，使用四幅图对该过程进行阐明：图( a ) 使用紫色点云模型只定 义了一条紫色的曲线品。图( b ) 对昂进行了重新的采样，新获取的采样点为r l ， 用红色代表新点云模型，其中满足n 昂。在图( c ) 用该新点云模型，拟合了一条 新的红色曲线，它充分逼近昂。最后在( d ) 图，对两条曲线进行了对比。 9 浙江大学硕士学位论文第2 章点云模型的移动最小二乘曲面重构法 ( a ) 图2 1m l s 基本思想示意图【2 2 l 通过对初始曲面函进行图2 1 所描述的重采样处理，得到下面一些重要特性： ( 1 ) 光滑二维流型 如果点云模型中的点足够靠近要描述的曲面，那么该点云模型的重构曲面满 足二维流型，并且具有矿光滑。 ( 2 ) 有限的采样误差 用& 表示在采样点集n 踯上定义的曲面。那么存在有限误差，满足，d ( s r , s p ) sg 这里计算符号破，) 代表h a u s d o r f f 距离。 ( 3 ) 局部计算 为计算曲面上的一个点，只需该点周围相邻点的信息。由于只依靠于期望的 特征大小，而与点云模型规模不相关，因此带来较小内存开销。 ( 4 ) 高质量 因为& 是一个光滑曲面，合理的重采样能产生出光滑的侧面轮廓和准确法向 量，这些都使后面的渲染结果更加的逼真。 l o 浙江大学硕士学位论文第2 章点云模型的移动最小二乘曲面重构法 总之，m l s 方法通过对原有的点云模型进行投影重采样，除去了噪声和冗余 数据，从而使新点云模型更加准确描述原模型，因此重构的曲面更加光滑和准确， 具有前述特性。 2 2 移动最小二乘法的原理及数学模型 基于为点云模型建立隐式表达的想法，a l e x a 丝 等提出点云模型的m l s 方法， 该方法核心是：定义一个投影的方式，它将在点云模型附近的任何点都投影到曲 面上。随后，使用这些投影点建立m l s 曲面。接下来，将阐明m l s 采用的投影 方式并描述它的数学模型。 2 2 1 投影方法的定义 假设存在曲面通过对它进行采样得到点云模型p 。尸中点a 满足研r 3 ， i e 1 ， n ) 。这里的目标是将s 附近的点r e r 3 投影到二维曲面昂上，它逼近点云 模型尸。下面过程建立在微分几何上，即使用一个函数局部逼近曲面。 1 参考域 为点，建立一个局部的参考域( 平面) 。建立局部平面日= 纠嘲矿d f ) ， 力萨，俐i = l ，满足点云模型p 中点a 到拟合平面距离平方和的最小值。如图2 2 所示，a 将向平面日进行投影。其中，点a 的权值由点p i 到点，在日的投影点 之间距离表示。假设用g 代表，在日上投影，那么通过局部最小化公式( 2 1 ) 获得 矾 ( - d ) 2 0 ( 1 l v ，一q 1 1 ) 公式( 2 1 ) j = l 其中p 是光滑单调递减的函数，并且在其定义域中值恒正。将q = ，+ t n ，距r 3 代入公式( 2 1 ) 中，得到公式( 2 2 ) 。 2o ( i p ，一，- 一叫1 ) 公式( 2 2 ) ，置i 浙江大学硕士学位论文第2 章点云模型的移动最小二乘曲面重构法 定义算确= q = ，+ 铆为公式( 2 2 ) 中具有最小值的投影点，与此对应的局部切 平面日也靠近点，。此时，局部参考域由以平面腱立的正交坐标系定义，其中投 影点g 是该坐标系的原点 图2 2m l s 方法投影原理示意图 2 局部映射 通过，的局部参考域，获得如同2 2 所示的局部二元多项式逼近函数g 。该 函数用来在r 邻域内逼近曲面。令缈表示肌到平面日上的投影，石为这两点之间 的距离，满足公式石= 刀慨d 。由此，通过最小化公式( 2 3 ) 的加权最小二乘误差， 求解函数g 的系数。 r ( g “，弗) 一z ) 2 e ( i l p , 一咖 公式( 2 3 ) 其中( x 棚表示点缈在局部坐标中的坐标值。那么，到曲面踯上的投影，由多项 式在原点的值求出，该计算公式为g + g ( o ，o ) n 。 l e v i n l 2 5 l 等证明了该投影方法构建的曲面满足二维流型的特征，并通过对 m l s 的分析还做出一个推断：只要函数矢r ，那么获得的曲面也无限光滑。 对点云模型曲面的逼近程度很大部分取决于径向加权函数伙力。本文使用 l e v i n 2 6 等建议的高斯加权函数： 烈d ) = p 一2 7 铲 公式( 2 4 ) 其中h 是固定的参数值，反映期望的相邻点之间的间距。通过改变h 值，能将曲 1 2 浙江大学硕士学位论文第2 章点云模型的移动最小二乘曲面重构法 面s 上的一些特征光滑化，这些特征满足s i z e h 。更特别的是，小值h 能使 公式( 2 4 ) 更加快速的退化，而且使函数逼近更加局部化。相反，大值h 产生更加 全局化的逼近，并且能光滑化曲面的尖锐特征。如图2 3 所示，对点云规模为3 8 8 k 的船模型进行处理时，不同h 值对重构结果将有影响，其中图( a ) 的h 值为3 0 ， 图( b ) 为1 0 。 ； ( a ) ( b ) 图2 3 参数h 对m l s 方法的影响 2 2 2 快速的计算投影 本节讨论如何有效计算投影，选取多项式次数和参数h 。i f 如上节对参数h 的解释，不同参数值在计算时间和特征的保留上会有差别。除此之外，本节还讨 论了如何在效率和准确性之间的达到平衡。 浙江大学硕士学位论文第2 章点云模型的移动最小二乘曲面重构法 对投影方程求解是求非线性最优解问题，如对公式( 2 2 ) 的求解，一般就有多 个局部最小极值点。通常r 是它的最小极值解集中的最小值，这样就保证所得参 考平面日能充分靠近，。对公式( 2 2 ) 进行最小化求解，需要使用迭代方式，每次 迭代都得到一个更小的局部极值。首先，令t = 0 ，因此得到固定权值研= 戗l 慨- d 1 ) ， 并其代入公式( 2 2 ) ，得到下列公式( 2 5 ) ： 2 只，2 = 矽( | b 一弗 公式( 2 5 ) i = l 公式( 2 5 ) 是以以为变量的二次函数，通过将它的梯度，见公式( 2 6 ) 设值为0 ，可以 对它进行求解。 2 8 , ( p ，一，) 公式( 2 6 ) i - ! 对最初结果使用p o w d l 迭代法进行优化，需要注意公式( 2 2 ) 的全局最小解可能在 f = 0 0 时才能获得。为避免该状况，使用目的权值总和来规范化公式( 2 2 ) 。 对公式( 2 3 ) 的求解过程，类似公式( 2 2 ) ：一旦参考平面日被计算出来，由式 子吠l 慨- g | i ) 代表的权值就可以计算出来。解公式( 2 3 ) 的梯度方程，就求解多项式 逼近函数g 的系数。 2 2 3 时间复杂度和函数性能分析 在整个计算，的投影过程中，使用点云模型中点p ，计算多项式逼近函数系数 时，消耗最多时间。如若不加优化执行，该过程需要0 | ( 加的时间复杂度，其中 是点云模型中点的数目。以下分析两种快速求解加权函数方法带来的效果。 1 当与点r 之间的距离超过一定值，将加权函数设为0 是有效的。令该一定 值为磊，它的取值范围与参数h 相关，因为h 值决定曲面特征的光滑程度。 并用大小为2 d 的单元格对点云模型中的点进行划分，得到一个规则网格。 由于每次投影操作中最多需要8 个这样的单元格，使所需存储空间与点云 模型规模相互独立，因此带来较小的内存损耗。 2 经过分析，当一簇点远离点，时，可将它们归并成一个点。为说明该想法 的可行性，令所有单元格都由八叉树管理。八叉树的每个叶子节点包含点 1 4 浙江大学硕士学位论文第2 章点云模型的移动最小二乘曲面重构法 云模型中的一个点肌，内部节点则包括以该节点为根的子树中点的数目， 还有它们的质心。如果节点尺寸远小于它到，的距离，那么使用节点的质 心计算多项式系数。反之，遍历它的子树。另外，如果节点到，的距离大 于磊，可对这些节点进行忽略。 简单的用精度交换速度的方法要求参考平面日通过所有要投影的点，该要求 当输入顶点比较靠近要定义曲面时是合理的。采取该简化方法，降低了最小化迭 代机制的开销。 投影过程带来的开销很大比重都取决于参数厅，因为需要考虑的点数目更 少，选小值j l 能使投影更加的快速。正如前面所强调的，相对点云模型尺寸，只 要取参数i l 足够小，在投影求解过程中的存储消耗就变得微乎其微了。 2 3 重采样点云模型 初始点云模型也许有大量噪声点，也可能拥有较多冗余数据，或没有足够的 采样点。通过前面m l s 投影方法，可有效的处理噪声点，使新获取的点云模型 更准确描述初始曲面。但该方法不能处理冗余数据或采样点不够这些问题。针对 冗余数据，需要有效的方式进行清除，这里称为向下采样。相对的，对于未有足 够采样点的点云模型，采取向上采样方法进行解决。 2 3 1 向下采样 假设存在一个点云模型，它具有较多的冗余数据。冗余数据的清除方式是进 行多次迭代，每次将对重构曲面影响最小的点进行移除，而该点对曲面的贡献由 曲面定义方式决定。若通过三角化方式重构曲面，那么采用三角化方法依据准则 控制点的重采样过程。这些准则包括曲面上点之间的距离和曲率 2 7 1 ，或是点到曲 面中轴线之间的距离【2 8 1 。在本节，将讨论符合m l s 方法的准则。 投影点印对曲面昂所做贡献可通过比较昂与跟间的差别来衡量。这里的 衡量方法是：通过计算点力到昂埘 的投影距离，近似代表点p l 所做贡献。 点云模型中点的贡献值都被插入到一个优先队列中。每次迭代，将具有最小 贡献值的点从点云模型和优先队列中移除。当移除该点时，由于该操作会影响邻 浙江大学硕士学位论文第2 章点云模型的移动最小二乘曲面重构法 近点，因此它邻近点的贡献值都需重新计算。将该操作反复进行，直到获得期望 点数或所有点的贡献值都高于预先设