Algorithm "Bridson" panics with certain parameters

ctbur commented 4 years ago

When using Bridson's algorithm to generate the samples I get the following panic in rare cases:

thread '<unnamed>' panicked at 'Because the sample is [0, 1] indexing it should work.', src/libcore/option.rs:1166:5
stack backtrace:
...
  11: core::option::Option<T>::expect
             at /rustc/625451e376bb2e5283fc4741caa0a3e8a2ca4d54/src/libcore/option.rs:345
  12: poisson::algorithm::bridson::Algo<F,V>::insert_if_valid
             at /home/cyrill/Code/Rust/poisson/poisson/src/algorithm/bridson.rs:143
  13: <poisson::algorithm::bridson::Algo<F,V> as poisson::algorithm::Algorithm<F,V>>::next
             at /home/cyrill/Code/Rust/poisson/poisson/src/algorithm/bridson.rs:66
  14: <poisson::PoissonIter<F,V,R,A> as core::iter::traits::iterator::Iterator>::next
             at /home/cyrill/Code/Rust/poisson/poisson/src/lib.rs:304
...

The algorithm is built with these parameters:

let poisson = Builder::<_, na::Vector2<f32>>::with_radius(0.004, Type::Normal)
        .build(rng, algorithm::Bridson);

I could not find a way to print the state of the XorShiftRng rng, but I can say that the index in bridson.rs that causes the illegal unwrap is (176.0, 154.0).

WaDelma commented 4 years ago

As were using the library in our game project we had noticed that before (currently were working around by catching the exception it by invoking it again with different seed) and I had created issue for it (#16), but that issue is brief and lacks context so I will close it in favor of this one.

This is one reason why I had been hesitant releasing new versions as I hadn't fixed it yet. (Other big one is that I would really like to rewrite the API as it's way too complex for what it is.)

I'll try to look at it fresh mind and see if I can figure it out this time.

WaDelma commented 4 years ago

This can be reproduced with

let seed = [160, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
let rng = SmallRng::from_seed(seed);
let poisson = Builder::<_, na::Vector2<f32>>::with_radius(0.004, Type::Normal)
    .build(rng, algorithm::Bridson)
    .generate();

using rand 0.6.5, nalgebra 0.17.3 and poisson 0.10.0

WaDelma / poisson

Algorithm "Bridson" panics with certain parameters #29