Spaces:

Upsampler
/

remesh

Running

remesh / remesh.py

Deploy from 3dvalley spaces/remesh: native.py, chunked bake, STL and PLY upright

2f89f22 verified 30 days ago

22.5 kB

"""
Remesh a model: new clean topology (quads or even triangles) at a target face
count, fresh UVs, and the original's look baked onto it.
  solid.py        one sealed surface around the input, whatever its state,
                  with parts thinner than a face widened to one face
  QuadriFlow      quad remeshing of that surface (Instant Meshes if it fails)
  topology.py     the result closed up: no holes, shards or tangled edges
  xatlas          UVs for the new mesh
  bake            per texel, the nearest point of the original: base colour,
                  metallic/roughness, and a normal map carrying the detail the
                  new mesh is too coarse to hold, in the tangents stored in the
                  file so every renderer shades it the way it was baked
"""

import os
import time

import numpy as np
import trimesh
from PIL import Image
from scipy import ndimage

import native
from glb import write_glb, write_obj
from solid import grid_surface, near, solid_grid, thicken
from topology import close_up, triangles, trouble


def sniff(path):
    """The format from the file itself, for uploads that lost their name on the way."""
    with open(path, "rb") as f:
        head = f.read(512)
    if head[:4] == b"glTF":
        return "glb"
    if head.startswith(b"ply"):
        return "ply"
    if head.lstrip().startswith(b"{"):
        return "gltf"
    text = head.decode("latin-1").lstrip()
    if text.startswith("solid") and b"facet" in head:
        return "stl"
    if any(line.split()[:1] in (["v"], ["vn"], ["vt"], ["f"], ["o"], ["g"], ["mtllib"], ["#"]) for line in text.splitlines() if line.strip()):
        return "obj"
    return "stl"  # binary STL has no magic; it is the one format left


# STL and PLY come from CAD, slicers and scanners, which are Z-up; glTF and
# OBJ are Y-up. The results are a GLB and an OBJ, so a Z-up model is turned
# upright on the way in: (x, y, z) -> (x, z, -y), the quarter turn about X that
# the site's viewer and converters make (src/lib/mesh/axes.ts).
Z_UP = ("stl", "ply")
Z_UP_TO_Y_UP = np.array([[1, 0, 0, 0], [0, 0, 1, 0], [0, -1, 0, 0], [0, 0, 0, 1]], dtype=np.float64)


def load(path):
    extension = os.path.splitext(path)[1].lower().lstrip(".")
    known = extension in ("glb", "gltf", "obj", "stl", "ply")
    kind = extension if known else sniff(path)
    scene = trimesh.load(path, force="scene") if known else trimesh.load(path, file_type=kind, force="scene")
    if len(scene.geometry) == 0:
        raise ValueError("The file has no mesh in it.")
    mesh = scene.to_geometry() if len(scene.geometry) == 1 else scene.dump(concatenate=True)
    if kind in Z_UP:
        mesh.apply_transform(Z_UP_TO_Y_UP)
    return mesh


# Auto: quad counts tried in turn, and how far the new surface may stray from
# the sealed one (99th percentile, as a share of the model's largest side).
# At 0.4% the shape, faces included, reads as the same object; measured on generated
# and scanned models, the count that takes ranges from a few thousand (a barrel)
# to tens of thousands (a race car's thin spoilers), so no single default fits.
AUTO_LADDER = [2000, 3500, 6000, 10000, 15000, 25000, 40000]
AUTO_TOLERANCE = 0.004
# A few small holes are filled cleanly; more corners than this on open or
# tangled edges means a thin part came apart, and it is remeshed widened.
TROUBLE = 24


class Sealed:
    """The model filled into voxels, and sealed surfaces made from it.
    Every surface is one closed piece whatever the input was, and sheets down
    to a voxel thick are kept (the smoothing would otherwise erase them).
    """

    def __init__(self, mesh):
        self.grid, self.h, self.lo = solid_grid(np.asarray(mesh.vertices, dtype=np.float64), np.asarray(mesh.faces))
        self.grid = thicken(self.grid, 1.0)
        self.v, self.f = grid_surface(self.grid, self.h, self.lo)
        # The reference the result is measured against.
        reference = trimesh.Trimesh(self.v, self.f, process=False)
        self.area = float(reference.area)
        self.size = float((reference.bounds[1] - reference.bounds[0]).max())
        # Seeded, so a model gets the same count every time it is run.
        self.points, _ = trimesh.sample.sample_surface(reference, 10000, seed=0)

    def widened(self, quads, spots):
        """The sealed surface with thin parts near `spots` made one face of `quads` thick.
        No remesher can lay faces on both sides of a sheet thinner than its
        edges: the sides snap together and leave holes and shards. Widening
        only where that happened leaves sharp edges elsewhere as they are.
        """
        edge = np.sqrt(self.area / max(quads, 1))
        where = near(self.grid.shape, self.h, self.lo, spots, 3 * edge)
        return grid_surface(thicken(self.grid, max(1.5, 0.5 * edge / self.h), where), self.h, self.lo)

    def deviation(self, v, tris):
        """99th percentile distance from the sealed model to (v, tris), as a share of the largest side."""
        return float(np.percentile(point_distances(self.points, v, tris), 99)) / self.size


def quad_mesh(sealed_v, sealed_f, quads):
    """About `quads` quads over a sealed surface: QuadriFlow, another seed, then Instant Meshes."""
    for seed in (0, 1):
        try:
            return native.quadriflow_remesh(sealed_v, sealed_f, quads, seed=seed)
        except RuntimeError as error:
            print(f"QuadriFlow, seed {seed}: {error}", flush=True)
    return native.instant_meshes(sealed_v, sealed_f, quads)


def build(sealed, quads, as_quads):
    """One new surface of about `quads` quads: (vertices, polygons, triangles).
    The result is closed and edge-manifold: tangled faces and loose shards the
    remesher leaves are removed and every hole is filled. As triangles, each
    quad is split along its shorter diagonal.
    """
    v, polys = quad_mesh(sealed.v, sealed.f, quads)
    spots = trouble(v, polys)
    print(f"{quads} quads: {len(spots)} trouble spots", flush=True)
    if len(spots) > TROUBLE:
        # Thin parts came out broken: widen them to one face there and run again,
        # and keep whichever run, closed up, stays nearer the model.
        again_v, again_polys = quad_mesh(*sealed.widened(quads, spots), quads)
        first, second = close_up(v, polys), close_up(again_v, again_polys)
        pick = min((first, second), key=lambda c: sealed.deviation(c[0], triangles(c[1], c[0])))
        v, polys = pick[0], pick[1]
    v, polys, _ = close_up(v, polys)
    tris = triangles(polys, v)
    # Normals out: the enclosed volume must come out positive.
    a, b, c = v[tris[:, 0]], v[tris[:, 1]], v[tris[:, 2]]
    if np.einsum("ij,ij->i", a, np.cross(b, c)).sum() < 0:
        polys, tris = polys[:, ::-1].copy(), tris[:, ::-1].copy()
    if not as_quads:
        polys = tris
    return v, polys, tris


def new_surface(mesh, target_faces, quads=True, note=None):
    """Clean topology at about `target_faces`, from a sealed rebuild of the input.
    QuadriFlow needs a manifold input and generated meshes rarely are, so it
    remeshes the sealed surface instead. The look is baked from the original
    afterwards, so nothing of it is lost here.
    A target of 0 is Auto: the fewest faces on AUTO_LADDER whose surface stays
    within AUTO_TOLERANCE of the sealed one. Returns the surface and, for Auto,
    what was found: {"deviation": share of the size, "held": within tolerance}.
    """
    sealed = Sealed(mesh)
    # Triangles come from splitting quads, two to a quad.
    per_quad = 1 if quads else 2
    if target_faces <= 0:
        return auto_surface(sealed, quads, note)
    want = max(50, int(target_faces / per_quad))
    # QuadriFlow lands a few percent under the count it is given.
    ask = int(want * 1.04)
    for _ in range(2):
        v, polys, tris = build(sealed, ask, quads)
        got = len(polys) / per_quad
        if abs(got - want) / want < 0.12:
            break
        ask = max(50, int(ask * want / max(got, 1)))
    return v, polys, tris, None


def auto_surface(sealed, quads, note=None):
    """The fewest quads on AUTO_LADDER that keep the shape.
    Each try is a full remesh, so the ladder is not walked from the bottom:
    the first try is in the middle, and how far it strays says where the
    count lies (the error shrinks about as the count grows to the power 0.75).
    From there it steps down while the shape holds, or up until it does.
    """
    # Never more quads than the sealed surface has triangles over four: that would add, not clean.
    most = max(AUTO_LADDER[0], len(sealed.f) // 4)
    ladder = [count for count in AUTO_LADDER if count <= most] or AUTO_LADDER[:1]
    tried = {}

    def attempt(i):
        if i not in tried:
            started = time.perf_counter()
            if note:
                # Each try can take a while: say which one is running.
                note(f"Trying {ladder[i]:,} {'quads' if quads else 'triangles'}")
            v, polys, tris = build(sealed, ladder[i], quads)
            tried[i] = (sealed.deviation(v, tris), v, polys, tris)
            print(f"Auto: {ladder[i]} quads, {tried[i][0]:.4f} of the size, {time.perf_counter() - started:.0f} s", flush=True)
        return tried[i][0] <= AUTO_TOLERANCE

    i = min(range(len(ladder)), key=lambda k: abs(ladder[k] - 6000))
    if attempt(i):
        while i > 0 and attempt(i - 1):
            i -= 1
    else:
        guess = ladder[i] * (tried[i][0] / AUTO_TOLERANCE) ** (1 / 0.75)
        i = next((k for k in range(i + 1, len(ladder)) if ladder[k] >= 0.9 * guess), len(ladder) - 1)
        if attempt(i):
            # A jump may overshoot: take the step below if it holds too.
            while i > 0 and i - 1 not in tried and attempt(i - 1):
                i -= 1
        else:
            while i + 1 < len(ladder) and not attempt(i + 1):
                i += 1
            i = min(i + 1, len(ladder) - 1)
    deviation, v, polys, tris = tried[i]
    return v, polys, tris, {"deviation": round(deviation, 4), "held": deviation <= AUTO_TOLERANCE}


def point_distances(points, v, tris):
    """Distance from each point to the nearest point of the mesh (v, tris)."""
    distance, _, _ = native.closest_points_on_mesh(points, v, tris)
    return distance


def vertex_tangents(positions, normals, uvs, faces):
    """Per-vertex tangents with handedness, averaged over the triangles around each vertex."""
    p0, p1, p2 = (positions[faces[:, k]] for k in range(3))
    u0, u1, u2 = (uvs[faces[:, k]] for k in range(3))
    e1, e2, d1, d2 = p1 - p0, p2 - p0, u1 - u0, u2 - u0
    det = d1[:, 0] * d2[:, 1] - d2[:, 0] * d1[:, 1]
    r = np.where(np.abs(det) < 1e-14, 0.0, 1.0 / np.where(det == 0, 1, det))[:, None]
    t_face = (e1 * d2[:, 1:2] - e2 * d1[:, 1:2]) * r
    b_face = (e2 * d1[:, 0:1] - e1 * d2[:, 0:1]) * r
    t = np.zeros_like(positions)
    b = np.zeros_like(positions)
    for k in range(3):
        np.add.at(t, faces[:, k], t_face)
        np.add.at(b, faces[:, k], b_face)
    t -= normals * np.sum(t * normals, axis=1, keepdims=True)
    length = np.linalg.norm(t, axis=1, keepdims=True)
    # A vertex whose UVs give no direction gets any vector perpendicular to its normal.
    fallback = np.cross(normals, np.where(np.abs(normals[:, :1]) < 0.9, [[1.0, 0, 0]], [[0, 1.0, 0]]))
    fallback /= np.maximum(np.linalg.norm(fallback, axis=1, keepdims=True), 1e-12)
    t = np.where(length > 1e-12, t / np.maximum(length, 1e-12), fallback)
    w = np.where(np.sum(np.cross(normals, t) * b, axis=1) < 0, -1.0, 1.0)
    return np.concatenate([t, w[:, None]], axis=1)


# Candidate texels tested at a time: every texel in each triangle's bounding box
# passes through a dozen arrays, so a few large triangles on a 4096 px map
# would otherwise be gigabytes in one go.
RASTER_TEXELS = 1_500_000


def rasterize(uvs, faces, size, budget=RASTER_TEXELS):
    """Every texel centre inside a UV triangle, as (row, col, triangle, barycentrics)."""
    px = np.stack([uvs[:, 0] * size, (1 - uvs[:, 1]) * size], axis=1)
    pa, pb, pc = px[faces[:, 0]], px[faces[:, 1]], px[faces[:, 2]]
    lo = np.clip(np.floor(np.minimum(np.minimum(pa, pb), pc)), 0, size - 1).astype(np.int64)
    hi = np.clip(np.ceil(np.maximum(np.maximum(pa, pb), pc)), 0, size - 1).astype(np.int64)
    wx, wy = hi[:, 0] - lo[:, 0] + 1, hi[:, 1] - lo[:, 1] + 1
    ends = np.cumsum(wx * wy)
    out = ([], [], [], [])
    start = 0
    while start < len(faces):
        # As many triangles as fit the budget, and always at least one.
        before = int(ends[start - 1]) if start else 0
        stop = max(start + 1, int(np.searchsorted(ends, before + budget, side="right")))
        part = slice(start, stop)
        a, b, c, low, width = pa[part], pb[part], pc[part], lo[part], wx[part]
        # intp: np.repeat takes nothing wider, and under Pyodide (32-bit) that is int32.
        counts = (width * wy[part]).astype(np.intp)
        tri = np.repeat(np.arange(stop - start), counts)
        k = np.arange(int(counts.sum())) - np.repeat(np.cumsum(counts) - counts, counts)
        x = low[tri, 0] + k % width[tri]
        y = low[tri, 1] + k // width[tri]
        p = np.stack([x + 0.5, y + 0.5], axis=1)
        v0, v1, v2 = b[tri] - a[tri], c[tri] - a[tri], p - a[tri]
        d = v0[:, 0] * v1[:, 1] - v1[:, 0] * v0[:, 1]
        ok = np.abs(d) > 1e-12
        d = np.where(ok, d, 1)
        w1 = (v2[:, 0] * v1[:, 1] - v1[:, 0] * v2[:, 1]) / d
        w2 = (v0[:, 0] * v2[:, 1] - v2[:, 0] * v0[:, 1]) / d
        w0 = 1 - w1 - w2
        inside = ok & (w0 >= -1e-4) & (w1 >= -1e-4) & (w2 >= -1e-4)
        # Compact types: at 4096 px there are over ten million texels.
        out[0].append(y[inside].astype(np.int32))
        out[1].append(x[inside].astype(np.int32))
        out[2].append((tri[inside] + start).astype(np.int32))
        out[3].append(np.stack([w0[inside], w1[inside], w2[inside]], axis=1).astype(np.float32))
        start = stop
    return tuple(np.concatenate(part) for part in out)


def sample(image, uvs):
    """Bilinear lookup; uvs with v up."""
    h, w = image.shape[:2]
    x = np.clip(uvs[:, 0] % 1.0 * w - 0.5, 0, w - 1)
    y = np.clip((1 - uvs[:, 1] % 1.0) * h - 0.5, 0, h - 1)
    x0, y0 = np.floor(x).astype(int), np.floor(y).astype(int)
    x1, y1 = np.minimum(x0 + 1, w - 1), np.minimum(y0 + 1, h - 1)
    fx, fy = (x - x0)[:, None], (y - y0)[:, None]
    fx, fy = fx.astype(np.float32), fy.astype(np.float32)
    px = lambda yy, xx: image[yy, xx].astype(np.float32)  # noqa: E731 - the image stays 8-bit; only the texels asked for are widened
    return ((px(y0, x0) * (1 - fx) + px(y0, x1) * fx) * (1 - fy) + (px(y1, x0) * (1 - fx) + px(y1, x1) * fx) * fy) / 255


def seam_fill(mask, reach=16):
    """For every texel within `reach` of a baked one, the index of the nearest baked texel.
    Filling the empty space around UV islands with their edge colour keeps
    texture filtering at a seam from mixing in the background. One distance
    transform serves every map.
    """
    distance, (iy, ix) = ndimage.distance_transform_edt(~mask, return_indices=True)
    near = ~mask & (distance <= reach)
    return near, iy[near], ix[near]


def source_look(high):
    """What the original looks like: colour and metallic/roughness as lookups by (face, barycentrics)."""
    visual = high.visual
    material = getattr(visual, "material", None)
    uv = getattr(visual, "uv", None)
    color_image = getattr(material, "baseColorTexture", None) if material is not None else None
    if color_image is None and material is not None:
        color_image = getattr(material, "image", None)
    mr_image = getattr(material, "metallicRoughnessTexture", None) if material is not None else None
    factor = np.array(getattr(material, "baseColorFactor", None) if material is not None and getattr(material, "baseColorFactor", None) is not None else [255, 255, 255, 255], dtype=np.float64)
    factor = factor / 255 if factor.max() > 1 else factor

    color_px = np.asarray(color_image.convert("RGBA")) if color_image is not None and uv is not None else None
    mr_px = np.asarray(mr_image.convert("RGB")) if mr_image is not None and uv is not None else None
    vertex_colors = None
    if color_px is None and hasattr(visual, "vertex_colors") and getattr(visual, "kind", None) == "vertex":
        vertex_colors = np.asarray(visual.vertex_colors, dtype=np.float64) / 255

    def lookup(face, bc):
        corners = high.faces[face]
        # A model may carry a metallic/roughness texture without a colour one.
        at = np.einsum("nk,nkd->nd", bc, uv[corners]) if color_px is not None or mr_px is not None else None
        if color_px is not None:
            color = sample(color_px, at) * factor
        elif vertex_colors is not None:
            color = np.einsum("nk,nkd->nd", bc, vertex_colors[corners])
        else:
            color = np.tile(factor, (len(face), 1))
        return color, sample(mr_px, at) if mr_px is not None else None

    return lookup, mr_px is not None


# Texels baked at a time. Each one passes through some fifty numbers on the way
# (its point, frame, nearest source point, colour), so all of a 4096 px map at
# once is several gigabytes: more than a browser tab's Python can have at all.
BAKE_CHUNK = 400_000


def to_bytes(values):
    return (np.clip(values, 0, 1) * 255 + 0.5).astype(np.uint8)


def bake(positions, normals, tangents, uvs, faces, high, size, step=None):
    rows, cols, tri, bary = rasterize(uvs, faces, size)
    lookup, has_mr = source_look(high)
    high_v = np.asarray(high.vertices, dtype=np.float64)
    high_f = np.asarray(high.faces)
    high_normals = np.asarray(high.vertex_normals)

    # The maps as they are stored, 8 bits a channel, filled chunk by chunk.
    color_map = np.zeros((size, size, 4), dtype=np.uint8)
    color_map[..., 3] = 255
    normal_map = np.empty((size, size, 3), dtype=np.uint8)
    normal_map[:] = (128, 128, 255)
    mr_map = None
    if has_mr:
        mr_map = np.zeros((size, size, 3), dtype=np.uint8)
        mr_map[..., 1] = 255

    for start in range(0, len(tri), BAKE_CHUNK):
        # Said per chunk: a large map takes a while, and silence reads as stuck.
        if step:
            step(0.5 + 0.4 * start / len(tri), "Baking textures from the original")
        part = slice(start, start + BAKE_CHUNK)
        y, x, b = rows[part], cols[part], bary[part].astype(np.float64)
        corners = faces[tri[part]]
        point = np.einsum("nk,nkd->nd", b, positions[corners])
        n = np.einsum("nk,nkd->nd", b, normals[corners])
        n /= np.linalg.norm(n, axis=1, keepdims=True) + 1e-12
        t = np.einsum("nk,nkd->nd", b, tangents[corners, :3])
        t -= n * np.sum(t * n, axis=1, keepdims=True)
        t /= np.linalg.norm(t, axis=1, keepdims=True) + 1e-12
        bt = np.cross(n, t) * tangents[corners[:, 0], 3:4]

        # The original surface point nearest to each texel.
        _, face, bc = native.closest_points_on_mesh(point, high_v, high_f)
        color, mr = lookup(face, bc)

        high_n = np.einsum("nk,nkd->nd", bc, high_normals[high_f[face]])
        high_n /= np.linalg.norm(high_n, axis=1, keepdims=True) + 1e-12
        # Generated meshes carry patches wound the wrong way, whose normals point
        # inward. Seen from outside, a surface cannot face away from the new one.
        high_n *= np.where(np.sum(high_n * n, axis=1, keepdims=True) < 0, -1.0, 1.0)
        ts = np.stack([np.sum(high_n * t, 1), np.sum(high_n * bt, 1), np.sum(high_n * n, 1)], axis=1)
        ts[:, 2] = np.maximum(ts[:, 2], 0.05)
        ts /= np.linalg.norm(ts, axis=1, keepdims=True)

        color_map[y, x] = to_bytes(color)
        normal_map[y, x] = to_bytes(ts * 0.5 + 0.5)
        if mr_map is not None:
            mr_map[y, x] = to_bytes(mr)

    mask = np.zeros((size, size), dtype=bool)
    mask[rows, cols] = True
    near, from_y, from_x = seam_fill(mask)
    maps = {"color": color_map, "normal": normal_map}
    if mr_map is not None:
        maps["metallicRoughness"] = mr_map
    for img in maps.values():
        img[near] = img[from_y, from_x]
    return maps, mask.mean()


def to_image(array, mode):
    return Image.fromarray(array, mode)


def remesh(path, glb_out, obj_out=None, target_faces=10000, quads=True, texture_size=2048, progress=None):
    step = progress or (lambda fraction, text: None)
    timings = {}
    clock = time.perf_counter()

    def lap(name):
        nonlocal clock
        now = time.perf_counter()
        timings[name] = round(now - clock, 1)
        clock = now

    step(0.05, "Reading the model")
    high = load(path)
    lap("load")

    step(0.15, "Building the new topology")
    v, polys, tris, auto = new_surface(high, target_faces, quads, lambda text: step(0.15, text))
    welded_normals = trimesh.Trimesh(v, tris, process=False).vertex_normals
    lap("remesh")

    step(0.35, "Unwrapping UVs")
    vmap, faces, uvs = native.parametrize(v, tris)
    faces = faces.astype(np.int64)
    uvs = uvs.astype(np.float64)
    positions, normals = v[vmap], np.asarray(welded_normals)[vmap]
    tangents = vertex_tangents(positions, normals, uvs, faces)
    lap("uv")

    step(0.5, "Baking textures from the original")
    maps, coverage = bake(positions, normals, tangents, uvs, faces, high, texture_size, step)
    lap("bake")

    step(0.9, "Writing the files")
    write_glb(
        glb_out, positions, normals, tangents, uvs, faces,
        {
            "color": to_image(maps["color"], "RGBA"),
            "metallicRoughness": to_image(maps["metallicRoughness"], "RGB") if "metallicRoughness" in maps else None,
            "normal": to_image(maps["normal"], "RGB"),
        },
    )
    if obj_out:
        write_obj(obj_out, v, polys)
    lap("write")
    return {
        "faces": int(len(polys)),
        "quads": int((polys[:, -1] != polys[:, 0]).sum()) if polys.shape[1] == 4 else 0,
        "triangles": int(len(faces)),
        "vertices": int(len(v)),
        "uv_coverage": round(float(coverage), 3),
        "timings": timings,
        **({"auto": auto} if auto else {}),
    }


if __name__ == "__main__":
    import sys

    src, dst = sys.argv[1], sys.argv[2]
    target = int(sys.argv[3]) if len(sys.argv) > 3 else 0
    quads = (sys.argv[4] if len(sys.argv) > 4 else "quad") == "quad"
    size = int(sys.argv[5]) if len(sys.argv) > 5 else 2048
    print(remesh(src, dst, dst.replace(".glb", ".obj"), target, quads, size))

	"""
	Remesh a model: new clean topology (quads or even triangles) at a target face
	count, fresh UVs, and the original's look baked onto it.

	solid.py one sealed surface around the input, whatever its state,
	with parts thinner than a face widened to one face
	QuadriFlow quad remeshing of that surface (Instant Meshes if it fails)
	topology.py the result closed up: no holes, shards or tangled edges
	xatlas UVs for the new mesh
	bake per texel, the nearest point of the original: base colour,
	metallic/roughness, and a normal map carrying the detail the
	new mesh is too coarse to hold, in the tangents stored in the
	file so every renderer shades it the way it was baked
	"""

	import os
	import time

	import numpy as np
	import trimesh
	from PIL import Image
	from scipy import ndimage

	import native
	from glb import write_glb, write_obj
	from solid import grid_surface, near, solid_grid, thicken
	from topology import close_up, triangles, trouble


	def sniff(path):
	"""The format from the file itself, for uploads that lost their name on the way."""
	with open(path, "rb") as f:
	head = f.read(512)
	if head[:4] == b"glTF":
	return "glb"
	if head.startswith(b"ply"):
	return "ply"
	if head.lstrip().startswith(b"{"):
	return "gltf"
	text = head.decode("latin-1").lstrip()
	if text.startswith("solid") and b"facet" in head:
	return "stl"
	if any(line.split()[:1] in (["v"], ["vn"], ["vt"], ["f"], ["o"], ["g"], ["mtllib"], ["#"]) for line in text.splitlines() if line.strip()):
	return "obj"
	return "stl" # binary STL has no magic; it is the one format left


	# STL and PLY come from CAD, slicers and scanners, which are Z-up; glTF and
	# OBJ are Y-up. The results are a GLB and an OBJ, so a Z-up model is turned
	# upright on the way in: (x, y, z) -> (x, z, -y), the quarter turn about X that
	# the site's viewer and converters make (src/lib/mesh/axes.ts).
	Z_UP = ("stl", "ply")
	Z_UP_TO_Y_UP = np.array([[1, 0, 0, 0], [0, 0, 1, 0], [0, -1, 0, 0], [0, 0, 0, 1]], dtype=np.float64)


	def load(path):
	extension = os.path.splitext(path)[1].lower().lstrip(".")
	known = extension in ("glb", "gltf", "obj", "stl", "ply")
	kind = extension if known else sniff(path)
	scene = trimesh.load(path, force="scene") if known else trimesh.load(path, file_type=kind, force="scene")
	if len(scene.geometry) == 0:
	raise ValueError("The file has no mesh in it.")
	mesh = scene.to_geometry() if len(scene.geometry) == 1 else scene.dump(concatenate=True)
	if kind in Z_UP:
	mesh.apply_transform(Z_UP_TO_Y_UP)
	return mesh


	# Auto: quad counts tried in turn, and how far the new surface may stray from
	# the sealed one (99th percentile, as a share of the model's largest side).
	# At 0.4% the shape, faces included, reads as the same object; measured on generated
	# and scanned models, the count that takes ranges from a few thousand (a barrel)
	# to tens of thousands (a race car's thin spoilers), so no single default fits.
	AUTO_LADDER = [2000, 3500, 6000, 10000, 15000, 25000, 40000]
	AUTO_TOLERANCE = 0.004
	# A few small holes are filled cleanly; more corners than this on open or
	# tangled edges means a thin part came apart, and it is remeshed widened.
	TROUBLE = 24


	class Sealed:
	"""The model filled into voxels, and sealed surfaces made from it.

	Every surface is one closed piece whatever the input was, and sheets down
	to a voxel thick are kept (the smoothing would otherwise erase them).
	"""

	def __init__(self, mesh):
	self.grid, self.h, self.lo = solid_grid(np.asarray(mesh.vertices, dtype=np.float64), np.asarray(mesh.faces))
	self.grid = thicken(self.grid, 1.0)
	self.v, self.f = grid_surface(self.grid, self.h, self.lo)
	# The reference the result is measured against.
	reference = trimesh.Trimesh(self.v, self.f, process=False)
	self.area = float(reference.area)
	self.size = float((reference.bounds[1] - reference.bounds[0]).max())
	# Seeded, so a model gets the same count every time it is run.
	self.points, _ = trimesh.sample.sample_surface(reference, 10000, seed=0)

	def widened(self, quads, spots):
	"""The sealed surface with thin parts near `spots` made one face of `quads` thick.

	No remesher can lay faces on both sides of a sheet thinner than its
	edges: the sides snap together and leave holes and shards. Widening
	only where that happened leaves sharp edges elsewhere as they are.
	"""
	edge = np.sqrt(self.area / max(quads, 1))
	where = near(self.grid.shape, self.h, self.lo, spots, 3 * edge)
	return grid_surface(thicken(self.grid, max(1.5, 0.5 * edge / self.h), where), self.h, self.lo)

	def deviation(self, v, tris):
	"""99th percentile distance from the sealed model to (v, tris), as a share of the largest side."""
	return float(np.percentile(point_distances(self.points, v, tris), 99)) / self.size


	def quad_mesh(sealed_v, sealed_f, quads):
	"""About `quads` quads over a sealed surface: QuadriFlow, another seed, then Instant Meshes."""
	for seed in (0, 1):
	try:
	return native.quadriflow_remesh(sealed_v, sealed_f, quads, seed=seed)
	except RuntimeError as error:
	print(f"QuadriFlow, seed {seed}: {error}", flush=True)
	return native.instant_meshes(sealed_v, sealed_f, quads)


	def build(sealed, quads, as_quads):
	"""One new surface of about `quads` quads: (vertices, polygons, triangles).

	The result is closed and edge-manifold: tangled faces and loose shards the
	remesher leaves are removed and every hole is filled. As triangles, each
	quad is split along its shorter diagonal.
	"""
	v, polys = quad_mesh(sealed.v, sealed.f, quads)
	spots = trouble(v, polys)
	print(f"{quads} quads: {len(spots)} trouble spots", flush=True)
	if len(spots) > TROUBLE:
	# Thin parts came out broken: widen them to one face there and run again,
	# and keep whichever run, closed up, stays nearer the model.
	again_v, again_polys = quad_mesh(*sealed.widened(quads, spots), quads)
	first, second = close_up(v, polys), close_up(again_v, again_polys)
	pick = min((first, second), key=lambda c: sealed.deviation(c[0], triangles(c[1], c[0])))
	v, polys = pick[0], pick[1]
	v, polys, _ = close_up(v, polys)
	tris = triangles(polys, v)
	# Normals out: the enclosed volume must come out positive.
	a, b, c = v[tris[:, 0]], v[tris[:, 1]], v[tris[:, 2]]
	if np.einsum("ij,ij->i", a, np.cross(b, c)).sum() < 0:
	polys, tris = polys[:, ::-1].copy(), tris[:, ::-1].copy()
	if not as_quads:
	polys = tris
	return v, polys, tris


	def new_surface(mesh, target_faces, quads=True, note=None):
	"""Clean topology at about `target_faces`, from a sealed rebuild of the input.

	QuadriFlow needs a manifold input and generated meshes rarely are, so it
	remeshes the sealed surface instead. The look is baked from the original
	afterwards, so nothing of it is lost here.

	A target of 0 is Auto: the fewest faces on AUTO_LADDER whose surface stays
	within AUTO_TOLERANCE of the sealed one. Returns the surface and, for Auto,
	what was found: {"deviation": share of the size, "held": within tolerance}.
	"""
	sealed = Sealed(mesh)
	# Triangles come from splitting quads, two to a quad.
	per_quad = 1 if quads else 2
	if target_faces <= 0:
	return auto_surface(sealed, quads, note)
	want = max(50, int(target_faces / per_quad))
	# QuadriFlow lands a few percent under the count it is given.
	ask = int(want * 1.04)
	for _ in range(2):
	v, polys, tris = build(sealed, ask, quads)
	got = len(polys) / per_quad
	if abs(got - want) / want < 0.12:
	break
	ask = max(50, int(ask * want / max(got, 1)))
	return v, polys, tris, None


	def auto_surface(sealed, quads, note=None):
	"""The fewest quads on AUTO_LADDER that keep the shape.

	Each try is a full remesh, so the ladder is not walked from the bottom:
	the first try is in the middle, and how far it strays says where the
	count lies (the error shrinks about as the count grows to the power 0.75).
	From there it steps down while the shape holds, or up until it does.
	"""
	# Never more quads than the sealed surface has triangles over four: that would add, not clean.
	most = max(AUTO_LADDER[0], len(sealed.f) // 4)
	ladder = [count for count in AUTO_LADDER if count <= most] or AUTO_LADDER[:1]
	tried = {}

	def attempt(i):
	if i not in tried:
	started = time.perf_counter()
	if note:
	# Each try can take a while: say which one is running.
	note(f"Trying {ladder[i]:,} {'quads' if quads else 'triangles'}")
	v, polys, tris = build(sealed, ladder[i], quads)
	tried[i] = (sealed.deviation(v, tris), v, polys, tris)
	print(f"Auto: {ladder[i]} quads, {tried[i][0]:.4f} of the size, {time.perf_counter() - started:.0f} s", flush=True)
	return tried[i][0] <= AUTO_TOLERANCE

	i = min(range(len(ladder)), key=lambda k: abs(ladder[k] - 6000))
	if attempt(i):
	while i > 0 and attempt(i - 1):
	i -= 1
	else:
	guess = ladder[i] * (tried[i][0] / AUTO_TOLERANCE) ** (1 / 0.75)
	i = next((k for k in range(i + 1, len(ladder)) if ladder[k] >= 0.9 * guess), len(ladder) - 1)
	if attempt(i):
	# A jump may overshoot: take the step below if it holds too.
	while i > 0 and i - 1 not in tried and attempt(i - 1):
	i -= 1
	else:
	while i + 1 < len(ladder) and not attempt(i + 1):
	i += 1
	i = min(i + 1, len(ladder) - 1)
	deviation, v, polys, tris = tried[i]
	return v, polys, tris, {"deviation": round(deviation, 4), "held": deviation <= AUTO_TOLERANCE}


	def point_distances(points, v, tris):
	"""Distance from each point to the nearest point of the mesh (v, tris)."""
	distance, _, _ = native.closest_points_on_mesh(points, v, tris)
	return distance


	def vertex_tangents(positions, normals, uvs, faces):
	"""Per-vertex tangents with handedness, averaged over the triangles around each vertex."""
	p0, p1, p2 = (positions[faces[:, k]] for k in range(3))
	u0, u1, u2 = (uvs[faces[:, k]] for k in range(3))
	e1, e2, d1, d2 = p1 - p0, p2 - p0, u1 - u0, u2 - u0
	det = d1[:, 0] * d2[:, 1] - d2[:, 0] * d1[:, 1]
	r = np.where(np.abs(det) < 1e-14, 0.0, 1.0 / np.where(det == 0, 1, det))[:, None]
	t_face = (e1 * d2[:, 1:2] - e2 * d1[:, 1:2]) * r
	b_face = (e2 * d1[:, 0:1] - e1 * d2[:, 0:1]) * r
	t = np.zeros_like(positions)
	b = np.zeros_like(positions)
	for k in range(3):
	np.add.at(t, faces[:, k], t_face)
	np.add.at(b, faces[:, k], b_face)
	t -= normals * np.sum(t * normals, axis=1, keepdims=True)
	length = np.linalg.norm(t, axis=1, keepdims=True)
	# A vertex whose UVs give no direction gets any vector perpendicular to its normal.
	fallback = np.cross(normals, np.where(np.abs(normals[:, :1]) < 0.9, [[1.0, 0, 0]], [[0, 1.0, 0]]))
	fallback /= np.maximum(np.linalg.norm(fallback, axis=1, keepdims=True), 1e-12)
	t = np.where(length > 1e-12, t / np.maximum(length, 1e-12), fallback)
	w = np.where(np.sum(np.cross(normals, t) * b, axis=1) < 0, -1.0, 1.0)
	return np.concatenate([t, w[:, None]], axis=1)


	# Candidate texels tested at a time: every texel in each triangle's bounding box
	# passes through a dozen arrays, so a few large triangles on a 4096 px map
	# would otherwise be gigabytes in one go.
	RASTER_TEXELS = 1_500_000


	def rasterize(uvs, faces, size, budget=RASTER_TEXELS):
	"""Every texel centre inside a UV triangle, as (row, col, triangle, barycentrics)."""
	px = np.stack([uvs[:, 0] * size, (1 - uvs[:, 1]) * size], axis=1)
	pa, pb, pc = px[faces[:, 0]], px[faces[:, 1]], px[faces[:, 2]]
	lo = np.clip(np.floor(np.minimum(np.minimum(pa, pb), pc)), 0, size - 1).astype(np.int64)
	hi = np.clip(np.ceil(np.maximum(np.maximum(pa, pb), pc)), 0, size - 1).astype(np.int64)
	wx, wy = hi[:, 0] - lo[:, 0] + 1, hi[:, 1] - lo[:, 1] + 1
	ends = np.cumsum(wx * wy)
	out = ([], [], [], [])
	start = 0
	while start < len(faces):
	# As many triangles as fit the budget, and always at least one.
	before = int(ends[start - 1]) if start else 0
	stop = max(start + 1, int(np.searchsorted(ends, before + budget, side="right")))
	part = slice(start, stop)
	a, b, c, low, width = pa[part], pb[part], pc[part], lo[part], wx[part]
	# intp: np.repeat takes nothing wider, and under Pyodide (32-bit) that is int32.
	counts = (width * wy[part]).astype(np.intp)
	tri = np.repeat(np.arange(stop - start), counts)
	k = np.arange(int(counts.sum())) - np.repeat(np.cumsum(counts) - counts, counts)
	x = low[tri, 0] + k % width[tri]
	y = low[tri, 1] + k // width[tri]
	p = np.stack([x + 0.5, y + 0.5], axis=1)
	v0, v1, v2 = b[tri] - a[tri], c[tri] - a[tri], p - a[tri]
	d = v0[:, 0] * v1[:, 1] - v1[:, 0] * v0[:, 1]
	ok = np.abs(d) > 1e-12
	d = np.where(ok, d, 1)
	w1 = (v2[:, 0] * v1[:, 1] - v1[:, 0] * v2[:, 1]) / d
	w2 = (v0[:, 0] * v2[:, 1] - v2[:, 0] * v0[:, 1]) / d
	w0 = 1 - w1 - w2
	inside = ok & (w0 >= -1e-4) & (w1 >= -1e-4) & (w2 >= -1e-4)
	# Compact types: at 4096 px there are over ten million texels.
	out[0].append(y[inside].astype(np.int32))
	out[1].append(x[inside].astype(np.int32))
	out[2].append((tri[inside] + start).astype(np.int32))
	out[3].append(np.stack([w0[inside], w1[inside], w2[inside]], axis=1).astype(np.float32))
	start = stop
	return tuple(np.concatenate(part) for part in out)


	def sample(image, uvs):
	"""Bilinear lookup; uvs with v up."""
	h, w = image.shape[:2]
	x = np.clip(uvs[:, 0] % 1.0 * w - 0.5, 0, w - 1)
	y = np.clip((1 - uvs[:, 1] % 1.0) * h - 0.5, 0, h - 1)
	x0, y0 = np.floor(x).astype(int), np.floor(y).astype(int)
	x1, y1 = np.minimum(x0 + 1, w - 1), np.minimum(y0 + 1, h - 1)
	fx, fy = (x - x0)[:, None], (y - y0)[:, None]
	fx, fy = fx.astype(np.float32), fy.astype(np.float32)
	px = lambda yy, xx: image[yy, xx].astype(np.float32) # noqa: E731 - the image stays 8-bit; only the texels asked for are widened
	return ((px(y0, x0) * (1 - fx) + px(y0, x1) * fx) * (1 - fy) + (px(y1, x0) * (1 - fx) + px(y1, x1) * fx) * fy) / 255


	def seam_fill(mask, reach=16):
	"""For every texel within `reach` of a baked one, the index of the nearest baked texel.

	Filling the empty space around UV islands with their edge colour keeps
	texture filtering at a seam from mixing in the background. One distance
	transform serves every map.
	"""
	distance, (iy, ix) = ndimage.distance_transform_edt(~mask, return_indices=True)
	near = ~mask & (distance <= reach)
	return near, iy[near], ix[near]


	def source_look(high):
	"""What the original looks like: colour and metallic/roughness as lookups by (face, barycentrics)."""
	visual = high.visual
	material = getattr(visual, "material", None)
	uv = getattr(visual, "uv", None)
	color_image = getattr(material, "baseColorTexture", None) if material is not None else None
	if color_image is None and material is not None:
	color_image = getattr(material, "image", None)
	mr_image = getattr(material, "metallicRoughnessTexture", None) if material is not None else None
	factor = np.array(getattr(material, "baseColorFactor", None) if material is not None and getattr(material, "baseColorFactor", None) is not None else [255, 255, 255, 255], dtype=np.float64)
	factor = factor / 255 if factor.max() > 1 else factor

	color_px = np.asarray(color_image.convert("RGBA")) if color_image is not None and uv is not None else None
	mr_px = np.asarray(mr_image.convert("RGB")) if mr_image is not None and uv is not None else None
	vertex_colors = None
	if color_px is None and hasattr(visual, "vertex_colors") and getattr(visual, "kind", None) == "vertex":
	vertex_colors = np.asarray(visual.vertex_colors, dtype=np.float64) / 255

	def lookup(face, bc):
	corners = high.faces[face]
	# A model may carry a metallic/roughness texture without a colour one.
	at = np.einsum("nk,nkd->nd", bc, uv[corners]) if color_px is not None or mr_px is not None else None
	if color_px is not None:
	color = sample(color_px, at) * factor
	elif vertex_colors is not None:
	color = np.einsum("nk,nkd->nd", bc, vertex_colors[corners])
	else:
	color = np.tile(factor, (len(face), 1))
	return color, sample(mr_px, at) if mr_px is not None else None

	return lookup, mr_px is not None


	# Texels baked at a time. Each one passes through some fifty numbers on the way
	# (its point, frame, nearest source point, colour), so all of a 4096 px map at
	# once is several gigabytes: more than a browser tab's Python can have at all.
	BAKE_CHUNK = 400_000


	def to_bytes(values):
	return (np.clip(values, 0, 1) * 255 + 0.5).astype(np.uint8)


	def bake(positions, normals, tangents, uvs, faces, high, size, step=None):
	rows, cols, tri, bary = rasterize(uvs, faces, size)
	lookup, has_mr = source_look(high)
	high_v = np.asarray(high.vertices, dtype=np.float64)
	high_f = np.asarray(high.faces)
	high_normals = np.asarray(high.vertex_normals)

	# The maps as they are stored, 8 bits a channel, filled chunk by chunk.
	color_map = np.zeros((size, size, 4), dtype=np.uint8)
	color_map[..., 3] = 255
	normal_map = np.empty((size, size, 3), dtype=np.uint8)
	normal_map[:] = (128, 128, 255)
	mr_map = None
	if has_mr:
	mr_map = np.zeros((size, size, 3), dtype=np.uint8)
	mr_map[..., 1] = 255

	for start in range(0, len(tri), BAKE_CHUNK):
	# Said per chunk: a large map takes a while, and silence reads as stuck.
	if step:
	step(0.5 + 0.4 * start / len(tri), "Baking textures from the original")
	part = slice(start, start + BAKE_CHUNK)
	y, x, b = rows[part], cols[part], bary[part].astype(np.float64)
	corners = faces[tri[part]]
	point = np.einsum("nk,nkd->nd", b, positions[corners])
	n = np.einsum("nk,nkd->nd", b, normals[corners])
	n /= np.linalg.norm(n, axis=1, keepdims=True) + 1e-12
	t = np.einsum("nk,nkd->nd", b, tangents[corners, :3])
	t -= n * np.sum(t * n, axis=1, keepdims=True)
	t /= np.linalg.norm(t, axis=1, keepdims=True) + 1e-12
	bt = np.cross(n, t) * tangents[corners[:, 0], 3:4]

	# The original surface point nearest to each texel.
	_, face, bc = native.closest_points_on_mesh(point, high_v, high_f)
	color, mr = lookup(face, bc)

	high_n = np.einsum("nk,nkd->nd", bc, high_normals[high_f[face]])
	high_n /= np.linalg.norm(high_n, axis=1, keepdims=True) + 1e-12
	# Generated meshes carry patches wound the wrong way, whose normals point
	# inward. Seen from outside, a surface cannot face away from the new one.
	high_n = np.where(np.sum(high_n n, axis=1, keepdims=True) < 0, -1.0, 1.0)
	ts = np.stack([np.sum(high_n * t, 1), np.sum(high_n * bt, 1), np.sum(high_n * n, 1)], axis=1)
	ts[:, 2] = np.maximum(ts[:, 2], 0.05)
	ts /= np.linalg.norm(ts, axis=1, keepdims=True)

	color_map[y, x] = to_bytes(color)
	normal_map[y, x] = to_bytes(ts * 0.5 + 0.5)
	if mr_map is not None:
	mr_map[y, x] = to_bytes(mr)

	mask = np.zeros((size, size), dtype=bool)
	mask[rows, cols] = True
	near, from_y, from_x = seam_fill(mask)
	maps = {"color": color_map, "normal": normal_map}
	if mr_map is not None:
	maps["metallicRoughness"] = mr_map
	for img in maps.values():
	img[near] = img[from_y, from_x]
	return maps, mask.mean()


	def to_image(array, mode):
	return Image.fromarray(array, mode)


	def remesh(path, glb_out, obj_out=None, target_faces=10000, quads=True, texture_size=2048, progress=None):
	step = progress or (lambda fraction, text: None)
	timings = {}
	clock = time.perf_counter()

	def lap(name):
	nonlocal clock
	now = time.perf_counter()
	timings[name] = round(now - clock, 1)
	clock = now

	step(0.05, "Reading the model")
	high = load(path)
	lap("load")

	step(0.15, "Building the new topology")
	v, polys, tris, auto = new_surface(high, target_faces, quads, lambda text: step(0.15, text))
	welded_normals = trimesh.Trimesh(v, tris, process=False).vertex_normals
	lap("remesh")

	step(0.35, "Unwrapping UVs")
	vmap, faces, uvs = native.parametrize(v, tris)
	faces = faces.astype(np.int64)
	uvs = uvs.astype(np.float64)
	positions, normals = v[vmap], np.asarray(welded_normals)[vmap]
	tangents = vertex_tangents(positions, normals, uvs, faces)
	lap("uv")

	step(0.5, "Baking textures from the original")
	maps, coverage = bake(positions, normals, tangents, uvs, faces, high, texture_size, step)
	lap("bake")

	step(0.9, "Writing the files")
	write_glb(
	glb_out, positions, normals, tangents, uvs, faces,
	{
	"color": to_image(maps["color"], "RGBA"),
	"metallicRoughness": to_image(maps["metallicRoughness"], "RGB") if "metallicRoughness" in maps else None,
	"normal": to_image(maps["normal"], "RGB"),
	},
	)
	if obj_out:
	write_obj(obj_out, v, polys)
	lap("write")
	return {
	"faces": int(len(polys)),
	"quads": int((polys[:, -1] != polys[:, 0]).sum()) if polys.shape[1] == 4 else 0,
	"triangles": int(len(faces)),
	"vertices": int(len(v)),
	"uv_coverage": round(float(coverage), 3),
	"timings": timings,
	**({"auto": auto} if auto else {}),
	}


	if __name__ == "__main__":
	import sys

	src, dst = sys.argv[1], sys.argv[2]
	target = int(sys.argv[3]) if len(sys.argv) > 3 else 0
	quads = (sys.argv[4] if len(sys.argv) > 4 else "quad") == "quad"
	size = int(sys.argv[5]) if len(sys.argv) > 5 else 2048
	print(remesh(src, dst, dst.replace(".glb", ".obj"), target, quads, size))