0028002: Invalid result of Boolean Fuse operation
[occt.git] / src / BRepClass3d / BRepClass3d_SolidExplorer.cxx
1 // Created on: 1994-03-10
2 // Created by: Laurent BUCHARD
3 // Copyright (c) 1994-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17 // Modifed:     Porting NT 7-5-97 DPF (stdio.h)
18 //              Apr 16 2002 eap, classification against infinite solid (occ299)
19
20
21 //  Modified by skv - Thu Sep  4 12:29:30 2003 OCC578
22
23 //-- Process the case of a hole!!
24 #define REJECTION 1
25
26 //-- To printf on NT
27
28 #include <Bnd_Box.hxx>
29 #include <BRep_Tool.hxx>
30 #include <BRepAdaptor_Curve2d.hxx>
31 #include <BRepAdaptor_HSurface.hxx>
32 #include <BRepAdaptor_Surface.hxx>
33 #include <BRepBndLib.hxx>
34 #include <BRepClass3d_DataMapIteratorOfMapOfInter.hxx>
35 #include <BRepClass3d_SolidExplorer.hxx>
36 #include <BRepClass_Edge.hxx>
37 #include <BRepClass_FaceClassifier.hxx>
38 #include <BRepClass_FacePassiveClassifier.hxx>
39 #include <BRepTools.hxx>
40 #include <BRepTopAdaptor_FClass2d.hxx>
41 #include <ElCLib.hxx>
42 #include <Extrema_ExtPS.hxx>
43 #include <Geom2d_Curve.hxx>
44 #include <GeomAbs_Shape.hxx>
45 #include <gp.hxx>
46 #include <gp_Lin.hxx>
47 #include <gp_Pnt.hxx>
48 #include <gp_Vec.hxx>
49 #include <gp_Vec2d.hxx>
50 #include <IntCurvesFace_Intersector.hxx>
51 #include <Precision.hxx>
52 #include <TopAbs_Orientation.hxx>
53 #include <TopExp_Explorer.hxx>
54 #include <TopoDS.hxx>
55 #include <TopoDS_Face.hxx>
56 #include <TopoDS_Shape.hxx>
57 #include <TopoDS_Shell.hxx>
58 #include <TopExp.hxx>
59
60 #include <stdio.h>
61 //OCC454(apo)->
62 //<-OCC454(apo)
63 //=======================================================================
64 //function : FindAPointInTheFace
65 //purpose  : Compute a point P in the face  F. Param is a Real in
66 //           ]0,1[ and   is  used to  initialise  the algorithm. For
67 //           different values , different points are returned.
68 //=======================================================================
69 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
70 (const TopoDS_Face& _face,
71  gp_Pnt& APoint_,
72  Standard_Real& param_)
73 {
74   Standard_Real u,v;
75   Standard_Boolean r = FindAPointInTheFace(_face,APoint_,u,v,param_);
76   return r;
77 }
78
79 //=======================================================================
80 //function : FindAPointInTheFace
81 //purpose  : 
82 //=======================================================================
83
84 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
85 (const TopoDS_Face& _face,
86  gp_Pnt& APoint_,
87  Standard_Real& u_, Standard_Real& v_,
88  Standard_Real& param_)
89 {
90   gp_Vec aVecD1U, aVecD1V;
91   return FindAPointInTheFace (_face, APoint_, u_, v_, param_, aVecD1U, aVecD1V);
92 }
93
94 //=======================================================================
95 //function : FindAPointInTheFace
96 //purpose  : 
97 //=======================================================================
98
99 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
100 (const TopoDS_Face& _face,
101  gp_Pnt& APoint_,
102  Standard_Real& u_, Standard_Real& v_,
103  Standard_Real& param_,
104  gp_Vec& theVecD1U,
105  gp_Vec& theVecD1V)
106 {
107   TopoDS_Face face = _face;
108   face.Orientation (TopAbs_FORWARD);
109
110   TopExp_Explorer faceexplorer;
111   BRepAdaptor_Curve2d c;
112   gp_Vec2d T;
113   gp_Pnt2d P;
114
115   for (faceexplorer.Init(face,TopAbs_EDGE); 
116        faceexplorer.More(); 
117        faceexplorer.Next())
118   {
119     TopoDS_Edge Edge = TopoDS::Edge (faceexplorer.Current());
120     c.Initialize (Edge, face);
121     c.D1((c.LastParameter() - c.FirstParameter()) * param_ + c.FirstParameter(),P,T);
122
123     Standard_Real x = T.X();
124     Standard_Real y = T.Y();
125     if (Edge.Orientation() == TopAbs_FORWARD)
126     {
127       T.SetCoord (-y,  x);
128     }
129     else
130     {
131       T.SetCoord ( y, -x);
132     }
133     Standard_Real ParamInit = RealLast();
134     Standard_Real TolInit   = 0.00001;
135     Standard_Boolean APointExist = Standard_False;
136
137     BRepClass_FacePassiveClassifier FClassifier;
138
139     T.Normalize();
140     P.SetCoord (P.X() + TolInit * T.X(), P.Y() + TolInit * T.Y());
141     FClassifier.Reset (gp_Lin2d (P, T), ParamInit, RealEpsilon()); //-- Length and Tolerance #######
142
143     TopExp_Explorer otherfaceexplorer;
144     Standard_Integer aNbEdges = 0;
145     for (otherfaceexplorer.Init (face, TopAbs_EDGE);
146          otherfaceexplorer.More(); 
147          otherfaceexplorer.Next(), ++aNbEdges)
148     {
149       TopoDS_Edge OtherEdge = TopoDS::Edge (otherfaceexplorer.Current());
150       if (OtherEdge.Orientation() != TopAbs_EXTERNAL && OtherEdge != Edge)
151       {
152         BRepClass_Edge AEdge (OtherEdge, face);
153         FClassifier.Compare (AEdge, OtherEdge.Orientation());
154         if (FClassifier.ClosestIntersection())
155         {
156           if(ParamInit > FClassifier.Parameter())
157           {
158             ParamInit = FClassifier.Parameter();
159             APointExist = Standard_True;
160           }
161         }
162       }
163     }
164
165     if (aNbEdges == 1)
166     {
167       BRepClass_Edge AEdge (Edge, face);
168       FClassifier.Compare (AEdge, Edge.Orientation());
169       if (FClassifier.ClosestIntersection())
170       {
171         if (ParamInit > FClassifier.Parameter())
172         {
173           ParamInit = FClassifier.Parameter();
174           APointExist = Standard_True;
175         }
176       }
177     }
178
179     while (APointExist)
180     { 
181       ParamInit *= 0.41234;
182       u_ = P.X() + ParamInit* T.X();
183       v_ = P.Y() + ParamInit* T.Y();
184
185       //Additional check
186       BRepTopAdaptor_FClass2d Classifier(face, Precision::Confusion());
187       gp_Pnt2d aPnt2d(u_, v_);
188       TopAbs_State StateOfResultingPoint = Classifier.Perform(aPnt2d);
189       if (StateOfResultingPoint != TopAbs_IN)
190         return Standard_False;
191       
192       BRepAdaptor_Surface s;
193       s.Initialize (face, Standard_False);
194       s.D1 (u_, v_, APoint_, theVecD1U, theVecD1V);
195
196       if(theVecD1U.CrossMagnitude(theVecD1V) > gp::Resolution())
197         return Standard_True;
198
199       if(ParamInit < Precision::PConfusion())
200         return Standard_False;
201     }
202   }
203   return Standard_False;
204 }
205
206 //=======================================================================
207 //function : PointInTheFace
208 //purpose  : 
209 //=======================================================================
210
211 Standard_Boolean BRepClass3d_SolidExplorer::PointInTheFace
212 (const TopoDS_Face& Face,
213  gp_Pnt& APoint_,
214  Standard_Real& u_, Standard_Real& v_,
215  Standard_Real& param_,
216  Standard_Integer& IndexPoint,
217  const Handle(BRepAdaptor_HSurface)& surf,
218  const Standard_Real U1,
219  const Standard_Real V1,
220  const Standard_Real U2,
221  const Standard_Real V2) const
222 {
223   gp_Vec aVecD1U, aVecD1V;
224   return PointInTheFace (Face, APoint_, u_, v_, param_, IndexPoint, surf,
225                          U1, V1, U2, V2, aVecD1U, aVecD1V);
226 }
227
228 //=======================================================================
229 //function : ClassifyUVPoint
230 //purpose  : 
231 //=======================================================================
232
233 TopAbs_State BRepClass3d_SolidExplorer::ClassifyUVPoint
234                    (const IntCurvesFace_Intersector& theIntersector,
235                     const Handle(BRepAdaptor_HSurface)& theSurf,
236                     const gp_Pnt2d& theP2d) const
237 {
238   // first find if the point is near an edge/vertex
239   gp_Pnt aP3d = theSurf->Value(theP2d.X(), theP2d.Y());
240   BRepClass3d_BndBoxTreeSelectorPoint aSelectorPoint(myMapEV);
241   aSelectorPoint.SetCurrentPoint(aP3d);
242   Standard_Integer aSelsVE = myTree.Select(aSelectorPoint);
243   if (aSelsVE > 0)
244   {
245     // The point is inside the tolerance area of vertices/edges => return ON state.
246     return TopAbs_ON;
247   }
248   return theIntersector.ClassifyUVPoint(theP2d);
249 }
250
251 //=======================================================================
252 //function : PointInTheFace
253 //purpose  : 
254 //=======================================================================
255
256 Standard_Boolean BRepClass3d_SolidExplorer::PointInTheFace
257 (const TopoDS_Face& Face,
258  gp_Pnt& APoint_,
259  Standard_Real& u_, Standard_Real& v_,
260  Standard_Real& param_,
261  Standard_Integer& IndexPoint,
262  const Handle(BRepAdaptor_HSurface)& surf,
263  const Standard_Real U1,
264  const Standard_Real V1,
265  const Standard_Real U2,
266  const Standard_Real V2,
267  gp_Vec& theVecD1U,
268  gp_Vec& theVecD1V) const
269 {
270   Standard_Real u,du = (U2-U1)/6.0;
271   Standard_Real v,dv = (V2-V1)/6.0;
272   if(du<1e-12) du=1e-12;
273   if(dv<1e-12) dv=1e-12;
274   Standard_Boolean IsNotUper = !surf->IsUPeriodic(), IsNotVper = !surf->IsVPeriodic();
275   Standard_Integer NbPntCalc=0;
276   if(myMapOfInter.IsBound(Face)) { 
277     void *ptr = (void*)(myMapOfInter.Find(Face));
278     Standard_Boolean IsInside = Standard_True;
279     if(IsNotUper)
280     {
281       IsInside = (u_ >= U1) && (u_ <= U2);
282     }
283     if(IsNotVper)
284     {
285       IsInside &= (v_ >= V1) && (v_ <= V2);
286     }
287     if(ptr) { 
288       const IntCurvesFace_Intersector& TheIntersector = (*((IntCurvesFace_Intersector *)ptr));
289       // Check if the point is already in the face
290       if (IsInside && (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u_, v_)) == TopAbs_IN)) {
291         gp_Pnt aPnt;
292         surf->D1(u_, v_, aPnt, theVecD1U, theVecD1V);
293         if (aPnt.SquareDistance(APoint_) < Precision::Confusion() * Precision::Confusion())
294           return Standard_True;
295       }
296
297       //-- Take 4 points in each Quarter of surface
298       //-- -> Index : 1 -> 16
299       //-- 
300       //--
301       //--  Then take a matrix of points on a tight grid
302       //--
303       for(u=du+(U1+U2)*0.5; u<U2; u+=du) {          //--  0  X    u increases
304         for(v=dv+(V1+V2)*0.5; v<V2; v+=dv) {        //--  0  0    v increases
305           if(++NbPntCalc>=IndexPoint) { 
306             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
307               u_=u; v_=v;
308               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
309               IndexPoint = NbPntCalc;
310               return(Standard_True);
311             }
312           }
313         }
314       }
315           
316       for(u=-du+(U1+U2)*0.5; u>U1; u-=du) {         //--  0  0    u decreases
317         for(v=-dv+(V1+V2)*0.5; v>V1; v-=dv) {       //--  X  0    v decreases
318           if(++NbPntCalc>=IndexPoint) {
319             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
320               u_=u; v_=v;
321               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
322               IndexPoint = NbPntCalc;
323               return(Standard_True);
324             }
325           }
326         }
327       }
328       for(u=-du+(U1+U2)*0.5; u>U1; u-=du) {         //--  X  0    u decreases
329         for(v=dv+(V1+V2)*0.5; v<V2; v+=dv) {        //--  0  0    v increases
330           if(++NbPntCalc>=IndexPoint) { 
331             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
332               u_=u; v_=v;
333               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
334               IndexPoint = NbPntCalc;
335               return(Standard_True);
336             }
337           }
338         }
339       }
340       for(u=du+(U1+U2)*0.5; u<U2; u+=du) {         //--  0  0     u increases
341         for(v=-dv+(V1+V2)*0.5; v>V1; v-=dv) {      //--  0  X     v decreases
342           if(++NbPntCalc>=IndexPoint) {
343             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
344               u_=u; v_=v;
345               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
346               IndexPoint = NbPntCalc;
347               return(Standard_True);
348             }
349           }
350         }
351       }
352       //-- the remainder
353       du = (U2-U1)/37.0;
354       dv = (V2-V1)/37.0;
355       if(du<1e-12) du=1e-12;
356       if(dv<1e-12) dv=1e-12;
357       
358       for(u=du+U1; u<U2; u+=du) { 
359         for(v=dv+V1; v<V2; v+=dv) {
360           if(++NbPntCalc>=IndexPoint) {
361             if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
362               u_=u; v_=v;
363               surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
364               IndexPoint = NbPntCalc;
365               return(Standard_True);
366             }
367           }
368         }
369       }
370       u=(U1+U2)*0.5;
371       v=(V1+V2)*0.5;
372       if(++NbPntCalc>=IndexPoint) {
373         if (ClassifyUVPoint(TheIntersector, surf, gp_Pnt2d(u, v)) == TopAbs_IN) {
374           u_=u; v_=v;
375           surf->D1 (u, v, APoint_, theVecD1U, theVecD1V);
376           IndexPoint = NbPntCalc;
377           return(Standard_True);
378         }
379       }
380     }
381     IndexPoint = NbPntCalc;
382   }
383   else { 
384     //printf("BRepClass3d_SolidExplorer Face not found ds the map \n");
385   }
386
387   return BRepClass3d_SolidExplorer
388     ::FindAPointInTheFace (Face,APoint_, u_, v_, param_, theVecD1U, theVecD1V);
389 }
390
391 //=======================================================================
392 //function : LimitInfiniteUV
393 //purpose  : Limit infinite parameters
394 //=======================================================================
395 static void LimitInfiniteUV (Standard_Real& U1,
396                              Standard_Real& V1,
397                              Standard_Real& U2,
398                              Standard_Real& V2)
399 {
400   Standard_Boolean
401     infU1 = Precision::IsNegativeInfinite(U1),
402     infV1 = Precision::IsNegativeInfinite(V1),
403     infU2 = Precision::IsPositiveInfinite(U2),
404     infV2 = Precision::IsPositiveInfinite(V2);
405
406   if (infU1) U1 = -1e10;
407   if (infV1) V1 = -1e10;
408   if (infU2) U2 =  1e10;
409   if (infV2) V2 =  1e10;
410 }
411 //=======================================================================
412 //function : IsInfiniteUV
413 //purpose  : 
414 //=======================================================================
415 static Standard_Integer IsInfiniteUV (Standard_Real& U1, 
416                                       Standard_Real& V1,
417                                       Standard_Real& U2, 
418                                       Standard_Real& V2) 
419 {
420   Standard_Integer aVal = 0;
421
422   if (Precision::IsInfinite(U1))
423     aVal |= 1;
424
425   if (Precision::IsInfinite(V1))
426     aVal |= 2;
427
428   if (Precision::IsInfinite(U2))
429     aVal |= 4;
430
431   if (Precision::IsInfinite(V2))
432     aVal |= 8;
433
434   return aVal;
435 }
436 //<-OCC454
437 //  Modified by skv - Tue Sep 16 13:50:39 2003 OCC578 End
438 //=======================================================================
439 //function : OtherSegment
440 //purpose  : Returns  in <L>, <Par>  a segment having at least
441 //           one  intersection  with  the  shape  boundary  to
442 //           compute  intersections. 
443 //           The First Call to this method returns a line which
444 //           point to a point of the first face of the shape.
445 //           The Second Call provide a line to the second face
446 //           and so on. 
447 //=======================================================================
448 Standard_Integer BRepClass3d_SolidExplorer::OtherSegment(const gp_Pnt& P, 
449                                                          gp_Lin& L, 
450                                                          Standard_Real& _Par) 
451 {
452   const Standard_Real TolU = Precision::PConfusion();
453   const Standard_Real TolV = TolU;
454
455   TopoDS_Face         face;
456   TopExp_Explorer     faceexplorer;
457   gp_Pnt APoint;
458   gp_Vec aVecD1U, aVecD1V;
459   Standard_Real maxscal=0;
460   Standard_Boolean ptfound=Standard_False;
461   Standard_Real Par;
462   Standard_Real _u,_v;
463   Standard_Integer IndexPoint=0;
464   Standard_Integer NbPointsOK=0;
465   Standard_Integer NbFacesInSolid=0;
466   Standard_Boolean aRestr = Standard_True;
467   Standard_Boolean aTestInvert = Standard_False;
468
469   for(;;) { 
470     myFirstFace++; 
471     faceexplorer.Init(myShape,TopAbs_FACE);
472     // look for point on face starting from myFirstFace
473 //  Modified by skv - Thu Sep  4 14:31:12 2003 OCC578 Begin
474 //     while (faceexplorer.More()) {
475     NbFacesInSolid = 0;
476     for (; faceexplorer.More(); faceexplorer.Next()) {
477 //  Modified by skv - Thu Sep  4 14:31:12 2003 OCC578 End
478       NbFacesInSolid++;
479       if (myFirstFace > NbFacesInSolid) continue;
480       face = TopoDS::Face(faceexplorer.Current());
481
482       Handle(BRepAdaptor_HSurface) surf = new BRepAdaptor_HSurface();
483       if(aTestInvert)
484       {
485         BRepTopAdaptor_FClass2d aClass(face, Precision::Confusion());
486         if(aClass.PerformInfinitePoint() == TopAbs_IN)
487         {
488           aRestr = Standard_False;
489           if(myMapOfInter.IsBound(face))
490           {
491             myMapOfInter.UnBind(face);
492             void *ptr = (void *)(new IntCurvesFace_Intersector(face, Precision::Confusion(),
493                                                                aRestr, Standard_False));
494             myMapOfInter.Bind(face,ptr);
495           }
496         }
497         else
498         {
499           aRestr = Standard_True;
500         }
501       }
502       surf->ChangeSurface().Initialize(face, aRestr);
503       Standard_Real U1,V1,U2,V2;
504       U1 = surf->FirstUParameter();
505       V1 = surf->FirstVParameter();
506       U2 = surf->LastUParameter();
507       V2 = surf->LastVParameter();
508       face.Orientation(TopAbs_FORWARD);
509       //
510       //avoid process faces from uncorrected shells
511       const Standard_Real eps = Precision::PConfusion();
512       Standard_Real epsU = Max(eps * Max(Abs(U2), Abs(U1)), eps);
513       Standard_Real epsV = Max(eps * Max(Abs(V2), Abs(V1)), eps);
514       if( Abs (U2 - U1) < epsU || Abs(V2 - V1) < epsV) {
515         return 2;
516       }
517       //
518       Standard_Real svmyparam=myParamOnEdge;
519       //
520       // Check if the point is on the face or the face is infinite.
521       Standard_Integer anInfFlag = IsInfiniteUV(U1,V1,U2,V2);
522       // default values
523       _u = (U1 + U2) * 0.5;
524       _v = (V1 + V2) * 0.5;
525
526       GeomAdaptor_Surface GA(BRep_Tool::Surface(face));
527       Extrema_ExtPS Ext(P, GA, TolU, TolV);
528       //
529       if (Ext.IsDone() && Ext.NbExt() > 0) {
530         Standard_Integer i, iNear,  iEnd;
531         Standard_Real  aUx, aVx, Dist2, Dist2Min;
532         Extrema_POnSurf aPx;
533         //
534         iNear = 1;
535         Dist2Min = Ext.SquareDistance(1);
536         iEnd = Ext.NbExt();
537         for (i = 2; i <= iEnd; i++) {
538           aPx=Ext.Point(i);
539           aPx.Parameter(aUx, aVx);
540           if (aUx>=U1 && aUx<=U2 && aVx>=V1 && aVx<=V2) {
541             Dist2 = Ext.SquareDistance(i);
542             if (Dist2 < Dist2Min) {
543               Dist2Min = Dist2; 
544               iNear = i;
545             }
546           }
547         }
548         //
549         Standard_Real aDist2Tresh=1.e-24;
550         //
551         if (Dist2Min<aDist2Tresh) {
552           if (anInfFlag) {
553             return 1;
554           } 
555           else {
556             BRepClass_FaceClassifier classifier2d;
557             Standard_Real            aU;
558             Standard_Real            aV;
559
560             (Ext.Point(iNear)).Parameter(aU, aV);
561
562             gp_Pnt2d aPuv(aU, aV);
563
564             classifier2d.Perform(face,aPuv,Precision::PConfusion());
565
566             TopAbs_State aState = classifier2d.State();
567
568             if (aState == TopAbs_IN || aState == TopAbs_ON) {
569               return 1;
570             }
571             else {
572               return 3; // skv - the point is on surface but outside face.
573             }
574           }
575         }
576         if (anInfFlag) {
577           APoint = (Ext.Point(iNear)).Value();
578           gp_Vec V(P,APoint);
579           _Par = V.Magnitude(); 
580           L = gp_Lin(P,V);
581           ptfound=Standard_True;
582           return 0;
583         }
584
585         // set the parameters found by extrema
586         aPx = Ext.Point(iNear);
587         aPx.Parameter(_u, _v);
588         APoint = aPx.Value();
589       }
590       //The point is not ON the face or surface. The face is restricted.
591       // find point in a face not too far from a projection of P on face
592       do {
593         if (PointInTheFace (face, APoint, _u, _v, myParamOnEdge, ++IndexPoint, surf,
594                             U1, V1, U2, V2,
595                             aVecD1U, aVecD1V))
596         {
597           ++NbPointsOK;
598           gp_Vec V (P, APoint);
599           Par = V.Magnitude();
600           if (Par > gp::Resolution() &&
601               aVecD1U.Magnitude() > gp::Resolution() &&
602               aVecD1V.Magnitude() > gp::Resolution())
603           {
604             gp_Vec Norm = aVecD1U.Crossed (aVecD1V);
605             Standard_Real tt = Norm.Magnitude();
606             tt = Abs (Norm.Dot (V)) / (tt * Par);
607             if (tt > maxscal)
608             {
609               maxscal = tt;
610               L = gp_Lin (P, V);
611               _Par = Par;
612               ptfound = Standard_True;
613               if (maxscal>0.2)
614               {
615                 myParamOnEdge=svmyparam;
616                 return 0;
617               }
618             }
619           }
620         }
621       }
622       while(IndexPoint<200 && NbPointsOK<16);
623
624       myParamOnEdge=svmyparam;
625       if(maxscal>0.2) {                  
626         return 0;
627       }
628
629
630       //  Modified by skv - Thu Sep  4 14:32:14 2003 OCC578 Begin
631       // Next is done in the main for(..) loop.
632       //       faceexplorer.Next();
633       //  Modified by skv - Thu Sep  4 14:32:14 2003 OCC578 End
634       IndexPoint = 0;
635
636       Standard_Boolean encoreuneface = faceexplorer.More();
637       if(ptfound==Standard_False && encoreuneface==Standard_False) { 
638         if(myParamOnEdge < 0.0001) { 
639           //-- This case takes place when the point is on the solid
640           //-- and this solid is reduced to a face 
641           gp_Pnt PBidon(P.X()+1.0,P.Y(),P.Z());
642           gp_Vec V(P,PBidon);
643           Par= 1.0;
644           _Par=Par;
645           L  = gp_Lin(P,V);
646           return 0;
647         }
648       }
649     } //-- Exploration of the faces   
650
651     if(NbFacesInSolid==0) { 
652       _Par=0.0;
653       myReject=Standard_True;
654 #ifdef OCCT_DEBUG
655       cout<<"\nWARNING : BRepClass3d_SolidExplorer.cxx  (Solid without face)"<<endl;
656 #endif  
657       return 0;
658     }
659
660     if(ptfound) {
661       return 0;
662     }
663     myFirstFace = 0;
664     if(myParamOnEdge==0.512345)  myParamOnEdge = 0.4;
665     else if(myParamOnEdge==0.4)  myParamOnEdge = 0.6; 
666     else if(myParamOnEdge==0.6)  myParamOnEdge = 0.3; 
667     else if(myParamOnEdge==0.3)  myParamOnEdge = 0.7; 
668     else if(myParamOnEdge==0.7)  myParamOnEdge = 0.2; 
669     else if(myParamOnEdge==0.2)  myParamOnEdge = 0.8; 
670     else if(myParamOnEdge==0.8)  myParamOnEdge = 0.1; 
671     else if(myParamOnEdge==0.1)  myParamOnEdge = 0.9;
672     //
673     else {
674       myParamOnEdge*=0.5;  
675       if(myParamOnEdge < 0.0001) { 
676         gp_Pnt PBidon(P.X()+1.0,P.Y(),P.Z());
677         gp_Vec V(P,PBidon);
678         Par= 1.0;
679         _Par=Par;
680         L  = gp_Lin(P,V);
681         return 0;
682       }
683     }
684     aTestInvert = Standard_True;
685   } //-- for(;;) { ...  } 
686 }
687
688 //  Modified by skv - Thu Sep  4 12:30:14 2003 OCC578 Begin
689 //=======================================================================
690 //function : GetFaceSegmentIndex
691 //purpose  : Returns the index of face for which last segment is calculated.
692 //=======================================================================
693
694 Standard_Integer BRepClass3d_SolidExplorer::GetFaceSegmentIndex() const
695 {
696   return myFirstFace;
697 }
698 //  Modified by skv - Thu Sep  4 12:30:14 2003 OCC578 End
699
700 //=======================================================================
701 //function : PointInTheFace
702 //purpose  : 
703 //=======================================================================
704
705 Standard_Boolean BRepClass3d_SolidExplorer::PointInTheFace
706 (const TopoDS_Face& _face,
707  gp_Pnt& APoint_,
708  Standard_Real& u_, Standard_Real& v_,
709  Standard_Real& param_,
710  Standard_Integer& IndexPoint) const  
711 {   
712   TopoDS_Face Face = _face;
713   Face.Orientation(TopAbs_FORWARD);
714   Handle(BRepAdaptor_HSurface) surf = new BRepAdaptor_HSurface();
715   surf->ChangeSurface().Initialize(Face);
716   Standard_Real U1,V1,U2,V2;//,u,v;
717   U1 = surf->FirstUParameter();
718   V1 = surf->FirstVParameter();
719   U2 = surf->LastUParameter();
720   V2 = surf->LastVParameter();
721   LimitInfiniteUV (U1,V1,U2,V2);
722   return(PointInTheFace(Face,APoint_,u_,v_,param_,IndexPoint,surf,U1,V1,U2,V2));
723 }
724
725 //=======================================================================
726 //function : FindAPointInTheFace
727 //purpose  : 
728 //=======================================================================
729
730 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
731 (const TopoDS_Face& _face,
732  gp_Pnt& APoint_,
733  Standard_Real& u_,Standard_Real& v_) 
734 {
735   Standard_Real param = 0.1;
736   Standard_Boolean r = FindAPointInTheFace(_face,APoint_,u_,v_,param);
737   return r;
738 }
739
740 //=======================================================================
741 //function : FindAPointInTheFace
742 //purpose  : 
743 //=======================================================================
744
745 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
746 (const TopoDS_Face& _face,
747  gp_Pnt& APoint_) 
748 { Standard_Real u,v;
749   Standard_Boolean r = FindAPointInTheFace(_face,APoint_,u,v);
750   return r;
751 }
752
753 //=======================================================================
754 //function : FindAPointInTheFace
755 //purpose  : 
756 //=======================================================================
757
758 Standard_Boolean BRepClass3d_SolidExplorer::FindAPointInTheFace
759 (const TopoDS_Face& _face,
760  Standard_Real& u_,Standard_Real& v_) 
761 { gp_Pnt APoint;
762   Standard_Boolean r = FindAPointInTheFace(_face,APoint,u_,v_);
763   return r;
764 }
765
766 //=======================================================================
767 //function : BRepClass3d_SolidExplorer
768 //purpose  : 
769 //=======================================================================
770
771 BRepClass3d_SolidExplorer::BRepClass3d_SolidExplorer() 
772 {
773 }
774 #include <Standard_ConstructionError.hxx>
775
776 //=======================================================================
777 //function : BRepClass3d_SolidExplorer
778 //purpose  : Raise if called.
779 //=======================================================================
780
781 //BRepClass3d_SolidExplorer::BRepClass3d_SolidExplorer(const BRepClass3d_SolidExplorer& Oth) 
782 BRepClass3d_SolidExplorer::BRepClass3d_SolidExplorer(const BRepClass3d_SolidExplorer& ) 
783 {
784   Standard_ConstructionError::Raise("Magic constructor not allowed");
785 }
786
787 //=======================================================================
788 //function : BRepClass3d_SolidExplorer
789 //purpose  : 
790 //=======================================================================
791
792 BRepClass3d_SolidExplorer::BRepClass3d_SolidExplorer(const TopoDS_Shape& S)
793 {
794   InitShape(S);
795 }
796
797 //=======================================================================
798 //function : ~BRepClass3d_SolidExplorer
799 //purpose  :
800 //=======================================================================
801
802 BRepClass3d_SolidExplorer::~BRepClass3d_SolidExplorer()
803 {
804  Destroy() ;
805 }
806
807 //=======================================================================
808 //function : Destroy
809 //purpose  : C++: alias ~
810 //=======================================================================
811
812 void BRepClass3d_SolidExplorer::Destroy() { 
813   BRepClass3d_DataMapIteratorOfMapOfInter iter(myMapOfInter);
814   for(;iter.More();iter.Next()) { 
815     void *ptr=iter.Value();
816     if(ptr) { 
817       delete (IntCurvesFace_Intersector *)ptr;
818       myMapOfInter.ChangeFind(iter.Key()) = NULL;
819     }
820   }
821   myMapOfInter.Clear();
822 }
823
824 //=======================================================================
825 //function : InitShape
826 //purpose  : 
827 //=======================================================================
828
829 void BRepClass3d_SolidExplorer::InitShape(const TopoDS_Shape& S)
830 {
831   myMapEV.Clear();
832   myTree.Clear();
833
834   myShape = S;
835   myFirstFace = 0;
836   myParamOnEdge = 0.512345;
837   //-- Exploring of the Map and removal of allocated objects
838   
839   
840   BRepClass3d_DataMapIteratorOfMapOfInter iter(myMapOfInter);
841   for(;iter.More();iter.Next()) { 
842     void *ptr=iter.Value();
843     if(ptr) { 
844       delete (IntCurvesFace_Intersector *)ptr;
845       myMapOfInter.ChangeFind(iter.Key()) = NULL;
846     }
847   }
848   
849   myMapOfInter.Clear();
850   
851   myReject = Standard_True; //-- case of infinite solid (without any face)
852
853   TopExp_Explorer Expl;
854   for(Expl.Init(S,TopAbs_FACE);
855       Expl.More();
856       Expl.Next()) { 
857     const TopoDS_Face Face = TopoDS::Face(Expl.Current());
858     void *ptr = (void *)(new IntCurvesFace_Intersector(Face,Precision::Confusion(),Standard_True, Standard_False));
859     myMapOfInter.Bind(Face,ptr);
860     myReject=Standard_False;  //-- at least one face in the solid 
861   }
862   
863 #ifdef OCCT_DEBUG
864   if(myReject) { 
865     cout<<"\nWARNING : BRepClass3d_SolidExplorer.cxx  (Solid without face)"<<endl;
866   }
867 #endif
868
869 #if REJECTION
870   BRepBndLib::Add(myShape,myBox);
871 #endif
872
873   // since the internal/external parts should be avoided in tree filler,
874   // there is no need to add these parts in the EV map as well
875   TopExp_Explorer aExpF(myShape, TopAbs_FACE);
876   for (; aExpF.More(); aExpF.Next()) {
877     const TopoDS_Shape& aF = aExpF.Current();
878     //
879     TopAbs_Orientation anOrF = aF.Orientation();
880     if (anOrF == TopAbs_INTERNAL || anOrF == TopAbs_EXTERNAL) {
881       continue;
882     }
883     //
884     TopExp_Explorer aExpE(aF, TopAbs_EDGE);
885     for (; aExpE.More(); aExpE.Next()) {
886       const TopoDS_Shape& aE = aExpE.Current();
887       //
888       TopAbs_Orientation anOrE = aE.Orientation();
889       if (anOrE == TopAbs_INTERNAL || anOrE == TopAbs_EXTERNAL) {
890         continue;
891       }
892       //
893       if (BRep_Tool::Degenerated(TopoDS::Edge(aE))) {
894         continue;
895       }
896       //
897       TopExp::MapShapes(aE, myMapEV);
898     }
899   }
900   //
901   // Fill mapEV with vertices and edges from shape
902   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller (myTree);
903   //
904   Standard_Integer i, aNbEV = myMapEV.Extent();
905   for (i = 1; i <= aNbEV; ++i) {
906     const TopoDS_Shape& aS = myMapEV(i);
907     //
908     Bnd_Box aBox;
909     BRepBndLib::Add(aS, aBox);
910     aTreeFiller.Add(i, aBox);
911   }
912   aTreeFiller.Fill();
913 }
914
915 //=======================================================================
916 //function : Reject
917 //purpose  : Should return True if P outside of bounding vol. of the shape
918 //=======================================================================
919
920 //Standard_Boolean  BRepClass3d_SolidExplorer::Reject(const gp_Pnt& P) const 
921 Standard_Boolean  BRepClass3d_SolidExplorer::Reject(const gp_Pnt& ) const 
922 {
923   return(myReject);  // case of solid without face 
924 }
925
926 //=======================================================================
927 //function : InitShell
928 //purpose  : Starts an exploration of the shells.
929 //=======================================================================
930
931 void BRepClass3d_SolidExplorer::InitShell()  
932 {
933   myShellExplorer.Init(myShape,TopAbs_SHELL);
934 }
935
936 //=======================================================================
937 //function : MoreShell
938 //purpose  : Returns True if there is a current shell. 
939 //=======================================================================
940
941 Standard_Boolean BRepClass3d_SolidExplorer::MoreShell() const 
942
943   return(myShellExplorer.More());
944 }
945
946 //=======================================================================
947 //function : NextShell
948 //purpose  : Sets the explorer to the next shell.
949 //=======================================================================
950
951 void BRepClass3d_SolidExplorer::NextShell() 
952
953   myShellExplorer.Next();
954 }
955
956 //=======================================================================
957 //function : CurrentShell
958 //purpose  : Returns the current shell.
959 //=======================================================================
960
961 TopoDS_Shell BRepClass3d_SolidExplorer::CurrentShell() const 
962
963   return(TopoDS::Shell(myShellExplorer.Current()));
964 }
965
966 //=======================================================================
967 //function : RejectShell
968 //purpose  : Returns True if the Shell is rejected.
969 //=======================================================================
970
971 Standard_Boolean BRepClass3d_SolidExplorer::RejectShell(const gp_Lin& ) const
972
973   return(Standard_False); 
974 }
975
976 //=======================================================================
977 //function : InitFace
978 //purpose  : Starts an exploration of the faces of the current shell.
979 //=======================================================================
980
981 void BRepClass3d_SolidExplorer::InitFace()  
982 {
983   myFaceExplorer.Init(TopoDS::Shell(myShellExplorer.Current()),TopAbs_FACE);
984 }
985
986 //=======================================================================
987 //function : MoreFace
988 //purpose  : Returns True if current face in current shell. 
989 //=======================================================================
990
991 Standard_Boolean BRepClass3d_SolidExplorer::MoreFace() const 
992
993   return(myFaceExplorer.More());
994 }
995
996 //=======================================================================
997 //function : NextFace
998 //purpose  : Sets the explorer to the next Face of the current shell.
999 //=======================================================================
1000
1001 void BRepClass3d_SolidExplorer::NextFace() 
1002
1003   myFaceExplorer.Next();
1004 }
1005
1006 //=======================================================================
1007 //function : CurrentFace
1008 //purpose  : Returns the current face.
1009 //=======================================================================
1010
1011 TopoDS_Face BRepClass3d_SolidExplorer::CurrentFace() const 
1012
1013   return(TopoDS::Face(myFaceExplorer.Current()));
1014 }
1015
1016 //=======================================================================
1017 //function : RejectFace
1018 //purpose  : returns True if the face is rejected.
1019 //=======================================================================
1020
1021 Standard_Boolean BRepClass3d_SolidExplorer::RejectFace(const gp_Lin& ) const 
1022
1023   return(Standard_False); 
1024 }
1025
1026 #ifdef OCCT_DEBUG
1027 #include <TopAbs_State.hxx>
1028 #endif
1029
1030 //=======================================================================
1031 //function : Segment
1032 //purpose  : Returns  in <L>, <Par>  a segment having at least
1033 //           one  intersection  with  the  shape  boundary  to
1034 //           compute  intersections. 
1035 //=======================================================================
1036 Standard_Integer  BRepClass3d_SolidExplorer::Segment(const gp_Pnt& P, 
1037                                                      gp_Lin& L, 
1038                                                      Standard_Real& Par)  
1039 {
1040   Standard_Integer bRetFlag;
1041   myFirstFace = 0;
1042   bRetFlag=OtherSegment(P,L,Par);
1043   return bRetFlag;
1044 }
1045
1046 //=======================================================================
1047 //function : Intersector
1048 //purpose  : 
1049 //=======================================================================
1050
1051 IntCurvesFace_Intersector&  BRepClass3d_SolidExplorer::Intersector(const TopoDS_Face& F) const  { 
1052   void *ptr = (void*)(myMapOfInter.Find(F));
1053   IntCurvesFace_Intersector& curr = (*((IntCurvesFace_Intersector *)ptr));
1054   return curr;
1055 }
1056
1057 //=======================================================================
1058 //function : Box
1059 //purpose  : 
1060 //=======================================================================
1061
1062 const Bnd_Box& BRepClass3d_SolidExplorer::Box() const { 
1063   return(myBox);
1064 }
1065
1066 //=======================================================================
1067 //function : DumpSegment
1068 //purpose  : 
1069 //=======================================================================
1070
1071 void BRepClass3d_SolidExplorer::DumpSegment(const gp_Pnt&,
1072                                             const gp_Lin&,
1073                                             const Standard_Real,
1074                                             const TopAbs_State) const
1075 {
1076 #ifdef OCCT_DEBUG
1077  
1078 #endif
1079 }
1080
1081 const TopoDS_Shape& BRepClass3d_SolidExplorer::GetShape() const 
1082
1083   return(myShape);
1084 }