/*----------------------------------------------------------------------

				 DXF2HSH
		DXF polyline to DXF 3DFace converter
			 by Vance Gloster	May 1994
			    based on
				 DXF2TRI
		DXF polyline/polygon to triangle converter
			 by Tim Riley   Aug 1993
				based on
		POLY2TRI - a polygon to triangle converter
			 by Steve Anger Jan 1993

This program is commited to the public domain. Feel free to use all or part
of this code in your own programs.

This is a utility that extracts polyline shapes from a DXF file and breaks
them down into individual triangles. The polylines are assumed to be closed,
planar (2D) polygons. This program only deals with POLYLINE entities and
ignores all other entities in the DXF file. All properties (color, line type)
are ignored. 

The input DXF file consists of one or more polylines with no more than 2000
vertices. This limit is rather arbitrary and can be changed if necessary (by
changing POLYMAX).

The program uses the following syntax:
	DXF2TRI infile[.DXF] outfile[.DXF] [xy]

The output is a DXF file that uses the 3DFace objects Animation Master can read
instead of polyline objects which is what most packages use.

-----------------------------------------------------------------------*/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    float x, y, z;
} Vector;

int remove_triangle (Vector *poly, int *polysize, Vector *v1, Vector *v2, Vector *v3);
int poly_inside (Vector *poly, int polysize, Vector *v);
void vect_init (Vector *v, float x, float y, float z);
void vect_copy (Vector *v1, Vector *v2);
void vect_add (Vector *v1, Vector *v2, Vector *v3);
void vect_sub (Vector *v1, Vector *v2, Vector *v3);
void vect_scale (Vector *v, float k);
float vect_mag (Vector *v);
float dot_prod (Vector *v1, Vector *v2);
void cross_prod (Vector *v1, Vector *v2, Vector *v3);
float vect_angle (Vector *v1, Vector *v2);
void add_ext (char *fname, char *ext, int force);
void pr_error (void);
void option (char *string, int *extrude, int *back);

#define POLYMAX 2000
#define M_PI	3.1415926535

int main (int argc, char *argv[])
{
	FILE *fp_in, *fp_out;
	char infile[20] = "", outfile[20] = "", string[80];
	int polysize, i, extrude = 0, back = 0, dimension_code;
	float temp1, temp2;
	Vector v[POLYMAX], v1, v2, v3;

    if (argc < 3) pr_error ();

    strcpy (infile, argv[1]);
	strcpy (outfile, argv[2]);
    add_ext (infile, "dxf", 0);
    add_ext (outfile, "dxf", 0);

	if((argc > 3) && (!strcmp(argv[3], "xy") || !strcmp(argv[3], "XY")))
		dimension_code = 20;
	else
		dimension_code = 30;
	
	if ((fp_in=fopen(infile,"r")) == NULL) {
		printf ("Cannot open input file '%s'\n", infile);
		exit (EXIT_FAILURE);
	}

	if ((fp_out=fopen(outfile,"w")) == NULL) {
		printf ("Cannot open output file '%s'\n", outfile);
		exit (EXIT_FAILURE);
	}
	fprintf(fp_out, "0\nSECTION\n2\nENTITIES\n");
	do {
		fscanf (fp_in, "%s", &string);
	} while (strcmp (string, "ENTITIES") != 0);

	while (1) {
		do {
			fscanf (fp_in, "%s", &string);
		} while (strcmp (string, "POLYLINE") != 0 &&
			 strcmp (string, "ENDSEC") != 0);
		if (strcmp (string, "ENDSEC") == 0) break;

		polysize = 0;
		while (1) {
			do{
				fscanf (fp_in, "%s", &string);
			}while (strcmp (string, "VERTEX") != 0 &&
				 strcmp (string, "SEQEND") != 0);
			if (strcmp (string, "SEQEND") == 0) break;
			do {
				fscanf (fp_in, "%f", &temp1);
				fscanf (fp_in, "%f", &temp2);
			} while (temp1 != 10);
			v[polysize].x = temp2;
			do {
				fscanf (fp_in, "%f", &temp1);
				fscanf (fp_in, "%f", &temp2);
			} while (temp1 != dimension_code);
			v[polysize].y = temp2;
			v[polysize++].z = (float) 0.0;
   			 if (polysize >= POLYMAX) {
				printf ("Too many vertices. Break up into smaller sections & try again.\n");
				fclose (fp_in);
				fclose (fp_out);
				exit (1);
 			 }
		}
		/* Extrude 1 unit deep along the z axis */
		/* extrusion is currently disabled */
		if (extrude == 1) {
			for (i=0; i<polysize; i++) {
				if (i<polysize-1) {
	  		  		fprintf (fp_out, "%f %f %f %f %f %f %f %f %f \n",
						 v[i].x, v[i].y, v[i].z,
						 v[i+1].x, v[i+1].y, v[i+1].z,
						 v[i+1].x, v[i+1].y, v[i+1].z+1);
					fprintf (fp_out, "%f %f %f %f %f %f %f %f %f \n",
						 v[i].x, v[i].y, v[i].z,
						 v[i+1].x, v[i+1].y, v[i+1].z+1,
						 v[i].x, v[i].y, v[i].z+1);
				}
				else {
					fprintf (fp_out, "%f %f %f %f %f %f %f %f %f \n",
						 v[i].x, v[i].y, v[i].z,
						 v[0].x, v[0].y, v[0].z,
						 v[0].x, v[0].y, v[0].z+1);
					fprintf (fp_out, "%f %f %f %f %f %f %f %f %f \n",
						 v[i].x, v[i].y, v[i].z,
						 v[0].x, v[0].y, v[0].z+1,
						 v[i].x, v[i].y, v[i].z+1);
				}
			}
		}

		/* Remove triangles from the polygon until there's nothing left */
		while (remove_triangle (v, &polysize, &v1, &v2, &v3)) {
			fprintf(fp_out, "0\n3DFACE\n8\n2\n10\n%f\n20\n%f\n30\n%f\n",
				v1.x, v1.y, v1.z);
			fprintf(fp_out, "11\n%f\n21\n%f\n31\n%f\n12\n%f\n22\n%f\n32\n%f\n13\n%f\n23\n%f\n33\n%f\n",
				v2.x, v2.y, v2.z, v3.x, v3.y, v3.z, v3.x, v3.y, v3.z);
		}
	}
	fprintf(fp_out, "0\nENDSEC\n0\nEOF\n");
	fclose (fp_in);
	fclose (fp_out);
	return 0;
}

void pr_error ()
{
	printf ("Usage: infile[.dxf] outfile[.dxf] [xy]\n\n");
	exit (1);
}

void option (char *string, int *extrude, int *back)
{
	if (string[0] != '-') pr_error();
	if (string[1] == 'e' || string[1] == 'E') *extrude =1;
	if (string[1] == 'b' || string[1] == 'B') *back =1;
}

/* Removes a triangle from the specified polygon. */
/* The size of the polygon is reduced */
int remove_triangle (Vector *poly, int *polysize,
		     Vector *v1, Vector *v2, Vector *v3)
{
    Vector tri[3], center;
    int    i, j, a, b, c;

    if (*polysize < 3)
	return 0; /* No triangle found */

    /* This simplest case */
    if (*polysize == 3) {
	vect_copy (v1, &poly[0]);
	vect_copy (v2, &poly[1]);
	vect_copy (v3, &poly[2]);

	*polysize = 0;

	return 1;  /* Ok */
    }

    for (i = 0; i < *polysize; i++) {
	a = i;
	b = (i + 1) % *polysize;
	c = (i + 2) % *polysize;

	/* Select a candidate triangle */
	vect_copy (&tri[0], &poly[a]);
	vect_copy (&tri[1], &poly[b]);
	vect_copy (&tri[2], &poly[c]);

	/* Calculate the center of the triangle */
	vect_init (&center, (float) 0.0, (float) 0.0, (float) 0.0);
	vect_add (&center, &center, &tri[0]);
	vect_add (&center, &center, &tri[1]);
	vect_add (&center, &center, &tri[2]);
	vect_scale (&center, (float) (1.0/3.0) );

	/* Is the center of the triangle inside the original polygon? */
	/* If not skip this triangle */
	if (!poly_inside (poly, *polysize, &center))
	    continue;

	/* Are any of the polygons other vertices inside the triangle */
	/* If so skip this triangle */
	for (j = 0; j < *polysize; j++) {
	    if (j != a && j != b && j != c && poly_inside (tri, 3, &poly[j]))
		break;
	}

	if (j < *polysize)
	    continue;

	/* This is the one */
	vect_copy (v1, &tri[0]);
	vect_copy (v2, &tri[1]);
	vect_copy (v3, &tri[2]);

	/* Remove this triangle from the polygon */
	(*polysize)--;
	for (j = b; j < *polysize; j++)
	    vect_copy (&poly[j], &poly[j+1]);

	return 1; /* Ok */
    }

    return 0; /* No triangle found */
}


/* Determines if the specified point 'v' is inside the polygon. */
/* Uses a convoluted version of the sum of angles approach */
int poly_inside (Vector *poly, int polysize, Vector *v)
{
    Vector sum, cross, v1, v2;
    float  magcross;
    int    i;

    vect_init (&sum, (float) 0.0, (float) 0.0, (float) 0.0);

    for (i = 0; i < polysize; i++) {
	vect_sub (&v1, v, &poly[i]);
	vect_sub (&v2, v, &poly[(i+1) % polysize]);

	cross_prod (&cross, &v1, &v2);
	magcross = vect_mag (&cross);

	if (magcross > 0.0)
	    vect_scale (&cross, (float) 1.0/magcross);

	vect_scale (&cross, vect_angle (&v1, &v2));
	vect_add (&sum, &sum, &cross);
    }

    return (vect_mag (&sum) > M_PI);
}


void vect_init (Vector *v, float  x, float  y, float  z)
{
    v->x = x;
    v->y = y;
    v->z = z;
}


void vect_copy (Vector *v1, Vector *v2)
{
    v1->x = v2->x;
    v1->y = v2->y;
    v1->z = v2->z;
}


void vect_add (Vector *v1, Vector *v2, Vector *v3)
{
    v1->x = v2->x + v3->x;
    v1->y = v2->y + v3->y;
    v1->z = v2->z + v3->z;
}


void vect_sub (Vector *v1, Vector *v2, Vector *v3)
{
    v1->x = v2->x - v3->x;
    v1->y = v2->y - v3->y;
    v1->z = v2->z - v3->z;
}


void vect_scale (Vector *v, float  k)
{
    v->x = k * v->x;
    v->y = k * v->y;
    v->z = k * v->z;
}


float vect_mag (Vector *v)
{
    float mag;
    if (v->x==0.0 && v->y==0.0 && v->z==0.0) return (float) 0.0;
    mag = (float) sqrt(v->x*v->x + v->y*v->y + v->z*v->z);

    return mag;
}


float dot_prod (Vector *v1, Vector *v2)
{
    return (v1->x*v2->x + v1->y*v2->y + v1->z*v2->z);
}


void cross_prod (Vector *v1, Vector *v2, Vector *v3)
{
    v1->x = (v2->y * v3->z) - (v2->z * v3->y);
    v1->y = (v2->z * v3->x) - (v2->x * v3->z);
    v1->z = (v2->x * v3->y) - (v2->y * v3->x);
}


/* Return the angle (rads) between two vectors */
float vect_angle (Vector *v1, Vector *v2)
{
    float  mag1, mag2, angle, cos_theta;

    mag1 = vect_mag(v1);
    mag2 = vect_mag(v2);

    if (mag1 * mag2 == 0.0)
	angle = (float) 0.0;
    else {
	cos_theta = dot_prod(v1,v2) / (mag1 * mag2);

	if (cos_theta <= -1.0)
	    angle = (float) M_PI;
	else if (cos_theta >= +1.0)
	    angle = (float) 0.0;
	else
	    angle = (float) acos(cos_theta);
    }

    return angle;
}

void add_ext (char *fname, char *ext, int force)
{
    int i;

    for (i = 0; i < (int) strlen (fname); i++)
	if (fname[i] == '.') break;

    if (fname[i] == '\0' || force) {
	if (strlen (ext) > 0)
	    fname[i++] = '.';

	strcpy (&fname[i], ext);
    }
}
