synchronized_detail_octree.cpp

#include "synchronized_detail_octree.h"
#include "exception.h"

#include <assert.h>




namespace Synchronized {


namespace detail {




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


void Octree::Insert( Vector< unsigned int, 3 > const& coordinates, unsigned int const logSize ) {

    assert( logSize <= m_height );

    assert( ( coordinates[ 0 ] & ( ( 1u << logSize ) - 1 ) ) == 0 );
    assert( ( coordinates[ 1 ] & ( ( 1u << logSize ) - 1 ) ) == 0 );
    assert( ( coordinates[ 2 ] & ( ( 1u << logSize ) - 1 ) ) == 0 );

    assert( ( coordinates[ 0 ] & ~( ( 1u << m_height ) - 1 ) ) == 0 );
    assert( ( coordinates[ 1 ] & ~( ( 1u << m_height ) - 1 ) ) == 0 );
    assert( ( coordinates[ 2 ] & ~( ( 1u << m_height ) - 1 ) ) == 0 );

    if ( m_root )
        m_root->FindInsert( coordinates, logSize, m_height );
    else {

        m_root.reset( new Node );
        m_root->Insert( coordinates, logSize, m_height );
    }
}


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

    Vector< unsigned int, 3 > coordinates = { { 0, 0, 0 } };
    bool success = false;
    if ( m_root && ( logSize <= m_height ) )
        success = m_root->Erase( coordinates, m_root, logSize, m_height );

    if ( ! success )
        THROW_EXCEPTION( "out of texture heap space!" );

    return coordinates;
}




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


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

    unsigned int result = 0;
    for ( unsigned int ii = 0; ii < 8; ++ii )
        if ( m_children[ ii ] )
            result += m_children[ ii ]->CountLeaves();

    // if no children, then this is a leaf
    if ( result == 0 )
        ++result;

    return result;
}


bool const Octree::Node::FindInsert(
    Vector< unsigned int, 3 > const& coordinates,
    unsigned int const logSize,
    unsigned int const height
)
{
    bool result = false;

    assert( logSize <= height );
    unsigned int children = 0;
    for ( unsigned int ii = 0; ii < 8; ++ii )
        if ( m_children[ ii ] )
            ++children;

    if ( children > 0 ) {

        if ( logSize == height ) {

            for ( unsigned int ii = 0; ii < 8; ++ii )
                if ( m_children[ ii ] )
                    m_children[ ii ].reset();

            result = true;
        }
        else if ( logSize < height ) {

            unsigned int index = 0;
            if ( coordinates[ 0 ] & ( 1u << ( height - 1 ) ) )
                index += 1;
            if ( coordinates[ 1 ] & ( 1u << ( height - 1 ) ) )
                index += 2;
            if ( coordinates[ 2 ] & ( 1u << ( height - 1 ) ) )
                index += 4;

            bool filled = false;
            if ( ! m_children[ index ] ) {

                m_children[ index ].reset( new Node );
                filled = m_children[ index ]->Insert( coordinates, logSize, height - 1 );
                ++children;
            }
            else
                filled = m_children[ index ]->FindInsert( coordinates, logSize, height - 1 );

            if ( filled && ( children == 8 ) ) {

                bool grandchildren = false;
                for ( unsigned int ii = 0; ( ! grandchildren ) && ( ii < 8 ); ++ii )
                    if ( ii != index )
                        for ( unsigned int jj = 0; ( ! grandchildren ) && ( jj < 8 ); ++jj )
                            grandchildren |= static_cast< bool >( m_children[ ii ]->m_children[ jj ] );

                if ( ! grandchildren ) {

                    for ( unsigned int ii = 0; ii < 8; ++ii )
                        m_children[ ii ].reset();

                    result = true;
                }
            }
        }
    }

    return result;
}


bool const Octree::Node::Insert(
    Vector< unsigned int, 3 > const& coordinates,
    unsigned int const logSize,
    unsigned int const height
)
{
    bool result = true;

    assert( logSize <= height );
    if ( logSize < height ) {

        unsigned int index = 0;
        if ( coordinates[ 0 ] & ( 1u << ( height - 1 ) ) )
            index += 1;
        if ( coordinates[ 1 ] & ( 1u << ( height - 1 ) ) )
            index += 2;
        if ( coordinates[ 2 ] & ( 1u << ( height - 1 ) ) )
            index += 4;

        assert( ! m_children[ index ] );
        m_children[ index ].reset( new Node );
        m_children[ index ]->Insert( coordinates, logSize, height - 1 );

        result = false;
    }

    return result;
}


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

    assert( logSize <= height );
    unsigned int children = 0;
    for ( unsigned int ii = 0; ii < 8; ++ii )
        if ( m_children[ ii ] )
            ++children;

    if ( logSize == height ) {

        if ( children == 0 ) {

            owner.reset();
            result = true;
        }
    }
    else if ( logSize < height ) {

        if ( children == 0 ) {

            if ( logSize + 1 == height ) {

                for ( unsigned int ii = 1; ii < 8; ++ii )
                    m_children[ ii ].reset( new Node );
            }
            else {

                for ( unsigned int ii = 0; ii < 8; ++ii )
                    m_children[ ii ].reset( new Node );

                result = m_children[ 0 ]->Erase( coordinates, m_children[ 0 ], logSize, height - 1 );
                assert( result );
            }

            result = true;
        }
        else {

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

                if ( m_children[ ii ] ) {

                    if ( m_children[ ii ]->Erase( coordinates, m_children[ ii ], logSize, height - 1 ) ) {

                        if ( ! m_children[ ii ] )
                            --children;

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

                        result = true;
                        break;
                    }
                }
            }

            if ( children == 0 )
                owner.reset();
        }
    }

    return result;
}




}    // namespace detail


}    // namespace Synchronized