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

research-article

Computing layouts with deformable templates

Authors:

Yong-Liang Yang,

Peter WonkaAuthors Info & Claims

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

Article No.: 99, Pages 1 - 11

https://doi.org/10.1145/2601097.2601164

Published: 27 July 2014 Publication History

Abstract

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.

Supplementary Material

MP4 File (a99-sidebyside.mp4)

Download
13.28 MB

References

[1]

Aliaga, D., Vanegas, C., and Benes, B. 2008. Interactive Example-Based Urban Layout Synthesis. ACM Trans. Graph. 27, 5.

Digital 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.

Digital Library

[3]

Bao, F., Schwarz, M., and Wonka, P. 2013. Procedural facade variations from a single layout. ACM Trans. Graph. 32, 1, 8.

Digital 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.

[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.

[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.

Digital Library

[7]

cgal, 2012. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.

[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.

Digital Library

[9]

Dai, D., Riemenschneider, H., Schmitt, G., and Van Gool, L. 2013. Example-based facade texture synthesis.

[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.

Digital 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.

[12]

Gurobi Optimization, I., 2014. Gurobi optimizer reference manual.

[13]

Hausner, A. 2001. Simulating decorative mosaics. In Proceedings of SIGGRAPH 2000, 573--580.

Digital 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.

Digital 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.

Digital Library

[16]

Kaplan, C. S., and Salesin, D. H. 2000. Escherization. In Proceedings of SIGGRAPH 2000, 499--510.

Digital Library

[17]

Kaplan, C. S. 2009. Introductory Tiling Theory for Computer Graphics. Morgan-Claypool Publishers.

Digital Library

[18]

Kim, J., and Pellacini, F. 2002. Jigsaw image mosaics. ACM Trans. Graph. 21, 3 (July), 657--664.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

[24]

Merrell, P., Schkufza, E., and Koltun, V. 2010. Computer-generated residential building layouts. ACM Trans. Graph. 29, 6 (Dec.), 181:1--181:12.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[28]

Prokopyev, O., and Karademir, S. 2012. Irregular polyomino tiling via integer programming with application in phased array antenna design.

[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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital Library

Cited By

Wang YWu WFei YZheng L(2025)CVTLayout: Automated generation of mid-scale commercial space layout via Centroidal Voronoi TessellationComputers & Graphics10.1016/j.cag.2025.104175127(104175)Online publication date: Apr-2025
https://doi.org/10.1016/j.cag.2025.104175
Mostafavi Fvan Engelenburg CKhademi SVrachliotis G(2024)Floor plan generation: The interplay among data, machine, and designerInternational Journal of Architectural Computing10.1177/14780771241290649Online publication date: 9-Oct-2024
https://doi.org/10.1177/14780771241290649
Aigerman NGroueix T(2024)Generative Escher MeshesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657452(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657452
Show More Cited By

Index Terms

Computing layouts with deformable templates
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Cephalometric Landmark Tracing Using Deformable Templates
HISB '11: Proceedings of the 2011 IEEE First International Conference on Healthcare Informatics, Imaging and Systems Biology

Automatic detection and identification of landmarks in cephalometry is of great significance to orthognathic surgery and clinic applications. Motivated by the increasing demands of computerized cephalometric analysis, we present a tree-shaped deformable ...
Adaptive Layouts and Nesting Templates for Hypermedia Composite Templates
WebMedia '15: Proceedings of the 21st Brazilian Symposium on Multimedia and the Web

Arranging interface components in a layout model, like a grid, is frequently supported in programming languages. However, in multimedia authoring declarative languages, those facilities are not provided and authors should declare presentation ...
Object Matching Using Deformable Templates

We propose a general object localization and retrieval scheme based on object shape using deformable templates. Prior knowledge of an object shape is described by a prototype template which consists of the representative contour/edges, and a set of ...

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 33, Issue 4

July 2014

1366 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2601097

Issue’s Table of Contents

Copyright © 2014 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 2014

Published in TOG Volume 33, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
1,136
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)6

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang YWu WFei YZheng L(2025)CVTLayout: Automated generation of mid-scale commercial space layout via Centroidal Voronoi TessellationComputers & Graphics10.1016/j.cag.2025.104175127(104175)Online publication date: Apr-2025
https://doi.org/10.1016/j.cag.2025.104175
Mostafavi Fvan Engelenburg CKhademi SVrachliotis G(2024)Floor plan generation: The interplay among data, machine, and designerInternational Journal of Architectural Computing10.1177/14780771241290649Online publication date: 9-Oct-2024
https://doi.org/10.1177/14780771241290649
Aigerman NGroueix T(2024)Generative Escher MeshesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657452(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657452
Fu QHe SLi XFu H(2024)PlanNet: A Generative Model for Component-Based Plan SynthesisIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.327520030:8(4739-4751)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3275200
Zhang HSavov ADillenburger B(2024)MaskPLAN: Masked Generative Layout Planning from Partial Input2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00856(8964-8973)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.00856
Yenew AAssefa BBelay E(2024)HouseGanDi: A Hybrid Approach to Strike a Balance of Sampling Time and Diversity in Floorplan GenerationIEEE Access10.1109/ACCESS.2024.345140612(125235-125252)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3451406
Chen DChen LZhang YLin SYe MSølvsten S(2024)Automated fire risk assessment and mitigation in building blueprints using computer vision and deep generative modelsAdvanced Engineering Informatics10.1016/j.aei.2024.10261462:PAOnline publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1016/j.aei.2024.102614
Yenew AAssefa B(2024)From Algorithms to Architecture: Computational Methods for House Floorplan GenerationSN Computer Science10.1007/s42979-024-02907-05:5Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1007/s42979-024-02907-0
Qin YZhao NYang JPan SSheng BLau R(2024)UrbanEvolver: Function-Aware Urban Layout RegenerationInternational Journal of Computer Vision10.1007/s11263-024-02030-w132:9(3408-3427)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11263-024-02030-w
Fan RWang LLiu XIm SLam C(2024)Real-scene-constrained virtual scene layout synthesis for mixed realityThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-023-03167-440:9(6319-6339)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00371-023-03167-4
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