Renegade/Code/ww3d2/stripoptimizer.cpp

/*
**	Command & Conquer Renegade(tm)
**	Copyright 2025 Electronic Arts 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 3 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, see <http://www.gnu.org/licenses/>.
*/

#include "stripoptimizer.h"
#include "hashtemplate.h"
#include "wwdebug.h"

template <class T> inline void swap (T& a, T& b)
{
	T t(a);
	a = b;
	b = t;
}

//------------------------------------------------------------------------
// Prototypes for sort functions. Note that class T must have
// operators =, > and < in order for the functions to compile.
//------------------------------------------------------------------------

template <class T> inline void Insertion_Sort	(T* a, int N);
template <class T> inline void Quick_Sort		(T* a, int N);

template <class T> inline void Insertion_Sort (T* a, int N)
{
	for (int i = 1; i < N; i++)
	if (a[i-1] > a[i])
	{
		T		v	= a[i];
		int		j	= i;
		while (a[j-1]> v)
		{
			a[j] = a[j-1];						// copy data
			j--;
			if (!j)
				break;
		};
		a[j]	= v;
	}
}


template <class T> inline void Quick_Sort (T* a, int l, int r)
{
	if (r-l <= 16)
	{
		Insertion_Sort(a+l,r-l+1);
		return;
	}
	T			v = a[r];
	int			i = l-1;
	int			j = r;
	do 
	{
		do { i++; } while (i < r && a[i] < v);
		do { j--; } while (j > 0 && a[j] > v);
		swap(a[i],a[j]);
	} while (j > i);
	
	T t     = a[j];
	a[j]	= a[i];	  
	a[i]	= a[r];		
	a[r]	= t;
	if ((i-1) > l)
		Quick_Sort (a,l,i-1);
	if (r > (i+1))
		Quick_Sort (a,i+1,r);
}

template <class T> inline void Quick_Sort (T* a, int N)
{
	Quick_Sort(a,0,N-1);
}

//------------------------------------------------------------------------
// Implementation
//------------------------------------------------------------------------

/*****************************************************************************
 *
 * Function:		StripOptimizerClass::getStripIndexCount()
 *
 * Description:		Returns number of indices in a set of strips
 *
 * Parameters:
 *
 *****************************************************************************/

int StripOptimizerClass::Get_Strip_Index_Count (const int* strips, int strip_count)
{
	int cnt = 0;
	for (int i = 0; i < strip_count; i++)
	{
		int len = *strips++;		// read len
		cnt += len;
		strips += len;				// skip data
	}
	return cnt;
}

/*****************************************************************************
 *
 * Function:		StripOptimizerClass::optimizeStripOrder()
 *
 * Description:		
 *
 * Parameters:
 *
 *****************************************************************************/

// compares two strips and returns number of shared indices
static inline int Get_Strip_Similarity (const int* A, const int* B)
{
	int cnt = 0;
	int lenA = *A++;
	int lenB = *B++;

	for (int i = 0; i < lenA; i++)
	{
		int index = A[i];									// index of A
		for (int j = 0; j < lenB; j++)
		if (B[j] == index)									// match
		{
			cnt++;
			break;
		}
	}

	return cnt;
}

// copies a strip, returns new destination pointer
static inline int* Copy_Strip (int* d, const int* s)
{
	int len = *s++;
	*d++ = len;
	for (int i = 0; i < len; i++)
		*d++ = *s++;
	return d;
}

void StripOptimizerClass::Optimize_Strip_Order (int* strips, int strip_count)
{
	if (strip_count <= 0)
		return;
//	WWASSERT(strips);
	
	int**	ss = new int*[strip_count];							// pointers to beginning of strips
	int* s = strips;
	for (int i = 0; i < strip_count; i++)
	{
		ss[i] = s;
		int len = *s++;			// read len
		s+=len;					// skip
	}
	int outSize = Get_Strip_Index_Count(strips, strip_count)+strip_count;	// output memory alloc size
	int* out	= new int[outSize];	
	int* o		= out;											// output pointer

	const int* prev = ss[0];								// previous strip
	o = Copy_Strip (o, ss[0]);								// output first strip
	ss[0] = 0;

	for (;;)
	{
		int		bestIndex		= -1;
		int		bestSimilarity	= -1;

		for (int j = 0; j < strip_count; j++)
		if (ss[j])
		{
			int sim = Get_Strip_Similarity (prev, ss[j]);		// get similarity
			if (sim > bestSimilarity)
			{
				bestSimilarity = sim;
				bestIndex	   = j;
			}
		}

		if (bestIndex==-1)									// we're done
			break;

		o = Copy_Strip(o, ss[bestIndex]);					// copy the strip
		prev = ss[bestIndex];								// set to prev
		ss[bestIndex] = NULL;								// mark as selected
	}

//	WWASSERT((out+outSize)==o);							// HUH?

	for (i = 0; i < outSize; i++)						// copy output
		strips[i] = out[i];

	delete[] out;
	delete[] ss;
}

/*****************************************************************************
 *
 * Function:		StripOptimizerClass::optimizeTriangleOrder()
 *
 * Description:		
 *
 * Parameters:
 *
 *****************************************************************************/

struct Tri
{
public:
	int a,b,c;

	bool operator< (const Tri& s) const { return a < s.a; }
	bool operator> (const Tri& s) const { return a > s.a; }
};

static inline int Get_Similarity (const Tri& A, const Tri& B)
{
	int sim = 0;

	if (A.a == B.a || A.a == B.b || A.a == B.c) sim++;
	if (A.b == B.a || A.b == B.b || A.b == B.c) sim++;
	if (A.c == B.a || A.c == B.b || A.c == B.c) sim++;

	return sim;
}

void StripOptimizerClass::Optimize_Triangle_Order (int *tris, int triangle_count)
{
	if (triangle_count<=0)
		return;
	WWASSERT(tris);

	Tri** t = new Tri*[triangle_count];
	for (int i = 0; i < triangle_count; i++)
	{
		t[i] = (Tri*)(tris + i*3);
	}

	Tri* out = new Tri[triangle_count];
	Tri* o   = out;

	Tri* prev = t[0];

	*o++ = *prev;
	t[0] = NULL;

	for (;;)
	{
		// match best
		int bestIndex = -1;
		int bestSim   = -1;

		for (int j = 0; j < triangle_count; j++)
		if (t[j])
		{
			int sim = Get_Similarity (*prev, *t[j]);
			if (sim > bestSim)
			{
				bestSim   = sim;
				bestIndex = j;
				if (sim >= 2)										// that's the best we could get
					break;
			}
		}

		if (bestIndex == -1)										// we're done
			break;

		*o++ = *t[bestIndex];
		prev = t[bestIndex];								
		t[bestIndex] = NULL;
	}


	WWASSERT(o == (out+triangle_count));

	for (i = 0; i < triangle_count; i++)
	{
		Tri* d = (Tri*)(tris)+i;
		*d = out[i];
	}

	delete[] t;
	delete[] out;

}


/*****************************************************************************
 *
 * Function:		StripOptimizerClass::combineStrips()
 *
 * Description:		Combines a number of strips into one
 *
 * Parameters:
 *
 *****************************************************************************/

int* StripOptimizerClass::Combine_Strips (const int* strips, int strip_count)
{
	int check = Get_Strip_Index_Count(strips,strip_count) + (strip_count-1)*3;

	int* out	= new int[check+1];
	int* o		= out + 1;

	int* tmp = new int[check];	// DEBUG DEBUG

	bool prevEven = true;

	for (int i = 0; i < strip_count; i++)
	{
		int len = *strips++;

		if (i != 0)
		{
			*o++ = *strips;						// duplicate first
		
			if (!prevEven)
				*o++ = *strips;
		}

		for (int j = 0; j < len; j++)
			*o++ = *strips++;					// copy the strip

		if (i != (strip_count-1))
			*o++ = o[-1];

		prevEven = (!(len&1));
	}

	delete[] tmp;
//	WWASSERT(check == (o-out-1));
	*out = (o-out-1);						// set length
	return out;
}

//------------------------------------------------------------------------
// New striping code
//------------------------------------------------------------------------

namespace Strip
{

/*****************************************************************************
 *
 * Struct:			Vector3i
 * 
 * Description:		Internal class for representing an edge
 *
 *****************************************************************************/

struct Vector3i
{
	int	v[3];
				Vector3i () {}
				Vector3i (int a, int b, int c) { v[0]=a; v[1]=b; v[2]=c; }

	int&		operator[](int i)		{ return v[i]; }
	const int&	operator[](int i) const { return v[i]; }

};

/*****************************************************************************
 *
 * Struct:			Edge
 * 
 * Description:		Internal class for representing an edge
 *
 *****************************************************************************/

struct Edge
{
				Edge		(void)					{}
				Edge		(int v0, int v1)		{ v[0] = v0; v[1] = v1;								}
	bool		operator==	(const Edge& s) const	{ return v[0]==s.v[0] && v[1] == s.v[1];			}
	void		sort		(void)					{ if (v[0]>v[1]) swap(v[0],v[1]);					}

	int			v[2];						// edge
};

/*****************************************************************************
 *
 * Struct:			Triangle
 * 
 * Description:		Internal class for representing a triangle and 
 *					associated connectivity information
 *
 *****************************************************************************/

struct Triangle
{
	Triangle (void)					
	{ 
		m_neighbors[0] = 0;
		m_neighbors[1] = 0;
		m_neighbors[2] = 0;
		m_vertices[0]  = 0;
		m_vertices[1]  = 0;
		m_vertices[2]  = 0;
		m_prev		   = 0;
		m_next		   = 0;
		m_bin		   = -1;
	}

	Triangle*	m_neighbors[3];				// pointers to neighbors of the triangle
	Vector3i	m_vertices;					// vertices of the triangle

	Triangle*	m_prev;						// previous triangle in same bin
	Triangle*	m_next;						// next triangle in same bin
	int			m_bin;						// current bin (-1 == not in any bin)

	int			getConnectivity (void) const	{ int cnt = 0; if (m_neighbors[0]) cnt++; if (m_neighbors[1]) cnt++; if (m_neighbors[2]) cnt++; return cnt;}
	const Edge	getEdge			(int i) const	{ WWASSERT(i>=0 && i<3); return Edge(m_vertices[i],i==2?m_vertices[0]:m_vertices[i+1]); }

};

/*****************************************************************************
 *
 * Class:			TriangleQueue
 * 
 * Description:		Internal class for maintaining triangles sorted by
 *					connectivity
 *
 *****************************************************************************/

class TriangleQueue
{
public:
					TriangleQueue			(Triangle* tris, int N);
					~TriangleQueue			(void);
	void			removeTriangle			(Triangle* t);
	Triangle*		getTop					(void) const;
	int				getVertexConnectivity	(int i)  const;
private:
					TriangleQueue			(const TriangleQueue&);
	TriangleQueue&	operator=				(const TriangleQueue&);
	void			reinsert				(Triangle* t);

	Triangle*		m_bin[4];				// bins (0 = triangles with zero neighbors, etc.)
	int*			m_nodeConnectivity;		// node connectivity count
	int				m_vertexCount;
};

/*****************************************************************************
 *
 * Class:			Stripify
 * 
 * Description:		Class for performing stripification
 *
 *****************************************************************************/

class Stripify
{
public:
	static int*			stripify	(const Vector3i* tris, int N);
private:
						Stripify							(void);	// not permitted
						Stripify	(const Stripify&);
	Stripify&			operator=	(const Stripify&);

	static Triangle*	generateTriangleList				(const Vector3i* tris, int N);
	static Vector3i		getTriangleNodeConnectivityWeights	(const TriangleQueue& queue, const Triangle& tri);
	static int			getMod3								(int i) { WWASSERT(i>=0 && i<6); return s_mod[i]; }
	static int			s_mod[6];						// small lookup table for mod3 operation (see getMod3())
};

int Stripify::s_mod[6] = {0,1,2,0,1,2};
} // Strip


template <> inline unsigned int HashTemplateKeyClass<Strip::Edge>::Get_Hash_Value(const Strip::Edge& s)
{
	return (s.v[0]*139) + (s.v[1]*7);
}

namespace Strip
{
/*****************************************************************************
 *
 * Function:		TriangleQueue::getTop()
 *
 * Description:		Returns pointer to triangle with smallest connectivity
 *
 * Returns:			pointer to triangle with smallest connectivity or NULL
 *					if the queue is empty
 *
 *****************************************************************************/

inline Triangle* TriangleQueue::getTop	(void) const
{
	for (int i = 0; i < 4; i++)
	if (m_bin[i])
		return m_bin[i];				// return head
	return 0;							// end
}

/*****************************************************************************
 *
 * Function:		TriangleQueue::getVertexConnectivity()
 *
 * Description:		Returns current connectivity count of specified vertex
 *
 * Parameters:		i = vertex index
 *
 * Returns:			connectivity count
 *
 *****************************************************************************/

inline int	TriangleQueue::getVertexConnectivity (int i)  const  
{ 
	WWASSERT(i>=0 && i< m_vertexCount); 
	return m_nodeConnectivity[i]; 
}

/*****************************************************************************
 *
 * Function:		TriangleQueue::~TriangleQueue()
 *
 * Description:		Destructor
 *
 *****************************************************************************/

inline TriangleQueue::~TriangleQueue ()
{
	delete[] m_nodeConnectivity;
}

/*****************************************************************************
 *
 * Function:		TriangleQueue::reinsert()
 *
 * Description:		Internal function for recalculating a triangle's
 *					connectivity
 *
 * Parameters:		t = pointer to triangle (non-NULL)
 *
 *****************************************************************************/

inline void TriangleQueue::reinsert (Triangle* t)
{
	WWASSERT (t && t->m_bin!=-1);					// must be in some bin
	int w = t->getConnectivity();

	// remove from bin
	if (t->m_prev)
		t->m_prev->m_next = t->m_next;
	else
	{
		WWASSERT(t->m_bin != -1);
		WWASSERT(t == m_bin[t->m_bin]);			// must be head
		m_bin[t->m_bin] = t->m_next;			// new head
	}

	if (t->m_next)
		t->m_next->m_prev = t->m_prev;			

	t->m_prev = 0;
	t->m_next = m_bin[w];
	if (t->m_next)
		t->m_next->m_prev = t;

	m_bin[w] = t;								// head of bin
	t->m_bin = w;								// set bin
}

/*****************************************************************************
 *
 * Function:		TriangleQueue::removeTriangle()
 *
 * Description:		Removes a triangle from the queue
 *
 * Parameters:		t = pointer to triangle (non-NULL)
 *
 *****************************************************************************/

inline void TriangleQueue::removeTriangle	(Triangle* t)
{
	WWASSERT(t);
	if (t->m_prev)
		t->m_prev->m_next = t->m_next;
	else
	{
		WWASSERT(t->m_bin != -1);
		WWASSERT(t == m_bin[t->m_bin]);			// must be head
		m_bin[t->m_bin] = t->m_next;			// new head
	}

	if (t->m_next)
		t->m_next->m_prev = t->m_prev;			
	t->m_bin = -1;

	// update connectivity of t's neighbors

	Triangle* update[3];
	int			i;

	for (i = 0; i < 3; i++)
	{
		update[i]  = 0;
		if (t->m_neighbors[i])
		{
			Triangle* n = t->m_neighbors[i];
			int k=0;
			for (k = 0; k < 3; k++)
			if (n->m_neighbors[k]==t)
				break;
			WWASSERT (k!=3);							// WASS??
			n->m_neighbors[k] = 0;					// reduce connection
			t->m_neighbors[i] = 0;
			update[i] = n;
		}
	}

	// update connectivity count of t's vertices

	for (i = 0; i < 3; i++)
	{
		m_nodeConnectivity[t->m_vertices[i]]--;
		WWASSERT(m_nodeConnectivity[t->m_vertices[i]] >= 0);		// WASS?
	}

	for (i = 0; i < 3; i++)							// perform reinsertions now...
	if (update[i])
		reinsert(update[i]);

}

/*****************************************************************************
 *
 * Function:		TriangleQueue::TriangleQueue()
 *
 * Description:		Constructor
 *
 * Parameters:		tris = array of triangles
 *					N	 = number of triangles in the array
 *
 *****************************************************************************/

inline TriangleQueue::TriangleQueue	(Triangle* tris, int N)
{
	int i;
	for (i = 0; i < 4; i++)
		m_bin[i] = 0;							// initialize to zero

	int largestIndex = 0;

	for (i = 0; i < N; i++)
	for (int j = 0; j < 3; j++)
	{
		WWASSERT(tris[i].m_vertices[j]>=0);
		if (tris[i].m_vertices[j] > largestIndex)
			largestIndex = tris[i].m_vertices[j];
	}

	m_vertexCount	   = largestIndex+1;
	m_nodeConnectivity = new int[m_vertexCount];			// 
	for (i = 0; i < m_vertexCount; i++)
		m_nodeConnectivity[i]  = 0;


	for (i = 0; i < N; i++)
	{
		Triangle* t = tris+i;
		int w = t->getConnectivity();			
		WWASSERT(w>=0 && w <=3);
		WWASSERT(!t->m_prev && !t->m_next && t->m_bin==-1);	// must not be in a bin
		t->m_prev = 0;
		t->m_next = m_bin[w];
		if (t->m_next)
			t->m_next->m_prev = t;
		m_bin[w] = t;							// head of bin
		t->m_bin = w;							// set bin
		for (int j = 0; j < 3; j++)
			m_nodeConnectivity[t->m_vertices[j]]++;
	}
}


/*****************************************************************************
 *
 * Function:		Stripify::getTriangleConnectivityWeights()
 *
 * Description:		Returns "node connectivity" weights for each triangle vertex
 *
 * Parameters:		queue	= reference to triangle queue
 *					tri		= reference to triangle
 *
 * Returns:			Vector structure containing three weights
 *
 *****************************************************************************/

inline Vector3i Stripify::getTriangleNodeConnectivityWeights (const TriangleQueue& queue, const Triangle& tri)
{
	int weight[3];
	for (int i = 0; i < 3; i++)
	{
		weight[i] = queue.getVertexConnectivity(tri.m_vertices[i]);
	}
	int highestVal = weight[0];
	if (weight[1] > highestVal) highestVal = weight[1];
	if (weight[2] > highestVal) highestVal = weight[2];

	Vector3i v(-1,-1,-1);

	for (i = 0; i < 3; i++) {
		if (weight[0] == highestVal) v[i] = +1;
	}
		
	return v;
}

/*****************************************************************************
 *
 * Function:		Stripify::generateTriangleList()
 *
 * Description:		Converts input triangles into internal Triangle structure
 *
 * Parameters:		inTris	= input triangles
 *					N		= number of input triangles
 *
 * Returns:			pointer to Triangle array
 *
 * Notes:			The function sets up the initial connectivity information
 *
 *****************************************************************************/

Triangle* Stripify::generateTriangleList (const Vector3i* inTris, int N)
{
	WWASSERT (inTris && N>=0);

	Triangle*	tris = new Triangle[N];			// allocate triangles
	int			i;

	//--------------------------------------------------------------------
	// Copy triangle vertex data 
	//--------------------------------------------------------------------

	for (i = 0; i < N; i++)				
	{
		//--------------------------------------------------------------------
		// We could perform random rotation here (this way we don't need random
		// comparisons later in the algo in equality cases).
		//--------------------------------------------------------------------

		tris[i].m_vertices[0] = inTris[i][0];
		tris[i].m_vertices[1] = inTris[i][1];
		tris[i].m_vertices[2] = inTris[i][2];
	}

	//--------------------------------------------------------------------
	// Build connectivity information using a hash table
	//--------------------------------------------------------------------

	HashTemplateClass<Edge,Triangle*> hash;
	Triangle*			 t = tris;

	for (i = 0; i < N; i++, t++)
	{
		for (int j = 0; j < 3; j++)
		if (!t->m_neighbors[j])											// if neighbor not defined yet
		{
			Edge	edge	= tris[i].getEdge(j);
			Edge	e		= edge;
			e.sort();													// sort vertices (smaller first)
			
			Triangle* n = hash.Get(e);
			if (n)														// if edge is already in the hash...
			{
				int k=0;
				for (k = 0; k < 3; k++)									// find matching edge
				if (!n->m_neighbors[k])									// this neighbor not located yet
				{
					Edge ek = n->getEdge(k);							// get edge
					if (ek.v[0] == edge.v[1] && ek.v[1] == edge.v[0])	// if matching edge (note that order must be different)
						break;											// .. we found the edge
				}

				if (k < 3)												// (k==3) -> no match
				{
					t->m_neighbors[j] = n;								// set neighbor
					n->m_neighbors[k] = t;								// set neighbor
					hash.Remove(e);										// remove from hash (this speeds up the hash queries considerably)
				}
			} else
				hash.Insert(e, t);										// insert triangle into hash
		}
	}

	return tris;														// return pointer to output data
}

/*****************************************************************************
 *
 * Function:		Stripify::stripify()
 *
 * Description:		Builds a set of triangle strips out of a triangle array
 *
 * Parameters:		inTris	= input triangles (three vertices per triangle)
 *					N		= number of input triangles
 *
 * Returns:			pointer to strip data array
 *
 * Notes:			The strip data array layout is as follows:
 *
 *					[int]		number of strips
 *					[int]		length of first strip (in vertices)
 *					[int,..]	vertex indices of the first strip
 *					[int]		length of second strip
 *					...
 *
 *					The routine assumes that degenerate triangles have been
 *					remove and input vertices have been welded
 *
 *****************************************************************************/

int* Stripify::stripify  (const Vector3i* inTris, int N)
{
	if (!inTris || N<=0)												// boo!
		return 0;

	//--------------------------------------------------------------------
	// Initial setup
	//--------------------------------------------------------------------

	Triangle*		tris	= generateTriangleList(inTris,N);			// build connectivity info
	int*			out		= new int[N*5];								// absolute worst case situation
	int*			o		= out;										// internal ptr (save entry[0] for later use)
	int				strip_count	= 0;										// number of output strips
	TriangleQueue	queue (tris, N);									// insert triangles into priority queue

	int nSwaps = 0;
	int nLen   = 0;

	//--------------------------------------------------------------------
	// Main loop. Always select triangle with smallest weight.
	//--------------------------------------------------------------------

	for (;;)
	{
		Triangle* t = queue.getTop();									// get triangle with smallest weight
		if (!t)															// ok, we ran out of triangles (we're done)
			break;

		//--------------------------------------------------------------------
		// Choose initial direction by selecting neighbor with smallest
		// weight
		//--------------------------------------------------------------------

		int*	pLen		= o;										// get current pointer (as we need to take care of it later)
		int		len			= 3;										// initial length
		int		best		= 0;										// best edge
		int		bestWeight	= 0x7fffffff;								// initialize to maximum width

		Vector3i nodeWeights = getTriangleNodeConnectivityWeights(queue, *t);
		
		for (int i = 0; i < 3; i++)
		if (t->m_neighbors[i])											// if triangle has a neighbor in this direction
		{
			int	weight = t->m_neighbors[i]->getConnectivity();			// get connectivity of neighbor

			weight += nodeWeights[i];									// add node weights
			weight += nodeWeights[getMod3(i+1)];

			// DEBUG DEBUG ADD SWAP COST HERE?
			if (weight <= bestWeight)
			{
				bestWeight = weight;
				best       = i;
			}
		}

		*o++ = len;														// output the first three vertices
		*o++ = t->m_vertices[getMod3(best+2)];
		*o++ = t->m_vertices[getMod3(best+0)];
		*o++ = t->m_vertices[getMod3(best+1)];

		for (;;)
		{
			Triangle* next = 0;											// find next triangle
		
			int i;
			for (i = 0; i < 3; i++)
			if (t->m_neighbors[i])
			{
				Triangle* n = t->m_neighbors[i];
				for (int j = 0; j < 3; j++)
				{
					Edge e = n->getEdge(j);
					if (!(len&1))
						swap(e.v[0],e.v[1]);							// swap
					if (e.v[0] == o[-1] && e.v[1] == o[-2])
					{
						next = n;
						break;
					}
				}
			}

			queue.removeTriangle(t);									// get rid of the old triangle

			if (!next)													// we're done
				break;

			//--------------------------------------------------------------------
			// Find out where we want to continue...
			//--------------------------------------------------------------------
	
			int		bestEdge	= -1;
			int		bestWeight	= 0x7fffffff;
			bool	bestSwap	= false;

			Vector3i nodeWeights = getTriangleNodeConnectivityWeights(queue, *next);
			
			for (i = 0; i < 3; i++)
			if (next->m_neighbors[i])									// is there a neighbor?
			{
				Edge e			= next->getEdge(i);						// a swap happens if it contains the prevprev

				bool swap = (e.v[0] == o[-2] || e.v[1] == o[-2]);

				Triangle* n = next->m_neighbors[i];						// get pointer to neighbor
				int       w = n->getConnectivity();


				w += nodeWeights[i];									// add vertex weight
				w += nodeWeights[getMod3(i+1)];							// add vertex weight

				w += (swap) ? 1 : -1;									// add swap penalty
							
				if (w <= bestWeight)
				{
					bestWeight = w;
					bestEdge   = i;
					bestSwap   = swap;
				}
			}

			if (bestEdge != -1 && bestSwap)								// if we're going to continue...
			{
				*o = o[-2];												// introduce swap vertex
				o++;
				len++;													// adjust length
				nSwaps++;												// update statistics
			}

			//--------------------------------------------------------------------
			// Find out which was the new vertex (store it to vIndex)
			//--------------------------------------------------------------------

			int vIndex = 0;

			if (next->m_vertices[1] != o[-1] && next->m_vertices[1] != o[-2]) vIndex = 1; else
			if (next->m_vertices[2] != o[-1] && next->m_vertices[2] != o[-2]) vIndex = 2; else
				WWASSERT (next->m_vertices[0] != o[-1] && next->m_vertices[0] != o[-2]);

			//--------------------------------------------------------------------
			// Output the vertex and move to next triangle
			//--------------------------------------------------------------------

			*o++ = next->m_vertices[vIndex];							// output the vertex
			len++;														// increase strip length
			t = next;													// move to next triangle
		}
		
		*pLen = len;													// patch final length
		strip_count++;														// increase strip count

		nLen += len;
//		printf ("strip len = %d\n",len);
	}

	//--------------------------------------------------------------------
	// Allocate new optimal-size array and copy output there. Then release
	// all temporary memory allocations.
	//--------------------------------------------------------------------

//	printf ("total indices = %d\n",nLen);
//	printf ("total swaps   = %d\n",nSwaps);

	int		len		= o-out;											// allocation length
	int*	rOut	= new int[len+1];

	*rOut = strip_count;													// first entry is number of strips
	for (int i = 0; i < len; i++)
	{
		WWASSERT(out[i] >= 0);											// would be nice to test for len as well
		rOut[i+1] = out[i];
	}

	delete[] out;														// delete internal output
	delete[] tris;														// delete internal triangle list

	return rOut;
}
} // Strip
int* StripOptimizerClass::Stripify(const int* tris, int N)
{
	return Strip::Stripify::stripify((const Strip::Vector3i*)tris,N);
}

//------------------------------------------------------------------------