Convex hull calculation returns incorrect points

[guylapid]

Hi, Thanks for this wonderful crate 😄

I'm experiencing a strange behavior in convex hull calculation. I'm creating a convex hull from a set of points (which indeed form a convex shape). The first time the created hull's points are the original points (up to some minor acceptable float precision differences) as expected. But when I take the points of this hull and create a second convex hull from them, the second hull has incorrect points.

An example that reproduces this behavior:

use ncollide3d::math::Point;
use ncollide3d::shape::ConvexHull;

let points = vec![
    Point::new(1., 0., 0.),
    Point::new(-2., 1., 1.),
    Point::new(2., 1., 1.),
    Point::new(2., 0., 2.),
    Point::new(-2., 0., 2.),
    Point::new(1., 1., 0.),
    Point::new(2., 0., 1.),
    Point::new(-2., 0., 1.),
    Point::new(-1., 0., 0.),
    Point::new(-2., 1., 2.),
    Point::new(2., 1., 2.),
    Point::new(-1., 1., 0.),
];

let hull_1 = ConvexHull::try_from_points(&points).unwrap();
println!("hull_1:");
// This prints pretty much the expected points (up to an acceptable float precision):
for point in hull_1.points() {
    println!("({}, {}, {})", point.x, point.y, point.z);
}

let hull_2 = ConvexHull::try_from_points(hull_1.points()).unwrap();
println!("hull_2:");
// This prints incorrect points:
for point in hull_2.points() {
    println!("({}, {}, {})", point.x, point.y, point.z);
}

In the above code, all of the points of hull_2 are completely different from the original point. For example, a point (2, 0.6875000000000018, 3.66666666666667) is somehow added, which is actually pretty far "outside" of the first convex hull.

I expected the second convex hull to have the same points as the first one (again, up to an acceptable minor float precision difference).

Thanks.

[sebcrozet]

Hi! Thank you for the test case. This looks like a bug. The convex hull computation does some scaling and centering of the data before processing, in order to reduce numerical problems. Though it is supposed to revert these scaling/centering before returning the result to the user. I guess there may be something wrong with this last step.

[guylapid]

I'd be happy to have this issue resolved. I guess you are talking about the normalize, denormalize stuff? I can try to have a deeper look at it and maybe open a fix if you're OK with that. But can you help me understand a little better what exactly is happening there? especially the Facets vs ResultMesh which seem to affect the flow of denormalization. Thanks.

[guylapid]

I just found out that when the improved_fixed_point_support feature is on, the bug doesn't happen, because the eigenvectors are identity vectors in the function get_initial_mesh. So this bug is resolved for me 😄 So if I turn on improved_fixed_point_support, I guess if my convex hulls points are far enough from each other I won't suffer too much accuracy loss as a result of skipping the eigenvectors part, right?