（机械制造及其自动化专业论文）反求工程中点云三角化算法的研究及其实现.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得澎姿盘茎或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：溜丹丹 签字日期：? 占年3 月8 日 学位论文版权使用授权书 本学位论文作者完全了解逝望盘堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权逝鎏盘鲎可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：潘丹订 签字日期：沙护6 ，年；月艿日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 刎左一 签字日期：可p 6 年；月占f 电话 邮编 浙江大学硕士学位论文 摘要 反求工程技术是结合当前先进的激光扫描技术和几何造型技术的一种新的 实体建模技术。当前的激光扫描技术能够获取各种拓扑结构的机械零件的点云数 据，其测量精度能够满足反求工程技术重建实体模型的需要。几何造型技术一直 是c a d c a m 的核心技术和研究基础，主要研究在计算机中表示、设计、显示 和分析复杂三维形体的理论和方法。这两种技术的发展使得反求工程成为当前的 研究热点，是企业实现产品设计现代化、缩短设计周期、提高产品质量、增强市 场应变能力和生存能力的又一种强有力的技术手段。 在反求工程技术中，对实体的描述存在多种模型。点云模型运用三维空间的 离散点集来表示物体，最大的优点在于可以表示任意物体，易于进行布尔操作。 三角网格模型形状简单，便于计算，而且可以表示任意拓扑结构的物体，能以任 意精度逼近曲面物体，已经成为各种造型系统的标准表示方法之一。参数曲面模 型一直是描述几何形状的主要工具，广泛应用于飞机、汽车、轮船等具有复杂外 形的产品设计与制造中。由于参数化表示具有与坐标轴无关，可直接进行几何变 换以及几何不变性等优点，它已经成为c a g d 中曲面的主要表示形式。三种模 型之间可以通过各种重建方法相互转换。 反求工程中实现点云的三维模型重建有多种反求策略，其中最常见的反求策 略是首先通过三维激光扫描仪在物体表面测得一些离散点，然后用数据预处理技 术对点云进行压缩、去噪等处理，再用散乱点重构算法生成三角网格模型，最后 基于网格模型进行网格优化、压缩、区域分割后，重建点云的参数曲面模型。 本文研究了反求流程中的点云三角化算法及其实现。通过对现有成果的研 究，改进和实现了一种基于曲面局平特性，在投影平面内重建某个采样点的 d e l a u n a y 三角化，然后在边界点上进行区域增长的点云三角化算法。该算法基 于半边数据结构和四种被证明可完整重建任意拓扑点云的拓扑操作，保证了区域 增长时三角网格一直是流形曲面。该算法对每个点只执行一次操作，时间复杂度 是线性的。只要点云数据在局部满足局平特性，该算法可以可靠稳定地重建任意 拓扑结构的三角网格。各种类型和各种来源的实例也证明该算法的实用性。 该算法已经在反求工程软件r e - s o f t 中得以实现，并应用于各种拓扑结构的 机械零件的三角网格曲面重建。重建的结果再次证明了该算法在时间复杂度和重 建质量上的优势。 本文还研究了基于三角网格的拓扑操作，并指出各种拓扑操作的合法性，实 现了其中换边、删边和删点三种基本的拓扑操作，证明了基于半边数据结构的网 格结构有利于网格的后续操作，包括网格优化、压缩、区域分割等操作。本文还 实现了种减少网格与原曲面二阶属性误差的网格优化算法。该算法在重建尖锐 边处凹凸性有一定作用。 关键词：反求工程点云三角化局平特性拓扑操作半边数据结构网格优化 2 浙江大学硕士学位论文 a b s t r a c t r e v e r s ee n g i n e e r i n gi st h eh o n e s tt e c h n o l o g yi nt h ec a d c a ma r e a , w h i c hi s b a s e do n3 ds c a n n i n gt e c h n i q u e sa n dg e o m e t r i cm o d e l i n gt e c h n o l o g y n e3 d s c a n n i n gm a k e s i t p o s s i b l et og e tt h ed i g i t a lm o d e lo fo b j e c t sw i t ha r b i t r a r y t o p o l o g yt y p e s ，a n dt h ed ig i _ t a lm o d e l sm e e tv a r i o u sa p p l i c a t i o nr e q u i r e m e n t s m g e o m e t r i cm o d e l i n gt e c h n o l o g yp r o v i d e st h et h e o r i e sa n dm e t h o d sf o rr e p r e s e n t i n g a n dc o n s t r u c t i n gk i n d so f c u r v ea n ds u r f a c em o d e l s i ng e o m e t r i cm o d e l i n g , t h e r ea s e v e r a lr e p r e s e n t a t i o n sa n dm o d e l s s u c ha s p o i n tc l o u d ，t r i a n g u l a rm e s ha n dp a r a m e t r i cs u r f a c e p o i n tc l o u dh a st h ea d v a n t a g e si n p r e s e n t i n go b j e c t sw i t hv a r i o u st o p o l o g i e sa n de a s yf o rb o o lo p e r a t i o n s t h a n g u l a r m e s hc a p t u r e so r i g i l l a lo b j e c tt o p o l o g y ，l i n e a r l ya p p r o x i m a t e st h eo b j e c tg e o m e t r y w i t h s i m p l er e p r e s e n t a t i o n ，a n db e c o m e s o n eo fr e p r e s e n t a t i o ns t a n d a r d sf o r g e o m e t r i cd e s i g ns y s t e m s n 圮d e s i g no fp a r a m e t r i cc u l - v e sa n ds u r f a c e sp l a y sa l l i m p o r t a n tr o l ef o rl o n gt i m ei nc o m p u t e ra i d e dg e o m e t r i cd e s i g n b e n e f i t e df r o mt h ed e v e l o p m e n to fs 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 s ，w eh a v e r e a l i z e da na l g o r i t h mt or e c o n s t r u c tam a n i f o l dm e s hf r o mu n o r g a n i z e dp o i n tc l o u d w i t he f f i c i e n c y , r o b u s t n e s sa n df l e x i b i l i t y w h i c h 撇e x p e r i m e n t a l l yd e m o n s t r a t e db y v a r i o u se x a m p l e s t o p o l o g i c a lo p e r a t i o n sa n dt h ed a t as t l u e t u r em a k ei ts u r et o i n c r e m e n t a l l yb u i mat r i a n g u l a rm e s h 、撕t l lt o p o l o g i c a li n t e g r i t y w eh a v ea l s or e a l i z e das e to ft h r e ee l e m e n t a r ym e s ht r a n s f o r m a t i o n s , e d g e c o l l a p s e ，v e r t e xc o l l a p s e ，a n de d g es w a p ，a n dd e f i n e dt h el e g a lc o n d i t i o nf o rt h e t h r e et r a n s f o r m a t i o n s a tl a s tam e s ho p t i m i z a t i o na l g o r i t h mi sr e a l i z e dt om i n i m i z e t h ed i f f e r e n c e sb e t w e e nt h ee s t i m a t e dc u r v a t u r e so ft h et r i a n g l em e s ha n dt h eo b j e e t s u r f a c e 髓ee x a m p l ed e m o n s t r a t e st h ea b i l i t yo fs t r o n gc o n v e x i t yr e c o v e r yo fs h 唧 e d g e s k e yw o r d ： r e v e r s ee n g i n e e r i n gp o i n tc l o u d , m a n i f o l d , m e s ht r a n s f o r m a t i o n , o p t i m i z a t i o n 3 浙江大学硕士学位论文 第一章引言 【内容提要】阐述了反求工程在c a d ，c a m 领域中的应用、反求工程的基础技术激光扫描 技术和关键技术几何建模技术，以及反求工程中的两种反求策略。阐述了点云三角化算法的 研究成果最后指出了本文的任务和论文的结构。 1 1 研究背景 反求工程作为一种新兴的模型重建技术，在过去3 0 多年中得到迅速的发展， 是c a d c a m 领域最活跃的分支之一。反求工程技术应用范围广泛，除了航空、 造船、汽车这三大制造业外，还涉及建筑设计、生物工程、医疗诊断、电子工程、 机器人、服装鞋帽设计等技术领域。例如在仿形设计中，需要克隆某个产品，然 而通常却没有该产品的原始设计草案或文档；又如在零件的修改与改良设计中， 需要从现存的产品出发，构造出他的几何模型，从而可以利用现有的c a d 系统 进行进一步的分析与优化，从而开发出新的产品；在汽车工业等领域，车体外壳 的美学设计显得尤其重要，对于众多设计师而言，他们更喜欢的是在真实的雕刻 或油泥模型上进行设计，实物模型相对于计算机二维屏幕而言更能真实的反映物 体的形状，更有利于设计师阐释他的设计思想；另外，在特制的服装、鞋帽等产 品定制领域，由于每个人的面部，身体结构不同，统一的尺码并不一定适合客户 的要求，又由于批量小，甚至可能就只生产一件产品，用传统的设计方法，冗长 费时，在经济上来说也是不合适的。反求设计方法使传统的正向设计方法与生产 组织模式发生了深刻的变化，为企业实现产品设计现代化、缩短设计周期、提高 产品质量、增强市场应变能力和生存能力、参与国际市场竞争提供了强有力的技 术手段。反求工程技术是结合当前先进的激光扫描技术、几何造型技术和快速成 型技术的一种新的实体建模技术，反求工程结构图如图1 1 。 6 浙江大学硕士学位论文 1 1 1 激光扫描技术 图1 1 反求工程结构图 激光扫描技术是反求工程技术的基础。近几年来，得益于各种低档和高档三 维扫描仪提供的三维几何获取能力的大大发展，把现实世界中的物体数字化成三 维几何模型已经不再困难。最著名的例子是s t a n f o r d 大学的d i g i t a lm i c h e l a n g e l o p r o j e c t ( l e v o y 2 0 0 0 ) ，该项目通过一整套三维扫描硬件和三维重建软件系统完成 了一些大型雕塑的数字化过程，生成的最复杂的模型三维模型包括2 0 亿个多边 形和7 0 0 0 幅彩色图像( 【周昆2 0 0 2 ) ! 现有的三维测量设备很多，基本上可分为 接触式与非接触式两大类。三坐标测量机( c 枷旧是应用最为广泛的接触式测量 设备，它具有噪声低、精度高和重复性好等优点。c m m 应用中比较著名的有英 国r e n i s h a w 公司推出的测头，其测量精度最高可达到o 5 朋l 。另一类方法是 非接触式方法，大多属于光学测量。按照物体被照明方式的不同可分为主动测量 法和被动测量法。从原理上来说主要有三角形法、几何光学法和光外差法等点光 源测量法，线光源测量法，结构光栅测量法，视觉分析法等。其中采用激光作为 光源的三角形法已经走向实用，它利用光源、物体表面反射点和成像点之间的三 角关系计算出表面反射点的空间位置。如果采用线光源，激光扫描测量方法可以 达到很高的测量速度。英国3 ds c a n n e r 公司生产的r e v e r s a 激光测头扫描 速度达1 50 0 0 点s ，测量精度可达1 0 3 0p r o 。结构光法也是正在兴起的一种 三维表面测量方法，它的原理是将具有一定模式的光源，如栅状光条投射到物体 7 h 2 7 则基本可以保证k 邻 域包含p 的d e l a u n e y 近邻，能够基本反映p 的局部曲面形状( p a u l y 2 0 0 1 ) 。综合 上述两种方法，选取邻域点的数量j = 2 8 。 在采样极其不均匀的数据里，无论采用什么样方式计算五和方块长度，都 会产生没有采样点的方块和采样点过多的方块。我们未实现根据点云采样密度的 变化，建立自适应的方块长度。但是一般情况下，2 = 3 ，k = 2 8 ，已经可以适应采 浙江大学硕士学位论文 样较为不均匀的点云。 以下是我们根据上述原理设计并实现的空间栅格划分算法和采样点k 一近邻 搜索算法。 ( a ) 采样点集( b ) 当a = 1 的情况 ( c ) 当a = 3 的情况 图2 2 高尔夫棒头模型 ( d ) 改进后的情况 浙江大学硕士学位论文 空间栅格划分算法 s t e p l ：i 发x m x ，y l n a x ，z m a x ，x m i n ，y m i n ，z m i n 为点云中测量点的 最大、最小x y ，z 坐标，为给定容差，定义以点( x m a x + ，y l i l a x + ， z m a x + ) 和( x m i n 一，y m i n 一8 ，z m i n e ) 为对角点且表面平行于 坐标平面的空间六面体为点云的空间包围盒。 s t e p 2 ：将点云数据的空间包围盒沿坐标轴方向按给定粒度( 栅格宽 度) 五划分为空间六面体栅格，划分的栅格总数： = 降掣d 1 降掣降掣d ( 符号 表示向上取整) 。 s t e p 3 ：对于点云中的任意一个测量点 p ，( ，y t , z j ) 2 ，首先根据其坐标 值计算对应的栅格空间坐标口4 刊，乩孕j ，值计算对应的栅格空间坐标 l j ， l j ， ，2 【孕j ( 符号lj 表示向下取整) ，而后舭 嬲) 存入对应的 栅格g ( 口，) 中。 s t e p 4 ：通过上述算法遍历点云中每个测量点，就完成了点云的空问栅 格划分划分结束后，含有测量点的栅格称为非空栅格，否则为空栅格。 上述划分方法的复杂度为d ( ) ，而常用的基于分割平面的2 叉树分割 方法的算法复杂度为d ( l o g ：“) ，考虑到通常情况下 行，这种分割方 法具有明显的速度优势。 浙江大学硕士学位论文 k 近邻抽取算法 s t e p1 将栅格g 加入集合n ( g ) s t e p2 搜索栅格g 的非空2 6 近邻 季， ：三，若茧萑( g ) ，将它们 加入集合n ( g ) s t e p3 检查n ( g ) 中的测量点数，若点数少于k + 1 则对( g ) 中 的每个栅格执行s t e p2 否则执行s t e p4 s t e p 4 对于砌，户( ( g ) ) u i o ) ， 计算l 1范数 i i p ，o - p 。= x j 0 - - x j l + l y 扩y 小i g l 0 - - z 1 i 。 s t e p5 将慨。一p 。从小到大进行排序，选择最近的k 个点加入r 的k _ 近邻。 上述抽取过程的特点在于a ) 将邻域的搜索范围限定在点集p ( ( g ) ) 内，无需遍历点云中的所有测量点b ) 选择忱。一p 儿代替 8 只。一p ，i i ：= 、( i = i f 习五i 孑了i 习，若将减法的运算时间 设为2 个单位时间，则乘法需要3 个单位时间，开根运算甚至需要7 个 单位时间，本章用l l 范数近似表达l 2 范数使得运算时间明显缩短。 2 2 2 切平面估计 每个采样点的切平面可以通过k - 近邻估计。因为实体表面是一个三维空间中 的二维流形，曲面上每个点都有一个与原盘同胚的邻域范围。采样点p 的切平面 就是对p 点附近的实体表面的局部几何逼近。这个逼近随着采样密度的增加而提 浙江大学硕士学位论文 高。切平面的法矢方向可以是任意的，没有必要与实体表面的法矢一致，因为不 一致的法矢将会在后面的网格构建过程中得到修正。根据p 的k _ 近邻n b h d ( p ) ，得 到对称的半正定矩阵c v = ( p j - p ) ( a - p ) 7 ，通过逆迭代法求解c v 的最小特 l _ e n b h d ( p ) 征向量该特征向量就是方程m i i i = “p j 一们 ) 2 的最小二乘解a 把该特征 p j e n b h d ( p ) 向量单位化就得到p 的估计法矢。点云的数量很大，切平面法矢的估计也在网格 重建算法中占很大一部分时间。因此在第三章的网格构建过程中采用的是一种较 为简单的法矢估计方法。两种方法的比较如图2 3 ，在尖锐处的法矢，一般估计 方法不如简便方法，因为前者的精度取决于全局变量k 值，后者则能更好的反映 局部特性。 ( a ) 采样点集 2 2 3 角度排序 ( b ) 迭代估计法矢 ( c ) 简单估计法矢 图2 3 柱体模型 为了进一步了解p 的k 一邻域的分布情况，在p 的切平面内计算每个邻域点到p 的方向。首先以p 点为原心建立局部坐标系 p ，口。，p ：，岛 ，其中e 3 是p 的切平面法 矢( 局部坐标系的z 轴) ，岛是切平面内的任意方向的向量( 局部坐标系的x 轴) ， 岛= 岛o p 。( 按右手坐标系定义局部坐标系的y 轴) 。p 的邻域点集n b h d ( p ) 内每一 个邻域点见投影到切平面内，得到投影邻域点见。聍= p i - p 表示邻域点只在 切平面到p 点的方向向量。贷表示q 到v i 的逆时针方向的旋转角度。对旋转角度贷 浙江大学硕士学位论文 高。切平面的法矢方向可以是任意的，没有必要与实体表面的法矢一致，因为不 一致的法矢将会在后面的网格构建过程中得到修正。根据p 的k _ 近邻n b h d ( p ) ，得 到对称的半正定矩阵c v = ( p j - p ) ( a - p ) 7 ，通过逆迭代法求解c v 的最小特 l _ e n b h d ( p ) 征向量该特征向量就是方程m i i i = “p j 一们 ) 2 的最小二乘解a 把该特征 p j e n b h d ( p ) 向量单位化就得到p 的估计法矢。点云的数量很大，切平面法矢的估计也在网格 重建算法中占很大一部分时间。因此在第三章的网格构建过程中采用的是一种较 为简单的法矢估计方法。两种方法的比较如图2 3 ，在尖锐处的法矢，一般估计 方法不如简便方法，因为前者的精度取决于全局变量k 值，后者则能更好的反映 局部特性。 ( a ) 采样点集 2 2 3 角度排序 ( b ) 迭代估计法矢 ( c ) 简单估计法矢 图2 3 柱体模型 为了进一步了解p 的k 一邻域的分布情况，在p 的切平面内计算每个邻域点到p 的方向。首先以p 点为原心建立局部坐标系 p ，口。，p ：，岛 ，其中e 3 是p 的切平面法 矢( 局部坐标系的z 轴) ，岛是切平面内的任意方向的向量( 局部坐标系的x 轴) ， 岛= 岛o p 。( 按右手坐标系定义局部坐标系的y 轴) 。p 的邻域点集n b h d ( p ) 内每一 个邻域点见投影到切平面内，得到投影邻域点见。聍= p i - p 表示邻域点只在 切平面到p 点的方向向量。贷表示q 到v i 的逆时针方向的旋转角度。对旋转角度贷 浙江大学硕士学位论文 排序于是p 。，p 咖。“，表示切平面内围绕p 点逆时针排序的邻域点。q 的方向 在网格构建过程中实际上并不是任意的，将在第三章中详细介绍。图2 4 所示k = l o 的邻域分布情况。e i 的方向与其中一个邻域点的方向矢量一样。 lc 2 广 么。 五互 n _ 、p 女 2 3 本章小节 图2 4k - 近邻在切平面上的角度排序 在这一章里对点云数据实行各种操作。数据压缩可以迅速减少点云的数量， 同时保持点云的大致形状不变。通过k 一近邻搜索，切平面估计和k _ 近邻在切平面 上的角度排序，建立每个离散点的邻域结构，初步描述离散点的局部曲面形状。 浙江大学硕士学位论文 第三章点云数据三角化算法及其实现 【内容提要】提出并实现了一种基于曲面局平特性的点云三角化算法。该算法在投影平面内 重建某个采样点的d e l a t m a y 三角化，然后在边界点上进行区域增长基于半边数据结构和 四种被证明可完整重建任意拓扑点云的拓扑操作，保证了区域增长时三角网格一直是流形曲 面。该算法对每个点只执行一次操作，时间复杂度是线性的。 3 1 引言 根据采样方式的不同，有些点云数据除了点的三维坐标外，还有栅格结构或 是轮廓结构等附加信息，利用这些信息可以方便获取采样点的法矢等信息。针对 带有特殊结构的点云数据有不同的网格重建算法，结构稍有不同，算法也就不同。 通常情况下的点云数据都是由多张扫描数据或是图片经过配准拼接而成，数据是 散落无章的。为了使我们的重建算法适应各种点云数据，我们假设点云数据除了 点的三维坐标外没有其他任何附加信息。 点云数据因为只有点的几何位置信息没有点之间的关联信息，只能模糊地描 述曲面的形状。连续的流形曲面则可以较为清楚地描述曲面的形状。三角网格插 值于点云数据，重建点云的拓扑结构，是一种连续的流形曲面，可以作为一种简 单的描述曲面形状的模型。因此重建点云的三角网格模型在近几年来得到广泛的 关注。 对结构复杂或特征繁多的实体，激光扫描仪或是c c d 摄像系统都要对实体进 行多次采集，使得点云数量众多。基于面的区域增长算法是从局部区域生长起来， 不需要中间结构，效果高，尤其适合海量点云数据。我们的算法结合 h u a n g ( 删2 0 0 2 ) 和g o p i ( g o p i 2 0 0 0 ) 的算法，保持了这类算法效率高的优点， 也在一些关键的方面做了改进和提高。该算法的特点是：1 ) 继承了h u a n g 提出 的一种新的数据结构。在该结构上可以方便地对网格进行各种拓扑或是几何的操 作。由于网格的数量众多，在使用前都要进行一些拓扑或是几何操作。比如在网 格基础上拟合b - 样条曲面片( k r i s h n a m r u t h y l 9 9 6 ) ，应用信号处理技术对三角 网格进行曲面光顺( t a u b i n ，1 9 9 5 ) ，用渐进式结构描述网格方便模型的数据传 输( h o p p e ，1 9 9 6 ) 等。2 ) 在区域增长的过程中，使用四种拓扑操作就可完成对任 意拓扑结构的网格重建。不过在构建时要时刻保持当前网格结构的拓扑完整性。 浙江大学硕士学位论文 3 ) 为每一个临时边界点挑选d e l a u n a y 近邻时，采用一种新的选取标准，使网格 满足几何完整性和自动边界检测。4 ) 选取合适的边界检测阈值a 和网格优化阈 值，实现算法的自动边界检测和网格形状优化。 3 2 数据结构 流形网格是原始实体的边界描述，而组合数据结构就是对流形网格中拓扑元 素点、边、面之间拓扑信息的描述，拓扑元素可以用点、线、三角形等几何元素 实现。合理的组合数据结构不仅使构建过程变得简单，而且方便在流形网格上作 几何或拓扑操作，比如减少几何或拓扑信息搜索的时间。在组合数据结构中放入 越多的拓扑信息，可以减少信息搜索时间，但同时增加了内存的需要和构建的难 度。可以根据实际的需要，对几何操作的方便性和构建的复杂性之间做一下协调。 在以往的研究中，已经提出不少的流形网格的组合数据结构，比如有翼边结构 b a u m g a r t1 9 7 5 1 ，点一边和面一边组合结构 w e i l e r1 9 8 5 1 ，边一边和边一面的组合结 构 h u a n g2 0 0 2 。 使用f l u a n g 的边一边和边一面的组合结构可以有效地进行网格构建和几何拓扑 操作，如图3 1 所示。在该组合数据结构中，每一个三角网格由一组面列表组成， 每一个面由三个绕面外法矢方向逆时针排列的半边组成。每一条内部边由两个面 共享，通过两个半边结构表示边一面之间的关系。边的方向从起点指向末点。面 向末点，位于左边的半边称为左半边，右边的称为右半边，分别代表两个关联面。 同时有四个边指针表示边一边之间的关系。处于左半边，又有一个端点为起点的 边称为该边的左起边，依次类推可得到左末边，右起边和右末边。两个半边共享 同一条边，分别以对方为自己的对半边，同时与所在面的对顶点关联。每个顶点 结构中除了该点的三维坐标，还有一条以该点为端点的关联边作为起始边。 用这种数据结构组合的流形网格，可以很容易地搜索到几何操作中所需要的 拓扑信息如顶点y 的边环，面环等。顶点v 的边环指的是与顶点v 相关联的所有 边，并按顶点的法矢方向逆时针排列。边环信息可以通过顶点的点一边信息和边 的边一边信息获得。以下根据数据结构用简单的递归函数即可实现顶点的边环信 息的搜索。 浙江大学硕士学位论文 面信息：i 半边3半边2半边1 半边信息： 顶点信息： 【所在边对半边对顶点所在面 w 图3 1 组合数据结构 浙江大学硕士学位论文 顶点的边环函数 i n p u t ：顶点v ，v 的起始边c u r e d g e o u t p u t ：边列表r i n g e d g e v o i dg e t r i n g e d g e ( v ，c u r e d g e ，r i n g e d g e ) 递归算法 i f c u r e d g e s t a r t vi sv t h e nn e x t e d g e = c u r e d g e s t a r t l e f t ； e l s en e x t e d g e = c u r e d g e e n d r i g h t ；，i 煎时针搜索 r i n g a r r a y a d d ( c u r e d g e ) ： ，加当前边到边环中 i f n e x t e d g ei s v s t a r t eo rn e x t e d g ei sn u l l t h e nr e t u r n ； e l s eg e t r i n g e d g e ( v , n e x t e d g e ，g i n g e d g o 3 3 建网操作 流形网格通过组合数据结构描述曲面的拓扑信息。拓扑信息分全局拓扑和局 部拓扑。全局拓扑指的是曲面的内在拓扑属性，包括欧拉特征值。局部拓扑指的 是曲面中点，边和面之间的局部关联信息。在流形网格的区域增长过程中，由于 增长方向的未定，网格的拓扑结构通过拓扑操作不断地被改变。根据二维流形曲 面的数学属性，在流形网格的区域增长过程中，存在四种拓扑操作：延伸，胶合， 面粘贴和补洞。如图3 2 所示，v 为候选点，v l - v 7 为v 的7 个d e l a u n a y 近邻点， 其中v 2 为自由点，其余为边界点。其中延伸( 3 2 b ) 和面粘贴( 3 2 d ) 属于局部拓 扑操作，只改变曲面的局部结构，整体拓扑属性不变。补洞( 3 2 e ) 和胶合( 3 2 c ) 都是全局拓扑操作，改变了曲面整体拓扑属性。补洞是增加一个三角形，让两条 边界变为一条边界，或是把一条边界围成的洞用一个三角形补完整。胶合就是增 加一个三角形，让一条边界变为两条边界，这样就出现了一个顶点有四条边界边 的情况，不符合流形的定义。通过增加两个三角形的方式使任意时候的网格都是 流形网格。因此在区域增长过程中，三角网格始终保持是流形结构。 浙江大学硕士学位论文 a ) 拓扑操作前 c ) 拓扑操作：胶合 ”拓扑操作：延伸 d ) 拓扑操作：面粘贴 v 2 e ) 拓扑操作：补洞 图3 2 流形网格的拓扑操作示意图 浙江大学硕士学位论文 3 4 建网流程 基于采样点的邻域结构，流形网格的构建过程分为两步：网格初始化和网格 区域增长。在网格初始化程序中，选取z 轴最大点和它的最近的两个点组成三角 形，法矢方向可与z 正方向一致，三个半边绕法矢方向逆时针排列。在网格区域 增长程序中，每一个边界顶点通过可见性标准，在邻域结构中选取d e l a u n a y 邻 域点，运用四种拓扑操作，把每一个d e l a u n a y 邻域点加入到网格中，完成该边 界点的局部区域增长。直到没有采样点可以加入网格，生长过程结束。因为对每 一边界点只执行一次d e l a u n a y 邻域搜索，所以该算法只具有线性时间复杂度。 图3 3 网格重建算法流程 在网格构建时，构建每一条新加入的三角形边时，都是先建左半边，保持右 半边的指针为空。因此在区域增长的过程中，曲面的每一条临时边界上的所有三 角形边的方向都是一致的。每个新加入的三角形与现有网格中的一个有向三角形 共享一条边，排列新加入三角形的顶点次序，使得两个三角形在共边上的方向是 相反的，从而自动确定法矢方向。这体现使用该组合数据结构，可以省去网格构 建时法矢一致性调整的时间。下面为点云三角化算法伪码。 3 3 浙江大学硕士学位论文 3 5d e l a u n a y 邻域选取 o e l a u n a y 邻域选取是点云三角化算法中最为关键的一步，它决定了最终入选 的合法邻域点是否满足流形网格的要求以及最终的网格质量。这里把每一个边界 顶点称为候选点r ，通过可见性标准，在邻域结构中选取1 ) e l a u n a y 邻域点，运 用四种拓扑操作，把每一个d e l a u n a y 邻域点加入到网格中，完成该边界点的局 部区域增长。图3 4 是一个在r 点切平面投影的局部三角网格，圆圈内就是候选 点r 和它的k 个邻域点。其中r 的切平面法矢可以简单认为是r 已有的关联三角 形的平均法矢。每一个d e l a u n a y 邻域点的加入都必须满足三角网格的几何完整 性，最直接的方法是判断新加入的边与局部三角网格的相交情况。相交性判断是 很费时间的。可见性标准则利用r 的邻域结构中已经排好序的邻域点，分为三种 情况进行可见性判断，排除可能相交的邻域点：1 ) r 的可见性点处于r 的两条 边界边的夹角内，所以蓝色的点不可能是r 的d e l a u n a y 邻域点。2 ) 绿色的点也 可不能是r 的d e l a u n a y 邻域点，因为r 不处于该点的可见性区域。3 ) 白色的点 因为该点与r 点的连线与现有网格相交了第三条仍需相交性判断，但是可见性 标准已经大大减少了相交性判断的次数。下面为合法邻域搜索算法的伪码。 浙江大学硕士学位论文 图3 4d e l a u n a y 近邻选取 合法邻域搜索算法 f i n d v a l i d n e i g h o r ( n e i g h b o r l i s t , v a l i d l i s t ) ； i n p u t ：k 个近邻n e i g h b o r l i s t o u t p u t ：合法的邻域点集v a l i d l i s t c r e a t e l o c a l s y s l e m ( ) ；构建局部坐标系 a n g l e o r d e r i n g ( ) ； ，邻域点角度排序 v i s i b l e c d t e r i a ( ) ；- i i 见性标准删除非法邻域点 o p t i m i z e c r i t e r i a ( ) ； 优化标准删除狭长三角形点 把每一个d e l a u n a y 邻域点与r 点相连加入到网格中，存在边界点的判断问 题。离散点云的边界不好判断，通常采用阈值来定量识别。比如口- s h a p e 就直 接用阈值口来识别边界元素，但是口值的选取与原始曲面的特征和采样方法有 关，如果采样密度不均匀，就不存在合理的口值。h u a n g 提出的相同邻域标准自 动识别边界边，一条边界边a 有两个边界点v 1 ，v 2 ，与其相连的一条边界边上b 的另一个边界点v 3 ，必须同时在v l 和v 2 的k 一邻域内，才能成为边界边a 的最 佳点。这实际上还是受全局变量k 的影响。口和k 都是全局变量，而边界边的识 别是与它的局部邻域有关，无法通过一个全局阈值来决定。我们的边界判断，也 只是简单的认为在切平面候选点的两条相邻边的夹角大于阈值口，就认为r 点为 边界点，o 一般为1 2 0 度。有大于1 2 0 度角的三角形已经属于狭长三角形了，在 形状上不满足要求 浙江大学硕士学位论文 r r 图3 5 优化算法 按次序连接d e l a u n a y 邻域点可以构建出局部三角网格，但是这样的网格可 能存在狭长三角形。如果不加入额外的点，是不可能完全避免狭长三角形的。如 图3 5 所示，n 2 r n ，么n 。r n 3 ，么n 。r n 。均为角度少于网格优化阈值( 卢一般 取3 0 度) ，如果相连会成为狭长三角形。如果去掉n 3 ，那么三角形r n , p 就会包 围n 3 ，这不符合构建时的准则( 三角形内部不能有采样点) ，所以即使是狭长三 角形也不能任意删除。我们在连接时采用贪婪算法即尽可能地减少狭长三角形的 数量，分别以r 和p 为中心，对邻域点集排序，r s = n i ，n 2 ，n 3 ，n 4 ，n 5 ， p s = n i ，n 2 ，n 5 ，n 4 n 3 ) 。通过以下伪代码找到可以与r 、p 组成三角形的点。 局部三角网格优化算法 f o r1 f s i 刊 设n j = p s i ； 设置n j f l a g = t r u e ； t ( n j ) = | ) i _ i x 0 ，v - y o ， z o ) ； g l e n d 0 ； 线框模型的显示： g l b e g i n ( g l - - l i n e s ) ； v t x l = e d g e - g e t s t a r t v t x 0 ； v t x 2 = e d g e - g e t e n d v t x 0 ； v t x l - y o ，v t x l - z o ) ； v t x 2 - y o , v t x 2 - z o ) ； g l v e r t e x 3 d ( v t x l - x 0 ， g l v e r t e x 3 d ( v t x 2 - x 0 g l e n d 0 ； 面模型的显示： g l e n a b l e ( o l l i g h t i n g ) ； e n a b l el i g h t i n g b r i g h tw h i t el i g h t - f u l li n t e n s i t yr g bv a l u e s g l f l o a tl i g h t a m b i e n t u = o 4 f , o 4 f , o 4 1 0 母； g l f l o a tl i g h t d i f f u s e 】- 1 o f a o f , 1 o f a o f ； g l f l o ml i g h t s p e e u l a d = 1 0 1 , 1 o f , 1 o c l 0 f ； 弧唧a n de n a b l el i g h t0 g l l i g h t f v ( g l _ l i g h t 0 ，g l _ a m b i e n t , l i g h t a m b i e n t ) ； g l l i g 的( g l - - l i g h t 0 ，g l _ d i f f u s e ，l i g h t d i f f u s e ) ； g l l i g h t f v ( g l _ l i o h t 0 ，g l _ s p e c u l a r ，l i g h t s p e e u l a r ) ； g l e n a b l e ( g l _ - l i g h t 0 ) ； g l d i s a b l e ( g lc o l o rm a t e r i a l ) ； g l l i g h t m o d e l i ( g l - l i g h t - - m o d e l - - t w o _ s i d e ，g l _ t r u e ) ； g l e n a b l e ( g l _ a u t on o r m a l ) ； g l e n a b l e ( g l _ o r m a l m e ) ； g l f l o a tm a t _ d i f f u s e _ f r o n t 4 ； 9 c o l o r t o m a t e r i a l ( m a t _ d i f f u s ef r o n t ) ； g l f l o a tm a t _ s p e c u l a r _ f r o n t = o 5 f , 0 5 f , 0 5 e 1 o f ； g l f l o mm a t _ s h i n i n e s sf r o n t = 5 0 o f f ； g l m m e r i a l f v ( g lf r o n t _ a n db a c k ，g l _ a m b i e n ta n dd i f f u s e , m a t _ d i f f u s e _ f r o n t ) ； g l m a t c r i a l f v ( g l _ f r o n t _ a n d _ b a c k , g l - s p e c u l a r , m a t _ s p e e u l a r _ 丹o m ) ； g l m a t e r i a l f v ( g l _ f r o n t n d _ b a c k , g ls h i n i n e s s , m a ts h i n i n e s s _ f r o n t ) ； 4 1 浙江大学硕士学位论文 在三角网格显示时主要有三种显示方式：点云显示方式，线框显示方式和渲 染显示方式。主要对o p e n g l 函数的调用实现三种显示。以下为调用的部分函数。 三角网格的显示方式 点模型的显示： g l g e t f l o a t v ( g i j o i n t _ s i z e ，& p s ) ； g l b e g i n ( g l _ p o i n t s ) ； g l v e r t e x 3 d ( v - x 0 ，v - y o ， z o ) ； g l e n d 0 ； 线框模型的显示： g l b e g i n ( g l - - l i n e s ) ； v t x l = e d g e - g e t s t a r t v t x 0 ； v t x 2 = e d g e - g e t e n d v t x 0 ； v t x l - y o ，v t x l - z o ) ； v t x 2 - y o ,