Skip to content

3D engine that AI agents drive

19.9 KB
Raw Blame
// GPU crowds (issue 323): one character and one clip draw as a few instanced batches, however many people there are.
//
// The clip's joint matrices are baked once into a table with one row of matrices per frame. Each instance carries
// only two frame offsets and a blend weight (in its assembly offset, which a crowd part does not otherwise use), and
// the vertex shader reads the matrices of its own clip time. Every instance of a material therefore shares a batch,
// and the batch can be culled and drawn in levels like any rigid part.
//
// The pose of an instance is a pure function of its clip time (crowdFrameBlend), so a frame at a seek time equals
// the same frame reached by playing.
import { mat4 } from 'gl-matrix';
import { installCrowdShader } from './shaders.js';
import { validateSkinGeometry } from './skinning.js';

const FLOATS_PER_MATRIX = 16;
const TEXELS_PER_MATRIX = 4;
const DEFAULT_FRAME_RATE = 30;
const MAXIMUM_PALETTE_FRAMES = 7200; // 2 minutes at 60 fps
const DEFAULT_LEVEL_CELLS = Object.freeze([0.02, 0.05]);
const JOINT_STRIDE = 4096;
const WEIGHT_STEPS = 4095;

// Each vertex carries four packed influences in the colour attribute (location 14): joint * 4096 + weight * 4095, exact in a float.
// The frame blend is in assemblyOffset: x and y are the texel offsets of the two frames, z the blend between them.
installCrowdShader(`
uniform float crowdEnabled;
mat4 crowdJoint(int frameTexel, int joint) {
  int texel = frameTexel + joint * 4;
  return mat4(skinTexel(jointPalette, texel), skinTexel(jointPalette, texel + 1),
    skinTexel(jointPalette, texel + 2), skinTexel(jointPalette, texel + 3));
}
mat4 crowdInfluence(float packedInfluence) {
  float joint = floor(packedInfluence / 4096.0);
  float weight = (packedInfluence - joint * 4096.0) / 4095.0;
  int firstFrame = int(assemblyOffset.x + 0.5);
  int secondFrame = int(assemblyOffset.y + 0.5);
  int jointIndex = int(joint + 0.5);
  return (crowdJoint(firstFrame, jointIndex) * (1.0 - assemblyOffset.z) + crowdJoint(secondFrame, jointIndex) * assemblyOffset.z) * weight;
}
mat4 crowdTransform() {
  return crowdInfluence(vertexColor.x) + crowdInfluence(vertexColor.y) + crowdInfluence(vertexColor.z) + crowdInfluence(vertexColor.w);
}`);

/**
 * Merge the parts of a character into crowd geometries, one per material. A rigid part becomes one joint that
 * follows its matrix; a skinned part keeps its joints, each premultiplied by the part's matrix. UVs are kept, so
 * materials with maps work. Parts with morph targets are merged with their weights ignored, unless `morphs` is true:
 * then each keeps its own geometry and draws with the weights it has when the rig is made (one set for the whole crowd,
 * and no levels or culling for that part). Each part is { name, geometry, matrix, material, skin?, morph? } as an imported asset lists them.
 */
export function createCrowdRig(sourceParts, { morphs = false } = {}) {
  if (!Array.isArray(sourceParts) || sourceParts.length === 0) throw new TypeError('A crowd rig needs a list of parts.');
  const jointOffsets = [];
  let jointCount = 0;
  for (const part of sourceParts) {
    if (!part.geometry?.positions || !part.geometry.indices || !part.material) throw new TypeError(`A crowd part needs a geometry and a material: ${part.name}`);
    if (part.skin && !part.geometry.skinIndices) throw new TypeError(`A skinned crowd part needs skin indices and weights: ${part.name}`);
    if (part.skin) validateCrowdSkin(part);
    jointOffsets.push(jointCount);
    jointCount += part.skin ? part.skin.jointMatrices.length / FLOATS_PER_MATRIX : 1;
  }
  if (jointCount > JOINT_STRIDE) throw new RangeError(`A crowd rig holds at most ${JOINT_STRIDE} joints; this one has ${jointCount}.`);
  const groups = new Map();
  const morphedParts = [];
  sourceParts.forEach((part, index) => {
    if (morphs && part.morph && part.geometry.morphTargets) {
      morphedParts.push(index);
      return;
    }
    if (!groups.has(part.material)) groups.set(part.material, []);
    groups.get(part.material).push(index);
  });
  const scratch = mat4.create();
  const entryOf = index => ({ part: sourceParts[index], jointOffset: jointOffsets[index] });
  const parts = [...groups].map(([material, indices]) => ({
    name: sourceParts[indices[0]].name,
    material,
    geometry: mergeCrowdGeometry(indices.map(entryOf)),
  }));
  for (const index of morphedParts) {
    const part = sourceParts[index];
    const geometry = mergeCrowdGeometry([entryOf(index)]);
    geometry.morphTargets = part.geometry.morphTargets;
    parts.push({ name: part.name, material: part.material, geometry, morph: { weights: new Float32Array(part.morph.weights) } });
  }
  return {
    jointCount,
    parts,
    /** Write the current joint matrices (mesh space, ready to skin with) of every joint into `output`. */
    readJointMatrices(output) {
      sourceParts.forEach((part, index) => {
        const offset = jointOffsets[index] * FLOATS_PER_MATRIX;
        if (!part.skin) {
          output.set(part.matrix, offset);
          return;
        }
        for (let joint = 0; joint < part.skin.jointMatrices.length / FLOATS_PER_MATRIX; joint++) {
          mat4.multiply(scratch, part.matrix, part.skin.jointMatrices.subarray(joint * FLOATS_PER_MATRIX, (joint + 1) * FLOATS_PER_MATRIX));
          output.set(scratch, offset + joint * FLOATS_PER_MATRIX);
        }
      });
      return output;
    },
  };
}

// A joint index past the part's own joints would read another part's joint, and weights that total zero pack as NaN.
function validateCrowdSkin(part) {
  try {
    validateSkinGeometry(part.geometry, part.skin);
  } catch (error) {
    throw new RangeError(`Crowd part ${part.name}: ${error.message}`);
  }
}

function mergeCrowdGeometry(entries) {
  const vertexCount = entries.reduce((total, { part }) => total + part.geometry.positions.length / 3, 0);
  const indexCount = entries.reduce((total, { part }) => total + part.geometry.indices.length, 0);
  const merged = {
    positions: new Float32Array(vertexCount * 3),
    normals: new Float32Array(vertexCount * 3),
    indices: new Uint32Array(indexCount),
    crowdJoints: new Float32Array(vertexCount * 4),
    crowdWeights: new Float32Array(vertexCount * 4),
  };
  if (entries.some(({ part }) => part.geometry.uvs)) merged.uvs = new Float32Array(vertexCount * 2);
  let vertexStart = 0;
  let indexStart = 0;
  for (const { part, jointOffset } of entries) {
    const geometry = part.geometry;
    const count = geometry.positions.length / 3;
    merged.positions.set(geometry.positions, vertexStart * 3);
    merged.normals.set(geometry.normals, vertexStart * 3);
    if (geometry.uvs) merged.uvs.set(geometry.uvs, vertexStart * 2);
    for (let index = 0; index < geometry.indices.length; index++) merged.indices[indexStart + index] = geometry.indices[index] + vertexStart;
    for (let vertex = 0; vertex < count; vertex++) {
      const target = (vertexStart + vertex) * 4;
      if (!part.skin) {
        merged.crowdJoints[target] = jointOffset;
        merged.crowdWeights[target] = 1;
        continue;
      }
      let total = 0;
      for (let influence = 0; influence < 4; influence++) total += geometry.skinWeights[vertex * 4 + influence];
      for (let influence = 0; influence < 4; influence++) {
        merged.crowdJoints[target + influence] = geometry.skinIndices[vertex * 4 + influence] + jointOffset;
        merged.crowdWeights[target + influence] = Math.round(geometry.skinWeights[vertex * 4 + influence] / total * WEIGHT_STEPS) / WEIGHT_STEPS;
      }
    }
    vertexStart += count;
    indexStart += geometry.indices.length;
  }
  packCrowdInfluences(merged);
  return merged;
}

/** The attribute the renderer uploads: joint * 4096 + round(weight * 4095) for each of four influences. Weights are already whole steps. */
function packCrowdInfluences(geometry) {
  geometry.crowdPacked = new Float32Array(geometry.crowdJoints.length);
  for (let index = 0; index < geometry.crowdJoints.length; index++) {
    geometry.crowdPacked[index] = geometry.crowdJoints[index] * JOINT_STRIDE + Math.round(geometry.crowdWeights[index] * WEIGHT_STEPS);
  }
}

/** The position of one crowd vertex under a table of joint matrices at `frameOffset` (in matrices), the maths the shader runs. */
function skinCrowdVertex(geometry, vertex, matrices, frameOffset, output = [0, 0, 0]) {
  const x = geometry.positions[vertex * 3];
  const y = geometry.positions[vertex * 3 + 1];
  const z = geometry.positions[vertex * 3 + 2];
  output[0] = 0;
  output[1] = 0;
  output[2] = 0;
  for (let influence = 0; influence < 4; influence++) {
    const weight = geometry.crowdWeights[vertex * 4 + influence];
    if (weight <= 0) continue;
    const base = (frameOffset + geometry.crowdJoints[vertex * 4 + influence]) * FLOATS_PER_MATRIX;
    output[0] += weight * (matrices[base] * x + matrices[base + 4] * y + matrices[base + 8] * z + matrices[base + 12]);
    output[1] += weight * (matrices[base + 1] * x + matrices[base + 5] * y + matrices[base + 9] * z + matrices[base + 13]);
    output[2] += weight * (matrices[base + 2] * x + matrices[base + 6] * y + matrices[base + 10] * z + matrices[base + 14]);
  }
  return output;
}

/**
 * Bake a clip into a palette: the joint matrices of `frameCount` evenly spaced poses, plus a bounding sphere (in the
 * space of the instance matrix) that covers every vertex in every pose. `poseAt(seconds)` must pose the parts the
 * rig was made from, such as `(seconds) => pose.apply(seconds)`. A looping clip is baked without its end frame, so
 * playback wraps between the last frame and the first.
 */
export function bakeCrowdPalette(rig, poseAt, { duration, loop = true, frameRate = DEFAULT_FRAME_RATE } = {}) {
  if (!Number.isFinite(duration) || duration <= 0) throw new RangeError('Crowd duration must be positive.');
  if (!Number.isFinite(frameRate) || frameRate <= 0) throw new RangeError('Crowd frame rate must be positive.');
  const frameCount = Math.max(2, Math.round(duration * frameRate) + (loop ? 0 : 1));
  if (frameCount > MAXIMUM_PALETTE_FRAMES) {
    throw new RangeError(`Crowd palette would bake ${frameCount} frames (duration ${duration} s at ${frameRate} fps), over the limit of ${MAXIMUM_PALETTE_FRAMES}. Lower frameRate or use a shorter clip.`);
  }
  const frameStep = loop ? duration / frameCount : duration / (frameCount - 1);
  const matricesPerFrame = rig.jointCount * FLOATS_PER_MATRIX;
  const data = new Float32Array(frameCount * matricesPerFrame);
  for (let frame = 0; frame < frameCount; frame++) {
    poseAt(frame * frameStep);
    rig.readJointMatrices(data.subarray(frame * matricesPerFrame, (frame + 1) * matricesPerFrame));
  }
  const palette = { data, jointCount: rig.jointCount, frameCount, frameStep, duration, loop };
  palette.bounds = measureCrowdBounds(rig, palette);
  return palette;
}

function measureCrowdBounds(rig, palette) {
  const minimum = [Infinity, Infinity, Infinity];
  const maximum = [-Infinity, -Infinity, -Infinity];
  const point = [0, 0, 0];
  const points = [];
  for (const { geometry } of rig.parts) {
    for (let frame = 0; frame < palette.frameCount; frame++) {
      for (let vertex = 0; vertex < geometry.positions.length / 3; vertex++) {
        skinCrowdVertex(geometry, vertex, palette.data, frame * palette.jointCount, point);
        points.push(point[0], point[1], point[2]);
        for (let axis = 0; axis < 3; axis++) {
          minimum[axis] = Math.min(minimum[axis], point[axis]);
          maximum[axis] = Math.max(maximum[axis], point[axis]);
        }
      }
    }
  }
  const center = minimum.map((value, axis) => (value + maximum[axis]) / 2);
  let radiusSquared = 0;
  for (let index = 0; index < points.length; index += 3) {
    radiusSquared = Math.max(radiusSquared, (points[index] - center[0]) ** 2 + (points[index + 1] - center[1]) ** 2 + (points[index + 2] - center[2]) ** 2);
  }
  return Object.freeze({ center: Object.freeze(center), radius: Math.sqrt(radiusSquared) });
}

/** The two frames and the blend between them for a clip time: [firstTexel, secondTexel, blend], as the shader reads them. */
export function crowdFrameBlend(palette, seconds, output = [0, 0, 0]) {
  if (!Number.isFinite(seconds)) seconds = 0; // a frame never throws: a bad clip time shows the first frame
  const lastFrame = palette.frameCount - 1;
  let position;
  if (palette.loop) {
    const wrapped = seconds - Math.floor(seconds / palette.duration) * palette.duration;
    position = wrapped / palette.frameStep;
  } else {
    position = Math.min(Math.max(seconds, 0), palette.duration) / palette.frameStep;
  }
  let first = Math.floor(position);
  let blend = position - first;
  let second = first + 1;
  if (palette.loop) {
    first %= palette.frameCount;
    second %= palette.frameCount;
  } else if (first >= lastFrame) {
    first = lastFrame;
    second = lastFrame;
    blend = 0;
  }
  const texelsPerFrame = palette.jointCount * TEXELS_PER_MATRIX;
  output[0] = first * texelsPerFrame;
  output[1] = second * texelsPerFrame;
  output[2] = blend;
  return output;
}

/** The skinned position of one vertex of a rig geometry at a clip time, on the CPU. The shader computes the same value. */
export function crowdVertexAt(palette, geometry, vertex, seconds, output = [0, 0, 0]) {
  const blend = crowdFrameBlend(palette, seconds);
  const firstPoint = skinCrowdVertex(geometry, vertex, palette.data, blend[0] / TEXELS_PER_MATRIX);
  const secondPoint = skinCrowdVertex(geometry, vertex, palette.data, blend[1] / TEXELS_PER_MATRIX);
  for (let axis = 0; axis < 3; axis++) output[axis] = firstPoint[axis] * (1 - blend[2]) + secondPoint[axis] * blend[2];
  return output;
}

/**
 * Coarser levels of a crowd geometry for the renderer's `lods`: vertices that share a grid cell and a dominant joint
 * merge into one, which keeps that vertex's joints and weights, so every level skins with the same palette.
 * `cells` lists cell sizes as fractions of the geometry's largest extent; `error` is the largest distance a vertex moves.
 */
export function createCrowdLods(geometry, { cells = DEFAULT_LEVEL_CELLS } = {}) {
  const extent = largestExtent(geometry.positions);
  return [{ geometry, error: 0 }, ...cells.map((fraction) => {
    const cellSize = fraction * extent;
    return { geometry: clusterCrowdGeometry(geometry, cellSize), error: cellSize * Math.sqrt(3) / 2 };
  })];
}

function largestExtent(positions) {
  const minimum = [Infinity, Infinity, Infinity];
  const maximum = [-Infinity, -Infinity, -Infinity];
  for (let index = 0; index < positions.length; index += 3) {
    for (let axis = 0; axis < 3; axis++) {
      minimum[axis] = Math.min(minimum[axis], positions[index + axis]);
      maximum[axis] = Math.max(maximum[axis], positions[index + axis]);
    }
  }
  return Math.max(...maximum.map((value, axis) => value - minimum[axis]));
}

function clusterCrowdGeometry(geometry, cellSize) {
  const vertexCount = geometry.positions.length / 3;
  const clusterOfVertex = new Uint32Array(vertexCount);
  const clusterByKey = new Map();
  const representatives = [];
  for (let vertex = 0; vertex < vertexCount; vertex++) {
    let dominant = 0;
    for (let influence = 1; influence < 4; influence++) {
      if (geometry.crowdWeights[vertex * 4 + influence] > geometry.crowdWeights[vertex * 4 + dominant]) dominant = influence;
    }
    const key = [0, 1, 2].map(axis => Math.floor(geometry.positions[vertex * 3 + axis] / cellSize)).join(',') + `:${geometry.crowdJoints[vertex * 4 + dominant]}`;
    if (!clusterByKey.has(key)) {
      clusterByKey.set(key, representatives.length);
      representatives.push({ vertex, count: 0, position: [0, 0, 0], normal: [0, 0, 0], uv: [0, 0] });
    }
    const clusterIndex = clusterByKey.get(key);
    const cluster = representatives[clusterIndex];
    clusterOfVertex[vertex] = clusterIndex;
    cluster.count++;
    for (let axis = 0; axis < 3; axis++) {
      cluster.position[axis] += geometry.positions[vertex * 3 + axis];
      cluster.normal[axis] += geometry.normals[vertex * 3 + axis];
    }
    if (geometry.uvs) {
      cluster.uv[0] += geometry.uvs[vertex * 2];
      cluster.uv[1] += geometry.uvs[vertex * 2 + 1];
    }
  }
  const coarse = {
    positions: new Float32Array(representatives.length * 3),
    normals: new Float32Array(representatives.length * 3),
    ...(geometry.uvs ? { uvs: new Float32Array(representatives.length * 2) } : {}),
    crowdJoints: new Float32Array(representatives.length * 4),
    crowdWeights: new Float32Array(representatives.length * 4),
  };
  representatives.forEach((cluster, index) => {
    const length = Math.hypot(...cluster.normal) || 1;
    for (let axis = 0; axis < 3; axis++) {
      coarse.positions[index * 3 + axis] = cluster.position[axis] / cluster.count;
      coarse.normals[index * 3 + axis] = cluster.normal[axis] / length;
    }
    if (geometry.uvs) {
      coarse.uvs[index * 2] = cluster.uv[0] / cluster.count;
      coarse.uvs[index * 2 + 1] = cluster.uv[1] / cluster.count;
    }
    coarse.crowdJoints.set(geometry.crowdJoints.subarray(cluster.vertex * 4, cluster.vertex * 4 + 4), index * 4);
    coarse.crowdWeights.set(geometry.crowdWeights.subarray(cluster.vertex * 4, cluster.vertex * 4 + 4), index * 4);
  });
  const indices = [];
  for (let corner = 0; corner < geometry.indices.length; corner += 3) {
    const first = clusterOfVertex[geometry.indices[corner]];
    const second = clusterOfVertex[geometry.indices[corner + 1]];
    const third = clusterOfVertex[geometry.indices[corner + 2]];
    if (first !== second && second !== third && first !== third) indices.push(first, second, third);
  }
  coarse.indices = Uint32Array.from(indices);
  packCrowdInfluences(coarse);
  return coarse;
}

/**
 * The renderer parts of a crowd: one part per instance and material, all instances of a material sharing a geometry,
 * a palette and `lods`, so they draw as one batch per material and level. `instances` come from createCrowd (or any
 * list with a column-major `matrix`). Call `setTimes` with each instance's clip time, then `renderer.updateParts(parts)`.
 * `lods: false` turns the coarser levels off; `cells` sets their sizes. `farPose: { distance, rate }` makes an instance
 * more than `distance` from the eye passed to `setTimes` hold each pose for 1 / `rate` seconds. That is still a pure
 * function of the clip time and the eye, so a seek equals playing.
 */
export function createCrowdParts({ rig, palette, instances, lods = true, cells, farPose = null, name = 'crowd' }) {
  if (!instances?.length) throw new TypeError('A crowd needs a list of instances.');
  if (farPose && !(farPose.distance > 0 && farPose.rate > 0)) throw new RangeError('farPose needs a positive distance and rate.');
  const rigParts = rig.parts.map(part => ({ ...part, levels: lods && !part.morph ? createCrowdLods(part.geometry, { cells }) : null }));
  const blends = [];
  const parts = [];
  instances.forEach((instance, index) => {
    const blend = [0, 0, 0];
    blends.push(blend);
    for (const rigPart of rigParts) {
      parts.push({
        name: `${name}-${index}-${rigPart.name}`,
        geometry: rigPart.geometry,
        matrix: instance.matrix,
        material: rigPart.material,
        crowd: palette,
        assembly: { offset: blend, detailOffset: [0, 0, 0] },
        ...(rigPart.morph ? { morph: rigPart.morph } : {}),
        ...(rigPart.levels ? { lods: rigPart.levels } : {}),
      });
    }
  });
  return {
    parts,
    /** Set every instance's clip time: an array of seconds or `(index) => seconds`. `eye` is the camera position, used with `farPose`. */
    setTimes(times, eye = null) {
      blends.forEach((blend, index) => {
        let seconds = typeof times === 'function' ? times(index) : times[index];
        if (!Number.isFinite(seconds)) throw new RangeError(`setTimes instance ${index} needs finite seconds, got ${seconds}. Pass the clip time in seconds.`);
        if (farPose && eye) {
          const matrix = instances[index].matrix;
          if (Math.hypot(matrix[12] - eye[0], matrix[13] - eye[1], matrix[14] - eye[2]) > farPose.distance) {
            seconds = Math.floor(seconds * farPose.rate) / farPose.rate;
          }
        }
        crowdFrameBlend(palette, seconds, blend);
      });
    },
  };
}