Skip to content

armgit / Aleph

Public Imported from GitHub
0

Give satellite imagery, terrain data, buildings, streetview photos to your LLM

18.8 KB
Raw Blame
"""Google Earth 3D meshes: plan octree nodes, then join saved nodes into one glTF binary.

Earth Web streams photogrammetry as an octree of protobuf messages. BulkMetadata
lists nodes four levels at a time; NodeData holds a node's meshes with JPEG
textures. A finer node replaces one octant of its parent's mesh. Positions lie
on a sphere, onto which latitude and longitude map directly.
Protocol notes: https://github.com/retroplasma/earth-reverse-engineering
"""

import json
import math
import shutil
import struct
import tempfile

import numpy as np

from .common import atomic_path, fetch
from .geo import extent, near, within
from .pbf import fields, varints

BASE = "https://kh.google.com/rt/earth/"
LEAF, NODATA, USE_IMAGERY_EPOCH = 4, 8, 16
JPEG = 1
LOWEST, HIGHEST = -1000, 9000  # Heights searched for nodes, in meters from the sphere.
NEAR = 100_000  # Largest node half-diagonal, in meters, checked against the polygon; larger ones always count.
GLB_LIMIT = 2**32
TILES_PER_MESH = 64  # Unreal's Nanite allows 64 materials per mesh; Godot allows 256 surfaces.


def first(data):
    """Protobuf fields keeping the first value of repeated ones."""
    values = {}
    for number, value in fields(data):
        values.setdefault(number, value)
    return values


def dot(a, b):
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def frame(lat, lon):
    """East, north, and up unit vectors."""
    la, lo = math.radians(lat), math.radians(lon)
    return ((-math.sin(lo), math.cos(lo), 0.0),
            (-math.sin(la) * math.cos(lo), -math.sin(la) * math.sin(lo), math.cos(la)),
            (math.cos(la) * math.cos(lo), math.cos(la) * math.sin(lo), math.sin(la)))


def search_box(area, radius):
    """An oriented box around the rectangle, from below sea level to above the highest peaks."""
    south, west, north, east = area
    lat, lon = (south + north) / 2, (west + east) / 2
    axes = frame(lat, lon)
    half_east = half_north = drop = 0
    for y in (south, north, lat, min(max(0, south), north)):
        for x in (west, east, lon):
            up = frame(y, x)[2]
            point = [radius * (a - b) for a, b in zip(up, axes[2])]
            half_east = max(half_east, abs(dot(point, axes[0])))
            half_north = max(half_north, abs(dot(point, axes[1])))
            drop = max(drop, -dot(point, axes[2]))
    middle = (HIGHEST + LOWEST - drop) / 2
    center = tuple((radius + middle) * a for a in axes[2])
    return center, (half_east + 1, half_north + 1, (HIGHEST - LOWEST + drop) / 2), axes


def overlaps(a, b):
    """Separating-axis test for two oriented boxes: (center, half sizes, unit axes)."""
    (c1, h1, r1), (c2, h2, r2) = a, b
    d = (c2[0] - c1[0], c2[1] - c1[1], c2[2] - c1[2])
    axes = [*r1, *r2]
    for u in r1:
        for v in r2:
            w = (u[1] * v[2] - u[2] * v[1], u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0])
            if dot(w, w) > 1e-12:
                axes.append(w)
    return all(abs(dot(d, x)) <= sum(h * abs(dot(r, x)) for h, r in zip(h1 + h2, r1 + r2)) for x in axes)


def degrees(x, y, z):
    """Latitude and longitude of planet coordinates, as numbers or arrays; frame() goes the other way."""
    return np.degrees(np.arctan2(z, np.hypot(x, y))), np.degrees(np.arctan2(y, x))


def reaches(polygon, box):
    """Whether a node's box may hold ground in the polygon, judging by its center and half-diagonal."""
    center, half, _ = box
    size = math.hypot(*half)
    return size > NEAR or near(polygon, degrees(*center), size * 1.05 + 1)


def node_box(packed, head, texel):
    if len(packed) != 15:
        raise ValueError("Unexpected 3D mesh node bounds.")
    cx, cy, cz, ex, ey, ez, a0, a1, a2 = struct.unpack("<3h3B3H", packed)
    a0, a1, a2 = a0 * math.pi / 32768, a1 * math.pi / 65536, a2 * math.pi / 32768
    c0, s0, c1, s1, c2, s2 = math.cos(a0), math.sin(a0), math.cos(a1), math.sin(a1), math.cos(a2), math.sin(a2)
    axes = ((c0 * c2 - c1 * s0 * s2, c1 * c0 * s2 + c2 * s0, s2 * s1),
            (-c0 * s2 - c2 * c1 * s0, c0 * c1 * c2 - s0 * s2, c2 * s1),
            (s1 * s0, -c0 * s1, c1))
    center = (head[0] + cx * texel, head[1] + cy * texel, head[2] + cz * texel)
    return center, (ex * texel, ey * texel, ez * texel), axes


def bulk(data, head, epoch):
    """Yield (path, flags, epoch, bulk epoch, imagery epoch, box) for up to four levels below head."""
    nodes, center, texels, imagery = [], None, (), None
    for number, value in fields(data):
        if number == 1:
            nodes.append(value)
        elif number == 2:
            epoch = dict(fields(value)).get(2, epoch)
        elif number == 3:
            center = struct.unpack("<3d", value)
        elif number == 4:
            texels = struct.unpack(f"<{len(value) // 4}f", value)
        elif number == 5:
            imagery = value
    for raw in nodes:
        node = dict(fields(raw))
        packed = node[1]
        depth = 1 + (packed & 3)
        packed >>= 2
        path = head
        for _ in range(depth):
            path += str(packed & 7)
            packed >>= 3
        texel = struct.unpack("<f", node[4])[0] if 4 in node else texels[depth - 1]
        box = node_box(node[3], center, texel) if 3 in node else None
        yield path, packed, node.get(2, epoch), node.get(5, epoch), node.get(7, imagery), box


def plan(client, polygon, level, workers, progress, *, allow_empty=False):
    """Nodes with data meeting the polygon down to level, and the octants their children refine."""
    planet = dict(fields(client.get(BASE + "PlanetoidMetadata")))
    root = dict(fields(planet[1]))
    radius = struct.unpack("<f", planet[2])[0]
    target = search_box(extent(polygon), radius)
    found, existing = [], set()
    pending, done = [("", root.get(5, root[2]))], 0
    progress("Finding 3D mesh nodes", done)
    while pending:
        batch, pending = pending, []
        addresses = [f"{BASE}BulkMetadata/pb=!1m2!1s{path}!2u{epoch}" for path, epoch in batch]
        for (head, epoch), data in zip(batch, fetch(client, addresses, workers, missing_ok=True)):
            done += 1
            progress("Finding 3D mesh nodes", done)
            if data is None:
                continue
            hit = set()
            for path, flags, node_epoch, bulk_epoch, imagery, box in sorted(bulk(data, head, epoch),
                                                                             key=lambda node: len(node[0])):
                if not flags & NODATA:
                    existing.add(path)
                # Parents come first; skip subtrees outside the area.
                if ((len(path) > len(head) + 1 and path[:-1] not in hit) or len(path) > level
                        or box is None or not overlaps(target, box) or not reaches(polygon, box)):
                    continue
                hit.add(path)
                if not flags & NODATA:
                    found.append((path, node_epoch, imagery if flags & USE_IMAGERY_EPOCH else None))
                if len(path) == len(head) + 4 and len(path) < level and not flags & LEAF:
                    pending.append((path, bulk_epoch))
    # Children replace their parent's octant, even outside the area where cropping removes them.
    # Skip parents with every octant replaced: they would add no triangles.
    nodes = []
    for path, epoch, imagery in sorted(found):
        mask = sum(1 << k for k in range(8) if f"{path}{k}" in existing) if len(path) < level else 0
        if mask != 255:
            nodes.append([path, epoch, imagery, mask])
    if not nodes and not allow_empty:
        raise ValueError("No Google Earth 3D data in this area.")
    return dict(mode="mesh", level=level, radius=radius, nodes=nodes, results=[])


def address(node):
    path, epoch, imagery, _ = node
    return (f"{BASE}NodeData/pb=!1m2!1s{path}!2u{epoch}!2e{JPEG}"
            + ("" if imagery is None else f"!3u{imagery}") + "!4b0")


def check(data):
    """Reject responses that are not a node with a 4 × 4 transform."""
    if len(first(data).get(1, b"")) != 128:
        raise ValueError("Unexpected 3D mesh node data.")


def counted(data, name):
    """Packed integers preceded by their count."""
    values = varints(data).astype(np.int64)
    if not values.size or values.size != values[0] + 1:
        raise ValueError(f"Unexpected 3D mesh {name}.")
    return values[1:]


def fitted(values, size):
    """Truncate or zero-pad to size."""
    return np.pad(values[:size], (0, max(0, size - len(values))))


def decode(data, mask, axes, radius, inside):
    """Yield (positions, texture coordinates, triangles, JPEG) per mesh, in local meters.

    Keeps the three base layers, without skirts, octants in mask, or triangles centered outside.
    """
    matrix, meshes = None, []
    for number, value in fields(data):
        if number == 1:
            matrix = struct.unpack("<16d", value)
        elif number == 2:
            meshes.append(value)
    if not meshes:
        return
    if matrix is None:
        raise ValueError("Unexpected 3D mesh node data.")
    # Fold the column-major globe transform into the move to east/north/up around the origin.
    rows = [[dot(axis, matrix[4 * j:4 * j + 3]) for j in range(4)] for axis in axes]
    rows[2][3] -= radius
    (a0, a1, a2, at), (b0, b1, b2, bt), (c0, c1, c2, ct) = rows
    for raw in meshes:
        mesh, offsets = {}, b""
        for number, value in fields(raw):
            if number == 10:
                offsets += value  # Four floats, packed or not.
            else:
                mesh.setdefault(number, value)
        vertices, uv = mesh.get(1, b""), mesh.get(7, b"")
        count = len(vertices) // 3
        if not count or len(vertices) != 3 * count or len(uv) != 4 + 4 * count:
            raise ValueError("Unexpected 3D mesh vertices.")
        texture = first(mesh.get(6, b""))
        if 1 not in texture or texture.get(2, JPEG) != JPEG:
            raise ValueError("Unexpected 3D mesh texture.")

        xs, ys, zs = np.cumsum(np.frombuffer(vertices, np.uint8).reshape(3, count), axis=1, dtype=np.uint8).astype(float)
        east = a0 * xs + a1 * ys + a2 * zs + at
        north = b0 * xs + b1 * ys + b2 * zs + bt
        up = c0 * xs + c1 * ys + c2 * zs + ct
        u_mod, v_mod = 1 + uv[0] + (uv[1] << 8), 1 + uv[2] + (uv[3] << 8)
        # Four byte planes: low u, low v, high u, high v.
        planes = np.frombuffer(uv, np.uint8, offset=4).reshape(4, count).astype(np.int64)
        if len(offsets) == 16:
            u_offset, v_offset, u_scale, v_scale = struct.unpack("<4f", offsets)
        else:
            u_offset, v_offset, u_scale, v_scale = 0.5, 0.5, 1 / u_mod, 1 / v_mod
        us = (np.cumsum(planes[0] | planes[2] << 8) % u_mod + u_offset) * u_scale
        vs = (np.cumsum(planes[1] | planes[3] << 8) % v_mod + v_offset) * v_scale

        # A zero index adds the next new vertex; others count back from the newest.
        values = counted(mesh.get(3, b""), "indices")
        new = values == 0
        strip = np.cumsum(new) - new - values
        if new.sum() > count or (strip.size and strip.min() < 0):
            raise ValueError("Unexpected 3D mesh indices.")
        # Runs cycle through eight octants per layer; trailing positions belong to no drawn layer.
        runs = counted(mesh.get(8, b""), "octants")
        layers = np.arange(runs.size)
        keep = fitted(np.repeat((layers < 24) & ~(mask >> (layers & 7) & 1).astype(bool), runs), strip.size)
        skirts = fitted(np.unpackbits(np.frombuffer(mesh.get(13, b""), np.uint8), bitorder="little"), strip.size)
        a, b, c = strip[:-2], strip[1:-1], strip[2:]
        drawn = (keep[2:].astype(bool) & ~skirts[:-2].astype(bool) & (a != b) & (b != c) & (c != a)
                 & inside((east[a] + east[b] + east[c]) / 3, (north[a] + north[b] + north[c]) / 3,
                          (up[a] + up[b] + up[c]) / 3))
        # Odd triangles in a strip are wound the other way.
        odd = np.arange(a.size) % 2 == 1
        triangles = np.stack((a, np.where(odd, c, b), np.where(odd, b, c)), axis=1)[drawn].ravel()
        if not triangles.size:
            continue
        # Vertices in order of first use.
        unique, first_use = np.unique(triangles, return_index=True)
        used = unique[np.argsort(first_use)]
        index = np.empty(count, np.int64)
        index[used] = np.arange(used.size)
        # glTF is Y-up: x east, y up, z south.
        positions = np.stack((east[used], up[used], -north[used]), axis=1).astype(np.float32)
        texcoords = np.stack((us[used], vs[used]), axis=1).astype(np.float32)
        indices = index[triangles].astype(np.uint16 if used.size <= 65536 else np.uint32)
        yield positions, texcoords, indices, texture[1]


def crop(polygon, axes, radius):
    """A test for local east/north/up points inside the polygon."""
    (ex, ey, ez), (nx, ny, nz), (ux, uy, uz) = axes

    def inside(e, n, u):
        r = radius + u
        x, y, z = ex * e + nx * n + ux * r, ey * e + ny * n + uy * r, ez * e + nz * n + uz * r
        return within(polygon, *degrees(x, y, z))

    return inside


def export(path, folder, stage, polygon, progress):
    """Join saved nodes into one glTF binary in a local east/north/up frame around the center.

    Each glTF mesh holds up to TILES_PER_MESH textured tiles from one octree block, named after
    its first tile: viewers import few objects, and Blender's import slows with many per mesh.
    """
    nodes, results = stage["nodes"], stage["results"]
    radius, block = stage["radius"], max(1, stage["level"] - 4)
    area = extent(polygon)
    lat, lon = (area[0] + area[2]) / 2, (area[1] + area[3]) / 2
    axes = frame(lat, lon)
    inside = crop(polygon, axes, radius)
    # Keep parent octants whose child was unavailable, so gaps stay covered.
    missing = {node[0] for node, result in zip(nodes, results) if result.get("status") == "skipped"}
    saved = [(node, result["filename"]) for node, result in zip(nodes, results) if "filename" in result]
    gltf = dict(
        asset=dict(version="2.0", generator="Aleph", copyright="© Google"),
        scene=0, scenes=[dict(nodes=[])], nodes=[], meshes=[], materials=[], textures=[], images=[],
        accessors=[], bufferViews=[], samplers=[dict(magFilter=9729, minFilter=9987, wrapS=33071, wrapT=33071)],
        extensionsUsed=["KHR_materials_unlit"],
    )
    progress("Building mesh.glb", 0, len(saved))
    with tempfile.TemporaryFile(dir=folder) as spool:
        def view(data, target=None):
            if isinstance(data, np.ndarray):
                data = data.astype(data.dtype.newbyteorder("<")).tobytes()
            gltf["bufferViews"].append(dict(buffer=0, byteOffset=spool.tell(), byteLength=len(data),
                                            **({"target": target} if target else {})))
            spool.write(data + b"\0" * (-len(data) % 4))
            if spool.tell() >= GLB_LIMIT:
                raise ValueError("The 3D mesh exceeds the 4 GiB glTF limit. Use a smaller area or lower mesh level.")
            return len(gltf["bufferViews"]) - 1

        # Nodes are sorted by path, so each block's nodes are consecutive.
        key = None
        for done, (node, filename) in enumerate(saved, 1):
            mask = node[3] & ~sum(1 << k for k in range(8) if f"{node[0]}{k}" in missing)
            data = (folder / filename).read_bytes()
            for part, (positions, texcoords, indices, jpeg) in enumerate(decode(data, mask, axes, radius, inside)):
                i, k = len(gltf["materials"]), len(gltf["accessors"])
                name = node[0] if not part else f"{node[0]}-{part}"
                gltf["accessors"] += [
                    dict(bufferView=view(positions, 34962), componentType=5126, count=len(positions),
                         type="VEC3", min=positions.min(axis=0).tolist(), max=positions.max(axis=0).tolist()),
                    dict(bufferView=view(texcoords, 34962), componentType=5126, count=len(texcoords),
                         type="VEC2"),
                    dict(bufferView=view(indices, 34963), componentType=5123 if indices.dtype == np.uint16 else 5125,
                         count=len(indices), type="SCALAR"),
                ]
                gltf["images"].append(dict(bufferView=view(jpeg), mimeType="image/jpeg"))
                gltf["textures"].append(dict(source=i, sampler=0))
                gltf["materials"].append(dict(name=name, doubleSided=True, extensions={"KHR_materials_unlit": {}},
                                              pbrMetallicRoughness=dict(baseColorTexture=dict(index=i),
                                                                        metallicFactor=0, roughnessFactor=1)))
                if node[0][:block] != key or len(gltf["meshes"][-1]["primitives"]) == TILES_PER_MESH:
                    key = node[0][:block]
                    gltf["meshes"].append(dict(name=name, primitives=[]))
                gltf["meshes"][-1]["primitives"].append(dict(
                    attributes=dict(POSITION=k, TEXCOORD_0=k + 1), indices=k + 2, material=i))
            progress("Building mesh.glb", done, len(saved))
        if not gltf["meshes"]:
            return
        gltf["nodes"] = [dict(name=mesh["name"], mesh=i) for i, mesh in enumerate(gltf["meshes"])]
        gltf["scenes"][0]["nodes"] = list(range(len(gltf["meshes"])))

        # Rest the lowest point on y = 0, so viewers orbit and zoom around the ground, not sea level.
        positions = [accessor for accessor in gltf["accessors"] if accessor["type"] == "VEC3"]
        base = min(accessor["min"][1] for accessor in positions)
        for accessor in positions:
            span = gltf["bufferViews"][accessor["bufferView"]]
            spool.seek(span["byteOffset"])
            values = np.frombuffer(spool.read(span["byteLength"]), "<f4").reshape(-1, 3).copy()
            # Subtract in double precision, then round once to float32.
            values[:, 1] = values[:, 1].astype(float) - base
            accessor["min"][1], accessor["max"][1] = float(values[:, 1].min()), float(values[:, 1].max())
            spool.seek(span["byteOffset"])
            spool.write(values.tobytes())
        spool.seek(0, 2)
        gltf["asset"]["extras"] = dict(
            latitude=lat, longitude=lon, base=base, radius=radius, bounds=list(area),
            frame="meters east (x), up (y), and south (z) of the center; y = 0 is the lowest point, base meters above sea level")
        size = spool.tell()
        gltf["buffers"] = [dict(byteLength=size)]
        header = json.dumps(gltf, ensure_ascii=False, separators=(",", ":")).encode()
        header += b" " * (-len(header) % 4)
        total = 28 + len(header) + size
        if total >= GLB_LIMIT:
            raise ValueError("The 3D mesh exceeds the 4 GiB glTF limit. Use a smaller area or lower mesh level.")
        with atomic_path(path) as temporary, temporary.open("wb") as output:
            output.write(struct.pack("<III", 0x46546C67, 2, total))
            output.write(struct.pack("<II", len(header), 0x4E4F534A) + header)
            output.write(struct.pack("<II", size, 0x004E4942))
            spool.seek(0)
            shutil.copyfileobj(spool, output)