Teil 3: Surface Nets

/**
 * Extra samples around the cells on every side. The normals need one sample beyond the
 * edge, and the last cells of surface nets reach one sample further.
 */
export const MARGIN = 2;

/** Two triangles for the four corners, split along the shorter diagonal. */
quad(a: number, b: number, c: number, d: number): void {
  if (this.distance(a, c) <= this.distance(b, d)) {
    this.triangle(a, b, c);
    this.triangle(a, c, d);
  } else {
    this.triangle(b, c, d);
    this.triangle(b, d, a);
  }
}

private distance(a: number, b: number): number {
  const p = this.positions;
  return Math.hypot(p[a * 3] - p[b * 3], p[a * 3 + 1] - p[b * 3 + 1], p[a * 3 + 2] - p[b * 3 + 2]);
}

import { CHUNK_SIZE, type DensityGrid } from './grid.ts';
import { MeshBuilder, type MeshData } from './meshData.ts';

/** The eight corners of a cell, numbered like the marching cubes corners. */
const 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],
];
/** The twelve edges of a cell, as the corners they join. */
const 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],
];

const lerp = (a: number, b: number, t: number) => a + (b - a) * t;

/**
 * A surface for the density with one vertex in each cell the surface passes through, and
 * a quad across each edge of the grid where the density changes sign. The quad joins the
 * vertices of the four cells around that edge.
 */
export function surfaceNets(grid: DensityGrid): MeshData {
  const mesh = new MeshBuilder();
  // Cells 0 to CHUNK_SIZE: one more on each axis than the chunk has, see below.
  const cells = CHUNK_SIZE + 1;
  const vertexIn = new Int32Array(cells ** 3).fill(-1);
  const step = [1, cells, cells * cells];
  const d = new Float32Array(8);

  for (let z = 0; z < cells; z += 1) {
    for (let y = 0; y < cells; y += 1) {
      for (let x = 0; x < cells; x += 1) {
        let solid = 0;
        for (let c = 0; c < 8; c += 1) {
          d[c] = grid.get(x + CORNERS[c][0], y + CORNERS[c][1], z + CORNERS[c][2]);
          if (d[c] > 0) solid += 1;
        }
        if (solid === 0 || solid === 8) continue;

        // The vertex sits at the average of the points where the edges cross the surface.
        let px = 0;
        let py = 0;
        let pz = 0;
        let crossings = 0;
        for (const [a, b] of EDGES) {
          if (d[a] > 0 === d[b] > 0) continue;
          const t = d[a] / (d[a] - d[b]);
          px += lerp(CORNERS[a][0], CORNERS[b][0], t);
          py += lerp(CORNERS[a][1], CORNERS[b][1], t);
          pz += lerp(CORNERS[a][2], CORNERS[b][2], t);
          crossings += 1;
        }
        px /= crossings;
        py /= crossings;
        pz /= crossings;

        // The normal: the corners' gradients, blended by how close the vertex is to each.
        let nx = 0;
        let ny = 0;
        let nz = 0;
        for (let c = 0; c < 8; c += 1) {
          const [cx, cy, cz] = CORNERS[c];
          const weight = (cx ? px : 1 - px) * (cy ? py : 1 - py) * (cz ? pz : 1 - pz);
          const [gx, gy, gz] = grid.gradient(x + cx, y + cy, z + cz);
          nx -= gx * weight;
          ny -= gy * weight;
          nz -= gz * weight;
        }
        vertexIn[x + y * step[1] + z * step[2]] = mesh.vertex(x + px, y + py, z + pz, nx, ny, nz);
      }
    }
  }

  // A quad for every edge with a sign change. Of the edges along an axis, the chunk takes
  // those 0 to CHUNK_SIZE - 1 along it and 1 to CHUNK_SIZE on the other two axes, so that
  // the four cells around each edge are among its cells. The neighbors take the rest.
  for (let z = 0; z <= CHUNK_SIZE; z += 1) {
    for (let y = 0; y <= CHUNK_SIZE; y += 1) {
      for (let x = 0; x <= CHUNK_SIZE; x += 1) {
        const p = [x, y, z];
        const here = grid.get(x, y, z) > 0;
        const cell = x + y * step[1] + z * step[2];
        for (let axis = 0; axis < 3; axis += 1) {
          const u = (axis + 1) % 3;
          const v = (axis + 2) % 3;
          if (p[axis] === CHUNK_SIZE || p[u] === 0 || p[v] === 0) continue;
          const there = grid.get(x + (axis === 0 ? 1 : 0), y + (axis === 1 ? 1 : 0), z + (axis === 2 ? 1 : 0)) > 0;
          if (here === there) continue;

          // The four cells around the edge, in order around it.
          const a = vertexIn[cell - step[u] - step[v]];
          const b = vertexIn[cell - step[v]];
          const c = vertexIn[cell];
          const e = vertexIn[cell - step[u]];
          // Which way the quad faces depends on which end of the edge is solid.
          if (here) mesh.quad(a, e, c, b);
          else mesh.quad(a, b, c, e);
        }
      }
    }
  }
  return mesh.build();
}

import type { DensityGrid } from './grid.ts';
import { marchingCubes } from './marchingCubes.ts';
import type { MeshData } from './meshData.ts';
import { surfaceNets } from './surfaceNets.ts';

/** Both ways to turn a grid into a mesh, by name. */
export const MESHERS = {
  'marching-cubes': { label: 'Marching cubes', mesh: marchingCubes },
  'surface-nets': { label: 'Surface nets', mesh: surfaceNets },
} satisfies Record<string, { label: string; mesh: (grid: DensityGrid) => MeshData }>;

export type MesherName = keyof typeof MESHERS;

/** The other mesher. */
export function otherMesher(name: MesherName): MesherName {
  return name === 'marching-cubes' ? 'surface-nets' : 'marching-cubes';
}

import {
  ArcRotateCamera,
  Color3,
  Color4,
  DirectionalLight,
  Engine,
  HemisphericLight,
  RegisterStandardEngineExtensions,
  RegisterStandardMaterial,
  RegisterThinInstanceMesh,
  Scene,
  StandardMaterial,
  Vector3,
  type Mesh,
} from '@babylonjs/core/pure';
import { showBlocks } from './blocks.ts';
import { CHUNK_SIZE, DensityGrid } from './grid.ts';
import { createMesh } from './meshData.ts';
import { MESHERS, otherMesher, type MesherName } from './meshers.ts';
import { testShape } from './shapes.ts';
import './style.css';

RegisterStandardEngineExtensions();
RegisterStandardMaterial();
RegisterThinInstanceMesh();

const canvas = document.querySelector<HTMLCanvasElement>('#game')!;
const hud = document.querySelector<HTMLElement>('#hud')!;

const engine = new Engine(canvas, true, {}, true);
const scene = new Scene(engine);
scene.clearColor = Color4.FromHexString('#2a1150ff');

// A cool light from the sky and a warm, low sun.
const sky = new HemisphericLight('sky', new Vector3(0, 1, 0), scene);
sky.intensity = 0.6;
sky.diffuse = Color3.FromHexString('#c4b5fd');
sky.groundColor = Color3.FromHexString('#3b1676');
const sun = new DirectionalLight('sun', new Vector3(0.5, -0.65, -0.55), scene);
sun.intensity = 1.1;
sun.diffuse = Color3.FromHexString('#ffd8a8');

const grid = new DensityGrid().fill(testShape);
const material = new StandardMaterial('ground', scene);
material.diffuseColor = Color3.FromHexString('#d9a066');
material.specularColor = Color3.Black();

// This part is about surface nets, so they come first; M switches to marching cubes.
let mesher: MesherName = 'surface-nets';
let mesh: Mesh | null = null;

/** Meshes the grid with the current mesher, in place of the last mesh. */
function remesh(): void {
  const started = performance.now();
  const data = MESHERS[mesher].mesh(grid);
  const time = performance.now() - started;
  mesh?.dispose();
  mesh = createMesh('shape', data, scene);
  mesh.material = material;
  hud.textContent =
    `${MESHERS[mesher].label} in ${time.toFixed(1)} ms\n` +
    `${data.indices.length / 3} triangles, ${data.positions.length / 3} vertices`;
}
remesh();

const blocks = showBlocks(scene, grid);
blocks.setEnabled(false);

window.addEventListener('keydown', (event) => {
  if (event.code === 'KeyB') blocks.setEnabled(!blocks.isEnabled());
  if (event.code === 'KeyL') material.wireframe = !material.wireframe;
  if (event.code === 'KeyM') {
    mesher = otherMesher(mesher);
    remesh();
  }
});

// Orbit around the middle of the grid.
const middle = new Vector3(CHUNK_SIZE / 2, CHUNK_SIZE / 3, CHUNK_SIZE / 2);
const camera = new ArcRotateCamera('camera', 2.2, 1.1, 60, middle, scene);
camera.attachControl();
camera.lowerRadiusLimit = 10;
camera.upperRadiusLimit = 120;
camera.wheelPrecision = 5;

engine.runRenderLoop(() => scene.render());
window.addEventListener('resize', () => engine.resize());