浏览全部资源
扫码关注微信
Received：18 December 2020，
Revised：2021-5-17，
Accepted：24 May 2021，
Published：16 February 2022
移动端阅览
目的
2
体映射建立了两个3维体网格之间的对应关系，是计算机图形学中的重要研究方向。很多应用要求体映射是无翻转的，即其雅可比矩阵的行列式处处大于0。然而，现有的无翻转体映射生成算法经常无法完全消除翻转。挑战主要在于很难在保证满足位置约束的前提下消除映射的翻转。为此，提出一种新的无翻转体映射计算方法，核心是一种新的变形方法。
方法
2
首先放松位置约束，然后在变形过程中通过线搜索的方式保证不产生翻转，最后将网格无翻转地变形到满足位置约束。为实现这个变形过程，提出一种雅可比矩阵引导的变形算法。虽然现有的无翻转体映射方法不能完全消除翻转，但其雅可比矩阵可以作为本文变形算法的指导。此外，优化了位置能量，使得变形网格最终能够满足位置约束要求。为了满足体映射低扭曲的要求，算法最后在固定位置约束的前提下进一步优化了体映射的扭曲能量。
结果
2
对大量复杂网格进行实验，本文算法能够保证生成无翻转的体映射，并且通过多步优化最终结果均能满足给定的位置约束要求。
结论
2
通过与现有其他算法的优点和局限性对比，结果表明本文算法具有较好的鲁棒性。本文算法从一个全新的角度促进了无翻转体映射生成技术的进步与发展。
Objective
2
Computing low-distortion volumetric mapping while avoiding foldovers is an important issue in computer graphics and geometry processing. Foldover-free volumetric mapping has a wide range of applications in many fields such as mesh deformation
remeshing
mesh optimization
and shape analysis. Objects in the real world contain internal structures. Volumetric mapping not only needs to consider the surface but also needs to deal with internal complex geometric and topological structures. Volumetric mapping must be foldover-free
that is
the determinant of the Jacobian matrix of the volume mapping is greater than 0 everywhere because no negative volume is observed in real objects. The difficulties in generating a foldover-free volumetric mapping are as follows: 1) The input mapping may have foldovers. Removing these foldovers is difficult because the foldover-free constraint is nonlinear and nonconvex. 2) Volumetric mapping needs to satisfy the given position constraints. Position constraints and foldover-free constraints are mutually restricted
and simultaneously meeting these two constraints is difficult. The traditional volumetric mapping generation method mainly includes two cate-gories. Maintenance-based methods start from a foldover-free initialization
try to reduce the mapping distortion by optimizing energy
and use the line search method to prevent the mesh from flipping during the optimization. However
these methods rely on foldover-free initialization
and several of them may require additional input information
which is difficult to obtain. Other methods try to eliminate foldovers in the initial volumetric mapping. These methods do not rely on the foldover-free initialization
and no additional input information is required. However
they cannot guarantee that foldovers can be completely eliminated. Our goal is to generate foldover-free volumetric mappings and make these mappings satisfy the position constraints. However
simultaneously satisfying these two conditions is not trivial.
Method
2
A volumetric mapping generation algorithm guided by Jacobian matrix is proposed to solve this problem. The core of our algorithm is a new deformation method that first relaxes the position constraint and then uses the Jacobian matrix as the deformation guide to deform the mesh to satisfy the position constraint while avoiding foldovers. To achieve this deformation goal
a Jacobian-guided deformation algorithm is proposed. Our findings reveal that although the previous method cannot completely eliminate flips
its Jacobian matrix can be used as a guide for our deformation algorithm. In addition
the position energy is optimized such that the deformed mesh can finally satisfy the position constraints. Finally
the position constraint is fixed
and the distortion of the volumetric mapping is further reduced by optimizing the energy.
Result
2
Experiments are conducted on a large number of complex models. Different target shapes (i.e.
a ball
a PolyCube and a general surface) are used as position constraints of the boundary vertices. When the boundary position is constrained to be a ball
the previous method often cannot completely eliminate foldovers because the target shape is very different from the input mesh. However
our method produces good results for these complex models. Our method has no requirements for the initial mapping
and three initialization types are used in our experiment. These initializations include a large number of foldovers
which can be completely eliminated in the end. These experiments prove that our method is robust. Compared with the previous method
our method can theoretically guarantee that the volumetric mapping generated by our method does not have foldovers. Experiment results show that the position energy can be controlled to a very small value
which proves that our method can meet the position constraint requirements.
Conclusion
2
This paper generates foldover-free volumetric mapping and proposes a Jacobian-guided deformation algorithm
which changes the idea of traditional volumetric mapping generation algorithm. Our algorithm can generate foldover-free volumetric mappings and be applied to more research. However
our method also has limitations. Our algorithm needs a reasonable Jacobian matrix as a guide
which affects our deformation results. In addition
although good volumetric mapping results can be generated
no theoretical guarantee ensures that the position constraints can be met.
Aigerman N and Lipman Y. 2013. Injective and bounded distortion mappings in 3D. ACM Transactions on Graphics, 32(4): #106[DOI: 10.1145/2461912.2461931]
Campen M, Silva C T and Zorin D. 2016. Bijective maps from simplicial foliations. ACM Transactions on Graphics, 35(4): #74[DOI: 10.1145/2897824.2925890]
Claici S, Bessmeltsev M, Schaefer S and Solomon J. 2017. Isometry-aware preconditioning for mesh parameterization. Computer Graphics Forum, 36(5): 37-47[DOI: 10.1111/cgf.13243]
Du X Y, Aigerman N, Zhou Q N, Kovalsky S Z, Yan Y J, Kaufman D M and Ju T. 2020. Lifting simplices to find injectivity. ACM Transactions on Graphics, 39(4): #120[DOI: 10.1145/3386569.3392484]
Fu X M, Liu Y and Guo B N. 2015. Computing locally injective mappings by advanced MIPS. ACM Transactions on Graphics, 34(4): #71[DOI: 10.1145/2766938]
Fu X M, Bai C Y and Liu Y. 2016. Efficient volumetric PolyCube-map construction. Computer Graphics Forum, 35(7): 97-106[DOI: 10.1111/cgf.13007]
Golla B, Seidel H P and Chen R J. 2018. Piecewise linear mapping optimization based on the complex view. Computer Graphics Forum, 37(7): 233-243[DOI: 10.1111/cgf.13563]
Hu X, Fu X M and Liu L G. 2018. Advanced hierarchical spherical parameterizations. IEEE Transactions on Visualization and Computer Graphics, 24(6): 1930-1941[DOI: 10.1109/TVCG.2017.2704119]
Jiang Z S, Schaefer S and Panozzo D. 2017. Simplicial complex augmentation framework for bijective maps. ACM Transactions on Graphics, 36(6): #186[DOI: 10.1145/3130800.3130895]
Kovalsky S Z, Aigerman N, Basri R and Lipman Y. 2014. Controlling singular values with semidefinite programming. ACM Transactions on Graphics, 33(4): #68[DOI: 10.1145/2601097.2601142]
Kovalsky S Z, Aigerman N, Basri R and Lipman Y. 2015. Large-scale bounded distortion mappings. ACM Transactions on Graphics, 34(6): #191[DOI: 10.1145/2816795.2818098]
Kovalsky S Z, Galun M and Lipman Y. 2016. Accelerated quadratic proxy for geometric optimization. ACM Transactions on Graphics, 35(4): #134[DOI: 10.1145/2897824.2925920]
Liu L G, Ye C Y, Ni R Q and Fu X M. 2018. Progressive parameterizations. ACM Transactions on Graphics, 37(4): #41[DOI:10.1145/3197517.3201331]
Liu T T, Gao M, Zhu L F, Sifakis E and Kavan L. 2016. Fast and robust inversion-free shape manipulation. Computer Graphics Forum, 35(2): 1-11[DOI: 10.1111/cgf.12806]
Paillé G P, Ray N, Poulin P, Sheffer A and Lévy B. 2015. Dihedral angle-based maps of tetrahedral meshes. ACM Transactions on Graphics, 34(4): #54[DOI: 10.1145/2766900]
Petra C G, Schenk O and Anitescu M. 2014a. Real-time stochastic optimization of complex energy systems on high-performance computers. Computing in Science and Engineering, 16(5): 32-42[DOI: 10.1109/MCSE.2014.53]
Petra C G, Schenk O, Lubin M and Gäertner K. 2014b. An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. SIAM Journal on Scientific Computing, 36(2): C139-C162[DOI: 10.1137/130908737]
Rabinovich M, Poranne R, Panozzo D and Sorkine-Hornung O. 2017. Scalable locally injective mappings. ACM Transactions on Graphics, 36(2): #16[DOI: 10.1145/2983621]
Schenk O, Wächter A and Hagemann M. 2007. Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization. Computational Optimization and Applications, 36(2/3): 321-341[DOI: 10.1007/s10589-006-9003-y]
Schreiner J, Asirvatham A, Praun E and Hoppe H. 2004. Inter-surface mapping. ACM Transactions on Graphics, 23(3): 870-877[DOI: 10.1145/1015706.1015812]
Shtengel A, Poranne R, Sorkine-Hornung O, Kovalsky S Z and Lipman Y. 2017. Geometric optimization via composite majorization. ACM Transactions on Graphics, 36(4): #38[DOI: 10.1145/3072959.3073618]
Smith B, Goes F D and Kim T. 2019. Analytic eigensystems for isotropic distortion energies. ACM Transactions on Graphics, 38(1): #3[DOI: 10.1145/3241041]
Smith J and Schaefer S. 2015. Bijective parameterization with free boundaries. ACM Transactions on Graphics, 34(4): #70[DOI: 10.1145/2766947]
Su J P, Fu X M and Liu L G. 2019. Practical foldover-free volumetric mapping construction. Computer Graphics Forum, 38(7): 287-297[DOI: 10.1111/cgf.13837]
Tutte W T. 1963. How to draw a graph. Proceedings of the London Mathematical Society, s3-13(1): 743-767[DOI: 10.1112/plms/s3-13.1.743]
Weber O, Myles A and Zorin D. 2012. Computing extremal quasiconformal maps. Computer Graphics Forum, 31(5): 1679-1689[DOI: 10.1111/j.1467-8659.2012.03173.x]
Weber O and Zorin D. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Transactions on Graphics, 33(4): #75[DOI: 10.1145/2601097.2601227]
Xu Y, Chen R J, Gotsman C and Liu L G. 2011. Embedding a triangular graph within a given boundary. Computer Aided Geometric Design, 28(6): 349-356[DOI: 10.1016/j.cagd.2011.07.001]
Yang Y, Fu X M, Chai S M, Xiao S W and Liu L G. 2019. Volume-enhanced compatible remeshing of 3D models. IEEE Transactions on Visualization and Computer Graphics, 25(10): 2999-3010[DOI: 10.1109/tvcg.2018.2861396]
Zhu Y F, Bridson R and Kaufman D M. 2018. Blended cured quasi-newton for distortion optimization. ACM Transactions on Graphics, 37(4): #40[DOI:10.1145/3197517.3201359]
相关作者
相关机构
京公网安备11010802024621
