<p>Here are several options:</p>
<ol>
<li><p>Use the jump flood algorithm to construct a voronoi diagram with pixels containing their <span class="math-container">$k$</span> closest seeds. Then use some weighting function between those <span class="math-container">$k$</span> values (e.g. linear for <span class="math-container">$3$</span>, billinear for <span class="math-container">$4$</span>, generalized barycentric coordinates, Shepard interpolation, Gaussians, rbfs, or other).</p>
</li>
<li><p>Pick a convolution kernel (e.g. Gaussian with appropriately large sigma) and convolve your points in a vertical and horizontal pass or using FFT.</p>
</li>
<li><p>Downsample your image until at every pixel you have a sample. At each level produce <code>ceil(N/2)</code> pixels in the given dimension provided the previous had <span class="math-container">$N$</span> pixels. If <span class="math-container">$N$</span> 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 <span class="math-container">$N$</span> 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 <span class="math-container">$0.5$</span>, 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.</p>
</li>
</ol>

CC BY-SA 4.0
2021-12-03T10:45:12.037Z
2021-12-03T15:28:22.123Z
2021-12-03T15:28:22.123Z
lightxbulb
<p>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.</p>
<p>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)?</p>
<p>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.</p>

CC BY-SA 4.0
2021-12-02T17:12:19.953Z
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
lightxbulb
CC BY-SA 4.0
2021-12-03T08:26:30.147Z
@lightxbulb Thanks! I changed the question to make it more specific, this is about poisson disk sampling after all.
TravisG
CC BY-SA 4.0
2021-12-03T09:10:59.540Z
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.
lightxbulb
CC BY-SA 4.0
2021-12-03T10:21:00.440Z
@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.
TravisG
<sampling><interpolation>
Interpolating poisson disk samples in real time
TravisG
# Interpolating poisson disk samples in real time

(Asked by: username_0 on 2021-12-02)

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.

**Tags:** sampling, interpolation

> **Comments:**
> **username_1**: 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  
> **username_0**: @username_1 Thanks! I changed the question to make it more specific, this is about poisson disk sampling after all.  
> **username_1**: 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.  
> **username_0**: @username_1 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.  

---

## 1 answers

### Answer by username_1 on 2021-12-03. Score: 1

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.


---

