0031404: Modeling Algorithms - BOP Fuse produces a self-interfering or a good shape...
[occt.git] / src / Approx / Approx_ComputeCLine.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 //  modified by Edward AGAPOV (eap) Tue Apr 2 2002 (occ265)
16 //  -- stop cutting an interval to approximate if next decisions
17 //  -- get worse on and on
18
19
20
21 #include <Approx_ParametrizationType.hxx>
22 #include <AppCont_LeastSquare.hxx>
23 #include <TColStd_Array1OfReal.hxx>
24 #include <AppParCurves_Constraint.hxx>
25 #include <Approx_Status.hxx>
26 #include <Precision.hxx>
27
28 const static Standard_Integer MAXSEGM = 1000;
29
30 //=======================================================================
31 //function : Approx_ComputeCLine
32 //purpose  : The MultiLine <Line> will be approximated until tolerances
33 //           will be reached.
34 //           The approximation will be done from degreemin to degreemax
35 //           with a cutting if the corresponding boolean is True.
36 //=======================================================================
37
38 Approx_ComputeCLine::Approx_ComputeCLine
39 (const MultiLine& Line,
40 const Standard_Integer degreemin,
41 const Standard_Integer degreemax,
42 const Standard_Real Tolerance3d,
43 const Standard_Real Tolerance2d,
44 const Standard_Boolean cutting,
45 const AppParCurves_Constraint FirstC,
46 const AppParCurves_Constraint LastC)
47 {
48   mydegremin = degreemin;
49   mydegremax = degreemax;
50   mytol3d = Tolerance3d;
51   mytol2d = Tolerance2d;
52   mycut = cutting;
53   myfirstC = FirstC;
54   mylastC = LastC;
55   myMaxSegments = MAXSEGM;
56   myInvOrder = Standard_True;
57   alldone = Standard_False;
58   Perform(Line);
59 }
60
61 //=======================================================================
62 //function : Approx_ComputeCLine
63 //purpose  : Initializes the fields of the algorithm.
64 //=======================================================================
65
66 Approx_ComputeCLine::Approx_ComputeCLine
67 (const Standard_Integer degreemin,
68 const Standard_Integer degreemax,
69 const Standard_Real Tolerance3d,
70 const Standard_Real Tolerance2d,
71 const Standard_Boolean cutting,
72 const AppParCurves_Constraint FirstC,
73 const AppParCurves_Constraint LastC)
74 {
75   alldone = Standard_False;
76   mydegremin = degreemin;
77   mydegremax = degreemax;
78   mytol3d = Tolerance3d;
79   mytol2d = Tolerance2d;
80   mycut = cutting;
81   myfirstC = FirstC;
82   mylastC = LastC;
83   myMaxSegments = MAXSEGM;
84   myInvOrder = Standard_True;
85 }
86
87 //=======================================================================
88 //function : Perform
89 //purpose  : runs the algorithm after having initialized the fields.
90 //=======================================================================
91
92 void Approx_ComputeCLine::Perform(const MultiLine& Line)
93 {
94   Standard_Real UFirst, ULast;
95   Standard_Boolean Finish = Standard_False,
96     begin = Standard_True, Ok = Standard_False;
97   Standard_Real thetol3d = Precision::Confusion(), thetol2d = Precision::Confusion();
98   UFirst = Line.FirstParameter();
99   ULast = Line.LastParameter();
100   Standard_Real TolU = Max((ULast - UFirst)*1.e-03, Precision::Confusion());
101   Standard_Real myfirstU = UFirst;
102   Standard_Real mylastU = ULast;
103   Standard_Integer aMaxSegments = 0;
104   Standard_Integer aMaxSegments1 = myMaxSegments - 1;
105   Standard_Integer aNbCut = 0, aNbImp = 0, aNbComp = 10;
106
107   if (!mycut)
108   {
109     alldone = Compute(Line, UFirst, ULast, thetol3d, thetol2d);
110     if (!alldone)
111     {
112       tolreached = Standard_False;
113       myfirstparam.Append(UFirst);
114       mylastparam.Append(ULast);
115       myMultiCurves.Append(TheMultiCurve);
116       Tolers3d.Append(currenttol3d);
117       Tolers2d.Append(currenttol2d);
118     }
119   }
120   else
121   {
122
123     // previous decision to be taken if we get worse with next cut (eap)
124     AppParCurves_MultiCurve KeptMultiCurve;
125     Standard_Real KeptUfirst = 0., KeptUlast = 0., KeptT3d = RealLast(), KeptT2d = 0.;
126
127     while (!Finish)
128     {
129
130       // Gestion du decoupage de la multiline pour approximer:
131       if (!begin)
132       {
133         if (Ok)
134         {
135           // Calcul de la partie a approximer.
136           myfirstU = mylastU;
137           mylastU = ULast;
138           aNbCut = 0;
139           aNbImp = 0;
140           if (Abs(ULast - myfirstU) <= RealEpsilon()
141               || aMaxSegments >= myMaxSegments)
142           {
143             Finish = Standard_True;
144             alldone = Standard_True;
145             return;
146           }
147           KeptT3d = RealLast(); KeptT2d = 0;
148           KeptUfirst = myfirstU;
149           KeptUlast = mylastU;
150         }
151         else
152         {
153           // keep best decison
154           if ((thetol3d + thetol2d) < (KeptT3d + KeptT2d))
155           {
156             KeptMultiCurve = TheMultiCurve;
157             KeptUfirst = myfirstU;
158             KeptUlast = mylastU;
159             KeptT3d = thetol3d;
160             KeptT2d = thetol2d;
161             aNbImp++;
162           }
163
164           // cut an interval
165           mylastU = (myfirstU + mylastU) / 2;
166           aNbCut++;
167         }
168       }
169
170       // Calcul des parametres sur ce nouvel intervalle.
171       Ok = Compute(Line, myfirstU, mylastU, thetol3d, thetol2d);
172       if (Ok)
173       {
174         aMaxSegments++;
175       }
176
177       //cout << myfirstU << " - " << mylastU << "  tol : " << thetol3d << " " << thetol2d << endl;
178       Standard_Boolean aStopCutting = Standard_False;
179       if (aNbCut >= aNbComp)
180       {
181         if (aNbCut > aNbImp + 1)
182         {
183           aStopCutting = Standard_True;
184         }
185         aNbCut = 0;
186         aNbImp = 0;
187       }
188       // is new decision better?
189       if (!Ok && (Abs(myfirstU - mylastU) <= TolU || aMaxSegments >= aMaxSegments1 || aStopCutting ))
190       {
191         Ok = Standard_True; // stop interval cutting, approx the rest part
192
193         if ((thetol3d + thetol2d) < (KeptT3d + KeptT2d))
194         {
195           KeptMultiCurve = TheMultiCurve;
196           KeptUfirst = myfirstU;
197           KeptUlast = mylastU;
198           KeptT3d = thetol3d;
199           KeptT2d = thetol2d;
200         }
201
202         mylastU = KeptUlast;
203
204         tolreached = Standard_False; // helas
205         myMultiCurves.Append(KeptMultiCurve);
206         aMaxSegments++;
207         Tolers3d.Append(KeptT3d);
208         Tolers2d.Append(KeptT2d);
209         myfirstparam.Append(KeptUfirst);
210         mylastparam.Append(KeptUlast);
211       }
212
213       begin = Standard_False;
214     } // while (!Finish)
215   }
216 }
217
218 //=======================================================================
219 //function : NbMultiCurves
220 //purpose  : Returns the number of MultiCurve doing the approximation
221 //           of the MultiLine.
222 //=======================================================================
223
224 Standard_Integer Approx_ComputeCLine::NbMultiCurves()const
225 {
226   return myMultiCurves.Length();
227 }
228
229 //=======================================================================
230 //function : Value
231 //purpose  : returns the approximation MultiCurve of range <Index>.
232 //=======================================================================
233
234 AppParCurves_MultiCurve Approx_ComputeCLine::Value(const Standard_Integer Index)
235 const
236 {
237   return myMultiCurves.Value(Index);
238 }
239
240 //=======================================================================
241 //function : Compute
242 //purpose  : is internally used by the algorithms.
243 //=======================================================================
244
245 Standard_Boolean Approx_ComputeCLine::Compute(const MultiLine& Line,
246   const Standard_Real Ufirst,
247   const Standard_Real Ulast,
248   Standard_Real&   TheTol3d,
249   Standard_Real&   TheTol2d)
250 {
251
252
253   const Standard_Integer NbPointsMax = 24;
254   const Standard_Real aMinRatio = 0.05;
255   const Standard_Integer aMaxDeg = 8;
256   //
257   Standard_Integer deg, NbPoints;
258   Standard_Boolean mydone;
259   Standard_Real Fv;
260
261   AppParCurves_MultiCurve aPrevCurve;
262   Standard_Real aPrevTol3d = RealLast(), aPrevTol2d = RealLast();
263   Standard_Boolean aPrevIsOk = Standard_False;
264   Standard_Boolean anInvOrder = myInvOrder;
265   if (anInvOrder && mydegremax > aMaxDeg)
266   {
267     if ((Ulast - Ufirst) / (Line.LastParameter() - Line.FirstParameter()) < aMinRatio)
268     {
269       anInvOrder = Standard_False;
270     }
271   }
272   if (anInvOrder)
273   {
274     for (deg = mydegremax; deg >= mydegremin; deg--) {
275       NbPoints = Min(2 * deg + 1, NbPointsMax);
276       AppCont_LeastSquare LSquare(Line, Ufirst, Ulast, myfirstC, mylastC, deg, NbPoints);
277       mydone = LSquare.IsDone();
278       if (mydone)
279       {
280         LSquare.Error(Fv, TheTol3d, TheTol2d);
281         if (TheTol3d <= mytol3d && TheTol2d <= mytol2d)
282         {
283           if (deg == mydegremin)
284           {
285             // Stockage de la multicurve approximee.
286             tolreached = Standard_True;
287             myMultiCurves.Append(LSquare.Value());
288             myfirstparam.Append(Ufirst);
289             mylastparam.Append(Ulast);
290             Tolers3d.Append(TheTol3d);
291             Tolers2d.Append(TheTol2d);
292             return Standard_True;
293           }
294           aPrevTol3d = TheTol3d;
295           aPrevTol2d = TheTol2d;
296           aPrevCurve = LSquare.Value();
297           aPrevIsOk = Standard_True;
298           continue;
299         }
300         else if (aPrevIsOk)
301         {
302           // Stockage de la multicurve approximee.
303           tolreached = Standard_True;
304           TheTol3d = aPrevTol3d;
305           TheTol2d = aPrevTol2d;
306           myMultiCurves.Append(aPrevCurve);
307           myfirstparam.Append(Ufirst);
308           mylastparam.Append(Ulast);
309           Tolers3d.Append(aPrevTol3d);
310           Tolers2d.Append(aPrevTol2d);
311           return Standard_True;
312         }
313       }
314       else if (aPrevIsOk)
315       {
316         // Stockage de la multicurve approximee.
317         tolreached = Standard_True;
318         TheTol3d = aPrevTol3d;
319         TheTol2d = aPrevTol2d;
320         myMultiCurves.Append(aPrevCurve);
321         myfirstparam.Append(Ufirst);
322         mylastparam.Append(Ulast);
323         Tolers3d.Append(aPrevTol3d);
324         Tolers2d.Append(aPrevTol2d);
325         return Standard_True;
326       }
327       if (!aPrevIsOk && deg == mydegremax)
328       {
329         TheMultiCurve = LSquare.Value();
330         currenttol3d = TheTol3d;
331         currenttol2d = TheTol2d;
332         aPrevTol3d = TheTol3d;
333         aPrevTol2d = TheTol2d;
334         aPrevCurve = TheMultiCurve;
335         break;
336       }
337     }
338   }
339   else
340   {
341     for (deg = mydegremin; deg <= mydegremax; deg++) {
342       NbPoints = Min(2 * deg + 1, NbPointsMax);
343       AppCont_LeastSquare LSquare(Line, Ufirst, Ulast, myfirstC, mylastC, deg, NbPoints);
344       mydone = LSquare.IsDone();
345       if (mydone) {
346         LSquare.Error(Fv, TheTol3d, TheTol2d);
347         if (TheTol3d <= mytol3d && TheTol2d <= mytol2d) {
348           // Stockage de la multicurve approximee.
349           tolreached = Standard_True;
350           myMultiCurves.Append(LSquare.Value());
351           myfirstparam.Append(Ufirst);
352           mylastparam.Append(Ulast);
353           Tolers3d.Append(TheTol3d);
354           Tolers2d.Append(TheTol2d);
355           return Standard_True;
356         }
357       }
358       if (deg == mydegremax) {
359         TheMultiCurve = LSquare.Value();
360         currenttol3d = TheTol3d;
361         currenttol2d = TheTol2d;
362       }
363     }
364   }
365   return Standard_False;
366 }
367
368 //=======================================================================
369 //function : Parameters
370 //purpose  : returns the first and last parameters of the 
371 //           <Index> MultiCurve.
372 //=======================================================================
373
374 void Approx_ComputeCLine::Parameters(const Standard_Integer Index,
375   Standard_Real& firstpar,
376   Standard_Real& lastpar) const
377 {
378   firstpar = myfirstparam.Value(Index);
379   lastpar = mylastparam.Value(Index);
380 }
381
382 //=======================================================================
383 //function : SetDegrees
384 //purpose  : changes the degrees of the approximation.
385 //=======================================================================
386
387 void Approx_ComputeCLine::SetDegrees(const Standard_Integer degreemin,
388   const Standard_Integer degreemax)
389 {
390   mydegremin = degreemin;
391   mydegremax = degreemax;
392 }
393
394 //=======================================================================
395 //function : SetTolerances
396 //purpose  : Changes the tolerances of the approximation.
397 //=======================================================================
398
399 void Approx_ComputeCLine::SetTolerances(const Standard_Real Tolerance3d,
400   const Standard_Real Tolerance2d)
401 {
402   mytol3d = Tolerance3d;
403   mytol2d = Tolerance2d;
404 }
405
406 //=======================================================================
407 //function : SetConstraints
408 //purpose  : Changes the constraints of the approximation.
409 //=======================================================================
410
411 void Approx_ComputeCLine::SetConstraints(const AppParCurves_Constraint FirstC,
412   const AppParCurves_Constraint LastC)
413 {
414   myfirstC = FirstC;
415   mylastC = LastC;
416 }
417
418 //=======================================================================
419 //function : SetMaxSegments
420 //purpose  : Changes the max number of segments, which is allowed for cutting.
421 //=======================================================================
422
423 void Approx_ComputeCLine::SetMaxSegments(const Standard_Integer theMaxSegments)
424 {
425   myMaxSegments = theMaxSegments;
426 }
427
428 //=======================================================================
429 //function : SetInvOrder
430 //purpose  : 
431 //=======================================================================
432 void Approx_ComputeCLine::SetInvOrder(const Standard_Boolean theInvOrder)
433 {
434   myInvOrder = theInvOrder;
435 }
436
437 //=======================================================================
438 //function : IsAllApproximated
439 //purpose  : returns False if at a moment of the approximation,
440 //           the status NoApproximation has been sent by the user
441 //           when more points were needed.
442 //=======================================================================
443
444 Standard_Boolean Approx_ComputeCLine::IsAllApproximated()
445 const {
446   return alldone;
447 }
448
449 //=======================================================================
450 //function : IsToleranceReached
451 //purpose  : returns False if the status NoPointsAdded has been sent.
452 //=======================================================================
453
454 Standard_Boolean Approx_ComputeCLine::IsToleranceReached()
455 const {
456   return tolreached;
457 }
458
459 //=======================================================================
460 //function : Error
461 //purpose  : returns the tolerances 2d and 3d of the <Index> MultiCurve.
462 //=======================================================================
463
464 void Approx_ComputeCLine::Error(const Standard_Integer Index,
465   Standard_Real& tol3d,
466   Standard_Real& tol2d) const
467 {
468   tol3d = Tolers3d.Value(Index);
469   tol2d = Tolers2d.Value(Index);
470 }