1 /******************************************************************************
2
3 @File PVRTTriStrip.cpp
4
5 @Title PVRTTriStrip
6
7 @Version @Version
8
9 @Copyright Copyright (c) Imagination Technologies Limited.
10
11 @Platform Independent
12
13 @Description Strips a triangle list.
14
15 ******************************************************************************/
16
17 /****************************************************************************
18 ** Includes
19 ****************************************************************************/
20 #include <stdlib.h>
21
22 #include "PVRTGlobal.h"
23 #include "PVRTContext.h"
24 #include "PVRTTriStrip.h"
25
26 /****************************************************************************
27 ** Defines
28 ****************************************************************************/
29 #define RND_TRIS_ORDER
30
31 /****************************************************************************
32 ** Structures
33 ****************************************************************************/
34
35 /****************************************************************************
36 ** Class: CTri
37 ****************************************************************************/
38 class CTri;
39
40 /*!***************************************************************************
41 @Class CTriState
42 @Description Stores a pointer to the triangles either side of itself,
43 as well as it's winding.
44 *****************************************************************************/
45 class CTriState
46 {
47 public:
48 CTri *pRev, *pFwd;
49 bool bWindFwd;
50
CTriState()51 CTriState()
52 {
53 bWindFwd = true; // Initial value irrelevent
54 pRev = NULL;
55 pFwd = NULL;
56 }
57 };
58 /*!***************************************************************************
59 @Class CTri
60 @Description Object used to store information about the triangle, such as
61 the vertex indices it is made from, which triangles are
62 adjacent to it, etc.
63 *****************************************************************************/
64 class CTri
65 {
66 public:
67 CTriState sNew, sOld;
68
69 CTri *pAdj[3];
70 bool bInStrip;
71
72 const unsigned int *pIdx; // three indices for the tri
73 bool bOutput;
74
75 public:
76 CTri();
77 int FindEdge(const unsigned int pw0, const unsigned int pw1) const;
78 void Cement();
79 void Undo();
80 int EdgeFromAdjTri(const CTri &tri) const; // Find the index of the adjacent tri
81 };
82
83 /*!***************************************************************************
84 @Class CStrip
85 @Description Object used to store the triangles that a given strip is
86 composed from.
87 *****************************************************************************/
88 class CStrip
89 {
90 protected:
91 unsigned int m_nTriCnt;
92 CTri *m_pTri;
93 unsigned int m_nStrips;
94
95 CTri **m_psStrip; // Working space for finding strips
96
97 public:
98 CStrip(
99 const unsigned int * const pui32TriList,
100 const unsigned int nTriCnt);
101 ~CStrip();
102
103 protected:
104 bool StripGrow(
105 CTri &triFrom,
106 const unsigned int nEdgeFrom,
107 const int nMaxChange);
108
109 public:
110 void StripFromEdges();
111 void StripImprove();
112
113 void Output(
114 unsigned int **ppui32Strips,
115 unsigned int **ppnStripLen,
116 unsigned int *pnStripCnt);
117 };
118
119 /****************************************************************************
120 ** Constants
121 ****************************************************************************/
122
123 /****************************************************************************
124 ** Code: Class: CTri
125 ****************************************************************************/
CTri()126 CTri::CTri()
127 {
128 pAdj[0] = NULL;
129 pAdj[1] = NULL;
130 pAdj[2] = NULL;
131 bInStrip = false;
132 bOutput = false;
133 }
134
135 /*!***************************************************************************
136 @Function FindEdge
137 @Input pw0 The first index
138 @Input pw1 The second index
139 @Return The index of the edge
140 @Description Finds the index of the edge that the current object shares
141 with the two vertex index values that have been passed in
142 (or returns -1 if they dont share an edge).
143 *****************************************************************************/
FindEdge(const unsigned int pw0,const unsigned int pw1) const144 int CTri::FindEdge(const unsigned int pw0, const unsigned int pw1) const
145 {
146 if((pIdx[0] == pw0 && pIdx[1] == pw1))
147 return 0;
148 if((pIdx[1] == pw0 && pIdx[2] == pw1))
149 return 1;
150 if((pIdx[2] == pw0 && pIdx[0] == pw1))
151 return 2;
152 return -1;
153 }
154 /*!***************************************************************************
155 @Function Cement
156 @Description Assigns the new state as the old state.
157 *****************************************************************************/
Cement()158 void CTri::Cement()
159 {
160 sOld = sNew;
161 }
162 /*!***************************************************************************
163 @Function Undo
164 @Description Reverts the new state to the old state.
165 *****************************************************************************/
Undo()166 void CTri::Undo()
167 {
168 sNew = sOld;
169 }
170 /*!***************************************************************************
171 @Function EdgeFromAdjTri
172 @Input tri The triangle to compare
173 @Return int Index of adjacent triangle (-1 if not adjacent)
174 @Description If the input triangle is adjacent to the current triangle,
175 it's index is returned.
176 *****************************************************************************/
EdgeFromAdjTri(const CTri & tri) const177 int CTri::EdgeFromAdjTri(const CTri &tri) const
178 {
179 for(int i = 0; i < 3; ++i)
180 {
181 if(pAdj[i] == &tri)
182 {
183 return i;
184 }
185 }
186 _ASSERT(false);
187 return -1;
188 }
189
190 /****************************************************************************
191 ** Local code
192 ****************************************************************************/
193 /*!***************************************************************************
194 @Function OrphanTri
195 @Input tri The triangle test
196 @Return int Returns 1 if change was made
197 @Description If the input triangle is not wound forward and is not the last
198 triangle in the strip, the connection with the next triangle
199 in the strip is removed.
200 *****************************************************************************/
OrphanTri(CTri * const pTri)201 static int OrphanTri(
202 CTri * const pTri)
203 {
204 _ASSERT(!pTri->bInStrip);
205 if(pTri->sNew.bWindFwd || !pTri->sNew.pFwd)
206 return 0;
207
208 pTri->sNew.pFwd->sNew.pRev = NULL;
209 pTri->sNew.pFwd = NULL;
210 return 1;
211 }
212 /*!***************************************************************************
213 @Function TakeTri
214 @Input pTri The triangle to take
215 @Input pRevNew The triangle that is before pTri in the new strip
216 @Return int Returns 1 if a new strip has been created
217 @Description Removes the triangle from it's current strip
218 and places it in a new one (following pRevNew in the new strip).
219 *****************************************************************************/
TakeTri(CTri * const pTri,CTri * const pRevNew,const bool bFwd)220 static int TakeTri(
221 CTri * const pTri,
222 CTri * const pRevNew,
223 const bool bFwd)
224 {
225 int nRet;
226
227 _ASSERT(!pTri->bInStrip);
228
229 if(pTri->sNew.pFwd && pTri->sNew.pRev)
230 {
231 _ASSERT(pTri->sNew.pFwd->sNew.pRev == pTri);
232 pTri->sNew.pFwd->sNew.pRev = NULL;
233 _ASSERT(pTri->sNew.pRev->sNew.pFwd == pTri);
234 pTri->sNew.pRev->sNew.pFwd = NULL;
235
236 // If in the middle of a Strip, this will generate a new Strip
237 nRet = 1;
238
239 // The second tri in the strip may need to be orphaned, or it will have wrong winding order
240 nRet += OrphanTri(pTri->sNew.pFwd);
241 }
242 else if(pTri->sNew.pFwd)
243 {
244 _ASSERT(pTri->sNew.pFwd->sNew.pRev == pTri);
245 pTri->sNew.pFwd->sNew.pRev = NULL;
246
247 // If at the beginning of a Strip, no change
248 nRet = 0;
249
250 // The second tri in the strip may need to be orphaned, or it will have wrong winding order
251 nRet += OrphanTri(pTri->sNew.pFwd);
252 }
253 else if(pTri->sNew.pRev)
254 {
255 _ASSERT(pTri->sNew.pRev->sNew.pFwd == pTri);
256 pTri->sNew.pRev->sNew.pFwd = NULL;
257
258 // If at the end of a Strip, no change
259 nRet = 0;
260 }
261 else
262 {
263 // Otherwise it's a lonesome triangle; one Strip removed!
264 nRet = -1;
265 }
266
267 pTri->sNew.pFwd = NULL;
268 pTri->sNew.pRev = pRevNew;
269 pTri->bInStrip = true;
270 pTri->sNew.bWindFwd = bFwd;
271
272 if(pRevNew)
273 {
274 _ASSERT(!pRevNew->sNew.pFwd);
275 pRevNew->sNew.pFwd = pTri;
276 }
277
278 return nRet;
279 }
280 /*!***************************************************************************
281 @Function TryLinkEdge
282 @Input src The source triangle
283 @Input cmp The triangle to compare with
284 @Input nSrcEdge The edge of souce triangle to compare
285 @Input idx0 Vertex index 0 of the compare triangle
286 @Input idx1 Vertex index 1 of the compare triangle
287 @Description If the triangle to compare currently has no adjacent
288 triangle along the specified edge, link the source triangle
289 (along it's specified edge) with the compare triangle.
290 *****************************************************************************/
TryLinkEdge(CTri & src,CTri & cmp,const int nSrcEdge,const unsigned int idx0,const unsigned int idx1)291 static bool TryLinkEdge(
292 CTri &src,
293 CTri &cmp,
294 const int nSrcEdge,
295 const unsigned int idx0,
296 const unsigned int idx1)
297 {
298 int nCmpEdge;
299
300 nCmpEdge = cmp.FindEdge(idx0, idx1);
301 if(nCmpEdge != -1 && !cmp.pAdj[nCmpEdge])
302 {
303 cmp.pAdj[nCmpEdge] = &src;
304 src.pAdj[nSrcEdge] = &cmp;
305 return true;
306 }
307 return false;
308 }
309
310 /****************************************************************************
311 ** Code: Class: CStrip
312 ****************************************************************************/
CStrip(const unsigned int * const pui32TriList,const unsigned int nTriCnt)313 CStrip::CStrip(
314 const unsigned int * const pui32TriList,
315 const unsigned int nTriCnt)
316 {
317 unsigned int i, j;
318 bool b0, b1, b2;
319
320 m_nTriCnt = nTriCnt;
321
322 /*
323 Generate adjacency info
324 */
325 m_pTri = new CTri[nTriCnt];
326 for(i = 0; i < nTriCnt; ++i)
327 {
328 // Set pointer to indices
329 m_pTri[i].pIdx = &pui32TriList[3 * i];
330
331 b0 = false;
332 b1 = false;
333 b2 = false;
334 for(j = 0; j < i && !(b0 & b1 & b2); ++j)
335 {
336 if(!b0)
337 b0 = TryLinkEdge(m_pTri[i], m_pTri[j], 0, m_pTri[i].pIdx[1], m_pTri[i].pIdx[0]);
338
339 if(!b1)
340 b1 = TryLinkEdge(m_pTri[i], m_pTri[j], 1, m_pTri[i].pIdx[2], m_pTri[i].pIdx[1]);
341
342 if(!b2)
343 b2 = TryLinkEdge(m_pTri[i], m_pTri[j], 2, m_pTri[i].pIdx[0], m_pTri[i].pIdx[2]);
344 }
345 }
346
347 // Initially, every triangle is a strip.
348 m_nStrips = m_nTriCnt;
349
350 // Allocate working space for the strippers
351 m_psStrip = new CTri*[m_nTriCnt];
352 }
353
~CStrip()354 CStrip::~CStrip()
355 {
356 delete [] m_pTri;
357 delete [] m_psStrip;
358 }
359 /*!***************************************************************************
360 @Function StripGrow
361 @Input triFrom The triangle to begin from
362 @Input nEdgeFrom The edge of the triangle to begin from
363 @Input maxChange The maximum number of changes to be made
364 @Description Takes triFrom as a starting point of triangles to add to
365 the list and adds triangles sequentially by finding the next
366 triangle that is adjacent to the current triangle.
367 This is repeated until the maximum number of changes
368 have been made.
369 *****************************************************************************/
StripGrow(CTri & triFrom,const unsigned int nEdgeFrom,const int nMaxChange)370 bool CStrip::StripGrow(
371 CTri &triFrom,
372 const unsigned int nEdgeFrom,
373 const int nMaxChange)
374 {
375 unsigned int i;
376 bool bFwd;
377 int nDiff, nDiffTot, nEdge;
378 CTri *pTri, *pTriPrev, *pTmp;
379 unsigned int nStripLen;
380
381 // Start strip from this tri
382 pTri = &triFrom;
383 pTriPrev = NULL;
384
385 nDiffTot = 0;
386 nStripLen = 0;
387
388 // Start strip from this edge
389 nEdge = nEdgeFrom;
390 bFwd = true;
391
392 // Extend the strip until we run out, or we find an improvement
393 nDiff = 1;
394 while(nDiff > nMaxChange)
395 {
396 // Add pTri to the strip
397 _ASSERT(pTri);
398 nDiff += TakeTri(pTri, pTriPrev, bFwd);
399 _ASSERT(nStripLen < m_nTriCnt);
400 m_psStrip[nStripLen++] = pTri;
401
402 // Jump to next tri
403 pTriPrev = pTri;
404 pTri = pTri->pAdj[nEdge];
405 if(!pTri)
406 break; // No more tris, gotta stop
407
408 if(pTri->bInStrip)
409 break; // No more tris, gotta stop
410
411 // Find which edge we came over
412 nEdge = pTri->EdgeFromAdjTri(*pTriPrev);
413
414 // Find the edge to leave over
415 if(bFwd)
416 {
417 if(--nEdge < 0)
418 nEdge = 2;
419 }
420 else
421 {
422 if(++nEdge > 2)
423 nEdge = 0;
424 }
425
426 // Swap the winding order for the next tri
427 bFwd = !bFwd;
428 }
429 _ASSERT(!pTriPrev->sNew.pFwd);
430
431 /*
432 Accept or reject this strip.
433
434 Accepting changes which don't change the number of strips
435 adds variety, which can help better strips to develop.
436 */
437 if(nDiff <= nMaxChange)
438 {
439 nDiffTot += nDiff;
440
441 // Great, take the Strip
442 for(i = 0; i < nStripLen; ++i)
443 {
444 pTri = m_psStrip[i];
445 _ASSERT(pTri->bInStrip);
446
447 // Cement affected tris
448 pTmp = pTri->sOld.pFwd;
449 if(pTmp && !pTmp->bInStrip)
450 {
451 if(pTmp->sOld.pFwd && !pTmp->sOld.pFwd->bInStrip)
452 pTmp->sOld.pFwd->Cement();
453 pTmp->Cement();
454 }
455
456 pTmp = pTri->sOld.pRev;
457 if(pTmp && !pTmp->bInStrip)
458 {
459 pTmp->Cement();
460 }
461
462 // Cement this tris
463 pTri->bInStrip = false;
464 pTri->Cement();
465 }
466 }
467 else
468 {
469 // Shame, undo the strip
470 for(i = 0; i < nStripLen; ++i)
471 {
472 pTri = m_psStrip[i];
473 _ASSERT(pTri->bInStrip);
474
475 // Undo affected tris
476 pTmp = pTri->sOld.pFwd;
477 if(pTmp && !pTmp->bInStrip)
478 {
479 if(pTmp->sOld.pFwd && !pTmp->sOld.pFwd->bInStrip)
480 pTmp->sOld.pFwd->Undo();
481 pTmp->Undo();
482 }
483
484 pTmp = pTri->sOld.pRev;
485 if(pTmp && !pTmp->bInStrip)
486 {
487 pTmp->Undo();
488 }
489
490 // Undo this tris
491 pTri->bInStrip = false;
492 pTri->Undo();
493 }
494 }
495
496 #ifdef _DEBUG
497 for(int nDbg = 0; nDbg < (int)m_nTriCnt; ++nDbg)
498 {
499 _ASSERT(m_pTri[nDbg].bInStrip == false);
500 _ASSERT(m_pTri[nDbg].bOutput == false);
501 _ASSERT(m_pTri[nDbg].sOld.pRev == m_pTri[nDbg].sNew.pRev);
502 _ASSERT(m_pTri[nDbg].sOld.pFwd == m_pTri[nDbg].sNew.pFwd);
503
504 if(m_pTri[nDbg].sNew.pRev)
505 {
506 _ASSERT(m_pTri[nDbg].sNew.pRev->sNew.pFwd == &m_pTri[nDbg]);
507 }
508
509 if(m_pTri[nDbg].sNew.pFwd)
510 {
511 _ASSERT(m_pTri[nDbg].sNew.pFwd->sNew.pRev == &m_pTri[nDbg]);
512 }
513 }
514 #endif
515
516 if(nDiffTot)
517 {
518 m_nStrips += nDiffTot;
519 return true;
520 }
521 return false;
522 }
523
524 /*!***************************************************************************
525 @Function StripFromEdges
526 @Description Creates a strip from the object's edge information.
527 *****************************************************************************/
StripFromEdges()528 void CStrip::StripFromEdges()
529 {
530 unsigned int i, j, nTest;
531 CTri *pTri, *pTriPrev;
532 int nEdge = 0;
533
534 /*
535 Attempt to create grid-oriented strips.
536 */
537 for(i = 0; i < m_nTriCnt; ++i)
538 {
539 pTri = &m_pTri[i];
540
541 // Count the number of empty edges
542 nTest = 0;
543 for(j = 0; j < 3; ++j)
544 {
545 if(!pTri->pAdj[j])
546 {
547 ++nTest;
548 }
549 else
550 {
551 nEdge = j;
552 }
553 }
554
555 if(nTest != 2)
556 continue;
557
558 for(;;)
559 {
560 // A tri with two empty edges is a corner (there are other corners too, but this works so...)
561 while(StripGrow(*pTri, nEdge, -1)) {};
562
563 pTriPrev = pTri;
564 pTri = pTri->pAdj[nEdge];
565 if(!pTri)
566 break;
567
568 // Find the edge we came over
569 nEdge = pTri->EdgeFromAdjTri(*pTriPrev);
570
571 // Step around to the next edge
572 if(++nEdge > 2)
573 nEdge = 0;
574
575 pTriPrev = pTri;
576 pTri = pTri->pAdj[nEdge];
577 if(!pTri)
578 break;
579
580 // Find the edge we came over
581 nEdge = pTri->EdgeFromAdjTri(*pTriPrev);
582
583 // Step around to the next edge
584 if(--nEdge < 0)
585 nEdge = 2;
586
587 #if 0
588 // If we're not tracking the edge, give up
589 nTest = nEdge - 1;
590 if(nTest < 0)
591 nTest = 2;
592 if(pTri->pAdj[nTest])
593 break;
594 else
595 continue;
596 #endif
597 }
598 }
599 }
600
601 #ifdef RND_TRIS_ORDER
602 struct pair
603 {
604 unsigned int i, o;
605 };
606
compare(const void * arg1,const void * arg2)607 static int compare(const void *arg1, const void *arg2)
608 {
609 return ((pair*)arg1)->i - ((pair*)arg2)->i;
610 }
611 #endif
612 /*!***************************************************************************
613 @Function StripImprove
614 @Description Optimises the strip
615 *****************************************************************************/
StripImprove()616 void CStrip::StripImprove()
617 {
618 unsigned int i, j;
619 bool bChanged;
620 int nRepCnt, nChecks;
621 int nMaxChange;
622 #ifdef RND_TRIS_ORDER
623 pair *pnOrder;
624
625 /*
626 Create a random order to process the tris
627 */
628 pnOrder = new pair[m_nTriCnt];
629 #endif
630
631 nRepCnt = 0;
632 nChecks = 2;
633 nMaxChange = 0;
634
635 /*
636 Reduce strip count by growing each of the three strips each tri can start.
637 */
638 while(nChecks)
639 {
640 --nChecks;
641
642 bChanged = false;
643
644 #ifdef RND_TRIS_ORDER
645 /*
646 Create a random order to process the tris
647 */
648 for(i = 0; i < m_nTriCnt; ++i)
649 {
650 pnOrder[i].i = rand() * rand();
651 pnOrder[i].o = i;
652 }
653 qsort(pnOrder, m_nTriCnt, sizeof(*pnOrder), compare);
654 #endif
655
656 /*
657 Process the tris
658 */
659 for(i = 0; i < m_nTriCnt; ++i)
660 {
661 for(j = 0; j < 3; ++j)
662 {
663 #ifdef RND_TRIS_ORDER
664 bChanged |= StripGrow(m_pTri[pnOrder[i].o], j, nMaxChange);
665 #else
666 bChanged |= StripGrow(m_pTri[i], j, nMaxChange);
667 #endif
668 }
669 }
670 ++nRepCnt;
671
672 // Check the results once or twice
673 if(bChanged)
674 nChecks = 2;
675
676 nMaxChange = (nMaxChange == 0 ? -1 : 0);
677 }
678
679 #ifdef RND_TRIS_ORDER
680 delete [] pnOrder;
681 #endif
682 _RPT1(_CRT_WARN, "Reps: %d\n", nRepCnt);
683 }
684 /*!***************************************************************************
685 @Function Output
686 @Output ppui32Strips
687 @Output ppnStripLen The length of the strip
688 @Output pnStripCnt
689 @Description Outputs key information about the strip to the output
690 parameters.
691 *****************************************************************************/
Output(unsigned int ** ppui32Strips,unsigned int ** ppnStripLen,unsigned int * pnStripCnt)692 void CStrip::Output(
693 unsigned int **ppui32Strips,
694 unsigned int **ppnStripLen,
695 unsigned int *pnStripCnt)
696 {
697 unsigned int *pui32Strips;
698 unsigned int *pnStripLen;
699 unsigned int i, j, nIdx, nStrip;
700 CTri *pTri;
701
702 /*
703 Output Strips
704 */
705 pnStripLen = (unsigned int*)malloc(m_nStrips * sizeof(*pnStripLen));
706 pui32Strips = (unsigned int*)malloc((m_nTriCnt + m_nStrips * 2) * sizeof(*pui32Strips));
707 nStrip = 0;
708 nIdx = 0;
709 for(i = 0; i < m_nTriCnt; ++i)
710 {
711 pTri = &m_pTri[i];
712
713 if(pTri->sNew.pRev)
714 continue;
715 _ASSERT(!pTri->sNew.pFwd || pTri->sNew.bWindFwd);
716 _ASSERT(pTri->bOutput == false);
717
718 if(!pTri->sNew.pFwd)
719 {
720 pui32Strips[nIdx++] = pTri->pIdx[0];
721 pui32Strips[nIdx++] = pTri->pIdx[1];
722 pui32Strips[nIdx++] = pTri->pIdx[2];
723 pnStripLen[nStrip] = 1;
724 pTri->bOutput = true;
725 }
726 else
727 {
728 if(pTri->sNew.pFwd == pTri->pAdj[0])
729 {
730 pui32Strips[nIdx++] = pTri->pIdx[2];
731 pui32Strips[nIdx++] = pTri->pIdx[0];
732 }
733 else if(pTri->sNew.pFwd == pTri->pAdj[1])
734 {
735 pui32Strips[nIdx++] = pTri->pIdx[0];
736 pui32Strips[nIdx++] = pTri->pIdx[1];
737 }
738 else
739 {
740 _ASSERT(pTri->sNew.pFwd == pTri->pAdj[2]);
741 pui32Strips[nIdx++] = pTri->pIdx[1];
742 pui32Strips[nIdx++] = pTri->pIdx[2];
743 }
744
745 pnStripLen[nStrip] = 0;
746 do
747 {
748 _ASSERT(pTri->bOutput == false);
749
750 // Increment tris-in-this-strip counter
751 ++pnStripLen[nStrip];
752
753 // Output the new vertex index
754 for(j = 0; j < 3; ++j)
755 {
756 if(
757 (pui32Strips[nIdx-2] != pTri->pIdx[j]) &&
758 (pui32Strips[nIdx-1] != pTri->pIdx[j]))
759 {
760 break;
761 }
762 }
763 _ASSERT(j != 3);
764 pui32Strips[nIdx++] = pTri->pIdx[j];
765
766 // Double-check that the previous three indices are the indices of this tris (in some order)
767 _ASSERT(
768 ((pui32Strips[nIdx-3] == pTri->pIdx[0]) && (pui32Strips[nIdx-2] == pTri->pIdx[1]) && (pui32Strips[nIdx-1] == pTri->pIdx[2])) ||
769 ((pui32Strips[nIdx-3] == pTri->pIdx[1]) && (pui32Strips[nIdx-2] == pTri->pIdx[2]) && (pui32Strips[nIdx-1] == pTri->pIdx[0])) ||
770 ((pui32Strips[nIdx-3] == pTri->pIdx[2]) && (pui32Strips[nIdx-2] == pTri->pIdx[0]) && (pui32Strips[nIdx-1] == pTri->pIdx[1])) ||
771 ((pui32Strips[nIdx-3] == pTri->pIdx[2]) && (pui32Strips[nIdx-2] == pTri->pIdx[1]) && (pui32Strips[nIdx-1] == pTri->pIdx[0])) ||
772 ((pui32Strips[nIdx-3] == pTri->pIdx[1]) && (pui32Strips[nIdx-2] == pTri->pIdx[0]) && (pui32Strips[nIdx-1] == pTri->pIdx[2])) ||
773 ((pui32Strips[nIdx-3] == pTri->pIdx[0]) && (pui32Strips[nIdx-2] == pTri->pIdx[2]) && (pui32Strips[nIdx-1] == pTri->pIdx[1])));
774
775 // Check that the latest three indices are not degenerate
776 _ASSERT(pui32Strips[nIdx-1] != pui32Strips[nIdx-2]);
777 _ASSERT(pui32Strips[nIdx-1] != pui32Strips[nIdx-3]);
778 _ASSERT(pui32Strips[nIdx-2] != pui32Strips[nIdx-3]);
779
780 pTri->bOutput = true;
781
782 // Check that the next triangle is adjacent to this triangle
783 _ASSERT(
784 (pTri->sNew.pFwd == pTri->pAdj[0]) ||
785 (pTri->sNew.pFwd == pTri->pAdj[1]) ||
786 (pTri->sNew.pFwd == pTri->pAdj[2]) ||
787 (!pTri->sNew.pFwd));
788 // Check that this triangle is adjacent to the next triangle
789 _ASSERT(
790 (!pTri->sNew.pFwd) ||
791 (pTri == pTri->sNew.pFwd->pAdj[0]) ||
792 (pTri == pTri->sNew.pFwd->pAdj[1]) ||
793 (pTri == pTri->sNew.pFwd->pAdj[2]));
794
795 pTri = pTri->sNew.pFwd;
796 } while(pTri);
797 }
798
799 ++nStrip;
800 }
801 _ASSERT(nIdx == m_nTriCnt + m_nStrips * 2);
802 _ASSERT(nStrip == m_nStrips);
803
804 // Check all triangles have been output
805 for(i = 0; i < m_nTriCnt; ++i)
806 {
807 _ASSERT(m_pTri[i].bOutput == true);
808 }
809
810 // Check all triangles are present
811 j = 0;
812 for(i = 0; i < m_nStrips; ++i)
813 {
814 j += pnStripLen[i];
815 }
816 _ASSERT(j == m_nTriCnt);
817
818 // Output data
819 *pnStripCnt = m_nStrips;
820 *ppui32Strips = pui32Strips;
821 *ppnStripLen = pnStripLen;
822 }
823
824 /****************************************************************************
825 ** Code
826 ****************************************************************************/
827
828 /*!***************************************************************************
829 @Function PVRTTriStrip
830 @Output ppui32Strips
831 @Output ppnStripLen
832 @Output pnStripCnt
833 @Input pui32TriList
834 @Input nTriCnt
835 @Description Reads a triangle list and generates an optimised triangle strip.
836 *****************************************************************************/
PVRTTriStrip(unsigned int ** ppui32Strips,unsigned int ** ppnStripLen,unsigned int * pnStripCnt,const unsigned int * const pui32TriList,const unsigned int nTriCnt)837 void PVRTTriStrip(
838 unsigned int **ppui32Strips,
839 unsigned int **ppnStripLen,
840 unsigned int *pnStripCnt,
841 const unsigned int * const pui32TriList,
842 const unsigned int nTriCnt)
843 {
844 unsigned int *pui32Strips;
845 unsigned int *pnStripLen;
846 unsigned int nStripCnt;
847
848 /*
849 If the order in which triangles are tested as strip roots is
850 randomised, then several attempts can be made. Use the best result.
851 */
852 for(int i = 0; i <
853 #ifdef RND_TRIS_ORDER
854 5
855 #else
856 1
857 #endif
858 ; ++i)
859 {
860 CStrip stripper(pui32TriList, nTriCnt);
861
862 #ifdef RND_TRIS_ORDER
863 srand(i);
864 #endif
865
866 stripper.StripFromEdges();
867 stripper.StripImprove();
868 stripper.Output(&pui32Strips, &pnStripLen, &nStripCnt);
869
870 if(!i || nStripCnt < *pnStripCnt)
871 {
872 if(i)
873 {
874 FREE(*ppui32Strips);
875 FREE(*ppnStripLen);
876 }
877
878 *ppui32Strips = pui32Strips;
879 *ppnStripLen = pnStripLen;
880 *pnStripCnt = nStripCnt;
881 }
882 else
883 {
884 FREE(pui32Strips);
885 FREE(pnStripLen);
886 }
887 }
888 }
889
890 /*!***************************************************************************
891 @Function PVRTTriStripList
892 @Modified pui32TriList
893 @Input nTriCnt
894 @Description Reads a triangle list and generates an optimised triangle strip.
895 Result is converted back to a triangle list.
896 *****************************************************************************/
PVRTTriStripList(unsigned int * const pui32TriList,const unsigned int nTriCnt)897 void PVRTTriStripList(unsigned int * const pui32TriList, const unsigned int nTriCnt)
898 {
899 unsigned int *pui32Strips;
900 unsigned int *pnStripLength;
901 unsigned int nNumStrips;
902 unsigned int *pui32TriPtr, *pui32StripPtr;
903
904 /*
905 Strip the geometry
906 */
907 PVRTTriStrip(&pui32Strips, &pnStripLength, &nNumStrips, pui32TriList, nTriCnt);
908
909 /*
910 Convert back to a triangle list
911 */
912 pui32StripPtr = pui32Strips;
913 pui32TriPtr = pui32TriList;
914 for(unsigned int i = 0; i < nNumStrips; ++i)
915 {
916 *pui32TriPtr++ = *pui32StripPtr++;
917 *pui32TriPtr++ = *pui32StripPtr++;
918 *pui32TriPtr++ = *pui32StripPtr++;
919
920 for(unsigned int j = 1; j < pnStripLength[i]; ++j)
921 {
922 // Use two indices from previous triangle, flipping tri order alternately.
923 if(j & 0x01)
924 {
925 *pui32TriPtr++ = pui32StripPtr[-1];
926 *pui32TriPtr++ = pui32StripPtr[-2];
927 }
928 else
929 {
930 *pui32TriPtr++ = pui32StripPtr[-2];
931 *pui32TriPtr++ = pui32StripPtr[-1];
932 }
933
934 *pui32TriPtr++ = *pui32StripPtr++;
935 }
936 }
937
938 free(pui32Strips);
939 free(pnStripLength);
940 }
941
942 /*****************************************************************************
943 End of file (PVRTTriStrip.cpp)
944 *****************************************************************************/
945
946