1 // Copyright (c) 1995-1999 Matra Datavision
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
4 // This file is part of Open CASCADE Technology software library.
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.
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
15 #include <NCollection_IncAllocator.hxx>
17 void IntWalk_IWalking::ComputeCloseLine(const TColStd_SequenceOfReal& Umult,
18 const TColStd_SequenceOfReal& Vmult,
19 const ThePOPIterator& Pnts1,
20 const ThePOLIterator& Pnts2,
22 Standard_Boolean& Rajout )
23 // *********** Processing of closed line **********************
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)
30 // (all calculated points do not form a closed loop)
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)
36 // frame the point of approach on borders if necessary
37 // calculate the point
38 // if point not found divide the step
40 // calculate step depending on the arrow and the max step (stop possible)
42 // ********************************************************************
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
56 Handle(IntWalk_TheIWLine) CurrentLine; //line under construction
57 ThePointOfPath PathPnt;
58 ThePointOfLoop LoopPnt;
60 Standard_Boolean Tgtbeg,Tgtend;
62 Standard_Integer StepSign;
64 IntWalk_StatusDeflection Status = IntWalk_OK, StatusPrecedent;
65 Standard_Integer NbDivision ; // number of divisions of step
66 // during calculation of 1 section
68 Standard_Integer Ipass ;
69 //index in the iterator of points on edge of point of passage
77 math_FunctionSetRoot Rsnld(Func,tolerance);
78 Standard_Integer nbLoop = Pnts2.Length();
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++)
89 Standard_Integer aChangeIdx = aBorderIdx == 2? 1 : 2;
93 UV(aBorderIdx) = BornInf(aBorderIdx);
94 for(Standard_Integer aParamIdx = 0; aParamIdx < aNbSamplePnt; aParamIdx++)
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())
101 isLeftDegeneratedBorder[aBorderIdx - 1] = Standard_False;
107 UV(aBorderIdx) = BornSup(aBorderIdx);
108 for(Standard_Integer aParamIdx = 0; aParamIdx < aNbSamplePnt; aParamIdx++)
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())
115 isRightDegeneratedBorder[aBorderIdx - 1] = Standard_False;
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);
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;
140 // first step of advancement
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;
147 else if (d2dy < tolerance(2)) {
148 PasC = pas * (UM-Um)/d2dx;
151 PasC = pas * Min((UM-Um)/d2dx,(VM-Vm)/d2dy);
156 Arrive = Standard_False;
157 ArretAjout = Standard_False;
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?
167 Rsnld.Perform(Func,Uvap,BornInf,BornSup);
173 if (Cadre) { // update of limits.
174 BornInf(1) = Um;BornSup(1) = UM;BornInf(2) = Vm;BornSup(2) = VM;
176 if (Rsnld.IsDone()) {
177 if (Abs(Func.Root()) > Func.Tolerance()) { // no solution for the tolerance
179 PasCu = Abs(PasC*previousd2d.X());
180 PasCv = Abs(PasC*previousd2d.Y());
182 if (PasCu <= tolerance(1) && PasCv <= tolerance(2)) {
183 if (CurrentLine->NbPoints()==1)
185 RemoveTwoEndPoints(I);
186 break; //cancel the line
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);
193 StatusPrecedent = IntWalk_OK;
194 Arrive = Standard_False;
196 Rajout = Standard_True;
197 seqAlone.Append(-lines.Length()-1);
198 seqAjout.Append(-lines.Length()-1);
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;
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;
219 else { // there is a solution
222 // Avoid unitialized memory access.
223 if (CurrentLine->NbPoints() > 2)
225 for(Standard_Integer aCoordIdx = 1; aCoordIdx <= 2; aCoordIdx++)
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()) )
233 Standard_Real uvprev[2], uv[2];
236 CurrentLine->Value(CurrentLine->NbPoints() - 1).ParametersOnS2(uvprev[0], uvprev[1]);
237 CurrentLine->Value(CurrentLine->NbPoints()).ParametersOnS2(uv[0], uv[1]);
241 CurrentLine->Value(CurrentLine->NbPoints() - 1).ParametersOnS1(uvprev[0], uvprev[1]);
242 CurrentLine->Value(CurrentLine->NbPoints()).ParametersOnS1(uv[0], uv[1]);
245 Standard_Real aScaleCoeff = 0.0;
247 // Avoid finite cycle which lead to stop computing iline.
248 if (Status != IntWalk_PasTropGrand)
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;
261 Arrive = TestArretPassage(Umult,Vmult,Uvap,I,Ipass);
262 if (Arrive) {//reset proper parameter to test the arrow.
263 Psol = CurrentLine->Value(1);
265 Psol.ParametersOnS2(Uvap(1),Uvap(2));
268 Psol.ParametersOnS1(Uvap(1),Uvap(2));
270 Cadre=Standard_False;
271 //in case if there is a frame and arrival at the same time
273 else { // modif jag 940615
274 if (Rajout) { // test on added points
275 ArretAjout =TestArretAjout(Func,Uvap,N,Psol);
279 Tgtend = lines.Value(N)->IsTangentAtEnd();
283 Tgtend = lines.Value(-N)->IsTangentAtBegining();
285 Arrive = (wd2[I].etat == 12);
289 if (!ArretAjout&& Cadre) { // test on already marked points
290 if (CurrentLine->NbPoints() == 1)
292 RemoveTwoEndPoints(I);
293 break; // cancel the line
295 TestArretCadre(Umult,Vmult,CurrentLine,Func,Uvap,N);
298 if (N <= 0) { // jag 941017
299 MakeWalkingPoint(2,Uvap(1),Uvap(2),Func,Psol);
300 Tgtend = Func.IsTangent(); // jag 940616
303 Arrive = (wd2[I].etat == 12); // the line is open
306 Status = TestDeflection(Func, Arrive,Uvap,StatusPrecedent,
307 NbDivision,PasC,StepSign);
309 StatusPrecedent = Status;
310 if (Status == IntWalk_PasTropGrand) {// division of the step
311 Arrive = Standard_False;
312 ArretAjout = Standard_False;
313 Tgtend = Standard_False; // jag 940616
315 previousPoint.ParametersOnS2(Uvap(1),Uvap(2));
318 previousPoint.ParametersOnS1(Uvap(1),Uvap(2));
321 else if (ArretAjout || Cadre) {
323 if (Arrive) { // line s is open
324 CurrentLine->AddStatusLast(Standard_False);
325 //if (Status != IntWalk_ArretSurPointPrecedent)
326 CurrentLine->AddPoint(Psol);
328 //Remove <SaveN> from <seqAlone> and, if it is first found point,
329 //from <seqAjout> too
330 if (IsValidEndPoint(I, SaveN))
332 for (Standard_Integer iseq = 1; iseq <= seqAlone.Length(); iseq++)
333 if (seqAlone(iseq) == SaveN)
335 seqAlone.Remove(iseq);
338 if (CurrentLine->NbPoints() <= 3)
339 for (Standard_Integer iseq = 1; iseq <= seqAjout.Length(); iseq++)
340 if (seqAjout(iseq) == SaveN)
342 seqAjout.Remove(iseq);
348 if (seqAlone.Last() == -lines.Length()-1)
350 seqAlone.Remove(seqAlone.Length());
351 seqAjout.Remove(seqAjout.Length());
353 RemoveTwoEndPoints(I);
354 Arrive = Standard_False;
355 break; //cancel the line
359 Rajout = Standard_True;
360 //seqAlone.Append(lines.Length()+1);
361 seqAjout.Append(lines.Length()+1);
366 wd2[I].etat = 12; // declare it open
368 Tgtend = Standard_False;
369 ArretAjout = Standard_False;
371 StatusPrecedent = IntWalk_OK;
373 if (Status == IntWalk_ArretSurPointPrecedent) {
374 CurrentLine->AddPoint(Psol);
375 OpenLine(0,Psol,Pnts1,Func,CurrentLine);
378 OpenLine(-lines.Length()-1,Psol,Pnts1,Func,CurrentLine);
380 //Remove <SaveN> from <seqAlone> and, if it is first found point,
381 //from <seqAjout> too
382 if (IsValidEndPoint(I, SaveN))
384 for (Standard_Integer iseq = 1; iseq <= seqAlone.Length(); iseq++)
385 if (seqAlone(iseq) == SaveN)
387 seqAlone.Remove(iseq);
390 if (CurrentLine->NbPoints() <= 2)
391 for (Standard_Integer iseq = 1; iseq <= seqAjout.Length(); iseq++)
392 if (seqAjout(iseq) == SaveN)
394 seqAjout.Remove(iseq);
400 RemoveTwoEndPoints(I);
401 break; //cancel the line
405 Rajout = Standard_True;
406 seqAjout.Append(-lines.Length()-1);
410 else if ( Status == IntWalk_ArretSurPointPrecedent) {
411 if (CurrentLine->NbPoints() == 1) { //cancel the line
412 Arrive = Standard_False;
413 RemoveTwoEndPoints(I);
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);
421 StatusPrecedent = IntWalk_OK;
422 Arrive = Standard_False;
424 Rajout = Standard_True;
425 seqAlone.Append(-lines.Length()-1);
426 seqAjout.Append(-lines.Length()-1);
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);
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));
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);
448 else if (Status == 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);
457 Rajout = Standard_True;
460 StatusPrecedent = IntWalk_OK;
461 Arrive = Standard_False;
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);
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);
482 else if (Status == 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);
489 else if (Status == IntWalk_PointConfondu)
495 else { //no numerical solution NotDone
497 PasCu = Abs(PasC*previousd2d.X());
498 PasCv = Abs(PasC*previousd2d.Y());
500 if (PasCu <= tolerance(1) && PasCv <= tolerance(2)) {
501 if (CurrentLine->NbPoints() == 1)
503 RemoveTwoEndPoints(I);
504 break; // cancel the line
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);
511 StatusPrecedent = IntWalk_OK;
512 Arrive = Standard_False;
514 Rajout = Standard_True;
515 seqAlone.Append(-lines.Length()-1);
516 seqAjout.Append(-lines.Length()-1);
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);
527 Arrive = Standard_True;
528 CurrentLine->AddStatusFirstLast(Standard_False,Standard_False,
530 Tgtend = Standard_True;
531 Rajout = Standard_True;
532 seqAlone.Append(lines.Length()+1);
533 seqAjout.Append(lines.Length()+1);
540 }// end of started line
542 CurrentLine->SetTangencyAtBegining(Tgtbeg);
543 CurrentLine->SetTangencyAtEnd(Tgtend);
545 lines.Append(CurrentLine);
546 wd2[I].etat=-wd2[I].etat; //mark point as processed
548 } //end of processing of start point
549 } //end of all start points