基于GPU并行优化的网格参数化算法-AET-电子技术应用

基于GPU并行优化的网格参数化算法

2020年信息技术与网络安全第9期

吴璇，张举勇

中国科学技术大学数学科学学院，安徽合肥230026

摘要： 网格参数化是计算机图形学、数字几何处理领域的研究热点，在动画、医疗、工业设计等领域中都发挥着重要作用。现有参数化方法主要思路是构造一个高度非线性的全局优化问题，因此计算效率低，难以并行。提出了一种可并行、可扩展的参数化算法。该算法通过引入辅助变量。然后使用交替方向乘子算法(Alternating Direction Method of Multipliers，ADMM)，迭代优化每个面和每条边上的子问题得到参数化映射。为了验证算法模型的高效性，使用GPU加速，相比于现存单线程算法，本文算法因为高度并行化运行时间缩短了至少百倍以上。

关键词： 并行计算交替方法乘子法网格参数化优化算法

中图分类号： TP391
文献标识码： A
DOI： 10.19358/j.issn.2096-5133.2020.09.004
引用格式：吴璇，张举勇. 基于GPU并行优化的网格参数化算法[J].信息技术与网络安全，2020，39(9)：16-23.

Mesh parameterization based on GPU parallel optimization

Wu Xuan，Zhang Juyong

School of Mathematical Sciences, University of Science and Technology of China，Hefei 230026，China

Abstract： Mesh parameterization is a research hotspot in the field of computer graphics and digital geometry processing. It plays an important role in animation, medical treatment, industrial design and other fields. Existing methods formulate this problem as a global optimization problem. Due to its high nonlinearity and global optimization of the model,it is very difficult to solve efficiently and parallelize. This paper presents a parallel and scalable algorithm for mesh parameterization. The proposed method solves this problem by introducing a set of auxiliary variables.Then using ADMM(Alternating Direction Method of Multipliers), this problem can be easily solved by optimizing small problems for each face and each edge iteratively. To verify the efficiency of the proposed method, we implement the proposed algorithm via GPU,reduce the running time by at least 100 times compared with single thread implementation due to the high parallelism of the proposed algorithm.

Key words : parallel computing；ADMM；mesh parameterization；optimization algorithm

0 引言

三维模型是一种使用三维曲面来表述物体的三维数据，网格是三维模型中一种应用广泛的表达方式。随着数字几何处理技术的发展以及扫描技术的进步，网格模型得以广泛应用于动画、游戏、建筑、医疗、工业设计等行业。网格曲面参数化是流形曲面和参数域之间的一一映射，是网格处理领域中不可或缺的基础工具，在网格变形、纹理映射、网格压缩中都发挥着重要作用。通常网格是在3D空间中的二维曲面，直接对于3D模型进行网格处理非常复杂，通过一一映射到简单的参数域，得到的参数化结果与原始网格有相同的拓扑结构以及尽可能小的失真，然后在参数域上进行网格处理，极大地降低了处理难度。

一个高质量的参数化映射f有以下性质：无翻转、低失真度量。无翻转意味着detJ(f)>0，这里J(f)是f的雅各比矩阵。理想中的映射是在映射后网格与初始网格之间没有形变，但这只是理想情况，一个高质量的网格需要尽量减少形变，而失真度量就是用于衡量映射形变的数值。

经典的参数化方法主要分为线性方法与非线性方法两种。线性方法计算简单，可扩展性强，因为线性方法通过计算一个线性系统来得到参数化结果。虽然线性方法在计算效率上占据优势，但是有许多方法都必须固定边界，无法获得自由边界的参数化结果，比如针对拓扑圆盘，FLOATER M^[1-2]通过把边界固定到一个凸多边形上，同时所有权重都保证为正数，得到一个无翻转的参数化结果。自由边界的方法可以通过虚拟边界、增添线性方程来实现。自由边界方法通常可以减少固定边界造成大的变形扭曲，却不一定确保得到的映射是无翻转的。非线性方法通常构造出一个以变形能量为目标式，包含无翻转硬约束的全局优化问题^[3-4]，使用牛顿法、高斯牛顿法等优化算法降低参数化网格的变形能量，这些能量函数描述了参数化映射后网格的变形、失真程度，通常是高度非线性、非凸的，所以这些方法计算效率低，而且在处理大型网格时，非线性方法通常会随着所处理网格的增大，收敛速度极大地降低。

为了解决以往参数化方法运算消耗大、运算效率低、非并行、可扩展性差的缺陷，本文提出了一种可并行、可扩展计算无翻转、高质量参数化网格的算法。不同于以往算法构造出一个无法并行的全局优化问题，本文算法通过引入辅助变量，把参数化问题分解为每个面上，每条内边上的局部子问题。该算法的空间复杂度与网格模型规模成线性关系，也就是4N+2|ε_int|，其中N是网格的面数，|ε_int|是网格内边条数。相比于现存算法不可并行性，本文算法最大创新点在于每次迭代都可以并行处理N个关于三角面片上映射的子问题以及|ε_int|个关于内边相容性约束的子问题。实验显示相比于现存算法，本文算法最终得到相同甚至更好质量网格所需运算时间缩短了至少百倍以上。随着扫描技术的飞快发展，3D网格模型的规模越来越大，可扩展的网格参数化算法意义重大。但计算大规模网格的无翻转映射是一个具有挑战性的难题，该算法可扩展，长于处理大型网格模型。

本文详细内容请下载:http://www.chinaaet.com/resource/share/2000003087

作者信息:

吴璇，张举勇

(中国科学技术大学数学科学学院，安徽合肥230026)

原创声明：此内容为AET网站原创，未经授权禁止转载。

相关内容