//
//  Filename         : Grid.h
//  Author(s)        : Stephane Grabli
//  Purpose          : Base class to define a cell grid surrounding
//                     the bounding box of the scene
//  Date of creation : 30/07/2002
//
///////////////////////////////////////////////////////////////////////////////


//
//  Copyright (C) : Please refer to the COPYRIGHT file distributed 
//   with this source distribution. 
//
//  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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
///////////////////////////////////////////////////////////////////////////////

#ifndef  GRID_H
# define GRID_H

# include <float.h>
# include <vector>
# include "../system/FreestyleConfig.h"
# include "GeomUtils.h"
# include "Geom.h"
# include "Polygon.h"

using namespace std;
using namespace Geometry;

typedef vector<Polygon3r*>	OccludersSet;


//
// Class to define cells used by the regular grid
//
///////////////////////////////////////////////////////////////////////////////

class LIB_GEOMETRY_EXPORT Cell
{
 public:
  
  Cell(Vec3r& orig) {
    _orig = orig;
  }

  virtual ~Cell() {}

  inline void addOccluder(Polygon3r* o) {
    if (o)
      _occluders.push_back(o);
  }

  inline const Vec3r& getOrigin() {
    return _orig;
  }

  inline OccludersSet& getOccluders() {
    return _occluders;
  }
  
 private:

  Vec3r		_orig;
  OccludersSet	_occluders;
};


class GridVisitor{
public:
	virtual ~GridVisitor() {}; //soc
    virtual void discoverCell(Cell *cell) {}
    virtual void examineOccluder(Polygon3r *occ) {}
    virtual void finishCell(Cell *cell) {}
    virtual bool stop() {return false;}
};

/*! Gathers all the occluders belonging to the cells
 * traversed by the ray */
class allOccludersGridVisitor : public GridVisitor{
public:
    allOccludersGridVisitor(OccludersSet& occluders)
        :GridVisitor(), occluders_(occluders){}
    virtual void examineOccluder(Polygon3r *occ);

    OccludersSet& occluders() {return occluders_;}
    void clear() {occluders_.clear();}

private:
    OccludersSet& occluders_;
};

/*! Finds the first intersection and breaks. The occluder and 
 * the intersection information are stored and accessible.
 */
class firstIntersectionGridVisitor : public GridVisitor {

//soc - changed order to remove warnings
public:
    double u_, v_, t_;
private:
    Polygon3r *occluder_;
	Vec3r ray_org_, ray_dir_, cell_size_;
    Cell * current_cell_;

public:
      firstIntersectionGridVisitor(const Vec3r& ray_org, const Vec3r& ray_dir, const Vec3r& cell_size) : 
		 GridVisitor(), u_(0),v_(0),t_(DBL_MAX),
		 occluder_(0),
		 ray_org_(ray_org), ray_dir_(ray_dir), cell_size_(cell_size),
      	 current_cell_(0) {}
      virtual ~firstIntersectionGridVisitor() {}

    virtual void discoverCell(Cell *cell) {current_cell_=cell;}
    virtual void examineOccluder(Polygon3r *occ);
    virtual bool stop();

    Polygon3r * occluder() {return occluder_;}
};

//
// Class to define a regular grid used for ray casting computations
//
///////////////////////////////////////////////////////////////////////////////

class LIB_GEOMETRY_EXPORT Grid
{
public:

  /*! Builds a Grid 
   *  Must be followed by a call to configure()
   */
  Grid() {}

  virtual ~Grid() {
    clear();
  }

  /*! clears the grid
   *  Deletes all the cells, clears the hashtable,
   *  resets size, size of cell, number of cells.
   */
  virtual void clear();

  /*! Sets the different parameters of the grid
   *    orig
   *      The grid origin
   *    size
   *      The grid's dimensions
   *    nb
   *      The number of cells of the grid
   */
  virtual void configure(const Vec3r& orig, const Vec3r& size, unsigned nb);
  
  /*! returns a vector of integer containing the
   *  coordinates of the cell containing the point
   *  passed as argument
   *    p
   *      The point for which we're looking the cell
   */
  inline void getCellCoordinates(const Vec3r& p, Vec3u& res) {
    int tmp;
    for (int i = 0; i < 3; i++) {
      tmp = (int)((p[i] - _orig[i]) / _cell_size[i]);
      if (tmp < 0)
	res[i] = 0;
      else if ((unsigned)tmp >= _cells_nb[i])
	res[i] = _cells_nb[i] - 1;
      else
	res[i] = tmp;
    }
  }

  /*! Fills the case corresponding to coord with the cell */
  virtual void fillCell(const Vec3u& coord, Cell& cell) = 0;

  /*! returns the cell whose coordinates
   *  are pased as argument
   */
  virtual Cell* getCell(const Vec3u& coord) = 0;

  /*! returns the cell containing the point
   *  passed as argument. If the cell is empty
   *  (contains no occluder), NULL is returned
   *    p
   *      The point for which we're looking the cell
   */
  inline Cell* getCell(const Vec3r& p) {    
    Vec3u coord;
    getCellCoordinates(p, coord);
    return getCell(coord);
  }

  /*! Retrieves the x,y,z coordinates of the origin of the cell whose coordinates (i,j,k)
   *  is passed as argument
   *    cell_coord
   *      i,j,k integer coordinates for the cell
   *    orig
   *      x,y,x vector to be filled in with the cell origin's coordinates
   */
  inline void getCellOrigin(const Vec3u& cell_coord, Vec3r& orig) {
    for (unsigned i = 0; i < 3; i++)
      orig[i] = _orig[i] + cell_coord[i] * _cell_size[i];
  }

  /*! Retrieves the box corresponding to the cell whose coordinates
   *  are passed as argument.
   *    cell_coord
   *      i,j,k integer coordinates for the cell
   *    min_out
   *      The min x,y,x vector of the box. Filled in by the method.
   *    max_out
   *      The max x,y,z coordinates of the box. Filled in by the method.
   */
  inline void getCellBox(const Vec3u& cell_coord, Vec3r& min_out, Vec3r& max_out) {
    getCellOrigin(cell_coord, min_out);
    max_out = min_out + _cell_size;
  }

  /*! inserts a convex polygon occluder
   *  This method is quite coarse insofar as it
   *  adds all cells intersecting the polygon bounding box
   *    convex_poly
   *      The list of 3D points constituing a convex polygon
   */
  void insertOccluder(Polygon3r * convex_poly);

  /*! Adds an occluder to the list of occluders */
  void addOccluder(Polygon3r* occluder) {
    _occluders.push_back(occluder);
  }

  /*! Casts a ray between a starting point and an ending point
   *  Returns the list of occluders contained
   *  in the cells intersected by this ray
   *  Starts with a call to InitRay.
   */
  void castRay(const Vec3r& orig,
	       const Vec3r& end,
	       OccludersSet& occluders,
	       unsigned timestamp);

  /*! Casts an infinite ray (still finishing at the end of the grid) from a starting point and in a given direction.
   *  Returns the list of occluders contained
   *  in the cells intersected by this ray
   *  Starts with a call to InitRay.
   */
  void castInfiniteRay(const Vec3r& orig,
		       const Vec3r& dir,
		       OccludersSet& occluders,
		       unsigned timestamp);

  /*! Casts an infinite ray (still finishing at the end of the grid) from a starting point and in a given direction.
  *  Returns the first intersection (occluder,t,u,v) or null.
  *  Starts with a call to InitRay.
  */
  Polygon3r * castRayToFindFirstIntersection(const Vec3r& orig,
      const Vec3r& dir,
      double& t,
      double& u,
      double& v,
      unsigned timestamp);


  /*! Init all structures and values for computing
   *  the cells intersected by this new ray
   */
  void initRay (const Vec3r &orig,
		const Vec3r& end,
		unsigned timestamp);

  /*! Init all structures and values for computing
   *  the cells intersected by this infinite ray.
   * Returns false if the ray doesn't intersect the 
   * grid.
   */
  bool initInfiniteRay (const Vec3r &orig,
		const Vec3r& dir,
		unsigned timestamp);

 
  /*! Accessors */
  inline const Vec3r& getOrigin() const {
    return _orig;
  }
  inline Vec3r gridSize() const {
    return _size;
  }
  inline Vec3r getCellSize() const {
    return _cell_size;
  }

  void displayDebug() {
    cerr << "Cells nb     : " << _cells_nb << endl;
    cerr << "Cell size    : " << _cell_size << endl;
    cerr << "Origin       : " << _orig << endl;
    cerr << "Occluders nb : " << _occluders.size() << endl;
  }

 protected:

  /*! Core of castRay and castInfiniteRay, find occluders
   *  along the given ray
   */
  inline void castRayInternal(GridVisitor& visitor) {
    Cell* current_cell = NULL;
    do {
      current_cell = getCell(_current_cell);
      if (current_cell){
          visitor.discoverCell(current_cell);
          OccludersSet& occluders = current_cell->getOccluders(); // FIXME: I had forgotten the ref &
          for (OccludersSet::iterator it = occluders.begin();
              it != occluders.end();
              it++) {
                  if ((unsigned)(*it)->userdata2 != _timestamp) {
                      (*it)->userdata2 = (void*)_timestamp;
                      visitor.examineOccluder(*it);
                  }
              }
          visitor.finishCell(current_cell);
      }
    } while ((!visitor.stop()) && (nextRayCell(_current_cell, _current_cell)));
  }

 
  /*! returns the  cell next to the cell
   *  passed as argument.
   */
  bool nextRayCell(Vec3u& current_cell, Vec3u& next_cell);

  unsigned	_timestamp;

  Vec3u		_cells_nb;  // number of cells for x,y,z axis
  Vec3r		_cell_size; // cell x,y,z dimensions
  Vec3r		_size;      // grid x,y,x dimensions
  Vec3r		_orig;      // grid origin

  Vec3r		_ray_dir;      // direction vector for the ray
  Vec3u		_current_cell; // The current cell being processed (designated by its 3 coordinates)
  Vec3r		_pt;           // Points corresponding to the incoming and outgoing intersections
                               // of one cell with the ray
  real		_t_end;        // To know when we are at the end of the ray
  real		_t;

  //OccludersSet _ray_occluders; // Set storing the occluders contained in the cells traversed by a ray
  OccludersSet _occluders;     // List of all occluders inserted in the grid
};

#endif // GRID_H