计算机视觉三维测量与建模 课件 【ch08】三维表面建模与网格模型滤波

第八章计算机视觉三维测量与建模三维表面建模与网格模型滤波南京航空航天大学研究生教育教学改革专项（优质教学资源建设）项目资助01三维表面网格模型】9在计算机上存储表面模型的网格（Mesh）的方法有很多种。不同的数据结构在编码、内存和访问性能方面具有非常不同的复杂性。这些结构的核心是存储定义网格的两类信息，即在创建的网格中会编码两种类型的信息：几何信息（即顶点在空间中的位置和表面法向量）和拓扑信息（即网格的连通性以及面之间的关系）。三维表面网格模型】9以三角形网格为例，网格中的每个三角形都和其他三角形共享边。这样的网格模型包含三类基本几何信息：每个三角形都有三个顶点，各顶点都有可能和其他三角形共享；边，一个三角形有三条边，每条边都连接了两个顶点：面，每个三角形都对应一个面，可以用顶点列表或边列表来表示面。010203三维表面网格模型在实际的数据存储中，一个网格模型通常会存储顶点列表和三角形列表（图8.2），存储多边形网格时，还需要定义一个多边形类，用来表达有任意多顶点的面。顶点列表中的每个顶点包含的最基本数据是一个三维坐标，也可能含有点的法向量和颜色亮度等附加数据。每个三角形由对应于顶点列表的三个索引组成，其中顶点索引的顺序是非常重要的，因为一个三角形的三个顶点顺序关系到该三角形面的“正面”和“反面”。一般会用逆时针方向列出顶点指示的面为正面，这样该面的法向量与三个点的列表顺序满足右手螺旋指向，另外预先计算的面的法向量和纹理坐标等也可以存储在面列表中。三维表面网格模型半边数据结构（FalfedgeDataStructure）是流形网格模型中的一种数据存储表达方式，其最大特点是定义了半边(Halfedge）的概念。如图8.4所示，网格的每条边都被分为两个半边，每条半边都是一个有向边，两条半边的方向相反。如果一条边被两个面元公用，则每个面元都能各自拥有一条半边。构造立体几何（ConstructiveSolidGeometry,CsG）是一种基于简单初级实体基元组成的对象模型表示法。CSG的模型通过初级实体集合的布尔型运算组合在一起。三维表面网格模型】9第一类算法是直接计算几何建模算法，也称为豆式建模算法，包括计算凸包（Convex

Fulls）、计算狱洛尼三角剖分（DelaunayTriangulation）和计算阿尔法形状（cshape）等代表性算法。显式建模算法主体上通过连接采样点构建三角形，是对采样点的精确插值。第二类是隐式建模算法，这类算法假设采样点云中隐含一种能够近似表达几何表面模型的隐函数。该类算法将空间区域假设为一个标量场，即由采样点云构造一个函数值分布空间。三维表面网格模型】9第三类算法是利用先导模式化结构对目标进行建模，是一种自上而下的建模算法。在第6章中介绍基于模型的场景结构分割的理论时，对模式化的结构有所定义，可以说这里的模式化建模就是在点云模型化分割的基础上形成网格的一种后处理。基于模板或者先验模式的重建方法可以细分出更多种类、更复杂的子类，随应用场景的不同而可以有多种多样的设计形式。三维表面网格模型纹理模式纹理模式是用于三维模型的真实可视化的直观表达方式，纹理是让三维模型看起来接近现实物体的一个最基本的要素。最简单形式的纹理贴图涉及将单个纹理（如照片或正射影像）映射到由一个或多个多边形组成的表面多边形上。当将影像映射到对象上时，每个对象的多边形颜色都将由从纹理派生的相应颜色进行修改。01三维表面网格模型阴影模式阴影模式（ShadingModel）是基于光学理论（兰伯特余弦定理）设计的，该理论指出，基于完美散射起伏表面的任何小区域（多边形）的亮度都会随着入射平行光角度的余弦而增大。该算法中，最广为人知的是平面阴影和平滑阴影。平面阴影和平滑阴影之间的主要区别在于使用法线的方式。02三维表面网格模型光照模式要为真实场景创建这样一个完整的模型，需要使用大量的视图。这些视图可以视为具有相应颜色值的光线集合，它们是一个完全连续函数的离散样本。考虑到物理限制的附加信息，必须从记录的光线中插入未表示的光线。03三维表面网格模型01压缩数据的几何形状：这类算法试图改善网格的数字信息（顶点的位置、法线、颜色等）的存储，或者寻求对网格拓扑进行有效编码的方法。02控制细节层次(LOD)：出于可视化目的，软件可以用LOD技术在整个场景中平滑变化，不同位置的渲染的细腻程度取决于观察者所在的当前位置。03网格滤波（Filtering）优化和简化(Decimation）：这些算法简化了网格，去掉了冗余的顶点、边和三角形基元，可以选代地移除不符合特定距离/角度标准的顶点，或将边折叠成唯一的项点。04点渲染：特别适用于点云可视化，并且通过是示较少数量的图元来工作。QSplat是一个基于点的渲染系统，能够使用不同复杂形状的溅斑（Splat）图元和不同的透明度米渲染相同的对象，以避免锯齿边缘，在实时性和渲染方面是示出良好的效果。基于网格模型的几何信息和拓扑结构这两个信息，学者们针对三角形网格模型提出了许多压缩算法。三维表面网格模型02显式建模方法凸集有两种定义方式。第一种：如果对任意两点2.9ES，线段P9CS，则集合S是凸的。第二种：如果集合5是(可能无限多个）半空间的交集，则S是凸的。图8.7给出了凸集和非凸集的二维示例。显式建模方法显式建模方法二维空间的Delaunay三角剖分Delaunay三角剖分是一种标准，己有许多计算Delaunay三角剖分的算法，它们主要依赖于检测点是否在三角形的外接圆内，需要设计快速存储三角形的有效数据结构。增量式的枸网算法是最直接有效地计算Delaunay三角剖分的算法。这类算法通过逐点添加的形式插入新顶点，确定图形受影响的部分，仅对一部分区域进行三角剖分约束判断和优化调整。显式建模方法二维空间的Delaunay三角剖分01显式建模方法三维点云数据的Delaunay三角剖分02把Delaunay三角剖分的屈性从二维扩展到更高的三维，其背后的原理是一致的。三维点云的Delaunay三角剖分的约束是四个点组成的四面体（4个三角形）的外接球不包含其他的点，即要生成符合空外接球规则的四面体组成。显式建模方法三维点云数据的Delaunay三角剖分对三维点云处理，依然适用增量式的Delaunay三角剂分算法。首先，初始化一个大的四面体，能够将场景中的所有三维点都包含在内，大四面体的顶点不一定是输入数据的点。然后，依次逐点向其中插入新的顶点，进行判断和构网。每次插入新顶点p时，需要判断点p是落在哪一个四面体的内部，这个四面体被视为一个父节点，新的顶点会将父节点四面体剖分重组，父节点四面体进而被标注为无效。新生成的四面体被视为子节点。寻找父节点的方法可以是遍历己经生成的列表中的所有四面体，也可以是通过设计数据结构加速检索。显式建模方法】9显式建模方法03隐式建模方法】9隐式建模方法】9隐函数表达式：隐式建模方法径向基函数（RadialBasisFunctions,RBF）是一种常用的对离散数据插值的函数方法。对于一组给定采样数据，RBF方法使用一组径向对称的基函数的线性组合生成高度平滑的拟合结果。隐式建模方法隐式建模方法移动最小二乘（MovingLeastSquares,MIS）算法将重建表面近似为一个空间变化的低阶多项式。如8.3.1节所达，隐式表面建模对应的是一个插值问题，MLS算法用局部多项式f(x)逼近表面F。用移动最小二乘算法将插值问题变为一个函数优化问题，f(x)被选为对数据点x的最佳名项式逼近。隐式建模方法隐式建模方法】9泊松表面重建方法（PoissonReconstruction）是KazhdanM等人在2006年提出的种隐函数建模方法143，并且提供了开源代码，是目前广为使用的一种表面建模方法。泊松表面重建方法利用Poisson两数来解决有向点云的表面拟合问题。它结合了全局拟合和局部拟合两类方法的特点，因此在速度和精度两个方面有较好的效果。由于全局优化的特性，在形成邻近区域、选择面片类型和调整权重时不涉及启发式的决策。另外，基函数是和周围空间相关的而不仅是和数据点相关的，有一个局部层次支持的结构，从而产生稀疏的优良表现。隐式建模方法】9隐式建模方法01下面介绍用MC算法构建网格模型的步骤：将三维空间规则地进行体素化，离散后的每个体素单元都包含8个顶点{v1,…,v8}，每个顶点都能够由隐函数计算出对应的函数值，即计算出f(vi）。02对体素的顶点进行标记。如果f(vi)的值大于或等于零等值面的值，则认为该顶点位于等值面之外，标记为“0”03根据8个顶点的二进制标记值计算体素的素31号index。隐式建模方法04根据体素的索引号index，在预先构建好的查找表中找到体素内的网格的连接方式。05尽管知道了等值面会穿过哪条边，如边（VaVb），但具体在边上会经过的点位置还没有确定。此时，需要通过插值计算找到，可以使用边的两个顶点位置由简单的线性插值计算。06消除歧义。在算法中设计了根据体素顶点的法向量消除这样的不连贯歧义。在整体的体素划分空间中，每个顶点有上、下、左、右、前、后6个相邻的顶点，采用中心差分方法可以计算该顶点的梯度矢量隐式建模方法04模型网格滤波去噪双边滤波（BilateralFilter）算法最早由Tomasi和Manduchi于1998年在影像处理领域中提出。双边港波利用像素的至高差异和亮度差异两类信息设计加权平均的平滑算子，在对亮度值降樂平滑的同时保持影像的梯度边缘特征。具体公式为:模型网格滤波去噪法向量是一种能够反映场景几何表面形态的重要参数，平滑区域的三角形面元的法向量应当是接近平行的；而表面转折明显的边缘区域的三角形面元的法向量表现出较大的夹角。法向量引导滤波（NormalGuidedFitter）1s91是指利用网格面元的法向量信息来引导面元的顶点更新的技术，它可以拆解为法向量更新和顶点更新两个主要的步骤。首先，对网格的三角形面元的法向量进行平滑滤波，得到调整后的法向量信息；然后，根据调整后的法向量更新面元的顶点坐标，使之能够与法向量的信息匹配一致。模型网格滤波去噪在SunX等人设计的法向量滤波中，滤波结果是邻域法向量的加权平均。下面介绍几种法向量滤波的改进技术。模型网格滤波去噪05应用举例在法向量引导的顶点更新算法中，法向量的准确性直接关系到顶点更新的准确性。在计算机图形学中使用的许多网格都是分段平滑的，即它们的表面包含由尖锁的边缘隔开的平滑区域。在对尖边缘附近的表面三角形面元的法向量进行滤波时，应避免将其与跨边缘的外部法向量相联系。应用举例】9数字化的三维模型几乎已经应用到了各行各业中，比如图8.32列举的例子。根据具体的应用需求不同，建模所选择的方法会有所区别，但整体而言，寻求精简、保真和表面流形的要求是大多数算法都需要满足条件。应用举例图8.34展示了一组利用各种网格去噪滤波算法对网格模型进行处理的对比实验，放大视口展示了局部的三角网分布。从图中可以看出模型经过滤