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