2b:null 2c:["$","title",null,{"children":"Drawing Lines | T.J. Jankun-Kelly | Observable"}] 31:T484,{ const pixels = new Uint8ClampedArray(4 * 4); pixels.set([70,130,180,255], 0); // steelblue const above_below = raster_grid({value: pixels, numberH: 2, grid_width: 160, grid_height: 160, mousedown: () => null}); let svg = d3.select(above_below).select("svg"); svg.style("margin", "auto"); svg.style("display", "block"); svg.selectAll(".raster_grid").style("transition", "fill .4s ease").attr("id", ([i,j]) => "above_below" + (2*j+i)); svg.append("text") .attr("x", 25).attr("y", 110) .text("(i,j)"); const line = svg.append("line") .attr("stroke", "black") .attr("stroke-width", 3) .attr("x1", 0) .attr("y1", 140) .attr("x2", 160) .attr("y2", 65); const rect1 = svg.select("rect#above_below1"); const rect3 = svg.select("rect#above_below3"); let low = true; while (true) { if(low) { rect1.attr("fill", "lightsteelblue"); rect3.attr("fill", "transparent"); low = !low; } else { rect1.attr("fill", "transparent"); rect3.attr("fill", "lightsteelblue"); low = !low; } yield Promises.tick(2000).then(() => above_below); } }32:T586,md`## Digital Difference Analyzer (DDA) The explicit line equation, or more commonly the *slope-intercept form*, solves for one of the coordinates in terms of the other; usually, we solve for ${tex`y`} in terms of ${tex`x`}: ${tex.block`y=mx+b`} Thus, every step by 1 in ${tex`x`} increments ${tex`y`} by ${tex`m`}; similarly, if we solve for ${tex`x`} instead, a step of 1 in ${tex`y`} means a step of ${tex`\frac{1}{m}`} in ${tex`x`}. The slope ${tex`m=\frac{y_1 - y_0}{x_1 - x_0} = \frac{\Delta y}{\Delta x}`} is just the ratio of the two differences; we analyze the amount of difference induced by increasing one dimension by a whole pixel to find the next pixel (thus, a *digial difference analyzer*). Algorithmically, we first determine the *driving axis* (DA) of the line: The dimension that varies the most in absolute value. The integer part of the DA's difference give us the number of whole iterations we have to do column- or row-wise as appropriate. For every increment, we add the appropriate ratio of the differences to the other (passive) axis to determine the next pixel. Thus, for the line ${tex`y=\frac{2}{3}x+10`} between ${tex`\left(0,10\right)`} and ${tex`\left(3,12\right)`}, we step over ${tex`i`} three times, adding ${tex`\frac{2}{3}`} to 0 each time to determine the next ${tex`j`}. We repeat until complete:`33:Tcad,viewof dda_grid = { const dda = raster_grid({size: grid_size, grid_width: ewidth, grid_height: height, mousedown: () => null}); dda.append(html`

DDA Algorithm. Drag line & ends to generate points.

`); let svg = dda.getElementsByTagName("svg")[0]; svg.style.margin = "auto"; svg.style.display = "block"; svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "transparent") .attr("id", ([i,j]) => "dda" + (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() { mutable dda_points.splice(0, mutable dda_points.length); mutable dda_points = mutable dda_points; svg.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) 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; } return dda; }34:T7a5,{ const pixels = new Uint8ClampedArray(4 * 4); pixels.set([70,130,180,255], 0); // steelblue const above_below = raster_grid({value: pixels, numberH: 2, grid_width: 160, grid_height: 160, mousedown: () => null}); let svg = d3.select(above_below).select("svg"); svg.style("margin", "auto"); svg.style("display", "block"); svg.selectAll(".raster_grid").style("transition", "fill .4s ease").attr("id", ([i,j]) => "above_below" + (2*j+i)); svg.append("text") .attr("x", 8).attr("y", 110) .text("(i,j)"); svg.append("circle") .attr("stroke", "black") .attr("fill", "transparent") .attr("r", 4) .attr("cx", 120).attr("cy", 80); svg.append("text") .attr("x", 128).attr("y", 78) .text("M"); const line = svg.append("line") .attr("stroke", "black") .attr("stroke-width", 3) .attr("x1", 0) .attr("y1", 140); const approach = svg.append("line") .attr("stroke", "black") .attr("stroke-width", 3) .attr("stroke-dasharray", "1%") .attr("x1", 120) .attr("y1", 80); const rect1 = svg.select("rect#above_below1"); const rect3 = svg.select("rect#above_below3"); const fig = d3.select(above_below).append("figcaption") .style("margin", "auto") .style("text-align", "center"); let low = true; while (true) { if(low) { rect1.attr("fill", "lightsteelblue"); rect3.attr("fill", "transparent"); line.attr("x2", 160).attr("y2", 100); approach.attr("x2", 127).attr("y2", 108); fig.html("Line above midpoint; do not increment j."); low = !low; } else { rect1.attr("fill", "transparent"); rect3.attr("fill", "lightsteelblue"); line.attr("x2", 160).attr("y2", 20); approach.attr("x2", 106).attr("y2", 61); fig.html("Line below midpoint; increment j."); low = !low; } yield Promises.tick(2000).then(() => above_below); } }35:Tc33,md`If we have filled in a raster pixel ${tex`\left(i,j\right)=\operatorname{round}\left(x,y\right)`}, we know our next step is to increment by 1 along the driving axis; now we must determine whether to increment along the passive axis or leave it the same. Using the implicit line equation, we can see if the border between those two pixels falls above or below the line. Specifically, we can check the *midpoint* along that edge ${tex`M=\left(i+1, j+\frac{1}{2}\right)`} (for lines with a slope between 0 and 1). If our line equation is ${tex`f\left(i,j\right)=Ai+Bj+C`}, then ${tex`f\left(M\left(i,j\right)\right)`} determines which side the line falls on: If ${tex`f\left(M\left(i,j\right)\right) > 0`}, the line is below the midpoint so we do not increment along the passive axis; otherwise, ${tex`f\left(M\left(i,j\right)\right) < 0`}, the line is above, so we increment. We call the value of the line equation at the midpoint our *decision variable* ${tex`d`} as its sign decides if we increment the passive axis count or leave it alone; the above figure toggles between these two states. While we could recalculate ${tex`d`} every increment, it is more efficient if we update the value as we walk the line. First, start with the midpoint distance we calculated after we set ${tex`\left(i,j\right)`}, i.e. the midpoint between ${tex`\left(i+1,j\right)`} and ${tex`\left(i+1,j+1\right)`}: ${tex.block`d=f(M(i,j))=-\Delta j\left(i+1\right) + \Delta i\left(j+\frac{1}{2}\right) + C`} After using this for our decision, we need to update the decision variable based upon the new midpoint; it is now ${tex`f(M(i+1,j))`} or ${tex`f(M(i+1,j+1))`} depending on which pixel was chosen. To derive the update values, we subtract the original decision variable from these updated terms as appropriate: ${tex.block`\begin{aligned} \left(i+1, j\right)\text{ chosen: } &\Delta d=f\left(M\left(i+1,j\right)\right) - f\left(M\left(i,j\right)\right) &=&-\Delta j \\ \left(i+1, j+1\right)\text{ chosen: } &\Delta d=f\left(M\left(i+1,j+1\right)\right) - f\left(M\left(i,j\right)\right) &=&-\Delta j +\Delta i \end{aligned}`} The final version of the Midpoint Algorithm makes it an integer algorithm to avoid floating point uncertainty and for speed. The initial decision variable at the starting point is a float due to the half pixel offset. We can rid ourselves of it by noting that multiplying by a positive number does not change our decision variable's sign (and thus how we use it). We can thus multiply our initial decision variable by two and collect terms to get: ${tex.block`d' = -2\Delta j + \Delta i`} We will have to modify the update values to work with this new ${tex`d'`} as well: ${tex.block` \begin{aligned} \left(i+1, j\right)\text{ chosen: } &\Delta d'& =&-2\Delta j\\ \left(i+1, j+1\right)\text{ chosen: } & \Delta d'&=&-2\Delta j +2\Delta i \end{aligned}`} For steep slopes (where ${tex`j`} is the driving axis), we can switch the roles of ${tex`i,j`} above; for negative slopes, we need only change our ${tex`i,j`} increments; the decision variables are unchanged if we use their absolute value.`36:Tcc1,viewof mid_grid = { const mid = raster_grid({size: grid_size, grid_width: ewidth, grid_height: height, mousedown: () => null}); mid.append(html`

DDA & Midpoint Algorithm Comparisons. Drag line & ends to generate new points.

`); let svg = mid.getElementsByTagName("svg")[0]; svg.style.margin = "auto"; svg.style.display = "block"; svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "mid" + (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() { mutable mid_points.splice(0, mutable mid_points.length); mutable mid_points = mutable mid_points; svg.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) 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; } return mid; }37:Ta55,{ const pixels = new Uint8ClampedArray(4 * 4); pixels.set([70,130,180,255], 0); // steelblue const above_below = raster_grid({value: pixels, numberH: 2, grid_width: 160, grid_height: 160, mousedown: () => null}); let svg = d3.select(above_below).select("svg"); svg.style("margin", "auto"); svg.style("display", "block"); svg.selectAll(".raster_grid").style("transition", "fill .4s ease").attr("id", ([i,j]) => "above_below" + (2*j+i)); svg.append("text") .attr("x", 8).attr("y", 110) .text("(i,j)"); svg.append("circle") .attr("stroke", "black") .attr("fill", "transparent") .attr("r", 4) .attr("cx", 120).attr("cy", 80); svg.append("text") .attr("x", 128).attr("y", 78) .text("M"); const line = svg.append("line") .attr("stroke", "black") .attr("stroke-width", 3) .attr("x1", 0) .attr("y1", 140); const q = svg.append("line") .attr("stroke", "rgb(44,160,44)") .attr("stroke-width", 3) .attr("stroke-dasharray", "1%") .attr("x1", 120) .attr("y1", 40); svg.append("circle") .attr("stroke", "none") .attr("fill", "steelblue") .attr("r", 3) .attr("cx", 120) .attr("cy", 40); const r = svg.append("line") .attr("stroke", "rgb(214,39,40)") .attr("stroke-width", 3) .attr("stroke-dasharray", "1%") .attr("x1", 120) .attr("y1", 120); svg.append("circle") .attr("stroke", "none") .attr("fill", "steelblue") .attr("r", 3) .attr("cx", 120) .attr("cy", 120); const rect1 = svg.select("rect#above_below1"); const rect3 = svg.select("rect#above_below3"); const fig = d3.select(above_below).append("figcaption") .style("margin", "auto") .style("text-align", "center"); let low = true; while (true) { if(low) { rect1.attr("fill", "lightsteelblue"); rect3.attr("fill", "transparent"); line.attr("x2", 160).attr("y2", 80); r.attr("x2", 120).attr("y2", 95); q.attr("x2", 120).attr("y2", 95); fig.html('r < q; do not increment j.'); low = !low; } else { rect1.attr("fill", "transparent"); rect3.attr("fill", "lightsteelblue"); line.attr("x2", 160).attr("y2", 40); r.attr("x2", 120).attr("y2", 65); q.attr("x2", 120).attr("y2", 65); fig.html(`r > q; increment j.`); low = !low; } yield Promises.tick(2000).then(() => above_below); } }38:T585,{ d3.select(viewof dda_grid).selectAll(".endpoint").each(function process() { const target = {"start": start_grid, "end": end_grid}[this.classList[1]]; d3.select(this).attr("cx", target[0]).attr("cy", target[1]); }); d3.select(viewof dda_grid).selectAll(".endbox").each(function process() { const target = {"start": start_grid, "end": end_grid}[this.classList[1]]; d3.select(this).attr("x", grid_size*Math.trunc(target[0]/grid_size)).attr("y", grid_size*Math.trunc(target[1]/grid_size)); }); d3.select(viewof dda_grid).select(".line") .attr("x1", start_grid[0]) .attr("y1", start_grid[1]) .attr("x2", end_grid[0]) .attr("y2", end_grid[1]); d3.select(viewof mid_grid).selectAll(".endpoint").each(function process() { const target = {"start": start_grid, "end": end_grid}[this.classList[1]]; d3.select(this).attr("cx", target[0]).attr("cy", target[1]); }); d3.select(viewof mid_grid).selectAll(".endbox").each(function process() { const target = {"start": start_grid, "end": end_grid}[this.classList[1]]; d3.select(this).attr("x", grid_size*Math.trunc(target[0]/grid_size)).attr("y", grid_size*Math.trunc(target[1]/grid_size)); }); d3.select(viewof mid_grid).select(".line") .attr("x1", start_grid[0]) .attr("y1", start_grid[1]) .attr("x2", end_grid[0]) .attr("y2", end_grid[1]); return md`Update the lines`; }39:[] 2f:{"id":"eac1bd3c82281cb2","slug":"drawing-lines","title":"Drawing Lines","thumbnail":"d5c3b01c0893e470c36b94422e96e3afb2aceb8dc49bfcc6dc485c7272d31b2c","access_level":"public","create_time":"$D2018-09-13T03:17:07.448Z","update_time":"$D2021-09-09T14:29:31.607Z","view_time":null,"first_public_time":"$D2018-09-21T16:21:33.969Z","fork":false,"stars":6,"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":679,"publish_version":null,"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":8,"collection":{"id":"fa97e7eb1e9d2163","slug":"computer-graphics","title":"Computer Graphics","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"type":"notebook","body":{"title":"Drawing Lines","cells":[{"id":0,"value":"md`# Drawing Lines\n\n\n\nAfter points, *lines* are the next simplex in complexity for Computer Graphics. For non-antialiased lines, there are two historical approaches: the Digitial Differential Analyzer (DDA) and the Midpoint Algorithm. Each algorithm answers the same fundamental question: If I just filled in raster pixel ${tex`\\left(i, j\\right)`}, which of the two candidate pixels do I fill in next?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":441,"value":"md`*Notes on conventions:* ${tex`\\left(x,y\\right)`} are floating point coordinates while ${tex`\\left(i,j\\right)`} are integral raster pixel locations. As there are no valid fractional raster locations, any floating point pixel coordinates are always rounded before rasterization. As is standard in Computer Graphics, horizontal coordinates increase to the right and vertical increases up.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":26,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":144,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":152,"value":"mutable dda_points = dda(mutable start, mutable end)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":109,"value":"function dda([x0, y0], [x1, y1]) {\n // Round to determine pixel location\n const pixel = (x, y) => [Math.round(x), Math.round(y)];\n \n // Differences and step value\n let [dx, dy] = [x1 - x0, y1 - y0];\n let step = 0;\n if(Math.abs(dx) > Math.abs(dy))\n step = Math.abs(dx);\n else\n step = Math.abs(dy);\n \n // Find slope and stepping direction\n dx /= step; dy /= step;\n \n // Generate\n let [x, y] = [x0, y0];\n const pixels = [pixel(x, y)];\n for(let i = 0; i < step; ++i)\n {\n x += dx; y += dy;\n pixels.push(pixel(x,y));\n } \n return pixels;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":338,"value":"md`Note that by dividing by the absolute value of the step size corrects for both negative slopes and cases where the second end point has lesser values than the first end point. Also note that this algorithm requires floating point arithmetic as specified; the Midpoint Algorithm requires only integer arithmetic.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":306,"value":"md`## Midpoint Algorithm\n\nThe DDA approach determines the next pixel to rasterize directly via calculation—we repeatedly add the slope to the previous point to solve for the next. The Midpoint Algorithm, in contrast, finds this point indirectly by instead asking which of the two candidate points we must fill. We answer this via an implicit line equation:\n\n${tex.block`Ax + By + C = 0`}\n\nwhere ${tex`A=y_0-y_1=-\\Delta y, B=x_1-x_0=\\Delta x, C=x_0y_1 - x_1y_0`}. \\[[1](#footnote-implicit \"Footnote: Implicit Lines\")\\]. Any point on the line satisfies this equation. Points off the line, however, return a positive or negative value that is proportional to the *signed distance* of that point from the line. This signed distance will be used to determine our next raster pixel.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":366,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":393,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":476,"value":"function midpoint([x0, y0], [x1, y1]) \n{\n // Round to determine pixel location\n const pixel = (x,y) => [Math.round(x), Math.round(y)]\n let [i0, j0] = pixel(x0,y0);\n let [i1, j1] = pixel(x1,y1);\n let [i,j] = [i0,j0];\n\n // Steps\n let stepi = i1 > i0 ? 1 : i1 < i0? -1 : 0;\n let stepj = j1 > j0 ? 1 : j1 < j0? -1 : 0;\n\n // Determine error \n let di = Math.abs(i1 - i0);\n let dj = Math.abs(j1 - j0);\n \n // Find line orientation\n let steep = false;\n if(dj > di)\n {\n steep = true;\n [i,j] = [j,i];\n [di,dj] = [dj,di];\n [stepi,stepj] = [stepj,stepi];\n }\n let d = di - (2 * dj);\n\n // Rasterize\n const pixels = [];\n const push_pixel = (i,j,steep) => steep? pixels.push([j,i]) : pixels.push([i,j]);\n push_pixel(i,j,steep);\n for(let count = 1; count <= di; ++count)\n {\n // Update midpoint/error term\n if(d <= 0)\n {\n j += stepj;\n d += 2 * di;\n }\n i += stepi;\n d -= 2 * dj;\n push_pixel(i,j,steep);\n }\n \n return pixels;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":455,"value":"md`Other then at points where the line passes through the midpoint, the DDA and the Midpoint algorithms generate the same points. Either pixel is valid at these intersections so niether pixel is \"wrong\". The following figure compares the two approaches by cycling between the two sets of points:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":464,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":466,"value":"mutable mid_points = []","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":344,"value":"md`### Bresenham's Algorithm\n\nThough I discuss the Midpoint Algorithm above, historically it was developed after [*Bresenham's Algorithm.*](https://pdfs.semanticscholar.org/c443/c0b5f74f75d87193bc373cdc5b0b61cf28fd.pdf \"Algorithm for computer control of a digital plotter\") Bresenham's approach does not look at the midpoint; instead, its decision variable is a measure of the difference of the lengths of the bisected segments ${tex`\\textcolor{#d62728}{r}, \\textcolor{#2ca02c}{q}`} of the line between the two candidate points ${tex`\\left(i+1,j\\right), \\left(i+1, j+1\\right)`}:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":489,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":351,"value":"md`Bresenham's Algorithm increases the passive axis term when ${tex`\\textcolor{#d62728}{r}>\\textcolor{#2ca02c}{q}`}; this occurs when ${tex`\\textcolor{#d62728}{r}`} passes through ${tex`M`} and the line is above the midpoint. Thus, the comparisons are the same and the algorithms give the same results.\n\n## Summary\n\nTo rasterize lines directly, we have the choice of a direct, floating point method or an indirect but computationally precise and efficient method. Most line drawing algorithms and modifications (such as antialiasing) are based upon the Midpoint/Bresenham family of algorithms historically. However, both of these algorithms are only suited for lines with limited styling in serial computation environments (e.g., CPUs). [Other approaches](https://mattdesl.svbtle.com/drawing-lines-is-hard \"Svbtle/Matt Deslauriers: Drawing Lines is Hard\") that better account for parallelism and add styling are better for GPU applications.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":357,"value":"footnote_implicit = md`## Footnotes\n\n\\[1\\] There are different formulations of the ${tex`A, B, C`} constants which are all valid; ours are chosen so that the positive signed distance to the line is along the gradient in the positive half plane (towards where ${tex`x,y>0`}). For example, in triangle rasterization, we can choose the constants so that the positive direction is always in the interior of the triangle.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":566,"value":"md`## Appendix: Implementation\nThe implementation for the DDA algorithm was adapted from [Wikipedia's](https://en.wikipedia.org/wiki/Digital_differential_analyzer_%28graphics_algorithm%29 \"Wikipedia: Digital differential analyzer (Computer Graphics)\"). The Midpoint algorithm is from ancient source I had, likely with some reference to [Foley and van Dam](https://en.wikipedia.org/wiki/Computer_Graphics:_Principles_and_Practice \"Computer Graphics: Principles and Practice, 2nd ed.\"), but I cannot be sure. For an efficient implementation of Bresenham's with extensions, see [Alois Zingl's *The Beauty of Bresenham's Algorithm*](http://members.chello.at/~easyfilter/bresenham.html). [Kelly van Evert](https://kelleyvanevert.nl/ \"Kelly van Evert's page\") assisted debugging a nasty hang the original had.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":14,"value":"import {raster_grid} from \"@infowantstobeseen/raster-grid\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":50,"value":"d3 = require(\"d3-selection@1.4\", \"d3-drag@1.2\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":137,"value":"ewidth = Math.min(width, 400)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":140,"value":"height = ewidth","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":319,"value":"grid_count = 20","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":142,"value":"grid_size = Math.min(ewidth, height) / grid_count","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":132,"value":"mutable start = [0,0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":134,"value":"mutable end = [19,19]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":210,"value":"mutable start_grid = [ grid_size / 2, height - grid_size / 2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":213,"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":277,"value":"{\n d3.select(viewof dda_grid).selectAll(\".raster_grid\").style(\"fill\",\"none\");\n d3.select(viewof mid_grid).selectAll(\".raster_grid\").style(\"fill\",\"none\");\n \n mutable dda_points.splice(0, mutable dda_points.length, ...dda(start, end));\n mutable dda_points = mutable dda_points;\n mutable mid_points.splice(0, mutable mid_points.length, ...midpoint(start, end));\n mutable mid_points = mutable mid_points;\n\n for(const pt of mutable dda_points) {\n const dda_rect = d3.select(viewof dda_grid).select(\"rect#dda\" + (grid_count * pt[1] + pt[0]));\n dda_rect.style(\"fill\", \"coral\"); \n }\n\n for(const pt of mutable mid_points) {\n const mid_rect = d3.select(viewof mid_grid).select(\"rect#mid\" + (grid_count * pt[1] + pt[0]));\n mid_rect.style(\"fill\", \"lightsteelblue\"); \n }\n \n return md`Update the points`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":597,"value":"{\n // Update forever; make sure to kill previous loops when update occurs. Courtesy Kelley van Evert\n while(true)\n {\n \n let num_pts = dda_points.length;\n for(const pt of mutable dda_points) {\n const mid_rect = d3.select(viewof mid_grid).select(\"rect#mid\" + (grid_count * pt[1] + pt[0]));\n mid_rect.style(\"fill\", num_pts == dda_points.length ? \"coral\" : \"none\"); \n if(num_pts != dda_points.length) return; // Terminate on change\n yield Promises.tick(100).then(() => md`Update animation`);\n }\n for(const pt of mutable mid_points) {\n const mid_rect = d3.select(viewof mid_grid).select(\"rect#mid\" + (grid_count * pt[1] + pt[0]));\n mid_rect.style(\"fill\", \"lightsteelblue\"); \n yield Promises.tick(100).then(() => md`Update animation`);\n if(num_pts != dda_points.length) return; // Terminate on change\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":197,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 30:"$2f:body"