The goal of Poisson disk sampling a set of random points where no 2 points are closer than a certain minimum distance.
The current implementation samples the points in 2D (parallel to the XY plane) and then projects the along the Z axis onto the mesh. This creates the unexpected (and undesirable in most cases?) artefact that "steep" faces have less points.
The proposed implementation does the Poisson disk sampling directly on the input mesh, resulting in an even spread of points over the mesh. I would argue that this should be the default behavior of the Poisson disk sampling method for point distribution.
Before, 2D sampling + Z-projection:
{F9535586}
After, directly sampling on mesh surface:
{F9535588}
The implementation is based on the algorithm described in: [[ https://www.cg.tuwien.ac.at/research/publications/2009/cline-09-poisson/cline-09-poisson-paper.pdf | Dart Throwing on Surfaces (Cline et al. 2009)]]. Including the logarithmic binning to ensure fast random sampling the triangles by area, even for meshes with many triangles and a wide distribution of triangle areas.
TODO:
- Speed up the minimum distance query, this currently loop over all accepted points.
- Improve the termination of the algorithm, currently it just terminates if 100 candidate points have been rejected because they are too close to accepted points. The termination should take into account the Density attribute the user specifies.
- Documentation & cleanup