Source code for morphogen.iga.basis

"""B-spline basis functions: values and derivatives, knot vectors and the operators of
their refinement.

A knot vector ``U = (u_0 <= ... <= u_m)`` and a degree ``p`` define ``n = m - p``
functions ``N_(i,p)`` by the recurrence of Cox and de Boor::

    N_(i,0)(u) = 1 on [u_i, u_(i+1)), 0 elsewhere,
    N_(i,p)(u) = (u - u_i) / (u_(i+p) - u_i) N_(i,p-1)(u)
               + (u_(i+p+1) - u) / (u_(i+p+1) - u_(i+1)) N_(i+1,p-1)(u),

piecewise polynomials of degree ``p``, non-negative, summing to one, each supported by
``p + 1`` spans, and ``p - k`` times differentiable at a knot repeated ``k`` times (Piegl &
Tiller 1997, ch. 2). The knot vectors here are *open*: their first and last knots are
repeated ``p + 1`` times, so that the functions interpolate at the two ends. In a span
``[u_s, u_(s+1))`` only the functions ``s - p ... s`` are non-zero: they are computed
there together (:func:`basis`), with their derivatives by::

    N'_(i,p) = p (N_(i,p-1) / (u_(i+p) - u_i) - N_(i+1,p-1) / (u_(i+p+1) - u_(i+1))).

Refinement. A space of splines contains that of a coarser knot vector (knots inserted:
*h*-refinement) or of a lower degree with the same continuity (the multiplicity of every
knot raised with the degree: *p*-refinement; both: *k*-refinement). A function keeps its
shape and gets new coefficients, linear in the old ones: :func:`embedding` gives the
matrix ``T`` of that map (``c_new = T c_old``), found by matching the two expansions at the
Gauss points of the new elements — exact since the spaces are nested, whatever the
continuity. Rational curves and surfaces (NURBS) refine through their homogeneous control
points.
"""

from __future__ import annotations

import numpy as np

#: Entries of a refinement operator below this are round-off (its rows sum to one)
_ROUNDOFF = 1e-13


[docs] def open_knots(n: int, degree: int, lower: float = 0.0, upper: float = 1.0) -> np.ndarray: """The open uniform knot vector of ``n`` functions of degree ``degree`` on ``[lower, upper]``: ``n - degree`` elements of equal length.""" n, degree = int(n), int(degree) if degree < 1 or n < degree + 1: raise ValueError("open_knots: a degree of 1 or more and at least degree + 1 functions") inner = np.linspace(lower, upper, n - degree + 1)[1:-1] return np.concatenate([np.full(degree + 1, lower), inner, np.full(degree + 1, upper)])
[docs] def check_knots(knots, degree: int) -> np.ndarray: """The knot vector as an array, checked: non-decreasing, open, no knot repeated more than ``degree`` times inside (continuous functions).""" knots = np.asarray(knots, dtype=float) degree = int(degree) if degree < 1: raise ValueError("degree: 1 or more") if knots.ndim != 1 or len(knots) < 2 * (degree + 1): raise ValueError(f"knots: at least {2 * (degree + 1)} knots for degree {degree}") if np.any(np.diff(knots) < 0): raise ValueError("knots: a non-decreasing sequence") if knots[degree] != knots[0] or knots[-degree - 1] != knots[-1] or knots[0] == knots[-1]: raise ValueError(f"knots: open (the end knots repeated {degree + 1} times)") inner, counts = np.unique(knots[degree + 1 : -degree - 1], return_counts=True) if inner.size and (counts.max() > degree or inner[0] == knots[0] or inner[-1] == knots[-1]): raise ValueError(f"knots: inner knots repeated at most {degree} times") return knots
[docs] def n_functions(knots, degree: int) -> int: """The number of functions of a knot vector.""" return len(knots) - int(degree) - 1
[docs] def breakpoints(knots) -> np.ndarray: """The distinct knots: the ends of the elements.""" return np.unique(np.asarray(knots, dtype=float))
[docs] def greville(knots, degree: int) -> np.ndarray: """The Greville abscissae ``(u_(i+1) + ... + u_(i+p)) / p`` of the functions: where each one is largest, and the parameters of the control points of the identity.""" knots = np.asarray(knots, dtype=float) p = int(degree) n = n_functions(knots, p) return np.array([knots[i + 1 : i + p + 1].mean() for i in range(n)])
[docs] def spans(knots, degree: int, u) -> np.ndarray: """The span ``s`` of each parameter (``u_s <= u < u_(s+1)``; the last span for the last knot). Parameters outside the knots are an error.""" knots = np.asarray(knots, dtype=float) u = np.atleast_1d(np.asarray(u, dtype=float)) tolerance = 1e-12 * (knots[-1] - knots[0]) if u.size and (u.min() < knots[0] - tolerance or u.max() > knots[-1] + tolerance): raise ValueError(f"parameters outside the knots [{knots[0]:g}, {knots[-1]:g}]") last = n_functions(knots, degree) - 1 return np.clip(np.searchsorted(knots, u, side="right") - 1, int(degree), last)
def _values(knots: np.ndarray, degree: int, u: np.ndarray, span: np.ndarray) -> np.ndarray: """The ``degree + 1`` functions of that degree that are non-zero in the span of each parameter (points x degree + 1): the recurrence of Cox and de Boor, by columns.""" m = len(u) values = np.zeros((m, degree + 1)) values[:, 0] = 1.0 left = np.empty((m, degree + 1)) right = np.empty((m, degree + 1)) for j in range(1, degree + 1): left[:, j] = u - knots[span + 1 - j] right[:, j] = knots[span + j] - u saved = np.zeros(m) for r in range(j): ratio = values[:, r] / (right[:, r + 1] + left[:, j - r]) values[:, r] = saved + right[:, r + 1] * ratio saved = left[:, j - r] * ratio values[:, j] = saved return values def _derived(knots, degree: int, u, span, order: int) -> np.ndarray: """The derivatives of order ``order`` of the non-zero functions of ``degree`` (points x degree + 1), from those of order ``order - 1`` of the degree below.""" if order == 0: return _values(knots, degree, u, span) out = np.zeros((len(u), degree + 1)) if order > degree: return out lower = _derived(knots, degree - 1, u, span, order - 1) # functions span - degree + 1 ... for a in range(degree + 1): i = span - degree + a if a >= 1: out[:, a] += degree * lower[:, a - 1] / (knots[i + degree] - knots[i]) if a <= degree - 1: out[:, a] -= degree * lower[:, a] / (knots[i + degree + 1] - knots[i + 1]) return out
[docs] def basis(knots, degree: int, u, derivatives: int = 0) -> tuple[np.ndarray, np.ndarray]: """The spans of the parameters ``u`` and the functions that are non-zero there with their derivatives: ``values[k, j, a]`` is the derivative of order ``k`` of the function ``span[j] - degree + a`` at ``u[j]`` (``k = 0 ... derivatives``, ``a = 0 ... degree``).""" knots = np.asarray(knots, dtype=float) u = np.atleast_1d(np.asarray(u, dtype=float)) degree = int(degree) span = spans(knots, degree, u) u = np.clip(u, knots[0], knots[-1]) values = np.stack([_derived(knots, degree, u, span, k) for k in range(int(derivatives) + 1)]) return span, values
[docs] def collocation(knots, degree: int, u, derivative: int = 0) -> np.ndarray: """The matrix of the functions (or of their derivatives of an order) at parameters: points x functions.""" span, values = basis(knots, degree, u, derivative) out = np.zeros((len(span), n_functions(knots, degree))) rows = np.arange(len(span)) for a in range(int(degree) + 1): out[rows, span - int(degree) + a] = values[derivative, :, a] return out
[docs] def gauss(n: int) -> tuple[np.ndarray, np.ndarray]: """The Gauss-Legendre rule of ``n`` points on ``[0, 1]``: points and weights.""" x, w = np.polynomial.legendre.leggauss(int(n)) return 0.5 * (x + 1.0), 0.5 * w
[docs] def refined_knots(knots, degree: int, subdivisions: int = 1, elevate: int = 0) -> np.ndarray: """The knot vector of a refinement: every element cut into ``subdivisions`` equal parts (new knots, once each), and the degree raised by ``elevate`` with the continuity of the knots kept (their multiplicities raised as much).""" knots = check_knots(knots, degree) subdivisions, elevate = int(subdivisions), int(elevate) if subdivisions < 1 or elevate < 0: raise ValueError("refinement: subdivisions >= 1 and elevate >= 0") points, counts = np.unique(knots, return_counts=True) out = [] for k, (point, count) in enumerate(zip(points, counts, strict=True)): out.extend([point] * (count + elevate)) if k + 1 < len(points) and subdivisions > 1: out.extend(np.linspace(point, points[k + 1], subdivisions + 1)[1:-1]) return np.array(out)
[docs] def embedding(knots, degree: int, new_knots, new_degree: int) -> np.ndarray: """The matrix ``T`` (new functions x old functions) of the coefficients of the old functions in a refined space that contains them: ``sum_i c_i N_i = sum_j (T c)_j N'_j``. Found by least squares at the Gauss points of the new elements, where the two expansions agree exactly; an error if the new space does not contain the old one.""" knots = check_knots(knots, degree) new_knots = check_knots(new_knots, new_degree) ends = breakpoints(new_knots) points, _ = gauss(int(new_degree) + 1) u = (ends[:-1, None] + np.diff(ends)[:, None] * points[None, :]).ravel() new = collocation(new_knots, new_degree, u) old = collocation(knots, degree, u) matrix, *_ = np.linalg.lstsq(new, old, rcond=None) if np.abs(new @ matrix - old).max() > 1e-9: raise ValueError("embedding: the new space does not contain the old one") matrix[np.abs(matrix) < _ROUNDOFF] = 0.0 return matrix
__all__ = [ "basis", "breakpoints", "check_knots", "collocation", "embedding", "gauss", "greville", "n_functions", "open_knots", "refined_knots", "spans", ]