Un nouvel algorithme génère des patrons façon « pliage du papier » pour produire n’importe quelle structure 3D.

Dans un article paru en 1999, Erik Demaine – aujourd’hui professeur en génie électrique et informatique au MIT, mais alors étudiant au doctorat de 18 ans à l’Université de Waterloo, au Canada – a décrit un algorithme qui pourrait déterminer comment plier une feuille de papier dans n’importe quelle forme 3D imaginable.

Il a été un jalon dans le domaine de l’origami computationnel, mais l’algorithme n’a pas donné des motifs de pliage très pratique. Essentiellement, il a pris une très longue bande de papier et l’a enroulée dans la forme désirée. Les structures résultantes avaient tendance à avoir beaucoup de coutures où la bande se doublait sur elle-même, donc elles n’étaient pas très solides.
Lors du Symposium sur la géométrie numérique en juillet, Demaine et Tomohiro Tachi de l’Université de Tokyo annonceront l’achèvement d’une quête qui a commencé avec ce papier de 1999: un algorithme universel pour plier les formes origami qui garantit un nombre minimum de coutures.

« En 1999, nous avons prouvé que nous pouvions plier n’importe quel polyèdre, mais la façon dont nous avons montré comment le faire était très inefficace« , dit Demaine. « C’est efficace si votre premier morceau de papier est super-long et mince. Mais si vous deviez commencer avec un morceau de papier carré, alors cette ancienne méthode plierait fondamentalement le papier carré vers le bas sur une bande mince, gaspillant presque tout le matériel. Le nouveau résultat promet d’être beaucoup plus efficace. C’est une toute autre stratégie pour penser à faire un polyèdre. »

Demaine et Tachi travaillent également à l’implémentation de l’algorithme dans une nouvelle version d’Origamizer, le logiciel libre pour générer des motifs de plis origami dont la première version Tachi est sortie en 2008.

Maintien des limites

L’algorithme des chercheurs conçoit des motifs de plis pour produire n’importe quel polyèdre, c’est-à-dire une surface 3D composée de nombreuses facettes planes. Les logiciels d’infographie, par exemple, modélisent des objets 3D sous forme de polyèdres composés de nombreux petits triangles. « N’importe quelle forme incurvée que l’on pourrait approcher avec beaucoup de petits côtés plats « , explique Demaine.

Techniquement parlant, la garantie que le pliage impliquera le minimum de coutures signifie qu’il préserve les « limites » du papier original. Supposons, par exemple, que vous ayez une feuille de papier circulaire et que vous souhaitiez la plier pour former une tasse. En laissant un cercle plus petit au centre du morceau de papier à plat, vous pourriez regrouper les côtés ensemble dans un motif plissé; en fait, certains gobelets refroidisseurs d’eau sont fabriqués sur ce dessin précis.
Dans ce cas, la limite de la coupe – son bord – est la même que celle du cercle déplié – son bord extérieur. La même chose ne serait pas vraie avec le pli produit par Demaine et l’algorithme précédent de ses collègues. Là-bas, la tasse se composait d’une fine bande de papier enroulée en rond comme une bobine – et elle ne retiendrait probablement pas l’eau.
« Le nouvel algorithme est censé vous donner des pliages bien meilleurs et plus pratiques », dit Demaine. « Nous ne savons pas comment quantifier cela mathématiquement, exactement, autrement que cela semble fonctionner beaucoup mieux dans la pratique. Mais nous avons une propriété mathématique qui distingue bien les deux méthodes. La nouvelle méthode maintient la limite du morceau de papier original sur la limite de la surface que vous essayez de faire. C’est ce qu’on appelle l’étanchéité. »
Une surface fermée – telle qu’une sphère – n’ a pas de limite, donc une « approximation origami » de celle-ci nécessitera une couture à l’endroit où les limites se rejoignent. Mais  » l’utilisateur peut choisir où fixer cette frontière « , dit Demaine. « On ne peut pas obtenir une surface fermée entière pour être étanche à l’eau, parce que la limite doit être quelque part, mais on peut choisir où elle est. »

Allumer des feux

« L’algorithme commence par cartographier les facettes du polyèdre cible sur une surface plane. Mais alors que les facettes se touchent lorsque le pliage est terminé, elles peuvent être très éloignées les unes des autres sur la surface plane. Vous pliez tout le matériel supplémentaire et rassemblez les faces du polyèdre « , dit Demaine.
Le pliage du matériel supplémentaire peut être un processus très complexe. Les plis qui rassemblent plusieurs faces peuvent comporter des dizaines, voire des centaines de plis séparés.
La mise au point d’une méthode de calcul automatique de ces courbes de froissement a impliqué un certain nombre d’idées différentes, mais une méthode centrale était qu’elles pouvaient être estimées par quelque chose appelé diagramme de Voronoi. Pour comprendre ce concept, imaginez une plaine verdoyante. Un certain nombre de feux sont allumés simultanément, et ils se propagent tous dans toutes les directions à la même vitesse. Le diagramme de Voronoi – nommé d’après le mathématicien ukrainien du XIXe siècle Gyorgy Voronoi – décrit à la fois l’endroit où les feux sont placés et les limites auxquelles les feux adjacents se rencontrent. Dans l’algorithme de Demaine et Tachi, les limites d’un diagramme de Voronoi définissent les plis du papier.


« Nous devons le peaufiner un peu dans notre environnement « , dit Demaine. « Nous imaginons aussi simultanément allumer un feu sur tout le polygone du polyèdre et en sortir. Mais ce concept était vraiment utile. Le défi est de savoir où « allumer les feux », essentiellement, pour que le diagramme de Voronoi ait toutes les propriétés dont nous avons besoin. »

Quête terminée

« C’est très impressionnant « , dit Robert Lang, un des pionniers de l’origami computationnel et un membre de l’American Mathematical Society, qui en 2001 a abandonné une carrière réussie dans l’ingénierie optique pour devenir un origamiste à plein temps. Il complète ce qu’on pourrait qualifier une quête qui a commencé il y a plus de 20 ans: une méthode de calcul pour plier efficacement n’importe quelle forme spécifiée à partir d’une feuille de papier. En cours de route, il y a eu plusieurs belles démonstrations de pièces du puzzle: un algorithme pour plier n’importe quelle forme, mais pas très efficacement; un algorithme pour plier efficacement des familles particulières de formes arborescentes, mais pas des surfaces; un algorithme pour plier des arbres et des surfaces, mais pas toutes les formes. Mais celui-ci couvre tout!
L’algorithme est étonnamment complexe, mais cela se produit parce qu’il est complet. Il couvre vraiment toutes les possibilités. « Et ce n’est pas seulement une preuve abstraite, c’est facilement réalisable par calcul. »
Joseph O’Rourke, professeur de mathématiques et d’informatique au Smith College et auteur de How To Fold It: The Mathematics of Linkages, Origami et Polyhedra, est d’accord.
« Ce que l’on savait auparavant, c’était soit « tricher » – enrouler le polyèdre avec une fine bande – soit ne pas garantir le succès « , dit-il. Leur nouvel algorithme est garanti de produire un pliage, et c’est l’opposé de la tricherie en ce sens que chaque facette du polyèdre est recouverte d’une facette « sans couture » du papier, et la limite des cartes en papier jusqu’à la limite du collecteur polyédrique – leur propriété « imperméable ». Enfin, le ‘flash’ structurel supplémentaire nécessaire pour réaliser leur pliage peut être caché à l’intérieur et donc invisible.

 

1 commentaire »

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.