Hi there,

i nailed down the closest point from box to plane successfully, now its getting much more complicated...

I have a line segment defined by a world position and two local points which may not be perpendicular.

Also i got a box defined by a world position and a local radius vector.

What must i do, to determine the closest point from the box to the line segment in 2D, including its normal vector??

Using the same approach i did for the plane does not work at all, because the normal changes when the center of the box is outside the line area. Same concept like circle vs line segment - which is much easier, because of the nature of just subtracting the radius from the projected distance.

Does someone have some ideas how to get this done?

The only way i could think of to get this solved is using separating axis theorem to project the line and the box against the following normals:

From A (Line segment): Its perpendicular from (B-A) / |(B-A)|

From B (Box): Two fixed unit vector (1.0, 0.0) and (0.0, 1.0).

In theory this should get me the smallest distance including its normal and from there it may be the same way i did with plane vs box...

What must i do, to determine the closest point from the box to the line segment in 2D, including its normal vector??

use the formula for the distance from a point to a line in 2d, do it for all four corners. the lowest result is the closest corner (or a corner on the closest side, if the line happens to be axis aligned).

Okay i now made some progress.

I used SAT to get the "least" and "most" distance with both normals. So i know now exactly what distances they are and which normal are the best.

From this i can now determine the support point(s) on the AABB...

But what is next?

I tried using the first support point to get the closest point on line segment, but this not always correct!

In case i have only one support point (Next support point has same distance as most one), it is correct.

In case i have two support points the aabb is on the full left or full right of the line segment, it is correct.

But in case for two support points where the aabb is partially inside the line segment, the closestpoint are just wrong :-(

Here are some code:

// ... SAT-Test to get normal and distance

// Get support point(s) on AABB
Vec2f[] supportPointsB = new Vec2f[2];
int supportPointBCount = getSupportPoints(localVerticesB, localVerticesB.length, new Vec2f(normal).multScalar(-1f), supportPointsB, 0);

// Get distance from line start to first support point
Vec2f lineA = new Vec2f(a.pos).add(localLineA[0]);
Vec2f closestVertex = new Vec2f(b.pos).add(supportPointsB[0]);
Vec2f lineToClosestVertex = new Vec2f(closestVertex).sub(lineA);

// Calculate percentage for closest point on line segment
float f = lineToClosestVertex.dot(localLineAB) / localLineAB.lengthSquared();
f = Math.max(Math.min(f, 1), 0);

// Get closest point on line segment
Vec2f pointOnA = new Vec2f(lineA).addMultScalar(localLineAB, f);

I made some illustrations:

Ok i got a bit closer:

Now i use support points for boths:

		// Get support points for A (Line Segment) and B (AABB)
		Vec2f[] supportPointsA = new Vec2f[2];
		Vec2f[] supportPointsB = new Vec2f[2];
		int supportPointACount = getSupportPoints(localVerticesA, localVerticesA.length, normal, supportPointsA, 0);
		int supportPointBCount = getSupportPoints(localVerticesB, localVerticesB.length, new Vec2f(normal).multScalar(-1f), supportPointsB, 0);

		// Build closest vertex for A and B in world space
		Vec2f closestVertexA = new Vec2f(a.pos).add(supportPointsA[0]);
		Vec2f closestVertexB = new Vec2f(b.pos).add(supportPointsB[0]);

		// Determine closest point on A (Line Segment)
		Vec2f pointOnA = new Vec2f();
		if (supportPointBCount > 1) {
			pointOnA.set(closestVertexA);
		} else {
			Vec2f lineToPoint = new Vec2f(closestVertexB).sub(closestVertexA);
			float f = lineToPoint.dot(localLineAB) / localLineAB.lengthSquared();
			f = Math.max(Math.min(f, 1), 0);
			pointOnA.set(closestVertexA).addMultScalar(localLineAB, f);
		}

Yeah i got it working, just using the point on the AABB´s face from the line support point was the key ;-)

See the result:

Thanks for the tips!

Bad news, i am stuck right now, my head wont work since days... i havent figured out a way to get the result i want.

I have two line segments basically, built from two support points on A (Line-Segment) and B with two support points (AABB) as well.

It works just fine, when i have a 2 vs 1 or 1 vs 1 support points, but not when i have two support points for both shapes - which means that both lines are parallel to each other.

So... how do i figure out the pair of support points which are the closest?

At the moment i have this - which is totally bogus...:

// A = Line-Segment
// B = AABB

// We have two support points on B
Vec2f worldSupportPointB0 = new Vec2f(b.pos).add(supportPointsB[0]);
Vec2f worldSupportPointB1 = new Vec2f(b.pos).add(supportPointsB[1]);

// We have 1 or 2 support points on A - but for now we use the first one
Vec2f worldSupportPointA0 = new Vec2f(a.pos).add(supportPointsA[0]);
			
// TODO: Find best pair of support points!
			
// Get line distance for both support points on B  
Vec2f lineDistance = new Vec2f(worldSupportPointB1).sub(worldSupportPointB0);
			
// Get distance from first support point on B to first support point point on A
Vec2f pointToLine = new Vec2f(worldSupportPointA0).sub(worldSupportPointB0);
// Determine the voroni region
float region = pointToLine.dot(lineDistance) / lineDistance.lengthSquared();
// Clamp that region to 0 - 1 to get a percentage
float percentage = Scalar.clamp(region);
// Calculate the closest point on line B
pointOnLine.set(worldSupportPointB0).addMultScalar(lineDistance, percentage);

// Write the target closest point on A to the array
// 
// FIXME: This is not correct - first support point on A is not always the closest point on A
pointsOnA[numPointsOnA++] = new Vec2f(worldSupportPointA0);
			
// When we are outside the line region AB,
// we need to use the distance between the current point on the line and  the first support point on A
// Also recalculate the normal and the distance - but only when we have a separation
// 
// FIXME: This is not correct - first support point on A is not always the closest point on A
if (region < 0 || region > 1 && d >= 0) {
	lineDistance.set(new Vec2f(pointOnLine).sub(worldSupportPointA0));
	normal.set(lineDistance).normalize();
	d = lineDistance.dot(normal);
}

What i want are just the closest point on A (Line-Segment)...

Please help me, i really want to nail this down.

Thanks in advance

It sounds like you're starting to implement pieces of the GJK algorithm. Though your question doesn't really say what you're doing or what you're trying to do, so I can't really help. Could you try explaining what specifically you want, and where you are stuck?

Sure... my overall goal are just to calculate the final contact point(s) on A (Line-Segment) and this is broken down in two different cases:

1. When SAT returns a separation, i just need to create a single contact point on A (Line-Segment) and recalculate the normal and distances eventually (outside the voronio region).

2. When SAT returns a penetration i need to create one or two contact points on A (Line-Segment) - this depends on the number of support points i get from A and B. And of course clipping is sometimes needed to get the proper points.

Currently first case works only when the support lines (Are these called edges?) are not parallel to each other.

Its important that i keep the separation points as well, because i use a technique called speculative contacts which projects the separation to the velocity as well to achieve a very stable simulation without using any warm starting.