Mein CSG-Tool
Verfasst: 31.07.2023, 11:13
Moin, ich wollte das mal ausbreiten, soweit wie's jetzt ist.
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:
Das Modell-Dreieck wird an den Stellen unterteilt, wo das Schnitt-Dreieck die Oberfläche schneidet. Die Version im Bild ist der Vollausbau mit 5 neuen Dreiecken - eins von vorn an die Schnittkante, eins von hinten an die Schnittkante, und drei von der jeweiligen Randkante zum nahesten Schnitt-Vertex. Von diesen 5 weiß ich nur von den zwei Schnittkanten-Dreiecken sicher, ob sie "innen" oder "außen" sind, bei den drei Außenkanten-Dreiecken ist es noch offen. Das ergibt sich dann aber im weiteren Verlauf, denn jetzt schneide ich diese Ergebnis-Dreieckssuppe mit dem nächsten Schnitt-Dreieck und bekomme so am Ende einen Haufen, der genau entlang der Schnittkante unterteilt ist. Und theoretisch sind jetzt alle Dreiecke auf der einen Seite der Schnittkante als "innen" markiert und alle auf der anderen Seite als "außen". Das mache ich mit jedem Dreieck des Modells, und bekomme so ein Modell, das eine Schnittkante entlang der Schnittform hat.
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.
Das war Teil 1. Teil zwei kommt bald und zeigt dann, wie sich viele Dreiecke der Schnittform zu einem zusammenhängenden Schnitt ergänzen.
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:
Das Modell-Dreieck wird an den Stellen unterteilt, wo das Schnitt-Dreieck die Oberfläche schneidet. Die Version im Bild ist der Vollausbau mit 5 neuen Dreiecken - eins von vorn an die Schnittkante, eins von hinten an die Schnittkante, und drei von der jeweiligen Randkante zum nahesten Schnitt-Vertex. Von diesen 5 weiß ich nur von den zwei Schnittkanten-Dreiecken sicher, ob sie "innen" oder "außen" sind, bei den drei Außenkanten-Dreiecken ist es noch offen. Das ergibt sich dann aber im weiteren Verlauf, denn jetzt schneide ich diese Ergebnis-Dreieckssuppe mit dem nächsten Schnitt-Dreieck und bekomme so am Ende einen Haufen, der genau entlang der Schnittkante unterteilt ist. Und theoretisch sind jetzt alle Dreiecke auf der einen Seite der Schnittkante als "innen" markiert und alle auf der anderen Seite als "außen". Das mache ich mit jedem Dreieck des Modells, und bekomme so ein Modell, das eine Schnittkante entlang der Schnittform hat.
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.
Das war Teil 1. Teil zwei kommt bald und zeigt dann, wie sich viele Dreiecke der Schnittform zu einem zusammenhängenden Schnitt ergänzen.