一种基于特征保留的三维模型递进传输方法

具体实施方式

本发明包括模型简化、压缩编码、递进传输三个方面的内容，实现流程如图1所示。

1.三维模型简化

本发明采用基于二次误差的三角形折叠算法对三维模型进行简化，并在简化的同时保留模型的拓扑边界及属性特征。算法的基本操作是三角形折叠收缩，即通过对三角形T_i执行折叠操作，使它的三个顶点合并为一个顶点v_i，从而简化了原来的网格。

算法首先将原始网格中所有三角形进行分类，划分原则如下：

对于网格模型中的每一个三角形，如果它的某一条边只被一个三角形(即该三角形)所拥有，则该边为边界边，该三角形为边界三角形；对于非边界三角形，如果至少有一个顶点在边界边上，则该顶点为边界点，该三角形为角点三角形；如果三个顶点都不在边界边上，则该三角形为内部三角形。

对于包含颜色属性的模型，使用每个三角形三个顶点颜色值的平均值作为该三角形的等价颜色值，如果当前三角形与其周围邻接三角形颜色值的差超过预先指定的阈值τ，即

$\underset{p\∈C_i}{\mathrm{\Σ}}\left(\right|r_i-r_p|+|g_i-g_p|+|b_i-b_p\left|\right)>\mathrm{\τ}$

则标记该三角形为特征三角形，其中[r_ig_ib_i]^T、[r_pg_pb_p]^T分别为三角形T_i、T_p的颜色值，而阈值τ则可以根据用户对几何及属性特征保留程度的不同要求来选取，对属性细节要求越高，则τ值越小，反之则越大。

此外，对于纹理，也采取类似的办法进行处理；不同之处只是需要通过纹理坐标从纹理图像中获取相应顶点的颜色信息，再来计算该三角形的纹理等价颜色值。

之后，计算每个三角形的几何折叠误差：

(1)对于原始网格中的每个内部三角形T_i，配备一个误差矩阵Q_i，如果三角形T_i折叠为点v_i＝[x_i y_i z_i1]^T，则定义该三角形的折叠误差为新点到原三角形的所有邻接三角形平面的距离平方之和：

$\mathrm{\ϵ}\left(T_i\right)=\underset{p\∈C_i}{\mathrm{\Σ}}{\left(p^T{v}_i\right)}^2$

这里p＝[a b c d]^T表示与三角形T_i邻接的三角形集合中每个三角形所在平面的平面方程ax+by+cz+d＝0(其中a²+b²+c²＝1)。于是上式给出的误差标准可以转换为下面的二次形式：

$\mathrm{\ϵ}\left(T_i\right)=\underset{p\∈C_i}{\mathrm{\Σ}}\left(v_i^{T}p\right)\left(p^T{v}_i\right)=\underset{p\∈C_i}{\mathrm{\Σ}}{v}_i^T\left({\mathrm{pp}}^T\right)v_i=v_i^T\left(\underset{p\∈C_i}{\mathrm{\Σ}}{M}_p\right)v_i$

其中M_p是4×4的对称矩阵，能够表示三角形网格中任一点到平面的二次距离：

而误差矩阵Q_i为所有邻接三角形的平面二次矩阵相加$Q_i=\underset{p\∈C_i}{\mathrm{\Σ}}{M}_p;$对于v_i位置的选取，则通过计算使得ε(T_i)的值最小来得到。

(2)对于每个角点三角形，限定其折叠后的新点v_i为原边界上的一个顶点，并通过$\mathrm{\ϵ}\left(T_i\right)=v_i^T{Q}_i{v}_i$计算折叠误差；

(3)对于边界三角形和特征三角形，置其折叠误差为最大值。

在得到每个三角形的折叠误差之后，按最终的误差从小到大排列三角形，从三角形序列中选取折叠误差最小的三角形执行折叠操作，这样，就在保持几何相似度的前提下保证了边界三角形和特征三角形不参与折叠，从而保留了模型的边界和属性细节。

利用上述简化方法，将模型简化70％之后仍与原始模型非常接近，当简化90％以上时，所得的结果除了在几何相似性上可以接受外，仍可较好地保留原始模型的边界、轮廓及属性特征，如图2所示。

在模型简化的同时，把参与折叠消失的三角形的顶点坐标以及其相关三角形的信息记录下来，以构造递进网格文件，从而支持有效地增量传输。对于包含属性的模型，可以对顶点坐标表达进行扩展，将顶点信息表示为v_i(x_i，y_i，z_i，)，其中x_i，y_i，z_i为顶点坐标，为顶点对应的标量属性(例如对于颜色属性来说，${\stackrel{\→}{A}}_i=r_i,g_i,b_i$代表RGB颜色值；对于纹理属性，${\stackrel{\text{\→}}{A}}_i=u_i,v_i$表纹理坐标)，经过以上处理，就可以将属性信息记录在递进网格文件中，从而在重建原始几何模型的同时提供属性的恢复。

2.基网格压缩编码

本发明对简化后的基网格进行基于八叉树划分的压缩编码，对顶点的几何坐标用12bit来进行量化，主要分三个步骤：

(1)对几何模型的顶点进行八叉树的多分辨率层次化组织，直到最精细化的树节点能够表达量化的精度：首先，通过对模型设置一个最小包围盒，并按照八叉树的划分方法进行递归细分，其中每个树节点记录其子树所含顶点的个数，对于不含顶点的树节点将不再继续子分，而包含顶点的树节点将被迭代子分，直到节点为空或只含一个顶点且达到最大精度层为止；因此生成的八叉树中叶节点中心隐含表示其所包含顶点的空间位置。

(2)由粗到细以广度优先的方式遍历八叉树的各个节点，并输出描述顶点位置情况的数据流：根据节点中所含顶点的个数，对于每个非空节点，用1bit标识其是否是一个单节点；对于一个单节点，用3bits来标识该单节点中的哪个子节点包含唯一顶点；而对于非空非单节点，则产生一个8bits的标识，表示该节点的子节点是否非空；如此循环，直至访问到最精细层的节点停止。

(3)对拓扑数据进行顶点索引的重排和压缩：采用叶节点中包含的顶点从左到右的顺序重新排列顶点索引，并且更新原始拓扑数据中的对应索引值，并对拓扑数据进行压缩。

(4)将属性信息预先按照几何节点流的叶顶点的顺序排列并压缩：将属性信息预先按照几何节点流的叶顶点的顺序排列好，在编码过程中使其与几何信息同步。

(5)对所有数据流进行算术编码。

采用压缩编码后，基网格文件量有了进一步缩小。

1.递进传输

本发明采用Browser/Server结构下八叉树解码-递进网格传输的递进传输模式。在传输解码阶段，首先采用基于八叉树广度优先遍历的逐层细化方式恢复基网格；在基网格信息传输完毕后，继续采用递进网格传输的方式，传输一系列细节恢复信息，对模型进行优化和恢复。

(1)浏览器-服务器

本发明在浏览器端使用内嵌于Web浏览器的Java Applet，因而不需要用户安装独立的应用程序，就能够对三维模型进行渲染；用户可以对模型进行旋转、平移、缩放等交互式操作，还可以在场景中漫游行走，查看感兴趣区域等；此外，由于采用了递进压缩及传输策略，使得响应时间大大缩短，更适合于普通用户网上浏览。

在三维数据传输的过程中，用户在需要查看和操作模型时，可以随时控制暂停传输，此时，浏览器端向服务器发送一个等待请求，请求中包含当前的数据流位置和状态，服务器暂停发送数据；在用户停止操作时，浏览器向服务器发出下载请求，服务器根据已保存的状态信息继续向浏览器端发送数据，从而继续三维模型的细化过程。

(2)通信线程及其管理

为了达到递进传输的目的，需要一边下载文件数据，一边进行模型渲染，因而采用多线程的实现方式。

服务器将模型文件顺序的传输到客户端，客户端在接收数据的同时分析数据内容，针对内容的不同构建不同的内部模型数据表示，以便开始绘制；同时在每个新信息到达时，都需要更新内部的数据内容，并重新更新屏幕中的图像。这里需要三个线程，分别为：数据下载线程、数据分析线程和图形绘制线程(主线程)。

下载线程负责从服务器端下载文件数据，每当客户端有数据之后，便交由分析线程对数据进行语义分析，形成内部的数据描述格式。绘图线程负责将这些内部数据显示到屏幕上去。在其后的过程中，每当接收到一条新信息，便转换成内部数据描述，随后显示；如此反复进行。

在此过程中需要解决线程之间的同步问题：第一，对于下载线程和分析线程来说，在数据没有下载之前进行分析是没有意义的，这就需要在这两个线程之间进行同步；第二，在分析线程分析已下载的文件数据时，下载线程可能又下载到新的数据并要求对文件数据进行更新，这就需要在这两个线程之间进行数据的互斥访问；同样，分析线程和绘图线程之间也存在这样的问题，绘图线程只有在分析线程部分完成(完成若干条优化信息的分析)之后才能进行显示，它们之间也存在一个读写互斥。

这里采用临界区实现这三个线程对资源的互斥访问，在下载线程未将数据下载到客户端本地的时候，分析线程只能等待，只有得到数据之后才能工作。根据二者速度的不同，可分为两种情况：

(1)下载速度比分析速度慢：当分析完毕当前的数据段后，分析线程需要根据当前下载的状态决定其本身运行状态。如果当前文件未下载完毕，那么继续等待下一段数据的到来；如果当前文件已经下载完毕，分析结束。

(2)下载速度比分析速度快：此时对于分析线程来说，所要分析的数据是一直存在的，只需要在开始的时候等待第一次数据的到来即可。

对于分析线程和绘图线程来说，它们之间的同步比较简单，只要在新数据分析结束之后，绘图线程可以进行绘制。

1.三维场景传输

三维场景由不同的对象组成，其中每个对象都是一个独立的形体或结构。为此，在简化和编码阶段，将三维场景看作是若干对象模型的组合体，而对其中的每个对象进行拓扑边界完全保留的网格简化，而在传输恢复阶段，使用多数据流的方法，并采用一种面向对象的视点相关传输策略，根据用户的视点的不同选择不同的模型对象进行优化。

首先为场景的每个对象建立了一个单独的数据流，因而对于每个数据流来说，都可以采用前述八叉树解码-递进网格传输的递进传输模式。与简单的对象模型传输不同，本发明设计了一个面向对象的视点相关的传输框架，如图3所示，服务器端提供模型数据并保存当前模型对象的传输状态，客户端下载数据并重构、渲染模型。除了下载、分析、绘图线程外，为客户端再增加一个可见性判断线程，用来计算视点信息，并根据视锥可见性判断需要传输的对象；服务器只需要接收每个客户端传送的所需对象标志，就可以发送相应的优化信息。这样，就将计算负载分散给每个客户端，从而提高了服务器的效率；而对于客户端来说，由于这种可见性判断是粗粒度的面向对象的，因而也不会造成大量的计算，影响可视效果。

该框架整个执行过程为：

(1)客户端向服务器发出场景传输请求；

(2)服务器接收客户请求，与该客户端建立一个连接，同时查看该用户请求的模型数据是否已经调入内存，如果没有则将其调入内存，然后为该场景的每个对象建立一棵八叉树；

(3)服务器向客户端传输每个对象的基网格数据(顶点的坐标、面的索引以及其它相关信息)；

(4)客户端接收完毕基网格信息后，进行显示；

(5)客户端根据自己的视点计算当前可见的对象，并将可见性状态传输到服务器；

(6)服务器根据当前客户端状态传输当前可见对象的优化信息，并将其他对象的优化信息数据流的传输暂停，保存当前状态；

(7)客户端每接收到一条优化信息，便对模型进行细化，并重新绘制；

(8)如果视点改变，重复上述(5)；

(9)客户端退出，服务器清理无用的状态信息。

利用上述传输方法，对模型进行递进传输，图4为一个观音模型的传输，首先进行八叉树解码，在得到基网格后，进而进行递进网格传输恢复。从图4传输过程可以看出，在八叉树启动并解码传输20％之后得到的基网格，与原始模型除了在几何相似性上非常接近外，还较好地保留原始模型的边界、轮廓及纹理特征。

图5为对场景中一组兵马俑模型进行递进传输的过程，其初始过程仍相似，首先对当前可见的兵马俑模型进行八叉树解码传输；随后视点拉近，部分对象进入视野并参与细化；当视点继续转动时，原先在窗口外的兵马俑模型由于刚开始传输，仍然显得比较粗糙。