/*
Copyright (C) 1996-1997 Id Software, Inc.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/
// r_bsp.c

#include "quakedef.h"
#include "r_local.h"

//
// current entity info
//
qboolean		insubmodel;
entity_t		*currententity;
vec3_t			modelorg, base_modelorg;
								// modelorg is the viewpoint reletive to
								// the currently rendering entity
vec3_t			r_entorigin;	// the currently rendering entity in world
								// coordinates

float			entity_rotation[3][3];

vec3_t			r_worldmodelorg;

int				r_currentbkey;

typedef enum {touchessolid, drawnode, nodrawnode} solidstate_t;

#define MAX_BMODEL_VERTS	250			// 6K
#define MAX_BMODEL_EDGES	500		// 12K

static mvertex_t	*pbverts;
static bedge_t		*pbedges;
static int			numbverts, numbedges;

static mvertex_t	*pfrontenter, *pfrontexit;

static qboolean		makeclippededge;

#define floattov16(n)         ((short int)((n) * (1 << 12)))
extern short int scaled_modelorg[3];
extern float tri2_scale;

#define USE_3D


//===========================================================================

/*
================
R_EntityRotate
================
*/
void R_EntityRotate (vec3_t vec)
{
	vec3_t	tvec;

	VectorCopy (vec, tvec);
	vec[0] = DotProduct (entity_rotation[0], tvec);
	vec[1] = DotProduct (entity_rotation[1], tvec);
	vec[2] = DotProduct (entity_rotation[2], tvec);
}


/*
================
R_RotateBmodel
================
*/
void R_RotateBmodel (void)
{
	float	angle, s, c, temp1[3][3], temp2[3][3], temp3[3][3];

// TODO: should use a look-up table
// TODO: should really be stored with the entity instead of being reconstructed
// TODO: could cache lazily, stored in the entity
// TODO: share work with R_SetUpAliasTransform

// yaw
	angle = currententity->angles[YAW];		
	angle = angle * M_PI*2 / 360;
	s = sin(angle);
	c = cos(angle);

	temp1[0][0] = c;
	temp1[0][1] = s;
	temp1[0][2] = 0;
	temp1[1][0] = -s;
	temp1[1][1] = c;
	temp1[1][2] = 0;
	temp1[2][0] = 0;
	temp1[2][1] = 0;
	temp1[2][2] = 1;


// pitch
	angle = currententity->angles[PITCH];		
	angle = angle * M_PI*2 / 360;
	s = sin(angle);
	c = cos(angle);

	temp2[0][0] = c;
	temp2[0][1] = 0;
	temp2[0][2] = -s;
	temp2[1][0] = 0;
	temp2[1][1] = 1;
	temp2[1][2] = 0;
	temp2[2][0] = s;
	temp2[2][1] = 0;
	temp2[2][2] = c;

	R_ConcatRotations (temp2, temp1, temp3);

// roll
	angle = currententity->angles[ROLL];		
	angle = angle * M_PI*2 / 360;
	s = sin(angle);
	c = cos(angle);

	temp1[0][0] = 1;
	temp1[0][1] = 0;
	temp1[0][2] = 0;
	temp1[1][0] = 0;
	temp1[1][1] = c;
	temp1[1][2] = s;
	temp1[2][0] = 0;
	temp1[2][1] = -s;
	temp1[2][2] = c;

	R_ConcatRotations (temp1, temp3, entity_rotation);

//
// rotate modelorg and the transformation matrix
//
	R_EntityRotate (modelorg);
	R_EntityRotate (vpn);
	R_EntityRotate (vright);
	R_EntityRotate (vup);

	R_TransformFrustum ();
	
	scaled_modelorg[0] = floattov16(modelorg[0] * tri2_scale);
	scaled_modelorg[1] = floattov16(modelorg[1] * tri2_scale);
	scaled_modelorg[2] = floattov16(modelorg[2] * tri2_scale);
}


/*
================
R_RecursiveClipBPoly
================
*/
#ifndef USE_3D
void R_RecursiveClipBPoly (bedge_t *pedges, mnode_t *pnode, msurface_t *psurf)
{
	bedge_t		*psideedges[2], *pnextedge, *ptedge;
	int			i, side, lastside;
	float		dist, frac, lastdist;
	mplane_t	*splitplane, tplane;
	mvertex_t	*pvert, *plastvert, *ptvert;
	mnode_t		*pn;

	psideedges[0] = psideedges[1] = NULL;

	makeclippededge = false;

// transform the BSP plane into model space
// FIXME: cache these?
	splitplane = pnode->plane;
	tplane.dist = splitplane->dist -
			DotProduct(r_entorigin, splitplane->normal);

//	tplane.bigdist = (splitplane->bigdist >> 10) -
//			DotProduct(r_entorigin, splitplane->normal) * 1024;
	tplane.normal[0] = DotProduct (entity_rotation[0], splitplane->normal);
	tplane.normal[1] = DotProduct (entity_rotation[1], splitplane->normal);
	tplane.normal[2] = DotProduct (entity_rotation[2], splitplane->normal);

//	int big_entorigin[3];
//	big_entorigin[0] = r_entorigin[0] * 1024;
//	big_entorigin[1] = r_entorigin[1] * 1024;
//	big_entorigin[2] = r_entorigin[2] * 1024;
//	
//	tplane.bigdist = splitplane->bigdist - DotProductII(big_entorigin, splitplane->bignormal);
//	
//	int big_entrotation[3][3];
//	int inner, outer;
//	
//	for (outer = 0; outer < 3; outer++)
//		for (inner = 0; inner < 3; inner++)
//			big_entrotation[outer][inner] = entity_rotation[outer][inner];
//	
//	tplane.bignormal[0] = DotProductII(big_entrotation[0], splitplane->bignormal);
//	tplane.bignormal[1] = DotProductII(big_entrotation[1], splitplane->bignormal);
//	tplane.bignormal[2] = DotProductII(big_entrotation[2], splitplane->bignormal);

// clip edges to BSP plane
	for ( ; pedges ; pedges = pnextedge)
	{
		pnextedge = pedges->pnext;

	// set the status for the last point as the previous point
	// FIXME: cache this stuff somehow?
		plastvert = pedges->v[0];
		lastdist = DotProduct (plastvert->position, tplane.normal);
		lastdist -= tplane.dist;
//		lastdist = DotProduct (plastvert->position, tplane.normal) -
//				   (tplane.bigdist >> 10);
//		lastdist = DotProductIFP(plastvert->position, tplane.bignormal) -
//				   (tplane.bigdist >> 10);

		if (lastdist > 0)
			lastside = 0;
		else
			lastside = 1;

		pvert = pedges->v[1];

		dist = DotProduct (pvert->position, tplane.normal);
		dist -= tplane.dist;
//		dist = DotProduct (pvert->position, tplane.normal) - (tplane.bigdist >> 10);
//		dist = DotProductIFP(pvert->position, tplane.bignormal) - (tplane.bigdist >> 10);

		if (dist > 0)
			side = 0;
		else
			side = 1;

		if (side != lastside)
		{
		// clipped
			if (numbverts >= MAX_BMODEL_VERTS)
				return;

		// generate the clipped vertex
			frac = lastdist / (lastdist - dist);
			ptvert = &pbverts[numbverts++];
			ptvert->position[0] = plastvert->position[0] +
					frac * (pvert->position[0] -
					plastvert->position[0]);
			ptvert->position[1] = plastvert->position[1] +
					frac * (pvert->position[1] -
					plastvert->position[1]);
			ptvert->position[2] = plastvert->position[2] +
					frac * (pvert->position[2] -
					plastvert->position[2]);

		// split into two edges, one on each side, and remember entering
		// and exiting points
		// FIXME: share the clip edge by having a winding direction flag?
			if (numbedges >= (MAX_BMODEL_EDGES - 1))
			{
				Con_Printf ("Out of edges for bmodel\n");
				return;
			}

			ptedge = &pbedges[numbedges];
			ptedge->pnext = psideedges[lastside];
			psideedges[lastside] = ptedge;
			ptedge->v[0] = plastvert;
			ptedge->v[1] = ptvert;

			ptedge = &pbedges[numbedges + 1];
			ptedge->pnext = psideedges[side];
			psideedges[side] = ptedge;
			ptedge->v[0] = ptvert;
			ptedge->v[1] = pvert;

			numbedges += 2;

			if (side == 0)
			{
			// entering for front, exiting for back
				pfrontenter = ptvert;
				makeclippededge = true;
			}
			else
			{
				pfrontexit = ptvert;
				makeclippededge = true;
			}
		}
		else
		{
		// add the edge to the appropriate side
			pedges->pnext = psideedges[side];
			psideedges[side] = pedges;
		}
	}

// if anything was clipped, reconstitute and add the edges along the clip
// plane to both sides (but in opposite directions)
	if (makeclippededge)
	{
		if (numbedges >= (MAX_BMODEL_EDGES - 2))
		{
			Con_Printf ("Out of edges for bmodel\n");
			return;
		}

		ptedge = &pbedges[numbedges];
		ptedge->pnext = psideedges[0];
		psideedges[0] = ptedge;
		ptedge->v[0] = pfrontexit;
		ptedge->v[1] = pfrontenter;

		ptedge = &pbedges[numbedges + 1];
		ptedge->pnext = psideedges[1];
		psideedges[1] = ptedge;
		ptedge->v[0] = pfrontenter;
		ptedge->v[1] = pfrontexit;

		numbedges += 2;
	}

// draw or recurse further
	for (i=0 ; i<2 ; i++)
	{
		if (psideedges[i])
		{
		// draw if we've reached a non-solid leaf, done if all that's left is a
		// solid leaf, and continue down the tree if it's not a leaf
			pn = pnode->children[i];

		// we're done with this branch if the node or leaf isn't in the PVS
			if (pn->visframe == r_visframecount)
			{
				if (pn->contents < 0)
				{
					if (pn->contents != CONTENTS_SOLID)
					{
						r_currentbkey = ((mleaf_t *)pn)->key;
						R_RenderBmodelFace (psideedges[i], psurf);
					}
				}
				else
				{
					R_RecursiveClipBPoly (psideedges[i], pnode->children[i],
									  psurf);
				}
			}
		}
	}
}


/*
================
R_DrawSolidClippedSubmodelPolygons
================
*/
void R_DrawSolidClippedSubmodelPolygons (model_t *pmodel)
{
	int			i, j, lindex;
	vec_t		dot;
	msurface_t	*psurf;
	int			numsurfaces;
	mplane_t	*pplane;
	mvertex_t	bverts[MAX_BMODEL_VERTS];
	bedge_t		bedges[MAX_BMODEL_EDGES], *pbedge;
	medge_t		*pedge, *pedges;

// FIXME: use bounding-box-based frustum clipping info?

	psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
	numsurfaces = pmodel->nummodelsurfaces;
	pedges = pmodel->edges;
//	
//	int big_modelorg[3];
//	big_modelorg[0] = modelorg[0] * 1024;
//	big_modelorg[1] = modelorg[1] * 1024;
//	big_modelorg[2] = modelorg[2] * 1024;

	for (i=0 ; i<numsurfaces ; i++, psurf++)
	{
	// find which side of the node we are on
		pplane = psurf->plane;

		dot = DotProduct (modelorg, pplane->normal);
		dot -= pplane->dist;
//		dot = DotProduct (modelorg, pplane->normal) - (pplane->bigdist >> 10);

//		dot = (DotProductII(big_modelorg, pplane->bignormal) - pplane->bigdist) >> 10;

	// draw the polygon
		if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
			(!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
		{
		// FIXME: use bounding-box-based frustum clipping info?

		// copy the edges to bedges, flipping if necessary so always
		// clockwise winding
		// FIXME: if edges and vertices get caches, these assignments must move
		// outside the loop, and overflow checking must be done here
			pbverts = bverts;
			pbedges = bedges;
			numbverts = numbedges = 0;

			if (psurf->numedges > 0)
			{
				pbedge = &bedges[numbedges];
				numbedges += psurf->numedges;

				for (j=0 ; j<psurf->numedges ; j++)
				{
				   lindex = pmodel->surfedges[psurf->firstedge+j];

					if (lindex > 0)
					{
						pedge = &pedges[lindex];
						pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]];
						pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]];
					}
					else
					{
						lindex = -lindex;
						pedge = &pedges[lindex];
						pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]];
						pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]];
					}

					pbedge[j].pnext = &pbedge[j+1];
				}

				pbedge[j-1].pnext = NULL;	// mark end of edges

				R_RecursiveClipBPoly (pbedge, currententity->topnode, psurf);
			}
			else
			{
				Sys_Error ("no edges in bmodel");
			}
		}
	}
}


/*
================
R_DrawSubmodelPolygons
================
*/
void R_DrawSubmodelPolygons (model_t *pmodel, int clipflags)
{
	int			i;
	vec_t		dot;
	msurface_t	*psurf;
	int			numsurfaces;
	mplane_t	*pplane;

// FIXME: use bounding-box-based frustum clipping info?

	psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
	numsurfaces = pmodel->nummodelsurfaces;
	
//	int big_modelorg[3];
//	big_modelorg[0] = modelorg[0] * 1024;
//	big_modelorg[1] = modelorg[1] * 1024;
//	big_modelorg[2] = modelorg[2] * 1024;

	for (i=0 ; i<numsurfaces ; i++, psurf++)
	{
	// find which side of the node we are on
		pplane = psurf->plane;

		dot = DotProduct (modelorg, pplane->normal);
		dot -= pplane->dist;
//		dot = DotProduct (modelorg, pplane->normal) - (pplane->bigdist >> 10);
//		dot = (DotProductII(big_modelorg, pplane->bignormal) - pplane->bigdist) >> 10;

	// draw the polygon
		if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
			(!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
		{
			r_currentkey = ((mleaf_t *)currententity->topnode)->key;

		// FIXME: use bounding-box-based frustum clipping info?
			R_RenderFace (psurf, clipflags);
		}
	}
}

#endif

/*
================
R_RecursiveWorldNode
================
*/
#if 0
void R_RecursiveWorldNode (mnode_t *node, int clipflags)
{
	int			i, c, side, *pindex;
	vec3_t		acceptpt, rejectpt;
	mplane_t	*plane;
	msurface_t	*surf, **mark;
	mleaf_t		*pleaf;
	int		d;
	float dot;
	//double d, dot;

	if (node->contents == CONTENTS_SOLID)
		return;		// solid

	if (node->visframe != r_visframecount)
		return;

// cull the clipping planes if not trivial accept
// FIXME: the compiler is doing a lousy job of optimizing here; it could be
//  twice as fast in ASM
	if (clipflags)
	{
		for (i=0 ; i<4 ; i++)
		{
			if (! (clipflags & (1<<i)) )
				continue;	// don't need to clip against it

		// generate accept and reject points
		// FIXME: do with fast look-ups or integer tests based on the sign bit
		// of the floating point values

			pindex = pfrustum_indexes[i];
			
			int bignormal[3];
//			bignormal[0] = view_clipplanes[i].normal[0] * 1024;
//			bignormal[1] = view_clipplanes[i].normal[1] * 1024;
//			bignormal[2] = view_clipplanes[i].normal[2] * 1024;
//			
//			int bigdist = view_clipplanes[i].dist * 1024;

			bignormal[0] = view_clipplanes[i].normal_int[0];
			bignormal[1] = view_clipplanes[i].normal_int[1];
			bignormal[2] = view_clipplanes[i].normal_int[2];
			
			int bigdist = view_clipplanes[i].dist_int;

			/*rejectpt[0] = (float)node->minmaxs[pindex[0]];
			rejectpt[1] = (float)node->minmaxs[pindex[1]];
			rejectpt[2] = (float)node->minmaxs[pindex[2]];
			
			d = DotProduct (rejectpt, view_clipplanes[i].normal);*/
			
			d = node->minmaxs[pindex[0]] * bignormal[0]
				+ node->minmaxs[pindex[1]] * bignormal[1]
				+ node->minmaxs[pindex[2]] * bignormal[2];
			
			d -= bigdist;

			if (d <= 0)
				return;

			/*acceptpt[0] = (float)node->minmaxs[pindex[3+0]];
			acceptpt[1] = (float)node->minmaxs[pindex[3+1]];
			acceptpt[2] = (float)node->minmaxs[pindex[3+2]];

			d = DotProduct (acceptpt, view_clipplanes[i].normal);*/
			
			d = node->minmaxs[pindex[3+0]] * bignormal[0]
				+ node->minmaxs[pindex[3+1]] * bignormal[1]
				+ node->minmaxs[pindex[3+2]] * bignormal[2];
			
			d -= bigdist;

			if (d >= 0)
				clipflags &= ~(1<<i);	// node is entirely on screen
		}
	}
	/*if (clipflags)
	{
		for (i=0 ; i<4 ; i++)
		{
			if (! (clipflags & (1<<i)) )
				continue;	// don't need to clip against it

		// generate accept and reject points
		// FIXME: do with fast look-ups or integer tests based on the sign bit
		// of the floating point values

			pindex = pfrustum_indexes[i];

			rejectpt[0] = (float)node->minmaxs[pindex[0]];
			rejectpt[1] = (float)node->minmaxs[pindex[1]];
			rejectpt[2] = (float)node->minmaxs[pindex[2]];
			
			d = DotProduct (rejectpt, view_clipplanes[i].normal);
			d -= view_clipplanes[i].dist;

			if (d <= 0)
				return;

			acceptpt[0] = (float)node->minmaxs[pindex[3+0]];
			acceptpt[1] = (float)node->minmaxs[pindex[3+1]];
			acceptpt[2] = (float)node->minmaxs[pindex[3+2]];

			d = DotProduct (acceptpt, view_clipplanes[i].normal);
			d -= view_clipplanes[i].dist;

			if (d >= 0)
				clipflags &= ~(1<<i);	// node is entirely on screen
		}
	}*/
	
// if a leaf node, draw stuff
	if (node->contents < 0)
	{
		pleaf = (mleaf_t *)node;

		mark = pleaf->firstmarksurface;
		c = pleaf->nummarksurfaces;

		if (c)
		{
			do
			{
				(*mark)->visframe = r_framecount;
				mark++;
			} while (--c);
		}

	// deal with model fragments in this leaf
		if (pleaf->efrags)
		{
			R_StoreEfrags (&pleaf->efrags);
		}

		pleaf->key = r_currentkey;
		r_currentkey++;		// all bmodels in a leaf share the same key
	}
	else
	{
	// node is just a decision point, so go down the apropriate sides

	// find which side of the node we are on
		plane = node->plane;
		
//		int big_modelorg[3];
//		big_modelorg[0] = modelorg[0] * 1024;
//		big_modelorg[1] = modelorg[1] * 1024;
//		big_modelorg[2] = modelorg[2] * 1024;

		switch (plane->type)
		{
		case PLANE_X:
			dot = modelorg[0] - plane->dist;
//			dot = modelorg[0] - (plane->bigdist >> 10);
//			dot = (big_modelorg[0] - plane->bigdist) >> 10;
			break;
		case PLANE_Y:
			dot = modelorg[1] - plane->dist;
//			dot = modelorg[1] - (plane->bigdist >> 10);
//			dot = (big_modelorg[1] - plane->bigdist) >> 10;
			break;
		case PLANE_Z:
			dot = modelorg[2] - plane->dist;
//			dot = modelorg[2] - (plane->bigdist >> 10);
//			dot = (big_modelorg[2] - plane->bigdist) >> 10;
			break;
		default:
			dot = DotProduct (modelorg, plane->normal);
			dot -= plane->dist;
//			dot = DotProduct (modelorg, plane->normal) - (plane->bigdist >> 10);
//			dot = (DotProductII(big_modelorg, plane->bignormal) - plane->bigdist) >> 10;
			break;
		}
	
		if (dot >= 0)
			side = 0;
		else
			side = 1;

	// recurse down the children, front side first
		R_RecursiveWorldNode (node->children[side], clipflags);

	// draw stuff
		c = node->numsurfaces;
		
		//c = 0;

		if (c)
		{
			surf = cl.worldmodel->surfaces + node->firstsurface;

			if (dot < -BACKFACE_EPSILON)
			{
				do
				{
					if ((surf->flags & SURF_PLANEBACK) &&
						(surf->visframe == r_framecount))
					{
						if (r_drawpolys)
						{
							if (r_worldpolysbacktofront)
							{
								if (numbtofpolys < MAX_BTOFPOLYS)
								{
									pbtofpolys[numbtofpolys].clipflags =
											clipflags;
									pbtofpolys[numbtofpolys].psurf = surf;
									numbtofpolys++;
								}
							}
							else
							{
//								scaled_modelorg[0] = floattov16(modelorg[0] * tri2_scale);
//								scaled_modelorg[1] = floattov16(modelorg[1] * tri2_scale);
//								scaled_modelorg[2] = floattov16(modelorg[2] * tri2_scale);
	
								R_RenderPoly (surf, clipflags);
							}
						}
						else
						{
#ifndef USE_3D
							R_RenderFace (surf, clipflags);
#endif
						}
					}

					surf++;
				} while (--c);
			}
			else if (dot > BACKFACE_EPSILON)
			{
				do
				{
					if (!(surf->flags & SURF_PLANEBACK) &&
						(surf->visframe == r_framecount))
					{
						if (r_drawpolys)
						{
							if (r_worldpolysbacktofront)
							{
								if (numbtofpolys < MAX_BTOFPOLYS)
								{
									pbtofpolys[numbtofpolys].clipflags =
											clipflags;
									pbtofpolys[numbtofpolys].psurf = surf;
									numbtofpolys++;
								}
							}
							else
							{
//								scaled_modelorg[0] = floattov16(modelorg[0] * tri2_scale);
//								scaled_modelorg[1] = floattov16(modelorg[1] * tri2_scale);
//								scaled_modelorg[2] = floattov16(modelorg[2] * tri2_scale);
	
								R_RenderPoly (surf, clipflags);
							}
						}
						else
						{
#ifndef USE_3D
							R_RenderFace (surf, clipflags);
#endif
						}
					}

					surf++;
				} while (--c);
			}

		// all surfaces on the same node share the same sequence number
			r_currentkey++;
		}

	// recurse down the back side
		R_RecursiveWorldNode (node->children[!side], clipflags);
	}
}

#else

inline bool world_clip(mnode_t *node, int *clipflags) __attribute__ ((no_instrument_function));
inline bool world_clip(mnode_t *node, int *clipflags)
{
	int clip = *clipflags;
	
	int *pindex;
	for (int i=0 ; i<4 ; i++)
	{
		if (! (clip & (1<<i)) )
			continue;	// don't need to clip against it

	// generate accept and reject points
	// FIXME: do with fast look-ups or integer tests based on the sign bit
	// of the floating point values

		pindex = pfrustum_indexes[i];
		
		int bignormal[3];

		bignormal[0] = view_clipplanes[i].normal_int[0];
		bignormal[1] = view_clipplanes[i].normal_int[1];
		bignormal[2] = view_clipplanes[i].normal_int[2];
		
		int bigdist = view_clipplanes[i].dist_int;
		
		int d1 = node->minmaxs[pindex[0]] * bignormal[0]
			+ node->minmaxs[pindex[1]] * bignormal[1]
			+ node->minmaxs[pindex[2]] * bignormal[2];
		
		d1 -= bigdist;

		if (d1 <= 0)
		{
			*clipflags = clip;
			return true;
		}
		
		int d2 = node->minmaxs[pindex[3+0]] * bignormal[0]
			+ node->minmaxs[pindex[3+1]] * bignormal[1]
			+ node->minmaxs[pindex[3+2]] * bignormal[2];
		
		d2 -= bigdist;

		if (d2 >= 0)
			clip &= ~(1<<i);	// node is entirely on screen
	}
	*clipflags = clip;
	return false;
}

inline void world_leaf_node(mleaf_t *pleaf, mnode_t *node) __attribute__ ((no_instrument_function));
inline void world_leaf_node(mleaf_t *pleaf, mnode_t *node)
{
	msurface_t	**mark;
	pleaf = (mleaf_t *)node;

	mark = pleaf->firstmarksurface;
	int c = pleaf->nummarksurfaces;

	if (c)
	{
		do
		{
			(*mark)->visframe = r_framecount;
			mark++;
		} while (--c);
	}

// deal with model fragments in this leaf
	if (pleaf->efrags)
	{
		R_StoreEfrags (&pleaf->efrags);
	}

	pleaf->key = r_currentkey;
	r_currentkey++;		// all bmodels in a leaf share the same key
}

fixed_point fp_modelorg[3];

void R_RecursiveWorldNode (mnode_t *node, int clipflags) __attribute__((section(".itcm"), long_call));
void R_RecursiveWorldNode (mnode_t *node, int clipflags)
{
	int			i, side, *pindex;
	vec3_t		acceptpt, rejectpt;
	mplane_t	*plane;
//	msurface_t	*surf, **mark;
	msurface_t	*surf;
	mleaf_t		*pleaf;
//	int		d;
//	float dot;
	int idot;
	//double d, dot;

	if (node->contents == CONTENTS_SOLID)
		return;		// solid

	if (node->visframe != r_visframecount)
		return;

// cull the clipping planes if not trivial accept
// FIXME: the compiler is doing a lousy job of optimizing here; it could be
//  twice as fast in ASM
	if (clipflags)
	{
		if (world_clip(node, &clipflags))
			return;
	}
	
// if a leaf node, draw stuff
	if (node->contents < 0)
	{
		world_leaf_node(pleaf, node);
	}
	else
	{
	// node is just a decision point, so go down the apropriate sides

	// find which side of the node we are on
		plane = node->plane;

		switch (plane->type)
		{
		case PLANE_X:
		case PLANE_Y:
		case PLANE_Z:
			idot = fp_modelorg[plane->type].value - plane->dist.value;
			break;
		default:
#define BIG_TYPE long long
			BIG_TYPE big_temp = (BIG_TYPE)fp_modelorg[0].value * (BIG_TYPE)plane->normal[0].value
					+ (BIG_TYPE)fp_modelorg[1].value * (BIG_TYPE)plane->normal[1].value
					+ (BIG_TYPE)fp_modelorg[2].value * (BIG_TYPE)plane->normal[2].value;
			idot = big_temp >> FP_SCALE_SHIFT;
			idot -= plane->dist.value;
#undef BIG_TYPE

//#define BIG_TYPE long long
//			int big_temp = (int)(((BIG_TYPE)fp_modelorg[0].value * (BIG_TYPE)plane->normal[0].value) >> FP_SCALE_SHIFT)
//					+ (int)(((BIG_TYPE)fp_modelorg[1].value * (BIG_TYPE)plane->normal[1].value) >> FP_SCALE_SHIFT)
//					+ (int)(((BIG_TYPE)fp_modelorg[2].value * (BIG_TYPE)plane->normal[2].value) >> FP_SCALE_SHIFT);
//			idot = big_temp;
//			idot -= plane->dist.value;
//#undef BIG_TYPE
			break;
		}
	
		if (idot >= 0)
			side = 0;
		else
			side = 1;

	// recurse down the children, front side first
		R_RecursiveWorldNode (node->children[side], clipflags);

	// draw stuff
		int c = node->numsurfaces;
		
		//c = 0;

		if (c)
		{
			surf = cl.worldmodel->surfaces + node->firstsurface;

//			if (dot < -BACKFACE_EPSILON)
			if (idot < -82)			//8192 * 0.01
			{
				do
				{
					if ((surf->visframe == r_framecount)
						&& (surf->flags & SURF_PLANEBACK))
					{
						R_RenderPoly (surf);
					}

					surf++;
				} while (--c);
			}
			else if (idot > 82)
			{
				do
				{
					if ((surf->visframe == r_framecount)
						&& !(surf->flags & SURF_PLANEBACK))
					{
						R_RenderPoly (surf);
					}

					surf++;
				} while (--c);
			}

		// all surfaces on the same node share the same sequence number
			r_currentkey++;
		}

	// recurse down the back side
		R_RecursiveWorldNode (node->children[!side], clipflags);
	}
}


#endif



/*
================
R_RenderWorld
================
*/
void ds_pushmatrix(void);
void ds_popmatrix(void);
void ds_rotateX(float);
void ds_rotateY(float);
void ds_rotateZ(float);
void ds_scalef(float x, float y, float z);

void print_top_four_blocks(void);

btofpoly_t	btofpolys[MAX_BTOFPOLYS];

void R_RenderWorld (void)
{
	int			i;
	model_t		*clmodel;
	//btofpoly_t	btofpolys[MAX_BTOFPOLYS];
//	btofpoly_t *btofpolys = (btofpoly_t *)malloc(MAX_BTOFPOLYS * sizeof(btofpoly_t));
	
	if (btofpolys == NULL)
	{
		print_top_four_blocks();
		Sys_Error("not enough memory for btf polys!, %.2fkb\n", (float)(MAX_BTOFPOLYS * sizeof(btofpoly_t)) / 1024);
	}

	pbtofpolys = btofpolys;

	currententity = &cl_entities[0];
	VectorCopy (r_origin, modelorg);
	
	clmodel = currententity->model;
//	r_pcurrentvertbase = clmodel->vertexes;
	r_pcurrentrealvertbase = clmodel->real_vertexes;
//	r_pcurrenttexvertbase = clmodel->tex_vertexes;


	ds_pushmatrix();
	
	ds_rotateX(-90);
	ds_rotateZ(90);
	
	ds_rotateX(-r_refdef.viewangles[2]);
	ds_rotateY(-r_refdef.viewangles[0]);
	ds_rotateZ(-r_refdef.viewangles[1]);
	
//	ds_scalef(1, 1, -1);
	
	scaled_modelorg[0] = floattov16(modelorg[0] * tri2_scale);
	scaled_modelorg[1] = floattov16(modelorg[1] * tri2_scale);
	scaled_modelorg[2] = floattov16(modelorg[2] * tri2_scale);
	
	fp_modelorg[0] = modelorg[0];
	fp_modelorg[1] = modelorg[1];
	fp_modelorg[2] = modelorg[2];
	
//	ds_pushmatrix();
	R_RecursiveWorldNode (clmodel->nodes, 15);
//	ds_popmatrix();
	
	R_DrawParticles ();
	
	ds_popmatrix();
	
	

// if the driver wants the polygons back to front, play the visible ones back
// in that order
	if (r_worldpolysbacktofront)
	{
//		for (i=numbtofpolys-1 ; i>=0 ; i--)
//		{
//			scaled_modelorg[0] = floattov16(modelorg[0] * tri2_scale);
//			scaled_modelorg[1] = floattov16(modelorg[1] * tri2_scale);
//			scaled_modelorg[2] = floattov16(modelorg[2] * tri2_scale);
//			
//			R_RenderPoly (btofpolys[i].psurf, btofpolys[i].clipflags);
//		}
		printf("trying to render back to front!\n");
		*(int *)0 = 0;
		while(1);
	}
//	free(btofpolys);
}


