octree.h

Go to the documentation of this file.

#pragma once
#include "triangle.h"
#include "box.h"
#include "vector.h"
#include <iostream>
#include <memory>
 
namespace GOAT
{
    namespace raytracing
    {
 
        template <class T> class Octree
        {
        public:
            bool isLeaf; 
            Octree()
            {
                /*parent = 0;
                child = 0;*/
                nChilds = 0;
    //          Element = 0;
                nElements = 0;
                isLeaf = false;
                MAX_RECURSIONS = 3;
            }
 
            Octree(const Octree& O);
 
            ~Octree()
            {
                delElements();
            }
            void delElements();
            void trimOctree();     
            void trimOctree(int rek);
            void createTree(int maxRecursions = 1, int rek = 0); 
            void createChilds(); 
            void delChild(int i); 
            void delAllChilds(); 
            void setBoundingBox(maths::Vector<double> MP, maths::Vector<double> d);
            void setRecursiondepth(int max_recursions);
            Octree<T>* parent;
 
            std::vector<std::unique_ptr<Octree<T>>> child;
            std::vector<T> Element;
            size_t nElements, nChilds;
            int MAX_RECURSIONS;
            Box BBox;
        };
 
        template <class T> Octree<T>::Octree(const Octree& O)
        {
            if (O.parent)
                parent = O.parent;
            else
                parent = nullptr;
            nChilds = O.nChilds;
            for (const auto& ptr : O.child)
                child.push_back(std::make_unique<Octree<T>>(*ptr));
 
            Element = O.Element;
            nElements = Element.size();
            
            MAX_RECURSIONS = O.MAX_RECURSIONS;
            BBox = O.BBox;
            isLeaf = O.isLeaf;
        }
 
        template <class T> void Octree<T>::delElements()
        {
            if (nElements > 0)
                Element.clear();
            nElements = 0;
        }
 
 
        template <class T> void Octree<T>::trimOctree()
        {
            int rek = 0;
            this->trimOctree(rek);
        }
 
        template <class T> void Octree<T>::trimOctree(int rek)
        {
            int hnChilds = nChilds;
            bool valid[8] = { true,true,true,true,true,true, true,true };
            for (size_t i = 0; i < child.size(); i++)
            {
                
                    if (child[i]->isLeaf && child[i]->Element.empty())
                    {
                    
                        child[i].reset();
                        valid[i] = false;
                        nChilds--;
                    }
                
                else
                    child[i]->trimOctree(rek + 1);
            }
 
            if (hnChilds < nChilds) // Kinder wurden gel�scht ==> umsortieren notwendig
            {
                std::vector<std::unique_ptr<Octree<T> > > hChild;
                int i = 0;
                for (int j = 0; j < hnChilds; j++)
                {
                    if (valid[j])
                    {
                        hChild.push_back(std::move(child[j]));
                        i++;
                    }
                }
 
                child = std::move(hChild);
                nChilds = child.size();
            }
        }
 
 
        template <class T> void Octree<T>::delAllChilds()
        {
            child.clear();
            nChilds = 0;
        }
 
        template <class T> void Octree<T>::delChild(int i)
        {
            child[i]->delAllChilds();
        }
 
        template <class T> void Octree<T>::createChilds()
        {
            int sx, sy, sz;
            maths::Vector<double> P, d;
            child.clear();
            for (int i = 0; i < 8; i++)
            {
                
                auto newChild = std::make_unique<Octree<T>>();
                newChild->parent = this;
 
                switch (i)
                {
                case 0: sx = -1; sy = -1; sz = -1; break;
                case 1: sx = +1; sy = -1; sz = -1; break;
                case 2: sx = -1; sy = +1; sz = -1; break;
                case 3: sx = +1; sy = +1; sz = -1; break;
                case 4: sx = -1; sy = -1; sz = +1; break;
                case 5: sx = +1; sy = -1; sz = +1; break;
                case 6: sx = -1; sy = +1; sz = +1; break;
                case 7: sx = +1; sy = +1; sz = +1; break;
                }
                P = BBox.P + maths::Vector<double>(sx * BBox.d[0] / 4.0, sy * BBox.d[1] / 4.0, sz * BBox.d[2] / 4.0);
                d = BBox.d / 2.0;
                newChild->BBox = Box(P, d, BBox.n);
 
                child.push_back(std::move(newChild));
 
            }
            nChilds = 8;
        }
 
 
 
        template <class T> void Octree<T>::createTree(int maxRecursions, int rek)
        {
            MAX_RECURSIONS = maxRecursions;
            if (rek < MAX_RECURSIONS)
            {
                createChilds();
                for (int i = 0; i < 8; i++) child[i]->createTree(maxRecursions, rek + 1);
            }
            else
            {
                nChilds = 0;
                isLeaf = true;
            }
        }
 
        template <class T> void Octree<T>::setBoundingBox(maths::Vector<double> MP, maths::Vector<double> d)
        {
            BBox = Box(MP, d, 1.0);
        }
 
        template <class T> void Octree<T>:: setRecursiondepth(int max_recursions)
        {           
            // delete the whole tree...
            delAllChilds();
            delElements();
 
            // ... and recreate it with the new number of
            // createTree(max_recursions);
        }
 
 
 
        bool checkTriangleBoxIntersection(Box B, triangle D);
 
 
        void addTriangleToTriangle(Octree<triangle>* O, triangle D, int rek);
        void addTriangleToTriangle(Octree<triangle>& O, triangle D);
        double rayOctreeIntersection(Octree<triangle>& T, maths::Vector<double> P, maths::Vector<double> k, triangle& D);
        void writeTriangleOctree(char* Fname, Octree<triangle>&);
        std::ostream& operator<< (std::ostream& os, Octree<triangle>&);
    }
}