21:null 22:["$","title",null,{"children":"Antialiasing Lines and Triangles II: Wu's Algorithm | T.J. Jankun-Kelly | Observable"}] 27:T16b8,viewof aliased_grid = { let fig = html`

Aliased Line. Drag line & ends to generate line.

` const aliased = raster_grid({size: grid_size, grid_width: ewidth, grid:false, centers: false, grid_height: height, mousedown: () => null}); aliased.style.width = ewidth + "px"; aliased.style.height = height + "px"; aliased.style.margin = "auto"; aliased.style.border = "thin solid steelblue"; let svg = aliased.querySelector("svg"); svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "aliased" + (grid_count*j+i)); svg.append("line") .attr("class", "line") .attr("stroke", "black") .attr("stroke-width", 3) .style("cursor", "move"); svg.append("rect") .attr("class", "endbox start") .attr("stroke", "black") .style("fill-opacity", 0) .attr("stroke-width", 3) .attr("width", grid_size) .attr("height", grid_size) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); svg.append("rect") .attr("class", "endbox end") .attr("stroke", "black") .style("fill-opacity", 0) .attr("stroke-width", 3) .attr("width", grid_size) .attr("height", grid_size) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); svg.append("circle") .attr("class", "endpoint start") .attr("stroke", "black") .attr("r", 4) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); svg.append("circle") .attr("class", "endpoint end") .attr("stroke", "black") .attr("r", 4) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); const wu = raster_grid({size: grid_size, grid_width: ewidth, grid:false, centers:false, grid_height: height, mousedown: () => null}); wu.style.width = ewidth + "px"; wu.style.height = height + "px"; wu.style.margin = "auto"; wu.style.display = "none"; wu.style.border = "thin solid steelblue"; svg = wu.querySelector("svg"); svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "wu" + (grid_count*j+i)); svg.append("line") .attr("class", "line") .attr("stroke", "black") .attr("stroke-width", 3); svg.append("rect") .attr("class", "endbox start") .attr("stroke", "black") .style("fill-opacity", 0) .attr("stroke-width", 3) .attr("width", grid_size) .attr("height", grid_size) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); svg.append("rect") .attr("class", "endbox end") .attr("stroke", "black") .style("fill-opacity", 0) .attr("stroke-width", 3) .attr("width", grid_size) .attr("height", grid_size) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); svg.append("circle") .attr("class", "endpoint start") .attr("stroke", "black") .attr("r", 4) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); svg.append("circle") .attr("class", "endpoint end") .attr("stroke", "black") .attr("r", 4) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); function clear() { d3.select(aliased).selectAll(".raster_grid").style("fill", "none"); d3.select(wu).selectAll(".raster_grid").style("fill", "none"); } function dragging() { if(d3.event.x < 0 || d3.event.x > ewidth || d3.event.y < 0 || d3.event.y > (height-0.5*grid_size)) return; const draggable = {"start": mutable start_grid, "end": mutable end_grid}; const dragged = draggable[this.classList[1]]; if(Math.trunc(dragged[0]/grid_size) != Math.trunc(d3.event.x/grid_size) || Math.trunc(dragged[1]/grid_size) != Math.trunc(d3.event.y/grid_size)) { dragged[0] = grid_size * Math.trunc(d3.event.x/grid_size) + 0.5 * grid_size; dragged[1] = grid_size * Math.trunc(d3.event.y/grid_size) + 0.5 * grid_size; mutable start_grid = mutable start_grid; mutable end_grid = mutable end_grid; } } function update() { mutable start[0] = Math.round((mutable start_grid[0]) / grid_size - 0.5); mutable start[1] = Math.round(grid_count - (mutable start_grid[1]) / grid_size - 0.5); mutable end[0] = Math.round((mutable end_grid[0]) / grid_size - 0.5); mutable end[1] = Math.round(grid_count - (mutable end_grid[1]) / grid_size - 0.5); mutable start = mutable start; mutable end = mutable end; } const context = DOM.context2d(window.devicePixelRatio * ewidth, window.devicePixelRatio * height, 1); const canvas = d3.select(context.canvas); canvas.style("border", "thin solid steelblue") .style("width", ewidth + "px") .style("height", height + "px") .style("margin", "auto") .style("display", "none"); fig.prepend(context.canvas); fig.canvas = context.canvas; fig.context = context; fig.prepend(wu); fig.wu = wu; fig.prepend(aliased); fig.aliased = aliased; return fig; }28:T71c,md`Computer graphic primitives are mathematical constructs; as such, they usually can be defined at any resolution desired. However, these are instantiated at a fixed resolution when finally rendered. If the detail within the primitive changes in a way that cannot be accurately represented, *aliasing* occurs: these are seen as "jaggies" or discontinuities in edges or sharp features. *Antialiasing* methods attempt to reduce the effect. In this series, I discuss some methods to antialias that appropriate for raster displays. ## Wu's Algorithm Unlike filter-based approaches such as Gupta-Sproul (which operate in [the frequency domain](https://en.wikipedia.org/wiki/Frequency_domain "Wikipedia: Frequency Domain")), [Wu's algorithm](https://dl.acm.org/citation.cfm?id=122734 "Xiaolin Wu: An Efficient Antialias Technique") is motivated by the spatial domain. Consider a pixel ${tex`\left(i,j\right)`} that has just been set, where ${tex`j`} is an approximation to the true value of the curve ${tex`y=f\left(i\right)`} (we are assuming ${tex`x`} is the driving axis; other cases are symmetric). Any other ${tex`j'`} in the same column could have been chosen; some of them may better visually approximate the curve (i.e., keep the curve from appearing concave) even if their absolute error is larger. Wu's algorithm seeks to minimize the visual error in each column in comparison to the other columns along the curve: ${tex.block`E_{i,i'}=f\left(i\right)-f\left(i'\right)-\left(j-j'\right)`} where ${tex`i,i'`} are two raster columns and the ${tex`j,j'`} are the chosen raster row. The goal is to minimize this error term over all columns on the curve (to minimize the error [matrix norm](https://en.wikipedia.org/wiki/Matrix_norm "Wikipedia: Matrix Norm")) by choosing the approximated ${tex`j,j'`} judiciously:`29:T856,viewof error = { let fig = html`

` const [x1,y1] = [-0.5, 0]; const [x2,y2] = [ 4.5, 1]; const line_eq = (i) => (i+0.5) / 5; const pts = midpoint([x1,y1], [x2,y2]); const w = Math.min(width,640); const alias_error = raster_grid({numberH: 5, numberV: 2, grid_width: w, grid_height: 256, mousedown: update}); alias_error.style.width = w + "px"; alias_error.style.height = 256 + "px"; alias_error.style.margin = "auto"; alias_error.style.border = "thin solid steelblue"; let svg = alias_error.querySelector("svg"); svg = d3.select(svg); svg.selectAll(".raster_grid") .style("fill", "none") .attr("id", ([i,j]) => "error" + (5*j+i)); svg.append("line") .attr("stroke", "steelblue") .attr("stroke-width", 4) .attr("x1", 0).attr("y1", 192) .attr("x2", w).attr("y2", 54); const active = pts.filter(p=> p[0] >= 0 && p[0] < 5 && p[1] >= 0 && p[1] < 5).map(p=>5*p[1]+p[0]); function error() { let row = (i) => active.indexOf(i) > -1 ? 0 : 1; let cum_err_sq = 0; for(let i1 = 0; i1 < 5; ++i1) for(let i2 = 0; i2 < 5; ++i2) cum_err_sq += (line_eq(i1) - line_eq(i2) - (row(i1) - row(i2)))**2; fig.value = Math.sqrt(cum_err_sq); } function update() { // Mouse update? if(d3.event) { let [x,y] = d3.mouse(d3.event.target); let i = Math.trunc(5* x / w); let j = 1 - Math.trunc(y / 128); if(active.indexOf(5*j+i) == -1) { // Turn off other active.splice(active.indexOf(5*(j?0:1)+i), 1, 5*j+i); } } // Update view svg.selectAll(".raster_grid").style("fill", "none"); for(let idx of active) svg.select("#error" + idx).style("fill", "lightsteelblue"); // Update error error(); d3.select(fig).select("#fig_error").text("Error:" + fmt(fig.value) + ". Click to change lit row for each column and update error."); } update(); fig.prepend(alias_error); return fig; }2a:Tb81,viewof fy = { const fig = html`

Actual spatial distribution of color vs approximation by surrounding pixels.
Drag line to change ${tex`f\left(i\right)`} position

` const svg = d3.select(fig).select(".fy_svg"); const actual = svg.append("rect"); actual.attr("id", "fy_actual") .attr("stroke", "none") .attr("fill", "lightsteelblue") .attr("x", 25) .attr("width", 100).attr("height", 100); svg.append("rect") .attr("stroke", "steelblue") .attr("fill", "none") .attr("x", 25).attr("y", 0) .attr("width", 100).attr("height", 100); svg.append("circle") .attr("stroke", "none") .attr("fill", "steelblue") .attr("cx", 75).attr("cy", 50) .attr("r", 4); svg.append("rect") .attr("stroke", "steelblue") .attr("fill", "none") .attr("x", 25).attr("y", 100) .attr("width", 100).attr("height", 100); svg.append("circle") .attr("stroke", "none") .attr("fill", "steelblue") .attr("cx", 75).attr("cy", 150) .attr("r", 4); const upper = svg.append("rect"); upper.attr("id", "fy_approx_upper") .attr("stroke", "steelblue") .attr("fill", "none") .attr("x", 135).attr("y", 0) .attr("width", 100).attr("height", 100); svg.append("circle") .attr("stroke", "none") .attr("fill", "steelblue") .attr("cx", 185).attr("cy", 50) .attr("r", 4); const lower = svg.append("rect"); lower.attr("id", "fy_approx_lower") .attr("stroke", "steelblue") .attr("fill", "none") .attr("x", 135).attr("y", 100) .attr("width", 100).attr("height", 100); svg.append("circle") .attr("stroke", "none") .attr("fill", "steelblue") .attr("cx", 185).attr("cy", 150) .attr("r", 4); const line = svg.append("line"); line.attr("id", "fy_line") .attr("stroke", "black") .attr("stroke-width", 4) .attr("cursor", "move") .call(d3.drag() .on("drag", dragging) .on("end", update)); function dragging() { if(d3.event.y < 50 || d3.event.y > 150) return; update(d3.event.y); } function update(value = undefined) { if(value !== undefined) fig.value = value; else fig.value = d3.event.y; fig.value = Math.min(150, Math.max(50, fig.value)); // Data bounds line.attr("x1", 0).attr("y1", fig.value) .attr("x2", 260).attr("y2", fig.value); actual.attr("y", fig.value - 50); upper.attr("fill", "rgb(" + lightsteelblue.map(c=>Math.round((150-fig.value)/100*c+(fig.value-50)/100*255)).join(",") + ")"); lower.attr("fill", "rgb(" + lightsteelblue.map(c=>Math.round((fig.value-50)/100*c+(150-fig.value)/100*255)).join(",") + ")"); } update(100); return fig; }2b:Ta43,{ const fig = html`

Similar triangles: The triangle containing our desired vertical distance ${tex`\color{${d3.schemeCategory10[2]}}v`} is similar to that defined by the line's slope.

` const svg = d3.select(fig).select(".similar_svg"); svg.append("rect") .attr("x", 100).attr("y", 0) .attr("stroke", "steelblue") .attr("width", 100).attr("height", 100) .attr("fill", "none"); svg.append("circle") .attr("stroke", "none") .attr("fill", "steelblue") .attr("cx", 150).attr("cy", 50) .attr("r", 4); svg.append("rect") .attr("x", 100).attr("y", 100) .attr("stroke", "steelblue") .attr("width", 100).attr("height", 100) .attr("fill", "none"); svg.append("circle") .attr("stroke", "none") .attr("fill", "steelblue") .attr("cx", 150).attr("cy", 150) .attr("r", 4); const g = svg.append("g"); g.attr("transform", "translate(0 -0)"); g.append("path") .attr("fill", "#eaeaea88") .attr("d", "M 139 64 L 150 100 L 150 60 Z"); g.append("line") .attr("stroke", d3.schemeCategory10[1]) .attr("x1", 139).attr("y1", 64) .attr("x2", 150).attr("y2", 100); g.append("text") .text("f'") .style("font-family", "KaTeX_Math") .style("font-style", "italic") .attr("fill", d3.schemeCategory10[1]) .attr("x", 126).attr("y", 88); g.append("line") .attr("stroke", d3.schemeCategory10[2]) .attr("x1", 150).attr("y1", 60) .attr("x2", 150).attr("y2", 100); g.append("text") .text("v") .style("font-family", "KaTeX_Math") .style("font-style", "italic") .attr("fill", d3.schemeCategory10[2]) .attr("x", 155).attr("y", 80); g.append("circle") .attr("stroke", "black") .attr("fill", "white") .attr("cx", 150).attr("cy", 100) .attr("r", 4); g.append("text") .text("M") .style("font-family", "KaTeX_Math") .attr("x", 155).attr("y", 115); g.append("line") .attr("stroke", d3.schemeCategory10[1]) .attr("stroke-dasharray", 4) .attr("x1", 0).attr("y1", 105) .attr("x2", 300).attr("y2", 105); g.append("line") .attr("stroke", "black") .attr("stroke-dasharray", 4) .attr("x1", 300).attr("y1", 15) .attr("x2", 300).attr("y2", 105); g.append("line") .attr("x1", 0).attr("y1", 105) .attr("x2", 300).attr("y2", 15) .attr("stroke", "steelblue") .attr("stroke-width", 4); return fig; }2c:T66b,md`Using [the property of similar triangles](https://en.wikipedia.org/wiki/Similarity_%28geometry%29#Similar_triangles "Wikipedia: Similarity (geometry)—Similar Triangles"), we can express the vertical distance ${tex`\color{${d3.schemeCategory10[2]}}v`} to the midpoint in ratio with the line distance: ${tex.block`\frac{\color{${d3.schemeCategory10[2]}}v}{\color{${d3.schemeCategory10[1]}}f'\left(\mathrm{M}\right)} = \frac{\sqrt{\Delta i^2 + \Delta j^2}}{\Delta i}`} The actual line distance is proportional to the implicit line equation, which is related to our decision variable ${tex`d'`}: ${tex.block`{\color{${d3.schemeCategory10[1]}}f'\left(i,j\right)} = \frac{f\left(\mathrm{M}\right)}{\sqrt{\Delta i^2 + \Delta j^2}}=\frac{d'}{2\sqrt{\Delta i^2 + \Delta j^2}}`} Thus, we can solve for ${tex`\color{${d3.schemeCategory10[2]}}v`} with variables we already have: ${tex.block`\begin{aligned} {\color{${d3.schemeCategory10[2]}}v} &= \frac{\sqrt{\Delta i^2 + \Delta j^2}}{\Delta i}{\color{${d3.schemeCategory10[1]}}f'\left(\mathrm{M}\right)}\\ &= \frac{d'}{2\Delta i} \end{aligned}`} To find the vertical distances we need (from the line to the *upper* pixel above the line and the *lower* one below it), we have to convert the midpoint vertical distance to the distance to the appropriate pixel centers. The line can be at most 1 pixel away from the Midpoint vertically (or a different choice would have been made earlier in the algorithm); similarly, the pixel chosen in that column was either ${tex`j`} or ${tex`j+1`}.Which pixel centers thus straddle the line depends on which of the four cases we find ourselves in: `2d:T10e0,{ const fig = html`

Four cases for the position of the line relative to the midpoint and enclosing pixel centers. Lit pixel is one chosen by Midpoint to fill.

` const svg = d3.select(fig).select(".cases_svg"); let g = svg.append("g"); g.append("rect") .attr("class", "jplus2") .attr("x", 25).attr("y", 0) .attr("stroke", "steelblue") .attr("stroke-dasharray", 4) .attr("width", 50).attr("height", 50) .attr("fill-opacity", 0) .attr("fill", "none"); g.append("circle") .attr("class", "jplus2") .attr("stroke", "none") .attr("stroke-opacity", 0) .attr("fill", "none") .attr("cx", 50).attr("cy", 25) .attr("r", 4); g.append("rect") .attr("class", "jplus") .attr("x", 25).attr("y", 50) .attr("stroke", "steelblue") .attr("stroke-dasharray", 4) .attr("width", 50).attr("height", 50) .attr("fill", "none"); g.append("circle") .attr("class", "jplus") .attr("stroke", "none") .attr("stroke-opacity", 0) .attr("fill", "none") .attr("cx", 50).attr("cy", 75) .attr("r", 4); g.append("rect") .attr("class", "jminus") .attr("x", 25).attr("y", 100) .attr("stroke", "steelblue") .attr("width", 50).attr("height", 50) .attr("fill", "lightsteelblue"); g.append("circle") .attr("class", "jminus") .attr("stroke", "none") .attr("stroke-opacity", 0) .attr("fill", "steelblue") .attr("cx", 50).attr("cy", 125) .attr("r", 4); g.append("rect") .attr("class", "jminus2") .attr("x", 25).attr("y", 150) .attr("stroke", "steelblue") .attr("width", 50).attr("height", 50) .attr("fill-opacity", 0) .attr("fill", "none"); g.append("circle") .attr("class", "jminus2") .attr("stroke", "none") .attr("stroke-opacity", 0) .attr("fill", "steelblue") .attr("cx", 50).attr("cy", 175) .attr("r", 4); g.append("line") .attr("class", "v_line") .attr("stroke", d3.schemeCategory10[2]) .attr("stroke-width", 2) .attr("x1", 50).attr("y1", 100) .attr("x2", 50).attr("y2", 132.5); g.append("text") .attr("class", "v") .text("v") .style("font-family", "KaTeX_Math") .style("font-style", "italic") .attr("fill", d3.schemeCategory10[2]) .attr("x", 35).attr("y", 125); g.append("circle") .attr("class", "M_circle") .attr("stroke", "black") .attr("fill", "white") .attr("cx", 50).attr("cy", 100) .attr("r", 4); g.append("text") .attr("class", "M") .text("M") .style("font-family", "KaTeX_Math") .attr("x", 55).attr("y", 115); g.append("line") .attr("transform", "translate(0 -28)") .attr("class", "line") .attr("x1", 0).attr("y1", 175) .attr("x2", 100).attr("y2", 150) .attr("stroke", "steelblue") .attr("stroke-width", 4); g = g.clone(true); g.attr("transform", "translate(110 0)"); g.select(".line").attr("transform", "translate(0 -45)"); g.select(".v_line").attr("y2", 117.5); g.select(".v").attr("y", 115); g.select(".M").attr("y", 98); g.selectAll(".jminus2").attr("stroke-dasharray", 4).attr("fill", "none"); g.selectAll(".jplus").attr("stroke-dasharray", 0).attr("fill", "steelblue"); g.select(".jplus").attr("fill", "none"); g = g.clone(true); g.attr("transform", "translate(220 0)"); g.select(".line").attr("transform", "translate(0 -80)"); g.select(".v_line").attr("y2", 82.5); g.select(".v").attr("y", 98); g.select(".M").attr("y", 115); g.select(".jplus").attr("fill", "lightsteelblue"); g.select(".jminus").attr("fill", "none"); g = g.clone(true); g.attr("transform", "translate(330 0)"); g.select(".line").attr("transform", "translate(0 -103)"); g.select(".v_line").attr("y2", 57.5); g.select(".v").attr("y", 74); g.selectAll(".jminus").attr("fill", "none").attr("stroke-dasharray", 4); g.selectAll(".jplus2").attr("stroke-dasharray", 0).attr("fill", "steelblue"); g.select(".jplus2").attr("fill", "none"); return fig; }2e:T100f,md`In the first case, row ${tex`j`} was chosen but the line is below its pixel center (thus ${tex`1\geq {\color{${d3.schemeCategory10[2]}}v} > 0.5`}); similarly, in the second case, the line is between the pixel center at ${tex`\left(i,j\right)`} and ${tex`\mathrm{M}`} (thus ${tex`0.5\geq {\color{${d3.schemeCategory10[2]}}v} > 0`}). The other two cases are symmetric geometrically and with respect to sign of ${tex`\color{${d3.schemeCategory10[2]}}v`}. Knowing this, we can determine which are the lower and upper pixels and their respective color weights. + In the first case, the lower pixel is ${tex`\left(i,j-1\right)`} and the upper pixel is ${tex`\left(i,j\right)`}. When ${tex`\color{${d3.schemeCategory10[2]}}v`} is closest to ${tex`\left(i,j\right)`}, its value is 0.5 and maximally intense; at the line's farthest, ${tex`{\color{${d3.schemeCategory10[2]}}v}=1`} and the intensity is split. The color weight just linearly interpolates along this line: ${tex.block` \begin{aligned} w_{i,j} &= \frac{{\color{${d3.schemeCategory10[2]}}v}-\frac{1}{2}}{1-\frac{1}{2}}\left(\frac{1}{2}-1\right) + 1\\ &= \frac{3}{2}- {\color{${d3.schemeCategory10[2]}}v}\\ &= \frac{3\Delta i-d'}{2\Delta i}\\ w_{i,j-1} &= 1-w_{i,j}\\ &={\color{${d3.schemeCategory10[2]}}v}-\frac{1}{2}\\ &=\frac{d'-\Delta i}{2\Delta i} \end{aligned} `} + In the second case, the lower pixel is ${tex`\left(i,j\right)`} and the upper pixel is ${tex`\left(i,j\right)`}, but the line is below the midpoint. The lower pixel has maximum intensity at the lower pixel center and decrease to split when the line hits the midpoint. ${tex.block` \begin{aligned} w_{i,j} &= \frac{{\color{${d3.schemeCategory10[2]}}v}-0}{\frac{1}{2}-0}\left(1-\frac{1}{2}\right) + \frac{1}{2}\\ &= {\color{${d3.schemeCategory10[2]}}v}+\frac{1}{2}\\ &= \frac{d'+\Delta i}{2\Delta i}\\ w_{i,j+1} &= 1-w_{i,j}\\ &=\frac{1}{2}-{\color{${d3.schemeCategory10[2]}}v}\\ &=\frac{\Delta i-d'}{2\Delta i} \end{aligned} `} + The only difference between the second and third case is that the line is *above* the midpoint and thus the lit pixel is above as well. This swaps the roles of the lower/upper from the previous case. In addition, ${tex`\color{${d3.schemeCategory10[2]}}v`} is now negative, but ranges through the same absolute values at the second case. But though the upper/lower roles are switched, the *values* assigned to them is the same as the second case. ${tex.block` \begin{aligned} w_{i,j} &= \frac{{\color{${d3.schemeCategory10[2]}}v}-0}{-\frac{1}{2}-0}\left(1-\frac{1}{2}\right) + \frac{1}{2}\\ &= \frac{1}{2}-{\color{${d3.schemeCategory10[2]}}v}\\ &= \frac{\Delta i-d'}{2\Delta i}\\ w_{i,j-1} &= 1-w_{i,j}\\ &=\frac{d'+\Delta i}{2\Delta i} \end{aligned} `} + The final case is a mirror of the first: The line is above the lit pixel, so it is the lower pixel and ${tex`\left(i,j+1\right)`} is the upper. The intensity decrease to split between the two pixels as ${tex`\color{${d3.schemeCategory10[2]}}v`} decreases and the approaches the pixel boundary. ${tex.block` \begin{aligned} w_{i,j} &= \frac{{\color{${d3.schemeCategory10[2]}}v}-{-\frac{1}{2}}}{-1-{-\frac{1}{2}}}\left(\frac{1}{2}-1\right) + 1\\ &= {\color{${d3.schemeCategory10[2]}}v}+\frac{3}{2}\\ &= \frac{d'+3\Delta i}{2\Delta i}\\ w_{i,j-1} &= 1-w_{i,j}\\ &=-\frac{1}{2}-{\color{${d3.schemeCategory10[2]}}v}\\ &=\frac{-d'-\Delta i}{2\Delta i} \end{aligned} `} The final color for each pixel just uses the appropriate weight as an alpha value for blending or scales the color directly. This color calculation occurs **after** we have determined the new pixel based upon the midpoint but **before** we update the decision variable ${tex`d'`}. While the above derivations are involved, remember the simple concept of Wu's approach: We color the two straddling pixels based upon their vertical distance from the true line. The above formulas just express this concept in terms of the Midpoint-based approach. `2f:Tc5f,viewof tri_grid = { let fig = html`

Aliased Triangle.

` const tri = raster_grid({size: grid_size, grid_width: ewidth, grid:false, centers: false, grid_height: height, mousedown: () => null}); tri.style.width = ewidth + "px"; tri.style.height = height + "px"; tri.style.margin = "auto"; tri.style.border = "thin solid steelblue"; let svg = tri.querySelector("svg"); svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "tri" + (grid_count*j+i)); for(const pt of fill_triangle(a, b, c)) { d3.select(tri).select("rect#tri" + (grid_count * pt[1] + pt[0])).style("fill", "lightsteelblue"); } const wu = raster_grid({size: grid_size, grid_width: ewidth, grid:false, centers:false, grid_height: height, mousedown: () => null}); wu.style.width = ewidth + "px"; wu.style.height = height + "px"; wu.style.margin = "auto"; wu.style.display = "none"; wu.style.border = "thin solid steelblue"; svg = wu.querySelector("svg"); svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "wutri" + (grid_count*j+i)); // Do Wu-like approach for triangles. Just use a modified version of our fill_triangle that checks // if near boundary function fill_triangle_wu(vert_a, vert_b, vert_c) { const pts = []; let i_min = d3.min([vert_a, vert_b, vert_c], ([x,y]) => (Math.floor(x))); let i_max = d3.max([vert_a, vert_b, vert_c], ([x,y]) => (Math.ceil(x))); let j_min = d3.min([vert_a, vert_b, vert_c], ([x,y]) => (Math.floor(y))); let j_max = d3.max([vert_a, vert_b, vert_c], ([x,y]) => (Math.ceil(y))); for(let i = i_min; i <= i_max; ++i) for(let j = j_min; j <= j_max; ++j) if(in_triangle([i,j], vert_a, vert_b, vert_c)) pts.push([[i,j], 1.0]); else { // Near boundary and need to AA? Set each coord to 0 in turn to find edge pt // Demo, not super efficient for(let [edge_start, edge_end] of [[vert_a, vert_b], [vert_b, vert_c], [vert_c, vert_a]]) { let w = 0.; if(Math.abs(edge_end[1] - edge_end[0]) <= Math.abs(edge_end[1] - edge_end[0])) { // Not steep w = 1 - vert_dist(edge_start, edge_end, [i,j] ); } else { // Steep w = 1 - vert_dist([edge_start[1], edge_start[0]], [edge_end[1], edge_end[0]], [j,i]); } if(w > 0) pts.push([[i,j], w]); } } return pts; } for(const pt of fill_triangle_wu(a, b, c)) { console.log(pt); d3.select(wu).select("rect#wutri" + (grid_count * pt[0][1] + pt[0][0])) .style("fill", "lightsteelblue") .style("fill-opacity", pt[1]); } fig.prepend(wu); fig.wu = wu; fig.prepend(tri); fig.tri = tri; return fig; }30:T5a6,{ let fig = html`

Location of "true" pixels that are effectively convolved with a box filter to produce a Wu-corrected line

` const w = Math.min(width,640); const convolve = raster_grid({numberH: 5, numberV: 2, grid_width: w, grid_height: 256, mousedown: ()=>{}}); convolve.style.width = w + "px"; convolve.style.height = 256 + "px"; convolve.style.margin = "auto"; convolve.style.border = "thin solid steelblue"; let svg = convolve.querySelector("svg"); svg = d3.select(svg); svg.selectAll(".raster_grid") .style("fill", "none") .attr("id", ([i,j]) => "convolve" + (5*j+i)); const [x1,y1] = [-0.5, 0]; const [x2,y2] = [ 4.5, 1]; const line_eq = (i) => (i+0.5) / 5; const pts = midpoint([x1,y1], [x2,y2]); const active = pts.filter(p=> p[0] >= 0 && p[0] < 5 && p[1] >= 0 && p[1] < 5) .map(p => [w*p[0]/5, 256 - 128 * ((2*p[0]+1)/10+1)]); for(let pt of active) svg.append("rect") .attr("fill", "lightsteelblue") .attr("stroke", "steelblue") .attr("x", pt[0]).attr("y", pt[1]) .attr("width", w/5).attr("height", 128); svg.append("line") .attr("stroke", "steelblue") .attr("stroke-width", 4) .attr("x1", 0).attr("y1", 192) .attr("x2", w).attr("y2", 54); fig.prepend(convolve); return fig; }31:T6fd,md`For polygons (as well as lines), the signed distance can be used on the GPU to implement a Wu's approach directly on the fragment shader (we can convert to vertical distance via the similar triangles above or the cosine directly), so it is still applicable on modern hardware. As an aside, the [Wikipedia article](https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm "Wikipedia: Xiaolin Wu's Line Algorithm") on Wu's algorithm as of this writing uses a floating-point DDA approach, but has "corrections" for the endpoints that do not exist in the original paper. From a theoretic standpoint, the line passes directly through the endpoints and thus no special treatment is needed. It does make the entire line have a two-pixel color for what it is worth. As even [the page's own Talk](https://en.wikipedia.org/wiki/Talk:Xiaolin_Wu%27s_line_algorithm#Pseudo-code_does_not_match_Wu's_Fast_Antialiased_Line_Generator 'Talk for "Xiaolin Wu's Line Algorithm"') indicates, the code has no tie to Wu's actual approach. I have not been able to track the provenance of this algorithm. ## Appendix: Implementation I hacked my midpoint code as described above, accounting for the fourish different cases. Nothing exciting otherwise. Similarly, I used my triangle code to generate polygon points while determining how far from each edge the point was. Both [Wu's original approach](https://dl.acm.org/citation.cfm?id=122734 "Xiaolin Wu: An Efficient Antialias Technique") and [Zingl's modifications to antialias Bresenham](http://members.chello.at/~easyfilter/bresenham.html "The Beauty of Bresenham's Algorithm") are likely faster if that is required, though neither fit GPU architectures well (whereas the *concept* of the above/below works well on GPUs with SDFs as mentioned above). `32:Td22,{ // Line offset depending on steepness const offset = Math.abs(end[0] - start[0]) >= Math.abs(end[1] - start[1])? [0, 1] : [1, 0]; // Base raster line. Just run Midpoint const line_points = midpoint(start, end); for(const pt of line_points) { // Update aliased line with full intensity let rect = d3.select(viewof aliased_grid).select("rect#aliased" + (grid_count * pt[1] + pt[0])); rect.style("fill", "lightsteelblue"); } // Wu corrected Midpoint function midpoint_wu([x0, y0], [x1, y1]) { // Round to determine pixel location const pixel = (x,y) => [Math.round(x), Math.round(y)] let [i0, j0] = pixel(x0,y0); let [i1, j1] = pixel(x1,y1); let [i,j] = [i0,j0]; // Steps let stepi = i1 > i0 ? 1 : i1 < i0? -1 : 0; let stepj = j1 > j0 ? 1 : j1 < j0? -1 : 0; // Determine error let di = Math.abs(i1 - i0); let dj = Math.abs(j1 - j0); // Find line orientation let steep = false; if(dj > di) { steep = true; [i,j] = [j,i]; [di,dj] = [dj,di]; [stepi,stepj] = [stepj,stepi]; } let d = di - (2 * dj); // Rasterize const pixels = []; const push_pixel = (i,j,steep,weight) => steep? pixels.push([j,i,weight]) : pixels.push([i,j,weight]); push_pixel(i,j,steep,1.0); for(let count = 1; count <= di; ++count) { // Determine color weights before moving let v = d / (2*di); let w_upper = 0, w_lower = 0; let direction = 1; let ij_upper = false; if(v > 0.5) // Line below lower pixel middle { ij_upper = true; w_upper = 1.5 - v; } else if(v < -0.5) // Line above upper pixel middle { w_upper = -v -.5; direction = -1; } else // Line between the two middles { w_upper = 0.5 - v; ij_upper = d <= 0; } w_lower = 1 - w_upper; // Update midpoint/error term if(d <= 0) { j += stepj; d += 2 * di; } i += stepi; d -= 2 * dj; //console.log(i,j,d,v,w_lower,w_upper); push_pixel(i,ij_upper? j-direction*stepj : j+direction*stepj,steep,ij_upper? w_lower : w_upper); push_pixel(i,j,steep,ij_upper? w_upper : w_lower); } return pixels; } const aa_points = midpoint_wu(start, end); for(const pt of aa_points) { let rect = d3.select(viewof aliased_grid).select("rect#wu" + (grid_count * pt[1] + pt[0])); rect.style("fill", "lightsteelblue"); rect.style("fill-opacity", pt[2]); } // Render to the canvas const context = (viewof aliased_grid).context; const [w,h] = [context.canvas.width, context.canvas.height]; const dpi = window.devicePixelRatio; context.clearRect(0,0,w,h); context.fillStyle = "lightsteelblue"; if(use_antialiasing.indexOf("aa") > -1) { const lightsteelblue = [176, 196, 222]; for(const pt of midpoint_wu(mutable start_grid.map(p=>dpi*p), mutable end_grid.map(p=>dpi*p))) { context.fillStyle = "rgba(" + lightsteelblue.join(",") + "," + pt[2] + ")"; context.fillRect(pt[0], pt[1], 1, 1); } } else for(const pt of midpoint(mutable start_grid.map(p=>dpi*p), mutable end_grid.map(p=>dpi*p))) context.fillRect(pt[0], pt[1], 1, 1); return md`Update points`; }33:[] 25:{"id":"85bb356f913fc9b1","slug":"antialiasing-lines-and-triangles-ii-wus-algorithm","title":"Antialiasing Lines and Triangles II: Wu's Algorithm","thumbnail":"1a81e3176a29f066f512ef7db1ca8d82e9ff9400fcf680135b7db335d6a7285c","access_level":"public","create_time":"$D2019-10-07T14:59:31.057Z","update_time":"$D2021-09-16T14:28:37.517Z","view_time":null,"first_public_time":"$D2019-10-14T14:46:26.101Z","has_unpublished_edits":null,"fork":{"id":"4b19474775183045","slug":"antialiasing-lines-and-triangles-i-supersamping","title":"Antialiasing Lines and Triangles I: Supersamping","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"stars":2,"starred":false,"owner":{"type":"team","id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":"starter_2024"},"version":1252,"publish_version":1252,"role":null,"authored":false,"authors":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null}],"members":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":6,"collection":{"id":"fa97e7eb1e9d2163","slug":"computer-graphics","title":"Computer Graphics","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"type":"notebook","body":{"titling":"auto","title":"Antialiasing Lines and Triangles II: Wu's Algorithm","cells":[{"id":149,"value":"md`# Antialiasing Lines and Triangles II: Wu's Algorithm\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"$27","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"viewof use_antialiasing = checkbox({\n options: [{value: \"aa\", label: \"Use antialiasing\"},\n {value: \"zoom\", label: \"Zoom In\"}],\n value: [\"zoom\"]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"$28","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":616,"value":"$29","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":612,"value":"md`To eliminate error, we would want to choose an integer ${tex`j=f\\left(i\\right)`} for every ${tex`i`}, which can only occur if the curve takes on only integer values at each sample column (e.g., is a horizontal line). Instead, we *simulate* the pixel ${tex`\\left(i, f\\left(i\\right)\\right)`} by splitting its intensity into two parts: One above and one below the true curve, weighted proportionally by how close each is to the true position. Of course, we cannot partially color in discrete pixels, so we color in the two surrounding rasters depending on what side of the curve they are on:\n\n${tex.block`\nc_{i,f\\left(i\\right)} \\approx \n\\begin{cases}\nc_{i,\\left\\lceil f\\left(i\\right)\\right\\rceil} = \\left( f\\left(i\\right) - \\left\\lfloor f\\left(i\\right) \\right\\rfloor\\right)c & \\text{above}\\\\\nc_{i,\\left\\lfloor f\\left(i\\right)\\right\\rfloor} = \\left( \\left\\lceil f\\left(i\\right) \\right\\rceil - f\\left(i\\right)\\right)c & \\text{below}\n\\end{cases}\n`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":500,"value":"$2a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":493,"value":"md`As the vertical separation from the sample position and a pixel center decreases, its color intensity increases while the intensity on the other side of the sample decreases in proportion. This visually approximates the true \"pixel\".`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":716,"value":"md`### Lines\n\nFor lines, we have [several incremental approaches](https://observablehq.com/@infowantstobeseen/drawing-lines \"Drawing Lines\") that can be adapted to incorporate Wu antialiasing. [Wu's paper](https://doi.org/10.1145%2F127719.122734 'Xiaolin Wu: \"An Efficient Antialias Technique\", SIGGRAPH 91') uses a modified, integerized DDA algorithm. Here, we modify the Midpoint Algorithm to include the antialias calculation. \n\nDuring the Midpoint line algorithm, we use the implicit line equation to provide our decision variable: whether the midpoint is above or below the line. To find the vertical distance from the pixel centers to the line, we will start first with the vertical of the midpoint from the line. Consider the triangle consisting of the midpoint, the point on the line vertically above or below the midpoint as appropriate, and the point on the line closest to the midpoint. This triangle is similar to the triangle defined by the entire line segment:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":774,"value":"$2b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":832,"value":"$2c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1039,"value":"$2d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1032,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":744,"value":"md`### Polygons\n\nWu's approach can be applied to polygons or other closed object, so long as a the function to determine the edge boundary ${tex`f\\left(i\\right)`} can be calculated at every position along the boundary. Wu's original approach integrates more naturally with scan-conversion, where the edges are walked directly. If using barycentric coordinates, the \"vertical\" distance from each edge can be calculated using the similar triangle approach above, and, if within half a pixel, colored appropriately. This is not as efficient as a the scan-line approach, but is suitable for a GPU implementation.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1216,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"md`## Summary\n\nWu's algorithm provides a simple and efficient means of antialiasing lines and curves based upon correcting visual error. This approach, though visually based, is equivalent to convolving a box filter over the two pixels straddling the line, where the original signal has support at the \"true\" pixel ${tex`\\left(i,f\\left(i\\right)\\right)`} for every row:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":875,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":871,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"import {raster_grid} from \"@infowantstobeseen/raster-grid\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":437,"value":"import {fill_triangle, in_triangle} from \"@infowantstobeseen/drawing-triangles\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"import {midpoint} from \"@infowantstobeseen/drawing-lines\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1226,"value":"import {calc_barycentric} from \"@infowantstobeseen/barycentric-coordinates\"\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"import {checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"d3 = require(\"d3-drag@1.2\",\"d3-selection@1.4\", \"d3-format\", \"d3-scale-chromatic\", \"d3-array\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":707,"value":"fmt = d3.format(\" 6.2f\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":641,"value":"lightsteelblue = [176, 196, 222]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"ewidth = Math.min(width, 400)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"height = ewidth","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"grid_count = 20","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"grid_size = Math.min(ewidth, height) / grid_count","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"mutable start = [0,0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"mutable end = [19,19]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"mutable start_grid = [ grid_size / 2, height - grid_size / 2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"mutable end_grid = [(grid_count - 0.5) * grid_size, height - (grid_count - 0.5) * grid_size]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":444,"value":"mutable a = [12, 18]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":447,"value":"mutable b = [0, 8]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":450,"value":"mutable c = [8,0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"distance_line = (start_line, end_line, pt) => \n{\n // Implicit line Ax+By+C=d where A=y0-y1, B=x1-x0, C=x0y1-x1y0\n let A = start_line[1] - end_line[1];\n let B = end_line[0] - start_line[0];\n let C = start_line[0] * end_line[1] - start_line[1] * end_line[0];\n return (A*pt[0]+B*pt[1]+C) / Math.sqrt(A**2 + B**2);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"vert_dist = (start_line, end_line, pt) =>\n{\n // Vertical distance of pt to line. Use similar triangles & implicit ditance D to show \n // that v = D * sqrt(dx**2 + d**y) / dx\n let dx = Math.abs(start_line[0] - end_line[0]);\n let dy = Math.abs(start_line[1] - end_line[1]);\n return Math.abs(distance_line(start_line, end_line, pt)) * Math.sqrt(dx**2+dy**2) / dx;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"{\n\n d3.select(viewof aliased_grid).selectAll(\".endpoint\").each(function process() {\n const target = {\"start\": start_grid, \"end\": end_grid}[this.classList[1]];\n d3.select(this).attr(\"cx\", target[0]).attr(\"cy\", target[1]);\n });\n\n d3.select(viewof aliased_grid).selectAll(\".endbox\").each(function process() {\n const target = {\"start\": start_grid, \"end\": end_grid}[this.classList[1]];\n d3.select(this).attr(\"x\", grid_size*Math.trunc(target[0]/grid_size))\n .attr(\"y\", grid_size*Math.trunc(target[1]/grid_size));\n });\n\n d3.select(viewof aliased_grid).selectAll(\".line\")\n .attr(\"x1\", start_grid[0])\n .attr(\"y1\", start_grid[1])\n .attr(\"x2\", end_grid[0])\n .attr(\"y2\", end_grid[1]);\n \n \n return md`Update the lines`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":291,"value":"{\n const zoomed = use_antialiasing.indexOf(\"zoom\") > -1;\n const aa = use_antialiasing.indexOf(\"aa\") > -1;\n if(zoomed)\n {\n (viewof aliased_grid).aliased.style.display = !aa? \"block\" : \"none\";\n (viewof aliased_grid).wu.style.display = aa? \"block\" : \"none\";\n (viewof aliased_grid).canvas.style.display = \"none\";\n d3.select(\"#fig_legend\").text((aa? \"Wu\" : \"Aliased\") + \" Zoomed-in Line. Drag ends to generate line.\");\n }\n else\n {\n (viewof aliased_grid).aliased.style.display = \"none\";\n (viewof aliased_grid).wu.style.display = \"none\";\n (viewof aliased_grid).canvas.style.display = \"block\";\n d3.select(\"#fig_legend\").text((aa? \"Wu\" : \"Aliased\") + \" Full Line. Zoom-in to change line.\"); \n }\n \n (viewof tri_grid).tri.style.display = !aa? \"block\" : \"none\";\n (viewof tri_grid).wu.style.display = aa? \"block\" : \"none\";\n d3.select(\"#tri_legend\").text((aa? \"Wu\" : \"Aliased\") + \" triangle.\"); \n\n return md`Update view`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 26:"$25:body"