/*****************************************************************************
*   "Irit" - the 3d (not only polygonal) solid modeller.		     *
*									     *
* Written by:  Gershon Elber				Ver 0.2, Mar. 1990   *
******************************************************************************
*   Module to handle the low level boolean operations. The routines in this  *
* module should be accessed from "bool-hi.c" module only.		     *
*   Note the polygons of the two given objects may not be convex, and must   *
* be subdivided into convex ones in the boolean upper level routines (module *
* bool-hi.c). All the routines of this module expects objects with convex    *
* polygons only although they might return objects with non convex polygons, *
* but marked as so (via polygons CONVEX tags - see IPPolygonStruct def.)!    *
*   Because Bool-low.c module was too big, it was subdivided to two:	     *
* Bool1Low.c - mainly handles the intersecting polyline between the oprnds.  *
* Bool2Low.c - mainly handles the polygon extraction from operands given the *
*	       polyline of intersection and the adjacencies (see ADJACNCY.C) *
*****************************************************************************/

/* #define DEBUG	    If defined, return intersection POLYLINE object. */
/* #define DEBUG2	         If defined, defines some printing routines. */
/* #define DEBUG3	         Print messages to entry/exit from routines. */

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include "irit_sm.h"
#include "allocate.h"
#include "bool_loc.h"
#include "convex.h"
#include "geomat3d.h"
#include "intrnrml.h"

static IPVertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead);
static int TestAinB(IPVertexStruct *V, IPPolygonStruct *Pl, int AinB);
static IPPolygonStruct *ClipOpenLoopFromPoly(IPPolygonStruct *Pl,
					     InterSegListStruct *OLoop,
					     int AinB);
static void ClosedLoopsToPolys(InterSegListStruct *PClosed,
			       IPPolygonStruct *Pl);
static IPVertexStruct *GenReverseVrtxList(IPVertexStruct *VIn);
static IPVertexStruct *CutPolygonAtRay(IPPolygonStruct *Pl, PointType Pt);
static int CombineClosedLoops(IPPolygonStruct *Pl,
			      InterSegListStruct *PClosed,
			      int AinB);
static void PushAdjOnStack(IPPolygonStruct *Pl,
			   IPPolygonStruct *AdjStack[],
			   int *StackPointer);
static IPPolygonStruct *ChainPolyLists(IPPolygonStruct *Pl1,
				       IPPolygonStruct *Pl2);

#ifdef DEBUG
void BoolPrintVrtxList(IPVertexStruct *V);
void BoolPrintInterList(InterSegmentStruct *PInt);
#endif /* DEBUG */

/*****************************************************************************
* DESCRIPTION:                                                               *
* Test on which side of polygon Pl, given Point V is, and according to       *
* the requirement (AinB) returns TRUE/FALSE.				     *
*   If test on V fails, we tries the next one V -> Pnext until success...    *
*                                                                            *
* PARAMETERS:                                                                *
*   V:       Is V inside/outside polygon Pl?                                 *
*   Pl:      The polygon to test for inclusion.                              *
*   AinB:    Either test for inclusion (TRUE) or exclusion (FALSE).          *
*                                                                            *
* RETURN VALUE:                                                              *
*   int:     TRUE if V relates to PL as AinB, FALSE otherwise.               *
*****************************************************************************/
static int TestAinB(IPVertexStruct *V, IPPolygonStruct *Pl, int AinB)
{
    int In;
    RealType Distance;
    IPVertexStruct
	*VHead = V;

    do {
	Distance = Pl -> Plane[0] * V -> Coord[0] +
		   Pl -> Plane[1] * V -> Coord[1] +
		   Pl -> Plane[2] * V -> Coord[2] + Pl -> Plane[3];
	In = Distance > 0.0;
	V = V -> Pnext;
    }
    while (ABS(Distance) < BOOL_EPSILON && V != NULL && V != VHead);

    if (ABS(Distance) < BOOL_EPSILON)
	IritFatalError("TestAInB: Failed to find non coplanar point.");

    return (In && AinB) || (!In && !AinB);   /* I wish I had logical XOR ... */
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Converts an intersection loop into an open vertex list.		     *
*                                                                            *
* PARAMETERS:                                                                *
*   PIHead:  Intersection list to be converted.                              *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPVertexStruct *: The same loop as a vertex list.                        *
*                                                                            *
* KEYWORDS:                                                                  *
*   InterLoopToVrtxList                                                      *
*****************************************************************************/
static IPVertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead)
{
    IPVertexStruct *VHead, *V;

    VHead = V = IPAllocVertex(0, 0, NULL, NULL);

    PT_COPY(VHead -> Coord, PIHead -> PtSeg[0]);

    while (PIHead != NULL) {
	V -> Pnext = IPAllocVertex(0, 0, NULL, NULL);
	V = V -> Pnext;
	PT_COPY(V -> Coord, PIHead -> PtSeg[1]);

	PIHead = PIHead -> Pnext;
    }

    V -> Pnext = NULL;

    return VHead;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Clip an open loop from a polygon:					     *
* 1. Clip the section (S) of the polygon between the two end points of the   *
*    loop end points and replace it by the loop itself.			     *
* 2. If the polygon formed from S and the loop should be in the output       *
*    (as tested by AinB) returns that polygon. Otherwise returns NULL.	     *
*   The open loop itself (excluding the header OLoop) is freed.		     *
* Note it is assumed (ordered by the sorting routines above) that the open   *
* loop starts from the second end back to first end:			     *
*									     *
*			       L1-----------------------L2		     *
*				|			|		     *
*				|L0			|L3		     *
*	*---------------*-------+----*-------------*----+-----------*	     *
*	P0		P1	     P2		   P3		    P0	     *
*                                                                            *
* PARAMETERS:                                                                *
*   Pl:        To clip against the given open loop.                          *
*   OLoop:     The given open loop (must start/end on Pl's boundary).        *
*   AinB:      TRUE for inclusion, FALSE for exclusion.                      *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPPolygonStruct: The newly created clipped polygon if AinB, or NULL      *
*                    otherwise.                                              *
*****************************************************************************/
static IPPolygonStruct *ClipOpenLoopFromPoly(IPPolygonStruct *Pl,
					     InterSegListStruct *OLoop,
					     int AinB)
{
    int GenClipPoly;	    /* TRUE if needs to form polygon from S & OLoop. */
    IPVertexStruct *VStart, *VEnd, *VEnd1,    /* Corresponds to L0 and L3... */
	*ClipPoly,			/* The clipped element from polygon. */
	*PLoop,				  /* The loop itself as vertex list. */
	*PLoopEnd, *PLoopEnd1, *Ptemp1, *Ptemp2,
	*PRevLoop = NULL;
    InterSegmentStruct *PISeg, *PItemp;
    IPPolygonStruct *ClipPl;

#ifdef DEBUG3
    printf("Enter ClipOpenLoopFromPoly\n");
#endif /* DEBUG3 */

    PISeg = OLoop -> PISeg;
    VStart = PISeg -> V[0];
    while (PISeg -> Pnext != NULL) PISeg = PISeg -> Pnext;
    VEnd = PISeg -> V[1];
    if (VStart == NULL || VEnd == NULL)
	IritFatalError("ClipOpenLoopFromPoly: None open loop");
    VEnd1 = VEnd;		   /* Find the pointer thats points on VEnd. */
    while (VEnd1 -> Pnext != VEnd) VEnd1 = VEnd1 -> Pnext;

    PLoop = InterLoopToVrtxList(OLoop -> PISeg);/* Make vertex list out of it*/
    PLoopEnd = PLoop;			  /* Prepare pointer on last vertex. */
    while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
    PLoopEnd1 = PLoop;
    while (PLoopEnd1 -> Pnext != PLoopEnd) PLoopEnd1 = PLoopEnd1 -> Pnext;

    if (VStart != VEnd) {
	/* Now we test if we need to create a polygon formed from S & open   */
	/* loop by testing on which side of the polygon that caused	     */
	/* intersection L0L1, point P2 is, and compare with requirement AinB.*/
	GenClipPoly = TestAinB(VStart -> Pnext, OLoop -> PISeg -> Pl, AinB);

	/* Keep the clipped VertexList P2, P3 & substitute with open loop:   */
	/* Note we must keep vertex VEnd in the polygon as another InterSeg. */
	/* may point on it, so we replace InterSeg point (L3) by (P3) and    */
	/* leave VEnd intact.						     */
	Ptemp1 = VEnd -> Pnext;		     /* Save that pointer temporary. */
	VEnd -> Pnext = NULL;		   /* Close the clipped vertex list. */

	PT_SWAP(VEnd -> Coord, PLoopEnd -> Coord);
	PT_SWAP(VEnd -> Normal, PLoopEnd -> Normal);
	VEnd1 -> Pnext = PLoopEnd;
	PLoopEnd1 -> Pnext = VEnd;
	PLoopEnd -> Count = VEnd -> Count;
	PLoopEnd -> Tags = VEnd -> Tags;

	Ptemp2 = VEnd;
	VEnd = PLoopEnd;
	PLoopEnd = Ptemp2;

	ClipPoly = VStart -> Pnext;

	/* New ClipPoly is isolated (Open loop of P2, P3 only). Save	     */
	/* reversed list of open loop if we need to form an S/OLoop polygon, */
	/* otherwise free ClipPoly. Chain the OLoop instead of S.	     */
	if (GenClipPoly)
	    PRevLoop = GenReverseVrtxList(PLoop);
	else
	    IPFreeVertexList(ClipPoly);
	VStart -> Pnext = PLoop;	    /* Chain the OLoop instead of S. */
	PLoopEnd -> Pnext = Ptemp1;
    }
    else { /* VStart == VEnd */
	/* Now we test if we need to create a polygon formed from S & open   */
	/* loop by testing on which side of the polygon that caused	     */
	/* intersection L0L1, point L3 is, and compare with requirement AinB.*/
	GenClipPoly = TestAinB(PLoopEnd, OLoop -> PISeg -> Pl, AinB);

	/* In this case the clipped part is empty, so its simpler: */
	ClipPoly = NULL;

	/* Save reversed list of open loop if we need to form an S/OLoop     */
	/* polygon. Chain the OLoop instead of S.			     */
	if (GenClipPoly)
	    PRevLoop = GenReverseVrtxList(PLoop);

	PLoopEnd -> Pnext = VEnd -> Pnext;
	PLoopEnd -> Tags = VEnd -> Tags;
	VStart -> Pnext = PLoop;	    /* Chain the OLoop instead of S. */
    }

    /* Time to free the InterSegment list pointed by OLoop: */
    PISeg = OLoop -> PISeg;
    while (PISeg != NULL) {
	PItemp = PISeg;
	PISeg = PISeg -> Pnext;
	IritFree((VoidPtr) PItemp);
    }
    OLoop -> PISeg = NULL;			/* To be on the safe side... */

    /* There is a chance that Pl -> PVertex will point on vertex in clipped  */
    /* part so we update it to point on VStart, which for sure is in polygon.*/
    Pl -> PVertex = VStart;
    if (GenClipPoly) {	   /* Generate the polygon from ClipPoly & PRevLoop: */
	PLoopEnd = PRevLoop;
	while (PLoopEnd -> Pnext != NULL)
	    PLoopEnd = PLoopEnd -> Pnext;

	if (ClipPoly == NULL) {
	    PLoopEnd -> Pnext = PRevLoop;  /* Close that loop and return it. */
	    ClipPl = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
				    PRevLoop, NULL);
	    PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
	    IP_RST_CONVEX_POLY(ClipPl);		   /* May be not convex now. */
	    return ClipPl;
	}

	PLoopEnd -> Pnext = ClipPoly;
	PLoopEnd -> Tags = VStart -> Tags;
	PLoopEnd -> Count = VStart -> Count;
	Ptemp1 = ClipPoly;
	while (Ptemp1 -> Pnext != NULL) Ptemp1 = Ptemp1 -> Pnext;
	Ptemp1 -> Pnext = PRevLoop;

	ClipPl = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
				ClipPoly, NULL);
	PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
	IP_RST_CONVEX_POLY(ClipPl);		   /* May be not convex now. */
	return ClipPl;
    }
    else
	return NULL;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Creates a new vertex list, in reverse order. The original list is not    *
* modified.                                                                  *
*                                                                            *
* PARAMETERS:                                                                *
*   VIn:      To create a reversed list for.                                 *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPVertexStruct *: The newly created reversed list.                       *
*****************************************************************************/
static IPVertexStruct *GenReverseVrtxList(IPVertexStruct *VIn)
{
    IPVertexStruct *VOutHead, *VOut;

    VOutHead = IPAllocVertex(0, 0, NULL, NULL);

    PT_COPY(VOutHead -> Coord, VIn -> Coord);
    VIn = VIn -> Pnext;

    while (VIn != NULL) {
	VOut = IPAllocVertex(0, 0, NULL, NULL);
	PT_COPY(VOut -> Coord, VIn -> Coord);
	PT_COPY(VOut -> Normal, VIn -> Normal);

	VOut -> Pnext = VOutHead;	     /* Chain them in reverse order. */
	VOutHead = VOut;

	VIn = VIn -> Pnext;
    }

    return VOutHead;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Finds the intersection of the ray fired from Pt to +X direction with the *
* given polygon. Note Pt MUST be in the polygon. Two vertices equal to	     *
* ray/polygon intersection point are added to polygon vertex list, and a     *
* pointer to the first one is also returned. This routine is exclusively     *
* used by the CombineClosedLoops below.					     *
*   The polygon is NOT assumed to be convex and we look for the minimum X    *
* intersection. The polygon might not be convex as a result of combinning    *
* some other closed loop before we got to do this test.			     *
*                                                                            *
* PARAMETERS:                                                                *
*   Pl:     The polygon to compute the ray intersection with.                *
*   Pt:     The origin of the ray point.                                     *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPVertexStruct *:  The added vertex on Pl where the intersection with    *
*                      the ray occured.                                      *
*****************************************************************************/
static IPVertexStruct *CutPolygonAtRay(IPPolygonStruct *Pl, PointType Pt)
{
    int OnVertex = FALSE;
    RealType X,
	MinX = INFINITY;
    IPVertexStruct *V, *Vnext,
	*VMinX = NULL;

    V = Pl -> PVertex;
    do {
	Vnext = V -> Pnext;

	/* A polygon edge might intersect the ray iff one of the following:  */
	/* 1. The first vertex is exactly on the ray Y level. (if this is    */
	/*    true for the second edge, it will be detected next iteration). */
	/* 2. The first vertex is below ray Y level, and second is above.    */
	/* 3. The first vertex is above ray Y level, and second is below.    */
	if (BOOL_APX_EQ(V -> Coord[1], Pt[1])) {	    /* Case 1 above. */
	    if (MinX > V -> Coord[0] && Pt[0] < V -> Coord[0]) {
		OnVertex = TRUE;
		MinX = V -> Coord[0];
		VMinX = V;
	    }
	}
	else if ((V -> Coord[1] < Pt[1] &&
		  Vnext -> Coord[1] > Pt[1]) || /* Case 2. */
		 (V -> Coord[1] > Pt[1] &&
		  Vnext -> Coord[1] < Pt[1])) { /* Case 3. */
	    X = ((Vnext -> Coord[1] - Pt[1]) * V -> Coord[0] +
		 (Pt[1] - V -> Coord[1]) * Vnext -> Coord[0]) /
		(Vnext -> Coord[1] - V -> Coord[1]);
	    if (MinX > X && Pt[0] < X) {
		OnVertex = FALSE;
		MinX = X;
		VMinX = V;
	    }

	}

	V = Vnext;
    }
    while (V != NULL && V != Pl -> PVertex);

    if ((V = VMinX) == NULL)
	IritFatalError("CutPolygonAtRay: fail to find intersection");

    /* Now that we have the intersection point - create two new vertices     */
    /* (one if OnVertex), insert them (it) after V and return the first.     */
    if (OnVertex) {
	V -> Pnext = IPAllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
	PT_COPY(V -> Pnext -> Coord, V -> Coord);
	PT_CLEAR(V -> Pnext -> Normal);
	V -> Tags = V -> Count = 0;
    }
    else {
	V -> Pnext = IPAllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
	Vnext = V -> Pnext;
	Vnext -> Coord[0] = MinX;	 /* X - as intersection point found. */
	Vnext -> Coord[1] = Pt[1];	      /* Y - must be as ray Y level. */
	Vnext -> Coord[2] = V -> Coord[2];/* Z - all polys has same Z value. */

	V -> Pnext = IPAllocVertex(0, 0, NULL, V -> Pnext);
	V = V -> Pnext;
	PT_COPY(V -> Coord, Vnext -> Coord);
	PT_CLEAR(V -> Normal);
    }

    return V;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Converts the given closed loop list to polygons, and returns them. The   *
* original given polygon's vertex list is freed, and the first loop is       *
* substituted instead.							     *
*                                                                            *
* PARAMETERS:                                                                *
*   PClosed:   To substitute into polygon Pl.                                *
*   Pl:        Polygon whose vertices are to be replaced by PClosed loops.   *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void ClosedLoopsToPolys(InterSegListStruct *PClosed,
			       IPPolygonStruct *Pl)
{
    int LoopNum = 0;
    IPVertexStruct *V, *VHead;
    InterSegmentStruct *PISeg, *PItemp;
    InterSegListStruct *PClosedTemp;

    IPFreeVertexList(Pl -> PVertex);

    SET_INOUTPUT_POLY(Pl);		   /* Mark the polygon as in output. */

    while (PClosed != NULL) {
	/* Convert the InterList to vertex list and free the first: */
	V = VHead = InterLoopToVrtxList(PClosed -> PISeg);
	if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
	    IritFatalError("ClosedLoopsToPolys: Closed loop with less than 3 vertices");

	PISeg = PClosed -> PISeg;      /* Time to free the InterSegmentList: */
	while (PISeg != NULL) {
	    PItemp = PISeg;
	    PISeg = PISeg -> Pnext;
	    IritFree((VoidPtr) PItemp);
	}

	while (V -> Pnext -> Pnext != NULL)
	    V = V -> Pnext;				   /* Go to last pt. */
	IPFreeVertex(V -> Pnext);		/* and free - same as first. */
	V -> Pnext = VHead;		       /* Make vertex list circular. */

	if (LoopNum++) {
	    Pl -> Pnext = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
					 VHead, Pl -> Pnext);
	    PLANE_COPY(Pl -> Pnext -> Plane, Pl -> Plane);
	}
	else {
	    Pl -> PVertex = VHead;
	}

	PClosedTemp = PClosed;
	PClosed = PClosed -> Pnext;
	IritFree((VoidPtr) PClosedTemp);
    }
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   This routines cuts the given polygon into its interior closed loops by   *
* adding an edge from the polygon boundary to each of its closed loops.      *
*   For example:							     *
*									     *
* +-----------------------+      +-----------------------+		     *
* |                       |	 |                       |		     *
* |  / \         / \      |	 |  / \________ / \      |		     *
* |  \ /        |   |     |	 |  \ /        |   |_____|		     *
* |      _       \ /      | -->  |      _       \ /      |		     *
* |     / \_              | -->  |     / \_              |		     *
* |    |    |             |	 |    |    |_____________|		     *
* |     \__/              |	 |     \__/              |		     *
* |                       |      |                       |		     *
* +-----------------------+      +-----------------------+		     *
*									     *
*   Algorithm:								     *
* 1. Transform the polygon and the closed loops to a plane parallel to XY    *
*    plane (Z = Const plane).						     *
* 2. For each loop find its MaxX while keeping the information on the        *
*    vertex on that extremum.						     *
* 3. For the loop with the biggest MaxX:				     *
*    3.1. Use that extremum vertex (which must be non concave corner) to     *
*         test if loop is in the reverse direction the polygon itself is,    *
*         and reverse it if not.					     *
*    3.2. Fire a ray from the extremum vertex, to the +X direction outside   *
*         of the loop till it intersect the polygon, break the polygon at    *
*         that point and add two edges to beginning of loop from breaking    *
*         point and from end of loop to breaking point (beginning/end point  *
*	  of loop is the extremum vertex point).			     *
* 4. Repeat step 3, with all loops.					     *
* 5. Transfrom the new polygon back (using the inverse matrix of step 1)     *
*    to its original orientation.					     *
*									     *
* PARAMETERS:                                                                *
*   Pl:        Polygon to comine with the given closed loops, in place.      *
*   PClosed:   Closed loops in polygon Pl.                                   *
*   AinB:      Do we want inclusion or exclusion?                            *
*                                                                            *
* RETURN VALUE:                                                              *
*   int:       TRUE iff the original polygon boundary is in output.	     *
*****************************************************************************/
static int CombineClosedLoops(IPPolygonStruct *Pl,
			      InterSegListStruct *PClosed,
			      int AinB)
{
    RealType MaxX;
    PointType V1, V2, Normal, PlNormal;
    MatrixType RotMat;
    IPVertexStruct *V, *Vnext, *Vprev, *VHead, *VMaxX, VStruct;
    InterSegListStruct *PClosedTemp, *PClosedMaxX, *PClosedLast,
	*PClosedMaxXLast = NULL;
    InterSegmentStruct *PISeg, *PItemp, *PISegMaxX;

    /* Stage 1 - Transform the vertices to a plane parallel to XY plane: */
    GenRotateMatrix(RotMat, Pl -> Plane);
    V = VHead = Pl -> PVertex;
    do {				    /* Transform the polygon itself. */
	MatMultVecby4by4(V -> Coord, V -> Coord, RotMat);
	V = V -> Pnext;
    }
    while (V != NULL && V != VHead);

    PClosedTemp = PClosed;
    while (PClosedTemp != NULL) {	    /* And transform the loops also. */
	PISeg = PClosed -> PISeg;
	while (PISeg != NULL) {
	    MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
	    MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);

	    PISeg = PISeg -> Pnext;
	}

	PClosedTemp = PClosedTemp -> Pnext;
    }
    if (!MatInverseMatrix(RotMat, RotMat))	 /* Find the inverse matrix. */
	IritFatalError("CombineClosedLoops: Inverse matrix does not exists");

    /* Evalaute the normal to the polygon (which must be convex!). Note we   */
    /* cannt simply use the Plane normal as the polygon was transformed.     */
    V = Pl -> PVertex;
    do {
	Vnext = V -> Pnext;
	PT_SUB(V1, Vnext -> Coord, V -> Coord);
	PT_SUB(V2, Vnext -> Pnext -> Coord, Vnext -> Coord);
	GMVecCrossProd(PlNormal, V1, V2);
	V = Vnext;
    }
    while (PT_LENGTH(PlNormal) < BOOL_EPSILON);

    PClosedTemp = PClosed;
    while (PClosedTemp != NULL) {
	/* Stage 2 - find MaxX extremum value of given loop, test the loop   */
	/* direction, and reverse it if wrong. Note we convert the loop      */
	/* given as InterSegListStruct list into IPVertexStruct list first.  */
	PISegMaxX = PISeg = PClosedTemp -> PISeg;
	MaxX = PISeg -> PtSeg[0][0];		  /* Get first vertex X val. */
	PISeg = PISeg -> Pnext;
	while (PISeg)
	{
	    if (PISeg -> PtSeg[0][0] > MaxX) {
		MaxX = PISeg -> PtSeg[0][0];
		PISegMaxX = PISeg;
	    }
	    PISeg = PISeg -> Pnext;
	}
	PClosedTemp -> PISegMaxX = PISegMaxX;

	PClosedTemp = PClosedTemp -> Pnext;
    }

    /* Stage 3/4 - find the loop with biggest MaxX and combine it with the   */
    /* polygon itself. Do it for all closed loops, in list:		     */
    while (PClosed != NULL) {
	/* Find the one with maximum MaxX, and delete it from PClosed list.  */
	PClosedLast = PClosedMaxX = PClosedTemp = PClosed;
	MaxX = PClosedMaxX -> PISegMaxX -> PtSeg[0][0];
	while (PClosedTemp != NULL)
	{
	    if (PClosedTemp -> PISegMaxX -> PtSeg[0][0] > MaxX) {
		PClosedMaxX = PClosedTemp;
		PClosedMaxXLast = PClosedLast;
	    }
	    PClosedLast = PClosedTemp;
	    PClosedTemp = PClosedTemp -> Pnext;
	}
	if (PClosedMaxX == PClosed)
	    PClosed = PClosed -> Pnext;			        /* Del. from */
	else
	    PClosedMaxXLast -> Pnext = PClosedMaxX -> Pnext; /* PClosed list.*/

	/* Create a vertex list from the loop: */
	V = VHead = InterLoopToVrtxList(PClosedMaxX -> PISeg);
	if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
	    IritFatalError("CombineClosedLoops: Closed loop with less than 3 vertices");

	V = VHead;
	while (V -> Pnext -> Pnext != NULL)
	    V = V -> Pnext;				   /* Go to last pt. */
	IPFreeVertex(V -> Pnext);		/* and free - same as first. */
	V -> Pnext = VHead;		       /* Make vertex list circular. */

	PISegMaxX = PClosedMaxX -> PISegMaxX;

	/* Now test if the vertex list should be reversed. Find the vertices */
	/* which form the PISegMaxX segment, so V -> Pnext is the first      */
        /* vertex in PISegMaxX segment. Then the 3 vertices V , V -> Pnext   */
        /* (on PISegMaxX), V -> Pnext -> Pnext (on PISegMaxX), must form     */
	/* convex corner which we use to test if loop needs to be reversed:  */
	while (!BOOL_PT_APX_EQ(V -> Pnext -> Coord, PISegMaxX -> PtSeg[0]))
    	    V = V -> Pnext;
	VMaxX = V -> Pnext;

	/* Prepare in point in REAL position. */
	PT_COPY(VStruct.Coord, V -> Coord);
	MatMultVecby4by4(VStruct.Coord, VStruct.Coord, RotMat);
	VStruct.Pnext = NULL;
	if (TestAinB(&VStruct, PISegMaxX -> Pl, AinB)) {
	    /* The Inside of the object is actually the loop itself. In that */
	    /* case we simply return all the loops converted into polygon.   */
	    /* This case is simple...					     */
	    IPFreeVertexList(VHead);		   /* Free loop vertex list. */
	    PClosedMaxX -> Pnext = PClosed;/* Put back first loop into list. */
	    PClosedTemp = PClosed = PClosedMaxX;
	    while (PClosedTemp != NULL) {	/* Transform the loops back. */
		PISeg = PClosed -> PISeg;
		while (PISeg != NULL) {
		    MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0],
				     RotMat);
		    MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1],
				     RotMat);

		    PISeg = PISeg -> Pnext;
		}
		PClosedTemp = PClosedTemp -> Pnext;
	    }

	    ClosedLoopsToPolys(PClosedMaxX, Pl);/* And convert them to polys.*/
	    return FALSE;	   /* Boundary is NOT part of object result. */
	}
	PT_SUB(V1, VMaxX -> Coord, V -> Coord);
	PT_SUB(V2, VMaxX -> Pnext -> Coord, VMaxX -> Coord);
	GMVecCrossProd(Normal, V1, V2);
	if (DOT_PROD(Normal, PlNormal) > 0) {	    /* Need to reverse list. */
	    Vprev = VHead;
	    V = Vprev -> Pnext;
	    Vnext = V -> Pnext;
	    do {
		V -> Pnext = Vprev;/* Reverse to point on prev instead next. */
		Vprev = V;
		V = Vnext;
		Vnext = V -> Pnext;
	    }
	    while (Vprev != VHead);
	}

	PISeg = PClosedMaxX -> PISeg;  /* Time to free the InterSegmentList: */
	while (PISeg != NULL) {
	    PItemp = PISeg;
	    PISeg = PISeg -> Pnext;
	    IritFree((VoidPtr) PItemp);
	}
	IritFree((VoidPtr) PClosedMaxX);

	/* O.k. lets fire a ray from VMaxX to +X direction and see where it  */
	/* intersects the polygon. The routine CutPolygonAtRay will add two  */
	/* vertices at the ray intersection into polygon vertex list and     */
	/* return a pointer to first one, so we can chain our loop directly  */
	/* between these two new vertices.				     */
	V = CutPolygonAtRay(Pl, VMaxX -> Coord);
	Vnext = V -> Pnext;
	/* Introduce a copy of VMaxX and successor to VMaxX: */
	VMaxX -> Pnext = IPAllocVertex(VMaxX -> Count, VMaxX -> Tags, NULL,
								VMaxX -> Pnext);
	PT_COPY(VMaxX -> Pnext -> Coord, VMaxX -> Coord);
	PT_CLEAR(VMaxX -> Pnext -> Normal);
	V -> Pnext = VMaxX -> Pnext;
	IP_SET_INTERNAL_VRTX(V);
	VMaxX -> Pnext = Vnext;
	IP_SET_INTERNAL_VRTX(VMaxX);
    }

    /* Stage 5 - Time to rotate polygon back to its original position. */
    V = VHead = Pl -> PVertex;
    do {
	MatMultVecby4by4(V -> Coord, V -> Coord, RotMat);
	V = V -> Pnext;
    }
    while (V != NULL && V != VHead);

    SET_INOUTPUT_POLY(Pl);		   /* Mark the polygon as in output. */
    IP_RST_CONVEX_POLY(Pl);	     /* This polygon is not convex any more. */

    return TRUE;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Pushes on the adjacency stack, all adjacent polygons which are complete  *
* (no intersection) and are adjacent to complete edges (originated from	     *
* input polygons) of the given polygon.					     *
*                                                                            *
* PARAMETERS:                                                                *
*   Pl:           To be added to the adjacency stack.                        *
*   AdjStack:     The adjacency stack to put Pl in.                          *
*   StackPointer: Where exactly in the stack Pl is going to be pushed?       *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void PushAdjOnStack(IPPolygonStruct *Pl,
			   IPPolygonStruct *AdjStack[],
			   int *StackPointer)
{
    IPVertexStruct
	*V = Pl -> PVertex;

    do {
	if (V -> PAdj != NULL && BoolVerifyShareEdge(V, V -> PAdj))
	    AdjStack[++*StackPointer] = V -> PAdj;
	if (*StackPointer >= ADJ_STACK_SIZE) {
	    IritFatalError("Adjacency stack overflow, object too big");
	}
	V = V -> Pnext;
    }
    while (V != Pl -> PVertex);
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Test if the edge [V - V->Pnext] is indeed on the boundary of Pl.         *
*                                                                            *
* PARAMETERS:                                                                *
*   V:       First vertex of edge to verify.                                 *
*   Pl:      Polygon to verify the edge shares its boundary.                 *
*                                                                            *
* RETURN VALUE:                                                              *
*   int:     TRUE if [V - V->Pnext] is on Pl's boundary, FALSE otherwise.    *
*****************************************************************************/
int BoolVerifyShareEdge(IPVertexStruct *V, IPPolygonStruct *Pl)
{
    IPVertexStruct
	*Vl = Pl -> PVertex;
    VectorType Dir;
    int InterNum = 0;
    RealType InterVal[2], Dist;

    PT_SUB(Dir, V -> Pnext -> Coord, V -> Coord);
    if ((Dist = PT_LENGTH(Dir)) == 0)
        Dist = IRIT_EPSILON;

    do {
	PointType Ptemp;

	CGPointFromPointLine(Vl -> Coord, V -> Coord, Dir, Ptemp);
	if (CGDistPointPoint(Vl -> Coord, Ptemp) < IRIT_EPSILON) {
	    VectorType Dir2; 
	    RealType
	        Dist2 = CGDistPointPoint(V -> Coord, Ptemp);

	    PT_SUB(Dir2, Ptemp, V -> Coord);
	    Dist2 = PT_LENGTH(Dir2);

	    InterVal[InterNum] = Dist2 / Dist;
	    if (DOT_PROD(Dir2, Dir) < 0)
		InterVal[InterNum] = -InterVal[InterNum];
	    if (++InterNum == 2) {
		if (MIN(InterVal[0], InterVal[1]) < 1.0 &&
		    MAX(InterVal[0], InterVal[1]) > 0.0)
		    return TRUE;

		/* Save the second intersection as first one for next time. */
		InterVal[0] = InterVal[1];
		InterNum = 1;       
	    }
	}
	else
	    InterNum = 0;

	Vl = Vl -> Pnext;
    }
    while (Vl != Pl -> PVertex);

    return FALSE;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Chains two polygonal lists into one. For fast processing it is prefered  *
* that the first one is shorter. Returns pointer to chained list.	     *
*                                                                            *
* PARAMETERS:                                                                *
*   Pl1, Pl2:   The two polygonal objects to be chained together.            *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPPolygonStruct *: The combined/chained together polygonal list.         *
*                                                                            *
*                                                                            *
*                                                                            *
*****************************************************************************/
static IPPolygonStruct *ChainPolyLists(IPPolygonStruct *Pl1,
				       IPPolygonStruct *Pl2)
{
    IPPolygonStruct *Ptemp;

    if (Pl1 == NULL)
        return Pl2;
    else if (Pl2 == NULL)
	return Pl1;
    else {
	Ptemp = Pl1;
	while (Ptemp -> Pnext != NULL)
	    Ptemp = Ptemp -> Pnext;
	Ptemp -> Pnext = Pl2;
	return Pl1;
    }
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   This routine coordinates all the extraction of the polygons from the     M
* intersecting lists. Does it in the following steps:			     M
* 1. Mark all polygons with no intersection at all as complete polygons.     M
*    (this is because this polygon will be totally in or out, according      M
*    to inter-polygon adjacencies propagation...)			     M
*    Also mark them as undefined (if in output or undefined) yet.	     M
*    Uses IPPolygonStruct Tags to save these bits.			     M
* 2. do									     M
*    2.1. Convert the unordered segment list of each polygon to closed loops M
*         (if create a hole in polygon) or open (if crosses its boundary).   M
*    2.2. Order the open loops along the perimeter of the polygon (note      M
*	  these loops cannt intersect. For example (5 vertices polygon):     M
*	         -----------------------------L3			     V
*		|  ---------------L1  -----L2 |          --------L4   --L5   V
*		| |               |  |     |  |         |        |   |  |    V
*	  P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 V
*         Note L1, L2 are enclosed in L3 loop, and that the order is         M
*         circular.							     M
*    2.3. "Break" the polygon at each open loop that has no enclosed loops   M
*	  in it. For example we can start at L1, L2, L4, L5 and then L3.     M
*	  "Break" means - replace the vertex chain between the two loop end  M
*	  points, with the loops itself. Depends upon the relation required  M
*	  we may need to output a new polygon form from the deleted chain    M
*	  and that loop. In addition we may form a new polygon from last     M
*	  loop and was was left from the original polygon		     M
*	  For each formed polygon, for each complete edge of it (i.e. edge   M
*	  which was originally in the polygon) test the adjacent polygon     M
*	  if it is complete (as marked in 1.) and if in or undefined (marked M
*	  undefined in 1.) is still undefined:				     M
*	  2.3.1. set it to be in.					     M
*	  2.3.2. push it on adjacency stack.				     M
*    2.4. For each closed loop - find in which polygon (from polygons	     M
*	  created in 2.3.) it is enclosed, and decompose it.		     M
* 3. While adjacencies stack not empty do:				     M
*    3.1. pop top polygon from stack and output it.			     M
*    3.2. For each of its edges (which obviousely must be complete edges)    M
*	  if adjacent polygon is complete and undefined:		     M
*	  3.3.1. set it to be in.					     M
*	  3.3.2. push it on adjacency stack.				     M
*    3.3  go back to 3.							     M
*									     M
*   The above algorithm defines in as in output, but dont be confused with   M
* the required inter-object AinB (or AoutB if FALSE), which used to	     M
* determine which side of the trimming loop should be output.		     M
*   Note this routine may return non-convex polygons (but marked as so) even M
* though the input for the booleans must be convex polygons only!	     M
*   In order to keep the given object unchanged, a whole new copy off the    M
* polygon list is made. The polygons of the list that are not in the output  M
* are freed: a global list of all polygons (pointers) is used to scan them   M
* in the end and free the unused ones (list PolysPtr).			     M
*                                                                            *
* PARAMETERS:                                                                M
*   PObj:    Object that need to be rebuilt according to the intersection    M
*            curves that were found, both closed and open loops.             M
*   AinB:    Type of inclusion/exclusion requested.                          M
*                                                                            *
* RETURN VALUE:                                                              M
*   IPObjectStruct *: The newly created clipped object.                      M
*                                                                            *
* KEYWORDS:                                                                  M
*   BoolExtractPolygons, Booleans                                            M
*****************************************************************************/
IPObjectStruct *BoolExtractPolygons(IPObjectStruct *PObj, int AinB)
{
    int NumOfPolys = 0,
	StackPointer = -1;
    IPPolygonStruct *AdjStack[ADJ_STACK_SIZE], **PolysPtr, *OriginalPl,
		*Pl, *PlHead, *PlNext, *OutputPl = NULL, *SplPl, *NewPl;
    IPVertexStruct *V, *Vnext;
    InterSegListStruct *PClosed, *POpen, *Ptemp;

#ifdef DEBUG3
    printf("Enter BoolExtractPolygons\n");
#endif /* DEBUG3 */

    /* Stage 1. - mark all polygons as needed: */
    PlHead = Pl = PObj -> U.Pl;
    /* Gen. a copy of Pl, so we can modify the original polygon list: */
    PObj -> U.Pl = CopyPolygonList(Pl);

    while (Pl != NULL) {
	NumOfPolys++;	     /* Count number of polygons in original object. */
	if (Pl -> PAux != NULL) {     /* The intersection list is not empty! */
	    RST_COMPLETE_POLY(Pl);	 /* Mark it as non complete polygon. */
	    V = Pl -> PVertex;
	    do {
		SET_ORIGINAL_VRTX(V); /* Mark vertices from original object. */
		V = V -> Pnext;
	    }
	    while (V != Pl -> PVertex);
	}
	else {
	    SET_COMPLETE_POLY(Pl);	     /* Mark it as complete polygon. */
	    RST_INOUTPUT_POLY(Pl);	 /* And as undefined (if in output). */
	    RST_ADJPUSHED_POLY(Pl);	 /* And as not pushed on adj. stack. */
	}
	Pl = Pl -> Pnext;
    }

    /* Stage 2. - scan the polygons and subdivide the intersecting ones: */
    Pl = PlHead;

    /* We will save pointers to ALL polygons in list so we could free in the */
    /* end the ones that are not in the output list, and therefore unused.   */
    PolysPtr = (IPPolygonStruct **)
		IritMalloc(sizeof(IPPolygonStruct *) * NumOfPolys);
    NumOfPolys = 0;

    while (Pl != NULL) {
	PolysPtr[NumOfPolys++] = Pl;	    /* Save pointer to this polygon. */

	PlNext = Pl -> Pnext;
	Pl -> Pnext = NULL;

	if (!IS_COMPLETE_POLY(Pl)) {/* They are intersections with this one. */
	    /* Convert the intersecting segments into open/closed loops. */
	    BoolLoopsFromInterList(Pl, &PClosed, &POpen);

	    /* Save copy of original polygon vertex list as we need its      */
	    /* normals to interpolate for the internal ones.		     */
	    OriginalPl = IPAllocPolygon(1, Pl -> Tags,
					CopyVertexList(Pl -> PVertex), NULL);
	    IP_RST_BBOX_POLY(OriginalPl);
	    PLANE_COPY(OriginalPl -> Plane, Pl -> Plane);

	    if (POpen != NULL) {
		/* Sort the Open loops into an order we can handle... */
		BoolSortOpenInterList(Pl, &POpen);
		SplPl = NewPl = NULL;	 /* Keep the list of split polygons. */

		while (POpen != NULL) {	/* Clip the open loops from polygon: */
		    /* Note ClipOpenLoopFromPoly also frees the InterSegment */
		    /* list pointed by POpen (but not POpen itself). 	     */
		    NewPl = ClipOpenLoopFromPoly(Pl, POpen, AinB);
		    if (NewPl != NULL) {   /* If loop clipped a new polygon, */
			PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
			NewPl -> Pnext = SplPl;/* add to split polygon list. */
			SplPl = NewPl;
			/* And push adj. polygons of complete edges on stack.*/
			PushAdjOnStack(NewPl, AdjStack, &StackPointer);
		    }
		    Ptemp = POpen;
		    POpen = POpen -> Pnext;
		    IritFree((VoidPtr) Ptemp);
		}

		/* Last clip generated nothing (NewPl == NULL) so part that  */
		/* left from Pl (PlCopy) is IN output list! Add this poly:   */
		if (NewPl == NULL) {
		    PLANE_COPY(Pl -> Plane, OriginalPl -> Plane);
		    Pl -> Pnext = SplPl; /* And chain what was left from it. */
		    SplPl = Pl;
		    /* And push adjacent polygons of complete edges on stack.*/
		    PushAdjOnStack(Pl, AdjStack, &StackPointer);
		    SET_INOUTPUT_POLY(Pl);/* So we wouldnt free that in end. */
		    IP_RST_CONVEX_POLY(Pl);	   /* May be not convex now. */
		}

		UpdateVerticesNormals(SplPl, OriginalPl);
	    }
	    else
		SplPl = Pl;

	    if (PClosed != NULL) {
		for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext)
		    Pl -> PAux = NULL;

		/* Classify the closed loops into the appropriate polygon. */
		while (PClosed != NULL) {
		    Ptemp = PClosed -> Pnext;
		    for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
			if (CGPolygonRayInter3D(Pl, PClosed -> PISeg -> PtSeg[0],
						0) % 2 == 1) {
			    /* This closed loop is contained in this polygon.*/
			    PClosed -> Pnext = (InterSegListStruct *) Pl -> PAux;
			    Pl -> PAux = (VoidPtr) PClosed;
			    break;
			}
		    }
		    if (Pl == NULL) {
			/* This closed loop is part of a trimmed out by open */
			/* loop region. It should be only the island formed  */
			/* by this closed loop then.			     */
			/* Make a new polygon - a copy of the original and   */
			/* Put this loop in it.				     */
			NewPl = IPAllocPolygon(1, OriginalPl -> Tags,
				CopyVertexList(OriginalPl -> PVertex), NULL);
			IP_RST_BBOX_POLY(NewPl);
			PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
			NewPl -> PAux = (VoidPtr) PClosed;
			NewPl -> Pnext = SplPl;
			SplPl = NewPl;
		    }
		    PClosed = Ptemp;
		}

		for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
		    /* Make a "cut" from the loop(s)  +-------+    +-------+ */
		    /* to boundary if possible, and   |       |    |       | */
		    /* converting Pl to a nonconvex   |  / \  | -> |  / \__| */
		    /* polygon, that has an edge (the |  \ /  | -> |  \ /  | */
		    /* cut) which is shared twice in  |       |    |       | */
		    /* the same polygon		      +-------+    +-------+ */
		    PClosed = (InterSegListStruct *) Pl -> PAux;
		    Pl -> PAux = NULL;
		    if (CombineClosedLoops(Pl, PClosed, AinB)) {
			/* If returned with TRUE -  polygon boundary is in   */
			/* output, so add all its neighbours to adj. stack.  */
			PushAdjOnStack(Pl, AdjStack, &StackPointer);
		    }

		    UpdateVerticesNormals(Pl, OriginalPl);
		}
	    }

	    OutputPl = ChainPolyLists(SplPl, OutputPl);

	    /* Free the original polygon vertex list. */
	    IPFreePolygon(OriginalPl);
	}

	Pl = PlNext;
    }

    /* Stage 3. - handling adjacencies and propagate them in polygons:	     */
    /* Pop off the elements from the stack, and propagate them using their   */
    /* adjacencies.							     */
    while (StackPointer >= 0) {
	Pl = AdjStack[StackPointer--];			 /* Pop top element. */
	if (!IS_COMPLETE_POLY(Pl) ||	    /* Ignore non complete polygons. */
	     IS_INOUTPUT_POLY(Pl))
		continue;			      /* If already handled. */

	SET_INOUTPUT_POLY(Pl);	  /* Mark this one as handled for next time. */

	V = Pl -> PVertex;   /* Push all adjacent ones that not handled yet. */
	do {
	    if (V -> PAdj &&
		IS_COMPLETE_POLY(V -> PAdj) &&
		!IS_INOUTPUT_POLY(V -> PAdj) &&
		!IS_ADJPUSHED_POLY(V -> PAdj)) {
		SET_ADJPUSHED_POLY(V -> PAdj);
		AdjStack[++StackPointer] = V -> PAdj;   /* Push it on stack. */
		if (StackPointer >= ADJ_STACK_SIZE)
		    IritFatalError("Adjacency stack overflow, object too big");
	    }
	    V = V -> Pnext;
	}
	while (V != Pl -> PVertex);

	Pl -> Pnext = OutputPl;		   /* And chain it into output list. */
	OutputPl = Pl;
    }

    /* Free all polygons which are not in the output list: */
    while (--NumOfPolys >= 0) {
	if (!IS_INOUTPUT_POLY(PolysPtr[NumOfPolys])) {
	    IPFreePolygon(PolysPtr[NumOfPolys]);
	}
    }
    IritFree((VoidPtr) PolysPtr);

    /* Another floating point kludge: a polygon may have zero length edge so */
    /* search for those and remove them - someone may die because of one...  */
    Pl = OutputPl;
    while (Pl != NULL) {
	V = Pl -> PVertex;
	do {
	    Vnext = V -> Pnext;
	    if (BOOL_PT_APX_EQ(V -> Coord, Vnext -> Coord)) {
		/* Ahh - we got you. Simply skip Vnext vertex and free it: */
		V -> Pnext = Vnext -> Pnext;
		/* Update polygon vertex pointer if point on freed vertex: */
		if (Pl -> PVertex == Vnext)
		    Pl -> PVertex = Vnext -> Pnext;
		IPFreeVertex(Vnext);
		Vnext = V -> Pnext;
	    }
	    V = Vnext;
	}
	while (V != Pl -> PVertex && V != NULL);

	Pl = Pl -> Pnext;
    }

#ifdef DEBUG3
    printf("Exit BoolExtractPolygons\n");
#endif /* DEBUG3 */

    return GenPolyObject("", OutputPl, NULL);	 /* Return resulting object. */
}

#ifdef DEBUG

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Print the content of the given vertex list, to standard output.	     *
*                                                                            *
* PARAMETERS:                                                                *
*   V:       The vertex list to be printed.                                  *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
void BoolPrintVrtxList(IPVertexStruct *V)
{
    IPVertexStruct
	*VHead = V;

    do {
	printf("    %12lf %12lf %12lf",
	       V -> Coord[0], V -> Coord[1], V -> Coord[2]);
	if (IP_IS_INTERNAL_VRTX(V))
	    printf(" (Internal)\n");
	else
	    printf("\n");
	V = V -> Pnext;
    }
    while (V!= NULL && V != VHead);
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Print the content of the given InterSegment list, to standard output.    *
*                                                                            *
* PARAMETERS:                                                                *
*   PInt:       The InterSegment list to be printed.                         *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
void BoolPrintInterList(InterSegmentStruct *PInt)
{
    printf("INTER SEGMENT LIST:\n");

    if (PInt)
	printf("Entry vertex pointer %p\n", PInt -> V[0]);
    while (PInt) {
	printf("%9lg %9lg %9lg (%04ld), %9lg %9lg %9lg (%04ld)\n",
	    PInt -> PtSeg[0][0], PInt -> PtSeg[0][1], PInt -> PtSeg[0][2],
	    PInt -> V[0],
	    PInt -> PtSeg[1][0], PInt -> PtSeg[1][1], PInt -> PtSeg[1][2],
	    PInt -> V[1]);
	if (PInt -> Pnext == NULL)
	    printf("Exit vertex pointer %p\n", PInt -> V[1]);

	PInt = PInt -> Pnext;
    }
}

#endif /* DEBUG */
