More Web Proxy on the site http://driver.im/

research-article

Controlling procedural modeling programs with stochastically-ordered sequential Monte Carlo

Authors:

Daniel Ritchie,

Ben Mildenhall,

Noah D. Goodman,

Pat HanrahanAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 34, Issue 4

Article No.: 105, Pages 1 - 11

https://doi.org/10.1145/2766895

Published: 27 July 2015 Publication History

Abstract

We present a method for controlling the output of procedural modeling programs using Sequential Monte Carlo (SMC). Previous probabilistic methods for controlling procedural models use Markov Chain Monte Carlo (MCMC), which receives control feedback only for completely-generated models. In contrast, SMC receives feedback incrementally on incomplete models, allowing it to reallocate computational resources and converge quickly. To handle the many possible sequentializations of a structured, recursive procedural modeling program, we develop and prove the correctness of a new SMC variant, Stochastically-Ordered Sequential Monte Carlo (SOSMC). We implement SOSMC for general-purpose programs using a new programming primitive: the stochastic future. Finally, we show that SOSMC reliably generates high-quality outputs for a variety of programs and control scoring functions. For small computational budgets, SOSMC's outputs often score nearly twice as high as those of MCMC or normal SMC.

References

[1]

Andrieu, C., Doucet, A., and Holenstein, R. 2010. Particle Markov Chain Monte Carlo Methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 72, 3.

[2]

Beneš, B., Šava, O., Měch, R., and Miller, G. 2011. Guided Procedural Modeling. In Proc. Eurographics 2011.

[3]

Bisiani, R. 1987. Beam Search. In Encyclopedia of Artificial Intelligence, S. Shapiro, Ed.

[4]

de Moura, A. L., and Ierusalimschy, R. 2004. Revisiting Coroutines. Tech. rep.

[5]

DeVito, Z., Hegarty, J., Aiken, A., Hanrahan, P., and Vitek, J. 2013. Terra: A Multi-stage Language for High-performance Computing. In Proc. PLDI 2013.

Digital Library

[6]

Douc, R., and Cappe, O. 2005. Comparison of Resampling Schemes for Particle Filtering. In Proc. ISPA 2005.

[7]

Doucet, A., De Freitas, N., and Gordon, N., Eds. 2001. Sequential Monte Carlo Methods in Practice. Springer.

[8]

Fan, S. 2006. Sequential Monte Carlo Methods for Physically Based Rendering. PhD thesis.

Digital Library

[9]

Gershman, S., and Goodman, N. D. 2014. Amortized Inference in Probabilistic Reasoning. In Proceedings of the Thirty-Sixth Annual Conference of the Cognitive Science Society.

[10]

Gilks, W. R., and Berzuini, C. 2001. Following a moving target---Monte Carlo inference for dynamic Bayesian models. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 63, 1.

[11]

Goodman, N. D., and Stuhlmüller, A., 2014. The Design and Implementation of Probabilistic Programming Languages. Retrieved 2014/12/15 from http://dippl.org.

[12]

Goodman, N. D., Mansinghka, V. K., Roy, D. M., Bonawitz, K., and Tenenbaum, J. B. 2008. Church: a language for generative models. In Proc. of UAI 2008.

[13]

Gordon, N., Salmond, D., and Smith, A. 1993. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. Radar and Signal Processing, IEE Proceedings F 140, 2.

[14]

Halstead, Jr., R. H. 1985. MULTILISP: A Language for Concurrent Symbolic Computation. ACM Trans. Program. Lang. Syst. 7, 4.

Digital Library

[15]

Hammersley, J. M., and Morton, K. W. 1954. Poor Man's Monte Carlo. Journal of the Royal Statistical Society. Series B (Methodological) 16, 1.

[16]

Hello Games, 2014. No Man's Sky. Retrieved 2014/12/18 from http://www.no-mans-sky.com/.

[17]

Hmlinen, P., Eriksson, S., Tanskanen, E., Kyrki, V., and Lehtinen, J. 2014. Online Motion Synthesis Using Sequential Monte Carlo. In Proc. SIGGRAPH 2014.

[18]

Kulkarni, T. D., Mansinghka, V. K., Kohli, P., and Tenenbaum, J. B. 2014. Inverse Graphics with Probabilistic CAD Models. CoRR.

[19]

Levy, R. P., Reali, F., and Griffiths, T. L. 2009. Modeling the effects of memory on human online sentence processing with particle filters. In In Proc. NIPS 2009.

[20]

Lindsten, F., Jordan, M. I., and Schön, T. B. 2014. Particle Gibbs with Ancestor Sampling. J. Mach. Learn. Res. 15, 1.

Digital Library

[21]

Müller, P., Wonka, P., Haegler, S., Ulmer, A., and Van Gool, L. 2006. Procedural Modeling of Buildings. In In Proc. SIGGRAPH 2006.

Digital Library

[22]

Měch, R., and Prusinkiewicz, P. 1996. Visual Models of Plants Interacting with Their Environment. In Proc. SIGGRAPH 1996.

Digital Library

[23]

Paige, B., and Wood, F. 2014. A Compilation Target for Probabilistic Programming Languages. In Proc. ICML 2014.

[24]

Paige, B., Wood, F., Doucet, A., and Teh, Y. 2014. Asynchronous Anytime Sequential Monte Carlo. In Proc. NIPS 2014.

[25]

Pegoraro, V., Wald, I., and Parker, S. G. 2008. Sequential Monte Carlo Adaptation in Low-Anisotropy Participating Media. Computer Graphics Forum 27, 4.

Digital Library

[26]

Procedural Reality, 2014. Limit Theory. Retrieved 2014/12/18 from http://ltheory.com.

[27]

Prusinkiewicz, P., JAMES, M., and Měch, R. 1994. Synthetic Topiary. In Proc. SIGGRAPH 1994.

Digital Library

[28]

Ritchie, D., Lin, S., Goodman, N. D., and Hanrahan, P. 2015. Generating Design Suggestions under Tight Constraints with Gradient-based Probabilistic Programming. In Proc. Eurographics 2015.

[29]

Rosenbluth, M. N., and Rosenbluth, A. W. 1955. Monte Carlo Calculation of the Average Extension of Molecular Chains. The Journal of Chemical Physics 23, 2.

[30]

Smith, A. F. M., and Gelfand, A. E. 1992. Bayesian Statistics without Tears: A Sampling-Resampling Perspective. The American Statistician 46, 2.

[31]

Stava, O., Pirk, S., Kratt, J., Chen, B., Mch, R., Deussen, O., and Benes, B. 2014. Inverse Procedural Modelling of Trees. Computer Graphics Forum 33, 6.

Digital Library

[32]

Stewart, L., and McCarty, Jr., P. 1992. Use of Bayesian belief networks to fuse continuous and discrete information for target recognition, tracking, and situation assessment. Proc. SPIE.

[33]

Talton, J. O., Lou, Y., Lesser, S., Duke, J., Měch, R., and Koltun, V. 2011. Metropolis Procedural Modeling. ACM Trans. Graph. 30, 2.

Digital Library

[34]

Vanegas, C. A., Garcia-Dorado, I., Aliaga, D. G., Benes, B., and Waddell, P. 2012. Inverse Design of Urban Procedural Models. In Proc. SIGGRAPH Asia 2012.

Digital Library

[35]

Veach, E., and Guibas, L. J. 1995. Optimally Combining Sampling Techniques for Monte Carlo Rendering. In Proc. SIGGRAPH 1995, SIGGRAPH '95.

Digital Library

[36]

Wingate, D., Stuhlmüller, A., and Goodman, N. D. 2011. Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation. In Proc. AISTATS 2011.

[37]

Wong, M. T., Zongker, D. E., and Salesin, D. H. 1998. Computer-generated Floral Ornament. In In Proc. SIGGRAPH 1998.

Digital Library

[38]

Wood, F., van De Meent, J. W., and Mansinghka, V. 2014. A New Approach to Probabilistic Programming Inference. In Proc. AISTATS 2014.

[39]

Xu, K., Zhang, H., Cohen-Or, D., and Chen, B. 2012. Fit and diverse: Set evolution for inspiring 3d shape galleries. In Proc. SIGGRAPH 2012, SIGGRAPH '12.

Digital Library

[40]

Yeh, Y.-T., Yang, L., Watson, M., Goodman, N. D., and Hanrahan, P. 2012. Synthesizing Open Worlds with Constraints Using Locally Annealed Reversible Jump MCMC. In Proc. SIGGRAPH 2012.

Digital Library

Cited By

Pearl OLang IHu YYeh RHanocka R(2025)GeoCode: Interpretable Shape ProgramsComputer Graphics Forum10.1111/cgf.15276Online publication date: 12-Feb-2025
https://doi.org/10.1111/cgf.15276
Zhang JWillis A(2024)Bridging Formal Shape Models and Deep Learning: A Novel Fusion for Understanding 3D ObjectsSensors10.3390/s2412387424:12(3874)Online publication date: 15-Jun-2024
https://doi.org/10.3390/s24123874
Perkins RVentura DLarson K(2024)Musical phrase segmentation via grammatical inductionProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/855(7726-7734)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/855
Show More Cited By

Index Terms

Controlling procedural modeling programs with stochastically-ordered sequential Monte Carlo
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Interacting sequential Monte Carlo samplers for trans-dimensional simulation

The methodology of interacting sequential Monte Carlo (SMC) samplers is introduced. SMC samplers are methods for sampling from a sequence of densities on a common measurable space using a combination of Markov chain Monte Carlo (MCMC) and sequential ...
An adaptive sequential Monte Carlo method for approximate Bayesian computation

Approximate Bayesian computation (ABC) is a popular approach to address inference problems where the likelihood function is intractable, or expensive to calculate. To improve over Markov chain Monte Carlo (MCMC) implementations of ABC, the use of ...
Multilevel Sequential Monte Carlo Samplers for Normalizing Constants

This article considers the Sequential Monte Carlo (SMC) approximation of ratios of normalizing constants associated to posterior distributions which in principle rely on continuum models. Therefore, the Monte Carlo estimation error and the discrete ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 34, Issue 4

August 2015

1307 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2809654

Issue’s Table of Contents

Copyright © 2015 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 ACM 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 [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2015

Published in TOG Volume 34, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DARPA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
816
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)2

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pearl OLang IHu YYeh RHanocka R(2025)GeoCode: Interpretable Shape ProgramsComputer Graphics Forum10.1111/cgf.15276Online publication date: 12-Feb-2025
https://doi.org/10.1111/cgf.15276
Zhang JWillis A(2024)Bridging Formal Shape Models and Deep Learning: A Novel Fusion for Understanding 3D ObjectsSensors10.3390/s2412387424:12(3874)Online publication date: 15-Jun-2024
https://doi.org/10.3390/s24123874
Perkins RVentura DLarson K(2024)Musical phrase segmentation via grammatical inductionProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/855(7726-7734)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/855
Ben Amara OHadouaj SMeneghetti N(2024)StarfishDB: A Query Execution Engine for Relational Probabilistic ProgrammingProceedings of the ACM on Management of Data10.1145/36549882:3(1-31)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654988
Li YMa TAljumayaat ZRitchie D(2024)PossibleImpossibles: Exploratory Procedural Design of Impossible StructuresComputer Graphics Forum10.1111/cgf.1505243:2Online publication date: 27-Apr-2024
https://doi.org/10.1111/cgf.15052
Merrell P(2023)Example-Based Procedural Modeling Using Graph GrammarsACM Transactions on Graphics10.1145/359211942:4(1-16)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592119
Niese TPirk SAlbrecht MBenes BDeussen O(2022)Procedural Urban ForestryACM Transactions on Graphics10.1145/350222041:2(1-18)Online publication date: 3-Mar-2022
https://dl.acm.org/doi/10.1145/3502220
Gaillard MKrs VGori GMěch RBenes B(2022)Automatic Differentiable Procedural ModelingComputer Graphics Forum10.1111/cgf.1447541:2(289-307)Online publication date: 24-May-2022
https://doi.org/10.1111/cgf.14475
Li YKong TLi LWu Y(2022)Learning Design and Construction with Varying-Sized Materials via Prioritized Memory Resets2022 International Conference on Robotics and Automation (ICRA)10.1109/ICRA46639.2022.9811624(7469-7476)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.1109/ICRA46639.2022.9811624
Lin CFang LLi SLuo BLin J(2022)Hybrid Artificial Immune System for Controlled Procedural Modeling2022 IEEE 2nd International Conference on Power, Electronics and Computer Applications (ICPECA)10.1109/ICPECA53709.2022.9719153(1197-1206)Online publication date: 21-Jan-2022
https://doi.org/10.1109/ICPECA53709.2022.9719153
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents