Gerade + Dreieck (Schnittpunkt)

26.09.2011, 19:50

Parallelepiped

Gerade + Dreieck (Schnittpunkt)

Hi,

wohl eine Standardfrage: Ich suche den Schnittpunkt von einer Geraden mit einem Dreieck im Dreidimensionalen. Vom Dreieck gegeben sind drei Eckpunkte, von der Geraden ein Aufhängepunkt und ein Richtungsvektor.

Etwas ungewöhnlicher: Ich suche eine programmierbare Lösung, d.h. es dürfen keine Gleichungssysteme etc. vorkommen, nur schrittweises Rechnen. Gegeben sind bereits eine Vektorklasse und Funktionen zum Manipulieren von Vektoren (Kreuz- und Scalarprodukt, Addieren, etc.).

Ich habe bereits gute Lösungen für Funktionen gefunden, die auf "schneiden" und "nicht schneiden" prüfen (http://www.blitzbasic.com/codearcs/codearcs.php?code=369), aber keine die den Schnittpunkt ausgibt.

Und ich bin allergisch gegen Formelschreibweisen Augenzwinkern

Die muss ich ja sonst auch wieder für den PC übersetzen...

26.09.2011, 19:56

riwe

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)
was soll denn der schnittpunkt einer geraden mit einem 3eck sein verwirrt

27.09.2011, 10:07

Parallelepiped

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)
Dann halt Gerade mit Dreiecksfläche, ich denke aber man versteht was ich meine.

27.09.2011, 10:34

riwe

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)

Zitat:

Original von Parallelepiped
Dann halt Gerade mit Dreiecksfläche, ich denke aber man versteht was ich meine.

ich nicht

27.09.2011, 10:42

Parallelepiped

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)
Hier der Ansatz, basierend auf dem Link den ich gepostet habe:

Im Code für den PC wird die Vektorklasse für Vektoren und Punkte verwendet, weil sie nicht mehr macht als drei Einträge zu verwalten, nicht irritieren lassen!

Von den Startparametern P (Aufhängepunkt der Geraden), D (Richtungsvektor der Geraden), V0, V1, V2 (die drei Eckpunkte) ist also nur D ein Vektor, der Rest eigentlich Punkte!

Zitat:

bool Ray_Intersect_Triangle(Vector P, Vector D, Vector V0, Vector V1, VectorV2)
{
"VektorDifferenz" zieht einfach vom Vektor V1 den Vektor V0 ab und speichert den neuen Vektor in E1
Vector E1 = VectorDifferenz(V1,V0);
Vector E2 = VectorDifferenz(V2,V0);

Vector H = Kreuzprodukt(D,E2);

float a = ScalarProdukt(E1,H);

Übersetzt: Wenn a = 0 (also Gerade parallel zur Fläche), der PC rundet aber nicht/falsch, deshalb verschafft man ihm etwas "Spielraum"
if((a > -0.00001) && (a < 0.00001))return false;

float f = 1/a;

Vector S = VectorDifferenz(P,V0);

float u = f * ScalarProdukt(S,H);

Übersetzt: Wenn u < 0 oder u > 1
if((u < 0.0) || (u > 1.0))return false;

Vektor Q = KreuzProdukt(S,E1);

float v = f * ScalarProdukt(D,Q);

Übersetzt: Wenn v < 0 oder (u+v) > 1
if((v < 0.0) || ((u + v) > 1.0))return false;
else return true;
}

Ich verlange natürlich keine fertige Lösung, schön wäre aber eine "Schritt für Schritt"-Anleitung, gerne auch in Worten.

Danke!

27.09.2011, 17:51

Parallelepiped

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)
Damit es bezüglich des Problems keine Unklarheiten gibt:

1) Ich suche eine Vorgehensweise zum Berechnen des Schnittpunktes zwischen einer Dreiecksfläche und einer Geraden im Dreidimensionalen. Von der Dreiecksfläche sind die drei Eckpunkte bekannt, von der Geraden eine Aufhängepunkt und ein Richtungsvektor.

2) Da das ganze am Ende von einem Programm durchgerechnet werden soll, dürfen keine Gleichungssysteme zum Lösen verwendet werden (siehe auch das Code-Beispiel oben). Ich brauche eine Schritt-Für-Schritt-Anleitung, man muss also nichts mit Informatik am Hut haben.

3) Bis auf Gleichungssysteme ist aber (fast) alles erlaubt: Scalarprodukte, Kreuzprodukte, Vektoren addieren und subtrahieren, etc.)

Über eine hilfreiche Antwort würde ich mich sehr freuen, weil diese Berechnung ein elementarer Teil meines Projektes ist. Danke!

28.09.2011, 17:33

Parallelepiped

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)
Niemand?? Hier gibt es doch bestimmt hunderte die sich damit auskennen Augenzwinkern

29.09.2011, 12:35

riwe

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)

Zitat:

Original von Parallelepiped
Niemand?? Hier gibt es doch bestimmt hunderte die sich damit auskennen Augenzwinkern

du hast es nicht anders gewollt:

$\begin{eqnarray*} g:\quad{ }\vec{x}=\vec{p}+\lambda\cdot\vec{r} \end{eqnarray*}$

$\begin{eqnarray*} \Delta{ABC}\quad{ }\text{}\quad{ }\vec{b}=\overrightarrow{AC}\wedge\vec{c}=\overrightarrow{AB}\to\vec{n}=\vec{b}\times\vec{c} \end{eqnarray*}$

$\begin{eqnarray*} \vec{a}=\overrightarrow{OA} \end{eqnarray*}$

$\begin{eqnarray*} \text{test:}\quad{ }\vec{n}\cdot\vec{r}=0 \end{eqnarray*}$

die koordinaten des schnittpunktes lauten

$\begin{eqnarray*} \vec{s}=\vec{p}-\frac{(\vec{p}-\vec{a})\cdot\vec{n}}{\vec{r}\cdot\vec{n}}\cdot\vec{r} \end{eqnarray*}$

$\begin{eqnarray*} \vec{s}=\vec{a}+\beta\cdot\vec{b}+\gamma\cdot\vec{c} \end{eqnarray*}$

$\begin{eqnarray*} \beta=\frac{(\vec{s}-\vec{a})\cdot\vec{b}\cdot c^2-(\vec{b}\cdot\vec{c})\cdot((\vec{s}-\vec{a})\cdot\vec{c})}{(\vec{b}\times\vec{c})^2} \end{eqnarray*}$

$\begin{eqnarray*} \gamma=\frac{(\vec{s}-\vec{a})\cdot\vec{c}\cdot b^2-(\vec{b}\cdot\vec{c})\cdot((\vec{s}-\vec{a})\cdot\vec{b})}{(\vec{b}\times\vec{c})^2} \end{eqnarray*}$

S liegt innerhalb des 3ecks, wenn gilt

$\begin{eqnarray*} 0\leq\beta,\gamma\leq 1\wedge 0\leq \beta+\gamma\leq 1 \end{eqnarray*}$

umsetzen darfst du das selbst, ist ja nicht allzu schwer

fehler etc. sind keineswegs ausgeschlossen Augenzwinkern

edit: nun sollte es möglicherweise stimmen Augenzwinkern

edit 2014: b = AC statt AB

29.09.2011, 13:42

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Parallelepiped
Und ich bin allergisch gegen Formelschreibweisen Augenzwinkern

Die muss ich ja sonst auch wieder für den PC übersetzen...

Mal ehrlich: Programmierer mit dieser Haltung sollten sich andere Schwerpunkte suchen, z.B. designen von Webseiten o.ä.

06.10.2011, 10:51

Parallelepiped

Auf diesen Beitrag antworten »

@riwe: Danke dir!
@René: Danke auch für die hilfreiche, themenbezogene Antwort!

21.01.2014, 11:53

bass05081986

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)
Hallo riwe, es funktioniert aber wie kommst du auf diese Gleichungen??? Kannst du mir das erklären??? Wäre sehr nett!

21.01.2014, 12:05

riwe

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)

Zitat:

Original von bass05081986
Hallo riwe, es funktioniert aber wie kommst du auf diese Gleichungen??? Kannst du mir das erklären??? Wäre sehr nett!

woher soll ich das heute noch wissen verwirrt

im Ernst: das braucht jetzt eine Weile, ich muß mir das erst wieder anschauen

21.01.2014, 14:23

riwe

Auf diesen Beitrag antworten »

RE: Gerade + Dreieck (Schnittpunkt)
der Test dient dazu festzustellen, ob tatsächlich genau 1 Schnittpunkt existiert,
wichtig, da im Nenner das entsprechende Skalarprodukt steht.

dann wird wie üblich der Schnittpunkt S bestimmt.

nun soll S im 3eck liegen, sein Ortsvektor kann daher als Linearkombination der beiden Seitenvektoren dargestellt werden.
die beiden Parameter werden aus dieser Darstellung gewonnen in der üblichen Art und Weise, indem man jeweils einen eliminiert.

Neue Frage »

Antworten »

Gerade + Dreieck (Schnittpunkt)

Verwandte Themen