做影评的网站模版,html5网页设计作业代码,期货模拟网站开发,建立手机也可浏览的网站教程重心映射 在许多应用中#xff0c;特别是在计算机图形学中#xff0c;现在通常使用三角形网格形式的分段线性曲面工作#xff0c;在本课程笔记的剩余部分#xff0c;我们将主要坚持使用这种类型的曲面。
3.1 三角形网格 如前一章所述#xff0c;让我们用 $ p (x,y,z) $ …重心映射 在许多应用中特别是在计算机图形学中现在通常使用三角形网格形式的分段线性曲面工作在本课程笔记的剩余部分我们将主要坚持使用这种类型的曲面。
3.1 三角形网格 如前一章所述让我们用 $ p (x,y,z) $ 表示 $ \mathbb{R}^3 $ 中的点用 $ u (u,v) $ 表示 $ \mathbb{R}^2 $ 中的点。边则定义为两个不同点的凸包或等价地两点之间的线段三角形定义为三个非共线点的凸包。我们将用大写字母表示 $ \mathbb{R}^3 $ 中的边和三角形用小写字母表示 $ \mathbb{R}^2 $ 中的边和三角形例如$ e [u_1, u_2] $ 和 $ T [p_1, p_2, p_3] $。
三角形网格 $ S_T $ 是一组表面三角形 $ T {T_1, …, T_m} $ 的并集这些三角形仅在公共边 $ E {E_1,…,E_l} $ 和顶点 $ V {p_1,…,p_{nb}} $ 处相交。具体来说顶点集由 $ n $ 个内部顶点 $ V_I {p_1, …, p_n} $ 和 $ b $ 个边界顶点 $ V_B {p_{n1}, …, p_{nb}} $ 组成。如果两个不同的顶点 $ p_i, p_j \in V $ 是某条边 $ E [p_i,p_j] \in E $ 的端点则称它们为邻居对于任何 $ p_i \in V $我们用 $ N_i {j : [p_i,p_j] \in E} $ 表示 $ p_i $ 所有邻居的索引集。
$ S_T $ 的参数化 $ f $ 通常以相反的方式指定即通过定义逆参数化 $ g f^{-1} $。这个映射 $ g $ 通过为每个顶点 $ p_i \in V $ 指定参数点 $ u_i g(p_i) $ 来唯一确定并要求 $ g $ 对每个三角形连续且线性。在这种设置下$ g|_T $ 是从表面三角形 $ T [p_i,p_j,p_k] $ 到相应参数三角形 $ t [u_i,u_j,u_k] $ 的线性映射$ f|_t (g|_T)^{-1} $ 是从 $ t $ 到 $ T $ 的逆线性映射。参数域 $ \Omega $ 最终是所有参数三角形的并集见图3.1。
3.2 仿射组合参数化
构建三角形网格参数化的一个相当简单的想法基于以下物理模型。想象三角形网格的边是弹簧它们在顶点处连接。如果我们现在将这个弹簧网络的边界固定在某个平面上那么这个网络的内部将会在能量上松弛。 在能量最高效的配置中我们可以简单地将网络关节所达到的静止位置指定为参数点。
如果我们假设每个弹簧都是理想的即静止长度为零势能仅为 $ \frac{1}{2}Ds^2 $其中 $ D $ 是弹簧常数$ s $ 是弹簧长度那么我们可以将这种方法形式化如下。我们首先以某种方式参见3.4节为网格的边界顶点 $ p_i \in V_B $ 指定参数点 $ u_i (u_i,v_i) i n 1,…,n b $。然后我们最小化总弹簧能量
$ E \frac{1}{2} \sum_{i1}^n \sum_{j\in N_i} \frac{1}{2}D_{ij}|u_i - u_j|^2 $
其中 $ D_{ij} D_{ji} $ 是 $ p_i $ 和 $ p_j $ 之间弹簧的弹簧常数关于未知的内部点参数位置 $ u_i (u_i, v_i) $。由于 $ E $ 关于 $ u_i $ 的偏导数是
$ \frac{\partial E}{\partial u_i} \sum_{j\in N_i} D_{ij}(u_i-u_j) $
$ E $ 的最小值在
$ \sum_{j \in N_i} D_{ij}u_i \sum_{j \in N_i} D_{ij}u_j $
对所有 $ i 1, \ldots, n $ 成立时获得。这等价于说每个内部参数点 $ u_i $ 是其邻居的仿射组合
$ u_i \sum_{j \in N_i} \lambda_{ij}u_j $
其中归一化系数
$ \lambda_{ij} \frac{D_{ij}}{\sum_{k \in N_i} D_{ik}} $
显然和为1。 注释1额外的因子 $ \frac{1}{2} $ 出现是因为以这种方式对边求和会导致每条边被计算两次。 通过在(3.1)式右侧的求和中分别分离出内部与边界顶点的参数点我们可以得到
$ u_i - \sum_{j\in N_i, j \leq n} \lambda_{ij}u_j \sum_{j\in N_i, j n} \lambda_{ij}u_j $
因此要计算内部参数点 $ u_i $ 的坐标 $ u_i $ 和 $ v_i $我们需要求解线性系统
$ AU \bar{U} \quad \text{和} \quad AV \bar{V} \quad (3.2) $
其中
$ U (u_1, …, u_n) $ 和 $ V (v_1, …, v_n) $ 是未知坐标的列向量$ \bar{U} (\bar{u}_1, …, \bar{u}_n) $ 和 $ \bar{V} (\bar{v}_1, …, \bar{v}_n) $ 是列向量系数为
$ \bar{u}i \sum{j\in N_i, j n} \lambda_{ij}u_j \quad \text{以及} \quad \bar{v}i \sum{j\in N_i, j n} \lambda_{ij}v_j $
$ A (a_{ij})_{i,j1,…,n} $ 是一个 $ n \times n $ 的矩阵其元素为
$ a_{ij} \begin{cases} 1 \text{如果 } i j \ -\lambda_{ij} \text{如果 } j \in N_i \ 0 \text{否则} \end{cases} $ 解决这些系统的有效方法在本课程笔记的第10章中有描述。 3.3 重心坐标 问题在于如何选择弹簧模型中的弹簧常数 $ D_{ij} $或更一般地如何选择(3.1)式中的归一化系数 $ \lambda_{ij} $。最简单的选择是使用常数弹簧常数 $ D_{ij} 1 $这可以追溯到 Tutte [1960, 1963] 的工作。他在更抽象的图论设置中使用这种方法来计算平面图的直线嵌入。而 Greiner 和 Hormann [1997] 则提出了使用与三角网格中相应边长成比例的弹簧常数的想法。这两种方法的主要缺点是它们不满足我们对任何参数化方法应该期望的最低要求。
线性再现性假设 $ S_T $ 包含在一个平面内使得其顶点相对于某个适当选择的正交坐标系具有坐标 $ p_i (x_i, y_i, 0) $。那么一个全局等距因此是最优的参数化可以通过直接使用局部坐标 $ x_i (x_i, y_i) $ 作为参数点来定义即对于 $ i 1,…,n b $设置 $ u_i x_i $。由于整体参数化此时是一个线性函数我们说一个参数化方法具有线性再现性如果它在这种设置下产生这样的等距映射。 在前一节的设置中如果正确设置边界顶点的参数点并且选择 $ \lambda_{ij} $ 值使得对所有内部顶点满足
$ x_i \sum_{j \in N_i} \lambda_{ij}x_j \quad \text{和} \quad \sum_{j \in N_i} \lambda_{ij} 1 $
那么就可以实现线性再现。具有这两个性质的 $ \lambda_{ij} $ 值也被称为 $ x_i $ 相对于其邻居 $ x_j $, $ j \in N_i $ 的重心坐标。 如果某个 $ x_i $ 恰好有三个邻居那么 $ \lambda_{ij} $ 是唯一确定的这些三角形内的重心坐标在计算机图形学例如Gouraud和Phong着色射线-三角形相交几何建模例如三角形Bézier片三角剖分上的样条以及许多其他领域例如有限元方法地形建模中都有许多有用的应用。 然而对于有超过三个顶点的多边形内部点的重心坐标不再是唯一的有几种定义它们的方法。最流行的方法都可以在一个共同的框架中描述[Floater et al., 2006]我们将简要回顾。
对于任何内部点 $ x_i $ 和它的一个邻居 $ x_j $令 $ r_{ij} |x_i - x_j| $ 为两点之间边 $ e_{ij} [x_i,x_j] $ 的长度并让与 $ e_{ij} $ 相邻的三角形角点的角度如图3.2所示。然后$ x_i $ 相对于其邻居 $ x_j $, $ j \in N_i $ 的重心坐标 $ \lambda_{ij} $ 可以通过以下任何一种齐次坐标 $ w_{ij} $ 的归一化 $ \lambda_{ij} \frac{w_{ij}}{\sum_{k\in N_i} w_{ik}} $ 来计算。
重心坐标的最早推广可以追溯到Wachspress [1975]他建议设置
$ w_{ij} \frac{\cot \alpha_{ji} \cot \beta_{ij}}{r_{ij}^2} $
虽然他主要对在有限元方法中应用这些坐标感兴趣但Desbrun等人[2002]将它们用于三角网格的参数化Meyer等人[2002]将它们用于插值例如凸多边形内的颜色值。此外Ju等人[2005b]给出了这些坐标的简单几何构造。 离散谐波坐标另一种来源于有限元方法的重心坐标实际上源自对拉普拉斯方程的标准分片线性近似其形式为
$ w_{ij} \cot \gamma_{ij} \cot \gamma_{ji}. $
在网格参数化的背景下这些坐标最早由 Eck 等人 [1995] 使用但它们也被用于计算离散极小曲面 [Pinkall 和 Polthier, 1993]。
平均值坐标通过离散化平均值定理Floater [2003a] 找到了另一组重心坐标其形式为
$ w_{ij} \frac{\tan\frac{ \alpha_{ij} }{2} \tan \frac{\beta_{ji}}{2}}{r_{ij}}. $
虽然他的主要应用是网格参数化但 Hormann 和 Tarini [2004] 以及 Hormann 和 Floater [2006] 后来展示了它们在计算机图形学中还有许多其他有用的应用。
上述三种选项的美妙之处在于权重 $ w_{ij} $ 仅依赖于角度和距离因此不仅在 $ x_i $ 和其邻居共面时可以计算当这些角度和距离从围绕 $ p_i $ 的三角形中取得时一般情况下也可以为三角网格的任何内部顶点 $ p_i \in V_I $ 进行计算。Floater [1997] 提出的另一种替代方法是将围绕 $ p_i $ 的一环三角形局部展平到平面中例如使用指数映射然后从这一平面配置中计算权重 $ w_{ij} $。
通过求解带有任何重心坐标集 $ \lambda_{ij} $ 的线性系统(3.2)计算的三角网格参数化称为重心映射并且显然具有线性再现性前提是使用了适当的方法来计算边界顶点的参数点例如将它们映射到最小二乘平面见第3.4节。
尽管具有这种性质但当为非平面网格构建时重心映射可能会产生意想不到的结果正如图3.3中的简单示例所示。 如图所示如果我们使用参数点 $ u_2 (-1, -1), u_3 (1, -1), u_4 (1, 1), u_5 (-1, 1) $ 来表示四个边界顶点并用上述公式计算重心权重 $ \lambda_{12}, \lambda_{13}, \lambda_{14}, \lambda_{15} $那么我们会得到以下 $ u_1 $ 的位置
Wachspress 坐标( u_1 (-35.1369, 0) )离散调和坐标( u_1 (2.1138, 0) )平均值坐标( u_1 (0.4538, 0) )
也就是说只有平均值坐标为 $ u_1 $ 提供了一个位置该位置位于其他四个参数点的凸包内使用其他坐标将导致参数三角形重叠从而违反任何参数化都应具备的双射性特征。
这种行为的原因是 Wachspress 和离散调和坐标在某些配置如图 3.3 所示中可能取负值而平均值坐标始终为正。当权重为负时可能会发生三角形重叠但如果所有权重为正且边界顶点的参数点形成凸形则不会发生这种情况。Tutte [1963] 首次证明了这一点适用于特殊情况 $ \lambda_{ij} 1/\eta_i $其中 $ \eta_i #N_i $ 是 $ p_i $ 的邻居数虽然这不是真正的重心坐标但 Floater [1997] 观察到这种证明可以推广到任意正权重 $ \lambda_{ij} $。最近Gortler 等人 [2006] 甚至显示出对凸边界的限制可以大大放宽但这需要解决一个非线性问题。
另一个重要方面涉及线性系统 (3.2) 的可解性已证明对于离散调和 [Pinkall 和 Polthier, 1993] 和平均值坐标 [Floater, 1997]矩阵 $ A $ 总是非奇异的。然而对于 Wachspress 坐标可能发生齐次坐标之和 $ W_i \sum_{k \in N_i} w_{ik} $ 为零从而归一化坐标 $ \lambda_{ij} $ 和矩阵 $ A $ 都未定义。在图 3.4 所示的例子中这种情况实际上出现在所有内部顶点 $ x_1, x_2, x_3 $ 上。但是即便跳过归一化并尝试解决等价且定义明确的齐次系统 $ WAU W\bar{U} $ 和 $ WAV W\bar{V} $其中 $ W \text{diag}(W_1,…,W_n) $我们发现矩阵 $ WA $ 在这个特例中是奇异的即 $ W A \begin{bmatrix} 0 -50 0 \ 40 0 -24 \ 0 18 0 \end{bmatrix} $。
3.4 边界映射 构造重心映射的第一步是为边界顶点选择参数点。最简单的方法是将边界顶点投影到最小二乘意义上最适合边界顶点的平面上。然而对于具有复杂边界的网格这种简单的程序可能会导致边界多边形中出现不希望的折叠因此不能使用。一般来说这里需要考虑两个问题(1)选择参数域边界的形状(2)选择参数点在边界周围的分布。
选择形状 在许多应用中选择矩形或圆形作为参数域就足够了甚至是理想的这样的凸形状有一个优点即如果使用像平均值坐标这样的正重心坐标来计算内部顶点的参数点就能保证参数化的双射性。然而当三角网格 ST 的边界不类似于凸形状时凸性限制可能会在边界附近产生大的扭曲。避免这种扭曲的一个实用解决方案是构建一个虚拟边界即在给定网格的边界周围增加额外的三角形以构造一个具有良好边界的扩展网格。Lee等人[2002]和Kós和Várady[2003]成功地使用了这种方法。
选择分布 文献中通常提到的程序是使用简单的单变量参数化方法如弦长[Ahlberg等人1967]或向心参数化[Lee1989]将参数点放置在整个边界周围或者在使用矩形域时沿着边界的每一侧放置[Hormann2001第1.2.5节]。
尽管这些启发式方法在某些情况下效果很好但在其他情况下必须固定边界顶点可能是一个严重的限制。下一章将研究可以在优化过程中包含边界参数点位置的参数化方法从而产生扭曲更小的参数化。
小结 1. **内容概述** - 介绍了三种不同的重心坐标系统Wachspress坐标、离散调和坐标和平均值坐标。 - 讨论了这些坐标系统在网格参数化中的应用和特性。 - 分析了不同坐标系统的优缺点以及它们在特定应用场景中的适用性。 2. **作用** - 提供了一种将3D网格映射到2D平面的技术方法保持网格的拓扑结构。 - 在计算机图形学、几何建模、纹理映射等领域有广泛应用。 - 帮助减少变形和扭曲保持网格的重要特征提高渲染效果和纹理质量。
重心映射的目的 **目的** - 将复杂的3D形状转换为2D平面表示以便于处理和分析。 - 保持网格的几何和拓扑特性避免重叠和扭曲。 - 在纹理映射、形状变形等应用中提供高质量的参数化结果。
假设和方法 1. **假设** - 网格由三角形组成包含内部顶点和边界顶点。 - 边界顶点的参数点需要预先确定通常选择一个简单的形状如矩形或圆形作为参数域。 2. **方法** - 使用选定的重心坐标系统如Wachspress、离散调和或平均值坐标来计算内部顶点的参数坐标。 - 构建并求解线性方程组确定每个内部顶点相对于其邻居的权重。 - 通过优化过程减少参数化过程中的扭曲和变形。
如何找到重心 **步骤** 1. **选择边界参数点**为边界顶点选择参数点通常通过投影到一个适合的平面上。 2. **计算重心坐标**使用选定的重心坐标系统计算内部顶点的权重。 3. **求解线性系统**通过求解线性方程组确定内部顶点的参数坐标。 4. **优化和调整**根据需要调整参数化结果以减少扭曲和提高质量。
总的来说这篇文章探讨了如何有效地将3D网格映射到2D平面这是计算机图形学和几何处理中的一个基本问题。不同的重心坐标系统提供了不同的解决方案每种方法都有其优缺点适用于不同的场景。
附件 Wachspress坐标、离散调和坐标和平均值坐标是三种不同的重心坐标系统用于三角网格参数化。它们的主要区别如下
Wachspress坐标
定义基于多边形的面积比特点 仅依赖于顶点的几何位置在凸多边形内部保持正值计算相对简单 局限性 只适用于凸多边形在某些情况下可能导致奇异性如文中图3.4所示 应用主要用于几何建模和有限元分析
离散调和坐标
定义源自拉普拉斯方程的离散化特点 基于余切公式$ w_{ij} \cot \gamma_{ij} \cot \gamma_{ji} $在某些情况下可以产生负值保证非奇异性 应用 网格参数化离散极小曲面计算 优点在某些情况下可以产生较低的角度变形
平均值坐标
定义基于均值定理的离散化特点 公式$ w_{ij} \frac{\tan(\alpha_{ij}/2) \tan(\beta_{ji}/2)}{r_{ij}} $始终保持正值适用于凸和非凸多边形保证非奇异性 优点 在大多数情况下能产生合理的参数化结果不会出现重叠三角形的问题 应用广泛用于计算机图形学特别是在纹理映射和形状变形中
主要区别总结
适用范围Wachspress坐标仅适用于凸多边形而平均值坐标可用于任意多边形。离散调和坐标介于两者之间。正值性平均值坐标始终为正Wachspress坐标在凸多边形内为正而离散调和坐标可能出现负值。奇异性Wachspress坐标在某些情况下可能导致奇异性而离散调和坐标和平均值坐标保证非奇异。计算复杂度Wachspress坐标计算相对简单而离散调和坐标和平均值坐标计算稍复杂。应用领域虽然都可用于网格参数化但各有特长。例如平均值坐标在计算机图形学中应用更广泛。
选择哪种坐标系统通常取决于具体应用场景、网格特性以及对计算效率和结果质量的要求。
重心重映射的原因 重心重映射或重心映射在三角网格参数化中具有重要意义主要原因包括以下几个方面
保持拓扑结构 重心映射能够将3D网格映射到2D平面同时保持网格的拓扑结构。这对于确保网格在参数化过程中不发生拓扑改变如翻转或交叉至关重要。 减少变形和扭曲 在将3D形状映射到2D平面时重心映射方法可以帮助减少形状的变形和扭曲。这对于纹理映射、形状分析和几何处理等应用非常重要因为它们要求尽可能保留原始形状的几何特征。 提高计算效率 重心映射方法通常涉及求解线性方程组这在计算上是高效的。相比于其他可能需要非线性优化的方法重心映射提供了一种相对简单且快速的解决方案。 适应不同应用场景 不同的重心坐标系统如Wachspress、离散调和、平均值坐标适用于不同的应用场景和网格特性。通过选择合适的重心映射方法可以针对特定问题优化参数化结果。 支持复杂几何形状的处理 在处理复杂几何形状时重心映射提供了一种有效的工具来实现形状的平面化。这对于计算机图形学、动画制作、CAD设计等领域的复杂模型处理非常有用。 增强视觉效果 在纹理映射中重心映射可以帮助确保纹理在模型表面上的均匀分布避免纹理拉伸或压缩从而提高视觉效果。
总之重心重映射在三角网格参数化中扮演着关键角色帮助实现高效、准确和保形的3D到2D映射。这对于许多计算机图形学和几何处理应用来说都是不可或缺的技术。
