基于数学形态学与拓扑规则的三角网格修补算法.pdf
《基于数学形态学与拓扑规则的三角网格修补算法.pdf》由会员分享,可在线阅读,更多相关《基于数学形态学与拓扑规则的三角网格修补算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、第 4 9卷第 1 期 2 0 1 3 年1 月 机械工程学报 J OUR NAL OF MECHANI CAL E NGI NE E RI NG VO 1 49 N O 1 J a n 2 01 3 DoI : 1 0 3 9 0 1 J M E 2 0 1 3 0 1 1 4 8 基于数学形态学与拓扑规则的三角网格修补算法水 蒋恒恒 李奇敏汤宝平 ( 重庆大学机械传动国家重点实验室重庆4 0 0 0 3 0 ) 摘要: 针对散乱点云数据在三角剖分过程中产生的拓扑缺陷, 提出一种基于数学形态学运算和拓扑规则的网格拓扑修补算法。 通过交互的方式选择需要修改的区域,使用自适应分层栅格的缺陷识别技
2、术提取有拓扑缺陷的网格的顶点,从而确定待修复 区域的边界,然后利用数学形态学的开启运算和闭合运算去除该修复区域的拓扑缺陷,并利用基于柄体理论的拓扑运算法则 对该区域进行局部拓扑修改,生成二维流形的三角网格。应用实例表明,由于不需要对整个点云数据重新进行三角剖分,简 化数据处理的过程,该算法具有运算速度快、结果准确性好的优点,并能较好地消除网格中的拓扑缺陷,有效地提高三角网 格的显示精度,最终得到具有几何一致性和网格单元拓扑一致性的三角网格模型。 关键词:点云数学形态学开启 闭合拓扑缺陷柄体算子星形算子 中图分类号:T P 3 9 1 Tr i a ng u l a r M e s h Re p
3、a i r Al g o r i t h m Ba s e d o n M a t h e m a t i c a l M o r ph o l o g y a nd To po l o g y Ru l e J I A NG He n g h e n g L I Qi mi n T A NG B a o p i n g ( T h e S t a t e Ke y L a b o r o r y o f Me c h a n i c a l T r a n s mi s s i o n , C h o n g q i n g Un i v e r s i t y , C h o n g q
4、i n g 4 0 0 0 3 0 ) Ab s t r a c t :F o r t h e t o p o l o g i c a l d e f e c t s g e n e r a t e d d u r i n g un o r g a n i z e d p o i n t c l o u d t r i a n g u l a t i o n , a n e w me tho d i s p r e s e n t e d f o r me s h r e p a i r b a s e d o n ma the ma t i c a l mo r p h o l o g y
5、a n d t o p o l o g y r u l e T h e r e p a i r e d a r e a s a r e c h o s e n wi t h t h e i n t e r a c t i v e wa y s , an d t h e me s h v e r t e x s wi th p o t e n t i a l t o p o l o g i c a l e r r o r s a r e f o u n d o u t b y me a n s o f a d e c t d e t e c t i n g t e c h n o l o gy
6、b a s e d o n a d a p t i v e h i e r arc h i c a l g r i d S O a s t o d e t e r mi n e the b o un d a r y n e e d t o b e r e p a i r e d Op e n i n g an d c l o s i n g o f ma the ma t i c a l mo rph o l o gy b e i n g u s e d , t h e t o p o l o gy o f the mo d e l c a n b e mo d i fi e d T h e
7、l o c a l t o p o l o gy r e p a i r i s a b l e t o b e fi n i s h e d a n d a 2 - ma n i fol d t r i an g l e me s h i s g e n e r a t e d q u i c k l y t h r o u g h t o p o l o g i c a l me s h o p e r a t o r s b a s e d o n Hand l e b o d y t h e o r y Ex p e r i me n t a l r e s u l t s s h o
8、 w t h a t t h e t r i a n g u l a t i o n o f t h e wh o l e p o i n t c l o u d i s n o l o n g e r n e e d e d S O t h a t the d a t a p r o c e s s i n g i s s i mp l i fi e d T h e p r o p o s e d a l g o ri t h m i s f a s t a n d a c c u r a t e , and the t o p o l o g i c a l d e f e c t s c
9、 a n b e e l i mi n a t e d s a t i s f a c t o r i l y a n d o u t p u t p r e c i s i o n o ft r i an gu l ar me s h e s C a l l b e i mp r o v e d e ffic i e n t l y T h e t r i a n gul a r me s h mo d e l wi t h g e o me t r i c a l an d t o p o l o g i c a l c o n s i s t e n c y i s a b l e t
10、o b e f o r me d Ke y wo r d s :P o i n t c l o u d s Ma t h e ma t i c a l mo rph o l o g y Op e n i n g Cl o s i n g T o p o l o g i c a l e r r o r Ha n d l e b o d y o p e r a t o r S t e l l a r o p e r a t o r 0 前言 三角剖分问题一直是近年来网格剖分技术中 的一个热点研究问题 。迄今为止已有很多成熟的 三角剖分算法, 但由于三维采样设备的固有局限性, 以及实体内部的几何性质
11、 ,大多数剖分算法生成 的网格模型存在着拓扑缺陷。B I S C H O F F等 利用 +高等学校博士学科点专项科研基金( 2 0 0 9 O 1 9 l 1 2 0 0 0 7 ) 和国家 自然科学 基金( 5 0 9 0 5 1 9 0 ) 资助项 目。2 0 1 1 1 2 2 2收到初稿,2 0 1 2 1 0 1 6收到修改稿 等值面重构与形态算子相结合的方法对三角网格的 拓扑缺陷进行修补,该方法虽然简单、易于编程 , 但修补后网格的精确度有待提高。Z H O U 等【4 】提出 一 种基于骨架算子的拓扑修补算法,该算法能够去 除低亏格模型中的小h a n d l e s , 但在
12、重构网格的过程 中容易引起模型变形。 L O ME NI E等L 5 J 引入 S h a p e s 理论, 提出一种基于形态算子与 D e l a u n a y三角网相 结合的三角剖分算法,该算法可较好地处理边界部分 的网格,但由于理论部分不够完善,适用范围有限。 以上几种方法在网格修补后、重构网格模型时 学兔兔 w w w .x u e t u t u .c o m 2 0 1 3 年 1 月 蒋恒恒等:基于数学形态学与拓扑规则的三捕网格修补算法 l 4 9 均使用隐式 曲面法,在表示实体边界的拓扑集合时 采用传统 的 E u l e r - P o i n c a r e 理论。 隐
13、式 曲面法适合于 构造任意拓扑的复杂形体,在分割点云的过程中, 易于跟踪有拓扑缺陷的网格,且曲面光顺性较高, 但该方法在构造复杂形状 H j 面时需要大量 的基本体 素,用户对此难 以有效控制,因此不能进行细节造 型 】 。欧拉算子是低层算子,实现较为简单,计算 量也较少 ,但在网格修补的过程中,会产生一些不 合法的中间模型,最终导致结果模型中出现不需要 的亏格【2 】 ,因此欧拉算子通常要封装更高层的算 子L 7 】 。为 了保证 网格在修补过程中的拓扑合法性, 为运算法则提供准确的抽象层次,本文采用较高层 次的拓扑算子对 网格进行编辑。具体思想如下:利 用 自适应栅格分割点云,在此基础上,
14、引入形态学 算子,消除网格中的拓扑缺陷,再利用基于柄体理 论与星形理论的拓扑规则,最终生成二流形 曲面。 该算法将基于面的二流形创建方法与自适应拓扑修 改算法相结合,避免了传统算法中特定等值面的构 建,不仅能够提高计算效率,而且用户可以根据实 际需要选择要修改的区域,从而提高了修改精度 。 1 算法描述 曲面拓扑重建所得网格模型上的缺陷可分为 两种:点云采样信息不完备导致 曲面拓扑重建算法 失效而产生的缺陷,如图 1 所示;未能根据点云类 型选择恰当的曲面拓扑重建算法而导致的缺陷,如 图 2所示 。而拓扑缺陷将影响最终模型生成理想的 亏格 以及连通分支个数【 8 。弥补第一种拓扑缺 陷的 方法
15、之一是提高采样密度 , 即增加采样点的数量L 3 J 。 如 图 l b所示,将 门框模型的采样点个数 由 1 3 5 8 9 5 个增加到 1 9 4 2 1 6个,可 以消除部分拓扑缺陷。提 高采样密度不仅需要较好的采样设备,同时会降低 算法的运行速度,如图 1 a的计算时间为 1 0 4 4 s , 图 1 b为 l 4 5 4 s ;而且用这种方法消除拓扑缺陷具 有一定局限性 , 如图 l b的门框把手处仍有未填平的 空洞。第二种缺陷是伪缺陷,因为样点间距通常小 于工艺孔洞 ,可在 曲面拓扑重建过程中避免误连接 情况的发生。如图2中的汽车零件模型,将其划分 点云的栅格尺寸减少为原来的2
16、 3,可部分修补拓 扑缺陷,如图 2 c所示;将栅格尺寸减少为原来的 1 2 ,可完全修补拓扑缺陷,如图2 d 所示。但有时 用户并不熟悉拓扑方面的知识,而且在拓扑重建阶 段解 决伪缺 陷也会增加算法的运行 时间。如 图 2 b 的计算时间为 O 5 9 s , 图2 c为 2 5 9 s , 图 2 d为 4 2 3 S 。 _ - 0 ( a ) 含有小h a n d le s 的三角剖分模型 ( 1 3 5 8 9 5 个点) 图 1 门 ( c ) 部分修补的三角剖分模型 ( d ) 完全修补的三角剖分模型 图 2 汽车零件模型 数学形 态学是一 门建立在严格数 学理论基础 上的学科,
17、在 图像处理中应用广泛【 9 】 ,如今也越来 越多地应用到计算机辅助设计及计算机辅助几何设 计 中。数学形态学用具有一定形态的结构元素去度 量和提取图形 图像 中的对应形状,从而简化 图形 图 像数据,保持其基本形状特征,同时除去其中的缺 陷 1 刚 。本文采用形态学开启和 闭合算子修补 网格 中 的拓扑缺陷,并结合柄体理论与星形理论的拓扑规则 重构网格,达到较好的效果。算法的具体步骤如下。 ( 1 )输入点云或三角 网格模 型,将其转换为 自 适应分层栅格集合 。 ( 2 )用户选择需要修改的区域( 可选) 。 ( 3 )利用 自适应分层栅格 识别技术分析有缺陷 的区域 。 ( 4 )应用
18、形态算子( 开启算子和闭合算子) 处理 有拓扑缺陷的区域f 填补空洞, 创建空洞, 连接间断 部分) 。 口 一 翕 学兔兔 w w w .x u e t u t u .c o m 1 5 0 机械工程学报 第 4 9卷第 1期 ( 5 )根据 拓扑规 则对 该区域进 行局 部拓 扑修 改,最终生成二维流形 的三角网格 曲面。 下面对其 中的关键步骤进一步展开论述 。 1 1 基于分层栅格的缺陷识别技术 一 般情况下,三角网格的缺陷存在于曲面的外 部或 内部边缘处、采样密度突变处或者有局部特征 的地方【 I 。为 了识别这些缺陷 ,本文改进柯映林 等【 】 】 提出的基于栅格的点云边界特征直接
19、提取算 法 ,采用分层栅格识别技术提取任意栅格的内外边 界 ,找到需要修复的区域。为更好地找到要修补的 区域,本文采用与用户交互相结合的方式:由用户 选择待修复区域 , 算法 自动确定待修复区域的边界 。 分层栅格识别算法分为以下三步: 建立分层栅格 的拓扑连接数学模型, 产生边界种子栅格; 种子 栅格沿边界方 向生长 , 产生所有边界栅格 ; 从边 界区域 中提取点云的边界点集合 。 对于用户选定的待修复区域,首先使用 自适应 三角剖分方法中的栅格分层算法 ,用较小的栅格 尺寸细化该区域的栅格 ,再按照实格和空格对选中 区域的空间栅格进行二值化处理。 汽车零件模型的分层栅格如图 3所示。 一
20、 ( a ) 分层栅格 ( b ) 放大后的子栅格 图 3 分层栅格示意图( 汽车零件模型) 令 g t ( x , Y , z ) : EIf , ( x , Y , z ) - ( + f , Y + J , Z + 露 ) I 一 1 i 1 一l Jl 一1 k l f + +k: l &( f =0 I l J=0 l I k=0 ) ( 1 ) 式中 ( , Y , z ) 栅格的坐标 ( , J , k ) 栅格的拓扑方向 ( , Y , z ) 第, 层空间栅格的二值化函数 g l ( x , Y , z ) 第, 层种子边界栅格的函数 如果 = 1 ,表示该栅格为实格,包含数
21、据点; 否则 = 0,该栅格为空格。如果g t ( x , Y , z ) 3, 并 且当g l ( x , Y , z ) = 3 时 满足约束条件 + f , Y + J f, z + k ) = 1 ,该空间实格是种子边界栅 格 。种子边界栅格分三种类型:当g , ( j c , Y , Z ) 3时, 说 明原始曲面的边界比较平坦,如图 4 a所示;当 g , ( , Y , z ) :4时,表明原始 曲面的边界弯 曲程度 比 较剧烈,如图 4 b所示 ;当g l ( x , Y , z ) =5时,表明原 始 曲面的边界存在尖锐特征,如图 4 c所示 。 一般情 况下,在网格修补中只
22、需要考虑弯曲程度比较剧烈 或含有尖锐特征 的边界,本文只考虑 g ( x , Y , Z ) 4 时的情况 。 J 霎 , ( a ) 较平坦的边界 ( b ) 弯曲剧烈的边界 ( c ) 含尖锐特征的边界 图 4 种子边界栅格的三种类型 很明显 ,种子栅格集合不包含所有边界栅格 , 为了获得所有边界栅格,可以利用种子栅格 自身的 拓扑关系使种子栅格沿特定的拓扑方向进行带约束 的生长 。令 ( , Y , z , 厂 ) = l ( , Y , z ) 一 ( + f , Y + J , z 十 七 ) l G ( , Y , z ) = If , C x , Y , z ) - ( + f
23、, Y + J , Z + ) l ( x , Y , z ) =1 - 1 1 - 1 J 1 1 k1 ( f , J f , 七 ) ( 0 , 0 , 0 ) ( 2 ) 式中,T t ( x , y , Z , f , J , k ) 为第 , 层边界种子栅格的拓扑 关系函数, G J ( , Y , Z ) 为约束条件。 利用 式( 2 ) 实 现种 子边 界 栅格 的生长 。如果 T l ( x , y , z , f , J , k ) =1 ,则表示该实格沿 ( f , J , k ) 方向的 拓扑关系为空;如果函数值为 , z , f , J , k ) =0, 则表示实格
24、沿 ( , J , k ) 方 向的拓扑关系不为空。种子 边界栅格的生长情况可按照 G i ( , Y , z ) 将其分为两 类: 当G j ( , Y , z ) = 5 或 ( , Y , z ) = 6 时, 表示该种子 边界栅格受参考约束拓扑关系的约束, 可沿( f , J , k ) 的拓扑方向进行生长; 其他情况该种子栅格不生长。 当生长完成后,从每个栅格中提取边界特征点 作为种子点,然后在种子点的邻域内搜索其他边界 点并进行优化 ,最终获得边界点集f 图 5 、6为渲染 后的三角网格1 。 学兔兔 w w w .x u e t u t u .c o m 2 0 1 3年 1 月
25、 蒋恒恒等:基于数学形态学与拓扑规则的三角网格修补算法 l 5 l ( a )人工选择 ( b )采用分层栅格识别 技术提取的边界点 图 6 汽车零件模型( 6 6 9 1个点) 1 2 形态算子 本 文采用形态算 子修复 网格 中存 在拓扑缺 陷 的区域 。形态学运算主要包括腐蚀 、膨胀、开启和 闭合 4种基本运算 ,可用于抑制噪声、特征提取、 边缘检测等方面【 1 引 。 可 以使用形态学腐 蚀运算扩张 空洞及细小 间 断,膨胀运算弥补空洞 。设 表示栅格集合, y 表 示栅格中的一个数据点,为了书写方便,记腐蚀算 子 ( , ) = v V , 的2 6 邻域都在 中, 膨 胀 算 子
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 数学 形态学 拓扑 规则 三角 网格 修补 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【wen****889】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【wen****889】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。