论文部分内容阅读
摘要：通过对三维模型原始三角面片的规格化，对原模型内的三角面片进行基于体素的划分和表示。将规格化后的三角面片进行基于连接边的分类，并对每一连接边类型对应的三角面片的位置进行编码。通过找寻规格化后的三角面片之间的表示特点，探索具有规律性的存储方法。实验结果表明，该方法能够有效的降低三维模型的存储空间，提高存储效率。
关键词：体素；规格化；连接边；三角面片
中图分类号：000000 文献标识码：A DOI：10.3969/j.issn.1003-6970.2016.04.008
0 引言
近年来，计算机三维模型的表示与存储方法成为计算机模型构建领域的研究热点。目前，三维模型的表示大多采用三角面片法，这种方法有很多优点：面、边、点及其拓扑关系完备，有利于生成和绘制线框图、投影图，有利于计算几何特性，易于同绘图软件衔接和关联等。但是，由于三角面片的大小与形状各异，毫无规律，使得数据的保存比较复杂。本文在三角面片表示的基础上，对面片进行规格化，重新对三维模型进行基于体素的表示，使模型的三角面片成为类型已知和大小可控的面片。通过对模型进行分层处理，探索规格化后三角面片之间的联系，从而达到压缩模型存储空间的目的。用本文的方式存储三维模型，可以极大的压缩模型数据，节省空间。
1 三维模型的规格化
1.1 三维模型的表示和提取
用SolidWorks软件对模型文件进行处理，生成对应的VRML文件（.wr1）。提取文件内各三角面片的点信息和面片索引信息，获得三角面片的点表与面表。这类三维模型的表达方式是常用由大小形状各异的三角面片组成，为本文所描述的原始模型。
1.2 体素的表示
由于原始模型中三角面片毫无规律可循，为了解决这个问题，提出体素的概念。将三维空间用平行于坐标面的平面划分成小方格（即体素），这样在每个体素内由8个顶点中的任意3个顶点可组成一个三角面片。这样的三角面片数量和位置是固定的，所以对每个三角面片用一个数字来表示。在表示三维物体模型时，在物体的边界体素上从上述三角面片中找一个与物体表面最接近的三角面片来表示物体。将这些三角面片连接起来就可表示整个三维物体。如此获得的三维模型全部是用已知的三角面片构成，整理和应用起来都更加方便、有序。
1.3 规格化
把原始模型中未知的三角面片转换成基于体素的已知的三角面片，称为规格化。其方法是，先对原始模型分层，再确定点面信息。
分层的过程，对原始模型的三角面片按垂直于某一坐标轴的切面进行切割，获得当前切面与模型三角面片的交点对。观察点对不难发现，对于任意一个点对，必有另外两个点对与其拥有公共点。照此关系链接所有点对，可得到当前层的轮廓线。按照此方法，对原始模型进行分割，生成各层轮廓线。
得到各层轮廓线之后，将组成相邻两层轮廓线上的点进行三角剖分。利用插点的方法将轮廓线上的三点组成一个新的小三角形，保证三角形都是单位大小且没有任何轮廓线上的点剩余，在满足上述两个条件基础上使轮廓线形状改变尽可能小。如图1所示。
最终得到的三维模型是一个基于体素的分层次规格化后的三角面片构成的模型。以三维模型Bunny为例，规划化后的模型表示如图2所示。
1.4 规格化优点
由于体素的规格是可控的，所以基于体素的三角面片的大小也是可以调整的。对于三维模型中难以构建的细节问题，可以把体素的规格设置到足够小，用细化后的三角面片来表示更为合适。而对于三维模型中简单的平面等，可以根据需要来设置体素的规格。图3给出了用三种不同规格的倒示的同一个模型。
2 压缩算法流程
2.1 面片分类
上述体素中，共有56种三角面片，可对这些三角面片进行分类编号。体素中，每两点连接都能成为某个三角面片的一条边，称为连接边。经分析，共有13种连接边。每种连接边和体素中其它任意一点连接都能构成一个三角面片。把所有三角面片进行归类整理，可总结出每种连接边下所有的三角面片种类及个数，其中不同连接边对应的三角面片可重复。
2.2 遍历模型
对规格化后的三维模型，用基于体素的三角面片对其进行分层遍历。由于体素中的三角面片包含多个层次。在遍历时，模型每层中按一个方向顺序遍历，不能遍历完整的三维模型。为此，遍历三维模型需要沿两个方向分层遍历。首先，沿x轴对模型进行分层遍历，再沿y轴对模型进行分层遍历。这样，能够实现对三维模型的遍历。
2.3 数据压缩
在上述面片分类中，共分为13种连接边。对连接边进行编号，并且对连接边对应的三角面片进行编号。这样每个三角面片，都可以用连接边编号和面片编号来表示。由于规格化后的三维模型是分层遍历，每层的三角面片可看作一个三角面片链。由此得到模型的各层编码链。
对每一连接边对应的三角面片分别编号，最多需要4位二进制数。可见，加上连接边编号的一位二进制数，表示一个三角面片总共只需5位二进制数。对于规格化后的三维模型，所有面片都可以用5位二进制数表示。这极大压缩了原始模型的数据。对三维模型Bunny进行了实验，具体压缩效果如表1所示。
3 结语
三维模型应用广泛，其表示方法和数据存储对模型的应用有着重要的意义。本文提出一种基于体素的规格化三维模型三角面片表示方法。将规格化后的三角面片按层次遍历，可获得用固定比特位表示三角面片的链式存储方式。由于定义的规格化三角面片的数据结构占用存储空间较小，因此可以有效的降低三维模型的存储空间。
关键词：体素；规格化；连接边；三角面片
中图分类号：000000 文献标识码：A DOI：10.3969/j.issn.1003-6970.2016.04.008
0 引言
近年来，计算机三维模型的表示与存储方法成为计算机模型构建领域的研究热点。目前，三维模型的表示大多采用三角面片法，这种方法有很多优点：面、边、点及其拓扑关系完备，有利于生成和绘制线框图、投影图，有利于计算几何特性，易于同绘图软件衔接和关联等。但是，由于三角面片的大小与形状各异，毫无规律，使得数据的保存比较复杂。本文在三角面片表示的基础上，对面片进行规格化，重新对三维模型进行基于体素的表示，使模型的三角面片成为类型已知和大小可控的面片。通过对模型进行分层处理，探索规格化后三角面片之间的联系，从而达到压缩模型存储空间的目的。用本文的方式存储三维模型，可以极大的压缩模型数据，节省空间。
1 三维模型的规格化
1.1 三维模型的表示和提取
用SolidWorks软件对模型文件进行处理，生成对应的VRML文件（.wr1）。提取文件内各三角面片的点信息和面片索引信息，获得三角面片的点表与面表。这类三维模型的表达方式是常用由大小形状各异的三角面片组成，为本文所描述的原始模型。
1.2 体素的表示
由于原始模型中三角面片毫无规律可循，为了解决这个问题，提出体素的概念。将三维空间用平行于坐标面的平面划分成小方格（即体素），这样在每个体素内由8个顶点中的任意3个顶点可组成一个三角面片。这样的三角面片数量和位置是固定的，所以对每个三角面片用一个数字来表示。在表示三维物体模型时，在物体的边界体素上从上述三角面片中找一个与物体表面最接近的三角面片来表示物体。将这些三角面片连接起来就可表示整个三维物体。如此获得的三维模型全部是用已知的三角面片构成，整理和应用起来都更加方便、有序。
1.3 规格化
把原始模型中未知的三角面片转换成基于体素的已知的三角面片，称为规格化。其方法是，先对原始模型分层，再确定点面信息。
分层的过程，对原始模型的三角面片按垂直于某一坐标轴的切面进行切割，获得当前切面与模型三角面片的交点对。观察点对不难发现，对于任意一个点对，必有另外两个点对与其拥有公共点。照此关系链接所有点对，可得到当前层的轮廓线。按照此方法，对原始模型进行分割，生成各层轮廓线。
得到各层轮廓线之后，将组成相邻两层轮廓线上的点进行三角剖分。利用插点的方法将轮廓线上的三点组成一个新的小三角形，保证三角形都是单位大小且没有任何轮廓线上的点剩余，在满足上述两个条件基础上使轮廓线形状改变尽可能小。如图1所示。
最终得到的三维模型是一个基于体素的分层次规格化后的三角面片构成的模型。以三维模型Bunny为例，规划化后的模型表示如图2所示。
1.4 规格化优点
由于体素的规格是可控的，所以基于体素的三角面片的大小也是可以调整的。对于三维模型中难以构建的细节问题，可以把体素的规格设置到足够小，用细化后的三角面片来表示更为合适。而对于三维模型中简单的平面等，可以根据需要来设置体素的规格。图3给出了用三种不同规格的倒示的同一个模型。
2 压缩算法流程
2.1 面片分类
上述体素中，共有56种三角面片，可对这些三角面片进行分类编号。体素中，每两点连接都能成为某个三角面片的一条边，称为连接边。经分析，共有13种连接边。每种连接边和体素中其它任意一点连接都能构成一个三角面片。把所有三角面片进行归类整理，可总结出每种连接边下所有的三角面片种类及个数，其中不同连接边对应的三角面片可重复。
2.2 遍历模型
对规格化后的三维模型，用基于体素的三角面片对其进行分层遍历。由于体素中的三角面片包含多个层次。在遍历时，模型每层中按一个方向顺序遍历，不能遍历完整的三维模型。为此，遍历三维模型需要沿两个方向分层遍历。首先，沿x轴对模型进行分层遍历，再沿y轴对模型进行分层遍历。这样，能够实现对三维模型的遍历。
2.3 数据压缩
在上述面片分类中，共分为13种连接边。对连接边进行编号，并且对连接边对应的三角面片进行编号。这样每个三角面片，都可以用连接边编号和面片编号来表示。由于规格化后的三维模型是分层遍历，每层的三角面片可看作一个三角面片链。由此得到模型的各层编码链。
对每一连接边对应的三角面片分别编号，最多需要4位二进制数。可见，加上连接边编号的一位二进制数，表示一个三角面片总共只需5位二进制数。对于规格化后的三维模型，所有面片都可以用5位二进制数表示。这极大压缩了原始模型的数据。对三维模型Bunny进行了实验，具体压缩效果如表1所示。
3 结语
三维模型应用广泛，其表示方法和数据存储对模型的应用有着重要的意义。本文提出一种基于体素的规格化三维模型三角面片表示方法。将规格化后的三角面片按层次遍历，可获得用固定比特位表示三角面片的链式存储方式。由于定义的规格化三角面片的数据结构占用存储空间较小，因此可以有效的降低三维模型的存储空间。