2
\$\begingroup\$

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...). enter image description here

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 !

\$\endgroup\$
  • \$\begingroup\$ Is there a way you can cast a ray? I am not sure which platform you are using, but typically you can throw a ray perpendicular to the surface from the player. Then you can simply call the hit point of the ray. Just find the Raycast in the platform you are using. \$\endgroup\$ – Shuvro Sarkar Mar 26 at 19:17
  • \$\begingroup\$ Google the GJK algorithm. There's lots of material on it. \$\endgroup\$ – Andrew Wilson Mar 26 at 20:49
  • 1
    \$\begingroup\$ I'll write up a detailed solution with reasoning as to why it's faster, over the weekend, if you can hold out till then. \$\endgroup\$ – Engineer Mar 27 at 9:27
  • \$\begingroup\$ ok @Engineer, I have found my way by Creating 2 triangle out of my rectangle, and calculate the closest point in both of them, and then chose the closest. But May be you have a better option. I wait a little, and then I publish my current solution with c# code \$\endgroup\$ – Ugo Hed Mar 30 at 23:01
  • \$\begingroup\$ Tim Holt's answer uses the approach I was thinking of. There are various improvements you can make on that, but the essence is that you only need square root / magnitude checks of you are in those portions of the grid that are considered corners. You also don't need 3D vector magnitude checks, but can get away with cheaper 2D magnitude checks if the rectangle is axis-aligned. \$\endgroup\$ – Engineer Mar 31 at 6:38
4
\$\begingroup\$

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

enter image description here

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

enter image description here

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ The question specifically requests the most efficient way. Answers without it are of little use. \$\endgroup\$ – Engineer Mar 27 at 6:08
  • \$\begingroup\$ @Engineer it's a very efficient solution , but if "the most efficient" part is crucial, then no one can answer this by themselves. \$\endgroup\$ – Bálint Mar 27 at 8:23
  • \$\begingroup\$ @Bálint That's just patently untrue. There are optimisations to be made, that can easily be made by a single person who thinks clearly about the problem. The normalization alone is costly and can be eliminated. \$\endgroup\$ – Engineer Mar 27 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.