ChunkData.cpp

#include "ChunkData.h"

#include <cassert>
#include <cstring>

ChunkData::ChunkData()
    : m_sideLength(0)
    , m_height(0)
    , m_isDirty(false)
    , m_data(nullptr)
    , m_mutex(nullptr)
{
}

ChunkData::ChunkData(uint32_t sideLength, uint32_t height)
    : m_sideLength(sideLength)
    , m_height(height)
    , m_isDirty(false)
    , m_mutex(new std::mutex())
{
    const uint32_t numVoxels = m_sideLength * m_sideLength * m_height;
    m_data = std::unique_ptr<Voxel[]>(new Voxel[numVoxels]);
    memset(m_data.get(), 0, numVoxels);
}

Voxel *ChunkData::data()
{
    return m_data.get();
}

std::mutex &ChunkData::dataMutex()
{
    return *m_mutex;
}

uint32_t ChunkData::sideLength() const
{
    return m_sideLength;
}

uint32_t ChunkData::height() const
{
    return m_height;
}

bool ChunkData::isDirty()
{
    return m_isDirty;
}

Voxel ChunkData::voxelAt(uint32_t xPos, uint32_t yPos, uint32_t zPos) const
{
    assert(xPos < m_sideLength);
    assert(yPos < m_height);
    assert(zPos < m_sideLength);

    return m_data[xPos +
                  yPos * m_sideLength +
                  zPos * m_sideLength * m_height];
}

Voxel ChunkData::voxelAt(const Vector3DInt &pos) const
{
    return voxelAt(pos.X(), pos.Y(), pos.Z());
}

void ChunkData::setDirty(bool isDirty)
{
    m_isDirty = isDirty;
}

void ChunkData::setVoxelAt(uint32_t xPos, uint32_t yPos, uint32_t zPos, Voxel voxel)
{
    assert(xPos < m_sideLength);
    assert(yPos < m_height);
    assert(zPos < m_sideLength);

    m_data[xPos +
           yPos * m_sideLength +
           zPos * m_sideLength * m_height] = voxel;

    m_isDirty = true;
}

void ChunkData::setVoxelAt(const Vector3DInt &pos, Voxel voxel)
{
    setVoxelAt(pos.X(), pos.Y(), pos.Z(), voxel);
}

ChunkData.h

#ifndef CHUNKDATA_H
#define CHUNKDATA_H

// std includes
#include <memory>
#include <mutex>

// Own includes
#include "Voxel.h"
#include "Vector3DInt.h"

class ChunkData
{
public:
    ChunkData();
    ChunkData(uint32_t sideLength, uint32_t height);

    Voxel *data();
    std::mutex &dataMutex();

    uint32_t sideLength() const;
    uint32_t height() const;

    bool isDirty();
    Voxel voxelAt(uint32_t xPos, uint32_t yPos, uint32_t zPos) const;
    Voxel voxelAt(const Vector3DInt &pos) const;

    void setDirty(bool isDirty);
    void setVoxelAt(uint32_t xPos, uint32_t yPos, uint32_t zPos, Voxel voxel);
    void setVoxelAt(const Vector3DInt &pos, Voxel voxel);

private:
    uint32_t m_sideLength;
    uint32_t m_height;
    bool m_isDirty;

    std::unique_ptr<Voxel[]> m_data;
    std::unique_ptr<std::mutex> m_mutex;
};

#endif // CHUNKDATA_H

SparseVolume.cpp

#include "SparseVolume.h"

#include <list>

using namespace std;

//Note: this function only works for inputs which are a power of two and not zero
//If this is not the case then the output is undefined.
uint8_t logBase2(uint32_t uInput)
{
    uint32_t uResult = 0;
    while( (uInput >> uResult) != 0)
    {
        ++uResult;
    }
    return static_cast<uint8_t>(uResult-1);
}

SparseVolume::SparseVolume(uint32_t chunkSideLength)
    : m_chunkSideLength(chunkSideLength)
{
    m_chunkSideLengthPower = logBase2(m_chunkSideLength);
}

uint8_t SparseVolume::chunkSideLengthPower() const
{
    return m_chunkSideLengthPower;
}

Voxel SparseVolume::voxelAt(int32_t xPos, int32_t yPos, int32_t zPos)
{
    const int32_t blockX = xPos >> m_chunkSideLengthPower;
    const int32_t blockZ = zPos >> m_chunkSideLengthPower;

    const uint32_t xOffset = static_cast<uint32_t>(xPos - (blockX << m_chunkSideLengthPower));
    const uint32_t yOffset = static_cast<uint32_t>(yPos);
    const uint32_t zOffset = static_cast<uint32_t>(zPos - (blockZ << m_chunkSideLengthPower));

    Chunk chunk(blockX, blockZ);
    Voxel voxel;

    lock_guard<mutex> lock(m_mutex);
    auto iter = m_dataHash.find(chunk);
    if (iter != m_dataHash.end()) {
        auto data = iter->second;
        lock_guard<mutex> chunkLock(data->dataMutex());
        voxel = data->voxelAt(xOffset, yOffset, zOffset);
    }

    return voxel;
}

Voxel SparseVolume::voxelAt(const Vector3DInt &pos)
{
    return voxelAt(pos.X(), pos.Y(), pos.Z());
}

void SparseVolume::setVoxelAt(int32_t xPos, int32_t yPos, int32_t zPos, Voxel voxel)
{
    const int32_t blockX = xPos >> m_chunkSideLengthPower;
    const int32_t blockZ = zPos >> m_chunkSideLengthPower;

    const uint32_t xOffset = static_cast<uint32_t>(xPos - (blockX << m_chunkSideLengthPower));
    const uint32_t yOffset = static_cast<uint32_t>(yPos);
    const uint32_t zOffset = static_cast<uint32_t>(zPos - (blockZ << m_chunkSideLengthPower));

    Chunk chunk(blockX, blockZ);

    lock_guard<mutex> lock(m_mutex);
    auto iter = m_dataHash.find(chunk);
    if (iter != m_dataHash.end()) {
        auto data = iter->second;
        lock_guard<mutex> chunkLock(data->dataMutex());
        data->setVoxelAt(xOffset, yOffset, zOffset, voxel);
    }
}

void SparseVolume::loadChunk(const Chunk &chunk, std::shared_ptr<ChunkData> data)
{
    lock_guard<mutex> lock(m_mutex);
    m_dataHash.insert(make_pair(chunk, data));
}

std::shared_ptr<ChunkData> SparseVolume::unloadChunk(const Chunk &chunk)
{
    lock_guard<mutex> lock(m_mutex);
    auto data = m_dataHash.at(chunk);
    m_dataHash.erase(chunk);

    return data;
}

std::shared_ptr<ChunkData> SparseVolume::chunkData(const Chunk &chunk)
{
    lock_guard<mutex> lock(m_mutex);
    return chunkDataUnsafe(chunk);
}

ChunkDataHash SparseVolume::chunkDataAndNeighbors(const Chunk &chunk)
{
    ChunkDataHash dataHash;
    auto pos = chunk.position();

    std::list<Chunk> chunks;

    chunks.push_back(chunk);
    chunks.push_back(Chunk(pos.X()+1, pos.Y()));   // x1 z0
    chunks.push_back(Chunk(pos.X()+1, pos.Y()+1)); // x1 z1
    chunks.push_back(Chunk(pos.X()-1, pos.Y()));   // x-1 z0
    chunks.push_back(Chunk(pos.X()-1, pos.Y()-1)); // x-1 z-1
    chunks.push_back(Chunk(pos.X(), pos.Y()+1));   // x0 y1
    chunks.push_back(Chunk(pos.X()-1, pos.Y()+1)); // x-1 z1
    chunks.push_back(Chunk(pos.X(), pos.Y()-1));   // x0 y-1
    chunks.push_back(Chunk(pos.X()+1, pos.Y()-1)); // x1 y-1

    lock_guard<mutex> lock(m_mutex);
    for (const auto &chunk : chunks) {
        auto chunkData = chunkDataUnsafe(chunk);
        if (chunkData != nullptr)
            dataHash[chunk] = chunkData;
    }

    return dataHash;
}

std::shared_ptr<ChunkData> SparseVolume::chunkDataUnsafe(const Chunk &chunk)
{
    auto iter = m_dataHash.find(chunk);

    if (iter != m_dataHash.end())
        return iter->second;

    return nullptr;
}

SparseVolume.h

#ifndef VOLUME_H
#define VOLUME_H

// std includes
#include <unordered_map>

// Own includes
#include "Chunk.h"
#include "ChunkData.h"

typedef std::unordered_map<Chunk, std::shared_ptr<ChunkData>> ChunkDataHash;

class SparseVolume
{
public:
    SparseVolume(uint32_t chunkSideLength = 16);

    uint8_t chunkSideLengthPower() const;

    // Methods for one-off, random access retrieval
    Voxel voxelAt(int32_t xPos, int32_t yPos, int32_t zPos);
    Voxel voxelAt(const Vector3DInt &pos);

    // Methods for one-off, random access setting
    void setVoxelAt(int32_t xPos, int32_t yPos, int32_t zPos, Voxel voxel);
    void setVoxelAt(const Vector3DInt &pos, Voxel voxel);

    // Chunk management
    void loadChunk(const Chunk &chunk, std::shared_ptr<ChunkData> data);
    std::shared_ptr<ChunkData> unloadChunk(const Chunk &chunk);
    std::shared_ptr<ChunkData> chunkData(const Chunk &chunk);
    ChunkDataHash chunkDataAndNeighbors(const Chunk &chunk);

private:
    uint32_t m_chunkSideLength;
    uint8_t m_chunkSideLengthPower;

    ChunkDataHash m_dataHash;
    std::mutex m_mutex;

    std::shared_ptr<ChunkData> chunkDataUnsafe(const Chunk &chunk);
};

#endif // VOLUME_H

VolumeSampler.cpp

#include "VolumeSampler.h"

using namespace std;

VolumeSampler::VolumeSampler(SparseVolume &volume)
    : m_volume(volume)
    , m_xPosInVolume(0)
    , m_yPosInVolume(0)
    , m_zPosInVolume(0)
{
}

VolumeSampler::VolumeSampler(SparseVolume &volume, ChunkDataHash dataHash)
    : m_volume(volume)
    , m_dataHash(dataHash)
    , m_xPosInVolume(0)
    , m_yPosInVolume(0)
    , m_zPosInVolume(0)
{
}

VolumeSampler::~VolumeSampler()
{
    if (m_lastAccessedChunkData != nullptr)
        m_lastAccessedChunkData->dataMutex().unlock();
}

Vector3DInt VolumeSampler::position() const
{
    return Vector3DInt(m_xPosInVolume, m_yPosInVolume, m_zPosInVolume);
}

Voxel VolumeSampler::currentVoxel()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume, m_zPosInVolume);
}

void VolumeSampler::setPosition(int32_t xPos, int32_t yPos, int32_t zPos)
{
    m_xPosInVolume = xPos;
    m_yPosInVolume = yPos;
    m_zPosInVolume = zPos;
}

void VolumeSampler::setPosition(const Vector3DInt &pos)
{
    setPosition(pos.X(), pos.Y(), pos.Z());
}

void VolumeSampler::movePositiveX()
{
    m_xPosInVolume++;
}

void VolumeSampler::movePositiveY()
{
    m_yPosInVolume++;
}

void VolumeSampler::movePositiveZ()
{
    m_zPosInVolume++;
}

void VolumeSampler::moveNegativeX()
{
    --m_xPosInVolume;
}

void VolumeSampler::moveNegativeY()
{
    --m_yPosInVolume;
}

void VolumeSampler::moveNegativeZ()
{
    --m_zPosInVolume;
}

Voxel VolumeSampler::peekVoxel1nx1ny1nz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume - 1, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel1nx1ny0pz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume - 1, m_zPosInVolume);
}
Voxel VolumeSampler::peekVoxel1nx1ny1pz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume - 1, m_zPosInVolume + 1);
}

Voxel VolumeSampler::peekVoxel1nx0py1nz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel1nx0py0pz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume, m_zPosInVolume);
}

Voxel VolumeSampler::peekVoxel1nx0py1pz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume, m_zPosInVolume + 1);
}

Voxel VolumeSampler::peekVoxel1nx1py1nz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume + 1, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel1nx1py0pz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume + 1, m_zPosInVolume);
}

Voxel VolumeSampler::peekVoxel1nx1py1pz()
{
    return voxelAt(m_xPosInVolume - 1, m_yPosInVolume + 1, m_zPosInVolume + 1);
}

Voxel VolumeSampler::peekVoxel0px1ny1nz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume - 1, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel0px1ny0pz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume - 1, m_zPosInVolume);
}

Voxel VolumeSampler::peekVoxel0px1ny1pz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume - 1, m_zPosInVolume + 1);
}

Voxel VolumeSampler::peekVoxel0px0py1nz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel0px0py0pz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume, m_zPosInVolume);
}

Voxel VolumeSampler::peekVoxel0px0py1pz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume, m_zPosInVolume + 1);
}

Voxel VolumeSampler::peekVoxel0px1py1nz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume + 1, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel0px1py0pz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume + 1, m_zPosInVolume);
}

Voxel VolumeSampler::peekVoxel0px1py1pz()
{
    return voxelAt(m_xPosInVolume, m_yPosInVolume + 1, m_zPosInVolume + 1);
}

Voxel VolumeSampler::peekVoxel1px1ny1nz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume - 1, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel1px1ny0pz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume - 1, m_zPosInVolume);
}

Voxel VolumeSampler::peekVoxel1px1ny1pz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume - 1, m_zPosInVolume + 1);
}

Voxel VolumeSampler::peekVoxel1px0py1nz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel1px0py0pz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume, m_zPosInVolume);
}

Voxel VolumeSampler::peekVoxel1px0py1pz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume, m_zPosInVolume + 1);
}

Voxel VolumeSampler::peekVoxel1px1py1nz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume + 1, m_zPosInVolume - 1);
}

Voxel VolumeSampler::peekVoxel1px1py0pz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume + 1, m_zPosInVolume);
}

Voxel VolumeSampler::peekVoxel1px1py1pz()
{
    return voxelAt(m_xPosInVolume + 1, m_yPosInVolume + 1, m_zPosInVolume + 1);
}

shared_ptr<ChunkData> VolumeSampler::chunkDataAt(const Chunk &chunk)
{
    if (m_lastAccessedChunkData) {
        if (chunk == m_lastAccessedChunk)
            return m_lastAccessedChunkData;

        // Release chunk data mutex
        m_lastAccessedChunkData->dataMutex().unlock();
    }

    // Search local cache for chunk
    auto iter = m_dataHash.find(chunk);
    std::shared_ptr<ChunkData> data;

    // If we don't find it, request it from the volume
    if (iter == m_dataHash.end()) {
        data = m_volume.chunkData(chunk);
        m_dataHash[chunk] = data;
    } else {
        data = iter->second;
    }

    // If such a chunk exists, lock its mutex
    if (data != nullptr) {
        data->dataMutex().lock();
    }

    m_lastAccessedChunk = chunk;
    m_lastAccessedChunkData = data;

    return data;
}

Voxel VolumeSampler::voxelAt(int32_t xPos, int32_t yPos, int32_t zPos)
{
    uint8_t chunkSideLengthPower = m_volume.chunkSideLengthPower();
    const int32_t blockX = xPos >> chunkSideLengthPower;
    const int32_t blockZ = zPos >> chunkSideLengthPower;
    if (yPos < 0 || yPos > 127)
        return Voxel();

    const uint32_t xOffset = static_cast<uint32_t>(xPos - (blockX << chunkSideLengthPower));
    const uint32_t yOffset = static_cast<uint32_t>(yPos);
    const uint32_t zOffset = static_cast<uint32_t>(zPos - (blockZ << chunkSideLengthPower));


    auto chunkData = chunkDataAt(Chunk(blockX, blockZ));

    return (chunkData) ? chunkData->voxelAt(xOffset, yOffset, zOffset) : Voxel();
}

VolumeSampler.h

#ifndef VOLUMESAMPLER_H
#define VOLUMESAMPLER_H

#include "SparseVolume.h"

class VolumeSampler
{
public:
    VolumeSampler(SparseVolume &volume);
    VolumeSampler(SparseVolume &volume, ChunkDataHash dataHash);
    ~VolumeSampler();

    Vector3DInt position() const;
    Voxel currentVoxel();

    void setPosition(int32_t xPos, int32_t yPos, int32_t zPos);
    void setPosition(const Vector3DInt &pos);

    void movePositiveX();
    void movePositiveY();
    void movePositiveZ();

    void moveNegativeX();
    void moveNegativeY();
    void moveNegativeZ();

    Voxel peekVoxel1nx1ny1nz();
    Voxel peekVoxel1nx1ny0pz();
    Voxel peekVoxel1nx1ny1pz();
    Voxel peekVoxel1nx0py1nz();
    Voxel peekVoxel1nx0py0pz();
    Voxel peekVoxel1nx0py1pz();
    Voxel peekVoxel1nx1py1nz();
    Voxel peekVoxel1nx1py0pz();
    Voxel peekVoxel1nx1py1pz();

    Voxel peekVoxel0px1ny1nz();
    Voxel peekVoxel0px1ny0pz();
    Voxel peekVoxel0px1ny1pz();
    Voxel peekVoxel0px0py1nz();
    Voxel peekVoxel0px0py0pz();
    Voxel peekVoxel0px0py1pz();
    Voxel peekVoxel0px1py1nz();
    Voxel peekVoxel0px1py0pz();
    Voxel peekVoxel0px1py1pz();

    Voxel peekVoxel1px1ny1nz();
    Voxel peekVoxel1px1ny0pz();
    Voxel peekVoxel1px1ny1pz();
    Voxel peekVoxel1px0py1nz();
    Voxel peekVoxel1px0py0pz();
    Voxel peekVoxel1px0py1pz();
    Voxel peekVoxel1px1py1nz();
    Voxel peekVoxel1px1py0pz();
    Voxel peekVoxel1px1py1pz();

private:
    SparseVolume &m_volume;
    ChunkDataHash m_dataHash;
    Chunk m_lastAccessedChunk;
    std::shared_ptr<ChunkData> m_lastAccessedChunkData;

    //The current position in the volume
    int32_t m_xPosInVolume;
    int32_t m_yPosInVolume;
    int32_t m_zPosInVolume;

    std::shared_ptr<ChunkData> chunkDataAt(const Chunk &chunk);
    Voxel voxelAt(int32_t xPos, int32_t yPos, int32_t zPos);
};

#endif // VOLUMESAMPLER_H