home *** CD-ROM | disk | FTP | other *** search
/ Virtual Reality Zone / VRZONE.ISO / mac / PC / MISC3D / 3DKIT1 / SHRINK.C < prev    next >
Text File  |  1992-09-08  |  10KB  |  339 lines
  1. /* shrink.c  -  minimize 3dv file size */
  2.  
  3. /* Oscar Garcia <garciao@mof.govt.nz>, May 1992 */
  4.  
  5. #define NDEBUG
  6.  
  7. /* uses getopt */
  8. int getopt(int argc, char *argv[], char *options);
  9. extern  int optind;
  10. extern char *optarg;
  11.  
  12. #include <stdlib.h>
  13. #include <stdio.h>
  14. #include <math.h>
  15. #include <assert.h>
  16. #include <mem.h>
  17. #include <alloc.h>
  18.  
  19. #define USAGE "usage: shrink [/on] [/tx] [/q] [input_file [output_file]]\n\
  20. \tIf file names are omitted, the standard i/o streams are used.\n\
  21. \tOptions (with defaults):\n\
  22. \t\t/o3    -  Optimization level (1, 2, or 3)\n\
  23. \t\t/t1e6  -  Points closer than (range / xx) considered equal\n\
  24. \t\t/q     -  Quiet, no progress info displayed\n"
  25.  
  26. #define ERROR(msg) {fputs(msg,stderr),exit(1);}
  27. #define PERROR(msg) {perror(msg),exit(1);}
  28.  
  29. #define BIG 3e33
  30. #define ODEFAULT 3
  31. #define TDEFAULT 1e6
  32.  
  33. typedef float POINT[3];
  34. typedef    struct
  35. {    int from, to, colour;
  36. }LINESTR;
  37.  
  38.  
  39. /* test if two points are close enough */
  40. int samepoint(POINT p, POINT q, double tol)
  41. {   int i = 3;
  42.     while (i-- > 0)
  43.         if (fabs(*p++ - *q++) > tol)
  44.             return 0;
  45.     return 1;
  46. }
  47.  
  48.  
  49. void main(int argc, char* argv[])
  50. {
  51.     int i, j, k, n, m, p, col, first, last, *newi,
  52.         oplevel = ODEFAULT, quiet = 0;
  53.     double u, tolerance = TDEFAULT;
  54.     unsigned long memory;
  55.     char options[] = "o:t:q";
  56.     FILE *infile = stdin, *outfile = stdout;
  57.     POINT min, max, *x, *this, *seen;
  58.     LINESTR *line;
  59.  
  60.     /* get options */
  61.     while ((n = getopt(argc, argv, options)) != EOF)
  62.         if (n == '?')
  63.             ERROR(USAGE)
  64.         else
  65.             switch (n)
  66.             {    case 'o':    oplevel = atoi(optarg); break;
  67.                 case 't':    tolerance = atof(optarg); break;
  68.                 case 'q':    quiet = 1; break;
  69.             }
  70.         if (oplevel < 1 || oplevel > 3 || tolerance <= 0)
  71.         ERROR(USAGE);
  72.  
  73.     if (!quiet)
  74.         fprintf(stderr, "SHRINK: 3dv file optimizer starting...\n");
  75.  
  76.     /* open files */
  77.     if (optind < argc - 2)
  78.         ERROR(USAGE);    /* too many */
  79.     if (optind < argc)
  80.     {    infile = fopen(argv[optind], "rt");
  81.         if (infile == NULL)
  82.             ERROR("Can't open input file");
  83.         if (++optind < argc)
  84.         {    outfile = fopen(argv[optind], "wt");
  85.             if (outfile == NULL)
  86.                 ERROR("Can't open output file");
  87.         }
  88.     }
  89.  
  90.     /* read points */
  91.     i = fscanf(infile, "%d", &n);
  92.     if (i != 1 || ferror(infile))
  93.         PERROR("Bad input file");
  94.     newi = calloc(n + 1, sizeof(int));    /* space for new indices */
  95. #ifdef __MSDOS__
  96.     if ((unsigned)n * sizeof(POINT) > 0xfff0U)
  97.         ERROR("64k memory block limit exceeded");
  98. #endif
  99.     x = malloc((unsigned)n * sizeof(POINT));
  100.     if (x == NULL)
  101.         ERROR("Out of memory");
  102.     for (j = 0; j < 3; j++)
  103.     {    min[j] = BIG;
  104.         max[j] = -BIG;
  105.     }
  106.     if (!quiet)
  107.         fprintf(stderr, "SHRINK: Reading %d points...\n",    n);
  108.     for (i = 0; i < n; i++)
  109.     {    fscanf(infile, "%f %f %f", &x[i][0], &x[i][1], &x[i][2]);
  110.         for (j = 0; j < 3; j++)
  111.         {    if (x[i][j] < min[j])
  112.                 min[j] = x[i][j];
  113.             else if (x[i][j] > max[j])
  114.                 max[j] = x[i][j];
  115.         }
  116.     }
  117.     if (ferror(infile))
  118.         PERROR("Error reading input");
  119.  
  120.     /* check for duplicated points */
  121.     if (!quiet)
  122.         fprintf(stderr, "SHRINK: OK, checking for duplicates...\n");
  123.     for (j = 0, u = -BIG; j < 3; j++)
  124.         if (u < max[j] - min[j])
  125.             u = max[j] - min[j];
  126.     tolerance = u / tolerance;        /* comparison tolerance */
  127.     for (this = x, i = j = 0; i++ < n; this++)
  128.     {    for (seen = this; seen-- > x; )
  129.             if (samepoint(*this, *seen, tolerance))
  130.             {    newi[i] = -abs(newi[(unsigned)(seen-x)+1]);    /* flag to del.*/
  131.                 break;
  132.             }
  133.         if (newi[i] == 0)
  134.             newi[i] = ++j;
  135.     }
  136.  
  137.     /* output points, without duplicates */
  138.     if (!quiet)
  139.         fprintf(stderr, "SHRINK: Writing coordinates for %d points...\n", j);
  140.     fprintf(outfile, "%d\n", j);    /* number of points */
  141.     for (i = 0; i < n; i++)
  142.     {    if (newi[i + 1] < 0)
  143.             newi[i + 1] = - newi[i + 1];
  144.         else
  145.             fprintf(outfile, "%g %g %g\n", x[i][0], x[i][1], x[i][2]);
  146.     }
  147.     n = j;    /* new number of points */
  148.     free(x);
  149.  
  150.     /* read lines, adjusting indices */
  151.     fscanf(infile, "%d", &m);    /* number of lines */
  152.     if (!quiet)
  153.         fprintf(stderr, "SHRINK: Reading %d line move/draw commands...\n", m);
  154.     memory = coreleft();
  155. #ifdef __MSDOS__
  156.     if (memory > 0xfff0U)
  157.         memory = 0xfff0U;        /* avoid segment wraparound */
  158. #endif
  159.     memory = memory / sizeof(LINESTR);
  160.     if (memory > m + 2)
  161.         memory = m + 2;    /* upper bound for number of segments */
  162.     line = malloc(memory * sizeof(LINESTR));
  163.     if (line == NULL)
  164.         ERROR("Memory allocation failure");    /* should not happen */
  165.     for (i = 1; m > 0 && i < memory; m--)
  166.     {    fscanf(infile, "%d %d", &j, &col);
  167.         j = newi[j];
  168.         if (col == 0)
  169.             line[i].from = j;
  170.         else
  171.         {    line[i].to = j;
  172.             line[i].colour = col;
  173.             line[++i].from = j;
  174.         }
  175.     }
  176.     if (i >= memory)
  177.         ERROR("Out of memory");
  178.     line[i].from = -1;    /* sentinel */
  179.     m = i - 1;    /* number of line segments */
  180.     if (ferror(infile))
  181.         PERROR("Error reading input");
  182.     if (feof(infile))
  183.         ERROR("Unexpected end of file on input");
  184.     fclose(infile);
  185.  
  186.     if (oplevel >1)
  187.     {    /* check for duplicated lines */
  188.         if (!quiet)
  189.             fprintf(stderr,
  190.                 "SHRINK: Checking %d line segments for duplicates...\n", m);
  191.         k = m;    /* count */
  192.         for (i = 1; i <= m; i++)
  193.             for (j = 1; j < i; j++)
  194.                 if ((line[i].from == line[j].from && line[i].to == line[j].to)
  195.                  || (line[i].from == line[j].to && line[i].to == line[j].from))
  196.                 {    line[j].colour |= line[i].colour;
  197.                     line[i].from = -1;    /* flag for deletion */
  198.                     k--;        /* count */
  199.                     break;
  200.                 }
  201.         if (!quiet)
  202.             fprintf(stderr, "SHRINK: %d segments left.\n", k);
  203.     }
  204.  
  205.     if (oplevel > 2)
  206.     {
  207.         /* minimize number of moves */
  208.         if (!quiet)
  209.             fprintf(stderr, "SHRINK: Minimizing moves...\n");
  210.         /* Chains of line segments built as linked lists, using line[].to as
  211.             pointers to next segment.  Last line[].to in chain in the last point
  212.             number, flagged with a minus sign.  Re-use newi[p] to point to chain
  213.             starting (positive) or ending (negative) with point p.  Actually,
  214.             use array indices instead of real pointers.
  215.         */
  216.         memset(newi, 0, (n+1) * sizeof(int));  /* zero chain pointers array */
  217.         for (i = 1; i <= m; i++)
  218.             if ((first = line[i].from) > 0)        /* valid segment */
  219.             {    if ((j = newi[first]) == 0)    /* other chains start/end at first? */
  220.                     newi[first] = i;    /* no, flag this one */
  221.                 else if (j < 0)
  222.                 {    /* chain at -j ends with first, link it to here */
  223.                     newi[first] = 0;    /* not end of chain anymore */
  224.                     first = line[-j].from;    /* new start of chain */
  225.                     for (j = -j; line[j].to > 0; j = line[j].to)
  226.                         ;    /* follow chain, last point flagged with minus */
  227.                     assert(-line[j].to == line[i].from);    /* debugging check */
  228.                     line[j].to = i;        /* point to current segment */
  229.                 }
  230.                 else
  231.                 {    /* chain at j starts with first, reverse it and link */
  232.                     assert(line[i].from == line[j].from);
  233.                     newi[first] = 0;    /* not start of chain anymore */
  234.                     p = i;    /* point to here */
  235.                     while ((first = -line[j].to) < 0)    /* reverse */
  236.                     {    line[j].to = p;    /* point to previous segment */
  237.                         p = j;            /* next one should point to here */
  238.                         j = -first;        /* next segment index */
  239.                         line[p].from = line[j].from;
  240.                     }
  241.                     line[j].from = first;    /* new first segment */
  242.                     line[j].to = p;
  243.                     newi[first] = j;    /* point to it */
  244.                 }
  245.  
  246.                 /* now link consecutive segments */
  247.                 while (line[i+1].from == line[i].to)
  248.                 {    line[i].to = i + 1;
  249.                     i++;
  250.                 }
  251.                 last = line[i].to;        /* last point */
  252.                 line[i].to = -last;        /* flag end of chain */
  253.  
  254.                 /* see if other chains start/end at last */
  255.                 if (last == first)
  256.                     ;    /* but avoid chasing your tail! */
  257.                 else if ((j = newi[last]) == 0)
  258.                     newi[last] = -newi[first];        /* flag this end */
  259.                 else if (j > 0)
  260.                 {    /* chain at j starts with last, link to it */
  261.                     newi[last] = 0;    /* not start of chain anymore */
  262.                     assert(-line[i].to == line[j].from);    /* debugging check */
  263.                     line[i].to = j;        /* point to it */
  264.                     while (line[j].to > 0)
  265.                         j = line[j].to;    /* follow chain to last point */
  266.                     newi[-line[j].to] = -newi[first];    /* end pointer */
  267.                 }
  268.                 else
  269.                 {    /* chain at -j ends with last, reverse and link to it */
  270.                     newi[last] = 0;    /* not end of chain anymore */
  271.                     p = -line[j = -j].from;    /* new end of chain */
  272.                     newi[-p] = - newi[first];    /* end pointer */
  273.                     while ((last = -line[j].to) < 0)    /* reverse */
  274.                     {    line[j].to = p;    /* point to previous segment */
  275.                         p = j;            /* next one should point to here */
  276.                         j = -last;        /* next segment index */
  277.                         line[p].from = line[j].from;
  278.                     }
  279.                     assert(-line[i].to == last);    /* check */
  280.                     line[j].from = last;    /* new first segment */
  281.                     line[j].to = p;
  282.                     line[i].to = j;    /* point to it */
  283.                 }
  284.             }
  285.  
  286.         /* output lines */
  287.         /* first count the moves/draws */
  288.         for (m = 0, i = 1; i <= n; i++)
  289.             if (newi[i] > 0)
  290.             {    m++;    /* move */
  291.                 for (j = newi[i]; j > 0; j = line[j].to)
  292.                     m++;    /* draw */
  293.             }
  294.         fprintf(outfile, "%d\n", m);    /* output the count */
  295.         /* now output the moves/draws */
  296.         if (!quiet)
  297.             fprintf(stderr,
  298.                 "SHRINK: OK, Writing %d line move/draw commands...\n", m);
  299.         for (i = 1; i <= n; i++)
  300.             if (newi[i] > 0)
  301.             {    for (j = newi[i], col = 0; j > 0; j = line[j].to)
  302.                 {    fprintf(outfile, "%d %d\n", line[j].from, col);
  303.                     col = line[j].colour;
  304.                 }
  305.                 fprintf(outfile, "%d %d\n", -j, col);
  306.             }
  307.     }
  308.  
  309.     else    /* optlevel < 3, no lines optimization */
  310.     {
  311.         /* just output the lines */
  312.         for (i = 1, j = -1, n = 0; i <= m; i++)    /* count moves/draws */
  313.             if (line[i].from > 0)
  314.             {    if (line[i].from != j)
  315.                     n++;    /* move */
  316.                 j = line[i].to;
  317.                 n++;    /* draw */
  318.             }
  319.         fprintf(outfile, "%d\n", n);
  320.         if (!quiet)
  321.             fprintf(stderr,
  322.                 "SHRINK: Writing %d line move/draw commands...\n", n);
  323.         for (i = 1, j = -1; i <= m; i++)        /* output moves/draws */
  324.             if (line[i].from > 0)
  325.             {    if (line[i].from != j)
  326.                     fprintf(outfile, "%d 0\n", line[i].from);    /* move */
  327.                 j = line[i].to;
  328.                 fprintf(outfile, "%d %d\n", j, line[i].colour);    /* draw */
  329.             }
  330.     }
  331.  
  332.     if (ferror(outfile))
  333.         PERROR("Error writing output");
  334.     fclose(outfile);
  335.     if (!quiet)
  336.         fprintf(stderr, "SHRINK: Done.\n");
  337.  
  338. }
  339.