Algorithmus Strecke x Dreieck < Geraden und Ebenen < Lin. Algebra/Vektor < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:45 Fr 24.07.2020 | | Autor: | urben |
Hallo,
Für ein Programmierprojekt versuche ich derzeit einen Algorithmus umzusetzen, der effizient auf einen möglichen Schnittpunkt zwischen einer Strecke und einem Dreieck prüft.
Mein Problem ist dass ich scheinbar missverstehe wie dieser Algorithmus funktioniert. Diese Frage ist also eher die nach der Unterstützung des Leseverständnisses. :P
![[]](/images/popup.gif) Es geht um den in dieser pdf (englisch) beschriebenen Algorithmus.
Ich verstehe diesen Algorithmus folgendermaßen:
Ebenen werden definiert durch
[mm]\vektor{x \\ y \\ z}*\overrightarrow{n}+d=0[/mm]
[mm] (|\overrightarrow{n}| [/mm] muss nicht 1 sein)
Das Dreieck mit den Punkten A, B und C wird definiert durch drei Ebenen:
[mm]\overrightarrow{n_{0}} = \overrightarrow{AB} \times \overrightarrow{AC},\ d_{0} = -A * \overrightarrow{n_{0}}[/mm]
und
[mm]\overrightarrow{n_{1}} = \bruch{\overrightarrow{AC} \times \overrightarrow{n_{0}}}{|\overrightarrow{n_{0}}|^{2}},\ d_{1} = -A * \overrightarrow{n_{1}}[/mm]
und
[mm]\overrightarrow{n_{2}} = \bruch{\overrightarrow{n_{0}} \times \overrightarrow{AB}}{|\overrightarrow{n_{0}}|^{2}},\ d_{2} = -A * \overrightarrow{n_{2}}[/mm]
Die Strecke wird definiert mit der Parameterform einer Geraden:
[mm]P(t) = \overrightarrow{o} + t * \overrightarrow{d}[/mm]
[mm] t_{max} [/mm] = maximale Wert für t
Es werden diverse Variablen im Algorithmus benötigt. Diese sind:
[mm]det = \overrightarrow{d} * \overrightarrow{n_{0}}[/mm]
[mm]t' = d_{0} - (\overrightarrow{o} * \overrightarrow{n_{0}})[/mm]
[mm]P(t)' = det * \overrightarrow{o} + t' * \overrightarrow{d}[/mm]
[mm]u' = P(t)' * \overrightarrow{n_{1}} + det * \overrightarrow{d_{1}}[/mm]
[mm]v' = P(t)' * \overrightarrow{n_{2}} + det * \overrightarrow{d_{2}}[/mm]
[mm]\vektor{t \\ u \\ v} = \bruch{1}{det} * \vektor{t' \\ u' \\ v'}[/mm]
Der Algorithmus stellt die Kollision fest wenn folgende Bedingungen erfüllt sind: (sign prüft auf das Vorzeichen)
[mm]sign(t') = sign(det * t_{max} - t')[/mm]
[mm]sign(u') = sign(det - u')[/mm]
[mm]sign(v') = sign(det - u' - v')[/mm]
Diese sind equivalent mit diesen Bedingungen:
[mm]0 \le t \le t_{max}[/mm]
[mm]u \ge 0[/mm]
[mm]v \ge 0[/mm]
[mm](u + v) \le 1[/mm]
Nun das Problem: In diesen Termen ist ein oder mehrere Fehler.
Gegeben ist das Dreieck:
[mm]A(2, 1, 1),\ B(1, 2, 2),\ C(3, 2, 1)[/mm]
Dieses wird gemäß den Vorgaben unter anderem definiert durch:
[mm]n_{0} = \vektor{-1 \\ 1 \\ -2},\ d_{0} = 3[/mm]
Gegeben ist die Gerade, die darauf angepasst ist den Punkt B zu treffen:
[mm]\overrightarrow{o} = \vektor{1 \\ 4 \\ 2},\ \overrightarrow{d} = \vektor{0 \\ -1 \\ 0},\ t_{max} = 10[/mm]
Zusammen ergeben sie Werte für diese Variablen...:
[mm]det = -1,\ t' = 4[/mm]
Doch obwohl hier ein Treffer erfolgen müsste, schlägt die erste Bedingung fehl:
[mm]sign(t') = sign(det * t_{max} - t')[/mm]
[mm]sign(4) \not= sign(-14)[/mm]
Beide weiteren Bedingungen schlagen auch fehl wenn man das vollständig durchrechnet.
Wo habe ich also etwas falsch verstanden?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:11 Mo 27.07.2020 | | Autor: | urben |
Ich habe die Frage nun auch auf math.stackexchange.com gepostet:
https://math.stackexchange.com/questions/3770643/ray-triangle-intersection-algorithm-havel-herout
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:30 Mo 27.07.2020 | | Autor: | hase-hh |
Moin!
Mal ein paar krause Gedanken, wie man die Aufgabe verstehen kann.
Gegeben ist ein Dreieck und eine Strecke.
Entweder soll geprüft werden, ob die Strecke das Dreieck schneidet (1).
Oder es soll geprüft werden, ob die Strecke innnerhalb des Dreiecks liegt (2).
zu (1)
Ich stelle die Gerade g auf, auf der die Strecke liegt.
Ich stelle die Geraden h, i, k auf, auf der die Seiten des Dreiecks liegen.
Dann berechne ich die Schnittpunkte von g mit h, i, k.
Für jeden Schnittpunkt ist dann zu prüfen, ob dieser auf der Strecke und auf der jeweiligen Seite des Dreiecks liegt.
zu (2) --- Ich vermute mal, die Aufgabe ist eher in diesem Sinn gemeint.
Ich stelle eine Ebene auf, in der das Dreieck liegt.
Ich stelle eine Gerade auf, auf der die Strecke liegt.
Ich berechne den Schnittpunkt der Geraden mit der Ebene.
Falls es einen Schnittpunkt gibt, ist zu prüfen, ob dieser auf der Strecke liegt.
Liegt der Schnittpunkt auf der Strecke, ist zu prüfen, ob dieser innerhalb des Dreiecks liegt.
Den letzten Punkt könnte man über die Paramterform der Ebene lösen...
> Hallo,
>
> Für ein Programmierprojekt versuche ich derzeit einen
> Algorithmus umzusetzen, der effizient auf einen möglichen
> Schnittpunkt zwischen einer Strecke und einem Dreieck
> prüft.
>
> Mein Problem ist dass ich scheinbar missverstehe wie dieser
> Algorithmus funktioniert. Diese Frage ist also eher die
> nach der Unterstützung des Leseverständnisses. :P
>
>
> Es geht um den in dieser pdf (englisch) beschriebenen Algorithmus.
>
> Ich verstehe diesen Algorithmus folgendermaßen:
>
> Ebenen werden definiert durch
> [mm]\vektor{x \\ y \\ z}*\overrightarrow{n}+d=0[/mm]
Anmerkung:
Die Allgemeine Normalenform einer Ebene lautet:
[mm] (\vec{x} -\vec{a})*\vec{n} [/mm] = 0
[mm] \vec{x}*\vec{n} [/mm] - d = 0
> [mm](|\overrightarrow{n}|[/mm] muss nicht 1 sein)
>
> Das Dreieck mit den Punkten A, B und C wird definiert durch
> drei Ebenen:
Wieso durch drei Ebenen? Soll hier nicht einfach eine Ebene berechnet werden, in der das Dreieck liegt?
> [mm]\overrightarrow{n_{0}} = \overrightarrow{AB} \times \overrightarrow{AC},\ d_{0} = -A * \overrightarrow{n_{0}}[/mm]
>
> und
> [mm]\overrightarrow{n_{1}} = \bruch{\overrightarrow{AC} \times \overrightarrow{n_{0}}}{|\overrightarrow{n_{0}}|^{2}},\ d_{1} = -A * \overrightarrow{n_{1}}[/mm]
>
> und
> [mm]\overrightarrow{n_{2}} = \bruch{\overrightarrow{n_{0}} \times \overrightarrow{AB}}{|\overrightarrow{n_{0}}|^{2}},\ d_{2} = -A * \overrightarrow{n_{2}}[/mm]
>
> Die Strecke wird definiert mit der Parameterform einer
> Geraden:
> [mm]P(t) = \overrightarrow{o} + t * \overrightarrow{d}[/mm]
>
> [mm]t_{max}[/mm] = maximale Wert für t
Eine Strecke ist ein Teil einer Geraden. Sie wird durch einen Anfangs- und einen Endpunkt festgelegt.
Müsste hier nicht sowohl ein maximaler Wert für t als auch ein minimaler Wert für t berechnet werden?
> Es werden diverse Variablen im Algorithmus benötigt. Diese
> sind:
>
> [mm]det = \overrightarrow{d} * \overrightarrow{n_{0}}[/mm]
> [mm]t' = d_{0} - (\overrightarrow{o} * \overrightarrow{n_{0}})[/mm]
>
> [mm]P(t)' = det * \overrightarrow{o} + t' * \overrightarrow{d}[/mm]
>
> [mm]u' = P(t)' * \overrightarrow{n_{1}} + det * \overrightarrow{d_{1}}[/mm]
>
> [mm]v' = P(t)' * \overrightarrow{n_{2}} + det * \overrightarrow{d_{2}}[/mm]
>
> [mm]\vektor{t \\ u \\ v} = \bruch{1}{det} * \vektor{t' \\ u' \\ v'}[/mm]
>
> Der Algorithmus stellt die Kollision fest wenn folgende
> Bedingungen erfüllt sind: (sign prüft auf das
> Vorzeichen)
> [mm]sign(t') = sign(det * t_{max} - t')[/mm]
> [mm]sign(u') = sign(det - u')[/mm]
>
> [mm]sign(v') = sign(det - u' - v')[/mm]
>
> Diese sind equivalent mit diesen Bedingungen:
> [mm]0 \le t \le t_{max}[/mm]
> [mm]u \ge 0[/mm]
> [mm]v \ge 0[/mm]
> [mm](u + v) \le 1[/mm]
>
> Nun das Problem: In diesen Termen ist ein oder mehrere
> Fehler.
>
> Gegeben ist das Dreieck:
> [mm]A(2, 1, 1),\ B(1, 2, 2),\ C(3, 2, 1)[/mm]
>
> Dieses wird gemäß den Vorgaben unter anderem definiert
> durch:
> [mm]n_{0} = \vektor{-1 \\ 1 \\ -2},\ d_{0} = 3[/mm]
[mm] \vektor{-1 \\ 1 \\ -2} [/mm] ist ein Normalenvektor der Ebene, in der das Dreieck liegt.
Äh, üblicherweise werden Einheitsvektoren mit einem Index 0 bezeichnet. Dies trifft für [mm] n_0 [/mm] hier schon mal nicht zu.
Dann wäre [mm] n_0 [/mm] = [mm] \vektor{-1*\wurzel{6} \\ 1*\wurzel{6} \\ -2*\wurzel{6}} [/mm] ...
Aber möglicherweise ist es hier anders gemeint?!??
Ok, ich verwende im folgenden mal deine Variablennamen...
Aus den drei Punkten A,B,C kann eine Ebene aufgestellt werden.
Ich mache es mal "umständlich" orthodox über die Parameterform.
A(2, 1, 1), B(1, 2, 2), C(3, 2, 1)
[mm] \vec{x} [/mm] = [mm] \vektor{2 \\ 1 \\ 1} +r*\vektor{-1 \\ 1 \\ 1} [/mm] + [mm] s*\vektor{1 \\ 1 \\ 0}
[/mm]
Normalenform:
[mm] (\vec{x} [/mm] - [mm] \vektor{2 \\ 1 \\ 1})*\vektor{-1 \\ 1 \\ -2} [/mm] = 0
[mm] \vec{x}*\vektor{-1 \\ 1 \\ -2} [/mm] - (-3) = 0
=> [mm] d_0 [/mm] = - 3 nicht +3, oder nicht?
> Gegeben ist die Gerade, die darauf angepasst ist den Punkt
> B zu treffen:
> [mm]\overrightarrow{o} = \vektor{1 \\ 4 \\ 2},\ \overrightarrow{d} = \vektor{0 \\ -1 \\ 0},\ t_{max} = 10[/mm]
>
> Zusammen ergeben sie Werte für diese Variablen...:
> [mm]det = -1,\ t' = 4[/mm]
M.E. müsste t' = -2 sein.
t' = [mm] d_0 [/mm] - [mm] \vec{\sigma}*\vec{n_0}
[/mm]
t' = -3 - [mm] (\vektor{-1 \\ 1 \\ -2}*\vektor{0 \\ -1\\ 0})
[/mm]
t' = -3 - (-1)
t' = -2
> Doch obwohl hier ein Treffer erfolgen müsste, schlägt die
> erste Bedingung fehl:
> [mm]sign(t') = sign(det * t_{max} - t')[/mm]
> [mm]sign(4) \not= sign(-14)[/mm]
>
> Beide weiteren Bedingungen schlagen auch fehl wenn man das
> vollständig durchrechnet.
>
> Wo habe ich also etwas falsch verstanden?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:02 Mo 27.07.2020 | | Autor: | urben |
Hallo,
Ich fürchte es kam nicht ganz rüber worum es mir geht. Ich suche nicht nach einem Weg einen Schnittpunkt zwischen Dreieck und Strecke zu ermitteln. Den hab ich ja eben schon.
Mir ging es ganz explizit um die Methode die in der pdf Datei beschrieben wird. Ich habe auch schon ähnliche Wege versucht wie du sie beschreibst, da das aber in einem Programm umgesetzt werden soll, will ich den effizientesten Weg (aus Sicht der Rechenkraft) verwenden, eben jener verlinkte.
Den Weg den ich beschreibe habe ich davon, nur da das Ergebnis noch nicht stimmt, will ich wissen was ich im Sinne jenes Algorithmuses falsch gemacht habe.
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:57 Di 28.07.2020 | | Autor: | hase-hh |
1. Zunächst ist mir dein Problem, nämlich das, was das Programm leisten soll, unklar. Ich habe dir zwei mögliche Weisen, die von dir gepostete Aufgabenstellung zu verstehen, gegeben.
Davon hängt selbstverständlich der Lösungsweg ab.
2. Ferner bin ich auf einen Fehler gestoßen, der sicher auch den gesuchten Algorithmus beeinflusst. [Ich habe selbst einige Jahre programmiert.]
3. Ob der dargestellte Weg in der pdf-Datei wirklich der effizienteste ist, ist zunächst - ausführlich - zu begründen.
Das einfach vorauszusetzen, ist mir zu flach, sorry. Wie auch immer.
4. Ich würde auch gerne wissen, ob das Problem wirklich auf Abiturniveau gelöst werden soll, oder ob es nicht schon Universitäsniveau hat.
5. Falls es nur um einen "Fehler" in dem Algorithmus geht, den du einfach nur abschreibst... So eine Fehlersuche wäre dann deine Aufgabe, die ziemlich zeitaufwändig sein kann.
Aus Programmierersicht kann ich nur antworten:
Mögliche Fehlerquellen
alle verwendeten Variablen müssen definiert sein
alle Variablen müssen gültige Werte aufweisen [zu jedem Zeitpunkt]
Jedes Zeichen, was zuviel oder zuwenig ist, kann zu fehlerhaften Ergebnissen führen. Gerade diese Fehler sind oft schwer zu finden.
Also bspw. [mm] n_0 [/mm] statt n oder t statt t' usw.
6. Dir und auch denen, die hier im Forum gerne Antworten geben, würde es bestimmt helfen, wenn du deinen Algorithmus Schritt für Schritt erklären würdest, soweit du diesen verstanden hast.
Je klarer du deine Frage formulieren kannst, desto mehr und genauere Antworten wirst du bekommen.
Sonst fürchte ich, wird es den Helfern hier vermutlich zu zeitaufwändig sein, die pdf-Datei [längerer englischer Text] im einzelnen nachzuvollziehen...
Viel Glück!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:45 Di 28.07.2020 | | Autor: | chrisno |
Die Autoren geben an, das ihr Algorithmus besser ist, als die bisherigen.
Das halte ich für eine ausreichende Motivation, zu versuchen, diesen Algorithmus zu implementieren.
Es geht dem Ratsuchen gerade darum, den beschriebenen Algorithmus nachzuvollziehen.
Dabei hat es ein Problem gegeben, und er hofft, einen Tipp zur Lösung zu bekommen.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:29 Mi 29.07.2020 | | Autor: | chrisno |
Ich habe dein Beispiel nachgerechnet und kann deine Rechnungen bestätigen.
Mehr zu tun habe ich nicht vor. Nun muss nämlich der Artikel Gleichung für Gleichung nachgerechnet werden. Denn auch wenn ich tmax auf 2 setze, passiert in der Vorzeichengleichung nichts Besonderes.
Allerdings musst du noch nachschauen, ob die Bedingung:
"the axis with the largest projection of the triangles normal vector ist discarded"
bei deiner Wahl erfüllt ist.
Du kannst auch die Autoren anschreiben, dsa ist wahrscheinlich der einfachste Weg.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:19 Sa 08.08.2020 | | Autor: | urben |
Ich habe den Fehler gefunden:
$ [mm] d_{0} [/mm] = -A [mm] \cdot{} \overrightarrow{n_{0}} [/mm] $
...ist falsch, es muss sein:
$ [mm] d_{0} [/mm] = A [mm] \cdot{} \overrightarrow{n_{0}} [/mm] $
Die Terme für [mm] d_{1} [/mm] und [mm] d_{2} [/mm] sind aber richtig.
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:41 Sa 08.08.2020 | | Autor: | chrisno |
Ich gratuliere. Teile deinen Fund den Autoren mit.
|
|
|
|
