title: Speeding up a closest point on a hyperbolic paraboloid algorithm
body: <p>I wrote a python script which finds the UV coords of the closest point on surface from a query point (p). The surface is defined by four linear edges made from four known points (p0,p1,p2,p3) listed counter clockwise.</p>
  
  <p>(Please ignore the little red ball)</p>
  
  <p><a href="https://imgur.com/7iKxTMO" rel="nofollow noreferrer"><img src="https://i.imgur.com/7iKxTMO.jpg" title="Hosted by imgur.com" /></a></p>
  
  <p>The problem with my approach is that it is very slow (~10 seconds to do 5000 queries with a low precision threshold.</p>
  
  <p>I'm looking for a better approach to achieve what i want, or suggestions to make my code more efficient. My only constraint is that it must be written in python.</p>
  
  <pre><code>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 &lt; 0.:
          return a,AC,0.
      elif test &gt; 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 &lt; dist:
              dist=closest_d
              closest_v=v
              ii=i
  
      # If both edge lengths &lt;= SMALL_VALUE, we're within our precision treshold so return results
      if len0 &lt;= SMALL_VALUE and len1 &lt;= 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
  </code></pre>