Skip to content

armgit / 67.js

Public Imported from GitHub
0

3D engine that AI agents drive

3.9 KB
Raw Blame
// Surface nets on a regular grid of signed distances (negative inside): one vertex in each cell the surface crosses,
// one quad around each crossing grid edge. Shared by the voxel remesh and the sdf geometry.

const CELL_CORNERS = [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1]];
const CELL_EDGES = [[0, 1], [2, 3], [4, 5], [6, 7], [0, 2], [1, 3], [4, 6], [5, 7], [0, 4], [1, 5], [2, 6], [3, 7]];

/** One vertex per crossed cell, at the mean of the edge crossings. Returns the cell-to-vertex map and positions. */
export function placeCellVertices(distances, grid, origin) {
  const [pointsX, pointsY, pointsZ] = grid.points;
  const cellsX = pointsX - 1;
  const cellsY = pointsY - 1;
  const cellVertex = new Int32Array(cellsX * cellsY * (pointsZ - 1)).fill(-1);
  const positions = [];
  const values = new Float64Array(8);
  for (let z = 0; z < pointsZ - 1; z++) {
    for (let y = 0; y < cellsY; y++) {
      for (let x = 0; x < cellsX; x++) {
        let negative = 0;
        for (let corner = 0; corner < 8; corner++) {
          const [dx, dy, dz] = CELL_CORNERS[corner];
          values[corner] = distances[((z + dz) * pointsY + y + dy) * pointsX + x + dx];
          if (values[corner] < 0) negative++;
        }
        if (negative === 0 || negative === 8) continue;
        const sum = [0, 0, 0];
        let crossings = 0;
        for (const [start, end] of CELL_EDGES) {
          if ((values[start] < 0) === (values[end] < 0)) continue;
          const fraction = values[start] / (values[start] - values[end]);
          for (let axis = 0; axis < 3; axis++) {
            sum[axis] += CELL_CORNERS[start][axis] + fraction * (CELL_CORNERS[end][axis] - CELL_CORNERS[start][axis]);
          }
          crossings++;
        }
        cellVertex[(z * cellsY + y) * cellsX + x] = positions.length / 3;
        positions.push(
          origin[0] + (x + sum[0] / crossings) * grid.edge,
          origin[1] + (y + sum[1] / crossings) * grid.edge,
          origin[2] + (z + sum[2] / crossings) * grid.edge,
        );
      }
    }
  }
  return { cellVertex, positions };
}

// For each axis, its two other axes in cyclic order (u, v). Seen from the positive axis, the four cells around an
// edge run counterclockwise through (-1,-1), (0,-1), (0,0), (-1,0) in (u, v).
const AXIS_BASES = [[1, 2], [2, 0], [0, 1]];
const QUAD_OFFSETS = [[-1, -1], [0, -1], [0, 0], [-1, 0]];

/** One quad of cell vertices per grid edge that crosses the surface, wound so the normal points outward. */
export function quadsAroundEdges(distances, grid, cellVertex) {
  const cellsPerAxis = grid.points.map(count => count - 1);
  const [pointsX, pointsY, pointsZ] = grid.points;
  const strides = [1, pointsX, pointsX * pointsY];
  const quads = [];
  const point = [0, 0, 0];
  for (let z = 0; z < pointsZ; z++) {
    for (let y = 0; y < pointsY; y++) {
      for (let x = 0; x < pointsX; x++) {
        point[0] = x;
        point[1] = y;
        point[2] = z;
        const index = (z * pointsY + y) * pointsX + x;
        for (let axis = 0; axis < 3; axis++) {
          const [u, v] = AXIS_BASES[axis];
          if (point[axis] + 1 >= grid.points[axis] || point[u] === 0 || point[v] === 0) continue;
          const here = distances[index];
          if ((here < 0) === (distances[index + strides[axis]] < 0)) continue;
          const quad = QUAD_OFFSETS.map(([stepU, stepV]) => cellVertexAt(cellVertex, cellsPerAxis, point, axis, u, v, stepU, stepV));
          if (quad.includes(-1)) continue;
          quads.push(here < 0 ? quad : quad.reverse());
        }
      }
    }
  }
  return quads;
}

function cellVertexAt(cellVertex, cellsPerAxis, point, axis, u, v, stepU, stepV) {
  const cell = [point[0], point[1], point[2]];
  cell[u] += stepU;
  cell[v] += stepV;
  if (cell[0] >= cellsPerAxis[0] || cell[1] >= cellsPerAxis[1] || cell[2] >= cellsPerAxis[2]) return -1;
  return cellVertex[(cell[2] * cellsPerAxis[1] + cell[1]) * cellsPerAxis[0] + cell[0]];
}