synchronized_detail_octree.h

#pragma once

#ifndef SYNCHRONIZED_TEXTURE_HEAP_DETAIL_OCTREE_H
#define SYNCHRONIZED_TEXTURE_HEAP_DETAIL_OCTREE_H




#include "vector.h"

#include <memory>




namespace Synchronized {


namespace detail {




/*==============================================================================
    Octree class
==============================================================================*/


struct Octree {

    inline Octree( unsigned int const height = 0 );


    inline unsigned int const Height() const;


    inline Vector< size_t, 3 > Fill( unsigned int const logSize );


    inline unsigned int const CountLeaves() const;

    template< typename t_Iterator >    // points to std::pair< Vector< unsigned int, 3 >, unsigned int >, which is a coordinate,logSize pair
    inline void Leaves( t_Iterator const& destination ) const;


    // logSize is the height at which to insert the node
    void Insert( Vector< unsigned int, 3 > const& coordinates, unsigned int const logSize );

    // logSize is the height from which to erase the node. return value is the coordinates from which it was erased. throws on failure
    Vector< unsigned int, 3 > const Erase( unsigned int const logSize );


private:

    struct Node {

        inline Node();
        inline Node( unsigned int const splits );


        unsigned int const CountLeaves() const;

        template< typename t_Iterator >
        void Leaves(
            t_Iterator& destination,
            Vector< unsigned int, 3 >& coordinates,
            unsigned int const height
        ) const;


        bool const FindInsert(    // returns true if this node was previously not filled, but now is
            Vector< unsigned int, 3 > const& coordinates,
            unsigned int const logSize,
            unsigned int const height
        );

        bool const Insert(    // returns true if this node was previously not filled, but now is
            Vector< unsigned int, 3 > const& coordinates,
            unsigned int const logSize,
            unsigned int const height
        );


        bool const Erase(
            Vector< unsigned int, 3 >& coordinates,
            std::unique_ptr< Node >& owner,
            unsigned int const logSize,
            unsigned int const height
        );


    private:

        std::unique_ptr< Node > m_children[ 8 ];
    };


    std::unique_ptr< Node > m_root;
    unsigned int m_height;
};




/*==============================================================================
    Octree methods
==============================================================================*/


Octree::Octree( unsigned int const height ) : m_height( height ) {
}


unsigned int const Octree::Height() const {

    return m_height;
}


Vector< size_t, 3 > Octree::Fill( unsigned int const logSize ) {

    Vector< unsigned int, 3 > logSizes;
    logSizes[ 2 ] = logSize / 3;
    logSizes[ 1 ] = ( logSize - logSizes[ 2 ] ) / 2;
    logSizes[ 0 ] = logSize - logSizes[ 1 ] - logSizes[ 2 ];
    assert( ( logSizes[ 0 ] >= logSizes[ 1 ] ) && ( logSizes[ 1 ] >= logSizes[ 2 ] ) );
    assert( logSizes[ 2 ] + 1 >= logSizes[ 0 ] );

    unsigned int splits = 0;
    if ( logSizes[ 1 ] < logSizes[ 0 ] )
        ++splits;
    if ( logSizes[ 2 ] < logSizes[ 0 ] )
        ++splits;

    m_root.reset( new Node( splits ) );
    m_height = logSizes[ 0 ];

    Vector< size_t, 3 > size = { { 1, 1, 1 } };
    size <<= logSizes;
    return size;
}


unsigned int const Octree::CountLeaves() const {

    unsigned int result = 0;
    if ( m_root )
        result = m_root->CountLeaves();
    return result;
}


template< typename t_Iterator >
void Octree::Leaves( t_Iterator const& destination ) const {

    if ( m_root ) {

        t_Iterator destinationCopy = destination;
        Vector< unsigned int, 3 > coordinates = { { 0, 0, 0 } };
        m_root->Leaves( destinationCopy, coordinates, m_height );
    }
}




/*==============================================================================
    Octree::Node methods
==============================================================================*/


Octree::Node::Node() {
}


Octree::Node::Node( unsigned int const splits ) {

    assert( ( splits >= 0 ) && ( splits < 3 ) );

    if ( splits > 0 ) {

        unsigned int const children = ( 1u << ( 3 - splits ) );
        for ( unsigned int ii = 0; ii < children; ++ii )
            m_children[ ii ].reset( new Node );
    }
}


template< typename t_Iterator >
void Octree::Node::Leaves( t_Iterator& destination, Vector< unsigned int, 3 >& coordinates, unsigned int const height ) const {

    unsigned int children = 0;

    for ( unsigned int ii = 0; ii < 8; ++ii ) {

        if ( m_children[ ii ] ) {

            coordinates &= ~( ( 1u << height ) - 1 );
            if ( ii & 1 )
                coordinates[ 0 ] |= ( 1u << ( height - 1 ) );
            if ( ii & 2 )
                coordinates[ 1 ] |= ( 1u << ( height - 1 ) );
            if ( ii & 4 )
                coordinates[ 2 ] |= ( 1u << ( height - 1 ) );

            m_children[ ii ]->Leaves( destination, coordinates, height - 1 );
            ++children;
        }
    }

    if ( children == 0 ) {

        *destination = std::pair< Vector< unsigned int, 3 >, unsigned int >( coordinates, height );
        ++destination;
    }
}




}    // namespace detail


}    // namespace Synchronized




#endif    // SYNCHRONIZED_TEXTURE_HEAP_DETAIL_OCTREE_H