1
$\begingroup$

If I have a regular sampling pattern there typically exist many reasonably fast ways to interpolate the results of the sampling procedure in between the sample locations. For example bilinear or bicubic (etc.) interpolation for a rectangular pattern.

How can I interpolate sample results from poisson disk sampling when the sample locations were randomly generated (but still, all of them are known before the sampling begins)?

If computation time wasn't a concern, I could e.g. find the nearest k neighbours of sample location and then use e.g. barycentric coordinates to interpolate any way I like. But that is too slow for applications like simple texture sampling in a shader.

Improve this question
$\endgroup$
4
  • $\begingroup$ Depends on the basis functions you pick. If you want something piecewise linear, then you would need to triangulate those samples (e.g. Delaunay triangulation) and then use linear interpolation within each. You could also try to quadrilaterize your point set, in which case you could use bilinear interpolation. You could also generate the Voronoi diagram and use generalized barycentric coordinates on that (there are multiple variants). Another possibility is to solve a PDE in order to construct the interpolating function. If you clarify the desired basis functions I can extend this in an answer $\endgroup$
    – lightxbulb
    Commented Dec 2, 2021 at 17:12
  • $\begingroup$ @lightxbulb Thanks! I changed the question to make it more specific, this is about poisson disk sampling after all. $\endgroup$
    – TravisG
    Commented Dec 3, 2021 at 8:26
  • 1
    $\begingroup$ The fact that your samples come from Poisson disk sampling doesn't help me. Prescribe properties your interpolation should adhere to. If you have no idea about what properties you want I can suggest some ad hoc ways to interpolate. $\endgroup$
    – lightxbulb
    Commented Dec 3, 2021 at 9:10
  • $\begingroup$ @lightxbulb I'm sampling textures so guess I'm looking for typical things you expect from texture sampling interpolation: Should match results of uninterpolated sampling at the actual sample points, and in between should give any kind of smooth and steadily increasing or decreasing result based on the distances from each nearby sample point. I'm not concerned too much about quality, triangulating the sample locations and then using, for example, linear interpolation within the triangles would be fine, but it's not doable in practice because it's too slow. $\endgroup$
    – TravisG
    Commented Dec 3, 2021 at 10:21

1 Answer 1

Reset to default
1
$\begingroup$

Here are several options:

  1. Use the jump flood algorithm to construct a voronoi diagram with pixels containing their $k$ closest seeds. Then use some weighting function between those $k$ values (e.g. linear for $3$, billinear for $4$, generalized barycentric coordinates, Shepard interpolation, Gaussians, rbfs, or other).

  2. Pick a convolution kernel (e.g. Gaussian with appropriately large sigma) and convolve your points in a vertical and horizontal pass or using FFT.

  3. Downsample your image until at every pixel you have a sample. At each level produce ceil(N/2) pixels in the given dimension provided the previous had $N$ pixels. If $N$ is even then consider every 2 pixels in that dimension. If both pixels contain samples then average, if only 1 contains a sample then just copy its value, otherwise set 0. That's you restriction operator. You can convolve before applying it. If $N$ is odd the consider every 3 pixels from the finer level (there is some overlap), if all 3 are samples then average all 3, if only 2 of the 3 are samples then average with weight $0.5$, if only 1 is a sample copy its value, otherwise 0. Your samples will thus grow in size at each downsampling until you get an image full of samples at some level. At that point start upsampling and at each level overwrite with the fine samples. This would produce a hierarchy of levels with the finest providing interpolation based on the convolution and interpolation operators you chose at each level.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.