Mesh an Ebene abschneiden

[Schrompf]

Heyho, liebes Kompetenz-Center.

Ich habe mir in den Kopf gesetzt, einen Mesh an einer schrägen Ebene abzuschneiden. Nun kriege ich Dreiecke schon noch an einer Ebene geschnitten, es können ein oder zwei neue Dreiecke entstehen. Aber wenn ich das resilient hinkriege, habe ich immer noch das Problem, dass die Schnittfläche dann leer ist. Ich sehe also in die Struktur des Modells hinein. Und das sieht doch scheiße aus.

Gibt's dafür etablierte Lösungsansätze?

Ich könnte Linienzüge entlang der Schnittebene bilden und die Fläche dazwischen dann mit irgendnem Algorithmus triangulieren. Aber das klingt anstrengend und gefühlt gibt's da zweiundzwanzig hässliche Grenzfälle, wo das schiefgehen könnte.

[Jonathan]

Ich denke im allgemeinen muss man die Menge der Schnitt-Polygone bestimmen (muss ja nicht zusammenhängend sein, kann also beliebig viele geben), und dann die Polygone triangulieren, vermutlich indem man sie in konvexe Teile zerlegt. Für den zweiten Schritt gibt es sicherlich eine Menge Material, die Schnittpolygone zu bestimmen klingt aber nervig (man erzeugt ja neue Geometrie und muss gleichzeitig mitschleifen, was womit verbunden ist, etc.).

Der einfach Weg wäre vermutlich eine vorhandene Bibliothek für boolsche Algebra zu nehmen (Mesh - Clipping-Plane ist ja ein Klassiker). CGAL scheint das z.B. zu können, aber das ist GPL, taugt also vermutlich eher zur Inspiration. Es muss noch eine Menge weitere geben, aber ich habe keinen Überblick der für Empfehlungen taugt.

Generell ist vermutlich die Frage: Willst du das selber machen um dann die Genugtuung zu haben es selber gemacht zu haben, oder möchtest du möglichst schnell das Ergebnis haben? (dann wäre eine vorhandene Bibliothek vermutlich die einzig sinnvolle Lösung)

Außerdem kann man noch darüber nachdenken, was der Anwendungsfall ist. Musst du das dynamisch machen? Ansonsten kann man mit wenigen Zeilen Python-Code das Problem in Blender lösen (wenn du z.B. per Batch-Job 500 Modelle ein einziges mal zerschneiden willst wäre das schnell und einfach und robust). Oder soll es möglichst wenig Abhängigkeiten haben oder gar auf GPU laufen? Dann wäre eine externe Bibliothek vlt. zu fett und man muss es so oder so nachimplementieren.

[joeydee]

CSG muss ja nicht gleich eine aufgeblasene externe Lib sein.
https://github.com/evanw/csg.js/blob/master/csg.js ist eine 1-Klassen-CSG-Lösung in rund 500 Codezeilen, das kann man schnell und gut in eigenem Code unterbringen, habe ich mal in C# ausprobiert.
Ich würde damit erstmal eine generell funktionierende Version basteln, dann lässt sich vielleicht noch einiges auf deinen Spezialfall optimieren.

P.S.: Technisch werden da BSP-Bäume aufgebaut. D.h. nicht nur die Mesh-Triangles, auch deine Plane wird dann BSP-gesplittet und ergibt dann die Grenzfläche. Evtl. musst du statt 'ner Plane eine passende geschlossene Box nehmen, weiß nicht mehr ob geschlossene Körper hier Bedingung waren.

[Schrompf]

Ok, cool, Danke für euren Input. Der UseCase ist echt plump, dass ich mir in den Kopf gesetzt habe, im Schleichspiel den (im Code erzeugten) Schrank schräg abzuschneiden, wenn die Spielfigur sich darin gerade versteckt, damit die Kamera beim Rumgucken nicht nur Schrank sieht.

Ne fertige Lib wäre weise, und unter anderen Umständen hätte ich die wahrscheinlich auch genommen. Joeydees verlinkte JS-Lib sieht echt gut aus, die Portierung nach C++ hat evtl. sogar schon jemand gemacht, sonst wär's ein freundlicher Nachmittag. Aber mir ist inzwischen eingefallen, dass ich ja einen Dreieck vs. Dreieck-Clipper bereits da habe. Und wenn ich damit nicht nur 1) den Mesh an der Ebene clippe, sondern auch 2) anders herum die Ebene (ein großes Dreieck) am Mesh clippe, kriege ich auch meine Schnittkanten gefüllt. Ich schau mal, wie weit ich mit dem Setup komme.

[Krishty]

Falls es nur um die Darstellung geht, kannst du die simpelste Form von CSG-Rendering machen:

1. Eine Clipping Plane setzen, die den Schrank schneidet. Geht je nach API unterschiedlich; notfalls manuell discard() im Shader.
2. Ausschließlich die Back Faces des Schranks rendern, ohne Beleuchtung in einer soliden Farbe (Schwarz oder weiß oder so).
3. Ausschließlich die Front Faces des Schranks rendern, ganz normal.

Überall, wo die Front Faces weggeclippt wurden, schauen jetzt die einfarbigen Back Faces durch. Sieht aus wie eine abgeschnittene, einfarbige Fläche.

Geht in Echtzeit, ist trivial zu implementieren (verglichen mit manueller Triangulierung) und sieht dann ungefähr so aus (nur, dass ich statt solidem Grün hier schwarz-rote Farbübergänge durch ein Signed Distance Field habe):

Geht natürlich nur, wenn die Schrank-Geometrie geschlossen ist. Das gilt aber für CSG generall, also auch für die CPU-Variante.

[joeydee]

Womit mal wieder bewiesen ist, dass:

Außerdem kann man noch darüber nachdenken, was der Anwendungsfall ist.

;)

[Thoran]

Alternativ könntest du den Schrank auch halbtransparent machen.

[TomasRiker]

Wie soll die Schnittfläche eigentlich texturiert werden (Material, Texturkoordinaten)? Das stelle ich mir auch nicht trivial vor, bzw. muss man das vielleicht von außen vorgeben, da es nicht immer auf sinnvolle Weise automatisch entschieden werden kann.

[Schrompf]

Alles gute Tipps. Ja, stimmt, einfach im Shader clippen hätte es für diesen Fall auch getan, und mit den Backfaces bekäme man zumindest ne einfarbige Schnittfläche, wie Krishty empfahl. Grmpf. Nagut, ich lass jetzt trotzdem erstmal meinen Clipper drauf los und schau, wie er performt. Wenn der funktioniert, würde mir das auch bei anderen Sachen in der Zukunft nützen. Und das wiederum vertreibt die depressive Grundstimmung, die das Schleichspiel hat. Ich habe eh schon ne Coding-Sinnkrise und Arbeit in ein Spiel zu stecken, dessen GameJam schon lange vorbei ist und das eh keinen mehr anhebt, macht's nur schlimmer.

[Jonathan]

Ich habe eh schon ne Coding-Sinnkrise und Arbeit in ein Spiel zu stecken, dessen GameJam schon lange vorbei ist und das eh keinen mehr anhebt, macht's nur schlimmer.

Aaach, Harald Hoppelhase ist auch noch hart WIP und das ist ja sogar Easter-themed... :D