Shape Collections
Generating Design Suggestions under Tight Constraints with Gradient-based Probabilistic Programming
Abstract
We present a system for generating suggestions from highly-constrained, continuous design spaces. We formulate suggestion as sampling from a probability distribution; constraints are represented as factors that concentrate probability mass around sub-manifolds of the design space. These sampling problems are intractable using typical random walk MCMC techniques, so we adopt Hamiltonian Monte Carlo (HMC), a gradient-based MCMC method. We implement HMC in a high-performance probabilistic programming language, and we evaluate its ability to efficiently generate suggestions for two different, highly-constrained example applications: vector art coloring and designing stable stacking structures.
Supporting Information
| Filename | Description |
|---|---|
| cgf12580-sup-0001-S1.mp4124.3 MB | Supporting Information |
Please note: The publisher is not responsible for the content or functionality of any supporting information supplied by the authors. Any queries (other than missing content) should be directed to the corresponding author for the article.
References
- Bergman R.: Wood Handbook âÂŞ Wood as an Engineering Material. Forest Products Laboratory, 2010. 10
- Brubaker M.A., Salzmann M., Urtasun R.: A family of mcmc methods on implicitly defined manifolds. In Proc. AISTATS 2012 (2012). 10
- Bao F., Yan D.-M., Mitra N.J., Wonka P.: Generating and exploring good building layouts. In Proc. SIGGRAPH 2013 (2013), SIGGRAPH ‘13. 2
- Corliss G., Faure C., Griewank A., Hascoët L., NAUMANN U.: Automatic Differentiation: From Simulation to Optimization. Computer and Information Science. Springer, 2001. 5
- Chaudhuri S., Solar-Lezama A.: Smooth interpretation. In Proc. PLDI 2010 (2010). 10
- Dow S.P., Glassco A., Kass J., Schwarz M., Schwartz D.L., Klemmer S.R.: Parallel prototyping leads to better design results, more divergence, and increased self-efficacy. ACM Trans. Comput.-Hum. Interact. 17, 4 (2010). 1
- DeVito Z., Hegarty J., Aiken A., Hanrahan P., Vitek J.: Terra: A multi-stage language for high-performance computing. In Proc. PLDI 2013 (2013). 2, 5
- Duane S., Kennedy A., Pendleton B.J., Roweth D.: Hybrid monte carlo. Physics Letters B 195, 2 (1987), 216–222. 4
- Fisher M., Ritchie D., Savva M., Funkhouser T., Hanrahan P.: Example-based synthesis of 3d object arrangements. In Proc. SIGGRAPH Asia 2012 (2012), SA ‘12. 2
- Goodman N.D., Mansinghka V.K., Roy D.M., Bonawitz K., Tenenbaum J.B.: Church: a language for generative models. In Proc. of UAI 2008 (2008). 2
- Guenter B.: Efficient symbolic differentiation for graphics applications. In Proc. SIGGRAPH ‘07' (2007), SIGGRAPH ‘07. 5
- Hoffman M.D., Gelman A.: The no-U-turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo. Journal of Machine Learning Research (2014). 5
- Huang Q., Zhang J., Sabbaghi A., Dasgupta T.: Optimal offline compensation of shape shrinkage for 3d printing processes. IIE Transactions on Quality and Reliability. 3
- Jakob W., Marschner S.: Manifold exploration: a markov chain monte carlo technique for rendering scenes with difficult specular transport. In Proc. SIGGRAPH 2012 (2012), SIGGRAPH ‘12. 2
- Jansson D., Smith S.: Design fixation. Design studies 12, 1 (1991). 1
10.1016/0142-694X(91)90003-F Google Scholar
- Jain A., Thormählen T., Ritschel T., Seidel H.-P.: Exploring shape variations by 3d-model decomposition and part-based recombination. Comp. Graph. Forum 31, 2pt3 (2012). 2
- Jain A., Thormählen T., Ritschel T., Seidel H.-P.: Material memex: Automatic material suggestions for 3d objects. In Proc. SIGGRAPH Asia 2012 (2012), SA ‘12. 2
- Kass R.E., Carlin B.P., Gelman A., Neal R.M.: Markov chain monte carlo in practice: A roundtable discussion. The American Statistician 52, 2 (1998). 4
- Kalogerakis E., Chaudhuri S., Koller D., Koltun V.: A probabilistic model for component-based shape synthesis. In Proc. SIGGRAPH 2012 (2012), SIGGRAPH ‘12. 2
- Kulkarni C., Dow S.P., Klemmer S.R.: Early and repeated exposure to examples improves creative work. In Design Thinking Research. Springer, 2014. 1
- Leimkuhler B., Reich S.: Simulating Hamiltonian Dynamics. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2004. 4
- Lin S., Ritchie D., Fisher M., Hanrahan P.: Probabilistic color-by-numbers: Suggesting pattern colorizations using factor graphs. In Proc. SIGGRAPH 2013 (2013), SIGGRAPH ‘13. 1, 3, 5, 12
- Marks J., Andalman B., Beardsley P.A., Freeman W., Gibson S., Hodgins J., Kang T., Mirtich B., Pfister H., Ruml W., Ryall K., Seims J., Shieber S.: Design galleries: A general approach to setting parameters for computer graphics and animation. In Proc. SIGGRAPH 1997 (1997), SIGGRAPH ‘97. 2
10.1145/258734.258887 Google Scholar
- Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H., Teller E.: Equation of State Calculations by Fast Computing Machines. The Journal of Computational Physics 21 (June 1953). 3
- Merrell P., Schkufza E., Li Z., Agrawala M., Koltun V.: Interactive furniture layout using interior design guidelines. In Proc. SIGGRAPH 2011 (2011), SIGGRAPH ‘11. 2, 3
- Neal R.M.: MCMC using Hamiltonian dynamics. Handbook of Markov Chain Monte Carlo (2010). 2, 3, 4
- O'Donovan P., Agarwala A., Hertzmann A.: Color Compatibility From Large Datasets. ACM Transactions on Graphics (2011). 5
- Ou L.-C., Luo M.R.: A colour harmony model for two-colour combinations. Color Research & Application (2006). 5
- Prévost R., Whiting E., Lefebvre S., Sorkine-Hornung O.: Make It Stand: Balancing shapes for 3D fabrication. In Proc. SIGGRAPH 2013 (2013). 7
- Roberts G.O., Gelman A., Gilks W.R.: Weak convergence and optimal scaling of random walk metropolis algorithms. The Annals of Applied Probability 7, 1 (1997). 5
- Ritchie D.: Quicksand: Low-level probabilistic programming in Terra. http://dritchie.github.io/quicksand, 2014. 2, 3, 5
- Smith J., Hodgins J., Oppenheim I., Witkin A.: Creating models of truss structures with optimization. In Proc. SIGGRAPH 2002 (2002). 7
- Speelpenning B.: Compiling Fast Partial Derivatives of Functions Given by Algorithms. PhD thesis, Champaign, IL, USA, 1980. 5
- Stan Development Team: Stan Modeling Language Users Guide and Reference Manual, Version 2.2, 2014. URL: http://mc-stan.org/. 3, 5
- Schwartz M., Wonka P.: Procedural design of exterior lighting for buildings with complex constraints. ACM Transactions on Graphics (2014). 2
- Talton J.O., Lou Y., Lesser S., Duke J., Mēch R., Koltun V.: Metropolis procedural modeling. ACM Trans. Graph. 30, 2 (2011). 2, 3
- Umetani N., Igarashi T., Mitra N.J.: Guided exploration of physically valid shapes for furniture design. In Proc. SIGGRAPH 2012 (2012), SIGGRAPH ‘12. 2, 12
- Wingate D., Goodman N.D., Stuhlmüller A., Siskind J.M.: Nonstandard interpretations of probabilistic programs for efficient inference. In Proc. NIPS 2011 (2011). 3
- Whiting E., Ochsendorf J., Durand F.: Procedural modeling of structurally-sound masonry buildings. In Proc. SIGGRAPH Asia 2009 (2009). 7, 12
10.1145/1661412.1618458 Google Scholar
- Xu K., Zhang H., Cohen-Or D., Chen B.: Fit and diverse: Set evolution for inspiring 3d shape galleries. In Proc. SIGGRAPH 2012 (2012), SIGGRAPH ‘12. 2
- Yeh Y.-T., Breeden K., Yang L., Fisher M., Hanrahan P.: Synthesis of tiled patterns using factor graphs. ACM Trans. Graph. 32, 1 (2013). 2
- Yang Y.-L., Yang Y.-J., Pottmann H., Mitra N.J.: Shape space exploration of constrained meshes. In Proc. SIGGRAPH Asia 2011 (2011), SA ‘11. 2
- Yeh Y.-T., Yang L., Watson M., Goodman N.D., Hanrahan P.: Synthesizing open worlds with constraints using locally annealed reversible jump mcmc. In Proc. SIGGRAPH 2012 (2012), SIGGRAPH ‘12. 1, 2, 5
- Zucker M., Ratliff N., Dragan A., Pivtoraiko M., Klingensmith M., Dellin C., Bagnell J. A. D., Srinivasa S.: Chomp: Covariant hamiltonian optimization for motion planning. International Journal of Robotics Research (May 2013). 3
