Skip to content

Next Gen STEP AP242 Native-ish BREP Geometric Modeling Kernel

20.4 KB
Raw Blame
using Aetheris.Kernel.Core.Math;

namespace Aetheris.Kernel.Core.Geometry.Surfaces;

/// <summary>
/// Replaces a rational (NURBS) surface with a non-rational B-spline that follows it within a stated tolerance.
/// <para>
/// Aetheris carries analytic geometry, and a spline face that is really a primitive is recovered as one. What is left
/// over are genuine free-form blends: variable-radius fillets and vertex blends that no primitive describes. Those
/// may remain rational import/display evidence, but production export requires non-rational authority. Since a
/// circular section is not polynomial, reduction is an approximation by construction. Its budget comes from
/// source accuracy during import or an explicit bounded engineering allowance during production normalization.
/// </para>
/// <para>
/// The reduction refines the knot vectors inside the existing domain and interpolates the rational surface at the
/// refined basis's Greville abscissae. Refinement leaves the domain and the parameter map alone, and interpolating at
/// matched parameters keeps the parameter map to within the same budget as the geometry, so trim intervals and
/// pcurves stay meaningful rather than merely landing somewhere on the new surface.
/// </para>
/// </summary>
public static class BSplineSurfaceRationalReduction
{
    /// <summary>Fraction of the source file's declared accuracy the reduction is required to stay inside.</summary>
    private const double DeclaredAccuracyFraction = 0.1d;

    /// <summary>Budget relative to the control net when a file declares no accuracy of its own.</summary>
    private const double UndeclaredAccuracyRelativeTolerance = 1e-7d;

    private const double MinimumTolerance = 1e-12d;

    /// <summary>
    /// Knot refinement converges as the span size to the degree plus one, so a handful of doublings is decisive; a
    /// cap keeps a pathological surface from growing an enormous control net instead of failing honestly.
    /// </summary>
    private const int MaximumSpanSubdivision = 32;
    // Long, narrow vendor nets can already contain hundreds of knots. The total bound still
    // limits allocation; admitting those existing spans does not authorize unlimited refinement.
    private const int MaximumControlPointsPerAxis = 1024;
    private const int MaximumControlPoints = 8192;

    private const int DeviationSamplesPerSpan = 3;
    private const int MinimumDeviationSamples = 24;
    private const int MaximumDeviationSamples = 160;

    /// <summary>The budget this reduction must meet, from the accuracy the source file declares for its geometry.</summary>
    public static double ResolveTolerance(BSplineSurfaceWithKnots surface, double? declaredAccuracyMillimetres)
    {
        if (declaredAccuracyMillimetres is { } declared && double.IsFinite(declared) && declared > 0d)
        {
            return double.Max(declared * DeclaredAccuracyFraction, MinimumTolerance);
        }

        return double.Max(ControlNetDiagonal(surface) * UndeclaredAccuracyRelativeTolerance, MinimumTolerance);
    }

    public static bool TryReduce(
        BSplineSurfaceWithKnots surface,
        double tolerance,
        out BSplineSurfaceWithKnots? reduced,
        out double deviation,
        out string reason)
    {
        reduced = null;
        deviation = double.PositiveInfinity;

        if (!surface.IsRational)
        {
            reason = "surface is already non-rational.";
            return false;
        }

        // Refinement subdivides the spans between declared knots, which only describes the domain when the vector is
        // clamped to it. An unclamped vector is left alone rather than reinterpreted.
        if (!IsClamped(surface.KnotMultiplicitiesU, surface.DegreeU) || !IsClamped(surface.KnotMultiplicitiesV, surface.DegreeV))
        {
            reason = "knot vectors are not clamped to the surface domain, so the spans cannot be refined safely.";
            return false;
        }

        var best = double.PositiveInfinity;
        var lastDeviation = double.PositiveInfinity;
        var controlLimitReached = false;

        BSplineSurfaceWithKnots? Attempt(int subdivisionU, int subdivisionV)
        {
            lastDeviation = double.PositiveInfinity;
            var refinedU = Subdivide(surface.KnotValuesU, surface.KnotMultiplicitiesU, subdivisionU);
            var refinedV = Subdivide(surface.KnotValuesV, surface.KnotMultiplicitiesV, subdivisionV);
            var countU = refinedU.Multiplicities.Sum() - surface.DegreeU - 1;
            var countV = refinedV.Multiplicities.Sum() - surface.DegreeV - 1;
            if (countU > MaximumControlPointsPerAxis || countV > MaximumControlPointsPerAxis ||
                (long)countU * countV > MaximumControlPoints)
            {
                controlLimitReached = true;
                return null;
            }
            if (!TryInterpolate(surface, refinedU, refinedV, out var attempt) || attempt is null)
            {
                return null;
            }

            var measured = MaximumDeviation(surface, attempt);
            lastDeviation = measured;
            best = double.Min(best, measured);
            return measured <= tolerance ? attempt : null;
        }

        // Refine both directions together until the budget is met, then relax each one on its own. Only the
        // directions that actually carry the rational sections need the extra spans, and a control net refined
        // where it did not need to be costs every later evaluation and every exported point for nothing.
        var uniform = 0;
        var lastFiniteSubdivision = 0;
        var lastFiniteDeviation = double.PositiveInfinity;
        for (var subdivision = 1; subdivision <= MaximumSpanSubdivision; subdivision *= 2)
        {
            var attempt = Attempt(subdivision, subdivision);
            if (double.IsFinite(lastDeviation)) { lastFiniteSubdivision = subdivision; lastFiniteDeviation = lastDeviation; }
            if (attempt is not null)
            {
                uniform = subdivision;
                break;
            }
        }

        var subdivisionU = uniform;
        var subdivisionV = uniform;
        if (uniform == 0 && lastFiniteSubdivision > 0)
        {
            // Low-degree rational sections can need many spans in one direction
            // while the other direction is already accurate. Doubling both would
            // exhaust the control-net budget unnecessarily. Continue a bounded
            // numerical refinement, choosing the axis that reduces measured error.
            subdivisionU = lastFiniteSubdivision;
            subdivisionV = lastFiniteSubdivision;
            var currentDeviation = lastFiniteDeviation;
            for (var step = 0; step < 4; step++)
            {
                var nextU = subdivisionU < 128 ? Attempt(subdivisionU * 2, subdivisionV) : null;
                var errorU = subdivisionU < 128 ? lastDeviation : double.PositiveInfinity;
                var nextV = subdivisionV < 128 ? Attempt(subdivisionU, subdivisionV * 2) : null;
                var errorV = subdivisionV < 128 ? lastDeviation : double.PositiveInfinity;
                if (double.Min(errorU, errorV) >= currentDeviation) break;
                if (errorU <= errorV) { subdivisionU *= 2; currentDeviation = errorU; }
                else { subdivisionV *= 2; currentDeviation = errorV; }
                if (nextU is not null || nextV is not null) { uniform = 1; break; }
            }
        }

        if (uniform == 0)
        {
            deviation = best;
            reason = $"bounded uniform/anisotropic refinement did not follow the rational surface to {tolerance:G4} mm (closest {best:G4} mm)" +
                (controlLimitReached ? $"; control-net cap {MaximumControlPointsPerAxis} per axis/{MaximumControlPoints} total reached" : string.Empty);
            return false;
        }

        for (var trial = subdivisionU / 2; trial >= 1; trial /= 2)
        {
            if (Attempt(trial, subdivisionV) is null)
            {
                break;
            }

            subdivisionU = trial;
        }

        for (var trial = subdivisionV / 2; trial >= 1; trial /= 2)
        {
            if (Attempt(subdivisionU, trial) is null)
            {
                break;
            }

            subdivisionV = trial;
        }

        var final = Attempt(subdivisionU, subdivisionV);
        if (final is null)
        {
            deviation = best;
            reason = $"refinement was not reproducible for the relaxed span counts {subdivisionU}x{subdivisionV}";
            return false;
        }

        reduced = final;
        deviation = MaximumDeviation(surface, final);
        reason = $"follows the rational surface to {deviation:G4} mm at matched parameters, within the {tolerance:G4} mm budget, using a {final.ControlPoints.Count}x{final.ControlPoints[0].Count} control net";
        return true;
    }

    private static bool IsClamped(IReadOnlyList<int> multiplicities, int degree)
        => multiplicities.Count >= 2 && multiplicities[0] == degree + 1 && multiplicities[^1] == degree + 1;

    /// <summary>Splits every interval between declared knots into <paramref name="subdivision"/> equal parts.</summary>
    private static (double[] Values, int[] Multiplicities) Subdivide(IReadOnlyList<double> values, IReadOnlyList<int> multiplicities, int subdivision)
    {
        var refinedValues = new List<double>(values.Count * subdivision) { values[0] };
        var refinedMultiplicities = new List<int>(values.Count * subdivision) { multiplicities[0] };

        for (var index = 0; index + 1 < values.Count; index++)
        {
            var start = values[index];
            var end = values[index + 1];
            for (var step = 1; step < subdivision; step++)
            {
                refinedValues.Add(start + ((end - start) * step / subdivision));
                refinedMultiplicities.Add(1);
            }

            refinedValues.Add(end);
            refinedMultiplicities.Add(multiplicities[index + 1]);
        }

        return (refinedValues.ToArray(), refinedMultiplicities.ToArray());
    }

    private static bool TryInterpolate(
        BSplineSurfaceWithKnots surface,
        (double[] Values, int[] Multiplicities) refinedU,
        (double[] Values, int[] Multiplicities) refinedV,
        out BSplineSurfaceWithKnots? candidate)
    {
        candidate = null;
        var knotsU = Expand(refinedU.Values, refinedU.Multiplicities);
        var knotsV = Expand(refinedV.Values, refinedV.Multiplicities);
        var countU = knotsU.Length - surface.DegreeU - 1;
        var countV = knotsV.Length - surface.DegreeV - 1;
        if (countU < surface.DegreeU + 1 || countV < surface.DegreeV + 1 ||
            countU > MaximumControlPointsPerAxis || countV > MaximumControlPointsPerAxis ||
            (long)countU * countV > MaximumControlPoints)
        {
            return false;
        }

        var sitesU = GrevilleAbscissae(knotsU, surface.DegreeU, countU);
        var sitesV = GrevilleAbscissae(knotsV, surface.DegreeV, countV);
        var collocationU = Collocation(knotsU, surface.DegreeU, countU, sitesU);
        var collocationV = Collocation(knotsV, surface.DegreeV, countV, sitesV);

        var permutationU = new int[countU];
        var permutationV = new int[countV];
        if (!TryFactor(collocationU, permutationU) || !TryFactor(collocationV, permutationV))
        {
            return false;
        }

        // Interpolate along u for every v site, then along v: the tensor-product system separates.
        var intermediate = new Vector3D[countV][];
        var column = new Vector3D[countU];
        for (var siteV = 0; siteV < countV; siteV++)
        {
            for (var siteU = 0; siteU < countU; siteU++)
            {
                column[siteU] = surface.Evaluate(sitesU[siteU], sitesV[siteV]) - Point3D.Origin;
            }

            intermediate[siteV] = Solve(collocationU, permutationU, column);
        }

        var net = new IReadOnlyList<Point3D>[countU];
        var row = new Vector3D[countV];
        for (var indexU = 0; indexU < countU; indexU++)
        {
            for (var siteV = 0; siteV < countV; siteV++)
            {
                row[siteV] = intermediate[siteV][indexU];
            }

            net[indexU] = Solve(collocationV, permutationV, row).Select(vector => Point3D.Origin + vector).ToArray();
        }

        try
        {
            candidate = new BSplineSurfaceWithKnots(
                surface.DegreeU,
                surface.DegreeV,
                net,
                surface.SurfaceForm,
                surface.UClosed,
                surface.VClosed,
                surface.SelfIntersect,
                refinedU.Multiplicities,
                refinedV.Multiplicities,
                refinedU.Values,
                refinedV.Values,
                "UNSPECIFIED");
            return true;
        }
        catch (ArgumentException)
        {
            return false;
        }
    }

    /// <summary>Largest sampled gap at matched parameters; this is measured evidence, not a rigorous supremum.</summary>
    private static double MaximumDeviation(BSplineSurfaceWithKnots surface, BSplineSurfaceWithKnots candidate)
    {
        var samplesU = SampleCount(candidate.KnotValuesU.Count);
        var samplesV = SampleCount(candidate.KnotValuesV.Count);
        var worst = 0d;
        for (var indexU = 0; indexU < samplesU; indexU++)
        {
            var u = Lerp(surface.DomainStartU, surface.DomainEndU, indexU / (double)(samplesU - 1));
            for (var indexV = 0; indexV < samplesV; indexV++)
            {
                var v = Lerp(surface.DomainStartV, surface.DomainEndV, indexV / (double)(samplesV - 1));
                var gap = (surface.Evaluate(u, v) - candidate.Evaluate(u, v)).Length;
                if (!double.IsFinite(gap))
                {
                    return double.PositiveInfinity;
                }

                worst = double.Max(worst, gap);
            }
        }

        return worst;
    }

    private static int SampleCount(int distinctKnotCount)
        => System.Math.Clamp((distinctKnotCount - 1) * DeviationSamplesPerSpan, MinimumDeviationSamples, MaximumDeviationSamples);

    private static double[] Expand(IReadOnlyList<double> values, IReadOnlyList<int> multiplicities)
    {
        var knots = new List<double>();
        for (var index = 0; index < values.Count; index++)
        {
            for (var repeat = 0; repeat < multiplicities[index]; repeat++)
            {
                knots.Add(values[index]);
            }
        }

        return knots.ToArray();
    }

    /// <summary>
    /// Greville abscissae are the natural interpolation sites for a B-spline basis: one per control point, each
    /// inside its own function's support, which is what makes the collocation matrix invertible.
    /// </summary>
    private static double[] GrevilleAbscissae(IReadOnlyList<double> knots, int degree, int count)
    {
        var sites = new double[count];
        for (var index = 0; index < count; index++)
        {
            var sum = 0d;
            for (var offset = 1; offset <= degree; offset++)
            {
                sum += knots[index + offset];
            }

            sites[index] = sum / degree;
        }

        return sites;
    }

    private static double[,] Collocation(IReadOnlyList<double> knots, int degree, int count, IReadOnlyList<double> sites)
    {
        var matrix = new double[count, count];
        for (var siteIndex = 0; siteIndex < count; siteIndex++)
        {
            var span = FindSpan(count, degree, knots, sites[siteIndex]);
            var values = BasisValues(span, sites[siteIndex], degree, knots);
            for (var offset = 0; offset <= degree; offset++)
            {
                matrix[siteIndex, span - degree + offset] = values[offset];
            }
        }

        return matrix;
    }

    private static int FindSpan(int count, int degree, IReadOnlyList<double> knots, double parameter)
    {
        var last = count - 1;
        if (parameter >= knots[last + 1])
        {
            return last;
        }

        if (parameter <= knots[degree])
        {
            return degree;
        }

        var low = degree;
        var high = last + 1;
        var mid = (low + high) / 2;
        while (parameter < knots[mid] || parameter >= knots[mid + 1])
        {
            if (parameter < knots[mid])
            {
                high = mid;
            }
            else
            {
                low = mid;
            }

            mid = (low + high) / 2;
        }

        return mid;
    }

    private static double[] BasisValues(int span, double parameter, int degree, IReadOnlyList<double> knots)
    {
        var values = new double[degree + 1];
        var left = new double[degree + 1];
        var right = new double[degree + 1];
        values[0] = 1d;
        for (var level = 1; level <= degree; level++)
        {
            left[level] = parameter - knots[span + 1 - level];
            right[level] = knots[span + level] - parameter;
            var saved = 0d;
            for (var index = 0; index < level; index++)
            {
                var denominator = right[index + 1] + left[level - index];
                var scaled = denominator == 0d ? 0d : values[index] / denominator;
                values[index] = saved + (right[index + 1] * scaled);
                saved = left[level - index] * scaled;
            }

            values[level] = saved;
        }

        return values;
    }

    private static bool TryFactor(double[,] matrix, int[] permutation)
    {
        var size = permutation.Length;
        for (var index = 0; index < size; index++)
        {
            permutation[index] = index;
        }

        for (var column = 0; column < size; column++)
        {
            var pivotRow = column;
            var best = double.Abs(matrix[column, column]);
            for (var row = column + 1; row < size; row++)
            {
                var magnitude = double.Abs(matrix[row, column]);
                if (magnitude > best)
                {
                    best = magnitude;
                    pivotRow = row;
                }
            }

            if (!(best > 0d))
            {
                return false;
            }

            if (pivotRow != column)
            {
                for (var index = 0; index < size; index++)
                {
                    (matrix[column, index], matrix[pivotRow, index]) = (matrix[pivotRow, index], matrix[column, index]);
                }

                (permutation[column], permutation[pivotRow]) = (permutation[pivotRow], permutation[column]);
            }

            for (var row = column + 1; row < size; row++)
            {
                var factor = matrix[row, column] / matrix[column, column];
                matrix[row, column] = factor;
                for (var index = column + 1; index < size; index++)
                {
                    matrix[row, index] -= factor * matrix[column, index];
                }
            }
        }

        return true;
    }

    private static Vector3D[] Solve(double[,] factored, int[] permutation, IReadOnlyList<Vector3D> rightHandSide)
    {
        var size = permutation.Length;
        var forward = new Vector3D[size];
        for (var row = 0; row < size; row++)
        {
            var sum = rightHandSide[permutation[row]];
            for (var column = 0; column < row; column++)
            {
                sum -= factored[row, column] * forward[column];
            }

            forward[row] = sum;
        }

        var solution = new Vector3D[size];
        for (var row = size - 1; row >= 0; row--)
        {
            var sum = forward[row];
            for (var column = row + 1; column < size; column++)
            {
                sum -= factored[row, column] * solution[column];
            }

            solution[row] = sum * (1d / factored[row, row]);
        }

        return solution;
    }

    private static double ControlNetDiagonal(BSplineSurfaceWithKnots surface)
    {
        var points = surface.ControlPoints.SelectMany(row => row).ToArray();
        if (points.Length == 0)
        {
            return 0d;
        }

        return new Vector3D(
            points.Max(point => point.X) - points.Min(point => point.X),
            points.Max(point => point.Y) - points.Min(point => point.Y),
            points.Max(point => point.Z) - points.Min(point => point.Z)).Length;
    }

    private static double Lerp(double start, double end, double fraction) => start + ((end - start) * fraction);
}