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