Convex hull produces invalid topology

[werner291]

Hi there,

I put this in the Discord too, but just for good measure I'll open an issue too.

It appears that ConvexPolyhedron::from_convex_hull(&points) produces invalid topology:

use std::fs::File;
use parry3d::na::Point3;
use parry3d::shape::{ConvexPolyhedron, TriMeshFlags};

fn main() {
    let decoded: Vec<f32> = bincode::deserialize_from(File::open("points.bin").unwrap()).unwrap();

    let points : Vec<Point3<f32>> = decoded.chunks(3).map(|c| Point3::new(c[0], c[1], c[2])).collect();

    let convex = ConvexPolyhedron::from_convex_hull(&points)
        .expect("Failed to compute convex hull of mesh");

    let (vertices, mut indices) = convex.to_trimesh();

    let mut convex_mesh = parry3d::shape::TriMesh::new(vertices, indices)
        .expect("Failed to convert convex polyhedron to triangle mesh");

    // This panics.
    convex_mesh.set_flags(TriMeshFlags::HALF_EDGE_TOPOLOGY).unwrap()
}

Here's the input data (remove the .txt, GitHub refused to upload it otherwise)

points.bin.txt

[werner291]

let (vertices, mut indices) = convex.to_trimesh();

    let mut edge_counter = HashMap::new();

    for triangle in indices.iter_mut() {
        for i in 0..3 {
            let edge = [triangle[i], triangle[(i + 1) % 3]];

            edge_counter.entry(edge).and_modify(|e| *e += 1).or_insert(1);

            if edge_counter[&edge] > 1 {
                println!("Edge {:?} is shared by {} triangles", edge, edge_counter[&edge]);
            }
        }
    }

Oh, this is weird:

Edge [31, 22] is shared by 2 triangles
Edge [22, 31] is shared by 2 triangles

If we see edges as undirected, that's one edge showing up 4 times there.

[werner291]

Here's a picture of the bad edge (highlighted in magenta); the renderer doesn't seem to quite know what to do with it either

[werner291]

Here I'm highlighting all triangles where at least one edge is part of a duplicated set:

[ThierryBerger]

I noticed that some points (48 and 53) are similar: [-0.47855484, -0.42577508, 1.4894236] ; I thought this was a source of issue but removing duplicates still lead to the same problem, I could reproduce with a small subset of points (compared to the initial 7000+):

Here triangle 3 in pink is enclosing triangle 4 and 5, which are identical.

I'm aware that this is a very flat example, but as it was detected on a "real" scenario as the original report, I believe this needs serious attention.

Points to reproduce my screenshot are:

[
  [-0.9759494, 0.08367488, 1.1975889]
  [-0.9760843, 0.08125789, 1.2047149]
  [-0.9695144, 0.08282869, 1.2013979]
  [-1.2464869, -0.07542472, 1.6015025]
  [-0.55810887, -0.47650382, 1.4873786]
]

From the visualization, the 4 points seems coplanar, it may be an opportunity to remove the offending point. But I suspect floating point imprecision may still provoke this situation.