“A connection between partial symmetry and inverse procedural modeling” by Bokeloh, Wand and Seidel

In this paper, we address the problem of inverse procedural modeling: Given a piece of exemplar 3D geometry, we would like to find a set of rules that describe objects that are similar to the exemplar. We consider local similarity, i.e., each local neighborhood of the newly created object must match some local neighborhood of the exemplar. We show that we can find explicit shape modification rules that guarantee strict local similarity by looking at the structure of the partial symmetries of the object. By cutting the object into pieces along curves within symmetric areas, we can build shape operations that maintain local similarity by construction. We systematically collect such editing operations and analyze their dependency to build a shape grammar. We discuss how to extract general rewriting systems, context free hierarchical rules, and grid-based rules. All of this information is derived directly from the model, without user interaction. The extracted rules are then used to implement tools for semi-automatic shape modeling by example, which are demonstrated on a number of different example data sets. Overall, our paper provides a concise theoretical and practical framework for inverse procedural modeling of 3D objects.

1. Aliaga, D., Rosen, P., and Bekins, D. 2007. Style grammars for interactive visualization of architecture. IEEE Trans. Vis. Comp. Graph. 13, 4, 786–797. Google ScholarDigital Library
2. Barla, P., Breslav, S., Thollot, J., Sillion, F., and Markosian, L. 2006. Stroke pattern analysis and synthesis. Computer Graphics Forum 25, 3.Google ScholarCross Ref
3. Bhat, P., Ingram, S., and Turk, G. 2004. Geometric texture synthesis by example. In Symp. Geometry Processing. Google ScholarDigital Library
4. Bokeloh, M., Berner, A., Wand, M., Seidel, H.-P., and Schilling, A. 2009. Symmetry detection using line features. Computer Graphics Forum 28, 2.Google ScholarCross Ref
5. Cabral, M., Lefbvre, S., Dachsbacher, C., and Drettakis, G. 2009. Structure-preserving reshape for textured architectural scenes. Computer Graphics Forum 28, 2.Google ScholarCross Ref
6. Chen, L., and Meng, X. 2009. Anisotropic resizing of model with geometric textures. In Conf. on Geometric and Physical Modeling (SPM), ACM, New York, NY, USA, 289–294. Google ScholarDigital Library
7. Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. In Proc. Int. Conf. Comp. Vision. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
10. Gelfand, N., and Guibas, L. 2004. Shape segmentation using local slippage analysis. In Proc. Symp. Geometry Processing. Google ScholarDigital Library
11. Hart, J., and Flynn, O. C. P. 1997. Similarity hashing: A computer vision solution to the inverse problem of linear fractals. Fractals 5, 35–50.Google ScholarCross Ref
12. Hertzmann, A., Jacobs, C. E., Oliver, N., Curless, B., and Salesin, D. H. 2001. Image analogies. In Proc. Siggraph 2001, 327–340. Google ScholarDigital Library
13. Ijiri, T., Měch, R., Igarashi, T., and Miller, G. 2008. An example-based procedural system for element arrangement. Computer Graphics Forum 27, 3.Google ScholarCross Ref
14. Kraevoy, V., Julius, D., and Sheffer, A. 2007. Shuffler: Modeling with interchangeable parts. In Pacific Graphics 2007.Google Scholar
15. Kraevoy, V., Sheffer, A., Shamir, A., and Cohen-Or, D. 2008. Non-homogeneous resizing of complex models. ACM Trans. Graph. 27, 5, 1–9. Google ScholarDigital Library
16. Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: image and video synthesis using graph cuts. ACM Trans. Graph. 22, 3, 277–286. Google ScholarDigital Library
17. Lagae, A., Dumont, O., and Dutré, P. 2005. Geometry synthesis by example. In Conf. Shape Modeling and Applications. Google ScholarDigital Library
18. Lai, Y.-K., Hu, S.-M., Gu, D. X., and Martin, R. R. 2005. Geometric texture synthesis and transfer via geometry images. In Symp. Solid and Physical Modeling, 15–26. Google ScholarDigital Library
19. Merrell, P., and Manocha, D. 2008. Continuous model synthesis. ACM Trans. Graph. 27, 5, 1–7. Google ScholarDigital Library
20. Merrell, P. 2007. Example-based model synthesis. In Symp. Interactive 3D Graphics and Games, 105–112. Google ScholarDigital Library
21. Mitra, N. J., and Pauly, M. 2008. Symmetry for architectural design. In Advances in Architectural Geometry, 13–16.Google Scholar
22. 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. Google ScholarDigital Library
23. Müller, P., Wonka, P., Haegler, S., Ulmer, A., and Gool, L. V. 2006. Procedural modeling of buildings. ACM Trans. Graph. 25, 3, 614–623. Google ScholarDigital Library
24. Müller, P., Zeng, G., Wonka, P., and Gool, L. V. 2007. Image-based procedural modeling of facades. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
25. Neubert, B., Franken, T., and Deussen, O. 2007. Approximate image-based tree-modeling using particle flows. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
26. Nguyen, M. X., Yuan, X., and Chen, B. 2005. Geometry completion and detail generation by texture synthesis. The Visual Computer 21, 9–10, 669–678.Google ScholarCross Ref
27. Parish, Y. I. H., and Müller, P. 2001. Procedural modeling of cities. In Proc. Siggraph 2001, 301–308. Google ScholarDigital Library
28. Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., and Guibas, L. 2008. Discovering structural regularity in 3D geometry. ACM Trans. Graph. 27, 3. Google ScholarDigital Library
29. Prusinkiewicz, P., and Lindenmayer, A. 1990. The Algorithmic Beauty of Plants. Springer Verlag. Google ScholarDigital Library
30. Rustamov, R. M. 2008. Augmented planar reflective symmetry transform. Vis. Comput. 24, 6, 423–433. Google ScholarDigital Library
31. Sharf, A., Alexa, M., and Cohen-Or, D. 2004. Context-based surface completion. ACM Trans. Graph. 23, 3, 878–887. Google ScholarDigital Library
32. Sharf, A., Blumenkrants, M., Shamir, A., and Cohen-Or, D. 2006. Snappaste: an interactive technique for easy mesh composition. The Visual Computer 22, 9, 835–844. Google ScholarDigital Library
33. Tan, P., Zeng, G., Wang, J., Kang, S. B., and Quan, L. 2007. Image-based tree modeling. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
34. Št’ava, O., Beneš, B., Měch, R., Aliaga, D., and Krištof, P. 2010. Inverse procedural modeling by automatic generation of l-systems. Computer Graphics Forum. to appear.Google Scholar
35. Wonka, P., Wimmer, M., Sillion, F., and Ribarsky, W. 2003. Instant architecture. ACM Trans. Graph. 22, 3, 669–677. Google ScholarDigital Library
36. Xiao, J., Fang, T., Zhao, P., Lhuillier, M., and Quan, L. 2009. Image-based street-side city modeling. ACM Trans. Graph. 28, 5, 1–12. Google ScholarDigital Library
37. Yeh, Y.-T., and Měch, R. 2009. Detecting symmetries and curvilinear arrangements in vector art. Computer Graphics Forum 28, 2, 707–716.Google ScholarCross Ref
38. Zelinka, S., and Garland, M. 2006. Surfacing by numbers. In Graphics Interface 2006. Google ScholarDigital Library
39. Zhou, K., Huang, X., Wang, X., Tong, Y., Desbrun, M., and Baining Guo, H.-Y. S. 2006. Mesh quilting for geometric texture synthesis. ACM Trans. Graph. 25, 3, 690–697. Google ScholarDigital Library