HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GA_Basis.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: GA_Basis.h ( GA Library, C++)
7  *
8  * COMMENTS: Stores an array of knots for a NURBs/Bezier patch
9  */
10 
11 #pragma once
12 
13 #ifndef __GA_Basis__
14 #define __GA_Basis__
15 
16 #include "GA_API.h"
17 #include "GA_Defines.h"
18 #include "GA_KnotVector.h"
19 
20 #include <UT/UT_VectorTypes.h>
21 
22 #include <SYS/SYS_Types.h>
23 
24 #include <iosfwd>
25 
26 
27 class UT_IStream;
28 class UT_JSONParser;
29 class UT_JSONValue;
30 class UT_JSONWriter;
31 
32 
34 {
37 };
38 
39 #define GA_BASIS_BEZIER_NAME "Bezier"
40 #define GA_BASIS_NURBS_NAME "NURBS"
41 
42 /// @brief Bezier or NURBS basis classes which maintain knot vectors
43 ///
44 /// The GA_Basis class maintains the knot vectors for Bezier or NURBS
45 /// splines. The basis consists of:
46 /// -# The order of the basis (degree+1)
47 /// -# The knot vector (an array of doubles)
48 /// -# A flag for end interpolation (NURBS only)
50 {
51 public:
52  /// Tolerance used to check equality of knot values.
53  /// The default of 1e-5 used by SYSisEqual et al. is too large
54  /// for NURBS curves with 45K vertices.
55  static const fpreal theBasisTolerance;
56 
57  /// Table of binomial coefficients
58  static const fpreal theBinomial[GA_MAXORDER][GA_MAXORDER];
59 
60  /// The default constructor will initialize order=0 and length=0.
61  GA_Basis();
62  GA_Basis(const GA_Basis &src);
63 
64  /// Destructor
65  virtual ~GA_Basis() {}
66 
67  /// Re-initializes the basis to default values
68  virtual void reset() = 0;
69 
70  /// Compare to see whether the basis is equal
71  virtual bool isEqual(const GA_Basis &basis) const = 0;
72 
73  /// Return the type of the basis
74  virtual GA_BASIS_TYPE getType() const = 0;
75 
76  /// Return the name of the basis
77  virtual const char *getTypeName() const = 0;
78 
79  /// Return the order of the basis
80  int getOrder() const { return myOrder; }
81 
82  /// Return the length of the knot vector
83  int getLength() const { return myData.entries(); }
84 
85  /// Return the dimension of the basis. For NURBS, this will be equivalent
86  /// to (getLength()-getOrder()). For Beziers the dimension is equivalent
87  /// to the length of the knot vector.
88  virtual int getDimension() const = 0;
89 
90  /// Get the boundaries of the valid evaluation interval (as indices)
91  virtual bool getValidInterval(int &a, int &b) const = 0;
92  /// Get the boundaries of the valid range of evaluation
93  bool getValidRange(fpreal &a, fpreal &b) const;
94 
95  /// Evaluate on a specific domain interval, on which at least one
96  /// basis function is non-zero given domain point u.
97  virtual void evalInterval(fpreal u, int offset, int deriv,
98  fpreal64 *vals) const = 0;
99  virtual void evalInterval(fpreal u, int offset,
100  int deriv, fpreal32 *vals) const = 0;
101 
102  /// Evaluate all the derivatives of the basis from 0 to deriv (inclusive).
103  virtual void evalDerivativeMatrix(fpreal u, int offset, int deriv,
104  fpreal64 bmatx[][GA_MAXORDER]) const = 0;
105  virtual void evalDerivativeMatrix(fpreal u,
106  int offset, int deriv,
107  fpreal32 bmatx[][GA_MAXORDER]) const = 0;
108 
109  /// Return either the break-point (Bezier) or the first valid segment for
110  /// NURBs. Returns -1 on an error.
111  virtual int findStartOffset(fpreal u, int uoffset) const = 0;
112 
113  /// Compute one basis function (ie. the one with the given index)
114  /// value at u.
115  virtual fpreal computeBValue(int index, fpreal u) const = 0;
116 
117  /// Return the number of breakpoints (ie. unique knots) in the knot
118  /// vector, in the valid interval.
119  virtual int getBreakCount() const = 0;
120 
121  /// Given the index of a knot (kidx) and two bounds in the knot sequence
122  /// (a and b) find out the index of the breakpoint that the knot represents,
123  /// and possibly adjust kidx so that knot[kidx+1] > knot[kidx]. Return -1
124  /// if not found.
125  virtual int knotToBreakpoint(int &kidx, int a, int b) const = 0;
126 
127  /// Compute an array of breakpoints (i.e. unique knots) in the valid
128  /// interval and return their number. The tolerance is used to
129  /// differentiate between close knots.
130  virtual int getBreakpoints(GA_KnotVector &a,
131  fpreal tol=theBasisTolerance) const = 0;
132 
133  /// Compute an array of multiplicities for each knot in the knot sequence.
134  /// Return the number of breakpoints (i.e. unique knots).
135  int getMultiplicities(UT_IntArray &arr) const;
136 
137  /// Return the multiplicity of a domain point or -1 if outside the domain.
138  /// "uidx" is the index of the largest breakpoint <= u.
139  virtual int getMultiplicity(fpreal u, int &uidx) const = 0;
140 
141  /// Return the expected multiplicity of the end knots (1 by default):
142  virtual int getEndMultiplicity() const;
143 
144  /// Given a domain range in the valid interval, compute the range of CVs
145  /// that will be involved in the evaluation of the curve in that range.
146  /// Since the basis doesn't know about wrapping, the endcv index might
147  /// be higher than the spline's number of CVs.
148  virtual void getCvRangeOfDomain(int ustartidx, int ustopidx,
149  int &start_cv, int &end_cv) const = 0;
150  virtual void getCvRangeOfDomain(fpreal ustart, fpreal ustop,
151  int &start_cv, int &end_cv) const = 0;
152 
153  /// Given valid breakpoint index, compute the range of CVs that have a
154  /// non-zero influence at the knot of the breakpoint. Since the basis
155  /// doesn't know about wrapping, the endcv index might be higher than the
156  /// spline's number of CVs.
157  virtual void getCvRangeOfBreakpoint(int bkp,
158  int &startcv, int &stopcv) const = 0;
159 
160  /// Generate a new basis of the species specified in the name or type
161  /// respectively.
162  static GA_Basis *newSpecies(GA_BASIS_TYPE type);
163 
164  /// Returns true if any NANs snuck into this vector.
165  bool testForNan() const;
166 
167  /// I/O functions for houdini9 format
168  virtual bool saveH9(std::ostream &os, bool wrapped, bool binary) const = 0;
169  virtual bool loadH9(UT_IStream &is, int cvs, bool wrapped) = 0;
170 
171  /// Save data to a JSON stream.
172  /// @section JSON-GA_Basis JSON Schema: GA_Basis
173  /// @code
174  /// {
175  /// "name" : "GA_Basis",
176  /// "description" : "A basis definition.",
177  /// "type" : "orderedmap",
178  /// "properties": {
179  /// "type": {
180  /// "type" : "string",
181  /// "description" : "Type of basis (case sensitive)",
182  /// "enum" : [ "Bezier", "NURBS" ],
183  /// },
184  /// "order": {
185  /// "type" : "integer",
186  /// "description" : "Order of the basis",
187  /// "minimum" : 2,
188  /// },
189  /// "endinterpolation": {
190  /// "type" : "boolean",
191  /// "description" : "End interpolation",
192  /// "default" : true,
193  /// "optional" : true,
194  /// },
195  /// "knots": {
196  /// "type" : { "$ref" : "GA_KnotVector" }
197  /// "description" : "Knot vector",
198  /// },
199  /// }
200  /// @endcode
201  /// @see @ref JSON_FileFormat
202  bool jsonSave(UT_JSONWriter &w) const;
203 
204  /// Save to a JSON value
205  bool jsonSave(UT_JSONValue &v) const;
206 
207  /// Load basis from a JSON parser
208  bool jsonLoad(UT_JSONParser &p);
209 
210  /// Load basis from a JSON value
211  bool jsonLoad(UT_JSONParser &p, const UT_JSONValue &v);
212 
213  /// Copy my data from the given source. If performing a compatible copy, we
214  /// only do the copy if if b has the same order and length as we do.
215  virtual bool copyFrom(const GA_Basis &b, bool compatible=false);
216 
217  /// When making the basis valid, the adapt enum will be used to adjust the
218  /// end-interpolation and knot values to ensure that the basis is valid.
219  enum
220  {
222  GA_BASIS_ADAPT_FLAGS, // Change flags to match knot values
223  GA_BASIS_ADAPT_KNOTS, // Change knots to match flags
224  };
225  /// The validate() method will force the basis to be valid (if possible).
226  /// The adapt enum can be used to control the behaviour of this method.
227  virtual bool validate(int adapt=GA_Basis::GA_BASIS_ADAPT_NONE) = 0;
228 
229  /// The checkValid() methods test to see whether th basis is valid given
230  /// a curve with
231  /// -# cvLen vertices
232  /// -# A basis length of bLen
233  /// -# Periodicity determined by doesWrap
234  virtual bool checkValid(int cvLen, int bLen, bool doesWrap) const = 0;
235  /// Convenience method to check validity using the basis's length
236  bool checkValid(int cvLen, bool doesWrap) const
237  { return checkValid(cvLen, getLength(), doesWrap); }
238 
239  /// Compute the idx'th greville abscissa of the domain vector. Clamping
240  /// to the valid interval is optional and might not make any difference
241  /// for some spline types.
242  virtual fpreal getGreville(int idx, bool clamp=true,
243  bool wrap=false) const = 0;
244 
245  /// Grow the length of the basis by one, and set the value of the new entry
246  /// to last knot+1. The method returns the index of the appended element.
247  virtual int grow(bool wrapped=false) = 0;
248 
249  /// Shrink the basis by one. The basis should not shrink beyond a valid
250  /// length. Return the new length.
251  virtual int shrink(bool wrapped=false) = 0;
252 
253  /// Attach another basis to us and grow our basis as a result. The bases
254  /// must have the same type and order.
255  /// If "overlap" is true, we overlap the beginning of b with
256  /// our end.
257  /// Spreading makes sense when you can have multiple knots in the basis, and
258  /// causes identical knots to be spread within range of the neighbouring
259  /// knots.
260  virtual bool attach(const GA_Basis &b, bool overlap=true,
261  bool spread=false) = 0;
262 
263  /// Change the size of the basis (and maybe some of its values too) to
264  /// make it a valid basis for wrapped splines.
265  virtual void setWrapping(bool wrap) = 0;
266 
267  /// Reverse the breakpoints in the basis.
268  virtual void reverse(bool wrapped) = 0;
269 
270  /// Find index in the knot vector for the break point corresponding to k.
271  virtual int findOffset(fpreal k, int startIdx=0) const = 0;
272 
273  /// Convert a value from unit to real knot. Usually you'll want to map
274  /// only within the valid interval.
275  fpreal unitToReal(fpreal u_unit, bool valid_interval=true) const;
276  /// Convert from real to unit values. Usually, you'll want to map only
277  /// within the valid interval.
278  fpreal realToUnit(fpreal u_real, bool valid_interval=true) const;
279 
280  /// Append a knot value to the end of the knot vector
281  int append(fpreal v) { return myData.append(v); }
282  /// Insert a knot value at a specific location
283  /// @note The order of arguments is different that UT_ValArray
284  int insertKnot(fpreal v, int i)
285  {
286  return myData.insertKnot(v, i);
287  }
288  /// Remove a knot value (by index)
289  int remove(int i) { return myData.removeIndex(i); }
290 
291  /// Merge the given basis into ours provided they both have the same order.
292  /// If their order is different returns false. Otherwise return true.
293  /// A copy of "b"'s knots is mapped to our knot interval first, then merged
294  /// with us.
295  /// The second method stres the mapping into "b" itself.
296  bool merge(const GA_Basis &b);
297  bool merge(GA_Basis &b);
298 
299  /// Find the index of a breakpoint such that the distance between it and the
300  /// next breakpoint is the largest in the whole sequence. The search is
301  /// done between two specified indices.
302  int findMaxSpan(int start, int stop) const;
303 
304  /// Convenience method to normalize this basis.
305  void normalize(fpreal scale=0, const fpreal *neworig=0);
306 
307  /// Rebuild the basis as a uniform sequence with a given step.
308  virtual void rebuild(fpreal ustart=0, fpreal ustep=1) = 0;
309 
310  /// Make the basis uniform of just find out if it is uniform:
311  virtual void makeUniform(fpreal ustep=1) = 0;
312 
313  /// Normalize the vector to the new length and optionally shift it to
314  /// a new origin. If "knots" is given, the resulting values are put in it.
315  /// The first method maps us to the interval of basis "b". In other words,
316  /// our extremities will be changed to match those of basis "b".
317  void map(const GA_Basis &b);
318  static void map(GA_KnotVector &knots, const GA_KnotVector &src,
319  fpreal newlen=1, const fpreal *neworig=0);
320  void map(fpreal newlen=1, const fpreal *neworig=0)
321  {
322  map(myData, myData, newlen, neworig);
323  }
324 
325  /// Map domain value "u", which should be between our min and max knots,
326  /// to a domain value in basis "b". If you know the index of the knot
327  /// in our sequence such that k[uoffset] <= u, enter in as the last
328  /// parameter. The method returns -1 if it has failed (the two bases don't
329  /// have the same length or u is out of range). Otherwise it returns the
330  /// uoffset.
331  int map(const GA_Basis &b, fpreal &u,
332  int uoffset=0) const;
333 
334  /// Reparameterize the basis using the chord-length method, and clamp it
335  /// to the valid interval. The origin and length of the valid domain remains
336  /// unchanged.
337  virtual void chord(UT_Vector4Array &cvs) = 0;
338 
339  /// Slide the knots found in the given range left or right by an amount at
340  /// most as large as the distance to the nearest knot outside the range.
341  /// The bias is a percentage value of the left-right distance, its default
342  /// value is 0.5 (i.e. don't change anything), and is clamped to [0,1].
343  virtual bool slideRange(fpreal umin, fpreal umax,
344  fpreal ubias=0.5) = 0;
345 
346  /// Set the order of the basis. Careful when you use it because it must
347  /// be <= GA_MAXORDER and must be appropriate for the number of knots.
348  void setOrder(int ord) { myOrder = ord; }
349 
350  /// Get the greatest value knot that is smaller than the search value.
351  /// Return false if search value is out of range.
352  /// The default search range is from order-1 to dimension.
353  bool findClosest(fpreal val, int &idx,
354  int startidx, int endidx) const;
355 
356  /// Return the index of the first knot that is approximately equal to
357  /// val. The entire sequence is searched from startidx.
358  /// Return -1 if not found.
359  int findApproximate(fpreal val, int startidx,
360  fpreal tol=theBasisTolerance) const;
361 
362  /// Compute alphas needed for degree elevation. "increment" is the amount
363  /// by which we want the degree to grow.
364  void computeRaiseOrderAlphas(int increment,
365  fpreal bezalfs[][GA_MAXORDER]) const;
366 
367  // Grow or shrink the basis array
368  void resize(int sz);
369 
370  /// @{
371  /// Get the knot vector for the basis
372  const GA_KnotVector &getVector() const { return myData; }
373  GA_KnotVector &getVector() { return myData; }
374  const GA_KnotVector &getKnotVector() const { return myData; }
375  GA_KnotVector &getKnotVector() { return myData; }
376  /// @}
377 
378  /// Return the amount of memory used
379  virtual int64 getMemoryUsage(bool inclusive) const
380  {
381  int64 mem = inclusive ? sizeof(*this) : 0;
382  mem += myData.getMemoryUsage(false);
383  return mem;
384  }
385 
386 protected:
387  const GA_KnotFloat *getData() const { return myData.getRawArray(); }
388  GA_KnotVector myData; // TODO: Replace with UT_DoubleArray
389  int myOrder;
390 
391  static void doMerge(GA_KnotVector &avec, const GA_KnotVector &bvec,
392  GA_KnotVector *inserts=0);
393 };
394 
395 #endif
virtual ~GA_Basis()
Destructor.
Definition: GA_Basis.h:65
const GA_KnotFloat * getData() const
Definition: GA_Basis.h:387
void map(fpreal newlen=1, const fpreal *neworig=0)
Definition: GA_Basis.h:320
int myOrder
Definition: GA_Basis.h:389
int myOrder
Definition: GT_CurveEval.h:263
const GLdouble * v
Definition: glcorearb.h:836
GLuint start
Definition: glcorearb.h:474
const GLuint GLenum const void * binary
Definition: glcorearb.h:1923
bool checkValid(int cvLen, bool doesWrap) const
Convenience method to check validity using the basis's length.
Definition: GA_Basis.h:236
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define GA_MAXORDER
Definition: GA_Defines.h:17
JSON reader class which handles parsing of JSON or bJSON files.
Definition: UT_JSONParser.h:72
#define GA_API
Definition: GA_API.h:12
Class which writes ASCII or binary JSON streams.
Definition: UT_JSONWriter.h:32
png_uint_32 i
Definition: png.h:2877
long long int64
Definition: SYS_Types.h:100
GA_API const UT_StringHolder scale
GA_KnotVector myData
Definition: GA_Basis.h:388
double fpreal64
Definition: SYS_Types.h:185
void setOrder(int ord)
Definition: GA_Basis.h:348
GLintptr offset
Definition: glcorearb.h:664
Bezier or NURBS basis classes which maintain knot vectors.
Definition: GA_Basis.h:49
virtual int64 getMemoryUsage(bool inclusive) const
Return the amount of memory used.
Definition: GA_Basis.h:379
GA_KnotVector & getVector()
Definition: GA_Basis.h:373
static const fpreal theBasisTolerance
Definition: GA_Basis.h:55
GridType::Ptr normalize(const GridType &grid, bool threaded, InterruptT *interrupt)
Normalize the vectors of the given vector-valued grid.
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
double fpreal
Definition: SYS_Types.h:263
GA_KnotVector & getKnotVector()
Definition: GA_Basis.h:375
int append(fpreal v)
Append a knot value to the end of the knot vector.
Definition: GA_Basis.h:281
GA_BASIS_TYPE
Definition: GA_Basis.h:33
int insertKnot(fpreal v, int i)
Definition: GA_Basis.h:284
GLuint index
Definition: glcorearb.h:785
const GA_KnotVector & getVector() const
Definition: GA_Basis.h:372
GLuint GLfloat * val
Definition: glcorearb.h:1607
int getLength() const
Return the length of the knot vector.
Definition: GA_Basis.h:83
Class to store JSON objects as C++ objects.
Definition: UT_JSONValue.h:75
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:856
const GA_KnotVector & getKnotVector() const
Definition: GA_Basis.h:374
fpreal64 GA_KnotFloat
Definition: GA_KnotVector.h:25
float fpreal32
Definition: SYS_Types.h:184
int getOrder() const
Return the order of the basis.
Definition: GA_Basis.h:80
GLenum clamp
Definition: glcorearb.h:1233
GLenum src
Definition: glcorearb.h:1792