const char * UsageLines [] = {
	"Usage: xyzproject (camera) (target) (width) (height) (magnification)",
	"Reads corners of polygons in x,y,z coordinates, from standard input.",
	"Writes a ppm image of specified width and height to standard output.",
	"Each nonblank input line must begin with colors r g b followed",
	"by x,y,z for each corner (at least 3 corners to have any effect).",
	"The order is front-to-back, meaning a polygon will cover",
	"any polygon given in a later line.",
	"The x,y,z position of the viewer (camera) and the target are given",
	"in the command line.",
	"z is the up direction.",
	"The camera cannot point straight up or straight down.",
	"xyzproject ignores anything after # to end-of-line.",
	"January 4, 2015.  Newest is at gopher -p users/julianbr sdf.org",
	};
const int NumUsageLines = sizeof (UsageLines)/sizeof (UsageLines [0] );


struct Polygon {
	int r, g, b;
	struct Corner {
		long int x, y, z;
		struct Corner * next;
		} * Corners;
	struct Polygon * next;
	};

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


#define LengthTarget 15
#define BackgroundR 200
#define BackgroundG 200
#define BackgroundB 200


int ReadPolygon (struct Polygon * * PolygonPtr, int * EndOfInputPtr)
	{
	struct Polygon * Polygon;
	struct Corner * * CornerPtr, * Corners, * Corner;
	int ok, c, IsNegative;
	int r, g, b, x, y, z, Found, FoundB, FoundZ;

	ok = 1;
	c = getchar ();
	while (c == ' ')
		c = getchar ();
	Found = 0;
	Polygon = NULL;
	if (c != EOF && c != '\n' && c != '#') {
		Found = 1;
		PolygonPtr [0] = malloc (sizeof (PolygonPtr [0] [0] ) );
		Polygon = PolygonPtr [0];
		if (ok && Polygon == NULL) {
			fprintf (stderr, "***xyzproject: Not enough memory");
			ok = 0;
			}
		}
	IsNegative = 0;
	if (c == '+')
		c = getchar ();
	else if (c == '-') {
		IsNegative = 1;
		c = getchar ();
		}
	r = 0;
	while (c >= '0' && c <= '9') {
		r = 10*r + (c - '0');
		c = getchar ();
		}
	if (IsNegative)
		r = - r;
	while (c == ' ')
		c = getchar ();
	IsNegative = 0;
	if (c == '+')
		c = getchar ();
	else if (c == '-') {
		IsNegative = 1;
		c = getchar ();
		}
	g = 0;
	while (c >= '0' && c <= '9') {
		g = 10*g + (c - '0');
		c = getchar ();
		}
	if (IsNegative)
		g = - g;
	while (c == ' ')
		c = getchar ();
	IsNegative = 0;
	if (c == '+')
		c = getchar ();
	else if (c == '-') {
		IsNegative = 1;
		c = getchar ();
		}
	FoundB = 0;
	b = 0;
	while (c >= '0' && c <= '9') {
		FoundB = 1;
		b = 10*b + (c - '0');
		c = getchar ();
		}
	if (IsNegative)
		b = - b;
	if (ok && Found && !FoundB) {
		fprintf (stderr, "***xyzproject: r g b not found");
		ok = 0;
		}
	Corners = NULL;
	CornerPtr = & Corners;
	while (c == ' ')
		c = getchar ();
	while (c == '+' || c == '-' || (c >= '0' && c <= '9') ) {
		CornerPtr [0] = malloc (sizeof (CornerPtr [0] [0] ) );
		Corner = CornerPtr [0];
		if (ok && CornerPtr [0] == NULL) {
			fprintf (stderr, "***xyzproject: Not");
			fprintf (stderr, " enough memory");
			ok = 0;
			}
		IsNegative = 0;
		if (c == '+')
			c = getchar ();
		else if (c == '-') {
			IsNegative = 1;
			c = getchar ();
			}
		x = 0;
		while (c >= '0' && c <= '9') {
			x = 10*x + (c - '0');
			c = getchar ();
			}
		if (IsNegative)
			x = - x;
		if (c == ',')
			c = getchar ();
		IsNegative = 0;
		if (c == '+')
			c = getchar ();
		else if (c == '-') {
			IsNegative = 1;
			c = getchar ();
			}
		y = 0;
		while (c >= '0' && c <= '9') {
			y = 10*y + (c - '0');
			c = getchar ();
			}
		if (IsNegative)
			y = - y;
		if (c == ',')
			c = getchar ();
		IsNegative = 0;
		if (c == '+')
			c = getchar ();
		else if (c == '-') {
			IsNegative = 1;
			c = getchar ();
			}
		FoundZ = 0;
		z = 0;
		while (c >= '0' && c <= '9') {
			FoundZ = 1;
			z = 10*z + (c - '0');
			c = getchar ();
			}
		if (IsNegative)
			z = - z;
		if (ok && !FoundZ) {
			fprintf (stderr, "***xyzproject: Didn't find x,y,z");
			ok = 0;
			}
		while (c == ' ')
			c = getchar ();
		if (Corner != NULL) {
			Corner->x = x;
			Corner->y = y;
			Corner->z = z;
			Corner->next = NULL;
			CornerPtr = & Corner->next;
			}
		}
	if (ok && c != EOF && c != '\n' && c != '#') {
		fprintf (stderr, "***xyzproject: Found improper");
		fprintf (stderr, " '%c'", c);
		ok = 0;
		}
	while (c != EOF && c != '\n')
		c = getchar ();
	if (Polygon != NULL) {
		Polygon->r = r;
		Polygon->g = g;
		Polygon->b = b;
		Polygon->Corners = Corners;
		Polygon->next = NULL;
		}
	PolygonPtr [0] = Polygon;
	if (c != '\n')
		EndOfInputPtr [0] = 1;
	return ok;
	}


void Translate (long int * xPtr, long int * yPtr, long int * zPtr,
		int CameraX, int CameraY, int CameraZ)
	{
	xPtr [0] -= CameraX;
	yPtr [0] -= CameraY;
	zPtr [0] -= CameraZ;
	}


void Rotate (long int * xPtr, long int * yPtr, long int * zPtr,
		int RotateCosNumer, int RotateSinNumer, int RotateDenom)
	{
	int x, y, z;

	x = xPtr [0];
	y = yPtr [0];
	z = zPtr [0];
	xPtr [0] = x*RotateCosNumer - y*RotateSinNumer;
	yPtr [0] = x*RotateSinNumer + y*RotateCosNumer;
	zPtr [0] = z*RotateDenom;
	}


void Tilt (long int * xPtr, long int * yPtr, long int * zPtr,
		int TiltCosNumer, int TiltSinNumer, int TiltDenom)
	{
	int x, y, z;

	x = xPtr [0];
	y = yPtr [0];
	z = zPtr [0];
	xPtr [0] = x*TiltDenom;
	yPtr [0] = y*TiltCosNumer - z*TiltSinNumer;
	zPtr [0] = y*TiltSinNumer + z*TiltCosNumer;
	}


void Magnify (long int * xPtr, long int * yPtr, long int * zPtr,
		int magnification)
	{
	int scale;

	scale = 1;
	if (scale < yPtr [0]/LengthTarget)
		scale = (yPtr [0] + LengthTarget/2)/LengthTarget;
	xPtr [0] = (magnification*xPtr [0] + scale/2)/scale;
	yPtr [0] = (yPtr [0] + scale/2)/ scale;
	zPtr [0] = (magnification*zPtr [0] + scale/2)/scale;
	}



int ReadPolygons (struct Polygon * * PolygonsPtr)
	{
	struct Polygon * * PolygonPtr, * Polygon;
	int EndOfInput, LineNum, ok;

	PolygonPtr = PolygonsPtr;
	ok = 1;
	LineNum = 0;
	EndOfInput = 0 ;
	while (!EndOfInput) {
		LineNum++;
		if (!ReadPolygon (& Polygon, & EndOfInput) ) {
			fprintf (stderr, " in line %d.\n", LineNum);
			ok = 0;
			}
		if (Polygon != NULL) {
			PolygonPtr [0] = Polygon;
			PolygonPtr = & Polygon->next;
			}
		}
	return ok;
	}


int SetCamera (
		int * RotateCosNumerPtr,
		int * RotateSinNumerPtr,
		int * RotateDenomPtr,
		int * TiltCosNumerPtr,
		int * TiltSinNumerPtr,
		int * TiltDenomPtr,
		int x,
		int y,
		int z)
	{
	int RotateDenom, RotateDenom2;
	int TiltDenom, TiltDenom2;
	int TiltCosNumer, TiltCosNumer2, scale;
	int ScaledX, ScaledY, ScaledZ;

	if (x == 0 && y == 0) {
		fprintf (stderr, "***xyzproject: Camera and target must");
		fprintf (stderr, " not have same x and y.\n");
		return 0;
		}
	scale = 1;
	if (scale < x/LengthTarget)
		scale = x/LengthTarget;
	if (scale < - x/LengthTarget)
		scale = - x/LengthTarget;
	if (scale < y/LengthTarget)
		scale = y/LengthTarget;
	if (scale < - y/LengthTarget)
		scale = - y/LengthTarget;
	if (scale < z/LengthTarget)
		scale = z/LengthTarget;
	if (scale < - z/LengthTarget)
		scale = - z/LengthTarget;
	if (x > 0)
		ScaledX = (scale/2 + x)/scale;
	else
		ScaledX = - (scale/2 - x)/scale;
	if (y > 0)
		ScaledY = (scale/2 + y)/scale;
	else
		ScaledY = - (scale/2 - y)/scale;
	if (z > 0)
		ScaledZ = (scale/2 + z)/scale;
	else
		ScaledZ = - (scale/2 - z)/scale;
	RotateCosNumerPtr [0] = ScaledY;
	RotateSinNumerPtr [0] = ScaledX;
	RotateDenom2 = ScaledX*ScaledX + ScaledY*ScaledY;
	RotateDenom = 0;
	while (RotateDenom*(RotateDenom + 1)
			< RotateDenom2)
		RotateDenom++;
	RotateDenomPtr [0] = RotateDenom;
	TiltCosNumer2 = ScaledX*ScaledX + ScaledY*ScaledY;
	TiltCosNumer = 0;
	while (TiltCosNumer*(TiltCosNumer + 1) < TiltCosNumer2)
		TiltCosNumer++;
	TiltCosNumerPtr [0] = TiltCosNumer;
	TiltSinNumerPtr [0] = - ScaledZ;
	TiltDenom2
		= ScaledX*ScaledX + ScaledY*ScaledY + ScaledZ*ScaledZ;
	TiltDenom = 0;
	while (TiltDenom*(TiltDenom + 1)
			< TiltDenom2)
		TiltDenom++;
	TiltDenomPtr [0] = TiltDenom;
	return 1;
	}


void OrientPolygons (struct Polygon * Polygons,
		int CameraX, int CameraY, int CameraZ,
		int RotateCosNumer, int RotateSinNumer, int RotateDenom,
		int TiltCosNumer, int TiltSinNumer, int TiltDenom,
		int magnification)
	{
	struct Polygon * Polygon;
	struct Corner * Corner;

	Polygon = Polygons;
	while (Polygon != NULL) {
		Corner = Polygon->Corners;
		while (Corner != NULL) {
			Translate (& Corner->x, & Corner->y, & Corner->z,
					CameraX, CameraY, CameraZ);
			Rotate (& Corner->x, & Corner->y, & Corner->z,
				RotateCosNumer, RotateSinNumer, RotateDenom);
			Tilt (& Corner->x, & Corner->y, & Corner->z,
				TiltCosNumer, TiltSinNumer, TiltDenom);
			Magnify (& Corner->x, & Corner->y, & Corner->z,
					magnification);
			Corner = Corner->next;
			}
		Polygon = Polygon->next;
		}
	}


void DrawPolygons (struct Polygon * Polygons, int width, int height)
	{
	struct Polygon * Polygon;
	struct Corner * Corner;
	long int x1, y1, z1, x2, y2, z2, x, y, z;
	int i, j, NumCrossings;

	printf ("P6\n");
	printf ("%d %d\n", width, height);
	printf ("255\n");
	y = 1;
	for (i = 0; i < height; i++) {
		z = height/2 - i;
		for (j = 0; j < width; j++) {
			x = j - width/2;
			NumCrossings = 0;
			Polygon = Polygons;
			while (Polygon != NULL && NumCrossings == 0) {
				Corner = Polygon->Corners;
				while (Corner != NULL) {
					x1 = Corner->x;
					y1 = Corner->y;
					z1 = Corner->z;
					if (Corner->next == NULL) {
						x2 = Polygon->Corners->x;
						y2 = Polygon->Corners->y;
						z2 = Polygon->Corners->z;
						}
					else {
						x2 = Corner->next->x;
						y2 = Corner->next->y;
						z2 = Corner->next->z;
						}
					if (y*y1*z2 > y1*y2*z && y1*y2*z >= y*y2*z1) {
						if (x*(y1*z2 - y2*z1) >= y*(x1*z2 - x2*z1) + z*(x2*y1 - x1*y2) )
							NumCrossings++;
						}
					else if (y*y2*z1 > y1*y2*z && y1*y2*z >= y*y1*z2) {
						if (x*(y2*z1 - y1*z2) >= y*(x2*z1 - x1*z2) + z*(x1*y2 - x2*y1) )
							NumCrossings--;
						}
					Corner = Corner->next;
					}
				if (NumCrossings != 0) {
					putchar (Polygon->r);
					putchar (Polygon->g);
					putchar (Polygon->b);
					}
				Polygon = Polygon->next;
				}
			if (NumCrossings == 0) {
				putchar (BackgroundR);
				putchar (BackgroundG);
				putchar (BackgroundB);
				}
			}
		}
	}


void WritePolygons (struct Polygon * Polygons)
	{
	struct Polygon * Polygon;
	struct Corner * Corner;

	Polygon = Polygons;
	while (Polygon != NULL) {
		printf ("%d %d %d", Polygon->r, Polygon->g, Polygon->b);
		Corner = Polygon->Corners;
		while (Corner != NULL) {
			printf (" %ld,%ld,%ld", Corner->x, Corner->y, Corner->z);
			Corner = Corner->next;
			}
		printf ("\n");
		Polygon = Polygon->next;
		}
	}


void ClosePolygons (struct Polygon * Polygons)
	{
	struct Polygon * Polygon, * NextPolygon;
	struct Corner * Corner, * NextCorner;

	Polygon = Polygons;
	while (Polygon != NULL) {
		NextPolygon = Polygon->next;
		Corner = Polygon->Corners;
		while (Corner != NULL) {
			NextCorner = Corner->next;
			free (Corner);
			Corner = NextCorner;
			}
		free (Polygon);
		Polygon = NextPolygon;
		}
	}

int main (int argc, char * argv [] )
	{
	struct Polygon * Polygons;
	int CameraX, CameraY, CameraZ, TargetX, TargetY, TargetZ;
	int RotateCosNumer, RotateSinNumer, RotateDenom;
	int TiltCosNumer, TiltSinNumer, TiltDenom;
	int i, width, height, magnification, ok;
	char c;

	if (argc < 2) {
		for (i = 0; i < NumUsageLines; i++)
			printf ("%s\n", UsageLines [i] );
		}
	else if (argc == 6) {
		ok = 1;
		if (sscanf (argv [1], "%d,%d,%d%c",
				& CameraX, & CameraY, & CameraZ, & c) != 3) {
			fprintf (stderr, "***xyztoad: expecting x,y,z");
			fprintf (stderr, " camera position, found");
			fprintf (stderr, " \"%s\".\n", argv [1] );
			ok = 0;
			}
		if (sscanf (argv [2], "%d,%d,%d%c",
				& TargetX, & TargetY, & TargetZ, & c) != 3) {
			fprintf (stderr, "***xyztoad: expecting x,y,z");
			fprintf (stderr, " target position, found");
			fprintf (stderr, " \"%s\".\n", argv [2] );
			ok = 0;
			}
		if (sscanf (argv [3], "%d%c", & width, & c) != 1
				&& magnification > 0) {
			fprintf (stderr, "***xyzproject: expecting");
			fprintf (stderr, " width, found");
			fprintf (stderr, " \"%s\".\n", argv [3] );
			ok = 0;
			}
		if (sscanf (argv [4], "%d%c", & height, & c) != 1
				&& magnification > 0) {
			fprintf (stderr, "***xyzproject: expecting");
			fprintf (stderr, " height, found");
			fprintf (stderr, " \"%s\".\n", argv [3] );
			ok = 0;
			}
		if (sscanf (argv [5], "%d%c", & magnification, & c) != 1
				&& magnification > 0) {
			fprintf (stderr, "***xyzproject: expecting");
			fprintf (stderr, " magnification, found");
			fprintf (stderr, " \"%s\".\n", argv [3] );
			ok = 0;
			}
		if (ok) {
			Polygons = NULL;
			if (ReadPolygons (& Polygons) ) {
				if (SetCamera (
						& RotateCosNumer, & RotateSinNumer,
							& RotateDenom,
						& TiltCosNumer, & TiltSinNumer,
							& TiltDenom,
						TargetX - CameraX,
						TargetY - CameraY,
						TargetZ - CameraZ) ) {
					OrientPolygons (Polygons,
							CameraX, CameraY, CameraZ,
							RotateCosNumer, RotateSinNumer,
								RotateDenom,
							TiltCosNumer, TiltSinNumer,
								TiltDenom,
							magnification);
					DrawPolygons (Polygons, width, height);
					/* WritePolygons (Polygons); */
					}
				else
					WritePolygons (Polygons);
				}
			ClosePolygons (Polygons);
			}
		}
	else {
		fprintf (stderr, "Usage: xyzproject");
		fprintf (stderr, " (camera) (target) (width) (height) (magnification)\n");
		}
	return 0;
	}