Most efficient way to get the closest point to a 3d rectangle

Question

I have a 3D rectangle, with 4 points (x,y,z) And I have a player, who can be anywere (inside the rectangle, outside, not even in the plane, in the corner...).

I would like to get the closest point in that rectangle, to my player. The most efficient way

I have already a struct who can say the closest point to a line:

public struct ExtLine
{
    public readonly Vector3 A;
    public readonly Vector3 B;
    public readonly Vector3 Delta;
    public bool noGravityBorders;//if I want to return true only if player is in the boundary

    public ExtLine(Vector3 a, Vector3 b, bool _noGravityBorders)
    {
        A = a;
        B = b;
        Delta = b - a;
        noGravityBorders = _noGravityBorders;
    }

    public Vector3 PointAt(double t) => A + (float)t * Delta;
    public double LengthSquared => Delta.sqrMagnitude;
    public double LengthLine => Delta.magnitude;

    public Vector3 ClosestPointTo(Vector3 p)
    {
        //The normalized "distance" from a to your closest point 
        double distance = Project(p); 

        if (distance < 0)     //Check if P projection is over vectorAB     
        {
            if (noGravityBorders)
                return (ExtUtilityFunction.GetNullVector()); //an extention who give me an "null vector", not useful here
            return A;
        }
        else if (distance > 1)
        {
            if (noGravityBorders)
                return (ExtUtilityFunction.GetNullVector());
            return B;
        }
        else
        {
            return A + Delta * (float)distance;
        }
    }

    public double GetLenght()
    {
        return (LengthLine);
    }

    public double Project(Vector3 p) => Vector3.DotProduct(Delta, p - A) / LengthSquared;
}

And a struct who can say the closest point to a plane:

public struct ExtPlane
{
    public Vector3 Point;
    public Vector3 Direction;

    public ExtPlane(Vector3 point, Vector3 direction)
    {
        Point = point;
        Direction = direction;
    }

    public bool IsAbove(Vector3 q) => Vector3.DotProduct(q - Point, Direction) > 0;

    public Vector3 Project(Vector3 randomPointInPlane, Vector3 normalPlane, Vector3 pointToProject)
    {
        Vector3 v = pointToProject - randomPointInPlane;
        Vector3 d = Vector3.Project(v, normalPlane.normalized);
        Vector3 projectedPoint = pointToProject - d;
        return (projectedPoint);
    }
}

How can I manage to find my point ? Thanks for help !

Answer 1

This is actually a pretty simple problem if you first rotate the rectangle so it lies flat and at right angles on one plane, and also apply the same rotation to the player location. Now, everything can be done with Cartesian coordinates to determine the closest point. In Cartesian space, it's trivial to find the point on the rectangle, then reverse the rotation to get your final answer.

Here's a basic illustration of how this works...

Let's say you rotate the rectangle so it lies flat on the Z plane, so you're working just with X and Y. Given that and looking only at the player location in X and Y (ignoring Z), the player will either be inside the rectangle, or outside the rectangle.

If inside, the point on the rectangle is simply the player X, Y coordinates on the rectangle.

If outside, it's also surprisingly trivial as well. Rather than answer the outside case, I'm going to point you to https://math.stackexchange.com/questions/356792/how-to-find-nearest-point-on-line-of-rectangle-from-anywhere which has a nice, extremely simple answer to that problem.

Here's a key illustration from the above linked Math stack answer, which shows how for a point outside the rectangle, it's either a simple line to an edge, or one of the corners, depending on the point location...

Now with the closest point on the rectangle located in Cartesian coordinates, you reverse the rotation on that point to find the desired point on the rectangle in 3D space.

The only thing I've left you as a challenge is to compute the rotational transformation needed for your rectangle. I'm going to say though that defining a plane (to work out the needed rotation) with 4 points is going to be a problem, because you'll never have enough precision to ever have 4 points truly lying on a flat plane (unless it's already flat on X, Y, or Z). The best thing would be for you to pick 3 of the points on the rectangle to define a triangle, then compute the normal from them (and from there the rotation).

Answer 2

Let \$\vec{n}\$ be a normalized normal vector of the plane (say, the cross-product of \$\vec{DA}\$ and \$\vec{DC}\$ divided by its length).

Let \$Q = P - (\vec{DP}\cdot \vec{n}) \vec{n}\$. (I.e., \$Q\$ is the projection of \$P\$ into the plane of \$ABCD\$. You seem to have a function for this already. The only missing part is to make sure that \$Q\$ belongs to the rectangle.)

Let \$x=(\vec{DQ}\cdot \vec{DC})/|DC|^2\$ and \$y=(\vec{DQ}\cdot \vec{DA})/|DA|^2\$. (That means, we find the place of \$Q\$ in a coordinate system in the rectangle that has its origin in \$D\$ and \$(1,0)\$ and \$(0,1)\$ in \$C\$ and \$A\$, respectively.) If \$x>1\$ or \$x<0\$, set \$x=1\$ or \$x=0\$, respectively; the same for \$y\$.

The point \$D + x\vec{DC} + y\vec{DA}\$ is the point you are looking for.

(Admittedly, this answer still leaves open the question of "most efficient way".)

Edit: In order to make this somewhat more efficient: The first step is unnecessary (the following steps would ignore the component perpendicular to the plane anyway); and it is possible to compute the projections (probably the most expensive parts of the algorithm) only when necessary.

Let \$a= \vec{DP}\cdot \vec{DC}\$. If \$a<0\$, let \$\vec{x}=\vec{0}\$. Else if \$a>l_c\$, where \$l_c=\vec{DC}\cdot\vec{DC}\$, let \$\vec{x}=\vec{DC}\$. Else let \$\vec{x}\$ be the projection of \$\vec{DP}\$ in the direction of \$\vec{DC}\$ (like above, e.g. as \$\frac{a}{l_c}\, \vec{DC}\$.).

Let \$b= \vec{DP}\cdot \vec{DA}\$. If \$b<0\$, let \$\vec{y}=\vec{0}\$. Else if \$b>\vec{DA}\cdot\vec{DA}\$, let \$\vec{y}=\vec{DA}\$. Else let \$\vec{y}\$ be the projection of \$\vec{DP}\$ in the direction of \$\vec{DA}\$.

The solution is \$D+\vec{x}+\vec{y}\$.

While this is certainly more efficient than my first attempt (source: count the operations of each type), on which it is based, I still cannot say how close it is to the 'most efficient' algorithm (if such exists) - and am looking forward to reading another answer that addresses this question (ideally comparing with all other possible algorithms and not only examples given here).