MercuryDPM  Trunk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
NurbsUtils Namespace Reference

Classes

class  array2
 A simple class for representing 2D runtime arrays. More...
 

Functions

bool isKnotVectorMonotonic (const std::vector< double > &knots)
 
bool close (double a, double b, double eps)
 
int findSpan (int degree, const std::vector< double > &knots, double u)
 Find the span of the given parameter in the knot vector. More...
 
double bsplineOneBasis (int i, int deg, const std::vector< double > &U, double u)
 Compute a single B-spline basis function. More...
 
void bsplineBasis (int deg, int span, const std::vector< double > &knots, double u, std::vector< double > &N)
 Compute all non-zero B-spline basis functions. More...
 
void bsplineDerBasis (int deg, int span, const std::vector< double > &knots, double u, int nDers, std::vector< std::vector< double >> &ders)
 Compute all non-zero derivatives of B-spline basis functions. More...
 

Function Documentation

void NurbsUtils::bsplineBasis ( int  deg,
int  span,
const std::vector< double > &  knots,
double  u,
std::vector< double > &  N 
)

Compute all non-zero B-spline basis functions.

Parameters
[in]degDegree of the basis function.
[in]spanIndex obtained from findSpan() corresponding the u and knots.
[in]knotsKnot vector corresponding to the basis functions.
[in]uParameter to evaluate the basis functions at.
[in,out]NValues of (deg+1) non-zero basis functions.

Definition at line 129 of file NurbsUtils.cc.

Referenced by NurbsSurface::evaluate().

131 {
132  N.clear();
133  N.resize(deg + 1, 0.0);
134  std::vector<double> left, right;
135  left.resize(deg + 1, 0.0);
136  right.resize(deg + 1, 0.0);
137 
138  N[0] = 1.0;
139 
140  for (int j = 1; j <= deg; j++)
141  {
142  left[j] = (u - knots[span + 1 - j]);
143  right[j] = knots[span + j] - u;
144  Mdouble saved = 0.0;
145  for (int r = 0; r < j; r++)
146  {
147  const Mdouble temp = N[r] / (right[r + 1] + left[j - r]);
148  N[r] = saved + right[r + 1] * temp;
149  saved = left[j - r] * temp;
150  }
151  N[j] = saved;
152  }
153 }
double Mdouble
Definition: GeneralDefine.h:34
void NurbsUtils::bsplineDerBasis ( int  deg,
int  span,
const std::vector< double > &  knots,
double  u,
int  nDers,
std::vector< std::vector< double >> &  ders 
)

Compute all non-zero derivatives of B-spline basis functions.

Parameters
[in]degDegree of the basis function.
[in]spanIndex obtained from findSpan() corresponding the u and knots.
[in]knotsKnot vector corresponding to the basis functions.
[in]uParameter to evaluate the basis functions at.
[in]nDersNumber of derivatives to compute (nDers <= deg)
[in,out]dersValues of non-zero derivatives of basis functions.

Definition at line 155 of file NurbsUtils.cc.

References constants::i.

Referenced by NurbsSurface::evaluateDerivatives().

156  {
157 
158  std::vector<double> left, right;
159  left.resize(deg + 1, 0.0);
160  right.resize(deg + 1, 0.0);
161  double saved = 0.0, temp = 0.0;
162 
163  array2<double> ndu(deg + 1, deg + 1);
164  ndu(0, 0) = 1.0;
165 
166  for (int j = 1; j <= deg; j++) {
167  left[j] = u - knots[span + 1 - j];
168  right[j] = knots[span + j] - u;
169  saved = 0.0;
170 
171  for (int r = 0; r < j; r++) {
172  // Lower triangle
173  ndu(j, r) = right[r + 1] + left[j - r];
174  temp = ndu(r, j - 1) / ndu(j, r);
175  // Upper triangle
176  ndu(r, j) = saved + right[r + 1] * temp;
177  saved = left[j - r] * temp;
178  }
179 
180  ndu(j, j) = saved;
181  }
182 
183  ders.clear();
184  ders.resize(nDers + 1);
185  for (int i = 0; i < ders.size(); i++) {
186  ders[i].resize(deg + 1, 0.0);
187  }
188 
189  for (int j = 0; j <= deg; j++) {
190  ders[0][j] = ndu(j, deg);
191  }
192 
193  array2<double> a(2, deg + 1);
194 
195  for (int r = 0; r <= deg; r++) {
196  int s1 = 0;
197  int s2 = 1;
198  a(0, 0) = 1.0;
199 
200  for (int k = 1; k <= nDers; k++) {
201  double d = 0.0;
202  int rk = r - k;
203  int pk = deg - k;
204  int j1 = 0;
205  int j2 = 0;
206 
207  if (r >= k) {
208  a(s2, 0) = a(s1, 0) / ndu(pk + 1, rk);
209  d = a(s2, 0) * ndu(rk, pk);
210  }
211 
212  if (rk >= -1) {
213  j1 = 1;
214  }
215  else {
216  j1 = -rk;
217  }
218 
219  if (r - 1 <= pk) {
220  j2 = k - 1;
221  }
222  else {
223  j2 = deg - r;
224  }
225 
226  for (int j = j1; j <= j2; j++) {
227  a(s2, j) = (a(s1, j) - a(s1, j - 1)) / ndu(pk + 1, rk + j);
228  d += a(s2, j) * ndu(rk + j, pk);
229  }
230 
231  if (r <= pk) {
232  a(s2, k) = -a(s1, k - 1) / ndu(pk + 1, r);
233  d += a(s2, k) * ndu(r, pk);
234  }
235 
236 
237  ders[k][r] = d;
238 
239  int temp = s1;
240  s1 = s2;
241  s2 = temp;
242  }
243  }
244 
245  double fac = static_cast<double>(deg);
246  for (int k = 1; k <= nDers; k++) {
247  for (int j = 0; j <= deg; j++) {
248  ders[k][j] *= fac;
249  }
250  fac *= static_cast<double>(deg - k);
251  }
252 }
const std::complex< Mdouble > i
Definition: ExtendedMath.h:50
double NurbsUtils::bsplineOneBasis ( int  i,
int  deg,
const std::vector< double > &  U,
double  u 
)

Compute a single B-spline basis function.

Parameters
[in]iThe ith basis function to compute.
[in]degDegree of the basis function.
[in]UKnot vector corresponding to the basis functions.
[in]uParameter to evaluate the basis functions at.
Returns
The value of the ith basis function at u.

Definition at line 84 of file NurbsUtils.cc.

References close().

85 {
86  int m = static_cast<int>(U.size()) - 1;
87  // Special case
88  if ((i == 0 && close(u, U[0])) || (i == m - deg - 1 && close(u, U[m])))
89  {
90  return 1.0;
91  }
92  // Local Property
93  if (u < U[i] || u >= U[i + deg + 1])
94  {
95  return 0.0;
96  }
97  // Initialize zeroth-degree functions
98  std::vector<double> N;
99  N.resize(deg + 1);
100  for (int j = 0; j <= deg; j++)
101  {
102  N[j] = (u >= U[i + j] && u < U[i + j + 1]) ? 1.0 : 0.0;
103  }
104  // Compute triangular table
105  for (int k = 1; k <= deg; k++)
106  {
107  double saved = (close(N[0], 0.0)) ? 0.0
108  : ((u - U[i]) * N[0]) / (U[i + k] - U[i]);
109  for (int j = 0; j < deg - k + 1; j++)
110  {
111  double Uleft = U[i + j + 1];
112  double Uright = U[i + j + k + 1];
113  if (close(N[j + 1], 0.0))
114  {
115  N[j] = saved;
116  saved = 0.0;
117  }
118  else
119  {
120  double temp = N[j + 1] / (Uright - Uleft);
121  N[j] = saved + (Uright - u) * temp;
122  saved = (u - Uleft) * temp;
123  }
124  }
125  }
126  return N[0];
127 }
const std::complex< Mdouble > i
Definition: ExtendedMath.h:50
bool close(double a, double b, double eps)
Definition: NurbsUtils.cc:38
bool NurbsUtils::close ( double  a,
double  b,
double  eps 
)

Definition at line 38 of file NurbsUtils.cc.

Referenced by bsplineOneBasis(), and findSpan().

39 {
40  return (std::abs(a - b) < eps) ? true : false;
41 }
int NurbsUtils::findSpan ( int  degree,
const std::vector< double > &  knots,
double  u 
)

Find the span of the given parameter in the knot vector.

Parameters
[in]degreeDegree of the curve.
[in]knotsKnot vector of the curve.
[in]uParameter value.
Returns
Span index into the knot vector such that (span - 1) < u <= span

Definition at line 43 of file NurbsUtils.cc.

References close().

Referenced by NurbsSurface::evaluate(), and NurbsSurface::evaluateDerivatives().

44 {
45  // index of last control point
46  int n = static_cast<int>(knots.size()) - degree - 2;
47 
48  // For u that is equal to last knot value
49  if (close(u, knots[n + 1]))
50  {
51  return n;
52  }
53 
54  // For values of u that lies outside the domain
55  if (u > knots[n + 1])
56  {
57  return n;
58  }
59  if (u < knots[degree])
60  {
61  return degree;
62  }
63 
64  // Binary search
65  // TODO: Replace this with std::lower_bound
66  int low = degree;
67  int high = n + 1;
68  int mid = (int) std::floor((low + high) / 2.0);
69  while (u < knots[mid] || u >= knots[mid + 1])
70  {
71  if (u < knots[mid])
72  {
73  high = mid;
74  }
75  else
76  {
77  low = mid;
78  }
79  mid = (low + high) / 2;
80  }
81  return mid;
82 }
bool close(double a, double b, double eps)
Definition: NurbsUtils.cc:38
bool NurbsUtils::isKnotVectorMonotonic ( const std::vector< double > &  knots)

Definition at line 33 of file NurbsUtils.cc.

Referenced by NurbsSurface::set().

34 {
35  return std::is_sorted(knots.begin(), knots.end());
36 }