Distanz eines Punktes zu einer Dreiecksfläche bestimmen (3D)

LukasBanana

Hallo,

ich habe ein furchtbares Problem: ich kenne mich mit Vectoren usw. in der Mathematik nur halbseiden aus und möchte dennoch eine 'Collision Detection Engine' schreien. Jetzt brauche ich einen Mathematischen Algorithmus um folgendes zu berechnen und das natürlich mit einem sehr schnellen Algorithmus:

Ich habe ein Dreieck mit den Vector-Koordinaten (3D) 'V1', 'V2' und 'V3' und ich habe einen weiteren 3D Punkt bzw. Vector 'P'. Wie man einen NormalenVector (Senkrecht zu einer Fläche) berechnet weiß ich schon in etwar, allerdings möchte ich den 3D Punkt haben wo der NormalVector (von 'P' zu der Fläche) auf der Fläche steht!

Beispiel abbildung:

Y   V1   P
    |   | \ /
    |   |  /
    |   | * \
    |   V2___V3
    |__________X
   /
  /
 /
Z

Der Stern '*' mackiert den Punkt den ich haben möchte

Ich hoffe ihr versteht was ich meine und könnt mir helfen.
Danke

nevermore

Du suchst den Fußpunkt des Punktes auf der Ebene.

Wenn du weißt, wie du den Normalenvektor der Ebene bekommst, hast du schon halb gewonnen. Du kannst nun eine Geradengleichung aufstellen, wobei dein Punkt der Stützpunkt ist und der Normalenvektor der Richtungsvektor.

Du berechnest nun den Schnittpunkt dieser Geraden mit der Ebene. Dieser Schnittpunkt ist der gesuchte Fußpunkt. Die Strecke Fußpunkt-Punkt ist genau der Abstand Punkt-Ebene.

Viele Grüße

XFame

Der Abstand zur Ebene ist aber nur der gesuchte, wenn der Lotfusspunkt im Dreieck liegt.

CStoll

Ja, wenn der Fußpunkt außerhalb des Dreiecks liegt, mußt du unterscheiden, wo außerhalb:

p    /
     /
----A
    |\
    | \  g
 g  |  \
    |   \   /
    |    \ /
----B-----C
    |     |  p
 p  |  g  |

in den 'p' Bereichen müsstest du den Abstand des Ziels zum nächstgelegenen Eckpunkt bilden (Pythagoras), in den 'g' Bereichen den Abstand zur nächstgelegenen Kante (Ebene durch Zielpunkt mit der Kante als Normale, und dann wieder Schnittpunkt bestimmen).

@Lukas: Was für einen Wert benötigst du überhaupt? Wenn du nur den Abstand des Punktes von der Dreiecksebene suchst, geht das auch ohne den Fußpunkt zu bestimmen (Hessesche Normalform).

Winn

LukasBanana schrieb:

... ich kenne mich mit Vectoren usw. in der Mathematik nur halbseiden aus und möchte dennoch eine 'Collision Detection Engine' schreien.

Ohne tieferliegende Mathekenntnisse wirst Du die angebotenen Algorithmen nicht verstehen und effektiv in Programmcode implementieren können...Eine gute Adresse wäre ->> http://www.geometryalgorithms.com/algorithms.htm

Aus Deinem Text geht nicht hervor, ob das Dreieck plan zur xy-Fläche, xz-Fläche, yz-Fläche oder im allgemeinsten Fall irgendwie im Raum liegt ?

LukasBanana

- Das Dreick liegt irgendwie im Raum
- Ja, ich suche nur den Abstand vom Punkt zur Ebene (allersdings handelt es sich nicht nur um eine Ebene sondern um ein 'endliches' Dreieck)
Okay, ich schau mir den Link schon mal an, aber wie geht das wenn es auch ohne Lotfusspunkt geht?

CStoll

LukasBanana schrieb:

- Ja, ich suche nur den Abstand vom Punkt zur Ebene (allersdings handelt es sich nicht nur um eine Ebene sondern um ein 'endliches' Dreieck)

Und brauchst du eine Sonderbehandlung, wenn der Lotfußpunkt außerhalb des Dreiecks liegt? Wenn nicht, ist es letztlich egal, ob das Dreieck endlich ist.
Okay, ich schau mir den Link schon mal an, aber wie geht das wenn es auch ohne Lotfusspunkt geht?[/quote]Das steht auch unter dem Link, den Winn dir gegeben hat (Kapitel 4).

Winn

LukasBanana schrieb:

- Das Dreick liegt irgendwie im Raum
- Ja, ich suche nur den Abstand vom Punkt zur Ebene (allersdings handelt es sich nicht nur um eine Ebene sondern um ein 'endliches' Dreieck)
Okay, ich schau mir den Link schon mal an, aber wie geht das wenn es auch ohne Lotfusspunkt geht?

Okay, ich habe noch eine Feststellung und eine Frage... wenn Du nun als Betrachter auf Deinem 3D Punkt sitzen würdest und schaust Dir nun jede der drei Kanten Deines Dreicks an, entstehen wiederum drei Dreicke (3D Punkt + 1.Kante, 3D Punkt + 2.Kante und 3D + 3.Kante), d.h. es entsteht eine Pyramide mit einer dreieckigen Grundfläche und d.h. auch letztendlich, daß Du unendlich viele Lotfusspunkte besitzt !
Frage: Was Du brauchst um einen oder keinen Lotfusspunkt zu Deinem Dreieck zu berechnen ist der Richtungsvektor, welcher Dir die Richtung festlegt, in welcher Du von Deinem 3D Punkt auf das Dreieck schaust... gibt es einen solchen Richtungsvektor ?

XFame

Winn schrieb:

[..] d.h. es entsteht eine Pyramide mit einer dreieckigen Grundfläche und d.h. auch letztendlich, daß Du unendlich viele Lotfusspunkte besitzt !

Wieso unendlich viele Lotfusspunkte?

Winn

XFame schrieb:

Winn schrieb:

[..] d.h. es entsteht eine Pyramide mit einer dreieckigen Grundfläche und d.h. auch letztendlich, daß Du unendlich viele Lotfusspunkte besitzt !

Wieso unendlich viele Lotfusspunkte?

Streng genommen ist es sowieso schon kein Lotfusspunkt, wenn das Dreieck irgendwie im Raum liegt, denn vom Lotfusspunkt würde in Normalenrichtung eine Gerade entstehen, welcher nur unter bestimmten Umständen den 3D Punkt einschließt... vernachlässigst Du das der Lotfusspunkt in Normalenrichtung zum 3D Punkt gehen soll, entsteht der erwähnte Kegel und damit unendliche viele Schnittpunkte auf seiner Grundfläche... es fehlt noch immer ein Richtungsvektor, denn nur ein Punkt + Richtungsvektor ergibt eine Gerade, welche eindeutig auf Schnittverhalten mit dem Dreieck getestet werden kann...

LukasBanana

Richtungsvektor währe doch in diesem Fall der Normalenvektor oder etwa nicht?!
Allerdings weiß ich nicht was ich genau mit dem Ergebniss des Normalenvektors machen soll
Der Normalenvektor gibt schließlich nur die Richtung an in die das Dreieck 'zeigt' bzw. in welcher Richtung die senkrechte Gerade auf dem Dreieck steht. Aber wie soll ich mit diesem Wert nun arbeiten?

Werner Salomon

LukasBanana schrieb:

aber wie geht das wenn es auch ohne Lotfusspunkt geht?

ganz einfach über die Hessesche Normalform.
Es gilt für den Normalenvektor, also der Vektor, der senkrecht auf der Ebene steht:
n = (u x v) / |u x v|
mit
u = v2 - v1
und
v = v3 - v1

Die Hessesche Normalform der Ebene ist dann:
n * x = n * v1
letzteres - also 'n * v1' ist ein Skalar und kann aus v1, v2 und v3 berechnet werden (s.o.) und ist gleichzeitig der Abstand der Ebene vom Ursprung. Den Abstand von P zur Ebene erhält man dann aus
abstand = n * P - n * v1

Ist 'abstand' negativ, so liegt P 'hinter' der Ebene; d.h. entgegengesetzt zu der Richtung von n, die über das Kreuzprodukt (v2 - v1) x (v3 - v1) vorgegeben ist.

Falls Du das in C++ programmieren möchtest, ist diese Vektorklasse vielleicht hilfreich.

Gruß
Werner

PS.: Liebe Leute, die sich um dieses Forum kümmern: bitte macht, dass der Latex-Prozessor wieder geht.

LukasBanana

OK. danke!