23:null 24:["$","title",null,{"children":"An improvement to Bridson's Algorithm for Poisson Disc sampling. | Martin Roberts | Observable"}] 29:T545,md`# An improvement to Bridson's Algorithm for Poisson Disc sampling. In many applications in graphics, particularly rendering, generating samples from a blue noise distribution is important. Poisson-disc sampling produces points that are tightly-packed, but no closer to each other than a specified minimum distance, resulting in a more natural pattern. To create such distributions, most people use Mitchell's best candidate, however, Bridson's 2007 algorithm is much faster as it is only O(n) time, rather than O(n^2) for Mitchell's. However, I show how, by changing only a few lines of code, we can make Bridson's algorithm much more efficient (ie, about 20x faster!). This new version is not only much faster, but it produces higher quality point distributions, as it allows for more tightly packed and consistent point distributions. The animation below illustrates how the frontier of candidate points is selected in this new algorithm. Comparing this with [Mike Bostock's visualization](https://observablehq.com/@mbostock/poisson-disc-distribution) of the Bridson algorithm, makes it clear how these two algorithms differ. See also [Jason Davies' implementation ](https://www.jasondavies.com/poisson-disc/) of Bridson's original algorithm which uses [Bridson’s original 2007 algorithm](https://dl.acm.org/citation.cfm?id=1278807).` 2a:T817,function* poissonDiscSampler(width, height, radius) { const k = 4; // maximum number of samples before rejection const radius2 = radius * radius; const cellSize = radius * Math.SQRT1_2; const gridWidth = Math.ceil(width / cellSize); const gridHeight = Math.ceil(height / cellSize); const grid = new Array(gridWidth * gridHeight); const queue = []; // Pick the first sample. yield {add: sample(width / 2 , height / 2, null)}; // Pick a random existing sample from the queue. pick: while (queue.length) { const i = Math.random() * queue.length | 0; const parent = queue[i]; const seed = Math.random(); const epsilon = 0.0000001; // Make a new candidate. for (let j = 0; j < k; ++j) { const a = 2 * Math.PI * (seed + 1.0*j/k); const r = radius + epsilon; const x = parent[0] + r * Math.cos(a); const y = parent[1] + r * Math.sin(a); // Accept candidates that are inside the allowed extent // and farther than 2 * radius to all existing samples. if (0 <= x && x < width && 0 <= y && y < height && far(x, y)) { yield {add: sample(x, y), parent}; continue pick; } } // If none of k candidates were accepted, remove it from the queue. const r = queue.pop(); if (i < queue.length) queue[i] = r; yield {remove: parent}; } function far(x, y) { const i = x / cellSize | 0; const j = y / cellSize | 0; const i0 = Math.max(i - 2, 0); const j0 = Math.max(j - 2, 0); const i1 = Math.min(i + 3, gridWidth); const j1 = Math.min(j + 3, gridHeight); for (let j = j0; j < j1; ++j) { const o = j * gridWidth; for (let i = i0; i < i1; ++i) { const s = grid[o + i]; if (s) { const dx = s[0] - x; const dy = s[1] - y; if (dx * dx + dy * dy < radius2) return false; } } } return true; } function sample(x, y, parent) { const s = grid[gridWidth * (y / cellSize | 0) + (x / cellSize | 0)] = [x, y]; queue.push(s); return s; } }2b:[] 27:{"id":"cceac657c07b5234","slug":"an-improvement-on-bridsons-algorithm-for-poisson-disc-samp/2","title":"An improvement to Bridson's Algorithm for Poisson Disc sampling.","thumbnail":"f6891a3832dbe33196816ebefdf9838641665a93a044632f0e6d7d014e7a59d2","access_level":"public","create_time":"$D2019-11-29T05:21:32.350Z","update_time":"$D2020-05-06T08:25:32.653Z","view_time":null,"first_public_time":"$D2019-11-29T05:28:00.251Z","has_unpublished_edits":null,"fork":{"id":"b968ef8147786375","slug":"poisson-disc-distribution","title":"Bridson’s Algorithm","owner":{"id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock"}},"stars":25,"starred":false,"owner":{"type":"team","id":"ee6ab7b050e04307","login":"techsparx","name":"Martin Roberts","avatar_url":"https://avatars-next.observableusercontent.com/c135045dd60a98c5ee9df7371be81e7222bbb1a597a4df3b3e3e1a5b5e0cc67d","tier":"starter_2024"},"version":295,"publish_version":295,"role":null,"authored":false,"authors":[{"type":"individual","id":"e194e76791bd232e","login":"techsparx","name":"Martin Roberts","avatar_url":"https://avatars-next.observableusercontent.com/c135045dd60a98c5ee9df7371be81e7222bbb1a597a4df3b3e3e1a5b5e0cc67d","tier":null}],"members":[{"type":"individual","id":"e194e76791bd232e","login":"techsparx","name":"Martin Roberts","avatar_url":"https://avatars-next.observableusercontent.com/c135045dd60a98c5ee9df7371be81e7222bbb1a597a4df3b3e3e1a5b5e0cc67d","tier":null,"role":"editor"}],"comments":[{"id":"8ae85c747aaf2674","reply_to_id":null,"content":"This version seems to cause more 'rivers' in the points than the original (easier to see if you turn off the lines). I think throwing in some radius variation helps. Here was my fiddling, https://observablehq.com/@jrus/bridson-fork/2\n\nwe have been discussing at https://d3js.zulipchat.com/#narrow/stream/273725-D3/topic/d3-force.2C.20fill.20a.20shape","create_time":"$D2021-04-26T20:36:08.363Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"ddd7235babc79ce0","login":"jrus","name":"Jacob Rus","avatar_url":"https://avatars-next.observableusercontent.com/c33dbeed76527c50e64208b0e005e0b6e54a3bef2a14ea6a823f1c7de4867662","tier":null}}],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":10,"collection":null,"type":"notebook","body":{"titling":"auto","title":"An improvement to Bridson's Algorithm for Poisson Disc sampling.","cells":[{"id":1,"value":"$29","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":236,"value":"viewof replay = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"chart = {\n const height = 600;\n const svg = d3.select(DOM.svg(width, height));\n \n replay;\n \n for (const event of poissonDiscSampler(width, height, 10)) {\n if (event.add) {\n event.parent && svg.insert(\"line\", \"circle\")\n .attr(\"x1\", event.parent[0])\n .attr(\"y1\", event.parent[1])\n .attr(\"x2\", event.add[0])\n .attr(\"y2\", event.add[1])\n .attr(\"stroke\", \"#999\");\n\n svg.append(\"circle\")\n .attr(\"id\", `point-${event.add.map(Math.round).join(\"-\")}`)\n .attr(\"r\", 0)\n .attr(\"cx\", event.add[0])\n .attr(\"cy\", event.add[1])\n .transition()\n .ease(d3.easeLinear)\n .attr(\"r\", 3)\n .transition()\n .attr(\"fill\", \"#f00\");\n } else if (event.remove) {\n svg.select(`#point-${event.remove.map(Math.round).join(\"-\")}`)\n .transition()\n .ease(d3.easeLinear)\n .attr(\"fill\", \"#999\")\n .attr(\"r\", 2);\n }\n \n yield svg.node();\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"$2a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W2b","stdlib":"1"}} 28:"$27:body"