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