BRL-CAD
nurb_knot.c
Go to the documentation of this file.
1 /* N U R B _ K N O T . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1990-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @addtogroup nurb */
21 /** @{ */
22 /** @file primitives/bspline/nurb_knot.c
23  *
24  * Various knot vector routines.
25  *
26  */
27 /** @} */
28 
29 #include "common.h"
30 
31 #include <math.h>
32 #include "bio.h"
33 
34 #include "vmath.h"
35 #include "raytrace.h"
36 #include "nurb.h"
37 
38 
39 /**
40  * rt_nurb_kvknot()
41  *
42  * Generate a open knot vector with n=order knots at the beginning of
43  * the sequence and n knots at the end of the sequence with a lower,
44  * and an upper value and num knots in between
45  */
46 void
47 rt_nurb_kvknot(register struct knot_vector *new_knots, int order, fastf_t lower, fastf_t upper, int num, struct resource *res)
48 {
49  register int i;
50  int total;
51  fastf_t knot_step;
52 
53  if (res) RT_CK_RESOURCE(res);
54 
55  total = order * 2 + num;
56 
57  knot_step = (upper - lower) / (num + 1);
58 
59  new_knots->k_size = total;
60 
61  new_knots->knots = (fastf_t *) bu_malloc (sizeof(fastf_t) * total,
62  "rt_nurb_kvknot: new knots values");
63 
64  for (i = 0; i < order; i++)
65  new_knots->knots[i] = lower;
66 
67  for (i = order; i <= (num + order - 1); i++)
68  new_knots->knots[i] = new_knots->knots[i-1] + knot_step;
69 
70  for (i = (num + order); i < total; i++)
71  new_knots->knots[i] = upper;
72 }
73 
74 
75 /**
76  * rt_nurb_kvmult()
77  *
78  * Construct a new knot vector which is the same as the passed in knot
79  * vector except it has multiplicity of num of val. It checks to see
80  * if val already is a multiple knot.
81  */
82 void
83 rt_nurb_kvmult(struct knot_vector *new_kv, const struct knot_vector *kv, int num, register fastf_t val, struct resource *res)
84 {
85  int n;
86  register int i;
87  struct knot_vector check;
88 
89  if (res) RT_CK_RESOURCE(res);
90 
91  n = rt_nurb_kvcheck(val, kv);
92 
93  check.k_size = num - n;
94  if (check.k_size <= 0) {
95  bu_log("rt_nurb_kvmult(new_kv=%p, kv=%p, num=%d, val=%g)\n",
96  (void *)new_kv, (void *)kv, num, val);
97  rt_nurb_pr_kv(kv);
98  bu_bomb("rt_nurb_kvmult\n");
99  }
100 
101  check.knots = (fastf_t *) bu_malloc(sizeof(fastf_t) * check.k_size,
102  "rt_nurb_kvmult: check knots");
103 
104  for (i = 0; i < num - n; i++)
105  check.knots[i] = val;
106 
107  rt_nurb_kvmerge(new_kv, &check, kv, res);
108 
109  /* free up old knot values */
110  bu_free((char *)check.knots, "rt_nurb_kvmult:check knots");
111 }
112 
113 
114 /**
115  * rt_nurb_kvgen()
116  *
117  * Generate a knot vector with num knots from lower value to the upper
118  * value.
119  */
120 void
121 rt_nurb_kvgen(register struct knot_vector *kv, fastf_t lower, fastf_t upper, int num, struct resource *res)
122 {
123  register int i;
124  register fastf_t inc;
125 
126  if (res) RT_CK_RESOURCE(res);
127 
128  inc = (upper - lower) / (num + 1);
129 
130  kv->k_size = num;
131 
132  kv->knots = (fastf_t *) bu_malloc (sizeof(fastf_t) * num,
133  "rt_nurb_kvgen: kv knots");
134 
135  for (i = 1; i <= num; i++)
136  kv->knots[i-1] = lower + i * inc;
137 }
138 
139 
140 /**
141  * rt_nurb_kvmerge()
142  *
143  * Merge two knot vectors together and return the new resulting knot
144  * vector.
145  */
146 void
147 rt_nurb_kvmerge(struct knot_vector *new_knots, const struct knot_vector *kv1, const struct knot_vector *kv2, struct resource *res)
148 {
149  int kv1_ptr = 0;
150  int kv2_ptr = 0;
151  int new_ptr;
152 
153  if (res) RT_CK_RESOURCE(res);
154 
155  new_knots->k_size = kv1->k_size + kv2->k_size;
156 
157  new_knots->knots = (fastf_t *) bu_malloc(
158  sizeof (fastf_t) * new_knots->k_size,
159  "rt_nurb_kvmerge: new knot values");
160 
161  for (new_ptr = 0; new_ptr < new_knots->k_size; new_ptr++) {
162  if (kv1_ptr >= kv1->k_size)
163  new_knots->knots[new_ptr] = kv2->knots[kv2_ptr++];
164  else if (kv2_ptr >= kv2->k_size)
165  new_knots->knots[new_ptr] = kv1->knots[kv1_ptr++];
166  else if (kv1->knots[kv1_ptr] < kv2->knots[kv2_ptr])
167  new_knots->knots[new_ptr] = kv1->knots[kv1_ptr++];
168  else
169  new_knots->knots[new_ptr] = kv2->knots[kv2_ptr++];
170  }
171 }
172 
173 
174 /**
175  * rt_nurb_kvcheck()
176  *
177  * Checks to see if the knot (val) exists in the Knot Vector and
178  * returns its multiplicity.
179  */
180 int
181 rt_nurb_kvcheck(fastf_t val, register const struct knot_vector *kv)
182 {
183  register int kv_num = 0;
184  register int i;
185 
186  for (i = 0; i < kv->k_size; i++) {
187  if (ZERO(val - kv->knots[i]))
188  kv_num++;
189  }
190 
191  return kv_num;
192 }
193 
194 
195 /**
196  * rt_nurb_kvextract()
197  *
198  * Extract the portion of the knot vector from kv->knots[lower] to
199  * kv->knots[upper]
200  */
201 void
202 rt_nurb_kvextract(struct knot_vector *new_kv, register const struct knot_vector *kv, int lower, int upper, struct resource *res)
203 {
204  register int i;
205  register fastf_t *ptr;
206 
207  if (res) RT_CK_RESOURCE(res);
208 
209  new_kv->knots = (fastf_t *) bu_malloc (
210  sizeof (fastf_t) * (upper - lower),
211  "spl_kvextract: nkw kv values");
212 
213  new_kv->k_size = upper - lower;
214  ptr = new_kv->knots;
215 
216  for (i = lower; i < upper; i++)
217  *ptr++ = kv->knots[i];
218 }
219 
220 
221 /**
222  * rt_nurb_kvcopy()
223  *
224  * Generic copy the knot vector and pass a new one in.
225  */
226 void
227 rt_nurb_kvcopy(struct knot_vector *new_kv, register const struct knot_vector *old_kv, struct resource *res)
228 {
229  register int i;
230 
231  if (res) RT_CK_RESOURCE(res);
232 
233  new_kv->k_size = old_kv->k_size;
234 
235  new_kv->knots = (fastf_t *) bu_malloc(sizeof(fastf_t) *
236  new_kv->k_size, "spl_kvcopy: new knot values");
237 
238  for (i = 0; i < new_kv->k_size; i++)
239  new_kv->knots[i] = old_kv->knots[i];
240 }
241 
242 
243 /**
244  * rt_nurb_kvnorm()
245  *
246  * Normalize the knot vector so its values are from zero to one.
247  *
248  * XXX Need to check to see if the lower value is zero
249  */
250 void
251 rt_nurb_kvnorm(register struct knot_vector *kv)
252 {
253  register fastf_t upper;
254  register int i;
255 
256  upper = kv->knots[kv->k_size - 1];
257  if (ZERO(upper))
258  upper = 0;
259  else
260  upper = 1 / upper;
261 
262  for (i = 0; i < kv->k_size; i++)
263  kv->knots[i] *= upper;
264 }
265 
266 
267 /**
268  * knot_index()
269  *
270  * Calculates and returns the index of the value for the knot vector
271  *
272  * XXX It is hard to know what tolerance to use here for the comparisons.
273  */
274 int
275 rt_nurb_knot_index(const struct knot_vector *kv, fastf_t k_value, int order)
276 {
277  int i;
278  fastf_t knt;
279  int k_index;
280 
281  if (k_value < (knt = *(kv->knots + order - 1))) {
282  if (fabs(k_value - knt) < 0.0001) {
283  k_value = knt;
284  } else
285  return - 1;
286  }
287 
288  if (k_value > (knt = *(kv->knots + kv->k_size - order + 1))) {
289  if (fabs(k_value - knt) < 0.0001) {
290  k_value = knt;
291  } else
292  return - 1;
293  }
294 
295  if (ZERO(k_value - kv->knots[ kv->k_size - order + 1]))
296  k_index = kv->k_size - order - 1;
297  else if (ZERO(k_value - kv->knots[ order - 1]))
298  k_index = order - 1;
299  else {
300  k_index = 0;
301  for (i = 0; i < kv->k_size - 1; i++)
302  if (kv->knots[i] < k_value && k_value <= kv->knots[i+1])
303  k_index = i;
304 
305  }
306 
307  return k_index;
308 }
309 
310 
311 /**
312  * rt_nurb_gen_knot_vector()
313  *
314  * Generate a open knot vector with n=order knots at the beginning of
315  * the sequence and n knots at the end of the sequence.
316  */
317 void
318 rt_nurb_gen_knot_vector(register struct knot_vector *new_knots, int order, fastf_t lower, fastf_t upper, struct resource *res)
319 {
320  register int i;
321  int total;
322 
323  if (res) RT_CK_RESOURCE(res);
324 
325  total = order * 2;
326 
327  new_knots->k_size = total;
328 
329  new_knots->knots = (fastf_t *) bu_malloc (sizeof(fastf_t) * total,
330  "rt_nurb_gen_knot_vector: new knots values");
331 
332  for (i = 0; i < order; i++)
333  new_knots->knots[i] = lower;
334 
335  for (i = order; i < total; i++)
336  new_knots->knots[i] = upper;
337 }
338 
339 
340 /*
341  * Local Variables:
342  * mode: C
343  * tab-width: 8
344  * indent-tabs-mode: t
345  * c-file-style: "stroustrup"
346  * End:
347  * ex: shiftwidth=4 tabstop=8
348  */
Definition: db_flip.c:35
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
int rt_nurb_knot_index(const struct knot_vector *kv, fastf_t k_value, int order)
Definition: nurb_knot.c:275
Header file for the BRL-CAD common definitions.
int rt_nurb_kvcheck(fastf_t val, register const struct knot_vector *kv)
Definition: nurb_knot.c:181
void rt_nurb_kvmult(struct knot_vector *new_kv, const struct knot_vector *kv, int num, register fastf_t val, struct resource *res)
Definition: nurb_knot.c:83
void rt_nurb_gen_knot_vector(register struct knot_vector *new_knots, int order, fastf_t lower, fastf_t upper, struct resource *res)
Definition: nurb_knot.c:318
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
void rt_nurb_kvmerge(struct knot_vector *new_knots, const struct knot_vector *kv1, const struct knot_vector *kv2, struct resource *res)
Definition: nurb_knot.c:147
void rt_nurb_kvnorm(register struct knot_vector *kv)
Definition: nurb_knot.c:251
#define ZERO(val)
Definition: units.c:38
#define RT_CK_RESOURCE(_p)
Definition: raytrace.h:1490
void rt_nurb_pr_kv(const struct knot_vector *kv)
Definition: nurb_util.c:235
void rt_nurb_kvgen(register struct knot_vector *kv, fastf_t lower, fastf_t upper, int num, struct resource *res)
Definition: nurb_knot.c:121
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
void rt_nurb_kvcopy(struct knot_vector *new_kv, register const struct knot_vector *old_kv, struct resource *res)
Definition: nurb_knot.c:227
void rt_nurb_kvextract(struct knot_vector *new_kv, register const struct knot_vector *kv, int lower, int upper, struct resource *res)
Definition: nurb_knot.c:202
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
double fastf_t
Definition: defines.h:300
void rt_nurb_kvknot(register struct knot_vector *new_knots, int order, fastf_t lower, fastf_t upper, int num, struct resource *res)
Definition: nurb_knot.c:47