The tiling problem is the decision problem to determine if the infinite plane can be tiled by copies of finitely many given Wang tiles. The problem is known since the 1960's to be undecidable. The undecidability is closely related to the existence of aperiodic Wang tile sets. There is a known method to construct small aperiodic tile sets that simulate iterations of one-dimensional piecewise linear functions using encodings of real numbers as Sturmian sequences. In this paper we provide details of a similar simulation of two-dimensional piecewise affine functions byWang tiles. Mortality of such functions is undecidable, which directly yields another proof of the undecidability of the tiling problem. We apply the same technique on the hyperbolic plane to provide a strongly aperiodic hyperbolic Wang tile set and to prove that the hyperbolic tiling problem is undecidable. These results are known in the literature but using different methods.
Praca opisuje metody pokrywania trójkątnymi płytkami dowolnych powierzchni trójwymiarowych reprezentowanych przez siatki trójkątowe. Omówione są znane metody konstruowania i układania trójkątnych płytek oraz ich optymalizacja algorytmami kolorowania grafów. Zaproponowana jest również ulepszona, hybrydowa metoda, umożliwiająca pokrycie dowolnej powierzchni wzorem, który wymaga kierunkowego uporządkowania. Przykładem zastosowań może być modelowanie wzorów na futrze zwierząt (np. paski zebry, cętki lamparta) oraz wzorów składających się z łusek (występujących u ryb i gadów). Metoda umożliwia optymalizację ilości pamięci zajmowanej przez teksturę oraz automatyczne pokrywanie wzorem geometrii generowanej proceduralnie.
EN
This paper describes methods of tiling arbitrary three-dimensional surfaces represented by triangular networks with triangular texture tiles. Despite two simple well known tiling methods, an interesting hybrid approach is proposed for tiling directional textures such as fish scales. An example of usage is modeling animal fur patterns, such as zebra stripes or scale patterns that can be found on fish and reptiles. The main advantage of proposed method over alternative texture mapping techniques is texture memory optimization. The method also provides an easy to implement solution for texturing procedurally generated animals (creatures).
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.