Dreiecke auseinander schneiden
-
Hallo,
ich habe ein - für mich sehr kompliziertes - Problem:
Ich entwickle seit einiger Zeit einen 3D-Level-Editor (fragt mich bitte nicht warum ich keinen fertigen nehme und versucht nicht mir das auszureden :p )
und will jetzt das "Fusionieren von Modellen" einbauen, sodass man per Button-klick zwei Objekte mit einander verschmelzen lassen kann.
Wer SeriousSam1 kennt sollte wissen was ich meine. Hie mal eine 2D Notitz (in der Praxis natürlich in 3D):Das da: *------* | | | *-------* *---|--* | | | *-------* soll in das: *------* | | | *----* *---* | | | *-------* "fusioniert" bzw. "verschmolzen" werden.Auch ein Problem in meinem Editor ist, dass ich alles als Polygone, die aus Dreiecken bestehen, betrachte und nicht aus Quads.
Eine Funktion habe ich schon geschrieben, um die ganzen Schnittlinien der jeweiligen sich schneidenden Dreiecke zu ermitteln (funktioniert leider noch nicht perfekt, aber das sollte ich noch hinbekommen).Wie funktioniert das ganze? Wie kann man berechnen, welche Dreiecke unversehrt bleibe, welche zerschnitten werden und welche komplett wegfallen müssen??
Kennt ihr vielleicht Tutorials dafür, und wie nennt man das ganze Konzept eigentlich?Fragen über Fragen ^^ aber ich hoffe ihr könnt mir weiter helfen.
-
Du hast also ein Polygon, das du in Dreiecke zerlegen willst? Das nennt man (allgemein) Tesselieren, bei Dreiecken auch Triangulieren. Ein Algorithmus ist zb die Delaunay-Triangulierung.
-
Nein nein, die Dreiecke habe ich ja schon.
Die sollen aber abgeschnitten werden, komplett wegfallen oder unberührt bleiben.
Jenach dem ob sie mit Dreiecken des anderen Objektes in Berührung kommt.
-
Du wirst wahrscheinlich Normalen für die Dreiecke brauchen, die dir sagen was die Außen- und Innenseite bzgl. des ursprünglichen Polygons sind.
Mit ein paar Skalarprodukten müsste man dann feststellen können ob so eine Seite von dem anderen Polygon eingeschlossen wird (Test auf allen Dreiecken des anderen Polygons). Du kannst da auch einzeln jeden Eckpunkt testen, da weißt du dann auch automatisch welche Dreieck geschnitten werden müssen, nämlich solche die Punkte innerhalb und außerhalb des anderen Polygons haben.
So einfach wie ich dass hier geschrieben habe, gehts aber wahrscheinlich nur für konvexe Polygone, für nichtkonvexe muss man sich was einfallen lassen, dafür hab ich jetzt aber leider nicht die Zeit.
Ich hoffe trotzdem, dass ich etwas weiterhelfen konnte.
-
Falls die Modelle geschlossen sind und keine (halb-)transparente Textur haben musst du im Grunde garnichts machen. Du könntest höchstens noch Dreiecke, die vollständig im jeweils andere Modell liegen entfernen, dazu bräuchtest du aber die Möglichkeit, das zu testen. Ansonsten kommst du nicht darum rum jedes Dreieck gegen Schnitte mit jeder Kante des anderen Objekts zu testen... Ist vermutlich so kompliziert wie es klingt.
Such mal nach "Constructive Solid Geometry" oder "Boolean Modelling".
geloescht
-
was du suchst nennt sich csg und fuer einen fall ist die sache recht einfach, nachdem du zwei dreiecke miteinander geschnitten hast, pruefst du jeweils mit dem 'zerschneiderdreieck' auf welcher seite von ihm die einzelnen teile sind.
liegt ein teil davor, behaelst du es, liegen ein teil dahinter, verwirst du es.