Collision Detection Between Two 3D Disks In Space

Viewed 103

I would like to develop an algorithm for performing collision detection between two 3D disks in 3D space. Is it possible to suggest an analytical method so I can develop this program.

Thanks,

1 Answers

So each of the disks sits on top of an infinite plane, each with a normal vector and a distance to the origin. Where the two planes meet, they form a line.

This line projects the centers c1 and c2 into two points on the line p1 and p2 with perpendicular distances h1 and h2. The distance between the projected points is l.

fig1

The common line will contain the contact point if the disks are in contact. If they are not in contact, or they are interpenetrating, this point pC is the point on the line closest to both disk centers at the same time.

fig2

To find the distance t1 from p1 to pC use similar triangles to solve (t1)/h1 = (l - t1)/h2

t_1 = h_1*ell/(h_1+h_2)

From the distance t1 and the common line direction, point pC is calculated, and then the two disks are intersecting if their respective distances to their centers are equal or less than their radii.

intersect = ( distance(c_1-p_C)<=R_1 ) && ( distance(c_2-p_C)<=R_2 )

There is a special case when both circles centers lie on the common line, which also needs to be considered. The full solution in C# is

Main

    static void Main(string[] args)
    {
        var disk_1 = new Disk(Point.Origin, Vector3.UnitZ, 1);
        var disk_2 = new Disk(
            Point.Origin + Vector3.UnitY,
            Vector3.UnitY,
            0.6f);
        if (Disk.Intersect(disk_1, disk_2))
        {
            Debug.WriteLine($"Crash");
        }
    }

Disk

using System.Numerics;
public class Disk : Plane
{
    public Disk(Point center, Vector3 normal, float radius, float thickness)
        : base(center, normal)
    {
        this.Center=center;
        this.Radius=radius;
        this.Thickness = thickness;
    }

    public Point Center { get; }
    public float Radius { get; }
    public float Thickness { get; }

    public bool Containts(Point point)
    {
        if (DistanceTo(point)<= Thickness/2)
        {
            var d = (point - Center).Length();
            return d<=Radius;
        }
        return false;
    }

    public static bool Intersect(Disk disk_1, Disk disk_2)
    {
        var commonLine = Line.Meet(disk_1, disk_2);
        var p_1 = commonLine.Project(disk_1.Center);
        var p_2 = commonLine.Project(disk_2.Center);
        var ell = p_1.DistanceTo(p_2);
        var h_1 = commonLine.DistanceTo(disk_1.Center);
        var h_2 = commonLine.DistanceTo(disk_2.Center);
        if (Math.Abs(h_1+h_2)>1e-8)
        {
            var t_1 = h_1*ell/(h_1+h_2);
            var contact = p_1 - commonLine.Direction * t_1;
            return disk_1.Containts(contact) && disk_2.Containts(contact);
        }
        else
        {
            return ell <= disk_1.Radius + disk_2.Radius;
        }
    }
}

Geometry

using System.Numerics;
public class Point 
{
    public Vector3 Vector { get; }
    public float Scalar { get; }

    public Point(Vector3 position)
        : this(position, 1) { }
    public Point(Vector3 vector, float scalar)
    {
        this.Vector = vector;
        this.Scalar=scalar;
    }
    public Point(Vector4 coordinates)
        : this(new Vector3(coordinates.X, coordinates.Y, coordinates.Z), coordinates.W)
    { }
    public Point(Plane plane)
        : this(-plane.Scalar*plane.Vector, plane.Vector.LengthSquared())
    { }
    public Point(Line line)
        : this(Vector3.Cross(line.Vector, line.Moment), line.Vector.LengthSquared())
    { }

    public static implicit operator Point(Vector3 position)
        => new Point(position, 1);
    public static implicit operator Point(Vector4 coordinates)
        => new Point(coordinates);

    public static readonly Point Origin = new Point(Vector3.Zero, 1);

    public static Point Meet(Plane plane, Line line)
    {
        return new Point(
            Vector3.Cross(line.Moment, plane.Vector)+plane.Scalar*line.Vector,
            -Vector3.Dot(plane.Vector, line.Vector));
    }
    public static Point Meet(Plane plane_1, Plane plane_2, Plane plane_3)
    {
        return Meet(plane_1, Line.Meet(plane_2, plane_3));
    }

    public float Magnitude { get => Math.Abs(Scalar); }
    public Vector3 Position { get => Vector/Scalar; }
    public float DistanceTo(Point point)
        => (Scalar*point.Vector - point.Scalar*Vector).Length()/(Scalar*point.Scalar);
    public float DistanceTo(Plane plane)
        => (Vector3.Dot(plane.Vector, Vector) + Scalar*plane.Scalar)/(Scalar*plane.Vector.Length());
    public float DistanceTo(Line line)
        => (Vector3.Cross(line.Vector, Vector) + Scalar * line.Moment).Length()/(Scalar*line.Vector.Length());
    public static Point operator +(Point point, Vector3 delta)
        => new Point(point.Vector + point.Scalar*delta, point.Scalar);
    public static Vector3 operator -(Point point, Point @base)
        => point.Position - @base.Position;

}
public class Plane 
{
    public Vector3 Vector { get; }
    public float Scalar { get; }

    public Plane(Vector3 vector, float scalar)
    {
        this.Vector=vector;
        this.Scalar=scalar;
    }
    public Plane(Vector4 coordinates)
        : this(new Vector3(coordinates.X, coordinates.Y, coordinates.Z), coordinates.W)
    { }
    public Plane(Point point, Vector3 normal)
        : this(normal, -Vector3.Dot(point.Position, normal))
    { }

    public Plane(Point point)
        : this(-point.Scalar*point.Vector, point.Vector.LengthSquared())
    { }
    public Plane(Line line)
        : this(Vector3.Cross(line.Moment, line.Vector), line.Moment.LengthSquared())
    { }
    public static implicit operator Plane(Vector4 coordinates)
        => new Plane(coordinates);

    public static Plane Join(Point point, Line line)
    {
        return new Plane(
            Vector3.Cross(line.Vector, point.Position) + line.Moment,
            -Vector3.Dot(point.Position, line.Moment));
    }
    public static Plane Join(Point point_1, Point point_2, Point point_3)
    {
        return Join(point_1, Line.Join(point_2, point_3));
    }
    public float Magnitude { get => Vector.Length(); }
    public Vector3 Normal { get => Vector3.Normalize(Vector); }
    public float Offset { get => -Scalar/Magnitude; }
    public Vector3 Position
    {
        get => Normal*Offset;
    }
    public float DistanceTo(Point point)
        => point.DistanceTo(this);

    public Point Project(Point point)
    {
        float t = Vector3.Dot(Normal, point.Position)-Offset;
        return point.Position - Normal*t;
    }
}
public class Line 
{
    public Vector3 Vector { get; }
    public Vector3 Moment { get; }

    public Line(Vector3 vector, Vector3 moment)
    {
        this.Vector=vector;
        this.Moment=moment;
    }

    public static Line Ray(Point point, Vector3 direction)
    {
        return new Line(direction,
            Vector3.Cross(point.Position, direction));
    }

    public static Line Join(Point point_1, Point point_2)
    {
        return new Line(
            point_2.Position-point_1.Position,
            Vector3.Cross(point_1.Position, point_2.Position));
    }
    public static Line Meet(Plane plane_1, Plane plane_2)
    {
        return new Line(
            Vector3.Cross(plane_1.Vector, plane_2.Vector),
            plane_2.Vector*plane_1.Scalar-plane_1.Vector*plane_2.Scalar);
    }
    public Point Along(float travel)
        => Position.Position + Direction * travel;
    public float Magnitude { get => Vector.Length(); }
    public Vector3 Direction { get => Vector3.Normalize(Vector); }
    public Point Position
    {
        get => new Point(this);
    }
    public float DistanceTo(Point point)
        => point.DistanceTo(this);
    public float DistanceTo(Line line)
        => (Vector3.Dot(Vector, line.Moment) + Vector3.Dot(line.Vector, Moment))/Vector3.Cross(Vector, line.Vector).Length();

    public Point Project(Point point)
    {
        return Along(Vector3.Dot(Direction, point.Position-Position.Position));
    }
}

Math above is based on Foundations of Game Engine Development, by Eric Lengyel.

Updates

  • Added thickness to the disk properties, and use it to check if a point is contained with a disk.
  • Link to MATALB code Class definitions for Point3.m, Plane3.m and Line3.m I wrote a long time ago. There might be some things missing, but it might give you a good starting point. Nothing specific about disks just the framework for geometry with homogeneous coordinates.
Related