====== StellarisWare Graphics Library Polygon ======

===== polygon.c =====

<code c>
//*****************************************************************************
//
// polygon.c - Routines for drawing and filling polygons.
//             Addition to StellarisWare library.
//
// Copyright (c) 2010 Mikk Leini, TUT Robotics Club NPO
//
// Polygon fill algorithm is based on Darel Rex Finley suggestions:
//   http://www.alienryderflex.com/polygon_fill
//
//*****************************************************************************

#include "driverlib/debug.h"
#include "grlib/grlib.h"

//*****************************************************************************
//
//! \addtogroup primitives_api
//! @{
//
//*****************************************************************************

//*****************************************************************************
//
//! Draws a polygon.
//!
//! \param pContext is a pointer to the drawing context to use.
//! \param pRect is a pointer to the array of structures containing the points
//! of the polygon.
//! \param ulNumPoints is a number of points in array.
//! \param bClosedLoop indicates wheter to draw line between the first and
//! the last point.
//!
//! This function draws lines between the consecutive points and if requiered
//! the line between the first and the last point.
//!
//! \return None.
//
//*****************************************************************************
void
GrPolyDraw(const tContext *pContext, const tPoint *pPoints, 
           unsigned long ulNumPoints, unsigned char ucClosedLoop)
{
	unsigned long ulIdx;

    //
    // Check the arguments.
    //
    ASSERT(pContext);
    ASSERT(pPoints);
	ASSERT(sNumPoints > (bClosedLoop ? 2 : 1));

	//
	// Draw the lines between points
	//
	for(ulIdx = 0; ulIdx < ulNumPoints - 1; ulIdx++)
	{
		GrLineDraw(pContext, pPoints[ulIdx].sX, pPoints[ulIdx].sY,
		           pPoints[ulIdx + 1].sX, pPoints[ulIdx + 1].sY);
	}

	//
	// Draw a closing line between first and last point?
	//
	if(ucClosedLoop)
	{
		GrLineDraw(pContext, pPoints[0].sX, pPoints[0].sY,
		           pPoints[ulNumPoints - 1].sX, pPoints[ulNumPoints - 1].sY);
	}
}

//*****************************************************************************
//
//! Draws a filled polygon.
//!
//! \param pContext is a pointer to the drawing context to use.
//! \param pRect is a pointer to the array of structures containing the points
//! of the polygon.
//! \param ulNumPoints is a number of points in array.
//!
//! This function fills a polygon specified by the consecutive points.
//!
//! The clipping of the polygon to the clipping rectangle is performed within
//! this routine;
//!
//! \return None.
//
//*****************************************************************************
void
GrPolyFill(const tContext *pContext, const tPoint *pPoints, 
           unsigned long ulNumPoints)
{    
	unsigned long ulIdx, ulIdx2;
	unsigned long ulNumNodes;
	short sY;
	short pNodeList[100];	
	short sSwap;

    //
    // Check the arguments.
    //
    ASSERT(pContext);
    ASSERT(pPoints);
 	ASSERT(sNumPoints > 2);

	//
	// Loop through the rows of the clipping area.
	//
	for(sY = pContext->sClipRegion.sYMin; sY <= pContext->sClipRegion.sYMax; sY++)
	{
		//
		// Build a list of nodes.
		//
  		ulNumNodes = 0;

		//
		// Search for X coordinates of polygons on the current row.
		//
		for(ulIdx = 0; ulIdx < ulNumPoints; ulIdx++)
		{
			//
			// Get the index of next point and wrap around points count.
			//
			ulIdx2 = (ulIdx + 1) % ulNumPoints;

			//
			// Check if the polygon line exists on the same row.
			//
			if(((pPoints[ulIdx].sY <  sY) && (pPoints[ulIdx2].sY >= sY)) ||
               ((pPoints[ulIdx].sY >= sY) && (pPoints[ulIdx2].sY <  sY)))
			{
				//
				// Make sure nodes list isn't overflowed.
				//
				if(ulNumNodes >= 100) break;

				//
				// Calculate the intersection point X coordinate
				// of the polygon edge.
				//
				pNodeList[ulNumNodes++] =
					(pPoints[ulIdx].sX + (sY - pPoints[ulIdx].sY) *
					(pPoints[ulIdx2].sX - pPoints[ulIdx].sX) /
					(pPoints[ulIdx2].sY - pPoints[ulIdx].sY));
			}
		}
	
		//
		// Sort the nodes, via a simple “Bubble” sort.
		//
		ulIdx = 0;

		while(ulIdx + 1 < ulNumNodes)
		{
			if(pNodeList[ulIdx] > pNodeList[ulIdx + 1])
			{
				sSwap = pNodeList[ulIdx];
				pNodeList[ulIdx] = pNodeList[ulIdx + 1];
				pNodeList[ulIdx + 1] = sSwap;

				if(ulIdx)
				{
					ulIdx--;
				}
			}
			else
			{
				ulIdx++;
			}
		}
	
		//
		// Fill the pixels between node pairs.
		//
		for(ulIdx = 0; ulIdx < ulNumNodes; ulIdx += 2)
		{
			//
			// Break when lines go out of clipping region.
			//
			if(pNodeList[ulIdx] > pContext->sClipRegion.sXMax) break;

			//
			// Skip when line ends before clipping region.
			//
			if(pNodeList[ulIdx + 1] < pContext->sClipRegion.sXMin) continue;
						
			//
			// Clip the line from left.
			//
			if(pNodeList[ulIdx] < pContext->sClipRegion.sXMin)
			{
				pNodeList[ulIdx] = pContext->sClipRegion.sXMin;
			}

			//
			// Clip the line from right.
			//
			if(pNodeList[ulIdx + 1] > pContext->sClipRegion.sXMax)
			{
				pNodeList[ulIdx + 1] = pContext->sClipRegion.sXMax;
			}

			//
			// Call the low level horizontal line drawing routine.
			//
			DpyLineDrawH(pContext->pDisplay, pNodeList[ulIdx],
			             pNodeList[ulIdx + 1], sY, pContext->ulForeground);
		}		
	}
}

//*****************************************************************************
//
//! Draws a triangle.
//!
//! \param pContext is a pointer to the drawing context to use.
//! \param pPoint1 is a pointer to the first point.
//! \param pPoint2 is a pointer to the second point.
//! \param pPoint3 is a pointer to the third point.
//!
//! This function draws a triangle specified by three points.
//!
//! \return None.
//
//*****************************************************************************
void
GrTriangleDraw(const tContext *pContext, const tPoint *pPoint1, 
               const tPoint *pPoint2, const tPoint *pPoint3)
{
	tPoint pPoints[3];

	pPoints[0] = *pPoint1;
	pPoints[1] = *pPoint2;
	pPoints[2] = *pPoint3;

	GrPolyDraw(pContext, pPoints, 3, 1);
}

//*****************************************************************************
//
//! Draws a filled triangle.
//!
//! \param pContext is a pointer to the drawing context to use.
//! \param pPoint1 is a pointer to the first point.
//! \param pPoint2 is a pointer to the second point.
//! \param pPoint3 is a pointer to the third point.
//!
//! This function fills a triangle specified by three points.
//!
//! \return None.
//
//*****************************************************************************
void
GrTriangleFill(const tContext *pContext, const tPoint *pPoint1, 
               const tPoint *pPoint2, const tPoint *pPoint3)
{
	tPoint pPoints[3];

	pPoints[0] = *pPoint1;
	pPoints[1] = *pPoint2;
	pPoints[2] = *pPoint3;

	GrPolyFill(pContext, pPoints, 3);
}

//*****************************************************************************
//
//! Draws a quad.
//!
//! \param pContext is a pointer to the drawing context to use.
//! \param pPoint1 is a pointer to the first point.
//! \param pPoint2 is a pointer to the second point.
//! \param pPoint3 is a pointer to the third point.
//! \param pPoint4 is a pointer to the fourth point.
//!
//! This function draws a quad specified by four points.
//!
//! \return None.
//
//*****************************************************************************
void
GrQuadDraw(const tContext *pContext, const tPoint *pPoint1, 
           const tPoint *pPoint2, const tPoint *pPoint3,
		   const tPoint *pPoint4)
{
	tPoint pPoints[4];

	pPoints[0] = *pPoint1;
	pPoints[1] = *pPoint2;
	pPoints[2] = *pPoint3;
	pPoints[3] = *pPoint4;

	GrPolyDraw(pContext, pPoints, 4, 1);
}

//*****************************************************************************
//
//! Draws a filled quad.
//!
//! \param pContext is a pointer to the drawing context to use.
//! \param pPoint1 is a pointer to the first point.
//! \param pPoint2 is a pointer to the second point.
//! \param pPoint3 is a pointer to the third point.
//! \param pPoint4 is a pointer to the fourth point.
//!
//! This function fills a quad specified by four points.
//!
//! The clipping of the polygon to the clipping rectangle is performed within
//! this routine;
//!
//! \return None.
//
//*****************************************************************************
void
GrQuadFill(const tContext *pContext, const tPoint *pPoint1, 
           const tPoint *pPoint2, const tPoint *pPoint3,
		   const tPoint *pPoint4)
{
	tPoint pPoints[4];

	pPoints[0] = *pPoint1;
	pPoints[1] = *pPoint2;
	pPoints[2] = *pPoint3;
	pPoints[3] = *pPoint4;

	GrPolyFill(pContext, pPoints, 4);
}

//*****************************************************************************
//
// Close the Doxygen group.
//! @}
//
//*****************************************************************************
</code>

===== grlib.h =====

<code c>
//*****************************************************************************
//
//! This structure defines the point.
//
//*****************************************************************************
typedef struct
{
    //
    //! The X coordinate of the point.
    //
    short sX;

    //
    //! The Y coordinate of the point.
    //
    short sY;
}
tPoint;

// Add these also:

extern void GrPolyDraw(const tContext *pContext, const tPoint *pPoints, 
           unsigned long ulNumPoints, unsigned char ucClosedLoop);
extern void GrPolyFill(const tContext *pContext, const tPoint *pPoints, 
           unsigned long ulNumPoints);
extern void GrTriangleDraw(const tContext *pContext, const tPoint *pPoint1, 
               const tPoint *pPoint2, const tPoint *pPoint3);
extern void GrTriangleFill(const tContext *pContext, const tPoint *pPoint1, 
               const tPoint *pPoint2, const tPoint *pPoint3);
extern void GrQuadDraw(const tContext *pContext, const tPoint *pPoint1, 
           const tPoint *pPoint2, const tPoint *pPoint3,
		   const tPoint *pPoint4);
extern void GrQuadFill(const tContext *pContext, const tPoint *pPoint1, 
           const tPoint *pPoint2, const tPoint *pPoint3,
		   const tPoint *pPoint4);

</code>