鲁棒的多层次平面参数化
|
摘要
为了提高平面参数化的鲁棒性,提出一种基于多层次结构的平面参数化算法,主要包含简化和细分加点2步.对于一个拓扑同胚于圆盘的三角形网格,首先对网格进行简化并存储所简化点的拓扑信息;然后将简化后的网格映射到圆盘上;再根据所存储的拓扑信息分批次加点直至恢复出三角网格的全部顶点,并在此过程中不断地优化网格,防止三角形翻转同时使网格顶点均匀分布;最后对恢复出全部顶点的圆盘网格进行优化,得到最终的参数化网格.实验结果表明,与当前的算法相比,该算法的鲁棒性有很大的提升.
In order to improve the robustness of planar parameterizations, we propose a novel hierarchical algorithm. The algorithm contains two procedures: decimation and subdivision. For a triangle mesh which is homeomorphic to disk, we decimate it firstly and store the topological information of the decimated vertices.Secondly, we map the decimated mesh into disk, subdivide the mesh and insert vertices flexibly according to the information stored until all of the vertices are restored. We optimize the mesh during the period to avoid flipping and make vertices distribute evenly meanwhile. Finally, we optimize the mesh and acquire the parameterized result. Compared with state-of-the-art methods, the experiments show that our algorithm performs better in robustness.
In order to improve the robustness of planar parameterizations, we propose a novel hierarchical algorithm. The algorithm contains two procedures: decimation and subdivision. For a triangle mesh which is homeomorphic to disk, we decimate it firstly and store the topological information of the decimated vertices.Secondly, we map the decimated mesh into disk, subdivide the mesh and insert vertices flexibly according to the information stored until all of the vertices are restored. We optimize the mesh during the period to avoid flipping and make vertices distribute evenly meanwhile. Finally, we optimize the mesh and acquire the parameterized result. Compared with state-of-the-art methods, the experiments show that our algorithm performs better in robustness.
引文
[1]Peng Qunsheng,Hu Guofei.Survey on parameterization of triangle meshes[J].Journal of Computer-Aided Design&Computer Graphics,2004,16(6):731-739(in Chinese)(彭群生,胡国飞.三角网格的参数化[J].计算机辅助设计与图形学学报,2004,16(6):731-739)
[2]Madaras M,?urikovi?R.Skeleton texture mapping[C]//Proceedings of the 28th Spring Conference on Computer Graphics.New York:ACM Press,2012:121-127
[3]Ohtake Y,Belyaev A,Seidel H P.Ridge-valley lines on meshes via implicit surface fitting[J].ACM Transactions on Graphics,2004,23(3):609-612
[4]Alliez P,Meyer M,Desbrun M.Interactive geometry remeshing[J].ACM Transactions on Graphics,2002,21(3):347-354
[5]Zhang Zhibang,Li Guiqing,Wei Guodong,et al.Survey on shape interpolation[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(8):1376-1387(in Chinese)(张智邦,李桂清,韦国栋,等.形状插值算法综述[J].计算机辅助设计与图形学学报,2015,27(8):1376-1387)
[6]Praun E,Hoppe H.Spherical parametrization and remeshing[J].ACM Transactions on Graphics,2003,22(3):340-349
[7]Peng C,Timalsena S.Fast mapping and morphing for genus-zero meshes with cross spherical parameterization[J].Computers&Graphics,2016,59:107-118
[8]Wan S H,Ye T F,Li M Q,et al.Efficient spherical parameterization using progressive optimization[C]//Proceedings of the1st International Conference on Computational Visual Media.Heidelberg:Springer,2012:170-177
[9]William T T.How to draw a graph[OL].[2018-06-29].http://www.cs.jhu.edu/~misha/Fall07/Papers/Tutte63.pdf
[10]Aigerman N,Lipman Y.Hyperbolic orbifold tutte embeddings[J].ACM Transactions on Graphics,2016,35(6):Article No.217
[11]Aigerman N,Poranne R,Lipman Y.Seamless surface mappings[J].ACM Transactions on Graphics,2015,34(4):Article No.72
[12]Floater M S.One-to-one piecewise linear mappings over triangulations[J].Mathematics of Computation,2003,72(242):685-696
[13]Aigerman N,Poranne R,Lipman Y.Lifted bijections for low distortion surface mappings[J].ACM Transactions on Graphics,2014,33(4):Article No.69
[14]Kovalsky S Z,Aigerman N,Basri R,et al.Large-scale bounded distortion mappings[J].ACM Transactions on Graphics,2015,34(6):Article No.191
[15]Lipman Y.Bounded distortion mapping spaces for triangular meshes[J].ACM Transactions on Graphics,2012,31(4):Article No.108
[16]Aigerman N,Lipman Y.Injective and bounded distortion mappings in 3D[J].ACM Transactions on Graphics,2013,32(4):Article No.106
[17]Kovalsky S Z,Aigerman N,Basri R,et al.Controlling singular values with semidefinite programming[J].ACM Transactions on Graphics,2014,33(4):Article No.68
[18]Poranne R,Lipman Y.Provably good planar mappings[J].ACM Transactions on Graphics,2014,33(4):Article No.76
[19]Weber O,Zorin D.Locally injective parametrization with arbitrary fixed boundaries[J].ACM Transactions on Graphics,2014,33(4):Article No.75
[20]Fu X M,Liu Y.Computing inversion-free mappings by simplex assembly[J].ACM Transactions on Graphics,2016,35(6):Article No.216
[21]Sheffer A,Lévy B,Mogilnitsky M,et al.ABF++:fast and robust angle based flattening[J].ACM Transactions on Graphics,2005,24(2):311-330
[22]Sheffer A,de Sturler E.Parameterization of faceted surfaces for meshing using angle-based flattening[J].Engineering with Computers,2001,17(3):326-337
[23]Kovalsky S Z,Galun M,Lipman Y.Accelerated quadratic proxy for geometric optimization[J].ACM Transactions on Graphics,2016,35(4):Article No.134
[24]Rabinovich M,Poranne R,Panozzo D,et al.Scalable locally injective mappings[J].ACM Transactions on Graphics,2017,36(2):Article No.16
[25]Claici S,Bessmeltsev M,Schaefer S,et al.Isometry-aware preconditioning for mesh parameterization[J].Computer Graphics Forum,2017,36(5):37-47
[26]Degener P,Meseth J,Klein R.An adaptable surface parameterization method[OL].[2018-06-29].https://imr.sandia.gov/papers/abstracts/De283.html
[27]Fu X M,Liu Y,Guo B N.Computing locally injective mappings by advanced MIPS[J].ACM Transactions on Graphics,2015,34(4):Article No.71
[28]Hormann K,Greiner G.MIPS:an efficient global parametrization method[M]//Curve and Surface Design:Saint-Malo.Nashville:Vanderbilt University Press,2000:153-162
[29]Jiang Z S,Schaefer S,Panozzo P.Simplicial complex augmentation framework for bijective maps[J].ACM Transactions on Graphics,2017,36(6):Article No.186
[30]Schüller C,Kavan L,Panozzo D,et al.Locally injective mappings[C]//Proceedings of the 11th Eurographics/ACMSIGG-RAPH Symposium on Geometry Processing.Aire-la-Ville:Eurographics Association Press,2013:125-135
[31]Shtengel A,Poranne R,Sorkine-Hornung O,et al.Geometric optimization via composite majorization[J].ACM Transactions on Graphics,2017,36(4):Article No.38
[32]Smith J,Schaefer S.Bijective parameterization with free boundaries[J].ACM Transactions on Graphics,2015,34(4):Article No.70
[33]Liu L G,Ye C Y,Ni R Q,et al.Progressive parameterizations[J].ACM Transactions on Graphics,2018,37(4):Article No.41
[34]Jin Y,Huang J,Tong R.Remeshing-assisted optimization for locally injective mappings[J].Computer Graphics Forum,2014,33(5):269-279
[35]Garland M,Heckbert P S.Surface simplification using quadric error metrics[C]//Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press/Addison-Wesley Publishing Co,1997:209-216
[36]Hu X,Fu X M,Liu L G,Advanced hierarchical spherical parameterizations[J].IEEE Transactions on Visualization and Computer Graphics,2017,24(6):1930-1941
[37]Lee A W F,Sweldens W,Schr?der P,et al.MAPS:multiresolution adaptive parameterization of surfaces[C]//Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press,1998:95-104
[38]Hormann K,Greiner G,Campagna S.Hierarchical parametrization of triangulated surfaces[OL].[2018-06-29].https://www.researchgate.net/publication/228554514_Hierarchical_Parametrization_of_Triangulated_Surfaces
[2]Madaras M,?urikovi?R.Skeleton texture mapping[C]//Proceedings of the 28th Spring Conference on Computer Graphics.New York:ACM Press,2012:121-127
[3]Ohtake Y,Belyaev A,Seidel H P.Ridge-valley lines on meshes via implicit surface fitting[J].ACM Transactions on Graphics,2004,23(3):609-612
[4]Alliez P,Meyer M,Desbrun M.Interactive geometry remeshing[J].ACM Transactions on Graphics,2002,21(3):347-354
[5]Zhang Zhibang,Li Guiqing,Wei Guodong,et al.Survey on shape interpolation[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(8):1376-1387(in Chinese)(张智邦,李桂清,韦国栋,等.形状插值算法综述[J].计算机辅助设计与图形学学报,2015,27(8):1376-1387)
[6]Praun E,Hoppe H.Spherical parametrization and remeshing[J].ACM Transactions on Graphics,2003,22(3):340-349
[7]Peng C,Timalsena S.Fast mapping and morphing for genus-zero meshes with cross spherical parameterization[J].Computers&Graphics,2016,59:107-118
[8]Wan S H,Ye T F,Li M Q,et al.Efficient spherical parameterization using progressive optimization[C]//Proceedings of the1st International Conference on Computational Visual Media.Heidelberg:Springer,2012:170-177
[9]William T T.How to draw a graph[OL].[2018-06-29].http://www.cs.jhu.edu/~misha/Fall07/Papers/Tutte63.pdf
[10]Aigerman N,Lipman Y.Hyperbolic orbifold tutte embeddings[J].ACM Transactions on Graphics,2016,35(6):Article No.217
[11]Aigerman N,Poranne R,Lipman Y.Seamless surface mappings[J].ACM Transactions on Graphics,2015,34(4):Article No.72
[12]Floater M S.One-to-one piecewise linear mappings over triangulations[J].Mathematics of Computation,2003,72(242):685-696
[13]Aigerman N,Poranne R,Lipman Y.Lifted bijections for low distortion surface mappings[J].ACM Transactions on Graphics,2014,33(4):Article No.69
[14]Kovalsky S Z,Aigerman N,Basri R,et al.Large-scale bounded distortion mappings[J].ACM Transactions on Graphics,2015,34(6):Article No.191
[15]Lipman Y.Bounded distortion mapping spaces for triangular meshes[J].ACM Transactions on Graphics,2012,31(4):Article No.108
[16]Aigerman N,Lipman Y.Injective and bounded distortion mappings in 3D[J].ACM Transactions on Graphics,2013,32(4):Article No.106
[17]Kovalsky S Z,Aigerman N,Basri R,et al.Controlling singular values with semidefinite programming[J].ACM Transactions on Graphics,2014,33(4):Article No.68
[18]Poranne R,Lipman Y.Provably good planar mappings[J].ACM Transactions on Graphics,2014,33(4):Article No.76
[19]Weber O,Zorin D.Locally injective parametrization with arbitrary fixed boundaries[J].ACM Transactions on Graphics,2014,33(4):Article No.75
[20]Fu X M,Liu Y.Computing inversion-free mappings by simplex assembly[J].ACM Transactions on Graphics,2016,35(6):Article No.216
[21]Sheffer A,Lévy B,Mogilnitsky M,et al.ABF++:fast and robust angle based flattening[J].ACM Transactions on Graphics,2005,24(2):311-330
[22]Sheffer A,de Sturler E.Parameterization of faceted surfaces for meshing using angle-based flattening[J].Engineering with Computers,2001,17(3):326-337
[23]Kovalsky S Z,Galun M,Lipman Y.Accelerated quadratic proxy for geometric optimization[J].ACM Transactions on Graphics,2016,35(4):Article No.134
[24]Rabinovich M,Poranne R,Panozzo D,et al.Scalable locally injective mappings[J].ACM Transactions on Graphics,2017,36(2):Article No.16
[25]Claici S,Bessmeltsev M,Schaefer S,et al.Isometry-aware preconditioning for mesh parameterization[J].Computer Graphics Forum,2017,36(5):37-47
[26]Degener P,Meseth J,Klein R.An adaptable surface parameterization method[OL].[2018-06-29].https://imr.sandia.gov/papers/abstracts/De283.html
[27]Fu X M,Liu Y,Guo B N.Computing locally injective mappings by advanced MIPS[J].ACM Transactions on Graphics,2015,34(4):Article No.71
[28]Hormann K,Greiner G.MIPS:an efficient global parametrization method[M]//Curve and Surface Design:Saint-Malo.Nashville:Vanderbilt University Press,2000:153-162
[29]Jiang Z S,Schaefer S,Panozzo P.Simplicial complex augmentation framework for bijective maps[J].ACM Transactions on Graphics,2017,36(6):Article No.186
[30]Schüller C,Kavan L,Panozzo D,et al.Locally injective mappings[C]//Proceedings of the 11th Eurographics/ACMSIGG-RAPH Symposium on Geometry Processing.Aire-la-Ville:Eurographics Association Press,2013:125-135
[31]Shtengel A,Poranne R,Sorkine-Hornung O,et al.Geometric optimization via composite majorization[J].ACM Transactions on Graphics,2017,36(4):Article No.38
[32]Smith J,Schaefer S.Bijective parameterization with free boundaries[J].ACM Transactions on Graphics,2015,34(4):Article No.70
[33]Liu L G,Ye C Y,Ni R Q,et al.Progressive parameterizations[J].ACM Transactions on Graphics,2018,37(4):Article No.41
[34]Jin Y,Huang J,Tong R.Remeshing-assisted optimization for locally injective mappings[J].Computer Graphics Forum,2014,33(5):269-279
[35]Garland M,Heckbert P S.Surface simplification using quadric error metrics[C]//Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press/Addison-Wesley Publishing Co,1997:209-216
[36]Hu X,Fu X M,Liu L G,Advanced hierarchical spherical parameterizations[J].IEEE Transactions on Visualization and Computer Graphics,2017,24(6):1930-1941
[37]Lee A W F,Sweldens W,Schr?der P,et al.MAPS:multiresolution adaptive parameterization of surfaces[C]//Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press,1998:95-104
[38]Hormann K,Greiner G,Campagna S.Hierarchical parametrization of triangulated surfaces[OL].[2018-06-29].https://www.researchgate.net/publication/228554514_Hierarchical_Parametrization_of_Triangulated_Surfaces