캡슐 형태와 점, 구의 충돌 체크

기본적으로 캡슐은 구의 이동 궤적이라 할 수 있다. (길이가 5이고 반지름이 2인 캡슐이 있다면 0부터 5까지 반지름이 2인 원이 쭉 이동 한 궤적이 바로 캡슐인 것이다.

그러므로 캡슐은 반지름과 중심 벡터로 표현 가능한데 구와 캡슐의 충돌체크를 위해 둘의 거리를 구할 때 

캡슐의 중심 벡터 위의 점중 구의 중심 점과 가장 가까운 점을 구한다면 이 점을 중심점으로 하는 구와 구의 충돌 체크를 수행 하면 되는것이다. 

그렇다면 캡슐의 중심 벡터 위의 점 중에서 상대 구의 중심점과 가장 가까운 점은 어떻게 구할까......

구의 중심점과 캡슐의 중심 벡터의 처음 점을 빼서 벡터를 구한 후 이 벡터를 캡슐의 중심벡터의 처음점 부터 끝점에 이르는 벡터와 내적을 해주어 나오는 값을 보면 된다.

이 값이 0보다 작거나 같으면 그 두 벡터의 각도가 90~180도 이므로 캡슐의 중심벡터의 처음점이 가장 가까운 점이 되며, 이 값이 양수 일 경우 0~90도 이므로 중심벡터 중간의 어느 위치의 점 이나 중심벡터의 끝점이 가장 가까운 것이다. 그러므로 이에 관해 다시 검색을 한다.

만약 캡슐의 중심 벡터의 끝점을 자기 자신과 내적한 값이 위에서 구한 벡터보다 작거나 같은 경우 끝점이 가장 가까운 점이며 그렇지 않을 경우 그 사이의 값이 된다. 

코드를 보는것이 말보다 더 간단할 것이라 본다.

vector3 w = sphere.center() - capsule.vecOrigin();

float proj = Vec3Dot(&w, &capsule.vecDirection());

// endpoint 0 is closest point

if ( proj <= 0 )

{

     return capsule.vecOrigin();

 }

 else

 {

     float vsq = Vec3Dot(&capsule.vecDirection(), &capsule.vecDirection());

     // endpoint 1 is closest point

     if ( proj >= vsq )

         return capsule.vecOrigin() + capsuel.vecDirection();

     // else somewhere else in segment

     else

         return capsule.vecOrigin() + (proj/vsq) * capsule.vecDirection();

  }

다음은 캡슐과 캡슐, 캡슐과 구의 충돌 체크를 고민 하던 중 외국 사이트에서 발견한 문건이다. 

예제가 있어서 이해하기 한결 수월 하다.

First, we need a test for the closest point, P, on a line segment, L, to point X.

We can define L as its endpoints A and B:

L = AB

We can derive the vector, v, as that which points from A to B:

v = AB = B - A

Next, we define a vector, w, pointing from A to our point, X.

w = AX = X - A

Now, we’ve expressed the relationship between X and L in terms of vectors. By defining w and v each pointing from A, we’re working in a 2D Cartesian coordinate frame where A is the origin. Because of this, we can take advantage of some geometrical properties of vectors that will allow us to find the closest point on L to X. Specifically, we’re going to project w onto v:

proj(w,v) = dot(w,v) / dot(v,v)

where dot is the dot product:

dot(w,v) = w.x * v.x + w.y * v.y

When envisioning projection, I find it helpful to think of vectors as having a spatial domain. If you compute the dot product of 2 vectors, it represents how much 1 vector exists in the domain of the other. The dot product of a vector and itself is a value which is a maximum of that vector’s domain. Anything greater than this value exceeds the domain. The dot product of a vector and one perpendicular to it is zero, and defines the minimum of that domain (exclusive). So the domain of a vector, u, in practice, ends up being spanned by any scalar value, q, which satisfies the constraint:

0 < q <= dot(u,u)

Now let’s apply this geometric intuition to our problem of finding the closest point on a line segment. What happens if the vector w points in an opposite direction than v? dot(w,v) will be negative. Therefore w cannot exist in the domain of v. If this is the case, it should be evident that A will be the closest point on L to X. Next, let’s consider the easy-to-imagine scenario of w exceeding the maximum of v’s domain, by defining w as pointing in the same direction as v, but having twice its length. Clearly, B in this case will be the closest point to X.

Example 1. Closest point on segment to user’s mouse:

If the projection of w onto v does satisfy the domain constraint, then P will be on the segment L (and may also be A or B). So what we need is for our projection to parametrize a point on v. Because projection includes division by the squared length of the vector being projected onto, our domain becomes:

0 <= t <= 1

Where t is the projection. By clamping t to this range, and using it to scale the vector v, we find the point on v closest to X. Because we’re working in the space of A, we need to transform back to world coordinates, by adding A:

P = A + v * clamp( proj(w,v), 0, 1 )

Here’s the implementation in my geometry library (Vector2D is not a native data type), with the variables changed to match the description of the problem:

public static function closestPointLineSegment( X:Vector2D, A:Vector2D, B:Vector2D ) : Vector2D
{
    var v:Vector2D = B.minus( A );
    var w:Vector2D = X.minus( A );
    var wDotv:Number = w.dot( v );
    var t:Number = w.dot( v ) / v.dot( v );
    t = MathUtil.clamp( 0, 1, t );
    return A.plus( v.times( t ) );
}

Circle/Line Collision Test

Now that we’ve found the closest point on a line segment, L, to a point, X, determining intersection of a circle and line segment is as simple as checking whether the distance between X and P is less than the radius of the circle. Of course, X defines the center of the circle.

Example 2. Intersecting a circle and line segment:

Note that in the code below, I’m checking for distance by comparing the squared distance against the squared length of the circle’s radius. This is to avoid an expensive square root call.

public static function testCircleSegment( X:Vector2D, r:Number, A:Vector2D, B:Vector2D ) : Vector2D
{
    var P:Vector2D = closestPointLineSegment( X, A, B );
    P.minusEquals( X );
    if( P.dot( P ) <= r * r ) return P;
    return null;
}

Circle/Capsule Collision Test

Lastly, intersecting a circle and a capsule is as simple as inflating the circle’s radius by the radius of the capsule. You can see in the below example that we’re really just doing a circle/line test on an inflated circle.

Example 3. Intersecting a circle and capsule:

One extremely nice aspect of working with circles is that, not allowing the shapes to penetrate, circle’s can be touching another convex shape at a maximum of 1 point. Due in part to this convenience, the collision normal will always point from the closest point on the convex shape through the circle’s center.

public static function testCircleCapsule( X:Vector2D, r1:Number, A:Vector2D, B:Vector2D, r2:Number ) : Vector2D
{
    var P:Vector2D = closestPointLineSegment( X, A, B );
    P.minusEquals( X );
    if( P.dot( P ) <= ( r1 + r2 ) * ( r1 + r2 ) ) return P;
    return null;
}