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
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
18 #include <Bnd_Array1OfBox.hxx>
19 #include <Bnd_BoundSortBox.hxx>
20 #include <Bnd_Box.hxx>
22 #include <Standard_MultiplyDefined.hxx>
23 #include <Standard_NullValue.hxx>
24 #include <TColStd_DataMapIteratorOfDataMapOfIntegerInteger.hxx>
25 #include <TColStd_ListIteratorOfListOfInteger.hxx>
28 //-- ================================================================================
32 //-- Initialisation: Bounding box BE
33 //-- List of boxes Bi (Bi in BE)
35 //-- Compare(b) returns the list of Boxes Bi touched by b
38 //-- General principle:
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 :
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 ... }
53 //-- X[.] | 1 2 3 4 .... N-1 N
54 //-- -----|-------------------------------------
60 //-- Produce the same thing for axes Y and Z
62 //-- Obtain 3 tables (X,Y,Z) of lists of integers (indexes of boxes)
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]
71 //-- Rejection of a higher level.
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
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
84 //-- The indices of these boxes are located in table ToTest, and these
85 // boxes are compared systematically with bt.
87 //-- Note : tables C replace here HArray1OfListOfInteger and other
88 //-- structures that are sufficient for data adding but slow for reading.
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
94 //=======================================================================
95 #define VERIFICATION 0
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;
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);
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};
123 //-- size is power of 2 > 4
128 Standard_Integer _DECAL;
129 Standard_Integer _DECAL2;
130 Standard_Integer _BASE;
131 Standard_Integer _BASEM1;
135 Standard_Integer ssize;
136 Standard_Real Xmin,Xmax,Ymin,Ymax,Zmin,Zmax;
139 Standard_Integer **axisX;
140 Standard_Integer **axisY;
141 Standard_Integer **axisZ;
143 Standard_Integer *ToTest;
146 BSB_T3Bits(int size);
149 //-- Part HArray1OfListOfInteger
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);
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]); }
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]); }
163 inline Standard_Integer GrilleInteger(Standard_Integer ix,
167 Standard_Integer tz = iz<<_DECAL2;
168 Standard_Integer ty = iy<<_DECAL;
169 Standard_Integer t = ix;
175 inline void IntegerGrille(Standard_Integer t,
176 Standard_Integer &ix,
177 Standard_Integer &iy,
178 Standard_Integer &iz)
180 ix = t & _BASEM1; t>>=_DECAL;
181 iy = t & _BASEM1; t>>=_DECAL;
187 BSB_T3Bits (const BSB_T3Bits&);
188 BSB_T3Bits& operator= (const BSB_T3Bits&);
191 //=======================================================================
192 BSB_T3Bits::~BSB_T3Bits()
194 if(p) { delete [] p; p=0; }
196 printf("\n BASE:%d\n",_BASE);
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; }
203 free(axisX); axisX=0;
204 free(axisY); axisY=0;
205 free(axisZ); axisZ=0;
206 if(ToTest) { delete [] ToTest; ToTest=0; }
208 //=======================================================================
209 BSB_T3Bits::BSB_T3Bits(int 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; }
223 long unsigned nb = (size*size*size)>>5;
226 p = new long unsigned [nb];
227 do { p[--nb]=0; } while(nb);
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 *));
233 axisX[0]=new Standard_Integer [_BASE+1];
234 axisY[0]=new Standard_Integer [_BASE+1];
235 axisZ[0]=new Standard_Integer [_BASE+1];
237 for( i=0; i<(_BASE+1); i++) {
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];
250 axisX[i][1]=axisY[i][1]=axisZ[i][1]=-1;
254 //=======================================================================
255 void BSB_T3Bits::AppendAxisZ(const Standard_Integer i,
256 const Standard_Integer v) {
257 Standard_Integer n = axisZ[0][i];
259 if(n<axisZ[i][0]) { axisZ[i][n]=v; }
261 Standard_Integer s=axisZ[i][0];
262 Standard_Integer *nt = new Standard_Integer [s+s];
264 for(Standard_Integer j=1;j<s;j++) {
273 //=======================================================================
274 void BSB_T3Bits::AppendAxisY(const Standard_Integer i,
275 const Standard_Integer v) {
276 Standard_Integer n = axisY[0][i];
278 if(n<axisY[i][0]) { axisY[i][n]=v; }
280 Standard_Integer s=axisY[i][0];
281 Standard_Integer *nt = new Standard_Integer [s+s];
283 for(Standard_Integer j=1;j<s;j++) {
292 //=======================================================================
293 void BSB_T3Bits::AppendAxisX(const Standard_Integer i,
294 const Standard_Integer v) {
295 Standard_Integer n = axisX[0][i];
298 if(n<axisX[i][0]) { axisX[i][n]=v; }
300 //-- it is required to extend
301 Standard_Integer s=axisX[i][0];
302 Standard_Integer *nt = new Standard_Integer [s+s];
304 for(Standard_Integer j=1;j<s;j++) {
313 //=======================================================================
314 //=======================================================================
315 //function : Bnd_BoundSortBox
317 //=======================================================================
318 Bnd_BoundSortBox::Bnd_BoundSortBox()
319 : discrX(0), discrY(0), discrZ(0)
323 NBCOMPARE=0L; NBBOITES=0L; NBBOITESATESTER=0L;
324 APPELREJECTION=0L; REJECTNIV0=0L; REJECTNIV1=0L;
327 //=======================================================================
328 //function : Initialize
330 //=======================================================================
332 void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
333 const Handle(Bnd_HArray1OfBox)& SetOfBox)
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())
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));
348 //=======================================================================
349 //function : Initialize
351 //=======================================================================
352 void Bnd_BoundSortBox::Initialize(const Handle(Bnd_HArray1OfBox)& SetOfBox)
354 myBndComponents=SetOfBox;
355 const Bnd_Array1OfBox & taBox=myBndComponents->Array1();
356 Standard_Integer i0,i1;
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));
366 Standard_Real Xmax, Ymax, Zmax;
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));
375 //=======================================================================
376 //function : SortBoxes
378 //=======================================================================
379 void Bnd_BoundSortBox::SortBoxes()
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();
391 BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
394 Map = new BSB_T3Bits(discrX);
395 TabBits = (void *)Map;
397 Standard_Integer s=i1-i0;
399 Map->ToTest = new Standard_Integer [s];
400 for(Standard_Integer i=0; i<s; i++) {
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;
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;
425 Standard_Integer n = (lastcaseX-firstcaseX);
426 if(n>(lastcaseY-firstcaseY)) n=lastcaseY-firstcaseY;
427 if(n>(lastcaseZ-firstcaseZ)) n=lastcaseZ-firstcaseZ;
436 for(Standard_Integer i=0; i<(i1-i0); i++) {
437 if(Map->ToTest[i]<i0) {
438 Map->ToTest[i]=labox;
444 for (lacaseX=firstcaseX; lacaseX<=lastcaseX; lacaseX++) {
445 Map->AppendAxisX(lacaseX,labox);
447 for (lacaseY=firstcaseY; lacaseY<=lastcaseY; lacaseY++) {
448 Map->AppendAxisY(lacaseY,labox);
450 for (lacaseZ=firstcaseZ; lacaseZ<=lastcaseZ; lacaseZ++) {
451 Map->AppendAxisZ(lacaseZ,labox);
453 //------------------------------------------------------------
454 //-- fill table with bits
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);
470 //=======================================================================
471 //function : Initialize
473 //=======================================================================
474 void Bnd_BoundSortBox::Initialize(const Bnd_Box& CompleteBox,
475 const Standard_Integer nbComponents)
477 Standard_NullValue_Raise_if (nbComponents <=0, "BoundSortBox nul!");
479 myBndComponents=new Bnd_HArray1OfBox(1,nbComponents);
481 //***>>> JCD - 04.08.2000 - Array initialization is missing...
483 myBndComponents->Init( emptyBox );
486 discrX=discrY=discrZ=ComputeSize(nbComponents);
487 Standard_Real Xmax, Ymax, Zmax;
489 if(CompleteBox.IsVoid())
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));
497 BSB_T3Bits* _Map = (BSB_T3Bits *)TabBits;
502 Map = new BSB_T3Bits(discrX);
503 TabBits = (void *)Map;
505 //=======================================================================
508 //=======================================================================
509 void Bnd_BoundSortBox::Add(const Bnd_Box& theBox,
510 const Standard_Integer boxIndex)
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;
524 Standard_Integer s=i1-i0;
526 Map->ToTest = new Standard_Integer [s];
527 for(Standard_Integer i=0; i<s; i++) {
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;
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;
557 for(Standard_Integer i=0; i<(i1-i0); i++) {
558 if(Map->ToTest[i]<i0) {
559 Map->ToTest[i]=boxIndex;
564 for (theGapY=firstGapY; theGapY<=lastGapY; theGapY++) {
565 Map->AppendAxisY(theGapY,boxIndex);
567 for (theGapX=firstGapX; theGapX<=lastGapX; theGapX++) {
568 Map->AppendAxisX(theGapX,boxIndex);
570 for (theGapZ=firstGapZ; theGapZ<=lastGapZ; theGapZ++) {
571 Map->AppendAxisZ(theGapZ,boxIndex);
573 //------------------------------------------------------------
574 //-- fill table with bits
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);
589 //=======================================================================
591 static void VerifCompare(const TColStd_ListOfInteger& lastResult,
592 const Bnd_Box& theBox,
593 const Bnd_Array1OfBox& taBox) {
594 static int Verif = 1;
598 Standard_Integer i0,i1;
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;
607 Standard_Integer labox;
608 for (labox=i0; labox<=i1; labox++) {
609 if (!taBox(labox).IsOut(theBox)) {
613 for(i=i0;i<=i1;i++) {
615 printf("\nPb with box: %d ",i);
618 printf("\n false rejection by %d \n",i);
625 //=======================================================================
628 //=======================================================================
629 const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare (const Bnd_Box& theBox)
632 Standard_Integer lacase ;
637 if (theBox.IsVoid()) return lastResult;
638 if (theBox.IsOut(myBox)) {
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;
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);
673 touch = Standard_True;
678 //-- processing of systematically tested boxes
680 Standard_Integer l0 = taBox.Lower();
681 Standard_Integer l1 = taBox.Upper();
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]);
691 if(touch == Standard_False) {
696 VerifCompare(lastResult,theBox,taBox);
700 //------------------------
701 //-- classic processing --
702 //------------------------
703 i0++; i1++; j0++; j1++; k0++; k1++;
706 Standard_Integer cardY=0;
707 for (lacase=j0; lacase<=j1; lacase++) {
708 Standard_Integer nby=Map->NbAxisY(lacase);
711 Crible.Bind(Map->axisY[lacase][nby], 4);
717 VerifCompare(lastResult,theBox,taBox);
721 Standard_Integer cardZ=0;
722 for (lacase=k0; lacase<=k1; lacase++) {
723 Standard_Integer nbz=Map->NbAxisZ(lacase);
726 if (Crible.IsBound(Map->axisZ[lacase][nbz])) {
727 Crible.Bind(Map->axisZ[lacase][nbz], 6);
734 VerifCompare(lastResult,theBox,taBox);
738 for (lacase=i0; lacase<=i1; lacase++) {
739 Standard_Integer nbx = Map->NbAxisX(lacase);
741 Standard_Integer x=Map->axisX[lacase][nbx];
742 if (Crible.IsBound(x)) {
743 if (Crible(x)==theFound) {
745 if (!taBox(x).IsOut(theBox)){
746 lastResult.Append(x);
754 VerifCompare(lastResult,theBox,taBox);
758 //=======================================================================
761 //=======================================================================
763 void Bnd_BoundSortBox::Dump() const
765 //=======================================================================
768 //=======================================================================
769 const TColStd_ListOfInteger& Bnd_BoundSortBox::Compare(const gp_Pln& thePlane)
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);
781 //=======================================================================
782 void Bnd_BoundSortBox::Destroy() {
784 printf("\nDESTROY NBCOMPARE:%lu REJECTNIV0:%lu REJECTIONSOK=%lu NBBOITES:%lu NBBOITESATESTER:%lu\n",
785 NBCOMPARE,REJECTNIV0,REJECTNIV1,NBBOITES,NBBOITESATESTER);
787 BSB_T3Bits* Map = (BSB_T3Bits *)TabBits;
793 //=======================================================================