31:[{"id":"c8f646fc0e1ac1f2a6bc400765a0521a5d74fa75380af607cb88c6300cf68d768398cd4277386268aee99d43f610b2475c27d0bd825f409d6c0a15bbeaa93d99","href":"https://static.observableusercontent.com/files/c8f646fc0e1ac1f2a6bc400765a0521a5d74fa75380af607cb88c6300cf68d768398cd4277386268aee99d43f610b2475c27d0bd825f409d6c0a15bbeaa93d99","name":"seamless_voronoi@2.svg","type":"image/svg+xml","lastModified":1605393657894.73,"size":9168}] 2f:{"title":"Infinite Voronoi tessellations","cells":[{"id":0,"value":"# Infinite Voronoi tessellations","pinned":false,"hidden":false,"mode":"md"},{"id":547,"value":"Let's play with infinite Voronoi tessellations ! The method is to tile the plan with instances of a unique Voronoi sample, computed such as it can be juxtaposed seamlessly.","pinned":false,"hidden":false,"mode":"md"},{"id":1204,"value":"To compute a cycling Voronoi sample, you have to take into account the siblings of each generator in the 8 surrounding clones of the generator set.","pinned":false,"hidden":false,"mode":"md"},{"id":1188,"value":"{\n const sketch = svg`${await FileAttachment(\"seamless_voronoi@2.svg\").text()}`;\n sketch.style.height = 300;\n return sketch;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3,"value":"## Tools","pinned":false,"hidden":false,"mode":"md"},{"id":553,"value":"First we need a Voronoi implementation that we can feed into a GPU kernel. The implementation is naive, but ensures the generated sample cycles seamlessly through its borders.","pinned":false,"hidden":false,"mode":"md"},{"id":33,"value":"voronoiAlgo = function(gens, nb) {\n let min = +Infinity;\n let index = 0;\n const { x, y } = this.thread;\n const { x: dim1, y: dim2 } = this.output;\n const [hd1, hd2] = [dim1 / 2, dim2 / 2];\n\n for (let k = 0; k < nb; k++) {\n const [gx, gy] = gens[k];\n let [dx, dy] = [x - gx, y - gy];\n // the following 2 lines ensure the sample\n // cycles seamlessly through its borders\n dx += dx > hd1 ? -dim1 : dx < -hd1 ? dim1 : 0;\n dy += dy > hd2 ? -dim2 : dy < -hd2 ? dim2 : 0;\n const sqdist = dx * dx + dy * dy;\n if (sqdist < min) {\n index = k;\n min = sqdist;\n }\n }\n\n return index;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":738,"value":"The corresponding kernel is shared among all renderings, to avoid consuming too many webGL contexts.","pinned":false,"hidden":false,"mode":"md"},{"id":703,"value":"voronoiKernel = {\n const gpu = new GPU.GPU();\n const options = { dynamicOutput: true, dynamicArguments: true };\n return gpu.createKernel(voronoiAlgo, options);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":557,"value":"Then we need a rendering kernel function that fills the user space with juxtaposed instances of a provided sample:","pinned":false,"hidden":false,"mode":"md"},{"id":358,"value":"renderAlgo = {\n let xs; // Allows injecting function in kernel while not pissing Observable's parser\n return function(sample, dims, viewbox, colors) {\n const [dim1, dim2] = dims;\n const [xmin, ymin, scale] = viewbox;\n const { x, y } = this.thread; // canvas space\n const [X, Y] = [xmin + x * scale, ymin - y * scale]; // user space\n const [I, J] = [xs(X, dim1), xs(Y, dim2)]; // sample space\n const [r, g, b] = colors[sample[J][I]];\n this.color(r, g, b);\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1448,"value":"We use a [shared graphical kernel](https://observablehq.com/@ehouais/shared-gpu-js-graphical-shader) to use only one rendering kernel for all interactive voronoi tilings","pinned":false,"hidden":false,"mode":"md"},{"id":1437,"value":"output = [800, 400]","pinned":false,"hidden":false,"mode":"ojs"},{"id":1376,"value":"renderKernel = {\n const gpu = new GPU.GPU();\n // Old-style declaration necessary for kernel injection\n function xs(coord, size) {\n return Math.floor(coord - size * Math.floor(coord / size));\n }\n return sharedGraphicalKernel(gpu, renderAlgo, { output, functions: [xs] });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":564,"value":"Finally, the following function wraps it all by taking an array of generators, computing the associated discrete voronoi sample, and rendering the corresponding tessellation with zoom and pan capabilities.","pinned":false,"hidden":false,"mode":"md"},{"id":623,"value":"vtess = function(dims, colors) {\n let voronoi;\n let viewbox = [[0, 0], [dims[0] * 3, dims[1] * 3]];\n const [W, H] = output;\n const div = html`

`;\n const render = renderKernel(div);\n const vb = ([[xmin, ymin], [xmax, ymax]]) => [xmin, ymax, (xmax - xmin) / W];\n const update = () => render(voronoi, dims, vb(viewbox), colors);\n const updateView = vb => ((viewbox = vb), voronoi && update());\n zoomAndPan2D(div, output, viewbox, updateView);\n return generators => {\n voronoiKernel.setOutput(dims);\n update((voronoi = voronoiKernel(generators, generators.length)));\n return div;\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":567,"value":"## Examples","pinned":false,"hidden":false,"mode":"md"},{"id":572,"value":"All examples can be infinitely zoomed and panned, and double-clicked to be reset to the initial viewbox.","pinned":false,"hidden":false,"mode":"md"},{"id":580,"value":"First a classic random Voronoi:","pinned":false,"hidden":false,"mode":"md"},{"id":465,"value":"mutable generators = [...Array(50)].map((_) => [\n 512 * Math.random(),\n 512 * Math.random()\n])","pinned":false,"hidden":false,"mode":"ojs"},{"id":1133,"value":"genView([512, 512])(generators)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1138,"value":"viewof toggle = {\n const rnd = val => val * Math.random();\n const vectors = [...Array(50)].map(_ => [rnd(6) - 3, rnd(6) - 3]);\n let animate = false;\n const update = () => {\n if (animate) {\n mutable generators = mutable generators.map(([x, y], i) => {\n const [vx, vy] = vectors[i];\n return [(x + vx + 512) % 512, (y + vy + 512) % 512];\n });\n }\n requestAnimationFrame(update);\n };\n update();\n const label = state => (state ? 'stop' : 'animate');\n const div = html``;\n const onClick = e => (div.innerText = label((animate = !animate)));\n div.addEventListener('click', onClick);\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1064,"value":"tess = vtess([512, 512], greyScale(50))","pinned":false,"hidden":false,"mode":"ojs"},{"id":427,"value":"tess(generators)","pinned":false,"hidden":false,"mode":"ojs"},{"id":583,"value":"Then some basic tessellations built from a few well-chosen generator sets:","pinned":false,"hidden":false,"mode":"md"},{"id":891,"value":"set1 = [[0, 0], [100, 100]]","pinned":true,"hidden":false,"mode":"ojs"},{"id":874,"value":"genView([200, 200])(set1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":758,"value":"vtess([200, 200], greyScale(2))(set1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":901,"value":"set2 = [[0, 0], [128, 221], [256, 0], [384, 221]]","pinned":true,"hidden":false,"mode":"ojs"},{"id":857,"value":"genView([512, 443])(set2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":409,"value":"vtess([512, 443], greyScale(4))(set2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":921,"value":"set3 = [[116, 0], [290, 100], [58, 100], [232, 0]]","pinned":true,"hidden":false,"mode":"ojs"},{"id":863,"value":"genView([348, 200])(set3)","pinned":false,"hidden":false,"mode":"ojs"},{"id":750,"value":"vtess([348, 200], greyScale(4))(set3)","pinned":false,"hidden":false,"mode":"ojs"},{"id":930,"value":"set4 = [[50, 50], [150, 150], [100, 100], [50, 150], [150, 50]]","pinned":true,"hidden":false,"mode":"ojs"},{"id":866,"value":"genView([200, 200])(set4)","pinned":false,"hidden":false,"mode":"ojs"},{"id":471,"value":"vtess([200, 200], greyScale(5))(set4)","pinned":false,"hidden":false,"mode":"ojs"},{"id":939,"value":"set5 = [[150, 25], [25, 150], [150, 150], [275, 150], [150, 275]]","pinned":true,"hidden":false,"mode":"ojs"},{"id":868,"value":"genView([300, 300])(set5)","pinned":false,"hidden":false,"mode":"ojs"},{"id":473,"value":"vtess([300, 300], greyScale(5))(set5)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1209,"value":"## Conclusion\n* The Voronoi fun never ends\n* GPU.js rocks !","pinned":false,"hidden":false,"mode":"md"},{"id":782,"value":"## About webGL contexts\nwebGL contexts are a precious resource: on my Mac Chrome, they seems to be limited to 16 by tab, so it would be useful to release the resources that are no longer used. However, gpu.js' kernel.destroy() and gpu.destroy() methods seem to have no immediate effect on the number of active contexts, may be due to the garbage-collected nature of javascript's memory management.","pinned":false,"hidden":false,"mode":"md"},{"id":7,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":23,"value":"GPU = require(\"gpu.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":210,"value":"import { zoomAndPan2D } from \"@ehouais/zoom-and-pan\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1442,"value":"import { sharedGraphicalKernel } from \"@ehouais/shared-gpu-js-graphical-shader\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":628,"value":"greyScale = nb => {\n const grey = val => [val, val, val];\n return [...Array(nb)].map((_, i) => grey(i / (nb - 1)));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":812,"value":"import { SVG } from \"@ehouais/svg-utility\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":854,"value":"genView = dims => {\n const { svg, rect, circle, viewbox } = SVG;\n const r = rect(dims, { fill: 'none', stroke: 'grey' });\n const radius = Math.max(...dims) / 50;\n const toPoint = ([cx, cy]) => circle(radius, { cx, cy });\n const viewBox = viewbox(-10, -10, dims[0] + 10, dims[1] + 10);\n return gens => svg([200, 200], [r, ...gens.map(toPoint)], { viewBox });\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}