0028838: Configuration - undefine macros coming from X11 headers in place of collision
[occt.git] / src / IntWalk / IntWalk_IWalking_4.gxx
1 // Copyright (c) 1995-1999 Matra Datavision
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
3 //
4 // This file is part of Open CASCADE Technology software library.
5 //
6 // This library is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU Lesser General Public License version 2.1 as published
8 // by the Free Software Foundation, with special exception defined in the file
9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
10 // distribution for complete text of the license and disclaimer of any warranty.
11 //
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
14
15 #include <NCollection_IncAllocator.hxx>
16
17 void IntWalk_IWalking::ComputeCloseLine(const TColStd_SequenceOfReal& Umult,
18                                         const TColStd_SequenceOfReal& Vmult,
19                                         const ThePOPIterator& Pnts1,
20                                         const ThePOLIterator& Pnts2,
21                                         TheIWFunction& Func,
22                                         Standard_Boolean& Rajout )
23 // *********** Processing of closed line **********************
24 //
25 // for any interior non-processed point 
26 //       calculate the step of advancement=step depending on the arrow and max step
27 //       calculate a point of approach (this point is on the tangent to the section
28 // of distance = no interior point)
29 //  conditions 
30 //            (all calculated points do not form a closed loop)  
31 //                              or                    
32 //            (all points do not form an open line going from 
33 //            one border of the domain to the other or from a point tangent
34 //            to the border or from 2 tangent points : single cases)
35 //  
36 //     frame the point of approach on borders if necessary
37 //     calculate the point
38 //     if point not found divide the step
39 //     test of stop    
40 //     calculate step depending on the arrow and the max step (stop possible)
41 //
42 // ******************************************************************** 
43 {
44   Standard_Integer I,N = 0,SaveN = 0;
45   Standard_Real aBornInf[2], aBornSup[2], aUVap[2];
46   math_Vector BornInf(aBornInf,1,2), BornSup(aBornSup,1,2);
47   math_Vector Uvap(aUVap,1,2);// parameters of current approach
48   Standard_Real PasC;  // step of advancement on the tangent
49   Standard_Real PasCu; // step of advancement current by U
50   Standard_Real PasCv; // step of advancement current by V
51   Standard_Real PasSav; // save first step of advancement
52   Standard_Boolean Arrive;// show if line ends
53   Standard_Boolean Cadre; // show if on border of the  domains
54   Standard_Boolean ArretAjout; // show if on the added point
55   IntSurf_PntOn2S Psol;
56   Handle(IntWalk_TheIWLine)  CurrentLine; //line under construction
57   ThePointOfPath PathPnt;
58   ThePointOfLoop LoopPnt;
59
60   Standard_Boolean Tgtbeg,Tgtend;
61
62   Standard_Integer StepSign;
63   
64   IntWalk_StatusDeflection aStatus = IntWalk_OK, StatusPrecedent;
65   Standard_Integer NbDivision ;   // number of divisions of step 
66   // during calculation of  1 section
67
68   Standard_Integer Ipass ;
69   //index in the iterator of points on edge of point of passage  
70
71
72   BornInf(1) = Um;
73   BornSup(1) = UM;
74   BornInf(2) = Vm;
75   BornSup(2) = VM;
76   
77   math_FunctionSetRoot Rsnld(Func,tolerance);
78   Standard_Integer nbLoop = Pnts2.Length();
79
80   // Check borders for degeneracy:
81   math_Matrix D(1,1,1,2);
82   const Standard_Integer aNbSamplePnt = 10;
83   Standard_Boolean isLeftDegeneratedBorder[2] = {Standard_True, Standard_True};
84   Standard_Boolean isRightDegeneratedBorder[2] = {Standard_True, Standard_True};
85   math_Vector aStep(1,2);
86   aStep = (BornSup - BornInf) / (aNbSamplePnt - 1);
87   for(Standard_Integer aBorderIdx = 1; aBorderIdx <= 2; aBorderIdx++)
88   {
89     Standard_Integer aChangeIdx = aBorderIdx == 2? 1 : 2;
90     math_Vector UV(1,2);
91
92     // Left border.
93     UV(aBorderIdx) = BornInf(aBorderIdx);
94     for(Standard_Integer aParamIdx = 0; aParamIdx < aNbSamplePnt; aParamIdx++)
95     {
96       Standard_Real aParam = BornInf(aChangeIdx) + aParamIdx * aStep(aChangeIdx);
97       UV(aChangeIdx) = aParam;
98       Func.Derivatives(UV, D);
99       if ( Abs(D(1, aChangeIdx) ) > Precision::Confusion())
100       {
101         isLeftDegeneratedBorder[aBorderIdx - 1] = Standard_False;
102         break;
103       }
104     }
105
106     // Right border.
107     UV(aBorderIdx) = BornSup(aBorderIdx);
108     for(Standard_Integer aParamIdx = 0; aParamIdx < aNbSamplePnt; aParamIdx++)
109     {
110       Standard_Real aParam = BornInf(aChangeIdx) + aParamIdx * aStep(aChangeIdx);
111       UV(aChangeIdx) = aParam;
112       Func.Derivatives(UV, D);
113       if ( Abs(D(1, aChangeIdx) ) > Precision::Confusion())
114       {
115         isRightDegeneratedBorder[aBorderIdx - 1] = Standard_False;
116         break;
117       }
118     }
119   }
120
121   for (I = 1;I<=nbLoop;I++) {
122     if (wd2[I].etat > 12)
123     { // start point of closed line
124       LoopPnt = Pnts2.Value(I);
125       previousPoint.SetValue(ThePointOfLoopTool::Value3d(LoopPnt),reversed,
126            wd2[I].ustart,wd2[I].vstart);
127       previousd3d = ThePointOfLoopTool::Direction3d(LoopPnt);
128       previousd2d = ThePointOfLoopTool::Direction2d(LoopPnt);
129
130       CurrentLine = new IntWalk_TheIWLine (new NCollection_IncAllocator());
131       CurrentLine->AddPoint(previousPoint);
132       CurrentLine->SetTangentVector(previousd3d,1);
133       Tgtbeg = Standard_False;
134       Tgtend = Standard_False;
135       Uvap(1) = wd2[I].ustart;
136       Uvap(2) = wd2[I].vstart;
137
138       StepSign = 1;
139
140       // first step of advancement
141
142       Standard_Real d2dx = Abs(previousd2d.X()); 
143       Standard_Real d2dy = Abs(previousd2d.Y()); 
144       if (d2dx < tolerance(1)) {
145         PasC = pas * (VM-Vm)/d2dy;
146       }
147       else if (d2dy < tolerance(2)) {
148         PasC = pas * (UM-Um)/d2dx;
149       }
150       else {
151         PasC = pas * Min((UM-Um)/d2dx,(VM-Vm)/d2dy);
152       }
153
154       PasSav = PasC;
155
156       Arrive = Standard_False;
157       ArretAjout = Standard_False;
158       NbDivision = 0;
159       StatusPrecedent = IntWalk_OK;
160       Standard_Integer aNbIter = 10;
161       while (!Arrive) {  // as no test of stop is passed
162         Cadre=Cadrage(BornInf,BornSup,Uvap,PasC, StepSign);  // border?
163 #ifdef CHRONO
164         Chronrsnld.Start();
165 #endif
166
167         Rsnld.Perform(Func,Uvap,BornInf,BornSup);
168
169 #ifdef CHRONO
170         Chronrsnld.Stop();
171 #endif
172
173         if (Cadre) { // update of limits.
174           BornInf(1) = Um;BornSup(1) = UM;BornInf(2) = Vm;BornSup(2) = VM;
175         }
176         if (Rsnld.IsDone()) {
177           if (Abs(Func.Root()) > Func.Tolerance()) { // no solution for the tolerance
178             PasC = PasC/2.;
179             PasCu = Abs(PasC*previousd2d.X());
180             PasCv = Abs(PasC*previousd2d.Y());
181
182             if (PasCu <= tolerance(1) && PasCv <= tolerance(2)) {
183               if (CurrentLine->NbPoints()==1)
184               {
185                 RemoveTwoEndPoints(I);
186                 break; //cancel the line
187               }
188               if (wd2[I].etat >12) { //the line should become open
189                 wd2[I].etat = 12; //declare it open
190                 ArretAjout = Standard_False;
191                 OpenLine(0,Psol,Pnts1,Func,CurrentLine);
192                 StepSign = -1;
193                 StatusPrecedent = IntWalk_OK;
194                 Arrive = Standard_False;
195                 PasC = PasSav;
196                 Rajout = Standard_True;
197                 seqAlone.Append(-lines.Length()-1);
198                 seqAjout.Append(-lines.Length()-1);
199               }
200               else { // line s is open                 
201                 Arrive =Standard_True;
202                 CurrentLine->AddStatusLast(Standard_False);
203                 Rajout = Standard_True;
204                 seqAlone.Append(lines.Length()+1);
205                 seqAjout.Append(lines.Length()+1);
206                 Tgtend = Standard_True;
207               } 
208               /*              
209               Arrive = Standard_True;
210               CurrentLine->AddStatusFirstLast(Standard_False,
211                 Standard_False,Standard_False);
212               Rajout = Standard_True;
213               seqAlone.Append(lines.Length()+1);
214               seqAjout.Append(lines.Length()+1);
215               Tgtend = Standard_True;
216               */
217             }
218           }
219           else { // there is a solution
220             Rsnld.Root(Uvap);
221
222             // Avoid unitialized memory access.
223             if (CurrentLine->NbPoints() > 2)
224             {
225               for(Standard_Integer aCoordIdx = 1; aCoordIdx <= 2; aCoordIdx++)
226               {
227                 // Check degenerated cases and fix if possible.
228                 if ( ( isLeftDegeneratedBorder[aCoordIdx - 1]
229                 && Abs (Uvap(aCoordIdx) - BornInf(aCoordIdx)) < Precision::PConfusion())||
230                   (isRightDegeneratedBorder[aCoordIdx - 1]
231                 && Abs (Uvap(aCoordIdx) - BornSup(aCoordIdx)) < Precision::PConfusion()) )
232                 {
233                   Standard_Real uvprev[2], uv[2];
234                   if (!reversed)
235                   {
236                     CurrentLine->Value(CurrentLine->NbPoints() - 1).ParametersOnS2(uvprev[0], uvprev[1]);
237                     CurrentLine->Value(CurrentLine->NbPoints()).ParametersOnS2(uv[0], uv[1]);
238                   }
239                   else
240                   {
241                     CurrentLine->Value(CurrentLine->NbPoints() - 1).ParametersOnS1(uvprev[0], uvprev[1]);
242                     CurrentLine->Value(CurrentLine->NbPoints()).ParametersOnS1(uv[0], uv[1]);
243                   }
244
245                   Standard_Real aScaleCoeff = 0.0;
246
247                   // Avoid finite cycle which lead to stop computing iline.
248                   if (aStatus != IntWalk_PasTropGrand)
249                   {
250                     // Make linear extrapolation.
251                     if ( Abs(uv[aCoordIdx - 1] - uvprev[aCoordIdx - 1]) > gp::Resolution())
252                       aScaleCoeff = Abs ((Uvap(aCoordIdx) - uv[aCoordIdx - 1])
253                                       /  (uv[aCoordIdx - 1] - uvprev[aCoordIdx - 1]) );
254                     Standard_Integer aFixIdx =  aCoordIdx == 1? 2 : 1; // Fixing index;
255                     Uvap(aFixIdx) = uv[aFixIdx - 1] + (uv[aFixIdx - 1] - uvprev[aFixIdx - 1]) * aScaleCoeff;
256                   }
257                 }
258               }
259             }
260
261             Arrive = TestArretPassage(Umult,Vmult,Uvap,I,Ipass);
262             if (Arrive) {//reset proper parameter to test the arrow.
263               Psol = CurrentLine->Value(1);
264               if (!reversed) {
265                 Psol.ParametersOnS2(Uvap(1),Uvap(2));
266               }
267               else {
268                 Psol.ParametersOnS1(Uvap(1),Uvap(2));
269               }
270               Cadre=Standard_False; 
271               //in case if there is a frame and arrival at the same time
272             }
273             else { // modif jag 940615
274               if (Rajout) {    // test on added points
275                 ArretAjout =TestArretAjout(Func,Uvap,N,Psol);
276                 SaveN = N;
277                 if (ArretAjout) {
278                   if (N >0) {
279                     Tgtend = lines.Value(N)->IsTangentAtEnd();
280                     N = -N;
281                   }
282                   else {
283                     Tgtend = lines.Value(-N)->IsTangentAtBegining();
284                   }
285                   Arrive = (wd2[I].etat == 12);
286                 }
287               }
288
289               if (!ArretAjout&& Cadre) {  // test on already marked points
290                 if (CurrentLine->NbPoints() == 1)
291                 {
292                   RemoveTwoEndPoints(I);
293                   break; // cancel the line
294                 }
295                 TestArretCadre(Umult,Vmult,CurrentLine,Func,Uvap,N);
296                 SaveN = N;
297                 //              if (N==0) {
298                 if (N <= 0) { // jag 941017
299                   MakeWalkingPoint(2,Uvap(1),Uvap(2),Func,Psol);
300                   Tgtend = Func.IsTangent(); // jag 940616
301                   N = -N;
302                 }
303                 Arrive = (wd2[I].etat == 12); // the line is open
304               }
305             }
306             aStatus = TestDeflection(Func, Arrive,Uvap,StatusPrecedent,
307                                                 NbDivision,PasC,StepSign);
308
309             StatusPrecedent = aStatus;
310             if (aStatus == IntWalk_PasTropGrand) {// division of the step
311               Arrive = Standard_False;
312               ArretAjout = Standard_False;
313               Tgtend = Standard_False; // jag 940616
314               if (!reversed) {
315                 previousPoint.ParametersOnS2(Uvap(1),Uvap(2));
316               }
317               else {
318                 previousPoint.ParametersOnS1(Uvap(1),Uvap(2));
319               }
320             }
321             else if (ArretAjout || Cadre) {
322
323               if (Arrive) { // line s is open
324                 CurrentLine->AddStatusLast(Standard_False);
325                 //if (aStatus != IntWalk_ArretSurPointPrecedent)
326                 CurrentLine->AddPoint(Psol);
327
328                 //Remove <SaveN> from <seqAlone> and, if it is first found point,
329                 //from <seqAjout> too
330                 if (IsValidEndPoint(I, SaveN))
331                 {
332                   for (Standard_Integer iseq = 1; iseq <= seqAlone.Length(); iseq++)
333                     if (seqAlone(iseq) == SaveN)
334                     {
335                       seqAlone.Remove(iseq);
336                       break;
337                     }
338                   if (CurrentLine->NbPoints() <= 3)
339                     for (Standard_Integer iseq = 1; iseq <= seqAjout.Length(); iseq++)
340                       if (seqAjout(iseq) == SaveN)
341                       {
342                         seqAjout.Remove(iseq);
343                         break;
344                       }
345                 }
346                 else
347                 {
348                   if (seqAlone.Last() == -lines.Length()-1)
349                   {
350                     seqAlone.Remove(seqAlone.Length());
351                     seqAjout.Remove(seqAjout.Length());
352                   }
353                   RemoveTwoEndPoints(I);
354                   Arrive = Standard_False;
355                   break; //cancel the line
356                 }
357
358                 if (Cadre && N==0) {
359                   Rajout = Standard_True;
360                   //seqAlone.Append(lines.Length()+1);
361                   seqAjout.Append(lines.Length()+1);
362                 }
363
364               }
365               else { // open
366                 wd2[I].etat = 12; // declare it open
367                 Tgtbeg = Tgtend;
368                 Tgtend = Standard_False;
369                 ArretAjout = Standard_False;
370                 StepSign = -1;
371                 StatusPrecedent = IntWalk_OK;
372                 PasC = PasSav;
373                 if (aStatus == IntWalk_ArretSurPointPrecedent) {
374                   CurrentLine->AddPoint(Psol);
375                   OpenLine(0,Psol,Pnts1,Func,CurrentLine);
376                 }
377                 else {
378                   OpenLine(-lines.Length()-1,Psol,Pnts1,Func,CurrentLine);
379                 }
380                 //Remove <SaveN> from <seqAlone> and, if it is first found point,
381                 //from <seqAjout> too
382                 if (IsValidEndPoint(I, SaveN))
383                 {
384                   for (Standard_Integer iseq = 1; iseq <= seqAlone.Length(); iseq++)
385                     if (seqAlone(iseq) == SaveN)
386                     {
387                       seqAlone.Remove(iseq);
388                       break;
389                     }
390                   if (CurrentLine->NbPoints() <= 2)
391                     for (Standard_Integer iseq = 1; iseq <= seqAjout.Length(); iseq++)
392                       if (seqAjout(iseq) == SaveN)
393                       {
394                         seqAjout.Remove(iseq);
395                         break;
396                       }
397                 }
398                 else
399                 {
400                   RemoveTwoEndPoints(I);
401                   break; //cancel the line
402                 }
403                 
404                 if (Cadre && N==0) {
405                   Rajout = Standard_True;
406                   seqAjout.Append(-lines.Length()-1);
407                 }
408               }
409             }
410             else if (aStatus == IntWalk_ArretSurPointPrecedent) {
411               if (CurrentLine->NbPoints() == 1) { //cancel the line
412                 Arrive = Standard_False;
413                 RemoveTwoEndPoints(I);
414                 break;
415               }
416               if (wd2[I].etat >12) { //the line should become open
417                 wd2[I].etat = 12; //declare it open
418                 ArretAjout = Standard_False;
419                 OpenLine(0,Psol,Pnts1,Func,CurrentLine);
420                 StepSign = -1;
421                 StatusPrecedent = IntWalk_OK;
422                 Arrive = Standard_False;
423                 PasC = PasSav;
424                 Rajout = Standard_True;
425                 seqAlone.Append(-lines.Length()-1);
426                 seqAjout.Append(-lines.Length()-1);
427               }
428               else { // line s is open                 
429                 Arrive =Standard_True;
430                 CurrentLine->AddStatusLast(Standard_False);
431                 Rajout = Standard_True;
432                 seqAlone.Append(lines.Length()+1);
433                 seqAjout.Append(lines.Length()+1);
434               } 
435             }
436             else if (Arrive)  {
437               if (wd2[I].etat > 12) {  //line closed good case
438                 CurrentLine->AddStatusFirstLast(Standard_True,
439                   Standard_False,Standard_False);
440                 CurrentLine->AddPoint(CurrentLine->Value(1));              
441               }
442               else if (N >0) { //point of stop given at input 
443                 PathPnt = Pnts1.Value(N);
444                 CurrentLine->AddStatusLast(Standard_True,N,PathPnt);
445                 AddPointInCurrentLine(N,PathPnt,CurrentLine);
446               }
447             }
448             else if (aStatus == IntWalk_ArretSurPoint) {
449               if (wd2[I].etat >12) { //line should become open
450                 wd2[I].etat = 12; //declare it open
451                 Tgtbeg = Standard_True;
452                 Tgtend = Standard_False;
453                 N= -lines.Length()-1;
454                 Psol.SetValue(Func.Point(),reversed,Uvap(1),Uvap(2));
455                 OpenLine(N,Psol,Pnts1,Func,CurrentLine);
456                 StepSign = -1;
457                 Rajout = Standard_True;
458                 seqAlone.Append(N);
459                 seqAjout.Append(N);
460                 StatusPrecedent = IntWalk_OK;
461                 Arrive = Standard_False;
462                 PasC = PasSav;  
463               }
464               else { 
465                 Arrive = Standard_True;                   
466                 if (Ipass!=0) { //point of passage, point of stop
467                   PathPnt = Pnts1.Value(Ipass);
468                   CurrentLine->AddStatusLast(Standard_True,Ipass,PathPnt);
469                   AddPointInCurrentLine(Ipass,PathPnt,CurrentLine);
470                 }
471                 else {
472                   CurrentLine->AddStatusLast(Standard_False);
473                   IntSurf_PntOn2S newP;
474                   newP.SetValue(Func.Point(),reversed,Uvap(1),Uvap(2));
475                   CurrentLine->AddPoint(newP);
476                   Rajout = Standard_True;
477                   seqAlone.Append(lines.Length()+1);
478                   seqAjout.Append(lines.Length()+1);
479                 }
480               }
481             }
482             else if (aStatus == IntWalk_OK) {
483               if (Ipass!=0) CurrentLine->AddIndexPassing(Ipass);
484               previousPoint.SetValue(Func.Point(),reversed,Uvap(1),Uvap(2));
485               previousd3d = Func.Direction3d();
486               previousd2d = Func.Direction2d();
487               CurrentLine->AddPoint(previousPoint);
488             }
489             else if (aStatus == IntWalk_PointConfondu)
490             {
491               aNbIter --;
492             }
493           }
494         }
495         else { //no numerical solution NotDone
496           PasC = PasC/2.;
497           PasCu = Abs(PasC*previousd2d.X());
498           PasCv = Abs(PasC*previousd2d.Y());
499
500           if (PasCu <= tolerance(1) && PasCv <= tolerance(2)) {
501             if (CurrentLine->NbPoints() == 1)
502             {
503               RemoveTwoEndPoints(I);
504               break; // cancel the line
505             }
506             if (wd2[I].etat >12) { //the line should become open
507               wd2[I].etat = 12; //declare it open
508               ArretAjout = Standard_False;
509               OpenLine(0,Psol,Pnts1,Func,CurrentLine);
510               StepSign = -1;
511               StatusPrecedent = IntWalk_OK;
512               Arrive = Standard_False;
513               PasC = PasSav;
514               Rajout = Standard_True;
515               seqAlone.Append(-lines.Length()-1);
516               seqAjout.Append(-lines.Length()-1);
517             }
518             else { // line s is open                 
519               Arrive =Standard_True;
520               CurrentLine->AddStatusLast(Standard_False);
521               Tgtend = Standard_True;
522               Rajout = Standard_True;
523               seqAlone.Append(lines.Length()+1);
524               seqAjout.Append(lines.Length()+1);
525             } 
526             /*
527             Arrive = Standard_True;
528             CurrentLine->AddStatusFirstLast(Standard_False,Standard_False,
529               Standard_False);
530             Tgtend = Standard_True;
531             Rajout = Standard_True;
532             seqAlone.Append(lines.Length()+1);
533             seqAjout.Append(lines.Length()+1);
534             */
535           }  
536         }
537
538         if(aNbIter < 0)
539           break;
540       }// end of started line 
541       if (Arrive) {
542         CurrentLine->SetTangencyAtBegining(Tgtbeg);
543         CurrentLine->SetTangencyAtEnd(Tgtend);
544
545         lines.Append(CurrentLine);
546         wd2[I].etat=-wd2[I].etat; //mark point as processed
547       }
548     } //end of processing of start point
549   } //end of all start points
550 }