2b:null 2c:["$","title",null,{"children":"CG HW 06: World Flight Paths Voronoi | Bairui Su | Observable"}] 31:T1bae,{ const vertexSize = 10; const maxLifespan = 200; const linkColor = [1.0, 0.2471, 0.498]; const colorInterpolator = d3.interpolateViridis; const SK = (d) => +d["source_longitude"] + "," + +d["source_latitude"]; const DK = (d) => +d["destination_longitude"] + "," + +d["destination_latitude"]; // prettier-ignore const bezierLink = (nu, nv, B) => parametric(bezier, nu, nv, B); const count = createCount(route); const coordinates = new Set(route.flatMap((d) => [SK(d), DK(d)])); const airports = Array.from(coordinates).map((d) => d.split(",").map(Number)); const links = transformLinks(route); const voronoiMesh = { data: new Float32Array(voronoi(airports).flat(Infinity)) }; const actives = []; let startTime = Date.now() / 1000; let restLinks = links.slice(); let frameCount = 0; function update(gl) { frameCount++; const time = (Date.now() / 1000 - startTime) / 3; const m = M.mxm( M.perspective(0, 0, 0), M.mxm(M.turnX(time), M.mxm(M.turnY(time), M.scale(0.7))) ); drawMeshAt(gl, voronoiMesh, m); // Add new links. if (frameCount % 2 === 0) { const index = d3.randomInt(0, restLinks.length)(); restLinks.splice(index, 1); actives.push({ index, lifespan: maxLifespan }); if (restLinks.length <= 0) restLinks = links.slice(); } // Update links. for (let i = actives.length - 1; i >= 0; i--) { const d = actives[i]; if (d.lifespan < 0) actives.splice(i, 1); else d.lifespan--; } const activeLinks = actives.map(({ index, lifespan }) => { const d = links[index]; const X = d.map((t) => t[0]); const Y = d.map((t) => t[1]); const Z = d.map((t) => t[2]); const t = (maxLifespan - lifespan) / maxLifespan; const st = Math.sin(t * Math.PI); return bezierLink(20, 3, [X, Y, Z, [...linkColor, st], 0.005]); }); for (const points of activeLinks) { const data = new Float32Array(points.flat()); drawMeshAt(gl, { data, triangle_strip: true }, m); } } function voronoi(airports) { const { centers, polygons } = d3.geoDelaunay(airports); const extent = d3.extent(airports, count); const scaleColor = d3.scaleSequentialLog(extent, colorInterpolator); return polygons.map((I, i) => { const color = scaleColor(count(airports[i])); const { r, g, b } = d3.color(color); const rgba = [r / 255, g / 255, b / 255, 1]; const P = I.map((i) => centers[i]); const { triangles } = d3.geoDelaunay(P); return triangles.map(([i, j, w]) => { const a = transformPoint(P[i]); const b = transformPoint(P[j]); const c = transformPoint(P[w]); return [a, a, rgba, b, b, rgba, c, c, rgba]; }); }); } function transformLinks(route) { const radius = 1.0; const heightFactor = 1.0; function createSphericalBezierPoints(p0, p3) { const midDir = V.normalize(V.add(p0, p3)); const mid = V.scale(midDir, radius * (1 + heightFactor)); const p1 = V.add(V.scale(p0, 0.7), V.scale(mid, 0.3)); const p2 = V.add(V.scale(p3, 0.7), V.scale(mid, 0.3)); return [p0, p1, p2, p3]; } return route.map((d) => { const s = [d["source_longitude"], d["source_latitude"]]; const t = [d["destination_longitude"], d["destination_latitude"]]; return createSphericalBezierPoints(transformPoint(s), transformPoint(t)); }); } function createCount(route) { const outByAirport = map(SK); const inByAirport = map(DK); function map(key) { const groups = d3 .groups(route, key) .map(([k, V]) => [k, d3.sum(V, (d) => +d.count)]); return new Map(groups); } return function (p) { const key = p[0] + "," + p[1]; const inCount = inByAirport.get(key) ?? 0; const outCount = outByAirport.get(key) ?? 0; return inCount + outCount; }; } function transformPoint(p) { const [lon, lat] = p; const theta = toRad(lon); const phi = toRad(lat); const x = Math.cos(theta) * Math.cos(phi); const y = Math.sin(theta) * Math.cos(phi); const z = Math.sin(phi); return [x, y, z]; } function parametric(f, nu, nv, other) { let V = []; for (let j = 0; j < nv; j++) { for (let i = 0; i <= nu; i++) { V.push(f(i / nu, j / nv, other)); V.push(f(i / nu, (j + 1) / nv, other)); } V.push(f(1, (j + 1) / nv, other)); V.push(f(0, (j + 1) / nv, other)); } return V.flat(); } function bezier(u, v, B) { let BX = B[0], BY = B[1], BZ = B[2], color = B[3], r = B[4], nk = (BX.length - 1) / 3; let M = [ [-1, 3, -3, 1], [3, -6, 3, 0], [-3, 3, 0, 0], [1, 0, 0, 0] ]; let T = (a, t) => a[0] * t ** 3 + a[1] * t ** 2 + a[2] * t + a[3]; let Vi = (V, i, t) => V[i] * T(M[i], t); let C = (V, t) => Vi(V, 0, t) + Vi(V, 1, t) + Vi(V, 2, t) + Vi(V, 3, t); let n = (nk * u - 0.001) >> 0; let f = nk * u - n; let x = C(BX.slice(3 * n), f); let y = C(BY.slice(3 * n), f); let z = C(BZ.slice(3 * n), f); let dx = C(BX.slice(3 * n), f + 0.001) - x; let dy = C(BY.slice(3 * n), f + 0.001) - y; let dz = C(BZ.slice(3 * n), f + 0.001) - z; let tangent = V.normalize([dx, dy, dz]); let ref = Math.abs(tangent[1]) < 0.9 ? [0, 1, 0] : [1, 0, 0]; let binormal = V.normalize(V.cross(tangent, ref)); let normal = V.normalize(V.cross(binormal, tangent)); let c = Math.cos(2 * Math.PI * v); let s = Math.sin(2 * Math.PI * v); let nx = normal[0] * c + binormal[0] * s; let ny = normal[1] * c + binormal[1] * s; let nz = normal[2] * c + binormal[2] * s; let px = x + r * nx; let py = y + r * ny; let pz = z + r * nz; return [px, py, pz, nx, ny, nz, ...color]; } function drawMeshAt(gl, mesh, m) { const type = mesh.triangle_strip ? gl.TRIANGLE_STRIP : gl.TRIANGLES; setUniform(gl, "Matrix4fv", "uMF", false, m); setUniform(gl, "Matrix4fv", "uMI", false, M.inverse(m)); gl.bufferData(gl.ARRAY_BUFFER, mesh.data, gl.STATIC_DRAW); gl.drawArrays(type, 0, mesh.data.length / vertexSize); } function toRad(d) { return (d * Math.PI) / 180; } const vertexShader = `\ #version 300 es uniform mat4 uMF, uMI; in vec3 aPos, aNor; in vec4 aColor; out vec3 vPos, vNor; out vec4 vColor; void main() { vec4 pos = uMF * vec4(aPos, 1.); vec4 nor = vec4(aNor, 0.) * uMI; gl_Position = pos * vec4(1.,1.,-1.,1.); vPos = pos.xyz; vNor = nor.xyz; vColor = aColor; }`; const fragmentShader = `\ #version 300 es precision highp float; in vec3 vPos, vNor; in vec4 vColor; out vec4 fragColor; void main() { vec3 nor = normalize(vNor); float c = .5+ max(0., dot(vec3(.5),nor)); float a = vColor.w == 1. ? 1. : vColor.w * c; fragColor = vec4(vColor.rgb * c, a); }`; return glStart({ width, height: width, vertexShader, fragmentShader, update, invalidation, vertexSize, style: { padding: 0 } }); }32:T684,M = { const m = {}; let c = (t) => Math.cos(t); let s = (t) => Math.sin(t); m.identity = () => [1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1]; // prettier-ignore m.move = (x,y,z) => [1,0,0,0, 0,1,0,0, 0,0,1,0, x,y,z,1]; // prettier-ignore m.turnX = t => [1,0,0,0, 0,c(t),s(t),0, 0,-s(t),c(t),0, 0,0,0,1]; // prettier-ignore m.turnY = t => [c(t),0,-s(t),0, 0,1,0,0, s(t),0,c(t),0, 0,0,0,1]; // prettier-ignore m.turnZ = t => [c(t),s(t),0,0, -s(t),c(t),0,0, 0,0,1,0, 0,0,0,1]; // prettier-ignore m.scale = (x,y,z) => [x,0,0,0, 0,y??x,0,0, 0,0,z??x,0, 0,0,0,1]; // prettier-ignore m.perspective = (x,y,z) => [1,0,0,x, 0,1,0,y??x, 0,0,1,z??x, 0,0,0,1]; // prettier-ignore // Multiply two matrices. m.mxm = (a, b) => { let m = []; for (let c = 0; c < 16; c += 4) { for (let r = 0 ; r < 4 ; r++) m.push( a[r]*b[c] + a[r+4]*b[c+1] + a[r+8]*b[c+2] + a[r+12]*b[c+3] ); // prettier-ignore } return m; }; // Invert a matrix. m.inverse = (src) => { let dst = [], det = 0, cofactor = (c, r) => { let s = (i, j) => src[((c + i) & 3) | (((r + j) & 3) << 2)]; // prettier-ignore return (c+r & 1 ? -1 : 1) * ( (s(1,1)*(s(2,2)*s(3,3)-s(3,2)*s(2,3))) - (s(2,1)*(s(1,2)*s(3,3)-s(3,2)*s(1,3))) + (s(3,1)*(s(1,2)*s(2,3)-s(2,2)*s(1,3))) ); }; for (let n = 0 ; n < 16 ; n++) dst.push(cofactor(n >> 2, n & 3)); // prettier-ignore for (let n = 0 ; n < 4 ; n++) det += src[n] * dst[n << 2]; // prettier-ignore for (let n = 0 ; n < 16 ; n++) dst[n] /= det; // prettier-ignore return dst; }; return m; }33:Td04,glStart = { let noiseCode = ` vec3 _s(vec3 i) { return cos(5.*(i+5.*cos(5.*(i.yzx+5.*cos(5.*(i.zxy+5.*cos(5.*i))))))); } float _t(vec3 i, vec3 u, vec3 a) { return dot(normalize(_s(i + a)), u - a); } float noise(vec3 p) { vec3 i = floor(p), u = p - i, v = 2.*mix(u*u, u*(2.-u)-.5, step(.5,u)); return mix(mix(mix(_t(i, u, vec3(0.,0.,0.)), _t(i, u, vec3(1.,0.,0.)), v.x), mix(_t(i, u, vec3(0.,1.,0.)), _t(i, u, vec3(1.,1.,0.)), v.x), v.y), mix(mix(_t(i, u, vec3(0.,0.,1.)), _t(i, u, vec3(1.,0.,1.)), v.x), mix(_t(i, u, vec3(0.,1.,1.)), _t(i, u, vec3(1.,1.,1.)), v.x), v.y), v.z); }`; let phongCode = ` vec3 phong(vec3 N, vec3 L, vec3 W, vec3 diffuse, vec4 specular) { vec3 R = 2. * N * dot(N,L) - L; return diffuse * max(0., dot(N, L)) + specular.rgb * pow(max(0.,dot(R,-W)), specular.a); } `; return (scene) => { const canvas = scene.canvas ?? document.createElement("canvas"); canvas.width = scene.width ?? 640; canvas.height = scene.height ?? 640; const gl = canvas.getContext("webgl2"); const vertexSize = scene.vertexSize; canvas.setShaders = function (vertexShader, fragmentShader) { gl.program = gl.createProgram(); gl.enable(gl.BLEND); gl.blendFunc(gl.SRC_ALPHA, gl.ONE_MINUS_SRC_ALPHA); function addshader(type, src) { let shader = gl.createShader(type); gl.shaderSource(shader, src); gl.compileShader(shader); if (!gl.getShaderParameter(shader, gl.COMPILE_STATUS)) console.log("Cannot compile shader:", gl.getShaderInfoLog(shader)); gl.attachShader(gl.program, shader); } addshader(gl.VERTEX_SHADER, vertexShader); let i = fragmentShader.indexOf("float") + 6; addshader( gl.FRAGMENT_SHADER, fragmentShader.substring(0, i) + noiseCode + phongCode + fragmentShader.substring(i) ); gl.linkProgram(gl.program); if (!gl.getProgramParameter(gl.program, gl.LINK_STATUS)) console.log("Could not link the shader program!"); gl.useProgram(gl.program); gl.bindBuffer(gl.ARRAY_BUFFER, gl.createBuffer()); gl.enable(gl.DEPTH_TEST); gl.depthFunc(gl.LEQUAL); let vertexAttribute = (name, size, position) => { let attr = gl.getAttribLocation(gl.program, name); gl.enableVertexAttribArray(attr); gl.vertexAttribPointer(attr, size, gl.FLOAT, false, vertexSize * 4, position * 4); // prettier-ignore }; /* Each vertex now has 9 numbers: 3 for the position attribute, 3 for the normal attribute, and another 4 for color attribute */ vertexAttribute("aPos", 3, 0); vertexAttribute("aNor", 3, 3); vertexAttribute("aColor", 4, 6); }; canvas.setShaders(scene.vertexShader.trim(), scene.fragmentShader.trim()); const timer = setInterval(function () { if (scene.update) scene.update(gl, [0, 0, 7]); }, 30); if (scene.invalidation) scene.invalidation.then(() => clearInterval(timer)); canvas.gl = gl; const style = scene.style ?? {}; style.background ??= "black"; style.padding ??= "30px"; for (const [key, value] of Object.entries(style)) { canvas.style[key] = value; } return canvas; }; }34:[] 2f:{"id":"dea043e8d65bf6d0","slug":null,"title":"CG HW 06: World Flight Paths Voronoi","thumbnail":"9188d04da4985aec997fca1841653755368339a718ba62aff2a6c48d64bf2bcc","access_level":"public","create_time":"$D2025-11-04T17:05:15.227Z","update_time":"$D2025-11-09T13:15:05.104Z","view_time":null,"first_public_time":"$D2025-11-05T01:04:58.081Z","has_unpublished_edits":null,"fork":{"id":"5c94de791de77e28","slug":null,"title":"CG HW 05: World Airports Delaunay","owner":{"id":"3e931206c18366b5","login":"pearmini","name":"Bairui Su"}},"stars":0,"starred":false,"owner":{"type":"team","id":"3e931206c18366b5","login":"pearmini","name":"Bairui Su","avatar_url":"https://avatars-next.observableusercontent.com/0c55731913f2096b86eadf187f5e21ae0a951f3c4dd6bbde4bf2a8536c5b6e49","tier":"starter_2024"},"version":1178,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"76ec39dbb0bd8e40","login":"pearmini","name":"Bairui SU","avatar_url":"https://avatars-next.observableusercontent.com/0c55731913f2096b86eadf187f5e21ae0a951f3c4dd6bbde4bf2a8536c5b6e49","tier":null}],"members":[{"type":"team","id":"3e931206c18366b5","login":"pearmini","name":"Bairui Su","avatar_url":"https://avatars-next.observableusercontent.com/0c55731913f2096b86eadf187f5e21ae0a951f3c4dd6bbde4bf2a8536c5b6e49","tier":"starter_2024","role":"editor"},{"type":"individual","id":"76ec39dbb0bd8e40","login":"pearmini","name":"Bairui SU","avatar_url":"https://avatars-next.observableusercontent.com/0c55731913f2096b86eadf187f5e21ae0a951f3c4dd6bbde4bf2a8536c5b6e49","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"CG HW 06: World Flight Paths Voronoi","cells":[{"id":0,"value":"# CG HW 06: World Flight Paths Voronoi\n\nAlso see [World Airports Delaunay](https://observablehq.com/d/5c94de791de77e28).\n\n- Ref. https://observablehq.com/@fil/flight-paths\n- Ref. https://observablehq.com/@d3/world-airports-voronoi\n- Ref. https://ourairports.com/data/","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":465,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":747,"value":"route = d3.csv(\n \"https://gist.githubusercontent.com/MichaelByrneAU/87383e163244055d641d4dcd58a5d24d/raw/d17299dcba8c9e18b4e1f4885f90a45618b55599/flight_paths_2014.csv\"\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":904,"value":"V = {\n const V = {};\n V.cross = (a,b) => [ a[1]*b[2] - a[2]*b[1], a[2]*b[0] - a[0]*b[2], a[0]*b[1] - a[1]*b[0] ]; // prettier-ignore\n V.dot = (a,b) => { let s = 0 ; for (let i=0 ; i Math.sqrt(V.dot(v,v)); // prettier-ignore\n V.normalize = v => { let s = V.norm(v); return v.length==3 ? [ v[0]/s,v[1]/s,v[2]/s ] : [v[0]/s, v[1]/s]; } // prettier-ignore\n V.subtract = (a,b) => { let v = []; for (let i=0 ; i { let v = []; for (let i=0 ; i< a.length ; i++) v.push(a[i] + b[i]); return v; } // prettier-ignore\n V.scale = (a, s) => [a[0] * s, a[1] * s, a[2] * s]; // prettier-ignore\n return V;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":381,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"setUniform = (gl, type, name, a, b, c) =>\n gl[\"uniform\" + type](gl.getUniformLocation(gl.program, name), a, b, c)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":539,"value":"d3 = require(\"d3@7\", \"d3-geo-voronoi@2\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 30:"$2f:body"