3D Ray-Plane Intersection

[milos]

Hallo,

ich habe hier im Forum diese funktion gefunden um den Schnittpunkt eines Graden und einer Form im 3D Raum zu berechnen.

Delphi-Quellcode:

function intersectPlaneLine(const planeA, planeB, planeC: TPoint3D;
  const lineA, lineB: TPoint3D): TPoint3D;
var
  AB, AC: TPoint3D;
  planeNormal: TPoint3D;
  DE: TPoint3D;
  d, t: Single;
  divisor: Single;
begin
  // 1a
  AB := Point3D(planeB.X - planeA.X, planeB.Y - planeA.Y, planeB.Z - planeA.Z);
  AC := Point3D(planeC.X - planeA.X, planeC.Y - planeA.Y, planeC.Z - planeA.Z);
  // 1b
  // Kreuzprodukt (siehe Wikipedia, sofern nicht verständlich)
  planeNormal := Point3D(AB.Y*AC.Z - AB.Z*AC.Y, AB.Z*AC.X - AB.X*AC.Z, AB.X*AC.Y - AB.Y*AC.X);
  d := planeA.X*planeNormal.X + planeA.Y*planeNormal.Y + planeA.Z*planeNormal.Z;
  // 2a
  DE := Point3D(lineB.X - lineA.X, lineB.Y - lineA.Y, lineB.Z - lineA.Z);
  // 3
  divisor := planeNormal.X*DE.X + planeNormal.Y*DE.Y + planeNormal.Z*DE.Z;
  if divisor = 0 then
    // die Gerade steht 90° zur Ebenennormale --> sie ist parallel
    // Lösung: keine oder unendlich viele - wir liefern niks
    Result := Point3D(0, 0, 0)
  else
  begin
    t := (d - planeNormal.X*lineA.X - planeNormal.Y*lineA.Y - planeNormal.Z*lineA.Z) / divisor;
    // 4
    Result := Point3D(lineA.X + t*DE.X, lineA.Y + t*DE.Y, lineA.Z + t*DE.Z);
  end;
end;

Diese funktioniert einwandfrei, jedoch gibt es mir auch Werte aus wenn kein Schnittpunkt dazwischen liegt.
z.B. das:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  LPoint : TPoint3D;
begin
  LPoint := intersectPlaneLine(
    Point3d(100,100,100),
    Point3d(200,200,100),
    Point3d(200,100,100),
    Point3d(0,0,-1000),
    Point3d(0,0,1000)
  )
end;

bekomme ich Point3D(0,0,100) zurück obwohl da gar nichts liegen sollte? Komisch ist das die Z Achse korrekt ist. Wo ist da der Wurm drin?

MfG

[JasonDX]

Die Funktion berechnet den Schnittpunkt zwischen einer unendlichen Geraden und einer unendlichen Ebene, nicht den einer Strecke und eines begrenzten Dreiecks im Raum. Das Ergebnis ist damit korrekt. Die 2 bzw 3 Punkte dienen zur eindeutigen Beschreibung der Geraden bzw Ebene, nicht zu ihrer Begrenzung. Wenn du eine Bereichsprüfung brauchst, muss diese separat implementiert werden.

(Wobei man zur Funktion anmerken sollte, dass das Ergebnis (0,0,0) für den Fall keines Schnittpunktes alles andere als ideal ist).

[Medium]

Das Ergebnis ist doch korrekt. Die Ebene, die du durch deine 3 Punkte beschreibst liegt plan in der Z-Ebene, und dein Vektor geht durch die Z-Ebene - sogar senkrecht. Alles richtig.

Es gibt nur kein Ergebnis, wenn Ebene und Vektor parallel zueinander sind. Zum Beispiel:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  LPoint : TPoint3D;
begin
  LPoint := intersectPlaneLine(
    Point3d(100,100,100),
    Point3d(200,200,100),
    Point3d(200,100,100),
    Point3d(0,0,0),
    Point3d(1,0,0)
  )
end;

[milos]

Zitat von JasonDX:

Die Funktion berechnet den Schnittpunkt zwischen einer unendlichen Geraden und einer unendlichen Ebene, nicht den einer Strecke und eines begrenzten Dreiecks im Raum. Das Ergebnis ist damit korrekt. Die 2 bzw 3 Punkte dienen zur eindeutigen Beschreibung der Geraden bzw Ebene, nicht zu ihrer Begrenzung. Wenn du eine Bereichsprüfung brauchst, muss diese separat implementiert werden.

Oh nein, ich dachte mit der Funktion hätte ich es endlich geschafft
Kannst du mir einen Hinweis geben wie ich mehr infos bekomme so eine Bereichsprüfung zu implementieren?

Zitat:

(Wobei man zur Funktion anmerken sollte, dass das Ergebnis (0,0,0) für den Fall keines Schnittpunktes alles andere als ideal ist).

Weiss ich, habe ich schon durch (infinite,infinite,infinite) ersetzt, wollte nur den richtigen Code rein schreiben ^^

Freundliche Grüsse

[Medium]

Du könntest die baryzentrischen Koordinaten des Schnittpunktes in Relation zu deinem Dreieck errechnen. Wenn die alle im Bereich [0..1] liegen, ist der Punkt zumindest schon mal im Dreieck. Ist die Gerade auch begrenzt?

[JasonDX]

Zitat von milos:

Oh nein, ich dachte mit der Funktion hätte ich es endlich geschafft
Kannst du mir einen Hinweis geben wie ich mehr infos bekomme so eine Bereichsprüfung zu implementieren?

Da du im Endeffekt bloß prüfen willst, ob ein Punkt auf einer Fläche liegt, kannst du auf 2D-Varianten zurückgreifen. Da hängts davon ab, was für Bereiche du prüfen willst (Dreieck? Polygon? Konvex oder konkav?). Für alles davon sollten sich unterschiedlich komplexe Algorithmen und Implementierungen dazu finden lassen, u.a. auch hier in der DP.

Um dann deine 3D-Bereichsprüfung zu machen, kannst du einfach einen Koordinaten-Parameter weglassen und damit deinen Raum auf bspw. die (x,y)-Ebene projizieren. Das funktioniert in nahezu allen Fällen, mit Ausnahme wenn die Ebene ortogonal dazu ist (also senkrecht dazu steht). In dem Fall müssen wir auf eine andere Ebene projizieren. In Pseudocode könnte das bspw. so aussehen:

Code:

// Edit: Die Bedingungen auf welche Ebene projiziert werden soll sind hier falsch. Richtig waere, die Normale der Schnitt-Ebene zu nehmen, um die Ebene zu vermeiden, die parallel zur Normalen ist. Diese Normale wird oben bereits in planeNormal berechnet.
is3DPointInTriangle((x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (px, py, pz))
  if (x1 = x2)
    return is2DPointInTriangle((y1, z1), (y2, z2), (y3, z3), (py, pz))
  else if (y1 = y2)
    return is2DPointInTriangle((x1, z1), (x2, z2), (x3, z3), (px, pz))
  else
    return is2DPointInTriangle((x1, y1), (x2, y2), (x3, y3), (px, py))

Für Bereichsprüfungen mit Polygonen bleibt das Prinzip das selbe. Sollte die Gerade auch begrenzt sein, kann das selbe Prinzip angewandt werden.

[milos]

Danke habe es hinbekommen

Angefügt ist das 1. Bild welches von meinem RayTracer korrekt dargestellt wurde, ist sowas wie eine Sensation
Und als "lustiges zwischendurch", ein Bild welches durch einen Fehler ziemlich bunt und falsch rausgekommen ist, aber ich mags xD

Danke viel mal!
Freundliche Grüsse