本论文主要提出了一种改进的快速三维凸包构造新算法。在过去几十年凸包算法的研究取得了一系列的进步,如二维的Graham扫描算法,Javis卷包裹(wrapping)算法等等,基于排序的算法平均时间复杂度都是O(nlogn)。而在三维凸包算法领域里,则有经典的Clarkson和Shor算法,以及Quick Hull算法。本质上讲,这两个算法都基于随机增量算法,通过动态地添加外部点来逐步构造出完整的凸包,优点是易于理解操作,并且时间复杂度仍然是凸包构造的下限O(nlogn)。而根据大量的统计数据表明,对于任意一个充分大的点集而言,绝大部分点不是最终凸包的顶点。所以,本文在详细研究了这两个算法的随机性基础上,进一步引入了非随机的性质,加速了Quick Hull算法。全文主要内容为:1)提出了一种新的三维凸包的构造算法,这种改进的快速算法参考了QuickHull算法里面每轮迭代选取外部集合中的极值点来作为候选点,更新成新的凸包的思想,并在这个基础上改进为选用二次极值点来构造新凸包的方法,同时综合使用了一个二部图数据结构“冲突图”来记录外部点与当前的凸包的可见性关系,最终达到了排除内部点,迅速缩小构建的规模,实现了高效地构建凸包,本文的实验也说明了两者相比,新算法比QuickHull算法效率更高。2)采用Visual C++和OpenGL语言为工具,设计了一个完整的实验平台,包括STLViewer.exe主程序和五个动态链接库。从数据生成,采集,加工,算法实现,到最后的结果显示,整个平台都是完全按照标准的CAD软件设计模式开发,使得这个平台具有了一定的实用性和可操作性。3)完成了实验数据的加工,比较,改进算法相对于QuickHull算法在效率上平均提升了20%。