yum-mirror/slang
Making it easier to work with shaders
git clone https://git.yummers.dev/yum-mirror/slang
c97166aed
master
1implementing fcpw; 2__include aggregate; 3__include geometry; 4__include bvh_node; 5 6public static const uint FCPW_BVH_MAX_DEPTH = 64; 7 8public struct TraversalStack 9{ 10 public uint node; // node index 11 public float distance; // minimum distance (parametric, squared, ...) to this node 12 13 // constructor 14 public __init() 15 { 16 node = 0; 17 distance = 0.0; 18 } 19}; 20 21public struct Bvh<N : IBvhNode, P : IPrimitive, S : ISilhouette> : IAggregate 22{ 23 public RWStructuredBuffer<N> nodes; 24 public StructuredBuffer<P> primitives; 25 public StructuredBuffer<S> silhouettes; 26 27 // updates the bounding volume of an aggregate leaf node 28 [mutating] 29 internal void refitLeafNode(uint nodeIndex) 30 { 31 // update leaf node's bounding box 32 float3 pMin = float3(FLT_MAX, FLT_MAX, FLT_MAX); 33 float3 pMax = float3(-FLT_MAX, -FLT_MAX, -FLT_MAX); 34 N node = nodes[nodeIndex]; 35 uint nPrimitives = node.getNumPrimitives(); 36 37 for (uint p = 0; p < nPrimitives; p++) 38 { 39 uint primitiveIndex = node.getPrimitiveOffset() + p; 40 BoundingBox primitiveBox = primitives[primitiveIndex].getBoundingBox(); 41 pMin = min(pMin, primitiveBox.pMin); 42 pMax = max(pMax, primitiveBox.pMax); 43 } 44 45 node.setBoundingBox(BoundingBox(pMin, pMax)); 46 47 if (node.hasBoundingCone()) 48 { 49 // update leaf node's bounding cone 50 float3 axis = float3(0.0, 0.0, 0.0); 51 float3 centroid = 0.5 * (pMin + pMax); 52 float halfAngle = 0.0; 53 float radius = 0.0; 54 bool anySilhouettes = false; 55 bool silhouettesHaveTwoAdjacentFaces = true; 56 uint nSilhouettes = node.getNumSilhouettes(); 57 58 for (uint p = 0; p < nSilhouettes; p++) 59 { 60 uint silhouetteIndex = node.getSilhouetteOffset() + p; 61 S silhouette = silhouettes[silhouetteIndex]; 62 axis += silhouette.getNormal(0); 63 axis += silhouette.getNormal(1); 64 radius = max(radius, length(silhouette.getCentroid() - centroid)); 65 silhouettesHaveTwoAdjacentFaces = silhouettesHaveTwoAdjacentFaces && 66 silhouette.hasTwoAdjacentFaces(); 67 anySilhouettes = true; 68 } 69 70 if (!anySilhouettes) 71 { 72 halfAngle = -M_PI; 73 } 74 else if (!silhouettesHaveTwoAdjacentFaces) 75 { 76 halfAngle = M_PI; 77 } 78 else 79 { 80 float axisNorm = length(axis); 81 if (axisNorm > FLT_EPSILON) 82 { 83 axis /= axisNorm; 84 85 for (uint p = 0; p < nSilhouettes; p++) 86 { 87 uint silhouetteIndex = node.getSilhouetteOffset() + p; 88 for (uint k = 0; k < 2; k++) 89 { 90 float3 n = silhouettes[silhouetteIndex].getNormal(k); 91 float angle = acos(max(-1.0, min(1.0, dot(axis, n)))); 92 halfAngle = max(halfAngle, angle); 93 } 94 } 95 } 96 } 97 98 node.setBoundingCone(BoundingCone(axis, halfAngle, radius)); 99 } 100 } 101 102 // updates the bounding volume of an aggregate internal node 103 [mutating] 104 internal void refitInternalNode(uint nodeIndex) 105 { 106 // update internal node's bounding box 107 N node = nodes[nodeIndex]; 108 uint leftNodeIndex = nodeIndex + 1; 109 uint rightNodeIndex = nodeIndex + node.getRightChildOffset(); 110 N leftNode = nodes[leftNodeIndex]; 111 N rightNode = nodes[rightNodeIndex]; 112 113 BoundingBox leftBox = leftNode.getBoundingBox(); 114 BoundingBox rightBox = rightNode.getBoundingBox(); 115 BoundingBox mergedBox = mergeBoundingBoxes(leftBox, rightBox); 116 node.setBoundingBox(mergedBox); 117 118 if (node.hasBoundingCone()) 119 { 120 // update internal node's bounding cone 121 BoundingCone leftCone = leftNode.getBoundingCone(); 122 BoundingCone rightCone = rightNode.getBoundingCone(); 123 BoundingCone mergedCone = mergeBoundingCones(leftCone, rightCone, 124 leftBox.getCentroid(), 125 rightBox.getCentroid(), 126 mergedBox.getCentroid()); 127 node.setBoundingCone(mergedCone); 128 } 129 } 130 131 // updates the bounding volume of an aggregate node 132 // NOTE: assumes node indices are provided in bottom-up order 133 [mutating] 134 public void refit(uint nodeIndex) 135 { 136 if (nodes[nodeIndex].isLeaf()) 137 { 138 refitLeafNode(nodeIndex); 139 } 140 else 141 { 142 refitInternalNode(nodeIndex); 143 } 144 } 145 146 // intersects aggregate geometry with ray 147 public bool intersect(inout Ray r, bool checkForOcclusion, inout Interaction i) 148 { 149 TraversalStack traversalStack[FCPW_BVH_MAX_DEPTH]; 150 float4 distToChildNodes = float4(0.0, 0.0, 0.0, 0.0); 151 BoundingBox rootBox = nodes[0].getBoundingBox(); 152 bool didIntersect = false; 153 154 if (rootBox.intersect(r, distToChildNodes[0], distToChildNodes[1])) 155 { 156 traversalStack[0].node = 0; 157 traversalStack[0].distance = distToChildNodes[0]; 158 int stackPtr = 0; 159 160 while (stackPtr >= 0) 161 { 162 // pop off the next node to work on 163 uint currentNodeIndex = traversalStack[stackPtr].node; 164 float currentDist = traversalStack[stackPtr].distance; 165 stackPtr--; 166 167 // if this node is further than the closest found intersection, continue 168 if (currentDist > r.tMax) 169 { 170 continue; 171 } 172 173 N node = nodes[currentNodeIndex]; 174 if (node.isLeaf()) 175 { 176 // intersect primitives in leaf node 177 uint nPrimitives = node.getNumPrimitives(); 178 for (uint p = 0; p < nPrimitives; p++) 179 { 180 Interaction c; 181 uint primitiveIndex = node.getPrimitiveOffset() + p; 182 bool didIntersectPrimitive = primitives[primitiveIndex].intersect(r, checkForOcclusion, c); 183 184 if (didIntersectPrimitive) 185 { 186 if (checkForOcclusion) 187 { 188 i.index = c.index; 189 return true; 190 } 191 192 didIntersect = true; 193 r.tMax = min(r.tMax, c.d); 194 i = c; 195 } 196 } 197 } 198 else 199 { 200 // intersect child nodes 201 uint leftNodeIndex = currentNodeIndex + 1; 202 BoundingBox leftBox = nodes[leftNodeIndex].getBoundingBox(); 203 bool didIntersectLeft = leftBox.intersect(r, distToChildNodes[0], distToChildNodes[1]); 204 205 uint rightNodeIndex = currentNodeIndex + node.getRightChildOffset(); 206 BoundingBox rightBox = nodes[rightNodeIndex].getBoundingBox(); 207 bool didIntersectRight = rightBox.intersect(r, distToChildNodes[2], distToChildNodes[3]); 208 209 // which nodes did we intersect? 210 if (didIntersectLeft && didIntersectRight) 211 { 212 // assume that the left child is closer 213 uint closer = leftNodeIndex; 214 uint other = rightNodeIndex; 215 216 // ... if the right child was actually closer, swap the relavent values 217 if (distToChildNodes[2] < distToChildNodes[0]) 218 { 219 float tmpDist = distToChildNodes[0]; 220 distToChildNodes[0] = distToChildNodes[2]; 221 distToChildNodes[2] = tmpDist; 222 223 uint tmpNodeIndex = closer; 224 closer = other; 225 other = tmpNodeIndex; 226 } 227 228 // it's possible that the nearest primitive is still in the other node, 229 // but we'll check the farther-away node later. 230 231 // push the further node first, then the closer node 232 stackPtr++; 233 traversalStack[stackPtr].node = other; 234 traversalStack[stackPtr].distance = distToChildNodes[2]; 235 236 stackPtr++; 237 traversalStack[stackPtr].node = closer; 238 traversalStack[stackPtr].distance = distToChildNodes[0]; 239 } 240 else if (didIntersectLeft) 241 { 242 stackPtr++; 243 traversalStack[stackPtr].node = leftNodeIndex; 244 traversalStack[stackPtr].distance = distToChildNodes[0]; 245 } 246 else if (didIntersectRight) 247 { 248 stackPtr++; 249 traversalStack[stackPtr].node = rightNodeIndex; 250 traversalStack[stackPtr].distance = distToChildNodes[2]; 251 } 252 } 253 } 254 } 255 256 return didIntersect; 257 } 258 259 // intersects aggregate geometry with sphere 260 public bool intersect<T : IBranchTraversalWeight>(BoundingSphere s, float3 randNums, 261 T branchTraversalWeight, 262 inout Interaction i) 263 { 264 float4 distToChildNodes = float4(0.0, 0.0, 0.0, 0.0); 265 BoundingBox rootBox = nodes[0].getBoundingBox(); 266 uint currentNodeIndex = 0; 267 uint selectedPrimitiveIndex = UINT_MAX; 268 bool didIntersect = false; 269 270 if (rootBox.overlap(s, distToChildNodes[0], distToChildNodes[1])) 271 { 272 float maxDistToChildNode = distToChildNodes[1]; 273 float traversalPdf = 1.0; 274 float u = randNums[0]; 275 int stackPtr = 0; 276 277 while (stackPtr >= 0) 278 { 279 // pop off the next node to work on 280 stackPtr--; 281 282 N node = nodes[currentNodeIndex]; 283 if (node.isLeaf()) 284 { 285 // probabilistically select a primitive 286 float totalPrimitiveWeight = 0.0; 287 uint nPrimitives = node.getNumPrimitives(); 288 for (uint p = 0; p < nPrimitives; p++) 289 { 290 Interaction c; 291 bool didIntersectPrimitive = false; 292 uint primitiveIndex = node.getPrimitiveOffset() + p; 293 P primitive = primitives[primitiveIndex]; 294 295 if (maxDistToChildNode <= s.r2) 296 { 297 didIntersectPrimitive = true; 298 c.d = primitive.getSurfaceArea(); 299 c.index = primitive.getIndex(); 300 } 301 else 302 { 303 didIntersectPrimitive = primitive.intersect(s, c); 304 } 305 306 if (didIntersectPrimitive) 307 { 308 didIntersect = true; 309 totalPrimitiveWeight += c.d; 310 float selectionProb = c.d / totalPrimitiveWeight; 311 312 if (u < selectionProb) 313 { 314 u = u / selectionProb; // rescale to [0,1) 315 i = c; 316 i.d *= traversalPdf; 317 selectedPrimitiveIndex = primitiveIndex; 318 } 319 else 320 { 321 u = (u - selectionProb) / (1.0 - selectionProb); 322 } 323 } 324 } 325 326 if (totalPrimitiveWeight > 0.0) 327 { 328 i.d /= totalPrimitiveWeight; 329 } 330 } 331 else 332 { 333 // probabilistically select one child node to traverse 334 uint leftNodeIndex = currentNodeIndex + 1; 335 BoundingBox leftBox = nodes[leftNodeIndex].getBoundingBox(); 336 bool overlapsLeft = leftBox.overlap(s, distToChildNodes[0], distToChildNodes[1]); 337 float weightLeft = overlapsLeft ? 1.0 : 0.0; 338 if (weightLeft > 0.0) 339 { 340 float3 u = s.c - leftBox.getCentroid(); 341 weightLeft *= branchTraversalWeight.compute(dot(u, u)); 342 } 343 344 uint rightNodeIndex = currentNodeIndex + node.getRightChildOffset(); 345 BoundingBox rightBox = nodes[rightNodeIndex].getBoundingBox(); 346 bool overlapsRight = rightBox.overlap(s, distToChildNodes[2], distToChildNodes[3]); 347 float weightRight = overlapsRight ? 1.0 : 0.0; 348 if (weightRight > 0.0) 349 { 350 float3 u = s.c - rightBox.getCentroid(); 351 weightRight *= branchTraversalWeight.compute(dot(u, u)); 352 } 353 354 float totalTraversalWeight = weightLeft + weightRight; 355 if (totalTraversalWeight > 0.0) 356 { 357 stackPtr++; 358 float traversalProbLeft = weightLeft / totalTraversalWeight; 359 float traversalProbRight = 1.0 - traversalProbLeft; 360 361 if (u < traversalProbLeft) 362 { 363 u = u / traversalProbLeft; // rescale to [0,1) 364 currentNodeIndex = leftNodeIndex; 365 traversalPdf *= traversalProbLeft; 366 maxDistToChildNode = distToChildNodes[1]; 367 } 368 else 369 { 370 u = (u - traversalProbLeft) / traversalProbRight; // rescale to [0,1) 371 currentNodeIndex = rightNodeIndex; 372 traversalPdf *= traversalProbRight; 373 maxDistToChildNode = distToChildNodes[3]; 374 } 375 } 376 } 377 } 378 } 379 380 if (didIntersect) 381 { 382 if (i.index == UINT_MAX || selectedPrimitiveIndex == UINT_MAX) 383 { 384 didIntersect = false; 385 } 386 else 387 { 388 // sample a point on the selected geometric primitive 389 float samplingPdf = primitives[selectedPrimitiveIndex].samplePoint(randNums.yz, i.uv, i.p, i.n); 390 i.d *= samplingPdf; 391 } 392 } 393 394 return didIntersect; 395 } 396 397 // finds closest point on aggregate geometry from sphere center 398 public bool findClosestPoint(inout BoundingSphere s, inout Interaction i, 399 bool recordNormal = false) 400 { 401 TraversalStack traversalStack[FCPW_BVH_MAX_DEPTH]; 402 float4 distToChildNodes = float4(0.0, 0.0, 0.0, 0.0); 403 BoundingBox rootBox = nodes[0].getBoundingBox(); 404 bool notFound = true; 405 406 if (rootBox.overlap(s, distToChildNodes[0], distToChildNodes[1])) 407 { 408 s.r2 = min(s.r2, distToChildNodes[1]); 409 traversalStack[0].node = 0; 410 traversalStack[0].distance = distToChildNodes[0]; 411 int stackPtr = 0; 412 413 while (stackPtr >= 0) 414 { 415 // pop off the next node to work on 416 uint currentNodeIndex = traversalStack[stackPtr].node; 417 float currentDist = traversalStack[stackPtr].distance; 418 stackPtr--; 419 420 // if this node is further than the closest found primitive, continue 421 if (currentDist > s.r2) 422 { 423 continue; 424 } 425 426 N node = nodes[currentNodeIndex]; 427 if (node.isLeaf()) 428 { 429 // compute distance to primitives in leaf node 430 uint nPrimitives = node.getNumPrimitives(); 431 for (uint p = 0; p < nPrimitives; p++) 432 { 433 Interaction c; 434 uint primitiveIndex = node.getPrimitiveOffset() + p; 435 bool found = primitives[primitiveIndex].findClosestPoint(s, c); 436 437 // keep the closest point only 438 if (found) 439 { 440 notFound = false; 441 s.r2 = min(s.r2, c.d * c.d); 442 i = c; 443 } 444 } 445 } 446 else 447 { 448 // find distance to child nodes 449 uint leftNodeIndex = currentNodeIndex + 1; 450 BoundingBox leftBox = nodes[leftNodeIndex].getBoundingBox(); 451 bool overlapsLeft = leftBox.overlap(s, distToChildNodes[0], distToChildNodes[1]); 452 s.r2 = min(s.r2, distToChildNodes[1]); 453 454 uint rightNodeIndex = currentNodeIndex + node.getRightChildOffset(); 455 BoundingBox rightBox = nodes[rightNodeIndex].getBoundingBox(); 456 bool overlapsRight = rightBox.overlap(s, distToChildNodes[2], distToChildNodes[3]); 457 s.r2 = min(s.r2, distToChildNodes[3]); 458 459 // which nodes do we overlap? 460 if (overlapsLeft && overlapsRight) 461 { 462 // assume that the left child is closer 463 uint closer = leftNodeIndex; 464 uint other = rightNodeIndex; 465 466 // ... if the right child was actually closer, swap the relavent values 467 if (distToChildNodes[0] == 0.0 && distToChildNodes[2] == 0.0) 468 { 469 if (distToChildNodes[3] < distToChildNodes[1]) 470 { 471 uint tmpNodeIndex = closer; 472 closer = other; 473 other = tmpNodeIndex; 474 } 475 } 476 else if (distToChildNodes[2] < distToChildNodes[0]) 477 { 478 float tmpDist = distToChildNodes[0]; 479 distToChildNodes[0] = distToChildNodes[2]; 480 distToChildNodes[2] = tmpDist; 481 482 uint tmpNodeIndex = closer; 483 closer = other; 484 other = tmpNodeIndex; 485 } 486 487 // it's possible that the nearest primitive is still in the other node, 488 // but we'll check the farther-away node later. 489 490 // push the further node first, then the closer node 491 stackPtr++; 492 traversalStack[stackPtr].node = other; 493 traversalStack[stackPtr].distance = distToChildNodes[2]; 494 495 stackPtr++; 496 traversalStack[stackPtr].node = closer; 497 traversalStack[stackPtr].distance = distToChildNodes[0]; 498 } 499 else if (overlapsLeft) 500 { 501 stackPtr++; 502 traversalStack[stackPtr].node = leftNodeIndex; 503 traversalStack[stackPtr].distance = distToChildNodes[0]; 504 } 505 else if (overlapsRight) 506 { 507 stackPtr++; 508 traversalStack[stackPtr].node = rightNodeIndex; 509 traversalStack[stackPtr].distance = distToChildNodes[2]; 510 } 511 } 512 } 513 } 514 515 if (!notFound && recordNormal) 516 { 517 i.n = primitives[i.index].getNormal(); 518 } 519 520 return !notFound; 521 } 522 523 // finds closest silhouette point on aggregate geometry from sphere center 524 public bool findClosestSilhouettePoint(inout BoundingSphere s, bool flipNormalOrientation, 525 float squaredMinRadius, float precision, 526 inout Interaction i) 527 { 528 if (squaredMinRadius >= s.r2) 529 { 530 return false; 531 } 532 533 TraversalStack traversalStack[FCPW_BVH_MAX_DEPTH]; 534 float2 distToChildNodes = float2(0.0, 0.0); 535 BoundingBox rootBox = nodes[0].getBoundingBox(); 536 bool notFound = true; 537 538 if (rootBox.overlap(s, distToChildNodes[0])) 539 { 540 traversalStack[0].node = 0; 541 traversalStack[0].distance = distToChildNodes[0]; 542 int stackPtr = 0; 543 544 while (stackPtr >= 0) 545 { 546 // pop off the next node to work on 547 uint currentNodeIndex = traversalStack[stackPtr].node; 548 float currentDist = traversalStack[stackPtr].distance; 549 stackPtr--; 550 551 // if this node is further than the closest found primitive, continue 552 if (currentDist > s.r2) 553 { 554 continue; 555 } 556 557 N node = nodes[currentNodeIndex]; 558 if (node.isLeaf()) 559 { 560 // compute distance to silhouettes in leaf node 561 uint nSilhouettes = node.getNumSilhouettes(); 562 for (uint p = 0; p < nSilhouettes; p++) 563 { 564 uint silhouetteIndex = node.getSilhouetteOffset() + p; 565 S silhouette = silhouettes[silhouetteIndex]; 566 if (silhouette.getIndex() == i.index) 567 { 568 // silhouette has already been checked 569 continue; 570 } 571 572 Interaction c; 573 bool found = silhouette.findClosestSilhouettePoint( 574 s, flipNormalOrientation, squaredMinRadius, precision, c); 575 576 // keep the closest silhouette point 577 if (found) 578 { 579 notFound = false; 580 s.r2 = min(s.r2, c.d * c.d); 581 i = c; 582 583 if (squaredMinRadius >= s.r2) 584 { 585 break; 586 } 587 } 588 } 589 } 590 else 591 { 592 // find distance to child nodes 593 // NOTE: Slang does not support short-circuiting with the && operator, hence the clunky code 594 uint leftNodeIndex = currentNodeIndex + 1; 595 N leftNode = nodes[leftNodeIndex]; 596 BoundingCone leftCone = leftNode.getBoundingCone(); 597 bool overlapsLeft = leftCone.isValid(); 598 if (overlapsLeft) 599 { 600 BoundingBox leftBox = leftNode.getBoundingBox(); 601 overlapsLeft = leftBox.overlap(s, distToChildNodes[0]); 602 if (overlapsLeft) 603 { 604 float minAngleRange, maxAngleRange; 605 overlapsLeft = leftCone.overlap(s.c, leftBox, distToChildNodes[0], 606 minAngleRange, maxAngleRange); 607 } 608 } 609 610 uint rightNodeIndex = currentNodeIndex + node.getRightChildOffset(); 611 N rightNode = nodes[rightNodeIndex]; 612 BoundingCone rightCone = rightNode.getBoundingCone(); 613 bool overlapsRight = rightCone.isValid(); 614 if (overlapsRight) 615 { 616 BoundingBox rightBox = rightNode.getBoundingBox(); 617 overlapsRight = rightBox.overlap(s, distToChildNodes[1]); 618 if (overlapsRight) 619 { 620 float minAngleRange, maxAngleRange; 621 overlapsRight = rightCone.overlap(s.c, rightBox, distToChildNodes[1], 622 minAngleRange, maxAngleRange); 623 } 624 } 625 626 // which nodes do we overlap? 627 if (overlapsLeft && overlapsRight) 628 { 629 // assume that the left child is closer 630 uint closer = leftNodeIndex; 631 uint other = rightNodeIndex; 632 633 // ... if the right child was actually closer, swap the relavent values 634 if (distToChildNodes[1] < distToChildNodes[0]) 635 { 636 float tmpDist = distToChildNodes[0]; 637 distToChildNodes[0] = distToChildNodes[1]; 638 distToChildNodes[1] = tmpDist; 639 640 uint tmpNodeIndex = closer; 641 closer = other; 642 other = tmpNodeIndex; 643 } 644 645 // it's possible that the nearest primitive is still in the other node, 646 // but we'll check the farther-away node later. 647 648 // push the further node first, then the closer node 649 stackPtr++; 650 traversalStack[stackPtr].node = other; 651 traversalStack[stackPtr].distance = distToChildNodes[1]; 652 653 stackPtr++; 654 traversalStack[stackPtr].node = closer; 655 traversalStack[stackPtr].distance = distToChildNodes[0]; 656 } 657 else if (overlapsLeft) 658 { 659 stackPtr++; 660 traversalStack[stackPtr].node = leftNodeIndex; 661 traversalStack[stackPtr].distance = distToChildNodes[0]; 662 } 663 else if (overlapsRight) 664 { 665 stackPtr++; 666 traversalStack[stackPtr].node = rightNodeIndex; 667 traversalStack[stackPtr].distance = distToChildNodes[1]; 668 } 669 } 670 } 671 } 672 673 return !notFound; 674 } 675};