OctSystem.cpp

#include "Context.h"
#include "ExtensionRegistry.h"
#include "Systems/Core/CameraSystem.h"
#include "Systems/Core/TransformSystem.h"
#include "Resources/MaterialManager.h"
 
#include "../OctBounds.h"
#include "OctSystem.h"
#include "../Renderers/OctRenderer.h"
 
#include "Rendering/ICapabilities.h"
#include "Rendering/IBuffers.h"
#include "Rendering/IEffects.h"
 
#include "Foundation/BitTwiddling/MortonCode.h"
#include "Foundation/BitTwiddling/PowerOfTwo.h"
#include "Foundation/Geometry/Glm.hpp"
#include "Foundation/Logging/Logger.h"
#include "Foundation/HashSequence.h"
 
 
namespace {
  using namespace Cogs::Core;
 
  Cogs::Logging::Log logger = Cogs::Logging::getLogger("OctSystem");
 
  void updateMaterialVariant(Volumetric::OctData& octData)
  {
    switch (octData.source)
    {
    case Volumetric::OctSource::Value:
      octData.materialInstance->setVariant("Source", "Value");
      break;
    case Volumetric::OctSource::ValueAge:
      octData.materialInstance->setVariant("Source", "ValueAge");
       break;
    }
    octData.materialInstance->setVariant("AlphaTest", "Discard");
    octData.materialInstance->setFloatProperty(octData.materialInstance->material->getFloatKey("alphaThreshold"), 0.0f);
  }
 
 
 
  bool forgetRegion(Volumetric::OctData& octData, const uint64_t regionKey)
  {
    auto jt = octData.knownRegions.find(regionKey);
    if (jt != octData.knownRegions.end()) {
      auto & regData = jt->second;
      for (const auto blockKey : regData->baseBlocks) {
 
        // Find block and erase.
        auto lt = octData.baseBlocks.find(blockKey);
        lt->second->regionKeys.erase(regData->regionKey);
 
        // If block has no regions left, delete it.
        if (lt->second->regionKeys.empty()) {
          octData.baseBlockPool.destroy(lt->second);
          octData.baseBlocks.erase(lt);
        }
      }
 
      octData.knownRegionPool.destroy(jt->second);
      octData.knownRegions.erase(jt);
      return true;
    }
    return false;
  }
 
  bool removeRegions(Volumetric::OctComponent& octComp, Volumetric::OctData& octData)
  {
    for (const auto regionKey : octComp.regionsToRemove) {
      forgetRegion(octData, regionKey);
    }
    auto rv = !octComp.regionsToRemove.empty();
    octComp.regionsToRemove.clear();
    return rv;
  }
 
  bool addRegions(Volumetric::OctComponent& octComp, Volumetric::OctData& octData, std::vector<Volumetric::Region>& regionsToAdd)
  {
    const glm::vec3 blockScale(1.f / octComp.blockExtent.x,
                               1.f / octComp.blockExtent.y,
                               1.f / octComp.blockExtent.z);
 
    const auto skirtExpand = float(Volumetric::OctSystem::skirtSize) / float(octComp.tileSize - Volumetric::OctSystem::skirtSize);
 
    const glm::vec3 skirtExtent = octComp.blockExtent * skirtExpand;
    
    const auto M = glm::scale(blockScale) * glm::translate(-octComp.blockShift);
 
 
    for (auto & region : regionsToAdd) {
 
      Volumetric::OctRegionData* regData = octData.knownRegionPool.create();
      regData->regionKey = region.regionKey;
      regData->min = region.min;
      regData->max = region.max;
 
      // Determine range of base blocks intersecting the region.
      glm::ivec3 i;
      const auto A4 = M * glm::vec4(region.min - skirtExtent, 1.f);
      const auto A = glm::ivec3(glm::floor((1.f / A4.w)*glm::vec3(A4)));
 
      const auto B4 = M * glm::vec4(region.max + skirtExtent, 1.f);
      const auto B = glm::ivec3(glm::floor((1.f / B4.w)*glm::vec3(B4)));
      regData->baseBlocks.reserve((B.x - A.x + 1)*(B.y - A.y + 1)*(B.z - A.z + 1));
      for (i.z = A.z; i.z <= B.z; i.z++) {
        for (i.y = A.y; i.y <= B.y; i.y++) {
          for (i.x = A.x; i.x <= B.x; i.x++) {
            const auto baseBlockKey = Volumetric::createBaseBlockKey(i.x, i.y, i.z);
 
            Volumetric::OctBaseBlock* baseBlock;
            auto blockIt = octData.baseBlocks.find(baseBlockKey);
            if (blockIt == octData.baseBlocks.end()) {      // New base block
              baseBlock = octData.baseBlockPool.create();
              baseBlock->ix3 = i;
              octData.baseBlocks[baseBlockKey] = baseBlock;
            }
            else {
              baseBlock = blockIt->second;
            }
 
            baseBlock->timestamp = octData.currentTimestamp;
            baseBlock->regionKeys.insert(region.regionKey);
            regData->baseBlocks.push_back(baseBlockKey);
          }
        }
      }
 
      if (forgetRegion(octData, region.regionKey)) {
        LOG_DEBUG(logger, "Region %PRIu64 overwritten", region.regionKey);
      }
      octData.knownRegions[region.regionKey] = std::move(regData);
    }
    auto rv = !regionsToAdd.empty();
    regionsToAdd.clear();
    return rv;
  }
 
  void wipe(Volumetric::OctData* octData)
  {
    LOG_DEBUG(logger, "Wiped %d baseblocks and %d regions.", unsigned(octData->baseBlocks.size()), unsigned(octData->knownRegions.size()));
    for (auto it : octData->baseBlocks) {
      octData->baseBlockPool.destroy(it.second);
    }
    octData->baseBlocks.clear();
 
    for (auto it : octData->knownRegions) {
      octData->knownRegionPool.destroy(it.second);
    }
    octData->knownRegions.clear();
  }
 
}
 
 
Cogs::Core::Volumetric::OctData::~OctData()
{
  // Make sure that destructors for pool contents get called.
  wipe(this);
}
 
void Cogs::Core::Volumetric::OctSystem::initialize(Context * context)
{
  ComponentSystemWithDataPool::initialize(context);
 
  renderer = new OctRenderer();
  context->renderer->registerExtension(renderer);
 
  material = context->materialManager->loadMaterial("OcttreeRaycastMaterial.material");
  context->materialManager->processLoading();
  transferTexKey = material->getTextureKey("transferTexture");
  volumeTexKey = material->getTextureKey("volumeTexture");
 
  bounds = new OctBounds();
  bounds->octSystem = this;
  context->bounds->addBoundsExtension(bounds);
 
  auto device = context->device;
  auto buffers = device->getBuffers();
 
  Cogs::EffectDescription desc;
  desc.name = "DebugEffect";
  desc.type = EffectDescriptionType::File;
  switch (device->getType()) {
  case Cogs::GraphicsDeviceType::OpenGLES30:
    desc.vertexShader = "Engine/DebugVS.es30.glsl";
    desc.pixelShader = "Engine/DebugPS.es30.glsl";
    desc.flags = static_cast<EffectFlags::EEffectFlags>(desc.flags | EffectFlags::GLSL);
    break;
  default:
    desc.vertexShader = "Engine/DebugVS.hlsl";
    desc.pixelShader = "Engine/DebugPS.hlsl";
    break;
  }
  effectHandle = device->getEffects()->loadEffect(desc);
 
  VertexElement elements[] = {
    { 0, DataFormat::X32Y32Z32_FLOAT, ElementSemantic::Position, 0, InputType::VertexData, {} }
  };
  debugVertexFormat = buffers->createVertexFormat(elements, 1);
}
 
bool Cogs::Core::Volumetric::OctSystem::isDebugEffectReady(Context* context)
{
  Cogs::IEffects* effects = context->device->getEffects();
  Cogs::ResourceStatus status = effects->checkEffect(effectHandle);
 
  if (status == Cogs::ResourceStatus::Ready && effectStatus != Cogs::ResourceStatus::Ready) {
    Cogs::IBuffers* buffers = context->device->getBuffers();
    inputLayoutHandle = buffers->loadInputLayout(&debugVertexFormat, 1, effectHandle);
  }
 
  if (status == Cogs::ResourceStatus::Error && effectStatus != Cogs::ResourceStatus::Error) {
    LOG_ERROR(logger, "OctSystem: Failed to build debug wireframe effect.");
  }
 
  effectStatus = status;
  return status == Cogs::ResourceStatus::Ready;
}
 
Cogs::ComponentModel::ComponentHandle Cogs::Core::Volumetric::OctSystem::createComponent()
{
  auto component = ComponentSystemWithDataPool::createComponent();
  auto * comp = component.resolveComponent<OctComponent>();
  comp->system = this;
  auto & data = getData(comp);
  data.comp = comp;
  for (unsigned i = 0; i < 32; i++) {
    data.tileResponsesStash.push_back(new TileResponse());
  }
  data.materialInstance = context->materialInstanceManager->createMaterialInstance(material);
  updateMaterialVariant(data);
  return component;
}
 
void Cogs::Core::Volumetric::OctSystem::update(Context * context)
{
  for (auto & octComp : pool) {
    auto & octData = getData(&octComp);
 
    if (octData.source != octComp.source) {
      octData.source = octComp.source;
      updateMaterialVariant(octData);
      octComp.forceWipe = true;
    }
 
    octData.currentTimestamp++;
    bool baseBlocksModified = false;
 
    // Sanity checks on octComp properties, force to sane ranges.
    octComp.tileSize = std::max(8u, std::min(256u, octComp.tileSize));
    octComp.gpuCacheSize = std::max(1u, std::min((2048 / octComp.tileSize), octComp.gpuCacheSize));
 
    // Check if basic assumptions used by the system has changed, if so, flush everything.
    const size_t layoutHash = hashSequence(octComp.blockExtent,
                                           octComp.blockShift,
                                           octComp.tileSize,
                                           octComp.gpuCacheSize);
    if (octComp.forceWipe || octComp.clearAllRegions ||  octData.layoutHash != layoutHash) {
      octComp.forceWipe = false;
      octComp.clearAllRegions = false;
      octData.gpuCacheWipe = true;
      octData.layoutHash = layoutHash;
      octData.maxFrontSize = octComp.gpuCacheSize * octComp.gpuCacheSize * octComp.gpuCacheSize - 1u;
 
      std::vector<Region> knownRegions;
      if (!octComp.clearAllRegions) {
        // Wipe and re-insert regions.
        knownRegions.reserve(octData.knownRegions.size());
        for (auto & it : octData.knownRegions) {
          const auto * regData = it.second;
          knownRegions.push_back(Region{ regData->regionKey, regData->min, regData->max });
        }
      }
      wipe(&octData);
      addRegions(octComp, octData, knownRegions);
      baseBlocksModified = true;
    }
 
    baseBlocksModified = addRegions(octComp, octData, octComp.regionsToAdd) || baseBlocksModified;
    baseBlocksModified = removeRegions(octComp, octData) || baseBlocksModified;
 
    if(baseBlocksModified) {
      buildTree(context, octComp, octData);
    }
 
    // Update current subset of oct-tree nodes based on viewports.
    const auto * camComp = context->cameraSystem->getMainCamera();
    const auto & camData = context->cameraSystem->getMainCameraData();
    const auto * transComp = octComp.getComponent<TransformComponent>();
    adaptiveSubset(context, octComp, octData, *transComp, *camComp, camData);
 
    // Build list of tile requests, update timestamps
    octComp.tileRequests.clear();
    for (auto & item : octData.front) {
      const auto & node = octData.nodes[item];
      const auto tileKey = createTileKey(node.ix4, octData.alignMinToZeroShift);
      auto staleness = octData.atlas.checkTile(tileKey, node.timestamp, octData.currentTimestamp);
      if (staleness == 0) {
        continue;
      }
      octComp.tileRequests.emplace_back(TileRequest{ tileKey, staleness });
    }
    std::stable_sort(octComp.tileRequests.begin(), octComp.tileRequests.end(), [](const auto &a, const auto & b) {return a.staleness > b.staleness; });
  }
 
}
 
 
void Cogs::Core::Volumetric::OctSystem::buildTree(Context* /*context*/, OctComponent& /*octComp*/, OctData& octData)
{
  auto & base = octData.baseBlocks;
  auto & nodes = octData.nodes;
 
  if (base.empty()) return;
 
  // Find min/max index.
  glm::i16vec3  baseBlockMinIndex = base.begin()->second->ix3;
  glm::i16vec3  baseBlockMaxIndex = base.begin()->second->ix3;
  for (auto & it : base) {
    baseBlockMinIndex = glm::min(baseBlockMinIndex, it.second->ix3);
    baseBlockMaxIndex = glm::max(baseBlockMaxIndex, it.second->ix3);
  }
 
  // An invariant of the oct-tree buildup is that all indices are non-negative.
  
 
 
  // Realign pyramid if we have new data on the negative sides. Try to preserve nodes by
  // moving in steps proportional to size of top node.
  if ((baseBlockMinIndex.x < octData.alignMinToZeroShift.x) || (baseBlockMinIndex.y < octData.alignMinToZeroShift.y) || (baseBlockMinIndex.z < octData.alignMinToZeroShift.z))
  {
    auto d = std::max(std::max((baseBlockMaxIndex.x - baseBlockMinIndex.x), (baseBlockMaxIndex.y - baseBlockMinIndex.y)), (baseBlockMaxIndex.z - baseBlockMinIndex.z));
    auto l = roundUpToPowerOfTwoShift((unsigned)d);
    auto m = -1 << l;
    octData.alignMinToZeroShift.x = baseBlockMinIndex.x & m;
    octData.alignMinToZeroShift.y = baseBlockMinIndex.y & m;
    octData.alignMinToZeroShift.z = baseBlockMinIndex.z & m;
    LOG_DEBUG(logger, "alignMinToZeroShift=[%d, %d, %d], l=%d", octData.alignMinToZeroShift.x, octData.alignMinToZeroShift.y, octData.alignMinToZeroShift.z, l);
  }
 
  // Build base layer
  nodes.clear();
  for (auto & it : octData.baseBlocks) {
    glm::uvec4 ix4 = glm::uvec4(it.second->ix3 - octData.alignMinToZeroShift, 0);
    nodes.emplace_back(NodeBlock{});
    nodes.back().ix = mortonCode(static_cast<uint16_t>(ix4.x),
                                 static_cast<uint16_t>(ix4.y),
                                 static_cast<uint16_t>(ix4.z));
    nodes.back().timestamp = it.second->timestamp;
    nodes.back().ix4 = ix4;
    nodes.back().extentMin = glm::uvec3(ix4);
    nodes.back().extentMax = glm::uvec3(ix4) + glm::uvec3(1);
    nodes.back().baseBlock = it.second;
  }
 
  // Sort by Morton code, which linearizes the 3D structure of the oct-tree.
  std::sort(nodes.begin(), nodes.end(), [](const auto& a, const auto& b) -> bool { return a.ix < b.ix; });
 
  // And build upper layers until we have a single apex node.
  size_t offset = 0;
  for (uint16_t l = 1; l < 16 && (1 < nodes.size() - offset); l++) {
    size_t nextOffset = nodes.size();
 
    NodeBlock * parent = nullptr;
    for (size_t i = offset; i < nextOffset; i++) {
      const auto child = nodes[i];
      // Upper bits of morton code give parent index.
      const auto parentIx = child.ix >> 3;
 
      // Sorted by morton code, so when parent index changes, so the childs of a parent lies successively.
      if (!parent || parent->ix != parentIx) {
        nodes.emplace_back(NodeBlock{});
        parent = &octData.nodes.back();
        parent->ix = parentIx;
        parent->timestamp = child.timestamp;
        parent->ix4 = glm::u16vec4(child.ix4.x >> 1, child.ix4.y >> 1, child.ix4.z >> 1, l);
        parent->extentMin = child.extentMin;
        parent->extentMax = child.extentMax;
        for (unsigned k = 0; k < 8; k++) parent->children[k] = ~0u;
      }
      // Some trickery comparing age instead of timestamps directly handle wrap-around of timestamps.
      parent->timestamp = octData.currentTimestamp - std::min(octData.currentTimestamp - parent->timestamp,
                                                              octData.currentTimestamp - child.timestamp);
      // Grow parent to include child node.
      parent->extentMin = glm::min(parent->extentMin, child.extentMin);
      parent->extentMax = glm::max(parent->extentMax, child.extentMax);
      // Lower three bits of morton code give child index.
      parent->children[child.ix & 7] = static_cast<uint32_t>(i);
    }
    offset = nextOffset;
  }
}
 
glm::mat4 Cogs::Core::Volumetric::OctSystem::LocalFromIndexSpaceTransform(const OctComponent& octComp, const OctData& octData)
{
  return
    glm::translate(glm::mat4(), octComp.blockShift) *
    glm::scale(octComp.blockExtent) *
    glm::translate(glm::mat4(), glm::vec3(octData.alignMinToZeroShift));
}
 
glm::mat4 Cogs::Core::Volumetric::OctSystem::IndexSpaceFromLocalTransform(const OctComponent& octComp, const OctData& octData)
{
  return
    glm::translate(glm::mat4(), -glm::vec3(octData.alignMinToZeroShift)) *
    glm::scale(glm::vec3(1.f / octComp.blockExtent.x,
                         1.f / octComp.blockExtent.y,
                         1.f / octComp.blockExtent.z)) *
    glm::translate(glm::mat4(), -octComp.blockShift);
}
 
 
void Cogs::Core::Volumetric::OctSystem::adaptiveSubset(Context * context,
                                                       OctComponent& octComp, OctData& octData,
                                                       const TransformComponent& transComp,
                                                       const CameraComponent& /*camComp*/, const CameraData& camData)
{
  const auto & nodes = octData.nodes;
  auto & front = octData.front;
  auto & stack = octData.stack;
 
  if (nodes.empty()) return;
 
  // Fixme: use LODreference
  // Discard only nodes that is not in any frustums, i.e. process all frustums simultaneously.
 
 
  const auto & worldFromLocal = context->transformSystem->getLocalToWorld(&transComp);
  const auto localFromWorld = glm::inverse(worldFromLocal);
  const auto & ViewFromWorld = camData.viewMatrix;
  const auto & worldFromView = camData.inverseViewMatrix;
  const auto & ClipFromWorld = camData.viewProjection;
  const auto LocalFromIxspc = LocalFromIndexSpaceTransform(octComp, octData);
  const auto IxspcFromLocal = IndexSpaceFromLocalTransform(octComp, octData);
  const auto viewFromIxspc = ViewFromWorld * worldFromLocal * LocalFromIxspc;
  const auto ixspcFromView = IxspcFromLocal * localFromWorld * worldFromView;
  const auto clipFromIxspc = ClipFromWorld * worldFromLocal * LocalFromIxspc;
  const auto camOriginIxspc = glm::vec3(ixspcFromView[3]);
 
  auto buildFront =
    [maxFrontSize = octData.maxFrontSize,
    &nodes,
    &stack,
    &viewFromIxspc,
    &clipFromIxspc,
    &camOriginIxspc](auto & front, const auto threshold) -> bool
  {
    front.clear();
    stack.clear();
    stack.push_back(static_cast<uint32_t>(nodes.size() - 1));
 
    while (!stack.empty()) {
      const auto nodeIx = stack.back();
      stack.pop_back();
 
      const auto & n = nodes[nodeIx];
 
      // Check if node is inside frustum.
      unsigned planes = 0;
      for (unsigned i = 0; i < 8; i++) {
        const glm::vec4 p((i & 1) == 0 ? n.extentMin.x : n.extentMax.x,
          (i & 2) == 0 ? n.extentMin.y : n.extentMax.y,
                          (i & 4) == 0 ? n.extentMin.z : n.extentMax.z,
                          1.f);
        auto v = viewFromIxspc * p;
        auto c = clipFromIxspc * p;
        planes = planes |
          (v.z < 0.f ? 1 : 0) |
          (c.x <= c.w ? 2 : 0) | (-c.w <= c.x ? 4 : 0) |
          (c.y <= c.w ? 8 : 0) | (-c.w <= c.y ? 16 : 0);
      }
 
      if (planes == 31) {
        // Find point inside node nearest to camera, and determine camera distance.
        glm::vec3 nearestIxspc = glm::clamp(camOriginIxspc, glm::vec3(n.extentMin), glm::vec3(n.extentMax));
        glm::vec4 nearestView = viewFromIxspc * glm::vec4(nearestIxspc, 1.f);
        float camDist = -nearestView.z / nearestView.w;
 
        if ((0 < n.ix4.w) && (camDist*threshold < (1 << n.ix4.w))) {
          for (auto childIx : n.children) {
            if (childIx != ~0u) stack.push_back(childIx);
          }
        }
        else {
          front.push_back(nodeIx);
          if (maxFrontSize < front.size()) {
            return false;
          }
        }
      }
    }
    return true;
  };
 
  float tolerance = std::max(0.01f, octData.tolerance);
  //const auto maxFrontSize = octData.maxFrontSize;
 
  // Try building front until it is smaller than the max size, doubling the tolerance for each try.
  bool success = false;
  for (unsigned i = 0; i < 8 && !success; i++) {
    success = buildFront(front, tolerance);
    if (!success) {
      tolerance = 2 * tolerance;
    }
  }
 
  const auto minFrontSize = (size_t)std::max(1.f, 0.9f*octData.maxFrontSize);
  for (unsigned i = 0; i < 8 && octComp.tolerance < tolerance && front.size() < minFrontSize; i++) {
    auto t = std::max(octComp.tolerance, 0.9f*tolerance);
    if (buildFront(octData.frontTmp, t)) {
      tolerance = t;
      octData.front.swap(octData.frontTmp);
    }
    else {
      break;
    }
  }
 
  //LOG_DEBUG(logger, "front size=%d / %d", octData.front.size(), octData.maxFrontSize);
 
  if (octData.tolerance != tolerance) {
    LOG_DEBUG(logger, "Current tolerance set to %f", octData.tolerance);
  }
  octData.tolerance = tolerance;
 
}