# GPU Procedural placement - Creating evenly distributed sampling points

I am working on a procedural placement system on the GPU, inspired by the work done by Guerrilla Games in Horizon Zero Dawn: https://www.guerrilla-games.com/read/gpu-based-procedural-placement-in-horizon-zero-dawn

On slide 28 they are showing a sampling pattern, which they use to determine whether to place an object or not. The pattern consists of evenly distributed points, each with a threshold value, which they test a artist-authored density map against.

The threshold values are picked, such that they are evenly distributed and maximize the distance to neighboring sample points.

I have looked into circle packing on a unit square to generate the sampling points, and this seems fine.

The point I am having trouble with is how to create the threshold values with the specified requirement (even distribution between 0 and 1 and maximizing the distance to neighbors). Can someone point me in the right direction, as to how to achieve this? Thanks in advance.

• Looks like a blue noise point set. You can try Lloyd relaxation. Jan 3 '20 at 14:26
• Thanks for your comment. As I said, the generation of the sampling parts is more or less clear to me. I am more having problems with the threshold values. Does Lloyd relaxation help with that? I guess it at least gives a more explicit notion of which points are neighbors (thanks to the voronoi graph). Jan 4 '20 at 9:16
• I think that maximizing the distance to the neighbours is with respect to the sample locations. The values that the samples hold (threshold values) seem to be required to be evenly distributed. The problem is that this can mean too many things, and just from the slides it's not obvious which meaning exactly they have in mind. I would go with uniform random thresholds. Jan 4 '20 at 9:42
• Sorry maybe I failed to describe this in much detail. A couple of slides earlier they speak about ordered dithering and that there the threshold values are picked such that they maximize the distance to neighboring values. In the speaker notes for this presentation they then say that they apply the same to their own sampling pattern. Jan 4 '20 at 10:48
• Ordered dither is usually defined on a rectilinear grid however. My best guess would be blue noise on a blue noise distributed pointset: $\sum_k v_k\delta(x - v_k)$ having a blue noise spectrum, but I am nkt aware how to optimize this efficiently on the GPU. Some pseudo-Jacobi method for example. All in all, the slides simply do not provide enough details, look for papers. Jan 4 '20 at 11:11