| 486 | } |
| 487 | |
| 488 | std::optional<uint32_t> QuadtreeAvailability::findChildNodeIndex( |
| 489 | const QuadtreeTileID& tileID, |
| 490 | const AvailabilityNode* pParentNode) const { |
| 491 | if (!pParentNode || !pParentNode->subtree || |
| 492 | (tileID.level % this->_subtreeLevels) != 0) { |
| 493 | return std::nullopt; |
| 494 | } |
| 495 | |
| 496 | uint32_t subtreeRelativeMask = ~(0xFFFFFFFF << this->_subtreeLevels); |
| 497 | uint32_t mortonIndex = getMortonIndex( |
| 498 | tileID.x & subtreeRelativeMask, |
| 499 | tileID.y & subtreeRelativeMask); |
| 500 | |
| 501 | AvailabilityAccessor subtreeAvailabilityAccessor( |
| 502 | pParentNode->subtree->subtreeAvailability, |
| 503 | *pParentNode->subtree); |
| 504 | |
| 505 | bool subtreeAvailable = false; |
| 506 | uint32_t subtreeIndex = 0; |
| 507 | if (subtreeAvailabilityAccessor.isConstant()) { |
| 508 | subtreeAvailable = subtreeAvailabilityAccessor.getConstant(); |
| 509 | subtreeIndex = mortonIndex; |
| 510 | } else if (subtreeAvailabilityAccessor.isBufferView()) { |
| 511 | uint32_t byteIndex = mortonIndex >> 3; |
| 512 | uint8_t bitIndex = static_cast<uint8_t>(mortonIndex & 7); |
| 513 | uint8_t bitMask = static_cast<uint8_t>(1 << bitIndex); |
| 514 | |
| 515 | std::span<const std::byte> clippedSubtreeAvailability = |
| 516 | subtreeAvailabilityAccessor.getBufferAccessor().subspan(0, byteIndex); |
| 517 | uint8_t availabilityByte = (uint8_t)subtreeAvailabilityAccessor[byteIndex]; |
| 518 | |
| 519 | subtreeAvailable = availabilityByte & bitMask; |
| 520 | |
| 521 | // Calculte the index the child subtree is stored in. |
| 522 | if (subtreeAvailable) { |
| 523 | subtreeIndex = |
| 524 | // TODO: maybe partial sums should be precomputed in the subtree |
| 525 | // availability, instead of iterating through the buffer each time. |
| 526 | AvailabilityUtilities::countOnesInBuffer(clippedSubtreeAvailability) + |
| 527 | AvailabilityUtilities::countOnesInByte( |
| 528 | static_cast<uint8_t>(availabilityByte << (8 - bitIndex))); |
| 529 | } |
| 530 | } |
| 531 | |
| 532 | if (subtreeAvailable) { |
| 533 | return subtreeIndex; |
| 534 | } |
| 535 | |
| 536 | return std::nullopt; |
| 537 | } |
| 538 | |
| 539 | AvailabilityNode* QuadtreeAvailability::findChildNode( |
| 540 | const QuadtreeTileID& tileID, |
no test coverage detected