Polygon splitten

Manuel

Hi,
kennt ihr gute Formeln / Funktionen, um:
1. Eine Kollisionslinie( x1 , y1 , z1 , x2 , y2 , z2) zu errechnen, an der eine Ebene( Normal ( x , y , z ) , Distance ) ein Polygon ( x1 , y1 , z1 , x2 , y2 , z2 , x3 , y3 , z3 ) schneidet
2. die Kollision eines Punktes mit einer Linie zu ermitteln
3. Die Position( x , y , z ) zu ermitteln, an der eine Ebene( s. o. ) ein Polygon( s. o. ) schneidet

Danke im Voraus

M.T.

[ Dieser Beitrag wurde am 19.04.2003 um 14:27 Uhr von Manuel editiert. ]

TomasRiker

Für Fall 1 könnte Dir der dritte Teil meines 3D-Kollisions-Tutorials helfen.

Bei Fall 2 kannst Du Dir eine solche Gleichung aufstellen:
Punkt = Linie.Start + s * Linie.Richtung

Punkt.x = Linie.Start.x + s * Linie.Richtung.x
Punkt.y = Linie.Start.y + s * Linie.Richtung.y
Punkt.z = Linie.Start.z + s * Linie.Richtung.z

Jetzt formst Du eine der Gleichungen nach s um, und zwar nimmst Du immer eine Gleichung, wo in dem Nenner dann nicht null steht.
Jetzt setzt Du den gefundenen Wert für s in die beiden anderen Gleichungen ein und wenn's passt, dann liegt der Punkt auf der Linie.

Ansonsten habe ich noch folgende Funktion für Dich, die die minimale Entfernung zwischen einem Punkt und einer Linie berechnet. Man kann dann sagen: Wenn diese Entfernung z.B. kleiner als 0.001 ist, dann liegt der Punkt auf der Linie:

// Minimale Distanz zwischen Punkt und Linie berechnen
float PointLineDistance(const Vector3D& Point,
                        const Vector3D& LineStart,
                        const Vector3D& LineEnd)
{
    const Vector3D v(LineEnd - LineStart);
    return (LineStart + v * (Vector3D::DotProduct(Point - LineStart, v) / v.LengthSq()) - Point).Length();
}

[ Dieser Beitrag wurde am 19.04.2003 um 12:26 Uhr von TomasRiker editiert. ]

Manuel

Danke erstmal, doch ich seh irgendwie nicht, was die Funktion Length() aus dem Vektor macht, um eine Fließkommazahl zu erhalten. Soll das vielleicht der Betrag (alswie [Wurzel](x² + y² + z²)) sein?

M.T.

[ Dieser Beitrag wurde am 19.04.2003 um 14:01 Uhr von Manuel editiert. ]

TomasRiker

Ja, die Vektorlänge!

Manuel

Danke, Tomas, so funktionierts...

------ Thema Ende -------

Ich formuliere die Frage am besten um - kennt jemand von euch eine gute Funktion, um ein Dreieck an einer Ebene zu splitten und die daraus resultierenden 2 (bzw. 3) Dreiecke zu berechnen (möglichst mit Texturkoordinaten)?

Nochmal Danke

M.T.

TomasRiker

Hehe, Du baust Dir wohl einen Octree oder einen BSP-Tree!
Am besten malst Du es Dir auf einem Blatt Papier auf. Du musst untersuchen, welche der drei Dreiecksseiten von der Ebenen geschnitten werden. Dann brauchst Du den Schnittpunkt bzw. den Linienabschnitt s (siehe mein Tutorial, da steht es genau erklärt). Diesen kannst Du dann als Faktor für die Interpolation von Texturkoordinaten, Farben und Normalvektor verwenden, eben für alles, was in dem Vertex so drin ist (Vorsicht bei Farben: erst die RGB-Komponenten extrahieren, und die dann einzeln interpolieren, dann wieder zu einem DWORD zusammensetzen!).
Es gibt noch eine Reihe von Spezialfällen, wenn z.B. eine Dreiecksseite genau entlang der Ebene verläuft.
Ich habe es bei mir so gemacht (Octree): Ich füge zu einem Node immer alle Dreiecke hinzu, die teilweise drin sind, und schneide sie dann ab, wenn sie teilweise den Node verlassen (Clipping). Beim Octree macht man das dann mit allen sechs Ebenen, die einen Node begrenzen (ist ja quaderförmig).

Manuel

Erraten ,
dein Tutorial hat mir schon sehr geholfen, doch wie wandle ich eine Ebene in ei Polygon um, sodass ich den dort geschriebenen Code verwenden kann?
Dann hab ich mit gedacht, wenn die Ebene durch einen Punkt des Polygon geht, dann macht man 2 draus, in allen anderen Fällen 3 - ist doch richtig, oder?

M.T.