“Computing layouts with deformable templates” by Peng, Yang and Wonka

  • ©Chi-Han Peng, Yong-Liang Yang, and Peter Wonka




    Computing layouts with deformable templates

Session/Category Title:   Layout Building & Scenes




    In this paper, we tackle the problem of tiling a domain with a set of deformable templates. A valid solution to this problem completely covers the domain with templates such that the templates do not overlap. We generalize existing specialized solutions and formulate a general layout problem by modeling important constraints and admissible template deformations. Our main idea is to break the layout algorithm into two steps: a discrete step to lay out the approximate template positions and a continuous step to refine the template shapes. Our approach is suitable for a large class of applications, including floorplans, urban layouts, and arts and design.


    1. Aliaga, D., Vanegas, C., and Benes, B. 2008. Interactive Example-Based Urban Layout Synthesis. ACM Trans. Graph. 27, 5. Google ScholarDigital Library
    2. Aliaga, D. G., Beneš, B., Vanegas, C. A., and Andrysco, N. 2008. Interactive Reconfiguration of Urban Layouts. IEEE Computer Graphics and Applications 28, 3, 38–47. Google ScholarDigital Library
    3. Bao, F., Schwarz, M., and Wonka, P. 2013. Procedural facade variations from a single layout. ACM Trans. Graph. 32, 1, 8. Google ScholarDigital Library
    4. Blacker, T. D., and Stephenson, M. B. 1991. Paving: A new approach to automated quadrilateral mesh generation. International Journal for Numerical Methods in Engineering 32, 4, 811–847.Google ScholarCross Ref
    5. Bommes, D., Lvy, B., Pietroni, N., Puppo, E., a, C. S., Tarini, M., and Zorin, D. 2012. State of the art in quad meshing. In Eurographics STARS.Google Scholar
    6. Bouaziz, S., Deuss, M., Schwartzburg, Y., Weise, T., and Pauly, M. 2012. Shape-up: Shaping discrete geometry with projections. Comp. Graph. Forum 31, 5 (Aug.), 1657–1667. Google ScholarDigital Library
    7. cgal, 2012. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.Google Scholar
    8. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Trans. Graph. 22, 3, 287–294. Google ScholarDigital Library
    9. Dai, D., Riemenschneider, H., Schmitt, G., and Van Gool, L. 2013. Example-based facade texture synthesis.Google Scholar
    10. Demaine, E. D., and Demaine, M. L. 2007. Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graph. Comb. 23, 1 (Feb.), 195–208. Google ScholarDigital Library
    11. Fasano, G. 2004. A mip approach for some practical packing problems: Balancing constraints and tetris-like items. Quarterly Journal of the Belgian, French and Italian Operations Research Societies 2, 2, 161–174.Google Scholar
    12. Gurobi Optimization, I., 2014. Gurobi optimizer reference manual.Google Scholar
    13. Hausner, A. 2001. Simulating decorative mosaics. In Proceedings of SIGGRAPH 2000, 573–580. Google ScholarDigital Library
    14. Huang, H., Zhang, L., and Zhang, H.-C. 2011. Arcimboldo-like collage using internet images. ACM Trans. Graph. 30, 6 (Dec.), 155:1–155:8. Google ScholarDigital Library
    15. Kalogerakis, E., Chaudhuri, S., Koller, D., and Koltun, V. 2012. A probabilistic model for component-based shape synthesis. ACM Trans. Graph. 31, 4, 55. Google ScholarDigital Library
    16. Kaplan, C. S., and Salesin, D. H. 2000. Escherization. In Proceedings of SIGGRAPH 2000, 499–510. Google ScholarDigital Library
    17. Kaplan, C. S. 2009. Introductory Tiling Theory for Computer Graphics. Morgan-Claypool Publishers. Google ScholarDigital Library
    18. Kim, J., and Pellacini, F. 2002. Jigsaw image mosaics. ACM Trans. Graph. 21, 3 (July), 657–664. Google ScholarDigital Library
    19. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. ACM Trans. Graph., 509–518. Google ScholarDigital Library
    20. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3, 362–371. Google ScholarDigital Library
    21. Lin, J., Cohen-Or, D., Zhang, H., Liang, C., Sharf, A., Deussen, O., and Chen, B. 2011. Structure-preserving retargeting of irregular 3D architecture. ACM Trans. Graph. 30, 6, 183:1–183:10. Google ScholarDigital Library
    22. Liu, Y., Xu, W., Wang, J., Zhu, L., Guo, B., Chen, F., and Wang, G. 2011. General planar quadrilateral mesh design using conjugate direction field. ACM Trans. Graph. 30, 6 (Dec.), 140:1–140:10. Google ScholarDigital Library
    23. Majerowicz, L., Shamir, A., Sheffer, A., and Hoos, H. H. 2014. Filling your shelves: Synthesizing diverse style-preserving artifact arrangements. IEEE Transactions on Visualization and Computer Graphics.Google ScholarCross Ref
    24. Merrell, P., Schkufza, E., and Koltun, V. 2010. Computer-generated residential building layouts. ACM Trans. Graph. 29, 6 (Dec.), 181:1–181:12. Google ScholarDigital Library
    25. Merrell, P., Schkufza, E., Li, Z., Agrawala, M., and Koltun, V. 2011. Interactive furniture layout using interior design guidelines. ACM Trans. Graph. 30, 4 (July), 87:1–87:10. Google ScholarDigital Library
    26. Park, C., Noh, J.-S., Jang, I.-S., and Kang, J. M. 2007. A new automated scheme of quadrilateral mesh generation for randomly distributed line constraints. Computer Aided Design 39, 4 (Apr.), 258–267. Google ScholarDigital Library
    27. Peng, C.-H., Barton, M., Jiang, C., and Wonka, P. 2014. Exploring quadrangulations. ACM Trans. Graph. 33, 1 (Feb.), 12:1–12:13. Google ScholarDigital Library
    28. Prokopyev, O., and Karademir, S. 2012. Irregular polyomino tiling via integer programming with application in phased array antenna design.Google Scholar
    29. Reinert, B., Ritschel, T., and Seidel, H.-P. 2013. Interactive by-example design of artistic packing layouts. ACM Trans. Graph. 32, 6 (Nov.), 218:1–218:7. Google ScholarDigital Library
    30. Vanegas, C. A., Kelly, T., Weber, B., Halatsch, J., Aliaga, D., and Müller, P. 2012. Procedural generation of parcels in urban modeling. Comput. Graph. Forum 31, 2. Google ScholarDigital Library
    31. Yang, Y.-L., Wang, J., Vouga, E., and Wonka, P. 2013. Urban pattern: Layout design by hierarchical domain splitting. ACM Trans. Graph. 32, 6 (Nov.), 181:1–181:12. Google ScholarDigital Library
    32. 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. ACM Trans. Graph. 31, 4. Google ScholarDigital Library
    33. Yeh, Y.-T., Breeden, K., Yang, L., Fisher, M., and Hanrahan, P. 2013. Synthesis of tiled patterns using factor graphs. ACM Trans. Graph. 32, 1 (Feb.), 3:1–3:13. Google ScholarDigital Library
    34. Yu, L.-F., Yeung, S.-K., Tang, C.-K., Terzopoulos, D., Chan, T. F., and Osher, S. J. 2011. Make it home: Automatic optimization of furniture arrangement. ACM Trans. Graph. 30, 4 (July), 86:1–86:12. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: