1import { 2 Vector3, 3 Vector4 4} from 'https://static.studyladder.com/cdn/games/0.143/three/three.module.js'; 5 6/** 7 * NURBS utils 8 * 9 * See NURBSCurve and NURBSSurface. 10 **/ 11 12 13/************************************************************** 14 * NURBS Utils 15 **************************************************************/ 16 17/* 18Finds knot vector span. 19 20p : degree 21u : parametric value 22U : knot vector 23 24returns the span 25*/ 26function findSpan( p, u, U ) { 27 28 const n = U.length - p - 1; 29 30 if ( u >= U[ n ] ) { 31 32 return n - 1; 33 34 } 35 36 if ( u <= U[ p ] ) { 37 38 return p; 39 40 } 41 42 let low = p; 43 let high = n; 44 let mid = Math.floor( ( low + high ) / 2 ); 45 46 while ( u < U[ mid ] || u >= U[ mid + 1 ] ) { 47 48 if ( u < U[ mid ] ) { 49 50 high = mid; 51 52 } else { 53 54 low = mid; 55 56 } 57 58 mid = Math.floor( ( low + high ) / 2 ); 59 60 } 61 62 return mid; 63 64} 65 66 67/* 68Calculate basis functions. See The NURBS Book, page 70, algorithm A2.2 69 70span : span in which u lies 71u : parametric point 72p : degree 73U : knot vector 74 75returns array[p+1] with basis functions values. 76*/ 77function calcBasisFunctions( span, u, p, U ) { 78 79 const N = []; 80 const left = []; 81 const right = []; 82 N[ 0 ] = 1.0; 83 84 for ( let j = 1; j <= p; ++ j ) { 85 86 left[ j ] = u - U[ span + 1 - j ]; 87 right[ j ] = U[ span + j ] - u; 88 89 let saved = 0.0; 90 91 for ( let r = 0; r < j; ++ r ) { 92 93 const rv = right[ r + 1 ]; 94 const lv = left[ j - r ]; 95 const temp = N[ r ] / ( rv + lv ); 96 N[ r ] = saved + rv * temp; 97 saved = lv * temp; 98 99 } 100 101 N[ j ] = saved; 102 103 } 104 105 return N; 106 107} 108 109 110/* 111Calculate B-Spline curve points. See The NURBS Book, page 82, algorithm A3.1. 112 113p : degree of B-Spline 114U : knot vector 115P : control points (x, y, z, w) 116u : parametric point 117 118returns point for given u 119*/ 120function calcBSplinePoint( p, U, P, u ) { 121 122 const span = findSpan( p, u, U ); 123 const N = calcBasisFunctions( span, u, p, U ); 124 const C = new Vector4( 0, 0, 0, 0 ); 125 126 for ( let j = 0; j <= p; ++ j ) { 127 128 const point = P[ span - p + j ]; 129 const Nj = N[ j ]; 130 const wNj = point.w * Nj; 131 C.x += point.x * wNj; 132 C.y += point.y * wNj; 133 C.z += point.z * wNj; 134 C.w += point.w * Nj; 135 136 } 137 138 return C; 139 140} 141 142 143/* 144Calculate basis functions derivatives. See The NURBS Book, page 72, algorithm A2.3. 145 146span : span in which u lies 147u : parametric point 148p : degree 149n : number of derivatives to calculate 150U : knot vector 151 152returns array[n+1][p+1] with basis functions derivatives 153*/ 154function calcBasisFunctionDerivatives( span, u, p, n, U ) { 155 156 const zeroArr = []; 157 for ( let i = 0; i <= p; ++ i ) 158 zeroArr[ i ] = 0.0; 159 160 const ders = []; 161 162 for ( let i = 0; i <= n; ++ i ) 163 ders[ i ] = zeroArr.slice( 0 ); 164 165 const ndu = []; 166 167 for ( let i = 0; i <= p; ++ i ) 168 ndu[ i ] = zeroArr.slice( 0 ); 169 170 ndu[ 0 ][ 0 ] = 1.0; 171 172 const left = zeroArr.slice( 0 ); 173 const right = zeroArr.slice( 0 ); 174 175 for ( let j = 1; j <= p; ++ j ) { 176 177 left[ j ] = u - U[ span + 1 - j ]; 178 right[ j ] = U[ span + j ] - u; 179 180 let saved = 0.0; 181 182 for ( let r = 0; r < j; ++ r ) { 183 184 const rv = right[ r + 1 ]; 185 const lv = left[ j - r ]; 186 ndu[ j ][ r ] = rv + lv; 187 188 const temp = ndu[ r ][ j - 1 ] / ndu[ j ][ r ]; 189 ndu[ r ][ j ] = saved + rv * temp; 190 saved = lv * temp; 191 192 } 193 194 ndu[ j ][ j ] = saved; 195 196 } 197 198 for ( let j = 0; j <= p; ++ j ) { 199 200 ders[ 0 ][ j ] = ndu[ j ][ p ]; 201 202 } 203 204 for ( let r = 0; r <= p; ++ r ) { 205 206 let s1 = 0; 207 let s2 = 1; 208 209 const a = []; 210 for ( let i = 0; i <= p; ++ i ) { 211 212 a[ i ] = zeroArr.slice( 0 ); 213 214 } 215 216 a[ 0 ][ 0 ] = 1.0; 217 218 for ( let k = 1; k <= n; ++ k ) { 219 220 let d = 0.0; 221 const rk = r - k; 222 const pk = p - k; 223 224 if ( r >= k ) { 225 226 a[ s2 ][ 0 ] = a[ s1 ][ 0 ] / ndu[ pk + 1 ][ rk ]; 227 d = a[ s2 ][ 0 ] * ndu[ rk ][ pk ]; 228 229 } 230 231 const j1 = ( rk >= - 1 ) ? 1 : - rk; 232 const j2 = ( r - 1 <= pk ) ? k - 1 : p - r; 233 234 for ( let j = j1; j <= j2; ++ j ) { 235 236 a[ s2 ][ j ] = ( a[ s1 ][ j ] - a[ s1 ][ j - 1 ] ) / ndu[ pk + 1 ][ rk + j ]; 237 d += a[ s2 ][ j ] * ndu[ rk + j ][ pk ]; 238 239 } 240 241 if ( r <= pk ) { 242 243 a[ s2 ][ k ] = - a[ s1 ][ k - 1 ] / ndu[ pk + 1 ][ r ]; 244 d += a[ s2 ][ k ] * ndu[ r ][ pk ]; 245 246 } 247 248 ders[ k ][ r ] = d; 249 250 const j = s1; 251 s1 = s2; 252 s2 = j; 253 254 } 255 256 } 257 258 let r = p; 259 260 for ( let k = 1; k <= n; ++ k ) { 261 262 for ( let j = 0; j <= p; ++ j ) { 263 264 ders[ k ][ j ] *= r; 265 266 } 267 268 r *= p - k; 269 270 } 271 272 return ders; 273 274} 275 276 277/* 278 Calculate derivatives of a B-Spline. See The NURBS Book, page 93, algorithm A3.2. 279 280 p : degree 281 U : knot vector 282 P : control points 283 u : Parametric points 284 nd : number of derivatives 285 286 returns array[d+1] with derivatives 287 */ 288function calcBSplineDerivatives( p, U, P, u, nd ) { 289 290 const du = nd < p ? nd : p; 291 const CK = []; 292 const span = findSpan( p, u, U ); 293 const nders = calcBasisFunctionDerivatives( span, u, p, du, U ); 294 const Pw = []; 295 296 for ( let i = 0; i < P.length; ++ i ) { 297 298 const point = P[ i ].clone(); 299 const w = point.w; 300 301 point.x *= w; 302 point.y *= w; 303 point.z *= w; 304 305 Pw[ i ] = point; 306 307 } 308 309 for ( let k = 0; k <= du; ++ k ) { 310 311 const point = Pw[ span - p ].clone().multiplyScalar( nders[ k ][ 0 ] ); 312 313 for ( let j = 1; j <= p; ++ j ) { 314
315 point.add( Pw[ span - p + j ].clone().multiplyScalar( nders[ k ][ j ] ) ); 316 317 } 318 319 CK[ k ] = point; 320 321 } 322 323 for ( let k = du + 1; k <= nd + 1; ++ k ) { 324 325 CK[ k ] = new Vector4( 0, 0, 0 ); 326 327 } 328 329 return CK; 330 331} 332 333 334/* 335Calculate "K over I" 336 337returns k!/(i!(k-i)!) 338*/ 339function calcKoverI( k, i ) { 340 341 let nom = 1; 342 343 for ( let j = 2; j <= k; ++ j ) { 344 345 nom *= j; 346 347 } 348 349 let denom = 1; 350 351 for ( let j = 2; j <= i; ++ j ) { 352 353 denom *= j; 354 355 } 356 357 for ( let j = 2; j <= k - i; ++ j ) { 358 359 denom *= j; 360 361 } 362 363 return nom / denom; 364 365} 366 367 368/* 369Calculate derivatives (0-nd) of rational curve. See The NURBS Book, page 127, algorithm A4.2. 370 371Pders : result of function calcBSplineDerivatives 372 373returns array with derivatives for rational curve. 374*/ 375function calcRationalCurveDerivatives( Pders ) { 376 377 const nd = Pders.length; 378 const Aders = []; 379 const wders = []; 380 381 for ( let i = 0; i < nd; ++ i ) { 382 383 const point = Pders[ i ]; 384 Aders[ i ] = new Vector3( point.x, point.y, point.z ); 385 wders[ i ] = point.w; 386 387 } 388 389 const CK = []; 390 391 for ( let k = 0; k < nd; ++ k ) { 392 393 const v = Aders[ k ].clone(); 394 395 for ( let i = 1; i <= k; ++ i ) { 396 397 v.sub( CK[ k - i ].clone().multiplyScalar( calcKoverI( k, i ) * wders[ i ] ) ); 398 399 } 400 401 CK[ k ] = v.divideScalar( wders[ 0 ] ); 402 403 } 404 405 return CK; 406 407} 408 409 410/* 411Calculate NURBS curve derivatives. See The NURBS Book, page 127, algorithm A4.2. 412 413p : degree 414U : knot vector 415P : control points in homogeneous space 416u : parametric points 417nd : number of derivatives 418 419returns array with derivatives. 420*/ 421function calcNURBSDerivatives( p, U, P, u, nd ) { 422 423 const Pders = calcBSplineDerivatives( p, U, P, u, nd ); 424 return calcRationalCurveDerivatives( Pders ); 425 426} 427 428 429/* 430Calculate rational B-Spline surface point. See The NURBS Book, page 134, algorithm A4.3. 431 432p1, p2 : degrees of B-Spline surface 433U1, U2 : knot vectors 434P : control points (x, y, z, w) 435u, v : parametric values 436 437returns point for given (u, v) 438*/ 439function calcSurfacePoint( p, q, U, V, P, u, v, target ) { 440 441 const uspan = findSpan( p, u, U ); 442 const vspan = findSpan( q, v, V ); 443 const Nu = calcBasisFunctions( uspan, u, p, U ); 444 const Nv = calcBasisFunctions( vspan, v, q, V ); 445 const temp = []; 446 447 for ( let l = 0; l <= q; ++ l ) { 448 449 temp[ l ] = new Vector4( 0, 0, 0, 0 ); 450 for ( let k = 0; k <= p; ++ k ) { 451 452 const point = P[ uspan - p + k ][ vspan - q + l ].clone(); 453 const w = point.w; 454 point.x *= w; 455 point.y *= w; 456 point.z *= w; 457 temp[ l ].add( point.multiplyScalar( Nu[ k ] ) ); 458 459 } 460 461 } 462 463 const Sw = new Vector4( 0, 0, 0, 0 ); 464 for ( let l = 0; l <= q; ++ l ) { 465 466 Sw.add( temp[ l ].multiplyScalar( Nv[ l ] ) ); 467 468 } 469 470 Sw.divideScalar( Sw.w ); 471 target.set( Sw.x, Sw.y, Sw.z ); 472 473} 474 475 476 477export { 478 findSpan, 479 calcBasisFunctions, 480 calcBSplinePoint, 481 calcBasisFunctionDerivatives, 482 calcBSplineDerivatives, 483 calcKoverI, 484 calcRationalCurveDerivatives, 485 calcNURBSDerivatives, 486 calcSurfacePoint, 487};
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.