ae9a414a |
1 | // Created on: 2015-04-26 |
2 | // Created by: Denis BOGOLEPOV |
3 | // Copyright (c) 2015 OPEN CASCADE SAS |
4 | // |
5 | // This file is part of Open CASCADE Technology software library. |
6 | // |
7 | // This library is free software; you can redistribute it and/or modify it under |
8 | // the terms of the GNU Lesser General Public License version 2.1 as published |
9 | // by the Free Software Foundation, with special exception defined in the file |
10 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT |
11 | // distribution for complete text of the license and disclaimer of any warranty. |
12 | // |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
15 | |
16 | #include <Precision.hxx> |
17 | |
18 | #include <BRepExtrema_OverlapTool.hxx> |
19 | |
20 | //======================================================================= |
21 | //function : BRepExtrema_OverlapTool |
22 | //purpose : |
23 | //======================================================================= |
24 | BRepExtrema_OverlapTool::BRepExtrema_OverlapTool() |
7c1a8210 |
25 | : myFilter (NULL), |
26 | myTolerance (0.0) |
ae9a414a |
27 | { |
28 | myIsDone = Standard_False; |
29 | } |
30 | |
31 | //======================================================================= |
32 | //function : BRepExtrema_OverlapTool |
33 | //purpose : |
34 | //======================================================================= |
35 | BRepExtrema_OverlapTool::BRepExtrema_OverlapTool (const Handle(BRepExtrema_TriangleSet)& theSet1, |
36 | const Handle(BRepExtrema_TriangleSet)& theSet2) |
7c1a8210 |
37 | : myFilter (NULL), |
38 | myTolerance (0.0) |
ae9a414a |
39 | { |
40 | LoadTriangleSets (theSet1, theSet2); |
41 | } |
42 | |
43 | //======================================================================= |
44 | //function : LoadTriangleSets |
45 | //purpose : |
46 | //======================================================================= |
47 | void BRepExtrema_OverlapTool::LoadTriangleSets (const Handle(BRepExtrema_TriangleSet)& theSet1, |
48 | const Handle(BRepExtrema_TriangleSet)& theSet2) |
49 | { |
50 | mySet1 = theSet1; |
51 | mySet2 = theSet2; |
52 | |
53 | myIsDone = Standard_False; |
54 | } |
55 | |
56 | #ifndef DBL_EPSILON |
57 | #define DBL_EPSILON std::numeric_limits<Standard_Real>::epsilon() |
58 | #endif |
59 | |
60 | namespace |
61 | { |
ae9a414a |
62 | //! Bounding triangular prism for specified triangle. |
63 | class BRepExtrema_BoundingPrism |
64 | { |
65 | public: |
66 | |
67 | //! Vertices of the prism. |
68 | BVH_Vec3d Vertices[6]; |
69 | |
70 | //! Edges of the prism. |
71 | BVH_Vec3d Edges[3]; |
72 | |
73 | //! Normal to prism caps. |
74 | BVH_Vec3d Normal; |
75 | |
76 | //! Normals to prism edges. |
77 | BVH_Vec3d EdgeNormals[3]; |
78 | |
79 | //! Is prism initialized? |
80 | Standard_Boolean IsInited; |
81 | |
82 | public: |
83 | |
84 | //! Creates uninitialized bounding prism. |
85 | BRepExtrema_BoundingPrism() : IsInited (Standard_False) |
86 | { |
87 | // |
88 | } |
89 | |
90 | //! Creates new bounding prism for the given triangle. |
91 | BRepExtrema_BoundingPrism (const BVH_Vec3d& theVertex0, |
92 | const BVH_Vec3d& theVertex1, |
93 | const BVH_Vec3d& theVertex2, |
94 | const Standard_Real theDeflect) |
95 | { |
96 | Init (theVertex0, |
97 | theVertex1, |
98 | theVertex2, |
99 | theDeflect); |
100 | } |
101 | |
102 | //! Calculates bounding prism for the given triangle. |
103 | void Init (const BVH_Vec3d& theVertex0, |
104 | const BVH_Vec3d& theVertex1, |
105 | const BVH_Vec3d& theVertex2, |
106 | const Standard_Real theDeflect) |
107 | { |
108 | Edges[0] = theVertex1 - theVertex0; |
109 | Edges[1] = theVertex2 - theVertex0; |
110 | Edges[2] = theVertex2 - theVertex1; |
111 | |
112 | Normal = BVH_Vec3d::Cross (Edges[0], Edges[1]); |
113 | |
114 | EdgeNormals[0] = BVH_Vec3d::Cross (Edges[0], Normal); |
115 | EdgeNormals[1] = BVH_Vec3d::Cross (Edges[1], Normal); |
116 | EdgeNormals[2] = BVH_Vec3d::Cross (Edges[2], Normal); |
117 | |
118 | EdgeNormals[0] *= 1.0 / Max (EdgeNormals[0].Modulus(), Precision::Confusion()); |
119 | EdgeNormals[1] *= 1.0 / Max (EdgeNormals[1].Modulus(), Precision::Confusion()); |
120 | EdgeNormals[2] *= 1.0 / Max (EdgeNormals[2].Modulus(), Precision::Confusion()); |
121 | |
122 | const BVH_Vec3d aDirect01 = EdgeNormals[0] - EdgeNormals[1]; |
123 | const BVH_Vec3d aDirect02 = EdgeNormals[0] + EdgeNormals[2]; |
124 | const BVH_Vec3d aDirect12 = EdgeNormals[2] - EdgeNormals[1]; |
125 | |
126 | Vertices[0] = Vertices[3] = theVertex0 + aDirect01 * (theDeflect / aDirect01.Dot (EdgeNormals[0])); |
127 | Vertices[1] = Vertices[4] = theVertex1 + aDirect02 * (theDeflect / aDirect02.Dot (EdgeNormals[2])); |
128 | Vertices[2] = Vertices[5] = theVertex2 + aDirect12 * (theDeflect / aDirect12.Dot (EdgeNormals[2])); |
129 | |
130 | const BVH_Vec3d aNormOffset = Normal * (theDeflect / Max (Normal.Modulus(), Precision::Confusion())); |
131 | |
132 | for (Standard_Integer aVertIdx = 0; aVertIdx < 3; ++aVertIdx) |
133 | { |
134 | Vertices[aVertIdx + 0] += aNormOffset; |
135 | Vertices[aVertIdx + 3] -= aNormOffset; |
136 | } |
137 | |
138 | IsInited = Standard_True; |
139 | } |
140 | |
141 | //! Checks if two prisms are separated along the given axis. |
142 | Standard_Boolean Separated (const BRepExtrema_BoundingPrism& thePrism, const BVH_Vec3d& theAxis) const |
143 | { |
144 | Standard_Real aMin1 = DBL_MAX; |
145 | Standard_Real aMax1 = -DBL_MAX; |
146 | |
147 | Standard_Real aMin2 = DBL_MAX; |
148 | Standard_Real aMax2 = -DBL_MAX; |
149 | |
150 | for (Standard_Integer aVertIdx = 0; aVertIdx < 6; ++aVertIdx) |
151 | { |
152 | const Standard_Real aProj1 = Vertices[aVertIdx].Dot (theAxis); |
153 | |
154 | aMin1 = Min (aMin1, aProj1); |
155 | aMax1 = Max (aMax1, aProj1); |
156 | |
157 | const Standard_Real aProj2 = thePrism.Vertices[aVertIdx].Dot (theAxis); |
158 | |
159 | aMin2 = Min (aMin2, aProj2); |
160 | aMax2 = Max (aMax2, aProj2); |
161 | |
162 | if (aMin1 <= aMax2 && aMax1 >= aMin2) |
163 | { |
164 | return Standard_False; |
165 | } |
166 | } |
167 | |
168 | return aMin1 > aMax2 || aMax1 < aMin2; |
169 | } |
170 | }; |
171 | |
172 | // ======================================================================= |
173 | // function : sign |
174 | // purpose : |
175 | // ======================================================================= |
176 | Standard_Real sign (const BVH_Vec3d& theVertex0, |
177 | const BVH_Vec3d& theVertex1, |
178 | const BVH_Vec3d& theVertex2, |
179 | const Standard_Integer theX, |
180 | const Standard_Integer theY) |
181 | { |
182 | return (theVertex0[theX] - theVertex2[theX]) * (theVertex1[theY] - theVertex2[theY]) - |
183 | (theVertex1[theX] - theVertex2[theX]) * (theVertex0[theY] - theVertex2[theY]); |
184 | } |
185 | |
186 | // ======================================================================= |
187 | // function : pointInTriangle |
188 | // purpose : |
189 | // ======================================================================= |
190 | Standard_Boolean pointInTriangle (const BVH_Vec3d& theTestPnt, |
191 | const BVH_Vec3d& theTrgVtx0, |
192 | const BVH_Vec3d& theTrgVtx1, |
193 | const BVH_Vec3d& theTrgVtx2, |
194 | const Standard_Integer theX, |
195 | const Standard_Integer theY) |
196 | { |
197 | const Standard_Boolean aSign0 = sign (theTestPnt, theTrgVtx0, theTrgVtx1, theX, theY) <= 0.0; |
198 | const Standard_Boolean aSign1 = sign (theTestPnt, theTrgVtx1, theTrgVtx2, theX, theY) <= 0.0; |
199 | const Standard_Boolean aSign2 = sign (theTestPnt, theTrgVtx2, theTrgVtx0, theX, theY) <= 0.0; |
200 | |
201 | return (aSign0 == aSign1) && (aSign1 == aSign2); |
202 | } |
203 | |
204 | // ======================================================================= |
205 | // function : segmentsIntersected |
206 | // purpose : Checks if two line segments are intersected |
207 | // ======================================================================= |
208 | Standard_Boolean segmentsIntersected (const BVH_Vec2d& theOriginSeg0, |
209 | const BVH_Vec2d& theOriginSeg1, |
210 | const BVH_Vec2d& theDirectSeg0, |
211 | const BVH_Vec2d& theDirectSeg1) |
212 | { |
213 | const Standard_Real aDet = -theDirectSeg1.x() * theDirectSeg0.y() + |
214 | theDirectSeg0.x() * theDirectSeg1.y(); |
215 | |
216 | if (fabs (aDet) < DBL_EPSILON) // segments are parallel |
217 | { |
218 | const BVH_Vec2d aDirect = theDirectSeg0 * (1.0 / theDirectSeg0.Modulus()); |
219 | |
220 | const Standard_Real aEdge0Time0 = theOriginSeg0.Dot (aDirect); |
221 | const Standard_Real aEdge1Time0 = theOriginSeg1.Dot (aDirect); |
222 | |
223 | const Standard_Real aEdge0Time1 = aEdge0Time0 + theDirectSeg0.Dot (aDirect); |
224 | const Standard_Real aEdge1Time1 = aEdge1Time0 + theDirectSeg1.Dot (aDirect); |
225 | |
226 | const Standard_Real aEdge0Min = Min (aEdge0Time0, aEdge0Time1); |
227 | const Standard_Real aEdge1Min = Min (aEdge1Time0, aEdge1Time1); |
228 | const Standard_Real aEdge0Max = Max (aEdge0Time0, aEdge0Time1); |
229 | const Standard_Real aEdge1Max = Max (aEdge1Time0, aEdge1Time1); |
230 | |
231 | if (Max (aEdge0Min, aEdge1Min) > Min (aEdge0Max, aEdge1Max)) |
232 | { |
233 | return Standard_False; |
234 | } |
235 | |
236 | const BVH_Vec2d aNormal (-aDirect.y(), aDirect.x()); |
237 | |
238 | return fabs (theOriginSeg0.Dot (aNormal) - theOriginSeg1.Dot (aNormal)) < DBL_EPSILON; |
239 | } |
240 | |
241 | const BVH_Vec2d aDelta = theOriginSeg0 - theOriginSeg1; |
242 | |
243 | const Standard_Real aU = (-theDirectSeg0.y() * aDelta.x() + theDirectSeg0.x() * aDelta.y()) / aDet; |
244 | const Standard_Real aV = ( theDirectSeg1.x() * aDelta.y() - theDirectSeg1.y() * aDelta.x()) / aDet; |
245 | |
246 | return aU >= 0.0 && aU <= 1.0 && aV >= 0.0 && aV <= 1.0; |
247 | } |
248 | |
249 | // ======================================================================= |
250 | // function : trianglesIntersected |
251 | // purpose : Checks if two triangles are intersected |
252 | // ("A Fast Triangle-Triangle Intersection Test" by T. Moller) |
253 | // ======================================================================= |
254 | Standard_Boolean trianglesIntersected (const BVH_Vec3d& theTrng0Vert0, |
255 | const BVH_Vec3d& theTrng0Vert1, |
256 | const BVH_Vec3d& theTrng0Vert2, |
257 | const BVH_Vec3d& theTrng1Vert0, |
258 | const BVH_Vec3d& theTrng1Vert1, |
259 | const BVH_Vec3d& theTrng1Vert2) |
260 | { |
261 | const BVH_Vec3d aTrng1Normal = BVH_Vec3d::Cross (theTrng1Vert1 - theTrng1Vert0, |
262 | theTrng1Vert2 - theTrng1Vert0).Normalized(); |
263 | |
264 | const Standard_Real aTrng1PlaneDist = aTrng1Normal.Dot (-theTrng1Vert0); |
265 | |
266 | Standard_Real aDistTrng0Vert0 = aTrng1Normal.Dot (theTrng0Vert0) + aTrng1PlaneDist; |
267 | Standard_Real aDistTrng0Vert1 = aTrng1Normal.Dot (theTrng0Vert1) + aTrng1PlaneDist; |
268 | Standard_Real aDistTrng0Vert2 = aTrng1Normal.Dot (theTrng0Vert2) + aTrng1PlaneDist; |
269 | |
270 | if ((aDistTrng0Vert0 < 0.0 && aDistTrng0Vert1 < 0.0 && aDistTrng0Vert2 < 0.0) |
271 | || (aDistTrng0Vert0 > 0.0 && aDistTrng0Vert1 > 0.0 && aDistTrng0Vert2 > 0.0)) |
272 | { |
273 | return Standard_False; // 1st triangle lies on one side of the 2nd triangle |
274 | } |
275 | |
276 | if (fabs (aDistTrng0Vert0) > Precision::Confusion() |
277 | || fabs (aDistTrng0Vert1) > Precision::Confusion() |
278 | || fabs (aDistTrng0Vert2) > Precision::Confusion()) // general 3D case |
279 | { |
280 | const BVH_Vec3d aTrng0Normal = BVH_Vec3d::Cross (theTrng0Vert1 - theTrng0Vert0, |
281 | theTrng0Vert2 - theTrng0Vert0).Normalized(); |
282 | |
283 | const Standard_Real aTrng0PlaneDist = aTrng0Normal.Dot (-theTrng0Vert0); |
284 | |
285 | Standard_Real aDistTrng1Vert0 = aTrng0Normal.Dot (theTrng1Vert0) + aTrng0PlaneDist; |
286 | Standard_Real aDistTrng1Vert1 = aTrng0Normal.Dot (theTrng1Vert1) + aTrng0PlaneDist; |
287 | Standard_Real aDistTrng1Vert2 = aTrng0Normal.Dot (theTrng1Vert2) + aTrng0PlaneDist; |
288 | |
289 | if ((aDistTrng1Vert0 < 0.0 && aDistTrng1Vert1 < 0.0 && aDistTrng1Vert2 < 0.0) |
290 | || (aDistTrng1Vert0 > 0.0 && aDistTrng1Vert1 > 0.0 && aDistTrng1Vert2 > 0.0)) |
291 | { |
292 | return Standard_False; // 2nd triangle lies on one side of the 1st triangle |
293 | } |
294 | |
295 | const BVH_Vec3d aCrossLine = BVH_Vec3d::Cross (aTrng0Normal, |
296 | aTrng1Normal); |
297 | |
298 | Standard_Real aProjTrng0Vert0 = theTrng0Vert0.Dot (aCrossLine); |
299 | Standard_Real aProjTrng0Vert1 = theTrng0Vert1.Dot (aCrossLine); |
300 | Standard_Real aProjTrng0Vert2 = theTrng0Vert2.Dot (aCrossLine); |
301 | |
302 | if (aDistTrng0Vert0 * aDistTrng0Vert1 > 0.0) |
303 | { |
304 | std::swap (aDistTrng0Vert1, aDistTrng0Vert2); |
305 | std::swap (aProjTrng0Vert1, aProjTrng0Vert2); |
306 | } |
307 | else if (aDistTrng0Vert1 * aDistTrng0Vert2 > 0.0) |
308 | { |
309 | std::swap (aDistTrng0Vert1, aDistTrng0Vert0); |
310 | std::swap (aProjTrng0Vert1, aProjTrng0Vert0); |
311 | } |
312 | |
313 | Standard_Real aTime1 = fabs (aDistTrng0Vert0) <= DBL_EPSILON ? aProjTrng0Vert0 : |
314 | aProjTrng0Vert0 + (aProjTrng0Vert1 - aProjTrng0Vert0) * aDistTrng0Vert0 / (aDistTrng0Vert0 - aDistTrng0Vert1); |
315 | Standard_Real aTime2 = fabs (aDistTrng0Vert2) <= DBL_EPSILON ? aProjTrng0Vert2 : |
316 | aProjTrng0Vert2 + (aProjTrng0Vert1 - aProjTrng0Vert2) * aDistTrng0Vert2 / (aDistTrng0Vert2 - aDistTrng0Vert1); |
317 | |
318 | const Standard_Real aTimeMin1 = Min (aTime1, aTime2); |
319 | const Standard_Real aTimeMax1 = Max (aTime1, aTime2); |
320 | |
321 | Standard_Real aProjTrng1Vert0 = theTrng1Vert0.Dot (aCrossLine); |
322 | Standard_Real aProjTrng1Vert1 = theTrng1Vert1.Dot (aCrossLine); |
323 | Standard_Real aProjTrng1Vert2 = theTrng1Vert2.Dot (aCrossLine); |
324 | |
325 | if (aDistTrng1Vert0 * aDistTrng1Vert1 > 0.0) |
326 | { |
327 | std::swap (aDistTrng1Vert1, aDistTrng1Vert2); |
328 | std::swap (aProjTrng1Vert1, aProjTrng1Vert2); |
329 | } |
330 | else if (aDistTrng1Vert1 * aDistTrng1Vert2 > 0.0) |
331 | { |
332 | std::swap (aDistTrng1Vert1, aDistTrng1Vert0); |
333 | std::swap (aProjTrng1Vert1, aProjTrng1Vert0); |
334 | } |
335 | |
336 | aTime1 = fabs (aDistTrng1Vert0) <= DBL_EPSILON ? aProjTrng1Vert0 : |
337 | aProjTrng1Vert0 + (aProjTrng1Vert1 - aProjTrng1Vert0) * aDistTrng1Vert0 / (aDistTrng1Vert0 - aDistTrng1Vert1); |
338 | aTime2 = fabs (aDistTrng1Vert2) <= DBL_EPSILON ? aProjTrng1Vert2 : |
339 | aProjTrng1Vert2 + (aProjTrng1Vert1 - aProjTrng1Vert2) * aDistTrng1Vert2 / (aDistTrng1Vert2 - aDistTrng1Vert1); |
340 | |
341 | const Standard_Real aTimeMin2 = Min (aTime1, aTime2); |
342 | const Standard_Real aTimeMax2 = Max (aTime1, aTime2); |
343 | |
344 | aTime1 = Max (aTimeMin1, aTimeMin2); |
345 | aTime2 = Min (aTimeMax1, aTimeMax2); |
346 | |
347 | return aTime1 <= aTime2; // intervals intersected --> triangles overlapped |
348 | } |
349 | else // triangles are co-planar |
350 | { |
351 | Standard_Integer anX; |
352 | Standard_Integer anY; |
353 | |
354 | if (fabs (aTrng1Normal[0]) > fabs (aTrng1Normal[1])) |
355 | { |
356 | anX = fabs (aTrng1Normal[0]) > fabs (aTrng1Normal[2]) ? 1 : 0; |
357 | anY = fabs (aTrng1Normal[0]) > fabs (aTrng1Normal[2]) ? 2 : 1; |
358 | } |
359 | else |
360 | { |
361 | anX = fabs (aTrng1Normal[1]) > fabs (aTrng1Normal[2]) ? 0 : 0; |
362 | anY = fabs (aTrng1Normal[1]) > fabs (aTrng1Normal[2]) ? 2 : 1; |
363 | } |
364 | |
365 | const BVH_Vec2d aOriginSeg0 [] = {BVH_Vec2d (theTrng0Vert0[anX], theTrng0Vert0[anY]), |
366 | BVH_Vec2d (theTrng0Vert1[anX], theTrng0Vert1[anY]), |
367 | BVH_Vec2d (theTrng0Vert2[anX], theTrng0Vert2[anY]) }; |
368 | |
369 | const BVH_Vec2d aDirectSeg0 [] = {aOriginSeg0[1] - aOriginSeg0[0], |
370 | aOriginSeg0[2] - aOriginSeg0[1], |
371 | aOriginSeg0[0] - aOriginSeg0[2] }; |
372 | |
373 | const BVH_Vec2d aOriginSeg1 [] = {BVH_Vec2d (theTrng1Vert0[anX], theTrng1Vert0[anY]), |
374 | BVH_Vec2d (theTrng1Vert1[anX], theTrng1Vert1[anY]), |
375 | BVH_Vec2d (theTrng1Vert2[anX], theTrng1Vert2[anY]) }; |
376 | |
377 | const BVH_Vec2d aDirectSeg1 [] = {aOriginSeg1[1] - aOriginSeg1[0], |
378 | aOriginSeg1[2] - aOriginSeg1[1], |
379 | aOriginSeg1[0] - aOriginSeg1[2] }; |
380 | |
381 | for (Standard_Integer aTrg0Edge = 0; aTrg0Edge < 3; ++aTrg0Edge) |
382 | { |
383 | for (Standard_Integer aTrg1Edge = 0; aTrg1Edge < 3; ++aTrg1Edge) |
384 | { |
385 | if (segmentsIntersected (aOriginSeg0[aTrg0Edge], |
386 | aOriginSeg1[aTrg1Edge], |
387 | aDirectSeg0[aTrg0Edge], |
388 | aDirectSeg1[aTrg1Edge])) |
389 | { |
390 | return Standard_True; // edges intersected --> triangles overlapped |
391 | } |
392 | } |
393 | } |
394 | |
395 | if (pointInTriangle (theTrng1Vert0, |
396 | theTrng0Vert0, |
397 | theTrng0Vert1, |
398 | theTrng0Vert2, |
399 | anX, |
400 | anY)) |
401 | { |
402 | return Standard_True; // 1st triangle inside 2nd --> triangles overlapped |
403 | } |
404 | |
405 | if (pointInTriangle (theTrng0Vert0, |
406 | theTrng1Vert0, |
407 | theTrng1Vert1, |
408 | theTrng1Vert2, |
409 | anX, |
410 | anY)) |
411 | { |
412 | return Standard_True; // 2nd triangle inside 1st --> triangles overlapped |
413 | } |
414 | } |
415 | |
416 | return Standard_False; |
417 | } |
418 | |
419 | // ======================================================================= |
420 | // function : prismsIntersected |
421 | // purpose : Checks if two triangular prisms are intersected |
422 | // (test uses SAT - Separating Axis Theorem) |
423 | // ======================================================================= |
424 | Standard_Boolean prismsIntersected (const BRepExtrema_BoundingPrism& thePrism1, |
425 | const BRepExtrema_BoundingPrism& thePrism2) |
426 | { |
427 | if (thePrism1.Separated (thePrism2, thePrism1.Normal)) |
428 | { |
429 | return Standard_False; |
430 | } |
431 | |
432 | if (thePrism1.Separated (thePrism2, thePrism2.Normal)) |
433 | { |
434 | return Standard_False; |
435 | } |
436 | |
437 | for (Standard_Integer anIdx = 0; anIdx < 3; ++anIdx) |
438 | { |
439 | if (thePrism1.Separated (thePrism2, thePrism1.EdgeNormals[anIdx])) |
440 | { |
441 | return Standard_False; |
442 | } |
443 | } |
444 | |
445 | for (Standard_Integer anIdx = 0; anIdx < 3; ++anIdx) |
446 | { |
447 | if (thePrism1.Separated (thePrism2, thePrism2.EdgeNormals[anIdx])) |
448 | { |
449 | return Standard_False; |
450 | } |
451 | } |
452 | |
453 | for (Standard_Integer anIdx1 = 0; anIdx1 < 4; ++anIdx1) |
454 | { |
455 | const BVH_Vec3d& aEdge1 = (anIdx1 == 3) ? thePrism1.Normal : thePrism1.Edges[anIdx1]; |
456 | |
457 | for (Standard_Integer anIdx2 = 0; anIdx2 < 4; ++anIdx2) |
458 | { |
459 | const BVH_Vec3d& aEdge2 = (anIdx2 == 3) ? thePrism2.Normal : thePrism2.Edges[anIdx2]; |
460 | |
461 | if (thePrism1.Separated (thePrism2, BVH_Vec3d::Cross (aEdge1, aEdge2))) |
462 | { |
463 | return Standard_False; |
464 | } |
465 | } |
466 | } |
467 | |
468 | return Standard_True; |
469 | } |
470 | |
471 | // ======================================================================= |
472 | // function : overlapBoxes |
473 | // purpose : Checks if two boxes (AABBs) are overlapped |
474 | // ======================================================================= |
475 | inline Standard_Boolean overlapBoxes (const BVH_Vec3d& theBoxMin1, |
476 | const BVH_Vec3d& theBoxMax1, |
477 | const BVH_Vec3d& theBoxMin2, |
478 | const BVH_Vec3d& theBoxMax2, |
479 | const Standard_Real theTolerance) |
480 | { |
481 | // Check for overlap |
482 | return !(theBoxMin1.x() > theBoxMax2.x() + theTolerance || |
483 | theBoxMax1.x() < theBoxMin2.x() - theTolerance || |
484 | theBoxMin1.y() > theBoxMax2.y() + theTolerance || |
485 | theBoxMax1.y() < theBoxMin2.y() - theTolerance || |
486 | theBoxMin1.z() > theBoxMax2.z() + theTolerance || |
487 | theBoxMax1.z() < theBoxMin2.z() - theTolerance); |
488 | } |
489 | |
490 | //======================================================================= |
491 | //function : getSetOfFaces |
492 | //purpose : |
493 | //======================================================================= |
494 | TColStd_PackedMapOfInteger& getSetOfFaces ( |
495 | BRepExtrema_MapOfIntegerPackedMapOfInteger& theFaces, const Standard_Integer theFaceIdx) |
496 | { |
497 | if (!theFaces.IsBound (theFaceIdx)) |
498 | { |
499 | theFaces.Bind (theFaceIdx, TColStd_PackedMapOfInteger()); |
500 | } |
501 | |
502 | return theFaces.ChangeFind (theFaceIdx); |
503 | } |
504 | } |
505 | |
506 | //======================================================================= |
7c1a8210 |
507 | //function : intersectTrianglesExact |
ae9a414a |
508 | //purpose : |
509 | //======================================================================= |
7c1a8210 |
510 | void BRepExtrema_OverlapTool::intersectTrianglesExact (const Standard_Integer theTrgIdx1, |
511 | const Standard_Integer theTrgIdx2) |
ae9a414a |
512 | { |
7c1a8210 |
513 | const Standard_Integer aFaceIdx1 = mySet1->GetFaceID (theTrgIdx1); |
ae9a414a |
514 | |
7c1a8210 |
515 | BVH_Vec3d aTrg1Vert1; |
516 | BVH_Vec3d aTrg1Vert2; |
517 | BVH_Vec3d aTrg1Vert3; |
ae9a414a |
518 | |
7c1a8210 |
519 | mySet1->GetVertices (theTrgIdx1, |
520 | aTrg1Vert1, |
521 | aTrg1Vert2, |
522 | aTrg1Vert3); |
ae9a414a |
523 | |
7c1a8210 |
524 | const Standard_Boolean aIsInSet = myOverlapSubShapes1.IsBound (aFaceIdx1); |
ae9a414a |
525 | |
7c1a8210 |
526 | const Standard_Integer aFaceIdx2 = mySet2->GetFaceID (theTrgIdx2); |
ae9a414a |
527 | |
7c1a8210 |
528 | if (aIsInSet && myOverlapSubShapes1.Find (aFaceIdx1).Contains (aFaceIdx2)) |
529 | { |
530 | return; |
531 | } |
ae9a414a |
532 | |
7c1a8210 |
533 | BRepExtrema_ElementFilter::FilterResult aResult = myFilter == NULL ? |
534 | BRepExtrema_ElementFilter::DoCheck : myFilter->PreCheckElements (theTrgIdx1, theTrgIdx2); |
ae9a414a |
535 | |
7c1a8210 |
536 | if (aResult == BRepExtrema_ElementFilter::Overlap) |
537 | { |
538 | getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); |
539 | getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); |
ae9a414a |
540 | |
541 | #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES |
7c1a8210 |
542 | if (mySet1 == mySet2) |
543 | { |
544 | myOverlapTriangles1.Add (theTrgIdx1); |
545 | myOverlapTriangles1.Add (theTrgIdx2); |
546 | } |
547 | else |
548 | { |
549 | myOverlapTriangles1.Add (theTrgIdx1); |
550 | myOverlapTriangles2.Add (theTrgIdx2); |
551 | } |
ae9a414a |
552 | #endif |
7c1a8210 |
553 | } |
554 | else if (aResult == BRepExtrema_ElementFilter::DoCheck) |
555 | { |
556 | BVH_Vec3d aTrg2Vert1; |
557 | BVH_Vec3d aTrg2Vert2; |
558 | BVH_Vec3d aTrg2Vert3; |
559 | |
560 | mySet2->GetVertices (theTrgIdx2, aTrg2Vert1, aTrg2Vert2, aTrg2Vert3); |
561 | |
562 | if (trianglesIntersected (aTrg1Vert1, |
563 | aTrg1Vert2, |
564 | aTrg1Vert3, |
565 | aTrg2Vert1, |
566 | aTrg2Vert2, |
567 | aTrg2Vert3)) |
568 | { |
569 | getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); |
570 | getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); |
ae9a414a |
571 | |
572 | #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES |
7c1a8210 |
573 | if (mySet1 == mySet2) |
574 | { |
575 | myOverlapTriangles1.Add (theTrgIdx1); |
576 | myOverlapTriangles1.Add (theTrgIdx2); |
577 | } |
578 | else |
579 | { |
580 | myOverlapTriangles1.Add (theTrgIdx1); |
581 | myOverlapTriangles2.Add (theTrgIdx2); |
ae9a414a |
582 | } |
7c1a8210 |
583 | #endif |
ae9a414a |
584 | } |
585 | } |
586 | } |
587 | |
588 | //======================================================================= |
7c1a8210 |
589 | //function : intersectTrianglesToler |
ae9a414a |
590 | //purpose : |
591 | //======================================================================= |
7c1a8210 |
592 | void BRepExtrema_OverlapTool::intersectTrianglesToler (const Standard_Integer theTrgIdx1, |
593 | const Standard_Integer theTrgIdx2, |
594 | const Standard_Real theToler) |
ae9a414a |
595 | { |
7c1a8210 |
596 | const Standard_Integer aFaceIdx1 = mySet1->GetFaceID (theTrgIdx1); |
ae9a414a |
597 | |
7c1a8210 |
598 | BVH_Vec3d aTrg1Vert1; |
599 | BVH_Vec3d aTrg1Vert2; |
600 | BVH_Vec3d aTrg1Vert3; |
ae9a414a |
601 | |
7c1a8210 |
602 | mySet1->GetVertices (theTrgIdx1, |
603 | aTrg1Vert1, |
604 | aTrg1Vert2, |
605 | aTrg1Vert3); |
ae9a414a |
606 | |
7c1a8210 |
607 | BRepExtrema_BoundingPrism aPrism1; // not initialized |
ae9a414a |
608 | |
7c1a8210 |
609 | const Standard_Boolean aIsInSet = myOverlapSubShapes1.IsBound (aFaceIdx1); |
ae9a414a |
610 | |
7c1a8210 |
611 | const Standard_Integer aFaceIdx2 = mySet2->GetFaceID (theTrgIdx2); |
ae9a414a |
612 | |
7c1a8210 |
613 | if (aIsInSet && myOverlapSubShapes1.Find (aFaceIdx1).Contains (aFaceIdx2)) |
614 | { |
615 | return; |
616 | } |
ae9a414a |
617 | |
7c1a8210 |
618 | BRepExtrema_ElementFilter::FilterResult aResult = myFilter == NULL ? |
619 | BRepExtrema_ElementFilter::DoCheck : myFilter->PreCheckElements (theTrgIdx1, theTrgIdx2); |
ae9a414a |
620 | |
7c1a8210 |
621 | if (aResult == BRepExtrema_ElementFilter::Overlap) |
622 | { |
623 | getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); |
624 | getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); |
ae9a414a |
625 | |
626 | #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES |
7c1a8210 |
627 | if (mySet1 == mySet2) |
628 | { |
629 | myOverlapTriangles1.Add (theTrgIdx1); |
630 | myOverlapTriangles1.Add (theTrgIdx2); |
631 | } |
632 | else |
633 | { |
634 | myOverlapTriangles1.Add (theTrgIdx1); |
635 | myOverlapTriangles2.Add (theTrgIdx2); |
636 | } |
ae9a414a |
637 | #endif |
7c1a8210 |
638 | } |
639 | else if (aResult == BRepExtrema_ElementFilter::DoCheck) |
640 | { |
641 | if (!aPrism1.IsInited) |
642 | { |
643 | aPrism1.Init (aTrg1Vert1, aTrg1Vert2, aTrg1Vert3, theToler); |
644 | } |
ae9a414a |
645 | |
7c1a8210 |
646 | BVH_Vec3d aTrg2Vert1; |
647 | BVH_Vec3d aTrg2Vert2; |
648 | BVH_Vec3d aTrg2Vert3; |
ae9a414a |
649 | |
7c1a8210 |
650 | mySet2->GetVertices (theTrgIdx2, |
651 | aTrg2Vert1, |
652 | aTrg2Vert2, |
653 | aTrg2Vert3); |
ae9a414a |
654 | |
7c1a8210 |
655 | BRepExtrema_BoundingPrism aPrism2 (aTrg2Vert1, |
656 | aTrg2Vert2, |
657 | aTrg2Vert3, |
658 | theToler); |
ae9a414a |
659 | |
7c1a8210 |
660 | if (prismsIntersected (aPrism1, aPrism2)) |
661 | { |
662 | getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); |
663 | getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); |
ae9a414a |
664 | } |
665 | } |
666 | } |
667 | |
668 | //======================================================================= |
669 | //function : Perform |
670 | //purpose : Performs search for overlapped faces |
671 | //======================================================================= |
672 | void BRepExtrema_OverlapTool::Perform (const Standard_Real theTolerance) |
673 | { |
7c1a8210 |
674 | myTolerance = theTolerance; |
ae9a414a |
675 | |
7c1a8210 |
676 | myIsDone = (this->Select(mySet1->BVH(), mySet2->BVH()) > 0); |
677 | } |
ae9a414a |
678 | |
7c1a8210 |
679 | //======================================================================= |
680 | //function : Branch rejection |
681 | //purpose : |
682 | //======================================================================= |
683 | Standard_Boolean BRepExtrema_OverlapTool::RejectNode (const BVH_Vec3d& theCornerMin1, |
684 | const BVH_Vec3d& theCornerMax1, |
685 | const BVH_Vec3d& theCornerMin2, |
686 | const BVH_Vec3d& theCornerMax2, |
687 | Standard_Real&) const |
688 | { |
689 | return !overlapBoxes (theCornerMin1, theCornerMax1, theCornerMin2, theCornerMax2, myTolerance); |
690 | } |
ae9a414a |
691 | |
7c1a8210 |
692 | //======================================================================= |
693 | //function : Leaf acceptance |
694 | //purpose : |
695 | //======================================================================= |
696 | Standard_Boolean BRepExtrema_OverlapTool::Accept (const Standard_Integer theTrgIdx1, |
697 | const Standard_Integer theTrgIdx2) |
698 | { |
699 | if (myTolerance == 0.0) |
ae9a414a |
700 | { |
7c1a8210 |
701 | intersectTrianglesExact (theTrgIdx1, theTrgIdx2); |
ae9a414a |
702 | } |
7c1a8210 |
703 | else |
ae9a414a |
704 | { |
7c1a8210 |
705 | intersectTrianglesToler (theTrgIdx1, theTrgIdx2, myTolerance); |
ae9a414a |
706 | } |
7c1a8210 |
707 | return Standard_True; |
ae9a414a |
708 | } |