1 // Created on: 2015-04-26
2 // Created by: Denis BOGOLEPOV
3 // Copyright (c) 2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #include <BRepExtrema_SelfIntersection.hxx>
18 #include <Precision.hxx>
19 #include <TopExp_Explorer.hxx>
21 //=======================================================================
22 //function : BRepExtrema_SelfIntersection
24 //=======================================================================
25 BRepExtrema_SelfIntersection::BRepExtrema_SelfIntersection (const Standard_Real theTolerance)
26 : myTolerance (theTolerance)
28 myIsInit = Standard_False;
31 //=======================================================================
32 //function : BRepExtrema_SelfIntersection
34 //=======================================================================
35 BRepExtrema_SelfIntersection::BRepExtrema_SelfIntersection (const TopoDS_Shape& theShape, const Standard_Real theTolerance)
36 : myTolerance (theTolerance)
41 //=======================================================================
42 //function : LoadShape
44 //=======================================================================
45 Standard_Boolean BRepExtrema_SelfIntersection::LoadShape (const TopoDS_Shape& theShape)
49 for (TopExp_Explorer anIter (theShape, TopAbs_FACE); anIter.More(); anIter.Next())
51 myFaceList.Append (static_cast<const TopoDS_Face&> (anIter.Current()));
54 if (myElementSet.IsNull())
56 myElementSet = new BRepExtrema_TriangleSet;
59 myIsInit = myElementSet->Init (myFaceList);
63 myOverlapTool.LoadTriangleSets (myElementSet,
70 #define ZERO_VEC BVH_Vec3d (0.0, 0.0, 0.0)
74 // =======================================================================
76 // purpose : Check if triple is in counterclockwise order
77 // =======================================================================
78 Standard_Boolean ccw (const BVH_Vec3d& theVertex0,
79 const BVH_Vec3d& theVertex1,
80 const BVH_Vec3d& theVertex2,
81 const Standard_Integer theX,
82 const Standard_Integer theY)
84 const Standard_Real aSum =
85 (theVertex1[theX] - theVertex0[theX]) * (theVertex1[theY] + theVertex0[theY]) +
86 (theVertex2[theX] - theVertex1[theX]) * (theVertex2[theY] + theVertex1[theY]) +
87 (theVertex0[theX] - theVertex2[theX]) * (theVertex0[theY] + theVertex2[theY]);
92 // =======================================================================
93 // function : rayInsideAngle
94 // purpose : Check the given ray is inside the angle
95 // =======================================================================
96 Standard_Boolean rayInsideAngle (const BVH_Vec3d& theDirec,
97 const BVH_Vec3d& theEdge0,
98 const BVH_Vec3d& theEdge1,
99 const Standard_Integer theX,
100 const Standard_Integer theY)
102 const Standard_Boolean aCCW = ccw (ZERO_VEC, theEdge0, theEdge1, theX, theY);
104 return ccw (ZERO_VEC, theEdge0, theDirec, theX, theY) == aCCW
105 && ccw (ZERO_VEC, theDirec, theEdge1, theX, theY) == aCCW;
108 // =======================================================================
109 // function : getProjectionAxes
111 // =======================================================================
112 void getProjectionAxes (const BVH_Vec3d& theNorm,
113 Standard_Integer& theAxisX,
114 Standard_Integer& theAxisY)
116 if (fabs (theNorm[0]) > fabs (theNorm[1]))
118 theAxisX = fabs (theNorm[0]) > fabs (theNorm[2]) ? 1 : 0;
119 theAxisY = fabs (theNorm[0]) > fabs (theNorm[2]) ? 2 : 1;
123 theAxisX = fabs (theNorm[1]) > fabs (theNorm[2]) ? 0 : 0;
124 theAxisY = fabs (theNorm[1]) > fabs (theNorm[2]) ? 2 : 1;
129 //=======================================================================
130 //function : isRegularSharedVertex
132 //=======================================================================
133 BRepExtrema_ElementFilter::FilterResult BRepExtrema_SelfIntersection::isRegularSharedVertex (const BVH_Vec3d& theSharedVert,
134 const BVH_Vec3d& theTrng0Vtxs1,
135 const BVH_Vec3d& theTrng0Vtxs2,
136 const BVH_Vec3d& theTrng1Vtxs1,
137 const BVH_Vec3d& theTrng1Vtxs2)
139 const BVH_Vec3d aTrng0Edges[] = { (theTrng0Vtxs1 - theSharedVert).Normalized(),
140 (theTrng0Vtxs2 - theSharedVert).Normalized() };
142 const BVH_Vec3d aTrng1Edges[] = { (theTrng1Vtxs1 - theSharedVert).Normalized(),
143 (theTrng1Vtxs2 - theSharedVert).Normalized() };
145 const BVH_Vec3d aTrng0Normal = BVH_Vec3d::Cross (aTrng0Edges[0], aTrng0Edges[1]);
146 const BVH_Vec3d aTrng1Normal = BVH_Vec3d::Cross (aTrng1Edges[0], aTrng1Edges[1]);
148 BVH_Vec3d aCrossLine = BVH_Vec3d::Cross (aTrng0Normal,
151 Standard_Integer anX;
152 Standard_Integer anY;
154 if (aCrossLine.SquareModulus() < Precision::SquareConfusion()) // coplanar case
156 getProjectionAxes (aTrng0Normal, anX, anY);
158 if (rayInsideAngle (aTrng1Edges[0], aTrng0Edges[0], aTrng0Edges[1], anX, anY)
159 || rayInsideAngle (aTrng1Edges[1], aTrng0Edges[0], aTrng0Edges[1], anX, anY)
160 || rayInsideAngle (aTrng0Edges[0], aTrng1Edges[0], aTrng1Edges[1], anX, anY)
161 || rayInsideAngle (aTrng0Edges[1], aTrng1Edges[0], aTrng1Edges[1], anX, anY))
163 return BRepExtrema_ElementFilter::Overlap;
166 return BRepExtrema_ElementFilter::NoCheck;
168 else // shared line should lie outside at least one triangle
170 getProjectionAxes (aTrng0Normal, anX, anY);
172 const Standard_Boolean aPosOutTrgn0 = !rayInsideAngle ( aCrossLine, aTrng0Edges[0], aTrng0Edges[1], anX, anY);
173 const Standard_Boolean aNegOutTrgn0 = !rayInsideAngle (-aCrossLine, aTrng0Edges[0], aTrng0Edges[1], anX, anY);
175 Standard_ASSERT_RAISE (aPosOutTrgn0 || aNegOutTrgn0,
176 "Failed to detect if shared vertex is regular or not");
178 if (aPosOutTrgn0 && aNegOutTrgn0)
180 return BRepExtrema_ElementFilter::NoCheck;
183 getProjectionAxes (aTrng1Normal, anX, anY);
185 const Standard_Boolean aPosOutTrgn1 = !rayInsideAngle ( aCrossLine, aTrng1Edges[0], aTrng1Edges[1], anX, anY);
186 const Standard_Boolean aNegOutTrgn1 = !rayInsideAngle (-aCrossLine, aTrng1Edges[0], aTrng1Edges[1], anX, anY);
188 Standard_ASSERT_RAISE (aPosOutTrgn1 || aNegOutTrgn1,
189 "Failed to detect if shared vertex is regular or not");
191 if (aPosOutTrgn1 && aNegOutTrgn1)
193 return BRepExtrema_ElementFilter::NoCheck;
196 return (aPosOutTrgn0 || aPosOutTrgn1) && (aNegOutTrgn0 || aNegOutTrgn1) ?
197 BRepExtrema_ElementFilter::NoCheck : BRepExtrema_ElementFilter::Overlap;
201 //=======================================================================
202 //function : isRegularSharedEdge
204 //=======================================================================
205 BRepExtrema_ElementFilter::FilterResult BRepExtrema_SelfIntersection::isRegularSharedEdge (const BVH_Vec3d& theTrng0Vtxs0,
206 const BVH_Vec3d& theTrng0Vtxs1,
207 const BVH_Vec3d& theTrng0Vtxs2,
208 const BVH_Vec3d& theTrng1Vtxs2)
210 const BVH_Vec3d aSharedEdge = (theTrng0Vtxs1 - theTrng0Vtxs0).Normalized();
212 const BVH_Vec3d aUniqueEdges[] = { (theTrng0Vtxs2 - theTrng0Vtxs0).Normalized(),
213 (theTrng1Vtxs2 - theTrng0Vtxs0).Normalized() };
215 const BVH_Vec3d aTrng0Normal = BVH_Vec3d::Cross (aSharedEdge, aUniqueEdges[0]);
216 const BVH_Vec3d aTrng1Normal = BVH_Vec3d::Cross (aSharedEdge, aUniqueEdges[1]);
218 BVH_Vec3d aCrossLine = BVH_Vec3d::Cross (aTrng0Normal,
221 if (aCrossLine.SquareModulus() > Precision::SquareConfusion()) // non-coplanar case
223 return BRepExtrema_ElementFilter::NoCheck;
226 Standard_Integer anX;
227 Standard_Integer anY;
229 getProjectionAxes (aTrng0Normal, anX, anY);
231 return ccw (ZERO_VEC, aSharedEdge, aUniqueEdges[0], anX, anY) !=
232 ccw (ZERO_VEC, aSharedEdge, aUniqueEdges[1], anX, anY) ? BRepExtrema_ElementFilter::NoCheck
233 : BRepExtrema_ElementFilter::Overlap;
236 //=======================================================================
237 //function : PreCheckElements
239 //=======================================================================
240 BRepExtrema_ElementFilter::FilterResult BRepExtrema_SelfIntersection::PreCheckElements (const Standard_Integer theIndex1,
241 const Standard_Integer theIndex2)
243 if (myElementSet->GetFaceID (theIndex1) == myElementSet->GetFaceID (theIndex2))
245 return BRepExtrema_ElementFilter::NoCheck; // triangles are from the same face
248 BVH_Vec3d aTrng0Vtxs[3];
249 BVH_Vec3d aTrng1Vtxs[3];
251 myElementSet->GetVertices (theIndex1,
256 myElementSet->GetVertices (theIndex2,
261 std::vector<std::pair<Standard_Integer, Standard_Integer> > aSharedVtxs;
263 for (Standard_Integer aVertIdx1 = 0; aVertIdx1 < 3; ++aVertIdx1)
265 for (Standard_Integer aVertIdx2 = 0; aVertIdx2 < 3; ++aVertIdx2)
267 if ((aTrng0Vtxs[aVertIdx1] - aTrng1Vtxs[aVertIdx2]).SquareModulus() < Precision::SquareConfusion())
269 aSharedVtxs.push_back (std::pair<Standard_Integer, Standard_Integer> (aVertIdx1, aVertIdx2));
271 break; // go to next vertex of the 1st triangle
276 if (aSharedVtxs.size() == 2) // check shared edge
278 return isRegularSharedEdge (aTrng0Vtxs[aSharedVtxs[0].first],
279 aTrng0Vtxs[aSharedVtxs[1].first],
280 aTrng0Vtxs[3 - aSharedVtxs[0]. first - aSharedVtxs[1]. first],
281 aTrng1Vtxs[3 - aSharedVtxs[0].second - aSharedVtxs[1].second]);
283 else if (aSharedVtxs.size() == 1) // check shared vertex
285 std::swap (*aTrng0Vtxs, aTrng0Vtxs[aSharedVtxs.front(). first]);
286 std::swap (*aTrng1Vtxs, aTrng1Vtxs[aSharedVtxs.front().second]);
288 return isRegularSharedVertex (aTrng0Vtxs[0],
295 return BRepExtrema_ElementFilter::DoCheck;
298 //=======================================================================
301 //=======================================================================
302 void BRepExtrema_SelfIntersection::Perform()
304 if (!myIsInit || myOverlapTool.IsDone())
309 myOverlapTool.SetElementFilter (this);
311 myOverlapTool.Perform (myTolerance);