The code below is from book Real-Time Collection Detection ch5.cpp file

Some of them I don't know where it come from.

float denom = a*e-b*b;

and

(b*f - c*e) / denom

what does this mean?I know a is square length of d1,e is square length of d2,b is d1 projection on d2,

but what does a*e-b*b means?where this guy come from,for what reason?any rule or fomular related??

Can somebody point me the direction or something to figure this out.Thanks

// Computes closest points C1 and C2 of S1(s)=P1+s*(Q1-P1) and
// S2(t)=P2+t*(Q2-P2), returning s and t. Function result is squared
// distance between between S1(s) and S2(t)
float ClosestPtSegmentSegment(Point p1, Point q1, Point p2, Point q2,
                              float &s, float &t, Point &c1, Point &c2)
{
    Vector d1 = q1 - p1; // Direction vector of segment S1
    Vector d2 = q2 - p2; // Direction vector of segment S2
    Vector r = p1 - p2;
    float a = Dot(d1, d1); // Squared length of segment S1, always nonnegative
    float e = Dot(d2, d2); // Squared length of segment S2, always nonnegative
    float f = Dot(d2, r);

    // Check if either or both segments degenerate into points
    if (a <= EPSILON && e <= EPSILON) {
        // Both segments degenerate into points
        s = t = 0.0f;
        c1 = p1;
        c2 = p2;
        return Dot(c1 - c2, c1 - c2);
    }
    if (a <= EPSILON) {
        // First segment degenerates into a point
        s = 0.0f;
        t = f / e; // s = 0 => t = (b*s + f) / e = f / e
        t = Clamp(t, 0.0f, 1.0f);
    } else {
        float c = Dot(d1, r);
        if (e <= EPSILON) {
            // Second segment degenerates into a point
            t = 0.0f;
            s = Clamp(-c / a, 0.0f, 1.0f); // t = 0 => s = (b*t - c) / a = -c / a
        } else {
            // The general nondegenerate case starts here
            float b = Dot(d1, d2);
            float denom = a*e-b*b; // Always nonnegative,======================================Here is the one ======================================

            // If segments not parallel, compute closest point on L1 to L2, and
            // clamp to segment S1. Else pick arbitrary s (here 0)
            if (denom != 0.0f) {
                s = Clamp((b*f - c*e) / denom, 0.0f, 1.0f);//======================================Here is the other one ======================================
            } else s = 0.0f;

            // Compute point on L2 closest to S1(s) using
            // t = Dot((P1+D1*s)-P2,D2) / Dot(D2,D2) = (b*s + f) / e
            t = (b*s + f) / e;

            // If t in [0,1] done. Else clamp t, recompute s for the new value
            // of t using s = Dot((P2+D2*t)-P1,D1) / Dot(D1,D1)= (t*b - c) / a
            // and clamp s to [0, 1]
            if (t < 0.0f) {
                t = 0.0f;
                s = Clamp(-c / a, 0.0f, 1.0f);
            } else if (t > 1.0f) {
                t = 1.0f;
                s = Clamp((b - c) / a, 0.0f, 1.0f);
            }
        }
    }

    c1 = p1 + d1 * s;
    c2 = p2 + d2 * t;
    return Dot(c1 - c2, c1 - c2);
}

I have no idea. I consider half that book "black magic". I consider it a major accomplishment any time I understand any of it. To say that it is "math intensive" is an understatement. He specifically says right before that code "Alternatively, Gaussian elimination can be used on the 2 x 2 system of linear equations to solve for the one unknown in terms of the other." Yep, over my head.

I am curious when you would need to know the closest points of two line segments?

Anyway, for anyone trying to help it's on page 148 section 5.1.9 "Closest Points of Two Line Segments" of Christer Ericson's book "Real Time Collision Detection". This book is a must have for the serious game programmer even if I don't understand 90% of it. Just having code you can copy and paste is a good start. Although it's probably more for someone doing low level engine type programming rather than just using an engine where a lot of this code is maybe already part of the engine.

tracegame,

It is the determinant of the matrix (A) you build to solve the linear system generated by requiring the closest points between two *lines*. If it is zero then the lines are paralell. Example:

Vec3 E1 = Q1 - P1;
Vec3 E2 = Q2 - P2;
Vec3 E3 = P1 - P2;

Mat22 A;
A.x.x = Dot(E1, E1);
A.x.y = Dot(E2, E1);
A.y.x = -Dot(E1, E2);
A.y.y = -Dot(E2, E2);

Vec2 b;
b.x = -Dot(E1, E3);
b.y = -Dot(E2, E3);

Vec2 x = A.Solve(b);

Oh, here is the full logic assuming two segments P1-Q1 and P2-Q2 are healthy. C1 and C2 are the closest points.

void ClosestPointSegmentAndSegment(Vec3* C1, Vec3* C2,
	const Vec3& P1, const Vec3& Q1,
	const Vec3& P2, const Vec3& Q2)
{
	Vec3 E1 = Q1 - P1;
	Vec3 E2 = Q2 - P2;
	Vec3 E3 = P1 - P2;

	Mat22 A;
	A.x.x = Dot(E1, E1);
	A.x.y = Dot(E2, E1);
	A.y.x = -Dot(E1, E2);
	A.y.y = -Dot(E2, E2);

	Vec2 b;
	b.x = -Dot(E1, E3);
	b.y = -Dot(E2, E3);

	Vec2 x = A.Solve(b);

	Vec3 V1, V2;
	if (x.x < 0.0f)
	{
		V1 = P1;
	}
	else if (x.x > 1.0f)
	{
		V1 = Q1;
	}
	else
	{
		V1 = P1 + x.x * E1;
	}

	// CP on E2 to V1
	V2 = ClosestPointOnSegment(V1, P2, Q2);
	// CP on E1 to V2
	V1 = ClosestPointOnSegment(V2, P1, Q1);

	*C1 = V1;
	*C2 = V2;
}

HTH,

Irlan

Thank you for your great help,now I understand. :D

I don't recommend Christer's formula: (b*f - c*e) / denom

In practice I have recieved negative squared distance from very small line segments, which resulted in NaNs being passed around if the result is given to a sqrt function. I wrote an article about the details here: http://www.randygaul.net/2014/07/23/distance-point-to-line-segment/. Usually drawings of vectors and deriving equations piece by piece helps to make sense of formulas.

Yeah, the ClosestPointOnSegment function must use barycentric coordinates avoiding the division, and hopefully return a correct result even when the segment degenerates into a point. Example:

void Barycentric(float out[3], const Vec3& A, const Vec3& B, const Vec3& Q)
{
	Vec3 AB = B - A;
	Vec3 QA = A - Q;
	Vec3 QB = B - Q;
	out[0] = Dot(QB, AB);
	out[1] = -Dot(QA, AB);
	out[2] = out[0] + out[1]; // This stores the divisor. Note: Not using Dot(AB, AB)!
}

Vec3 ClosestPointOnSegment(const Vec3& P, 
	const Vec3& A, const Vec3& B)
{
	float wAB[3];
	Barycentric(wAB, A, B, P);

	if (wAB[1] <= 0.0f)
	{
		return A;
	}

	if (wAB[0] <= 0.0f)
	{
		return B;
	}
	
	ASSERT(wAB[0] > 0.0f && wAB[1] > 0.0f && wAB[2] > 0.0f);
	float32 s = 1.0f / wAB[2];
	float32 lambda1 = s * wAB[0];
	float32 lambda2 = s * wAB[1];
	return lambda1 * A + lambda2 * B;
}

Randy, what about the closest points between two *lines*, which is the case present in this discussion. Are you aware of a more numerically friendly solver?

I haven't taken the time to write down functions specifically for two lines, but it should be very similar. I recall a strategy that works is to make sure whatever expression is returned cannot be negative when dealing with functions that return distance or squared distance (e.g. by returning a dot product of a vector with itself). For example I took Christer's line in question and derived my own version: e = pa - n * (c / Dot( n, n )). The division cannot be 0 and no NaNs should arise.

Your function should be totally fine since the division is predicated by the assert. Also your return value is a point, not a scalar, so nobody will know if your point is slightly outside of the line segment since users will likely be using a tolerance anyway. Christer's code had no such safety mechanism or even an explanation of potential problems. Edit: Which is unfortunate since all the rest of his code I've ever used seems totally robust.

I used this approach as well for the point vs. line test and am aware of it.

For a correct segments test there are some performance penalties. For example, if the segments are parallel and not normalized then we need to take their length into account for this test to pass obviously. Fortunately, people recommend to run them only on healthy segments (e.g. capsules) as we can enforce this off-line.

Yeah, this function is the one we end up using on GJK as well and probably the one used out there on-line.

The book has warnings so I don't thing there is any problem. He skipped over probably because for more complex tests such as triangle vs. point the degeneracy tests (e.g. linear dependence) easely increase the code size, but all this is warned if you take a look again.

BBeck,

The closest points between two line segments is usefull for detecting when two capsules overlap and ray-casting against them in the absence of a full general GJK algorithm. It is faster as well and we can check for non-degenerate simplexes more easily than in GJK.

I disagree the book is black magic. However, I agree that some of Christer's simplification might be confusing, but is not recommended to simplify before understanding the general case obviously. (I guess is because his code samples were performance-oriented?). Christer's book is excelent and used as a reference for collision detection in most game studios today.

Ah. Thank you. Good to know.

When I said "Black Magic" I was trying to be funny and throw out some self deprecating humor regarding my lack of understanding the math. There are parts of the book I understand and I think that it's an awesome book. I highly recommend it for anyone doing serious 3D game programming. Just the Oriented Bound Box collision algorithm is worth the price of purchase by itself. My lack of understanding the math is largely just me not taking the time to understand it. I have had so many other things to work on. But it is pretty much the book on collision detection. That's why it's on my shelf. And I think it is one of the most important game programming books on my shelf even if I struggle a little with some of the math in it. A lot of it is just that the math is new to me and I need to slowly work through it line by line and have not had the time to do that with more than a few of the algorithms. But you don't necessarily have to understand how the code in the book works to use it.

Anyway, I did not mean to disparage the book in any way. It's one of my favorite game programming books.