/****************************************************************************
*                   csg.c
*
*  This module implements routines for constructive solid geometry.
*
*  from Persistence of Vision(tm) Ray Tracer
*  Copyright 1996 Persistence of Vision Team
*---------------------------------------------------------------------------
*  NOTICE: This source code file is provided so that users may experiment
*  with enhancements to POV-Ray and to port the software to platforms other
*  than those supported by the POV-Ray Team.  There are strict rules under
*  which you are permitted to use this file.  The rules are in the file
*  named POVLEGAL.DOC which should be distributed with this file. If
*  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
*  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
*  Forum.  The latest version of POV-Ray may be found there as well.
*
* This program is based on the popular DKB raytracer version 2.12.
* DKBTrace was originally written by David K. Buck.
* DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
*
*****************************************************************************/

#include "frame.h"
#include "povray.h"
#include "vector.h"
#include "povproto.h"
#include "bbox.h"
#include "csg.h"
#include "hfield.h"
#include "matrices.h"
#include "objects.h"
#include "planes.h"
#include "quadrics.h"



/*****************************************************************************
* Local preprocessor defines
******************************************************************************/




/*****************************************************************************
* Static functions
******************************************************************************/

static int All_CSG_Union_Intersections PARAMS((OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack));
static int All_CSG_Merge_Intersections PARAMS((OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack));
static int All_CSG_Intersect_Intersections PARAMS((OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack));
static int Inside_CSG_Union PARAMS((VECTOR point, OBJECT *Object));
static int Inside_CSG_Intersection PARAMS((VECTOR point, OBJECT *Object));
static void *Copy_CSG PARAMS((OBJECT *Object));
static void Translate_CSG PARAMS((OBJECT *Object, VECTOR Vector, TRANSFORM *Trans));
static void Rotate_CSG PARAMS((OBJECT *Object, VECTOR Vector, TRANSFORM *Trans));
static void Scale_CSG PARAMS((OBJECT *Object, VECTOR Vector, TRANSFORM *Trans));
static void Transform_CSG PARAMS((OBJECT *Object, TRANSFORM *Trans));
static void Destroy_CSG PARAMS((OBJECT *Object));
static void Invert_CSG_Union PARAMS((OBJECT *Object));
static void Invert_CSG_Intersection PARAMS((OBJECT *Object));


/*****************************************************************************
* Local variables
******************************************************************************/

METHODS CSG_Union_Methods =
{
  All_CSG_Union_Intersections,
  Inside_CSG_Union, NULL /*Normal*/,
  Copy_CSG,
  Translate_CSG, Rotate_CSG,
  Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
};

METHODS CSG_Merge_Methods =
{
  All_CSG_Merge_Intersections,
  Inside_CSG_Union, NULL /*Normal*/,
  Copy_CSG,
  Translate_CSG, Rotate_CSG,
  Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
};

METHODS CSG_Intersection_Methods =
{
  All_CSG_Intersect_Intersections,
  Inside_CSG_Intersection, NULL /*Normal*/,
  Copy_CSG,
  Translate_CSG, Rotate_CSG,
  Scale_CSG, Transform_CSG, Invert_CSG_Intersection, Destroy_CSG
};



/*****************************************************************************
*
* FUNCTION
*
*   All_CSG_Union_Intersections
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*   
* AUTHOR
*
*   POV-Ray Team
*   
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   Sep 1994 : Added code to count intersection tests. [DB]
*
******************************************************************************/

static int All_CSG_Union_Intersections (Object, Ray, Depth_Stack)
OBJECT *Object;
RAY *Ray;
ISTACK *Depth_Stack;
{
  int Found;
  OBJECT *Current_Sib, *Clip;
  ISTACK *Local_Stack;
  INTERSECTION *Sibling_Intersection;

  Increase_Counter(stats[Ray_CSG_Union_Tests]);

  Found = FALSE;

  /* Use shortcut if no clip. */

  if ((Clip = Object->Clip) == NULL)
  {
    for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
    {
      if (Ray_In_Bound (Ray, Current_Sib->Bound))
      {
        if (All_Intersections (Current_Sib, Ray, Depth_Stack))
        {
          Found = TRUE;
        }
      }
    }
  }
  else
  {
    Local_Stack = open_istack();

    for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
    {
      if (Ray_In_Bound (Ray, Current_Sib->Bound))
      {
        if (All_Intersections (Current_Sib, Ray, Local_Stack))
        {
          while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
          {
            if (Point_In_Clip (Sibling_Intersection->IPoint, Clip))
            {
              push_copy (Depth_Stack, Sibling_Intersection);

              Found = TRUE;
            }
          }
        }
      }
    }

    close_istack (Local_Stack);
  }

  if (Found)
  {
    Increase_Counter(stats[Ray_CSG_Union_Tests_Succeeded]);
  }

  return (Found);
}



/*****************************************************************************
*
* FUNCTION
*
*   All_CSG_Intersection_Intersections
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   Sep 1994 : Added code to count intersection tests. [DB]
*
******************************************************************************/

static int All_CSG_Intersect_Intersections (Object, Ray, Depth_Stack)
OBJECT *Object;
RAY *Ray;
ISTACK *Depth_Stack;
{
  int Maybe_Found, Found;
  OBJECT *Current_Sib, *Inside_Sib;
  ISTACK *Local_Stack;
  INTERSECTION *Sibling_Intersection;

  Increase_Counter(stats[Ray_CSG_Intersection_Tests]);

  Local_Stack = open_istack ();

  Found = FALSE;

  for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
  {
    if (Ray_In_Bound (Ray, Current_Sib->Bound))
    {
      if (All_Intersections (Current_Sib, Ray, Local_Stack))
      {
        while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
        {
          Maybe_Found = TRUE;

          for (Inside_Sib = ((CSG *)Object)->Children; Inside_Sib != NULL; Inside_Sib = Inside_Sib->Sibling)
          {
            if (Inside_Sib != Current_Sib)
            {
              if (!Inside_Object (Sibling_Intersection->IPoint, Inside_Sib))
              {
                Maybe_Found = FALSE;

                break;
              }
            }
          }

          if (Maybe_Found)
          {
            if (Point_In_Clip (Sibling_Intersection->IPoint, Object->Clip))
            {
              push_copy(Depth_Stack, Sibling_Intersection);

              Found = TRUE;
            }
          }
        }
      }
    }
  }

  close_istack (Local_Stack);

  if (Found)
  {
    Increase_Counter(stats[Ray_CSG_Intersection_Tests_Succeeded]);
  }

  return (Found);
}



/*****************************************************************************
*
* FUNCTION
*
*   All_CSG_Merge_Intersections
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   Sep 1994 : Added code to count intersection tests. [DB]
*
******************************************************************************/

static int All_CSG_Merge_Intersections (Object, Ray, Depth_Stack)
OBJECT *Object;
RAY *Ray;
ISTACK *Depth_Stack;
{
  int Found, inside_flag;
  OBJECT *Sib1, *Sib2;
  ISTACK *Local_Stack;
  INTERSECTION *Sibling_Intersection;

  Increase_Counter(stats[Ray_CSG_Merge_Tests]);

  Found = FALSE;

  Local_Stack = open_istack ();

  for (Sib1 = ((CSG *)Object)->Children; Sib1 != NULL; Sib1 = Sib1->Sibling)
  {
    if (Ray_In_Bound (Ray, Sib1->Bound))
    {
      if (All_Intersections (Sib1, Ray, Local_Stack))
      {
        while ((Sibling_Intersection = pop_entry (Local_Stack)) !=  NULL)
        {
          if (Point_In_Clip (Sibling_Intersection->IPoint, Object->Clip))
          {
            inside_flag = TRUE;

            for (Sib2 = ((CSG *)Object)->Children; Sib2 != NULL && inside_flag == TRUE; Sib2 = Sib2->Sibling)
            {
              if (Sib1 != Sib2)
              {
                if (Inside_Object(Sibling_Intersection->IPoint, Sib2))
                {
                  inside_flag = FALSE;
                }
              }
            }

            if (inside_flag == TRUE)
            {
              Found = TRUE;

              push_copy (Depth_Stack, Sibling_Intersection);
            }
          }
        }
      }
    }
  }

  close_istack (Local_Stack);

  if (Found)
  {
    Increase_Counter(stats[Ray_CSG_Merge_Tests_Succeeded]);
  }

  return (Found);
}



/*****************************************************************************
*
* FUNCTION
*
*   Inside_CSG_Union
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static int Inside_CSG_Union (IPoint, Object)
VECTOR IPoint;
OBJECT *Object;
{
  OBJECT *Current_Sib;

  for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
  {
    if (Inside_Object (IPoint, Current_Sib))
    {
      return (TRUE);
    }
  }

  return (FALSE);
}



/*****************************************************************************
*
* FUNCTION
*
*   Inside_CSG_Intersection
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static int Inside_CSG_Intersection (IPoint, Object)
OBJECT *Object;
VECTOR IPoint;
{
  OBJECT *Current_Sib;

  for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
  {
    if (!Inside_Object (IPoint, Current_Sib))
    {
      return (FALSE);
    }
  }

  return (TRUE);
}



/*****************************************************************************
*
* FUNCTION
*
*   Translate_CSG
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Translate_CSG (Object, Vector, Trans)
OBJECT *Object;
VECTOR Vector;
TRANSFORM *Trans;
{
  OBJECT *Sib;

  for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  {
    Translate_Object(Sib, Vector, Trans);
  }

  Recompute_BBox(&Object->BBox, Trans);
}



/*****************************************************************************
*
* FUNCTION
*
*   Rotate_CSG
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Rotate_CSG (Object, Vector, Trans)
OBJECT *Object;
VECTOR Vector;
TRANSFORM *Trans;
{
  OBJECT *Sib;

  for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  {
    Rotate_Object(Sib, Vector, Trans);
  }

  Recompute_BBox(&Object->BBox, Trans);
}



/*****************************************************************************
*
* FUNCTION
*
*   Scale_CSG
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Scale_CSG (Object, Vector, Trans)
OBJECT *Object;
VECTOR Vector;
TRANSFORM *Trans;
{
  OBJECT *Sib;

  for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  {
    Scale_Object(Sib, Vector, Trans);
  }

  Recompute_BBox(&Object->BBox, Trans);
}



/*****************************************************************************
*
* FUNCTION
*
*   Transform_CSG
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Transform_CSG (Object, Trans)
OBJECT *Object;
TRANSFORM *Trans;
{
  OBJECT *Sib;

  for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  {
    Transform_Object (Sib, Trans);
  }

  Recompute_BBox(&Object->BBox, Trans);
}



/*****************************************************************************
*
* FUNCTION
*
*   Invert_CSG_Union
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Invert_CSG_Union (Object)
OBJECT *Object;
{
  OBJECT *Sib;

  Object->Methods = &CSG_Intersection_Methods;

  for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  {
    Invert_Object (Sib);
  }

  Invert_Flag(Object, INVERTED_FLAG);
}



/*****************************************************************************
*
* FUNCTION
*
*   Invert_CSG_Intersection
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Invert_CSG_Intersection (Object)
OBJECT *Object;
{
  OBJECT *Sib;

  Object->Methods = &CSG_Union_Methods;

  for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  {
    Invert_Object (Sib);
  }

  Invert_Flag(Object, INVERTED_FLAG);
}



/*****************************************************************************
*
* FUNCTION
*
*   Create_CSG_Union
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

CSG *Create_CSG_Union ()
{
  CSG *New;

  New = (CSG *)POV_MALLOC(sizeof (CSG), "union");

  INIT_OBJECT_FIELDS(New, UNION_OBJECT, &CSG_Union_Methods)

  New->Children = NULL;

  return (New);
}



/*****************************************************************************
*
* FUNCTION
*
*   Create_CSG_Merge
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

CSG *Create_CSG_Merge ()
{
  CSG *New;

  New = (CSG *)POV_MALLOC(sizeof (CSG), "merge");

  INIT_OBJECT_FIELDS(New, MERGE_OBJECT, &CSG_Merge_Methods)

  New->Children = NULL;

  return (New);
}



/*****************************************************************************
*
* FUNCTION
*
*   Create_CSG_Intersection
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

CSG *Create_CSG_Intersection ()
{
  CSG *New;

  New = (CSG *)POV_MALLOC(sizeof (CSG), "intersection");

  INIT_OBJECT_FIELDS(New, INTERSECTION_OBJECT, &CSG_Intersection_Methods)

  New->Children = NULL;

  return (New);
}



/*****************************************************************************
*
* FUNCTION
*
*   Copy_CSG
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void *Copy_CSG (Object)
OBJECT *Object;
{
  CSG *New;
  OBJECT *Old_Sib, *New_Sib, *Prev_Sib;

  New = (CSG *)POV_MALLOC(sizeof (CSG), "csg");

  *New = *(CSG *)Object;

  New->Children = Prev_Sib = NULL;

  for (Old_Sib = ((CSG *)Object)->Children; Old_Sib != NULL; Old_Sib = Old_Sib->Sibling)
  {
    New_Sib = Copy_Object (Old_Sib);

    if (New->Children == NULL)
    {
      New->Children = New_Sib;
    }

    if (Prev_Sib != NULL)
    {
      Prev_Sib->Sibling = New_Sib;
    }

    Prev_Sib = New_Sib;
  }

  return (New);
}



/*****************************************************************************
*
* FUNCTION
*
*   Destroy_CSG
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Destroy_CSG (Object)
OBJECT *Object;
{
  Destroy_Object (((CSG *) Object)->Children);

  POV_FREE (Object);
}



/*****************************************************************************
*
* FUNCTION
*
*   Compute_CSG_BBox
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   POV-Ray Team
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   Sep 1994 : Improved bounding of quadrics used in CSG intersections. [DB]
*
******************************************************************************/

void Compute_CSG_BBox (Object)
OBJECT *Object;
{
  int i, count;
  DBL Old_Volume, New_Volume;
  VECTOR NewMin, NewMax, TmpMin, TmpMax, Min, Max;
  OBJECT *Sib;
  QUADRIC **Quadrics;

  if (Object->Methods == &CSG_Intersection_Methods)
  {
    /*
     * Calculate the bounding box of a CSG intersection
     * by intersecting the bounding boxes of all children.
     */

    Make_Vector(NewMin, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
    Make_Vector(NewMax,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);

    count = 0;

    Quadrics = NULL;

    /* Process all children. */

    for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
    {
      /* Inverted objects and height fields mustn't be considered */

      if (!Test_Flag(Sib, INVERTED_FLAG) && (Sib->Methods != &HField_Methods))
      {
        /* Store quadrics since they'll be processed last. */

        if (Sib->Methods == &Quadric_Methods)
        {
          Quadrics = (QUADRIC **)POV_REALLOC(Quadrics, (count+1)*sizeof(QUADRIC *), "temporary quadric list");

          Quadrics[count++] = (QUADRIC *)Sib;
        }
        else
        {
          if (Sib->Methods == &Plane_Methods)
          {
            Compute_Plane_Min_Max((PLANE *)Sib, TmpMin, TmpMax);
          }
          else
          {
            Make_min_max_from_BBox(TmpMin, TmpMax, Sib->BBox);
          }

          NewMin[X] = max(NewMin[X], TmpMin[X]);
          NewMin[Y] = max(NewMin[Y], TmpMin[Y]);
          NewMin[Z] = max(NewMin[Z], TmpMin[Z]);
          NewMax[X] = min(NewMax[X], TmpMax[X]);
          NewMax[Y] = min(NewMax[Y], TmpMax[Y]);
          NewMax[Z] = min(NewMax[Z], TmpMax[Z]);
        }
      }
    }

    /* Process any quadrics. */

    for (i = 0; i < count; i++)
    {
      Assign_Vector(Min, NewMin);
      Assign_Vector(Max, NewMax);

      Compute_Quadric_BBox(Quadrics[i], Min, Max);

      Make_min_max_from_BBox(TmpMin, TmpMax, Quadrics[i]->BBox);

      NewMin[X] = max(NewMin[X], TmpMin[X]);
      NewMin[Y] = max(NewMin[Y], TmpMin[Y]);
      NewMin[Z] = max(NewMin[Z], TmpMin[Z]);
      NewMax[X] = min(NewMax[X], TmpMax[X]);
      NewMax[Y] = min(NewMax[Y], TmpMax[Y]);
      NewMax[Z] = min(NewMax[Z], TmpMax[Z]);
    }

    if (Quadrics != NULL)
    {
      POV_FREE(Quadrics);
    }
  }
  else
  {
    /* Calculate the bounding box of a CSG merge/union object. */

    Make_Vector(NewMin,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
    Make_Vector(NewMax, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);

    for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
    {
      Make_min_max_from_BBox(TmpMin, TmpMax, Sib->BBox);

      NewMin[X] = min(NewMin[X], TmpMin[X]);
      NewMin[Y] = min(NewMin[Y], TmpMin[Y]);
      NewMin[Z] = min(NewMin[Z], TmpMin[Z]);
      NewMax[X] = max(NewMax[X], TmpMax[X]);
      NewMax[Y] = max(NewMax[Y], TmpMax[Y]);
      NewMax[Z] = max(NewMax[Z], TmpMax[Z]);
    }
  }

  if ((NewMin[X] > NewMax[X]) || (NewMin[Y] > NewMax[Y]) || (NewMin[Z] > NewMax[Z]))
  {
    Warning(0.0, "Degenerate CSG bounding box (not used!).\n");
  }
  else
  {
    New_Volume = (NewMax[X] - NewMin[X]) * (NewMax[Y] - NewMin[Y]) * (NewMax[Z] - NewMin[Z]);

    BOUNDS_VOLUME(Old_Volume, Object->BBox);

    if (New_Volume < Old_Volume)
    {
      Make_BBox_from_min_max(Object->BBox, NewMin, NewMax);

      /* Beware of bounding boxes to large. */

      if ((Object->BBox.Lengths[X] > CRITICAL_LENGTH) ||
          (Object->BBox.Lengths[Y] > CRITICAL_LENGTH) ||
          (Object->BBox.Lengths[Z] > CRITICAL_LENGTH))
      {
        Make_BBox(Object->BBox, -BOUND_HUGE/2, -BOUND_HUGE/2, -BOUND_HUGE/2,
          BOUND_HUGE, BOUND_HUGE, BOUND_HUGE);
      }
    }
  }
}