Polygon Infill-Algorithmus

Question

Ich arbeite an Mesh-Slicing-Dienstprogramm für 3D-Druck-Zwecken. Im Allgemeinen sollte ein 3D-Mesh-Modell in 2D-Formen (eine Anzahl von Polygonen, wahrscheinlich mit Löchern) geschnitten werden und diese mit Pfaden einer bestimmten Dicke unter Verwendung eines spezifischen Musters füllen. Diese Pfade werden verwendet, um einen gcode-Befehl für eine 3d-Drucker-Firmware zu generieren.

Es gibt verschiedene Open-Source-Tools mit gleichen Zwecken, geschrieben auf Python und Perl. Aber mein Ziel ist es, den Arbeitsablauf von Slicer zu verstehen und mein eigenes Werkzeug in C oder C++ zu schreiben.

Bis jetzt bin ich in der Lage Kontur von Scheibe zu bekommen und werde sie jetzt mit Pfaden füllen. Das Problem ist, dass ich keinen effizienten Algorithmus dafür gefunden habe. Ein schematischer Prozess des Füllbeispiels:

Kann jemand empfehlen, wie man diese füllenden Wege erzeugt? Vielen Dank.

---

Derzeit bin ich mit dem folgenden Algorithmus:

1. Finden Sie einen Begrenzungsrahmen der Form
2. Split bb vertikal mit Linien (Anzahl der Zeilen = bb.width/path.thickness)
3. Suche Schnittpunkte für die Form und jede Zeile
4. Construct a-Segmente von diesen Punkten (sollten zwei Punkte pro Zeile sein) mit von Grenzoffset
5. ein Segment hinzufügen, die ein ursprünglichen Segmente zusammen eine Linie Streife
6. Wir sind bereit zu erzeugen gcode oder zeichnen Sie einen Pfad

Dies ist ein einfaches und schneller Algorithmus verbinden bilden, aber es funktioniert funktioniert nicht für konkave Polygone und Polygone mit Löchern. Außerdem verwendet es nur ein bestimmtes Muster.

Answer 1

Nach einiger Zeit der Forschung, die ich in dem folgenden Algorithmus beendet habe: eine Reihe von Optimierungen Gelegenheit Es gibt jedoch.

Answer 2

Sie können sich this webpage über Algorithmen zum Anwenden von Schraffuren in Regionen ansehen.

Answer 3

Der folgende Ansatz erzeugt ein Füllmuster, das aus einem Einwegpfad besteht (d. H. Die Fülldüse wird niemals ausgeschaltet, bewegt und wieder eingeschaltet), wann immer dies möglich ist.

Nach Ihrem Schritt 4 ("Konstruieren Sie Segmente von diesen Punkten mit Versatz von der Grenze"), drehen Sie jedes vertikale Liniensegment in 2 oder mehr Punkte: die oberen und unteren Endpunkte, plus (stellen Sie sich vor, Ihr Diagramm ist gezeichnet auf a Transparente Folie, legen Sie ein Stück Papier mit horizontalen Linien darunter und markieren Sie, wo die vertikalen Liniensegmente in Ihrem Diagramm die horizontalen Linien auf dem Papier schneiden.

Bilden Sie nun einen kantengewichteten Graphen, der für jeden Punkt einen Scheitelpunkt enthält, wobei eine Kante zwei Scheitelpunkte verbindet, wenn ihre entsprechenden Punkte kleiner oder gleich einer Gittereinheit voneinander entfernt sind. Fügen Sie außerdem Kanten zwischen benachbarten obersten Punkten von Liniensegmenten und zwischen benachbarten untersten Punkten hinzu. Verwenden Sie den euklidischen Abstand zwischen den Punkten für das Kantengewicht.Schließlich der magische Teil: Finden Sie ein Minimum-Gewicht Hamiltonian path auf dieser Grafik. Dies ist ein Pfad, der jeden Scheitelpunkt genau einmal besucht und eine minimale Länge hat. Die minimale Längenbeschränkung garantiert, dass sich der Pfad niemals selbst kreuzt, da, wenn zwei Linien sich kreuzen, die Linie von a nach b und die Linie von c nach d, dann wäre es immer möglich, einen kürzeren Gesamtweg durch Löschen dieser zu schaffen zwei Zeilen und Erstellen von zwei neuen Zeilen mit einer anderen Kombination von Endpunkten (entweder a --- c und b --- d, oder a --- d und b - c). Dies ist der Pfad, den Sie füllen werden.

Einen Hamilton-Pfad zu finden (geschweige denn einen Hamilton-Pfad mit minimalem Gewicht) ist ein NP-schweres Problem, das eng mit dem berühmteren Problem des Traveling Salesman verbunden ist. Da viele gute exakte TSP-Löser bereits existieren (z. B. Concorde), wäre es sinnvoll, stattdessen einen von diesen zu verwenden, um eine Reiseverkäufer-Tour zu finden, und dann einfach eine der Kanten zu löschen, um einen kurzen Hamilton-Pfad zu erzeugen. (Selbst wenn Sie die schwerste Kante löschen, wird dies nicht notwendigerweise einen Hamilton-Pfad mit minimaler Länge erzeugen, da es möglicherweise kürzere Pfade gibt, die nicht an benachbarten Knoten beginnen und enden; aber uns interessiert nicht wirklich der Gesamtlänge hier, wir wollen nur einen Pfad, der alle Scheitelpunkte besucht und sich nicht kreuzt.)

Leider kann ein Diagramm nicht garantieren, dass es entweder einen Hamilton-Pfad oder eine Reiseverkäufer-Tour enthält. (Sie können natürlich nicht existieren, wenn der Graph zum Beispiel getrennt ist, aber selbst verbundene Graphen können entweder keine oder beide haben: z. B. kann ein Graph mit einem Eckpunkt von Grad 1 keine TSP-Tour haben.) In diesem Fall, wenn TSP Solver, den Sie verwenden, kann Touren finden, die nicht alle Scheitelpunkte besuchen, Sie können dies einfach wiederholen, bis alle Scheitelpunkte abgedeckt sind. Andernfalls würde ich auf Ihren ursprünglichen Algorithmus zurückgreifen.