/* $Id: HFLod.cpp,v 1.1 2002/08/28 22:44:52 mrq Exp $
**
** Ark - Libraries, Tools & Programs for MMORPG developpements.
** Copyright (C) 1999-2000 The Contributors of the Ark Project
** Please see the file "AUTHORS" for a list of contributors
**
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

// for std::min and std::max
#include <algorithm>

#include <iostream>
#include <sstream>

#include <math.h>

#include <Ark/ArkConfig.h>
#include <Ark/ArkRenderer.h>
#include <Modules/HeightField/HFLod.h>
#include <Modules/HeightField/HFWorld.h>

namespace Ark
{

   // Allocate a new "size*size" height field
    HeightFieldLod::HeightFieldLod (HeightField* hf) : 
	HeightFieldRender (hf),
	m_LodData (0)
   {
   }


   // Destroy the given Height-field.
   HeightFieldLod::~HeightFieldLod ()
   {
       // delete 0 is legal and should do nothing
       delete[] m_LodData;
       
   }


   bool
   HeightFieldLod::Load(const String &path)
   {
      const size_t minSize = std::min(m_Heightfield->m_SizeX, m_Heightfield->m_SizeZ);
      const double minDouble = static_cast< double >( minSize );
      const double minLog2 = log( minDouble ) / log( 2.0 );

      m_Depth = static_cast< size_t >( minLog2 );
      std::cerr << "Depth is " << m_Depth << std::endl;
      m_Size = (1 << m_Depth) + 1;
      std::cerr << "Size is " << m_Size << std::endl;

      m_Points = m_Size * m_Size;
      std::cerr << "Vertices is " << m_Points << std::endl;

      // Allocate vertices data
      m_LodData = new VertexLodData[ m_Points ];

      // Fill the data
      const int center[2] = { m_Size >> 1, m_Size >> 1 };
      const int northWest[2] = { 0, 0 };
      const int northEast[2] = { m_Size - 1, 0 };
      const int southEast[2] = { m_Size - 1, m_Size - 1 };
      const int southWest[2] = { 0, m_Size - 1 };

      {
	  size_t index;

	  // North West corner
	  index = 0;
	  m_LodData[ index ].set( 0.f, 0.f );

	  // North East corner
	  index = m_Size - 1;
	  m_LodData[ index ].set( 0.f, 0.f );

	  // South East corner
	  index = m_Points - 1;
	  m_LodData[ index ].set( 0.f, 0.f );

	  // South West corner
	  index = m_Points - m_Size;
	  m_LodData[ index ].set( 0.f, 0.f );
      }

      bool* processed = new bool[m_Points];

      const size_t d = m_Depth + 1;
      FillVertexLodData(processed, center, northEast, northWest, d);
      FillVertexLodData(processed, center, northWest, southWest, d);
      FillVertexLodData(processed, center, southWest, southEast, d);
      FillVertexLodData(processed, center, southEast, northEast, d);

      delete[] processed;
      return true;
   }

   // ======
   // Write the hf to a file
   // ======
   bool
   HeightFieldLod::Write (const String& path)
   {
      assert (!"todo Write for LOD");
      
      return false;
   }

   size_t
   HeightFieldLod::FillVertexLodData(
	   bool* processed,
	   const int* top,
	   const int* left,
	   const int* right,
	   size_t depth
	   )
   {
       const int middle[2] = {
	   (left[0] + right[0]) >> 1,
	   (left[1] + right[1]) >> 1
       };
	   
       const size_t index = middle[0] + m_Size * middle[1];
       
       // already processed ?
       if (! processed[index] )
       {

	   processed[ index ] = true;

	   // Reference inside data
	   VertexLodData& ref = m_LodData[ index ];

	   // Set error and radius to zero, will be increased later
	   ref.m_Error = 0.f;
	   ref.m_Radius = 0.f;
	   // The error, is the max of the error for the 4 (or 2) children
	   // The radius is the max of ( children radius + distance to child )
	   //   in our case, children are equidistant, distance to child is 
	   //   added later.

	   // If not a leaf, recurse to get child error and radius
	   if ( 0 < depth )
	   {
	       size_t childIndex;
	       
	       // Recurse on the left side (inside, no test)
	       childIndex = FillVertexLodData(processed, middle, top, left, depth-1);
	       ref.m_Error = std::max(ref.m_Error, m_LodData[childIndex].m_Error);
	       ref.m_Radius = std::max(ref.m_Radius, m_LodData[childIndex].m_Radius);
		   
	       // Recurse on the right side (inside, no test)
	       childIndex = FillVertexLodData(processed, middle, right, top, depth-1);
	       ref.m_Error = std::max(ref.m_Error, m_LodData[childIndex].m_Error);
	       ref.m_Radius = std::max(ref.m_Radius, m_LodData[childIndex].m_Radius);
		   
	       // Coordinates for outside tests
	       const int bottom[2] = 
	       {
		   left[0] + right[0] - top[0],
		   left[1] + right[1] - top[1]
	       };
		   
	       // Test whether or not bottom is inside
	       if ( (0 <= bottom[0]) && (bottom[0] < (int)m_Size)
		       && (0 <= bottom[1]) && (bottom[1] < (int)m_Size) )
	       {
		   // Recurse on the left outside
		   childIndex = FillVertexLodData(processed, middle, left, bottom, depth-1);
		   ref.m_Error = std::max(ref.m_Error, m_LodData[childIndex].m_Error);
		   ref.m_Radius = std::max(ref.m_Radius, m_LodData[childIndex].m_Radius);
		   
		   // Recurse on the right outside
		   childIndex = FillVertexLodData(processed, middle, bottom, right, depth-1);
		   ref.m_Error = std::max(ref.m_Error, m_LodData[childIndex].m_Error);
		   ref.m_Radius = std::max(ref.m_Radius, m_LodData[childIndex].m_Radius);
	       }
	       

	       // compute radius for current vertex
	       const int dx = top[0] - middle[0];
	       const int dz = top[1] - middle[1];
	       const scalar distance2 = static_cast< scalar >( dx*dx + dz*dz ) / 2.f;
	
	       ref.m_Radius += sqrtf( distance2 );
	   }

	   // TODO get data from VertexBuffer XXX
	   // Now we've got inherited error and radius from children
	   //   Compute intrinsic error, and add it to m_Error
	   //const size_t leftIndex = left[0] + m_Size * left[1];
	   //const size_t rightIndex = right[0] + m_Size * right[1];

	   // TODO get data from VertexBuffer XXX
	   // Linear interpolation, could be bilinear (later)
	   //const scalar nonRefined = ( m_LodData[leftIndex].m_Y + m_LodData[rightIndex].m_Y ) / 2.f;

	   // TODO get data from VertexBuffer XXX
	   // Take the bigger error
	   //const scalar localError = fabsf( nonRefined - ref.m_Y );
	   //ref.m_Error = std::max(ref.m_Error, localError);
       }

       // returns current index for computations
       return index;
   }

   void
   HeightFieldLod::Render (Renderer &renderer, const Camera& camera)
   {
   }

}