/*****************************************************************************
*   "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 <graphics.h>
#include <alloc.h>
#endif /* __MSDOS__ */

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include <signal.h>
#include "program.h"
#include "allocatg.h"
#include "objects.h"
#include "ctrl-brk.h"
#include "graphgng.h"
#include "booleang.h"
#include "booleanl.h"
#include "convexg.h"
#include "windowsg.h"
#include "matherr.h"

#ifndef __MSDOS__
#include "xgraphic.h"
#endif /* __MSDOS__ */

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 void BooleanFPE(int Sig, int Type, int *RegList);
static void SetBooleanOutputKind(void);

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

    BooleanOperation = BOOL_OPEN_OR;

    if (!IS_GEOM_OBJ(PObj1) || !IS_GEOM_OBJ(PObj2))
	FatalError("Boolean: operation on none geometric object(s)\n");

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

    if (IS_POLYLINE_GEOM_OBJ(PObj1) && IS_POLYLINE_GEOM_OBJ(PObj2)) {
	if (PObj1 -> U.Pl == NULL) PObj = CopyObject(NULL, PObj2, FALSE);
	else {
	    PObj = CopyObject(NULL, PObj1, FALSE);   /* Copy Obj1 polylines. */
	    Pl = PObj -> U.Pl;
	    while (Pl -> Pnext) Pl = Pl -> Pnext;
	    Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl); /* Obj2 polylines. */
	}
    }
    else
    if (IS_POLYLINE_GEOM_OBJ(PObj1) || IS_POLYLINE_GEOM_OBJ(PObj2)) {
	WndwInputWindowPutStr(
	   "Boolean: illegal operation on mixed polygon/line geometric object(s).",
	   RED);
	PObj = GenGeomObject("", NULL, NULL);
    }
    else {
	ConvexPolyObject(PObj1);       /* Make sure all polygons are convex: */
	ConvexPolyObject(PObj2);

	SetBooleanOutputKind();

	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 = GenGeomObject("", NULL, NULL);/* Return empty object. */
	    }
	    else {
		if (PObj1 -> U.Pl == NULL) PObj = CopyObject(NULL, PObj2, FALSE);
		else {
		    PObj = CopyObject(NULL, PObj1, FALSE);/* Copy Obj1 polys.*/
		    Pl = PObj -> U.Pl;
		    while (Pl -> Pnext) Pl = Pl -> Pnext;
		    Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl);/*Obj2 poly.*/
		}
	    }
	}
    }

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

    SET_OBJECT_COLOR(PObj, BooleanOutputInterCurve ?
			   ICrvColor :
			   BoolColor);	       /* Default bool object color. */

    return PObj;
}

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

    BooleanOperation = BOOL_OPEN_AND;

    if (!IS_GEOM_OBJ(PObj1) || !IS_GEOM_OBJ(PObj2))
	FatalError("Boolean: operation on none geometric object(s)\n");

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

    if (IS_POLYLINE_GEOM_OBJ(PObj1) || IS_POLYLINE_GEOM_OBJ(PObj2)) {
	WndwInputWindowPutStr(
	   "Boolean: illegal operation on polyline geometric object(s).",
	   RED);
	PObj = GenGeomObject("", NULL, NULL);
    }
    else {
	ConvexPolyObject(PObj1);       /* Make sure all polygons are convex: */
	ConvexPolyObject(PObj2);

	SetBooleanOutputKind();

	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 = GenGeomObject("", NULL, NULL);
	}
    }

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

    SET_OBJECT_COLOR(PObj, BooleanOutputInterCurve ?
			   ICrvColor :
			   BoolColor);	       /* 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;

    BooleanOperation = BOOL_OPEN_SUB;

    if (!IS_GEOM_OBJ(PObj1) || !IS_GEOM_OBJ(PObj2))
	FatalError("Boolean: operation on none geometric object(s)\n");

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

    if (IS_POLYLINE_GEOM_OBJ(PObj1) || IS_POLYLINE_GEOM_OBJ(PObj2)) {
	WndwInputWindowPutStr(
	   "Boolean: illegal operation on polyline geometric object(s).",
	   RED);
	PObj = GenGeomObject("", NULL, NULL);
    }
    else {
	ConvexPolyObject(PObj1);       /* Make sure all polygons are convex: */
	ConvexPolyObject(PObj2);

	SetBooleanOutputKind();

	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, OBJECT_TYPE);

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

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

    SET_OBJECT_COLOR(PObj, BooleanOutputInterCurve ?
			   ICrvColor :
			   BoolColor);	       /* 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;

    BooleanOperation = BOOL_OPEN_NEG;

    SetBooleanOutputKind();

    if (!IS_GEOM_OBJ(PObj))
	FatalError("Boolean: operation on none geometric object(s)\n");

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

    if (IS_POLYLINE_GEOM_OBJ(PObj)) {
	WndwInputWindowPutStr(
	   "Boolean: illegal operation on polyline geometric object(s).",
	   RED);
	PTemp = GenGeomObject("", NULL, NULL);
    }
    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;
	while (Pl != NULL) {
	    for (i=0; i<4; i++) Pl -> Plane[i] = (-Pl -> Plane[i]);
	    RST_CONVEX_POLY(Pl);
	    Pl = Pl -> Pnext;
	}
    }

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

    SET_OBJECT_COLOR(PTemp, BooleanOutputInterCurve ?
			    ICrvColor :
			    BoolColor);	       /* 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);
    CleanUpPolygonList(&PObj2 -> U.Pl);

    if (PObj2 == NULL) return PObj1;
    else {
	if (PObj1 == NULL) return NULL;
	Pl = PObj1 -> U.Pl;
	while (Pl -> Pnext != NULL) Pl = Pl -> Pnext;
	Pl -> Pnext = PObj2 -> U.Pl;  /* Concat. the polygons into one list. */
	PObj2 -> U.Pl = NULL;	    /* And release the second object header. */
	MyFree((char *) PObj2, OBJECT_TYPE);
	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, VERTEX_TYPE);
	    }
	    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, POLYGON_TYPE);
		PPHead = (*PPolygon);
	    }
	    else {
		PPLast -> Pnext = PPHead -> Pnext;
		PPHead -> Pnext = NULL;
		MyFree((char *) PPHead, POLYGON_TYPE);
		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.    *
*****************************************************************************/
static void BooleanFPE(int Sig, int Type, int *RegList)
{
    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 booelan operator   *
* can be the real boolean result model, or the intersection curves only.     *
*****************************************************************************/
static void SetBooleanOutputKind(void)
{
    struct ObjectStruct *PObj = GetObject("INTERCRV");

    if (PObj == NULL || !IS_NUM_OBJ(PObj)) {
	WndwInputWindowPutStr("No numeric object name INTERCRV is defined",
									RED);
	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 (WasCtrlBrk) {
	WndwInputWindowPutStr("Control Break traps - Empty object result", RED);

	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_OPEN_OR) {
		sprintf(s, "Boolean: %s",
			"Objects do not intersect - Empty object result");
		WndwInputWindowPutStr(s, RED);
	    }
	    break;
	default:
	    sprintf(s, "Boolean: Undefined Fatal Error (%d !?)", ErrorType);
	    WndwInputWindowPutStr(s, RED);
	    break;
    }

    longjmp(LclLongJumpBuffer, 1);
}