1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 *
16 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17 * All rights reserved.
18 */
19
20 /** \file
21 * \ingroup bke
22 */
23
24 #include <math.h> /* floor */
25 #include <stdlib.h>
26 #include <string.h>
27
28 #include "MEM_guardedalloc.h"
29
30 #include "BLI_blenlib.h"
31 #include "BLI_endian_switch.h"
32 #include "BLI_ghash.h"
33 #include "BLI_math.h"
34 #include "BLI_utildefines.h"
35
36 #include "BLT_translation.h"
37
38 /* Allow using deprecated functionality for .blend file I/O. */
39 #define DNA_DEPRECATED_ALLOW
40
41 #include "DNA_anim_types.h"
42 #include "DNA_curve_types.h"
43 #include "DNA_defaults.h"
44 #include "DNA_material_types.h"
45
46 /* for dereferencing pointers */
47 #include "DNA_key_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_vfont_types.h"
50
51 #include "BKE_anim_data.h"
52 #include "BKE_curve.h"
53 #include "BKE_curveprofile.h"
54 #include "BKE_displist.h"
55 #include "BKE_font.h"
56 #include "BKE_idtype.h"
57 #include "BKE_key.h"
58 #include "BKE_lib_id.h"
59 #include "BKE_lib_query.h"
60 #include "BKE_main.h"
61 #include "BKE_object.h"
62
63 #include "DEG_depsgraph.h"
64 #include "DEG_depsgraph_query.h"
65
66 #include "CLG_log.h"
67
68 #include "BLO_read_write.h"
69
70 /* globals */
71
72 /* local */
73 static CLG_LogRef LOG = {"bke.curve"};
74
curve_init_data(ID * id)75 static void curve_init_data(ID *id)
76 {
77 Curve *curve = (Curve *)id;
78
79 BLI_assert(MEMCMP_STRUCT_AFTER_IS_ZERO(curve, id));
80
81 MEMCPY_STRUCT_AFTER(curve, DNA_struct_default_get(Curve), id);
82 }
83
curve_copy_data(Main * bmain,ID * id_dst,const ID * id_src,const int flag)84 static void curve_copy_data(Main *bmain, ID *id_dst, const ID *id_src, const int flag)
85 {
86 Curve *curve_dst = (Curve *)id_dst;
87 const Curve *curve_src = (const Curve *)id_src;
88
89 BLI_listbase_clear(&curve_dst->nurb);
90 BKE_nurbList_duplicate(&(curve_dst->nurb), &(curve_src->nurb));
91
92 curve_dst->mat = MEM_dupallocN(curve_src->mat);
93
94 curve_dst->str = MEM_dupallocN(curve_src->str);
95 curve_dst->strinfo = MEM_dupallocN(curve_src->strinfo);
96 curve_dst->tb = MEM_dupallocN(curve_src->tb);
97 curve_dst->batch_cache = NULL;
98
99 curve_dst->bevel_profile = BKE_curveprofile_copy(curve_src->bevel_profile);
100
101 if (curve_src->key && (flag & LIB_ID_COPY_SHAPEKEY)) {
102 BKE_id_copy_ex(bmain, &curve_src->key->id, (ID **)&curve_dst->key, flag);
103 /* XXX This is not nice, we need to make BKE_id_copy_ex fully re-entrant... */
104 curve_dst->key->from = &curve_dst->id;
105 }
106
107 curve_dst->editnurb = NULL;
108 curve_dst->editfont = NULL;
109 }
110
curve_free_data(ID * id)111 static void curve_free_data(ID *id)
112 {
113 Curve *curve = (Curve *)id;
114
115 BKE_curve_batch_cache_free(curve);
116
117 BKE_nurbList_free(&curve->nurb);
118 BKE_curve_editfont_free(curve);
119
120 BKE_curve_editNurb_free(curve);
121
122 BKE_curveprofile_free(curve->bevel_profile);
123
124 MEM_SAFE_FREE(curve->mat);
125 MEM_SAFE_FREE(curve->str);
126 MEM_SAFE_FREE(curve->strinfo);
127 MEM_SAFE_FREE(curve->tb);
128 }
129
curve_foreach_id(ID * id,LibraryForeachIDData * data)130 static void curve_foreach_id(ID *id, LibraryForeachIDData *data)
131 {
132 Curve *curve = (Curve *)id;
133 BKE_LIB_FOREACHID_PROCESS(data, curve->bevobj, IDWALK_CB_NOP);
134 BKE_LIB_FOREACHID_PROCESS(data, curve->taperobj, IDWALK_CB_NOP);
135 BKE_LIB_FOREACHID_PROCESS(data, curve->textoncurve, IDWALK_CB_NOP);
136 BKE_LIB_FOREACHID_PROCESS(data, curve->key, IDWALK_CB_USER);
137 for (int i = 0; i < curve->totcol; i++) {
138 BKE_LIB_FOREACHID_PROCESS(data, curve->mat[i], IDWALK_CB_USER);
139 }
140 BKE_LIB_FOREACHID_PROCESS(data, curve->vfont, IDWALK_CB_USER);
141 BKE_LIB_FOREACHID_PROCESS(data, curve->vfontb, IDWALK_CB_USER);
142 BKE_LIB_FOREACHID_PROCESS(data, curve->vfonti, IDWALK_CB_USER);
143 BKE_LIB_FOREACHID_PROCESS(data, curve->vfontbi, IDWALK_CB_USER);
144 }
145
curve_blend_write(BlendWriter * writer,ID * id,const void * id_address)146 static void curve_blend_write(BlendWriter *writer, ID *id, const void *id_address)
147 {
148 Curve *cu = (Curve *)id;
149 if (cu->id.us > 0 || BLO_write_is_undo(writer)) {
150 /* Clean up, important in undo case to reduce false detection of changed datablocks. */
151 cu->editnurb = NULL;
152 cu->editfont = NULL;
153 cu->batch_cache = NULL;
154
155 /* write LibData */
156 BLO_write_id_struct(writer, Curve, id_address, &cu->id);
157 BKE_id_blend_write(writer, &cu->id);
158
159 /* direct data */
160 BLO_write_pointer_array(writer, cu->totcol, cu->mat);
161 if (cu->adt) {
162 BKE_animdata_blend_write(writer, cu->adt);
163 }
164
165 if (cu->vfont) {
166 BLO_write_raw(writer, cu->len + 1, cu->str);
167 BLO_write_struct_array(writer, CharInfo, cu->len_char32 + 1, cu->strinfo);
168 BLO_write_struct_array(writer, TextBox, cu->totbox, cu->tb);
169 }
170 else {
171 /* is also the order of reading */
172 LISTBASE_FOREACH (Nurb *, nu, &cu->nurb) {
173 BLO_write_struct(writer, Nurb, nu);
174 }
175 LISTBASE_FOREACH (Nurb *, nu, &cu->nurb) {
176 if (nu->type == CU_BEZIER) {
177 BLO_write_struct_array(writer, BezTriple, nu->pntsu, nu->bezt);
178 }
179 else {
180 BLO_write_struct_array(writer, BPoint, nu->pntsu * nu->pntsv, nu->bp);
181 if (nu->knotsu) {
182 BLO_write_float_array(writer, KNOTSU(nu), nu->knotsu);
183 }
184 if (nu->knotsv) {
185 BLO_write_float_array(writer, KNOTSV(nu), nu->knotsv);
186 }
187 }
188 }
189 }
190
191 if (cu->bevel_profile != NULL) {
192 BKE_curveprofile_blend_write(writer, cu->bevel_profile);
193 }
194 }
195 }
196
switch_endian_knots(Nurb * nu)197 static void switch_endian_knots(Nurb *nu)
198 {
199 if (nu->knotsu) {
200 BLI_endian_switch_float_array(nu->knotsu, KNOTSU(nu));
201 }
202 if (nu->knotsv) {
203 BLI_endian_switch_float_array(nu->knotsv, KNOTSV(nu));
204 }
205 }
206
curve_blend_read_data(BlendDataReader * reader,ID * id)207 static void curve_blend_read_data(BlendDataReader *reader, ID *id)
208 {
209 Curve *cu = (Curve *)id;
210 BLO_read_data_address(reader, &cu->adt);
211 BKE_animdata_blend_read_data(reader, cu->adt);
212
213 /* Protect against integer overflow vulnerability. */
214 CLAMP(cu->len_char32, 0, INT_MAX - 4);
215
216 BLO_read_pointer_array(reader, (void **)&cu->mat);
217
218 BLO_read_data_address(reader, &cu->str);
219 BLO_read_data_address(reader, &cu->strinfo);
220 BLO_read_data_address(reader, &cu->tb);
221
222 if (cu->vfont == NULL) {
223 BLO_read_list(reader, &(cu->nurb));
224 }
225 else {
226 cu->nurb.first = cu->nurb.last = NULL;
227
228 TextBox *tb = MEM_calloc_arrayN(MAXTEXTBOX, sizeof(TextBox), "TextBoxread");
229 if (cu->tb) {
230 memcpy(tb, cu->tb, cu->totbox * sizeof(TextBox));
231 MEM_freeN(cu->tb);
232 cu->tb = tb;
233 }
234 else {
235 cu->totbox = 1;
236 cu->actbox = 1;
237 cu->tb = tb;
238 cu->tb[0].w = cu->linewidth;
239 }
240 if (cu->wordspace == 0.0f) {
241 cu->wordspace = 1.0f;
242 }
243 }
244
245 cu->editnurb = NULL;
246 cu->editfont = NULL;
247 cu->batch_cache = NULL;
248
249 LISTBASE_FOREACH (Nurb *, nu, &cu->nurb) {
250 BLO_read_data_address(reader, &nu->bezt);
251 BLO_read_data_address(reader, &nu->bp);
252 BLO_read_data_address(reader, &nu->knotsu);
253 BLO_read_data_address(reader, &nu->knotsv);
254 if (cu->vfont == NULL) {
255 nu->charidx = 0;
256 }
257
258 if (BLO_read_requires_endian_switch(reader)) {
259 switch_endian_knots(nu);
260 }
261 }
262 cu->texflag &= ~CU_AUTOSPACE_EVALUATED;
263
264 BLO_read_data_address(reader, &cu->bevel_profile);
265 if (cu->bevel_profile != NULL) {
266 BKE_curveprofile_blend_read(reader, cu->bevel_profile);
267 }
268 }
269
curve_blend_read_lib(BlendLibReader * reader,ID * id)270 static void curve_blend_read_lib(BlendLibReader *reader, ID *id)
271 {
272 Curve *cu = (Curve *)id;
273 for (int a = 0; a < cu->totcol; a++) {
274 BLO_read_id_address(reader, cu->id.lib, &cu->mat[a]);
275 }
276
277 BLO_read_id_address(reader, cu->id.lib, &cu->bevobj);
278 BLO_read_id_address(reader, cu->id.lib, &cu->taperobj);
279 BLO_read_id_address(reader, cu->id.lib, &cu->textoncurve);
280 BLO_read_id_address(reader, cu->id.lib, &cu->vfont);
281 BLO_read_id_address(reader, cu->id.lib, &cu->vfontb);
282 BLO_read_id_address(reader, cu->id.lib, &cu->vfonti);
283 BLO_read_id_address(reader, cu->id.lib, &cu->vfontbi);
284
285 BLO_read_id_address(reader, cu->id.lib, &cu->ipo); /* XXX deprecated - old animation system */
286 BLO_read_id_address(reader, cu->id.lib, &cu->key);
287 }
288
curve_blend_read_expand(BlendExpander * expander,ID * id)289 static void curve_blend_read_expand(BlendExpander *expander, ID *id)
290 {
291 Curve *cu = (Curve *)id;
292 for (int a = 0; a < cu->totcol; a++) {
293 BLO_expand(expander, cu->mat[a]);
294 }
295
296 BLO_expand(expander, cu->vfont);
297 BLO_expand(expander, cu->vfontb);
298 BLO_expand(expander, cu->vfonti);
299 BLO_expand(expander, cu->vfontbi);
300 BLO_expand(expander, cu->key);
301 BLO_expand(expander, cu->ipo); /* XXX deprecated - old animation system */
302 BLO_expand(expander, cu->bevobj);
303 BLO_expand(expander, cu->taperobj);
304 BLO_expand(expander, cu->textoncurve);
305 }
306
307 IDTypeInfo IDType_ID_CU = {
308 .id_code = ID_CU,
309 .id_filter = FILTER_ID_CU,
310 .main_listbase_index = INDEX_ID_CU,
311 .struct_size = sizeof(Curve),
312 .name = "Curve",
313 .name_plural = "curves",
314 .translation_context = BLT_I18NCONTEXT_ID_CURVE,
315 .flags = 0,
316
317 .init_data = curve_init_data,
318 .copy_data = curve_copy_data,
319 .free_data = curve_free_data,
320 .make_local = NULL,
321 .foreach_id = curve_foreach_id,
322 .foreach_cache = NULL,
323
324 .blend_write = curve_blend_write,
325 .blend_read_data = curve_blend_read_data,
326 .blend_read_lib = curve_blend_read_lib,
327 .blend_read_expand = curve_blend_read_expand,
328 };
329
330 static int cu_isectLL(const float v1[3],
331 const float v2[3],
332 const float v3[3],
333 const float v4[3],
334 short cox,
335 short coy,
336 float *lambda,
337 float *mu,
338 float vec[3]);
339
340 /* frees editcurve entirely */
BKE_curve_editfont_free(Curve * cu)341 void BKE_curve_editfont_free(Curve *cu)
342 {
343 if (cu->editfont) {
344 EditFont *ef = cu->editfont;
345
346 if (ef->textbuf) {
347 MEM_freeN(ef->textbuf);
348 }
349 if (ef->textbufinfo) {
350 MEM_freeN(ef->textbufinfo);
351 }
352 if (ef->selboxes) {
353 MEM_freeN(ef->selboxes);
354 }
355
356 MEM_freeN(ef);
357 cu->editfont = NULL;
358 }
359 }
360
curve_editNurb_keyIndex_cv_free_cb(void * val)361 static void curve_editNurb_keyIndex_cv_free_cb(void *val)
362 {
363 CVKeyIndex *index = val;
364 MEM_freeN(index->orig_cv);
365 MEM_freeN(val);
366 }
367
BKE_curve_editNurb_keyIndex_delCV(GHash * keyindex,const void * cv)368 void BKE_curve_editNurb_keyIndex_delCV(GHash *keyindex, const void *cv)
369 {
370 BLI_assert(keyindex != NULL);
371 BLI_ghash_remove(keyindex, cv, NULL, curve_editNurb_keyIndex_cv_free_cb);
372 }
373
BKE_curve_editNurb_keyIndex_free(GHash ** keyindex)374 void BKE_curve_editNurb_keyIndex_free(GHash **keyindex)
375 {
376 if (!(*keyindex)) {
377 return;
378 }
379 BLI_ghash_free(*keyindex, NULL, curve_editNurb_keyIndex_cv_free_cb);
380 *keyindex = NULL;
381 }
382
BKE_curve_editNurb_free(Curve * cu)383 void BKE_curve_editNurb_free(Curve *cu)
384 {
385 if (cu->editnurb) {
386 BKE_nurbList_free(&cu->editnurb->nurbs);
387 BKE_curve_editNurb_keyIndex_free(&cu->editnurb->keyindex);
388 MEM_freeN(cu->editnurb);
389 cu->editnurb = NULL;
390 }
391 }
392
BKE_curve_init(Curve * cu,const short curve_type)393 void BKE_curve_init(Curve *cu, const short curve_type)
394 {
395 curve_init_data(&cu->id);
396
397 cu->type = curve_type;
398
399 if (cu->type == OB_FONT) {
400 cu->flag |= CU_FRONT | CU_BACK;
401 cu->vfont = cu->vfontb = cu->vfonti = cu->vfontbi = BKE_vfont_builtin_get();
402 cu->vfont->id.us += 4;
403 cu->str = MEM_malloc_arrayN(12, sizeof(unsigned char), "str");
404 BLI_strncpy(cu->str, "Text", 12);
405 cu->len = cu->len_char32 = cu->pos = 4;
406 cu->strinfo = MEM_calloc_arrayN(12, sizeof(CharInfo), "strinfo new");
407 cu->totbox = cu->actbox = 1;
408 cu->tb = MEM_calloc_arrayN(MAXTEXTBOX, sizeof(TextBox), "textbox");
409 cu->tb[0].w = cu->tb[0].h = 0.0;
410 }
411 else if (cu->type == OB_SURF) {
412 cu->resolv = 4;
413 }
414 cu->bevel_profile = NULL;
415 }
416
BKE_curve_add(Main * bmain,const char * name,int type)417 Curve *BKE_curve_add(Main *bmain, const char *name, int type)
418 {
419 Curve *cu;
420
421 /* We cannot use #BKE_id_new here as we need some custom initialization code. */
422 cu = BKE_libblock_alloc(bmain, ID_CU, name, 0);
423
424 BKE_curve_init(cu, type);
425
426 return cu;
427 }
428
429 /* Get list of nurbs from editnurbs structure */
BKE_curve_editNurbs_get(Curve * cu)430 ListBase *BKE_curve_editNurbs_get(Curve *cu)
431 {
432 if (cu->editnurb) {
433 return &cu->editnurb->nurbs;
434 }
435
436 return NULL;
437 }
438
BKE_curve_type_get(const Curve * cu)439 short BKE_curve_type_get(const Curve *cu)
440 {
441 Nurb *nu;
442 int type = cu->type;
443
444 if (cu->vfont) {
445 return OB_FONT;
446 }
447
448 if (!cu->type) {
449 type = OB_CURVE;
450
451 for (nu = cu->nurb.first; nu; nu = nu->next) {
452 if (nu->pntsv > 1) {
453 type = OB_SURF;
454 }
455 }
456 }
457
458 return type;
459 }
460
BKE_curve_curve_dimension_update(Curve * cu)461 void BKE_curve_curve_dimension_update(Curve *cu)
462 {
463 ListBase *nurbs = BKE_curve_nurbs_get(cu);
464 Nurb *nu = nurbs->first;
465
466 if (cu->flag & CU_3D) {
467 for (; nu; nu = nu->next) {
468 nu->flag &= ~CU_2D;
469 }
470 }
471 else {
472 for (; nu; nu = nu->next) {
473 nu->flag |= CU_2D;
474 BKE_nurb_test_2d(nu);
475
476 /* since the handles are moved they need to be auto-located again */
477 if (nu->type == CU_BEZIER) {
478 BKE_nurb_handles_calc(nu);
479 }
480 }
481 }
482 }
483
BKE_curve_type_test(Object * ob)484 void BKE_curve_type_test(Object *ob)
485 {
486 ob->type = BKE_curve_type_get(ob->data);
487
488 if (ob->type == OB_CURVE) {
489 BKE_curve_curve_dimension_update((Curve *)ob->data);
490 }
491 }
492
BKE_curve_boundbox_get(Object * ob)493 BoundBox *BKE_curve_boundbox_get(Object *ob)
494 {
495 /* This is Object-level data access,
496 * DO NOT touch to Mesh's bb, would be totally thread-unsafe. */
497 if (ob->runtime.bb == NULL || ob->runtime.bb->flag & BOUNDBOX_DIRTY) {
498 Curve *cu = ob->data;
499 float min[3], max[3];
500
501 INIT_MINMAX(min, max);
502 BKE_curve_minmax(cu, true, min, max);
503
504 if (ob->runtime.bb == NULL) {
505 ob->runtime.bb = MEM_mallocN(sizeof(*ob->runtime.bb), __func__);
506 }
507 BKE_boundbox_init_from_minmax(ob->runtime.bb, min, max);
508 ob->runtime.bb->flag &= ~BOUNDBOX_DIRTY;
509 }
510
511 return ob->runtime.bb;
512 }
513
BKE_curve_texspace_calc(Curve * cu)514 void BKE_curve_texspace_calc(Curve *cu)
515 {
516 if (cu->texflag & CU_AUTOSPACE) {
517 float min[3], max[3];
518
519 INIT_MINMAX(min, max);
520 if (!BKE_curve_minmax(cu, true, min, max)) {
521 min[0] = min[1] = min[2] = -1.0f;
522 max[0] = max[1] = max[2] = 1.0f;
523 }
524
525 float loc[3], size[3];
526 mid_v3_v3v3(loc, min, max);
527
528 size[0] = (max[0] - min[0]) / 2.0f;
529 size[1] = (max[1] - min[1]) / 2.0f;
530 size[2] = (max[2] - min[2]) / 2.0f;
531
532 for (int a = 0; a < 3; a++) {
533 if (size[a] == 0.0f) {
534 size[a] = 1.0f;
535 }
536 else if (size[a] > 0.0f && size[a] < 0.00001f) {
537 size[a] = 0.00001f;
538 }
539 else if (size[a] < 0.0f && size[a] > -0.00001f) {
540 size[a] = -0.00001f;
541 }
542 }
543
544 copy_v3_v3(cu->loc, loc);
545 copy_v3_v3(cu->size, size);
546
547 cu->texflag |= CU_AUTOSPACE_EVALUATED;
548 }
549 }
550
BKE_curve_texspace_ensure(Curve * cu)551 void BKE_curve_texspace_ensure(Curve *cu)
552 {
553 if ((cu->texflag & CU_AUTOSPACE) && !(cu->texflag & CU_AUTOSPACE_EVALUATED)) {
554 BKE_curve_texspace_calc(cu);
555 }
556 }
557
BKE_curve_texspace_get(Curve * cu,float r_loc[3],float r_size[3])558 void BKE_curve_texspace_get(Curve *cu, float r_loc[3], float r_size[3])
559 {
560 BKE_curve_texspace_ensure(cu);
561
562 if (r_loc) {
563 copy_v3_v3(r_loc, cu->loc);
564 }
565 if (r_size) {
566 copy_v3_v3(r_size, cu->size);
567 }
568 }
569
BKE_nurbList_index_get_co(ListBase * nurb,const int index,float r_co[3])570 bool BKE_nurbList_index_get_co(ListBase *nurb, const int index, float r_co[3])
571 {
572 Nurb *nu;
573 int tot = 0;
574
575 for (nu = nurb->first; nu; nu = nu->next) {
576 int tot_nu;
577 if (nu->type == CU_BEZIER) {
578 tot_nu = nu->pntsu;
579 if (index - tot < tot_nu) {
580 copy_v3_v3(r_co, nu->bezt[index - tot].vec[1]);
581 return true;
582 }
583 }
584 else {
585 tot_nu = nu->pntsu * nu->pntsv;
586 if (index - tot < tot_nu) {
587 copy_v3_v3(r_co, nu->bp[index - tot].vec);
588 return true;
589 }
590 }
591 tot += tot_nu;
592 }
593
594 return false;
595 }
596
BKE_nurbList_verts_count(ListBase * nurb)597 int BKE_nurbList_verts_count(ListBase *nurb)
598 {
599 Nurb *nu;
600 int tot = 0;
601
602 nu = nurb->first;
603 while (nu) {
604 if (nu->bezt) {
605 tot += 3 * nu->pntsu;
606 }
607 else if (nu->bp) {
608 tot += nu->pntsu * nu->pntsv;
609 }
610
611 nu = nu->next;
612 }
613 return tot;
614 }
615
BKE_nurbList_verts_count_without_handles(ListBase * nurb)616 int BKE_nurbList_verts_count_without_handles(ListBase *nurb)
617 {
618 Nurb *nu;
619 int tot = 0;
620
621 nu = nurb->first;
622 while (nu) {
623 if (nu->bezt) {
624 tot += nu->pntsu;
625 }
626 else if (nu->bp) {
627 tot += nu->pntsu * nu->pntsv;
628 }
629
630 nu = nu->next;
631 }
632 return tot;
633 }
634
635 /* **************** NURBS ROUTINES ******************** */
636
BKE_nurb_free(Nurb * nu)637 void BKE_nurb_free(Nurb *nu)
638 {
639
640 if (nu == NULL) {
641 return;
642 }
643
644 if (nu->bezt) {
645 MEM_freeN(nu->bezt);
646 }
647 nu->bezt = NULL;
648 if (nu->bp) {
649 MEM_freeN(nu->bp);
650 }
651 nu->bp = NULL;
652 if (nu->knotsu) {
653 MEM_freeN(nu->knotsu);
654 }
655 nu->knotsu = NULL;
656 if (nu->knotsv) {
657 MEM_freeN(nu->knotsv);
658 }
659 nu->knotsv = NULL;
660 /* if (nu->trim.first) freeNurblist(&(nu->trim)); */
661
662 MEM_freeN(nu);
663 }
664
BKE_nurbList_free(ListBase * lb)665 void BKE_nurbList_free(ListBase *lb)
666 {
667 Nurb *nu, *next;
668
669 if (lb == NULL) {
670 return;
671 }
672
673 nu = lb->first;
674 while (nu) {
675 next = nu->next;
676 BKE_nurb_free(nu);
677 nu = next;
678 }
679 BLI_listbase_clear(lb);
680 }
681
BKE_nurb_duplicate(const Nurb * nu)682 Nurb *BKE_nurb_duplicate(const Nurb *nu)
683 {
684 Nurb *newnu;
685 int len;
686
687 newnu = (Nurb *)MEM_mallocN(sizeof(Nurb), "duplicateNurb");
688 if (newnu == NULL) {
689 return NULL;
690 }
691 memcpy(newnu, nu, sizeof(Nurb));
692
693 if (nu->bezt) {
694 newnu->bezt = (BezTriple *)MEM_malloc_arrayN(nu->pntsu, sizeof(BezTriple), "duplicateNurb2");
695 memcpy(newnu->bezt, nu->bezt, nu->pntsu * sizeof(BezTriple));
696 }
697 else {
698 len = nu->pntsu * nu->pntsv;
699 newnu->bp = (BPoint *)MEM_malloc_arrayN(len, sizeof(BPoint), "duplicateNurb3");
700 memcpy(newnu->bp, nu->bp, len * sizeof(BPoint));
701
702 newnu->knotsu = newnu->knotsv = NULL;
703
704 if (nu->knotsu) {
705 len = KNOTSU(nu);
706 if (len) {
707 newnu->knotsu = MEM_malloc_arrayN(len, sizeof(float), "duplicateNurb4");
708 memcpy(newnu->knotsu, nu->knotsu, sizeof(float) * len);
709 }
710 }
711 if (nu->pntsv > 1 && nu->knotsv) {
712 len = KNOTSV(nu);
713 if (len) {
714 newnu->knotsv = MEM_malloc_arrayN(len, sizeof(float), "duplicateNurb5");
715 memcpy(newnu->knotsv, nu->knotsv, sizeof(float) * len);
716 }
717 }
718 }
719 return newnu;
720 }
721
722 /* copy the nurb but allow for different number of points (to be copied after this) */
BKE_nurb_copy(Nurb * src,int pntsu,int pntsv)723 Nurb *BKE_nurb_copy(Nurb *src, int pntsu, int pntsv)
724 {
725 Nurb *newnu = (Nurb *)MEM_mallocN(sizeof(Nurb), "copyNurb");
726 memcpy(newnu, src, sizeof(Nurb));
727
728 if (pntsu == 1) {
729 SWAP(int, pntsu, pntsv);
730 }
731 newnu->pntsu = pntsu;
732 newnu->pntsv = pntsv;
733
734 /* caller can manually handle these arrays */
735 newnu->knotsu = NULL;
736 newnu->knotsv = NULL;
737
738 if (src->bezt) {
739 newnu->bezt = (BezTriple *)MEM_malloc_arrayN(pntsu * pntsv, sizeof(BezTriple), "copyNurb2");
740 }
741 else {
742 newnu->bp = (BPoint *)MEM_malloc_arrayN(pntsu * pntsv, sizeof(BPoint), "copyNurb3");
743 }
744
745 return newnu;
746 }
747
BKE_nurbList_duplicate(ListBase * lb1,const ListBase * lb2)748 void BKE_nurbList_duplicate(ListBase *lb1, const ListBase *lb2)
749 {
750 Nurb *nu, *nun;
751
752 BKE_nurbList_free(lb1);
753
754 nu = lb2->first;
755 while (nu) {
756 nun = BKE_nurb_duplicate(nu);
757 BLI_addtail(lb1, nun);
758
759 nu = nu->next;
760 }
761 }
762
BKE_nurb_test_2d(Nurb * nu)763 void BKE_nurb_test_2d(Nurb *nu)
764 {
765 BezTriple *bezt;
766 BPoint *bp;
767 int a;
768
769 if ((nu->flag & CU_2D) == 0) {
770 return;
771 }
772
773 if (nu->type == CU_BEZIER) {
774 a = nu->pntsu;
775 bezt = nu->bezt;
776 while (a--) {
777 bezt->vec[0][2] = 0.0;
778 bezt->vec[1][2] = 0.0;
779 bezt->vec[2][2] = 0.0;
780 bezt++;
781 }
782 }
783 else {
784 a = nu->pntsu * nu->pntsv;
785 bp = nu->bp;
786 while (a--) {
787 bp->vec[2] = 0.0;
788 bp++;
789 }
790 }
791 }
792
793 /**
794 * if use_radius is truth, minmax will take points' radius into account,
795 * which will make boundbox closer to beveled curve.
796 */
BKE_nurb_minmax(Nurb * nu,bool use_radius,float min[3],float max[3])797 void BKE_nurb_minmax(Nurb *nu, bool use_radius, float min[3], float max[3])
798 {
799 BezTriple *bezt;
800 BPoint *bp;
801 int a;
802 float point[3];
803
804 if (nu->type == CU_BEZIER) {
805 a = nu->pntsu;
806 bezt = nu->bezt;
807 while (a--) {
808 if (use_radius) {
809 float radius_vector[3];
810 radius_vector[0] = radius_vector[1] = radius_vector[2] = bezt->radius;
811
812 add_v3_v3v3(point, bezt->vec[1], radius_vector);
813 minmax_v3v3_v3(min, max, point);
814
815 sub_v3_v3v3(point, bezt->vec[1], radius_vector);
816 minmax_v3v3_v3(min, max, point);
817 }
818 else {
819 minmax_v3v3_v3(min, max, bezt->vec[1]);
820 }
821 minmax_v3v3_v3(min, max, bezt->vec[0]);
822 minmax_v3v3_v3(min, max, bezt->vec[2]);
823 bezt++;
824 }
825 }
826 else {
827 a = nu->pntsu * nu->pntsv;
828 bp = nu->bp;
829 while (a--) {
830 if (nu->pntsv == 1 && use_radius) {
831 float radius_vector[3];
832 radius_vector[0] = radius_vector[1] = radius_vector[2] = bp->radius;
833
834 add_v3_v3v3(point, bp->vec, radius_vector);
835 minmax_v3v3_v3(min, max, point);
836
837 sub_v3_v3v3(point, bp->vec, radius_vector);
838 minmax_v3v3_v3(min, max, point);
839 }
840 else {
841 /* Surfaces doesn't use bevel, so no need to take radius into account. */
842 minmax_v3v3_v3(min, max, bp->vec);
843 }
844 bp++;
845 }
846 }
847 }
848
BKE_nurb_calc_length(const Nurb * nu,int resolution)849 float BKE_nurb_calc_length(const Nurb *nu, int resolution)
850 {
851 BezTriple *bezt, *prevbezt;
852 BPoint *bp, *prevbp;
853 int a, b;
854 float length = 0.0f;
855 int resolu = resolution ? resolution : nu->resolu;
856 int pntsu = nu->pntsu;
857 float *points, *pntsit, *prevpntsit;
858
859 if (nu->type == CU_POLY) {
860 a = nu->pntsu - 1;
861 bp = nu->bp;
862 if (nu->flagu & CU_NURB_CYCLIC) {
863 a++;
864 prevbp = nu->bp + (nu->pntsu - 1);
865 }
866 else {
867 prevbp = bp;
868 bp++;
869 }
870
871 while (a--) {
872 length += len_v3v3(prevbp->vec, bp->vec);
873 prevbp = bp;
874 bp++;
875 }
876 }
877 else if (nu->type == CU_BEZIER) {
878 points = MEM_mallocN(sizeof(float[3]) * (resolu + 1), "getLength_bezier");
879 a = nu->pntsu - 1;
880 bezt = nu->bezt;
881 if (nu->flagu & CU_NURB_CYCLIC) {
882 a++;
883 prevbezt = nu->bezt + (nu->pntsu - 1);
884 }
885 else {
886 prevbezt = bezt;
887 bezt++;
888 }
889
890 while (a--) {
891 if (prevbezt->h2 == HD_VECT && bezt->h1 == HD_VECT) {
892 length += len_v3v3(prevbezt->vec[1], bezt->vec[1]);
893 }
894 else {
895 for (int j = 0; j < 3; j++) {
896 BKE_curve_forward_diff_bezier(prevbezt->vec[1][j],
897 prevbezt->vec[2][j],
898 bezt->vec[0][j],
899 bezt->vec[1][j],
900 points + j,
901 resolu,
902 sizeof(float[3]));
903 }
904
905 prevpntsit = pntsit = points;
906 b = resolu;
907 while (b--) {
908 pntsit += 3;
909 length += len_v3v3(prevpntsit, pntsit);
910 prevpntsit = pntsit;
911 }
912 }
913 prevbezt = bezt;
914 bezt++;
915 }
916
917 MEM_freeN(points);
918 }
919 else if (nu->type == CU_NURBS) {
920 if (nu->pntsv == 1) {
921 /* important to zero for BKE_nurb_makeCurve. */
922 points = MEM_callocN(sizeof(float[3]) * pntsu * resolu, "getLength_nurbs");
923
924 BKE_nurb_makeCurve(nu, points, NULL, NULL, NULL, resolu, sizeof(float[3]));
925
926 if (nu->flagu & CU_NURB_CYCLIC) {
927 b = pntsu * resolu + 1;
928 prevpntsit = points + 3 * (pntsu * resolu - 1);
929 pntsit = points;
930 }
931 else {
932 b = (pntsu - 1) * resolu;
933 prevpntsit = points;
934 pntsit = points + 3;
935 }
936
937 while (--b) {
938 length += len_v3v3(prevpntsit, pntsit);
939 prevpntsit = pntsit;
940 pntsit += 3;
941 }
942
943 MEM_freeN(points);
944 }
945 }
946
947 return length;
948 }
949
950 /* be sure to call makeknots after this */
BKE_nurb_points_add(Nurb * nu,int number)951 void BKE_nurb_points_add(Nurb *nu, int number)
952 {
953 nu->bp = MEM_recallocN(nu->bp, (nu->pntsu + number) * sizeof(BPoint));
954
955 BPoint *bp;
956 int i;
957 for (i = 0, bp = &nu->bp[nu->pntsu]; i < number; i++, bp++) {
958 bp->radius = 1.0f;
959 }
960
961 nu->pntsu += number;
962 }
963
BKE_nurb_bezierPoints_add(Nurb * nu,int number)964 void BKE_nurb_bezierPoints_add(Nurb *nu, int number)
965 {
966 BezTriple *bezt;
967 int i;
968
969 nu->bezt = MEM_recallocN(nu->bezt, (nu->pntsu + number) * sizeof(BezTriple));
970
971 for (i = 0, bezt = &nu->bezt[nu->pntsu]; i < number; i++, bezt++) {
972 bezt->radius = 1.0f;
973 }
974
975 nu->pntsu += number;
976 }
977
BKE_nurb_index_from_uv(Nurb * nu,int u,int v)978 int BKE_nurb_index_from_uv(Nurb *nu, int u, int v)
979 {
980 const int totu = nu->pntsu;
981 const int totv = nu->pntsv;
982
983 if (nu->flagu & CU_NURB_CYCLIC) {
984 u = mod_i(u, totu);
985 }
986 else if (u < 0 || u >= totu) {
987 return -1;
988 }
989
990 if (nu->flagv & CU_NURB_CYCLIC) {
991 v = mod_i(v, totv);
992 }
993 else if (v < 0 || v >= totv) {
994 return -1;
995 }
996
997 return (v * totu) + u;
998 }
999
BKE_nurb_index_to_uv(Nurb * nu,int index,int * r_u,int * r_v)1000 void BKE_nurb_index_to_uv(Nurb *nu, int index, int *r_u, int *r_v)
1001 {
1002 const int totu = nu->pntsu;
1003 const int totv = nu->pntsv;
1004 BLI_assert(index >= 0 && index < (nu->pntsu * nu->pntsv));
1005 *r_u = (index % totu);
1006 *r_v = (index / totu) % totv;
1007 }
1008
BKE_nurb_bezt_get_next(Nurb * nu,BezTriple * bezt)1009 BezTriple *BKE_nurb_bezt_get_next(Nurb *nu, BezTriple *bezt)
1010 {
1011 BezTriple *bezt_next;
1012
1013 BLI_assert(ARRAY_HAS_ITEM(bezt, nu->bezt, nu->pntsu));
1014
1015 if (bezt == &nu->bezt[nu->pntsu - 1]) {
1016 if (nu->flagu & CU_NURB_CYCLIC) {
1017 bezt_next = nu->bezt;
1018 }
1019 else {
1020 bezt_next = NULL;
1021 }
1022 }
1023 else {
1024 bezt_next = bezt + 1;
1025 }
1026
1027 return bezt_next;
1028 }
1029
BKE_nurb_bpoint_get_next(Nurb * nu,BPoint * bp)1030 BPoint *BKE_nurb_bpoint_get_next(Nurb *nu, BPoint *bp)
1031 {
1032 BPoint *bp_next;
1033
1034 BLI_assert(ARRAY_HAS_ITEM(bp, nu->bp, nu->pntsu));
1035
1036 if (bp == &nu->bp[nu->pntsu - 1]) {
1037 if (nu->flagu & CU_NURB_CYCLIC) {
1038 bp_next = nu->bp;
1039 }
1040 else {
1041 bp_next = NULL;
1042 }
1043 }
1044 else {
1045 bp_next = bp + 1;
1046 }
1047
1048 return bp_next;
1049 }
1050
BKE_nurb_bezt_get_prev(Nurb * nu,BezTriple * bezt)1051 BezTriple *BKE_nurb_bezt_get_prev(Nurb *nu, BezTriple *bezt)
1052 {
1053 BezTriple *bezt_prev;
1054
1055 BLI_assert(ARRAY_HAS_ITEM(bezt, nu->bezt, nu->pntsu));
1056 BLI_assert(nu->pntsv <= 1);
1057
1058 if (bezt == nu->bezt) {
1059 if (nu->flagu & CU_NURB_CYCLIC) {
1060 bezt_prev = &nu->bezt[nu->pntsu - 1];
1061 }
1062 else {
1063 bezt_prev = NULL;
1064 }
1065 }
1066 else {
1067 bezt_prev = bezt - 1;
1068 }
1069
1070 return bezt_prev;
1071 }
1072
BKE_nurb_bpoint_get_prev(Nurb * nu,BPoint * bp)1073 BPoint *BKE_nurb_bpoint_get_prev(Nurb *nu, BPoint *bp)
1074 {
1075 BPoint *bp_prev;
1076
1077 BLI_assert(ARRAY_HAS_ITEM(bp, nu->bp, nu->pntsu));
1078 BLI_assert(nu->pntsv == 1);
1079
1080 if (bp == nu->bp) {
1081 if (nu->flagu & CU_NURB_CYCLIC) {
1082 bp_prev = &nu->bp[nu->pntsu - 1];
1083 }
1084 else {
1085 bp_prev = NULL;
1086 }
1087 }
1088 else {
1089 bp_prev = bp - 1;
1090 }
1091
1092 return bp_prev;
1093 }
1094
BKE_nurb_bezt_calc_normal(struct Nurb * UNUSED (nu),BezTriple * bezt,float r_normal[3])1095 void BKE_nurb_bezt_calc_normal(struct Nurb *UNUSED(nu), BezTriple *bezt, float r_normal[3])
1096 {
1097 /* calculate the axis matrix from the spline */
1098 float dir_prev[3], dir_next[3];
1099
1100 sub_v3_v3v3(dir_prev, bezt->vec[0], bezt->vec[1]);
1101 sub_v3_v3v3(dir_next, bezt->vec[1], bezt->vec[2]);
1102
1103 normalize_v3(dir_prev);
1104 normalize_v3(dir_next);
1105
1106 add_v3_v3v3(r_normal, dir_prev, dir_next);
1107 normalize_v3(r_normal);
1108 }
1109
BKE_nurb_bezt_calc_plane(struct Nurb * nu,BezTriple * bezt,float r_plane[3])1110 void BKE_nurb_bezt_calc_plane(struct Nurb *nu, BezTriple *bezt, float r_plane[3])
1111 {
1112 float dir_prev[3], dir_next[3];
1113
1114 sub_v3_v3v3(dir_prev, bezt->vec[0], bezt->vec[1]);
1115 sub_v3_v3v3(dir_next, bezt->vec[1], bezt->vec[2]);
1116
1117 normalize_v3(dir_prev);
1118 normalize_v3(dir_next);
1119
1120 cross_v3_v3v3(r_plane, dir_prev, dir_next);
1121 if (normalize_v3(r_plane) < FLT_EPSILON) {
1122 BezTriple *bezt_prev = BKE_nurb_bezt_get_prev(nu, bezt);
1123 BezTriple *bezt_next = BKE_nurb_bezt_get_next(nu, bezt);
1124
1125 if (bezt_prev) {
1126 sub_v3_v3v3(dir_prev, bezt_prev->vec[1], bezt->vec[1]);
1127 normalize_v3(dir_prev);
1128 }
1129 if (bezt_next) {
1130 sub_v3_v3v3(dir_next, bezt->vec[1], bezt_next->vec[1]);
1131 normalize_v3(dir_next);
1132 }
1133 cross_v3_v3v3(r_plane, dir_prev, dir_next);
1134 }
1135
1136 /* matches with bones more closely */
1137 {
1138 float dir_mid[3], tvec[3];
1139 add_v3_v3v3(dir_mid, dir_prev, dir_next);
1140 cross_v3_v3v3(tvec, r_plane, dir_mid);
1141 copy_v3_v3(r_plane, tvec);
1142 }
1143
1144 normalize_v3(r_plane);
1145 }
1146
BKE_nurb_bpoint_calc_normal(struct Nurb * nu,BPoint * bp,float r_normal[3])1147 void BKE_nurb_bpoint_calc_normal(struct Nurb *nu, BPoint *bp, float r_normal[3])
1148 {
1149 BPoint *bp_prev = BKE_nurb_bpoint_get_prev(nu, bp);
1150 BPoint *bp_next = BKE_nurb_bpoint_get_next(nu, bp);
1151
1152 zero_v3(r_normal);
1153
1154 if (bp_prev) {
1155 float dir_prev[3];
1156 sub_v3_v3v3(dir_prev, bp_prev->vec, bp->vec);
1157 normalize_v3(dir_prev);
1158 add_v3_v3(r_normal, dir_prev);
1159 }
1160 if (bp_next) {
1161 float dir_next[3];
1162 sub_v3_v3v3(dir_next, bp->vec, bp_next->vec);
1163 normalize_v3(dir_next);
1164 add_v3_v3(r_normal, dir_next);
1165 }
1166
1167 normalize_v3(r_normal);
1168 }
1169
BKE_nurb_bpoint_calc_plane(struct Nurb * nu,BPoint * bp,float r_plane[3])1170 void BKE_nurb_bpoint_calc_plane(struct Nurb *nu, BPoint *bp, float r_plane[3])
1171 {
1172 BPoint *bp_prev = BKE_nurb_bpoint_get_prev(nu, bp);
1173 BPoint *bp_next = BKE_nurb_bpoint_get_next(nu, bp);
1174
1175 float dir_prev[3] = {0.0f}, dir_next[3] = {0.0f};
1176
1177 if (bp_prev) {
1178 sub_v3_v3v3(dir_prev, bp_prev->vec, bp->vec);
1179 normalize_v3(dir_prev);
1180 }
1181 if (bp_next) {
1182 sub_v3_v3v3(dir_next, bp->vec, bp_next->vec);
1183 normalize_v3(dir_next);
1184 }
1185 cross_v3_v3v3(r_plane, dir_prev, dir_next);
1186
1187 /* matches with bones more closely */
1188 {
1189 float dir_mid[3], tvec[3];
1190 add_v3_v3v3(dir_mid, dir_prev, dir_next);
1191 cross_v3_v3v3(tvec, r_plane, dir_mid);
1192 copy_v3_v3(r_plane, tvec);
1193 }
1194
1195 normalize_v3(r_plane);
1196 }
1197
1198 /* ~~~~~~~~~~~~~~~~~~~~Non Uniform Rational B Spline calculations ~~~~~~~~~~~ */
1199
calcknots(float * knots,const int pnts,const short order,const short flag)1200 static void calcknots(float *knots, const int pnts, const short order, const short flag)
1201 {
1202 /* knots: number of pnts NOT corrected for cyclic */
1203 const int pnts_order = pnts + order;
1204 float k;
1205 int a;
1206
1207 switch (flag & (CU_NURB_ENDPOINT | CU_NURB_BEZIER)) {
1208 case CU_NURB_ENDPOINT:
1209 k = 0.0;
1210 for (a = 1; a <= pnts_order; a++) {
1211 knots[a - 1] = k;
1212 if (a >= order && a <= pnts) {
1213 k += 1.0f;
1214 }
1215 }
1216 break;
1217 case CU_NURB_BEZIER:
1218 /* Warning, the order MUST be 2 or 4,
1219 * if this is not enforced, the displist will be corrupt */
1220 if (order == 4) {
1221 k = 0.34;
1222 for (a = 0; a < pnts_order; a++) {
1223 knots[a] = floorf(k);
1224 k += (1.0f / 3.0f);
1225 }
1226 }
1227 else if (order == 3) {
1228 k = 0.6f;
1229 for (a = 0; a < pnts_order; a++) {
1230 if (a >= order && a <= pnts) {
1231 k += 0.5f;
1232 }
1233 knots[a] = floorf(k);
1234 }
1235 }
1236 else {
1237 CLOG_ERROR(&LOG, "bez nurb curve order is not 3 or 4, should never happen");
1238 }
1239 break;
1240 default:
1241 for (a = 0; a < pnts_order; a++) {
1242 knots[a] = (float)a;
1243 }
1244 break;
1245 }
1246 }
1247
makecyclicknots(float * knots,int pnts,short order)1248 static void makecyclicknots(float *knots, int pnts, short order)
1249 /* pnts, order: number of pnts NOT corrected for cyclic */
1250 {
1251 int a, b, order2, c;
1252
1253 if (knots == NULL) {
1254 return;
1255 }
1256
1257 order2 = order - 1;
1258
1259 /* do first long rows (order -1), remove identical knots at endpoints */
1260 if (order > 2) {
1261 b = pnts + order2;
1262 for (a = 1; a < order2; a++) {
1263 if (knots[b] != knots[b - a]) {
1264 break;
1265 }
1266 }
1267 if (a == order2) {
1268 knots[pnts + order - 2] += 1.0f;
1269 }
1270 }
1271
1272 b = order;
1273 c = pnts + order + order2;
1274 for (a = pnts + order2; a < c; a++) {
1275 knots[a] = knots[a - 1] + (knots[b] - knots[b - 1]);
1276 b--;
1277 }
1278 }
1279
makeknots(Nurb * nu,short uv)1280 static void makeknots(Nurb *nu, short uv)
1281 {
1282 if (nu->type == CU_NURBS) {
1283 if (uv == 1) {
1284 if (nu->knotsu) {
1285 MEM_freeN(nu->knotsu);
1286 }
1287 if (BKE_nurb_check_valid_u(nu)) {
1288 nu->knotsu = MEM_calloc_arrayN(KNOTSU(nu) + 1, sizeof(float), "makeknots");
1289 if (nu->flagu & CU_NURB_CYCLIC) {
1290 calcknots(nu->knotsu, nu->pntsu, nu->orderu, 0); /* cyclic should be uniform */
1291 makecyclicknots(nu->knotsu, nu->pntsu, nu->orderu);
1292 }
1293 else {
1294 calcknots(nu->knotsu, nu->pntsu, nu->orderu, nu->flagu);
1295 }
1296 }
1297 else {
1298 nu->knotsu = NULL;
1299 }
1300 }
1301 else if (uv == 2) {
1302 if (nu->knotsv) {
1303 MEM_freeN(nu->knotsv);
1304 }
1305 if (BKE_nurb_check_valid_v(nu)) {
1306 nu->knotsv = MEM_calloc_arrayN(KNOTSV(nu) + 1, sizeof(float), "makeknots");
1307 if (nu->flagv & CU_NURB_CYCLIC) {
1308 calcknots(nu->knotsv, nu->pntsv, nu->orderv, 0); /* cyclic should be uniform */
1309 makecyclicknots(nu->knotsv, nu->pntsv, nu->orderv);
1310 }
1311 else {
1312 calcknots(nu->knotsv, nu->pntsv, nu->orderv, nu->flagv);
1313 }
1314 }
1315 else {
1316 nu->knotsv = NULL;
1317 }
1318 }
1319 }
1320 }
1321
BKE_nurb_knot_calc_u(Nurb * nu)1322 void BKE_nurb_knot_calc_u(Nurb *nu)
1323 {
1324 makeknots(nu, 1);
1325 }
1326
BKE_nurb_knot_calc_v(Nurb * nu)1327 void BKE_nurb_knot_calc_v(Nurb *nu)
1328 {
1329 makeknots(nu, 2);
1330 }
1331
basisNurb(float t,short order,int pnts,const float * knots,float * basis,int * start,int * end)1332 static void basisNurb(
1333 float t, short order, int pnts, const float *knots, float *basis, int *start, int *end)
1334 {
1335 float d, e;
1336 int i, i1 = 0, i2 = 0, j, orderpluspnts, opp2, o2;
1337
1338 orderpluspnts = order + pnts;
1339 opp2 = orderpluspnts - 1;
1340
1341 /* this is for float inaccuracy */
1342 if (t < knots[0]) {
1343 t = knots[0];
1344 }
1345 else if (t > knots[opp2]) {
1346 t = knots[opp2];
1347 }
1348
1349 /* this part is order '1' */
1350 o2 = order + 1;
1351 for (i = 0; i < opp2; i++) {
1352 if (knots[i] != knots[i + 1] && t >= knots[i] && t <= knots[i + 1]) {
1353 basis[i] = 1.0;
1354 i1 = i - o2;
1355 if (i1 < 0) {
1356 i1 = 0;
1357 }
1358 i2 = i;
1359 i++;
1360 while (i < opp2) {
1361 basis[i] = 0.0;
1362 i++;
1363 }
1364 break;
1365 }
1366
1367 basis[i] = 0.0;
1368 }
1369 basis[i] = 0.0;
1370
1371 /* this is order 2, 3, ... */
1372 for (j = 2; j <= order; j++) {
1373
1374 if (i2 + j >= orderpluspnts) {
1375 i2 = opp2 - j;
1376 }
1377
1378 for (i = i1; i <= i2; i++) {
1379 if (basis[i] != 0.0f) {
1380 d = ((t - knots[i]) * basis[i]) / (knots[i + j - 1] - knots[i]);
1381 }
1382 else {
1383 d = 0.0f;
1384 }
1385
1386 if (basis[i + 1] != 0.0f) {
1387 e = ((knots[i + j] - t) * basis[i + 1]) / (knots[i + j] - knots[i + 1]);
1388 }
1389 else {
1390 e = 0.0;
1391 }
1392
1393 basis[i] = d + e;
1394 }
1395 }
1396
1397 *start = 1000;
1398 *end = 0;
1399
1400 for (i = i1; i <= i2; i++) {
1401 if (basis[i] > 0.0f) {
1402 *end = i;
1403 if (*start == 1000) {
1404 *start = i;
1405 }
1406 }
1407 }
1408 }
1409
1410 /**
1411 * \param coord_array: has to be (3 * 4 * resolu * resolv) in size, and zero-ed.
1412 */
BKE_nurb_makeFaces(const Nurb * nu,float * coord_array,int rowstride,int resolu,int resolv)1413 void BKE_nurb_makeFaces(const Nurb *nu, float *coord_array, int rowstride, int resolu, int resolv)
1414 {
1415 BPoint *bp;
1416 float *basisu, *basis, *basisv, *sum, *fp, *in;
1417 float u, v, ustart, uend, ustep, vstart, vend, vstep, sumdiv;
1418 int i, j, iofs, jofs, cycl, len, curu, curv;
1419 int istart, iend, jsta, jen, *jstart, *jend, ratcomp;
1420
1421 int totu = nu->pntsu * resolu, totv = nu->pntsv * resolv;
1422
1423 if (nu->knotsu == NULL || nu->knotsv == NULL) {
1424 return;
1425 }
1426 if (nu->orderu > nu->pntsu) {
1427 return;
1428 }
1429 if (nu->orderv > nu->pntsv) {
1430 return;
1431 }
1432 if (coord_array == NULL) {
1433 return;
1434 }
1435
1436 /* allocate and initialize */
1437 len = totu * totv;
1438 if (len == 0) {
1439 return;
1440 }
1441
1442 sum = (float *)MEM_calloc_arrayN(len, sizeof(float), "makeNurbfaces1");
1443
1444 bp = nu->bp;
1445 i = nu->pntsu * nu->pntsv;
1446 ratcomp = 0;
1447 while (i--) {
1448 if (bp->vec[3] != 1.0f) {
1449 ratcomp = 1;
1450 break;
1451 }
1452 bp++;
1453 }
1454
1455 fp = nu->knotsu;
1456 ustart = fp[nu->orderu - 1];
1457 if (nu->flagu & CU_NURB_CYCLIC) {
1458 uend = fp[nu->pntsu + nu->orderu - 1];
1459 }
1460 else {
1461 uend = fp[nu->pntsu];
1462 }
1463 ustep = (uend - ustart) / ((nu->flagu & CU_NURB_CYCLIC) ? totu : totu - 1);
1464
1465 basisu = (float *)MEM_malloc_arrayN(KNOTSU(nu), sizeof(float), "makeNurbfaces3");
1466
1467 fp = nu->knotsv;
1468 vstart = fp[nu->orderv - 1];
1469
1470 if (nu->flagv & CU_NURB_CYCLIC) {
1471 vend = fp[nu->pntsv + nu->orderv - 1];
1472 }
1473 else {
1474 vend = fp[nu->pntsv];
1475 }
1476 vstep = (vend - vstart) / ((nu->flagv & CU_NURB_CYCLIC) ? totv : totv - 1);
1477
1478 len = KNOTSV(nu);
1479 basisv = (float *)MEM_malloc_arrayN(len * totv, sizeof(float), "makeNurbfaces3");
1480 jstart = (int *)MEM_malloc_arrayN(totv, sizeof(float), "makeNurbfaces4");
1481 jend = (int *)MEM_malloc_arrayN(totv, sizeof(float), "makeNurbfaces5");
1482
1483 /* precalculation of basisv and jstart, jend */
1484 if (nu->flagv & CU_NURB_CYCLIC) {
1485 cycl = nu->orderv - 1;
1486 }
1487 else {
1488 cycl = 0;
1489 }
1490 v = vstart;
1491 basis = basisv;
1492 curv = totv;
1493 while (curv--) {
1494 basisNurb(v, nu->orderv, nu->pntsv + cycl, nu->knotsv, basis, jstart + curv, jend + curv);
1495 basis += KNOTSV(nu);
1496 v += vstep;
1497 }
1498
1499 if (nu->flagu & CU_NURB_CYCLIC) {
1500 cycl = nu->orderu - 1;
1501 }
1502 else {
1503 cycl = 0;
1504 }
1505 in = coord_array;
1506 u = ustart;
1507 curu = totu;
1508 while (curu--) {
1509 basisNurb(u, nu->orderu, nu->pntsu + cycl, nu->knotsu, basisu, &istart, &iend);
1510
1511 basis = basisv;
1512 curv = totv;
1513 while (curv--) {
1514 jsta = jstart[curv];
1515 jen = jend[curv];
1516
1517 /* calculate sum */
1518 sumdiv = 0.0;
1519 fp = sum;
1520
1521 for (j = jsta; j <= jen; j++) {
1522
1523 if (j >= nu->pntsv) {
1524 jofs = (j - nu->pntsv);
1525 }
1526 else {
1527 jofs = j;
1528 }
1529 bp = nu->bp + nu->pntsu * jofs + istart - 1;
1530
1531 for (i = istart; i <= iend; i++, fp++) {
1532 if (i >= nu->pntsu) {
1533 iofs = i - nu->pntsu;
1534 bp = nu->bp + nu->pntsu * jofs + iofs;
1535 }
1536 else {
1537 bp++;
1538 }
1539
1540 if (ratcomp) {
1541 *fp = basisu[i] * basis[j] * bp->vec[3];
1542 sumdiv += *fp;
1543 }
1544 else {
1545 *fp = basisu[i] * basis[j];
1546 }
1547 }
1548 }
1549
1550 if (ratcomp) {
1551 fp = sum;
1552 for (j = jsta; j <= jen; j++) {
1553 for (i = istart; i <= iend; i++, fp++) {
1554 *fp /= sumdiv;
1555 }
1556 }
1557 }
1558
1559 zero_v3(in);
1560
1561 /* one! (1.0) real point now */
1562 fp = sum;
1563 for (j = jsta; j <= jen; j++) {
1564
1565 if (j >= nu->pntsv) {
1566 jofs = (j - nu->pntsv);
1567 }
1568 else {
1569 jofs = j;
1570 }
1571 bp = nu->bp + nu->pntsu * jofs + istart - 1;
1572
1573 for (i = istart; i <= iend; i++, fp++) {
1574 if (i >= nu->pntsu) {
1575 iofs = i - nu->pntsu;
1576 bp = nu->bp + nu->pntsu * jofs + iofs;
1577 }
1578 else {
1579 bp++;
1580 }
1581
1582 if (*fp != 0.0f) {
1583 madd_v3_v3fl(in, bp->vec, *fp);
1584 }
1585 }
1586 }
1587
1588 in += 3;
1589 basis += KNOTSV(nu);
1590 }
1591 u += ustep;
1592 if (rowstride != 0) {
1593 in = (float *)(((unsigned char *)in) + (rowstride - 3 * totv * sizeof(*in)));
1594 }
1595 }
1596
1597 /* free */
1598 MEM_freeN(sum);
1599 MEM_freeN(basisu);
1600 MEM_freeN(basisv);
1601 MEM_freeN(jstart);
1602 MEM_freeN(jend);
1603 }
1604
1605 /**
1606 * \param coord_array: Has to be 3 * 4 * pntsu * resolu in size and zero-ed
1607 * \param tilt_array: set when non-NULL
1608 * \param radius_array: set when non-NULL
1609 */
BKE_nurb_makeCurve(const Nurb * nu,float * coord_array,float * tilt_array,float * radius_array,float * weight_array,int resolu,int stride)1610 void BKE_nurb_makeCurve(const Nurb *nu,
1611 float *coord_array,
1612 float *tilt_array,
1613 float *radius_array,
1614 float *weight_array,
1615 int resolu,
1616 int stride)
1617 {
1618 const float eps = 1e-6f;
1619 BPoint *bp;
1620 float u, ustart, uend, ustep, sumdiv;
1621 float *basisu, *sum, *fp;
1622 float *coord_fp = coord_array, *tilt_fp = tilt_array, *radius_fp = radius_array,
1623 *weight_fp = weight_array;
1624 int i, len, istart, iend, cycl;
1625
1626 if (nu->knotsu == NULL) {
1627 return;
1628 }
1629 if (nu->orderu > nu->pntsu) {
1630 return;
1631 }
1632 if (coord_array == NULL) {
1633 return;
1634 }
1635
1636 /* allocate and initialize */
1637 len = nu->pntsu;
1638 if (len == 0) {
1639 return;
1640 }
1641 sum = (float *)MEM_calloc_arrayN(len, sizeof(float), "makeNurbcurve1");
1642
1643 resolu = (resolu * SEGMENTSU(nu));
1644
1645 if (resolu == 0) {
1646 MEM_freeN(sum);
1647 return;
1648 }
1649
1650 fp = nu->knotsu;
1651 ustart = fp[nu->orderu - 1];
1652 if (nu->flagu & CU_NURB_CYCLIC) {
1653 uend = fp[nu->pntsu + nu->orderu - 1];
1654 }
1655 else {
1656 uend = fp[nu->pntsu];
1657 }
1658 ustep = (uend - ustart) / (resolu - ((nu->flagu & CU_NURB_CYCLIC) ? 0 : 1));
1659
1660 basisu = (float *)MEM_malloc_arrayN(KNOTSU(nu), sizeof(float), "makeNurbcurve3");
1661
1662 if (nu->flagu & CU_NURB_CYCLIC) {
1663 cycl = nu->orderu - 1;
1664 }
1665 else {
1666 cycl = 0;
1667 }
1668
1669 u = ustart;
1670 while (resolu--) {
1671 basisNurb(u, nu->orderu, nu->pntsu + cycl, nu->knotsu, basisu, &istart, &iend);
1672
1673 /* calc sum */
1674 sumdiv = 0.0;
1675 fp = sum;
1676 bp = nu->bp + istart - 1;
1677 for (i = istart; i <= iend; i++, fp++) {
1678 if (i >= nu->pntsu) {
1679 bp = nu->bp + (i - nu->pntsu);
1680 }
1681 else {
1682 bp++;
1683 }
1684
1685 *fp = basisu[i] * bp->vec[3];
1686 sumdiv += *fp;
1687 }
1688 if ((sumdiv != 0.0f) && (sumdiv < 1.0f - eps || sumdiv > 1.0f + eps)) {
1689 /* is normalizing needed? */
1690 fp = sum;
1691 for (i = istart; i <= iend; i++, fp++) {
1692 *fp /= sumdiv;
1693 }
1694 }
1695
1696 zero_v3(coord_fp);
1697
1698 /* one! (1.0) real point */
1699 fp = sum;
1700 bp = nu->bp + istart - 1;
1701 for (i = istart; i <= iend; i++, fp++) {
1702 if (i >= nu->pntsu) {
1703 bp = nu->bp + (i - nu->pntsu);
1704 }
1705 else {
1706 bp++;
1707 }
1708
1709 if (*fp != 0.0f) {
1710 madd_v3_v3fl(coord_fp, bp->vec, *fp);
1711
1712 if (tilt_fp) {
1713 (*tilt_fp) += (*fp) * bp->tilt;
1714 }
1715
1716 if (radius_fp) {
1717 (*radius_fp) += (*fp) * bp->radius;
1718 }
1719
1720 if (weight_fp) {
1721 (*weight_fp) += (*fp) * bp->weight;
1722 }
1723 }
1724 }
1725
1726 coord_fp = POINTER_OFFSET(coord_fp, stride);
1727
1728 if (tilt_fp) {
1729 tilt_fp = POINTER_OFFSET(tilt_fp, stride);
1730 }
1731 if (radius_fp) {
1732 radius_fp = POINTER_OFFSET(radius_fp, stride);
1733 }
1734 if (weight_fp) {
1735 weight_fp = POINTER_OFFSET(weight_fp, stride);
1736 }
1737
1738 u += ustep;
1739 }
1740
1741 /* free */
1742 MEM_freeN(sum);
1743 MEM_freeN(basisu);
1744 }
1745
1746 /**
1747 * Calculate the length for arrays filled in by #BKE_curve_calc_coords_axis.
1748 */
BKE_curve_calc_coords_axis_len(const unsigned int bezt_array_len,const unsigned int resolu,const bool is_cyclic,const bool use_cyclic_duplicate_endpoint)1749 unsigned int BKE_curve_calc_coords_axis_len(const unsigned int bezt_array_len,
1750 const unsigned int resolu,
1751 const bool is_cyclic,
1752 const bool use_cyclic_duplicate_endpoint)
1753 {
1754 const unsigned int segments = bezt_array_len - (is_cyclic ? 0 : 1);
1755 const unsigned int points_len = (segments * resolu) +
1756 (is_cyclic ? (use_cyclic_duplicate_endpoint) : 1);
1757 return points_len;
1758 }
1759
1760 /**
1761 * Calculate an array for the entire curve (cyclic or non-cyclic).
1762 * \note Call for each axis.
1763 *
1764 * \param use_cyclic_duplicate_endpoint: Duplicate values at the beginning & end of the array.
1765 */
BKE_curve_calc_coords_axis(const BezTriple * bezt_array,const unsigned int bezt_array_len,const unsigned int resolu,const bool is_cyclic,const bool use_cyclic_duplicate_endpoint,const unsigned int axis,const unsigned int stride,float * r_points)1766 void BKE_curve_calc_coords_axis(const BezTriple *bezt_array,
1767 const unsigned int bezt_array_len,
1768 const unsigned int resolu,
1769 const bool is_cyclic,
1770 const bool use_cyclic_duplicate_endpoint,
1771 /* array params */
1772 const unsigned int axis,
1773 const unsigned int stride,
1774 float *r_points)
1775 {
1776 const unsigned int points_len = BKE_curve_calc_coords_axis_len(
1777 bezt_array_len, resolu, is_cyclic, use_cyclic_duplicate_endpoint);
1778 float *r_points_offset = r_points;
1779
1780 const unsigned int resolu_stride = resolu * stride;
1781 const unsigned int bezt_array_last = bezt_array_len - 1;
1782
1783 for (unsigned int i = 0; i < bezt_array_last; i++) {
1784 const BezTriple *bezt_curr = &bezt_array[i];
1785 const BezTriple *bezt_next = &bezt_array[i + 1];
1786 BKE_curve_forward_diff_bezier(bezt_curr->vec[1][axis],
1787 bezt_curr->vec[2][axis],
1788 bezt_next->vec[0][axis],
1789 bezt_next->vec[1][axis],
1790 r_points_offset,
1791 (int)resolu,
1792 stride);
1793 r_points_offset = POINTER_OFFSET(r_points_offset, resolu_stride);
1794 }
1795
1796 if (is_cyclic) {
1797 const BezTriple *bezt_curr = &bezt_array[bezt_array_last];
1798 const BezTriple *bezt_next = &bezt_array[0];
1799 BKE_curve_forward_diff_bezier(bezt_curr->vec[1][axis],
1800 bezt_curr->vec[2][axis],
1801 bezt_next->vec[0][axis],
1802 bezt_next->vec[1][axis],
1803 r_points_offset,
1804 (int)resolu,
1805 stride);
1806 r_points_offset = POINTER_OFFSET(r_points_offset, resolu_stride);
1807 if (use_cyclic_duplicate_endpoint) {
1808 *r_points_offset = *r_points;
1809 r_points_offset = POINTER_OFFSET(r_points_offset, stride);
1810 }
1811 }
1812 else {
1813 float *r_points_last = POINTER_OFFSET(r_points, bezt_array_last * resolu_stride);
1814 *r_points_last = bezt_array[bezt_array_last].vec[1][axis];
1815 r_points_offset = POINTER_OFFSET(r_points_offset, stride);
1816 }
1817
1818 BLI_assert(POINTER_OFFSET(r_points, points_len * stride) == r_points_offset);
1819 UNUSED_VARS_NDEBUG(points_len);
1820 }
1821
1822 /* forward differencing method for bezier curve */
BKE_curve_forward_diff_bezier(float q0,float q1,float q2,float q3,float * p,int it,int stride)1823 void BKE_curve_forward_diff_bezier(
1824 float q0, float q1, float q2, float q3, float *p, int it, int stride)
1825 {
1826 float rt0, rt1, rt2, rt3, f;
1827 int a;
1828
1829 f = (float)it;
1830 rt0 = q0;
1831 rt1 = 3.0f * (q1 - q0) / f;
1832 f *= f;
1833 rt2 = 3.0f * (q0 - 2.0f * q1 + q2) / f;
1834 f *= it;
1835 rt3 = (q3 - q0 + 3.0f * (q1 - q2)) / f;
1836
1837 q0 = rt0;
1838 q1 = rt1 + rt2 + rt3;
1839 q2 = 2 * rt2 + 6 * rt3;
1840 q3 = 6 * rt3;
1841
1842 for (a = 0; a <= it; a++) {
1843 *p = q0;
1844 p = POINTER_OFFSET(p, stride);
1845 q0 += q1;
1846 q1 += q2;
1847 q2 += q3;
1848 }
1849 }
1850
1851 /* forward differencing method for first derivative of cubic bezier curve */
BKE_curve_forward_diff_tangent_bezier(float q0,float q1,float q2,float q3,float * p,int it,int stride)1852 void BKE_curve_forward_diff_tangent_bezier(
1853 float q0, float q1, float q2, float q3, float *p, int it, int stride)
1854 {
1855 float rt0, rt1, rt2, f;
1856 int a;
1857
1858 f = 1.0f / (float)it;
1859
1860 rt0 = 3.0f * (q1 - q0);
1861 rt1 = f * (3.0f * (q3 - q0) + 9.0f * (q1 - q2));
1862 rt2 = 6.0f * (q0 + q2) - 12.0f * q1;
1863
1864 q0 = rt0;
1865 q1 = f * (rt1 + rt2);
1866 q2 = 2.0f * f * rt1;
1867
1868 for (a = 0; a <= it; a++) {
1869 *p = q0;
1870 p = POINTER_OFFSET(p, stride);
1871 q0 += q1;
1872 q1 += q2;
1873 }
1874 }
1875
forward_diff_bezier_cotangent(const float p0[3],const float p1[3],const float p2[3],const float p3[3],float p[3],int it,int stride)1876 static void forward_diff_bezier_cotangent(const float p0[3],
1877 const float p1[3],
1878 const float p2[3],
1879 const float p3[3],
1880 float p[3],
1881 int it,
1882 int stride)
1883 {
1884 /* note that these are not perpendicular to the curve
1885 * they need to be rotated for this,
1886 *
1887 * This could also be optimized like BKE_curve_forward_diff_bezier */
1888 for (int a = 0; a <= it; a++) {
1889 float t = (float)a / (float)it;
1890
1891 for (int i = 0; i < 3; i++) {
1892 p[i] = (-6.0f * t + 6.0f) * p0[i] + (18.0f * t - 12.0f) * p1[i] +
1893 (-18.0f * t + 6.0f) * p2[i] + (6.0f * t) * p3[i];
1894 }
1895 normalize_v3(p);
1896 p = POINTER_OFFSET(p, stride);
1897 }
1898 }
1899
cu_isectLL(const float v1[3],const float v2[3],const float v3[3],const float v4[3],short cox,short coy,float * lambda,float * mu,float vec[3])1900 static int cu_isectLL(const float v1[3],
1901 const float v2[3],
1902 const float v3[3],
1903 const float v4[3],
1904 short cox,
1905 short coy,
1906 float *lambda,
1907 float *mu,
1908 float vec[3])
1909 {
1910 /* return:
1911 * -1: collinear
1912 * 0: no intersection of segments
1913 * 1: exact intersection of segments
1914 * 2: cross-intersection of segments
1915 */
1916 float deler;
1917
1918 deler = (v1[cox] - v2[cox]) * (v3[coy] - v4[coy]) - (v3[cox] - v4[cox]) * (v1[coy] - v2[coy]);
1919 if (deler == 0.0f) {
1920 return -1;
1921 }
1922
1923 *lambda = (v1[coy] - v3[coy]) * (v3[cox] - v4[cox]) - (v1[cox] - v3[cox]) * (v3[coy] - v4[coy]);
1924 *lambda = -(*lambda / deler);
1925
1926 deler = v3[coy] - v4[coy];
1927 if (deler == 0) {
1928 deler = v3[cox] - v4[cox];
1929 *mu = -(*lambda * (v2[cox] - v1[cox]) + v1[cox] - v3[cox]) / deler;
1930 }
1931 else {
1932 *mu = -(*lambda * (v2[coy] - v1[coy]) + v1[coy] - v3[coy]) / deler;
1933 }
1934 vec[cox] = *lambda * (v2[cox] - v1[cox]) + v1[cox];
1935 vec[coy] = *lambda * (v2[coy] - v1[coy]) + v1[coy];
1936
1937 if (*lambda >= 0.0f && *lambda <= 1.0f && *mu >= 0.0f && *mu <= 1.0f) {
1938 if (*lambda == 0.0f || *lambda == 1.0f || *mu == 0.0f || *mu == 1.0f) {
1939 return 1;
1940 }
1941 return 2;
1942 }
1943 return 0;
1944 }
1945
bevelinside(BevList * bl1,BevList * bl2)1946 static bool bevelinside(BevList *bl1, BevList *bl2)
1947 {
1948 /* is bl2 INSIDE bl1 ? with left-right method and "lambda's" */
1949 /* returns '1' if correct hole */
1950 BevPoint *bevp, *prevbevp;
1951 float min, max, vec[3], hvec1[3], hvec2[3], lab, mu;
1952 int nr, links = 0, rechts = 0, mode;
1953
1954 /* take first vertex of possible hole */
1955
1956 bevp = bl2->bevpoints;
1957 hvec1[0] = bevp->vec[0];
1958 hvec1[1] = bevp->vec[1];
1959 hvec1[2] = 0.0;
1960 copy_v3_v3(hvec2, hvec1);
1961 hvec2[0] += 1000;
1962
1963 /* test it with all edges of potential surrounding poly */
1964 /* count number of transitions left-right */
1965
1966 bevp = bl1->bevpoints;
1967 nr = bl1->nr;
1968 prevbevp = bevp + (nr - 1);
1969
1970 while (nr--) {
1971 min = prevbevp->vec[1];
1972 max = bevp->vec[1];
1973 if (max < min) {
1974 min = max;
1975 max = prevbevp->vec[1];
1976 }
1977 if (min != max) {
1978 if (min <= hvec1[1] && max >= hvec1[1]) {
1979 /* there's a transition, calc intersection point */
1980 mode = cu_isectLL(prevbevp->vec, bevp->vec, hvec1, hvec2, 0, 1, &lab, &mu, vec);
1981 /* if lab==0.0 or lab==1.0 then the edge intersects exactly a transition
1982 * only allow for one situation: we choose lab= 1.0
1983 */
1984 if (mode >= 0 && lab != 0.0f) {
1985 if (vec[0] < hvec1[0]) {
1986 links++;
1987 }
1988 else {
1989 rechts++;
1990 }
1991 }
1992 }
1993 }
1994 prevbevp = bevp;
1995 bevp++;
1996 }
1997
1998 return (links & 1) && (rechts & 1);
1999 }
2000
2001 struct BevelSort {
2002 BevList *bl;
2003 float left;
2004 int dir;
2005 };
2006
vergxcobev(const void * a1,const void * a2)2007 static int vergxcobev(const void *a1, const void *a2)
2008 {
2009 const struct BevelSort *x1 = a1, *x2 = a2;
2010
2011 if (x1->left > x2->left) {
2012 return 1;
2013 }
2014 if (x1->left < x2->left) {
2015 return -1;
2016 }
2017 return 0;
2018 }
2019
2020 /* this function cannot be replaced with atan2, but why? */
2021
calc_bevel_sin_cos(float x1,float y1,float x2,float y2,float * r_sina,float * r_cosa)2022 static void calc_bevel_sin_cos(
2023 float x1, float y1, float x2, float y2, float *r_sina, float *r_cosa)
2024 {
2025 float t01, t02, x3, y3;
2026
2027 t01 = sqrtf(x1 * x1 + y1 * y1);
2028 t02 = sqrtf(x2 * x2 + y2 * y2);
2029 if (t01 == 0.0f) {
2030 t01 = 1.0f;
2031 }
2032 if (t02 == 0.0f) {
2033 t02 = 1.0f;
2034 }
2035
2036 x1 /= t01;
2037 y1 /= t01;
2038 x2 /= t02;
2039 y2 /= t02;
2040
2041 t02 = x1 * x2 + y1 * y2;
2042 if (fabsf(t02) >= 1.0f) {
2043 t02 = M_PI_2;
2044 }
2045 else {
2046 t02 = (saacos(t02)) / 2.0f;
2047 }
2048
2049 t02 = sinf(t02);
2050 if (t02 == 0.0f) {
2051 t02 = 1.0f;
2052 }
2053
2054 x3 = x1 - x2;
2055 y3 = y1 - y2;
2056 if (x3 == 0 && y3 == 0) {
2057 x3 = y1;
2058 y3 = -x1;
2059 }
2060 else {
2061 t01 = sqrtf(x3 * x3 + y3 * y3);
2062 x3 /= t01;
2063 y3 /= t01;
2064 }
2065
2066 *r_sina = -y3 / t02;
2067 *r_cosa = x3 / t02;
2068 }
2069
tilt_bezpart(BezTriple * prevbezt,BezTriple * bezt,Nurb * nu,float * tilt_array,float * radius_array,float * weight_array,int resolu,int stride)2070 static void tilt_bezpart(BezTriple *prevbezt,
2071 BezTriple *bezt,
2072 Nurb *nu,
2073 float *tilt_array,
2074 float *radius_array,
2075 float *weight_array,
2076 int resolu,
2077 int stride)
2078 {
2079 BezTriple *pprev, *next, *last;
2080 float fac, dfac, t[4];
2081 int a;
2082
2083 if (tilt_array == NULL && radius_array == NULL) {
2084 return;
2085 }
2086
2087 last = nu->bezt + (nu->pntsu - 1);
2088
2089 /* returns a point */
2090 if (prevbezt == nu->bezt) {
2091 if (nu->flagu & CU_NURB_CYCLIC) {
2092 pprev = last;
2093 }
2094 else {
2095 pprev = prevbezt;
2096 }
2097 }
2098 else {
2099 pprev = prevbezt - 1;
2100 }
2101
2102 /* next point */
2103 if (bezt == last) {
2104 if (nu->flagu & CU_NURB_CYCLIC) {
2105 next = nu->bezt;
2106 }
2107 else {
2108 next = bezt;
2109 }
2110 }
2111 else {
2112 next = bezt + 1;
2113 }
2114
2115 fac = 0.0;
2116 dfac = 1.0f / (float)resolu;
2117
2118 for (a = 0; a < resolu; a++, fac += dfac) {
2119 if (tilt_array) {
2120 if (nu->tilt_interp == KEY_CU_EASE) {
2121 /* May as well support for tilt also 2.47 ease interp. */
2122 *tilt_array = prevbezt->tilt +
2123 (bezt->tilt - prevbezt->tilt) * (3.0f * fac * fac - 2.0f * fac * fac * fac);
2124 }
2125 else {
2126 key_curve_position_weights(fac, t, nu->tilt_interp);
2127 *tilt_array = t[0] * pprev->tilt + t[1] * prevbezt->tilt + t[2] * bezt->tilt +
2128 t[3] * next->tilt;
2129 }
2130
2131 tilt_array = POINTER_OFFSET(tilt_array, stride);
2132 }
2133
2134 if (radius_array) {
2135 if (nu->radius_interp == KEY_CU_EASE) {
2136 /* Support 2.47 ease interp
2137 * Note! - this only takes the 2 points into account,
2138 * giving much more localized results to changes in radius, sometimes you want that */
2139 *radius_array = prevbezt->radius + (bezt->radius - prevbezt->radius) *
2140 (3.0f * fac * fac - 2.0f * fac * fac * fac);
2141 }
2142 else {
2143
2144 /* reuse interpolation from tilt if we can */
2145 if (tilt_array == NULL || nu->tilt_interp != nu->radius_interp) {
2146 key_curve_position_weights(fac, t, nu->radius_interp);
2147 }
2148 *radius_array = t[0] * pprev->radius + t[1] * prevbezt->radius + t[2] * bezt->radius +
2149 t[3] * next->radius;
2150 }
2151
2152 radius_array = POINTER_OFFSET(radius_array, stride);
2153 }
2154
2155 if (weight_array) {
2156 /* basic interpolation for now, could copy tilt interp too */
2157 *weight_array = prevbezt->weight + (bezt->weight - prevbezt->weight) *
2158 (3.0f * fac * fac - 2.0f * fac * fac * fac);
2159
2160 weight_array = POINTER_OFFSET(weight_array, stride);
2161 }
2162 }
2163 }
2164
2165 /* make_bevel_list_3D_* funcs, at a minimum these must
2166 * fill in the bezp->quat and bezp->dir values */
2167
2168 /* utility for make_bevel_list_3D_* funcs */
bevel_list_calc_bisect(BevList * bl)2169 static void bevel_list_calc_bisect(BevList *bl)
2170 {
2171 BevPoint *bevp2, *bevp1, *bevp0;
2172 int nr;
2173 bool is_cyclic = bl->poly != -1;
2174
2175 if (is_cyclic) {
2176 bevp2 = bl->bevpoints;
2177 bevp1 = bevp2 + (bl->nr - 1);
2178 bevp0 = bevp1 - 1;
2179 nr = bl->nr;
2180 }
2181 else {
2182 /* If spline is not cyclic, direction of first and
2183 * last bevel points matches direction of CV handle.
2184 *
2185 * This is getting calculated earlier when we know
2186 * CV's handles and here we might simply skip evaluation
2187 * of direction for this guys.
2188 */
2189
2190 bevp0 = bl->bevpoints;
2191 bevp1 = bevp0 + 1;
2192 bevp2 = bevp1 + 1;
2193
2194 nr = bl->nr - 2;
2195 }
2196
2197 while (nr--) {
2198 /* totally simple */
2199 bisect_v3_v3v3v3(bevp1->dir, bevp0->vec, bevp1->vec, bevp2->vec);
2200
2201 bevp0 = bevp1;
2202 bevp1 = bevp2;
2203 bevp2++;
2204 }
2205 }
bevel_list_flip_tangents(BevList * bl)2206 static void bevel_list_flip_tangents(BevList *bl)
2207 {
2208 BevPoint *bevp2, *bevp1, *bevp0;
2209 int nr;
2210
2211 bevp2 = bl->bevpoints;
2212 bevp1 = bevp2 + (bl->nr - 1);
2213 bevp0 = bevp1 - 1;
2214
2215 nr = bl->nr;
2216 while (nr--) {
2217 if (angle_normalized_v3v3(bevp0->tan, bevp1->tan) > DEG2RADF(90.0f)) {
2218 negate_v3(bevp1->tan);
2219 }
2220
2221 bevp0 = bevp1;
2222 bevp1 = bevp2;
2223 bevp2++;
2224 }
2225 }
2226 /* apply user tilt */
bevel_list_apply_tilt(BevList * bl)2227 static void bevel_list_apply_tilt(BevList *bl)
2228 {
2229 BevPoint *bevp2, *bevp1;
2230 int nr;
2231 float q[4];
2232
2233 bevp2 = bl->bevpoints;
2234 bevp1 = bevp2 + (bl->nr - 1);
2235
2236 nr = bl->nr;
2237 while (nr--) {
2238 axis_angle_to_quat(q, bevp1->dir, bevp1->tilt);
2239 mul_qt_qtqt(bevp1->quat, q, bevp1->quat);
2240 normalize_qt(bevp1->quat);
2241
2242 bevp1 = bevp2;
2243 bevp2++;
2244 }
2245 }
2246 /* smooth quats, this function should be optimized, it can get slow with many iterations. */
bevel_list_smooth(BevList * bl,int smooth_iter)2247 static void bevel_list_smooth(BevList *bl, int smooth_iter)
2248 {
2249 BevPoint *bevp2, *bevp1, *bevp0;
2250 int nr;
2251
2252 float q[4];
2253 float bevp0_quat[4];
2254 int a;
2255
2256 for (a = 0; a < smooth_iter; a++) {
2257 bevp2 = bl->bevpoints;
2258 bevp1 = bevp2 + (bl->nr - 1);
2259 bevp0 = bevp1 - 1;
2260
2261 nr = bl->nr;
2262
2263 if (bl->poly == -1) { /* check its not cyclic */
2264 /* skip the first point */
2265 /* bevp0 = bevp1; */
2266 bevp1 = bevp2;
2267 bevp2++;
2268 nr--;
2269
2270 bevp0 = bevp1;
2271 bevp1 = bevp2;
2272 bevp2++;
2273 nr--;
2274 }
2275
2276 copy_qt_qt(bevp0_quat, bevp0->quat);
2277
2278 while (nr--) {
2279 /* interpolate quats */
2280 float zaxis[3] = {0, 0, 1}, cross[3], q2[4];
2281 interp_qt_qtqt(q, bevp0_quat, bevp2->quat, 0.5);
2282 normalize_qt(q);
2283
2284 mul_qt_v3(q, zaxis);
2285 cross_v3_v3v3(cross, zaxis, bevp1->dir);
2286 axis_angle_to_quat(q2, cross, angle_normalized_v3v3(zaxis, bevp1->dir));
2287 normalize_qt(q2);
2288
2289 copy_qt_qt(bevp0_quat, bevp1->quat);
2290 mul_qt_qtqt(q, q2, q);
2291 interp_qt_qtqt(bevp1->quat, bevp1->quat, q, 0.5);
2292 normalize_qt(bevp1->quat);
2293
2294 /* bevp0 = bevp1; */ /* UNUSED */
2295 bevp1 = bevp2;
2296 bevp2++;
2297 }
2298 }
2299 }
2300
make_bevel_list_3D_zup(BevList * bl)2301 static void make_bevel_list_3D_zup(BevList *bl)
2302 {
2303 BevPoint *bevp = bl->bevpoints;
2304 int nr = bl->nr;
2305
2306 bevel_list_calc_bisect(bl);
2307
2308 while (nr--) {
2309 vec_to_quat(bevp->quat, bevp->dir, 5, 1);
2310 bevp++;
2311 }
2312 }
2313
minimum_twist_between_two_points(BevPoint * current_point,BevPoint * previous_point)2314 static void minimum_twist_between_two_points(BevPoint *current_point, BevPoint *previous_point)
2315 {
2316 float angle = angle_normalized_v3v3(previous_point->dir, current_point->dir);
2317 float q[4];
2318
2319 if (angle > 0.0f) { /* otherwise we can keep as is */
2320 float cross_tmp[3];
2321 cross_v3_v3v3(cross_tmp, previous_point->dir, current_point->dir);
2322 axis_angle_to_quat(q, cross_tmp, angle);
2323 mul_qt_qtqt(current_point->quat, q, previous_point->quat);
2324 }
2325 else {
2326 copy_qt_qt(current_point->quat, previous_point->quat);
2327 }
2328 }
2329
make_bevel_list_3D_minimum_twist(BevList * bl)2330 static void make_bevel_list_3D_minimum_twist(BevList *bl)
2331 {
2332 BevPoint *bevp2, *bevp1, *bevp0; /* standard for all make_bevel_list_3D_* funcs */
2333 int nr;
2334 float q[4];
2335
2336 bevel_list_calc_bisect(bl);
2337
2338 bevp2 = bl->bevpoints;
2339 bevp1 = bevp2 + (bl->nr - 1);
2340 bevp0 = bevp1 - 1;
2341
2342 nr = bl->nr;
2343 while (nr--) {
2344
2345 if (nr + 3 > bl->nr) { /* first time and second time, otherwise first point adjusts last */
2346 vec_to_quat(bevp1->quat, bevp1->dir, 5, 1);
2347 }
2348 else {
2349 minimum_twist_between_two_points(bevp1, bevp0);
2350 }
2351
2352 bevp0 = bevp1;
2353 bevp1 = bevp2;
2354 bevp2++;
2355 }
2356
2357 if (bl->poly != -1) { /* check for cyclic */
2358
2359 /* Need to correct for the start/end points not matching
2360 * do this by calculating the tilt angle difference, then apply
2361 * the rotation gradually over the entire curve
2362 *
2363 * note that the split is between last and second last, rather than first/last as youd expect.
2364 *
2365 * real order is like this
2366 * 0,1,2,3,4 --> 1,2,3,4,0
2367 *
2368 * this is why we compare last with second last
2369 * */
2370 float vec_1[3] = {0, 1, 0}, vec_2[3] = {0, 1, 0}, angle, ang_fac, cross_tmp[3];
2371
2372 BevPoint *bevp_first;
2373 BevPoint *bevp_last;
2374
2375 bevp_first = bl->bevpoints;
2376 bevp_first += bl->nr - 1;
2377 bevp_last = bevp_first;
2378 bevp_last--;
2379
2380 /* quats and vec's are normalized, should not need to re-normalize */
2381 mul_qt_v3(bevp_first->quat, vec_1);
2382 mul_qt_v3(bevp_last->quat, vec_2);
2383 normalize_v3(vec_1);
2384 normalize_v3(vec_2);
2385
2386 /* align the vector, can avoid this and it looks 98% OK but
2387 * better to align the angle quat roll's before comparing */
2388 {
2389 cross_v3_v3v3(cross_tmp, bevp_last->dir, bevp_first->dir);
2390 angle = angle_normalized_v3v3(bevp_first->dir, bevp_last->dir);
2391 axis_angle_to_quat(q, cross_tmp, angle);
2392 mul_qt_v3(q, vec_2);
2393 }
2394
2395 angle = angle_normalized_v3v3(vec_1, vec_2);
2396
2397 /* flip rotation if needs be */
2398 cross_v3_v3v3(cross_tmp, vec_1, vec_2);
2399 normalize_v3(cross_tmp);
2400 if (angle_normalized_v3v3(bevp_first->dir, cross_tmp) < DEG2RADF(90.0f)) {
2401 angle = -angle;
2402 }
2403
2404 bevp2 = bl->bevpoints;
2405 bevp1 = bevp2 + (bl->nr - 1);
2406 bevp0 = bevp1 - 1;
2407
2408 nr = bl->nr;
2409 while (nr--) {
2410 ang_fac = angle * (1.0f - ((float)nr / bl->nr)); /* also works */
2411
2412 axis_angle_to_quat(q, bevp1->dir, ang_fac);
2413 mul_qt_qtqt(bevp1->quat, q, bevp1->quat);
2414
2415 bevp0 = bevp1;
2416 bevp1 = bevp2;
2417 bevp2++;
2418 }
2419 }
2420 else {
2421 /* Need to correct quat for the first/last point,
2422 * this is so because previously it was only calculated
2423 * using its own direction, which might not correspond
2424 * the twist of neighbor point.
2425 */
2426 bevp1 = bl->bevpoints;
2427 bevp0 = bevp1 + 1;
2428 minimum_twist_between_two_points(bevp1, bevp0);
2429
2430 bevp2 = bl->bevpoints;
2431 bevp1 = bevp2 + (bl->nr - 1);
2432 bevp0 = bevp1 - 1;
2433 minimum_twist_between_two_points(bevp1, bevp0);
2434 }
2435 }
2436
make_bevel_list_3D_tangent(BevList * bl)2437 static void make_bevel_list_3D_tangent(BevList *bl)
2438 {
2439 BevPoint *bevp2, *bevp1, *bevp0; /* standard for all make_bevel_list_3D_* funcs */
2440 int nr;
2441
2442 float bevp0_tan[3];
2443
2444 bevel_list_calc_bisect(bl);
2445 bevel_list_flip_tangents(bl);
2446
2447 /* correct the tangents */
2448 bevp2 = bl->bevpoints;
2449 bevp1 = bevp2 + (bl->nr - 1);
2450 bevp0 = bevp1 - 1;
2451
2452 nr = bl->nr;
2453 while (nr--) {
2454 float cross_tmp[3];
2455 cross_v3_v3v3(cross_tmp, bevp1->tan, bevp1->dir);
2456 cross_v3_v3v3(bevp1->tan, cross_tmp, bevp1->dir);
2457 normalize_v3(bevp1->tan);
2458
2459 bevp0 = bevp1;
2460 bevp1 = bevp2;
2461 bevp2++;
2462 }
2463
2464 /* now for the real twist calc */
2465 bevp2 = bl->bevpoints;
2466 bevp1 = bevp2 + (bl->nr - 1);
2467 bevp0 = bevp1 - 1;
2468
2469 copy_v3_v3(bevp0_tan, bevp0->tan);
2470
2471 nr = bl->nr;
2472 while (nr--) {
2473 /* make perpendicular, modify tan in place, is ok */
2474 float cross_tmp[3];
2475 const float zero[3] = {0, 0, 0};
2476
2477 cross_v3_v3v3(cross_tmp, bevp1->tan, bevp1->dir);
2478 normalize_v3(cross_tmp);
2479 tri_to_quat(bevp1->quat, zero, cross_tmp, bevp1->tan); /* XXX - could be faster */
2480
2481 /* bevp0 = bevp1; */ /* UNUSED */
2482 bevp1 = bevp2;
2483 bevp2++;
2484 }
2485 }
2486
make_bevel_list_3D(BevList * bl,int smooth_iter,int twist_mode)2487 static void make_bevel_list_3D(BevList *bl, int smooth_iter, int twist_mode)
2488 {
2489 switch (twist_mode) {
2490 case CU_TWIST_TANGENT:
2491 make_bevel_list_3D_tangent(bl);
2492 break;
2493 case CU_TWIST_MINIMUM:
2494 make_bevel_list_3D_minimum_twist(bl);
2495 break;
2496 default: /* CU_TWIST_Z_UP default, pre 2.49c */
2497 make_bevel_list_3D_zup(bl);
2498 break;
2499 }
2500
2501 if (smooth_iter) {
2502 bevel_list_smooth(bl, smooth_iter);
2503 }
2504
2505 bevel_list_apply_tilt(bl);
2506 }
2507
2508 /* only for 2 points */
make_bevel_list_segment_3D(BevList * bl)2509 static void make_bevel_list_segment_3D(BevList *bl)
2510 {
2511 float q[4];
2512
2513 BevPoint *bevp2 = bl->bevpoints;
2514 BevPoint *bevp1 = bevp2 + 1;
2515
2516 /* simple quat/dir */
2517 sub_v3_v3v3(bevp1->dir, bevp1->vec, bevp2->vec);
2518 normalize_v3(bevp1->dir);
2519
2520 vec_to_quat(bevp1->quat, bevp1->dir, 5, 1);
2521
2522 axis_angle_to_quat(q, bevp1->dir, bevp1->tilt);
2523 mul_qt_qtqt(bevp1->quat, q, bevp1->quat);
2524 normalize_qt(bevp1->quat);
2525 copy_v3_v3(bevp2->dir, bevp1->dir);
2526 copy_qt_qt(bevp2->quat, bevp1->quat);
2527 }
2528
2529 /* only for 2 points */
make_bevel_list_segment_2D(BevList * bl)2530 static void make_bevel_list_segment_2D(BevList *bl)
2531 {
2532 BevPoint *bevp2 = bl->bevpoints;
2533 BevPoint *bevp1 = bevp2 + 1;
2534
2535 const float x1 = bevp1->vec[0] - bevp2->vec[0];
2536 const float y1 = bevp1->vec[1] - bevp2->vec[1];
2537
2538 calc_bevel_sin_cos(x1, y1, -x1, -y1, &(bevp1->sina), &(bevp1->cosa));
2539 bevp2->sina = bevp1->sina;
2540 bevp2->cosa = bevp1->cosa;
2541
2542 /* fill in dir & quat */
2543 make_bevel_list_segment_3D(bl);
2544 }
2545
make_bevel_list_2D(BevList * bl)2546 static void make_bevel_list_2D(BevList *bl)
2547 {
2548 /* note: bevp->dir and bevp->quat are not needed for beveling but are
2549 * used when making a path from a 2D curve, therefore they need to be set - Campbell */
2550
2551 BevPoint *bevp0, *bevp1, *bevp2;
2552 int nr;
2553
2554 if (bl->poly != -1) {
2555 bevp2 = bl->bevpoints;
2556 bevp1 = bevp2 + (bl->nr - 1);
2557 bevp0 = bevp1 - 1;
2558 nr = bl->nr;
2559 }
2560 else {
2561 bevp0 = bl->bevpoints;
2562 bevp1 = bevp0 + 1;
2563 bevp2 = bevp1 + 1;
2564
2565 nr = bl->nr - 2;
2566 }
2567
2568 while (nr--) {
2569 const float x1 = bevp1->vec[0] - bevp0->vec[0];
2570 const float x2 = bevp1->vec[0] - bevp2->vec[0];
2571 const float y1 = bevp1->vec[1] - bevp0->vec[1];
2572 const float y2 = bevp1->vec[1] - bevp2->vec[1];
2573
2574 calc_bevel_sin_cos(x1, y1, x2, y2, &(bevp1->sina), &(bevp1->cosa));
2575
2576 /* from: make_bevel_list_3D_zup, could call but avoid a second loop.
2577 * no need for tricky tilt calculation as with 3D curves */
2578 bisect_v3_v3v3v3(bevp1->dir, bevp0->vec, bevp1->vec, bevp2->vec);
2579 vec_to_quat(bevp1->quat, bevp1->dir, 5, 1);
2580 /* done with inline make_bevel_list_3D_zup */
2581
2582 bevp0 = bevp1;
2583 bevp1 = bevp2;
2584 bevp2++;
2585 }
2586
2587 /* correct non-cyclic cases */
2588 if (bl->poly == -1) {
2589 BevPoint *bevp;
2590 float angle;
2591
2592 /* first */
2593 bevp = bl->bevpoints;
2594 angle = atan2f(bevp->dir[0], bevp->dir[1]) - (float)M_PI_2;
2595 bevp->sina = sinf(angle);
2596 bevp->cosa = cosf(angle);
2597 vec_to_quat(bevp->quat, bevp->dir, 5, 1);
2598
2599 /* last */
2600 bevp = bl->bevpoints;
2601 bevp += (bl->nr - 1);
2602 angle = atan2f(bevp->dir[0], bevp->dir[1]) - (float)M_PI_2;
2603 bevp->sina = sinf(angle);
2604 bevp->cosa = cosf(angle);
2605 vec_to_quat(bevp->quat, bevp->dir, 5, 1);
2606 }
2607 }
2608
bevlist_firstlast_direction_calc_from_bpoint(Nurb * nu,BevList * bl)2609 static void bevlist_firstlast_direction_calc_from_bpoint(Nurb *nu, BevList *bl)
2610 {
2611 if (nu->pntsu > 1) {
2612 BPoint *first_bp = nu->bp, *last_bp = nu->bp + (nu->pntsu - 1);
2613 BevPoint *first_bevp, *last_bevp;
2614
2615 first_bevp = bl->bevpoints;
2616 last_bevp = first_bevp + (bl->nr - 1);
2617
2618 sub_v3_v3v3(first_bevp->dir, (first_bp + 1)->vec, first_bp->vec);
2619 normalize_v3(first_bevp->dir);
2620
2621 sub_v3_v3v3(last_bevp->dir, last_bp->vec, (last_bp - 1)->vec);
2622 normalize_v3(last_bevp->dir);
2623 }
2624 }
2625
BKE_curve_bevelList_free(ListBase * bev)2626 void BKE_curve_bevelList_free(ListBase *bev)
2627 {
2628 BevList *bl, *blnext;
2629 for (bl = bev->first; bl != NULL; bl = blnext) {
2630 blnext = bl->next;
2631 if (bl->seglen != NULL) {
2632 MEM_freeN(bl->seglen);
2633 }
2634 if (bl->segbevcount != NULL) {
2635 MEM_freeN(bl->segbevcount);
2636 }
2637 if (bl->bevpoints != NULL) {
2638 MEM_freeN(bl->bevpoints);
2639 }
2640 MEM_freeN(bl);
2641 }
2642
2643 BLI_listbase_clear(bev);
2644 }
2645
BKE_curve_bevelList_make(Object * ob,ListBase * nurbs,bool for_render)2646 void BKE_curve_bevelList_make(Object *ob, ListBase *nurbs, bool for_render)
2647 {
2648 /*
2649 * - convert all curves to polys, with indication of resol and flags for double-vertices
2650 * - possibly; do a smart vertice removal (in case Nurb)
2651 * - separate in individual blocks with BoundBox
2652 * - AutoHole detection
2653 */
2654
2655 /* this function needs an object, because of tflag and upflag */
2656 Curve *cu = ob->data;
2657 Nurb *nu;
2658 BezTriple *bezt, *prevbezt;
2659 BPoint *bp;
2660 BevList *bl, *blnew, *blnext;
2661 BevPoint *bevp2, *bevp1 = NULL, *bevp0;
2662 const float treshold = 0.00001f;
2663 float min, inp;
2664 float *seglen = NULL;
2665 struct BevelSort *sortdata, *sd, *sd1;
2666 int a, b, nr, poly, resolu = 0, len = 0, segcount;
2667 int *segbevcount;
2668 bool do_tilt, do_radius, do_weight;
2669 bool is_editmode = false;
2670 ListBase *bev;
2671
2672 /* segbevcount alsp requires seglen. */
2673 const bool need_seglen = ELEM(
2674 cu->bevfac1_mapping, CU_BEVFAC_MAP_SEGMENT, CU_BEVFAC_MAP_SPLINE) ||
2675 ELEM(cu->bevfac2_mapping, CU_BEVFAC_MAP_SEGMENT, CU_BEVFAC_MAP_SPLINE);
2676
2677 bev = &ob->runtime.curve_cache->bev;
2678
2679 #if 0
2680 /* do we need to calculate the radius for each point? */
2681 do_radius = (cu->bevobj || cu->taperobj || (cu->flag & CU_FRONT) || (cu->flag & CU_BACK)) ? 0 :
2682 1;
2683 #endif
2684
2685 /* STEP 1: MAKE POLYS */
2686
2687 BKE_curve_bevelList_free(&ob->runtime.curve_cache->bev);
2688 nu = nurbs->first;
2689 if (cu->editnurb && ob->type != OB_FONT) {
2690 is_editmode = 1;
2691 }
2692
2693 for (; nu; nu = nu->next) {
2694 if (nu->hide && is_editmode) {
2695 continue;
2696 }
2697
2698 /* check if we will calculate tilt data */
2699 do_tilt = CU_DO_TILT(cu, nu);
2700
2701 /* Normal display uses the radius, better just to calculate them. */
2702 do_radius = CU_DO_RADIUS(cu, nu);
2703
2704 do_weight = true;
2705
2706 /* check we are a single point? also check we are not a surface and that the orderu is sane,
2707 * enforced in the UI but can go wrong possibly */
2708 if (!BKE_nurb_check_valid_u(nu)) {
2709 bl = MEM_callocN(sizeof(BevList), "makeBevelList1");
2710 bl->bevpoints = MEM_calloc_arrayN(1, sizeof(BevPoint), "makeBevelPoints1");
2711 BLI_addtail(bev, bl);
2712 bl->nr = 0;
2713 bl->charidx = nu->charidx;
2714 }
2715 else {
2716 BevPoint *bevp;
2717
2718 if (for_render && cu->resolu_ren != 0) {
2719 resolu = cu->resolu_ren;
2720 }
2721 else {
2722 resolu = nu->resolu;
2723 }
2724
2725 segcount = SEGMENTSU(nu);
2726
2727 if (nu->type == CU_POLY) {
2728 len = nu->pntsu;
2729 bl = MEM_callocN(sizeof(BevList), "makeBevelList2");
2730 bl->bevpoints = MEM_calloc_arrayN(len, sizeof(BevPoint), "makeBevelPoints2");
2731 if (need_seglen && (nu->flagu & CU_NURB_CYCLIC) == 0) {
2732 bl->seglen = MEM_malloc_arrayN(segcount, sizeof(float), "makeBevelList2_seglen");
2733 bl->segbevcount = MEM_malloc_arrayN(segcount, sizeof(int), "makeBevelList2_segbevcount");
2734 }
2735 BLI_addtail(bev, bl);
2736
2737 bl->poly = (nu->flagu & CU_NURB_CYCLIC) ? 0 : -1;
2738 bl->nr = len;
2739 bl->dupe_nr = 0;
2740 bl->charidx = nu->charidx;
2741 bevp = bl->bevpoints;
2742 bevp->offset = 0;
2743 bp = nu->bp;
2744 seglen = bl->seglen;
2745 segbevcount = bl->segbevcount;
2746
2747 while (len--) {
2748 copy_v3_v3(bevp->vec, bp->vec);
2749 bevp->tilt = bp->tilt;
2750 bevp->radius = bp->radius;
2751 bevp->weight = bp->weight;
2752 bevp->split_tag = true;
2753 bp++;
2754 if (seglen != NULL && len != 0) {
2755 *seglen = len_v3v3(bevp->vec, bp->vec);
2756 bevp++;
2757 bevp->offset = *seglen;
2758 if (*seglen > treshold) {
2759 *segbevcount = 1;
2760 }
2761 else {
2762 *segbevcount = 0;
2763 }
2764 seglen++;
2765 segbevcount++;
2766 }
2767 else {
2768 bevp++;
2769 }
2770 }
2771
2772 if ((nu->flagu & CU_NURB_CYCLIC) == 0) {
2773 bevlist_firstlast_direction_calc_from_bpoint(nu, bl);
2774 }
2775 }
2776 else if (nu->type == CU_BEZIER) {
2777 /* in case last point is not cyclic */
2778 len = segcount * resolu + 1;
2779
2780 bl = MEM_callocN(sizeof(BevList), "makeBevelBPoints");
2781 bl->bevpoints = MEM_calloc_arrayN(len, sizeof(BevPoint), "makeBevelBPointsPoints");
2782 if (need_seglen && (nu->flagu & CU_NURB_CYCLIC) == 0) {
2783 bl->seglen = MEM_malloc_arrayN(segcount, sizeof(float), "makeBevelBPoints_seglen");
2784 bl->segbevcount = MEM_malloc_arrayN(
2785 segcount, sizeof(int), "makeBevelBPoints_segbevcount");
2786 }
2787 BLI_addtail(bev, bl);
2788
2789 bl->poly = (nu->flagu & CU_NURB_CYCLIC) ? 0 : -1;
2790 bl->charidx = nu->charidx;
2791
2792 bevp = bl->bevpoints;
2793 seglen = bl->seglen;
2794 segbevcount = bl->segbevcount;
2795
2796 bevp->offset = 0;
2797 if (seglen != NULL) {
2798 *seglen = 0;
2799 *segbevcount = 0;
2800 }
2801
2802 a = nu->pntsu - 1;
2803 bezt = nu->bezt;
2804 if (nu->flagu & CU_NURB_CYCLIC) {
2805 a++;
2806 prevbezt = nu->bezt + (nu->pntsu - 1);
2807 }
2808 else {
2809 prevbezt = bezt;
2810 bezt++;
2811 }
2812
2813 sub_v3_v3v3(bevp->dir, prevbezt->vec[2], prevbezt->vec[1]);
2814 normalize_v3(bevp->dir);
2815
2816 BLI_assert(segcount >= a);
2817
2818 while (a--) {
2819 if (prevbezt->h2 == HD_VECT && bezt->h1 == HD_VECT) {
2820
2821 copy_v3_v3(bevp->vec, prevbezt->vec[1]);
2822 bevp->tilt = prevbezt->tilt;
2823 bevp->radius = prevbezt->radius;
2824 bevp->weight = prevbezt->weight;
2825 bevp->split_tag = true;
2826 bevp->dupe_tag = false;
2827 bevp++;
2828 bl->nr++;
2829 bl->dupe_nr = 1;
2830 if (seglen != NULL) {
2831 *seglen = len_v3v3(prevbezt->vec[1], bezt->vec[1]);
2832 bevp->offset = *seglen;
2833 seglen++;
2834 /* match segbevcount to the cleaned up bevel lists (see STEP 2) */
2835 if (bevp->offset > treshold) {
2836 *segbevcount = 1;
2837 }
2838 segbevcount++;
2839 }
2840 }
2841 else {
2842 /* always do all three, to prevent data hanging around */
2843 int j;
2844
2845 /* BevPoint must stay aligned to 4 so sizeof(BevPoint)/sizeof(float) works */
2846 for (j = 0; j < 3; j++) {
2847 BKE_curve_forward_diff_bezier(prevbezt->vec[1][j],
2848 prevbezt->vec[2][j],
2849 bezt->vec[0][j],
2850 bezt->vec[1][j],
2851 &(bevp->vec[j]),
2852 resolu,
2853 sizeof(BevPoint));
2854 }
2855
2856 /* if both arrays are NULL do nothiong */
2857 tilt_bezpart(prevbezt,
2858 bezt,
2859 nu,
2860 do_tilt ? &bevp->tilt : NULL,
2861 do_radius ? &bevp->radius : NULL,
2862 do_weight ? &bevp->weight : NULL,
2863 resolu,
2864 sizeof(BevPoint));
2865
2866 if (cu->twist_mode == CU_TWIST_TANGENT) {
2867 forward_diff_bezier_cotangent(prevbezt->vec[1],
2868 prevbezt->vec[2],
2869 bezt->vec[0],
2870 bezt->vec[1],
2871 bevp->tan,
2872 resolu,
2873 sizeof(BevPoint));
2874 }
2875
2876 /* indicate with handlecodes double points */
2877 if (prevbezt->h1 == prevbezt->h2) {
2878 if (prevbezt->h1 == 0 || prevbezt->h1 == HD_VECT) {
2879 bevp->split_tag = true;
2880 }
2881 }
2882 else {
2883 if (prevbezt->h1 == 0 || prevbezt->h1 == HD_VECT) {
2884 bevp->split_tag = true;
2885 }
2886 else if (prevbezt->h2 == 0 || prevbezt->h2 == HD_VECT) {
2887 bevp->split_tag = true;
2888 }
2889 }
2890
2891 /* seglen */
2892 if (seglen != NULL) {
2893 *seglen = 0;
2894 *segbevcount = 0;
2895 for (j = 0; j < resolu; j++) {
2896 bevp0 = bevp;
2897 bevp++;
2898 bevp->offset = len_v3v3(bevp0->vec, bevp->vec);
2899 /* match seglen and segbevcount to the cleaned up bevel lists (see STEP 2) */
2900 if (bevp->offset > treshold) {
2901 *seglen += bevp->offset;
2902 *segbevcount += 1;
2903 }
2904 }
2905 seglen++;
2906 segbevcount++;
2907 }
2908 else {
2909 bevp += resolu;
2910 }
2911 bl->nr += resolu;
2912 }
2913 prevbezt = bezt;
2914 bezt++;
2915 }
2916
2917 if ((nu->flagu & CU_NURB_CYCLIC) == 0) { /* not cyclic: endpoint */
2918 copy_v3_v3(bevp->vec, prevbezt->vec[1]);
2919 bevp->tilt = prevbezt->tilt;
2920 bevp->radius = prevbezt->radius;
2921 bevp->weight = prevbezt->weight;
2922
2923 sub_v3_v3v3(bevp->dir, prevbezt->vec[1], prevbezt->vec[0]);
2924 normalize_v3(bevp->dir);
2925
2926 bl->nr++;
2927 }
2928 }
2929 else if (nu->type == CU_NURBS) {
2930 if (nu->pntsv == 1) {
2931 len = (resolu * segcount);
2932
2933 bl = MEM_callocN(sizeof(BevList), "makeBevelList3");
2934 bl->bevpoints = MEM_calloc_arrayN(len, sizeof(BevPoint), "makeBevelPoints3");
2935 if (need_seglen && (nu->flagu & CU_NURB_CYCLIC) == 0) {
2936 bl->seglen = MEM_malloc_arrayN(segcount, sizeof(float), "makeBevelList3_seglen");
2937 bl->segbevcount = MEM_malloc_arrayN(
2938 segcount, sizeof(int), "makeBevelList3_segbevcount");
2939 }
2940 BLI_addtail(bev, bl);
2941 bl->nr = len;
2942 bl->dupe_nr = 0;
2943 bl->poly = (nu->flagu & CU_NURB_CYCLIC) ? 0 : -1;
2944 bl->charidx = nu->charidx;
2945
2946 bevp = bl->bevpoints;
2947 seglen = bl->seglen;
2948 segbevcount = bl->segbevcount;
2949
2950 BKE_nurb_makeCurve(nu,
2951 &bevp->vec[0],
2952 do_tilt ? &bevp->tilt : NULL,
2953 do_radius ? &bevp->radius : NULL,
2954 do_weight ? &bevp->weight : NULL,
2955 resolu,
2956 sizeof(BevPoint));
2957
2958 /* match seglen and segbevcount to the cleaned up bevel lists (see STEP 2) */
2959 if (seglen != NULL) {
2960 nr = segcount;
2961 bevp0 = bevp;
2962 bevp++;
2963 while (nr) {
2964 int j;
2965 *seglen = 0;
2966 *segbevcount = 0;
2967 /* We keep last bevel segment zero-length. */
2968 for (j = 0; j < ((nr == 1) ? (resolu - 1) : resolu); j++) {
2969 bevp->offset = len_v3v3(bevp0->vec, bevp->vec);
2970 if (bevp->offset > treshold) {
2971 *seglen += bevp->offset;
2972 *segbevcount += 1;
2973 }
2974 bevp0 = bevp;
2975 bevp++;
2976 }
2977 seglen++;
2978 segbevcount++;
2979 nr--;
2980 }
2981 }
2982
2983 if ((nu->flagu & CU_NURB_CYCLIC) == 0) {
2984 bevlist_firstlast_direction_calc_from_bpoint(nu, bl);
2985 }
2986 }
2987 }
2988 }
2989 }
2990
2991 /* STEP 2: DOUBLE POINTS AND AUTOMATIC RESOLUTION, REDUCE DATABLOCKS */
2992 bl = bev->first;
2993 while (bl) {
2994 if (bl->nr) { /* null bevel items come from single points */
2995 /* Scale the threshold so high resolution shapes don't get over reduced, see: T49850. */
2996 const float threshold_resolu = 0.00001f / resolu;
2997 bool is_cyclic = bl->poly != -1;
2998 nr = bl->nr;
2999 if (is_cyclic) {
3000 bevp1 = bl->bevpoints;
3001 bevp0 = bevp1 + (nr - 1);
3002 }
3003 else {
3004 bevp0 = bl->bevpoints;
3005 bevp0->offset = 0;
3006 bevp1 = bevp0 + 1;
3007 }
3008 nr--;
3009 while (nr--) {
3010 if (seglen != NULL) {
3011 if (fabsf(bevp1->offset) < treshold) {
3012 bevp0->dupe_tag = true;
3013 bl->dupe_nr++;
3014 }
3015 }
3016 else {
3017 if (compare_v3v3(bevp0->vec, bevp1->vec, threshold_resolu)) {
3018 bevp0->dupe_tag = true;
3019 bl->dupe_nr++;
3020 }
3021 }
3022 bevp0 = bevp1;
3023 bevp1++;
3024 }
3025 }
3026 bl = bl->next;
3027 }
3028 bl = bev->first;
3029 while (bl) {
3030 blnext = bl->next;
3031 if (bl->nr && bl->dupe_nr) {
3032 nr = bl->nr - bl->dupe_nr + 1; /* +1 because vectorbezier sets flag too */
3033 blnew = MEM_mallocN(sizeof(BevList), "makeBevelList4");
3034 memcpy(blnew, bl, sizeof(BevList));
3035 blnew->bevpoints = MEM_calloc_arrayN(nr, sizeof(BevPoint), "makeBevelPoints4");
3036 if (!blnew->bevpoints) {
3037 MEM_freeN(blnew);
3038 break;
3039 }
3040 blnew->segbevcount = bl->segbevcount;
3041 blnew->seglen = bl->seglen;
3042 blnew->nr = 0;
3043 BLI_remlink(bev, bl);
3044 BLI_insertlinkbefore(bev, blnext, blnew); /* to make sure bevlijst is tuned with nurblist */
3045 bevp0 = bl->bevpoints;
3046 bevp1 = blnew->bevpoints;
3047 nr = bl->nr;
3048 while (nr--) {
3049 if (bevp0->dupe_tag == 0) {
3050 memcpy(bevp1, bevp0, sizeof(BevPoint));
3051 bevp1++;
3052 blnew->nr++;
3053 }
3054 bevp0++;
3055 }
3056 if (bl->bevpoints != NULL) {
3057 MEM_freeN(bl->bevpoints);
3058 }
3059 MEM_freeN(bl);
3060 blnew->dupe_nr = 0;
3061 }
3062 bl = blnext;
3063 }
3064
3065 /* STEP 3: POLYS COUNT AND AUTOHOLE */
3066 bl = bev->first;
3067 poly = 0;
3068 while (bl) {
3069 if (bl->nr && bl->poly >= 0) {
3070 poly++;
3071 bl->poly = poly;
3072 bl->hole = 0;
3073 }
3074 bl = bl->next;
3075 }
3076
3077 /* find extreme left points, also test (turning) direction */
3078 if (poly > 0) {
3079 sd = sortdata = MEM_malloc_arrayN(poly, sizeof(struct BevelSort), "makeBevelList5");
3080 bl = bev->first;
3081 while (bl) {
3082 if (bl->poly > 0) {
3083 BevPoint *bevp;
3084
3085 bevp = bl->bevpoints;
3086 bevp1 = bl->bevpoints;
3087 min = bevp1->vec[0];
3088 nr = bl->nr;
3089 while (nr--) {
3090 if (min > bevp->vec[0]) {
3091 min = bevp->vec[0];
3092 bevp1 = bevp;
3093 }
3094 bevp++;
3095 }
3096 sd->bl = bl;
3097 sd->left = min;
3098
3099 bevp = bl->bevpoints;
3100 if (bevp1 == bevp) {
3101 bevp0 = bevp + (bl->nr - 1);
3102 }
3103 else {
3104 bevp0 = bevp1 - 1;
3105 }
3106 bevp = bevp + (bl->nr - 1);
3107 if (bevp1 == bevp) {
3108 bevp2 = bl->bevpoints;
3109 }
3110 else {
3111 bevp2 = bevp1 + 1;
3112 }
3113
3114 inp = ((bevp1->vec[0] - bevp0->vec[0]) * (bevp0->vec[1] - bevp2->vec[1]) +
3115 (bevp0->vec[1] - bevp1->vec[1]) * (bevp0->vec[0] - bevp2->vec[0]));
3116
3117 if (inp > 0.0f) {
3118 sd->dir = 1;
3119 }
3120 else {
3121 sd->dir = 0;
3122 }
3123
3124 sd++;
3125 }
3126
3127 bl = bl->next;
3128 }
3129 qsort(sortdata, poly, sizeof(struct BevelSort), vergxcobev);
3130
3131 sd = sortdata + 1;
3132 for (a = 1; a < poly; a++, sd++) {
3133 bl = sd->bl; /* is bl a hole? */
3134 sd1 = sortdata + (a - 1);
3135 for (b = a - 1; b >= 0; b--, sd1--) { /* all polys to the left */
3136 if (sd1->bl->charidx == bl->charidx) { /* for text, only check matching char */
3137 if (bevelinside(sd1->bl, bl)) {
3138 bl->hole = 1 - sd1->bl->hole;
3139 break;
3140 }
3141 }
3142 }
3143 }
3144
3145 /* turning direction */
3146 if ((cu->flag & CU_3D) == 0) {
3147 sd = sortdata;
3148 for (a = 0; a < poly; a++, sd++) {
3149 if (sd->bl->hole == sd->dir) {
3150 bl = sd->bl;
3151 bevp1 = bl->bevpoints;
3152 bevp2 = bevp1 + (bl->nr - 1);
3153 nr = bl->nr / 2;
3154 while (nr--) {
3155 SWAP(BevPoint, *bevp1, *bevp2);
3156 bevp1++;
3157 bevp2--;
3158 }
3159 }
3160 }
3161 }
3162 MEM_freeN(sortdata);
3163 }
3164
3165 /* STEP 4: 2D-COSINES or 3D ORIENTATION */
3166 if ((cu->flag & CU_3D) == 0) {
3167 /* 2D Curves */
3168 for (bl = bev->first; bl; bl = bl->next) {
3169 if (bl->nr < 2) {
3170 BevPoint *bevp = bl->bevpoints;
3171 unit_qt(bevp->quat);
3172 }
3173 else if (bl->nr == 2) { /* 2 pnt, treat separate */
3174 make_bevel_list_segment_2D(bl);
3175 }
3176 else {
3177 make_bevel_list_2D(bl);
3178 }
3179 }
3180 }
3181 else {
3182 /* 3D Curves */
3183 for (bl = bev->first; bl; bl = bl->next) {
3184 if (bl->nr < 2) {
3185 BevPoint *bevp = bl->bevpoints;
3186 unit_qt(bevp->quat);
3187 }
3188 else if (bl->nr == 2) { /* 2 pnt, treat separate */
3189 make_bevel_list_segment_3D(bl);
3190 }
3191 else {
3192 make_bevel_list_3D(bl, (int)(resolu * cu->twist_smooth), cu->twist_mode);
3193 }
3194 }
3195 }
3196 }
3197
3198 /* ****************** HANDLES ************** */
3199
calchandleNurb_intern(BezTriple * bezt,const BezTriple * prev,const BezTriple * next,eBezTriple_Flag handle_sel_flag,bool is_fcurve,bool skip_align,char fcurve_smoothing)3200 static void calchandleNurb_intern(BezTriple *bezt,
3201 const BezTriple *prev,
3202 const BezTriple *next,
3203 eBezTriple_Flag handle_sel_flag,
3204 bool is_fcurve,
3205 bool skip_align,
3206 char fcurve_smoothing)
3207 {
3208 /* defines to avoid confusion */
3209 #define p2_h1 ((p2)-3)
3210 #define p2_h2 ((p2) + 3)
3211
3212 const float *p1, *p3;
3213 float *p2;
3214 float pt[3];
3215 float dvec_a[3], dvec_b[3];
3216 float len, len_a, len_b;
3217 float len_ratio;
3218 const float eps = 1e-5;
3219
3220 /* assume normal handle until we check */
3221 bezt->f5 = HD_AUTOTYPE_NORMAL;
3222
3223 if (bezt->h1 == 0 && bezt->h2 == 0) {
3224 return;
3225 }
3226
3227 p2 = bezt->vec[1];
3228
3229 if (prev == NULL) {
3230 p3 = next->vec[1];
3231 pt[0] = 2.0f * p2[0] - p3[0];
3232 pt[1] = 2.0f * p2[1] - p3[1];
3233 pt[2] = 2.0f * p2[2] - p3[2];
3234 p1 = pt;
3235 }
3236 else {
3237 p1 = prev->vec[1];
3238 }
3239
3240 if (next == NULL) {
3241 pt[0] = 2.0f * p2[0] - p1[0];
3242 pt[1] = 2.0f * p2[1] - p1[1];
3243 pt[2] = 2.0f * p2[2] - p1[2];
3244 p3 = pt;
3245 }
3246 else {
3247 p3 = next->vec[1];
3248 }
3249
3250 sub_v3_v3v3(dvec_a, p2, p1);
3251 sub_v3_v3v3(dvec_b, p3, p2);
3252
3253 if (is_fcurve) {
3254 len_a = dvec_a[0];
3255 len_b = dvec_b[0];
3256 }
3257 else {
3258 len_a = len_v3(dvec_a);
3259 len_b = len_v3(dvec_b);
3260 }
3261
3262 if (len_a == 0.0f) {
3263 len_a = 1.0f;
3264 }
3265 if (len_b == 0.0f) {
3266 len_b = 1.0f;
3267 }
3268
3269 len_ratio = len_a / len_b;
3270
3271 if (ELEM(bezt->h1, HD_AUTO, HD_AUTO_ANIM) || ELEM(bezt->h2, HD_AUTO, HD_AUTO_ANIM)) { /* auto */
3272 float tvec[3];
3273 tvec[0] = dvec_b[0] / len_b + dvec_a[0] / len_a;
3274 tvec[1] = dvec_b[1] / len_b + dvec_a[1] / len_a;
3275 tvec[2] = dvec_b[2] / len_b + dvec_a[2] / len_a;
3276
3277 if (is_fcurve) {
3278 if (fcurve_smoothing != FCURVE_SMOOTH_NONE) {
3279 /* force the horizontal handle size to be 1/3 of the key interval so that
3280 * the X component of the parametric bezier curve is a linear spline */
3281 len = 6.0f / 2.5614f;
3282 }
3283 else {
3284 len = tvec[0];
3285 }
3286 }
3287 else {
3288 len = len_v3(tvec);
3289 }
3290 len *= 2.5614f;
3291
3292 if (len != 0.0f) {
3293 /* only for fcurves */
3294 bool leftviolate = false, rightviolate = false;
3295
3296 if (!is_fcurve || fcurve_smoothing == FCURVE_SMOOTH_NONE) {
3297 if (len_a > 5.0f * len_b) {
3298 len_a = 5.0f * len_b;
3299 }
3300 if (len_b > 5.0f * len_a) {
3301 len_b = 5.0f * len_a;
3302 }
3303 }
3304
3305 if (ELEM(bezt->h1, HD_AUTO, HD_AUTO_ANIM)) {
3306 len_a /= len;
3307 madd_v3_v3v3fl(p2_h1, p2, tvec, -len_a);
3308
3309 if ((bezt->h1 == HD_AUTO_ANIM) && next && prev) { /* keep horizontal if extrema */
3310 float ydiff1 = prev->vec[1][1] - bezt->vec[1][1];
3311 float ydiff2 = next->vec[1][1] - bezt->vec[1][1];
3312 if ((ydiff1 <= 0.0f && ydiff2 <= 0.0f) || (ydiff1 >= 0.0f && ydiff2 >= 0.0f)) {
3313 bezt->vec[0][1] = bezt->vec[1][1];
3314 bezt->f5 = HD_AUTOTYPE_SPECIAL;
3315 }
3316 else { /* handles should not be beyond y coord of two others */
3317 if (ydiff1 <= 0.0f) {
3318 if (prev->vec[1][1] > bezt->vec[0][1]) {
3319 bezt->vec[0][1] = prev->vec[1][1];
3320 leftviolate = 1;
3321 }
3322 }
3323 else {
3324 if (prev->vec[1][1] < bezt->vec[0][1]) {
3325 bezt->vec[0][1] = prev->vec[1][1];
3326 leftviolate = 1;
3327 }
3328 }
3329 }
3330 }
3331 }
3332 if (ELEM(bezt->h2, HD_AUTO, HD_AUTO_ANIM)) {
3333 len_b /= len;
3334 madd_v3_v3v3fl(p2_h2, p2, tvec, len_b);
3335
3336 if ((bezt->h2 == HD_AUTO_ANIM) && next && prev) { /* keep horizontal if extrema */
3337 float ydiff1 = prev->vec[1][1] - bezt->vec[1][1];
3338 float ydiff2 = next->vec[1][1] - bezt->vec[1][1];
3339 if ((ydiff1 <= 0.0f && ydiff2 <= 0.0f) || (ydiff1 >= 0.0f && ydiff2 >= 0.0f)) {
3340 bezt->vec[2][1] = bezt->vec[1][1];
3341 bezt->f5 = HD_AUTOTYPE_SPECIAL;
3342 }
3343 else { /* handles should not be beyond y coord of two others */
3344 if (ydiff1 <= 0.0f) {
3345 if (next->vec[1][1] < bezt->vec[2][1]) {
3346 bezt->vec[2][1] = next->vec[1][1];
3347 rightviolate = 1;
3348 }
3349 }
3350 else {
3351 if (next->vec[1][1] > bezt->vec[2][1]) {
3352 bezt->vec[2][1] = next->vec[1][1];
3353 rightviolate = 1;
3354 }
3355 }
3356 }
3357 }
3358 }
3359 if (leftviolate || rightviolate) { /* align left handle */
3360 BLI_assert(is_fcurve);
3361 /* simple 2d calculation */
3362 float h1_x = p2_h1[0] - p2[0];
3363 float h2_x = p2[0] - p2_h2[0];
3364
3365 if (leftviolate) {
3366 p2_h2[1] = p2[1] + ((p2[1] - p2_h1[1]) / h1_x) * h2_x;
3367 }
3368 else {
3369 p2_h1[1] = p2[1] + ((p2[1] - p2_h2[1]) / h2_x) * h1_x;
3370 }
3371 }
3372 }
3373 }
3374
3375 if (bezt->h1 == HD_VECT) { /* vector */
3376 madd_v3_v3v3fl(p2_h1, p2, dvec_a, -1.0f / 3.0f);
3377 }
3378 if (bezt->h2 == HD_VECT) {
3379 madd_v3_v3v3fl(p2_h2, p2, dvec_b, 1.0f / 3.0f);
3380 }
3381
3382 if (skip_align ||
3383 /* when one handle is free, alignming makes no sense, see: T35952 */
3384 (ELEM(HD_FREE, bezt->h1, bezt->h2)) ||
3385 /* also when no handles are aligned, skip this step */
3386 (!ELEM(HD_ALIGN, bezt->h1, bezt->h2) && !ELEM(HD_ALIGN_DOUBLESIDE, bezt->h1, bezt->h2))) {
3387 /* handles need to be updated during animation and applying stuff like hooks,
3388 * but in such situations it's quite difficult to distinguish in which order
3389 * align handles should be aligned so skip them for now */
3390 return;
3391 }
3392
3393 len_a = len_v3v3(p2, p2_h1);
3394 len_b = len_v3v3(p2, p2_h2);
3395
3396 if (len_a == 0.0f) {
3397 len_a = 1.0f;
3398 }
3399 if (len_b == 0.0f) {
3400 len_b = 1.0f;
3401 }
3402
3403 len_ratio = len_a / len_b;
3404
3405 if (bezt->f1 & handle_sel_flag) { /* order of calculation */
3406 if (ELEM(bezt->h2, HD_ALIGN, HD_ALIGN_DOUBLESIDE)) { /* aligned */
3407 if (len_a > eps) {
3408 len = 1.0f / len_ratio;
3409 p2_h2[0] = p2[0] + len * (p2[0] - p2_h1[0]);
3410 p2_h2[1] = p2[1] + len * (p2[1] - p2_h1[1]);
3411 p2_h2[2] = p2[2] + len * (p2[2] - p2_h1[2]);
3412 }
3413 }
3414 if (ELEM(bezt->h1, HD_ALIGN, HD_ALIGN_DOUBLESIDE)) {
3415 if (len_b > eps) {
3416 len = len_ratio;
3417 p2_h1[0] = p2[0] + len * (p2[0] - p2_h2[0]);
3418 p2_h1[1] = p2[1] + len * (p2[1] - p2_h2[1]);
3419 p2_h1[2] = p2[2] + len * (p2[2] - p2_h2[2]);
3420 }
3421 }
3422 }
3423 else {
3424 if (ELEM(bezt->h1, HD_ALIGN, HD_ALIGN_DOUBLESIDE)) {
3425 if (len_b > eps) {
3426 len = len_ratio;
3427 p2_h1[0] = p2[0] + len * (p2[0] - p2_h2[0]);
3428 p2_h1[1] = p2[1] + len * (p2[1] - p2_h2[1]);
3429 p2_h1[2] = p2[2] + len * (p2[2] - p2_h2[2]);
3430 }
3431 }
3432 if (ELEM(bezt->h2, HD_ALIGN, HD_ALIGN_DOUBLESIDE)) { /* aligned */
3433 if (len_a > eps) {
3434 len = 1.0f / len_ratio;
3435 p2_h2[0] = p2[0] + len * (p2[0] - p2_h1[0]);
3436 p2_h2[1] = p2[1] + len * (p2[1] - p2_h1[1]);
3437 p2_h2[2] = p2[2] + len * (p2[2] - p2_h1[2]);
3438 }
3439 }
3440 }
3441
3442 #undef p2_h1
3443 #undef p2_h2
3444 }
3445
calchandlesNurb_intern(Nurb * nu,eBezTriple_Flag handle_sel_flag,bool skip_align)3446 static void calchandlesNurb_intern(Nurb *nu, eBezTriple_Flag handle_sel_flag, bool skip_align)
3447 {
3448 BezTriple *bezt, *prev, *next;
3449 int a;
3450
3451 if (nu->type != CU_BEZIER) {
3452 return;
3453 }
3454 if (nu->pntsu < 2) {
3455 return;
3456 }
3457
3458 a = nu->pntsu;
3459 bezt = nu->bezt;
3460 if (nu->flagu & CU_NURB_CYCLIC) {
3461 prev = bezt + (a - 1);
3462 }
3463 else {
3464 prev = NULL;
3465 }
3466 next = bezt + 1;
3467
3468 while (a--) {
3469 calchandleNurb_intern(bezt, prev, next, handle_sel_flag, 0, skip_align, 0);
3470 prev = bezt;
3471 if (a == 1) {
3472 if (nu->flagu & CU_NURB_CYCLIC) {
3473 next = nu->bezt;
3474 }
3475 else {
3476 next = NULL;
3477 }
3478 }
3479 else {
3480 next++;
3481 }
3482
3483 bezt++;
3484 }
3485 }
3486
3487 /**
3488 * A utility function for allocating a number of arrays of the same length
3489 * with easy error checking and de-allocation, and an easy way to add or remove
3490 * arrays that are processed in this way when changing code.
3491 *
3492 * floats, chars: NULL-terminated arrays of pointers to array pointers that need to be allocated.
3493 *
3494 * Returns: pointer to the buffer that contains all of the arrays.
3495 */
allocate_arrays(int count,float *** floats,char *** chars,const char * name)3496 static void *allocate_arrays(int count, float ***floats, char ***chars, const char *name)
3497 {
3498 size_t num_floats = 0, num_chars = 0;
3499
3500 while (floats && floats[num_floats]) {
3501 num_floats++;
3502 }
3503
3504 while (chars && chars[num_chars]) {
3505 num_chars++;
3506 }
3507
3508 void *buffer = (float *)MEM_malloc_arrayN(count, (sizeof(float) * num_floats + num_chars), name);
3509
3510 if (!buffer) {
3511 return NULL;
3512 }
3513
3514 float *fptr = buffer;
3515
3516 for (int i = 0; i < num_floats; i++, fptr += count) {
3517 *floats[i] = fptr;
3518 }
3519
3520 char *cptr = (char *)fptr;
3521
3522 for (int i = 0; i < num_chars; i++, cptr += count) {
3523 *chars[i] = cptr;
3524 }
3525
3526 return buffer;
3527 }
3528
free_arrays(void * buffer)3529 static void free_arrays(void *buffer)
3530 {
3531 MEM_freeN(buffer);
3532 }
3533
3534 /* computes in which direction to change h[i] to satisfy conditions better */
bezier_relax_direction(const float * a,const float * b,const float * c,const float * d,const float * h,int i,int count)3535 static float bezier_relax_direction(const float *a,
3536 const float *b,
3537 const float *c,
3538 const float *d,
3539 const float *h,
3540 int i,
3541 int count)
3542 {
3543 /* current deviation between sides of the equation */
3544 float state = a[i] * h[(i + count - 1) % count] + b[i] * h[i] + c[i] * h[(i + 1) % count] - d[i];
3545
3546 /* only the sign is meaningful */
3547 return -state * b[i];
3548 }
3549
bezier_lock_unknown(float * a,float * b,float * c,float * d,int i,float value)3550 static void bezier_lock_unknown(float *a, float *b, float *c, float *d, int i, float value)
3551 {
3552 a[i] = c[i] = 0.0f;
3553 b[i] = 1.0f;
3554 d[i] = value;
3555 }
3556
bezier_restore_equation(float * a,float * b,float * c,float * d,const float * a0,const float * b0,const float * c0,const float * d0,int i)3557 static void bezier_restore_equation(float *a,
3558 float *b,
3559 float *c,
3560 float *d,
3561 const float *a0,
3562 const float *b0,
3563 const float *c0,
3564 const float *d0,
3565 int i)
3566 {
3567 a[i] = a0[i];
3568 b[i] = b0[i];
3569 c[i] = c0[i];
3570 d[i] = d0[i];
3571 }
3572
tridiagonal_solve_with_limits(float * a,float * b,float * c,float * d,float * h,const float * hmin,const float * hmax,int solve_count)3573 static bool tridiagonal_solve_with_limits(float *a,
3574 float *b,
3575 float *c,
3576 float *d,
3577 float *h,
3578 const float *hmin,
3579 const float *hmax,
3580 int solve_count)
3581 {
3582 float *a0, *b0, *c0, *d0;
3583 float **arrays[] = {&a0, &b0, &c0, &d0, NULL};
3584 char *is_locked, *num_unlocks;
3585 char **flagarrays[] = {&is_locked, &num_unlocks, NULL};
3586
3587 void *tmps = allocate_arrays(solve_count, arrays, flagarrays, "tridiagonal_solve_with_limits");
3588 if (!tmps) {
3589 return false;
3590 }
3591
3592 memcpy(a0, a, sizeof(float) * solve_count);
3593 memcpy(b0, b, sizeof(float) * solve_count);
3594 memcpy(c0, c, sizeof(float) * solve_count);
3595 memcpy(d0, d, sizeof(float) * solve_count);
3596
3597 memset(is_locked, 0, solve_count);
3598 memset(num_unlocks, 0, solve_count);
3599
3600 bool overshoot, unlocked;
3601
3602 do {
3603 if (!BLI_tridiagonal_solve_cyclic(a, b, c, d, h, solve_count)) {
3604 free_arrays(tmps);
3605 return false;
3606 }
3607
3608 /* first check if any handles overshoot the limits, and lock them */
3609 bool all = false, locked = false;
3610
3611 overshoot = unlocked = false;
3612
3613 do {
3614 for (int i = 0; i < solve_count; i++) {
3615 if (h[i] >= hmin[i] && h[i] <= hmax[i]) {
3616 continue;
3617 }
3618
3619 overshoot = true;
3620
3621 float target = h[i] > hmax[i] ? hmax[i] : hmin[i];
3622
3623 /* heuristically only lock handles that go in the right direction if there are such ones */
3624 if (target != 0.0f || all) {
3625 /* mark item locked */
3626 is_locked[i] = 1;
3627
3628 bezier_lock_unknown(a, b, c, d, i, target);
3629 locked = true;
3630 }
3631 }
3632
3633 all = true;
3634 } while (overshoot && !locked);
3635
3636 /* If no handles overshot and were locked,
3637 * see if it may be a good idea to unlock some handles. */
3638 if (!locked) {
3639 for (int i = 0; i < solve_count; i++) {
3640 /* to definitely avoid infinite loops limit this to 2 times */
3641 if (!is_locked[i] || num_unlocks[i] >= 2) {
3642 continue;
3643 }
3644
3645 /* if the handle wants to move in allowable direction, release it */
3646 float relax = bezier_relax_direction(a0, b0, c0, d0, h, i, solve_count);
3647
3648 if ((relax > 0 && h[i] < hmax[i]) || (relax < 0 && h[i] > hmin[i])) {
3649 bezier_restore_equation(a, b, c, d, a0, b0, c0, d0, i);
3650
3651 is_locked[i] = 0;
3652 num_unlocks[i]++;
3653 unlocked = true;
3654 }
3655 }
3656 }
3657 } while (overshoot || unlocked);
3658
3659 free_arrays(tmps);
3660 return true;
3661 }
3662
3663 /* Keep ascii art. */
3664 /* clang-format off */
3665 /*
3666 * This function computes the handles of a series of auto bezier points
3667 * on the basis of 'no acceleration discontinuities' at the points.
3668 * The first and last bezier points are considered 'fixed' (their handles are not touched)
3669 * The result is the smoothest possible trajectory going through intermediate points.
3670 * The difficulty is that the handles depends on their neighbors.
3671 *
3672 * The exact solution is found by solving a tridiagonal matrix equation formed
3673 * by the continuity and boundary conditions. Although theoretically handle position
3674 * is affected by all other points of the curve segment, in practice the influence
3675 * decreases exponentially with distance.
3676 *
3677 * Note: this algorithm assumes that the handle horizontal size if always 1/3 of the
3678 * of the interval to the next point. This rule ensures linear interpolation of time.
3679 *
3680 * ^ height (co 1)
3681 * | yN
3682 * | yN-1 |
3683 * | y2 | |
3684 * | y1 | | |
3685 * | y0 | | | |
3686 * | | | | | |
3687 * | | | | | |
3688 * | | | | | |
3689 * |-------t1---------t2--------- ~ --------tN-------------------> time (co 0)
3690 * Mathematical basis:
3691 *
3692 * 1. Handle lengths on either side of each point are connected by a factor
3693 * ensuring continuity of the first derivative:
3694 *
3695 * l[i] = t[i+1]/t[i]
3696 *
3697 * 2. The tridiagonal system is formed by the following equation, which is derived
3698 * by differentiating the bezier curve and specifies second derivative continuity
3699 * at every point:
3700 *
3701 * l[i]^2 * h[i-1] + (2*l[i]+2) * h[i] + 1/l[i+1] * h[i+1] = (y[i]-y[i-1])*l[i]^2 + y[i+1]-y[i]
3702 *
3703 * 3. If this point is adjacent to a manually set handle with X size not equal to 1/3
3704 * of the horizontal interval, this equation becomes slightly more complex:
3705 *
3706 * l[i]^2 * h[i-1] + (3*(1-R[i-1])*l[i] + 3*(1-L[i+1])) * h[i] + 1/l[i+1] * h[i+1] = (y[i]-y[i-1])*l[i]^2 + y[i+1]-y[i]
3707 *
3708 * The difference between equations amounts to this, and it's obvious that when R[i-1]
3709 * and L[i+1] are both 1/3, it becomes zero:
3710 *
3711 * ( (1-3*R[i-1])*l[i] + (1-3*L[i+1]) ) * h[i]
3712 *
3713 * 4. The equations for zero acceleration border conditions are basically the above
3714 * equation with parts omitted, so the handle size correction also applies.
3715 */
3716 /* clang-format on */
3717
bezier_eq_continuous(float * a,float * b,float * c,float * d,const float * dy,const float * l,int i)3718 static void bezier_eq_continuous(
3719 float *a, float *b, float *c, float *d, const float *dy, const float *l, int i)
3720 {
3721 a[i] = l[i] * l[i];
3722 b[i] = 2.0f * (l[i] + 1);
3723 c[i] = 1.0f / l[i + 1];
3724 d[i] = dy[i] * l[i] * l[i] + dy[i + 1];
3725 }
3726
bezier_eq_noaccel_right(float * a,float * b,float * c,float * d,const float * dy,const float * l,int i)3727 static void bezier_eq_noaccel_right(
3728 float *a, float *b, float *c, float *d, const float *dy, const float *l, int i)
3729 {
3730 a[i] = 0.0f;
3731 b[i] = 2.0f;
3732 c[i] = 1.0f / l[i + 1];
3733 d[i] = dy[i + 1];
3734 }
3735
bezier_eq_noaccel_left(float * a,float * b,float * c,float * d,const float * dy,const float * l,int i)3736 static void bezier_eq_noaccel_left(
3737 float *a, float *b, float *c, float *d, const float *dy, const float *l, int i)
3738 {
3739 a[i] = l[i] * l[i];
3740 b[i] = 2.0f * l[i];
3741 c[i] = 0.0f;
3742 d[i] = dy[i] * l[i] * l[i];
3743 }
3744
3745 /* auto clamp prevents its own point going the wrong way, and adjacent handles overshooting */
bezier_clamp(float * hmax,float * hmin,int i,float dy,bool no_reverse,bool no_overshoot)3746 static void bezier_clamp(
3747 float *hmax, float *hmin, int i, float dy, bool no_reverse, bool no_overshoot)
3748 {
3749 if (dy > 0) {
3750 if (no_overshoot) {
3751 hmax[i] = min_ff(hmax[i], dy);
3752 }
3753 if (no_reverse) {
3754 hmin[i] = 0.0f;
3755 }
3756 }
3757 else if (dy < 0) {
3758 if (no_reverse) {
3759 hmax[i] = 0.0f;
3760 }
3761 if (no_overshoot) {
3762 hmin[i] = max_ff(hmin[i], dy);
3763 }
3764 }
3765 else if (no_reverse || no_overshoot) {
3766 hmax[i] = hmin[i] = 0.0f;
3767 }
3768 }
3769
3770 /* write changes to a bezier handle */
bezier_output_handle_inner(BezTriple * bezt,bool right,const float newval[3],bool endpoint)3771 static void bezier_output_handle_inner(BezTriple *bezt,
3772 bool right,
3773 const float newval[3],
3774 bool endpoint)
3775 {
3776 float tmp[3];
3777
3778 int idx = right ? 2 : 0;
3779 char hr = right ? bezt->h2 : bezt->h1;
3780 char hm = right ? bezt->h1 : bezt->h2;
3781
3782 /* only assign Auto/Vector handles */
3783 if (!ELEM(hr, HD_AUTO, HD_AUTO_ANIM, HD_VECT)) {
3784 return;
3785 }
3786
3787 copy_v3_v3(bezt->vec[idx], newval);
3788
3789 /* fix up the Align handle if any */
3790 if (ELEM(hm, HD_ALIGN, HD_ALIGN_DOUBLESIDE)) {
3791 float hlen = len_v3v3(bezt->vec[1], bezt->vec[2 - idx]);
3792 float h2len = len_v3v3(bezt->vec[1], bezt->vec[idx]);
3793
3794 sub_v3_v3v3(tmp, bezt->vec[1], bezt->vec[idx]);
3795 madd_v3_v3v3fl(bezt->vec[2 - idx], bezt->vec[1], tmp, hlen / h2len);
3796 }
3797 /* at end points of the curve, mirror handle to the other side */
3798 else if (endpoint && ELEM(hm, HD_AUTO, HD_AUTO_ANIM, HD_VECT)) {
3799 sub_v3_v3v3(tmp, bezt->vec[1], bezt->vec[idx]);
3800 add_v3_v3v3(bezt->vec[2 - idx], bezt->vec[1], tmp);
3801 }
3802 }
3803
bezier_output_handle(BezTriple * bezt,bool right,float dy,bool endpoint)3804 static void bezier_output_handle(BezTriple *bezt, bool right, float dy, bool endpoint)
3805 {
3806 float tmp[3];
3807
3808 copy_v3_v3(tmp, bezt->vec[right ? 2 : 0]);
3809
3810 tmp[1] = bezt->vec[1][1] + dy;
3811
3812 bezier_output_handle_inner(bezt, right, tmp, endpoint);
3813 }
3814
bezier_check_solve_end_handle(BezTriple * bezt,char htype,bool end)3815 static bool bezier_check_solve_end_handle(BezTriple *bezt, char htype, bool end)
3816 {
3817 return (htype == HD_VECT) ||
3818 (end && ELEM(htype, HD_AUTO, HD_AUTO_ANIM) && bezt->f5 == HD_AUTOTYPE_NORMAL);
3819 }
3820
bezier_calc_handle_adj(float hsize[2],float dx)3821 static float bezier_calc_handle_adj(float hsize[2], float dx)
3822 {
3823 /* if handles intersect in x direction, they are scaled to fit */
3824 float fac = dx / (hsize[0] + dx / 3.0f);
3825 if (fac < 1.0f) {
3826 mul_v2_fl(hsize, fac);
3827 }
3828 return 1.0f - 3.0f * hsize[0] / dx;
3829 }
3830
bezier_handle_calc_smooth_fcurve(BezTriple * bezt,int total,int start,int count,bool cycle)3831 static void bezier_handle_calc_smooth_fcurve(
3832 BezTriple *bezt, int total, int start, int count, bool cycle)
3833 {
3834 float *dx, *dy, *l, *a, *b, *c, *d, *h, *hmax, *hmin;
3835 float **arrays[] = {&dx, &dy, &l, &a, &b, &c, &d, &h, &hmax, &hmin, NULL};
3836
3837 int solve_count = count;
3838
3839 /* verify index ranges */
3840
3841 if (count < 2) {
3842 return;
3843 }
3844
3845 BLI_assert(start < total - 1 && count <= total);
3846 BLI_assert(start + count <= total || cycle);
3847
3848 bool full_cycle = (start == 0 && count == total && cycle);
3849
3850 BezTriple *bezt_first = &bezt[start];
3851 BezTriple *bezt_last =
3852 &bezt[(start + count > total) ? start + count - total : start + count - 1];
3853
3854 bool solve_first = bezier_check_solve_end_handle(bezt_first, bezt_first->h2, start == 0);
3855 bool solve_last = bezier_check_solve_end_handle(
3856 bezt_last, bezt_last->h1, start + count == total);
3857
3858 if (count == 2 && !full_cycle && solve_first == solve_last) {
3859 return;
3860 }
3861
3862 /* allocate all */
3863
3864 void *tmp_buffer = allocate_arrays(count, arrays, NULL, "bezier_calc_smooth_tmp");
3865 if (!tmp_buffer) {
3866 return;
3867 }
3868
3869 /* point locations */
3870
3871 dx[0] = dy[0] = NAN_FLT;
3872
3873 for (int i = 1, j = start + 1; i < count; i++, j++) {
3874 dx[i] = bezt[j].vec[1][0] - bezt[j - 1].vec[1][0];
3875 dy[i] = bezt[j].vec[1][1] - bezt[j - 1].vec[1][1];
3876
3877 /* when cyclic, jump from last point to first */
3878 if (cycle && j == total - 1) {
3879 j = 0;
3880 }
3881 }
3882
3883 /* ratio of x intervals */
3884
3885 l[0] = l[count - 1] = 1.0f;
3886
3887 for (int i = 1; i < count - 1; i++) {
3888 l[i] = dx[i + 1] / dx[i];
3889 }
3890
3891 /* compute handle clamp ranges */
3892
3893 bool clamped_prev = false, clamped_cur = ELEM(HD_AUTO_ANIM, bezt_first->h1, bezt_first->h2);
3894
3895 for (int i = 0; i < count; i++) {
3896 hmax[i] = FLT_MAX;
3897 hmin[i] = -FLT_MAX;
3898 }
3899
3900 for (int i = 1, j = start + 1; i < count; i++, j++) {
3901 clamped_prev = clamped_cur;
3902 clamped_cur = ELEM(HD_AUTO_ANIM, bezt[j].h1, bezt[j].h2);
3903
3904 if (cycle && j == total - 1) {
3905 j = 0;
3906 clamped_cur = clamped_cur || ELEM(HD_AUTO_ANIM, bezt[j].h1, bezt[j].h2);
3907 }
3908
3909 bezier_clamp(hmax, hmin, i - 1, dy[i], clamped_prev, clamped_prev);
3910 bezier_clamp(hmax, hmin, i, dy[i] * l[i], clamped_cur, clamped_cur);
3911 }
3912
3913 /* full cycle merges first and last points into continuous loop */
3914
3915 float first_handle_adj = 0.0f, last_handle_adj = 0.0f;
3916
3917 if (full_cycle) {
3918 /* reduce the number of unknowns by one */
3919 int i = solve_count = count - 1;
3920
3921 dx[0] = dx[i];
3922 dy[0] = dy[i];
3923
3924 l[0] = l[i] = dx[1] / dx[0];
3925
3926 hmin[0] = max_ff(hmin[0], hmin[i]);
3927 hmax[0] = min_ff(hmax[0], hmax[i]);
3928
3929 solve_first = solve_last = true;
3930
3931 bezier_eq_continuous(a, b, c, d, dy, l, 0);
3932 }
3933 else {
3934 float tmp[2];
3935
3936 /* boundary condition: fixed handles or zero curvature */
3937 if (!solve_first) {
3938 sub_v2_v2v2(tmp, bezt_first->vec[2], bezt_first->vec[1]);
3939 first_handle_adj = bezier_calc_handle_adj(tmp, dx[1]);
3940
3941 bezier_lock_unknown(a, b, c, d, 0, tmp[1]);
3942 }
3943 else {
3944 bezier_eq_noaccel_right(a, b, c, d, dy, l, 0);
3945 }
3946
3947 if (!solve_last) {
3948 sub_v2_v2v2(tmp, bezt_last->vec[1], bezt_last->vec[0]);
3949 last_handle_adj = bezier_calc_handle_adj(tmp, dx[count - 1]);
3950
3951 bezier_lock_unknown(a, b, c, d, count - 1, tmp[1]);
3952 }
3953 else {
3954 bezier_eq_noaccel_left(a, b, c, d, dy, l, count - 1);
3955 }
3956 }
3957
3958 /* main tridiagonal system of equations */
3959
3960 for (int i = 1; i < count - 1; i++) {
3961 bezier_eq_continuous(a, b, c, d, dy, l, i);
3962 }
3963
3964 /* apply correction for user-defined handles with nonstandard x positions */
3965
3966 if (!full_cycle) {
3967 if (count > 2 || solve_last) {
3968 b[1] += l[1] * first_handle_adj;
3969 }
3970
3971 if (count > 2 || solve_first) {
3972 b[count - 2] += last_handle_adj;
3973 }
3974 }
3975
3976 /* solve and output results */
3977
3978 if (tridiagonal_solve_with_limits(a, b, c, d, h, hmin, hmax, solve_count)) {
3979 if (full_cycle) {
3980 h[count - 1] = h[0];
3981 }
3982
3983 for (int i = 1, j = start + 1; i < count - 1; i++, j++) {
3984 bool end = (j == total - 1);
3985
3986 bezier_output_handle(&bezt[j], false, -h[i] / l[i], end);
3987
3988 if (end) {
3989 j = 0;
3990 }
3991
3992 bezier_output_handle(&bezt[j], true, h[i], end);
3993 }
3994
3995 if (solve_first) {
3996 bezier_output_handle(bezt_first, true, h[0], start == 0);
3997 }
3998
3999 if (solve_last) {
4000 bezier_output_handle(bezt_last, false, -h[count - 1] / l[count - 1], start + count == total);
4001 }
4002 }
4003
4004 /* free all */
4005
4006 free_arrays(tmp_buffer);
4007 }
4008
is_free_auto_point(BezTriple * bezt)4009 static bool is_free_auto_point(BezTriple *bezt)
4010 {
4011 return BEZT_IS_AUTOH(bezt) && bezt->f5 == HD_AUTOTYPE_NORMAL;
4012 }
4013
BKE_nurb_handle_smooth_fcurve(BezTriple * bezt,int total,bool cyclic)4014 void BKE_nurb_handle_smooth_fcurve(BezTriple *bezt, int total, bool cyclic)
4015 {
4016 /* ignore cyclic extrapolation if end points are locked */
4017 cyclic = cyclic && is_free_auto_point(&bezt[0]) && is_free_auto_point(&bezt[total - 1]);
4018
4019 /* if cyclic, try to find a sequence break point */
4020 int search_base = 0;
4021
4022 if (cyclic) {
4023 for (int i = 1; i < total - 1; i++) {
4024 if (!is_free_auto_point(&bezt[i])) {
4025 search_base = i;
4026 break;
4027 }
4028 }
4029
4030 /* all points of the curve are freely changeable auto handles - solve as full cycle */
4031 if (search_base == 0) {
4032 bezier_handle_calc_smooth_fcurve(bezt, total, 0, total, cyclic);
4033 return;
4034 }
4035 }
4036
4037 /* Find continuous subsequences of free auto handles and smooth them, starting at
4038 * search_base. In cyclic mode these subsequences can span the cycle boundary. */
4039 int start = search_base, count = 1;
4040
4041 for (int i = 1, j = start + 1; i < total; i++, j++) {
4042 /* in cyclic mode: jump from last to first point when necessary */
4043 if (j == total - 1 && cyclic) {
4044 j = 0;
4045 }
4046
4047 /* non auto handle closes the list (we come here at least for the last handle, see above) */
4048 if (!is_free_auto_point(&bezt[j])) {
4049 bezier_handle_calc_smooth_fcurve(bezt, total, start, count + 1, cyclic);
4050 start = j;
4051 count = 1;
4052 }
4053 else {
4054 count++;
4055 }
4056 }
4057
4058 if (count > 1) {
4059 bezier_handle_calc_smooth_fcurve(bezt, total, start, count, cyclic);
4060 }
4061 }
4062
4063 /**
4064 * Recalculate the handles of a nurb bezier-triple. Acts based on handle selection with `SELECT`
4065 * flag. To use a different flag, use #BKE_nurb_handle_calc_ex().
4066 */
BKE_nurb_handle_calc(BezTriple * bezt,BezTriple * prev,BezTriple * next,const bool is_fcurve,const char smoothing)4067 void BKE_nurb_handle_calc(
4068 BezTriple *bezt, BezTriple *prev, BezTriple *next, const bool is_fcurve, const char smoothing)
4069 {
4070 calchandleNurb_intern(bezt, prev, next, SELECT, is_fcurve, false, smoothing);
4071 }
4072
4073 /**
4074 * Variant of #BKE_nurb_handle_calc() that allows calculating based on a different select flag.
4075 *
4076 * \param handle_sel_flag: The flag (bezt.f1/2/3) value to use to determine selection.
4077 * Usually #SELECT, but may want to use a different one at times
4078 * (if caller does not operate on selection).
4079 */
BKE_nurb_handle_calc_ex(BezTriple * bezt,BezTriple * prev,BezTriple * next,const eBezTriple_Flag__Alias handle_sel_flag,const bool is_fcurve,const char smoothing)4080 void BKE_nurb_handle_calc_ex(BezTriple *bezt,
4081 BezTriple *prev,
4082 BezTriple *next,
4083 const eBezTriple_Flag__Alias handle_sel_flag,
4084 const bool is_fcurve,
4085 const char smoothing)
4086 {
4087 calchandleNurb_intern(bezt, prev, next, handle_sel_flag, is_fcurve, false, smoothing);
4088 }
4089
BKE_nurb_handles_calc(Nurb * nu)4090 void BKE_nurb_handles_calc(Nurb *nu) /* first, if needed, set handle flags */
4091 {
4092 calchandlesNurb_intern(nu, SELECT, false);
4093 }
4094
4095 /**
4096 * Workaround #BKE_nurb_handles_calc logic
4097 * that makes unselected align to the selected handle.
4098 */
nurbList_handles_swap_select(Nurb * nu)4099 static void nurbList_handles_swap_select(Nurb *nu)
4100 {
4101 BezTriple *bezt;
4102 int i;
4103
4104 for (i = nu->pntsu, bezt = nu->bezt; i--; bezt++) {
4105 if ((bezt->f1 & SELECT) != (bezt->f3 & SELECT)) {
4106 bezt->f1 ^= SELECT;
4107 bezt->f3 ^= SELECT;
4108 }
4109 }
4110 }
4111
4112 /* internal use only (weak) */
nurb_handles_calc__align_selected(Nurb * nu)4113 static void nurb_handles_calc__align_selected(Nurb *nu)
4114 {
4115 nurbList_handles_swap_select(nu);
4116 BKE_nurb_handles_calc(nu);
4117 nurbList_handles_swap_select(nu);
4118 }
4119
4120 /* similar to BKE_nurb_handle_calc but for curves and
4121 * figures out the previous and next for us */
BKE_nurb_handle_calc_simple(Nurb * nu,BezTriple * bezt)4122 void BKE_nurb_handle_calc_simple(Nurb *nu, BezTriple *bezt)
4123 {
4124 if (nu->pntsu > 1) {
4125 BezTriple *prev = BKE_nurb_bezt_get_prev(nu, bezt);
4126 BezTriple *next = BKE_nurb_bezt_get_next(nu, bezt);
4127 BKE_nurb_handle_calc(bezt, prev, next, 0, 0);
4128 }
4129 }
4130
BKE_nurb_handle_calc_simple_auto(Nurb * nu,BezTriple * bezt)4131 void BKE_nurb_handle_calc_simple_auto(Nurb *nu, BezTriple *bezt)
4132 {
4133 if (nu->pntsu > 1) {
4134 const char h1_back = bezt->h1, h2_back = bezt->h2;
4135
4136 bezt->h1 = bezt->h2 = HD_AUTO;
4137
4138 /* Override handle types to HD_AUTO and recalculate */
4139 BKE_nurb_handle_calc_simple(nu, bezt);
4140
4141 bezt->h1 = h1_back;
4142 bezt->h2 = h2_back;
4143 }
4144 }
4145
4146 /**
4147 * Update selected handle types to ensure valid state, e.g. deduce "Auto" types to concrete ones.
4148 * Thereby \a sel_flag defines what qualifies as selected.
4149 * Use when something has changed handle positions.
4150 *
4151 * The caller needs to recalculate handles.
4152 *
4153 * \param sel_flag: The flag (bezt.f1/2/3) value to use to determine selection. Usually `SELECT`,
4154 * but may want to use a different one at times (if caller does not operate on
4155 * selection).
4156 * \param use_handle: Check selection state of individual handles, otherwise always update both
4157 * handles if the key is selected.
4158 */
BKE_nurb_bezt_handle_test(BezTriple * bezt,const eBezTriple_Flag__Alias sel_flag,const bool use_handle,const bool use_around_local)4159 void BKE_nurb_bezt_handle_test(BezTriple *bezt,
4160 const eBezTriple_Flag__Alias sel_flag,
4161 const bool use_handle,
4162 const bool use_around_local)
4163 {
4164 short flag = 0;
4165
4166 #define SEL_F1 (1 << 0)
4167 #define SEL_F2 (1 << 1)
4168 #define SEL_F3 (1 << 2)
4169
4170 if (use_handle) {
4171 if (bezt->f1 & sel_flag) {
4172 flag |= SEL_F1;
4173 }
4174 if (bezt->f2 & sel_flag) {
4175 flag |= SEL_F2;
4176 }
4177 if (bezt->f3 & sel_flag) {
4178 flag |= SEL_F3;
4179 }
4180 }
4181 else {
4182 flag = (bezt->f2 & sel_flag) ? (SEL_F1 | SEL_F2 | SEL_F3) : 0;
4183 }
4184
4185 if (use_around_local) {
4186 flag &= ~SEL_F2;
4187 }
4188
4189 /* check for partial selection */
4190 if (!ELEM(flag, 0, SEL_F1 | SEL_F2 | SEL_F3)) {
4191 if (ELEM(bezt->h1, HD_AUTO, HD_AUTO_ANIM)) {
4192 bezt->h1 = HD_ALIGN;
4193 }
4194 if (ELEM(bezt->h2, HD_AUTO, HD_AUTO_ANIM)) {
4195 bezt->h2 = HD_ALIGN;
4196 }
4197
4198 if (bezt->h1 == HD_VECT) {
4199 if ((!(flag & SEL_F1)) != (!(flag & SEL_F2))) {
4200 bezt->h1 = HD_FREE;
4201 }
4202 }
4203 if (bezt->h2 == HD_VECT) {
4204 if ((!(flag & SEL_F3)) != (!(flag & SEL_F2))) {
4205 bezt->h2 = HD_FREE;
4206 }
4207 }
4208 }
4209
4210 #undef SEL_F1
4211 #undef SEL_F2
4212 #undef SEL_F3
4213 }
4214
BKE_nurb_handles_test(Nurb * nu,const bool use_handle,const bool use_around_local)4215 void BKE_nurb_handles_test(Nurb *nu, const bool use_handle, const bool use_around_local)
4216 {
4217 BezTriple *bezt;
4218 int a;
4219
4220 if (nu->type != CU_BEZIER) {
4221 return;
4222 }
4223
4224 bezt = nu->bezt;
4225 a = nu->pntsu;
4226 while (a--) {
4227 BKE_nurb_bezt_handle_test(bezt, SELECT, use_handle, use_around_local);
4228 bezt++;
4229 }
4230
4231 BKE_nurb_handles_calc(nu);
4232 }
4233
BKE_nurb_handles_autocalc(Nurb * nu,uint8_t flag)4234 void BKE_nurb_handles_autocalc(Nurb *nu, uint8_t flag)
4235 {
4236 /* checks handle coordinates and calculates type */
4237 const float eps = 0.0001f;
4238 const float eps_sq = eps * eps;
4239
4240 if (nu == NULL || nu->bezt == NULL) {
4241 return;
4242 }
4243
4244 BezTriple *bezt2 = nu->bezt;
4245 BezTriple *bezt1 = bezt2 + (nu->pntsu - 1);
4246 BezTriple *bezt0 = bezt1 - 1;
4247 int i = nu->pntsu;
4248
4249 while (i--) {
4250 bool align = false, leftsmall = false, rightsmall = false;
4251
4252 /* left handle: */
4253 if (flag == 0 || (bezt1->f1 & flag)) {
4254 bezt1->h1 = HD_FREE;
4255 /* distance too short: vectorhandle */
4256 if (len_squared_v3v3(bezt1->vec[1], bezt0->vec[1]) < eps_sq) {
4257 bezt1->h1 = HD_VECT;
4258 leftsmall = true;
4259 }
4260 else {
4261 /* aligned handle? */
4262 if (dist_squared_to_line_v3(bezt1->vec[1], bezt1->vec[0], bezt1->vec[2]) < eps_sq) {
4263 align = true;
4264 bezt1->h1 = HD_ALIGN;
4265 }
4266 /* or vector handle? */
4267 if (dist_squared_to_line_v3(bezt1->vec[0], bezt1->vec[1], bezt0->vec[1]) < eps_sq) {
4268 bezt1->h1 = HD_VECT;
4269 }
4270 }
4271 }
4272 /* right handle: */
4273 if (flag == 0 || (bezt1->f3 & flag)) {
4274 bezt1->h2 = HD_FREE;
4275 /* distance too short: vectorhandle */
4276 if (len_squared_v3v3(bezt1->vec[1], bezt2->vec[1]) < eps_sq) {
4277 bezt1->h2 = HD_VECT;
4278 rightsmall = true;
4279 }
4280 else {
4281 /* aligned handle? */
4282 if (align) {
4283 bezt1->h2 = HD_ALIGN;
4284 }
4285
4286 /* or vector handle? */
4287 if (dist_squared_to_line_v3(bezt1->vec[2], bezt1->vec[1], bezt2->vec[1]) < eps_sq) {
4288 bezt1->h2 = HD_VECT;
4289 }
4290 }
4291 }
4292 if (leftsmall && bezt1->h2 == HD_ALIGN) {
4293 bezt1->h2 = HD_FREE;
4294 }
4295 if (rightsmall && bezt1->h1 == HD_ALIGN) {
4296 bezt1->h1 = HD_FREE;
4297 }
4298
4299 /* undesired combination: */
4300 if (bezt1->h1 == HD_ALIGN && bezt1->h2 == HD_VECT) {
4301 bezt1->h1 = HD_FREE;
4302 }
4303 if (bezt1->h2 == HD_ALIGN && bezt1->h1 == HD_VECT) {
4304 bezt1->h2 = HD_FREE;
4305 }
4306
4307 bezt0 = bezt1;
4308 bezt1 = bezt2;
4309 bezt2++;
4310 }
4311
4312 BKE_nurb_handles_calc(nu);
4313 }
4314
BKE_nurbList_handles_autocalc(ListBase * editnurb,uint8_t flag)4315 void BKE_nurbList_handles_autocalc(ListBase *editnurb, uint8_t flag)
4316 {
4317 Nurb *nu;
4318
4319 nu = editnurb->first;
4320 while (nu) {
4321 BKE_nurb_handles_autocalc(nu, flag);
4322 nu = nu->next;
4323 }
4324 }
4325
BKE_nurbList_handles_set(ListBase * editnurb,const char code)4326 void BKE_nurbList_handles_set(ListBase *editnurb, const char code)
4327 {
4328 /* code==1: set autohandle */
4329 /* code==2: set vectorhandle */
4330 /* code==3 (HD_ALIGN) it toggle, vectorhandles become HD_FREE */
4331 /* code==4: sets icu flag to become IPO_AUTO_HORIZ, horizontal extremes on auto-handles */
4332 /* code==5: Set align, like 3 but no toggle */
4333 /* code==6: Clear align, like 3 but no toggle */
4334 Nurb *nu;
4335 BezTriple *bezt;
4336 int a;
4337
4338 if (ELEM(code, HD_AUTO, HD_VECT)) {
4339 nu = editnurb->first;
4340 while (nu) {
4341 if (nu->type == CU_BEZIER) {
4342 bezt = nu->bezt;
4343 a = nu->pntsu;
4344 while (a--) {
4345 if ((bezt->f1 & SELECT) || (bezt->f3 & SELECT)) {
4346 if (bezt->f1 & SELECT) {
4347 bezt->h1 = code;
4348 }
4349 if (bezt->f3 & SELECT) {
4350 bezt->h2 = code;
4351 }
4352 if (bezt->h1 != bezt->h2) {
4353 if (ELEM(bezt->h1, HD_ALIGN, HD_AUTO)) {
4354 bezt->h1 = HD_FREE;
4355 }
4356 if (ELEM(bezt->h2, HD_ALIGN, HD_AUTO)) {
4357 bezt->h2 = HD_FREE;
4358 }
4359 }
4360 }
4361 bezt++;
4362 }
4363
4364 /* like BKE_nurb_handles_calc but moves selected */
4365 nurb_handles_calc__align_selected(nu);
4366 }
4367 nu = nu->next;
4368 }
4369 }
4370 else {
4371 char h_new = HD_FREE;
4372
4373 /* there is 1 handle not FREE: FREE it all, else make ALIGNED */
4374 if (code == 5) {
4375 h_new = HD_ALIGN;
4376 }
4377 else if (code == 6) {
4378 h_new = HD_FREE;
4379 }
4380 else {
4381 /* Toggle */
4382 for (nu = editnurb->first; nu; nu = nu->next) {
4383 if (nu->type == CU_BEZIER) {
4384 bezt = nu->bezt;
4385 a = nu->pntsu;
4386 while (a--) {
4387 if (((bezt->f1 & SELECT) && bezt->h1 != HD_FREE) ||
4388 ((bezt->f3 & SELECT) && bezt->h2 != HD_FREE)) {
4389 h_new = HD_AUTO;
4390 break;
4391 }
4392 bezt++;
4393 }
4394 }
4395 }
4396 h_new = (h_new == HD_FREE) ? HD_ALIGN : HD_FREE;
4397 }
4398 for (nu = editnurb->first; nu; nu = nu->next) {
4399 if (nu->type == CU_BEZIER) {
4400 bezt = nu->bezt;
4401 a = nu->pntsu;
4402 while (a--) {
4403 if (bezt->f1 & SELECT) {
4404 bezt->h1 = h_new;
4405 }
4406 if (bezt->f3 & SELECT) {
4407 bezt->h2 = h_new;
4408 }
4409
4410 bezt++;
4411 }
4412
4413 /* like BKE_nurb_handles_calc but moves selected */
4414 nurb_handles_calc__align_selected(nu);
4415 }
4416 }
4417 }
4418 }
4419
BKE_nurbList_handles_recalculate(ListBase * editnurb,const bool calc_length,const uint8_t flag)4420 void BKE_nurbList_handles_recalculate(ListBase *editnurb,
4421 const bool calc_length,
4422 const uint8_t flag)
4423 {
4424 Nurb *nu;
4425 BezTriple *bezt;
4426 int a;
4427
4428 for (nu = editnurb->first; nu; nu = nu->next) {
4429 if (nu->type == CU_BEZIER) {
4430 bool changed = false;
4431
4432 for (a = nu->pntsu, bezt = nu->bezt; a--; bezt++) {
4433
4434 const bool h1_select = (bezt->f1 & flag) == flag;
4435 const bool h2_select = (bezt->f3 & flag) == flag;
4436
4437 if (h1_select || h2_select) {
4438
4439 float co1_back[3], co2_back[3];
4440
4441 copy_v3_v3(co1_back, bezt->vec[0]);
4442 copy_v3_v3(co2_back, bezt->vec[2]);
4443
4444 BKE_nurb_handle_calc_simple_auto(nu, bezt);
4445
4446 if (h1_select) {
4447 if (!calc_length) {
4448 dist_ensure_v3_v3fl(bezt->vec[0], bezt->vec[1], len_v3v3(co1_back, bezt->vec[1]));
4449 }
4450 }
4451 else {
4452 copy_v3_v3(bezt->vec[0], co1_back);
4453 }
4454
4455 if (h2_select) {
4456 if (!calc_length) {
4457 dist_ensure_v3_v3fl(bezt->vec[2], bezt->vec[1], len_v3v3(co2_back, bezt->vec[1]));
4458 }
4459 }
4460 else {
4461 copy_v3_v3(bezt->vec[2], co2_back);
4462 }
4463
4464 changed = true;
4465 }
4466 }
4467
4468 if (changed) {
4469 /* Recalculate the whole curve */
4470 BKE_nurb_handles_calc(nu);
4471 }
4472 }
4473 }
4474 }
4475
BKE_nurbList_flag_set(ListBase * editnurb,uint8_t flag,bool set)4476 void BKE_nurbList_flag_set(ListBase *editnurb, uint8_t flag, bool set)
4477 {
4478 Nurb *nu;
4479 BezTriple *bezt;
4480 BPoint *bp;
4481 int a;
4482
4483 for (nu = editnurb->first; nu; nu = nu->next) {
4484 if (nu->type == CU_BEZIER) {
4485 a = nu->pntsu;
4486 bezt = nu->bezt;
4487 while (a--) {
4488 if (set) {
4489 bezt->f1 |= flag;
4490 bezt->f2 |= flag;
4491 bezt->f3 |= flag;
4492 }
4493 else {
4494 bezt->f1 &= ~flag;
4495 bezt->f2 &= ~flag;
4496 bezt->f3 &= ~flag;
4497 }
4498 bezt++;
4499 }
4500 }
4501 else {
4502 a = nu->pntsu * nu->pntsv;
4503 bp = nu->bp;
4504 while (a--) {
4505 SET_FLAG_FROM_TEST(bp->f1, set, flag);
4506 bp++;
4507 }
4508 }
4509 }
4510 }
4511
4512 /**
4513 * Set \a flag for every point that already has \a from_flag set.
4514 */
BKE_nurbList_flag_set_from_flag(ListBase * editnurb,uint8_t from_flag,uint8_t flag)4515 bool BKE_nurbList_flag_set_from_flag(ListBase *editnurb, uint8_t from_flag, uint8_t flag)
4516 {
4517 bool changed = false;
4518
4519 for (Nurb *nu = editnurb->first; nu; nu = nu->next) {
4520 if (nu->type == CU_BEZIER) {
4521 for (int i = 0; i < nu->pntsu; i++) {
4522 BezTriple *bezt = &nu->bezt[i];
4523 uint8_t old_f1 = bezt->f1, old_f2 = bezt->f2, old_f3 = bezt->f3;
4524
4525 SET_FLAG_FROM_TEST(bezt->f1, bezt->f1 & from_flag, flag);
4526 SET_FLAG_FROM_TEST(bezt->f2, bezt->f2 & from_flag, flag);
4527 SET_FLAG_FROM_TEST(bezt->f3, bezt->f3 & from_flag, flag);
4528
4529 changed |= (old_f1 != bezt->f1) || (old_f2 != bezt->f2) || (old_f3 != bezt->f3);
4530 }
4531 }
4532 else {
4533 for (int i = 0; i < nu->pntsu * nu->pntsv; i++) {
4534 BPoint *bp = &nu->bp[i];
4535 uint8_t old_f1 = bp->f1;
4536
4537 SET_FLAG_FROM_TEST(bp->f1, bp->f1 & from_flag, flag);
4538 changed |= (old_f1 != bp->f1);
4539 }
4540 }
4541 }
4542
4543 return changed;
4544 }
4545
BKE_nurb_direction_switch(Nurb * nu)4546 void BKE_nurb_direction_switch(Nurb *nu)
4547 {
4548 BezTriple *bezt1, *bezt2;
4549 BPoint *bp1, *bp2;
4550 float *fp1, *fp2, *tempf;
4551 int a, b;
4552
4553 if (nu->pntsu == 1 && nu->pntsv == 1) {
4554 return;
4555 }
4556
4557 if (nu->type == CU_BEZIER) {
4558 a = nu->pntsu;
4559 bezt1 = nu->bezt;
4560 bezt2 = bezt1 + (a - 1);
4561 if (a & 1) {
4562 a += 1; /* if odd, also swap middle content */
4563 }
4564 a /= 2;
4565 while (a > 0) {
4566 if (bezt1 != bezt2) {
4567 SWAP(BezTriple, *bezt1, *bezt2);
4568 }
4569
4570 swap_v3_v3(bezt1->vec[0], bezt1->vec[2]);
4571
4572 if (bezt1 != bezt2) {
4573 swap_v3_v3(bezt2->vec[0], bezt2->vec[2]);
4574 }
4575
4576 SWAP(uint8_t, bezt1->h1, bezt1->h2);
4577 SWAP(uint8_t, bezt1->f1, bezt1->f3);
4578
4579 if (bezt1 != bezt2) {
4580 SWAP(uint8_t, bezt2->h1, bezt2->h2);
4581 SWAP(uint8_t, bezt2->f1, bezt2->f3);
4582 bezt1->tilt = -bezt1->tilt;
4583 bezt2->tilt = -bezt2->tilt;
4584 }
4585 else {
4586 bezt1->tilt = -bezt1->tilt;
4587 }
4588 a--;
4589 bezt1++;
4590 bezt2--;
4591 }
4592 }
4593 else if (nu->pntsv == 1) {
4594 a = nu->pntsu;
4595 bp1 = nu->bp;
4596 bp2 = bp1 + (a - 1);
4597 a /= 2;
4598 while (bp1 != bp2 && a > 0) {
4599 SWAP(BPoint, *bp1, *bp2);
4600 a--;
4601 bp1->tilt = -bp1->tilt;
4602 bp2->tilt = -bp2->tilt;
4603 bp1++;
4604 bp2--;
4605 }
4606 /* If there are odd number of points no need to touch coord of middle one,
4607 * but still need to change its tilt.
4608 */
4609 if (nu->pntsu & 1) {
4610 bp1->tilt = -bp1->tilt;
4611 }
4612 if (nu->type == CU_NURBS) {
4613 /* no knots for too short paths */
4614 if (nu->knotsu) {
4615 /* inverse knots */
4616 a = KNOTSU(nu);
4617 fp1 = nu->knotsu;
4618 fp2 = fp1 + (a - 1);
4619 a /= 2;
4620 while (fp1 != fp2 && a > 0) {
4621 SWAP(float, *fp1, *fp2);
4622 a--;
4623 fp1++;
4624 fp2--;
4625 }
4626 /* and make in increasing order again */
4627 a = KNOTSU(nu);
4628 fp1 = nu->knotsu;
4629 fp2 = tempf = MEM_malloc_arrayN(a, sizeof(float), "switchdirect");
4630 a--;
4631 fp2[a] = fp1[a];
4632 while (a--) {
4633 fp2[0] = fabsf(fp1[1] - fp1[0]);
4634 fp1++;
4635 fp2++;
4636 }
4637
4638 a = KNOTSU(nu) - 1;
4639 fp1 = nu->knotsu;
4640 fp2 = tempf;
4641 fp1[0] = 0.0;
4642 fp1++;
4643 while (a--) {
4644 fp1[0] = fp1[-1] + fp2[0];
4645 fp1++;
4646 fp2++;
4647 }
4648 MEM_freeN(tempf);
4649 }
4650 }
4651 }
4652 else {
4653 for (b = 0; b < nu->pntsv; b++) {
4654 bp1 = nu->bp + b * nu->pntsu;
4655 a = nu->pntsu;
4656 bp2 = bp1 + (a - 1);
4657 a /= 2;
4658
4659 while (bp1 != bp2 && a > 0) {
4660 SWAP(BPoint, *bp1, *bp2);
4661 a--;
4662 bp1++;
4663 bp2--;
4664 }
4665 }
4666 }
4667 }
4668
BKE_curve_nurbs_vert_coords_get(ListBase * lb,float (* vert_coords)[3],int vert_len)4669 void BKE_curve_nurbs_vert_coords_get(ListBase *lb, float (*vert_coords)[3], int vert_len)
4670 {
4671 float *co = vert_coords[0];
4672 LISTBASE_FOREACH (Nurb *, nu, lb) {
4673 if (nu->type == CU_BEZIER) {
4674 BezTriple *bezt = nu->bezt;
4675 for (int i = 0; i < nu->pntsu; i++, bezt++) {
4676 copy_v3_v3(co, bezt->vec[0]);
4677 co += 3;
4678 copy_v3_v3(co, bezt->vec[1]);
4679 co += 3;
4680 copy_v3_v3(co, bezt->vec[2]);
4681 co += 3;
4682 }
4683 }
4684 else {
4685 BPoint *bp = nu->bp;
4686 for (int i = 0; i < nu->pntsu * nu->pntsv; i++, bp++) {
4687 copy_v3_v3(co, bp->vec);
4688 co += 3;
4689 }
4690 }
4691 }
4692 BLI_assert(co == vert_coords[vert_len]);
4693 UNUSED_VARS_NDEBUG(vert_len);
4694 }
4695
BKE_curve_nurbs_vert_coords_alloc(ListBase * lb,int * r_vert_len)4696 float (*BKE_curve_nurbs_vert_coords_alloc(ListBase *lb, int *r_vert_len))[3]
4697 {
4698 const int vert_len = BKE_nurbList_verts_count(lb);
4699 float(*vert_coords)[3] = MEM_malloc_arrayN(vert_len, sizeof(*vert_coords), __func__);
4700 BKE_curve_nurbs_vert_coords_get(lb, vert_coords, vert_len);
4701 *r_vert_len = vert_len;
4702 return vert_coords;
4703 }
4704
BKE_curve_nurbs_vert_coords_apply_with_mat4(ListBase * lb,const float (* vert_coords)[3],const float mat[4][4],const bool constrain_2d)4705 void BKE_curve_nurbs_vert_coords_apply_with_mat4(ListBase *lb,
4706 const float (*vert_coords)[3],
4707 const float mat[4][4],
4708 const bool constrain_2d)
4709 {
4710 const float *co = vert_coords[0];
4711
4712 LISTBASE_FOREACH (Nurb *, nu, lb) {
4713 if (nu->type == CU_BEZIER) {
4714 BezTriple *bezt = nu->bezt;
4715
4716 for (int i = 0; i < nu->pntsu; i++, bezt++) {
4717 mul_v3_m4v3(bezt->vec[0], mat, co);
4718 co += 3;
4719 mul_v3_m4v3(bezt->vec[1], mat, co);
4720 co += 3;
4721 mul_v3_m4v3(bezt->vec[2], mat, co);
4722 co += 3;
4723 }
4724 }
4725 else {
4726 BPoint *bp = nu->bp;
4727
4728 for (int i = 0; i < nu->pntsu * nu->pntsv; i++, bp++) {
4729 mul_v3_m4v3(bp->vec, mat, co);
4730 co += 3;
4731 }
4732 }
4733
4734 if (constrain_2d) {
4735 if (nu->flag & CU_2D) {
4736 BKE_nurb_test_2d(nu);
4737 }
4738 }
4739
4740 calchandlesNurb_intern(nu, SELECT, true);
4741 }
4742 }
4743
BKE_curve_nurbs_vert_coords_apply(ListBase * lb,const float (* vert_coords)[3],const bool constrain_2d)4744 void BKE_curve_nurbs_vert_coords_apply(ListBase *lb,
4745 const float (*vert_coords)[3],
4746 const bool constrain_2d)
4747 {
4748 const float *co = vert_coords[0];
4749
4750 LISTBASE_FOREACH (Nurb *, nu, lb) {
4751 if (nu->type == CU_BEZIER) {
4752 BezTriple *bezt = nu->bezt;
4753
4754 for (int i = 0; i < nu->pntsu; i++, bezt++) {
4755 copy_v3_v3(bezt->vec[0], co);
4756 co += 3;
4757 copy_v3_v3(bezt->vec[1], co);
4758 co += 3;
4759 copy_v3_v3(bezt->vec[2], co);
4760 co += 3;
4761 }
4762 }
4763 else {
4764 BPoint *bp = nu->bp;
4765
4766 for (int i = 0; i < nu->pntsu * nu->pntsv; i++, bp++) {
4767 copy_v3_v3(bp->vec, co);
4768 co += 3;
4769 }
4770 }
4771
4772 if (constrain_2d) {
4773 if (nu->flag & CU_2D) {
4774 BKE_nurb_test_2d(nu);
4775 }
4776 }
4777
4778 calchandlesNurb_intern(nu, SELECT, true);
4779 }
4780 }
4781
BKE_curve_nurbs_key_vert_coords_alloc(ListBase * lb,float * key,int * r_vert_len)4782 float (*BKE_curve_nurbs_key_vert_coords_alloc(ListBase *lb, float *key, int *r_vert_len))[3]
4783 {
4784 int vert_len = BKE_nurbList_verts_count(lb);
4785 float(*cos)[3] = MEM_malloc_arrayN(vert_len, sizeof(*cos), __func__);
4786
4787 float *co = cos[0];
4788 LISTBASE_FOREACH (Nurb *, nu, lb) {
4789 if (nu->type == CU_BEZIER) {
4790 BezTriple *bezt = nu->bezt;
4791
4792 for (int i = 0; i < nu->pntsu; i++, bezt++) {
4793 copy_v3_v3(co, &key[0]);
4794 co += 3;
4795 copy_v3_v3(co, &key[3]);
4796 co += 3;
4797 copy_v3_v3(co, &key[6]);
4798 co += 3;
4799 key += KEYELEM_FLOAT_LEN_BEZTRIPLE;
4800 }
4801 }
4802 else {
4803 BPoint *bp = nu->bp;
4804
4805 for (int i = 0; i < nu->pntsu * nu->pntsv; i++, bp++) {
4806 copy_v3_v3(co, key);
4807 co += 3;
4808 key += KEYELEM_FLOAT_LEN_BPOINT;
4809 }
4810 }
4811 }
4812 *r_vert_len = vert_len;
4813 return cos;
4814 }
4815
BKE_curve_nurbs_key_vert_tilts_apply(ListBase * lb,const float * key)4816 void BKE_curve_nurbs_key_vert_tilts_apply(ListBase *lb, const float *key)
4817 {
4818 LISTBASE_FOREACH (Nurb *, nu, lb) {
4819 if (nu->type == CU_BEZIER) {
4820 BezTriple *bezt = nu->bezt;
4821
4822 for (int i = 0; i < nu->pntsu; i++, bezt++) {
4823 bezt->tilt = key[9];
4824 bezt->radius = key[10];
4825 key += KEYELEM_FLOAT_LEN_BEZTRIPLE;
4826 }
4827 }
4828 else {
4829 BPoint *bp = nu->bp;
4830
4831 for (int i = 0; i < nu->pntsu * nu->pntsv; i++, bp++) {
4832 bp->tilt = key[3];
4833 bp->radius = key[4];
4834 key += KEYELEM_FLOAT_LEN_BPOINT;
4835 }
4836 }
4837 }
4838 }
4839
BKE_nurb_check_valid_u(const Nurb * nu)4840 bool BKE_nurb_check_valid_u(const Nurb *nu)
4841 {
4842 if (nu->pntsu <= 1) {
4843 return false;
4844 }
4845 if (nu->type != CU_NURBS) {
4846 return true; /* not a nurb, lets assume its valid */
4847 }
4848
4849 if (nu->pntsu < nu->orderu) {
4850 return false;
4851 }
4852 if (((nu->flagu & CU_NURB_CYCLIC) == 0) && (nu->flagu & CU_NURB_BEZIER)) {
4853 /* Bezier U Endpoints */
4854 if (nu->orderu == 4) {
4855 if (nu->pntsu < 5) {
4856 return false; /* bezier with 4 orderu needs 5 points */
4857 }
4858 }
4859 else {
4860 if (nu->orderu != 3) {
4861 return false; /* order must be 3 or 4 */
4862 }
4863 }
4864 }
4865 return true;
4866 }
BKE_nurb_check_valid_v(const Nurb * nu)4867 bool BKE_nurb_check_valid_v(const Nurb *nu)
4868 {
4869 if (nu->pntsv <= 1) {
4870 return false;
4871 }
4872 if (nu->type != CU_NURBS) {
4873 return true; /* not a nurb, lets assume its valid */
4874 }
4875
4876 if (nu->pntsv < nu->orderv) {
4877 return false;
4878 }
4879 if (((nu->flagv & CU_NURB_CYCLIC) == 0) && (nu->flagv & CU_NURB_BEZIER)) {
4880 /* Bezier V Endpoints */
4881 if (nu->orderv == 4) {
4882 if (nu->pntsv < 5) {
4883 return false; /* bezier with 4 orderu needs 5 points */
4884 }
4885 }
4886 else {
4887 if (nu->orderv != 3) {
4888 return false; /* order must be 3 or 4 */
4889 }
4890 }
4891 }
4892 return true;
4893 }
4894
BKE_nurb_check_valid_uv(const Nurb * nu)4895 bool BKE_nurb_check_valid_uv(const Nurb *nu)
4896 {
4897 if (!BKE_nurb_check_valid_u(nu)) {
4898 return false;
4899 }
4900 if ((nu->pntsv > 1) && !BKE_nurb_check_valid_v(nu)) {
4901 return false;
4902 }
4903
4904 return true;
4905 }
4906
BKE_nurb_order_clamp_u(struct Nurb * nu)4907 bool BKE_nurb_order_clamp_u(struct Nurb *nu)
4908 {
4909 bool changed = false;
4910 if (nu->pntsu < nu->orderu) {
4911 nu->orderu = max_ii(2, nu->pntsu);
4912 changed = true;
4913 }
4914 if (((nu->flagu & CU_NURB_CYCLIC) == 0) && (nu->flagu & CU_NURB_BEZIER)) {
4915 CLAMP(nu->orderu, 3, 4);
4916 changed = true;
4917 }
4918 return changed;
4919 }
4920
BKE_nurb_order_clamp_v(struct Nurb * nu)4921 bool BKE_nurb_order_clamp_v(struct Nurb *nu)
4922 {
4923 bool changed = false;
4924 if (nu->pntsv < nu->orderv) {
4925 nu->orderv = max_ii(2, nu->pntsv);
4926 changed = true;
4927 }
4928 if (((nu->flagv & CU_NURB_CYCLIC) == 0) && (nu->flagv & CU_NURB_BEZIER)) {
4929 CLAMP(nu->orderv, 3, 4);
4930 changed = true;
4931 }
4932 return changed;
4933 }
4934
4935 /**
4936 * \note caller must ensure active vertex remains valid.
4937 */
BKE_nurb_type_convert(Nurb * nu,const short type,const bool use_handles,const char ** r_err_msg)4938 bool BKE_nurb_type_convert(Nurb *nu,
4939 const short type,
4940 const bool use_handles,
4941 const char **r_err_msg)
4942 {
4943 BezTriple *bezt;
4944 BPoint *bp;
4945 int a, c, nr;
4946
4947 if (nu->type == CU_POLY) {
4948 if (type == CU_BEZIER) { /* to Bezier with vecthandles */
4949 nr = nu->pntsu;
4950 bezt = (BezTriple *)MEM_calloc_arrayN(nr, sizeof(BezTriple), "setsplinetype2");
4951 nu->bezt = bezt;
4952 a = nr;
4953 bp = nu->bp;
4954 while (a--) {
4955 copy_v3_v3(bezt->vec[1], bp->vec);
4956 bezt->f1 = bezt->f2 = bezt->f3 = bp->f1;
4957 bezt->h1 = bezt->h2 = HD_VECT;
4958 bezt->weight = bp->weight;
4959 bezt->radius = bp->radius;
4960 bp++;
4961 bezt++;
4962 }
4963 MEM_freeN(nu->bp);
4964 nu->bp = NULL;
4965 nu->pntsu = nr;
4966 nu->pntsv = 0;
4967 nu->type = CU_BEZIER;
4968 BKE_nurb_handles_calc(nu);
4969 }
4970 else if (type == CU_NURBS) {
4971 nu->type = CU_NURBS;
4972 nu->orderu = 4;
4973 nu->flagu &= CU_NURB_CYCLIC; /* disable all flags except for cyclic */
4974 BKE_nurb_knot_calc_u(nu);
4975 a = nu->pntsu * nu->pntsv;
4976 bp = nu->bp;
4977 while (a--) {
4978 bp->vec[3] = 1.0;
4979 bp++;
4980 }
4981 }
4982 }
4983 else if (nu->type == CU_BEZIER) { /* Bezier */
4984 if (type == CU_POLY || type == CU_NURBS) {
4985 nr = use_handles ? (3 * nu->pntsu) : nu->pntsu;
4986 nu->bp = MEM_calloc_arrayN(nr, sizeof(BPoint), "setsplinetype");
4987 a = nu->pntsu;
4988 bezt = nu->bezt;
4989 bp = nu->bp;
4990 while (a--) {
4991 if ((type == CU_POLY && bezt->h1 == HD_VECT && bezt->h2 == HD_VECT) ||
4992 (use_handles == false)) {
4993 /* vector handle becomes 1 poly vertice */
4994 copy_v3_v3(bp->vec, bezt->vec[1]);
4995 bp->vec[3] = 1.0;
4996 bp->f1 = bezt->f2;
4997 if (use_handles) {
4998 nr -= 2;
4999 }
5000 bp->radius = bezt->radius;
5001 bp->weight = bezt->weight;
5002 bp++;
5003 }
5004 else {
5005 const uint8_t *f = &bezt->f1;
5006 for (c = 0; c < 3; c++, f++) {
5007 copy_v3_v3(bp->vec, bezt->vec[c]);
5008 bp->vec[3] = 1.0;
5009 bp->f1 = *f;
5010 bp->radius = bezt->radius;
5011 bp->weight = bezt->weight;
5012 bp++;
5013 }
5014 }
5015 bezt++;
5016 }
5017 MEM_freeN(nu->bezt);
5018 nu->bezt = NULL;
5019 nu->pntsu = nr;
5020 nu->pntsv = 1;
5021 nu->orderu = 4;
5022 nu->orderv = 1;
5023 nu->type = type;
5024
5025 if (type == CU_NURBS) {
5026 nu->flagu &= CU_NURB_CYCLIC; /* disable all flags except for cyclic */
5027 nu->flagu |= CU_NURB_BEZIER;
5028 BKE_nurb_knot_calc_u(nu);
5029 }
5030 }
5031 }
5032 else if (nu->type == CU_NURBS) {
5033 if (type == CU_POLY) {
5034 nu->type = CU_POLY;
5035 if (nu->knotsu) {
5036 MEM_freeN(nu->knotsu); /* python created nurbs have a knotsu of zero */
5037 }
5038 nu->knotsu = NULL;
5039 if (nu->knotsv) {
5040 MEM_freeN(nu->knotsv);
5041 }
5042 nu->knotsv = NULL;
5043 }
5044 else if (type == CU_BEZIER) { /* to Bezier */
5045 nr = nu->pntsu / 3;
5046
5047 if (nr < 2) {
5048 if (r_err_msg != NULL) {
5049 *r_err_msg = "At least 6 points required for conversion";
5050 }
5051 return false; /* conversion impossible */
5052 }
5053
5054 bezt = MEM_calloc_arrayN(nr, sizeof(BezTriple), "setsplinetype2");
5055 nu->bezt = bezt;
5056 a = nr;
5057 bp = nu->bp;
5058 while (a--) {
5059 copy_v3_v3(bezt->vec[0], bp->vec);
5060 bezt->f1 = bp->f1;
5061 bp++;
5062 copy_v3_v3(bezt->vec[1], bp->vec);
5063 bezt->f2 = bp->f1;
5064 bp++;
5065 copy_v3_v3(bezt->vec[2], bp->vec);
5066 bezt->f3 = bp->f1;
5067 bezt->radius = bp->radius;
5068 bezt->weight = bp->weight;
5069 bp++;
5070 bezt++;
5071 }
5072 MEM_freeN(nu->bp);
5073 nu->bp = NULL;
5074 MEM_freeN(nu->knotsu);
5075 nu->knotsu = NULL;
5076 nu->pntsu = nr;
5077 nu->type = CU_BEZIER;
5078 }
5079 }
5080
5081 return true;
5082 }
5083
5084 /* Get edit nurbs or normal nurbs list */
BKE_curve_nurbs_get(Curve * cu)5085 ListBase *BKE_curve_nurbs_get(Curve *cu)
5086 {
5087 if (cu->editnurb) {
5088 return BKE_curve_editNurbs_get(cu);
5089 }
5090
5091 return &cu->nurb;
5092 }
5093
BKE_curve_nurb_active_set(Curve * cu,const Nurb * nu)5094 void BKE_curve_nurb_active_set(Curve *cu, const Nurb *nu)
5095 {
5096 if (nu == NULL) {
5097 cu->actnu = CU_ACT_NONE;
5098 }
5099 else {
5100 BLI_assert(!nu->hide);
5101 ListBase *nurbs = BKE_curve_editNurbs_get(cu);
5102 cu->actnu = BLI_findindex(nurbs, nu);
5103 }
5104 }
5105
BKE_curve_nurb_active_get(Curve * cu)5106 Nurb *BKE_curve_nurb_active_get(Curve *cu)
5107 {
5108 ListBase *nurbs = BKE_curve_editNurbs_get(cu);
5109 return BLI_findlink(nurbs, cu->actnu);
5110 }
5111
5112 /* Get active vert for curve */
BKE_curve_vert_active_get(Curve * cu)5113 void *BKE_curve_vert_active_get(Curve *cu)
5114 {
5115 Nurb *nu = NULL;
5116 void *vert = NULL;
5117
5118 BKE_curve_nurb_vert_active_get(cu, &nu, &vert);
5119 return vert;
5120 }
5121
BKE_curve_nurb_vert_index_get(const Nurb * nu,const void * vert)5122 int BKE_curve_nurb_vert_index_get(const Nurb *nu, const void *vert)
5123 {
5124 if (nu->type == CU_BEZIER) {
5125 BLI_assert(ARRAY_HAS_ITEM((BezTriple *)vert, nu->bezt, nu->pntsu));
5126 return (BezTriple *)vert - nu->bezt;
5127 }
5128
5129 BLI_assert(ARRAY_HAS_ITEM((BPoint *)vert, nu->bp, nu->pntsu * nu->pntsv));
5130 return (BPoint *)vert - nu->bp;
5131 }
5132
5133 /* Set active nurb and active vert for curve */
BKE_curve_nurb_vert_active_set(Curve * cu,const Nurb * nu,const void * vert)5134 void BKE_curve_nurb_vert_active_set(Curve *cu, const Nurb *nu, const void *vert)
5135 {
5136 if (nu) {
5137 BKE_curve_nurb_active_set(cu, nu);
5138
5139 if (vert) {
5140 cu->actvert = BKE_curve_nurb_vert_index_get(nu, vert);
5141 }
5142 else {
5143 cu->actvert = CU_ACT_NONE;
5144 }
5145 }
5146 else {
5147 cu->actnu = cu->actvert = CU_ACT_NONE;
5148 }
5149 }
5150
5151 /* Get points to active active nurb and active vert for curve */
BKE_curve_nurb_vert_active_get(Curve * cu,Nurb ** r_nu,void ** r_vert)5152 bool BKE_curve_nurb_vert_active_get(Curve *cu, Nurb **r_nu, void **r_vert)
5153 {
5154 Nurb *nu = NULL;
5155 void *vert = NULL;
5156
5157 if (cu->actvert != CU_ACT_NONE) {
5158 ListBase *nurbs = BKE_curve_editNurbs_get(cu);
5159 nu = BLI_findlink(nurbs, cu->actnu);
5160
5161 if (nu) {
5162 if (nu->type == CU_BEZIER) {
5163 BLI_assert(nu->pntsu > cu->actvert);
5164 vert = &nu->bezt[cu->actvert];
5165 }
5166 else {
5167 BLI_assert((nu->pntsu * nu->pntsv) > cu->actvert);
5168 vert = &nu->bp[cu->actvert];
5169 }
5170 }
5171 }
5172
5173 *r_nu = nu;
5174 *r_vert = vert;
5175
5176 return (*r_vert != NULL);
5177 }
5178
BKE_curve_nurb_vert_active_validate(Curve * cu)5179 void BKE_curve_nurb_vert_active_validate(Curve *cu)
5180 {
5181 Nurb *nu;
5182 void *vert;
5183
5184 if (BKE_curve_nurb_vert_active_get(cu, &nu, &vert)) {
5185 if (nu->type == CU_BEZIER) {
5186 BezTriple *bezt = vert;
5187 if (BEZT_ISSEL_ANY(bezt) == 0) {
5188 cu->actvert = CU_ACT_NONE;
5189 }
5190 }
5191 else {
5192 BPoint *bp = vert;
5193 if ((bp->f1 & SELECT) == 0) {
5194 cu->actvert = CU_ACT_NONE;
5195 }
5196 }
5197
5198 if (nu->hide) {
5199 cu->actnu = CU_ACT_NONE;
5200 }
5201 }
5202 }
5203
5204 /* basic vertex data functions */
BKE_curve_minmax(Curve * cu,bool use_radius,float min[3],float max[3])5205 bool BKE_curve_minmax(Curve *cu, bool use_radius, float min[3], float max[3])
5206 {
5207 ListBase *nurb_lb = BKE_curve_nurbs_get(cu);
5208 ListBase temp_nurb_lb = {NULL, NULL};
5209 const bool is_font = (BLI_listbase_is_empty(nurb_lb)) && (cu->len != 0);
5210 /* For font curves we generate temp list of splines.
5211 *
5212 * This is likely to be fine, this function is not supposed to be called
5213 * often, and it's the only way to get meaningful bounds for fonts.
5214 */
5215 if (is_font) {
5216 nurb_lb = &temp_nurb_lb;
5217 BKE_vfont_to_curve_ex(NULL, cu, FO_EDIT, nurb_lb, NULL, NULL, NULL, NULL);
5218 use_radius = false;
5219 }
5220 /* Do bounding box based on splines. */
5221 LISTBASE_FOREACH (Nurb *, nu, nurb_lb) {
5222 BKE_nurb_minmax(nu, use_radius, min, max);
5223 }
5224 const bool result = (BLI_listbase_is_empty(nurb_lb) == false);
5225 /* Cleanup if needed. */
5226 BKE_nurbList_free(&temp_nurb_lb);
5227 return result;
5228 }
5229
BKE_curve_center_median(Curve * cu,float cent[3])5230 bool BKE_curve_center_median(Curve *cu, float cent[3])
5231 {
5232 ListBase *nurb_lb = BKE_curve_nurbs_get(cu);
5233 Nurb *nu;
5234 int total = 0;
5235
5236 zero_v3(cent);
5237
5238 for (nu = nurb_lb->first; nu; nu = nu->next) {
5239 int i;
5240
5241 if (nu->type == CU_BEZIER) {
5242 BezTriple *bezt;
5243 i = nu->pntsu;
5244 total += i * 3;
5245 for (bezt = nu->bezt; i--; bezt++) {
5246 add_v3_v3(cent, bezt->vec[0]);
5247 add_v3_v3(cent, bezt->vec[1]);
5248 add_v3_v3(cent, bezt->vec[2]);
5249 }
5250 }
5251 else {
5252 BPoint *bp;
5253 i = nu->pntsu * nu->pntsv;
5254 total += i;
5255 for (bp = nu->bp; i--; bp++) {
5256 add_v3_v3(cent, bp->vec);
5257 }
5258 }
5259 }
5260
5261 if (total) {
5262 mul_v3_fl(cent, 1.0f / (float)total);
5263 }
5264
5265 return (total != 0);
5266 }
5267
BKE_curve_center_bounds(Curve * cu,float cent[3])5268 bool BKE_curve_center_bounds(Curve *cu, float cent[3])
5269 {
5270 float min[3], max[3];
5271 INIT_MINMAX(min, max);
5272 if (BKE_curve_minmax(cu, false, min, max)) {
5273 mid_v3_v3v3(cent, min, max);
5274 return true;
5275 }
5276
5277 return false;
5278 }
5279
BKE_curve_transform_ex(Curve * cu,const float mat[4][4],const bool do_keys,const bool do_props,const float unit_scale)5280 void BKE_curve_transform_ex(Curve *cu,
5281 const float mat[4][4],
5282 const bool do_keys,
5283 const bool do_props,
5284 const float unit_scale)
5285 {
5286 Nurb *nu;
5287 BPoint *bp;
5288 BezTriple *bezt;
5289 int i;
5290
5291 for (nu = cu->nurb.first; nu; nu = nu->next) {
5292 if (nu->type == CU_BEZIER) {
5293 i = nu->pntsu;
5294 for (bezt = nu->bezt; i--; bezt++) {
5295 mul_m4_v3(mat, bezt->vec[0]);
5296 mul_m4_v3(mat, bezt->vec[1]);
5297 mul_m4_v3(mat, bezt->vec[2]);
5298 if (do_props) {
5299 bezt->radius *= unit_scale;
5300 }
5301 }
5302 BKE_nurb_handles_calc(nu);
5303 }
5304 else {
5305 i = nu->pntsu * nu->pntsv;
5306 for (bp = nu->bp; i--; bp++) {
5307 mul_m4_v3(mat, bp->vec);
5308 if (do_props) {
5309 bp->radius *= unit_scale;
5310 }
5311 }
5312 }
5313 }
5314
5315 if (do_keys && cu->key) {
5316 KeyBlock *kb;
5317 for (kb = cu->key->block.first; kb; kb = kb->next) {
5318 float *fp = kb->data;
5319 int n = kb->totelem;
5320
5321 for (nu = cu->nurb.first; nu; nu = nu->next) {
5322 if (nu->type == CU_BEZIER) {
5323 for (i = nu->pntsu; i && (n -= KEYELEM_ELEM_LEN_BEZTRIPLE) >= 0; i--) {
5324 mul_m4_v3(mat, &fp[0]);
5325 mul_m4_v3(mat, &fp[3]);
5326 mul_m4_v3(mat, &fp[6]);
5327 if (do_props) {
5328 fp[10] *= unit_scale; /* radius */
5329 }
5330 fp += KEYELEM_FLOAT_LEN_BEZTRIPLE;
5331 }
5332 }
5333 else {
5334 for (i = nu->pntsu * nu->pntsv; i && (n -= KEYELEM_ELEM_LEN_BPOINT) >= 0; i--) {
5335 mul_m4_v3(mat, fp);
5336 if (do_props) {
5337 fp[4] *= unit_scale; /* radius */
5338 }
5339 fp += KEYELEM_FLOAT_LEN_BPOINT;
5340 }
5341 }
5342 }
5343 }
5344 }
5345 }
5346
BKE_curve_transform(Curve * cu,const float mat[4][4],const bool do_keys,const bool do_props)5347 void BKE_curve_transform(Curve *cu, const float mat[4][4], const bool do_keys, const bool do_props)
5348 {
5349 float unit_scale = mat4_to_scale(mat);
5350 BKE_curve_transform_ex(cu, mat, do_keys, do_props, unit_scale);
5351 }
5352
BKE_curve_translate(Curve * cu,const float offset[3],const bool do_keys)5353 void BKE_curve_translate(Curve *cu, const float offset[3], const bool do_keys)
5354 {
5355 ListBase *nurb_lb = BKE_curve_nurbs_get(cu);
5356
5357 LISTBASE_FOREACH (Nurb *, nu, nurb_lb) {
5358 if (nu->type == CU_BEZIER) {
5359 int i = nu->pntsu;
5360 for (BezTriple *bezt = nu->bezt; i--; bezt++) {
5361 add_v3_v3(bezt->vec[0], offset);
5362 add_v3_v3(bezt->vec[1], offset);
5363 add_v3_v3(bezt->vec[2], offset);
5364 }
5365 }
5366 else {
5367 int i = nu->pntsu * nu->pntsv;
5368 for (BPoint *bp = nu->bp; i--; bp++) {
5369 add_v3_v3(bp->vec, offset);
5370 }
5371 }
5372 }
5373
5374 if (do_keys && cu->key) {
5375 LISTBASE_FOREACH (KeyBlock *, kb, &cu->key->block) {
5376 float *fp = kb->data;
5377 int n = kb->totelem;
5378
5379 LISTBASE_FOREACH (Nurb *, nu, &cu->nurb) {
5380 if (nu->type == CU_BEZIER) {
5381 for (int i = nu->pntsu; i && (n -= KEYELEM_ELEM_LEN_BEZTRIPLE) >= 0; i--) {
5382 add_v3_v3(&fp[0], offset);
5383 add_v3_v3(&fp[3], offset);
5384 add_v3_v3(&fp[6], offset);
5385 fp += KEYELEM_FLOAT_LEN_BEZTRIPLE;
5386 }
5387 }
5388 else {
5389 for (int i = nu->pntsu * nu->pntsv; i && (n -= KEYELEM_ELEM_LEN_BPOINT) >= 0; i--) {
5390 add_v3_v3(fp, offset);
5391 fp += KEYELEM_FLOAT_LEN_BPOINT;
5392 }
5393 }
5394 }
5395 }
5396 }
5397 }
5398
BKE_curve_material_index_remove(Curve * cu,int index)5399 void BKE_curve_material_index_remove(Curve *cu, int index)
5400 {
5401 const int curvetype = BKE_curve_type_get(cu);
5402
5403 if (curvetype == OB_FONT) {
5404 struct CharInfo *info = cu->strinfo;
5405 for (int i = cu->len_char32 - 1; i >= 0; i--, info++) {
5406 if (info->mat_nr && info->mat_nr >= index) {
5407 info->mat_nr--;
5408 }
5409 }
5410 }
5411 else {
5412 LISTBASE_FOREACH (Nurb *, nu, &cu->nurb) {
5413 if (nu->mat_nr && nu->mat_nr >= index) {
5414 nu->mat_nr--;
5415 }
5416 }
5417 }
5418 }
5419
BKE_curve_material_index_used(Curve * cu,int index)5420 bool BKE_curve_material_index_used(Curve *cu, int index)
5421 {
5422 const int curvetype = BKE_curve_type_get(cu);
5423
5424 if (curvetype == OB_FONT) {
5425 struct CharInfo *info = cu->strinfo;
5426 for (int i = cu->len_char32 - 1; i >= 0; i--, info++) {
5427 if (info->mat_nr == index) {
5428 return true;
5429 }
5430 }
5431 }
5432 else {
5433 LISTBASE_FOREACH (Nurb *, nu, &cu->nurb) {
5434 if (nu->mat_nr == index) {
5435 return true;
5436 }
5437 }
5438 }
5439
5440 return false;
5441 }
5442
BKE_curve_material_index_clear(Curve * cu)5443 void BKE_curve_material_index_clear(Curve *cu)
5444 {
5445 const int curvetype = BKE_curve_type_get(cu);
5446
5447 if (curvetype == OB_FONT) {
5448 struct CharInfo *info = cu->strinfo;
5449 for (int i = cu->len_char32 - 1; i >= 0; i--, info++) {
5450 info->mat_nr = 0;
5451 }
5452 }
5453 else {
5454 LISTBASE_FOREACH (Nurb *, nu, &cu->nurb) {
5455 nu->mat_nr = 0;
5456 }
5457 }
5458 }
5459
BKE_curve_material_index_validate(Curve * cu)5460 bool BKE_curve_material_index_validate(Curve *cu)
5461 {
5462 const int curvetype = BKE_curve_type_get(cu);
5463 bool is_valid = true;
5464
5465 if (curvetype == OB_FONT) {
5466 CharInfo *info = cu->strinfo;
5467 const int max_idx = max_ii(0, cu->totcol); /* OB_FONT use 1 as first mat index, not 0!!! */
5468 int i;
5469 for (i = cu->len_char32 - 1; i >= 0; i--, info++) {
5470 if (info->mat_nr > max_idx) {
5471 info->mat_nr = 0;
5472 is_valid = false;
5473 }
5474 }
5475 }
5476 else {
5477 Nurb *nu;
5478 const int max_idx = max_ii(0, cu->totcol - 1);
5479 for (nu = cu->nurb.first; nu; nu = nu->next) {
5480 if (nu->mat_nr > max_idx) {
5481 nu->mat_nr = 0;
5482 is_valid = false;
5483 }
5484 }
5485 }
5486
5487 if (!is_valid) {
5488 DEG_id_tag_update(&cu->id, ID_RECALC_GEOMETRY);
5489 return true;
5490 }
5491 return false;
5492 }
5493
BKE_curve_material_remap(Curve * cu,const unsigned int * remap,unsigned int remap_len)5494 void BKE_curve_material_remap(Curve *cu, const unsigned int *remap, unsigned int remap_len)
5495 {
5496 const int curvetype = BKE_curve_type_get(cu);
5497 const short remap_len_short = (short)remap_len;
5498
5499 #define MAT_NR_REMAP(n) \
5500 if (n < remap_len_short) { \
5501 BLI_assert(n >= 0 && remap[n] < remap_len_short); \
5502 n = remap[n]; \
5503 } \
5504 ((void)0)
5505
5506 if (curvetype == OB_FONT) {
5507 struct CharInfo *strinfo;
5508 int charinfo_len, i;
5509
5510 if (cu->editfont) {
5511 EditFont *ef = cu->editfont;
5512 strinfo = ef->textbufinfo;
5513 charinfo_len = ef->len;
5514 }
5515 else {
5516 strinfo = cu->strinfo;
5517 charinfo_len = cu->len_char32;
5518 }
5519
5520 for (i = 0; i <= charinfo_len; i++) {
5521 if (strinfo[i].mat_nr > 0) {
5522 strinfo[i].mat_nr -= 1;
5523 MAT_NR_REMAP(strinfo[i].mat_nr);
5524 strinfo[i].mat_nr += 1;
5525 }
5526 }
5527 }
5528 else {
5529 Nurb *nu;
5530 ListBase *nurbs = BKE_curve_editNurbs_get(cu);
5531
5532 if (nurbs) {
5533 for (nu = nurbs->first; nu; nu = nu->next) {
5534 MAT_NR_REMAP(nu->mat_nr);
5535 }
5536 }
5537 }
5538
5539 #undef MAT_NR_REMAP
5540 }
5541
BKE_curve_smooth_flag_set(Curve * cu,const bool use_smooth)5542 void BKE_curve_smooth_flag_set(Curve *cu, const bool use_smooth)
5543 {
5544 if (use_smooth) {
5545 for (Nurb *nu = cu->nurb.first; nu; nu = nu->next) {
5546 nu->flag |= CU_SMOOTH;
5547 }
5548 }
5549 else {
5550 for (Nurb *nu = cu->nurb.first; nu; nu = nu->next) {
5551 nu->flag &= ~CU_SMOOTH;
5552 }
5553 }
5554 }
5555
BKE_curve_rect_from_textbox(const struct Curve * cu,const struct TextBox * tb,struct rctf * r_rect)5556 void BKE_curve_rect_from_textbox(const struct Curve *cu,
5557 const struct TextBox *tb,
5558 struct rctf *r_rect)
5559 {
5560 r_rect->xmin = cu->xof + tb->x;
5561 r_rect->ymax = cu->yof + tb->y + cu->fsize;
5562
5563 r_rect->xmax = r_rect->xmin + tb->w;
5564 r_rect->ymin = r_rect->ymax - tb->h;
5565 }
5566
5567 /* This function is almost the same as BKE_fcurve_correct_bezpart(), but doesn't allow as large a
5568 * tangent. */
BKE_curve_correct_bezpart(const float v1[2],float v2[2],float v3[2],const float v4[2])5569 void BKE_curve_correct_bezpart(const float v1[2], float v2[2], float v3[2], const float v4[2])
5570 {
5571 float h1[2], h2[2], len1, len2, len, fac;
5572
5573 /* Calculate handle deltas. */
5574 h1[0] = v1[0] - v2[0];
5575 h1[1] = v1[1] - v2[1];
5576
5577 h2[0] = v4[0] - v3[0];
5578 h2[1] = v4[1] - v3[1];
5579
5580 /* Calculate distances:
5581 * - len = span of time between keyframes
5582 * - len1 = length of handle of start key
5583 * - len2 = length of handle of end key
5584 */
5585 len = v4[0] - v1[0];
5586 len1 = fabsf(h1[0]);
5587 len2 = fabsf(h2[0]);
5588
5589 /* If the handles have no length, no need to do any corrections. */
5590 if ((len1 + len2) == 0.0f) {
5591 return;
5592 }
5593
5594 /* the two handles cross over each other, so force them
5595 * apart using the proportion they overlap
5596 */
5597 if ((len1 + len2) > len) {
5598 fac = len / (len1 + len2);
5599
5600 v2[0] = (v1[0] - fac * h1[0]);
5601 v2[1] = (v1[1] - fac * h1[1]);
5602
5603 v3[0] = (v4[0] - fac * h2[0]);
5604 v3[1] = (v4[1] - fac * h2[1]);
5605 }
5606 }
5607
5608 /* **** Depsgraph evaluation **** */
5609
BKE_curve_eval_geometry(Depsgraph * depsgraph,Curve * curve)5610 void BKE_curve_eval_geometry(Depsgraph *depsgraph, Curve *curve)
5611 {
5612 DEG_debug_print_eval(depsgraph, __func__, curve->id.name, curve);
5613 BKE_curve_texspace_calc(curve);
5614 if (DEG_is_active(depsgraph)) {
5615 Curve *curve_orig = (Curve *)DEG_get_original_id(&curve->id);
5616 if (curve->texflag & CU_AUTOSPACE_EVALUATED) {
5617 curve_orig->texflag |= CU_AUTOSPACE_EVALUATED;
5618 copy_v3_v3(curve_orig->loc, curve->loc);
5619 copy_v3_v3(curve_orig->size, curve->size);
5620 }
5621 }
5622 }
5623
5624 /* Draw Engine */
5625 void (*BKE_curve_batch_cache_dirty_tag_cb)(Curve *cu, int mode) = NULL;
5626 void (*BKE_curve_batch_cache_free_cb)(Curve *cu) = NULL;
5627
BKE_curve_batch_cache_dirty_tag(Curve * cu,int mode)5628 void BKE_curve_batch_cache_dirty_tag(Curve *cu, int mode)
5629 {
5630 if (cu->batch_cache) {
5631 BKE_curve_batch_cache_dirty_tag_cb(cu, mode);
5632 }
5633 }
BKE_curve_batch_cache_free(Curve * cu)5634 void BKE_curve_batch_cache_free(Curve *cu)
5635 {
5636 if (cu->batch_cache) {
5637 BKE_curve_batch_cache_free_cb(cu);
5638 }
5639 }
5640