在计算机图形学和几何造型中,为了获得对三维世界的描述,实现曲面的重构是非常重要的.曲面的重构也即得到待构曲面上的散乱点群,对这些散乱点群进行曲面重构得到待构曲面的几何模型.三维散乱数据的曲面重构方法分为整体的逼近和局部逼近及其它的如变形逼近等.这种构建复杂的几何模型,在工程以及地质中有广泛的应用前景,是各国研究热门领域.构建复杂的几何模型,物体表面常用多边形网格模型,尤其是三角形网格模型描述三维实体.局部逼近是构建复杂曲面造型的主要造型手段,这样构建的复杂曲面造型没有冗余信息,从而由局部逼近得到的复杂曲面造型的形状良好.该论文的主要工作对三维曲面重构的局部逼近进行研究,主要工作内容如下:1)概述了国内外对曲面重构算法的研究状况,并简要介绍了作者所做的一些工作.2)根据曲面测量数据量庞大,密集,无序的特点,提出了基于八叉树扩展的局部B-样条曲面逼近曲面重建算法.在处理大量的散乱点时,结合八叉树的特点,建立了八叉树的空间分割、编码和解码算法等等,大大减少了曲面-重构过程中查询数据搜索时间.在分析了曲面数据时,特别结合面向对象的思想,建立了恰当的数据结构来表示数据及要维护的拓扑关系.并获得了良好的曲面形态.3)分析研究了散乱点的空间三角剖分的算法.对三维散乱数据点直接进行三角剖分的算法基础上加以改进,提出了基于空间八叉树与直接三角剖分算法的结合.在处理大量的散乱点时,分析八叉树的特点,建立了八叉树的空间分割、编码和解码算法等等,大大减少了在构建三角网过程中查询数据搜索时间.实现大规模散乱数据在空间上的三角剖分算法,并获得了较好的效果,为后续进一步进行曲面重构打下基础,最终实现曲面模形的表达奠定了基石.4)平面点集作为一种常见数学模型,其上常做的运算是求其凸包和三角网格.基于平面区域内的三角剖分也就是直接将在平面域上的点进行三角剖分,并根据这些点的高度值映射到空间得到三维空间的拓扑,目前对凸包与三角形网格二者的研究是独立进行的,鉴于在很多情形下这两种处理结果均需要,因此该文提出了一种综合算法:在对离散点集进行三角剖分的过程中,增加对三角形边界的判别、管理功能,记录其中作为点集凸包边界的线段,使得在实现剖分的同时产生出点集的凸包.该算法采用逐层求凸包,然后逐层分割环域成三角形序列,三角网格的优化是在三角网格生成过程中完成的,从而提高了算法效率.且当该算法实现单一的点集剖分或凸包功能或是用于多边形的凸包与剖分时效果也很好.