/****************************************************************************
*                   vlbuffer.c
*
*  This module implements functions that are used by the vista/light buffer.
*
*  This module was written by Dieter Bayer [DB].
*
*  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.
*
*****************************************************************************/

/****************************************************************************
*
*  Explanation:
*
*    -
*
*  ---
*
*  Mar 1994 : Creation.
*
*****************************************************************************/

#include "frame.h"
#include "vector.h"
#include "povproto.h"
#include "bbox.h"
#include "vlbuffer.h"



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

#define INITIAL_NUMBER_OF_ENTRIES 256


/*****************************************************************************
* Local typedefs
******************************************************************************/



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

/* Tree node queue. */

PROJECT_QUEUE *Node_Queue;

/* Priority queue. */

PRIORITY_QUEUE *VLBuffer_Queue;



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



/*****************************************************************************
*
* FUNCTION
*
*   Initialize_VLBuffer_Code
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*   
* AUTHOR
*
*   Dieter Bayer
*   
* DESCRIPTION
*
*   Init queues used by the light and vista buffer.
*
* CHANGES
*
*   May 1994 : Creation.
*
******************************************************************************/

void Initialize_VLBuffer_Code()
{
  Node_Queue = (PROJECT_QUEUE *)POV_MALLOC(sizeof(PROJECT_QUEUE),
    "vista/light buffer node queue");

  Node_Queue->QSize = 0;

  Node_Queue->Max_QSize = INITIAL_NUMBER_OF_ENTRIES;

  Node_Queue->Queue = (PROJECT_TREE_NODE **)POV_MALLOC(Node_Queue->Max_QSize*sizeof(PROJECT_TREE_NODE *),
    "vista/light buffer node queue");

  VLBuffer_Queue = Create_Priority_Queue(INITIAL_NUMBER_OF_ENTRIES);
}



/*****************************************************************************
*
* FUNCTION
*
*   Reinitialize_VLBuffer_Code
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*   
* AUTHOR
*
*   Dieter Bayer
*   
* DESCRIPTION
*
*   Reinit queues used by the light and vista buffer.
*
*   Note that only the node queue needs to be reinitialized.
*
* CHANGES
*
*   Feb 1995 : Creation.
*
******************************************************************************/

void Reinitialize_VLBuffer_Code()
{
  if (Node_Queue->QSize >= Node_Queue->Max_QSize)
  {
    if (Node_Queue->QSize >= INT_MAX/2)
    {
      Error("Node queue overflow.\n");
    }

    Node_Queue->Max_QSize *= 2;

    Node_Queue->Queue = (PROJECT_TREE_NODE **)POV_REALLOC(Node_Queue->Queue,
      Node_Queue->Max_QSize*sizeof(PROJECT_TREE_NODE *),
      "vista/light buffer node queue");
  }
}



/*****************************************************************************
*
* FUNCTION
*
*   Deinitialize_VLBuffer_Code
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*   
* AUTHOR
*
*   Dieter Bayer
*   
* DESCRIPTION
*
*   Deinit queues used by the light and vista buffer.
*
* CHANGES
*
*   May 1994 : Creation.
*
******************************************************************************/

void Deinitialize_VLBuffer_Code()
{
  if (Node_Queue != NULL)
{
    POV_FREE(Node_Queue->Queue);

    POV_FREE(Node_Queue);
  }

  if (VLBuffer_Queue != NULL)
  {
    Destroy_Priority_Queue(VLBuffer_Queue);
  }

  Node_Queue     = NULL;
  VLBuffer_Queue = NULL;
}



/*****************************************************************************
*
* FUNCTION
*
*   Clip_Polygon
*
* INPUT
*
*   Points             - polygon's points
*   PointCnt           - Number of points in polygon
*   VX1, VY1, VX2, VY1 - Normal vectors of the clipping planes
*   DX1, DY1, DX2, DY2 - Distances of the clipping planes from
*   the origin
*   
* OUTPUT
*
*   Points, PointCnt
*   
* RETURNS
*   
* AUTHOR
*
*   Dieter Bayer
*   
* DESCRIPTION
*
*   Clip polygon at the viewing pyramid define by the normal vectors
*   VX1, VX2, VY1, VY2 and the distances DX1, DX2, DY1, DY2.
*
* CHANGES
*
*   May 1994 : Creation.
*
******************************************************************************/

void Clip_Polygon(Points, PointCnt, VX1, VX2, VY1, VY2, DX1, DX2, DY1, DY2)
VECTOR *Points;
int *PointCnt;
VECTOR VX1, VX2, VY1, VY2;
DBL DX1, DX2, DY1, DY2;
{
  DBL aktd, pred, fird, k;
  VECTOR aktP, intP, preP, firP, d;
  int i, pc;
  VECTOR ClipPoints[MAX_CLIP_POINTS];

  /********** clip polygon at "left" plane **********/

  pc = 0;

  Assign_Vector(firP, Points[0]);

  fird = VX1[X] * firP[X] + VX1[Y] * firP[Y] + VX1[Z] * firP[Z] - DX1;

  if (fird <= 0.0)
  {
    Assign_Vector(ClipPoints[pc++], firP);
  }

  Assign_Vector(aktP, firP);
  Assign_Vector(preP, firP);

  aktd = pred = fird;

  for (i = 1; i < *PointCnt; i++)
  {
    Assign_Vector(aktP, Points[i]);

    aktd = VX1[X] * aktP[X] + VX1[Y] * aktP[Y] + VX1[Z] * aktP[Z] - DX1;

    if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0)))
    {
      d[X] = preP[X] - aktP[X];
      d[Y] = preP[Y] - aktP[Y];
      d[Z] = preP[Z] - aktP[Z];

      k = -aktd / (VX1[X] * d[X] + VX1[Y] * d[Y] + VX1[Z] * d[Z]);

      intP[X] = aktP[X] + k * d[X];
      intP[Y] = aktP[Y] + k * d[Y];
      intP[Z] = aktP[Z] + k * d[Z];

      Assign_Vector(ClipPoints[pc++], intP);
    }

    if (aktd <= 0.0)
    {
      Assign_Vector(ClipPoints[pc++], aktP);
    }

    Assign_Vector(preP, aktP);

    pred = aktd;
  }

  if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0)))
  {
    d[X] = firP[X] - aktP[X];
    d[Y] = firP[Y] - aktP[Y];
    d[Z] = firP[Z] - aktP[Z];

    k = -aktd / (VX1[X] * d[X] + VX1[Y] * d[Y] + VX1[Z] * d[Z]);

    intP[X] = aktP[X] + k * d[X];
    intP[Y] = aktP[Y] + k * d[Y];
    intP[Z] = aktP[Z] + k * d[Z];

    Assign_Vector(ClipPoints[pc++], intP);
  }

  for (i = 0; i < pc; i++)
  {
    Assign_Vector(Points[i], ClipPoints[i]);
  }

  if ((*PointCnt = pc) == 0)
    return;

  /********** clip polygon at "right" plane **********/

  pc = 0;

  Assign_Vector(firP, Points[0]);

  fird = VX2[X] * firP[X] + VX2[Y] * firP[Y] + VX2[Z] * firP[Z] - DX2;

  if (fird <= 0.0)
  {
    Assign_Vector(ClipPoints[pc++], firP);
  }

  Assign_Vector(aktP, firP);
  Assign_Vector(preP, firP);

  aktd = pred = fird;

  for (i = 1; i < *PointCnt; i++)
  {
    Assign_Vector(aktP, Points[i]);

    aktd = VX2[X] * aktP[X] + VX2[Y] * aktP[Y] + VX2[Z] * aktP[Z] - DX2;

    if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0)))
    {
      d[X] = preP[X] - aktP[X];
      d[Y] = preP[Y] - aktP[Y];
      d[Z] = preP[Z] - aktP[Z];

      k = -aktd / (VX2[X] * d[X] + VX2[Y] * d[Y] + VX2[Z] * d[Z]);

      intP[X] = aktP[X] + k * d[X];
      intP[Y] = aktP[Y] + k * d[Y];
      intP[Z] = aktP[Z] + k * d[Z];

      Assign_Vector(ClipPoints[pc++], intP);
    }

    if (aktd <= 0.0)
    {
      Assign_Vector(ClipPoints[pc++], aktP);
    }

    Assign_Vector(preP, aktP);

    pred = aktd;
  }

  if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0)))
  {
    d[X] = firP[X] - aktP[X];
    d[Y] = firP[Y] - aktP[Y];
    d[Z] = firP[Z] - aktP[Z];

    k = -aktd / (VX2[X] * d[X] + VX2[Y] * d[Y] + VX2[Z] * d[Z]);

    intP[X] = aktP[X] + k * d[X];
    intP[Y] = aktP[Y] + k * d[Y];
    intP[Z] = aktP[Z] + k * d[Z];

    Assign_Vector(ClipPoints[pc++], intP);
  }

  for (i = 0; i < pc; i++)
  {
    Assign_Vector(Points[i], ClipPoints[i]);
  }

  if ((*PointCnt = pc) == 0)
    return;

  /********** clip polygon at "bottom" plane **********/

  pc = 0;

  Assign_Vector(firP, Points[0]);

  fird = VY1[X] * firP[X] + VY1[Y] * firP[Y] + VY1[Z] * firP[Z] - DY1;

  if (fird <= 0.0)
  {
    Assign_Vector(ClipPoints[pc++], firP);
  }

  Assign_Vector(aktP, firP);
  Assign_Vector(preP, firP);

  aktd = pred = fird;

  for (i = 1; i < *PointCnt; i++)
  {
    Assign_Vector(aktP, Points[i]);

    aktd = VY1[X] * aktP[X] + VY1[Y] * aktP[Y] + VY1[Z] * aktP[Z] - DY1;

    if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0)))
    {
      d[X] = preP[X] - aktP[X];
      d[Y] = preP[Y] - aktP[Y];
      d[Z] = preP[Z] - aktP[Z];

      k = -aktd / (VY1[X] * d[X] + VY1[Y] * d[Y] + VY1[Z] * d[Z]);

      intP[X] = aktP[X] + k * d[X];
      intP[Y] = aktP[Y] + k * d[Y];
      intP[Z] = aktP[Z] + k * d[Z];

      Assign_Vector(ClipPoints[pc++], intP);
    }

    if (aktd <= 0.0)
    {
      Assign_Vector(ClipPoints[pc++], aktP);
    }

    Assign_Vector(preP, aktP);

    pred = aktd;
  }

  if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0)))
  {
    d[X] = firP[X] - aktP[X];
    d[Y] = firP[Y] - aktP[Y];
    d[Z] = firP[Z] - aktP[Z];

    k = -aktd / (VY1[X] * d[X] + VY1[Y] * d[Y] + VY1[Z] * d[Z]);

    intP[X] = aktP[X] + k * d[X];
    intP[Y] = aktP[Y] + k * d[Y];
    intP[Z] = aktP[Z] + k * d[Z];

    Assign_Vector(ClipPoints[pc++], intP);
  }

  for (i = 0; i < pc; i++)
  {
    Assign_Vector(Points[i], ClipPoints[i]);
  }

  if ((*PointCnt = pc) == 0)
    return;

  /********** clip polygon at "top" plane **********/

  pc = 0;

  Assign_Vector(firP, Points[0]);

  fird = VY2[X] * firP[X] + VY2[Y] * firP[Y] + VY2[Z] * firP[Z] - DY2;

  if (fird <= 0.0)
  {
    Assign_Vector(ClipPoints[pc++], firP);
  }

  Assign_Vector(aktP, firP);
  Assign_Vector(preP, firP);

  aktd = pred = fird;

  for (i = pc = 0; i < *PointCnt; i++)
  {
    Assign_Vector(aktP, Points[i]);

    aktd = VY2[X] * aktP[X] + VY2[Y] * aktP[Y] + VY2[Z] * aktP[Z] - DY2;

    if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0)))
    {
      d[X] = preP[X] - aktP[X];
      d[Y] = preP[Y] - aktP[Y];
      d[Z] = preP[Z] - aktP[Z];

      k = -aktd / (VY2[X] * d[X] + VY2[Y] * d[Y] + VY2[Z] * d[Z]);

      intP[X] = aktP[X] + k * d[X];
      intP[Y] = aktP[Y] + k * d[Y];
      intP[Z] = aktP[Z] + k * d[Z];

      Assign_Vector(ClipPoints[pc++], intP);
    }

    if (aktd <= 0.0)
    {
      Assign_Vector(ClipPoints[pc++], aktP);
    }

    Assign_Vector(preP, aktP);

    pred = aktd;
  }

  if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0)))
  {
    d[X] = firP[X] - aktP[X];
    d[Y] = firP[Y] - aktP[Y];
    d[Z] = firP[Z] - aktP[Z];

    k = -aktd / (VY2[X] * d[X] + VY2[Y] * d[Y] + VY2[Z] * d[Z]);

    intP[X] = aktP[X] + k * d[X];
    intP[Y] = aktP[Y] + k * d[Y];
    intP[Z] = aktP[Z] + k * d[Z];

    Assign_Vector(ClipPoints[pc++], intP);
  }

  for (i = 0; i < pc; i++)
  {
    Assign_Vector(Points[i], ClipPoints[i]);
  }

  *PointCnt = pc;
}



/*****************************************************************************
*
* FUNCTION
*
*   Destroy_Project_Tree
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*   
* AUTHOR
*
*   Dieter Bayer
*   
* DESCRIPTION
*
*   Recursively destroy a node in a projection (i.e. vista/light) tree.
*
* CHANGES
*
*   Sep 1994 : Creation.
*
*   Dec 1994 : Fixed memory leakage due to pruned branches. [DB]
*   Mar 1996 : Added COOPERATE for GUIs. [esp]
*
******************************************************************************/

void Destroy_Project_Tree(Node)
PROJECT_TREE_NODE *Node;
{
  unsigned short i;

  if (Node->is_leaf & TRUE)
  {
    COOPERATE_1
    POV_FREE(Node);
  }
  else
  {
    for (i = 0; i < Node->Entries; i++)
    {
      Destroy_Project_Tree(Node->Entry[i]);
    }

    POV_FREE(Node->Entry);

    POV_FREE(Node);
  }
}