0030655: Modeling Data - Provide interfaces for selection of the elements from BVH...
[occt.git] / src / BRepExtrema / BRepExtrema_OverlapTool.cxx
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()
25 : myFilter (NULL),
26   myTolerance (0.0)
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)
37 : myFilter (NULL),
38   myTolerance (0.0)
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 {
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 //=======================================================================
507 //function : intersectTrianglesExact
508 //purpose  :
509 //=======================================================================
510 void BRepExtrema_OverlapTool::intersectTrianglesExact (const Standard_Integer theTrgIdx1,
511                                                        const Standard_Integer theTrgIdx2)
512 {
513   const Standard_Integer aFaceIdx1 = mySet1->GetFaceID (theTrgIdx1);
514
515   BVH_Vec3d aTrg1Vert1;
516   BVH_Vec3d aTrg1Vert2;
517   BVH_Vec3d aTrg1Vert3;
518
519   mySet1->GetVertices (theTrgIdx1,
520                        aTrg1Vert1,
521                        aTrg1Vert2,
522                        aTrg1Vert3);
523
524   const Standard_Boolean aIsInSet = myOverlapSubShapes1.IsBound (aFaceIdx1);
525
526   const Standard_Integer aFaceIdx2 = mySet2->GetFaceID (theTrgIdx2);
527
528   if (aIsInSet && myOverlapSubShapes1.Find (aFaceIdx1).Contains (aFaceIdx2))
529   {
530     return;
531   }
532
533   BRepExtrema_ElementFilter::FilterResult aResult = myFilter == NULL ?
534     BRepExtrema_ElementFilter::DoCheck : myFilter->PreCheckElements (theTrgIdx1, theTrgIdx2);
535
536   if (aResult == BRepExtrema_ElementFilter::Overlap)
537   {
538     getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2);
539     getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1);
540
541 #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES
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     }
552 #endif
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);
571
572 #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES
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);
582       }
583 #endif
584     }
585   }
586 }
587
588 //=======================================================================
589 //function : intersectTrianglesToler
590 //purpose  :
591 //=======================================================================
592 void BRepExtrema_OverlapTool::intersectTrianglesToler (const Standard_Integer theTrgIdx1,
593                                                        const Standard_Integer theTrgIdx2,
594                                                        const Standard_Real theToler)
595 {
596   const Standard_Integer aFaceIdx1 = mySet1->GetFaceID (theTrgIdx1);
597
598   BVH_Vec3d aTrg1Vert1;
599   BVH_Vec3d aTrg1Vert2;
600   BVH_Vec3d aTrg1Vert3;
601
602   mySet1->GetVertices (theTrgIdx1,
603                        aTrg1Vert1,
604                        aTrg1Vert2,
605                        aTrg1Vert3);
606
607   BRepExtrema_BoundingPrism aPrism1; // not initialized
608
609   const Standard_Boolean aIsInSet = myOverlapSubShapes1.IsBound (aFaceIdx1);
610
611   const Standard_Integer aFaceIdx2 = mySet2->GetFaceID (theTrgIdx2);
612
613   if (aIsInSet && myOverlapSubShapes1.Find (aFaceIdx1).Contains (aFaceIdx2))
614   {
615     return;
616   }
617
618   BRepExtrema_ElementFilter::FilterResult aResult = myFilter == NULL ?
619     BRepExtrema_ElementFilter::DoCheck : myFilter->PreCheckElements (theTrgIdx1, theTrgIdx2);
620
621   if (aResult == BRepExtrema_ElementFilter::Overlap)
622   {
623     getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2);
624     getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1);
625
626 #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES
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     }
637 #endif
638   }
639   else if (aResult == BRepExtrema_ElementFilter::DoCheck)
640   {
641     if (!aPrism1.IsInited)
642     {
643       aPrism1.Init (aTrg1Vert1, aTrg1Vert2, aTrg1Vert3, theToler);
644     }
645
646     BVH_Vec3d aTrg2Vert1;
647     BVH_Vec3d aTrg2Vert2;
648     BVH_Vec3d aTrg2Vert3;
649
650     mySet2->GetVertices (theTrgIdx2,
651                          aTrg2Vert1,
652                          aTrg2Vert2,
653                          aTrg2Vert3);
654
655     BRepExtrema_BoundingPrism aPrism2 (aTrg2Vert1,
656                                        aTrg2Vert2,
657                                        aTrg2Vert3,
658                                        theToler);
659
660     if (prismsIntersected (aPrism1, aPrism2))
661     {
662       getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2);
663       getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1);
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 {
674   myTolerance = theTolerance;
675
676   myIsDone = (this->Select(mySet1->BVH(), mySet2->BVH()) > 0);
677 }
678
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 }
691
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)
700   {
701     intersectTrianglesExact (theTrgIdx1, theTrgIdx2);
702   }
703   else
704   {
705     intersectTrianglesToler (theTrgIdx1, theTrgIdx2, myTolerance);
706   }
707   return Standard_True;
708 }