使用GPU渲染的离散最优传输算法
|
摘要
针对离散最优传输算法复杂实现难度大的问题,将最优传输转换成多个三维平面的渲染问题,提出一种利用GPU渲染管线以绘制四边形的方式求解的简单算法.首先根据最优传输的原像计算得到一系列三维空间中的平面;然后使用正交相机对这些平面进行渲染得到其垂直投影,并根据投影中每个胞腔的面积可以得到当前测度;接着使用梯度下降法调整平面的位置,使得当前测度等于目标测度,得到最优传输的结果;最后基于该算法构建了拓扑圆盘网格的保面积参数化算法.使用Maxplanck, Alexraw, Lion, Totoro和Buddaha模型进行实验,与使用数值法进行比较,该算法的迭代速度提升了8倍;与其他类似的算法进行对比,使用面积之比取对数作为评判指标,结果表明该算法的保面积效果更好.
To solve the problem of difficulty in implementing the discrete optimal transportation algorithm,this paper presents a simple algorithm that solve the problem by rendering quadrilateral with the help of GPU rendering pipeline. Firstly, a series of 3D plane was built from the preimage of optimal mass transportation map. In order to obtain the vertical projection, these planes were rendered using orthographic camera.Current measure can be computed from it. Then, gradient descent was used to adjust the planes' position so as to let current measure be equal to target measure, obtaining the results of optimal mass transportation.Finally, an equiareal parameterization for topological disk was constructed based on the algorithm The algorithm was evaluated on the models of Maxplanck, Alexraw, Lion, Totoro and Buddaha. Compared with the numerical method, the iteration speed of this algorithm is improved by 8 times and compared with other similar methods, taking the logarithm of ratio of area as evaluation criteria, our algorithm is more area-preserving.
To solve the problem of difficulty in implementing the discrete optimal transportation algorithm,this paper presents a simple algorithm that solve the problem by rendering quadrilateral with the help of GPU rendering pipeline. Firstly, a series of 3D plane was built from the preimage of optimal mass transportation map. In order to obtain the vertical projection, these planes were rendered using orthographic camera.Current measure can be computed from it. Then, gradient descent was used to adjust the planes' position so as to let current measure be equal to target measure, obtaining the results of optimal mass transportation.Finally, an equiareal parameterization for topological disk was constructed based on the algorithm The algorithm was evaluated on the models of Maxplanck, Alexraw, Lion, Totoro and Buddaha. Compared with the numerical method, the iteration speed of this algorithm is improved by 8 times and compared with other similar methods, taking the logarithm of ratio of area as evaluation criteria, our algorithm is more area-preserving.
引文
[1]Tutte W T.Convex representations of graphs[J].Proceedings of the London Mathematical Society,1960,3(1):304-320
[2]Floater M S.Parametrization and smooth approximation of surface triangulations[J].Computer Aided Geometric Design,1997,14(3):231-250
[3]Sheffer A,de Sturler E.Parameterization of faceted surfaces for meshing using angle-based flattening[J].Engineering with Computers,2001,17(3):326-337
[4]Hormann K,Greiner G.MIPS:an efficient global parametrization method[M]//Curve and Surface Design.Nashville:Vanderbilt University Press,2000
[5]Zhang M,Guo R,Zeng W,et al.The unified discrete surface Ricci flow[J].Graphical Models,2014,76(5):321-339
[6]Zeng M,Zhang W,Guo R,et al.Survey on discrete surface Ricci flow[J].Journal of Computer Science and Technology,2015,30(3):598-613
[7]Hamilton R S.Three-manifolds with positive Ricci curvature[J].Journal of Differential Geometry,1982,17(2):255-306
[8]Eells J,Sampson J H.Harmonic mappings of Riemannian manifolds[J].American Journal of Mathematics,1964,86(1):109-160
[9]Yoshizawa S,Belyaev A,Seidel H P.A fast and simple stretch-minimizing mesh parameterization[C]//Proceedings of Shape Modeling Applications.Los Alamitos:IEEE Computer Society Press,2004:200-208
[10]Yueh M H,Lin W W,Wu C T,et al.A novel stretch energy minimization algorithm for equiareal parameterizations[OL].[2018-06-29].https://doi.org/10.1007/s10915-018-0822-7
[11]Xue J X,Li Q B,Liu C M,et al.Parameterization of triangulated surface meshes based on constraints of distortion energy optimization[J].Journal of Visual Languages and Computing,2018,46:53-62
[12]Su K H,Cui L,Qian K,et al.Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation[J].Computer Aided Geometric Design,2016,46:76-91
[13]Zou G Y,Hu J X,Gu X,et al.Authalic parameterization of general surfaces using lie advection[J].IEEE Transactions on Visualization and Computer Graphics,2011,17(12):2005-2014
[14]Monge G.Thesis on the theory of excavations and embankments[M].Paris:History of the Royal Academy of Sciences,1781
[15]Lévy B,Schwindt E L.Notions of optimal transport theory and how to implement them on a computer[J].Computers&Graphics,2018,72:135-148
[16]Luebke D,Harris M,Krüger J,et al.GPGPU:general-purpose computation on graphics hardware[C]//Proceedings of ACMSIGGRAPH 2004 Course Notes.New York:ACM Press,2004:Article No.33
[17]Gu X F,Luo F,Sun J,et al.Variational principles for Minkowski type problems,discrete optimal transport,and discrete Monge-Ampere equations[J].Asian Journal of Mathematics,2016,20(2):383-398
[18]Lei N,Su K H,Cui L,et al.A geometric view of optimal transportation and generative model[OL].[2018-06-29].https://arxiv.org/abs/1710.05488
[19]Su K H,Chen W,Lei N,et al.Volume preserving mesh parameterization based on optimal mass transportation[J].Computer-Aided Design,2017,82:42-56
[20]Kantorovich L V.On a problem of Monge[J].Journal of Mathematical Sciences,2006,133(4):1383
[21]Brenier Y.Polar factorization and monotone rearrangement of vector-valued functions[J].Communications on Pure and Applied Mathematics,1991,44(4):375-417
[22]Villani C.Optimal transport:old and new[M].Heidelberg:Springer,2008
[23]Alexandrov A D.Convex polyhedra[M].Heidelberg:Springer,2005
[24]Hoff III K E,Keyser J,Lin M,et al.Fast computation of generalized Voronoi diagrams using graphics hardware[C]//Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press/Addison-Wesley Publishing Co,1999:277-286
[25]Wellons C.A GPU approach to voronoi diagrams[OL].[2018-06-29].https://nullprogram.com/blog/2014/06/01/
[26]Dominitz A,Tannenbaum A.Texture mapping via optimal mass transport[J].IEEE Transactions on Visualization and Computer Graphics,2010,16(3):419-433
[2]Floater M S.Parametrization and smooth approximation of surface triangulations[J].Computer Aided Geometric Design,1997,14(3):231-250
[3]Sheffer A,de Sturler E.Parameterization of faceted surfaces for meshing using angle-based flattening[J].Engineering with Computers,2001,17(3):326-337
[4]Hormann K,Greiner G.MIPS:an efficient global parametrization method[M]//Curve and Surface Design.Nashville:Vanderbilt University Press,2000
[5]Zhang M,Guo R,Zeng W,et al.The unified discrete surface Ricci flow[J].Graphical Models,2014,76(5):321-339
[6]Zeng M,Zhang W,Guo R,et al.Survey on discrete surface Ricci flow[J].Journal of Computer Science and Technology,2015,30(3):598-613
[7]Hamilton R S.Three-manifolds with positive Ricci curvature[J].Journal of Differential Geometry,1982,17(2):255-306
[8]Eells J,Sampson J H.Harmonic mappings of Riemannian manifolds[J].American Journal of Mathematics,1964,86(1):109-160
[9]Yoshizawa S,Belyaev A,Seidel H P.A fast and simple stretch-minimizing mesh parameterization[C]//Proceedings of Shape Modeling Applications.Los Alamitos:IEEE Computer Society Press,2004:200-208
[10]Yueh M H,Lin W W,Wu C T,et al.A novel stretch energy minimization algorithm for equiareal parameterizations[OL].[2018-06-29].https://doi.org/10.1007/s10915-018-0822-7
[11]Xue J X,Li Q B,Liu C M,et al.Parameterization of triangulated surface meshes based on constraints of distortion energy optimization[J].Journal of Visual Languages and Computing,2018,46:53-62
[12]Su K H,Cui L,Qian K,et al.Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation[J].Computer Aided Geometric Design,2016,46:76-91
[13]Zou G Y,Hu J X,Gu X,et al.Authalic parameterization of general surfaces using lie advection[J].IEEE Transactions on Visualization and Computer Graphics,2011,17(12):2005-2014
[14]Monge G.Thesis on the theory of excavations and embankments[M].Paris:History of the Royal Academy of Sciences,1781
[15]Lévy B,Schwindt E L.Notions of optimal transport theory and how to implement them on a computer[J].Computers&Graphics,2018,72:135-148
[16]Luebke D,Harris M,Krüger J,et al.GPGPU:general-purpose computation on graphics hardware[C]//Proceedings of ACMSIGGRAPH 2004 Course Notes.New York:ACM Press,2004:Article No.33
[17]Gu X F,Luo F,Sun J,et al.Variational principles for Minkowski type problems,discrete optimal transport,and discrete Monge-Ampere equations[J].Asian Journal of Mathematics,2016,20(2):383-398
[18]Lei N,Su K H,Cui L,et al.A geometric view of optimal transportation and generative model[OL].[2018-06-29].https://arxiv.org/abs/1710.05488
[19]Su K H,Chen W,Lei N,et al.Volume preserving mesh parameterization based on optimal mass transportation[J].Computer-Aided Design,2017,82:42-56
[20]Kantorovich L V.On a problem of Monge[J].Journal of Mathematical Sciences,2006,133(4):1383
[21]Brenier Y.Polar factorization and monotone rearrangement of vector-valued functions[J].Communications on Pure and Applied Mathematics,1991,44(4):375-417
[22]Villani C.Optimal transport:old and new[M].Heidelberg:Springer,2008
[23]Alexandrov A D.Convex polyhedra[M].Heidelberg:Springer,2005
[24]Hoff III K E,Keyser J,Lin M,et al.Fast computation of generalized Voronoi diagrams using graphics hardware[C]//Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press/Addison-Wesley Publishing Co,1999:277-286
[25]Wellons C.A GPU approach to voronoi diagrams[OL].[2018-06-29].https://nullprogram.com/blog/2014/06/01/
[26]Dominitz A,Tannenbaum A.Texture mapping via optimal mass transport[J].IEEE Transactions on Visualization and Computer Graphics,2010,16(3):419-433
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |