摘 要

本文综合以往学者提出的所有三维重构思想，自行设计并实现了一套完整的三维重构算法。该算法基于自底向上的决策构建法，通过逐步构建三维点，三维边和三维面来重建三维模型，并给出每一步的详细描述。实现的程序允许三视图出现直线和椭圆线，具有较高的时间效率，且支持保存/加载已有的项目文件来免除重新生成的时间，提供基本的绘图功能来方便用户输入，并使用OpenGL来将生成结果展现给用户。

关键词：三维重构；三视图；OpenGL

Abstract

This paper integrated all the algorithm that people have ever done.Since most articles do not write down the details about what the algorithm is exactly going on, I come up with a detailed algorithm to solve the problem of 3D reconstruction. This algorithm is based on the down-to-up method which complete the mission through reconstructing 3d points, 3d sides and 3d faces. Meanwhile this paper gives the elaborate explanation about how the whole algorithm works. The program in this paper can deal with the inputs including any lines and arcs and it has a high efficiency of time. Also it supports saving and loading the existed project files to restore the inputs and outputs. It still has a simple inbuilt drawing tool to make it more convenient to give inputs and uses OpenGL to render the results to the users.

Key Words：3D reconstruction;three views;OpenGL

目录

第一章 绪论 1

1.1 问题背景 1

1.2 本文的工作 1

1.3 开发环境 2

第二章 准备工作 3

2.1 重要的几何定理 3

2.2 数学符号表示 5

2.3 坐标系规范 5

2.4 数据结构 7

2.4.1 二维顶点 7

2.4.2 二维边 7

2.4.3 三维顶点 7

2.4.4 三维边 7

2.4.5 面环 8

2.4.6 面 8

第三章 重构算法详述 9

3.1 输入数据 9

3.1.1 图元表示方法 9

3.1.2 数据分类 9

3.1.3 数据输入方式 10

3.1.4 输入数据处理 13

3.2 数据检查 19

3.3 重构三维顶点 20

3.4 重构三维边 22

3.5 重构三维面 26

3.5.1 三维面的生成 26

3.6 构建三维模型 30

第四章 结果展示与性能分析 32

4.1 算法复杂度分析 32

4.1.1数据预处理阶段 32

4.1.2 三维点重构阶段 32

4.1.3 三维边重构阶段 32

4.1.4 三维面重构阶段 32

4.1.5 三维模型生成阶段 32

4.2 结果展示 33

4.3 性能测试 34

4.3.1 测试平台 34

4.3.2 测试结果 34

第五章 结论 36

参考文献 37

致谢 38

附录A 程序源代码 38

附录B 编译配置 38

附录C 引用的第三方库 39

附C1 OpenGL 39

附C2 glm 39

第一章 绪论

1.1 问题背景

如何由三视图重构三维模型一直是三维重构的一个焦点问题，解决这一问题的算法最早可至上世纪70年代【10】，该文章作者首次提出了重建三维模型的基本步骤，后来的算法基本都是基于这一基本思想的发展。之后，重建三维模型的算法主要可以分为2类，一类是通过重建候选体，然后进行决策筛选来构建三维模型的自底向上方法，一类是通过进行基元匹配来找出最终的三维模型的自顶向下方法。

  而我国学术界对于这一问题跟进较晚，在上世纪80年代，辜凯宁【4】等人进一步扩展了算法的输入空间，允许高次曲线的平面图输入，同时能够找到所有符合条件的解，并引入面域基，体域基的概念，提高了算法的时间效率。之后，Shin B.S.和Shin Y.G.进一步改进了之前的自底向上方法【9】，使得其时间效率大幅提高（约600%），MH Kuo则重点解决了二义性问题，使用决策链找出所有符合输入的解。

然而，所有这些文章都仅仅描述了整个重建过程的某1个或2个步骤，且没有给出规范化的算法描述和算法过程，同样也没有关于所用数据结构的任何说明。另外，也没有任何一篇文章完整地描述了3维重构的整个算法流程和具体细节。

1.2 本文的工作

本文在参考以上文章的思想后，自行研发并设计了一套完整的算法，定义了一系列的数据结构来完成简单的三维重构工作。该算法使用自底向上的决策方法，通过逐步恢复三维点，三维边，三维面来重构三维模型，并使用OpenGL 4.5来完成最终的渲染工作。该程序支持保存/加载已有的项目文件，也提供了一套简单的绘图工具来供用户进行输入。

接下来，本文将详细介绍整个算法中用到的数据结构以及算法的详细流程。算法的大致流程可参照下图：

图1.1 算法流程图

1.3 开发环境

本程序使用Visual Studio 2017专业版进行开发，编程语言为C/C ，最终代码量约12000行，核心算法约5000行。程序为基于基本对话框的Windows MFC应用程序，提供64位Debug和Release版本。经测试，在Windows7和Windows 10 1809上均能正常运行。

第二章 准备工作

2.1 重要的几何定理

定义1.1 二维顶点：一个二维顶点由2个相互独立的坐标值确定，可以表示为一个二元有序对(x,y)，表示某一个视图中的一个顶点。

定义1.2 二维边：一个二维边由2个二维顶点组成，代表平面上一条以这2点为端点的线段。

定义1.3 三维顶点：一个三维顶点由3个相互独立的坐标值确定，可以表示为一个三元有序对(x,y,z)，用于表示一个三维模型的一个顶点。