Yttesselationer är ett arrangemang av former som sitter tätt, och forma upprepade mönster på en yta utan att överlappa varandra. Föreställ dig mönstret av en giraffs päls, skalet av en sköldpadda och bikakan av bin — alla bildar naturliga tesseller. Att efterlikna dessa naturliga mönster beräkningsmässigt är en komplex, multidisciplinärt problem. Ett globalt team av datavetare har utvecklat en ny, alternativ modell för att replikera dessa intrikata ytdesigner, viker bort från det klassiska, flerstegsstrategier för en mer effektiv, strömlinjeformad algoritm.

"När vi tittar på hur naturlig tessellation uppstår i naturen, de enskilda cellerna växer samtidigt, och varje enskild cell vet inte nödvändigtvis vilka som är dess närliggande celler eller deras plats eller koordinater, " förklarar huvudförfattaren till verket, Rhaleb Zayer, forskare vid Max Planck Institute for Informatics i Saarbrücken, Tyskland. Celler representerar formen eller brickorna som består av invecklade tessellationsmönster. "För att fånga detta beteende, vi måste anta en inneboende syn på problemet och avvika från det allmänt antagna yttre perspektivet som kräver full kunskap om alla individuella cellinteraktioner och platser."

Vanligtvis, forskare har vänt sig till Voronoi-modellen för att efterlikna sådana upprepade ytmönster. I matematik, Ett Voronoi-diagram delar upp plan i ett mönster baserat på avstånden mellan punkter. Ansträngningar att utvidga samma idé till ytor hämmas av de omfattande kostnaderna för noggranna avståndsmätningar, bokföring och korsningsberäkningar.

I detta nya verk, forskare förenklar skapandet av naturliga tesselleringar på ytmaskor genom att slopa antagandet att regioner måste separeras med linjer. Istället, de har utvecklat en metod som tar hänsyn till regiongränser i mönstret som smala band, som inte nödvändigtvis är raka, och modellera partitionen som en uppsättning släta funktioner skiktade över ytan. Deras metod bygger huvudsakligen på grundläggande glesa linjära algebrakärnor, dvs multiplikation och addition, lättillgänglig, eftersom de är hörnstenen i modern numerisk beräkning.

"På det här sättet, vi tillhandahåller små, koncis, mänskligt läsbar och viktigast av allt, plattformsoberoende parallellkod, " konstaterar Zayer.

"För att observera de framsteg som gjorts med att parallellisera befintliga seriella Voronoi-diagramkoder under de senaste två decennierna, de resultatvinster som uppnås med vår föreslagna metod är mycket betydande, " tillägger Markus Steinberger, medförfattare till verket och biträdande professor vid Graz tekniska universitet i Österrike.

Zayer, Steinberger och deras medarbetare, som inkluderar Hans-Peter Seidel vid Max Planck Institute for Informatics, och Daniel Mlakar vid Graz tekniska universitet, kommer att presentera sin nya metod på SIGGRAPH Asia 2018 i Tokyo 4 december till 7 december. Den årliga konferensen har de mest respekterade tekniska och kreativa medlemmarna inom området datorgrafik och interaktiva tekniker, och visar upp ledande forskning inom vetenskap, konst, spel och animation, bland andra sektorer.

I deras tidning, "Lagerade fält för naturliga tessellations på ytor, " Författarna demonstrerar framgångsrikt sin nya metod i flera storskaliga testfall utöver kapaciteten hos state-of-the-art. De kunde visa att deras metod är tillämpbar på mycket detaljerade modeller, som 3D-modellen av den berömda piloten Amelia Earharts flygdräkt, omfattar tio miljoner aspekter. Tessellations på skanningen av den mycket utsmyckade historiska Pergolesi Side Chair visar upp 30 miljoner facetter bearbetade fullt och effektivt på en enda modern grafisk bearbetningsenhet, aka, GPU. Trots algoritmens enkelhet, forskarna säger att deras lösning visade sig vara heltäckande med minimala krav.

I framtida arbete, Zayer och teamet hoppas kunna lägga till funktionen att interaktivt redigera tessellationer med hjälp av deras ramverk. Denna funktion kan riktas till designers och arkitekter som är nya inom 3D-utskriftsapplikationer och modellering. Forskarna avser också att utvidga detta arbete till högre dimensioner och till behandling av andra mått.