Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Closest point on catmull-rom spline help please.

Discussion in 'Scripting' started by jarden, Mar 29, 2011.

  1. jarden

    jarden

    Joined:
    Mar 29, 2011
    Posts:
    74
    Hello I'm a novice mathematician and programmer and have been looking for the solution in the topic over the internet. I found some code that appears to be for a 2D catmull-rom spline. I was hoping someone can help me convert the function to JavaScript (if it is not already) and add the extra dimension code.

    Here is the code (obtained from http://www.openprocessing.org/visuals/?visualID=12768):

    Code (csharp):
    1. /**
    2.  * Returns the closest point on a catmull-rom curve relative to a search location.
    3.  * This is only an approximation, by subdividing the curve a given number of times.
    4.  * More subdivisions gives a better approximation but takes longer, and vice versa.
    5.  * No concern is given to handling multiple equidistant points on the curve - the
    6.  *   first encountered equidistant point on the subdivided curve is returned.
    7.  *
    8.  * @param cps    array of four PVectors that define the control points of the curve
    9.  * @param pt     the search-from location
    10.  * @param ndivs  how many segments to subdivide the curve into
    11.  * @returns      PVector containing closest subdivided point on curve
    12.  */
    13. PVector ClosestPointOnCatmullRom(PVector [] cps, PVector pt, int ndivs) {
    14.   PVector result = new PVector();
    15.   float bestDistanceSquared = 0;
    16.   float bestT = 0;
    17.   for (int i=0; i<=ndivs; i++) {
    18.     float t = (float)(i) / (float)(ndivs);
    19.     float x = curvePoint(cps[0].x,cps[1].x,cps[2].x,cps[3].x,t);
    20.     float y = curvePoint(cps[0].y,cps[1].y,cps[2].y,cps[3].y,t);
    21.     float dx = x - pt.x;
    22.     float dy = y - pt.y;
    23.     float dissq = dx*dx+dy*dy;
    24.     if (i==0 || dissq < bestDistanceSquared) {
    25.       bestDistanceSquared = dissq;
    26.       bestT = t;
    27.       result.set(x,y,0);
    28.     }
    29.   }
    30.   return result;
    31. }
    Is it as simple as adding these lines in their relative places?:

    Code (csharp):
    1. float z = curvePoint(cps[0].z,cps[1].z,cps[2].z,cps[3].z,t);
    2. float dz = z - pt.z;
    3. float dissq = dx*dx+dy*dy+dz*dz;
    4. result.set(x,y,z);
     
  2. Jesse Anders

    Jesse Anders

    Joined:
    Apr 5, 2008
    Posts:
    2,857
    Adapting the code you linked to should indeed be as simple as incorporating the third dimension, as in your example.

    However, the method used in the demo is fairly naive, and isn't particularly suitable for the general case, IMO.

    At the very least, I would search for the closest point on a piecewise linear approximation of the curve (that is, a series of line segments) rather than a set of sample points. A logical optimization would then be to subdivide adaptively based on curvature so as to make the search space as small as possible while still maintaining reasonable accuracy.

    There are probably other solutions that make use of numerical methods, but I don't have any particular suggestions off the top of my head. A search for 'closest point on catmull rom' should turn up some discussion of the problem, although you may have to dig a bit to find a solution.

    At the very least, I'd use the piecewise linear method rather than the sample point method used in the demo.
     
  3. dmko

    dmko

    Joined:
    Jun 15, 2014
    Posts:
    65
    I realize this is a bit old, but by any chance does someone have a good working example (I actually only need it for 2d, but either way...) I had a bit of trouble understanding @Jesse Anderson's answer here