OGC3DTilesSubtree.cpp

#include "OGC3DTilesSubtree.h"
#include "OGC3DTilesUtils.h"
 
#include "Systems/OGC3DTilesSystem.h"
#include "ExtensionRegistry.h"
 
#include <Context.h>
#include <Engine.h>
 
#include <Foundation/Logging/Logger.h>
#include <Foundation/Platform/IO.h>
#include <Foundation/BitTwiddling/MortonCode.h>
 
#include <Serialization/JsonParser.h>
 
#include <tuple>
#include <cassert>
#include <bitset>
 
using namespace Cogs::Core;
using namespace Cogs::Core::OGC3DTilesSubtree;
using namespace std::chrono_literals;
 
namespace {
  Cogs::Logging::Log logger = Cogs::Logging::getLogger("OGC3DTilesSubtree");
 
  // Ref: https://github.com/CesiumGS/3d-tiles/tree/draft-1.1/specification/ImplicitTiling#subtree-binary-format
  struct Header {
    uint32_t magic;
    uint32_t version;
    uint64_t jsonLength;
    uint64_t bitstreamLength;
  };
 
  // Will interleave A and B, bitwise.
  inline uint32_t interleaveBits(uint16_t a, uint16_t b)
  {
    return Cogs::mortonCode(a, b);
  }
 
  // Will interleave A, B and C, bitwise.
  inline uint64_t interleaveBits(uint16_t a, uint16_t b, uint16_t c)
  {
    // FIXME: We should do some checking here to see if the result will exceed 32bit
    // and maybe print some warnings. If not, prepare the code for 64-bits morton codes
    // in OctTree-mode.
    // NOTE: I assume that a Morton code which exceeds 32bit is not realistic in our scenario,
    // expecially when it comes to checking the content/subtree availability bitset. A 32bit+ index
    // would mean that the subtree-bitset would exceed 0xffffff+ bytes in length, ie. 16+ MB.
    return Cogs::mortonCode(a, b, c);
  }
 
  inline uint32_t concatBits(uint16_t a, uint16_t b, int numBitsFromB)
  {
    b = b << (16 - numBitsFromB);
    uint32_t ax = uint32_t(a) << 16;
    ax = ax + b;
    return ax >> (16 - numBitsFromB);
  }
 
  // Ref:  https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/
  inline uint32_t removeTwoSpacing(uint32_t v) {
    v &= 0x09249249;
    v = (v ^ (v >> 2)) & 0x030c30c3;
    v = (v ^ (v >> 4)) & 0x0300f00f;
    v = (v ^ (v >> 8)) & 0xff0000ff;
    v = (v ^ (v >> 16)) & 0x000003ff;
    return v;
  }
  inline uint32_t removeOneSpacing(uint32_t x)
  {
    x &= 0x55555555;
    x = (x ^ (x >> 1)) & 0x33333333;
    x = (x ^ (x >> 2)) & 0x0f0f0f0f;
    x = (x ^ (x >> 4)) & 0x00ff00ff;
    x = (x ^ (x >> 8)) & 0x0000ffff;
    return x;
  }
}
 
#if 0
// Debug utility
// NOTE: The Subtree-object needs to have been given a correct 'levelsPerSubtree' value from the tileset
void
printAvailableSubtrees(const Subtree* subtree)
{
  int bitstreamIdx = subtree->childSubtreeAvailability.bitstreamIdx;
  int level = subtree->globalCoord.level + subtree->levelsPerSubtree;
  int range = (int)OGC3DTilesUtils::fastPow2(level);
  bool isOctTree = subtree->globalCoord.z >= 0;
 
  printf("subtree->globalCoord.level=%d, levelsPerSubtree=%d\n", subtree->globalCoord.level, subtree->levelsPerSubtree);
  LOG_DEBUG(logger, "printAvailableSubtrees(): level=%d, range=%d, section=%d (x=%d, y=%d, z=%d):",
    level, range, bitstreamIdx, subtree->globalCoord.x, subtree->globalCoord.y, subtree->globalCoord.z);
 
  if (subtree->childSubtreeAvailability.availableCount == 0) {
    LOG_DEBUG(logger, "  => No subtrees available\n");
    return;
  }
 
  for (int x = 0; x < range; ++x) {
    for (int y = 0; y < range; ++y) {
      for (int z = 0; z < range; ++z) {
        uint32_t mortonIndex = 0;
        if (isOctTree) {
          mortonIndex = interleaveBits(x, y, z);
        }
        else {
          mortonIndex = interleaveBits(x, y);
        }
 
        uint32_t levelOffset = 0; // The subtree-array is always a single array/level.
        uint32_t offset = levelOffset + mortonIndex;
 
        assert(bitstreamIdx < subtree->bitstreamSections.size() && "Index out of bounds");
        const BitstreamSection& section = subtree->bitstreamSections[bitstreamIdx];
 
        auto bsBegin = subtree->bitstreams[section.bitstreamIdx].cbegin();
        std::vector<unsigned char>::const_iterator start = bsBegin + section.startIdx;
        std::vector<unsigned char>::const_iterator end = bsBegin + section.startIdx + section.length;
        std::vector<unsigned char> buf(start, end);
 
        int coarseIdx = offset >> 3; // Divide by 8
        int fineIdx = offset & 0b111;
 
        assert(level >= 0 && "Internal error");
        assert(coarseIdx < buf.size() && "Index out of bounds");
 
        unsigned char val = buf[coarseIdx];
        std::bitset<8> valBits(val);
 
        bool isSet = valBits.test(fineIdx);
        if (isSet) {
          if (isOctTree) LOG_DEBUG(logger, "  %d.%d.%d.%d.subtree\n", level, x, y, z);
          else LOG_DEBUG(logger, "  %d.%d.%d.subtree\n", level, x, y);
 
          LOG_DEBUG(logger, " parent?: %d:%d|%d\n", level - 1, x >> 1, y >> 1);
        }
 
        if (!isOctTree) {
          break;
        }
      }
    }
  }
}
#endif
 
bool
parseAvailabilityJSON(const Value& value, Availability* target)
{
  target->allIsAvailable = false; // We'll assume all tiles are available unless specified
  target->availableCount = 0;
 
  if (value.HasMember("constant")) {
    target->allIsAvailable = value["constant"].GetInt() >= 1;
  }
 
  if (!target->allIsAvailable && value.MemberCount() > 1) {
    if (value.HasMember("availableCount")) {
      target->availableCount = value["availableCount"].GetInt();
    }
    else {
      LOG_ERROR(logger, "Availability struct must contain a 'availableCount' member if 'constant=0' or undefined.");
      return false;
    }
 
    if (value.HasMember("bitstream")) {
      target->bitstreamIdx = value["bitstream"].GetInt();
    }
    else {
      if (target->availableCount != 0) {
        LOG_ERROR(logger, "Availability struct must contain a 'bitstream' member if 'constant==0' or undefined and 'availibilityCount != 0'.");
        return false;
      }
    }
  }
 
  return true;
}
 
void
fetchSubtreeBufferFile(Context* context, const std::string& URI, const std::string& originURL, Subtree* target, int bufferIdx, uint32_t uniqueComponentId)
{
  assert(bufferIdx < int(target->bitstreamSections.size()));
 
  size_t pos = originURL.rfind("/");
  assert(pos != std::string::npos && "Invalid originURL");
  std::string baseURL = originURL.substr(0, pos);
  std::string newURL = baseURL + "/" + URI;
 
  // Does the originURL contain an "access_token" parameter?
  // FIXME: Do we need to do the same with the "key=" session keys used by some servers?
  size_t accessTokenPos = originURL.find("access_token");
  if (accessTokenPos != std::string::npos) {
    size_t endPos = originURL.find("&", accessTokenPos);
    if (endPos == std::string::npos) {
      endPos = originURL.size();
    }
    std::string accessToken = originURL.substr(accessTokenPos, endPos - accessTokenPos);
    newURL += "?" + accessToken;
  }
 
  target->bitstreams.resize(target->bitstreamSections.size());
 
  // FIXME: We should explicitly register WHICH subtrees we are waiting for. This will make it possible
  // to start processing before all subtrees are loaded (see OGC3DTilesSubtree::getChildren() f.ex).
  target->pendingRequests += 1;
 
  (void)DataFetcherManager::fetchAsync(context, newURL,
    [context, target, bufferIdx, uniqueComponentId](std::unique_ptr<Cogs::FileContents> inData) {
      if (OGC3DTilesSystem::componentIsStale(context, uniqueComponentId) || !inData.get()) {
        return;
      }
 
      auto data = inData.release();
      BitstreamSection section = target->bitstreamSections[bufferIdx];
 
      target->bitstreams[section.bitstreamIdx].reserve(section.length);
      for (size_t j = 0; j < section.length; ++j) {
        target->bitstreams[section.bitstreamIdx].emplace_back(data->ptr[section.startIdx + j]);
      }
      target->pendingRequests -= 1;
 
      // As this request is an async prosess independent of the original subtree-request,
      // we'll have to flag that the 3DTiles component needs an update.
      OGC3DTilesSystem* system = ExtensionRegistry::getExtensionSystem<OGC3DTilesSystem>(context);
      for (auto& comp : system->pool) {
        OGC3DTilesDataHolder& h = system->getData(&comp);
        OGC3DTilesData* componentState = h.data.get();
        if (componentState->uniqueComponentId == uniqueComponentId) {
          context->engine->setDirty();
          break;
        }
      }
 
      delete data;
    });
}
 
bool
parseSubtreeBufferJSON(Context* context, std::string_view json, Subtree* target, const std::string& originURL, uint32_t uniqueComponentId)
{
  Document doc = parseJson(json, JsonParseFlags::None);
 
  std::vector<std::vector<std::pair<uint32_t, uint32_t>>> bufferSections;
  if (doc.HasMember("bufferViews")) {
    GenericArray array = doc["bufferViews"].GetArray();
    for (Value& bv : array) {
      if (!(bv.HasMember("buffer") && bv.HasMember("byteOffset") && bv.HasMember("byteLength"))) {
        LOG_ERROR(logger, "No 'buffer', 'byteOffset' and 'byteLength' in 'bufferViews' section");
        return false;
      }
      BitstreamSection bss{
        (uint8_t) bv["buffer"].GetUint(), // "bitstreamIdx"
        bv["byteOffset"].GetUint(),       // "startIdx"
        bv["byteLength"].GetUint()        // "length"
      };
      target->bitstreamSections.emplace_back(bss);
    }
  }
 
  bool ok = true;
  if (doc.HasMember("tileAvailability")) {
    ok &= parseAvailabilityJSON(doc["tileAvailability"], &target->tileAvailability);
    if (!ok) {
      LOG_ERROR(logger, "Could not parse 'tileAvailability'");
    }
 
    if (!target->tileAvailability.allIsAvailable && target->tileAvailability.availableCount != 0) {
      assert(target->tileAvailability.bitstreamIdx < target->bitstreams.size() && "Bitstream index out of bounds");
    }
  }
  else {
    LOG_ERROR(logger, "Subtree JSON did not contain a 'tileAvailability' section.");
    return false;
  }
 
  if (doc.HasMember("contentAvailability")) {
    GenericArray array = doc["contentAvailability"].GetArray();
    target->contentAvailability.resize(array.Size());
    int i = 0;
    for (Value& c : array) {
      ok &= parseAvailabilityJSON(c, &target->contentAvailability[i]);
      if (!ok) {
        LOG_ERROR(logger, "Could not parse 'contentAvailability' nr %d", (i + 1));
      }
      i += 1;
    }
  }
  else {
    LOG_ERROR(logger, "Subtree JSON did not contain a 'contentAvailability' section.");
    return false;
  }
 
  if (doc.HasMember("childSubtreeAvailability")) {
    ok &= parseAvailabilityJSON(doc["childSubtreeAvailability"], &target->childSubtreeAvailability);
    if (!ok) {
      LOG_ERROR(logger, "Could not parse 'childSubtreeAvailability'");
    }
  }
  else {
    LOG_ERROR(logger, "Subtree JSON did not contain a 'childSubtreeAvailability' section.");
    return false;
  }
 
  if (doc.HasMember("buffers") && target->tileAvailability.availableCount > 0) {
    GenericArray array = doc["buffers"].GetArray();
    int bufferIdx = 0;
    for (Value& buf : array) {
      assert(buf.HasMember("byteLength"));
 
      if (buf.HasMember("uri")) {
        //LOG_DEBUG(logger, "Subtree.buffer is not of type 'Internal Buffer'. Fetching '%s'", buf["uri"].GetString());
        fetchSubtreeBufferFile(context, buf["uri"].GetString(), originURL, target, bufferIdx, uniqueComponentId);
      }
      else {
        // Default/internal buffer which is already loaded
        assert(bufferIdx == 0 && "Internal buffer must always be index 0");
      }
      ++bufferIdx;
    }
  }
  else {
    if (!target->tileAvailability.allIsAvailable && target->tileAvailability.availableCount > 0) {
      LOG_ERROR(logger, "Subtree JSON has sparse tile-availibility but did not contain a 'buffers' section.");
      return false;
    }
  }
 
  return ok;
}
 
bool
parseSubtreeBufferBinary(Context* context, const Cogs::Memory::MemoryBuffer* buf, Subtree* target, const std::string& originURL, uint32_t uniqueComponentId)
{
  const uint8_t* data = static_cast<const uint8_t*>(buf->data());
  const Header* h = (const Header*)data;
 
  if (h->magic != 0x74627573) {
    LOG_ERROR(logger, "Subtree header magic value was not 0x74627573 (was 0x%x)", h->magic);
    return false;
  }
 
  if (h->version != 1) {
    LOG_ERROR(logger, "Subtree version was not '1' (was %d)", h->version);
    return false;
  }
 
  // Read bitstreams before we parse the JSON for easier validation.
  if (h->bitstreamLength > 0) {
    // As a default we'll always load the data into bitstream #1.
    uint32_t paddedJSONLength = static_cast<uint32_t>(h->jsonLength);
    uint32_t offset = sizeof(Header) + paddedJSONLength;
    const uint8_t* bitstreamStartPtr = &(static_cast<const uint8_t*>(buf->data())[offset]);
    target->bitstreams.emplace_back(std::vector<uint8_t>(bitstreamStartPtr, bitstreamStartPtr + h->bitstreamLength));
  }
  else {
    LOG_ERROR(logger, "parseSubtreeBufferBinary(): BitstreamLength value in header <= 0");
    return false;
  }
 
  const char* jsonStartPtr = &(static_cast<const char*>(buf->data())[sizeof(Header)]);
  const std::string json = std::string(jsonStartPtr, h->jsonLength);
  bool ok = parseSubtreeBufferJSON(context, json, target, originURL, uniqueComponentId);
  if (!ok) {
    return false;
  }
 
#if 0
  if (target->bitstreamSections.size() > 1) {
    LOG_DEBUG(logger, "parseSubtreeBufferBinary(): Bitstream sections:");
    for (int x = 1; x < target->bitstreamSections.size(); ++x) {
      BitstreamSection section = target->bitstreamSections[x];
      int bufIdx = section.bitstreamIdx;
      int start = section.startIdx;
      int len = section.length;
 
      LOG_DEBUG(logger, " #%d: BufferIdx=%d, start=%d, len=%d => [ ", x, bufIdx, start, len);
      for (int i = (len - 1); i >= 0; --i) {
        std::bitset<8> x(target->bitstreams[bufIdx][i]);
        std::cout << x << ' ';
      }
      LOG_DEBUG(logger, "] (NB: read backwards)\n");
    }
  }
#endif
  return true;
}
 
std::vector<OGC3DTiles::Coord>
OGC3DTilesSubtree::getLeafNodesSubtreeCoords(const Subtree* subtree, const OGC3DTiles::Coord& leafNodeCoord)
{
  std::vector<OGC3DTiles::Coord> coords;
 
  if (subtree->childSubtreeAvailability.allIsAvailable) {
    return getAllChildren(subtree, leafNodeCoord);
  }
 
  if (subtree->childSubtreeAvailability.availableCount == 0 || subtree->pendingRequests > 0) {
    return coords;
  }
 
  const int bitstreamIdx = subtree->childSubtreeAvailability.bitstreamIdx;
  assert(bitstreamIdx < int(subtree->bitstreamSections.size()) && "Index out of bounds");
  const OGC3DTilesSubtree::BitstreamSection& section = subtree->bitstreamSections[bitstreamIdx];
 
  const bool isOctTree = subtree->globalCoord.z >= 0;
  const OGC3DTiles::Coord localCoord = globalToLocal(subtree, leafNodeCoord);
 
  const uint64_t leafNodeMortonIndex = isOctTree ?
    interleaveBits(uint16_t(leafNodeCoord.x), uint16_t(leafNodeCoord.y), uint16_t(leafNodeCoord.z)) :
    interleaveBits(uint16_t(leafNodeCoord.x), uint16_t(leafNodeCoord.y));
 
  const uint64_t localMortonIndex = isOctTree ?
    interleaveBits(uint16_t(localCoord.x), uint16_t(localCoord.y), uint16_t(localCoord.z)) :
    interleaveBits(uint16_t(localCoord.x), uint16_t(localCoord.y));
 
  assert(leafNodeMortonIndex * (isOctTree ? 8 : 4) <= 0xFFFFFFFF && "Morton code for leaf-node is out of 32bit range");
  const uint32_t leafNodeOffset = uint32_t(isOctTree ? leafNodeMortonIndex * 8 : leafNodeMortonIndex * 4);
  const uint32_t localOffset = uint32_t(isOctTree ? localMortonIndex * 8 : localMortonIndex * 4);
 
  const int num = isOctTree ? 8 : 4;
  coords.reserve(num);
 
  const std::vector<uint8_t>& bitarray = subtree->bitstreams[section.bitstreamIdx];
  const size_t bufSize = bitarray.size();
 
  for (int i = 0; i < num; ++i) {
    const uint32_t offset = localOffset + i;
    const uint32_t coarseIdx = offset >> 3; // Divide by 8
    const int fineIdx = offset & 0b111;
    assert(coarseIdx < section.length && "Buffer index out of bounds for bitstream section");
    assert(section.startIdx + coarseIdx < bufSize && "Buffer index out of bounds for bitstream");
 
    const uint8_t val = bitarray[section.startIdx + coarseIdx];
    if (val) {
      std::bitset<8> valBits(val);
      if (valBits.test(fineIdx)) {
        OGC3DTiles::Coord subtreeCoord = mortonCodeToCoord(isOctTree, leafNodeCoord.level + 1, leafNodeOffset + i);
        coords.emplace_back(subtreeCoord);
      }
    }
  }
 
  return coords;
}
 
bool
OGC3DTilesSubtree::isLeafNodeInSubtree(const Subtree* subtree, const OGC3DTiles::Coord& coord)
{
  assert(coord.level <= subtree->globalCoord.level + subtree->levelsPerSubtree && "Coord level is deeper into subtree than allowed max depth.");
  const bool isLeaf = coord.level == subtree->globalCoord.level + (subtree->levelsPerSubtree - 1);
  return isLeaf;
}
 
std::vector<OGC3DTiles::Coord>
OGC3DTilesSubtree::getAllChildren(const Subtree* subtree, const OGC3DTiles::Coord& parent)
{
  std::vector<OGC3DTiles::Coord> children;
 
  const bool isOctTree = subtree->globalCoord.z >= 0;
 
  const uint64_t parentMortonCode = isOctTree ?
    interleaveBits(uint16_t(parent.x), uint16_t(parent.y), uint16_t(parent.z)) :
    interleaveBits(uint16_t(parent.x), uint16_t(parent.y));
 
  assert(parentMortonCode * (isOctTree ? 8 : 4) <= 0xFFFFFFFF && "Morton code for parent is out of 32bit range");
  const uint32_t offset = uint32_t(isOctTree ? parentMortonCode * 8 : parentMortonCode * 4);
 
  const int num = isOctTree ? 8 : 4;
  children.resize(num);
 
  for (int i = 0; i < num; ++i) {
    children[i] = mortonCodeToCoord(isOctTree, parent.level + 1, offset + i);
  }
 
  return children;
}
 
std::vector<OGC3DTiles::Coord>
OGC3DTilesSubtree::getChildren(const Subtree* subtree, const OGC3DTiles::Coord& parent)
{
  std::vector<OGC3DTiles::Coord> children;
  if (subtree->pendingRequests > 0) {
    return children;
  }
 
  int bitstreamIdx = subtree->tileAvailability.bitstreamIdx;
  assert(bitstreamIdx < int(subtree->bitstreamSections.size()) && "Index out of bounds");
  const OGC3DTilesSubtree::BitstreamSection& section = subtree->bitstreamSections[bitstreamIdx];
  const std::vector<uint8_t>& bitarray = subtree->bitstreams[section.bitstreamIdx];
 
  const bool isOctTree = subtree->globalCoord.z >= 0;
  const OGC3DTiles::Coord localCoord = globalToLocal(subtree, parent);
 
  const uint64_t parentMortonCode = isOctTree ?
    interleaveBits(uint16_t(parent.x), uint16_t(parent.y), uint16_t(parent.z)) :
    interleaveBits(uint16_t(parent.x), uint16_t(parent.y));
  assert(parentMortonCode * (isOctTree ? 8 : 4) <= 0xFFFFFFFF && "Morton code for parent is out of 32bit range");
  const uint32_t globalOffset = uint32_t(isOctTree ? parentMortonCode * 8 : parentMortonCode * 4);
 
  const uint32_t levelOffset = isOctTree ?
    static_cast<uint32_t>((OGC3DTilesUtils::fastPow8(localCoord.level + 1) - 1) / (8 - 1)) :
    static_cast<uint32_t>((OGC3DTilesUtils::fastPow4(localCoord.level + 1) - 1) / (4 - 1));
 
  const uint64_t localMortonCode = isOctTree ?
    interleaveBits(uint16_t(localCoord.x), uint16_t(localCoord.y), uint16_t(localCoord.z)) :
    interleaveBits(uint16_t(localCoord.x), uint16_t(localCoord.y));
  const uint32_t localOffset = uint32_t(isOctTree ? localMortonCode * 8 : localMortonCode * 4);
 
  const int num = isOctTree ? 8 : 4;
  children.reserve(num);
 
  for (int i = 0; i < num; ++i) {
    int offset = levelOffset + localOffset + i;
    const uint32_t coarseIdx = offset >> 3; // Divide by 8
    assert(coarseIdx < section.length && "Index out of bounds for bitstream section");
    const int fineIdx = offset & 0b111;
 
    assert(section.startIdx + coarseIdx < bitarray.size() && "Index out of bounds");
    const uint8_t val = bitarray[section.startIdx + coarseIdx];
    if (val) {
      std::bitset<8> valBits(val);
      if (valBits.test(fineIdx)) {
        children.emplace_back(mortonCodeToCoord(isOctTree, parent.level + 1, globalOffset + i));
      }
    }
  }
 
  return children;
}
 
Cogs::Core::DataFetcherManager::FetchId
OGC3DTilesSubtree::fetchSubtree(Cogs::Core::Context* context, const std::string& URL, uint32_t uniqueComponentId, FetchSubtreeCallback callback)
{
  Cogs::Core::DataFetcherManager::FetchId fetchId = DataFetcherManager::fetchAsync(context, URL,
    [context, URL, callback, uniqueComponentId](std::unique_ptr<Cogs::FileContents> inData) {
      if (OGC3DTilesSystem::componentIsStale(context, uniqueComponentId)) {
        return;
      }
 
      Cogs::FileContents* data = inData.get();
      Subtree* subtree = nullptr;
      bool success = false;
 
      if (data && data->data()) {
        subtree = new Subtree;
        subtree->pendingRequests = 0;
        subtree->tileAvailability.allIsAvailable = false;
        subtree->childSubtreeAvailability.allIsAvailable = false;
 
        size_t paramPos = URL.find_last_of('?');
        const std::string fileURL = URL.substr(0, paramPos == std::string::npos ? URL.size() : paramPos);
 
        Memory::MemoryBuffer contentsBuff = inData->take();
        if (IO::extension(fileURL) == ".subtree" || IO::extension(fileURL) == ".SUBTREE") {
          success = parseSubtreeBufferBinary(context, &contentsBuff, subtree, URL, uniqueComponentId);
        }
        else if (IO::extension(fileURL) == ".json" || IO::extension(fileURL) == ".JSON") {
          std::string_view jsonStr = std::string_view(static_cast<const char*>(contentsBuff.data()), contentsBuff.size());
          success = parseSubtreeBufferJSON(context, jsonStr, subtree, URL, uniqueComponentId);
        }
        else {
          LOG_ERROR(logger, "fetchSubtree(): Unknown subtree extension for '%s'", fileURL.c_str());
        }
 
        if (!success) {
          delete subtree;
          subtree = nullptr;
        }
      }
      else {
        LOG_ERROR(logger, "fetchSubtree(): Could not fetch subtree '%s'", URL.c_str());
      }
 
      auto finishTask = [callback, subtree]() {
        callback(subtree);
      };
 
#if defined(EMSCRIPTEN)
      // Cogs.js support - no threading
      (void)context; // Silence unused capture warning.
      finishTask();
#else
      context->engine->runTaskInMainThread(std::move(finishTask));
#endif
    });
 
  return fetchId;
}
 
bool
checkAvailability(const Subtree* subtree, int bitstreamSectionIdx, int localLevel, int localX, int localY, /*opt*/ int localZ)
{
  if (subtree->pendingRequests > 0) {
    return false;
  }
 
  uint32_t levelOffset = 0;
  uint64_t mortonIndex = 0;
  if (localZ >= 0) { // We are in Octree mode
    levelOffset = static_cast<uint32_t>((OGC3DTilesUtils::fastPow8(localLevel) - 1) / (8 - 1));
    mortonIndex = static_cast<uint32_t>(interleaveBits(static_cast<uint16_t>(localX), static_cast<uint16_t>(localY), static_cast<uint16_t>(localZ)));
  }
  else {
    levelOffset = static_cast<uint32_t>((OGC3DTilesUtils::fastPow4(localLevel) - 1) / (4 - 1));
    mortonIndex = interleaveBits(static_cast<uint16_t>(localX), static_cast<uint16_t>(localY));
  }
  assert(mortonIndex < 0xFFFFFFFF && "Internal error. Morton index is way too large.");
 
  uint32_t offset = levelOffset + ((uint32_t) mortonIndex);
 
  assert(bitstreamSectionIdx < int(subtree->bitstreamSections.size()) && "Index out of bounds");
  const BitstreamSection& section = subtree->bitstreamSections[bitstreamSectionIdx];
 
  if (section.bitstreamIdx >= subtree->bitstreams.size()) {
    LOG_ERROR(logger, "checkAvailibility(): Bitstream index > number of available bitstreams (%d vs %d)", section.bitstreamIdx, (int)subtree->bitstreams.size());
    return false;
  }
  assert(section.bitstreamIdx < subtree->bitstreams.size());
 
  const std::vector<uint8_t>& bitarray = subtree->bitstreams[section.bitstreamIdx];
 
  uint32_t coarseIdx = offset >> 3; // Divide by 8
  uint32_t fineIdx = offset & 0b111;
  assert(coarseIdx < section.length && "Index out of bounds for section bitstream");
  assert(section.startIdx + coarseIdx < bitarray.size() && "Index out of bounds to bitstream");
 
  unsigned char val = bitarray[section.startIdx + coarseIdx];
  std::bitset<8> valBits(val);
  return valBits.test(fineIdx);
}
 
bool
OGC3DTilesSubtree::hasContent(const Subtree* subtree, const OGC3DTiles::Coord& coord)
{
  const OGC3DTiles::Coord & localCoord = globalToLocal(subtree, coord);
 
  bool hasContent = false;
  for (const Availability& c : subtree->contentAvailability) {
    if (c.allIsAvailable) {
      hasContent = true;
      break;
    }
    else if (c.availableCount > 0) {
      hasContent = checkAvailability(subtree, c.bitstreamIdx, localCoord.level, localCoord.x, localCoord.y, localCoord.z);
      if (hasContent) {
        break;
      }
    }
  }
 
  return hasContent;
}
 
OGC3DTiles::Coord
OGC3DTilesSubtree::getSubtreesRootCoord(int levelsPerSubtree, const OGC3DTiles::Coord& coord)
{
  int subtreeLevel = coord.level / levelsPerSubtree;
  int levelsLeft = coord.level % levelsPerSubtree;
 
  return OGC3DTiles::Coord{ subtreeLevel * levelsPerSubtree,
    coord.x >> levelsLeft,
    coord.y >> levelsLeft,
    coord.z >= 0 ? coord.z >> levelsLeft : -1 };
}
 
OGC3DTiles::Coord
OGC3DTilesSubtree::globalToLocal(const Subtree* subtree, const OGC3DTiles::Coord& globalCoord)
{
  const int relativeLevel = globalCoord.level - subtree->globalCoord.level;
  return OGC3DTiles::Coord{
    relativeLevel,
    globalCoord.x - (subtree->globalCoord.x << relativeLevel),
    globalCoord.y - (subtree->globalCoord.y << relativeLevel) ,
    globalCoord.z >= 0 ? globalCoord.z - (subtree->globalCoord.z << relativeLevel) : -1
  };
}
 
OGC3DTiles::Coord
OGC3DTilesSubtree::mortonCodeToCoord(bool isOctTree, int level, uint32_t mortonCode)
{
  OGC3DTiles::Coord coord;
  coord.level = level;
 
  if (isOctTree) {
    coord.x = removeTwoSpacing(mortonCode);
    coord.y = removeTwoSpacing(mortonCode >> 1);
    coord.z = removeTwoSpacing(mortonCode >> 2);
  }
  else {
    coord.x = removeOneSpacing(mortonCode);
    coord.y = removeOneSpacing(mortonCode >> 1);
    coord.z = -1;
  }
 
  return coord;
}