home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / IRIT / IRITS.ZIP / BOOL-HI.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-05  |  14.6 KB  |  425 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the high level boolean operations. The other modules    *
  7. * should only call this module to perform boolean operations. All the        *
  8. * operations are none-destructives, meaning the given data is not modified.  *
  9. *   Note all the polygons of the two given objects must be convex, and the   *
  10. * returned object will also have only convex polygons!                 *
  11. *****************************************************************************/
  12.  
  13. /* #define DEBUG        If defined, return intersection polyline object. */
  14.  
  15. #ifdef __MSDOS__
  16. #include <graphics.h>
  17. #include <alloc.h>
  18. #endif /* __MSDOS__ */
  19.  
  20. #include <stdio.h>
  21. #include <ctype.h>
  22. #include <math.h>
  23. #include <string.h>
  24. #include <signal.h>
  25. #include "program.h"
  26. #include "allocatg.h"
  27. #include "objects.h"
  28. #include "ctrl-brk.h"
  29. #include "graphgng.h"
  30. #include "booleang.h"
  31. #include "booleanl.h"
  32. #include "convexg.h"
  33. #include "windowsg.h"
  34. #include "matherr.h"
  35.  
  36. #ifndef __MSDOS__
  37. #include "xgraphic.h"
  38. #endif /* __MSDOS__ */
  39.  
  40. int BooleanOutputInterCurve = FALSE;    /* Kind of output from boolean oper. */
  41.  
  42. static jmp_buf LclLongJumpBuffer;         /* Used in fatal boolean error. */
  43. static int FatalErrorType,             /* Type of fatal boolean error. */
  44.        BooleanOperation;           /* One of BooleanOR, BooleanAND, etc. */
  45.  
  46. static ObjectStruct *BooleanCombineTwoObjs(ObjectStruct *PObj1,
  47.                        ObjectStruct *PObj2);
  48. static void BooleanFPE(int Sig, int Type, int *RegList);
  49. static void SetBooleanOutputKind(void);
  50.  
  51. /*****************************************************************************
  52. *   Perform a boolean OR between two objects.                     *
  53. *****************************************************************************/
  54. ObjectStruct *BooleanOR(ObjectStruct *PObj1, ObjectStruct *PObj2)
  55. {
  56.     ObjectStruct *PObj;
  57.     PolygonStruct *Pl;
  58.  
  59.     BooleanOperation = BOOL_OPEN_OR;
  60.  
  61.     if (!IS_GEOM_OBJ(PObj1) || !IS_GEOM_OBJ(PObj2))
  62.     FatalError("Boolean: operation on none geometric object(s)\n");
  63.  
  64.     signal(SIGFPE, BooleanFPE);         /* Will trap floating point errors. */
  65.  
  66.     if (IS_POLYLINE_GEOM_OBJ(PObj1) && IS_POLYLINE_GEOM_OBJ(PObj2)) {
  67.     if (PObj1 -> U.Pl == NULL) PObj = CopyObject(NULL, PObj2, FALSE);
  68.     else {
  69.         PObj = CopyObject(NULL, PObj1, FALSE);   /* Copy Obj1 polylines. */
  70.         Pl = PObj -> U.Pl;
  71.         while (Pl -> Pnext) Pl = Pl -> Pnext;
  72.         Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl); /* Obj2 polylines. */
  73.     }
  74.     }
  75.     else
  76.     if (IS_POLYLINE_GEOM_OBJ(PObj1) || IS_POLYLINE_GEOM_OBJ(PObj2)) {
  77.     WndwInputWindowPutStr(
  78.        "Boolean: illegal operation on mixed polygon/line geometric object(s).",
  79.        RED);
  80.     PObj = GenGeomObject("", NULL, NULL);
  81.     }
  82.     else {
  83.     ConvexPolyObject(PObj1);       /* Make sure all polygons are convex: */
  84.     ConvexPolyObject(PObj2);
  85.  
  86.     SetBooleanOutputKind();
  87.  
  88.     if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
  89.         signal(SIGFPE, BooleanFPE);     /* Will trap floating point errors. */
  90.         if (BooleanOutputInterCurve)
  91.         PObj = BooleanLow1Out2(PObj1, PObj2);/* Ret intersection crv.*/
  92.         else
  93.         PObj = BooleanCombineTwoObjs(BooleanLow1Out2(PObj1, PObj2),
  94.                          BooleanLow1Out2(PObj2, PObj1));
  95.     }
  96.     else {
  97.         /* We gain control from fatal error long jump - usually we should*/
  98.         /* return empty object, but if error is No intersection between  */
  99.         /* the two objects, we assume they have no common volume and     */
  100.         /* return a new object consists of the concat. of all polygons!  */
  101.         if (FatalErrorType != FTL_BOOL_NO_INTER) {
  102.         PObj = GenGeomObject("", NULL, NULL);/* Return empty object. */
  103.         }
  104.         else {
  105.         if (PObj1 -> U.Pl == NULL) PObj = CopyObject(NULL, PObj2, FALSE);
  106.         else {
  107.             PObj = CopyObject(NULL, PObj1, FALSE);/* Copy Obj1 polys.*/
  108.             Pl = PObj -> U.Pl;
  109.             while (Pl -> Pnext) Pl = Pl -> Pnext;
  110.             Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl);/*Obj2 poly.*/
  111.         }
  112.         }
  113.     }
  114.     }
  115.  
  116.     signal(SIGFPE, DefaultFPEHandler);                /* Default FPE trapping. */
  117.  
  118.     SET_OBJECT_COLOR(PObj, BooleanOutputInterCurve ?
  119.                ICrvColor :
  120.                BoolColor);           /* Default bool object color. */
  121.  
  122.     return PObj;
  123. }
  124.  
  125. /*****************************************************************************
  126. *   Perform a boolean AND between two objects.                     *
  127. *****************************************************************************/
  128. ObjectStruct *BooleanAND(ObjectStruct *PObj1, ObjectStruct *PObj2)
  129. {
  130.     ObjectStruct *PObj;
  131.  
  132.     BooleanOperation = BOOL_OPEN_AND;
  133.  
  134.     if (!IS_GEOM_OBJ(PObj1) || !IS_GEOM_OBJ(PObj2))
  135.     FatalError("Boolean: operation on none geometric object(s)\n");
  136.  
  137.     signal(SIGFPE, BooleanFPE);         /* Will trap floating point errors. */
  138.  
  139.     if (IS_POLYLINE_GEOM_OBJ(PObj1) || IS_POLYLINE_GEOM_OBJ(PObj2)) {
  140.     WndwInputWindowPutStr(
  141.        "Boolean: illegal operation on polyline geometric object(s).",
  142.        RED);
  143.     PObj = GenGeomObject("", NULL, NULL);
  144.     }
  145.     else {
  146.     ConvexPolyObject(PObj1);       /* Make sure all polygons are convex: */
  147.     ConvexPolyObject(PObj2);
  148.  
  149.     SetBooleanOutputKind();
  150.  
  151.     if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
  152.         signal(SIGFPE, BooleanFPE);     /* Will trap floating point errors. */
  153.         if (BooleanOutputInterCurve)
  154.         PObj = BooleanLow1In2(PObj1, PObj2);/* Ret intersection crv. */
  155.         else
  156.         PObj = BooleanCombineTwoObjs(BooleanLow1In2(PObj1, PObj2),
  157.                          BooleanLow1In2(PObj2, PObj1));
  158.     }
  159.     else {/* We gain control from fatal error long jump - ret empty obj. */
  160.         PObj = GenGeomObject("", NULL, NULL);
  161.     }
  162.     }
  163.  
  164.     signal(SIGFPE, DefaultFPEHandler);            /* Default FPE trapping. */
  165.  
  166.     SET_OBJECT_COLOR(PObj, BooleanOutputInterCurve ?
  167.                ICrvColor :
  168.                BoolColor);           /* Default bool object color. */
  169.  
  170.     return PObj;
  171. }
  172.  
  173. /*****************************************************************************
  174. *   Perform a boolean SUBSTRACT between two objects (PObj1 - PObj2).         *
  175. *****************************************************************************/
  176. ObjectStruct *BooleanSUB(ObjectStruct *PObj1, ObjectStruct *PObj2)
  177. {
  178.     ObjectStruct *PObj, *PTemp, *PTempRev;
  179.  
  180.     BooleanOperation = BOOL_OPEN_SUB;
  181.  
  182.     if (!IS_GEOM_OBJ(PObj1) || !IS_GEOM_OBJ(PObj2))
  183.     FatalError("Boolean: operation on none geometric object(s)\n");
  184.  
  185.     signal(SIGFPE, BooleanFPE);         /* Will trap floating point errors. */
  186.  
  187.     if (IS_POLYLINE_GEOM_OBJ(PObj1) || IS_POLYLINE_GEOM_OBJ(PObj2)) {
  188.     WndwInputWindowPutStr(
  189.        "Boolean: illegal operation on polyline geometric object(s).",
  190.        RED);
  191.     PObj = GenGeomObject("", NULL, NULL);
  192.     }
  193.     else {
  194.     ConvexPolyObject(PObj1);       /* Make sure all polygons are convex: */
  195.     ConvexPolyObject(PObj2);
  196.  
  197.     SetBooleanOutputKind();
  198.  
  199.     if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
  200.         signal(SIGFPE, BooleanFPE);     /* Will trap floating point errors. */
  201.         /* The 1 in 2 must be reversed (the inside/outside orientation): */
  202.         if (BooleanOutputInterCurve) {
  203.         PObj = BooleanLow1In2(PObj2, PObj1);/* Ret intersection crv. */
  204.         }
  205.         else {
  206.         PTemp = BooleanLow1In2(PObj2, PObj1);
  207.         PTempRev = BooleanNEG(PTemp);
  208.         MyFree((char *) PTemp, OBJECT_TYPE);
  209.  
  210.         PObj = BooleanCombineTwoObjs(BooleanLow1Out2(PObj1, PObj2),
  211.                          PTempRev);
  212.         }
  213.     }
  214.     else {/* We gain control from fatal error long jump - ret empty obj. */
  215.         PObj = GenGeomObject("", NULL, NULL);
  216.     }
  217.     }
  218.  
  219.     signal(SIGFPE, DefaultFPEHandler);                /* Default FPE trapping. */
  220.  
  221.     SET_OBJECT_COLOR(PObj, BooleanOutputInterCurve ?
  222.                ICrvColor :
  223.                BoolColor);           /* Default bool object color. */
  224.  
  225.     return PObj;
  226. }
  227.  
  228. /*****************************************************************************
  229. *   Perform a boolean NEGATION of given object PObj.                 *
  230. *  Negation is simply reversing the direction of the plane equation of each  *
  231. * polygon - the simplest boolean operation...                     *
  232. *****************************************************************************/
  233. ObjectStruct *BooleanNEG(ObjectStruct *PObj)
  234. {
  235.     int i;
  236.     ObjectStruct *PTemp;
  237.     PolygonStruct *Pl;
  238.  
  239.     BooleanOperation = BOOL_OPEN_NEG;
  240.  
  241.     SetBooleanOutputKind();
  242.  
  243.     if (!IS_GEOM_OBJ(PObj))
  244.     FatalError("Boolean: operation on none geometric object(s)\n");
  245.  
  246.     signal(SIGFPE, BooleanFPE);         /* Will trap floating point errors. */
  247.  
  248.     if (IS_POLYLINE_GEOM_OBJ(PObj)) {
  249.     WndwInputWindowPutStr(
  250.        "Boolean: illegal operation on polyline geometric object(s).",
  251.        RED);
  252.     PTemp = GenGeomObject("", NULL, NULL);
  253.     }
  254.     else {
  255.     PTemp = CopyObject(NULL, PObj, FALSE); /* Make fresh copy of object. */
  256.  
  257.     /* Scans all polygons and reverse plane equation and their vetrex    */
  258.     /* list (cross prod. of consecutive edges must be in normal dir.).   */
  259.     Pl = PTemp -> U.Pl;
  260.     while (Pl != NULL) {
  261.         for (i=0; i<4; i++) Pl -> Plane[i] = (-Pl -> Plane[i]);
  262.         RST_CONVEX_POLY(Pl);
  263.         Pl = Pl -> Pnext;
  264.     }
  265.     }
  266.  
  267.     signal(SIGFPE, DefaultFPEHandler);            /* Default FPE trapping. */
  268.  
  269.     SET_OBJECT_COLOR(PTemp, BooleanOutputInterCurve ?
  270.                 ICrvColor :
  271.                 BoolColor);           /* Default bool object color. */
  272.  
  273.     return PTemp;
  274. }
  275.  
  276. /*****************************************************************************
  277. *   Combining two geometric objects, by simply concat. their polygon lists:  *
  278. *****************************************************************************/
  279. static ObjectStruct *BooleanCombineTwoObjs(ObjectStruct *PObj1,
  280.                        ObjectStruct *PObj2)
  281. {
  282.     PolygonStruct *Pl;
  283.  
  284.     CleanUpPolygonList(&PObj1 -> U.Pl);
  285.     CleanUpPolygonList(&PObj2 -> U.Pl);
  286.  
  287.     if (PObj2 == NULL) return PObj1;
  288.     else {
  289.     if (PObj1 == NULL) return NULL;
  290.     Pl = PObj1 -> U.Pl;
  291.     while (Pl -> Pnext != NULL) Pl = Pl -> Pnext;
  292.     Pl -> Pnext = PObj2 -> U.Pl;  /* Concat. the polygons into one list. */
  293.     PObj2 -> U.Pl = NULL;        /* And release the second object header. */
  294.     MyFree((char *) PObj2, OBJECT_TYPE);
  295.     return PObj1;
  296.     }
  297. }
  298.  
  299. /*****************************************************************************
  300. *   Routine to clean up boolean operation result polygons - delete zero      *
  301. * length edges, and polygons with less than 3 vertices.                 *
  302. *****************************************************************************/
  303. void CleanUpPolygonList(PolygonStruct **PPolygon)
  304. {
  305.     PolygonStruct *PPHead, *PPLast;
  306.     VertexStruct *PVHead, *PVTemp, *PVNext;
  307.  
  308.     PPLast = PPHead = (*PPolygon);
  309.  
  310.     while (PPHead != NULL) {
  311.     PVHead = PVTemp = PPHead -> V;
  312.     /* Look for zero length edges (V == V -> Pnext): */
  313.     do {
  314.         PVNext = PVTemp -> Pnext;
  315.         if (PT_EQ(PVTemp -> Pt, PVNext -> Pt)) {       /* Delete PVNext. */
  316.         PVTemp -> Pnext = PVTemp -> Pnext -> Pnext;
  317.         PVNext -> Pnext = NULL;            /* Free only PVNext. */
  318.         if (PVHead == PVNext) {          /* If we actually kill header. */
  319.             PPHead -> V = PVHead = PVTemp;
  320.             break;
  321.         }
  322.         MyFree((char *) PVNext, VERTEX_TYPE);
  323.         }
  324.         else PVTemp = PVTemp -> Pnext;
  325.     }
  326.     while (PVTemp != NULL && PVTemp != PVHead);
  327.  
  328.     /* Now test if at list 3 vertices in polygon, otherwise delete it:   */
  329.     if (PVHead == PVHead -> Pnext ||         /* One vertex only. */
  330.         PVHead == PVHead -> Pnext -> Pnext) {      /* Two vertices only. */
  331.         if (PPHead == (*PPolygon)) {
  332.         *PPolygon = (*PPolygon) -> Pnext;
  333.         PPHead -> Pnext = NULL;
  334.         MyFree((char *) PPHead, POLYGON_TYPE);
  335.         PPHead = (*PPolygon);
  336.         }
  337.         else {
  338.         PPLast -> Pnext = PPHead -> Pnext;
  339.         PPHead -> Pnext = NULL;
  340.         MyFree((char *) PPHead, POLYGON_TYPE);
  341.         PPHead = PPLast -> Pnext;
  342.         }
  343.     }
  344.     else {
  345.         PPLast = PPHead;
  346.         PPHead = PPHead -> Pnext;
  347.     }
  348.     }
  349. }
  350.  
  351. /*****************************************************************************
  352. *   Routine that is called from the floating point package in case of fatal  *
  353. * floating point error. Print error message, and quit the boolean module.    *
  354. *****************************************************************************/
  355. static void BooleanFPE(int Sig, int Type, int *RegList)
  356. {
  357.     PrintFPError(Type);             /* Print the floating point error type. */
  358.  
  359.     FatalErrorType = FTL_BOOL_FPE;
  360.  
  361.     longjmp(LclLongJumpBuffer, 1);
  362. }
  363.  
  364. /*****************************************************************************
  365. *   Routine to select the output kind needed. Output of a booelan operator   *
  366. * can be the real boolean result model, or the intersection curves only.     *
  367. *****************************************************************************/
  368. static void SetBooleanOutputKind(void)
  369. {
  370.     struct ObjectStruct *PObj = GetObject("INTERCRV");
  371.  
  372.     if (PObj == NULL || !IS_NUM_OBJ(PObj)) {
  373.     WndwInputWindowPutStr("No numeric object name INTERCRV is defined",
  374.                                     RED);
  375.     BooleanOutputInterCurve = FALSE;
  376.     }
  377.     else BooleanOutputInterCurve = !APX_EQ(PObj -> U.R, 0.0);
  378. }
  379.  
  380. /*****************************************************************************
  381. *   Routine that is called by the boolean low level routines every small     *
  382. * amount of time (syncronically) to test if ^C/^Break was pressed and quit   *
  383. * if so. Note we could do it asyncronically, but this complicate thing too   *
  384. * much, and makes them highly unportable...                     *
  385. *****************************************************************************/
  386. void TestBooleanCtrlBrk(void)
  387. {
  388.     if (WasCtrlBrk) {
  389.     WndwInputWindowPutStr("Control Break traps - Empty object result", RED);
  390.  
  391.     FatalErrorType = FTL_BOOL_CTRL_BRK;
  392.  
  393.     longjmp(LclLongJumpBuffer, 1);
  394.     }
  395. }
  396.  
  397. /*****************************************************************************
  398. *   Routine that is called by the bool-low module in fatal cases errors.     *
  399. * Will print error message and long jump using LclLongJumpBuffer.         *
  400. *****************************************************************************/
  401. void FatalBooleanError(int ErrorType)
  402. {
  403.     char s[LINE_LEN_LONG];
  404.  
  405.     FatalErrorType = ErrorType;
  406.  
  407.     switch (ErrorType) {
  408.     case FTL_BOOL_NO_INTER:
  409.         /* If operation is union (OR), then if no intersection we assume */
  410.         /* the objects have no common volume and simply combine them!    */
  411.         if (BooleanOperation != BOOL_OPEN_OR) {
  412.         sprintf(s, "Boolean: %s",
  413.             "Objects do not intersect - Empty object result");
  414.         WndwInputWindowPutStr(s, RED);
  415.         }
  416.         break;
  417.     default:
  418.         sprintf(s, "Boolean: Undefined Fatal Error (%d !?)", ErrorType);
  419.         WndwInputWindowPutStr(s, RED);
  420.         break;
  421.     }
  422.  
  423.     longjmp(LclLongJumpBuffer, 1);
  424. }
  425.