闭合三角网格的分割与保角参数化.pdf

1 闭合三角网格的分割与保角参数化闭合三角网格的分割与保角参数化1 付妍 周秉锋 北京大学计算机科学技术研究所 北京 100871 E mail fuyan 摘摘 要 要 对闭合三角网格进行切割与参数化是很多应用的基础 本文提出了一种自动将网格 切开并参数化到二维平面域的方法 该算法主要通过对模型初始切割线进行逐步优化来得到 模型切割线 整个优化过程由一个与参数化扭曲度和合法性相关的成本函数来控制 并针对 不同的应用定义了不同的成本函数 为了减小参数化带来的扭曲 本算法不事先确定参数域 的边界而是根据切开后的模型的形状自动地确定网格的边界 实验表明 本算法通过优化切 割线和参数化域边界有效地降低了扭曲 并保证了参数化结果的合法性 关键词 关键词 网格分割 网格参数化 自然边界 中图分类号 中图分类号 TP 391 1 引引 言言 在很多领域中所使用的模型都是通过三角形表示的流形网格 在诸如纹理映射 交互绘 图 网格重建等应用中为了方便处理 通常需要将原始网格转换到平面中 平面参数化通过 寻找一个分段线性函数以建立网格顶点与平面中一系列点之间的映射关系 有了三维网格与 二维网格之间的一一映射关系 在平面上进行的操作可以被映射回三维网格中 从而减小了 网格编辑的复杂性 然而 一个任意的封闭网格模型不能直接被参数化到平面域中 为了进 行任意封闭网格的平面参数化 通常需要先需要寻找合适的边集以将模型分割成一个或若干 个与圆盘同胚的区域 在参数化的过程中 最理想的参数化要求参数化之后平面网格中的每条边都与原始网格 的边等长 即三角形的形状和面积完全不发生改变 然而只有可展开表面 developable surfaces 如圆柱面和三角锥 能满足这个要求 对于其他的一般网格 参数化势必会引入扭 曲 1 在参数化的研究中 研究者都致力于研究如何尽量减小参数化引入的扭曲 对于一 给定面片 扭曲度由参数化方法的性质所决定 对于一个三维网格 为了参数化到平面上 仅仅将它切分成与圆盘同胚的区域是不够的 复杂的面片还需要通过优化切割线来减小网格 参数化后的整体扭曲 若网格上的切割线将模型切分成过多的区域 容易导致各个参数域之 间的不连续性 在应用中需要进行特殊的处理 并且在映射回三维空间时可能会出现明显的 缝合迹象 因此应尽量减小分割后所得面片的个数 此外 参数域边界的选择也对整体扭曲有很大的影响 在很多的平面参数化方法中 都 要求参数域的边界事先被固定 较常用的选择是正方形边界 圆形边界或凸多边形边界 在 大部分情况下 这些选择都能满足要求 但是选择凸边形和圆的问题在于 当表面 S 与一个 凸多边形或圆的形状并不相似的时候 将产生很大的扭曲 为了避免这种扭曲 研究者提出 可以建立一个 虚拟边界 virtual boundary 2 即在边界的周围添加一些三角形从而构成一 个具有很好的边界的扩展网格 之后再以凸多边形为边界进行参数化 但更自然的方法是采 用自然边界 即在参数化时并不需要事先固定边界点的位置 而且也不要求边界一定为凸的 而是在参数化的过程中产生一个自然的边界 这样产生的边界扭曲相对于固定边界参数化方 法产生的扭曲通常会相对更小 1 3 4 1本课题得到国家自然科学基金 60573149 的资助 2 因此 在本文中 我们提出了一个任意封闭三角网格的分割与参数化的方法 网格模型 被切开后仅形成一个面片以减少多个区域参数化的不连续性和缝合的复杂性 将切割所得的 面片保角参数化到具有自由边界的参数域中 以减小参数化带来的扭曲 模型切割线的优化 过程通过一个与扭曲度和合法性相关的成本函数来控制 以在此过程中保证模型参数化的合 法性 2 相关工作相关工作 研究者已经提出了很多任意网格的分割方法 Bennis 5 通过不断交互选择模型切割线迭 代地将模型中的与切割线相邻的面展平到平面上直到达到指定的扭曲率 Sorkine 等人 6 的 方法与该方法思想类似 但是定义了新的扭曲度量 而且切割线可以在算法中通过加入模型 展平停止条件自动地产生 Maillot 等人 7 是根据模型的属性例如法线和曲率等信息将具有 相似属性的区域聚集成一块区域从而形成对整个模型的分割 然后再通过最小化所定义的扭 曲度量能量将每个区域展平到平面中 这样的方法往往对分割后的面片的拓扑结构没有保 证 Eck 等人 8 和 Lee 等人 9 通过网格简化操作来构建模型的基网格 base mesh 基网 格中三角形的边映射回原始网格即构成了对整个模型的区域分割 在各个区域 分别采用谐 映射 harmonic map 的方法将原始网格映射到基网格的三角形中 Sander 等人 10 采用的方 法是先用一个贪心法的面片合并的算法来将模型切分成若干个子面片 初始时每个三角形为 一个面片 如果各面片合并带来的成本函数 用平面度和紧凑性来衡量 小于某一个阈值的 话则合并面片 最终将模型切分成若干较平的区域 然后通过松弛法将面片参数化到平面中 这种方法中产生的面片过多 不利于后续处理 为了降低参数化扭曲度 Sheffer 4 提出了 一个网格切割方法 她认为由于扭曲度主要以来于表面的高斯曲率 因此 可以使切点通过 高斯曲率较大的地方以减小扭曲 切割线通过构造切点之间的最小生成树来得到 在参数化方面 很多研究者都假定模型已经被切割开 仅研究如何将单个面片参数化到 平面中 使参数化引入的扭曲尽量小 Floater 11 首先提出了通过凸组合的重心坐标法可以 将模型嵌入到平面中 该方法只需要通过解一组线性方程组即可得到三维顶点在二维平面中 的映射坐标 但是 该方法要求参数域的边界被事先固定 而且边界必须为凸的 若边界选 择不当 则可能引入较大的扭曲 Eck 等人和 Lee 等人采用的参数化方法对边界也有同样的 要求 Levy 和 Mallet 12 通过定义一系列非线性的限制以保证参数化后的角度不变 通过 固定两个顶点 该算法也可以简化成解一组线性方程组 Hormann 1 提出的最等长参数化方 法 Most Isometric Parameterization 方法则不需要事先固定边界 他通过最小化一个非线性能 量函数来得到最后的映射结果 速度比较慢 因此后来 Hormann 又提出了一个分层的算法 来解决这个问题 13 Sheffer 等人 14 也定义了一系列仅与角度相关的非线性限制条件以保 证映射后的角度不变形 但该算法最后也可能会产生自折叠 需要进行一些后处理以消除折 叠 Desbrun 等人 3 提出了可用的扭曲度量的集合 并定义了离散保角映射和 Chi 能量以达 到参数化保角和保面积的目的 这两种能量最小化方法最后都可以归结为解一组线性方程 并被推广到自然边界的参数化 Levy 等人 15 基于对 Cauchy Riemann 等式的最小平方逼近 定义了一个目标函数以最小化角度扭曲 边界也可以在最小化的过程中被自然地确定 该方 法在理论上与 Desbrun 等人的方法是等价的 Gu 等人 16 是基于模型参数化引入的扭曲逐步 地对切割线进行优化的 并最终将模型参数化到一个正方形中 但该方法中由于也必须强制 参数域边界为正方形边界 所以对于实际展开结果与正方形差距较大的情况下扭曲较大 本 文的思想与 Gu 的思想类似 但是采用了不同的参数化方法使得模型最终被参数化到一个平 3 面中的自由区域 并定义了一个新的成本函数以控制切线的优化和模型参数化结果的合法 性 3 具有自然边界的保角参数化具有自然边界的保角参数化 Eck 8 等人指出谐映射 Harmonic mapping 在保持平面嵌 入的性质下能试图保持三角形的形状 使扭曲最小化 在离散 情况下 谐映射的最小化问题可以转化为解如下线性方程组的 问题 17 在边界点固定的情况下 对于每个内部点有 i Nj jiijij vv0 cot cot 1 其中 ij 和 ij 如右图所示 为了将拓扑结构与圆盘相同的网格参数化到无限定边界的平面域中 我们采用了 Desbrun 等人提出的具有自然边界的保角参数化方法 3 该方法通过解一个线性方程组来找 到最好的边界 Desbrun 等人证明了一个三角形的 Dirichlet 能量 对它其中的一个顶点 v 的导数等于该顶点对应的边旋转 90 度 因此 对于网格中的每个点的邻域都有 ijkijk jkkiji uuRuuuu cot cot 90 2 其中 和 为顶点 k 和 j 所对应的角度 01 10 90 R 对于内部顶点 等式右边为 0 与等式 1 一致 因此 内部顶点依然为它周围顶点的凸 组合 保证了内部顶点邻域局部的合法性 该算法不能保证在任何时候都得到合法的平面嵌 入 但是我们在下一节将通过成本函数控制参数化过程以阻止不合法情况的产生 由于整个参数化过程只需要解一个线性方程组 因此该方法从速度上来讲是非常快速 的 在实现时 为了固定参数域的位置和方向 需要先任意固定两个顶点 选取不同的固定 点以及他们的位置不同将导致不同的参数化结果 4 成本函数定义成本函数定义 为了控制模型的切割与参数化过程 我们定义了与模型切割和参数化过程相关的成本函 数 与每个三角形 i T 相关联的成本函数可以定义如下 C M L M P M 3 其中 C M 为由当前切线切割所得模型参数化到平面之后的成本函数 L M 用来衡量网格被参数化到平面后所引入的扭曲 P M 用于保证平面参数化的合法性 L M 和 P M 的定义分别如下 在 10 中 Sander 等人定义了一种扭曲度量方法 它用来衡量参数化对纹理信号的采样 精细程度 也可以看成是定义在参数域进行均匀采样时重构出来的网格与原始网格的差距 参数化 23 RRf 相当于在参数化前后的三角形之间建立仿射变换 对网格中的每个三维 ij ij vj ui uk uj vi 4 三角形到一个二维三角形的映射 iii tTf 可以表示成 bxAxg 在 i T 处引入一个 局部坐标系 则矩阵 A 为 2 2 的 对 A 进行奇异值分解 2 1 0 0 AVU T 其中 21 4 即该仿射变换的扭曲主要可以通过其雅可比矩阵的奇异值来近似衡量变换引入的扭曲 对于纹理映射等应用 三角形面积的保持非常重要 因此 扭曲度应该将三角形的尺度 缩放也考虑在内 因此 几何拉伸的量度可以定义为 2 2 2 2 1 2 1 TL 5 基于这个度量空间 整体网格的参数化变形可以定义为 MTMT ii ii TATATLML 2 2 1 2 1 6 为了方便在不同参数域进行比较 扭曲度量可以通过乘以以下因子来归一化 MT i MT i ii TATA 即参数化后整个参数域的面积和原始网格面积之比 其中 i TA 为三角形 i T 在 3D 空间中的面积 i TA 为三角形 i T 在 2D 空间中的面积 在除了纹理映射的一些其他应用 例如有限元分析中 扭曲度量可能仅仅需要考虑三角 形形状的扭曲 而忽略三角形大小尺度的变化 在这种情况下 几何拉伸的量度可以定义为 2 1 2 2ii TATATL MTi TLML 2 2 2 2 2 7 即通过每个三角形的拉伸和压缩比来表征三角形变形程度 并对每个三角形的拉伸度量 都进行归一化 整个三角网格的扭曲度表示为各三角形拉伸度量的平 方和 我们采用的参数化方法仅对内部点能保证其合法性 而计算所得 的边界可能会重叠 由此导致了三角形的重叠 fold over 如图 1 所 示 为了避免产生不合法的平面嵌入 我们在成本函数中加入 P M 在每次参数化之后 我们检查平面参数化之后的结果中是否有重叠情 况出现 如果有重叠情况出现 则 P M 的值为无穷大 否则为零 由于在合法嵌入的情况下 每个顶点仅仅落在它的邻点的中心 因此 我们通过判断是否存在一个点落在它的邻域之外的三角形内部来判断是否发生了重叠现象 若存在这种点 则说明有重叠情况出现 5 算法流程算法流程 闭合三角网格切割与参数的整个流程包括以下步骤 1 寻找初始切割线 Cut0 2 初始网格参数化 计算此时的成本函数 C0 3 寻找参数域中扭曲最大的一个三角形 T 4 在模型边集中找到当前切线到 T 中的一个顶点的最短路径 将该段路径添加到切线 集合中 得到新的切线集合 Cutnew 5 计算此时成本函数 Cnew 如果成本函数小于初始成本函数 返回到 3 如果成 图 1 折叠情况 5 a d i h c b f g e 图 3 切割线展开 本函数大于初始成本函数 优化过程结束 一个亏格为 g 的模型 最少用 2g 个环可以将模型切开成一个与圆盘拓扑结构相同 的面片 我们采用的是 Gu 等人 16 中寻找初始切割线的方法 图 2 为用该算法对亏格分 别为 0 1 2 的模型找到的初始切线 图 2 对不同亏格模型提取的初始切割线边集 获得初始切线之后 需要将切割线展开成一个环 以将这个 环作为参数域的边界 在这个环中 边界切线出现一次 其他切 线各出现两次 即一条切线 c 将被拆分成 c c 例如 对于如图 3 的切线边集 展开后的环为 a b c b d e f e g e d h d b i b a 假定模型的法线方向都朝里或朝外 算法的基本思想是对于每一 个结点 连接大于两条切线的点 都按一个固定方向 顺时针或逆时 针 遍历与之连接的切线顶点 并由此深入遍历子切线边集直到 到达端点 类似于树遍历中的深度优先法 在找扭曲度最大的三 角形时 对于不同的成本函数 应采用相应的扭曲度量来确定扭 曲度最大的三角形 在找当前切割线到这个三角形中某一个点的最短路径时 需要以切割线 上的每个点为起点都进行尝试 以找到最短路径 6 实验结果及分析实验结果及分析 图 4 显示了我们的算法对不同的闭合网格模型进行切割再参数化之后得到的效果 从图 中可以看出 我们的算法较好地保持了原始模型的角度 而且保证了参数化的合法性 为了便于比较 我们分别实现了将网格模型参数化到正方形域和圆形域与非固定边界等 三种情况 结果对比如图 5 所示 从扭曲度来看 本文的算法的扭曲度明显低于参数化到前 两种参数域的情况 6 图 4 模型切割和参数化结果示例 第一行为原始模型 第二行所示为切开并参数化之后的模型 a 原始模型 b 参数化到正方形域 L 42 4237 c 参数化到圆形域 L 21 4589 d 不固定边界参数化 L 14 8588 图 5 将模型参数化到不同参数域的比较 图 6 是对球模型采用不同的拉伸度量和成本函数进行切割和参数化后得到的结果 图 a 为采用 L1 扭曲度量所得的结果 即在参数化的过程中将三角形的大小及形状变化都考虑在 内 该结果尽量保持三角形大小都相同 而图 b 为采用 L2 扭曲度量所得的结果 在参数化 的过程中不考虑三角形的大小变化 它只尽量保持三角形的形状不发生改变 从图 6 中的结 果中可以看出我们定义的成本函数有效地对参数化的结果进行了控制 a 采用 L1 扭曲度量 b 采用 L2 扭曲度量 图 6 对球模型采用不同的成本函数所得的不同切割线和参数化结果 通过实验 我们还发现 在参数化的过程中 固定的边界顶点位置不同将导致不同的参 数化结果 如图 7 所示 7 a b c d 图 7 分别对 sphere 和 sphere2 两个模型进行切割和参数化 当初始固定的两个顶点不同时所得的结果不同 a b 为对 sphere 切割和参数化后的结果 c d 为对 sphere2 切割和参数化后的结果 7 结论结论 本文提出了一个对闭合三角网格模型进行分割和参数化的算法 模型的切割线通过对模 型的初始切线进行不断优化得到 优化过程通过一个与参数化的扭曲度和合法性相关的成本 函数来控制 以模型的切割线为边界将整个模型参数化到没有固定边界的平面域中 同时模 型的切割线由参数化的结果进行引导优化 该算法与固定边界的参数化相比 减小了参数化 带来的扭曲 并保证了参数化的合法性 但是对于复杂物体 要将整个物体切割开然后展开 到一个面片中带来的扭曲总是很大的 8 参考文献参考文献 1 Hormann K and Greiner G MIPS An Efficient Global Parameterization Method In Curve and Surface Design Saint Malo 1999 Vanderbilt University Press pp 153 162 1999 2 Lee Y Kim H S and Lee S Mesh parameterization with a virtual boundary Computers Vezien J Cohen Or D Goldenthal R et al Bounded distortion Piecewise Mesh Parameterization VIS 02 Proceedings of the conference on Visualization 02 7 Maillot J Yahia H Sweldens W Schroder P et al MAPS multi resolution adaptive parameterization of surfaces SIGGRAPH 98 Proceedings of the 25th annual conference on Computer graphics and interactive techniques pp 95 104 10 Sander P V Snyder J Gortler S J et al Texture mapping progressive meshes SIGGRAPH 01 Proceedings of the