0025929: Make Approx_ComputeLine algorithm adaptive
[occt.git] / src / ApproxInt / ApproxInt_KnotTools.hxx
1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
2 //
3 // This file is part of Open CASCADE Technology software library.
4 //
5 // This library is free software; you can redistribute it and/or modify it under
6 // the terms of the GNU Lesser General Public License version 2.1 as published
7 // by the Free Software Foundation, with special exception defined in the file
8 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
9 // distribution for complete text of the license and disclaimer of any warranty.
10 //
11 // Alternatively, this file may be used under the terms of Open CASCADE
12 // commercial license or contractual agreement.
13
14 #ifndef _ApproxInt_KnotTools_HeaderFile
15 #define _ApproxInt_KnotTools_HeaderFile
16
17 #ifndef _Standard_HeaderFile
18 #include <Standard.hxx>
19 #endif
20 #ifndef _Standard_DefineAlloc_HeaderFile
21 #include <Standard_DefineAlloc.hxx>
22 #endif
23 #ifndef _Standard_Macro_HeaderFile
24 #include <Standard_Macro.hxx>
25 #endif
26
27 #ifndef _Standard_Boolean_HeaderFile
28 #include <Standard_Boolean.hxx>
29 #endif
30 #ifndef _Standard_Real_HeaderFile
31 #include <Standard_Real.hxx>
32 #endif
33 #ifndef _Standard_Integer_HeaderFile
34 #include <Standard_Integer.hxx>
35 #endif
36
37 #include <TColgp_Array1OfPnt2d.hxx>
38 #include <TColgp_Array1OfPnt.hxx>
39 #include <TColStd_Array1OfReal.hxx>
40 #include <NCollection_LocalArray.hxx>
41
42 class math_Vector;
43 template <class A> class NCollection_Sequence;
44 template <class A> class NCollection_List;
45 template <class A> class NCollection_Vector;
46
47 // Corresponds for debug information output.
48 // Debug information is also printed when OCCT_DEBUG defined.
49 //#define APPROXINT_KNOTTOOLS_DEBUG
50
51 //! This class intended to build knots sequence on discrete set of points for further approximation into bspline curve.
52 //!
53 //! Short description of algorithm:
54 //! 1) Build discrete curvature on points set.
55 //! 2) According to special rules build draft knots sequence.
56 //! 3) Filter draft sequence to build output sequence.
57 //!
58 //! For more details look at:
59 //! Anshuman Razdan - Knot Placement for B-Spline curve Approximation.
60 class ApproxInt_KnotTools
61 {
62 public:
63
64   DEFINE_STANDARD_ALLOC
65
66   //! Main function to build optimal knot sequence.
67   //! At least one set from (thePntsXYZ, thePntsU1V1, thePntsU2V2) should exist.
68   //! @param thePntsXYZ - Set of 3d points.
69   //! @param thePntsU1V1 - Set of 2d points.
70   //! @param thePntsU2V2 - Set of 2d points.
71   //! @param thePars - Expected parameters assoiated with set.
72   //! @param theApproxXYZ - Flag, existence of 3d set.
73   //! @param theApproxU1V1 - Flag existence of first 2d set.
74   //! @param theApproxU2V2 - Flag existence of second 2d set.
75   //! @param theMinNbPnts - Minimal number of points per knot interval.
76   //! @param theKnots - output knots sequence.
77   Standard_EXPORT static void BuildKnots(const TColgp_Array1OfPnt& thePntsXYZ,
78                                          const TColgp_Array1OfPnt2d& thePntsU1V1,
79                                          const TColgp_Array1OfPnt2d& thePntsU2V2,
80                                          const math_Vector& thePars,
81                                          const Standard_Boolean theApproxXYZ,
82                                          const Standard_Boolean theApproxU1V1,
83                                          const Standard_Boolean theApproxU2V2,
84                                          const Standard_Integer theMinNbPnts,
85                                          NCollection_Vector<Standard_Integer>& theKnots);
86
87 private:
88
89   //! Compute indices of knots:
90   //!
91   //! I: Build discrete curvature in points set,
92   //! using outer product of two vectors.
93   //!
94   //! II: Put knots in points which has extremity on discrete curvature.
95   //!
96   //! III: Put knots in monotone intervals of curvature.
97   //!
98   //! IV: Put additional knots near extrema points.
99   static void ComputeKnotInds(const NCollection_LocalArray<Standard_Real>& theCoords,
100                               const Standard_Integer theDim,
101                               const math_Vector& thePars,
102                               NCollection_Sequence<Standard_Integer>& theInds);
103
104   //! Insert knots before index I.
105   //!
106   //! I: Check curvature change:
107   //! if ( maxCurvature / minCurvature ) of current interval greater than 
108   //! threshold value, then stop and use upper index as knot.
109   //!
110   //! II: Check midpoint criteria:
111   //! If exist point between two knot indices with angle greater than
112   //! threshold value, then stop and put this index as knot.
113   static Standard_Boolean InsKnotBefI(const Standard_Integer theI,
114                                       const TColStd_Array1OfReal& theCurv,
115                                       const NCollection_LocalArray<Standard_Real>& theCoords,
116                                       const Standard_Integer theDim, 
117                                       NCollection_Sequence<Standard_Integer>& theInds,
118                                       const Standard_Boolean ChkCurv);
119
120   //! Perform knots filtration.
121   //!
122   //! I: Filter too big number of points per knot interval.
123   //!
124   //! II: Filter poins with too small amount of points per knot interval.
125   //!
126   //! III: Fill Last Knot.
127   static void FilterKnots(NCollection_Sequence<Standard_Integer>& theInds, 
128                           const Standard_Integer theMinNbPnts,
129                           NCollection_Vector<Standard_Integer>& theLKnots);
130 };
131
132 #endif