Ausgangspunkt: zwei Meshes als Dreieckshaufen. Sie müssen nicht wasserdicht sein, aber frei von degeneriertem Gedöns und ich weiß auch nicht, was passiert, wenn die nicht alle einheitliches Winding haben.
Im Gegensatz zu anderen Libs rechne ich einfach direkt jedes Dreieck gegen jedes Dreieck. Wenn man ein Dreieck durch ein anderes steckt, können dabei maximal zwei neue Vertizes entstehen. Das sieht dann so aus:
Nun ist beim CSG die eigentliche Herausforderung die zwanzig komma vier millionen Grenzfälle, die man zu behandeln hat. Ich habe da sicher nicht an alles gedacht, aber einige Fälle habe ich bereits abgedeckt.
Das ist zum Einen die Anzahl Schnittpunkte - wenn man ein Dreieck durch eine Ebene steckt, sollte man immer zwei oder gar keinen Schnittpunkt erwarten. Es gibt aber auch den Grenzfall "1 Schnittpunkt", wo das Dreieck so auf der Spitze die Ebene berührt - den Fall ignoriere ich einfach, die Nachbarn dieses Schnitt-Dreiecks werden sich darum kümmern. Und es gibt den Grenzfall "3 Schnittpunkte", wo das Dreieck genau mit dem "mittleren" Vertex auf der Ebene liegt und die Schnittpunktberechnung mit Epsilon dann ergibt, dass alle drei Dreieckskanten die Ebene schneiden. In dem Fall suche ich die beiden Schnittpunkte raus, die sehr nah beieinander liegen, und vereine sie, so dass ich wieder zwei hab.
Und da sind zum Anderen die furchtbar dünnen Dreiecke, die entstehen, wenn ein Schnittpunkt nach an Vertex oder Kante des Modell-Dreiecks liegt. Und die behandle ich, indem ich sie provoziere. Ich bewege absichtlich einen Schnittpunkt auf einen nahen Vertex des Modelldreiecks oder auf die Kante drauf. Dabei merke ich mir, wo ich diesen Schnittpunkt einrasten ließ, und benutze diese "Einrast-Info" bei der Erstellung der Dreiecke. Die entsprechenden Dreiecke werden dann gar nicht erst erzeugt. Auf die Art werden Konflikte durch Rundungsfehler vermieden, wenn z.B. das Einrasten meint "nicht nah genug, Punkt bleibt eigenständig", aber die Dreieckserzeugung nachher meint "das Dreieck ist sehr schmal, das erzeuge ich nicht".
Ich habe das Epsilon mal auf 10cm angehoben, damit man's deutlich sieht. Das ist ein GIF, aber man muss drauf klicken, damit es abspielt.
