我编写了一个 python 脚本，它从查询点 (p) 中找到表面上最近点的 UV 坐标。曲面由四个线性边定义，这些边由逆时针列出的四个已知点 (p0,p1,p2,p3) 构成。
（请忽略小红球）
我的方法的问题是它非常慢（以低精度阈值进行 5000 次查询大约需要 10 秒。
我正在寻找一种更好的方法来实现我想要的，或者寻找让我的代码更高效的建议。我唯一的限制是它必须用 python 编写。
import numpy as np
# Define constants
LARGE_VALUE=99999999.0
SMALL_VALUE=0.00000001
SUBSAMPLES=10.0
def closestPointOnLineSegment(a,b,c):
''' Given two points (a,b) defining a line segment and a query point (c)
return the closest point on that segment, the distance between
query and closest points, and a u value derived from the results
'''
# Check if c is same as a or b
ac=c-a
AC=np.linalg.norm(ac)
if AC==0.:
return c,0.,0.
bc=c-b
BC=np.linalg.norm(bc)
if BC==0.:
return c,0.,1.
# See if segment length is 0
ab=b-a
AB=np.linalg.norm(ab)
if AB == 0.:
return a,0.,0.
# Normalize segment and do edge tests
ab=ab/AB
test=np.dot(ac,ab)
if test < 0.:
return a,AC,0.
elif test > AB:
return b,BC,1.
# Return closest xyz on segment, distance, and u value
p=(test*ab)+a
return p,np.linalg.norm(c-p),(test/AB)
def surfaceWalk(e0,e1,p,v0=0.,v1=1.):
''' Walk on the surface along 2 edges, for each sample segment
look for closest point, recurse until the both sampled edges
are smaller than SMALL_VALUE
'''
edge0=(e1[0]-e0[0])
edge1=(e1[1]-e0[1])
len0=np.linalg.norm(edge0*(v1-v0))
len1=np.linalg.norm(edge1*(v1-v0))
vMin=v0
vMax=v1
closest_d=0.
closest_u=0.
closest_v=0.
ii=0.
dist=LARGE_VALUE
for i in range(int(SUBSAMPLES)+1):
v=v0+((v1-v0)*(i/SUBSAMPLES))
a=(edge0*v)+e0[0]
b=(edge1*v)+e0[1]
closest_p,closest_d,closest_u=closestPointOnLineSegment(a,b,p)
if closest_d < dist:
dist=closest_d
closest_v=v
ii=i
# If both edge lengths <= SMALL_VALUE, we're within our precision treshold so return results
if len0 <= SMALL_VALUE and len1 <= SMALL_VALUE:
return closest_p,closest_d,closest_u,closest_v
# Threshold hasn't been met, set v0 anf v1 limits to either side of closest_v and keep recursing
vMin=v0+((v1-v0)*(np.clip((ii-1),0.,SUBSAMPLES)/SUBSAMPLES))
vMax=v0+((v1-v0)*(np.clip((ii+1),0.,SUBSAMPLES)/SUBSAMPLES))
return surfaceWalk(e0,e1,p,vMin,vMax)
def closestPointToPlane(p0,p1,p2,p3,p,debug=True):
''' Given four points defining a quad surface (p0,p1,p2,3) and
a query point p. Find the closest edge and begin walking
across one end to the next until we find the closest point
'''
# Find the closest edge, we'll use that edge to start our walk
c,d,u,v=surfaceWalk([p0,p1],[p3,p2],p)
if debug:
print 'Closest Point: %s'%c
print 'Distance to Point: %s'%d
print 'U Coord: %s'%u
print 'V Coord: %s'%v
return c,d,u,v
p0 = np.array([1.15, 0.62, -1.01])
p1 = np.array([1.74, 0.86, -0.88])
p2 = np.array([1.79, 0.40, -1.46])
p3 = np.array([0.91, 0.79, -1.84])
p = np.array([1.17, 0.94, -1.52])
closestPointToPlane(p0,p1,p2,p3,p)
Closest Point: [ 1.11588876 0.70474519 -1.52660706]
Distance to Point: 0.241488104197
U Coord: 0.164463481066
V Coord: 0.681959858995