4
$\begingroup$

I've seen a number of 2D Poisson disc sampling algorithms online that use a grid to accelerate checking for existing points within the minimum radius [![r][r image]][r link] of a candidate point. For example:

They use a grid of squares of side $\frac{r}{\sqrt2}$, which is the same side length that I intuitively came up with when implementing this myself.

I can see the reason - that is the largest square that cannot contain more than 1 point (assuming the minimum is not attainable - the distance between two points must be strictly greater than $r$).

However, having thought about it further, I adjusted the grid size to $\frac{r}2$ instead. This finer grid means 4 additional squares need to be checked (the 4 corner squares are now within the radius), but the total area covered by the required squares is less, so that on average fewer points will need to go through the Euclidean distance check. The difference can be visualized using the same style as the diagram in the first linked article.

Grid with side length r over root 2 Grid with side length r over 2

For a candidate new point, existing points must be checked in all squares that are within a radius $r$ of the corners of the candidate's square. Here the two grid sizes are shown side by side, to scale, for the same radius $r$. This shows clearly that a significantly smaller area is being checked. Each square is exactly half the area of the previous approach, and even if the 4 outer corner squares are excluded in the previous approach (left image), this still gives an area $2 \cdot \frac{21}{25} = 1.68$ times larger than in the new approach.

My main question is this: Is this approach still correct, and does it give identical results?

I'm also interested to know whether there is any reason to favor the $\frac{r}{\sqrt2}$ approach. Using $\frac{r}{2}$ seems more efficient in time, which seems worth the cost in space efficiency. Is there anything I'm missing?


Images produced with this jsfiddle (in case I need to edit them later).

$\endgroup$
  • $\begingroup$ If you are worried about the square root, you can probably square both sides of the equation. $\endgroup$ – Alan Wolfe Aug 24 '15 at 0:26
  • $\begingroup$ @AlanWolfe I can precompute the square root - it's only ever root 2. My main reason for changing the side length is the significant reduction in area. I just wonder if it broke anything... $\endgroup$ – trichoplax Aug 24 '15 at 0:35
5
+50
$\begingroup$

You approach will work, and in general any square of size < enter image description here will work fine because the invariant "at most 1 point per square" is valid. Extrapolating from your idea, it means that one should get the best reduction in area checks for infinitesimally small squares. But we don't want to do that, right?

There are two reasons why enter image description here is usually better than enter image description here:

  1. How much state do you want to manage? Each square can either be "occupied" or "unoccupied" and contains a pointer to its sample point (if any).

    For very large domains with small r, storage costs can be hard to manage. The problem is much worse if you're working with many dimensions. See Gamito et al.'s paper, Figure 12. Even in 4D you can be severely storage limited.

  2. In your proposed grid size, each candidate points checks 24 squares, as opposed to 20 in the usual method. There is a per-square cost (e.g. checking whether square is occupied and fetching sample point if it is) which increases the overall cost in your method.

Basically, your method works, but it is usually not more efficient.

However, the state of the art in unbiased Poisson-disk sampling techniques actually successively reduces the grid size as the uncovered area reduces. In addition to Gamito et al.'s paper, also see Ebeida et al.'s paper.

P.S. Sorry, I don't know how to do math formatting in Stack Exchange.

$\endgroup$
  • 5
    $\begingroup$ Vote for MathJax formatting on this site. $\endgroup$ – luser droog Sep 2 '15 at 22:28
  • 2
    $\begingroup$ I've added this question to that meta post as an example of further need for MathJax $\endgroup$ – trichoplax Sep 2 '15 at 23:14
  • $\begingroup$ @trichoplax, you used mathurl for pasting images? I'm reading from Android app and i can't check. $\endgroup$ – psicomante Sep 8 '15 at 1:56
  • $\begingroup$ @psicomante yes I used mathurl.com and included the links inline - are they readable on Android? It's the next best thing until we get MathJax activated. $\endgroup$ – trichoplax Sep 8 '15 at 14:05
  • $\begingroup$ @psicomante press edit under the question if you want to see the markup (you need to add .png to the end of the mathurl.com link to make it show as an image here). Any questions just @mention me in Computer Graphics Chat. $\endgroup$ – trichoplax Sep 8 '15 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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