2009 年 第5期
工 程 图 学 学 报
JOURNAL OF ENGINEERING GRAPHICS
2009 No.5
最小二乘网格的模型修补
周明东, 林俊聪, 金小刚
(浙江大学CAD&CG国家重点实验室, 浙江 杭州 310058)
摘 要:最小二乘网格是在给定连接图和离散控制点集的基础上, 通过求解线性系 统对网格中的顶点重新定位而形成的网格.本文提出了一种最小二乘网格的模型修补算法, 首先根据模型孔洞构造合适的连接图, 然后根据网格连接图以及边界几何信息构造一个线性 稀疏系统,最后求解连接网格中所有顶点的三维几何坐标.该算法计算速度快,能取得理想 的效果. 关 键 词:计算机应用;模型修补;最小二乘网格;连接网格 中图分类号:TP 391.7 文献标识码:A 文 章 编 号:1003-0158(2009)05-0013-09
Model Repair with Least-Squares Meshes
ZHOU Ming-dong, LIN Jun-cong, JIN Xiao-gang
( State Key Lab of CAD&CG, Zhejiang University, Hangzhou Zhejiang 310058, China )
Abstract: Least-squares meshes are generated from a given connectivity graph and a set of control points with geometry in a least-squares sense. A model repair algorithm based on the least-squares meshes is proposed. Firstly, an appropriate connectivity graph for the hole is generated. Secondly, a sparse linear system is constructed according to the connectivity graph. Finally, the Euler coordinates of the vertices on the connectivity graph are solved. The algorithm is highly efficient. Key words: computer application; model repair; least-squares meshes; connectivity graph
由于概念简单并能支持高效而灵活的几何 处理, 三角网格已经发展成为传统 CAGD 领域除 样条曲面以外的另一种选择.将三角网格作为曲 面表示形式,可以避免会引入误差的转换(如将
收稿日期:2008-08-16
CAD 曲面转换成数值仿真所需要的网格数据) . 此外,三角网格在其它一些领域如计算机游戏, 影视特效也得到越来越广泛的应用.进入 90 年 代以后,三角网格逐渐发展成为一种主流的表示
基金项目:国家自然科学基金资助项目(60533080) ;国家"863"研究计划资助项目(2006AA01Z314) ;国家科技支撑计划课题 (2007BAH11B03) ;新世纪优秀人才支持计划(NCET-05-0519) 作者简介:周明东(1987-) ,男,重庆人,本科生,主要研究方向为几何造型,网格融合等.
14
工
程
图
学
学
报
2009 年
方式,并广泛应用于计算机图形学和几何处理的 各个领域. 目前,三维网格模型原始数据的最主要来源 是三维扫描.由于扫描工具和技术自身的限制, 所获得的三维网格模型往往存在一些不应有的 孔洞,裂缝等.此外,在自动化 CAD/CAE/CAM 设计领域中, CAD 系统里用 NURBS 曲面设计得 到的模型经常需要转化成三角网格以进行后续 的处理,这个转化的过程往往会产生一些瑕疵, 影响后续的应用.模型修补旨在移除几何模型中 的瑕疵并生成一个适合后续处理操作的模型,它 是几何处理的一个重要组成部分.近年来,国内 外的学者提出了很多模型修补的算法,这些算法 大致上可以分为:基于体的方法和基于曲面的方 法.基于体的方法首先把输入模型转化为体表示 再通过抽取算法得到输出网格.Nooruddinhe 和 Turk 在这方面进行了一些早期的研究工作 ,他 们提出了一种修补任意网格模型的体技术,可以 处理孔洞,自交,以及三角片重叠等各种情况, 但是该算法中用对体素的内外情况进行判定的 递归方法并不是特别稳定,此外,该算法也不能 处理尖锐特征.Bischoff 等人 通过建立输入网 格的自适应八叉树,然后在八叉树上应用形态操 作以确定模型拓扑,最后由八叉树结构重构出模 型的连接和几何关系,该方法能够很好地处理模 型尖锐特征.Ju 提出了一种在对偶网格上进行 模型修补的算法,尽管该算法对孔洞边界进行显 式跟踪和修补,但本质上仍是一个基于体的方 法.该方法的内存消耗并不依赖于输入模型的规 模,因此特别适合于任意大规模网格的修补.这 类基于体的方法通常是完全自动的,并且能够鲁 棒地生成封闭模型.然而体表示和网格表示的相 互转化涉及到模型重采样,这很容易引入走样误 差,导致特征丢失,破坏附着的一些其它属性. 此外,基于体的方法会生成大量质量不高的三角 片.基于曲面的方法直接检测网格曲面的几何和 拓扑上的瑕疵并进行修补,在尽可能保持模型其 它部分结构的情况下对模型进行局部的变动,这 类方法不仅在修补的同时能够很好地保留模型 上附着的材质等属性,而且仅仅增加少量的额外

下一页