Skip to content

armgit / 67.js

Public Imported from GitHub
0

3D engine that AI agents drive

9.4 KB
Raw Blame
// The float64 ray cast behind ground-truth.js (issue #751): which triangle is visible at each pixel centre. It scan-converts every
// triangle into a small per-pixel list of the nearest hits, in double precision with perspective-correct depth, so no depth
// buffer rounding can pick the wrong face. Cost follows the area the triangles cover, not triangles times pixels.

export const NO_TRIANGLE = -1;
export const RIVALS_PER_PIXEL = 2;
const TIE_RELATIVE_DISTANCE = 1e-9;
export const DEFAULT_HITS_PER_PIXEL = 6;
const NEAR_DEPTH = 1e-4;
// A pixel centre exactly on an edge shared by two triangles must not fall between them through rounding.
const EDGE_SLACK = 1e-9;

export function subtract(first, second) {
  return [first[0] - second[0], first[1] - second[1], first[2] - second[2]];
}

export function dot(first, second) {
  return first[0] * second[0] + first[1] * second[1] + first[2] * second[2];
}

export function crossProduct(first, second) {
  return [first[1] * second[2] - first[2] * second[1], first[2] * second[0] - first[0] * second[2], first[0] * second[1] - first[1] * second[0]];
}

export function normalized(vector) {
  const length = Math.hypot(...vector) || 1;
  return vector.map(value => value / length);
}

function cameraBasis({ eye, target, up = [0, 1, 0], fov = 45 }, width, height) {
  const forward = normalized(subtract(target, eye));
  const right = normalized(crossProduct(forward, up));
  const upward = crossProduct(right, forward);
  return { eye, forward, right, upward, tangent: Math.tan(fov * Math.PI / 360), aspect: width / height };
}

// A world point as [sideways, up, depth] from the camera.
function toCameraSpace(basis, x, y, z) {
  const relative = [x - basis.eye[0], y - basis.eye[1], z - basis.eye[2]];
  return [dot(relative, basis.right), dot(relative, basis.upward), dot(relative, basis.forward)];
}

// The part of a camera-space triangle in front of the near depth, as a polygon of up to four points.
function clipToNear(points) {
  const kept = [];
  for (let index = 0; index < points.length; index++) {
    const current = points[index];
    const next = points[(index + 1) % points.length];
    const currentInside = current[2] >= NEAR_DEPTH;
    if (currentInside) kept.push(current);
    if (currentInside !== (next[2] >= NEAR_DEPTH)) {
      const share = (NEAR_DEPTH - current[2]) / (next[2] - current[2]);
      kept.push([0, 1, 2].map(axis => current[axis] + (next[axis] - current[axis]) * share));
    }
  }
  return kept;
}

// Whether the first hit is nearer than the second; hits at one distance (to 1e-9) go to the higher rank, then the later triangle.
function isNearer(world, firstDistance, firstTriangle, secondDistance, secondTriangle) {
  const gap = firstDistance - secondDistance;
  if (Math.abs(gap) > TIE_RELATIVE_DISTANCE * firstDistance) return gap < 0;
  return world.ranks[firstTriangle] !== world.ranks[secondTriangle] ? world.ranks[firstTriangle] > world.ranks[secondTriangle] : firstTriangle > secondTriangle;
}

function recordHit(world, hits, pixel, distance, triangle) {
  const { hitDistances, hitTriangles, hitsPerPixel } = hits;
  const base = pixel * hitsPerPixel;
  let slot = 0;
  while (slot < hitsPerPixel - 1 && hitTriangles[base + slot] !== NO_TRIANGLE) slot++;
  const full = hitTriangles[base + slot] !== NO_TRIANGLE;
  if (full && !isNearer(world, distance, triangle, hitDistances[base + slot], hitTriangles[base + slot])) return;
  while (slot > 0 && isNearer(world, distance, triangle, hitDistances[base + slot - 1], hitTriangles[base + slot - 1])) {
    hitDistances[base + slot] = hitDistances[base + slot - 1];
    hitTriangles[base + slot] = hitTriangles[base + slot - 1];
    slot--;
  }
  hitDistances[base + slot] = distance;
  hitTriangles[base + slot] = triangle;
}

// Scan-converts one camera-space triangle: pixel centres inside it, with depth interpolated as 1/depth in screen space.
function rasterize(world, basis, triangle, points, width, height, hits) {
  const screen = points.map(([sideways, upward, depth]) => [
    (sideways / depth / (basis.aspect * basis.tangent) * 0.5 + 0.5) * width,
    (0.5 - upward / depth / basis.tangent * 0.5) * height,
    1 / depth,
  ]);
  const [first, second, third] = screen;
  const area = (second[0] - first[0]) * (third[1] - first[1]) - (second[1] - first[1]) * (third[0] - first[0]);
  if (area === 0) return;
  const minimumX = Math.max(0, Math.floor(Math.min(first[0], second[0], third[0]) - 0.5));
  const maximumX = Math.min(width - 1, Math.ceil(Math.max(first[0], second[0], third[0]) - 0.5));
  const minimumY = Math.max(0, Math.floor(Math.min(first[1], second[1], third[1]) - 0.5));
  const maximumY = Math.min(height - 1, Math.ceil(Math.max(first[1], second[1], third[1]) - 0.5));
  for (let y = minimumY; y <= maximumY; y++) {
    for (let x = minimumX; x <= maximumX; x++) {
      const centreX = x + 0.5;
      const centreY = y + 0.5;
      const weightFirst = ((second[0] - centreX) * (third[1] - centreY) - (second[1] - centreY) * (third[0] - centreX)) / area;
      const weightSecond = ((third[0] - centreX) * (first[1] - centreY) - (third[1] - centreY) * (first[0] - centreX)) / area;
      const weightThird = 1 - weightFirst - weightSecond;
      if (weightFirst < -EDGE_SLACK || weightSecond < -EDGE_SLACK || weightThird < -EDGE_SLACK) continue;
      const inverseDepth = weightFirst * first[2] + weightSecond * second[2] + weightThird * third[2];
      recordHit(world, hits, y * width + x, 1 / inverseDepth, triangle);
    }
  }
}

// Whether the triangle faces the eye (counter-clockwise seen from it); double-sided triangles always count.
function facesEye(world, basis, triangle) {
  if (world.doubleSided[triangle] === 1) return true;
  const base = triangle * 9;
  const corners = world.corners;
  const edgeOne = [corners[base + 3] - corners[base], corners[base + 4] - corners[base + 1], corners[base + 5] - corners[base + 2]];
  const edgeTwo = [corners[base + 6] - corners[base], corners[base + 7] - corners[base + 1], corners[base + 8] - corners[base + 2]];
  return dot(crossProduct(edgeOne, edgeTwo), subtract(basis.eye, [corners[base], corners[base + 1], corners[base + 2]])) > 0;
}

// Two faces of different colour at one distance with one rank: nothing in the scene says which is in front, so no render is wrong.
function isTie(world, distances, triangles, base, hitsPerPixel) {
  const nearestTriangle = triangles[base];
  for (let slot = 1; slot < hitsPerPixel && triangles[base + slot] !== NO_TRIANGLE; slot++) {
    if (Math.abs(distances[base + slot] - distances[base]) > TIE_RELATIVE_DISTANCE * distances[base]) return false;
    const other = triangles[base + slot];
    if (world.keyOf[nearestTriangle] !== world.keyOf[other] && world.ranks[nearestTriangle] === world.ranks[other]) return true;
  }
  return false;
}

/**
 * Casts one ray through every pixel centre of a `width` x `height` image. `world` is the result of `collectWorldTriangles`,
 * `camera` the `{ eye, target, up, fov }` of the frame. Returns `{ owner, rivals, tied, distance }`: `distance` is the depth of the visible face in front of the camera (0 for the background); `owner` is the visible triangle of
 * each pixel (`NO_TRIANGLE` for the background), `rivals` holds up to two colour keys of other triangles on the same ray, or
 * -1, and `tied` marks pixels where two faces of different colour lie at one distance with one rank. Only the `hitsPerPixel` (default six) nearest
 * faces of a ray are kept, which is enough to name its visible face and the faces right behind it.
 */
export function castPixelOwners(world, camera, width, height, hitsPerPixel = DEFAULT_HITS_PER_PIXEL) {
  const basis = cameraBasis(camera, width, height);
  const hitDistances = new Float64Array(width * height * hitsPerPixel);
  const hitTriangles = new Int32Array(width * height * hitsPerPixel).fill(NO_TRIANGLE);
  const hits = { hitDistances, hitTriangles, hitsPerPixel };
  for (let triangle = 0; triangle < world.count; triangle++) {
    if (!facesEye(world, basis, triangle)) continue;
    const base = triangle * 9;
    const points = [0, 1, 2].map(corner => toCameraSpace(basis, world.corners[base + corner * 3], world.corners[base + corner * 3 + 1], world.corners[base + corner * 3 + 2]));
    const polygon = points.every(point => point[2] >= NEAR_DEPTH) ? points : clipToNear(points);
    for (let corner = 1; corner + 1 < polygon.length; corner++) {
      rasterize(world, basis, triangle, [polygon[0], polygon[corner], polygon[corner + 1]], width, height, hits);
    }
  }
  const owner = new Int32Array(width * height).fill(NO_TRIANGLE);
  const rivals = new Int32Array(width * height * RIVALS_PER_PIXEL).fill(-1);
  const tied = new Uint8Array(width * height);
  const distance = new Float64Array(width * height);
  for (let pixel = 0; pixel < width * height; pixel++) {
    const base = pixel * hitsPerPixel;
    if (hitTriangles[base] === NO_TRIANGLE) continue;
    owner[pixel] = hitTriangles[base];
    distance[pixel] = hitDistances[base];
    tied[pixel] = isTie(world, hitDistances, hitTriangles, base, hitsPerPixel) ? 1 : 0;
    const ownKey = world.keyOf[hitTriangles[base]];
    let stored = 0;
    for (let slot = 1; slot < hitsPerPixel && hitTriangles[base + slot] !== NO_TRIANGLE && stored < RIVALS_PER_PIXEL; slot++) {
      const key = world.keyOf[hitTriangles[base + slot]];
      const known = key === ownKey || (stored > 0 && rivals[pixel * RIVALS_PER_PIXEL] === key);
      if (!known) rivals[pixel * RIVALS_PER_PIXEL + stored++] = key;
    }
  }
  return { owner, rivals, tied, distance, hitTriangles, hitDistances, hitsPerPixel };
}