home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / formats / off / code / packobj.c < prev    next >
C/C++ Source or Header  |  1994-06-20  |  9KB  |  405 lines
  1.  
  2. /*
  3.  *
  4.  * Description
  5.  *    Pack an OFF object in memory
  6.  *    ``Packing'' means to rearrange the data structure so common vertices
  7.  *    are shared.  Since in typical objects every vertex
  8.  *    is shared by three or more polygons, this can often result in a
  9.  *    substantial reduction in storage and increase in rendering
  10.  *    efficiency (because shared vertices need only be transformed once).
  11.  *
  12.  * Input
  13.  *    Obj        Pointer to object structure in which data is stored.
  14.  * Output
  15.  *    obj        Same as input pointer, but underlying object structure
  16.  *            is modified.
  17.  *
  18.  * Diagnostics
  19.  *    None.  (If unsuccessful, the object is returned unchanged.)
  20.  *
  21.  * Author
  22.  *    Allen Akin
  23.  *    Digital Equipment Corp.
  24.  *    Workstation Systems Engineering
  25.  *    Palo Alto, CA
  26.  *
  27.  * History
  28.  *    20-Feb-87    Created
  29.  *    11-Oct-89    Ability to pack normals was removed when conventions
  30.  *            for dealing with normals were changed.
  31.  *
  32.  * Notes
  33.  *    In order to do this properly, one should really treat all of the
  34.  *     attributes at a vertex simultaneously - a vertex is redundant only
  35.  *    if all of the attributes at that vertex are redundant (vertex
  36.  *    coordinate, color, vertex normal, etc.).  This routine will just
  37.  *    pack the geometry property.  It is currently up to the application to
  38.  *    regenerate per-vertex colors or normals.
  39.  */
  40.  
  41. #include <stdio.h>
  42. #include "off.h"
  43.  
  44.  
  45.  
  46. typedef struct {float x, y, z;} OFFxyz;
  47. static qsort();
  48. static turtlesort();
  49. static int precedes();
  50. static int follows();
  51. static int equals();
  52.  
  53.  
  54.  
  55. OFFPackObj(obj)
  56. OFFObjDesc *obj;
  57.     {
  58.     register OFFProperty *prop;
  59.  
  60.     for (prop = obj->FirstProp; prop; prop = prop->NextProp)
  61.         {
  62.         if (strcmp(prop->PropName, "geometry") == 0
  63.             && strcmp(prop->DataFormat, "fff") == 0)
  64.             OFFPackProperty(prop);
  65.         }
  66.     }
  67.  
  68.  
  69.  
  70. OFFPackProperty(prop)
  71. OFFProperty *prop;
  72.     {
  73.     register int newI;
  74.     register int *vlist;
  75.     register OFFxyz *newVertices;
  76.     register int *ip;
  77.     register int *indexMap;
  78.     register int oldI;
  79.     int nVertices;
  80.     int nCounts;
  81.     int nIndices;
  82.     OFFxyz *oldVertices;
  83.     short *oldCounts;
  84.     short *oldIndices;
  85.     char *newData;
  86.     OFFxyz *xyzp;
  87.     short *sp;
  88.     int vertex;
  89.     char *malloc();
  90.  
  91.  
  92.     ip = (int *) prop->PropData;
  93.     nVertices = *ip++;
  94.     nCounts = *ip++;
  95.     nIndices = *ip++;
  96.     oldVertices = (OFFxyz *) ip;
  97.     oldCounts = (short *) (oldVertices + nVertices);
  98.     oldIndices = oldCounts + nCounts;
  99.  
  100.  
  101.     newVertices = NULL;
  102.     vlist = indexMap = NULL;
  103.     if (!(newVertices = (OFFxyz *) malloc(nVertices * sizeof(OFFxyz)))
  104.      || !(vlist = (int *) malloc(nVertices * sizeof(int)))
  105.      || !(indexMap = (int *) malloc(nVertices * sizeof(int))) )
  106.         {
  107.         fprintf(stderr, "OFFPackProperty:  insufficient memory\n");
  108.         if (newVertices)
  109.             free((char *) newVertices);
  110.         if (vlist)
  111.             free((char *) vlist);
  112.         if (indexMap)
  113.             free((char *) indexMap);
  114.         return;
  115.         }
  116.  
  117.  
  118.     /* Set up indices of original vertices: */
  119.  
  120.     for (newI = 0; newI < nVertices; ++newI)
  121.         vlist[newI] = newI;
  122.  
  123.  
  124.     /* Sort original vertices by swapping indices in vlist: */
  125.  
  126.     qsort(oldVertices, vlist, vlist + (nVertices - 1));
  127.  
  128.  
  129.     /*
  130.      * The following code does two things:
  131.      *    (1) Copies vertices from oldVertices to newVertices,
  132.      *        throwing away duplicates.
  133.      *    (2) Builds a mapping from old vertex indices to new
  134.      *        vertex indices.
  135.      * Because vlist gives us ordered access to oldVertices, it's
  136.      * efficient to do these operations in parallel.
  137.      */
  138.  
  139.     newI = -1;
  140.     for (vertex = 0, oldI = vlist[vertex]; vertex < nVertices; )
  141.         {
  142.         /*
  143.          * At this point, we have a new unique vertex.  Store it
  144.          * in the next position in the newVertices array, and
  145.          * update the indexMap to show how the old vertex index
  146.          * maps into the new one.
  147.          */
  148.  
  149.         newVertices[++newI] = oldVertices[oldI];
  150.         indexMap[oldI] = newI;
  151.  
  152.  
  153.         /*
  154.          * Now scan through succeeding oldVertices (continuing in
  155.          * sorted order).  If the old vertex equals the current new
  156.          * vertex, discard it and make the old vertex index map to
  157.          * the new vertex index.  If the old vertex doesn't equal
  158.          * the current new vertex, go back to the outer loop and
  159.          * store the new vertex.
  160.          */
  161.  
  162.         for (++vertex; vertex < nVertices; ++vertex)
  163.             {
  164.             oldI = vlist[vertex];
  165.             if (!equals(oldVertices + oldI, newVertices + newI))
  166.                 break;
  167.             indexMap[oldI] = newI;
  168.             }
  169.         }
  170.  
  171.  
  172.     /*
  173.      * newI contains the index of the last-used element of newVertices.
  174.      * Use this information plus the old data sizes to compute the size
  175.      * of the new data block, and allocate it.
  176.      */
  177.     
  178.     ++newI;
  179.     if (!(newData = malloc(
  180.         3 * sizeof(int)
  181.         + newI * sizeof(OFFxyz)
  182.         + nCounts * sizeof(short)
  183.         + nIndices * sizeof(short)  )))
  184.         {
  185.         free((char *) newVertices);
  186.         free((char *) vlist);
  187.         free((char *) indexMap);
  188.         fprintf(stderr, "OFFPackProperty:  insufficient memory\n");
  189.         return;
  190.         }
  191.  
  192.  
  193.     /*
  194.      * Stuff the new values into the new data record, mapping old
  195.      * vertex indices into new ones as we go.
  196.      */
  197.  
  198.     ip = (int *) newData;
  199.     *ip++ = newI;
  200.     *ip++ = nCounts;
  201.     *ip++ = nIndices;
  202.     bcopy((char *) newVertices, (char *) ip, newI * sizeof(OFFxyz));
  203.     xyzp = (OFFxyz *) ip;
  204.     xyzp += newI;
  205.     sp = (short *) xyzp;
  206.     bcopy((char *) oldCounts, (char *) sp, nCounts * sizeof(int));
  207.     sp += nCounts;
  208.     while (--nIndices >= 0)
  209.         *sp++ = indexMap[*oldIndices++ - 1] + 1;
  210.  
  211.  
  212.     /*
  213.      * Throw away the old and auxiliary data structures, and store the
  214.      * new ones.
  215.      */
  216.  
  217.     free(prop->PropData);
  218.     prop->PropData = newData;
  219.     free((char *) newVertices);
  220.     free((char *) vlist);
  221.     free((char *) indexMap);
  222.     }
  223.  
  224.  
  225.  
  226. #define PRECEDES(a,b) precedes(&(a), &(b))
  227. #define FOLLOWS(a,b) follows(&(a), &(b))
  228. #define QTHRESH 10    /* threshold for linear sort versus quicksort */
  229.  
  230.  
  231. static turtlesort(v, first, last)
  232. OFFxyz *v;
  233. register int *first;
  234. register int *last;
  235.     {
  236.     int temp;
  237.     OFFxyz min_key;
  238.     OFFxyz cur_key;
  239.     register int *current;
  240.  
  241.     for (; first < last; ++first)
  242.         {
  243.         min_key = v[*first];
  244.         for (current = first + 1; current <= last; ++current)
  245.             {
  246.             cur_key = v[*current];
  247.             if (PRECEDES(cur_key, min_key))
  248.                 {
  249.                 min_key = cur_key;
  250.                 temp = *first;
  251.                 *first = *current;
  252.                 *current = temp;
  253.                 }
  254.             }
  255.         }
  256.     }
  257.  
  258.  
  259. static qsort(v, first, last)
  260. OFFxyz *v;
  261. register int *first;
  262. register int *last;
  263.     {
  264.     OFFxyz pivot_key;
  265.     int *pivot;
  266.     register int *high;
  267.     register int *low;
  268.     int temp;
  269.  
  270. reenter:
  271.     if (first + QTHRESH >= last)
  272.         {
  273.         turtlesort(v, first, last);
  274.         return;
  275.         }
  276.     
  277.  
  278.     /* Find median of first, middle, and last keys: */
  279.  
  280.     {
  281.     int *mid;
  282.     OFFxyz f, m, l;
  283.  
  284.     mid = first + ((last - first) >> 1);
  285.  
  286.     f = v[*first];
  287.     m = v[*mid];
  288.     l = v[*last];
  289.  
  290.     if (PRECEDES(f, l))
  291.         {
  292.         if (PRECEDES(f, m))
  293.             pivot = (PRECEDES(m, l))? mid: last;
  294.         else
  295.             pivot = first;
  296.         }
  297.     else
  298.         {
  299.         if (FOLLOWS(f, m))
  300.             pivot = (PRECEDES(m, l))? last: mid;
  301.         else
  302.             pivot = first;
  303.         }
  304.     }
  305.  
  306.  
  307.     /* Swap the pivot element into sentinel position at the beginning: */
  308.  
  309.     pivot_key = v[*pivot];
  310.  
  311.     temp = *first;
  312.     *first = *pivot;
  313.     *pivot = temp;
  314.  
  315.  
  316.     /* Partition the array around the pivot: */
  317.  
  318.     low = first;
  319.     high = last;
  320.     while (low < high)
  321.         {
  322.         while (FOLLOWS(v[*high], pivot_key))
  323.             --high;
  324.         while (low < high && !(FOLLOWS(v[*low], pivot_key)))
  325.             ++low;
  326.         if (low < high)
  327.             {
  328.             temp = *low;
  329.             *low = *high;
  330.             *high = temp;
  331.             }
  332.         }
  333.  
  334.  
  335.     /* Swap the pivot into its proper place in the middle: */
  336.  
  337.     temp = *first;
  338.     *first = *high;
  339.     *high = temp;
  340.  
  341.  
  342.     /*
  343.      * Recurse to handle subarrays.  Use direct recursion on shortest
  344.      * subarray, then unwind tail recursion to handle second subarray.
  345.      * (This minimizes worst-case stack requirements.)  (Note:  the
  346.      * casts below eliminate two divisions.)
  347.      */
  348.  
  349.     if ((char *)high - (char *)first < (char *)last - (char *)high)
  350.         {
  351.         qsort(v, first, high - 1);
  352.         first = high + 1;
  353.         goto reenter;
  354.         }
  355.     else
  356.         {
  357.         qsort(v, high + 1, last);
  358.         last = high - 1;
  359.         goto reenter;
  360.         }
  361.     }
  362.  
  363.  
  364.  
  365. static int precedes(a, b)
  366. register OFFxyz *a;
  367. register OFFxyz *b;
  368.     {
  369.     if (a->x < b->x)
  370.         return 1;
  371.     if (a->x > b->x)
  372.         return 0;
  373.     if (a->y < b->y)
  374.         return 1;
  375.     if (a->y > b->y)
  376.         return 0;
  377.     return a->z < b->z;
  378.     }
  379.  
  380.  
  381.  
  382. static int follows(a, b)
  383. register OFFxyz *a;
  384. register OFFxyz *b;
  385.     {
  386.     if (a->x > b->x)
  387.         return 1;
  388.     if (a->x < b->x)
  389.         return 0;
  390.     if (a->y > b->y)
  391.         return 1;
  392.     if (a->y < b->y)
  393.         return 0;
  394.     return a->z > b->z;
  395.     }
  396.  
  397.  
  398.  
  399. static int equals(a, b)
  400. register OFFxyz *a;
  401. register OFFxyz *b;
  402.     {
  403.     return a->x == b->x && a->y == b->y && a->z == b->z;
  404.     }
  405.