# Ellipsoid - Triangle (yet another)

This topic is 5453 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello. I have a problem trying to implement the collision detection algorithm mentioned in "Generic collision detection for games using ellipsoids." I am in the part of Ray/Triangle_Faces. I am using the following algorithm (Möller, Trumbore) :
// S: ray origin
// T: ray end point
// v0,v1,v2  : triangle vertices
// return : time intersection

public static float intersect(Vector3f s, Vector3f t,
Vector3f v0,Vector3f v1, Vector3f v2){
d1 = v1 - v0;
d2 = v2 - v0;

n = d1 x d2 ;
n.normalize();

r = T - S;

float delta = -r * n;

if(delta > EPSILON ){
b = S - v0;
float lambda = b * n / delta;

if(lambda <= 1f  && lambda >= 0 ){
u  = b x r ;
float u1 = ( d2 * u ) / delta;
float u2 = ( -d1 * u ) / delta;
if( (u1 + u2)<= 1f && u1 >= 0f && u2 >= 0f ){
return lambda;
}
return INFINITY;
}
return INFINITY;
}
return INFINITY;
}


When the time is not infinite, I calculate the new position like: new_position = tIntersecction * (T-S) and the "slide position" SP like: SP = T - (T - new_position ) * 1.005 * NORMAL]*NORMAL then I make the recursion: collisionRecursion(new_position,SP,++numIterations); But sometimes this doesn't work. !! .In situations like: www.mycgiserver.com/~luisopazo/desinflado.gif When I move the ellipsoid forward, the triangle "A" is not detected. I have observed that in these situations, the value (lambda = b * n / delta) is negative and very small (with the triangle "A"), but I believe that this should be positive. I believe that something like this happens in the "unit sphere space": www.mycgiserver.com/~luisopazo/inflado.gif I TRIED BY CHANGING THIS: if(lambda <= 1f && lambda >= -EPSILON ) BUT IT DID NOT WORK EITHER Could somebody give me some advice? Thanks. [Edited by - luzop on October 14, 2004 9:26:33 AM]

##### Share on other sites
I'm running so can't look at the code now, but I just thought I'd let you know that the images are the infamous 'red x's'. Maybe just on my computer though...

##### Share on other sites
mmm .... The last time this worked (HTML <IMG> tag)

##### Share on other sites
I've got working code for what you're talking about up and running. I don't have time now, but if nobody's answered your question by this evening I'll look at your code and see if I can figure out the problem - unless of course you've solved it by then :-)

##### Share on other sites
OK . thanks.

I think the problem is in the code of 'simple physic' simulation. ( acceleration , decceleration)

I use euler formula twice,

  A = (F - V*Friction ) * 1/mass;  V += A*dt;  F = ZERO_VECTOR;  f(V.length() <0.0001f){  	V = ZERO_VECTOR;  }  else{  	POSITION += V*dt;   }

but I do not apply an impulse at the moment of collision, just I reposition the swept esfere/ellipsoid.

I do this:(My code is a real MESS. So I present just the pseudo code.)

  public void update(float f) {    applyForce(gravity);    tempPosition = currentPosition;    super.update(f);  // Euler, Euler    futurePosition = currentPosition;    collisionDetection(tempPosition , futurePosition, 0);		super.setPosicion(tempPosition);}collisionDetection(Vector3f P1, Vector3f P2, int iteration){        if(iteration >= MAX_ITERACIONES){            return;        }        delta = P2 - P1;        float length = delta.length();        if(length < 1E-6f){            return;        }		        AABB_temp.empty();        AABB_temp.add(P1.x + radioZX + 1, P1.y + radioY + 1, P1.z + radioZX + 1);        AABB_temp.add(P1.x - radioZX - 1, P1.y - radioY - 1 , P1.z - radioZX  - 1);        AABB_temp.add(P2.x + radioZX + 1, P2.y + radioY  + 1, P2.z + radioZX  + 1);        AABB_temp.add(P2.x - radioZX - 1, P2.y - radioY  - 1, P2.z - radioZX  - 1);        List list = getCandidateLeafs(AABBTree.root,AABB_temp);        if(list.size()==0){            P1 = P2;            return;        }        transform(P1);   // P1.x /= radioZX  ;  P1.Y /= radioY    ; P1.z /= radioZX        transform(P2);   // P2.x /= radioZX  ;  P2.Y /= radioY    ; P2.z /= radioZX        float tInterTemp = Float.MAX_VALUE;			        checkInterseccions:{			// First, all triangle faces            tInterTemp = minFaceIntersection(P1,P2,list);            if(tInterTemp < Float.MAX_VALUE){                break checkInterseccions;            }						// if not, all edges			tInterTemp = minEdgeIntersection(P1,P2,list);            if(tInterTemp < Float.MAX_VALUE){                break checkInterseccions;            }			// if not, all vertices			tInterTemp = minVertexIntersection(P1,P2,list);            if(tInterTemp < Float.MAX_VALUE){                break checkInterseccions;            }            else{				// no intersection                P1 = P2;                unTransform(P1); // P1.x *= radioZX  ;  P1.Y *= radioY    ; P1.z *= radioZX                return;            }        }		Vector3f Q = new Vector3f();		Q = P2 - P1;        Q *= tInterTemp;        P1 = Q;        		Vector3f SP = new Vector3f();				SP = P2 - [ (P2 - P1 ) * 1.005 * NORMAL] * NORMAL        unTransform(P1);        unTransform(SP);        collisionDetection(P1,SP,++iteracion);}float minFaceIntersection(Vector3f P1,Vector3f P2,List list){        float tMin = Float.MAX_VALUE;        float tInter = Float.MAX_VALUE;        AABBNodeScene aabbNodeScene;        Face face;        Mesh mesh;				final Vector3f g_v1 = new Vector3f();	    final Vector3f g_v2 = new Vector3f();	    final Vector3f g_v3 = new Vector3f();            // for each node        for (int i = 0; i < list.size(); i++) {            aabbNodeScene = (AABBNodeScene) list.get(i);            // for each triangle in the current node            for(int j=0 ; j< aabbNodeScene.getNumFaces();j++){                mesh = aabbTree.getScene().getMeshes()[aabbNodeScene.getIndexMesh(j)];                face = mesh.getFaces()[aabbNodeScene.getIndexFace(j)];				g_v1 = (mesh.getVertices()[face.p0]);                g_v2 = (mesh.getVertices()[face.p1]);                g_v3 = (mesh.getVertices()[face.p2]);                transform(g_v1);                transform(g_v2);                transform(g_v3);                d1 = g_v2 - g_v1;				d2 = g_v3 - g_v1;                NORMAL = d1 x d2;                NORMAL.normalize();									P1 -= NORMAL;		// offset the ray a distance radius = 1 in the -NORMAL direction				P2 -= NORMAL;                if(RayIntersect.intersect(P1,P2, g_v1,g_v2,g_v3, tInter)){                    if(tInter < tMin){                        tMin = tInter;                    }                }            }        }        return tMin;    }

##### Share on other sites
This kind of stuff is very hard to debug. I haven't looked at your code, but I will make a couple of suggestions. Kasper Fauerby's paper 'Improved Collision Detection and Response' fixes some of the problems in the article you're using. The article includes code - I've tried it and it does work very well. You might look into it.

The Fauerby article doesn't deal with a few cases, like getting stuck or shaking in corners. But it's a good foundation.

##### Share on other sites
Quote:
 This kind of stuff is very hard to debug.

... definitively yes (at least for me ) :)

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 22
• 17
• 46