QuadTree.hpp

Go to the documentation of this file.

#pragma once

#include "HUD.hpp"

class QuadTree
{
    template<typename T>
    class Level
    {
        uvec2       m_size;             
        vector<T>   m_data;             
        T           m_borderValue;      
        public:
            Level(uvec2 const & size = uvec2(0,0), T const & borderValue = (T)0)
                : m_data(size.x*size.y, 0)
                , m_size(size)
                , m_borderValue(borderValue)
            { }

            T& at(uvec2 const & pos)
            {
                if (pos.x < 0 || pos.x >= m_size.x ||
                    pos.y < 0 || pos.y >= m_size.y)
                {
                    return m_borderValue;
                }
                    
                return m_data[m_size.x * pos.y + pos.x];
            } 

            T& at(uint const x, uint const y)
            {
                return at(vec2(x,y));
            } 
            T* data()
            {
                return m_data.data();
            }   
            void clear()
            {
                m_data.assign(m_size.x*m_size.y, 0);
            } 
            void resize(uvec2 const & size)
            {
                if (m_size == size) return;

                m_size = size;

                auto realSize = size.x*size.y;

                if (realSize == 0)
                    m_data.clear();
                else
                {
                    m_data.resize(realSize);
                    m_data.assign(realSize, 0);
                }
                m_data.shrink_to_fit();
            }   
            uvec2 const & size() const
            {
                return m_size;
            }   

    };

    typedef Level<id_t> DataLevel;
    typedef Level<BOOLEAN> MidLevel;


    Application*                    m_app;                          
    DataLevel                       m_data;                         
    vector<MidLevel>                m_levels;                       
    uint                            m_maxDistance;                  
    array<auto_reset_event, 4>      m_updateLayersParallelMutex;    
    public:
        QuadTree(Application* app, uvec2 const & size, uint const maxDistance);
        
        void resize(uvec2 const & size);

        template<typename tFnc>
        void fill(tFnc readIds)
        {
            if (m_data.size() == uvec2(0,0)) 
                return;
    
            // copy data
            readIds(m_data.data());
    
            if (m_levels.empty())
                return;

            if (m_app->getConfig().pickerMultiThreaded() && (m_levels.size() > 5))
                updateLayersParallel();
            else
                updateLayersSerial();
        }

        bool findNear(uvec2 const & pos, OUT id_t & foundId, OUT uvec2 & foundPos, OUT float & foundDistance);
        
        void maxDistance(uint const distance);
        uint const maxDistance() const;


    private:
        void updateLayersParallel();
        void updateLayersSerial();

        void updateLayersBaseCell(uint const layer, uint const x, uint const y);

        template<typename TBaseLayer, typename TCurrentLayer>
        void updateLayerArea(TBaseLayer base, TCurrentLayer current, uint const offset_x, uint const offset_y, uint size)
        {
            for (uint y = 0; y < min(offset_y+size,current->size().y); y++)
                for (uint x = 0; x < min(offset_x+size,current->size().x); x++)
                    updateLayerCell(base, current, x, y);
        }
        
        template<typename TBaseLayer, typename TCurrentLayer>
        void updateLayerCell(TBaseLayer base, TCurrentLayer current, uint const x, uint const y)
        {
            current->at(x,y) = base->at(x*2+0, y*2+0)
                            || base->at(x*2+1, y*2+0)
                            || base->at(x*2+0, y*2+1)
                            || base->at(x*2+1, y*2+1);
        }
};