/* shrink.c  -  minimize 3dv file size */

/* Oscar Garcia <garciao@mof.govt.nz>, May 1992 */

#define NDEBUG

/* uses getopt */
int getopt(int argc, char *argv[], char *options);
extern  int optind;
extern char *optarg;

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <mem.h>
#include <alloc.h>

#define USAGE "usage: shrink [/on] [/tx] [/q] [input_file [output_file]]\n\
\tIf file names are omitted, the standard i/o streams are used.\n\
\tOptions (with defaults):\n\
\t\t/o3    -  Optimization level (1, 2, or 3)\n\
\t\t/t1e6  -  Points closer than (range / xx) considered equal\n\
\t\t/q     -  Quiet, no progress info displayed\n"

#define ERROR(msg) {fputs(msg,stderr),exit(1);}
#define PERROR(msg) {perror(msg),exit(1);}

#define BIG 3e33
#define ODEFAULT 3
#define TDEFAULT 1e6

typedef float POINT[3];
typedef	struct
{	int from, to, colour;
}LINESTR;


/* test if two points are close enough */
int samepoint(POINT p, POINT q, double tol)
{   int i = 3;
	while (i-- > 0)
		if (fabs(*p++ - *q++) > tol)
			return 0;
	return 1;
}


void main(int argc, char* argv[])
{
	int i, j, k, n, m, p, col, first, last, *newi,
		oplevel = ODEFAULT, quiet = 0;
	double u, tolerance = TDEFAULT;
	unsigned long memory;
	char options[] = "o:t:q";
	FILE *infile = stdin, *outfile = stdout;
	POINT min, max, *x, *this, *seen;
	LINESTR *line;

	/* get options */
	while ((n = getopt(argc, argv, options)) != EOF)
		if (n == '?')
			ERROR(USAGE)
		else
			switch (n)
			{	case 'o':	oplevel = atoi(optarg); break;
				case 't':	tolerance = atof(optarg); break;
				case 'q':	quiet = 1; break;
			}
		if (oplevel < 1 || oplevel > 3 || tolerance <= 0)
		ERROR(USAGE);

	if (!quiet)
		fprintf(stderr, "SHRINK: 3dv file optimizer starting...\n");

	/* open files */
	if (optind < argc - 2)
		ERROR(USAGE);	/* too many */
	if (optind < argc)
	{	infile = fopen(argv[optind], "rt");
		if (infile == NULL)
			ERROR("Can't open input file");
		if (++optind < argc)
		{	outfile = fopen(argv[optind], "wt");
			if (outfile == NULL)
				ERROR("Can't open output file");
		}
	}

	/* read points */
	i = fscanf(infile, "%d", &n);
	if (i != 1 || ferror(infile))
		PERROR("Bad input file");
	newi = calloc(n + 1, sizeof(int));	/* space for new indices */
#ifdef __MSDOS__
	if ((unsigned)n * sizeof(POINT) > 0xfff0U)
		ERROR("64k memory block limit exceeded");
#endif
	x = malloc((unsigned)n * sizeof(POINT));
	if (x == NULL)
		ERROR("Out of memory");
	for (j = 0; j < 3; j++)
	{	min[j] = BIG;
		max[j] = -BIG;
	}
	if (!quiet)
		fprintf(stderr, "SHRINK: Reading %d points...\n",	n);
	for (i = 0; i < n; i++)
	{	fscanf(infile, "%f %f %f", &x[i][0], &x[i][1], &x[i][2]);
		for (j = 0; j < 3; j++)
		{	if (x[i][j] < min[j])
				min[j] = x[i][j];
			else if (x[i][j] > max[j])
				max[j] = x[i][j];
		}
	}
	if (ferror(infile))
		PERROR("Error reading input");

	/* check for duplicated points */
	if (!quiet)
		fprintf(stderr, "SHRINK: OK, checking for duplicates...\n");
	for (j = 0, u = -BIG; j < 3; j++)
		if (u < max[j] - min[j])
			u = max[j] - min[j];
	tolerance = u / tolerance;		/* comparison tolerance */
	for (this = x, i = j = 0; i++ < n; this++)
	{	for (seen = this; seen-- > x; )
			if (samepoint(*this, *seen, tolerance))
			{	newi[i] = -abs(newi[(unsigned)(seen-x)+1]);	/* flag to del.*/
				break;
			}
		if (newi[i] == 0)
			newi[i] = ++j;
	}

	/* output points, without duplicates */
	if (!quiet)
		fprintf(stderr, "SHRINK: Writing coordinates for %d points...\n", j);
	fprintf(outfile, "%d\n", j);	/* number of points */
	for (i = 0; i < n; i++)
	{	if (newi[i + 1] < 0)
			newi[i + 1] = - newi[i + 1];
		else
			fprintf(outfile, "%g %g %g\n", x[i][0], x[i][1], x[i][2]);
	}
	n = j;	/* new number of points */
	free(x);

	/* read lines, adjusting indices */
	fscanf(infile, "%d", &m);	/* number of lines */
	if (!quiet)
		fprintf(stderr, "SHRINK: Reading %d line move/draw commands...\n", m);
	memory = coreleft();
#ifdef __MSDOS__
	if (memory > 0xfff0U)
		memory = 0xfff0U;		/* avoid segment wraparound */
#endif
	memory = memory / sizeof(LINESTR);
	if (memory > m + 2)
		memory = m + 2;	/* upper bound for number of segments */
	line = malloc(memory * sizeof(LINESTR));
	if (line == NULL)
		ERROR("Memory allocation failure");	/* should not happen */
	for (i = 1; m > 0 && i < memory; m--)
	{	fscanf(infile, "%d %d", &j, &col);
		j = newi[j];
		if (col == 0)
			line[i].from = j;
		else
		{	line[i].to = j;
			line[i].colour = col;
			line[++i].from = j;
		}
	}
	if (i >= memory)
		ERROR("Out of memory");
	line[i].from = -1;	/* sentinel */
	m = i - 1;	/* number of line segments */
	if (ferror(infile))
		PERROR("Error reading input");
	if (feof(infile))
		ERROR("Unexpected end of file on input");
	fclose(infile);

	if (oplevel >1)
	{	/* check for duplicated lines */
		if (!quiet)
			fprintf(stderr,
				"SHRINK: Checking %d line segments for duplicates...\n", m);
		k = m;	/* count */
		for (i = 1; i <= m; i++)
			for (j = 1; j < i; j++)
				if ((line[i].from == line[j].from && line[i].to == line[j].to)
				 || (line[i].from == line[j].to && line[i].to == line[j].from))
				{	line[j].colour |= line[i].colour;
					line[i].from = -1;	/* flag for deletion */
					k--;		/* count */
					break;
				}
		if (!quiet)
			fprintf(stderr, "SHRINK: %d segments left.\n", k);
	}

	if (oplevel > 2)
	{
		/* minimize number of moves */
		if (!quiet)
			fprintf(stderr, "SHRINK: Minimizing moves...\n");
		/* Chains of line segments built as linked lists, using line[].to as
			pointers to next segment.  Last line[].to in chain in the last point
			number, flagged with a minus sign.  Re-use newi[p] to point to chain
			starting (positive) or ending (negative) with point p.  Actually,
			use array indices instead of real pointers.
		*/
		memset(newi, 0, (n+1) * sizeof(int));  /* zero chain pointers array */
		for (i = 1; i <= m; i++)
			if ((first = line[i].from) > 0)		/* valid segment */
			{	if ((j = newi[first]) == 0)	/* other chains start/end at first? */
					newi[first] = i;	/* no, flag this one */
				else if (j < 0)
				{	/* chain at -j ends with first, link it to here */
					newi[first] = 0;	/* not end of chain anymore */
					first = line[-j].from;	/* new start of chain */
					for (j = -j; line[j].to > 0; j = line[j].to)
						;	/* follow chain, last point flagged with minus */
					assert(-line[j].to == line[i].from);	/* debugging check */
					line[j].to = i;		/* point to current segment */
				}
				else
				{	/* chain at j starts with first, reverse it and link */
					assert(line[i].from == line[j].from);
					newi[first] = 0;	/* not start of chain anymore */
					p = i;	/* point to here */
					while ((first = -line[j].to) < 0)	/* reverse */
					{	line[j].to = p;	/* point to previous segment */
						p = j;			/* next one should point to here */
						j = -first;		/* next segment index */
						line[p].from = line[j].from;
					}
					line[j].from = first;	/* new first segment */
					line[j].to = p;
					newi[first] = j;	/* point to it */
				}

				/* now link consecutive segments */
				while (line[i+1].from == line[i].to)
				{	line[i].to = i + 1;
					i++;
				}
				last = line[i].to;		/* last point */
				line[i].to = -last;		/* flag end of chain */

				/* see if other chains start/end at last */
				if (last == first)
					;	/* but avoid chasing your tail! */
				else if ((j = newi[last]) == 0)
					newi[last] = -newi[first];		/* flag this end */
				else if (j > 0)
				{	/* chain at j starts with last, link to it */
					newi[last] = 0;	/* not start of chain anymore */
					assert(-line[i].to == line[j].from);	/* debugging check */
					line[i].to = j;		/* point to it */
					while (line[j].to > 0)
						j = line[j].to;	/* follow chain to last point */
					newi[-line[j].to] = -newi[first];	/* end pointer */
				}
				else
				{	/* chain at -j ends with last, reverse and link to it */
					newi[last] = 0;	/* not end of chain anymore */
					p = -line[j = -j].from;	/* new end of chain */
					newi[-p] = - newi[first];	/* end pointer */
					while ((last = -line[j].to) < 0)	/* reverse */
					{	line[j].to = p;	/* point to previous segment */
						p = j;			/* next one should point to here */
						j = -last;		/* next segment index */
						line[p].from = line[j].from;
					}
					assert(-line[i].to == last);	/* check */
					line[j].from = last;	/* new first segment */
					line[j].to = p;
					line[i].to = j;	/* point to it */
				}
			}

		/* output lines */
		/* first count the moves/draws */
		for (m = 0, i = 1; i <= n; i++)
			if (newi[i] > 0)
			{	m++;	/* move */
				for (j = newi[i]; j > 0; j = line[j].to)
					m++;	/* draw */
			}
		fprintf(outfile, "%d\n", m);	/* output the count */
		/* now output the moves/draws */
		if (!quiet)
			fprintf(stderr,
				"SHRINK: OK, Writing %d line move/draw commands...\n", m);
		for (i = 1; i <= n; i++)
			if (newi[i] > 0)
			{	for (j = newi[i], col = 0; j > 0; j = line[j].to)
				{	fprintf(outfile, "%d %d\n", line[j].from, col);
					col = line[j].colour;
				}
				fprintf(outfile, "%d %d\n", -j, col);
			}
	}

	else	/* optlevel < 3, no lines optimization */
	{
		/* just output the lines */
		for (i = 1, j = -1, n = 0; i <= m; i++)	/* count moves/draws */
			if (line[i].from > 0)
			{	if (line[i].from != j)
					n++;	/* move */
				j = line[i].to;
				n++;	/* draw */
			}
		fprintf(outfile, "%d\n", n);
		if (!quiet)
			fprintf(stderr,
				"SHRINK: Writing %d line move/draw commands...\n", n);
		for (i = 1, j = -1; i <= m; i++)		/* output moves/draws */
			if (line[i].from > 0)
			{	if (line[i].from != j)
					fprintf(outfile, "%d 0\n", line[i].from);	/* move */
				j = line[i].to;
				fprintf(outfile, "%d %d\n", j, line[i].colour);	/* draw */
			}
	}

	if (ferror(outfile))
		PERROR("Error writing output");
	fclose(outfile);
	if (!quiet)
		fprintf(stderr, "SHRINK: Done.\n");

}