Collision response - solver, penetration recovery

Please don't post Bullet support questions here, use the above forums instead.
Pipirongu
Posts: 10
Joined: Fri Dec 04, 2015 2:48 am

Collision response - solver, penetration recovery

Post by Pipirongu »

I'm using OBB with SAT to detect collisions and then Sutherland-Hodgman clipping for contact generation.

An impulse is applied for each contact point using the equation for impulse based method.
https://upload.wikimedia.org/math/a/f/9 ... cbb794.png

However, i'm having penetration issues that two objects can overlap slightly. After researching it seems I should use Baumgarte stabilization to recover from penetration, but I'm unsure how to.
One thing that confuses me is "solver" that people keep mentioning.

If I use impulse based method to solve collisions is that a solver?
This site http://allenchou.net/2013/12/game-physi ... l-impulse/ uses a different equation than the one I use. Is that something entirely different thing or just an alternative way to solve collisions?
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Collision response - solver, penetration recovery

Post by bone »

There is more than one way to fix the inevitable overlap. I don't think Baumgarte stabilization is in favor anymore (I have used it in the past, but it seemed difficult to tune). If you look up the CFM/ERP variables that Erin Catto uses on his impulses, that is one good method (which I am currently using with decent success). Another method is to physically move the bodies out of each other after the impulse solver has completed (it's a "position correction") - I think Dirk Gregorius has advocated something like this idea. I have tried that but it sometimes caused additional issues (say I rotate a long stick to get out of a collision at one end, well that sometimes puts it into a different collision at the other end!). So my recommendation is to look up CFM and ERP and how to use those in your impulse calculation.

What people generally mean by a solver is solving all the constraints simultaneously, since the constraints may be in conflict with each other. Iterating through your constraints multiple times in such a way that they resolve the conflicts is indeed one type of solver - called Sequential Impulse (both it and Erin Catto are mentioned in your bottom link). That method iterates towards a solution but can usually never reach it exactly. There are direct solvers that sometimes can solve exactly, but they are somewhat difficult to use and quite limiting.

Hope this helps.
Pipirongu
Posts: 10
Joined: Fri Dec 04, 2015 2:48 am

Re: Collision response - solver, penetration recovery

Post by Pipirongu »

Is the impulse based model on my first link an outdated method? I haven't seen people using it as a solver.

Is a contact point the same as a constraint? Or does a constraint store more information?
The data I currently have is contact points and collision normal, penetration from SAT.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Collision response - solver, penetration recovery

Post by Dirk Gregorius »

You first create contact points as you describe using e.g. SAT or any other method of choice. Then (in the solver) you create usually one non-penetration constraint and two friction constraints per contact point. While the contact point contains all geometrical information (position, normal, penetration depth), the constraint has additional information like the Jacobian and effective mass which is needed to resolve the contact. It can also contain the Baumgarte information to recover from penetration.

I recommend reading everything published by Erin and others on Box2D.org. There is also a simple version of Box2D called Box2D Lite which implements a very basic physic engine. The best way to learn these things is to port it to 3D in my opinion.
Allen Chou
Posts: 1
Joined: Wed Dec 09, 2015 4:06 am
Location: Santa Monica, CA
Contact:

Re: Collision response - solver, penetration recovery

Post by Allen Chou »

bone wrote:I don't think Baumgarte stabilization is in favor anymore (I have used it in the past, but it seemed difficult to tune). If you look up the CFM/ERP variables that Erin Catto uses on his impulses, that is one good method (which I am currently using with decent success).
Actually, ERP IS the Baumgarte stabilization factor (beta).
I think I know which of Erin's presentation you are talking about.
Perhaps you were thinking about the re-parameterization of beta and gamma into oscillation frequency (omega) and damping ratio (zeta)?
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Collision response - solver, penetration recovery

Post by bone »

OK, you're (basically) right, ERP is a form of Baumgarte stabilization. My confusion stems from originally using Baumgarte's method on a force-based rather than impulse-based physics system. Perhaps that even has something to do with my difficulty tuning it, but that's water over the dam at this point.

EDIT: In fact, I believe Baumgarte originally developed the technique on a force-based system. And other people seemed to have the same tuning issue, according to a description here: http://www.cs.ucsb.edu/~cse/Files/Stabi ... 071993.pdf. The problem described, which indicates the necessary Baumgarte factor depends on both the step size and discretization method, is seemingly solved with Catto's ERP method.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Collision response - solver, penetration recovery

Post by Dirk Gregorius »

A notable thing that is often overlooked is that Baumgarte for force based steppers is applied before the discretization, and for impulse based steppers it applied after. Tweaking Baumgarte is usually pretty difficult and it is even harder for force based steppers from my experience.

I personally prefer projection methods since they are more forgiving. E.g. orthogonal projection (NGS) or symmetric projection which is more popular in high end cloth simulation since it preservers momentum better. To give a practical example e.g. if you switch to ragdoll and you have intermediate bones which are not mapped to a rigid body this can introduce positional errors that result in strange velocities giving pretty bad looking simulations. Similarly when you have hierarchical destruction, child pieces can be overlapping when created and this adds momentum to the simulation which might be undesirable. Artists are often a bit sloppy when setting up the hierarchical scenes and it is nice not to worry about small initial overlaps from my experience. On the pro side Baumgarte stabilization is the easiest and fastest stabilization approach.

There exist more evolved methods like e.g. the Spook solver. KenB and Claude can elaborate more about this. I tried both and found that it doesn't matter too much when using iterative solvers. For direct solvers I assume the Spook method to behave much better and to be easier to tweak.

http://www8.cs.umu.se/kurser/5DV058/VT1 ... knotes.pdf
DannyChapman
Posts: 84
Joined: Sun Jan 07, 2007 4:29 pm
Location: Oxford, England
Contact:

Re: Collision response - solver, penetration recovery

Post by DannyChapman »

For error correction, look up "split impulses". This allows overlap to be corrected without adding momentum to the system (i.e. a sphere that starts slightly below the floor will pop up to the level of the floor in one update, but it won't do so in a way that makes it continue to move upwards in subsequent updates), and the calculations can use the same code and pre-calculated data as your normal contact handling system.
Pipirongu
Posts: 10
Joined: Fri Dec 04, 2015 2:48 am

Re: Collision response - solver, penetration recovery

Post by Pipirongu »

What do I need to do to prevent jittering when stacking boxes? The box on top starts to rotate and slide off.

I'm correcting penetration by moving them with position and not velocity. And don't have friction yet.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Collision response - solver, penetration recovery

Post by Dirk Gregorius »

I think you need to add friction from what you are describing. If you still see jitter after this make sure that the penetration recovery is not overshooting.
Pipirongu
Posts: 10
Joined: Fri Dec 04, 2015 2:48 am

Re: Collision response - solver, penetration recovery

Post by Pipirongu »

I still don't have friction. I can stack 3-4 boxes for awhile with 10 iterations before they slide off.

I have a question about the clipping part. I first clip the incident face against the 4 side planes of the reference object. I then filter the points against the reference plane. In the picture the cube with the white line(the direction the impulse should be applied) is the incident face. I feel like the two points on the left side of the picture should be filtered as well?

I tried by filtering the points I get from clipping against the reference plane and the 4 sideplanes. Which gives me 4 points instead and I can stack the boxes without iterations or position correction. But if the cube collide with a plane and the plane happens to be the incident object, no points will be generated. Every point gets filtered. A
Image
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Collision response - solver, penetration recovery

Post by Dirk Gregorius »

Do you use Sutherland-Hodgman clipping?
Pipirongu
Posts: 10
Joined: Fri Dec 04, 2015 2:48 am

Re: Collision response - solver, penetration recovery

Post by Pipirongu »

Dirk Gregorius wrote:Do you use Sutherland-Hodgman clipping?
Yes, I followed your example here: http://www.gamedev.net/topic/667499-3d- ... try5224015
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Collision response - solver, penetration recovery

Post by Dirk Gregorius »

It is difficult to tell from your picture, but I *think* (if I interpret the image correctly) that the two left vertices are wrong as well and the normal clipping code would handle this. There is no additional filtering necessary. You should debug your clipping code. E.g. draw the clip planes (a simple quad per edge) with the normal at the center of the edge making sure it is oriented correctly. Draw the incident face vertices. Make sure that they are all in the right space (world space would be the easiest initially). Also make sure that the normals are unit length before constructing the clip planes.

Regarding my example code I posted on Gamedev the assumption is that the normals of the clip planes point outside (e.g. clip_plane.normal = cross(edge_direction, reference_plane.normal).

HTH,
-Dirk
Pipirongu
Posts: 10
Joined: Fri Dec 04, 2015 2:48 am

Re: Collision response - solver, penetration recovery

Post by Pipirongu »

Dirk Gregorius wrote:It is difficult to tell from your picture, but I *think* (if I interpret the image correctly) that the two left vertices are wrong as well and the normal clipping code would handle this. There is no additional filtering necessary. You should debug your clipping code. E.g. draw the clip planes (a simple quad per edge) with the normal at the center of the edge making sure it is oriented correctly. Draw the incident face vertices. Make sure that they are all in the right space (world space would be the easiest initially). Also make sure that the normals are unit length before constructing the clip planes.

Regarding my example code I posted on Gamedev the assumption is that the normals of the clip planes point outside (e.g. clip_plane.normal = cross(edge_direction, reference_plane.normal).

HTH,
-Dirk
Ok so I rendered the reference plane normals and I've checked the incident face vertices before and they seem right. If i just filter against the reference plane. Shouldn't all these points be considered valid because they are on the plane? And if I clip against the red and blue side planes they should be filtered?

EDIT: Hmm I think they shouldn't even be there after clipping against the reference sideplanes

Image
Image

This is my side planes creation code. I looked at box2d lite for it. I use my oriented bounding box rotation axes as normals.

Code: Select all

void RenderScene::CreateReferenceSidePlanes(RigidBody* reference_body, int &axis_number, Vector3& normal1, Vector3& normal2, float& neg_offset1, float& pos_offset1, float& neg_offset2, float& pos_offset2)
{
	switch (axis_number)
	{
	case 0: //Reference face is on the x axis so we create side planes for the other axes
	{
				normal1 = reference_body->obb->rot[1];
				normal2 = reference_body->obb->rot[2];
				float y = Vector3::Dot(reference_body->obb->pos, normal1);
				float z = Vector3::Dot(reference_body->obb->pos, normal2);
				neg_offset1 = -y + reference_body->obb->half_extent[1];
				pos_offset1 = y + reference_body->obb->half_extent[1];
				neg_offset2 = -z + reference_body->obb->half_extent[2];
				pos_offset2 = z + reference_body->obb->half_extent[2];

				this->DrawSidePlanes(normal1, normal2, reference_body->obb->pos, 1, 2, reference_body->obb->half_extent);
	}
		break;

	case 1: //Reference face is on the y axis so we create side planes for the other axes
	{
				normal1 = reference_body->obb->rot[0];
				normal2 = reference_body->obb->rot[2];
				float x = Vector3::Dot(reference_body->obb->pos, normal1);
				float z = Vector3::Dot(reference_body->obb->pos, normal2);
				neg_offset1 = -x + reference_body->obb->half_extent[0];
				pos_offset1 = x + reference_body->obb->half_extent[0];
				neg_offset2 = -z + reference_body->obb->half_extent[2];
				pos_offset2 = z + reference_body->obb->half_extent[2];

				this->DrawSidePlanes(normal1, normal2, reference_body->obb->pos, 0, 2, reference_body->obb->half_extent);
	}
		break;

	case 2: //Reference face is on the z axis so we create side planes for the other axes
	{
				normal1 = reference_body->obb->rot[0];
				normal2 = reference_body->obb->rot[1];
				float x = Vector3::Dot(reference_body->obb->pos, normal1);
				float y = Vector3::Dot(reference_body->obb->pos, normal2);
				neg_offset1 = -x + reference_body->obb->half_extent[0];
				pos_offset1 = x + reference_body->obb->half_extent[0];
				neg_offset2 = -y + reference_body->obb->half_extent[1];
				pos_offset2 = y + reference_body->obb->half_extent[1];

				this->DrawSidePlanes(normal1, normal2, reference_body->obb->pos, 0, 1, reference_body->obb->half_extent);
	}
		break;
	}

}
Post Reply