面向移动终端的三维CAD模型面片生成方法*

蔡 强，许 杰，李海生，李 楠，曹 健

1.北京工商大学 食品安全大数据技术北京市重点实验室，北京 100048 2.北京工商大学 材料与机械工程学院，北京 100048

面向移动终端的三维CAD模型面片生成方法*

蔡 强1+，许 杰1，李海生1，李 楠2，曹 健1

1.北京工商大学 食品安全大数据技术北京市重点实验室，北京 100048 2.北京工商大学 材料与机械工程学院，北京 100048

CAI Qiang,XU Jie,LI Haisheng,et al.3D CAD model patch generation method in mobile terminal.Journal of Frontiers of Computer Science and Technology,2017,11(6)：972-979.

移动终端；三维CAD模型；面片生成；分类树；规模系数

1 引言

随着计算机技术的快速发展，智能手机、平板电脑和可穿戴设备等移动终端成为一种重要的计算载体，其便于携带和适于多种工作环境的优点在很多行业得到了应用。同时，人们对移动终端的图形交互体验有了更多的需求，三维场景的广泛应用由PC端开始转向移动终端设备。尤其在工业设计领域，一个复杂的三维场景包含的对象体不仅范围广泛，种类繁多，大部分还具有复杂的几何结构和形态描述，因此构建的模型数据量不但巨大，而且还占用很多的内存空间，这就影响了视觉效果和计算机处理速度[1]。而且与高端的图形工作站和桌面PC相比，移动终端的各种资源极为有限，如CPU的主频低且大多数浮点计算能力差，存储小等，三维模型的高效绘制在移动终端上的研究面临更多的难点[2]。因此基于移动终端的三维模型面片生成技术用于提高移动终端三维模型显示效率，已成为近年来计算机辅助设计与制造领域一个新的研究热点。

表示三维模型的最基本单位称为顶点，它代表三维空间中的一个点。两个顶点连接成线段，3个不在同一条直线的顶点构成一个三角形，也就能表示一个面。因此，通过顶点数组定义点、线段、三角形或四边形，可以构建简单的二维图形，而不同的二维图形则可以构成复杂的三维立体模型[3]。在图形显示系统中一般采用三角面片[4]表示图形，通过面片的集合来表示物体表面，能够简单有效地用于显示系统。因此本文使用基于三角面片的模型生成方法。

基于此，本文针对移动终端的特点，在利用CAD模型中的层次类型和图形表达信息[5]的基础上，提出了基于规模估算的三维模型面片生成方法。该方法以CAD模型的层次类型和图形表达的关系数据为信息输入源，首先根据数据中的图形、拓扑和分类信息构建包含整个模型图形信息的图形分类树[6]，叶子节点就是表示模型最小单元的体元，每个体元包含生成三角面片所需的参数信息；其次，在移动终端实现交互方法，以便选取所要显示的模型节点，计算出模型规模系数；最后，根据规模系数，生成所要显示模型的三角面片集来实现三维模型的面片构建。

2 基本概念和思路

2.1 基本概念

本文充分利用三维CAD模型对象的层次类型和图形表达数据来进行三维面片的生成，模型对象按其工程意义可分为若干大类，每个大类又可细分为若干子类，子类还可以继续划分子类，从而形成一个树形层次分类结构。

定义1类型层次关系RC。类型层次关系为三元关系，属性CID是其唯一ID，属性Name是该分类的名称，属性ParentCID是其父分类的ID。表示如下：

定义2模型对象关系RO。模型对象关系为二元关系，属性OID表示其唯一ID，属性CID表示其所属的分类ID。表示如下：

定义3图形描述关系RG。图形描述关系为二元关系，属性OID是对象ID，属性Data是对象包含的所有体元信息。表示如下：

一个模型对象的三维图形由若干体元组成，体元之间没有布尔运算，只是简单堆积。定义G为基本体元集[7]，G={Cylinder（圆柱），Scylinder（斜截圆柱），Prism（多棱柱），Econe（偏心圆台），Concone（同心圆台），Squcir（天圆地方），Squcone（矩形断面台），Box（长方体），Torus（圆形断面圆环），Squtorus（矩形断面圆环），Sphere（球），Wedge（直角楔形体），Saddle（马鞍形），Oval（椭球封头）}；每个体元包含生成三角面片所需的参数信息[7-8]，以Sphere为例，该体元图形描述为Sphere:〈Center(圆心)〉，〈Radius(半径)〉。

2.2 方法概述

针对移动终端的三维模型显示存在的问题，首先以CAD模型的3种关系数据RC、RO和RG为信息输入源，根据数据中的图形、拓扑和分类信息[9]构建包含整个模型图形信息的图形分类树，叶子节点就是表示模型最小单元的体元，每个体元包含生成三角面片所需的参数信息；在移动终端实现交互方法，以便选取所要显示的模型节点，计算出模型规模系数；然后，根据规模系数，生成所要显示模型的三角面片集来实现三维模型面片的生成。具体步骤如下。

步骤1解析CAD模型文件，构建模型图形信息分类树。依据类型层次关系RC建立类型层次结构；依据模型对象关系RO将对象分类；依据图形描述关系RG将体元信息作为叶子结构。

步骤2在移动终端构建良好的交互界面，交互地选取所要浏览的模型节点，估算所要显示的模型节点的规模系数。

步骤3根据模型规模系数，选择不同体元的三角面片生成策略，生成顶点数组。

3 图形分类树的构建

3.1 类型层次结构

CAD模型通常包含多种类型信息，具有层次结构。以CAD模型的3种关系数据RC、RO和RG为输入源，通过对其中类型层次关系RC的解析能够建立一种树形结构来表示这种层次结构。根据RC的定义，按如下步骤生成一些中间关系来体现类型层次结构。

步骤1求根节点关系。在类型层次关系RC中，父类型编号等于类型编号的元组变量，即为图形分类树的根节点。

式中，Rroot为根节点关系；t[1]表示元组变量t的属性CID；t[3]表示元组变量t的属性ParentCID。因为根节点的唯一性，所以Rroot度数为1。

步骤2求一级类型节点关系。在RC中，父类型编号等于根节点类型编号的元组变量为根节点的子节点，即一级类型节点。

步骤3求二级类型节点关系。在RC中，父类型编号等于一级类型节点编号的元组变量为一级类型节点的子节点，即二级类型节点。

式中，RC2i为ti一级类型节点的二级类型关系。

基于上述步骤，可以构建图形分类树的类型层次节点。其中，根节点root为Rroot唯一的元组变量；一级类型节点的所有元组变量；一级类型节点Ci对应的二级类型节点的所有元组变量。

表1中的示例数据采取上述算法构建的树如图1所示。

Table 1 Type hierarchy sample data表1 类型层次示例数据

Fig.1 Type hierarchy structure tree of sample data图1 示例数据类型层级结构树

3.2 模型对象分类

CAD模型中各类型节点又包含了若干模型对象[10]，本文基于上面构建的树来将模型对象分类，进一步构建图形分类树。根据模型对象关系RO的定义，依次对二级类型层次关系值为的度）进行对象分类：

式中，ROi,j表示中每一个元组变量tj的对象关系。t[2]为RO的元组变量t的属性CID。

基于此，就可以构建图形分类树的对象节点，即二级类型节点Ci,j的对象节点Oi,j,k为ROi,j的所有元组变量。

3.3 图形信息解析

对象为在CAD模型设计中，对于工程而言有意义的最小单位[11]，如一段管子、一个设备、一个元件等。一个模型对象的三维图形由若干体元组成，体元之间没有布尔运算，只是简单堆积。

根据图形描述关系RG的定义，依次对模型对象关系

根据上述算法，构建了如图2所示的图形分类树。

Fig.2 Structure of shape classification tree图2 图形分类树结构图

4 模型节点规模的估算

4.1 交互选取模型节点

为了解决大规模三维模型在移动终端显示存在的难点，本文特地对CAD模型构建了图形分类树，在移动终端可视化该图形分类树，可视化方式是实现4个列表，分别是一级层次类型列表、二级层次类型列表、模型对象列表和体元列表。其中，一级层次类型列表列举图形分类树的一级层次类型节点Ci；构建了良好的交互方式[12]来选取任意节点，当选取任意Ci之后，二级层次类型列表列举所选取的Ci节点的所有子节点Ci,j；当选取任意Ci,j之后,模型对象列表列举所选取的Ci,j节点的所有子节点Oi,j,k；当选取任意Oi,j,k之后，最后的体元列表列举所选取的Oi,j,k节点的所有体元信息。

根据上述的移动终端模型节点选取方式，能够高效地选取需要显示的局部三维模型（细节），并从图形分类树中获取该节点所有子节点的图形信息，这样便能构建表示三维模型所需的三角面片，使注意力集中在模型的细节上。

4.2 规模系数计算

不同体元在相同显示精度的情况下，构成体元的三角面片数量差别很大，如长方体体元在任意显示精度下都可以使用12个三角面片来表示；在圆显示精度为圆周16等分时，圆柱体元需要64个三角面片，球体元需要240个三角面片。而且，当显示精度越高，不同体元的三角面片数量差异会越来越大。因此，根据构建体元面片的实际情况，使用对不同体元加权的方式来计算出模型的体元总量：

其中，k表示不同体元，如设k=1表示圆柱，k=2表示斜截圆柱，以此类推，n=14；num(Ok)表示所选对象节点Ok所包含的体元k的数量；wk为体元k的体元权重。

至此，可以用N来表示所选模型节点的体元总量。对于在移动终端三角面片显示存在的效率问题，并不能随意地对任意体元总量实现高精度的显示，因此引入模型规模系数来衡量模型节点的面片规模，从而判断实际显示所需的精度级别。面片规模越大，显示精度越低；面片规模越小，显示精度越高。采用如下公式计算规模系数：

其中，N是所选取模型节点的体元总量，在交互选择需要浏览的对象时计算出N；nMin为可以显示的模型最少体元总量，这里取1；nMax为整个模型包含的体元总量，在构建图形分类树时得到；λ为调整指数，因为通过前面的标准化可以得到一个区间在(0,1)之间的实数，但是当面片数很小时，面片的缓慢增加对显示性能影响不大，而当面片数很大时，面片的增加对显示性能的影响就明显增大，因此引入λ调整规模系数，使它满足这种特性。

这样，规模系数的范围在(0,1)之间，用来度量模型节点的规模，规模系数越大，模型规模越大。

5 模型面片的生成策略

三维模型的主流表示方法就是用三角面片来表示三维空间的面，三角面片用3个三维空间的点依据规定好的顺序（逆时针或顺时针）来表示的。前文在移动终端中选取了所要显示的模型节点，并依上述算法得到了模型规模系数，据此动态地计算所需显示的三角面片。本文使用顶点数组[13]的方式来构建三角面片，每3个顶点以逆时针的方式表示一个三角面片。

如图3所示，圆周上分为8个顶点，其中顶点V1、V2、V3和V4组成了面片F1和F2。PX、PY、PZ、NX、NY、NZ、R、G、B、A分别表示顶点三维空间坐标、顶点法向量和顶点颜色，坐标用来确定三维空间位置，法向量和颜色用来添加环境光照，这样显示的效果会接近自然环境。

Fig.3 Structure of triangular patch vertex array图3 三角面片顶点数组结构

得到所选模型节点的体元信息后，据此还需要判断显示精度来计算如图3的顶点数组。不同体元在不同显示精度的情况下构建面片的策略都略有不同，其中最主要的是包含圆的情况，如圆柱、斜截圆柱、偏心圆台、同心圆台、天圆地方、圆形断面圆环、矩形断面圆环、球、椭球封头这几种体元都包含圆形。因此，以圆为例，不同的显示精度本质就是圆周需要用多少面片来表示，圆周需要的面片数计算如下：

其中，s为规模系数；cMax为显示最细致的情况圆上顶点数，根据实际情况，取值36（即将圆36等分）。

在根据规模系数计算出模型的顶点数组之后，需要在移动终端借助三维图形接口显示出模型，并添加交互方式实现模型的旋转、缩放和平移，将模型进行实用。

Table 2 Patches number of some model nodes表2 部分模型节点面片数

6 实验及结果分析

上述基于分类树的三维模型面片生成方法，用于提高在移动终端显示三维模型的效率，能够有效地将注意力集中在关注的模型细节上。根据某公司对旗下三维模型产品移动化的需求，笔者自主设计并开发了“基于分类树的三维模型显示系统”。开发所用移动设备是Apple的iPad mini2，A7 CPU，1 GB内存；使用的3D引擎是OpenGL ES[14]。因为在PC领域专业的图形程序接口有两种标准的3D API：OpenGL和DirectX。一般主流的游戏和显卡都支持这两种渲染方式，DirectX在Windows平台上有很大的优势，但是OpenGL具有更好的跨平台性。为了满足嵌入式设备对3D绘图的要求，Khronos公司对标准的OpenGL系统进行了维护和改动，形成一套为手持和嵌入式系统设计的3D引擎API，即OpenGL ES。

以文献[2]中的某流程工厂模型（本质是关系型数据库文件[15]，三维CAD模型所包含的图形、拓扑和分类信息以数据表的形式储存）为例，对本文基于分类树的三维CAD模型面片生成方法在上诉系统进行实验。为了进行比较，选取不同模型节点，采用上诉算法进行绘制，得到的三角面片数量如表2所示，其中原面片数指模型以普通精度构建所需面片数。

从表2中可以看出，对于模型规模较大时，本文方法大大降低了模型面片数量，以实现其在移动终端的高效显示；当模型规模较小时，对移动终端的渲染压力较少，因此增加面片的数量以提高显示精度。

同时，在相同的漫游路径下，采用不同方法对该模型进行绘制，得到的绘制帧速如图4所示。可以从图中看出，本文方法虽然在模型规模较小时，绘制帧速低于文献[7]，但在规模较大时，绘制的帧速满足浏览的实时性。重要的是，本文方法占用内存空间较其他方法少很多，充分考虑了移动终端内存小的特性，而文献[7]是使用多分辨率的绘制方法，极大地增加了内存的占用。

Fig.4 Drawing frame of different methods图4 不同方法的绘制帧速

在该系统中，用户可以轻松地选取如图5所示的图形分类树的模型节点，并查看模型的图形信息和工程信息，同时可以进行交互浏览。其中，图5（a）所示的运行界面是本文集加载解析文件和可视化图形分类树功能的主界面，用户可清楚明了地查看模型组成结构，包括一级类型节点、二级类型节点、对象节点和体元节点；图5（b）所示为模型二级类型节点“管线-13S-9003-H”的显示界面。

7 结束语

Fig.5 Screenshots of running system图5 系统运行截图

本文提出了一种基于分类树的移动终端三维CAD模型面片生成方法。依据模型包含的层次类型和图形表达信息，根据数据中的图形、拓扑和分类信息构建包含整个模型图形信息的图形分类树。图形分类树能够较好地体现CAD模型的层次结构以及构成层次结构的图形对象信息，这些图形信息存储在作为叶子节点的体元中；在移动终端实现三维模型显示时，通过友好的交互方式选取所要显示的模型节点，计算出模型规模系数；最后，通过规模系数，选择不同体元三角面片生成策略来实现三维模型面片的生成。实现的显示效果表明，本文方法较好地解决了由于三维模型信息量巨大，信息结构复杂的特点导致的移动终端三维模型浏览效果不理想的问题，使用户关注于模型的具体细节。

下一步工作将针对模型二义性进行模型结构的优化。二义性是指某个模型可由多种方法堆积而成，比如长方体，可由一个长方体体元构造，也可由两个小的长方体体元构造。以此达到减少图元数目的目的，从另一个角度实现对模型显示精度的控制。

[1]Olatunji O A,Sher W.Estimating in geometric 3D CAD[J]. Journal of Financial Management of Property and Construction,2015,20(1):24-49.

[2]Su Zhiyong,Tang Weiqing,Li Weiqing,et al.A fast approach for constructing hierarchical levels of details of dy-namic process plant model[J].Journal of Computer-Aided Design &Computer Graphics,2008,20(8):1038-1046.

[3]Huang Xiaofeng,Song Jinyu,Yu Chenghai.Three-dimensional model drawing in mobile platform based on OpenGL ES[J]. Industrial Control Computer,2013,26(1):60-62.

[4]Yue Liting,Yu Ming,Yu Yang,et al.3D reconstruction algorithm based on facet[J].Computer Engineering,2012,38 (14):199-202.

[5]Su Zhiyong,Xia Ming,Li Weiqing,et al.Design review oriented model simplification for collaborative process plant CAD[C]//Proceedings of the 7th International Conference on Virtual-Reality Continuum and Its Applications in Industry,Singapore,Dec 8-9,2008.New York:ACM,2008:1-6.

[6]Minne L,Eslami S,Keizer N D,et al.Statistical process control for validating a classification tree model for predicting mortality—a novel approach towards temporal validation[J].Journal of Biomedical Informatics,2012,45(1): 37-44.

[7]Zhou Jian,Tang Weiqing,Zhu Yaoqin,et al.Multi-resolution rendering approach of large-scale process plant models based on programmable graphics pipeline[J].Journal of Image and Graphics,2012,17(3):426-434.

[8]Wen Rui,Tang Weiqing,Su Zhiyong,et al.Edit distance based partial retrieval algorithm for large scale process plant models[J].Computer Integrated Manufacturing Systems,2015,21(12):3349-3355.

[9]Nyamsuren P,Lee S H,Kim S.A Web-based revision control framework for 3D CAD model data[J].International Journal of Precision Engineering&Manufacturing,2013, 14(10):1797-1803.

[10]Nie Weizhi,Li Xixi,Liu Anan,et al.3D object retrieval based on Spatial+LDA model[J].Multimedia Tools&Applications,2015:1-14.

[11]Bosché F.Automated recognition of 3D CAD model objects in laser scans and calculation of as-built dimensions for dimensional compliance control in construction[J].Advanced Engineering Informatics,2010,24(1):107-118.

[12]Lee J,Kim T,Lee T,et al.Bouncing animation of a lock mode screen in a mobile communication terminal:US,US20110028186[P].2011.

[13]Shreiner D.OpenGL®programming guide:the official guide to learning OpenGL®,Versions 3.0 and 3.1[M].[S.l.]: Addison-Wesley Professional,2009.

[14]Sellers G,Wright R S,Haemel N.OpenGL SuperBible[M]. Amsterdam:Addison-Wesley Longman,2013.

[15]Zhu Longxian.The analysis and design of SQLite database encryption[J].Electronic Design Engineering,2014,22 (16):191-193.

附中文参考文献：

[2]苏智勇,唐卫清,李蔚清,等.面向动态流程工厂模型的快速分层层次细节法[J].计算机辅助设计与图形学报,2008, 20(8):1038-1046.

[3]黄小凤,宋瑾钰,俞成海.基于OpenGL ES的移动平台的三维模型绘制[J].工业控制计算机,2013,26(1):60-62.

[4]岳立廷,于明,于洋,等.一种基于面片的三维重建算法[J].计算机工程,2012,38(14):199-202.

[7]周剑,唐卫清,朱耀琴,等.基于可编程图形管线的大规模流程工厂模型多分辨率绘制方法[J].中国图象图形学报, 2012,17(3):426-434.

[8]温蕊,唐卫清,苏智勇.基于编辑距离的大规模流程工厂模型局部检索算法[J].计算机集成制造系统,2015,21(12): 3349-3355.

[15]褚龙现.SQLite数据库加密的分析与设计[J].电子设计工程,2014,22(16):191-193.

蔡强（1969—），男，重庆永川人，2003年于北京航空航天大学计算机图形学专业获得博士学位，现为北京工商大学计算机与信息工程学院教授、硕士生导师，CCF高级会员，主要研究领域为计算几何，可视化等。

XU Jie was born in 1991.He is an M.S.candidate at Beijing Technology and Business University.His research interest is computer graphics.

许杰（1991—），男，四川汶川人，北京工商大学硕士研究生，主要研究领域为计算机图形学。

LI Haisheng was born in 1974.He received the Ph.D.degree in computer graphics from Beihang University in 2002.Now he is a professor and M.S.supervisor at Beijing Technology and Business University,and the senior member of CCF.His research interests include computer graphics and scientific visualization,etc.

李海生（1974—），男，山东宁津人，2002年于北京航空航天大学计算机图形学专业获得博士学位，现为北京工商大学计算机与信息工程学院教授、硕士生导师，CCF高级会员，主要研究领域为计算机图形学，可视化等。

LI Nan was born in 1979.He received the Ph.D.degree in mechanical design and theory from Beijing Jiaotong University in 2010.Now he is an associate professor at School of Materials Science and Mechanical Engineering,Beijing Technology and Business University.His research interests include design methodology,digital design and manufacturing,etc.

李楠（1979—），男，北京人，2010年于北京交通大学获得博士学位，现为北京工商大学材料与机械工程学院副教授，主要研究领域为设计方法学，数字化设计与制造等。

CAO Jian was born in 1982.He received the Ph.D.degree from Beijing Institute of Technology in 2010.Now he is an associate professor at School of Computer and Information Engineering,Beijing Technology and Business University,and the member of CCF.His research interests include image processing and pattern recognition,etc.

曹健（1982—），男，山东临沂人，2010年于北京理工大学获得博士学位，现为北京工商大学计算机与信息工程学院副教授，CCF会员，主要研究领域为图像处理，模式识别等。

3D CAD Model Patch Generation Method in Mobile Terminal*

CAI Qiang1+,XU Jie1,LI Haisheng1,LI Nan2,CAO Jian1
1.Beijing Key Laboratory of Big Data Technology for Food Safety,Beijing Technology and Business University, Beijing 100048,China
2.School of Materials Science and Mechanical Engineering,Beijing Technology and Business University,Beijing 100048,China
+Corresponding author:E-mail:caiq@th.btbu.edu.cn

To improve the display efficiency in the mobile terminal and the display accuracy of model detail,this paper proposes a novel algorithm for 3D CAD model patch generation based on type hierarchy and object graph element. By extracting the database information such as the type and shape attributes of models,3D CAD models are represented by shape classification tree.The scale coefficient is estimated by 0-1 normalization method for classification tree node of interactive selection.After estimating the scale coefficient,the display accuracy of the model is confirmed and 3D CAD model patch is generated.Finally,this paper proposes a 3D CAD model display system in mobile terminal,and carries out the experiments on 3D CAD model patch generation.The experimental results prove the feasibility and effectiveness of this 3D CAD model patch generation method.

mobile terminal;3D CAD model;patch generation;classification tree;scale coefficient

was born in 1969.He

the Ph.D.degree in computer graphics from Beihang University in 2003. Now he is a professor and M.S.supervisor at Beijing Technology and Business University,and the senior member of CCF.His research interests include computational geometry and scientific visualization,etc.

A

TP391

*The National Natural Science Foundation of China under Grant No.51405005(国家自然科学基金);the Natural Science Foundation of Beijing under Grant No.4162019(北京市自然科学基金);the General Project of Science and Technology Development Plans of Beijing Municipal Education Commission under Grant No.SQKM201610011010(北京市教委科研计划一般项目).

Received 2016-04,Accepted 2016-06.

CNKI网络优先出版:2016-06-02,http://www.cnki.net/kcms/detail/11.5602.TP.20160602.1144.008.html

摘要：为提高三维CAD模型在移动终端的显示效率，提高模型细节的显示精度，提出了一种基于类型层次结构及对象体元的三维CAD模型面片生成方法。依据模型的数据库表示形式，抽取其必要的类型和图形信息，将三维CAD模型用图形分类树表示；对交互选择的分类树节点，使用基于离差标准化的方法估算所选节点的模型规模系数；依据规模系数确定模型的显示精度，以此进行三维CAD模型面片的生成。在移动终端开发了三维CAD显示系统并进行了三维CAD模型面片生成实验，通过实验证明了所提三维CAD模型面片生成方法的可行性和有效性。