多边形网格是一种表面表示,由多边形面沿边和顶点连接而成。其几何信息规定各个元素在空间中的位置,而连接关系则规定这些元素如何彼此相连。三角形网格和四边形网格尤为常见。虽然人们最熟悉的是用作三维模型的网格,但网格也可以表示平面区域、抽象曲面,以及嵌入高维空间的边界。
多边形网格在计算机图形学中占据核心地位,因为它们在几何形状与计算操作之间架起了一座实用的桥梁。它们可以近似表示光滑物体,表现刻意设计的多面形态,承载材质和纹理信息,并支持高效的可见性与光照计算。相关方法也是工程分析、数字化制造、科学可视化以及根据测量数据重建物体的基础。
同一个可见表面可以采用多种不同的网格表示,而这些网格在编辑、变形、渲染或数值计算中的表现可能大不相同。因此,网格设计不仅要考虑多边形的数量和位置,还要考虑拓扑结构、单元质量、属性的组织方式,以及后续应用的需求。
几何、连接关系与曲面拓扑
网格通常由顶点、边和面的集合来描述。顶点一般具有位置 。边连接两个顶点,面则由顶点或边组成的有序闭环来确定。这一顺序确定了面的朝向。几何与连接关系彼此独立:移动顶点会改变形状,但不一定改变连接关系;而拆分一条边会改变连接关系,即使所表示曲面的几何形状保持不变。
三角形具有独特的计算优势。三个不共线的点确定一个平面,因此三角形面的平面内部区域是明确无歧义的。四边形或顶点更多的多边形可能不共面;此时,要确定其内部区域,就需要采用某种约定,例如三角剖分或双线性曲面片。对于不共面的四边形,沿不同对角线进行划分,通常会得到不同的分片平面曲面。自相交的多边形边界会带来更多歧义,因为其预期内部区域取决于填充规则或预先进行的修复操作。
区分几何重合与拓扑连接至关重要。两个顶点可以具有完全相同的坐标,却仍是彼此独立的网格元素。反过来,多个面可以共享同一个顶点,即使由此形成的邻域不符合通常意义上的曲面要求。在二维流形网格中,每个点的邻域都类似于圆盘,边界点的邻域则类似于半圆盘。内部边恰好与两个面关联,边界边则与一个面关联。仅考察边与面的关联关系还不够:两片原本分离的曲面若仅在一个顶点处接触,即使没有任何一条边被两个以上的面共享,也会形成非流形顶点。
对于有限网格,欧拉示性数为
其中,、 和 分别为顶点数、边数和面数。对于亏格为 、具有 个边界分支的连通、紧致、可定向曲面,
与球面拓扑等价的闭曲面的欧拉示性数为 ,环面的欧拉示性数则为 。这些恒等式可用于一致性检查,但计数符合预期并不能证明网格不存在自相交或其他缺陷。几何上自相交的曲面,其抽象连接关系仍可能完全有效。
多边形网格通常描述的是曲面,而不是填充某个体积的材料。封闭、朝向一致且不自相交的曲面可以界定一个实体,但任意一组多边形并不必然具备这一能力。相比之下,体网格会明确地将三维区域划分为四面体或六面体等单元。混淆边界表示与内部离散化,可能导致仿真、体积计算和制造中的错误。
数据结构与属性组织
最简单的存储方案是逐个独立列出多边形,为每个多边形重复存储其所有顶点坐标。这种“多边形汤”易于构建和拼接,但共享边界并未显式记录。要判断两个面是否相邻,就必须比较它们的坐标,或先合并等价的顶点。这种方法可以用于组织较为松散的三角形集合,但不太适合需要反复遍历邻域的操作。
索引网格则存储一个位置数组和一个面索引数组。例如,一个三角形由三个指向位置的整数表示。闭合三角形流形满足 ,因为每个三角形贡献三次边关联,而每条边属于两个三角形。因此,对于大型的类球面三角剖分,由欧拉公式可得近似关系 。若仅存储采用 32 位数值的位置坐标和 32 位三角形索引,则需要约 字节,即约 字节。法线、纹理坐标、邻接关系、材质、内存对齐及其他属性都可能使存储需求大幅增加。
更显式的数据结构支持局部遍历。半边结构通过有向关联来表示每条边,通常记录一个顶点、一个关联面、沿该面的下一条半边,以及一条方向相反的孪生半边。边界的处理约定各不相同:有些实现会创建不与普通面关联的边界半边。有了适当的引用,软件便可绕面或绕顶点遍历,而无须在整个网格中搜索。布鲁斯·鲍姆加特于 1972 年提出的翼边结构则围绕边来组织邻接关系。这两种方法都以额外的内存开销换取便捷的拓扑访问。
属性不必与位置使用相同的索引。纹理接缝处的一个曲面点可能只有一个几何位置,却有两个纹理坐标。一条锐边的两侧可能需要不同的法线。因此,建模系统通常会将数据关联到面的角点(也称为 loop),而不是只关联到顶点。在准备索引渲染缓冲区时,只要某个位置对应的完整属性元组有所不同,软件通常就会复制该位置。因此,模型的几何顶点数可能小于其渲染顶点数。
连接关系也会影响执行效率。重新排列面和顶点可以改善 CPU 缓存中的数据局部性,并减少图形处理器中的重复工作。紧凑排列的数组适合流式处理和并行处理,而大量使用指针的结构则适合某些编辑操作。非流形网格可能需要径向边结构或更通用的关联表示,因为单个孪生引用无法表达任意数量的关联面。因此,没有一种存储布局能同时在模型创作、渲染、修复和数值分析中达到最优。
网格构建与重建
网格可以通过交互式建模操作直接创建。挤出操作将选定的面或边界延伸为新的几何形状;旋转操作使轮廓绕轴旋转,构建出表面;扫掠操作则使截面沿路径移动。这些过程通常会生成规则的四边形布局,但在分支结构或轮廓退化的位置附近,需要进行特殊处理。长方体、圆柱体和球体等基本几何体提供初始的连接关系,供美术人员和工程师通过后续操作加以修改。
另一种途径是对已有的数学曲面进行镶嵌剖分。在计算机辅助设计中,物体通常由经过裁剪的参数曲面片定义,而不是由多边形定义。镶嵌剖分对这些曲面片进行采样,再将采样点连接成面。自适应方法会在曲率较大或投影误差可能被察觉的区域使用更小的单元。弦高公差用于限制曲面与其多边形近似之间的偏差,角度公差则可约束表面法线的变化。相邻曲面片在公共边界处的剖分必须一致,以避免出现裂缝。
实测数据带来了不同的问题。激光扫描和基于图像的重建通常会生成点云,其中记录了采样点,却不一定包含表面的连接关系。摄影测量利用相机几何关系和对应关系,从相互重叠的图像中估计三维结构。重建过程必须推断哪些采样点属于同一表面,区分噪声与微小特征,并处理因遮挡而没有观测数据的区域。仅有较高的采样密度并不能保证网格准确:即使数据非常密集,标定误差或系统性的重建偏差仍可能存在。
一些重建方法通过中间场来恢复表面。迈克尔·卡兹丹、马修·博利索和于格·霍普于2006年提出的泊松曲面重建方法,利用带有方向信息的采样点估计一个指示函数,该函数的梯度与测得的法线相关。所得场的一个等值面便构成重建网格。这种方法可以从不完整的测量数据中生成封闭表面,但推断出的区域未必与实际观测到的几何形状相符。法线方向不准确以及彼此靠近的薄层表面,也可能导致错误连接。
体标量数据提供了另一种途径。威廉·洛伦森和哈维·克莱恩于1987年发表的移动立方体算法会逐一检查网格单元,在选定标量等值面与单元边相交的位置构建三角形。该算法广泛用于采样场的可视化,包括经过分割的成像数据。最初基于不同情形分类处理的构建方法存在歧义配置,后来的变体引入了规则,以获得更一致的拓扑结构。网格间距和所选等值都会影响生成的几何形状;网格体现的是对采样场的一种特定解读,而不是不受分辨率影响的精确还原。
渲染、法线与纹理坐标
大多数交互式渲染系统最终都将网格作为三角形来处理。在光栅化过程中,顶点被变换到观察坐标系中,三角形经过裁剪和投影,其覆盖的图像采样点则获得插值后的属性。三角形尤其适合这一过程,因为其内部坐标和插值规则都很简单。因此,包含四边形或更大多边形面的模型,通常会在绘制前进行三角剖分;这一操作既可以由导出程序显式完成,也可以由渲染系统在内部完成。
对于顶点位置为 的三角形,其有向单位面法线为
对于退化三角形,分母为零。颠倒顶点顺序会使法线反向,并可能影响背面剔除。使用面法线会产生平面着色的外观;而顶点法线则能产生视觉上平滑的着色效果,通常由相邻面的法线按面积或角度加权计算得到。对法线进行插值会改变光照计算,但不会改变底层的分片平面几何形状。
从历史上看,亨利·高洛德于 1971 年发表的高洛德着色法,是在多边形内对顶点的光照结果进行插值。裴祥风于 1975 年的研究确立了涉及法线插值和镜面反射的重要方法。现代可编程着色器支持复杂得多的材质计算,但曲面的几何朝向与插值后的着色法线之间的区别仍然十分重要。一个看似平滑的物体,仍可能显露出多边形轮廓,投下带有棱角的阴影,或与另一物体相交形成明显的直线段。
纹理映射将曲面上的位置与一幅或多幅图像中的坐标关联起来。对于三角形,可以用重心坐标表示其中的一个点:
同样的权重也可用于对三角形上的属性进行插值,但投影后,相关的量需要进行透视校正。纹理接缝允许将曲面切分成若干平面参数图,但也会在属性空间中造成不连续。跨越参数图边界进行滤波可能产生可见的伪影,除非图像布局提供了适当的边缘填充,并采用合适的采样约定。
法线贴图会扰动着色所用的法线,而不移动曲面。相比之下,位移贴图会修改几何形状或求值所得的曲面,因此能够改变轮廓和可见性。这些区别在光线追踪中十分重要,因为光线与实际几何体求交;在近距离观察时也同样重要,因为仅靠光照无法掩盖粗糙的曲面细分。图像采样不足时,纹理细节还会引入混叠;滤波和分级纹理表示所解决的问题,与提高网格分辨率所解决的问题并不相同。
细分与多分辨率曲面
粗网格可以充当较光滑曲面的控制结构,而不必直接作为最终渲染的几何体。细分曲面通过反复细化网格连接结构,并依照局部规则更新顶点位置来定义。在适当条件下,这些逐次生成的网格会收敛到一个极限曲面。这种方法将可编辑的控制笼与渲染所需的网格密度分离开来,使相对少量的控制顶点就能描述复杂的光滑物体。
埃德温·卡特穆尔和吉姆·克拉克于 1978 年提出了影响深远的细分方法。该方法为每个面生成一个面点,为每条边生成一个边点,并重新定位已有顶点。经过一次细化后,即使原始各面的边数不同,生成的网格也全部由四边形组成。在远离奇异顶点(即价数不同于常规值 4 的顶点)的区域,极限曲面具有双三次 B 样条曲面的性质。在满足该方案假设的前提下,其广泛使用的形式通常在规则区域具有二阶连续可微性,在一般的奇异顶点处具有一阶连续可微性。
查尔斯·卢普于 1987 年提出的细分方案则作用于三角形网格。每个三角形被分成四个,新顶点和已有顶点的位置均通过对邻域加权计算得到。其常规顶点价数为 6。Catmull–Clark 细分和 Loop 细分都会使控制网格变得光滑,因此通常不会插值通过所有原始顶点。包括蝶形细分在内的插值型方案适用于必须通过已有采样点的应用,不过,其光滑性以及在不规则连接结构附近的表现需要采用不同的分析方法。
实际实现还会加入边界规则和折痕控制。标记出的折痕可以保留尖锐的棱脊,而不受限制的平滑处理则会将其磨圆。半锐折痕允许特征随着细化层级的增加而逐渐变得柔和。属性的细化需要单独处理:位置连续并不意味着纹理坐标也应在接缝处保持连续。不加区分地将同一种平均规则应用于位置、法线、颜色和材质标识符,可能会破坏刻意保留的不连续性。
细分不同于仅将多边形分割而不改变其形状。将一个三角形分成若干共面的小三角形,只会提高分辨率,并不会增加新的几何细节。细分平滑会改变所表示的曲面,而置换则可以为细化后的基面添加细节。多分辨率编辑将这些思路结合起来,在较粗层级存储整体形状,在较细层级存储更小尺度的修正。由于均匀细化会使面数迅速成倍增长——常见的三角形和四边形方案通常每一步都会使面数变为原来的四倍——自适应求值会将计算集中在可见细节、轮廓或高曲率区域附近,而不是对整个物体进行同等程度的细化。
简化、重网格化与几何处理
网格处理通过改变几何形状或连接关系来实现某种计算目标。简化是在控制某种误差度量的前提下减少元素数量;重网格化通过重新剖分来改善元素的分布或排列方向;平滑则抑制不需要的变化。这些操作彼此相关,但不能相互替代。一个网格可能面数很少,却无法准确保留几何形状;也可能面数很多,元素形状却很差。网格质量必须结合其预期用途来评估。
一种常见的简化操作是边折叠,即合并一条边的两个端点,并移除因此变得冗余的相邻面。迈克尔·加兰和保罗·赫克伯特于 1997 年提出的二次误差度量方法,为每个顶点关联一个由附近面所在平面导出的二次代价。对于齐次坐标位置 ,累积代价的形式为
候选的边折叠操作按代价排序,并使用优先队列依次处理。还需要进行额外检查,以避免产生无效拓扑、面翻转,或对边界及属性接缝造成不可接受的破坏;仅仅保证到平面的距离代价较小,并不能确保得到良好结果。
重网格化通常结合边分裂、边折叠、边翻转和顶点重定位等操作。各向同性重网格化力求生成大小较为均匀、形状良好的元素,而各向异性重网格化则根据曲率等具有方向性的特征,调整元素的朝向和长宽比。三角形的质量很重要,因为过小的角度或接近零的面积可能使几何计算和数值方程求解变得不稳定。不过,并不存在普遍最优的形状:如果细长元素是为了顺应具有明显方向性的解或表面特征而特意设置的,那么它们也可能是合适的。
平滑体现了视觉效果改善与几何形状保持之间的区别。简单的拉普拉斯更新会将顶点移向其邻接顶点的平均位置,
反复应用这一操作可以消除高频变化,但往往也会使表面收缩,并使尖锐细节变圆。其他方法则采用不同的权重、受约束的移动、隐式积分,或多种平滑步骤的组合。离散微分几何提供了余切权重拉普拉斯算子等工具,将网格计算与曲率及微分方程联系起来。
修复和布尔运算对鲁棒性提出了更高要求。重复面、孔洞、朝向不一致、自相交以及几乎重合的表面,都可能使原本有效的算法失效。计算并集或交集通常需要检测面之间的相交、细分相交区域、对各部分进行分类,并组装出一致的边界。计算几何为朝向判断和相交判断等提供了精确谓词或过滤谓词。这些工具十分重要,因为浮点误差可能使相邻的处理步骤对某个点是否位于面的某一侧得出不一致的判断,从而留下裂缝或产生相互矛盾的连接关系。
变形与网格动画
动画使网格的几何形状随时间变化,而通常保持其连接关系不变。固定的顶点对应关系有助于简化存储、插值以及帧间材质属性的传递。刚体运动对整个对象施加同一个变换,而非刚性变形则使不同区域以不同方式运动。变形网格的质量取决于其连接关系、变形方法与预期运动之间的配合,而不只是网格的分辨率。
骨骼动画利用具有层级关系的关节来驱动表面。在线性混合蒙皮中,每个顶点都关联着若干关节权重,通常要求这些权重非负且总和为一。若 包含相应的关节变换和绑定变换的逆变换,则有
这种计算开销较低,也很适合在图形硬件上执行。然而,以矩阵形式混合刚体变换并不能保持刚性:扭转的肢体可能在其轴线周围塌缩,产生常见的“糖纸扭曲”伪影,而关节弯曲时则可能损失体积。
双四元数蒙皮采用更适合描述旋转和平移的表示方式来混合变换,通常能够减轻扭曲伪影。但它也带来了其他设计上的考量,尤其是在需要表示缩放或剪切时。修正形状和随姿态变化的调整可以弥补基础蒙皮无法处理的变形问题。这些补充手段十分常见,因为少量刚体运动的加权平均无法准确描述人体关节或衣物褶皱。
混合形状动画将表情或形状变化表示为多个连接关系一致的网格的组合。给定中性姿态下的位置 和目标偏移量 ,有
这种方法适用于面部表情和美术师控制的形状修正,但其前提是顶点之间存在一致的对应关系。如果没有预先建立映射,仅按数组索引对两个互不相关的网格进行插值,在几何上并无实际意义。
网格布局会影响这些技术的效果。沿嘴部或关节周围布置的边,比任意三角剖分更有助于让变形以可预测的方式分布;而形状或尺寸极不均匀的网格单元在拉伸或折叠时可能表现不佳。物理动画还会加入由弹性、弯曲、接触或体积守恒推导出的约束。布料模型可以使用曲面网格,而实心弹性物体通常需要体积离散化或其他内部模型。大变形、撕裂以及接触关系的变化,可能要求重新划分网格,并将速度、材料属性和其他状态变量转移到新的网格单元上。
工程、科学与制造领域的应用
在工程中,网格既可以表示几何边界,也可以是数值离散化的一部分。有限元法通过与单元及其自由度相关联的基函数来近似表示场。面单元用于壳体和薄膜,而四面体或六面体单元则用于表示三维连续体。用于渲染的网格并不一定适合分析:一个视觉上逼真的模型可能包含间隙、重叠、狭长碎片或缺失的内部信息,从而导致计算无法稳定进行。
分析质量取决于单元几何形状、网格细化程度以及所求解的数学模型。增加单元数量可以提高近似精度,但形状不良的单元可能导致方程组病态,或使计算得到的梯度不准确。在角节点数量相同的情况下,带曲边或曲面的高阶有限元可能比线性多边形面更准确地表示边界。网格细化通常集中在解变化剧烈的区域,例如几何奇异点或应力集中部位附近,而不是为了视觉上的平滑而均匀分布。
在科学可视化中,网格既用于描述观测到的结构,也用于描述推导出的表面。地形模型可以采用不规则三角网,根据地形的复杂程度分配采样点,而不是采用均匀栅格。等值面用于呈现标量场中选定的数值层面,而表面属性着色则用于显示温度、压力或位移等物理量。此时,可见网格只是整个表示的一部分:场的单位、坐标系、采样不确定性和插值规则共同决定了可视化结果的科学含义。
数字化制造利用表面网格向后续处理环节传递形状信息。在逐层成形的3D打印中,软件将模型与一系列平面求交,以生成轮廓和工具路径。开放边界、翻转的面和自相交都可能使模型预期的内部区域难以确定。水密边界固然重要,但仅凭这一点并不能认定设计具备可制造性。壁厚、工艺分辨率、支撑要求和材料行为,都不是仅有一个有效的多边形表面就能涵盖的。
其他应用则将实测几何与语义或历史信息相结合。文化遗产项目利用重建网格记录文物和遗址;虚拟现实系统需要在视点不断变化时仍能高效处理的几何模型;计算机视觉系统则可能利用网格进行物体跟踪或基于模型的重建。不同应用场景所需的表示方式各不相同。存档用扫描模型可能优先考虑测量保真度和来源记录,交互式资产可能优先考虑每帧耗时的稳定性,而数值模型则可能优先考虑单元质量和物理边界条件。
交换、压缩与验证
网格交换之所以困难,是因为网格包含的内容远不止三角形列表。坐标系、单位、朝向约定、材质、纹理图像、动画和自定义属性都可能十分重要。有的应用程序允许位置和纹理坐标分别使用独立索引,而另一些则要求用一个索引来引用完整的顶点记录。因此,格式转换可能会重复生成顶点或丢弃属性,而表面上的三角形数量却不变;看似细微的约定差异,也可能导致模型被镜像翻转或面朝向反转。
几种格式体现了不同的侧重点。STL 存储三角形面片及其标称法向量,但既没有规定通用的材质系统,也不声明物理单位。它逐一显式记录三角形,因此结构简单,却不会直接表示三角形之间共享的连接关系。Wavefront OBJ 可以表示多边形面,并分别为位置、纹理坐标和法向量使用独立索引,材质信息通常由配套文件提供。PLY 支持具名的元素属性,广泛用于存储扫描数据。这些格式在几何表示能力上有所重叠,但在属性约定和场景语义方面存在显著差异。
更侧重场景的格式还会承载单个曲面以外的各种关系。Khronos Group 于 2017 年发布的 glTF 2.0 规范定义了网格图元、缓冲区、材质、节点变换、蒙皮和动画,以实现高效的资产交付。通用场景描述(Universal Scene Description,USD)最初由皮克斯开发,用于场景的组合与交换,其中也涵盖多边形曲面和细分曲面。在这类系统之间作出选择,并不只是选择文件扩展名:它决定了模型的结构、行为以及制作背景中的哪些信息能够在传递过程中保留下来。
数据压缩可以同时减少连接关系和属性所需的存储空间。连接关系编码利用网格局部遍历中的规律,而位置编码则可以采用量化,以及基于相邻顶点的预测。量化会限制坐标分辨率,因此,名义上只是经过压缩的模型,也可能无法再精确保留微小间隙或重合的边界。网格简化则有所不同:它减少的是几何复杂度,而不只是以更紧凑的方式编码相同的连接关系。渐进式表示将粗糙的基础网格与细化操作组织在一起,使细节能够逐步传输或显示,Hugues Hoppe 于 1996 年提出的渐进网格就是其中一例。
验证必须与预期用途相适应。渲染器或许能够接受相交或互不连接的三角形,而实体建模操作却可能无法解释这些几何结构。实用的检查项目包括索引有效性、坐标是否为有限值、面的面积是否非零、朝向是否一致、边界检测、流形性、自相交,以及所需属性是否得到保留。数值容差必须与模型尺度相适应:同一个固定的坐标阈值,对千米尺度的地形可能无伤大雅,却可能抹去微观模型中的特征。因此,验证结果描述的是网格是否满足某一组特定的几何要求和应用要求,而不是判定它是否达到了某种普适的“好网格”标准。