- 1 :
import { AABB } from './AABB.js'; - 2 :
import { Vector3 } from './Vector3.js'; - 3 :
- 4 :
const v1 = new Vector3(); - 5 :
const v2 = new Vector3(); - 6 :
const v3 = new Vector3(); - 7 :
- 8 :
const xAxis = new Vector3( 1, 0, 0 ); - 9 :
const yAxis = new Vector3( 0, 1, 0 ); - 10 :
const zAxis = new Vector3( 0, 0, 1 ); - 11 :
- 12 :
const triangle = { a: new Vector3(), b: new Vector3(), c: new Vector3() }; - 13 :
const intersection = new Vector3(); - 14 :
const intersections = new Array(); - 15 :
- 16 :
/** - 17 :
* Class representing a bounding volume hierarchy. The current implementation - 18 :
* represents single BVH nodes as AABBs. It accepts arbitrary branching factors - 19 :
* and can subdivide the given geometry until a defined hierarchy depth has been reached. - 20 :
* Besides, the hierarchy construction is performed top-down and the algorithm only - 21 :
* performs splits along the cardinal axes. - 22 :
* - 23 :
* Reference: Bounding Volume Hierarchies in Real-Time Collision Detection - 24 :
* by Christer Ericson (chapter 6). - 25 :
* - 26 :
* @author {@link https://github.com/robp94|robp94} - 27 :
* @author {@link https://github.com/Mugen87|Mugen87} - 28 :
*/ - 29 :
class BVH { - 30 :
- 31 :
/** - 32 :
* Constructs a new BVH. - 33 :
* - 34 :
* @param {Number} branchingFactor - The branching factor. - 35 :
* @param {Number} primitivesPerNode - The minimum amount of primitives per BVH node. - 36 :
* @param {Number} depth - The maximum hierarchical depth. - 37 :
*/ - 38 :
constructor( branchingFactor = 2, primitivesPerNode = 1, depth = 10 ) { - 39 :
- 40 :
/** - 41 :
* The branching factor (how many nodes per level). - 42 :
* @type {Number} - 43 :
* @default 2 - 44 :
*/ - 45 :
this.branchingFactor = branchingFactor; - 46 :
- 47 :
/** - 48 :
* The minimum amount of primitives per BVH node. - 49 :
* @type {Number} - 50 :
* @default 10 - 51 :
*/ - 52 :
this.primitivesPerNode = primitivesPerNode; - 53 :
- 54 :
/** - 55 :
* The maximum hierarchical depth. - 56 :
* @type {Number} - 57 :
* @default 10 - 58 :
*/ - 59 :
this.depth = depth; - 60 :
- 61 :
/** - 62 :
* The root BVH node. - 63 :
* @type {BVHNode} - 64 :
* @default null - 65 :
*/ - 66 :
this.root = null; - 67 :
- 68 :
} - 69 :
- 70 :
/** - 71 :
* Computes a BVH for the given mesh geometry. - 72 :
* - 73 :
* @param {MeshGeometry} geometry - The mesh geometry. - 74 :
* @return {BVH} A reference to this BVH. - 75 :
*/ - 76 :
fromMeshGeometry( geometry ) { - 77 :
- 78 :
this.root = new BVHNode(); - 79 :
- 80 :
// primitives - 81 :
- 82 :
if ( geometry.indices !== null ) geometry = geometry.toTriangleSoup(); - 83 :
- 84 :
const vertices = geometry.vertices; - 85 :
- 86 :
for ( let i = 0, l = vertices.length; i < l; i ++ ) { - 87 :
- 88 :
this.root.primitives.push( vertices[ i ] ); - 89 :
- 90 :
} - 91 :
- 92 :
// centroids - 93 :
- 94 :
const primitives = this.root.primitives; - 95 :
- 96 :
for ( let i = 0, l = primitives.length; i < l; i += 9 ) { - 97 :
- 98 :
v1.fromArray( primitives, i ); - 99 :
v2.fromArray( primitives, i + 3 ); - 100 :
v3.fromArray( primitives, i + 6 ); - 101 :
- 102 :
v1.add( v2 ).add( v3 ).divideScalar( 3 ); - 103 :
- 104 :
this.root.centroids.push( v1.x, v1.y, v1.z ); - 105 :
- 106 :
} - 107 :
- 108 :
// build - 109 :
- 110 :
this.root.build( this.branchingFactor, this.primitivesPerNode, this.depth, 1 ); - 111 :
- 112 :
return this; - 113 :
- 114 :
} - 115 :
- 116 :
/** - 117 :
* Executes the given callback for each node of the BVH. - 118 :
* - 119 :
* @param {Function} callback - The callback to execute. - 120 :
* @return {BVH} A reference to this BVH. - 121 :
*/ - 122 :
traverse( callback ) { - 123 :
- 124 :
this.root.traverse( callback ); - 125 :
- 126 :
return this; - 127 :
- 128 :
} - 129 :
- 130 :
} - 131 :
- 132 :
/** - 133 :
* A single node in a bounding volume hierarchy (BVH). - 134 :
* - 135 :
* @author {@link https://github.com/robp94|robp94} - 136 :
* @author {@link https://github.com/Mugen87|Mugen87} - 137 :
*/ - 138 :
class BVHNode { - 139 :
- 140 :
/** - 141 :
* Constructs a BVH node. - 142 :
*/ - 143 :
constructor() { - 144 :
- 145 :
/** - 146 :
* The parent BVH node. - 147 :
* @type {BVHNode} - 148 :
* @default null - 149 :
*/ - 150 :
this.parent = null; - 151 :
- 152 :
/** - 153 :
* The child BVH nodes. - 154 :
* @type {Array<BVHNode>} - 155 :
*/ - 156 :
this.children = new Array(); - 157 :
- 158 :
/** - 159 :
* The bounding volume of this BVH node. - 160 :
* @type {AABB} - 161 :
*/ - 162 :
this.boundingVolume = new AABB(); - 163 :
- 164 :
/** - 165 :
* The primitives (triangles) of this BVH node. - 166 :
* Only filled for leaf nodes. - 167 :
* @type {Array<Number>} - 168 :
*/ - 169 :
this.primitives = new Array(); - 170 :
- 171 :
/** - 172 :
* The centroids of the node's triangles. - 173 :
* Only filled for leaf nodes. - 174 :
* @type {Array<Number>} - 175 :
*/ - 176 :
this.centroids = new Array(); - 177 :
- 178 :
} - 179 :
- 180 :
/** - 181 :
* Returns true if this BVH node is a root node. - 182 :
* - 183 :
* @return {Boolean} Whether this BVH node is a root node or not. - 184 :
*/ - 185 :
root() { - 186 :
- 187 :
return this.parent === null; - 188 :
- 189 :
} - 190 :
- 191 :
/** - 192 :
* Returns true if this BVH node is a leaf node. - 193 :
* - 194 :
* @return {Boolean} Whether this BVH node is a leaf node or not. - 195 :
*/ - 196 :
leaf() { - 197 :
- 198 :
return this.children.length === 0; - 199 :
- 200 :
} - 201 :
- 202 :
/** - 203 :
* Returns the depth of this BVH node in its hierarchy. - 204 :
* - 205 :
* @return {Number} The hierarchical depth of this BVH node. - 206 :
*/ - 207 :
getDepth() { - 208 :
- 209 :
let depth = 0; - 210 :
- 211 :
let parent = this.parent; - 212 :
- 213 :
while ( parent !== null ) { - 214 :
- 215 :
parent = parent.parent; - 216 :
depth ++; - 217 :
- 218 :
} - 219 :
- 220 :
return depth; - 221 :
- 222 :
} - 223 :
- 224 :
/** - 225 :
* Executes the given callback for this BVH node and its ancestors. - 226 :
* - 227 :
* @param {Function} callback - The callback to execute. - 228 :
* @return {BVHNode} A reference to this BVH node. - 229 :
*/ - 230 :
traverse( callback ) { - 231 :
- 232 :
callback( this ); - 233 :
- 234 :
for ( let i = 0, l = this.children.length; i < l; i ++ ) { - 235 :
- 236 :
this.children[ i ].traverse( callback ); - 237 :
- 238 :
} - 239 :
- 240 :
return this; - 241 :
- 242 :
} - 243 :
- 244 :
/** - 245 :
* Builds this BVH node. That means the respective bounding volume - 246 :
* is computed and the node's primitives are distributed under new child nodes. - 247 :
* This only happens if the maximum hierarchical depth is not yet reached and - 248 :
* the node does contain enough primitives required for a split. - 249 :
* - 250 :
* @param {Number} branchingFactor - The branching factor. - 251 :
* @param {Number} primitivesPerNode - The minimum amount of primitives per BVH node. - 252 :
* @param {Number} maxDepth - The maximum hierarchical depth. - 253 :
* @param {Number} currentDepth - The current hierarchical depth. - 254 :
* @return {BVHNode} A reference to this BVH node. - 255 :
*/ - 256 :
build( branchingFactor, primitivesPerNode, maxDepth, currentDepth ) { - 257 :
- 258 :
this.computeBoundingVolume(); - 259 :
- 260 :
// check depth and primitive count - 261 :
- 262 :
const primitiveCount = this.primitives.length / 9; - 263 :
const newPrimitiveCount = Math.floor( primitiveCount / branchingFactor ); - 264 :
- 265 :
if ( ( currentDepth <= maxDepth ) && ( newPrimitiveCount >= primitivesPerNode ) ) { - 266 :
- 267 :
// split (distribute primitives on new child BVH nodes) - 268 :
- 269 :
this.split( branchingFactor ); - 270 :
- 271 :
// proceed with build on the next hierarchy level - 272 :
- 273 :
for ( let i = 0; i < branchingFactor; i ++ ) { - 274 :
- 275 :
this.children[ i ].build( branchingFactor, primitivesPerNode, maxDepth, currentDepth + 1 ); - 276 :
- 277 :
} - 278 :
- 279 :
} - 280 :
- 281 :
return this; - 282 :
- 283 :
} - 284 :
- 285 :
/** - 286 :
* Computes the AABB for this BVH node. - 287 :
* - 288 :
* @return {BVHNode} A reference to this BVH node. - 289 :
*/ - 290 :
computeBoundingVolume() { - 291 :
- 292 :
const primitives = this.primitives; - 293 :
- 294 :
const aabb = this.boundingVolume; - 295 :
- 296 :
// compute AABB - 297 :
- 298 :
aabb.min.set( Infinity, Infinity, Infinity ); - 299 :
aabb.max.set( - Infinity, - Infinity, - Infinity ); - 300 :
- 301 :
for ( let i = 0, l = primitives.length; i < l; i += 3 ) { - 302 :
- 303 :
v1.x = primitives[ i ]; - 304 :
v1.y = primitives[ i + 1 ]; - 305 :
v1.z = primitives[ i + 2 ]; - 306 :
- 307 :
aabb.expand( v1 ); - 308 :
- 309 :
} - 310 :
- 311 :
return this; - 312 :
- 313 :
} - 314 :
- 315 :
/** - 316 :
* Computes the split axis. Right now, only the cardinal axes - 317 :
* are potential split axes. - 318 :
* - 319 :
* @return {Vector3} The split axis. - 320 :
*/ - 321 :
computeSplitAxis() { - 322 :
- 323 :
let maxX, maxY, maxZ = maxY = maxX = - Infinity; - 324 :
let minX, minY, minZ = minY = minX = Infinity; - 325 :
- 326 :
const centroids = this.centroids; - 327 :
- 328 :
for ( let i = 0, l = centroids.length; i < l; i += 3 ) { - 329 :
- 330 :
const x = centroids[ i ]; - 331 :
const y = centroids[ i + 1 ]; - 332 :
const z = centroids[ i + 2 ]; - 333 :
- 334 :
if ( x > maxX ) { - 335 :
- 336 :
maxX = x; - 337 :
- 338 :
} - 339 :
- 340 :
if ( y > maxY ) { - 341 :
- 342 :
maxY = y; - 343 :
- 344 :
} - 345 :
- 346 :
if ( z > maxZ ) { - 347 :
- 348 :
maxZ = z; - 349 :
- 350 :
} - 351 :
- 352 :
if ( x < minX ) { - 353 :
- 354 :
minX = x; - 355 :
- 356 :
} - 357 :
- 358 :
if ( y < minY ) { - 359 :
- 360 :
minY = y; - 361 :
- 362 :
} - 363 :
- 364 :
if ( z < minZ ) { - 365 :
- 366 :
minZ = z; - 367 :
- 368 :
} - 369 :
- 370 :
} - 371 :
- 372 :
const rangeX = maxX - minX; - 373 :
const rangeY = maxY - minY; - 374 :
const rangeZ = maxZ - minZ; - 375 :
- 376 :
if ( rangeX > rangeY && rangeX > rangeZ ) { - 377 :
- 378 :
return xAxis; - 379 :
- 380 :
} else if ( rangeY > rangeZ ) { - 381 :
- 382 :
return yAxis; - 383 :
- 384 :
} else { - 385 :
- 386 :
return zAxis; - 387 :
- 388 :
} - 389 :
- 390 :
} - 391 :
- 392 :
/** - 393 :
* Splits the node and distributes node's primitives over new child nodes. - 394 :
* - 395 :
* @param {Number} branchingFactor - The branching factor. - 396 :
* @return {BVHNode} A reference to this BVH node. - 397 :
*/ - 398 :
split( branchingFactor ) { - 399 :
- 400 :
const centroids = this.centroids; - 401 :
const primitives = this.primitives; - 402 :
- 403 :
// create (empty) child BVH nodes - 404 :
- 405 :
for ( let i = 0; i < branchingFactor; i ++ ) { - 406 :
- 407 :
this.children[ i ] = new BVHNode(); - 408 :
this.children[ i ].parent = this; - 409 :
- 410 :
} - 411 :
- 412 :
// sort primitives along split axis - 413 :
- 414 :
const axis = this.computeSplitAxis(); - 415 :
const sortedPrimitiveIndices = new Array(); - 416 :
- 417 :
for ( let i = 0, l = centroids.length; i < l; i += 3 ) { - 418 :
- 419 :
v1.fromArray( centroids, i ); - 420 :
- 421 :
// the result from the dot product is our sort criterion. - 422 :
// it represents the projection of the centroid on the split axis - 423 :
- 424 :
const p = v1.dot( axis ); - 425 :
const primitiveIndex = i / 3; - 426 :
- 427 :
sortedPrimitiveIndices.push( { index: primitiveIndex, p: p } ); - 428 :
- 429 :
} - 430 :
- 431 :
sortedPrimitiveIndices.sort( sortPrimitives ); - 432 :
- 433 :
// distribute data - 434 :
- 435 :
const primitveCount = sortedPrimitiveIndices.length; - 436 :
const primitivesPerChild = Math.floor( primitveCount / branchingFactor ); - 437 :
- 438 :
var childIndex = 0; - 439 :
var primitivesIndex = 0; - 440 :
- 441 :
for ( let i = 0; i < primitveCount; i ++ ) { - 442 :
- 443 :
// selected child - 444 :
- 445 :
primitivesIndex ++; - 446 :
- 447 :
// check if we try to add more primitives to a child than "primitivesPerChild" defines. - 448 :
// move primitives to the next child - 449 :
- 450 :
if ( primitivesIndex > primitivesPerChild ) { - 451 :
- 452 :
// ensure "childIndex" does not overflow (meaning the last child takes all remaining primitives) - 453 :
- 454 :
if ( childIndex < ( branchingFactor - 1 ) ) { - 455 :
- 456 :
primitivesIndex = 1; // reset primitive index - 457 :
childIndex ++; // raise child index - 458 :
- 459 :
} - 460 :
- 461 :
} - 462 :
- 463 :
const child = this.children[ childIndex ]; - 464 :
- 465 :
// move data to the next level - 466 :
- 467 :
// 1. primitives - 468 :
- 469 :
const primitiveIndex = sortedPrimitiveIndices[ i ].index; - 470 :
const stride = primitiveIndex * 9; // remember the "primitives" array holds raw vertex data defining triangles - 471 :
- 472 :
v1.fromArray( primitives, stride ); - 473 :
v2.fromArray( primitives, stride + 3 ); - 474 :
v3.fromArray( primitives, stride + 6 ); - 475 :
- 476 :
child.primitives.push( v1.x, v1.y, v1.z ); - 477 :
child.primitives.push( v2.x, v2.y, v2.z ); - 478 :
child.primitives.push( v3.x, v3.y, v3.z ); - 479 :
- 480 :
// 2. centroid - 481 :
- 482 :
v1.fromArray( centroids, primitiveIndex * 3 ); - 483 :
- 484 :
child.centroids.push( v1.x, v1.y, v1.z ); - 485 :
- 486 :
} - 487 :
- 488 :
// remove centroids/primitives after split from this node - 489 :
- 490 :
this.centroids.length = 0; - 491 :
this.primitives.length = 0; - 492 :
- 493 :
return this; - 494 :
- 495 :
} - 496 :
- 497 :
/** - 498 :
* Performs a ray/BVH node intersection test and stores the closest intersection point - 499 :
* to the given 3D vector. If no intersection is detected, *null* is returned. - 500 :
* - 501 :
* @param {Ray} ray - The ray. - 502 :
* @param {Vector3} result - The result vector. - 503 :
* @return {Vector3} The result vector. - 504 :
*/ - 505 :
intersectRay( ray, result ) { - 506 :
- 507 :
// gather all intersection points along the hierarchy - 508 :
- 509 :
if ( ray.intersectAABB( this.boundingVolume, result ) !== null ) { - 510 :
- 511 :
if ( this.leaf() === true ) { - 512 :
- 513 :
const vertices = this.primitives; - 514 :
- 515 :
for ( let i = 0, l = vertices.length; i < l; i += 9 ) { - 516 :
- 517 :
// remember: we assume primitives are triangles - 518 :
- 519 :
triangle.a.fromArray( vertices, i ); - 520 :
triangle.b.fromArray( vertices, i + 3 ); - 521 :
triangle.c.fromArray( vertices, i + 6 ); - 522 :
- 523 :
if ( ray.intersectTriangle( triangle, true, result ) !== null ) { - 524 :
- 525 :
intersections.push( result.clone() ); - 526 :
- 527 :
} - 528 :
- 529 :
} - 530 :
- 531 :
} else { - 532 :
- 533 :
// process childs - 534 :
- 535 :
for ( let i = 0, l = this.children.length; i < l; i ++ ) { - 536 :
- 537 :
this.children[ i ].intersectRay( ray, result ); - 538 :
- 539 :
} - 540 :
- 541 :
} - 542 :
- 543 :
} - 544 :
- 545 :
// determine the closest intersection point in the root node (so after - 546 :
// the hierarchy was processed) - 547 :
- 548 :
if ( this.root() === true ) { - 549 :
- 550 :
if ( intersections.length > 0 ) { - 551 :
- 552 :
let minDistance = Infinity; - 553 :
- 554 :
for ( let i = 0, l = intersections.length; i < l; i ++ ) { - 555 :
- 556 :
const squaredDistance = ray.origin.squaredDistanceTo( intersections[ i ] ); - 557 :
- 558 :
if ( squaredDistance < minDistance ) { - 559 :
- 560 :
minDistance = squaredDistance; - 561 :
result.copy( intersections[ i ] ); - 562 :
- 563 :
} - 564 :
- 565 :
} - 566 :
- 567 :
// reset array - 568 :
- 569 :
intersections.length = 0; - 570 :
- 571 :
// return closest intersection point - 572 :
- 573 :
return result; - 574 :
- 575 :
} else { - 576 :
- 577 :
// no intersection detected - 578 :
- 579 :
return null; - 580 :
- 581 :
} - 582 :
- 583 :
} else { - 584 :
- 585 :
// always return null for non-root nodes - 586 :
- 587 :
return null; - 588 :
- 589 :
} - 590 :
- 591 :
} - 592 :
- 593 :
/** - 594 :
* Performs a ray/BVH node intersection test. Returns either true or false if - 595 :
* there is a intersection or not. - 596 :
* - 597 :
* @param {Ray} ray - The ray. - 598 :
* @return {boolean} Whether there is an intersection or not. - 599 :
*/ - 600 :
intersectsRay( ray ) { - 601 :
- 602 :
if ( ray.intersectAABB( this.boundingVolume, intersection ) !== null ) { - 603 :
- 604 :
if ( this.leaf() === true ) { - 605 :
- 606 :
const vertices = this.primitives; - 607 :
- 608 :
for ( let i = 0, l = vertices.length; i < l; i += 9 ) { - 609 :
- 610 :
// remember: we assume primitives are triangles - 611 :
- 612 :
triangle.a.fromArray( vertices, i ); - 613 :
triangle.b.fromArray( vertices, i + 3 ); - 614 :
triangle.c.fromArray( vertices, i + 6 ); - 615 :
- 616 :
if ( ray.intersectTriangle( triangle, true, intersection ) !== null ) { - 617 :
- 618 :
return true; - 619 :
- 620 :
} - 621 :
- 622 :
} - 623 :
- 624 :
return false; - 625 :
- 626 :
} else { - 627 :
- 628 :
// process child BVH nodes - 629 :
- 630 :
for ( let i = 0, l = this.children.length; i < l; i ++ ) { - 631 :
- 632 :
if ( this.children[ i ].intersectsRay( ray ) === true ) { - 633 :
- 634 :
return true; - 635 :
- 636 :
} - 637 :
- 638 :
} - 639 :
- 640 :
return false; - 641 :
- 642 :
} - 643 :
- 644 :
} else { - 645 :
- 646 :
return false; - 647 :
- 648 :
} - 649 :
- 650 :
} - 651 :
- 652 :
} - 653 :
- 654 :
// - 655 :
- 656 :
function sortPrimitives( a, b ) { - 657 :
- 658 :
return a.p - b.p; - 659 :
- 660 :
} - 661 :
- 662 :
export { BVH, BVHNode };