Skip to content

armgit / 67.js

Public Imported from GitHub
0

3D engine that AI agents drive

14.4 KB
Raw Blame
// Ground truth for the flicker probe (issue #751). The jitter probe compares a render with a copy of itself, so it counts crease
// anti-aliasing as flicker and misses speckle that sits next to a colour step. This module answers the question directly: for
// every pixel it intersects the camera ray with every triangle in float64, which cannot z-fight, names the triangle that is
// visible, and the probe then asks whether the raster render shows that triangle's colour there.
//
// A triangle's colour is looked up by a key (albedo, vertex colour and facing), not by its own pixels: a plaque flush on a wall
// has no pixel of its own that the wall could not also claim, so the colour it should have is the median of the pixels where
// the ray cast says it is visible. Pixels next to another key (silhouettes, creases, anti-aliased edges) are left out, so only
// the interior of a face is judged.

import { depthLayerOf, RANKS_PER_LAYER } from '../../src/depth-layer.js';
import { castPixelOwners, crossProduct, normalized, subtract, NO_TRIANGLE, RIVALS_PER_PIXEL } from './pixel-cast.js';

export { castPixelOwners, NO_TRIANGLE };

const NORMAL_KEY_SCALE = 100;
// Fine enough that triangle ids painted as 24-bit colours stay apart as keys, however a frame encodes them.
export const COLOUR_KEY_SCALE = 1e7;
export const DEFAULT_COLOUR_THRESHOLD = 40;
const MINIMUM_REFERENCE_PIXELS = 3;
// A shown colour this close (largest channel, in bytes) to the one the ray cast expects is a rounding step of the frame, not another face.
const OFF_BY_ONE_STEP = 2;
const SMALL_COLOUR_GAP = 16;

function transformPoint(matrix, x, y, z, target, offset) {
  target[offset] = matrix[0] * x + matrix[4] * y + matrix[8] * z + matrix[12];
  target[offset + 1] = matrix[1] * x + matrix[5] * y + matrix[9] * z + matrix[13];
  target[offset + 2] = matrix[2] * x + matrix[6] * y + matrix[10] * z + matrix[14];
}

// The triangles of a part as it is drawn: the cut geometry and the rank of each triangle when the flush pass made an order.
function drawnTriangles(part, flushOrder) {
  if (!flushOrder) return { geometry: part.geometry, indices: part.geometry.indices, ranks: null };
  const geometry = flushOrder.geometry ?? part.geometry;
  const ranks = new Uint8Array(flushOrder.indices.length / 3);
  for (const range of flushOrder.ranges) ranks.fill(range.rank, range.start / 3, (range.start + range.count) / 3);
  return { geometry, indices: flushOrder.indices, ranks };
}

function colourKey(part, geometry, firstVertex, vertexCount, facing) {
  const material = part.material?.color ?? [1, 1, 1];
  const stride = geometry.colors ? geometry.colors.length / vertexCount : 0;
  const vertexColour = stride >= 3 ? [0, 1, 2].map(channel => geometry.colors[firstVertex * stride + channel]) : [1, 1, 1];
  const colour = [0, 1, 2].map(channel => Math.round(material[channel] * vertexColour[channel] * COLOUR_KEY_SCALE));
  const normal = facing.map(value => Math.round(value * NORMAL_KEY_SCALE));
  return `${colour.join(',')}|${normal.join(',')}`;
}

/**
 * Every opaque triangle of the parts in world space, in float64.
 * Returns `{ corners, keys, keyOf, ranks, doubleSided, count }`: `corners` holds nine numbers per triangle, `keyOf` the colour key
 * id of each triangle, `ranks` its flush rank (0 without an order). `flushOrderOf` is the lookup of depth-layer.js.
 * Parts that blend or cut out alpha are skipped: their visible colour is a mix the key cannot name.
 */
export function collectWorldTriangles(parts, flushOrderOf) {
  const cornerChunks = [];
  const keyIds = new Map();
  const keyColours = [];
  const keyOf = [];
  const rankList = [];
  const doubleSidedList = [];
  for (const part of parts) {
    if ((part.material?.alphaMode ?? 'opaque') !== 'opaque') continue;
    const { geometry, indices, ranks } = drawnTriangles(part, flushOrderOf(part));
    const vertexCount = geometry.positions.length / 3;
    const triangleCount = indices.length / 3;
    const corners = new Float64Array(triangleCount * 9);
    for (let triangle = 0; triangle < triangleCount; triangle++) {
      for (let corner = 0; corner < 3; corner++) {
        const vertex = indices[triangle * 3 + corner] * 3;
        transformPoint(part.matrix, geometry.positions[vertex], geometry.positions[vertex + 1], geometry.positions[vertex + 2], corners, triangle * 9 + corner * 3);
      }
      const base = triangle * 9;
      const first = [corners[base], corners[base + 1], corners[base + 2]];
      const edgeOne = subtract([corners[base + 3], corners[base + 4], corners[base + 5]], first);
      const edgeTwo = subtract([corners[base + 6], corners[base + 7], corners[base + 8]], first);
      const key = colourKey(part, geometry, indices[triangle * 3], vertexCount, normalized(crossProduct(edgeOne, edgeTwo)));
      if (!keyIds.has(key)) {
        keyIds.set(key, keyIds.size);
        keyColours.push(key.split('|')[0].split(',').map(Number));
      }
      keyOf.push(keyIds.get(key));
      rankList.push(depthLayerOf(part) * RANKS_PER_LAYER + (ranks ? ranks[triangle] : 0));
      doubleSidedList.push(part.material?.doubleSided === true ? 1 : 0);
    }
    cornerChunks.push(corners);
  }
  const total = cornerChunks.reduce((sum, chunk) => sum + chunk.length, 0);
  const corners = new Float64Array(total);
  let offset = 0;
  for (const chunk of cornerChunks) {
    corners.set(chunk, offset);
    offset += chunk.length;
  }
  return { corners, keyOf: Int32Array.from(keyOf), ranks: Uint8Array.from(rankList), doubleSided: Uint8Array.from(doubleSidedList), keyCount: keyIds.size, keyColours, count: keyOf.length };
}

function channelDistance(pixels, index, reference) {
  return Math.max(Math.abs(pixels[index] - reference[0]), Math.abs(pixels[index + 1] - reference[1]), Math.abs(pixels[index + 2] - reference[2]));
}

function median(values) {
  const sorted = Float64Array.from(values).sort();
  return sorted[Math.floor(sorted.length / 2)];
}

// A pixel is judged only when it and its eight neighbours see one colour key: edges, creases and silhouettes are left out.
function hasUniformSurroundings(keyAt, width, height, x, y) {
  if (x < 1 || y < 1 || x >= width - 1 || y >= height - 1) return false;
  const own = keyAt[y * width + x];
  if (own < 0) return false;
  for (let row = -1; row <= 1; row++) {
    for (let column = -1; column <= 1; column++) {
      if (keyAt[(y + row) * width + x + column] !== own) return false;
    }
  }
  return true;
}

// The rank of the nearest face of colour key `key` on the ray of `pixel`, which is the face a swapped pixel shows.
function shownRank(world, cast, pixel, key) {
  for (let slot = 0; slot < cast.hitsPerPixel; slot++) {
    const triangle = cast.hitTriangles[pixel * cast.hitsPerPixel + slot];
    if (triangle === NO_TRIANGLE) break;
    if (world.keyOf[triangle] === key) return world.ranks[triangle];
  }
  return -1;
}

// Whether any of the eight neighbours of a pixel has another visible triangle (or none): the pixel then sits within a pixel of an
// edge, silhouette or crease of the ray cast, where the rasteriser and the cast may disagree about which side the centre is on.
function touchesOwnerChange(owner, width, pixel) {
  const own = owner[pixel];
  for (let row = -1; row <= 1; row++) {
    for (let column = -1; column <= 1; column++) {
      if (owner[pixel + row * width + column] !== own) return true;
    }
  }
  return false;
}

// Says what a wrong pixel of an exact frame shows. The colour names a face: when that face lies on the ray (one of its six nearest
// hits) the pixel is swapped, and it is flipped when the face has no higher rank than the one the ray cast puts in front. A face
// that is not on the ray is the rasteriser and the ray cast disagreeing about a pixel centre (offRay), and a colour that names no
// face is a blend of two (blended). Neither is depth fighting.
function classifyExactMismatch(result, mismatchMask, { pixels, pixel, width, world, cast, keyByColour, expected }) {
  const shownKey = keyByColour.get(`${pixels[pixel * 4]},${pixels[pixel * 4 + 1]},${pixels[pixel * 4 + 2]}`);
  if (shownKey === undefined) {
    result.blended++;
    return;
  }
  const rank = shownRank(world, cast, pixel, shownKey);
  if (rank < 0) {
    result.offRay++;
    const gap = channelDistance(pixels, pixel * 4, expected);
    const atEdge = touchesOwnerChange(cast.owner, width, pixel);
    if (atEdge) result.offRayEdge++;
    else result.offRayInterior++;
    if (gap <= OFF_BY_ONE_STEP) result.offRayNearColour++;
    else if (gap <= SMALL_COLOUR_GAP) result.offRaySmallGap++;
    if (!atEdge && gap > SMALL_COLOUR_GAP) result.offRayUnexplained++;
    return;
  }
  result.swapped++;
  mismatchMask[pixel] = 2;
  if (rank > world.ranks[cast.owner[pixel]]) result.ranked++;
  else result.flipped++;
}

/**
 * Compares a rendered frame (RGBA bytes, rows from the top) with the ray cast of `castPixelOwners`.
 * Returns `{ contested, wrong, swapped, tied, unjudged, edge }`:
 * - `contested`: interior pixels where another colour lies behind the visible one, the only place depth can fight;
 * - `wrong`: contested pixels whose colour is further than `threshold` (0 to 255, largest channel) from the visible face's colour;
 * - `swapped`: wrong pixels that sit within `threshold` of the colour of a face behind, a fight and not shading;
 * - `tied`: contested pixels where the scene itself does not say which face is in front (the flush pass off, or a seam); left out of the other counts;
 * - `unjudged`: contested pixels whose face has too few clean pixels to know its colour;
 * - `offRay` and `blended`: with `exact`, wrong pixels that show a face not on the ray, or no single face (see classifyExactMismatch);
 * - `offRayEdge` and `offRayInterior`: `offRay` split by whether the pixel touches an owner change of the ray cast in its 3x3
 *   neighbourhood. Edge pixels are the rasteriser and the cast disagreeing about a pixel centre. An interior pixel has no such excuse:
 *   its face may be one deeper than `hitsPerPixel` of the cast, which would be a real flip. `offRayUnexplained` is the interior part
 *   whose shown colour is also more than 16 bytes from the colour expected there, so `flipped + offRayUnexplained` is the upper bound
 *   of true flips (`flipUpperBound`);
 * - `offRayNearColour` and `offRaySmallGap`: offRay pixels whose shown colour is within 2 bytes, or 3 to 16, of the colour the ray cast
 *   expects. Triangle numbers are neighbours in colour, so a rounding step of the frame can name another, unrelated triangle.
 * - `flipped`: with `exact`, the swapped pixels where the face shown has no higher rank than the face the ray cast puts in front, so
 *   a face behind covers one in front and nothing in the scene asked for it: a true visibility flip. The rest of `swapped` is
 *   `ranked`, a face that the flush pass deliberately lifts over the nearer one inside its bias, which is stable and not flicker;
 * - `edge`: pixels left out for having another colour next to them.
 * With `exact`, a function from the colour of a face (0 to 1 per channel) to the bytes the frame shows for it, the frame holds an
 * unshaded colour per face (an unlit scene painted with one colour per triangle): the colour a face must show is that, not a median
 * of its pixels, and `threshold` is 0, so a swapped pixel is a true visibility
 * flip (the raster shows another face's id where the ray cast says this face is in front) and no shading step can pass for one.
 * `mismatchMask` marks the wrong pixels for a picture: 1 for a wrong pixel, 2 for a swapped one.
 */
export function compareWithGroundTruth({ pixels, world, cast, width, height, exact = null, threshold = exact ? 0 : DEFAULT_COLOUR_THRESHOLD }) {
  const keyAt = new Int32Array(width * height);
  for (let pixel = 0; pixel < keyAt.length; pixel++) keyAt[pixel] = cast.owner[pixel] === NO_TRIANGLE ? -1 : world.keyOf[cast.owner[pixel]];
  const references = new Array(world.keyCount);
  const samples = Array.from({ length: exact ? 0 : world.keyCount }, () => ({ clean: [[], [], []], any: [[], [], []], cleanCount: 0 }));
  if (exact) world.keyColours.forEach((colour, key) => { references[key] = exact(colour.map(channel => channel / COLOUR_KEY_SCALE)); });
  for (let y = 1; y < height - 1 && !exact; y++) {
    for (let x = 1; x < width - 1; x++) {
      if (!hasUniformSurroundings(keyAt, width, height, x, y)) continue;
      const pixel = y * width + x;
      const bucket = samples[keyAt[pixel]];
      const contested = cast.rivals[pixel * RIVALS_PER_PIXEL] >= 0;
      for (let channel = 0; channel < 3; channel++) {
        bucket.any[channel].push(pixels[pixel * 4 + channel]);
        if (!contested) bucket.clean[channel].push(pixels[pixel * 4 + channel]);
      }
      if (!contested) bucket.cleanCount++;
    }
  }
  samples.forEach((bucket, key) => {
    const source = bucket.cleanCount >= MINIMUM_REFERENCE_PIXELS ? bucket.clean : bucket.any;
    if (source[0].length >= MINIMUM_REFERENCE_PIXELS) references[key] = source.map(median);
  });
  const result = { contested: 0, wrong: 0, swapped: 0, tied: 0, unjudged: 0, edge: 0, flipped: 0, ranked: 0, offRay: 0, offRayEdge: 0, offRayInterior: 0, offRayNearColour: 0, offRaySmallGap: 0, offRayUnexplained: 0, blended: 0 };
  const keyByColour = new Map();
  references.forEach((reference, key) => { if (exact) keyByColour.set(reference.join(','), key); });
  const mismatchMask = new Uint8Array(width * height);
  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      const pixel = y * width + x;
      if (keyAt[pixel] < 0 || cast.rivals[pixel * RIVALS_PER_PIXEL] < 0) continue;
      if (!hasUniformSurroundings(keyAt, width, height, x, y)) {
        result.edge++;
        continue;
      }
      result.contested++;
      if (cast.tied[pixel]) {
        result.tied++;
        continue;
      }
      const reference = references[keyAt[pixel]];
      if (!reference) {
        result.unjudged++;
        continue;
      }
      if (channelDistance(pixels, pixel * 4, reference) <= threshold) continue;
      result.wrong++;
      mismatchMask[pixel] = 1;
      if (exact) {
        classifyExactMismatch(result, mismatchMask, { pixels, pixel, width, world, cast, keyByColour, expected: reference });
        continue;
      }
      for (let slot = 0; slot < RIVALS_PER_PIXEL; slot++) {
        const rival = references[cast.rivals[pixel * RIVALS_PER_PIXEL + slot]];
        if (rival && channelDistance(pixels, pixel * 4, rival) <= threshold) {
          result.swapped++;
          mismatchMask[pixel] = 2;
          break;
        }
      }
    }
  }
  return { ...result, flipUpperBound: result.flipped + result.offRayUnexplained, mismatchMask };
}