/****************************************************************************
*
*  ATTENTION!!!
*
*  THIS FILE HAS BEEN MODIFIED!!! IT IS NOT PART OF THE OFFICAL
*  POV-RAY 2.2 DISTRIBUTION!!!
*
*  THIS FILE IS PART OF "FASTER THAN POV-RAY" (VERSION 1.1),
*  A SPED-UP VERSION OF POV-RAY 2.2. USE AT YOUR OWN RISK!!!!!!
*
*  New files: addon0.c, addon1.c, addon2.c, addon3.c, addon.h
*
*  The additional modules were written by Dieter Bayer.
*
*  Send comments, suggestions, bugs, ideas ... to:
*
*  dieter@cip.e-technik.uni-erlangen.de
*
*  All changed/added lines are enclosed in #ifdef DB_CODE ... #endif
*
*  The vista projection was taken from:
*
*    A. Hashimoto, T. Akimoto, K. Mase, and Y. Suenaga, 
*    "Vista Ray-Tracing: High Speed Ray Tracing Using Perspective
*    Projection Image", New Advances in Computer Graphics, Proceedings
*    of CG International '89, R. A. Earnshaw, B. Wyvill (Eds.), 
*    Springer, ..., pp. 549-560
*
*  The idea for the light buffer was taken from:
*
*    E. Haines and D. Greenberg, "The Light Buffer: A Shadow-Testing 
*    Accelerator", IEEE CG&A, Vol. 6, No. 9, Sept. 1986, pp. 6-16
*
*****************************************************************************/

/*****************************************************************************
*  addon0.c
*
*  This module was written by Dieter Bayer.
*
*  This module contains functions for initialisation, statistics, previewing,
*  and other gegeneral purposes.
*
*  01.03.1994 : Creation
*
*  29.04.1994 : Version 2.0
*
******************************************************************************/

#include <time.h>
#include "frame.h"
#include "vector.h"
#include "povproto.h"
#include "addon.h"

#ifdef DB_CODE

#define RED 0
#define GREEN 1
#define BLUE 2

#define NUMBER_OF_TYPES      19
#define TYPE_BICUBIC_PATCH    0
#define TYPE_BLOB             1
#define TYPE_BOX              2
#define TYPE_CONE             3
#define TYPE_CSG_INTERSECTION 4
#define TYPE_CSG_MERGE        5
#define TYPE_CSG_UNION        6
#define TYPE_DISC             7
#define TYPE_ELLIPSOID        8
#define TYPE_HEIGHT_FIELD     9
#define TYPE_LIGHT_SOURCE    10
#define TYPE_PLANE           11
#define TYPE_POLY            12
#define TYPE_POLYGON         13
#define TYPE_QUADRIC         14
#define TYPE_SMOOTH_TRIANGLE 15
#define TYPE_SPHERE          16
#define TYPE_TRIANGLE        17
#define TYPE_UNKNOWN         18

#define NUMBER_OF_FLAGS     7
#define FLAG_SUM            0
#define FLAG_INFINITE       1
#define FLAG_USED_IN_CSG    2
#define FLAG_BOUNDED        3
#define FLAG_CLIPPED        4
#define FLAG_BOUND_OBJECT   5
#define FLAG_CLIP_OBJECT    6



/*****************************************************************************
* External variables
******************************************************************************/

extern FRAME Frame;
extern unsigned int Options;
extern METHODS Ellipsoid_Methods;
extern METHODS Sphere_Methods;
extern time_t tstart, tstop;
extern int Use_Slabs;
extern unsigned long Quality_Flags;

extern METHODS Bicubic_Patch_Methods;
extern METHODS Blob_Methods;
extern METHODS Box_Methods;
extern METHODS Cone_Methods;
extern METHODS Csg_Height_Field_Methods;
extern METHODS CSG_Intersection_Methods;
extern METHODS CSG_Merge_Methods;
extern METHODS CSG_Union_Methods;
extern METHODS Disc_Methods;
extern METHODS Ellipsoid_Methods;
extern METHODS Height_Field_Methods;
extern METHODS Light_Source_Methods;
extern METHODS Plane_Methods;
extern METHODS Poly_Methods;
extern METHODS Quadric_Methods;
extern METHODS Smooth_Triangle_Methods;
extern METHODS Sphere_Methods;
extern METHODS Triangle_Methods;

extern PROJECT_TREE_NODE *Root_Vista;

extern size_t Mem_Polygon;



/*****************************************************************************
* Global variables
******************************************************************************/

unsigned int Extended_Options = 0;

/* Amount of memory occupied by the vista buffer and light buffers */

size_t Mem_Vista_Buffer  = 0;
size_t Mem_Light_Buffers = 0;
size_t Allocated_Memory  = 0;



/*****************************************************************************
* Static variables
******************************************************************************/

static int Point_Counter;

static DBL time_used1, time_used2;

static long counter[NUMBER_OF_TYPES][NUMBER_OF_FLAGS];



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

static int Get_Object_Type PARAMS((OBJECT *Object));
static void Print_Object_Info PARAMS((int type));
static void Get_Object_Stats PARAMS((OBJECT *Object, int Csg, int Bound_Object, int Clip_Object));
static void Print_Object_Stats PARAMS((void));

static void Draw_Projection PARAMS((PROJECT *Project, int color));
static void Draw_Vista PARAMS((PROJECT_TREE_NODE *Tree));



/*****************************************************************************
*
* FUNCTION      : VB_malloc
*
* ARGUMENTS     : size   - Amount of memory to allocate
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : void * - Pointer at allocated memory
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Allocate memory for the vista buffer and keep track of the memory allocated.
*
* CHANGES
*
*   -
*
******************************************************************************/

void *VB_malloc(size)
size_t size;
{
  Allocated_Memory += size;

  Mem_Vista_Buffer += size;

  return(malloc(size));
}



/*****************************************************************************
*
* FUNCTION      : LB_malloc
*
* ARGUMENTS     : size   - Amount of memory to allocate
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : void * - Pointer at allocated memory
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Allocate memory for the light buffer and keep track of the memory allocated.
*
* CHANGES
*
*   -
*
******************************************************************************/

void *LB_malloc(size)
size_t size;
{
  Allocated_Memory += size;

  Mem_Light_Buffers += size;

  return(malloc(size));
}



/*****************************************************************************
*
* FUNCTION      : new_malloc
*
* ARGUMENTS     : size   - Amount of memory to allocate
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : void * - Pointer at allocated memory
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Allocate memory and keep track of the memory allocated.
*
*   Use instead of malloc when allocating memory!
*
* CHANGES
*
*   -
*
******************************************************************************/

void *new_malloc(size)
size_t size;
{
  Allocated_Memory += size;

  return(malloc(size));
}



/*****************************************************************************
*
* FUNCTION      : new_free
*
* ARGUMENTS     : pointer - Memory to free
*                 size    - Amount of memory that will be freed
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Free memory and keep track of the memory allocated.
*
*   Use instead of free when freeing memory!
*
* CHANGES
*
*   -
*
******************************************************************************/

void new_free(pointer, size)
void *pointer;
size_t size;
{
  Allocated_Memory -= size;

  free(pointer);
}


/*****************************************************************************
*
* FUNCTION      : Init_Additional_1
*
* ARGUMENTS     : none
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Additional initialisation before boundind slabs are build.
*
*   Split union objects and pass bounding objects to the children if they
*   aren't already bounded (most bounding objects will be removed later).
*
* CHANGES
*
*   -
*
******************************************************************************/

void Init_Additionals_1()
{
  int children_finite;
  long count;
  DBL Volume;
  OBJECT **Object, *Sib, *Last_Sib, *Bound;

  Print_Quadric_Stats();

  /* If slabs are not used --> vista and light buffer can't be used */

  if (!Use_Slabs)
  {
    Extended_Options &= ~USE_VISTA_BUFFER;
    Extended_Options &= ~USE_LIGHT_BUFFER;
  }

  /* We don't use shadows so we don't need a light buffer */

  if (!(Quality_Flags & Q_SHADOW))
  {
    Extended_Options &= ~USE_LIGHT_BUFFER;
  }

  if ((Extended_Options & USE_SPLIT_FINITE_UNIONS) ||
      (Extended_Options & USE_SPLIT_INFINITE_UNIONS))
  {
    START_TIME

    Recompute_Bboxes();

    fprintf(stderr, "Splitting union objects");

    Begin_Point();

    count = 0;

    for (Object = &Frame.Objects; (*Object) != NULL; )
    {
      children_finite = FALSE;

      if (Extended_Options & USE_SPLIT_INFINITE_UNIONS)
      {
	/* +usi option is used, i.e. split all unions */

	children_finite = TRUE;
      }
      else
      {
	/* Check, if all children of the union have finite bounding boxes */

	if ((*Object)->Methods == &CSG_Union_Methods)
	{
	  children_finite = TRUE;

	  for (Sib = ((CSG *)(*Object))->Children; Sib != NULL; Sib = Sib->Sibling)
	  {
	    BOUNDS_VOLUME(Volume, Sib->Bounds);
	    if (Volume > INFINITE_VOLUME) children_finite = FALSE;
	  }
	}
      }

      /* Split union object, if all children are finite (or tracing slows
	 down!) and the union isn't clipped */

      if (((*Object)->Methods == &CSG_Union_Methods) &&
	  ((*Object)->Clip == NULL) && (children_finite))
      {
	count++;

	Print_Point(POINT_MOD);

	Bound = (*Object)->Bound;

	if ((Sib = ((CSG *)(*Object))->Children) != NULL)
	{
	  for (; Sib != NULL; Sib = Sib->Sibling)
	  {
	    /* Set child's bound to father's bound (some peolpe use objects
	       that don't fit in the bounding object. Argh!!!
	       The question is: should this be done or not?) */

	    if (Sib->Bound == NULL) Sib->Bound = Bound;

	    Last_Sib = Sib;
	  }

	  Last_Sib->Sibling = (*Object)->Sibling;

	  (*Object) = ((CSG *)(*Object))->Children;
	}
	else
	{
	  (*Object) = (*Object)->Sibling;
	}
      }
      else
      {
	Object = &(*Object)->Sibling;
      }
    }

    fprintf(stderr, "(%ld split)", count);

    End_Point();

    if (count > 0)
    {
      /* Just to be sure */

      Recompute_Bboxes();
    }

    STOP_TIME

    time_used1 = TIME_ELAPSED
  }
  else
  {
    Recompute_Bboxes();
  }
}



/*****************************************************************************
*
* FUNCTION      : Init_Additionals_2
*
* ARGUMENTS     : none
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Additional initialisation after boundind slabs have been build.
*
*   - Project objects onto the screen.
*   - Build the light buffers.
*   - Remove all unnecessary bounding objects.
*   - Print a statistic of the scene.
*
* CHANGES
*
*   -
*
******************************************************************************/

void Init_Additionals_2()
{
  DBL time_used;

  if ((Extended_Options & USE_VISTA_BUFFER) ||
      (Extended_Options & USE_LIGHT_BUFFER))
  {
    START_TIME

    if (Use_Slabs)
    {
      Init_Project_Tree_Queues();

      if (Extended_Options & USE_VISTA_BUFFER)
      {
	Init_View_Coordinates();

	Build_Vista_Tree();
      }

      if (Extended_Options & USE_LIGHT_BUFFER)
      {
	Build_Light_Buffers();
      }
    }

    Remove_Unnecessary_Bounds();

    Print_Object_Stats();

    STOP_TIME

    time_used2 = TIME_ELAPSED

    time_used = time_used1 + time_used2;

    fprintf(stderr, "Time Overhead : %.0f seconds\n", time_used);
  }
  else
  {
    Remove_Unnecessary_Bounds();
  }
}



/*****************************************************************************
*
* FUNCTION      : Get_Object_Type
*
* ARGUMENTS     : Object - Point to an object
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : int - Type of object
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Returns the type of an object.
*
* CHANGES
*
*   -
*
******************************************************************************/

static int Get_Object_Type(Object)
OBJECT *Object;
{
  if (Object->Methods == &Bicubic_Patch_Methods)    return(TYPE_BICUBIC_PATCH);

  if (Object->Methods == &Blob_Methods)             return(TYPE_BLOB);

  if (Object->Methods == &Box_Methods)              return(TYPE_BOX);

  if (Object->Methods == &Cone_Methods)             return(TYPE_CONE);

  if (Object->Methods == &CSG_Intersection_Methods) return(TYPE_CSG_INTERSECTION);

  if (Object->Methods == &CSG_Merge_Methods)        return(TYPE_CSG_MERGE);

  if (Object->Methods == &CSG_Union_Methods)        return(TYPE_CSG_UNION);

  if (Object->Methods == &Disc_Methods)             return(TYPE_DISC);

  if (Object->Methods == &Ellipsoid_Methods)        return(TYPE_ELLIPSOID);

  if (Object->Methods == &Height_Field_Methods)     return(TYPE_HEIGHT_FIELD);

  if (Object->Methods == &Csg_Height_Field_Methods) return(TYPE_HEIGHT_FIELD);

  if (Object->Methods == &Light_Source_Methods)     return(TYPE_LIGHT_SOURCE);

  if (Object->Methods == &Plane_Methods)            return(TYPE_PLANE);

  if (Object->Methods == &Poly_Methods)             return(TYPE_POLY);

  if (Object->Methods == &Quadric_Methods)          return(TYPE_QUADRIC);

  if (Object->Methods == &Smooth_Triangle_Methods)  return(TYPE_SMOOTH_TRIANGLE);

  if (Object->Methods == &Sphere_Methods)           return(TYPE_SPHERE);

  if (Object->Methods == &Triangle_Methods)         return(TYPE_TRIANGLE);

  return(TYPE_UNKNOWN);
}



/*****************************************************************************
*
* FUNCTION      : Get_Object_Stats
*
* ARGUMENTS     : Object       - object
*                 csg          - Flag if inside a csg object
*                 bound_object - Flag if object is part of a bounding object
*                 clip_object  - Flag if object is part of a clipping object
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Get some information about an object and add it to the scene statistic.
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Get_Object_Stats(Object, csg, bound_object, clip_object)
OBJECT *Object;
int csg, bound_object, clip_object;
{
  int bounded, clipped, infinite, type;
  DBL Volume;

  OBJECT *Sib;

  if (Object == NULL)
    return;

  /* Bounded/Clipped object? */

  bounded = (Object->Bound != NULL);
  clipped = (Object->Clip != NULL);

  /* Don't care about infinite objects if they are inside
     a CSG object or used as clipping/bounding objects */

  if (csg || bound_object || clip_object)
  {
    infinite = FALSE;
  }
  else
  {
    /* Infinte object? */

    BOUNDS_VOLUME(Volume, Object->Bounds);

    infinite = (Volume > INFINITE_VOLUME);
  }

  /* Get object type */

  type = Get_Object_Type(Object);

  /* Count bounding objects */

  if (Object->Bound != NULL)
  {
    for (Sib = Object->Bound; Sib != NULL; Sib = Sib->Sibling)
    {
      Get_Object_Stats(Sib, csg, TRUE, clip_object);
    }
  }

  /* Count clipping objects */

  if (Object->Clip != NULL)
  {
    for (Sib = Object->Clip; Sib != NULL; Sib = Sib->Sibling)
    {
      Get_Object_Stats(Sib, csg, bound_object, TRUE);
    }
  }

  if (Object->Type & COMPOUND_OBJECT)
  {
    if (Object->Type & LIGHT_SOURCE_OBJECT)
    {
      /* Count light source */

      counter[type][FLAG_SUM]++;

      Get_Object_Stats(((LIGHT_SOURCE *)Object)->Children, csg, bound_object, clip_object);
    }
    else
    {
      /* Count CSG object */

      counter[type][FLAG_SUM]++;

      if (csg)            counter[type][FLAG_USED_IN_CSG]++;
      if (infinite)       counter[type][FLAG_INFINITE]++;
      if (bounded)        counter[type][FLAG_BOUNDED]++;
      if (clipped)        counter[type][FLAG_CLIPPED]++;
      if (bound_object)   counter[type][FLAG_BOUND_OBJECT]++;
      if (clip_object)    counter[type][FLAG_CLIP_OBJECT]++;

      for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
      {
	Get_Object_Stats(Sib, TRUE, bound_object, clip_object);
      }
    }
  }
  else
  {
    /* Count the primitive object */

    counter[type][FLAG_SUM]++;

    if (csg)            counter[type][FLAG_USED_IN_CSG]++;
    if (infinite)       counter[type][FLAG_INFINITE]++;
    if (bounded)        counter[type][FLAG_BOUNDED]++;
    if (clipped)        counter[type][FLAG_CLIPPED]++;
    if (bound_object)   counter[type][FLAG_BOUND_OBJECT]++;
    if (clip_object)    counter[type][FLAG_CLIP_OBJECT]++;
  }
}



/*****************************************************************************
*
* FUNCTION      : Print_Object_Info
*
* ARGUMENTS     : type - Object's type
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Print the statistics of one type of object.
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Print_Object_Info(type)
int type;
{
  fprintf(stderr, " : %5ld %5ld %5ld %5ld %5ld   %5ld   %5ld\n",
    counter[type][FLAG_SUM],
    counter[type][FLAG_USED_IN_CSG],
    counter[type][FLAG_INFINITE],
    counter[type][FLAG_BOUND_OBJECT],
    counter[type][FLAG_CLIP_OBJECT],
    counter[type][FLAG_BOUNDED],
    counter[type][FLAG_CLIPPED]);
}



/*****************************************************************************
*
* FUNCTION      : Print_Object_Stats
*
* ARGUMENTS     : none
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Collect and print a statistic about the scene.
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Print_Object_Stats()
{
  int i, j;
  long sum1, sum2, sum3, sum4, sum5, sum6, sum7, frame_level;
  OBJECT *Sib;

  /* Initialize counters */

  for (i = 0; i < NUMBER_OF_TYPES; i++)
  {
    for (j = 0; j < NUMBER_OF_FLAGS; j++)
    {
      counter[i][j] = 0;
    }
  }

  frame_level = 0;

  for (Sib = Frame.Objects; Sib != NULL; Sib = Sib->Sibling)
  {
    if (Sib->Type & LIGHT_SOURCE_OBJECT)
    {
      if (((LIGHT_SOURCE *)Sib)->Children != NULL)
      {
	frame_level++;
      }
    }
    else
    {
      frame_level++;
    }
    Get_Object_Stats(Sib, FALSE, FALSE, FALSE);
  }

  sum1 = sum2 = sum3 = sum4 = sum5 = sum6 = sum7 = 0;

  for (i = 0; i < NUMBER_OF_TYPES; i++)
  {
    sum1 += counter[i][FLAG_SUM];
    sum2 += counter[i][FLAG_USED_IN_CSG];
    sum3 += counter[i][FLAG_INFINITE];
    sum4 += counter[i][FLAG_BOUND_OBJECT];
    sum5 += counter[i][FLAG_CLIP_OBJECT];
    sum6 += counter[i][FLAG_BOUNDED];
    sum7 += counter[i][FLAG_CLIPPED];
  }

  fprintf(stderr, "                  Sum   CSG Infin Bound  Clip Bounded Clipped\n");
  fprintf(stderr, "Blob         "); Print_Object_Info(TYPE_BLOB);
  fprintf(stderr, "Box          "); Print_Object_Info(TYPE_BOX);
  fprintf(stderr, "Cone/Cylinder"); Print_Object_Info(TYPE_CONE);
  fprintf(stderr, "Ellipsoid    "); Print_Object_Info(TYPE_ELLIPSOID);
  fprintf(stderr, "Heightfield  "); Print_Object_Info(TYPE_HEIGHT_FIELD);
  fprintf(stderr, "Sphere       "); Print_Object_Info(TYPE_SPHERE);

  fprintf(stderr, "Bezierpatch  "); Print_Object_Info(TYPE_BICUBIC_PATCH);
  fprintf(stderr, "Disc         "); Print_Object_Info(TYPE_DISC);
  fprintf(stderr, "Tri (Phong)  "); Print_Object_Info(TYPE_SMOOTH_TRIANGLE);
  fprintf(stderr, "Tri (Flat)   "); Print_Object_Info(TYPE_TRIANGLE);

  fprintf(stderr, "Plane        "); Print_Object_Info(TYPE_PLANE);
  fprintf(stderr, "Quartic/Poly "); Print_Object_Info(TYPE_POLY);
  fprintf(stderr, "Quadric      "); Print_Object_Info(TYPE_QUADRIC);

  fprintf(stderr, "CSG-ISect    "); Print_Object_Info(TYPE_CSG_INTERSECTION);
  fprintf(stderr, "CSG-Merge    "); Print_Object_Info(TYPE_CSG_MERGE);
  fprintf(stderr, "CSG-Union    "); Print_Object_Info(TYPE_CSG_UNION);

  fprintf(stderr, "Lightsource  "); Print_Object_Info(TYPE_LIGHT_SOURCE);

  fprintf(stderr, "Grand totals  : %5ld %5ld %5ld %5ld %5ld   %5ld   %5ld\n", sum1, sum2, sum3, sum4, sum5, sum6, sum7);

  fprintf(stderr, "Root objects  : %5ld\n\n", frame_level);

/*
  fprintf(stderr, "Scene contains %ld frame level objects.\n", frame_level);
*/
  /* Print amount of allocated memory */

  if (Mem_Vista_Buffer)
    fprintf(stderr, "Vista Buffer  : %.2f KBytes\n", (DBL)(Mem_Vista_Buffer) / 1024.0);

  if (Mem_Light_Buffers)
    fprintf(stderr, "Light Buffer  : %.2f KBytes\n", (DBL)(Mem_Light_Buffers) / 1024.0);
/*
  if (Allocated_Memory)
    fprintf(stderr, "RAM Overhead  : %.2f KBytes\n", (DBL)Allocated_Memory / 1024.0);
*/
}



/*****************************************************************************
*
* FUNCTION      : Clip_Polygon
*
* ARGUMENTS     : 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
*
* MODIFIED ARGS : Points, PointCnt
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Clip polygon at the viewing pyramid define by the normal vectors
*   VX1, VX2, VY1, VY2 and the distances DX1, DX2, DY1, DY2.
*
* CHANGES
*
*   -
*
******************************************************************************/

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;

  firP = Points[0];
  fird = VX1->x * firP.x + VX1->y * firP.y + VX1->z * firP.z - DX1;

  if (fird <= 0.0)
    ClipPoints[pc++] = firP;

  aktP = preP = firP;
  aktd = pred = fird;

  for (i = 1; i < *PointCnt; i++)
  {
    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;

      ClipPoints[pc++] = intP;
    }

    if (aktd <= 0.0)
      ClipPoints[pc++] = aktP;

    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;

    ClipPoints[pc++] = intP;
  }

  for (i = 0; i < pc; i++)
    Points[i] = ClipPoints[i];

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

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

  pc = 0;

  firP = Points[0];
  fird = VX2->x * firP.x + VX2->y * firP.y + VX2->z * firP.z - DX2;

  if (fird <= 0.0)
    ClipPoints[pc++] = firP;

  aktP = preP = firP;
  aktd = pred = fird;

  for (i = 1; i < *PointCnt; i++)
  {
    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;

      ClipPoints[pc++] = intP;
    }

    if (aktd <= 0.0)
      ClipPoints[pc++] = aktP;

    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;

    ClipPoints[pc++] = intP;
  }

  for (i = 0; i < pc; i++)
    Points[i] = ClipPoints[i];

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

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

  pc = 0;

  firP = Points[0];
  fird = VY1->x * firP.x + VY1->y * firP.y + VY1->z * firP.z - DY1;

  if (fird <= 0.0)
    ClipPoints[pc++] = firP;

  aktP = preP = firP;
  aktd = pred = fird;

  for (i = 1; i < *PointCnt; i++)
  {
    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;

      ClipPoints[pc++] = intP;
    }

    if (aktd <= 0.0)
      ClipPoints[pc++] = aktP;

    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;

    ClipPoints[pc++] = intP;
  }

  for (i = 0; i < pc; i++)
    Points[i] = ClipPoints[i];

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

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

  pc = 0;

  firP = Points[0];
  fird = VY2->x * firP.x + VY2->y * firP.y + VY2->z * firP.z - DY2;

  if (fird <= 0.0)
    ClipPoints[pc++] = firP;

  aktP = preP = firP;
  aktd = pred = fird;

  for (i = pc = 0; i < *PointCnt; i++)
  {
    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;
      
      ClipPoints[pc++] = intP;
    }

    if (aktd <= 0.0)
      ClipPoints[pc++] = aktP;

    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;

    ClipPoints[pc++] = intP;
  }

  for (i = 0; i < pc; i++)
    Points[i] = ClipPoints[i];

  *PointCnt = pc;
}



/*****************************************************************************
*
* FUNCTION      : MInvers
*
* ARGUMENTS     : m - matrix to invert
*                 r - inverted matrix
*
* MODIFIED ARGS : r
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Invert a 4x4 matrix.
*
* CHANGES
*
*   -
*
******************************************************************************/

void MInvers(r, m)
MATRIX *r, *m;
{
  DBL d00, d01, d02, d03;
  DBL d10, d11, d12, d13;
  DBL d20, d21, d22, d23;
  DBL d30, d31, d32, d33;
  DBL m00, m01, m02, m03;
  DBL m10, m11, m12, m13;
  DBL m20, m21, m22, m23;
  DBL m30, m31, m32, m33;
  DBL D;

  m00 = (*m)[0][0];  m01 = (*m)[0][1];  m02 = (*m)[0][2];  m03 = (*m)[0][3];
  m10 = (*m)[1][0];  m11 = (*m)[1][1];  m12 = (*m)[1][2];  m13 = (*m)[1][3];
  m20 = (*m)[2][0];  m21 = (*m)[2][1];  m22 = (*m)[2][2];  m23 = (*m)[2][3];
  m30 = (*m)[3][0];  m31 = (*m)[3][1];  m32 = (*m)[3][2];  m33 = (*m)[3][3];

  d00 = m11*m22*m33 + m12*m23*m31 + m13*m21*m32 - m31*m22*m13 - m32*m23*m11 - m33*m21*m12;
  d01 = m10*m22*m33 + m12*m23*m30 + m13*m20*m32 - m30*m22*m13 - m32*m23*m10 - m33*m20*m12;
  d02 = m10*m21*m33 + m11*m23*m30 + m13*m20*m31 - m30*m21*m13 - m31*m23*m10 - m33*m20*m11;
  d03 = m10*m21*m32 + m11*m22*m30 + m12*m20*m31 - m30*m21*m12 - m31*m22*m10 - m32*m20*m11;

  d10 = m01*m22*m33 + m02*m23*m31 + m03*m21*m32 - m31*m22*m03 - m32*m23*m01 - m33*m21*m02;
  d11 = m00*m22*m33 + m02*m23*m30 + m03*m20*m32 - m30*m22*m03 - m32*m23*m00 - m33*m20*m02;
  d12 = m00*m21*m33 + m01*m23*m30 + m03*m20*m31 - m30*m21*m03 - m31*m23*m00 - m33*m20*m01;
  d13 = m00*m21*m32 + m01*m22*m30 + m02*m20*m31 - m30*m21*m02 - m31*m22*m00 - m32*m20*m01;

  d20 = m01*m12*m33 + m02*m13*m31 + m03*m11*m32 - m31*m12*m03 - m32*m13*m01 - m33*m11*m02;
  d21 = m00*m12*m33 + m02*m13*m30 + m03*m10*m32 - m30*m12*m03 - m32*m13*m00 - m33*m10*m02;
  d22 = m00*m11*m33 + m01*m13*m30 + m03*m10*m31 - m30*m11*m03 - m31*m13*m00 - m33*m10*m01;
  d23 = m00*m11*m32 + m01*m12*m30 + m02*m10*m31 - m30*m11*m02 - m31*m12*m00 - m32*m10*m01;

  d30 = m01*m12*m23 + m02*m13*m21 + m03*m11*m22 - m21*m12*m03 - m22*m13*m01 - m23*m11*m02;
  d31 = m00*m12*m23 + m02*m13*m20 + m03*m10*m22 - m20*m12*m03 - m22*m13*m00 - m23*m10*m02;
  d32 = m00*m11*m23 + m01*m13*m20 + m03*m10*m21 - m20*m11*m03 - m21*m13*m00 - m23*m10*m01;
  d33 = m00*m11*m22 + m01*m12*m20 + m02*m10*m21 - m20*m11*m02 - m21*m12*m00 - m22*m10*m01;

  D = m00*d00 - m01*d01 + m02*d02 - m03*d03;

  if (fabs(D) < EPSILON)
    Fatal_Error("Singular matrix in MInvers.\n");

  (*r)[0][0] = +d00/D; (*r)[0][1] = -d10/D;  (*r)[0][2] = +d20/D; (*r)[0][3] = -d30/D;
  (*r)[1][0] = -d01/D; (*r)[1][1] = +d11/D;  (*r)[1][2] = -d21/D; (*r)[1][3] = +d31/D;
  (*r)[2][0] = +d02/D; (*r)[2][1] = -d12/D;  (*r)[2][2] = +d22/D; (*r)[2][3] = -d32/D;
  (*r)[3][0] = -d03/D; (*r)[3][1] = +d13/D;  (*r)[3][2] = -d23/D; (*r)[3][3] = +d33/D;
}



/*****************************************************************************
*
* FUNCTION      : Fatal_Error
*
* ARGUMENTS     : str - String to print to stderr
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Print an error message and leave program.
*
* CHANGES
*
*   -
*
******************************************************************************/

void Fatal_Error(str)
char *str;
{
  fputs(str, stderr);
  exit(1);
}



/*****************************************************************************
*
* FUNCTION      : Fatal_MAError
*
* ARGUMENTS     : str - String to print to stderr after out of memory message
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Print an error message and leave program. Call if memory
*   allocation fails.
*
* CHANGES
*
*   -
*
******************************************************************************/

void Fatal_MAError(str)
char *str;
{
  fprintf(stderr, "Out of memory. Cannot allocate %s.\n", str);
  exit (1);
}



/*****************************************************************************
*
* FUNCTION      : Begin_Point
*
* ARGUMENTS     : none
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Print points to stderr and initialize point counter.
*
* CHANGES
*
*   -
*
******************************************************************************/

void Begin_Point()
{
  fprintf(stderr, "...");
  Point_Counter = 0;
}



/*****************************************************************************
*
* FUNCTION      : Print_Point
*
* ARGUMENTS     : Repeat - Determines after how many calls a point will be printed
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Print points to stderr.
*
* CHANGES
*
*   -
*
******************************************************************************/

void Print_Point(Repeat)
int Repeat;
{
  if ((Point_Counter % Repeat) == 0)
    fprintf(stderr, ".");
  Point_Counter++;
}



/*****************************************************************************
*
* FUNCTION      : End_Point
*
* ARGUMENTS     : none
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Print newline to stderr.
*
* CHANGES
*
*   -
*
******************************************************************************/

void End_Point()
{
  fprintf(stderr, "\n");
}



/*****************************************************************************
*
* FUNCTION      : Draw_Projection
*
* ARGUMENTS     : Project - projection to draw
*                 color   - Color to be used
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Draws a projection in the specified color.
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Draw_Projection(Project, color)
PROJECT *Project;
int color;
{
}

/*
{
  int x, y, x1, x2, y1, y2;
  unsigned short int r, g, b;

  switch (color)
  {
    case RED   : r = 255; g = b = 0; break;
    case GREEN : g = 255; r = b = 0; break;
    case BLUE  : b = 255; r = g = 0; break;
    default    : r = g = b = 255;
  }

  x1 = Project->x1;
  x2 = Project->x2;
  y1 = Project->y1;
  y2 = Project->y2;

  if ((x1 <= x2) && (y1 <= y2))
  {
    if (x1 < 0) x1 = 0;
    if (x2 < 0) x2 = 0;
    if (y1 < 0) y1 = 0;
    if (y2 < 0) y2 = 0;

    if (x1 >= Frame.Screen_Width)  x1 = Frame.Screen_Width - 1;
    if (x2 >= Frame.Screen_Width)  x2 = Frame.Screen_Width - 1;
    if (y1 >= Frame.Screen_Height) y1 = Frame.Screen_Height - 1;
    if (y2 >= Frame.Screen_Height) y2 = Frame.Screen_Height - 1;

    for (x = x1; x <= x2; x++)
    {
      display_plot (x, y1, r, g, b);
      display_plot (x, y2, r, g, b);
    }
    for (y = y1; y <= y2; y++)
    {
      display_plot (x1, y, r, g, b);
      display_plot (x2, y, r, g, b);
    }
  }
}

*/

/*****************************************************************************
*
* FUNCTION      : Draw_Vista
*
* ARGUMENTS     : Tree - current node/leaf in the vista tree
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Draws recursively all projections of subnodes in the current node.
*
* CHANGES
*
*   -
*
******************************************************************************/

static void Draw_Vista(Tree)
PROJECT_TREE_NODE *Tree;
{
/*
  unsigned short i;
  PROJECT_TREE_LEAF *Leaf;

  if (Tree->is_leaf)
  {
    Leaf = (PROJECT_TREE_LEAF *)Tree;

    if (Leaf->Object->Type & COMPOUND_OBJECT)
    {
      Draw_Projection(&Leaf->Project, BLUE);
    }
    else
    {
      Draw_Projection(&Leaf->Project, RED);
    }
  }
  else
  {
    for (i = 0; i < Tree->Entries; i++)
    {
      Draw_Vista(Tree->Entry[i]);
    }
  }

  /* draw bounding object's vista */

/*
  Draw_Projection(&Tree->Project, GREEN);
*/
*/
}



/*****************************************************************************
*
* FUNCTION      : Draw_Vista_Tree
*
* ARGUMENTS     : none
*
* MODIFIED ARGS : none
*
* RETURN VALUE  : none
*
* AUTHOR        : Dieter Bayer, May, 1994
*
* DESCRIPTION
*
*   Draw the vista tree.
*
* CHANGES
*
*   -
*
******************************************************************************/

void Draw_Vista_Tree()
{
/*
  if (Extended_Options & USE_VISTA_BUFFER)
  {

/*    Draw_Vista(Root_Vista);  */

  }
*/
}



#endif