Results 1 to 3 of 3

Math Help - Minimum distance between two catmull rom splines

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    1

    Minimum distance between two catmull rom splines

    For a project I'm working on I need to find the minimum distance between two three dimensional catmull rom splines (cubic b-spline defined by at least four control points). At the moment I'm using a very naive algorithm that just recursively finds the closest points on the two curves then refines a new curve (set of points) using the adjacent points as new control points. A few recursions gives the true closest point to enough accuracy but of course if there are multiple closest points it won't find them all.

    Minimum distance between two catmull rom splines-catmullromsplinesminimumdistance.png

    I'm hoping one of the math experts here can give me some advice on a way to solve this more efficiently.

    Frustratingly, I was able to find a reference to a paper which supposedly describes an implementation of a multidimensional Newton's method that can solve this problem but the paper itself is nowhere to be found and I don't understand how Newton's method can be applied here.

    Thanks a lot for any help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Do you have a formula that you can show here that describes the paths of the two curves? Otherwise, multidimensional Newton-Raphsons method will be good enough if the only thing you want is a numerical value. Normally, the method works as follows:

    x_{n+1}=x_n - \displaystyle{\frac{f(x)}{f'(x)}}

    But if you instead have a function operating on a vector

    f: \mathbb{R}^n \rightarrow \mathbb{R}

    there is no derivative of f, so the original formula doesn't work. However, there are directional derivatives, and the function does have a gradient. The gradient will point in the direction in which the function will increase the fastest. Therefore, setting

    \bar{d}=\displaystyle{\frac{\nabla f}{\left|\nabla f\right|}}

    will tell in which direction the function increases. Now, starting with the original formula, there are two things that have to be changed.

    1. While x_n becomes the vector \bar{x}_n, the second term in the subtraction is a scalar. It has to be made a vector too, before the subtraction be performed. Therefore, we will multiply it by the (normalized) vector d, since d is the direction in which the function increases. So

    \displaystyle{\frac{f(x)}{f'(x)}}

    becomes

    \bar{d}(\bar{x})\ \displaystyle{\frac{f(\bar{x})}{f'(\bar{x})}}

    2. There is no f'(\bar{x}). However, there is a directional derivative in the direction (d) we are heading, \nabla_{\bar{d}}f'(\bar{x}), which should be used instead. Substitution will give us

    \bar{d}(\bar{x})\ \displaystyle{\frac{f(\bar{x})}{\nabla_{\bar{d}}f'  (\bar{x})}}

    Now, we can make the realization that \nabla_{\bar{d}}f'(\bar{x}) = \left|\nabla f(\bar{x})\right|, so we will get

    \bar{d}\ \displaystyle{\frac{f(\bar{x})}{\left|\nabla f(\bar{x})\right|}}\ =\ \displaystyle{\frac{\nabla f(\bar{x})}{\left|\nabla f(\bar{x})\right|}}\ \displaystyle{\frac{f(\bar{x})}{\left|\nabla f(\bar{x})\right|}}\ =\ \displaystyle{\frac{\left(\nabla f(\bar{x})\right)f(\bar{x})}{\left|\nabla f(\bar{x})\right|^2}}

    Inserting this into the original formula yields

    \bar{x}_{n+1}=\bar{x}_n -\displaystyle{\frac{\left(\nabla f(\bar{x})\right)f(\bar{x})}{\left|\nabla f(\bar{x})\right|^2}}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    I forgot to mention it, but the function that you want to find the root for is \nabla f(\bar{x}), where f(\bar{x}) is the distance between the two points depending on some parameters that are stored in \bar{x}. I just realized that you can't use the method from above directly. However, if you square all the elements in \nabla f(\bar{x}) and add them together to a new function g, i.e. g(\bar{x})=(\nabla f(\bar{x}))^2, then you will be able to find the root using g. Also, since g will now have a gradient equal to the null vector for the place where the root is, you might find it faster to double the step length when you get close to the root, i.e:

    \bar{x}_{n+1}\ =\ \bar{x}_n - \lambda\ \displaystyle{\frac{(\nabla g(\bar{x}))g(\bar{x})}{\left|\nabla g(\bar{x})\right|^2}}

    Where 1\leq\lambda\leq 2. You may just set \lambda to be 2 all the time. However, if \bar{x} is far away from any root, a lower value will probably work better.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Minimum distance
    Posted in the Calculus Forum
    Replies: 11
    Last Post: January 11th 2010, 05:12 AM
  2. Minimum Distance
    Posted in the Calculus Forum
    Replies: 8
    Last Post: October 19th 2009, 12:12 PM
  3. minimum distance
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 21st 2009, 04:07 PM
  4. Minimum Distance
    Posted in the Geometry Forum
    Replies: 6
    Last Post: October 25th 2007, 02:58 AM
  5. Minimum Distance
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 14th 2007, 07:40 PM

Search Tags


/mathhelpforum @mathhelpforum