Harmonic volumetric mapping for solid modeling applications

ABSTRACT

Harmonic volumetric mapping for two solid objects establishes a one-to-one smooth correspondence between them. It finds its applications in shape registration and analysis, shape retrieval, information reuse, and material/texture transplant. In sharp contrast to harmonic surface mapping techniques, little research has been conducted for designing volumetric mapping algorithms due to its technical challenges. In this paper, we develop an automatic and effective algorithm for computing harmonic volumetric mapping between two models of the same topology. Given a boundary mapping between two models, the volumetric (interior) mapping is derived by solving a linear system constructed from a boundary method called the fundamental solution method. The mapping is represented as a set of points with different weights in the vicinity of the solid boundary. In a nutshell, our algorithm is a true meshless method (with no need of specific connectivity) and the behavior of the interior region is directly determined by the boundary. These two properties help improve the computational efficiency and robustness. Therefore, our algorithm can be applied to massive volume data sets with various geometric primitives and topological types. We demonstrate the utility and efficacy of our algorithm in shape registration, information reuse, deformation sequence analysis, tetrahedral remeshing and solid texture synthesis.

REFERENCES

• 1: Pierre Alliez , David Cohen-Steiner , Mariette Yvinec , Mathieu Desbrun, Variational tetrahedral meshing, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 2: Banerjee, P. 1994. The Boundary Element Methods in Engineering. McGraw-Hill, New York.
• 3: Belytschko, T., Lu, Y. Y., and Gu, L. 1994. Element free galerkin methods. International Journal for Numerical Methods in Engineering 37, 229--256.
• 4: Belytschko, T., Krongauz, Y., Organ, D., Fleming, M., and Krysl, P. 1996. Meshless methods: An overview and recent developments. Computer Methods in Applied Mechanics and Engineering 139, 3--47.
• 5: Jules Bloomenthal, An implicit surface polygonizer, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 6: Bogomolny, A. 1985. Fundamental solutions method for elliptic boundary value problems. SIAM Journal on Numerical Analysis 22, 644--669.
• 7: Bridson, R., Teran, J., Molino, N., and Fedkiw, R. 2005. Adaptive physics based tetrahedral mesh generation using level sets. Engineering with Computers 21, 2--18.
• 8: H. Cheng , L. Greengard , V. Rokhlin, A fast adaptive multipole algorithm in three dimensions, Journal of Computational Physics, v.155 n.2, p.468-498, Nov. 1, 1999 [doi>10.1006/jcph.1999.6355]
• 9: Mathieu Desbrun , Marie-Paule Gascuel, Animating soft substances with implicit surfaces, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.287-290, September 1995 [doi>10.1145/218380.218456]
• 10: Mathieu Desbrun , Marie-Paule Gascuel, Smoothed particles: a new paradigm for animating highly deformable bodies, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.61-76, December 1996, Poitiers, France
• 11: Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21, 3, 209--218.
• 12: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 13: Fairweather, G., and Karageorghis, A. 1998. The method of fundamental solution for elliptic boundary value problems. Advances in Computational Mathematics 9, 1--2 (September), 69--95.
• 14: Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization. Springer, Berlin, Heidelberg, 157--186.
• 15: Michael S. Floater, Mean value coordinates, Computer Aided Geometric Design, v.20 n.1, p.19-27, March 2003 [doi>10.1016/S0167-8396(02)00002-5]
• 16: Frisken, S., and Perry, R. 2003. Simple and efficient traversal methods for quadtrees and octrees.
• 17: Garabedian, P. 1998. Partial Differential Equations. American Mathematical Society.
• 18: Golberg, M. A., and Chen, C. S. 1999. The method of fundamental solutions for potential, helmholtz and diffusion problems. Boundary integral methods: Numerical and mathematical aspects (A99-30801 07-64) 1, 103--176.
• 19: Gu, X., Wang, Y., Chan, T., Thompson, P., and Yau, S. T. 2004. Genus zero surface conformal mapping and its application to brain surface mapping. IEEE Trans. Med. Imaging 23, 8, 949--958.
• 20: Xiaohu Guo , Xin Li , Yunfan Bao , Xianfeng Gu , Hong Qin, Meshless Thin-Shell Simulation Based on Global Conformal Parameterization, IEEE Transactions on Visualization and Computer Graphics, v.12 n.3, p.375-385, May 2006 [doi>10.1109/TVCG.2006.52]
• 21: Robert Jagnow , Julie Dorsey , Holly Rushmeier, Stereological techniques for solid textures, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 22: Doug L. James , Dinesh K. Pai, ArtDefo: accurate real time deformable objects, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.65-72, July 1999 [doi>10.1145/311535.311542]
• 23: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 24: Kanai, T., Suzuki, H., and Kimura, F. 1998. Three-dimensional geometric metamorphosis based on harmonic maps. The Visual Comput. 14, 4, 166--176.
• 25: Kitagawa, T. 1988. On the numerical stability of the method of fundamental solutions applied to the dirichlet problem. Japan Journal of Applied Mathematics 35, 507--518.
• 26: Vladislav Kraevoy , Alla Sheffer, Cross-parameterization and compatible remeshing of 3D models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 27: Larsen, E., Gottschalk, S., Lin, M. C., and Manocha, D. 2000. Fast distance queries with rectangular swept sphere volumes. In Proc. IEEE International Conference on Robotics and Automation, 3719--3726.
• 28: Aaron W. F. Lee , David Dobkin , Wim Sweldens , Peter Schröder, Multiresolution mesh morphing, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.343-350, July 1999 [doi>10.1145/311535.311586]
• 29: Li, X., Bao, Y., Guo, X., Gu, X., and Qin, H. 2007. Extremal quasiconformal surface mapping. Manuscript submitted for publication.
• 30: Liu, Y., Nishimura, N., and Yao, Z. 2005. A fast multipole accelerated method of fundamental solutions for potential problems. Engineering Analysis with Boundary Elements 29, 1016--1024.
• 31: Takashi Michikawa , Takashi Kanai , Masahiro Fujita , Hiroaki Chiyokura, Multiresolution Interpolation Meshes, Proceedings of the 9th Pacific Conference on Computer Graphics and Applications, p.60, October 16-18, 2001
• 32: Monaghan, J. 1988. An introduction to sph. Computer Physics Communications 48, 89--96.
• 33: M. Müller , R. Keiser , A. Nealen , M. Pauly , M. Gross , M. Alexa, Point based animation of elastic, plastic and melting objects, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028542]
• 34: Matthias Müller , Bruno Heidelberger , Matthias Teschner , Markus Gross, Meshless deformations based on shape matching, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 35: Mark Pauly , Richard Keiser , Bart Adams , Philip Dutré , Markus Gross , Leonidas J. Guibas, Meshless animation of fracturing solids, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 36: Darwyn R. Peachey, Solid texturing of complex surfaces, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.279-286, July 1985
• 37: Ken Perlin, An image synthesizer, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.287-296, July 1985
• 38: Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugate. In Experimental Mathematics, vol. 2, 15--36.
• 39: Serban D. Porumbescu , Brian Budge , Louis Feng , Kenneth I. Joy, Shell maps, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 40: Emil Praun , Wim Sweldens , Peter Schröder, Consistent mesh parameterizations, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.179-184, August 2001 [doi>10.1145/383259.383277]
• 41: Ramachandran, P. A. 2002. Method of fundamental solutions: singular value decomposition analysis. Comunications in Numerical Methods in Engineering 18, 11, 789--801.
• 42: John Schreiner , Arul Asirvatham , Emil Praun , Hugues Hoppe, Inter-surface mapping, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 43: Si, H. 2006. http://tetgen.berlios.de/version1.41.
• 44: Sumner, R. W., and Popovic, J. Mesh data from deformation transfer for triangle meshes. http://people.csail.mit.edu/sumner/research/deftransfer/data.html.
• 45: Robert W. Sumner , Jovan Popović, Deformation transfer for triangle meshes, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 46: Tanklevich, R., Fairweather, G., Karageorghis, A., and Smyrlis, Y. S. Potential field based geometric modeling using the method of fundamental solutions. Technical Report.
• 47: Voruganti, H. K., Dasgupta, B., and Hommel, G. 2006. A novel potential field based domain mapping method. In Proceedings of 10th WSEAS Conference on Computers.
• 48: Wang, Y., Gu, X., Chan, T. F., Thompson, P. M., and Yau, S. T. 2004. Volumetric harmonic brain mapping. In ISBI '04: IEEE International Symposium on Biomedical Imaging: Macro to Nano., 1275--1278.
• 49: Wang, Y., Gu, X., and Yau, S. T. 2004. Volumetric harmonic map. Communications in Information and Systems 3, 3, 191--202.
• 50: Yizhou Yu , Kun Zhou , Dong Xu , Xiaohan Shi , Hujun Bao , Baining Guo , Heung-Yeung Shum, Mesh editing with poisson-based gradient field manipulation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 51: Zayer, R., Rössl, C., Karni, Z., and Seidel, H.-P. 2005. Harmonic guidance for surface deformation. Computer Graphics Forum 24, 3, 601--609.

INDEX TERMS

Keywords:
harmonic mapping, information reuse, shape registration and analysis, solid texture synthesis, volumetric mapping