1 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2 //
3 // Source code for "Creating Efficient Triangle Strips"
4 // (C) 2000, Pierre Terdiman (p.terdiman@wanadoo.fr)
5 //
6 // Version is 2.0.
7 //
8 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
9
10 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
11 // Precompiled Header
12 #include "StripStdafx.h"
13
14 #include "Striper.h"
15
16 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17 //
18 // Striper Class Implementation
19 //
20 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
21
22 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
23 // Constructor
24 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Striper()25 Striper::Striper() : mAdj(null), mTags(null), mStripLengths(null), mStripRuns(null), mSingleStrip(null)
26 {
27 }
28
29 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
30 // Destructor
31 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
~Striper()32 Striper::~Striper()
33 {
34 FreeUsedRam();
35 }
36
37 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
38 // A method to free possibly used ram
39 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
40 // Input : -
41 // Output : -
42 // Return : Self-reference
43 // Exception: -
44 // Remark : -
FreeUsedRam()45 Striper& Striper::FreeUsedRam()
46 {
47 RELEASE(mSingleStrip);
48 RELEASE(mStripRuns);
49 RELEASE(mStripLengths);
50 RELEASEARRAY(mTags);
51 RELEASE(mAdj);
52 return *this;
53 }
54
55 void ZeroMemory(void* addr, udword size);
56 void CopyMemory(void* dest, const void* src, udword size);
57 void FillMemory(void* dest, udword size, ubyte val);
58
ZeroMemory(void * addr,udword size)59 void ZeroMemory(void* addr, udword size)
60 {
61 memset(addr, 0, size);
62 }
63
CopyMemory(void * dest,const void * src,udword size)64 void CopyMemory(void* dest, const void* src, udword size)
65 {
66 memcpy(dest, src, size);
67 }
68
FillMemory(void * dest,udword size,ubyte val)69 void FillMemory(void* dest, udword size, ubyte val)
70 {
71 memset(dest, val, size);
72 }
73
74 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
75 // A method to initialize the striper
76 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
77 // Input : create, the creation structure
78 // Output : -
79 // Return : true if success
80 // Exception: -
81 // Remark : -
Init(STRIPERCREATE & create)82 bool Striper::Init(STRIPERCREATE& create)
83 {
84 // Release possibly already used ram
85 FreeUsedRam();
86
87 // Create adjacencies
88 {
89 mAdj = new Adjacencies;
90 if(!mAdj) return false;
91
92 ADJACENCIESCREATE ac;
93 ac.NbFaces = create.NbFaces;
94 ac.DFaces = create.DFaces;
95 ac.WFaces = create.WFaces;
96 bool Status = mAdj->Init(ac);
97 if(!Status) { RELEASE(mAdj); return false; }
98
99 Status = mAdj->CreateDatabase();
100 if(!Status) { RELEASE(mAdj); return false; }
101
102 mAskForWords = create.AskForWords;
103 mOneSided = create.OneSided;
104 mSGIAlgorithm = create.SGIAlgorithm;
105 mConnectAllStrips = create.ConnectAllStrips;
106 }
107
108 return true;
109 }
110
111 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
112 // A method to create the triangle strips
113 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
114 // Input : result, the result structure
115 // Output : -
116 // Return : true if success
117 // Exception: -
118 // Remark : -
Compute(STRIPERRESULT & result)119 bool Striper::Compute(STRIPERRESULT& result)
120 {
121 // You must call Init() first
122 if(!mAdj) return false;
123
124 // Get some bytes
125 mStripLengths = new CustomArray; if(!mStripLengths) return false;
126 mStripRuns = new CustomArray; if(!mStripRuns) return false;
127 mTags = new bool[mAdj->mNbFaces]; if(!mTags) return false;
128 udword* Connectivity = new udword[mAdj->mNbFaces]; if(!Connectivity) return false;
129
130 // mTags contains one bool/face. True=>the face has already been included in a strip
131 ZeroMemory(mTags, mAdj->mNbFaces*sizeof(bool));
132
133 // Compute the number of connections for each face. This buffer is further recycled into
134 // the insertion order, ie contains face indices in the order we should treat them
135 ZeroMemory(Connectivity, mAdj->mNbFaces*sizeof(udword));
136 if(mSGIAlgorithm)
137 {
138 // Compute number of adjacent triangles for each face
139 for(udword i=0;i<mAdj->mNbFaces;i++)
140 {
141 AdjTriangle* Tri = &mAdj->mFaces[i];
142 if(!IS_BOUNDARY(Tri->ATri[0])) Connectivity[i]++;
143 if(!IS_BOUNDARY(Tri->ATri[1])) Connectivity[i]++;
144 if(!IS_BOUNDARY(Tri->ATri[2])) Connectivity[i]++;
145 }
146
147 // Sort by number of neighbors
148 RadixSorter RS;
149 udword* Sorted = RS.Sort(Connectivity, mAdj->mNbFaces).GetIndices();
150
151 // The sorted indices become the order of insertion in the strips
152 CopyMemory(Connectivity, Sorted, mAdj->mNbFaces*sizeof(udword));
153 }
154 else
155 {
156 // Default order
157 for(udword i=0;i<mAdj->mNbFaces;i++) Connectivity[i] = i;
158 }
159
160 mNbStrips = 0; // #strips created
161 udword TotalNbFaces = 0; // #faces already transformed into strips
162 udword Index = 0; // Index of first face
163
164 while(TotalNbFaces!=mAdj->mNbFaces)
165 {
166 // Look for the first face [could be optimized]
167 while(mTags[Connectivity[Index]]) Index++;
168 udword FirstFace = Connectivity[Index];
169
170 // Compute the three possible strips from this face and take the best
171 TotalNbFaces += ComputeBestStrip(FirstFace);
172
173 // Let's wrap
174 mNbStrips++;
175 }
176
177 // Free now useless ram
178 RELEASEARRAY(Connectivity);
179 RELEASEARRAY(mTags);
180
181 // Fill result structure and exit
182 result.NbStrips = mNbStrips;
183 result.StripLengths = (udword*) mStripLengths ->Collapse();
184 result.StripRuns = mStripRuns ->Collapse();
185
186 if(mConnectAllStrips) ConnectAllStrips(result);
187
188 return true;
189 }
190
191 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
192 // A method to compute the three possible strips starting from a given face
193 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
194 // Input : face, the first face
195 // Output : -
196 // Return : udword, the #faces included in the strip
197 // Exception: -
198 // Remark : mStripLengths and mStripRuns are filled with strip data
ComputeBestStrip(udword face)199 udword Striper::ComputeBestStrip(udword face)
200 {
201 udword* Strip[3]; // Strips computed in the 3 possible directions
202 udword* Faces[3]; // Faces involved in the 3 previous strips
203 udword Length[3] = {0,0,0}; // Lengths of the 3 previous strips
204
205 udword FirstLength[3]; // Lengths of the first parts of the strips are saved for culling
206 udword jLook = 1;
207
208 // Starting references
209 udword Refs0[3];
210 udword Refs1[3];
211 Refs0[0] = mAdj->mFaces[face].VRef[0];
212 Refs1[0] = mAdj->mFaces[face].VRef[1];
213
214 // Bugfix by Eric Malafeew!
215 Refs0[1] = mAdj->mFaces[face].VRef[2];
216 Refs1[1] = mAdj->mFaces[face].VRef[0];
217
218 Refs0[2] = mAdj->mFaces[face].VRef[1];
219 Refs1[2] = mAdj->mFaces[face].VRef[2];
220
221 // Compute jLook strips
222 for(udword j=0;j<jLook;j++)
223 {
224 // Get some bytes for the strip and its faces
225 Strip[j] = new udword[mAdj->mNbFaces+2+1+2]; // max possible length is NbFaces+2, 1 more if the first index gets replicated
226 Faces[j] = new udword[mAdj->mNbFaces+2];
227 FillMemory(Strip[j], (mAdj->mNbFaces+2+1+2)*sizeof(udword), 0xff);
228 FillMemory(Faces[j], (mAdj->mNbFaces+2)*sizeof(udword), 0xff);
229
230 // Create a local copy of the tags
231 bool* Tags = new bool[mAdj->mNbFaces];
232 CopyMemory(Tags, mTags, mAdj->mNbFaces*sizeof(bool));
233
234 // Track first part of the strip
235 Length[j] = TrackStrip(face, Refs0[j], Refs1[j], &Strip[j][0], &Faces[j][0], Tags);
236
237 // Save first length for culling
238 FirstLength[j] = Length[j];
239 // if(j==1) FirstLength[j]++; // ...because the first face is written in reverse order for j==1
240
241 // Reverse first part of the strip
242 for(udword i=0;i<Length[j]/2;i++)
243 {
244 Strip[j][i] ^= Strip[j][Length[j]-i-1];
245 Strip[j][Length[j]-i-1] ^= Strip[j][i];
246 Strip[j][i] ^= Strip[j][Length[j]-i-1];
247 }
248 for(udword i=0;i<(Length[j]-2)/2;i++)
249 {
250 Faces[j][i] ^= Faces[j][Length[j]-i-3];
251 Faces[j][Length[j]-i-3] ^= Faces[j][i];
252 Faces[j][i] ^= Faces[j][Length[j]-i-3];
253 }
254
255 // Track second part of the strip
256 udword NewRef0 = Strip[j][Length[j]-3];
257 udword NewRef1 = Strip[j][Length[j]-2];
258 udword ExtraLength = TrackStrip(face, NewRef0, NewRef1, &Strip[j][Length[j]-3], &Faces[j][Length[j]-3], Tags);
259 Length[j]+=ExtraLength-3;
260
261 // Free temp ram
262 RELEASEARRAY(Tags);
263 }
264
265 // Look for the best strip among the three
266 udword Longest = Length[0];
267 udword Best = 0;
268 if(Length[1] > Longest) { Longest = Length[1]; Best = 1; }
269 if(Length[2] > Longest) { Longest = Length[2]; Best = 2; }
270
271 udword NbFaces = Longest-2;
272
273 // Update global tags
274 for(udword j=0;j<Longest-2;j++) mTags[Faces[Best][j]] = true;
275
276 // Flip strip if needed ("if the length of the first part of the strip is odd, the strip must be reversed")
277 if(mOneSided && FirstLength[Best]&1)
278 {
279 // Here the strip must be flipped. I hardcoded a special case for triangles and quads.
280 if(Longest==3 || Longest==4)
281 {
282 // Flip isolated triangle or quad
283 Strip[Best][1] ^= Strip[Best][2];
284 Strip[Best][2] ^= Strip[Best][1];
285 Strip[Best][1] ^= Strip[Best][2];
286 }
287 else
288 {
289 // "to reverse the strip, write it in reverse order"
290 for(udword j=0;j<Longest/2;j++)
291 {
292 Strip[Best][j] ^= Strip[Best][Longest-j-1];
293 Strip[Best][Longest-j-1] ^= Strip[Best][j];
294 Strip[Best][j] ^= Strip[Best][Longest-j-1];
295 }
296
297 // "If the position of the original face in this new reversed strip is odd, you're done"
298 udword NewPos = Longest-FirstLength[Best];
299 if(NewPos&1)
300 {
301 // "Else replicate the first index"
302 for(udword j=0;j<Longest;j++) Strip[Best][Longest-j] = Strip[Best][Longest-j-1];
303 Longest++;
304 }
305 }
306 }
307
308 // Copy best strip in the strip buffers
309 for(udword j=0;j<Longest;j++)
310 {
311 udword Ref = Strip[Best][j];
312 if(mAskForWords) mStripRuns->Store((uword)Ref); // Saves word reference
313 else mStripRuns->Store(Ref); // Saves dword reference
314 }
315 mStripLengths->Store(Longest);
316
317 // Free local ram
318 for(udword j=0;j<jLook;j++)
319 {
320 RELEASEARRAY(Faces[j]);
321 RELEASEARRAY(Strip[j]);
322 }
323
324 // Returns #faces involved in the strip
325 return NbFaces;
326 }
327
328 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
329 // A method to extend a strip in a given direction, starting from a given face
330 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
331 // Input : face, the starting face
332 // oldest, middle, the two first indices of the strip == a starting edge == a direction
333 // Output : strip, a buffer to store the strip
334 // faces, a buffer to store the faces of the strip
335 // tags, a buffer to mark the visited faces
336 // Return : udword, the strip length
337 // Exception: -
338 // Remark : -
TrackStrip(udword face,udword oldest,udword middle,udword * strip,udword * faces,bool * tags)339 udword Striper::TrackStrip(udword face, udword oldest, udword middle, udword* strip, udword* faces, bool* tags)
340 {
341 udword Length = 2; // Initial length is 2 since we have 2 indices in input
342 strip[0] = oldest; // First index of the strip
343 strip[1] = middle; // Second index of the strip
344
345 bool DoTheStrip = true;
346 while(DoTheStrip)
347 {
348 udword Newest = mAdj->mFaces[face].OppositeVertex(oldest, middle); // Get the third index of a face given two of them
349 strip[Length++] = Newest; // Extend the strip,...
350 *faces++ = face; // ...keep track of the face,...
351 tags[face] = true; // ...and mark it as "done".
352
353 ubyte CurEdge = mAdj->mFaces[face].FindEdge(middle, Newest); // Get the edge ID...
354
355 udword Link = mAdj->mFaces[face].ATri[CurEdge]; // ...and use it to catch the link to adjacent face.
356 if(IS_BOUNDARY(Link)) DoTheStrip = false; // If the face is no more connected, we're done...
357 else
358 {
359 face = MAKE_ADJ_TRI(Link); // ...else the link gives us the new face index.
360 if(tags[face]) DoTheStrip=false; // Is the new face already done?
361 }
362 oldest = middle; // Shift the indices and wrap
363 middle = Newest;
364 }
365 return Length;
366 }
367
368 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
369 // A method to link all strips in a single one.
370 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
371 // Input : result, the result structure
372 // Output : the result structure is updated
373 // Return : true if success
374 // Exception: -
375 // Remark : -
ConnectAllStrips(STRIPERRESULT & result)376 bool Striper::ConnectAllStrips(STRIPERRESULT& result)
377 {
378 mSingleStrip = new CustomArray;
379 if(!mSingleStrip) return false;
380
381 mTotalLength = 0;
382 uword* wrefs = mAskForWords ? (uword*)result.StripRuns : null;
383 udword* drefs = mAskForWords ? null : (udword*)result.StripRuns;
384
385 // Loop over strips and link them together
386 for(udword k=0;k<result.NbStrips;k++)
387 {
388 // Nothing to do for the first strip, we just copy it
389 if(k)
390 {
391 // This is not the first strip, so we must copy two void vertices between the linked strips
392 udword LastRef = drefs ? drefs[-1] : (udword)wrefs[-1];
393 udword FirstRef = drefs ? drefs[0] : (udword)wrefs[0];
394 if(mAskForWords) mSingleStrip->Store((uword)LastRef).Store((uword)FirstRef);
395 else mSingleStrip->Store(LastRef).Store(FirstRef);
396 mTotalLength += 2;
397
398 // Linking two strips may flip their culling. If the user asked for single-sided strips we must fix that
399 if(mOneSided)
400 {
401 // Culling has been inverted only if mTotalLength is odd
402 if(mTotalLength&1)
403 {
404 // We can fix culling by replicating the first vertex once again...
405 udword SecondRef = drefs ? drefs[1] : (udword)wrefs[1];
406 if(FirstRef!=SecondRef)
407 {
408 if(mAskForWords) mSingleStrip->Store((uword)FirstRef);
409 else mSingleStrip->Store(FirstRef);
410 mTotalLength++;
411 }
412 else
413 {
414 // ...but if flipped strip already begin with a replicated vertex, we just can skip it.
415 result.StripLengths[k]--;
416 if(wrefs) wrefs++;
417 if(drefs) drefs++;
418 }
419 }
420 }
421 }
422
423 // Copy strip
424 for(udword j=0;j<result.StripLengths[k];j++)
425 {
426 udword Ref = drefs ? drefs[j] : (udword)wrefs[j];
427 if(mAskForWords) mSingleStrip->Store((uword)Ref);
428 else mSingleStrip->Store(Ref);
429 }
430 if(wrefs) wrefs += result.StripLengths[k];
431 if(drefs) drefs += result.StripLengths[k];
432 mTotalLength += result.StripLengths[k];
433 }
434
435 // Update result
436 result.NbStrips = 1;
437 result.StripRuns = mSingleStrip->Collapse();
438 result.StripLengths = &mTotalLength;
439
440 return true;
441 }
442