search

WaDelma / poisson

n-dimensional poisson-disk distribution generation for rust.
MIT License
10 stars 8 forks source link

Allow non-uniform point densities #5

Open WaDelma opened 8 years ago

WaDelma commented 8 years ago

Have some way to specify somekind of non-uniformity for point densities.

ConnyOnny commented 7 years ago

How about accepting a closure of the form

Fn(V) -> F

allowing for a different minimum radius at each position in space (V and F according to the template parameters you usually use).

Of course, this is not perfect, the sample position for the function will depend only on the existing Poisson sample, but I don't know how to sample between a point and the next point, when it is the next point we want to generate…

I don't know about Ebeida, but with Bridson this will be very simple to implement.

ConnyOnny commented 7 years ago

There's also the possibility for anisotropy. But it's not so easy to make an interface for that and I don't know if anyone will ever use this…

WaDelma commented 7 years ago

Yeah that was what I thought first too, but I was unsure how to actually make it work well.

If there is sudden changes on the minimum radii the result might end up completely different what the closure tells the algorithm to do.

Here is a paper the talks about poisson-disk distributions with variable radii.

ConnyOnny commented 7 years ago

According to that paper, what I proposed is called "Prior" method and works okay. I think the other options from the paper may not be easy to implement with Bridson. If somebody wants to implement another method (Current, Bigger or Smaller), we can add another enum option.

ConnyOnny commented 7 years ago

Oh and if there are sudden changes in the function, there's really not much we can do about it. Garbage in -> garbage out.

WaDelma commented 7 years ago

I tried to implement this by making radius in Builder to be a closure that takes coordinate and returns the radius, but I ran into problem that needs impl Trait(rust-lang/rust#34511) to work.

Taking it as closure means that Builder needs to parametrise on the closure. This works fine if the user provides the closure. If you try to still provide way to just take constant in and use that as radius, you need to construct constant returning closure in the function, which type is unnameable and thus needs ìmpl Trait.

So we can either wait for impl Trait to stabilise or just get rid of constant constructors.

Also taking just closure isn't enough to Bridsons algorithm allow varying radii: Because it uses grid to speed up spatial searches, maximum radius used is also needed to calculate right cell size (And grid needs to be changed so it can contain multiple samples. Propably small size optimized vector?). (I also would really like to enforce that the closure returns valid values for radii, but thats propably pipe dream. Oh well)

ConnyOnny commented 7 years ago

Would it help to box the closure? If so, would that be so bad?

WaDelma commented 7 years ago

Yeah, that would be possibility... I wasn't considering it, because the closure is so small for the uniform case: just returning value and having that impose dynamic dispatch seem silly.

The times you need to call the closure is exactly the amount of samples (in the prior method) so O(n) which doesn't change algorithms complexity. If we also allowed other variations, it would be more important (still O(n), but would be called once for each try).