2c:null 2d:["$","title",null,{"children":"Stippling of 2D Scalar Fields | Jochen Görtler | Observable"}] 32:T4c5,class Grid { // `func` has to be a 2d function constructor([n, m], func, [xmin, xmax], [ymin, ymax], [vmin, vmax]) { this.width = n; this.height = m; this.x = d3.scaleLinear().domain([0, this.width]).range([xmin, xmax]); this.y = d3.scaleLinear().domain([0, this.height]).range([ymax, ymin]); // Turn upside down this.color = d3.scaleSequentialSqrt(d3.interpolateYlGnBu).domain([vmin, vmax]); this.values = new Array(this.width * this.height); // populate array with values for (var j = 0, k = 0; j < this.height; ++j) { for (var i = 0; i < this.width; ++i, ++k) { this.values[k] = func(this.x(i), this.y(j)); } } } get(i, j) { return this.values[i + j * this.width]; } pos_at_index(idx) { return [idx % this.width, idx / this.width | 0]; } to_context() { let ctx = DOM.context2d(this.width, this.height); ctx.canvas.width = this.width; ctx.canvas.height = this.height; for (let u of d3.range(this.width)) { for (let v of d3.range(this.height)) { ctx.fillStyle = this.color(this.get(u,v)); ctx.fillRect(u,v,1,1); } } ctx.canvas.id = "canvas" return ctx; } }33:T1172,class Stippling { constructor(grid) { this.grid = grid; this.radius_extent = [3, 3]; this.threshold = 0.4; this.delta_threshold = 0.01; // we initialize the algorithm with random stipples this.stipples = this.random_stipples(100); } // enables adaptive stipple sizes, depending on the underlying density. with_adaptive_radius(min_radius, max_radius) { this.radius_extent = [min_radius, max_radius]; return this; } // returns the thresholds for split and delete thresholds(radius) { const area = Math.PI * radius * radius; return [ (1.0 + this.threshold / 2.0) * area, (1.0 - this.threshold / 2.0) * area ]; } // generates `num` random stipples on top of the grid. random_stipples(num) { const stipples = new Array(num); const xran = d3.randomUniform(0, this.grid.width); const yran = d3.randomUniform(0, this.grid.height); for (var i = 0; i < num; ++i) { stipples[i] = [xran(), yran()]; stipples[i].radius = this.radius_extent[0]; } return stipples; } // performs one iteration of the stippling algorithm iterate() { const delaunay = d3.Delaunay.from(this.stipples), voronoi = delaunay.voronoi([0, 0, this.grid.width, this.grid.height]); // initialize densities for(let i = 0; i < this.stipples.length; i++) { const st = this.stipples[i]; st.density = 0; st.moment10 = 0; st.moment01 = 0; st.moment11 = 0; st.moment20 = 0; st.moment02 = 0; } // compute the density and the weighted centroid of each cell var found = 0; for(let y = 0; y < this.grid.height; y++) { const line = y * this.grid.width; for(let x = 0; x < this.grid.width; x++) { found = delaunay.find(x, y, found); const st = this.stipples[found]; const val = this.grid.values[x + line]; st.density += val; // Moment00 const xval = x*val; const yval = y*val; st.moment10 += xval st.moment01 += yval st.moment11 += x * yval; st.moment20 += x * xval; st.moment02 += y * yval; } } const grid_extent = d3.extent(this.grid.values); const density_to_radius = d3 .scaleLinear() .domain(grid_extent) .range(this.radius_extent); const deleted = []; const splitted = []; const relaxed = []; for (let i = 0; i < this.stipples.length; i++) { const polygon = voronoi.cellPolygon(i); if (!polygon) continue; const st = this.stipples[i]; const density = st.density; // determine point size based on average intensity const area = Math.abs(d3.polygonArea(polygon)) || 1; const avg_density = density / area; const radius = density_to_radius(avg_density); const [split_threshold, delete_threshold] = this.thresholds(radius); if (density < delete_threshold * grid_extent[1]) { // Delete deleted.push[i]; // nop } else if (density > split_threshold * grid_extent[1]) { // Split const centroid = d3.polygonCentroid(polygon); const cx = centroid[0]; const cy = centroid[1]; const dist = Math.sqrt(area / Math.PI) / 2.0; const x = st.moment20 / density - cx * cx; const y = 2 * (st.moment11 / density - cx * cy); const z = st.moment02 / density - cy * cy; var orientation = Math.atan2(y, x - z) / 2.0; var deltaX = dist * Math.cos(orientation); var deltaY = dist * Math.sin(orientation); // re-use arrays to reduce GC pressure st[0] = cx + deltaX; st[1] = cy + deltaY; st.radius = radius; centroid[0] -= deltaX; centroid[1] -= deltaY; centroid.radius = radius; splitted.push(st); splitted.push(centroid); } else { // Relax st[0] = st.moment10 / density; st[1] = st.moment01 / density; st.radius = radius; relaxed.push(st); } } // we increase the threshold with each iteration for faster convergence this.threshold = this.threshold + this.delta_threshold; this.stipples.length = relaxed.length + splitted.length; for(let i = 0; i < relaxed.length; i++) this.stipples[i] = relaxed[i]; for(let i = 0; i < splitted.length; i++) this.stipples[i + relaxed.length] = splitted[i]; return { deleted, relaxed, splitted }; } }34:[] 30:{"id":"9933a5a4d721beaf","slug":"stippling-of-2d-scalar-fields","title":"Stippling of 2D Scalar Fields","thumbnail":"8dd3dded955a54c3fe9080662bf5eb6dcf5576d2cc7ca41537c3f886ae3266c4","access_level":"public","create_time":"$D2019-04-16T07:52:05.126Z","update_time":"$D2021-04-22T12:53:38.766Z","view_time":null,"first_public_time":"$D2019-04-22T09:37:46.220Z","has_unpublished_edits":null,"fork":false,"stars":27,"starred":false,"owner":{"type":"team","id":"e571624afcb07048","login":"grtlr","name":"Jochen Görtler","avatar_url":"https://avatars-next.observableusercontent.com/a03922ad3fe91ba57e14428d7078f39d27d951b45adb9ee0910fbfabe810c133","tier":"starter_2024"},"version":452,"publish_version":452,"role":null,"authored":false,"authors":[{"type":"individual","id":"bb5bce7199c6ac19","login":"grtlr","name":"Jochen Görtler","avatar_url":"https://avatars-next.observableusercontent.com/a03922ad3fe91ba57e14428d7078f39d27d951b45adb9ee0910fbfabe810c133","tier":null}],"members":[{"type":"individual","id":"bb5bce7199c6ac19","login":"grtlr","name":"Jochen Görtler","avatar_url":"https://avatars-next.observableusercontent.com/a03922ad3fe91ba57e14428d7078f39d27d951b45adb9ee0910fbfabe810c133","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":7,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Stippling of 2D Scalar Fields","cells":[{"id":0,"value":"md`# Stippling of 2D Scalar Fields`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"md`\nThis notebook shows an example of using the Linde–Buzo–Gray stippling algorithm to abstract two-dimensional scalar fields.\nPlease note that this is not the actual implementation but rather a simplified version of the actual algorithm—a more detailed description of our method can be found in the [paper](https://ieeexplore.ieee.org/document/8667696).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":429,"value":"md`\nFor demonstration purposes, we will use the [Himmelblau](https://en.wikipedia.org/wiki/Himmelblau%27s_function) function, which is often used to benchmark optimization algortihms.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"himmelblau = (x, y) => Math.pow(x * x + y - 11, 2) + Math.pow(x + y * y - 7, 2);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":238,"value":"md`\nWe can put the values in a grid and visualize the function using color.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"himmelblau_grid = new Grid([400,400], himmelblau, [-5,5], [-5,5], [0, 800]);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"md`\nFor ${tex`x \\in [${himmelblau_grid.x.range()[0]},${himmelblau_grid.x.range()[1]}]`} and ${tex`y \\in [${himmelblau_grid.y.range()[1]},${himmelblau_grid.y.range()[0]}]`} it looks like this:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"viewof canvas = {\n return himmelblau_grid.to_context().canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":135,"value":"md`\nNow, our goal is to create a stippled abstraction of this function. For this we will use an adaptation of the Linde–Buzo-Gray stippling algorithm.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":355,"value":"md`We are now ready to iterate the algorithm.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":339,"value":"stipples_new = {\n const lbg_stippling = new Stippling(himmelblau_grid);\n lbg_stippling.with_adaptive_radius(1,5);\n let status = lbg_stippling.iterate();\n const svg = d3.select(DOM.svg(himmelblau_grid.width, himmelblau_grid.height));\n \n while(status.splitted.length != 0 || status.deleted.length != 0) {\n console.log(status);\n status = lbg_stippling.iterate();\n const circles = svg.selectAll(\"circle\")\n .data(lbg_stippling.stipples);\n\n circles.enter().append(\"circle\")\n .attr(\"r\", d => d.radius)\n .attr(\"cx\", d => d[0])\n .attr(\"cy\", d => d[1]);\n\n circles.merge(circles)\n .attr(\"r\", d => d.radius)\n .attr(\"cx\", d => d[0])\n .attr(\"cy\", d => d[1]);\n\n circles.exit().remove();\n yield Promises.delay(100, svg.node());\n }\n yield svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":175,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":177,"value":"md`Below, we define a \\`Grid\\` type and the stippling algorithm, which we use to create the examples above.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":319,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":424,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"md`\nBelow we just include [d3](https://github.com/d3/d3) for convenience:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":154,"value":"d3 = require(\"d3@5\", \"d3-delaunay@5\");","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 31:"$30:body"