0029915: Porting to VC 2017 : Regressions in Modeling Algorithms on VC 2017
[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
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