Query for the nearest point on a transformed sphere
Given the sphere's 4x4 transformation matrix and a point in space, I want to find the closest point on the sphere's surface.
Normally I would trace the line between a point and the center of the sphere and use the radius of the sphere to get my solution, but here I am dealing with an unevenly scaled sphere. Here's a quick example in 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.]
This solution is fast and works well when the query point is already close to the sphere, but not so much when it is far away. See in the image above: point p2, which will be the desired result.
source to share
You want to look at David Eberley's "Distance from a Point to an Ellipse, Ellipsoid, or Hyperellipsoid" ( PDF Download .) Ultimately you find the roots of the quartic polynomial for the 2D ellipse and the roots of the 6th degree polynomial for the 3D ellipsoid, so this is by no means simple problem.
Given this complexity, you can instead search for an approximate result, for example by merging the ellipsoid and finding the closest mesh vertex.
source to share
I don't know if the iterative procedure below will work, but it comes to mind intuitively. It might be worth a try.
-
From this point, draw a line to the center of the ellipsoid and get the point of intersection with the surface.
-
Construct a normal plane at the intersection and project the specified point onto it.
-
Join the projection to the center, find the intersection with the surface, and repeat from 2.until convergence.
I cannot say if convergence to the nearest point can be guaranteed. All I can say is that when you converge, you find the orthogonal projection of this point onto the surface.
The image shows the first iterations (intersections in green, projections in orange).
This is probably equivalent to Newton's iterations.
source to share