2b:null 2c:["$","title",null,{"children":"B-Splines | Matthew Berger | Observable"}] 31:T528,basis_function_plot = { let total_height = 400, actual_height = 300 let svg = d3.create('svg').attr('width', width).attr('height', total_height) let g = svg.append('g').attr('transform', 'translate(50,50)') let x_scale = d3.scaleLinear().domain([0,1]).range([0,450]) let y_scale = d3.scaleLinear().domain([0,1]).range([actual_height,0]) let line_shape = d3.line() .x(d => x_scale(d.t)) .y(d => y_scale(d.func)) let n_funcs = sampled_basis_functions.length let hue_scale = d3.scalePoint().domain(d3.range(n_funcs)).range([80,330]) let lum_scale = d3.scalePoint().domain(d3.range(n_funcs)).range([80,30]) let chroma_scale = d3.scalePoint().domain(d3.range(n_funcs)).range([50,10]) let access_color = (i) => d3.hcl(hue_scale(i),i%2==0 ? 20 : 50,i%2==0 ? 70 : 30) g.selectAll('path') .data(sampled_basis_functions) .enter() .append('path') .attr('d', d => line_shape(d)) .attr('fill', 'none') .attr('stroke', (d,i) => access_color(i)).attr('stroke-width', 4) g.append('g').attr('class', 'axis y').lower() .call(d3.axisLeft(y_scale).ticks(4)).call(axis_tweak) g.append('g').attr('class', 'axis x').lower() .attr('transform', `translate(0,${actual_height})`) .call(d3.axisBottom(x_scale).ticks(4)).call(axis_tweak) return svg.node() }32:T4ae,md` There are different ways to construct the basis functions. A common technique is through the recurrence relation defined as follows: ${tex.block` B_{i,1}(t) = \begin{cases} 1 & \text{if } t_i \le t < t_{i+1} \\ 0 & \text{otherwise}, \end{cases} `} which represents the base case, and: ${tex.block` B_{i,k+1}(t) = w_{i,k} B_{i,k}(t) + (1 - w_{i+1,k}(t)) B_{i+1,k}(t), `} with weights linear in the input ${tex.block` w_{i,k}(t) = \frac{t-t_i}{t_{i+k}-t_i} `} The ${tex`t_i`} values are known as **knots**, and they are the main parameters that control the curve's shape. To make things concrete, consider a B-spline of order 2. We should expect a polynomial of degree 1, e.g. a linear function. We see that the **base case** is just piecewise-constant: 1 or 0. The next basis function, ${tex`B_{i,2}`} is _linear_ in the input, which can be seen from the weights ${tex`w_{i,k}(t)`}. In fact, all we are performing is **linear interpolation**. B-splines of order 3 are, in fact, performing "linear interpolation of linear interpolation" due to the recurrence relation, and naturally, this results in a quadratic polynomial. Similar reasoning can be applied for higher-order B-splines. `33:T5c7,plot = { let svg = d3.create('svg').attr('width', width).attr('height', 400) let line_shape = d3.line() .x(d => d[0]) .y(d => d[1]) svg.append('path') .attr('d', line_shape(sampled_curve)) .attr('fill', 'none') .attr('stroke', d3.hcl(0,0,25)) .attr('stroke-width', 2.5) svg.selectAll('control') .data(control_points) .enter() .append('circle') .attr('cx', d => d[0]) .attr('cy', d => d[1]) .attr('r', 8) .attr('fill', 'white') .attr('stroke', (_,i) => { if(control_points.length==4 || (control_points.length == 6 && i >= 1 && i <= 4) || (control_points.length == 8 && i >= 2 && i <= 5)) return d3.hcl(140,50,40) return d3.hcl(250,25,60) }) .attr('stroke-width', 4) if(num_edges == 'two') { svg.append('path') .attr('d', line_shape(other_sampled_curve)) .attr('fill', 'none') .attr('stroke', d3.hcl(0,0,25)) .attr('stroke-width', 2.5) svg.selectAll('control') .data(other_control_points) .enter() .append('circle') .attr('cx', d => d[0]) .attr('cy', d => d[1]) .attr('r', 8) .attr('fill', 'white') .attr('stroke', (_,i) => { if(control_points.length==4 || (control_points.length == 6 && i >= 1 && i <= 4) || (control_points.length == 8 && i >= 2 && i <= 5)) return d3.hcl(140,50,40) return d3.hcl(340,25,60) }) .attr('stroke-width', 4) } return svg.node() }34:T5a8,bundled_plot = { let svg = d3.create('svg').attr('width', width).attr('height', 400) let line_shape = d3.line() .x(d => d[0]) .y(d => d[1]) svg.append('path') .attr('d', line_shape(sampled_bundled_curve)) .attr('fill', 'none') .attr('stroke', d3.hcl(0,0,25)) .attr('stroke-width', 2.5) svg.selectAll('control') .data(bundled_control_points) .enter() .append('circle') .attr('cx', d => d[0]) .attr('cy', d => d[1]) .attr('r', 8) .attr('fill', 'white') .attr('stroke', (_,i) => { if(control_points.length==4 || (control_points.length == 6 && i >= 1 && i <= 4) || (control_points.length == 8 && i >= 2 && i <= 5)) return d3.hcl(140,50,40) return d3.hcl(250,25,60) }) .attr('stroke-width', 4) svg.append('path') .attr('d', line_shape(other_sampled_bundled_curve)) .attr('fill', 'none') .attr('stroke', d3.hcl(0,0,25)) .attr('stroke-width', 2.5) svg.selectAll('control') .data(bundled_other_control_points) .enter() .append('circle') .attr('cx', d => d[0]) .attr('cy', d => d[1]) .attr('r', 8) .attr('fill', 'white') .attr('stroke', (_,i) => { if(control_points.length==4 || (control_points.length == 6 && i >= 1 && i <= 4) || (control_points.length == 8 && i >= 2 && i <= 5)) return d3.hcl(140,50,40) return d3.hcl(340,25,60) }) .attr('stroke-width', 4) return svg.node() }35:[] 2f:{"id":"aa0ebe32864c9524","slug":null,"title":"B-Splines","thumbnail":"493304aaa49762ef5272b9906a3cfed656bc8f061da85df26e49f0593ecedff6","access_level":"unlisted","create_time":"$D2020-10-16T02:15:20.288Z","update_time":"$D2020-10-18T00:17:15.663Z","view_time":null,"first_public_time":null,"has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"ff8d3dc5309f0e8f","login":"mattberger","name":"Matthew Berger","avatar_url":"https://avatars-next.observableusercontent.com/db43c568a6d4eb06d6475f8809d39dc6cc8e44a37000cb82904f063c85599c88","tier":"starter_2024"},"version":418,"publish_version":418,"role":null,"authored":false,"authors":[{"type":"individual","id":"3e3683c87ab9f224","login":"mattberger","name":"Matthew Berger","avatar_url":"https://avatars-next.observableusercontent.com/db43c568a6d4eb06d6475f8809d39dc6cc8e44a37000cb82904f063c85599c88","tier":null}],"members":[{"type":"individual","id":"3e3683c87ab9f224","login":"mattberger","name":"Matthew Berger","avatar_url":"https://avatars-next.observableusercontent.com/db43c568a6d4eb06d6475f8809d39dc6cc8e44a37000cb82904f063c85599c88","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"B-Splines","cells":[{"id":0,"value":"md`# B-Splines`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"md`\n\nWe will draw edges between nodes using a particular class of curves known as B-Splines.\n\nB-Splines allow us to create polynomial functions with particular properties:\n\n* We specify the degree of the polynomial, e.g. quadratic, cubic, etc..\n* We define a sequence of function values that controls the behavior of the polynomial.\n * In particular, we will create a pair of functions from **control points**: a sequence of (x,y) positions. This will, ultimately, allow us to create a curve.\n * The first control point is the position of a node.\n * The last control point is the position of another node that is connected to the first, in the graph.\n * The control points between the first and last are obtained through the hierarchy (from the inverted Sunburst).\n* Intermediary control points will govern the **shape** of the curve.\n* Further, we will prescribe the curve to start and end at the first and last control points.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":230,"value":"md`\n\nOur curve will be defined by a pair of 1D functions:\n\n${tex.block`\nx(t) = \\sum_{i=1}^m x_i B_{i,n}(t)\n`}\n\n${tex.block`\ny(t) = \\sum_{i=1}^m y_i B_{i,n}(t)\n`}\n\nEach ${tex`(x_i,y_i)`} is a control point, and the ${tex`B_{i,n}`} are **B-spline basis functions** - one basis function for each control point. They are governed by an **order** ${tex`n`}, which in turn, determines the degree of the polynomial as ${tex`d=n-1`}. The function is evaluated over an interval of our choosing, for simplicity, ${tex`t \\in [0,1]`}.\n\nSo, we can see that evaluating the curve at a given parameter ${tex`t`} amounts to taking our control points, weighting them by basis functions evaluated at ${tex`t`}, and summing everything together.\n\nLet's see what these basis functions look like...\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"knots = {\n let knot_vector = d3.range(order+n_control_points).map(_ => 0.0)\n for(let i = knot_vector.length-(degree); i < knot_vector.length; i++)\n knot_vector[i] = 1.0\n for(let i = (degree); i < knot_vector.length-(degree); i++)\n knot_vector[i] = (i-degree)/(n_control_points-order+1)\n \n return knot_vector\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":283,"value":"control_point_sets = [\n [\n [150,200],\n [233,100],\n [366,300],\n [450,200]\n ],\n [\n [80,150],\n [150,200],\n [233,100],\n [366,300],\n [450,200],\n [500,250]\n ],\n [\n [20,40],\n [80,150],\n [150,200],\n [233,100],\n [366,300],\n [450,200],\n [500,250],\n [600,50]\n ],\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"degree = order-1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"bspline = (x,k,d) => {\n function cox_de_boor(x,k,d) {\n if(d==1)\n return (x >= knots[k] && x < knots[k+1]) ? 1 : 0\n \n let alpha_begin = knots[k+d-1]==knots[k] ? 0 : (x-knots[k])/(knots[k+d-1]-knots[k])\n let alpha_end = knots[k+d]==knots[k+1] ? 0 : 1 - (x-knots[k+1])/(knots[k+d]-knots[k+1])\n\n return alpha_begin*cox_de_boor(x,k,d-1) + alpha_end*cox_de_boor(x,k+1,d-1)\n }\n \n return cox_de_boor(x,k,d)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"sampled_basis_functions = {\n let simple_scale = d3.scaleLinear().domain([0,100-1]).range([1e-10,1-1e-10])\n let t_samples = d3.range(100).map(d => simple_scale(d))\n let basis_funcs = []\n for(let c = 0; c < n_control_points; c++) {\n let basis_func = []\n for(let t = 0; t < t_samples.length; t++) {\n let t_val = t_samples[t]\n let basis_func_val = bspline(t_val,c,order)\n basis_func.push({t:t_val,func:basis_func_val})\n }\n basis_funcs.push(basis_func)\n }\n return basis_funcs\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":269,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"control_points = control_point_sets[(n_control_points-4)/2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":379,"value":"sample_bspline_curve = (cps) => {\n let simple_scale = d3.scaleLinear().domain([0,n_samples-1]).range([0,1-1e-10])\n let t_samples = d3.range(n_samples).map(d => simple_scale(d))\n let the_curve = []\n for(let t = 0; t < t_samples.length; t++) {\n let t_val = t_samples[t], x = 0, y = 0\n for(let c = 0; c < cps.length; c++) {\n let basis_func_val = bspline(t_val,c,order)\n x += cps[c][0]*basis_func_val\n y += cps[c][1]*basis_func_val\n }\n the_curve.push([x,y])\n }\n return the_curve\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"sampled_curve = sample_bspline_curve(control_points)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":334,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"md`## Interactive Curve Construction\n\nWe can inspect how the (1) control points, and (2) order, provide us different types of curves below:\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":312,"value":"other_control_point_sets = [\n [\n [150,200],\n [233,100],\n [366,300],\n [450,200]\n ],\n [\n [80,350],\n [150,200],\n [233,100],\n [366,300],\n [450,200],\n [500,375]\n ],\n [\n [20,380],\n [80,350],\n [150,200],\n [233,100],\n [366,300],\n [450,200],\n [500,375],\n [600,330]\n ],\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":320,"value":"other_control_points = other_control_point_sets[(n_control_points-4)/2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":317,"value":"other_sampled_curve = sample_bspline_curve(other_control_points)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"n_samples = 100","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"viewof num_edges = select({\n description: \"Number of graph edges to show\",\n options: [\"one\", \"two\"],\n value: \"one\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":407,"value":"viewof order = slider({\n min: 2, \n max: 4, \n step: 1, \n value: 2,\n description: 'Order of B-spline'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":410,"value":"viewof n_control_points = slider({\n min: 4, \n max: 8, \n step: 2, \n value: 4,\n description: 'Number of control points'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":353,"value":"md`## Bundling Curves\n\nThe key idea behind hierarchical edge bundling is to introduce a parameter, ${tex`\\beta \\in [0,1]`}, that controls the \"bundling\" of two curves that share ancestor nodes in the hierarchy.\n\nThis boils down to individually adjusting the control points of the two curves, using the following scheme:\n\n${tex.block`\n\\mathbf{p'}_i = \\beta \\cdot \\mathbf{p}_i + (1-\\beta) \\cdot \\left(\\mathbf{p}_1 + \\frac{i-1}{m-1} (\\mathbf{p}_m - \\mathbf{p}_1)\\right)\n`}\n\nThis is a simple linear interpolation between a given control point's original value, and a point that lies along the line between the first point and the last point.\n\nConsequently: when ${tex`\\beta = 0`}, all of our control points lie along a line, and _regardless of the order_, we obtain lines from the B-spline. This is \"straightening out\" the curve. When ${tex`\\beta = 1`}, we resort back to our original B-spline.\n\nDifferent values of ${tex`\\beta`} give us different levels of bundling. We can inspect a toy example:\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":368,"value":"bundle = (p, i, p1, pm) => {\n let new_x = beta*p[0] + (1-beta)*(p1[0] + (i/(n_control_points-1))*(pm[0]-p1[0]))\n let new_y = beta*p[1] + (1-beta)*(p1[1] + (i/(n_control_points-1))*(pm[1]-p1[1]))\n return [new_x,new_y]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":373,"value":"bundled_control_points = control_points\n .map((d,i) => bundle(d,i,control_points[0],control_points[n_control_points-1]))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":387,"value":"sampled_bundled_curve = sample_bspline_curve(bundled_control_points)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":376,"value":"bundled_other_control_points = other_control_points\n .map((d,i) => bundle(d,i,other_control_points[0],other_control_points[n_control_points-1]))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":389,"value":"other_sampled_bundled_curve = sample_bspline_curve(bundled_other_control_points)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":370,"value":"viewof beta = slider({\n min: 0, \n max: 1, \n step: .01, \n value: 1,\n description: 'Bundling parameter'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":399,"value":"md`# Misc`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":303,"value":"axis_tweak = (axis_g,remove_span) => {\n if(remove_span)\n axis_g.selectAll('path').remove()\n else\n axis_g.selectAll('path').attr('stroke', d3.hcl(0,0,70))\n axis_g.selectAll('.tick').selectAll('line').attr('stroke', d3.hcl(0,0,45))\n axis_g.selectAll('.tick').selectAll('text').attr('fill', d3.hcl(0,0,45))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"md`# Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":242,"value":"import {slider,select} from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 30:"$2f:body"