Press Release

CAPTURING THE FRUGAL BEAUTY OF COMPLEX NATURAL TESSELLATIONS
The ability to efficiently compute tessellation surfaces has real-world appeal. For instance, it can be appliedin urban and regional planning, geographic mapping, in physiology (e.g. replicating capillary supply tomuscle tissues), metallography and forestry, to name a few. Rhaleb Zayer and collaborators developed
parsimonious algorithms that can be applied to these surface partitioning challenges without agonizing
efforts.
TOKYO, Japan, 21 November 2018 – 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, theshell 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 individual cells 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 thatcomprise intricate tessellation patterns. “To capture thisbehavior, 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.”

Image Caption: 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- andmemory efficient approach.)

Page 1 of 4

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 distancemeasurements, bookkeeping and intersection computations.
In this new work, researchers simplify the creation of natural tessellations on surface meshes by dropping theassumption that regions need to be separated by lines. Instead, they have developed a method 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 surface. Their method relies mainly on basic sparselinear algebra kernels, i.e. multiplication and addition, readily available, as they are the cornerstone ofmodern 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 forInformatics, 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 technicaland creative members in the field of computer graphics and interactive techniques, and showcases leadingedge 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 3D 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 theirsolution proved to be comprehensive with minimal requirements.
In future work, Zayer and team hope to add the function of interactively editing tessellations using theirframework. This feature could be aimed at designers and architects new to 3D printing applications andPage 2 of 4

modeling. The researchers also intend to extend this work to higher dimensions and to the treatment of othermetrics.
More details on this Technical Papers Session at SIGGRAPH Asia 2018:
Session: Meshing
Date: 6 December 2018, Thursday
Time: 4:15pm – 6:00pm
Venue: Hall B5 (1), 5F, B BlockTo register for SIGGRAPH Asia, and for more details of the event, visit http://sa2018.siggraph.org.
– end –Notes to editors:•For more information on the Technical Papers Program, click here.

•For media accreditation to SIGGRAPH Asia 2018, please register here.

About SIGGRAPH Asia 2018
The 11th ACM SIGGRAPH Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia
(SIGGRAPH Asia 2018) will be held in Tokyo, Japan at the Tokyo International Forum from 4 to 7 December
2018. The annual event held in Asia attracts the most respected technical and creative people from all overthe world who are excited by research, science, art, animation, gaming, interactivity, education and emerging
technologies.
The four-day conference will include a diverse range of juried programs, such as the Art Gallery, Computer
Animation Festival, Courses, Emerging Technologies, Posters, Technical Briefs, Technical Papers and Virtual &Augmented Reality. A three-day exhibition held from 5 to 7 December 2018 will offer a business platform forindustry players to market their innovative products and services to the computer graphics and interactive
techniques professionals and enthusiasts from Asia and beyond. For more information, please visit
http://sa2018.siggraph.org. Find us on: Facebook, Twitter, Instagram and YouTube with the official event
hashtag, #SIGGRAPHAsia.

About ACM SIGGRAPH
The ACM Special Interest Group on Computer Graphics and Interactive Techniques is an interdisciplinary
community interested in research, technology, and applications in computer graphics and interactivetechniques. Members include researchers, developers, and users from the technical, academic, business, andPage 3 of 4

art communities. ACM SIGGRAPH enriches the computer graphics and interactive techniques community
year-round through its conferences, global network of professional and student chapters, publications, andeducational activities. For more information, please visit www.siggraph.org.

About Koelnmesse
Koelnmesse Pte Ltd is one of the world's largest trade fair companies. Its more than 80 trade fairs andexhibitions have the broadest international scope in the industry, as 60 percent of the exhibitors and 40
percent of the visitors come from outside Germany. The Koelnmesse events include leading global trade fairs
for 25 sectors, such as Imm Cologne, Anuga, IDS, INTERMOT, Interzum Cologne, Photokina, Gamescom, andthe International Hardware Fair Cologne. Koelnmesse is ACM SIGGRAPH’s event organizer for the last 10
editions of SIGGRAPH Asia. For more information, please visit www.koelnmesse.com.sg.

Media Contacts
Hitoshi Kasai
Head of Communications, SIGGRAPH Asia 2018
MIACIS Associates
hitoshi.kasai@siggraph.org
Jamie Huang
Marketing & Media Partnerships, SIGGRAPH Asia 2018
Koelnmesse Pte Ltd
jamie.huang@siggraph.org

Page 4 of 4