"""Enclose the smallest orthographic shadow of a binary STL.

Run with Python 3, NumPy, and SciPy:

    python verify_projected_area.py "path/to/model.stl"

All lengths use the STL's coordinate unit. STL does not specify a unit.
The reported areas are in squared coordinate units.

The upper bound is the projected convex hull at one explicit direction.
The projected union is also computed to estimate the best observed area.
The lower bound uses an inscribed convex polytope. Move selected convex-hull
planes inward until each source triangle is outside at least one plane.
The source mesh is a closed, consistently oriented triangular surface, and
an exact integer ray test verifies that the common center is inside it.
The moved halfspace intersection is connected, contains that center, and
its interior meets none of the triangles. It is therefore inside the mesh.

For a convex polytope, orthographic area equals half the sum, over facets,
of the absolute area-vector dot products with the viewing direction.
The signs of those dot products partition the sphere into regions.
On each region the area is linear in the direction, and its minimum
occurs at a corner. To see this, write a unit direction as a positive
combination of the region's unit corner rays. Its coefficients sum to
at least 1, so the linear area's value is at least the smallest ray value.
The corners are intersections of facet-normal great circles. We enumerate
cross-products of all moved plane normals, including redundant planes.

The source-center test, inner sample containment, inner supporting facets,
and viewed outer polygon use exact integer predicates. Qhull proposes
geometry for verification. The directional lower scan uses double precision
with an explicit conservative allowance for arithmetic. The localized
union estimates are double-precision measurements, not a uniqueness proof.
"""
from collections import defaultdict
from decimal import Context, Decimal, ROUND_CEILING, ROUND_FLOOR
from functools import reduce
from math import gcd
from fractions import Fraction
from itertools import product
from pathlib import Path
import argparse
import struct

import numpy as np
from scipy.optimize import minimize
from scipy.spatial import ConvexHull, HalfspaceIntersection


def unit(vector):
    vector = np.asarray(vector, dtype=float)
    return vector / np.linalg.norm(vector)


def read_stl(path):
    data = path.read_bytes()
    if len(data) < 84:
        raise ValueError("The file is shorter than a binary STL header.")
    number = struct.unpack_from("<I", data, 80)[0]
    if len(data) != 84 + 50 * number:
        raise ValueError("This verifier expects a binary STL with no trailing data.")
    stl = np.dtype([("normal", "<f4", (3,)), ("v", "<f4", (3, 3)), ("attr", "<u2")])
    triangles = np.frombuffer(data, stl, offset=84)["v"].astype(np.float64)
    vertices, vertex_index = np.unique(triangles.reshape(-1, 3), axis=0, return_inverse=True)
    face_index = vertex_index.reshape(-1, 3)
    if not np.isfinite(vertices).all():
        raise ValueError("The STL contains a nonfinite coordinate.")
    center = (vertices.min(axis=0) + vertices.max(axis=0)) / 2
    vertices -= center
    triangles = vertices[face_index]
    edge_use = defaultdict(list)
    for index, (a, b, c) in enumerate(face_index):
        for start, end in ((a, b), (b, c), (c, a)):
            edge_use[tuple(sorted((start, end)))].append((index, start < end))
    if not all(len(pair) == 2 and pair[0][1] != pair[1][1] for pair in edge_use.values()):
        raise ValueError("The STL needs consistent orientation and exactly two faces on every edge.")
    raw_normals = np.cross(triangles[:, 1] - triangles[:, 0], triangles[:, 2] - triangles[:, 0])
    if not np.all(np.linalg.norm(raw_normals, axis=1) > 0):
        raise ValueError("The STL contains a degenerate triangular face.")
    signed_volume = np.einsum("ij,ij->i", raw_normals, triangles[:, 0]).sum() / 6
    if signed_volume <= 0:
        raise ValueError("The STL needs outward orientation.")
    return triangles, vertices, face_index, raw_normals, edge_use, signed_volume


def subtract(a, b):
    return tuple(x - y for x, y in zip(a, b))


def cross(a, b):
    return a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0]


def dot(a, b):
    return sum(x * y for x, y in zip(a, b))


def scale(a, multiplier):
    return tuple(multiplier * x for x in a)


def integer_points(points):
    """Write binary64 data as integer vectors over a common dyadic divisor."""
    exact = [tuple(Fraction(float(component)) for component in point) for point in points]
    denominator = max(t.denominator for point in exact for t in point)
    coordinates = [tuple(int(component * denominator) for component in point) for point in exact]
    return coordinates, denominator


def inside_center(vertices, face_index):
    """Use exact integers to count intersections of a rational ray."""
    coordinates, _ = integer_points(vertices)
    ray = (16, 7, 3)
    count = 0
    for indices in face_index:
        a, b, c = (coordinates[i] for i in indices)
        normal = cross(subtract(b, a), subtract(c, a))
        numerator = dot(normal, a)
        if numerator <= 0:
            raise ValueError("The bounding-box center is not strictly inward of every oriented face.")
        divisor = dot(normal, ray)
        if divisor <= 0:
            continue
        intersection = scale(ray, numerator)
        side = [
            dot(cross(subtract(end, start), subtract(intersection, scale(start, divisor))), normal)
            for start, end in ((a, b), (b, c), (c, a))
        ]
        if min(side) < 0:
            continue
        if min(side) == 0:
            raise ValueError("The test ray hit an edge. Choose another rational ray.")
        count += 1
    if count != 1:
        raise ValueError(f"Expected one exact ray crossing from the center, got {count}.")
    return count


def convex_area_vectors(vertices, hull):
    faces = vertices[hull.simplices]
    return 0.5 * np.cross(faces[:, 1] - faces[:, 0], faces[:, 2] - faces[:, 0])


def pair_directions(normals, index):
    left = normals[index]
    exact = [cross(left, right) for right in normals[index + 1:]]
    rays = np.asarray([ray for ray in exact if any(ray)], dtype=np.float64).reshape(-1, 3)
    return rays / np.linalg.norm(rays, axis=1)[:, None]


def convex_minimum(normals, area_vectors, relative_seed_margin=None):
    exact_normals, _ = integer_points(normals)
    best_area = np.inf
    direction = None
    examined = 0
    nearby = []
    for index in range(len(normals) - 1):
        rays = pair_directions(exact_normals, index)
        if not len(rays):
            continue
        areas = 0.5 * np.abs(rays @ area_vectors.T).sum(axis=1)
        index_min = areas.argmin()
        if areas[index_min] < best_area:
            best_area = areas[index_min]
            direction = rays[index_min].copy()
        examined += len(areas)
        if relative_seed_margin is not None:
            threshold = best_area * (1 + relative_seed_margin)
            nearby.extend((area, ray.copy()) for area, ray in zip(areas, rays) if area < threshold)
    if relative_seed_margin is not None:
        nearby = [(area, ray) for area, ray in nearby if area < best_area * (1 + relative_seed_margin)]
    return best_area, direction, examined, nearby


def inscribed_sample_hull(triangles, hull_planes):
    normals = hull_planes[:, :3]
    outer_offsets = -hull_planes[:, 3]
    if np.min(outer_offsets) <= 0:
        raise ValueError("The center does not lie inside the convex hull.")

    # Assign each triangle to a single plane. The minimum over its vertices
    # is the minimum over the whole triangle, by linearity.
    flat_triangles = triangles.reshape(-1, 3)
    distances = (flat_triangles @ normals.T).reshape(len(triangles), 3, -1).min(axis=1)
    assignment = np.argmin(outer_offsets[None, :] - distances, axis=1)
    offsets = outer_offsets.copy()
    np.minimum.at(offsets, assignment, distances[np.arange(len(triangles)), assignment] - 1e-8)
    moved_planes, _ = integer_points(np.column_stack((normals, offsets)))
    if any(plane[3] <= 0 for plane in moved_planes):
        raise ValueError("The moved planes exclude the center.")

    exact_triangles, scale_triangles = integer_points(flat_triangles)
    for index, plane_index in enumerate(assignment):
        x, y, z, limit = moved_planes[plane_index]
        for a, b, c in exact_triangles[index * 3:index * 3 + 3]:
            if x * a + y * b + z * c <= limit * scale_triangles:
                raise RuntimeError("The exact triangle-separation test failed.")

    intersections = HalfspaceIntersection(np.column_stack((normals, -offsets)), np.zeros(3),
                                         qhull_options="Qx").intersections
    # The small inward shrink leaves room for a grid whose exact convex
    # facets are easy to check. Grid points inside every moved plane suffice
    # even if Qhull's approximated intersection list were incomplete.
    scale_samples = 2**26
    samples_i = np.unique(np.rint(intersections * ((1 - 1e-8) * scale_samples)).astype(np.int64),
                          axis=0)
    samples = samples_i.astype(np.float64) / scale_samples
    samples_exact = samples_i.tolist()
    for a, b, c, limit in moved_planes:
        if any(a * x + b * y + c * z >= limit * scale_samples for x, y, z in samples_exact):
            raise RuntimeError("A sample does not lie strictly inside the moved planes.")

    sample_hull = ConvexHull(samples)
    facets = []
    seen_planes = set()
    for simplex in sample_hull.simplices:
        a, b, c = (samples_exact[index] for index in simplex)
        normal = cross(subtract(b, a), subtract(c, a))
        offset = dot(normal, a)
        if offset < 0:
            normal, offset = scale(normal, -1), -offset
        if offset == 0:
            raise RuntimeError("A proposed sample facet is degenerate or goes through the center.")
        x, y, z = normal
        if any(x * u + y * v + z * w > offset for u, v, w in samples_exact):
            raise RuntimeError("A proposed sample facet is not a supporting facet.")
        coefficients = (*normal, offset)
        factor = reduce(gcd, coefficients)
        key = tuple(value // factor for value in coefficients)
        if key in seen_planes:
            raise RuntimeError("A supporting plane has multiple triangles. Check that they partition it.")
        seen_planes.add(key)
        facets.append(normal)
    # Each verified triangle belongs to a distinct supporting plane.
    # Therefore its area contributes to the convex sample hull formula,
    # without requiring that the proposed triangles exhaust its boundary.
    lower_area_vectors = np.asarray(facets, dtype=np.float64) / (2 * scale_samples**2)
    return lower_area_vectors


def outward_hull_area(vertices, direction):
    """Upper-rounded area of the exact convex projection at a dyadic ray."""
    coordinates, denominator = integer_points(vertices)
    (n,), _ = integer_points([direction])
    axes = ((1, 0, 0), (0, 1, 0), (0, 0, 1))
    u = cross(n, axes[np.abs(direction).argmin()])
    v = cross(n, u)
    pts = sorted(set((dot(p, u), dot(p, v)) for p in coordinates))

    def hull_chain(sequence):
        result = []
        for x, y in sequence:
            while len(result) >= 2:
                a, b = result[-2:]
                determinant = (b[0] - a[0]) * (y - a[1]) - (b[1] - a[1]) * (x - a[0])
                if determinant > 0:
                    break
                result.pop()
            result.append((x, y))
        return result

    polygon = hull_chain(pts)[:-1] + hull_chain(reversed(pts))[:-1]
    doubled_area = sum(x * v - y * u for (x, y), (u, v) in zip(polygon, polygon[1:] + polygon[:1]))
    norm_product = dot(u, u) * dot(v, v)
    floor = Context(prec=45, rounding=ROUND_FLOOR)
    ceil = Context(prec=45, rounding=ROUND_CEILING)
    root_lower = floor.next_minus(floor.sqrt(Decimal(norm_product)))
    base = floor.multiply(Decimal(2 * denominator**2), root_lower)
    return ceil.divide(Decimal(doubled_area), base)


def projected_union_area(vertices, face_normals, edge_array, edge_faces, edge_order, direction):
    """Integrate the positive winding intervals of the projected front mesh."""
    n = unit(direction)
    first_axis = unit(np.cross(n, np.eye(3)[np.abs(n).argmin()]))
    xy = vertices @ np.column_stack((first_axis, np.cross(n, first_axis)))
    front = face_normals @ n > 0
    included = front[edge_faces[:, 0]] != front[edge_faces[:, 1]]
    orientation = front[edge_faces[:, 0]][included] == edge_order[included]
    ij = edge_array[included]
    a, b = xy[ij[:, 0]], xy[ij[:, 1]]
    first = np.where(orientation[:, None], a, b)
    last = np.where(orientation[:, None], b, a)
    edge = last - first

    # Front-face shared edges cancel. Split the remaining oriented edges
    # into sweep slabs at endpoints and crossing abscissae. Edge order is
    # constant in each slab; its occupied length is affine in x.
    i, j = np.triu_indices(len(edge), 1)

    def cross_2d(u, v):
        return u[:, 0] * v[:, 1] - u[:, 1] * v[:, 0]

    denominator = cross_2d(edge[i], edge[j])
    finite = np.abs(denominator) > 1e-15
    i, j, denominator = i[finite], j[finite], denominator[finite]
    gap = first[j] - first[i]
    t = cross_2d(gap, edge[j]) / denominator
    s = cross_2d(gap, edge[i]) / denominator
    crossing = (0 < t) & (t < 1) & (0 < s) & (s < 1)
    events = np.unique(np.concatenate((first[:, 0], last[:, 0],
                                       first[i[crossing], 0] + t[crossing] * edge[i[crossing], 0])))
    widths = np.diff(events)
    valid = widths > 1e-14
    widths = widths[valid]
    centers = 0.5 * (events[1:] + events[:-1])[valid]
    left = np.minimum(first[:, 0], last[:, 0])
    right = np.maximum(first[:, 0], last[:, 0])
    active = (left[None, :] < centers[:, None]) & (centers[:, None] < right[None, :])
    slopes = np.divide(edge[:, 1], edge[:, 0], out=np.zeros(len(edge)), where=edge[:, 0] != 0)
    heights = first[:, 1] + (centers[:, None] - first[:, 0]) * slopes
    order = np.argsort(heights, axis=1)
    signed = np.sign(edge[:, 0]) * active
    levels = np.cumsum(np.take_along_axis(signed, order, axis=1), axis=1)
    if not np.all(levels[:, -1] == 0):
        raise RuntimeError("Projected contour winding did not close.")
    lengths = np.diff(np.take_along_axis(heights, order, axis=1), axis=1)
    return float(widths @ np.sum(np.where(levels[:, :-1] > 0, lengths, 0), axis=1))


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("stl", type=Path)
    args = parser.parse_args()
    triangles, vertices, indices, face_normals, edge_use, volume = read_stl(args.stl)
    print(f"{len(triangles)} triangles, {len(vertices)} vertices, {len(edge_use)} edges.", flush=True)
    print(f"Exact inside-center ray test: {inside_center(vertices, indices)} crossing.", flush=True)
    hull = ConvexHull(vertices)
    normals = hull.equations[:, :3]
    hull_min, hull_n, outer_rays, seeds = convex_minimum(
        normals, convex_area_vectors(vertices, hull), relative_seed_margin=4e-5)
    print(f"Mesh volume {volume:.9f}; hull volume {hull.volume:.9f} cubic coordinate units.")
    print(f"Hull minimum {hull_min:.9f} square coordinate units at {hull_n}; {outer_rays:,} rays.",
          flush=True)

    lower_vectors = inscribed_sample_hull(triangles, hull.equations)
    inner_min, inner_n, inner_rays, _ = convex_minimum(normals, lower_vectors)
    print(f"Inner lower estimate {inner_min:.9f} at {inner_n}; {inner_rays:,} rays.")
    print(f"Exactly checked {len(lower_vectors)} supporting triangles on distinct planes.",
          flush=True)

    edge_array = np.asarray(list(edge_use))
    edge_faces = np.asarray([[a[0], b[0]] for a, b in edge_use.values()])
    edge_order = np.asarray([a[1] for a, b in edge_use.values()])

    def area(n):
        return projected_union_area(vertices, face_normals, edge_array, edge_faces, edge_order, n)

    starts = [hull_n, inner_n]
    for _, n in sorted(seeds, key=lambda record: record[0]):
        if all(abs(n @ existing) < 0.999995 for existing in starts):
            starts.append(n)
    best_area = area(hull_n)
    best_n = hull_n
    for start in starts:
        x = unit(np.cross(start, np.eye(3)[np.abs(start).argmin()]))
        y = np.cross(start, x)
        result = minimize(lambda t: area(start + t[0] * x + t[1] * y), [0.0, 0.0],
                          method="Nelder-Mead", options={"xatol": 1e-10, "fatol": 1e-10})
        n = unit(start + result.x[0] * x + result.x[1] * y)
        measured = area(n)
        print(f"Localized triangle-union result {measured:.9f} at {n}.", flush=True)
        if measured < best_area:
            best_area, best_n = measured, n

    # Exact crossed normals and area vectors are first converted to binary64.
    # Bound round-off from length, normalization, short dot products, and
    # sequential summation by a generous multiple of machine epsilon times
    # total area. The retained 0.0001 margin also exceeds this bound by orders
    # of magnitude on the study coordinates.
    rounding_allowance = (4 * len(lower_vectors) + 100) * np.finfo(float).eps * (
        np.linalg.norm(lower_vectors, axis=1).sum()
    )
    numerical_margin = max(1e-4, rounding_allowance)
    lower = inner_min - numerical_margin
    outer_upper = outward_hull_area(vertices, hull_n)
    if not Decimal(str(lower)) <= outer_upper:
        raise RuntimeError("The enclosure endpoints are inconsistent.")
    print("Best tested viewing direction (object toward viewer):",
          "(" + ", ".join(f"{x:.12g}" for x in best_n) + ")")
    print(f"Best tested mesh union area {best_area:.9f} square coordinate units.")
    print(f"All-direction lower bound (> {lower:.6f}) with arithmetic margin {numerical_margin:.3g}.")
    print(f"Exact-projection upper bound: {outer_upper} square coordinate units.")


if __name__ == "__main__":
    main()
