Jump to content
  • Advertisement
Sign in to follow this  
luzop

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


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


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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!