23:null 24:["$","title",null,{"children":"A Fork of Roberts’s Tweak to Bridson's Algorithm for Poisson Disc sampling. | Jacob Rus | Observable"}] 29:T46b,chart = { const height = 600; const svg = d3.select(DOM.svg(width, height)); svg.append('rect') .attr('x', 0).attr('y', 0).attr('width', width).attr('height', height) .attr('fill', 'white') replay; let i = 0; mutable points = 0 for (const event of poissonDiscSampler(width, height, 10.28)) { if (event.add) { // event.parent && svg.insert("line", "circle") // .attr("x1", event.parent[0]) // .attr("y1", event.parent[1]) // .attr("x2", event.add[0]) // .attr("y2", event.add[1]) // .attr("stroke", "#999"); svg.append("circle") .attr("id", `point-${event.add.map(Math.round).join("-")}`) .attr("r", 0) .attr("cx", event.add[0]) .attr("cy", event.add[1]) .attr("r", 10.28/2) .attr("fill", "#e00"); } else if (event.remove) { mutable points++; svg.select(`#point-${event.remove.map(Math.round).join("-")}`) .attr("fill", "#333") .attr('opacity', .3) .attr("r", 6); } if (!(i++ % 200)) yield svg.node(); } yield svg.node(); }2a:T9b5,function* poissonDiscSampler(width, height, radius) { const k = 13, // maximum number of samples before rejection m = 5, // a number mutually prime to k radius2 = radius * radius, cellSize = radius * Math.SQRT1_2, gridWidth = Math.ceil(width / cellSize), gridHeight = Math.ceil(height / cellSize), grid = new Array(gridWidth * gridHeight), queue = [], rotx = Math.cos(2 * Math.PI * m/k), roty = Math.sin(2 * Math.PI * m/k); // 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, parent = queue[i], epsilon = 1e-7, t = tanpi_2(2 * Math.random() - 1), q = 1 / (1 + t*t); let dw, dx = q ? (1 - t*t)*q : -1, dy = q ? 2*t*q : 0; // Make a new candidate. for (let j = 0; j < k; ++j) { dw = dx * rotx - dy * roty; // temporary name for dx dy = dx * roty + dy * rotx; dx = dw; const r = radius * (1 + epsilon + 0.65 * Math.random() * Math.random()), x = parent[0] + r*dx, y = parent[1] + r*dy; // 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}; } // fast approximation of tan(πx/2) function tanpi_2 (a) { let b = (1 - a*a); return a * (-0.0187108*b + 0.31583526 + 1.27365776/b); } function far(x, y) { const i = x / cellSize | 0, j = y / cellSize | 0, i0 = Math.max(i - 2, 0), j0 = Math.max(j - 2, 0), i1 = Math.min(i + 3, gridWidth), 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, 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":"56f0b5136ccb6049","slug":"bridson-fork/2","title":"A Fork of Roberts’s Tweak to Bridson's Algorithm for Poisson Disc sampling.","thumbnail":"8d58ee6106cf7765432fe8a45b76fcaf520653b39759060744938aeff245bef5","access_level":"unlisted","create_time":"$D2021-04-26T20:29:37.200Z","update_time":"$D2022-06-05T17:27:21.334Z","view_time":null,"first_public_time":null,"has_unpublished_edits":null,"fork":true,"stars":4,"starred":false,"owner":{"type":"team","id":"9b8a8e177a49059a","login":"jrus","name":"Jacob Rus","avatar_url":"https://avatars-next.observableusercontent.com/c33dbeed76527c50e64208b0e005e0b6e54a3bef2a14ea6a823f1c7de4867662","tier":"starter_2024"},"version":431,"publish_version":431,"role":null,"authored":false,"authors":[{"type":"individual","id":"ddd7235babc79ce0","login":"jrus","name":"Jacob Rus","avatar_url":"https://avatars-next.observableusercontent.com/c33dbeed76527c50e64208b0e005e0b6e54a3bef2a14ea6a823f1c7de4867662","tier":null}],"members":[{"type":"individual","id":"ddd7235babc79ce0","login":"jrus","name":"Jacob Rus","avatar_url":"https://avatars-next.observableusercontent.com/c33dbeed76527c50e64208b0e005e0b6e54a3bef2a14ea6a823f1c7de4867662","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"A Fork of Roberts’s Tweak to Bridson's Algorithm for Poisson Disc sampling.","cells":[{"id":1,"value":"md`# A Fork of Roberts’s Tweak to Bridson's Algorithm for Poisson Disc sampling.\n \nIn 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.\n\nTo create such distributions, most people use Mitchell’s best candidate algorithm, however this takes ${tex`O(n^2)`} time in the number of points, Bridson's 2007 algorithm is much faster, taking ${tex`O(n)`} time.\n\nMartin Roberts made Bridson's algorithm about 10 times faster at the expense of a less uniform point distribution. Here we tweaked his algorithm to be not quite as fast, but produce better distributed points.\n\nSee also [Jason Davies' implementation ](https://www.jasondavies.com/poisson-disc/) of Bridson's original algorithm\nwhich uses [Bridson’s original 2007 algorithm](https://dl.acm.org/citation.cfm?id=1278807).`\n","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":"$29","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"mutable points = 0","pinned":true,"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"