python - 查询变换球体上的最近点

Question

给定一个球体的 4x4 变换矩阵和空间中的一个点，我想找到球体表面上最近的点。

通常我会在点和球体中心之间画一条线，并使用球体的半径来得到我的解决方案，但在这里我处理的是一个非均匀缩放的球体。这是 Python 中的一个简单示例:

import numpy as np
from numpy.core.umath_tests import inner1d

# 4x4 transform matrix of a sphere with the following components:
# Scale XYZ = 1,5,1 (Scaled only in Y axis to keep this example simple)
# Rotation XYZ = 0,0,45 (Simple tilt for this example)
# Position XYZ = -1,3,0 (Position along XY plane, again for simplicity)
M = np.array([[ 0.70710678,  0.70710678,  0.        ,  0.        ],
              [-3.53553391,  3.53553391,  0.        ,  0.        ],
              [ 0.        ,  0.        ,  1.        ,  0.        ],
              [-1.        ,  3.        ,  0.        ,  1.        ]])

# Query point p0
p0 = np.array([-2,6,0])

# Transform the point into a unit sphere
I = np.linalg.inv(M)
p1 = np.array(p)-M[3,:3]
p1 = np.dot(p1,I)

# Normalize the point so it is on the surface of the unit sphere
mag = np.sqrt(inner1d(p1,p1)) # magnitude
p1 /= mag

# Transform back into 3D space
p1 = np.dot(p1,M[:3,:3]) + M[3,:3] #result [-1.65653216, 4.96959649, 0.]

当查询点已经靠近球体时，此解决方案速度很快且效果很好，但当距离较远时效果不佳。请参见上图:点 p2 这将是所需的结果。

Answer 1

您想看看 David Eberley 的“从一个点到一个椭圆、一个椭圆体或一个超椭球体"(PDF download。)最终，您将找到 2D 椭圆的四次多项式的根，并且3D 椭球的 6 次多项式的根，所以这是绝不是一个简单的问题。

鉴于这种复杂性，您可能想要寻求近似结果，例如，通过对椭圆体进行网格剖分并寻找最近的网格顶点。