Sign in to follow this  
Gumgo

Swept 2d capsule physics

Recommended Posts

Gumgo    968
I'm currently trying to code up some 2D platformer physics. My goal is to get something along the lines of Super Metroid style movement. Level creation is done by drawing line segments to represent surfaces, so it should support slopes and not just horizontal/vertical surfaces. As a first attempt, I tried implementing swept capsule - line segment collision detection and response (code posted below). It is essentially this implementation: [url="http://www.peroxide.dk/papers/collision/collision.pdf"]http://www.peroxide....n/collision.pdf[/url], except using line segments and capsules instead of triangles and ellipsoids, and in 2D instead of 3D. Unfortunately I keep running into bugs which seem to be caused by floating point precision. I have a few questions relating to this, as well as the overall technique I'm using. (I've attached an image explaining what I mean for a lot of this.)

1. My implementation predicts when a capsule is about to hit a line segment, moves it close, and alters its velocity. However, it doesn't deal with the case where the capsule somehow is intersecting already with the line segment (it shouldn't happen with infinite precision, but of course, that doesn't exist). What's the best approach for handling this, since it seems to be causing problems.

2. Sometimes a capsule is able to get a distance of 0 from a line segment, rather than the enforced minimum epsilon distance. When this happens, a collision is always immediately detected after 0 time, so the capsule gets "stuck". How should I be dealing with these cases? (I guess this is the same as question 1.)

3. Right now to detect whether I'm on a surface, I check whether there are any line segments within an epsilon distance from the capsule that aren't too steep. If so, I don't apply gravity but instead move the capsule back and forth along the tangent vector. However, due to floating point, I believe the capsule sometimes gets a little bit "too far" and gravity kicks back in for 1 frame (3). What's the best approach for "consistently" keeping the player on a slope once they've hit?

4. There are a few issues I've noticed with the overall technique that don't seem to be quite what I expected. For example, when you collide upward with a sloped ceiling, you shoot off at the angle of the slope (1). Another example is walking over a "kink" in the floor - rather than following the floor, the player overshoots and then lands (2). What alternative platformer physics techniques exist that don't have these problems?

5. I really like the technique of swept collisions to solve for the exact intersection point since it doesn't have the problem other techniques do with fast moving objects (it is also very easy to test), but it seems very finicky - if you get floating point imprecision which brings the player just a little too close or too far from the line segment, the whole thing breaks. Is there an approach which uses the accuracy of sweep tests to find the closest intersection point but is more forgiving about precision?

6. Related to question 4 - perhaps I'm actually going about this all wrong... am I using the sweep tests incorrectly? Thinking more about it, sweep testing is only in the detection phase, and it's really my collision responses that are wrong. If someone could explain to me or point me to a description of an algorithm that uses sweep tests correctly/doesn't suffer from the finickyness, that would be really great.

Here's the algorithm I've come up with (the actual code is more optimized) - I've tried to put it in readable pseudocode and explain it will with images, but let me know if it's unclear (note: "colliders" are line segments):
[source]
actor: a // this is the capsule we're colliding

// check whether the actor is on the ground
bool on_ground = false // whether ground is detected
vec2 ground_normal // the normal vector we find for the ground
Collider ground // the line we found to be the ground

// this is the range the ground must be in
float ground_range = epsilon * 3

// loop through each potential collider and see which one is closest
float min_distance = FLOAT_MAX
for each potential collider ls:
// find the distance and normal vector of this collider to the capsule (img 4)
( float dist, vec2 normal ) = distance2( a.capsule, ls )

// make sure the distance is within range
if dist >= 0 and dist < ground_range and dist < min_distance:

if ls is not too steep:
min_distance = dist
ground_normal = normal
ground = ls
on_ground = true

// now we apply either walking or gravity
if on_ground:
// if on the ground, apply walking

// find a vector orthogonal to the ground normal
vec2 right_vec = ground_normal.orthogonal()
if right_vec.x < 0:
right_vec.negate()

// split the velocity into 2 components so we can edit the right/left velocity (img 5)
float up_velocity = ground_normal.dot( a.velocity )
float right_velocity = right_vec.dot( a.velocity )

// adjust left/right velocity
if walking right:
if right_velocity < a.walk_speed:
right_velocity = min( a.walk_speed, right_velocity + a.walk_acceleration )
else if right_velocity > a.walk_speed:
right_velocity = max( a.walk_speed, right_velocity - a.walk_acceleration )
else if walking left:
if right_velocity > -a.walk_speed:
right_velocity = max( -a.walk_speed, right_velocity - a.walk_acceleration )
else if right_velocity < -a.walk_speed:
right_velocity = min( -a.walk_speed, right_velocity + a.walk_acceleration )
else if standing still:
if right_velocity > 0:
right_velocity = max( 0, right_velocity - a.walk_acceleration )
else if right_velocity < 0:
right_velocity = min( 0, right_velocity + a.walk_acceleration )

// recombine the velocity
a.velocity = up_velocity*ground_normal + right_velocity*right_vec

// if jumping, add some vertical speed
if a.jump:
a.velocity.y -= a.jump_speed
else:
// we aren't on the ground, so apply gravity
if a.gravity > 0:
a.velocity.y += a.gravity
else if a.gravity < 0:
a.velocity.y += a.gravity

// now do the actual collision detection/response
// we start out with 100% of the original velocity
// each iteration, we subtract the percentage of the velocity we move until we reach 0
float velocity_remaining = 1

// the direction and magnitude of the current velocity
vec2 next_velocity = a.velocity

for r = 0 to MAX_ITERATIONS:
// do some early outs first
if velocity_remaining < epsilon or next_velocity.magnitude() == 0:
break

// we can only move the remaining portion of next_velocity
vec2 velocity = next_velocity * velocity_remaining

// get the magnitude of the velocity and find the normalized velocity
float velocity_magnitude = velocity.magnitude()
vec2 velocity_normalized = velocity / velocity_magnitude

// when we do the sweep test, we actually use a slightly larger velocity
// this is so we detect collisions that are at the very end of the velocity vector,
// so we don't accidentally move right up next to any objects (img 6)
vec2 larger_velocity = velocity + velocity_normalized*epsilon
float larger_velocity_magnitude = velocity_magnitude + epsilon

// loop through each potential collider and see which one we hit first
// store the minimum sweep time in min_sweep_time and the collider in min_collision
// store the normal vector of the intersection in min_isect_normal and the point of intersection in min_isect_point
// (img 7)
float min_sweep_time = 1
vec2 min_isect_normal
vec2 min_isect_point
Collider min_collision
bool collision = false
for each potential collider ls:
// perform the sweep test using velocity plus epsilon (that is, velocity_larger)
( float sweep_time, vec2 isect_normal, vec2 isect_point ) = sweep( a.capsule, larger_velocity, ls )

// if this is the smallest time, store this potential collider
if (sweep_time < min_sweep_time) {
min_sweep_time = sweep_time
min_isect_normal = isect_normal
min_isect_point = isect_point
min_collider = ls
collision = true
}
}

if !collision:
// if there was no collision, we just move forward by the original velocity (remaining)
velocity_remaining = 0
a.capsule.position += velocity
else:
// there was a collision! now things get tricky

// the sweep time is currently in terms of larger_velocity
// however, this was just to make sure there wasn't an object "just out of reach";
// that is, within epsilon units from the end of the velocity vector
// larger_velocity is velocity + epsilon, so we need to get
// sweep time back in terms of velocity
float actual_min_sweep_time = min_sweep_time * (larger_velocity_magnitude / velocity_magnitude)

// we move to the point of collision
float move_magnitude = velocity_magnitude * actual_min_sweep_time

// now there's a problem; we never want to get within epsilon units of the collider
// we could just subtract epsilon from move_magnitude, however that doesn't account for grazing angles
// see (img 7) for visual explanation
// instead, we solve for the magnitude of the velocity vector that will bring us epsilon units from the collider
// see (img 8) for visual explanation
// first, we find the point on the capsule that the collision would occur at if moved along velocity
vec2 isect_on_capsule = min_isect_point - actual_min_sweep_time*velocity
// now we parameterize this point as p + vt; that is, moving along the velocity vector
// we solve for t such that the distance between p + vt and the collider is equal to epsilon
// n = min_isect_normal, i = min_isect_point, p = isect_on_capsule, v = velocity, t = time, d = distance
// d = n . ((p + vt) - i)
// d = n.(p + vt) - n.i
// d = n.p + n.vt - n.i
// d = n.vt + n.p - n.i
// d = n.vt + n.(p-i)
// d - n.(p-i) = n.vt
// t = (d + n.(i-p)) / n.v
// we want to solve for when d = epsilon
float denom = min_isect_normal.dot( velocity )
if denom != 0:
// find t
float t = (epsilon + min_isect_normal.dot( min_isect_point - isect_on_capsule )) / denom

// this is the maximum we can move before we get epsilon distance
float max_allowed_move_magnitude = velocity_magnitude * t

// if our current velocity magnitude exceeds this, set it to max_allowed_move_magnitude instead
if max_allowed_move_magnitude < move_magnitude:
move_magnitude = max_allowed_move_magnitude

// make sure we're not moving further than the original velocity or backward
move_magnitude = clamp( move_magnitude, 0, velocity_magnitude )

// adjust the remaining velocity based on the percent move_magnitude is of the original magnitude
velocity_remaining *= (1 - move_magnitude / velocity_magnitude)

// perform the move by moveMagnitude
vec2 move = velocity_normalized * move_magnitude
a.capsule.position += move
// we need this still, so move it also
isect_on_capsule += move

// now that we have moved epsilon way from the collider, we find our new velocity vector
// we need to figure out the next velocity based on the angle of the collider
// we want to move to a point down the collider which is also epsilon away from it
// therefore, we find the point on the collider we would want to move to and push it out by epsilon
// first find the vector to slide along - this is orthogonal to the collider's normal
vec2 slide_vector = min_isect_normal.orthogonal()

// the new velocity is the component of the velocity in the direction of slide_vector,
// since the collider absorbed the perpendicular force

// we find the destination point on the slope
vec2 destination = min_isect_point + slide_vector * slide_vector.dot( next_velocity )

// again, we don't want to move to the collider, we want to move a little bit away
destination += min_isect_normal * epsilon
next_velocity = destination - isect_on_capsule

// loop another iteration

// finally, set the actor up for the next frame with the new velocity
a.velocity = next_velocity
[/source]

Thanks in advance.

EDIT: Anyone? How about if I rephrase it like this: I am able to successfully detect exact intersection points between objects (capsule to line) using sweep tests. Now that I have this functionality, what approach should I take to implement "stable" collision which doesn't break if something goes a bit wrong with small values?

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