ae9a414a |
1 | // Created on: 2015-04-26 |
2 | // Created by: Denis BOGOLEPOV |
3 | // Copyright (c) 2014 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 <BRepExtrema_SelfIntersection.hxx> |
17 | |
18 | #include <Precision.hxx> |
19 | #include <TopExp_Explorer.hxx> |
20 | |
21 | //======================================================================= |
22 | //function : BRepExtrema_SelfIntersection |
23 | //purpose : |
24 | //======================================================================= |
25 | BRepExtrema_SelfIntersection::BRepExtrema_SelfIntersection (const Standard_Real theTolerance) |
26 | : myTolerance (theTolerance) |
27 | { |
28 | myIsInit = Standard_False; |
29 | } |
30 | |
31 | //======================================================================= |
32 | //function : BRepExtrema_SelfIntersection |
33 | //purpose : |
34 | //======================================================================= |
35 | BRepExtrema_SelfIntersection::BRepExtrema_SelfIntersection (const TopoDS_Shape& theShape, const Standard_Real theTolerance) |
36 | : myTolerance (theTolerance) |
37 | { |
38 | LoadShape (theShape); |
39 | } |
40 | |
41 | //======================================================================= |
42 | //function : LoadShape |
43 | //purpose : |
44 | //======================================================================= |
45 | Standard_Boolean BRepExtrema_SelfIntersection::LoadShape (const TopoDS_Shape& theShape) |
46 | { |
47 | myFaceList.Clear(); |
48 | |
49 | for (TopExp_Explorer anIter (theShape, TopAbs_FACE); anIter.More(); anIter.Next()) |
50 | { |
51 | myFaceList.Append (static_cast<const TopoDS_Face&> (anIter.Current())); |
52 | } |
53 | |
54 | if (myElementSet.IsNull()) |
55 | { |
56 | myElementSet = new BRepExtrema_TriangleSet; |
57 | } |
58 | |
59 | myIsInit = myElementSet->Init (myFaceList); |
60 | |
61 | if (myIsInit) |
62 | { |
63 | myOverlapTool.LoadTriangleSets (myElementSet, |
64 | myElementSet); |
65 | } |
66 | |
67 | return myIsInit; |
68 | } |
69 | |
70 | #define ZERO_VEC BVH_Vec3d (0.0, 0.0, 0.0) |
71 | |
72 | namespace |
73 | { |
74 | // ======================================================================= |
75 | // function : ccw |
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) |
83 | { |
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]); |
88 | |
89 | return aSum < 0.0; |
90 | } |
91 | |
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) |
101 | { |
102 | const Standard_Boolean aCCW = ccw (ZERO_VEC, theEdge0, theEdge1, theX, theY); |
103 | |
104 | return ccw (ZERO_VEC, theEdge0, theDirec, theX, theY) == aCCW |
105 | && ccw (ZERO_VEC, theDirec, theEdge1, theX, theY) == aCCW; |
106 | } |
107 | |
108 | // ======================================================================= |
109 | // function : getProjectionAxes |
110 | // purpose : |
111 | // ======================================================================= |
112 | void getProjectionAxes (const BVH_Vec3d& theNorm, |
113 | Standard_Integer& theAxisX, |
114 | Standard_Integer& theAxisY) |
115 | { |
116 | if (fabs (theNorm[0]) > fabs (theNorm[1])) |
117 | { |
118 | theAxisX = fabs (theNorm[0]) > fabs (theNorm[2]) ? 1 : 0; |
119 | theAxisY = fabs (theNorm[0]) > fabs (theNorm[2]) ? 2 : 1; |
120 | } |
121 | else |
122 | { |
123 | theAxisX = fabs (theNorm[1]) > fabs (theNorm[2]) ? 0 : 0; |
124 | theAxisY = fabs (theNorm[1]) > fabs (theNorm[2]) ? 2 : 1; |
125 | } |
126 | } |
127 | } |
128 | |
129 | //======================================================================= |
130 | //function : isRegularSharedVertex |
131 | //purpose : |
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) |
138 | { |
139 | const BVH_Vec3d aTrng0Edges[] = { (theTrng0Vtxs1 - theSharedVert).Normalized(), |
140 | (theTrng0Vtxs2 - theSharedVert).Normalized() }; |
141 | |
142 | const BVH_Vec3d aTrng1Edges[] = { (theTrng1Vtxs1 - theSharedVert).Normalized(), |
143 | (theTrng1Vtxs2 - theSharedVert).Normalized() }; |
144 | |
145 | const BVH_Vec3d aTrng0Normal = BVH_Vec3d::Cross (aTrng0Edges[0], aTrng0Edges[1]); |
146 | const BVH_Vec3d aTrng1Normal = BVH_Vec3d::Cross (aTrng1Edges[0], aTrng1Edges[1]); |
147 | |
148 | BVH_Vec3d aCrossLine = BVH_Vec3d::Cross (aTrng0Normal, |
149 | aTrng1Normal); |
150 | |
151 | Standard_Integer anX; |
152 | Standard_Integer anY; |
153 | |
154 | if (aCrossLine.SquareModulus() < Precision::SquareConfusion()) // coplanar case |
155 | { |
156 | getProjectionAxes (aTrng0Normal, anX, anY); |
157 | |
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)) |
162 | { |
163 | return BRepExtrema_ElementFilter::Overlap; |
164 | } |
165 | |
166 | return BRepExtrema_ElementFilter::NoCheck; |
167 | } |
168 | else // shared line should lie outside at least one triangle |
169 | { |
170 | getProjectionAxes (aTrng0Normal, anX, anY); |
171 | |
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); |
174 | |
175 | Standard_ASSERT_RAISE (aPosOutTrgn0 || aNegOutTrgn0, |
176 | "Failed to detect if shared vertex is regular or not"); |
177 | |
178 | if (aPosOutTrgn0 && aNegOutTrgn0) |
179 | { |
180 | return BRepExtrema_ElementFilter::NoCheck; |
181 | } |
182 | |
183 | getProjectionAxes (aTrng1Normal, anX, anY); |
184 | |
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); |
187 | |
188 | Standard_ASSERT_RAISE (aPosOutTrgn1 || aNegOutTrgn1, |
189 | "Failed to detect if shared vertex is regular or not"); |
190 | |
191 | if (aPosOutTrgn1 && aNegOutTrgn1) |
192 | { |
193 | return BRepExtrema_ElementFilter::NoCheck; |
194 | } |
195 | |
196 | return (aPosOutTrgn0 || aPosOutTrgn1) && (aNegOutTrgn0 || aNegOutTrgn1) ? |
197 | BRepExtrema_ElementFilter::NoCheck : BRepExtrema_ElementFilter::Overlap; |
198 | } |
199 | } |
200 | |
201 | //======================================================================= |
202 | //function : isRegularSharedEdge |
203 | //purpose : |
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) |
209 | { |
210 | const BVH_Vec3d aSharedEdge = (theTrng0Vtxs1 - theTrng0Vtxs0).Normalized(); |
211 | |
212 | const BVH_Vec3d aUniqueEdges[] = { (theTrng0Vtxs2 - theTrng0Vtxs0).Normalized(), |
213 | (theTrng1Vtxs2 - theTrng0Vtxs0).Normalized() }; |
214 | |
215 | const BVH_Vec3d aTrng0Normal = BVH_Vec3d::Cross (aSharedEdge, aUniqueEdges[0]); |
216 | const BVH_Vec3d aTrng1Normal = BVH_Vec3d::Cross (aSharedEdge, aUniqueEdges[1]); |
217 | |
218 | BVH_Vec3d aCrossLine = BVH_Vec3d::Cross (aTrng0Normal, |
219 | aTrng1Normal); |
220 | |
221 | if (aCrossLine.SquareModulus() > Precision::SquareConfusion()) // non-coplanar case |
222 | { |
223 | return BRepExtrema_ElementFilter::NoCheck; |
224 | } |
225 | |
226 | Standard_Integer anX; |
227 | Standard_Integer anY; |
228 | |
229 | getProjectionAxes (aTrng0Normal, anX, anY); |
230 | |
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; |
234 | } |
235 | |
236 | //======================================================================= |
237 | //function : PreCheckElements |
238 | //purpose : |
239 | //======================================================================= |
240 | BRepExtrema_ElementFilter::FilterResult BRepExtrema_SelfIntersection::PreCheckElements (const Standard_Integer theIndex1, |
241 | const Standard_Integer theIndex2) |
242 | { |
243 | if (myElementSet->GetFaceID (theIndex1) == myElementSet->GetFaceID (theIndex2)) |
244 | { |
245 | return BRepExtrema_ElementFilter::NoCheck; // triangles are from the same face |
246 | } |
247 | |
248 | BVH_Vec3d aTrng0Vtxs[3]; |
249 | BVH_Vec3d aTrng1Vtxs[3]; |
250 | |
251 | myElementSet->GetVertices (theIndex1, |
252 | aTrng0Vtxs[0], |
253 | aTrng0Vtxs[1], |
254 | aTrng0Vtxs[2]); |
255 | |
256 | myElementSet->GetVertices (theIndex2, |
257 | aTrng1Vtxs[0], |
258 | aTrng1Vtxs[1], |
259 | aTrng1Vtxs[2]); |
260 | |
261 | std::vector<std::pair<Standard_Integer, Standard_Integer> > aSharedVtxs; |
262 | |
263 | for (Standard_Integer aVertIdx1 = 0; aVertIdx1 < 3; ++aVertIdx1) |
264 | { |
265 | for (Standard_Integer aVertIdx2 = 0; aVertIdx2 < 3; ++aVertIdx2) |
266 | { |
267 | if ((aTrng0Vtxs[aVertIdx1] - aTrng1Vtxs[aVertIdx2]).SquareModulus() < Precision::SquareConfusion()) |
268 | { |
269 | aSharedVtxs.push_back (std::pair<Standard_Integer, Standard_Integer> (aVertIdx1, aVertIdx2)); |
270 | |
271 | break; // go to next vertex of the 1st triangle |
272 | } |
273 | } |
274 | } |
275 | |
276 | if (aSharedVtxs.size() == 2) // check shared edge |
277 | { |
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]); |
282 | } |
283 | else if (aSharedVtxs.size() == 1) // check shared vertex |
284 | { |
285 | std::swap (*aTrng0Vtxs, aTrng0Vtxs[aSharedVtxs.front(). first]); |
286 | std::swap (*aTrng1Vtxs, aTrng1Vtxs[aSharedVtxs.front().second]); |
287 | |
288 | return isRegularSharedVertex (aTrng0Vtxs[0], |
289 | aTrng0Vtxs[1], |
290 | aTrng0Vtxs[2], |
291 | aTrng1Vtxs[1], |
292 | aTrng1Vtxs[2]); |
293 | } |
294 | |
295 | return BRepExtrema_ElementFilter::DoCheck; |
296 | } |
297 | |
298 | //======================================================================= |
299 | //function : Perform |
300 | //purpose : |
301 | //======================================================================= |
302 | void BRepExtrema_SelfIntersection::Perform() |
303 | { |
304 | if (!myIsInit || myOverlapTool.IsDone()) |
305 | { |
306 | return; |
307 | } |
308 | |
309 | myOverlapTool.SetElementFilter (this); |
310 | |
311 | myOverlapTool.Perform (myTolerance); |
312 | } |