Oppervlakte-mozaïeken zijn een rangschikking van vormen die nauw aansluiten, en herhaal patronen op een oppervlak zonder overlapping. Stel je het patroon van de vacht van een giraf voor, het schild van een schildpad en de honingraat van bijen - ze vormen allemaal natuurlijke vlakvullingen. Het is een complexe, multidisciplinair probleem. Een wereldwijd team van computerwetenschappers heeft een nieuwe, alternatief model voor het repliceren van deze ingewikkelde oppervlakteontwerpen, afwijkt van klassiek, meerstapsbenaderingen voor een efficiëntere, gestroomlijnd algoritme.

"Als we kijken naar hoe natuurlijke mozaïekpatroon in de natuur voorkomt, de individuele cellen groeien gelijktijdig, en elke individuele cel weet niet noodzakelijkerwijs wie de aangrenzende cellen zijn, noch hun locatie of coördinaten, " legt hoofdauteur van het werk uit, Rhaleb Zayer, onderzoeker bij Max Planck Instituut voor Informatica in Saarbrücken, Duitsland. Cellen vertegenwoordigen de vorm of tegels die ingewikkelde mozaïekpatronen bevatten. "Om dit gedrag vast te leggen, we moeten een intrinsieke kijk op het probleem aannemen en uitgaan van het algemeen aanvaarde extrinsieke perspectief dat volledige kennis vereist van alle individuele celinteracties en locaties."

Typisch, onderzoekers hebben zich tot het Voronoi-model gewend om dergelijke herhaalde oppervlaktepatronen na te bootsen. In wiskunde, Een Voronoi-diagram verdeelt vlakken in een patroon op basis van de afstanden tussen punten. Pogingen om hetzelfde idee uit te breiden naar oppervlakken worden gehinderd door de hoge kosten van nauwkeurige afstandsmetingen, boekhouding en intersectieberekeningen.

In dit nieuwe werk onderzoekers vereenvoudigen het maken van natuurlijke mozaïekpatronen op oppervlaktemazen door de veronderstelling te laten vallen dat regio's moeten worden gescheiden door lijnen. In plaats daarvan, ze hebben een methode ontwikkeld die rekening houdt met regiogrenzen in het patroon als smalle banden, die niet noodzakelijk recht zijn, en modelleer de partitie als een reeks gladde functies die over het oppervlak zijn gelaagd. Hun methode is voornamelijk gebaseerd op elementaire schaarse lineaire algebra-kernels, dat wil zeggen vermenigvuldigen en optellen, beschikbaar, omdat ze de hoeksteen vormen van het moderne numerieke computergebruik.

"Op deze manier, wij bieden kleine, beknopt, menselijk leesbaar en vooral, platformonafhankelijke parallelle code, " merkt Zayer op.

"Bij het observeren van de vooruitgang die is geboekt bij het parallelliseren van bestaande seriële Voronoi-diagramcodes in de afgelopen twee decennia, de prestatieverbeteringen die door onze voorgestelde methode worden bereikt, zijn zeer aanzienlijk, " voegt Markus Steinberger toe, co-auteur van het werk en een assistent-professor aan de Technische Universiteit van Graz in Oostenrijk.

Zayer, Steinberger en hun medewerkers, waaronder Hans-Peter Seidel van het Max Planck Instituut voor Informatica, en Daniel Mlakar aan de Technische Universiteit van Graz, zullen hun nieuwe methode presenteren op SIGGRAPH Asia 2018 in Tokyo van 4 december tot 7 december. De jaarlijkse conferentie bevat de meest gerespecteerde technische en creatieve leden op het gebied van computergraphics en interactieve technieken, en toont toonaangevend onderzoek in de wetenschap, kunst, gamen en animatie, onder andere sectoren.

In hun krant "Gelaagde velden voor natuurlijke mozaïekpatronen op oppervlakken, "De auteurs demonstreren met succes hun nieuwe methode op verschillende grootschalige testgevallen die verder gaan dan de mogelijkheden van state-of-the-art. Ze waren in staat om aan te tonen dat hun methode toepasbaar is op zeer gedetailleerde modellen, zoals het 3D-model van het vliegpak van de beroemde piloot Amelia Earhart, die tien miljoen facetten omvat. Tessellations op de scan van de zeer versierde historische Pergolesi Side Chair tonen 30 miljoen facetten die volledig en efficiënt zijn verwerkt op een enkele moderne grafische verwerkingseenheid, oftewel, GPU. Ondanks de eenvoud van het algoritme, de onderzoekers zeggen dat hun oplossing alomvattend bleek te zijn met minimale vereisten.

Bij toekomstig werk, Zayer en team hopen de functie van interactief bewerken van vlakvullingen toe te voegen met behulp van hun framework. Deze functie kan bedoeld zijn voor ontwerpers en architecten die nieuw zijn in 3D-printtoepassingen en -modellering. De onderzoekers zijn ook van plan dit werk uit te breiden naar hogere dimensies en naar de behandeling van andere statistieken.