自学教程：C++ AllocWinding函数代码示例

/** * @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;}

/*==================ReverseWinding==================*/winding_t *ReverseWinding( winding_t *w ){	int		i;	winding_t *neww;	if( w->numpoints > MAX_POINTS_ON_WINDING )		Error( "ReverseWinding: %i points", w->numpoints );	neww = AllocWinding( w->numpoints );	neww->numpoints = w->numpoints;	for( i = 0; i < w->numpoints; i++ )		// add points backwards		VectorCopy( w->points[w->numpoints - 1 - i], neww->points[i] );#ifdef PARANOID	CheckWinding( neww );#endif	return neww;}

static winding_t* WindingFromFace (const dBspSurface_t* f){	int i, v;	winding_t* w;	w = AllocWinding(f->numedges);	w->numpoints = f->numedges;	for (i = 0; i < f->numedges; i++) {		const int se = curTile->surfedges[f->firstedge + i];		if (se < 0)			v = curTile->edges[-se].v[1];		else			v = curTile->edges[se].v[0];		dBspVertex_t* dv = &curTile->vertexes[v];		VectorCopy(dv->point, w->p[i]);	}	RemoveColinearPoints(w);	return w;}

//-----------------------------------------------------------------------------// Purpose: // Input  : *pPatch - //			*pPoints - //			&vecNormal - //			flArea - //-----------------------------------------------------------------------------bool CVRADDispColl::InitPatch( int iPatch, int iParentPatch, int iChild, Vector *pPoints, int *pIndices, float &flArea ){	// Get the current patch.	CPatch *pPatch = &g_Patches[iPatch];	if ( !pPatch )		return false;	// Clear the patch data.	memset( pPatch, 0, sizeof( CPatch ) );	// Setup the parent if we are not the parent.	CPatch *pParentPatch = NULL;	if ( iParentPatch != g_Patches.InvalidIndex() )	{		// Get the parent patch.		pParentPatch = &g_Patches[iParentPatch];		if ( !pParentPatch )			return false;	}	// Attach the face to the correct lists.	if ( !pParentPatch )	{		// This is a parent.		pPatch->ndxNext = g_FacePatches.Element( GetParentIndex() );		g_FacePatches[GetParentIndex()] = iPatch;		pPatch->faceNumber = GetParentIndex();	}	else	{		pPatch->ndxNext = g_Patches.InvalidIndex();		pPatch->faceNumber = pParentPatch->faceNumber;		// Attach to the parent patch.		if ( iChild == 0 )		{			pParentPatch->child1 = iPatch;		}		else		{			pParentPatch->child2 = iPatch;		}	}	// Initialize parent and children indices.	pPatch->child1 = g_Patches.InvalidIndex();	pPatch->child2 = g_Patches.InvalidIndex();	pPatch->ndxNextClusterChild = g_Patches.InvalidIndex();	pPatch->ndxNextParent = g_Patches.InvalidIndex();	pPatch->parent = iParentPatch;	// Get triangle edges.	Vector vecEdges[3];	vecEdges[0] = pPoints[1] - pPoints[0];	vecEdges[1] = pPoints[2] - pPoints[0];	vecEdges[2] = pPoints[2] - pPoints[1];	// Find the longest edge.//	float flEdgeLength = 0.0f;//	for ( int iEdge = 0; iEdge < 3; ++iEdge )//	{//		if ( flEdgeLength < vecEdges[iEdge].Length() )//		{//			flEdgeLength = vecEdges[iEdge].Length();//		}//	}	// Calculate the triangle normal and area.	Vector vecNormal = vecEdges[1].Cross( vecEdges[0] );	flArea = VectorNormalize( vecNormal );	flArea *= 0.5f;	// Initialize the patch scale.	pPatch->scale[0] = pPatch->scale[1] = 1.0f;	// Set the patch chop - minchop (that is what the minimum area is based on).	pPatch->chop = dispchop;	// Displacements are not sky!	pPatch->sky = false;	// Copy the winding.	Vector vecCenter( 0.0f, 0.0f, 0.0f );	pPatch->winding = AllocWinding( 3 );	pPatch->winding->numpoints = 3;	for ( int iPoint = 0; iPoint < 3; ++iPoint )	{		VectorCopy( pPoints[iPoint], pPatch->winding->p[iPoint] );		VectorAdd( pPoints[iPoint], vecCenter, vecCenter );		pPatch->indices[iPoint] = static_cast<short>( pIndices[iPoint] );	}//.........这里部分代码省略.........

/** * @brief If two polygons share a common edge and the edges that meet at the * common points are both inside the other polygons, merge them * @return nullptr if the faces couldn't be merged, or the new winding. * @note The originals will NOT be freed. */static winding_t* TryMergeWinding (winding_t* f1, winding_t* f2, const vec3_t planenormal){	vec_t* p1, *p2, *back;	winding_t* newf;	int i, j, k, l;	vec3_t normal, delta;	vec_t dot;	bool keep1, keep2;	p1 = p2 = nullptr;	j = 0;	/* find a common edge */	for (i = 0; i < f1->numpoints; i++) {		p1 = f1->p[i];		p2 = f1->p[(i + 1) % f1->numpoints];		for (j = 0; j < f2->numpoints; j++) {			const vec_t* p3 = f2->p[j];			const vec_t* p4 = f2->p[(j + 1) % f2->numpoints];			for (k = 0; k < 3; k++) {				if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)					break;				if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)					break;			}			if (k == 3)				break;		}		if (j < f2->numpoints)			break;	}	/* no matching edges */	if (i == f1->numpoints)		return nullptr;	/* check slope of connected lines */	/* if the slopes are colinear, the point can be removed */	back = f1->p[(i + f1->numpoints - 1) % f1->numpoints];	VectorSubtract(p1, back, delta);	CrossProduct(planenormal, delta, normal);	VectorNormalize(normal);	back = f2->p[(j + 2) % f2->numpoints];	VectorSubtract(back, p1, delta);	dot = DotProduct(delta, normal);	/* not a convex polygon */	if (dot > CONTINUOUS_EPSILON)		return nullptr;	keep1 = (bool)(dot < -CONTINUOUS_EPSILON);	back = f1->p[(i + 2) % f1->numpoints];	VectorSubtract(back, p2, delta);	CrossProduct(planenormal, delta, normal);	VectorNormalize(normal);	back = f2->p[(j + f2->numpoints - 1) % f2->numpoints];	VectorSubtract(back, p2, delta);	dot = DotProduct(delta, normal);	/* not a convex polygon */	if (dot > CONTINUOUS_EPSILON)		return nullptr;	keep2 = (bool)(dot < -CONTINUOUS_EPSILON);	/* build the new polygon */	newf = AllocWinding(f1->numpoints + f2->numpoints);	/* copy first polygon */	for (k = (i + 1) % f1->numpoints; k != i; k = (k + 1) % f1->numpoints) {		if (k == (i + 1) % f1->numpoints && !keep2)			continue;		VectorCopy(f1->p[k], newf->p[newf->numpoints]);		newf->numpoints++;	}	/* copy second polygon */	for (l = (j + 1) % f2->numpoints; l != j; l = (l + 1) % f2->numpoints) {		if (l == (j + 1) % f2->numpoints && !keep1)			continue;		VectorCopy(f2->p[l], newf->p[newf->numpoints]);		newf->numpoints++;	}	return newf;}

void AddWindingToConvexHull(winding_t * w, winding_t ** hull, vec3_t normal) {	int             i, j, k, numHullPoints, numNew;	float          *p, *copy, d;	vec3_t          dir;	vec3_t          hullPoints[MAX_HULL_POINTS], newHullPoints[MAX_HULL_POINTS], hullDirs[MAX_HULL_POINTS];	bool        hullSide[MAX_HULL_POINTS], outside;	if(!*hull) {		*hull = CopyWinding(w);		return;	}	numHullPoints = (*hull)->numpoints;	Com_Memcpy(hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t));	for(i = 0; i < w->numpoints; i++) {		p = w->p[i];		// calculate hull side vectors		for(j = 0; j < numHullPoints; j++) {			k = (j + 1) % numHullPoints;			VectorSubtract(hullPoints[k], hullPoints[j], dir);			VectorNormalize2(dir, dir);			CrossProduct(normal, dir, hullDirs[j]);		}		outside = false;		for(j = 0; j < numHullPoints; j++) {			VectorSubtract(p, hullPoints[j], dir);			d = DotProduct(dir, hullDirs[j]);			if(d >= ON_EPSILON) {				outside = true;			}			if(d >= -ON_EPSILON) {				hullSide[j] = true;			} else {				hullSide[j] = false;			}		}		// if the point is effectively inside, do nothing		if(!outside) {			continue;		}		// find the back side to front side transition		for(j = 0; j < numHullPoints; j++) {			if(!hullSide[j % numHullPoints] && hullSide[(j + 1) % numHullPoints]) {				break;			}		}		if(j == numHullPoints) {			continue;		}		// insert the point here		VectorCopy(p, newHullPoints[0]);		numNew = 1;		// copy over all points that aren't double fronts		j = (j + 1) % numHullPoints;		for(k = 0; k < numHullPoints; k++) {			if(hullSide[(j + k) % numHullPoints] && hullSide[(j + k + 1) % numHullPoints]) {				continue;			}			copy = hullPoints[(j + k + 1) % numHullPoints];			VectorCopy(copy, newHullPoints[numNew]);			numNew++;		}		numHullPoints = numNew;		Com_Memcpy(hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t));	}	FreeWinding(*hull);	w = AllocWinding(numHullPoints);	w->numpoints = numHullPoints;	*hull = w;	Com_Memcpy(w->p, hullPoints, numHullPoints * sizeof(vec3_t));}