rapier It's possible to make `convex

I was able to pass some inputs that made convex_decomposition panic. I was testing it in 2D, and one of the ways to make it panic was to pass several (3 or more) identical points in a row.

Here's the backtrace I've got:

thread 'Compute Task Pool (0)' panicked at 'Matrix index out of bounds.', /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/parry2d-0.5.1/src/query/clip/clip_aabb_line.rs:141:13
stack backtrace:
   0: std::panicking::begin_panic
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/std/src/panicking.rs:541:12
   1: nalgebra::base::ops::<impl core::ops::index::IndexMut<(usize,usize)> for nalgebra::base::matrix::Matrix<T,R,C,S>>::index_mut
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/nalgebra-0.27.1/src/base/ops.rs:69:9
   2: nalgebra::base::ops::<impl core::ops::index::IndexMut<usize> for nalgebra::base::matrix::Matrix<T,R,C,S>>::index_mut
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/nalgebra-0.27.1/src/base/ops.rs:57:14
   3: parry2d::query::clip::clip_aabb_line::clip_aabb_line
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/parry2d-0.5.1/src/query/clip/clip_aabb_line.rs:141:13
   4: parry2d::query::clip::clip_aabb_line::<impl parry2d::bounding_volume::aabb::AABB>::clip_segment
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/parry2d-0.5.1/src/query/clip/clip_aabb_line.rs:14:9
   5: parry2d::transformation::voxelization::voxel_set::VoxelSet::do_compute_exact_convex_hull
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/parry2d-0.5.1/src/transformation/voxelization/voxel_set.rs:244:40
   6: parry2d::transformation::voxelization::voxel_set::VoxelSet::compute_exact_convex_hull
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/parry2d-0.5.1/src/transformation/voxelization/voxel_set.rs:189:9
   7: parry2d::transformation::vhacd::vhacd::VHACD::compute_exact_convex_hulls::{{closure}}
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/parry2d-0.5.1/src/transformation/vhacd/vhacd.rs:518:25
   8: core::iter::adapters::map::map_fold::{{closure}}
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/core/src/iter/adapters/map.rs:82:28
   9: core::iter::traits::iterator::Iterator::fold
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/core/src/iter/traits/iterator.rs:2173:21
  10: <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::fold
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/core/src/iter/adapters/map.rs:122:9
  11: core::iter::traits::iterator::Iterator::for_each
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/core/src/iter/traits/iterator.rs:736:9
  12: <alloc::vec::Vec<T,A> as alloc::vec::spec_extend::SpecExtend<T,I>>::spec_extend
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/alloc/src/vec/spec_extend.rs:40:17
  13: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter_nested::SpecFromIterNested<T,I>>::from_iter
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/alloc/src/vec/spec_from_iter_nested.rs:56:9
  14: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/alloc/src/vec/spec_from_iter.rs:33:9
  15: <alloc::vec::Vec<T> as core::iter::traits::collect::FromIterator<T>>::from_iter
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/alloc/src/vec/mod.rs:2453:9
  16: core::iter::traits::iterator::Iterator::collect
             at /rustc/59216858a323978a97593cba22b5ed84350a3783/library/core/src/iter/traits/iterator.rs:1748:9
  17: parry2d::transformation::vhacd::vhacd::VHACD::compute_exact_convex_hulls
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/parry2d-0.5.1/src/transformation/vhacd/vhacd.rs:516:9
  18: parry2d::shape::shared_shape::SharedShape::convex_decomposition_with_params
             at /Users/mvlabat/.cargo/registry/src/github.com-1ecc6299db9ec823/parry2d-0.5.1/src/shape/shared_shape.rs:204:25

I assume it might be not the only scenario when decomposition can fail if users come up with some other invalid inputs. So I have a couple of questions:

Is it possible to change this function's function signature to return Option or Result, to make the error recoverable?
Is there any reliable way to validate the parameters? They might be coming as user input, panicking in such a case would be undesirable.

Jul 28 '21 10:07 vladbat00

I've just got another panic with a different backtrace.

My polyline is defined as follows:

points: [Vec2(2.4130993, -1.5863237), Vec2(5.3191123, 2.1477852), Vec2(8.482585, 8.418664), Vec2(-0.22556305, 13.561576), Vec2(-6.1814785, 5.8251677), Vec2(-6.716458, 3.5166368), Vec2(-6.397316, 1.1379433), Vec2(-1.9486294, -1.0720501), Vec2(-0.5479183, -3.3834772)]

indices: [[0, 1], [1, 2], ..., [7, 8], [8, 0]]

I use the following VHACDParameters (with resolution set to 256 it doesn't panic, btw):

&VHACDParameters {
    concavity: 0.01,
    resolution: 64,
    ..Default::default()
},

thread 'main' panicked at 'index out of bounds: the len is 0 but the index is 0', C:\Users\mvlabat\.cargo\registry\src\github.com-1ecc6299db9ec823\parry2d-0.5.1\src\shape\convex_polygon.rs:42:12
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/4e282795d7d1d28a4c6c1c6521045ae2b59f3519\/library\std\src\panicking.rs:516
   1: core::panicking::panic_fmt
             at /rustc/4e282795d7d1d28a4c6c1c6521045ae2b59f3519\/library\core\src\panicking.rs:93
   2: core::panicking::panic_bounds_check
             at /rustc/4e282795d7d1d28a4c6c1c6521045ae2b59f3519\/library\core\src\panicking.rs:69
   3: core::slice::index::impl$2::index
             at /rustc/4e282795d7d1d28a4c6c1c6521045ae2b59f3519\library\core\src\slice\index.rs:184
   4: core::slice::index::impl$0::index
             at /rustc/4e282795d7d1d28a4c6c1c6521045ae2b59f3519\library\core\src\slice\index.rs:15
   5: alloc::vec::impl$14::index
             at /rustc/4e282795d7d1d28a4c6c1c6521045ae2b59f3519\library\alloc\src\vec\mod.rs:2435
   6: parry2d::shape::convex_polygon::ConvexPolygon::from_convex_polyline
             at C:\Users\mvlabat\.cargo\registry\src\github.com-1ecc6299db9ec823\parry2d-0.5.1\src\shape\convex_polygon.rs:42
   7: parry2d::shape::shared_shape::SharedShape::convex_polyline
             at C:\Users\mvlabat\.cargo\registry\src\github.com-1ecc6299db9ec823\parry2d-0.5.1\src\shape\shared_shape.rs:261
   8: parry2d::shape::shared_shape::SharedShape::convex_decomposition_with_params
             at C:\Users\mvlabat\.cargo\registry\src\github.com-1ecc6299db9ec823\parry2d-0.5.1\src\shape\shared_shape.rs:205

Aug 01 '21 12:08 vladbat00

I'm not sure if my scenario should be written up as a new issue, since the panic I'm getting is a different one, but I'll throw mine into the ring:

When running decomposition on a cuboid, if using v0.11.1 from crates.io, I get the following trace:

thread 'main' panicked at 'capacity overflow', library\alloc\src\raw_vec.rs:536:5
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/9bc8c42bb2f19e745a63f3445f1ac248fb015e53\/library\std\src\panicking.rs:493
   1: core::panicking::panic_fmt
             at /rustc/9bc8c42bb2f19e745a63f3445f1ac248fb015e53\/library\core\src\panicking.rs:92
   2: core::panicking::panic
             at /rustc/9bc8c42bb2f19e745a63f3445f1ac248fb015e53\/library\core\src\panicking.rs:50
   3: alloc::raw_vec::capacity_overflow
             at /rustc/9bc8c42bb2f19e745a63f3445f1ac248fb015e53\/library\alloc\src\raw_vec.rs:536
   4: alloc::raw_vec::RawVec<T,A>::reserve
   5: parry3d::shape::convex_polyhedron::ConvexPolyhedron::from_convex_mesh
   6: parry3d::shape::shared_shape::SharedShape::convex_decomposition_with_params
   7: parry3d::shape::shared_shape::SharedShape::convex_decomposition
   8: rapier3d::geometry::collider::ColliderBuilder::convex_decomposition
   ...

The message is somewhat different if I reference a local copy of Rapier (7aa94e9):

thread 'main' panicked at 'attempt to subtract with overflow', C:\Users\macgy\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.1\src\shape\convex_polyhedron.rs:119:22
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/9bc8c42bb2f19e745a63f3445f1ac248fb015e53\/library\std\src\panicking.rs:493
   1: core::panicking::panic_fmt
             at /rustc/9bc8c42bb2f19e745a63f3445f1ac248fb015e53\/library\core\src\panicking.rs:92
   2: core::panicking::panic
             at /rustc/9bc8c42bb2f19e745a63f3445f1ac248fb015e53\/library\core\src\panicking.rs:50
   3: parry3d::shape::convex_polyhedron::ConvexPolyhedron::from_convex_mesh
             at C:\Users\macgy\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.1\src\shape\convex_polyhedron.rs:119
   4: parry3d::shape::shared_shape::SharedShape::convex_mesh
             at C:\Users\macgy\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.1\src\shape\shared_shape.rs:269
   5: parry3d::shape::shared_shape::SharedShape::convex_decomposition_with_params
             at C:\Users\macgy\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.1\src\shape\shared_shape.rs:212
   6: parry3d::shape::shared_shape::SharedShape::convex_decomposition
             at C:\Users\macgy\.cargo\registry\src\github.com-1ecc6299db9ec823\parry3d-0.7.1\src\shape\shared_shape.rs:175
   7: rapier3d::geometry::collider::ColliderBuilder::convex_decomposition
             at C:\Users\macgy\Documents\development\foss\rapier\src\geometry\collider.rs:477

What I believe is going on is that decomposition is returning empty lists here. My reference example to reproduce this is shown below:

use rapier3d::prelude::ColliderBuilder;
use rapier3d::na::Point3;

fn main() {
    let points = [
        Point3::new(-0.74, -1.74, 52.3025),
        Point3::new(-0.74, -1.74, -52.3025),
        Point3::new(0.74, -1.74, -52.3025),
        Point3::new(0.74, -1.74, 52.3025),
        Point3::new(-0.74, 1.74, 52.3025),
        Point3::new(-0.74, 1.74, -52.3025),
        Point3::new(0.74, 1.74, -52.3025),
        Point3::new(0.74, 1.74, 52.3025),
    ];
    let indices = [
        [4, 5, 0],
        [5, 1, 0],
        [5, 6, 1],
        [6, 2, 1],
        [6, 7, 3],
        [2, 6, 3],
        [7, 4, 0],
        [3, 7, 0],
        [0, 1, 2],
        [3, 0, 2],
        [7, 6, 5],
        [4, 7, 5]
    ];

    let _collider = ColliderBuilder::convex_decomposition(
        &points,
        &indices,
    ).build();
}

Sep 27 '21 12:09 bellwether-softworks

It's possible to make `convex_decomposition` panic