三维形状的匹配，在逆向工程、虚拟现实、医学图像配准、机器人、自动控制、以及药物分子结构设计等领域有着广泛应用，是计算机图形学中的重要研究课题。三维形状匹配的关键是曲面的匹配，其基本问题是定义和计算两个曲面(通常是三维几何体的表面)的差异。这一差异完全由曲面的内蕴性质决定，与其它因素无关。例如，将一个曲面与其经过刚体运动(平移和旋转)后的像相比较，其差异应该为零。曲面匹配可分为刚性曲面(无形变)匹配和弹性曲面(有形变)匹配两大类。二者的区别在于：刚性曲面匹配仅仅将一个曲面与其在刚体运动作用下的像视为相同；弹性曲面匹配则将曲面在一个包括刚体运动在内的更大的运动群作用下的像视为相同。刚性匹配是弹性匹配的特例；研究刚性匹配的有效算法，是实现更一般的弹性曲面匹配的基础。曲面匹配的算法在很大程度上依赖于曲面表示的方法。在计算机图形学中，最为常用的离散曲面表示，有点云和三角网格两种。三维激光扫描仪获取的原始测量数据就是点云，它具有结构简单、处理手段灵活多样等优点。本文的主要工作，是针对基于点云的刚性曲面匹配问题，提出了一种通用的匹配算法。该算法不需要在被测物体上附加任何参考点或标签点，对待匹配点云的相对位置没有要求，可以处在空间任意位置上，仅利用曲率估计创建八叉树，再结合SEPMap实现点云的部分匹配和整体匹配。本算法不需要提取特征点，因而也不依赖于曲率的极值。本文具体结构如下：第一章综述国内外有关曲面匹配的工作，主要是有关特征的研究；第二章介绍有关点云的基本概念，包括常用的处理方法；第三章是关于八叉树的简要介绍，这是本文下面提出的新算法中使用的重要工具；第四章提出了新的曲面匹配八叉树算法，并从实验和理论上分析了算法的可行性；在本文的结论中对我们的研究进行了总结和展望。