chull.C

Go to the documentation of this file.

/* --
OpenFX version 2.0 - Modelling, Animation and Rendering Package
Copyright (C) 2000 - 2007 OpenFX Development Team
-- */

/*  CHULL.C  */
#include <stdlib.h>
#include <stdio.h>
#include <setjmp.h>
#include <math.h>
#include <windows.h>

#include "struct.h"
#include "dstruct.h"

#include "chull.h"

jmp_buf jmp_buf_here;

/* Define structures for O'Rourke's code vertices, edges and faces */
typedef BOOL    bool;

typedef struct tVertexStructure tsVertex;
typedef tsVertex *tVertex;

typedef struct tEdgeStructure tsEdge;
typedef tsEdge *tEdge;

typedef struct tFaceStructure tsFace;
typedef tsFace *tFace;

struct tVertexStructure {
   int      v[3];
   int      vnum;
   int      OFXid;           /* used by OpenFX for vertex ID when building */
   tEdge    duplicate;       /* pointer to incident cone edge (or NULL) */
   bool     onhull;                    /* T iff point on hull. */
   bool     mark;            /* T iff point already processed. */
   tVertex  next, prev;
};

struct tEdgeStructure {
   tFace    adjface[2];
   tVertex  endpts[2];
   tFace    newface;            /* pointer to incident cone face. */
   bool     HULL_DELETE;                /* T iff edge should be HULL_DELETE. */
   tEdge    next, prev;
};

struct tFaceStructure {
   tEdge    edge[3];
   tVertex  vertex[3];
   bool     visible;            /* T iff face visible from new point. */
   tFace    next, prev;
};

/*====================================================================
    macros.h
 
        macros used to access data structures and perform quick tests.

  ====================================================================*/

/* general-purpose macros */
#define SWAP(t,x,y)     { t = x; x = y; y = t; }


#define NEW(p,type)     if ((p=(type *) malloc (sizeof(type))) == NULL) {\
                                longjmp(jmp_buf_here,-1);\
                        }

#define FREE(p)         if (p) { free ((char *) p); p = NULL; }


#define HULL_ADD( head, p )  if ( head )  { \
                                p->next = head; \
                                p->prev = head->prev; \
                                head->prev = p; \
                                p->prev->next = p; \
                        } \
                        else { \
                                head = p; \
                                head->next = head->prev = p; \
                        }

#define HULL_DELETE( head, p ) if ( head )  { \
                                if ( head == head->next ) \
                                        head = NULL;  \
                                else if ( p == head ) \
                                        head = head->next; \
                                p->next->prev = p->prev;  \
                                p->prev->next = p->next;  \
                                FREE( p ); \
                        } 


#define DESELECTED 0
#define SELECTED   1
#define MINUNIT       2048L     // was 1024 trying larger to prevent error
#define MAXUNIT   33554432L

#ifndef min
#define min(a,b)  ( ((a) < (b)) ? (a) : (b) )
#endif
#ifndef max
#define max(a,b)  ( ((a) > (b)) ? (a) : (b) )
#endif

BOOL    DoubleTriangle( void );
void    ConstructHull( void );
tVertex MakeNullVertex( void );
void    DeleteTemporaryStructures(void);

/* Define vertex indices. */
#define X   0
#define Y   1
#define Z   2

/* Global variable definitions for temporary structures */
tVertex vertices = NULL;
tEdge edges      = NULL;
tFace faces      = NULL;

static HWND      hParent;
static HINSTANCE hThisInstance;

#if __WATCOMC__
int APIENTRY LibMain(HANDLE hDLL, DWORD dwReason, LPVOID lpReserved){
#else
BOOL WINAPI DllMain(HANDLE hDLL, DWORD dwReason, LPVOID lpReserved){
#endif
  switch (dwReason) {
    case DLL_PROCESS_ATTACH: {
      hThisInstance=hDLL;
      if(hDLL == NULL)MessageBox ( GetFocus()," NULL instance",NULL, MB_OK);
      break;
    }
    case DLL_PROCESS_DETACH:
      break;
  }
  return TRUE;
}

BOOL _Xmodeler
 (HWND parent_window,HWND info_window,X__STRUCTURE *lpevi){
 char text_string[255],name_string[255];
 lpEVI=lpevi;
 hParent=parent_window;
 LoadString(hThisInstance,IDX_STRING2,text_string,256);
 LoadString(hThisInstance,IDX_STRING1,name_string,256);
 if(MessageBox(hParent,text_string,name_string,MB_OKCANCEL)
               == IDCANCEL)return FALSE;
 else{
   HCURSOR hSave;
   vertex *vp;
   long i,maxdim;
   long xmin=MAXUNIT,xmax=-MAXUNIT,ymin=MAXUNIT,ymax=-MAXUNIT,zmin=MAXUNIT,zmax=-MAXUNIT;
   double scale;
   if(NvertSelect < 4 || NvertSelect > 32000)return FALSE;
   hSave=SetCursor(LoadCursor(NULL,IDC_WAIT));
   vp=MainVp; for(i=0;i<Nvert;i++){
     if(vp->status == SELECTED){
       if(vp->xyz[0] < xmin)xmin=vp->xyz[0];
       if(vp->xyz[1] < ymin)ymin=vp->xyz[1];
       if(vp->xyz[2] < zmin)zmin=vp->xyz[2];
       if(vp->xyz[0] > xmax)xmax=vp->xyz[0];
       if(vp->xyz[1] > ymax)ymax=vp->xyz[1];
       if(vp->xyz[2] > zmax)zmax=vp->xyz[2];
           }
     vp++;
   }
   maxdim=max(xmax-xmin,ymax-ymin);
   maxdim=max(maxdim,zmax-zmin);
   if(xmax-xmin > MINUNIT &&
      ymax-ymin > MINUNIT && 
          zmax-zmin > MINUNIT){ // have at least 4 non-planar non-linear vertices
     tVertex v;
     tEdge   e;
     tFace   f;
     int vnum=0;
     scale=(double)MINUNIT/(double)maxdim;        
     vp=MainVp; for(i=0;i<Nvert;i++){
       if(vp->status == SELECTED){
         v=MakeNullVertex();
         v->v[X] = (long)((double)vp->xyz[0]*scale);
         v->v[Y] = (long)((double)vp->xyz[1]*scale);
         v->v[Z] = (long)((double)vp->xyz[2]*scale);
         v->vnum=vnum++;
       }
       vp++;
     }
     //{
     //char str[128]; sprintf(str,"Making hull with %ld vertices",vnum);
     //MessageBox(NULL,str,"Before Making Hull",MB_OK);
     //}
     if(setjmp(jmp_buf_here) != 0){
       DeleteTemporaryStructures();
       SetCursor(hSave);
       LoadString(hThisInstance,IDX_STRING3,text_string,256);
       MessageBox(hParent,text_string,name_string,MB_OKCANCEL);
       return FALSE;
     }
     if(DoubleTriangle()){
       long nf=0,ne=0,nv=0;
             ConstructHull();
       // now build the OpenFX data - first count the number of extra V E F
       f=faces; if(f != NULL)do {
         nf++;
         f = f->next;
       } while(f != faces);
       e = edges;if(e != NULL)do {
         ne++;
               e = e->next;
       } while (e != edges);
       v = vertices; if(v != NULL)do {
         nv++;
         v = v->next;
       } while (v != vertices);
       //{
       //char str[128]; sprintf(str,"NV = %ld NE = %ld NF = %ld",nv,ne,nf);
       //MessageBox(NULL,str,"After Making Hull",MB_OK);
       //}
       // Now extend the OpenFX
       if(!UpdateVertexHeap(Nvert+nv))goto CANTDO;
       if(!UpdateEdgeHeap(Nedge+ne))goto CANTDO;
       if(!UpdateFaceHeap(Nface+ne))goto CANTDO;
       v = vertices; if(v != NULL)do {
         CreateVertex();
         vp=(MainVp+Nvert-1);
         vp->xyz[0]=(long)((double)(v->v[X])/scale);
         vp->xyz[1]=(long)((double)(v->v[Y])/scale);
         vp->xyz[2]=(long)((double)(v->v[Z])/scale);
         vp->status=DESELECTED;
         v->OFXid = Nvert-1;
         NvertDeselect++; NvertSelect--;
         nv++;
         v = v->next;
       } while (v != vertices);

       e = edges;
       if(e != NULL)do {
         CreateEdge(e->endpts[0]->OFXid,e->endpts[1]->OFXid);
         e = e->next;
       } while (e != edges);
       f = faces;
       if(f != NULL)do {
         CreateFace(f->vertex[0]->OFXid,f->vertex[1]->OFXid,f->vertex[2]->OFXid);
         f = f->next;
       } while(f != faces);
       CANTDO:;
     }
     DeleteTemporaryStructures();
     SetCursor(hSave);
     LoadString(hThisInstance,IDX_STRING3,text_string,256);
     MessageBox(hParent,text_string,name_string,MB_OKCANCEL);
   }
   else{
     LoadString(hThisInstance,IDX_STRING4,text_string,256);
     MessageBox(hParent,text_string,name_string,MB_OKCANCEL);
     SetCursor(hSave);
   }
 }
 return TRUE;
}

void DeleteTemporaryStructures(void){
 tEdge   e,te;
 tFace   f,tf;
 tVertex v,tv;
 f=faces;
 if(f != NULL)do {
   tf = f;
   f = f->next;
         FREE(tf)
 } while(f != faces);
 e = edges;
 if(e != NULL)do {
         te = e;
         e = e->next;
         FREE(te)
 } while (e != edges);
 v = vertices;
 if(v != NULL)do {
         tv = v; 
         v = v->next;
         FREE(tv)
 } while (v != vertices);
 return;
}

// THE O'ROURKE CODE BELOW IS MODIFIED TO ALLOW FOR A SOFT LANDING AND
// COMPLY WITH OPENFX DATA STRUCTURE & WINDOWS REQUIREMENTS

/*
This code is described in "Computational Geometry in C" (Second Edition),
Chapter 4.  It is not written to be comprehensible without the 
explanation in that book.

Input: 3n integer coordinates for the points.
Output: the 3D convex hull, in postscript with embedded comments
        showing the vertices and faces.

Compile: gcc -o chull chull.c (or simply: make)

Written by Joseph O'Rourke, with contributions by 
  Kristy Anderson, John Kutcher, Catherine Schevon, Susan Weller.
Last modified: March 1998
Questions to orourke@cs.smith.edu.

--------------------------------------------------------------------
This code is Copyright 1998 by Joseph O'Rourke.  It may be freely 
redistributed in its entirety provided that this copyright notice is 
not removed.
--------------------------------------------------------------------
*/

/* Define flags */
#define ONHULL          TRUE
#define REMOVED         TRUE
#define VISIBLE         TRUE
#define PROCESSED       TRUE
#define SAFE            1000000         /* Range of safe coord values. */

/* Function declarations */
void    ReadVertices( void );
void    Print( void );
void    SubVec( int a[3], int b[3], int c[3]);
bool    HULL_ADDOne( tVertex p );
int     VolumeSign(tFace f, tVertex p);
int     Volumei( tFace f, tVertex p );
tFace   MakeConeFace( tEdge e, tVertex p );
void    MakeCcw( tFace f, tEdge e, tVertex p );
tEdge   MakeNullEdge( void );
tFace   MakeNullFace( void );
tFace   MakeFace( tVertex v0, tVertex v1, tVertex v2, tFace f );
void    CleanUp( void );
void    CleanEdges( void );
void    CleanFaces( void );
void    CleanVertices( void );
bool    Collinear( tVertex a, tVertex b, tVertex c );

/*---------------------------------------------------------------------
MakeNullVertex: Makes a vertex, nulls out fields.
---------------------------------------------------------------------*/
tVertex MakeNullVertex( void ){
   tVertex  v;
   NEW( v, tsVertex );
   v->duplicate = NULL;
   v->onhull = !ONHULL;
   v->mark = !PROCESSED;
   HULL_ADD( vertices, v );

   return v;
}

/*---------------------------------------------------------------------
SubVec:  Computes a - b and puts it into c.
---------------------------------------------------------------------*/
void    SubVec( int a[3], int b[3], int c[3]){
   int  i;

   for( i=0; i < 2; i++ )
      c[i] = a[i] - b[i];

}

/*---------------------------------------------------------------------
 DoubleTriangle builds the initial double triangle.  It first finds 3 
 noncollinear points and makes two faces out of them, in opposite order.
 It then finds a fourth point that is not coplanar with that face.  The  
 vertices are stored in the face structure in counterclockwise order so 
 that the volume between the face and the point is negative. Lastly, the
 3 newfaces to the fourth point are constructed and the data structures
 are cleaned up. 
---------------------------------------------------------------------*/
BOOL    DoubleTriangle( void ){
   tVertex  v0, v1, v2, v3, t;
   tFace    f0, f1 = NULL;
   tEdge    e0, e1, e2, s;
   int      vol;
        
   /* Find 3 noncollinear points. */
   v0 = vertices;
   while ( Collinear( v0, v0->next, v0->next->next ) )
      if ( ( v0 = v0->next ) == vertices )
          return FALSE;
   v1 = v0->next;
   v2 = v1->next;
        
   /* Mark the vertices as processed. */
   v0->mark = PROCESSED;
   v1->mark = PROCESSED;
   v2->mark = PROCESSED;
   
   /* Create the two "twin" faces. */
   f0 = MakeFace( v0, v1, v2, f1 );
   f1 = MakeFace( v2, v1, v0, f0 );

   /* Link adjacent face fields. */
   f0->edge[0]->adjface[1] = f1;
   f0->edge[1]->adjface[1] = f1;
   f0->edge[2]->adjface[1] = f1;
   f1->edge[0]->adjface[1] = f0;
   f1->edge[1]->adjface[1] = f0;
   f1->edge[2]->adjface[1] = f0;
        
   /* Find a fourth, noncoplanar point to form tetrahedron. */
   v3 = v2->next;
   vol = VolumeSign( f0, v3 );
   while ( !vol )   {
      if ( ( v3 = v3->next ) == v0 ) 
                  return FALSE;
      vol = VolumeSign( f0, v3 );
   }
        
   /* Insure that v3 will be the first HULL_ADDed. */
   vertices = v3;
   return TRUE; 
}

  
/*---------------------------------------------------------------------
ConstructHull HULL_ADDs the vertices to the hull one at a time.  The hull
vertices are those in the list marked as onhull.
---------------------------------------------------------------------*/
void    ConstructHull( void ){
   tVertex  v, vnext;
   int      vol;
   bool     changed;
   v = vertices;
   do {
      vnext = v->next;
      if ( !v->mark ) {
         v->mark = PROCESSED;
         changed = HULL_ADDOne( v );
             CleanUp();
      }
      v = vnext;
   } while ( v != vertices );
}

/*---------------------------------------------------------------------
HULL_ADDOne is passed a vertex.  It first determines all faces visible from 
that point.  If none are visible then the point is marked as not 
onhull.  Next is a loop over edges.  If both faces adjacent to an edge
are visible, then the edge is marked for deletion.  If just one of the
adjacent faces is visible then a new face is constructed.
---------------------------------------------------------------------*/
bool    HULL_ADDOne( tVertex p )
{
   tFace  f; 
   tEdge  e, temp;
   int    vol;
   bool   vis = FALSE;

   /* Mark faces visible from p. */
   f = faces;
   do {
      vol = VolumeSign( f, p );
      if ( vol < 0 ) {
         f->visible = VISIBLE;  
         vis = TRUE;                      
      }
      f = f->next;
   } while ( f != faces );

   /* If no faces are visible from p, then p is inside the hull. */
   if ( !vis ) {
      p->onhull = !ONHULL;  
      return FALSE; 
   }

   /* Mark edges in interior of visible region for deletion.
      Erect a newface based on each border edge. */
   e = edges;
   do {
      temp = e->next;
      if ( e->adjface[0]->visible && e->adjface[1]->visible )
         /* e interior: mark for deletion. */
         e->HULL_DELETE = REMOVED;
      else if ( e->adjface[0]->visible || e->adjface[1]->visible ) 
         /* e border: make a new face. */
         e->newface = MakeConeFace( e, p );
      e = temp;
   } while ( e != edges );
   return TRUE;
}

/*---------------------------------------------------------------------
VolumeSign returns the sign of the volume of the tetrahedron determined by f
and p.  VolumeSign is +1 iff p is on the negative side of f,
where the positive side is determined by the rh-rule.  So the volume 
is positive if the ccw normal to f points outside the tetrahedron.
The final fewer-multiplications form is due to Bob Williamson.
---------------------------------------------------------------------*/
int  VolumeSign( tFace f, tVertex p ){
   double  vol;
   int     voli;
   double  ax, ay, az, bx, by, bz, cx, cy, cz;

   ax = f->vertex[0]->v[X] - p->v[X];
   ay = f->vertex[0]->v[Y] - p->v[Y];
   az = f->vertex[0]->v[Z] - p->v[Z];
   bx = f->vertex[1]->v[X] - p->v[X];
   by = f->vertex[1]->v[Y] - p->v[Y];
   bz = f->vertex[1]->v[Z] - p->v[Z];
   cx = f->vertex[2]->v[X] - p->v[X];
   cy = f->vertex[2]->v[Y] - p->v[Y];
   cz = f->vertex[2]->v[Z] - p->v[Z];

   vol =   ax * (by*cz - bz*cy)
         + ay * (bz*cx - bx*cz)
         + az * (bx*cy - by*cx);

   /* The volume should be an integer. */
   if      ( vol >  0.5 )  return  1;
   else if ( vol < -0.5 )  return -1;
   else                    return  0;
}
/*---------------------------------------------------------------------
Same computation, but computes using ints, and returns the actual volume.
---------------------------------------------------------------------*/
int  Volumei( tFace f, tVertex p ){
   int  vol;
   int  ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz;

   ax = f->vertex[0]->v[X] - p->v[X];
   ay = f->vertex[0]->v[Y] - p->v[Y];
   az = f->vertex[0]->v[Z] - p->v[Z];
   bx = f->vertex[1]->v[X] - p->v[X];
   by = f->vertex[1]->v[Y] - p->v[Y];
   bz = f->vertex[1]->v[Z] - p->v[Z];
   cx = f->vertex[2]->v[X] - p->v[X];
   cy = f->vertex[2]->v[Y] - p->v[Y];
   cz = f->vertex[2]->v[Z] - p->v[Z];

   vol =  (ax * (by*cz - bz*cy)
         + ay * (bz*cx - bx*cz)
         + az * (bx*cy - by*cx));

   return vol;
}

/*---------------------------------------------------------------------
MakeConeFace makes a new face and two new edges between the 
edge and the point that are passed to it. It returns a pointer to
the new face.
---------------------------------------------------------------------*/
tFace   MakeConeFace( tEdge e, tVertex p )
{
   tEdge  new_edge[2];
   tFace  new_face;
   int    i, j;

   /* Make two new edges (if don't already exist). */
   for ( i=0; i < 2; ++i ) 
      /* If the edge exists, copy it into new_edge. */
      if ( !( new_edge[i] = e->endpts[i]->duplicate) ) {
         /* Otherwise (duplicate is NULL), MakeNullEdge. */
         new_edge[i] = MakeNullEdge();
         new_edge[i]->endpts[0] = e->endpts[i];
         new_edge[i]->endpts[1] = p;
         e->endpts[i]->duplicate = new_edge[i];
      }

   /* Make the new face. */
   new_face = MakeNullFace();   
   new_face->edge[0] = e;
   new_face->edge[1] = new_edge[0];
   new_face->edge[2] = new_edge[1];
   MakeCcw( new_face, e, p ); 
        
   /* Set the adjacent face pointers. */
   for ( i=0; i < 2; ++i )
      for ( j=0; j < 2; ++j )  
         /* Only one NULL link should be set to new_face. */
         if ( !new_edge[i]->adjface[j] ) {
            new_edge[i]->adjface[j] = new_face;
            break;
         }
        
   return new_face;
}

/*---------------------------------------------------------------------
MakeCcw puts the vertices in the face structure in counterclock wise 
order.  We want to store the vertices in the same 
order as in the visible face.  The third vertex is always p.

Although no specific ordering of the edges of a face are used
by the code, the following condition is maintained for each face f:
one of the two endpoints of f->edge[i] matches f->vertex[i]. 
But note that this does not imply that f->edge[i] is between
f->vertex[i] and f->vertex[(i+1)%3].  (Thanks to Bob Williamson.)
---------------------------------------------------------------------*/
void    MakeCcw( tFace f, tEdge e, tVertex p )
{
   tFace  fv;   /* The visible face adjacent to e */
   int    i;    /* Index of e->endpoint[0] in fv. */
   tEdge  s;    /* Temporary, for swapping */
      
   if  ( e->adjface[0]->visible )      
        fv = e->adjface[0];
   else fv = e->adjface[1];
       
   /* Set vertex[0] & [1] of f to have the same orientation
      as do the corresponding vertices of fv. */ 
   for ( i=0; fv->vertex[i] != e->endpts[0]; ++i )
      ;
   /* Orient f the same as fv. */
   if ( fv->vertex[ (i+1) % 3 ] != e->endpts[1] ) {
      f->vertex[0] = e->endpts[1];  
      f->vertex[1] = e->endpts[0];    
   }
   else {                               
      f->vertex[0] = e->endpts[0];   
      f->vertex[1] = e->endpts[1];      
      SWAP( s, f->edge[1], f->edge[2] );
   }
   /* This swap is tricky. e is edge[0]. edge[1] is based on endpt[0],
      edge[2] on endpt[1].  So if e is oriented "forwards," we
      need to move edge[1] to follow [0], because it precedes. */
   
   f->vertex[2] = p;
}
 
/*---------------------------------------------------------------------
MakeNullEdge creates a new cell and initializes all pointers to NULL
and sets all flags to off.  It returns a pointer to the empty cell.
---------------------------------------------------------------------*/
tEdge   MakeNullEdge( void )
{
   tEdge  e;

   NEW( e, tsEdge );
   e->adjface[0] = e->adjface[1] = e->newface = NULL;
   e->endpts[0] = e->endpts[1] = NULL;
   e->HULL_DELETE = !REMOVED;
   HULL_ADD( edges, e );
   return e;
}

/*--------------------------------------------------------------------
MakeNullFace creates a new face structure and initializes all of its
flags to NULL and sets all the flags to off.  It returns a pointer
to the empty cell.
---------------------------------------------------------------------*/
tFace   MakeNullFace( void ){
   tFace  f;
   int    i;

   NEW( f, tsFace);
   for ( i=0; i < 3; ++i ) {
      f->edge[i] = NULL;
      f->vertex[i] = NULL;
   }
   f->visible = !VISIBLE;
   HULL_ADD( faces, f );
   return f;
}

/*---------------------------------------------------------------------
MakeFace creates a new face structure from three vertices (in ccw
order).  It returns a pointer to the face.
---------------------------------------------------------------------*/
tFace   MakeFace( tVertex v0, tVertex v1, tVertex v2, tFace fold ){
   tFace  f;
   tEdge  e0, e1, e2;

   /* Create edges of the initial triangle. */
   if( !fold ) {
     e0 = MakeNullEdge();
     e1 = MakeNullEdge();
     e2 = MakeNullEdge();
   }
   else { /* Copy from fold, in reverse order. */
     e0 = fold->edge[2];
     e1 = fold->edge[1];
     e2 = fold->edge[0];
   }
   e0->endpts[0] = v0;              e0->endpts[1] = v1;
   e1->endpts[0] = v1;              e1->endpts[1] = v2;
   e2->endpts[0] = v2;              e2->endpts[1] = v0;
        
   /* Create face for triangle. */
   f = MakeNullFace();
   f->edge[0]   = e0;  f->edge[1]   = e1; f->edge[2]   = e2;
   f->vertex[0] = v0;  f->vertex[1] = v1; f->vertex[2] = v2;
        
   /* Link edges to face. */
   e0->adjface[0] = e1->adjface[0] = e2->adjface[0] = f;
        
   return f;
}

/*---------------------------------------------------------------------
CleanUp goes through each data structure list and clears all
flags and NULLs out some pointers.  The order of processing
(edges, faces, vertices) is important.
---------------------------------------------------------------------*/
void    CleanUp( void ){
   CleanEdges();
   CleanFaces();
   CleanVertices();
}

/*---------------------------------------------------------------------
CleanEdges runs through the edge list and cleans up the structure.
If there is a newface then it will put that face in place of the 
visible face and NULL out newface. It also HULL_DELETEs so marked edges.
---------------------------------------------------------------------*/
void    CleanEdges( void ){
   tEdge  e;    /* Primary index into edge list. */
   tEdge  t;    /* Temporary edge pointer. */
                
   /* Integrate the newface's into the data structure. */
   /* Check every edge. */
   e = edges;
   do {
      if ( e->newface ) { 
         if ( e->adjface[0]->visible )
            e->adjface[0] = e->newface; 
         else   e->adjface[1] = e->newface;
         e->newface = NULL;
      }
      e = e->next;
   } while ( e != edges );

   /* HULL_DELETE any edges marked for deletion. */
   while ( edges && edges->HULL_DELETE ) { 
      e = edges;
      HULL_DELETE( edges, e );
   }
   e = edges->next;
   do {
      if ( e->HULL_DELETE ) {
         t = e;
         e = e->next;
         HULL_DELETE( edges, t );
      }
      else e = e->next;
   } while ( e != edges );
}

/*---------------------------------------------------------------------
CleanFaces runs through the face list and HULL_DELETEs any face marked visible.
---------------------------------------------------------------------*/
void    CleanFaces( void ){
   tFace  f;    /* Primary pointer into face list. */
   tFace  t;    /* Temporary pointer, for deleting. */
   while ( faces && faces->visible ) { 
      f = faces;
      HULL_DELETE( faces, f );
   }
   f = faces->next;
   do {
      if ( f->visible ) {
         t = f;
         f = f->next;
         HULL_DELETE( faces, t );
      }
      else f = f->next;
   } while ( f != faces );
}

/*---------------------------------------------------------------------
CleanVertices runs through the vertex list and HULL_DELETEs the 
vertices that are marked as processed but are not incident to any 
unHULL_DELETEd edges. 
---------------------------------------------------------------------*/
void    CleanVertices( void ){
   tEdge    e;
   tVertex  v, t;
        
   /* Mark all vertices incident to some unHULL_DELETEd edge as on the hull. */
   e = edges;
   do {
      e->endpts[0]->onhull = e->endpts[1]->onhull = ONHULL;
      e = e->next;
   } while (e != edges);
        
   /* HULL_DELETE all vertices that have been processed but
      are not on the hull. */
   while ( vertices && vertices->mark && !vertices->onhull ) { 
      v = vertices;
      HULL_DELETE( vertices, v );
   }
   v = vertices->next;
   do {
      if ( v->mark && !v->onhull ) {    
         t = v; 
         v = v->next;
         HULL_DELETE( vertices, t )
      }
      else v = v->next;
   } while ( v != vertices );
        
   /* Reset flags. */
   v = vertices;
   do {
      v->duplicate = NULL; 
      v->onhull = !ONHULL; 
      v = v->next;
   } while ( v != vertices );
}

/*---------------------------------------------------------------------
Collinear checks to see if the three points given are collinear,
by checking to see if each element of the cross product is zero.
---------------------------------------------------------------------*/
bool    Collinear( tVertex a, tVertex b, tVertex c )
{
   return 
         ( c->v[Z] - a->v[Z] ) * ( b->v[Y] - a->v[Y] ) -
         ( b->v[Z] - a->v[Z] ) * ( c->v[Y] - a->v[Y] ) == 0
      && ( b->v[Z] - a->v[Z] ) * ( c->v[X] - a->v[X] ) -
         ( b->v[X] - a->v[X] ) * ( c->v[Z] - a->v[Z] ) == 0
      && ( b->v[X] - a->v[X] ) * ( c->v[Y] - a->v[Y] ) -
         ( b->v[Y] - a->v[Y] ) * ( c->v[X] - a->v[X] ) == 0  ;
}