shadowVolumeBSP.cpp

Engine/source/lighting/common/shadowVolumeBSP.cpp

More...

Detailed Description

  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 "lighting/common/shadowVolumeBSP.h"
 26
 27#include "lighting/lightInfo.h"
 28#include "math/mPlane.h"
 29
 30
 31ShadowVolumeBSP::ShadowVolumeBSP() :
 32   mSVRoot(0),
 33   mNodeStore(0),
 34   mPolyStore(0),
 35   mFirstInteriorNode(0)
 36{
 37}
 38
 39ShadowVolumeBSP::~ShadowVolumeBSP()
 40{
 41   for(U32 i = 0; i < mSurfaces.size(); i++)
 42      delete mSurfaces[i];
 43}
 44
 45void ShadowVolumeBSP::insertShadowVolume(SVNode ** root, U32 volume)
 46{
 47   SVNode * traverse = mShadowVolumes[volume];
 48
 49   // insert 'em
 50   while(traverse)
 51   {
 52      // copy it
 53      *root = createNode();
 54      (*root)->mPlaneIndex = traverse->mPlaneIndex;
 55      (*root)->mSurfaceInfo = traverse->mSurfaceInfo;
 56      (*root)->mShadowVolume = traverse->mShadowVolume;
 57
 58      // do the next
 59      root = &(*root)->mFront;
 60      traverse = traverse->mFront;
 61   }
 62}
 63
 64ShadowVolumeBSP::SVNode::Side ShadowVolumeBSP::whichSide(SVPoly * poly, const PlaneF & plane) const
 65{
 66   bool front = false;
 67   bool back = false;
 68
 69   for(U32 i = 0; i < poly->mWindingCount; i++)
 70   {
 71      switch(plane.whichSide(poly->mWinding[i]))
 72      {
 73         case PlaneF::Front:
 74            if(back)
 75               return(SVNode::Split);
 76            front = true;
 77            break;
 78
 79         case PlaneF::Back:
 80            if(front)
 81               return(SVNode::Split);
 82            back = true;
 83            break;
 84
 85         default:
 86            break;
 87      }
 88   }
 89
 90   AssertFatal(!(front && back), "ShadowVolumeBSP::whichSide - failed to classify poly");
 91
 92   if(!front && !back)
 93      return(SVNode::On);
 94
 95   return(front ? SVNode::Front : SVNode::Back);
 96}
 97
 98void ShadowVolumeBSP::splitPoly(SVPoly * poly, const PlaneF & plane, SVPoly ** front, SVPoly ** back)
 99{
100   PlaneF::Side sides[SVPoly::MaxWinding];
101
102   U32 i;
103   for(i = 0; i < poly->mWindingCount; i++)
104      sides[i] = plane.whichSide(poly->mWinding[i]);
105
106   // create the polys
107   (*front) = createPoly();
108   (*back) = createPoly();
109
110   // copy the info
111   (*front)->mWindingCount = (*back)->mWindingCount = 0;
112   (*front)->mPlane = (*back)->mPlane = poly->mPlane;
113   (*front)->mTarget = (*back)->mTarget = poly->mTarget;
114   (*front)->mSurfaceInfo = (*back)->mSurfaceInfo = poly->mSurfaceInfo;
115   (*front)->mShadowVolume = (*back)->mShadowVolume = poly->mShadowVolume;
116
117   //
118   for(i = 0; i < poly->mWindingCount; i++)
119   {
120      U32 j = (i+1) % poly->mWindingCount;
121
122      if(sides[i] == PlaneF::On)
123      {
124         (*front)->mWinding[(*front)->mWindingCount++] = poly->mWinding[i];
125         (*back)->mWinding[(*back)->mWindingCount++] = poly->mWinding[i];
126      }
127      else if(sides[i] == PlaneF::Front)
128      {
129         (*front)->mWinding[(*front)->mWindingCount++] = poly->mWinding[i];
130
131         if(sides[j] == PlaneF::Back)
132         {
133            const Point3F & a = poly->mWinding[i];
134            const Point3F & b = poly->mWinding[j];
135
136            F32 t = plane.intersect(a, b);
137            AssertFatal(t >=0 && t <= 1, "ShadowVolumeBSP::splitPoly - bad plane intersection");
138
139            Point3F pos;
140            pos.interpolate(a, b, t);
141
142            //
143            (*front)->mWinding[(*front)->mWindingCount++] =
144               (*back)->mWinding[(*back)->mWindingCount++] = pos;
145         }
146      }
147      else if(sides[i] == PlaneF::Back)
148      {
149         (*back)->mWinding[(*back)->mWindingCount++] = poly->mWinding[i];
150
151         if(sides[j] == PlaneF::Front)
152         {
153            const Point3F & a = poly->mWinding[i];
154            const Point3F & b = poly->mWinding[j];
155
156            F32 t = plane.intersect(a, b);
157            AssertFatal(t >=0 && t <= 1, "ShadowVolumeBSP::splitPoly - bad plane intersection");
158
159            Point3F pos;
160            pos.interpolate(a, b, t);
161
162            (*front)->mWinding[(*front)->mWindingCount++] =
163               (*back)->mWinding[(*back)->mWindingCount++] = pos;
164         }
165      }
166   }
167
168   AssertFatal((*front)->mWindingCount && (*back)->mWindingCount, "ShadowVolume::split - invalid split");
169}
170
171void ShadowVolumeBSP::addUniqueVolume(SurfaceInfo * surfaceInfo, U32 volume)
172{
173   if(!surfaceInfo)
174      return;
175
176   for(U32 i = 0; i < surfaceInfo->mShadowed.size(); i++)
177      if(surfaceInfo->mShadowed[i] == volume)
178         return;
179
180   // add it
181   surfaceInfo->mShadowed.push_back(volume);
182}
183
184void ShadowVolumeBSP::insertPoly(SVNode ** root, SVPoly * poly)
185{
186   if(!(*root))
187   {
188      insertShadowVolume(root, poly->mShadowVolume);
189
190      if(poly->mSurfaceInfo && !mFirstInteriorNode)
191         mFirstInteriorNode = mShadowVolumes[poly->mShadowVolume];
192
193      if(poly->mTarget)
194         addUniqueVolume(poly->mTarget->mSurfaceInfo, poly->mShadowVolume);
195
196      recyclePoly(poly);
197      return;
198   }
199
200   const PlaneF & plane = getPlane((*root)->mPlaneIndex);
201
202   //
203   switch(whichSide(poly, plane))
204   {
205      case SVNode::On:
206      case SVNode::Front:
207         insertPolyFront(root, poly);
208         break;
209
210      case SVNode::Back:
211         insertPolyBack(root, poly);
212         break;
213
214      case SVNode::Split:
215      {
216         SVPoly * front;
217         SVPoly * back;
218
219         splitPoly(poly, plane, &front, &back);
220         recyclePoly(poly);
221
222         insertPolyFront(root, front);
223         insertPolyBack(root, back);
224
225         break;
226      }
227   }
228}
229
230void ShadowVolumeBSP::insertPolyFront(SVNode ** root, SVPoly * poly)
231{
232   // POLY type node?
233   if(!(*root)->mFront)
234   {
235      if(poly->mSurfaceInfo && !mFirstInteriorNode)
236         mFirstInteriorNode = mShadowVolumes[poly->mShadowVolume];
237      addUniqueVolume(poly->mSurfaceInfo, (*root)->mShadowVolume);
238      recyclePoly(poly);
239   }
240   else
241      insertPoly(&(*root)->mFront, poly);
242}
243
244void ShadowVolumeBSP::insertPolyBack(SVNode ** root, SVPoly * poly)
245{
246   // list of nodes where an interior has been added
247   if(poly->mSurfaceInfo && !(*root)->mSurfaceInfo && !(*root)->mBack)
248   {
249      if(!mFirstInteriorNode)
250         mFirstInteriorNode = mShadowVolumes[poly->mShadowVolume];
251      mParentNodes.push_back(*root);
252   }
253
254   // POLY type node?
255   if(!(*root)->mFront)
256   {
257      poly->mTarget = (*root);
258      insertPoly(&(*root)->mBack, poly);
259   }
260   else
261      insertPoly(&(*root)->mBack, poly);
262}
263
264//------------------------------------------------------------------------------
265
266ShadowVolumeBSP::SVNode * ShadowVolumeBSP::createNode()
267{
268   SVNode * node;
269   if(mNodeStore)
270   {
271      node = mNodeStore;
272      mNodeStore = mNodeStore->mFront;
273   }
274   else
275      node = mNodeChunker.alloc();
276
277   //
278   node->mFront = node->mBack = 0;
279   node->mShadowVolume = 0;
280   node->mSurfaceInfo = 0;
281
282   return(node);
283}
284
285void ShadowVolumeBSP::recycleNode(SVNode * node)
286{
287   if(!node)
288      return;
289
290   recycleNode(node->mFront);
291   recycleNode(node->mBack);
292
293   //
294   node->mFront = mNodeStore;
295   node->mBack = 0;
296   mNodeStore = node;
297}
298
299ShadowVolumeBSP::SVPoly * ShadowVolumeBSP::createPoly()
300{
301   SVPoly * poly;
302
303   if(mPolyStore)
304   {
305      poly = mPolyStore;
306      mPolyStore = mPolyStore->mNext;
307   }
308   else
309      poly = mPolyChunker.alloc();
310
311   //
312   poly->mNext = 0;
313   poly->mTarget = 0;
314   poly->mSurfaceInfo = 0;
315   poly->mShadowVolume = 0;
316   poly->mWindingCount = 0;
317
318   for (U32 i = 0; i < SVPoly::MaxWinding; i++)
319      poly->mWinding[i] = Point3F(0.0f, 0.0f, 0.0f);
320
321   return(poly);
322}
323
324void ShadowVolumeBSP::recyclePoly(SVPoly * poly)
325{
326   if(!poly)
327      return;
328
329   recyclePoly(poly->mNext);
330
331   //
332   poly->mNext = mPolyStore;
333   mPolyStore = poly;
334}
335
336U32 ShadowVolumeBSP::insertPlane(const PlaneF & plane)
337{
338   mPlanes.push_back(plane);
339   return(mPlanes.size() - 1);
340}
341
342const PlaneF & ShadowVolumeBSP::getPlane(U32 index) const
343{
344   AssertFatal(index < mPlanes.size(), "ShadowVolumeBSP::getPlane - index out of range");
345   return(mPlanes[index]);
346}
347
348ShadowVolumeBSP::SVNode * ShadowVolumeBSP::getShadowVolume(U32 index)
349{
350   AssertFatal(index < mShadowVolumes.size(), "ShadowVolumeBSP::getShadowVolume - index out of range");
351   return(mShadowVolumes[index]);
352}
353
354bool ShadowVolumeBSP::testPoint(SVNode * root, const Point3F & pnt)
355{
356   const PlaneF & plane = getPlane(root->mPlaneIndex);
357   switch(plane.whichSide(pnt))
358   {
359      case PlaneF::On:
360
361         if(!root->mFront)
362            return(true);
363         else
364         {
365            if(testPoint(root->mFront, pnt))
366               return(true);
367            else
368            {
369               if(!root->mBack)
370                  return(false);
371               else
372                  return(testPoint(root->mBack, pnt));
373            }
374         }
375         break;
376
377      //
378      case PlaneF::Front:
379         if(root->mFront)
380            return(testPoint(root->mFront, pnt));
381         else
382            return(true);
383         break;
384
385      //
386      case PlaneF::Back:
387         if(root->mBack)
388            return(testPoint(root->mBack, pnt));
389         else
390            return(false);
391         break;
392   }
393
394   return(false);
395}
396
397//------------------------------------------------------------------------------
398bool ShadowVolumeBSP::testPoly(SVNode * root, SVPoly * poly)
399{
400   const PlaneF & plane = getPlane(root->mPlaneIndex);
401   switch(whichSide(poly, plane))
402   {
403      case SVNode::On:
404      case SVNode::Front:
405         if(root->mFront)
406            return(testPoly(root->mFront, poly));
407
408         recyclePoly(poly);
409         return(true);
410
411      case SVNode::Back:
412         if(root->mBack)
413            return(testPoly(root->mBack, poly));
414         recyclePoly(poly);
415         break;
416
417      case SVNode::Split:
418      {
419         if(!root->mFront)
420         {
421            recyclePoly(poly);
422            return(true);
423         }
424
425         SVPoly * front;
426         SVPoly * back;
427
428         splitPoly(poly, plane, &front, &back);
429         recyclePoly(poly);
430
431         if(testPoly(root->mFront, front))
432         {
433            recyclePoly(back);
434            return(true);
435         }
436
437         if(root->mBack)
438            return(testPoly(root->mBack, back));
439
440         recyclePoly(back);
441         break;
442      }
443   }
444   return(false);
445}
446
447//------------------------------------------------------------------------------
448void ShadowVolumeBSP::buildPolyVolume(SVPoly * poly, LightInfo * light)
449{
450   if(light->getType() != LightInfo::Vector)
451      return;
452
453   // build the poly
454   Point3F pointOffset = light->getDirection() * 10.f;
455
456   // create the shadow volume
457   mShadowVolumes.increment();
458   SVNode ** traverse = &mShadowVolumes.last();
459   U32 shadowVolumeIndex = mShadowVolumes.size() - 1;
460
461   for(U32 i = 0; i < poly->mWindingCount; i++)
462   {
463      U32 j = (i + 1) % poly->mWindingCount;
464      if(poly->mWinding[i] == poly->mWinding[j])
465         continue;
466
467      (*traverse) = createNode();
468      Point3F & a = poly->mWinding[i];
469      Point3F & b = poly->mWinding[j];
470      Point3F c = b + pointOffset;
471
472      (*traverse)->mPlaneIndex = insertPlane(PlaneF(a,b,c));
473      (*traverse)->mShadowVolume = shadowVolumeIndex;
474
475      traverse = &(*traverse)->mFront;
476   }
477
478   // do the poly node
479   (*traverse) = createNode();
480   (*traverse)->mPlaneIndex = insertPlane(poly->mPlane);
481   (*traverse)->mShadowVolume = poly->mShadowVolume = shadowVolumeIndex;
482}
483
484ShadowVolumeBSP::SVPoly * ShadowVolumeBSP::copyPoly(SVPoly * src)
485{
486   SVPoly * poly = createPoly();
487   dMemcpy(poly, src, sizeof(SVPoly));
488
489   poly->mTarget = 0;
490   poly->mNext = 0;
491
492   return(poly);
493}
494
495//------------------------------------------------------------------------------
496void ShadowVolumeBSP::addToPolyList(SVPoly ** store, SVPoly * poly) const
497{
498   poly->mNext = *store;
499   *store = poly;
500}
501
502//------------------------------------------------------------------------------
503void ShadowVolumeBSP::clipPoly(SVNode * root, SVPoly ** store, SVPoly * poly)
504{
505   if(!root)
506   {
507      recyclePoly(poly);
508      return;
509   }
510
511   const PlaneF & plane = getPlane(root->mPlaneIndex);
512
513   switch(whichSide(poly, plane))
514   {
515      case SVNode::On:
516      case SVNode::Back:
517         if(root->mBack)
518            clipPoly(root->mBack, store, poly);
519         else
520            addToPolyList(store, poly);
521         break;
522
523      case SVNode::Front:
524         // encountered POLY node?
525         if(!root->mFront)
526         {
527            recyclePoly(poly);
528            return;
529         }
530         else
531            clipPoly(root->mFront, store, poly);
532         break;
533
534      case SVNode::Split:
535      {
536         SVPoly * front;
537         SVPoly * back;
538
539         splitPoly(poly, plane, &front, &back);
540         AssertFatal(front && back, "ShadowVolumeBSP::clipPoly: invalid split");
541         recyclePoly(poly);
542
543         // front
544         if(!root->mFront)
545         {
546            recyclePoly(front);
547            return;
548         }
549         else
550            clipPoly(root->mFront, store, front);
551
552         // back
553         if(root->mBack)
554            clipPoly(root->mBack, store, back);
555         else
556            addToPolyList(store, back);
557         break;
558      }
559   }
560}
561
562// clip a poly to it's own shadow volume
563void ShadowVolumeBSP::clipToSelf(SVNode * root, SVPoly ** store, SVPoly * poly)
564{
565   if(!root)
566   {
567      addToPolyList(store, poly);
568      return;
569   }
570
571   const PlaneF & plane = getPlane(root->mPlaneIndex);
572
573   switch(whichSide(poly, plane))
574   {
575      case SVNode::Front:
576         clipToSelf(root->mFront, store, poly);
577         break;
578
579      case SVNode::On:
580         addToPolyList(store, poly);
581         break;
582
583      case SVNode::Back:
584         recyclePoly(poly);
585         break;
586
587      case SVNode::Split:
588      {
589         SVPoly * front = 0;
590         SVPoly * back = 0;
591         splitPoly(poly, plane, &front, &back);
592         AssertFatal(front && back, "ShadowVolumeBSP::clipToSelf: invalid split");
593
594         recyclePoly(poly);
595         recyclePoly(back);
596
597         clipToSelf(root->mFront, store, front);
598         break;
599      }
600   }
601}
602
603//------------------------------------------------------------------------------
604F32 ShadowVolumeBSP::getPolySurfaceArea(SVPoly * poly) const
605{
606   if(!poly)
607      return(0.f);
608
609   Point3F areaNorm(0,0,0);
610   for(U32 i = 0; i < poly->mWindingCount; i++)
611   {
612      U32 j = (i + 1) % poly->mWindingCount;
613
614      Point3F tmp;
615      mCross(poly->mWinding[i], poly->mWinding[j], &tmp);
616
617      areaNorm += tmp;
618   }
619
620   F32 area = mDot(poly->mPlane, areaNorm);
621
622   if(area < 0.f)
623      area *= -0.5f;
624   else
625      area *= 0.5f;
626
627   if(poly->mNext)
628      area += getPolySurfaceArea(poly->mNext);
629
630   return(area);
631}
632
633//------------------------------------------------------------------------------
634F32 ShadowVolumeBSP::getClippedSurfaceArea(SVNode * root, SVPoly * poly)
635{
636   SVPoly * store = 0;
637   clipPoly(root, &store, poly);
638
639   F32 area = getPolySurfaceArea(store);
640   recyclePoly(store);
641   return(area);
642}
643
644
645//-------------------------------------------------------------------------------
646// Class SceneLighting::ShadowVolumeBSP
647//-------------------------------------------------------------------------------
648
649void ShadowVolumeBSP::movePolyList(SVPoly ** dest, SVPoly * list) const
650{
651   while(list)
652   {
653      SVPoly * next = list->mNext;
654      addToPolyList(dest, list);
655      list = next;
656   }
657}
658
659
660F32 ShadowVolumeBSP::getLitSurfaceArea(SVPoly * poly, SurfaceInfo * surfaceInfo)
661{
662   // clip the poly to the shadow volumes
663   SVPoly * polyStore = poly;
664
665   for(U32 i = 0; polyStore && (i < surfaceInfo->mShadowed.size()); i++)
666   {
667      SVPoly * polyList = 0;
668      SVPoly * traverse = polyStore;
669
670      while(traverse)
671      {
672         SVPoly * next = traverse->mNext;
673         traverse->mNext = 0;
674
675         SVPoly * currentStore = 0;
676
677         clipPoly(mShadowVolumes[surfaceInfo->mShadowed[i]], &currentStore, traverse);
678
679         if(currentStore)
680            movePolyList(&polyList, currentStore);
681
682         traverse = next;
683      }
684      polyStore = polyList;
685   }
686
687   // get the lit area
688   F32 area = getPolySurfaceArea(polyStore);
689   recyclePoly(polyStore);
690   return(area);
691}
692
693//------------------------------------------------------------------------------
694void ShadowVolumeBSP::removeLastInterior()
695{
696   if(!mSVRoot || !mFirstInteriorNode)
697      return;
698
699   AssertFatal(mFirstInteriorNode->mSurfaceInfo, "No surface info for first interior node!");
700
701   // reset the planes
702   mPlanes.setSize(mFirstInteriorNode->mPlaneIndex);
703
704   U32 i;
705
706   // flush the shadow volumes
707   for(i = mFirstInteriorNode->mShadowVolume; i < mShadowVolumes.size(); i++)
708      recycleNode(mShadowVolumes[i]);
709   mShadowVolumes.setSize(mFirstInteriorNode->mShadowVolume);
710
711   // flush the interior nodes
712   if(!mParentNodes.size() && (mFirstInteriorNode->mShadowVolume == mSVRoot->mShadowVolume))
713   {
714      recycleNode(mSVRoot);
715      mSVRoot = 0;
716   }
717   else
718   {
719      for(i = 0; i < mParentNodes.size(); i++)
720      {
721         recycleNode(mParentNodes[i]->mBack);
722         mParentNodes[i]->mBack = 0;
723      }
724   }
725
726   // flush the surfaces
727   for(i = 0; i < mSurfaces.size(); i++)
728      delete mSurfaces[i];
729   mSurfaces.clear();
730
731   mFirstInteriorNode = 0;
732}
733