Boolesche Operationen auf Maschen

15

eine Reihe von Eckpunkten und Dreiecken für jedes Netz gegeben. Kennt jemand einen Algorithmus oder einen Ort zum Suchen (ich habe zuerst Google ausprobiert, aber keinen geeigneten Ort gefunden, um zu beginnen), um boolesche Operationen an den Netzen durchzuführen und eine Reihe von Eckpunkten und Dreiecken für das resultierende Netz zu erhalten? Von besonderem Interesse sind Subtraktion und Vereinigung.

Beispielbilder: http://www.rhino3d.com/4/help/Commands/Booleans.htm

graphics algorithm graphics-programming procedural lathomas64
quelle

Antworten:

10

Ich stelle mir das als Konstruktive-Festkörper-Geometrie (CSG) vor. Hoffentlich finden Sie hier Hilfe.

http://www.alsprogrammingresource.com/csg.html

http://createuniverses.blogspot.com/2009/09/qtcsg-constructive-solid-geometry.html

http://www.nigels.com/research/

Durchsuchen Sie auch Google nach Constructive Solid Geometry als Start.

HTH

JustBoo
quelle
+1 - Ich wollte die gleichen Links posten, JustBoo - bis ich bemerkte, dass du mich verprügelt hast! :)
jacmoe
Vielen Dank! Die Terminologie Konstruktive-Festkörper-Geometrie ist genau das, was ich brauchte!
Lathomas64
@jacmoe - Die Ironie ist jetzt erstaunlich und vollständig :-) Einige davon verdienen Anerkennung. Danke.
JustBoo
einige davon? : PI glaube, ich habe sie alle da unten notiert. : D Trotzdem sind sie nur grundlegende CSG-Sachen. Von da an wird es ziemlich haarig - nicht einmal die großen kommerziellen Modeling-Pakete haben es richtig gemacht.
Jacmoe
3

Ich denke, wir können es rätseln, wenn wir nur darüber nachdenken.

Sie möchten offensichtlich Flächen (Dreiecke) erstellen, in denen sich die beiden Geometrien schneiden. Dann bleiben Ihnen drei Maschen: der Schnittpunkt, den Sie gerade isoliert haben, Geometrie 1 und Geometrie 2.

Dann löschen Sie einfach, was Sie nicht brauchen!

  • BooleanDifference: Löschen Sie das isolierte Teil und die Geometrie. 2.
  • BooleanIntersection: Löschen Sie Geometrie 1 und 2, und lassen Sie das isolierte Teil
  • BooleanUnion: Geometrien 1 und 2 zusammenführen und das isolierte Teil löschen (stellen Sie sicher, dass Geometrien 1 und 2 zu einer festen Geometrie zusammengefügt werden)
  • BooleanSplit: Trennen Sie Geometrie 1 und Geometrie 2 voneinander und duplizieren Sie das isolierte Teil (fügen Sie eines zu Geometrie 1 und das andere zu Geometrie 2 hinzu).

Ich denke, das deckt es ab, oder? Das Schwierigste wäre natürlich, die Schnittflächen zu erstellen. Durchlaufen Sie dazu jedes Gesicht des einen und prüfen Sie, ob dieses Gesicht Teil des anderen ist. Wenn es sich vollständig innerhalb befindet, kopieren Sie die Fläche als Teil des Schnittgitters. Wenn es teilweise innen liegt, müssen Sie das Dreieck entlang der Schnittlinie teilen. Ich denke, DirectX und OpenGL hätten beide Hilfsfunktionen dafür, oder es ist nur eine 3D-Ebenenmathematik (Vektoren). Ich habe so etwas in Kalkül 3 gelernt (oder war es 2?), Aber wenn Sie keine Ahnung haben, fragen Sie vielleicht unter math.stackexchange.com . Und wenn das Gesicht draußen ist, dann tun Sie natürlich nichts. Sobald Sie alle Flächen beider Netze durchlaufen haben, bleibt das Schnittgitter erhalten.

Ricket
quelle
2

Wenn Sie mit polygonalen Modellen arbeiten, müssen Sie sich möglicherweise mit nicht-vielfältiger Geometrie befassen, was bedeutet, dass die Frage, was "innen" und was "außen" ist, nicht definiert ist. Es ist schwierig, eine boolesche Operation auszuführen, wenn Sie nicht wissen, ob Sie eine 0 oder eine 1 haben.

Sie müssen sich auch mit Randfällen wie koplanaren Polygonen, Polygonen, die Kanten schneiden, Scheitelpunkten, die auf Kanten und / oder Flächen liegen, und Dingen dieser Art befassen. Nichts davon ist unmöglich, Sie brauchen nur eine sehr robuste Art der Darstellung Ihrer Maschendaten und eine genaue Definition dessen, was Sie in diesen Fällen erwarten.

JasonD
quelle
1

Es ist erwähnenswert, dass die meisten Ihrer Operationen durch Negation und Vereinigung dargestellt werden können, wobei die Negation einiger Geometrie nur die Geometrie ist, deren Normalen umgekehrt sind. Wenn Sie also die Gewerkschaft in Ordnung bringen können, sollten die anderen Operationen einfach folgen:

  • Kreuzung (A, B): =! Vereinigung (! A,! B)
  • subtrahiere (A und B): =! union (! A, B)

Sander hat einige ziemlich gute Blog-Posts, die CSG-Implementierungen behandeln: http://sandervanrossen.blogspot.com/search/label/CSG

jpaver
quelle
1
Ich wollte mein eigenes CSG-Zeug erwähnen, aber anscheinend hat es bereits jemand anderes getan: O)
Sander van Rossen