1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
3 // This file is part of Open CASCADE Technology software library.
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.
11 // Alternatively, this file may be used under the terms of Open CASCADE
12 // commercial license or contractual agreement.
14 #ifndef _ApproxInt_KnotTools_HeaderFile
15 #define _ApproxInt_KnotTools_HeaderFile
17 #ifndef _Standard_DefineAlloc_HeaderFile
18 #include <Standard_DefineAlloc.hxx>
20 #ifndef _Standard_Macro_HeaderFile
21 #include <Standard_Macro.hxx>
24 #ifndef _Standard_Boolean_HeaderFile
25 #include <Standard_Boolean.hxx>
27 #ifndef _Standard_Real_HeaderFile
28 #include <Standard_Real.hxx>
30 #ifndef _Standard_Integer_HeaderFile
31 #include <Standard_Integer.hxx>
34 #include <TColgp_Array1OfPnt2d.hxx>
35 #include <TColgp_Array1OfPnt.hxx>
36 #include <TColStd_Array1OfReal.hxx>
37 #include <NCollection_LocalArray.hxx>
40 template <class A> class NCollection_Sequence;
41 template <class A> class NCollection_List;
42 template <class A> class NCollection_Vector;
44 // Corresponds for debug information output.
45 // Debug information is also printed when OCCT_DEBUG defined.
46 //#define APPROXINT_KNOTTOOLS_DEBUG
48 //! This class intended to build knots sequence on discrete set of points for further approximation into bspline curve.
50 //! Short description of algorithm:
51 //! 1) Build discrete curvature on points set.
52 //! 2) According to special rules build draft knots sequence.
53 //! 3) Filter draft sequence to build output sequence.
55 //! For more details look at:
56 //! Anshuman Razdan - Knot Placement for B-Spline curve Approximation.
57 class ApproxInt_KnotTools
63 //! Main function to build optimal knot sequence.
64 //! At least one set from (thePntsXYZ, thePntsU1V1, thePntsU2V2) should exist.
65 //! @param thePntsXYZ - Set of 3d points.
66 //! @param thePntsU1V1 - Set of 2d points.
67 //! @param thePntsU2V2 - Set of 2d points.
68 //! @param thePars - Expected parameters associated with set.
69 //! @param theApproxXYZ - Flag, existence of 3d set.
70 //! @param theApproxU1V1 - Flag existence of first 2d set.
71 //! @param theApproxU2V2 - Flag existence of second 2d set.
72 //! @param theMinNbPnts - Minimal number of points per knot interval.
73 //! @param theKnots - output knots sequence.
74 Standard_EXPORT static void BuildKnots(const TColgp_Array1OfPnt& thePntsXYZ,
75 const TColgp_Array1OfPnt2d& thePntsU1V1,
76 const TColgp_Array1OfPnt2d& thePntsU2V2,
77 const math_Vector& thePars,
78 const Standard_Boolean theApproxXYZ,
79 const Standard_Boolean theApproxU1V1,
80 const Standard_Boolean theApproxU2V2,
81 const Standard_Integer theMinNbPnts,
82 NCollection_Vector<Standard_Integer>& theKnots);
86 //! Compute indices of knots:
88 //! I: Build discrete curvature in points set,
89 //! using outer product of two vectors.
91 //! II: Put knots in points which has extremity on discrete curvature.
93 //! III: Put knots in monotone intervals of curvature.
95 //! IV: Put additional knots near extrema points.
96 static void ComputeKnotInds(const NCollection_LocalArray<Standard_Real>& theCoords,
97 const Standard_Integer theDim,
98 const math_Vector& thePars,
99 NCollection_Sequence<Standard_Integer>& theInds);
101 //! Insert knots before index I.
103 //! I: Check curvature change:
104 //! if ( maxCurvature / minCurvature ) of current interval greater than
105 //! threshold value, then stop and use upper index as knot.
107 //! II: Check midpoint criteria:
108 //! If exist point between two knot indices with angle greater than
109 //! threshold value, then stop and put this index as knot.
110 static Standard_Boolean InsKnotBefI(const Standard_Integer theI,
111 const TColStd_Array1OfReal& theCurv,
112 const NCollection_LocalArray<Standard_Real>& theCoords,
113 const Standard_Integer theDim,
114 NCollection_Sequence<Standard_Integer>& theInds,
115 const Standard_Boolean ChkCurv);
117 //! Perform knots filtration.
119 //! I: Filter too big number of points per knot interval.
121 //! II: Filter points with too small amount of points per knot interval.
123 //! III: Fill Last Knot.
124 static void FilterKnots(NCollection_Sequence<Standard_Integer>& theInds,
125 const Standard_Integer theMinNbPnts,
126 NCollection_Vector<Standard_Integer>& theLKnots);