基于凸包的物体三维表面轮廓模型的构建

摘要： 该文提出了一种以凸包为基础来表达物体表面近似轮廓模型的方法。通过对由各种方式所得的散乱点集进行预处理，然后进行凸包运算，求得物体表面轮廓极值点，再依据这些点进行物体表面的三维重建。该文以Visual C++ 6.0为开发平台，采用可视化类库VTK，对这一方法进行计算机仿真，取得了较为理想的效果。

关键词： 三维凸包；表面重构；VTK；可视化

中图分类号：TP311.1 文献标识码：A 文章编号：1009-3044（2013）03-0603-04

1 概述

随着计算机图像处理技术的发展，三维重构技术已经成为计算机辅助设计与计算机图形学中的一个重要研究领域。在诸多工程实践和现实生活中，人们往往需要能直观的看到一些物体表面的大概轮廓，本文提出的三维物体近似表面模型的构建方法是采用可视化软件系统，对以一定的方式获得的三维散乱点集（如点云数据，采集得到的离散数据等），首先根据数据处理要求进行预处理，而后进行求凸包运算获取物体表面极值点，最后利用这些点生成物体表面的多面体模型，进行各种后处理（如平滑等），并在计算机上显示、进行人机交互的过程。

VTK（Visualization ToolKit）是针对计算图形学，可视化和图象处理的一个源码开放，面向对象的软件系统。随着科学可视化这一技术被人们越来越多的应用于医学、产品设计、地球科学、流体力学等各个领域，VTK作为一个优秀的可视化工具包，为各级研究人员和机构提供了强大的支持。

2 VTK概述

VTK是Willliam Schroeder等人利用C++语言开发的集3D图形学、图象处理以及可视化于一体的软件系统。该软件系统由两个子系统构成，一个是通过编译生成的C++类库；另一个是用Tcl、JAVA和Python语言来使用编译过的C++类的解释器包。这种做法的优势在于即可以在编译过的语言C++类中创建效率比较高的算法，同时又能够使用解释型语言进行快速的应用程序开发。

VTK是一个面向对象的系统，由图形模型和可视化模型两种对象模型构成。

2.1 图形模型

图形模型通过几个主要的C++类有机的组合在一起生成一幅图象。

在VTK软件系统中，vtkProp或vtkProp3D的子类表示一幅图象中的可见物体；vtkLight类封装了有关图形光线处理的方法，包括光线开关状态、位置、颜色等；vtkCamera类封装了关于视点操作的方法，包括观察者的位置、焦点的调整等；vtkProperty与vtkProperty2D这两个类可以控制显示图形的属性；vtkAbstractMapper及其子类是可视化模型和图形模型的接口；利用vtkTransform类可以对图形中显示的物体进行平移、旋转、缩放等操作；vtkScalarsToColors及其子类可以将映射数据转变成不同的颜色来表达，是图象处理中的关键技术；vtkRender和vtkRenderWindow这两个类用来管理图形引擎与计算机窗口系统之间的接口；vtkRenderWindowInteractor类封装了窗口系统与数据之间交互相关的方法。

2.2 可视化模型

VTK采用数据流方法将输入的原始数据转变成图形数据，该方法涉及数据对象（vtkDataObject）和流程对象（vtkProcessObject）两个基本的对象类型。

在VTK软件系统中，数据对象用来表达各种类型的数据，它支持5种不同的数据类型，分别是：直线网格（vtkRectilinearGrid）、结构网格（vtkStructuredGrid）、非结构网格（vtkUnstructuredGrid）、多边形数据（vtkPolyData）及图象数据（vtkImageData）。流程对象通过对数据对象进行操作产生新的数据，体现了系统的运算法则。流程对象和数据对象通过可视化流水线相连，在数据流动过程中对数据进行操作。流程对象又可以细分为源对象（vtkSource）、过滤器对象（vtkFilter）及映射对象（vtkMapper）。源对象是整个可视化流程的起点，它既可以在程序内部通过一定的法则产生，也可以直接从文件中读取；过滤器对象接受数据对象的输入，产生一个或多个数据对象输出，由于运算法则的不同，过滤器对象输出的数据类型可能与输入的数据类型不同；映射对象接受源对象或者过滤器对象输入的数据并把数据映射成基本图元。

数据对象和流程对象的有机结合就产生了可视化流程，如图1所示：

3 三维凸包模型重建算法简介

凸包是数学和计算几何的重要内容之一，它是包含给定点集中所有点的最小凸域的边界。很多的工程实际问题最终都可以归结为凸包问题，比如Delaunay 三角剖分、 Voronoi 图、功率图、halfspace intersection等。这些结构在科学研究和工程实践中有着非常广泛的应用，如图象处理、碰撞检测、城市规划、文件检索、数值积分、冶金学、统计学等。

凸包的定义：在一个实数向量空间[V]中，对于给定集合[X]，所有包含[X]凸集的交集[S]被称为[X]的凸包。

[S=X?K?VK is convexK]

[X]的凸包可以用[X]内所有点[x1，…，xn]的线性组合来构造。

[S=j=1ntjxjxj∈X，j=1ntj=1，tj∈0，1]

计算三维凸包的算法有很多种成熟的算法，包括随机增量法，Graham扫描法，Jarvis步进法，分治法和快速算法（Quickhull算法）等。每种算法都有各自的特点，本文采用的是运算效率比较高的快速算法。它由随机增量算法改进得到，其时间复杂度与输出的凸包顶点数[k]有关，为[Οnlogk]。该算法的优点是无需存放额外结果，能够做并行处理，其空间复杂度与时间复杂度都比较低。图2为快速算法的伪代码：

说明：[p]在[F]的上方当且仅当[p]到[F]的有符号距离[d>0]；

明暗界限[H]是边[R]的集合，[R]满足它的两个邻接面一个可见，一个不可见（点在面的上方称为该面可见，反之则不可见）。

4 算法实现

本文以Visual C++6.0为平台，使用C++语言和可视化类库VTK对所得的三维散乱点集进行表面轮廓重建。三维凸包用组成凸包的三维顶点和二维平面来表示，凸包的顶点为输入点集的极值点，组成凸包的平面包括三个点集合，三个邻接面集合和一个平面方程。程序求取凸包通过类CHull_Alg来实现：