#1 02.06.2007 15:32:05

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Triangle <-> Triangle Intersection

Hallo,

hat jemand zufällig einen Triangle Triangle Intersection Algo rumliegen?!
Wäre Praktisch... wink

mein Ansatz wäre:
Das eine 3Eck in eine Plane umwandeln, dann die Ebene gegen alle Linien (3 Stück) des anderen 3Ecks testen. Wenn ein Schnittpunkt vorhanden ist, muss man noch schaun ob dieser auf dem Dreieck liegt, und nicht auf der Ebene.

Andere Vorschläge?

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#2 02.06.2007 16:14:31

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Triangle <-> Triangle Intersection

Also ich würde http://www.delphidev.de/phpBB2/viewtopic.php?t=69 benutzen.
Teste jede Kante von Dreieck 1 mit Dreieck 2 und jede Kante von Dreieck 2 mit Dreieck 1. Du musst beides testen, eine Richtung reicht nicht.

Die Funktion kannst du dahingehend kürzen, das du t, u und v nicht benötigst.

Vielleicht gibt's auch noch was schöneres, mir fällt aber nichts ein.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#3 02.06.2007 16:31:15

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Triangle <-> Triangle Intersection

Zitat:


Teste jede Kante von Dreieck 1 mit Dreieck 2 und jede Kante von Dreieck 2 mit Dreieck 1. Du musst beides testen, eine Richtung reicht nicht.Coolcat

Wie soll das denn gehen?
Das bestimmt doch immernoch keine eindeutige kollision...
Soweit ich weiß

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#4 02.06.2007 16:48:20

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Triangle <-> Triangle Intersection

Also mir fällt keine Möglichkeit ein wie sich zwei Dreiecke schneiden können und dieser Test fehlschlägt?

Zitat:

Wie soll das denn gehen?

so:

Code: delphi

intersect := rayintersecttriangle(d1a, d1b-d1a, d2a, d2b, d2c, t, u, v);
if (intersect) begin result = true; return; end;
intersect := rayintersecttriangle(d1b, d1c-d1b, d2a, d2b, d2c, t, u, v);
if (intersect) begin result = true; return; end;
intersect := rayintersecttriangle(d1c, d1a-d1c, d2a, d2b, d2c, t, u, v);
if (intersect) begin result = true; return; end;
intersect := rayintersecttriangle(d2a, d2b-d2a, d1a, d1b, d1c, t, u, v);
if (intersect) begin result = true; return; end;
intersect := rayintersecttriangle(d2b, d2c-d2b, d1a, d1b, d1c, t, u, v);
if (intersect) begin result = true; return; end;
intersect := rayintersecttriangle(d2c, d2a-d2c, d1a, d1b, d1c, t, u, v);
if (intersect) begin result = true; return; end;
result = false;

My software never has bugs. It just develops random features.

Offline

 

#5 02.06.2007 17:07:49

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Triangle <-> Triangle Intersection

Denk dir beide Dreiecke komplanar, (kongruent), nebeneinanden, nicht überschneidend, um 180° verdeht und ein stück nach oben verschoben.

(muss ich dazu ein Bild malen???) EDIT: Bild gemalt

dann scheindet die 'Grundlinie' von Dreieck A das Dreieck B und umgekehrt, aber sie schneiden sich nicht...

Edit:

Jeder Delphiprogrammierer kriegt bei deinem Delphi/C gemisch einen kleinen Schreikrampf :mrgreen:

mfg Chris


Attachments:
Attachment Icon intersect.JPG, Größe: 13,918 bytes, Downloads: 530

Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#6 02.06.2007 17:51:39

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Triangle <-> Triangle Intersection

Ähm....aso.....ja hab vergessen t zu testen...

Code: delphi

rayintersecttriangle(d1a, d1b-d1a, d2a, d2b, d2c, t, u, v);
if (0<=t and t<=1) begin result := true; return; end;
rayintersecttriangle(d1b, d1c-d1b, d2a, d2b, d2c, t, u, v);
if (0<=t and t<=1) begin result := true; return; end;
rayintersecttriangle(d1c, d1a-d1c, d2a, d2b, d2c, t, u, v);
if (0<=t and t<=1) begin result := true; return; end;
rayintersecttriangle(d2a, d2b-d2a, d1a, d1b, d1c, t, u, v);
if (0<=t and t<=1) begin result := true; return; end;
rayintersecttriangle(d2b, d2c-d2b, d1a, d1b, d1c, t, u, v);
if (0<=t and t<=1) begin result := true; return; end;
rayintersecttriangle(d2c, d2a-d2c, d1a, d1b, d1c, t, u, v);
if (0<=t and t<=1) begin result := true; return; end;
result := false;



Zitat:

Jeder Delphiprogrammierer kriegt bei deinem Delphi/C gemisch einen kleinen Schreikrampf Mr.Green

Ich proge seit Wochen nur noch an einem https://jabber.rwth-aachen.de/wiki/index.php/Helga der Uni rum....in Java...sry


My software never has bugs. It just develops random features.

Offline

 

#7 03.06.2007 09:47:21

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Triangle <-> Triangle Intersection

Zur Erklärung vielleicht noch:
RayIntersectTriangle(P, R, A, B, C, t, u, v);

Dann liegt der Schnittpunkt S der Geraden  P + t * R mit dem Dreieck ABC, wenn es ihn gibt bei:
S := P + t * R;

Und da ich das "wenn es ihn gibt" vergessen habe muss man entweder t vorher z.B. auf -1 setzen, oder jedesmal das Ergebnis der Funktion abfragen.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#8 04.06.2007 10:23:26

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Triangle <-> Triangle Intersection

Man könnte auch schauen, ob ein Eckpunkt eines Dreieckes innerhalb des anderen Dreieckes liegt.
Das für jeden Eckpunkt und die entgegengesetzte Richtung.

Ob ein Punkt in einem Dreieck liegt, bekommt man glaub ich mit dem Kreuzprodukt raus, wo man schaut ob der Punkt immer auf derselben Seite (links oder rechts) der einzelnen drei Seiten liegt.

Der Spezialfall, wo ein kleines Dreieck vollständig in einem größeren liegt, ist damit aber nicht erfaßt.

DerPeer

P.S.: Dreiecke sind ja Gott sei Dank konvex smile

Edit: Hm. Noch ein Spezialfall wird nicht erfaßt: Wenn wir ein Dreieck nehmen (gleichseitig), und es kopieren und die Kopie um 180° drehen und die Position unverändertlassen (sechszackiger Stern) - dann gehts auch schief.

Edit2: Je mehr ich darüber nachdenke, desto unzuverlässiger wird die Idee...

Offline

 

#9 04.06.2007 19:14:12

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Triangle <-> Triangle Intersection

Ähm....*hust....reden wir eigentlich von 2D oder 3D?

Mein "Algo" ist für 3D ausgelegt...


My software never has bugs. It just develops random features.

Offline

 

#10 04.06.2007 20:31:38

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Triangle <-> Triangle Intersection

Hoppala! Okay, da hörts dann natürlich auf...

DerPeer

Offline

 

#11 05.06.2007 02:11:17

BeRo
Newbie
Registriert: 01.06.2007
Beiträge: 2

Re: Triangle <-> Triangle Intersection

Vielleicht würde dich das hier interessieren: http://bero.0ok.de/downloads/TriTriCollision.pas  big_smile

Offline

 

#12 05.06.2007 10:54:07

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Triangle <-> Triangle Intersection

@BeRo: Also mal angenommen mein Vorschlag funktioniert, ist das nicht 'etwas' übertrieben aufwendig?

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#13 05.06.2007 15:36:26

BeRo
Newbie
Registriert: 01.06.2007
Beiträge: 2

Re: Triangle <-> Triangle Intersection

Das ist halt die alte. nun ausgestortierte, Tri2Tri Kollisionroutine von meiner Rigidbody&Ragdoll Physikengine, wo ich halt so genaue Kollisionkontaktpunkttinformationen  (was für ein langes Wort lol ) brauche.  wink

Für die Physikengine habe ich aber jetzt eine schnellere und zuverlässigere Tri2Tri Kollisionroutine implementiert, die unter anderem vieles cacht, z.B. die transformierten Triangledaten etc, so dass die nicht bei jeder Objekt vs. Objekt Kollision ständig neu berechnen werden müssen. Und die neue arbeitet jetzt zudem auch mit einem Kollision AABB Tree (pro Objekt auf Trianglebasis). die das ganze auch nun extrem beschleunigt.

Wenn meine Physikengine dann soweit einsatz bereit ist, kann ich die hier auch gerne mal posten.  big_smile

BeRo

Offline

 

#14 05.06.2007 21:18:14

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Triangle <-> Triangle Intersection

So,

ich habe auch nach einer Lösung geforstet und habe schließlich mit Hilfe dieses Papers: http://www.cs.lth.se/home/Tomas_Akenine_Moller/pubs/tritri.pdf
einen relativ schnellen (aber noch nicht Optimierten Algo geschrieben)

Code: delphi

procedure intersect(vv0,vv1,vv2,d0,d1,d2 : double; var isect0,isect1 : double);
begin
  isect0:=vv0+(vv1-vv0)*d0/(d0-d1);
  isect1:=vv0+(vv2-vv0)*d0/(d0-d2);
end;

procedure computeintervals(vv0,vv1,vv2,d0,d1,d2,d0d1,d0d2: double; var isect0,isect1 : double);
begin
  if(d0d1>0)then
    // here we know that D0D2<=0.0
    // that is D0, D1 are on the same side, D2 on the other or on the plane
    intersect(vv2,vv0,vv1,d2,d0,d1,isect0,isect1)
  else
    if(d0d2>0)then//here we know that d0d1<=0.0
      intersect(vv1,vv0,vv2,d1,d0,d2,isect0,isect1)
    else
      if(d1*d2>0)or(d0 <> 0)then // here we know that d0d1<=0.0 or that D0!=0.0
        intersect(vv0,vv1,vv2,d0,d1,d2,isect0,isect1)
      else
        if(d1<>0)then
          intersect(vv1,vv0,vv2,d1,d0,d2,isect0,isect1)
        else
          if(d2<>0)then
            intersect(vv2,vv0,vv1,d2,d0,d1,isect0,isect1)
          else // triangles are coplanar
            exit;
end;

//sorts that a <= b
procedure sortdouble( var a,b : double );
var
  c : double;
begin
  if a > b then
  begin
    c := b;
    b := a;
    a := c;
  end;
end;

function triangleintersecttriangle( a0,a1,a2, b0,b1,b2 : td3dxvector3 ) : boolean;
const
  epsilon = 0.00001;
var
  vnorm1, vnorm2,
  vtmp1,vtmp2,
  vdir : td3dxvector3;
  d1,d2,
  da0,da1,da2,
  db0,db1,db2,
  max,b,c,
  pa0,pa1,pa2,
  pb0,pb1,pb2 : double;
  index : integer;
  da0da1,da0da2,
  db0db1,db0db2,
  isecta0,isecta1,
  isectb0,isectb1 : double;
begin
  d3dxvec3subtract(vtmp1, b1,b0);
  d3dxvec3subtract(vtmp2, b2,b0);
  d3dxvec3cross(vnorm2, vtmp1, vtmp2);
  d2  := -d3dxvec3dot(vnorm2, b0);
  da0 :=  d3dxvec3dot(vnorm2, a0) + d2;
  da1 :=  d3dxvec3dot(vnorm2, a1) + d2;
  da2 :=  d3dxvec3dot(vnorm2, a2) + d2;
  if(abs(da0)<epsilon)then da0:=0.0;
  if(abs(da1)<epsilon)then da1:=0.0;
  if(abs(da2)<epsilon)then da2:=0.0;
  da0da1 := da0*da1;
  da0da2 := da0*da2;
  if(da0da1>0)and(da0da2>0)then
  begin
    //All Ponit of Triangle A are on one Side of Triangle B
    result := false;
    exit;
  end;

  d3dxvec3subtract(vtmp1, a1,a0);
  d3dxvec3subtract(vtmp2, a2,a0);
  d3dxvec3cross(vnorm1, vtmp1, vtmp2);
  d1  := -d3dxvec3dot(vnorm1, a0);
  db0 :=  d3dxvec3dot(vnorm1, b0) + d1;
  db1 :=  d3dxvec3dot(vnorm1, b1) + d1;
  db2 :=  d3dxvec3dot(vnorm1, b2) + d1;
  if(abs(db0)<epsilon)then db0:=0.0;
  if(abs(db1)<epsilon)then db1:=0.0;
  if(abs(db2)<epsilon)then db2:=0.0;
  db0db1 := db0*db1;
  db0db2 := db0*db2;
  if(db0db1>0)and(db0db2>0)then
  begin
    //All Ponit of Triangle B are on one Side of Triangle A
    result := false;
    exit;
  end;

  d3dxvec3cross(vdir, vnorm2, vnorm1);

  // compute and index to the largest component of D
  max  := abs(vdir.x);
  index:=0;
  b    := abs(vdir.y);
  c    := abs(vdir.z);
  if(b>max)then
  begin
    max  :=b;
    index:=1;
  end;
  if(c>max)then
  begin
    max  := c;
    index:=2;
  end;
  // this is the simplified projection onto L
  if index = 0 then
  begin
    pa0 := a0.x;
    pa1 := a1.x;
    pa2 := a2.x;
    pb0 := b0.x;
    pb1 := b1.x;
    pb2 := b2.x;
  end;
  if index = 1 then
  begin
    pa0 := a0.y;
    pa1 := a1.y;
    pa2 := a2.y;
    pb0 := b0.y;
    pb1 := b1.y;
    pb2 := b2.y;
  end;
  if index = 2 then
  begin
    pa0 := a0.z;
    pa1 := a1.z;
    pa2 := a2.z;
    pb0 := b0.z;
    pb1 := b1.z;
    pb2 := b2.z;
  end;

  // compute interval for triangle 1
  computeintervals(pa0,pa1,pa2,da0,da1,da2,da0da1,da0da2,isecta0,isecta1);

  // compute interval for triangle 2
  computeintervals(pb0,pb1,pb2,db0,db1,db2,db0db1,db0db2,isectb0,isectb1);

  sortdouble(isecta0,isecta1);
  sortdouble(isectb0,isectb1);

  if (isecta1<isectb0)or(isectb1<isecta0) then
  begin
    result := false;
    exit;
  end;

  result := true;
end;



Vielen Dank für eure Hilfe,
ich werds jedenfalls so machen...

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson