0031404: Modeling Algorithms - BOP Fuse produces a self-interfering or a good shape...
[occt.git] / src / Approx / Approx_ComputeCLine.gxx
CommitLineData
b311480e 1// Copyright (c) 1995-1999 Matra Datavision
973c2be1 2// Copyright (c) 1999-2014 OPEN CASCADE SAS
b311480e 3//
973c2be1 4// This file is part of Open CASCADE Technology software library.
b311480e 5//
d5f74e42 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
973c2be1 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.
b311480e 11//
973c2be1 12// Alternatively, this file may be used under the terms of Open CASCADE
13// commercial license or contractual agreement.
7fd59977 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>
368cdde6 22#include <AppCont_LeastSquare.hxx>
7fd59977 23#include <TColStd_Array1OfReal.hxx>
24#include <AppParCurves_Constraint.hxx>
25#include <Approx_Status.hxx>
1d47d8d0 26#include <Precision.hxx>
7fd59977 27
ba7f665d 28const static Standard_Integer MAXSEGM = 1000;
29
7fd59977 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
38Approx_ComputeCLine::Approx_ComputeCLine
afb3647b 39(const MultiLine& Line,
40const Standard_Integer degreemin,
41const Standard_Integer degreemax,
42const Standard_Real Tolerance3d,
43const Standard_Real Tolerance2d,
44const Standard_Boolean cutting,
45const AppParCurves_Constraint FirstC,
46const AppParCurves_Constraint LastC)
7fd59977 47{
48 mydegremin = degreemin;
49 mydegremax = degreemax;
50 mytol3d = Tolerance3d;
51 mytol2d = Tolerance2d;
52 mycut = cutting;
53 myfirstC = FirstC;
54 mylastC = LastC;
ba7f665d 55 myMaxSegments = MAXSEGM;
56 myInvOrder = Standard_True;
7fd59977 57 alldone = Standard_False;
58 Perform(Line);
59}
60
61//=======================================================================
62//function : Approx_ComputeCLine
63//purpose : Initializes the fields of the algorithm.
64//=======================================================================
65
66Approx_ComputeCLine::Approx_ComputeCLine
afb3647b 67(const Standard_Integer degreemin,
68const Standard_Integer degreemax,
69const Standard_Real Tolerance3d,
70const Standard_Real Tolerance2d,
71const Standard_Boolean cutting,
72const AppParCurves_Constraint FirstC,
73const AppParCurves_Constraint LastC)
7fd59977 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;
ba7f665d 83 myMaxSegments = MAXSEGM;
84 myInvOrder = Standard_True;
7fd59977 85}
86
87//=======================================================================
88//function : Perform
89//purpose : runs the algorithm after having initialized the fields.
90//=======================================================================
91
92void Approx_ComputeCLine::Perform(const MultiLine& Line)
93{
7fd59977 94 Standard_Real UFirst, ULast;
afb3647b 95 Standard_Boolean Finish = Standard_False,
96 begin = Standard_True, Ok = Standard_False;
1d47d8d0 97 Standard_Real thetol3d = Precision::Confusion(), thetol2d = Precision::Confusion();
368cdde6 98 UFirst = Line.FirstParameter();
afb3647b 99 ULast = Line.LastParameter();
100 Standard_Real TolU = Max((ULast - UFirst)*1.e-03, Precision::Confusion());
101 Standard_Real myfirstU = UFirst;
7fd59977 102 Standard_Real mylastU = ULast;
f998596a 103 Standard_Integer aMaxSegments = 0;
104 Standard_Integer aMaxSegments1 = myMaxSegments - 1;
895a80d3 105 Standard_Integer aNbCut = 0, aNbImp = 0, aNbComp = 10;
7fd59977 106
7da00517 107 if (!mycut)
108 {
7fd59977 109 alldone = Compute(Line, UFirst, ULast, thetol3d, thetol2d);
afb3647b 110 if (!alldone)
7da00517 111 {
7fd59977 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 }
afb3647b 120 else
7da00517 121 {
7fd59977 122
123 // previous decision to be taken if we get worse with next cut (eap)
124 AppParCurves_MultiCurve KeptMultiCurve;
1d47d8d0 125 Standard_Real KeptUfirst = 0., KeptUlast = 0., KeptT3d = RealLast(), KeptT2d = 0.;
1d47d8d0 126
afb3647b 127 while (!Finish)
7da00517 128 {
afb3647b 129
7fd59977 130 // Gestion du decoupage de la multiline pour approximer:
afb3647b 131 if (!begin)
7da00517 132 {
afb3647b 133 if (Ok)
7da00517 134 {
135 // Calcul de la partie a approximer.
136 myfirstU = mylastU;
afb3647b 137 mylastU = ULast;
138 aNbCut = 0;
139 aNbImp = 0;
140 if (Abs(ULast - myfirstU) <= RealEpsilon()
f998596a 141 || aMaxSegments >= myMaxSegments)
7da00517 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;
afb3647b 157 KeptUfirst = myfirstU;
158 KeptUlast = mylastU;
159 KeptT3d = thetol3d;
160 KeptT2d = thetol2d;
161 aNbImp++;
7da00517 162 }
163
164 // cut an interval
afb3647b 165 mylastU = (myfirstU + mylastU) / 2;
166 aNbCut++;
7da00517 167 }
7fd59977 168 }
169
7fd59977 170 // Calcul des parametres sur ce nouvel intervalle.
171 Ok = Compute(Line, myfirstU, mylastU, thetol3d, thetol2d);
afb3647b 172 if (Ok)
f998596a 173 {
174 aMaxSegments++;
175 }
7fd59977 176
177 //cout << myfirstU << " - " << mylastU << " tol : " << thetol3d << " " << thetol2d << endl;
afb3647b 178 Standard_Boolean aStopCutting = Standard_False;
179 if (aNbCut >= aNbComp)
180 {
895a80d3 181 if (aNbCut > aNbImp + 1)
afb3647b 182 {
183 aStopCutting = Standard_True;
184 }
895a80d3 185 aNbCut = 0;
186 aNbImp = 0;
afb3647b 187 }
7fd59977 188 // is new decision better?
afb3647b 189 if (!Ok && (Abs(myfirstU - mylastU) <= TolU || aMaxSegments >= aMaxSegments1 || aStopCutting ))
7fd59977 190 {
afb3647b 191 Ok = Standard_True; // stop interval cutting, approx the rest part
3629864d 192
afb3647b 193 if ((thetol3d + thetol2d) < (KeptT3d + KeptT2d))
194 {
195 KeptMultiCurve = TheMultiCurve;
196 KeptUfirst = myfirstU;
197 KeptUlast = mylastU;
198 KeptT3d = thetol3d;
199 KeptT2d = thetol2d;
200 }
3629864d 201
afb3647b 202 mylastU = KeptUlast;
7da00517 203
afb3647b 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 }
7fd59977 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
224Standard_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
234AppParCurves_MultiCurve Approx_ComputeCLine::Value(const Standard_Integer Index)
235const
236{
237 return myMultiCurves.Value(Index);
238}
239
240//=======================================================================
241//function : Compute
242//purpose : is internally used by the algorithms.
243//=======================================================================
244
245Standard_Boolean Approx_ComputeCLine::Compute(const MultiLine& Line,
afb3647b 246 const Standard_Real Ufirst,
247 const Standard_Real Ulast,
248 Standard_Real& TheTol3d,
249 Standard_Real& TheTol2d)
7fd59977 250{
251
252
ba7f665d 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;
7fd59977 258 Standard_Boolean mydone;
259 Standard_Real Fv;
260
ba7f665d 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 {
afb3647b 316 // Stockage de la multicurve approximee.
317 tolreached = Standard_True;
ba7f665d 318 TheTol3d = aPrevTol3d;
319 TheTol2d = aPrevTol2d;
320 myMultiCurves.Append(aPrevCurve);
afb3647b 321 myfirstparam.Append(Ufirst);
322 mylastparam.Append(Ulast);
ba7f665d 323 Tolers3d.Append(aPrevTol3d);
324 Tolers2d.Append(aPrevTol2d);
afb3647b 325 return Standard_True;
7fd59977 326 }
ba7f665d 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 }
7fd59977 337 }
ba7f665d 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 }
7fd59977 363 }
7fd59977 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
374void Approx_ComputeCLine::Parameters(const Standard_Integer Index,
afb3647b 375 Standard_Real& firstpar,
376 Standard_Real& lastpar) const
7fd59977 377{
378 firstpar = myfirstparam.Value(Index);
afb3647b 379 lastpar = mylastparam.Value(Index);
7fd59977 380}
381
382//=======================================================================
383//function : SetDegrees
384//purpose : changes the degrees of the approximation.
385//=======================================================================
386
387void Approx_ComputeCLine::SetDegrees(const Standard_Integer degreemin,
afb3647b 388 const Standard_Integer degreemax)
7fd59977 389{
390 mydegremin = degreemin;
391 mydegremax = degreemax;
392}
393
394//=======================================================================
395//function : SetTolerances
396//purpose : Changes the tolerances of the approximation.
397//=======================================================================
398
399void Approx_ComputeCLine::SetTolerances(const Standard_Real Tolerance3d,
afb3647b 400 const Standard_Real Tolerance2d)
7fd59977 401{
402 mytol3d = Tolerance3d;
403 mytol2d = Tolerance2d;
404}
405
406//=======================================================================
407//function : SetConstraints
408//purpose : Changes the constraints of the approximation.
409//=======================================================================
410
411void Approx_ComputeCLine::SetConstraints(const AppParCurves_Constraint FirstC,
afb3647b 412 const AppParCurves_Constraint LastC)
7fd59977 413{
414 myfirstC = FirstC;
afb3647b 415 mylastC = LastC;
7fd59977 416}
417
418//=======================================================================
f998596a 419//function : SetMaxSegments
420//purpose : Changes the max number of segments, which is allowed for cutting.
421//=======================================================================
422
afb3647b 423void Approx_ComputeCLine::SetMaxSegments(const Standard_Integer theMaxSegments)
f998596a 424{
425 myMaxSegments = theMaxSegments;
426}
427
428//=======================================================================
ba7f665d 429//function : SetInvOrder
430//purpose :
431//=======================================================================
432void Approx_ComputeCLine::SetInvOrder(const Standard_Boolean theInvOrder)
433{
434 myInvOrder = theInvOrder;
435}
436
437//=======================================================================
7fd59977 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
444Standard_Boolean Approx_ComputeCLine::IsAllApproximated()
445const {
446 return alldone;
447}
448
449//=======================================================================
450//function : IsToleranceReached
451//purpose : returns False if the status NoPointsAdded has been sent.
452//=======================================================================
453
454Standard_Boolean Approx_ComputeCLine::IsToleranceReached()
455const {
456 return tolreached;
457}
458
459//=======================================================================
460//function : Error
461//purpose : returns the tolerances 2d and 3d of the <Index> MultiCurve.
462//=======================================================================
463
464void Approx_ComputeCLine::Error(const Standard_Integer Index,
afb3647b 465 Standard_Real& tol3d,
466 Standard_Real& tol2d) const
7fd59977 467{
468 tol3d = Tolers3d.Value(Index);
469 tol2d = Tolers2d.Value(Index);
470}