Martin Bokeloh
Abstract
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.
Supplemental Material
Available for Download
Zip contains: - video including explanations and results (InverseProceduralModeling.mp4) - visualization of an extracted shape grammar (castlegrammar.png)
- 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 Scholar
Digital Library
- 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
- Bhat, P., Ingram, S., and Turk, G. 2004. Geometric texture synthesis by example. In Symp. Geometry Processing. Google ScholarDigital Library
- 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
- 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
- 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
- Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. In Proc. Int. Conf. Comp. Vision. Google ScholarDigital Library
- 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
- 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
- Gelfand, N., and Guibas, L. 2004. Shape segmentation using local slippage analysis. In Proc. Symp. Geometry Processing. Google ScholarDigital Library
- 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
- 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
- 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
- Kraevoy, V., Julius, D., and Sheffer, A. 2007. Shuffler: Modeling with interchangeable parts. In Pacific Graphics 2007.Google Scholar
- 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
- 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
- Lagae, A., Dumont, O., and Dutré, P. 2005. Geometry synthesis by example. In Conf. Shape Modeling and Applications. Google ScholarDigital Library
- 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
- Merrell, P., and Manocha, D. 2008. Continuous model synthesis. ACM Trans. Graph. 27, 5, 1--7. Google ScholarDigital Library
- Merrell, P. 2007. Example-based model synthesis. In Symp. Interactive 3D Graphics and Games, 105--112. Google ScholarDigital Library
- Mitra, N. J., and Pauly, M. 2008. Symmetry for architectural design. In Advances in Architectural Geometry, 13--16.Google Scholar
- 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
- 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
- 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
- Neubert, B., Franken, T., and Deussen, O. 2007. Approximate image-based tree-modeling using particle flows. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
- 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
- Parish, Y. I. H., and Müller, P. 2001. Procedural modeling of cities. In Proc. Siggraph 2001, 301--308. Google ScholarDigital Library
- 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
- Prusinkiewicz, P., and Lindenmayer, A. 1990. The Algorithmic Beauty of Plants. Springer Verlag. Google ScholarDigital Library
- Rustamov, R. M. 2008. Augmented planar reflective symmetry transform. Vis. Comput. 24, 6, 423--433. Google ScholarDigital Library
- Sharf, A., Alexa, M., and Cohen-Or, D. 2004. Context-based surface completion. ACM Trans. Graph. 23, 3, 878--887. Google ScholarDigital Library
- 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
- 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
- Š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
- Wonka, P., Wimmer, M., Sillion, F., and Ribarsky, W. 2003. Instant architecture. ACM Trans. Graph. 22, 3, 669--677. Google ScholarDigital Library
- 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
- 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
- Zelinka, S., and Garland, M. 2006. Surfacing by numbers. In Graphics Interface 2006. Google ScholarDigital Library
- 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
Index Terms
- A connection between partial symmetry and inverse procedural modeling
Recommendations
Interactive sketching of urban procedural models
3D modeling remains a notoriously difficult task for novices despite significant research effort to provide intuitive and automated systems. We tackle this problem by combining the strengths of two popular domains: sketch-based modeling and procedural ...
Metropolis procedural modeling
Procedural representations provide powerful means for generating complex geometric structures. They are also notoriously difficult to control. In this article, we present an algorithm for controlling grammar-based procedural models. Given a grammar and ...
Inverse design of urban procedural models
We propose a framework that enables adding intuitive high level control to an existing urban procedural model. In particular, we provide a mechanism to interactively edit urban models, a task which is important to stakeholders in gaming, urban planning, ...
Comments