(function (global, factory) {
  if (typeof define === "function" && define.amd) {
    define(["exports", "three"], factory);
  } else if (typeof exports !== "undefined") {
    factory(exports, require("three"));
  } else {
    var mod = {
      exports: {}
    };
    factory(mod.exports, global.three);
    global.NURBSUtils = mod.exports;
  }
})(typeof globalThis !== "undefined" ? globalThis : typeof self !== "undefined" ? self : this, function (_exports, _three) {
  "use strict";

  Object.defineProperty(_exports, "__esModule", {
    value: true
  });
  _exports.calcBSplineDerivatives = calcBSplineDerivatives;
  _exports.calcBSplinePoint = calcBSplinePoint;
  _exports.calcBasisFunctionDerivatives = calcBasisFunctionDerivatives;
  _exports.calcBasisFunctions = calcBasisFunctions;
  _exports.calcKoverI = calcKoverI;
  _exports.calcNURBSDerivatives = calcNURBSDerivatives;
  _exports.calcRationalCurveDerivatives = calcRationalCurveDerivatives;
  _exports.calcSurfacePoint = calcSurfacePoint;
  _exports.findSpan = findSpan;

  /**
   * NURBS utils
   *
   * See NURBSCurve and NURBSSurface.
   **/

  /**************************************************************
   *	NURBS Utils
   **************************************************************/

  /*
  Finds knot vector span.
  
  p : degree
  u : parametric value
  U : knot vector
  
  returns the span
  */
  function findSpan(p, u, U) {
    var n = U.length - p - 1;

    if (u >= U[n]) {
      return n - 1;
    }

    if (u <= U[p]) {
      return p;
    }

    var low = p;
    var high = n;
    var mid = Math.floor((low + high) / 2);

    while (u < U[mid] || u >= U[mid + 1]) {
      if (u < U[mid]) {
        high = mid;
      } else {
        low = mid;
      }

      mid = Math.floor((low + high) / 2);
    }

    return mid;
  }
  /*
  Calculate basis functions. See The NURBS Book, page 70, algorithm A2.2
  
  span : span in which u lies
  u    : parametric point
  p    : degree
  U    : knot vector
  
  returns array[p+1] with basis functions values.
  */


  function calcBasisFunctions(span, u, p, U) {
    var N = [];
    var left = [];
    var right = [];
    N[0] = 1.0;

    for (var j = 1; j <= p; ++j) {
      left[j] = u - U[span + 1 - j];
      right[j] = U[span + j] - u;
      var saved = 0.0;

      for (var r = 0; r < j; ++r) {
        var rv = right[r + 1];
        var lv = left[j - r];
        var temp = N[r] / (rv + lv);
        N[r] = saved + rv * temp;
        saved = lv * temp;
      }

      N[j] = saved;
    }

    return N;
  }
  /*
  Calculate B-Spline curve points. See The NURBS Book, page 82, algorithm A3.1.
  
  p : degree of B-Spline
  U : knot vector
  P : control points (x, y, z, w)
  u : parametric point
  
  returns point for given u
  */


  function calcBSplinePoint(p, U, P, u) {
    var span = findSpan(p, u, U);
    var N = calcBasisFunctions(span, u, p, U);
    var C = new _three.Vector4(0, 0, 0, 0);

    for (var j = 0; j <= p; ++j) {
      var point = P[span - p + j];
      var Nj = N[j];
      var wNj = point.w * Nj;
      C.x += point.x * wNj;
      C.y += point.y * wNj;
      C.z += point.z * wNj;
      C.w += point.w * Nj;
    }

    return C;
  }
  /*
  Calculate basis functions derivatives. See The NURBS Book, page 72, algorithm A2.3.
  
  span : span in which u lies
  u    : parametric point
  p    : degree
  n    : number of derivatives to calculate
  U    : knot vector
  
  returns array[n+1][p+1] with basis functions derivatives
  */


  function calcBasisFunctionDerivatives(span, u, p, n, U) {
    var zeroArr = [];

    for (var i = 0; i <= p; ++i) {
      zeroArr[i] = 0.0;
    }

    var ders = [];

    for (var _i = 0; _i <= n; ++_i) {
      ders[_i] = zeroArr.slice(0);
    }

    var ndu = [];

    for (var _i2 = 0; _i2 <= p; ++_i2) {
      ndu[_i2] = zeroArr.slice(0);
    }

    ndu[0][0] = 1.0;
    var left = zeroArr.slice(0);
    var right = zeroArr.slice(0);

    for (var j = 1; j <= p; ++j) {
      left[j] = u - U[span + 1 - j];
      right[j] = U[span + j] - u;
      var saved = 0.0;

      for (var _r = 0; _r < j; ++_r) {
        var rv = right[_r + 1];
        var lv = left[j - _r];
        ndu[j][_r] = rv + lv;
        var temp = ndu[_r][j - 1] / ndu[j][_r];
        ndu[_r][j] = saved + rv * temp;
        saved = lv * temp;
      }

      ndu[j][j] = saved;
    }

    for (var _j = 0; _j <= p; ++_j) {
      ders[0][_j] = ndu[_j][p];
    }

    for (var _r2 = 0; _r2 <= p; ++_r2) {
      var s1 = 0;
      var s2 = 1;
      var a = [];

      for (var _i3 = 0; _i3 <= p; ++_i3) {
        a[_i3] = zeroArr.slice(0);
      }

      a[0][0] = 1.0;

      for (var k = 1; k <= n; ++k) {
        var d = 0.0;
        var rk = _r2 - k;
        var pk = p - k;

        if (_r2 >= k) {
          a[s2][0] = a[s1][0] / ndu[pk + 1][rk];
          d = a[s2][0] * ndu[rk][pk];
        }

        var j1 = rk >= -1 ? 1 : -rk;
        var j2 = _r2 - 1 <= pk ? k - 1 : p - _r2;

        for (var _j3 = j1; _j3 <= j2; ++_j3) {
          a[s2][_j3] = (a[s1][_j3] - a[s1][_j3 - 1]) / ndu[pk + 1][rk + _j3];
          d += a[s2][_j3] * ndu[rk + _j3][pk];
        }

        if (_r2 <= pk) {
          a[s2][k] = -a[s1][k - 1] / ndu[pk + 1][_r2];
          d += a[s2][k] * ndu[_r2][pk];
        }

        ders[k][_r2] = d;
        var _j2 = s1;
        s1 = s2;
        s2 = _j2;
      }
    }

    var r = p;

    for (var _k = 1; _k <= n; ++_k) {
      for (var _j4 = 0; _j4 <= p; ++_j4) {
        ders[_k][_j4] *= r;
      }

      r *= p - _k;
    }

    return ders;
  }
  /*
  	Calculate derivatives of a B-Spline. See The NURBS Book, page 93, algorithm A3.2.
  
  	p  : degree
  	U  : knot vector
  	P  : control points
  	u  : Parametric points
  	nd : number of derivatives
  
  	returns array[d+1] with derivatives
  	*/


  function calcBSplineDerivatives(p, U, P, u, nd) {
    var du = nd < p ? nd : p;
    var CK = [];
    var span = findSpan(p, u, U);
    var nders = calcBasisFunctionDerivatives(span, u, p, du, U);
    var Pw = [];

    for (var i = 0; i < P.length; ++i) {
      var point = P[i].clone();
      var w = point.w;
      point.x *= w;
      point.y *= w;
      point.z *= w;
      Pw[i] = point;
    }

    for (var k = 0; k <= du; ++k) {
      var _point = Pw[span - p].clone().multiplyScalar(nders[k][0]);

      for (var j = 1; j <= p; ++j) {
        _point.add(Pw[span - p + j].clone().multiplyScalar(nders[k][j]));
      }

      CK[k] = _point;
    }

    for (var _k2 = du + 1; _k2 <= nd + 1; ++_k2) {
      CK[_k2] = new _three.Vector4(0, 0, 0);
    }

    return CK;
  }
  /*
  Calculate "K over I"
  
  returns k!/(i!(k-i)!)
  */


  function calcKoverI(k, i) {
    var nom = 1;

    for (var j = 2; j <= k; ++j) {
      nom *= j;
    }

    var denom = 1;

    for (var _j5 = 2; _j5 <= i; ++_j5) {
      denom *= _j5;
    }

    for (var _j6 = 2; _j6 <= k - i; ++_j6) {
      denom *= _j6;
    }

    return nom / denom;
  }
  /*
  Calculate derivatives (0-nd) of rational curve. See The NURBS Book, page 127, algorithm A4.2.
  
  Pders : result of function calcBSplineDerivatives
  
  returns array with derivatives for rational curve.
  */


  function calcRationalCurveDerivatives(Pders) {
    var nd = Pders.length;
    var Aders = [];
    var wders = [];

    for (var i = 0; i < nd; ++i) {
      var point = Pders[i];
      Aders[i] = new _three.Vector3(point.x, point.y, point.z);
      wders[i] = point.w;
    }

    var CK = [];

    for (var k = 0; k < nd; ++k) {
      var v = Aders[k].clone();

      for (var _i4 = 1; _i4 <= k; ++_i4) {
        v.sub(CK[k - _i4].clone().multiplyScalar(calcKoverI(k, _i4) * wders[_i4]));
      }

      CK[k] = v.divideScalar(wders[0]);
    }

    return CK;
  }
  /*
  Calculate NURBS curve derivatives. See The NURBS Book, page 127, algorithm A4.2.
  
  p  : degree
  U  : knot vector
  P  : control points in homogeneous space
  u  : parametric points
  nd : number of derivatives
  
  returns array with derivatives.
  */


  function calcNURBSDerivatives(p, U, P, u, nd) {
    var Pders = calcBSplineDerivatives(p, U, P, u, nd);
    return calcRationalCurveDerivatives(Pders);
  }
  /*
  Calculate rational B-Spline surface point. See The NURBS Book, page 134, algorithm A4.3.
  
  p1, p2 : degrees of B-Spline surface
  U1, U2 : knot vectors
  P      : control points (x, y, z, w)
  u, v   : parametric values
  
  returns point for given (u, v)
  */


  function calcSurfacePoint(p, q, U, V, P, u, v, target) {
    var uspan = findSpan(p, u, U);
    var vspan = findSpan(q, v, V);
    var Nu = calcBasisFunctions(uspan, u, p, U);
    var Nv = calcBasisFunctions(vspan, v, q, V);
    var temp = [];

    for (var l = 0; l <= q; ++l) {
      temp[l] = new _three.Vector4(0, 0, 0, 0);

      for (var k = 0; k <= p; ++k) {
        var point = P[uspan - p + k][vspan - q + l].clone();
        var w = point.w;
        point.x *= w;
        point.y *= w;
        point.z *= w;
        temp[l].add(point.multiplyScalar(Nu[k]));
      }
    }

    var Sw = new _three.Vector4(0, 0, 0, 0);

    for (var _l = 0; _l <= q; ++_l) {
      Sw.add(temp[_l].multiplyScalar(Nv[_l]));
    }

    Sw.divideScalar(Sw.w);
    target.set(Sw.x, Sw.y, Sw.z);
  }
});