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
  18 #include <Bnd_Array1OfBox.hxx>
  19 #include <Bnd_BoundSortBox.hxx>
  20 #include <Bnd_Box.hxx>
  21 #include <gp_Pln.hxx>
  22 #include <Standard_MultiplyDefined.hxx>
  23 #include <Standard_NullValue.hxx>
  24 #include <TColStd_DataMapIteratorOfDataMapOfIntegerInteger.hxx>
  25 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  26
  27 #include <stdio.h>
  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 #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
 123 //-- size is power of 2 > 4
 124 class BSB_T3Bits
 125 {
 126 public:
 127
 128   Standard_Integer _DECAL;
 129   Standard_Integer _DECAL2;
 130   Standard_Integer _BASE;
 131   Standard_Integer _BASEM1;
 132
 133   long unsigned ind;
 134   long unsigned Isize;
 135   Standard_Integer ssize;
 136   Standard_Real Xmin,Xmax,Ymin,Ymax,Zmin,Zmax;
 137
 138   long unsigned *p;
 139   Standard_Integer **axisX;
 140   Standard_Integer **axisY;
 141   Standard_Integer **axisZ;
 142
 143   Standard_Integer *ToTest;
 144
 145 public:
 146   BSB_T3Bits(int size);
 147   ~BSB_T3Bits();
 148
 149   //-- Part HArray1OfListOfInteger
 150
 151   void AppendAxisX(const Standard_Integer i,const Standard_Integer v);
 152   void AppendAxisY(const Standard_Integer i,const Standard_Integer v);
 153   void AppendAxisZ(const Standard_Integer i,const Standard_Integer v);
 154
 155   void Add(long unsigned t) { int o=t&31;    int k=t>>5;    p[k]|=_P2[o];          }
 156   int Val(long unsigned t)  { int o=t&31;    int k=t>>5;    return(p[k]&_P2[o]);   }
 157   void Raz(long unsigned t) { int o=t&31;    int k=t>>5;    p[k]&= ~(_P2[o]);      }
 158
 159   Standard_Integer NbAxisX(const Standard_Integer i) {   return(axisX[0][i]);   }
 160   Standard_Integer NbAxisY(const Standard_Integer i) {   return(axisY[0][i]);   }
 161   Standard_Integer NbAxisZ(const Standard_Integer i) {   return(axisZ[0][i]);   }
 162
 163   inline Standard_Integer GrilleInteger(Standard_Integer ix,
 164                                         Standard_Integer iy,
 165                                         Standard_Integer iz)
 166   {
 167     Standard_Integer tz = iz<<_DECAL2;
 168     Standard_Integer ty = iy<<_DECAL;
 169     Standard_Integer t  = ix;
 170     t|=ty;
 171     t|=tz;
 172     return(t);
 173   }
 174
 175   inline void IntegerGrille(Standard_Integer t,
 176                             Standard_Integer &ix,
 177                             Standard_Integer &iy,
 178                             Standard_Integer &iz)
 179   {
 180     ix = t & _BASEM1; t>>=_DECAL;
 181     iy = t & _BASEM1; t>>=_DECAL;
 182     iz = t;
 183   }
 184
 185 private:
 186
 187   BSB_T3Bits (const BSB_T3Bits&);
 188   BSB_T3Bits& operator= (const BSB_T3Bits&);
 189 };
 190
 191 //=======================================================================
 192 BSB_T3Bits::~BSB_T3Bits()
 193 {
 194   if(p) { delete [] p; p=0; }
 195 #if DEBUG
 196   printf("\n BASE:%d\n",_BASE);
 197 #endif
 198   for(Standard_Integer i=0; i<=ssize; i++) {
 199     if(axisX[i]) { delete [] axisX[i]; axisX[i]=0; }
 200     if(axisY[i]) { delete [] axisY[i]; axisY[i]=0; }
 201     if(axisZ[i]) { delete [] axisZ[i]; axisZ[i]=0; }
 202   }
 203   free(axisX); axisX=0;
 204   free(axisY); axisY=0;
 205   free(axisZ); axisZ=0;
 206   if(ToTest)  { delete [] ToTest; ToTest=0; }
 207 }
 208 //=======================================================================
 209 BSB_T3Bits::BSB_T3Bits(int size)
 210         : ind(0),
 211     Xmin(0),Xmax(0),
 212         Ymin(0),Ymax(0),
 213         Zmin(0),Zmax(0)
 214 {
 215   switch (size) {
 216   case 128: {  _DECAL=7;   _DECAL2=14;   _BASE=128;  _BASEM1=127;  break; }
 217   case  64: {  _DECAL=6;   _DECAL2=12;   _BASE= 64;  _BASEM1= 63;  break; }
 218   case  32: {  _DECAL=5;   _DECAL2=10;   _BASE= 32;  _BASEM1= 31;  break; }
 219   case  16: {  _DECAL=4;   _DECAL2= 8;   _BASE= 16;  _BASEM1= 15;  break; }
 220   default : {  _DECAL=3;   _DECAL2= 6;   _BASE=  8;  _BASEM1=  7;  break; }
 221   }
 222   Standard_Integer i ;
 223   long unsigned nb = (size*size*size)>>5;
 224   Isize = nb;
 225   ssize = size;
 226   p = new long unsigned [nb];
 227   do { p[--nb]=0; } while(nb);
 228
 229   axisX = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 230   axisY = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 231   axisZ = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
 232
 233   axisX[0]=new Standard_Integer [_BASE+1];
 234   axisY[0]=new Standard_Integer [_BASE+1];
 235   axisZ[0]=new Standard_Integer [_BASE+1];
 236
 237   for( i=0; i<(_BASE+1); i++) {
 238     axisX[0][i]=0;
 239     axisY[0][i]=0;
 240     axisZ[0][i]=0;
 241   }
 242
 243   for(i=1; i<=size; i++) {
 244     axisX[i] =  new Standard_Integer[DIMAXIS];
 245     axisY[i] =  new Standard_Integer[DIMAXIS];
 246     axisZ[i] =  new Standard_Integer[DIMAXIS];
 247     axisX[i][0]=DIMAXIS;
 248     axisY[i][0]=DIMAXIS;
 249     axisZ[i][0]=DIMAXIS;
 250     axisX[i][1]=axisY[i][1]=axisZ[i][1]=-1;
 251   }
 252   ToTest=0;
 253 }
 254 //=======================================================================
 255 void BSB_T3Bits::AppendAxisZ(const Standard_Integer i,
 256                              const Standard_Integer v) {
 257   Standard_Integer n = axisZ[0][i];
 258   n++;
 259   if(n<axisZ[i][0]) { axisZ[i][n]=v; }
 260   else {
 261     Standard_Integer s=axisZ[i][0];
 262     Standard_Integer *nt = new Standard_Integer [s+s];
 263     nt[0]=s+s;
 264     for(Standard_Integer j=1;j<s;j++) {
 265       nt[j]=axisZ[i][j];
 266     }
 267     nt[n]=v;
 268     delete [] axisZ[i];
 269     axisZ[i]=nt;
 270   }
 271   axisZ[0][i]=n;
 272 }
 273 //=======================================================================
 274 void BSB_T3Bits::AppendAxisY(const Standard_Integer i,
 275                              const Standard_Integer v) {
 276   Standard_Integer n = axisY[0][i];
 277   n++;
 278   if(n<axisY[i][0]) { axisY[i][n]=v;   }
 279   else {
 280     Standard_Integer s=axisY[i][0];
 281     Standard_Integer *nt = new Standard_Integer [s+s];
 282     nt[0]=s+s;
 283     for(Standard_Integer j=1;j<s;j++) {
 284       nt[j]=axisY[i][j];
 285     }
 286     nt[n]=v;
 287     delete [] axisY[i];
 288     axisY[i]=nt;
 289   }
 290   axisY[0][i]=n;
 291 }
 292 //=======================================================================
 293 void BSB_T3Bits::AppendAxisX(const Standard_Integer i,
 294                              const Standard_Integer v) {
 295   Standard_Integer n = axisX[0][i];
 296
 297   n++;
 298   if(n<axisX[i][0]) {   axisX[i][n]=v;   }
 299   else {
 300     //-- it is required to extend
 301     Standard_Integer s=axisX[i][0];
 302     Standard_Integer *nt = new Standard_Integer [s+s];
 303     nt[0]=s+s;
 304     for(Standard_Integer j=1;j<s;j++) {
 305       nt[j]=axisX[i][j];
 306     }
 307     nt[n]=v;
 308     delete [] axisX[i];
 309     axisX[i]=nt;
 310   }
 311   axisX[0][i]=n;
 312 }
 313 //=======================================================================
 314 //=======================================================================
 315 //function : Bnd_BoundSortBox
 316 //purpose  :
 317 //=======================================================================
 318 Bnd_BoundSortBox::Bnd_BoundSortBox()
 319      : discrX(0), discrY(0), discrZ(0)
 320 {
 321   TabBits=0;
 322 #if DEBUG
 323   NBCOMPARE=0L;   NBBOITES=0L;   NBBOITESATESTER=0L;
 324   APPELREJECTION=0L;  REJECTNIV0=0L;  REJECTNIV1=0L;
 325 #endif
 326 }
 327 //=======================================================================
 328 //function : Initialize
 329 //purpose  :
 330 //=======================================================================
 331
 332 void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
 333                                   const Handle(Bnd_HArray1OfBox)& SetOfBox)
 334 {
 335   myBox=CompleteBox;
 336   myBndComponents=SetOfBox;
 337   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 338   discrX=discrY=discrZ=ComputeSize(taBox.Upper()-taBox.Lower());
 339   Standard_Real Xmax, Ymax, Zmax;
 340   if(CompleteBox.IsVoid())
 341     return;
 342   CompleteBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 343   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 344   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 345   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 346   SortBoxes();
 347 }
 348 //=======================================================================
 349 //function : Initialize
 350 //purpose  :
 351 //=======================================================================
 352 void Bnd_BoundSortBox::Initialize(const Handle(Bnd_HArray1OfBox)& SetOfBox)
 353 {
 354   myBndComponents=SetOfBox;
 355   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 356   Standard_Integer i0,i1;
 357   i0=taBox.Lower();
 358   i1=taBox.Upper();
 359   discrX=discrY=discrZ=ComputeSize(i1-i0);
 360   Standard_Integer labox;
 361   for (labox=i0; labox<=i1; labox++) {
 362     if (!taBox(labox).IsVoid()) {
 363       myBox.Add(taBox(labox));
 364     }
 365   }
 366   Standard_Real Xmax, Ymax, Zmax;
 367   if(myBox.IsVoid())
 368     return;
 369   myBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 370   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 371   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 372   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 373   SortBoxes();
 374 }
 375 //=======================================================================
 376 //function : SortBoxes
 377 //purpose  :
 378 //=======================================================================
 379 void Bnd_BoundSortBox::SortBoxes()
 380 {
 381   Standard_Integer labox;
 382   Standard_Integer lacaseX, firstcaseX, lastcaseX;
 383   Standard_Integer lacaseY, firstcaseY, lastcaseY;
 384   Standard_Integer lacaseZ, firstcaseZ, lastcaseZ;
 385   Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 386   const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
 387   Standard_Integer i0=taBox.Lower();
 388   Standard_Integer i1=taBox.Upper();
 389   BSB_T3Bits* Map=0;
 390   if(TabBits) {
 391     BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
 392     delete _Map;
 393   }
 394   Map = new BSB_T3Bits(discrX);
 395   TabBits = (void *)Map;
 396   if(Map->ToTest==0) {
 397     Standard_Integer s=i1-i0;
 398     if(s<2) s=2;
 399     Map->ToTest = new Standard_Integer [s];
 400     for(Standard_Integer i=0; i<s; i++) {
 401       Map->ToTest[i]=i0-1;
 402     }
 403   }
 404   Standard_Real _Xmax,_Xmin,_Ymax,_Ymin,_Zmin,_Zmax;
 405   myBox.Get(_Xmin,_Ymin,_Zmin,_Xmax,_Ymax,_Zmax);
 406   Map->Xmax=_Xmax; Map->Ymax=_Ymax; Map->Zmax=_Zmax;
 407   Map->Xmin=_Xmin; Map->Ymin=_Ymin; Map->Zmin=_Zmin;
 408   for (labox=i0; labox<=i1; labox++) {
 409     if (!taBox(labox).IsVoid()) {
 410       taBox(labox).Get(xmin, ymin, zmin, xmax, ymax, zmax);
 411       if(xmin>Xmin) firstcaseX=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  firstcaseX=1;
 412       if(ymin>Ymin) firstcaseY=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  firstcaseY=1;
 413       if(zmin>Zmin) firstcaseZ=(Standard_Integer )((zmin-Zmin)*deltaZ)-1; else  firstcaseZ=1;
 414       if(xmax<_Xmax) lastcaseX=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  lastcaseX=discrX;
 415       if(ymax<_Ymax) lastcaseY=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  lastcaseY=discrY;
 416       if(zmax<_Zmax) lastcaseZ=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  lastcaseZ=discrZ;
 417       if(firstcaseX<1) firstcaseX=1; else if(firstcaseX>discrX) firstcaseX=discrX;
 418       if(firstcaseY<1) firstcaseY=1; else if(firstcaseY>discrY) firstcaseY=discrY;
 419       if(firstcaseZ<1) firstcaseZ=1; else if(firstcaseZ>discrZ) firstcaseZ=discrZ;
 420
 421       if(lastcaseX<1) lastcaseX=1; else if(lastcaseX>discrX) lastcaseX=discrX;
 422       if(lastcaseY<1) lastcaseY=1; else if(lastcaseY>discrY) lastcaseY=discrY;
 423       if(lastcaseZ<1) lastcaseZ=1; else if(lastcaseZ>discrZ) lastcaseZ=discrZ;
 424
 425       Standard_Integer n = (lastcaseX-firstcaseX);
 426       if(n>(lastcaseY-firstcaseY)) n=lastcaseY-firstcaseY;
 427       if(n>(lastcaseZ-firstcaseZ)) n=lastcaseZ-firstcaseZ;
 428 #if DEBUG
 429       NBBOITES++;
 430 #endif
 431       n<<=2;
 432       if(n>discrX) {
 433 #if DEBUG
 434       NBBOITESATESTER++;
 435 #endif
 436         for(Standard_Integer i=0; i<(i1-i0); i++) {
 437           if(Map->ToTest[i]<i0) {
 438             Map->ToTest[i]=labox;
 439             break;
 440           }
 441         }
 442       }
 443       else {
 444         for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
 445           Map->AppendAxisX(lacaseX,labox);
 446         }
 447         for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
 448           Map->AppendAxisY(lacaseY,labox);
 449         }
 450         for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
 451           Map->AppendAxisZ(lacaseZ,labox);
 452         }
 453         //------------------------------------------------------------
 454         //-- fill table with bits
 455         //--
 456         if(Map) {
 457           for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
 458             for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
 459               for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
 460                 long unsigned t=Map->GrilleInteger(lacaseX-1,lacaseY-1,lacaseZ-1);
 461                 Map->Add(t);
 462               }
 463             }
 464           }
 465         }
 466       }
 467     }
 468   }
 469 }
 470 //=======================================================================
 471 //function : Initialize
 472 //purpose  :
 473 //=======================================================================
 474 void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
 475                                   const Standard_Integer nbComponents)
 476 {
 477   Standard_NullValue_Raise_if (nbComponents <=0, "BoundSortBox nul!");
 478   myBox=CompleteBox;
 479   myBndComponents=new Bnd_HArray1OfBox(1,nbComponents);
 480
 481   //***>>> JCD - 04.08.2000 - Array initialization is missing...
 482   Bnd_Box emptyBox;
 483   myBndComponents->Init( emptyBox );
 484   //***<<< JCD - End
 485
 486   discrX=discrY=discrZ=ComputeSize(nbComponents);
 487   Standard_Real Xmax, Ymax, Zmax;
 488
 489   if(CompleteBox.IsVoid())
 490     return;
 491   CompleteBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 492   myBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
 493   deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
 494   deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
 495   deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
 496   if(TabBits) {
 497     BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
 498     delete _Map;
 499     TabBits=0;
 500   }
 501   BSB_T3Bits* Map=0;
 502   Map = new BSB_T3Bits(discrX);
 503   TabBits = (void *)Map;
 504 }
 505 //=======================================================================
 506 //function : Add
 507 //purpose  :
 508 //=======================================================================
 509 void Bnd_BoundSortBox::Add(const Bnd_Box& theBox,
 510                            const Standard_Integer boxIndex)
 511 {
 512   Standard_MultiplyDefined_Raise_if (!(myBndComponents->Value(boxIndex).IsVoid()), " This box is already defined !");
 513   if (!theBox.IsVoid()) {
 514     Standard_Integer i0=myBndComponents->Lower();
 515     Standard_Integer i1=myBndComponents->Upper();
 516     Standard_Integer theGapX, firstGapX , lastGapX;
 517     Standard_Integer theGapY, firstGapY , lastGapY;
 518     Standard_Integer theGapZ, firstGapZ , lastGapZ;
 519     Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 520     myBndComponents->SetValue(boxIndex, theBox);
 521     theBox.Get(xmin, ymin, zmin, xmax, ymax, zmax);
 522     BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 523     if(Map->ToTest==0) {
 524       Standard_Integer s=i1-i0;
 525       if(s<2) s=2;
 526       Map->ToTest = new Standard_Integer [s];
 527       for(Standard_Integer i=0; i<s; i++) {
 528         Map->ToTest[i]=i0-1;
 529       }
 530     }
 531     Standard_Real _Xmax,_Ymax,_Zmax;
 532     _Xmax=Map->Xmax; _Ymax=Map->Ymax; _Zmax=Map->Zmax;
 533     if(xmin>Xmin) firstGapX=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  firstGapX=1;
 534     if(ymin>Ymin) firstGapY=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  firstGapY=1;
 535     if(zmin>Zmin) firstGapZ=(Standard_Integer ) ((zmin-Zmin)*deltaZ)-1; else  firstGapZ=1;
 536     if(xmax<_Xmax) lastGapX=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  lastGapX=discrX;
 537     if(ymax<_Ymax) lastGapY=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  lastGapY=discrY;
 538     if(zmax<_Zmax) lastGapZ=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  lastGapZ=discrZ;
 539     if(firstGapX<1) firstGapX=1; else if(firstGapX>discrX) firstGapX=discrX;
 540     if(firstGapY<1) firstGapY=1; else if(firstGapY>discrY) firstGapY=discrY;
 541     if(firstGapZ<1) firstGapZ=1; else if(firstGapZ>discrZ) firstGapZ=discrZ;
 542
 543     if(lastGapX<1) lastGapX=1; else if(lastGapX>discrX) lastGapX=discrX;
 544     if(lastGapY<1) lastGapY=1; else if(lastGapY>discrY) lastGapY=discrY;
 545     if(lastGapZ<1) lastGapZ=1; else if(lastGapZ>discrZ) lastGapZ=discrZ;
 546     Standard_Integer n = (lastGapX-firstGapX);
 547     if(n>(lastGapY-firstGapY)) n=lastGapY-firstGapY;
 548     if(n>(lastGapZ-firstGapZ)) n=lastGapZ-firstGapZ;
 549     n<<=2;
 550 #if DEBUG
 551       NBBOITES++;
 552 #endif
 553     if(n>discrX) {
 554 #if DEBUG
 555       NBBOITESATESTER++;
 556 #endif
 557       for(Standard_Integer i=0; i<(i1-i0); i++) {
 558         if(Map->ToTest[i]<i0) {
 559           Map->ToTest[i]=boxIndex;
 560           break;
 561         }
 562       }
 563     }
 564     for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
 565       Map->AppendAxisY(theGapY,boxIndex);
 566     }
 567     for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
 568       Map->AppendAxisX(theGapX,boxIndex);
 569     }
 570     for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
 571       Map->AppendAxisZ(theGapZ,boxIndex);
 572     }
 573     //------------------------------------------------------------
 574     //-- fill table with bits
 575     //--
 576     if(TabBits) {
 577       Map=(BSB_T3Bits *)TabBits;
 578       for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
 579         for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
 580           for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
 581             long unsigned t=Map->GrilleInteger(theGapX-1,theGapY-1,theGapZ-1);
 582             Map->Add(t);
 583           }
 584         }
 585       }
 586     }
 587   }
 588 }
 589 //=======================================================================
 590 #if VERIFICATION
 591 static void VerifCompare(const TColStd_ListOfInteger& lastResult,
 592                          const Bnd_Box& theBox,
 593                          const Bnd_Array1OfBox&  taBox) {
 594   static int Verif = 1;
 595   Standard_Integer i ;
 596
 597   if(Verif) {
 598     Standard_Integer i0,i1;
 599     i0=taBox.Lower();
 600     i1=taBox.Upper();
 601     char * qwe=new char [i1+1];  //-- $$$$$$$ ATTENTION IF I0 < 0
 602     for( i=i0; i<=i1; i++) qwe[i]='\0';
 603     TColStd_ListIteratorOfListOfInteger  theList(lastResult);
 604     for (; theList.More(); theList.Next()) {
 605       qwe[theList.Value()]=(char)1;
 606     }
 607     Standard_Integer labox;
 608     for (labox=i0; labox<=i1; labox++) {
 609       if (!taBox(labox).IsOut(theBox)) {
 610         qwe[labox]+=2;
 611       }
 612     }
 613     for(i=i0;i<=i1;i++) {
 614       if(qwe[i]==2) {
 615         printf("\nPb with box: %d ",i);
 616       }
 617       else if(qwe[i]==1) {
 618         printf("\n false rejection by %d \n",i);
 619       }
 620     }
 621     delete [] qwe;
 622   }
 623 }
 624 #endif
 625 //=======================================================================
 626 //function : Compare
 627 //purpose  :
 628 //=======================================================================
 629 const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare (const Bnd_Box& theBox)
 630
 631 {
 632  Standard_Integer lacase ;
 633 #if DEBUG
 634   NBCOMPARE++;
 635 #endif
 636   lastResult.Clear();
 637   if (theBox.IsVoid()) return lastResult;
 638   if (theBox.IsOut(myBox)) {
 639 #if DEBUG
 640     REJECTNIV0++;
 641 #endif
 642     return lastResult;
 643   }
 644   const Bnd_Array1OfBox& taBox=myBndComponents->Array1();
 645   //-- Rejection with the table of bits
 646   Standard_Boolean touch = Standard_True;
 647   touch = Standard_False;
 648   Standard_Real _Xmax,_Ymax,_Zmax;
 649   BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 650   Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
 651   _Xmax=Map->Xmax; _Ymax=Map->Ymax; _Zmax=Map->Zmax;
 652   theBox.Get(xmin, ymin, zmin, xmax, ymax, zmax);
 653   Standard_Integer i0,i1,j0,j1,k0,k1;
 654   if(xmin>Xmin) i0=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else  i0=1;
 655   if(ymin>Ymin) j0=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else  j0=1;
 656   if(zmin>Zmin) k0=(Standard_Integer )((zmin-Zmin)*deltaZ)-1; else  k0=1;
 657   if(xmax<_Xmax) i1=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else  i1=discrX;
 658   if(ymax<_Ymax) j1=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else  j1=discrY;
 659   if(zmax<_Zmax) k1=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else  k1=discrZ;
 660   if(i0<1) i0=1; else if(i0>discrX) i0=discrX;
 661   if(j0<1) j0=1; else if(j0>discrY) j0=discrY;
 662   if(k0<1) k0=1; else if(k0>discrZ) k0=discrZ;
 663
 664   if(i1<1) i1=1; else if(i1>discrX) i1=discrX;
 665   if(j1<1) j1=1; else if(j1>discrY) j1=discrY;
 666   if(k1<1) k1=1; else if(k1>discrZ) k1=discrZ;
 667   i0--; j0--; k0--; i1--; j1--; k1--;
 668   for(Standard_Integer i=i0; touch==Standard_False && i<=i1;i++) {
 669     for(Standard_Integer j=j0; touch==Standard_False && j<=j1;j++) {
 670       for(Standard_Integer k=k0;  touch==Standard_False && k<=k1;k++) {
 671         long unsigned t=Map->GrilleInteger(i,j,k);
 672         if(Map->Val(t)) {
 673           touch = Standard_True;
 674         }
 675       }
 676     }
 677   }
 678   //-- processing of systematically tested boxes
 679   if(Map->ToTest) {
 680     Standard_Integer l0 = taBox.Lower();
 681     Standard_Integer l1 = taBox.Upper();
 682     l1-=l0;
 683     for(Standard_Integer l=0; Map->ToTest[l]>=l0 && l<(l1-l0); l++) {
 684       if(Map->ToTest[l]>=l0) {
 685         if (!taBox(Map->ToTest[l]).IsOut(theBox)){
 686           lastResult.Append(Map->ToTest[l]);
 687         }
 688       }
 689     }
 690   }
 691   if(touch == Standard_False) {
 692 #if DEBUG
 693     REJECTNIV1++;
 694 #endif
 695 #if VERIFICATION
 696     VerifCompare(lastResult,theBox,taBox);
 697 #endif
 698     return(lastResult);
 699   }
 700   //------------------------
 701   //-- classic processing --
 702   //------------------------
 703   i0++; i1++; j0++; j1++; k0++; k1++;
 704   Crible.Clear();
 705   theFound=6;
 706   Standard_Integer cardY=0;
 707   for (lacase=j0; lacase<=j1; lacase++) {
 708     Standard_Integer nby=Map->NbAxisY(lacase);
 709     while(nby>0) {
 710       cardY++;
 711       Crible.Bind(Map->axisY[lacase][nby], 4);
 712       nby--;
 713     }
 714   }
 715   if (cardY==0) {
 716 #if VERIFICATION
 717     VerifCompare(lastResult,theBox,taBox);
 718 #endif
 719     return lastResult;
 720   }
 721   Standard_Integer cardZ=0;
 722   for (lacase=k0; lacase<=k1; lacase++) {
 723     Standard_Integer nbz=Map->NbAxisZ(lacase);
 724     while(nbz>0) {
 725       cardZ++;
 726       if (Crible.IsBound(Map->axisZ[lacase][nbz])) {
 727         Crible.Bind(Map->axisZ[lacase][nbz], 6);
 728       }
 729       nbz--;
 730     }
 731   }
 732   if (cardZ==0) {
 733 #if VERIFICATION
 734     VerifCompare(lastResult,theBox,taBox);
 735 #endif
 736     return lastResult;
 737   }
 738   for (lacase=i0; lacase<=i1; lacase++) {
 739     Standard_Integer nbx = Map->NbAxisX(lacase);
 740     while(nbx>0) {
 741       Standard_Integer x=Map->axisX[lacase][nbx];
 742       if (Crible.IsBound(x)) {
 743         if (Crible(x)==theFound) {
 744           Crible.UnBind(x);
 745           if (!taBox(x).IsOut(theBox)){
 746             lastResult.Append(x);
 747           }
 748         }
 749       }
 750       nbx--;
 751     }
 752   }
 753 #if VERIFICATION
 754   VerifCompare(lastResult,theBox,taBox);
 755 #endif
 756   return lastResult;
 757 }
 758 //=======================================================================
 759 //function : Dump
 760 //purpose  :
 761 //=======================================================================
 762
 763 void Bnd_BoundSortBox::Dump() const
 764 {}
 765 //=======================================================================
 766 //function : Compare
 767 //purpose  :
 768 //=======================================================================
 769 const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare(const gp_Pln& thePlane)
 770
 771 {
 772   lastResult.Clear();
 773   Standard_Integer i;
 774   const Bnd_Array1OfBox& boxes = myBndComponents->Array1();
 775   for (i = boxes.Lower(); i <= boxes.Upper(); i++) {
 776     if (!boxes(i).IsOut(thePlane))
 777       lastResult.Append(i);
 778   }
 779   return lastResult;
 780 }
 781 //=======================================================================
 782 void Bnd_BoundSortBox::Destroy() {
 783 #if DEBUG
 784   printf("\nDESTROY NBCOMPARE:%lu  REJECTNIV0:%lu  REJECTIONSOK=%lu  NBBOITES:%lu NBBOITESATESTER:%lu\n",
 785          NBCOMPARE,REJECTNIV0,REJECTNIV1,NBBOITES,NBBOITESATESTER);
 786 #endif
 787   BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
 788   if(Map) {
 789     delete Map;
 790     Map=0;
 791   }
 792 }
 793 //=======================================================================
 794