2d:null 2e:["$","title",null,{"children":"Jump Flooding | Claudio Esperança | Observable"}] 33:T51a,buttons = { let div = html`

`; let clear = html``; div.append(clear); clear.onclick = function () { for (let ifbo = 0; ifbo < 2; ifbo++) { gl.bindFramebuffer(gl.FRAMEBUFFER, fbo[(ifbo+1)%2]); gl.clearColor(0.0, 0.0, 0.0, 0.0); gl.clear(gl.COLOR_BUFFER_BIT); } } let voronoi = html``; div.append(voronoi); voronoi.onclick = function () { for (let i = 10, ifbo = 0; i >= 0; i-=1, ifbo = (ifbo+1)%2) { let stepWidth = Math.pow(2, i); gl.bindFramebuffer(gl.FRAMEBUFFER, fbo[(ifbo+1)%2]); gl.viewport (0, 0, width, height); gl.useProgram (distanceProgram.program); twgl.setBuffersAndAttributes(gl, distanceProgram, quadBufferInfo); twgl.setUniforms (distanceProgram, { color1Map: texArray[ifbo*2], color2Map: texArray[ifbo*2+1], pixel: [1.0/width,1.0/height], stepWidth: stepWidth }); twgl.drawBufferInfo(gl, quadBufferInfo, gl.TRIANGLE_STRIP); } } let demobutton = html``; div.append(demobutton); demobutton.onclick = function () { clear.onclick(); mutable startdemo++; } return div; }34:T54f,{ let ifbo = 0; let frame = 0; while (true) { // First step - paint onto textures gl.bindFramebuffer(gl.FRAMEBUFFER, fbo[ifbo]); gl.viewport (0, 0, width, height); gl.useProgram (paintProgram.program); twgl.setBuffersAndAttributes(gl, paintProgram, quadBufferInfo); let { id, color } = mutable paint; twgl.setUniforms (paintProgram, { mouse : mutable mouse, // Mouse position / mousepressed paintId : [(id&0xff)/255.0, (id>>8)/255.0, 0.0, 1.0], // Id to paint paintColor: color, // Color to paint radius : paintRadius // Paint radius in pixels }); twgl.drawBufferInfo(gl, quadBufferInfo, gl.TRIANGLE_STRIP); // Step 2 gl.bindFramebuffer(gl.FRAMEBUFFER, null); let prog = displayType == 'color' ? displayProgram : borderProgram; gl.useProgram (prog.program); twgl.setBuffersAndAttributes(gl, prog, quadBufferInfo); twgl.setUniforms(prog, { color1Map: texArray[ifbo*2], color2Map: texArray[ifbo*2+1], pixel : [1.0/width,1.0/height], // Size of a pixel }); twgl.drawBufferInfo(gl, quadBufferInfo, gl.TRIANGLE_STRIP); yield frame++; } }35:T64a,distancefs = `#version 300 es precision highp float; precision highp int; uniform sampler2D color1Map; uniform sampler2D color2Map; uniform vec2 pixel; // Inverse of the size of the screen uniform float stepWidth; in vec2 v_st; layout(location = 0) out vec4 color1; // Paint ids layout(location = 1) out vec4 color2; // Paint color vec4 nullId = vec4 (0.0); ${packunpack} void main() { vec4 sampleId = texture (color1Map, v_st); if (sampleId.w == 1.0) { // A seed pixel color1 = sampleId; color2 = texture (color2Map, v_st); return; } // Background pixel vec4 bestId = nullId; vec2 bestCoord = vec2 (0.0); float bestDist = 99999.0; for (int y = -1; y <= 1; ++y) { for (int x = -1; x <= 1; ++x) { vec2 sampleCoord = v_st + vec2(x,y)*pixel*stepWidth; vec4 sampleId = texture (color1Map, sampleCoord); if (sampleId == nullId) continue; // Empty background neighbor pixel if (sampleId.w == 0.0) { // Neighbor pixel vec4 tmp = texture (color2Map, sampleCoord); // Coordinate of actual seed stored in color2Map sampleCoord = vec2(unpack2 (tmp.xy), unpack2(tmp.zw)); } float dist = distance(sampleCoord,v_st); if (dist < bestDist) { bestDist = dist; bestCoord = sampleCoord; bestId = vec4 (texture (color1Map, sampleCoord).xy, 0.0, 0.0); } } } color1 = bestId; color2 = vec4(pack2 (bestCoord.x), pack2 (bestCoord.y)); }`36:T7d1,borderfs = `#version 300 es precision highp float; precision highp int; uniform vec2 pixel; // Inverse of the size of the screen uniform sampler2D color1Map; uniform sampler2D color2Map; in vec2 v_st; out vec4 color; ${packunpack} void main() { vec4 paintId = texture(color1Map, v_st); vec4 paintColor = texture(color2Map, v_st); float id = (paintId.x + paintId.y * 256.0)*256.0; if (paintId.w > 0.0) { // A seed color = paintColor; } else if (id > 0.0) { // Not a seed, but neighbor to a seed vec2 seedCoord = vec2(unpack2(paintColor.xy),unpack2 (paintColor.zw)); vec2 seedVector = v_st-seedCoord; float seedDist = length(seedVector); bool farEnough = seedDist > length(pixel) * ${1.001*minMedialDist}; seedVector = seedVector/seedDist; vec3 seedColor = texture (color2Map, seedCoord).rgb; float flag = 1.0; for (int y = -1; y <= 1; ++y) { for (int x = -1; x <= 1; ++x) { vec2 sampleCoord = v_st + vec2(x,y)*pixel*1.0; vec4 neighborId = texture (color1Map, sampleCoord); vec3 neighborColor = texture (color2Map, sampleCoord).rgb; if (neighborId.w == 0.0) { // Neighbor not a seed vec4 tmp = texture (color2Map, sampleCoord); // Coordinate of actual seed stored in color2Map sampleCoord = vec2(unpack2 (tmp.xy), unpack2(tmp.zw)); neighborColor = texture (color2Map, sampleCoord).rgb; } vec2 sampleVector = normalize(v_st - sampleCoord); if (neighborColor != seedColor) flag = 0.0; else if (farEnough && dot (sampleVector,seedVector) < ${medialThreshold}) flag = 0.5; } } //color = vec4(seedColor,1.0); color = vec4 (flag, flag, flag, 1.0); } else { // A background pixel color = vec4 (1.0, 1.0, 1.0, 1.0); } }`37:[] 31:{"id":"2055b6e60d0e31a0","slug":"jump-flooding","title":"Jump Flooding","thumbnail":"c67e3010b4b682fdfa5d1c41f4f545002c53f7b27eb6baf5c438030e61939d84","access_level":"public","create_time":"$D2018-07-16T16:49:08.691Z","update_time":"$D2022-04-11T19:19:45.768Z","view_time":null,"first_public_time":"$D2018-07-26T22:23:02.427Z","has_unpublished_edits":null,"fork":false,"stars":11,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024"},"version":279,"publish_version":279,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Jump Flooding","cells":[{"id":0,"value":"md`# Jump Flooding\n\nA sample implementation of Rong and Tan's paper [Jump flooding in GPU with applications to Voronoi diagram and distance transform\n](https://dl.acm.org/citation.cfm?id=1111431)\n\nIn the demo below you can choose to show the Voronoi cells using a distance-based gradient or the Voronoi cell boundaries along with the discrete medial axis. Note that you can also draw on the canvas with the mouse.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"canvas = {\n let canvas = DOM.canvas(width,height);\n function setMouse(event) {\n if (event.buttons) {\n mutable mouse = [event.offsetX, height - event.offsetY, 1];\n }\n else {\n mutable mouse = [event.offsetX, height - event.offsetY, 0];\n }\n }\n canvas.onmousedown = function(event) {\n let id = mutable paint.id;\n mutable paint = {id : id+1, color: [Math.random(), Math.random(), Math.random(),1.0]};\n setMouse(event);\n };\n canvas.onmousemove = setMouse;\n canvas.onmouseup = setMouse;\n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":165,"value":"viewof displayType = radio({\n title: 'Display distance field as',\n options: [\n { label: 'Color gradient', value: 'color' },\n { label: 'Voronoi and medial axis lines', value: 'lines' },\n ],\n value: 'color'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"viewof voronoiColorAttenuation = slider({\n title : 'Distance field color attenuation',\n min: 0.01,\n max: 0.99,\n value: 0.5,\n precision: 3,\n description: \"Controls how much color is attenuated by distance\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":132,"value":"viewof paintRadius = slider({\n title: 'Brush size',\n min: 1,\n max: 30,\n value: 10,\n precision: 3,\n format:\".1f\",\n description: \"Controls the radius of the brush for painting\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"viewof medialThreshold = slider({\n title: 'Medial gradient threshold',\n min: 0,\n max: 0.9,\n value: 0.5,\n precision: 3,\n format:\".1f\",\n description: \"Maximum value of the dot product between neighbor gradients\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"viewof minMedialDist = slider({\n title: 'Minimum medial distance',\n min: 1,\n max: 20,\n value: 5,\n format: \".1f\",\n description: \"Minimum distance from the border for a pixel to be considered part of the medial axis\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"height = ~~(width * 9 /16)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"mutable mouse = [0,0,0]\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"mutable paint = ({id: 0, color: [1,1,1,1]})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"gl = twgl.getContext(canvas)\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"texArray = {\n // Create textures\n const textures = twgl.createTextures(gl, {\n texture0: { width : width, height : height, minMag : gl.NEAREST, wrap : gl.CLAMP_TO_EDGE },\n texture1: { width : width, height : height, minMag : gl.NEAREST, wrap : gl.CLAMP_TO_EDGE },\n texture2: { width : width, height : height, minMag : gl.NEAREST, wrap : gl.CLAMP_TO_EDGE },\n texture3: { width : width, height : height, minMag : gl.NEAREST, wrap : gl.CLAMP_TO_EDGE } });\n return [textures.texture0, textures.texture1, textures.texture2, textures.texture3];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"fbo = {\n // Create fbos\n var fbo = [gl.createFramebuffer(),gl.createFramebuffer()];\n\n // Configure fbos\n for (var ifbo = 0; ifbo < 2; ifbo++) {\n gl.bindFramebuffer(gl.DRAW_FRAMEBUFFER, fbo[ifbo]);\n gl.framebufferTexture2D(gl.DRAW_FRAMEBUFFER, gl.COLOR_ATTACHMENT0, gl.TEXTURE_2D, texArray[ifbo*2], 0);\n gl.framebufferTexture2D(gl.DRAW_FRAMEBUFFER, gl.COLOR_ATTACHMENT1, gl.TEXTURE_2D, texArray[ifbo*2+1], 0);\n gl.drawBuffers([\n gl.COLOR_ATTACHMENT0,\n gl.COLOR_ATTACHMENT1\n ]);\n\n // Check fbo[0]\n var status = gl.checkFramebufferStatus (gl.DRAW_FRAMEBUFFER);\n if (status != gl.FRAMEBUFFER_COMPLETE) {\n console.log('fb status: ' + status.toString(16) );\n }\n }\n return fbo;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"quadBufferInfo = {\n // A quad covering the whole screen\n const quadArrays = {\n position: { numComponents: 2, data: [-1, -1, 1, -1, -1, 1, 1, 1] },\n textureCoordinates: { numComponents: 2, data: [0, 0, 1, 0, 0, 1, 1, 1] },\n };\n return twgl.createBufferInfoFromArrays(gl, quadArrays);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":221,"value":"mutable startdemo = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":205,"value":"demo = {\n startdemo;\n for (let i = 0; i < 30; i++) {\n mutable mouse = [width*Math.random(),height*Math.random(),1];\n mutable paint = ({id: 1, color: [Math.random(),Math.random(),Math.random(),1]});\n yield Promises.delay(100,i)\n }\n mutable mouse = [0,0,0];\n let voronoi = d3.select(\"#voronoi\").node();\n voronoi.onclick(); \n} ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"md`### Shader programs`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"paintProgram = twgl.createProgramInfo(gl, [vs,paintfs])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"distanceProgram = twgl.createProgramInfo(gl, [vs,distancefs])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"displayProgram = twgl.createProgramInfo(gl, [vs,displayfs])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"borderProgram = twgl.createProgramInfo(gl, [vs,borderfs])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":183,"value":"md`## CSS`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":185,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"md`## Shaders`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"md`### Vertex shader\nJust sets position and texture coordinates.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"vs = `#version 300 es\nprecision highp float;\nprecision highp int;\nin vec4 position;\nin vec2 textureCoordinates;\nout vec2 v_st;\nvoid main()\n{\n v_st = textureCoordinates;\n gl_Position = position;\n}`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"md`### Paint fragment shader\nPaints a circle of the given radius at the mouse position into the textures. First texture is set to the current paint id and second texture is set to the paint color.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"paintfs = `#version 300 es\nprecision highp float;\nprecision highp int;\nuniform vec3 mouse; // Mouse position / mousepressed\nuniform vec4 paintId; // Id to paint\nuniform vec4 paintColor; // Color to paint\nuniform float radius; // Paint radius in pixels\nlayout(location = 0) out vec4 color1; // Paint ids \nlayout(location = 1) out vec4 color2; // Paint color \n\nvoid main() {\n if (mouse.z == 0.0 || distance(mouse.xy, gl_FragCoord.xy) > radius) discard;\n color1 = paintId; \n color2 = paintColor;\n}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":146,"value":"md`### Pack and unpack functions\nGLSL code for packing and unpacking a float in range [0..1] into 2 texture coordinates.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"packunpack = `vec2 pack2 (float value) {\n int ivalue = int(value * 256.0 * 256.0);\n int ix = ivalue%256;\n int iy = ivalue/256;\n return vec2 (float(ix)/255.0, float(iy)/255.0);\n}\n\nfloat unpack2 (vec2 v) {\n int ix = int(round(v.x*255.0));\n int iy = int(round(v.y*255.0));\n int ivalue = ix+iy*256;\n return float (ivalue) / 256.0 / 256.0;\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"md`### Distance fragment shader\nDoes one jump flooding step by reading one set of textures and writing another. \\`stepWidth\\` defines the distance each fragment will look for neighbors.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":68,"value":"md`### Display fragment shader\nReads the textures and exhibits the contents of texture 2 (i.e., colors) onto the canvas.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"displayfs = `#version 300 es\nprecision highp float;\nprecision highp int;\nuniform vec2 pixel; // Inverse of the size of the screen\nuniform sampler2D color1Map;\nuniform sampler2D color2Map;\nin vec2 v_st;\nout vec4 color;\n\n${packunpack}\n\nvoid main()\n{\n vec4 paintId = texture(color1Map, v_st);\n vec4 paintColor = texture(color2Map, v_st);\n float id = (paintId.x + paintId.y * 256.0)*256.0;\n if (paintId.w > 0.0) { // A seed\n color = paintColor;\n }\n else if (id > 0.0) { // Not a seed, but neighbor to a seed\n vec2 seedCoord = vec2(unpack2(paintColor.xy),unpack2 (paintColor.zw));\n float dist = pow(distance(seedCoord,v_st),${1.0-voronoiColorAttenuation});\n //color = vec4 ((1.0-2.0*dist)*texture(color2Map, seedCoord).xyz,1.0);\n color = vec4 (mix(texture(color2Map, seedCoord).xyz,vec3(1.0,1.0,1.0),dist),1.0);\n }\n else { // A background pixel\n color = vec4 (1.0, 1.0, 1.0, 1.0);\n }\n}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"md`### Border fragment shader\nDraws the borders of the Voronoi diagram and also the medial axes.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"md`## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"twgl = require('twgl.js@4.4.0/dist/4.x/twgl-full.js')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":195,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":126,"value":"import {radio, slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W37","stdlib":"1","titling":"auto"}} 32:"$31:body"