几何表示
1 几何表示的几种方法
如何在计算机内表示/存储一个三维的几何体? 比如下面的 Stanford Bunny.
在数学上, 我们可以用函数的水平集 (比如方程 \(F=0\) 的解集) 或者参数曲面来表达一个几何体. 然而现实中的几何体一般都复杂到难以写出具体的解析式. 因此, 我们只能利用一些近似手段, 将几何体 (或者其表面) 的近似形态存储在计算机里.
最直接的办法是用若干固定大小的小立方体, 像搭积木一样砌成几何体形状.
这被称为体素表示 (voxel representation) (下图最中间,
图源 Research Gate
另一种比较直接的方法是在几何体表面采样很多很多点, 称为点云 (point cloid), 用这些点拟合几何体的表面 (下图左).
为了表示几何体的表面, 还可以采用多边形网格 (polygon mesh), 即用若干多边形 (一般是三角形) 组成的一张 "网" 拟合几何体的表面 (下图右, 三角形网格).
受到隐函数曲面 (比如球面 \(x^2+y^2+z^2-r^2=0\)) 的启发, 我们可以用符号距离场 (signed distance field, SDF) 表示几何体的表面. 对于空间中的每一点 \(x\), SDF 给出了 \(x\) 到几何体表面的有符号距离 (几何体内部为负, 外部为正, 表面上为零; 当然内外也可以反过来). 下图是 bunny 的 SDF (图源课程 PPT).
上面四种表示方法中, 体素、点云、多边形网格称为显式表达, 符号距离场称为隐式表达. 它们对应了不同的应用场景, 并且可以相互转换.
Polygon mesh processing (Mario Botsch et al.) Section 1.6 中总结显式表达和隐式表达如下:
Parametric surfaces can capture even the finest detail, are easy to sample, and can be modified intuitively but it is difficult to answer distance queries and topological changes require a major restructuring. On the other hand, topological changes and distance queries are easy for implicit surfaces but sampling and shape editing is not straightforward and the geometric detail resolution depends on the voxel size.
我们目前只介绍一些最基本的表示方法. 一些先进的方法, 比如八叉树 (体素的升级版, 实现自适应分辨率), radiance field, 3D Gaussian 等将在之后特定 topic 中介绍.
1.1 三角形网格
严格地说, 一个多边形网格指的是 \(\R^3\) 中有限个多边形的集合 \({\cal K}\), 满足:
- \({\cal K}\) 中任意两个多边形或者不交 (交集为空), 或者有公共边/公共顶点.
多边形 \(P\in{\cal K}\) 也称为一个 "多边形面片 (polygon facet)". 三角形是最基本的多边形, 任意多边形网格 \({\cal K}\) 可以通过切割面片的方式化为一个三角形网格. 下面我们主要研究三角形网格.
三角形网格的表达能力很强, 任意二维拓扑流形都能表达为三角形网格 (当然也能表示一些非流形的几何体), 而且三角形网格能表达细致的几何信息, 也容易编辑. 三角形网格的另一个好处是经典微分几何中的曲面理论能直接推广到三角形网格.
1.1.1 Local averaging region
由于三角形网格是分片线性的, 在交界处不可微, 故顶点 \(v\) 处的微分量不能直接计算. 一种办法是计算微分量在 \(v\) 的一个邻域内的平均值. 这样的邻域称为局部平均区域 (local averaging region). 下图展示了几种不同的 local averaging regions: (图源 Polygon mesh processing, Figure 3.7)
- Barycentric cell: 顶点 \(v\) 周围一圈三角形的重心和边的中点连成的多边形.
- Voronoi cell: 顶点 \(v\) 周围一圈三角形的外心连成的多边形. (该区域内任意一点 \(p\) 到 \(v\) 的距离不大于 \(p\) 到其他顶点的距离).
- Mixed Voronoi cell: 和 Voronoi cell 差不多, 只不过如果外心在三角形外, 则用边的中点代替.
在近似精度上, mixed Voronoi cell 最佳, Voronoi cell 次之.
1.1.2 法向量
顶点 \(v\) 处的单位法向量定义为周围一圈三角形的法向量之平均值: \[ n(v) := \frac{ \sum_{T\in{\cal N}_1(v)}\alpha_T n(T) }{ \|\sum_{T\in{\cal N}_1(v)}\alpha_T n(T)\| }, \] 其中 \({\cal N}_1(v)\) 是以 \(v\) 为顶点的三角形的集合, \(\alpha_T\) 为三角形 \(T\) 的权重, 通常有如下几种选择:
- 常值 \(\alpha_T\equiv1\), 方便计算但并未考虑网格的几何.
- 面积 \(\alpha_T=|T|\), 比较方便, 但仍会导致一些反直觉结果.
- 顶角 \(\alpha_T=\theta_T\) (即 \(T\) 在 \(v\) 处的内角), 需要反三角函数, 计算量大, 但是效果很好.
对大多数应用场景, \(\alpha_T=\theta_T\) 都是不错的选择.
1.1.3 梯度
记三角形 \(T\) 的三个顶点为 \(v_i,v_j,v_k\), 分片线性函数 \(f\) (在每个三角形上是线性的) 在顶点处的值 \(f_i,f_j,f_k\), 则函数值在三角形内的值为 \[ f(x) = \frac{A_i(x)f_i + A_j(x)f_j + A_k(x)f_k}{A},\quad x\in T, \] 其中 \(A_i(x),A_j(x),A_k(x)\) 为三个小三角形的面积, \(A\) 为整个三角形的面积, 如下图.
- 实际上, \(x=(A_i/A)v_i+(A_j/A)v_j+(A_k/A)v_k\). 系数 \((A_i/A,A_j/A,A_k/A)\) 称为 \(x\) 的重心坐标 (barycentric coordinates).
三角形面积等于底边长乘以高, \[ \Align{ B_i(x) &= \frac{ \lr{(x-v_j),\frac{(v_k-v_j)^\perp}{\|v_k-v_j\|}} \|v_k-v_j\| }{2A} \\ &= \frac{ \lr{(x-v_j),(v_k-v_j)^\perp} }{2A}, } \] (其中 \((\cdot)^\perp\) 表示 \((\cdot)\) 逆时针旋转 \(\pi/2\) 得到的向量) 有 \(\nabla B_i(x) = \frac{(v_k-v_j)^\perp}{2A}\), 于是 \(f\) 的梯度为 \[ \nabla f(x) = \sum_{\sf cyc} f_i \nabla B_i(x) = \frac1{2A} \sum_{\sf cyc} f_i (v_k-v_j)^\perp. \] 可以发现 \(\nabla f\) 与 \(x\) 无关, 即在三角形 \(T\) 上是常数. 这是 \(f\) 的分片线性性的必然结果.
1.1.4 Laplace-Beltrami 算子
1.1.5 数据结构
最后说说怎么把三角形网格存储在计算机里.
面表: 需要一个顶点列表 \(\{(x_1,y_1,z_1),(x_2,y_2,z_2),\dots\}\)
和三角形列表 \(\{(i_1,j_1,k_1),(i_2,j_2,k_2),\dots\}\).
顶点列表记录每个顶点的坐标, 三角形列表记录每个三角形由哪些顶点组成
(顶点索引). 使用面表存储 mesh 的文件格式有 .obj,
.off 等.
半边: 将每条边拆成两条有向半边 (halfedge), 方向相反.
每条半边只属于一个面片, 并且我们要求每个面片中的三条半边首尾相接
(呈顺时针/逆时针方向)
下图中, 每个三角形的三条半边都呈现逆时针方向 (蓝色箭头). 我们规定三角形法向量的方向应当与蓝色箭头满足 "右手螺旋定则" (右手握拳并竖起大拇指, 四指的方向与蓝色箭头相同, 则拇指指向法向; 在下图中, 法向量指向屏幕外).
每条半边 (以下图橙色边为例) 存储了如下数据:
- 它指向的顶点, 下图 1.
- 它的另一半, 下图 2.
- 它相邻的面, 下图左边的三角形.
- 它在该三角形中的下一条边, 下图 3.
- 它在该三角形中的上一条边, 下图 4 (非必需, 因为可通过上述操作组合得到, 比如下下条边).
此外, 每个顶点还保存了它的坐标以及从它出发的某一条半边. 每个面保存了它的某一条半边.
从顶点 \(v\) 出发, 可以在常数时间内遍历其 \(1\)-邻域 (所有与 \(v\) 相邻的三角形) \({\cal N}_1(v)\):
- 获取从 \(v\) 出发的某条半边 \(e_1\). (半边 \(e_1\) 的相邻面便是 \({\cal N}_1(v)\) 的第一个元素.)
- 获取 \(e_1\) 的另一半 \(e_2\).
- 获取 \(e_2\) 的下一条边 \(e_3\). (半边 \(e_3\) 的相邻面便是 \({\cal N}_1(v)\) 的第二个元素.)
- 以此类推, 获取 \(e_4,e_5,\dots\), 直到回到 \(e_1\).
1.2 点云
点云是最容易表示与存储的, 只需列出每个点的坐标即可. 点云也是最容易获得的, 使用一个深度传感器获取深度图, 再根据相机参数将点的深度转化为点坐标即可. 一般会对物体的各个侧面分别构建点云, 然后将它们合并起来. 将几个小点云合成一个大点云的过程称为点云配准 (registration). 下图展示了将两个点云 (黑色和蓝色) 对齐的过程 (图源 Wikimedia).
1.2.1 ICP
ICP (iterative closest point) 是一种迭代的点云配准算法. 算法假设两个点云 \(P=\{p_i\}\) 和 \(Q=\{q_i\}\) 可以用刚体变换 (平移, 旋转, 反射) 对齐. 设刚体变换为 \(p\mapsto Rp+t\) (\(R\) 为正交阵). 算法迭代地优化 \(R,t\), 具体流程如下:
- 利用 PCA 初始化 \(R,t\).
- 将 \(p_i'=Rp_i+t\) 与离它最近的 \(q_i\) 匹配.
- 丢弃距离大于 \(k\) 倍中位距离的点对 (outliers).
- 构造误差函数 \(E=\sum_i\|Rp_i+t-q_i\|^2\) (点对距离的平方和).
- 利用 SVD 分解最小化 \(E\), 解出新的 \(R,t\).
重复以上 2-5 步, 直到误差 \(E\) 足够小, 便得到了我们想要的 \(R,t\).
ICP 的可视化见此网站.
1.2.2 法向量
由于传感器生成的点云具有很规则的空间排布, 即在成像平面为矩形点列, 我们可以据此直接构建一个三角形网格 (如下图, 图源课程 PPT), 为每个三角形计算法向量, 再插值得到顶点法向量.
另一种比较通用的计算点云法向量的方法见 "SDF 曲面重建" 中的 MLS 方法.
1.3 样条曲线与曲面
3D Vision with Transformers: A Survey - Scientific Figure on ResearchGate. Available from: https://www.researchgate.net/figure/arious-3D-representations-of-the-Stanford-bunny-22-The-projection-based-3D_fig1_362567752 [accessed 25 Feb 2025]↩︎
这实际上要求 mesh 是可定向的 (orientable), 即曲面有正反两个面. 大部分常见曲面 (如平面, 球面, 环面) 都可定向. Möbius 带和 Klein 瓶都只有一个面, 是不可定向的. 可定向等价于曲面拥有连续的单位法向量场.↩︎