Skip to content

armgit / 67.js

Public Imported from GitHub
0

3D engine that AI agents drive

27.7 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: 2011-2022 Blender Foundation
//
// Host-side light tree for the Cycles-parity native kernel. A translation of the build half of Blender Cycles 5.3
// `scene/light_tree.cpp` and `light_tree.h`: a bounding volume tree over analytic lights and emissive triangles whose
// nodes hold a bounding box, a bounding cone (axis, theta_o, theta_e) and an energy, split with the surface area
// orientation heuristic (12 centroid buckets, at most 8 emitters per leaf). Distant lights (the sun) form one leaf
// outside the local tree, as in Cycles, and the environment is not an emitter of this tree.
// Pure typed arrays, no Node-only imports. The buffer layout is documented in FORMAT-v2.md section 7.

export const LIGHT_TREE_REVISION = 1;
export const LIGHT_TREE_NODE_BYTES = 64;
export const LIGHT_TREE_EMITTER_BYTES = 32;
export const LIGHT_TREE_MAX_LEAF_EMITTERS = 8;
// The kernel reads at most this many emitters of one leaf (`LTR_MAX_LEAF_EMITTERS` in light_tree.wgsl); only the distant leaf can hold more than 8.
export const LIGHT_TREE_KERNEL_MAX_LEAF_EMITTERS = 32;
export const LIGHT_TREE_MAX_EMITTERS = 4194304;
export const LIGHT_TREE_BUCKET_COUNT = 12;
export const LIGHT_TREE_MAX_DEPTH = 63;

// Node `emitter_count_and_kind` bits.
export const LIGHT_TREE_NODE_COUNT_MASK = 0xffff;
export const LIGHT_TREE_NODE_HAS_TRIANGLE = 1 << 16;
export const LIGHT_TREE_NODE_DISTANT = 1 << 17;
export const LIGHT_TREE_NODE_HAS_LIGHT = 1 << 18;

// Emitter `kind_and_depth` bits: bit 0 triangle, bit 1 distant, bits 8..15 depth.
export const LIGHT_TREE_EMITTER_TRIANGLE = 1;
export const LIGHT_TREE_EMITTER_DISTANT = 2;
export const LIGHT_TREE_EMITTER_DEPTH_SHIFT = 8;

const LIGHT_BYTES = 128;
const EMISSIVE_TRIANGLE_BYTES = 96;
const LIGHT_TYPE_POINT = 0;
const LIGHT_TYPE_SPOT = 1;
const LIGHT_TYPE_AREA_RECT = 2;
const LIGHT_TYPE_AREA_DISK = 3;
const LIGHT_TYPE_SUN = 4;
const LIGHT_TREE_LEAF_MARKER = -1;
const LEAF_FORCED_BALANCE_DEPTH = 24;
const NO_LEAF_INDEX = 0xffffffff;
const ANGLE_EPSILON = 5e-4;

const HALF_PI = Math.PI / 2;

function vectorLength(vector) {
  return Math.hypot(vector[0], vector[1], vector[2]);
}

function dotProduct(a, b) {
  return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
}

function normalizeOrZero(vector) {
  const length = vectorLength(vector);
  if (!(length > 1e-20)) {
    return [0, 0, 0];
  }
  return [vector[0] / length, vector[1] / length, vector[2] / length];
}

function safeArccosine(value) {
  return Math.acos(Math.min(1, Math.max(-1, value)));
}

function perpendicularTo(axis) {
  const helper = Math.abs(axis[0]) < 0.9 ? [1, 0, 0] : [0, 1, 0];
  const projected = [
    helper[0] - axis[0] * dotProduct(helper, axis),
    helper[1] - axis[1] * dotProduct(helper, axis),
    helper[2] - axis[2] * dotProduct(helper, axis),
  ];
  return normalizeOrZero(projected);
}

// ---- Orientation cone (Cycles OrientationBounds) --------------------------------------------------------------

function emptyCone() {
  return { axis: [0, 0, 0], thetaO: 0, thetaE: 0 };
}

function isEmptyCone(cone) {
  return cone.axis[0] === 0 && cone.axis[1] === 0 && cone.axis[2] === 0;
}

export function coneMeasure(cone) {
  if (isEmptyCone(cone)) {
    return 0;
  }
  const thetaW = Math.min(Math.PI, cone.thetaO + cone.thetaE);
  const cosThetaO = Math.cos(cone.thetaO);
  const sinThetaO = Math.sin(cone.thetaO);
  return (
    2 * Math.PI * (1 - cosThetaO) +
    HALF_PI *
      (2 * thetaW * sinThetaO - Math.cos(cone.thetaO - 2 * thetaW) - 2 * cone.thetaO * sinThetaO + cosThetaO)
  );
}

export function mergeCones(coneA, coneB) {
  if (isEmptyCone(coneA)) {
    return coneB;
  }
  if (isEmptyCone(coneB)) {
    return coneA;
  }
  const [wider, narrower] = coneB.thetaO > coneA.thetaO ? [coneB, coneA] : [coneA, coneB];
  const cosBetween = dotProduct(wider.axis, narrower.axis);
  const thetaD = safeArccosine(cosBetween);
  const thetaE = Math.max(wider.thetaE, narrower.thetaE);

  if (wider.thetaO + ANGLE_EPSILON >= Math.min(Math.PI, thetaD + narrower.thetaO)) {
    return { axis: wider.axis, thetaO: wider.thetaO, thetaE };
  }
  const oppositeAxes = cosBetween < -0.9995;
  // Cycles keeps the midpoint theta_o for opposite axes, but an orthogonal axis then misses part of the wider cone.
  // A quarter turn plus the larger theta_o (the narrower one pushed out by its offset from exactly opposite)
  // contains both, so the node cone stays a true bound.
  const thetaO = oppositeAxes
    ? Math.max(
        (thetaD + wider.thetaO + narrower.thetaO) * 0.5,
        HALF_PI + Math.max(wider.thetaO, narrower.thetaO + Math.PI - thetaD)
      )
    : (thetaD + wider.thetaO + narrower.thetaO) * 0.5;
  if (thetaO >= Math.PI) {
    return { axis: wider.axis, thetaO: Math.PI, thetaE };
  }
  let axis;
  if (oppositeAxes) {
    axis = perpendicularTo(wider.axis);
  } else {
    const thetaR = thetaO - wider.thetaO;
    const ortho = normalizeOrZero([
      narrower.axis[0] - wider.axis[0] * cosBetween,
      narrower.axis[1] - wider.axis[1] * cosBetween,
      narrower.axis[2] - wider.axis[2] * cosBetween,
    ]);
    const cosR = Math.cos(thetaR);
    const sinR = Math.sin(thetaR);
    axis = [
      wider.axis[0] * cosR + ortho[0] * sinR,
      wider.axis[1] * cosR + ortho[1] * sinR,
      wider.axis[2] * cosR + ortho[2] * sinR,
    ];
  }
  return { axis, thetaO, thetaE };
}

// ---- Measure: bounding box, cone and energy (Cycles LightTreeMeasure) ----------------------------------------

function emptyMeasure() {
  return {
    boxMin: [Infinity, Infinity, Infinity],
    boxMax: [-Infinity, -Infinity, -Infinity],
    cone: emptyCone(),
    energy: 0,
  };
}

function addMeasure(target, other) {
  if (other.energy === 0) {
    return;
  }
  for (let axis = 0; axis < 3; axis++) {
    target.boxMin[axis] = Math.min(target.boxMin[axis], other.boxMin[axis]);
    target.boxMax[axis] = Math.max(target.boxMax[axis], other.boxMax[axis]);
  }
  target.cone = mergeCones(target.cone, other.cone);
  target.energy += other.energy;
}

function copyMeasure(measure) {
  return {
    boxMin: measure.boxMin.slice(),
    boxMax: measure.boxMax.slice(),
    cone: measure.cone,
    energy: measure.energy,
  };
}

function sumMeasures(a, b) {
  const sum = copyMeasure(a);
  addMeasure(sum, b);
  return sum;
}

// energy * box area * cone measure, Eq. 2 of the many-light paper.
export function measureCost(measure) {
  if (measure.energy === 0) {
    return 0;
  }
  const sizeX = measure.boxMax[0] - measure.boxMin[0];
  const sizeY = measure.boxMax[1] - measure.boxMin[1];
  const sizeZ = measure.boxMax[2] - measure.boxMin[2];
  const area = 2 * (sizeX * sizeY + sizeY * sizeZ + sizeZ * sizeX);
  const areaMeasure = area === 0 ? Math.hypot(sizeX, sizeY, sizeZ) : area;
  return measure.energy * areaMeasure * coneMeasure(measure.cone);
}

// ---- Emitters read from the packed FORMAT-v2 tables ----------------------------------------------------------

function assertFiniteNumbers(values, label, index) {
  for (const value of values) {
    if (!Number.isFinite(value)) {
      throw new Error(`buildLightTree: ${label} ${index} has a non-finite value; pass finite positions, sizes and radiance.`);
    }
  }
}

function averageAbsolute(red, green, blue) {
  return (Math.abs(red) + Math.abs(green) + Math.abs(blue)) / 3;
}

function lightEmitter(view, index, unifiedIndex) {
  const floats = new Float32Array(view.buffer, view.byteOffset + index * LIGHT_BYTES, LIGHT_BYTES / 4);
  const words = new Uint32Array(view.buffer, view.byteOffset + index * LIGHT_BYTES, LIGHT_BYTES / 4);
  // Words 3 and 7 are integers, 26 and 27 hold an index and a leaf; only the float fields can be non-finite.
  assertFiniteNumbers(
    [...floats.subarray(0, 3), ...floats.subarray(4, 7), ...floats.subarray(8, 26)],
    'analytic light',
    index
  );
  const lightType = words[3];
  const position = [floats[0], floats[1], floats[2]];
  const direction = normalizeOrZero([floats[8], floats[9], floats[10]]);
  const radius = floats[11];
  const averageRadiance = averageAbsolute(floats[4], floats[5], floats[6]);
  const areaOrSolidAngle = floats[24];
  const emitter = {
    unifiedIndex,
    isTriangle: false,
    recordIndex: index,
    isDistant: lightType === LIGHT_TYPE_SUN,
    maskLow: words[30],
    boxMin: [0, 0, 0],
    boxMax: [0, 0, 0],
    centroid: position,
    cone: emptyCone(),
    energy: 0,
  };
  const axis = direction[0] === 0 && direction[1] === 0 && direction[2] === 0 ? [0, 0, -1] : direction;
  if (lightType === LIGHT_TYPE_POINT || lightType === LIGHT_TYPE_SPOT) {
    const extent = Math.max(0, radius);
    emitter.boxMin = position.map((value) => value - extent);
    emitter.boxMax = position.map((value) => value + extent);
    emitter.energy = radius > 0 ? averageRadiance * Math.PI * radius * radius : averageRadiance;
    if (lightType === LIGHT_TYPE_POINT) {
      emitter.cone = { axis, thetaO: Math.PI, thetaE: HALF_PI };
    } else {
      emitter.cone = { axis, thetaO: 0, thetaE: Math.min(HALF_PI, safeArccosine(floats[20])) };
    }
  } else if (lightType === LIGHT_TYPE_AREA_RECT || lightType === LIGHT_TYPE_AREA_DISK) {
    const halfU = [0.5 * floats[15] * floats[12], 0.5 * floats[15] * floats[13], 0.5 * floats[15] * floats[14]];
    const halfV = [0.5 * floats[19] * floats[16], 0.5 * floats[19] * floats[17], 0.5 * floats[19] * floats[18]];
    for (let axisIndex = 0; axisIndex < 3; axisIndex++) {
      const spread = Math.abs(halfU[axisIndex]) + Math.abs(halfV[axisIndex]);
      emitter.boxMin[axisIndex] = position[axisIndex] - spread;
      emitter.boxMax[axisIndex] = position[axisIndex] + spread;
    }
    emitter.energy = averageRadiance * areaOrSolidAngle;
    const tanHalfSpread = floats[22];
    const thetaE = tanHalfSpread > 0 ? Math.min(HALF_PI, Math.atan(tanHalfSpread)) : HALF_PI;
    emitter.cone = { axis, thetaO: 0, thetaE };
  } else if (lightType === LIGHT_TYPE_SUN) {
    emitter.energy = averageRadiance * areaOrSolidAngle;
    emitter.cone = { axis, thetaO: 0, thetaE: safeArccosine(floats[20]) };
  } else {
    throw new Error(`buildLightTree: analytic light ${index} has unknown light_type ${lightType}; pass 0 to 4.`);
  }
  return emitter;
}

// The kernel samples emissive triangles on both sides (abs of the cosine), so the cone is the double-sided
// one of Cycles: any vector in the triangle plane with theta_o = pi/2.
function triangleEmitter(view, index, unifiedIndex) {
  const floats = new Float32Array(view.buffer, view.byteOffset + index * EMISSIVE_TRIANGLE_BYTES, EMISSIVE_TRIANGLE_BYTES / 4);
  const words = new Uint32Array(view.buffer, view.byteOffset + index * EMISSIVE_TRIANGLE_BYTES, EMISSIVE_TRIANGLE_BYTES / 4);
  // Words 7, 11 and 15 are u32 indices; only the float fields are checked.
  assertFiniteNumbers([...floats.subarray(0, 7), ...floats.subarray(8, 11), ...floats.subarray(12, 15), ...floats.subarray(16, 20)], 'emissive triangle', index);
  const origin = [floats[0], floats[1], floats[2]];
  const edgeOne = [floats[4], floats[5], floats[6]];
  const edgeTwo = [floats[8], floats[9], floats[10]];
  const vertices = [
    origin,
    origin.map((value, axis) => value + edgeOne[axis]),
    origin.map((value, axis) => value + edgeTwo[axis]),
  ];
  const emitter = {
    unifiedIndex,
    isTriangle: true,
    recordIndex: index,
    isDistant: false,
    maskLow: words[22],
    boxMin: [0, 1, 2].map((axis) => Math.min(vertices[0][axis], vertices[1][axis], vertices[2][axis])),
    boxMax: [0, 1, 2].map((axis) => Math.max(vertices[0][axis], vertices[1][axis], vertices[2][axis])),
    centroid: [0, 1, 2].map((axis) => (vertices[0][axis] + vertices[1][axis] + vertices[2][axis]) / 3),
    cone: emptyCone(),
    energy: floats[3] * averageAbsolute(floats[16], floats[17], floats[18]),
  };
  const inPlane = normalizeOrZero(edgeOne.map((value) => -value));
  const axis = inPlane[0] === 0 && inPlane[1] === 0 && inPlane[2] === 0 ? [1, 0, 0] : inPlane;
  emitter.cone = { axis, thetaO: HALF_PI, thetaE: HALF_PI };
  return emitter;
}

function emitterMeasure(emitter) {
  return {
    boxMin: emitter.boxMin.slice(),
    boxMax: emitter.boxMax.slice(),
    cone: emitter.cone,
    energy: emitter.energy,
  };
}

// ---- Build (Cycles LightTree::recursive_build and should_split) ----------------------------------------------

function createBuckets() {
  return Array.from({ length: LIGHT_TREE_BUCKET_COUNT }, () => ({ measure: emptyMeasure(), count: 0, maskOr: 0 }));
}

function addToBucket(bucket, emitter) {
  addMeasure(bucket.measure, emitterMeasure(emitter));
  bucket.count += 1;
  bucket.maskOr = (bucket.maskOr | emitter.maskLow) >>> 0;
}

function sumBuckets(a, b) {
  return {
    measure: sumMeasures(a.measure, b.measure),
    count: a.count + b.count,
    maskOr: (a.maskOr | b.maskOr) >>> 0,
  };
}

function fillBuckets(order, start, end, dimension, centroidMin, centroidSize) {
  const buckets = createBuckets();
  if (centroidSize[dimension] === 0) {
    for (let position = start; position < end; position++) {
      addToBucket(buckets[0], order[position]);
    }
    return buckets;
  }
  const inverseExtent = 1 / centroidSize[dimension];
  for (let position = start; position < end; position++) {
    const emitter = order[position];
    const rawIndex = Math.floor(
      LIGHT_TREE_BUCKET_COUNT * (emitter.centroid[dimension] - centroidMin[dimension]) * inverseExtent
    );
    const bucketIndex = Math.min(LIGHT_TREE_BUCKET_COUNT - 1, Math.max(0, rawIndex));
    addToBucket(buckets[bucketIndex], emitter);
  }
  return buckets;
}

function cumulativeFromLeft(buckets) {
  const result = [buckets[0]];
  for (let index = 1; index < LIGHT_TREE_BUCKET_COUNT - 1; index++) {
    result.push(sumBuckets(result[index - 1], buckets[index]));
  }
  return result;
}

function cumulativeFromRight(buckets) {
  const result = new Array(LIGHT_TREE_BUCKET_COUNT - 1);
  result[LIGHT_TREE_BUCKET_COUNT - 2] = buckets[LIGHT_TREE_BUCKET_COUNT - 1];
  for (let index = LIGHT_TREE_BUCKET_COUNT - 3; index >= 0; index--) {
    result[index] = sumBuckets(result[index + 1], buckets[index + 1]);
  }
  return result;
}

function centroidBounds(order, start, end) {
  const centroidMin = [Infinity, Infinity, Infinity];
  const centroidMax = [-Infinity, -Infinity, -Infinity];
  for (let position = start; position < end; position++) {
    for (let axis = 0; axis < 3; axis++) {
      centroidMin[axis] = Math.min(centroidMin[axis], order[position].centroid[axis]);
      centroidMax[axis] = Math.max(centroidMax[axis], order[position].centroid[axis]);
    }
  }
  return { centroidMin, centroidSize: centroidMax.map((value, axis) => value - centroidMin[axis]) };
}

// Returns { shouldSplit, middle, splitDimension, measure, maskOr }. Mirrors the quirks of the Cycles loop: the node
// measure is summed from the buckets of dimension 0, and the total cost is only set when the centroid box has an
// extent along x, so a set of emitters on one x plane only splits by count once it has more than a leaf's worth.
function chooseSplit(order, start, end) {
  const emitterCount = end - start;
  if (emitterCount < 2) {
    const only = order[start];
    return {
      shouldSplit: false,
      middle: start,
      splitDimension: -1,
      measure: emitterMeasure(only),
      maskOr: only.maskLow,
    };
  }
  let middle = (start + end) >> 1;
  const { centroidMin, centroidSize } = centroidBounds(order, start, end);
  const maxExtent = Math.max(centroidSize[0], centroidSize[1], centroidSize[2], 0);
  const allExtentsZero = centroidSize[0] === 0 && centroidSize[1] === 0 && centroidSize[2] === 0;

  let totalCost = 0;
  let minimumCost = Number.MAX_VALUE;
  let splitDimension = -1;
  let nodeMeasure = emptyMeasure();
  let nodeMaskOr = 0;

  for (let dimension = 0; dimension < 3; dimension++) {
    if (centroidSize[dimension] === 0 && dimension !== 0) {
      continue;
    }
    const buckets = fillBuckets(order, start, end, dimension, centroidMin, centroidSize);
    const leftBuckets = cumulativeFromLeft(buckets);
    if (dimension === 0) {
      const whole = sumBuckets(leftBuckets[LIGHT_TREE_BUCKET_COUNT - 2], buckets[LIGHT_TREE_BUCKET_COUNT - 1]);
      nodeMeasure = whole.measure;
      nodeMaskOr = whole.maskOr;
      if (allExtentsZero) {
        break;
      }
      if (centroidSize[0] === 0) {
        continue;
      }
      totalCost = measureCost(nodeMeasure);
      if (totalCost === 0) {
        break;
      }
    }
    const rightBuckets = cumulativeFromRight(buckets);
    const inverseExtent = centroidSize[dimension] === 0 ? Number.MAX_VALUE : 1 / centroidSize[dimension];
    const regularization = maxExtent * inverseExtent;
    for (let split = 0; split < LIGHT_TREE_BUCKET_COUNT - 1; split++) {
      const cost = regularization * (measureCost(leftBuckets[split].measure) + measureCost(rightBuckets[split].measure));
      if (cost < totalCost && cost < minimumCost) {
        minimumCost = cost;
        splitDimension = dimension;
        middle = start + leftBuckets[split].count;
      }
    }
  }
  return {
    shouldSplit: minimumCost < totalCost || emitterCount > LIGHT_TREE_MAX_LEAF_EMITTERS,
    middle,
    splitDimension,
    measure: nodeMeasure,
    maskOr: nodeMaskOr,
  };
}

function partitionByCentroid(order, start, end, dimension) {
  const slice = order.slice(start, end);
  slice.sort((a, b) => a.centroid[dimension] - b.centroid[dimension] || a.unifiedIndex - b.unifiedIndex);
  for (let offset = 0; offset < slice.length; offset++) {
    order[start + offset] = slice[offset];
  }
}

function sortLeafByIndex(order, start, end) {
  const slice = order.slice(start, end);
  slice.sort((a, b) => a.unifiedIndex - b.unifiedIndex);
  for (let offset = 0; offset < slice.length; offset++) {
    order[start + offset] = slice[offset];
  }
}

function trailBit(depth, trailLow, trailHigh) {
  if (depth < 32) {
    return [(trailLow | (1 << depth)) >>> 0, trailHigh];
  }
  return [trailLow, (trailHigh | (1 << (depth - 32))) >>> 0];
}

function summarizeLeafFlags(order, start, end) {
  let flags = 0;
  for (let position = start; position < end; position++) {
    flags |= order[position].isTriangle ? LIGHT_TREE_NODE_HAS_TRIANGLE : LIGHT_TREE_NODE_HAS_LIGHT;
  }
  return flags;
}

function buildSubtree(state, start, end, depth, trailLow, trailHigh) {
  const nodeIndex = state.nodes.length;
  const node = { measure: null, leftChild: LIGHT_TREE_LEAF_MARKER, rightOrFirst: 0, countAndKind: 0, maskOr: 0 };
  state.nodes.push(node);

  const decision = chooseSplit(state.order, start, end);
  node.measure = decision.measure;
  node.maskOr = decision.maskOr;

  const forceBalance = depth >= LEAF_FORCED_BALANCE_DEPTH && end - start >= 2;
  let shouldSplit = decision.shouldSplit || (forceBalance && end - start > LIGHT_TREE_MAX_LEAF_EMITTERS);
  let middle = decision.middle;
  if (shouldSplit && forceBalance) {
    middle = (start + end) >> 1;
  } else if (shouldSplit && decision.splitDimension !== -1) {
    partitionByCentroid(state.order, start, end, decision.splitDimension);
  }
  if (shouldSplit && (middle <= start || middle >= end)) {
    middle = (start + end) >> 1;
  }
  if (depth > LIGHT_TREE_MAX_DEPTH) {
    shouldSplit = false;
  }

  if (!shouldSplit) {
    sortLeafByIndex(state.order, start, end);
    const leafCount = end - start;
    if (leafCount > LIGHT_TREE_NODE_COUNT_MASK) {
      throw new Error(`buildLightTree: a leaf holds ${leafCount} emitters, more than ${LIGHT_TREE_NODE_COUNT_MASK}.`);
    }
    node.rightOrFirst = start;
    node.countAndKind = (leafCount | summarizeLeafFlags(state.order, start, end)) >>> 0;
    for (let position = start; position < end; position++) {
      const emitter = state.order[position];
      emitter.leafIndex = nodeIndex;
      emitter.depth = depth;
      emitter.trailLow = trailLow;
      emitter.trailHigh = trailHigh;
    }
    return nodeIndex;
  }

  const leftIndex = buildSubtree(state, start, middle, depth + 1, trailLow, trailHigh);
  const [rightLow, rightHigh] = trailBit(depth, trailLow, trailHigh);
  const rightIndex = buildSubtree(state, middle, end, depth + 1, rightLow, rightHigh);
  node.leftChild = leftIndex;
  node.rightOrFirst = rightIndex;
  node.countAndKind = (state.nodes[leftIndex].countAndKind | state.nodes[rightIndex].countAndKind) & ~LIGHT_TREE_NODE_COUNT_MASK;
  node.countAndKind >>>= 0;
  node.measure = sumMeasures(state.nodes[leftIndex].measure, state.nodes[rightIndex].measure);
  node.maskOr = (state.nodes[leftIndex].maskOr | state.nodes[rightIndex].maskOr) >>> 0;
  return nodeIndex;
}

function buildDistantLeaf(state, start, end, depth, trailLow, trailHigh) {
  const nodeIndex = state.nodes.length;
  const measure = emptyMeasure();
  let maskOr = 0;
  for (let position = start; position < end; position++) {
    addMeasure(measure, emitterMeasure(state.order[position]));
    maskOr = (maskOr | state.order[position].maskLow) >>> 0;
  }
  sortLeafByIndex(state.order, start, end);
  for (let position = start; position < end; position++) {
    const emitter = state.order[position];
    emitter.leafIndex = nodeIndex;
    emitter.depth = depth;
    emitter.trailLow = trailLow;
    emitter.trailHigh = trailHigh;
  }
  const count = end - start;
  if (count > LIGHT_TREE_KERNEL_MAX_LEAF_EMITTERS) {
    throw new Error(
      `buildLightTree: ${count} distant lights exceed the ${LIGHT_TREE_KERNEL_MAX_LEAF_EMITTERS} the kernel reads from one leaf. ` +
        `Pass at most ${LIGHT_TREE_KERNEL_MAX_LEAF_EMITTERS} sun or distant lights, or merge some of them.`
    );
  }
  state.nodes.push({
    measure,
    leftChild: LIGHT_TREE_LEAF_MARKER,
    rightOrFirst: start,
    countAndKind: (count | LIGHT_TREE_NODE_DISTANT | LIGHT_TREE_NODE_HAS_LIGHT) >>> 0,
    maskOr,
  });
  return nodeIndex;
}

// ---- Serialization ------------------------------------------------------------------------------------------

function writeNode(floats, words, ints, node) {
  const { measure } = node;
  const hasBox = measure.energy > 0 && measure.boxMin[0] <= measure.boxMax[0];
  const boxMin = hasBox ? measure.boxMin : [0, 0, 0];
  const boxMax = hasBox ? measure.boxMax : [0, 0, 0];
  const cone = measure.energy > 0 ? measure.cone : emptyCone();
  floats[0] = boxMin[0];
  floats[1] = boxMin[1];
  floats[2] = boxMin[2];
  floats[3] = measure.energy;
  floats[4] = boxMax[0];
  floats[5] = boxMax[1];
  floats[6] = boxMax[2];
  floats[7] = cone.thetaO;
  floats[8] = cone.axis[0];
  floats[9] = cone.axis[1];
  floats[10] = cone.axis[2];
  floats[11] = cone.thetaE;
  ints[12] = node.leftChild;
  words[13] = node.rightOrFirst;
  words[14] = node.countAndKind;
  words[15] = node.maskOr;
}

function serializeNodes(nodes) {
  const bytes = new Uint8Array(Math.max(1, nodes.length) * LIGHT_TREE_NODE_BYTES);
  for (let index = 0; index < nodes.length; index++) {
    const offset = index * LIGHT_TREE_NODE_BYTES;
    writeNode(
      new Float32Array(bytes.buffer, offset, 16),
      new Uint32Array(bytes.buffer, offset, 16),
      new Int32Array(bytes.buffer, offset, 16),
      nodes[index]
    );
  }
  return bytes;
}

function serializeEmitters(order) {
  const bytes = new Uint8Array(Math.max(1, order.length) * LIGHT_TREE_EMITTER_BYTES);
  for (let slot = 0; slot < order.length; slot++) {
    const emitter = order[slot];
    const offset = slot * LIGHT_TREE_EMITTER_BYTES;
    const floats = new Float32Array(bytes.buffer, offset, 8);
    const words = new Uint32Array(bytes.buffer, offset, 8);
    floats[0] = emitter.energy;
    floats[1] = emitter.cone.thetaO;
    floats[2] = emitter.cone.thetaE;
    words[3] =
      ((emitter.isTriangle ? LIGHT_TREE_EMITTER_TRIANGLE : 0) |
        (emitter.isDistant ? LIGHT_TREE_EMITTER_DISTANT : 0) |
        (emitter.depth << LIGHT_TREE_EMITTER_DEPTH_SHIFT)) >>>
      0;
    words[4] = emitter.recordIndex;
    words[5] = emitter.leafIndex;
    words[6] = emitter.trailLow;
    words[7] = emitter.trailHigh;
  }
  return bytes;
}

function assertCount(label, count) {
  if (!Number.isInteger(count) || count < 0) {
    throw new Error(`buildLightTree: ${label} count must be a non-negative integer, got ${count}.`);
  }
}

function validateRecordTable(label, bytes, count, stride) {
  if (!(bytes instanceof Uint8Array)) {
    throw new Error(`buildLightTree: ${label} must be a Uint8Array of FORMAT-v2 records.`);
  }
  if (bytes.byteLength < count * stride) {
    throw new Error(`buildLightTree: ${label} holds ${bytes.byteLength} bytes, fewer than ${count} records of ${stride} bytes.`);
  }
}

/**
 * Builds the light tree over the packed analytic lights and emissive triangles.
 *
 * @param {Uint8Array} lights packed `LightRecord` table (FORMAT-v2 section 6)
 * @param {number} lightCount number of analytic lights
 * @param {Uint8Array} emissiveTriangles packed `EmissiveTriangleRecord` table (section 5)
 * @param {number} emissiveTriangleCount number of emissive triangles
 * @returns {{nodes: Uint8Array, nodeCount: number, emitters: Uint8Array, emitterCount: number,
 *   lightToTree: Uint32Array, lightLeafIndices: Uint32Array}} `lightToTree[i]` is the emitter slot of unified
 *   emitter `i` (analytic lights first, then emissive triangles); `lightLeafIndices[i]` the leaf node of light `i`.
 */
export function buildLightTree(lights, lightCount, emissiveTriangles, emissiveTriangleCount) {
  assertCount('lights', lightCount);
  assertCount('emissiveTriangles', emissiveTriangleCount);
  const totalEmitters = lightCount + emissiveTriangleCount;
  if (totalEmitters > LIGHT_TREE_MAX_EMITTERS) {
    throw new Error(
      `buildLightTree: ${totalEmitters} emitters exceed the limit of ${LIGHT_TREE_MAX_EMITTERS}; merge emissive triangles or drop lights.`
    );
  }
  validateRecordTable('lights', lights, lightCount, LIGHT_BYTES);
  validateRecordTable('emissiveTriangles', emissiveTriangles, emissiveTriangleCount, EMISSIVE_TRIANGLE_BYTES);
  if (totalEmitters === 0) {
    return {
      nodes: new Uint8Array(LIGHT_TREE_NODE_BYTES),
      nodeCount: 0,
      emitters: new Uint8Array(LIGHT_TREE_EMITTER_BYTES),
      emitterCount: 0,
      lightToTree: new Uint32Array(1),
      lightLeafIndices: new Uint32Array(0),
    };
  }

  const localEmitters = [];
  const distantEmitters = [];
  for (let index = 0; index < lightCount; index++) {
    const emitter = lightEmitter(lights, index, index);
    (emitter.isDistant ? distantEmitters : localEmitters).push(emitter);
  }
  for (let index = 0; index < emissiveTriangleCount; index++) {
    localEmitters.push(triangleEmitter(emissiveTriangles, index, lightCount + index));
  }

  const state = { nodes: [], order: localEmitters.concat(distantEmitters) };
  const localCount = localEmitters.length;
  if (distantEmitters.length === 0) {
    buildSubtree(state, 0, localCount, 0, 0, 0);
  } else if (localCount === 0) {
    buildDistantLeaf(state, 0, distantEmitters.length, 0, 0, 0);
  } else {
    const rootIndex = state.nodes.length;
    const root = { measure: null, leftChild: 0, rightOrFirst: 0, countAndKind: 0, maskOr: 0 };
    state.nodes.push(root);
    const leftIndex = buildSubtree(state, 0, localCount, 1, 0, 0);
    const rightIndex = buildDistantLeaf(state, localCount, state.order.length, 1, 1, 0);
    root.leftChild = leftIndex;
    root.rightOrFirst = rightIndex;
    root.measure = sumMeasures(state.nodes[leftIndex].measure, state.nodes[rightIndex].measure);
    root.countAndKind =
      ((state.nodes[leftIndex].countAndKind | state.nodes[rightIndex].countAndKind) & ~LIGHT_TREE_NODE_COUNT_MASK) >>> 0;
    root.maskOr = (state.nodes[leftIndex].maskOr | state.nodes[rightIndex].maskOr) >>> 0;
    if (rootIndex !== 0) {
      throw new Error('buildLightTree: the root node must be node 0.');
    }
  }

  const lightToTree = new Uint32Array(totalEmitters);
  const lightLeafIndices = new Uint32Array(lightCount).fill(NO_LEAF_INDEX);
  for (let slot = 0; slot < state.order.length; slot++) {
    const emitter = state.order[slot];
    lightToTree[emitter.unifiedIndex] = slot;
    if (!emitter.isTriangle) {
      lightLeafIndices[emitter.recordIndex] = emitter.leafIndex;
    }
  }
  return {
    nodes: serializeNodes(state.nodes),
    nodeCount: state.nodes.length,
    emitters: serializeEmitters(state.order),
    emitterCount: state.order.length,
    lightToTree,
    lightLeafIndices,
  };
}