src/Bnd/Bnd_BoundSortBox.cxx

   1 // File:        Bnd_BoundSortBox.cxx
   2 // Created:     Tue Nov 24 16:06:09 1992
   3 // Author:      Didier PIFFAULT
   4 //              <dpf@phylox>
   5
   6 #include <Bnd_BoundSortBox.ixx>
   7 #include <Standard_NullValue.hxx>
   8 #include <Standard_MultiplyDefined.hxx>
   9 #include <Bnd_Array1OfBox.hxx>
  10 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  11 #include <TColStd_DataMapIteratorOfDataMapOfIntegerInteger.hxx>
  12
  13 //#if defined(WNT) || defined(LIN)
  14 # include <stdio.h>
  15 //#endif  // WNT
  16
  17 //-- ================================================================================
  18 //--  lbr le 27 fev 97
  19 //--
  20 //--
  21 //--      Initialisation:  Une boite englobante BE
  22 //--                       Une liste de boites Bi (Bi dans BE)
  23 //--
  24 //--      Compare(b) renvoie la liste des Boites Bi touchees par b
  25 //--
  26 //--
  27 //--   Principe General:
  28 //--
  29 //--       1) On discretise la boite BE en N*N*N  voxels
  30 //--          Chaque boite Bi touche un certain nombre de voxels
  31 //--          Bi touche { Vijk  avec i0<=i<=i1 ...  k0<=k<=k1 }
  32 //--       2) On projete sur chaque axe X,Y,Z les boites Bi
  33 //--          pour obtenir les structures suivantes :
  34 //--
  35 //--          Exemple :
  36 //--
  37 //--             la boite i1 touche les voxels { Vijk  avec 1<=i<=N-1  ... }
  38 //--             la boite i2 touche les voxels { Vijk  avec 2<=i<=3  ... }
  39 //--             la boite i3 touche les voxels { Vijk  avec 1<=i<=2  ... }
  40 //--
  41 //--
  42 //--         X[.] |  1    2    3    4   ....   N-1   N
  43 //--         -----|-------------------------------------
  44 //--              |  i3   i1   i1   i1          i1
  45 //--              |       i2   i2
  46 //--              |       i3
  47 //--
  48 //--
  49 //--         On realise la meme chose pour les axes Y et Z
  50 //--
  51 //--         On obtient donc 3 tableaux (X,Y,Z) de listes d entiers (les indices des boites)
  52 //--
  53 //--       3) Pour rechercher les boites en contact avec une boite bt
  54 //--             a) On cherche les voxels touches par bt -> i0bt,i1bt ... k0bt,k1bt
  55 //--             b) On cherche dans la liste Z les boites presentes dans les cases Z[k0bt ... k1bt]
  56 //--             c) On cherche parmi ces boites celles presentes dans les cases Y[j0bt ... j1bt]
  57 //--             d) et le resultat est l intersection du result. precedent avec X[i0bt ... i1bt]
  58 //--
  59 //--
  60 //--  Rejection de plus haut niveau.
  61 //--
  62 //--       *) On garde une representation a l aide d un tableau de bit des voxels de l espace BE
  63 //--          qui contiennenrt au moins une boite Bi.
  64 //--       *) Lorsque on teste une boite bt, on regarde tout d abord si cette boite comprend dans
  65 //--          le tableau de bit au moins un voxel occuppe.
  66 //--          Si un voxel occuppe est touche : pas de rejection
  67 //--          Sinon return
  68 //--
  69 //--      **) Une autre rejection a ete adoptee. Elle consiste a ne pas checher a placer dans les
  70 //--          structures ci-dessus (tableaux X,Y,Z et tableau de Bits) une boite Bi qui est grande
  71 //--          devant la boite englobante BE.
  72 //--
  73 //--          Les indices de ces boites sont placees dans un tableau ToTest, et on comparera
  74 //--          systematiquement ces boites avec bt.
  75 //--
  76 //--
  77 //--
  78 //--
  79 //--   Note : des tableaux C remplacent ici avantageusement les HArray1OfListOfInteger et autres
  80 //--          structures agreables lorsqu il faut ajouter des donnees mais lentes a la lecture.
  81 //--
  82 //--          Ici, on ajoute les donnees au debut (ds les fcts Initialize et SortBoxes) et ensuite,
  83 //--          on passe beaucoup de temps a parcourir les tableaux. Des structures lentes a l ecriture
  84 //--          mais rapides a la lecture sont donc meilleures.
  85 //--
  86 //--
  87 //--
  88 //--
  89 //--
  90
  91
  92
  93
  94 //=======================================================================
  95 #define VERIFICATION 0
  96 #define DEBUG 0
  97 #define DIMAXIS 20
  98
  99 #if DEBUG
 100 static long unsigned   APPELREJECTION=0L;
 101 static long unsigned   REJECTNIV0=0L;
 102 static long unsigned   REJECTNIV1=0L;
 103 static long unsigned   NBCOMPARE=0L;
 104 static long unsigned   NBBOITES=0L;
 105 static long unsigned   NBBOITESATESTER=0L;
 106 #endif
 107 //=======================================================================
 108 static Standard_Integer  ComputeSize(const Standard_Integer n) {
 109   if(n>40000) return(128);
 110   if(n>10000)  return(64);
 111   if(n>1000)   return(32);
 112   if(n>100)    return(16);
 113   return(8);
 114 }
 115 //=======================================================================
 116 static long unsigned _P2[32] = { 1,2,4,8,  16,32,64,128,  256,512,1024,2048,
 117                                  4096,8192,16384,32768,
 118                                  65536,131072,262144,524288,
 119                                  1048576,2097152,4194304,8388608,
 120                                  16777216,33554432,67108864,134217728,
 121                                  268435456,536870912,1073741824,2147483648U};
 122 class BSB_T3Bits { //-- size est une puissance de 2 > 4
 123 public:
 124
 125   Standard_Integer _DECAL;
 126   Standard_Integer _DECAL2;
 127   Standard_Integer _BASE;
 128   Standard_Integer _BASEM1;
 129
 130   long unsigned ind;
 131   long unsigned Isize;
 132   Standard_Integer ssize;
 133   Standard_Real Xmin,Xmax,Ymin,Ymax,Zmin,Zmax;
 134
 135   long unsigned *p;
 136   Standard_Integer **axisX;
 137   Standard_Integer **axisY;
 138   Standard_Integer **axisZ;
 139
 140   Standard_Integer *ToTest;
 141
 142 public:
 143   BSB_T3Bits(int size);
 144   ~BSB_T3Bits();
 145
 146   //-- Partie HArray1OfListOfInteger
 147
 148   void AppendAxisX(const Standard_Integer i,const Standard_Integer v);
 149   void AppendAxisY(const Standard_Integer i,const Standard_Integer v);
 150   void AppendAxisZ(const Standard_Integer i,const Standard_Integer v);
 151
 152   void Add(long unsigned t) { int o=t&31;    int k=t>>5;    p[k]|=_P2[o];          }
 153   int Val(long unsigned t)  { int o=t&31;    int k=t>>5;    return(p[k]&_P2[o]);   }
 154   void Raz(long unsigned t) { int o=t&31;    int k=t>>5;    p[k]&= ~(_P2[o]);      }
 155
 156   Standard_Integer NbAxisX(const Standard_Integer i) {   return(axisX[0][i]);   }
 157   Standard_Integer NbAxisY(const Standard_Integer i) {   return(axisY[0][i]);   }
 158   Standard_Integer NbAxisZ(const Standard_Integer i) {   return(axisZ[0][i]);   }
 159
 160   inline Standard_Integer GrilleInteger(Standard_Integer ix,
 161                                         Standard_Integer iy,
 162                                         Standard_Integer iz) {
 163     Standard_Integer tz = iz<<_DECAL2;
 164     Standard_Integer ty = iy<<_DECAL;
 165     Standard_Integer t  = ix;
 166     t|=ty; t|=tz;
 167     return(t);
 168   }
 169
 170   inline void IntegerGrille(Standard_Integer t,
 171                             Standard_Integer &ix,
 172                             Standard_Integer &iy,
 173                             Standard_Integer &iz) {
 174     ix = t & _BASEM1; t>>=_DECAL;
 175     iy = t & _BASEM1; t>>=_DECAL;
 176     iz = t;
 177   }
 178 };
 179 //=======================================================================
 180 BSB_T3Bits::~BSB_T3Bits() {
 181   if(p) { delete [] p; p=0; }
 182 #if DEBUG
 183   printf("\n BASE:%d\n",_BASE);
 184 #endif
 185   for(Standard_Integer i=0; i<=ssize; i++) {
 186     if(axisX[i]) { delete [] axisX[i]; axisX[i]=0; }
 187     if(axisY[i]) { delete [] axisY[i]; axisY[i]=0; }
 188     if(axisZ[i]) { delete [] axisZ[i]; axisZ[i]=0; }
 189   }
 190   free(axisX); axisX=0;
 191   free(axisY); axisY=0;
 192   free(axisZ); axisZ=0;
 193   if(ToTest)  { delete [] ToTest; ToTest=0; }
 194 }
 195 //=======================================================================
 196 BSB_T3Bits::BSB_T3Bits(int size) {
 197   switch (size) {
 198   case 128: {  _DECAL=7;   _DECAL2=14;   _BASE=128;  _BASEM1=127;  break; }
 199   case  64: {  _DECAL=6;   _DECAL2=12;   _BASE= 64;  _BASEM1= 63;  break; }
 200   case  32: {  _DECAL=5;   _DECAL2=10;   _BASE= 32;  _BASEM1= 31;  break; }
 201   case  16: {  _DECAL=4;   _DECAL2= 8;   _BASE= 16;  _BASEM1= 15;  break; }
 202   default : {  _DECAL=3;   _DECAL2= 6;   _BASE=  8;  _BASEM1=  7;  break; }
 203   }
 204   Standard_Integer i ;
 205   long unsigned nb = (size*size*size)>>5;
 206   Isize = nb;
 207   ssize = size;
 208   p = new long unsigned [nb];
 209   do { p[--nb]=0; } while(nb);
 210
 211   axisX = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 212   axisY = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 213   axisZ = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 214
 215   axisX[0]=new Standard_Integer [_BASE+1];
 216   axisY[0]=new Standard_Integer [_BASE+1];
 217   axisZ[0]=new Standard_Integer [_BASE+1];
 218
 219   for( i=0; i<(_BASE+1); i++) {
 220     axisX[0][i]=0;
 221     axisY[0][i]=0;
 222     axisZ[0][i]=0;
 223   }
 224
 225   for(i=1; i<=size; i++) {
 226     axisX[i] =  new Standard_Integer[DIMAXIS];
 227     axisY[i] =  new Standard_Integer[DIMAXIS];
 228     axisZ[i] =  new Standard_Integer[DIMAXIS];
 229     axisX[i][0]=DIMAXIS;
 230     axisY[i][0]=DIMAXIS;
 231     axisZ[i][0]=DIMAXIS;
 232     axisX[i][1]=axisY[i][1]=axisZ[i][1]=-1;
 233   }
 234   ToTest=0;
 235 }
 236 //=======================================================================
 237 void BSB_T3Bits::AppendAxisZ(const Standard_Integer i,
 238                              const Standard_Integer v) {
 239   Standard_Integer n = axisZ[0][i];
 240   n++;
 241   if(n<axisZ[i][0]) { axisZ[i][n]=v; }
 242   else {
 243     Standard_Integer s=axisZ[i][0];
 244     Standard_Integer *nt = new Standard_Integer [s+s];
 245     nt[0]=s+s;
 246     for(Standard_Integer j=1;j<s;j++) {
 247       nt[j]=axisZ[i][j];
 248     }
 249     nt[n]=v;
 250     delete [] axisZ[i];
 251     axisZ[i]=nt;
 252   }
 253   axisZ[0][i]=n;
 254 }
 255 //=======================================================================
 256 void BSB_T3Bits::AppendAxisY(const Standard_Integer i,
 257                              const Standard_Integer v) {
 258   Standard_Integer n = axisY[0][i];
 259   n++;
 260   if(n<axisY[i][0]) { axisY[i][n]=v;   }
 261   else {
 262     Standard_Integer s=axisY[i][0];
 263     Standard_Integer *nt = new Standard_Integer [s+s];
 264     nt[0]=s+s;
 265     for(Standard_Integer j=1;j<s;j++) {
 266       nt[j]=axisY[i][j];
 267     }
 268     nt[n]=v;
 269     delete [] axisY[i];
 270     axisY[i]=nt;
 271   }
 272   axisY[0][i]=n;
 273 }
 274 //=======================================================================
 275 void BSB_T3Bits::AppendAxisX(const Standard_Integer i,
 276                              const Standard_Integer v) {
 277   Standard_Integer n = axisX[0][i];
 278
 279   n++;
 280   if(n<axisX[i][0]) {   axisX[i][n]=v;   }
 281   else {
 282     //-- il faut etendre
 283     Standard_Integer s=axisX[i][0];
 284     Standard_Integer *nt = new Standard_Integer [s+s];
 285     nt[0]=s+s;
 286     for(Standard_Integer j=1;j<s;j++) {
 287       nt[j]=axisX[i][j];
 288     }
 289     nt[n]=v;
 290     delete [] axisX[i];
 291     axisX[i]=nt;
 292   }
 293   axisX[0][i]=n;
 294 }
 295 //=======================================================================
 296 //=======================================================================
 297 //function : Bnd_BoundSortBox
 298 //purpose  :
 299 //=======================================================================
 300 Bnd_BoundSortBox::Bnd_BoundSortBox()
 301      : discrX(0), discrY(0), discrZ(0)
 302 {
 303   TabBits=0;
 304 #if DEBUG
 305   NBCOMPARE=0L;   NBBOITES=0L;   NBBOITESATESTER=0L;
 306   APPELREJECTION=0L;  REJECTNIV0=0L;  REJECTNIV1=0L;
 307 #endif
 308 }
 309 //=======================================================================
 310 //function : Initialize
 311 //purpose  :
 312 //=======================================================================
 313
 314 void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
 315                                   const Handle(Bnd_HArray1OfBox)& SetOfBox)
 316 {
 317   myBox=CompleteBox;
 318   myBndComponents=SetOfBox;
 319   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 320   discrX=discrY=discrZ=ComputeSize(taBox.Upper()-taBox.Lower());
 321   Standard_Real Xmax, Ymax, Zmax;
 322   if(CompleteBox.IsVoid())
 323     return;
 324   CompleteBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 325   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 326   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 327   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 328   SortBoxes();
 329 }
 330 //=======================================================================
 331 //function : Initialize
 332 //purpose  :
 333 //=======================================================================
 334 void Bnd_BoundSortBox::Initialize(const Handle(Bnd_HArray1OfBox)& SetOfBox)
 335 {
 336   myBndComponents=SetOfBox;
 337   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 338   Standard_Integer i0,i1;
 339   i0=taBox.Lower();
 340   i1=taBox.Upper();
 341   discrX=discrY=discrZ=ComputeSize(i1-i0);
 342   Standard_Integer labox;
 343   for (labox=i0; labox<=i1; labox++) {
 344     if (!taBox(labox).IsVoid()) {
 345       myBox.Add(taBox(labox));
 346     }
 347   }
 348   Standard_Real Xmax, Ymax, Zmax;
 349   if(myBox.IsVoid())
 350     return;
 351   myBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 352   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 353   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 354   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 355   SortBoxes();
 356 }
 357 //=======================================================================
 358 //function : SortBoxes
 359 //purpose  :
 360 //=======================================================================
 361 void Bnd_BoundSortBox::SortBoxes()
 362 {
 363   Standard_Integer labox;
 364   Standard_Integer lacaseX, firstcaseX, lastcaseX;
 365   Standard_Integer lacaseY, firstcaseY, lastcaseY;
 366   Standard_Integer lacaseZ, firstcaseZ, lastcaseZ;
 367   Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 368   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 369   Standard_Integer i0=taBox.Lower();
 370   Standard_Integer i1=taBox.Upper();
 371   BSB_T3Bits* Map=0;
 372   if(TabBits) {
 373     BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
 374     delete _Map;
 375   }
 376   Map = new BSB_T3Bits(discrX);
 377   TabBits = (void *)Map;
 378   if(Map->ToTest==0) {
 379     Standard_Integer s=i1-i0;
 380     if(s<2) s=2;
 381     Map->ToTest = new Standard_Integer [s];
 382     for(Standard_Integer i=0; i<s; i++) {
 383       Map->ToTest[i]=i0-1;
 384     }
 385   }
 386   Standard_Real _Xmax,_Xmin,_Ymax,_Ymin,_Zmin,_Zmax;
 387   myBox.Get(_Xmin,_Ymin,_Zmin,_Xmax,_Ymax,_Zmax);
 388   Map->Xmax=_Xmax; Map->Ymax=_Ymax; Map->Zmax=_Zmax;
 389   Map->Xmin=_Xmin; Map->Ymin=_Ymin; Map->Zmin=_Zmin;
 390   for (labox=i0; labox<=i1; labox++) {
 391     if (!taBox(labox).IsVoid()) {
 392       taBox(labox).Get(xmin, ymin, zmin, xmax, ymax, zmax);
 393       if(xmin>Xmin) firstcaseX=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  firstcaseX=1;
 394       if(ymin>Ymin) firstcaseY=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  firstcaseY=1;
 395       if(zmin>Zmin) firstcaseZ=(Standard_Integer )((zmin-Zmin)*deltaZ)-1; else  firstcaseZ=1;
 396       if(xmax<_Xmax) lastcaseX=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  lastcaseX=discrX;
 397       if(ymax<_Ymax) lastcaseY=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  lastcaseY=discrY;
 398       if(zmax<_Zmax) lastcaseZ=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  lastcaseZ=discrZ;
 399       if(firstcaseX<1) firstcaseX=1; else if(firstcaseX>discrX) firstcaseX=discrX;
 400       if(firstcaseY<1) firstcaseY=1; else if(firstcaseY>discrY) firstcaseY=discrY;
 401       if(firstcaseZ<1) firstcaseZ=1; else if(firstcaseZ>discrZ) firstcaseZ=discrZ;
 402
 403       if(lastcaseX<1) lastcaseX=1; else if(lastcaseX>discrX) lastcaseX=discrX;
 404       if(lastcaseY<1) lastcaseY=1; else if(lastcaseY>discrY) lastcaseY=discrY;
 405       if(lastcaseZ<1) lastcaseZ=1; else if(lastcaseZ>discrZ) lastcaseZ=discrZ;
 406
 407       Standard_Integer n = (lastcaseX-firstcaseX);
 408       if(n>(lastcaseY-firstcaseY)) n=lastcaseY-firstcaseY;
 409       if(n>(lastcaseZ-firstcaseZ)) n=lastcaseZ-firstcaseZ;
 410 #if DEBUG
 411       NBBOITES++;
 412 #endif
 413       n<<=2;
 414       if(n>discrX) {
 415 #if DEBUG
 416       NBBOITESATESTER++;
 417 #endif
 418         for(Standard_Integer i=0; i<(i1-i0); i++) {
 419           if(Map->ToTest[i]<i0) {
 420             Map->ToTest[i]=labox;
 421             break;
 422           }
 423         }
 424       }
 425       else {
 426         for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
 427           Map->AppendAxisX(lacaseX,labox);
 428         }
 429         for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
 430           Map->AppendAxisY(lacaseY,labox);
 431         }
 432         for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
 433           Map->AppendAxisZ(lacaseZ,labox);
 434         }
 435         //------------------------------------------------------------
 436         //-- remplissage du tableau de bits
 437         //--
 438         if(Map) {
 439           for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
 440             for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
 441               for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
 442                 long unsigned t=Map->GrilleInteger(lacaseX-1,lacaseY-1,lacaseZ-1);
 443                 Map->Add(t);
 444               }
 445             }
 446           }
 447         }
 448       }
 449     }
 450   }
 451 }
 452 //=======================================================================
 453 //function : Initialize
 454 //purpose  :
 455 //=======================================================================
 456 void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
 457                                   const Standard_Integer nbComponents)
 458 {
 459   Standard_NullValue_Raise_if (nbComponents <=0, "BoundSortBox nul!");
 460   myBox=CompleteBox;
 461   myBndComponents=new Bnd_HArray1OfBox(1,nbComponents);
 462
 463   //***>>> JCD - 04.08.2000 - Array initialization is missing...
 464   Bnd_Box emptyBox;
 465   myBndComponents->Init( emptyBox );
 466   //***<<< JCD - End
 467
 468   discrX=discrY=discrZ=ComputeSize(nbComponents);
 469   Standard_Real Xmax, Ymax, Zmax;
 470
 471   if(CompleteBox.IsVoid())
 472     return;
 473   CompleteBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 474   myBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 475   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 476   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 477   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 478   if(TabBits) {
 479     BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
 480     delete _Map;
 481     TabBits=0;
 482   }
 483   BSB_T3Bits* Map=0;
 484   Map = new BSB_T3Bits(discrX);
 485   TabBits = (void *)Map;
 486 }
 487 //=======================================================================
 488 //function : Add
 489 //purpose  :
 490 //=======================================================================
 491 void Bnd_BoundSortBox::Add(const Bnd_Box& theBox,
 492                            const Standard_Integer boxIndex)
 493 {
 494   Standard_MultiplyDefined_Raise_if (!(myBndComponents->Value(boxIndex).IsVoid()), " This box is already defined !");
 495   if (!theBox.IsVoid()) {
 496     Standard_Integer i0=myBndComponents->Lower();
 497     Standard_Integer i1=myBndComponents->Upper();
 498     Standard_Integer theGapX, firstGapX , lastGapX;
 499     Standard_Integer theGapY, firstGapY , lastGapY;
 500     Standard_Integer theGapZ, firstGapZ , lastGapZ;
 501     Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 502     myBndComponents->SetValue(boxIndex, theBox);
 503     theBox.Get(xmin, ymin, zmin, xmax, ymax, zmax);
 504     BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 505     if(Map->ToTest==0) {
 506       Standard_Integer s=i1-i0;
 507       if(s<2) s=2;
 508       Map->ToTest = new Standard_Integer [s];
 509       for(Standard_Integer i=0; i<s; i++) {
 510         Map->ToTest[i]=i0-1;
 511       }
 512     }
 513     Standard_Real _Xmax,_Ymax,_Zmax;
 514     _Xmax=Map->Xmax; _Ymax=Map->Ymax; _Zmax=Map->Zmax;
 515     if(xmin>Xmin) firstGapX=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  firstGapX=1;
 516     if(ymin>Ymin) firstGapY=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  firstGapY=1;
 517     if(zmin>Zmin) firstGapZ=(Standard_Integer ) ((zmin-Zmin)*deltaZ)-1; else  firstGapZ=1;
 518     if(xmax<_Xmax) lastGapX=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  lastGapX=discrX;
 519     if(ymax<_Ymax) lastGapY=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  lastGapY=discrY;
 520     if(zmax<_Zmax) lastGapZ=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  lastGapZ=discrZ;
 521     if(firstGapX<1) firstGapX=1; else if(firstGapX>discrX) firstGapX=discrX;
 522     if(firstGapY<1) firstGapY=1; else if(firstGapY>discrY) firstGapY=discrY;
 523     if(firstGapZ<1) firstGapZ=1; else if(firstGapZ>discrZ) firstGapZ=discrZ;
 524
 525     if(lastGapX<1) lastGapX=1; else if(lastGapX>discrX) lastGapX=discrX;
 526     if(lastGapY<1) lastGapY=1; else if(lastGapY>discrY) lastGapY=discrY;
 527     if(lastGapZ<1) lastGapZ=1; else if(lastGapZ>discrZ) lastGapZ=discrZ;
 528     Standard_Integer n = (lastGapX-firstGapX);
 529     if(n>(lastGapY-firstGapY)) n=lastGapY-firstGapY;
 530     if(n>(lastGapZ-firstGapZ)) n=lastGapZ-firstGapZ;
 531     n<<=2;
 532 #if DEBUG
 533       NBBOITES++;
 534 #endif
 535     if(n>discrX) {
 536 #if DEBUG
 537       NBBOITESATESTER++;
 538 #endif
 539       for(Standard_Integer i=0; i<(i1-i0); i++) {
 540         if(Map->ToTest[i]<i0) {
 541           Map->ToTest[i]=boxIndex;
 542           break;
 543         }
 544       }
 545     }
 546     for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
 547       Map->AppendAxisY(theGapY,boxIndex);
 548     }
 549     for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
 550       Map->AppendAxisX(theGapX,boxIndex);
 551     }
 552     for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
 553       Map->AppendAxisZ(theGapZ,boxIndex);
 554     }
 555     //------------------------------------------------------------
 556     //-- remplissage du tableau de bits
 557     //--
 558     if(TabBits) {
 559       Map=(BSB_T3Bits *)TabBits;
 560       for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
 561         for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
 562           for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
 563             long unsigned t=Map->GrilleInteger(theGapX-1,theGapY-1,theGapZ-1);
 564             Map->Add(t);
 565           }
 566         }
 567       }
 568     }
 569   }
 570 }
 571 //=======================================================================
 572 #if VERIFICATION
 573 static void VerifCompare(const TColStd_ListOfInteger& lastResult,
 574                          const Bnd_Box& theBox,
 575                          const Bnd_Array1OfBox&  taBox) {
 576   static int Verif = 1;
 577   Standard_Integer i ;
 578
 579   if(Verif) {
 580     Standard_Integer i0,i1;
 581     i0=taBox.Lower();
 582     i1=taBox.Upper();
 583     char * qwe=new char [i1+1];  //-- $$$$$$$ ATTENTION SI I0 < 0
 584     for( i=i0; i<=i1; i++) qwe[i]='\0';
 585     TColStd_ListIteratorOfListOfInteger  theList(lastResult);
 586     for (; theList.More(); theList.Next()) {
 587       qwe[theList.Value()]=(char)1;
 588     }
 589     Standard_Integer labox;
 590     for (labox=i0; labox<=i1; labox++) {
 591       if (!taBox(labox).IsOut(theBox)) {
 592         qwe[labox]+=2;
 593       }
 594     }
 595     for(i=i0;i<=i1;i++) {
 596       if(qwe[i]==2) {
 597         printf("\nPb avec boite: %d ",i);
 598       }
 599       else if(qwe[i]==1) {
 600         printf("\n fausse rejection en %d \n",i);
 601       }
 602     }
 603     delete [] qwe;
 604   }
 605 }
 606 #endif
 607 //=======================================================================
 608 //function : Compare
 609 //purpose  :
 610 //=======================================================================
 611 const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare (const Bnd_Box& theBox)
 612
 613 {
 614  Standard_Integer lacase ;
 615 #if DEBUG
 616   NBCOMPARE++;
 617 #endif
 618   lastResult.Clear();
 619   if (theBox.IsVoid()) return lastResult;
 620   if (theBox.IsOut(myBox)) {
 621 #if DEBUG
 622     REJECTNIV0++;
 623 #endif
 624     return lastResult;
 625   }
 626   const Bnd_Array1OfBox& taBox=myBndComponents->Array1();
 627   //-- Rejection avec le tableau de bits
 628   Standard_Boolean touch = Standard_True;
 629   touch = Standard_False;
 630   Standard_Real _Xmin,_Ymin,_Zmin,_Xmax,_Ymax,_Zmax;
 631   BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 632   Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 633   _Xmax=Map->Xmax; _Ymax=Map->Ymax; _Zmax=Map->Zmax;
 634   _Xmin=Map->Xmin; _Ymin=Map->Ymin; _Zmin=Map->Zmin;
 635   theBox.Get(xmin, ymin, zmin, xmax, ymax, zmax);
 636   Standard_Integer i0,i1,j0,j1,k0,k1;
 637   if(xmin>Xmin) i0=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  i0=1;
 638   if(ymin>Ymin) j0=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  j0=1;
 639   if(zmin>Zmin) k0=(Standard_Integer )((zmin-Zmin)*deltaZ)-1; else  k0=1;
 640   if(xmax<_Xmax) i1=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  i1=discrX;
 641   if(ymax<_Ymax) j1=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  j1=discrY;
 642   if(zmax<_Zmax) k1=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  k1=discrZ;
 643   if(i0<1) i0=1; else if(i0>discrX) i0=discrX;
 644   if(j0<1) j0=1; else if(j0>discrY) j0=discrY;
 645   if(k0<1) k0=1; else if(k0>discrZ) k0=discrZ;
 646
 647   if(i1<1) i1=1; else if(i1>discrX) i1=discrX;
 648   if(j1<1) j1=1; else if(j1>discrY) j1=discrY;
 649   if(k1<1) k1=1; else if(k1>discrZ) k1=discrZ;
 650   i0--; j0--; k0--; i1--; j1--; k1--;
 651   for(Standard_Integer i=i0; touch==Standard_False && i<=i1;i++) {
 652     for(Standard_Integer j=j0; touch==Standard_False && j<=j1;j++) {
 653       for(Standard_Integer k=k0;  touch==Standard_False && k<=k1;k++) {
 654         long unsigned t=Map->GrilleInteger(i,j,k);
 655         if(Map->Val(t)) {
 656           touch = Standard_True;
 657         }
 658       }
 659     }
 660   }
 661   //-- traitement des boites a tester systematiquement
 662   if(Map->ToTest) {
 663     Standard_Integer l0 = taBox.Lower();
 664     Standard_Integer l1 = taBox.Upper();
 665     l1-=l0;
 666     for(Standard_Integer l=0; Map->ToTest[l]>=l0 && l<(l1-l0); l++) {
 667       if(Map->ToTest[l]>=l0) {
 668         if (!taBox(Map->ToTest[l]).IsOut(theBox)){
 669           lastResult.Append(Map->ToTest[l]);
 670         }
 671       }
 672     }
 673   }
 674   if(touch == Standard_False) {
 675 #if DEBUG
 676     REJECTNIV1++;
 677 #endif
 678 #if VERIFICATION
 679     VerifCompare(lastResult,theBox,taBox);
 680 #endif
 681     return(lastResult);
 682   }
 683   //-------------------------
 684   //-- traitement classique
 685   //-------------------------
 686   i0++; i1++; j0++; j1++; k0++; k1++;
 687   Crible.Clear();
 688   theFound=6;
 689   Standard_Integer cardY=0;
 690   for (lacase=j0; lacase<=j1; lacase++) {
 691     Standard_Integer nby=Map->NbAxisY(lacase);
 692     while(nby>0) {
 693       cardY++;
 694       Crible.Bind(Map->axisY[lacase][nby], 4);
 695       nby--;
 696     }
 697   }
 698   if (cardY==0) {
 699 #if VERIFICATION
 700     VerifCompare(lastResult,theBox,taBox);
 701 #endif
 702     return lastResult;
 703   }
 704   Standard_Integer cardZ=0;
 705   for (lacase=k0; lacase<=k1; lacase++) {
 706     Standard_Integer nbz=Map->NbAxisZ(lacase);
 707     while(nbz>0) {
 708       cardZ++;
 709       if (Crible.IsBound(Map->axisZ[lacase][nbz])) {
 710         Crible.Bind(Map->axisZ[lacase][nbz], 6);
 711       }
 712       nbz--;
 713     }
 714   }
 715   if (cardZ==0) {
 716 #if VERIFICATION
 717     VerifCompare(lastResult,theBox,taBox);
 718 #endif
 719     return lastResult;
 720   }
 721   for (lacase=i0; lacase<=i1; lacase++) {
 722     Standard_Integer nbx = Map->NbAxisX(lacase);
 723     while(nbx>0) {
 724       Standard_Integer x=Map->axisX[lacase][nbx];
 725       if (Crible.IsBound(x)) {
 726         if (Crible(x)==theFound) {
 727           Crible.UnBind(x);
 728           if (!taBox(x).IsOut(theBox)){
 729             lastResult.Append(x);
 730           }
 731         }
 732       }
 733       nbx--;
 734     }
 735   }
 736 #if VERIFICATION
 737   VerifCompare(lastResult,theBox,taBox);
 738 #endif
 739   return lastResult;
 740 }
 741 //=======================================================================
 742 //function : Dump
 743 //purpose  :
 744 //=======================================================================
 745
 746 void Bnd_BoundSortBox::Dump() const
 747 {}
 748 //=======================================================================
 749 //function : Compare
 750 //purpose  :
 751 //=======================================================================
 752 const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare(const gp_Pln& thePlane)
 753
 754 {
 755   lastResult.Clear();
 756   Standard_Integer i;
 757   const Bnd_Array1OfBox& boxes = myBndComponents->Array1();
 758   for (i = boxes.Lower(); i <= boxes.Upper(); i++) {
 759     if (!boxes(i).IsOut(thePlane))
 760       lastResult.Append(i);
 761   }
 762   return lastResult;
 763 }
 764 //=======================================================================
 765 void Bnd_BoundSortBox::Destroy() {
 766 #if DEBUG
 767   printf("\nDESTROY NBCOMPARE:%lu  REJECTNIV0:%lu  REJECTIONSOK=%lu  NBBOITES:%lu NBBOITESATESTER:%lu\n",
 768          NBCOMPARE,REJECTNIV0,REJECTNIV1,NBBOITES,NBBOITESATESTER);
 769 #endif
 770   BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 771   if(Map) {
 772     delete Map;
 773     Map=0;
 774   }
 775 }
 776 //=======================================================================
 777