Shadowmap Caching

TileCache.cpp

//****************************************************************************
//
//  File:       LightShadow.cpp
//  License:    MIT
//  Project:    GLVU
//
//****************************************************************************

#include "LightShadow.h"

#include "Renderables.h"

#include <atomic>

using namespace math;
using namespace std;

namespace GLVU
{

static double atlasSizeTable[] = {
    1.0 / 2,
    1.0 / 4,
    1.0 / 8,
    1.0 / 16,
    1.0 / 32,
    1.0 / 64,
    1.0 / 128
};

const math::float4 AtlasCellTable::InvalidCell(-1, -1, -1, -1);

//****************************************************************************
//
//  Function:   AtlasCellTable::AtlasCellTabe
//
//  Purpose:    Constructs and sets up for up to 64x64 units.
//
//****************************************************************************
AtlasCellTable::AtlasCellTable(int dim) :
    dim_(dim)
{
    levels_ = 0;
    while (dim > 64)
    {
        levels_ += 1;
        dim /= 2;
    }

    cellCount_.resize(levels_ + 1, 0);
    regions_.resize(levels_ + 1);
    Clear();

    dim = dim_;
    levelDims_.resize(levels_ + 1);
    for (int i = 0; i < levels_ + 1; ++i)
    {
        levelDims_[i] = dim;
        dim /= 2;
    }
}

//****************************************************************************
//
//  Function:   AtlasCelLTable::AtlasCellTable
//
//  Purpose:    Constructs, and then configures itself to support up to N-levels.
//              Care should be taken that given params don't result in a level
//              reaching 0x0 units as there are no safety checks.
//
//****************************************************************************
AtlasCellTable::AtlasCellTable(int levels, int dim) :
    dim_(dim),
    levels_(levels)
{
    cellCount_.resize(levels_ + 1, 0);
    regions_.resize(levels_ + 1);
    Clear();

    levelDims_.resize(levels_ + 1);
    for (int i = 0; i < levels_ + 1; ++i)
    {
        levelDims_[i] = dim;
        dim /= 2;
    }
}

//****************************************************************************
//
//  Function:   AtlasCellTable::GetCell
//
//  Purpose:    
//
//  Return:     The coordinates of the cell, or the sentinel InvalidCell value.
//
//****************************************************************************
math::float4 AtlasCellTable::GetCell(int level)
{
    if (level == -1)
        return { -1, -1, -1, -1 };
        
    if (cellCount_[level] > 0 || DivideCells(level - 1))
    {
        auto cell = regions_[level][cellCount_[level] - 1];
        cellCount_[level]--;
        return cell;
    }
    else
        return InvalidCell;
}

//****************************************************************************
//
//  Function:   AtlasCellTable::CalculateLevel
//
//  Purpose:    Calculates subdivision level based on the desired dimensions of the provided tile.
//
//  Return:     The level that is appropriate for a given NxN size.
//
//****************************************************************************
int AtlasCellTable::CalculateLevel(int forSize) const
{
    for (int i = 0; i < levels_ + 1; ++i)
        if (levelDims_[i] == forSize)
            return i;
    return -1;
}

//****************************************************************************
//
//  Function:   AtlasCellTable::Clear
//
//  Purpose:    Wipes all data and resets to a single full cell.
//
//****************************************************************************
void AtlasCellTable::Clear()
{
    cellCount_[0] = 1;
    regions_[0][0] = float4 { 0.0f, 0.0f, 1.0f, 1.0f };
    for (int i = 1; i < levels_ + 1; ++i)
        cellCount_[i] = 0;
}

//****************************************************************************
//
//  Function:   AtlasCellTable::ToViewport
//
//  Purpose:    Converts UV coordinates into meaningful { START, DIM } viewport
//              coordinates that other code uses.
//
//  Return:     UV mapped to viewport.
//
//****************************************************************************
math::uint4 AtlasCellTable::ToViewport(math::float4 value) const
{
    return uint4(value.x * dim_, value.y * dim_, value.Width() * dim_, value.Height() * dim_);
}

//****************************************************************************
//
//  Function:   AtlasCellTable::Divide
//
//  Purpose:    Slices the given rectangle and writes it into the output.
//
//              Why is this unused?
//
//****************************************************************************
void AtlasCellTable::Divide(float4 rect, float4* output)
{
    const float width = (rect.z - rect.x);
    const float height = (rect.w - rect.y);
    const float halfWidth = (rect.z - rect.x) / 2.0f;
    const float halfHeight = (rect.w - rect.y) / 2.0f;

    output[0] = float4 { rect.x, rect.y, rect.x + halfWidth, rect.y + halfHeight }; // 0, 0 -> 0.5, 0.5
    output[1] = float4 { rect.x + halfWidth, rect.y, rect.x + width, rect.y + halfHeight }; // 0.5, 0, -> 1.0, 0.5
    output[2] = float4 { rect.x, rect.y + halfHeight, rect.x + halfWidth, rect.y + height }; // 0, 0.5 -> 0.5, 1.0
    output[3] = float4 { rect.x + halfWidth, rect.y + halfHeight, rect.x + width, rect.y + height }; // 0.5, 0.05 -> 1, 1
}

//****************************************************************************
//
//  Function:   AtlasCellTable::SplitCells
//
//  Purpose:    Chops up the cells at a given level.
//
//****************************************************************************
void AtlasCellTable::SplitCells(int size)
{
    float4 rect = regions_[size][cellCount_[size] - 1];

    const float width = (rect.z - rect.x);
    const float height = (rect.w - rect.y);
    const float halfWidth =  (rect.z - rect.x) / 2.0f;
    const float halfHeight = (rect.w - rect.y) / 2.0f;

    cellCount_[size + 1] = 4;
    cellCount_[size]--;

    ///     |---------| 1,1
    //      |  C | D  |
    ///     |----|----|
    //      |  A | B  |
    /// 0,0 |---------|
    // allocation order is D, C, B, A
    regions_[size + 1][0] = float4 { rect.x, rect.y, rect.x + halfWidth, rect.y + halfHeight }; // 0, 0 -> 0.5, 0.5
    regions_[size + 1][1] = float4 { rect.x + halfWidth, rect.y, rect.x + width, rect.y + halfHeight }; // 0.5, 0, -> 1.0, 0.5
    regions_[size + 1][2] = float4 { rect.x, rect.y + halfHeight, rect.x + halfWidth, rect.y + height }; // 0, 0.5 -> 0.5, 1.0
    regions_[size + 1][3] = float4 { rect.x + halfWidth, rect.y + halfHeight, rect.x + width, rect.y + height }; // 0.5, 0.05 -> 1, 1
}

//****************************************************************************
//
//  Function:   AtlasCellTable::DivideCells
//
//  Purpose:    Tries to divide a given level into 4 cells, will divide
//              up the tree as necessary in an attempt to acquire cells.
//
//  Return:     True if we were able to, false if division failed.
//              If failed then there's no room.
//
//****************************************************************************
bool AtlasCellTable::DivideCells(int level)
{
    if (level < 0 || level > levels_)
        return false;

    if (cellCount_[level] > 0)
    {
        // do we have a cell on our level we can divide?
        SplitCells(level);
        return true;
    }
    else if (DivideCells(level - 1)) 
    {
        // try to go up a level and divide from there
        SplitCells(level);
        return true;
    }
    else
        return false;
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::QuadTreeAllocator
//
//  Purpose:    Constructs and initializes for a given set of dimensions.
//
//****************************************************************************
QuadTreeAllocator::QuadTreeAllocator(uint32_t width, uint32_t height) : 
    width_(width), 
    height_(height)
{
    root_ = new Cell();
    root_->coords_ = math::uint4::FromPosSize(0, 0, width, height);
    root_->Free();
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::~QuadTreeAllocator
//
//  Purpose:    Deletes the root cell, and thus the entire tree.
//
//****************************************************************************
QuadTreeAllocator::~QuadTreeAllocator()
{
    delete root_;
    root_ = nullptr;
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::GetCell
//
//  Purpose:    Grabs a cell from the quad-tree with the appropriate dimensions
//
//  Return:     Viewport coordinates or -1,-1,-1,-1 if unable to acquire a cell.
//
//****************************************************************************
math::uint4 QuadTreeAllocator::GetCell(Cell* cell, uint32_t dim, uintptr_t datum)
{
    // This cell the right size and not taken?
    // cell is bigger or equal, but half of it would be too small
    if (cell->Width() >= dim && (cell->Width()/2) < dim && !cell->taken_ && !cell->AnyTaken())
    {
        cell->taken_ = true;
        if (datum)
        {
            // if we have a datum then mark so we can try to preserve.
            auto& found = datumTable_.find(datum);
            if (found != datumTable_.end())
                found->second.first += 1;
            else
                datumTable_.insert(make_pair(datum, make_pair(1, cell)));
        }
        return cell->ToViewport();
    }

    // if our cell is larger than our size, then continue
    if (cell->Width() > dim)
    {
        // can we and do we need to divide?
        if (cell->children_ == nullptr && cell->Width() > 1)
            cell->Divide();
        if (cell->children_)
        {
            for (int i = 0; i < 4; ++i)
            {
                if (cell->children_[i].taken_)
                    continue;
                auto ret = GetCell(&cell->children_[i], dim, datum);
                if (ret.Width() > 0) // did we get something valid?
                    return ret;
            }
        }
    }

    // Return a sentinel for invaid cell, zero sized.
    return uint4(-1, -1, -1, -1);
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::GetCell
//
//  Purpose:    Base call for attempting to acquire a cell,
//              first checks the datum value for whether a cell has been
//              requested to be used as a sticky.
//
//****************************************************************************
math::uint4 QuadTreeAllocator::GetCell(uint32_t dim, uintptr_t datum)
{
    if (datum)
    {
        // if we have a datum then check it
        auto& found = datumTable_.find(datum);
        if (found != datumTable_.end())
        {
            // is our current cell still a good choice?
            auto foundWidth = found->second.second->Width();
            if (foundWidth >= dim && (foundWidth / 2) < dim)
            {
                found->second.first += 1;
                found->second.second->taken_ = true;
                return found->second.second->ToViewport();
            }

            // not the same size, free the cell we found.
            found->second.second->taken_ = false;
            datumTable_.erase(found);
        }
    }
    return GetCell(root_, dim, datum);
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::QuadTreeAllocator
//
//  Purpose:    Constructs and initializes for a given set of dimensions.
//
//****************************************************************************
void QuadTreeAllocator::ProcessUpdate()
{
    // Check and see if anything has expired.
    vector<uint32_t> toRemove;
    for (auto& rec : datumTable_)
    {
        // anyone that's at 0 should be cleaned since it wasn't marked with a +1 again
        if (rec.second.first <= 0)
            toRemove.push_back(rec.first);

        rec.second.first -= 1; // now mark everything down as having been through a cycle.
    }
    // remove everything we need to
    for (auto r : toRemove)
        datumTable_.erase(r);

    // Free everything indiscriminately (mark them taken again soon).
    root_->Free();

    // mark anyone left in the table as taken so that others can't take it.
    for (auto& rec : datumTable_)
        rec.second.second->taken_ = true;
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::ReturnCell
//
//  Purpose:    Returns the cell associated to a datum back to the allocator.
//
//****************************************************************************
void QuadTreeAllocator::ReturnCell(uintptr_t datum)
{
    auto& found = datumTable_.find(datum);
    if (found != datumTable_.end())
    {
        found->second.second->taken_ = false;
        datumTable_.erase(found);
    }
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::Cell::AnyTaken
//
//  Purpose:    Checks if this cell or any of its' children are marked as taken.
//
//  Return:     True, if taken.
//
//****************************************************************************
bool QuadTreeAllocator::Cell::AnyTaken() const
{
    if (children_)
    {
        if (children_[0].AnyTaken() ||
            children_[1].AnyTaken() ||
            children_[2].AnyTaken() || 
            children_[3].AnyTaken())
            return true;
    }
    return taken_;
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::CollectRects
//
//  Purpose:    Recurses through the tree collecting the rectangles of everything
//              that isn't claimed, this can be used to gather the minimum number
//              of clear rects for something like vkCmdClearAttachments.
//
//****************************************************************************
void QuadTreeAllocator::CollectRects(Cell* cell, vector<uint4>& holder)
{
    if (cell->AnyTaken())
    {
        if (cell->children_)
        {
            if (!cell->children_[0].taken_)
                CollectRects(&cell->children_[0], holder);
            if (!cell->children_[1].taken_)
                CollectRects(&cell->children_[1], holder);
            if (!cell->children_[2].taken_)
                CollectRects(&cell->children_[2], holder);
            if (!cell->children_[3].taken_)
                CollectRects(&cell->children_[3], holder);
        }
    }
    else
        holder.push_back(cell->ToViewport());
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::CollectRects
//
//  Purpose:    Public wrapper around the recursive rect collector.
//
//****************************************************************************
void QuadTreeAllocator::CollectRects(vector<uint4>& holder)
{
    CollectRects(root_, holder);
}

//****************************************************************************
//
//  Function:   QuadTreeAllocator::Clear
//
//  Purpose:    Resets state of the quad-tree allocator so that everything is clear.
//
//****************************************************************************
void QuadTreeAllocator::Clear()
{
    root_->Clear();
    datumTable_.clear();
}

}

TileCache.h

//****************************************************************************
//
//  File:       LightShadow.h
//  License:    MIT
//  Project:    GLVU
//  Contents:   Core lighting and shadowing backend needs.
//              Not the actual rendering/execution (yet at least),
//              but the guts needed such as atlasing and tile clustering.
//
//****************************************************************************

#pragma once

#include "glvu.h"
#include "RenderScript.h"

namespace GLVU
{

    class IQueriableScene;

    /// Subdividing allocator for square blocks of a 2D domain. Doesn't actually care what purpose.
    class AtlasCellTable
    {
    public:
        /// Construct for a number of levels and a given total size (ie. 5 subdivisions of a 4096x4096 texture).
        AtlasCellTable(int levels, int dim);
        /// Construct for a fitment to a 64x64 minimum tile size.
        AtlasCellTable(int dim);

        /// Helper to hide need for levels knowledge.
        math::float4 GetArea(int size) { return GetCell(CalculateLevel(size)); }
        /// Try to get a texture-region for a given subdivision level.
        math::float4 GetCell(int level);
        /// Determines the subdivision levels based on an actual pixel-size (such as 64x64)
        int CalculateLevel(int forSize) const;
        /// Reset the state.
        void Clear();

        /// Convert into a viewport appropriate rect. As in glViewport
        math::uint4 ToViewport(math::float4) const;

        /// Sentinel value for comparisons.
        static const math::float4 InvalidCell;

        static void Divide(float4 input, float4* output);

    private:
        /// Inner handling of splitting a subdivision.
        void SplitCells(int level);
        /// Outer logical concerns for whether to split and from where in the tree to split if there is no one suitable.
        bool DivideCells(int level);

        /// Count of cells in each region.
        std::vector<int> cellCount_;
        /// There's never more than 4 cells needed for a given level at any time due to subdivision spiral
        std::vector< std::array<float4, 4> > regions_;

        /// LUT for mapping a pixel-size to a level of subdivision.
        std::vector<int> levelDims_;
        /// Intended dimensions of our texture.
        int dim_;
        /// Number of subdivision levels.
        int levels_;
    };

    /// Subdividing alloator for blocks of a 2D domain. Doesn't actually care what purpose.
    /// Unlike the AtlasCellTable this one supports retaining cells for caching purposes
    /// 
    class QuadTreeAllocator
    {
        struct Cell {
            Cell* children_ = nullptr;
            math::uint4 coords_;
            bool taken_ = false;

            ~Cell() {
                if (children_)
                    delete[] children_;
                children_ = nullptr;
            }

            void Clear() {
                if (children_)
                {
                    children_[0].Clear();
                    children_[1].Clear();
                    children_[2].Clear();
                    children_[3].Clear();
                }
                taken_ = false;
            }

            void Free() {
                if (children_)
                {
                    children_[0].Free();
                    children_[1].Free();
                    children_[2].Free();
                    children_[3].Free();
                }
                taken_ = false;
            }
            void Divide() {
                children_ = new Cell[4];
                
                const unsigned bX = coords_.x;
                const unsigned bY = coords_.y;
                const unsigned w = coords_.z / 2;
                const unsigned h = coords_.w / 2;
                children_[0].coords_ = math::uint4(bX, bY, w, h);
                children_[1].coords_ = math::uint4(bX + w, bY, w, h);
                children_[2].coords_ = math::uint4(bX, bY + h, w, h);
                children_[3].coords_ = math::uint4(bX + w, bY + h, w, h);
            }
            inline math::uint4 ToViewport() {
                return math::uint4::FromPosSize(coords_.x, coords_.y, coords_.z, coords_.w);
            }

            inline uint32_t Width() const { return coords_.z; }
            inline uint32_t Height() const { return coords_.w; }
            bool AnyTaken() const;
        };
        Cell* root_;

        math::uint4 GetCell(Cell*, uint32_t dim, uintptr_t datum = 0);
        void CollectRects(Cell*, std::vector<math::uint4>&);

        std::map<uintptr_t, std::pair<int, Cell*> > datumTable_;

    public:
        QuadTreeAllocator(uint32_t width, uint32_t height);
        ~QuadTreeAllocator();

        // as in glViewport
        inline math::uint4 ToViewport(math::float4 value) const {
            return uint4(value.x * width_, value.y * height_, value.Width() * width_, value.Height() * height_);
        }

        inline math::float4 ToFractional(math::uint4 value) const {
            return math::float4(value.x / (float)width_, value.y / (float)height_, value.z / (float)width_, value.w / (float)height_);
        }

        math::uint4 GetCell(uint32_t dim, uintptr_t datum = 0);
        void ProcessUpdate();
        void ReturnCell(uintptr_t datum);
        void CollectRects(std::vector<math::uint4>&);
        void Clear();

        uint32_t width_;
        uint32_t height_;
    };
}