TexAtlasLodTree.cpp

#include <algorithm>
 
#include "Foundation/Logging/Logger.h"
 
#include "Systems/Core/CameraSystem.h"
#include "Systems/Core/TransformSystem.h"
 
#include "Context.h"
 
#include "TexAtlasSystem.h"
 
namespace {
  using namespace Cogs::Core;
  using namespace Cogs::Core::TexAtlas;
 
  Cogs::Logging::Log logger = Cogs::Logging::getLogger("TexAtlas");
 
  bool mightBeVisible(const glm::mat4& M, const glm::mat4& V, const glm::vec4* corners, bool restrictBetweenNearAndFar)
  {
    if (restrictBetweenNearAndFar) {
      uint32_t anyInside = 0;
      for (size_t i = 0; i < 8; i++) {
        const glm::vec4 p = M * corners[i];
        if (-p.w < p.x) anyInside |= 1;
        if (p.x < p.w)  anyInside |= 2;
        if (-p.w < p.y) anyInside |= 4;
        if (p.y < p.w)  anyInside |= 8;
        if (-p.w < p.z) anyInside |= 16;
        if (p.z < p.w)  anyInside |= 32;
      }
      return anyInside == 0b111111u;
    }
    else {
      uint32_t anyInside = 0;
      for (size_t i = 0; i < 8; i++) {
        const glm::vec4 p = M * corners[i];
        if (-p.w < p.x) anyInside |= 1;
        if (p.x < p.w)  anyInside |= 2;
        if (-p.w < p.y) anyInside |= 4;
        if (p.y < p.w)  anyInside |= 8;
 
        const glm::vec4 q = V * corners[i];
        if (q.z < 0.f) anyInside |= 16;
      }
      return anyInside == 0b011111u;
    }
  }
 
  float getScaledError(const glm::mat4& /*P*/, const glm::mat4& V, glm::vec4* corners, float texelSizeView, float tolerance, uint32_t level)
  {
    float near = std::numeric_limits<float>::max();
    for (size_t i = 0; i < 8; i++) {
      near = std::min(near, -(V * corners[i]).z);
    }
    return texelSizeView / (2.f * tolerance * (1 << level) * std::max(1.0f, near));
  }
 
  // Convenience func to wrap lookups
  SlotIx getOrAllocCacheSlotWrap(Context* context, Cache& cache, Fetcher& fetcher, const LodTree::Tile& tile)
  {
    const uint32_t mask = (1u << tile.level) - 1u;
    return cache.getOrAllocCacheSlot(context, fetcher, glm::uvec3(uint32_t(tile.x) & mask,
                                                                  uint32_t(tile.y) & mask,
                                                                  tile.level));
  }
 
}
 
void Cogs::Core::TexAtlas::Geometry::calcTileCorners(glm::vec4* corners, const LodTree::Tile& tile) const
{
  const float w = 1.f / float(1 << tile.level);
  glm::vec2 u0 = w * glm::vec2(tile.x, tile.y);
  glm::vec2 u1 = w * glm::vec2(tile.x + 1, tile.y + 1);
 
  glm::vec2 d0 = glm::clamp(invDomainMapScale * (u0 + invDomainMapShift), glm::vec2(0.0), glm::vec2(1.0));
  glm::vec2 d1 = glm::clamp(invDomainMapScale * (u1 + invDomainMapShift), glm::vec2(0.0), glm::vec2(1.0));
 
  glm::vec2 U[4] = {
    glm::vec2(d0.x, d0.y),
    glm::vec2(d1.x, d0.y),
    glm::vec2(d1.x, d1.y),
    glm::vec2(d0.x, d1.y)
  };
 
  for (size_t i = 0; i < 4; i++) {
    const glm::vec2& u = U[i];
    glm::vec2 p = (coefficients[0] * (1.f - u.x) * (1.f - u.y) +
                   coefficients[1] * u.x * (1.f - u.y) +
                   coefficients[2] * (1.f - u.x) * u.y +
                   coefficients[3] * u.x * u.y);
 
    corners[i + 0] = glm::vec4(p, elevationMin, 1.f);
    corners[i + 4] = glm::vec4(p, elevationMax, 1.f);
  }
}
 
namespace {
 
  bool compareTile(const LodTree::Tile& a, const LodTree::Tile& b)
  {
    return a.error < b.error;
  }
 
}
 
void Cogs::Core::TexAtlas::LodTree::update(Context* context, const Geometry& geo, Cache& cache, Fetcher& fetcher, const Layout& layout, float tolerance, bool restrictBetweenNearAndFar, bool lodFreeze)
{
  // Upper two bits control the meaning of the lower bits.
  constexpr uint16_t TileHasData                  = 0x0000u;  // Tile is loaded, lower bits contains atlas slot of tile.
  constexpr uint16_t TileIsRefined                = 0x4000u;  // Tile is refined, lower bits contain tree offset to first of four consecutive elemnts containing child nodes.
  constexpr uint16_t TileHadDataAndIsDebugFlagged = 0x8000u;  // Tile is loaded, but flagged for debugging purposes.
  constexpr uint16_t TileNotYetLoaded             = 0xc000u;  // Tile is not yet loaded, lower bits contain atlas slot of parent tile.
 
  (void)TileHadDataAndIsDebugFlagged; // Don't complain on this being used when it is not in use.
 
  if (!lodFreeze) {
 
    const CameraData& camData = context->cameraSystem->getMainCameraData();
    const glm::mat4 P = camData.rawProjectionMatrix;
    const glm::mat4 V = camData.viewMatrix;
 
    const glm::mat4 PV = camData.rawViewProjection;
 
    float baseLevelPixels = std::max(1u, fetcher.tileWidth) * glm::length(glm::vec2(geo.domain[1] - geo.domain[0]));
    float baseLevelExtent = static_cast<float>(std::sqrt(std::abs(glm::cross(glm::dvec3(geo.coefficients[2] - geo.coefficients[0], 0.f), glm::dvec3(geo.coefficients[3] - geo.coefficients[0], 0.f)).z +
                                                                  glm::cross(glm::dvec3(geo.coefficients[3] - geo.coefficients[0], 0.f), glm::dvec3(geo.coefficients[1] - geo.coefficients[0], 0.f)).z)));
    float texelSizeWorld = baseLevelExtent / baseLevelPixels;
    float texelSizeView = glm::determinant(glm::mat3(V)) * texelSizeWorld;
 
    // screen x-axis in world space
    glm::vec3 x_w = glm::normalize(glm::vec3(camData.inverseViewMatrix * glm::vec4(1.f, 0.f, 0.f, 0.f)));
 
    // Calculate the max allowed size. This is the size of a tile at the near plane.
    /*float maxAllowedSize = 0.f;
    {
      const glm::mat4 PVinv = glm::inverse(PV);
      const glm::vec4 o = PVinv * glm::vec4(0.f, 0.f, -1.f, 1.f);
      glm::vec4 a = PV * o;
      glm::vec4 b = PV * (o + o.w * glm::vec4(x_w, 0.f));
      maxAllowedSize = b.x / b.w - a.x / a.w;
    }*/
 
 
    encoded.resize(std::max(1u, layout.size.x * layout.size.y));
 
    glm::vec4 corners[8];
 
    candidates.clear();
    for (uint32_t j = 0; j < layout.size.y; j++) {
      for (uint32_t i = 0; i < layout.size.x; i++) {
 
        Tile tile{
          .error = 0.f,
          .x = layout.offset.x + int32_t(i),
          .y = layout.offset.y + int32_t(j),
          .level = static_cast<uint8_t>(layout.level),
          .encodedIx = static_cast<uint16_t>(j * layout.size.x + i),
          .slotIx = 0
        };
 
        // We probe cache of tile regardless of it being visible or not, as we
        // try to keep the most coarse version always in cache.
        tile.slotIx = getOrAllocCacheSlotWrap(context, cache, fetcher, tile);
        if (tile.slotIx != NoSlotIx) {
          encoded[tile.encodedIx] = tile.slotIx;
          geo.calcTileCorners(corners, tile);
          if (mightBeVisible(PV, V, corners, restrictBetweenNearAndFar)) {
            tile.error = getScaledError(P, V, corners, texelSizeView, tolerance, tile.level);
            if (1.f < tile.error) {
              candidates.push_back(tile);
            }
          }
        }
 
        else {
          encoded[tile.encodedIx] = TileNotYetLoaded;
        }
      }
    }
 
 
    std::make_heap(candidates.begin(), candidates.end(), compareTile);
 
    // We process tiles as the group of four children so we have the four children
    // adjacent in the encoded array (simplifies traversal in shader).
 
    tiles.clear();
    while (!candidates.empty()) {
 
      // Pop visible parent
      std::pop_heap(candidates.begin(), candidates.end(), compareTile);
      tiles.push_back(candidates.back());
      candidates.pop_back();
 
      // Check if parent tile should be refined
      const Tile& parentTile = tiles.back();
      if (parentTile.level < layout.maxLevel) {
 
        bool anyValid = false;
        uint32_t firstSlot = static_cast<uint32_t>(encoded.size());
 
        for (int32_t j = 0; j < 2; j++) {
          for (int32_t i = 0; i < 2; i++) {
 
            Tile childTile{
              .error = 0.f,
              .x = 2 * parentTile.x + i,
              .y = 2 * parentTile.y + j,
              .level = static_cast<uint8_t>(parentTile.level + 1),
              .encodedIx = static_cast<uint16_t>(encoded.size()),
              .slotIx = NoSlotIx
            };
 
            geo.calcTileCorners(corners, childTile);
            if (mightBeVisible(PV, V, corners, restrictBetweenNearAndFar)) {
              childTile.error = getScaledError(P, V, corners, texelSizeView, tolerance, childTile.level);
              if (1.f < childTile.error) {
                childTile.slotIx = getOrAllocCacheSlotWrap(context, cache, fetcher, childTile);
                if (childTile.slotIx != NoSlotIx) {
 
                  candidates.push_back(childTile);
                  std::push_heap(candidates.begin(), candidates.end(), compareTile);
 
                  anyValid = true;
                }
              }
            }
 
            if (childTile.slotIx != NoSlotIx) {
              encoded.push_back(childTile.slotIx + TileHasData);
            }
            else {
              // If this tile is refined, we do not yet have data here, so we use the parent's data.
              encoded.push_back(TileNotYetLoaded + parentTile.slotIx);
            }
          }
        }
 
 
        if (anyValid) {
          // Update parent to point at that the first of the four slots
          encoded[parentTile.encodedIx] = TileIsRefined + static_cast<uint16_t>(firstSlot);
        }
        else {
          // Otherwise, discard the slots allocated in this iteration
          encoded.resize(firstSlot);
        }
 
      }
    }
  }
 
  // Make sure texture has at least one element.
  if (encoded.empty()) {
    encoded.push_back(0xc000u);
  }
}