/*
 *  Ray++ - Object-oriented ray tracing library
 *  Copyright (C) 1998-2001 Martin Reinecke and others.
 *  See the AUTHORS file for more information.
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Library General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library 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
 *  Library General Public License for more details.
 *
 *  You should have received a copy of the GNU Library General Public
 *  License along with this library; if not, write to the Free
 *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 *  See the README file for more information.
 */

#include "shapes/csg_shape.h"

namespace RAYPP {

//virtual
void CSG_SHAPE::Init ()
  {
  if (initialized) return;
  if (Shp.size()<2) error ("CSG_SHAPE: too few elements");
  uint4 i;
  Mybox.Reset();
  for (i=0; i<Shp.size(); ++i)
    {
    Shp[i]->Init ();
    if (!Shp[i]->Has_Inside()) error ("CSG_SHAPE: shape without inside");
    Mybox.Include (Shp[i]->BBox());
    }
  if (Type == INTERSECTION)
    {
    for (i=0; i<Shp.size(); ++i)
      if (Shp[i]->Inside_in_BBox()) Mybox.Build_Intersection (Shp[i]->BBox());
    }
  initialized = true;
  }

//virtual
void CSG_SHAPE::Deinit ()
  {
  if (!initialized) return;
  for (uint4 i=0; i<Shp.size(); ++i)
    Shp[i]->Deinit ();
  initialized = false;
  }

//virtual
void CSG_SHAPE::Transform (const TRANSFORM &trans)
  {
  cni();
  for (uint4 i=0; i<Shp.size(); ++i)
    Shp[i]->Transform (trans);
  }

//virtual
AXISBOX CSG_SHAPE::BBox () const
  {
  ci();
  return Mybox;
  }

//virtual
bool CSG_SHAPE::Test (const GEOM_RAY &Ray, float8 &dist, bool &realhit) const
  {
//realhit=false;dist=Ray.mindist;return true;
  GEOM_RAY Local_Ray = Ray;
  bool found = false;
  float8 depth;

  if (!Mybox.Ray_in_Bounds (Local_Ray, depth)) return false;
  for (uint4 i=0; i<Shp.size(); ++i)
    {
    if (Shp[i]->Test (Local_Ray, depth, realhit))
      {
      Local_Ray.maxdist = depth;
      found = true;
      dist = depth;
      }
    }
  realhit = false;
  return found;
  }

//virtual
bool CSG_SHAPE::Inside (const VECTOR &loc) const
  {
  uint4 i;

  switch (Type)
    {
    case INTERSECTION:
      for (i=0; i<Shp.size(); ++i)
        {
        if (!Shp[i]->Inside (loc)) return Inverted;
        }
      return (!Inverted);
    case UNION:
      for (i=0; i<Shp.size(); ++i)
        {
        if (Shp[i]->Inside (loc)) return (!Inverted);
        }
      return Inverted;
    }
// kludge: return value required
  return false;
  }

class CSG_SHAPE_ENTRY
  {
  public:
    uint4 number;
    VECTOR Normal;
    float8 dist;

    CSG_SHAPE_ENTRY () {}
    CSG_SHAPE_ENTRY (uint4 num, const SHAPE::INTER &Inter)
      : number (num), Normal (Inter.second), dist (Inter.first) {}

    bool operator< (const CSG_SHAPE_ENTRY &other) const
// YES, that's correct, since we need the NEAREST intersection first
      { return (dist > other.dist); }
  };

//virtual
bool CSG_SHAPE::Intersect (const GEOM_RAY &Ray, float8 &dist,
  VECTOR &Normal) const
  {
  priority_queue<CSG_SHAPE_ENTRY> Queue;
  vector<INTER> Intersections;
  vector<bool> nowInside (Shp.size());
  VECTOR actpoint = Ray.evalmin();
  uint4 i;

  for (i=0; i<Shp.size(); ++i)
    {
    nowInside[i] = Shp[i]->Inside (actpoint);
    Intersections.clear();
    Shp[i]->All_Intersections (Ray, Intersections);
    for (uint4 n=0; n<Intersections.size(); ++n)
      {
      Queue.push (CSG_SHAPE_ENTRY (i, Intersections[n]));
      }
    }

  bool bailout;
  CSG_SHAPE_ENTRY entry;
  while (!Queue.empty())
    {
    entry = Queue.top();
    dist = entry.dist;
    Queue.pop();
    nowInside[entry.number] = !nowInside[entry.number];
    bailout = false;
    switch (Type)
      {
      case INTERSECTION:
        for (i=0; (i<Shp.size()) && (!bailout); ++i)
          {
          if ((i!=entry.number) && (!nowInside[i])) bailout = true;
          }
        break;
      case UNION:
        for (i=0; (i<Shp.size()) && (!bailout); ++i)
          {
          if ((i!=entry.number) && (nowInside[i])) bailout = true;
          }
        break;
      }
    if (!bailout)
      {
      Normal = entry.Normal;
      if (Inverted) Normal.Flip();
      return true;
      }
    }
  return false;
  }

//virtual
void CSG_SHAPE::All_Intersections (const GEOM_RAY &Ray, vector<INTER> &Inter)
  const
  {
  float8 dist;
  uint4 i;
  priority_queue<CSG_SHAPE_ENTRY> Queue;
  vector<INTER> myInter;
  vector <bool> nowInside (Shp.size());
  VECTOR actpoint = Ray.evalmin();

  for (i=0; i<Shp.size(); ++i)
    {
    nowInside[i] = Shp[i]->Inside (actpoint);
    myInter.clear();
    Shp[i]->All_Intersections (Ray, myInter);
    for (uint4 n=0; n<myInter.size(); ++n)
      Queue.push (CSG_SHAPE_ENTRY (i, myInter[n]));
    }

  bool bailout;
  CSG_SHAPE_ENTRY entry;
  while (!Queue.empty())
    {
    entry = Queue.top();
    dist = entry.dist;
    Queue.pop();
    nowInside[entry.number] = !nowInside[entry.number];
    bailout = false;
    switch (Type)
      {
      case INTERSECTION:
        for (i=0; (i<Shp.size()) && (!bailout); ++i)
          {
          if ((i!=entry.number) && (!nowInside[i])) bailout = true;
          }
        break;
      case UNION:
        for (i=0; (i<Shp.size()) && (!bailout); ++i)
          {
          if ((i!=entry.number) && (nowInside[i])) bailout = true;
          }
        break;
      }
    if (!bailout)
      {
      if (Inverted) entry.Normal.Flip();
      Inter.push_back (INTER (dist, entry.Normal));
      }
    }
  }

void CSG_SHAPE::Add (HANDLE<SHAPE> Shape)
  {
  cni();
  Shp.push_back (Shape);
  }

} // namespace RAYPP