Volumetric B-tree

#include <iostream>
#include <fstream>
#include<algorithm>
#include <vector>
#include <memory>
#include <bitset>
#include <map>

struct Point {
    float x;
    float y;
    float z;

    bool operator>=(const Point& other) const
    {
        return x >= other.x && y >= other.y && z >= other.z;
    }
};

struct BoundingBox {
    BoundingBox(bool isZero = true, const Point& low = { INFINITY ,INFINITY ,INFINITY }, const Point& high = { -INFINITY ,-INFINITY ,-INFINITY })
        : m_isZero(isZero)
        , m_Low(low)
        , m_High(high)
    {}

    BoundingBox& operator+=(const BoundingBox& other)
    {
        m_Low.x = std::min(m_Low.x, other.m_Low.x);
        m_Low.y = std::min(m_Low.y, other.m_Low.y);
        m_Low.z = std::min(m_Low.z, other.m_Low.z);

        m_High.x = std::max(m_High.x, other.m_High.x);
        m_High.y = std::max(m_High.y, other.m_High.y);
        m_High.z = std::max(m_High.z, other.m_High.z);

        m_isZero = m_isZero && other.m_isZero;

        return *this;
    }

    BoundingBox& operator^=(const BoundingBox& other)
    {
        if (m_High >= other.m_Low && other.m_High >= m_Low)
        {
            m_Low.x = std::max(m_Low.x, other.m_Low.x);
            m_Low.y = std::max(m_Low.y, other.m_Low.y);
            m_Low.z = std::max(m_Low.z, other.m_Low.z);

            m_High.x = std::min(m_High.x, other.m_High.x);
            m_High.y = std::min(m_High.y, other.m_High.y);
            m_High.z = std::min(m_High.z, other.m_High.z);

            m_isZero = m_isZero || other.m_isZero;
        }
        else
        {
            m_isZero = true;
            m_Low = { INFINITY ,INFINITY ,INFINITY };
            m_High = { -INFINITY ,-INFINITY ,-INFINITY };
        }
        return *this;
    }

    float size() const
    {
        return m_isZero? 0 : (m_High.x - m_Low.x) * (m_High.y - m_Low.y) * (m_High.z - m_Low.z);
    }

    bool m_isZero;
    Point m_Low;
    Point m_High;
};

enum class BoundedObjectType {
    BoundingBox = 0,
    BBTree,
    Polygon
};

class BoundedObject {
public:
    BoundedObject(BoundedObjectType type = BoundedObjectType::BoundingBox)
                : m_type(type)
    {}

    virtual ~BoundedObject() {}

    virtual const BoundingBox& GetBound() = 0;

    BoundedObjectType GetType()
    {
        return m_type;
    }

private:
    BoundedObjectType m_type;
};

class Polygon : public BoundedObject
{
public:
    Polygon(std::vector<Point>& inputPoints)
        :BoundedObject(BoundedObjectType::Polygon)
    {
        points = inputPoints;
        for (auto& point : points)
        {
            box += BoundingBox(false, point, point);
        }
    }
    virtual ~Polygon() {}

    virtual const BoundingBox& GetBound() { return box; };
private:
    BoundingBox box;
    std::vector<Point> points;
};

template <typename T=BoundedObject, int k=10>
class BBTree : public BoundedObject
{
public:
    BBTree()
        :m_IsLeafLevel(true)
        , m_Parent(nullptr)
    {
        m_Objects.reserve(k);
    }
    virtual ~BBTree() {}

    virtual const BoundingBox& GetBound() { return m_TotalBounds; };

    void add(std::shared_ptr<BoundedObject> object)
    {
        auto& objBound = object->GetBound();
        m_TotalBounds += objBound;

        //if it's a leaf, insert straight away
        if (m_IsLeafLevel)
        {
            m_Objects.push_back(object);
        }
        else
        {
            int foundIdx = 0;
            float minAdditionalVolume = INFINITY;
            for (int idx = 0 ; idx<m_Objects.size() ; ++idx)
            {
                BoundingBox cpyBound = m_Objects[idx]->GetBound();
                float cpyVolume = cpyBound.size();
                cpyBound += objBound;
                cpyVolume = cpyBound.size() - cpyVolume;
                if (cpyVolume < minAdditionalVolume)
                {
                    foundIdx = idx;
                    minAdditionalVolume = cpyVolume;
                }
            }
            ((BBTree<T, k>*) m_Objects[foundIdx].get())->add(object);
        }
        //if it's not a leaf, find which child node will accept the current object with minimal additional volume and insert it there

        // if the size isn't k, there's no need to split the current object
        if (m_Objects.size() < k)
        {
            return;
        }

        // find the best split of the objects in the current tree node (this alogirhm may not be that good as it's O(k^3)
        float minimalIntersection = INFINITY;
        std::bitset<k> minimalSplit;

        for (int i = 0; i < k; ++i)
        {
            BoundingBox currentBox = m_Objects[i]->GetBound();
            std::bitset<k> takenElems;
            takenElems[i] = true;
            for (int filledElements = 1; filledElements < k / 2; ++filledElements)
            {
                int minElem = -1;
                BoundingBox minElemBox;
                for (int j = 0; j < k; ++j)
                {
                    if (takenElems[j]) continue;
                    if (minElem == -1)
                    {
                        minElem = j;
                        minElemBox = m_Objects[j]->GetBound();
                        minElemBox += currentBox;
                    }
                    else
                    {
                        BoundingBox testBox = m_Objects[j]->GetBound();
                        testBox += currentBox;
                        if (testBox.size() < minElemBox.size())
                        {
                            minElem = j;
                            minElemBox = testBox;
                        }
                    }
                }
                //if (minElem == -1) continue; should never happen
                takenElems[minElem] = true;
                currentBox = minElemBox;
            }
            BoundingBox otherBox;
            for (int j = 0; j < k; ++j)
            {
                if (takenElems[j]) continue;
                otherBox += m_Objects[j]->GetBound();
            }
            currentBox ^= otherBox;
            if (currentBox.size() < minimalIntersection)
            {
                minimalIntersection = currentBox.size();
                minimalSplit = takenElems;
            }
        }

        std::vector<std::shared_ptr<BoundedObject>> ltObjects; ltObjects.reserve(k);
        std::shared_ptr<BoundedObject> rtObject(new BBTree<T, k>());
        std::vector<std::shared_ptr<BoundedObject>>& rtObjects = ((BBTree<T, k>*)rtObject.get())->m_Objects;
        ((BBTree<T, k>*)rtObject.get())->m_IsLeafLevel = m_IsLeafLevel;
        ((BBTree<T, k>*)rtObject.get())->m_Parent = m_Parent;

        //insert objects that are true in minimalSplit to ltObjects and false to the rtObjects (they also get assigned their parent if needed)
        for (int i = 0; i < k; ++i)
        {
            if (minimalSplit[i])
            {
                ltObjects.push_back(m_Objects[i]);
            }
            else
            {
                rtObjects.push_back(m_Objects[i]);
                ((BBTree<T, k>*)rtObject.get())->m_TotalBounds += m_Objects[i]->GetBound();
                if (!m_IsLeafLevel)
                {
                    ((BBTree<T, k>*)m_Objects[i].get())->m_Parent = ((BBTree<T, k>*)rtObject.get());
                }
            }
        }


        // is the root -> current object stays and children are made from the split of the current object
        if (!m_Parent)
        {
            std::shared_ptr<BoundedObject> ltObject(new BBTree<T, k>());
            ((BBTree<T, k>*)ltObject.get())->m_IsLeafLevel = m_IsLeafLevel;

            for (auto& object : ltObjects)
            {
                ((BBTree<T, k>*)ltObject.get())->m_TotalBounds += object->GetBound();
                if (!m_IsLeafLevel) ((BBTree<T, k>*)object.get())->m_Parent = (BBTree<T, k>*)ltObject.get();
            }

            std::swap(((BBTree<T, k>*)ltObject.get())->m_Objects, ltObjects);

            // add objects and change their parent
            ((BBTree<T, k>*)rtObject.get())->m_Parent = this;
            ((BBTree<T, k>*)ltObject.get())->m_Parent = this;
            m_Objects.clear();
            m_Objects.push_back(ltObject);
            m_Objects.push_back(rtObject);
            m_IsLeafLevel = false;
        }
        else
        {
            std::swap(m_Objects, ltObjects);
            m_TotalBounds = BoundingBox();
            for (auto& object : m_Objects)
            {
                m_TotalBounds += object->GetBound();
            }
            m_Parent->m_Objects.push_back(rtObject);
        }
        // is not the root -> current object is split and the leftover objects are moved to a new child to the parent of this object
    }

    void FillVolume(std::map<int, float>& totalVolumes, int level = 1)
    {
        for (auto& object : m_Objects)
        {
            totalVolumes[level] += object->GetBound().size();
            if (!m_IsLeafLevel) ((BBTree<T, k>*)object.get())->FillVolume(totalVolumes, level + 1);
        }
    }

private:
    std::vector<std::shared_ptr<BoundedObject>> m_Objects;
    BBTree<T, k>* m_Parent;
    bool m_IsLeafLevel;
    BoundingBox m_TotalBounds;
};

int main() {
    std::vector<Point> vertices;
    std::ifstream file("teapot.obj");
    std::string c;

    BBTree<Polygon, 10> tree;

    file >> c;
    while (file) {
        if (c == "v")
        {
            float x;
            float y;
            float z;
            file >> x >> y >> z;
            vertices.push_back({ x, y, z });
        }
        else if (c == "vt")
        {
            while (file && file.peek() != '\n')
            {
                char s;
                s = file.get();
            }
        }
        else if (c == "f")
        {
            std::vector<Point> polygon;
            std::string value;
            while (file && file.peek() != '\n')
            {
                char s;
                s = file.get();
                switch (s) {
                case '\t':
                case ' ':
                    value.clear();
                    break;
                case '/':
                {
                    int idx = std::atoi(value.c_str())-1;
                    polygon.push_back(vertices[idx]);
                    value.clear();
                }
                    break;
                default:
                    value += s;
                }
            }
            tree.add(std::shared_ptr<BoundedObject>(new Polygon(polygon)));
        }
        else
        {
            while (file && file.peek() != '\n')
            {
                char s;
                s = file.get();
            }
        }
        file >> c;
    }
    std::map<int, float> levelVolume;
    tree.FillVolume(levelVolume);
    std::cout << "level : totalVolume" << std::endl;
    std::cout << "0 : " << tree.GetBound().size() << std::endl;
    for (auto& levelAndVolume : levelVolume)
    {
        std::cout << levelAndVolume.first << " : " << levelAndVolume.second << std::endl;
    }

    return 0;
}