31:T459,class Interval { constructor(t0, t1) { this.t0 = t0; this.t1 = t1; } get min() { return Math.min(this.t0, this.t1); } get max() { return Math.max(this.t0, this.t1); } get delta() { return this.t1 - this.t0; } get length() { return Math.abs(this.t1 - this.t0); } normalizedAt(t) { return (t - this.t0) / this.length; } parameterAtNormalized(t) { return this.t0 + (this.t1 - this.t0) * t; } static parameterAtNormalized(a, b, t) { return a + (b - a) * t; } normalizedInterval(t0, t1) { const t0Normalized = this.normalizedAt(t0); const t1Normalized = this.normalizedAt(t1); return new Interval(t0Normalized, t1Normalized); } contains(t) { return (this.min <= t) && (t <= this.max); } clamp(value) { return Interval.clamp(value, this.min, this.max); } static clamp(value, min, max) { if (value < min) { return min; } if (value > max) { return max; } return value; } static clamp01(value) { return Interval.clamp(value, 0, 1); } }32:T13b9,class NurbsCurveShapeFunction { constructor(degree, order) { this._values = new Float64Array((order + 1) * (degree + 1)); this._left = new Float64Array(degree); this._right = new Float64Array(degree); this._ndu = new Float64Array((degree + 1) * (degree + 1)); this._a = new Float64Array(degree + 1); this._b = new Float64Array(degree + 1); this.degree = degree; this.order = order; this.firstNonzeroPole = 0; } get nbNonzeroPoles() { return this.degree + 1; } get nbShapes() { return this.order + 1; } get lastNonzeroPole() { return this.firstNonzeroPole + this.degree; } isNonzeroPole(index) { if (index < this.firstNonzeroPole) return false; if (index > this.lastNonzeroPole) return false; return true; } _getNdu(i, j) { const index = singleIndex(this.nbShapes, this.nbNonzeroPoles, i, j); return this._ndu[index]; } _setNdu(i, j, value) { const index = singleIndex(this.nbShapes, this.nbNonzeroPoles, i, j); this._ndu[index] = value; } value(order, pole) { const index = singleIndex(this.nbShapes, this.nbNonzeroPoles, order, pole); return this._values[index]; } _setValue(order, pole, value) { const index = singleIndex(this.nbShapes, this.nbNonzeroPoles, order, pole); this._values[index] = value; } _subValue(order, pole, value) { const index = singleIndex(this.nbShapes, this.nbNonzeroPoles, order, pole); this._values[index] -= value; } _mulValue(order, pole, value) { const index = singleIndex(this.nbShapes, this.nbNonzeroPoles, order, pole); this._values[index] *= value; } _divValue(order, pole, value) { const index = singleIndex(this.nbShapes, this.nbNonzeroPoles, order, pole); this._values[index] /= value; } nonzeroPoleIndices() { const indices = new Int32Array(this.nbNonzeroPoles); for (let i = 0; i < this.nbNonzeroPoles; i++) { indices[i] = this.firstNonzeroPole + i; } return indices; } computeAtSpan(knots, span, t, weights=null) { this._values.fill(0); this.firstNonzeroPole = span - this.degree + 1; // compute B-Spline shape this._setNdu(0, 0, 1.0); for (let j = 0; j < this.degree; j++) { this._left[j] = t - knots[span - j]; this._right[j] = knots[span + j + 1] - t; let saved = 0.0; for (let r = 0; r <= j; r++) { this._setNdu(j + 1, r, this._right[r] + this._left[j - r]); const temp = this._getNdu(r, j) / this._getNdu(j + 1, r); this._setNdu(r, j + 1, saved + this._right[r] * temp); saved = this._left[j - r] * temp; } this._setNdu(j + 1, j + 1, saved); } for (let j = 0; j < this.nbNonzeroPoles; j++) { this._setValue(0, j, this._getNdu(j, this.degree)); } let a = this._a; let b = this._b; for (let r = 0; r < this.nbNonzeroPoles; r++) { a[0] = 1.0; for (let k = 1; k < this.nbShapes; k++) { let value = this.value(k, r); const rk = r - k; const pk = this.degree - k; if (r >= k) { b[0] = a[0] / this._getNdu(pk + 1, rk); value = b[0] * this._getNdu(rk, pk); } const j1 = r >= k - 1 ? 1 : k - r; const j2 = r <= pk + 1 ? k : this.nbNonzeroPoles - r; for (let j = j1; j < j2; j++) { b[j] = (a[j] - a[j - 1]) / this._getNdu(pk + 1, rk + j); value += b[j] * this._getNdu(rk + j, pk); } if (r <= pk) { b[k] = -a[k - 1] / this._getNdu(pk + 1, r); value += b[k] * this._getNdu(r, pk); } this._setValue(k, r, value); [a, b] = [b, a]; } } let s = this.degree; for (let k = 1; k < this.nbShapes; k++) { for (let j = 0; j < this.nbNonzeroPoles; j++) { this._mulValue(k, j, s); } s *= this.degree - k; } if (weights == null) return; let weightedSums = new Float64Array(this.nbShapes); for (let k = 0; k < this.nbShapes; k++) { weightedSums[k] = 0; for (let i = 0; i < this.nbNonzeroPoles; i++) { this._mulValue(k, i, weights[this.firstNonzeroPole + i]); weightedSums[k] += this.value(k, i); } } for (let k = 0; k < this.nbShapes; k++) { for (let i = 1; i <= k; i++) { const a = binom(k, i) * weightedSums[i]; for (let p = 0; p < this.nbNonzeroPoles; p++) { this._subValue(k, p, a * this.value(k - i, p)); } } for (let p = 0; p < this.nbNonzeroPoles; p++) { this._divValue(k, p, weightedSums[0]); } } } compute(knots, t, weights=null) { const span = upperSpan(this.degree, knots, t); this.computeAtSpan(knots, span, t, weights); } static compute(degree, order, knots, t, weights=null) { const shapeFunctions = new NurbsCurveShapeFunction(degree, order); shapeFunctions.compute(knots, t, weights); return shapeFunctions; } }33:T750,class NurbsCurveGeometry { constructor(dimension, degree, knots, poles, weights=null) { this.dimension = dimension; this.degree = degree; this.knots = knots; this.poles = poles; this.weights = weights; } get domain() { return new Interval(this.knots[this.degree - 1], this.knots[this.knots.length - this.degree]); } pointAt(t) { const shapeFunctions = NurbsCurveShapeFunction.compute(this.degree, 0, this.knots, t, this.weights); let point = new Float64Array(this.dimension); for (let i = 0; i < shapeFunctions.nbNonzeroPoles; i++) { const n = shapeFunctions.value(0, i); const pole = this.poles[shapeFunctions.firstNonzeroPole + i]; for (let k = 0; k < this.dimension; k++) { point[k] += n * pole[k]; } } return point; } derivativesAt(t, order) { const shapeFunctions = NurbsCurveShapeFunction.compute(this.degree, order, this.knots, t, this.weights); const derivatives = []; for (let j = 0; j <= order; j++) { let vector = new Float64Array(this.dimension); for (let i = 0; i < shapeFunctions.nbNonzeroPoles; i++) { const n = shapeFunctions.value(j, i); const pole = this.poles[shapeFunctions.firstNonzeroPole + i]; for (let k = 0; k < this.dimension; k++) { vector[k] += n * pole[k]; } } derivatives.push(vector); } return derivatives; } spans() { const first_span = this.degree - 1; const last_span = this.knots.length - this.degree - 1; const nb_spans = last_span - first_span + 1; const result = []; for (let i = 0; i < nb_spans; i++) { const t0 = this.knots[first_span + i]; const t1 = this.knots[first_span + i + 1]; result.push(new Interval(t0, t1)); } return result; } }34:T66d,function tessellate(curve, tolerance=1e-8) { const dimension = curve.dimension; const domain = curve.domain; const samplePoints = []; let points = []; // compute sample points for (let span of curve.spans()) { const normalizedSpan = domain.normalizedInterval(span.t0, span.t1); if (normalizedSpan.length < 1e-7) { continue; } const t = normalizedSpan.t0; const point = curve.pointAt(span.t0); samplePoints.push([t, point]); } samplePoints.push([1.0, curve.pointAt(domain.parameterAtNormalized(1.0))]); _.sortBy(samplePoints, function(parameterPoint) { return -parameterPoint[0]; }); // compute polyline const n = curve.degree * 2 + 1; while (true) { const [tA, pointA] = samplePoints.pop(); points.push([domain.parameterAtNormalized(tA), pointA]); if (samplePoints.length == 0) { break; } while (true) { const [tB, pointB] = _.last(samplePoints); let maxDistance = 0.0; let maxPoint = null; for (let i = 1; i <= n; i++) { const t = Interval.parameterAtNormalized(tA, tB, i / (n + 1)); const point = curve.pointAt(domain.parameterAtNormalized(t)); const distance = distanceToLine(point, pointA, pointB); if (distance > maxDistance) { maxDistance = distance; maxPoint = [t, point]; } } if (maxDistance < tolerance) { break; } samplePoints.push(maxPoint); } } points = points.reverse(); const parameters = points.map(o => o[0]); const polygon = points.map(o => o[1]); return {parameters, polygon}; }35:[] 2f:{"title":"ANurbs.js","cells":[{"id":0,"value":"md`# ANurbs.js`","pinned":false,"hidden":false,"mode":"ojs"},{"id":168,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":117,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":358,"value":"class Curve\n{\n constructor(curveGeometry, domain=null)\n {\n this.curveGeometry = curveGeometry;\n this.domain = domain != null ? domain : curveGeometry.domain;\n }\n \n get degree()\n {\n return this.curveGeometry.degree;\n }\n \n pointAt(t)\n {\n return this.curveGeometry.pointAt(t);\n }\n \n derivativesAt(t, order)\n {\n return this.curveGeometry.derivativesAt(t, order);\n }\n \n spans()\n {\n const knots = this.curveGeometry.knots;\n\n const firstSpan = upperSpan(this.degree, knots, this.domain.t0);\n const lastSpan = lowerSpan(this.degree, knots, this.domain.t1);\n\n const nbSpans = firstSpan - lastSpan + 1;\n\n const result = [];\n\n for (let i = 0; i < nbSpans; i++) {\n const t0 = this.curveGeometry.knots[firstSpan + i];\n const t1 = this.curveGeometry.knots[firstSpan + i + 1];\n\n result[i] = new Interval(this.domain.clamp(t0), this.domain.clamp(t1));\n }\n\n return result;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":109,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":55,"value":"function binom(n, k)\n{\n return (k > n ) ? 0 : // out of range\n (k == 0 || k == n ) ? 1 : // edge\n (k == 1 || k == n - 1) ? n : // first\n (k + k < n ) ? // recursive:\n (binom(n - 1, k - 1 ) * n) / k : // path to k = 1 faster\n (binom(n - 1, k ) * n) / (n - k); // path to k = n - 1 faster\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"function singleIndex(rows, cols, row, col)\n{\n return row * cols + col;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":73,"value":"function upperBound(values, first, last, value)\n{\n let count = last - first;\n let i, step;\n\n while (count > 0) {\n i = first; \n step = Math.floor(count / 2); \n i += step;\n if (!(value < values[i])) {\n first = ++i;\n count -= step + 1;\n } else {\n count = step;\n }\n }\n return first;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":360,"value":"function lowerBound(values, first, last, value)\n{\n let count = last - first;\n let i, step;\n\n while (count > 0) {\n i = first; \n step = count / 2; \n i += step;\n if (values[i] < value) {\n first = ++i; \n count -= step + 1; \n } else {\n count = step;\n }\n }\n return first;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":71,"value":"function upperSpan(degree, knots, t)\n{\n return upperBound(knots, degree, knots.length - degree, t) - 1;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":363,"value":"function lowerSpan(degree, knots, t)\n{\n return lowerBound(knots, degree, knots.length - degree, t) - 1;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":180,"value":"function distanceToLine(point, lineA, lineB)\n{\n const pow = Math.pow;\n \n if (point.length == 2) {\n const [x, y] = point;\n const [ax, ay] = lineA;\n const [bx, by] = lineB;\n\n const u = ay * bx - ax * by - ay * x + by * x + ax * y - bx * y;\n\n const d = pow(ax - bx, 2) + pow(ay - by, 2);\n \n return pow(pow(u, 2), 2) / pow(d, 2);\n } else {\n const [x, y, z] = point;\n const [ax, ay, az] = lineA;\n const [bx, by, bz] = lineB;\n\n const u = ay * bx - ax * by - ay * x + by * x + ax * y - bx * y;\n const v = az * bx - ax * bz - az * x + bz * x + ax * z - bx * z;\n const w = az * by - ay * bz - az * y + bz * y + ay * z - by * z;\n\n const d = pow(ax - bx, 2) + pow(ay - by, 2) + pow(az - bz, 2);\n\n return pow(pow(u, 2) + pow(v, 2) + pow(w, 2), 2) / pow(d, 2);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":382,"value":"function nbSpans(degree, nbKnots)\n{\n return nbKnots - 2 * degree + 1;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":187,"value":"_ = require(\"underscore\");","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}