A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.
TypeScript 2d-game-engine3d3d-game-engineandroidcppecsgame-editorgame-enginegamedeviostypescriptwebassemblywebglwebgpuwechat-minigame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
* @file atlas.ts
* @brief Which texel of the atlas is which point of the world.
*
* Every object gets a patch sized by the surface it actually has, so one
* world-to-texel ratio holds across the whole bake — the same rule the unwrap
* follows inside one mesh, applied between them.
*/
import { MeshChannel, MeshChannelType, type MeshData, type MeshChannelDesc } from '../asset/meshFormat';
import { packSkyline } from './pack';
/** One object to bake: geometry with a lightmap UV set, and where it stands. */
export interface BakeSurface {
mesh: MeshData;
/** Column-major 4x4, as `glm` and the engine write one. */
transform: ArrayLike<number>;
/** What fraction of each channel the surface reflects. Drives the bounce;
* a surface that reflects nothing still receives light. */
albedo?: readonly [number, number, number];
/** What to call it when a bake has something to say about it. */
label?: string;
/** True when its draw adds the lamps itself (a lit renderer): its patch then
* holds only what arrives indirectly, or the lamps would land twice. */
realtimeDirect?: boolean;
/** Drawn with both faces: a ray arriving at its back finds it lit, not black. */
twoSided?: boolean;
/** Share of its area that is there — for a cutout, the texels past its cutoff.
* Rays pass the rest, so foliage shades what is under it without walling it in. */
coverage?: number;
}
/** Texels of one object's patch, and where in the atlas it sits. */
export interface SurfacePatch {
/** Side of the square patch, in texels. */
side: number;
x: number;
y: number;
rotated: boolean;
/** What a `MeshLightmap` carries: `[scaleU, scaleV, offsetU, offsetV]`. */
scaleOffset: [number, number, number, number];
}
/** Every texel a bake will solve, as parallel arrays. */
export interface LumelField {
count: number;
/** World position, three floats each. */
position: Float32Array;
/** World normal, three floats each. */
normal: Float32Array;
/** Index into the atlas, one per lumel. */
texel: Int32Array;
/** Which surface each lumel belongs to. */
surface: Int32Array;
/** Per surface: the share of its triangles' texels another of its own already held. */
shared: Float32Array;
}
const chan = (m: MeshData, s: number): MeshChannelDesc | undefined =>
m.channels.find((c) => c.semantic === s);
function reader(mesh: MeshData): (v: number, semantic: number, n: number, out: Float32Array, at: number) => boolean {
const view = new DataView(mesh.vertices.buffer, mesh.vertices.byteOffset, mesh.vertices.byteLength);
return (v, semantic, n, out, at) => {
const c = chan(mesh, semantic);
if (!c || c.type !== MeshChannelType.Float32) return false;
const base = v * mesh.vertexStride + c.offset;
for (let k = 0; k < n; k++) out[at + k] = k < c.components ? view.getFloat32(base + k * 4, true) : 0;
return true;
};
}
function transformPoint(m: ArrayLike<number>, x: number, y: number, z: number, out: Float32Array, at: number): void {
out[at] = m[0] * x + m[4] * y + m[8] * z + m[12];
out[at + 1] = m[1] * x + m[5] * y + m[9] * z + m[13];
out[at + 2] = m[2] * x + m[6] * y + m[10] * z + m[14];
}
/** Direction under the same transform, without its translation. Not the inverse
* transpose: a bake takes objects as placed, and a non-uniform scale on baked
* geometry is a modelling choice this does not try to rescue. */
function transformDir(m: ArrayLike<number>, x: number, y: number, z: number, out: Float32Array, at: number): void {
const nx = m[0] * x + m[4] * y + m[8] * z;
const ny = m[1] * x + m[5] * y + m[9] * z;
const nz = m[2] * x + m[6] * y + m[10] * z;
const len = Math.hypot(nx, ny, nz) || 1;
out[at] = nx / len; out[at + 1] = ny / len; out[at + 2] = nz / len;
}
/** World and UV area of one surface, which together give its texel ratio. */
function areasOf(surface: BakeSurface): { world: number; uv: number } {
const read = reader(surface.mesh);
const p = new Float32Array(9);
const t = new Float32Array(6);
const w = new Float32Array(9);
let world = 0, uv = 0;
const idx = surface.mesh.indices;
for (let i = 0; i + 2 < idx.length; i += 3) {
for (let k = 0; k < 3; k++) {
if (!read(idx[i + k], MeshChannel.Position, 3, p, k * 3)) return { world: 0, uv: 0 };
if (!read(idx[i + k], MeshChannel.TexCoord1, 2, t, k * 2)) return { world: 0, uv: 0 };
transformPoint(surface.transform, p[k * 3], p[k * 3 + 1], p[k * 3 + 2], w, k * 3);
}
const ux = w[3] - w[0], uy = w[4] - w[1], uz = w[5] - w[2];
const vx = w[6] - w[0], vy = w[7] - w[1], vz = w[8] - w[2];
world += Math.hypot(uy * vz - uz * vy, uz * vx - ux * vz, ux * vy - uy * vx) / 2;
uv += Math.abs((t[2] - t[0]) * (t[5] - t[1]) - (t[4] - t[0]) * (t[3] - t[1])) / 2;
}
return { world, uv };
}
/**
* Below this share of its unit square, a lightmap UV set is too sparse to bake
* into: a patch holds the whole square, so ORCA Bistro's road, 3533 m² in 0.5%
* of it, asked for more atlas than the rest of the town together.
*/
export const SPARSE_LIGHTMAP_UV = 0.05;
/**
* Above this many layers of a lightmap UV set lying on itself, parts of the mesh
* would share texels and so share light: a curb laid over its own UVs eighty
* times over took whatever its first triangle saw, underside included.
*/
export const OVERLAPPING_LIGHTMAP_UV = 1.1;
/**
* The patch each surface asks for, and how much of its lightmap UV square its
* triangles cover: a patch holds the whole square, so a sparse layout pays for
* the empty rest.
*/
export function atlasDemand(surfaces: readonly BakeSurface[], size: number,
texelsPerUnit: number): { side: number; uvCoverage: number }[] {
return surfaces.map((s) => {
const { world, uv } = areasOf(s);
if (world <= 0 || uv <= 0) return { side: 1, uvCoverage: uv };
// The unwrap kept one ratio inside the mesh; this is what that ratio is,
// and it says how many texels a patch needs to hit the density asked for.
const side = texelsPerUnit / Math.sqrt(uv / world);
return { side: Math.max(2, Math.min(size, Math.ceil(side))), uvCoverage: uv };
});
}
/**
* Gives every surface a patch of an `size`-by-`size` atlas at `texelsPerUnit`.
*
* Returns null when they do not fit — the caller's signal to ask for a bigger
* atlas or a coarser density, which is a decision an author makes rather than
* one a packer should make quietly by shrinking someone.
*/
export function layoutAtlas(surfaces: readonly BakeSurface[], size: number,
texelsPerUnit: number): SurfacePatch[] | null {
const sides = atlasDemand(surfaces, size, texelsPerUnit).map((d) => d.side);
const placed = packSkyline(sides.map((s) => [s, s] as const), size);
if (!placed) return null;
return sides.map((side, i) => ({
side,
x: placed[i].x,
y: placed[i].y,
rotated: placed[i].rotated,
scaleOffset: [side / size, side / size, placed[i].x / size, placed[i].y / size],
}));
}
/**
* The world point and normal behind every texel the surfaces cover.
*
* A texel centred outside every triangle is not in the field: solving it would
* pay for the gaps between charts. What keeps a bilinear tap off those gaps is
* the dilate afterwards, not a lumel invented here.
*/
export function rasterizeLumels(surfaces: readonly BakeSurface[],
patches: readonly SurfacePatch[], size: number): LumelField {
const position: number[] = [];
const normal: number[] = [];
const texel: number[] = [];
const owner: number[] = [];
const seen = new Set<number>();
const shared = new Float32Array(surfaces.length);
const p = new Float32Array(9);
const n = new Float32Array(9);
const t = new Float32Array(6);
const wp = new Float32Array(9);
const wn = new Float32Array(9);
for (let s = 0; s < surfaces.length; s++) {
const surface = surfaces[s];
const patch = patches[s];
const read = reader(surface.mesh);
const idx = surface.mesh.indices;
const hasNormals = chan(surface.mesh, MeshChannel.Normal) !== undefined;
let claimed = 0, taken = 0;
for (let i = 0; i + 2 < idx.length; i += 3) {
let ok = true;
for (let k = 0; k < 3 && ok; k++) {
ok = read(idx[i + k], MeshChannel.Position, 3, p, k * 3)
&& read(idx[i + k], MeshChannel.TexCoord1, 2, t, k * 2);
if (!ok) break;
transformPoint(surface.transform, p[k * 3], p[k * 3 + 1], p[k * 3 + 2], wp, k * 3);
if (hasNormals && read(idx[i + k], MeshChannel.Normal, 3, n, k * 3)) {
transformDir(surface.transform, n[k * 3], n[k * 3 + 1], n[k * 3 + 2], wn, k * 3);
}
}
if (!ok) continue;
if (!hasNormals) {
// The face's own normal, for geometry that carries none.
const ux = wp[3] - wp[0], uy = wp[4] - wp[1], uz = wp[5] - wp[2];
const vx = wp[6] - wp[0], vy = wp[7] - wp[1], vz = wp[8] - wp[2];
const fx = uy * vz - uz * vy, fy = uz * vx - ux * vz, fz = ux * vy - uy * vx;
const len = Math.hypot(fx, fy, fz) || 1;
for (let k = 0; k < 3; k++) {
wn[k * 3] = fx / len; wn[k * 3 + 1] = fy / len; wn[k * 3 + 2] = fz / len;
}
}
// Into the patch's own texels, then into the atlas.
const ax: number[] = [], ay: number[] = [];
for (let k = 0; k < 3; k++) {
const u = patch.rotated ? t[k * 2 + 1] : t[k * 2];
const v = patch.rotated ? t[k * 2] : t[k * 2 + 1];
ax.push(patch.x + u * patch.side);
ay.push(patch.y + v * patch.side);
}
const area = (ax[1] - ax[0]) * (ay[2] - ay[0]) - (ax[2] - ax[0]) * (ay[1] - ay[0]);
if (Math.abs(area) < 1e-9) continue;
const minX = Math.max(0, Math.floor(Math.min(...ax)));
const maxX = Math.min(size - 1, Math.ceil(Math.max(...ax)));
const minY = Math.max(0, Math.floor(Math.min(...ay)));
const maxY = Math.min(size - 1, Math.ceil(Math.max(...ay)));
for (let y = minY; y <= maxY; y++) {
for (let x = minX; x <= maxX; x++) {
const cx = x + 0.5, cy = y + 0.5;
const w0 = ((ax[1] - cx) * (ay[2] - cy) - (ax[2] - cx) * (ay[1] - cy)) / area;
const w1 = ((ax[2] - cx) * (ay[0] - cy) - (ax[0] - cx) * (ay[2] - cy)) / area;
const w2 = 1 - w0 - w1;
if (w0 < 0 || w1 < 0 || w2 < 0) continue;
const at = y * size + x;
claimed++;
// A centre on an edge the triangles share is one texel, not a second layer.
if (seen.has(at)) { if (w0 > 1e-6 && w1 > 1e-6 && w2 > 1e-6) taken++; continue; }
seen.add(at);
for (let k = 0; k < 3; k++) {
position.push(w0 * wp[k] + w1 * wp[3 + k] + w2 * wp[6 + k]);
}
let nx = w0 * wn[0] + w1 * wn[3] + w2 * wn[6];
let ny = w0 * wn[1] + w1 * wn[4] + w2 * wn[7];
let nz = w0 * wn[2] + w1 * wn[5] + w2 * wn[8];
const len = Math.hypot(nx, ny, nz) || 1;
nx /= len; ny /= len; nz /= len;
normal.push(nx, ny, nz);
texel.push(at);
owner.push(s);
}
}
}
shared[s] = claimed > 0 ? taken / claimed : 0;
}
return {
count: texel.length,
position: Float32Array.from(position),
normal: Float32Array.from(normal),
texel: Int32Array.from(texel),
surface: Int32Array.from(owner),
shared,
};
}