This paper presents a new polyomino tiling algorithm for three-dimensional surface geometric model. We first apply surface subdivision to the input polygonal mesh or subdivision surface mesh. Then we construct a random Hamiltonian path to connect all subdivided input mesh. This path is used to build initial polyomino tiling on the original input mesh. Finally we apply random polyomino exchanging to the polyomino tiling to get more uniform occurrence of each polyomino types. Our method is applicable to construct three-dimensional puzzle and we show the results of proposed algorithm on three-dimensional mesh data.

폴리노미오는 하나 이상의 정사각형이 연결되어 만들어지는 다각형으로 퍼즐 게임에서 다양하게 사용된다. 폴리노미오를 일정한 크기의 보드에 타일링하기 위해서 기존에는 주로 백트래킹(backtracking)을 이용한 전체 탐색(exhaustive search) 방법을 사용하였다. 이러한 방법은 정확한 조건을 만족하는 경우를 찾을 때 사용되어 왔으며 각 폴리오미노의 개수를 엄밀하게 만족할 필요가 없는 퍼즐의 타일링 경우에도 주로 이용해 왔다. 본 논문에서는 랜덤하게 폴리노미오를 조합하여 구성하는 타일링에 적합한 새로운 생성 방법을 제안한다.