convex_hull panics on some degenerate input

[jpetkau]

convex_hull will panic on some degenerate inputs.

Repro with Parry3d 0.7.0 (f32):

    #[test]
    fn chull_panic()
    {
        use nalgebra as na;
        let points: [na::Point3<f32>; 4] = [
            [0.000000000000000000000023624029, 0.000000000000000000000013771984, 0.0000000000000000000000022062083].into(),
            [0.000000000000000000000013807439, 0.000000000000000000000018596945, -0.000000000000000000000001784406].into(),
            [0.000000000000000000000014174896, -0.000000000000000000000003200329, 0.000000000000000000000004664615].into(),
            [0.000000000000000000000013685897, 0.0000000000000000000000046402988, 0.0000000000000000000000022509113].into(),
        ];
        let _= parry3d::transformation::convex_hull(&points[..]);
    }

Backtrace:

running 1 test
thread 'meshutil::test::chull_panic' panicked at 'called `Option::unwrap()` on a `None` value', C:\Users\fake\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.0\src\transformation\convex_hull3\initial_mesh.rs:151:74
stack backtrace:
  [...]
  16:     0x7ff71159ea69 - enum$<core::option::Option<usize>>::unwrap<usize>
                               at /rustc/a178d0322ce20e33eac124758e837cbd80a6f633\library\core\src\option.rs:388
  17:     0x7ff7115ed82b - parry3d::transformation::convex_hull3::initial_mesh::get_initial_mesh
                               at C:\Users\fake\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.0\src\transformation\convex_hull3\initial_mesh.rs:151
  18:     0x7ff711590a2b - parry3d::transformation::convex_hull3::convex_hull::convex_hull
                               at C:\Users\fake\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.0\src\transformation\convex_hull3\convex_hull.rs:26
  19:     0x7ff7115415b6 - evogame::meshutil::test::chull_panic
                               at C:\pbox\dev\rust\evogame\src\meshutil.rs:113
  [...]

This bug has been around for a long time (inherited from ncollide). It looks like the problem is due to convex_hull_utils::normalize() . The bbox is nonempty, but in (max-min.norm()), the squared components underflow to 0, so let diag = na::distance(&aabb.mins, &aabb.maxs); returns 0, and then normalize divides by zero.

Later, support_point_id() fails because the points are all NaN, so all points fail the test for finding the support point.

Possible fixes:

• Could be fixed by checking explicitly for that case (AABB.diagonal length = 0) and returning a 1-point degenerate hull in that case. (Just skipping the division would do it, since the eigenvalues would be near 0 and get_initial_mesh() would treat it as a 0-D case instead of 3-D).
• The dimensionality count (from the eigenvalues) counts NaN as a nonzero dimension, so this ends up in the 3D case instead of the 0D case. It could be fixed to not count NaN as a nonzero eigenvalues.

(I'm not actually sure why the normalization is being done in the first place; convex hull is in principle an exact operation, and normalizing the overall shape doesn't necessarily improve the conditioning of any particular triangles. It also means the returned points are no longer a subset of the input points. Maybe there are a bunch of epsilons in the code that assume approximately-unit overall scale?)