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