□   山西省专用通信局  林  妍

内容提要  本文简介了一种对三角形网格的三维几何数据压缩算法, 采用顺序树实现三维模型的拓扑结构压缩和几何数据压缩，可以达到在精度损失较小的情况下对拓扑结构和几何数据的有效压缩。在对大量实验数据的分析下，得到比较理想的压缩效果。
关键词  三维几何压缩  三角形  网格
1. 前言
      随着计算机的不断发展，计算机图形得到越来越广泛的利用。屏幕上的图形是由显示缓冲器的数据决定的，结构简单，但存储空间较多，为数据存储和传输带来了不便；实时性要求较高的系统若采用通常的数据压缩，恢复时却又难以满足实时性。而三维几何数据压缩不仅可以提高图形数据的存储效率，而且保证了图形处理的实时要求。
      1995年至今，三维几何压缩技术不断发展：Michael Deering[2]提出的基于通用三角形网格的几何压缩算法，压缩比可达6/1～10/1，物体失真度较小，但最优通用三角形网格的求解较困难。Gabriel Taubin和Jarek Rossignac[3]提出了基于拓扑手术的几何数据压缩算法，提出了非链式的扩展方式的新思路，但在支路上仍然存在不连续性和不稳定性。而破边法[4]是对拓扑手术压缩算法的增强和改进，使用的转角表数据结构使得实现比较简单。
      鉴于以上，综合改进出采用顺序树的拓扑结构压缩和几何数据压缩算法。该算法是以环状三角形带对三维几何图形进行扩展，以环的每个顶点继续扩展新环，利用树的数据结构进行存储。
2.    采用顺序树的拓扑结构压缩算法和几何数据压缩算法
2.1 思想：
      该算法是以Deering 算法为雏形，基于拓扑手术算法提出的，利用树或森林来对三维几何数据的拓扑结构和几何数据进行压缩。拓扑结构压缩算法是以环状三角形带对图形进行扩展，以环的每个顶点继续按正序和逆序扩展新的环，用树的数据结构来存储数据，按照从左至右，从上至下的顺序存储顶点的扩展顺序，位于同一个环带上的三角形的顶点作为树的同一层兄弟，在树中的父子，兄弟，子女位置的顶点与图中的顶点关系一一相对应；而几何数据压缩利用拓扑结构扩展得到的树中的子女，兄弟以及兄弟的子女相互关系得到相对的差值来表示，并将浮点数转化为定点数以节省存储空间。    
2.2数据结构：
为了压缩的方便和易于识别，将三角形网格图形的每个三角形，及其顶点﹑边进行了标识。
2.2.1原始数据结构：
       a.模型的点表：
对原始三角形分解图扫描，对数据检索，将图形中的每个顶点及其三维坐标录入：
顶点序号：该顶点在三角形网格图形中的编号。
X、Y、Z坐标值：该顶点在三维模型中的空间三维坐标值。
b.模型的面表：
      将图形中每个三角形的顶点编号录入：2.2.2压缩过程中使用的过渡结构表：
将每一条边及其两个顶点和所在的两个三角形的序号录入：
所在三角形1、2序号：拥有该条边的两个三角形在图形中的编号。当只有一个三角形拥有该条边，则其一数据为0。
2.2.3压缩的主结构表：
 兄弟、子女位：是所要存储的点与其周围的点的关系标识。
顺序位：默认值是0，表示节点最右子女和它的后继点存在一条边。
连续位：默认值是1，表示节点和它的后继点存在一条边。当它为0时，它的子女的连续位为0。
X、Y、Z差值坐标：表示所要存储的点坐标的相对三维向量差值。
 2.3拓扑结构的压缩：
三维模型拓扑结构的压缩中，检索模型数据与树有着关联，因而将扩展与树对应关系为：
2.3.1 树的根节点：
对图形进行拓扑结构压缩时，起始节点是一条边界边的一个顶点。边界边是指唯一的属于一个三角形，选取边界边是为了保证压缩过程中减少数据冗余。
2.3.2 拓扑结构扩展：
i. 节点ai没有左兄弟时不扩展；节点ai存在左兄弟，但其左兄弟ai-1的连续位为0（即节点ai和节点ai-1之间不存在一条边），则节点ai不扩展。
        ii.节点ai-1 不存在子女节点，且该节点的连续位为1时，用节点ai-1和节点ai所组的边aiai-1对节点ai扩展；节点ai-1存在子女节点，且该节点的顺序位为1 时，用边aiai-1对节点ai扩展。
iii. 节点ai-1的连续位为1，且顺序位为0时，以边aiam对节点ai扩展。
        iv.  逆序扩展：以边aibi 对节点ai 扩展，当存在未检索三角形时，得到cici+1…cj。
2.3.3 结束扩展：
 i. 正常结束：
     节点ai扩展出的下一个点bm与节点ai+1(该节点是节点ai的右兄弟或后续点)为同一个点时，则停止对节点ai 扩展。
 ii.异常结束：
节点ai扩展出的下一个点bm时，但节点bm已被检索过，节点bm不是节点ai的右兄弟或后继点ai+1（即边aibm是边界边）,则停止对节点ai扩展，同时置节点ai的顺序位为1，而节点bm-1的连续位为0。
2.4顺序树中节点间关系：
1.节点A经扩展得节点B时，则节点B是节点A的子节点，节点A的子女位为1。
2.节点A 与节点B都是它们的父节点扩展出来的节点时，则节点A与节点B是兄弟节点，则节点A的兄弟位为1。
3.节点A与其右节点B之间存在一条边时，节点A的连续位为1，反之，则为0。
4.节点A经顺序扩展，则它的左兄弟节点B的顺序位为1。反之，默认情况下，顺序位为0。
5.特殊用法：为节省存储空间，节点A为曾经存储过的节点，并且节点A不存在子节点，则置该节点的顺序位为1，在该节点的数据位存放的是该节点曾存储的地址。
2.5 几何数据的压缩
对三维模型中的空间三维坐标的三个坐标值的压缩的过程是：
       i.  将原始的三维坐标值转化为正数，然后归一化；
ii. 根据压缩中顺序树的兄弟和子女节点，将归一化的绝对数据化为相对数据。
计算公式是：ε=Vn-f(λ,Vn+1,…,Vn+j)
其中：f(λ,Vn+1,…,Vn+j)= λiVn+i
      λ1+λ2+…+λj=1 ,λi是系数，λi =1/j
        Vn表示要存储的节点归一化后的绝对三维坐标值；
        （Vn+1,…,Vn+j）表示符合规则的相邻节点归一化后的绝对三维坐标值；
         计算相邻节点的规则是：
1. 节点Vn是非叶子节点时，需检索该节点的左兄弟的最右子女，其本身的所有子女节点，以及该节点连续位为1时的后继节点最左子女，这些节点就为（Vn+1,…,Vn+j）表示的相邻节点。当某节点不存在，则不录入相邻节点，只须计算存在的相邻节点。       
2. 节点是叶子节点时，相邻节点表示的是所有相互连接的叶子节点。
       iii. 最后将相对三维坐标值进行浮点数化为定点数：用2位表示浮点数化定点数时改变的位数，用8位存储定点数的三维坐标值。
3结束语
      该算法在已有算法的基础上，对拓扑结构压缩算法进行了改进，经大量图形数据的试验，达到预计效果,而后对拓扑结构压缩算法中未能解决的三维坐标的压缩,进行了分析和研究，经过试验数据的验证,实现较大的压缩比,精度损失也保持在一定范围内,压缩速度比较快。