## Thursday, March 18, 2010

### Narrow Phase: Sweeping a Sphere Against a Polygon

Before sweeping a sphere against a polygon, you should determine if the sphere is already intersecting the polygon. I will discuss the case where the sphere is not initially intersecting the polygon.

We will use a 2D representation of the hypothetical setup, since it's easier to draw 2D pictures.

In this setup, there is a sphere with radius r located at point c, a relative velocity vector v that represents the difference of velocity between the sphere and the polygon. This relative velocity can be considered as the velocity of the sphere from the point of view of the polygon. The velocity is given in units that represent how much the sphere will move over the course of a given frame. Thus, at the end of the frame, the center of the sphere should be positioned at the tip of the velocity vector. The polygon lies entirely within some plane, and we are projecting the setup in such a way that the plane occupies a single line. The polygon itself is the bold section of the line. The normal n of the plane is pointing out of the front side of the polygon.

Before determining collision with the polygon, we will first determine collision with the plane. The first step is to find the point on the sphere that will first come into contact with the plane. This can be done scaling the normal of the plane by the radius of the sphere, and subtracting this from the center of the sphere.

$\mathbf{p}_1=\mathbf{c}-\mathbf{n}r$

We will sweep the point p1 forward. The sweep is accomplished by finding a line that passes through p1, and is parallel to v. We then find the point where the line intersects the plane. The point on the plane is the point where the sphere will first make contact with the plane.

The point p2 can be calculated using the following expression

$s=d-\mathbf{p}_1\cdot\mathbf{n}$
$\mathbf{p}_2=\mathbf{p}_1+\mathbf{v}s$

Here d is the plane parameter, and can be found by dotting the plane normal with any point that resides on the plane, such as one of the vertices of the polygon.

Before calculating p2, check if s is less than 0, or greater than 1. If it is then the collision is not going to happen during this frame, so you can return a false on your collision routine.

If s is between 0 and 1, then go ahead and calculate p2 and continue with the operation.

The next step is to find a point inside the polygon that is nearest to p2. The method for doing this is dependant on the polygon. If p2 already resides within the polygon, then the nearest point to p2 is just p2. Otherwise, the nearest point lies on the boundary of the polygon.

$\mathbf{p}_3={\rm nearestPoint}\left(\mathbf{p}_2\right)$

NOTE: Finding the nearest point on the polygon to p2 does not actually work in 3D, since it is possible to have components of velocity that are tangent to the polygon plane. To correct for this, you should try to find the point on the polygon that is closest to the ray that is cast from p1. This is done by finding which feature of the polygon (vertex, edge, or face) is closest to the line, and then finding the closest point on this feature to the line.

The point p3 is the point on the polygon that will first be touched by the sphere.

Now we will sweep the point p3 backward, and see if it touches the sphere. This sweep is performed by finding a line that passes throw p3 and is parallel with v. This line will intersect the sphere in 0, 1, or 2 places.

The formula for this sweep involves a square root. If the stuff we are trying to take the square root of is negative, then there is no intersection. So, we first check to see if this stuff is negative.

$\Delta =\left[\left(\mathbf{p}_3-\mathbf{c}\right)\cdot\mathbf{v}\right]^2-4\left(\mathbf{v}\cdot\mathbf{v}\right)\left[\left(\mathbf{p}_3+\mathbf{c}\right)\cdot\left(\mathbf{p}_3-\mathbf{c}\right)-r^2\right]$

If this is negative, then there is no collision and we can return false. Otherwise, we will continue to calculate the fraction of the time step t at which the collision takes place

$t=\frac{\sqrt{\Delta}-2\left(\mathbf{p}_3-\mathbf{c}\right)\cdot\mathbf{v}}{2\mathbf{v}\cdot\mathbf{v}}$

This quantity should not be less than 0. It may however be greater than 1. If it is, then there will be a collision, but not during this time interval, so return false. If however, t is less than 1, you can proceed to determine the point p4 that represents the point that the sphere will first come into contact with the polygon.

$\mathbf{p}_4=\mathbf{p}_3-\mathbf{v}t$

At this point, we can move the sphere forward so that it just touches the polygon. The task now is to determine how to resolve this collision, by adjusting the velocity of the sphere. Once we have determined the new, resolved, velocity we continue to sweep the sphere for the remainder of the time step - checking for collisions with other polygons along the way.

#### 1 comment:

1. You wrote:
" NOTE: Finding the nearest point on the polygon to p2 does not actually work in 3D, since it is possible to have components of velocity that are tangent to the polygon plane. To correct for this, you should try to find the point on the polygon that is closest to the ray that is cast from p1. This is done by finding which feature of the polygon (vertex, edge, or face) is closest to the line, and then finding the closest point on this feature to the line. "

But this is wrong.

Imagine a triangle lying flat on the ground. The triangle points west, with one very long edge going north-to-south.
To its east a little, and upwards a little is a sphere, not yet touching the ground. The sphere is moving northwards, and downwards a little also.

The sphere's radius is 1 metre.
The sphere's centre is 30 centimetres eastwards of the triangle's very long edge.
So obviously as the sphere moves northwards and downwards, it will eventually graze the triangle's very long edge.

As your note mentions, if you take the plane's intersection point (where the sphere first touches the ground), and get the edge's closest point to that, we will NOT get the real intersection point between triangle and sphere. We've got a "false closest" instead. But your note says that in order to handle this, we must find the closest point on the triangle to a line that extends from P1, and P1 is described as the point on the sphere that will first intersect the triangle's plane. Or in this case, the ground. So P1 is the bottom of the sphere.

Well, that "false closest" we just found IS the closest point on the triangle to a line extending from P1. That line never moves west at all; it's never going to get any closer to the triangle than the moment it hits the ground. But the sphere is moving northwards very, very quickly, and downwards only a little, so the point where the sphere actually grazes the triangle is actually miles and miles to the north.

For similar reasons, you can't extend that line from the sphere's centre either.
This is a similar approach to Paul Nettle's old 2000 guide (at least yours recognises the potential error though), but not a correct solution, I believe.