As per title: if I have two surfaces that do not overlap, how do I find the smallest distance between them? I haven’t found anything in RhinoCommon (should there be something?) so I have tried this in C++:
ON_Surface* srf1, srf2; // defined elsewhere
const ON_SurfaceTree* pTree1 = srf1->SurfaceTree();
const ON_SurfaceTree* pTree2 = srf2->SurfaceTree();
return pTree1->MinimumDistanceLowerBound(pTree2);
but for other than trivial test cases (planes, spheres) this returns zero.
Hi Menno,
David did a workaround for this in RhinoCommon:
Start with some random point on first surface, then find the closest point to that random one on second surface. Repeating this process in a loop (finding the closest point from on surface to another) will end up in sufficient results in just a few iterations.
Hope it helps.
Yeah, I was kinda hoping not to have to do this iteratively.
I think it will either be you or someone else’s function that does it iteratively. Unless you can discover a clever analytical method.
Iterative solutions seem to depend a lot on their starting point and typically end up in a local minimum for more complex shapes (think: ship hulls, propeller blades). Therefore an analytical solution, or another solution that is guaranteed to give the global minimum is needed.
I don’t disagree, but as far as I know iteration is all we’ve got so far. I mean in general, not just Rhino users. Maybe the McNeel big math brains are aware of some recent developments and can point you to them.
Giving this a little more thought: Do you think there might be something helpful in gaming collision detection math?
I think a safe method are minkowski sums / minkowski difference. (they’re used in gaming a lot) Unfortunately, they are not trivial to implement in rhino, they use solid meshes, and are not trivial to implement.
Digitalrune offers a library that can do minkowski sums/differences for convex meshes:
http://www.digitalrune.com/
I’ve found david’s method to be quite reliable when sampled from multiple points (not one starting point, but running it multiple times from many starting points). I’ve tested with a sinusoid surface, with many local optima, and it quite reliably finds all local optima. Here’s my test: it seems to work quite well for a case with a few dozen local minima.
I’m working on a combination of first using the ON_SurfaceTree to identify the Bézier patches on each surface that are closest to each other, then use iterative (?) closest point on these to get the final answer.
As this has to run inside a loop I hope to implement a speedy robust algorithm.
@dalelear, do you have a suggestion for Menno?
Menno,
There may be one to an infinite number of solutions. A simple example of infinitely many solutions is a case like orthogonal rectangles with the edge of one rectangle being closest and equidistant to the other. If the surfaces intersect in a curve there are also infinitely solutions. There are also many situations where there are multiple discrete solutions and these occur with disturbing frequency in the real world of modeling.
You need to carefully consider what you want to do in these cases.
Typically you will use an iterative techniques find a local solution, and then look for a better one until you are certain no better one exists.
Mathematically, you are searching for an extreme value of a function of four parameters over a bounded domain. The function is differentiable, but the derivatives can be parallel or zero (when control points are coincident.) To handle cases when the closest point or points are on a boundary, you will need code that finds extreme points of functions with two, three and four parameters.
This is a tough numerical problem. If you have not written this kind of code before, read the optimization sections of something like Numerical Recipes in C.
I typically use a three phase approach to this style of problem
First: A fast and simple algorithm that gets a decent answer most of the time (bounded Newton style stuff) together with a reliable way to determine that the fast and simple algorithm failed. Detecting failure is the tricky part. The algorithm can converge and still fail miserably when derivatives are parallel-ish or zero-ish (the difference between precision and accuracy). When these simple algorithms work, and they do work most of time on “reasonable” surfaces, they tend to be fast and accurate.
Second: A slower but better algorithm to try again (conjugate gradient, etc.) and a reliable way to determine if it failed. Again, detecting failure is the tricky part
Third: A guided sampling style algorithm as a last ditch fallback (these are typically much slower than bounded newton stuff because they require lots of iterations.)
I often use course tessellations to get seed values for iterative algorithms.
We need to expose the closest distance functions we have in the opennurbs SDK Rhino plug-in devs have access to, so our customers don’t need to write stuff like this. I’ve added http://mcneel.myjetbrains.com/youtrack/issue/RH-28493 to remind me to get this done.
Thanks for your insight @dalelear. I am not shy of these kind of optimization problems. We use a good math library (extreme optimization) for multidimensional optimization and other stuff, so that will take a lot of effort out of this.
Currently I have a reasonably fast solution that finds the closest pair of points from two lists of points on both surfaces, then I use the iterative closest distance approach discussed above.
I’ll see where I can get with the multidimensional optimization approach.
Thanks for a great explanation.
Given that it’s fairly easy for a user to determine visually when the closest distance is to a corner or edge, how would the problem change (if at all) if the search was only conducted when it’s already known that the answer will be interior points on both surfaces?
I finally made it to a robust algorithm for this problem. After checking that the surfaces do not intersect, in the first step I create coarse meshes on the surfaces and use an RTree-based branch-and-bound algorithm to find the closest pair of mesh vertices. These two points are then the seeds for the iterative approach ClosestPoint described earlier.
By the way, the algorithm to find the closest pair of points on meshes (or any point collection) performs the pants off of ON_GetMeshMeshClosestPoint. For two MeshSpheres of each 360,000 vertices, the algorithm finds the closest pair in 15 seconds. Comparing with ON_GetMeshMeshClosestPoint, shows that that takes 9 seconds to find the closest pair for two MeshSpheres with only 1000 vertices.
It is of course conceivable that I am doing something wrong, but the approach below gives me 9 seconds for two 1000-vertex meshes. I did note, however, that even though I requested multiple thread, that it only uses one core on my machine.
const ON_Mesh* meshA, const ON_Mesh* meshB; // obtained from command
LARGE_INTEGER f, t1, t2;
QueryPerformanceFrequency(&f);
QueryPerformanceCounter(&t1);
int fA, fB;
double wA[4], wB[4];
ON_GetMeshMeshClosestPoint(*meshA, *meshB, DBL_MAX, true, &fA, wA, &fB, wB);
QueryPerformanceCounter(&t2);
double elapsed = (t2.QuadPart - t1.QuadPart)*1000/f.QuadPart;
RhinoApp().Print("Elapsed: %3.2f ms\n", elapsed);
@stevebaer: I would be happy to share my closest point pair-finding algorithm into openNURBS - any pointers on how to do this best?
It was @dalelear that gave the suggestions and he may have better ideas than I currently do about sharing this algorithm in OpenNURBS.