Jump to content
  • Advertisement
whitwhoa

Sliding Plane Collision Response | Stop Object From Sliding Backwards on Slope

Recommended Posts

Alright...I've been trying to figure this out for about a week now to no avail, so I'm hoping someone on here can lend a hand or point me in the right direction. I have implemented a collision detection / response algorithm as discussed in the famous paper: Improved Collision detection and Response, and when I say "implemented" what I really did was convert the source code provided by the following tutorial: Sliding Camera Collision Detection to work with my opengl engine (which uses glm library). I was able to get everything working as expected, however for the life of me I cannot figure out how to limit sliding.

For example, If I move my character object up an incline and then stop, it will slide backwards until it reaches a flat surface. This is the behavior I have been attempting to rectify. I know why it's happening, gravity is being applied to the object on the Y-axis pushing it down into the plane, then the position is corrected moving the object outside of the plane which is now a lower position than it was before the collision, then this process repeats until a flat surface is reached.

Things I have tried so far include:

  • Only applying gravity if my initial velocity does not equal (0,0,0), so if player is providing input. I quickly realized how naive this was when I stopped moving while being "in-air".
  • Ray casting from the position of the character object downwards on the Y axis and returning the closest intersection point, then only applying gravity if the difference between the character object and intersection point was greater than a specific value. This sort of worked, but was inconsistent and caused a horrible stutter when running down a slope.
  • Finding the collision intersection point, a `min_y`, and a `max_y` value. `min_y` and `max_y` denoted a range of y values that if the intersection point was between then we knew we were "grounded". This produced the same results as my attempt with the ray cast.

If anyone knows how I should go about implementing this, please, for the love of god let me know as my sanity is slowly slipping away! Any and all tips, suggestions, links to articles, etc greatly appreciated.

Below is my code relevant to the question (let me know if I missed something or if you want to see something else). Also if anyone is interested I can provide a link to a .zip of the project. Just let me know.

void PlayerController::updateVelocity() {

	float speed = player_move_speed * delta;
	
	player_velocity = glm::vec3(0.0f, 0.0f, 0.0f);

	if (input_state->key_w)
		player_velocity += speed * player_direction;
	if (input_state->key_s)
		player_velocity -= speed * player_direction;
	if (input_state->key_a)
		player_velocity -= glm::normalize(glm::cross(player_direction, up)) * speed;
	if (input_state->key_d)
		player_velocity += glm::normalize(glm::cross(player_direction, up)) * speed;
	if (input_state->key_space)
		player_velocity += speed * glm::vec3(0.0f, 10.0f, 0.0f);

}

void PlayerController::updatePosition() {
	
	CollisionPacket cp;
	cp.ellipsoid_space = glm::vec3(0.5f, 1.0f, 0.5f); // dimension of player ellipsoid collision object (radius)
	cp.w_position = player_position;
	cp.w_velocity = player_velocity;

	player_position = collisionSlide(cp);
	view_position = player_position + view_offset;

}

glm::vec3 PlayerController::collisionSlide(CollisionPacket cp) {

	cp.e_velocity = cp.w_velocity / cp.ellipsoid_space;
	cp.e_position = cp.w_position / cp.ellipsoid_space;

	cp.collision_recursion_depth = 0;
	glm::vec3 final_position = collideWithWorld(cp);

	cp.e_velocity = gravity / cp.ellipsoid_space;
	cp.e_position = final_position;
	cp.collision_recursion_depth = 0;
	final_position = collideWithWorld(cp);

	final_position = final_position * cp.ellipsoid_space;

	return final_position;

}

glm::vec3 PlayerController::collideWithWorld(CollisionPacket& cp) {

	float unit_scale = 1.0f; // 1 unit per meter

	float very_close_distance = 0.005f * unit_scale;


	if (cp.collision_recursion_depth > 5) {
		return cp.e_position;
	}

	cp.e_normalized_velocity = glm::normalize(cp.e_velocity);

	cp.found_collision = false;
	cp.nearest_distance = 0.0f;

	glm::vec3 p0, p1, p2;
	for (int tri_counter = 0; tri_counter < collision_soup.indices.size() / 3; tri_counter++) {

		p0 = collision_soup.positions[collision_soup.indices[3 * tri_counter]];
		p1 = collision_soup.positions[collision_soup.indices[3 * tri_counter + 1]];
		p2 = collision_soup.positions[collision_soup.indices[3 * tri_counter + 2]];

		p0 = p0 / cp.ellipsoid_space;
		p1 = p1 / cp.ellipsoid_space;
		p2 = p2 / cp.ellipsoid_space;

		glm::vec3 tri_normal = glm::normalize(glm::cross((p1 - p0), (p2 - p0)));

		sphereCollidingWithTriangle(cp, p0, p1, p2, tri_normal);

	}

	if (cp.found_collision == false) {
		return cp.e_position + cp.e_velocity;
	}
	
	glm::vec3 destination_point = cp.e_position + cp.e_velocity;
	glm::vec3 new_position = cp.e_position;

	if (cp.nearest_distance >= very_close_distance) {

		glm::vec3 V = cp.e_velocity;
		V = glm::normalize(V);
		V = V * (cp.nearest_distance - very_close_distance);
		new_position = cp.e_position + V;

		V = glm::normalize(V);
		cp.intersection_point -= very_close_distance * V;

	}

	glm::vec3 slide_plane_origin = cp.intersection_point;
	glm::vec3 slide_plane_normal = new_position - cp.intersection_point;
	slide_plane_normal = glm::normalize(slide_plane_normal);

	float x = slide_plane_origin.x;
	float y = slide_plane_origin.y;
	float z = slide_plane_origin.z;

	float A = slide_plane_normal.x;
	float B = slide_plane_normal.y;
	float C = slide_plane_normal.z;
	float D = -((A*x) + (B*y) + (C*z));

	float plane_constant = D;

	float signed_distance_from_destination_point_to_sliding_plane = glm::dot(destination_point, slide_plane_normal) + plane_constant;

	glm::vec3 new_destination_point = destination_point - signed_distance_from_destination_point_to_sliding_plane * slide_plane_normal;

	glm::vec3 new_velocity_vector = new_destination_point - cp.intersection_point;

	
	if (glm::length(new_velocity_vector) < very_close_distance) {

		return new_position;

	}

	cp.collision_recursion_depth++;
	cp.e_position = new_position;
	cp.e_velocity = new_velocity_vector;
	return collideWithWorld(cp);
	
}

bool PlayerController::sphereCollidingWithTriangle(CollisionPacket& cp, glm::vec3& p0, 
	glm::vec3& p1, glm::vec3& p2, glm::vec3& tri_normal) {

	float facing = glm::dot(tri_normal, cp.e_normalized_velocity);
	if (facing <= 0) {

		glm::vec3 velocity = cp.e_velocity;
		glm::vec3 position = cp.e_position;

		float t0, t1;

		bool sphere_in_plane = false;

		// First the point in the plane
		float x = p0.x;
		float y = p0.y;
		float z = p0.z;

		// Next the planes normal
		float A = tri_normal.x;
		float B = tri_normal.y;
		float C = tri_normal.z;

		// Lets solve for D
		// step 1: 0 = Ax + By + Cz + D
		// step 2: subtract D from both sides
		//			-D = Ax + By + Cz
		// setp 3: multiply both sides by -1
		//			-D*-1 = -1 * (Ax + By + Cz)
		// final answer: D = -(Ax + By + Cz)
		float D = -((A*x) + (B*y) + (C*z));

		// To keep the variable names clear, we will rename D to plane_constant
		float plane_constant = D;

		float signed_distance_from_position_to_tri_plane = glm::dot(position, tri_normal) + plane_constant;
		float plane_normal_dot_velocity = glm::dot(tri_normal, velocity);

		if (plane_normal_dot_velocity == 0.0f) {

			if (fabs(signed_distance_from_position_to_tri_plane) >= 1.0f) {

				return false;

			}
			else {

				sphere_in_plane = true;

			}

		}
		else {

			t0 = (1.0f - signed_distance_from_position_to_tri_plane) / plane_normal_dot_velocity;
			t1 = (-1.0f - signed_distance_from_position_to_tri_plane) / plane_normal_dot_velocity;

			if (t0 > t1) {
				float temp = t0;
				t0 = t1;
				t1 = temp;
			}

			if (t0 > 1.0f || t1 < 0.0f) {
				return false;
			}

			if (t0 < 0.0) t0 = 0.0;
			if (t1 > 1.0) t1 = 1.0;

			glm::vec3 collision_point;			
			bool colliding_with_tri = false;	
			float t = 1.0f;						

			if (!sphere_in_plane) {

				glm::vec3 plane_intersection_point = (position + t0 * velocity - tri_normal);

				if (checkPointInTriangle(plane_intersection_point, p0, p1, p2)) {

					colliding_with_tri = true;
					t = t0;
					collision_point = plane_intersection_point;

				}

			}

			if (colliding_with_tri == false) {

				float a, b, c; // Equation Parameters

				float velocity_length_squared = glm::length(velocity);
				velocity_length_squared *= velocity_length_squared;

				a = velocity_length_squared;

				float new_t;

				// P0 - Collision test with sphere and p0
				b = 2.0f * glm::dot(velocity, position - p0);
				c = glm::length((p0 - position));
				c = (c*c) - 1.0f;

				if (getLowestRoot(a, b, c, t, &new_t)) {

					t = new_t;
					colliding_with_tri = true;
					collision_point = p0;

				}

				// P1 - Collision test with sphere and p1
				b = 2.0f * glm::dot(velocity, position - p1);
				c = glm::length((p1 - position));
				c = (c*c) - 1.0f;
				if (getLowestRoot(a, b, c, t, &new_t)) {

					t = new_t;
					colliding_with_tri = true;
					collision_point = p1;

				}

				// P2 - Collision test with sphere and p2
				b = 2.0f * glm::dot(velocity, position - p2);
				c = glm::length((p2 - position));
				c = (c*c) - 1.0f;
				if (getLowestRoot(a, b, c, t, &new_t)) {

					t = new_t;
					colliding_with_tri = true;
					collision_point = p2;

				}

				// Edge (p0, p1):
				glm::vec3 edge = p1 - p0;
				glm::vec3 sphere_position_to_vertex = p0 - position;
				float edge_length_squared = glm::length(edge);
				edge_length_squared *= edge_length_squared;
				float edge_dot_velocity = glm::dot(edge, velocity);
				float edge_dot_sphere_position_to_vertex = glm::dot(edge, sphere_position_to_vertex);
				float sphere_position_to_vertex_length_squared = glm::length(sphere_position_to_vertex);
				sphere_position_to_vertex_length_squared = sphere_position_to_vertex_length_squared * sphere_position_to_vertex_length_squared;

				// Equation parameters
				a = edge_length_squared * -velocity_length_squared + (edge_dot_velocity * edge_dot_velocity);
				b = edge_length_squared * (2.0f * glm::dot(velocity, sphere_position_to_vertex)) - (2.0f * edge_dot_velocity * edge_dot_sphere_position_to_vertex);
				c = edge_length_squared * (1.0f - sphere_position_to_vertex_length_squared) + (edge_dot_sphere_position_to_vertex * edge_dot_sphere_position_to_vertex);

				if (getLowestRoot(a, b, c, t, &new_t)) {
					float f = (edge_dot_velocity * new_t - edge_dot_sphere_position_to_vertex) / edge_length_squared;
					if (f >= 0.0f && f <= 1.0f) {
						t = new_t;
						colliding_with_tri = true;
						collision_point = p0 + f * edge;
					}
				}

				// Edge (p1, p2):
				edge = p2 - p1;
				sphere_position_to_vertex = p1 - position;
				edge_length_squared = glm::length(edge);
				edge_length_squared *= edge_length_squared;
				edge_dot_velocity = glm::dot(edge, velocity);
				edge_dot_sphere_position_to_vertex = glm::dot(edge, sphere_position_to_vertex);
				sphere_position_to_vertex_length_squared = glm::length(sphere_position_to_vertex);
				sphere_position_to_vertex_length_squared = sphere_position_to_vertex_length_squared * sphere_position_to_vertex_length_squared;

				// Equation parameters
				a = edge_length_squared * -velocity_length_squared + (edge_dot_velocity * edge_dot_velocity);
				b = edge_length_squared * (2.0f * glm::dot(velocity, sphere_position_to_vertex)) - (2.0f * edge_dot_velocity * edge_dot_sphere_position_to_vertex);
				c = edge_length_squared * (1.0f - sphere_position_to_vertex_length_squared) + (edge_dot_sphere_position_to_vertex * edge_dot_sphere_position_to_vertex);

				if (getLowestRoot(a, b, c, t, &new_t)) {
					float f = (edge_dot_velocity * new_t - edge_dot_sphere_position_to_vertex) / edge_length_squared;
					if (f >= 0.0f && f <= 1.0f) {
						t = new_t;
						colliding_with_tri = true;
						collision_point = p1 + f * edge;
					}
				}

				// Edge (p2, p0):
				edge = p0 - p2;
				sphere_position_to_vertex = p2 - position;
				edge_length_squared = glm::length(edge);
				edge_length_squared *= edge_length_squared;
				edge_dot_velocity = glm::dot(edge, velocity);
				edge_dot_sphere_position_to_vertex = glm::dot(edge, sphere_position_to_vertex);
				sphere_position_to_vertex_length_squared = glm::length(sphere_position_to_vertex);
				sphere_position_to_vertex_length_squared = sphere_position_to_vertex_length_squared * sphere_position_to_vertex_length_squared;

				// Equation parameters
				a = edge_length_squared * -velocity_length_squared + (edge_dot_velocity * edge_dot_velocity);
				b = edge_length_squared * (2.0f * glm::dot(velocity, sphere_position_to_vertex)) - (2.0f * edge_dot_velocity * edge_dot_sphere_position_to_vertex);
				c = edge_length_squared * (1.0f - sphere_position_to_vertex_length_squared) + (edge_dot_sphere_position_to_vertex * edge_dot_sphere_position_to_vertex);

				if (getLowestRoot(a, b, c, t, &new_t)) {
					float f = (edge_dot_velocity * new_t - edge_dot_sphere_position_to_vertex) / edge_length_squared;
					if (f >= 0.0f && f <= 1.0f) {
						t = new_t;
						colliding_with_tri = true;
						collision_point = p2 + f * edge;
					}
				}

			}

			if (colliding_with_tri == true) {

				float dist_to_collision = t * glm::length(velocity);

				if (cp.found_collision == false || dist_to_collision < cp.nearest_distance) {
					cp.nearest_distance = dist_to_collision;
					cp.intersection_point = collision_point;
					cp.found_collision = true;

					return true;

				}

			}

		}

		return false;

	}

/* End sphereCollidingWithTriangle
--------------------------------------------------------------*/
}

bool PlayerController::checkPointInTriangle(const glm::vec3& point, const glm::vec3& triV1, const glm::vec3& triV2, const glm::vec3& triV3) {

	glm::vec3 cp1 = glm::cross((triV3 - triV2), (point - triV2));
	glm::vec3 cp2 = glm::cross((triV3 - triV2), (triV1 - triV2));
	if (glm::dot(cp1, cp2) >= 0) {

		cp1 = glm::cross((triV3 - triV1), (point - triV1));
		cp2 = glm::cross((triV3 - triV1), (triV2 - triV1));
		if (glm::dot(cp1, cp2) >= 0) {

			cp1 = glm::cross((triV2 - triV1), (point - triV1));
			cp2 = glm::cross((triV2 - triV1), (triV3 - triV1));
			if (glm::dot(cp1, cp2) >= 0) {

				return true;

			}

		}

	}

	return false;

}

bool PlayerController::getLowestRoot(float a, float b, float c, float maxR, float* root) {

	float determinant = b * b - 4.0f*a*c;

	if (determinant < 0.0f) return false;

	float sqrtD = sqrt(determinant);
	float r1 = (-b - sqrtD) / (2 * a);
	float r2 = (-b + sqrtD) / (2 * a);

	if (r1 > r2) {
		float temp = r2;
		r2 = r1;
		r1 = temp;
	}

	if (r1 > 0 && r1 < maxR) {
		*root = r1;
		return true;
	}

	if (r2 > 0 && r2 < maxR) {
		*root = r2;
		return true;
	}

	return false;
}

 

 

Share this post


Link to post
Share on other sites
Advertisement
Posted (edited)

I like to solve this scenario by only applying gravity when the player is in the "not on the ground" state. I use a time of impact sweep function to see if the player can fall. If they can, they enter the "not on the ground" state and gravity starts applying. Exactly how far down to sweep is a tuneable parameter. This is very similar to traditional raycast approaches, where they have an "on the ground state" for the player that simply raycasts downward to find the ground. If you have jittering problem with these approaches then you must be doing something incorrect or not in a good way. Generally a player is on the ground until a certain slope is reached, then they transition to sliding or falling, or until they walk off of a complete cliff and there's just empty space below them. These are detectable scenarios where you can make state shifts from "on the ground" to "not on the ground".

For racing games I have seen this problem solved by aggressive sleeping techniques, much like sleeping rigid bodies. Detect when the player is not pressing any inputs, and when the player isn't moving much, and set them into a "non-moving" state where gravity is not applied.

Another option is to calculate the exact velocity it would take to move the player up the hill, and then feed that into the player's velocity a-priori, in an attempt to get the correct result. I've seen this sort of work ok in production, but this is a pretty terrible solution in my opinion, at least when compared to the other options I mentioned.

Edited by Randy Gaul

Share this post


Link to post
Share on other sites
31 minutes ago, Randy Gaul said:

 If you have jittering problem with these approaches then you must be doing something incorrect or not in a good way.

I absolutely agree I'm probably doing something incorrect or not in a good way 😀.

I think I'm going to give the raycasting solution another go with a grounded and not grounded state as you mentioned. I will post back my findings, as it will either work or I will have more details that would probably help to determine what I'm doing wrong here. 

Share this post


Link to post
Share on other sites
Posted (edited)

After attempting ray casting solution with a grounded flag, I remember why the stuttering / hopping was happening exactly now, only I'm unsure of how to circumvent it. I have created the following illustration to assist in my explanation. Below that is my updated collisionSlide function source, then my explanation follows:

collision_ray_intersection.jpg.3b2752ec44b09ce6aa86d88a4f3aa7ac.jpg

glm::vec3 PlayerController::collisionSlide(CollisionPacket cp) {

	cp.e_velocity = cp.w_velocity / cp.ellipsoid_space;
	cp.e_position = cp.w_position / cp.ellipsoid_space;
	cp.collision_recursion_depth = 0;
	
	glm::vec3 final_position = collideWithWorld(cp);


	glm::vec3 final_world_position = final_position * cp.ellipsoid_space;
	float distance_from_floor = ((final_world_position - checkVerticalPosition(final_world_position) - glm::vec3(0.0f, 1.0f, 0.0f))).y;
	
  	std::cout << distance_from_floor << "\n";

	bool grounded = false;
	if (distance_from_floor <= 0.05) {
		grounded = true;
	}

  	std::cout << std::boolalpha << grounded << "\n";
	
	if (!grounded) {
		cp.e_velocity = gravity / cp.ellipsoid_space;
		cp.e_position = final_position;
		cp.collision_recursion_depth = 0;
		final_position = collideWithWorld(cp);
	}


	// Convert our final position from ellipsoid space to world space
	final_position = final_position * cp.ellipsoid_space;

	return final_position;

}

Ok. So. In the above source, the line `if (distance_from_floor <= 0.05) {` is using a pre-determined offset value of 0.05 to account for the case of collision at an incline. When collision happens at an incline `distance_from_floor` is not zero due to the collision point not being directly below the object.  If the collision were between the object and a flat plane, `distance_from_floor` would be 0 (or close to it). Below is the cli output in the following order: resting on ground | running up left slope | running down left slope | running up right slope | running down right slope:

ray_collision_cli.jpg.077a4bf5e7e1e34f14038dd90735ff0a.jpg

From the cli print out it is clear that the stuttering does not happen going up either slope. However, the hopping does occur while traversing down each slope (although going down the left slope is barely noticeable if at all since the grounded state is set to false in fewer updates), the right slope being very noticeable.

This appears to be happening because of the number of updates it takes for the object to reach the 0.05 offset required to set the `grounded` flag to false so that gravity is then applied.

Any idea how I might go about resolving this issue? Or is there something horribly flawed with what I'm doing?

Edited by whitwhoa

Share this post


Link to post
Share on other sites

Usually the implementation of a grounded state just moves the player to the raycasting position instead of letting the player fall due to gravity. So each frame raycast downwards and set the player onto the floor. The grounded state can be thought of as “gliding along the floor” state, but with defined exit conditions (like max slope or max fall distance for a single timestep).

There are many extensions that can be added to make this all work better. For example, letting the player slightly intersect slopes floors so their center is placed directly on the raycast position. Or, detecting slope to prevent the player from instantly falling or running up huge hills with a very large slope.

Share this post


Link to post
Share on other sites
1 hour ago, Randy Gaul said:

Or, detecting slope to prevent the player from instantly falling or running up huge hills with a very large slope.

I believe if I were to understand how to detect the slope of the ground the player is colliding with, that would be the ah-ha! moment I'm looking for. Would you happen to know how I might do this?

Share this post


Link to post
Share on other sites

Usually the raycast function can return you the surface normal. Does your raycast function not have this?

Of course you still have to be careful with raycasting onto edges - you can get strange normals returned if you hit edges/vertices.

Share this post


Link to post
Share on other sites
11 minutes ago, Randy Gaul said:

Usually the raycast function can return you the surface normal. Does your raycast function not have this?

Of course you still have to be careful with raycasting onto edges - you can get strange normals returned if you hit edges/vertices.

I do have the surface normal, but how would I go about using that to determine if the angle of the slope?

Share this post


Link to post
Share on other sites

You can dot the gravity vector with the surface normal to understand the slope. The equation for the dot product has a cos(theta) within it to describe the angle of the surface relative to the gravity vector.

Share this post


Link to post
Share on other sites
Posted (edited)

Well my plan is to first read your article and then the external resources-of your research and my own post-research; as it is not an area of my primary specialization.

So here is the primary comment and in a later post(a couple weeks from now), I'll add the opinion of what I learnt about your topic in the mean-time.

Well first you should use doubles instead floats, uniform initialization and what regards if sentences, use this code:

if (a)
{

}

if (a == false)
{

}

Also what does gml namespace stand for?

And if you could provide us the header of the PlayerController class definition?

Edited by Acosix

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

  • 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!