MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); function MyAutoRun() {    var topp=$(window).height()/2; if($(window).height()>450){ jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); }  }    window.onload=MyAutoRun; $(window).resize(function(){ var bodyw=$win.width(); var _leftPaneInner_width = jQuery(".rich_html_content #leftPaneInner").width(); var _main_article_body = jQuery(".rich_html_content #main_article_body").width(); var rightw=bodyw-_leftPaneInner_width-_main_article_body-25;   var topp=$(window).height()/2; if(rightw<0||$(window).height()<455){ $("#nav-article-page").hide(); $(".outline_switch_td").hide(); }else{ $("#nav-article-page").show(); $(".outline_switch_td").show(); var topp=$(window).height()/2; jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); } }); 基于特征的离散网格模型表示与编辑技术
  软件学报  2016, Vol. 27 Issue (10): 2654-2660   PDF    
基于特征的离散网格模型表示与编辑技术
盖孟1,2, 赖舜男1, 李胜1,2,3     
1. 北京大学 信息科学技术学院, 北京 100871 ;
2. 北京市虚拟仿真与可视化工程技术研究中心(北京大学), 北京 100871 ;
3. 数学工程与先进计算国家重点实验室, 江苏 无锡 214215
摘要: 提出了一种基于特征的离散网格模型表示方法,能够表达传统三维网格模型中缺失的高层次信息,并以模型编辑为例显示了其应用价值.该特征结构利用特征线、特征面、特征组来建立离散网格的特征结构,用于描述模型的形状、约束、语义等信息,在原有网格模型的基础上构建了一个“超网格”.通过构建特征间的拓扑关系和约束关系,模型在编辑过程中能够保持特定的形状和结构属性,同时,由于编辑操作造成的网格修改被限定在局部的特征区域内,从而提高了模型编辑的运算效率.
关键词: 模型表示     形状操纵     网格编辑     模型特征     模型语义    
Feature Based Mesh Model Representation and Manipulation
GAI Meng1,2, LAI Shun-Nan1, LI Sheng1,2,3     
1. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China ;
2. Beijing Engineering Reseach Center of Virtual Simulition and Visualization(Peking University), Beijing 100871, China ;
3. State Key Labortory of Mathematical Engineering and Advanced Computing, Wuxi 214215, China
Foundation item: National Natural Science Foundation of China (61421062, 61232014, 61472010), National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2015BAK01B06); Specialized Research Fund for the Doctoral Program of Higher Education of China (20120001110089)
Abstract: This paper presents a novel feature based mesh model representation to represent the missing high level information of the traditional 3D mesh model. The application value of this representation is demonstrated by employing it in the model manipulation approach. Its feature structure, which consists of feature line, feature patch and feature group, is designed to describe the shape, constraint and semantic information of the model. As a result, it constructs a hyper-mesh beyond the original mesh model. With the topology and constraint information between features, the model can maintain its shape and structure properties during the editing. Meanwhile, as the modifications are limited in the local area, the manipulation approach is more efficient.
Key words: model representation     shape manipulation     mesh editing     model feature     model semantics    

三维离散网格模型在几何造型、计算机辅助设计等计算机图形学领域有着广泛的应用, 然而在参数模型离散网格化、三维扫描等过程中, 模型原有的形状、参数等高层信息会被大量丢失.传统的网格模型表示方法都无法有效地表达这些丢失的信息.因此, 研究一种能够同时表达模型高层信息的网格结构有着重要的意义.

另一方面, 网格模型编辑在三维建模、几何处理等领域有着重要的作用.从早期的低层次的自由形变技术, 到近年来高层次保结构的模型编辑技术, 这一领域一直吸引了许多研究人员的关注.而要在网格模型编辑过程中保持模型的结构, 同样需要一种描述模型结构信息的表达方式.

我们提出了一种模型特征的离散网格模型的表达方法.与iWires[1]方法类似, 我们也使用了曲线(特征线)来表达模型的尖锐特征.此外, 我们使用特征面来表达由特征线围成的区域, 用特征组来描述部件和约束信息.特征组由一系列特征线和特征面组成, 特征组也可以包含特征组, 从而有着很强的表示能力.

基于该特征结构, 我们将低层次的网格变形方法与高层次的保持结构的编辑方法统一到一个框架下.用户的编辑操作首先作用于低层次的网格元素, 例如网格的顶点.接着, 编辑操作的作用效果通过特征关系传播到其他受影响的特征上.得益于我们的特征结构, 所有的网格修改操作都作用于有限的特征区域内.在特征编辑传播的每一步过程中, 只有少数特征关联的网格需要被更新, 且不同特征关联的网格更新可以并行执行, 从而使得我们的方法可以处理较大规模的网格模型.

1 相关工作 1.1 离散网格的表达

离散网格通常使用三角形网格来表达三维物体, 当网格顶点足够多时即可达到足够的表达精度.传统的网格表达方式, 不论是基于点面表的结构, 还是基于半边[2, 3]的结构, 都不能表达模型在离散网格化过程中丢失的高层次结构信息.有许多研究工作专注于从离散网格[4]或点云[5]数据中恢复模型的参数信息, 但它们并没有提出特定的模型表达方式.

1.2 网格编辑

网格编辑技术一直以来是三维建模过程中的重要研究对象.网格的自由形变(free form deformation, 简称FFD)方法[6]可以追溯到20世纪80年代.21世纪初基于微分坐标[7]求解稀疏线性方程组的形变方法变得更加流行.直到后来非线性形变技术[8-10]的出现, 标志着低层次的网格变形技术基本成熟.近年来, 保持模型高层结构信息的编辑技术[11-13]逐渐发展起来.它们有的靠检测模型的重要区域进行非均匀的缩放, 有的利用模型线框、模型的特征部件等作为控制对象驱动模型变形并保持一定的结构和约束特性, 然而它们都没有提出统一的特征描述方式, 且没有很好地利用模型修改时的局部性特征.

2 基于特征的模型表达

为了对网格模型的形状、结构等信息给出统一的表达方式, 我们提出了特征的概念, 它基于离散网格来定义, 用于组织网格的高层次信息.我们定义了3种特征:特征线、特征面和特征组.

特征线储存了一系列网格顶点的索引用来表达模型上的曲线, 通常用来表达模型上的尖锐边缘及边界信息; 特征面则由一系列网格面片的索引组成, 它用来表达网格上的一个区域, 例如网格上的平面区域、圆柱面区域等.不失一般性, 我们没有显式地定义“特征点”, 这是由于特征点可以用只包含一个顶点的特征线来表示, 从而使得特征结构的定义更加简洁.特征线和特征面都有一个“形状”的成员属性来描述特征的几何参数信息.例如, 特征线可以包含一个圆形的形状成员来表明该特征线是一个圆形, 圆心、半径等参数存储于圆形的形状成员属性中.我们定义了圆形、圆弧、直线段等特征线形状以及平面、球面、锥面、柱面等特征面形状.在特征线与特征面之上, 同时构建了它们之间的拓扑邻接关系, 可以通过特征线、特征面查找其一邻域的特征线、特征面.因此, 从这个意义上看, 我们在原有模型网格的基础上构建了一个由特征线、特征面及其拓扑邻接关系构成的“超网格”, 如图 1所示.

Fig. 1 Features are constructed as a hypermesh beyond the original mesh model 图 1 特征——原始网格模型上构建的“超网格”

特征组包含了一组特征, 即特征线、特征面、特征组.特征组可用来定义特征间的邻接关系, 因此可以用来构成组件信息.它也可以用来在特征间定义更复杂的规则, 即约束关系.我们总共定义了等长、相连、共线、平行、同心、共轴、垂直、固定角度、等角、对称这10种常用的约束关系.由于在我们的设计中, 约束关系是一种特征组, 而特征组又可以包含特征组, 因此, 我们甚至可以在约束关系上定义约束, 从而构建出更加复杂的特征关系, 例如共轴约束下, 轴线又保持平行约束.这也显示出我们设计的特征概念拥有强大的表达能力.

此外, 对于所有特征, 用户都可以向其添加键值对形式的自定义属性值.因此, 对于构成部件的特征组, 用户可以添加自定义的部件语义信息.

整个特征结构的示意图如图 2所示.

Fig. 2 The feature structure 图 2 特征结构示意图

3 特征分析

在实际应用中使用的网格模型, 不论是来自于参数模型的离散化, 还是来自三维扫描, 模型的结构信息大多已丢失.因此在处理这些模型时, 首先要进行一定的特征提取、形状拟合、约束分析等步骤, 将模型丢失的结构信息恢复出来, 并存储到我们定义的特征结构中形成带有特征的模型.在此过程中, 始终允许用户参与, 采用交互的方式修正每个步骤的结果.整个特征分析的流程如图 3所示.

Fig. 3 The feature analysis pipeline 图 3 特征分析流程

3.1 特征提取

特征提取与模型分割紧密相关, 目的是提取出模型中有意义的区域, 并生成区域间的分割边界.模型分割领域有许多成熟的方法.由于我们处理的模型大多是人造CAD模型, 因此简单地采用了基于张量投票[14]的方法, 其算法具有良好的运行效率和算法鲁棒性.

算法自动进行特征提取的结果可能无法满足用户的预期, 因此我们为用户提供了一系列手动增删编辑特征的工具.例如删除一条特征边, 将相邻的特征面合并, 或添加一条特征线, 将某个特征面分裂等.

对一个车门模型进行特征提取的结果如图 4所示.

Fig. 4 The feature extraction result of a car door model 图 4 车门模型的特征提取结果

在进行完特征线与特征面的提取之后, 我们通过一系列简单的查询操作即可构建出特征线与特征面之间的拓扑邻接关系.将这些拓扑信息储存下来, 以便在之后的编辑过程中进行快速查询.

3.2 形状拟合

形状拟合步骤是为了恢复特征的形状参数信息, 从而在之后的编辑步骤中用于恢复形变后的特征形状.与常用的形状拟合策略[1]类似, 我们使用预先给定的一系列基本图形作为候选形状对特征进行拟合, 产生最小拟合误差, 且在一定阈值范围内的形状被选择作为特征的形状.

为了避免在特征线与特征面之间产生冗余的形状信息, 我们使用特征线的形状成员来描述区域的边界形状属性, 用特征面的形状成员来描述区域的内部曲面形状属性.例如, 对于圆柱的底面, 使用特征线来描述圆形的属性, 而用特征面来描述平面的属性.

3.3 约束分析

在我们的定义中, 约束是一种特征组, 它表达了一组特征之间的相互关系.在有了前一步的形状拟合结果之后, 对所有识别出的形状进行两两检查, 判断其是否满足一定的约束关系.同样地, 在特征线与特征面之间有可能产生冗余的约束信息.例如, 长方体相对的两个面的特征边描述了多组平行关系, 而这相对的两个面描述了同样的平行关系.为了减少冗余约束, 我们优先保留特征线的约束.这是由于特征面的关系通常可以由特征边的关系推导得到.只有在必需的情况下才使用特征面的约束关系, 例如两个不规则边界的平行平面区域, 这种情况下, 平行约束只有用特征面来定义.

4 基于特征的模型编辑

在模型编辑过程中, 用户既可以对网格的点、边、面等基础元素进行低层次的编辑, 又可以基于特征进行高层次的编辑操作.两种层次的操作被整合在统一的框架之下, 我们称其为“冒泡传播”过程.用户操作首先作用于低层次元素, 然后向上“冒泡”影响到所关联的局部特征, 接着, 局部特征的修改通过特征的拓扑邻域关系影响到邻接的特征, 最后, 编辑操作通过约束关系在特征之间进行传播, 更新相关联的其他特征.整个流程如图 5所示.

Fig. 5 The feature based model manipulation pipeline 图 5 基于特征的模型编辑流程

4.1 低层次编辑

对于低层次的网格编辑, 操作对象是网格的点、边、面等低层次元素.这种操作形式在用户需要编辑模型的局部细节时非常有用.

对于低层次网格编辑, 已有许多成熟的算法.我们采用了保持刚性的网格变形算法[10], 该算法采用交替迭代的方式优化如下目标能量函数, 求解局部刚性变换的旋转矩阵和顶点坐标, 有着较好的计算效率和变形效果.

$ E({S}')=\sum\limits_{i=1}^{n}{{{w}_{i}}}\sum\limits_{j\in N}{{{w}_{ij}}}{{\left\| ({{{{p}'}}_{i}}-{{{{p}'}}_{j}})-{{R}_{i}}({{p}_{i}}-{{p}_{j}}) \right\|}^{2}}, $

其中, p, p'分别为形变前后的顶点坐标, j为顶点i一邻域的顶点索引.wi是顶点i的一邻域面片构成的单元权重, 对于均一材料, 通常可取wi=1.wij为一邻域单元及边上的权重系数, 通常取wij=(cotaij+cotbij)/2, 其中, aij, bij为网格边(i, j)的对侧角度.S'为形变后的曲面.

当用户操作的低层次元素位于特征面内部时, 只有该特征面上的网格顶点参与计算并更新位置; 当操作的元素位于特征边上时, 则只有该特征边上的点进行更新.由于更新的顶点被限制在局部特征的范围内, 因此可以大大提高算法的运行效率.这种由网格低层次元素的编辑操作向上传递到所在特征形变的过程, 我们称其为“冒泡”过程.其他特征的相应形变在之后的“传播”过程中加以解决.

4.2 高层次特征编辑

高层次的编辑操作意味着用户的操作对象是模型的高层结构特征, 这种操作形式使得用户可以更方便、快速地对模型进行大幅度修改.特征修改的来源可能是低层次操作冒泡传递的结果, 也可能是用户直接对特征进行操作的结果.

当特征发生修改时, 通常只有一小部分区域受到影响需要被调整.为了查找出受影响区域, 我们利用了在之前的步骤中获得的特征拓扑结构.对于任何被编辑的特征, 其一邻域特征被设置为受影响区域, 其二邻域的特征被设置为固定区域.其中需要注意的是, 即使只共享一个顶点的特征, 仍然被认为是邻域特征.

一旦受影响的区域被确定下来, 我们继续使用经典的保持刚性的网格形变算法, 逐个地更新每个受影响的特征面.在这一步骤中, 仅考虑了特征的邻接信息, 未考虑其约束信息.如果用户不关注特征约束, 到这一步为止已经可以获得较好的编辑结果.

4.3 约束优化

若模型特征中存在约束信息, 当一个特征被编辑时, 与之满足一定约束关系的其他特征也需要被更新.全局优化所有特征满足目标约束是比较困难的, 为了避免直接求解这一问题, 我们采用了被广泛采用的贪心传播策略[13].类似于其线框到线框或部件到部件的模式, 我们的控制对象为特征.特征可以看作是线框和部件的推广.从当前被编辑的特征出发, 遍历所有包含此特征的约束, 满足约束的其他特征根据约束类型进行相应调整, 并重复上述步骤继续传播.这一传播过程直到遇到已经修改过的特征为止.

5 结果及讨论 5.1 实验结果

我们在多种模型上测试了本文所提的模型编辑方法.图 6显示了部分模型编辑的结果, 并以彩色图显示了特征分割的结果.注意, 在不同的编辑结果中, 模型的局部形状均得到了很好的保持.

Fig. 6 Some results of the mesh model manipulation 图 6 部分网格模型编辑结果

与现有的模型编辑方法相比, 我们的方法在处理顶点数目众多的大模型时有着更加明显的优势.图 7显示了一个约有5万顶点的车门网格模型.该模型若采用iWires[1]的方法进行编辑, 其形变过程中对模型整体作处理, 在中间步骤中需要求解5万×5万的稀疏矩阵, 虽然对于大规模稀疏矩阵的求解已有许多成熟算法, 但这显然不是最优方案.同时, 该模型由于仅由一张网格构成, 因此基于部件的模型编辑方法[13]不再适用, 且模型中的孔洞特征也难以用部件来表达.在我们的测试环境(Intel Core i5 2300 PC, 6GB Memory)下, 用户的编辑操作都能够达到实时交互的帧率.

Fig. 7 An example of big model editing. The right figure shows a local part of the features and the editing effect 图 7 大模型的编辑示例.右图为局部特征及编辑效果展示

5.2 局限性讨论

目前的特征结构虽然支持用户交互修改, 但仍然在很大程度上依赖于自动特征提取算法的输出结果, 这会直接影响特征结构的实用性.对于CAD模型、人造物体的模型, 通常都有较好的自动分析结果, 而对于噪声模型、有机体模型等, 则需要研究更通用和鲁棒的特征分析算法.由于我们同样采用了贪心传播的约束求解策略, 因此在遇到约束冲突的情况时, 可能产生不理想的编辑结果.接下来, 我们将研究在约束冲突的前提下, 如何以重要约束优先和尽可能地满足最多约束的更新策略.此外, 虽然我们支持用户向特征中添加自定义的语义信息, 但在目前的模型编辑应用中, 尚未对模型更高层的语义信息加以利用.在未来的工作中, 我们将探究对模型其他语义信息的利用.例如, 利用特征的功能目的、材料属性等信息, 来实现更精确的仿真编辑结果.

6 总结

本文提出了一种基于特征的离散网格模型表示方法, 并以模型编辑为例显示了该特征结构的应用.该特征结构包含特征线、特征面、特征组, 在原网格的基础上构建了一个“超网格”, 可用于表达传统离散网格模型中缺失的结构信息.特征组既可以用于表达部件信息, 又可以用于表达约束关系, 有着强大的表示能力.在基于特征的模型编辑应用中, 通过利用模型的特征信息, 使得模型在编辑过程中可以保持一定的形状和约束.同时, 特征的局部性和拓扑关系, 使得编辑操作造成的模型修改限制在局部的特征区域内, 从而大大加快了编辑算法的运行效率, 这都为用户快速、便利地编辑模型提供了有力的工具.由于该特征结构包含了丰富的结构信息, 且支持用户扩展添加更多属性及语义信息, 因此其在三维建模、几何处理的其他应用场景中也会有着潜在的重要意义.

参考文献
[1] Gal R, Sorkine O, Mitra NJ, Cohen-Or D. iWIRES:An analyze-and-edit approach to shape manipulation. ACM Trans.on Graphics (TOG), 2009, 28 (33) :1–10. [doi:10.1145/1531326.1531339]
[2] Botsch M, Steinberg S, Bischoff S, Kobbelt L.OpenMesh-A generic and efficient polygon mesh data structure.2002.http://www.lsi.usp.br/~mkzuffo/PSI5787/opensg/Botsch_OpenMesh.pdf
[3] Sieger D, Botsch M. Design, implementation, and evaluation of the surface_mesh data structure. In:Proc.of the 20th Int'l Meshing Roundtable.Berlin, Heidelberg:Springer-Verlag, 2012 :533–550. [doi:10.1007/978-3-642-24734-7_29]
[4] Yan DM, Wang W, Liu Y, Yang Z. Variational mesh segmentation via quadric surface fitting. Computer-Aided Design, 2012, 44 (11) :1072–1082. [doi:10.1016/j.cad.2012.04.005]
[5] Li Y, Wu X, Chrysathou Y, Sharf A, Cohen-Or D, Mitra NJ. Globfit:Consistently fitting primitives by discovering global relations. ACM Trans.on Graphics (TOG), 2011, 30 (4) :52. [doi:10.1145/2010324.1964947]
[6] Sederberg TW, Parry SR. Free-Form deformation of solid geometric models. ACM SIGGRAPH Computer Graphics, 1986, 20 (4) :151–160. [doi:10.1145/15886.15903]
[7] Sorkine O, Cohen-Or D, Lipman Y, Alexa M, Rössl C, Seidel HP. Laplacian surface editing.In:Proc.of the 2004 Eurographics/ACM SIGGRAPH Symp. on Geometry Processing, 2004 :175–184. [doi:10.1145/1057432.1057456]
[8] Botsch M, Sorkine O. On linear variational surface deformation methods. IEEE Trans.on Visualization and Computer Graphics, 2008, 14 (1) :213–230. [doi:10.1109/TVCG.2007.1054]
[9] Yu Y, Zhou K, Xu D, Shi X, Bao H, Guo B, Shum HY. Mesh editing with poisson-based gradient field manipulation. ACM Trans.on Graphics (TOG), 2004, 23 (3) :644–651. [doi:10.1145/1015706.1015774]
[10] Sorkine O, Alexa M.As-Rigid-as-Possible surface modeling.In:Proc.of the Symp.on Geometry Processing.2007.4.http://dl.acm.org/citation.cfm?id=1282006
[11] Jacobson A, Baran I, Kavan L, Popović J, Sorkine O. Fast automatic skinning transformations. ACM Trans.on Graphics (TOG), 2012, 31 (4) :13–15. [doi:10.1145/2185520.2185573]
[12] Kraevoy V, Sheffer A, Shamir A, Cohen-Or D. Non-Homogeneous resizing of complex models. ACM Trans.on Graphics (TOG), 2008, 27 (5) :1–9. [doi:10.1145/1409060.1409064]
[13] Zheng Y, Fu H, Cohen-Or D, Au OKC, Tai CL. Component-Wise controllers for structure-Preserving shape manipulation. Computer Graphics Forum, 2011, 30 (2) :563–572. [doi:10.1111/j.1467-8659.2011.01880.x]
[14] Kim HS, Choi HK, Lee KH. Feature detection of triangular meshes based on tensor voting theory. Computer-Aided Design, 2009, 41 (1) :47–58. [doi:10.1016/j.cad.2008.12.003]