Algorithmus oder software für das schneiden eine Masche

Meine open-source-Spiel Bibliothek enthält eine Implementierung von mesh schneiden. Es arbeitet mit der Irrlicht-api, aber könnte neu geschrieben werden, verwenden Sie eine andere API mit geringem Aufwand. Sie können den code unter den Bedingungen der BSD-Lizenz, oder lernen Sie implementieren Ihre eigenen.

Sehen MeshTools::splitMeshZ in diese Datei für eine Implementierung von mesh-slicing.

Wenn Sie wollen einfach nur, um zu wissen, den Algorithmus, hier ist ein high-level-Beschreibung von was ich getan habe:

Ursprünglich habe ich daran gedacht, mit einer axis-aligned bounding box, um anzugeben, wo schneiden Sie das mesh. Dies war problematisch, denn es stellte viele Spezial-Fälle. Zum Beispiel, eine Kante, die sich über die Ecke der box kann aufgeteilt werden in drei Stücke, anstatt nur zwei.

Mit einer Ebene zu schneiden Sie das mesh in eine linke Masche und eine Rechte Masche reduziert die Anzahl der besonderen Fälle, da eine Kante ist entweder auf einer Seite der Ebene oder der anderen, oder er überquert die Ebene und so wird gehackt in genau zwei Stück.

Jede gewünschte Konfiguration von Schnitten gemacht werden kann, einfach durch schneiden einmal, mit den daraus resultierenden meshes und schneiden Sie es erneut an einem anderen Ort, und so weiter. Speziell im Fall, den Sie beschreiben, in dem Abschnitt, eine Kreis könnte sein Schnitt aus einer Kugel, die durch schneiden eine Hälfte der Kugel aus, bewegen Sie das Flugzeug, eine kleine Menge und das abschneiden der anderen Hälfte, so dass nur ein dünnes band. (Können Sie nicht, schneiden Sie ein Netz nach unten, um buchstäblich keine Tiefe mit dem code, den ich schrieb, aber Sie können schneiden Sie ein Netz, was Sie haben, setzen Sie Ihre floating-point-Gleichheit Schwelle. Ich denke, dass ich willkürlich wählte 0,001 in meinem code.)

Verwendung einer ähnlichen Logik, jedem gewünschten Winkel der Schnittebene erreicht werden kann, mit einer festen Ebene, die Sie gerade brauchen, verwandeln Sie das mesh, um es zu drehen relativ zu dem fixierten Schnittebene, und dann transformieren Sie das Ergebnis zurück. (Für mein Spiel brauchte ich nur Schnitte senkrecht zu der XY-Ebene, so dass ich der Einfachheit halber erlauben nur den Z-Wert der cut zu setzen, und annehmen, ist der Schnitt auf die Z-Position.)

OK, jetzt haben wir vereinfachten das problem, der Algorithmus ist gar nicht so schlecht:

Starten Voraussetzung: Sie haben eine Schnittebene. Sie haben eine Reihe von source-Dreiecke. Sie haben zwei Ziel-Gruppen von Polygone (nicht Dreiecke; quads generiert werden kann, durch schneiden des Dreiecks). Die beiden Ziel setzt, werden als Links und Rechts.

Prozess: Iteration über drei Punkte eines Dreiecks. Die Anzahl der Punkte, die weniger als die Schnittebene. Ich nenne diejenigen, die weniger als die Schnittebene Links und die größer als die Schnittebene Rechts. Es gibt nur eine Handvoll von Fällen:

• Alle Dreieck-Punkte sind auf der Linken Seite: stellen Sie das Dreieck in den Linken gesetzt
• Alle Punkte sind auf der Rechten Seite: legen Sie das Dreieck in der Richtigen
• Ein Punkt Übrig ist, die anderen haben Recht: wenn Sie schneiden Sie ein Dreieck über zwei Kanten, und Sie waren mit einer der Punkte, die Sie bis Ende halten ein kleineres Dreieck. Legen Sie ein Dreieck in die Linke setzen sich aus den Linken Punkt und die zwei Punkte, wo die Kanten kreuzt das Flugzeug. Setzen Sie ein quad in das Recht gesetzt (siehe Nächster Fall).

• Zwei Punkte sind noch Übrig, ein Punkt ist Richtig. Wenn Sie halten eine Kante eines Dreiecks und schneiden Sie es über die beiden anderen Kanten, Sie sind Links halten ein Trapez. Setzen Sie ein quad in der Linken Seite setzen die beiden Punkte in der hand, plus die zwei Punkte über dem Schnitt. Legen Sie ein Dreieck in der richtigen Reihe (Spiegelbild der Fall oben).

• Wenn Sie fertig sind, drehen Sie die Quadrate in Dreiecke, indem ein link über den kürzesten Teil.

Das ist es. Das ist der grundlegende Algorithmus. Der eigentliche code verarbeitet ein paar mehr Fälle, wie was ist, wenn eine Kante ist genau gleich dem cut, was ist, wenn ein Dreieck genau auf der Kante, nicht degenerierte Polygone (z.B. ein Punkt ohne Körper), etc.

Misc. Fragen (alle im verlinkten code):

• Nicht überkompliziert der Mathematik für LERP ' Ing der Stelle, wo die Kante kreuzt den Schnitt Ebene. Es muss nicht eine volle lineare interpolation, es ist eigentlich nur Highschool Algebra II: Aufstieg vorbei laufen, mal ein Verhältnis

• Ist es vorteilhaft, cache generiert (LERP') Punkten, so dass Dreiecke, die gemeinsame Ecken in der uncut-Netz teilen sich die entsprechenden neuen Eckpunkte im Schnitt mesh.

• Wenn Sie sich zu bewahren vertex-sharing, und Sie sind mit Dreieck, index-buffer, die man leider nicht wissen, der index noch beim ersten erzeugen der shapes in der Links und Rechts setzt. Ich benutze eine Klasse namens "PossibleVertex" zu vertreten, eine Zukunft, Dreieck, index-Nummer.

• Wenn Sie gehen, um die Anzeige der Netz -, Wickel-Angelegenheiten. Vorsichtig, überlegt, wie Sie code, der es sicherstellen kann, dass die resultierenden Polygone verwenden Sie die gleiche Wicklung, um so die Dreiecke kamen Sie aus. Dies wird besonders schwierig, wenn triangulieren die quads. Ich kann mich nicht erinnern, die details, aber es ist alles gehandhabt wird in dem verlinkten code.

• Für mein Spiel, ich wollte ein Flachband-Verbindung zwischen zwei schneiden, die Maschen. Das ist, warum splitMeshZ Ergebnisse in 3 Maschen, anstatt nur zwei. Sie können verwenden Sie die mittlere Masche, oder ignorieren Sie es einfach.

InformationsquelleAutor Dennis

Habe ich skizziert den Algorithmus zur Berechnung Flugzeug-Lautstärke-Kreuzungen in diese Antwort. Eine Implementierung in Java zur Verfügung.

InformationsquelleAutor ryanm

Wäre es schneller (für dich, nicht laufen-Zeit), wenn Sie es selbst implementieren: Dies sind die einfachen Schritte, die Sie tun müssen:

1-Extrahieren Sie alle Dreiecke des mesh

2-Für jedes Dreieck,

2-1 - prüfen Sie, ob eine Dreieck-Punkte sind auf die slice-Ebene,

2-2 - wenn nicht, dann für jede der drei Kanten, finden an der Kreuzung mit der slice-Ebene (wenn vorhanden). Sie müssen entweder 2 von Ihnen durchzogen mit dem Flugzeug oder keiner.

2-2-1 Wenn 2 Kanten geschnitten mit der Ebene, dann fügen Sie eine Linie zwischen diese 2 Punkte auf der Ebene.

InformationsquelleAutor