随着海战场感知手段的不断增强，海战场环境信息保障方式开始向三维可视化方向发展。研究海水温度的三维可视化，把不可见的海洋环境参数物理量转变为可见的形式，直观地描绘蕴含其中的丰富内涵和潜在规律，不仅在海战场环境信息保障中具有重要的应用，还在地方渔业、海洋牧场等方面都具有广泛的应用前景。目前关于温度场的可视化出现了一些研究成果[1-4]，杨冠杰等[3]利用多重二次型插值法对散乱体数据建模，进而用光照模型进行整体可视化，并采用Marching Cube算法绘制等温面，得到了较好的可视化效果。但该算法在处理大量数据时计算量明显增大，而且还会出现空洞问题[4]。近年来，三维Delaunay三角化方法由于具有完整的理论基础和较好的实践效果，得到了广泛的研究和应用[5-8]。

Bowyer [9]和Watson[10]将二维Delaunay三角化推广到多维，进而出现了一些利用Delaunay三角化构建表面的算法：Edelsbrunner[11]提出了-shape算法，以球界定Delaunay三角化后的凸包，删除包围球半径大于的四面体，但该算法很难事先估计合适的半径；Chaine[12]提出的SHRINK算法构造一个伪表面，该伪表面从空间三维点集的Delaunay三角化闭包开始收缩，可以得到很好的闭合曲面，但在非闭合曲面时效果不理想，而且该算法需要输入合适的孔洞系数，很难进行事先估计；陈定造等[13]提出的三维Delaunay三角剖分快速点定位算法，对Escobar[14]的点定位算法进行了优化，提高了运行效率，但该算法还是需要法向一致化调整及相应计算。

标准的三维Delaunay剖分只是在当对象为简单凸体时比较完善，而对经常遇到的复杂受限的数据场剖分还存在一些问题，例如点集中存在五点共球的情况，其剖分结果是不唯一的[15]。此外，逐点插入的三角化方法虽然简单易实现、对内存消耗较少，但对大数据量处理速度很慢。在面向大量多维数据时，影响Delaunay逐点插入算法速度的主要因素是包含插入点四面体单元的查找和生成四面体的优化处理。因此，本文针对标准的三维Delaunay三角化算法的缺陷，研究利用模糊聚类分析首先将原始数据进行分类得到需要的数据集，进而采用一种改进的三维Delaunay三角化快速算法构建表面，并对构建的三维曲面进行渲染着色，应用于海水温度场大量数据的快速三维可视化。

1 改进模糊C均值聚类

等温数据集的划分实质上就是一个聚类的过程，而聚类[16]是一种无监督的学习过程，近年来已广泛应用到数据的组织与分类、数据压缩以及模型构造等多领域。C均值算法是一种硬分类的方法，但通常类与类之间的界限是模糊的，因而产生了模糊C均值聚类[17]（FCM），FCM用值在(0,1)之间的隶属度来确定每个给定数据点属于各个组的程度，但由于引入了归一化条件，使其在样本集不理想的情况下，可能导致结果不好，而改进模糊C均值聚类具有更好的鲁棒性，可以在野值存在的情况下，得到较好的聚类结果。

设为个样本组成的样本集合，为预定的类别数目，为每个聚类的中心，是第个样本对于第类的隶属度函数，是设定控制聚类结果模糊程度的参数（），为一个预定的距离最小值，则改进模糊C均值算法为：

                                        （1）

                                     （2）

                           （3）

对于远离各类中心的样本（野值），采用FCM将会使其对各类都有较大的隶属度，从而影响迭代的最终结果，而且该算法很容易陷入局部最优。为了克服这个缺点，改进模糊C均值聚类对归一化条件进行修改，使所有样本对各类的隶属度总和为，如式（1）所示，隶属度函数的计算也相应地进行了修正，如式（3）所示。利用该算法对海洋环境信息数据进行预处理可以得到需要的分类数据集。

2 三维Delaunay三角化改进算法

三维Delaunay三角化（又称为Delaunay四面体化）[18,19]采用“空球规则”使每个划分成的四面体各顶点的外接球内不含有点集中的任一点，这样各场值点对整个场分布的影响具有局部化、均匀化的特点。其三角化方法可分为逐点插入法、三角网生长算法和分治算法等，其中逐点插入法是比较适合空间三维数据场三角化的稳定性算法。但标准的Delaunay三维剖分对于点集中有五点共球的情况剖分结果不唯一，而且影响逐点插入算法速度主要有两个因素：一是包含插入点四面体单元的查找；二是新生成四面体的优化处理。因此，这里针对标准算法存在的缺陷进行改进，进而提高算法的性能。

对于包含插入点四面体单元的查找，主要是通过路径算法 [4]对待插入点在当前网格中的位置进行定位，该算法首先要选择一个起始单元，起始单元的位置将决定搜索路径的长度，而这一长度决定了查找速度。显然，选择合适的起始单元，尽快在三维空间中找到待插入点的位置可以提高算法的效率。对于通过模糊聚类得到的分类数据集，先在空间中建立可以包含所有待插入点的背景网格，然后根据点集中每个点的坐标，将其存储到相应的背景网格中，建立点与点之间的相对位置关系，从而在线性时间内可以查找到每个点附近的其他待插入点。为了便于表达，以二维为例，如图1所示。当插入点时，通过背景网格找出点附近的其他待插入点，按由近及远的顺序查找，直到发现已经插入网格内的点为止。以与这一点相连的单元作为起始单元，应用路径算法则可以缩短查找路径长度，进而提高算法的速度。对于新生成四面体的优化处理，我们采用如下方法：设为前个点形成的Delaunay三角化子集，对于的一个边界面，取点为以为边界面的四面体内部的一点，如果第个点与点位于该边界面的异侧，且满足第个点位于前个点组成的凸多边形之外，则将第个点与该边界面形成一个新的四面体，这样便将第个点加入到前个点集中。如果在第个点加入到前个点形成的四面体子集过程中存在五点共球的情况，则局部改变有共同边界面的两个四面体顶点的拓扑连接关系，进而消除五点共球的情形，这样就完成了前个点的三角化组合。依此类推，便可完成点集中所有点的三维Delaunay三角化。

图1 分类数据集的背景网格图 

3 海水温度场三维可视化算法

本文提出的温度场三维可视化算法总体思路主要分为以下三步：（1）利用改进模糊C均值聚类对原始数据进行预处理得到等温数据集；（2）采用三维Delaunay改进算法快速构建三维等温曲面；（3）采取颜色法对三维等温曲面进行着色可视化显示。

详细算法步骤如下：

Step 1 利用改进模糊C均值对数据进行聚类提取等温面数据。

（1）确定隶属度范围和分类的个数范围以及划分准则；

（2）遍历所有原始数据确定满足划分准则的隶属度和等温面个数，进而得到等温数据集。

Step 2 采用三维Delaunay快速算法得到需要的等温曲面。

（1）对于某等温面的离散三维点集，定义一个包含所有节点的凸壳；

（2）向凸壳中引入一节点，按照我们第2节中给出的对于包含插入点四面体单元的快速查找算法，选择合适的起始单元，根据“空球规则”删除不符合规则的四面体单元；

（3）将该节点与表面的三角形构成新单元，按照第2节中给出的方法对生成的四面体进行优化处理；

（4）对于下一节点重复（2）和（3）直至所有节点插入完毕；

（5）对于下一个等温面的数据重复（1）至（4）直至遍历完所有的等温面数据集。

Step 3 添加三角形定点颜色绘制等温面。

（1）建立海水温度值与颜色的对应关系，以色相代表等温面的值，用亮度代表等温面的浮动变化；

（2）采用OpenGL绘制等温面进行三维可视化展示。

4 仿真测试与分析

为了验证算法的性能，我们采用多组试验进行仿真比较与分析。试验条件为：Intel Core 2 Duo CPU P8700 2.53GHz，内存为1.93GB，显卡为ATI Radeon HD 3450 128MB，Microsoft Windows XP Professional操作系统的PC机。

首先对某局部海域四月份的温度数据进行测试，为了便于比较和说明问题，这里采用经典的散乱体数据可视化方法和我们提出的方法分别进行仿真测试，考虑到前者不宜处理大量数据，这里取数据量为400，高度为50m以内，范围m2，模糊聚类的分类数的值取为5，控制聚类结果模糊程度的参数b的值取1.5，每个类中的点数大于50。我们提取出两种方法生成同一等温面的仿真结果进行比较和分析，如图2所示。从图中可以看出两种方法生成的等温曲面轮廓比较相似，经典的散乱体数据可视化方法出现了空洞问题，而本文的方法不仅避免了空洞现象，而且计算速度要快近一倍。

为了测试我们提出的方法处理大量数据的能力，这里分别采用经典的三维Delaunay三角化方法和本文提出的方法依次对上万和上百万数据进行仿真测试，两种方法主要步骤的计算量对比分析如表1所示。这里重点考察点定位和优化处理的计算量，从表中我们可以清楚的看到：经典方法计算量主要集中在这两步，而且随着节点数目的增多，点定位计算量比重增大；而本文方法这两步的计算量总和几乎仅占整个计算量的一半，其中点定位算法所占的计算量比重很小，而且随着节点数目的增多，其比重也没有明显增加，这是由于按照空间距离由近及远的顺序查找的缘故。

为了进一步测试本文提出的方法处理大规模数据的性能，对某海域三月份和五月份的海水温度大量数据集分别进行温度场三维可视化仿真测试，试验结果如图3所示，本文方法单元生成的平均速度可达到12.9万单元每秒。图中从红色到蓝色依次表示海水温度由高到低，从图中我们可以很清楚直观地了解和掌握整个海域内温度随季节变化的详细情况。

经典的散乱体数据可视化方法生成的等温面                   本文提出的方法生成的等温面

图2两种方法生成的等温面可视化效果比较 

表1 两种方法计算量对比分析表

5 结束语

本文对海水温度场大量数据的可视化问题进行了研究，提出了采用改进模糊C均值聚类对海水温度原始数据进行预处理得到等温数据集，并提出一种改进的三维Delaunay算法快速构建三维等温曲面，最后采取颜色法对三维曲面进行可视化，通过对某海域海水温度数据的多组仿真测试证明了我们提出方法的性能。采用该方法对海水温度进行三维可视化使我们能够清楚直观地了解海水温度的变化情况，在军用和民用很多领域都具有广泛的应用前景，该方法同样可以推广到海水盐度场的三维可视化。需要说明的是，本文主要是研究大量数据的快速可视化问题，直接对原始数据提取等温面一定程度上会影响精度，但我们是对大量数据进行处理为前提，保证了足够的数据密度。下一步将在此基础上进一步研究海水潮流和海流等矢量场的快速三维可视化问题。

三月份温度场三维可视化结果                     五月份温度场三维可视化结果

图3 某海域不同月份温度场三维可视化仿真结果

参考文献

[1]涂超. 海洋温度场的三维可视化[J]. 武汉大学学报，2007,40(6)：126-128.

[2]李建璞. 温度场的快速计算[D]. 上海：上海师范大学，2010.

[3]杨冠杰，耿震，孙菁. 散乱体数据可视化：海洋水团分析的新途径[J]. 海洋通报，2000,19(2)：66-71. 

[4]William E Lorensen, Harvey E Cline. Marching Cubes: A High Resolution 3D Surface Construction Algorithm[J]. Computer Graphics, 1987,21(4): 163-169.

[5]Liu, J.，B. Chen, and Y. Chen. Boundary Recovery after 3D Delaunay Tetrahedralization without Adding Extra Nodes[J].International Journal for Numerical Methods in Engineering, 2007,72:744-756.

[6]Si, H.. Constrained Delaunay Tetrahedral Mesh Generation and Refinement [J]. Finite Elements in Analysis and Design, 2010,46:33-46.

[7]李水乡，陈斌，赵亮等. 快速Delaunay逐点插入网格生成算法[J].北京大学学报,2007,43(3): 302-306.

[8]宋超，关振群，顾元宪. 三维约束Delaunay三角化的边界恢复和薄元消除方法[J].计算力学学报，2004,21: 169-176.

[9]Bowyer A．Computing Dirichlet tessellations[J]．The Computer Journal，1981,24(2): 162-166．

[10]Watson D F．Computing the N-dimensional Delaunay Tessellation with Application to Voronoi Polytopes[J]．The Computer Journal，1981，24(2):167-172．

[11]Edelsbrunner H, Mucke E P. Three-dimensional Alpha Shapes[J]. ACM Transaction on Graphics, 1994,13(1):43-72．

[12]Chaine R. A Geometric Convection Approach of 3-D Reconstruction[C]//Eurographics Symposium on Geometry Processing. [s.1.]: [s.n.], 2003.

[13]陈定造，林奕新，刘东峰. 三维Delaunay三角剖分快速点定位算法研究[J]. 计算机工程与科学，2009,31( 5):79-80.

[14]Escobar J M, Montenegro R. Several Aspects of Three-Dimensional Delaunay Triangulation[J]. Advances in Engineering Software, 1996,27(1-2):27-39.

[15]李强. 三维Delaunay剖分在3D GIS中的应用[J]. 三晋测绘，2002,3(1): 14-16.

[16]高新波，谢维信. 模糊聚类理论发展及应用的研究进展[J]. 科学通报，1999,44(21)：2241-2251.

[17]汤兵勇，路林吉. 模糊控制理论与应用技术[M]. 清华大学出版社，2002.9.

[18]黄运保，王启付，武剑洁等. 基于局部三维Delaunay的插值网格边界增量构造算法[J]. 工程图学学报，2004,3,46-51.

[19]刘少华，吴东胜，罗小龙等. Delaunay三角网中目标快速定位算法研究[J]. 测绘科学，2007,32(2):69-71.