//=============================================================================
//
// Glagen : a planet sized landscape generator
// Copyright (C) 2002  Julien Guertault, Hugues Hiegel, Meng-Tih Lam
//
// 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.
//
//=============================================================================
//
// Glagen : GPL LAndscape GENerator
//
// triangle.cc for Glagen : made by Zavie (Julien Guertault)
//
// www.glagen.org
//
//=============================================================================

#include	<cmath>
#include	<cstdlib>
#include	"data_glagen.hh"
#include	"dot.hh"
#include	"misc.hh"
#include	"triangle.hh"
#include	"vector.hh"

// ================================================= Constructor and destructor

Triangle :: Triangle (Dot	*a,
		      Dot	*b,
		      Dot	*c,
		      Triangle	*father):
  _a(a), _b(b), _c(c),
  _neighbor_ab(NULL), _neighbor_bc(NULL), _neighbor_ca(NULL),
  _father(father),
  _child_a(NULL), _child_b(NULL), _child_c(NULL), _child_center(NULL),
  _visible(true)
{
  Vector	v1;
  Vector	v2;

  glagen.triangles = glagen.triangles + 1;
  if (glagen.triangles > glagen.max_triangles)
    exit (1);
  if (father == NULL)
    _level = 0;
  else
    _level = father->Level () + 1;

  a->Use (father, this);
  b->Use (father, this);
  c->Use (father, this);

  _center = Vector ((a->x () + b->x () + c-> x()) / 3,
		    (a->y () + b->y () + c-> y()) / 3,
		    (a->z () + b->z () + c-> z()) / 3);

  v1 = Vector (a->x () - b->x (), a->y () - b->y (), a->z () - b->z ());
  v2 = Vector (a->x () - c->x (), a->y () - c->y (), a->z () - c->z ());
  _normal = Vector (v1 ^ v2);
  _size = _normal.Norm ();
  _normal = _normal / _size;
  _normal_real = _normal;
  _size = sqrtf (_size / 2);

  step = glagen.step - 1;
}

Triangle :: ~Triangle ()
{
  if (_child_center != NULL)
    {
      delete _child_center;
      delete _child_a;
      delete _child_b;
      delete _child_c;
    }

  // Del the old connexity
  if (_neighbor_ab != NULL)
    _neighbor_ab->Del_connexity (this);
  if (_neighbor_bc != NULL)
    _neighbor_bc->Del_connexity (this);
  if (_neighbor_ca != NULL)
    _neighbor_ca->Del_connexity (this);

  // Tell the vertices they aren't used by this triangle anymore
  if (_a->Drop (this, _father))
    delete _a;
  if (_b->Drop (this, _father))
    delete _b;
  if (_c->Drop (this, _father))
    delete _c;

  if (_father != NULL)
    _father->Child_dead (this);

  glagen.triangles = glagen.triangles - 1;
}


// ======================================================================= Read

// The level
unsigned int	Triangle :: Level () const	{ return _level; }

// The vertices
Dot		*Triangle :: A () const	{ return _a; }
Dot		*Triangle :: B () const	{ return _b; }
Dot		*Triangle :: C () const	{ return _c; }

// The neighborhood
Triangle	*Triangle :: Neighbor_ab () const { return _neighbor_ab; }
Triangle	*Triangle :: Neighbor_bc () const { return _neighbor_bc; }
Triangle	*Triangle :: Neighbor_ca () const { return _neighbor_ca; }

// The father
Triangle	*Triangle :: Father () const { return _father; }

// The childs
Triangle	*Triangle :: Child_a() const { return _child_a; }
Triangle	*Triangle :: Child_b() const { return _child_b; }
Triangle	*Triangle :: Child_c() const { return _child_c; }
Triangle	*Triangle :: Child_center() const { return _child_center; }
Triangle	*Triangle :: Child (Dot *match) const
{
  if (match == _a)
    return _child_a;
  if (match == _b)
    return _child_b;
  if (match == _c)
    return _child_c;
  return NULL;
}

Vector		&Triangle :: Normal () { return _normal; }
Vector		&Triangle :: Normal_real () { return _normal_real; }

float		Triangle :: Size () const	{ return _size; }

// Is this triangle split ?
bool		Triangle :: Is_split () const
{
  return (_child_center != NULL);
}

// In the current turn, has this triangle been checked ?
bool		Triangle :: Is_checked () const
{
  return (step == glagen.step);
}

// According to the position of the observer, does this triangle
// need to be split ?
float		Triangle :: To_split () const
{
  float x = _center.X () - glagen.observer.frame.Origin_X ();
  float y = _center.Y () - glagen.observer.frame.Origin_Y ();
  float z = _center.Z () - glagen.observer.frame.Origin_Z ();
//   float dist = x * x + y * y + z * z;
  float dist = Approx_dist(x, y, z);
//   float alpha = dist / (_size * _size);
  float alpha = (dist * dist) / (_size * _size);

  // Special case :
  // if over the horizon, the result is increased
//   if (dist > 100 * glagen.observer.altitude * glagen.observer.altitude)
  if (dist > 10 * glagen.observer.altitude)
    alpha = alpha * alpha / 2;
//   if (dist > 1000 * glagen.observer.altitude * glagen.observer.altitude)
  if (dist > 32 * glagen.observer.altitude)
    alpha = alpha * alpha / 2;
  if (!_visible)
    alpha = (alpha * alpha) / 2;
  return (alpha);
}

// According to the position of the observer, does this triangle
// need to be merged ?
bool		Triangle :: Is_visible () const { return _visible; }

// ====================================================================== Write

// This triangle must set a reference to the given other one
void		Triangle :: Make_connexity (Triangle *neighborhood)
{
  // Find on which side is the other triangle and then set the connexity
  if ((neighborhood->A () == _a)
      || (neighborhood->B () == _a)
      || (neighborhood->C () == _a))
    {
      if ((neighborhood->A () == _b)
	  || (neighborhood->B () == _b)
	  || (neighborhood->C () == _b))
	_neighbor_ab = neighborhood;
      else
	_neighbor_ca = neighborhood;
    }
  else
    _neighbor_bc = neighborhood;
}

// This triangle must forget its reference to the given other one
void		Triangle :: Del_connexity (Triangle *related)
{
  // Find the connexity and delete it
  if (_neighbor_ab == related)
    _neighbor_ab = NULL;
  if (_neighbor_bc == related)
    _neighbor_bc = NULL;
  if (_neighbor_ca == related)
    _neighbor_ca = NULL;
}

// The split function
void		Triangle :: Split ()
{
  Dot		*d;
  Dot		*e;
  Dot		*f;
  Triangle	*neighbor_af;
  Triangle	*neighbor_ae;
  Triangle	*neighbor_bd;
  Triangle	*neighbor_bf;
  Triangle	*neighbor_ce;
  Triangle	*neighbor_cd;

  // Test if the triangle is already split
  if (Is_split ())
    return;

  // Check the differences of iterations
  if (_neighbor_ab == NULL || _neighbor_bc == NULL || _neighbor_ca == NULL)
     _father->Split_neighbor();

  // Find / create vertex
  if (_neighbor_bc->Is_split ())
    {
      // Identify and save the future connexity
      neighbor_bd = _neighbor_bc->Child (_b);
      neighbor_cd = _neighbor_bc->Child (_c);

      // Pop the vertex to use
      if (neighbor_bd->B () == neighbor_cd->C ())
	d = neighbor_bd->B ();
      else
	d = neighbor_bd->C ();
    }
  else
    {
      // Create the vertex and set the connexity to NULL
      d = _b->Middle (_c); // new ; delete : triangle.cc l99, 101, 103
      neighbor_bd = NULL;
      neighbor_cd = NULL;
    }

  // The same for each side
  if (_neighbor_ca->Is_split ())
    {
      neighbor_ce = _neighbor_ca->Child (_c);
      neighbor_ae = _neighbor_ca->Child (_a);
      if (neighbor_ce->B () == neighbor_ae->C ())
	e = neighbor_ce->B ();
      else
	e = neighbor_ce->C ();
    }
  else
    {
      e = _c->Middle (_a); // new ; delete : triangle.cc l99, 101, 103
      neighbor_ce = NULL;
      neighbor_ae = NULL;
    }

  if (_neighbor_ab->Is_split ())
    {
      neighbor_af = _neighbor_ab->Child (_a);
      neighbor_bf = _neighbor_ab->Child (_b);
      if (neighbor_af->B () == neighbor_bf->C ())
	f = neighbor_af->B ();
      else
	f = neighbor_af->C ();
    }
  else
    {
      f = _a->Middle (_b); // new ; delete : triangle.cc l99, 101, 103
      neighbor_af = NULL;
      neighbor_bf = NULL;
    }

  // Create triangles
  _child_center = new Triangle (d, e, f, this); // delete : triangle.cc l90
  _child_a = new Triangle (_a, f, e, this); // delete : triangle.cc l91
  _child_b = new Triangle (_b, d, f, this); // delete : triangle.cc l92
  _child_c = new Triangle (_c, e, d, this); // delete : triangle.cc l93

  // Set the final connexity
  if (neighbor_af != NULL)
    {
      _child_a->Make_connexity (neighbor_af);
      neighbor_af->Make_connexity (_child_a);
    }
  if (neighbor_ae != NULL)
    {
      _child_a->Make_connexity (neighbor_ae);
      neighbor_ae->Make_connexity (_child_a);
    }
  if (neighbor_bd != NULL)
    {
      _child_b->Make_connexity (neighbor_bd);
      neighbor_bd->Make_connexity (_child_b);
   }
  if (neighbor_bf != NULL)
    {
      _child_b->Make_connexity (neighbor_bf);
      neighbor_bf->Make_connexity (_child_b);
    }
  if (neighbor_ce != NULL)
    {
      _child_c->Make_connexity (neighbor_ce);
      neighbor_ce->Make_connexity (_child_c);
    }
  if (neighbor_cd != NULL)
    {
      _child_c->Make_connexity (neighbor_cd);
      neighbor_cd->Make_connexity (_child_c);
    }

  _child_a->Make_connexity (_child_center);
  _child_b->Make_connexity (_child_center);
  _child_c->Make_connexity (_child_center);
  _child_center->Make_connexity (_child_a);
  _child_center->Make_connexity (_child_b);
  _child_center->Make_connexity (_child_c);

  // Check for chained reactions
  if (_neighbor_ab != NULL)
    _neighbor_ab->Check_T ();
  if (_neighbor_bc != NULL)
    _neighbor_bc->Check_T ();
  if (_neighbor_ca != NULL)
    _neighbor_ca->Check_T ();
}

// Check if a triangle needs to be split just because too many
// triangles in the neighborhood are split.
void		Triangle :: Check_T ()
{
  int		warning;

  // The T problem only occurs if the triangle isn't Split
  if (_child_center != NULL)
    return;
  warning = 0;
  if (_neighbor_ab != NULL)
    if (_neighbor_ab->Is_split ())
      warning = warning + 1;
  if (_neighbor_bc != NULL)
    if (_neighbor_bc->Is_split ())
      warning = warning + 1;
  if (_neighbor_ca != NULL)
    if (_neighbor_ca->Is_split ())
      warning = warning + 1;
  if (warning > 1)
    Split ();
}

// The big merging function : we are not sure it will really merge
// the triangle, but at least, it will merge the children.
void		Triangle :: Merge ()
{
  unsigned char	i;

  if (Is_split())
    {
      // First we merge the children
      _child_center->Merge_simple ();
      _child_a->Merge_simple ();
      _child_b->Merge_simple ();
      _child_c->Merge_simple ();

      // Then we check the neighborhood
      i = 0;
      if (_neighbor_ab != NULL)
	if (_neighbor_ab->Is_split ())
	  {
	    _neighbor_ab->Front_attack (_a, _b);
	    i = i + 1;
	  }
      if (_neighbor_bc != NULL)
	if (_neighbor_bc->Is_split ())
	  {
	    _neighbor_bc->Front_attack (_b, _c);
	    i = i + 1;
	  }
      if (_neighbor_ca != NULL)
	if (_neighbor_ca->Is_split ())
	  {
	    _neighbor_ca->Front_attack (_c, _a);
	    i = i + 1;
	  }

      // If there's only one split neighbor triangle, then we can
      // also destroy the children. Else we can't because it would
      // have too much unexpected effects
      if (i < 2)
	{
	  // Destroy the child
	  delete _child_center;
	  delete _child_a;
	  delete _child_b;
	  delete _child_c;

	  // Don't forget to change the pointers !
	  _child_center = NULL;
	  _child_a = NULL;
	  _child_b = NULL;
	  _child_c = NULL;
	}
    }
}

// Just a merge function without T case management
void		Triangle :: Merge_simple ()
{
  if (_child_center != NULL)
    {
      // Recursive merge
      _child_center->Merge_simple ();
      _child_a->Merge_simple ();
      _child_b->Merge_simple ();
      _child_c->Merge_simple ();

      // Destroy the child
      delete _child_center;
      delete _child_a;
      delete _child_b;
      delete _child_c;

      // Don't forget to change the pointers !
      _child_center = NULL;
      _child_a = NULL;
      _child_b = NULL;
      _child_c = NULL;
    }
}

// Check the triangle for T cases when the neigbor triangle is merged
void		Triangle :: Front_attack (Dot *quad_a, Dot *quad_d)
{
  Dot		*quad_b;
  Dot		*quad_c;
  Triangle	*triangle_ab;
  Triangle	*triangle_cd;
  Triangle	*last_child;

  triangle_ab = Child (quad_a);
  triangle_cd = Child (quad_d);
  if (quad_a == _a)
    {
      if (quad_d == _b)
	last_child = _child_c;
      else
	last_child = _child_b;
    }
  else
    if (quad_a == _b)
      {
	if (quad_d == _c)
	  last_child = _child_a;
	else
	  last_child = _child_c;
      }
    else
      if (quad_d == _a)
	last_child = _child_b;
      else
	last_child = _child_a;

  triangle_ab->Merge_simple ();
  _child_center->Merge_simple ();
  triangle_cd->Merge_simple ();

  if (triangle_ab->B () == triangle_cd->C ())
    {
      quad_b = triangle_ab->C ();
      quad_c = triangle_cd->B ();
      if (triangle_ab->Neighbor_ca () != NULL)
	if (triangle_ab->Neighbor_ca ()->Is_split ())
	  triangle_ab->Neighbor_ca ()->Front_attack (quad_a, quad_b);
      if (triangle_cd->Neighbor_ab () != NULL)
	if (triangle_cd->Neighbor_ab ()->Is_split ())
	  triangle_cd->Neighbor_ab ()->Front_attack (quad_c, quad_d);
    }
  else
    {
      quad_b = triangle_ab->B ();
      quad_c = triangle_cd->C ();
      if (triangle_ab->Neighbor_ab () != NULL)
	if (triangle_ab->Neighbor_ab ()->Is_split ())
	  triangle_ab->Neighbor_ab ()->Front_attack (quad_a, quad_b);
      if (triangle_cd->Neighbor_ca () != NULL)
	if (triangle_cd->Neighbor_ca ()->Is_split ())
	  triangle_cd->Neighbor_ca ()->Front_attack (quad_c, quad_d);
    }
  if (last_child->Is_split ())
    last_child->Front_attack (quad_b, quad_c);
}

// Check all the triangles to apply split or merge
void		Triangle :: Split_visitor ()
{
  if (step == glagen.step)
    return;
  step = glagen.step;

  float to_split = To_split ();

  if (to_split != 0)
    {
      if (to_split > 350)
	Merge ();
      else
	{
	  if (glagen.triangles <= glagen.max_triangles)
	    if (to_split < 300)
	      if (false == Is_split ())
	        Split ();

	  if (Is_split ())
	    {
	      // We check the childs
	      _child_center->Split_visitor ();
	      _child_a->Split_visitor ();
	      _child_b->Split_visitor ();
	      _child_c->Split_visitor ();
	    }
	}
    }

  // If there's no father, it means it's one of the root
  // triangles and we can go to check the neighborhood
  if (NULL == _father)
    {
      _neighbor_ab->Split_visitor ();
      _neighbor_bc->Split_visitor ();
      _neighbor_ca->Split_visitor ();
    }
}

// The visitor that computes if a triangle is visible or not.
bool		Triangle :: Hide_visitor ()
{
  if (step != glagen.step)
    {
      step = glagen.step;
      if (Is_split ())
	{
	  _visible = _child_a->Hide_visitor ();
	  _visible = _child_b->Hide_visitor () || _visible;
	  _visible = _child_c->Hide_visitor () || _visible;
	  _visible = _child_center->Hide_visitor () || _visible;
	}
      else
	{
	  // Let compute if it is visible...

	  // We construct the vector from the center of to planet to
	  // the observer
	  Vector v = Vector (glagen.observer.frame.Origin_X () - _center.X (),
			     glagen.observer.frame.Origin_Y () - _center.Y (),
			     glagen.observer.frame.Origin_Z () -
			     _center.Z ());
	  // We compute the scalar product to know how far it is
	  _visible = ((_normal * v) > 0);

	  // Now, let compute if it is in the vision field
	  if (_visible == true)
	    {
	      v.Approx_normalize ();
	      _visible = (v * glagen.observer.frame.Basis_Z () < -0.70);
	    }
	}

      // If there's no father, it means it's one of the root
      // triangles and we can go to check the neighborhood
      if (NULL == _father)
	{
	  _neighbor_ab->Hide_visitor ();
	  _neighbor_bc->Hide_visitor ();
	  _neighbor_ca->Hide_visitor ();
	}
    }
  return _visible;
}

// Called by a child when deleted
void		Triangle :: Child_dead (Triangle *child)
{
  if (_child_center == child)
    _child_center = NULL;
  if (_child_a == child)
    _child_a = NULL;
  if (_child_b == child)
    _child_b = NULL;
  if (_child_c == child)
    _child_c = NULL;
}

// This triangle is checked
void		Triangle :: Checked ()	{ step = glagen.step; }


// ====================================================================== Other

// Split the neighborhood triangles
void		Triangle :: Split_neighbor ()
{
  if (_neighbor_ab != NULL)
    _neighbor_ab->Split ();
  if (_neighbor_bc != NULL)
    _neighbor_bc->Split ();
  if (_neighbor_ca != NULL)
    _neighbor_ca->Split ();
}

// Update the normal vector, if the triangle is moving.
void		Triangle :: Update_normal ()
{
  surface_t	*surface;
  float		adjust = 0;

  // Get the position of the dot A
  if (glagen.display_planet == true)
    {
      if (NULL == _a->Property (0))
	adjust = 0;
      else
	{
	  surface = static_cast <surface_t *> (_a->Property (0)->data);
	  if (NULL == surface)
	    adjust = 0;
	  else
	    adjust = surface->height;
	}
    }
  float	ax = _a->x () * (glagen.size + adjust);
  float	ay = _a->y () * (glagen.size + adjust);
  float	az = _a->z () * (glagen.size + adjust);

  // Get the position of the dot B
  if (glagen.display_planet)
    {
      if (NULL == _b->Property (0))
	adjust = 0;
      else
	{
	  surface = static_cast <surface_t *> (_b->Property (0)->data);
	  if (NULL == surface)
	    adjust = 0;
	  else
	    adjust = surface->height;
	}
    }
  float	bx = _b->x () * (glagen.size + adjust);
  float	by = _b->y () * (glagen.size + adjust);
  float	bz = _b->z () * (glagen.size + adjust);

  // Get the position of the dot C
  if (glagen.display_planet)
    {
      if (NULL == _c->Property (0))
	adjust = 0;
      else
	{
	  surface = static_cast <surface_t *> (_c->Property (0)->data);
	  if (NULL == surface)
	    adjust = 0;
	  else
	    adjust = surface->height;
	}
    }
  float	cx = _c->x () * (glagen.size + adjust);
  float	cy = _c->y () * (glagen.size + adjust);
  float	cz = _c->z () * (glagen.size + adjust);

  Vector v1 = Vector (ax - bx, ay - by, az - bz);
  Vector v2 = Vector (ax - cx, ay - cy, az - cz);
  _normal_real = Vector (v1 ^ v2);
  _normal_real.Normalize ();
}

void		Triangle :: Update_normal_visitor ()
{
  if (step == glagen.step)
    return;
  step = glagen.step;

  Update_normal ();

  if (_child_center != NULL)
    {
      _child_center->Update_normal_visitor ();
      _child_a->Update_normal_visitor ();
      _child_b->Update_normal_visitor ();
      _child_c->Update_normal_visitor ();
    }

  if (NULL == _father)
    {
      _neighbor_ab->Update_normal_visitor ();
      _neighbor_bc->Update_normal_visitor ();
      _neighbor_ca->Update_normal_visitor ();
    }

  _a->Update_normal ();
  _b->Update_normal ();
  _c->Update_normal ();
}