“Metropolis Procedural Modeling” by Talton, Lou, Lesser, Duke, Mech, et al. …

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 a high-level specification of the desired production, the algorithm computes a production from the grammar that conforms to the specification. This production is generated by optimizing over the space of possible productions from the grammar. The algorithm supports specifications of many forms, including geometric shapes and analytical objectives. We demonstrate the algorithm on procedural models of trees, cities, buildings, and Mondrian paintings.

1. Agarwal, M. and Cagan, J. 1998. A blend of different tastes: the language of coffee makers. Environ. Plan. B: Plan. Des. 25, 2, 205–226.
2. Alegre, F. and Dellaert, F. 2004. A probabilistic approach to the semantic interpretation of building façades. In Proceedings of the International Workshop on Vision Techniques Applied to the Rehabilitation of City Centres.
3. Andrieu, C., de Freitas, N., Doucet, A., and Jordan, M. I. 2003. An introduction to MCMC for machine learning. Mach. Learn. 50, 1, 5–43.
4. Andrzejewski, D., Stork, D. G., Zhu, X., and Spronk, R. 2010. Inferring compositional style in the neo-plastic paintings of Piet Mondrian by machine learning. Comput. Vis. Image Anal. Art 7531, 1.
5. Bokeloh, M., Wand, M., and Seidel, H.-P. 2010. A connection between partial symmetry and inverse procedural modeling. In Proceedings of the SIGGRAPH Conference. ACM.
6. Box, G. E. P. and Muller, M. E. 1958. A note on the generation of random normal deviates. Ann. Math. Statis. 29, 610–611.
7. Buelinckx, H. 1993. Wren’s language of City church designs: a formal generative classification. Environ. Plan. B: Plan. Des. 20, 6, 645–676.
8. Cagan, J. and Mitchell, W. J. 1993. Optimally directed shape generation by shape annealing. Environ. Plan. B: Plan. Des. 20, 1, 5–12.
9. Chen, X., Neubert, B., Xu, Y.-Q., Deussen, O., and Kang, S. B. 2008. Sketch-Based tree modeling using Markov random field. In Proceedings of the SIGGRAPH Asia Conference. ACM.
10. Chenney, S. and Forsyth, D. A. 2000. Sampling plausible solutions to multi-body constraint problems. In Proceedings of the SIGGRAPH Conference. ACM, 219–228.
11. Deussen, O., Hanrahan, P., Lintermann, B., Měch, R., Pharr, M., and Prusinkiewicz, P. 1998. Realistic modeling and rendering of plant ecosystems. In Proceedings of the SIGGRAPH Conference. ACM, 275–286.
12. Duarte, J. P., Rocha, J. M., and Soares, G. D. 2007. Unveiling the structure of the Marrakech Medina: A shape grammar and an interpreter for generating urban form. Artif. Intell. Engin. Des. Anal. Manufact. 21, 4, 317–349.
13. Ebert, D. S., Musgrave, F. K., Peachey, D., Perlin, K., and Worley, S. 2002. Texturing and Modeling: A Procedural Approach, 3rd ed. Morgan Kaufmann.
14. Geyer, C. 1991. Markov chain Monte Carlo maximum likelihood. In Proceedings of the 23rd Symposium on the Interface: Computing Science and Statistics. 156–163.
15. Green, P. J. 1995. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika 82, 711–732.
16. Green, P. J. and Mira, A. 1999. Delayed rejection in reversible jump Metropolis-Hastings. Biometrika 88, 1035–1053.
17. Hastie, D. and Green, P. J. 2009. Reversible jump MCMC. Tech. rep., University of Bristol.
18. Hastings, W. K. 1970. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 1, 97–109.
19. Knight, T. W. 1980. The generation of Hepplewhite-style chair-back designs. Environ. Plan. B: Plan. Des. 7, 2, 227–238.
20. Koning, H. and Eizenberg, J. 1981. The language of the prairie: Frank Lloyd Wright’s prairie houses. Environ. Plan. B: Plan. Des. 8, 3, 295–323.
21. Lindenmayer, A. 1968. Mathematical models for cellular interactions in development ii. Simple and branching filaments with two-sided inputs. J. Theor. Biol. 18, 3, 300–315.
22. Marinari, E. and Parisi, G. 1992. Simulated tempering: A new Monte Carlo scheme. Europhys. Lett. 19, 6, 451–458.
23. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. 1953. Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 6, 1087–1092.
24. Müller, P., Wonka, P., Haegler, S., Ulmer, A., and Van Gool, L. 2006. Procedural modeling of buildings. In Proceedings of the SIGGRAPH Conference. ACM, 614–623.
25. Měch, R. and Prusinkiewicz, P. 1996. Visual models of plants interacting with their environment. In Proceedings of the SIGGRAPH Conference. ACM, 397–410.
26. Neal, R. 1994. Sampling from multimodal distributions using tempered transitions. Statis. Comput. 6, 353–366.
27. Neubert, B., Franken, T., and Deussen, O. 2007. Approximate image-based tree-modeling using particle flows. In Proceedings of the SIGGRAPH Conference. ACM.
28. Palubicki, W., Horel, K., Longay, S., Runions, A., Lane, B., Měch, R., and Prusinkiewicz, P. 2009. Self-Organizing tree models for image synthesis. In Proceedings of the SIGGRAPH Conference. ACM.
29. Parish, Y. I. H. and Müller, P. 2001. Procedural modeling of cities. In Proceedings of the SIGGRAPH Conference. ACM, 301–308.
30. Propp, J. G. and Wilson, D. B. 1996. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Struct. Algor. 9, 1&2.
31. Prusinkiewicz, P. 1986. Graphical applications of L-systems. In Proceedings on Graphics Interface. Canadian Information Processing Society, 247–253.
32. Prusinkiewicz, P. and Hanan, J. 1990. Visualization of botanical structures and processes using parametric L-systems. In Scientific Visualization and Graphics Simulation, 183–201.
33. Prusinkiewicz, P., James, M., and Měch, R. 1994. Synthetic topiary. In Proceedings of the SIGGRAPH Conference. ACM, 351–358.
34. Prusinkiewicz, P. and Lindenmayer, A. 1990. The Algorithmic Beauty of Plants. Springer, New York.
35. Pugliese, M. J. and Cagan, J. 2002. Capturing a rebel: Modeling the Harley-Davidson brand through a motorcycle shape grammar. Res. Engin. Des. 13, 139–156.
36. Ripperda, N. and Brenner, C. 2006. Reconstruction of façade structures using a formal grammar and RjMCMC. In Proceedings of the DAGM Symposium on Pattern Recognition. 750–759.
37. Ripperda, N. and Brenner, C. 2009. Evaluation of structure recognition using labelled façade images. In Proceedings of the DAGM Symposium on Pattern Recognition. 532–541.
38. Schlecht, J., Barnard, K., Spriggs, E., and Pryor, B. 2007. Inferring grammar-based structure models from 3D microscopy data. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Conference. 17–22.
39. Stava, O., Beneš, B., Měch, R., Aliaga, D., and Kristof, P. 2010. Inverse procedural modeling by automatic generation of L-systems. Comput. Graph. Forum 29, 2.
40. Stiny, G. and Gips, J. 1971. Shape grammars and the generative specification of painting and sculpture. In Proceedings of IFIP Congress 71. 1460–1465.
41. Stiny, G. and Mitchell, W. J. 1978. The palladian grammar. Environ. Plan. B: Plan. Des. 5, 1, 5–18.
42. Szeliski, R. and Terzopoulos, D. 1989. From splines to fractals. In Proceedings of the SIGGRAPH Conference. ACM, 51–60.
43. Tierney, L. 1994. Markov chains for exploring posterior distributions. Ann. Statist. 22, 1701–1762.
44. Tierney, L. and Mira, A. 1999. Some adaptive Monte Carlo methods for Bayesian inference. Statist. Med. 18, 2507–2515.
45. Veach, E. and Guibas, L. J. 1997. Metropolis light transport. In Proceedings of the SIGGRAPH Conference. ACM, 65–76.
46. White, S. R. 1984. Concepts of scale in simulated annealing. AIP Conf. Proc. 122, 1, 261–270.
47. Wong, M. T., Zongker, D. E., and Salesin, D. H. 1998. Computer-Generated floral ornament. In Proceedings of the SIGGRAPH Conference. ACM, 423–434.