How to get the closest point from a aabb to a line segment in 2D

This topic is 1133 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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...

Share on other sites

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).

Share on other sites

First make sure the AABB is on one side of the plane or the other. Then compute the support point of the AABB along the normal of the plane, and clamp this point within your lane segment.

If the AABB overlaps the line segments plane, then make sure the segment doesn't intersect the box. The closest point on the AABB can now be any point on the surface, and some other algorithm can be run. Personally I'd just use support points on all the potential axes of separation and call it good enough. Keep the point with the minimum projected signed distance.

Share on other sites

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 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);



Share on other sites

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

// 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);
}


Edited by Finalspace

Share on other sites

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!

Share on other sites

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

// We have 1 or 2 support points on A - but for now we use the first one

// 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

// 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)...

Edited by Finalspace

Share on other sites

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?

Share on other sites

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.

Edited by Finalspace

Share on other sites

Okay gotcha! Let me say that you should probably use Erin Catto's 2D GJK algorithm he posted up online as open source if you're going to be writing this kind of code, it was from like GDC ~2009 (or you can reference it to write your own). If you try to write a custom SAT-based routine you will end up recreating pieces of the GJK algorithm in your routine. Then the next time you might want to implement AABB vs capsule, or some other configuration and will have to re-write pieces of GJK yet again. You can see where this is going.

So lets, see... Try this algorithm out:

1. Run GJK on A and B to find witness points (closest point pair)
2. exit if witness points are unique (no intersection)
3. else find axis of minimum penetration on AABB (dot segment endpoints with each face)
4. clip segment to this face to find contact points (result of clip is contacts)

Unless I forgot some edge case this should work for penetrating configurations. Should be able to use the witness points in the non-penetrating case to track separation over time.

Edited by Randy Gaul

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 13
• 10
• 12
• 10
• 13
• Forum Statistics

• Total Topics
632998
• Total Posts
3009808
• Who's Online (See full list)

There are no registered users currently online

×