// Gray - A simple ray tracing program
// Copyright (C) 2008-2018 Eric Bechet
//
// See the COPYING file for contributions and license information.
// Please report all bugs and problems to <bechet@cadxfem.org>.
//

#include "BVTree.h"
#include "scene.h"

BVTree::BVTree ( Gscene* scene )
{
  std::list<BVNode*> nodes;
  Gscene::iteratorModel it_models = scene->beginModel();

  for ( ; it_models != scene->endModel(); ++it_models )
  {
    BoundingBox* box = new BoundingBox ( *it_models );
    nodes.push_back ( new BVNode ( box ) );
  }

  std::list<BVNode*> parentNodes;

  while ( nodes.size() > 1 )
  {
    parentNodes.clear();

    std::list<BVNode*>::iterator it_nodes = nodes.begin();

    for ( ; it_nodes != nodes.end(); it_nodes = nodes.begin() )
    {

      // Noeud courant
      BVNode* node = *it_nodes;
      Point box_center = ( node->getBVNodeInfo() )->getBBoxCenter();

      // Dernier noeud
      if ( it_nodes == --nodes.end() )
      {
        parentNodes.push_back ( node );
        break;
      }
      else
      {
        // Supprimer le noeud courant de la liste
        nodes.erase ( it_nodes );

        // On va trouver le noeud le plus proche
        std::list<BVNode*>::iterator it2_nodes = nodes.begin();
        std::list<BVNode*>::iterator del = nodes.begin();
        // Prendre le suivant pour commencer les tests
        Point box2_center = ( ( *it2_nodes )->getBVNodeInfo() )->getBBoxCenter();
        double dist = sqrt ( ( ( box_center.X - box2_center.X ) * ( box_center.X - box2_center.X ) )
                             + ( ( box_center.Y - box2_center.Y ) * ( box_center.Y - box2_center.Y ) )
                             + ( ( box_center.Z - box2_center.Z ) * ( box_center.Z - box2_center.Z ) ) );

        ++it2_nodes;

        for ( ; it2_nodes != nodes.end(); ++it2_nodes )
        {
          box2_center = ( ( *it2_nodes )->getBVNodeInfo() )->getBBoxCenter();
          double dist_tmp = sqrt ( ( ( box_center.X - box2_center.X ) * ( box_center.X - box2_center.X ) )
                                   + ( ( box_center.Y - box2_center.Y ) * ( box_center.Y - box2_center.Y ) )
                                   + ( ( box_center.Z - box2_center.Z ) * ( box_center.Z - box2_center.Z ) ) );

          if ( dist_tmp < dist )
          {
            del = it2_nodes;
            dist = dist_tmp;
          }
        }

        // Supprimer le second élément de la liste
        BVNode* node2 = *del;
        BVNode* parentNode = new BVNode ( new BoundingBox ( node->getBVNodeInfo(),
                                          node2->getBVNodeInfo() ) );
        parentNode->setBVNodeLeft ( node );
        parentNode->setBVNodeRight ( node2 );
        parentNodes.push_back ( parentNode );

        nodes.erase ( del );
      }
    }

    nodes = parentNodes;
    // Niveau suivant
  }

  if ( !nodes.empty() )
  {
    root = nodes.front();
  }
  else
  {
    root = NULL;
  }
}

BVTree::~BVTree()
{
  freeBVTree ( root );
}

void BVTree::intersectionBBox ( BVNode* node, Ray* ray, std::vector<Gmodel*>* intersectModels )
{
  if ( node == NULL )
  {
    return;
  }

  if ( node->isBVNodeLeaf() )
  {
    Gmodel* model = node->getBVNodeInfo()->getModel();
    intersectModels->push_back ( model );
  }
  else
  {
    if ( node->getBVNodeInfo()->intersect ( ray ) )
    {
      intersectionBBox ( node->getBVNodeLeft(), ray, intersectModels );
      intersectionBBox ( node->getBVNodeRight(), ray, intersectModels );
    }
  }
}

void BVTree::freeBVTree ( BVNode* node )
{
  if ( node == NULL )
  {
    return;
  }

  if ( node->isBVNodeLeaf() )
  {
    delete ( node->getBVNodeInfo() );
    delete ( node );
  }
  else
  {
    freeBVTree ( node->getBVNodeLeft() );
    freeBVTree ( node->getBVNodeRight() );
    delete ( node );
  }
}
// kate: indent-mode cstyle; indent-width 2; replace-tabs on;