Hallo,

ich versuche schon länger, dreiecksbasiertes CSG in 3D zu realisieren. Ich habe das bisher über den folgenden Ansatz versucht:

1. Testen, welche Dreiecke der Ausgangsobjekte vollständig innerhalb oder außerhalb des anderen liegen (und je nach Modus einzelne aussortiert).

2. Bei den Dreiecken, die sich mit dem anderen Objekt (bzw. dessen Dreiecken) schneiden, habe ich versucht, die Schnittpunkte herauszufinden und in die richtige Reihenfolge zu bringen (mit mäßigem Erfolg )

3. Wenn man dann das Dreieck hat, aus dem Teile herausgeschnitten werden müssen (da es ja von dem anderen Objekt zerschnitten wird), und die Schnittpunkte, kann man dies ja in 2D umrechnen und dann das eigentliche CSG in 2D durchführen. Dies hat bei mir aber auch nicht richtig funktioniert.

Meine Frage ist jetzt: Ist diese Methode überhaupt brauchbar? Kennt jemand gute Tuts oder Dokumentationen darüber? Für Hilfe wäre ich sehr dankbar.

Gruß Joni.

Google ist Dein Freund, Stichworte: „Constructive Solid Geometry“, da ist so einiges zu finden. Englischkenntnisse sind gefordert, vielleicht gibts was im deutschen Sprachraum. Ich hab zwar nichts gesehen, aber ich hab nicht sehr gründlich nachgeschaut. Bei Tutorials sehe ich schwarz - die Tutorials, die mich angehüpft sind waren von der Art: „Wie man in POVRAY .....“. Üblicherweise erklären die Tutorials, was ein Durchschnitt/eine Vereinigung usw. eigentlich ist.

Stichwort Punkte in die richtige Reihenfolge bringen: ich habe so etwas mal versucht. Ich bastel schon seit langer Zeit an einem Modeller herum (infolge eines anderen Projekts ist der leider derzeit ein Trümmerhaufen). Ich wollte dem Benutzer ermöglichen, ein paar Punkte zu selektieren und daraus ein Polygon zu machen. Milkshape schreibt dem Benutzer vor, die Punkte in der richtigen Reihenfolge anzugeben (also CCW), aber das fand ich zu unprofessionell. Also hatte ich das gleiche Problem wie Du. Ich hab das so gelöst (vermutlich gibt es bessere Algorithmen):

Input = eine unsortierte Liste von 3D-Punkten, die alle auf einer Ebene legen müssen
Aufgabe: Punkte sortieren gegen den Uhrzeigersinn

*** Tangentspace-Matrix erzeugen
*** 3D Punkte mit der Tangentspace-Matrix in die XY-Ebene bringen, das CenterOfMass muss dann im Koordinatenursprung liegen
*** Jetzt ist es ein 2D-Problem und man kann die Winkel aller Punkte messen
*** die 3D-Punkte nach den Winkeln sortieren ==> fertig

Das funktioniert im allgemeinen. Es gibt aber immer wieder Probleme, wenn der Algo sich einbildet, dass es ein Backface ist. Man selektiert ein paar Punkte und drückt auf den Knopf „Polygon erzeugen“ und plötzlich verschwindet es, weil das Backface-Culling eingeschaltet ist. Ich bin dem Problem noch nicht auf den Grund gegangen.

Also bei CSG macht man nach meinem Wissen normalerweise zuerst den Umweg über ein Volumen. Dieses Volumen wandelt man dann anschließend wieder in Geometrie um. Stichwort: Marching Cubes

_________________
Yeah!

Das kommt aus der Medizintechnik, glaub ich. aber es gibt durchaus auch so etwas: http://www.flipcode.com/archives/Constructive_Solid_Geometry.shtml

Hallo,

vielen Dank für die Antworten. Ich habe schon vor längerer Zeit gegoogelt, hatte jedoch genau dieselben Probleme wie Traude (hauptsächlich POVRAY-Tuts, Beschreibungen, was CSG überhaupt ist, wie realisiere ich CSG in einem Raytracer,...). Die Idee, die Punkte gegen den Urzeigersinn zu sortieren klingt gut, aber sehe ich das richtig, dass diese Methode auf konvexe Objekte (und einige, aber nicht alle konkaven) Objekte beschränkt ist? Oder ist CSG bei konkaven Objekten überhaupt möglich? (Soweit ich weiss, klappt das bei der Raytracer/Stencil-Methode jedenfalls nicht). Ich stehe jedoch immer noch vor dem Problem, dass, wenn ich die Punktmengen (bzw. Polygone) in 2D habe, diese immer noch verbinden muss. Dies war auch im Text auf flipcode schlecht dokumentiert, das einzige zu dem Thema war das hier:



Soll das heißen, dass ich jedes Polygon einzeln mit jedem schneiden soll? Das würde doch dahingehend enden, dass ich dasselbe Polygon mehrfach "anschneide", oder habe ich das falsch verstanden? Bei meinen Ansätzen habe ich versucht, zu jedem Polygon alle Schnittpunkte zu finden, die Schnittpunkte dann zu verbinden und das ursprüngliche Polygon mit dem aus den Schnittpunkten entstandenen Polygon zu schneiden. Das habe ich bisher nicht geschafft, aber gabs da nicht einen Wikipedia-Artikel dazu? Ich find den nicht mehr Für weitere Hilfe wäre ich sehr dankbar.

Edit: Hab eben im Forum das hier gefunden, suche nochmal nach Polygon Clipping...

Gruß Joni.

Darüber habe ich jetzt eine Zeit lang nachgedacht. Wenn Du Dir sicher bist, dass alle Polygone regulär sind (dh. dass alle ihre Punkte auf einer Ebene liegen), dann könnte man sich das anfängliche Triangulieren wahrscheinlich sparen. Aber ich bin nicht sicher. Durch den nachfolgenden CSG-Prozeß werden viele davon ohnehin trianguliert werden. Die Polygone, die während des CSG-Prozeß erzeugt werden, sollten jedenfalls Dreiecke sein, damit man sicher sein kann, dass sie regulär sind. Das Umsortieren der Punkte wie ich es oben beschrieben habe braucht auch konvexe Polygone.

AAAAABER die Objekte, die Du schneidest (ich meine jetzt die Dreiecksnetze insgesamt) können durchaus konkav sein.


JA. Stell Dir Folgendes vor: Du nimmst einen Würfel und steckst einen dünnen Zylinder längs durch. Die Zylinder-Faces werden sowohl vom Front-Quad als auch vom Back-Quad des Würfels geschnitten - ich hoffe, Du weißt, was ich meine.

Wenn man jetzt nicht einen Zylinder und einen Würfel hat, wo das unmittelbar einsichtig ist, sondern zwei komplexere (konkave)Meshes, musst Du eigentlich alle Polygone des einen Körpers mit allen Polygonen des zweiten Körpers schneiden, wobei während dieses Vorganges sich die Anzahl der Polygone erhöhen wird, weil dauernd neue erzeugt werden. Einzige Abhilfe die mir einfällt: so wie oc2k1 in dem gelinkten Thread sagte, muss man die Dreiecke in ein Hilfsobjekt einsortieren, damit die Laufzeit nicht explodiert. Da wir hier in 3D sind und nicht in 2D muss man wohl einen Octree nehmen und keinen QuadTree.

Leider kann ich Dir da auch nicht wirklich helfen, weil ich das selber noch nicht gemacht habe. Ich weiß nicht, welche Programmiersprache Du benutzt, aber in C gibts glaub ich sogar eine Open Source Library dazu: OpenCSG. Allerdings hab ich grade nachgeschaut und die machen das mit dem Frame Buffer. Weiß nicht, ob das für Dich eine Option ist.

Wenn die Eingabepunkte regulär sind, sind die ausgabedaten doch auch zwingen regulär, oder? Ich meine, du verschiebst beim Triangulieren keine Punkte aus ihrer Ebene. Oder hab ich was übersehen?

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Beim Ineinander-Keilen zweier komplexer Polygon-Netze trau ich mich nicht, Irgendetwas zu garantieren. Insbesondere, wenn ich es selber noch nicht ausprobiert habe.