Move sphere out of line segment = stuck

Math and Physics Programming

Started by _WeirdCat_ August 06, 2020 03:03 PM

30 comments, last by NikiTo 3 years, 8 months ago

_WeirdCat_

1,512

Author

August 06, 2020 03:03 PM

So the sphere is moving but after hitting closest point on edge it gets stuck

These are two drawings of thing what i am currently doing

Sphere is moving from rA to rB and i compute closest points on both line segments (edge of polygon and movement ray), if distance between them it closer than SR (sphere radius) theres a collision, i know all intersection points etc

Look at bottom right drawing - theres a h which is distance between closest points between - edge of poly and movement ray, knowing that i must move sphere by its radius out of the edge.

To do that i compute x with basic a^2 + b^2 = c^2 (sr^2 - h^2 = x^2) then i calc new sphere position from closest_rayP - normalize(rB-rA)*x;

But once i hit the the edge i have no sliding, it just stays at one position and sometimes it jitters but it does not slide around this edge..

So how actually i move sphere out of edge so i get sliding effect?

I force movement vector to be in the same direction as below all the time and i expect sphere to slide even changing it slightly does not indicate any sliding…

Master & Mentor
https://sites.google.com/site/customprog/

NikiTo

245

August 06, 2020 10:03 PM

Just copy the direction of the wall. How long it slides is another theme.
Jitter smells to me as floating precision problems.

_WeirdCat_

1,512

Author

August 06, 2020 10:54 PM

Yeah i was thinking about that but time distribution after collision bothers me there. What would be new wanna to go vector if i hit - what time it will get i think its (dt-timeof_last_hit)* vel

Master & Mentor
https://sites.google.com/site/customprog/

NikiTo

245

August 06, 2020 10:59 PM

I coded it for myself without time. Only lengths. If you shorten the vector, it will look like if you change time/velocity, but you only play with the length. At least in my case.

_WeirdCat_

1,512

Author

August 06, 2020 11:11 PM

Still even forcing new position to follow velocity vector does exactly the same:

Look here:

This is how i handle collision i check until theres no collision (in while loop which returns intersection points etc) nadt aint accurate here for now but i think it ddoesnt matter for now

void HandleCollision(PFComponent * pp, float dt)
{
	float sdt = dt;
	//start timer
	vec3 s = pp->vel*dt;
vec3 velocity = s;
	vec3 npos = pp->pos + s;
float rlen = VectorLength(pp->vel*dt);

	int citerations = 0;
	bool collided = false;
float scaled_radius = MetricToScale(0.01, float(map->one_meter_stands_for_units));

	while (( ( CalcColliders(pp->pos, npos,  scaled_radius) ) &amp;&amp; (citerations < 20) &amp;&amp; (VectorLength(pp->vel) > 0.01) &amp;&amp;
	 (sdt > 0.01) ))
	{
		citerations = citerations + 1;
		
		vec3 slide_n = nearest_col.col_normal;    // normalize( vectorAB(nearest_col.col_point, nearest_col.new_pos));
float nadt = n3ddistance(pp->pos, nearest_col.col_point);
if (nadt > rlen) rlen = nadt;
sdt = sdt - sdt * (nadt / rlen);
rlen = nadt;
		pp->pos = nearest_col.new_pos;
		float sd = dot(slide_n, npos);
		
		pp->vel = /*npos-slide_n*sd;*/ProjectVectorOnPlane(slide_n, pp->vel);
		
		npos = pp->pos + pp->vel*sdt;
		collided = true;
	}

pp->pos = npos;

}

Master & Mentor
https://sites.google.com/site/customprog/

NikiTo

245

August 06, 2020 11:33 PM

These jitters come from floating point imprecision.

It seems like it should work even with FP errors, but in practice it does not.

Can't you just use the library of somebody else who did it already?

It took me lot of time to solve it in 2D.
Why not just use the code of others? Somebody who did it in 3D?

I am not a master at FP, but simply put, the very same piece of code, can make different decisions at any moment -

JoeJ

4,185

August 07, 2020 06:02 AM

Not sure if it helps, but for convex shapes you can use Voroni Regions to differentiate between face, edge and vertex collision.

Her image for 2D case, so only lines and vertices:

The body is the green polygon. For each of its lines, we extrude them outwards to get the Voroni Region (E) of the line (along 2Dline / 3Dface normal). If the center of the ball is in this region, it should perform ball - face collision that you already have.

But if it is in a vertex region (V), it should only keep minimum distance (ball radius) to the vertex, and no sliding should be necessary.

Notice in 3d we have regions for polygons, edges and vertices.

It seems you have jitter because instead doing that, you alternate both adjacent lines (or faces in 3D). It's clearly a mistake but no floating point precision issue.

After fixing this, one good test case is this:

If the sphere has force to the right, it should not jitter or get stuck between the two objects forming a narrowing open space. It should just stop.

JoeJ

4,185

August 07, 2020 06:13 AM

… learned it form this paper: http://graphics.stanford.edu/courses/cs448b-00-winter/papers/TR97-05.pdf

JoeJ

4,185

August 07, 2020 06:20 AM

Another way to look at it is so called 'Minkovski Sum':

Here we extend the shape of the body with the shape of the ball, resulting in extrusion of the body and getting round vertices.
After that, we can ignore the radius of the ball and treat it only as a point that slides on the extruded body. (Collision detection / prediction can be done with simple raytracing from ball center along velocity towards extruded body.)
Notice the vertex regions span an arc, illustrating we need min distance constraint only.

NikiTo

245

August 07, 2020 12:05 PM

JoeJ said:
It's clearly a mistake but no floating point precision issue.

As it is shown here, both of the tests could fail and the player could pass through the walls. Although the two wals share the very same vertex, the floating precision problem messes it up.

It is something they teach students in the second month in any programming school.

https://stackoverflow.com/questions/56084008/how-to-prevent-floating-point-error-in-point-polygon-sliding-collision-detection

It is something really basic in computing. It is mentioned everywhere.

@_WeirdCat_ If i were you i would find somebody who already did it and use his code. Last time i reinvented the Minkowski Sum, and it worked perfectly for me, but in 2D only. Did not even try in 3D. And it took me lot of time. And now i am not needing it. So a bit of loss of time. At least i learned more about precision problems.

Move sphere out of line segment = stuck

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Move sphere out of line segment = stuck

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines