#+title: Line drawing on a grid
#+options: toc:nil
#+property: header-args:js  :tangle "_line-drawing.js"
#+date: <2014-12-01>

#+begin_comment
I set a global :tangle filename and then suppress it with
:tangle no. I can't use :tangle yes because that will override the filename.
#+end_comment

Graphics libraries provide line-drawing routines, sometimes with [[https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm][antialiasing]] and variable width. On a grid map, line drawing is useful for for visibility, the path of an arrow/bullet, and enemy AI. I sometimes see people adapting the Bresenham line drawing algorithm to draw lines on a grid (especially for roguelike games), but I prefer a /much/ simpler algorithms that runs just as fast. I'll show the algorithms I use.

This is the code. The first section will explain how it works and the helper functions =round_point= and =lerp_point= and =diagonal_distance= (these are all short), and then the other sections will describe variants of the algorithm.

#+begin_src js :tangle no
function line(p0, p1) {
    let points = [];
    let N = diagonal_distance(p0, p1);
    for (let step = 0; step <= N; step++) {
        let t = N === 0? 0.0 : step / N;
        points.push(round_point(lerp_point(p0, p1, t)));
    }
    return points;
}
#+end_src

* Linear interpolation
:PROPERTIES:
:CUSTOM_ID: interpolation
:END:

This demo shows what grid locations should be marked if you're drawing a line between two points. *Try moving the endpoints around*.

#+begin_export html
<div id="line-top"/>
#+end_export

I find the easiest way to find these points is to use /linear interpolation/. Let's see how that works.

** Interpolating numbers
   :PROPERTIES:
   :CUSTOM_ID: interpolation-numbers
   :END:

Here's a simple (Javascript) helper function I'll use:

#+begin_src js :exports code
function lerp(start, end, t) {
    return start * (1.0 - t) + end * t;
}
#+end_src

@@html:<u>L</u>inear int<u>erp</u>olation@@ (“lerp”) gives you a number between two other numbers. When =t= = 0.0 you get the start point; when =t= = 1.0 you get the end point. *Try setting t*, the third parameter to lerp():

#+begin_export html
<pre>
lerp(  0,   1, <span data-name="t0" data-format=".2f"/>) = <span id="lerp1"/>
lerp(  0, 100, <span data-name="t0" data-format=".2f"/>) = <span id="lerp2"/>
lerp(  3,   5, <span data-name="t0" data-format=".2f"/>) = <span id="lerp3"/>
lerp(  5,   3, <span data-name="t0" data-format=".2f"/>) = <span id="lerp4"/>
</pre>
#+end_export

#+begin_src js :exports none
var t0 = make_scrubbable('t0', 0.3, [0.0, 1.0], 0.01);
t0.trigger(function() {
    function set(id, fmt, lo, hi) { d3.select(id).text(d3.format(fmt)(lerp(lo, hi, t0.value))); }
    set("#lerp1", ".2f", 0, 1);
    set("#lerp2", ".0f", 0, 100);
    set("#lerp3", ".1f", 3, 5);
    set("#lerp4", ".1f", 5, 3);
});
#+end_src

** Interpolating points
   :PROPERTIES:
   :CUSTOM_ID: interpolation-points
   :END:

We can extend the idea of interpolation to work on points, by interpolating both the x and y coordinates. *Try varying t* = @@html:<span data-name="line-interpolation-t" data-format=".2f"/>@@:

#+begin_export html
<div id="line-interpolation"/>
#+end_export

Here's the code to find point x,y between point p_{0} = (x_{0},y_{0}) and point p_{1} = (x_{1},y_{1}):

#+begin_src js
function lerp_point(p0, p1, t) {
    return new Point(lerp(p0.x, p1.x, t),
                     lerp(p0.y, p1.y, t));
}
#+end_src

Let's divide the line into @@html:<span data-name="line-midpoints-N" data-format=".0f"/>@@ equal line segments:

#+begin_export html
<div id="line-midpoints"/>
#+end_export

Here's the code to find those points:

#+begin_src js :exports none
function Point(x, y) { this.x = x; this.y = y; }
#+end_src

#+begin_src js :exports none
// This will make it easier to use with d3+svg
Point.prototype.toString = function() { return this.x + "," + this.y; };
#+end_src

#+begin_src js :tangle no
let points = [];
for (let step = 0; step <= N; step++) {
    let t = step / N;
    points.push(lerp_point(p0, p1, t));
}
#+end_src

Variant: we can start ~let step = 1~, and stop at ~step < N~ if we want to exclude the two endpoints. Variant: we can replace ~step <= N~ with another condition, such as stopping at a wall or at the edge of the map.

** Snap to grid
   :PROPERTIES:
   :CUSTOM_ID: snap-to-grid
   :END:

Next we need to figure out which /grid squares/ those points are in. We can round x and y to the nearest integer to find the grid tile:

#+begin_export html
<div id="line-rounding"/>
#+end_export

We also need to decide how many points to include. Too few and the line has holes. Too many and the line has overdraw. How many do we need? The right number is the /diagonal distance/ between the endpoints, which in this case is @@html:<span class="line-rounding-distance"/>@@.

*Adjust N* = @@html:<span data-name="line-rounding-N" data-format=".0f"/>@@ to @@html:<span class="line-rounding-distance"/>@@ to see how the line fills in. @@html:<span class="line-rounding-N-is-correct" style="color:green"/>@@

That's it!

1. Set N to the diagonal distance between the start and end point.
2. Pick N+1 interpolation points, evenly spaced.
3. Round those points to the nearest grid tile.

Here's the final code:

#+begin_src js
function line(p0, p1) {
    let points = [];
    let N = diagonal_distance(p0, p1);
    for (let step = 0; step <= N; step++) {
        let t = N === 0? 0.0 : step / N;
        points.push(round_point(lerp_point(p0, p1, t)));
    }
    return points;
}
#+end_src

This is the simplest line drawing algorithm I know of. Here are the helper functions, which you may have already implemented:

#+begin_src js
function diagonal_distance(p0, p1) {
    let dx = p1.x - p0.x, dy = p1.y - p0.y;
    return Math.max(Math.abs(dx), Math.abs(dy));
}

function round_point(p) {
    return new Point(Math.round(p.x), Math.round(p.y));
}

function lerp_point(p0, p1, t) {
    return new Point(lerp(p0.x, p1.x, t),
                     lerp(p0.y, p1.y, t));
}

function lerp(start, end, t) {
    return start * (1.0 - t) + t * end;
}
#+end_src

#+begin_src js :exports none
// You should use the line() function presented in the article.
// However, for the interactive illustrations I want to show the
// unrounded points, and I also want the reader to choose N, so this
// is a variant of the line() function.
function line_N_unrounded(p0, p1, N) {
    let points = [];
    for (let step = 0; step <= N; step++) {
        let t = N === 0? 0.0 : step / N; // special case: N=0 when p0==p1
        points.push(lerp_point(p0, p1, t));
    }
    return points;
}
#+end_src

#+begin_src js :exports none
// Make a line-drawing diagram
//
// #$id will get a new <svg> element
// *[data-name=$id-N] will become draggable N
// *[data-name=$id-t] will become draggable t
//
// Components:
// * Grid (g.grid rect)
// * Rasterized line drawn on grid (g.grid rect.line)
// * Draggable endpoints (.endpoints .draggable)
// * Straight line (.endpoints line)
// * Interpolation point controlled by $t
// * Multiple labeled interpolation points controlled by $N (.midpoints circle, .midpoints text)
//
// Select features by setting the CSS rules
function Diagram(id) {
    this.scale = 20;
    this.N = make_scrubbable(id+"-N", 5, [1, 30], 1);
    this.t = make_scrubbable(id+"-t", 0.3, [0.0, 1.0], 0.01);
    this.endpoints = [new Point(2, 2), new Point(20, 8)];
    this.distance = 0;
    this.redrawers = []; // list of functions

    this.svg = d3.select("#"+id).append('svg')
        .attr('viewBox', "0 0 600 200")
        .append('g')
        .attr('transform', "translate(0.5, 0.5) scale(" + this.scale + ") translate(0.5, 0.5)");

    let g_grid = this.svg.append('g')
        .attr('class', "grid");
    let coords = [];
    for (let x = 0; x < 30; x++) {
        for (let y = 0; y < 10; y++) {
            coords.push(new Point(x, y));
        }
    }
    g_grid.selectAll("rect").data(coords).enter()
        .append('rect')
        .attr('transform', function(d) { return "translate(" + d + ") translate(-0.5, -0.5)"; })
        .attr('width', 1-1/this.scale)
        .attr('height', 1-1/this.scale);

    this.redraw = function() {
        this.distance = diagonal_distance(this.endpoints[0], this.endpoints[1]);
        this.find_line();
        d3.selectAll("." + id + "-distance").text(this.distance);
        this.redrawers.forEach(function(f) { f.call(this); }.bind(this));

        return this;
    };

    this.find_line = function() {
        let N = this.N? this.N.value : this.distance;
        this.points = line_N_unrounded(this.endpoints[0], this.endpoints[1], N);
    };

    this.N.trigger(this.redraw.bind(this));
    this.t.trigger(this.redraw.bind(this));
}


Diagram.prototype.automatic_N = function() {
    this.N = null;
    return this;
}


Diagram.prototype.add_line_draw = function() {
    let g = this.svg.append('g')
        .attr('class', "linedraw");

    this.redrawers.push(function() {
        let sel = g.selectAll("rect").data(this.points);
        sel.exit().remove();
        sel.enter().append('rect')
            .attr('width', 1-1/this.scale)
            .attr('height', 1-1/this.scale);
        sel.attr('transform', function(d) { return "translate(" + round_point(d) + ") translate(-0.5, -0.5)"; });
    });
    return this;
}


Diagram.prototype.add_track = function() {
    let line = this.svg.append('line')
        .attr('class', "track");

    this.redrawers.push(function() {
        line
            .attr('x1', this.endpoints[0].x)
            .attr('x2', this.endpoints[1].x)
            .attr('y1', this.endpoints[0].y)
            .attr('y2', this.endpoints[1].y);
    });
    return this;
}


Diagram.prototype.add_midpoints = function() {
    let g = this.svg.append('g')
        .attr('class', "midpoints");

    this.redrawers.push(function() {
        // Mark the line midpoints as small circles
        let sel = g.selectAll("circle").data(this.points);
        sel.exit().remove()
        sel.enter().append('circle').attr('r', 2.5/this.scale);
        sel.attr('transform', function(d) { return "translate(" + d + ")"; });

        let offset = Math.abs(this.endpoints[1].y - this.endpoints[0].y) > Math.abs(this.endpoints[1].x - this.endpoints[0].x)? [0.8, 0] : [0, -0.8];
        sel = g.selectAll("text").data(this.points);
        sel.exit().remove();
        sel.enter().append('text')
            .attr('text-anchor', "middle")
            .text(function(d,i) { return i; });
        sel.attr('transform', function(d) { return "translate(" + d + ") translate(" + offset + ") translate(0, 0.25)"; });
    });
    return this;
}


// Endpoints will be large invisible circles with a small visible circle. Draggable.
Diagram.prototype.add_endpoints = function() {
    let g = this.svg.append('g')
        .attr('class', "endpoints");
    let sel = g.selectAll("g").data(this.endpoints)
        .enter().append('g');
    sel.append('circle')
        .attr('class', "invisible")
        .attr('r', 0.9);
    sel.append('circle')
        .attr('class', "visible")
        .attr('r', 0.3);
    this.on_drag = function(endpoint) {
        d3.event.sourceEvent.preventDefault(); // stop scrolling on touch devices
        let x = Math.round(d3.event.x), y = Math.round(d3.event.y);
        if (0 <= x && x < 30 && 0 <= y && y < 10) {
            endpoint.x = x;
            endpoint.y = y;
            this.redraw();
        }
    }
    let drag = d3.behavior.drag()
        .on('drag', this.on_drag.bind(this))
        .on('dragstart', function() {
            d3.event.sourceEvent.preventDefault(); // stop scrolling on touch devices
            d3.select(this).classed('dragging', true);
        })
        .on('dragend', function() { d3.select(this).classed('dragging', false); })
        .call(sel);

    this.redrawers.push(function() {
        g.selectAll("g")
            .attr('transform', function(d) { return "translate(" + d + ")"; });
    });
    return this;
}


// Calculate an interpolation point based on t
Diagram.prototype.add_interpolation = function() {
    let g = this.svg.append('g')
        .attr('class', "interpolation");
    g.append('circle')
        .attr('r', 4/this.scale);

    this.redrawers.push(function() {
        g.select("circle")
            .attr('transform', "translate(" + lerp_point(this.endpoints[0], this.endpoints[1], this.t.value) + ")");
    });
    return this;
}

let diagram_top = new Diagram('line-top')
    .automatic_N()
    .add_line_draw()
    .add_endpoints()
    .redraw();

let diagram_interpolation = new Diagram('line-interpolation')
    .add_track()
    .add_endpoints()
    .add_interpolation()
    .redraw();

let diagram_midpoints = new Diagram('line-midpoints')
    .add_track()
    .add_midpoints()
    .add_endpoints()
    .redraw();

let diagram_rounding = new Diagram('line-rounding')
    .add_track()
    .add_line_draw()
    .add_midpoints()
    .add_endpoints()
    .redraw();
diagram_rounding.redrawers.push(function() {
    d3.selectAll(".line-rounding-N-is-correct").text(diagram_rounding.N.value === diagram_rounding.distance? "\u2714" : "");
});
#+end_src

** Interpolating other types
   :PROPERTIES:
   :CUSTOM_ID: interpolation-other
   :END:

I defined the =lerp= function to interpolate between two /numbers/, and then I defined =lerp_point= to work on two /points/. How about other types /T/? We need these operations to define interpolation:

- addition :: b = a + d where a: /T/, b: /T/, and d: /ΔT/. For points, b.x = a.x + d.x; b.y = a.y + d.y
- subtraction :: d = a - b where a: /T/, b: /T/, and d: /ΔT/. For points, d.x = a.x - b.x; d.y = a.y - b.y
- multiplication by scalar :: e = k * d where d: /ΔT/, e: /ΔT/, and k: /number/. For points, e.x = k * d.x; e.y = k * d.y

We can do interpolation on any [[https://en.wikipedia.org/wiki/Vector_space][vector space]]. /T/ can be a number, a 2d point, a 3d point, an angle, a time, a color, or other things too. My [[https://www.redblobgames.com/grids/hexagons/#line-drawing][guide to hexagonal grids]] uses interpolation to draw lines on a hex grid. Note that /T/ and /ΔT/ may be the same type, but sometimes they are different. For example, /T/ may be a timestamp and /ΔT/ may be a time difference, or /T/ may be an orientation and /ΔT/ may be a rotation. When /T/ and /ΔT/ are the same type, d = a - b can be implemented as d = a + (-1 * b).

** Aesthetics
   :PROPERTIES:
   :CUSTOM_ID: interpolation-aesthetics
   :END:

Linear interpolation is calculating a position and then rounding it. What happens when the value is exactly 0.5? [[https://en.wikipedia.org/wiki/Rounding#Tie-breaking][Rounding rules vary]]. That, and floating point precision, make linear interpolation not always choose points in a way that preserves consistency with rotation, reversing, and other symmetry.

I think the thing to do would be to “nudge” the initial points by epsilon. However I haven't explored this with square grids. I've used it with hex grids.

** Code optimization
   :PROPERTIES:
   :CUSTOM_ID: optimization
   :END:

You can optimize the regular line drawing algorithm with these steps; it will turn into the [[https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)][DDA algorithm]]:

- Inlining function calls :: Your compiler will likely do this but you may spot additional optimization opportunities by doing this yourself first.
- Unrolling lerp :: Instead of calculating t each time through the loop, and then x = (b.x-a.x)*t (a subtract and multiply), you can calculate Δx = (b.x-a.x)*Δt outside the loop, and then use x += Δx. Same for y. This will replace the multiplies with adds.
- Unrolling loop :: You can unroll the loop by keeping four x and y pairs, and then using t += 4*Δt. Would this allow the use of SSE instructions? I don't know.
- Separate cases :: Either Δx or Δy will be ±1. You might want to have a separate versions for each case. For diagonal lines, both will be ±1. For orthogonal lines, one or the other will be 0. If these cases are common, write a separate routine for them.
- Floating point vs fixed point :: If you profile and find Math.round() is expensive, you can switch to fixed point arithmetic, and replace rounding with bit shifting. On x86, consider using the =fist=/=fistp= instruction or maybe SSE for =cvtsd2si= (I haven't gone this far in optimization).

Before optimizing, profile and make sure linear interpolation is your bottleneck.
In my projects, it rarely is, so I haven't bothered implementing these optimizations.
Here's an example (in approximate C# syntax, to show the types) of inlining + unrolling lerp, but without applying the other optimizations:

#+begin_src csharp
List<Point> line(Point p0, Point p1) {
    List<Point> = new List<Point>();
    int dx = p1.x - p0.x;
    int dy int = p1.y - p0.y;
    int N = Math.Max(Math.Abs(dx), Math.Abs(dy));
    float divN = (N === 0)? 0.0 : 1.0 / N;
    float xstep = dx * divN;
    float ystep = dy * divN;
    float x = p0.x, y = p0.y;
    for (int step = 0; step <= N; step++, x += xstep, y += ystep) {
        points.Add(new Point(Math.Round(x), Math.Round(y));
    }
    return points;
}
#+end_src


* Grid walking
:PROPERTIES:
:CUSTOM_ID: stepping
:END:

Interpolation is simple and general but doesn't take into account properties of the grid. Another approach to line drawing is to take one step at a time. This type of movement also allows /putting walls on edges/ so that a wall could block line of sight or movement.

** Orthogonal steps
   :PROPERTIES:
   :CUSTOM_ID: orthogonal-steps
   :END:

In the above lines, we took both orthogonal steps (north, east, south, west) and diagonal steps. Step-by-step algorithms give us more flexibility. What if we only want to take orthogonal steps?

#+begin_export html
<div id="diagram-grid-movement"/>
#+end_export

#+begin_src js :exports none
let diagram_grid_movement = new Diagram('diagram-grid-movement')
    .add_track()
    .add_line_draw()
    .add_endpoints();
diagram_grid_movement.find_line = function() {
    this.points = walk_grid(this.endpoints[0], this.endpoints[1]);
};
diagram_grid_movement.redraw();
#+end_src

The strategy here is to think about the /grid edges/ being crossed, both vertical and horizontal. At every step we either cross a vertical edge (horizontal step) or cross a horizontal edge (vertical step). The way we can tell which way to go is by looking to see which of =(0.5+ix) / nx= and =(0.5+iy) / ny= is smaller. The smaller one is where we want to take the next step.

#+begin_src js
function walk_grid(p0, p1) {
    let dx = p1.x-p0.x, dy = p1.y-p0.y;
    let nx = Math.abs(dx), ny = Math.abs(dy);
    let sign_x = dx > 0? 1 : -1, sign_y = dy > 0? 1 : -1;

    let p = new Point(p0.x, p0.y);
    let points = [new Point(p.x, p.y)];
    for (let ix = 0, iy = 0; ix < nx || iy < ny;) {
        if ((0.5+ix) / nx < (0.5+iy) / ny) {
            // next step is horizontal
            p.x += sign_x;
            ix++;
        } else {
            // next step is vertical
            p.y += sign_y;
            iy++;
        }
        points.push(new Point(p.x, p.y));
    }
    return points;
}
#+end_src

To avoid the division, including a potential divide by zero, we can rewrite the comparison from =(0.5+ix) / nx < (0.5+iy) / ny= to =(0.5+ix) * ny < (0.5+iy) * nx=. Then to avoid the floating point we can rewrite that to =(1 + 2*ix) * ny < (1 + 2*iy) * nx=.

It's more work to make it symmetric. Also, sometimes you'll want more control over whether you pick a horizontal step or a vertical step, especially if the choice is close, and there's a wall in one direction but not the other.

** Supercover lines
   :PROPERTIES:
   :CUSTOM_ID: supercover
   :END:

"Supercover" lines catch all the grid squares that a line passes through. I believe (but am not sure) that it is somewhere in between regular line drawing and grid movement line drawing. Unlike grid movement line drawing, we can take a diagonal step /only/ if the line passes exactly through the corner.

This looks like the grid movement line drawing, except when the line goes through a grid corner.

#+begin_export html
<div id="diagram-supercover"/>
#+end_export

#+begin_src js :exports none
let diagram_supercover = new Diagram('diagram-supercover')
    .add_track()
    .add_line_draw()
    .add_endpoints();
diagram_supercover.find_line = function() {
    this.points = supercover_line(this.endpoints[0], this.endpoints[1]);
};
diagram_supercover.redraw();
#+end_src

Let's modify the grid movement line drawing code for this:

#+begin_src js
function supercover_line(p0, p1) {
    let dx = p1.x-p0.x, dy = p1.y-p0.y;
    let nx = Math.abs(dx), ny = Math.abs(dy);
    let sign_x = dx > 0? 1 : -1, sign_y = dy > 0? 1 : -1;

    let p = new Point(p0.x, p0.y);
    let points = [new Point(p.x, p.y)];
    for (let ix = 0, iy = 0; ix < nx || iy < ny;) {
        let decision = (1 + 2*ix) * ny - (1 + 2*iy) * nx;
        if (decision === 0) {
            // next step is diagonal
            p.x += sign_x;
            p.y += sign_y;
            ix++;
            iy++;
        } else if (decision < 0) {
            // next step is horizontal
            p.x += sign_x;
            ix++;
        } else {
            // next step is vertical
            p.y += sign_y;
            iy++;
        }
        points.push(new Point(p.x, p.y));
    }
    return points;
}
#+end_src



** Line of sight
:PROPERTIES:
:CUSTOM_ID: line-of-sight
:END:

If you allow diagonal steps, some algorithms will step through walls:

#+begin_export html
<figure>
<svg width="300" height="100">
<g class="grid" transform="scale(50)">
  <rect x="0" y="0" width="0.95" height="0.95"/>
  <rect x="1" y="0" width="0.95" height="0.95" class="wall"/>
  <rect x="2" y="0" width="0.95" height="0.95"/>
  <rect x="3" y="0" width="0.95" height="0.95"/>
  <rect x="0" y="1" width="0.95" height="0.95"/>
  <rect x="1" y="1" width="0.95" height="0.95"/>
  <rect x="2" y="1" width="0.95" height="0.95" class="wall"/>
  <rect x="3" y="1" width="0.95" height="0.95"/>
  <path d="M 0.5,1.5 l 1,0 l 1,-1 l 0.7,0 m 0.3,0 l -0.3,-0.2 l 0,0.4 l 0.3,-0.2" fill="none" stroke="black" stroke-width="0.04"/>
</g>
</svg>
</figure>
#+end_export

In this case, you can either take the diagonal step if /either/ the horizontal or vertical step is clear, or you can disallow the diagonal step unless /both/ the horizontal and vertical steps are clear.

* More reading
  :PROPERTIES:
  :CUSTOM_ID: more
  :END:

There's lots written about line drawing but I haven't researched it extensively. When drawing graphical lines, I use the graphics library. It's only on grids that I needed to find some other algorithms.

You might have read that Bresenham's Line Algorithm is the fastest way to draw lines. *Please test this yourself*. It was the fastest way many decades ago, but modern CPUs and compilers work quite differently. I've tried a few different implementations of Bresenham's Line Algorithm and it's not any faster than the code from this page. But the code here is /much/ simpler and generalizes to more than 2D lines.

#+begin_src cpp
// For use in benchmark http://www.edepot.com/linebenchmark.html
void naive(int x1,int y1,int x2, int y2, UByte clr) {
  // based on https://www.redblobgames.com/grids/line-drawing/
  int dx = abs(x2 - x1);
  int dy = abs(y2 - y1);
  int length = dx > dy? dx : dy; // diagonal_distance
  for (int i = 0; i <= length; ++i) {
      double t = double(i) / length;
      int x = x1 + int(t * (x2 - x1)); // lerp
      int y = y1 + int(t * (y2 - y1)); // lerp
      pixel(x, y, clr);
  }
}
#+end_src

- The lerp function is called [[https://learn.microsoft.com/en-us/windows/win32/direct3dhlsl/dx-graphics-hlsl-lerp][=lerp=]] in DirectX and [[https://registry.khronos.org/OpenGL-Refpages/gl4/html/mix.xhtml][=mix=]] in OpenGL and [[https://docs.unrealengine.com/5.0/en-US/API/Runtime/Core/Math/FMath/LerpStable/][=LerpStable=]] in Unreal. It works for any =t=, including =t= < 0 or =t= > 1. In contrast, Unity's [[https://docs.unity3d.com/ScriptReference/Mathf.Lerp.html][Mathf.Lerp]], C++'s [[https://en.cppreference.com/w/cpp/numeric/lerp][std::lerp]] are a /clamped lerp/, clamping =t= to be 0 ≤ =t= ≤ 1.
- In terms of math, I prefer to think of lerp as =start + t * (end-start)=, but for code, there are [[https://en.wikipedia.org/wiki/Linear_interpolation#Programming_language_support][fewer floating point numerical issues]] by writing it as =start * (1.0 - t) + t * end=. Unreal offers both, with =Lerp= being the first form and =LerpStable= being the second form. [[https://github.com/rust-lang/rust/issues/86269#issuecomment-869108301][Christopher Durham lists the properties we want from lerp]]: exact, monotonic, consistent, bounded, but neither form provides all four properties.
- If you're interpolating 3d rotations, look at the [[https://en.wikipedia.org/wiki/Slerp][slerp]] variant, which works on quaternions.
- If you want non-linear interpolation, take look at [[https://en.wikipedia.org/wiki/Smoothstep][smoothstep]] and [[http://inloop.github.io/interpolator/][others]], especially for animation.
- Roguebasin has an article [[http://www.roguebasin.com/index.php/Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds][various qualities you might want on a grid if calculating field of view or line of sight]].
- Roguebasin also has an an article about [[http://www.roguebasin.com/index.php/Digital_lines]["digital lines", representing all possible lines]] between two points.
- [[http://www.cse.yorku.ca/~amana/research/grid.pdf][A Fast Voxel Traversal Algorithm]] by Amanatides and Woo gives an extension of the step-by-step line drawing algorithm for 3D coordinates.
- [[https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm][Wu's algorithm]] for anti-aliasing might be useful for determining how much of an object is on one grid cell or another; I haven't tried this.
- [[https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams-algorithm/][This article]] looks at DDA line drawing with fixed point arithmetic. It's from 2009 though and CPUs have changed since then. Also look at [[http://www.edepot.com/algorithm.html][Extremely Fast Line Algorithm]].
- I find Bresenham's algorithm to be much longer than I'd like, but if you'd like to compare, take a look at [[http://www.phatcode.net/res/224/files/html/ch35/35-03.html][Michael Abrash's implementation]] and [[http://www.phatcode.net/res/224/files/html/ch35/35-01.html][explanation]].
- [[http://www.quiss.org/boo/][Boo]] is another line drawing algorithm which works differently than the usual ones.

#+begin_export html
<style>
svg { pointer-events: none; }
.grid rect { fill: hsl(0,10%,85%); }
.grid rect.wall { fill: hsl(30,30%,60%); }
.linedraw rect { fill: hsl(0,30%,50%); fill-opacity: 0.3; stroke: hsl(0,30%,50%); stroke-width:0.06px; }
.endpoints circle { cursor: move; touch-action: none; pointer-events: all; }
.endpoints circle.invisible { fill: none; }
.endpoints circle.visible { fill: hsl(0,50%,50%); stroke: hsl(0,100%,100%); stroke-width: 0.04px; }
.track { fill: none; stroke: hsl(0,0%,100%); stroke-opacity: 0.5; stroke-width: 0.7px; }
#diagram-supercover .track { stroke-opacity: 1.0; stroke-width: 0.1px; }
.midpoints circle { fill: hsl(0,100%,70%); stroke: hsl(0,100%,100%); stroke-width: 0.04px; }
.midpoints text { fill: black; font: 0.6px sans-serif; }
#line-rounding .midpoints text { fill: none; }
.interpolation circle { fill: hsl(0,100%,70%); stroke: hsl(0,100%,100%); stroke-width: 0.04px; }

*[data-format] { white-space: pre-wrap; font-family: "Source Code Pro", sans-serif; }

.draggable {
  cursor: col-resize;
  touch-action: pan-y;
  /* Expand the region where mouse/touch events are grabbed */
  padding: 0.5rem;
  margin: -0.5rem;
}
.draggable span {
  font-weight: bold;
  line-height: 1.8;
  background-color: #eee;
  box-shadow: 0 0 0.25em hsla(0,0%,0%,0.3);
  border-radius: 0.25em;
  padding: 0.125em 0.25em;
  transition: background-color 0.15s, box-shadow 0.15s;
}
.draggable:hover span, .dragging span {
  box-shadow: 0 0 0.25em hsla(0,50%,50%,0.5);
}
.dragging span {
  background-color: hsl(0,50%,80%);
}
</style>

<script src="/js/d3.v3.min.js"/>
<script src="_line-drawing-helper.js"/>
<script src="_line-drawing.js"/>

<x:footer>
Created December 2014
with <a href="https://orgmode.org/">Emacs Org-mode</a>, from <a href="index.org">index.org</a>,
and <a href="https://d3js.org/">D3.js</a> v3,
and a mix of Typescript and Javascript. As much as possible, the algorithms presented are used to power the page.
 &#160;
<!-- hhmts start -->Last modified: 29 Sep 2023<!-- hhmts end -->
.
  </x:footer>

#+end_export

#+begin_src sh :exports none
tsc -t es5 --out _line-drawing-helper.js ../../articles/probability/scrub-number.ts
#+end_src