home *** CD-ROM | disk | FTP | other *** search
/ Quake 'em / QUAKEEM.BIN / quake / programs / qube / area.c next >
Encoding:
C/C++ Source or Header  |  1996-03-07  |  9.6 KB  |  398 lines
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include "area.h"
  5.  
  6. #define MAX(a,b) (((a) > (b)) ? (a) : (b))
  7. #define MIN(a,b) (((a) < (b)) ? (a) : (b))
  8.  
  9. static void *AreaMalloc(long int size);
  10. static void *AreaRealloc(void *buffer, long int size);
  11. static void AreaFree(void *buffer);
  12.  
  13. static Area *AreaFixup(Area *a, Area *b, int (*overlapfunc)(Area *a, Rect *ra, Rect *rb));
  14. static void AreaFixBounds(Area *a);
  15.  
  16. static int GetNextLeft(Rect **ra, Rect **rb, int y, int *x1, int *x2);
  17. static int _Union(Area *a, Rect *ra, Rect *rb);
  18. static int _Intersect(Area *a, Rect *ra, Rect *rb);
  19. static int _Subtract(Area *a, Rect *ra, Rect *rb);
  20.  
  21. Area *AreaCreate(void)
  22. {
  23.     Area *temp = AreaMalloc(sizeof(Area));
  24.  
  25.     temp->count = 0;
  26.     temp->rectspace = 1;
  27.     temp->rects = AreaMalloc(sizeof(Rect) * temp->rectspace);
  28.     temp->bound.x1 = 0;
  29.     temp->bound.y1 = 0;
  30.     temp->bound.x2 = 0;
  31.     temp->bound.y2 = 0;
  32.  
  33.     return(temp);
  34. }
  35.  
  36. void AreaDestroy(Area *a)
  37. {
  38.     free(a->rects);
  39.     free(a);
  40. }
  41.  
  42. Area *AreaUnionRect(Area *a, int x1, int y1, int x2, int y2)
  43. {
  44.     Area *temp = AreaCreate();
  45.     Area *temp2;
  46.  
  47.     temp->count = 1;
  48.     temp->rects[0].x1 = x1;
  49.     temp->rects[0].y1 = y1;
  50.     temp->rects[0].x2 = x2;
  51.     temp->rects[0].y2 = y2;
  52.  
  53.     temp2 = AreaUnionArea(a, temp);
  54.     AreaDestroy(temp);
  55.     return(temp2);
  56. }
  57.  
  58. Area *AreaIntersectRect(Area *a, int x1, int y1, int x2, int y2)
  59. {
  60.     Area *temp = AreaCreate();
  61.     Area *temp2;
  62.  
  63.     temp->count = 1;
  64.     temp->rects[0].x1 = x1;
  65.     temp->rects[0].y1 = y1;
  66.     temp->rects[0].x2 = x2;
  67.     temp->rects[0].y2 = y2;
  68.  
  69.     temp2 = AreaIntersectArea(a, temp);
  70.     AreaDestroy(temp);
  71.     return(temp2);
  72. }
  73.  
  74. Area *AreaSubRect(Area *a, int x1, int y1, int x2, int y2)
  75. {
  76.     Area *temp = AreaCreate();
  77.     Area *temp2;
  78.  
  79.     temp->count = 1;
  80.     temp->rects[0].x1 = x1;
  81.     temp->rects[0].y1 = y1;
  82.     temp->rects[0].x2 = x2;
  83.     temp->rects[0].y2 = y2;
  84.  
  85.     temp2 = AreaSubArea(a, temp);
  86.     AreaDestroy(temp);
  87.     return(temp2);
  88. }
  89.  
  90. Area *AreaUnionArea(Area *a, Area *b)
  91. {
  92.     Area *n = AreaFixup(a, b, _Union);
  93.  
  94.     n->bound.x1 = MIN(a->bound.x1, b->bound.x1);
  95.     n->bound.y1 = MIN(a->bound.y1, b->bound.y1);
  96.     n->bound.x2 = MAX(a->bound.x2, b->bound.x2);
  97.     n->bound.y2 = MAX(a->bound.y2, b->bound.y2);
  98.  
  99.     return(n);
  100. }
  101.  
  102. Area *AreaIntersectArea(Area *a, Area *b)
  103. {
  104.     Area *n = AreaFixup(a, b, _Intersect);
  105.     AreaFixBounds(n);
  106.     return(n);
  107. }
  108.  
  109. Area *AreaSubArea(Area *a, Area *b)
  110. {
  111.     Area *n = AreaFixup(a, b, _Subtract);
  112.     AreaFixBounds(n);
  113.     return(n);
  114. }
  115.  
  116. static void AreaFixBounds(Area *a)
  117. {
  118.     Rect *box, *boxend, *bound;
  119.  
  120.     if (a->count == 0) {
  121.         a->bound.x1 = 0;
  122.         a->bound.y1 = 0;
  123.         a->bound.x2 = 0;
  124.         a->bound.y2 = 0;
  125.         return;
  126.     }
  127.  
  128.     bound = &a->bound;
  129.     boxend = &box[a->count - 1];
  130.  
  131.     bound->x1 = box->x1;
  132.     bound->y1 = box->y1;
  133.     bound->x2 = boxend->x2;
  134.     bound->y2 = boxend->y2;
  135.  
  136.     for (box = a->rects; box <= boxend; box++) {
  137.                 if (box->x1 < bound->x1) bound->x1 = box->x1;
  138.         if (box->x2 > bound->x2) bound->x2 = box->x2;
  139.     }
  140. }
  141.  
  142. static void *AreaMalloc(long int size)
  143. {
  144.     void *temp = malloc(size);
  145.  
  146.     if (temp == NULL) {
  147.         fprintf(stderr, "Unable to allocate enough memory.  %ld bytes not available.\n", size);
  148.                 exit(0);
  149.         }
  150.  
  151.     return(temp);
  152. }
  153.  
  154. static void *AreaRealloc(void *buffer, long int size)
  155. {
  156.     void *temp = realloc(buffer, size);
  157.  
  158.     if (temp == NULL) {
  159.         fprintf(stderr, "Unable to allocate enough memory.  %ld bytes not available.\n", size);
  160.         exit(0);
  161.         }
  162.  
  163.         return(temp);
  164. }
  165.  
  166. Area *AreaCopy(Area *src)
  167. {
  168.     Area *dest;
  169.  
  170.     dest = AreaCreate();
  171.     dest->rects = realloc(dest->rects, sizeof(Rect) * src->count);
  172.     dest->rectspace = src->count;
  173.  
  174.         dest->count = src->count;
  175.     dest->bound.x1 = src->bound.x1;
  176.     dest->bound.y1 = src->bound.y1;
  177.     dest->bound.x2 = src->bound.x2;
  178.     dest->bound.y2 = src->bound.y2;
  179.  
  180.     memcpy((char *)dest->rects, (char *)src->rects, src->count * sizeof(Rect));
  181.  
  182.     return(dest);
  183. }
  184.  
  185. static Area *AreaFixup(Area *a, Area *b, int (*overlapfunc)(Area *a, Rect *ra, Rect *rb))
  186. {
  187.     int i, j, k;
  188.     Area *temp2, *temp, *newarea;
  189.  
  190.     /* First step is to duplicate all the incoming rectangles, since
  191.        we're not allowed to modify the input */
  192.  
  193.     temp2 = AreaCopy(a);
  194.     temp = AreaCopy(b);
  195.  
  196.     /* Second step is to split all the rectangles on each others' y1
  197.        and y2 bounds.  i iterates through the first area.  j iterates
  198.        through the second, though its motion is dependent on that of i. */
  199.  
  200.     for (i = 0, j = 0; i < temp2->count; i++) {
  201.         if (temp2->rects[i].y1 > temp->rects[j].y1 && temp->rects[j].y1 <= temp2->rects[i].y2) {
  202.             /* i's band needs to be split at [j].y1 */
  203.             i = AreaSplitBand(temp2, i, temp->rects[j].y1) - 1;
  204.                 }
  205.         else if (temp2->rects[i].y1 > temp->rects[j].y2-1 && temp->rects[j].y2-1 <= temp2->rects[i].y2) {
  206.             /* i's band needs to be split at [j].y2-1 */
  207.             i = AreaSplitBand(temp2, i, temp->rects[j].y2-1) - 1;
  208.                 }
  209.         }
  210.  
  211.     /* Okay, we've split up one list nicely.  Now do the other. */
  212.  
  213.     for (i = 0, j = 0; i < temp->count; i++) {
  214.         if (temp->rects[i].y1 > temp2->rects[j].y1 && temp2->rects[j].y1 <= temp->rects[i].y2) {
  215.             /* i's band needs to be split at [j].y1 */
  216.             i = AreaSplitBand(temp, i, temp2->rects[j].y1) - 1;
  217.                 }
  218.         else if (temp->rects[i].y1 > temp2->rects[j].y2-1 && temp2->rects[j].y2-1 <= temp->rects[i].y2) {
  219.             /* i's band needs to be split at [j].y2-1 */
  220.             i = AreaSplitBand(temp, i, temp2->rects[j].y2-1) - 1;
  221.                 }
  222.         }
  223.  
  224.     /* Step three.    Perform a merge on the two arrays, letting the supplied
  225.        function handle overlap. */
  226.  
  227.     newarea = AreaCreate();
  228.  
  229.     for (i = 0; i < temp2->count + temp->count;) {
  230.         if (temp2->rects[i].y1 < temp->rects[j].y1)
  231.             /* Copy the i band */
  232.             i += (*overlapfunc)(newarea, &(temp2->rects[i]), NULL);
  233.  
  234.                 else if (temp2->rects[i].y1 > temp->rects[j].y1)
  235.             /* Copy the j band */
  236.             i += (*overlapfunc)(newarea, NULL, &(temp->rects[j]));
  237.  
  238.         else
  239.             /* Merge them however necessary */
  240.                         i += (*overlapfunc)(newarea, &(temp2->rects[i]), &(temp->rects[j]));
  241.         }
  242.  
  243.     AreaDestroy(temp);
  244.     AreaDestroy(temp2);
  245.  
  246.     return(newarea);
  247. }
  248.  
  249. /* The y below that gets passed in is the top edge of the new bottom band
  250.    and y-1 is the bottom edge of the new top band. */
  251.  
  252. int AreaSplitBand(Area *a, int bandstart, int y)
  253. {
  254.     Rect *temp = malloc(sizeof(Rect) * a->count * 2);    /* The *2 is guaranteed to encompass all possible growth */
  255.     int yorg = a->rects[bandstart].y1;
  256.     int bandtemp = bandstart;
  257.     int bandtemp2;
  258.  
  259.     /* Duplicate up to just before this band */
  260.  
  261.     for (bandtemp = 0; bandtemp < bandstart; bandtemp++) {
  262.         temp[bandtemp].x1 = a->rects[bandtemp].x1;
  263.         temp[bandtemp].y1 = a->rects[bandtemp].y1;
  264.         temp[bandtemp].x2 = a->rects[bandtemp].x2;
  265.         temp[bandtemp].y2 = a->rects[bandtemp].y2;
  266.     }
  267.  
  268.     /* Duplicate this band once, but make it shorter, and move it up */
  269.  
  270.     for (bandtemp = bandstart, yorg = a->rects[bandtemp].y1, bandtemp2 = 0;
  271.          a->rects[bandtemp].y1 == yorg;
  272.          bandtemp++, bandtemp2++) {
  273.         temp[bandtemp2].x1 = a->rects[bandtemp].x1;
  274.         temp[bandtemp2].y1 = a->rects[bandtemp].y1;
  275.         temp[bandtemp2].x2 = a->rects[bandtemp].x2;
  276.         temp[bandtemp2].y2 = y - 1;
  277.         }
  278.  
  279.     /* Duplicate this band again, but make it shorter, and move it down */
  280.  
  281.     for (bandtemp = bandstart, yorg = a->rects[bandtemp].y1, bandtemp2 = 0;
  282.          a->rects[bandtemp].y1 == yorg;
  283.          bandtemp++, bandtemp2++) {
  284.         temp[bandtemp2].x1 = a->rects[bandtemp].x1;
  285.         temp[bandtemp2].y1 = y;
  286.         temp[bandtemp2].x2 = a->rects[bandtemp].x2;
  287.         temp[bandtemp2].y2 = a->rects[bandtemp].y2;
  288.         }
  289.  
  290.     bandstart = bandtemp;
  291.  
  292.     /* Copy the leftover stuff */
  293.  
  294.     for (; bandtemp < a->count; bandtemp++, bandtemp2++) {
  295.         temp[bandtemp2].x1 = a->rects[bandtemp].x1;
  296.         temp[bandtemp2].y1 = a->rects[bandtemp].y1;
  297.         temp[bandtemp2].x2 = a->rects[bandtemp].x2;
  298.         temp[bandtemp2].y2 = a->rects[bandtemp].y2;
  299.         }
  300.  
  301.     free(a->rects);
  302.  
  303.     a->rectspace = a->count * 2;
  304.         a->rects = temp;
  305.     a->count = bandtemp2;
  306.  
  307.     return(bandstart);
  308. }
  309.  
  310. static int GetNextLeft(Rect **ra, Rect **rb, int y, int *x1, int *x2)
  311. {
  312.     if ((*ra) != NULL && (*ra)->y1 == y) {
  313.         *x1 = (*ra)->x1;
  314.         if ((*rb) != NULL && (*rb)->y1 == y && (*rb)->x1 < *x1) {
  315.             *x1 = (*rb)->x1;
  316.             *x2 = (*rb)->x2;
  317.             (*rb)++;
  318.                 }
  319.         else {
  320.             *x2 = (*ra)->x2;
  321.                         (*ra)++;
  322.         }
  323.                 return(1);
  324.         }
  325.     else if ((*rb) != NULL && (*rb)->y1 == y) {
  326.         (*x1) = (*rb)->x1;
  327.         (*x2) = (*rb)->x2;
  328.         (*rb)++;
  329.         return(1);
  330.         }
  331.     else return(0);
  332. }
  333.  
  334. static int _Union(Area *a, Rect *ra, Rect *rb)
  335. {
  336.         int ox1, ox2;
  337.         int x1, x2;
  338.     int gotleft;
  339.     int y1, y2;
  340.     int count;
  341.  
  342.     if (ra != NULL && rb != NULL) {
  343.         if (ra->y1 <= rb->y1) {
  344.             y1 = ra->y1;
  345.             y2 = ra->y2;
  346.         }
  347.         else {
  348.             y1 = rb->y1;
  349.             y2 = rb->y2;
  350.         }
  351.     }
  352.     else if (ra != NULL) {
  353.         y1 = ra->y1;
  354.         y2 = ra->y2;
  355.         }
  356.     else if (rb != NULL) {
  357.         y1 = rb->y1;
  358.         y2 = rb->y2;
  359.         }
  360.     else return(0);
  361.  
  362.     while (1) {
  363.         if (!GetNextLeft(&ra, &rb, y1, &ox1, &ox2)) break;
  364.         count++;
  365.  
  366.         do {
  367.             if (!(gotleft = GetNextLeft(&ra, &rb, y1, &x1, &x2))) break;
  368.             count++;
  369.                         if (x1 <= ox2+1 && x2 > ox2) ox2 = x2;
  370.         } while (x1 <= ox2+1);
  371.  
  372.         if (!gotleft) break;
  373.  
  374.         if (a->count >= rectspace)
  375.             a->rects = realloc((void *)a->rects, a->count * 2);
  376.  
  377.                 a->rects[a->count].y1 = y1;
  378.         a->rects[a->count].y2 = y2;
  379.         a->rects[a->count].x1 = ox1;
  380.         a->rects[a->count].x2 = ox2;
  381.  
  382.         (a->count)++;
  383.         }
  384.  
  385.     return(count);
  386. }
  387.  
  388. static int _Intersect(Area *a, Rect *ra, Rect *rb)
  389. {
  390.  
  391. }
  392.  
  393. static int _Subtract(Area *a, Rect *ra, Rect *rb)
  394. {
  395.  
  396. }
  397.  
  398.