三维建筑模型的低模网格生成.pdf

2023 年 8 月 图 学 学 报 August2023第 44 卷 第4期 JOURNAL OF GRAPHICS Vol.44No.4 收稿日期：2022-11-24；定稿日期：2022-12-26 Received：24 November，2022；Finalized：26 December，2022 基金项目：国家重点研发计划项目(2021YFE0108400)；国家自然科学基金项目(62172294)Foundation items：National Key Research and Development Program of China(2021YFE0108400);National Natural Science Foundation of China(62172294)第一作者：岳明宇(1999)，男，硕士研究生。主要研究方向为三维模型处理。E-mail： First author：YUE Ming-yu(1999),master student.His main research interest covers 3D model processing.E-mail： 通信作者：毕重科(1982)，男，副教授，博士。主要研究方向为可视化与高性能计算。E-mail： Corresponding author：BI Chong-ke(1982),associate professor,Ph.D.His main research interests cover visualization and high performance computing.E-mail： 三维建筑模型的低模网格生成 岳明宇1，高希峰2，毕重科1(1.天津大学智能与计算学部，天津 300350；2.腾讯科技有限公司光子游戏工作室群，华盛顿 贝尔维尤 98004)摘要：三维虚拟场景中，低模网格(三角面数较少的网格)在多细节层次等方面的运用对实时运算效率提升有着重要的作用。然而，给定高精度的建筑模型(高模网格)，现有方法所生成的低模网格很难在达到极低简化率的同时依旧与原高模网格保持良好的视觉相似性，仍需人工调整以修正缺陷。为此提出了一个新的方法，用户仅需提供少量鲁棒的参数，就能生成具有良好视觉相似性和满足水密性、流形等良好几何特性的低模建筑网格。首先，为了从高模网格中捕获重要的几何特征，需通过逆渲染的方法对另一个新网格变形，使其与高模网格有相似的外观且仅保留大尺度的外观特征。为保持网格拓扑在变形过程中的一致性，可将高模网格体素化后的外包(The outer hull)作为被变形网格的初始化。之后，为处理变形过程中带来的相交三角形，还设计了参数自适应模型拓扑的 alpha wrapping 算法。通过保证变形后网格体素化后的外包和结果网格的亏格数一致，该算法能够生成变形后网格的近似网格，且保证近似网格无相交三角形、满足水密性和二流形。最后，部署了一个改进的边收缩算法将 alpha wrapping 算法生成的网格简化到用户的目标面数，该算法对平面上点对合并过程进行了数值优化。在一个建筑模型的数据集上测试了本文方法并将其与最流行和最先进的方法进行了比较，证明了其稳健性和有效性。关键词：网格简化；三角形网格；低模网格生成；细节层次；建筑模型 中图分类号：TP 391 DOI：10.11996/JG.j.2095-302X.2023040764 文献标识码：A 文 章 编 号：2095-302X(2023)04-0764-11 3D low-poly mesh generation for building models YUE Ming-yu1,GAO Xi-feng2,BI Chong-ke1(1.College of Intelligence and Computing,Tianjin University,Tianjin 300350,China;2.LightSpeed Studios,Tencent Technology Company Limited,Bellevue WA 98004,USA)Abstract:Within the domain of 3D virtual scenes,the usage of low-poly meshes(meshes comprised of few triangles)used in levels of detail play a pivotal role in improving the efficiency of real-time rendering.However,given detailed building models(high-poly meshes),it is difficult for the low-poly meshes generated by the existing methods to maintain good visual similarity with the high-poly meshes while achieving extremely low simplification rates,requiring the manual correction of defects.We proposed a novel method in which the user only needed to provide a few robust parameters to generate low-poly building meshes with good visual similarity and satisfying benign geometric properties such as watertightness and two-manifold.Firstly,new meshes were morphed by inverse 第 4 期 岳明宇，等：三维建筑模型的低模网格生成 765 1 rendering,enabling the capture of important geometric features from the high-poly meshes,so that they could have similar appearances to the high-poly meshes and retain only the large-scale appearance features.Additionally,to maintain the consistency of the mesh topology during the morphing process,we leveraged the outer hull of the voxelized high-poly meshes as the initialization of the new meshes.Secondly,to address the intersecting triangles that arose during the morphing process,we designed the alpha wrapping algorithm with topology-adaptive parameters.The algorithm ensured that the genus of the outer hull of the voxelized morphed meshes and the genus of the results remained the same,generating approximate meshes from the morphed meshes with no intersecting triangles,satisfying watertightness and two-manifold.Finally,an improved edge collapse algorithm was applied and generated meshes that were simplified to users target facet count.The algorithm optimized the contraction of vertex pairs on planes.We evaluated our methods robustness and effectiveness against a dataset of building models and compared it against popular and state-of-the-art methods.Keywords:mesh simplification;triangle mesh;low-poly mesh generation;level of detail;building model 建筑模型作为一类重要的数字模型，在虚拟场景构建中起到了关键作用。一般来说，在游戏和三维导航等移动端图形应用中，一个城市场景中可有数百个不同形状的建筑模型，但在一个屏幕上渲染这些高精度的模型需要计算上万个三角形。由于移动平台的计算能力有限，对于这些实时应用场景而言，计算是非常昂贵的。实际上，建筑模型作为一类静态模型，在参与渲染时通常被采用多细节层次(level of detail，LOD)技术进行优化，距离视点近的建筑加载高精度模型参与渲染，距离视点远的建筑需加载低精度模型参与渲染。由于用户对视野远处的模型关注度较低，距离视点较远的低精度模型虽然相比于高精度模型更加粗糙，但只要其在轮廓上与高精度模型相似，用户的体验就不会明显下降且能保证加载速度和渲染速度更快。低模网格是高模网格(三角形数较多的网格，即高精度模型)的极简化版本，其具有与高精度模型相似的外观，但三角形数量要少得多，且通常只有高模网格的百分之五以下。由于移动设备的计算能力达不到个人电脑、家用游戏主机的计算能力，移动端应用中的LOD 各级模型通常比其他平台上模型的三角面数少，就其最粗粒度级别而言，模型的面数及细节保留程度与低模网格相似。因此在移动端应用中，低模建筑模型可以作为高模建筑模型 LOD 的最粗粒度细节层次使用，在提高渲染效率、提升虚拟场景响应速度上发挥重要作用。然而，建筑模型的低模网格生成具有挑战性。一般低模网格是由高模网格简化或抽象得到的。但建模者在创造高精度建筑时首要考虑的是如何提升视觉质量或如何使建筑更美观，而不关心建筑本身的几何及拓扑性质。由建模工程师创造的高精度建筑模型可能有复杂的拓扑结构和较差的几何属性，如非流形边、开放的边界、不连接的表面和退化或重叠的三角形。然而对于自动化算法，良好的几何质量和可控的拓扑复杂度才是至关重要的。不良的属性会成为低模网格生成的阻碍，一些方法不能使用，而另一些方法则会产生糟糕的结果。图 1展示了使用二次误差测度(quadric error metrics，QEM)1和 Simplygon2中的网格简化模块对具有这些属性的建筑模型进行处理而生成的网格。因为模型表面并不紧凑而是由许多不相连的网格块组成，这 2 种方法都会产生许多破碎的三角面和视觉上的洞，随着三角面数逐渐降低，视觉误差越来越大。目前，现有方法生成的建筑低模网格得到的视觉效果一般不佳或由于模型本身几何性质过差而产生各种错误，仍然需要大量的人工干预或调整。因此本文认为，为建筑模型生成低模网格是一个尚未解决的挑战性问题。本文提出了一个鲁棒的方法，用于有效地生成建筑模型的低模网格，并作为高精度模型的超低分 (a)(b)(c)(d)图 1 高模网格和不同方法生成的简化结果(a)高精度模型 10 081 个面；(b)QEM 402 个面；(c)Simplygon 402 个面；(d)本文方法 290 个面)Fig.1 A high-poly mesh and simplified results generated by different methods(a)The high-poly mesh with 10 081 triangles;(b)QEM with 402 triangles;(c)Simplygon with 402 triangles;(d)Our method with 290 triangles)766 计算机图形学与虚拟现实 2023 年 辨率替代模型在 LOD 中发挥作用。本文方法分为3 步：首先，捕捉建筑表面重要的外观特征同时忽略微小的细节，采用逆渲染的方式并根据原始模型不同角度的照片对一个新网格进行变形，以捕捉原始模型的大型视觉特征。同时针对逆渲染仅优化顶点位置而不改变网格拓扑的问题，将被变形的新网格初始化为原始网格经过体素化后得到网格的外包(The outer hull)。模型体素化的外包网格的拓扑结构可以与模型视觉上预期的拓扑结构保持一致，经过变形可得到具有期望拓扑且与原始模型相似外观的结果。逆渲染优化过程是基于外观相似度的优化，所以变形后网格不可避免地会出现大量的自相交三角形且需处理。本文设计了自适应模型拓扑的 alpha wrapping 算法3处理网格。由于变形后网格的几何属性不良，该算法的参数范围需要根据不同的模型自动调整并严格控制，以使得生成网格与模型期望拓扑相一致。Alpha wrapping 算法生成网格无相交三角形且满足水密、流形，同时能够最大程度地保留上一步变形得到的大尺度外观特征。最后，对 alpha wrapping 算法生成网格进行边收缩产生低面数的最终网格，边收缩算法针对平面上点对合并进行了数值问题的优化。在一个包含有 30 个模型的数据集上测试本文方法的效果，同时与数个代表性的商业方法和学术方法的结果进行比较，以证明该方法能够生成视觉相似性更高的低模网格。本文主要贡献如下：(1)使用模型体素化网格的外包作为被变形网格的初始网格，大大提高了面向三维重建逆渲染对不同拓扑结构模型的鲁棒性；(2)设计自适应模型拓扑的 alpha wrapping 算法，自动确定算法的合理参数，使得生成结果的亏格与变形后网格体素化后的外包亏格一致，从而得到具有正确期望拓扑的结果；(3)边收缩过程中，针对平面上点对合并进行数值问题的优化，提高合并后点位置方程的可解率，从而使得点对合并后位置最佳。1 相关工作 首先回顾网格元素约简、网格几何特征捕获和网格修复等几个方面的工作。1.1 网格元素约简 网格元素约简研究已非常成熟，其传统做法是在误差度量的引导下对网格元素进行消除，从而达到简化网格的目的，其中包括顶点约简4、顶点聚类5、边收缩1等。其误差度量都是基于几何的。在基于几何简化思想的引导下，有更多约束的框架被开发出来。LUEBKE 和 ERIKSON6基于视图对顶点聚类得到层次动态简化结果。LINDSTROM和 TURK7提出了图像驱动的简化方法，也是通过边的合并简化网格，并通过比较原模型与简化模型的图像之间的差异来确定边合并的误差。COHEN等8引入了简化包络，用于生成多边形网格的LOD。由 2 个偏移面包裹着原网格，简化在该空间内进行，并将简化网格距离原网格误差控制在用户设定的参数之内，同时保证无自相交。显然这些方法只适用于几何结构良好的网格，因为其处理网格的基础依赖于几何元素的连接关系。如果网格表面顶点有断连接的情况出现，就很难得到良好的结果。1.2 网格几何特征捕获 网格的几何特征捕获是指利用模型或模型的图像及点云，重新生成一个近似模型，一般采用三维重建的方式。COHEN-STEINER 等9提出了基于几何的变分形状近似方法，即将三角面聚类成较大的补丁，然后对补丁重三角化得到简化的网格。MEHRA 等10利用同样方法得到人造物体模型的近似。另一类方法是基于点云的三维重建工作。NAN和 WONKA11提出在建筑模型点云中提取平面原语，通过其相交得到候选面，并优化筛选得到轻量级多边形表面。BAUCHET 和 LAFARGE12将空间划分为多面体，标记多面体位于模型内部或外部，提取多面体表面得到网格。FANG 和 LAFARGE13采用一种混合方法，将从三维数据中检测到的平面依次连接并切片得到多边形网格。其共同的问题是结果的好坏非常依赖于几何原语的提取结果。而对不同的模型，从点云中提取合适数量及视觉尺度的几何原语是一件困难的事。MILDENHALL 等14将场景表示为一个神经辐射场，并重建出高质量的场景图片。在此基础上，WANG等15提出从神经辐射场中提取显式几何表示从而实现三维重建。无独有偶，文献16-18也提出了从隐式场中提取几何表示的方法。近年来随着可微渲染19的兴起，基于逆渲染的外观驱动三维重建方法20-22被提出，将新网格依据原始网格的图像进行变形，实现几何特征的捕获。但是逆渲染框架不能改变新网格的拓扑，所以不能直接运用在低模网格生成上。本文工作将围绕该问 第 4 期 岳明宇，等：三维建筑模型的低模网格生成 767 题进行探索。1.3 网格修复 网格修复是对已有的三维模型进行处理，得到几何、拓扑质量良好模型的过程。该研究领域主要包括 2 类方法23：全局修复方法和局部修复方法。全局修复方法一般通过输入网格构造中间体积表示，并重建新的网格作为输出。这种方法一般比较鲁棒，但输出网格一般是输入网格的近似结果。如文献24-25的研究都是通过占用体素网格构造中间体积表示；而文献26-27则是对体素网格编码距离模型表面的距离场的研究；除此之外，文献28通过 BSP(binary space partitioning)树分割空间体积，文献29通过四面体实现网格重建。局部修复方法只针对输入网格有缺陷的区域进行修改，一般能得到精确的模型，但由于浮点数舍入误差的存在，其结果可能并不有效，这类方法30-31一般用于修复模型表面的非流形、自相交等。在本文方法中，经过逆渲染框架变形得到的网格几何性质过差，局部修复很难取得好的效果，所以本文采用了四面体单元收缩的方式得到内外空间分割面，以作为变形后网格的近似。2 问题定义与概述 本节中，首先需要对本文处理的问题进行定义，然后对其方法进行概述。本文方法输入是高精度建筑模型 Mori，其几何质量和拓扑性质没有保证，可能是非水密的、可能有大量的顶点在几何上不连接、可能是非流形的，还有可能有面片丢失或面片翻转。本文明确目标是需生成一个满足 3 个定性要求的网格 Mtarget。首先，Mtarget的视觉外观应该与 Mori在任何远处视角下都相似。其次，Mtarget的三角形数量不应太多，一般不超过 Mori的百分之五，通常只有数百个面甚至数十个面。最后，Mtarget应具有较高的几何质量和简单的拓扑性质，如应保证水密和二流形且能将 Mori较大的视觉拓扑特征保留的同时自动将小的视觉拓扑特征去除。解决该问题流程如图 2 所示，其可分为 3 步。步骤 1.在视觉特征捕捉阶段，本文对原始模型做体素化处理，然后对体素化网格求其外包。此外包网格能够保留模型的大尺度拓扑特征。之后将此网格作为逆渲染框架的基网格(即被变形的新网格)。将原始模型的外观作为变形过程的参照，基网格被逐渐变形并恢复了原始模型的大尺度外观特征。步骤 2.由于变形后网格的几何质量较差，本文需要保留其外观特征并重建其表面。再对变形后网格做体素化处理并求外包，并将外包作为 alpha wrapping 算法生成网格的拓扑参考网格。尝试不同的 alpha wrapping 算法参数得到不同的结果，并选择与拓扑参考网格亏格一致且最精细的结果作为此步的最终结果。步骤 3.通过边收缩算法产生一个低面数的最终网格，边收缩算法针对平面上点对的合并进行了优化。产生的最终网格就是本文所求的低模网格。由于低模网格是一个相对于高模网格的笼统概念，其面数并没有明确规定，因此最终网格的面数将由用户决定。图 2 方法概览(a)原始模型，逆渲染框架的参考网格；(b)逆渲染框架的基网格，模型的体素化网格外包；(c)变形后的网格；(d)变形后的网格的体素化网格外包；(e)Alpha wrapping 算法处理后的网格；(f)简化后的网格)Fig.2 An overview of our method(a)The original model,also the reference mesh of the inverse rendering framework;(b)The base mesh of the inverse rendering framework,also the outer hull of the voxelized original model;(c)The mesh after being morphed;(d)The outer hull of the voxelized morphed model;(e)The mesh generated by alpha wrapping algorithm;(f)The simplified mesh)768 计算机图形学与虚拟现实 2023 年 3 视觉特征捕捉 给定一个高精度的建筑模型 Mori，首先要对其外观特征进行取舍，保留大尺度的特征和轮廓并去除表面细节以满足低模网格的要求。图 1 和图 2 中表面的门窗等细节对于低模网格是不必要且可忽略的，但大的建筑轮廓需要保留。在这一步需引入逆渲染技术，因逆渲染的重建功能可以满足上述需求。在一定的观看条件下，逆渲染以原始模型作为参考从而变形基网格，其具有原始模型绝大部分外观特征，而小的细节如表面的凸凹和小的把手将不会在变形中体现出来。在给定一个高精度的建筑模型 Mori，可生成一个经过逆渲染重建后的网格Mmorphed，其保留了 Mori的大尺度特征，这些特征也是本文生成的低模网格的目标特征。首先介绍使用的逆渲染框架，然后阐述关于逆渲染技术在重建方面对模型拓扑鲁棒性的改进，即如何得到每个模型的初始基网格以获得良好的变形。本文修改了文献20提出的逆渲染框架，该框架以原始模型拍摄的图像作为参考，优化基网格的顶点位置和纹理从而使基网格与原始模型具有相似的外观。本文将基网格和参考网格(原始模型)输入框架，并进行数千次的迭代以优化基网格的顶点位置。在每一次迭代中，基网格都由一个可微的渲染管道来渲染。基网格被放置在一个球体的中心，球面上有一个单点光源和一台摄像机。每一次迭代中，光源和摄像机在球面上的位置都是随机的，以保证能从任意角度观察到网格。参考网格在相同的视角和光照条件下被渲染，但用于参考网格的渲染管道可以是不可微的。之后计算相同条件下拍摄的 2 个网格的图像之间的图像域损失，以计算损失梯度，并将其传回参数，即顶点位置数据。通过随机梯度下降，基网格被逐渐变形并与参考网格的视觉相似性越来越高。值得一提的是，渲染管道被设置为双面照明，所以即使有些面片法线朝向错误，基网格也可以捕获参考网格的外观从而正确地得到变形。从实践中可发现该框架的不足之处是，原始框架使用一个球体作为基网格的初始值，而其对不同的拓扑不鲁棒。在涉及到其他种类模型(如人体、动物)重建时，由于自身拓扑的简单性，变形后的基网格都能与参考网格具有较高的视觉相似度。然而，建筑模型的拓扑本身就千变万化，镂空的结构更是非常普遍。如图 3 中的柱子就不能由球体网格通过变形得到，柱子和墙壁之间会被凹陷的三角面所填充。造成该结果的原因是逆渲染框架只会改变顶点的位置，且不会改变顶点的连接关系，即不能根据参考网格动态改变基网格的拓扑结构。球体的亏格是零，所以当原始模型有把手时，其以难被很好地变形。也就是说，如果想对一个球体网格变形重建出一个甜甜圈是不可能的。如果能根据模型的拓扑结构自动将基网格初始化为具有相应拓扑性质的网格，这将大大提高变形结果对模型拓扑的鲁棒性，从而在缺乏人工干预的情况下进行良好的变形。但建筑模型本身可能不紧凑或非流形，导致视觉上所感受到的模型拓扑性质与模型实际拓扑性质并不一致，很难得到想要的视觉上所感受到的拓扑结构特征的紧凑网格。本文通过模型体素化来解决这一问题。体素化能够表示模型的体积占用，同时捕捉大的拓扑结构特征，而模型上小的把手就会被忽略，这与低模网格生成的要求是一致的。本文将一个体素看作是一个有 12 个三角面的立方体网格，其所有体素的外表面，即外包，就是一个理想的基网格的候选。生成基网格的过程分为 2 步：首先，标记所有被模型表面占用的体素；之后，提取立方体网格的外表面。(a)(b)(c)(d)图 3 基网格的不同初始化及其得到的变形结果之间的比较(a)球体网格；(b)球体网格变形结果；(c)模型体素化网格外包；(d)外包网格变形结果)Fig.3 Comparison between different initial base meshes and the morphed results obtained from them(a)The sphere mesh;(b)The mesh morphed from the sphere;(c)The outer hull of the voxelized mesh;(d)The mesh morphed from the outer hull)第 4 期 岳明宇，等：三维建筑模型的低模网格生成 769 3.1 占用体素标记 本文提出了一个鲁棒而简单的体素化方法，该方法基于体素块和三角面之间的重叠测试，标记所有与模型三角面重叠的体素，且不关心模型内部体素的状态。本文将三维空间划分为成千上万个立方体，每个立方体代表一个体素。本文定义，如果一个体素与网格的任何一个三角形重叠，则该体素被标记为被占用。找到所有被占用的体素，就得到了网格表面的体素化结果，该体素化方法得到的网格的外包足以作为基网格的初始化网格。为了确定一个体素是否被占用，需遍历模型的每个三角面。对于每个三角面，需计算其轴对齐包围盒(Axis aligned bound box)，任何与包围盒重叠的体素都被视为潜在占用的体素。然后，对潜在占用的体素与该三角形进行重叠测试。如果一个体素和该面确实重叠，则将这个体素标记为被该网格所占用。重叠测试的方法基于由 AKENINE-MLLER32提出的分离轴定理。该定理认为对于 2 个凸多面体，如果将其投影到空间中的一条轴上，且没有重叠，那么其在三维空间中就是不相交的。在所设场景中，将体素立方体和三角形面投射到包括立方体的边向量、三角形的边向量与立方体的边向量的外积和三角形的法向量在内的 13 条轴上，测试其是否在这些轴上重叠。如果没与 13 条轴其中之一重叠，那么在三维空间中就没有重叠。最后，体素将以三角形网格的方式存储，以便下一步的外包提取。3.2 体素网格外包提取 网格外包，即输入的三角形网格的外表面，被定义为那些从无限远处可以通过一些(可能是不直的)路径到达的三角形，这些路径不与网格相交33。换言之，外包网格就是站在无穷远处也能看到的网格面，看不见的面均被剔除。现在已经有了一个封闭的用以表示模型体积占用的体素化网格，但由于该体素化过程不考虑模型内部体素，结果会产生空腔，而本文只想将最外层的封闭网格作为基网格并初始化。为了达到这个目的，需对这个网格进行紧凑化处理并求其外包。体素化网格中的立方体是离散的，必须先将所有的几何元素连接在一起：距离小于某个阈值的顶点被视为同一顶点，并合并为一个；由相同顶点组成的面被认为是同一个面，只需保留一个。当这些操作完成后，运用文献33提出的网格外包提取方法提取该紧凑网格的最外层封闭的三角面。这个封闭网格就是本文需要的体素化网格外包，并将其作为逆渲染框架基网格的初始化网格。本文使用模型体素化和提取体素化网格外包的方法为每个模型获得一个更好的初始基网格来进行变形，从而提升逆渲染框架对不同拓扑结构的适应能力。4 无自交网格生成 变形后的网格 Mmorphed能保留原始模型大尺度的外观特征，同时去除包括表面特征在内的细节尺度特征。这个网格的外观特征即是本文所求的低模网格的外观特征，接下来的任务是保持当前网格的外观，保证几何质量，降低网格的面数。对于变形后的网格，最要紧的问题是如何提升网格质量。如图 3(b)和(d)所示，逆渲染优化过程仅仅通过改变顶点位置使得其整体外观与原始模型接近，但该过程会伴随着网格三角形自相交的产生。本文尝试将基网格初始化为面数相对较少的网格，以遏制自相交的出现。但结果只能减少自相交的产生，并不能保证变形后网格无自相交。更糟糕的是，面数较少导致基网格优化过程中变形的可能性变小了(因为顶点数目少了)，变形过程中损失无法下降，从而丢失重要特征。因此本文不再刻意为逆渲染提供面数不足的基网格，而聚焦于如何处理变形产生的相交面。通过本文实验发现很难直接修复网格。如通过Delaunay 三角剖分处理相交面33，之后再求其外包。但这样做会使得网格存在非流形边或非流形顶点。同时发现该网格的几何特性过差，且难对其进行局部网格修复，保留网格外观而重建网格可能是简单而有效的思路。文献3提出的 alpha wrapping算法可鲁棒且快速地计算输入网格的近似网格，并生成近似网格以保证是二流形且水密的。该算法将近似网格初始化为包裹输入网格的粗糙网格，然后细化粗糙网格从而逐渐收缩包裹空间，使粗糙网格外观接近输入网格，形成最终的近似网格。全过程中，近似网格将输入网格严格包裹在内部，算法通过近似网格逼近输入网格且避免近似网格与输入网格相交达到 2 个网络外形近似的效果。Alpha wrapping 算法能够根据 Mmorphed的外观重建一个几何质量优秀的网格 Mwrapping，只要保证 Mwrapping与Mmorphed足够近似即可。自适应网格拓扑的算法参数确定。对于该算法，粗糙网格收缩的过程是通过交错进行雕刻和细化 2 步骤完成，且由用户提供的参数来控制停止。770 计算机图形学与虚拟现实 2023 年 对于初始化，网格的一个松散包围盒(比严格的AABB 包围盒大一些)的 8 个顶点被插入到三维Delaunay 三角剖分中而生成若干个四面体单元。三角剖分外部空间被虚拟四面体单元填充，所有的虚拟四面体将被初始化为外部单元，三角剖分内的单元被初始化为内部单元。对于收缩过程，通过洪泛法遍历所有单元，找到所有外部单元和与其相邻的内部单元所共享的面，判定这些面是否为 可通过的(Alpha-traversable)面。如果某个被共享的面是 可通过的面，那么内部单元就会被标记为外部单元。一个面是 可通过则指三角形面的最小空Delaunay 球的半径大于用户定义的参数。对于将被标记为外部单元的内部单元而言，如果没有满足算法关于 Steiner 点插入的条件，其将被雕刻步骤标记为外部单元；反之，则进行细化步骤。细化步骤会将一个位于偏移面上的 Steiner 点插入到Delaunay 三角剖分中，将内部四面体单元细分。偏移面是一个到输入网格的无符号距离场，以保证输入网格在整个雕刻和细化过程中被包裹起来且不会暴露。当没有 可通过的面时，程序停止，生成网格由分离内外单元的三角面所构成。在这个过程中，有 2 个参数控制着近似网格Mwrapping与输入网格 Mmorphed之间的相似程度。一个是，控制一个面是否为 可通过。另一个是偏移量，定义偏移面与输入网格之间的距离。就参数 而言，其控制着近似网格与输入网格之间的紧密程度，本文希望近似网格在一定程度上紧紧地包裹着输入网格，所以对于所有输入网格而言，其可是一个固定值。只要 足够小，偏移面与输入网格之间的距离足够小，就适用于所有输入网格。但参数 并不易确定。理论上，越小，四面体单元间 可通过的面就越多，近似网格越接近输入网格，输出网格的三角面越小，更多细节被刻画出来，得到更精细的结果。但是，alpha wrapping 算法的输入网格 Mwrapping在几何质量上过差。在 Mwrapping表面上许多三角形堆叠在一起从而在视觉上形成一个平面。如果三角形堆叠地不紧，视觉平面上就会有缝隙(这在变形中同样无法避免)，较小的 会导致算法中的收缩过程通过缝隙进入网格内而开始刻画网格内部，从而改变输出网格的拓扑结构，这显然不是本文想要的。而且，不同模型得到变形后的网格表面缝隙的宽度不一，对不同的模型，正确且理想的 值是不同的。本文希望对于不同的模型，算法有能力自动选择适当的 值，保证输出网格具有正确的拓扑结构且结果更精细。由于网格内部三角形折叠在一起而导致内部结构很复杂，如果 足够小且对网格的内部进行了雕刻，输出的网格通常与预期结果的拓扑不同，具有与预期不符的亏格(图 4)。图 4(a)中的网格亏格与本文期望一致；从外观上很难区分图 4(b)(d)，但只有图 4(b)与(a)有相同的亏格，图 4(c)和(d)均出现了雕刻内部结构而拓扑改变的情况。因此，可通过计算网格的目标亏格来确定 合适的范围。只要知道 Mmorphed的亏格的预期值，并通过将 Mwrapping的亏格与该预期值进行对比，并判定其是否一致，就能知道 是否合适。如果网格的内部被雕刻了，会导致亏格数比网格的预期亏格数大，因为更多、更复杂的拓扑结构被刻画了出来。通过该方法，可以得到 的一个下限范围，只要 不小于这个下限范围，就能得到正确的输出网格。而得到网格亏格的期望值的方式也是通过体素化，因体素化对网格拓扑结构具有良好的捕获能力。对于变形后的网格，需再次提取其体素化网格的外包(方法与 3.1节和 3.2 节所述相同)。这里不直接使用模型的体素化网格的外包是因为经过变形，2 个外包的拓扑可能会不同(小的特征在变形中已经被去除)。然后通 (a)(b)(c)(d)图 4?取不同值的结果(a)变形后网格的体素化网格的外包，亏格为 8；(b)=d/190，=d/10000，亏格为 8；(c)=d/200，=d/10000，亏格为 10；(d)=d/210，=d/10000，亏格为 10。d 是网格的包围盒的对角线长度)Fig.4 The result of the different values of?(a)The outer hull of the voxelized morphed mesh;(b)The result with=d/190&=d/10000,and the genus is 8;(c)The result with=d/200&=d/10000,and the genus is 10;(d)The result with=d/210&=d/10000,and the genus is 10.d is the diagonal length of the bounding box of the mesh)第 4 期 岳明宇，等：三维建筑模型的低模网格生成 771 过 Euler 公式34计算当前变形后网格的期望亏格为 12VEFg (1)其中，V，E和F分别为网格上的顶点、边和面的数量；g为亏格数。Alpha wrapping算法生成的输出网格应该具有与体素化网格外包相同的拓扑结构，即具有相同的亏格。本文在一个适当的范围内寻找的最佳值：测试中通常有十几个作为备选，在Mwrapping的亏格与体素化网格外包的亏格一致的前提下，取最小的作为最终值。并取该值下的结果作为无自交网格生成的输出结果。5 简化网格生成 对网格的表面进行了重建后，这些网格具有与原始模型相似的外观的同时又有着优秀的几何质量。接下来只需要将网格的面数减少到一个理想的范围内。经过前两步的网格处理，边收缩算法有能力简化当前的网格，从而满足本文要求。本文基于QEM进行边收缩，并修改传统QEM的公式以解决平面上边收缩所产生的数值问题。对于传统的QEM，假设P是一个三角形所在的平面，该平面满足 22201axbyczdabc(2)则一点T,1,xyzvv v v到P的平方距离是vTQPv，其中，QP是平面P的二次误差测度矩阵，满足 2222PacadaabbcbdabbacbcccdadbdcddQ(3)QEM算法定义一个顶点的二次误差测度矩阵是与该