/*****************************************************************************
*   "Irit" - the 3d polygonal solid modeller.				     *
*									     *
* Written by:  Gershon Elber				Ver 0.2, Mar. 1990   *
******************************************************************************
*   Module to handle the high level Boolean operations. The other modules    *
* should only call this module to perform Boolean operations. All the        *
* operations are none-destructives, meaning the given data is not modified.  *
*   Note all the polygons of the two given objects must be convex, and the   *
* returned object will also have only convex polygons!			     *
*****************************************************************************/

/* #define DEBUG	    If defined, return intersection polyline object. */

#ifdef __MSDOS__
#include <alloc.h>
#endif /* __MSDOS__ */

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include <signal.h>
#include "program.h"
#include "allocate.h"
#include "attribut.h"
#include "booleang.h"
#include "booleanl.h"
#include "convex.h"
#include "ctrl-brk.h"
#include "graphgen.h"
#include "matherr.h"
#include "objects.h"
#include "windows.h"

int BooleanOutputInterCurve = FALSE;	/* Kind of output from Boolean oper. */

static jmp_buf LclLongJumpBuffer;	     /* Used in fatal Boolean error. */
static int FatalErrorType,		     /* Type of fatal Boolean error. */
	   BooleanOperation;	       /* One of BooleanOR, BooleanAND, etc. */

static ObjectStruct *BooleanCombineTwoObjs(ObjectStruct *PObj1,
					   ObjectStruct *PObj2);
static ObjectStruct *VerifyBooleanInput(ObjectStruct *PObj1,
					ObjectStruct *PObj2, int Oper);

#ifdef __MSDOS__
static void cdecl BooleanFPE(int Sig, int Type, int *RegList);
#else
static void BooleanFPE(int Type);
#endif /* __MSDOS__ */
static void SetBooleanOutputKind(void);

/*****************************************************************************
*   Verify input for Booleans. Ret. NULL if OK, otherwise an obj to return.  *
*****************************************************************************/
static ObjectStruct *VerifyBooleanInput(ObjectStruct *PObj1,
					ObjectStruct *PObj2, int Oper)
{
    ObjectStruct *PObj;
    PolygonStruct *Pl;

    BooleanOperation = Oper;

    SetBooleanOutputKind();

    if (!IS_POLY_OBJ(PObj1) || (PObj2 != NULL && !IS_POLY_OBJ(PObj2)))
	FatalError("Boolean: operation on non polygonal object(s).\n");

    signal(SIGFPE, BooleanFPE);		 /* Will trap floating point errors. */

    switch (Oper) {
	case BOOL_OPER_OR:
	    if (IS_POLYLINE_OBJ(PObj1) && IS_POLYLINE_OBJ(PObj2)) {
		if (PObj1 -> U.Pl.P == NULL)
		    PObj = CopyObject(NULL, PObj2, FALSE);
		else {
		    PObj = CopyObject(NULL, PObj1, FALSE);
		    Pl = PObj -> U.Pl.P;
		    while (Pl -> Pnext) Pl = Pl -> Pnext;
		    Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl.P);
		}
	    	return PObj;
	    }
	case BOOL_OPER_AND:
	case BOOL_OPER_SUB:
	case BOOL_OPER_CUT:
	case BOOL_OPER_MERGE:
	case BOOL_OPER_NEG:
    	    if (IS_POLYLINE_OBJ(PObj1) ||
		(PObj2 != NULL && IS_POLYLINE_OBJ(PObj2))) {
    	    	WndwInputWindowPutStr(
		"Boolean: illegal operation on mixed polygon/line geometric object(s).");
		PObj = GenPolyObject("", NULL, NULL);
		return PObj;
    	    }

	    if (Oper != BOOL_OPER_NEG) {
	    	ConvexPolyObject(PObj1);/* Make sure all polygons are convex.*/
	    	ConvexPolyObject(PObj2);
	    }

	    return NULL;
	default:
    	    FatalError("Boolean: undefined Boolean operation.\n");
    	    return NULL;			     /* Make warning silent. */
    }
}

/*****************************************************************************
*   Perform a Boolean OR between two objects.				     *
*****************************************************************************/
ObjectStruct *BooleanOR(ObjectStruct *PObj1, ObjectStruct *PObj2)
{
    ObjectStruct *PObj;
    PolygonStruct *Pl;

    if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_OR)) != NULL)
	return PObj;
    else {
	if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
	    signal(SIGFPE, BooleanFPE);	 /* Will trap floating point errors. */
	    if (BooleanOutputInterCurve)
		PObj = BooleanLow1Out2(PObj1, PObj2);/* Ret intersection crv.*/
	    else
		PObj = BooleanCombineTwoObjs(BooleanLow1Out2(PObj1, PObj2),
					     BooleanLow1Out2(PObj2, PObj1));
	}
	else {
	    /* We gain control from fatal error long jump - usually we should*/
	    /* return empty object, but if error is No intersection between  */
	    /* the two objects, we assume they have no common volume and     */
	    /* return a new object consists of the concat. of all polygons!  */
	    if (FatalErrorType != FTL_BOOL_NO_INTER) {
		PObj = GenPolyObject("", NULL, NULL);/* Return empty object. */
	    }
	    else {
		if (PObj1 -> U.Pl.P == NULL)
		    PObj = CopyObject(NULL, PObj2, FALSE);
		else {
		    PObj = CopyObject(NULL, PObj1, FALSE);/* Copy Obj1 polys.*/
		    Pl = PObj -> U.Pl.P;
		    while (Pl -> Pnext) Pl = Pl -> Pnext;
		    Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl.P);/*Obj2 poly.*/
		}
	    }
	}
    }

    signal(SIGFPE, DefaultFPEHandler);	            /* Default FPE trapping. */

    SetObjectColor(PObj, BooleanOutputInterCurve ?
			 GlblICrvColor :
			 GlblBoolColor);       /* Default bool object color. */

    return PObj;
}

/*****************************************************************************
*   Perform a Boolean AND between two objects.				     *
*****************************************************************************/
ObjectStruct *BooleanAND(ObjectStruct *PObj1, ObjectStruct *PObj2)
{
    ObjectStruct *PObj;

    if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_AND)) != NULL)
	return PObj;
    else {
	if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
	    signal(SIGFPE, BooleanFPE);	 /* Will trap floating point errors. */
	    if (BooleanOutputInterCurve)
		PObj = BooleanLow1In2(PObj1, PObj2);/* Ret intersection crv. */
	    else
		PObj = BooleanCombineTwoObjs(BooleanLow1In2(PObj1, PObj2),
					     BooleanLow1In2(PObj2, PObj1));
	}
	else {/* We gain control from fatal error long jump - ret empty obj. */
	    PObj = GenPolyObject("", NULL, NULL);
	}
    }

    signal(SIGFPE, DefaultFPEHandler);		    /* Default FPE trapping. */

    SetObjectColor(PObj, BooleanOutputInterCurve ?
			 GlblICrvColor :
			 GlblBoolColor);       /* Default bool object color. */

    return PObj;
}

/*****************************************************************************
*   Perform a Boolean SUBSTRACT between two objects (PObj1 - PObj2).	     *
*****************************************************************************/
ObjectStruct *BooleanSUB(ObjectStruct *PObj1, ObjectStruct *PObj2)
{
    ObjectStruct *PObj, *PTemp, *PTempRev;

    if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_SUB)) != NULL)
	return PObj;
    else {
	if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
	    signal(SIGFPE, BooleanFPE);	 /* Will trap floating point errors. */
	    /* The 1 in 2 must be reversed (the inside/outside orientation): */
	    if (BooleanOutputInterCurve) {
		PObj = BooleanLow1In2(PObj2, PObj1);/* Ret intersection crv. */
	    }
	    else {
		PTemp = BooleanLow1In2(PObj2, PObj1);
		PTempRev = BooleanNEG(PTemp);
		MyFree((char *) PTemp, ALLOC_OBJECT);

		PObj = BooleanCombineTwoObjs(BooleanLow1Out2(PObj1, PObj2),
					     PTempRev);
	    }
	}
	else {/* We gain control from fatal error long jump - ret empty obj. */
	    PObj = GenPolyObject("", NULL, NULL);
	}
    }

    signal(SIGFPE, DefaultFPEHandler);	            /* Default FPE trapping. */

    SetObjectColor(PObj, BooleanOutputInterCurve ?
			 GlblICrvColor :
			 GlblBoolColor);       /* Default bool object color. */

    return PObj;
}

/*****************************************************************************
*   Perform a Boolean CUT between two objects (PObj1 / PObj2).		     *
*****************************************************************************/
ObjectStruct *BooleanCUT(ObjectStruct *PObj1, ObjectStruct *PObj2)
{
    ObjectStruct *PObj;

    if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_CUT)) != NULL)
	return PObj;
    else {
	if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
	    signal(SIGFPE, BooleanFPE);	 /* Will trap floating point errors. */
	    /* The 1 in 2 must be reversed (the inside/outside orientation): */
	    if (BooleanOutputInterCurve) {
		PObj = BooleanLow1In2(PObj2, PObj1);/* Ret intersection crv. */
	    }
	    else {
		PObj = BooleanLow1Out2(PObj1, PObj2);
	    }
	}
	else {/* We gain control from fatal error long jump - ret empty obj. */
	    PObj = GenPolyObject("", NULL, NULL);
	}
    }

    signal(SIGFPE, DefaultFPEHandler);	            /* Default FPE trapping. */

    SetObjectColor(PObj, BooleanOutputInterCurve ?
			 GlblICrvColor :
			 GlblBoolColor);       /* Default bool object color. */

    return PObj;
}

/*****************************************************************************
*   Perform a Boolean MERGE between two objects.			     *
*****************************************************************************/
ObjectStruct *BooleanMERGE(ObjectStruct *PObj1, ObjectStruct *PObj2)
{
    ObjectStruct *PObj;
    PolygonStruct *Pl;

    if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_MERGE)) != NULL)
	return PObj;
    else {
	if (PObj1 -> U.Pl.P == NULL)
    	    PObj = CopyObject(NULL, PObj2, FALSE);
    	else {
    	    PObj = CopyObject(NULL, PObj1, FALSE);       /* Copy Obj1 polys. */
	    Pl = PObj -> U.Pl.P;
	    while (Pl -> Pnext) Pl = Pl -> Pnext;
	    Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl.P);   /* Obj2 polys. */
	}
    }

    SetObjectColor(PObj, GlblBoolColor);       /* Default bool object color. */

    return PObj;
}

/*****************************************************************************
*   Perform a Boolean NEGATION of given object PObj.			     *
*  Negation is simply reversing the direction of the plane equation of each  *
* polygon - the simplest Boolean operation...				     *
*****************************************************************************/
ObjectStruct *BooleanNEG(ObjectStruct *PObj)
{
    int i;
    ObjectStruct *PTemp;
    PolygonStruct *Pl;
    VertexStruct *V;

    if ((PTemp = VerifyBooleanInput(PObj, NULL, BOOL_OPER_NEG)) != NULL)
	return PTemp;
    else {
	PTemp = CopyObject(NULL, PObj, FALSE); /* Make fresh copy of object. */

	/* Scans all polygons and reverse plane equation and their vetrex    */
	/* list (cross prod. of consecutive edges must be in normal dir.).   */
	Pl = PTemp -> U.Pl.P;
	while (Pl != NULL) {
	    for (i = 0; i < 4; i++) Pl -> Plane[i] = (-Pl -> Plane[i]);
	    RST_CONVEX_POLY(Pl);

	    /* Invert vertices normals as well. */
	    V = Pl -> V;
	    do {
		PT_SCALE(V -> Normal, -1.0);
		V = V -> Pnext;
	    }
	    while (V != NULL && V != Pl -> V);

	    Pl = Pl -> Pnext;
	}
    }

    signal(SIGFPE, DefaultFPEHandler);		    /* Default FPE trapping. */

    SetObjectColor(PTemp, BooleanOutputInterCurve ?
			  GlblICrvColor :
			  GlblBoolColor);      /* Default bool object color. */

    return PTemp;
}

/*****************************************************************************
*   Combining two geometric objects, by simply concat. their polygon lists:  *
*****************************************************************************/
static ObjectStruct *BooleanCombineTwoObjs(ObjectStruct *PObj1,
					   ObjectStruct *PObj2)
{
    PolygonStruct *Pl;

    CleanUpPolygonList(&PObj1 -> U.Pl.P);
    CleanUpPolygonList(&PObj2 -> U.Pl.P);

    if (PObj2 == NULL)
	return PObj1;
    else {
	if (PObj1 == NULL) return NULL;
	Pl = PObj1 -> U.Pl.P;
	while (Pl -> Pnext != NULL) Pl = Pl -> Pnext;
	Pl -> Pnext = PObj2 -> U.Pl.P;/* Concat. the polygons into one list. */
	PObj2 -> U.Pl.P = NULL;	    /* And release the second object header. */
	MyFree((char *) PObj2, ALLOC_OBJECT);
	return PObj1;
    }
}

/*****************************************************************************
*   Routine to clean up Boolean operation result polygons - delete zero      *
* length edges, and polygons with less than 3 vertices.			     *
*****************************************************************************/
void CleanUpPolygonList(PolygonStruct **PPolygon)
{
    PolygonStruct *PPHead, *PPLast;
    VertexStruct *PVHead, *PVTemp, *PVNext;

    PPLast = PPHead = (*PPolygon);

    while (PPHead != NULL) {
	PVHead = PVTemp = PPHead -> V;
	/* Look for zero length edges (V == V -> Pnext): */
	do {
	    PVNext = PVTemp -> Pnext;
	    if (PT_EQ(PVTemp -> Pt, PVNext -> Pt)) {	   /* Delete PVNext. */
		PVTemp -> Pnext = PVTemp -> Pnext -> Pnext;
		PVNext -> Pnext = NULL;			/* Free only PVNext. */
		if (PVHead == PVNext) {	      /* If we actually kill header. */
		    PPHead -> V = PVHead = PVTemp;
		    break;
		}
		MyFree((char *) PVNext, ALLOC_VERTEX);
	    }
	    else
		PVTemp = PVTemp -> Pnext;
	}
	while (PVTemp != NULL && PVTemp != PVHead);

	/* Now test if at list 3 vertices in polygon, otherwise delete it:   */
	if (PVHead == PVHead -> Pnext ||		 /* One vertex only. */
	    PVHead == PVHead -> Pnext -> Pnext) {      /* Two vertices only. */
	    if (PPHead == (*PPolygon)) {
		*PPolygon = (*PPolygon) -> Pnext;
		PPHead -> Pnext = NULL;
		MyFree((char *) PPHead, ALLOC_POLYGON);
		PPHead = (*PPolygon);
	    }
	    else {
		PPLast -> Pnext = PPHead -> Pnext;
		PPHead -> Pnext = NULL;
		MyFree((char *) PPHead, ALLOC_POLYGON);
		PPHead = PPLast -> Pnext;
	    }
	}
	else {
	    PPLast = PPHead;
	    PPHead = PPHead -> Pnext;
	}
    }
}

/*****************************************************************************
*   Routine that is called from the floating point package in case of fatal  *
* floating point error. Print error message, and quit the Boolean module.    *
*****************************************************************************/
#ifdef __MSDOS__
static void cdecl BooleanFPE(int Sig, int Type, int *RegList)
#else
static void BooleanFPE(int Type)
#endif /* __MSDOS__ */
{
    PrintFPError(Type);		     /* Print the floating point error type. */

    FatalErrorType = FTL_BOOL_FPE;

    longjmp(LclLongJumpBuffer, 1);
}

/*****************************************************************************
*   Routine to select the output kind needed. Output of a Boolean operator   *
* can be the real Boolean result model, or the intersection curves only.     *
*****************************************************************************/
static void SetBooleanOutputKind(void)
{
    ObjectStruct *PObj = GetObject("INTERCRV");

    if (PObj == NULL || !IS_NUM_OBJ(PObj)) {
	WndwInputWindowPutStr("No numeric object name INTERCRV is defined");
	BooleanOutputInterCurve = FALSE;
    }
    else
	BooleanOutputInterCurve = !APX_EQ(PObj -> U.R, 0.0);
}

/*****************************************************************************
*   Routine that is called by the Boolean low level routines every small     *
* amount of time (syncronically) to test if ^C/^Break was pressed and quit   *
* if so. Note we could do it asyncronically, but this complicate thing too   *
* much, and makes them highly unportable...				     *
*****************************************************************************/
void TestBooleanCtrlBrk(void)
{
    if (GlblWasCtrlBrk) {
	WndwInputWindowPutStr("Control Break traps - Empty object result");

	FatalErrorType = FTL_BOOL_CTRL_BRK;

	longjmp(LclLongJumpBuffer, 1);
    }
}

/*****************************************************************************
*   Routine that is called by the bool-low module in fatal cases errors.     *
* Will print error message and long jump using LclLongJumpBuffer.	     *
*****************************************************************************/
void FatalBooleanError(int ErrorType)
{
    char s[LINE_LEN_LONG];

    FatalErrorType = ErrorType;

    switch (ErrorType) {
	case FTL_BOOL_NO_INTER:
	    /* If operation is union (OR), then if no intersection we assume */
	    /* the objects have no common volume and simply combine them!    */
	    if (BooleanOperation != BOOL_OPER_OR) {
		sprintf(s, "Boolean: %s",
			"Objects do not intersect - Empty object result");
		WndwInputWindowPutStr(s);
	    }
	    break;
	default:
	    sprintf(s, "Boolean: Undefined Fatal Error (%d !?)", ErrorType);
	    WndwInputWindowPutStr(s);
	    break;
    }

    longjmp(LclLongJumpBuffer, 1);
}