A 3d point primitive represented by a Vec3 from the origin of an unspecified frame, and a collection of point-related utility methods.
More...
|
|
These static methods work with points or collections of points.
Collections of points are represented either as an Array of point locations or as an indirect Array of pointers to point locations, which can save a lot of copying for large point sets.
|
static RealP | calcDistance (const Vec3P &p1, const Vec3P &p2) |
| Calculate the distance between two points (expensive). More...
|
|
static RealP | findDistanceSqr (const Vec3P &p1, const Vec3P &p2) |
| Find the square of the distance between two points (cheap). More...
|
|
static Vec3P | findMidpoint (const Vec3P &p1, const Vec3P &p2) |
| Find the point midway between two points. More...
|
|
static bool | pointsAreNumericallyCoincident (const Vec3P &p1, const Vec3P &p2) |
| Determine whether two points whose locations are known to an accuracy tol are numerically indistinguishable. More...
|
|
static bool | pointsAreNumericallyCoincident (const Vec3P &p1, const Vec3P &p2, RealP tol) |
| Alternate signature with explicitly-supplied tolerance. More...
|
|
static void | findSupportPoint (const Array_< Vec3P > &points, const UnitVec3P &direction, int &most, RealP &mostCoord) |
| Given a set of points, find the one that is the furthest in a given direction, and return its index and location along that direction. More...
|
|
static void | findSupportPointIndirect (const Array_< const Vec3P *> &points, const UnitVec3P &direction, int &most, RealP &mostCoord) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
static void | findExtremePoints (const Array_< Vec3P > &points, const UnitVec3P &direction, int &least, int &most, RealP &leastCoord, RealP &mostCoord) |
| Given a set of points, find the two points that are the most extreme along a given direction (not necessarily distinct), and return their indices and locations along the given direction. More...
|
|
static void | findExtremePointsIndirect (const Array_< const Vec3P *> &points, const UnitVec3P &direction, int &least, int &most, RealP &leastCoord, RealP &mostCoord) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
static Vec3P | calcCentroid (const Array_< Vec3P > &points_F) |
| Given a set of points, calculate the centroid (average location) of those points. More...
|
|
static Vec3P | calcCentroidIndirect (const Array_< const Vec3P *> &points_F) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
static void | calcCovariance (const Array_< Vec3P > &points_F, Vec3P ¢roid, SymMat33P &covariance) |
| Given a set of points, calculate the centroid (average location) and covariance matrix of those points. More...
|
|
static void | calcCovarianceIndirect (const Array_< const Vec3P *> &points_F, Vec3P ¢roid, SymMat33P &covariance) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
static void | calcPrincipalComponents (const Array_< Vec3P > &points_F, TransformP &X_FP) |
| Given a set of points in an unspecified frame F, find the principal component directions describing the distribution of the points in space. More...
|
|
static void | calcPrincipalComponentsIndirect (const Array_< const Vec3P *> &points_F, TransformP &X_FP) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
|
These static methods create a minimal axis-aligned box that includes all of a set of given points.
|
static void | findAxisAlignedExtremePoints (const Array_< Vec3P > &points, int least[3], int most[3], Vec3P &low, Vec3P &high) |
| Given a set of points, find the six points that are the most extreme along the axial directions (not necessarily distinct points). More...
|
|
static void | findAxisAlignedExtremePointsIndirect (const Array_< const Vec3P *> &points, int least[3], int most[3], Vec3P &low, Vec3P &high) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
static Geo::AlignedBox_< P > | calcAxisAlignedBoundingBox (const Array_< Vec3P > &points, Array_< int > &support) |
| Calculate the smallest axis-aligned bounding box including all n given points. More...
|
|
static Geo::AlignedBox_< P > | calcAxisAlignedBoundingBox (const Array_< Vec3P > &points) |
| Alternate signature doesn't return support points. More...
|
|
static Geo::AlignedBox_< P > | calcAxisAlignedBoundingBoxIndirect (const Array_< const Vec3P *> &points, Array_< int > &support) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
static Geo::AlignedBox_< P > | calcAxisAlignedBoundingBoxIndirect (const Array_< const Vec3P *> &points) |
| Alternate signature doesn't return support points. More...
|
|
|
These static methods create a tight-fitting oriented bounding box (OBB) that includes all of a set of given points.
The OBB is not guaranteed to be minimal but will usually be very good. You can optionally obtain the set of support points that determined the size of the box.
|
static void | findOrientedExtremePoints (const Array_< Vec3P > &points_F, const RotationP &R_FB, int least[3], int most[3], Vec3P &low_B, Vec3P &high_B) |
| Given a set of points, find the six points that are the most extreme along specified orientation directions (not necessarily distinct points). More...
|
|
static void | findOrientedExtremePointsIndirect (const Array_< const Vec3P *> &points_F, const RotationP &R_FB, int least[3], int most[3], Vec3P &low_B, Vec3P &high_B) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
static Geo::OrientedBox_< P > | calcOrientedBoundingBox (const Array_< Vec3P > &points, Array_< int > &support, bool optimize=true) |
| Calculate a tight-fitting oriented bounding box (OBB) that includes all n given points. More...
|
|
static Geo::OrientedBox_< P > | calcOrientedBoundingBox (const Array_< Vec3P > &points) |
| Alternate signature doesn't return support points. More...
|
|
static Geo::OrientedBox_< P > | calcOrientedBoundingBoxIndirect (const Array_< const Vec3P *> &points, Array_< int > &support, bool optimize=true) |
| Alternate signature taking an array of pointers to points rather than the points themselves. More...
|
|
static Geo::OrientedBox_< P > | calcOrientedBoundingBoxIndirect (const Array_< const Vec3P *> &points, bool optimize=true) |
| Alternate signature doesn't return support points. More...
|
|
|
These static methods work with spheres or collections of spheres.
Bounding spheres
Bounding sphere methods calculate the smallest sphere around a given set of points such that no point is outside the sphere, although some may be on its surface. How many and specifically which points were actually used to define the sphere can be returned; there will never be more than 4. This information is primarily used to construct bounding sphere algorithms; users normally just need the sphere so can use the simpler signatures.
Bounding sphere methods address roundoff by stretching the sphere enough to guarantee that all points are strictly inside the sphere and that later tests can produce only false positives not false negatives which might cause a contact to be missed. To do that we have to account not just for machine precision, but for relative errors caused by spheres of large radius or spheres that are located far from the origin. These adjustments ensure that if a test point appears numerically to be outside the sphere, it really cannot contact anything that is inside the sphere.
We use a bounding sphere method due originally to Emo Welzl that computes a near-perfect minimal bounding sphere around a set of points with expected O(n) run time. Our implementation has been extensively modified to deal with singular cases so you do not have to precondition the points before asking for their bounding sphere.
We also provide a conventional fast and dumb approximate bounding sphere using Ritter's method as described in Christer Ericson's book. This is mostly useful for testing the Welzl method's accuracy and performance and should not generally be used. A Welzl bounding sphere should never be larger than a Ritter sphere and should normally be substantially smaller.
|
static Sphere_< P > | calcBoundingSphere (const Vec3P &p) |
| Create a tiny bounding sphere around a single point. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Vec3P &p0, const Vec3P &p1) |
| Create a minimal bounding sphere around two points. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Vec3P &p0, const Vec3P &p1, const Vec3P &p2) |
| Create a minimal bounding sphere around three points. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Vec3P &p0, const Vec3P &p1, const Vec3P &p2, const Vec3P &p3) |
| Create a minimal bounding sphere around four points. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Array_< Vec3P > &points) |
| Create a minimal bounding sphere around a collection of n points. More...
|
|
static Sphere_< P > | calcBoundingSphere (const std::vector< Vec3P > &points) |
| This signature takes an std::vector rather than a SimTK::Array_; no extra copying is required. More...
|
|
static Sphere_< P > | calcBoundingSphereIndirect (const Array_< const Vec3P *> &points) |
| Create a minimal bounding sphere around a collection of n points, given indirectly as an array of pointers. More...
|
|
static Sphere_< P > | calcBoundingSphere (const std::vector< const Vec3P *> &points) |
| This signature takes an std::vector rather than a SimTK::Array_; no extra copying is required. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Vec3P &p0, Array_< int > &which) |
| Create one-point bounding sphere and return the (trivial) support point, of which there is always one. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Vec3P &p0, const Vec3P &p1, Array_< int > &which) |
| Create a minimum sphere around two points. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Vec3P &p0, const Vec3P &p1, const Vec3P &p2, bool forceCircumsphere, Array_< int > &which) |
| Create a minimum sphere around three points. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Vec3P &p0, const Vec3P &p1, const Vec3P &p2, const Vec3P &p3, bool forceCircumsphere, Array_< int > &which) |
| Create a minimum sphere around four points. More...
|
|
static Sphere_< P > | calcBoundingSphere (const Array_< Vec3P > &points, Array_< int > &which) |
| Create an optimal minimum sphere around a collection of n points. More...
|
|
static Sphere_< P > | calcBoundingSphereIndirect (const Array_< const Vec3P *> &points, Array_< int > &which) |
| Alternate signature works with an array of pointers to points. More...
|
|
static Sphere_< P > | calcApproxBoundingSphere (const Array_< Vec3P > &points) |
| Calculate an approximate bounding sphere. You should normally use calcBoundingSphere() which will give a smaller sphere. More...
|
|
static Sphere_< P > | calcApproxBoundingSphere (const std::vector< Vec3P > &points) |
| This signature takes an std::vector rather than a SimTK::Array_; no extra copying is required. More...
|
|
static Sphere_< P > | calcApproxBoundingSphereIndirect (const Array_< const Vec3P *> &points) |
| Alternate signature works with an array of pointers to points. More...
|
|
static Sphere_< P > | calcApproxBoundingSphereIndirect (const std::vector< const Vec3P *> &points) |
| This signature takes an std::vector rather than a SimTK::Array_; no extra copying is required. More...
|
|
template<class P>
class SimTK::Geo::Point_< P >
A 3d point primitive represented by a Vec3 from the origin of an unspecified frame, and a collection of point-related utility methods.