src/BVH/BVH_Sorter.lxx

   1 // Created on: 2014-01-10
   2 // Created by: Denis BOGOLEPOV
   3 // Copyright (c) 2013-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 // =======================================================================
  17 // function : Perform
  18 // purpose  :
  19 // =======================================================================
  20 template<class T, int N>
  21 void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>*         theSet,
  22                                 const Standard_Integer theAxis)
  23 {
  24   Perform (theSet, theAxis, 0, theSet->Size() - 1);
  25 }
  26
  27 // =======================================================================
  28 // function : Perform
  29 // purpose  :
  30 // =======================================================================
  31 template<class T, int N>
  32 void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>*         theSet,
  33                                 const Standard_Integer theAxis,
  34                                 const Standard_Integer theBegElement,
  35                                 const Standard_Integer theEndElement)
  36 {
  37   Standard_Integer aLft = theBegElement;
  38   Standard_Integer aRgh = theEndElement;
  39
  40   T aPivot = theSet->Center ((aRgh + aLft) / 2, theAxis);
  41
  42   while (aLft < aRgh)
  43   {
  44     while (theSet->Center (aLft, theAxis) < aPivot && aLft < theEndElement)
  45     {
  46       ++aLft;
  47     }
  48
  49     while (theSet->Center (aRgh, theAxis) > aPivot && aRgh > theBegElement)
  50     {
  51       --aRgh;
  52     }
  53
  54     if (aLft <= aRgh)
  55     {
  56       if (aLft != aRgh)
  57       {
  58         theSet->Swap (aLft, aRgh);
  59       }
  60
  61       ++aLft;
  62       --aRgh;
  63     }
  64   }
  65
  66   if (aRgh > theBegElement)
  67   {
  68     Perform (theSet, theAxis, theBegElement, aRgh);
  69   }
  70
  71   if (aLft < theEndElement)
  72   {
  73     Perform (theSet, theAxis, aLft, theEndElement);
  74   }
  75 }