/**
 * @brief Create a massive polygon for the specified plane. This will be used
 * as the basis for all clipping operations against the plane. Double precision
 * is used to produce very accurate results; this is an improvement over the
 * Quake II tools.
 */
winding_t *WindingForPlane(const vec3_t normal, const vec_t dist) {
	dvec3_t org, vnormal, vright, vup;
	int32_t i;

	// find the major axis
	vec_t max = -BOGUS_RANGE;
	int32_t x = -1;
	for (i = 0; i < 3; i++) {
		const vec_t v = fabs(normal[i]);
		if (v > max) {
			x = i;
			max = v;
		}
	}
	if (x == -1) {
		Com_Error(ERROR_FATAL, "No axis found\n");
	}

	switch (x) {
		case 0:
		case 1:
			VectorSet(vright, -normal[1], normal[0], 0.0);
			break;
		case 2:
			VectorSet(vright, 0.0, -normal[2], normal[1]);
			break;
		default:
			Com_Error(ERROR_FATAL, "Bad axis\n");
	}

	VectorScale(vright, MAX_WORLD_COORD * 8.0, vright);

	VectorCopy(normal, vnormal);

	// CrossProduct(vnormal, vright, vup);
	vup[0] = vnormal[1] * vright[2] - vnormal[2] * vright[1];
	vup[1] = vnormal[2] * vright[0] - vnormal[0] * vright[2];
	vup[2] = vnormal[0] * vright[1] - vnormal[1] * vright[0];

	VectorScale(vnormal, dist, org);

	// project a really big	axis aligned box onto the plane
	winding_t *w = AllocWinding(4);

	VectorSubtract(org, vright, w->points[0]);
	VectorAdd(w->points[0], vup, w->points[0]);

	VectorAdd(org, vright, w->points[1]);
	VectorAdd(w->points[1], vup, w->points[1]);

	VectorAdd(org, vright, w->points[2]);
	VectorSubtract(w->points[2], vup, w->points[2]);

	VectorSubtract(org, vright, w->points[3]);
	VectorSubtract(w->points[3], vup, w->points[3]);

	w->num_points = 4;

	return w;
}

winding_t *WindingFromDrawSurf( mapDrawSurface_t *ds ){
	winding_t   *w;
	int i;

	// we use the first point of the surface, maybe something more clever would be useful
	// (actually send the whole draw surface would be cool?)
	if ( ds->numVerts >= MAX_POINTS_ON_WINDING ) {
		int max = ds->numVerts;
		vec3_t p[256];

		if ( max > 256 ) {
			max = 256;
		}

		for ( i = 0 ; i < max ; i++ ) {
			VectorCopy( ds->verts[i].xyz, p[i] );
		}

		xml_Winding( "WindingFromDrawSurf failed: MAX_POINTS_ON_WINDING exceeded", p, max, qtrue );
	}

	w = AllocWinding( ds->numVerts );
	w->numpoints = ds->numVerts;
	for ( i = 0 ; i < ds->numVerts ; i++ ) {
		VectorCopy( ds->verts[i].xyz, w->p[i] );
	}
	return w;
}

void DWinding::RemoveColinearPoints()
{
	vec3_t	p2[MAX_POINTS_ON_WINDING];

	int nump = 0;
	for (int i = 0; i < numpoints; i++)
	{
		int j = (i+1)%numpoints;
		int k = (i+numpoints-1)%numpoints;

		vec3_t	v1, v2;
		VectorSubtract (p[j], p[i], v1);
		VectorSubtract (p[i], p[k], v2);
		VectorNormalize(v1, v1);
		VectorNormalize(v2, v2);

		if (DotProduct(v1, v2) < 0.999)
		{
			VectorCopy (p[i], p2[nump]);
			nump++;
		}
	}

	if (nump == numpoints)
		return;

	AllocWinding(nump);
	memcpy (p, p2, nump*sizeof(vec3_t));
}

//===========================================================================
// adds the given point to a winding at the given spot
// (for instance when spot is zero then the point is added at position zero)
// the original winding is NOT freed
//
// Parameter:				-
// Returns:					the new winding with the added point
// Changes Globals:		-
//===========================================================================
winding_t *AddWindingPoint( winding_t *w, vec3_t point, int spot ) {
	int i, j;
	winding_t *neww;

	if ( spot > w->numpoints ) {
		Error( "AddWindingPoint: num > w->numpoints" );
	} //end if
	if ( spot < 0 ) {
		Error( "AddWindingPoint: num < 0" );
	} //end if
	neww = AllocWinding( w->numpoints + 1 );
	neww->numpoints = w->numpoints + 1;
	for ( i = 0, j = 0; i < neww->numpoints; i++ )
	{
		if ( i == spot ) {
			VectorCopy( point, neww->p[i] );
		} //end if
		else
		{
			VectorCopy( w->p[j], neww->p[i] );
			j++;
		} //end else
	} //end for
	return neww;
} //end of the function AddWindingPoint

/*
=============
WindingFromFace
=============
*/
winding_t	*WindingFromFace (dface_t *f)
{
	int			i;
	int			se;
	dvertex_t	*dv;
	int			v;
	winding_t	*w;

	w = AllocWinding (f->numedges);
	w->numpoints = f->numedges;

	for (i=0 ; i<f->numedges ; i++)
	{
		se = dsurfedges[f->firstedge + i];
		if (se < 0)
			v = dedges[-se].v[1];
		else
			v = dedges[se].v[0];

		dv = &dvertexes[v];
		VectorCopy (dv->point, w->p[i]);
	}

	RemoveColinearPoints (w);

	return w;
}

static void ProjectDecalOntoTriangles( decalProjector_t *dp, mapDrawSurface_t *ds )
{
	int			i;
	vec4_t		plane;
	float		d;
	winding_t	*w;
	
	
	/* triangle surfaces without shaders don't get marks by default */
	if( ds->type == SURFACE_TRIANGLES && ds->shaderInfo->shaderText == NULL )
		return;
	
	/* backface check */
	if( ds->planar )
	{
		VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
		plane[ 3 ] = mapplanes[ ds->planeNum ].dist + DotProduct( plane, entityOrigin );
		d = DotProduct( dp->planes[ 0 ], plane );
		if( d < -0.0001f )
			return;
	}
	
	/* iterate through triangles */
	for( i = 0; i < ds->numIndexes; i += 3 )
	{
		/* generate decal */
		w = AllocWinding( 3 );
		w->numpoints = 3;
		VectorCopy( ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
		VectorCopy( ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
		VectorCopy( ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
		ProjectDecalOntoWinding( dp, ds, w );
	}
}

/**
 * @brief
 */
winding_t *WindingForFace(const bsp_face_t *f) {
	int32_t i;
	bsp_vertex_t *dv;
	int32_t v;
	winding_t *w;

	w = AllocWinding(f->num_edges);
	w->num_points = f->num_edges;

	for (i = 0; i < f->num_edges; i++) {
		const int32_t se = bsp_file.face_edges[f->first_edge + i];
		if (se < 0) {
			v = bsp_file.edges[-se].v[1];
		} else {
			v = bsp_file.edges[se].v[0];
		}

		dv = &bsp_file.vertexes[v];
		VectorCopy(dv->point, w->points[i]);
	}

	RemoveColinearPoints(w);

	return w;
}

/*
==================
CopyWinding
==================
*/
winding_t *CopyWinding(winding_t * w) {
	intptr_t        size;
	winding_t      *c;

	c = AllocWinding(w->numpoints);
	size = (intptr_t) ((winding_t *)0)->p[w->numpoints];
	Com_Memcpy(c, w, size);
	return c;
}

/*
=======================================================================================================================================
BaseWindingForPlane
=======================================================================================================================================
*/
winding_t *BaseWindingForPlane(vec3_t normal, vec_t dist) {
	int i, x = -1;
	vec_t max = -MAX_MAP_BOUNDS, v;
	vec3_t org, vright, vup;
	winding_t *w;

	// find the major axis
	for (i = 0; i < 3; i++) {
		v = Q_fabs(normal[i]);

		if (v > max) {
			x = i;
			max = v;
		}
	}

	if (x == -1) {
		Com_Error(ERR_DROP, "BaseWindingForPlane: no axis found");
	}

	VectorCopy(vec3_origin, vup);

	switch (x) {
		case 0:
		case 1:
			vup[2] = 1;
			break;
		case 2:
			vup[0] = 1;
			break;
	}

	v = DotProduct(vup, normal);

	VectorMA(vup, -v, normal, vup);
	vec3_norm2(vup, vup);
	VectorScale(normal, dist, org);
	vec3_cross(vup, normal, vright);
	VectorScale(vup, MAX_MAP_BOUNDS, vup);
	VectorScale(vright, MAX_MAP_BOUNDS, vright);
	// project a really big axis aligned box onto the plane
	w = AllocWinding(4);

	VectorSubtract(org, vright, w->p[0]);
	VectorAdd(w->p[0], vup, w->p[0]);
	VectorAdd(org, vright, w->p[1]);
	VectorAdd(w->p[1], vup, w->p[1]);
	VectorAdd(org, vright, w->p[2]);
	VectorSubtract(w->p[2], vup, w->p[2]);
	VectorSubtract(org, vright, w->p[3]);
	VectorSubtract(w->p[3], vup, w->p[3]);

	w->numpoints = 4;

	return w;
}

/*
==================
CopyWinding
==================
*/
winding_t *CopyWinding (winding_t *w)
{
	int			size;
	winding_t	*c;

	c = AllocWinding (w->numpoints);
	size = sizeof(*w) + sizeof(*w->p) * w->numpoints;
	memcpy (c, w, size);
	return c;
}

/*
==================
CopyWinding
==================
*/
winding_t	*CopyWinding (winding_t *w)
{
    int			size;
    winding_t	*c;

    c = AllocWinding (w->numpoints);
    size = sizeof(vec3_t) * w->numpoints + sizeof(int);
    Com_Memcpy (c, w, size);
    return c;
}

/*
==================
CopyWinding
==================
*/
winding_t	*CopyWinding (winding_t *w)
{
	int			size;
	winding_t	*c;

	c = AllocWinding (w->numpoints);
	size = (int)((size_t)((winding_t *)0)->p[w->numpoints]);
	memcpy (c, w, size);
	return c;
}

/*
==================
CopyWinding
==================
*/
winding_t	*CopyWinding (winding_t *w)
{
	unsigned long	size;
	winding_t	*c;

	c = AllocWinding (w->numpoints);
	size = (long)((winding_t *)0)->p[w->numpoints];
	Com_Memcpy (c, w, size);
	return c;
}

/*
==================
CopyWinding
==================
*/
winding_t *CopyWinding (winding_t *w)
{
	int			size;
	winding_t	*c;

	c = AllocWinding (w->numpoints);
	c->numpoints = w->numpoints;
	size = w->numpoints*sizeof(w->p[0]);
	memcpy (c->p, w->p, size);
	return c;
}

/*
==================
CopyWinding
==================
*/
winding_t *CopyWinding (winding_t *w)
{
	int			size;
	winding_t	*c;

	c = AllocWinding (w->numpoints);
	// Compute size the same way than in AllocWinding
	size = sizeof(vec_t)*3*w->numpoints + sizeof(int);
	memcpy (c, w, size);
	return c;
}

/*
==================
CopyWinding
==================
*/
winding_t	*CopyWinding (winding_t *w)
{
	size_t			size;
	winding_t	*c;

	if (!w) Error("CopyWinding: winding is NULL");

	c = AllocWinding (w->numpoints);
	size = (size_t)((winding_t *)NULL)->p[w->numpoints];
	memcpy (c, w, size);
	return c;
}

/*
   ==================
   CopyWinding
   ==================
 */
winding_t   *CopyWinding( winding_t *w ){
	size_t size;
	winding_t   *c;

	if ( !w ) {
		Error( "CopyWinding: winding is NULL" );
	}

	c = AllocWinding( w->numpoints );
	size = sizeof( *w ) + sizeof( *w->p ) * w->numpoints;
	memcpy( c, w, size );
	return c;
}

/*
====================
WindingFromDrawSurf
====================
*/
winding_t      *WindingFromDrawSurf(drawSurface_t * ds)
{
	winding_t      *w;
	int             i;

	w = AllocWinding(ds->numVerts);
	w->numpoints = ds->numVerts;
	for(i = 0; i < ds->numVerts; i++)
	{
		VectorCopy(ds->verts[i].xyz, w->p[i]);
	}
	return w;
}

/*
==================
CopyWinding
==================
*/
winding_t	*CopyWinding (winding_t *w)
{
	int			size;
	winding_t	*c;
	
	c = AllocWinding(w->numpoints);
	c->next = 0;
	c->numpoints = w->numpoints;
	c->parent = w->parent;
	c->children[0] = w->children[0];
	c->children[1] = w->children[1];
	memcpy (c->p, w->p, w->numpoints*sizeof(vertex_t));
	return c;
}

/*
==================
CopyWinding
==================
*/
winding_t   *CopyWinding( winding_t *w ) {
	int size;
	winding_t   *c;

	c = AllocWinding( w->numpoints );
	size = (int)( (winding_t *)0 )->p[w->numpoints];

#if defined RTCW_SP
	Com_Memcpy( c, w, size );
#else
	memcpy( c, w, size );
#endif // RTCW_XX

	return c;
}