old/PAS/RayTracing/Src/BOXES.C

/****************************************************************************
*                boxes.c
*
*  This module implements the box primitive.
*  This file was written by Alexander Enzmann.  He wrote the code for
*  boxes and generously provided us these enhancements.
*
*  from Persistence of Vision(tm) Ray Tracer
*  Copyright 1996,1999 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 email to team-coord@povray.org or visit us on the web at
*  http://www.povray.org. The latest version of POV-Ray may be found at this site.
*
* 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 "boxes.h"
#include "matrices.h"
#include "objects.h"



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

/* Minimal intersection depth. */

#define DEPTH_TOLERANCE 1.0e-6

/* Two values are equal if their difference is small than CLOSE_TOLERANCE. */

#define CLOSE_TOLERANCE 1.0e-6

/* Side hit. */

#define SIDE_X_0 1
#define SIDE_X_1 2
#define SIDE_Y_0 3
#define SIDE_Y_1 4
#define SIDE_Z_0 5
#define SIDE_Z_1 6



/*****************************************************************************
* Static functions
******************************************************************************/
static int  All_Box_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack);
static int  Inside_Box (VECTOR point, OBJECT *Object);
static void Box_Normal (VECTOR Result, OBJECT *Object, INTERSECTION *Inter);
static void Translate_Box (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
static void Rotate_Box (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
static void Scale_Box (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
static void Transform_Box (OBJECT *Object, TRANSFORM *Trans);
static void Invert_Box (OBJECT *Object);



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

METHODS Box_Methods =
{
  All_Box_Intersections,
  Inside_Box, Box_Normal,
  (COPY_METHOD)Copy_Box, Translate_Box, Rotate_Box, Scale_Box, Transform_Box,
  Invert_Box, Destroy_Box
};



/*****************************************************************************
*
* FUNCTION
*
*   All_Box_Intersections
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static int All_Box_Intersections(OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack)
{
  int Intersection_Found;
  int Side1, Side2;
  DBL Depth1, Depth2;
  VECTOR IPoint;

  Increase_Counter(stats[Ray_Box_Tests]);

  Intersection_Found = FALSE;

  if (Intersect_Box(Ray, (BOX *)Object, &Depth1, &Depth2, &Side1, &Side2))
  {
    if (Depth1 > DEPTH_TOLERANCE)
    {
      VEvaluateRay(IPoint, Ray->Initial, Depth1, Ray->Direction);

      if (Point_In_Clip(IPoint, Object->Clip))
      {
        push_entry_i1(Depth1,IPoint,Object,Side1,Depth_Stack);

        Intersection_Found = TRUE;
      }
    }

    VEvaluateRay(IPoint, Ray->Initial, Depth2, Ray->Direction);

    if (Point_In_Clip(IPoint, Object->Clip))
    {
      push_entry_i1(Depth2,IPoint,Object,Side2,Depth_Stack);

      Intersection_Found = TRUE;
    }
  }

  if (Intersection_Found)
  {
    Increase_Counter(stats[Ray_Box_Tests_Succeeded]);
  }

  return (Intersection_Found);
}



/*****************************************************************************
*
* FUNCTION
*
*   Intersect_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   Sep 1994 : Added code to decide which side was hit in the case
*              intersection points are close to each other. This removes
*              some ugly artefacts one could observe at the corners of
*              boxes due to the usage of the wrong normal vector. [DB]
*
******************************************************************************/

int Intersect_Box(RAY *Ray, BOX *box, DBL *Depth1, DBL  *Depth2, int *Side1, int  *Side2)
{
  int smin = 0, smax = 0;    /* Side hit for min/max intersection. */
  DBL t, tmin, tmax;
  VECTOR P, D;

  /* Transform the point into the boxes space */

  if (box->Trans != NULL)
  {
    MInvTransPoint(P, Ray->Initial, box->Trans);
    MInvTransDirection(D, Ray->Direction, box->Trans);
  }
  else
  {
    Assign_Vector(P, Ray->Initial);
    Assign_Vector(D, Ray->Direction);
  }

  tmin = 0.0;
  tmax = BOUND_HUGE;

  /*
   * Sides first.
   */

  if (D[X] < -EPSILON)
  {
    t = (box->bounds[0][X] - P[X]) / D[X];

    if (t < tmin) return(FALSE);

    if (t <= tmax)
    {
      smax = SIDE_X_0;
      tmax = t;
    }

    t = (box->bounds[1][X] - P[X]) / D[X];

    if (t >= tmin)
    {
      if (t > tmax) return(FALSE);

      smin = SIDE_X_1;
      tmin = t;
    }
  }
  else
  {
    if (D[X] > EPSILON)
    {
      t = (box->bounds[1][X] - P[X]) / D[X];

      if (t < tmin) return(FALSE);

      if (t <= tmax)
      {
        smax = SIDE_X_1;
        tmax = t;
      }

      t = (box->bounds[0][X] - P[X]) / D[X];

      if (t >= tmin)
      {
        if (t > tmax) return(FALSE);

        smin = SIDE_X_0;
        tmin = t;
      }
    }
    else
    {
      if ((P[X] < box->bounds[0][X]) || (P[X] > box->bounds[1][X]))
      {
        return(FALSE);
      }
    }
  }

  /*
   * Check Top/Bottom.
   */

  if (D[Y] < -EPSILON)
  {
    t = (box->bounds[0][Y] - P[Y]) / D[Y];

    if (t < tmin) return(FALSE);

    if (t <= tmax - CLOSE_TOLERANCE)
    {
      smax = SIDE_Y_0;
      tmax = t;
    }
    else
    {
      /*
       * If intersection points are close to each other find out
       * which side to use, i.e. is most probably hit. [DB 9/94]
       */

      if (t <= tmax + CLOSE_TOLERANCE)
      {
        if (-D[Y] > fabs(D[X])) smax = SIDE_Y_0;
      }
    }

    t = (box->bounds[1][Y] - P[Y]) / D[Y];

    if (t >= tmin + CLOSE_TOLERANCE)
    {
      if (t > tmax) return(FALSE);

      smin = SIDE_Y_1;
      tmin = t;
    }
    else
    {
      /*
       * If intersection points are close to each other find out
       * which side to use, i.e. is most probably hit. [DB 9/94]
       */

      if (t >= tmin - CLOSE_TOLERANCE)
      {
        if (-D[Y] > fabs(D[X])) smin = SIDE_Y_1;
      }
    }
  }
  else
  {
    if (D[Y] > EPSILON)
    {
      t = (box->bounds[1][Y] - P[Y]) / D[Y];

      if (t < tmin) return(FALSE);

      if (t <= tmax - CLOSE_TOLERANCE)
      {
        smax = SIDE_Y_1;
        tmax = t;
      }
      else
      {
        /*
         * If intersection points are close to each other find out
         * which side to use, i.e. is most probably hit. [DB 9/94]
         */

        if (t <= tmax + CLOSE_TOLERANCE)
        {
          if (D[Y] > fabs(D[X])) smax = SIDE_Y_1;
        }
      }

      t = (box->bounds[0][Y] - P[Y]) / D[Y];

      if (t >= tmin + CLOSE_TOLERANCE)
      {
        if (t > tmax) return(FALSE);

        smin = SIDE_Y_0;
        tmin = t;
      }
      else
      {
        /*
         * If intersection points are close to each other find out
         * which side to use, i.e. is most probably hit. [DB 9/94]
         */

        if (t >= tmin - CLOSE_TOLERANCE)
        {
          if (D[Y] > fabs(D[X])) smin = SIDE_Y_0;
        }
      }
    }
    else
    {
      if ((P[Y] < box->bounds[0][Y]) || (P[Y] > box->bounds[1][Y]))
      {
        return(FALSE);
      }
    }
  }

  /* Now front/back */

  if (D[Z] < -EPSILON)
  {
    t = (box->bounds[0][Z] - P[Z]) / D[Z];

    if (t < tmin) return(FALSE);

    if (t <= tmax - CLOSE_TOLERANCE)
    {
      smax = SIDE_Z_0;
      tmax = t;
    }
    else
    {
      /*
       * If intersection points are close to each other find out
       * which side to use, i.e. is most probably hit. [DB 9/94]
       */

      if (t <= tmax + CLOSE_TOLERANCE)
      {
        switch (smax)
        {
          case SIDE_X_0 :
          case SIDE_X_1 : if (-D[Z] > fabs(D[X])) smax = SIDE_Z_0; break;

          case SIDE_Y_0 :
          case SIDE_Y_1 : if (-D[Z] > fabs(D[Y])) smax = SIDE_Z_0; break;
        }
      }
    }

    t = (box->bounds[1][Z] - P[Z]) / D[Z];

    if (t >= tmin + CLOSE_TOLERANCE)
    {
      if (t > tmax) return(FALSE);

      smin = SIDE_Z_1;
      tmin = t;
    }
    else
    {
      /*
       * If intersection points are close to each other find out
       * which side to use, i.e. is most probably hit. [DB 9/94]
       */

      if (t >= tmin - CLOSE_TOLERANCE)
      {
        switch (smin)
        {
          case SIDE_X_0 :
          case SIDE_X_1 : if (-D[Z] > fabs(D[X])) smin = SIDE_Z_1; break;

          case SIDE_Y_0 :
          case SIDE_Y_1 : if (-D[Z] > fabs(D[Y])) smin = SIDE_Z_1; break;
        }
      }
    }
  }
  else
  {
    if (D[Z] > EPSILON)
    {
      t = (box->bounds[1][Z] - P[Z]) / D[Z];

      if (t < tmin) return(FALSE);

      if (t <= tmax - CLOSE_TOLERANCE)
      {
        smax = SIDE_Z_1;
        tmax = t;
      }
      else
      {
        /*
         * If intersection points are close to each other find out
         * which side to use, i.e. is most probably hit. [DB 9/94]
         */

        if (t <= tmax + CLOSE_TOLERANCE)
        {
          switch (smax)
          {
            case SIDE_X_0 :
            case SIDE_X_1 : if (D[Z] > fabs(D[X])) smax = SIDE_Z_1; break;

            case SIDE_Y_0 :
            case SIDE_Y_1 : if (D[Z] > fabs(D[Y])) smax = SIDE_Z_1; break;
          }
        }
      }

      t = (box->bounds[0][Z] - P[Z]) / D[Z];

      if (t >= tmin + CLOSE_TOLERANCE)
      {
        if (t > tmax) return(FALSE);

        smin = SIDE_Z_0;
        tmin = t;
      }
      else
      {
        /*
         * If intersection points are close to each other find out
         * which side to use, i.e. is most probably hit. [DB 9/94]
         */

        if (t >= tmin - CLOSE_TOLERANCE)
        {
          switch (smin)
          {
            case SIDE_X_0 :
            case SIDE_X_1 : if (D[Z] > fabs(D[X])) smin = SIDE_Z_0; break;

            case SIDE_Y_0 :
            case SIDE_Y_1 : if (D[Z] > fabs(D[Y])) smin = SIDE_Z_0; break;
          }
        }
      }
    }
    else
    {
      if ((P[Z] < box->bounds[0][Z]) || (P[Z] > box->bounds[1][Z]))
      {
        return(FALSE);
      }
    }
  }

  if (tmax < DEPTH_TOLERANCE)
  {
    return (FALSE);
  }

  *Depth1 = tmin;
  *Depth2 = tmax;

  *Side1 = smin;
  *Side2 = smax;

  return(TRUE);
}



/*****************************************************************************
*
* FUNCTION
*
*   Inside_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static int Inside_Box(VECTOR IPoint, OBJECT *Object)
{
  VECTOR New_Point;
  BOX *box = (BOX *) Object;

  /* Transform the point into box space. */

  if (box->Trans != NULL)
  {
    MInvTransPoint(New_Point, IPoint, box->Trans);
  }
  else
  {
    Assign_Vector(New_Point,IPoint);
  }

  /* Test to see if we are outside the box. */

  if ((New_Point[X] < box->bounds[0][X]) || (New_Point[X] > box->bounds[1][X]))
  {
    return (Test_Flag(box, INVERTED_FLAG));
  }

  if ((New_Point[Y] < box->bounds[0][Y]) || (New_Point[Y] > box->bounds[1][Y]))
  {
    return (Test_Flag(box, INVERTED_FLAG));
  }

  if ((New_Point[Z] < box->bounds[0][Z]) || (New_Point[Z] > box->bounds[1][Z]))
  {
    return (Test_Flag(box, INVERTED_FLAG));
  }

  /* Inside the box. */

  return (!Test_Flag(box, INVERTED_FLAG));
}



/*****************************************************************************
*
* FUNCTION
*
*   Box_Normal
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Box_Normal(VECTOR Result, OBJECT *Object, INTERSECTION *Inter)
{
  switch (Inter->i1)
  {
    case SIDE_X_0: Make_Vector(Result, -1.0,  0.0,  0.0); break;
    case SIDE_X_1: Make_Vector(Result,  1.0,  0.0,  0.0); break;
    case SIDE_Y_0: Make_Vector(Result,  0.0, -1.0,  0.0); break;
    case SIDE_Y_1: Make_Vector(Result,  0.0,  1.0,  0.0); break;
    case SIDE_Z_0: Make_Vector(Result,  0.0,  0.0, -1.0); break;
    case SIDE_Z_1: Make_Vector(Result,  0.0,  0.0,  1.0); break;

    default: Error("Unknown box side in Box_Normal().\n");
  }

  /* Transform the point into the boxes space. */

  if (((BOX *)Object)->Trans != NULL)
  {
    MTransNormal(Result, Result, ((BOX *)Object)->Trans);

    VNormalize(Result, Result);
  }
}



/*****************************************************************************
*
* FUNCTION
*
*   Translate_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Translate_Box(OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
{
  if (((BOX *)Object)->Trans == NULL)
  {
    VAddEq(((BOX *)Object)->bounds[0], Vector);

    VAddEq(((BOX *)Object)->bounds[1], Vector);

    Compute_Box_BBox((BOX *)Object);
  }
  else
  {
    Transform_Box(Object, Trans);
  }
}



/*****************************************************************************
*
* FUNCTION
*
*   Rotate_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Rotate_Box(OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
{
  Transform_Box(Object, Trans);
}



/*****************************************************************************
*
* FUNCTION
*
*   Scale_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Scale_Box(OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
{
  DBL temp;
  BOX *Box = (BOX *)Object;

  if (((BOX *)Object)->Trans == NULL)
  {
    VEvaluateEq(Box->bounds[0], Vector);
    VEvaluateEq(Box->bounds[1], Vector);

    if (Box->bounds[0][X] > Box->bounds[1][X])
    {
      temp = Box->bounds[0][X];

      Box->bounds[0][X] = Box->bounds[1][X];
      Box->bounds[1][X] = temp;
    }

    if (Box->bounds[0][Y] > Box->bounds[1][Y])
    {
      temp = Box->bounds[0][Y];

      Box->bounds[0][Y] = Box->bounds[1][Y];
      Box->bounds[1][Y] = temp;
    }

    if (Box->bounds[0][Z] > Box->bounds[1][Z])
    {
      temp = Box->bounds[0][Z];

      Box->bounds[0][Z] = Box->bounds[1][Z];
      Box->bounds[1][Z] = temp;
    }

    Compute_Box_BBox((BOX *)Object);
  }
  else
  {
    Transform_Box(Object, Trans);
  }
}



/*****************************************************************************
*
* FUNCTION
*
*   Invert_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Invert_Box(OBJECT *Object)
{
  Invert_Flag(Object, INVERTED_FLAG);
}



/*****************************************************************************
*
* FUNCTION
*
*   Transform_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Transform_Box(OBJECT *Object, TRANSFORM *Trans)
{
  BOX *box = (BOX *)Object;

  if (box->Trans == NULL)
  {
    box->Trans = Create_Transform();
  }

  Compose_Transforms(box->Trans, Trans);

  Compute_Box_BBox(box);
}



/*****************************************************************************
*
* FUNCTION
*
*   Create_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

BOX *Create_Box()
{
  BOX *New;

  New = (BOX *)POV_MALLOC(sizeof(BOX), "box");

  INIT_OBJECT_FIELDS(New, BOX_OBJECT, &Box_Methods)

  Make_Vector(New->bounds[0], -1.0, -1.0, -1.0);
  Make_Vector(New->bounds[1],  1.0,  1.0,  1.0);

  Make_BBox(New->BBox, -1.0, -1.0, -1.0, 2.0, 2.0, 2.0);

  New->Trans = NULL;

  return (New);
}



/*****************************************************************************
*
* FUNCTION
*
*   Copy_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

BOX *Copy_Box(OBJECT *Object)
{
  BOX *New;

  New  = Create_Box();

  /* Copy box. */

  *New = *((BOX *)Object);

  New->Trans = Copy_Transform(((BOX *)Object)->Trans);

  return (New);
}



/*****************************************************************************
*
* FUNCTION
*
*   Destroy_Box
*
* INPUT
*
* OUTPUT
*
* RETURNS
*
* AUTHOR
*
*   Alexander Enzmann
*
* DESCRIPTION
*
*   -
*
* CHANGES
*
*   -
*
******************************************************************************/

void Destroy_Box(OBJECT *Object)
{
  Destroy_Transform(((BOX *)Object)->Trans);

  POV_FREE (Object);
}



/*****************************************************************************
*
* FUNCTION
*
*   Compute_Box_BBox
*
* INPUT
*
*   Box - Box
*
* OUTPUT
*
*   Box
*
* RETURNS
*
* AUTHOR
*
*   Dieter Bayer
*
* DESCRIPTION
*
*   Calculate the bounding box of a box.
*
* CHANGES
*
*   Aug 1994 : Creation.
*
******************************************************************************/

void Compute_Box_BBox(BOX *Box)
{
  Assign_BBox_Vect(Box->BBox.Lower_Left, Box->bounds[0]);

  VSub(Box->BBox.Lengths, Box->bounds[1], Box->bounds[0]);

  if (Box->Trans != NULL)
  {
    Recompute_BBox(&Box->BBox, Box->Trans);
  }
}