Incremental generation & other ideas

[cdlm]

As you've seen I started my own implementation as a toy, to learn Rust. My idea was to make an interactive / generative art sort of thing, so there were a few features I imagined:

1. incremental generation: an iterator on successive points, rather than a Vec
2. insertion of arbitrary points
3. arbitrary generation perimeter: here it could mean predicating candidate points instead of just generating them uniformly in the whole unit hypercube
4. non-uniform point density

Do any of those match your use-case? Any clues on how they could be best implemented?

[WaDelma]

What I am currently doing myself is implementing tile based Poisson disk distributions [1], but I would be interested on implementing these features to my library too.
The changes that are required for the tile algorithm and which I have already done locally requires giving the generator method arbitary point set as parameter and an predicate that restricts new the points to non-square shape. So those are already pretty close to what you want, but without the incremental part. Have to think how the incrementality would be implemented.

[1] Lagae, Ares, and Philip Dutré. "An alternative for Wang tiles: colored edges versus colored corners." ACM Transactions on Graphics (TOG) 25.4 (2006): 1442-1459.

[WaDelma]

I made initial implementation of incremental generation: https://github.com/WaDelma/poisson/tree/incremental

[cdlm]

I've pushed my test code in a clean branch of my repo: https://github.com/cdlm/poisson-surface.rs/blob/wadelma/src/main.rs

If you run it, you will see points appear all over the window. But in Mike Bostock's implementation, new points only appear in the neighbourhood of existing ones, and the point set grows from there. I guess that's what your subdivide method is for, to have a more or less uniform distribution even if it's not complete?

[WaDelma]

The Ebeidas et al algorithm that I have implemented works differently to Bridsons' algorithm that Bostock/Davies have implented. Where Bridsons' algorithm starts from one point and adds points randomly based on it, the Ebeidas' algorithm can been seen as optimisation of naive dart throwing algorithm where new points don't directly relate to old ones.

What Ebeidas' algorithm does is that it splits the space in to a grid in which each cell can only contain at most one sample (their dimensions are chosen depending on the radius). In one iteration certain amount of samples are tried to random position of random cell of the grid. After those tries each cell is subdivided to half for each dimension same way as in quadtree/octree and cells that are covered by existing samples are discarded. This is continued until there is no cells left.

If you need same kind of effect as in the Bridson's, then Ebeidas isn't really useful as it's basically just fast way of doing dart throwing... :/

Potentially I could add Bridson's algorithm to this library, so both algorithms would be under same API...

[cdlm]

I think they are both really close: my implementation of Bridson's algo (not the Rust one) also uses a similar grid for proximity lookup, and a list of active "seed" points or cells. So the data is the same or really similar, and only the behavior differs.

[WaDelma]

I started implementing arbitary point insertion, but I stumbled upon design choise I am not sure about. I am currently implementing insert method for the iterator that produces the points. But when the iterator should output added points or should it even output them?
Not outputing inserted points would potentially be most flexible choise: The user could then choose if they want to output them, provided they can store clones of the points somewhere themselves.
Perhaps have different methods for both?
Also it seems bit wrong to think iterator as a container of sorts.

[WaDelma]

I have implemented and first 2 ideas in this issue and opened #4 and #5 for the rest.

[cdlm]

Nice ! I have little time to play with this these days, sadly… but I hope to come back to it

[WaDelma]

Np. Was fun to work with it (and completely redesign the API 3 times xD). Btw I also implemented Bridsons algorithm.