Strahl Dreieck Kollision

    Ich hab gestern Abi dadrüber geschrieben.
    Es geht dir also nur um den Schnittpunkt von dem Dreieck mit der Gerade?
    Müsste machbar sein, ich setze mich mal dran...

    /Edit:
    mein Ansatz (is noch ned fertig, weil der Schnittpunkt noch nicht ausgerechnet wird. Aber alle Grundrechenarten mit Vektoren sind drin, damit kann man weiter machen. Habe jetzt keine Zeit mehr, aber heute abend oder morgen mach ich das auch noch)

    Spoiler anzeigen
    [autoit]

    $schnittpunkt = _intersection("(3|4|5)", "(6|7|9)", "(9|10|11)", "(12|13|14)", "(15|16|17)")

    [/autoit] [autoit][/autoit] [autoit]

    Func _intersection($dreieckA, $dreieckB, $dreieckC, $Aufpunktgerade, $Richtungsvektorgerade)
    Local $splitarr[5] = [$dreieckA, $dreieckB, $dreieckC, $Aufpunktgerade, $Richtungsvektorgerade]
    For $i = 0 To 4
    If Not StringRegExp($splitarr[$i], "\(\d+\|\d+\|\d+\)") Then Return -1
    Next
    $dreieckA = StringSplit(StringTrimRight(StringTrimLeft($splitarr[0], 1), 1), "|")
    $dreieckB = StringSplit(StringTrimRight(StringTrimLeft($splitarr[1], 1), 1), "|")
    $dreieckC = StringSplit(StringTrimRight(StringTrimLeft($splitarr[2], 1), 1), "|")
    $Aufpunktgerade = StringSplit(StringTrimRight(StringTrimLeft($splitarr[3], 1), 1), "|")
    $Richtungsvektorgerade = StringSplit(StringTrimRight(StringTrimLeft($splitarr[4], 1), 1), "|")

    [/autoit] [autoit][/autoit] [autoit]

    ; Aufpunkt von Ebene = A
    ; 1. Richtungsvektor = -A+B = B-A
    ; 2. Richtungsvektor = -A+C = C-A
    $dreieckrichtungsvektor1 = _calculatevector($dreieckB, '-', $dreieckA)
    $dreieckrichtungsvektor2 = _calculatevector($dreieckC, '-', $dreieckA)

    [/autoit] [autoit][/autoit] [autoit]

    ; normalenvektor Ebene = $dreieckrichtungsvektor1 kreuz $dreieckrichtungsvektor2
    $normalenvektor = _calculatevector($dreieckA, 'x', $dreieckB)
    ; Ebenengleichung: 0 = $normalenvektor * (x - Aufpunkt)
    ; <=> 0 = $normalenvektor * (x - $dreieckA)
    ; <=> 0 = $normalenvektor *(skalar) x - $normalenvektor *(skalar) $dreieckA

    [/autoit] [autoit][/autoit] [autoit]

    $c = _calculatevector($normalenvektor, 'scalar', $dreieckA)
    ; Ebenengleichung: 0 = $normalenvektor * x - $c
    ; Geradengleichung: x = $Aufpunktgerade + lamda * $Richtungsvektorgerade

    [/autoit] [autoit][/autoit] [autoit]

    ; --> Einsetzen von Geradengleichung in Ebenengleichung. Umformen nach lamda. Einsetzen von lamda in Geradengleichung
    ; Ausrechnen von Punkt --> Schnittpunkt von Ebene und Gerade
    ; Schauen ob Punkt in Dreieck liegt
    EndFunc ;==>_intersection

    [/autoit] [autoit][/autoit] [autoit]

    Func _calculatevector($parameter1, $arithmetic, $parameter2)
    ; kann vektoren addieren, subtrahieren, dividieren, multiplizieren + kreuzprodukt ausrechnen ($aithmetic muss 'x' sein für Kreuzprodukt)
    ; + Skalarprodukt ($aithmetic muss 'scalar' sein für Skalarprodukt)
    Switch $arithmetic
    Case 'scalar'
    Return $parameter1[1] * $parameter2[1] + $parameter1[2] * $parameter2[2] + $parameter1[3] * $parameter2[3]
    Case 'x'
    Local $result[4]
    $result[1] = ($parameter1[2] * $parameter2[3]) - ($parameter1[3] * $parameter2[2])
    $result[2] = $parameter1[3] * $parameter2[1] - $parameter1[1] * $parameter2[3]
    $result[3] = $parameter1[1] * $parameter2[2] - $parameter1[2] * $parameter2[1]
    Case Else
    Local $result[4]
    $result[1] = Execute($parameter1[1] & $arithmetic & $parameter2[1])
    $result[2] = Execute($parameter1[2] & $arithmetic & $parameter2[2])
    $result[3] = Execute($parameter1[3] & $arithmetic & $parameter2[3])
    EndSwitch
    Return $result
    EndFunc ;==>_calculatevector

    [/autoit]

    Einmal editiert, zuletzt von anno2008 (22. April 2010 um 14:32)

    Genau, es soll geprüft werden ob die Gerade durchs Dreieck geht oder nicht (mit Rückgabe des Punktes).

    Endlich mal ein Abiturient, da ist man noch fit in Sachen Vektoren :thumbup:

    edit \ Der interessante Teil fehlt noch :D
    Bin sehr gespannt auf deine Lösung.

    Ich habe mir überlegt man könnte auch einfach das dreieck so drehen, dass alle y coordianten 0 sind (bzw x, z). Dann könnte man es leicht aussrechnen, jedoch braucht man dafür sin, cos etc. und dadruch würde hinterher der rechenaufwand bestimmt 3mal so groß sein, als wenn man es mit dem bereits genannten wege macht.
    Achja und erstmal danke für deine Mühen :)

    Einmal editiert, zuletzt von moritz1243 (22. April 2010 um 15:18)

    Ok, den Schnittpunkt mit der Ebene, in der auch das Dreieck liegt kann ich ausrechnen.

    Spoiler anzeigen
    [autoit]

    $schnittpunkt = _intersection("(3|4|5)", "(6|7|9)", "(9|10|11)", "(12|13|14)", "(15|16|17)")
    MsgBox(0, "", $schnittpunkt)

    [/autoit] [autoit][/autoit] [autoit]

    Func _intersection($dreieckA, $dreieckB, $dreieckC, $Aufpunktgerade, $Richtungsvektorgerade)
    Local $splitarr[5] = [$dreieckA, $dreieckB, $dreieckC, $Aufpunktgerade, $Richtungsvektorgerade], $lambda[4]
    For $i = 0 To 4
    If Not StringRegExp($splitarr[$i], "\(\d+\|\d+\|\d+\)") Then Return -1
    Next
    $dreieckA = StringSplit(StringTrimRight(StringTrimLeft($splitarr[0], 1), 1), "|")
    $dreieckB = StringSplit(StringTrimRight(StringTrimLeft($splitarr[1], 1), 1), "|")
    $dreieckC = StringSplit(StringTrimRight(StringTrimLeft($splitarr[2], 1), 1), "|")
    $Aufpunktgerade = StringSplit(StringTrimRight(StringTrimLeft($splitarr[3], 1), 1), "|")
    $Richtungsvektorgerade = StringSplit(StringTrimRight(StringTrimLeft($splitarr[4], 1), 1), "|")
    ; Aufpunkt von Ebene = A
    ; 1. Richtungsvektor = -A+B = B-A
    ; 2. Richtungsvektor = -A+C = C-A
    $dreieckrichtungsvektor1 = _calculatevector($dreieckB, '-', $dreieckA)
    $dreieckrichtungsvektor2 = _calculatevector($dreieckC, '-', $dreieckA)
    ; normalenvektor Ebene = $dreieckrichtungsvektor1 kreuz $dreieckrichtungsvektor2
    $normalenvektor = _calculatevector($dreieckrichtungsvektor1, 'x', $dreieckrichtungsvektor2)
    ; Ebenengleichung: 0 = $normalenvektor * (x - Aufpunkt)
    ; <=> 0 = $normalenvektor * (x - $dreieckA)
    ; <=> 0 = $normalenvektor *(skalar) x - $normalenvektor *(skalar) $dreieckA
    $c = _calculatevector($normalenvektor, 'scalar', $dreieckA)
    ; Ebenengleichung: 0 = $normalenvektor * x - $c
    ; Geradengleichung: x = $Aufpunktgerade + lambda * $Richtungsvektorgerade
    ; --> Einsetzen von Geradengleichung in Ebenengleichung. Umformen nach lambda. Einsetzen von lambda in Geradengleichung
    ; --> neue Gleichung $normalenvektor *(skalar) $Aufpunktgerade + $normalenvektor *(skalar) $Richtungsvektorgerade * lambda - $c = 0
    $lambda[1] = (0 - _calculatevector($normalenvektor, 'scalar', $Aufpunktgerade) + $c) / _calculatevector($normalenvektor, 'scalar', $Richtungsvektorgerade)
    $lambda[2] = $lambda[1]
    $lambda[3] = $lambda[1]
    ; lambda in Geradengleichung einsetzen
    $intersection = _calculatevector($Aufpunktgerade, '+', _calculatevector($lambda, '*', $Richtungsvektorgerade))
    ;~ _ArrayDisplay($intersection)
    Return '(' & $intersection[1] & '|' & $intersection[2] & '|' & $intersection[3] & ')'
    EndFunc ;==>_intersection

    [/autoit] [autoit][/autoit] [autoit]

    Func _calculatevector($parameter1, $arithmetic, $parameter2)
    ; kann vektoren addieren, subtrahieren, dividieren, multiplizieren + kreuzprodukt ausrechnen ($aithmetic muss 'x' sein für Kreuzprodukt)
    ; + Skalarprodukt ($aithmetic muss 'scalar' sein für Skalarprodukt)
    Switch $arithmetic
    Case 'scalar'
    Return $parameter1[1] * $parameter2[1] + $parameter1[2] * $parameter2[2] + $parameter1[3] * $parameter2[3]
    Case 'x'
    Local $result[4]
    $result[1] = ($parameter1[2] * $parameter2[3]) - ($parameter1[3] * $parameter2[2])
    $result[2] = $parameter1[3] * $parameter2[1] - $parameter1[1] * $parameter2[3]
    $result[3] = $parameter1[1] * $parameter2[2] - $parameter1[2] * $parameter2[1]
    Case Else
    Local $result[4]
    $result[1] = Execute($parameter1[1] & $arithmetic & $parameter2[1])
    $result[2] = Execute($parameter1[2] & $arithmetic & $parameter2[2])
    $result[3] = Execute($parameter1[3] & $arithmetic & $parameter2[3])
    EndSwitch
    Return $result
    EndFunc ;==>_calculatevector

    [/autoit]

    Ob der Punkt im Dreieckt liegt kann man nicht so einfach bestimmen. Das ist sehr viel komplexer.

    Man muss prüfen ob AP = r * AB + s * AC
    mit
    r >= 0 und u <= 1
    s >= 0 und s <= 1
    r+s = 1

    Zuerst musst du es hinbekommen aus der Linearkombination r und s zu berechnen. Da das ein Gleichungsystem mit 2 Unbekannten ist, wird das kompliziert. Die Lösung, die am einfachsten zu implementieren ist, ist der Gaußsche Algorithmus.
    Einfach ist es bestimmt nicht, aber mit etwas Zeit machbar.

    /Edit:
    Jetzt wo ich den Thread komplett durchgelesen habe, sehe ich, dass nuts das alles schonmal geschrieben hat :D.
    Sry, dann hab ich dir jetzt gar nicht weitergeholfen.
    http://www.cs.virginia.edu/~gfx/Courses/2…ntersection.pdf
    Diesen Algorithmus könnte man umsetzen. Aber ich habe mich nicht näher damit beschäftigt. Morgen sehen wir weiter :)
    http://www.cs.princeton.edu/courses/archiv…cast/sld016.htm
    Der 1. Schritt ist immerhin gemacht :D.

    2 Mal editiert, zuletzt von anno2008 (23. April 2010 um 00:55)

    Zitat

    Ob der Punkt im Dreieckt liegt kann man nicht so einfach bestimmen. Das ist sehr viel komplexer.

    2 Möglichkeiten:
    -Wenn Punkt im Dreieck, dann ist die Summe der 3 Winkel zwischen den Geraden PA,PB und PC = 360° ansonsten liegt der Punkt nicht im Dreieck.
    -Gleichungssystem lösen: stell die 3 Gleichungen auf und ich mach den Löser, aber der Vektorkram war noch nie mein Ding ^^

    Zitat von Andy

    2 Möglichkeiten:
    -Wenn Punkt im Dreieck, dann ist die Summe der 3 Winkel zwischen den Geraden PA,PB und PC = 360° ansonsten liegt der Punkt nicht im Dreieck.
    -Gleichungssystem lösen: stell die 3 Gleichungen auf und ich mach den Löser, aber der Vektorkram war noch nie mein Ding ^^

    Die Bedingung gilt im Koordinatensystem mit 3 Achsen glaube ich nicht. Bist du dir da sicher?

    moritz1243, kannst du mir vielleicht Koordinaten nennen, bei denen der Punkt im Dreieck liegt?
    Ich habe hier eine Lösung, nur muss ich zuerst schauen, ob das was ich da gemacht habe stimmt.

    Zitat

    Bist du dir da sicher?

    wenn du mir glaubhaft bestätigen kannst, daß ein DREIECK ein RÄUMLICHES Objekt ist, dann denk ich nochmal drüber nach ^^
    Das Dreieck ist, auch im 3-dimensionalen Raum, immer eine Ebene.

    Zitat von Andy

    wenn du mir glaubhaft bestätigen kannst, daß ein DREIECK ein RÄUMLICHES Objekt ist, dann denk ich nochmal drüber nach ^^

    Das hab ich ja nicht gesagt. ^^
    Ja, ok, wundert mich nur, warum die Lösung nirgendwo auftaucht.
    Aber eigentlich müsste es stimmen, weil immer eine Pyramide entsteht. Und die Innenwinkel können niemals 360° ergeben.
    Ok, aber trotzdem ist es komplizierter als die andere Bedingung, weil man dazu die Richtungsvektoren multiplizieren muss und dann durch das Produkt der beiden Beträge teilen muss.
    Bei der anderen braucht man nur die beiden Richtungsvektoren der Ebene, die man sowieso ausrechnen muss.

    Also als Beispiel kannst du einfach eine "Basisebenen" nehmen und den Durchstoßpunkt bei (0|0|0) setzen.

    A(0|0|0)
    B(1|0|0)
    C(0|1|0)

    D(0|0|0)
    Bewegungsvektor der Geraden beliebig.

    Oder eben den Durchstoßpunkt (Startpunkt der Geraden) einer beliebigen Ebene auf einen der 3 Dreieckspunkte legen.

    P.S: Das mit den Winkeln stimmt, ist aber auch schwierig umzusetzen. :whistling:

    anno2008: Deine dritte Bedingung für die "liegt im Dreiecke" Prüfung stimmt nicht.
    => 0<=r+s<=1

    Hey,
    also so müsste es gehen.
    Die Frage ist, ob man die Ränder des Dreiecks als Punkte im Dreieck dazuzählt.
    Wenn nicht musst du die Bedingung ändern:

    [autoit]

    $isinT = ($u >= 0) And ($v >= 0) And ($u + $v <= 1)

    [/autoit]

    Wenn man geschickt umformt brauch man keinen Gauß :). Musste aber viel lesen bis ich das verstanden hatte :D.

    Spoiler anzeigen
    [autoit]

    $schnittpunkt = _intersection("(0|0|0)", "(1|0|0)", "(0|1|0)", "(0|0|0)", "(1|0|1)")
    MsgBox(0, "", $schnittpunkt)

    [/autoit] [autoit][/autoit] [autoit]

    Func _intersection($dreieckA, $dreieckB, $dreieckC, $Aufpunktgerade, $Richtungsvektorgerade)
    Local $splitarr[5] = [$dreieckA, $dreieckB, $dreieckC, $Aufpunktgerade, $Richtungsvektorgerade], $lambda[4], $mp0[4], $isinT
    For $i = 0 To 4
    If Not StringRegExp($splitarr[$i], "\(\-?\d+\|\-?\d+\|\-?\d+\)") Then Return SetError(1)
    Next
    $dreieckA = StringSplit(StringTrimRight(StringTrimLeft($splitarr[0], 1), 1), "|")
    $dreieckB = StringSplit(StringTrimRight(StringTrimLeft($splitarr[1], 1), 1), "|")
    $dreieckC = StringSplit(StringTrimRight(StringTrimLeft($splitarr[2], 1), 1), "|")
    $Aufpunktgerade = StringSplit(StringTrimRight(StringTrimLeft($splitarr[3], 1), 1), "|")
    $Richtungsvektorgerade = StringSplit(StringTrimRight(StringTrimLeft($splitarr[4], 1), 1), "|")
    ; Aufpunkt von Ebene = A
    ; 1. Richtungsvektor = -A+B = B-A
    ; 2. Richtungsvektor = -A+C = C-A
    $dreieckrichtungsvektor1 = _calculatevector($dreieckB, '-', $dreieckA)
    $dreieckrichtungsvektor2 = _calculatevector($dreieckC, '-', $dreieckA)
    ; normalenvektor Ebene = $dreieckrichtungsvektor1 kreuz $dreieckrichtungsvektor2
    $normalenvektor = _calculatevector($dreieckrichtungsvektor1, 'x', $dreieckrichtungsvektor2)
    ; Ebenengleichung: 0 = $normalenvektor * (x - Aufpunkt)
    ; <=> 0 = $normalenvektor * (x - $dreieckA)
    ; <=> 0 = $normalenvektor *(skalar) x - $normalenvektor *(skalar) $dreieckA
    $c = _calculatevector($normalenvektor, 'scalar', $dreieckA)
    ; Ebenengleichung: 0 = $normalenvektor * x - $c
    ; Geradengleichung: x = $Aufpunktgerade + lambda * $Richtungsvektorgerade
    ; --> Einsetzen von Geradengleichung in Ebenengleichung. Umformen nach lambda. Einsetzen von lambda in Geradengleichung
    ; --> neue Gleichung $normalenvektor *(skalar) $Aufpunktgerade + $normalenvektor *(skalar) $Richtungsvektorgerade * lambda - $c = 0
    $lambda[1] = (0 - _calculatevector($normalenvektor, 'scalar', $Aufpunktgerade) + $c) / _calculatevector($normalenvektor, 'scalar', $Richtungsvektorgerade)
    $lambda[2] = $lambda[1]
    $lambda[3] = $lambda[1]
    ; lambda in Geradengleichung einsetzen
    $intersection = _calculatevector($Aufpunktgerade, '+', _calculatevector($lambda, '*', $Richtungsvektorgerade))

    [/autoit] [autoit][/autoit] [autoit]

    ; prüfen ob Punkt in Dreieck
    ; Richtungsvektor von A nach Schnittpunkt
    $richtungsvektor2 = _calculatevector($intersection, '-', $dreieckA)
    $scalar00 = _calculatevector($dreieckrichtungsvektor2, 'scalar', $dreieckrichtungsvektor2)
    $scalar01 = _calculatevector($dreieckrichtungsvektor2, 'scalar', $dreieckrichtungsvektor1)
    $scalar02 = _calculatevector($dreieckrichtungsvektor2, 'scalar', $richtungsvektor2)
    $scalar11 = _calculatevector($dreieckrichtungsvektor1, 'scalar', $dreieckrichtungsvektor1)
    $scalar12 = _calculatevector($dreieckrichtungsvektor1, 'scalar', $richtungsvektor2)
    $invDenom = 1 / ($scalar00 * $scalar11 - $scalar01 * $scalar01)
    $u = ($scalar11 * $scalar02 - $scalar01 * $scalar12) * $invDenom
    $v = ($scalar00 * $scalar12 - $scalar01 * $scalar02) * $invDenom
    $isinT = ($u >= 0) And ($v >= 0) And ($u + $v <= 1)

    [/autoit] [autoit][/autoit] [autoit]

    Return '(' & $intersection[1] & '|' & $intersection[2] & '|' & $intersection[3] & ')' & @TAB & $isinT
    EndFunc ;==>_intersection

    [/autoit] [autoit][/autoit] [autoit]

    Func _calculatevector($parameter1, $arithmetic, $parameter2)
    ; kann vektoren addieren, subtrahieren, dividieren, multiplizieren + kreuzprodukt ausrechnen ($aithmetic muss 'x' sein für Kreuzprodukt)
    ; + Skalarprodukt ($aithmetic muss 'scalar' sein für Skalarprodukt)
    Switch $arithmetic
    Case 'scalar'
    Return $parameter1[1] * $parameter2[1] + $parameter1[2] * $parameter2[2] + $parameter1[3] * $parameter2[3]
    Case 'x'
    Local $result[4]
    $result[1] = ($parameter1[2] * $parameter2[3]) - ($parameter1[3] * $parameter2[2])
    $result[2] = $parameter1[3] * $parameter2[1] - $parameter1[1] * $parameter2[3]
    $result[3] = $parameter1[1] * $parameter2[2] - $parameter1[2] * $parameter2[1]
    Case Else
    Local $result[4]
    $result[1] = Execute($parameter1[1] & $arithmetic & $parameter2[1])
    $result[2] = Execute($parameter1[2] & $arithmetic & $parameter2[2])
    $result[3] = Execute($parameter1[3] & $arithmetic & $parameter2[3])
    EndSwitch
    Return $result
    EndFunc ;==>_calculatevector

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit]

    Das Rückgabeformat ist nicht geschickt gewählt und der RegEx muss noch angepasst werden, weil bis jetzt nur Ganzzahlen erkannt werden.

    Mir ist gerade eine Idee gekommen.
    Ich hab nicht Nachgerechnet, aber nuts, du hast als Richtungsvektor für die Gerade (1|0|0) benutzt.
    Dieser Richtungsvektor ist parallel zur Ebene und somit haben die gar keinen Schnittpunkt!!!

    Also, es ist nicht zwangsläufig mein Fehler :).

    Oke war doch kein fehler drin, der fehler lag bei meiner fehlerhalften implementierung :D . Danke für eure Hilfe.
    Noch ne kleinigkeit, im ersten teil bestimmt man ja erstmal den schnittpunkt des strahl mit der ebene auf der das dreieck liegt. Wie Könnte man jetzt prüfen ob sich der punkt auf der ebene in einem quadrat befindet, welches ebenefalls auf der ebene ist?

    Einmal editiert, zuletzt von moritz1243 (25. April 2010 um 13:54)

    keiner ne idee wie man brechenne könnte ob der punkt auf der ebene in einem viereck(oder sogar in einem polygon ist)?. Und noch ne kleine frage wie bekommt man den punkt A auf einer Linie(L) der dem punkt B am nächsten ist?

    Zitat von anno2008

    Mir ist gerade eine Idee gekommen.
    Ich hab nicht Nachgerechnet, aber nuts, du hast als Richtungsvektor für die Gerade (1|0|0) benutzt.
    Dieser Richtungsvektor ist parallel zur Ebene und somit haben die gar keinen Schnittpunkt!!!

    Also, es ist nicht zwangsläufig mein Fehler :).


    Na wenn die Gerade parallel zur Ebene liegt darf zumindest nicht "True" rauskommen.
    Diesen Spezialfall sollte man möglichst früh eleminieren.