/******************************************************************************
 * OCTANT.C														\ 3 | 2 /
 * This group of routines draws a line using the Octantal		 \	|  /
 * Digital Differential Analyser algorithm described on page	4 \ | / 1
 * 25 of "Microcomputer Displays, Graphics and Animation". Its     \|/
 * advantage over the system line drawing routines is that it  -----+-----
 * saves the color register values of the pixels that it draws	   /|\
 * over, so that they can be restored as the line is erased.	5 / | \ 8
 *																 /	|  \
 * These routines are optimized for speed not compactness.		/ 6 | 7	\
 * When a line is drawn, the original pixels and their coordinates are saved.
 * Thus, the line can be erased rather quickly but severl K of ram can be 
 * required. If necessary, the line drawing speed can be increased some what
 * by including the plot() routine as in line code of the octant routines,
 * thus eliminating the function call overhead.
 *
 * These routines do not perform clipping.
 *
 * For normal use, the entry points to this file are draw_line() and
 * restore_line().
 *
 ******************************************************************************/


/* Some of these include files are not necessary.	*/

#include	<functions.h>
#include	<exec/types.h>
#include 	<exec/nodes.h>
#include	<exec/memory.h>
#include	<exec/libraries.h>
#include	<graphics/gfx.h>
#include	<graphics/rastport.h>
#include	<intuition/intuitionbase.h>
#include 	<stdio.h>
/* #include	<exec/tasks.h>			*/
/* #include	<graphics/text.h>		*/


/* This struct keeps track of the image pixels blotted out by the line	*/

static struct saved_line
{
	struct RastPort	*RPort;		/* RastPort the line was drawn in.		*/
	UBYTE			*storage;	/* Color registers of drawn over pixels	*/
	USHORT			*x;			/* X screen coordinates of line points.	*/
	USHORT			*y;			/* Y screen coordinates of line points.	*/
	USHORT			points;		/* Num of elements in the allocated		*/
}line;							/* array. Eq the max index plus 1.		*/

/************************  Error messages  ************************************/

static char alloc_err[] = "Can't alloc pixel arrays.";
static char rp_err[]	= "ERROR READING PIXEL";
static char wp_err[]	= "ERROR WRITINGING PIXEL";
static char line_err[]	= "Plot() called before array allocation.";
static char rest_err[]	= "Tried to restore nonexistant line.";

/*****************************************************************************
 * Allocate arrays pointed to by members of the save_line structure and init 
 * the struct members. Arrays are allocated from Fast RAM if possible.
 *****************************************************************************/

static alloc_line(RPort, length)
struct RastPort	*RPort;
short			length;				/* Number of pixels in the line.	*/
{
ULONG	size;

size = length * sizeof(*line.storage);
line.storage = (UBYTE *)AllocMem(size, MEMF_CLEAR | MEMF_PUBLIC);

size	= length * sizeof(*line.x);
line.x	= (USHORT *)AllocMem(size, MEMF_CLEAR | MEMF_PUBLIC);
line.y	= (USHORT *)AllocMem(size, MEMF_CLEAR | MEMF_PUBLIC);


if (line.storage == NULL || line.x == NULL || line.y == NULL)
{
	free_line();
	return(FALSE);
}
line.RPort  = RPort;
line.points = length;	/* This value can't be altered til arrays are freed. */

return(TRUE);

} /*  End of alloc_line()	*/


/******************************************************************************
 * Release arrays pointed to by members of the line struct.
 ******************************************************************************/

static free_line()
{

if (line.storage)
{
	FreeMem(line.storage, (long)line.points * sizeof(*line.storage) );
	line.storage = NULL;
}
if (line.x)
{
	FreeMem(line.x, (long)line.points * sizeof(*line.x) );
	line.x = NULL;
}
if (line.y)
{
	FreeMem(line.y, (long)line.points * sizeof(*line.y) );
	line.y = NULL;
}
line.RPort	= NULL;
line.points	= 0;

return;

} /*  End of free_line()  */


/******************************************************************************
 * Save image pixel and replace it with a line pixel. This routine does not 
 * waste time checking index to see if it is within the range of the allocated
 * array. The client routine better not fuck up the index calculation.
 ******************************************************************************/

static plot(index, x, y)
short		index, x, y;
{
long		result;

if (!line.points)					/* A major error.	*/
{
	puts(line_err);
	return(FALSE);
}
result = ReadPixel(line.RPort, (long)x, (long)y );

line.storage[index] = result;
line.x[index]		= x;
line.y[index]		= y;

WritePixel(line.RPort, (long)x, (long)y );

} /*  End of plot()  */


/******************************************************************************
 * First (and fourth) octant.     Dy < 0       |Dy| < |Dx|
 ******************************************************************************/

static octant1(RPort, x, y, deltax, deltay)
struct RastPort	*RPort;
short			x, y, deltax, deltay;
{
register short countdown;	/* Number of pixels still to be drawn.	*/
register short err;			/* Running error term.					*/
register short index;		/* Index of current point.				*/

countdown	= deltax + 1;
err			= -deltax / 2;	/* err starts out being less than zero.	*/
index		= 0;

if ( !alloc_line(RPort, countdown) )
{
	puts(alloc_err);
	return(FALSE);
}

/*----------------------------------------------------------------------*
 * While there are more points to plot... There must be something wrong
 * with an algorythm that requires both assending and decending counters.
 *----------------------------------------------------------------------*/

while (countdown--)
{
	plot(index++, x++, y);
	err -= deltay;			/* err gradually becomes positive.	*/
	if (err >= 0)
	{
		--y;				/* Moving up screen.				*/
		err -= deltax;		/* err goes negative again.			*/
	}
}
return(TRUE);

} /*  End of octant1()  */


/*****************************************************************************
 * Second (and third) octant.		|Dy| > |Dx|
 *****************************************************************************/

static octant2(RPort, x, y, deltax, deltay)
struct RastPort	*RPort;
short			x, y, deltax, deltay;
{
register short countdown;	/* Number of pixels still to be drawn.	*/
register short err;			/* Running error term.					*/
register short index;		/* Index of current point.				*/

countdown	= -deltay + 1;
err			= deltay / 2;
index		= 0;

if ( !alloc_line(RPort, countdown) )
{
	puts(alloc_err);
	return(FALSE);
}
while (countdown--)
{
	plot(index++, x, y--);
	err += deltax;			/* err growing positive.	*/
	if (err >= 0)
	{
		++x;
		err += deltay;		/* err goes negative.		*/
	}
}
return(TRUE);

} /*  End of octant2()  */


/******************************************************************************
 * Seventh (and sixth) octant.   Dy > Dx > 0
 ******************************************************************************/

static octant7(RPort, x, y, deltax, deltay)
struct RastPort	*RPort;
short			x, y, deltax, deltay;
{
register short countdown;	/* Number of pixels still to be drawn.	*/
register short err;			/* Running error term.					*/
register short index;		/* Index of current point.				*/

countdown	= deltay + 1;
err			= -deltay / 2;
index		= 0;

if ( !alloc_line(RPort, countdown) )
{
	puts(alloc_err);
	return(FALSE);
}
while (countdown--)
{
	plot(index++, x, y++);
	err += deltax;			/* err growing positive	*/
	if (err >= 0)
	{
		++x;
		err -= deltay;		/* err goes negative.	*/
	}
}
return(TRUE);

} /*  End of octant7()  */


/*****************************************************************************
 * Eighth (and fifth) octant.      Dx > Dy > 0.
 *****************************************************************************/

static octant8(RPort, x, y, deltax, deltay)
struct RastPort	*RPort;
short			x, y, deltax, deltay;
{
register short countdown;	/* Number of pixels still to be drawn.	*/
register short err;			/* Running error term.					*/
register short index;		/* Index of current point.				*/

countdown	= deltax + 1;
err			= -deltax / 2;
index		= 0;

if ( !alloc_line(RPort, countdown) )
{
	puts(alloc_err);
	return(FALSE);
}
while (countdown--)
{
	plot(index++, x++, y);	/* Moving left to right.	*/
	err += deltay;			/* err growing positive.	*/
	if (err >= 0)
	{
		++y;				/* Move down screen next time.	*/
		err -= deltax;		/* err goes negative.		*/
	}
}
return(TRUE);

} /*  End of octant8()  */


/*****************************************************************************
 *	A quicker vertical line stroker. The end point supplied by client must be
 *  the one with the smallest y value.
 *****************************************************************************/

static vert_line(RPort, x, y, len)
struct RastPort	*RPort;
short			x, y, len;
{

register short index;		/* Index of current point.				*/

index = 0;

if ( !alloc_line(RPort, len) )
{
	puts(alloc_err);
	return(FALSE);
}
while (index < len)
	plot(index++, x, y++);

return(TRUE);

} /*  End of vert_line()  */


/*****************************************************************************
 * Quick horizontal line draw. The end point supplied must be the one with 
 * the smallest x value.
 *****************************************************************************/

static horiz_line(RPort, x, y, len)
struct RastPort	*RPort;
USHORT			x, y, len;
{

register USHORT index;		/* Index of current point.				*/

index = 0;

if ( !alloc_line(RPort, len) )
{
	puts(alloc_err);
	return(FALSE);
}

while (index < len)
	plot(index++, x++, y);

return(TRUE);

} /*  End of horiz_line()  */


/*****************************************************************************
 * Quicker diagonal line drawer. For line with a negative slope
 *****************************************************************************/

static diagdn_line(RPort, x, y, len)
struct RastPort	*RPort;
short			x, y, len;
{

register short index;		/* Index of current point.				*/

index		= 0;

if ( !alloc_line(RPort, len) )
{
	puts(alloc_err);
	return(0);
}

while (index < len)
	plot(index++, x++, y++);

return(1);

} /*  End of diagdn_line()  */


/*****************************************************************************
 * Quicker diagonal line drawer. For line with a positive slope
 *****************************************************************************/

static diagup_line(RPort, x, y, len)
struct RastPort	*RPort;
short			x, y, len;
{

register short index;		/* Index of current point.				*/

index = 0;

if ( !alloc_line(RPort, len) )
{
	puts(alloc_err);
	return(FALSE);
}

while (index < len)
	plot(index++, x++, y--);

return(TRUE);

} /*  End of diagup_line()  */


/******************************************************************************
 * This function is the normal entry point for line drawing. It determins 
 * which octant the line is in and calls the appropriate line drawing routine.
 * the screen's coordinate system is used. Thus, Y values increase as you move
 * down the screen. Lines are always drawn from left to right, swapping end
 * points if necessary.
 *
 *	RPort		Pointer to the RastPort of the window being drawn in.
 *  (x1, y1)	First end point.
 *  (x2, y2)	Other end point.
 *
 ******************************************************************************/

draw_line(RPort, color, x1, y1, x2, y2)
struct RastPort	*RPort;
USHORT			color;
USHORT			x1, y1, x2, y2;
{

short			deltax, deltay;
short			rc;
short			temp;
BYTE			save_color;

if (x1 > x2)
{
	temp = x1;	x1 = x2;  x2 = temp;
	temp = y1;	y1 = y2;  y2 = temp;
}
deltax = x2 - x1;
deltay = y2 - y1;

save_color = RPort->FgPen;			/* Save pen color for later restoration. */
SetAPen(RPort, (long)color);

/* Trap hoizontal and vertical lines for special treatment.	*/

if (!deltay)
{
	rc = horiz_line(RPort, x1, y1, deltax + 1);
}
else if (!deltax)
{
	if (deltay > 0)
		rc = vert_line(RPort, x1, y1, deltay + 1);
	else
		rc = vert_line(RPort, x2, y2, 1 - deltay);
}
else if (deltay > 0)								/* Fourth Quadrant	*/
{
	if (deltax == deltay)
		rc = diagdn_line(RPort, x1, y1, deltax + 1);
	else if (deltay > deltax)
		rc = octant7(RPort, x1, y1, deltax, deltay);
	else
		rc = octant8(RPort, x1, y1, deltax, deltay);
}
else												/* First Quadrant	*/
{
	if ( !(deltax + deltay) )
		rc = diagup_line(RPort, x1, y1, deltax + 1);
	else if (-deltay > deltax)
		rc = octant2(RPort, x1, y1, deltax, deltay);
	else
		rc = octant1(RPort, x1, y1, deltax, deltay);
}

SetAPen(RPort, (long)save_color);	/* Restore original pen color. */

return(rc);

} /*  End of draw_line()  */


/******************************************************************************
 * Restore image pixels that have been overdrawn by the line. This is the 
 * entry point for line erasure. This routine can not mess with the value of 
 * line.points because it will be needed to release the arrays. Note that if
 * line.points is initially zero, this routine is a nop.
 ******************************************************************************/

restore_line()
{
register short	index;
BYTE			save_color;

if (!line.points)
{
	puts(rest_err);
	return(FALSE);
}

save_color = line.RPort->FgPen;

index = line.points;		/* Index of last point + 1.	*/

while (index--)
{
	SetAPen(line.RPort, (ULONG)line.storage[index] );

	/* if (!line.x[index]) puts("Restored point with zero X value."); */

	WritePixel(line.RPort, (ULONG)line.x[index], (ULONG)line.y[index] );
}
SetAPen(line.RPort, (ULONG)save_color);
free_line();

} /*  End of restore_line()  */