home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The World of Computer Software
/
World_Of_Computer_Software-02-385-Vol-1of3.iso
/
i
/
iritsm3s.zip
/
irit
/
bool-hi.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-01-28
|
17KB
|
490 lines
/*****************************************************************************
* "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);
}