DGL • Thema anzeigen - Punkt im Dreieck?

Punkt im Dreieck?

Moderator: DGL-Team

Seite 1 von 1

[ 5 Beiträge ]

Vorheriges Thema | Nächstes Thema

Autor

Nachricht

Andreas

Betreff des Beitrags: Punkt im Dreieck?

Verfasst: Sa Apr 11, 2009 18:56

DGL Member

Registriert: Sa Aug 09, 2008 09:07
Beiträge: 112

Hallo,

Ich versuche zur Zeit einen Raytracer zu programmieren. Mir hat sich dann folgendes Problem gestellt:
Wie finde ich heraus ob die Gerade das Dreieck schneidet?
Wie bekomme ich den Schnittpunkt?

Ich bin das Problem dann so angegangen:
1. Zuerst den Schnittpunkt der Gerade und der Dreiecksebene finden.
2. Dann prüfen ob sich der Punkt im Dreieck befindet.

-> 1. hab ich jetzt einmal so gelöst:

Gerade in Parameterform:

Code:

(x, y, z) = 0A + f * AB
 
(x, y, z) ... Ortsvektor der einen Punkt auf der Geraden beschreibt
0A ... Ortsvektor des Anfangspunktes der Geraden
f ... unbekannter Faktor
AB ... Vektor der die Richtung der Geraden angibt

Ebene in Normalvektorform:

Code:

n * 0E = n * (x, y, z)
 
n ... Normalvektor
0E ... Ortsvektor des "Anfangspunktes" der Ebene
(x, y, z) ... Ortsvektor der einen Punkt auf der Ebene beschreibt

Dann hab ich die 1. Gleichung einfach in die 2. eingesetzt.
Das Ergebnis ist:

Code:

 Zähler        n * OE - n * OA
---------- = -------------------- = f
 Nenner             n * AB
 
Nenner = 0                  : Schneidet sich im Unendlichen, kein Schnittpunkt
Nenner, Zähler = 0       : laut Newton ist 0/0 eine belibige Zahl, er hatte also Recht :) , Unendlichviele Schnittpunkte
 
f < 0     : Gerade und Ebene treffen sich "hinter" dem Punkt A, -> Der Strahl ist nur eine Halbgerade, Berechnung wird also
abgebrochen

-> 2. dafür hab ich jetzt zwei Ansätze:

1)
Ich verwende die Formel die mir Coolcat gezeigt hat:

Code:

(x, y, z) = OA + u * AB + v * AC
 
OA ... Ortsvektor auf den Punkt A
u ... unbekannter Faktor
AB ... Vektor zwischen dem Punkt A und B
v ... unbekannter Faktor
AC ... Vektor zwischen dem Punkt A und C
 
Wobei gilt:
u, v >= 0
u + v <= 1

Dann müsste ich nur noch den Schnittpunkt der Ebene und der Gerade einsetzten und das LGS lösen.
Leider muss ich da den Vektor zerlegen und das gefällt mir nicht so ganz...

2)
Ich rechne die Einheitsvektoren von AB und AC aus (ich bezeichne diese einmal mit a und b).
(x, y, z) bezeichne ich jetzt mit 0P.
Dann rechne ich den Vektor AP aus.

Und es ergibt sich folgendes:

Code:

u = (a * AP) / |AB|
v = (b * AP) / |AC|
 
u ... s.o.
|AB| ... Betrag von AB
v ... s.o.
|AC| ... Betrag von AC

Nur noch die Bedingungen prüfen (s.o.) und weiß schon ob der Punkt auf dem Dreieck liegt.

Stimmt das alles so?
Bzw. was denkt ihr wäre effizienter ( 1) oder 2) )?

Danke im Voraus!
Andreas

Nach oben

Coolcat

Betreff des Beitrags:

Verfasst: Sa Apr 11, 2009 22:18

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Mir fällt da gerade ein ich hatte mal ne Mathe-Unit geschrieben....die Unit stammt zwar aus meinen DirectX-Zeiten...aber das sollte ja nicht das Problem sein.
=> http://www.delphidev.de/forum/viewtopic.php?id=69

Code:

// =============================================================================
// RayIntersectTriangle
// =============================================================================
// Testet eine Gerade mit einem Dreieck
// Gibt exakte Koordinaten des Schnittpunktes zurück, diese müssen jedoch 
// umgewandelt werden:
// D3DXVec3BaryCentric( Schnittpunkt, v0, v1, v2, u, v );
// Das Funktioniert auch wenn man dort statt v0, v1 und v2 die Texturkoords der 
// entsprechenden Vertices übergibt.
// Will man einfach nur den Schnittpunkt, ginge auch 
// Schnittpunkt := Origin + t * Dir;
// (Funktion aus DirectX-SDK übersetzt in Delphi)
function RayIntersectTriangle(const Origin, Dir, v0, v1, v2: TD3DXVector3; 
                               var t, u, v: Single ): Boolean;
var edge1, edge2,
    pvec, qvec, tvec: TD3DXVector3;
    det, InvDet: single;
begin
  D3DXVec3Subtract( edge1, v1, v0 );
  D3DXVec3Subtract( edge2, v2, v0 );
 
  D3DXVec3Cross( pvec, Dir, edge2 );
 
  det := D3DXVec3Dot( edge1, pvec );
  if (det > 0) then begin
    D3DXVec3Subtract( tvec, Origin, v0 );
  end
  else begin
    D3DXVec3Subtract( tvec, v0, Origin );
    det := -det;
  end;
 
  if (det < 0.0001) then begin
    result := false;
    exit;
  end;
 
  u := D3DXVec3Dot( tvec, pvec );
  if ((u < 0) or (u > det)) then begin
    result := false;
    exit;
  end;
 
  D3DXVec3Cross( qvec, tvec, edge1 );
 
  v := D3DXVec3Dot( Dir, qvec );
  if ((v < 0) or ((u + v) > det)) then begin
    result := false;
    exit;
  end;
 
  t := D3DXVec3Dot( edge2, qvec );
  InvDet := 1 / det;
  t := t * InvDet;
  u := u * InvDet;
  v := v * InvDet;
 
  result := true;
end;

_________________
Yeah! :mrgreen:

Nach oben

Andreas

Betreff des Beitrags:

Verfasst: So Apr 12, 2009 17:28

DGL Member

Registriert: Sa Aug 09, 2008 09:07
Beiträge: 112

Danke. Nur kann ich leider kein Delphi^^

Ich mach mit den oben geposteten Formeln einmal ein paar Test, um zu sehen ob sie stimmen...

Nach oben

Pellaeon

Betreff des Beitrags:

Verfasst: Mo Apr 13, 2009 10:50

DGL Member

Registriert: Mo Apr 25, 2005 17:51
Beiträge: 464

Da benutz ich folgendes: http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf

Ist einer der effektivsten Algorithmen, was das angeht.

edit: wenn ich den Delphi-Code da überfliege, scheint das genau die Methode aus der pdf zu sein

_________________
__________
"C++ is the best language for garbage collection principally because it creates less garbage." Bjarne Stroustrup

Nach oben

Coolcat

Betreff des Beitrags:

Verfasst: Mo Apr 13, 2009 12:00

DGL Member

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java

Zitat:

Danke. Nur kann ich leider kein Delphi^^

Dann schau ins DirectX SDK, wie im Kommentar zu lesen ist kommt die Methode nämlich daher...

_________________
Yeah! :mrgreen:

Nach oben

Seite 1 von 1

[ 5 Beiträge ]

Foren-Übersicht » Programmierung » Mathematik-Forum

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 4 Gäste

Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.