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 unwrap.ts
* @brief A second UV set for a mesh that has none — the whole unwrap, in order.
*
* Cut into flat charts, project each onto its own plane, scale them all by ONE
* ratio, pack, split the vertices the cuts run through. A bake is read through
* the result, so what it must guarantee is that no two surfaces share a texel —
* which is exactly what the UV set the art is wrapped in does not.
*/
import { MeshChannel, MeshChannelType, type MeshData, type MeshChannelDesc } from '../asset/meshFormat';
import { buildCharts, weldByPosition, type Tri } from './charts';
import { packOutlines, packSkyline, type ChartOutline, type PackedRect } from './pack';
export interface UnwrapOptions {
/** Widest angle two neighbouring faces may differ by and stay one chart. */
maxChartAngleDegrees?: number;
/** Texels of empty space kept around every chart, at {@link atlasSize}. Two is
* the least that stops a bilinear tap reading the chart next door. */
paddingTexels?: number;
/** The atlas size the padding is reckoned against. Not stored anywhere: a UV
* set is resolution-independent, and this only fixes what "two texels" means. */
atlasSize?: number;
}
export interface UnwrapResult {
/** The mesh with a `TexCoord1` channel. Has MORE vertices than the input
* wherever a chart boundary runs through one — a vertex on a seam holds a
* different lightmap UV for each side of it. */
mesh: MeshData;
charts: number;
/** Fraction of the unit square the triangles cover. What is left is the price
* of packing charts, and of the padding that keeps them apart. */
coverage: number;
}
const DEFAULTS = { maxChartAngleDegrees: 60, paddingTexels: 2, atlasSize: 1024 };
/** Cells along a side when laying out by outline. Past this a chart's outline is finer than anything packing gains from. */
const MAX_LAYOUT_GRID = 512;
/** Beyond these, charts are packed as rectangles: outlines cost seconds, and many small charts gain little from them. */
const MAX_OUTLINE_CHARTS = 200;
const MAX_OUTLINE_TRIANGLES = 200000;
const SHRINK = 0.8;
/** Halvings of the gap between a size that fits and one that does not: from a gap of 20%, to about a third of a percent. */
const REFINE_STEPS = 6;
function channelAt(channels: readonly MeshChannelDesc[], semantic: number): MeshChannelDesc | undefined {
return channels.find((c) => c.semantic === semantic);
}
/** Positions as a tight `vertexCount * 3` array, whatever the source stride is. */
function readPositions(mesh: MeshData): Float32Array {
const pos = channelAt(mesh.channels, MeshChannel.Position);
if (!pos || pos.type !== MeshChannelType.Float32) {
throw new Error('unwrapLightmapUV: the mesh carries no float Position channel');
}
const view = new DataView(mesh.vertices.buffer, mesh.vertices.byteOffset, mesh.vertices.byteLength);
const out = new Float32Array(mesh.vertexCount * 3);
for (let v = 0; v < mesh.vertexCount; v++) {
const at = v * mesh.vertexStride + pos.offset;
out[v * 3] = view.getFloat32(at, true);
out[v * 3 + 1] = view.getFloat32(at + 4, true);
out[v * 3 + 2] = pos.components >= 3 ? view.getFloat32(at + 8, true) : 0;
}
return out;
}
/** The diagonal of the bounds, as the scale a weld epsilon is relative to. */
function weldEpsilon(mesh: MeshData): number {
const d = Math.hypot(mesh.aabbMax[0] - mesh.aabbMin[0],
mesh.aabbMax[1] - mesh.aabbMin[1],
mesh.aabbMax[2] - mesh.aabbMin[2]);
return Math.max(d, 1e-6) * 1e-5;
}
/**
* Gives `mesh` a lightmap UV set, splitting vertices where charts meet.
*
* Every per-vertex datum follows its vertex, morph deltas included, so the result
* is the same mesh — drawn, skinned and shaped identically — that now also
* carries somewhere to read a bake from.
*/
export function unwrapLightmapUV(mesh: MeshData, options: UnwrapOptions = {}): UnwrapResult {
const opts = { ...DEFAULTS, ...options };
const positions = readPositions(mesh);
const tris: Tri[] = [];
for (let i = 0; i + 2 < mesh.indices.length; i += 3) {
tris.push({ a: mesh.indices[i], b: mesh.indices[i + 1], c: mesh.indices[i + 2] });
}
const rep = weldByPosition(positions, mesh.vertexCount, weldEpsilon(mesh));
const maxCos = Math.cos((opts.maxChartAngleDegrees * Math.PI) / 180);
const charts = buildCharts(positions, tris, rep, maxCos);
// Project every corner into its chart's plane. Held per (triangle, corner)
// rather than per vertex: a vertex on a seam belongs to more than one chart
// and has a different answer in each.
const cornerU = new Float32Array(tris.length * 3);
const cornerV = new Float32Array(tris.length * 3);
const lo = new Float32Array(charts.count * 2).fill(Infinity);
const hi = new Float32Array(charts.count * 2).fill(-Infinity);
for (let t = 0; t < tris.length; t++) {
const c = charts.chartOf[t] * 6;
const corners = [tris[t].a, tris[t].b, tris[t].c];
for (let k = 0; k < 3; k++) {
const p = corners[k] * 3;
const u = positions[p] * charts.basis[c] + positions[p + 1] * charts.basis[c + 1]
+ positions[p + 2] * charts.basis[c + 2];
const v = positions[p] * charts.basis[c + 3] + positions[p + 1] * charts.basis[c + 4]
+ positions[p + 2] * charts.basis[c + 5];
cornerU[t * 3 + k] = u;
cornerV[t * 3 + k] = v;
const b = charts.chartOf[t] * 2;
if (u < lo[b]) lo[b] = u;
if (u > hi[b]) hi[b] = u;
if (v < lo[b + 1]) lo[b + 1] = v;
if (v > hi[b + 1]) hi[b + 1] = v;
}
}
const extent: Array<readonly [number, number]> = [];
for (let c = 0; c < charts.count; c++) {
extent.push([Math.max(hi[c * 2] - lo[c * 2], 0), Math.max(hi[c * 2 + 1] - lo[c * 2 + 1], 0)]);
}
const pad = opts.paddingTexels / opts.atlasSize;
// Every chart's triangles in its own units, for what is laid out and how much of the square they really fill.
const pieces: number[][] = Array.from({ length: charts.count }, () => []);
let area = 0;
for (let t = 0; t < tris.length; t++) {
const chart = charts.chartOf[t];
const piece = pieces[chart];
for (let k = 0; k < 3; k++) piece.push(cornerU[t * 3 + k] - lo[chart * 2], cornerV[t * 3 + k] - lo[chart * 2 + 1]);
area += Math.abs((cornerU[t * 3 + 1] - cornerU[t * 3]) * (cornerV[t * 3 + 2] - cornerV[t * 3])
- (cornerU[t * 3 + 2] - cornerU[t * 3]) * (cornerV[t * 3 + 1] - cornerV[t * 3])) / 2;
}
const grid = Math.min(opts.atlasSize, MAX_LAYOUT_GRID);
const padCells = Math.max(1, Math.ceil(pad * grid));
const byOutline = charts.count <= MAX_OUTLINE_CHARTS && tris.length <= MAX_OUTLINE_TRIANGLES;
const outlines: ChartOutline[] = byOutline ? pieces.map((triangles, c) => ({ triangles, width: extent[c][0], height: extent[c][1] })) : [];
const layout = (at: number): PackedRect[] | null => {
if (byOutline) return packOutlines(outlines, at, grid, padCells);
const boxes = extent.map(([w, h]) => [w * at + pad * 2, h * at + pad * 2] as const);
const laid = packSkyline(boxes, 1);
// A box holds its chart inside its padding; the outline's places are the chart's own already.
return laid && laid.map((box) => ({ ...box, x: box.x + pad, y: box.y + pad }));
};
// ONE ratio for every chart, the largest that fits. A chart scaled on its own would be lit at a different
// resolution from the surface it joins, and the seam is where that shows. No layout can fill more than the
// whole square, so that is where the search starts, and it shrinks until something fits.
let scale = area > 0 ? Math.sqrt(1 / area) : 1;
let placed: PackedRect[] | null = null;
let tooBig = scale;
for (let attempt = 0; attempt < 32 && !placed; attempt++) {
placed = layout(scale);
if (!placed) { tooBig = scale; scale *= SHRINK; }
}
if (!placed) throw new Error('unwrapLightmapUV: charts do not fit even at 0.1% of their size');
// Then toward the last size that did not: the room a first fit leaves is what this is all for.
let fits = scale;
for (let step = 0; step < REFINE_STEPS && tooBig > fits; step++) {
const middle = Math.sqrt(fits * tooBig);
const tried = layout(middle);
if (tried) { placed = tried; fits = middle; } else { tooBig = middle; }
}
scale = fits;
const covered = area * scale * scale;
// Split: a vertex is one new vertex per chart that uses it.
const remap = new Map<number, number>();
const source: number[] = [];
const uv: number[] = [];
const indices = new Uint32Array(tris.length * 3);
for (let t = 0; t < tris.length; t++) {
const chart = charts.chartOf[t];
const box = placed[chart];
const corners = [tris[t].a, tris[t].b, tris[t].c];
for (let k = 0; k < 3; k++) {
const key = corners[k] * charts.count + chart;
let out = remap.get(key);
if (out === undefined) {
out = source.length;
remap.set(key, out);
source.push(corners[k]);
const du = (cornerU[t * 3 + k] - lo[chart * 2]) * scale;
const dv = (cornerV[t * 3 + k] - lo[chart * 2 + 1]) * scale;
uv.push(box.rotated ? box.x + dv : box.x + du,
box.rotated ? box.y + du : box.y + dv);
}
indices[t * 3 + k] = out;
}
}
return {
mesh: rebuild(mesh, source, uv, indices),
charts: charts.count,
coverage: covered,
};
}
/** The same mesh over a new vertex table, with the UV set appended to each. */
function rebuild(mesh: MeshData, source: number[], uv: number[], indices: Uint32Array): MeshData {
const had = channelAt(mesh.channels, MeshChannel.TexCoord1);
const stride = had ? mesh.vertexStride : mesh.vertexStride + 8;
const at = had ? had.offset : mesh.vertexStride;
const channels: MeshChannelDesc[] = had ? [...mesh.channels] : [
...mesh.channels,
{ semantic: MeshChannel.TexCoord1, components: 2, type: MeshChannelType.Float32, offset: at },
];
const vertices = new Uint8Array(source.length * stride);
const view = new DataView(vertices.buffer);
for (let v = 0; v < source.length; v++) {
vertices.set(mesh.vertices.subarray(source[v] * mesh.vertexStride,
(source[v] + 1) * mesh.vertexStride), v * stride);
view.setFloat32(v * stride + at, uv[v * 2], true);
view.setFloat32(v * stride + at + 4, uv[v * 2 + 1], true);
}
let morph = mesh.morph;
if (morph) {
const per = morph.hasNormals ? 6 : 3;
const targets = morph.names.length;
const deltas = new Float32Array(targets * source.length * per);
for (let t = 0; t < targets; t++) {
for (let v = 0; v < source.length; v++) {
const from = (t * mesh.vertexCount + source[v]) * per;
deltas.set(morph.deltas.subarray(from, from + per), (t * source.length + v) * per);
}
}
morph = { ...morph, deltas };
}
return {
...mesh,
channels,
vertexStride: stride,
vertexCount: source.length,
vertices,
indices,
morph,
};
}