0026937: Eliminate NO_CXX_EXCEPTION macro support
[occt.git] / src / GeomInt / GeomInt_LineConstructor.cxx
1 // Created on: 1995-02-07
2 // Created by: Jacques GOUSSARD
3 // Copyright (c) 1995-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
18 #include <Adaptor2d_HCurve2d.hxx>
19 #include <Adaptor3d_TopolTool.hxx>
20 #include <ElCLib.hxx>
21 #include <GeomAbs_SurfaceType.hxx>
22 #include <GeomAdaptor_HSurface.hxx>
23 #include <GeomInt.hxx>
24 #include <GeomInt_LineConstructor.hxx>
25 #include <GeomInt_LineTool.hxx>
26 #include <GeomInt_ParameterAndOrientation.hxx>
27 #include <GeomInt_SequenceOfParameterAndOrientation.hxx>
28 #include <gp_Pnt2d.hxx>
29 #include <IntPatch_ALine.hxx>
30 #include <IntPatch_GLine.hxx>
31 #include <IntPatch_Line.hxx>
32 #include <IntPatch_Point.hxx>
33 #include <IntPatch_WLine.hxx>
34 #include <IntSurf_PntOn2S.hxx>
35 #include <IntSurf_Quadric.hxx>
36 #include <IntSurf_Transition.hxx>
37 #include <Precision.hxx>
38 #include <Standard_ConstructionError.hxx>
39 #include <Standard_OutOfRange.hxx>
40 #include <StdFail_NotDone.hxx>
41 #include <TColStd_IndexedMapOfInteger.hxx>
42 #include <TopAbs_Orientation.hxx>
43
44 static
45   void Parameters(const Handle(GeomAdaptor_HSurface)& myHS1,
46                   const gp_Pnt& Ptref,
47                   Standard_Real& U1,
48                   Standard_Real& V1);
49 static
50   void Parameters(const Handle(GeomAdaptor_HSurface)& myHS1,
51                   const Handle(GeomAdaptor_HSurface)& myHS2,
52                   const gp_Pnt& Ptref,
53                   Standard_Real& U1,
54                   Standard_Real& V1,
55                   Standard_Real& U2,
56                   Standard_Real& V2);
57
58 static 
59   void GLinePoint(const IntPatch_IType typl,
60                   const Handle(IntPatch_GLine)& GLine,
61                   const Standard_Real aT,
62                   gp_Pnt& aP);
63 static
64   void Recadre(const Handle(GeomAdaptor_HSurface)& myHS1,
65                const Handle(GeomAdaptor_HSurface)& myHS2,
66                Standard_Real& u1,
67                Standard_Real& v1,
68                Standard_Real& u2,
69                Standard_Real& v2);
70
71 //XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
72 //
73 //=======================================================================
74 //class    : GeomInt_RealWithFlag
75 //purpose  : 
76 //=======================================================================
77 class GeomInt_RealWithFlag {
78  public:
79   GeomInt_RealWithFlag() : 
80     myValue(-99.), myFlag(1) 
81   {
82   };
83   //
84   ~GeomInt_RealWithFlag() {
85   };
86   //
87   void SetValue(const Standard_Real aT) {
88     myValue=aT;
89   };
90   //
91   Standard_Real Value() const {
92     return myValue;
93   }
94   //
95   void SetFlag(const Standard_Integer aFlag) {
96     myFlag=aFlag;
97   };
98   //
99   Standard_Integer Flag() const {
100     return myFlag;
101   }
102   //
103   Standard_Boolean operator < (const GeomInt_RealWithFlag& aOther) {
104     return myValue<aOther.myValue;
105   }
106   //
107  protected:
108   Standard_Real myValue;
109   Standard_Integer myFlag;
110 };
111 //------------
112 static 
113   void SortShell(const Standard_Integer, 
114                  GeomInt_RealWithFlag *); 
115 static
116   void RejectDuplicates(Standard_Integer& aNbVtx, 
117                         GeomInt_RealWithFlag *pVtx, 
118                         Standard_Real aTolPrm);
119 static
120   void RejectNearBeacons(Standard_Integer& aNbVtx, 
121                          GeomInt_RealWithFlag *pVtx, 
122                          Standard_Real aTolPC1,
123                          const GeomAbs_SurfaceType aTS1,
124                          const GeomAbs_SurfaceType aTS2); 
125 static
126   Standard_Real AdjustOnPeriod(const Standard_Real aTr,
127                                const Standard_Real aPeriod);
128
129 static
130   Standard_Boolean RejectMicroCircle(const Handle(IntPatch_GLine)& aGLine,
131                                      const IntPatch_IType aType,
132                                      const Standard_Real aTol3D);
133
134 //=======================================================================
135 //function : Perform
136 //purpose  : 
137 //=======================================================================
138 void GeomInt_LineConstructor::Perform(const Handle(IntPatch_Line)& L)
139 {
140   Standard_Integer i,nbvtx;
141   Standard_Real firstp,lastp;
142   const Standard_Real Tol = Precision::PConfusion() * 35.0;
143   
144   const IntPatch_IType typl = L->ArcType();
145   if(typl == IntPatch_Analytic)  {
146     Standard_Real u1,v1,u2,v2;
147     Handle(IntPatch_ALine) ALine (Handle(IntPatch_ALine)::DownCast (L));
148     seqp.Clear();
149     nbvtx = GeomInt_LineTool::NbVertex(L);
150     for(i=1;i<nbvtx;i++)   {
151       firstp = GeomInt_LineTool::Vertex(L,i).ParameterOnLine();
152       lastp =  GeomInt_LineTool::Vertex(L,i+1).ParameterOnLine();
153       if(firstp!=lastp)      {
154         const Standard_Real pmid = (firstp+lastp)*0.5;
155         const gp_Pnt Pmid = ALine->Value(pmid);
156         Parameters(myHS1,myHS2,Pmid,u1,v1,u2,v2);
157         Recadre(myHS1,myHS2,u1,v1,u2,v2);
158         const TopAbs_State in1 = myDom1->Classify(gp_Pnt2d(u1,v1),Tol);
159         if(in1 !=  TopAbs_OUT) {
160           const TopAbs_State in2 = myDom2->Classify(gp_Pnt2d(u2,v2),Tol);
161           if(in2 != TopAbs_OUT) { 
162             seqp.Append(firstp);
163             seqp.Append(lastp);
164           }
165         }
166       }
167     }
168     done = Standard_True;
169     return;
170   } // if(typl == IntPatch_Analytic)  {
171   else if(typl == IntPatch_Walking)  {
172     Standard_Real u1,v1,u2,v2;
173     Handle(IntPatch_WLine) WLine (Handle(IntPatch_WLine)::DownCast (L));
174     seqp.Clear();
175     nbvtx = GeomInt_LineTool::NbVertex(L);
176     for(i=1;i<nbvtx;i++)    { 
177       firstp = GeomInt_LineTool::Vertex(L,i).ParameterOnLine();
178       lastp =  GeomInt_LineTool::Vertex(L,i+1).ParameterOnLine();
179       if(firstp!=lastp) { 
180         if(lastp != firstp+1)  {
181           const Standard_Integer pmid = (Standard_Integer )( (firstp+lastp)/2);
182           const IntSurf_PntOn2S& Pmid = WLine->Point(pmid);
183           Pmid.Parameters(u1,v1,u2,v2);
184           Recadre(myHS1,myHS2,u1,v1,u2,v2);
185           const TopAbs_State in1 = myDom1->Classify(gp_Pnt2d(u1,v1),Tol);
186           if(in1 !=  TopAbs_OUT) {   
187             const TopAbs_State in2 = myDom2->Classify(gp_Pnt2d(u2,v2),Tol);
188             if(in2 != TopAbs_OUT) {   
189               seqp.Append(firstp);
190               seqp.Append(lastp);
191             }
192           }
193         }
194         else {
195           const IntSurf_PntOn2S& Pfirst = WLine->Point((Standard_Integer)(firstp));
196           Pfirst.Parameters(u1,v1,u2,v2);
197           Recadre(myHS1,myHS2,u1,v1,u2,v2);
198           TopAbs_State in1 = myDom1->Classify(gp_Pnt2d(u1,v1),Tol);
199           if(in1 !=  TopAbs_OUT) {  //-- !=ON donne Pb 
200             TopAbs_State in2 = myDom2->Classify(gp_Pnt2d(u2,v2),Tol);
201             if(in2 != TopAbs_OUT) { //-- !=ON  
202               const IntSurf_PntOn2S& Plast = WLine->Point((Standard_Integer)(lastp));
203               Plast.Parameters(u1,v1,u2,v2);
204               Recadre(myHS1,myHS2,u1,v1,u2,v2);
205               in1 = myDom1->Classify(gp_Pnt2d(u1,v1),Tol);
206               if(in1 !=  TopAbs_OUT) {  //-- !=ON donne Pb 
207                 in2 = myDom2->Classify(gp_Pnt2d(u2,v2),Tol);
208                 if(in2 != TopAbs_OUT) {
209                   seqp.Append(firstp);
210                   seqp.Append(lastp);
211                 }
212               }
213             }
214           }
215         }
216       }
217     }
218     //
219     // The One resulting curve consists of 7 segments that are 
220     // connected between each other.
221     // The aim of the block is to reject these segments and have
222     // one segment instead of 7. 
223     //     The other reason to do that is value of TolReached3D=49.
224     //     Why -? It is not known yet. 
225     //                                             PKV 22.Apr.2002
226     //
227     Standard_Integer aNbParts;
228     //
229     aNbParts = seqp.Length()/2;
230     if (aNbParts > 1) {  
231       Standard_Boolean bCond;
232       GeomAbs_SurfaceType aST1, aST2;
233       aST1 = myHS1->Surface().GetType();
234       aST2 = myHS2->Surface().GetType();
235       //
236       bCond=Standard_False;
237       if (aST1==GeomAbs_Plane) {
238         if (aST2==GeomAbs_SurfaceOfExtrusion || 
239             aST2==GeomAbs_SurfaceOfRevolution) {//+zft
240           bCond=!bCond;
241         }
242       }
243       else if (aST2==GeomAbs_Plane) {
244         if (aST1==GeomAbs_SurfaceOfExtrusion || 
245             aST1==GeomAbs_SurfaceOfRevolution) {//+zft
246           bCond=!bCond;
247         }
248       }
249       //
250       if (bCond) {
251         Standard_Integer aNb, anIndex, aNbTmp, jx;
252         TColStd_IndexedMapOfInteger aMap;
253         TColStd_SequenceOfReal aSeqTmp;
254         //
255         aNb=seqp.Length();
256         for(i=1; i<=aNb; ++i) {
257           lastp =seqp(i);
258           anIndex=(Standard_Integer)lastp;
259           if (!aMap.Contains(anIndex)){
260             aMap.Add(anIndex);
261             aSeqTmp.Append(lastp);
262           }
263           else {
264             aNbTmp=aSeqTmp.Length();
265             aSeqTmp.Remove(aNbTmp);
266           }
267         }
268         //
269         seqp.Clear();
270         //
271         aNb=aSeqTmp.Length()/2;
272         for(i=1; i<=aNb;++i) {
273           jx=2*i;
274           firstp=aSeqTmp(jx-1);
275           lastp =aSeqTmp(jx);
276           seqp.Append(firstp);
277           seqp.Append(lastp);
278         }
279       }//if (bCond) {
280     }
281     done = Standard_True;
282     return;
283   }// else if(typl == IntPatch_Walking)  {
284   //
285   //-----------------------------------------------------------
286   else if (typl != IntPatch_Restriction)  {
287     seqp.Clear();
288     //
289     Handle(IntPatch_GLine) GLine (Handle(IntPatch_GLine)::DownCast (L));
290     //
291     if(typl == IntPatch_Circle || typl == IntPatch_Ellipse) { 
292       TreatCircle(L, Tol);
293       done=Standard_True;
294       return;
295     }
296     //----------------------------
297     Standard_Boolean intrvtested;
298     Standard_Real u1,v1,u2,v2;
299     //
300     nbvtx = GeomInt_LineTool::NbVertex(L);
301     intrvtested = Standard_False;
302     for(i=1; i<nbvtx; ++i) { 
303       firstp = GeomInt_LineTool::Vertex(L,i).ParameterOnLine();
304       lastp =  GeomInt_LineTool::Vertex(L,i+1).ParameterOnLine();
305       if(Abs(firstp-lastp)>Precision::PConfusion()) {
306         intrvtested = Standard_True;
307         const Standard_Real pmid = (firstp+lastp)*0.5;
308         gp_Pnt Pmid;
309         GLinePoint(typl, GLine, pmid, Pmid);
310         //
311         Parameters(myHS1,myHS2,Pmid,u1,v1,u2,v2);
312         Recadre(myHS1,myHS2,u1,v1,u2,v2);
313         const TopAbs_State in1 = myDom1->Classify(gp_Pnt2d(u1,v1),Tol);
314         if(in1 !=  TopAbs_OUT) { 
315           const TopAbs_State in2 = myDom2->Classify(gp_Pnt2d(u2,v2),Tol);
316           if(in2 != TopAbs_OUT) { 
317             seqp.Append(firstp);
318             seqp.Append(lastp);
319           }
320         }
321       }
322     }
323     //
324     if (!intrvtested) {
325       // Keep a priori. A point 2d on each
326       // surface is required to make the decision. Will be done in the caller
327       seqp.Append(GeomInt_LineTool::FirstParameter(L));
328       seqp.Append(GeomInt_LineTool::LastParameter(L));
329     }
330     //
331     done =Standard_True;
332     return;
333   } // else if (typl != IntPatch_Restriction)  { 
334
335   done = Standard_False;
336   seqp.Clear();
337   nbvtx = GeomInt_LineTool::NbVertex(L);
338   if (nbvtx == 0) { // Keep a priori. Point 2d is required on each
339                     // surface to make the decision. Will be done in the caller
340     seqp.Append(GeomInt_LineTool::FirstParameter(L));
341     seqp.Append(GeomInt_LineTool::LastParameter(L));
342     done = Standard_True;
343     return;
344   }
345
346   GeomInt_SequenceOfParameterAndOrientation seqpss;
347   TopAbs_Orientation or1=TopAbs_FORWARD,or2=TopAbs_FORWARD;
348
349   for (i=1; i<=nbvtx; i++)  {
350     const IntPatch_Point& thevtx = GeomInt_LineTool::Vertex(L,i);
351     const Standard_Real prm = thevtx.ParameterOnLine();
352     if (thevtx.IsOnDomS1())    {
353       switch (thevtx.TransitionLineArc1().TransitionType())      {
354         case IntSurf_In:        or1 = TopAbs_FORWARD; break;  
355         case IntSurf_Out:       or1 = TopAbs_REVERSED; break;  
356         case IntSurf_Touch:     or1 = TopAbs_INTERNAL; break;  
357         case IntSurf_Undecided: or1 = TopAbs_INTERNAL; break;  
358       }
359     }
360     else {
361       or1 = TopAbs_INTERNAL;
362     }
363     
364     if (thevtx.IsOnDomS2())    {
365       switch (thevtx.TransitionLineArc2().TransitionType())      {
366         case IntSurf_In:        or2 = TopAbs_FORWARD; break;
367         case IntSurf_Out:       or2 = TopAbs_REVERSED; break;
368         case IntSurf_Touch:     or2 = TopAbs_INTERNAL; break;
369         case IntSurf_Undecided: or2 = TopAbs_INTERNAL; break;
370       }
371     }
372     else {
373       or2 = TopAbs_INTERNAL;
374     }
375     //
376     const Standard_Integer nbinserted = seqpss.Length();
377     Standard_Boolean inserted = Standard_False;
378     for (Standard_Integer j=1; j<=nbinserted;j++)    {
379       if (Abs(prm-seqpss(j).Parameter()) <= Tol)      {
380         // accumulate
381         GeomInt_ParameterAndOrientation& valj = seqpss.ChangeValue(j);
382         if (or1 != TopAbs_INTERNAL) {
383           if (valj.Orientation1() != TopAbs_INTERNAL) {
384             if (or1 != valj.Orientation1()) {
385               valj.SetOrientation1(TopAbs_INTERNAL);
386             }
387           }
388           else {
389             valj.SetOrientation1(or1);
390           }
391         }
392         
393         if (or2 != TopAbs_INTERNAL) {
394           if (valj.Orientation2() != TopAbs_INTERNAL) {
395             if (or2 != valj.Orientation2()) {
396               valj.SetOrientation2(TopAbs_INTERNAL);
397             }
398           }
399           else {
400             valj.SetOrientation2(or2);
401           }
402         }          
403         inserted = Standard_True;
404         break;
405       }
406       
407       if (prm < seqpss(j).Parameter()-Tol ) {
408         // insert before position j
409         seqpss.InsertBefore(j,GeomInt_ParameterAndOrientation(prm,or1,or2));
410         inserted = Standard_True;
411         break;
412       }
413       
414     }
415     if (!inserted) {
416       seqpss.Append(GeomInt_ParameterAndOrientation(prm,or1,or2));
417     }
418   }
419
420   // determine the state at the beginning of line
421   Standard_Boolean trim = Standard_False;
422   Standard_Boolean dansS1 = Standard_False;
423   Standard_Boolean dansS2 = Standard_False;
424
425   nbvtx = seqpss.Length();
426   for (i=1; i<= nbvtx; i++)  {
427     or1 = seqpss(i).Orientation1();
428     if (or1 != TopAbs_INTERNAL)    {
429       trim = Standard_True;
430       dansS1 = (or1 != TopAbs_FORWARD);
431       break;
432     }
433   }
434   
435   if (i > nbvtx)  {
436     Standard_Real U,V;
437     for (i=1; i<=GeomInt_LineTool::NbVertex(L); i++ )    {
438       if (!GeomInt_LineTool::Vertex(L,i).IsOnDomS1() )      {
439         GeomInt_LineTool::Vertex(L,i).ParametersOnS1(U,V);
440         gp_Pnt2d PPCC(U,V);
441         if (myDom1->Classify(PPCC,Tol) == TopAbs_OUT) {
442           done = Standard_True;
443           return;
444         }
445         break;
446       }
447     }
448     dansS1 = Standard_True; // Keep in doubt
449   }
450   //
451   for (i=1; i<= nbvtx; i++)  {
452     or2 = seqpss(i).Orientation2();
453     if (or2 != TopAbs_INTERNAL)    {
454       trim = Standard_True;
455       dansS2 = (or2 != TopAbs_FORWARD);
456       break;
457     }
458   }
459   
460   if (i > nbvtx)  {
461     Standard_Real U,V;
462     for (i=1; i<=GeomInt_LineTool::NbVertex(L); i++ )    {
463       if (!GeomInt_LineTool::Vertex(L,i).IsOnDomS2() )      {
464         GeomInt_LineTool::Vertex(L,i).ParametersOnS2(U,V);
465         if (myDom2->Classify(gp_Pnt2d(U,V),Tol) == TopAbs_OUT) {
466           done = Standard_True;
467           return;
468         }
469         break;
470       }
471     }
472     dansS2 = Standard_True; //  Keep in doubt
473   }
474
475   if (!trim) { // necessarily dansS1 == dansS2 == Standard_True
476     seqp.Append(GeomInt_LineTool::FirstParameter(L));
477     seqp.Append(GeomInt_LineTool::LastParameter(L));
478     done = Standard_True;
479     return;
480   }
481
482   // sequence seqpss is peeled to create valid ends 
483   // and store them in seqp(2*i+1) and seqp(2*i+2)
484   Standard_Real thefirst = GeomInt_LineTool::FirstParameter(L);
485   Standard_Real thelast = GeomInt_LineTool::LastParameter(L);
486   firstp = thefirst;
487
488   for (i=1; i<=nbvtx; i++)  {
489     or1 = seqpss(i).Orientation1(); 
490     or2 = seqpss(i).Orientation2(); 
491     if (dansS1 && dansS2)    {
492       if (or1 == TopAbs_REVERSED){
493         dansS1 = Standard_False;
494       }
495       
496       if (or2 == TopAbs_REVERSED){
497         dansS2 = Standard_False;
498       }
499       if (!dansS1 || !dansS2)      {
500         lastp = seqpss(i).Parameter();
501         Standard_Real stofirst = Max(firstp, thefirst);
502         Standard_Real stolast  = Min(lastp,  thelast) ;
503
504         if (stolast > stofirst) {
505           seqp.Append(stofirst);
506           seqp.Append(stolast);
507         }
508         if (lastp > thelast) {
509           break;
510         }
511       }
512     }
513     else    {
514       if (dansS1)      {
515         if (or1 == TopAbs_REVERSED) {
516           dansS1 = Standard_False;
517         }
518       }
519       else      {
520         if (or1 == TopAbs_FORWARD){
521           dansS1 = Standard_True;
522         }
523       }
524       if (dansS2) {
525         if (or2 == TopAbs_REVERSED) {
526           dansS2 = Standard_False;
527         }
528       }
529       else {
530         if (or2 == TopAbs_FORWARD){
531           dansS2 = Standard_True;
532         }
533       }
534       if (dansS1 && dansS2){
535         firstp = seqpss(i).Parameter();
536       }
537     }
538   }
539   //
540   // finally to add
541   if (dansS1 && dansS2)  {
542     lastp  = thelast;
543     firstp = Max(firstp,thefirst);
544     if (lastp > firstp) {
545       seqp.Append(firstp);
546       seqp.Append(lastp);
547     }
548   }
549   done = Standard_True;
550 }
551
552
553 //=======================================================================
554 //function : Recadre
555 //purpose  : 
556 //=======================================================================
557 void Recadre(const Handle(GeomAdaptor_HSurface)& myHS1,
558              const Handle(GeomAdaptor_HSurface)& myHS2,
559              Standard_Real& u1,
560              Standard_Real& v1,
561              Standard_Real& u2,
562              Standard_Real& v2)
563
564   Standard_Boolean myHS1IsUPeriodic,myHS1IsVPeriodic;
565   const GeomAbs_SurfaceType typs1 = myHS1->GetType();
566   switch (typs1)
567   { 
568     case GeomAbs_Cylinder:
569     case GeomAbs_Cone:
570     case GeomAbs_Sphere: 
571     { 
572       myHS1IsUPeriodic = Standard_True;
573       myHS1IsVPeriodic = Standard_False;
574       break;
575     }
576     case GeomAbs_Torus:
577     {
578       myHS1IsUPeriodic = myHS1IsVPeriodic = Standard_True;
579       break;
580     }
581     default:
582     {
583       //-- Case of periodic biparameters is processed upstream
584       myHS1IsUPeriodic = myHS1IsVPeriodic = Standard_False;
585       break;
586     }
587   }
588   Standard_Boolean myHS2IsUPeriodic,myHS2IsVPeriodic;
589   const GeomAbs_SurfaceType typs2 = myHS2->GetType();
590   switch (typs2)
591   { 
592     case GeomAbs_Cylinder:
593     case GeomAbs_Cone:
594     case GeomAbs_Sphere: 
595     { 
596       myHS2IsUPeriodic = Standard_True;
597       myHS2IsVPeriodic = Standard_False;
598       break;
599     }
600     case GeomAbs_Torus:
601     {
602       myHS2IsUPeriodic = myHS2IsVPeriodic = Standard_True;
603       break;
604     }
605     default:
606     {
607       //-- Case of periodic biparameters is processed upstream
608       myHS2IsUPeriodic = myHS2IsVPeriodic = Standard_False;
609       break;
610     }
611   }
612   Standard_Real du, dv;
613   //
614   if(myHS1IsUPeriodic) {
615     const Standard_Real lmf = M_PI+M_PI; //-- myHS1->UPeriod();
616     const Standard_Real f = myHS1->FirstUParameter();
617     const Standard_Real l = myHS1->LastUParameter();
618     GeomInt::AdjustPeriodic(u1, f, l, lmf, u1, du);
619   }
620   if(myHS1IsVPeriodic) {
621     const Standard_Real lmf = M_PI+M_PI; //-- myHS1->VPeriod(); 
622     const Standard_Real f = myHS1->FirstVParameter();
623     const Standard_Real l = myHS1->LastVParameter();
624     GeomInt::AdjustPeriodic(v1, f, l, lmf, v1, dv);
625   }
626   if(myHS2IsUPeriodic) { 
627     const Standard_Real lmf = M_PI+M_PI; //-- myHS2->UPeriod();
628     const Standard_Real f = myHS2->FirstUParameter();
629     const Standard_Real l = myHS2->LastUParameter();
630     GeomInt::AdjustPeriodic(u2, f, l, lmf, u2, du);
631   }
632   if(myHS2IsVPeriodic) { 
633     const Standard_Real lmf = M_PI+M_PI; //-- myHS2->VPeriod();
634     const Standard_Real f = myHS2->FirstVParameter();
635     const Standard_Real l = myHS2->LastVParameter();
636     GeomInt::AdjustPeriodic(v2, f, l, lmf, v2, dv);
637   }
638 }
639 //=======================================================================
640 //function : Parameters
641 //purpose  : 
642 //=======================================================================
643 void Parameters(const Handle(GeomAdaptor_HSurface)& myHS1,
644                 const Handle(GeomAdaptor_HSurface)& myHS2,
645                 const gp_Pnt& Ptref,
646                 Standard_Real& U1,
647                 Standard_Real& V1,
648                 Standard_Real& U2,
649                 Standard_Real& V2)
650 {
651   Parameters(myHS1, Ptref, U1, V1);
652   Parameters(myHS2, Ptref, U2, V2);
653 }
654 //=======================================================================
655 //function : Parameter
656 //purpose  : 
657 //=======================================================================
658 void Parameters(const Handle(GeomAdaptor_HSurface)& myHS1,
659                 const gp_Pnt& Ptref,
660                 Standard_Real& U1,
661                 Standard_Real& V1)
662 {
663   IntSurf_Quadric quad1;
664   //
665   switch (myHS1->Surface().GetType())  {
666     case GeomAbs_Plane:    
667       quad1.SetValue(myHS1->Surface().Plane()); 
668       break;
669     case GeomAbs_Cylinder: 
670       quad1.SetValue(myHS1->Surface().Cylinder()); 
671       break;
672     case GeomAbs_Cone:     
673       quad1.SetValue(myHS1->Surface().Cone()); 
674       break;
675     case GeomAbs_Sphere:   
676       quad1.SetValue(myHS1->Surface().Sphere()); 
677       break;
678     case GeomAbs_Torus:
679       quad1.SetValue(myHS1->Surface().Torus()); 
680       break;
681     default: 
682       throw Standard_ConstructionError("GeomInt_LineConstructor::Parameters");
683   }
684   quad1.Parameters(Ptref,U1,V1);
685 }
686
687 //=======================================================================
688 //function : GLinePoint
689 //purpose  : 
690 //=======================================================================
691 void GLinePoint(const IntPatch_IType typl,
692                 const Handle(IntPatch_GLine)& GLine,
693                 const Standard_Real aT,
694                 gp_Pnt& aP)
695 {
696   switch (typl) {
697     case IntPatch_Lin:       
698     aP = ElCLib::Value(aT, GLine->Line()); 
699     break;
700   case IntPatch_Circle:    
701     aP = ElCLib::Value(aT, GLine->Circle()); 
702     break;
703   case IntPatch_Ellipse:   
704     aP = ElCLib::Value(aT, GLine->Ellipse()); 
705     break;
706   case IntPatch_Hyperbola: 
707     aP = ElCLib::Value(aT, GLine->Hyperbola()); 
708     break;
709   case IntPatch_Parabola:  
710     aP = ElCLib::Value(aT, GLine->Parabola()); 
711     break;
712   default:
713     throw Standard_ConstructionError("GeomInt_LineConstructor::Parameters");
714   }
715 }
716
717 //=======================================================================
718 //function : TreatCircle
719 //purpose  : 
720 //=======================================================================
721 void GeomInt_LineConstructor::TreatCircle(const Handle(IntPatch_Line)& aLine,
722                                            const Standard_Real aTol)
723 {  
724   Standard_Boolean bRejected;
725   IntPatch_IType aType;
726   //
727   aType=aLine->ArcType();
728   Handle(IntPatch_GLine) aGLine (Handle(IntPatch_GLine)::DownCast (aLine));
729   //
730   bRejected=RejectMicroCircle(aGLine, aType, aTol);
731   if (bRejected) {
732     return;
733   }
734   //----------------------------------------
735   Standard_Boolean bFound;
736   Standard_Integer aNbVtx, aNbVtxWas, i;
737   Standard_Real aTolPC, aT, aT1, aT2, aTmid, aTwoPI, aTolPC1;
738   Standard_Real aU1, aV1, aU2, aV2;
739   TopAbs_State aIn1, aIn2;
740   GeomAbs_SurfaceType aTS1, aTS2;
741   gp_Pnt aPmid;
742   gp_Pnt2d aP2D;
743   GeomInt_RealWithFlag *pVtx;
744   //-------------------------------------1
745   aTwoPI=M_PI+M_PI;
746   aTolPC=Precision::PConfusion();
747   aNbVtxWas=GeomInt_LineTool::NbVertex(aLine);
748   
749   aNbVtx=aNbVtxWas+2;
750   //-------------------------------------2
751   aTS1=myHS1->GetType();
752   aTS2=myHS2->GetType();
753   //
754   // About the value aTolPC1=1000.*aTolPC,
755   // see IntPatch_GLine.cxx, line:398
756   // for more details;
757   aTolPC1=1000.*aTolPC; 
758   //-------------------------------------
759   //
760   pVtx=new GeomInt_RealWithFlag [aNbVtx];
761   //
762   pVtx[0].SetValue(0.);
763   pVtx[1].SetValue(aTwoPI);
764   //
765   for(i=1; i<=aNbVtxWas; ++i) {
766     aT=GeomInt_LineTool::Vertex(aLine, i).ParameterOnLine();
767     aT=AdjustOnPeriod(aT, aTwoPI);
768     pVtx[i+1].SetValue(aT);
769   }
770   //
771   SortShell(aNbVtx, pVtx);
772   //
773   RejectNearBeacons(aNbVtx, pVtx, aTolPC1, aTS1, aTS2);
774   //
775   RejectDuplicates(aNbVtx, pVtx, aTolPC);
776   //
777   if ((aType==IntPatch_Circle || aType==IntPatch_Ellipse)&& aNbVtx>2) { // zz
778     bFound=Standard_False;
779     for(i=1; i<=aNbVtxWas; ++i) {
780       aT=GeomInt_LineTool::Vertex(aLine, i).ParameterOnLine();
781       if (fabs(aT) < aTolPC1 || fabs(aT-aTwoPI) < aTolPC1) {
782         bFound=!bFound;
783         break;
784       }
785     }
786     if (!bFound) {
787       aT=pVtx[1].Value()+aTwoPI;
788       pVtx[aNbVtx-1].SetValue(aT);
789       //
790       for(i=0; i<aNbVtx - 1; ++i) { 
791         aT=pVtx[i+1].Value();
792         pVtx[i].SetValue(aT);
793       }
794       --aNbVtx;
795     }
796   }
797   //
798   for(i=0; i<aNbVtx-1; ++i) { 
799     aT1=pVtx[i].Value();
800     aT2=pVtx[i+1].Value();
801     aTmid=(aT1+aT2)*0.5;
802     GLinePoint(aType, aGLine, aTmid, aPmid);
803     //
804     Parameters(myHS1, myHS2, aPmid, aU1, aV1, aU2, aV2);
805     Recadre(myHS1, myHS2, aU1, aV1, aU2, aV2);
806     //
807     aP2D.SetCoord(aU1, aV1);
808     aIn1=myDom1->Classify(aP2D, aTol);
809     if(aIn1 !=  TopAbs_OUT) { 
810       aP2D.SetCoord(aU2, aV2);
811       aIn2=myDom2->Classify(aP2D, aTol);
812       if(aIn2 != TopAbs_OUT) { 
813         seqp.Append(aT1);
814         seqp.Append(aT2);
815       }
816     }
817   }
818   //
819   delete [] pVtx;
820 }
821 //=======================================================================
822 //function : RejectNearBeacons
823 //purpose  : Reject the thickenings near the beacon points (if exist)
824 //           The gifts, made by sweep algo.  
825 //           chl/930/B5 B8 C2 C5 E2 E5 E8 F2 G8 H2 H5 H8
826 //=======================================================================
827 void RejectNearBeacons(Standard_Integer& aNbVtx, 
828                        GeomInt_RealWithFlag *pVtx, 
829                        Standard_Real aTolPC1,
830                        const GeomAbs_SurfaceType aTS1,
831                        const GeomAbs_SurfaceType aTS2) 
832 {
833   Standard_Integer i, j, iBcn;
834   Standard_Real aT, aBcn[2];
835   //
836   if (aTS1==GeomAbs_Cylinder && aTS2==GeomAbs_Cylinder) {
837     aBcn[0]=0.5*M_PI;
838     aBcn[1]=1.5*M_PI;
839     //
840     for (j=0; j<2; ++j) {
841       iBcn=-1;
842       for(i=0; i<aNbVtx; ++i) {
843         aT=pVtx[i].Value();
844         if (aT==aBcn[j]) {
845           iBcn=i;
846           break;
847         }
848       }
849       //
850       if (iBcn<0) {
851         // The beacon is not found
852         continue;
853       }
854       //  
855       for(i=0; i<aNbVtx; ++i) {
856         if (i!=iBcn) {
857           aT=pVtx[i].Value();
858           if (fabs(aT-aBcn[j]) < aTolPC1) {
859             pVtx[i].SetFlag(0);
860           }
861         }
862       }
863     }// for (j=0; j<2; ++j) {
864     //------------------------------------------
865     j=0;
866     for(i=0; i<aNbVtx; ++i) {
867       if (pVtx[i].Flag()) {
868         pVtx[j]=pVtx[i];
869         ++j;
870       }
871     }
872     aNbVtx=j;
873   }// if (aTS1==GeomAbs_Cylinder && aTS2==GeomAbs_Cylinder) {
874 }
875
876 //=======================================================================
877 //function : RejectDuplicates
878 //purpose  : 
879 //=======================================================================
880 void RejectDuplicates(Standard_Integer& aNbVtx, 
881                       GeomInt_RealWithFlag *pVtx, 
882                       Standard_Real aTolPC) 
883 {
884   Standard_Integer i, j;
885   Standard_Real dX, aT1, aT2; 
886   //
887   for(i=0; i<aNbVtx-1; ++i) {
888     aT2=pVtx[i+1].Value();
889     aT1=pVtx[i].Value();
890     dX=aT2-aT1;
891     if (dX<aTolPC) {
892       pVtx[i+1].SetFlag(0);
893     }
894   }
895   //
896   j=0;
897   for(i=0; i<aNbVtx; ++i) {
898     if (pVtx[i].Flag()) {
899       pVtx[j]=pVtx[i];
900       ++j;
901     }
902   }
903   aNbVtx=j;
904 }
905 //=======================================================================
906 //function : AdjustOnPeriod
907 //purpose  : 
908 //=======================================================================
909 Standard_Real AdjustOnPeriod(const Standard_Real aTr,
910                              const Standard_Real aPeriod)
911 {
912   Standard_Integer k;
913   Standard_Real aT;
914   //
915   aT=aTr;
916   if (aT<0.) {
917     k=-(Standard_Integer)(aT/aPeriod)+1;
918     aT=aT+k*aPeriod;
919   }
920   //
921   if (!(aT>=0. && aT<=aPeriod)) {
922     k=(Standard_Integer)(aT/aPeriod);
923     aT=aT-k*aPeriod;
924   }
925   //
926   return aT;
927 }
928 //=======================================================================
929 //function : RejectMicroCrcles
930 //purpose  : 
931 //=======================================================================
932 Standard_Boolean RejectMicroCircle(const Handle(IntPatch_GLine)& aGLine,
933                                    const IntPatch_IType aType,
934                                    const Standard_Real aTol3D)
935 {
936   Standard_Boolean bRet;
937   Standard_Real aR;
938   //
939   bRet=Standard_False;
940   //
941   if (aType==IntPatch_Circle) {
942     aR=aGLine->Circle().Radius();
943     bRet=(aR<aTol3D);
944   }
945   else if (aType==IntPatch_Ellipse) {
946     aR=aGLine->Ellipse().MajorRadius();
947     bRet=(aR<aTol3D);
948   }
949   return bRet;
950 }
951 //=======================================================================
952 // function: SortShell
953 // purpose : 
954 //=======================================================================
955 void SortShell(const Standard_Integer n, 
956                GeomInt_RealWithFlag *a) 
957 {
958   Standard_Integer nd, i, j, l, d=1;
959   GeomInt_RealWithFlag x;
960   //
961   while(d<=n) {
962     d*=2;
963   }
964   //
965   while (d) {
966     d=(d-1)/2;
967     //
968     nd=n-d;
969     for (i=0; i<nd; ++i) {
970       j=i;
971     m30:;
972       l=j+d;
973       if (a[l] < a[j]){
974         x=a[j];
975         a[j]=a[l];
976         a[l]=x;
977         j-=d;
978         if (j > -1) goto m30;
979       }//if (a[l] < a[j]){
980     }//for (i=0; i<nd; ++i) 
981   }//while (1)
982 }