/*
==================
WriteBrushMap
==================
*/
void WriteBrushMap (char *name, bspbrush_t *list)
{
	FILE	*f;
	side_t	*s;
	int		i;
	winding_t	*w;

	Sys_Printf ("writing %s\n", name);
	f = fopen (name, "wb");
	if (!f)
		Error ("Can't write %s\b", name);

	fprintf (f, "{\n\"classname\" \"worldspawn\"\n");

	for ( ; list ; list=list->next )
	{
		fprintf (f, "{\n");
		for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
		{
			w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);

			fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
			fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
			fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);

			fprintf (f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);
			FreeWinding (w);
		}
		fprintf (f, "}\n");
	}
	fprintf (f, "}\n");

	fclose (f);

}

//===========================================================================
// returns the amount the face and the winding overlap
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
float Q3_FaceOnWinding(dsurface_t *surface, winding_t *winding)
{
	int i;
	float dist, area;
	dplane_t plane;
	vec_t *v1, *v2;
	vec3_t normal, edgevec;
	winding_t *w;

	//copy the winding before chopping
	w = CopyWinding(winding);
	//retrieve the surface plane
	Q3_SurfacePlane(surface, plane.normal, &plane.dist);
	//chop the winding with the surface edge planes
	for (i = 0; i < surface->numVerts && w; i++)
	{
		v1 = drawVerts[surface->firstVert + ((i) % surface->numVerts)].xyz;
		v2 = drawVerts[surface->firstVert + ((i+1) % surface->numVerts)].xyz;
		//create a plane through the edge from v1 to v2, orthogonal to the
		//surface plane and with the normal vector pointing inward
		VectorSubtract(v2, v1, edgevec);
		CrossProduct(edgevec, plane.normal, normal);
		VectorNormalize(normal);
		dist = DotProduct(normal, v1);
		//
		ChopWindingInPlace(&w, normal, dist, -0.1); //CLIP_EPSILON
	} //end for
	if (w)
	{
		area = WindingArea(w);
		FreeWinding(w);
		return area;
	} //end if
	return 0;
} //end of the function Q3_FaceOnWinding

/*
=============
OutputPortal
=============
*/
void OutputPortal(portal_t *p, FILE *glview)
{
	winding_t   *w;
	int sides;

	sides = PortalVisibleSides(p);

	if(!sides)
	{
		return;
	}

	c_glfaces++;

	w = p->winding;

	if(sides == 2)        // back side
	{
		w = ReverseWinding(w);
	}

	OutputWinding(w, glview);

	if(sides == 2)
	{
		FreeWinding(w);
	}
}

/**
 * @sa AllocPortal
 */
void FreePortal (portal_t *p)
{
	if (p->winding)
		FreeWinding(p->winding);
	if (threadstate.numthreads == 1)
		c_active_portals--;
	Mem_Free(p);
}

void FreePortal (portal_t *p)
{
	if (p->winding)
		FreeWinding (p->winding);
	if (numthreads == 1)
		c_active_portals--;
	free (p);
}

/*
================
FreeBspFace
================
*/
void FreeBspFace(bspFace_t * f)
{
	if(f->w)
	{
		FreeWinding(f->w);
	}
	free(f);
}

/*
==================
CM_ValidateFacet

If the facet isn't bounded by its borders, we screwed up.
==================
*/
static qboolean CM_ValidateFacet( facet_t *facet ) {
	float plane[4];
	int j;
	winding_t   *w;
	vec3_t bounds[2];

	if ( facet->surfacePlane == -1 ) {
		return qfalse;
	}

	Vector4Copy( planes[ facet->surfacePlane ].plane, plane );
	w = BaseWindingForPlane( plane,  plane[3] );
	for ( j = 0 ; j < facet->numBorders && w ; j++ ) {
		if ( facet->borderPlanes[j] == -1 ) {
			FreeWinding( w );
			return qfalse;
		}
		Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane );
		if ( !facet->borderInward[j] ) {
			VectorSubtract( vec3_origin, plane, plane );
			plane[3] = -plane[3];
		}
		ChopWindingInPlace( &w, plane, plane[3], 0.1f );
	}

	if ( !w ) {
		return qfalse;      // winding was completely chopped away
	}

	// see if the facet is unreasonably large
	WindingBounds( w, bounds[0], bounds[1] );
	FreeWinding( w );

	for ( j = 0 ; j < 3 ; j++ ) {
		if ( bounds[1][j] - bounds[0][j] > MAX_MAP_BOUNDS ) {
			return qfalse;      // we must be missing a plane
		}
		if ( bounds[0][j] >= MAX_MAP_BOUNDS ) {
			return qfalse;
		}
		if ( bounds[1][j] <= -MAX_MAP_BOUNDS ) {
			return qfalse;
		}
	}
	return qtrue;       // winding is fine
}

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_CheckFaceWindingPlane( tmp_face_t *face ) {
	float dist, sign1, sign2;
	vec3_t normal;
	plane_t *plane;
	winding_t *w;

	//check if the winding plane is the same as the face plane
	WindingPlane( face->winding, normal, &dist );
	plane = &mapplanes[face->planenum];
	//
	sign1 = DotProduct( plane->normal, normal );
	//
	if ( fabs( dist - plane->dist ) > 0.4 ||
		 fabs( normal[0] - plane->normal[0] ) > 0.0001 ||
		 fabs( normal[1] - plane->normal[1] ) > 0.0001 ||
		 fabs( normal[2] - plane->normal[2] ) > 0.0001 ) {
		VectorInverse( normal );
		dist = -dist;
		if ( fabs( dist - plane->dist ) > 0.4 ||
			 fabs( normal[0] - plane->normal[0] ) > 0.0001 ||
			 fabs( normal[1] - plane->normal[1] ) > 0.0001 ||
			 fabs( normal[2] - plane->normal[2] ) > 0.0001 ) {
			Log_Write( "AAS_CheckFaceWindingPlane: face %d winding plane unequal to face plane\r\n",
					   face->num );
			//
			sign2 = DotProduct( plane->normal, normal );
			if ( ( sign1 < 0 && sign2 > 0 ) ||
				 ( sign1 > 0 && sign2 < 0 ) ) {
				Log_Write( "AAS_CheckFaceWindingPlane: face %d winding reversed\r\n",
						   face->num );
				w = face->winding;
				face->winding = ReverseWinding( w );
				FreeWinding( w );
			} //end if
		} //end if
		else
		{
			Log_Write( "AAS_CheckFaceWindingPlane: face %d winding reversed\r\n",
					   face->num );
			w = face->winding;
			face->winding = ReverseWinding( w );
			FreeWinding( w );
		} //end else
	} //end if
} //end of the function AAS_CheckFaceWindingPlane

void FreePortal(portal_t * p) {

    if (p->winding)
        FreeWinding(p->winding);

    if (debug)
        SDL_SemWait(semaphores.active_portals);

    Mem_Free(p);
}

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_TryMergeFaces( tmp_face_t *face1, tmp_face_t *face2 ) {
	winding_t *neww;

#ifdef DEBUG
	if ( !face1->winding ) {
		Error( "face1 %d without winding", face1->num );
	}
	if ( !face2->winding ) {
		Error( "face2 %d without winding", face2->num );
	}
#endif //DEBUG
	   //
	if ( face1->faceflags != face2->faceflags ) {
		return false;
	}
	//NOTE: if the front or back area is zero this doesn't mean there's
	//a real area. It means there's solid at that side of the face
	//if both faces have the same front area
	if ( face1->frontarea == face2->frontarea ) {
		//if both faces have the same back area
		if ( face1->backarea == face2->backarea ) {
			//if the faces are in the same plane
			if ( face1->planenum == face2->planenum ) {
				//if they have both a front and a back area (no solid on either side)
				if ( face1->frontarea && face1->backarea ) {
					neww = MergeWindings( face1->winding, face2->winding,
										  mapplanes[face1->planenum].normal );
				} //end if
				else
				{
					//this function is to be found in l_poly.c
					neww = TryMergeWinding( face1->winding, face2->winding,
											mapplanes[face1->planenum].normal );
				} //end else
				if ( neww ) {
					FreeWinding( face1->winding );
					face1->winding = neww;
					if ( face2->frontarea ) {
						AAS_RemoveFaceFromArea( face2, face2->frontarea );
					}
					if ( face2->backarea ) {
						AAS_RemoveFaceFromArea( face2, face2->backarea );
					}
					AAS_FreeTmpFace( face2 );
					return true;
				} //end if
			} //end if
			else if ( ( face1->planenum & ~1 ) == ( face2->planenum & ~1 ) ) {
				Log_Write( "face %d and %d, same front and back area but flipped planes\r\n",
						   face1->num, face2->num );
			} //end if
		} //end if
	} //end if
	return false;
} //end of the function AAS_TryMergeFaces

//===========================================================================
// NOTE: the original face is invalid after splitting
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_SplitFace( tmp_face_t *face, vec3_t normal, float dist,
					tmp_face_t **frontface, tmp_face_t **backface ) {
	winding_t *frontw, *backw;

	//
	*frontface = *backface = NULL;

	ClipWindingEpsilon( face->winding, normal, dist, FACECLIP_EPSILON, &frontw, &backw );

#ifdef DEBUG
	//
	if ( frontw ) {
		if ( WindingIsTiny( frontw ) ) {
			Log_Write( "AAS_SplitFace: tiny back face\r\n" );
			FreeWinding( frontw );
			frontw = NULL;
		} //end if
	} //end if
	if ( backw ) {
		if ( WindingIsTiny( backw ) ) {
			Log_Write( "AAS_SplitFace: tiny back face\r\n" );
			FreeWinding( backw );
			backw = NULL;
		} //end if
	} //end if
#endif //DEBUG
	   //if the winding was split
	if ( frontw ) {
		//check bounds
		( *frontface ) = AAS_AllocTmpFace();
		( *frontface )->planenum = face->planenum;
		( *frontface )->winding = frontw;
		( *frontface )->faceflags = face->faceflags;
	} //end if
	if ( backw ) {
		//check bounds
		( *backface ) = AAS_AllocTmpFace();
		( *backface )->planenum = face->planenum;
		( *backface )->winding = backw;
		( *backface )->faceflags = face->faceflags;
	} //end if
} //end of the function AAS_SplitFace

/**
 * @sa AllocBrush
 */
void FreeBrush (bspbrush_t* brushes)
{
	int i;

	for (i = 0; i < brushes->numsides; i++)
		if (brushes->sides[i].winding)
			FreeWinding(brushes->sides[i].winding);
	Mem_Free(brushes);
	if (threadstate.numthreads == 1)
		c_active_brushes--;
}

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FreeTmpFace(tmp_face_t *tmpface)
{
	if (tmpface->l_next) tmpface->l_next->l_prev = tmpface->l_prev;
	if (tmpface->l_prev) tmpface->l_prev->l_next = tmpface->l_next;
	else tmpaasworld.faces = tmpface->l_next;
	//free the winding
	if (tmpface->winding) FreeWinding(tmpface->winding);
	//free the face
	FreeMemory(tmpface);
	tmpaasworld.numfaces--;
} //end of the function AAS_FreeTmpFace

	bool TestPointAgainstSkySurface( Vector const &pt, dface_t *pFace )
	{
		// Create sky face winding.
		winding_t *pWinding = WindingFromFace( pFace, Vector( 0.0f, 0.0f, 0.0f ) );

		// Test point in winding. (Since it is at the node, it is in the plane.)
		bool bRet = PointInWinding( pt, pWinding );

		FreeWinding( pWinding );

		return bRet;
	}

/*
==================
MakeNodePortal

create the new portal by taking the full plane winding for the cutting plane
and clipping it by all of parents of this node
==================
*/
void MakeNodePortal (node_t *node)
{
	portal_t	*new_portal, *p;
	winding_t	*w;
	Vector		normal;
	float		dist = 0.0f;
	int			side = 0;

	w = BaseWindingForNode (node);

	// clip the portal by all the other portals in the node
	for (p = node->portals ; p && w; p = p->next[side])	
	{
		if (p->nodes[0] == node)
		{
			side = 0;
			VectorCopy (p->plane.normal, normal);
			dist = p->plane.dist;
		}
		else if (p->nodes[1] == node)
		{
			side = 1;
			VectorSubtract (vec3_origin, p->plane.normal, normal);
			dist = -p->plane.dist;
		}
		else
		{
			Error ("CutNodePortals_r: mislinked portal");
		}

		ChopWindingInPlace (&w, normal, dist, 0.1);
	}

	if (!w)
	{
		return;
	}

	if (WindingIsTiny (w))
	{
		c_tinyportals++;
		FreeWinding (w);
		return;
	}


	new_portal = AllocPortal ();
	new_portal->plane = mapplanes[node->planenum];
	new_portal->onnode = node;
	new_portal->winding = w;	

	AddPortalToNodes (new_portal, node->children[0], node->children[1]);
}

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void FreeBrushWindings(mapbrush_t *brush)
{
	int n;
	side_t *side;
	//
	for (n = 0; n < brush->numsides; n++)
	{
		side = brush->original_sides + n;
		//
		if (side->winding) FreeWinding(side->winding);
	} //end for
} //end of the function FreeBrushWindings

//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void FreeBrush (bspbrush_t *brushes)
{
	int			i;

	for (i=0 ; i<brushes->numsides ; i++)
		if (brushes->sides[i].winding)
			FreeWinding(brushes->sides[i].winding);
	if (numthreads == 1)
	{
		c_active_brushes--;
		c_brushmemory -= MemorySize(brushes);
		if (c_brushmemory < 0) c_brushmemory = 0;
	} //end if
	FreeMemory(brushes);
} //end of the function FreeBrush

void RadFreeLights( void )
{
    light_t        *light, *next;
    
    
    /* delete lights */
    for( light = lights; light; light = next )
    {
        next = light->next;
        if( light->w != NULL )
            FreeWinding( light->w );
        free( light );
    }
    numLights = 0;
    lights = NULL;
}

/*
================
TestExpandBrushes

Expands all the brush planes and saves a new map out
================
*/
void TestExpandBrushes(void)
{
	FILE       *f;
	side_t     *s;
	int        i, j, bn;
	winding_t  *w;
	char       *name = "expanded.map";
	mapbrush_t *brush;
	vec_t      dist;

	Log_Print("writing %s\n", name);
	f = fopen(name, "wb");
	if (!f)
	{
		Error("Can't write %s\n", name);
	}

	fprintf(f, "{\n\"classname\" \"worldspawn\"\n");

	for (bn = 0 ; bn < nummapbrushes ; bn++)
	{
		brush = &mapbrushes[bn];
		fprintf(f, "{\n");
		for (i = 0 ; i < brush->numsides ; i++)
		{
			s    = brush->original_sides + i;
			dist = mapplanes[s->planenum].dist;
			for (j = 0 ; j < 3 ; j++)
				dist += fabs(16 * mapplanes[s->planenum].normal[j]);

			w = BaseWindingForPlane(mapplanes[s->planenum].normal, dist);

			fprintf(f, "( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
			fprintf(f, "( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
			fprintf(f, "( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);

			fprintf(f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);
			FreeWinding(w);
		}
		fprintf(f, "}\n");
	}
	fprintf(f, "}\n");

	fclose(f);

	Error("can't proceed after expanding brushes");
} //end of the function TestExpandBrushes

/*
==================
CM_ValidateFacet

If the facet isn't bounded by its borders, we screwed up.
==================
*/
static qboolean CM_ValidateFacet( facet_t *facet ) {
	planeDef_t	plane;
	int			j;
	winding_t	*w;
	bvec3_t		bounds[2];

	if ( facet->surfacePlane == -1 ) {
		return qfalse;
	}

	plane=planes[ facet->surfacePlane ].pd;
	w = BaseWindingForPlane( plane.normal,  plane.dist );
	for ( j = 0 ; j < facet->numBorders && w ; j++ ) {
		if ( facet->borderPlanes[j] == -1 ) {
			return qfalse;
		}
		plane=planes[ facet->borderPlanes[j] ].pd;
		if ( !facet->borderInward[j] ) {
			VectorSubtract( avec3_origin, plane.normal, plane.normal );
			plane.dist = -plane.dist;
		}
		ChopWindingInPlace( &w, plane.normal, plane.dist, BFIXED(0,1) );
	}

	if ( !w ) {
		return qfalse;		// winding was completely chopped away
	}

	// see if the facet is unreasonably large
	WindingBounds( w, bounds[0], bounds[1] );
	FreeWinding( w );
	
	for ( j = 0 ; j < 3 ; j++ ) {
		if ( bounds[1][j] - bounds[0][j] > BFIXED(MAX_MAP_BOUNDS,0) ) {
			return qfalse;		// we must be missing a plane
		}
		if ( bounds[0][j] >= BFIXED(MAX_MAP_BOUNDS,0) ) {
			return qfalse;
		}
		if ( bounds[1][j] <= -BFIXED(MAX_MAP_BOUNDS,0) ) {
			return qfalse;
		}
	}
	return qtrue;		// winding is fine
}