Line Triangle intersection

[Empire Phoenix]

Hi leute, was ich scuhe ist eine schnelle Methode um einen Ray auf ein Trimesh loszulassen.

Was ich bereits habe in einer while schleife: die 3 punkte, normal und center. (die länge bis wo mich eine intersection interessiert)
Ebenfalls primitve rechen algorithmen wie sie google nennt.

Nur ich kann mir nicht vorstellen das man das nicht irgetwie optmieren kann indem ich komplette triangles aus der berechnung rauschmeißen kann mit relativ simplen verfahren, allerdings fällt mir dazu ncihts genaues ein, und wollte mal fragen ob irgetwer hier damit erfahrung hat?

 

[spyboot]

Wie wärs mit Line/Line Intersection?

//Sucht den Scnittpunkt der Linien (ap1x/ap1y)->(ep1x/ep1y) und (ap2x/ap2y)->(ep2x/ep2y). Gibt null zurück wenn kein Schnittpunkt existiert 
	public static Point SchnittPunkt(double ap1x,double ap1y, double ep1x, double ep1y,double ap2x,double ap2y, double ep2x, double ep2y){
	
		double m1 = (ep1x-ap1x)/(ep1y-ap1y);
		double m2 = (ep2x-ap2x)/(ep2y-ap2y);
	
		if(m1==m2)return null;
		
		double t1 = -(m1*ap1y-ap1x);
	
		double t2 = -(m2*ap2y-ap2x);
		double xs = (t2-t1)/(m1-m2);
	
		Range xRange1 = new Range(ap1y,ep1y);
		Range xRange2 = new Range(ap2y,ep2y);
		if (xs < xRange1.min() ||  xs < xRange2.min() || xs > xRange1.max() || xs > xRange2.max)return null;
	
		double ys = m1 * xs + t1;
	
		return new tools.Point(xs, ys);
		
	}

Point-Klasse:

public class Point {

	public float x=0;
	public float y=0;
	
	
	public Point(float x2, float y2) {
		
		x=x2;
		y=y2;
		
	}
	
	public Point() {
	}
	
	public double distance(Point p2) {
		return distance(p2.x,p2.y);
	}
	
	
	public double distance(float x2, float y2) {
		return distance(x,y,x2,y2);
	}
	
	protected static float distance1d(float x2, float y2) {
		float zw=x2-y2;
		if(zw<0)zw=-zw;
		return zw;
	} 
	
	
	public static double distance(float x, float y, float x2, float y2) {
		float xq=x2-x;
		float yq=y2-y;
		xq=xq*xq;
		yq=yq*yq;
		
		return Math.sqrt(xq+yq);
	}

	public float getX() {
		return x;
	}

	public float getY() {
		return y;
	}
	
	public  String toString(){
		
		return x+"x"+y;
		
	}


}

Range-Klasse:

public class Range { //Ein Wertebereich
	
	float min=0;
	float max=0;
	boolean unsettet=true;
	
	public Range(float r1, float r2) {
	
		unsettet=false;
		
		if(r1>r2){
			
			max=r1;
			min=r2;
			
			return;
			
		}else{
			
			max=r2;
			min=r1;
			
			return;
			
		}
		
	
		
	}
	
	public Range() {
		
		return;
		
	}
	
	public void reset(){
		
		unsettet=true;
		return;
		
	}

	public void add(float p){
		
		if(unsettet){
			
			max=p;
			min=p;
			unsettet=false;
			
			return;
			
		}else{
			
			if(p>max)max=p;
			if(p<min)min=p;
			
			return;
			
		}
		
		
		
	}
	

	public float min() { //Kleinster wert
		return min;
	}

	public float max() { //Größter Wert
		return max;
	}
	
	

}

Hinweis: Wenn man die new's aus der Schnittpunktmethode entfernt verdoppelt sich die Performance (Ranges einfach static und nurnoch über reset() zurücksetzen).

Edit: ich hoffe ich habe deine Problemstellung jetzt richtig verstanden...
Wenn du nur prüfen willst ob ein Punkt in einem Dreieck liegt ist dass hier wohl am einfachsten:

(Ungetestet und hoffentlich selbsterklärend)

// Überprüft ob ein Punkt in einem Dreieck liegt
	 public static boolean PointInTriangle( Point p , Point p1 , Point p2 , Point p3 ) {

		 double n1=new Vector(p2.x-p1.x,p2.y-p1.y,0).cross(p.x-p1.x,p.y-p1.y,0).z;
		 double n2=new Vector(p3.x-p2.x,p3.y-p2.y,0).cross(p.x-p2.x,p.y-p2.y,0).z;
		 double n3=new Vector(p1.x-p3.x,p1.y-p3.y,0).cross(p.x-p3.x,p.y-p3.y,0).z;
		 
		 if(n1*n2 > 0.0 && n1*n3 > 0.0 && n2*n3 > 0.0){
			 return true;
		 }
		 
		 return false;
		 
	 }

 

[Empire Phoenix]

Ja nein, ich will genau genommen einen Ray auf ein Trimesh loslassen, nur das eigentliche problem das ich dabei habe möglichste effizient für jedes triangle rausfinden ob es getrofen wurde und wo., dann und will über distancechecks alles rauswerfen, bis ich entweder den hitpoint + das getroffene triangle habe, oder null returnt. also brache ich eigentlich die trefferposition im Koordiantensystem wo sich auch das Triangle befindet

Was macht vector.cross genau? bin da etwas eingerostet

 

[spyboot]

Vector.cross() liefert das Kreuzprodukt. Was dass genau ist sagt dir Wikipedia.
Dann müsste die Schnittpunktmethode eig. genau dass machen was du brauchst? Notfalls musst du nur 2 sachen aus der if-Bedingung entfernen und du hast ne Linie/Vektor(o. Gerade) intersection Methode.

if (xs < xRange1.min() ||  xs < xRange2.min() || xs > xRange1.max() || xs > xRange2.max)return null;

zu

if (xs < xRange1.min() || xs > xRange1.max())return null;

 

[Empire Phoenix]

Super ich hänge aber immer noch ein bischen, wahrscheinlich weil ich nicht verstehe wie du die berechnung machst vom Konzept her.

Welchen Sinn hat die Range classe?
Und wie bekomme ich aus den Schnittpunkten von Vectoren den schnittpunkt von einem Triangle mit einem Vector?

Sag mal das ist alles für 2d oder?

Weil ich brauche das ganze in einem 3draum... Hast du dazu evtl. auch eine Idee?

 

[spyboot]

Edit: ACHTUNG! Alles für den 2D-Raum!!

Is iwie noch lustiger wenn ich dir sage dass es Stoff der 8. Klasse Realschule ist... Egal wenn mann sich nicht direkt damit beschäftigt hatt kann mann dass nicht so einfach wissen:
Erstmal ist die Range klasse total egal und die punkt klasse auch:

Wir haben also 4 Punkte: 2 Punkte auf dem Vektor
pv1(10,0) und
pv2(10,10)

und die Punkte die die Linie begrenzen:

pl1(0,5) und
pl2(10,5)

zuerst rechnen wir beides in Vektoren um in denen y=1 ist dadurch muss mann nur x berechnen:

v1=(pv2.x-pv1.x)/(pv2.y-pv1.y)
v2=das gleiche halt nur mit pl1 und pl2

Gut jetzt haben wir Vektoren die ganz einfach die richtung der Linie und des Vektors angeben.

jetzt prüfen wir erst einmal ob beide parallel verlaufen weils sie sich dann auchnicht schneiden können:
if(v1==v2)//parallel

jetzt können wir uns daran machen den Schnittpunkt auszurechnen:

//BlaBla schnittpunkt von 2 Vektoren mit Vektor1(v1,1) und Vektor2(v2,1)

gut jetzt haben wir den Schnittpunkt.
da Vektoren aber unendlich lang sind und unsere Linie nicht, prüfen wir ob der Schnittpunkt auf der Linie ist. Der muss auf der Linie sein wenn die xKoordinate des Schnittpunktes zwischen den xKoordinaten des start- und endpunktes der Linie ist.

Edit: Achso und ja es ist für den 2d Raum: hmm :lol: verdammt... ???:L vl kann mann das einfach erweitern ???:L ... Und damit wär es auch nichtmehr 8. Klasse Realschule.....

 

[spyboot]

Hier scheint was zu stehen: Intersection of Rays/Segments with Triangles

Edit: und hier http://www.cs.cornell.edu/Courses/cs465/2003fa/homeworks/raytri.pdf
Edit: und dort http://www.ugrad.cs.ubc.ca/~cs314/Vsep2009/raytriangle.pdf

 

[Empire Phoenix]

Ah super das 2d verstehe ich schonmal, versuche gerade mich in das 3d reinzuarbeiten *kotz die variablen haben da echt tolle namen*

 

[Marco13]

Auf GeometricTools.com gibt es für "solche" Probleme meist gute Lösungen, im speziellen unter Geometric Tools: Intersection . Die sind zwar in C++, lassen sich aber leicht nach Java portieren.

Ging es nicht eigentlich darum, dass du 1000000 Dreiecke hast, und gerne schnell rausfinden würdest, dass mit 999999 davon gar kein Schnitt stattfinden kann (man also den rechenaufwändigen Test gar nicht machen muss)? Da müßte man wissen, ob das Dreiecksmesh "statisch" ist oder sich verändert. Man könnte da irgendwelche beschleunigenden Datenstrukturen aufbauen, je nachdem, welcher Fall vorliegt... irgendwas wie eine BVH (Bounding Volume Hierarchie) mit AABBs (Axis Aligned Bounding Boxes). Aber wenn das nur für sowas wie Picking gedacht ist, lohnt sich das wahrscheinlich gar nicht...

 

[Empire Phoenix]

Es handelt sich extra um relativ simple modelle , Allerdings verändern die sich evtl(wenn auch selten (Player hitzones)),
die Engine die ich verwende hat bereits bounding boxes, daher will ich die dazu benutzen den aufwand etwas zu verringern (wenn alle Ecken der Bounding box auf einer Seite des STart-Endpunktes sind, dann kann ich das Object da drinnen ja auch nicht treffen.
))

 

[Empire Phoenix]

Oh shit wie ich c++ doch hasse das stinkt... Jetzt muss ich mich dadurch quälen und hoffen das ich den sinn der Classen verstehe :/ Ganz vergessen wie herrlich unlesbaren code man damit programmieren kann

 

[Marco13]

Woha, musst du ja nicht. War nur der Hinweis: WENN man mal sowas braucht (auch speczielleres wie "Schnitt zwischen Kugel und Capsule" oder so...) dann findet man das da. Ray-Triangle gibt's 1000e, und vielleicht auch einfachere....

 

[Empire Phoenix]

Naja habs jetzt halbwegs hinbekommen, habe festgestellt das in den tiefen der Engine dazu einiges rumliegt für das offensichtlich nen brahbares interfae noch nicht ganz fertig ist, geht jetzt soweit ganz gut..

 

[Empire Phoenix]

Am rande weil es mir heute aufgefallen ist, JBullet hat eine portierte Version von GImpact drinne, wääre noch eine Idee wie man sowas halbwegs effizient berechnen kann.