File size: 3,947 Bytes
9f85448 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | """Mesh simplification for the software rasterizer.
The rasterizer costs roughly a fixed amount of Python work per triangle, so a
film-quality character mesh has to be thinned before it can animate in real
time. Vertex clustering is used rather than edge-collapse: it is a few lines,
runs once at load, and carries skinning weights and UVs along untouched, which
matters because these meshes are posed every frame.
"""
from __future__ import annotations
import numpy as np
import gltf
# Resolution of the texture-space grid that keeps atlas islands from merging.
_UV_CELLS = 16
def _weld(prim: gltf.Primitive, cells: int) -> gltf.Primitive:
"""Snap vertices to a grid of `cells` per axis and drop collapsed triangles."""
pos = prim.positions
lo = pos.min(axis=0)
span = np.maximum(pos.max(axis=0) - lo, 1e-9)
# Grid coordinate per vertex, then one representative vertex per cell.
grid = np.floor((pos - lo) / span * cells).astype(np.int64)
grid = np.clip(grid, 0, cells - 1)
keys = (grid[:, 0] * cells + grid[:, 1]) * cells + grid[:, 2]
# Vertices that a nearby grid cell would merge but that belong to different
# bones must stay apart, or an arm gets welded to the chest it rests against.
dominant = prim.joints[np.arange(len(prim.joints)), np.argmax(prim.weights, axis=1)]
keys = keys * (int(dominant.max()) + 1) + dominant.astype(np.int64)
if prim.uv is not None:
# Keep texture-atlas islands apart too. Neighbours straddling a UV seam
# look adjacent in space but map to unrelated pixels, and collapsing
# them together is what speckles small details like hair and shoes.
uv_cell = np.clip(np.floor(np.mod(prim.uv, 1.0) * _UV_CELLS), 0, _UV_CELLS - 1)
uv_key = uv_cell[:, 0].astype(np.int64) * _UV_CELLS + uv_cell[:, 1].astype(np.int64)
keys = keys * (_UV_CELLS * _UV_CELLS) + uv_key
_, first, inverse = np.unique(keys, return_index=True, return_inverse=True)
tris = inverse[prim.triangles]
# A triangle whose corners landed in the same cell has no area left.
keep = (tris[:, 0] != tris[:, 1]) & (tris[:, 1] != tris[:, 2]) & (tris[:, 0] != tris[:, 2])
tris = tris[keep]
if tris.shape[0] == 0:
return prim
# Every surviving attribute is taken from the same representative vertex, so
# position, normal and UV stay mutually consistent.
merged_pos = pos[first]
merged_nrm = (prim.normals[first] if prim.normals is not None and prim.normals.size
else np.zeros((len(first), 3)))
# UVs come from one representative vertex, never averaged: neighbours in
# space can sit far apart in the texture atlas, and a mean of two such
# coordinates points at unrelated pixels, which speckles the face and shoes.
merged_uv = None if prim.uv is None else prim.uv[first]
return gltf.Primitive(
positions=merged_pos,
normals=merged_nrm,
# Joints and weights are taken from one representative vertex per cell;
# averaging them would blend unrelated bones and tear the mesh.
joints=prim.joints[first],
weights=prim.weights[first],
triangles=tris,
color=prim.color,
uv=merged_uv,
texture=prim.texture,
)
def to_budget(primitives: list[gltf.Primitive], budget: int) -> list[gltf.Primitive]:
"""Thin primitives until their combined triangle count fits the budget."""
total = sum(len(p.triangles) for p in primitives)
if total <= budget:
return primitives
out = list(primitives)
# Search downward for the coarsest grid that still meets the budget; each
# pass is cheap and this runs once per model load.
for cells in (128, 96, 72, 56, 44, 34, 26, 20, 16, 12):
candidate = [_weld(p, cells) for p in primitives]
if sum(len(p.triangles) for p in candidate) <= budget:
return candidate
out = candidate
return out
|