---
title: "视频课程——点云到网格的重建"
author: "Perrin Yong"
author_profile: https://www.pystone.net/profile/
published_by: "Perrin Yong"
canonical: https://www.pystone.net/notes/pointcloud-to-mesh-reconstruction-course/
type: note
content_role: unspecified
visibility: public
id_stability: rename-stable
source_path: "10-计算机、信息技术与工程/08-图形学与三维重构/视频课程——点云到网格的重建.md"
content_hash: 2889749a8ad13268dbfd0d08c4ee764e6cbcdeed952b08854de6233f1f3ce6e8
knowledge_version: 224c990773de.5fa8af6e39fa
site_commit: 224c990773de166d23a886306577dd90379529ce
notes_commit: 5fa8af6e39fa3891d1b9b4832bfa6c4e0ecaaf0a
---
# 视频课程——点云到网格的重建

> 创建时间：2020/5/5 21:44

## 三维模型的表述方式

### 边界表述法 Boundary Representation, B-reps

  * 将三维物体描述成一组表面，该表面将物体的内部和外部分离开

  * 有较多的关于面、边、点及其相互关系的信息，便于对模型进行几何运算和操作

  * 可以精确地表示简单规则的物体，例如多面体和椭球

  * 可分为基于多面体的表述法和基于曲面的表述法

#### 多面体表述法

将物体表面表述成一组封闭物体空间的多边形（最常用三角形、四边形 ）

##### 三角网格（绝大部分）

三角形表示物体的表面也叫 **三角剖分**

>   * 稳定性强
>
>   * 能表示各种形状的的三维模型
>
>   * 有助于恢复模型的表面细节
>
>   * 要求点云稠密且分布均匀
>
>

基本结构：顶点（Vertex） 面片（Facet） 边（Edge）

属性：颜色（Color）法向量（Normal）纹理坐标（Texture Coordinate)

**流形(Manifold Mesh)** 与 **非流形(Non-manifold Mesh)**

> 流形的定义：
>  1）一条边只能由一个或两个面片共享
>  2）一个网格顶点的一环邻域三角片构成一个闭合或者开放大扇面
>  三角网格曲面中大多数算法是基于流形网格的

**常用数据结构：共享顶点(Shared Vertex)**

  1. 顶点的坐标数组

  2. 三角形面的数组
**缺点** 可以表示点之间的连接关系(Connectivity)，但是没有局部之间的邻接关系 (Neighborhood),例如从一个顶点到与其相邻的面片，因此在很多局部操作上速度 和效率低

**半边数据结构 (Half-Edge Data Structure)**
一边为中心的数据结构
存储三维模型所有顶点、边和面的数据以及相邻接关系的信息
利用半边表示边的方向

![Alt text](/media/4cf2d2dbe5bb8203f2ae.png)

  * 局部操作速度快

  * 只能处理流形(Manifold)模型

    1. 顶点(Vertex)
以此顶点为源点的半边 （随机选取一条）

    2. 半边(HalfEdge) : 有方向（Oriented）的边
目的顶点（Target Vertex）
半边左侧面
前一个（Prev）半边
下一个（Next）半边
孪生（Twin）半边

    3. 边(Edge) ：Non-Oriented = 两个方向相反的半边
任意一条半边

    4. 面(Face)
一条和此面相邻的半边(Adjacent HalfEdge)

    5. 模型(Mesh)：顶点列表，边列表，半边列表，面列表

![Alt text](/media/d7c9803b83da70bb8b7f.png)

> 找顶点的邻域顶点
>  a）确定给顶点
>  b）通过该点可以直接得到此点的 一个相邻的半边
>  c）通过该半边便可以确定一个相邻 的顶点,以及此半边下一个相邻的半边
>  d）重复上述过程可以得到所有的相邻顶

#### 曲面表述法

一组曲面

##### 参数曲面表述法 Parametric Surface

z = f(x, y) 球、椭球、圆环
二次曲面，多项式曲面，样条曲面

##### 隐式曲面表述法 Implicit Surface

{x, y, z| f(x, y, z) = 0}

### 空间划分法 Space-partitioning Representation

将物体内部的空间划分为细小、不重叠的连续实体来描述物体的形状，常用方法有：构造体素法，八叉树法和二分空间法

#### 构造体素法 Constructive Solid Geometry

通过对一些基本元素(如四面体、圆柱体、 圆锥、球体或者带有样条曲面的刚体)进行加、减、并集和交集等组合运算生成新的物体。

  * 操作简单，便于实现

  * 只能用来表述结构较为简单的实体，无法用于形状复杂或者表面细节丰富的物体

  * 由于信息简单，这种数据结构无法存贮物体最终的详细信息，例如边界、顶点的信息

#### 八叉树 Octree

利用分层的树结构将要表述的物体 建造一个树结构，树节点对用空间 中一块特定的区域(根节点是包含整个物体的正方体边界区域)。
从根节点开始，包含物体的节点 将被均匀地划分成八个字节点。 这种迭代进行直到满足终止条件 为止

![Alt text](/media/69f40b5cd8ed4bd6774e.png)

设定划分条件：树深度

#### 二分空间法 Binary Space-partitioning

与八叉树结构表述法类似，都是对空间进行逐步划分。不同之处在于二分空间法每一步都将空间划分成两部分，且划分平面的位置和方向根据物体的空间分布随时调整，因此增加了表述的灵活性。

## Delaunay Triangulation 德劳内三角剖分

  * 空圆特性: 任意3个点的外接圆不包含第4个点（空的）。 Delaunay三角剖分中，所有三角形都满足空圆特性。
点集P的Delaunay三角剖分满足任意P内任意一个点都不在P内任意一个三角面片的外接圆内。

  * 要求最大化三角面片内三角形的最小角。

**劳森翻转算法（Lawson Flip Algorithm）**

![Alt text](/media/da56efe2b3cca7518937.png)

原理: 四个点进行三角剖分，如果不满足空圆特性，那么进行翻转后一定满足空圆特性。
满足空圆特性的，三角形最小角一定比不满足的要大。
每次翻转，都是最大化最小角。

### 一种增量的德劳内三角剖分算法

Step1:
添加两个足够远的点𝑝−1, 𝑝−2 以保证𝑝−1, 𝑝−2 位于所有三角形 的外接圆外。三角形𝑝0𝑝−1𝑝−2 包含所有的点。初始的时候仅有一 个空的三角形。
Step2:
依次添加新的点𝑝𝑟,检测相关三角形的空圆特性
情况1：𝑝𝑟位于三角形𝑝𝑖𝑝𝑗 𝑝𝑘内部
情况2:𝑝𝑟位于一条边上
第一种情况： 分别连接 𝑝𝑟𝑝𝑖,𝑝𝑟𝑝𝑗, 𝑝𝑟𝑝𝑘, 分别检查与三 角形𝑝𝑟𝑝𝑖𝑝𝑘, 𝑝𝑟𝑝𝑗𝑝𝑘, 𝑝𝑟𝑝𝑖𝑝𝑘相 邻的三角形的空圆特性
第二种情况： 分别连接 𝑝𝑟𝑝𝑙,𝑝𝑟𝑝𝑘, 分别检查与三角形 𝑝𝑟𝑝𝑗𝑝𝑘, 𝑝𝑟𝑝𝑗𝑝𝑙, 𝑝𝑟𝑝𝑙𝑝𝑖, 𝑝𝑟𝑝𝑘𝑝𝑖 相邻的三角形的空圆特性

### 三维上的Dela.三角剖分（四面体剖分）

3D上D四面体剖分+MRF优化 -> 三维网格

缺点：

  1. 得到的网格存在冗余

  2. 没法处理空洞的情况，没有自动补洞的功能

  3. 没有用到法向量，只用到顶点的属性信息，容易受到噪声影响。

优点：算法简单，速度快
适用于:

  1. 规模比较小，噪声比较少

## 基于隐函数的三维模型重建

### 空间划分

#### 均匀（Grid）——存在浪费

#### 非均匀（Octree非均匀划分）

有点的立方体才进行继续划分，没有的就不继续划分

##### 深度确定：

深度越高，分辨率越高
泊松重建——深度设成10-11
确定方法 : 根据点的尺度->Octree Node的宽度->深度
尺度：定义为顶点到最近邻的平均距离，它反映点的分辨率

![Alt text](/media/273f060884c6b5e982fc.png)

### 符号距离场的构建 ？？ 有待研究

#### 符号距离函数（SDF，Signed Distance Function）

在空间中的一个有限区域上确定一个点到区域边界的距离并同时对距离的符号进行定义：点在区域边界内部为正，外部为负，位于边界上时为0。

用一个截断符号距离，范围外的点不去考虑

  * 对于grid，计算每个node的符号距离

  * 对于octree，计算每个叶子节点的符号距离值

#### 全局的方法

节点处的符号距离值，是对空间距离值的一个采样
每个节点上建立一个基函数，得到隐函数的明确表达形式
求系数，用符号距离值拟合函数
**优点** :比较鲁棒，比较稳定，能处理存在空洞的情况
**缺点** :存在过平滑的情况，会损失一些细节，计算量比较大
泊松重建——全局的特性+局部的方法

#### 局部的方法

**优点** ：计算起来比较灵活，只需要考虑局部的信息，能比较好的保持一些细节。
**缺点** ：容易受到一些噪声的影响。
法向量和向量之间的夹角
去领域，对领域内的点进行加权

#### 构建符号距离场

全部
局部

### Marching Cube生成表面

符号距离场 -> 三角网格

#### 针对Grid划分的方法

根据体素的8个顶点的符号距离值，通过插值的方法生成面片。
插值，得到符号距离值为0的点
二维：一共16种情况
三维：一共256种情况

#### 对于Octree

相邻体素分辨率不同，导致出现空洞

### 常见方法：

全局：
泊松表面重建算法（06年提出，现在版本多）：
原理简单（用隐函数去拟合符号距离函数），中间推导非常麻烦，代码难看懂
Ssd重建算法：
局部：
Fssr重建算法