Pattern-aware shape deformation using sliding dockers

ABSTRACT

This paper introduces a new structure-aware shape deformation technique. The key idea is to detect continuous and discrete regular patterns and ensure that these patterns are preserved during free-form deformation. We propose a variational deformation model that preserves these structures, and a discrete algorithm that adaptively inserts or removes repeated elements in regular patterns to minimize distortion. As a tool for such structural adaptation, we introduce sliding dockers, which represent repeatable elements that fit together seamlessly for arbitrary repetition counts. We demonstrate the presented approach on a number of complex 3D models from commercial shape libraries.

References

1. Adams, B., Ovsjanikov, M., Wand, M., Seidel, H.-P., and Guibas, L. J. 2008. Meshless modeling of deformable shapes and their motion. In Symposium on Computer Animation.
2. Allen, B., Curless, B., and Popović, Z. 2003. The space of human body shapes: reconstruction and parameterization from range scans. In SIGGRAPH '03: ACM SIGGRAPH 2003 Papers, ACM, New York, NY, USA, 587--594.
3. Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Variational harmonic maps for space deformation. ACM Transactions on Graphics 28, 3.
4. Bokeloh, M., Berner, A., Wand, M., Seidel, H.-P., and Schilling, A. 2009. Symmetry detection using line features. Computer Graphics Forum 28, 2.
5. Bokeloh, M., Wand, M., and Seidel, H.-P. 2010. A connection between partial symmetry and inverse procedural modeling. ACM Trans. Graph. 29 (July), 104:1--104:10.
6. Botsch, M., and Sorkine, O. 2008. On linear variational surface deformation methods. IEEE Transactions on Visualization and Computer Graphics 14, 1, 213--230.
7. Coquillart, S. 1990. Extended free-form deformation: a sculpturing tool for 3d geometric modeling. In Proc. Siggraph.
8. Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., and Dobkin, D. 2004. Modeling by example. ACM Trans. Graph. 23, 3.
9. Gal, R., Sorkine, O., Mitra, N., and Cohen-Or, D. 2009. iwires: An analyze-and-edit approach to shape manipulation. ACM Trans. Graph. 28, 3.
10. Gelfand, N., and Guibas, L. 2004. Shape segmentation using local slippage analysis. In Proc. Symp. Geometry Processing.
11. Huang, J., Shi, X., Liu, X., Zhou, K., Wei, L.-Y., Teng, S.-H., Bao, H., Guo, B., and Shum, H.-Y. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graph. 25, 3.
12. Huang, Q., Mech, R., and Carr, N. 2009. Optimizing structure preserving embedded deformation for resizing images and vector art. In Pacific Graphics.
13. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26 (July).
14. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24 (July), 561--566.
15. Kraevoy, V., Julius, D., and Sheffer, A. 2007. Shuffler: Modeling with interchangeable parts. In Pacific Graphics 2007.
16. Kraevoy, V., Sheffer, A., Shamir, A., and Cohen-Or, D. 2008. Non-homogeneous resizing of complex models. ACM Trans. Graph. 27, 5, 1--9.
17. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27 (August).
18. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. 2008. A local/global approach to mesh parameterization. Computer Graphics Forum 27, 5, 1495--1504.
19. Mitra, N. J., and Pauly, M. 2008. Symmetry for architectural design. In Advances in Architectural Geometry, 13--16.
20. Mitra, N. J., Guibas, L. J., and Pauly, M. 2006. Partial and approximate symmetry detection for 3d geometry. ACM Trans. Graph. 25, 3, 560--568.
21. Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and B., C. 2002. Stable real-time deformations. In Proc. Symp. Computer Animation (SCA), 49--54.
22. Pauly, M., Mitra, N., Giesen, J., Gross, M., and Guibas, L. J. 2005. Example-based 3d scan completion. In Proc. Symp. Geometry Processing.
23. Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., and Guibas, L. 2008. Discovering structural regularity in 3D geometry. ACM Trans. Graph. 27, 3.
24. Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., and Funkhouser, T. 2006. A planar-reflective symmetry transform for 3D shapes. ACM Trans. Graph. 25, 3.
25. Sederberg, T. W., and Parry, S. R. 1986. Free-form deformation of solid geometric models. In Proc. Siggraph, 151--160.
26. Simari, P., Kalogerakis, E., and Singh, K. 2006. Folding meshes: hierarchical mesh segmentation based on planar symmetry. In Proc. Symp. Geometry Processing, 111--119.
27. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proceedings of Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 109--116.
28. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Symposium on Geometry processing.
29. Sumner, R. W., Schmid, J., and Pauly, M. 2007. Embedded deformation for shape manipulation. ACM Trans. Graph. 26, 3.
30. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proc. SIGGRAPH '87, ACM, New York, NY, USA, 205--214.
31. Toledo, S., 2003. Taucs: A library of sparse linear solvers. Tel-Aviv University, http://www.tau.ac.il/stoledo/taucs/.
32. von Funck, W., Theisel, H., and Seidel, H.-P. 2006. Vector field based shape deformations. ACM Trans. Graph. 25, 3.
33. Wang, Y., Xu, K., Li, J., Zhang, H., Shamir, A., Liu, L., Cheng, Z., and Xiong, Y. 2011. Symmetry hierarchy of man-made objects. In Proc. Eurographics.
34. Wu, H., Wang, Y.-S., Feng, K.-C., Wong, T.-T., Lee, T.-Y., and Heng, P.-A. 2010. Resizing by symmetry-summarization. ACM Transactions on Graphics 29, 6.
35. Xu, W., Wang, J., Yin, K., Zhou, K., van de Panne, M., Chen, F., and Guo, B. 2009. Joint-aware manipulation of deformable models. ACM Trans. Graph. 28, 3, 1--9.
36. Zheng, Y., Fu, H., Cohen-Or, D., Au, O. K.-C., and Tai, C.-L. 2011. Component-wise controllers for structure-preserving shape manipulation. In Proc. Eurographics.
37. Zhou, K., Huang, J., Snyder, J., Liu, X., Bao, H., Guo, B., and Shum, H.-Y. 2005. Large mesh deformation using the volumetric graph laplacian. ACM Trans. Graph. 24, 3, 496--503.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry