TilinGNN: Learning to Tile with Self-Supervised Graph Neural Network

Hao Xu*¹

Ka-Hei Hui*¹

Chi-Wing Fu¹

Hao Zhang²

(* joint 1st authors)

SIGGRAPH 2020

Our self-supervised neural network, TilinGNN, produces tiling results in time roughly linear to the number of candidate tile locations, significantly outperforming traditional combinatorial search methods. The average runtime of our network for tiling a character is only 25.71s. The character shapes to be tiled are shown in grey and different types of tiles are displayed using different colors (note that mirror reflections count as different tile types).

Abstract

We introduce the first neural optimization framework to solve a classical instance of the tiling problem. Namely, we seek a non-periodic tiling of an arbitrary 2D shape using one or more types of tiles—the tiles maximally fill the shape’s interior without overlaps or holes. To start, we reformulate tiling as a graph problem by modeling candidate tile locations in the target shape as graph nodes and connectivity between tile locations as edges. Further, we build a graph convolutional neural network, coined TilinGNN, to progressively propagate and aggregate features over graph edges and predict tile placements. TilinGNN is trained by maximizing the tiling coverage on target shapes, while avoiding overlaps and holes between the tiles. Importantly, our network is self-supervised, as we articulate these criteria as loss terms defined on the network outputs, without the need of ground-truth tiling solutions. After training, the runtime of TilinGNN is roughly linear to the number of candidate tile locations, significantly outperforming traditional combinatorial search. We conducted various experiments on a variety of shapes to showcase the speed and versatility of TilinGNN. We also present comparisons to alternative methods and manual solutions, robustness analysis, and ablation studies to demonstrate the quality of our approach.

Results

A gallery, showcasing the tiling solutions produced by our learn-to-tile approach on 36 different shapes. Under each tiling solution, we show the original input shape in gray and the region covered by the union of all the candidate tile locations (inside the input shape) in blue, as references.

Paper and Supplementary Material

TilinGNN: Learning to Tile with Self-Supervised Graph Neural Network
In SIGGRAPH 2020.
[Paper] [supp] [presentation] [data & code]

Video

Bibtex

            @article {xu-sig20-tilingnn,
                author = {Hao Xu* and Ka Hei Hui* and Chi-Wing Fu and Hao Zhang (* joint first authors)},
                title = {TilinGNN: Learning to Tile with Self-Supervised Graph Neural Network},
                journal = {ACM Trans. on Graphics (SIGGRAPH)},
                volume = 39,
                number = 4,
                year = {2020},
                note = {Article no. 129},
            }

Acknowledgments

We thank all the anonymous reviewers for their comments and feedback. Figures 2(a), (b), and (c) are courtesy of National Trust of Australia (Victoria), Erhan Cubukcuoglu, and Katie Walker, respectively. This work is supported in part by grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project no. CUHK 14201717 and 14201918), NSERC grants (No. 611370), and gift funds from Adobe.