1016 lines
26 KiB
C++
1016 lines
26 KiB
C++
/*
|
|
** 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);
|
|
}
|
|
|
|
//------------------------------------------------------------------------
|
|
|