在3D模式下计算点到三角形距离的最快方法？

Question

用于计算从点到3D三角形的最小距离的一种显而易见的方法是将点投影到三角形的平面上，确定所得点的重心坐标，然后使用它们来确定投影点是否位于三角形。如果不是，请将其重心坐标固定在[0,1]范围内，这将为您提供位于三角形内部的最近点。

有没有一种方法可以加快速度或以某种方式简化它？

Answer 1

有多种方法可以找到从点P0到三角形P1，P2，P3的距离。

3D方法。将点投影到三角形的平面上，并使用重心坐标或其他找到三角形中最接近点的方法。可以用通常的方式找到距离。

二维方法。对这些点应用平移/旋转，以使P1在原点上，P2在z轴上，P3在yz平面上。 P0点的投影是微不足道的（忽略x坐标）。这导致二维问题。使用边方程，可以确定最接近的顶点或三角形的边。这样就可以轻松计算距离。

此paper将两者的性能与2D方法获胜进行比较。

Answer 2

假设您使用的是已知的快速算法之一，那么加快速度的唯一方法就是对多个三角形进行大量测量。在这种情况下，您可以保留很多

在“边缘”或“绕组”结构中预先计算的数量。而不是存储3点，而是存储由边结构组成的网格。然后投影变得非常快，并且可以对重心测试进行编码，以使它们成为[[分支可预测。

真正的关键是将所有内容都保留在缓存中。处理器可以在近1个时钟周期内执行MUL和DIV，因此内存通常是瓶颈。也请考虑使用
SSE3
或类似的东西（例如Mono's SIMD support）编写算法。它是可行的，但是如果您考虑得足够周全，通常一次可以创建几个三角形。
我将尝试找到有关该主题的一些论文，但您可能想在Google上找到“ Ray Mesh Intersection”。当人们努力优化这些东西时，这将带来80年代和90年代的所有出色工作。

Answer 3

测试用例代码和实现在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 ); }

由于我有许多框架类，所以实现代码很奇怪。希望您可以将其视为伪代码并提取算法。原始向量类型来自https://www.nuget.org/packages/System.DoubleNumerics/。

请注意，可以缓存Triangle的某些属性以提高性能。注意，返回最接近的点不需要任何平方根，也不需要将问题转换为2D。 
该算法首先快速测试测试点是否最接近端点区域。如果不确定，则一个接一个地测试边缘外部区域。如果这些测试失败，则该点位于三角形内。请注意，对于远离三角形的随机选择的点，最有可能的点是最接近的点将是三角形的角点。
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 );

    }
}

和边缘结构

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;

}

和平面结构

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;

}

Answer 4

这里有一些基于this post的稳健代码，用于计算此投影，而这又是基于本书

实时碰撞检测。

如果在三角形平面上的正交投影不在三角形内，则该代码将返回null。

该代码在Java中，使用JOML线性代数库。
/** * Find the closest orthogonal projection of a point p onto a triangle given by three vertices * a, b and c. Returns either the projection point, or null if the projection is not within * the triangle. */ public static Vector3d closestPoint(Vector3d p, Vector3d a, Vector3d b, Vector3d c) { // Find the normal to the plane Vector3d n = b.sub(a, new Vector3d()).cross(c.sub(a, new Vector3d())); double nLen = n.length(); if (nLen < 1.0e-30) { return null; // Triangle is degenerate } else { n.mul(1.0f / nLen); } // Project point p onto plane spanned by a->b and a->c. // // Given a plane // // a : point on plane // n : *unit* normal to plane // // Then the *signed* distance from point p to the plane (in the direction // of the normal) is // // dist = p . n - a . n // double dist = p.dot(n) - a.dot(n); // Project p onto the plane by stepping the distance from p to the plane // in the direction opposite the normal Vector3d proj = p.add(n.mul(-dist, new Vector3d()), new Vector3d()); // Find out if the projected point falls within the triangle -- see: // http://blackpawn.com/texts/pointinpoly/default.html // Compute edge vectors double v0x = c.x - a.x; double v0y = c.y - a.y; double v0z = c.z - a.z; double v1x = b.x - a.x; double v1y = b.y - a.y; double v1z = b.z - a.z; double v2x = proj.x - a.x; double v2y = proj.y - a.y; double v2z = proj.z - a.z; // Compute dot products double dot00 = v0x * v0x + v0y * v0y + v0z * v0z; double dot01 = v0x * v1x + v0y * v1y + v0z * v1z; double dot02 = v0x * v2x + v0y * v2y + v0z * v2z; double dot11 = v1x * v1x + v1y * v1y + v1z * v1z; double dot12 = v1x * v2x + v1y * v2y + v1z * v2z; // Compute barycentric coordinates double denom = (dot00 * dot11 - dot01 * dot01); if (Math.abs(denom) < 1.0e-30) { return null; // Triangle is degenerate } double invDenom = 1.0 / denom; double u = (dot11 * dot02 - dot01 * dot12) * invDenom; double v = (dot00 * dot12 - dot01 * dot02) * invDenom; // Check barycentric coordinates of orthogonal projection point if ((u >= 0) && (v >= 0) && (u + v < 1)) { // Point is in triangle return proj; } else { // Nearest orthogonal projection point is outside triangle return null; } }

在3D模式下计算点到三角形距离的最快方法？

问题描述投票：13回答：4

4个回答

最新问题

在3D模式下计算点到三角形距离的最快方法？

问题描述 投票：13回答：4

4个回答

最新问题

问题描述投票：13回答：4