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. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617--625.
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. Bloomenthal, J. 1994. An implicit surface polygonizer. Graphics Gems IV, 324--349.
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. Cheng, H., Greengard, L., and Rokhlin, V. 1999. A fast adaptive multipole algorithm in three dimensions. Journal of Computational Physics 155, 468--498.
9. Desbrun, M., and Cani, M. P. 1995. Animating soft substances with implicit surfaces. In Proc. SIGGRAPH '95, 287--290.
10. Desbrun, M., and Cani, M. P. 1996. Smoothed particles: A new paradigm for animating highly deformable bodies. In Proc. EG Workshop on Animation and Simulation, 61--76.
11. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21, 3, 209--218.
12. Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In SIGGRAPH, 173--182.
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. Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1, 19--27.
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. Guo, X., Li, X., Bao, Y., Gu, X., and Qin, H. 2006. Meshless thin-shell simulation based on global conformal parameterization. IEEE Transactions on Visualization and Computer Graphics 12, 3, 375--385.
21. Jagnow, R., Dorsey, J., and Rushmeier, H. 2004. Stereological techniques for solid textures. ACM Trans. Graph. 23, 3, 329--335.
22. James, D. L., and Pai, D. K. 1999. Artdefo: accurate real time deformable objects. In Proc. SIGGRAPH '99, 65--72.
23. Ju, T., Schaefer, S., and Warren, J. D. 2005. Mean value coordinates for closed triangular meshes. SIGGRAPH 24, 3, 561--566.
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. Kraevoy, V., and Sheffer, A. 2004. Cross-parameterization and compatible remeshing of 3d models. ACM Trans. Graph. 23, 3, 861--869.
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. Lee, A., Dobkin, D., Sweldens, W., and Schröder, P. 1999. Multiresolution mesh morphing. In Proc. SIGGRAPH, 343--350.
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. Michikawa, T., Kanai, T., Fujita, M., and Chiyokura, H. 2001. Multiresolution interpolation meshes. In Proc. Pacific Graphics, 60--69.
32. Monaghan, J. 1988. An introduction to sph. Computer Physics Communications 48, 89--96.
33. Müller, M., Keiser, R., Nealen, A., Pauly, M., Gross, M., and Alexa, M. 2004. Point based animation of elastic, plastic and melting objects. In Proc. ACM SIGGRAPH/EG Symp. Computer Animation, 141--151.
34. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3, 471--478.
35. Pauly, M., Keiser, R., Adams, B., Dutre, P., Gross, M., and Guibas, L. J. 2005. Meshless animation of fracturing solids. ACM Trans. Graph. 24, 3, 957--964.
36. Peachey, D. R. 1985. Solid texturing of complex surfaces. In SIGGRAPH, ACM Press, New York, NY, USA, 279--286.
37. Perlin, K. 1985. An image synthesizer. In SIGGRAPH, ACM Press, New York, NY, USA, 287--296.
38. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugate. In Experimental Mathematics, vol. 2, 15--36.
39. Porumbescu, S. D., Budge, B., Feng, L., and Joy, K. I. 2005. Shell maps. ACM Trans. Graph. 24, 3, 626--633.
40. Praun, E., Sweldens, W., and Schröder, P. 2001. Consistent mesh parameterizations. In Proc. SIGGRAPH, 179--184.
41. Ramachandran, P. A. 2002. Method of fundamental solutions: singular value decomposition analysis. Comunications in Numerical Methods in Engineering 18, 11, 789--801.
42. Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. Inter-surface mapping. SIGGRAPH. 23, 3, 870--877.
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. Sumner, R. W., and Popovic, J. 2004. Deformation transfer for triangle meshes. ACM Trans. Graph. 23, 3, 399--405.
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. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., and Shum, H.-Y. 2004. Mesh editing with poisson-based gradient field manipulation. ACM Trans. Graph. 23, 3, 644--651.
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.

• Computing methodologies

  • Computer graphics

• Theory of computation