1 /*
2 * Copyright (C) 1998, 2000-2007, 2010, 2011, 2012, 2013 SINTEF ICT,
3 * Applied Mathematics, Norway.
4 *
5 * Contact information: E-mail: tor.dokken@sintef.no
6 * SINTEF ICT, Department of Applied Mathematics,
7 * P.O. Box 124 Blindern,
8 * 0314 Oslo, Norway.
9 *
10 * This file is part of SISL.
11 *
12 * SISL is free software: you can redistribute it and/or modify
13 * it under the terms of the GNU Affero General Public License as
14 * published by the Free Software Foundation, either version 3 of the
15 * License, or (at your option) any later version.
16 *
17 * SISL is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Affero General Public License for more details.
21 *
22 * You should have received a copy of the GNU Affero General Public
23 * License along with SISL. If not, see
24 * <http://www.gnu.org/licenses/>.
25 *
26 * In accordance with Section 7(b) of the GNU Affero General Public
27 * License, a covered work must retain the producer line in every data
28 * file that is created or manipulated using SISL.
29 *
30 * Other Usage
31 * You can be released from the requirements of the license by purchasing
32 * a commercial license. Buying such a license is mandatory as soon as you
33 * develop commercial activities involving the SISL library without
34 * disclosing the source code of your own applications.
35 *
36 * This file may be used in accordance with the terms contained in a
37 * written agreement between you and SINTEF ICT.
38 */
39
40 #include "sisl-copyright.h"
41
42 /*
43 *
44 * $Id: sh1790.c,v 1.2 2001-03-19 15:59:05 afr Exp $
45 *
46 */
47
48
49 #define SH1790
50
51 #include "sislP.h"
52
53 #if defined(SISLNEEDPROTOTYPES)
sh1790(SISLObject * po1,SISLObject * po2,int itype,double aepsge,int * jstat)54 void sh1790(SISLObject *po1,SISLObject *po2,int itype,
55 double aepsge,int *jstat)
56 #else
57 void sh1790(po1,po2,itype,aepsge,jstat)
58 SISLObject *po1;
59 SISLObject *po2;
60 int itype;
61 double aepsge;
62 int *jstat;
63 #endif
64 /*
65 *********************************************************************
66 *
67 *********************************************************************
68 *
69 * PURPOSE : Perform a box-test on the two object given by
70 * po1 and po2 and check if the boxes overlap.
71 *
72 *
73 *
74 * INPUT : po1 - First object.
75 * po2 - Second object.
76 * itype - Kind of box to make.
77 * = 0 : Do not expand box.
78 * = 1 : Make a totally expanded box.
79 * = 2 : Make a box expanded in the inner of the
80 * object, and reduced along the edges/endpoints.
81 * If itype>=10, it is interpreted as itype-10. This
82 * code is present to reduce the number of sides in
83 * the box to be made.
84 * aepsge - Geometry resolution.
85 *
86 *
87 * OUTPUT : jstat - status messages
88 * = 5 : Danger of shadow area in point
89 * intersection.
90 * = 4 : One box is collapsed into a point.
91 * = 3 : Both boxes inside geometry resolution.
92 * = 2 : Overlap as closed sets only.
93 * = 1 : Overlap as open sets.
94 * = 0 : No overlap.
95 * < 0 : error
96 *
97 *
98 * METHOD :
99 *
100 *
101 * REFERENCES :
102 *
103 *-
104 * CALLS :
105 *
106 * WRITTEN BY : Arne Laksaa, SI, 89-03.
107 * Arne Laksaa, SI, 89-07.
108 * REWISED BY : Vibeke Skytt, SI, 91-01. Tolerance dependant boxes.
109 * CORRECTED BY: UJK and ALA, SI, 91-08. Removed edge test
110 * REWISED BY : VSK, SI, 92-10. Transform tolerance to other object when a point
111 * is included. Special check on "shadow area",
112 * which may arise in point-object intersection
113 * where the point lies outside the reduced box
114 * of the other object, but still within a
115 * distance less than the tolerance from the
116 * object itself (in particular curve). This
117 * is possible near the endpoints/edges of the
118 * other object.
119 *********************************************************************
120 */
121 {
122 int kstat = 0; /* Local status error. */
123 int kpos = 0; /* Position of error. */
124 int ktype = itype%10; /* Type of box to make. */
125 int kant; /* Number of sides in all boxes. */
126 int kdim1,kdim2; /* Dimension of space. */
127 int ki,kj=0; /* Counters. */
128 int kpttest=0; /* Indicates wether one object is a point and
129 the geometry has dimension greater than 1.
130 In that case the boundaries of the box is
131 placed further out in the min- and max-arrays. */
132 int kshadow = 0; /* Indicates if there is a risk of a shadow areas */
133 int kbez = 0; /* Indicates if any object is a bezier object. */
134 double tdist; /* Distance between boxes. */
135 double teps1; /* To be used in 1D. */
136 double teps2; /* Two times aepsge if expanded box. */
137 double tepsge = aepsge; /* Tolerance to be used locally. In 1D
138 tepsge=2*aepsge since the point is not
139 expended. */
140 double t1,t2,t3,t4; /* Help variables. */
141 double t01,t02,t03,t04; /* Help variables. */
142 double *tmin1,*tmax1; /* Smallest and larges value of the vertices of
143 first object in each box in all dimension. */
144 double *tmin2,*tmax2; /* Smallest and larges value of the vertices of
145 second object in each box in all dimension.*/
146
147 /* Set local tolerance. */
148
149 teps2 = (ktype == 0) ? aepsge : (double)2.0*aepsge;
150
151 /* Check if one object is a point. */
152
153 if (po1->iobj == SISLPOINT) kdim1 = po1->p1->idim;
154 else if (po1->iobj == SISLCURVE) kdim1 = po1->c1->idim;
155 else if (po1->iobj == SISLSURFACE) kdim1 = po1->s1->idim;
156
157 if (kdim1 == 1)
158 {
159 if (ktype != 0) teps2 = (double)3.0*aepsge;
160 teps1 = (ktype == 0) ? aepsge : aepsge+aepsge;
161
162 if (po1->iobj == SISLPOINT || po2->iobj == SISLPOINT)
163 tepsge += aepsge;
164 }
165 else
166 {
167 teps1 = DZERO;
168 if (po1->iobj == SISLPOINT || po2->iobj == SISLPOINT)
169 kpttest = 1;
170 }
171
172
173 /* Compute the box of the first object. */
174
175 sh1992(po1,itype,tepsge,&kstat);
176 if (kstat < 0) goto error;
177
178 /* VSK. 06.93. Adjust microbox tolerance in bezier case. */
179
180 if (ktype != 0 && kstat == 1) kbez = 1;
181
182 /* Set pointers to box boundaries. */
183
184 if (po1->iobj == SISLPOINT)
185 {
186 tmin1 = po1->p1->pbox->e2min[ktype];
187 tmax1 = po1->p1->pbox->e2max[ktype];
188 }
189 else if (po1->iobj == SISLCURVE)
190 {
191 tmin1 = po1->c1->pbox->e2min[ktype];
192 tmax1 = po1->c1->pbox->e2max[ktype];
193 }
194 else if (po1->iobj == SISLSURFACE)
195 {
196 tmin1 = po1->s1->pbox->e2min[ktype];
197 tmax1 = po1->s1->pbox->e2max[ktype];
198 }
199 else goto err121;
200
201 /* Make requested box. */
202
203 sh1992(po2,itype,tepsge,&kstat);
204 if (kstat < 0) goto error;
205
206 /* VSK. 06.93. Adjust microbox tolerance in bezier case. */
207
208 if (ktype != 0 && kstat == 1) kbez += 1;
209 if (kdim1 == 1 && kbez > 0) teps2 -= (double)2.0*aepsge;
210 else if (kbez > 0) teps2 -= aepsge;
211 if (kbez) teps1 = aepsge;
212
213 /* Set pointers to box boundaries. */
214
215 if (po2->iobj == SISLPOINT)
216 {
217 tmin2 = po2->p1->pbox->e2min[ktype];
218 tmax2 = po2->p1->pbox->e2max[ktype];
219 kdim2 = po2->p1->idim;
220 }
221 else if (po2->iobj == SISLCURVE)
222 {
223 tmin2 = po2->c1->pbox->e2min[ktype];
224 tmax2 = po2->c1->pbox->e2max[ktype];
225 kdim2 = po2->c1->idim;
226 }
227 else if (po2->iobj == SISLSURFACE)
228 {
229 tmin2 = po2->s1->pbox->e2min[ktype];
230 tmax2 = po2->s1->pbox->e2max[ktype];
231 kdim2 = po2->s1->idim;
232 }
233 else goto err121;
234
235 /* Check dimension. */
236
237 if (kdim1 != kdim2 ) goto err106;
238 else
239 if (kdim1 < 1 ) goto err105;
240
241
242 /* Compute total number of SISLbox edges. */
243
244 if (itype < 10 && kdim1 == 3) kant = 9;
245 else
246 if (itype < 10 && kdim1 == 2) kant = 4;
247 else kant = kdim1;
248
249
250 /* For each dimension in all boxes perform box-test. First check
251 that we point on the right place in the min- and max-arrays. */
252
253 if (kpttest)
254 {
255 tmin1 += kant;
256 tmin2 += kant;
257 tmax1 += kant;
258 tmax2 += kant;
259 }
260
261 for (ki=0; ki<kant; ki++,tmin1++,tmax1++,tmin2++,tmax2++)
262 {
263 /* Sorting: t1-t2 The SISLbox with largest max value.
264 t3-t4 The other box. */
265
266 if (*tmax1 > *tmax2)
267 {
268 t1 = *tmax1; t01 = *(tmax1 - kant*kpttest);
269 t2 = *tmin1; t02 = *(tmin1 - kant*kpttest);
270 t3 = *tmax2; t03 = *(tmax2 - kant*kpttest);
271 t4 = *tmin2; t04 = *(tmin2 - kant*kpttest);
272 }
273 else
274 {
275 t1 = *tmax2; t01 = *(tmax2 - kant*kpttest);
276 t2 = *tmin2; t02 = *(tmin2 - kant*kpttest);
277 t3 = *tmax1; t03 = *(tmax1 - kant*kpttest);
278 t4 = *tmin1; t04 = *(tmin1 - kant*kpttest);
279 }
280 tdist = t2 - t3;
281
282 /* Use non-expanded boxes when testing if minibox is possible. */
283
284 if (t01 - min(t02,t04) <= teps2)
285 kj++; /* Minibox is possible. */
286 else if (kdim1 == 1 && t01-t04 <= teps1 && t03-t02 <= teps1)
287 kj++; /* Minibox is possible. */
288 else if (t3 < t2 && (tdist > teps2 || !kpttest))
289 {
290 *jstat = 0; /* No overlap. */
291 goto out;
292 }
293 else if (t3 < t2)
294 kshadow = 1; /* Danger of shadow area. */
295
296 /* UJK and ALA, 91-08: The tolerance is now
297 incorporated in the box.
298 else if (kdim1 != 1 && t3 - t2 < tepsge && t3 - t4 > teps2 &&
299 t1 - t2 > teps2)
300 {
301 *jstat = 2; Only edge touching possible.
302 goto degenerate;
303 }
304 else if ( kdim1 == 1 && (t1 - t4 < tepsge || t3 - t2 < tepsge))
305 {
306 *jstat = 2; Only edge touching possible.
307 goto out;
308 } */
309
310 /* else possible overlap. */
311 }
312
313 if (kj == kant)
314 *jstat = 3; /* Minibox found. */
315 else if (kshadow)
316 *jstat = 5; /* Danger of shadow area. */
317 else
318 *jstat = 1; /* Overlap. */
319
320
321 /* Box-test performed. */
322
323 /* degenerate: */
324 /* Test if one of the objects has collapsed. Use non-expanded box. */
325 if (kdim1 != 1 && po1->iobj > SISLPOINT)
326 {
327 if (po1->iobj == SISLCURVE)
328 {
329 tmin1 = po1->c1->pbox->e2min[ktype];
330 tmax1 = po1->c1->pbox->e2max[ktype];
331 }
332
333 else if (po1->iobj == SISLSURFACE)
334 {
335 tmin1 = po1->s1->pbox->e2min[ktype];
336 tmax1 = po1->s1->pbox->e2max[ktype];
337 }
338
339 /* Make sure that we are correct place in the min- and max-arrays. */
340
341 if (kpttest)
342 {
343 tmin1 += kant;
344 tmax1 += kant;
345 }
346
347 for(ki=0;ki<kdim1;ki++,tmin1++,tmax1++)
348 if (fabs(tmax1[0]-tmin1[0]) > tepsge) break;
349
350 if (ki == kdim1+1)
351 {
352 *jstat = 4;
353 goto out;
354 }
355 }
356
357 if (kdim1 != 1 && po2->iobj > SISLPOINT)
358 {
359 if (po2->iobj == SISLCURVE)
360 {
361 tmin1 = po2->c1->pbox->e2min[ktype];
362 tmax1 = po2->c1->pbox->e2max[ktype];
363 }
364
365 else if (po2->iobj == SISLSURFACE)
366 {
367 tmin1 = po2->s1->pbox->e2min[ktype];
368 tmax1 = po2->s1->pbox->e2max[ktype];
369 }
370
371 /* Make sure that we are correct place in the min- and max-arrays. */
372
373 if (kpttest)
374 {
375 tmin1 += kant;
376 tmax1 += kant;
377 }
378
379 for(ki=0;ki<kdim1;ki++,tmin1++,tmax1++)
380 if (fabs(tmax1[0]-tmin1[0]) > tepsge) break;
381
382 if (ki == kdim1+1)
383 {
384 *jstat = 4;
385 goto out;
386 }
387 }
388 goto out;
389
390 /* Dimensions conflicting. */
391
392 err106: *jstat = -106;
393 s6err("sh1790",*jstat,kpos);
394 goto out;
395
396 /* Dimensions less than one. */
397
398 err105: *jstat = -105;
399 s6err("sh1790",*jstat,kpos);
400 goto out;
401
402 /* Kind of object does not exist. */
403
404 err121: *jstat = -121;
405 s6err("sh1790",*jstat,kpos);
406 goto out;
407
408 /* Error in lower level routine. */
409
410 error: *jstat = kstat;
411 s6err("sh1790",*jstat,kpos);
412 goto out;
413
414 out: return;
415 }
416
417
418
419
420
421