Rasterising triangles with edge functions

A triangle that covers 200 pixels on a phone still has to be decided one pixel at a time: is this pixel’s centre inside it or not? A 1920 × 1080 frame asks that question more than two million times for each layer of triangles, so the test must be cheap, exact, and agreed by every triangle that touches the pixel.

Rasterisers answer it with three edge functions per triangle, the test of Juan Pineda’s 1988 paper on parallel rasterisation. You will test pixel centres with them, build a working rasteriser around them, settle the centres that fall exactly on an edge with the top-left rule, and step the tests across a row in fixed point, so that rounding never moves an edge. Every pixel count below comes from a program that runs on this page.

An edge function says which side of an edge a pixel centre is on

Take triangle A with corners a = (2.2, 1.4), b = (4.6, 10.8) and c = (14.3, 6.1), in framebuffer coordinates, where y grows down the screen. A renderer decides each pixel from a single point, its centre (x + 0.5, y + 0.5): that is point samplingpoint sampling: Deciding coverage at one point per pixel, its centre: a primitive covers the pixel when it encloses that point, however much or little of the pixel's square it overlaps., the rule WebGPU’s specification uses when multisampling is off.

The edge functionedge function: A function of a point that is 0 on the line through an edge of a triangle, positive on one side and negative on the other: a 2D cross product. Three of them, one per edge, decide whether a pixel centre is inside. of the edge from a to b, at a point p, is the 2D cross product that the vectors lesson built, with its operands in the order Pineda wrote it:

In words: E is 0 on the line through a and b, positive on one side and negative on the other, and it grows in proportion to the distance from the line. At the centre (6.5, 5.5), E_ab = (4.3)(9.4) − (4.1)(2.4) = 30.58. When the corners run counter-clockwise on screen, as A’s do, the inside of the triangle is the positive side of all three edges, so a centre is inside when E_bc, E_ca and E_ab are all positive. Look at the figure: each edge has a + side facing the triangle and a − side facing away, and the filled dots are the centres on the + side of all three.

The three values have a property worth checking by hand: at any point they add up to the same number, 102.46 for triangle A, which is twice its area. At (6.5, 5.5) the values are 42.48, 29.40 and 30.58; at a point far outside they change, but their sum does not.

Dividing an edge value by the edge’s length gives the distance from the edge: the centre (2.5, 2.5) has E_ab = 0.18, and with edge ab 9.70 long it is inside by less than 0.02 pixel.

Three tests over a bounding box make a rasteriser

A complete rasteriser wraps the three tests in a short loop. It snaps the corners to a grid of 1/256 pixel, so that every later number is a whole number. It checks the winding: E of corner c against edge ab is twice the signed area, positive when the corners run counter-clockwise, and when it is negative the loop swaps two corners. Then it tests only the centres inside the triangle’s bounding boxbounding box: The smallest rectangle, with sides along the axes, that holds a shape. A rasteriser tests only the pixel centres inside its triangle's box, clamped to the target., clamped to the target. Step through the loop on triangle A, from the snapped corners to the last test:

The program is that loop, with a tie rule for centres exactly on an edge that the next section explains. It rasterises four triangles on a 16 × 12 target and prints each mask:

// A triangle rasteriser built on edge functions. Each vertex is snapped to 1/256 of a pixel (8 sub-pixel bits),
// the triangle is turned to run counter-clockwise on screen, and every pixel centre (x + 1/2, y + 1/2) of its
// bounding box is tested against the three edges. A centre exactly on an edge counts only for a top or a left edge.
const SUB = 256;
const W = 16;
const H = 12;

const snap = ([x, y]) => [Math.round(x * SUB), Math.round(y * SUB)];

// E(a, b, p) = (p.x - a.x)(b.y - a.y) - (p.y - a.y)(b.x - a.x). With y pointing down the screen, it is positive
// for points inside a triangle whose corners run counter-clockwise on screen, 0 on the edge's line.
const edge = (a, b, p) => (p[0] - a[0]) * (b[1] - a[1]) - (p[1] - a[1]) * (b[0] - a[0]);

// For a counter-clockwise triangle a left edge runs down the screen, and a top edge is horizontal, running left.
const topLeft = (a, b) => b[1] > a[1] || (b[1] === a[1] && b[0] < a[0]);

function rasterize(corners) {
  let [a, b, c] = corners.map(snap);
  const area2 = edge(a, b, c); // twice the signed area, in (1/256 pixel) squared
  if (area2 < 0) [b, c] = [c, b]; // clockwise on screen: swap two corners
  const xs = [a[0], b[0], c[0]];
  const ys = [a[1], b[1], c[1]];
  const x0 = Math.max(0, Math.ceil((Math.min(...xs) - SUB / 2) / SUB));
  const x1 = Math.min(W - 1, Math.floor((Math.max(...xs) - SUB / 2) / SUB));
  const y0 = Math.max(0, Math.ceil((Math.min(...ys) - SUB / 2) / SUB));
  const y1 = Math.min(H - 1, Math.floor((Math.max(...ys) - SUB / 2) / SUB));
  const edges = [
    [b, c],
    [c, a],
    [a, b],
  ];
  const rows = Array.from({ length: H }, () => Array(W).fill('.'));
  let tested = 0;
  let covered = 0;
  let ties = 0;
  let tiesKept = 0;
  if (area2 !== 0) {
    for (let y = y0; y <= y1; y++) {
      for (let x = x0; x <= x1; x++) {
        const p = [x * SUB + SUB / 2, y * SUB + SUB / 2];
        tested++;
        let inside = true;
        let onEdge = false;
        for (const [e0, e1] of edges) {
          const w = edge(e0, e1, p);
          if (w === 0) onEdge = true;
          if (w < 0 || (w === 0 && !topLeft(e0, e1))) inside = false;
        }
        if (onEdge) ties++;
        if (inside) {
          covered++;
          if (onEdge) tiesKept++;
        }
        rows[y][x] = inside ? (onEdge ? 'o' : '#') : onEdge ? '-' : rows[y][x];
      }
    }
  }
  return { area: Math.abs(area2) / (2 * SUB * SUB), clockwise: area2 < 0, box: [x0, x1, y0, y1], tested, covered, ties, tiesKept, rows };
}

const TRIANGLES = [
  ['A', [[2.2, 1.4], [4.6, 10.8], [14.3, 6.1]]],
  ['B, A listed clockwise', [[2.2, 1.4], [14.3, 6.1], [4.6, 10.8]]],
  ['C, corners on pixel centres', [[12.5, 2.5], [3.5, 2.5], [7.5, 9.5]]],
  ['D, a sliver', [[0.6, 10.2], [15.4, 8.3], [15.4, 8.9]]],
];

for (const [name, corners] of TRIANGLES) {
  const r = rasterize(corners);
  const [x0, x1, y0, y1] = r.box;
  console.log(`Triangle ${name}: ${corners.map((p) => `(${p.join(', ')})`).join(' ')}`);
  console.log(`  ${r.clockwise ? 'clockwise on screen, two corners swapped' : 'counter-clockwise on screen'}; area ${r.area.toFixed(2)} pixels`);
  console.log(`  bounding box x ${x0}-${x1}, y ${y0}-${y1}: ${r.tested} centres tested, ${r.covered} covered`);
  if (r.ties) console.log(`  ${r.ties} centres exactly on an edge, ${r.tiesKept} of them kept by the top-left rule`);
  for (const row of r.rows) console.log(`  ${row.join('')}`);
}
console.log("# covered, o on a top or left edge (kept), - on a right or bottom edge (dropped), . outside");

Triangle A: (2.2, 1.4) (4.6, 10.8) (14.3, 6.1)
  counter-clockwise on screen; area 51.24 pixels
  bounding box x 2-13, y 1-10: 120 centres tested, 49 covered
  ................
  ................
  ..###...........
  ...#####........
  ...#######......
  ...##########...
  ....#########...
  ....#######.....
  ....#####.......
  ....###.........
  ................
  ................
Triangle B, A listed clockwise: (2.2, 1.4) (14.3, 6.1) (4.6, 10.8)
  clockwise on screen, two corners swapped; area 51.24 pixels
  bounding box x 2-13, y 1-10: 120 centres tested, 49 covered
  ................
  ................
  ..###...........
  ...#####........
  ...#######......
  ...##########...
  ....#########...
  ....#######.....
  ....#####.......
  ....###.........
  ................
  ................
Triangle C, corners on pixel centres: (12.5, 2.5) (3.5, 2.5) (7.5, 9.5)
  counter-clockwise on screen; area 31.50 pixels
  bounding box x 3-12, y 2-9: 80 centres tested, 36 covered
  11 centres exactly on an edge, 9 of them kept by the top-left rule
  ................
  ................
  ...ooooooooo-...
  ....########....
  .....######.....
  .....#####......
  ......####......
  ......###.......
  .......#........
  .......-........
  ................
  ................
Triangle D, a sliver: (0.6, 10.2) (15.4, 8.3) (15.4, 8.9)
  clockwise on screen, two corners swapped; area 4.42 pixels
  bounding box x 1-14, y 8-9: 28 centres tested, 4 covered
  ................
  ................
  ................
  ................
  ................
  ................
  ................
  ................
  ..............#.
  ......###.......
  ................
  ................
# covered, o on a top or left edge (kept), - on a right or bottom edge (dropped), . outside

Triangle A covers 49 pixels and needed 120 tests, not the target’s 192. Triangle B is A with its corners listed clockwise: the area comes out negative, two corners are swapped, and the 49 pixels are identical, so the winding orderwinding order: The order of a triangle's vertices as seen on screen, clockwise or counter-clockwise. A pipeline uses it to decide which triangles face the viewer. More in “Vectors, points, dot and cross products” changes the signs, never the coverage. Triangle D is a sliver trianglesliver triangle: A long, very thin triangle. It may enclose no pixel centre in some columns or rows, so its pixels come out in separate pieces, as point sampling allows. of 4.42 square pixels that covers 4 pixels in two separate pieces: in most columns its two long edges pass between centres, so it encloses none. That is point sampling working as specified, not a bug.

The top-left rule gives each shared centre to one triangle

Triangle C’s corners lie on pixel centres, so 11 of its centres give an edge value of exactly 0: ten on its horizontal top edge and one at its bottom corner. A centre on an edge is a tie, and in a mesh most edges are shared by two triangles. If both count such a centre as inside, the pixel is drawn twice; if neither does, it is a hole.

The top-left ruletop-left rule: A tie rule for a pixel centre that lies exactly on an edge: it belongs to a shape only when the edge is a top or a left edge of that shape, so shapes sharing the edge never both claim the pixel. More in “Polygon fill: scanline, boundary and flood fill” of Direct3D’s rasterization rules gives such a centre to a triangle when it lies on a top edge, horizontal with the triangle below it, or on a left edge, an edge that is not horizontal and is on the triangle’s left. A rasteriser applies it edge by edge, so a centre that lies on a right edge or a bottom edge as well is left out. For a counter-clockwise triangle in y-down coordinates, an edge from a to b is a left edge when b.y > a.y, and the top edge when b.y = a.y and b.x < a.x, so the rule is one comparison per edge. In triangle C it kept 9 of the 11: the top row from pixel 3 to 11, but not pixel 12, which also lies on the right edge, nor the bottom corner, which lies on a left edge and a right edge.

The real test is a shared edge. Cut a 10 × 10 square whose corners lie on pixel centres along its diagonal, and 11 centres lie on the cut:

The diagonal runs down the screen, so it is a left edge of the upper triangle, which lies to its right, and a right edge of the lower one: its centres go to the upper triangle, except the square’s last corner, which lies on the square’s bottom and right edges and goes to neither. The program counts the same square under four tie rules:

// A 10 x 10 square whose corners lie on pixel centres, cut along its diagonal into two triangles. Eleven pixel
// centres lie exactly on the shared diagonal, so the rule for a centre on an edge decides who draws them.
const SUB = 256;
const snap = ([x, y]) => [Math.round(x * SUB), Math.round(y * SUB)];
const edge = (a, b, p) => (p[0] - a[0]) * (b[1] - a[1]) - (p[1] - a[1]) * (b[0] - a[0]);
const topLeft = (a, b) => b[1] > a[1] || (b[1] === a[1] && b[0] < a[0]);

// What each rule does with a centre at w = 0, exactly on the edge from a to b.
const RULES = {
  closed: () => true, // on the edge counts as inside, for both triangles
  open: () => false, // on the edge counts as outside, for both triangles
  'top-left': (a, b) => topLeft(a, b),
  'bottom-right': (a, b) => !topLeft(a, b),
};

function covers(corners, x, y, onEdge) {
  let [a, b, c] = corners.map(snap);
  if (edge(a, b, c) < 0) [b, c] = [c, b];
  const p = [x * SUB + SUB / 2, y * SUB + SUB / 2];
  for (const [e0, e1] of [[b, c], [c, a], [a, b]]) {
    const w = edge(e0, e1, p);
    if (w < 0 || (w === 0 && !onEdge(e0, e1))) return false;
  }
  return true;
}

const corner = [[2.5, 1.5], [12.5, 1.5], [12.5, 11.5], [2.5, 11.5]];
const upper = [corner[0], corner[1], corner[2]];
const lower = [corner[0], corner[2], corner[3]];
// The nine centres on the diagonal between its two ends (the ends are corners of the square too).
const onDiagonal = (x, y) => x - 2 === y - 1 && x >= 3 && x <= 11;

const masks = {};
console.log('rule          drawn once  drawn twice  holes on the diagonal  pixels unlike top-left');
for (const [name, onEdge] of Object.entries(RULES)) {
  let once = 0;
  let twice = 0;
  let holes = 0;
  const mask = new Set();
  for (let y = 0; y < 14; y++) {
    for (let x = 0; x < 16; x++) {
      const n = Number(covers(upper, x, y, onEdge)) + Number(covers(lower, x, y, onEdge));
      if (n === 1) once++;
      if (n === 2) twice++;
      if (n === 0 && onDiagonal(x, y)) holes++;
      if (n > 0) mask.add(`${x},${y}`);
    }
  }
  masks[name] = mask;
  const ref = masks['top-left'];
  const unlike = ref ? [...mask].filter((k) => !ref.has(k)).length + [...ref].filter((k) => !mask.has(k)).length : 0;
  console.log(`${name.padEnd(14)}${String(once).padEnd(12)}${String(twice).padEnd(13)}${String(holes).padEnd(23)}${name === 'closed' || name === 'open' ? '-' : unlike}`);
}
const tl = masks['top-left'];
const cols = [...tl].map((k) => Number(k.split(',')[0]));
const rows = [...tl].map((k) => Number(k.split(',')[1]));
console.log(`top-left: columns ${Math.min(...cols)}-${Math.max(...cols)}, rows ${Math.min(...rows)}-${Math.max(...rows)}, ${tl.size} pixels for a square of area 100`);
const br = masks['bottom-right'];
const bcols = [...br].map((k) => Number(k.split(',')[0]));
const brows = [...br].map((k) => Number(k.split(',')[1]));
console.log(`bottom-right: columns ${Math.min(...bcols)}-${Math.max(...bcols)}, rows ${Math.min(...brows)}-${Math.max(...brows)}, ${br.size} pixels`);

rule          drawn once  drawn twice  holes on the diagonal  pixels unlike top-left
closed        110         11           0                      -
open          72          0            9                      -
top-left      100         0            0                      0
bottom-right  100         0            0                      38
top-left: columns 2-11, rows 1-10, 100 pixels for a square of area 100
bottom-right: columns 3-12, rows 2-11, 100 pixels

Counting a centre on an edge as inside, the closed rule, drew the 11 diagonal pixels twice; counting it as outside left 9 holes along the diagonal and shrank the square to 72 pixels. The top-left rule covered exactly 100 pixels, as a square of area 100 should, with none twice. The mirror rule, bottom-right, also covered 100 pixels once, yet its mask and the top-left one differ in 38 pixels: any consistent rule tiles a mesh exactly, and matching another renderer pixel for pixel needs the same rule.

Fixed point makes stepping across a row exact

Testing a centre costs three edge functions, two multiplications each. But E is linear in x and y, so moving one pixel to the right changes it by a constant, the edge’s height, and moving one row down by another, minus its width. With corners snapped to 1/256 pixel, one step in each direction is

In words: after the first centre of a row, each further centre costs one addition per edge. Triangle A’s snapped corners a and b differ by 2,407 in y, so one pixel to the right adds 256 × 2,407 = 616,192 to E_ab, which is 9.40 square pixels. The snapping is sub-pixel precisionsub-pixel precision: The number of fraction bits with which a rasteriser stores vertex positions. With 8 bits it snaps them to 1/256 of a pixel, so every edge test becomes exact integer arithmetic. of 8 bits: the Vulkan specification requires at least 4, and its Roadmap 2026 milestone asks for 8. With fixed pointfixed point: Numbers stored as integers that count a fixed fraction, such as 1/256 of a pixel, so that sums, products and comparisons of them are exact. More in “Floating point, precision and robust geometry”, every edge value is a whole number, so a step adds exactly, and E = 0 means the centre is exactly on the edge. The next program steps the three edges of a triangle about 1,000 pixels across over its whole bounding box, in fixed point and in float32:

// An edge function is linear in x and y, so stepping one pixel right adds a constant and stepping one row down adds
// another. This program steps the three edge functions of one large triangle across its whole bounding box, in
// fixed point (whole numbers of 1/256 pixel) and in float32, and compares every value with a direct evaluation.
const SUB = 256;
const f = Math.fround;
const corners = [[37.3, 21.8], [180.6, 1010.2], [997.9, 412.7]];

const snap = ([x, y]) => [Math.round(x * SUB), Math.round(y * SUB)];
const edge = (a, b, p) => (p[0] - a[0]) * (b[1] - a[1]) - (p[1] - a[1]) * (b[0] - a[0]);
const [a, b, c] = corners.map(snap);
const edges = [[b, c], [c, a], [a, b]];
// The pixels whose centres lie inside the triangle's bounding box.
const first = (v) => Math.ceil((v - SUB / 2) / SUB);
const last = (v) => Math.floor((v - SUB / 2) / SUB);
const x0 = first(Math.min(a[0], b[0], c[0]));
const x1 = last(Math.max(a[0], b[0], c[0]));
const y0 = first(Math.min(a[1], b[1], c[1]));
const y1 = last(Math.max(a[1], b[1], c[1]));

// Exact: every value is a whole number far below 2^53, so a double holds it exactly.
let fixedMismatch = 0;
let floatDecisions = 0;
let worstDrift = 0;
let largest = 0;
let pixels = 0;
const startP = [x0 * SUB + SUB / 2, y0 * SUB + SUB / 2];
for (const [e0, e1] of edges) {
  const stepX = SUB * (e1[1] - e0[1]); // E(p + one pixel right) - E(p)
  const stepY = -SUB * (e1[0] - e0[0]); // E(p + one row down) - E(p)
  let rowFixed = edge(e0, e1, startP);
  // float32: the same values in pixel units, stepped with float32 additions as a float rasteriser would.
  const scale = SUB * SUB;
  let rowFloat = f(rowFixed / scale);
  const stepXf = f(stepX / scale);
  const stepYf = f(stepY / scale);
  for (let y = y0; y <= y1; y++) {
    let eFixed = rowFixed;
    let eFloat = rowFloat;
    for (let x = x0; x <= x1; x++) {
      const direct = edge(e0, e1, [x * SUB + SUB / 2, y * SUB + SUB / 2]);
      if (eFixed !== direct) fixedMismatch++;
      largest = Math.max(largest, Math.abs(direct));
      // How far sideways the edge seems to move: the error divided by the change of E per pixel.
      const drift = Math.abs(eFloat * scale - direct) / Math.abs(stepX || stepY);
      worstDrift = Math.max(worstDrift, drift);
      if (eFloat >= 0 !== direct >= 0) floatDecisions++;
      pixels++;
      eFixed += stepX;
      eFloat = f(eFloat + stepXf);
    }
    rowFixed += stepY;
    rowFloat = f(rowFloat + stepYf);
  }
}
const group = (n) => String(n).replace(/\B(?=(\d{3})+(?!\d))/g, ',');
console.log(`bounding box x ${x0}-${x1}, y ${y0}-${y1}: ${group(pixels / 3)} pixel centres, 3 edge functions each`);
console.log(`fixed point, stepped: ${fixedMismatch} values differ from a direct evaluation`);
console.log(`float32, stepped: ${floatDecisions} centres land on the wrong side of an edge`);
console.log(`float32: the stepped edges stray up to ${worstDrift.toFixed(3)} pixel from where they are`);
console.log(`largest |E|: ${group(largest)}, about 2^${Math.log2(largest).toFixed(1)}: more than 32-bit integers hold, exact in a double`);

bounding box x 37-997, y 22-1009: 949,468 pixel centres, 3 edge functions each
fixed point, stepped: 0 values differ from a direct evaluation
float32, stepped: 13 centres land on the wrong side of an edge
float32: the stepped edges stray up to 0.084 pixel from where they are
largest |E|: 62,190,990,715, about 2^35.9: more than 32-bit integers hold, exact in a double

Over 949,468 centres, the fixed-point steps never differed from a direct evaluation. Float32 steps, the precision of a shader’s f32, put 13 centres on the wrong side of an edge: each addition rounds, and after hundreds of steps the edges had drifted by up to 0.084 pixel. The cost of exactness is width. The largest value was 62,190,990,715, about 2^35.9, more than a 32-bit integer holds, but far below 2^53, so a JavaScript number, a double, keeps every value exact.

Practise: rasterise a triangle with the top-left rule

Two exercises build the rasteriser of this lesson, and their sample tests run here. The first writes the edge function, puts the corners in counter-clockwise order and tests a point strictly inside; the second is the whole loop, with snapping, a clamped bounding box and the top-left rule, tested on triangles A to D and on the square cut along its diagonal:

/**
 * edge(a, b, p): the edge function of the edge from a to b at point p. counterClockwise(v0, v1, v2): the corners in
 * counter-clockwise screen order, or null when they lie on one line. inside(v0, v1, v2, p): strictly inside.
 * This first version takes the two vectors the other way round, so every sign is flipped, and it trusts the winding.
 */
export function edge(a, b, p) {
  return (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]);
}

export function counterClockwise(v0, v1, v2) {
  return [v0, v1, v2];
}

export function inside(v0, v1, v2, p) {
  const [a, b, c] = counterClockwise(v0, v1, v2);
  return edge(b, c, p) > 0 && edge(c, a, p) > 0 && edge(a, b, p) > 0;
}

import { test, assert } from 'mysmartcopilot:test';
import { counterClockwise, edge, inside } from './edges.mjs';

// The lesson's triangle A, counter-clockwise on screen, and B, the same corners listed clockwise.
const A = [[2.2, 1.4], [4.6, 10.8], [14.3, 6.1]];
const B = [[2.2, 1.4], [14.3, 6.1], [4.6, 10.8]];
const near = (got, want, label) => assert.ok(Math.abs(got - want) < 1e-9, `${label}: got ${got}, expected ${want}`);

test("edge values of triangle A at the lesson's centres", () => {
  const [a, b, c] = A;
  near(edge(b, c, [6.5, 5.5]), 42.48, 'E_bc at (6.5, 5.5)');
  near(edge(c, a, [6.5, 5.5]), 29.4, 'E_ca at (6.5, 5.5)');
  near(edge(a, b, [6.5, 5.5]), 30.58, 'E_ab at (6.5, 5.5)');
  near(edge(b, c, [13.5, 6.5]), -0.12, 'E_bc at (13.5, 6.5): just outside, near corner c');
  near(edge(a, b, [2.5, 2.5]), 0.18, 'E_ab at (2.5, 2.5): just inside');
  near(edge(a, b, a), 0, 'a corner lies on its own edges');
  near(edge(a, b, [3.4, 6.1]), 0, 'the midpoint of edge ab');
});

test('the three edge values always add up to twice the area', () => {
  const [a, b, c] = A;
  for (const p of [[0, 0], [6.5, 5.5], [20, -3], [13.5, 6.5]]) {
    near(edge(b, c, p) + edge(c, a, p) + edge(a, b, p), 102.46, `the sum at (${p})`);
  }
  near(edge(a, b, c), 102.46, 'corner c against edge ab');
});

test('counterClockwise keeps A, swaps B and refuses a flat triangle', () => {
  assert.deepEqual(counterClockwise(...A), A, 'A already runs counter-clockwise');
  const fixed = counterClockwise(...B);
  assert.ok(Array.isArray(fixed) && fixed.length === 3, 'B gives three corners');
  assert.ok(edge(fixed[0], fixed[1], fixed[2]) > 0, 'after the swap the area is positive');
  assert.deepEqual(fixed, [B[0], B[2], B[1]], 'B with its last two corners swapped');
  assert.equal(counterClockwise([0, 0], [2, 1], [6, 3]), null, 'three corners on one line');
});

test('inside, for either winding, strictly', () => {
  for (const t of [A, B]) {
    assert.equal(inside(...t, [6.5, 5.5]), true, '(6.5, 5.5) is inside');
    assert.equal(inside(...t, [2.5, 2.5]), true, '(2.5, 2.5) is inside, by 0.18');
    assert.equal(inside(...t, [13.5, 6.5]), false, '(13.5, 6.5) is outside edge bc');
    assert.equal(inside(...t, [3.5, 9.5]), false, '(3.5, 9.5) is outside edge ab');
  }
  // Whole-number corners, so that a point on an edge gives exactly 0.
  const T = [[1, 1], [3, 9], [11, 5]];
  assert.equal(inside(...T, [5, 5]), true, '(5, 5) is inside the whole-number triangle');
  assert.equal(inside(...T, [2, 5]), false, 'the midpoint of an edge is not strictly inside');
  assert.equal(inside(T[0], T[2], T[1], [2, 5]), false, 'nor with the corners listed clockwise');
  assert.equal(inside(...T, [1, 1]), false, 'nor a corner');
  assert.equal(inside([0, 0], [2, 1], [6, 3], [2, 1]), false, 'a flat triangle has no inside');
});

/**
 * rasterizeTriangle(v0, v1, v2, width, height): a Uint8Array of width × height, 1 where the triangle covers the pixel
 * centre (x + 0.5, y + 0.5). This first version counts every centre on an edge as inside, from both sides, and
 * assumes that the corners run counter-clockwise on screen.
 */
export function rasterizeTriangle(v0, v1, v2, width, height) {
  const mask = new Uint8Array(width * height);
  const edge = (a, b, p) => (p[0] - a[0]) * (b[1] - a[1]) - (p[1] - a[1]) * (b[0] - a[0]);
  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      const p = [x + 0.5, y + 0.5];
      if (edge(v1, v2, p) >= 0 && edge(v2, v0, p) >= 0 && edge(v0, v1, p) >= 0) mask[y * width + x] = 1;
    }
  }
  return mask;
}

import { test, assert } from 'mysmartcopilot:test';
import { rasterizeTriangle } from './raster.mjs';

const W = 16;
const H = 12;
const rows = (mask, w = W, h = H) => Array.from({ length: h }, (_, y) => Array.from({ length: w }, (_, x) => (mask[y * w + x] ? '#' : '.')).join(''));
const count = (mask) => mask.reduce((n, v) => n + (v ? 1 : 0), 0);
// The lesson's triangles (examples/raster/rasterize_tri.mjs).
const A = [[2.2, 1.4], [4.6, 10.8], [14.3, 6.1]];
const C = [[12.5, 2.5], [3.5, 2.5], [7.5, 9.5]];
const D = [[0.6, 10.2], [15.4, 8.3], [15.4, 8.9]];

test('triangle A covers the 49 pixels of the lesson', () => {
  const mask = rasterizeTriangle(...A, W, H);
  assert.ok(mask instanceof Uint8Array && mask.length === W * H, 'a Uint8Array of width × height values');
  assert.deepEqual(rows(mask), [
    '................',
    '................',
    '..###...........',
    '...#####........',
    '...#######......',
    '...##########...',
    '....#########...',
    '....#######.....',
    '....#####.......',
    '....###.........',
    '................',
    '................',
  ]);
});

test('the same corners listed clockwise give the same pixels', () => {
  const B = [A[0], A[2], A[1]];
  assert.deepEqual(rows(rasterizeTriangle(...B, W, H)), rows(rasterizeTriangle(...A, W, H)));
  assert.deepEqual(rows(rasterizeTriangle(C[1], C[0], C[2], W, H)), rows(rasterizeTriangle(...C, W, H)), 'C clockwise');
});

test('triangle C: centres on its top and left edges count, those on its right edge do not', () => {
  const mask = rasterizeTriangle(...C, W, H);
  assert.equal(count(mask), 36);
  assert.equal(rows(mask)[2], '...#########....', 'row 2 lies on the top edge: pixels 3 to 11, not 12, which is on the right edge too');
  assert.equal(mask[9 * W + 7], 0, 'the bottom corner (7.5, 9.5) lies on a left and a right edge: not covered');
  assert.equal(mask[3 * W + 4], 1, 'pixel (4, 3) is inside');
});

test('corners are snapped to 1/256 pixel', () => {
  const nudged = C.map(([x, y]) => [x + 0.001, y + 0.001]);
  assert.equal(count(rasterizeTriangle(...nudged, W, H)), 36, '0.001 pixel rounds back onto the corners of C');
  const moved = C.map(([x, y]) => [x + 0.004, y + 0.004]);
  assert.equal(count(rasterizeTriangle(...moved, W, H)), 27, '0.004 pixel snaps 1/256 lower, below the centres of row 2');
});

test('a sliver, a flat triangle and one that pokes out of the target', () => {
  const sliver = rows(rasterizeTriangle(...D, W, H));
  assert.equal(sliver[8], '..............#.');
  assert.equal(sliver[9], '......###.......');
  assert.equal(count(rasterizeTriangle([1, 1], [5, 5], [9, 9], W, H)), 0, 'three corners on one line cover nothing');
  const big = rasterizeTriangle([-5, -5], [20, 2], [3, 20], W, H);
  assert.equal(big.length, W * H, 'nothing is written outside the target');
  assert.equal(count(big), 176);
  assert.equal(rows(big)[11], '###########.....');
});

test('the 10 × 10 square cut on its diagonal: every pixel once', () => {
  const sq = [[2.5, 1.5], [12.5, 1.5], [12.5, 11.5], [2.5, 11.5]];
  const upper = rasterizeTriangle(sq[0], sq[1], sq[2], 16, 14);
  const lower = rasterizeTriangle(sq[0], sq[2], sq[3], 16, 14);
  let twice = 0;
  let once = 0;
  for (let i = 0; i < upper.length; i++) {
    if (upper[i] && lower[i]) twice++;
    else if (upper[i] || lower[i]) once++;
  }
  assert.equal(twice, 0, 'no pixel on the diagonal is drawn by both triangles');
  assert.equal(once, 100, 'the square covers exactly 100 pixels');
  assert.equal(count(upper), 55, 'the upper triangle takes the centres on the diagonal');
});

A last round of questions covers the four ideas, starting with the one your answers so far found hardest:

Interview questions

The warm-up is answered here in full. The two questions after it come from rasterisers at work, and each row leads to the software-rasteriser question bank, where its first step and likely follow-ups are listed:

Key takeaways

• An edge function is a cross product that is 0 on the edge’s line and positive on the inside of a counter-clockwise triangle; a pixel centre is inside when all three edge values are positive, and the three always add up to twice the area.
• A rasteriser snaps the corners, fixes the winding from the sign of the area, and tests only the centres of the bounding box: 120 tests for triangle A’s 49 pixels, the same pixels in either winding.
• The top-left rule gives a centre that lies exactly on an edge to the triangle for which that edge is a top or a left edge, so the square cut on its diagonal covered exactly 100 pixels, none twice.
• Edge values change by constants from pixel to pixel; in fixed point with 8 sub-pixel bits every step is exact, while float32 steps put 13 of 949,468 centres on the wrong side.