Jump to content

  • Log In with Google      Sign In   
  • Create Account

Circle vs Line Segment collision


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 Ntwiles   Members   -  Reputation: 144

Like
0Likes
Like

Posted 28 September 2013 - 12:42 PM

I'm trying to implement a method to check if a circle, given a certain displacement vector, will collide with a line segment. Though I don't follow some of the math, I've managed already to get a working method to determine if a circle will collide with an infinite line, defined by a line segment:

        public static CollisionData CircleVSLine(Vector2 position, float radius, VectorX displacement, LineSegment line)
        {
            CollisionData data = new CollisionData();

            Vector2 line_to_circle;

            VectorX line_vector = new VectorX(line.Size);
            Vector2 n = line_vector.Normal;

            //Shortest distance from circle's center to line - before vector is applied 
            line_to_circle = line.Position1 - position;
            float d1 = Math.Abs(VectorX.DotProduct(line_to_circle,n));

            //After vector is applied
            line_to_circle = line.Position1 - position - displacement.Components;
            float d2 = Math.Abs(VectorX.DotProduct(line_to_circle, n));

            float t = (radius - d1) / (d2 - d1);

            if (Math.Abs(d2) < radius)
            {
                data.Collides = true;
                data.CollisionPoint = position + (displacement * t);
            }

            return data;
        }

And below is my attempt to check for collisions on line segments:

        public static CollisionData CircleVSLineSegment(Vector2 position, float radius, VectorX displacement, LineSegment line)
        {
            VectorX line_vector = new VectorX(line.Size);
            //First check if collision happened on entire length of line
            CollisionData data = CircleVSLine(position,radius,displacement,line);

            //Early out
            if (!data.Collides) { return data; }

            /* Next, get the vector form Position1 to data.CollisionPoint. If they are going in the same general direction,
             * they will have a positive Dot Product, if they aren't, then the collision point must be BEHIND line_vector 
             * (I.E., not ON the vector, and not truly colliding.)
             * http://hub.tutsplus.com/tutorials/quick-tip-collision-detection-between-a-circle-and-a-line-segment--active-10632 */

            VectorX start_to_circle = new VectorX(position - line.Position1);
            float dot_start = VectorX.DotProduct(line_vector.Components, start_to_circle.Components);

            //Early out
            if (dot_start < 0) { data.Collides = false; return data; }

            if (line.Position1.X == 48 + 16)
            {
                //Debugger.Break();
                GameStatus.Pause();
            }
            if (position.Y < line.Position1.Y && line.Position1.X == 48+16) Debugger.Break();

            /* Next, we make sure the collision point doesn't happen after line_vector has ended. If it does, the projection
             * of start_to_circle onto line_vector will exceed the length of line_vector. */

            float projection = start_to_circle.ScalarProjection(line_vector);
            if (projection > line_vector.Length) { data.Collides = false; }

            return data;
        }

As you can see, I link to a tutorial which attempts to explain how the test is done. The algorithm treats the line segment as a vector (which I know is strange), and first tests to see if the circle is actually colliding with the line defined by our line segment BEFORE the start of said line segment.  It then tests in an entirely different way to see if the circle collides with the line at a point AFTER the vector ends. If it doesn't collide before the line segment, and it doesn't collide after the line segment, it collides on the line segment. 

 

The logic of the first half of the test is that if two vectors (the vector defined by our line segment, and the vector from the start of that line segment to the starting position of our circle) have generally opposite directions, then the circle MUST be behind the start of our line segment vector, which makes sense to me.  The test to check if the two vectors ARE going in the same direction though, gives lots of false positives. This is my big issue. I haven't even got to the second half of the algorithm, which doesn't seem to be working either.

 

Can anyone help me wrap my mind around this? I'd like to repeat that I do have a working test for circles vs infinite lines, which I don't want to discard and which I feel will provide a lot of the data needed to make the more precise circle vs line segment test. Any input would be really appreciated.



Sponsor:

#2 Muzzy A   Members   -  Reputation: 689

Like
2Likes
Like

Posted 28 September 2013 - 04:02 PM

struct Segment
{
    Vector3 start;
    Vector3 end;
};
struct Sphere
{
    Vector3 center;
    float fRadius;
};

This code will find the closest point to the sphere that is on the line segment.

Vector3 point = sphere.center;
 
// Get the direction of the line segment from start to end
Vector3 line = segment.end - segment.start;
float length = Math::Length(line); // The length of the line
line /= length; // Normalize
 
// The Vector from the center of the sphere to the start of the line seg
Vector3 toStart = segment.start - point;
 
// How far up the line the closest point is
float dist = Math::DotProduct(toStart,line);
 
// ensure that the closest point is on the line segment
if( dist < 0 )
dist = 0;
else if(dist > length)
dist = length;
 
// Calculate the closest point
ClosestPoint = segment.start + line * dist;

Now you have the closest point, just do a simple radius check

Vector3 toPoint = sphere.center - ClosestPoint;
 
// For optimization you can use the square distances
float dist = dot_product( toPoint,toPoint ); // Equivelant to LengthSqu()
 
if( dist <= sphere.fRadius*sphere.fRadius )
    // There is a collision

Edited by Muzzy A, 28 September 2013 - 04:04 PM.


#3 raigan   Members   -  Reputation: 744

Like
1Likes
Like

Posted 28 September 2013 - 04:09 PM

Here is OTOH pseudocode for a distance-from-point-to-lineseg query: 

//given seg defined as points p0,p1, return distance to query point qp
float getDistanceToSeg(float2 p0, float2 p1, float2 qp) 
{
   float2 p0p1 = p1 - p0;
   float2 p0qp = qp - p0;
	
   float len2 = dot(p0p1, p0p1);
	
   //t is a number in [0,1] describing 
   //the closest point on the lineseg as a blend of endpoints.. 
   float t = max(0, min(len2, dot(p0p1, p0qp))) / len2;
	
   //cp is the position (i.e actual coordinates) of the closest point on the seg
   float2 cp = p0 + t*p0p1;
	
   return len(cp - qp);
}

Use the circle's center position as the query point; subtract the circle's radius from the reported distance to get the circle-to-lineseg distance (negative means the shapes overlap). cp is the closest point on the lineseg; this along with the signed distance should be all you need for collision response (i.e collision normal from circle's POV is the vector (cp - qp)).

 

(Note that you can use the same code for circle-vs-capsule (i.e if you want to inflate the lineseg/give it a radius too))

 

Sorry if this doesn't make sense, I don't have time for a better explanation right now! sad.png

 

Raigan

p.s - you *might* be able to use the same code for circle-vs-infinite-line, if you don't clamp t to (0,1), but I think there are likely better (more direct/simpler) methods for solving that problem.


Edited by raigan, 28 September 2013 - 05:07 PM.


#4 l0k0   Members   -  Reputation: 278

Like
1Likes
Like

Posted 29 September 2013 - 10:53 PM

Treat it like a circle against an infinite line first.  Validate the t value of the intersection between the circle and the infinite line is valid first [0 - 1].  Then, take the scalar projection of this intersection pt onto p0p1 and validate that the scalar projection is also valid [0 - 1].  Give this a try:

bool TestSweptCircleLine(const Vector2& c, const float r, const Vector2& d, const Vector2& p0, const Vector2& p1, float &outT) {
    Vector2 p0p1 = p1 - p0;
    // we have this annoying case first, where the circle is *already* intersecting the line segment so check for that first.  In this case, t would be 0.0f.  As for intersection points technically you have 2, but your "solver" might just want to use c
    Vector2 closestPointOnLineSegment = p0 + p0p1 * Saturate(Dot(c - p0, p0p1) / Dot(p0p1, p0p1));
    if (DistSquared(closestPointOnLineSegment, c) <= r * r)
    {
       outT = 0.0f;
       return true;
    }
    Vector2 p0p1Perp = RightPerp(p0p1);
    // can avoid normalisation here, but lets keep this simpler for now
    Vector2 pn = Normalise(p0p1Perp);
    float   pd = -Dot(pn, p0);
    // system of equations is:
    // dot(pn, X) = -pd +- r (X is any point that is +r or -r distance away from the infinite line)
    // c + d * t = X (t is in the 0 to 1 range inclusive, X in this case is again the center of the circle when it intersects the infinite line (not necessarily the segment))
    // using substitution and solving for T
    float distanceLineToCenterOfCircle = Dot(pn, c) + pd; // just line signed plane distance
    float signSideOfLine = Sign(distanceLineToCenterOfCircle );
    // if our sign is positive, then our system of equations is + R
    // if not our system of equations is - R
    float modR = signSideOfLine * r;
    outT = (((-pd + modR) - Dot(pn, c)) / (Dot(pn, d)));
    // now validate t and s
    if (outT >= 0.0f && outT <= 1.0f)
    {
        // alright, our swept circle is intersecting the infinite line
        // now validate that this intersection is in the line segment
        // range too
        Vector2 ptCenterOfCircleWhenIntersecting = c + d * outT;
        Vector2 ptOnLineWhenIntersecting = ptCenterOfCircleWhenIntersecting + pn * -modR;
        // find the scalar projection of ptOnLineWhenIntersecting.  If it is between 0 and 1 inclusive we have an intersection
        float s = Dot(ptOnLineWhenIntersecting - p0, p0p1) / Dot(p0p1, p0p1);
        if (s >= 0.0f && s <= 1.0f)
        {
            return true;
        }
    }
    return false;
}


Edited by l0k0, 29 September 2013 - 10:58 PM.

<shameless blog plug>
A Floating Point
</shameless blog plug>

#5 Ntwiles   Members   -  Reputation: 144

Like
0Likes
Like

Posted 02 October 2013 - 06:29 PM

Thanks for the great replies! I0k0, your function is the only one doing a sweep test, which was my goal. I have a couple questions on some of your values.

 

d - Is this the diameter of the circle?

outT - I have no idea what this is, can you explain?

Saturate() - I've read that saturation arithmetic constrains the result of any mathematical operation to a range of values. Is this what you're doing? If so, what are you constraining the values to? 0-1?



#6 l0k0   Members   -  Reputation: 278

Like
0Likes
Like

Posted 02 October 2013 - 09:42 PM

Thanks for the great replies! I0k0, your function is the only one doing a sweep test, which was my goal. I have a couple questions on some of your values.

 

d - Is this the diameter of the circle?

outT - I have no idea what this is, can you explain?

Saturate() - I've read that saturation arithmetic constrains the result of any mathematical operation to a range of values. Is this what you're doing? If so, what are you constraining the values to? 0-1?

Hi

d: d is the sweep vector.  So if your swept circle has a velocity of {2, 0} for the given frame, you'd pass that vector for d.

outT: The multiplier of d that gives you the point at the center of the circle when the circle first intersects the line: X = c + d * t.  It's useful for getting a percentage of your sweep that contact was made.  It's very useful for things like raycasts.  Perhaps for your needs at a higher level just a boolean test is needed, but the way I'm doing the test you have to calculate this t value anyways.

Saturate: saturate is equivalent to Clamp(someVal, 0.0, 1.0)

 

Hope that helps.


Edited by l0k0, 02 October 2013 - 09:52 PM.

<shameless blog plug>
A Floating Point
</shameless blog plug>

#7 Ntwiles   Members   -  Reputation: 144

Like
0Likes
Like

Posted 03 October 2013 - 06:35 AM

Ahh gotcha! So it looks like to me your value of outT is the same as my data.Ratio in this method:
        public static CollisionData CircleVSLine(Vector2 position, float radius, VectorX displacement, LineSegment line)
        {
            CollisionData data = new CollisionData();
 
            Vector2 line_to_circle;
 
            VectorX line_vector = new VectorX(line.Size);
            Vector2 n = line_vector.Normal;
 
            //Shortest distance from circle's center to line - before vector is applied 
            line_to_circle = line.Position1 - position;
            float d1 = Math.Abs(VectorX.DotProduct(line_to_circle, n));
 
            //After vector is applied
            line_to_circle = line.Position1 - position - displacement.Components;
            float d2 = Math.Abs(VectorX.DotProduct(line_to_circle, n));
 
            data.Ratio = (radius - d1) / (d2 - d1);
 
            if (Math.Abs(d2) < radius)
            {
                data.Collides = true;
                data.CollisionPoint = position + (displacement * data.Ratio);
            }
 
            return data;
        }
The math looks to be very much similar, but it looks to me like you're applying some sort of coefficient (I'm guessing Sign() returns either -1 or 1?) based on the sign of the distance, where I'm just storing the absolute value of the distance. Will I be safe continuing to do it that way?

Edited by Ntwiles, 03 October 2013 - 06:35 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS