Kiste zerschneiden

[Xin]

Moin,

um die aktuelle Gemütlichkeit hier ein wenig zu unterbrechen und euch nach dem auslaufenden Sommerloch die Gelegenheit zu geben, eure grauen Zellen wieder zu starten, werfe ich mal ein Programmierproblem in die Runde, dass ich in der letzten Woche lösen musste. Nur mal so zum drüber nachdenken.

Benötigt wird eine Datenstruktur, die eine Kiste/Box darstellt. Anschließend möchte ich diese Kiste an einer Ebene zerschneiden.
Ein Beispiel, wie das aussehen kann - einmal von der Seite - die Kiste steht mit einer Kante zur Kamera, die vordere Kante verdeckt gleichzeitig die hintere Kante. die Ebeen verläuft durch eine Ecke diagonal durch die Kiste und schneidet an der anderen Seite durch eine weitere Ecke.

cube1.png

und einmal etwas angeschrägt, damit man die Perspektive sehen kann, die ebene schneidet den obere linke Kante.

cube2.png

Die Ebene könnte natürlich auch beliebig anders stehen.

Wie würdet ihr dieses Problem angehen?

[cloidnerux]

Die Ebene, solange nicht größenbegrenzt ist, ist sie von der Gleichung

Code: Alles auswählen

(p - x) * n = 0

wobei p, x und n Vektoren sind, p ein beliebiger Ortsvektor eines Punktes der Ebene, x ein Beliebiger Punkt der Ebene und n der Normalenvektor der ebene, ausmultipliziert zu

Code: Alles auswählen

x * n = p * n

wobei p*n konstant ist.

Nun ist dein Geometrisches Objekt durch eine Menge Punkte P und der Verbindungsvektoren V definiert.
Nun kannst du für jede Verbindung den Schnitt mit der Ebene bestimmen, denn deine Aufpunkt ist P_i mit dem Verbindungsvektor V_i sodass

Code: Alles auswählen

P_i + V_i = P_i+1

gilt, wobei P_i+1 hier der zweite Punkt der Verbindung ist.
Die Entsprechende Geradengleichung ist

Code: Alles auswählen

P_i + r * V_i = x

Eingesetzt in die Ebenengleichung:

Code: Alles auswählen

(P_i + r * V_i) * n = p*n
P_i * n + r* V_i * n = p*n
r(x*nx + y*ny + z*nz) = p*n - P_i * n
r = (p*n - P_i * n)/(x*nx + y*ny + z*nz)

Damit die Ebene die gerade innerhalb eines sinnvollen Bereiches schneidet, muss 0<=r<=1 sein.
Mit

Code: Alles auswählen

P_i * r * V_i = x

erhälst du den Schnittpunkt. Das kannst du mit allen Verbindungen so handhaben.
Sind Verbindungsvektor und Normalenvektor senkrecht zu einander, so ergibt der Nenner des Bruches 0 und die Gerade verläuft parallel zur Ebene oder liegt in dieser Drin, das kann man prüfen indem man ein Punkt in die Ebenengleichung einsetzt.

MfG cloidnerux

[Xin]

Schöne Mathematik. Jetzt mal die Inforamtik dahinter. ^^
Wie sieht so eine Datenstruktur aus? Wie beschreibst Du die Box und wie beschreibst Du den Körper, wenn man ihm eine Ecke abgeschnitten hat? ^^

[cloidnerux]

Schöne Mathematik. Jetzt mal die Inforamtik dahinter. ^^
Wie sieht so eine Datenstruktur aus? Wie beschreibst Du die Box und wie beschreibst Du den Körper, wenn man ihm eine Ecke abgeschnitten hat? ^^

Du hast deine Menge Punkte P

Code: Alles auswählen

List<Point> points

Du hast die Liste der Verbindungen

Code: Alles auswählen

struct connection
{
    Point * p1;
    Point * p2;
}
List<connection> connections

Dann hast du deine Ebene

Code: Alles auswählen

Vector p, n

Und dann dürfen wir durchiterieren

Code: Alles auswählen

foreach( connection c in connections)
{
    vector v = *c.p2 - *c.p1;
    double zaehler = v * n;
    if(zaehler == 0.0)        //Liegt in der Ebene, nix weiter machen
    {
        break;
    }
    double r = (p * n - *c.P1 * n) / zaehler;
    if(r < 0 || r > 1)
        break;
    Point * newPoint = new Point();
    *newPoint = *c.P1 + r * v;
    if((p - *c.p1) * n < 0)        //Prüfen Linksseitig, rechtsseitig
    {
        points.remove(c.p2);
        c.p2 = newPoint
    }
    else
    {
        points.remove(c.p1);
        c.p1 = newPoint;
    }
    points.Add(newPoint);
}

Im Grunde genommen, jede Verbindung durchiterieren, prüfen ob sie Schneidet und wenn ja wo, den neuen Punkt in die liste Eintragen, die Verbindung updaten(mal davon ausgehen, dass das so möglich ist), den alten Punkt löschen(auch mal davon ausgehen, dass das so möglich ist).
Was man noch machen müsste, wäre die neuen Punkte miteinander zu verbinden, dass habe ich mal außen vor gelassen.
Das ganze ist nen Mischmasch aus C/C++/C# pseudo-code.

[Xin]

Bei den ganzen Verbindungen, wie erkennt man dann, welche eine Fläche ergeben? Oder ist das nur eine Sammlung von Segmenten, die irgendwo in der Gegend rumliegen und zufälligerweise die Kanten einer Kiste darstellen?

Im Grunde genommen, jede Verbindung durchiterieren, prüfen ob sie Schneidet und wenn ja wo, den neuen Punkt in die liste Eintragen, die Verbindung updaten(mal davon ausgehen, dass das so möglich ist), den alten Punkt löschen(auch mal davon ausgehen, dass das so möglich ist).

Wie updated man denn die Verbindungen und welche Punkte löscht man?

Wobei sich daraus in meinem Kopf durchaus ein Verfahren entwickelt, was mir gefällt, aber nicht identisch ist mit dem, was ich gewählt habe. ^^

Was man noch machen müsste, wäre die neuen Punkte miteinander zu verbinden, dass habe ich mal außen vor gelassen.

Aber das ist doch gerade das interessante.

[cloidnerux]

Aber das ist doch gerade das interessante.

Ich kenne die Algorithmen nicht, um eine Fläche in Dreiecke zu zerlegen. Du hast aber nach dem Prozess eine Reihe neuer Punkte, die alle auf einer Ebene liegen, damit also eine Fläche aufspannen.
Wenn du immer nur einen Quader hast, müssen alle Punkte eine Fläche ergeben. Was ist aber nun, wenn du ein U-hast, dass zerschnitten wird?
Hier hilft vlt eine Projektion der Grundfläche auf die Schnittebene.

Wie updated man denn die Verbindungen und welche Punkte löscht man?

Ich hatte an Links und Rechtsseitigkeit gedacht. Der Normalenvektor zeigt in eine Richtung und für mich solle er in die Richtung zeigen, die weg sollte, daher auch die Prüfung mit den ifs.
Alles was in die selbe Richtung zeigt kommt weg und wird mit dem Schnittpunkt substituiert.
Dann muss man noch die Verbindungen neu ziehen.
Mein Problem ist gerade, dass ich den Algorithmus im Kopf und hier im Beitrag entwickelt habe, es ich mir erstmal selber vorstellen muss, wie das auszusehen hat.

[Xin]

Aber das ist doch gerade das interessante.

Ich kenne die Algorithmen nicht, um eine Fläche in Dreiecke zu zerlegen. Du hast aber nach dem Prozess eine Reihe neuer Punkte, die alle auf einer Ebene liegen, damit also eine Fläche aufspannen.
Wenn du immer nur einen Quader hast, müssen alle Punkte eine Fläche ergeben. Was ist aber nun, wenn du ein U-hast, dass zerschnitten wird?

Wenn Du ein U hast, musst Du vorher schon wissen, welche Teile zu der Fläche gehören und welche nicht. ^^
Es kann in dem Fall also nicht sein, dass es sich ausschließlich um eine unsortierte Menge von Liniensegmenten handelt.

Wie updated man denn die Verbindungen und welche Punkte löscht man?

Ich hatte an Links und Rechtsseitigkeit gedacht. Der Normalenvektor zeigt in eine Richtung und für mich solle er in die Richtung zeigen, die weg sollte, daher auch die Prüfung mit den ifs.
Alles was in die selbe Richtung zeigt kommt weg und wird mit dem Schnittpunkt substituiert.
Dann muss man noch die Verbindungen neu ziehen.

Das ist eigentlich der interessanteste Punkt. Wie zieht man die fehlenden Verbindungen?

Mein Problem ist gerade, dass ich den Algorithmus im Kopf und hier im Beitrag entwickelt habe, es ich mir erstmal selber vorstellen muss, wie das auszusehen hat.

Darum geht's ja in dem Thread... ein echtes Problem aus der Praxis und sich einfach mal ein paar Gedanken zu machen. ^^

[Leverator]

Hmm,

also ich würde so vorgehen, dass ich zunächst ein Objekt "3Dobj" definiere.
Dieses 3Dobj enthält eine gewisse Anzahl an Objekt-Flächen (3Darea).
Diese Flächen müssen zunächst kein zusammenhängendes Objekt beschreiben. Sie sind einfach nur Teil eines 3Dobj.
Eine 3Darea enthält neben einer gewissen Anzahl an 3Dconn, die gemeinsam eine gerade Fläche darstellen, auch eine vorberechnete Flächennormale. Dort könnte man noch zusätzlich Werte für Materialien, Brechungsinex usw. für die spätere 3D-Darstellung einfügen.

Die 3Dconn stellen Verbindungen zweier Punkte im Raum dar (3Dvertice).
Bilden die einzelnen 3Dareas ein geschlossenes Objekt, so werden die einzelnen 3Dconns von mehreren 3Dareas verwendet.

Möchte man nun ein 3Dobj durchschneiden, so besteht die Hauptaufgabe lediglich darin, die Verbindungen in den einzelnen 3Dconns zu finden, die durchschnitten werden.
Die betroffenen Verbindungen werden aufgetrennt, und jeweils mit einem neuen 3Dvertice verbunden, der am Schnittpunkt sich befindet. Somit besteht eine alte Verbindung nun aus zwei Verbindungen (3Dconn).

Bis jetzt haben wir also ein 3Dobj, welches an den Schnittpunkten neue 3D-Punkte eingefügt bekommen hat.

Nun kann man wählen, ob man ein neues 3D-Objekt erstellen will, welches eine Seite des durchgeschnittenen Objekts enthält, oder es löschen usw.

Werden die beiden Teile in tatsächlich zwei unterschiedliche 3Dobj aufgetrennt, so müssen die offenen Flächen wieder durch jeweils ein 3Darea-Objekt geschlossen werden und die Flächennormale neu berechnet werden.


Naja, so in der Art wäre mein Vorschlag.


Grüße,
Lev

[Leverator]

Morgähn,

also nachdem ich eine Nacht drüber geschlafen habe, muss ich zugeben, dass ich nicht ganz zufrieden bin mit der Lösung.
Auf den ersten Blick sieht sie ganz gut aus, jedoch besteht ein Problem: Die gespeicherten Punkte, die eine Ebene bilden sollen, bilden keine exate mathematische Ebene. Das Problem besteht darin, wie die Zahlen im Rechner dargestellt werden. Und hier haben wir eine begrenzte Genauigkeit.

Vielleicht ist es sinnvoller, wenn man eine Fläche wie folgt darstellt:

1. Einen "Schwerpunkt" der Fläche definieren.
2. Alle Punkte der Fläche werden relativ zu dem Schwerpunkt gemessen und in Form von Abstand und Winkel gespeichert.

Aber auch hier ist ein Problem bei größeren Ausmaßen durch die Veränderung der Genauigkeit zu erwarten (durch Mantisse, Exponent).

Vielleicht kann man die Genauigkeit dadurch austricksen, indem man für die Anwendung eine bestimmte Genauigkeit festlegt und dann statt mit Fließkommazahlen zu rechnen, das Ganze in Festpunktzahlen umwandelt.

Aber auch hier bleibt das Problem: Wir zerschneiden eine Fläche und müssen neue Punkte einfügen, deren Positionen nicht genau darstellbar sind.

Vielleicht müssen wir auch garnicht ein Objekt zerschneiden, sondern nur die Bearbeitungsschritte an diesem Objekt merken.
Wenn wir mal von einem realen Beispiel ausgehen wollen: Das Dach eines Hauses benötigt ein Loch, damit man dort den Schornstein eines Kamins durchziehen kann.
Vielleicht lässt man in der Datenstruktur das Dach als Ganzes und berechnet das Loch nur in der Darstellung hinein. Jenachdem wie stark der Nutzer auf das Objekt gezoomt hat, kann man die Berechnung mehr oder weniger genau durchführen.
Will der Nutzer plötzlich, dass der Kamin an einer anderen Stelle im Haus aufgebaut wird, so muss die Software auch nicht mehr umständlich das Loch "flicken", sondern einfach nur in der Darstellung den Bearbeitungsschritt anpassen.
Erst ganz zum Schluss, wenn der Bauplan "gerendert" werden muss, werden die entsprechenden mathematischen Operationen am Objekt durchgeführt und die Positionen auf eine gewisse Genauigkeit gerundet.

Beispiel:
Es muss durch eine Holzbohle ein Loch für eine Querverstrebung gebohrt werden.
Die Holzbohle ist nichts weiter als ein lang gestreckter Quader. Der Quader enthält einen Schwerpunkt von dem die relativen Entfernungen der einzelnen Flächenschwerpunkte berechnet werden. Relativ zu den Flächenschwerpunkten definieren wir die Ebenen, die wiederum durch Punkte "begrenzt" werden. Da der Quader ein geschlossenes Objekt beschreiben soll, werden einige Punkte mehrfach verwendet.
Das Loch ist wiederum ein neues geometrisches Objekt, welches durch Länge, Durchmesser und Posistion des Schwerpunktes definiert wird.
Für die Darstellung muss das Loch in ein Gitterobjekt überführt werden, dessen Genauigkeit variiert werden kann.
Die mathematische Operation ist nun die Subtraktion des Loches von der Holzbohle, welches bei der Darstellung mit geringer Genauigkeit durchgeführt wird.

Ich bin jetzt mal auf Eure Kommentare gespannt,

Grüße Lev

[Xin]

also nachdem ich eine Nacht drüber geschlafen habe, muss ich zugeben, dass ich nicht ganz zufrieden bin mit der Lösung.

Es gibt keine zufriedenstellende Lösung, wenn Du an die Grenzen der Genauigkeit von Fließkommazahlen kommst. ^^

Grundsätzlich kann man die Lösung, die Du vorher genannt hast, als die Lösung ansehen, die implementiert wurde: Der Würfel wurde in 12 Kanten zerlegt, die einen Anfang und ein Ende haben. Die Flächen wurden in 6 Loops zerlegt, die je nach Drehsinn den Index auf die Kante besitzen: Geht man von Start zu Ziel, so wäre der Index x, geht man von Ziel zu Start, so ist der Index -x. Eine Fläche ist damit mit den Indizes 1,2,3,4 beispielweise beschrieben. Davon gibt es entsprechend 6 Flächen für den Würfel.
Alle Segmente werden nun mit der Ebene geschnitten. Gleichzeit wird sich gemerkt, ob die Ebene schneidet (der Schnittpunkt wird gemerkt) und wenn auf welcher Seite Startpunkt und Endpunkt liegen. Anschließend baut dem Körper wieder zusammen: Jeder Segment im Loop wird gefragt, ob es zur Seite gehört, die erhalten bleibt oder schneidet. Wird geschnitten, so wird der Schnittpunkt gemerkt. Da jeder Loop, der geschnitten wird immer gradzahlig (bei Würfeln genau 2mal) schneiden muss, entsteht so pro geschnittenem Loop ein Segment von Ausgehendem Schnittpunkt 1 zu eingehendem Schnittpunkt. Die Segmente speichere ich in einem zusätzlichem Loop.

Im Standardfall, fällt ein Loop weg, weil er komplett im abzutrennenden Bereich liegt. Die gesammelten Segmente der vier geschnittenen Flächen ergeben aber einen neuen Deckel.
Wird nur eine Ecke abgeschnitten, so bleiben alle 6 Loops (teils geschnitten) erhalten, es kommt ein 7 Loop hinzu, der das Lock schließt.

Sonderfälle abfangen (Ebene berührt nur und liegt außerhalb) und fertig ist die Geschichte.

Auf den ersten Blick sieht sie ganz gut aus, jedoch besteht ein Problem: Die gespeicherten Punkte, die eine Ebene bilden sollen, bilden keine exate mathematische Ebene. Das Problem besteht darin, wie die Zahlen im Rechner dargestellt werden. Und hier haben wir eine begrenzte Genauigkeit.

Das stimmt. Da kannst Du aber schlussendlich auch nichts dran ändern. Jeder Punkt beim Würfel liegt auf drei Flächen und wenn das nicht exakt passt (z.B. weil die Kanten genau den Dimensionen folgen), dann musst Du ein wenig Spielraum haben, wo Du behauptest, dass der vierte Punkt nunmal jetzt doch genau auf der Ebene liegt, den die drei anderen Punkte aufspannen.

Vielleicht ist es sinnvoller, wenn man eine Fläche wie folgt darstellt:

1. Einen "Schwerpunkt" der Fläche definieren.
2. Alle Punkte der Fläche werden relativ zu dem Schwerpunkt gemessen und in Form von Abstand und Winkel gespeichert.

Abstand und Winkel ist immer problematisch: Je größer der Abstand, desto mehr verstärkt sich die Ungenauigkeit der Winkel. Da Du auch zwei Winkel brauchst, um eine Position im Raum zu bestimmen, verlierst Du reichlich Nachkommastellen.

Vielleicht kann man die Genauigkeit dadurch austricksen, indem man für die Anwendung eine bestimmte Genauigkeit festlegt und dann statt mit Fließkommazahlen zu rechnen, das Ganze in Festpunktzahlen umwandelt.

Warum Festkommazahlen? Du hast eine 53 Bit Mantisse. Wenn Du den zu betrachtenden Raum möglichst klein hältst, hast Du möglichst wenig Rundungsfehler.

Sinnvoll wäre große Transformationen rauszurechnen. Ein Würfel von 1ccm größe, der in der stationären Bahn positioniert ist, kann man absolut positionieren, dann fällt aber die Genauigkeit von "Das ist 1 cm" oder man beschreibt den Würfel exakt und fügt für den Körper, der ein Ausmaß von 1ccm hat, eine relative Verschieben auf die stationäre Umlaufbahn hinzu, die sich auf alle Punkte des Körpers beziehen.
Das sind dann natürlich mehr Daten erforderlich.

Vielleicht müssen wir auch garnicht ein Objekt zerschneiden, sondern nur die Bearbeitungsschritte an diesem Objekt merken.

Das ist eine übliches Vorgehen. Aber irgendwann muss man was darstellen und dann muss auch was gerechnet werden. Man kann schließlich nicht sagen "Hier ist eine Box, stellen Sie sich bitte vor, dass sie den Teil davon nicht sehen."

Wenn wir mal von einem realen Beispiel ausgehen wollen: Das Dach eines Hauses benötigt ein Loch, damit man dort den Schornstein eines Kamins durchziehen kann.
Vielleicht lässt man in der Datenstruktur das Dach als Ganzes und berechnet das Loch nur in der Darstellung hinein. Jenachdem wie stark der Nutzer auf das Objekt gezoomt hat, kann man die Berechnung mehr oder weniger genau durchführen.
Will der Nutzer plötzlich, dass der Kamin an einer anderen Stelle im Haus aufgebaut wird, so muss die Software auch nicht mehr umständlich das Loch "flicken", sondern einfach nur in der Darstellung den Bearbeitungsschritt anpassen.
Erst ganz zum Schluss, wenn der Bauplan "gerendert" werden muss, werden die entsprechenden mathematischen Operationen am Objekt durchgeführt und die Positionen auf eine gewisse Genauigkeit gerundet.

Ich muss rendern können. ^^

Tatsächlich wird die geschnittene Box als ein Abzugskörper konstruiert, der von einem anderen Körper abgezogen wird.

Beispiel: Ein Quader ist eine Wand, die oben schräg abschnitten werden soll. Von dieser Wand wird ein unendlich großer Körper abgezogen, der an einer Ebene abgeschnitten wird: Ein sogenannter Halbraum. Unendlich groß ist immer unpraktisch, deswegen konstruiere ich eine Box, die so groß ist, wie die Wand und schneide den Teil der Wand aus der Box heraus, der stehen bleiben soll. Den übrigen Körper schneide ich vom Quader der Wand ab.