Skip to main content

9. August 2022

Das perfekt verschachtelte 3D-Rätsel

Prämiertes Computerdesign und 3D-Druck von hochgradig verzahnten Puzzles

Dreidimensionale Puzzles sind viel mehr als nur Denkspiele. Sie sind beeindruckende Beispiele für die vielfältigen Möglichkeiten des 3D-Drucks. Technologisch relevant ist das für elektromagnetischen Einheiten, Architektur und Robotermontage. Ein Team internationaler Computerwissenschafter:innen um den ISTA-Vizepräsidenten für Technologietransfer und Oscar-Preisträger Professor Bernd Bickel hat nun eine Toolbox veröffentlicht, mit der sich hochgradig verschachtelte Puzzles entwerfen lassen. Die Arbeit wurde auf der SIGGRAPH-Konferenz mit dem Technical Paper Award ausgezeichnet.

interlocking puzzle in the shape of a cow
Knifflige Puzzles verschiedenster Form mit ineinander verschlungenen 3D-Teilen. Das leistungsfähige neue Toolkit, das von einem internationalen Team von Computerwissenschafter:innen entwickelt wurde, lässt jede:n das eigene Puzzle entwerfen. © Rulin Chen et al.

Verzahnte Puzzles sind verblüffende geometrische Spiele. Ihre Teile werden durch ihre geometrische Anordnung zusammengehalten, die auch verhindert, dass man sie auseinandernehmen kann. Eine spezielle Unterklasse dieser „Interlocking Puzzles“ hat dabei einen sehr hohen Schwierigkeitsgrad. Es sind mehrere Schritte nötig, um sie zu zerlegen. Und das ist eine herausfordernde Aufgabe, da man zahlreiche Konfigurationen erkunden muss, bis man einen Punkt erreicht, an dem das erste Stück freiliegt und herausgenommen werden kann. Eine noch größere Herausforderung ist aber das Design solcher Puzzles.

Ein Team von Forscher:innen der Singapore University of Technology and Design, der ETH Zürich und der École polytechnique fédérale de Lausanne (EPFL) in der Schweiz sowie des Institute of Science and Technology Austria (ISTA) stellen nun auf der SIGGRAPH-Konferenz ein Programm vor, um solche Puzzles mit der Rechenleistung von Computern zu erstellen. Der iterative und robuste Algorithmus ist für alle frei zugänglich, die ihr eigenes Puzzle entwerfen möchten. „Wir haben ein Toolkit entwickelt, mit dem sich hochgradig verschachtelte Puzzles nach den Wünschen der Benutzer:innen entwerfen lassen, einschließlich der Form, der Anzahl der Puzzleteile und des Schwierigkeitsgrads“, lädt Computerwissenschafter Rulin Chen die Community ein.

Please accept YouTube cookies to play this video. By accepting you will be accessing content from YouTube, a service provided by an external third party.

YouTube privacy policy

If you accept this notice, your choice will be saved and the page will refresh.

Animation von Erstellung und Lösung des Puzzles. In einer virtuellen Umgebung modellierten die Informatiker:innen die ineinandergreifenden Puzzles, die später zum Ausprobieren im 3D-Drucker gefertigt wurden. © Rulin Chen et al.

Die Lösung des Rätsels, wie man lösbare Rätsel erstellt

Stellen Sie sich vor, Ihr Lieblingstier wäre eine Eule. Das Computerprogramm würde die Eulenform als 3D-Gitter modellieren, das gleichmäßig in kleine Volumeneinheiten, so genannten Voxel, unterteilt ist (2D-Bildelemente werden bekanntlich Pixel genannt). Der Algorithmus garantiert, dass alle Puzzleteile die gleiche Größe haben und alle Voxel, die ein Puzzleteil bilden, miteinander verbunden sind. Außerdem verhindert er Konstruktionen, bei denen man ein Teil mit dem ersten Zug entfernen kann. Mit diesen Anforderungen im digitalen Hinterkopf beginnt der Algorithmus mit dem Entwerfen von Puzzleteilen innerhalb des „voxelisierten“ Gitters.

Einzelheiten des Algorithmus
1.
Für das erste Stück wählt das Programm zufällig eine Bewegungsrichtung aus. Von allen möglichen Voxel, die sich bewegen lassen, aber durch den Rest der Struktur blockiert werden, wählt es zufällig eines aus, das so genannte Keimvoxel.

2.
Wenn sich das Keimvoxel auch in eine andere Richtung bewegen kann, fügt das Programm dem Puzzlestück einen Blockiervoxel hinzu, so dass es sich nur in die gewünschte Richtung bewegen kann: Es verbindet das Startvoxel mit einem Voxel, das die unerwünschte Bewegung blockiert. Dafür inkludiert es alle Voxel auf dem kürzesten Weg zwischen Start- und Blockiervoxel.

3.
Um eine praktische Stückgröße zu erreichen, wird der Voxelblock erweitert, jedoch so, dass die ersten beiden Schritte respektiert werden. Schließlich wird das Stück in die gewählte Richtung bewegt, und die Konstruktion eines neuen Stücks beginnt auf die gleiche Weise (Schritt 1-3).

4.
Sobald die Form und die Größe der Teile festgelegt sind und der Schwierigkeitsgrad erreicht ist, werden die nicht verwendeten Voxel entfernt. Das Puzzle ist fertig, aber sein Aussehen kann noch verbessert werden.

5.
Dieser optionale Schritt verbessert sowohl das Aussehen als auch „schwache“ Puzzlestücke. Ein schwaches Teil ist gekennzeichnet durch Voxel, die viel kleiner als die anderen sind. Ein solches Teil kann bei der Herstellung oder beim Spielen leicht brechen. Durch eine leichte Anpassung der Gesamtform können schwache Teile vermieden werden.

stylized cow next to rendered blocks
Formoptimierung einer Kuh. Indem man die Form des Kuhpuzzles leicht anpasst, werden die einzelnen Puzzleteile stabiler. © Rulin Chen et al.

Der Algorithmus braucht nur sechs Minuten, um ein vierteiliges Kuhpuzzle mit dem Schwierigkeitsgrad 6 zu erstellen – das bedeutet, dass mindestens sechs Züge erforderlich sind, um das erste Teil zu entfernen. Für einen Würfel mit dem Schwierigkeitsgrad 27 braucht der Computer mehr als sechs Stunden.

Testlauf mit gedruckten Puzzles

Fast jede Form kann zum Puzzle werden, solange sie keine eingeschlossenen Volumina aufweist, so wie etwa Muscheln oder Bäume. Wenn das Puzzle weniger als acht Teile hat, bleibt die Komplexität des Problems und die Dauer der Erstellung überschaubar. „Natürlich funktioniert unser Projekt nicht nur in der Theorie. Wir haben verschiedene Puzzles in 3D gedruckt, um herauszufinden, wie schwierig es für Leute ist, sie zu lösen“, sagt Professor Bernd Bickel und scherzt: „Schnell war klar: die Puzzles sind echt knifflig. Und auch, dass das Eulenpuzzle mit Abstand als das niedlichste empfunden wird.“

3D interlocking puzzles in various shapes
Verschiedene Varianten von 3D-gedruckten, hochgradig ineinandergreifenden Puzzles. Die Form des Puzzles, die Anzahl der Teile und der Schwierigkeitsgrad können nach Belieben gewählt werden. © Rulin Chen et al.

Publikation

Rulin Chen, Ziqi Wang, Peng Song, und Bernd Bickel. 2022. Computational Design of High-Level Interlocking Puzzles. ACM Transactions on Graphics, Vol. 41, No. 4, Art. 150 (Proceedings of SIGGRAPH). DOI: 10.1145/3528223.3530071

Förderungen

DieArbeit wurde durch den SUTD Start-up Research Grant SRG ISTD 2019 148, den Schweizerischen Nationalfonds (SNF) NCCR Digital Fabrication Agreement #51NF40-141853 und den European Research Council (ERC) Grant MATERIALIZABLE-715767 finanziert.



Teilen

facebook share icon
twitter share icon
back-to-top icon
Nach Oben