research-article
Author: Paul Merrell
ACM Transactions on Graphics (TOG), Volume 42, Issue 4
Article No.: 60, Pages 1 - 16
Published: 26 July 2023 Publication History
- 0citation
- 379
- Downloads
Metrics
Total Citations0Total Downloads379Last 12 Months379
Last 6 weeks31
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
Get Access
- Get Access
- References
- Media
- Tables
- Share
Abstract
We present a method for automatically generating polygonal shapes from an example using a graph grammar. Most procedural modeling techniques use grammars with manually created rules, but our method can create them automatically from an example. Our graph grammars generate graphs that are locally similar to a given example. We disassemble the input into small pieces called primitives and then reassemble the primitives into new graphs. We organize all possible locally similar graphs into a hierarchy and find matching graphs within the hierarchy. These matches are used to create a graph grammar that can construct every locally similar graph. Our method generates graphs using the grammar and then converts them into a planar graph drawing to produce the final shape.
Supplementary Material
supplemental material.
- Download
- 656.05 MB
presentation
- Download
- 172.33 MB
References
[1]
Daniel G. Aliaga, Paul A. Rosen, and Daniel R. Bekins. 2007. Style Grammars for Interactive Visualization of Architecture. IEEE Transactions on Visualization and Computer Graphics 13, 4 (2007), 786--797.
Digital Library
[2]
Connelly Barnes, Eli Shechtman, Adam Finkelstein, and Dan B Goldman. 2009. PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing. ACM Transactions on Graphics (Proc. SIGGRAPH) 28, 3 (2009).
Digital Library
[3]
Martin Bokeloh, Michael Wand, and Hans-Peter Seidel. 2010. A Connection between Partial Symmetry and Inverse Procedural Modeling. ACM Trans. Graph. 29, 4 (2010).
Digital Library
[4]
Martin Bokeloh, Michael Wand, Hans-Peter Seidel, and Vladlen Koltun. 2012. An Algebraic Model for Parameterized Shape Editing. ACM Trans. Graph. 31, 4 (2012).
Digital Library
[5]
Asger Nyman Christiansen and Jakob Andreas Bærentzen. 2012. Generic graph grammar: a simple grammar for generic procedural modelling. In SCCG.
[6]
Stephen A. Cook. 1971. The Complexity of Theorem-Proving Procedures (STOC '71). Association for Computing Machinery, New York, NY, USA, 151--158.
[7]
George R. Cross and Anil K. Jain. 1983. Markov Random Field Texture Models. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-5, 1 (1983), 25--39.
Digital Library
[8]
Minh Dang, Stefan Lienhard, Duygu Ceylan, Boris Neubert, Peter Wonka, and Mark Pauly. 2015. Interactive Design of Probability Density Functions for Shape Grammars. ACM Trans. Graph. 34, 6 (2015).
Digital Library
[9]
İlke Demir, Daniel G. Aliaga, and Bedrich Benes. 2016. Proceduralization for Editing 3D Architectural Models. In 2016 Fourth International Conference on 3D Vision (3DV). 194--202.
[10]
Alexei Efros and Thomas Leung. 1999. Texture synthesis by non-parametric sampling. In ICCV, Vol. 2. 1033--1038.
Digital Library
[11]
Hartmut Ehrig. 1979. Introduction to the algebraic theory of graph grammars. In Graph-Grammars and Their Application to Computer Science and Biology, Volker Claus, Hartmut Ehrig, and Grzegorz Rozenberg (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1--69.
[12]
H. Ehrig, M. Pfender, and H. J. Schneider. 1973. Graph-grammars: An algebraic approach. In 14th Annual Symposium on Switching and Automata Theory (swat 1973). 167--180.
Digital Library
[13]
David Eppstein. 1999. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications 3, 1--3 (1999).
[14]
Marek Fiser, Bedrich Benes, Jorge Garcia Galicia, Michel Abdul-Massih, Daniel G. Aliaga, and Vojtech Krs. 2016. Learning Geometric Graph Grammars. In Proceedings of the 32nd Spring Conference on Computer Graphics (SCCG '16). Association for Computing Machinery, New York, NY, USA, 7--15.
Digital Library
[15]
Ashim Garg. 1998. New results on drawing angle graphs. Computational Geometry 9, 1 (1998), 43--82. Special Issue on Geometric Representations of Graphs.
Digital Library
[16]
Leon A. Gatys, Alexander S. Ecker, and Matthias Bethge. 2015. Texture Synthesis Using Convolutional Neural Networks (NIPS'15). MIT Press, Cambridge, MA, USA, 262--270.
[17]
Maxim Gumin. 2016. WaveFunctionCollapse. https://github.com/mxgmn/WaveFunctionCollapse
[18]
Jianwei Guo, Haiyong Jiang, Bedrich Benes, Oliver Deussen, Xiaopeng Zhang, Dani Lischinski, and Hui Huang. 2020. Inverse Procedural Modeling of Branching Structures by Inferring L-Systems. ACM Transactions on Graphics 39, 5 (2020), 155:1--155:13.
Digital Library
[19]
Aaron Hertzmann, Nuria Oliver, Brian Curless, and Steven M. Seitz. 2002. Curve Analogies. In Proceedings of the 13th Eurographics Workshop on Rendering (Pisa, Italy) (EGRW '02). Eurographics Association, 233--246.
[20]
Takashi Ijiri, Radomír Mêch, Takeo Igarashi, and Gavin Miller. 2008. An Example-based Procedural System for Element Arrangement. Computer Graphics Forum 27, 2 (2008), 429--436.
[21]
Javor Kalojanov, Martin Bokeloh, Michael Wand, Leonidas Guibas, Hans-Peter Seidel, and Philipp Slusallek. 2012. Microtiles: Extracting Building Blocks from Correspondences. Comput. Graph. Forum 31, 5 (2012), 1597--1606.
Digital Library
[22]
Barbara König, Dennis Nolte, Julia Padberg, and Arend Rensink. 2018. A Tutorial on Graph Transformation. Springer International Publishing, Cham, 83--104.
[23]
Johannes Kopf, Chi-Wing Fu, Daniel Cohen-Or, Oliver Deussen, Dani Lischinski, and Tien-Tsin Wong. 2007. Solid Texture Synthesis from 2D Exemplars. ACM Trans. Graph. 26, 3 (2007).
Digital Library
[24]
Aristid Lindenmayer. 1968. Mathematical models for cellular interactions in development. II. Simple and branching filaments with two-sided inputs. J Theor Biol 18, 3 (1968), 300--315.
[25]
Markus Lipp, Peter Wonka, and Michael Wimmer. 2008. Interactive Visual Editing of Grammars for Procedural Architecture. ACM Transactions on Graphics (Proc. SIGGRAPH) (2008).
[26]
Han Liu, Ulysse Vimont, Michael Wand, Marie-Paule Cani, Stefanie Hahmann, Damien Rohmer, and Niloy Mitra. 2015. Replaceable Substructures for Efficient Part-Based Modeling. Computer Graphics Forum 34 (05 2015).
[27]
Chongyang Ma, Li-Yi Wei, Sylvain Lefebvre, and Xin Tong. 2013. Dynamic Element Textures. ACM Trans. Graph. 32, 4 (2013).
Digital Library
[28]
Chongyang Ma, Li-Yi Wei, and Xin Tong. 2011. Discrete Element Textures. ACM Trans. Graph. 30, 4 (2011).
Digital Library
[29]
Andelo Martinovic and Luc Van Gool. 2013. Bayesian Grammar Learning for Inverse Procedural Modeling. In CVPR. 201--208.
[30]
Paul Merrell. 2007. Example-Based Model Synthesis. Symp. Interactive 3D Graphics and Games (2007), 105--112.
[31]
Paul Merrell and Dinesh Manocha. 2008. Continuous Model Synthesis. ACM Trans. Graph. 27, 5 (2008).
Digital Library
[32]
Paul Merrell and Dinesh Manocha. 2010. Example-based curve synthesis. Computers & Graphics 34, 4 (2010), 304--311.
Digital Library
[33]
Paul Merrell and Dinesh Manocha. 2011. Model Synthesis: A General Procedural Modeling Algorithm. IEEE Transactions on Visualization and Computer Graphics 17, 6 (2011), 715--728.
Digital Library
[34]
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. 1953. Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics 21, 6 (1953), 1087--1092.
[35]
Pascal Müller, Peter Wonka, Simon Haegler, Andreas Ulmer, and Luc Van Gool. 2006. Procedural Modeling of Buildings. ACM Trans. Graph. 25, 3 (2006), 614--623.
Digital Library
[36]
Wojtek Pałubicki, Miłosz Makowski, Weronika Gajda, Torsten Hädrich, Dominik L. Michels, and Sören Pirk. 2022. Ecoclimates: Climate-Response Modeling of Vegetation. ACM Trans. Graph. 41, 4, Article 155 (jul 2022), 19 pages.
Digital Library
[37]
Yoav I. H. Parish and Pascal Müller. 2001. Procedural Modeling of Cities (SIGGRAPH '01). Association for Computing Machinery, New York, NY, USA, 301--308.
[38]
John L. Pfaltz and Azriel Rosenfeld. 1969. Web Grammars. In Proceedings of the 1st International Joint Conference on Artificial Intelligence (Washington, DC) (IJCAI'69). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 609--619.
[39]
Viktor Pogrzebacz and Martin Ilčík. 2019. A Graph Grammar for Modelling of 2D Shapes. In Proceedings of the 23rd Central European Seminar on Computer Graphics. TU Wien.
[40]
Przemyslaw Prusinkiewicz. 1986. Graphical applications of l-systems. In In Proceedings of Graphics Interface '86 --- Vision Interface '86. 247--253.
Digital Library
[41]
Daniel Ritchie, Ben Mildenhall, Noah D. Goodman, and Pat Hanrahan. 2015. Controlling Procedural Modeling Programs with Stochastically-Ordered Sequential Monte Carlo. ACM Trans. Graph. 34, 4, Article 105 (jul 2015), 11 pages.
Digital Library
[42]
Grzegorz Rozenberg. 1997. Handbook of graph grammars and computing by graph transformation. Vol. 1. World scientific.
[43]
Ruben M. Smelik, Tim Tutenel, Rafael Bidarra, and Bedrich Benes. 2014. A Survey on Procedural Modelling for Virtual Worlds. Computer Graphics Forum 33, 6 (2014), 31--50.
Digital Library
[44]
Colin Smith, Przemyslaw Prusinkiewicz, and Faramarz Samavati. 2004. Local Specification of Surface Subdivision Algorithms. In Applications of Graph Transformations with Industrial Relevance. Springer Berlin Heidelberg, Berlin, Heidelberg, 313--327.
[45]
Ondrej Stava, Bedrich Benes, Radomir Mech, Daniel Aliaga, and Peter Kristof. 2010. Inverse Procedural Modeling by Automatic Generation of L-systems. Computer Graphics Forum 29 (05 2010), 1467--8659.
[46]
O. Stava, S. Pirk, J. Kratt, B. Chen, R. Mźch, O. Deussen, and B. Benes. 2014. Inverse Procedural Modelling of Trees. 33, 6 (2014), 118--131.
[47]
George Stiny. 1975. Pictorial and Formal Aspects of Shape and Shape Grammars. Birkhauser Verlag, Basel.
[48]
George Stiny. 1982. Spatial relations and grammars. Environment and Planning B 9 (1982), 313--314.
[49]
Jerry Talton, Lingfeng Yang, Ranjitha Kumar, Maxine Lim, Noah Goodman, and Radomír Měch. 2012. Learning Design Patterns with Bayesian Grammar Induction. Association for Computing Machinery, 63--74.
[50]
Jerry O. Talton, Yu Lou, Steve Lesser, Jared Duke, Radomír Měch, and Vladlen Koltun. 2011. Metropolis Procedural Modeling. ACM Trans. Graph. 30, 2 (2011).
Digital Library
[51]
Peihan Tu, Li-Yi Wei, Koji Yatani, Takeo Igarashi, and Matthias Zwicker. 2020. Continuous Curve Textures. ACM Trans. Graph. 39, 6 (2020).
Digital Library
[52]
Carlos A. Vanegas, Ignacio Garcia-Dorado, Daniel G. Aliaga, Bedrich Benes, and Paul Waddell. 2012. Inverse Design of Urban Procedural Models. ACM Trans. Graph. 31, 6 (2012).
Digital Library
[53]
Luiz Velho. 2003. Stellar Subdivision Grammars. In Proceedings of the 2003 Eurographics ACM SIGGRAPH Symposium on Geometry Processing (SGP '03). Eurographics Association, 188--199.
Digital Library
[54]
Michael T. Wong, Douglas E. Zongker, and David H. Salesin. 1998. Computer-Generated Floral Ornament (SIGGRAPH '98). Association for Computing Machinery, New York, NY, USA, 423--434.
[55]
Peter Wonka, Michael Wimmer, François Sillion, and William Ribarsky. 2003. Instant Architecture. ACM Trans. Graph. 22, 3 (2003), 669--677.
Digital Library
[56]
Fuzhang Wu, Dong-Ming Yan, Weiming Dong, Xiaopeng Zhang, and Peter Wonka. 2014. Inverse Procedural Modeling of Facade Layouts. ACM Trans. Graph. 33, 4 (2014).
Digital Library
[57]
Rundi Wu and Changxi Zheng. 2022. Learning to Generate 3D Shapes from a Single Example. ACM Trans. Graph. 41, 6, Article 224 (nov 2022), 19 pages.
Digital Library
[58]
Yi-Ting Yeh, Katherine Breeden, Lingfeng Yang, Matthew Fisher, and Pat Hanrahan. 2013. Synthesis of Tiled Patterns Using Factor Graphs. ACM Trans. Graph. 32, 1 (2013).
Digital Library
[59]
Allan Zhao, Jie Xu, Mina Konaković Luković, Josephine Hughes, Andrew Speilberg, Daniela Rus, and Wojciech Matusik. 2020. RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1--16.
Digital Library
Index Terms
Example-Based Procedural Modeling Using Graph Grammars
Computing methodologies
Computer graphics
Shape modeling
Mesh geometry models
Recommendations
- Translating Controlled Graph Grammars to Ordinary Graph Grammars
Graph Grammar (GG) is an appropriate formal language for specifying complex systems. In a GG the system states are represented by graphs and the changes between the states are described by rules. The use of GGs is interesting as there are several ...
Read More
- Converting metamodels to graph grammars: doing without advanced graph grammar features
In this paper, we present a method to convert a metamodel in the form of a UML class diagram into a context-sensitive graph grammar whose language comprises precisely the set of model graphs (UML object diagrams) that conform to the input metamodel. ...
Read More
- Learning geometric graph grammars
SCCG '16: Proceedings of the 32nd Spring Conference on Computer Graphics
We introduce geometric graph grammars, demonstrate how they can generate geometric structures, and introduce an algorithm for their automatic learning (inverse procedural modeling). Our approach extends the concept of graph grammars to allow for coding ...
Read More
Comments
Information & Contributors
Information
Published In
ACM Transactions on Graphics Volume 42, Issue 4
August 2023
1912 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/3609020
Issue’s Table of Contents
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [emailprotected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 26 July 2023
Published inTOGVolume 42, Issue 4
Permissions
Request permissions for this article.
Check for updates
Author Tags
- inverse procedural modeling
- graph grammar
- local similarity
Qualifiers
- Research-article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
Total Citations
379
Total Downloads
- Downloads (Last 12 months)379
- Downloads (Last 6 weeks)31
Other Metrics
View Author Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Article
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderMedia
Figures
Other
Tables
