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