TerrainStorage.hpp

Go to the documentation of this file.

//
//  CeresEngine - A game development framework
//
//  Created by Rogiel Sulzbach.
//  Copyright (c) 2018-2023 Rogiel Sulzbach. All rights reserved.
//
 
#pragma once
 
#include "CeresEngine/DataTypes.hpp"
#include "CeresEngine/Macros.hpp"
 
#include "CeresEngine/Foundation/Generator.hpp"
#include "CeresEngine/Foundation/Iterator.hpp"
#include "CeresEngine/Foundation/Logging.hpp"
#include "CeresEngine/Foundation/OffsetPtr.hpp"
#include "CeresEngine/Foundation/SharedMemory.hpp"
#include "CeresEngine/Foundation/Container/DynamicBitSet.hpp"
 
#include "CeresEngine/Math/Geometry.hpp"
 
namespace CeresEngine {
 
    template<typename T> class MemoryMappedTerrainOctree {
        template<typename U> using Ptr = OffsetPtr<U, std::ptrdiff_t, Int32>;
 
        struct Node {
            T value;
            Ptr<Node> children[8] = {
                this, this, this, this, //
                this, this, this, this, //
            };
        };
 
        struct FreeNode {
            Ptr<FreeNode> next;
            explicit FreeNode(const Ptr<FreeNode>& next) : next(next) {}
        };
 
        struct Header {
            uint32_t version = 0;
 
            Ptr<Node> root = nullptr;
            Ptr<FreeNode> freeList = nullptr;
 
            AABox aabb{Vector3(-7000 * 1000), Vector3(7000 * 1000)};
            float maximumResolution = 10;
 
            size_t capacity = 0;
            uint8_t reserved[8 * 16];
        };
 
        SharedMemory mSharedMemory;
        Header* mHeader;
 
    public:
        explicit MemoryMappedTerrainOctree(const FilePath& path) : mSharedMemory(path, SharedMemory::AccessMode::Write) {
            if(mSharedMemory.empty()) {
                mSharedMemory.resize(sizeof(Header));
                mHeader = new(mSharedMemory.data()) Header();
                mHeader->root = allocateNode();
            } else {
                mHeader = reinterpret_cast<Header*>(mSharedMemory.data());
            }
        }
 
        ~MemoryMappedTerrainOctree() { mSharedMemory.sync(); }
 
    public:
        void reserve(size_t newCapacity) {
            if(mHeader->capacity >= newCapacity) {
                return;
            }
 
            const size_t newSize = sizeof(Node) * newCapacity + sizeof(Header);
            mSharedMemory.resize(newSize);
 
            mHeader = reinterpret_cast<Header*>(mSharedMemory.data());
 
            const size_t oldCapacity = mHeader->capacity;
            mHeader->capacity = newCapacity;
 
            for(const size_t nodeIndex : range(oldCapacity, newCapacity)) {
                FreeNode* const nodeMemory = reinterpret_cast<FreeNode*>(nodeAt(nodeIndex));
                mHeader->freeList = new(nodeMemory) FreeNode(mHeader->freeList);
            }
        }
 
        bool insert(Vector3 position, T value) {
            insert(mHeader->root.get(), position, T(value), mHeader->aabb, mHeader->aabb.getSize().x);
            return true;
        }
 
        bool insert(const AABox& area, T value) {}
 
        bool insert(const Sphere& sphere, T value) {
            insert(mHeader->root.get(), sphere, T(value), mHeader->aabb, mHeader->aabb.getSize().x);
            return true;
        }
 
        Node* allocateNode() {
            if(!mHeader->freeList) {
                reserve(mHeader->capacity * 2 + 1);
            }
 
            CE_ASSERT(mHeader->freeList != nullptr);
 
            FreeNode* const freeNode = mHeader->freeList.get();
            mHeader->freeList = freeNode->next;
 
            freeNode->~FreeNode();
            return new(freeNode) Node();
        }
 
    private:
        void insert(Node* node, Vector3 position, T&& value, AABox aabb, double resolution) {
            info("resolution = {}", resolution);
            if(resolution <= mHeader->maximumResolution) {
                node->value = value;
                return;
            }
 
            const size_t octant = getOctantFor(position, aabb);
            subdivide(node, octant);
 
            aabb.minimum = aabb.getCenter() + aabb.getHalfSize() * octantDelta(octant) / 2.0;
            aabb.maximum = aabb.getCenter() - aabb.getHalfSize() * octantDelta(octant) / 2.0;
            return insert(node->children[octant].get(), position, std::forward<T>(value), aabb, resolution / 2.0);
        }
 
        template<typename Primitive> void insert(Node* node, const Primitive& primitive, const T& value, const AABox& aabb, double resolution) {
            // If the AABB is fully contained inside the primitive or we have
            // reached our maximum resolution, stop recursion and write the
            // value to the node.
            //
            if(primitive.contains(aabb) || resolution <= mHeader->maximumResolution) {
                node->value = value;
                return;
            }
 
            // Else, we might be partially contained, so we iterate over the
            // 8 octants and find which ones we overlap with.
            //
            const Vector3 center = aabb.getCenter();
            const Vector3 halfSize = aabb.getHalfSize();
            for(const size_t octant : range(0, 8)) {
                AABox octantAABB = aabb;
                {
                    const Vector3 size = halfSize;
                    octantAABB.minimum = center + halfSize / 2.0 * octantDelta(octant) - size / 2.0;
                    octantAABB.maximum = octantAABB.minimum + size;
                }
 
                if(!octantAABB.intersects(primitive)) {
                    continue;
                }
 
                subdivide(node, octant);
                insert(node->children[octant].get(), primitive, value, octantAABB, resolution / 2.0);
            }
        }
 
        void subdivide(Node* node) {
            for(const size_t childIndex : range(0, 8)) {
                if(node->children[childIndex] != node) {
                    continue;
                }
 
                node->children[childIndex] = allocateNode();
                node->children[childIndex]->value = node->value;
            }
        }
 
        void subdivide(Node* node, size_t octant) {
            if(node->children[octant] != node) {
                return;
            }
 
            node->children[octant] = allocateNode();
            node->children[octant]->value = node->value;
        }
 
        bool shouldCollapse(Node* const node, const T& firstValue) {
            // if any of the nodes has a different value, we cannot collapse
            // this.
            //
            for(const Ptr<Node>& child : node->children) {
                if(child == nullptr || child == node) {
                    return false;
                }
 
                if(child->value == firstValue) {
                    continue;
                }
            }
            return true;
        }
 
        Node* findOrCreateNode(Node* node, Vector2 position, T value, const UInt64 depth, const UInt64 maxDepth) {
            if(depth == maxDepth) {
                return node;
            }
        }
 
        void* nodeAt(size_t index) {
            Node* const firstNode = reinterpret_cast<Node*>(mHeader + 1);
            return firstNode + index;
        }
 
        static size_t getOctantFor(const Vector3& position, const AABox& aabb) {
            const Vector3 center = aabb.getCenter();
            return (position.x > center.x ? 0 : (1 << 0)) + //
                (position.y > center.y ? 0 : (1 << 1)) + //
                (position.z > center.z ? 0 : (1 << 2));
        }
 
        static Vector3 octantDelta(const size_t octant) {
            return Vector3( //
                (octant & (1 << 0)) ? -1.0 : 1.0, //
                (octant & (1 << 1)) ? -1.0 : 1.0, //
                (octant & (1 << 2)) ? -1.0 : 1.0);
        }
    };
 
} // namespace CeresEngine