/****************************************************************************
 *                  vlbuffer.cpp
 *
 * 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 version 3.6.
 * Copyright 1991-2003 Persistence of Vision Team
 * Copyright 2003-2004 Persistence of Vision Raytracer Pty. Ltd.
 *---------------------------------------------------------------------------
 * 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 developers. There are strict rules
 * regarding how you are permitted to use this file. These rules are contained
 * in the distribution and derivative versions licenses which should have been
 * provided with this file.
 *
 * These licences may be found online, linked from the end-user license
 * agreement that is located at http://www.povray.org/povlegal.html
 *---------------------------------------------------------------------------
 * 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.
 *---------------------------------------------------------------------------
 * $File: //depot/povray/3.6-release/source/vlbuffer.cpp $
 * $Revision: #3 $
 * $Change: 3032 $
 * $DateTime: 2004/08/02 18:43:41 $
 * $Author: chrisc $
 * $Log$
 *****************************************************************************/

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

BEGIN_POV_NAMESPACE

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

const int INITIAL_NUMBER_OF_ENTRIES = 256;


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



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

/* Tree node queue. */

PROJECT_QUEUE *Node_Queue; // GLOBAL VARIABLE

/* Priority queue. */

PRIORITY_QUEUE *VLBuffer_Queue; // GLOBAL VARIABLE



/*****************************************************************************
* 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.");
    }

    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(VECTOR *Points, int *PointCnt, const VECTOR VX1, const VECTOR  VX2, const VECTOR  VY1, const VECTOR  VY2, const DBL DX1, const DBL  DX2, const DBL  DY1, const DBL  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(PROJECT_TREE_NODE *Node)
{
  unsigned short i;

  if (Node->is_leaf & true)
  {
    Do_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);
  }
}

END_POV_NAMESPACE
