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

  • ©Martin Bokeloh, Michael Wand, and Hans-Peter Seidel




    A connection between partial symmetry and inverse procedural modeling



    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

ACM Digital Library Publication: