Les pavages de surface sont un arrangement de formes étroitement ajustées, et former des motifs répétés sur une surface sans chevauchement. Imaginez le motif de la fourrure d'une girafe, la carapace d'une tortue et le nid d'abeilles des abeilles forment tous des pavages naturels. L'imitation informatique de ces conceptions naturelles est une tâche complexe, problème multidisciplinaire. Une équipe mondiale d'informaticiens a développé un nouveau modèle alternatif pour reproduire ces conceptions de surface complexes, s'éloigner du classique, approches en plusieurs étapes pour une algorithme simplifié.

« Quand on regarde comment la tessellation naturelle se produit dans la nature, les cellules individuelles se développent simultanément, et chaque cellule individuelle ne sait pas nécessairement qui sont ses cellules voisines ni leur emplacement ou leurs coordonnées, " explique l'auteur principal de l'ouvrage, Rhaleb Zayer, chercheur à l'Institut Max Planck d'informatique de Sarrebruck, Allemagne. Les cellules représentent la forme ou les tuiles qui comprennent des motifs de tessellation complexes. "Pour capturer ce comportement, nous devons adopter une vision intrinsèque du problème et nous écarter de la perspective extrinsèque largement adoptée qui nécessite une connaissance complète de toutes les interactions et emplacements des cellules individuelles. »

Typiquement, les chercheurs se sont tournés vers le modèle de Voronoi pour imiter de tels motifs de surface répétés. En mathématiques, Un diagramme de Voronoï divise les plans selon un motif basé sur les distances entre les points. Les efforts pour étendre la même idée aux surfaces sont entravés par les coûts élevés des mesures de distance précises, la comptabilité et les calculs d'intersection.

Dans ce nouveau travail, les chercheurs simplifient la création de pavages naturels sur les maillages de surface en abandonnant l'hypothèse selon laquelle les régions doivent être séparées par des lignes. Au lieu, ils ont développé une méthode qui prend en compte les limites des régions dans le motif sous forme de bandes étroites, qui ne sont pas forcément rectilignes, et modéliser la partition comme un ensemble de fonctions lisses superposées à la surface. Leur méthode repose principalement sur des noyaux d'algèbre linéaire clairsemée basiques, c'est-à-dire la multiplication et l'addition, facilement disponible, car ils sont la pierre angulaire de l'informatique numérique moderne.

"De cette façon, nous fournissons petit, concis, lisible par l'homme et surtout, code parallèle indépendant de la plate-forme, " note Zayer.

« Observant les progrès réalisés dans la parallélisation des codes des diagrammes de Voronoï en série existants au cours des deux dernières décennies, les gains de performances obtenus par notre méthode proposée sont très importants, " ajoute Markus Steinberger, co-auteur de l'ouvrage et professeur assistant à l'Université de technologie de Graz en Autriche.

Zayer, Steinberger et leurs collaborateurs, qui incluent Hans-Peter Seidel au Max Planck Institute for Informatics, et Daniel Mlakar de l'Université de technologie de Graz, présenteront leur nouvelle méthode au SIGGRAPH Asia 2018 à Tokyo du 4 au 7 décembre. La conférence annuelle présente les membres techniques et créatifs les plus respectés dans le domaine de l'infographie et des techniques interactives, et met en valeur la recherche de pointe en science, de l'art, jeux et animations, entre autres secteurs.

Dans leur papier, "Champs en couches pour les tessellations naturelles sur les surfaces, " les auteurs ont réussi à démontrer leur nouvelle méthode sur plusieurs cas de test à grande échelle au-delà des capacités de l'état de l'art. Ils ont pu montrer que leur méthode est applicable à des modèles très détaillés, tels que le modèle 3D de la combinaison de vol de la célèbre pilote Amelia Earhart, englobant dix millions de facettes. Les tessellations sur le scan de la chaise d'appoint historique Pergolesi très ornementée présentent 30 millions de facettes traitées entièrement et efficacement sur une seule unité de traitement graphique moderne, alias, GPU. Malgré la simplicité de l'algorithme, les chercheurs affirment que leur solution s'est avérée complète avec des exigences minimales.

Dans les travaux futurs, Zayer et son équipe espèrent ajouter la fonction d'édition interactive des pavages à l'aide de leur framework. Cette fonctionnalité pourrait s'adresser aux concepteurs et architectes novices en matière d'applications d'impression 3D et de modélisation. Les chercheurs entendent également étendre ce travail à des dimensions supérieures et au traitement d'autres métriques.