Get nearest point on spline?



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 22/10/2008 at 00:32, xxxxxxxx wrote:

    User Information:
    Cinema 4D Version:   10.1 
    Platform:   Windows  ; Mac  ;  
    Language(s) :     C++  ;

    ---------
    Hi,

    is there a function to get the nearest point on a spline?

    For example, I have an object somewhere in the scene and a spline. How can I calculate the position of the point where the spline is nearest to the object?

    Thanks in advance for any help!

    Best regards,
    Jack



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 22/10/2008 at 00:56, xxxxxxxx wrote:

    The problem is this is not very welld defined. Lets say you have a point in the center of a circular spline. Each distance to the spline would be identical. Currently I can only think of splitting the spline into line segments and using PointLineDistance() to measure the distance and comparing the measured distances.

    cheers,
    Matthias



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 22/10/2008 at 04:47, xxxxxxxx wrote:

    I agree with Matthias. Finding the closest point on a spline analytically is quite tricky in the general case. The best approach is to convert the spline to line segments, and then do the check for all segments.

    regards
    /Filip



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 22/10/2008 at 12:50, xxxxxxxx wrote:

    Sounds like a good approach to me, thank you guys ;-)

    Greetings,
    Jack



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 06/01/2009 at 15:42, xxxxxxxx wrote:

    Quote: _Lets say you have a point in the center of a circular spline. Each distance to the spline would be identical.
    >
    > * * *
    _


    While I agree with this, it is not always a problem making a (eh-hem) 'random' decision in cases where there are competing equidistant closest point options. You can do this randomly or first-encountered or whatever other decision criteria.

    The reason I say this is because my situation is going to be like this. I'm growing ivy and want it 'generally' to follow a user-specified spline. In order to do that, there must be a consideration of proximity constantly.

    My question is this though: how accurate is the LineObject from GetLineObject() and what values for Real lod (0.0 to 1.0? meaning?)?



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 17/03/2009 at 12:10, xxxxxxxx wrote:

    Hi Robert,

    did you figure something out? (I guess so :D)
    How's it done? Can you give me a little hint?

    I guess, I'll just sample a given amount of positions along the spline and pick the nearest one. That way, the user has control about precision and performance.

    Greetings,
    Jack



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 17/03/2009 at 12:43, xxxxxxxx wrote:

    Well, first you need a LineObject which can be tricky. Here is the routine I used for IvyGrower to get the proper one from a Spline of some sort:

    > // Prepare spline (primitive to real, consider deformers) \> //\*---------------------------------------------------------------------------\* \> Bool Ivy::PrepareSpline(SplineObject\* sobj) \> //\*---------------------------------------------------------------------------\* \> { \>      Matrix               mg =               sobj->GetMg(); \>      // GetRealSpline (returns self if already 'real') \>      Bool               free =               FALSE; \>      SplineObject\*     test =               sobj->GetRealSpline(); \>      if (!test)                              return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.GetRealSpline"); \>      if (test != sobj) \>      { \>           // Clone Spline \>           sobj =                                   ToSpline(sobj->GetClone(0L, NULL)); \>           if (!sobj)                              return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.GetClone"); \>           // MakeEditable \>           ModelingCommandData     mcd; \>           mcd.doc =                              doc; \>           mcd.op =                              sobj; \>           mcd.mode =                              0L; \>           if (!SendModelingCommand(MCOMMAND_MAKEEDITABLE, mcd)) \>           { \>                return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.SendModelingCommand(MAKEEDITABLE)"); \>           } \>           sobj =                                   ToSpline(mcd.result->GetIndex(0L)); \>           if (!sobj)                              return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.sobj"); \>           free =                                   TRUE; \>      } \>      // CurrentStateToObject obj \>      ModelingCommandData     mcd; \>      BaseContainer          mbc; \>      mbc.SetBool(MDATA_CURRENTSTATETOOBJECT_INHERITANCE,          TRUE); \>      mbc.SetBool(MDATA_CURRENTSTATETOOBJECT_KEEPANIMATION,     FALSE); \> #ifdef     C4D_R95 \>      mbc.SetBool(MDATA_CURRENTSTATETOOBJECT_NOGENERATE,          FALSE); \> #endif     // C4D_R95 \>      mcd.doc =                              doc; \>      mcd.flags =                              0L; \>      mcd.bc =                              &mbc; \>      mcd.mode =                              MODIFY_ALL; \>      mcd.op =                              sobj; \>      if (!SendModelingCommand(MCOMMAND_CURRENTSTATETOOBJECT, mcd)) \>      { \>           if (free)     SplineObject::Free(sobj); \>           return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.SendModelingCommand(CURRENTSTATETOOBJECT)"); \>      } \>      if (free)                              SplineObject::Free(sobj); \>      SplineObject\*          cstoObj =     static_cast<SplineObject\*>(mcd.result->GetIndex(0L)); \>      if (!cstoObj)                         return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.cstoObj"); \>      // Get LineObject \>      followSpline =                         cstoObj->GetLineObject(doc, 1.0f, NULL); \>      SplineObject::Free(cstoObj); \>      if (!followSpline)                    return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.GetLineObject()"); \>      if (!followSpline->GetSegmentCount()) \>      { \>           LineObject::Free(followSpline); \>           followSpline =     NULL; \>           return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy Grower doesn't support following multi-segmented splines"); \>      } \>      followSPtCnt =                         followSpline->GetPointCount(); \> #ifdef     C4D_R10 \>      followSPoint =                         followSpline->GetPointW(); \> #else \>      followSPoint =                         followSpline->GetPoint(); \> #endif \>      if ((followSPtCnt < 2L) || !followSPoint) \>      { \>           LineObject::Free(followSpline); \>           followSpline =     NULL; \>           return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.followSPoint"); \>      } \>      // Apply global matrix to points \>      for (LONG n = 0L; n != followSPtCnt; ++n) \>      { \>           followSPoint[n] \*=     mg; \>      } \>      // Always considering pairs of points (line segments) \>      --followSPtCnt; \> \>      return TRUE; \> }

    And then here you can see how I test for distance. Not optimized for speed in any way (always tests all line segments) :

    > // Get the distance of a line segment from a Sphere surface. \> //    Input:     a Line Segment P0-P1 and a Sphere C,r \> //    Return:     whether or not line segment is outside sphere \> //                    Pn contains the closest point on the line segment \> //                    dist contains the shortest distance from P0-P1 to C,r \> //\*---------------------------------------------------------------------------\* \> Bool DistanceSegmentSphere(const Vector& P0, const Vector& P1, const Vector& C, const Real r, Vector& Pn, Real& dist) \> //\*---------------------------------------------------------------------------\* \> { \>      Vector     v =               P1 - P0; \>      Vector     w =               C - P0; \> \>      double     c1 =          w \* v; \>      if (c1 > 0.0) \>      { \>           double     c2 =     v \* v; \>           if (c1 < c2) \>           { \>                c1 /=               c2; \>                Pn =               P0 + c1 \* v; \>           } \>           else     Pn =     P1; \>      } \>      else          Pn =     P0; \> \>      v =                         C-Pn; \>      // Inside sphere \>      if (Len(v) < r)          return FALSE; \>      // Outside/on sphere \>      dist =                    Sqrt(v\*v); \>      return TRUE; \> } \> //\*---------------------------------------------------------------------------\* \> Bool Ivy::computeTowardsSpline(const Real& floatLength, const Vector& oldPos, Vector& newPos, Bool& climbing) \> //\*---------------------------------------------------------------------------\* \> { \>      Vector          nearPt =                         newPos; \>      Vector          segPt; \>      Real          r =                                   Len(newPos-oldPos); \>      Real          minDistance =                    MAXREAL; \>      Real          distance; \> \>      climbing =                                        FALSE; \>      for (LONG n = 0L; n != followSPtCnt; ++n) \>      { \>           // LineSegment-Sphere Distance calculation - return if a line segment is found to be interpenetrating sphere \>           if (!DistanceSegmentSphere(followSPoint[n], followSPoint[n+1], oldPos, r, segPt, distance)) \>           { \>                climbing =     TRUE; \>                return TRUE; \>           } \>           if (distance >= minDistance)     continue; \>           minDistance =     distance; \>           nearPt =          segPt; \>      } \>      // get a point along line segment 'nearPt to newPos' using a 0.0 to 1.0 parameter (splineWeight with some random variation) \>      nearPt =                                        !(nearPt - oldPos); \>      newPos =                                        !(newPos - oldPos); \>      segPt =                                             newPos + ((nearPt - newPos) \* splineWeight \* rand() \* irand); \>      newPos =                                        (!segPt \* r) + oldPos; \>      climbing =                                        (minDistance <= floatLength); \>      return climbing; \> }

    Hope that helps a bit. :)



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 17/03/2009 at 12:45, xxxxxxxx wrote:

    Note that I'm testing DistanceSegmentSphere as there is a line segment (not associated with the spline) being tested for closeness allowing for change in direction.



  • THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

    On 17/03/2009 at 15:56, xxxxxxxx wrote:

    Ha, I already solved it :-)

    But totally different from your approach. I just take a user-given amount of samples from the spline and store those positions in an array.

    Then I iterate the array whenever I need to get a nearest point on the spline, and calculate the distance from my position to each of the positions in the array. The one that gives the lowest distance is returned.

    The performance is astonishingly good, and the code is quite simple.

    This function creates fills an array with sampled positions on the spline:

    > void SampleSplinePoints(SplineObject \*sp, GeDynamicArray<Vector>&SampleArr;, LONG Accuracy) \> { \>      LONG i = C_ZERO; \> \>      // Init Length \>      sp->InitLength(); \> \>      for (i = C_ZERO; i < Accuracy; i++) \>      { \>           SampleArr[i] = sp->GetSplinePoint(sp->UniformTonatural((Real)i / (Real)(Accuracy-C_ONE))); \>      } \> \>      // Free Length \>      sp->FreeLength(); \> } \>

    This function picks the one that gives the lowest distance and returns it in "ShortestPos". Forget about the "Flat" parameter, it's just something I needed for a specific feature.

    > void GetNearestPoint(GeDynamicArray<Vector>&SampleArr;, Vector &Position;, LONG &Accuracy;, Vector &ShortestPos;, const Bool Flat = TRUE) \> { \>      LONG i = C_ZERO; \>      Real p = C_FLOATZERO; \> \>      Vector Match = Vector(C_FLOATZERO); \>      Vector pos = Vector(); \>      Real Dist = C_FLOATZERO; \>      Real Shortest = C_FLOATZERO; \> \>      // Iterate sample positions on spline \>      for (i = C_ZERO; i < Accuracy; i++) \>      { \>           // Get position \>           pos = SampleArr[i]; \> \>           // Calculate Distance \>           if (Flat) \>                Dist = Len(Vector(pos.x, C_FLOATZERO, pos.z) - Vector(Position.x, C_FLOATZERO, Position.z)); \>           else \>                Dist = Len(pos - Position); \> \>           // If shortest distance found, memorize! \>           if ((i == C_ZERO) || (Dist < Shortest)) \>           { \>                Shortest = Dist; \>                Match = pos; \>                //GePrint("Position=" + VectorToString(Position) + "; Found=" + VectorToString(pos) + "; Dist=" + RealToString(Dist)); \>           } \>      } \> \>      // Return position with shortest distance \>      ShortestPos = Match; \> } \>

    This approach is, of course, only as exact as the user allows it to be (be specifying the Accuracy == Number of samples). But it's totally sufficient for what I'M doing with it :)

    Best Greetings,
    Jack



  • On 18/10/2017 at 13:20, xxxxxxxx wrote:

    Maybe someone else will find it helpful to have this ported to Python

    Thanks to the OP(s) for the original code

    # build an array of points from a spline
    def SampleSplinePoints(spline, acc) :                           #spline object, accuracy (int)
        
        sarr = []                                                  #point array
        for i in xrange(0, acc) :                                   #iterate through points
          sarr.append(spline.GetSplinePoint(float(i) / (acc-1)))   #append current point to array
        
        return sarr                                                #return array
      
      
    # find the nearest point in a point array
    def GetNearestPoint(sarr, p) :          #point array, point (vector)
        
        index = 0                          #closest point index
        md = 9e9999                        #min dist to keep track of
        
        for i in xrange(0, len(sarr)) :     #iterate through point array
            v = sarr[i]-p                  #store current difference vector
            d = v.GetLength()              #calc distance of vector
            if d < md:                     #if dist < minimum so far
                index = i                  #   then store index
                md = d                     #   and also set new minimum
                
        return index                       #return index of closest point in array
    

    Hope it helps :)

    Jenny


Log in to reply