《现代计算机图形学基础》课件 chap4-数字几何处理

计算机图形学第四章数字几何处理供《现代计算机图形学基础》配套使用1提纲1.基础2.网格去噪3.网格简化

4.重新网格化5.网格编辑6.网格形变21.1几何数字化媒体数字化进程声音、图像、视频、几何3媒体数字化声音图像视频几何1.1几何数字化2000年左右1995年，“玩具总动员”动画，数字化娱乐1997年，“数字米开朗基罗”计划，数字化文物1998年，“数字地球”，数字化生活41.2数字几何1.2.1几何表示离散元素表示几何形状点云多边形网格51.2数字几何1.2.1几何表示1.2.1-1点云采用三维坐标点作为模型几何表示的基本单元62.5K6K17K1.2数字几何1.2.1几何表示1.2.1-1点云优点简单的数据结构更精致缺点不连续的几何基元大量的数据拓扑结构等性质表示复杂7≈10亿个点1.2数字几何1.2.1几何表示1.2.1-2多边形网格由顶点、边和多边形面组成的集合，定义了三维形状8三角形网格四边形网格1.2数字几何1.2.1几何表示1.2.1-2多边形网格由顶点、边和多边形面组成的集合，定义了三维形状分段线性逼近函数91.2数字几何1.2.1几何表示1.2.1-2多边形网格10NURBS网格CncontinuityQuadtopologyC0continuityTopologyfree点云网格C-1continuityTopologyfreeNo-connectivityC0continuityTopologyfreeConnectivity1.2数字几何1.2.2几何性质1.2.2-1基本概念顶点的度（degree）：相邻边的数量表面朝向（orientation）：顺时针方向的顶点的顺序或者逆时针方向111.2数字几何1.2.2几何性质1.2.2-1基本概念拓扑（topology）：网格几何元素的连接关系亏格（genus）：影响表面连续性的分割曲线条数121.2数字几何1.2.2几何性质1.2.2-2基本性质流形网格：局部同胚与圆盘每个边只连接一个或者两个表面表面上相邻顶点形成一个封闭或开放式扇形非流形网格：局部与圆盘不同胚131.2数字几何1.2.2几何性质1.2.2-2基本性质开网格：具有一条或多条边界边界边：只连接一个入射的表面，或者说顶点只连接一个开的扇形闭网格：不存在边界141.2数字几何1.2.2几何性质1.2.2-2基本性质欧拉-庞加莱特性给定一个无边界的流形网格M，顶点、边、面的个数满足：15#V=766#F=1536#E=2304g=2#V=2999#F=5998#E=8997g=1#V=7929#F=15855#E=23782g=01.2数字几何1.2.3三角网格上的微分算子三角面片的线性表示：重心坐标161.2数字几何1.2.3三角网格上的微分算子三角面片的线性表示：重心坐标一阶导数171.2数字几何1.2.3三角网格上的微分算子三角面片的线性表示：重心坐标一阶导数181.2数字几何1.2.3三角网格上的微分算子三角面片的线性表示：重心坐标一阶导数二阶导数191.3几何深度学习通过在三维几何上定义深度神经网络并进行计算，完成数字几何处理的相关任务。20?1.3几何深度学习1.3.1点云神经网络PointNet：面向三维点云数据的深度神经网络输入：点云转换成n×3的向量结构：多层感知机、向量卷积输出：特征向量211.3几何深度学习1.3.1点云神经网络PointNet：面向三维点云数据的深度神经网络22点云分割1.3几何深度学习1.3.2网格神经网络MeshCNN：面向三角网格数据的深度神经网络输入：三角网格面片结构：以边为基本单元的卷积算子输出：特征向量23五维向量1.3几何深度学习1.3.2网格神经网络MeshCNN：面向三角网格数据的深度神经网络24网格分割提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变252.1概念现实世界中的物体通过数字化扫描获取与重建后的网格往往是带有噪声的激光扫描的深度图像

从图像重建的三维模型262.1概念网格去噪消除网格模型表面噪声，获得一个几何光滑模型又称为网格光顺、网格滤波等27网格去噪2.1概念网格去噪的主要挑战什么是网格表面的噪声？表面的凹凸表面的高频部分…没有精确的数学公式检测困难较弯曲的地方高频部分…282.2方法目标

消除高频噪声：量化模型表面的高频信息保留全局特征：全局特征的几何表示29+=平滑噪声特征2.2方法形状演化策略移动网格顶点保持拓扑：不改变连接关系保持形状：减少曲率变化描述为形状演化302.2方法形状演化策略直接方案直接拉普拉斯平滑加权拉普拉斯平滑间接方案全局拉普拉斯平滑312.2方法2.2.1直接拉普拉斯平滑将顶点移动到相邻顶点的平均位置32平均位置移动顶点2.2方法2.2.1直接拉普拉斯平滑示例332.2方法2.2.1直接拉普拉斯平滑特点循环迭代执行等价于某种能量函数最小化能量：网格中边长平方之和参数：𝜆>

0控制收敛速度不反映网格形状拉普拉斯坐标对旋转敏感局部几何形状会发生扭曲342.2方法2.2.2加权拉普拉斯平滑伞型权重均值权重简单的平均，获得的精度较低余切权重可获得较好的网格变形结果352.2方法2.2.2加权拉普拉斯平滑结果36原始直接拉普拉斯加权拉普拉斯(余切)2.2方法2.2.3全局拉普拉斯平滑37网格的拉普拉斯算子其他

线性方程组2.2方法2.2.3全局拉普拉斯平滑求解拉普拉斯方程齐次方程k是网格中连通区域的数量需要加上某些限制38秩(L)=n-k；2.2方法39控制点控制点2.2.3全局拉普拉斯平滑求解拉普拉斯方程加上部分控制点进行约束秩(L)=n3070个顶点，6144个三角形2.2方法2.2.3全局拉普拉斯平滑结果40Demo134359个顶点，268714个三角形提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变413.1概念网格简化（meshsimplification）通过删除或者修改模型中对形状影响不大的部分网格面片信息（包括顶点、边和面片等）来减少多边形面片数量。423.1概念网格简化（meshsimplification）问题起源：重建的网格模型通常规模较大，不利于存储、传输和显示，因此需要进行满足条件的网格数据简化43≈20亿个三角形移动设备3.1概念遵循原则顶点最少原则：即在给定误差上界的情况下,使得简化模型的顶点数最少误差最小原则：给定简化模型的顶点个数,使得简化模型与原始模型之间的误差最小443.2简化方法3.2.1顶点聚类思想：空间相邻的近似顶点进行合并方法：将原模型包围盒划分,使得小区域中包含了许多散落其中的顶点；再将此区域中的顶点合并,形成新的顶点；根据原始网格的拓扑关系,把这些顶点三角化后,从而得到简化模型453.2简化方法3.2.1顶点聚类算法聚类生成通过空间划分将原始模型的包围盒划分成若干区域463.2简化方法3.2.1顶点聚类算法合并新顶点顶点位置的平均值作为新顶点顶点位置的中值作为新顶点通过二次误差测度求得新顶点473.2简化方法3.2.1顶点聚类算法合并新顶点顶点位置的平均值作为新顶点顶点位置的中值作为新顶点通过二次误差测度求得新顶点48平均顶点位置中值顶点位置二次误差测度3.2简化方法3.2.1顶点聚类算法网格生成聚类p：{𝑝_0,…𝑝_𝑛}q：{𝑞_0,…𝑞_𝑛}如果(𝑝_𝑖,𝑞_𝑖)中间有边那么就连接(p,q)49Demo3.2简化方法3.2.2渐进式网格（Progressivemesh,PM）思想：基于顶点和边的基本操作进行化简方法：以边合并和点移除为基本操作，记录模型简化过程中原顶点和新顶点位置以及顶点间的连接关系的变动信息,从而生成由原始模型的最简化模型和一系列简化信息组成的渐进表示503.2简化方法3.2.2渐进式网格（Progressivemesh,PM）迭代算法选取网格区域应用简化算子(减少顶点与边)直到没有更多减少的可能513.2简化方法3.2.2渐进式网格（Progressivemesh,PM）简化算子：点移除52选择一个即将移除的顶点选择所有和顶点相连的三角形移除选择的三角形添补缺失3.2简化方法3.2.2渐进式网格（Progressivemesh,PM）简化算子：边合并533.2简化方法3.2.2渐进式网格（Progressivemesh,PM）结果54Demo3.2简化方法方法对比顶点聚类计算快，但难以控制简化网格网格拓扑结构被改变误差在全局范围内，但没有接近最优渐进式网格网格质量与速度之间良好的平衡网格拓扑结构不改变可以限制偏差，提高网格质量553.3基于深度学习的网格简化简化算子：复杂网格到简单网格的映射深度神经网络进行简化算子的函数拟合56顶点聚类f顶点移除点采样器边预测器面分类器3.3基于深度学习的网格简化点采样器：从原始网格的N个顶点中选取用于构造简化网格的M个顶点。顶点与1-邻域内顶点偏离程度为573.3基于深度学习的网格简化边预测器：建立采样顶点之间的边连接关系。两个顶点与

之间边连接的概率为583.3基于深度学习的网格简化面分类器：根据边预测器得到的三角面片作为初值，通过图神经网络挑选能够出现在简化网格中的三角面片。两个三角面片与

之间相对位置关系593.3基于深度学习的网格简化60通过面分类器获得每个三角面片属于简化网格的概率，并通过和预设的阈值比较，得到保留下来的三角面片，组成简化后的网格。提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变614.1概念4.1.1定义网格表面和参数域之间的连续映射输入：三维多边形网格表面输出：参数域同构多边形624.1概念4.1.1定义问题起源：1974年，Catmull提出纹理映射技术，通过纹理空间(u,v)和三维曲面(s,t)之间的对应关系，计算三维曲面上每一点颜色值63纹理映射4.1概念4.1.1定义问题起源世界地图绘制球面坐标系644.1概念4.1.1定义问题起源世界地图绘制65原图球极平面投影墨卡托投影阿尔伯斯投影保角的等积的保角的4.1概念4.1.1定义问题起源世界地图绘制66墨卡托投影4.1概念4.1.2类型理想的参数化：保形参数化保持所有的基本几何量不变：长度、角度、面积仅适用于可展曲面对于一般曲面总会有扭曲！67可展曲面一般曲面4.1概念4.1.2类型按照几何量扭曲分类保长度参数化（等距）保角度参数化（等角）保面积参数化（等积）68保长度参数化保角度参数化保面积参数化长度角度面积4.1概念4.1.2类型按照参数域分类平面参数化参数域是平面非平面参数化球面参数化基域参数化……69平面参数化球面参数化基域参数化4.2方法4.2.1数学模型参数域(u,v)参数化映射X(u,v)Jacobi矩阵反映

几何扭曲704.2方法4.2.1数学模型Jacobi矩阵奇异值分解71gG奇异值:γ,Γ保角度

γ=Γ保面积

γ

Γ

=1保长度

γ=Γ

=14.2方法4.2.1数学模型Jacobi矩阵奇异值分解724.2方法4.2.1数学模型定理：每一个保长度的映射都是保角度的和保面积的，反之亦然。保长度参数化是理想的但是并不多见。在实际计算中，我们使用：保角度的保面积的两者之间的平衡73保长度保角度保面积4.2方法4.2.2平面参数化寻找网格表面和平面之间的一一映射开网格（具有边界的网格）固定边界映射自由边界映射闭网格设定边界转化为开网格744.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化弹簧模型（Springsystem）75弹簧系数4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化弹簧模型（Springsystem）76仿射组合系数4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化弹簧模型（Springsystem）仿射组合系数凸组合（convexcombination）线性重构（linearreproduction）77平均系数均值坐标调和坐标4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化弹簧模型（Springsystem）仿射组合系数线性方程组求解78增加约束条件计算非平凡解！4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化固定边界映射（重心坐标映射）79正方形已知未知4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化固定边界映射（重心坐标映射）804.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化固定边界映射（重心坐标映射）81平均系数均值坐标调和坐标4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化自由边界映射固定边界（凸边界）产生较大的几何扭曲通过自由边界减少参数化过程中几何扭曲82固定边界自由边界关键问题：寻找合适的约束来计算有效参数化4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化基于角度的网格展开（Angle-basedflattening,ABF）思想：通过构建参数域三角形内角分布，恢复顶点对应的平面坐标，从而达到保持角度的目的方法：在三角形的内角形成的角度空间定义参数化映射，通过平面三角形的角度约束计算最优参数化坐标834.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化基于角度的网格展开（Angle-basedflattening,ABF）84角度约束:所有内角为正三角形内角之和为π平面顶点周角为2π平面顶点一周封闭4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化基于角度的网格展开（Angle-basedflattening,ABF）优点不会发生边“翻转”优化过程收敛缺点非线性优化（牛顿迭代优化）边界可能发生交叉854.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化最小二乘共形映射（Least-squareconformalmapping,LSCM）思想：保角度映射即共形映射，满足柯西-黎曼方程方法：在三角面上离散柯西-黎曼方程864.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化最小二乘共形映射（Least-squareconformalmapping,LSCM）87目标函数:4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化最小二乘共形映射（Least-squareconformalmapping,LSCM）优点保持角度线性优化缺点无法保证参数化的有效性884.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化直接几何扭曲优化思想：约束三角片参数化映射的几何扭曲方法：直接优化以奇异值为变量的函数89保角度

γ=Γ保面积

γ

Γ

=1保长度

γ=Γ

=1ASAPAAAPARAP4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化直接几何扭曲优化904.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化直接几何扭曲优化优点保长度参数化迭代线性优化缺点无法保证参数化结果的有效性911st2nd3rd4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化92ABFLSCMARAP4.2方法4.2.2平面参数化4.2.2-2闭网格的平面参数化寻找最优切割线将网格切开，变成开网格采用开网格平面参数化934.2方法4.2.2平面参数化4.2.2-2闭网格的平面参数化切割线方法方法1：通过最小生成树在网格表面寻找曲率高的网格顶点及边，形成分割线方法2：结合网格顶点的可见性分布，寻找尽可能被隐藏的切割线94方法1方法24.2方法4.2.2平面参数化优点计算复杂度较低显式控制几何扭曲缺点仅适用于与拓扑圆盘同构的网格曲面对于亏格大于0的网格曲面，一般需要按照一定的规则将整个网格分片，会引起参数化结果不连续954.2方法4.2.3球面参数化将亏格为零的三维网格参数化映射到球面等价于将顶点之间连接结构嵌入到单位球96Steinitz‘stheorem：任何亏格为零且封闭的三角化可以映射成球面三角化。4.2方法4.2.3球面参数化球面重心坐标映射97Laplacian矩阵i-throwofLaplacian4.2方法4.2.3球面参数化球面重心坐标映射984.2方法4.2.4基域参数化选取几何简单，同时拓扑结构（亏格）一致的基网格作为参数域。最常用的基网格参数域是单纯复形（可以看作是传统网格的一部分，只包含连接信息）。99genus=0genus=3提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变1005.1概念网格编辑（Meshediting/deformation）定义：操纵和修改网格表面的几何形状，同时能够保留原始网格几何细节的操作。1015.1概念网格编辑（Meshediting/deformation）问题起源：各种应用中需要动态形状，例如，游戏、电影、计算机辅助设计等。但是，每种状态下的形状单独建模比较费时费力。目标通过内部或者外部作用力改变形状编辑应该是快速的并且尽可能接近现实物体操作1025.2编辑方法5.2.1自由编辑（Free-formdeformation）思想：将网格嵌入到一个简单的控制多面体中控制多面体比原始形状简单方法：对控制多面体进行变形

根据变形后的控制多面体更新嵌入网格的形状103控制网格和原始网格编辑后结果5.2编辑方法5.2.1自由编辑（Free-formdeformation）5.2.1-1基于样条控制顶点的编辑采用三变量张量积样条表示网格形状改变样条控制顶点编辑网格形状1045.2编辑方法5.2.1自由编辑（Free-formdeformation）5.2.1-2基于重心坐标的编辑三角形重心坐标三角网格重心坐标1055.2编辑方法5.2.1自由编辑（Free-formdeformation）5.2.1-2基于重心坐标的编辑结果106Demo5.2编辑方法5.2.1自由编辑（Free-formdeformation）优点任意形状的平滑编辑对编辑的局部控制编辑迅速缺点:难以得到满足物理的编辑效果1075.2编辑方法108Demo5.2.2骨架驱动编辑（Skeleton-drivendeformation）通过改变骨架驱动网格形状变化方便动画师更加灵活地控制具有骨架结构的物体变形

5.2编辑方法1095.2.3基于约束的编辑（Constrain-baseddeformation）思想：交互指定约束类型作为编辑限制点/区域约束方向约束位置约束方法：通过求解满足约束的形状方程计算编辑结果5.2编辑方法5.2.3基于约束的编辑（Constrain-baseddeformation）拉普拉斯网格编辑通过离散的Laplacian微分坐标表示几何细节110

平均邻域5.2编辑方法5.2.3基于约束的编辑（Constrain-baseddeformation）拉普拉斯网格编辑通过离散的Laplacian微分坐标表示几何细节111平均邻域

方向接近法线大小近似于平均曲率1125.2编辑方法

Laplacian微分坐标约束顶点1135.2编辑方法5.2.3基于约束的编辑（Constrain-baseddeformation）拉普拉斯网格编辑结果Demo1145.2编辑方法5.2.4编辑迁移（Deformationtransfer）思想：将网格编辑过程迁移到其他网格方法在源对象和目标之间建立对应的映射将对源对象的编辑迁移到目标，快速生成目标的编辑效果Demo原图目标参考提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变1156.1概念网格形变（Meshmorphing）定义：给定源网格和目标网格形状，自动插值生成中间过度形状的网格116源网格目标网格6.2方法6.2.1基于参数化的网格形变MAPS(曲面的多分辨率自适应参数化)网格变形指定源网格S和目标网格T之间的特征点对和特征线对1176.2方法6.2.1基于参数化的网格形变MAPS(曲面的多分辨率自适应参数化)网格变形使用MAPS来构造基域（basedomain）Sb

和Tb，作为源网格和目标网格的参数域118SbTb6.2方法6.2.1基于参数化的网格形变MAPS(曲面的多分辨率自适应参数化)网格变形网格简化：使用边合并的顶点消除法，重建拓扑一致的源/目标网格1196.2方法

120S

TTb6.2方法6.2.1基于参数化的网格形变MAPS(曲面的多分辨率自适应参数化)网格变形插值生成中间形状网格：对源三角网格和目标三角网格对应的顶点进行几何插值，生成中间形状的三角网格。121Demo6.2方法6.2.2基于微分坐标的网格形变思想：源网格和目标网格顶点的直接插值，容易产生体积收缩、几何细节扭曲等问题。通过插值网格表面的几何细节，生成更优的中间网格。方法：插值微分坐标表示的几何细节122顶点线性插值微分坐标插值源网格目标网格6.2方法6.2.2基于微分坐标的网格形变拉普拉斯形状插值拉普拉斯微分算子计算微分坐标微分坐标变换的极分解，插值旋转R和缩放S123源网格目标网格6.2方法6.2.2基于微分坐标的网格形变拉普拉斯形状插值结果124顶点线性插值微分坐标插值6.3深度学习方法6.3.1变分自编码器VariationalAuto-Encoder（VAE）是一种典型的非监督式深度神经网络。1256.3深度学习方法6.3.2基于VAE的网格形变通过VAE提取和表示表示三角网格特征和生成插值的中间形状。126旋转不变网格差分（RIMD）6.3深度学习方法6.3.2基于VAE的网格形变RIMD：Rotation-InvariantMeshDifference127极分解6.3深度学习方法6.3.2基于VAE的网格形变RIMD：Rotation-InvariantMeshDifferenceLoss函数：VAE输出向量进行线性插值：1286.3深度学习方法6.3.2基于VAE的网格形变结果129ReferencesRecentadvancesinremeshingofsurfaces.P.Alliez.,UCELLIG.Ucelli,C.Gotsman,M.Attene.InShapeAnalysisandStructuring.SpringerBerlinHeidelberg,2008,pp.53–82.Asignalprocessingapproachtofairsurfacedesign.Taubin.SIGGRAPH1996ImplicitFairingofIrregularMeshesusingDiffusionandCurvatureFlow.Desbrun,Meyer,Schroeder,Barr.SIGGRAPH1999.AnIntuitiveFrameworkforReal-TimeFreeformModeling.Botsch,Kobbelt.SIGGRAPH2004Bilateralmeshdenoising.Fleishman,Drori,Cohen-Or.SIGGRAPH2003Non-iterativefeaturepreservingmeshsmoothing.Jones,Durand,Desbrun.SIGGRAPH2003Surfacesimplificationusingquadraticerrormetrics.M.Garland,P.Heckbert.SIGGRAPH1997.Quadrilateralmeshsimplification.J.Daniels,C.Silva,J.Shepherd,E.Cohen.SIGGRAPHASI