home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / raytrace / radiance / simplerd.lha / simplerad / FinalFTP / Light / hbvol.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-21  |  23.5 KB  |  724 lines
  1. /**********************************************************************/
  2. /* hbvol.c                                                            */
  3. /*                                                                    */
  4. /* Hierarchical bounding volume code.                                 */
  5. /* Use of algorithm by [Goldsmith and Salmon87] for automatic         */
  6. /* create of the hierarchy. Note: no shuffling or sorting has been    */
  7. /* done on the input data. Also assume that only axis-aligned         */
  8. /* bounding boxes are in the tree.                                    */
  9. /*                                                                    */
  10. /* Also code for receiver object list creation wrt a given source.    */
  11. /*                                                                    */
  12. /* Copyright (C) 1992, Bernard Kwok                                   */
  13. /* All rights reserved.                                               */
  14. /* Revision 1.0                                                       */
  15. /* May, 1992                                                          */
  16. /**********************************************************************/
  17. #include <stdio.h>
  18. #include <string.h>
  19. #include <math.h>
  20. #include "misc.h"
  21. #include "geo.h"
  22. #include "struct.h"
  23. #include "io.h"
  24. #include "bvol.h"
  25. #include "scull.h"
  26.  
  27. extern OptionType Option;
  28. extern void BoundsPrint();
  29. extern BoundingBoxType BoxPoly();
  30. extern Scene RadScene;         /* Scene enclosed by hiearchy         */
  31. HBBox Scene_BVH;               /* Scene bounding volume hierarchy    */
  32. HBBox_OptionType HBoxOption    /* Hierarchy building options         */
  33.   = { UNCHANGED, ALL_BOX };
  34.     
  35. Object_List *objlist;          /* List of objects seen by source patch*/
  36. Object_List *objlist_tail;     /* End of list                         */
  37. int objlist_size = 0;          /* Size of list                        */
  38. int objlist_receivers = 0;     /* Number of object that are receivers */
  39. HBBox root_BVH;
  40.  
  41. /**********************************************************************/
  42. /* Print a box node */
  43. /**********************************************************************/
  44. void BVH_PrintBox(BVtree)
  45.      HBBox *BVtree;
  46. {
  47.   printf("\tHBox {\n");
  48.   printf("\tarea: %g; ", BVtree->area);
  49.   if (BVtree->object != NULL) {
  50.     printf("object: %s%d ", BVtree->object->name, BVtree->object->id);
  51.     if (BVtree->poly != NULL)
  52.       printf("polygon: %s%d\n", BVtree->poly->name, BVtree->poly->id);
  53.     else
  54.       printf("\n");
  55.   } else
  56.     printf("object: None\n");
  57.  
  58.  
  59.   printf("\tlevel %d; ", BVtree->level);
  60.   if (BVtree->father != NULL)
  61.     printf("father level: %d; ", BVtree->father->level);
  62.   else
  63.     printf("This is the root !; ");
  64.   printf("%d children\n", BVtree->num_children);
  65.  
  66.   BoundsPrint(*BVtree->box, stdout, "");
  67.   printf("\t}\n");
  68. }
  69.  
  70. /**********************************************************************/
  71. /* Print BV tree */
  72. /**********************************************************************/
  73. void BVH_PrintHier(BVtree)
  74.      HBBox *BVtree;
  75. {
  76.   int i;
  77.   
  78.   if (BVtree != NULL) 
  79.     for (i=0;i<BVtree->num_children;i++) {
  80.       BVH_PrintBox(BVtree->child[i]);
  81.       BVH_PrintHier(BVtree->child[i]);
  82.     }
  83. }
  84.  
  85. /**********************************************************************/
  86. /* Cost of bounding box is proportional to area of box                */
  87. /**********************************************************************/
  88. double BVH_Cost_Box(bbox)
  89.      BoundingBoxType *bbox;
  90. {
  91.   double dx,dy,dz;
  92.  
  93.   dx = bbox->max.x - bbox->min.x;
  94.   dy = bbox->max.y - bbox->min.y;
  95.   dz = bbox->max.z - bbox->min.z;
  96.  
  97.   if (HBoxOption.boxtype == ALL_BOX) 
  98.     return((dx + dy)*dz + dx*dy);
  99.   else
  100.     return(2.0*dx*dy + 2.0*dx*dz + 2.0*dy*dz);
  101. }
  102.  
  103. /**********************************************************************/
  104. /* Cost of bounding sphere is proportional to area of sphere          */
  105. /**********************************************************************/
  106. double BVH_Cost_Sphere(bsph)
  107.      BoundingSphereType *bsph;
  108. {
  109.   if (HBoxOption.boxtype == ALL_SPHERE) 
  110.     return(bsph->r * bsph->r);
  111.   else
  112.     return(4.0 * PI * bsph->r * bsph->r);
  113. }
  114.  
  115. /**********************************************************************/
  116. /* Is node a leaf */
  117. /**********************************************************************/
  118. int IsLeafBox(hbox)
  119.      HBBox *hbox;
  120. {  return (hbox->num_children == 0); }
  121.  
  122. /**********************************************************************/
  123. /* Maximum number of children reached */
  124. /**********************************************************************/
  125. int IsFullBox(hbox)
  126.      HBBox *hbox;
  127. {  return (hbox->num_children == MAX_BV_CHILDREN); }
  128.  
  129. /**********************************************************************/
  130. /* Incremental area as a result of insertion of new bounding volume   */
  131. /* into an existing one                                               */
  132. /**********************************************************************/
  133. double BVH_IncrementalCost_Box(hbox, newbox)
  134.      HBBox *hbox;
  135.      BoundingBoxType *newbox;
  136. {
  137.   double old_area, new_area;
  138.   BoundingBoxType incrbox;
  139.   double delta_area;
  140.  
  141.   /* Find increase in area if new box where put into hier. box */
  142.   old_area = hbox->area;
  143.   Bounds_Union(*hbox->box, *newbox, &incrbox);
  144.   new_area = BVH_Cost_Box(&incrbox);
  145.   delta_area = new_area - old_area;
  146.  
  147.   if (Option.debug)
  148.     if (delta_area == 0.0) {
  149.       printf("\tHey no change in area if you added this box in !\n");
  150.     } else {
  151.       printf("\tChange in area = %g\n", delta_area);
  152.     }
  153.   return delta_area;
  154. }
  155.  
  156. /**********************************************************************/
  157. /* Create a new box in heriarchical BV tree */
  158. /**********************************************************************/
  159. HBBox *HBBox_Create(box, poly, obj, hb_father, level)
  160.      BoundingBoxType *box;
  161.      Polygon *poly;
  162.      Objectt *obj;
  163.      HBBox *hb_father;
  164.      int level;
  165. {
  166.   int i;
  167.   HBBox *newhbox;
  168.  
  169.   newhbox = (HBBox *) malloc(sizeof(HBBox));
  170.   newhbox->box = box;
  171.   newhbox->area = BVH_Cost_Box(box);
  172.   newhbox->poly = poly;
  173.   newhbox->object = obj;
  174.   if (hb_father != 0) {
  175.     newhbox->father = hb_father;
  176.   } else {                              /* Is the root of the tree */
  177.     newhbox->father = (HBBox *)NULL;
  178.   }
  179.   newhbox->level = level;
  180.   newhbox->num_children = 0;            /* No children */
  181.   for (i=0;i<MAX_BV_CHILDREN;i++)
  182.     newhbox->child[i] = (HBBox *)NULL;
  183.   
  184.   return newhbox;
  185. }
  186.  
  187. /**********************************************************************/
  188. /* Find cost to add to box to each of children. Return minimum cost   */
  189. /* found and path of minimum cost.                                    */
  190. /**********************************************************************/
  191. int BVH_MinCost_Child(BVtree, box, min_incr)
  192.      HBBox *BVtree;
  193.      BoundingBoxType *box;
  194.      double *min_incr;
  195. {
  196.   int i;
  197.   double incr_cost;
  198.   HBBox *childbox;
  199.   int min_path;  
  200.  
  201.   if (Option.debug) printf("\tStart finding min cost child[0]\n");
  202.   childbox = BVtree->child[0];
  203.   *min_incr = BVH_IncrementalCost_Box(childbox, box);
  204.   min_path = 0;
  205.   
  206.   for(i=1;i<BVtree->num_children;i++) {
  207.   if (Option.debug) printf("\tStart finding min cost child[%d]\n", i);
  208.     childbox = BVtree->child[i];
  209.     incr_cost = BVH_IncrementalCost_Box(childbox, box);
  210.     if (incr_cost < *min_incr) {    /* Find a new min path */
  211.       *min_incr = incr_cost;
  212.       min_path = i;
  213.     }
  214.   }
  215.  
  216.   if (Option.debug) printf("\tEnd finding min cost child\n");
  217.   return min_path;
  218. }
  219.  
  220. /**********************************************************************/
  221. /* Make a duplicate of BV node */
  222. /**********************************************************************/
  223. HBBox *BVH_DuplicateBox(hbox)
  224.      HBBox *hbox;
  225. {
  226.   int i;
  227.   HBBox *nhbox;
  228.  
  229.   nhbox = (HBBox *) malloc(sizeof(HBBox));  
  230.   nhbox->area = hbox->area;
  231.   nhbox->box = hbox->box;
  232.   nhbox->poly = hbox->poly;
  233.   nhbox->object = hbox->object;
  234.   nhbox->father = hbox->father;
  235.   nhbox->num_children = hbox->num_children;
  236.   for (i=0;i<MAX_BV_CHILDREN;i++)
  237.     nhbox->child[i] = hbox->child[i];
  238.   nhbox->level = hbox->level;
  239.  
  240.   return nhbox;
  241. }
  242.  
  243. /**********************************************************************/
  244. /* Quick hack to fix poly root box update problem */
  245. /**********************************************************************/
  246. void Enlarge_Root()
  247. {
  248.   int i;
  249.   BoundingBoxType *newroot_box;
  250.  
  251.   newroot_box = (BoundingBoxType *) malloc(sizeof(BoundingBoxType));
  252.   *newroot_box = *Scene_BVH.box;
  253.  
  254.   for (i=0;i<Scene_BVH.num_children;i++) {
  255.     Bounds_Union(*Scene_BVH.child[i]->box, *newroot_box, newroot_box);  
  256.   }
  257.   Scene_BVH.box = newroot_box;
  258.   Scene_BVH.area = BVH_Cost_Box(Scene_BVH.box);
  259. }
  260.  
  261. /**********************************************************************/
  262. /* Enlarge boxes along a path from a current node up to the root by   */
  263. /* amount of addition of a new box at the current node                */
  264. /**********************************************************************/
  265. void Enlarge_Ancestors(BVtree, box)
  266.      HBBox *BVtree;
  267.      BoundingBoxType *box;
  268. {
  269.   BoundingBoxType *newfather_box;
  270.   
  271.   if (BVtree != 0) {
  272.     /* printf("At level %d:\n", BVtree->level); */
  273.  
  274.     newfather_box = (BoundingBoxType *) malloc(sizeof(BoundingBoxType));
  275.     Bounds_Union(*box, *BVtree->box, newfather_box);  
  276.     free(BVtree->box);
  277.     BVtree->box = newfather_box;
  278.     BVtree->area = BVH_Cost_Box(newfather_box);
  279.     Enlarge_Ancestors(BVtree->father, box);
  280.   }
  281. }
  282.  
  283. /**********************************************************************/
  284. /* Add box as sibling of cuurent BV, create new father */
  285. /**********************************************************************/
  286. void BVH_AddBox_Sibling(BVtree, box, pptr, optr, child_index)
  287.      HBBox *BVtree;
  288.      BoundingBoxType *box;
  289.      Polygon *pptr;
  290.      Objectt *optr;
  291.      int child_index;
  292. {
  293.   HBBox *newhbox, *new_father, *BVtree_sib;
  294.   HBBox *old_father;
  295.   BoundingBoxType *newfather_box;
  296.  
  297.   if (Option.debug) printf("\tAdding as sibling\n");
  298.   
  299.   /* Make duplicate of current node (for pointer updating) */
  300.   BVtree_sib = BVH_DuplicateBox(BVtree);
  301.   BVtree_sib->level++;                      /* Push down 1 level ! */
  302.   old_father = BVtree->father;
  303.  
  304.   /* Create new node for object box to insert  (one level down) */
  305.   newhbox = HBBox_Create(box, pptr, optr, 
  306.              (HBBox *)NULL, BVtree->level+1);
  307.   
  308.   /* New node needs a new parent = union(new BV node, current node) */
  309.   newfather_box = (BoundingBoxType *) malloc(sizeof(BoundingBoxType));
  310.   Bounds_Union(*box, *BVtree->box, newfather_box);
  311.   new_father = HBBox_Create(newfather_box, (Polygon *)NULL, 
  312.                 (Objectt *)NULL, old_father, BVtree->level);
  313.   new_father->num_children = 2;
  314.   new_father->child[0] = BVtree_sib;
  315.   new_father->child[1] = newhbox;
  316.  
  317.   /* Link old nodes father to old nodes new father */
  318.   if (old_father == NULL) {  
  319.     root_BVH = *new_father;
  320.     /* root_BVH->box = newfather_box; */
  321.     BVtree_sib->father = &root_BVH;
  322.     newhbox->father = &root_BVH;
  323.   } else if (old_father != NULL) {
  324.     old_father->child[child_index] = new_father;
  325.     BVtree_sib->father = new_father;
  326.     newhbox->father = new_father;
  327.   }
  328.  
  329.   /* Traverse up the tree and increase size of ancestor boxes
  330.      starting with old-father of current box */
  331.   if (old_father != NULL)
  332.     Enlarge_Ancestors(old_father, box);
  333. }
  334.  
  335. /**********************************************************************/
  336. /* Add box as child of BV tree node with children */
  337. /**********************************************************************/
  338. void BVH_AddBox_Child(BVtree, pptr, optr, box)
  339.      HBBox *BVtree;
  340.      BoundingBoxType *box;
  341.      Polygon *pptr;
  342.      Objectt *optr;
  343. {
  344.   HBBox *newhbox;
  345.   BoundingBoxType *newcurrent_box;
  346.   
  347.   if (Option.debug) printf("\tAdding as child\n");
  348.  
  349.   /* Create new box for current node 
  350.      = union(old+box to insert), discard old */
  351.   newcurrent_box = (BoundingBoxType *) malloc(sizeof(BoundingBoxType));
  352.   Bounds_Union(*box, *BVtree->box, newcurrent_box);  
  353.   free(BVtree->box);
  354.   BVtree->box = newcurrent_box;
  355.  
  356.   /* Create new node for box to insert, and link father to it */
  357.   newhbox = HBBox_Create(box, pptr, optr, BVtree, BVtree->level+1);
  358.   BVtree->child[BVtree->num_children] = newhbox;
  359.   BVtree->num_children++;
  360.  
  361.   /* Traverse up the tree and increase size of ancestor boxes
  362.      starting with father of current box */
  363.   if (BVtree != NULL)
  364.     Enlarge_Ancestors(BVtree, box);
  365. }
  366.  
  367. HBBox *addition_pos;             /* Current node position to add to   */
  368. /**********************************************************************/
  369. /* Place box in the current BV tree */
  370. /**********************************************************************/
  371. void BVH_AddBox_To_Hier(BVtree, pptr, optr, box, level, child_index, 
  372.             min_child_index, global_min_incr)
  373.      HBBox *BVtree;              /* Current node to check             */
  374.      Polygon *pptr;              /* Polygon's BV to add               */
  375.      Objectt *optr;              /* Object's BV to add                */
  376.      BoundingBoxType *box;       /* Box to add                        */
  377.      int *child_index;           /* Index of father to current node   */
  378.      int *min_child_index;       /* Link to node to insert box under  */
  379.      double *global_min_incr;    /* Current minimum increase cost     */
  380. {
  381.   double child_min_incr;         /* Local increase */
  382.   int min_path;                  /* Local path to follow */
  383.  
  384.   if (IsLeafBox(BVtree)) {    /* Is a leaf check for addition to leaf */
  385.     child_min_incr = BVH_IncrementalCost_Box(BVtree, box);
  386.     if (child_min_incr <= *global_min_incr) {
  387.       *min_child_index = *child_index;
  388.       *global_min_incr = child_min_incr;
  389.       addition_pos = BVtree;
  390.       if (Option.debug) {
  391.     printf("\t+ Adding under box:\n");
  392.     BoundsPrint(*BVtree->box, stdout, "");    
  393.       }
  394.     }
  395.   } else {
  396.     /* Continue to traverse down tree and find place to put the box */
  397.     /* Find path whose incr. area will be minimized if you add this
  398.        object's box to it. */
  399.     min_path = BVH_MinCost_Child(BVtree, box, &child_min_incr);
  400.  
  401.     /* Update minimum incremental cost, and position to add
  402.        if necessary */    
  403.     if (child_min_incr <= *global_min_incr) {
  404.       *min_child_index = min_path;
  405.       *global_min_incr = child_min_incr;
  406.       addition_pos = BVtree->child[min_path];
  407.       if (Option.debug) {
  408.     printf("\t+ Adding under box:\n");
  409.     BoundsPrint(*BVtree->child[min_path]->box, stdout, "");    
  410.       }
  411.     }
  412.     
  413.     if (Option.debug) {
  414.       printf("\n\tAt level %d\n", level);
  415.       printf("\tFollowing min path %d, global incr. cost = %g\n",
  416.          min_path, *global_min_incr);
  417.     }
  418.     
  419.     /* Follow the path that provides the minimum incremental cost */
  420.     level++;
  421.     *child_index = min_path;
  422.     BVH_AddBox_To_Hier(BVtree->child[min_path], pptr, optr, box, 
  423.                level, child_index, min_child_index, 
  424.                global_min_incr);
  425.   }
  426. }
  427.  
  428. /**********************************************************************/
  429. /* Create bounding volume hierarchy from the bounding volumes in the  */
  430. /* scene                                                              */
  431. /**********************************************************************/
  432. void BVH_Create_Hierarchy(theScene, scene_BVH)
  433.      Scene *theScene;
  434.      HBBox *scene_BVH;
  435. {
  436.   int i;
  437.   int child_index;
  438.   int min_child_index;
  439.   int level = 0;
  440.   Scene *sptr;
  441.   Objectt *optr;
  442.   double min_insert_cost;
  443.   int temp; 
  444.  
  445.   printf("\n\t*** Building Hierarchical BV's from scene ***\n");
  446.   temp = Option.debug; Option.debug = 0;
  447.   
  448.   sptr = theScene;
  449.   optr=sptr->objects;
  450.  
  451.   /* First object is the root */
  452.   root_BVH = *HBBox_Create(optr->box, (Polygon *)NULL, optr, 
  453.                (HBBox *)NULL, level);
  454.   optr++;
  455.  
  456.   /* Scan rest of objects in the scene and add to global BV tree */
  457.   for(i=1;i<sptr->num_objects;i++, optr++) {
  458.     min_insert_cost = DAMN_LARGE;  /* Initialize minimum position, cost */
  459.     addition_pos = NULL;
  460.     min_child_index = -1;
  461.  
  462.     /* Check the rest of the tree for a smaller minimum cost */
  463.     BVH_AddBox_To_Hier(&root_BVH, (Polygon *)0, optr, 
  464.                optr->box, level, &child_index, 
  465.                &min_child_index, &min_insert_cost);
  466.     
  467.     /* Insert new node into correct position, enlarge ancestor's boxes */
  468.     if (!IsLeafBox(addition_pos) && !IsFullBox(addition_pos))
  469.       BVH_AddBox_Child(addition_pos, (Polygon *)0, optr, optr->box);
  470.     else 
  471.       BVH_AddBox_Sibling(addition_pos, optr->box, (Polygon *)0, optr, 
  472.              min_child_index);
  473.     
  474.     if (Option.debug) printf("\tCost to insert %s%d's box = %g\n", 
  475.                  optr->name, optr->id, min_insert_cost);
  476.   }
  477.   *scene_BVH = root_BVH;
  478.   Option.debug = temp;
  479. }
  480.  
  481. int p_count = 0;
  482. /**********************************************************************/
  483. /* Create polygon hierarchical bounding volumes */
  484. /**********************************************************************/
  485. void BVH_Create_PHierarchy(hbox)
  486.      HBBox *hbox;
  487. {
  488.   int i,j;
  489.   int child_index;
  490.   int min_child_index;
  491.   int level;
  492.   double min_insert_cost;
  493.   Mesh *mptr;
  494.   Polygon *pptr;
  495.   Objectt *optr;
  496.   BoundingBoxType *pbox;
  497.  
  498.   /* Add polygons of objects under node for object */
  499.   if (hbox->object != 0 && hbox->poly == 0) {
  500.     optr = hbox->object;
  501.     if (optr->primid == MESH) {  /* Only add polys for meshes ! */
  502.       for(i=0,mptr=optr->meshes;i<optr->num_meshes;i++, mptr++) {
  503.     
  504.     /* Add first polygon */
  505.     /* first_BVH = HBBox_Create(pptr->box, pptr, optr, 
  506.                  hbox, level); */
  507.   
  508.     pptr = mptr->polys;
  509.     pbox = (BoundingBoxType *) malloc(sizeof(BoundingBoxType));
  510.     *pbox = BoxPoly(pptr);
  511.     p_count++;
  512.  
  513.     BVH_AddBox_Child(hbox, pptr, optr, pbox);
  514.     pptr = pptr->next;
  515.     
  516.     /* BVH_PrintBox(&Scene_BVH);
  517.        BVH_PrintHier(&Scene_BVH); */
  518.  
  519.     for(j=1;j<mptr->num_polys;j++, pptr=pptr->next) {
  520.       level = hbox->level;
  521.       min_insert_cost = DAMN_LARGE;
  522.       addition_pos = NULL;
  523.       min_child_index = -1;
  524.       child_index = 0;
  525.  
  526.       /* Create bounding box for the current polygon and add it to 
  527.          tree under the object node at the min-cost position */
  528.       pbox = (BoundingBoxType *) malloc(sizeof(BoundingBoxType));
  529.       *pbox = BoxPoly(pptr);
  530.       BVH_AddBox_To_Hier(hbox, pptr, optr, pbox, 
  531.                  level, &child_index, 
  532.                  &min_child_index, &min_insert_cost);
  533.       
  534.       /* Insert new node, enlarge ancestor's boxes */
  535.       if (!IsLeafBox(addition_pos)) {
  536.         if (!IsFullBox(addition_pos)) {
  537.           p_count++;
  538.           BVH_AddBox_Child(addition_pos, pptr, optr, pbox);
  539.         }
  540.       } else {
  541.         p_count++;
  542.         BVH_AddBox_Sibling(addition_pos, pbox, pptr, optr, 
  543.                    min_child_index);
  544.       }
  545.       if (Option.debug) printf("\tCost to insert %s%d's box = %g\n", 
  546.                    pptr->name, pptr->id, min_insert_cost);
  547.     }
  548.       }
  549.     }
  550.   }
  551.   else {
  552.     /* Check all children bounding volumes */
  553.     for(i=0; i<hbox->num_children; i++)
  554.       BVH_Create_PHierarchy(hbox->child[i]);
  555.   }
  556. }
  557.  
  558. /**********************************************************************/
  559. /* Print object list of potential receivers */
  560. /**********************************************************************/
  561. void Print_ObjectList()
  562. {
  563.   int i;
  564.   Object_List *olptr;
  565.   
  566.   printf("\t> Object Receiver List {\n");
  567.   olptr = objlist;
  568.   for(i=0;i<objlist_size;i++) {
  569.     printf("\t%s%d is%s a possible receiver. And is%s a possible obstructor\n",
  570.        olptr->hbox->object->name, olptr->hbox->object->id, 
  571.        (olptr->is_receiver ? " " : " not"),
  572.        (olptr->is_obstructor ? " " : " not"));
  573.     olptr = olptr->next;
  574.   }
  575.   printf("\t}\n");
  576. }
  577.  
  578. /**********************************************************************/
  579. /* Print candidate list for current shaft */
  580. /**********************************************************************/
  581. void Print_CandidateList()
  582. {
  583.   int i;
  584.   Object_List *olptr;
  585.   char *tmp = "                                                  ";
  586.   
  587.   printf("\t> Shaft  Candidate List {\n");
  588.   olptr = objlist;
  589.   for(i=0;i<objlist_size;i++) {
  590.     if (olptr->hbox->object != 0) 
  591.       sprintf(tmp,"%s%d", olptr->hbox->object->name, olptr->hbox->object->id);
  592.     else 
  593.       tmp = "No object";
  594.     BoundsPrint(*olptr->hbox->box, stdout, tmp);
  595.     
  596.     printf("\tAt level %d. ",olptr->hbox->level);
  597.     switch (olptr->is_receiver) {
  598.     case OUTSIDE: 
  599.       fprintf(stderr,"PR_Clist: Is outside. Oh oh\n"); exit(1); break;
  600.     case OVERLAP: printf("Overlaps.\n"); break;
  601.     case INSIDE: printf("Is inside.\n"); break;
  602.     case CONTAINS: printf("Contains\n"); break;
  603.     default: fprintf(stderr, "PR_Clist: Invalid candidate box condition\n");
  604.       exit(1);
  605.     }
  606.     olptr = olptr->next;
  607.   }
  608.   printf("\t}\n");
  609. }
  610.  
  611. /**********************************************************************/
  612. /* Initialize object list of potential receivers to be empty */
  613. /**********************************************************************/
  614. void Init_ObjectList()
  615. {
  616.   int i;
  617.   Object_List *olptr, *tmp;
  618.  
  619.   if (Option.debug)
  620.     printf("\t> Initializing object receiver list\n");
  621.   olptr = objlist;
  622.   for (i=0;i<objlist_size;i++) {
  623.     tmp = olptr->next;
  624.     free(olptr);
  625.     olptr = tmp;
  626.   }
  627.   objlist = objlist_tail = 0;
  628.   objlist_size = 0;
  629.   objlist_receivers = 0;
  630. }
  631.   
  632. /**********************************************************************/
  633. /* Add object containing potential receivers to object list */
  634. /**********************************************************************/
  635. void AddTo_ObjectList(hbox,obj_seen)
  636.      HBBox *hbox;
  637.      int obj_seen;
  638. {
  639.   Object_List *olptr;
  640.  
  641.   /* Create object list node, set whether object seen or not */
  642.   olptr = (Object_List *) malloc(sizeof(Object_List));
  643.   olptr->hbox = hbox;
  644.   olptr->next = (Object_List *)NULL;
  645.   olptr->is_receiver = obj_seen;  /* Mark if object is a receiver */
  646.   olptr->is_obstructor = 0; /* Assume does not obstruct any receiver */
  647.   
  648.   if (objlist_size == 0) {      /* First possible receiver */
  649.     objlist = olptr;
  650.     objlist_tail = olptr;
  651.   } else {
  652.     objlist_tail->next = olptr;   /* Add to end of list */
  653.     objlist_tail = olptr;
  654.   }
  655.   objlist_size++;                /* Count total # of elements */
  656.   if (obj_seen)
  657.     objlist_receivers++;         /* Count # of receivers */
  658. }
  659.  
  660. #define At_Object_Level(hbox) ((hbox)->object != 0 && (hbox)->poly == 0)
  661. /**********************************************************************/
  662. /* Bounding volume hierarchy visibility test */
  663. /* return list of potentially visible objects */
  664. /**********************************************************************/
  665. void Make_ObjectList(shootPatch, hbox, obj_seen)
  666.      Polygon *shootPatch;
  667.      HBBox *hbox;
  668.      int obj_seen;
  669. {
  670.   int i;
  671.  
  672.   if (hbox->object != 0 && hbox->poly == 0) {
  673.     /* Object cannot be a receiver and contain shooter, 
  674.        if object is convex and patches don't face in */
  675.     if (obj_seen)
  676.       if (hbox->object->primid != MESH)
  677.     if (poly_object(shootPatch) == hbox->object) 
  678.       obj_seen = hbox->object->in_facingprim;
  679.     
  680.     /* Check if bounding volume of object can be seen or not 
  681.        but only if parent bounding volume can be seen */
  682.     if (obj_seen)
  683.       obj_seen = 1 - Bounds_Behind_Plane(hbox->box, shootPatch->normal[0],
  684.                      shootPatch->d);    
  685.     AddTo_ObjectList(hbox,obj_seen);
  686.   } 
  687.   
  688.   /* Check if this BV can be seen as pass a visibility flag 
  689.      down the hierarchy */
  690.   else { 
  691.     obj_seen = 1 - Bounds_Behind_Plane(hbox->box, shootPatch->normal[0],
  692.                        shootPatch->d);
  693.   }
  694.  
  695.   /* Check all children bounding volumes */
  696.   for(i=0; i<hbox->num_children; i++) {
  697.     Make_ObjectList(shootPatch, hbox->child[i], obj_seen);
  698.   }
  699. }
  700.  
  701.  
  702. /**********************************************************************/
  703. /* Find out objects in front of receiver from list of objects in front*/
  704. /* of the source */
  705. /**********************************************************************/
  706. void Cull_ObjectList(rec)
  707.      Polygon *rec;
  708. {
  709.   int i;
  710.   Object_List *olptr;
  711.   
  712.   for(i=0, olptr=objlist; i<objlist_size; i++, olptr=olptr->next) {
  713.     olptr->is_obstructor = 0;
  714.     if (olptr->is_receiver) {
  715.       /* if ((hbox->object != poly_object(shootPatch)) &&
  716.      (hbox->object != poly_object(rec))) */
  717.       if (Bounds_Behind_Plane(olptr->hbox->box, rec->normal[0], 
  718.                   rec->d) == 0) {
  719.     olptr->is_obstructor = 1;
  720.       }
  721.     }
  722.   }
  723. }
  724.