张承钿 赵静
摘 要：由于传统单凭经验使用插座式积木搭建大型场景模型时会出现费时费力，无法提前统计成本等难题，所以急需开发出一个积木智能搭建系统。邦宝模型积木分析系统正是应企业需求开发，涉及到智能选择不同形状的积木来完成每一层的铺设、上下层交叉铺设、模型不同位置不同染色、减少零碎颗粒等要求，针对这种情况，提出了基于OpenGL技术，设计出相应的算法。本文从工程应用的角度出发，简要介绍了3DS文件格式，系统用到的开发平台及OpenGL技术，整个系统的结构总框架及功能，基于扫描法的栅格化算法、单层积木铺设算法及上下层粘连性检验算法。在此基础上实现了从3D模型文件导入、模型调整、切片分层、颗粒化到输出积木搭建方案的全自动化。
关键词：积木;3D模型;OpenGL
0 引言
随着当今时代计算机技术的突飞猛进，三维图形技术在建筑虚拟、场景漫游、虚拟教育、3D游戏等各方面的应用越来越广泛。同时各种3D模拟积木软件也得到迅猛的发展，目前国内外应用较多的软件有Lego Digital Designer、MLCad、LDView、LPub等，虽然这些都是非常优秀的3D模拟积木软件，但它们并没有一个软件能彻底解决从三维模型导入、模型调整、切片分层、颗粒化到输出积木搭建方案的全自动化。
OpenGL是一个功能强大的三维图形开发接口，由于它方便而强大的三维图形的绘制功能，并具有可靠性高、可扩展性、可伸缩性、容易使用、灵活性和可移植性等优点，因此应用OpenGL开发技术能够极大地提高开发效率。尽管很多文献[1-4]介绍了利用OpenGL技术对3DS模型数据进行读取、显示和控制的方法，但大多数只涉及到基本的静态3DS模型数据的使用，并没有对动态数据进行处理。本文基于OpenGL技术对邦宝模型积木分析系统进行了研究，通过这个系统，我们可以读取出3DS模型文件并对其进行显示控制，然后通过切片、颗粒化等一系列操作计算出在使用邦宝基本部件搭建一个模型时所需要的部件种类、个数及每层的积木搭建排列，进一步计算出整个模型所用积木的总重量及总价格。
1 3DS文件格式简介
3DS是Autodesk公司存储3D模型数据的一种文件格式。
3DS文件结构由许多块组成，每个块由信息类别和下一个块的相对位置两部分组成，其中块的信息类别用ID来标识。由于每个块指出了下一个块的相对于该块起始位置的偏移字节数，这样即使你不明白这个块的含义，也可以很容易地忽略它。与许多文件格式一样，3DS二进制文件中的数据也是按低位在前、高位在后的方式组织的。例如，两个十六进制字节0x4A5C组成的整型数，表明5C是高位字节，4A是低位字节[5]。
3DS文件中块的前两项信息分别是块的ID和块的长度，其中块的ID是一个整型数，而块的长度是一个块相对于该块的字节偏移量，是一个长整型数。3DS文件中每个块是一个层次结构，不同类型的块具有不同的层次结构。每一个3DS文件的开头都是由一个根块构成，它包含了整个文件，其ID是0x4D4D。根块内的块称为主块，主块有3D编辑程序块和关键帧块两种类型。主块后面是该主块所包括的子块，而3D编辑程序块是物体的形体数据定义的开始。3D编辑程序块的子块包括材质列表块、物体块等，而物体块又包含了网格块、亮度信息块、相机参数块等。其中网格块包括位置信息块、顶点列表块、面信息块等;关键帧块定义关键帧的信息。3DS文件这种复杂的块层次结构的优势在于即使我们并不知道每一个块的具体含义，在程序中读取3DS文件类型的模型时，完全可以忽略掉那些不感兴趣或不需要的块信息，仅读取所需要的块。
2 开发平台和技术
2.1 使用C#编程语言
C#是一种完全建立在Microsoft.NET框架平台上的高级编程语言，它几乎集中了所有关于软件开发和软件工程研究的最新成果，如面向对象、类型安全等。C#充分利用了.NET框架的优点，是开发.NET框架应用程序最好的语言之一。与VC++相比，C#的程序调试更加容易，语法更加简洁，且可以更加快速地开发应用程序。把C#和OpenGL结合起来开发3D图形程序和软件，将显着提高开发效率[6]。
2.2 使用OpenGL技术
OpenGL的英文全称是“Open Graphics Library”，即“开放性图形库”，它是计算机工业标准3D应用程序接口，是一个功能强大，调用方便的底层3D图形库。作为图形硬件的软件接口，OpenGL由几百个指令或函数组成，这些指令允许用户说明二维几何对象或三维几何对象，允许用户对对象实施操作以便把这些对象着色到帧存上。OpenGL作为一个性能优越的图形应用程序设计界面（API），适用于广泛的计算机环境。OpenGL是一套底层三维图形API，之所以称之为底层API，是因为它没有提供几何实体图元，不能直接用以描述场景。但通过一些转换程序，可以很方便的将AutoCAD、3DS等图形设计软件制作的3DS模型文件转换成OpenGL的顶点数据。由于OpenGL提供了清晰明了的图形函数，所以不要求开发者把三维物体模型的数据写成固定的数据格式，开发者不但可以直接使用自己的数据，而且可以利用其它不同格式的数据源，这种灵活性极大地节省了开发时间，提高了开发效率。因此我们选择使用OpenGL技术进行开发。
2.3 在C#中使用Tao框架实现OpenGL建模技术
由于OpenGL的广泛应用，它已经成为了一个工业标准。
目前虽然有很多软件开发商提供的程序设计语言都提供了对开发基于OpenGL应用软件的支持，如Visual C++，C++builder等。但是并没有提供在C#中开发OpenGL的标准和规范的方法，而且，在.NET框架中也没有提供0penGL API的接口。目前在C#中可以通过CsGL等第三方软件进行OpenGL建模的技术，也可以基于Tao技术，因为Tao Framework提供了许多基于.NET和Mono的库，它是由美国华盛顿大学分布式对象计算组织开发的开放源码的CORBA（通用对象请求代理体系结构）产品，它实现了C0RBA2.6规范中的说明。因此，我们利用Tao框架实现在C#中进行OpenGL建模的方法[7]。
2.4 使用SharpGL扩展库
SharpGL是C#对OpenGL库的封装，是一个方便我们在Windows窗体中和WPF中使用OpenGL的扩展库，它能够设置一个强大的场景图和Visual Studio模板。SharpGL扩展库包装了所有当前的OpenGL函数，所有主要的扩展和一套丰富的先进功能的对象，并且能够将代码移植到其它的平台中，所以我们使用它很容易开发出3D图形程序。它的命名空间包括：
①SharpGL：包含OpenGL的主要对象，这个对象封装了所有的OpenGL函数、枚举和扩展。
②SharpGL.SceneGraph：包含所有包装OpenGL的对象和场景中的元素-灯光、材料、纹理、材质等。
③SharpGL.WinForms：为我们的应用程序包含Windows窗体控件。
④SharpGL.WPF：为我们的应用程序包含WPF控件。
⑤SharpGL.Serialization：包含用于装载几何和来自于3D Studio Max文件的数据，不引人注意的obj文件和truespace文件的类。
3 邦宝模型积木分析系统设计与实现
3.1 系统概述
积木是公认能培养儿童创造力、学习能力以及训练手眼协调的最佳工具，积木中的排列，接合，环形，对称等都对开发孩子的智力有好处。积木的生产是个很有发展前景的项目，但是由于组成实物的小积木块，一般都由几百、几千甚至上万个小积木组成，零件的数据量庞大，目前大部分玩具厂商都是先通过先人手动地拼成我们需要的积木实体形状，再统计所需的积木小零件的种类和总个数，最后交由工厂生产，显然这过程的任务很繁重，拼装设计时稍微的改动对整体的影响很大，效率也很低。如果积木的拼装和统计能用计算机模拟，那将极大地节约人力、物力和成本。因此，我们急需开发出一个系统，能够用计算机来实现从三维模型导入、模型调整、切片分层、颗粒化到输出积木搭建方案的全自动化，这样既能节约生产成本和生产周期，又能提供实践指导。
本系统的目标就是建立一个3D图形应用程序，用于计算在使用邦宝基本部件搭建一个模型时所需要的部件种类、个数及输出每层的积木搭建排列方案，进一步计算出搭建这样的模型时的初步报价。不同形状的积木可以由不同的颗粒状的积木块（积木砖）组成，积木的拼装过程整体上可以看出是从下到上（或从上到下）。对于给定实物模型的3D外观数据，用计算机模拟分层切割过程，计算出每层的排列情况并显示，且满足以下条件：
①所用的积木块数量总数尽量少，即中心部分是骨架连接或镂空的。
②拼成后积木尽可能的牢固。
③拼成后尽可能的逼近原始形状的物体。
3.2 系统结构总框架设计
邦宝模型积木分析系统主要包括八大功能模块，即数据导入、数据管理、模型副本管理、模型副本分层、分层颗粒化、积木搭建、查看三维图、数据导出，这些模块又是由若干个子模块构成的，系统结构总框架如下图所示：
图一 系统结构总框架图
3.3 系统的主要功能介绍
系统的主要功能如下：
①数据导入
基本部件：导入邦宝基本部件的3DS文件。
三维模型：导入模型的3DS文件。
②数据管理
数据修改：修改部件及模型的基本数据并保存在数据库。
数据计算：计算部件及模型的长、宽、高等数据并保存在Access数据库。
数据增删：添加或删除部件或模型的相关数据。
③模型副本管理
副本增删：按某个比例放大或缩小原始模型来添加其副本或删除模型副本及其相关数据。
副本编辑：修改模型副本的相关数据，设置镂空壁厚、分层方式等参数并保存在Access数据库。
④模型副本分层
部件选择：可以选择不同类型的部件，如小颗粒块（砖）等， 按所选部件的高度将模型等距地分为若干层并进行切片操作。
最优分层：将各层分层后所得矢量多边形进行栅格化，并提供基础性的镂空及编辑功能（一般大型积木模型不会是实心的）。
⑤分层颗粒化
颗粒化：将分层得到的平面多边形用不同颜色的小方块最佳覆盖，对模型的所有层进行颗粒化。
镂空设定：用户可以调整镂空时的厚度参数。
⑥积木搭建
底层排列：第一层是底层，在此层的部件排列方式与其它层不同。
逐层排列：每层在它下层排列的基础上进行积木排列，准许用户调整镂空时的厚度参数，并提供上下层粘连性检验，但要保证搭建的模型牢固。
⑦查看三维图
三维显示及编辑：查看部件和模型的三维图，能够用鼠标进行三维图的旋转、缩放和平移等交互操作，并提供对积木模型的编辑功能，如对某块积木的增删、着色、移动等。
单层显示：查看整个模型每一层的三维图。
双层显示：查看整个模型每两层叠加在一起的三维图。
三层显示：查看整个模型每三层叠加在一起的三维图。
所有层显示：查看整个模型所有层的三维图。
⑧数据导出
积木统计：系统可以计算出模型中总共使用的部件种类及其数量，进而计算出其总重量及总价格。
数据导出：系统可以导出3DS和bmp格式的文件。
3.4 系统的核心算法简介
3.4.1 3DS文件导入算法
在数据读取之前，首先要建立存储点、面、材质、对象等信息的数据结构，以用来保存3DS模型数据。OpenGL读取3DS的算法思路是：首先根据偏移量和长度找到一个块的ID标识符，再根据这个来判断它是什幺块，遇到我们需要的块，就进一步读取，如果不需要，直接忽略这一块，读取下面的块，最后循环遍历所有的块，即读出各个数据块[9]。
读取出3DS文件后，需要在OpenGL环境下将读出来并存在数据结构中的3DS文件信息绘制出来。在绘制场景时，首先计算法向量，它直接影响到光线从不同的角度入射到模型表面，产生不同的显示结果，如果法向量不确定，三维效果的图形是显示不出来的。再通过模型的各种变换来实现法向量的计算，本系统首先遍历对象的面和顶点的所有信息，从而计算出这些信息的法向量，并将法向量添加到法向量列表中。然后根据存储在自定义的数据结构的信息，这样OpenGL就能将模型绘制出来。
3.4.2 基于扫描法的栅格化算法
整个模型的颗粒化需要对模型副本所有分层得到的矢量多边形进行栅格化。目前虽然已存在多种栅格化算法[10]，如常见的有内部点扩散法、边界代数法、边界点跟踪算法、射线法、扫描法等，但每种算法都有自己的缺陷。本系统采用了各方面性能比较平衡的扫描法，虽然避免了上述的内部填充过程，但模型的颗粒化模块在设计的过程中还遇到了一些特殊问题。因此本系统的算法设计在扫描法的基础上，添加了横边表并制定了更加详细的规则，使其能正确处理各种特殊情况。
3.4.3 单层积木铺设算法
根据现实中经验丰富的员工搭建的每一层积木大体上是十分规律的，只是在局部上作出某些调整。因此在本系统提出这样一种算法，这种算法可分三个部分，一是利用“基本件”的特点，选取了1×1、1×2、1×3、2×2、2×3和“L型拐”这6种积木为基本铺设颗粒，采用贪心加局部搜索的算法铺设;二是为了减少零碎颗粒，就近调整“单粒”;三是“并小为大”，将基本铺设颗粒拼合成大的积木。结果证明，此算法可以很好地完成积木铺设问题。
3.4.4 上下层粘连性检验算法
一个合格的积木模型搭建方案必须确保这个积木模型不散架，在本系统中，通过上下层粘连性检验算法来达到这一效果。这个算法可分为两个方面，一是相邻层采用不同的优先顺序可以巧妙地使相邻层的积木尽量多的交叉相扣，增强上下层的粘连性;二是结合并查集算法，将每块积木视为图中的一个结点，为积木粘连问题建立图论模型。通过这两个方面的相互配合，不仅在一定程度上提高了运算速率，而且较好地保证了模型的粘连性。
4 结束语
邦宝模型积木分析系统的成功使用，能够用计算机实现从三维模型导入、模型调整、切片分层、颗粒化到输出积木搭建方案的全自动化。这不仅在一定程度上节约了大型模型的搭建时间和生产成本，而且为员工提供了实践指导，有效地提高了工作效率。本文基于OpenGL技术对邦宝模型积木分析系统进行了研究，简要介绍了实现这一系统所需的开发平台、技术及算法。由于时间和知识水平的限制，本系统还存在着很多的不足之处，比如在整个积木模型的内部镂空、积木模型的受力分析（如积木悬空部分、倒吊部分）等方面还是比较不足的。对此，我们可以进一步研究，将本系统的相关知识运用到其他工程项目中。
参考文献：
[1]施瑞奈尔（DaveShreiner）.OpenGL编程指南[M].北京：机械工业出版社，2010.
[2]赖特（RichardS.Wright.Jr）.OpenGL超级宝典[M].北京：人民邮电出版社，2010.
[3]Donald Hearn，M.Pauline Baker.计算机图形学（第四版）[M].北京：电子工业出版社，2012.
[4]吕希奎，周小平.实战OpenGL三维可视化系统与源码精解[M].北京：电子工业出版社，2009.
[5]刘芳，刘贤梅.3DS文件读取、绘制与控制方法的研究与应用[J].计算机工程与设计，2009，30（19）：4575-4578.
[6]高明向，陈定方.OpenGL建模技术在C#中的实现[J].武汉理工大学学报，2005，27（1）：65-68.
[7]门光福，田芳.基于Tao框架的C#中OpenGL建模技术的实现[J].新余高专学报，2006，11（6）：73-74.
[8]殷素峰，高雪强，杨胜强.在OpenGL环境下开发3DS 文件浏览器[J].工程图学学报，2005，26（6）：22-25.
[9]陈雪梅，谢清钟.浅析一种运用OpenGL导入显示3DS三维模型的方法[J].吉林省教育学院学报，2012，28（299）：86-87.
[10]周琛，陈振杰，张帅.基于边界代数法的矢量栅格化并行算法设计与实现[J].计算机工程与科学，2013，35（4）：37-41.
作者简介：
张承钿，男，1961.02.24，籍贯：德国，副教授，研究方向：软件工程及项目管理、云计算技术在科学计算中的应用、流体力学计算。
赵静，女，1991.01.01，湖北崇阳人，汉族，硕士研究生，研究方向：软件工程。
