Jungfraujoch/image_analysis/indexing/FFTIndexer.cpp

// SPDX-FileCopyrightText: 2025 Filip Leonarski, Paul Scherrer Institute <filip.leonarski@psi.ch>
// SPDX-License-Identifier: GPL-3.0-only

#include <algorithm>
#include <cmath>
#include <numeric>
#include "../../common/JFJochMath.h"
#include "FFTIndexer.h"
#include <Eigen/Eigen>
#include "PostIndexingRefinement.h"
#include "../../common/Logger.h"

// Following Steller, Bolotovsky & Rossmann (1997) J. Appl. Cryst. 30, 1036-1040, after Bricogne (1986) EEC PSD Software Workshop, LURE
FFTIndexer::FFTIndexer(const IndexingSettings &settings)
    : max_length_A(settings.GetFFT_MaxUnitCell_A()),
      min_length_A(settings.GetFFT_MinUnitCell_A()),
      min_angle_deg(settings.GetFFT_MinAngle_deg()),
      max_angle_deg(settings.GetFFT_MaxAngle_deg()),
      nDirections(settings.GetFFT_NumVectors()),
      refine_threads(static_cast<unsigned>(settings.GetRefineThreads())),
      result_fft(nDirections) {

    // Reciprocal-magnitude histogram in one_over_d = 1/d units (the internal convention -
    // the spot coordinates and histogram_spacing are 1/d too; the resolution limit converts
    // as 1/HighRes). NB in this code Q always means the powder 2*pi/d, so 1/d is named
    // one_over_d, never q. The histogram covers the data range [0, one_over_d_max] and is
    // zero-padded by OVERSAMPLING for sub-bin peak localisation (finer cell lengths than the
    // raw bin width gives). len_coeff (= 2*max_length/histogram_size) cancels the factor, so
    // recovered lengths are independent of it. The padding factor is 2*pi: a historical value
    // from when the extent was mistakenly written as 2*pi/d (the Q convention); it is kept
    // because the exact amount sets which marginal frames index - rounding it to a nearby
    // integer shifts the indexing rate ~0.5-1% (measured on the test datasets).
    const float oversampling = 2.0f * static_cast<float>(PI);
    const float one_over_d_max = 1.0f / settings.GetFFT_HighResolution_A();

    histogram_spacing = 1.0f / (2.0f * max_length_A);
    histogram_size = std::ceil(oversampling * one_over_d_max / histogram_spacing);

    input_size = histogram_size * nDirections;
    output_size = (histogram_size / 2 + 1) * nDirections;

    if (max_length_A <= settings.GetFFT_HighResolution_A())
        throw std::invalid_argument("Largest unit cell cannot be smaller than resolution");
    if (nDirections <= 1)
        throw std::invalid_argument("FFTWIndexer: number of directions must be > 1");
    if (!(max_length_A > 0.f))
        throw std::invalid_argument("FFTWIndexer: max_length_A must be > 0");
    if (!(settings.GetFFT_HighResolution_A() > 0.f))
        throw std::invalid_argument("FFTWIndexer: high resolution must be > 0");
    if (histogram_size < 1)
        throw std::invalid_argument("FFTWIndexer: histogram_size must be >= 1");
    if (histogram_size > 1000000)
        throw std::invalid_argument("FFTWIndexer: histogram_size too large");

    SetupDirectionVectors();
}

void FFTIndexer::SetupDirectionVectors() {
    direction_vectors.reserve(static_cast<size_t>(nDirections));

    const double phi = (1.0 + std::sqrt(5.0)) / 2.0; // Golden ratio
    const double golden_angle = 2.0 * PI / phi;

    for (int i = 0; i < nDirections; i++) {
        // Half-sphere distribution (z in [0,1])
        double z = static_cast<double>(i) / static_cast<double>(nDirections - 1);
        double theta = golden_angle * static_cast<double>(i);
        double radius = std::sqrt(std::max(0.0, 1.0 - z * z));

        double x = radius * std::cos(theta);
        double y = radius * std::sin(theta);

        // Add unit vector to the list
        direction_vectors.emplace_back(static_cast<float>(x),
                                       static_cast<float>(y),
                                       static_cast<float>(z));
    }
}


void FFTIndexer::SetupUnitCell(const std::optional<UnitCell> &cell) {
    reference_unit_cell = cell;
}


void Sort(Coord &A, Coord &B, Coord &C) {
    // A is the smallest, C is the largest

    if (A.Length() > B.Length())
        std::swap(A, B);

    if (B.Length() > C.Length())
        std::swap(B, C);

    if (A.Length() > B.Length())
        std::swap(A, B);
}

std::vector<CrystalLattice> FFTIndexer::ReduceResults(const std::vector<Coord> &results, bool widen,
                                                      float min_length) const {
    if (results.size() < 3)
        return {};

    std::vector<CrystalLattice> candidates;

    if (!widen) {
        // Standard: combine only the shortest few filtered vectors (original behaviour, unchanged).
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (i + j + k + 2 >= results.size())
                        break;
                    Coord A = results[i];
                    Coord B = results[(i + j + 1)];
                    Coord C = results[(i + j + 1) + k + 1];

                    // sort vectors by length for reduction
                    Sort(A,B,C);

                    CrystalLattice raw(A, B, C);
                    CrystalLattice reduced = raw.NiggliReduce(); // Reduce cell
                    const auto uc = reduced.GetUnitCell();

                    if (uc.a < min_length || uc.b < min_length || uc.c < min_length)
                        continue;

                    float alpha = uc.alpha, beta = uc.beta, gamma = uc.gamma;
                    if (alpha < min_angle_deg || alpha > max_angle_deg ||
                        beta  < min_angle_deg || beta  > max_angle_deg ||
                        gamma < min_angle_deg || gamma > max_angle_deg)
                        continue;

                    // Three coplanar rows are invisible to the two tests above: they give perfectly
                    // ordinary lengths and angles - 30 to 150 deg admits any flat combination - and
                    // only the volume betrays them. Such a cell has no reciprocal basis at all
                    // (1/V -> infinity), so it cannot be refined, only crashed into.
                    if (reduced.VolumeFraction() < MIN_BASIS_VOLUME_FRACTION)
                        continue;

                    candidates.emplace_back(std::move(reduced));
                }
            }
        }
        return candidates;
    }

    // Fallback: anchor the two short axes (first 12) but let the third reach any longer axis, so a
    // large/elongated cell whose long axis sits beyond the standard window is built. Dedup because
    // most triples of one lattice Niggli-reduce to the same cell (keeps the refine set small).
    const size_t n = std::min<size_t>(results.size(), 64);
    const size_t n_short = std::min<size_t>(n, 12);
    // The cells accepted so far, ordered by a, for the dedup test below. A triple duplicates an accepted
    // cell only if is_close holds, which needs the two a to agree within 2% of the new one; so only the
    // accepted cells in that window of a are asked, with the window a little wider than the tolerance so
    // rounding cannot leave a match outside it. The answer - is there any accepted cell close to this
    // one - is the one a scan over all of them gives. A cell that is not finite is close to nothing, so
    // it is never a duplicate and never needs to be found.
    std::vector<UnitCell> candidate_cells;
    for (size_t i = 0; i < n_short; i++) {
        for (size_t j = i + 1; j < n_short; j++) {
            for (size_t k = j + 1; k < n; k++) {
                Coord A = results[i], B = results[j], C = results[k];
                Sort(A, B, C);
                CrystalLattice reduced = CrystalLattice(A, B, C).NiggliReduce();
                const auto uc = reduced.GetUnitCell();

                if (uc.a < min_length || uc.b < min_length || uc.c < min_length)
                    continue;
                if (uc.alpha < min_angle_deg || uc.alpha > max_angle_deg ||
                    uc.beta  < min_angle_deg || uc.beta  > max_angle_deg ||
                    uc.gamma < min_angle_deg || uc.gamma > max_angle_deg)
                    continue;
                if (reduced.VolumeFraction() < MIN_BASIS_VOLUME_FRACTION)
                    continue;

                const auto by_a = [](const UnitCell &x, float a) { return x.a < a; };
                bool duplicate = false;
                if (uc.is_finite()) {
                    const float window = 0.021f * std::max(std::fabs(uc.a), 1e-6f);
                    for (auto c = std::lower_bound(candidate_cells.begin(), candidate_cells.end(),
                                                   uc.a - window, by_a);
                         c != candidate_cells.end() && c->a <= uc.a + window; ++c)
                        if (c->is_close(uc, 0.02f, 1.0f)) { duplicate = true; break; }
                }
                if (!duplicate) {
                    // Keep each accepted candidate's cell rather than re-deriving it on the next
                    // triple: GetUnitCell costs three acos.
                    if (uc.is_finite())
                        candidate_cells.insert(std::upper_bound(candidate_cells.begin(), candidate_cells.end(), uc.a,
                                                                [](float a, const UnitCell &x) { return a < x.a; }),
                                               uc);
                    candidates.emplace_back(std::move(reduced));
                }
            }
        }
    }

    return candidates;
}

std::vector<Coord> FFTIndexer::FilterFFTResults(size_t max_vectors,
                                               std::vector<float> *magnitudes) const {
    // No legitimate row is non-finite (lengths are bin*coeff or -1, magnitudes guarded
    // prominences), but a corrupted result buffer would put NaN into the magnitude sort below,
    // and std::sort with a NaN key walks out of bounds. Drop such rows instead.
    std::vector<int> by_magnitude;
    by_magnitude.reserve(direction_vectors.size());
    for (int i = 0; i < direction_vectors.size(); i++) {
        if (!std::isfinite(result_fft[i].magnitude) || !std::isfinite(result_fft[i].length))
            continue;
        by_magnitude.push_back(i);
    }

    // Strongest first, and among equal magnitudes the later direction first - the order a multimap
    // keyed on the magnitude, walked from its end, gives. Only the head of that order is read in the
    // normal case, so only the head is sorted; the tail is sorted on the rare walk that reaches it.
    const auto stronger = [this](int a, int b) {
        const float ma = result_fft[a].magnitude, mb = result_fft[b].magnitude;
        if (ma != mb)
            return ma > mb;
        return a > b;
    };
    const size_t head = std::min(by_magnitude.size(), std::max<size_t>(4 * max_vectors, 256));
    std::partial_sort(by_magnitude.begin(), by_magnitude.begin() + head, by_magnitude.end(), stronger);

    std::vector<FFTResult> fft_result_filtered;
    // `it` outlives the loop: the extra scan at the end of the function carries on from the
    // first direction the budget did not reach.
    size_t it = 0;
    for (; it < by_magnitude.size() && it < max_vectors; ++it)
        fft_result_filtered.emplace_back(result_fft[by_magnitude[it]]);

    std::vector<Coord> ret;

    // Remove vectors less than 5 deg apart, as most likely these are colinear
    const float COS_5_DEG = std::cos(5.0f * PI / 180.0f);

    // Minimum relative amplitude to accept a shorter vector (fundamental)
    // over a longer one (harmonic).
    // 0.25 means the fundamental frequency must have at least 25% of the
    // intensity of the harmonic. If less, the odd-indexed spots are likely
    // systematic absences or noise, and the longer vector is the true cell.
    constexpr float MIN_FUNDAMENTAL_PEAK_RATIO = 0.25f;

    std::vector<bool> ignore(fft_result_filtered.size(), false);

    for (int i = 0; i < fft_result_filtered.size(); i++) {
        if (ignore[i])
            continue;

        Coord dir_i = direction_vectors.at(fft_result_filtered[i].direction);
        float len_i = fft_result_filtered[i].length;
        int best_idx = i; // Index of the vector we currently plan to keep

        for (int j = i + 1; j < fft_result_filtered.size(); j++) {
            if (ignore[j]) continue;

            Coord dir_j = direction_vectors.at(fft_result_filtered[j].direction);

            // If vectors are colinear (angle < 5 deg)
            if (std::fabs(dir_i * dir_j) > COS_5_DEG) {
                ignore[j] = true;

                // CHECK: Is the new candidate (j) shorter than current best (best_idx)?
                // We prefer shorter vectors (fundamental periodicity) over longer ones (harmonics)
                // BUT only if the shorter vector has "enough" amplitude to be real.

                if (fft_result_filtered[j].length < len_i * 0.9f) {
                    // Compare against 'i' (the strongest in the cluster) to define the noise floor.
                    // Using 'best_idx' could allow stepping down into noise if we already swapped to a weak peak.
                    float magnitude_ratio = fft_result_filtered[j].magnitude / fft_result_filtered[i].magnitude;

                    // Heuristic: If the shorter vector has at least 25% of the amplitude of the
                    // stronger (longer) vector, assume the shorter one is the true unit cell.
                    // If it's less than 25%, the shorter peak is likely noise/aliasing,
                    // and the longer vector is the true primitive cell.
                    if (magnitude_ratio > MIN_FUNDAMENTAL_PEAK_RATIO) {
                        dir_i = dir_j;
                        len_i = fft_result_filtered[j].length;
                        best_idx = j;
                    }
                }
            }
        }
        Coord best_dir = direction_vectors.at(fft_result_filtered[best_idx].direction);
        ret.push_back(best_dir * fft_result_filtered[best_idx].length);
        if (magnitudes)
            magnitudes->push_back(fft_result_filtered[best_idx].magnitude);
    }

    // Sort filtered vectors by length. The keys are computed once, never inside the comparator:
    // with FMA contraction the compiler may evaluate Length() with different roundings at different
    // inlined call sites, so a key recomputed per comparison can differ by one ulp between calls.
    // Lengths come from quantised FFT bins and tie often, and on a tie that one-ulp flip lets
    // std::sort's unguarded partition scan run off the index array (the broker SEGV).
    std::vector<float> length(ret.size());
    for (size_t i = 0; i < ret.size(); i++)
        length[i] = ret[i].Length();
    std::vector<size_t> order(ret.size());
    std::iota(order.begin(), order.end(), 0);
    std::stable_sort(order.begin(), order.end(), [&](size_t a, size_t b) {
        return length[a] < length[b];
    });
    std::vector<Coord> sorted_ret;
    std::vector<float> sorted_mag;
    sorted_ret.reserve(order.size());
    sorted_mag.reserve(order.size());
    for (const auto i : order) {
        sorted_ret.push_back(ret[i]);
        if (magnitudes)
            sorted_mag.push_back((*magnitudes)[i]);
    }
    ret = std::move(sorted_ret);
    if (magnitudes)
        *magnitudes = std::move(sorted_mag);

    // max_vectors counts RAW search directions, but one lattice row is sampled by many neighbouring
    // directions of the 16k half-sphere, so nearly all the strongest entries belong to the same two or
    // three rows: 30 raw peaks prune down to only four or five distinct directions in practice, and
    // those are the strongest - hence the shortest, densest - rows. When a crystal's densest rows share
    // one plane, every direction that survives is coplanar, every triple ReduceResults forms from them
    // is degenerate, and the indexer returns no cell at all. Keep walking the same magnitude order for
    // a few more directions that are 5 deg clear of everything kept - the weak long axis that closes
    // such a cell sits well past where the budget stops. They are appended AFTER the sort, so the
    // entries above hold their positions and ReduceResults still forms every triple it formed before;
    // the shortlist only gains candidates at its end. Four, because the standard reduction combines
    // results[0..8] and a five-vector shortlist leaves most of that window unusable.
    constexpr int EXTRA_DISTINCT_DIRECTIONS = 4;

    for (int extra = 0; it < by_magnitude.size() && extra < EXTRA_DISTINCT_DIRECTIONS; ++it) {
        if (it == head)
            std::sort(by_magnitude.begin() + head, by_magnitude.end(), stronger);
        const FFTResult &r = result_fft[by_magnitude[it]];
        Coord dir = direction_vectors.at(r.direction);

        bool distinct = true;
        for (const auto &v: ret) {
            if (std::fabs(dir * v.Normalize()) > COS_5_DEG) {
                distinct = false;
                break;
            }
        }

        if (distinct) {
            ret.push_back(dir * r.length);
            if (magnitudes)
                magnitudes->push_back(r.magnitude);
            extra++;
        }
    }

    return ret;
}


// The projected histogram is sampled every histogram_spacing = 1/(2*max_length_A) of 1/d, so its
// transform holds lengths up to max_length_A and no further: a lattice row of length L between
// max_length_A and 2*max_length_A is not lost but FOLDED, and peaks at 2*max_length_A - L. The fold is
// as sharp as a real peak (it is the same samples) and nothing downstream can tell it from one - a
// 602 A axis comes back as a 398 A one, a 701 A axis as 299 A, and a cell built on such a row puts
// only the reflections whose index happens to land on an integer of the folded period on itself.
//
// The samples cannot say which of the two lengths they came from, but the spots can: the transform at
// a single length, summed over the spot positions themselves, has no sampling and so no fold. So each
// row is asked once, at its own length and at its partner's, and keeps whichever the spots carry more
// strongly. Where the partner is an integer multiple of the row (within a tenth), the row itself
// explains it as a harmonic and the question is an axis-multiple one that is settled elsewhere, so
// such a row is left as it is.
namespace {
    // The transform at one length, summed over the spots' projections on the row's direction, as the
    // largest over +-`window_A` about `centre_A` in quarter steps; with the length it was found at.
    std::pair<double, double> RowAmplitude(const std::vector<float> &proj, double centre_A, double window_A) {
        double best = 0.0, best_len = centre_A;
        for (int k = -4; k <= 4; k++) {
            const double len = centre_A + 0.25 * k * window_A;
            double re = 0.0, im = 0.0;
            for (const float p : proj) {
                const double phase = 2.0 * PI * len * p;
                re += std::cos(phase);
                im += std::sin(phase);
            }
            const double a = std::hypot(re, im);
            if (a > best) {
                best = a;
                best_len = len;
            }
        }
        return {best, best_len};
    }

    // The sum is a test between lengths, not a measurement, so a sample of the spots decides it as well
    // as all of them: the coherent part grows as N and the incoherent one as sqrt(N).
    constexpr size_t ROW_TEST_MAX_SPOTS = 4096;
}

void FFTIndexer::DeAlias(const std::vector<Coord> &coord, size_t nspots, std::vector<Coord> &rows) const {
    const size_t stride = std::max<size_t>(1, nspots / ROW_TEST_MAX_SPOTS);
    // The FFT gives a row's length to one bin, 2*max_length_A/histogram_size; the partner inherits that
    // error, and the spots' phases stay coherent only over a fraction of it at high resolution. Search
    // both lengths over +-1 bin in quarter-bin steps.
    const double bin_A = 2.0 * static_cast<double>(max_length_A) / static_cast<double>(histogram_size);
    std::vector<float> proj;
    proj.reserve(nspots / stride + 1);

    const auto amplitude = [&](double centre_A) { return RowAmplitude(proj, centre_A, bin_A).first; };

    for (auto &row : rows) {
        const double len = row.Length();
        if (!(len > 0.0))
            continue;
        const double partner = 2.0 * static_cast<double>(max_length_A) - len;
        const double ratio = partner / len;
        if (std::abs(ratio - std::round(ratio)) < 0.1)
            continue;
        const Coord dir = row.Normalize();
        proj.clear();
        for (size_t i = 0; i < nspots; i += stride)
            proj.push_back(dir * coord[i]);
        const double a_len = amplitude(len), a_partner = amplitude(partner);
        if (a_partner > a_len) {
            Logger("FFTIndexer").Debug("FFT row of {:.1f} A unfolded to {:.1f} A: the spots carry {:.0f} at "
                                       "the longer length against {:.0f} at the folded one",
                                       len, partner, a_partner, a_len);
            row = dir * static_cast<float>(partner);
        }
    }
}

// The per-direction peak search skips every length up to min_length_A, so a lattice row shorter than
// that is reported at a multiple of itself past it - an exact harmonic - and the cell built from such
// rows is an exact integer supercell of the crystal's. Small molecules have rows like that; no
// protein does. The spots can tell the two apart where the histogram cannot: summed at the row's
// own length every spot is in phase, whichever of the two the row is, but at a whole fraction of
// that length only the spots of a lattice whose row it is are, and the others cancel. So each row
// reported within a few multiples of the floor is asked at every fraction of its length between
// SHORT_ROW_MIN_A and the floor, and takes the shortest one that keeps at least half its amplitude.
// The transform of a lattice comb has all its harmonics at one height, less what positional scatter
// takes from the higher ones, so the true row is the strongest of them, not merely half as strong.
bool FFTIndexer::Fundamentals(const std::vector<Coord> &coord, size_t nspots, std::vector<Coord> &rows) const {
    // A harmonic past the first few multiples past the floor is damped below the ones before it, so
    // the peak search does not report a short row there.
    constexpr float MAX_ROW_OVER_FLOOR = 3.0f;
    constexpr double MIN_AMPLITUDE_RATIO = 0.5;

    const size_t stride = std::max<size_t>(1, nspots / ROW_TEST_MAX_SPOTS);
    const double bin_A = 2.0 * static_cast<double>(max_length_A) / static_cast<double>(histogram_size);
    std::vector<float> proj;
    proj.reserve(nspots / stride + 1);

    bool changed = false;
    for (auto &row : rows) {
        const double len = row.Length();
        if (!(len > min_length_A) || len > MAX_ROW_OVER_FLOOR * min_length_A)
            continue;
        const Coord dir = row.Normalize();
        proj.clear();
        for (size_t i = 0; i < nspots; i += stride)
            proj.push_back(dir * coord[i]);
        const auto [a_row, len_row] = RowAmplitude(proj, len, bin_A);
        double fundamental = 0.0;
        for (int k = 2; len_row / k >= SHORT_ROW_MIN_A; k++) {
            if (len_row / k >= min_length_A)
                continue;
            // The row's length is known to a bin, its k-th fraction to a k-th of one.
            const auto [a, l] = RowAmplitude(proj, len_row / k, bin_A / k);
            if (a >= MIN_AMPLITUDE_RATIO * a_row)
                fundamental = l;
        }
        if (fundamental > 0.0) {
            Logger("FFTIndexer").Debug("FFT row of {:.2f} A is a multiple of a {:.2f} A row below the {:.1f} A floor",
                                       len, fundamental, min_length_A);
            row = dir * static_cast<float>(fundamental);
            changed = true;
        }
    }
    return changed;
}

float FFTIndexer::IndexedFraction(const CrystalLattice &latt,
                                  const std::vector<Coord> &coord, size_t nspots) const {
    if (nspots == 0)
        return 0.0f;
    const Coord a = latt.Vec0(), b = latt.Vec1(), c = latt.Vec2();
    const float tol_sq = indexing_tolerance * indexing_tolerance;
    size_t indexed = 0;
    for (size_t i = 0; i < nspots; i++) {
        const Coord &s = coord[i];
        const float hf = a * s, kf = b * s, lf = c * s;   // Coord operator* = dot product = Miller index
        // std::rint, not std::round: rounding half away from zero has to be a libm call, half to even is
        // inlined. Only the squared residual is used, and the rules can differ only at an exact .5, where
        // either leaves |frac| = 0.5 - so the indexed count is the same either way.
        const float dh = hf - std::rint(hf);
        const float dk = kf - std::rint(kf);
        const float dl = lf - std::rint(lf);
        if (dh * dh + dk * dk + dl * dl < tol_sq)
            ++indexed;
    }
    return static_cast<float>(indexed) / static_cast<float>(nspots);
}

std::vector<CrystalLattice> FFTIndexer::ReduceAndRefine(const std::vector<Coord> &coord, size_t nspots,
                                                        const std::vector<Coord> &filtered, bool widen,
                                                        const std::vector<Coord> &short_rows) {
    auto r = ReduceResults(filtered, widen, min_length_A);
    // Widened: the short rows a small cell has many combinations of within one plane, enough to fill
    // the standard reduction's window and leave the third axis out of every triple it forms.
    for (auto &l : ReduceResults(short_rows, true, SHORT_ROW_MIN_A))
        r.push_back(std::move(l));

    Eigen::MatrixX3<float> oCell(r.size() * 3u, 3u);
    Eigen::VectorX<float> scores(r.size());

    for (int i = 0; i < r.size(); i++) {
        oCell(i * 3u, 0u) = r[i].Vec0().x;
        oCell(i * 3u, 1u) = r[i].Vec0().y;
        oCell(i * 3u, 2u) = r[i].Vec0().z;

        oCell(i * 3u + 1, 0u) = r[i].Vec1().x;
        oCell(i * 3u + 1, 1u) = r[i].Vec1().y;
        oCell(i * 3u + 1, 2u) = r[i].Vec1().z;

        oCell(i * 3u + 2, 0u) = r[i].Vec2().x;
        oCell(i * 3u + 2, 1u) = r[i].Vec2().y;
        oCell(i * 3u + 2, 2u) = r[i].Vec2().z;

        // Bootstrap score
        scores(i) = 0.2;
    }

    RefineParameters parameters{
        .viable_cell_min_spots = viable_cell_min_spots,
        .dist_tolerance_vs_reference = dist_tolerance_vs_reference,
        .step_down_to_reference = step_down_to_reference,
        .reference_unit_cell = reference_unit_cell,
        .min_length_A = short_rows.empty() ? min_length_A : SHORT_ROW_MIN_A,
        // A row DeAlias unfolded is longer than max_length_A by construction, and shorter than twice it.
        .max_length_A = std::any_of(filtered.begin(), filtered.end(),
                                    [&](const Coord &v) { return v.Length() > max_length_A; })
                        ? 2.0f * max_length_A : max_length_A,
        .min_angle_deg = min_angle_deg,
        .max_angle_deg = max_angle_deg,
        .indexing_tolerance = indexing_tolerance,
        .refine_threads = refine_threads
    };

    return Refine(coord, nspots, oCell, scores, parameters);
}

// Vector perpendicular to a shortlist that lies in a single plane. Three vectors of one plane can
// never be reduced to a cell - every triple ReduceResults forms from them is degenerate - so a
// shortlist like that means the row that closes the cell was not among the search directions at all.
// The scatter matrix's smallest eigenvector is that plane's normal, and its eigenvalue ratio says how
// flat the set is: lambda_min/lambda_max = 2 <sin^2(out-of-plane angle)>. The threshold below is a
// 3.5 deg rms out-of-plane spread, which sits in a wide empty gap - measured over the accumulated
// clouds of ten rotation first passes, a degenerate shortlist scores 2e-5 to 3e-4 (0.2-0.8 deg) and
// every non-degenerate one 0.026 or more (7.7 deg and up).
std::optional<Coord> FFTIndexer::DegeneratePlaneNormal(const std::vector<Coord> &filtered) const {
    // Below five rows the test says nothing: three directions drawn at random pass it 23% of the time
    // and four 4.2%, against 0.7% at five and under 0.01% at eight (measured, 20000 draws each). A net
    // that really is planar contributes far more rows than five - the crystal here gives sixteen.
    if (filtered.size() < 5)
        return {};

    Eigen::Matrix3f scatter = Eigen::Matrix3f::Zero();
    for (const auto &v : filtered) {
        const Coord n = v.Normalize();
        const Eigen::Vector3f e(n.x, n.y, n.z);
        scatter += e * e.transpose();
    }

    Eigen::SelfAdjointEigenSolver<Eigen::Matrix3f> es(scatter);
    if (es.info() != Eigen::Success)
        return {};

    constexpr float MAX_OUT_OF_PLANE = 0.0076f;   // 2*<sin^2 eps> at eps_rms = 3.5 deg
    if (es.eigenvalues()(0) > MAX_OUT_OF_PLANE * es.eigenvalues()(2))
        return {};

    const auto v = es.eigenvectors().col(0);
    return Coord(v(0), v(1), v(2));
}

// One more transform, with every search direction inside a cap about `axis`. The peak of a length-L
// row stays coherent only within roughly 10.7/(L * sigma_perp) degrees of its own direction (sigma_perp
// = the spread of the accumulated cloud across that direction), which for a long axis is finer than the
// ~0.43 deg the half-sphere grid leaves between a direction and its nearest node. Spending the same
// number of directions on a 3 deg cap samples it to ~0.016 deg instead, so the row is found where the
// global pass could only miss it. The count is unchanged, so the transform and its plan are untouched
// and this costs exactly one extra pass.
std::optional<Coord> FFTIndexer::SearchCap(const std::vector<Coord> &coord, size_t nspots,
                                           const Coord &axis, float half_angle_deg) {
    // An axis that is not a direction normalizes to NaN, and a grid of NaN directions is not a worse
    // answer but a crash: every row it produces is a NaN length, and a NaN key makes the sort in
    // FilterFFTResults walk off its index array. There is nothing to search about such an axis.
    const float axis_length = axis.Length();
    if (!std::isfinite(axis_length) || (axis_length <= 0.0f))
        return {};

    const Coord u = axis.Normalize();
    Coord seed = std::fabs(u.x) < 0.9f ? Coord(1.0f, 0.0f, 0.0f) : Coord(0.0f, 1.0f, 0.0f);
    const Coord e1 = (u % seed).Normalize();
    const Coord e2 = u % e1;

    const double cos_half = std::cos(half_angle_deg * PI / 180.0);
    const double golden_angle = 2.0 * PI / ((1.0 + std::sqrt(5.0)) / 2.0);

    std::vector<Coord> saved;
    saved.swap(direction_vectors);

    // The search borrows a member the object keeps using afterwards, and an indexer outlives a failed
    // transform - the broker's pool logs the error and hands the same indexer the next image - so the
    // grid has to go back however this function leaves. Everything between the swap and the restore is
    // inside the try for that reason: the fill can run out of memory, the upload can fail, and the
    // .at() below throws on exactly the corrupted result row this search has to survive. Leaving the
    // cap grid installed poisons every later image on that indexer.
    std::optional<Coord> found;
    try {
        direction_vectors.reserve(saved.size());
        for (size_t i = 0; i < saved.size(); i++) {
            // Same spiral as SetupDirectionVectors, with z restricted to the cap instead of the half-sphere.
            const double z = 1.0 - (1.0 - cos_half) * static_cast<double>(i) / static_cast<double>(saved.size() - 1);
            const double r = std::sqrt(std::max(0.0, 1.0 - z * z));
            const double theta = golden_angle * static_cast<double>(i);
            direction_vectors.emplace_back(u * static_cast<float>(z)
                                           + e1 * static_cast<float>(r * std::cos(theta))
                                           + e2 * static_cast<float>(r * std::sin(theta)));
        }
        DirectionsChanged();

        ExecuteFFT(coord, nspots);

        int best = 0;
        for (int i = 1; i < nDirections; i++)
            if (result_fft[i].magnitude > result_fft[best].magnitude)
                best = i;
        const FFTResult peak = result_fft[best];
        if (peak.length >= min_length_A)
            found = direction_vectors.at(peak.direction) * peak.length;
    } catch (...) {
        direction_vectors.swap(saved);
        DirectionsChanged();
        throw;
    }

    direction_vectors.swap(saved);
    DirectionsChanged();

    return found;
}

std::optional<SpindleSeverity> FFTIndexer::RunSeverityOnly(const std::vector<Coord> &coord) {
    if (!spindle_axis || spindle_theta_max_deg <= 0 || coord.size() < SPINDLE_MIN_SPOTS)
        return {};
    const size_t nspots = std::min(coord.size(), static_cast<size_t>(FFT_MAX_SPOTS));
    ExecuteFFT(coord, nspots);
    std::vector<float> magnitudes;
    const auto shortlist = FilterFFTResults(30, &magnitudes);
    return SpindleBlindFraction(shortlist, magnitudes, *spindle_axis, spindle_theta_max_deg);
}

std::vector<CrystalLattice> FFTIndexer::RunInternal(const std::vector<Coord> &coord, size_t nspots) {
    if (nspots > coord.size())
        nspots = coord.size();

    if (nspots < viable_cell_min_spots)
        return {};

    assert(nspots <= FFT_MAX_SPOTS);
    assert(coord.size() <= FFT_MAX_SPOTS);

    ExecuteFFT(coord, nspots);

    // Standard reduction: 30 strongest peaks, shortest-vector triples. Unchanged for the common case.
    std::vector<float> magnitudes;
    const auto shortlist = FilterFFTResults(30, &magnitudes);

    // Free ride on that shortlist: how much of a single sweep's blind cone this orientation makes
    // unrecoverable. Needs the spindle and the cone width, both already computed in Setup; costs one
    // pass over 30-odd rows. The cone is the GEOMETRIC one (see spindle_theta_max_deg in Indexer.h),
    // not the still's own spot resolution, which on a weak attenuated frame understates the sweep's
    // real loss.
    // The floor was calibrated on a pass over a frame's WHOLE spot list, but nspots here is whatever
    // the caller fed this call - IndexAndRefine escalates 30 -> 80 -> all and usually stops at 30,
    // so on a frame that indexes cleanly nothing is computed here; the caller then asks for the
    // severity with a RunSeverityOnly pass over the full list instead of leaving it absent.
    spindle_severity = {};
    if (spindle_axis && spindle_theta_max_deg > 0 && nspots >= SPINDLE_MIN_SPOTS)
        spindle_severity = SpindleBlindFraction(shortlist, magnitudes, *spindle_axis,
                                                spindle_theta_max_deg);

    auto rows = shortlist;
    DeAlias(coord, nspots, rows);
    // The cells of the short rows are offered beside the standard ones, not instead of them: the
    // refinement ranks them all on the spots they index, and where the two index alike it keeps the
    // smaller cell.
    std::vector<Coord> short_rows;
    if (search_short_rows) {
        auto replaced = rows;
        if (Fundamentals(coord, nspots, replaced)) {
            // Shortest first, as ReduceResults combines the first few; keys computed once (see
            // FilterFFTResults).
            std::vector<std::pair<float, size_t>> by_length;
            for (size_t i = 0; i < replaced.size(); i++)
                by_length.emplace_back(replaced[i].Length(), i);
            std::stable_sort(by_length.begin(), by_length.end(),
                             [](const auto &a, const auto &b) { return a.first < b.first; });
            for (const auto &[len, i] : by_length)
                short_rows.push_back(replaced[i]);
        }
    }
    auto lattices = ReduceAndRefine(coord, nspots, rows, false, short_rows);

    // If the best cell indexes few of the (un-refined) accumulated spots, the true cell may be large/
    // elongated with a long axis beyond the standard triple window (a superstructure, or a satellite-
    // bearing modulated crystal). OFFER widened alternatives too - the raw fraction here is not a
    // reliable enough discriminator to replace, so the caller refines each candidate and picks the one
    // that indexes best after geometry refinement. A well-indexing compact crystal keeps only its
    // standard candidates (the widened pass never runs).
    const float frac = lattices.empty() ? 0.0f : IndexedFraction(lattices.front(), coord, nspots);
    if (frac < 0.5f) {
        auto filtered = FilterFFTResults(60);
        // A shortlist confined to one plane cannot close a cell whatever is done with it, and the row
        // that would close it is the one perpendicular to that plane. Look for it there, at an angular
        // resolution the global grid does not have.
        if (const auto normal = DegeneratePlaneNormal(filtered))
            if (const auto v = SearchCap(coord, nspots, *normal, 3.0f))
                filtered.push_back(*v);
        DeAlias(coord, nspots, filtered);

        for (auto &w : ReduceAndRefine(coord, nspots, filtered, true)) {
            bool duplicate = false;
            for (const auto &l : lattices)
                if (l.GetUnitCell().is_close(w.GetUnitCell(), 0.02f, 1.0f)) { duplicate = true; break; }
            if (!duplicate)
                lattices.push_back(std::move(w));
        }
    }

    return lattices;
}