Capturing the frugal beauty of complex natural tessellations

November 21, 2018, Association for Computing Machinery
Amelia Earhart's Flight Suit (10M?) with 10 000 seeds, the resulting cells are visualized in different colors. A close-up of the cell distribution (top row) and the underlying mesh (middle and bottom rows) reveals small scale geometric complexity (pocket fold, button fold) that can successfully be processed with our computationally- and memory efficient approach.) Credit: SIGGRAPH ASIA

Surface tessellations are an arrangement of shapes which are tightly fitted, and form repeat patterns on a surface without overlapping. Imagine the pattern of a giraffe's fur, the shell of a tortoise and the honeycomb of bees—all form natural tessellations. Mimicking these natural designs computationally is a complex, multi-disciplinary problem. A global team of computer scientists has developed a new, alternate model for replicating these intricate surface designs, veering away from classical, multi-step approaches to a more efficient, streamlined algorithm.

"When we look at how natural tessellation occurs in nature, the grow simultaneously, and each individual cell does not necessarily know who are its neighboring cells nor their location or coordinates," explains lead author of the work, Rhaleb Zayer, researcher at Max Planck Institute for Informatics in Saarbrücken, Germany. Cells represent the shape or tiles that comprise intricate tessellation patterns. "To capture this behavior, we need to adopt an intrinsic view of the problem and depart from the widely adopted extrinsic perspective which requires full knowledge of all individual cell interactions and locations."

Typically, researchers have turned to the Voronoi model to mimic such repeat surface patterns. In mathematics, A Voronoi diagram partitions planes in a pattern based on the distances between points. Efforts at extending the same idea to surfaces are hampered by the extensive costs of accurate distance measurements, bookkeeping and intersection computations.

In this new work, researchers simplify the creation of natural tessellations on surface meshes by dropping the assumption that regions need to be separated by lines. Instead, they have developed a that takes into account region boundaries in the pattern as narrow bands, which are not necessarily straight, and model the partition as a set of smooth functions layered over the . Their method relies mainly on basic sparse linear algebra kernels, i.e. multiplication and addition, readily available, as they are the cornerstone of modern numerical computing.

"In this way, we provide small, concise, humanly readable and most importantly, platform-independent parallel code," notes Zayer.

"Observing the progress made in parallelizing existing serial Voronoi diagram codes over the last two decades, the performance gains achieved by our proposed method are very considerable," adds Markus Steinberger, coauthor of the work and an assistant professor at Graz University of Technology in Austria.

Zayer, Steinberger and their collaborators, which include Hans-Peter Seidel at Max Planck Institute for Informatics, and Daniel Mlakar at Graz University of Technology, will present their novel method at SIGGRAPH Asia 2018 in Tokyo 4 December to 7 December. The annual conference features the most respected technical and creative members in the field of computer graphics and interactive techniques, and showcases leading edge research in science, art, gaming and animation, among other sectors.

In their paper, "Layered Fields for Natural Tessellations on Surfaces," the authors successfully demonstrate their new method on several large-scale test cases beyond the capabilities of state-of-the-art. They were able to show that their method is applicable to highly detailed models, such as the 3-D Model of the famed pilot Amelia Earhart's flight suit, encompassing ten million facets. Tessellations on the scan of the highly ornamented historic Pergolesi Side Chair showcase 30 million facets processed fully and efficiently on a single modern graphics-processing unit, aka, GPU. Despite the simplicity of the algorithm, the researchers say their solution proved to be comprehensive with minimal requirements.

In future work, Zayer and team hope to add the function of interactively editing tessellations using their framework. This feature could be aimed at designers and architects new to 3-D printing applications and modeling. The researchers also intend to extend this work to higher dimensions and to the treatment of other metrics.

Explore further: Exploring tessellations beyond Escher

More information: sa2018.siggraph.org/en/attende … s/session/32/details

Related Stories

Exploring tessellations beyond Escher

June 16, 2011

(PhysOrg.com) -- By incorporating geometrical concepts into his artwork, M. C. Escher demonstrated the potential beauty that could be achieved by combining mathematics and art. One of Escher's most well-known types of art ...

Recommended for you

Uber filed paperwork for IPO: report

December 8, 2018

Ride-share company Uber quietly filed paperwork this week for its initial public offering, the Wall Street Journal reported late Friday.

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.