projects / occt.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
0022312: Translation of french commentaries in OCCT files
[occt.git] / src / Bnd / Bnd_BoundSortBox.cxx
CommitLineData
7fd59977 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//--
0d969553
Y		 21//-- Initialisation: Bounding box BE
22//-- List of boxes Bi (Bi in BE)
7fd59977 23//--
0d969553 24//-- Compare(b) returns the list of Boxes Bi touched by b
7fd59977 25//--
26//--
0d969553 27//-- General principle:
7fd59977 28//--
0d969553
Y		 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 :
7fd59977 34//--
0d969553 35//-- Example :
7fd59977 36//--
0d969553
Y		 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 ... }
7fd59977 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//--
0d969553 49//-- Produce the same thing for axes Y and Z
7fd59977 50//--
0d969553 51//-- Obtain 3 tables (X,Y,Z) of lists of integers (indexes of boxes)
7fd59977 52//--
0d969553
Y		 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]
7fd59977 58//--
59//--
0d969553 60//-- Rejection of a higher level.
7fd59977 61//--
0d969553
Y		 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
7fd59977 68//--
0d969553
Y		 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.
7fd59977 72//--
0d969553
Y		 73//-- The indices of these boxes are located in table ToTest, and these
74// boxes are compared systematically with bt.
7fd59977 75//--
0d969553
Y		 76//-- Note : tables C replace here HArray1OfListOfInteger and other
77//-- structures that are sufficient for data adding but slow for reading.
7fd59977 78//--
0d969553
Y		 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.
7fd59977 82//--
83
84
85
86
87//=======================================================================
88#define VERIFICATION 0
89#define DEBUG 0
90#define DIMAXIS 20
91
92#if DEBUG
93static long unsigned APPELREJECTION=0L;
94static long unsigned REJECTNIV0=0L;
95static long unsigned REJECTNIV1=0L;
96static long unsigned NBCOMPARE=0L;
97static long unsigned NBBOITES=0L;
98static long unsigned NBBOITESATESTER=0L;
99#endif
100//=======================================================================
101static 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//=======================================================================
109static 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};
0d969553 115class BSB_T3Bits { //-- size is power of 2 > 4
7fd59977 116public:
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
135public:
136 BSB_T3Bits(int size);
137 ~BSB_T3Bits();
138
0d969553 139 //-- Part HArray1OfListOfInteger
7fd59977 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//=======================================================================
173BSB_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//=======================================================================
189BSB_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//=======================================================================
230void 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//=======================================================================
249void 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//=======================================================================
268void 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 {
0d969553 275 //-- it is required to extend
7fd59977 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//=======================================================================
293Bnd_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
307void 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//=======================================================================
327void 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//=======================================================================
354void 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 //------------------------------------------------------------
0d969553 429 //-- fill table with bits
7fd59977 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//=======================================================================
449void 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//=======================================================================
484void 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 //------------------------------------------------------------
0d969553 549 //-- fill table with bits
7fd59977 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
566static 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();
0d969553 576 char * qwe=new char [i1+1]; //-- $$$$$$$ ATTENTION IF I0 < 0
7fd59977 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) {
0d969553 590 printf("\nPb with box: %d ",i);
7fd59977 591 }
592 else if(qwe[i]==1) {
0d969553 593 printf("\n false rejection by %d \n",i);
7fd59977 594 }
595 }
596 delete [] qwe;
597 }
598}
599#endif
600//=======================================================================
601//function : Compare
602//purpose :
603//=======================================================================
604const 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();
0d969553 620 //-- Rejection with the table of bits
7fd59977 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 }
0d969553 654 //-- processing of systematically tested boxes
7fd59977 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 }
0d969553
Y		 676 //------------------------
677 //-- classic processing --
678 //------------------------
7fd59977 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
739void Bnd_BoundSortBox::Dump() const
740{}
741//=======================================================================
742//function : Compare
743//purpose :
744//=======================================================================
745const 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//=======================================================================
758void 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
Open CASCADE Technology repository