>>There is free code around the net for actual "best fits" in the sense of minimum volume or minimum surface area.
References please? I never like to re-invent the wheel. I wrote some of this code based on asking questions on the algorithms mailing list and not getting particularly good answers other than 'brute force it'.
Thanks for posting these John. I'm looking for a best fit sphere routine (for reasonably automatic calibration of a three axis magnetometer).
Is the best fit sphere a "best fit" in terms of minimum least squares error for the sum of the sample points' distances from the nearest point on the sphere's surface?
I've found your code snippets useful more often than I'd prefer to professionally admit! The one problem I always have though when I want to look up something that I'm 100% sure you've written is that I'm terrible with names.
Your sites name and your own invariably vanish from memory whenever I most need them.
Lately though I've found a way around this, I just got to Google Images and search for "A concrete example of two best fit spheres"... it's usually the highest result :)
Thanks for ALL of the snippets I find your site/blog incredibly helpful and best of luck with Duatiu.
7:30 AM
Anonymous said...
With blogs like this around I don't even need website anymore. I can just visit here and see all the latest happenings in the world.
11:31 AM
Anonymous said...
) Hyper-texting and Hyper-Networking pose new health risks for teens. E-mail alerts are free, private and secure, and you won't get any ink on your fingers. Don't think that just because you're domain is obscure or specific you're protected from hijackers.
[Image]
(A concrete example of two best fit spheres.)
Today I put together a code snippet that contains just my 'best fit' routines. Probably the most common thing people come to this website for. They have been isolated into a single CPP and header file inside the namespace 'BEST_FIT'.
These are simply copies of the same routines which are found in the larger snippets collection called 'FloatMath'.
There is one new function I haven't previously posted which is a best fit capsule routine. The best fit capsule is derived by first computing the best fit OBB and then orienting the capsule along its longest edge and computing the radius by examining the maximum distance along the two shorter edges.
The capsule returned is in the exact format used by the PhysX SDK; which assumes that the Y axis of the capsule represents 'height' and the X/Z plane is the radius.
It is important to note that if the returned capsule height is a negative number, that means it could not be represented as a capsule and, instead, you should treat it as a sphere with the radius returned. Also, intentionally, there is a chance some points of the input cloud could extend outside of the capped spheres at then ends of the capsule. I did this on purpose because my primary use for the capsule fitting code is for automatic ragdoll generation and that kind of error is more than acceptable. I doubt it would matter in most use cases, but you should be aware of the limitation.
As in my previous source snippets, these routines should allow you to directly use your existing vector, matrix, and quaternion classes, unless they are particularily non-standard.
A vector is assumed to be a float pointer representing X, Y, and Z
A quaternioni is assumed to be a float 4 pointer to a quaternion in the format X, Y, Z, W
A matrix is assumed to be a float 16 pointer to a 4x4 matrix in the traditional D3DX format.
If you represent your quaternions or matrices differently, you will want to translate the results on the way in and out, otherwise you can just cast your existing classes to a float pointer and you should be able to use the routines directly.
Here is a direct link to the BestFit source code snippet:
The best fit sphere routine has been updated to be exact, per Charles Bloom's recommendations. I will update the OBB routine relatively soon, I'm going to try out Bloom's convex hull routine and see if it is appropriate as a pre-process stage for the OBB point cloud.
posted by John W. Ratcliff at 2:26 PM on Mar 8, 2009
"Best Fit Plane : Best Fit AABB : Best Fit OBB : Best Fit Sphere : Best Fit Capsule"
7 Comments -
Okay, but these are in no way "best fits" unless you define "best" by the quality of picture in the blog.
There is free code around the net for actual "best fits" in the sense of minimum volume or minimum surface area.
5:09 PM
>>There is free code around the net for actual "best fits" in the sense of minimum volume or minimum surface area.
References please? I never like to re-invent the wheel. I wrote some of this code based on asking questions on the algorithms mailing list and not getting particularly good answers other than 'brute force it'.
Thanks,
John
5:13 PM
Nice pic. I may read the article one day.
3:46 AM
Thanks for posting these John. I'm looking for a best fit sphere routine (for reasonably automatic calibration of a three axis magnetometer).
Is the best fit sphere a "best fit" in terms of minimum least squares error for the sum of the sample points' distances from the nearest point on the sphere's surface?
Thanks,
Benjohn Barnes
2:16 AM
I've found your code snippets useful more often than I'd prefer to professionally admit! The one problem I always have though when I want to look up something that I'm 100% sure you've written is that I'm terrible with names.
Your sites name and your own invariably vanish from memory whenever I most need them.
Lately though I've found a way around this, I just got to Google Images and search for "A concrete example of two best fit spheres"... it's usually the highest result :)
Thanks for ALL of the snippets I find your site/blog incredibly helpful and best of luck with Duatiu.
7:30 AM
With blogs like this around I don't even need website anymore.
I can just visit here and see all the latest happenings in the world.
11:31 AM
) Hyper-texting and Hyper-Networking pose new health risks for teens.
E-mail alerts are free, private and secure, and you won't get any ink on your fingers.
Don't think that just because you're domain is obscure or specific you're protected from hijackers.
My site; japanese bukakke
3:23 AM