La façon la plus rapide pour calculer le point de triangle distance en 3D?

Il existe différentes approches pour trouver la distance d'un point P0 à un triangle P1,P2,P3.

1. La méthode 3D.
   Projet le point sur le plan de la triangle et utiliser les coordonnées barycentriques ou d'un autre moyen de trouver le point le plus proche dans le triangle. La distance est trouvé dans la manière habituelle.

2. 2D par la méthode. Appliquer une translation/rotation pour les points de sorte que P1 est sur l'origine, la P2 est sur l'axe des z, P3 dans le plan yz. La Projection est le point P0 est trivial (la négligence de la coordonnée x). Il en résulte un problème 2D. À l'aide de la pointe équation, il est possible de déterminer le sommet le plus proche ou le bord du triangle. Calcul de la distance est alors facile comme bonjour.

Ce papier compare les performances des deux, avec la 2D méthode gagnante.

OriginalL'auteur Il-Bhima

Je vais conduire avec mes résultats de test.

Le cas de test de code et la mise en œuvre est en C#

    public void ClosestPointToShouldWork()
    {
        var r = new Random(0);
        double next() => r.NextDouble() * 5 - 1;
        var t = new Triangle(new Vector3(0,0,0), new Vector3(3.5,2,0), new Vector3(3,0.0,0));

        DrawTriangle(t);

        var hash = new Vector3( 0, 0, 0 );
        for (int i = 0; i < 800; i++)
        {
            var pt = new Vector3( next(), next(), 0 );
            var pc = t.ClosestPointTo( pt );
            hash += pc;

            DrawLine(pc,pt);
        }

        //Test the hash
        //If it doesn't match then eyeball the visualization
        //and see what has gone wrong

        hash.ShouldBeApproximately( new Vector3(1496.28118561104,618.196568578824,0),1e-5  );

    }

La mise en œuvre du code est délicat comme j'ai un certain nombre de classes du framework. J'espère que vous pouvez traiter cette pseudo-code et sortez de l'algorithme. Le raw types de vecteurs sont de https://www.nuget.org/packages/System.DoubleNumerics/.

Noter que certaines propriétés du Triangle peut être mis en cache pour améliorer les performances.

Noter que pour le retour au point le plus proche ne nécessite pas de racines carrées et ne nécessite pas de transformer le problème de la 2D.

L'algorithme d'abord rapidement teste si le point de test est plus proche d'un point de fin de la région. Si cela n'est pas concluant, il teste ensuite le bord externe des régions, un par un. Si les tests échouent, alors le point est à l'intérieur du triangle. Notez que pour les sélectionnés au hasard des points de mesure à partir du triangle, il est plus probable que le point le plus proche sera un point d'angle du triangle.

public class Triangle
{
    public Vector3 A => EdgeAb.A;
    public Vector3 B => EdgeBc.A;
    public Vector3 C => EdgeCa.A;

    public readonly Edge3 EdgeAb;
    public readonly Edge3 EdgeBc;
    public readonly Edge3 EdgeCa;

    public Triangle(Vector3 a, Vector3 b, Vector3 c)
    {
        EdgeAb = new Edge3( a, b );
        EdgeBc = new Edge3( b, c );
        EdgeCa = new Edge3( c, a );
        TriNorm = Vector3.Cross(a - b, a - c);
    }

    public Vector3[] Verticies => new[] {A, B, C};

    public readonly Vector3 TriNorm;

    private static readonly RangeDouble ZeroToOne = new RangeDouble(0,1);

    public Plane TriPlane => new Plane(A, TriNorm);

    //The below three could be pre-calculated to
    //trade off space vs time

    public Plane PlaneAb => new Plane(EdgeAb.A, Vector3.Cross(TriNorm, EdgeAb.Delta  ));
    public Plane PlaneBc => new Plane(EdgeBc.A, Vector3.Cross(TriNorm, EdgeBc.Delta  ));
    public Plane PlaneCa => new Plane(EdgeCa.A, Vector3.Cross(TriNorm, EdgeCa.Delta  ));

    public static readonly  RangeDouble Zero1 = new RangeDouble(0,1);

    public Vector3 ClosestPointTo(Vector3 p)
    {
        //Find the projection of the point onto the edge

        var uab = EdgeAb.Project( p );
        var uca = EdgeCa.Project( p );

        if (uca > 1 && uab < 0)
            return A;

        var ubc = EdgeBc.Project( p );

        if (uab > 1 && ubc < 0)
            return B;

        if (ubc > 1 && uca < 0)
            return C;

        if (ZeroToOne.Contains( uab ) && !PlaneAb.IsAbove( p ))
            return EdgeAb.PointAt( uab );

        if (ZeroToOne.Contains( ubc ) && !PlaneBc.IsAbove( p ))
            return EdgeBc.PointAt( ubc );

        if (ZeroToOne.Contains( uca ) && !PlaneCa.IsAbove( p ))
            return EdgeCa.PointAt( uca );

        //The closest point is in the triangle so 
        //project to the plane to find it
        return TriPlane.Project( p );

    }
}

Et de la structure du bord

public struct Edge3
{

    public readonly Vector3 A;
    public readonly Vector3 B;
    public readonly Vector3 Delta;

    public Edge3(Vector3 a, Vector3 b)
    {
        A = a;
        B = b;
        Delta = b -a;
    }

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

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

}

Et le plan de la structure

public struct Plane
{
    public Vector3 Point;
    public Vector3 Direction;

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

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

}

OriginalL'auteur bradgonesurfing