source: trunk/src/gl/texture_atlas.cc @ 13

// Copyright (C) 2012-2013 ChaosForge / Kornel Kisielewicz
// http://chaosforge.org/
//
// This file is part of NV Libraries.
// For conditions of distribution and use, see copyright notice in nv.hh

#include "nv/gl/texture_atlas.hh"

#include "nv/logging.hh"

using namespace nv;

texture_atlas::texture_atlas( glm::ivec2 size, size_t depth )
        : image( size, depth ), m_used( 0 )
{
        m_nodes.push_back( glm::ivec3( 1, 1, m_size.x - 2 ) );
        fill( 0 );
}

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

    int best_height = INT_MAX;
    int best_index  = -1;
    int best_width  = INT_MAX;
        for( size_t i=0; i < m_nodes.size(); ++i )
        {
        int y = fit( i, size );
                if( y >= 0 )
                {
            glm::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 = i;
                                best_width = node.z;
                                r.pos.x = node.x;
                                r.pos.y = y;
                        }
        }
    }
   
        if( best_index == -1 )
    {
        return region( glm::ivec2( -1, -1 ), glm::ivec2( 0, 0 ) );
    }

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

    for( size_t i = best_index+1; i < m_nodes.size(); ++i )
    {
        glm::ivec3 node = m_nodes[ i ];
        glm::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() + i );
                --i;
            }
            else
            {
                break;
            }
        }
        else
        {
            break;
        }
    }
    merge();
    m_used += size.x * size.y;
    return r;
}

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

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

        int y     = node.y;
        int wleft = size.x;
        size_t i  = index;

        while( wleft > 0 )
        {
        node = m_nodes[ i ];
        if( node.y > y )
        {
            y = node.y;
        }
                if( (y + size.y) > (m_size.y-1) )
        {
                        return -1;
        }
                wleft -= node.z;
                ++i;
        }
        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()+i+1 );
                        --i;
                }
    }
}

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