text: //=========== (C) Copyright 1999 Valve, L.L.C. All rights reserved. ===========
  //
  // The copyright to the contents herein is the property of Valve, L.L.C.
  // The contents may be used and/or copied only with the written permission of
  // Valve, L.L.C., or in accordance with the terms and conditions stipulated in
  // the agreement/contract under which the contents have been supplied.
  //
  // Purpose: 
  //
  // $Workfile:     $
  // $Date:         $
  // $NoKeywords: $
  //=============================================================================
  
  #include "vrad.h"
  #include "imagepacker.h"
  
  
  bool CImagePacker::Reset( int maxLightmapWidth, int maxLightmapHeight )
  {
  	int i;
  	
  	Assert( maxLightmapWidth <= MAX_MAX_LIGHTMAP_WIDTH );
  	
  	m_MaxLightmapWidth = maxLightmapWidth;
  	m_MaxLightmapHeight = maxLightmapHeight;
  	
  	m_MaxBlockWidth = maxLightmapWidth + 1;
  	m_MaxBlockHeight = maxLightmapHeight + 1;
  
  	m_AreaUsed = 0;
  	m_MinimumHeight = -1;
  	for( i = 0; i < m_MaxLightmapWidth; i++ )
      {
  		m_pLightmapWavefront[i] = -1;
      }
  	return true;
  }
  
  
  inline int CImagePacker::GetMaxYIndex( int firstX, int width )
  {
  	int maxY = -1;
  	int maxYIndex = 0;
  	for( int x = firstX; x < firstX + width; ++x )
  	{
  		// NOTE: Want the equals here since we'll never be able to fit
  		// in between the multiple instances of maxY
  		if( m_pLightmapWavefront[x] >= maxY )
  		{
  			maxY = m_pLightmapWavefront[x];
  			maxYIndex = x;
  		}
  	}
  	return maxYIndex;
  }
  
  
  bool CImagePacker::AddBlock( int width, int height, int *returnX, int *returnY )
  {
  	// If we've already determined that a block this big couldn't fit
  	// then blow off checking again...
  	if ( ( width >= m_MaxBlockWidth ) && ( height >= m_MaxBlockHeight ) )
  		return false;
  
  	int bestX = -1;	
  	int maxYIdx;
  	int outerX = 0;
  	int outerMinY = m_MaxLightmapHeight;
  	int lastX = m_MaxLightmapWidth - width;
  	int lastMaxYVal = -2;
  	while (outerX <= lastX)
  	{
  		// Skip all tiles that have the last Y value, these
  		// aren't going to change our min Y value
  		if (m_pLightmapWavefront[outerX] == lastMaxYVal)
  		{
  			++outerX;
  			continue;
  		}
  
  		maxYIdx = GetMaxYIndex( outerX, width );
  		lastMaxYVal = m_pLightmapWavefront[maxYIdx];
  		if (outerMinY > lastMaxYVal)
  		{
  			outerMinY = lastMaxYVal;
  			bestX = outerX;
  		}
  		outerX = maxYIdx + 1;
  	}
  	
  	if( bestX == -1 )
  	{
  		// If we failed to add it, remember the block size that failed
  		// *only if both dimensions are smaller*!!
  		// Just because a 1x10 block failed, doesn't mean a 10x1 block will fail
  		if ( ( width <= m_MaxBlockWidth ) && ( height <= m_MaxBlockHeight )	)
  		{
  			m_MaxBlockWidth = width;
  			m_MaxBlockHeight = height;
  		}
  
  		return false;
  	}
  	
  	// Set the return positions for the block.
  	*returnX = bestX;
  	*returnY = outerMinY + 1;
  	
  	// Check if it actually fit height-wise.
  	// hack
  	//  if( *returnY + height > maxLightmapHeight )
  	if( *returnY + height >= m_MaxLightmapHeight - 1 )
  	{
  		if ( ( width <= m_MaxBlockWidth ) && ( height <= m_MaxBlockHeight )	)
  		{
  			m_MaxBlockWidth = width;
  			m_MaxBlockHeight = height;
  		}
  
  		return false;
  	}
  						   
  	// It fit!
  	// Keep up with the smallest possible size for the image so far.
  	if( *returnY + height > m_MinimumHeight )
  		m_MinimumHeight = *returnY + height;
  	
  	// Update the wavefront info.
  	int x;
  	for( x = bestX; x < bestX + width; x++ )
      {
  		m_pLightmapWavefront[x] = outerMinY + height;
      }
  	
  	//  AddBlockToLightmapImage( *returnX, *returnY, width, height );
  	m_AreaUsed += width * height;
  
  	return true;
  }
  
  