BRL-CAD
nurb_split.c
Go to the documentation of this file.
1 /* N U R B _ S P L I 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_split.c
23  *
24  * Subdivide a nurb surface by inserting a multiple knot of of the
25  * surface order in a given direction and return the resulting
26  * surfaces.
27  *
28  */
29 /** @} */
30 
31 #include "common.h"
32 
33 #include "bio.h"
34 
35 #include "vmath.h"
36 #include "nmg.h"
37 #include "raytrace.h"
38 #include "nurb.h"
39 
40 
41 /**
42  * Algorithm
43  *
44  * Given a parametric direction (u or v) look at the direction knot
45  * vector and insert a multiple knot of parametric direction surface
46  * order. If internal knot values exist than pick the one closest to
47  * the middle and add additional knots to split at that value,
48  * otherwise add multiple knots at the mid point of the knot
49  * vector. Use the new knot vector to pass to the oslo refinement
50  * process and split the surface. Separate the surface and return the
51  * two resulting surface.
52  *
53  * The original surface is undisturbed by this operation.
54  */
55 void
56 rt_nurb_s_split(struct bu_list *split_hd, const struct face_g_snurb *srf, int dir, struct resource *res)
57 {
58  struct knot_vector new_kv;
59  fastf_t value;
60  struct oslo_mat * oslo;
61  int i;
62  int k_index = 0;
63  struct face_g_snurb * srf1, * srf2;
64 
65  NMG_CK_SNURB(srf);
66 
67  if (dir == RT_NURB_SPLIT_ROW) {
68  value = srf->u.knots[(srf->u.k_size -1)/2];
69 
70  for (i = 0; i < srf->u.k_size; i++)
71  if (ZERO(value - srf->u.knots[i])) {
72  k_index = i;
73  break;
74  }
75  if (k_index == 0) {
76  value = (value +
77  srf->u.knots[ srf->u.k_size -1])
78  /2.0;
79  k_index = srf->order[0];
80  }
81 
82  rt_nurb_kvmult(&new_kv, &srf->u, srf->order[0], value, res);
83 
84  oslo = (struct oslo_mat *)
85  rt_nurb_calc_oslo(srf->order[RT_NURB_SPLIT_ROW], &srf->u, &new_kv, res);
86 
87  GET_SNURB(srf1);
88  srf1->order[0] = srf->order[0];
89  srf1->order[1] = srf->order[1];
90  srf1->dir = RT_NURB_SPLIT_ROW;
91  rt_nurb_kvextract(&srf1->u, &new_kv, 0, k_index + srf1->order[0], res);
92  rt_nurb_kvcopy(&srf1->v, &srf->v, res);
93 
94  srf1->pt_type = srf->pt_type;
95  srf1->s_size[0] = srf1->v.k_size -
96  srf1->order[1];
97  srf1->s_size[1] = srf1->u.k_size -
98  srf1->order[0];
99 
100  srf1->ctl_points = (fastf_t *)
101  bu_malloc(sizeof(fastf_t) * srf1->s_size[0] *
102  srf1->s_size[1] *
103  RT_NURB_EXTRACT_COORDS(srf1->pt_type),
104  "rt_nurb_s_split: srf1 row mesh control points");
105 
106  GET_SNURB(srf2);
107  srf2->order[0] = srf->order[0];
108  srf2->order[1] = srf->order[1];
109  srf2->dir = RT_NURB_SPLIT_ROW;
110  rt_nurb_kvextract(&srf2->u, &new_kv, k_index, new_kv.k_size, res);
111  rt_nurb_kvcopy(&srf2->v, &srf->v, res);
112 
113  srf2->pt_type = srf->pt_type;
114  srf2->s_size[0] = srf2->v.k_size -
115  srf2->order[1];
116  srf2->s_size[1] = srf2->u.k_size -
117  srf2->order[0];
118 
119  srf2->ctl_points = (fastf_t *)
120  bu_malloc(sizeof(fastf_t) * srf2->s_size[0] *
121  srf2->s_size[1] *
122  RT_NURB_EXTRACT_COORDS(srf2->pt_type),
123  "rt_nurb_s_split: srf2 row mesh control points");
124 
125  for (i = 0; i < srf->s_size[0]; i++) {
126  fastf_t * old_mesh_ptr;
127  fastf_t * new_mesh_ptr;
128 
129  old_mesh_ptr = &srf->ctl_points[
130  i * srf->s_size[1] *
131  RT_NURB_EXTRACT_COORDS(srf->pt_type)];
132  new_mesh_ptr = &srf1->ctl_points[
133  i * srf1->s_size[1] *
134  RT_NURB_EXTRACT_COORDS(srf1->pt_type)];
135  rt_nurb_map_oslo(oslo, old_mesh_ptr, new_mesh_ptr,
136  RT_NURB_EXTRACT_COORDS(srf->pt_type),
137  RT_NURB_EXTRACT_COORDS(srf1->pt_type),
138  0, k_index, srf1->pt_type);
139  new_mesh_ptr = &srf2->ctl_points[
140  i * srf2->s_size[1] *
141  RT_NURB_EXTRACT_COORDS(srf2->pt_type)];
142  rt_nurb_map_oslo(oslo, old_mesh_ptr, new_mesh_ptr,
143  RT_NURB_EXTRACT_COORDS(srf->pt_type),
144  RT_NURB_EXTRACT_COORDS(srf2->pt_type),
145  k_index, new_kv.k_size - srf2->order[0],
146  srf2->pt_type);
147  }
148  } else {
149  value = srf->v.knots[(srf->v.k_size -1)/2];
150 
151  for (i = 0; i < srf->v.k_size; i++)
152  if (ZERO(value - srf->v.knots[i])) {
153  k_index = i;
154  break;
155  }
156  if (k_index == 0) {
157  value = (value +
158  srf->v.knots[ srf->v.k_size -1])
159  /2.0;
160  k_index = srf->order[1];
161  }
162 
163  rt_nurb_kvmult(&new_kv, &srf->v, srf->order[RT_NURB_SPLIT_COL], value, res);
164 
165  oslo = (struct oslo_mat *)
166  rt_nurb_calc_oslo(srf->order[RT_NURB_SPLIT_COL], &srf->v, &new_kv, res);
167 
168  GET_SNURB(srf1);
169  srf1->order[0] = srf->order[0];
170  srf1->order[1] = srf->order[1];
171  srf1->dir = RT_NURB_SPLIT_COL;
172  rt_nurb_kvextract(&srf1->v, &new_kv, 0, k_index + srf1->order[RT_NURB_SPLIT_COL], res);
173  rt_nurb_kvcopy(&srf1->u, &srf->u, res);
174 
175  srf1->pt_type = srf->pt_type;
176  srf1->s_size[0] = srf1->v.k_size -
177  srf1->order[1];
178  srf1->s_size[1] = srf1->u.k_size -
179  srf1->order[0];
180 
181  srf1->ctl_points = (fastf_t *)
182  bu_malloc(sizeof(fastf_t) * srf1->s_size[0] *
183  srf1->s_size[1] *
184  RT_NURB_EXTRACT_COORDS(srf1->pt_type),
185  "rt_nurb_s_split: srf1 col mesh control points");
186 
187  GET_SNURB(srf2);
188  srf2->order[0] = srf->order[0];
189  srf2->order[1] = srf->order[1];
190  srf2->dir = RT_NURB_SPLIT_COL;
191  rt_nurb_kvextract(&srf2->v, &new_kv, k_index, new_kv.k_size, res);
192  rt_nurb_kvcopy(&srf2->u, &srf->u, res);
193 
194  srf2->pt_type = srf->pt_type;
195  srf2->s_size[0] = srf2->v.k_size -
196  srf2->order[1];
197  srf2->s_size[1] = srf2->u.k_size -
198  srf2->order[0];
199 
200  srf2->ctl_points = (fastf_t *)
201  bu_malloc(sizeof(fastf_t) * srf2->s_size[0] *
202  srf2->s_size[1] *
203  RT_NURB_EXTRACT_COORDS(srf2->pt_type),
204  "rt_nurb_s_split: srf2 col mesh control points");
205 
206  for (i = 0; i < srf->s_size[1]; i++) {
207  fastf_t * old_mesh_ptr;
208  fastf_t * new_mesh_ptr;
209 
210  old_mesh_ptr = &srf->ctl_points[
211  i * RT_NURB_EXTRACT_COORDS(srf->pt_type)];
212  new_mesh_ptr = &srf1->ctl_points[
213  i * RT_NURB_EXTRACT_COORDS(srf1->pt_type)];
214  rt_nurb_map_oslo(oslo, old_mesh_ptr, new_mesh_ptr,
215  srf->s_size[1] *
216  RT_NURB_EXTRACT_COORDS(srf->pt_type),
217  srf1->s_size[1] *
218  RT_NURB_EXTRACT_COORDS(srf1->pt_type),
219  0, k_index, srf1->pt_type);
220  new_mesh_ptr = &srf2->ctl_points[
221  i * RT_NURB_EXTRACT_COORDS(srf2->pt_type)];
222  rt_nurb_map_oslo(oslo, old_mesh_ptr, new_mesh_ptr,
223  srf->s_size[1] *
224  RT_NURB_EXTRACT_COORDS(srf->pt_type),
225  srf2->s_size[1] *
226  RT_NURB_EXTRACT_COORDS(srf2->pt_type),
227  k_index, new_kv.k_size - srf2->order[1],
228  srf2->pt_type);
229  }
230  }
231 
232  /* Arrangement will be: head, srf1, srf2 */
233  BU_LIST_APPEND(split_hd, &srf2->l);
234  BU_LIST_APPEND(split_hd, &srf1->l);
235 
236  rt_nurb_free_oslo(oslo, res);
237  bu_free((char *)new_kv.knots, "rt_nurb_s_split: new kv knots");
238 
239 }
240 
241 
242 /**
243  * Split a NURB curve by inserting a multiple knot and return the
244  * result of the two curves.
245  *
246  * Algorithm
247  *
248  * Insert a multiple knot of the curve order. If internal knot values
249  * exist than pick the one closest to the middle and add additional
250  * knots to split at that value, otherwise add multiple knots at the
251  * mid point of the knot vector. Use the new knot vector to pass to
252  * the oslo refinement process and split the curve. Separate the
253  * curve and return the two resulting curves.
254  *
255  * The original curve is undisturbed by this operation.
256  */
257 void
258 rt_nurb_c_split(struct bu_list *split_hd, const struct edge_g_cnurb *crv)
259 {
260  struct knot_vector new_kv;
261  fastf_t value;
262  struct oslo_mat * oslo;
263  int i;
264  int k_index = 0;
265  struct edge_g_cnurb * crv1, * crv2;
266  int coords;
267 
268  NMG_CK_CNURB(crv);
269 
270  coords = RT_NURB_EXTRACT_COORDS(crv->pt_type),
271 
272  value = crv->k.knots[(crv->k.k_size -1)/2];
273 
274  for (i = 0; i < crv->k.k_size; i++)
275  if (ZERO(value - crv->k.knots[i])) {
276  k_index = i;
277  break;
278  }
279  if (k_index == 0) {
280  value = (value +
281  crv->k.knots[ crv->k.k_size -1])
282  /2.0;
283  k_index = crv->order;
284  }
285 
286  rt_nurb_kvmult(&new_kv, &crv->k, crv->order, value, (struct resource *)NULL);
287 
288  oslo = (struct oslo_mat *)
289  rt_nurb_calc_oslo(crv->order, &crv->k, &new_kv, (struct resource *)NULL);
290 
291  GET_CNURB(crv1);
292  crv1->order = crv->order;
293  rt_nurb_kvextract(&crv1->k, &new_kv, 0, k_index + crv->order, (struct resource *)NULL);
294  crv1->pt_type = crv->pt_type;
295  crv1->c_size = crv1->k.k_size - crv1->order;
296  crv1->ctl_points = (fastf_t *)
297  bu_malloc(sizeof(fastf_t) * crv1->c_size *
298  RT_NURB_EXTRACT_COORDS(crv1->pt_type),
299  "rt_nurb_c_split: crv1 control points");
300 
301  GET_CNURB(crv2);
302  crv2->order = crv->order;
303  rt_nurb_kvextract(&crv2->k, &new_kv, k_index, new_kv.k_size, (struct resource *)NULL);
304  crv2->pt_type = crv->pt_type;
305  crv2->c_size = crv2->k.k_size - crv2->order;
306  crv2->ctl_points = (fastf_t *)
307  bu_malloc(sizeof(fastf_t) * crv2->c_size *
308  RT_NURB_EXTRACT_COORDS(crv2->pt_type),
309  "rt_nurb_s_split: crv2 mesh control points");
310 
311  rt_nurb_map_oslo(oslo, crv->ctl_points, crv1->ctl_points,
312  coords, coords, 0, k_index, crv->pt_type);
313 
314  rt_nurb_map_oslo(oslo, crv->ctl_points, crv2->ctl_points,
315  coords, coords, k_index, new_kv.k_size - crv2->order,
316  crv2->pt_type);
317 
318  rt_nurb_free_oslo(oslo, (struct resource *)NULL);
319 
320  bu_free((char *) new_kv.knots, "rt_nurb_c_split; new_kv.knots");
321 
322  /* Arrangement will be: head, crv1, crv2 */
323  BU_LIST_APPEND(split_hd, &crv2->l);
324  BU_LIST_APPEND(split_hd, &crv1->l);
325 }
326 
327 
328 /*
329  * Local Variables:
330  * mode: C
331  * tab-width: 8
332  * indent-tabs-mode: t
333  * c-file-style: "stroustrup"
334  * End:
335  * ex: shiftwidth=4 tabstop=8
336  */
Definition: list.h:118
void rt_nurb_map_oslo(struct oslo_mat *oslo, fastf_t *old_pts, fastf_t *new_pts, int o_stride, int n_stride, int lower, int upper, int pt_type)
Definition: oslo_map.c:45
Header file for the BRL-CAD common definitions.
#define BU_LIST_APPEND(old, new)
Definition: list.h:197
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 * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
void rt_nurb_free_oslo(struct oslo_mat *om, struct resource *res)
Definition: oslo_calc.c:214
void rt_nurb_c_split(struct bu_list *split_hd, const struct edge_g_cnurb *crv)
Definition: nurb_split.c:258
#define ZERO(val)
Definition: units.c:38
void rt_nurb_s_split(struct bu_list *split_hd, const struct face_g_snurb *srf, int dir, struct resource *res)
Definition: nurb_split.c:56
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
double fastf_t
Definition: defines.h:300
struct oslo_mat * rt_nurb_calc_oslo(register int order, register const struct knot_vector *tau_kv, register struct knot_vector *t_kv, struct resource *res)
Definition: oslo_calc.c:51