home *** CD-ROM | disk | FTP | other *** search
/ gondwana.ecr.mu.oz.au/pub/ / Graphics.tar / Graphics / atomart.tar.gz / atomart.tar / split.c < prev    next >
C/C++ Source or Header  |  1990-06-14  |  4KB  |  171 lines
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include "atomart.h"
  4. #include "macro.h"
  5.  
  6. extern object    *oblist;
  7. extern light    *lights;
  8. extern hlist    *fhlist;
  9. extern int    maxhitlevel;
  10.  
  11. extern pixel    backcol;
  12. extern colour    ambient;
  13.  
  14. extern double    power();
  15.  
  16. extern float    tolerance;
  17.  
  18. /*
  19.  * splitleaf
  20.  *
  21.  *    split a leaf along the middle of an axis.
  22.  */
  23. splitleaf(axis, leaf, val)
  24.     int    axis;
  25.     stree    *leaf;
  26.     float    val;
  27. {
  28.     olist    *objs, *nxtobj, *tmpobj;
  29.     stree    *left, *right;
  30.     int    leftcount, rightcount, totcount;
  31.     float    min, max;
  32.     sphere    *s;
  33.  
  34.     if (leaf->type != SPLITABLELEAF)
  35.         return;
  36.  
  37.     left = (stree *)smalloc(sizeof(stree));
  38.     right = (stree *)smalloc(sizeof(stree));
  39.  
  40.     leftcount = rightcount = totcount = 0;
  41.  
  42.     left->u.leaf.oblist = right->u.leaf.oblist = (olist *)NULL;
  43.  
  44.     for (objs = leaf->u.leaf.oblist; objs != (olist *)NULL; objs = nxtobj) {
  45.         nxtobj = objs->nxt;
  46.         totcount++;
  47.         s = objs->obj->u.sph;
  48.         switch (axis) {
  49.         case X:
  50.             min = s->cent.x - s->rad;
  51.             max = s->cent.x + s->rad;
  52.             break;
  53.         case Y:
  54.             min = s->cent.y - s->rad;
  55.             max = s->cent.y + s->rad;
  56.             break;
  57.         case Z:
  58.             min = s->cent.z - s->rad;
  59.             max = s->cent.z + s->rad;
  60.             break;
  61.         default:
  62.             fatal("atomart: bad axis in splitleaf.\n");
  63.         }
  64.  
  65.         if (max < val) {            /* to the left */
  66.             leftcount++;
  67.             objs->nxt = left->u.leaf.oblist;
  68.             left->u.leaf.oblist = objs;
  69.         } else if (min > val) {            /* to the right */
  70.             rightcount++;
  71.             objs->nxt = right->u.leaf.oblist;
  72.             right->u.leaf.oblist = objs;
  73.         } else {                /* in both (sigh) */
  74.             tmpobj = (olist *)smalloc(sizeof(olist));
  75.             tmpobj->obj = objs->obj;
  76.             leftcount++;
  77.             tmpobj->nxt = left->u.leaf.oblist;
  78.             left->u.leaf.oblist = tmpobj;
  79.             rightcount++;
  80.             objs->nxt = right->u.leaf.oblist;
  81.             right->u.leaf.oblist = objs;
  82.         }
  83.     }
  84.  
  85.     left->u.leaf.depth = right->u.leaf.depth = leaf->u.leaf.depth + 1;
  86.     left->type = (leftcount < MAXOBJS || leaf->u.leaf.depth == 13) ? LEAF : SPLITABLELEAF;
  87.     right->type = (rightcount < MAXOBJS || leaf->u.leaf.depth == 13) ? LEAF : SPLITABLELEAF;
  88.  
  89.     left->bb = right->bb = leaf->bb;
  90.     left->bb.max[axis] = val;
  91.     right->bb.min[axis] = val;
  92.  
  93.     leaf->type = axis;
  94.     leaf->splitval = val;
  95.     leaf->u.branch.left = left;
  96.     leaf->u.branch.right = right;
  97. }
  98.  
  99. /*
  100.  * split
  101.  *
  102.  *    split a splittable leaf into two nodes.
  103.  */
  104. void
  105. split(root)
  106.     stree    *root;
  107. {
  108.     int    i, total, left[3], right[3];
  109.     float    vals[3], min, max;
  110.     olist    *ol;
  111.     sphere    *s;
  112.  
  113.     total = 0;
  114.  
  115.     vals[X] = (root->bb.max[X] + root->bb.min[X]) / 2;
  116.     vals[Y] = (root->bb.max[Y] + root->bb.min[Y]) / 2;
  117.     vals[Z] = (root->bb.max[Z] + root->bb.min[Z]) / 2;
  118.  
  119.     left[X] = right[X] = 0;
  120.     left[Y] = right[Y] = 0;
  121.     left[Z] = right[Z] = 0;
  122.  
  123.     for (ol = root->u.leaf.oblist; ol != (olist *)NULL; ol = ol->nxt) {
  124.         s = ol->obj->u.sph;
  125.  
  126.         min = s->cent.x - s->rad;    /* check for x */
  127.         max = s->cent.x + s->rad;
  128.         if (max < vals[X])        /* to the left */
  129.             left[X]++;
  130.         else if (min > vals[X])    /* to the right */
  131.             right[X]++;
  132.         else {            /* in both (sigh) */
  133.             left[X]++;
  134.             right[X]++;
  135.         }
  136.  
  137.         min = s->cent.y - s->rad;    /* check for y */
  138.         max = s->cent.y + s->rad;
  139.         if (max < vals[Y])        /* to the left */
  140.             left[Y]++;
  141.         else if (min > vals[Y])    /* to the right */
  142.             right[Y]++;
  143.         else {            /* in both (sigh) */
  144.             left[Y]++;
  145.             right[Y]++;
  146.         }
  147.  
  148.         min = s->cent.z - s->rad;    /* check for z */
  149.         max = s->cent.z + s->rad;
  150.         if (max < vals[Z])        /* to the left */
  151.             left[Z]++;
  152.         else if (min > vals[Z])    /* to the right */
  153.             right[Z]++;
  154.         else {            /* in both (sigh) */
  155.             left[Z]++;
  156.             right[Z]++;
  157.         }
  158.     }
  159.  
  160.     if ((left[X] + right[X]) < (left[Y] + right[Y]))
  161.         if ((left[X] + right[X]) < (left[Z] + right[Z]))
  162.             splitleaf(X, root, vals[X]);
  163.         else
  164.             splitleaf(Z, root, vals[Z]);
  165.     else
  166.         if ((left[Y] + right[Y]) < (left[Z] + right[Z]))
  167.             splitleaf(Y, root, vals[Y]);
  168.         else
  169.             splitleaf(Z, root, vals[Z]);
  170. }
  171.