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