/* ** 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 . */ #include "stripoptimizer.h" #include "hashtemplate.h" #include "wwdebug.h" template 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 inline void Insertion_Sort (T* a, int N); template inline void Quick_Sort (T* a, int N); template 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 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 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::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 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); } //------------------------------------------------------------------------