题目：基于四面体体元的非结构数据场等值面抽取方法研究与实现

矢量场可视化是科学计算可视化的重要研究内容，在科学计算和工程分析中有着非常重要的作用。矢量场可视化已被广泛应用于地质勘探、航空航天、军事仿真、医学、气象科学等领域，具有重要理论研究价值的实际应用背景。本文以国家863课题“非结构化非稳定矢量场可视化方法研究”为背景，重点研究了非结构化数据场可视化中的等值面抽取问题，完成的工作主要包括：1）给出了一种基于四面体体元的非结构化等值面构造算法，该算法具有以下特点：利用Delaunay三角化进行非结构化数据场的预处理，将输入的非结构化数据点集转化为四面体体元的集合；采用非线性插值（与距离成反比的加权法）计算等值点，保证了计算结果的精度；采用曲面重建方法构造等值面（使用Hermite双三次曲面逼近等值面），提高了结果图像的光滑度。2）对红黑树加以扩展，并就扩展红黑树的插入、删除、旋转等基本操作给出了一套修改方法，以保证操作后仍具备红黑树的性质；基于该扩展红黑树的结构给出了一种等值面提取的加速算法，该算法的特点主要包括：扩展红黑树每个结点的关键字域为一个区间；以比较区间左值大小的方式定义了两个区间的“大小”关系；增加两个字段域，用以判断是否继续遍历左子树或者右子树；该算法的时间复杂度为O(min(klgn,n)) 。3）参与设计并实现了三维矢量场可视化软件BHVS系统。实验结果表明：采用本文基于四面体体元的非结构化等值面抽取算法能够获得比经典的MT算法更为精确的等值面图像；采用本文基于扩展红黑树的等值面抽取加速算法可以有效减少运行时间。