2c:null 2d:["$","title",null,{"children":"Antialiasing Lines and Triangles I: Supersamping | T.J. Jankun-Kelly | Observable"}] 32:T1708,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 supersam = raster_grid({size: 0.5 * grid_size, grid_width: ewidth, grid:false, centers:false, grid_height: height, mousedown: () => null}); supersam.style.width = ewidth + "px"; supersam.style.height = height + "px"; supersam.style.margin = "auto"; supersam.style.display = "none"; supersam.style.border = "thin solid steelblue"; svg = supersam.querySelector("svg"); svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "supersam" + (2*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(supersam).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(supersam); fig.supersam = supersam; fig.prepend(aliased); fig.aliased = aliased; return fig; }33:T764,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. ## Supersampling Supersamping attempts to solve the problem of not having enough pixels by adding more pixels, generally increasing each dimension 2x, 4x, or some other increase. It is by far the simplest method, but also very costly, having to render up to 4x, 16x, or some squared factor additional pixels. In addition, when downsampling, the choice of filter will affect the performance and appearance. Finally, everything must be drawn twice or more times as large, which includes the width of lines. As [the line drawing methods we discussed](https://observablehq.com/@infowantstobeseen/drawing-lines "Drawing Lines") only render 1 pixel width lines, other approaches must be taken to correct for supersampling widths (such as rendering each line more than once). If we do not widen the lines, they will appear less bright when downsampled to the lower resolution. Note that high "DPI" (really PPI, [pixel-per-inch](https://en.wikipedia.org/wiki/Pixel_density "Pixel Density")) displays such as Retina Displays are already supersampled from their reported resolution. If aliasing artifacts still occurs on these diplays, we must supersample at an even higher resolution or apply an alternative method. ### Polygons Polygons need no special treatment under supersampling other than increasing their bounding box to account for the higher pixel density. `34:T6e2,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 supersam = raster_grid({size: 0.5 * grid_size, grid_width: ewidth, grid:false, centers:false, grid_height: height, mousedown: () => null}); supersam.style.width = ewidth + "px"; supersam.style.height = height + "px"; supersam.style.margin = "auto"; supersam.style.display = "none"; supersam.style.border = "thin solid steelblue"; svg = supersam.querySelector("svg"); svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "supertri" + (2*grid_count*j+i)); for(const pt of fill_triangle(a.map(p=>2*p), b.map(p=>2*p), c.map(p=>2*p))) { d3.select(supersam).select("rect#supertri" + (2*grid_count * pt[1] + pt[0])).style("fill", "lightsteelblue"); } fig.prepend(supersam); fig.supersam = supersam; fig.prepend(tri); fig.tri = tri; return fig; }35:T8b6,{ // 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"); } // Supersampled raster line. For each point drawn figure out which side the true line was and draw the other // side (essentially, what we would do w/ Wu's. // Exact endpoints for AA calculations const start_true = start.map(p=>2*p); const end_true = end.map(p=>2*p); for(const pt of midpoint(start_true, end_true)) { let srect = d3.select(viewof aliased_grid).select("rect#supersam" + (2*grid_count * pt[1] + pt[0])); srect.style("fill", "lightsteelblue"); if(distance_line(start_true, end_true, pt) <= 0) srect = d3.select(viewof aliased_grid).select("rect#supersam" + (2*grid_count * (pt[1]+offset[1]) + pt[0] + offset[0])); else srect = d3.select(viewof aliased_grid).select("rect#supersam" + (2*grid_count * (pt[1]-offset[1]) + pt[0] - offset[0])); srect.style("fill", "lightsteelblue"); } // Render to the canvases 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"; 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); offscreen.clearRect(0,0,2*w,2*h); offscreen.fillStyle = "lightsteelblue"; for(const pt of midpoint(mutable start_grid.map(p=>2*dpi*p), mutable end_grid.map(p=>2*dpi*p))) { offscreen.fillRect(...pt, 1, 1); offscreen.fillRect(...pt.map(p=>[p[0]+ offset[0],p[1]+ offset[1]]), 1, 1); } // Copy supersampled canvas if antialiasing if(use_antialiasing.indexOf("aa") > -1) { context.imageSmoothingEnabled = true; context.drawImage(offscreen.canvas, 0, 0, 2*w, 2*h, 0, 0, w, h); } return md`Update points`; }36:[] 30:{"id":"4b19474775183045","slug":"antialiasing-lines-and-triangles-i-supersamping","title":"Antialiasing Lines and Triangles I: Supersamping","thumbnail":"1a81e3176a29f066f512ef7db1ca8d82e9ff9400fcf680135b7db335d6a7285c","access_level":"public","create_time":"$D2019-09-24T21:24:19.077Z","update_time":"$D2021-09-16T14:27:28.796Z","view_time":null,"first_public_time":"$D2019-10-07T15:01:56.560Z","fork":false,"stars":0,"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":482,"publish_version":482,"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,"subscribed":null,"forks":1,"collection":{"id":"fa97e7eb1e9d2163","slug":"computer-graphics","title":"Computer Graphics","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"type":"notebook","body":{"title":"Antialiasing Lines and Triangles I: Supersamping","cells":[{"id":149,"value":"md`# Antialiasing Lines and Triangles I: Supersamping\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$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"},{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":440,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":156,"value":"md`## Summary\n\nSupersampling is simple, but not cheap, even with parallel GPUs; adding interativity makes the cost generally too prohibitive. In addition, it may not address the pixelation if the change in the primitive is higher than the supersampled rate. Others approaches are generally taken.\n\n## Appendix: Implementation\n\nTwo canvases are used for each example: The displayed canvas, an a hidden supersampled canvas as 2x resolution. We just toggle which is displayed as appropriate.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9,"value":"import {raster_grid} from \"@infowantstobeseen/raster-grid\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":437,"value":"import {fill_triangle} from \"@infowantstobeseen/drawing-triangles\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":35,"value":"import {midpoint} from \"@infowantstobeseen/drawing-lines\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":144,"value":"import {checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11,"value":"d3 = require(\"d3-drag@1.2\",\"d3-selection@1.4\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":13,"value":"ewidth = Math.min(width, 400)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":15,"value":"height = ewidth","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":17,"value":"grid_count = 20","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":19,"value":"grid_size = Math.min(ewidth, height) / grid_count","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":21,"value":"mutable start = [0,0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":23,"value":"mutable end = [19,19]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":25,"value":"mutable start_grid = [ grid_size / 2, height - grid_size / 2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$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"},{"id":444,"value":"mutable a = [12, 18]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":447,"value":"mutable b = [0, 8]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":450,"value":"mutable c = [8,0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$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"},{"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"},{"id":343,"value":"offscreen = DOM.context2d(window.devicePixelRatio*2*ewidth, window.devicePixelRatio*2*height, 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":31,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$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"},{"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).supersam.style.display = aa? \"block\" : \"none\";\n (viewof aliased_grid).canvas.style.display = \"none\";\n d3.select(\"#fig_legend\").text((aa? \"Supersampled\" : \"Aliased\") + \" Zoomed-in Line. Drag line & ends to generate line.\");\n }\n else\n {\n (viewof aliased_grid).aliased.style.display = \"none\";\n (viewof aliased_grid).supersam.style.display = \"none\";\n (viewof aliased_grid).canvas.style.display = \"block\";\n d3.select(\"#fig_legend\").text((aa? \"Supersampled\" : \"Aliased\") + \" Full Line. Zoom-in to change line.\"); \n }\n (viewof tri_grid).tri.style.display = !aa? \"block\" : \"none\";\n (viewof tri_grid).supersam.style.display = aa? \"block\" : \"none\";\n d3.select(\"#tri_legend\").text((aa? \"Supersampled\" : \"Aliased\") + \" triangle.\"); \n \n return md`Update view`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 31:"$30:body"