Sign in to follow this  

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

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 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:

 

sat_closest_correct_or_not.png

Share this post


Link to post
Share on other sites

Ok i got a bit closer:

 

sat_better_but_still_not_correct.png

 

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

Edited by Finalspace

Share this post


Link to post
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
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

Edited by Finalspace

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
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

 

Meh... i thought i would get around GJK somehow, but seems i wont...

 

But before i use GJK as my last resort, i will try something else - using SAT again to project the support points against the perpendicular axis, to get the interval between both shapes and using this to determine if inside, left outside, right outside... something like that.

 

If this wont work, i will just implement GJK - i already know the theory behind.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this