QuadTree.cpp

Go to the documentation of this file.

#include "Application.hpp"

QuadTree::QuadTree(Application* app, uvec2 const & size, uint const maxDistance)
    : m_maxDistance(maxDistance)
    , m_app(app)
{
    resize(size);

    if (m_app->getConfig().pickerMultiThreaded())
        cout << "Picker-Mode: multi-threaded" << endl;
    else
        cout << "Picker-Mode: single-threaded" << endl;
}
void QuadTree::resize(uvec2 const & size)
{
    if (m_data.size() == size) return;

    m_data.resize(size);

    if (size == uvec2(0,0))
        m_levels.clear();
    else
        m_levels.resize((uint)glm::max(glm::ceil(glm::log2((float)size.x)), 
                                       glm::ceil(glm::log2((float)size.y)) ));
    m_levels.shrink_to_fit();

    uint level = 0;
    for (uvec2 levelSize(1,1); levelSize.x < size.x || levelSize.y < size.y ; levelSize *= 2)
    {
        m_levels[level].resize(levelSize);

        level ++;
    }
}
bool QuadTree::findNear(uvec2 const & pos_, OUT id_t & foundId, OUT uvec2 & foundPos, OUT float & foundDistance)
{
    auto pos = pos_;

    if (m_data.size() == uvec2(0,0)) 
        return false;

    if (false)
    {
        if (m_data.at(pos) == 0)
            return false;
    
        foundId = m_data.at(pos);
        foundPos = pos;
        return true;
    }

    if (!m_levels[0].at(0,0)) return false;

    list<uvec2> candidates;
    candidates.push_back(uvec2(0,0));


    for (auto levelIdx = 1U; levelIdx < m_levels.size() ; levelIdx ++)
    {
        auto& level = m_levels[levelIdx];
        auto posOnLevel = pos / (2U << (m_levels.size() - levelIdx - 1));
        auto maxDistanceOnLevel = m_maxDistance / (2U << (m_levels.size() - levelIdx - 1));
        auto nCandidates = candidates.size();
        
        for (auto& candidate : candidates)
        {
            candidate *= 2U;
            candidates.push_front(candidate + uvec2(1,0));
            candidates.push_front(candidate + uvec2(0,1));
            candidates.push_front(candidate + uvec2(1,1));
        }
                        
        // remove empty candidates
        candidates.remove_if([&level]
                             (uvec2 const & candidate)
                             {
                                 return !level.at(candidate);
                             });
        
        // declare distance-function
        auto distances = [&posOnLevel]
                         (uvec2 const & candidate, float* deltas)
                         {
                             deltas[0] = glm::length(vec2(candidate) - vec2(posOnLevel) - vec2(-0.5f,-0.5f));
                             deltas[1] = glm::length(vec2(candidate) - vec2(posOnLevel) - vec2( 0.5f,-0.5f));
                             deltas[2] = glm::length(vec2(candidate) - vec2(posOnLevel) - vec2(-0.5f, 0.5f));
                             deltas[3] = glm::length(vec2(candidate) - vec2(posOnLevel) - vec2( 0.5f, 0.5f));
                         }; 
        auto minDistance = [distances]
                           (uvec2 const & candidate)
                           {
                               float deltas[4];
                               distances(candidate, deltas);
                               return (float)(*min_element(deltas, deltas + 4));
                           };
        auto maxDistance = [distances]
                           (uvec2 const & candidate)
                           {
                               float deltas[4];
                               distances(candidate, deltas);
                               return (float)(*max_element(deltas, deltas + 4));
                           };


        // compute min-distance
        float minimum_of_maxDistance = (float)(maxDistanceOnLevel+1);
        for(auto& candidate : candidates)
            minimum_of_maxDistance = glm::min(minimum_of_maxDistance, 
                                              maxDistance(candidate));
                
        // remove candidates further away than min-distance
        candidates.remove_if([minDistance, minimum_of_maxDistance]
                             (uvec2 const & candidate)
                             {
                                 return minDistance(candidate) > (minimum_of_maxDistance);
                             });
    }
    
    auto nCandidates = candidates.size();
    for (auto& candidate : candidates)
    {
        candidate *= 2U;
        candidates.push_front(candidate + uvec2(1,0));
        candidates.push_front(candidate + uvec2(0,1));
        candidates.push_front(candidate + uvec2(1,1));
    }
                        
    // remove empty candidates
    candidates.remove_if([this]
                         (uvec2 const & candidate)
                         {
                             return m_data.at(candidate) == 0;
                         });

    if (candidates.empty()) 
        return false;

    // declare distance-function
    auto distance = [pos]
                    (uvec2 const & candidate)
                    {
                        return glm::length(vec2(candidate)-vec2(pos));
                    };

    foundPos = *min_element(candidates.begin(), candidates.end(), [distance]
                                                                  (uvec2 const & a, uvec2 const & b)
                                                                  {
                                                                      return distance(a) < distance(b);
                                                                  });

    foundDistance = distance(foundPos);
    if (foundDistance > m_maxDistance)
        return false;

    foundId = m_data.at(foundPos);
    return true;
}

void QuadTree::maxDistance(uint const distance)
{
    m_maxDistance = distance;
}
uint const QuadTree::maxDistance() const
{
    return m_maxDistance;
}

    
void QuadTree::updateLayersBaseCell(uint const layer, uint const x, uint const y)
{   
    auto baseLevel = m_levels.rbegin();

    auto const layerDiff = m_levels.size() - layer;
    auto layerExpansion = 2 << (layerDiff-1);

    updateLayerArea(&m_data, baseLevel, x * layerExpansion, y * layerExpansion, layerExpansion);
    
    // create other layers
    for (auto level = m_levels.rbegin() + 1; level != m_levels.rend(); level ++)
    {
        auto lastLevel = level - 1;
                
        layerExpansion /= 2;

        updateLayerArea(lastLevel, level, x * layerExpansion, y * layerExpansion, layerExpansion);

        if (layerExpansion == 1)
            break;
    }

}

void QuadTree::updateLayersParallel()
{
    auto& tasks = m_app->getTasks();
    
    tasks.schedule([this](){ updateLayersBaseCell(1, 0, 0); }, &(m_updateLayersParallelMutex[0]));
    tasks.schedule([this](){ updateLayersBaseCell(1, 1, 0); }, &(m_updateLayersParallelMutex[1]));
    tasks.schedule([this](){ updateLayersBaseCell(1, 0, 1); }, &(m_updateLayersParallelMutex[2]));
    tasks.schedule([this](){ updateLayersBaseCell(1, 1, 1); }, &(m_updateLayersParallelMutex[3]));

    for (auto& handle : m_updateLayersParallelMutex)
        handle.wait();

    updateLayerCell(&(m_levels[1]), &(m_levels[0]), 0, 0);
}
void QuadTree::updateLayersSerial()
{
    updateLayersBaseCell(0, 0, 0);
}