Sign in to follow this  
too_many_stars

2 x OBB, SAT test and penetration depth

Recommended Posts

too_many_stars    336

Hi guys,

 

A quick question. I am using an impulse based physical system which works well for AABB and Circles (including resolving the penetration depth).

 

However, when attempting to calculate the penetration depth for 2 x OBBs in contact, I am relaying on this function, which also incidently gives the surface normal of contact (that works well) along the axis of least penetration.

 

However, when i turn on my penetration solver, I have the OBBs jumping through each other and acting in a strange fashion. Of course I need the penetration depth to solve the sinking problem and to help stabilize the system.

 

I am rather new to SAT test, and I am not sure if I am missing something. Should the accompanying normal with the penetration returned by the function below not give me proper penetration depth?

float overlapDist(Projection p1,Projection p2){
	
	if(p1.min>p2.max)
		return (p2.max-p1.min);
	else
		return (p1.max-p2.min);
		
}

Thanks,

 

Mike

Share this post


Link to post
Share on other sites
Randy Gaul    2762

I'd recommend debug rendering contact points and contact normals. Then visually debug your program. If you still can't debug it, then implement frame by frame stepping (e.g. hit space bar to simulate 1 frame), and make sure the simulation is deterministic.

 

I'm also not sure if the function you have is correct since I'm not sure what you're passing in. A more modern style of implementing SAT makes use of support points to calculate projection depths, which should be a little more efficient and simpler than computing and comparing actual projections.

Share this post


Link to post
Share on other sites
too_many_stars    336

Hello again Randy, it just happens I was reading your article on torque and orientation.

 

If done correctly, can I use the overlap to calculate the penetration depth, or do I have to go to your "support points?"

 

I am not sure if I am even doing the right thing in calculating the penetration depth. Articles talk about Minkowski distances, and other algos I am not familiar with. I just took a stab at the overlap thinking intuitivly that it should work.

 

Thanks,

 

Mike

Share this post


Link to post
Share on other sites
Irlan    4067

You have GJK-SAT + EPA as an option too; is the easy thing in the world, and the last Bullet™ EPA implementation avoids the numerical drifts you find when expanding the polytope in the expanding phase of the native implementation by Gino Van Den Bergen.

 

The only flaw of EPA is that only return the two closest points (position constraint contact points) in the objects, so you need to build some kind of contact point cache mechanism in order to get up to 2 or > points (2D) or 4 or > points (3D).

 

Make sure that the penetration depth is positive and the correct contact normal points from 0 to 1 or 1 to 0 objects.

 

If you have some problem when applying sequential impulses to the rigid body velocity constraints try to change the contact normal sign to see if you get correct results. You can debug all information using Randy Gauls approach also since is the preferable way.

 

Oh, I forgot to mention that you can download a simple demo of my working GJK-SAT here.

Edited by Irlan

Share this post


Link to post
Share on other sites
Randy Gaul    2762

Hello again Randy, it just happens I was reading your article on torque and orientation.

 

If done correctly, can I use the overlap to calculate the penetration depth, or do I have to go to your "support points?"

 

I am not sure if I am even doing the right thing in calculating the penetration depth. Articles talk about Minkowski distances, and other algos I am not familiar with. I just took a stab at the overlap thinking intuitivly that it should work.

 

Thanks,

 

Mike

Oh yeah you can totally implement a robust version where you compute projections and calculate their overlaps. It's just a little more involved. I wrote some introductory slides for the alternate newer style with support points here, maybe this can help: http://www.randygaul.net/2013/07/16/separating-axis-test-and-support-points-in-2d/

Share this post


Link to post
Share on other sites
too_many_stars    336

Hi Irlan,

 

Thanks for the response, but I must admit I have no idea what you are talking about with respect to the following (that should come as no surprise however as I am a noob)

 

GJK

EPA

Polytope

native implementation by Gino Van Den Bergen

 

Thanks,

 

Mike

Share this post


Link to post
Share on other sites
Irlan    4067

Hi Irlan,

 

Thanks for the response, but I must admit I have no idea what you are talking about with respect to the following (that should come as no surprise however as I am a noob)

 

GJK

EPA

Polytope

native implementation by Gino Van Den Bergen

 

Thanks,

 

Mike

 

Oh, sorry then. 

 

You should stay with SAT and find the minimum translation vector and the axis with minumum penetration for the two OBB to find  collision information. I won't say that this is the best way of doing it because you will find only one single point, and if  you want to get a stable physics simulation, you should get up to 4 contact points (a box above another box) (using some clipping algorithm), then if you want to support multiple convex objects like a cylinders, boxes, spheres, etc. you have the option to use GJK (Gilbert-Johnson-Keerthi).

 
GJK is based on Minkowski Difference (A-B). You subtract all points in A minus all points in B and if the objects are intersecting the A-B will contain a zero vector (a point in A equals to a point in B and its subtraction equals zero). So, GJK tries to find if there is a zero vector (the origin) inside the A-B set, reducing the time that takes to compute the A-B set by using shotcurts. That's the most basic idea of GJK, and if you want to visualize the algorithm you should spend some time reading articles and try to implement by yourself to see if its what you need.
 
I used GJK before getting into SAT and to me was more easely to visualize what I was doing.
Edited by Irlan

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this