/*
 * $Id: selection.c 195 2005-10-28 15:08:07Z hderuiter $
 *
 * $Date: 2005-10-28 10:08:07 $
 * $Revision: 195 $
 *
 * (C) 1999 by Hans de Ruiter
 * All rights reserved
 *
 * This file is part of the MiniGL library project
 * See the file Licence.txt for more details
 *
 */

#include "sysinc.h"
#include "displaylists.h"
#include "hclip.h"
#include "selection.h"
#include "util.h"
#include <math.h>

#define min(x,y) (x) < (y) ? (x) : (y)
#define max(x,y) (x) > (y) ? (x) : (y)

// ----- DATATYPES -----

typedef struct SelectionHitHeader_s
{
	GLuint numNames; // the number of names that were in the stack
	GLuint minDepth;
	GLuint maxDepth;
} SelectionHitHeader;

// ----- FUNCTION PROTOTYPES -----

extern void    m_CombineMatrices(GLcontext context);
extern void    v_GenEyeCoords(GLcontext context);
extern GLfloat v_PolygonOffset(GLcontext context, int v1, int v2, int v3);
extern GLfloat dh_AreaSign(GLcontext context, MGLPolygon *poly);

/** Initialises the given SelectionHitHeader for a new hit
 */
void selectionNewHit(struct GLcontext_t *context, SelectionHitHeader *newHeader);

/** Adds a vertex to the selection hit header data. Call this for every vertex added.
 */
void selectionHitAddVertex(struct GLcontext_t *context, SelectionHitHeader *hitHeader, MGLVertex *vertex);

/** Writes the given selection hit to the selection buffer.
 * This will automatically discard invalid hits (i.e., hits with no vertices recorded.
 */
void selectionWriteHit(struct GLcontext_t *context, SelectionHitHeader *hitHeader);

INLINE void selection_v_Transform(GLcontext context);
void s_DrawPoly(GLcontext context, MGLPolygon *poly, SelectionHitHeader *hitHeader);
void s_DrawPolyFF(GLcontext context, MGLPolygon *poly, SelectionHitHeader *hitHeader);
void s_DrawLine(GLcontext context, MGLPolygon *poly, SelectionHitHeader *hitHeader);
INLINE void selection_v_ToScreen(GLcontext context, int i);

// ----- PUBLIC FUNCTIONS -----

void cgl_GLInitNames(struct GLContextIFace *Self) {
	GLcontext context = GET_INSTANCE(Self);

	DL_CHECK(InitNames(Self))
	// Make sure that we're not between glBegin()/glEnd() calls
	if (context->CurrentPrimitive != GL_BASE) {
		context->CurrentError = GL_INVALID_OPERATION;
		return;
	}

	if (context->renderMode == GL_SELECT) {
		context->nameStackPointer = NAMESTACK_EMPTY;
	}
}

void cgl_GLLoadName(struct GLContextIFace *Self, GLuint name) {
	GLcontext context = GET_INSTANCE(Self);

	DL_CHECK(LoadName(Self, name))

	// Make sure that we're not between glBegin()/glEnd() calls
	if (context->CurrentPrimitive != GL_BASE) {
		context->CurrentError = GL_INVALID_OPERATION;
		return;
	}

	if (context->renderMode != GL_SELECT) {
		return;
	}

	// This call fails if the stack is empty
	if (context->nameStackPointer == NAMESTACK_EMPTY) {
		context->CurrentError = GL_INVALID_OPERATION;
		return;
	}
	else if (context->nameStackPointer >= NAME_STACK_SIZE) {
		dprintf("%s internal error: name stack pointer was above the maximum stack size.\n", __func__);
	}

	context->nameStack[context->nameStackPointer] = name;
}

void cgl_GLPushName(struct GLContextIFace *Self, GLuint name) {
	GLcontext context = GET_INSTANCE(Self);

	DL_CHECK(PushName(Self, name))

	// Make sure that we're not between glBegin()/glEnd() calls
	if (context->CurrentPrimitive != GL_BASE) {
		context->CurrentError = GL_INVALID_OPERATION;
		return;
	}

	if (context->renderMode != GL_SELECT) {
		return;
	}

	if (context->nameStackPointer == NAMESTACK_EMPTY) {
		context->nameStackPointer = 0;
	}
	else {
		if (context->nameStackPointer >= NAME_STACK_SIZE - 1) {
			context->CurrentError = GL_STACK_OVERFLOW;
			return;
		}
		++(context->nameStackPointer);
	}

	context->nameStack[context->nameStackPointer] = name;
}

void cgl_GLPopName(struct GLContextIFace *Self) {
	GLcontext context = GET_INSTANCE(Self);

	DL_CHECK(PopName(Self))
    // Make sure that we're not between glBegin()/glEnd() calls
	if (context->CurrentPrimitive != GL_BASE) {
		context->CurrentError = GL_INVALID_OPERATION;
		return;
	}

	if (context->renderMode != GL_SELECT) {
		return;
	}

	if (context->nameStackPointer == NAMESTACK_EMPTY) {
		context->CurrentError = GL_STACK_UNDERFLOW;
		return;
	}

	if (context->nameStackPointer < 1) {
		context->nameStackPointer = NAMESTACK_EMPTY;
	}
	else {
		--context->nameStackPointer;
	}
}

void cgl_GLSelectBuffer(struct GLContextIFace *Self, GLsizei size, GLuint *buffer) {
	GLcontext context = GET_INSTANCE(Self);

	// NOTE: This command is never added to a display-list so DO NOT add any display-list code here

	// Make sure that we're not between glBegin()/glEnd() calls
	if (context->CurrentPrimitive != GL_BASE || context->renderMode == GL_SELECT) {
		context->CurrentError = GL_INVALID_OPERATION;
		return;
	}

	GLFlagError(context, size < 0, GL_INVALID_VALUE);

	context->selectionBuffer = buffer;
	context->selectionBufferSize = size;
	context->selectionBufferPointer = 0;
	context->selectionBufferOverflow = TRUE;
	context->selectionNumHits = 0;
}

GLint cgl_GLRenderMode(struct GLContextIFace *Self, GLenum mode) {
	GLcontext context = GET_INSTANCE(Self);
	GLint retVal;

	// NOTE: This command is never added to a display-list so DO NOT add any display-list code here

	// Make sure that we're not between glBegin()/glEnd() calls
	if (context->CurrentPrimitive != GL_BASE) {
		context->CurrentError = GL_INVALID_OPERATION;
		return 0;
	}

	switch (context->renderMode) {
		case GL_SELECT:
			if (context->selectionBufferOverflow) {
				retVal = -context->selectionNumHits;
			}
			else {
				retVal = context->selectionNumHits;
			}
			break;

		case GL_FEEDBACK:
			// not implemented yet
			retVal = 0;
			break;
		case GL_RENDER:
		default:
			retVal = 0;
	}

	switch (mode) {
		case GL_RENDER:
			break;

		case GL_SELECT:
			if (context->selectionBuffer == NULL || context->renderMode == GL_SELECT) {
				context->CurrentError = GL_INVALID_OPERATION;
				return 0;
			}
			context->nameStackPointer = NAMESTACK_EMPTY;
			context->selectionBufferPointer = 0;
			context->selectionNumHits = 0;
			context->selectionBufferOverflow = FALSE;
			break;

		case GL_FEEDBACK:
			if (context->renderMode == GL_FEEDBACK) {
				context->CurrentError = GL_INVALID_OPERATION;
				return 0;
			}
			else {
				// not implemented yet
				dprintf("%s: Feedback render mode is not implemented yet\n", __func__);
				context->CurrentError = GL_INVALID_ENUM;
				return 0;
			}
			break;

		default:
			context->CurrentError = GL_INVALID_ENUM;
			return 0;
	}

	if (mode != GL_SELECT) {
		context->nameStackPointer = NAMESTACK_EMPTY;
	}

	context->renderMode = mode;

	return retVal;
}


// ---- SELECTION VERSIONS OF DRAW FUNCTIONS ----

void s_DrawPoints(struct GLcontext_t *context)
{
	int i;
	uint32 *idx = (uint32 *)context->IndexBuffer;
	uint32 num = 0;

	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

	selection_v_Transform(context);
	for (i=0; i<context->VertexBufferPointer; i++) {
		/* First of all, code the point and see if it is inside */
		hc_CodePoint(context, &(context->VertexBuffer[i]));
		if (context->VertexBuffer[i].outcode == 0) {
			/* Any point inside the clip volume is added to the index array */
			*idx++ = i;
			num++;
			selection_v_ToScreen(context, i);
		}
	}

	if (num != 0) {
		// Anything left after clipping?
		if (num < context->VertexBufferPointer - 1) {
			// Draw indexed, some points are off
			for (i=0; i<num; i++) {
				selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[context->IndexBuffer[i]]));
			}
		}
		else {
			// Draw in one go, all of them are onscreen
			for (i=0; i<num; i++) {
				selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i]));
			}
		}
	}
	selectionWriteHit(context, &hitHeader);
}

void s_DrawLines(struct GLcontext_t *context)
{
	int i;
	GLuint or_code, and_code;
	selection_v_Transform(context);

	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

	for (i=0; i<context->VertexBufferPointer; i+=2) {
		hc_CodePoint(context, &(context->VertexBuffer[i]));
		hc_CodePoint(context, &(context->VertexBuffer[i+1]));

		and_code = context->VertexBuffer[i+0].outcode & context->VertexBuffer[i+1].outcode;

		if (and_code) {
			continue;
		}

		or_code = context->VertexBuffer[i+0].outcode | context->VertexBuffer[i+1].outcode;

		if (or_code == 0) {
			selection_v_ToScreen(context, i);
			selection_v_ToScreen(context, i+1);

			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+1]));
		}
		else {
			MGLPolygon p;
			uint32 pts[2];

			pts[0] = i;
			pts[1] = i+1;
			if (GL_FALSE == hc_LineClip(context, pts)) {
				return; // rejected
			}
			p.numverts = 2;
			p.verts[0] = pts[0];
			p.verts[1] = pts[1];
			s_DrawLine(context,&p, &hitHeader);
		}
	}

	selectionWriteHit(context, &hitHeader);
}

#define NEXT_IDX(a) (((a)+1)%context->VertexBufferPointer)
#define PREV_IDX(a) ((a) == 0?context->VertexBufferPointer-1:(a)-1)

#define IS_INSIDE(a) ((a) == 0)
#define IS_OUTSIDE(a) ((a) != 0)

void s_DrawLineStrip(struct GLcontext_t *context)
{
	int i;
	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

	GLuint or_code, and_code;
	selection_v_Transform(context);

	or_code  = 0;
	and_code = 0;

	for (int i=0; i<context->VertexBufferPointer; i++) {
		hc_CodePoint(context, &(context->VertexBuffer[i]));
		or_code  |= context->VertexBuffer[i+0].outcode;
		and_code &= context->VertexBuffer[i+0].outcode;
	}

	if (and_code) {
		return;
	}

	if (or_code == 0) {
		// nice case - everything is on-screen
		for (int i = 0; i < context->VertexBufferPointer; i++) {
			selection_v_ToScreen(context, i);
		}
		for (i=0; i<context->VertexBufferPointer; i++) {
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i]));
		}
	}
	else {
		/*
		 * If there is at least one vertex outside the screen, we need to draw
		 * the whole loop/strip as a series of line strips. We start at the
		 * first vertex (or the last vertex if it is a loop) and move along
		 * the lines of the strip, adding points to the index array as we
		 * go.
		 */
		int count = 0; // Number of points in the current loop.
		int currentIndex;
		int primSize = context->VertexBufferPointer;
		if (context->CurrentPrimitive == GL_LINE_LOOP) {
			currentIndex = primSize-1;
		}
		else {
			currentIndex = 0;
		}
		/*
		 * If the starting point is on-screen, we output it prior to the
		 * inner loop, because we will always add endpoints of the line.
		 */
		if (context->VertexBuffer[currentIndex].outcode == 0) {
			context->IndexBuffer[count] = currentIndex;
			selection_v_ToScreen(context, currentIndex);
			count++;
		}

		currentIndex = NEXT_IDX(currentIndex);

		//while (currentIndex < primSize)
		for (int vtxcount = 0; vtxcount < primSize; vtxcount++) {
			/*
			 * The inner loop starts here
			 * There are four cases we have to take care of
			 * 1) we are outside and stay outside
			 * 2) we are outside but pass into the inside
			 * 3) we are inside and stay inside
			 * 4) we are inside and pass into the outside
			 *
			 * if 1) do nothing
			 * if 2) clip the line segment, adding the new point as the
			 *               start of a new loop
			 * if 3) add the current point to the line loop
			 * if 4) clip the line segment, the add new (clipped) point to the
			 * output, then draw it.
			 *
			 * There is actually one more case which is borderline - the place
			 * when we hit the end of the actual loop/strip. This is not
			 * strictly part of the inner loop, and hence will be handled after
			 * the end of the while loop if there is an incomplete strip
			 * waiting.
			 *
			 * Note that the points we usually add are the endpoints of the
			 * line segments.
			 */
			int thisOutcode = context->VertexBuffer[currentIndex].outcode;
			int prevOutcode = context->VertexBuffer[PREV_IDX(currentIndex)].outcode;
			// we don't handle case 1. There is nothing to do but increment
			// the counter

			if (IS_OUTSIDE(prevOutcode) && IS_INSIDE(thisOutcode)) {
				// case 2
#ifdef OBSOLETE_CODE
				uint32 out1 = 0, out2 = 0;
				MGLPolygon line;
				line.verts[0] = currentIndex;
				line.verts[1] = PREV_IDX(currentIndex);
				line.numverts = 2;
				hc_ClipLine(context, &line, thisOutcode | prevOutcode, &out1, &out2);
#endif
				uint32 pts[2];
				pts[0] = currentIndex;
				pts[1] = PREV_IDX(currentIndex);
				// can ignore result - this is never rejected completely
				hc_LineClip(context, pts);
				uint32 out1 = pts[0];
				uint32 out2 = pts[1];
				count = 0; // start a new strip here

				// add the clipped point...
				if (out1 >= primSize) {
					// out1 is new
					context->IndexBuffer[count]  = out1;
					context->VertexBufferPointer = MAX(context->VertexBufferPointer, out1+1);
					selection_v_ToScreen(context, out1);
				}
				else {
					context->IndexBuffer[count]  = out2;
					context->VertexBufferPointer = MAX(context->VertexBufferPointer, out2+1);
					selection_v_ToScreen(context, out2);
				}

				count++;

				// ... and the endpoint
				context->IndexBuffer[count] = currentIndex;
				selection_v_ToScreen(context, currentIndex);
				count++;
			}
			else if (IS_INSIDE(prevOutcode) && IS_INSIDE(thisOutcode)) {
				// case 3
				context->IndexBuffer[count] = currentIndex;
				selection_v_ToScreen(context, currentIndex);
				count++;
			}
			else if (IS_INSIDE(prevOutcode) && IS_OUTSIDE(thisOutcode)) {
				// case 4
#ifdef OBSOLETE_CODE
				uint32 out1 = 0, out2 = 0;
				MGLPolygon line;
				line.verts[0] = currentIndex;
				line.verts[1] = PREV_IDX(currentIndex);
				line.numverts = 2;
				hc_ClipLine(context, &line, thisOutcode | prevOutcode, &out1, &out2);
#endif

				uint32 pts[2];
				pts[0] = currentIndex;
				pts[1] = PREV_IDX(currentIndex);
				// can ignore result - this is never rejected completely
				hc_LineClip(context, pts);
				uint32 out1 = pts[0];
				uint32 out2 = pts[1];
				// add the clipped point
				if (out1 >= primSize) {
					// out1 is new
					context->IndexBuffer[count]  = out1;
					context->VertexBufferPointer = MAX(context->VertexBufferPointer, out1+1);
					selection_v_ToScreen(context, out1);
				}
				else {
					context->IndexBuffer[count]  = out2;
					context->VertexBufferPointer = MAX(context->VertexBufferPointer, out2+1);
					selection_v_ToScreen(context, out2);
				}

				count++;
				// draw the strip
				for (i=0; i<count; i++) {
					selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i]));
				}

				count = 0;
			}
			else {
				uint32 and_code = prevOutcode & thisOutcode;
				if (!and_code) {
					int prev = PREV_IDX(currentIndex);
					MGLPolygon p;
					uint32 pts[2];

					pts[0] = MIN(currentIndex, prev);
					pts[1] = MAX(currentIndex, prev);
					if (GL_FALSE == hc_LineClip(context, pts)) return; // rejected
					p.numverts = 2;
					p.verts[0] = pts[0];
					p.verts[1] = pts[1];
					s_DrawLine(context,&p, &hitHeader);
				}
			}

			currentIndex = NEXT_IDX(currentIndex);
			//if (currentIndex == primSize/*-1*/) break;
		}

		if (count) {
			for (i=0; i<count; i++) {
				selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i]));
			}
		}
	}

	selectionWriteHit(context, &hitHeader);
}

#define CLIP_EPS (1e-7)

void s_DrawTriangles(struct GLcontext_t *context)
{
	int i;
	GLuint or_code, and_code;

	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

/* FIXME: Use an approach similar to strips/fans: Gather as many triangles as
 * possible (i.e. visible, non-clipped) and draw them in one go
 */
	selection_v_Transform(context);

	for (i=0; i<context->VertexBufferPointer; i+=3) {
		hc_CodePoint(context, &(context->VertexBuffer[i]));
		hc_CodePoint(context, &(context->VertexBuffer[i+1]));
		hc_CodePoint(context, &(context->VertexBuffer[i+2]));

		and_code = context->VertexBuffer[i+0].outcode
		         & context->VertexBuffer[i+1].outcode
		         & context->VertexBuffer[i+2].outcode;
		if (and_code) {
			continue;
		}

		or_code = context->VertexBuffer[i+0].outcode
		        | context->VertexBuffer[i+1].outcode
		        | context->VertexBuffer[i+2].outcode;

		if (
			hc_DecideFrontface(
				context, &(context->VertexBuffer[i]),
				&(context->VertexBuffer[i+1]),
				&(context->VertexBuffer[i+2]),
				or_code
			) == GL_FALSE
		) {
			continue;
		}

		if (or_code == 0) {
			selection_v_ToScreen(context, i);
			selection_v_ToScreen(context, i+1);
			selection_v_ToScreen(context, i+2);

			if (context->enable.PolygonOffsetFill) {
				GLfloat offset = v_PolygonOffset(context, i, i+1, i+2);
				context->VertexBuffer[i].z += offset;
				context->VertexBuffer[i+1].z += offset;
				context->VertexBuffer[i+2].z += offset;
			}

			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+1]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+2]));

		}
		else {
			MGLPolygon poly;
			poly.numverts = 3;
			poly.verts[0] = i;
			poly.verts[1] = i+1;
			poly.verts[2] = i+2;

			if (context->enable.PolygonOffsetFill) {
				GLfloat offset = v_PolygonOffset(context, i, i+1, i+2);
				context->VertexBuffer[i].z += offset;
				context->VertexBuffer[i+1].z += offset;
				context->VertexBuffer[i+2].z += offset;
			}

			MGLPolygon *clippedPoly, temp;
			if (hc_ClipPoly(context, &poly, or_code, &clippedPoly, &temp) == GL_TRUE) {
				s_DrawPoly(context, clippedPoly, &hitHeader);
			}
		}
	}

	selectionWriteHit(context, &hitHeader);
}

void s_DrawTriangleFan(struct GLcontext_t *context)
{
	int i;
	GLuint and_code, or_code;
	GLboolean * visible  = context->ts_Visible;
	GLubyte   * complete = context->ts_Complete;
	int triangle = 0;

	dprintf("REVIEW ME\n");

	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

	if (
		context->enable.CullFace == GL_TRUE &&
		context->polygon.CullFace == GL_FRONT_AND_BACK
	) {
		return;
	}
	selection_v_Transform(context);

	and_code = 0xFF;
	or_code = 0;

	for (i=0; i<context->VertexBufferPointer; i++) {
		MGLVertex *v = &(context->VertexBuffer[i]);
		float w = v->clip.w;
		GLuint local_outcode = 0;

		if (w < CLIP_EPS ) {
			local_outcode |= MGL_CLIP_NEGW;
		}
		if (-w > v->clip.x) {
			local_outcode |= MGL_CLIP_LEFT;
		}
		else if (v->clip.x > w) {
			local_outcode |= MGL_CLIP_RIGHT;
		}
		if (-w > v->clip.y) {
			local_outcode |= MGL_CLIP_BOTTOM;
		}
		else if (v->clip.y > w) {
			local_outcode |= MGL_CLIP_TOP;
		}
		if (-w > v->clip.z) {
			local_outcode |= MGL_CLIP_BACK;
		}
		else if (v->clip.z > w) {
			local_outcode |= MGL_CLIP_FRONT;
		}
		v->outcode = local_outcode;
		and_code &= local_outcode;
		or_code  |= local_outcode;
	}

	if (and_code) {
		return;
	}

	/*
	** Up to now everything is like a polygon. Unlike a polygon, however,
	** triangle fans and strips may be concave, and each individual triangle
	** might be backfacing.
	**
	** We calculate how many of the triangles are visible.
	*/

	for (i=1,triangle=0; i<context->VertexBufferPointer - 1; i++, triangle++) {
		GLuint local_and = context->VertexBuffer[0].outcode
		          & context->VertexBuffer[i].outcode
		          & context->VertexBuffer[i+1].outcode;

		if (local_and == 0) {
			// if the local and code is zero, we're not
      // completely off screen
			GLuint local_or = context->VertexBuffer[0].outcode
			         | context->VertexBuffer[i].outcode
			         | context->VertexBuffer[i+1].outcode;
			visible[triangle] = hc_DecideFrontface(
				context,
				&(context->VertexBuffer[0]),
				&(context->VertexBuffer[i]),
				&(context->VertexBuffer[i+1]),
				local_or
			);

			// if our local or codes are zero, we are completely
			// visible

			complete[triangle] = local_or;
		}
		else {
			visible[triangle] = GL_FALSE;
		}
	}



	/*
	** Draw...
	** There are three cases:
	**
	** 1) Triangle is partially visible
	** 2) Triangle is fully visible
	** 3) Triangle is invisible
	**
	** In case 1, we draw the triangle with clip_ClipAndDrawPoly.
	** In case 2, we collect a triangle fan/strip of maximum length
	** and draw that directly
	** in case 3... WE IGNORE IT! HA!
	*/
	triangle = 0; i=1;

	do {
		if (visible[triangle] == GL_FALSE) {
			// case 3
			triangle++;
			i++;
		}
		else {
			if (complete[triangle]) {
				// case 1
				MGLPolygon poly;
				poly.numverts = 3;
				poly.verts[0] = 0;
				poly.verts[1] = i;
				poly.verts[2] = i + 1;
				// HERE
				MGLPolygon *clippedPoly, temp;
				if (hc_ClipPoly(context, &poly, or_code, &clippedPoly, &temp) == GL_TRUE) {
					s_DrawPoly(context, clippedPoly, &hitHeader);
				}

				triangle++;
				i++;
			}
			else {
				// case 2 (the difficult part)
				int k = 3;

				context->IndexBuffer[0] = 0;
				context->IndexBuffer[1] = i;
				context->IndexBuffer[2] = i+1;

				selection_v_ToScreen(context, 0);
				selection_v_ToScreen(context, i);
				selection_v_ToScreen(context, i+1);

				triangle++;
				i++;

				while (complete[triangle]==0 && visible[triangle] && i<context->VertexBufferPointer - 1) {
					context->IndexBuffer[k] = i+1;
					selection_v_ToScreen(context, i+1);
					i++;
					k++;
					triangle++;
				}

				for (i=0; i<k; i++) {
					selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[context->IndexBuffer[i]]));
				}
			}
		}
	} while (i<context->VertexBufferPointer-1);

	selectionWriteHit(context, &hitHeader);
}

void s_DrawTriangleStrip(struct GLcontext_t *context)
{
	int i;
	GLuint and_code, or_code;
	GLenum CurrentFrontFace = context->polygon.FrontFace;

	dprintf("REVIEW ME\n");

	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

	if (
		context->enable.CullFace == GL_TRUE &&
		context->polygon.CullFace == GL_FRONT_AND_BACK
	) {
		return;
	}

	selection_v_Transform(context);

	and_code = 0xFF;
	or_code = 0;

	for (i=0; i<context->VertexBufferPointer; i++) {
		MGLVertex *v = &(context->VertexBuffer[i]);
		float w = v->clip.w;
		GLuint local_outcode = 0;

		if (w < CLIP_EPS ) {
			local_outcode |= MGL_CLIP_NEGW;
		}

		if (-w > v->clip.x) {
			local_outcode |= MGL_CLIP_LEFT;
		}
		else if (v->clip.x > w) {
			local_outcode |= MGL_CLIP_RIGHT;
		}

		if (-w > v->clip.y) {
			local_outcode |= MGL_CLIP_BOTTOM;
		}
		else if (v->clip.y > w) {
			local_outcode |= MGL_CLIP_TOP;
		}

		if (-w > v->clip.z) {
			local_outcode |= MGL_CLIP_BACK;
		}
		else if (v->clip.z > w) {
			local_outcode |= MGL_CLIP_FRONT;
		}
		v->outcode = local_outcode;
		and_code &= local_outcode;
		or_code  |= local_outcode;
	}

	if (and_code) {
		return;
	}

	// Fill mode dictates we need to draw these singular
	for (i=0; i<context->VertexBufferPointer - 2; i++) {
		MGLPolygon poly;

		GLuint local_and = context->VertexBuffer[i+0].outcode
		          & context->VertexBuffer[i+1].outcode
		          & context->VertexBuffer[i+2].outcode;

		if (local_and) {
			continue;
		}
		poly.numverts = 3;
		poly.verts[0] = i+0;
		poly.verts[1] = i+1;
		poly.verts[2] = i+2;

		#if 0
		GLuint local_or = context->VertexBuffer[i+0].outcode
		         | context->VertexBuffer[i+1].outcode
		         | context->VertexBuffer[i+2].outcode;
		#endif		         

		MGLPolygon *clippedPoly, temp;
		if (hc_ClipPoly(context, &poly, or_code, &clippedPoly, &temp) == GL_TRUE) {
			s_DrawPoly(context, clippedPoly, &hitHeader);
		}
	}

	if (context->polygon.FrontFace == GL_CCW) {
		context->polygon.FrontFace = GL_CW;
	}
	else {
		context->polygon.FrontFace = GL_CCW;
	}
	context->polygon.FrontFace = CurrentFrontFace;

	selectionWriteHit(context, &hitHeader);
}

void s_DrawQuads(struct GLcontext_t *context)
{
	int i;
	GLuint or_code, and_code;
	SelectionHitHeader hitHeader;

	selectionNewHit(context, &hitHeader);

	dprintf("Num quads: %u\n", context->VertexBufferPointer / 4);

	selection_v_Transform(context);

	for (i=0; i<context->VertexBufferPointer; i+=4) {
		hc_CodePoint(context, &(context->VertexBuffer[i]));
		hc_CodePoint(context, &(context->VertexBuffer[i+1]));
		hc_CodePoint(context, &(context->VertexBuffer[i+2]));
		hc_CodePoint(context, &(context->VertexBuffer[i+3]));

		and_code = context->VertexBuffer[i+0].outcode
		         & context->VertexBuffer[i+1].outcode
		         & context->VertexBuffer[i+2].outcode
		         & context->VertexBuffer[i+3].outcode;

		if (and_code) {
			continue;
		}

		or_code = context->VertexBuffer[i+0].outcode
		        | context->VertexBuffer[i+1].outcode
		        | context->VertexBuffer[i+2].outcode
		        | context->VertexBuffer[i+3].outcode;

		if (
			hc_DecideFrontface(
				context, &(context->VertexBuffer[i]),
				&(context->VertexBuffer[i+1]),
				&(context->VertexBuffer[i+2]),
				or_code
			) == GL_FALSE
		) {
			continue;
		}
		// If we get here, we have at least one hit

		if (or_code == 0) {
			selection_v_ToScreen(context, i);
			selection_v_ToScreen(context, i+1);
			selection_v_ToScreen(context, i+2);
			selection_v_ToScreen(context, i+3);

			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+1]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+2]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+3]));
		}
		else {
			MGLPolygon poly;
			poly.numverts = 4;
			poly.verts[0] = i;
			poly.verts[1] = i+1;
			poly.verts[2] = i+2;
			poly.verts[3] = i+3;

			MGLPolygon *clippedPoly, temp;
			if (hc_ClipPoly(context, &poly, or_code, &clippedPoly, &temp) == GL_TRUE) {
				s_DrawPoly(context, clippedPoly, &hitHeader);
			}
		}
	}

	selectionWriteHit(context, &hitHeader);
}

void s_DrawPolygon(struct GLcontext_t *context)
{
	int i;
	GLuint or_code, and_code;
	MGLPolygon *poly = context->LargePolygon;

	SelectionHitHeader hitHeader;

	selectionNewHit(context, &hitHeader);

	selection_v_Transform(context);
	or_code = 0; and_code = 0xFF;

	for (i=0; i<context->VertexBufferPointer; i++) {
		hc_CodePoint(context, &(context->VertexBuffer[i]));
		or_code  |= context->VertexBuffer[i].outcode;
		and_code &= context->VertexBuffer[i].outcode;
		poly->verts[i] = i;
	}

	if (and_code) {
		return;
	}

	poly->numverts = context->VertexBufferPointer;

	if (or_code == 0) {
		s_DrawPolyFF(context, poly, &hitHeader);
	}
	else {
		MGLPolygon *clippedPoly, *temp = context->LargePolygonOut;
		if (hc_ClipPolyFF(context, poly, or_code, &clippedPoly, temp) == GL_TRUE) {
			s_DrawPolyFF(context, clippedPoly, &hitHeader);
		}
	}

	selectionWriteHit(context, &hitHeader);
}

void s_DrawFlatFan(struct GLcontext_t *context)
{
	int i;

	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

	for (i=0; i<context->VertexBufferPointer; i++) {
		context->VertexBuffer[i].x = (W3D_Float) context->VertexBuffer[i].object.x;
		context->VertexBuffer[i].y = (W3D_Float) context->VertexBuffer[i].object.y;
		context->VertexBuffer[i].z = (W3D_Double)context->VertexBuffer[i].object.z;
		context->VertexBuffer[i].uvw[context->texture.ActiveTexture].w =
			(W3D_Float) context->VertexBuffer[i].object.w;
	}

	for (i = 0; i < context->VertexBufferPointer; i++) {
		selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[context->IndexBuffer[i]]));
	}

	selectionWriteHit(context, &hitHeader);
}


void s_DrawQuadStrip(struct GLcontext_t *context)
{
	int i;
	GLuint or_code, and_code;


	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

	selection_v_Transform(context);

	for (i=0; i<context->VertexBufferPointer-3; i+=2) {
		hc_CodePoint(context, &(context->VertexBuffer[i]));
		hc_CodePoint(context, &(context->VertexBuffer[i+1]));
		hc_CodePoint(context, &(context->VertexBuffer[i+2]));
		hc_CodePoint(context, &(context->VertexBuffer[i+3]));

		and_code = context->VertexBuffer[i+0].outcode
		         & context->VertexBuffer[i+1].outcode
		         & context->VertexBuffer[i+2].outcode
		         & context->VertexBuffer[i+3].outcode;
		if (and_code) {
			continue;
		}

		or_code = context->VertexBuffer[i+0].outcode
		        | context->VertexBuffer[i+1].outcode
		        | context->VertexBuffer[i+2].outcode
		        | context->VertexBuffer[i+3].outcode;

		if (
			hc_DecideFrontface(
				context, &(context->VertexBuffer[i]),
				&(context->VertexBuffer[i+1]),
				&(context->VertexBuffer[i+2]),
				or_code
			) == GL_FALSE &&
			hc_DecideFrontface(
				context, &(context->VertexBuffer[i+1]),
				&(context->VertexBuffer[i+3]),
				&(context->VertexBuffer[i+2]),
				or_code
			) == GL_FALSE
		) {
			continue;
		}

		if (or_code == 0) {
			selection_v_ToScreen(context, i);
			selection_v_ToScreen(context, i+1);
			selection_v_ToScreen(context, i+2);
			selection_v_ToScreen(context, i+3);

			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+1]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+2]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[i+3]));
		}
		else {
			MGLPolygon poly;
			poly.numverts = 4;
			poly.verts[0] = i;
			poly.verts[1] = i+1;
			poly.verts[2] = i+3;
			poly.verts[3] = i+2;

			MGLPolygon *clippedPoly, temp;
			if (hc_ClipPoly(
				context, &poly, or_code, &clippedPoly, &temp
			) == GL_TRUE ) {
				s_DrawPoly(context, clippedPoly, &hitHeader);
			}
		}
	}

	selectionWriteHit(context, &hitHeader);
}

extern GLuint FetchElementByte(GLvoid **indices);
extern GLuint FetchElementShort(GLvoid **indices);
extern GLuint FetchElementInt(GLvoid **indices);

// Warning: This function currently expects GLDrawElementsTriangles() to have performed the initial transformations
void s_GLDrawElementsTriangles(struct GLcontext_t *context, GLsizei count, GLenum type, const GLvoid *indices)
{
	GLuint (*index_fetch)(GLvoid **indices);
	GLvoid *index_pointer = (GLvoid *)indices;
	GLuint and_code, or_code;
	GLuint i;
	GLfloat offset;
        /* If */
	GLuint first = context->LockArraysFirst;

	SelectionHitHeader hitHeader;
	selectionNewHit(context, &hitHeader);

	selection_v_Transform(context);

	/* Determine the index type */
	switch (type) {
		case GL_UNSIGNED_BYTE:
			index_fetch = FetchElementByte;
			break;

		case GL_UNSIGNED_SHORT:
			index_fetch = FetchElementShort;
			break;

		case GL_UNSIGNED_INT:
			index_fetch = FetchElementInt;
			break;

		default:
			GLFlagError(context, 1, GL_INVALID_ENUM);
	}

	/* Go through the array and draw */
	for (i = 0; i < count; i+=3) {
		GLfloat z1 = 0.0, z2 = 0.0, z3 = 0.0;

		GLuint idx1 = index_fetch(&index_pointer) - first;
		GLuint idx2 = index_fetch(&index_pointer) - first;
		GLuint idx3 = index_fetch(&index_pointer) - first;

		and_code = context->VertexBuffer[idx1].outcode
		         & context->VertexBuffer[idx2].outcode
		         & context->VertexBuffer[idx3].outcode;

		if (and_code) {
			continue;
		}

		or_code = context->VertexBuffer[idx1].outcode
		        | context->VertexBuffer[idx2].outcode
		        | context->VertexBuffer[idx3].outcode;

		if ((hc_DecideFrontface(context, &(context->VertexBuffer[idx1]),
			&(context->VertexBuffer[idx2]),
			&(context->VertexBuffer[idx3]),or_code
		) == GL_FALSE)) {
			continue;
		}

		if (context->enable.PolygonOffsetFill) {
			offset = v_PolygonOffset(context, idx1, idx2, idx3);

			z1 = context->VertexBuffer[idx1].z;
			z2 = context->VertexBuffer[idx2].z;
			z3 = context->VertexBuffer[idx3].z;

			context->VertexBuffer[idx1].z = min (1.0, context->VertexBuffer[idx1].z + offset);
			context->VertexBuffer[idx2].z = min (1.0, context->VertexBuffer[idx2].z + offset);
			context->VertexBuffer[idx3].z = min (1.0, context->VertexBuffer[idx3].z + offset);
		}
		else {
			offset = 0.0;
		}
		if (or_code == 0) {
			selection_v_ToScreen(context, idx1);
			selection_v_ToScreen(context, idx2);
			selection_v_ToScreen(context, idx3);

			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[idx1]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[idx2]));
			selectionHitAddVertex(context, &hitHeader, &(context->VertexBuffer[idx3]));
		}
		else {
			MGLPolygon poly;
			poly.numverts = 3;
			poly.verts[0] = idx1;
			poly.verts[1] = idx2;
			poly.verts[2] = idx3;
			poly.zoffset = offset;

			MGLPolygon *clippedPoly, temp;
			if (hc_ClipPoly(context, &poly, or_code, &clippedPoly, &temp) == GL_TRUE) {
				s_DrawPoly(context, clippedPoly, &hitHeader);
			}
		}

		if (context->enable.PolygonOffsetFill) {
			context->VertexBuffer[idx1].z = z1;
			context->VertexBuffer[idx2].z = z2;
			context->VertexBuffer[idx3].z = z3;
		}
	}
}

// ----- PRIVATE FUNCTIONS -----

void selectionNewHit(struct GLcontext_t *context, SelectionHitHeader *newHeader)
{
	newHeader->numNames = context->nameStackPointer + 1;
	newHeader->minDepth = (GLuint)~0;
	newHeader->maxDepth = 0;
}

void selectionHitAddVertex(struct GLcontext_t *context, SelectionHitHeader *hitHeader, MGLVertex *vertex)
{
	dprintf("x:%f, y:%f, z:%f\n", vertex->x, vertex->y, vertex->z);
	GLuint depthVal = (GLuint)(vertex->z * 4294967296 - 1);
	if (depthVal < hitHeader->minDepth) {
		hitHeader->minDepth = depthVal;
	}
	if (depthVal > hitHeader->maxDepth) {
		hitHeader->maxDepth = depthVal;
	}
}

#define CHECK_SB_OVERFLOW \
	if (context->selectionBufferPointer >= context->selectionBufferSize) { \
		context->selectionBufferOverflow = TRUE;                            \
		dprintf("%s: selection buffer overflow.\n", __func__);              \
		return;                                                             \
	}

void selectionWriteHit(struct GLcontext_t *context, SelectionHitHeader *hitHeader)
{
	if (hitHeader->maxDepth < hitHeader->minDepth) {
		// No vertices were added so there was no actual hit
		return;
	}

	if (context->selectionBufferOverflow) {
		// Can't add any more to the buffer
		return;
	}

	if (!context->selectionBuffer) {
		dprintf("Internal error, in GL_SELECT mode but there is no selection buffer\n");
	}

	#define buffIdx (context->selectionBufferPointer)

	CHECK_SB_OVERFLOW
	context->selectionBuffer[buffIdx] = hitHeader->numNames;

	buffIdx++;
	CHECK_SB_OVERFLOW
	context->selectionBuffer[buffIdx] = hitHeader->minDepth;

	buffIdx++;
	CHECK_SB_OVERFLOW
	context->selectionBuffer[buffIdx] = hitHeader->maxDepth;

	buffIdx++;
	if (context->nameStackPointer == NAMESTACK_EMPTY) {
		context->selectionNumHits++;
		return;
	}
	for (GLuint i = 0; i <=context->nameStackPointer; i++) {
		CHECK_SB_OVERFLOW
		context->selectionBuffer[buffIdx] = context->nameStack[i];
		buffIdx++;
	}
	#undef buffIdx
	context->selectionNumHits++;
}


INLINE void selection_v_Transform(GLcontext context)
{
	int i;

	if (context->NeedEye) {
		v_GenEyeCoords(context);
	}
	if (context->CombinedValid == GL_FALSE) {
		m_CombineMatrices(context);
	}

	if (context->WOne_Hint == GL_FALSE) {
		#define a(x) (context->CombinedMatrix.v[OF_##x])
		float a11 = a(11);
		float a12 = a(12);
		float a13 = a(13);
		float a14 = a(14);
		float a21 = a(21);
		float a22 = a(22);
		float a23 = a(23);
		float a24 = a(24);
		float a31 = a(31);
		float a32 = a(32);
		float a33 = a(33);
		float a34 = a(34);
		float a41 = a(41);
		float a42 = a(42);
		float a43 = a(43);
		float a44 = a(44);

		int counter = context->VertexBufferPointer;
		MGLVertex *vf = context->VertexBuffer;

		for (i = 0; i < counter; i++) {
			MGLVertex *v = &vf[i];
			float x = v->object.x;
			float y = v->object.y;
			float z = v->object.z;
			float w = v->object.w;

			v->clip.x = a11*x + a12*y + a13*z + a14*w;
			v->clip.y = a21*x + a22*y + a23*z + a24*w;
			v->clip.z = a31*x + a32*y + a33*z + a34*w;
			v->clip.w = a41*x + a42*y + a43*z + a44*w;
		}

		#undef a
	}
	else {
		#define a(x) (context->CombinedMatrix.v[OF_##x])
		float a11 = a(11);
		float a12 = a(12);
		float a13 = a(13);
		float a14 = a(14);
		float a21 = a(21);
		float a22 = a(22);
		float a23 = a(23);
		float a24 = a(24);
		float a31 = a(31);
		float a32 = a(32);
		float a33 = a(33);
		float a34 = a(34);
		float a41 = a(41);
		float a42 = a(42);
		float a43 = a(43);
		float a44 = a(44);

		int counter   = context->VertexBufferPointer;
		MGLVertex *vf = context->VertexBuffer;

		for (i=0; i<counter; i++) {
			MGLVertex *v = &vf[i];
			float x = v->object.x;
			float y = v->object.y;
			float z = v->object.z;
			v->clip.x = a11*x + a12*y + a13*z + a14;
			v->clip.y = a21*x + a22*y + a23*z + a24;
			v->clip.z = a31*x + a32*y + a33*z + a34;
			v->clip.w = a41*x + a42*y + a43*z + a44;
		}
		#undef a
	}
}

void s_DrawPoly(GLcontext context, MGLPolygon *poly, SelectionHitHeader *hitHeader)
{
	int i;
	float area;
	GLfloat z[MGL_MAXVERTS];

	for (i=0; i<poly->numverts; i++) {
		selection_v_ToScreen(context, poly->verts[i]);
	}

	area = dh_AreaSign(context, poly);
	if (fast_fabs(area) <= context->MinTriArea) {
		return;
	}
	if (context->enable.PolygonOffsetFill) {
		/* This is really bad! */
		for (i=0; i<poly->numverts; i++) {
			z[i] = context->VertexBuffer[poly->verts[i]].z;
			context->VertexBuffer[poly->verts[i]].z = min (1.0, context->VertexBuffer[poly->verts[i]].z + poly->zoffset);
		}
	}

	for (i=0; i<poly->numverts; i++) {
		selectionHitAddVertex(context, hitHeader, &(context->VertexBuffer[poly->verts[i]]));
	}

	if (context->enable.PolygonOffsetFill) {
		for (i=0; i<poly->numverts; i++) {
			context->VertexBuffer[poly->verts[i]].z = z[i];
		}
	}
}

void s_DrawPolyFF(GLcontext context, MGLPolygon *poly, SelectionHitHeader *hitHeader)
{
	int i;
	GLfloat area = 0.0;

	for (i=0; i<poly->numverts; i++) {
		selection_v_ToScreen(context, poly->verts[i]);
	}
	if (context->enable.CullFace == GL_TRUE) {
		area = dh_AreaSign(context, poly);

		if (context->polygon.FrontFace == GL_CW) {
			area *= -1.f;
		}
		if (area < context->MinTriArea) {
			return; // Either backfacing, or too small
		}
	}
	else {
		area = dh_AreaSign(context, poly);
		if (fast_fabs(area) < context->MinTriArea) {
			return;
		}
	}

	for (i=0; i<poly->numverts; i++) {
		selectionHitAddVertex(context, hitHeader, &(context->VertexBuffer[poly->verts[i]]));
	}
}

void s_DrawLine(GLcontext context, MGLPolygon *poly, SelectionHitHeader *hitHeader)
{
	selection_v_ToScreen(context, poly->verts[0]);
	selection_v_ToScreen(context, poly->verts[1]);

	selectionHitAddVertex(context, hitHeader, &(context->VertexBuffer[poly->verts[0]]));
	selectionHitAddVertex(context, hitHeader, &(context->VertexBuffer[poly->verts[1]]));
}

INLINE void selection_v_ToScreen(GLcontext context, int i)
{
	float w;

	w = 1.0 / context->VertexBuffer[i].clip.w;

	context->VertexBuffer[i].x =
					context->ax + context->VertexBuffer[i].clip.x * w * context->sx;
	context->VertexBuffer[i].y =
					context->ay - context->VertexBuffer[i].clip.y * w * context->sy;
	context->VertexBuffer[i].z =
					context->az + context->VertexBuffer[i].clip.z * w * context->sz;

	if (context->enable.ZOffset == GL_TRUE) {
		context->VertexBuffer[i].z += (W3D_Float)context->depth_buffer.ZOffset;
	}
}