（计算数学专业论文）基于三维散乱点的曲面重建和边界检测问题研究(1).pdf

大连理工大学硕士学位论文 摘要 近十几年间，基于海量离散采样数据( 称为点云) 的曲面重建，得到了理论界和应 用领域的广泛重视，成为计算几何的主要研究方向之一。由于采样手段和应用背景的多 样性，国际上已经发展出数十种各具特色的算法。其中许多算法，重建曲面的拓扑正确 性与原始曲面是否带边界有着密切关系，因而如何对采样数据有效地进行边界检测的问 题，引起了普遍关注。本文在总结曲面重建主流算法的基础上，对点云的边界检测问题 进行了研究，提出了一种基于空间正规分割的边界检测新算法。该算法将数据点所在的 空间区域剖分成边长相等的正方体，对包含样本点的相邻方体之间的邻接关系进行一定 的拓扑分类，由此检测出原始曲面边界附近的采样数据点。该算法直接对点云执行，无 须重建曲面网格，并且是一种高效的局部算法，其复杂性为o ( n b gi v ) ，此处为采样 点个数。 本文内容安排如下： 第一章：基于海量离散采样数据的曲面重建。这是对基于点云的曲面重建问题、理 论和算法的进展综述。 第二章：离散曲面的边界检测。介绍离散形式下的曲面边界检测问题及研究进展。 第三章：基于空间正规分割的边界检测算法。我们提出了一种直接对点云的边界进 行检测的算法，并且从理论上证明了该算法的正确性。 关键词：计算几何；逆向工程；曲面重建；边界检测 i 一 基于三维散乱点的曲面重建和边界检测问题研究 r e s e a r c ho ns u r f a c er e c o n s t r u c t i o na n db o u n d a r y d e t e c t i o nf r o m 3 ds c a t t e r e dp o i n t s a b s t r a c t f o rt e no d d y e a r s t h es u r f a c er e c o n s l r u c t i o nv i al a r g ed i s c r e t es a m p l i n gd a t a s e t ( e a a e d p o i n t c l o u d ) h a s b 。e nd e v e l o p e da so n eo f t h em a i nr e s e a r c hs u b j e c t sw i t ht h ew i d ea t t e n t i o no f b o t h t h e o r e t i c a la n d a p p l i e dc i r c l e s d u et ot h ed i v e r s i t yo f t h es a m p l i n ga p p r o a c h e sa n da p p l i c a t i o n b a c k g r o u n d s ，t h e r eh a v eb e e nd e v e l o p e dt e n s o fa l g o r i t h m so fm i s c e l l a n e o u sf e a t u r e s t h e t o p o l o g i c a lc o r r e c t l l e s so ft h er e c o n s t r u c t i o ns u r f a c e sp m d i l c e db ym a n yo f t h e mi si nt i g h t c o n n e c t i o nw i t hw h e t h e rt h e o f i g i n a is u r f a c e s h a v eb o u n d a r i e s t h 苴d b r ei ta t t l a c t sw i d ea t t e n t i o n h o wt oe f f i c i e n t l yp e r f o r mb o u n d a r yd e t e c t i o nt ot h es a m p l i n gd a t a i nt h i st h e s i sw e s u m m a r i z e t h em a i n a p p r o a c h e s f o rs u r f a c er e c o n s t r u c t i o n , s t u d yt h ep m b l e m o f b o u n d a r yd e t e c t i o n f o rp o i m c l o u d s , a n dp r o p o s eal l e wa l g o r i t h mb a s e do nr e g u l a rs p a c es u b d i v i s i o n o u ra p p r o a c hd e t e c t s t h es a m p l i n gp o i n t sc l o s et ot h eb o u n d a r yo ft h eo r i g 砌s u r f a c eb yd i v i d i n gt h es p a t i a lr a n g e w h e r et h ed a t ap o i n t sl o c a t e si n t oc u b e so fe q u a l e d g e - l e n g t ha n dm a k i n gat o p o l o g i c a l c l a s s i f i c a t i o nf o rt h ea d j a c e n tr e l a t i o n sa m o n gt h ec u b e sc o n t a i n i n gt h es a m p l i n gp o i n t s t h e a l g o r i t h mi sp e r f o r m e dd i r e c t l yt ot h ep o 洫c l o u d w i t hn on e e dt or e c o n s t r u c tas u r f a c ef i r s t i t c a l c u l a t e sl o c a l l yw i t ht h et i m ec o m p l e x i t y0 ( l o g d ，w h e r en i st h en u m b e ro f t h es a m p l i n g p o i n t s t h et h e s i si so r g a n i z e da sf o l l o w s ： c h a p t e ro n e ：s u r f a c er e c o n s t r u c t i o nv i al a r g ed i s c r e t es a m p l i n gd a t a s e t i nw h i c hw e s a r n m a r i z et h et h e o r ya n dr e c e n t d e v e l o p m e n t s w i t h r e g a r d t ot h e p r o b l e m o fs u r f a c 2 r e c o n s t r u c t i o nv i a p o 缸c l o u d s c h a p t e rt w o ：b o u n d a r yd e t e c t i o nf o rd i s c r e t es u r f a c e s i nt h i sc h a p t e rt h ep r o b l e ma n d r e c e n td e v e l o p m e n t sa b o u t b o u n d a r yd e t e c t i o n f o rs u r f a c e si nd i s c r e t ef o r m si ss u m m a r i z e d 。 c h a p t e rt h r e e ：ab o u n d a r yd e t e c t i o na l g o r i t h mb a s e d o n r e g u l a rs p a c es u b d i v i s i o n i n t h i sc h a p t e ran e w a l g o r i t h md i r e c t l yd e t e c t i j l g t h eb o u n d a r yo f t h e p o i n tc l o u d i sp r o p o s e d , w i t ha p r o o f o f i t sc o r r e c t n e s s i nm a t h e m a t i c s k e yw o r d s ：c o m p u t a t i o n a lg e o m e t r y ；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 ； b o u n d a r y d e t e c t i o n i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：车豳宰 日期：2 丝盥墨旦! ! 鳗 大连理工大学硕士学位论文 1 基于海量离散采样数据的曲面重建 1 1c a g d 的历史和现状 c a g d ，即计算机辅助几何设计，是一门迅速发展的新兴学科，它的出现和发展是现 代工业发展的要求，又对现代工业的发展起到了巨大的促进性作用。而反向工程又是 c a g d 中一个比较活跃的课题。多年来，国内外学者在c a g d 以及反向工程领域进行了 广泛深入的研究，取得了很多重要的理论与实际成果，并有大量著作和文献面世。 计算机辅助几何设计( c o m p u t e ra i d e d g e o m e t r i cd e s i g n , 简称c a g d ) 这一术语1 9 7 4 年 由巴恩希尔( b a m h i l l ) 与里森费而德( r i s e n f e l d ) 在美国犹他( u m h ) 大学的一次国际会议上提 出，以描述计算机辅助设计( c o m p u t e ra i d e dd e s i g n ) 的更多的数学方面，为此加上“几 何”的修饰词。在当时，其含义包括曲线、曲面和实体的表示，及其在实时显示条件下 的设计，也扩展到其他方面，例如四维曲面的表示与显示。自此以后，计算机辅助几何 设计开始以一门独立的学科出现。 c a g d 主要研究在计算机图形系统的环境下对曲面信息的表示、逼近、分析和综 合。它起源于飞机、船舶的外形放样( l o f i j n g ) - r 艺，由c o o n s ( 1 9 1 2 - - 1 9 7 9 ) 、b e z i e r ( 1 9 1 0 1 9 9 9 ) 等大师于2 0 世纪6 0 年代奠定理论基础。典型的曲面表示，2 0 世纪6 0 年代是 c o o n s 技术和b e z i e r 技术，2 0 世纪7 0 年代是b 样条技术，2 0 世纪8 0 年代是有理b 样条 技术。现在，曲面表示和造型已经形成了以非均匀有理b 样条( n u r b s ：n o n - - u n i f o r m r a t i o n a lb s p l i n e ) 、参数化特征设计( p a r a m e t e r i z e da n dc h a r a c t e r i s t i cd e s i g n ) 和隐式代数曲 面表示( i m p l i c i ta l g e b r a i c s u r f a c e r e p r e s e n t a t i o n ) 这两类方法为主体，以插值 ( i n t e r p o l a t i o n ) 、拟合( f i t t i n g ) 、i 勖( h p p r o x i m a f i o n ) 这三种手段为骨架的几何理论体系。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着几何设计对 象向着多样性、特殊性、和拓扑结构复杂性靠拢这种趋势的日益明显，随着图形工业和 制造工业迈向一体化、信息化和网络化步伐的日益加快，随着激光测距扫描等三维数据 采样技术和硬件设备的日益完善，c a g d 在近年来得到了长足的发展。这主要表现在研 究领域的急剧扩展和表示方法的开拓创新。 从研究领域来看，c a g d 技术已从传统的研究曲面表示、曲面求交和曲面拼接，扩 展到曲面变形、曲面重建、曲面简化、曲面转换和曲面位差：从表示方法来看，以网格 细分( s u b d i v i s i o n ) 为特征的离散造型与传统的连续造型相比，大有后来居上的创新之势。 基于三维散乱点的曲面重建和边界检测问题研究 而且，这种曲面造型方法在生动逼真的特征动画和雕塑曲面的设计加工中如鱼得水，得 到了高度得运用。 计算机辅助几何设计是随着航空、汽车等现代工业的发展与计算机的出现而产生和 发展起来的一门新兴学科。尽管研究对象扩展到四维曲面的表示与显示等，但其主要研 究对象仍是工业产品的几何形状。工业产品的形状大致上可分为两类：一类是仅由初等 解析曲面( 例如平面、圆柱面、圆锥面、球面、圆环面等) 组成，大多数机械零件属于 这一类，可以用画法几何与机械制图的方法完全清楚表达和传递所包含的全部形状信 息：第二类是不能由初等解析曲面组成，而以复杂方式自由变化的曲线曲面即所谓自由 型曲线曲面组成，例如飞机、汽车、船舶的外形零件。显然，后一类形状单纯用画法几 何与机械制图是不能表达清楚的。 在制造飞机和船舶的工厂里，传统上采用模线样板法表示和传递自由型曲线曲面的 形状。模线员与绘图员用均匀的带弹性的细木条、有机玻璃条或金属条通过一系列点绘 制所需要的曲线即模线，依此样板作为生产和检验的依据。在曲面上没有模线控制的部 分取成光滑过渡。这种采用模拟量传递信息的设计制造方法所表示与传递的几何形状因 人而异，要求设计与制造人员付出繁重的体力劳动，设计制造周期长，制造精度低，互 换协调性差，不能适应现代航空、汽车等工业的发展。人们一直在寻求用数学方法唯一 地定义自由型曲线曲面的形状，将形状信息从模拟量改变为数值量。由此而来的大量计 算工作手工无法完成，只能由计算机来完成。随着计算机的出现，采用数学方法定义自 由型曲线曲面才达到实际应用的地步。这导致了本学科的产生与发展。依据定义形状的 几何信息，应用本学科所提供的方法，就可建立相应的曲线曲面方程即数学模型，并通 过在计算机上执行计算和处理程序，计算出曲线曲面上大量的点和其它信息。期间，通 过分析和综合就可了解所定义形状具有的局部和整体的几何特征，这里实时显示与交互 修改工作几乎同步进行。形状的几何定义所有的后置处理( 如数控加工、物性计算、有 限元分析等) 提供了必要的先决条件。 在形状信息的计算机表示、分析与综合中，核心的问题是计算机表示，即要找到既 适合计算机处理且有效的满足形状表示与几何设计要求，又便于形状信息传递和产品数 据交换的形状描述的数学方法。 关于实体造型的理论的发展落后于曲线曲面，虽然近几年来已取得了很大进展并进 入实际应用，仍不及曲线曲面理论那么成熟。 一2 一 大连理工大学硕士学位论文 1 2 逆向工程与曲面重建 反向工程( r e v e r s ee n g i n e e r i n g ) ，是国外近几年随着c a d c a m c a e ( 计算机辅助 设计制造工程) 的迅速普及而发展起来的崭新的信息科学领域。c a d c a m c a e 技术使 人们能够借助计算机工具，十分方便地通过数字模型生成实体模型。然而，实际工程中 经常需要将物理实体转化为数字模型，以便用计算机进行处理。实现这一过程的科学方 法，就是所谓的反向工程。显而易见，反向工程具有极大的普遍意义和实用性。它与 c a d c a i c a e 相辅相成，互为补充，共同构成一个强有力的工具，使得人们可以在实体 模型与数字模型之间、物理实体与虚拟现实之间自由地往来。 反向工程在娱乐、工业设计和加工、医学、仿真与虚拟现实及网络等领域具有广泛 的应用。在电影、游戏、动画、电视等娱乐产品中三维光滑模型的创建，传统的方法是 用取样器将艺术家制作的小模型一点点地输入到计算机中，既费时又费力，反向工程可 提供一个便捷而有效的工具。与娱乐业三维光滑模型的创建过程类似，在玩具、汽车和 飞机零部件等工业产品的制造过程中，现有的c a d c a m 软件也不能很好地解决这些实体 的数字模型的建立问题，同样，反向工程是处理这些问题的强有力的工具。在医学领 域，经常需要用c t 或磁共振的切片图像建立三维数字模型，这密切依赖于反向工程。在 网络领域，反向工程也将发挥重要的作用。随着立体电视、电子商务等科技的发展和产 业的需要，三维数据传输必将成为网络技术的重要研究课题，反向工程是不可缺少的工 具。此外，在仿真和虚拟现实的领域中也能遇到大量的反向工程问题。从广义而言，二 十世纪九十年代末提出的“数字地球”计划，本身就是一个规模巨大的反向工程。 反向工程有两个主要的研究内容：一是实物模型表面数据获取技术；二是曲面重构 技术。数据获取技术的发展为我们处理复杂物体模型提供了可能。例如，在医学图像可 视化中常用c t 切片来得到人体内脏器官表面的三维数据。采样工具获取的实体表面数据 通常是稠密的点集( 称为点云) ，曲面重构技术就是根据获取的“点云”来恢复原始曲 面的几何模型。 以点云或者多边形模型为基础来进行实体表面的曲面重构，必须考虑以下两个问 题：一是曲面数据散乱而且实体表面形状复杂；二是物体表面通常难以用一片曲面构 成。 目前，反向工程的处理过程可以大致分为以下几个主要步骤： 1 提取样本点。通常的方法是用三维扫描仪( 3 ds c a n n e r ) 将样本点的三维坐标提取到 计算机中形成点云( p o i n tc l o u d ) 。点云是一种形象说法，说明样本点是海量的， 一3 一 基于三维散乱点的曲面重建和边界检测问题研究 像一团云彩一样稠密。显然这种数据形式既不便于保存又不便于处理，并且是无序 的，即点与点之间的邻接关系并不清楚；如图1 1 所示。 2 由点云形成多面体模型( p o l y g o nm o d e l ) 。该过程的主要目的是整序( 建立点云的 空间结构) 、初步参数化和数据压缩；如图1 2 所示。 3 形成( 空间) 四边形剖分( 四边形的边不必是直线) ，即将多面体模型分解为满足一 定条件的( 空间) 四边形的并，迸一步将其适当参数化；如图1 3 所示。 4 在第3 步的基础上形成n u r b s ( 非均匀有理b 样条) 曲面模型。如图1 4 所示。 图1 1 点云模型 f i g u r e1 1p o h a tc l o u dm o d e l 图1 3 四边形模型 f i g u r e1 3q u a d a n g u l a t i o nm o d e l 图1 2 多边形模型 f i g u r e1 2p o l y g o n a lm o d e l 图1 4 m m b s 模型 f i g u r e1 4n u r b sm o d e l 我国浙江大学、中国科技大学、北京航空航天大学、吉林大学、大连理工大学等单 位对多元样条、b e z i e r 曲面、隐式代数曲面、单个n u r b s 曲面等进行了多年富有成果 4 一 大连理工大学硕士学位论文 的研究；清华大学、上海科技大学、广州军医大学等单位在医学图像重建方面做了许多 工作。 伴随着计算机图形技术的发展，几何造型技术不仅可应用于原有的外形设计，还广 泛应用于机械制造、医学可视化、虚拟场景生成、铁路勘察设计与环境工程，地形地貌 描述、矿藏储量图示、气象、影视等众多领域。几何造型技术的发展促进了它的应用领 域的扩大，反过来应用领域的扩大又丰富了几何的表示形式，促进了造型手段和造型方 法的发展。在c 删c a g d 中，曲面造型是一个有着较长历史的领域，6 0 年代初期就已 经诞生。1 9 6 3 年f u g e r s o n 4 提出将曲线曲面表示为参数向量函数形式，并引入参数三次 曲线，构造了组合曲线和由四个角点的位置矢量及两个方向的切矢定义的f u g e r s o n 双三 次曲面片。在此之前曲线曲面都是采用普通的函数表示形式y = f ( x ) 和z = f ( x ，y ) 或它们的 隐式方程表示形式。1 9 6 4 年，c o o n s 5 ，6 】发表了一个更具一般性的曲面描述方法，即一种 由四条边界曲线确定的参数曲面积c o o n s 曲面片，从而使分片表示完整曲面称为可能。 但这两种曲面都存在形状控制和光滑拼接问题。s c h o e n b e r g 利用样条函数成功解决了曲面 片之问的拼接问题，并解决了插值问题。但插值样条曲线曲面的自由度较少，所以难以 用于自由型曲线曲面的设计。b e z i e r 7 于1 9 7 1 年发表的由控制多边形定义曲线的方法， 并将其成功的用在自由型曲线曲面设计系统u n i s u r f 中。后来f o r r e s t 【8 对最初的b e z i e r 曲线形式做了重新处理，得到了当前常用的基于控制顶点b e m s t e i n 基表示的b e z i e r 曲线 曲面的形式。 b e z i e r 方法是一种由控制多边形( 网格) 定义曲线曲面的方法，从几何变换的角度来 说，即是把b e z i e r 控制网格变换为b e f i e r 曲线曲面，是一种映射关系。这种曲线曲面具 有一系列如几何与仿射不变性、凸包性、保凸性、对称性、端点插值性等优良形式；且 具有如d e c a s t e l j a u 求值、离散、升阶、插值、包络生成算法等简单易用的计算方法，很 好地解决了整体形状控制问题。b e z i e r 方法仍存在拼接问题和局部修改问题。 b e 商e r 曲线的优点在于，曲线曲面的形状的改变只需简单的移动控制顶点就可实现， 因而具有良好的交互性。在这个基础上人们又陆续提出三角域上的张量积曲面和 b e m s t e i n 曲面( 即b b 曲面) 。 b e 五e r 曲线曲面的不足之处在于它缺少局部性，而且在处理曲面片之间的光滑拼接方 面也存在困难。曲线上任一点都与多变形的所有顶点相关因此对控制多边形的任何修改 都会影响到曲线的整体形状，7 0 年代初d e b o o r 9 和c o x 1 0 1 分别独立提出了b 样条的 d e b o o r - c o x 递推公式，使b 样条曲线曲面得以广泛的应用。1 9 7 4 年g o r d o n 和r i e s e n f e l d 首次将b 样条理论应用于外形设计，较好地克服了b e z i e r 曲线曲面在局部控制方面的不 一a 一 基于三维散乱点的曲面重建和边界检测问题研究 足。但是上述方法不能精确表示圆锥截面和球面椭球面等初等解析曲面，为此v e r s p r l l l e 于1 9 7 5 年提出有理b 样条方法来克服上述缺陷。有理b e z i e r 曲线曲面不仅能表示自由曲 线、曲面，而且能精确表示圆锥曲线、二次曲面与旋转曲面，因而获得广泛的应用 1 1 , 1 2 ，1 3 ，1 4 。最后在p i g e l 和t i l l e r 等许多学者的努力下，在8 0 年代后期形成了丰富的 非均匀有理b 样条( n o n - u n i f o r mr a t i o n a lb s p l i n e 缩写为n u r b s ) 1 7 ，1 6 的一整套理论和 方法，因为它在外形表示方面的强大功能和潜力，n u r b s 已被作为工业产品数据交换 的s t e p 标准，也被作为描述工业产品几何形状的唯一数学方法。把有理和非有理b e z i e r 曲线和b 样条曲线曲面及圆锥曲线和初等解析曲面统一在一种表示之中，最终使n u r b s 成为c 胱舢行业的工业标准。 在数学和计算机科学中，通常也用隐函数来定义几何物体。不等式f ( x ，y ，z ) 0 描述 了空间中的半空间( 即实体) ，等式i ( x ，y ，z ) = 0 可定义为该半空间的边界( 即隐式曲 面) ，这种曲面表示方法在几何造型和图形学中也得到了诸多的应用。参数化表示具有 许多优点，如计算曲线曲面的几何量较简单，曲线曲面的显示方便，具有离散等优良性 质。然而，在另外一些几何操作，如判断一个点使否在曲线或曲面上以及在哪一侧时， 参数化表示又极为不方便。与之相反，隐式化表示给这些操作带来了极大的方便。同 时，隐式化表示在曲线曲面求交方面也有及其重要的应用。因此，在c a g d 中，也越来 越多的使用曲线曲面的隐式化表示。 为了解决任意拓扑上的曲面造型，人们提出并发展了细分曲面( s u b d i v i s i o ns u r f a c e ) 造 型方法。细分曲面时一类采用组成曲面的多边形网格点、线、面及其拓扑信息完整的描 述的曲面，这个多边形网格可以从手工模型上输入，也可以从激光扫描输入。它与连续 函数所描述的曲面在方法和数据结构上有着本质的区别。其基本方法是：从初始多面体 网格开始，按某种规则，递归的计算新网格的每个顶点，这些顶点都是原网格上相邻的 几个顶点的加权平均。随着细分的不断进行，控制网格就被逐渐磨光。在一定条件( 一 定的细分规则) 下，细分无穷多次之后多边形网格将收敛到一张光滑曲面。细分曲面的 最大优点就是算法简单，几乎可以描述任意复杂的曲面，显著的压缩了设计和建立一个 原始模型的时间。而且，这种曲面造型方法在生动逼真的特征动画和雕塑曲面的设计加 工种如鱼得水，得到了高度运用。 人们在发展了曲线曲面得多种表现形式得同时也创造出了曲线曲面得各种构造技术和 方法，包括变形曲面构造技术、散乱点拟合造型技术、蒙皮( s k i n n i n g ) 造型技术、广义 s w e e p i n g 造型技术、基于变分原理得造型技术以及分形造型技术等许多方法。随着应用 领域得扩大和对造型质量要求的提高，人们还是不断地发展新的造型方法。 一6 一 大连理工大学硕士学位论文 随着计算机图形显示对于真实性、实时性和交互性要求的日趋增强，随着几何设计对 象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的日益明显，随着图形工业和制造 工业迈向体化、集成化和网络化步骤的臼益加快，随着激光测距扫描等三维数据采样 技术和硬件设备的日益完善，曲面造型在近几年来得到了长足的发展。 1 3 基于点云的曲面重建方法 近年来基于散乱数据的曲面重建引起了国内外众多学者的广泛关注，提出了一系列 曲面重建的算法。曲面重建主要有两大类，一类是基于三角剖分的曲面重建，一类是基 于正规空间分割的曲面重建。下面我们将其做一简单介绍。 1 3 1 基于正规空问分割的曲面重建算法 1 w i l l i a me l o r e n s e n 和h a r v e y e c l i n e 的m a r c h i n gc u b e 方法 2 】 m a r c h i n gc u b e 方法是对3 d 医学数据的常密度曲面创建三角形模型。 算法简述： ( 1 ) 将空问样本点集分成大小相同的小方体。 ( 2 ) 决定曲面与小立方体的相交位置并且创建三角片。 ( 3 ) 为每一个三角形的c e d - 顶点计算一个单位法向量，以便产生g o t t r a u d - s h a d e 图像。 步骤( 2 ) 是决定曲面与小立方体的相交情况，主要分为以下几步： 确定方体顶点与曲面的位置关系。 如果在立方体顶点处的值大于等于曲面的值，将立方体这个顶点处的值分配为1 ，这 个顶点在曲面的里面或者是在曲面上。若方体的顶点值小于曲面的值，则这个顶点位于 曲面的外部，将它的值分配为0 。 找到曲面与方体的相交位置，确定曲面在方体里的拓扑。 每个方体有8 个顶点，每个顶点有两种状态( 标记为“0 ”或1 ) ，因此曲面与小立 方体的相交情况有2 5 6 种。根据立方体顶点处的标记，我们创建一个表来观察曲面和边 的相交l 青况。根据相反和旋转两种对称性，我们将相交情况减少到1 4 种。最简单的情形 是，8 个顶点均标记为0 ，此时方体内没有三角片。如果一个顶点标记为l ，其它的顶点 标记为0 ，则方体内只有一个三角形。其余的情形均有多个三角形。以顶点的状态为基 础，我们对每种情况创建个下标。由于此下标表明哪条边与曲面相交，我们可以沿着 这条边来插值曲面。注意，每个方体种至少有一个，至多有4 个三角片。 步骤( 4 ) 具体如下： 一7 一 基于三维散乱点的曲面重建和边界检测问题研究 由于样本是常密度的，所以在曲面的切平面方向有一个零梯度组成部分。相应的， 梯度向量唇的模吲非零，则季方向垂直于曲面。利用这个事实，可以计算曲面的法向量 亓。因此，为了估计曲面的梯度向量，首先要估计方体顶点处的梯度向量然后线性插值相 交点处的梯度。 方体顶点处( f ，j ，) 的梯度，沿3 个坐标轴利用中心差分来得到。 g ，( f ，j ，i ) ；盟丛盟兰幽 g y ( f ，j ，七) ：旦照丛生生；丛生上二塑，其中d ( f ，j ，七) 在第k 层象素( f ，) 处的密度， 掣 g ；( f 肌j ) ：堕丛避型盟业 f ，缈，缸是方体边长。 对此梯度进行单位化，得到顶点处的单位法向量。 2 a 1 9 0 玎i 和s c h m i t t 方法【3 】： 算法简述： ( 1 ) 先把给定的空间数据点集细分为相同的小立方体，小立方体的长度必须大于任意 两个数据点之间的距离。 ( 2 )抽取至少含有一个样本点的小立方体。 ( 3 ) 用曲面跟踪法( f a s ts u r f a c et r a c k i n gi nt h r e e - d i m e n s i o n a lb i n a r yi m a g e s ) 抽取由不被任 何两个小立方体共享的四边形即外表面组成的曲面。 ( 4 )为了得到曲面的更满意的表示，连接由步骤( 3 ) 得到的每个四边形的其中一条对 角线，从而每个四边形变成了两个三角形。并用低通过滤器( 1 0 wp a s sf i l t e r ) 的方 法来光滑得到的曲面。它给每个三角形的顶点重新分配一个位置。得到的新位置 是其原来位置和它的邻居位置的加权平均。 ( 5 ) 为了得到曲面的进一步的逼近，将前面得到的曲面看作一个自适应网格。a l g o r r i 和s e h m i l t 把给定的三角形网格转换成物理模型。将网格顶点看作是质点，边用弹 簧代替。每个质点和它在样本点中最近的点用弹簧连接( 最近点在原c u b e 和它的 2 6 个邻居c u b e 里边找) 。质点和弹簧为了使三角网格向数据点变形。模型可以用 二阶的线性微分方程 “争+ 托警+ 。七，伍，一- ) + k a p 。一x 。) = 。 8 一 大连理工大学硕士学位论文 来表示。其中x t 是节点i 在时间t 的三维坐标k ，y ，z 】，h 和一是关于节点i 的 质量和阻尼系数，k ，是节点i 和节点j 的弹簧的冈q 度系数，k 。是节点i 连到离它 最近节点x 。的弹簧的刚度系数，方程可以用显式的欧拉积分方法来解。 3 h o p p e 的方法【l8 】 算法简述： ( 1 )先把给定的数据点集细分为相同的小立方体。 ( 2 ) 计算每个立方体顶点的带符号的距离，选择那些顶点距离符号相反的小立方体。 显然曲面将穿过这些立方体。 ( 2 ) 面用m a r c h i n gc u b e 算法得到。对于一个立方体顶点处的距离值的符号的每种可能 的图形，m a r c h i n gc u b e 算法定义了相应的分离曲面片的模板。用这些三角化的面 片代替这些小立方体。 在步骤( 2 ) 中顶点的符号由有向距离函数得到。有向距离函数的计算如下： 现对每一个样本点p 计算一个有向切平面。该切平面是由p 。和它的k 个邻居点通过 最小二乘拟合得到的。用一个中，t b 和一个法向量来表示该平面。中心d 。是p ，的k 个邻居 点的质一t b ( c e n t m i d ) 。法向量j ；，由k 个邻居点的协方差矩阵得到。该3 3 半正定对称阵 为： c v = ( y d j ) 固o o i ) y e n b h d ( 置) o 表示外积，如果硝石刀表示c v 的特征值，对应的特征向量为科，辞，口? 。我们选 择自。为印或者一$ 0p 是任意点，它到一个切平面的距离为： ，) = 如，0 ) = 0 一d f ) 癣 0 ，是离p 最近的切平面的中心。 计算p 在硒k ) 的投影z ：z - 0 一 一d f ) 露弦， i f d ( z ，x ) 图1 5 被从视点发出的光穿透的体素是伪数据 f i g u r e l 5v o x e l sw h i c h a r ep i e r c e do f e n ( u n f i l l e dc i r c l e ) r a y sf r o mv i e wp o i n t sa r el i k e yt ob es p u r i o u s 一1 0 _ 人连理工大学硕士学位论文 ( 4 ) 对每个点计算法向量。对每个点，在它所在的小方格内找到和它最邻近的两个 点，利用这些点来计算法线。它的方向的确定：假设我们从无穷远处沿着轴 ( + x ，y ，z ) ，来看小方格，能被看见的小方格里面的法线点一定沿着视点方向， 计算这些可见点的法向量。将这些法向向它的邻居方格传播。如图1 6 所示。 ( 5 ) 利用一个r e l a x a t i o n 方法来光滑法向量。这个算法将每个小方格的法向量计算为 它的邻居方格的加权平均。 殁汉 殁妓 殁 ) (致 致k妓x 图1 6 在体素切片上设定法向符号，黑点设为垂直于视角方向，白点由法向扩散设定 f i g u r e l 6s e t t i n g t h en o r m a ls i g n si nav o x e ls l i c e ：u n t i t l e dc i r c l e sa r es e tf r o mt h e o r t h o g o n a l v i e wd i r e c t i o n s , w h i l ef i l l e dc i r c l e sa r cs e tb y n o r m a l p r o p a g a t i o n ( 6 ) 运行m a r c h i n gc u b e 算法得到三角形。它是一个i s o s u r f a c e 算法，它抽取一个有向 距离函数的零集。有向距离函数由三维数据点和它们的法向量来创建。每一个小 基于三维散乱点的曲面重建和边界检测问题研究 方格顶点处的有向距离，我们称之为域值。它是通过计算邻居方格里的每个点的 有向距离的加权平均得到的。知道了顶点处的域值，利用线性插值，可得到被重 建曲面和小方格的每条边的交点。每一个交点是最终三角剖分的一个顶点。 ( 7 )“补洞”。以上得到的模型往往有小的“缝”或者“洞”。这就要把它补上。首 先找到没有连到其他三角形的三角形边，这些边叫做自由边，表明是三角剖分的 一个洞。一个“洞圈”是一个有方向的自由边的闭序列。该方向是用“右手”法 则得到：把右手的拇指指向三角面的法向，那么右手食指指向的方向就是自由边 的方向。对“洞圈”的自由边的遍历方向和自由边的方向相反。然后利用“洞 圈”边的顶点拟合一个平面，把这些顶点投影到该平面。在洞圈中检查自交情 况，如果没有自交，在该平面对投影的“洞圈”进行三角化，然后对三维的“洞 圈”进行同样的三角化。 ( 8 ) 颜色和强度映射。将离三角形顶点最近的数据点的颜色和强度值分配给此顶点。 ( 9 ) 删除孤立的网格区域。当第4 步还留下噪声点，这些噪声点被三角化后，容易产 生小的、孤立的三角网格区域。利用三维连续算法找到最后网格的每个连续的三 角区域集的大小，那些只含有少量三角形的区域被删除。 ( 1 0 ) 计算最终网格的精确性。对每一个数据点，计算它与离它最近的三角形的距离。 然后寻找所有数据点的这些晟近距离的最大值。这个最大值应该小于方格的最长 边的大小。 5 b i t t a r 的方法 2 5 】 为了由采样于物体表面的散乱数据点来重建一个3 d 实体，该方法将中轴和隐式曲面 结合起来。得到的表达式是以由骨架产生的i s o s u r f a c e 为基础的。该方法是建立在一个代 表数据点集和i s o s u r f a c e 之间距离的个能量的晟小化的基础上的。为了得到更为精确的 曲面，该重建算法以一个局部能量准则逐渐地从计算出来的中轴中选择骨架点。它能够 重建具有复杂拓扑和几何的物体。 该方法先计算曲面的中轴，得到了曲面的骨架( s k e l e t o n ) ，以中轴为中心的一系列 最大球得到了曲面的一个逼近。然后在每个骨架点上定义一个标量函数，隐式曲面就是 这些标量函数之和等于某个给定值的方程。 设s 是包含在对象内部的球的集合。 最大球：不包含在s 中的任意其它球的球。 中轴：中轴就是对象的最大球的中心，相关的还有它的半径。 该方法分为两步： 一1 2 大连理工大学硕士学位论文 ( 1 ) 计算中轴： 空间剖分：包含数据点的小方体标记为“b o r d e rv o x e l s ”，表示它们会与曲面相 交。 标记内部方体：先标记外部方格，从位于3 d 方格的角上的一个方体起，将“外 部”信息传播到它的所有未被标记的邻居方体。 “i l l d _ e rv o x e l ”是在这个过程之后 没有达到的方体。边界方体没有完全包含在物体中，我们不将它们看作是“i n n e r v o x e l ”。 d i s t a n c e - m a p 计算和中轴提取。一旦定义了物体的边界和内部，就可以计算一个 d i s t a n c e - m a p ，它给出了物体的每个内部方体和外部的距离。 ( 2 ) 计算隐式曲面。基本思想是逐渐地选择一些中轴元素，并利用相关的域函数将它 们转化成骨架，通过调整参数来重建精确的曲面。选择合适的解析度的最大球来 表示曲面很重要。解析度太低，会使曲面失去细节。解析度太高，曲面会出现不 连续。隐式曲面由一组骨架s 。( j = 1 , 2 ，n ) 相应的标量函数z 定义： s = 扫r 3l 厂0 ) = i s o ，) = z 幻) 。 其中i s o 是一个给定的标量值。现定义： z 0 ) = 一k ，+ 女，p 。+ l如果r 【o ，q 】 ，。) = 生墨量i 云铲( r 一置) 2 如果r e k ，r 】 - ，：0 ) = 0 其它 其中，= dp , s i ) ，r = 卜一詈 是影响域半径，巳是骨架点s 最大球半径。在重 建过程的每一步，为了使曲面更好地和数据相吻合，加入了一些原型( p r i m i t i v e ) 。选择 的标准是：c ，：量( 厂b 川) 一i s 。r 个在墨影响球内的点p , i , t 选择具有最大g 的原 型。 重建算法： 我们把标记“c h o s e np r i m i t i v e ”和每个中轴的元素关联，以便表明它是否被插入了隐 式曲面。同样，为了表示点是否在一个已被选择的球的影响范围，我们把“c h o s e n p o i n t ”和每个数据点关联。在当前步： 一1 3 基于三维散乱点的曲面重建和边界检测问题研究 ( 1 ) 每个点的“c h o s e n p o i n t ”标记要重设。 ( 2 ) 只要数据点没有被选择： 计算每个基于没被选择的点的没被选择的原型的局部标准c i 且 有最大e 的原型标记为“c h o s e n p r i m i t i v e ”，它的影响域的数据点标记为 “c h o s e np o i n t ”。 ( 3 ) 被选择的原型的参数e 。和k 被优化。 ( 4 ) 所有骨架定义的隐曲面的参数都要被优化，这允许用更少的骨架重建。 在优化步骤中，本着能量最小的原则，能量e 定义为： ，厂、 e 去【等) 一加) 2j 其中 m m 为数据点的数目o 1 3 2 基于三角剖分的曲面重建算法 1 b a j a j 、b e m a r d i n i 等人的方法【1 9 】 给定样本点集p = 缸，儿，z 。) ) c r 3 和相关值矿= c r ，i = 1 , 2 ， 。假设p 取 样于r 中的区域d j w 取样于d 上的某个标量函数f 。要建立一个c 1 光滑的分片多项式 曲面s 。：，o g ，弘z ) = 0 和某个包含样本点集p 的区域上的一个c 1 光滑的分片多项式函数 s ：f 5 k y ，z ) = 0 。使得： 匕：芝：蜀：；，其中占。，占是用户自定义的参数。 算法简述：首先对给定的数据点进行三维的d e l a u n a yu i a n g u l a f i o n 。并且计算它的 v o r o n o i 图和一组d s h a p e s ，利用d s h a p e s 来计算区域s o