depthSortList.cpp

Public Functions

compareYExtents(const void * e1, const void * e2)

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#include "platform/platform.h"
 25#include "math/mMath.h"
 26#include "console/console.h"
 27#include "collision/depthSortList.h"
 28#include "core/color.h"
 29#include "core/stream/fileStream.h" // TODO, remove this
 30
 31//----------------------------------------------------------------------------
 32
 33// some defines and global parameters that affect poly split routine
 34F32 SPLIT_TOL = 0.0005f;
 35bool ALWAYS_RETURN_FRONT_AND_BACK = false; // if false, split routine will return polys only if a split occurs
 36
 37// more global parameters
 38F32 XZ_TOL    = 0.0f;
 39F32 DEPTH_TOL = 0.01f;
 40#define MIN_Y_DOT 0.05f
 41DepthSortList * gCurrentSort = NULL;
 42S32 gForceOverlap = -1; // force an overlap test to result in an overlap
 43S32 gNoOverlapCount;
 44S32 gBadSpots = 0;
 45
 46//----------------------------------------------------------------------------
 47
 48DepthSortList::DepthSortList()
 49{
 50   mBase = 0;
 51   mBasePoly = NULL;
 52   mBaseNormal = NULL;
 53   mBaseDot = 0.0f;
 54   mBaseYMax = 0.0f;
 55   mMaxTouched = 0;
 56   mBaseExtents = NULL;
 57   VECTOR_SET_ASSOCIATION(mPolyExtentsList);
 58   VECTOR_SET_ASSOCIATION(mPolyIndexList);
 59}
 60
 61DepthSortList::~DepthSortList()
 62{
 63}
 64
 65//----------------------------------------------------------------------------
 66
 67void DepthSortList::clear()
 68{
 69   Parent::clear();
 70
 71   mPolyExtentsList.clear();
 72   mPolyIndexList.clear();
 73
 74   clearSort();
 75}
 76
 77void DepthSortList::clearSort()
 78{
 79   mBase = -1;
 80   mMaxTouched = 0;
 81   gNoOverlapCount = 0;
 82}
 83
 84//----------------------------------------------------------------------------
 85
 86void DepthSortList::end()
 87{
 88   S32 numPoly = mPolyList.size();
 89
 90   if (mPolyList.last().plane.y >= -MIN_Y_DOT)
 91   {
 92      mIndexList.setSize(mPolyList.last().vertexStart);
 93      mPolyList.decrement();
 94      return;
 95   }
 96
 97   Parent::end();
 98
 99   // we deleted this poly, be sure not to add anything more...
100   if (mPolyList.size()!=numPoly)
101      return;
102
103   AssertFatal(mPolyList.last().vertexCount>2,"DepthSortList::end: only two vertices in poly");
104
105   mPolyExtentsList.increment();
106   setExtents(mPolyList.last(),mPolyExtentsList.last());
107   mPolyIndexList.push_back(numPoly-1);
108}
109
110//----------------------------------------------------------------------------
111
112bool DepthSortList::getMapping(MatrixF * mat, Box3F * box)
113{
114   // return list transform and bounds in list space...optional
115   *mat = mMatrix;
116   mat->inverse();
117   box->minExtents.set(-mExtent.x,             0.0f, -mExtent.z);
118   box->maxExtents.set( mExtent.x, 2.0f * mExtent.y,  mExtent.z);
119
120   return true;
121}
122
123//----------------------------------------------------------------------------
124//----------------------------------------------------------------------------
125
126void DepthSortList::setExtents(Poly & poly, PolyExtents & polyExtents)
127{
128   Point3F p = mVertexList[mIndexList[poly.vertexStart]].point;
129   polyExtents.xMin = polyExtents.xMax = p.x;
130   polyExtents.yMin = polyExtents.yMax = p.y;
131   polyExtents.zMin = polyExtents.zMax = p.z;
132   for (S32 i=poly.vertexStart+1; i<poly.vertexStart+poly.vertexCount; i++)
133   {
134      p = mVertexList[mIndexList[i]].point;
135
136      // x
137      if (p.x < polyExtents.xMin)
138         polyExtents.xMin = p.x;
139      else if (p.x > polyExtents.xMax)
140         polyExtents.xMax = p.x;
141
142      // y
143      if (p.y < polyExtents.yMin)
144         polyExtents.yMin = p.y;
145      else if (p.y > polyExtents.yMax)
146         polyExtents.yMax = p.y;
147
148      // z
149      if (p.z < polyExtents.zMin)
150         polyExtents.zMin = p.z;
151      else if (p.z > polyExtents.zMax)
152         polyExtents.zMax = p.z;
153   }
154}
155
156//----------------------------------------------------------------------------
157
158// function for comparing two poly indices
159S32 FN_CDECL compareYExtents( const void* e1, const void* e2)
160{
161   DepthSortList::PolyExtents & poly1 = gCurrentSort->getExtents(*(U32*)e1);
162   DepthSortList::PolyExtents & poly2 = gCurrentSort->getExtents(*(U32*)e2);
163
164   if (poly1.yMin < poly2.yMin)
165      return -1;
166   if (poly2.yMin < poly1.yMin)
167      return 1;
168   return 0;
169}
170
171//----------------------------------------------------------------------------
172
173void DepthSortList::sortByYExtents()
174{
175   gCurrentSort = this;
176   dQsort(mPolyIndexList.address(),mPolyIndexList.size(),sizeof(U32),compareYExtents);
177}
178
179//----------------------------------------------------------------------------
180
181void DepthSortList::set(const MatrixF & mat, Point3F & extents)
182{
183   setBaseTransform(mat);
184   mNormal.set(0,1,0); // ignore polys not facing up...
185   mExtent = extents;
186   mExtent *= 0.5f;
187
188   // set clip planes
189   mPlaneList.clear();
190
191   mPlaneList.increment();
192   mPlaneList.last().set(-1.0f, 0.0f, 0.0f, -mExtent.x);
193   mPlaneList.increment();
194   mPlaneList.last().set( 1.0f, 0.0f, 0.0f, -mExtent.x);
195
196   mPlaneList.increment();
197   mPlaneList.last().set( 0.0f,-1.0f, 0.0f, 0);
198   mPlaneList.increment();
199   mPlaneList.last().set( 0.0f, 1.0f, 0.0f, -2.0f * mExtent.y);
200
201   mPlaneList.increment();
202   mPlaneList.last().set( 0.0f, 0.0f,-1.0f, -mExtent.z);
203   mPlaneList.increment();
204   mPlaneList.last().set( 0.0f, 0.0f, 1.0f, -mExtent.z);
205}
206
207//----------------------------------------------------------------------------
208
209void DepthSortList::setBase(S32 base)
210{
211   mBase = base;
212   getOrderedPoly(mBase, &mBasePoly, &mBaseExtents);
213   mBaseNormal = &mBasePoly->plane;
214   mBaseDot = -mBasePoly->plane.d;
215   mBaseYMax = mBaseExtents->yMax;
216}
217
218//----------------------------------------------------------------------------
219
220bool DepthSortList::sortNext()
221{
222   // find the next poly in the depth order
223   // NOTE: a closer poly may occur before a farther away poly so long as
224   // they don't overlap in the x-z plane...
225   if (++mBase>=<a href="/coding/class/classdepthsortlist/#classdepthsortlist_1a61a4ede65303c421030f3530487d9f2b">mPolyIndexList</a>.size())
226      return false;
227
228   setBase(mBase);
229
230   gBadSpots = 0;
231   ALWAYS_RETURN_FRONT_AND_BACK = false; // split routine will return polys only if a split occurs
232
233   bool switched = false; // haven't switched base poly yet
234   S32 i = 0; // currently comparing base to base+i
235   Poly * testPoly;
236   PolyExtents * testExtents;
237
238   while (mBase+i+1<mPolyIndexList.size())
239   {
240      i++;
241
242      // get test poly...
243      getOrderedPoly(mBase+i,&testPoly,&testExtents);
244      Point3F & testNormal = testPoly->plane;
245      F32 testDot = -testPoly->plane.d;
246
247      // if base poly's y extents don't overlap test poly's, base poly can stay where it is...
248      if (mBase+i>mMaxTouched && mBaseYMax<=testExtents->yMin+DEPTH_TOL)
249         break;
250
251      // if base poly and test poly don't have overlapping x & z extents, then order doesn't matter...stay the same
252      if (mBaseExtents->xMin>=testExtents->xMax-XZ_TOL || mBaseExtents->xMax<=testExtents->xMin+XZ_TOL ||
253          mBaseExtents->zMin>=testExtents->zMax-XZ_TOL || mBaseExtents->zMax<=testExtents->zMin+XZ_TOL)
254         continue;
255
256      // is test poly completely behind base poly? if so, order is fine as it is
257      S32 v;
258      for (v=0; v<testPoly->vertexCount; v++)
259         if (mDot(mVertexList[mIndexList[testPoly->vertexStart+v]].point,*mBaseNormal)>mBaseDot+DEPTH_TOL)
260            break;
261      if (v==testPoly->vertexCount)
262         // test behind base
263         continue;
264
265      // is base poly completely in front of test poly?  if so, order is fine as it is
266      for (v=0; v<mBasePoly->vertexCount; v++)
267         if (mDot(mVertexList[mIndexList[mBasePoly->vertexStart+v]].point,testNormal)<testDot-DEPTH_TOL)
268            break;
269      if (v==<a href="/coding/class/classdepthsortlist/#classdepthsortlist_1a4561fd32be470168ae4063211a8c514e">mBasePoly</a>->vertexCount)
270         // base in front of test
271         continue;
272
273      // if the polys don't overlap in the x-z plane, then order doesn't matter, stay as we are
274      if (!overlap(mBasePoly,testPoly))
275      {
276         gNoOverlapCount++;
277         if (gNoOverlapCount!=<a href="/coding/file/depthsortlist_8cpp/#depthsortlist_8cpp_1a6527f778f65b797b5616c44738f62d4c">gForceOverlap</a>)
278            continue;
279      }
280
281      // handle switching/splitting of polys due to overlap
282      handleOverlap(testPoly,testNormal,testDot,i,switched);
283   }
284   return true;
285}
286
287//----------------------------------------------------------------------------
288
289void DepthSortList::sort()
290{
291   // depth sort mPolyIndexList -- entries are indices into mPolyList (where poly is found) & mPolyExtentsList
292
293   // sort by min y extent
294   sortByYExtents();
295
296   mBase = -1;
297
298   while (sortNext())
299      ;
300}
301
302//----------------------------------------------------------------------------
303
304void DepthSortList::handleOverlap(Poly * testPoly, Point3F & testNormal, F32 testDot, S32 & testOffset, bool & switched)
305{
306   // first reverse the plane tests (i.e., test to see if basePoly behind testPoly or testPoly in front of basePoly...
307   // if either succeeds, switch poly
308   // if they both fail, split base poly
309   // But split anyway if basePoly has already been switched...
310   bool doSwitch = false;
311
312   if (!switched)
313   {
314      S32 v;
315      for (v=0; v<mBasePoly->vertexCount; v++)
316         if (mDot(mVertexList[mIndexList[mBasePoly->vertexStart+v]].point,testNormal)>testDot+DEPTH_TOL)
317            break;
318      if (v==<a href="/coding/class/classdepthsortlist/#classdepthsortlist_1a4561fd32be470168ae4063211a8c514e">mBasePoly</a>->vertexCount)
319         doSwitch = true;
320      else
321      {
322         for (v=0; v<testPoly->vertexCount; v++)
323            if (mDot(mVertexList[mIndexList[testPoly->vertexStart+v]].point,*mBaseNormal)<mBaseDot-DEPTH_TOL)
324               break;
325         if (v==testPoly->vertexCount)
326            doSwitch = true;
327      }
328   }
329
330   // try to split base poly along plane of test poly
331   Poly frontPoly, backPoly;
332   bool splitBase = false, splitTest = false;
333   if (!doSwitch)
334   {
335      splitBase = splitPoly(*mBasePoly,testNormal,testDot,frontPoly,backPoly);
336      if (!splitBase)
337         // didn't take...no splitting happened...try splitting test poly by base poly
338         splitTest = splitPoly(*testPoly,*mBaseNormal,mBaseDot,frontPoly,backPoly);
339   }
340
341   U32 testIdx = mPolyIndexList[mBase+testOffset];
342
343   // should we switch order of test and base poly?  Might have to even if we
344   // don't want to if there's no splitting to do...
345   // Note: possibility that infinite loop can be introduced here...if that happens,
346   // then we need to split along edges of polys
347   if (doSwitch || (!splitTest && !splitBase))
348      {
349      if (!doSwitch && gBadSpots++ > (mPolyIndexList.size()-mBase)<<1)
350         // got here one too many times...just leave and don't touch poly -- avoid infinite loop
351         return;
352
353      // move test poly to the front of the order
354      dMemmove(&mPolyIndexList[mBase+1],&mPolyIndexList[mBase],testOffset*sizeof(U32));
355      mPolyIndexList[mBase] = testIdx;
356
357      // base poly changed...
358      setBase(mBase);
359
360      if (mBase+testOffset>mMaxTouched)
361         mMaxTouched=<a href="/coding/class/classdepthsortlist/#classdepthsortlist_1a774238f0ef5dfff8666251b9975d73e2">mBase</a>+testOffset;
362
363      testOffset=1; // don't need to compare against old base
364      switched=true;
365      return;
366   }
367
368   if (splitBase)
369   {
370      // need one more spot...frontPoly and backPoly replace basePoly
371      setExtents(frontPoly,mPolyExtentsList[mPolyIndexList[mBase]]);
372      mPolyExtentsList.increment();
373      setExtents(backPoly,mPolyExtentsList.last());
374
375      mPolyList[mPolyIndexList[mBase]] = frontPoly;
376      mPolyIndexList.insert(mBase+1);
377      mPolyIndexList[mBase+1] = mPolyList.size();
378      mPolyList.push_back(backPoly);
379
380      // new base poly...
381      setBase(mBase);
382
383      // increase tsetOffset & mMaxTouched because of insertion of back poly
384      testOffset++;
385      mMaxTouched++;
386
387      //
388      switched=false;
389      return;
390   }
391
392   // splitTest -- no other way to get here
393   AssertFatal(splitTest,"DepthSortList::handleOverlap: how did we get here like this?");
394
395   // put frontPoly in front of basePoly, leave backPoly where testPoly was
396
397   // we need one more spot (testPoly broken into front and back)
398   // and we need to shift everything from base up to test down one spot
399   mPolyIndexList.insert(mBase);
400
401   // need one more poly for front poly
402   mPolyIndexList[mBase] = mPolyList.size();
403   mPolyList.push_back(frontPoly);
404   mPolyExtentsList.increment();
405   setExtents(mPolyList.last(),mPolyExtentsList.last());
406
407   // set up back poly
408   mPolyList[testIdx] = backPoly;
409   setExtents(mPolyList[testIdx],mPolyExtentsList[testIdx]);
410
411   // new base poly...
412   setBase(mBase);
413
414   // we inserted an element, increase mMaxTouched...
415   mMaxTouched++;
416
417   testOffset=0;
418   switched = false;
419}
420
421//----------------------------------------------------------------------------
422
423bool DepthSortList::overlap(Poly * poly1, Poly * poly2)
424{
425   // check for overlap without any shortcuts
426   S32 sz1 = poly1->vertexCount;
427   S32 sz2 = poly2->vertexCount;
428
429   Point3F * a1, * b1;
430   Point3F * a2, * b2;
431   Point2F norm;
432   F32 dot;
433   b1 = &mVertexList[mIndexList[poly1->vertexStart+sz1-1]].point;
434   S32 i;
435   for (i=0; i<sz1; i++)
436   {
437      a1 = b1;
438      b1 = &mVertexList[mIndexList[poly1->vertexStart+i]].point;
439
440      // get the mid-point of this edge
441      Point3F mid1 = *a1+*b1;
442      mid1 *= 0.5f;
443      bool midOutside = false;
444
445      b2 = &mVertexList[mIndexList[poly2->vertexStart+sz2-1]].point;
446      for (S32 j=0; j<sz2; j++)
447      {
448         a2 = b2;
449         b2 = &mVertexList[mIndexList[poly2->vertexStart+j]].point;
450
451         // test for intersection of a1-b1 and a2-b2 (on x-z plane)
452
453         // they intersect if a1 & b1 are on opp. sides of line a2-b2
454         // and a2 & b2 are on opp. sides of line a1-b1
455
456         norm.set(a2->z - b2->z, b2->x - a2->x); // normal to line a2-b2
457         dot = norm.x * a2->x + norm.y * a2->z; // dot of a2 and norm
458         if (norm.x * mid1.x + norm.y * mid1.z - dot >= 0) // special check for midpoint of line
459            midOutside = true;
460         if ( ((norm.x * a1->x + norm.y * a1->z) - dot) * ((norm.x * b1->x + norm.y * b1->z) - dot) >= 0 )
461            // a1 & b1 are on the same side of the line a2-b2...edges don't overlap
462            continue;
463
464         norm.set(a1->z - b1->z, b1->x - a1->x); // normal to line a1-b1
465         dot = norm.x * a1->x + norm.y * a1->z; // dot of a1 and norm
466         if ( ((norm.x * a2->x + norm.y * a2->z) - dot) * ((norm.x * b2->x + norm.y * b2->z) - dot) >= 0 )
467            // a2 & b2 are on the same side of the line a1-b1...edges don't overlap
468            continue;
469
470         return true; // edges overlap, so polys overlap
471      }
472      if (!midOutside)
473         return true; // midpoint of a1-b1 is inside the poly
474   }
475
476   // edges don't overlap...but one poly might be contained inside the other
477   Point3F center = mVertexList[mIndexList[poly2->vertexStart]].point;
478   for (i=1; i<sz2; i++)
479      center += mVertexList[mIndexList[poly2->vertexStart+i]].point;
480   center *= 1.0f / (F32)poly2->vertexCount;
481   b1 = &mVertexList[mIndexList[poly1->vertexStart+sz1-1]].point;
482   for (i=0; i<sz1; i++)
483   {
484      a1 = b1;
485      b1 = &mVertexList[mIndexList[poly1->vertexStart+i]].point;
486
487      norm.set(a1->z - b1->z, b1->x - a1->x); // normal to line a1-b1
488      dot = norm.x * a1->x + norm.y * a1->z; // dot of a1 and norm
489      if (center.x * norm.x + center.z * norm.y > dot)
490         // center is outside this edge, poly2 is not inside poly1
491         break;
492   }
493   if (i==sz1)
494      return true; // first vert of poly2 inside poly1 (so all of poly2 inside poly1)
495
496   center = mVertexList[mIndexList[poly1->vertexStart]].point;
497   for (i=1; i<sz1; i++)
498      center += mVertexList[mIndexList[poly1->vertexStart+i]].point;
499   center *= 1.0f / (F32)poly1->vertexCount;
500   b2 = &mVertexList[mIndexList[poly2->vertexStart+sz2-1]].point;
501   for (i=0; i<sz2; i++)
502   {
503      a2 = b2;
504      b2 = &mVertexList[mIndexList[poly2->vertexStart+i]].point;
505
506      norm.set(a2->z - b2->z, b2->x - a2->x); // normal to line a2-b2
507      dot = norm.x * a2->x + norm.y * a2->z; // dot of a1 and norm
508      if (center.x * norm.x + center.z * norm.y > dot)
509         // v is outside this edge, poly1 is not inside poly2
510         break;
511   }
512   if (i==sz2)
513      return true; // first vert of poly1 inside poly2 (so all of poly1 inside poly2)
514
515   return false; // we survived, no overlap
516}
517
518//----------------------------------------------------------------------------
519
520Vector<U32> frontVerts(__FILE__, __LINE__);
521Vector<U32> backVerts(__FILE__, __LINE__);
522
523// Split source poly into front and back.  If either front or back is degenerate, don't do anything.
524// If we have a front and a back, then add the verts to our vertex list and fill out the poly structures.
525bool DepthSortList::splitPoly(const Poly & src, Point3F & normal, F32 k, Poly & frontPoly, Poly & backPoly)
526{
527   frontVerts.clear();
528   backVerts.clear();
529
530   // already degenerate...
531   AssertFatal(src.vertexCount>=3,"DepthSortList::splitPoly - Don't need to split a triangle!");
532
533   S32 startSize = mVertexList.size();
534
535   // Assume back and front are degenerate polygons until proven otherwise.
536   bool backDegen = true, frontDegen = true;
537
538   U32 bIdx;
539   Point3F * a, * b;
540   F32 dota, dotb;
541   S32 signA, signB;
542
543   F32 splitTolSq = SPLIT_TOL * SPLIT_TOL * mDot(normal,normal);
544
545   bIdx = mIndexList[src.vertexStart+src.vertexCount-1];
546   b = &mVertexList[bIdx].point;
547   dotb = mDot(normal,*b)-k;
548
549   // Sign variable coded as follows: 1 for outside, 0 on the plane and -1 for inside.
550   if (dotb*dotb > splitTolSq)
551      signB = dotb > 0.0f ? 1 : -1;
552   else
553      signB = 0;
554
555   S32 i;
556   for (i = 0; i<src.vertexCount; i++)
557   {
558      a = b;
559      bIdx = mIndexList[src.vertexStart+i];
560      b = &mVertexList[bIdx].point;
561      dota = dotb;
562      dotb = mDot(normal,*b)-k;
563      signA = signB;
564      if (dotb*dotb > splitTolSq)
565         signB = dotb > 0.0f ? 1 : -1;
566      else
567         signB = 0;
568
569      switch(signA*3 + signB + 4) // +4 is to make values go from 0 up...hopefully enticing compiler to make a jump-table
570      {
571         case 0:     // A-, B-
572         case 3:     // A., B-
573            backVerts.push_back(bIdx);
574            backDegen = false;
575            break;
576         case 8:     // A+, B+
577         case 5:     // A., B+
578            frontVerts.push_back(bIdx);
579            frontDegen = false;
580            break;
581
582         case 1:     // A-, B.
583         case 4:     // A., B.
584         case 7:     // A+, B.
585            backVerts.push_back(bIdx);
586            frontVerts.push_back(bIdx);
587            break;
588
589         case 2:     // A-, B+
590         {
591            // intersect line A-B with plane
592            F32 dotA = mDot(*a,normal);
593            F32 dotB = mDot(*b,normal);
594            Vertex v;
595            v.point  = *a-*b;
596            v.point *= (k-dotB)/(dotA-dotB);
597            v.point += *b;
598            v.mask = 0;
599            frontVerts.push_back(mVertexList.size());
600            backVerts.push_back(mVertexList.size());
601            frontVerts.push_back(bIdx);
602            mVertexList.push_back(v);
603            b = &mVertexList[bIdx].point; // better get this pointer again since we just incremented vector
604            frontDegen = false;
605            break;
606         }
607         case 6:     // A+, B-
608         {
609            // intersect line A-B with plane
610            F32 dotA = mDot(*a,normal);
611            F32 dotB = mDot(*b,normal);
612            Vertex v;
613            v.point  = *a-*b;
614            v.point *= (k-dotB)/(dotA-dotB);
615            v.point += *b;
616            v.mask = 0;
617            frontVerts.push_back(mVertexList.size());
618            backVerts.push_back(mVertexList.size());
619            backVerts.push_back(bIdx);
620            mVertexList.push_back(v);
621            b = &mVertexList[bIdx].point; // better get this pointer again since we just incremented vector
622            backDegen = false;
623            break;
624         }
625      }
626   }
627
628   // Check for degeneracy.
629
630   if (!ALWAYS_RETURN_FRONT_AND_BACK)
631   {
632      if (frontVerts.size()<3 || backVerts.size()<3 || frontDegen || backDegen)
633      {
634         // didn't need to be split...return two empty polys
635         // and restore vertex list to how it was
636         mVertexList.setSize(startSize);
637         frontPoly.vertexCount = backPoly.vertexCount = 0;
638         return false;
639      }
640   }
641   else
642   {
643      if (frontDegen)
644         frontVerts.clear();
645      if (backDegen)
646         backVerts.clear();
647   }
648
649   // front poly
650   frontPoly.plane = src.plane;
651   frontPoly.object = src.object;
652   frontPoly.material = src.material;
653   frontPoly.vertexStart = mIndexList.size();
654   frontPoly.vertexCount = frontVerts.size();
655   frontPoly.surfaceKey = src.surfaceKey;
656   frontPoly.polyFlags = src.polyFlags;
657
658   // back poly
659   backPoly.plane = src.plane;
660   backPoly.object = src.object;
661   backPoly.material = src.material;
662   backPoly.vertexStart = frontPoly.vertexStart + frontPoly.vertexCount;
663   backPoly.vertexCount = backVerts.size();
664   backPoly.surfaceKey = src.surfaceKey;
665   backPoly.polyFlags = src.polyFlags;
666
667   // add indices
668   mIndexList.setSize(backPoly.vertexStart+backPoly.vertexCount);
669
670   if( frontPoly.vertexCount ) {
671      dMemcpy(&mIndexList[frontPoly.vertexStart],
672         frontVerts.address(),
673         sizeof(U32)*frontPoly.vertexCount);
674   }
675
676   if( backPoly.vertexCount ) {
677      dMemcpy(&mIndexList[backPoly.vertexStart],
678         backVerts.address(),
679         sizeof(U32)*backPoly.vertexCount);
680   }
681
682   return true;
683}
684
685//----------------------------------------------------------------------------
686
687Vector<DepthSortList::Poly> gWorkListA(256, __FILE__, __LINE__ );
688Vector<DepthSortList::Poly> gWorkListB(256, __FILE__, __LINE__ );
689Vector<DepthSortList::Poly> gWorkListJunkBin(256, __FILE__, __LINE__ );
690
691void DepthSortList::depthPartition(const Point3F * sourceVerts, U32 numVerts, Vector<Poly> & partition, Vector<Point3F> & partitionVerts)
692{
693   // create the depth partition of the passed poly
694   // a depth partition is a partition of the poly on the
695   // x-z plane so that each sub-poly in the partition can be
696   // mapped onto exactly one plane in the depth list (i.e.,
697   // those polys found in mPolyIndexList... the ones that are
698   // depth sorted).  The plane the sub-polys are mapped onto
699   // is the plane of the closest facing poly.
700   //
701   // y-coord of input polys are ignored, and are remapped
702   // on output to put the output polys on the
703   // corresponding planes.
704
705   // This routine is confusing because there are three lists of polys.
706   //
707   // The source list (passed in as a single poly, but becomes a list as
708   // it is split up) comprises the poly to be partitioned.  Verts for sourcePoly
709   // are held in sourceVerts when passed to this routine, but immediately copied
710   // to mVertexList (and indices are added for each vert to mIndexList).
711   //
712   // The scraps list is generated from the source poly (it contains the outside
713   // piece of each cut that is made).  Indices for polys in the scraps list are
714   // found in mIndexList and verts are found in mVerts list.  Note that the depthPartition
715   // routine will add verts and indices to the member lists, but not polys.
716   //
717   // Finally, the partition list is the end result -- the depth partition.  These
718   // polys are not indexed polys.  The vertexStart field indexes directly into partitionVerts
719   // array.
720
721   if (mBase<0)
722      // begin the depth sort
723      sortByYExtents();
724
725   // apply cookie cutter to these polys
726   Vector<Poly> * sourceList = &gWorkListA;
727   sourceList->clear();
728
729   // add source poly for to passed verts
730   sourceList->increment();
731   sourceList->last().vertexStart = mIndexList.size();
732   sourceList->last().vertexCount = numVerts;
733
734   // add verts of source poly to mVertexList and mIndexList
735   mVertexList.setSize(mVertexList.size()+numVerts);
736   mIndexList.setSize(mIndexList.size()+numVerts);
737   for (S32 v=0; v<numVerts; v++)
738   {
739      mVertexList[mVertexList.size()-numVerts+v].point = sourceVerts[v];
740      mIndexList[mIndexList.size()-numVerts+v] = mVertexList.size()-numVerts+v;
741   }
742
743   // put scraps from cookie cutter in this list
744   Vector<Poly> * scraps = &gWorkListB;
745   scraps->clear();
746
747   gWorkListJunkBin.clear();
748
749   S32 i=0;
750   while (sourceList->size())
751   {
752      if (i>=<a href="/coding/class/classdepthsortlist/#classdepthsortlist_1a774238f0ef5dfff8666251b9975d73e2">mBase</a> && !sortNext())
753         // that's it, no more polys to sort
754         break;
755      AssertFatal(i<=<a href="/coding/class/classdepthsortlist/#classdepthsortlist_1a774238f0ef5dfff8666251b9975d73e2">mBase</a>,"DepthSortList::depthPartition - exceeded mBase.");
756
757      // use the topmost poly as the cookie cutter
758      Poly & cutter = mPolyList[mPolyIndexList[i]];
759      S32 startVert = partitionVerts.size();
760
761     bool allowclipping = cutter.polyFlags & CLIPPEDPOLYLIST_FLAG_ALLOWCLIPPING;
762
763      S32 j;
764      for (j=0; j<sourceList->size(); j++)
765      {
766         Poly toCut = (*sourceList)[j];
767
768       if(allowclipping)
769            cookieCutter(cutter,toCut,*scraps,partition,partitionVerts);
770       else
771          cookieCutter(cutter,toCut,gWorkListJunkBin,partition,partitionVerts);
772      }
773
774      // project all the new verts onto the cutter's plane
775      AssertFatal(mFabs(cutter.plane.y)>=<a href="/coding/file/depthsortlist_8cpp/#depthsortlist_8cpp_1a0cdba6eae1b2c252163bcd9e2fba3783">MIN_Y_DOT</a>,"DepthSortList::depthPartition - below MIN_Y_DOT.");
776      F32 invY = -1.0f / cutter.plane.y;
777      for (j=startVert; j<partitionVerts.size(); j++)
778         partitionVerts[j].y = invY * (cutter.plane.d + cutter.plane.x * partitionVerts[j].x + cutter.plane.z * partitionVerts[j].z);
779
780     if(allowclipping)
781     {
782         sourceList->clear();
783         // swap work lists -- scraps become source for next closest poly
784         Vector<Poly> * tmpListPtr = sourceList;
785         sourceList = scraps;
786         scraps = tmpListPtr;
787     }
788      i++;
789   }
790}
791
792//----------------------------------------------------------------------------
793
794void DepthSortList::cookieCutter(Poly & cutter, Poly & cuttee,
795                                 Vector<Poly> & scraps,                                   // outsides
796                                 Vector<Poly> & cookies, Vector<Point3F> & cookieVerts)   // insides
797{
798   // perhaps going too far with the cookie cutter analogy, but...
799   // cutter is used to cut cuttee
800   //
801   // the part that is inside of all cutter edges (on x-z plane)
802   // is put into the "cookie" list, parts that are outside are put
803   // onto the "scraps" list.  "scraps" are indexed polys with indices
804   // and vertices in mIndexList and mVertexList.  Cookies aren't indexed
805   // and points go into cookieVerts list.
806
807   ALWAYS_RETURN_FRONT_AND_BACK = true; // split routine will return polys even if no split occurs
808
809   // save off current state in case nothing inside all the edges of cutter (i.e., no "cookie")
810   S32 vsStart  = cuttee.vertexStart;
811   S32 vcStart  = cuttee.vertexCount;
812   S32 milStart = mIndexList.size();
813   S32 mvlStart = mVertexList.size();
814   S32 scStart  = scraps.size();
815
816   Point3F a, b;
817   Poly scrap;
818   a = mVertexList[mIndexList[cutter.vertexStart+cutter.vertexCount-1]].point;
819   for (S32 i=0; i<cutter.vertexCount; i++)
820   {
821      b = mVertexList[mIndexList[cutter.vertexStart+i]].point;
822      Point3F n(a.z-b.z,0.0f,b.x-a.x);
823      F32 k = mDot(n,a);
824      splitPoly(cuttee,n,k,scrap,cuttee);
825      if (scrap.vertexCount)
826         scraps.push_back(scrap);
827      if (!cuttee.vertexCount)
828         // cut down to nothing...no need to keep cutting
829         break;
830      a = b;
831   }
832   if (cuttee.vertexCount)
833   {
834      // cuttee is non-degenerate, add it to cookies
835      cookies.push_back(cuttee);
836      cookies.last().vertexStart = cookieVerts.size();
837      for (S32 i=0; i<cuttee.vertexCount; i++)
838         cookieVerts.push_back(mVertexList[mIndexList[cuttee.vertexStart+i]].point);
839   }
840   else
841   {
842      // no cookie -- leave things as they were (except add cuttee to scraps)
843      cuttee.vertexStart = vsStart;
844      cuttee.vertexCount = vcStart;
845      mIndexList.setSize(milStart);
846      mVertexList.setSize(mvlStart);
847      scraps.setSize(scStart);
848      scraps.push_back(cuttee);
849   }
850}
851
852//----------------------------------------------------------------------------
853