DGL • Thema anzeigen - Ray Triangle intersect

Ray Triangle intersect

Moderator: DGL-Team

Seite 1 von 1

[ 6 Beiträge ]

Vorheriges Thema | Nächstes Thema

Autor

Nachricht

Wölfchen

Betreff des Beitrags: Ray Triangle intersect

Verfasst: Di Dez 04, 2012 20:54

DGL Member

Registriert: Do Mär 05, 2009 20:17
Beiträge: 284
Wohnort: Kaiserslautern

Hallo,

ich suche eine schnelle Methode um einen Schnittpunkt zwischen einem Strahl und einem Dreieck zu generieren.
Leider finde ich nur Algorythmen in C und bekomme es nicht übersetzt... http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf hat jemand zufällig was in delphi?

Danke schonmal!

W.

Nach oben

Ida

Betreff des Beitrags: Re: Ray Triangle intersect

Verfasst: Di Dez 04, 2012 21:14

DGL Member

Registriert: Mi Apr 13, 2011 22:05
Beiträge: 218
Programmiersprache: Lazarus/FPC

Ich hätt eine alte Funktion die dir die Entfernung zum Schnittpunkt ausgibt fals das was hilft.
Daraus sollten sich der Schnittpunkt eigentlich berechnen lassen müssen.

Die 3 Eckpunkte vom Dreieck (vertex1 2 und 3), die Startposition vom Strahl(raypos) und dessen Richtungsvektor(raydir) übergibst du als TGLVectord3-Variablen (nichts weiter als ein Array [0..3] mit floats)

Code:

 
function SchnitpunktDistanz(raydir, raypos, vertex1, vertex2, vertex3: TGLVectord3): real;
var
  edge1, edge2, distanceCrossEdge1, directionCrossEdge2,
    distanceVector: TGLVectord3;
  distance, determinant, inverseDeterminant, triangleU, triangleV: real;
begin
  edge1[0] := vertex2[0] - vertex1[0];
  edge1[1] := vertex2[1] - vertex1[1];
  edge1[2] := vertex2[2] - vertex1[2];
  edge2[0] := vertex3[0] - vertex1[0];
  edge2[1] := vertex3[1] - vertex1[1];
  edge2[2] := vertex3[2] - vertex1[2];
  directionCrossEdge2[0] := raydir[1] * edge2[2] - raydir[2] * edge2[1];
  directionCrossEdge2[1] := raydir[2] * edge2[0] - raydir[0] * edge2[2];
  directionCrossEdge2[2] := raydir[0] * edge2[1] - raydir[1] * edge2[0];
  determinant := edge1[0] * directionCrossEdge2[0] + edge1[1]
    * directionCrossEdge2[1] + edge1[2] * directionCrossEdge2[2];
  inverseDeterminant := 1 / determinant;
  distanceVector[0] := raypos[0] - vertex1[0];
  distanceVector[1] := raypos[1] - vertex1[1];
  distanceVector[2] := raypos[2] - vertex1[2];
  triangleU := (distanceVector[0] * directionCrossEdge2[0] + distanceVector[1]
      * directionCrossEdge2[1] + distanceVector[2] * directionCrossEdge2[2])
    * inverseDeterminant;
  if (triangleU < 0) or (triangleU > 1) then
  begin
    result := 0;
    exit;
  end;
  distanceCrossEdge1[0] := distanceVector[1] * edge1[2] - distanceVector[2]
    * edge1[1];
  distanceCrossEdge1[1] := distanceVector[2] * edge1[0] - distanceVector[0]
    * edge1[2];
  distanceCrossEdge1[2] := distanceVector[0] * edge1[1] - distanceVector[1]
    * edge1[0];
  triangleV := (raydir[0] * distanceCrossEdge1[0] + raydir[1]
      * distanceCrossEdge1[1] + raydir[2] * distanceCrossEdge1[2])
    * inverseDeterminant;
  if (triangleV < 0) or (triangleV > 1) then
  begin
    result := 0;
    exit;
  end;
  distance := (edge2[0] * distanceCrossEdge1[0] + edge2[1] * distanceCrossEdge1
      [1] + edge2[2] * distanceCrossEdge1[2]) * inverseDeterminant;
 
  if distance < 0 then
  begin
    result := 0;
    exit;
  end;
  result := distance;
end;
 

_________________
Ich teile manchmal heimlich durch Null. - Alber Einstein

Nach oben

Wölfchen

Betreff des Beitrags: Re: Ray Triangle intersect

Verfasst: Di Dez 04, 2012 22:28

DGL Member

Registriert: Do Mär 05, 2009 20:17
Beiträge: 284
Wohnort: Kaiserslautern

Wow Spitze! vielen Dank! Das ist ja sogar schon mit Distanzberechnung super!

2 Fragen:
a) Lässt sich das noch performanter machen? ich habs in ner Schleife getestet und 900.000.000 Prüfungen brauchen bei mir ca. 84 sekunden
b) ist es ok

Code:

  if (triangleU < 0) or (triangleU > 1) then
  begin
    result := -1;
    exit;
  end;

zu schreiben um fälle bei denen der strahl vorbeigeht besser von welchen zu unterscheiden, bei denen der strahl auf dem dreieck startet?

Nach oben

Ida

Betreff des Beitrags: Re: Ray Triangle intersect

Verfasst: Mi Dez 05, 2012 06:58

DGL Member

Registriert: Mi Apr 13, 2011 22:05
Beiträge: 218
Programmiersprache: Lazarus/FPC

900.000.000 Dreiecksprüfungen?
Bild

Hey mal ehrlich, was ist das denn für ein Programm das 900 Millionen Dreiecksprüfungen hat^^
Nur mal überschlagen...3 Ecken...zu je 3 Koordinaten, warscheinlich Float-Werte, also 8byte x 3 X 3 = 72 Byte /Dreieck
Das wären dann 64800000000 bytes, was ungefähr 61,8GB an Daten entspricht!!!!
Ok, warscheinlich hast du da was ganz anderes als ich mir grad vorstelle^^

Und performater...kommt drauf an WIE performant du das haben willst. Wenn du das in Echtzeit berechnen lassen willst, also im Bruchteil einer Sekunde musst du glaub ich auf die Quantencomputer warten.

Ansonsten vielleicht:
- Alle Kerne der CPU komplett auslasten, MultiThreading, ist aber saublöd zu coden.(meiner Erfahrung nach)
- Das ganze in OpenCL packen und von der Grafikkarte berechnen lassen.
- Oder das beste: Eine eigene Ray-Triangle-Colission schreibe/suchen die vielleicht wirklich performanter ist. Es kommt halt drauf an für was genau du sie brauchst. =D

Und: das mit -1 bei der Ausgabe ist ganz dir überlassen =D
An dem Code kannst du rumpfuschen was du willst, ich hab den mal im Internet gefunden und von C++ nach Delphi übersetzt.

lg Ida

_________________
Ich teile manchmal heimlich durch Null. - Alber Einstein

Nach oben

Wölfchen

Betreff des Beitrags: Re: Ray Triangle intersect

Verfasst: Mi Dez 05, 2012 09:06

DGL Member

Registriert: Do Mär 05, 2009 20:17
Beiträge: 284
Wohnort: Kaiserslautern

lach

nee ich hab nicht 900.000.000 dreiecke

ich hab aber 90.000 strahlen und eine million dreiecke

das ganze muß nicht in echtzeit laufen, nur ein einziges mal.
ich werde versuchen was auszuknobeln um nicht jedes dreieck mit jedem strahl prüfen zu müssen, vielleicht lässt sich so die zeit reduzieren...

vielen dank nochmal

Nach oben

Coolcat

Betreff des Beitrags: Re: Ray Triangle intersect

Verfasst: Mi Dez 05, 2012 18:39

DGL Member

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

Zitat:

ich werde versuchen was auszuknobeln um nicht jedes dreieck mit jedem strahl prüfen zu müssen, vielleicht lässt sich so die zeit reduzieren...

Da solltest du zuerst optimieren, da liegt nämlich das wirkliche Bottleneck. Übliche Lösung wäre eine Baumstruktur, z.B. ein Octtree oder ein R-Tree.

_________________
Yeah! :mrgreen:

Nach oben

Seite 1 von 1

[ 6 Beiträge ]

Foren-Übersicht » Programmierung » Einsteiger-Fragen

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 58 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.