几何处理

几何处理，亦称网格处理，是一个以应用数学、计算机科学、工程学等领域理论为基础，以设计高效获取、重建、分析、处理、模拟及传输复杂三维模型算法为目标的快速成长的新兴研究领域。作为计算机图形学的分支之一，几何处理关注对几何形体本身的建模，处理，分析及应用，常见操作包括表面重建，噪点过滤，几何分析，形状简化以及交互设计。在概念与方法层面上，几何处理可以被理解为信号处理（一维）和图像处理（二维）的三维类比。

几何处理的过程常被形象地比喻为几何形体的生命周期。

几何处理的应用领域包括从多媒体、娱乐、传统的计算机辅助设计到生物医学计算、逆向工程及计算科学等等。

几何处理作为几何形体的生命周期

几何形体在几何处理中通常是多维的，尤其以2D和3D最为常见。关于几何形体的处理，通常涉及三个阶段：建模，分析与编辑，使用。这三种阶段统称为几何形体的生命周期。

离散模型

不同于数学，在计算机科学中，几何处理的模型通常是离散的。这些离散模型需要具有几何和拓扑性质：几何性质与模型的维度，空间位置，切线，法线和曲率有关；拓扑性质并不会随着平滑的空间变化而发生改变，比如空洞和边界的数量，以及模型的可定向性。有名的不可定向的模型是莫比乌斯带和克莱因瓶。

几何处理常用三角网格（多边形网格的一种）来建立模型。三角网格的几何性质由其构成来表现： 网格中每一个三角形有三个顶点与其相应的空间坐标（通常是3维）；连接这些顶点的是具有方向的线段；线段的方向通过右手定则决定了三角形的法线。

网格匹配

几何处理中遇到的一个常见问题是如何将不同视角、位置的同一物体合并起来，这个问题称为匹配。匹配问题需要找到最优的刚体变换，使得曲面${\displaystyle X}$和曲面${\displaystyle Y}$尽可能地重合。用公式来表示，如果${\displaystyle P_{Y}(x)}$是点${\displaystyle x}$在曲面${\displaystyle Y}$上的射影，我们希望找到最优的旋转矩阵${\displaystyle R}$和平移坐标${\displaystyle t}$来最小化目标函数：

${\displaystyle \int _{x\in X}||Rx+t-P_{Y}(x)||dx}$

虽然旋转不是线性变换，但一个微小的旋转可以线性化成反对称矩阵。同样的距离函数${\displaystyle x-P_{Y}(x)}$也不是线性的，但当${\displaystyle X}$的变化足够小时，也可以线性近似。于是可以使用迭代最近点法（ICP），每次迭代计算微小的变换，而不是一口气计算一个很大的变换。在迭代最近点法（ICP）中，从曲面${\displaystyle X}$选择${\displaystyle n}$个随机的样本点，并投影到曲面${\displaystyle Y}$。为了在网格曲面上均匀抽样，抽样过程分为两步：在单一三角形内均匀抽样；不均匀地抽样三角形，使得每个三角形出现的概率正比于它的面积。单步最优变换从${\displaystyle x}$与它的投影计算而得，变换迭代到收敛为止。

变形

变形是涉及将一些几何形状转换为新几何形状的问题。通常，这些变换是连续的，不会改变形状的拓扑性质。现代基于网格的变形方法能在满足用户在网格上选定的顶点或区域的变形约束的同时，将这些操控位置的变形平滑地传播到其余形状区域，而不会移除或扭曲细节。常见的交互式变形有基于点，基于骨架和基于网箱的形式^[1]。在基于点的变形中，用户可以在形状上的一小组点上施加位置变换。基于骨架的变形定义了形状的骨架，允许用户移动骨架并旋转关节。基于网箱的变形需要围绕全部或部分形状绘制网箱，以便用户在操纵网箱上的点时，其包围的体积相应地发生改变。

参见

• 计算机辅助设计 (CAD)

外部链接

• "数字几何处理", Peter Schroder 与 Wim Sweldens

• 几何处理论文集（页面存档备份，存于互联网档案馆）

• Multi-Res Modeling Group（页面存档备份，存于互联网档案馆）, Caltech

• Computer Graphics & Multimedia Department, RWTH-Aachen University

参考资料

1. Jacobson, Alec; Baran, Ilya; Popović, Jovan; Sorkine, Olga. Bounded Biharmonic Weights for Real-Time Deformation (PDF). ACM Transactions on Graphics - Proceedings of ACM SIGGRAPH 2011. 2011, 30 [2018-12-11]. （原始内容存档 (PDF)于2017-07-22）.