projects / occt.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Integration of OCCT 6.5.0 from SVN
[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//--
21//-- Initialisation: Une boite englobante BE
22//-- Une liste de boites Bi (Bi dans BE)
23//--
24//-- Compare(b) renvoie la liste des Boites Bi touchees par b
25//--
26//--
27//-- Principe General:
28//--
29//-- 1) On discretise la boite BE en N*N*N voxels
30//-- Chaque boite Bi touche un certain nombre de voxels
31//-- Bi touche { Vijk avec i0<=i<=i1 ... k0<=k<=k1 }
32//-- 2) On projete sur chaque axe X,Y,Z les boites Bi
33//-- pour obtenir les structures suivantes :
34//--
35//-- Exemple :
36//--
37//-- la boite i1 touche les voxels { Vijk avec 1<=i<=N-1 ... }
38//-- la boite i2 touche les voxels { Vijk avec 2<=i<=3 ... }
39//-- la boite i3 touche les voxels { Vijk avec 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//-- On realise la meme chose pour les axes Y et Z
50//--
51//-- On obtient donc 3 tableaux (X,Y,Z) de listes d entiers (les indices des boites)
52//--
53//-- 3) Pour rechercher les boites en contact avec une boite bt
54//-- a) On cherche les voxels touches par bt -> i0bt,i1bt ... k0bt,k1bt
55//-- b) On cherche dans la liste Z les boites presentes dans les cases Z[k0bt ... k1bt]
56//-- c) On cherche parmi ces boites celles presentes dans les cases Y[j0bt ... j1bt]
57//-- d) et le resultat est l intersection du result. precedent avec X[i0bt ... i1bt]
58//--
59//--
60//-- Rejection de plus haut niveau.
61//--
62//-- *) On garde une representation a l aide d un tableau de bit des voxels de l espace BE
63//-- qui contiennenrt au moins une boite Bi.
64//-- *) Lorsque on teste une boite bt, on regarde tout d abord si cette boite comprend dans
65//-- le tableau de bit au moins un voxel occuppe.
66//-- Si un voxel occuppe est touche : pas de rejection
67//-- Sinon return
68//--
69//-- **) Une autre rejection a ete adoptee. Elle consiste a ne pas checher a placer dans les
70//-- structures ci-dessus (tableaux X,Y,Z et tableau de Bits) une boite Bi qui est grande
71//-- devant la boite englobante BE.
72//--
73//-- Les indices de ces boites sont placees dans un tableau ToTest, et on comparera
74//-- systematiquement ces boites avec bt.
75//--
76//--
77//--
78//--
79//-- Note : des tableaux C remplacent ici avantageusement les HArray1OfListOfInteger et autres
80//-- structures agreables lorsqu il faut ajouter des donnees mais lentes a la lecture.
81//--
82//-- Ici, on ajoute les donnees au debut (ds les fcts Initialize et SortBoxes) et ensuite,
83//-- on passe beaucoup de temps a parcourir les tableaux. Des structures lentes a l ecriture
84//-- mais rapides a la lecture sont donc meilleures.
85//--
86//--
87//--
88//--
89//--
90
91
92
93
94//=======================================================================
95#define VERIFICATION 0
96#define DEBUG 0
97#define DIMAXIS 20
98
99#if DEBUG
100static long unsigned APPELREJECTION=0L;
101static long unsigned REJECTNIV0=0L;
102static long unsigned REJECTNIV1=0L;
103static long unsigned NBCOMPARE=0L;
104static long unsigned NBBOITES=0L;
105static long unsigned NBBOITESATESTER=0L;
106#endif
107//=======================================================================
108static 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//=======================================================================
116static 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};
122class BSB_T3Bits { //-- size est une puissance de 2 > 4
123public:
124
125 Standard_Integer _DECAL;
126 Standard_Integer _DECAL2;
127 Standard_Integer _BASE;
128 Standard_Integer _BASEM1;
129
130 long unsigned ind;
131 long unsigned Isize;
132 Standard_Integer ssize;
133 Standard_Real Xmin,Xmax,Ymin,Ymax,Zmin,Zmax;
134
135 long unsigned *p;
136 Standard_Integer **axisX;
137 Standard_Integer **axisY;
138 Standard_Integer **axisZ;
139
140 Standard_Integer *ToTest;
141
142public:
143 BSB_T3Bits(int size);
144 ~BSB_T3Bits();
145
146 //-- Partie HArray1OfListOfInteger
147
148 void AppendAxisX(const Standard_Integer i,const Standard_Integer v);
149 void AppendAxisY(const Standard_Integer i,const Standard_Integer v);
150 void AppendAxisZ(const Standard_Integer i,const Standard_Integer v);
151
152 void Add(long unsigned t) { int o=t&31; int k=t>>5; p[k]|=_P2[o]; }
153 int Val(long unsigned t) { int o=t&31; int k=t>>5; return(p[k]&_P2[o]); }
154 void Raz(long unsigned t) { int o=t&31; int k=t>>5; p[k]&= ~(_P2[o]); }
155
156 Standard_Integer NbAxisX(const Standard_Integer i) { return(axisX[0][i]); }
157 Standard_Integer NbAxisY(const Standard_Integer i) { return(axisY[0][i]); }
158 Standard_Integer NbAxisZ(const Standard_Integer i) { return(axisZ[0][i]); }
159
160 inline Standard_Integer GrilleInteger(Standard_Integer ix,
161 Standard_Integer iy,
162 Standard_Integer iz) {
163 Standard_Integer tz = iz<<_DECAL2;
164 Standard_Integer ty = iy<<_DECAL;
165 Standard_Integer t = ix;
166 t|=ty; t|=tz;
167 return(t);
168 }
169
170 inline void IntegerGrille(Standard_Integer t,
171 Standard_Integer &ix,
172 Standard_Integer &iy,
173 Standard_Integer &iz) {
174 ix = t & _BASEM1; t>>=_DECAL;
175 iy = t & _BASEM1; t>>=_DECAL;
176 iz = t;
177 }
178};
179//=======================================================================
180BSB_T3Bits::~BSB_T3Bits() {
181 if(p) { delete [] p; p=0; }
182#if DEBUG
183 printf("\n BASE:%d\n",_BASE);
184#endif
185 for(Standard_Integer i=0; i<=ssize; i++) {
186 if(axisX[i]) { delete [] axisX[i]; axisX[i]=0; }
187 if(axisY[i]) { delete [] axisY[i]; axisY[i]=0; }
188 if(axisZ[i]) { delete [] axisZ[i]; axisZ[i]=0; }
189 }
190 free(axisX); axisX=0;
191 free(axisY); axisY=0;
192 free(axisZ); axisZ=0;
193 if(ToTest) { delete [] ToTest; ToTest=0; }
194}
195//=======================================================================
196BSB_T3Bits::BSB_T3Bits(int size) {
197 switch (size) {
198 case 128: { _DECAL=7; _DECAL2=14; _BASE=128; _BASEM1=127; break; }
199 case 64: { _DECAL=6; _DECAL2=12; _BASE= 64; _BASEM1= 63; break; }
200 case 32: { _DECAL=5; _DECAL2=10; _BASE= 32; _BASEM1= 31; break; }
201 case 16: { _DECAL=4; _DECAL2= 8; _BASE= 16; _BASEM1= 15; break; }
202 default : { _DECAL=3; _DECAL2= 6; _BASE= 8; _BASEM1= 7; break; }
203 }
204 Standard_Integer i ;
205 long unsigned nb = (size*size*size)>>5;
206 Isize = nb;
207 ssize = size;
208 p = new long unsigned [nb];
209 do { p[--nb]=0; } while(nb);
210
211 axisX = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
212 axisY = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
213 axisZ = (Standard_Integer **) malloc((size+1)*sizeof(Standard_Integer *));
214
215 axisX[0]=new Standard_Integer [_BASE+1];
216 axisY[0]=new Standard_Integer [_BASE+1];
217 axisZ[0]=new Standard_Integer [_BASE+1];
218
219 for( i=0; i<(_BASE+1); i++) {
220 axisX[0][i]=0;
221 axisY[0][i]=0;
222 axisZ[0][i]=0;
223 }
224
225 for(i=1; i<=size; i++) {
226 axisX[i] = new Standard_Integer[DIMAXIS];
227 axisY[i] = new Standard_Integer[DIMAXIS];
228 axisZ[i] = new Standard_Integer[DIMAXIS];
229 axisX[i][0]=DIMAXIS;
230 axisY[i][0]=DIMAXIS;
231 axisZ[i][0]=DIMAXIS;
232 axisX[i][1]=axisY[i][1]=axisZ[i][1]=-1;
233 }
234 ToTest=0;
235}
236//=======================================================================
237void BSB_T3Bits::AppendAxisZ(const Standard_Integer i,
238 const Standard_Integer v) {
239 Standard_Integer n = axisZ[0][i];
240 n++;
241 if(n<axisZ[i][0]) { axisZ[i][n]=v; }
242 else {
243 Standard_Integer s=axisZ[i][0];
244 Standard_Integer *nt = new Standard_Integer [s+s];
245 nt[0]=s+s;
246 for(Standard_Integer j=1;j<s;j++) {
247 nt[j]=axisZ[i][j];
248 }
249 nt[n]=v;
250 delete [] axisZ[i];
251 axisZ[i]=nt;
252 }
253 axisZ[0][i]=n;
254}
255//=======================================================================
256void BSB_T3Bits::AppendAxisY(const Standard_Integer i,
257 const Standard_Integer v) {
258 Standard_Integer n = axisY[0][i];
259 n++;
260 if(n<axisY[i][0]) { axisY[i][n]=v; }
261 else {
262 Standard_Integer s=axisY[i][0];
263 Standard_Integer *nt = new Standard_Integer [s+s];
264 nt[0]=s+s;
265 for(Standard_Integer j=1;j<s;j++) {
266 nt[j]=axisY[i][j];
267 }
268 nt[n]=v;
269 delete [] axisY[i];
270 axisY[i]=nt;
271 }
272 axisY[0][i]=n;
273}
274//=======================================================================
275void BSB_T3Bits::AppendAxisX(const Standard_Integer i,
276 const Standard_Integer v) {
277 Standard_Integer n = axisX[0][i];
278
279 n++;
280 if(n<axisX[i][0]) { axisX[i][n]=v; }
281 else {
282 //-- il faut etendre
283 Standard_Integer s=axisX[i][0];
284 Standard_Integer *nt = new Standard_Integer [s+s];
285 nt[0]=s+s;
286 for(Standard_Integer j=1;j<s;j++) {
287 nt[j]=axisX[i][j];
288 }
289 nt[n]=v;
290 delete [] axisX[i];
291 axisX[i]=nt;
292 }
293 axisX[0][i]=n;
294}
295//=======================================================================
296//=======================================================================
297//function : Bnd_BoundSortBox
298//purpose :
299//=======================================================================
300Bnd_BoundSortBox::Bnd_BoundSortBox()
301 : discrX(0), discrY(0), discrZ(0)
302{
303 TabBits=0;
304#if DEBUG
305 NBCOMPARE=0L; NBBOITES=0L; NBBOITESATESTER=0L;
306 APPELREJECTION=0L; REJECTNIV0=0L; REJECTNIV1=0L;
307#endif
308}
309//=======================================================================
310//function : Initialize
311//purpose :
312//=======================================================================
313
314void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
315 const Handle(Bnd_HArray1OfBox)& SetOfBox)
316{
317 myBox=CompleteBox;
318 myBndComponents=SetOfBox;
319 const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
320 discrX=discrY=discrZ=ComputeSize(taBox.Upper()-taBox.Lower());
321 Standard_Real Xmax, Ymax, Zmax;
322 if(CompleteBox.IsVoid())
323 return;
324 CompleteBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
325 deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
326 deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
327 deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
328 SortBoxes();
329}
330//=======================================================================
331//function : Initialize
332//purpose :
333//=======================================================================
334void Bnd_BoundSortBox::Initialize(const Handle(Bnd_HArray1OfBox)& SetOfBox)
335{
336 myBndComponents=SetOfBox;
337 const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
338 Standard_Integer i0,i1;
339 i0=taBox.Lower();
340 i1=taBox.Upper();
341 discrX=discrY=discrZ=ComputeSize(i1-i0);
342 Standard_Integer labox;
343 for (labox=i0; labox<=i1; labox++) {
344 if (!taBox(labox).IsVoid()) {
345 myBox.Add(taBox(labox));
346 }
347 }
348 Standard_Real Xmax, Ymax, Zmax;
349 if(myBox.IsVoid())
350 return;
351 myBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
352 deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
353 deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
354 deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
355 SortBoxes();
356}
357//=======================================================================
358//function : SortBoxes
359//purpose :
360//=======================================================================
361void Bnd_BoundSortBox::SortBoxes()
362{
363 Standard_Integer labox;
364 Standard_Integer lacaseX, firstcaseX, lastcaseX;
365 Standard_Integer lacaseY, firstcaseY, lastcaseY;
366 Standard_Integer lacaseZ, firstcaseZ, lastcaseZ;
367 Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
368 const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
369 Standard_Integer i0=taBox.Lower();
370 Standard_Integer i1=taBox.Upper();
371 BSB_T3Bits* Map=0;
372 if(TabBits) {
373 BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
374 delete _Map;
375 }
376 Map = new BSB_T3Bits(discrX);
377 TabBits = (void *)Map;
378 if(Map->ToTest==0) {
379 Standard_Integer s=i1-i0;
380 if(s<2) s=2;
381 Map->ToTest = new Standard_Integer [s];
382 for(Standard_Integer i=0; i<s; i++) {
383 Map->ToTest[i]=i0-1;
384 }
385 }
386 Standard_Real _Xmax,_Xmin,_Ymax,_Ymin,_Zmin,_Zmax;
387 myBox.Get(_Xmin,_Ymin,_Zmin,_Xmax,_Ymax,_Zmax);
388 Map->Xmax=_Xmax; Map->Ymax=_Ymax; Map->Zmax=_Zmax;
389 Map->Xmin=_Xmin; Map->Ymin=_Ymin; Map->Zmin=_Zmin;
390 for (labox=i0; labox<=i1; labox++) {
391 if (!taBox(labox).IsVoid()) {
392 taBox(labox).Get(xmin, ymin, zmin, xmax, ymax, zmax);
393 if(xmin>Xmin) firstcaseX=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else firstcaseX=1;
394 if(ymin>Ymin) firstcaseY=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else firstcaseY=1;
395 if(zmin>Zmin) firstcaseZ=(Standard_Integer )((zmin-Zmin)*deltaZ)-1; else firstcaseZ=1;
396 if(xmax<_Xmax) lastcaseX=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else lastcaseX=discrX;
397 if(ymax<_Ymax) lastcaseY=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else lastcaseY=discrY;
398 if(zmax<_Zmax) lastcaseZ=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else lastcaseZ=discrZ;
399 if(firstcaseX<1) firstcaseX=1; else if(firstcaseX>discrX) firstcaseX=discrX;
400 if(firstcaseY<1) firstcaseY=1; else if(firstcaseY>discrY) firstcaseY=discrY;
401 if(firstcaseZ<1) firstcaseZ=1; else if(firstcaseZ>discrZ) firstcaseZ=discrZ;
402
403 if(lastcaseX<1) lastcaseX=1; else if(lastcaseX>discrX) lastcaseX=discrX;
404 if(lastcaseY<1) lastcaseY=1; else if(lastcaseY>discrY) lastcaseY=discrY;
405 if(lastcaseZ<1) lastcaseZ=1; else if(lastcaseZ>discrZ) lastcaseZ=discrZ;
406
407 Standard_Integer n = (lastcaseX-firstcaseX);
408 if(n>(lastcaseY-firstcaseY)) n=lastcaseY-firstcaseY;
409 if(n>(lastcaseZ-firstcaseZ)) n=lastcaseZ-firstcaseZ;
410#if DEBUG
411 NBBOITES++;
412#endif
413 n<<=2;
414 if(n>discrX) {
415#if DEBUG
416 NBBOITESATESTER++;
417#endif
418 for(Standard_Integer i=0; i<(i1-i0); i++) {
419 if(Map->ToTest[i]<i0) {
420 Map->ToTest[i]=labox;
421 break;
422 }
423 }
424 }
425 else {
426 for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
427 Map->AppendAxisX(lacaseX,labox);
428 }
429 for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
430 Map->AppendAxisY(lacaseY,labox);
431 }
432 for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
433 Map->AppendAxisZ(lacaseZ,labox);
434 }
435 //------------------------------------------------------------
436 //-- remplissage du tableau de bits
437 //--
438 if(Map) {
439 for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
440 for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
441 for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
442 long unsigned t=Map->GrilleInteger(lacaseX-1,lacaseY-1,lacaseZ-1);
443 Map->Add(t);
444 }
445 }
446 }
447 }
448 }
449 }
450 }
451}
452//=======================================================================
453//function : Initialize
454//purpose :
455//=======================================================================
456void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
457 const Standard_Integer nbComponents)
458{
459 Standard_NullValue_Raise_if (nbComponents <=0, "BoundSortBox nul!");
460 myBox=CompleteBox;
461 myBndComponents=new Bnd_HArray1OfBox(1,nbComponents);
462
463 //***>>> JCD - 04.08.2000 - Array initialization is missing...
464 Bnd_Box emptyBox;
465 myBndComponents->Init( emptyBox );
466 //***<<< JCD - End
467
468 discrX=discrY=discrZ=ComputeSize(nbComponents);
469 Standard_Real Xmax, Ymax, Zmax;
470
471 if(CompleteBox.IsVoid())
472 return;
473 CompleteBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
474 myBox.Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
475 deltaX = (Xmax-Xmin == 0. ? 0. : discrX/(Xmax-Xmin));
476 deltaY = (Ymax-Ymin == 0. ? 0. : discrY/(Ymax-Ymin));
477 deltaZ = (Zmax-Zmin == 0. ? 0. : discrZ/(Zmax-Zmin));
478 if(TabBits) {
479 BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
480 delete _Map;
481 TabBits=0;
482 }
483 BSB_T3Bits* Map=0;
484 Map = new BSB_T3Bits(discrX);
485 TabBits = (void *)Map;
486}
487//=======================================================================
488//function : Add
489//purpose :
490//=======================================================================
491void Bnd_BoundSortBox::Add(const Bnd_Box& theBox,
492 const Standard_Integer boxIndex)
493{
494 Standard_MultiplyDefined_Raise_if (!(myBndComponents->Value(boxIndex).IsVoid()), " This box is already defined !");
495 if (!theBox.IsVoid()) {
496 Standard_Integer i0=myBndComponents->Lower();
497 Standard_Integer i1=myBndComponents->Upper();
498 Standard_Integer theGapX, firstGapX , lastGapX;
499 Standard_Integer theGapY, firstGapY , lastGapY;
500 Standard_Integer theGapZ, firstGapZ , lastGapZ;
501 Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
502 myBndComponents->SetValue(boxIndex, theBox);
503 theBox.Get(xmin, ymin, zmin, xmax, ymax, zmax);
504 BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
505 if(Map->ToTest==0) {
506 Standard_Integer s=i1-i0;
507 if(s<2) s=2;
508 Map->ToTest = new Standard_Integer [s];
509 for(Standard_Integer i=0; i<s; i++) {
510 Map->ToTest[i]=i0-1;
511 }
512 }
513 Standard_Real _Xmax,_Ymax,_Zmax;
514 _Xmax=Map->Xmax; _Ymax=Map->Ymax; _Zmax=Map->Zmax;
515 if(xmin>Xmin) firstGapX=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else firstGapX=1;
516 if(ymin>Ymin) firstGapY=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else firstGapY=1;
517 if(zmin>Zmin) firstGapZ=(Standard_Integer ) ((zmin-Zmin)*deltaZ)-1; else firstGapZ=1;
518 if(xmax<_Xmax) lastGapX=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else lastGapX=discrX;
519 if(ymax<_Ymax) lastGapY=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else lastGapY=discrY;
520 if(zmax<_Zmax) lastGapZ=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else lastGapZ=discrZ;
521 if(firstGapX<1) firstGapX=1; else if(firstGapX>discrX) firstGapX=discrX;
522 if(firstGapY<1) firstGapY=1; else if(firstGapY>discrY) firstGapY=discrY;
523 if(firstGapZ<1) firstGapZ=1; else if(firstGapZ>discrZ) firstGapZ=discrZ;
524
525 if(lastGapX<1) lastGapX=1; else if(lastGapX>discrX) lastGapX=discrX;
526 if(lastGapY<1) lastGapY=1; else if(lastGapY>discrY) lastGapY=discrY;
527 if(lastGapZ<1) lastGapZ=1; else if(lastGapZ>discrZ) lastGapZ=discrZ;
528 Standard_Integer n = (lastGapX-firstGapX);
529 if(n>(lastGapY-firstGapY)) n=lastGapY-firstGapY;
530 if(n>(lastGapZ-firstGapZ)) n=lastGapZ-firstGapZ;
531 n<<=2;
532#if DEBUG
533 NBBOITES++;
534#endif
535 if(n>discrX) {
536#if DEBUG
537 NBBOITESATESTER++;
538#endif
539 for(Standard_Integer i=0; i<(i1-i0); i++) {
540 if(Map->ToTest[i]<i0) {
541 Map->ToTest[i]=boxIndex;
542 break;
543 }
544 }
545 }
546 for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
547 Map->AppendAxisY(theGapY,boxIndex);
548 }
549 for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
550 Map->AppendAxisX(theGapX,boxIndex);
551 }
552 for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
553 Map->AppendAxisZ(theGapZ,boxIndex);
554 }
555 //------------------------------------------------------------
556 //-- remplissage du tableau de bits
557 //--
558 if(TabBits) {
559 Map=(BSB_T3Bits *)TabBits;
560 for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
561 for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
562 for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
563 long unsigned t=Map->GrilleInteger(theGapX-1,theGapY-1,theGapZ-1);
564 Map->Add(t);
565 }
566 }
567 }
568 }
569 }
570}
571//=======================================================================
572#if VERIFICATION
573static void VerifCompare(const TColStd_ListOfInteger& lastResult,
574 const Bnd_Box& theBox,
575 const Bnd_Array1OfBox& taBox) {
576 static int Verif = 1;
577 Standard_Integer i ;
578
579 if(Verif) {
580 Standard_Integer i0,i1;
581 i0=taBox.Lower();
582 i1=taBox.Upper();
583 char * qwe=new char [i1+1]; //-- $$$$$$$ ATTENTION SI I0 < 0
584 for( i=i0; i<=i1; i++) qwe[i]='\0';
585 TColStd_ListIteratorOfListOfInteger theList(lastResult);
586 for (; theList.More(); theList.Next()) {
587 qwe[theList.Value()]=(char)1;
588 }
589 Standard_Integer labox;
590 for (labox=i0; labox<=i1; labox++) {
591 if (!taBox(labox).IsOut(theBox)) {
592 qwe[labox]+=2;
593 }
594 }
595 for(i=i0;i<=i1;i++) {
596 if(qwe[i]==2) {
597 printf("\nPb avec boite: %d ",i);
598 }
599 else if(qwe[i]==1) {
600 printf("\n fausse rejection en %d \n",i);
601 }
602 }
603 delete [] qwe;
604 }
605}
606#endif
607//=======================================================================
608//function : Compare
609//purpose :
610//=======================================================================
611const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare (const Bnd_Box& theBox)
612
613{
614 Standard_Integer lacase ;
615#if DEBUG
616 NBCOMPARE++;
617#endif
618 lastResult.Clear();
619 if (theBox.IsVoid()) return lastResult;
620 if (theBox.IsOut(myBox)) {
621#if DEBUG
622 REJECTNIV0++;
623#endif
624 return lastResult;
625 }
626 const Bnd_Array1OfBox& taBox=myBndComponents->Array1();
627 //-- Rejection avec le tableau de bits
628 Standard_Boolean touch = Standard_True;
629 touch = Standard_False;
630 Standard_Real _Xmin,_Ymin,_Zmin,_Xmax,_Ymax,_Zmax;
631 BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
632 Standard_Real xmin, ymin, zmin, xmax, ymax, zmax;
633 _Xmax=Map->Xmax; _Ymax=Map->Ymax; _Zmax=Map->Zmax;
634 _Xmin=Map->Xmin; _Ymin=Map->Ymin; _Zmin=Map->Zmin;
635 theBox.Get(xmin, ymin, zmin, xmax, ymax, zmax);
636 Standard_Integer i0,i1,j0,j1,k0,k1;
637 if(xmin>Xmin) i0=(Standard_Integer )((xmin-Xmin)*deltaX)-1; else i0=1;
638 if(ymin>Ymin) j0=(Standard_Integer )((ymin-Ymin)*deltaY)-1; else j0=1;
639 if(zmin>Zmin) k0=(Standard_Integer )((zmin-Zmin)*deltaZ)-1; else k0=1;
640 if(xmax<_Xmax) i1=(Standard_Integer )((xmax-Xmin)*deltaX)+1; else i1=discrX;
641 if(ymax<_Ymax) j1=(Standard_Integer )((ymax-Ymin)*deltaY)+1; else j1=discrY;
642 if(zmax<_Zmax) k1=(Standard_Integer )((zmax-Zmin)*deltaZ)+1; else k1=discrZ;
643 if(i0<1) i0=1; else if(i0>discrX) i0=discrX;
644 if(j0<1) j0=1; else if(j0>discrY) j0=discrY;
645 if(k0<1) k0=1; else if(k0>discrZ) k0=discrZ;
646
647 if(i1<1) i1=1; else if(i1>discrX) i1=discrX;
648 if(j1<1) j1=1; else if(j1>discrY) j1=discrY;
649 if(k1<1) k1=1; else if(k1>discrZ) k1=discrZ;
650 i0--; j0--; k0--; i1--; j1--; k1--;
651 for(Standard_Integer i=i0; touch==Standard_False && i<=i1;i++) {
652 for(Standard_Integer j=j0; touch==Standard_False && j<=j1;j++) {
653 for(Standard_Integer k=k0; touch==Standard_False && k<=k1;k++) {
654 long unsigned t=Map->GrilleInteger(i,j,k);
655 if(Map->Val(t)) {
656 touch = Standard_True;
657 }
658 }
659 }
660 }
661 //-- traitement des boites a tester systematiquement
662 if(Map->ToTest) {
663 Standard_Integer l0 = taBox.Lower();
664 Standard_Integer l1 = taBox.Upper();
665 l1-=l0;
666 for(Standard_Integer l=0; Map->ToTest[l]>=l0 && l<(l1-l0); l++) {
667 if(Map->ToTest[l]>=l0) {
668 if (!taBox(Map->ToTest[l]).IsOut(theBox)){
669 lastResult.Append(Map->ToTest[l]);
670 }
671 }
672 }
673 }
674 if(touch == Standard_False) {
675#if DEBUG
676 REJECTNIV1++;
677#endif
678#if VERIFICATION
679 VerifCompare(lastResult,theBox,taBox);
680#endif
681 return(lastResult);
682 }
683 //-------------------------
684 //-- traitement classique
685 //-------------------------
686 i0++; i1++; j0++; j1++; k0++; k1++;
687 Crible.Clear();
688 theFound=6;
689 Standard_Integer cardY=0;
690 for (lacase=j0; lacase<=j1; lacase++) {
691 Standard_Integer nby=Map->NbAxisY(lacase);
692 while(nby>0) {
693 cardY++;
694 Crible.Bind(Map->axisY[lacase][nby], 4);
695 nby--;
696 }
697 }
698 if (cardY==0) {
699#if VERIFICATION
700 VerifCompare(lastResult,theBox,taBox);
701#endif
702 return lastResult;
703 }
704 Standard_Integer cardZ=0;
705 for (lacase=k0; lacase<=k1; lacase++) {
706 Standard_Integer nbz=Map->NbAxisZ(lacase);
707 while(nbz>0) {
708 cardZ++;
709 if (Crible.IsBound(Map->axisZ[lacase][nbz])) {
710 Crible.Bind(Map->axisZ[lacase][nbz], 6);
711 }
712 nbz--;
713 }
714 }
715 if (cardZ==0) {
716#if VERIFICATION
717 VerifCompare(lastResult,theBox,taBox);
718#endif
719 return lastResult;
720 }
721 for (lacase=i0; lacase<=i1; lacase++) {
722 Standard_Integer nbx = Map->NbAxisX(lacase);
723 while(nbx>0) {
724 Standard_Integer x=Map->axisX[lacase][nbx];
725 if (Crible.IsBound(x)) {
726 if (Crible(x)==theFound) {
727 Crible.UnBind(x);
728 if (!taBox(x).IsOut(theBox)){
729 lastResult.Append(x);
730 }
731 }
732 }
733 nbx--;
734 }
735 }
736#if VERIFICATION
737 VerifCompare(lastResult,theBox,taBox);
738#endif
739 return lastResult;
740}
741//=======================================================================
742//function : Dump
743//purpose :
744//=======================================================================
745
746void Bnd_BoundSortBox::Dump() const
747{}
748//=======================================================================
749//function : Compare
750//purpose :
751//=======================================================================
752const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare(const gp_Pln& thePlane)
753
754{
755 lastResult.Clear();
756 Standard_Integer i;
757 const Bnd_Array1OfBox& boxes = myBndComponents->Array1();
758 for (i = boxes.Lower(); i <= boxes.Upper(); i++) {
759 if (!boxes(i).IsOut(thePlane))
760 lastResult.Append(i);
761 }
762 return lastResult;
763}
764//=======================================================================
765void Bnd_BoundSortBox::Destroy() {
766#if DEBUG
767 printf("\nDESTROY NBCOMPARE:%lu REJECTNIV0:%lu REJECTIONSOK=%lu NBBOITES:%lu NBBOITESATESTER:%lu\n",
768 NBCOMPARE,REJECTNIV0,REJECTNIV1,NBBOITES,NBBOITESATESTER);
769#endif
770 BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
771 if(Map) {
772 delete Map;
773 Map=0;
774 }
775}
776//=======================================================================
777
Open CASCADE Technology repository