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