home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / mac / developm / source / macraysh.sit / Code / Source / csg.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-04  |  10.4 KB  |  462 lines
  1. /*
  2.  * csg.c
  3.  *
  4.  * Copyright (C) 1991, Rod G. Bogart, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * $Id: csg.c,v 4.0 91/07/17 14:37:00 kolb Exp Locker: kolb $
  17.  *
  18.  * $Log:    csg.c,v $
  19.  * Revision 4.0  91/07/17  14:37:00  kolb
  20.  * Initial version.
  21.  * 
  22.  */
  23.  
  24. #include "geom.h"
  25. #include "csg.h"
  26.  
  27. #define csg_set_enter(l, f) ((l)->data[0].enter = (f) + 1)
  28.  
  29. Methods *iCsgMethods = NULL;
  30. static char csgName[] = "csg";
  31.  
  32. static int    CsgUnionInt(), CsgDifferenceInt(),
  33.         CsgIntersectInt();
  34. static void    CsgHitlistCopy(), CsgSetBounds();
  35.  
  36. Csg *
  37. CsgCreate(op)
  38. int op;
  39. {
  40.     Csg *csg;
  41.  
  42.     csg = (Csg *)share_malloc(sizeof(Csg));
  43.     csg->operator = op;
  44.     csg->obj1 = csg->obj2 = (Geom *)NULL;
  45.  
  46.  
  47.     switch(op) {
  48.         case CSG_UNION:
  49.             csg->intmeth = CsgUnionInt;
  50.             break;
  51.         case CSG_INTERSECT:
  52.             csg->intmeth = CsgIntersectInt;
  53.             break;
  54.         case CSG_DIFFERENCE:
  55.             csg->intmeth = CsgDifferenceInt;
  56.             break;
  57.         default:
  58.             RLerror(RL_ABORT, "Unknown csg op type %d?\n",(char *)op,0,0);
  59.     }
  60.     return csg;
  61. }
  62.  
  63. Methods *
  64. CsgMethods()
  65. {
  66.     if (iCsgMethods== (Methods *)NULL) {
  67.         iCsgMethods = MethodsCreate();
  68.         iCsgMethods->create = (GeomCreateFunc *)CsgCreate;
  69.         iCsgMethods->convert = CsgConvert;
  70.         iCsgMethods->methods = CsgMethods;
  71.         iCsgMethods->name = CsgName;
  72.         iCsgMethods->intersect = CsgIntersect;
  73.         iCsgMethods->bounds = CsgBounds;
  74.         iCsgMethods->checkbounds = FALSE;
  75.         iCsgMethods->closed = TRUE;
  76.     }
  77.     return iCsgMethods;
  78. }
  79.  
  80. char *
  81. CsgName()
  82. {
  83.     return csgName;
  84. }
  85.  
  86. csg_intersect_objs(csg, ray, hit1, hit2, mindist, dist1, dist2)
  87. Csg *csg;
  88. Ray *ray;
  89. HitList *hit1, *hit2;
  90. Float mindist, *dist1, *dist2;
  91. {
  92.     int operator;
  93.  
  94.     hit1->nodes = 0;
  95.     hit2->nodes = 0;
  96.     *dist1 = FAR_AWAY;
  97.     *dist2 = FAR_AWAY;
  98.     operator = csg->operator;
  99.  
  100.     if (!intersect(csg->obj1, ray, hit1, mindist, dist1) &&
  101.         ((operator == CSG_INTERSECT) || (operator == CSG_DIFFERENCE))) {
  102.         /*
  103.          * Intersection and Difference cases: if you miss the first
  104.          * object, you missed the whole thing.
  105.          */
  106.         return FALSE;
  107.     }
  108.  
  109.     if (!intersect(csg->obj2, ray, hit2, mindist, dist2) &&
  110.         ((operator == CSG_INTERSECT) ||
  111.          (hit1->nodes == 0) && (operator == CSG_UNION))) {
  112.         /*
  113.          * Intersect case:  if you miss either object, you miss whole
  114.          * Union case: if you miss both object, you miss whole
  115.          */
  116.         return FALSE;
  117.     }
  118.  
  119.     return TRUE;
  120. }
  121.  
  122. int
  123. csg_enter_obj(hitp)
  124. HitList *hitp;
  125. {
  126.     if (hitp->data[0].enter)
  127.         return hitp->data[0].enter - 1;
  128.  
  129.     return PrimEnter(hitp->data[0].obj, &hitp->data[0].ray,
  130.             hitp->data[0].mindist, hitp->data[0].dist);
  131. }
  132.  
  133. static int
  134. CsgUnionInt(ray, hit1p, hit2p, dist1, dist2, hitclose, distclose)
  135. Ray *ray;
  136. HitList *hit1p, *hit2p, **hitclose;
  137. Float dist1, dist2, *distclose;
  138. {
  139.     Float distnext;
  140.     HitList hitnext, *hittmp;
  141.  
  142.     while (TRUE) {
  143.         if (hit2p->nodes == 0 ||
  144.             csg_enter_obj(hit2p)) {
  145.             /* return hit1 */
  146.             *hitclose = hit1p;
  147.             *distclose = dist1;
  148.             csg_set_enter(hit1p, csg_enter_obj(hit1p));
  149.             return TRUE;
  150.         } else {
  151.             distnext = FAR_AWAY;
  152.             hitnext.nodes = 0;
  153.             if (!intersect(hit1p->data[hit1p->nodes-1].obj,
  154.                 ray, &hitnext, dist2+EPSILON, &distnext)) {
  155.                 /*
  156.                  * None of obj1 beyond, return hit2 (leaving)
  157.                  */
  158.                 *hitclose = hit2p;
  159.                 *distclose = dist2;
  160.                 csg_set_enter(hit2p, FALSE);
  161.                 return TRUE;
  162.             } else {
  163.                 /*
  164.                  * Since hit1 is supposed to be the close one,
  165.                  * swap them and copy hitnext into hit2.
  166.                       */
  167.                 hittmp = hit1p;
  168.                 hit1p = hit2p;
  169.                 hit2p = hittmp;
  170.                 dist1 = dist2;
  171.                 CsgHitlistCopy(&hitnext, hit2p);
  172.                 dist2 = distnext;
  173.                 /* and continue */
  174.             }
  175.         }
  176.     }
  177. }
  178.  
  179. static int
  180. CsgIntersectInt(ray, hit1p, hit2p, dist1, dist2, hitclose, distclose)
  181. Ray *ray;
  182. HitList *hit1p, *hit2p, **hitclose;
  183. Float dist1, dist2, *distclose;
  184. {
  185.     HitList *hittmp, hitnext;
  186.     Float distnext;
  187.  
  188.     while (TRUE) {
  189.         if (!csg_enter_obj(hit2p)) {
  190.             /* Ray is leaving obj2 */
  191.             /* Return hit1 info */
  192.             *hitclose = hit1p;
  193.             *distclose = dist1;
  194.             csg_set_enter(hit1p, csg_enter_obj(hit1p));
  195.             return TRUE;
  196.         } else {
  197.             distnext = FAR_AWAY;
  198.             hitnext.nodes = 0;
  199.             if (!intersect(hit1p->data[hit1p->nodes-1].obj,
  200.                 ray, &hitnext, dist2+EPSILON, &distnext)) {
  201.                 /*
  202.                  * None of obj1 beyond, so return miss
  203.                  */
  204.                 return FALSE;
  205.             } else {
  206.                 /*
  207.                  * Since hit1 is supposed to be the
  208.                  * close one, swap them and copy
  209.                  * hitnext into hit2.
  210.                  */
  211.                 hittmp = hit1p;
  212.                 hit1p = hit2p;
  213.                 hit2p = hittmp;
  214.                 dist1 = dist2;
  215.                 CsgHitlistCopy(&hitnext, hit2p);
  216.                 dist2 = distnext;
  217.                 /* and continue */
  218.             }
  219.         }
  220.     }
  221. }
  222.  
  223. static int
  224. CsgDifferenceInt(ray, hit1p, hit2p, dist1, dist2, hitclose, distclose)
  225. Ray *ray;
  226. HitList *hit1p, *hit2p, **hitclose;
  227. Float dist1, dist2, *distclose;
  228. {
  229.     Float distnext;
  230.     HitList hitnext;
  231.  
  232.     while (TRUE) {
  233.         if (dist1 < dist2) {
  234.             if (hit2p->nodes == 0 ||
  235.                 csg_enter_obj(hit2p)) {
  236.                 /* return hit1 */
  237.                 *hitclose = hit1p;
  238.                 *distclose = dist1;
  239.                 csg_set_enter(hit1p, csg_enter_obj(hit1p));
  240.                 return TRUE;
  241.             } else {
  242.                 distnext = FAR_AWAY;
  243.                 hitnext.nodes = 0;
  244.                 if (!intersect(hit1p->data[hit1p->nodes-1].obj,
  245.                     ray, &hitnext, dist2+EPSILON, &distnext)) {
  246.                     /*
  247.                      * None of obj1 beyond, so
  248.                      * return miss
  249.                      */
  250.                     return FALSE;
  251.                 } else {
  252.                     dist1 = distnext;
  253.                     CsgHitlistCopy(&hitnext, hit1p);
  254.                     /* and continue */
  255.                 }
  256.             }
  257.         } else { /* dist1 <= dist2 */
  258.             if (hit1p->nodes == 0) {
  259.                 /* return a miss */
  260.                 return FALSE;
  261.             }
  262.             if (!csg_enter_obj(hit1p)) {
  263.                 /*
  264.                  * return hit2, but invert hit2
  265.                  * Enter/Leave flag
  266.                  */
  267.                 *hitclose = hit2p;
  268.                 *distclose = dist2;
  269.                 csg_set_enter(hit2p, !csg_enter_obj(hit2p));
  270.                 return TRUE;
  271.             } else {
  272.                 distnext = FAR_AWAY;
  273.                 hitnext.nodes = 0;
  274.                 if (!intersect(hit2p->data[hit2p->nodes-1].obj,
  275.                     ray, &hitnext, dist1+EPSILON, &distnext)) {
  276.                     /*
  277.                      * None of obj2 beyond, so
  278.                      * return hit1
  279.                      */
  280.                     *hitclose = hit1p;
  281.                     *distclose = dist1;
  282.                     /* we know we're entering obj1 */
  283.                     csg_set_enter(hit1p, TRUE);
  284.                     return TRUE;
  285.                 } else {
  286.                     dist2 = distnext;
  287.                     CsgHitlistCopy(&hitnext, hit2p);
  288.                     /* and continue */
  289.                 }
  290.             }
  291.         }
  292.     }
  293. }
  294.  
  295. int
  296. CsgIntersect(csg, ray, hitlist, mindist, maxdist)
  297. Csg *csg;
  298. Ray *ray;
  299. HitList *hitlist;
  300. Float mindist, *maxdist;
  301. {
  302.     Float dist1, dist2, disttmp, distclose;
  303.     HitList hit1, hit2, *hit1p, *hit2p, *hitclose;
  304.  
  305.     hit1p = &hit1;
  306.     hit2p = &hit2;
  307.     if (!csg_intersect_objs(csg, ray, hit1p, hit2p, mindist,
  308.         &dist1, &dist2)) {
  309.         /* missed the csg object */
  310.         return FALSE;
  311.     }
  312.  
  313.     if ((dist1 > dist2) &&
  314.         (csg->operator == CSG_UNION || csg->operator == CSG_INTERSECT)) {
  315.         /* swap so 1 is closest (except in difference case) */
  316.         disttmp = dist2;  
  317.         dist2 = dist1;  
  318.         dist1 = disttmp;
  319.         hit1p = &hit2;  
  320.         hit2p = &hit1;
  321.     }
  322.  
  323.     /*
  324.      * Call appropriate intersection method.  If FALSE is return,
  325.      * no hit of any kind was found.
  326.      */
  327.     if (!(*csg->intmeth)(ray, hit1p, hit2p, dist1, dist2,
  328.         &hitclose, &distclose))
  329.         return FALSE;
  330.  
  331.     /*
  332.      * At this time, the closest hit is in hitclose and
  333.      * distclose.
  334.      */
  335.     if (distclose < mindist || distclose > *maxdist)
  336.         return FALSE;
  337.  
  338.     CsgHitlistCopy(hitclose, hitlist);
  339.     *maxdist = distclose;
  340.     return TRUE;
  341. }
  342.  
  343. static void
  344. CsgHitlistCopy(from, to)
  345. HitList *from, *to;
  346. {
  347.     int i;
  348.  
  349.     to->nodes = from->nodes;
  350.     for (i = 0; i < from->nodes; i++)
  351.         to->data[i] = from->data[i];
  352. }
  353.  
  354. static void
  355. CsgSetBounds(csg, bounds)
  356. Csg *csg;
  357. Float bounds[2][3];
  358. {
  359.     GeomComputeBounds(csg->obj1);
  360.     GeomComputeBounds(csg->obj2);
  361.  
  362.     switch (csg->operator) {
  363.     case CSG_UNION:
  364.         bounds[LOW][X] = min(csg->obj1->bounds[LOW][X], csg->obj2->bounds[LOW][X]);
  365.         bounds[HIGH][X] = max(csg->obj1->bounds[HIGH][X], csg->obj2->bounds[HIGH][X]);
  366.         bounds[LOW][Y] = min(csg->obj1->bounds[LOW][Y], csg->obj2->bounds[LOW][Y]);
  367.         bounds[HIGH][Y] = max(csg->obj1->bounds[HIGH][Y], csg->obj2->bounds[HIGH][Y]);
  368.         bounds[LOW][Z] = min(csg->obj1->bounds[LOW][Z], csg->obj2->bounds[LOW][Z]);
  369.         bounds[HIGH][Z] = max(csg->obj1->bounds[HIGH][Z], csg->obj2->bounds[HIGH][Z]);
  370.         break;
  371.     case CSG_INTERSECT:
  372.         bounds[LOW][X] = max(csg->obj1->bounds[LOW][X], csg->obj2->bounds[LOW][X]);
  373.         bounds[HIGH][X] = min(csg->obj1->bounds[HIGH][X], csg->obj2->bounds[HIGH][X]);
  374.         bounds[LOW][Y] = max(csg->obj1->bounds[LOW][Y], csg->obj2->bounds[LOW][Y]);
  375.         bounds[HIGH][Y] = min(csg->obj1->bounds[HIGH][Y], csg->obj2->bounds[HIGH][Y]);
  376.         bounds[LOW][Z] = max(csg->obj1->bounds[LOW][Z], csg->obj2->bounds[LOW][Z]);
  377.         bounds[HIGH][Z] = min(csg->obj1->bounds[HIGH][Z], csg->obj2->bounds[HIGH][Z]);
  378.         break;
  379.     case CSG_DIFFERENCE:
  380.         bounds[LOW][X] = csg->obj1->bounds[LOW][X];
  381.         bounds[HIGH][X] = csg->obj1->bounds[HIGH][X];
  382.         bounds[LOW][Y] = csg->obj1->bounds[LOW][Y];
  383.         bounds[HIGH][Y] = csg->obj1->bounds[HIGH][Y];
  384.         bounds[LOW][Z] = csg->obj1->bounds[LOW][Z];
  385.         bounds[HIGH][Z] = csg->obj1->bounds[HIGH][Z];
  386.         break;
  387.     default:
  388.         RLerror(RL_ABORT, "Unknown csg operator type %d?\n",
  389.             (char *)csg->operator,0,0);
  390.     }
  391. }
  392.  
  393. /*
  394.  * Return index of hitlist node closest to the leaf and not below any
  395.  * CSG object.
  396.  */
  397. int
  398. FirstCSGGeom(hitlist)
  399. HitList *hitlist;
  400. {
  401.     int i;
  402.  
  403.     /*
  404.      * UUUUGLY -- detect if obj is a CsgGeom by comparing
  405.      * methods with iCsgMethods.
  406.      */
  407.     for (i = hitlist->nodes -1; i; i--)
  408.         if (hitlist->data[i].obj->methods == iCsgMethods)
  409.             return i;
  410.     return 0;
  411. }
  412.  
  413. void
  414. CsgBounds(csg, bounds)
  415. Csg *csg;
  416. Float bounds[2][3];
  417. {
  418.     CsgSetBounds(csg, csg->bounds);
  419.     BoundsCopy(csg->bounds, bounds);
  420. }
  421.  
  422. int
  423. CsgConvert(csg, list)
  424. Csg *csg;
  425. Geom *list;
  426. {
  427.     static int OpenAdvised = FALSE;
  428.     /*
  429.      * Currently, this only handles two objects.
  430.      * Will be fixed in the future.
  431.      * No really we promise.
  432.      */
  433.     if (!list || !list->next) {
  434. /*        RLerror(RL_WARN, "CSG needs at least two objects.\n"); */
  435.         return 0;
  436.     }
  437.     if (list->next->next) {
  438. /*        RLerror(RL_WARN, "Currently, CSG only handles two objects.\n"); */
  439.         return 0;
  440.     }
  441.     /*
  442.      * Things are put into lists backwards....
  443.      */
  444.     csg->obj2 = list;
  445.     csg->obj1 = list->next;
  446.     if ((!csg->obj1->methods->closed || !csg->obj2->methods->closed) &&
  447.         !OpenAdvised) {
  448. /*        RLerror(RL_ADVISE,
  449.             "Performing CSG with non-closed object(s).\n"); */
  450.         OpenAdvised = TRUE;
  451.     }
  452.     return csg->obj1->prims + csg->obj2->prims;
  453. }
  454.  
  455. void
  456. CsgMethodRegister(meth)
  457. UserMethodType meth;
  458. {
  459.     if (iCsgMethods)
  460.         iCsgMethods->user = meth;
  461. }
  462.