src/Bnd/Bnd_BoundSortBox.cxx

   1 // Created on: 1992-11-24
   2 // Created by: Didier PIFFAULT
   3 // Copyright (c) 1992-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <Bnd_BoundSortBox.ixx>
  18 #include <Standard_NullValue.hxx>
  19 #include <Standard_MultiplyDefined.hxx>
  20 #include <Bnd_Array1OfBox.hxx>
  21 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  22 #include <TColStd_DataMapIteratorOfDataMapOfIntegerInteger.hxx>
  23
  24 //#if defined(WNT) || defined(LIN)
  25 # include <stdio.h>
  26 //#endif  // WNT
  27
  28 //-- ================================================================================
  29 //--  lbr le 27 fev 97
  30 //--
  31 //--
  32 //--      Initialisation:  Bounding box BE
  33 //--                       List of boxes Bi (Bi in BE)
  34 //--
  35 //--      Compare(b) returns the list of Boxes Bi touched by b
  36 //--
  37 //--
  38 //--      General principle:
  39 //--
  40 //--       1) Discretize box BE into N*N*N voxels
  41 //--          Each box Bi touches a certain number of voxels
  42 //--          Bi touches { Vijk with i0<=i<=i1 ...  k0<=k<=k1 }
  43 //--       2) Project on each axis X,Y,Z boxes Bi
  44 //--          to get the following structures :
  45 //--
  46 //--          Example :
  47 //--
  48 //--             box i1 touches voxels { Vijk  with 1<=i<=N-1  ... }
  49 //--             box i2 touches voxels { Vijk  with 2<=i<=3  ... }
  50 //--             box i3 touches voxels { Vijk  with 1<=i<=2  ... }
  51 //--
  52 //--
  53 //--         X[.] |  1    2    3    4   ....   N-1   N
  54 //--         -----|-------------------------------------
  55 //--              |  i3   i1   i1   i1          i1
  56 //--              |       i2   i2
  57 //--              |       i3
  58 //--
  59 //--
  60 //--         Produce the same thing for axes Y and Z
  61 //--
  62 //--         Obtain 3 tables (X,Y,Z) of lists of integers (indexes of boxes)
  63 //--
  64 //--       3) To find boxes contacting with box bt
  65 //--             a) Find voxels touched by bt -> i0bt,i1bt ... k0bt,k1bt
  66 //--             b) Find in list Z the boxes present in cases Z[k0bt ... k1bt]
  67 //--             c) Find among these boxes the ones present in cases Y[j0bt ... j1bt]
  68 //--             d) and the result is the intersection of the previous result with X[i0bt ... i1bt]
  69 //--
  70 //--
  71 //--  Rejection of a higher level.
  72 //--
  73 //--       *) Preserve a table representation of bit of voxels of space BE
  74 //--          that contains at least one box Bi.
  75 //--       *) While box bt is texted, it is checked if this box includes in
  76 //--          the table of bit at least one occupied voxel.
  77 //--          If the occupied voxel is touched : no rejection
  78 //--          Otherwise return
  79 //--
  80 //--      **) Another rejection was adopted. It consists in trying to locate in
  81 //--          the above structures (tables X,Y,Z and  table of Bits) a box Bi which is greater than the
  82 //--          bounding box BE.
  83 //--
  84 //--          The indices of these boxes are located in table ToTest, and these
  85 //            boxes are compared systematically with bt.
  86 //--
  87 //--   Note : tables C replace here HArray1OfListOfInteger and other
  88 //--          structures that are sufficient for data adding but slow for reading.
  89 //--
  90 //--          Here the data is added at start (Initialize and SortBoxes) and later,
  91 //--          it takes much time to parse the tables. The slowly written, byut fastly read structures
  92 //--          are thus better.
  93 //--
  94
  95
  96
  97
  98 //=======================================================================
  99 #define VERIFICATION 0
 100 #define DEBUG 0
 101 #define DIMAXIS 20
 102
 103 #if DEBUG
 104 static long unsigned   APPELREJECTION=0L;
 105 static long unsigned   REJECTNIV0=0L;
 106 static long unsigned   REJECTNIV1=0L;
 107 static long unsigned   NBCOMPARE=0L;
 108 static long unsigned   NBBOITES=0L;
 109 static long unsigned   NBBOITESATESTER=0L;
 110 #endif
 111 //=======================================================================
 112 static Standard_Integer  ComputeSize(const Standard_Integer n) {
 113   if(n>40000) return(128);
 114   if(n>10000)  return(64);
 115   if(n>1000)   return(32);
 116   if(n>100)    return(16);
 117   return(8);
 118 }
 119 //=======================================================================
 120 static long unsigned _P2[32] = { 1,2,4,8,  16,32,64,128,  256,512,1024,2048,
 121                                  4096,8192,16384,32768,
 122                                  65536,131072,262144,524288,
 123                                  1048576,2097152,4194304,8388608,
 124                                  16777216,33554432,67108864,134217728,
 125                                  268435456,536870912,1073741824,2147483648U};
 126
 127 //-- size is power of 2 > 4
 128 class BSB_T3Bits
 129 {
 130 public:
 131
 132   Standard_Integer _DECAL;
 133   Standard_Integer _DECAL2;
 134   Standard_Integer _BASE;
 135   Standard_Integer _BASEM1;
 136
 137   long unsigned ind;
 138   long unsigned Isize;
 139   Standard_Integer ssize;
 140   Standard_Real Xmin,Xmax,Ymin,Ymax,Zmin,Zmax;
 141
 142   long unsigned *p;
 143   Standard_Integer **axisX;
 144   Standard_Integer **axisY;
 145   Standard_Integer **axisZ;
 146
 147   Standard_Integer *ToTest;
 148
 149 public:
 150   BSB_T3Bits(int size);
 151   ~BSB_T3Bits();
 152
 153   //-- Part HArray1OfListOfInteger
 154
 155   void AppendAxisX(const Standard_Integer i,const Standard_Integer v);
 156   void AppendAxisY(const Standard_Integer i,const Standard_Integer v);
 157   void AppendAxisZ(const Standard_Integer i,const Standard_Integer v);
 158
 159   void Add(long unsigned t) { int o=t&31;    int k=t>>5;    p[k]|=_P2[o];          }
 160   int Val(long unsigned t)  { int o=t&31;    int k=t>>5;    return(p[k]&_P2[o]);   }
 161   void Raz(long unsigned t) { int o=t&31;    int k=t>>5;    p[k]&= ~(_P2[o]);      }
 162
 163   Standard_Integer NbAxisX(const Standard_Integer i) {   return(axisX[0][i]);   }
 164   Standard_Integer NbAxisY(const Standard_Integer i) {   return(axisY[0][i]);   }
 165   Standard_Integer NbAxisZ(const Standard_Integer i) {   return(axisZ[0][i]);   }
 166
 167   inline Standard_Integer GrilleInteger(Standard_Integer ix,
 168                                         Standard_Integer iy,
 169                                         Standard_Integer iz)
 170   {
 171     Standard_Integer tz = iz<<_DECAL2;
 172     Standard_Integer ty = iy<<_DECAL;
 173     Standard_Integer t  = ix;
 174     t|=ty;
 175     t|=tz;
 176     return(t);
 177   }
 178
 179   inline void IntegerGrille(Standard_Integer t,
 180                             Standard_Integer &ix,
 181                             Standard_Integer &iy,
 182                             Standard_Integer &iz)
 183   {
 184     ix = t & _BASEM1; t>>=_DECAL;
 185     iy = t & _BASEM1; t>>=_DECAL;
 186     iz = t;
 187   }
 188
 189 private:
 190
 191   BSB_T3Bits (const BSB_T3Bits&);
 192   BSB_T3Bits& operator= (const BSB_T3Bits&);
 193 };
 194
 195 //=======================================================================
 196 BSB_T3Bits::~BSB_T3Bits()
 197 {
 198   if(p) { delete [] p; p=0; }
 199 #if DEBUG
 200   printf("\n BASE:%d\n",_BASE);
 201 #endif
 202   for(Standard_Integer i=0; i<=ssize; i++) {
 203     if(axisX[i]) { delete [] axisX[i]; axisX[i]=0; }
 204     if(axisY[i]) { delete [] axisY[i]; axisY[i]=0; }
 205     if(axisZ[i]) { delete [] axisZ[i]; axisZ[i]=0; }
 206   }
 207   free(axisX); axisX=0;
 208   free(axisY); axisY=0;
 209   free(axisZ); axisZ=0;
 210   if(ToTest)  { delete [] ToTest; ToTest=0; }
 211 }
 212 //=======================================================================
 213 BSB_T3Bits::BSB_T3Bits(int size)
 214         : ind(0),
 215     Xmin(0),Xmax(0),
 216         Ymin(0),Ymax(0),
 217         Zmin(0),Zmax(0)
 218 {
 219   switch (size) {
 220   case 128: {  _DECAL=7;   _DECAL2=14;   _BASE=128;  _BASEM1=127;  break; }
 221   case  64: {  _DECAL=6;   _DECAL2=12;   _BASE= 64;  _BASEM1= 63;  break; }
 222   case  32: {  _DECAL=5;   _DECAL2=10;   _BASE= 32;  _BASEM1= 31;  break; }
 223   case  16: {  _DECAL=4;   _DECAL2= 8;   _BASE= 16;  _BASEM1= 15;  break; }
 224   default : {  _DECAL=3;   _DECAL2= 6;   _BASE=  8;  _BASEM1=  7;  break; }
 225   }
 226   Standard_Integer i ;
 227   long unsigned nb = (size*size*size)>>5;
 228   Isize = nb;
 229   ssize = size;
 230   p = new long unsigned [nb];
 231   do { p[--nb]=0; } while(nb);
 232
 233   axisX = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 234   axisY = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 235   axisZ = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 236
 237   axisX[0]=new Standard_Integer [_BASE+1];
 238   axisY[0]=new Standard_Integer [_BASE+1];
 239   axisZ[0]=new Standard_Integer [_BASE+1];
 240
 241   for( i=0; i<(_BASE+1); i++) {
 242     axisX[0][i]=0;
 243     axisY[0][i]=0;
 244     axisZ[0][i]=0;
 245   }
 246
 247   for(i=1; i<=size; i++) {
 248     axisX[i] =  new Standard_Integer[DIMAXIS];
 249     axisY[i] =  new Standard_Integer[DIMAXIS];
 250     axisZ[i] =  new Standard_Integer[DIMAXIS];
 251     axisX[i][0]=DIMAXIS;
 252     axisY[i][0]=DIMAXIS;
 253     axisZ[i][0]=DIMAXIS;
 254     axisX[i][1]=axisY[i][1]=axisZ[i][1]=-1;
 255   }
 256   ToTest=0;
 257 }
 258 //=======================================================================
 259 void BSB_T3Bits::AppendAxisZ(const Standard_Integer i,
 260                              const Standard_Integer v) {
 261   Standard_Integer n = axisZ[0][i];
 262   n++;
 263   if(n<axisZ[i][0]) { axisZ[i][n]=v; }
 264   else {
 265     Standard_Integer s=axisZ[i][0];
 266     Standard_Integer *nt = new Standard_Integer [s+s];
 267     nt[0]=s+s;
 268     for(Standard_Integer j=1;j<s;j++) {
 269       nt[j]=axisZ[i][j];
 270     }
 271     nt[n]=v;
 272     delete [] axisZ[i];
 273     axisZ[i]=nt;
 274   }
 275   axisZ[0][i]=n;
 276 }
 277 //=======================================================================
 278 void BSB_T3Bits::AppendAxisY(const Standard_Integer i,
 279                              const Standard_Integer v) {
 280   Standard_Integer n = axisY[0][i];
 281   n++;
 282   if(n<axisY[i][0]) { axisY[i][n]=v;   }
 283   else {
 284     Standard_Integer s=axisY[i][0];
 285     Standard_Integer *nt = new Standard_Integer [s+s];
 286     nt[0]=s+s;
 287     for(Standard_Integer j=1;j<s;j++) {
 288       nt[j]=axisY[i][j];
 289     }
 290     nt[n]=v;
 291     delete [] axisY[i];
 292     axisY[i]=nt;
 293   }
 294   axisY[0][i]=n;
 295 }
 296 //=======================================================================
 297 void BSB_T3Bits::AppendAxisX(const Standard_Integer i,
 298                              const Standard_Integer v) {
 299   Standard_Integer n = axisX[0][i];
 300
 301   n++;
 302   if(n<axisX[i][0]) {   axisX[i][n]=v;   }
 303   else {
 304     //-- it is required to extend
 305     Standard_Integer s=axisX[i][0];
 306     Standard_Integer *nt = new Standard_Integer [s+s];
 307     nt[0]=s+s;
 308     for(Standard_Integer j=1;j<s;j++) {
 309       nt[j]=axisX[i][j];
 310     }
 311     nt[n]=v;
 312     delete [] axisX[i];
 313     axisX[i]=nt;
 314   }
 315   axisX[0][i]=n;
 316 }
 317 //=======================================================================
 318 //=======================================================================
 319 //function : Bnd_BoundSortBox
 320 //purpose  :
 321 //=======================================================================
 322 Bnd_BoundSortBox::Bnd_BoundSortBox()
 323      : discrX(0), discrY(0), discrZ(0)
 324 {
 325   TabBits=0;
 326 #if DEBUG
 327   NBCOMPARE=0L;   NBBOITES=0L;   NBBOITESATESTER=0L;
 328   APPELREJECTION=0L;  REJECTNIV0=0L;  REJECTNIV1=0L;
 329 #endif
 330 }
 331 //=======================================================================
 332 //function : Initialize
 333 //purpose  :
 334 //=======================================================================
 335
 336 void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
 337                                   const Handle(Bnd_HArray1OfBox)& SetOfBox)
 338 {
 339   myBox=CompleteBox;
 340   myBndComponents=SetOfBox;
 341   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 342   discrX=discrY=discrZ=ComputeSize(taBox.Upper()-taBox.Lower());
 343   Standard_Real Xmax, Ymax, Zmax;
 344   if(CompleteBox.IsVoid())
 345     return;
 346   CompleteBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 347   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 348   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 349   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 350   SortBoxes();
 351 }
 352 //=======================================================================
 353 //function : Initialize
 354 //purpose  :
 355 //=======================================================================
 356 void Bnd_BoundSortBox::Initialize(const Handle(Bnd_HArray1OfBox)& SetOfBox)
 357 {
 358   myBndComponents=SetOfBox;
 359   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 360   Standard_Integer i0,i1;
 361   i0=taBox.Lower();
 362   i1=taBox.Upper();
 363   discrX=discrY=discrZ=ComputeSize(i1-i0);
 364   Standard_Integer labox;
 365   for (labox=i0; labox<=i1; labox++) {
 366     if (!taBox(labox).IsVoid()) {
 367       myBox.Add(taBox(labox));
 368     }
 369   }
 370   Standard_Real Xmax, Ymax, Zmax;
 371   if(myBox.IsVoid())
 372     return;
 373   myBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 374   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 375   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 376   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 377   SortBoxes();
 378 }
 379 //=======================================================================
 380 //function : SortBoxes
 381 //purpose  :
 382 //=======================================================================
 383 void Bnd_BoundSortBox::SortBoxes()
 384 {
 385   Standard_Integer labox;
 386   Standard_Integer lacaseX, firstcaseX, lastcaseX;
 387   Standard_Integer lacaseY, firstcaseY, lastcaseY;
 388   Standard_Integer lacaseZ, firstcaseZ, lastcaseZ;
 389   Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 390   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 391   Standard_Integer i0=taBox.Lower();
 392   Standard_Integer i1=taBox.Upper();
 393   BSB_T3Bits* Map=0;
 394   if(TabBits) {
 395     BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
 396     delete _Map;
 397   }
 398   Map = new BSB_T3Bits(discrX);
 399   TabBits = (void *)Map;
 400   if(Map->ToTest==0) {
 401     Standard_Integer s=i1-i0;
 402     if(s<2) s=2;
 403     Map->ToTest = new Standard_Integer [s];
 404     for(Standard_Integer i=0; i<s; i++) {
 405       Map->ToTest[i]=i0-1;
 406     }
 407   }
 408   Standard_Real _Xmax,_Xmin,_Ymax,_Ymin,_Zmin,_Zmax;
 409   myBox.Get(_Xmin,_Ymin,_Zmin,_Xmax,_Ymax,_Zmax);
 410   Map->Xmax=_Xmax; Map->Ymax=_Ymax; Map->Zmax=_Zmax;
 411   Map->Xmin=_Xmin; Map->Ymin=_Ymin; Map->Zmin=_Zmin;
 412   for (labox=i0; labox<=i1; labox++) {
 413     if (!taBox(labox).IsVoid()) {
 414       taBox(labox).Get(xmin, ymin, zmin, xmax, ymax, zmax);
 415       if(xmin>Xmin) firstcaseX=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  firstcaseX=1;
 416       if(ymin>Ymin) firstcaseY=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  firstcaseY=1;
 417       if(zmin>Zmin) firstcaseZ=(Standard_Integer )((zmin-Zmin)*deltaZ)-1; else  firstcaseZ=1;
 418       if(xmax<_Xmax) lastcaseX=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  lastcaseX=discrX;
 419       if(ymax<_Ymax) lastcaseY=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  lastcaseY=discrY;
 420       if(zmax<_Zmax) lastcaseZ=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  lastcaseZ=discrZ;
 421       if(firstcaseX<1) firstcaseX=1; else if(firstcaseX>discrX) firstcaseX=discrX;
 422       if(firstcaseY<1) firstcaseY=1; else if(firstcaseY>discrY) firstcaseY=discrY;
 423       if(firstcaseZ<1) firstcaseZ=1; else if(firstcaseZ>discrZ) firstcaseZ=discrZ;
 424
 425       if(lastcaseX<1) lastcaseX=1; else if(lastcaseX>discrX) lastcaseX=discrX;
 426       if(lastcaseY<1) lastcaseY=1; else if(lastcaseY>discrY) lastcaseY=discrY;
 427       if(lastcaseZ<1) lastcaseZ=1; else if(lastcaseZ>discrZ) lastcaseZ=discrZ;
 428
 429       Standard_Integer n = (lastcaseX-firstcaseX);
 430       if(n>(lastcaseY-firstcaseY)) n=lastcaseY-firstcaseY;
 431       if(n>(lastcaseZ-firstcaseZ)) n=lastcaseZ-firstcaseZ;
 432 #if DEBUG
 433       NBBOITES++;
 434 #endif
 435       n<<=2;
 436       if(n>discrX) {
 437 #if DEBUG
 438       NBBOITESATESTER++;
 439 #endif
 440         for(Standard_Integer i=0; i<(i1-i0); i++) {
 441           if(Map->ToTest[i]<i0) {
 442             Map->ToTest[i]=labox;
 443             break;
 444           }
 445         }
 446       }
 447       else {
 448         for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
 449           Map->AppendAxisX(lacaseX,labox);
 450         }
 451         for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
 452           Map->AppendAxisY(lacaseY,labox);
 453         }
 454         for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
 455           Map->AppendAxisZ(lacaseZ,labox);
 456         }
 457         //------------------------------------------------------------
 458         //-- fill table with bits
 459         //--
 460         if(Map) {
 461           for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
 462             for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
 463               for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
 464                 long unsigned t=Map->GrilleInteger(lacaseX-1,lacaseY-1,lacaseZ-1);
 465                 Map->Add(t);
 466               }
 467             }
 468           }
 469         }
 470       }
 471     }
 472   }
 473 }
 474 //=======================================================================
 475 //function : Initialize
 476 //purpose  :
 477 //=======================================================================
 478 void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
 479                                   const Standard_Integer nbComponents)
 480 {
 481   Standard_NullValue_Raise_if (nbComponents <=0, "BoundSortBox nul!");
 482   myBox=CompleteBox;
 483   myBndComponents=new Bnd_HArray1OfBox(1,nbComponents);
 484
 485   //***>>> JCD - 04.08.2000 - Array initialization is missing...
 486   Bnd_Box emptyBox;
 487   myBndComponents->Init( emptyBox );
 488   //***<<< JCD - End
 489
 490   discrX=discrY=discrZ=ComputeSize(nbComponents);
 491   Standard_Real Xmax, Ymax, Zmax;
 492
 493   if(CompleteBox.IsVoid())
 494     return;
 495   CompleteBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 496   myBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 497   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 498   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 499   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 500   if(TabBits) {
 501     BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
 502     delete _Map;
 503     TabBits=0;
 504   }
 505   BSB_T3Bits* Map=0;
 506   Map = new BSB_T3Bits(discrX);
 507   TabBits = (void *)Map;
 508 }
 509 //=======================================================================
 510 //function : Add
 511 //purpose  :
 512 //=======================================================================
 513 void Bnd_BoundSortBox::Add(const Bnd_Box& theBox,
 514                            const Standard_Integer boxIndex)
 515 {
 516   Standard_MultiplyDefined_Raise_if (!(myBndComponents->Value(boxIndex).IsVoid()), " This box is already defined !");
 517   if (!theBox.IsVoid()) {
 518     Standard_Integer i0=myBndComponents->Lower();
 519     Standard_Integer i1=myBndComponents->Upper();
 520     Standard_Integer theGapX, firstGapX , lastGapX;
 521     Standard_Integer theGapY, firstGapY , lastGapY;
 522     Standard_Integer theGapZ, firstGapZ , lastGapZ;
 523     Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 524     myBndComponents->SetValue(boxIndex, theBox);
 525     theBox.Get(xmin, ymin, zmin, xmax, ymax, zmax);
 526     BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 527     if(Map->ToTest==0) {
 528       Standard_Integer s=i1-i0;
 529       if(s<2) s=2;
 530       Map->ToTest = new Standard_Integer [s];
 531       for(Standard_Integer i=0; i<s; i++) {
 532         Map->ToTest[i]=i0-1;
 533       }
 534     }
 535     Standard_Real _Xmax,_Ymax,_Zmax;
 536     _Xmax=Map->Xmax; _Ymax=Map->Ymax; _Zmax=Map->Zmax;
 537     if(xmin>Xmin) firstGapX=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  firstGapX=1;
 538     if(ymin>Ymin) firstGapY=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  firstGapY=1;
 539     if(zmin>Zmin) firstGapZ=(Standard_Integer ) ((zmin-Zmin)*deltaZ)-1; else  firstGapZ=1;
 540     if(xmax<_Xmax) lastGapX=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  lastGapX=discrX;
 541     if(ymax<_Ymax) lastGapY=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  lastGapY=discrY;
 542     if(zmax<_Zmax) lastGapZ=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  lastGapZ=discrZ;
 543     if(firstGapX<1) firstGapX=1; else if(firstGapX>discrX) firstGapX=discrX;
 544     if(firstGapY<1) firstGapY=1; else if(firstGapY>discrY) firstGapY=discrY;
 545     if(firstGapZ<1) firstGapZ=1; else if(firstGapZ>discrZ) firstGapZ=discrZ;
 546
 547     if(lastGapX<1) lastGapX=1; else if(lastGapX>discrX) lastGapX=discrX;
 548     if(lastGapY<1) lastGapY=1; else if(lastGapY>discrY) lastGapY=discrY;
 549     if(lastGapZ<1) lastGapZ=1; else if(lastGapZ>discrZ) lastGapZ=discrZ;
 550     Standard_Integer n = (lastGapX-firstGapX);
 551     if(n>(lastGapY-firstGapY)) n=lastGapY-firstGapY;
 552     if(n>(lastGapZ-firstGapZ)) n=lastGapZ-firstGapZ;
 553     n<<=2;
 554 #if DEBUG
 555       NBBOITES++;
 556 #endif
 557     if(n>discrX) {
 558 #if DEBUG
 559       NBBOITESATESTER++;
 560 #endif
 561       for(Standard_Integer i=0; i<(i1-i0); i++) {
 562         if(Map->ToTest[i]<i0) {
 563           Map->ToTest[i]=boxIndex;
 564           break;
 565         }
 566       }
 567     }
 568     for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
 569       Map->AppendAxisY(theGapY,boxIndex);
 570     }
 571     for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
 572       Map->AppendAxisX(theGapX,boxIndex);
 573     }
 574     for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
 575       Map->AppendAxisZ(theGapZ,boxIndex);
 576     }
 577     //------------------------------------------------------------
 578     //-- fill table with bits
 579     //--
 580     if(TabBits) {
 581       Map=(BSB_T3Bits *)TabBits;
 582       for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
 583         for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
 584           for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
 585             long unsigned t=Map->GrilleInteger(theGapX-1,theGapY-1,theGapZ-1);
 586             Map->Add(t);
 587           }
 588         }
 589       }
 590     }
 591   }
 592 }
 593 //=======================================================================
 594 #if VERIFICATION
 595 static void VerifCompare(const TColStd_ListOfInteger& lastResult,
 596                          const Bnd_Box& theBox,
 597                          const Bnd_Array1OfBox&  taBox) {
 598   static int Verif = 1;
 599   Standard_Integer i ;
 600
 601   if(Verif) {
 602     Standard_Integer i0,i1;
 603     i0=taBox.Lower();
 604     i1=taBox.Upper();
 605     char * qwe=new char [i1+1];  //-- $$$$$$$ ATTENTION IF I0 < 0
 606     for( i=i0; i<=i1; i++) qwe[i]='\0';
 607     TColStd_ListIteratorOfListOfInteger  theList(lastResult);
 608     for (; theList.More(); theList.Next()) {
 609       qwe[theList.Value()]=(char)1;
 610     }
 611     Standard_Integer labox;
 612     for (labox=i0; labox<=i1; labox++) {
 613       if (!taBox(labox).IsOut(theBox)) {
 614         qwe[labox]+=2;
 615       }
 616     }
 617     for(i=i0;i<=i1;i++) {
 618       if(qwe[i]==2) {
 619         printf("\nPb with box: %d ",i);
 620       }
 621       else if(qwe[i]==1) {
 622         printf("\n false rejection by %d \n",i);
 623       }
 624     }
 625     delete [] qwe;
 626   }
 627 }
 628 #endif
 629 //=======================================================================
 630 //function : Compare
 631 //purpose  :
 632 //=======================================================================
 633 const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare (const Bnd_Box& theBox)
 634
 635 {
 636  Standard_Integer lacase ;
 637 #if DEBUG
 638   NBCOMPARE++;
 639 #endif
 640   lastResult.Clear();
 641   if (theBox.IsVoid()) return lastResult;
 642   if (theBox.IsOut(myBox)) {
 643 #if DEBUG
 644     REJECTNIV0++;
 645 #endif
 646     return lastResult;
 647   }
 648   const Bnd_Array1OfBox& taBox=myBndComponents->Array1();
 649   //-- Rejection with the table of bits
 650   Standard_Boolean touch = Standard_True;
 651   touch = Standard_False;
 652   Standard_Real _Xmin,_Ymin,_Zmin,_Xmax,_Ymax,_Zmax;
 653   BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 654   Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 655   _Xmax=Map->Xmax; _Ymax=Map->Ymax; _Zmax=Map->Zmax;
 656   _Xmin=Map->Xmin; _Ymin=Map->Ymin; _Zmin=Map->Zmin;
 657   theBox.Get(xmin, ymin, zmin, xmax, ymax, zmax);
 658   Standard_Integer i0,i1,j0,j1,k0,k1;
 659   if(xmin>Xmin) i0=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  i0=1;
 660   if(ymin>Ymin) j0=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  j0=1;
 661   if(zmin>Zmin) k0=(Standard_Integer )((zmin-Zmin)*deltaZ)-1; else  k0=1;
 662   if(xmax<_Xmax) i1=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  i1=discrX;
 663   if(ymax<_Ymax) j1=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  j1=discrY;
 664   if(zmax<_Zmax) k1=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  k1=discrZ;
 665   if(i0<1) i0=1; else if(i0>discrX) i0=discrX;
 666   if(j0<1) j0=1; else if(j0>discrY) j0=discrY;
 667   if(k0<1) k0=1; else if(k0>discrZ) k0=discrZ;
 668
 669   if(i1<1) i1=1; else if(i1>discrX) i1=discrX;
 670   if(j1<1) j1=1; else if(j1>discrY) j1=discrY;
 671   if(k1<1) k1=1; else if(k1>discrZ) k1=discrZ;
 672   i0--; j0--; k0--; i1--; j1--; k1--;
 673   for(Standard_Integer i=i0; touch==Standard_False && i<=i1;i++) {
 674     for(Standard_Integer j=j0; touch==Standard_False && j<=j1;j++) {
 675       for(Standard_Integer k=k0;  touch==Standard_False && k<=k1;k++) {
 676         long unsigned t=Map->GrilleInteger(i,j,k);
 677         if(Map->Val(t)) {
 678           touch = Standard_True;
 679         }
 680       }
 681     }
 682   }
 683   //-- processing of systematically tested boxes
 684   if(Map->ToTest) {
 685     Standard_Integer l0 = taBox.Lower();
 686     Standard_Integer l1 = taBox.Upper();
 687     l1-=l0;
 688     for(Standard_Integer l=0; Map->ToTest[l]>=l0 && l<(l1-l0); l++) {
 689       if(Map->ToTest[l]>=l0) {
 690         if (!taBox(Map->ToTest[l]).IsOut(theBox)){
 691           lastResult.Append(Map->ToTest[l]);
 692         }
 693       }
 694     }
 695   }
 696   if(touch == Standard_False) {
 697 #if DEBUG
 698     REJECTNIV1++;
 699 #endif
 700 #if VERIFICATION
 701     VerifCompare(lastResult,theBox,taBox);
 702 #endif
 703     return(lastResult);
 704   }
 705   //------------------------
 706   //-- classic processing --
 707   //------------------------
 708   i0++; i1++; j0++; j1++; k0++; k1++;
 709   Crible.Clear();
 710   theFound=6;
 711   Standard_Integer cardY=0;
 712   for (lacase=j0; lacase<=j1; lacase++) {
 713     Standard_Integer nby=Map->NbAxisY(lacase);
 714     while(nby>0) {
 715       cardY++;
 716       Crible.Bind(Map->axisY[lacase][nby], 4);
 717       nby--;
 718     }
 719   }
 720   if (cardY==0) {
 721 #if VERIFICATION
 722     VerifCompare(lastResult,theBox,taBox);
 723 #endif
 724     return lastResult;
 725   }
 726   Standard_Integer cardZ=0;
 727   for (lacase=k0; lacase<=k1; lacase++) {
 728     Standard_Integer nbz=Map->NbAxisZ(lacase);
 729     while(nbz>0) {
 730       cardZ++;
 731       if (Crible.IsBound(Map->axisZ[lacase][nbz])) {
 732         Crible.Bind(Map->axisZ[lacase][nbz], 6);
 733       }
 734       nbz--;
 735     }
 736   }
 737   if (cardZ==0) {
 738 #if VERIFICATION
 739     VerifCompare(lastResult,theBox,taBox);
 740 #endif
 741     return lastResult;
 742   }
 743   for (lacase=i0; lacase<=i1; lacase++) {
 744     Standard_Integer nbx = Map->NbAxisX(lacase);
 745     while(nbx>0) {
 746       Standard_Integer x=Map->axisX[lacase][nbx];
 747       if (Crible.IsBound(x)) {
 748         if (Crible(x)==theFound) {
 749           Crible.UnBind(x);
 750           if (!taBox(x).IsOut(theBox)){
 751             lastResult.Append(x);
 752           }
 753         }
 754       }
 755       nbx--;
 756     }
 757   }
 758 #if VERIFICATION
 759   VerifCompare(lastResult,theBox,taBox);
 760 #endif
 761   return lastResult;
 762 }
 763 //=======================================================================
 764 //function : Dump
 765 //purpose  :
 766 //=======================================================================
 767
 768 void Bnd_BoundSortBox::Dump() const
 769 {}
 770 //=======================================================================
 771 //function : Compare
 772 //purpose  :
 773 //=======================================================================
 774 const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare(const gp_Pln& thePlane)
 775
 776 {
 777   lastResult.Clear();
 778   Standard_Integer i;
 779   const Bnd_Array1OfBox& boxes = myBndComponents->Array1();
 780   for (i = boxes.Lower(); i <= boxes.Upper(); i++) {
 781     if (!boxes(i).IsOut(thePlane))
 782       lastResult.Append(i);
 783   }
 784   return lastResult;
 785 }
 786 //=======================================================================
 787 void Bnd_BoundSortBox::Destroy() {
 788 #if DEBUG
 789   printf("\nDESTROY NBCOMPARE:%lu  REJECTNIV0:%lu  REJECTIONSOK=%lu  NBBOITES:%lu NBBOITESATESTER:%lu\n",
 790          NBCOMPARE,REJECTNIV0,REJECTNIV1,NBBOITES,NBBOITESATESTER);
 791 #endif
 792   BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 793   if(Map) {
 794     delete Map;
 795     Map=0;
 796   }
 797 }
 798 //=======================================================================
 799