0030008: BRepMesh does not respect angular deflection in internal area of bspline...
[occt.git] / src / BRepMesh / BRepMesh_NURBSRangeSplitter.cxx
1 // Created on: 2016-04-19
2 // Copyright (c) 2016 OPEN CASCADE SAS
3 // Created by: Oleg AGASHIN
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #include <BRepMesh_NURBSRangeSplitter.hxx>
17
18 #include <algorithm>
19 #include <BRepMesh_GeomTool.hxx>
20 #include <GeomAdaptor_Curve.hxx>
21 #include <GeomLib.hxx>
22 #include <IMeshData_Edge.hxx>
23 #include <IMeshData_Wire.hxx>
24 #include <NCollection_Handle.hxx>
25
26 namespace
27 {
28   class AnalyticalFilter
29   {
30   public:
31     //! Constructor.
32     AnalyticalFilter(
33       const IMeshData::IFaceHandle&             theDFace,
34       const GeomAbs_IsoType                     theIsoType,
35       const Handle(IMeshData::SequenceOfReal)&  theParams,
36       const Handle(IMeshData::SequenceOfReal)&  theControlParams,
37       const Handle(IMeshData::MapOfReal)&       theParamsForbiddenToRemove,
38       const Handle(IMeshData::MapOfReal)&       theControlParamsForbiddenToRemove)
39       : myDFace(theDFace),
40         mySurface(myDFace->GetSurface()->ChangeSurface().Surface().Surface()),
41         myIsoU(theIsoType == GeomAbs_IsoU),
42         myParams(theParams),
43         myControlParams(theControlParams),
44         myParamsForbiddenToRemove(theParamsForbiddenToRemove),
45         myControlParamsForbiddenToRemove(theControlParamsForbiddenToRemove),
46         myAllocator(new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE)),
47         myControlParamsToRemove(new IMeshData::MapOfReal(1, myAllocator))
48     {
49     }
50
51     //! Returns map of parameters supposed to be removed.
52     const Handle(IMeshData::MapOfReal)& GetControlParametersToRemove(
53       const IMeshTools_Parameters& theParameters)
54     {
55       myParameters = theParameters;
56
57       Standard_Integer aStartIndex, aEndIndex;
58       if (myIsoU)
59       {
60         aStartIndex = 1;
61         aEndIndex = myParams->Length();
62       }
63       else
64       {
65         aStartIndex = 2;
66         aEndIndex = myParams->Length() - 1;
67       }
68
69       for (Standard_Integer i = aStartIndex; i <= aEndIndex; ++i)
70       {
71         myCurrParam = myParams->Value(i);
72         myIso = new GeomAdaptor_Curve(myIsoU ? mySurface->UIso(myCurrParam) : mySurface->VIso(myCurrParam));
73
74         myPrevControlParam = myControlParams->Value(1);
75         myIso->D1(myPrevControlParam, myPrevControlPnt, myPrevControlVec);
76         for (Standard_Integer j = 2; j <= myControlParams->Length();)
77         {
78           j += checkControlPointAndMoveOn(j);
79         }
80       }
81
82       return myControlParamsToRemove;
83     }
84
85   private:
86
87     //! Checks the given control point for deviation.
88     //! Returns number of steps to be used to move point iterator.
89     Standard_Integer checkControlPointAndMoveOn(const Standard_Integer theIndex)
90     {
91       Standard_Integer aMoveSteps = 0;
92       myCurrControlParam = myControlParams->Value(theIndex);
93       myIso->D1(myCurrControlParam, myCurrControlPnt, myCurrControlVec);
94
95       const Standard_Real aMidParam = 0.5 * (myPrevControlParam + myCurrControlParam);
96       const gp_Pnt aMidPnt = myIso->Value(aMidParam);
97
98       const Standard_Real aSqDist = BRepMesh_GeomTool::SquareDeflectionOfSegment(
99         myPrevControlPnt, myCurrControlPnt, aMidPnt);
100
101       Standard_Real anAngle = 0.0;
102       
103       if ((myPrevControlVec.SquareMagnitude() > Precision::SquareConfusion()) &&
104           (myCurrControlVec.SquareMagnitude() > Precision::SquareConfusion()))
105       {
106         anAngle = myPrevControlVec.Angle(myCurrControlVec);
107       }
108
109       const Standard_Real aSqMaxDeflection = myDFace->GetDeflection() *
110         myDFace->GetDeflection();
111
112       if (((aSqDist > aSqMaxDeflection) || (anAngle > myParameters.AngleInterior)) &&
113           aSqDist > myParameters.MinSize * myParameters.MinSize)
114       {
115         // insertion 
116         myControlParams->InsertBefore(theIndex, aMidParam);
117       }
118       else
119       {
120         // Here we should leave at least 3 parameters as far as
121         // we must have at least one parameter related to surface
122         // internals in order to prevent movement of triangle body
123         // outside the surface in case of highly curved ones, e.g.
124         // BSpline springs.
125         if (((aSqDist < aSqMaxDeflection) || (anAngle < myParameters.AngleInterior)) &&
126             myControlParams->Length() > 3 && theIndex < myControlParams->Length())
127         {
128           // Remove too dense points
129           const Standard_Real aTmpParam = myControlParams->Value(theIndex + 1);
130           if (checkParameterForDeflectionAndUpdateCache(aTmpParam))
131           {
132             ++aMoveSteps;
133           }
134         }
135
136         myPrevControlParam = myCurrControlParam;
137         myPrevControlPnt   = myCurrControlPnt;
138         myPrevControlVec   = myCurrControlVec;
139
140         ++aMoveSteps;
141       }
142
143       return aMoveSteps;
144     }
145
146     //! Checks whether the given param suits specified deflection. Updates cache.
147     Standard_Boolean checkParameterForDeflectionAndUpdateCache(const Standard_Real theParam)
148     {
149       gp_Pnt aTmpPnt;
150       gp_Vec aTmpVec;
151       myIso->D1(theParam, aTmpPnt, aTmpVec);
152
153       const Standard_Real aTmpMidParam = 0.5 * (myPrevControlParam + theParam);
154       const gp_Pnt        aTmpMidPnt = myIso->Value(aTmpMidParam);
155
156       // Lets check next parameter.
157       // If it also fits deflection, we can remove previous parameter.
158       const Standard_Real aSqDist = BRepMesh_GeomTool::SquareDeflectionOfSegment(
159         myPrevControlPnt, aTmpPnt, aTmpMidPnt);
160
161       if (aSqDist < myDFace->GetDeflection() * myDFace->GetDeflection())
162       {
163         // Lets check parameters for angular deflection.
164         if (myPrevControlVec.SquareMagnitude() < gp::Resolution() ||
165             aTmpVec.SquareMagnitude()          < gp::Resolution() ||
166             myPrevControlVec.Angle(aTmpVec)    < myParameters.AngleInterior)
167         {
168           // For current Iso line we can remove this parameter.
169           myControlParamsToRemove->Add(myCurrControlParam);
170           myCurrControlParam = theParam;
171           myCurrControlPnt   = aTmpPnt;
172           myCurrControlVec   = aTmpVec;
173           return Standard_True;
174         }
175         else
176         {
177           // We have found a place on the surface refusing 
178           // removement of this parameter.
179           myParamsForbiddenToRemove       ->Add(myCurrParam);
180           myControlParamsForbiddenToRemove->Add(myCurrControlParam);
181         }
182       }
183
184       return Standard_False;
185     }
186
187   private:
188
189     IMeshData::IFaceHandle                myDFace;
190     Handle(Geom_Surface)                  mySurface;
191     Standard_Boolean                      myIsoU;
192     Handle(IMeshData::SequenceOfReal)     myParams;
193     Handle(IMeshData::SequenceOfReal)     myControlParams;
194
195     Handle(IMeshData::MapOfReal)          myParamsForbiddenToRemove;
196     Handle(IMeshData::MapOfReal)          myControlParamsForbiddenToRemove;
197
198     Handle(NCollection_IncAllocator)      myAllocator;
199     Handle(IMeshData::MapOfReal)          myControlParamsToRemove;
200
201
202     IMeshTools_Parameters                 myParameters;
203     NCollection_Handle<GeomAdaptor_Curve> myIso;
204
205     Standard_Real                         myCurrParam;
206
207     Standard_Real                         myCurrControlParam;
208     gp_Pnt                                myCurrControlPnt;
209     gp_Vec                                myCurrControlVec;
210
211     Standard_Real                         myPrevControlParam;
212     gp_Pnt                                myPrevControlPnt;
213     gp_Vec                                myPrevControlVec;
214   };
215
216   //! Adds param to map if it fits specified range.
217   inline Standard_Boolean addParam(
218     const Standard_Real&                           theParam,
219     const std::pair<Standard_Real, Standard_Real>& theRange,
220     IMeshData::IMapOfReal&                         theParams)
221   {
222     if (theParam < theRange.first ||
223         theParam > theRange.second)
224     {
225       return Standard_False;
226     }
227
228     theParams.Add(theParam);
229     return Standard_True;
230   }
231
232   //! Initializes parameters map using CN intervals.
233   inline Standard_Boolean initParamsFromIntervals(
234     const TColStd_Array1OfReal&                    theIntervals,
235     const std::pair<Standard_Real, Standard_Real>& theRange,
236     const Standard_Boolean                         isSplitIntervals,
237     IMeshData::IMapOfReal&                         theParams)
238   {
239     Standard_Boolean isAdded = Standard_False;
240
241     for (Standard_Integer i = theIntervals.Lower(); i <= theIntervals.Upper(); ++i)
242     {
243       const Standard_Real aStartParam = theIntervals.Value(i);
244       if (addParam(aStartParam, theRange, theParams))
245       {
246         isAdded = Standard_True;
247       }
248
249       if (isSplitIntervals && i < theIntervals.Upper())
250       {
251         const Standard_Real aMidParam = (aStartParam + theIntervals.Value(i + 1)) / 2.;
252         if (addParam(aMidParam, theRange, theParams))
253         {
254           isAdded = Standard_True;
255         }
256       }
257     }
258
259     return isAdded;
260   }
261
262   //! Checks whether intervals should be split.
263   //! Returns true in case if it is impossible to compute normal 
264   //! directly on intervals, false is returned elsewhere.
265   Standard_Boolean toSplitIntervals (const Handle (Geom_Surface)&  theSurf,
266                                      const TColStd_Array1OfReal  (&theIntervals)[2])
267   {
268     Standard_Integer aIntervalU = theIntervals[0].Lower ();
269     for (; aIntervalU <= theIntervals[0].Upper (); ++aIntervalU)
270     {
271       const Standard_Real aParamU = theIntervals[0].Value(aIntervalU);
272       Standard_Integer aIntervalV = theIntervals[1].Lower ();
273       for (; aIntervalV <= theIntervals[1].Upper (); ++aIntervalV)
274       {
275         gp_Dir aNorm;
276         const Standard_Real aParamV = theIntervals[1].Value(aIntervalV);
277         if (GeomLib::NormEstim (theSurf, gp_Pnt2d (aParamU, aParamV), Precision::Confusion (), aNorm) != 0)
278         {
279           return Standard_True;
280         }
281         // TODO: do not split intervals if there is no normal in the middle of interval.
282       }
283     }
284
285     return Standard_False;
286   }
287 }
288
289 //=======================================================================
290 // Function: AdjustRange
291 // Purpose : 
292 //=======================================================================
293 void BRepMesh_NURBSRangeSplitter::AdjustRange()
294 {
295   BRepMesh_DefaultRangeSplitter::AdjustRange();
296   mySurfaceType = GetSurface()->GetType();
297
298   if (mySurfaceType == GeomAbs_BezierSurface)
299   {
300     const std::pair<Standard_Real, Standard_Real>& aRangeU = GetRangeU();
301     const std::pair<Standard_Real, Standard_Real>& aRangeV = GetRangeV();
302
303     myIsValid = !(aRangeU.first  < -0.5 ||
304                   aRangeU.second >  1.5 ||
305                   aRangeV.first  < -0.5 ||
306                   aRangeV.second >  1.5);
307   }
308 }
309
310 //=======================================================================
311 // Function: GenerateSurfaceNodes
312 // Purpose : 
313 //=======================================================================
314 Handle(IMeshData::ListOfPnt2d) BRepMesh_NURBSRangeSplitter::GenerateSurfaceNodes(
315   const IMeshTools_Parameters& theParameters) const
316 {
317   if (!initParameters())
318   {
319     return Handle(IMeshData::ListOfPnt2d)();
320   }
321
322   const std::pair<Standard_Real, Standard_Real>& aRangeU = GetRangeU();
323   const std::pair<Standard_Real, Standard_Real>& aRangeV = GetRangeV();
324   const std::pair<Standard_Real, Standard_Real>& aDelta  = GetDelta ();
325
326   const Standard_Real                 aDefFace = GetDFace()->GetDeflection();
327   const Handle(BRepAdaptor_HSurface)& gFace    = GetSurface();
328   Handle(Geom_Surface)                aSurface = gFace->ChangeSurface().Surface().Surface();
329
330   const Handle(NCollection_IncAllocator) aTmpAlloc =
331     new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE);
332
333   const Handle(IMeshData::SequenceOfReal) aParams[2] = {
334     computeGrainAndFilterParameters(GetParametersU(), gFace->UResolution(aDefFace),
335       (aRangeU.second - aRangeU.first), aDelta.first,  theParameters, aTmpAlloc),
336
337     computeGrainAndFilterParameters(GetParametersV(), gFace->VResolution(aDefFace),
338       (aRangeV.second - aRangeV.first), aDelta.second, theParameters, aTmpAlloc)
339   };
340
341   // check intermediate isolines
342   Handle(IMeshData::MapOfReal) aFixedParams[2] = {
343     new IMeshData::MapOfReal(1, aTmpAlloc),
344     new IMeshData::MapOfReal(1, aTmpAlloc)
345   };
346
347   const Handle(IMeshData::MapOfReal) aParamsToRemove[2] = {
348     AnalyticalFilter(GetDFace(), GeomAbs_IsoV, aParams[1], aParams[0],
349       aFixedParams[1], aFixedParams[0]).GetControlParametersToRemove(theParameters),
350
351     AnalyticalFilter(GetDFace(), GeomAbs_IsoU, aParams[0], aParams[1],
352       aFixedParams[0], aFixedParams[1]).GetControlParametersToRemove(theParameters),
353   };
354
355   aParamsToRemove[0]->Subtract(*aFixedParams[0]);
356   aParamsToRemove[1]->Subtract(*aFixedParams[1]);
357
358   // insert nodes of the regular grid
359   Handle(IMeshData::ListOfPnt2d) aNodes = new IMeshData::ListOfPnt2d(
360     new NCollection_IncAllocator(IMeshData::MEMORY_BLOCK_SIZE_HUGE));
361
362   // insert nodes of the regular grid
363   for (Standard_Integer i = 1; i <= aParams[0]->Length(); ++i)
364   {
365     const Standard_Real aParam1 = aParams[0]->Value(i);
366     if (aParamsToRemove[0]->Contains(aParam1))
367     {
368       continue;
369     }
370
371     for (Standard_Integer j = 1; j <= aParams[1]->Length(); ++j)
372     {
373       const Standard_Real aParam2 = aParams[1]->Value(j);
374       if (aParamsToRemove[1]->Contains(aParam2))
375       {
376         continue;
377       }
378
379       aNodes->Append(gp_Pnt2d(aParam1, aParam2));
380     }
381   }
382
383   return aNodes;
384 }
385
386 //=======================================================================
387 // Function: initParameters
388 // Purpose : 
389 //=======================================================================
390 Standard_Boolean BRepMesh_NURBSRangeSplitter::initParameters() const
391 {
392   const Handle(BRepAdaptor_HSurface)& aSurface = GetSurface();
393
394   const GeomAbs_Shape aContinuity = GeomAbs_CN;
395   const std::pair<Standard_Integer, Standard_Integer> aIntervalsNb(
396     aSurface->NbUIntervals(aContinuity),
397     aSurface->NbVIntervals(aContinuity)
398   );
399
400   TColStd_Array1OfReal aIntervals[2] = {
401     TColStd_Array1OfReal(1, aIntervalsNb.first  + 1),
402     TColStd_Array1OfReal(1, aIntervalsNb.second + 1)
403   };
404
405   aSurface->UIntervals(aIntervals[0], aContinuity);
406   aSurface->VIntervals(aIntervals[1], aContinuity);
407
408   const Standard_Boolean isSplitIntervals = toSplitIntervals (
409     aSurface->ChangeSurface().Surface().Surface(), aIntervals);
410
411   if (!initParamsFromIntervals(aIntervals[0], GetRangeU(), isSplitIntervals,
412                                const_cast<IMeshData::IMapOfReal&>(GetParametersU())))
413   {
414     //if (!grabParamsOfEdges (Edge_Frontier, Param_U))
415     {
416       return Standard_False;
417     }
418   }
419
420   if (!initParamsFromIntervals(aIntervals[1], GetRangeV(), isSplitIntervals,
421                                const_cast<IMeshData::IMapOfReal&>(GetParametersV())))
422   {
423     //if (!grabParamsOfEdges (Edge_Frontier, Param_V))
424     {
425       return Standard_False;
426     }
427   }
428
429   return grabParamsOfEdges(Edge_Internal, Param_U | Param_V);
430 }
431
432 //=======================================================================
433 //function : grabParamsOfInternalEdges
434 //purpose  : 
435 //=======================================================================
436 Standard_Boolean BRepMesh_NURBSRangeSplitter::grabParamsOfEdges (
437   const EdgeType         theEdgeType,
438   const Standard_Integer theParamDimensionFlag) const
439 {
440   if ((theParamDimensionFlag & (Param_U | Param_V)) == 0)
441   {
442     return Standard_False;
443   }
444
445   const IMeshData::IFaceHandle& aDFace = GetDFace ();
446   for (Standard_Integer aWireIt = 0; aWireIt < aDFace->WiresNb (); ++aWireIt)
447   {
448     const IMeshData::IWireHandle& aDWire = aDFace->GetWire (aWireIt);
449     for (Standard_Integer aEdgeIt = 0; aEdgeIt < aDWire->EdgesNb (); ++aEdgeIt)
450     {
451       const IMeshData::IEdgePtr& aDEdge = aDWire->GetEdge (aEdgeIt);
452       for (Standard_Integer aPCurveIt = 0; aPCurveIt < aDEdge->PCurvesNb (); ++aPCurveIt)
453       {
454         const IMeshData::IPCurveHandle& aDPCurve = aDEdge->GetPCurve (aPCurveIt);
455         if (aDPCurve->GetFace () == aDFace)
456         {
457           if (theEdgeType == Edge_Internal && !aDPCurve->IsInternal ())
458           {
459             continue;
460           }
461
462           for (Standard_Integer aPointIt = 0; aPointIt < aDPCurve->ParametersNb (); ++aPointIt)
463           {
464             const gp_Pnt2d& aPnt2d = aDPCurve->GetPoint (aPointIt);
465             if (theParamDimensionFlag & Param_U)
466             {
467               const_cast<IMeshData::IMapOfReal&>(GetParametersU ()).Add (aPnt2d.X ());
468             }
469
470             if (theParamDimensionFlag & Param_V)
471             {
472               const_cast<IMeshData::IMapOfReal&>(GetParametersV ()).Add (aPnt2d.Y ());
473             }
474           }
475         }
476       }
477     }
478   }
479
480   return Standard_True;
481 }
482
483 //=======================================================================
484 //function : computeGrainAndFilterParameters
485 //purpose  : 
486 //=======================================================================
487 Handle(IMeshData::SequenceOfReal) BRepMesh_NURBSRangeSplitter::computeGrainAndFilterParameters(
488   const IMeshData::IMapOfReal&            theSourceParams,
489   const Standard_Real                     theTol2d,
490   const Standard_Real                     theRangeDiff,
491   const Standard_Real                     theDelta,
492   const IMeshTools_Parameters&            theParameters,
493   const Handle(NCollection_IncAllocator)& theAllocator) const
494 {
495   // Sort and filter sequence of parameters
496   Standard_Real aMinDiff = Precision::PConfusion();
497   if (theDelta < 1.)
498   {
499     aMinDiff /= theDelta;
500   }
501
502   aMinDiff = Max(theParameters.MinSize, aMinDiff);
503
504   const Standard_Real aDiffMaxLim = 0.1 * theRangeDiff;
505   const Standard_Real aDiffMinLim = Max(0.005 * theRangeDiff,
506                                         2. * theTol2d);
507   const Standard_Real aDiff = Max(theParameters.MinSize,
508                                   Min(aDiffMaxLim, aDiffMinLim));
509   return filterParameters(theSourceParams, aMinDiff, aDiff, theAllocator);
510 }
511
512 //=======================================================================
513 //function : filterParameters
514 //purpose  : 
515 //=======================================================================
516 Handle(IMeshData::SequenceOfReal) BRepMesh_NURBSRangeSplitter::filterParameters(
517   const IMeshData::IMapOfReal&            theParams,
518   const Standard_Real                     theMinDist,
519   const Standard_Real                     theFilterDist,
520   const Handle(NCollection_IncAllocator)& theAllocator) const
521 {
522   Handle(IMeshData::SequenceOfReal) aResult = new IMeshData::SequenceOfReal(theAllocator);
523
524   // Sort sequence of parameters
525   const Standard_Integer anInitLen = theParams.Extent();
526
527   if (anInitLen < 1)
528   {
529     return aResult;
530   }
531
532   TColStd_Array1OfReal aParamArray(1, anInitLen);
533   Standard_Integer j;
534   for (j = 1; j <= anInitLen; j++)
535     aParamArray(j) = theParams(j);
536
537   std::sort(aParamArray.begin(), aParamArray.end());
538
539   // mandatory pre-filtering using the first (minimal) filter value
540   Standard_Integer aParamLength = 1;
541   for (j = 2; j <= anInitLen; j++)
542   {
543     if ((aParamArray(j) - aParamArray(aParamLength)) > theMinDist)
544     {
545       if (++aParamLength < j)
546         aParamArray(aParamLength) = aParamArray(j);
547     }
548   }
549
550   //perform filtering on series
551   Standard_Real aLastAdded, aLastCandidate;
552   Standard_Boolean isCandidateDefined = Standard_False;
553   aLastAdded = aParamArray(1);
554   aLastCandidate = aLastAdded;
555   aResult->Append(aLastAdded);
556
557   for (j = 2; j < aParamLength; j++)
558   {
559     Standard_Real aVal = aParamArray(j);
560     if (aVal - aLastAdded > theFilterDist)
561     {
562       //adds the parameter
563       if (isCandidateDefined)
564       {
565         aLastAdded = aLastCandidate;
566         isCandidateDefined = Standard_False;
567         j--;
568       }
569       else
570       {
571         aLastAdded = aVal;
572       }
573       aResult->Append(aLastAdded);
574       continue;
575     }
576
577     aLastCandidate = aVal;
578     isCandidateDefined = Standard_True;
579   }
580   aResult->Append(aParamArray(aParamLength));
581
582   return aResult;
583 }