source: trunk/src/gfx/texture_atlas.cc @ 520

// Copyright (C) 2012-2015 ChaosForge Ltd
// http://chaosforge.org/
//
// This file is part of Nova libraries. 
// For conditions of distribution and use, see copying.txt file in root folder.

#include "nv/gfx/texture_atlas.hh"

#include "nv/core/logging.hh"

using namespace nv;

texture_atlas::texture_atlas( ivec2 size, nv::size_t depth, nv::size_t border /*= 1*/ )
        : image( size, depth ), m_used( 0 ), m_border( border )
{
        m_nodes.push_back( ivec3( m_border, m_border, m_size.x - 2 * static_cast<int>( m_border ) ) );
        fill( 0 );
}

region texture_atlas::get_region( ivec2 size )
{
        region r ( ivec2(0,0), size );

        int best_height = nv::limits::si_max;
        int best_index  = -1;
        int best_width  = nv::limits::si_max;

        for( size_t i=0; i < m_nodes.size(); ++i )
        {
                int y = fit( i, size );
                if ( y >= 0 )
                {
                        ivec3 node = m_nodes[ i ];
                        if ( ( (y + size.y) < best_height ) ||
                                ( ((y + size.y) == best_height) && (node.z < best_width)) )
                        {
                                best_height = y + size.y;
                                best_index = static_cast<int>( i );
                                best_width = node.z;
                                r.pos.x = node.x;
                                r.pos.y = y;
                        }
                }
        }
   
        if ( best_index == -1 )
        {
                return region( ivec2( -1, -1 ), ivec2( 0, 0 ) );
        }

        m_nodes.insert( m_nodes.begin() + best_index, ivec3( r.pos.x, r.pos.y + size.y, size.x ) );

        for( size_t i = static_cast<size_t>( best_index )+1; i < m_nodes.size(); ++i )
        {
                ivec3 node = m_nodes[ i ];
                ivec3 prev = m_nodes[ i-1 ];

                if ( node.x < prev.x + prev.z )
                {
                        int shrink = prev.x + prev.z - node.x;
                        m_nodes[ i ].x += shrink;
                        m_nodes[ i ].z -= shrink;

                        if ( m_nodes[ i ].z <= 0 )
                        {
                                m_nodes.erase( m_nodes.begin() + static_cast<int>(i) );
                                --i;
                        }
                        else
                        {
                                break;
                        }
                }
                else
                {
                        break;
                }
        }
        merge();
        m_used += static_cast<uint32>(size.x * size.y);
        return r;
}

int texture_atlas::fit( nv::size_t index, ivec2 size )
{
        ivec3 node = m_nodes[ index ];

        if ( node.x + size.x > m_size.x - static_cast<int>( m_border ) ) 
        {
                return -1;
        }

        int y     = node.y;
        int wleft = size.x;

        while ( wleft > 0 )
        {
                node = m_nodes[ index ];
                if ( node.y > y )
                {
                        y = node.y;
                }
                if ( y + size.y > m_size.y - static_cast<int>( m_border ) )
                {
                        return -1;
                }
                wleft -= node.z;
                ++index;
        }
        return y;
}

void texture_atlas::merge()
{
        for ( size_t i=0; i < m_nodes.size()-1; ++i )
    {
                if ( m_nodes[ i ].y == m_nodes[ i+1 ].y )
                {
                        m_nodes[ i ].z += m_nodes[ i+1 ].z;
            m_nodes.erase( m_nodes.begin()+static_cast<int>(i+1) );
                        --i;
                }
    }
}

void texture_atlas::clear()
{
        m_nodes.clear();
        m_used = 0;
        m_nodes.push_back( ivec3( 1, 1, m_size.x - 2 ) );
        fill( 0 );
}