/*****************************************************************************
*   "Irit" - the 3d (not only polygonal) solid modeller.		     *
*									     *
* Written by:  Gershon Elber				Ver 0.2, Mar. 1990   *
******************************************************************************
* (C) Gershon Elber, Technion, Israel Institute of Technology                *
******************************************************************************
*   Module to handle Boolean operation between two polygons in the XY plane. *
* The Z coords. are totally ignored. Input polygons are assumed to be convex.*
*****************************************************************************/

/* #define DEBUG2	         If defined, defines some printing routines. */

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

#define Z_CROSS_PROD(V1, V2) (V1[0] * V2[1] - V1[1] * V2[0])

static IPPolygonStruct *MergeTwoPolygons(IPPolygonStruct *Pl1,
					 IPPolygonStruct *Pl2);
static IPPolygonStruct *Boolean2DCombine(IPPolygonStruct *Pl1,
					 IPPolygonStruct *Pl2);
static void SortParam(Bool2DInterStruct **Bool2D, int First);
static IPPolygonStruct *Boolean2DCompute1InOut2(IPPolygonStruct *Pl1,
					        IPPolygonStruct *Pl2,
					        Bool2DInterStruct **Bool2D,
					        int Pl1First, int ComputeOut);
static IPPolygonStruct *Boolean2DReverse(IPPolygonStruct *PlHead);

#ifdef DEBUG2
static void PrintVrtxList(IPVertexStruct *V);
#endif /* DEBUG2 */

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Given two polygons assumed to be in the same plane, compute their 2D     M
* Boolean operation BoolOper and return it as a new polygon.		     M
* NULL is returned if an error occur (No intersection or invalid BoolOper).  M
*                                                                            *
* PARAMETERS:                                                                M
*   Pl1:        First polygon to compute 2D Boolean for.                     M
*   Pl2:        Second polygon to compute 2D Boolean for.                    M
*   BoolOper:   Boolean operation requested (and, or, etc.)                  M
*                                                                            *
* RETURN VALUE:                                                              M
*   IPPolygonStruct: The resulting Boolean operation.                        M
*                                                                            *
* SEE ALSO:                                                                  M
*   BooleanOR, BooleanAND, BooleanSUB, BooleanCUT, BooleanMERGE, BooleanNEG, M
*   BoolSetHandleCoplanarPoly, BoolSetOutputInterCurve,			     M
*   Boolean2DComputeInters						     M
*                                                                            *
* KEYWORDS:                                                                  M
*   Boolean2D, Booleans                                                      M
*****************************************************************************/
IPPolygonStruct *Boolean2D(IPPolygonStruct *Pl1,
			   IPPolygonStruct *Pl2,
			   BoolOperType BoolOper)
{
    IPPolygonStruct *RetVal;
    Bool2DInterStruct
	*Bool2D = Boolean2DComputeInters(Pl1, Pl2, TRUE);

    if (Bool2D == NULL) {
	IPPolygonStruct *PlOut, *PlIn;

	/* Coplanar polygons have no intersection. Test for inclusion. */
	if ((CGPolygonRayInter(Pl1, Pl2 -> PVertex -> Coord, 0) & 0x01) == 1) {
	    /* Pl2 is enclosed within Pl1 */
	    PlOut = Pl1;
	    PlIn = Pl2;
	}
	else if ((CGPolygonRayInter(Pl2,
				    Pl1 -> PVertex -> Coord, 0) & 0x01) == 1) {
	    /* Pl1 is enclosed within Pl2 */
	    PlOut = Pl2;
	    PlIn = Pl1;
	}
	else {
	    PlOut = NULL;
	    PlIn = NULL;
	}

	RetVal = NULL;
	switch (BoolOper) {
	    case BOOL_OPER_OR:
	        if (PlOut != NULL)
		    RetVal = IPAllocPolygon(PlOut -> Tags,
				  CopyVertexList(PlOut -> PVertex), NULL);
		break;
	    case BOOL_OPER_AND:
	        if (PlIn != NULL)
		    RetVal = IPAllocPolygon(PlIn -> Tags,
				  CopyVertexList(PlIn -> PVertex), NULL);
		break;
	    case BOOL_OPER_SUB:
		if (PlOut == Pl1) {
		    /* Merge the two polygons PlOut as is and PlIn reversed. */
		    RetVal = MergeTwoPolygons(
			IPAllocPolygon(PlOut -> Tags,
				       CopyVertexList(PlOut -> PVertex), NULL),
			IPAllocPolygon(PlIn -> Tags,
				       CopyVertexList(PlIn -> PVertex), NULL));
		}
		break;
	    default:
		IritFatalError("Unsupported 2D Boolean operation");
		RetVal = NULL;
		break;
	}

	return RetVal;
    }

    switch (BoolOper) {
	case BOOL_OPER_OR:
	    RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
							      TRUE, TRUE),
				      Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
							      FALSE, TRUE));
	    break;
	case BOOL_OPER_AND:
	    RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
							      TRUE, FALSE),
				      Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
							      FALSE, FALSE));
	    break;
	case BOOL_OPER_SUB:
	    RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
							      TRUE, TRUE),
				      Boolean2DReverse(
				      Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
							      FALSE, FALSE)));
	    break;
	default:
	    IritFatalError("Unsupported 2D Boolean operation");
	    RetVal = NULL;
	    break;
    }

    while (Bool2D) {
	Bool2DInterStruct
	    *NextBool2D = Bool2D -> Pnext;

	IritFree((VoidPtr) Bool2D);
	Bool2D = NextBool2D;
    }

    return RetVal;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Merges the two provided polygons. Pl1 is assumed to fully contain Pl2.   *
*   Pl1/2 are assumed to be convex. Pl2 vertex list is reversed and the two  *
* polygon's vertex lists are connected via the maximum X vertices.	     *
*   This function is destructive and Pl1/2 are modifed in place.	     *
*                                                                            *
* PARAMETERS:                                                                *
*   Pl1, Pl2:    The two polygons to merge into one.                         *
*   Pl2:                                                                     *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPPolygonStruct:  The merged polygon.                                    *
*****************************************************************************/
static IPPolygonStruct *MergeTwoPolygons(IPPolygonStruct *Pl1,
					 IPPolygonStruct *Pl2)
{
    RealType MaxX;
    IPVertexStruct *V, *VMaxX1Copy, *VMaxX2Copy,
	*VMaxX1 = NULL,
	*VMaxX2 = NULL;

    IritPrsrReverseVrtxList(Pl2);

    /* FInd the vertices in both polygons with the maximum X value. */
    V = Pl1 -> PVertex;
    MaxX = -IRIT_INFNTY;
    do {
	if (V -> Coord[0] > MaxX) {
	    VMaxX1 = V;
	    MaxX = V -> Coord[0];
	}
	V = V -> Pnext;
    } while (V != NULL && V != Pl1 -> PVertex);

    V = Pl2 -> PVertex;
    MaxX = -IRIT_INFNTY;
    do {
	if (V -> Coord[0] > MaxX) {
	    VMaxX2 = V;
	    MaxX = V -> Coord[0];
	}
	V = V -> Pnext;
    } while (V != NULL && V != Pl2 -> PVertex);

    /* Duplicate this maximum points. */
    VMaxX1Copy = IPAllocVertex(VMaxX1 -> Tags, NULL, VMaxX1 -> Pnext);
    PT_COPY(VMaxX1Copy -> Coord, VMaxX1 -> Coord);
    PT_COPY(VMaxX1Copy -> Normal, VMaxX1 -> Normal);

    VMaxX2Copy = IPAllocVertex(VMaxX2 -> Tags, NULL, VMaxX2 -> Pnext);
    PT_COPY(VMaxX2Copy -> Coord, VMaxX2 -> Coord);
    PT_COPY(VMaxX2Copy -> Normal, VMaxX2 -> Normal);

    /* And exchange pointers. */
    VMaxX1 -> Pnext = VMaxX2Copy;
    IP_SET_INTERNAL_VRTX(VMaxX1);
    VMaxX2 -> Pnext = VMaxX1Copy;
    IP_SET_INTERNAL_VRTX(VMaxX2);

    Pl2 -> PVertex = NULL;
    IPFreePolygonList(Pl2);

    IP_RST_CONVEX_POLY(Pl1);

    return Pl1;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Connects the two provided lists of polylines into a closed polygon.	     *
* Pl1/2 are being used by this routine and being destroyed.		     *
*                                                                            *
* PARAMETERS:                                                                *
*   Pl1, Pl2:   The two lists of polylines to merge into one closed polygon. *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPPolygonStruct:  The constructed polygon.                               *
*****************************************************************************/
static IPPolygonStruct *Boolean2DCombine(IPPolygonStruct *Pl1,
					 IPPolygonStruct *Pl2)
{
    IPVertexStruct *VTail;
    IPPolygonStruct *Pl, *PlLast,
	*PlOut = NULL;

    /* Chain the two lists into one: */
    for (Pl = Pl1; Pl -> Pnext != NULL; Pl = Pl -> Pnext);
    Pl -> Pnext = Pl2;
    for (VTail = Pl1 -> PVertex; VTail -> Pnext != NULL; VTail = VTail -> Pnext);

    while (Pl1 != NULL)
    {
	for (PlLast = Pl1, Pl = Pl1 -> Pnext;
	     Pl != NULL &&
	     !BOOL_PT_APX_EQ(Pl -> PVertex -> Coord, VTail -> Coord);
	     PlLast = Pl, Pl = Pl -> Pnext);
	if (Pl == NULL) {
	    IritFatalError("Boolean2D: Failed to match polylines.");
	    return NULL;
	}

	VTail -> Pnext = Pl -> PVertex -> Pnext;

	/* Free the merged polyline (with its first vertex). */
	PlLast -> Pnext = Pl -> Pnext;
	Pl -> PVertex -> Pnext = NULL;
	IPFreePolygon(Pl);

	/* Update the Tail pointer. */
	for ( ; VTail -> Pnext != NULL; VTail = VTail -> Pnext);

	if (BOOL_PT_APX_EQ(VTail -> Coord, Pl1 -> PVertex -> Coord)) {
	    /* We closed a loop here. Add to output list. */
	    Pl = Pl1 -> Pnext;
	    Pl1 -> Pnext = PlOut;
	    PlOut = Pl1;

	    /* Close the loop and remove the duplicate vertex. */
	    VTail -> Pnext = Pl1 -> PVertex -> Pnext;
	    IPFreeVertex(Pl1 -> PVertex);
	    Pl1 -> PVertex = VTail;

	    /* Continue with next polygon. */
	    if ((Pl1 = Pl) != NULL) {
		for (VTail = Pl1 -> PVertex;
		     VTail -> Pnext != NULL;
		     VTail = VTail -> Pnext);
	    }
	}
    }

    return PlOut;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Given two polygons/lines, Detect all edges in Pl1 that intersect with    M
* edges in Pl2. Returned is the information about all intersections as a     M
* Bool2DInter structure list.						     M
*                                                                            *
* PARAMETERS:                                                                M
*   Poly1, Poly2:    The two polygons/lines to intersect.                    M
*   HandlePolygons:  If polygons, needs to handle normals etc.               M
*                                                                            *
* RETURN VALUE:                                                              M
*   Bool2DInterStruct *:  Intersection information.                          M
*                                                                            *
* SEE ALSO:                                                                  M
*   Boolean2D                                                                M
*                                                                            *
* KEYWORDS:                                                                  M
*   Boolean2DComputeInters, Booleans                                         M
*****************************************************************************/
Bool2DInterStruct *Boolean2DComputeInters(IPPolygonStruct *Poly1,
					  IPPolygonStruct *Poly2,
					  int HandlePolygons)
{
    Bool2DInterStruct *Bool2D,
	*Bool2DHead = NULL;
    RealType Pl1Param, Pl2Param;
    RealType *Pl1, *Pl2, t1, t2;
    PointType Pt1, Pt2;
    VectorType Vl1, Vl2;
    IPVertexStruct *V1, *V2,
	*V1Head = Poly1 -> PVertex,
	*V2Head = Poly2 -> PVertex;

    V1 = V1Head;
    Pl1Param = 0.0;
    do {
	if (V1 == NULL || V1 -> Pnext == NULL)
	    break;
	Pl1 = V1 -> Coord;
	PT_SUB(Vl1, V1 -> Pnext -> Coord, Pl1);

	V2 = V2Head;
        Pl2Param = 0.0;
	do {
	    if (V2 == NULL || V2 -> Pnext == NULL)
	        break;
	    Pl2 = V2 -> Coord;
	    PT_SUB(Vl2, V2 -> Pnext -> Coord, Pl2);

	    if (CG2PointsFromLineLine(Pl1, Vl1, Pl2, Vl2, Pt1, &t1, Pt2, &t2) &&
		t1 > 0.0 && t1 <= 1.0 && t2 > 0.0 && t2 <= 1.0) {
		/* We detected an intersection here. */
		Bool2D = (Bool2DInterStruct *)
			       IritMalloc(sizeof(Bool2DInterStruct));
		PT_COPY(Bool2D -> InterPt, Pt1);
		if (HandlePolygons)
		    InterpNrmlBetweenTwo2(Pt1, Bool2D -> Normal, V1, V2);

		Bool2D -> Poly1Vrtx = V1;
		Bool2D -> Param1 = Pl1Param + t1;
		Bool2D -> Poly2Vrtx = V2;
		Bool2D -> Param2 = Pl2Param + t2;

		Bool2D -> Pnext = Bool2DHead;
		Bool2DHead = Bool2D;
	    }

	    Pl2Param += 1.0;
	    V2 = V2 -> Pnext;
	}
	while (V2 != NULL && V2 != V2Head);

	Pl1Param += 1.0;
	V1 = V1 -> Pnext;
    }
    while (V1 != NULL && V1 != V1Head);

    if (HandlePolygons && Bool2DHead != NULL && Bool2DHead -> Pnext == NULL) {
	/* If only one intersection - ignore it (point intersection). */
	IritFree((VoidPtr) Bool2DHead);
	Bool2DHead = NULL;
    }
    
    return Bool2DHead;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Sorts the provided list with according to Param1 (First == TRUE) or      *
* Param2 (First == FALSE). Bool2D is sorted in place.                        *
*                                                                            *
* PARAMETERS:                                                                *
*   Bool2D:      List of intersection locations to sort.                     *
*   First:       TRUE if sort according to first, FALSE otherwise.           *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void SortParam(Bool2DInterStruct **Bool2D, int First)
{
    Bool2DInterStruct
	*Bool2DSorted = NULL;

    while (*Bool2D != NULL) {
	Bool2DInterStruct *BTmp,
	    *B = *Bool2D;

	*Bool2D = (*Bool2D) -> Pnext;
	B -> Pnext = NULL;

	if (Bool2DSorted) {
	    if ((First && Bool2DSorted -> Param1 > B -> Param1) ||
		(!First && Bool2DSorted -> Param2 > B -> Param2)) {
		/* Put it as first in list. */
		B -> Pnext = Bool2DSorted;
		Bool2DSorted = B;
	    }
	    else {
		for (BTmp = Bool2DSorted;
		     BTmp -> Pnext != NULL;
		     BTmp = BTmp -> Pnext)
		    if ((First && BTmp -> Pnext -> Param1 > B -> Param1) ||
			(!First && BTmp -> Pnext -> Param2 > B -> Param2))
			break;
		B -> Pnext = BTmp -> Pnext;
		BTmp -> Pnext = B;
	    }
	}
	else
	    Bool2DSorted = B;
    }

    *Bool2D = Bool2DSorted;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
* Given two polygons, Computes the region(s) of Pl1 in or out of Pl2.        *
*                                                                            *
* PARAMETERS:                                                                *
*   Pl1, Pl2:      Polygons to compute Pl1 in or out Pl2 for.                *
*   Bool2D:        List of intersection locations.                           *
*   Pl1First:      If in fact Pl1 is second in Bool2D.                       *
*   ComputeOut:    TRUE for Pl1 Out Pl2, FALSE for Pl1 in Pl2.               *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPPolygonStruct:  Retulting Boolean.                                     *
*****************************************************************************/
static IPPolygonStruct *Boolean2DCompute1InOut2(IPPolygonStruct *Pl1,
					        IPPolygonStruct *Pl2,
					        Bool2DInterStruct **Bool2D,
					        int Pl1First,
						int ComputeOut)
{
    VectorType V1, V2;
    IPVertexStruct *V, *VTail, *VTmp, *VTmp2,
	*VHead = Pl1 -> PVertex;
    IPPolygonStruct *Pl,
	*PlOut = NULL;
    Bool2DInterStruct *B, *NextB;

    SortParam(Bool2D, Pl1First);

    for (B = *Bool2D; B != NULL; B = B -> Pnext) {
	NextB = B -> Pnext ? B -> Pnext : *Bool2D;

	VTmp = Pl1First ? B -> Poly1Vrtx : B -> Poly2Vrtx;
	if (BOOL_PT_APX_EQ(B -> InterPt, VTmp -> Coord))
	    PT_SUB(V1, VTmp -> Pnext -> Coord, B -> InterPt)
	else
	    PT_SUB(V1, B -> InterPt, VTmp -> Coord)

	VTmp = Pl1First ? B -> Poly2Vrtx : B -> Poly1Vrtx;
	if (BOOL_PT_APX_EQ(B -> InterPt, VTmp -> Coord))
	    PT_SUB(V2, VTmp -> Pnext -> Coord, B -> InterPt)
	else
	    PT_SUB(V2, B -> InterPt, VTmp -> Coord)

        if ((Z_CROSS_PROD(V1, V2) < 0.0) ^ (ComputeOut != FALSE)) {
	    VTmp = Pl1First ? B -> Poly1Vrtx : B -> Poly2Vrtx;
	    VHead = VTail = IPAllocVertex(VTmp -> Tags, NULL, NULL);
	    PT_COPY(VHead -> Coord, B -> InterPt);
	    PT_COPY(VHead -> Normal, B -> Normal);

	    VTmp2 = Pl1First ? NextB -> Poly1Vrtx : NextB -> Poly2Vrtx;
	    if (VTmp != VTmp2)
		for (V = VTmp -> Pnext;
		     V != VTmp2 -> Pnext;
		     V = V -> Pnext) {
	        VTail -> Pnext =
		    IPAllocVertex(V -> Tags, NULL, NULL);
	        VTail = VTail -> Pnext;
	        PT_COPY(VTail -> Coord, V -> Coord);
		PT_COPY(VTail -> Normal, V -> Normal);
	    }

	    VTail -> Pnext = IPAllocVertex(VTmp2 -> Tags, NULL, NULL);
	    VTail = VTail -> Pnext;
	    PT_COPY(VTail -> Coord, NextB -> InterPt);
	    PT_COPY(VTail -> Normal, NextB -> Normal);

	    Pl = IPAllocPolygon(0, VHead, NULL);
	    PLANE_COPY(Pl -> Plane, Pl1 -> Plane);
	    Pl -> Pnext = PlOut;
	    PlOut = Pl;
	}
    }

    if (PlOut == NULL)
	IritFatalError("Bool2D: Failed to compute in/out.");
    return PlOut;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Given a polyline (= list of IPVertexStruct), computes the reverse of     *
* the list, in place. Returns pointer to reversed list.			     *
*                                                                            *
* PARAMETERS:                                                                *
*   PlHead:        Polyline to reverse.                                      *
*                                                                            *
* RETURN VALUE:                                                              *
*   IPPolygonStruct:    Reversed polyline.                                   *
*****************************************************************************/
static IPPolygonStruct *Boolean2DReverse(IPPolygonStruct *PlHead)
{
    IPPolygonStruct *Pl;

    for (Pl = PlHead; Pl != NULL; Pl = Pl -> Pnext) {
	IPVertexStruct *VNextNext, *V, *VNext;

	V = Pl -> PVertex;
	VNext = V -> Pnext;

	while (VNext != NULL) {
	    VNextNext = VNext -> Pnext;
	    VNext -> Pnext = V;			     /* Reverse the pointer! */

	    V = VNext;			   /* Advance all 3 pointers by one. */
	    VNext = VNextNext;
	}
	Pl -> PVertex -> Pnext = NULL;
	Pl -> PVertex = V;

	/* Move the Tags. */
	while (V -> Pnext != NULL) {
	    V -> Tags = V -> Pnext -> Tags;

	    V = V -> Pnext;
	}
    }
    return PlHead;
}

#ifdef DEBUG2

/*****************************************************************************
* DESCRIPTION:                                                               *
*   Print the content of the given vertex list, to standard output.	     *
*                                                                            *
* PARAMETERS:                                                                *
*   V:        Vertex list to print.                                          *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void PrintVrtxList(IPVertexStruct *V)
{
    IPVertexStruct
	*VHead = V;

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

#endif /* DEBUG2 */