Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / curve.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/curve.c
29  *  \ingroup bke
30  */
31
32
33 #include <math.h>  // floor
34 #include <string.h>
35 #include <stdlib.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_blenlib.h"
40 #include "BLI_math.h"
41 #include "BLI_utildefines.h"
42 #include "BLI_ghash.h"
43
44 #include "DNA_anim_types.h"
45 #include "DNA_curve_types.h"
46 #include "DNA_material_types.h"
47
48 /* for dereferencing pointers */
49 #include "DNA_key_types.h"
50 #include "DNA_scene_types.h"
51 #include "DNA_vfont_types.h"
52 #include "DNA_object_types.h"
53
54 #include "BKE_animsys.h"
55 #include "BKE_curve.h"
56 #include "BKE_displist.h"
57 #include "BKE_font.h"
58 #include "BKE_global.h"
59 #include "BKE_key.h"
60 #include "BKE_library.h"
61 #include "BKE_library_query.h"
62 #include "BKE_library_remap.h"
63 #include "BKE_main.h"
64 #include "BKE_object.h"
65 #include "BKE_material.h"
66
67 #include "DEG_depsgraph.h"
68
69 /* globals */
70
71 /* local */
72 static int cu_isectLL(const float v1[3], const float v2[3], const float v3[3], const float v4[3],
73                       short cox, short coy,
74                       float *lambda, float *mu, float vec[3]);
75
76 /* frees editcurve entirely */
77 void BKE_curve_editfont_free(Curve *cu)
78 {
79         if (cu->editfont) {
80                 EditFont *ef = cu->editfont;
81
82                 if (ef->textbuf)
83                         MEM_freeN(ef->textbuf);
84                 if (ef->textbufinfo)
85                         MEM_freeN(ef->textbufinfo);
86                 if (ef->selboxes)
87                         MEM_freeN(ef->selboxes);
88
89                 MEM_freeN(ef);
90                 cu->editfont = NULL;
91         }
92 }
93
94 static void curve_editNurb_keyIndex_cv_free_cb(void *val)
95 {
96         CVKeyIndex *index = val;
97         MEM_freeN(index->orig_cv);
98         MEM_freeN(val);
99 }
100
101 void BKE_curve_editNurb_keyIndex_delCV(GHash *keyindex, const void *cv)
102 {
103         BLI_assert(keyindex != NULL);
104         BLI_ghash_remove(keyindex, cv, NULL, curve_editNurb_keyIndex_cv_free_cb);
105 }
106
107 void BKE_curve_editNurb_keyIndex_free(GHash **keyindex)
108 {
109         if (!(*keyindex)) {
110                 return;
111         }
112         BLI_ghash_free(*keyindex, NULL, curve_editNurb_keyIndex_cv_free_cb);
113         *keyindex = NULL;
114 }
115
116 void BKE_curve_editNurb_free(Curve *cu)
117 {
118         if (cu->editnurb) {
119                 BKE_nurbList_free(&cu->editnurb->nurbs);
120                 BKE_curve_editNurb_keyIndex_free(&cu->editnurb->keyindex);
121                 MEM_freeN(cu->editnurb);
122                 cu->editnurb = NULL;
123         }
124 }
125
126 /** Free (or release) any data used by this curve (does not free the curve itself). */
127 void BKE_curve_free(Curve *cu)
128 {
129         BKE_animdata_free((ID *)cu, false);
130
131         BKE_curve_batch_cache_free(cu);
132
133         BKE_nurbList_free(&cu->nurb);
134         BKE_curve_editfont_free(cu);
135
136         BKE_curve_editNurb_free(cu);
137
138         MEM_SAFE_FREE(cu->mat);
139         MEM_SAFE_FREE(cu->str);
140         MEM_SAFE_FREE(cu->strinfo);
141         MEM_SAFE_FREE(cu->bb);
142         MEM_SAFE_FREE(cu->tb);
143 }
144
145 void BKE_curve_init(Curve *cu)
146 {
147         /* BLI_assert(MEMCMP_STRUCT_OFS_IS_ZERO(cu, id)); */  /* cu->type is already initialized... */
148
149         copy_v3_fl(cu->size, 1.0f);
150         cu->flag = CU_FRONT | CU_BACK | CU_DEFORM_BOUNDS_OFF | CU_PATH_RADIUS;
151         cu->pathlen = 100;
152         cu->resolu = cu->resolv = (cu->type == OB_SURF) ? 4 : 12;
153         cu->width = 1.0;
154         cu->wordspace = 1.0;
155         cu->spacing = cu->linedist = 1.0;
156         cu->fsize = 1.0;
157         cu->ulheight = 0.05;
158         cu->texflag = CU_AUTOSPACE;
159         cu->smallcaps_scale = 0.75f;
160         /* XXX: this one seems to be the best one in most cases, at least for curve deform... */
161         cu->twist_mode = CU_TWIST_MINIMUM;
162         cu->bevfac1 = 0.0f;
163         cu->bevfac2 = 1.0f;
164         cu->bevfac1_mapping = CU_BEVFAC_MAP_RESOLU;
165         cu->bevfac2_mapping = CU_BEVFAC_MAP_RESOLU;
166
167         cu->bb = BKE_boundbox_alloc_unit();
168
169         if (cu->type == OB_FONT) {
170                 cu->vfont = cu->vfontb = cu->vfonti = cu->vfontbi = BKE_vfont_builtin_get();
171                 cu->vfont->id.us += 4;
172                 cu->str = MEM_malloc_arrayN(12, sizeof(unsigned char), "str");
173                 BLI_strncpy(cu->str, "Text", 12);
174                 cu->len = cu->len_wchar = cu->pos = 4;
175                 cu->strinfo = MEM_calloc_arrayN(12, sizeof(CharInfo), "strinfo new");
176                 cu->totbox = cu->actbox = 1;
177                 cu->tb = MEM_calloc_arrayN(MAXTEXTBOX, sizeof(TextBox), "textbox");
178                 cu->tb[0].w = cu->tb[0].h = 0.0;
179         }
180 }
181
182 Curve *BKE_curve_add(Main *bmain, const char *name, int type)
183 {
184         Curve *cu;
185
186         cu = BKE_libblock_alloc(bmain, ID_CU, name, 0);
187         cu->type = type;
188
189         BKE_curve_init(cu);
190
191         return cu;
192 }
193
194 /**
195  * Only copy internal data of Curve ID from source to already allocated/initialized destination.
196  * You probably nerver want to use that directly, use id_copy or BKE_id_copy_ex for typical needs.
197  *
198  * WARNING! This function will not handle ID user count!
199  *
200  * \param flag  Copying options (see BKE_library.h's LIB_ID_COPY_... flags for more).
201  */
202 void BKE_curve_copy_data(Main *bmain, Curve *cu_dst, const Curve *cu_src, const int flag)
203 {
204         BLI_listbase_clear(&cu_dst->nurb);
205         BKE_nurbList_duplicate(&(cu_dst->nurb), &(cu_src->nurb));
206
207         cu_dst->mat = MEM_dupallocN(cu_src->mat);
208
209         cu_dst->str = MEM_dupallocN(cu_src->str);
210         cu_dst->strinfo = MEM_dupallocN(cu_src->strinfo);
211         cu_dst->tb = MEM_dupallocN(cu_src->tb);
212         cu_dst->bb = MEM_dupallocN(cu_src->bb);
213         cu_dst->batch_cache = NULL;
214
215         if (cu_src->key) {
216                 BKE_id_copy_ex(bmain, &cu_src->key->id, (ID **)&cu_dst->key, flag, false);
217         }
218
219         cu_dst->editnurb = NULL;
220         cu_dst->editfont = NULL;
221 }
222
223 Curve *BKE_curve_copy(Main *bmain, const Curve *cu)
224 {
225         Curve *cu_copy;
226         BKE_id_copy_ex(bmain, &cu->id, (ID **)&cu_copy, 0, false);
227         return cu_copy;
228 }
229
230 void BKE_curve_make_local(Main *bmain, Curve *cu, const bool lib_local)
231 {
232         BKE_id_make_local_generic(bmain, &cu->id, true, lib_local);
233 }
234
235 /* Get list of nurbs from editnurbs structure */
236 ListBase *BKE_curve_editNurbs_get(Curve *cu)
237 {
238         if (cu->editnurb) {
239                 return &cu->editnurb->nurbs;
240         }
241
242         return NULL;
243 }
244
245 short BKE_curve_type_get(Curve *cu)
246 {
247         Nurb *nu;
248         int type = cu->type;
249
250         if (cu->vfont) {
251                 return OB_FONT;
252         }
253
254         if (!cu->type) {
255                 type = OB_CURVE;
256
257                 for (nu = cu->nurb.first; nu; nu = nu->next) {
258                         if (nu->pntsv > 1) {
259                                 type = OB_SURF;
260                         }
261                 }
262         }
263
264         return type;
265 }
266
267 void BKE_curve_curve_dimension_update(Curve *cu)
268 {
269         ListBase *nurbs = BKE_curve_nurbs_get(cu);
270         Nurb *nu = nurbs->first;
271
272         if (cu->flag & CU_3D) {
273                 for (; nu; nu = nu->next) {
274                         nu->flag &= ~CU_2D;
275                 }
276         }
277         else {
278                 for (; nu; nu = nu->next) {
279                         nu->flag |= CU_2D;
280                         BKE_nurb_test2D(nu);
281
282                         /* since the handles are moved they need to be auto-located again */
283                         if (nu->type == CU_BEZIER)
284                                 BKE_nurb_handles_calc(nu);
285                 }
286         }
287 }
288
289 void BKE_curve_type_test(Object *ob)
290 {
291         ob->type = BKE_curve_type_get(ob->data);
292
293         if (ob->type == OB_CURVE)
294                 BKE_curve_curve_dimension_update((Curve *)ob->data);
295 }
296
297 void BKE_curve_boundbox_calc(Curve *cu, float r_loc[3], float r_size[3])
298 {
299         BoundBox *bb;
300         float min[3], max[3];
301         float mloc[3], msize[3];
302
303         if (cu->bb == NULL) cu->bb = MEM_callocN(sizeof(BoundBox), "boundbox");
304         bb = cu->bb;
305
306         if (!r_loc) r_loc = mloc;
307         if (!r_size) r_size = msize;
308
309         INIT_MINMAX(min, max);
310         if (!BKE_curve_minmax(cu, true, min, max)) {
311                 min[0] = min[1] = min[2] = -1.0f;
312                 max[0] = max[1] = max[2] = 1.0f;
313         }
314
315         mid_v3_v3v3(r_loc, min, max);
316
317         r_size[0] = (max[0] - min[0]) / 2.0f;
318         r_size[1] = (max[1] - min[1]) / 2.0f;
319         r_size[2] = (max[2] - min[2]) / 2.0f;
320
321         BKE_boundbox_init_from_minmax(bb, min, max);
322
323         bb->flag &= ~BOUNDBOX_DIRTY;
324 }
325
326 BoundBox *BKE_curve_boundbox_get(Object *ob)
327 {
328         Curve *cu = ob->data;
329
330         if (ob->bb)
331                 return ob->bb;
332
333         if (cu->bb == NULL || (cu->bb->flag & BOUNDBOX_DIRTY)) {
334                 BKE_curve_texspace_calc(cu);
335         }
336
337         return cu->bb;
338 }
339
340 void BKE_curve_texspace_calc(Curve *cu)
341 {
342         float loc[3], size[3];
343         int a;
344
345         BKE_curve_boundbox_calc(cu, loc, size);
346
347         if (cu->texflag & CU_AUTOSPACE) {
348                 for (a = 0; a < 3; a++) {
349                         if (size[a] == 0.0f) size[a] = 1.0f;
350                         else if (size[a] > 0.0f && size[a] < 0.00001f) size[a] = 0.00001f;
351                         else if (size[a] < 0.0f && size[a] > -0.00001f) size[a] = -0.00001f;
352                 }
353
354                 copy_v3_v3(cu->loc, loc);
355                 copy_v3_v3(cu->size, size);
356                 zero_v3(cu->rot);
357         }
358 }
359
360 void BKE_curve_texspace_get(Curve *cu, float r_loc[3], float r_rot[3], float r_size[3])
361 {
362         if (cu->bb == NULL || (cu->bb->flag & BOUNDBOX_DIRTY)) {
363                 BKE_curve_texspace_calc(cu);
364         }
365
366         if (r_loc) copy_v3_v3(r_loc,  cu->loc);
367         if (r_rot) copy_v3_v3(r_rot,  cu->rot);
368         if (r_size) copy_v3_v3(r_size, cu->size);
369 }
370
371 bool BKE_nurbList_index_get_co(ListBase *nurb, const int index, float r_co[3])
372 {
373         Nurb *nu;
374         int tot = 0;
375
376         for (nu = nurb->first; nu; nu = nu->next) {
377                 int tot_nu;
378                 if (nu->type == CU_BEZIER) {
379                         tot_nu = nu->pntsu;
380                         if (index - tot < tot_nu) {
381                                 copy_v3_v3(r_co, nu->bezt[index - tot].vec[1]);
382                                 return true;
383                         }
384                 }
385                 else {
386                         tot_nu = nu->pntsu * nu->pntsv;
387                         if (index - tot < tot_nu) {
388                                 copy_v3_v3(r_co, nu->bp[index - tot].vec);
389                                 return true;
390                         }
391                 }
392                 tot += tot_nu;
393         }
394
395         return false;
396 }
397
398 int BKE_nurbList_verts_count(ListBase *nurb)
399 {
400         Nurb *nu;
401         int tot = 0;
402
403         nu = nurb->first;
404         while (nu) {
405                 if (nu->bezt)
406                         tot += 3 * nu->pntsu;
407                 else if (nu->bp)
408                         tot += nu->pntsu * nu->pntsv;
409
410                 nu = nu->next;
411         }
412         return tot;
413 }
414
415 int BKE_nurbList_verts_count_without_handles(ListBase *nurb)
416 {
417         Nurb *nu;
418         int tot = 0;
419
420         nu = nurb->first;
421         while (nu) {
422                 if (nu->bezt)
423                         tot += nu->pntsu;
424                 else if (nu->bp)
425                         tot += nu->pntsu * nu->pntsv;
426
427                 nu = nu->next;
428         }
429         return tot;
430 }
431
432 /* **************** NURBS ROUTINES ******************** */
433
434 void BKE_nurb_free(Nurb *nu)
435 {
436
437         if (nu == NULL) return;
438
439         if (nu->bezt)
440                 MEM_freeN(nu->bezt);
441         nu->bezt = NULL;
442         if (nu->bp)
443                 MEM_freeN(nu->bp);
444         nu->bp = NULL;
445         if (nu->knotsu)
446                 MEM_freeN(nu->knotsu);
447         nu->knotsu = NULL;
448         if (nu->knotsv)
449                 MEM_freeN(nu->knotsv);
450         nu->knotsv = NULL;
451         /* if (nu->trim.first) freeNurblist(&(nu->trim)); */
452
453         MEM_freeN(nu);
454
455 }
456
457
458 void BKE_nurbList_free(ListBase *lb)
459 {
460         Nurb *nu, *next;
461
462         if (lb == NULL) return;
463
464         nu = lb->first;
465         while (nu) {
466                 next = nu->next;
467                 BKE_nurb_free(nu);
468                 nu = next;
469         }
470         BLI_listbase_clear(lb);
471 }
472
473 Nurb *BKE_nurb_duplicate(const Nurb *nu)
474 {
475         Nurb *newnu;
476         int len;
477
478         newnu = (Nurb *)MEM_mallocN(sizeof(Nurb), "duplicateNurb");
479         if (newnu == NULL) return NULL;
480         memcpy(newnu, nu, sizeof(Nurb));
481
482         if (nu->bezt) {
483                 newnu->bezt =
484                     (BezTriple *)MEM_malloc_arrayN(nu->pntsu, sizeof(BezTriple), "duplicateNurb2");
485                 memcpy(newnu->bezt, nu->bezt, nu->pntsu * sizeof(BezTriple));
486         }
487         else {
488                 len = nu->pntsu * nu->pntsv;
489                 newnu->bp =
490                     (BPoint *)MEM_malloc_arrayN(len, sizeof(BPoint), "duplicateNurb3");
491                 memcpy(newnu->bp, nu->bp, len * sizeof(BPoint));
492
493                 newnu->knotsu = newnu->knotsv = NULL;
494
495                 if (nu->knotsu) {
496                         len = KNOTSU(nu);
497                         if (len) {
498                                 newnu->knotsu = MEM_malloc_arrayN(len, sizeof(float), "duplicateNurb4");
499                                 memcpy(newnu->knotsu, nu->knotsu, sizeof(float) * len);
500                         }
501                 }
502                 if (nu->pntsv > 1 && nu->knotsv) {
503                         len = KNOTSV(nu);
504                         if (len) {
505                                 newnu->knotsv = MEM_malloc_arrayN(len, sizeof(float), "duplicateNurb5");
506                                 memcpy(newnu->knotsv, nu->knotsv, sizeof(float) * len);
507                         }
508                 }
509         }
510         return newnu;
511 }
512
513 /* copy the nurb but allow for different number of points (to be copied after this) */
514 Nurb *BKE_nurb_copy(Nurb *src, int pntsu, int pntsv)
515 {
516         Nurb *newnu = (Nurb *)MEM_mallocN(sizeof(Nurb), "copyNurb");
517         memcpy(newnu, src, sizeof(Nurb));
518
519         if (pntsu == 1) SWAP(int, pntsu, pntsv);
520         newnu->pntsu = pntsu;
521         newnu->pntsv = pntsv;
522
523         /* caller can manually handle these arrays */
524         newnu->knotsu = NULL;
525         newnu->knotsv = NULL;
526
527         if (src->bezt) {
528                 newnu->bezt = (BezTriple *)MEM_malloc_arrayN(pntsu * pntsv, sizeof(BezTriple), "copyNurb2");
529         }
530         else {
531                 newnu->bp = (BPoint *)MEM_malloc_arrayN(pntsu * pntsv, sizeof(BPoint), "copyNurb3");
532         }
533
534         return newnu;
535 }
536
537 void BKE_nurbList_duplicate(ListBase *lb1, const ListBase *lb2)
538 {
539         Nurb *nu, *nun;
540
541         BKE_nurbList_free(lb1);
542
543         nu = lb2->first;
544         while (nu) {
545                 nun = BKE_nurb_duplicate(nu);
546                 BLI_addtail(lb1, nun);
547
548                 nu = nu->next;
549         }
550 }
551
552 void BKE_nurb_test2D(Nurb *nu)
553 {
554         BezTriple *bezt;
555         BPoint *bp;
556         int a;
557
558         if ((nu->flag & CU_2D) == 0)
559                 return;
560
561         if (nu->type == CU_BEZIER) {
562                 a = nu->pntsu;
563                 bezt = nu->bezt;
564                 while (a--) {
565                         bezt->vec[0][2] = 0.0;
566                         bezt->vec[1][2] = 0.0;
567                         bezt->vec[2][2] = 0.0;
568                         bezt++;
569                 }
570         }
571         else {
572                 a = nu->pntsu * nu->pntsv;
573                 bp = nu->bp;
574                 while (a--) {
575                         bp->vec[2] = 0.0;
576                         bp++;
577                 }
578         }
579 }
580
581 /**
582  * if use_radius is truth, minmax will take points' radius into account,
583  * which will make boundbox closer to beveled curve.
584  */
585 void BKE_nurb_minmax(Nurb *nu, bool use_radius, float min[3], float max[3])
586 {
587         BezTriple *bezt;
588         BPoint *bp;
589         int a;
590         float point[3];
591
592         if (nu->type == CU_BEZIER) {
593                 a = nu->pntsu;
594                 bezt = nu->bezt;
595                 while (a--) {
596                         if (use_radius) {
597                                 float radius_vector[3];
598                                 radius_vector[0] = radius_vector[1] = radius_vector[2] = bezt->radius;
599
600                                 add_v3_v3v3(point, bezt->vec[1], radius_vector);
601                                 minmax_v3v3_v3(min, max, point);
602
603                                 sub_v3_v3v3(point, bezt->vec[1], radius_vector);
604                                 minmax_v3v3_v3(min, max, point);
605                         }
606                         else {
607                                 minmax_v3v3_v3(min, max, bezt->vec[1]);
608                         }
609                         minmax_v3v3_v3(min, max, bezt->vec[0]);
610                         minmax_v3v3_v3(min, max, bezt->vec[2]);
611                         bezt++;
612                 }
613         }
614         else {
615                 a = nu->pntsu * nu->pntsv;
616                 bp = nu->bp;
617                 while (a--) {
618                         if (nu->pntsv == 1 && use_radius) {
619                                 float radius_vector[3];
620                                 radius_vector[0] = radius_vector[1] = radius_vector[2] = bp->radius;
621
622                                 add_v3_v3v3(point, bp->vec, radius_vector);
623                                 minmax_v3v3_v3(min, max, point);
624
625                                 sub_v3_v3v3(point, bp->vec, radius_vector);
626                                 minmax_v3v3_v3(min, max, point);
627                         }
628                         else {
629                                 /* Surfaces doesn't use bevel, so no need to take radius into account. */
630                                 minmax_v3v3_v3(min, max, bp->vec);
631                         }
632                         bp++;
633                 }
634         }
635 }
636
637 /* be sure to call makeknots after this */
638 void BKE_nurb_points_add(Nurb *nu, int number)
639 {
640         BPoint *bp;
641         int i;
642
643         nu->bp = MEM_recallocN(nu->bp, (nu->pntsu + number) * sizeof(BPoint));
644
645         for (i = 0, bp = &nu->bp[nu->pntsu]; i < number; i++, bp++) {
646                 bp->radius = 1.0f;
647         }
648
649         nu->pntsu += number;
650 }
651
652 void BKE_nurb_bezierPoints_add(Nurb *nu, int number)
653 {
654         BezTriple *bezt;
655         int i;
656
657         nu->bezt = MEM_recallocN(nu->bezt, (nu->pntsu + number) * sizeof(BezTriple));
658
659         for (i = 0, bezt = &nu->bezt[nu->pntsu]; i < number; i++, bezt++) {
660                 bezt->radius = 1.0f;
661         }
662
663         nu->pntsu += number;
664 }
665
666
667 int BKE_nurb_index_from_uv(
668         Nurb *nu,
669         int u, int v)
670 {
671         const int totu = nu->pntsu;
672         const int totv = nu->pntsv;
673
674         if (nu->flagu & CU_NURB_CYCLIC) {
675                 u = mod_i(u, totu);
676         }
677         else if (u < 0 || u >= totu) {
678                 return -1;
679         }
680
681         if (nu->flagv & CU_NURB_CYCLIC) {
682                 v = mod_i(v, totv);
683         }
684         else if (v < 0 || v >= totv) {
685                 return -1;
686         }
687
688         return (v * totu) + u;
689 }
690
691 void BKE_nurb_index_to_uv(
692         Nurb *nu, int index,
693         int *r_u, int *r_v)
694 {
695         const int totu = nu->pntsu;
696         const int totv = nu->pntsv;
697         BLI_assert(index >= 0 && index < (nu->pntsu * nu->pntsv));
698         *r_u = (index % totu);
699         *r_v = (index / totu) % totv;
700 }
701
702 BezTriple *BKE_nurb_bezt_get_next(Nurb *nu, BezTriple *bezt)
703 {
704         BezTriple *bezt_next;
705
706         BLI_assert(ARRAY_HAS_ITEM(bezt, nu->bezt, nu->pntsu));
707
708         if (bezt == &nu->bezt[nu->pntsu - 1]) {
709                 if (nu->flagu & CU_NURB_CYCLIC) {
710                         bezt_next = nu->bezt;
711                 }
712                 else {
713                         bezt_next = NULL;
714                 }
715         }
716         else {
717                 bezt_next = bezt + 1;
718         }
719
720         return bezt_next;
721 }
722
723 BPoint *BKE_nurb_bpoint_get_next(Nurb *nu, BPoint *bp)
724 {
725         BPoint *bp_next;
726
727         BLI_assert(ARRAY_HAS_ITEM(bp, nu->bp, nu->pntsu));
728
729         if (bp == &nu->bp[nu->pntsu - 1]) {
730                 if (nu->flagu & CU_NURB_CYCLIC) {
731                         bp_next = nu->bp;
732                 }
733                 else {
734                         bp_next = NULL;
735                 }
736         }
737         else {
738                 bp_next = bp + 1;
739         }
740
741         return bp_next;
742 }
743
744 BezTriple *BKE_nurb_bezt_get_prev(Nurb *nu, BezTriple *bezt)
745 {
746         BezTriple *bezt_prev;
747
748         BLI_assert(ARRAY_HAS_ITEM(bezt, nu->bezt, nu->pntsu));
749         BLI_assert(nu->pntsv <= 1);
750
751         if (bezt == nu->bezt) {
752                 if (nu->flagu & CU_NURB_CYCLIC) {
753                         bezt_prev = &nu->bezt[nu->pntsu - 1];
754                 }
755                 else {
756                         bezt_prev = NULL;
757                 }
758         }
759         else {
760                 bezt_prev = bezt - 1;
761         }
762
763         return bezt_prev;
764 }
765
766 BPoint *BKE_nurb_bpoint_get_prev(Nurb *nu, BPoint *bp)
767 {
768         BPoint *bp_prev;
769
770         BLI_assert(ARRAY_HAS_ITEM(bp, nu->bp, nu->pntsu));
771         BLI_assert(nu->pntsv == 1);
772
773         if (bp == nu->bp) {
774                 if (nu->flagu & CU_NURB_CYCLIC) {
775                         bp_prev = &nu->bp[nu->pntsu - 1];
776                 }
777                 else {
778                         bp_prev = NULL;
779                 }
780         }
781         else {
782                 bp_prev = bp - 1;
783         }
784
785         return bp_prev;
786 }
787
788 void BKE_nurb_bezt_calc_normal(struct Nurb *UNUSED(nu), BezTriple *bezt, float r_normal[3])
789 {
790         /* calculate the axis matrix from the spline */
791         float dir_prev[3], dir_next[3];
792
793         sub_v3_v3v3(dir_prev, bezt->vec[0], bezt->vec[1]);
794         sub_v3_v3v3(dir_next, bezt->vec[1], bezt->vec[2]);
795
796         normalize_v3(dir_prev);
797         normalize_v3(dir_next);
798
799         add_v3_v3v3(r_normal, dir_prev, dir_next);
800         normalize_v3(r_normal);
801 }
802
803 void BKE_nurb_bezt_calc_plane(struct Nurb *nu, BezTriple *bezt, float r_plane[3])
804 {
805         float dir_prev[3], dir_next[3];
806
807         sub_v3_v3v3(dir_prev, bezt->vec[0], bezt->vec[1]);
808         sub_v3_v3v3(dir_next, bezt->vec[1], bezt->vec[2]);
809
810         normalize_v3(dir_prev);
811         normalize_v3(dir_next);
812
813         cross_v3_v3v3(r_plane, dir_prev, dir_next);
814         if (normalize_v3(r_plane) < FLT_EPSILON) {
815                 BezTriple *bezt_prev = BKE_nurb_bezt_get_prev(nu, bezt);
816                 BezTriple *bezt_next = BKE_nurb_bezt_get_next(nu, bezt);
817
818                 if (bezt_prev) {
819                         sub_v3_v3v3(dir_prev, bezt_prev->vec[1], bezt->vec[1]);
820                         normalize_v3(dir_prev);
821                 }
822                 if (bezt_next) {
823                         sub_v3_v3v3(dir_next, bezt->vec[1], bezt_next->vec[1]);
824                         normalize_v3(dir_next);
825                 }
826                 cross_v3_v3v3(r_plane, dir_prev, dir_next);
827         }
828
829         /* matches with bones more closely */
830         {
831                 float dir_mid[3], tvec[3];
832                 add_v3_v3v3(dir_mid, dir_prev, dir_next);
833                 cross_v3_v3v3(tvec, r_plane, dir_mid);
834                 copy_v3_v3(r_plane, tvec);
835         }
836
837         normalize_v3(r_plane);
838 }
839
840 void BKE_nurb_bpoint_calc_normal(struct Nurb *nu, BPoint *bp, float r_normal[3])
841 {
842         BPoint *bp_prev = BKE_nurb_bpoint_get_prev(nu, bp);
843         BPoint *bp_next = BKE_nurb_bpoint_get_next(nu, bp);
844
845         zero_v3(r_normal);
846
847         if (bp_prev) {
848                 float dir_prev[3];
849                 sub_v3_v3v3(dir_prev, bp_prev->vec, bp->vec);
850                 normalize_v3(dir_prev);
851                 add_v3_v3(r_normal, dir_prev);
852         }
853         if (bp_next) {
854                 float dir_next[3];
855                 sub_v3_v3v3(dir_next, bp->vec, bp_next->vec);
856                 normalize_v3(dir_next);
857                 add_v3_v3(r_normal, dir_next);
858         }
859
860         normalize_v3(r_normal);
861 }
862
863 void BKE_nurb_bpoint_calc_plane(struct Nurb *nu, BPoint *bp, float r_plane[3])
864 {
865         BPoint *bp_prev = BKE_nurb_bpoint_get_prev(nu, bp);
866         BPoint *bp_next = BKE_nurb_bpoint_get_next(nu, bp);
867
868         float dir_prev[3] = {0.0f}, dir_next[3] = {0.0f};
869
870         if (bp_prev) {
871                 sub_v3_v3v3(dir_prev, bp_prev->vec, bp->vec);
872                 normalize_v3(dir_prev);
873         }
874         if (bp_next) {
875                 sub_v3_v3v3(dir_next, bp->vec, bp_next->vec);
876                 normalize_v3(dir_next);
877         }
878         cross_v3_v3v3(r_plane, dir_prev, dir_next);
879
880         /* matches with bones more closely */
881         {
882                 float dir_mid[3], tvec[3];
883                 add_v3_v3v3(dir_mid, dir_prev, dir_next);
884                 cross_v3_v3v3(tvec, r_plane, dir_mid);
885                 copy_v3_v3(r_plane, tvec);
886         }
887
888         normalize_v3(r_plane);
889 }
890
891 /* ~~~~~~~~~~~~~~~~~~~~Non Uniform Rational B Spline calculations ~~~~~~~~~~~ */
892
893
894 static void calcknots(float *knots, const int pnts, const short order, const short flag)
895 {
896         /* knots: number of pnts NOT corrected for cyclic */
897         const int pnts_order = pnts + order;
898         float k;
899         int a;
900
901         switch (flag & (CU_NURB_ENDPOINT | CU_NURB_BEZIER)) {
902                 case CU_NURB_ENDPOINT:
903                         k = 0.0;
904                         for (a = 1; a <= pnts_order; a++) {
905                                 knots[a - 1] = k;
906                                 if (a >= order && a <= pnts)
907                                         k += 1.0f;
908                         }
909                         break;
910                 case CU_NURB_BEZIER:
911                         /* Warning, the order MUST be 2 or 4,
912                          * if this is not enforced, the displist will be corrupt */
913                         if (order == 4) {
914                                 k = 0.34;
915                                 for (a = 0; a < pnts_order; a++) {
916                                         knots[a] = floorf(k);
917                                         k += (1.0f / 3.0f);
918                                 }
919                         }
920                         else if (order == 3) {
921                                 k = 0.6f;
922                                 for (a = 0; a < pnts_order; a++) {
923                                         if (a >= order && a <= pnts)
924                                                 k += 0.5f;
925                                         knots[a] = floorf(k);
926                                 }
927                         }
928                         else {
929                                 printf("bez nurb curve order is not 3 or 4, should never happen\n");
930                         }
931                         break;
932                 default:
933                         for (a = 0; a < pnts_order; a++) {
934                                 knots[a] = (float)a;
935                         }
936                         break;
937         }
938 }
939
940 static void makecyclicknots(float *knots, int pnts, short order)
941 /* pnts, order: number of pnts NOT corrected for cyclic */
942 {
943         int a, b, order2, c;
944
945         if (knots == NULL)
946                 return;
947
948         order2 = order - 1;
949
950         /* do first long rows (order -1), remove identical knots at endpoints */
951         if (order > 2) {
952                 b = pnts + order2;
953                 for (a = 1; a < order2; a++) {
954                         if (knots[b] != knots[b - a])
955                                 break;
956                 }
957                 if (a == order2)
958                         knots[pnts + order - 2] += 1.0f;
959         }
960
961         b = order;
962         c = pnts + order + order2;
963         for (a = pnts + order2; a < c; a++) {
964                 knots[a] = knots[a - 1] + (knots[b] - knots[b - 1]);
965                 b--;
966         }
967 }
968
969
970
971 static void makeknots(Nurb *nu, short uv)
972 {
973         if (nu->type == CU_NURBS) {
974                 if (uv == 1) {
975                         if (nu->knotsu)
976                                 MEM_freeN(nu->knotsu);
977                         if (BKE_nurb_check_valid_u(nu)) {
978                                 nu->knotsu = MEM_calloc_arrayN(KNOTSU(nu) + 1, sizeof(float), "makeknots");
979                                 if (nu->flagu & CU_NURB_CYCLIC) {
980                                         calcknots(nu->knotsu, nu->pntsu, nu->orderu, 0);  /* cyclic should be uniform */
981                                         makecyclicknots(nu->knotsu, nu->pntsu, nu->orderu);
982                                 }
983                                 else {
984                                         calcknots(nu->knotsu, nu->pntsu, nu->orderu, nu->flagu);
985                                 }
986                         }
987                         else
988                                 nu->knotsu = NULL;
989                 }
990                 else if (uv == 2) {
991                         if (nu->knotsv)
992                                 MEM_freeN(nu->knotsv);
993                         if (BKE_nurb_check_valid_v(nu)) {
994                                 nu->knotsv = MEM_calloc_arrayN(KNOTSV(nu) + 1, sizeof(float), "makeknots");
995                                 if (nu->flagv & CU_NURB_CYCLIC) {
996                                         calcknots(nu->knotsv, nu->pntsv, nu->orderv, 0);  /* cyclic should be uniform */
997                                         makecyclicknots(nu->knotsv, nu->pntsv, nu->orderv);
998                                 }
999                                 else {
1000                                         calcknots(nu->knotsv, nu->pntsv, nu->orderv, nu->flagv);
1001                                 }
1002                         }
1003                         else {
1004                                 nu->knotsv = NULL;
1005                         }
1006                 }
1007         }
1008 }
1009
1010 void BKE_nurb_knot_calc_u(Nurb *nu)
1011 {
1012         makeknots(nu, 1);
1013 }
1014
1015 void BKE_nurb_knot_calc_v(Nurb *nu)
1016 {
1017         makeknots(nu, 2);
1018 }
1019
1020 static void basisNurb(float t, short order, int pnts, float *knots, float *basis, int *start, int *end)
1021 {
1022         float d, e;
1023         int i, i1 = 0, i2 = 0, j, orderpluspnts, opp2, o2;
1024
1025         orderpluspnts = order + pnts;
1026         opp2 = orderpluspnts - 1;
1027
1028         /* this is for float inaccuracy */
1029         if (t < knots[0])
1030                 t = knots[0];
1031         else if (t > knots[opp2]) 
1032                 t = knots[opp2];
1033
1034         /* this part is order '1' */
1035         o2 = order + 1;
1036         for (i = 0; i < opp2; i++) {
1037                 if (knots[i] != knots[i + 1] && t >= knots[i] && t <= knots[i + 1]) {
1038                         basis[i] = 1.0;
1039                         i1 = i - o2;
1040                         if (i1 < 0) i1 = 0;
1041                         i2 = i;
1042                         i++;
1043                         while (i < opp2) {
1044                                 basis[i] = 0.0;
1045                                 i++;
1046                         }
1047                         break;
1048                 }
1049                 else
1050                         basis[i] = 0.0;
1051         }
1052         basis[i] = 0.0;
1053
1054         /* this is order 2, 3, ... */
1055         for (j = 2; j <= order; j++) {
1056
1057                 if (i2 + j >= orderpluspnts) i2 = opp2 - j;
1058
1059                 for (i = i1; i <= i2; i++) {
1060                         if (basis[i] != 0.0f)
1061                                 d = ((t - knots[i]) * basis[i]) / (knots[i + j - 1] - knots[i]);
1062                         else
1063                                 d = 0.0f;
1064
1065                         if (basis[i + 1] != 0.0f)
1066                                 e = ((knots[i + j] - t) * basis[i + 1]) / (knots[i + j] - knots[i + 1]);
1067                         else
1068                                 e = 0.0;
1069
1070                         basis[i] = d + e;
1071                 }
1072         }
1073
1074         *start = 1000;
1075         *end = 0;
1076
1077         for (i = i1; i <= i2; i++) {
1078                 if (basis[i] > 0.0f) {
1079                         *end = i;
1080                         if (*start == 1000) *start = i;
1081                 }
1082         }
1083 }
1084
1085
1086 void BKE_nurb_makeFaces(Nurb *nu, float *coord_array, int rowstride, int resolu, int resolv)
1087 /* coord_array  has to be (3 * 4 * resolu * resolv) in size, and zero-ed */
1088 {
1089         BPoint *bp;
1090         float *basisu, *basis, *basisv, *sum, *fp, *in;
1091         float u, v, ustart, uend, ustep, vstart, vend, vstep, sumdiv;
1092         int i, j, iofs, jofs, cycl, len, curu, curv;
1093         int istart, iend, jsta, jen, *jstart, *jend, ratcomp;
1094
1095         int totu = nu->pntsu * resolu, totv = nu->pntsv * resolv;
1096
1097         if (nu->knotsu == NULL || nu->knotsv == NULL)
1098                 return;
1099         if (nu->orderu > nu->pntsu)
1100                 return;
1101         if (nu->orderv > nu->pntsv)
1102                 return;
1103         if (coord_array == NULL)
1104                 return;
1105
1106         /* allocate and initialize */
1107         len = totu * totv;
1108         if (len == 0)
1109                 return;
1110
1111         sum = (float *)MEM_calloc_arrayN(len, sizeof(float), "makeNurbfaces1");
1112
1113         bp = nu->bp;
1114         i = nu->pntsu * nu->pntsv;
1115         ratcomp = 0;
1116         while (i--) {
1117                 if (bp->vec[3] != 1.0f) {
1118                         ratcomp = 1;
1119                         break;
1120                 }
1121                 bp++;
1122         }
1123
1124         fp = nu->knotsu;
1125         ustart = fp[nu->orderu - 1];
1126         if (nu->flagu & CU_NURB_CYCLIC)
1127                 uend = fp[nu->pntsu + nu->orderu - 1];
1128         else
1129                 uend = fp[nu->pntsu];
1130         ustep = (uend - ustart) / ((nu->flagu & CU_NURB_CYCLIC) ? totu : totu - 1);
1131
1132         basisu = (float *)MEM_malloc_arrayN(KNOTSU(nu), sizeof(float), "makeNurbfaces3");
1133
1134         fp = nu->knotsv;
1135         vstart = fp[nu->orderv - 1];
1136
1137         if (nu->flagv & CU_NURB_CYCLIC)
1138                 vend = fp[nu->pntsv + nu->orderv - 1];
1139         else
1140                 vend = fp[nu->pntsv];
1141         vstep = (vend - vstart) / ((nu->flagv & CU_NURB_CYCLIC) ? totv : totv - 1);
1142
1143         len = KNOTSV(nu);
1144         basisv = (float *)MEM_malloc_arrayN(len * totv, sizeof(float), "makeNurbfaces3");
1145         jstart = (int *)MEM_malloc_arrayN(totv, sizeof(float), "makeNurbfaces4");
1146         jend = (int *)MEM_malloc_arrayN(totv, sizeof(float), "makeNurbfaces5");
1147
1148         /* precalculation of basisv and jstart, jend */
1149         if (nu->flagv & CU_NURB_CYCLIC)
1150                 cycl = nu->orderv - 1;
1151         else cycl = 0;
1152         v = vstart;
1153         basis = basisv;
1154         curv = totv;
1155         while (curv--) {
1156                 basisNurb(v, nu->orderv, nu->pntsv + cycl, nu->knotsv, basis, jstart + curv, jend + curv);
1157                 basis += KNOTSV(nu);
1158                 v += vstep;
1159         }
1160
1161         if (nu->flagu & CU_NURB_CYCLIC)
1162                 cycl = nu->orderu - 1;
1163         else
1164                 cycl = 0;
1165         in = coord_array;
1166         u = ustart;
1167         curu = totu;
1168         while (curu--) {
1169                 basisNurb(u, nu->orderu, nu->pntsu + cycl, nu->knotsu, basisu, &istart, &iend);
1170
1171                 basis = basisv;
1172                 curv = totv;
1173                 while (curv--) {
1174                         jsta = jstart[curv];
1175                         jen = jend[curv];
1176
1177                         /* calculate sum */
1178                         sumdiv = 0.0;
1179                         fp = sum;
1180
1181                         for (j = jsta; j <= jen; j++) {
1182
1183                                 if (j >= nu->pntsv)
1184                                         jofs = (j - nu->pntsv);
1185                                 else
1186                                         jofs = j;
1187                                 bp = nu->bp + nu->pntsu * jofs + istart - 1;
1188
1189                                 for (i = istart; i <= iend; i++, fp++) {
1190                                         if (i >= nu->pntsu) {
1191                                                 iofs = i - nu->pntsu;
1192                                                 bp = nu->bp + nu->pntsu * jofs + iofs;
1193                                         }
1194                                         else
1195                                                 bp++;
1196
1197                                         if (ratcomp) {
1198                                                 *fp = basisu[i] * basis[j] * bp->vec[3];
1199                                                 sumdiv += *fp;
1200                                         }
1201                                         else
1202                                                 *fp = basisu[i] * basis[j];
1203                                 }
1204                         }
1205
1206                         if (ratcomp) {
1207                                 fp = sum;
1208                                 for (j = jsta; j <= jen; j++) {
1209                                         for (i = istart; i <= iend; i++, fp++) {
1210                                                 *fp /= sumdiv;
1211                                         }
1212                                 }
1213                         }
1214
1215                         zero_v3(in);
1216
1217                         /* one! (1.0) real point now */
1218                         fp = sum;
1219                         for (j = jsta; j <= jen; j++) {
1220
1221                                 if (j >= nu->pntsv)
1222                                         jofs = (j - nu->pntsv);
1223                                 else
1224                                         jofs = j;
1225                                 bp = nu->bp + nu->pntsu * jofs + istart - 1;
1226
1227                                 for (i = istart; i <= iend; i++, fp++) {
1228                                         if (i >= nu->pntsu) {
1229                                                 iofs = i - nu->pntsu;
1230                                                 bp = nu->bp + nu->pntsu * jofs + iofs;
1231                                         }
1232                                         else
1233                                                 bp++;
1234
1235                                         if (*fp != 0.0f) {
1236                                                 madd_v3_v3fl(in, bp->vec, *fp);
1237                                         }
1238                                 }
1239                         }
1240
1241                         in += 3;
1242                         basis += KNOTSV(nu);
1243                 }
1244                 u += ustep;
1245                 if (rowstride != 0) {
1246                         in = (float *)(((unsigned char *)in) + (rowstride - 3 * totv * sizeof(*in)));
1247                 }
1248         }
1249
1250         /* free */
1251         MEM_freeN(sum);
1252         MEM_freeN(basisu);
1253         MEM_freeN(basisv);
1254         MEM_freeN(jstart);
1255         MEM_freeN(jend);
1256 }
1257
1258 /**
1259  * \param coord_array Has to be 3 * 4 * pntsu * resolu in size and zero-ed
1260  * \param tilt_array   set when non-NULL
1261  * \param radius_array set when non-NULL
1262  */
1263 void BKE_nurb_makeCurve(Nurb *nu, float *coord_array, float *tilt_array, float *radius_array, float *weight_array,
1264                         int resolu, int stride)
1265 {
1266         const float eps = 1e-6f;
1267         BPoint *bp;
1268         float u, ustart, uend, ustep, sumdiv;
1269         float *basisu, *sum, *fp;
1270         float *coord_fp = coord_array, *tilt_fp = tilt_array, *radius_fp = radius_array, *weight_fp = weight_array;
1271         int i, len, istart, iend, cycl;
1272
1273         if (nu->knotsu == NULL)
1274                 return;
1275         if (nu->orderu > nu->pntsu)
1276                 return;
1277         if (coord_array == NULL)
1278                 return;
1279
1280         /* allocate and initialize */
1281         len = nu->pntsu;
1282         if (len == 0)
1283                 return;
1284         sum = (float *)MEM_calloc_arrayN(len, sizeof(float), "makeNurbcurve1");
1285
1286         resolu = (resolu * SEGMENTSU(nu));
1287
1288         if (resolu == 0) {
1289                 MEM_freeN(sum);
1290                 return;
1291         }
1292
1293         fp = nu->knotsu;
1294         ustart = fp[nu->orderu - 1];
1295         if (nu->flagu & CU_NURB_CYCLIC)
1296                 uend = fp[nu->pntsu + nu->orderu - 1];
1297         else
1298                 uend = fp[nu->pntsu];
1299         ustep = (uend - ustart) / (resolu - ((nu->flagu & CU_NURB_CYCLIC) ? 0 : 1));
1300
1301         basisu = (float *)MEM_malloc_arrayN(KNOTSU(nu), sizeof(float), "makeNurbcurve3");
1302
1303         if (nu->flagu & CU_NURB_CYCLIC)
1304                 cycl = nu->orderu - 1;
1305         else
1306                 cycl = 0;
1307
1308         u = ustart;
1309         while (resolu--) {
1310                 basisNurb(u, nu->orderu, nu->pntsu + cycl, nu->knotsu, basisu, &istart, &iend);
1311
1312                 /* calc sum */
1313                 sumdiv = 0.0;
1314                 fp = sum;
1315                 bp = nu->bp + istart - 1;
1316                 for (i = istart; i <= iend; i++, fp++) {
1317                         if (i >= nu->pntsu)
1318                                 bp = nu->bp + (i - nu->pntsu);
1319                         else
1320                                 bp++;
1321
1322                         *fp = basisu[i] * bp->vec[3];
1323                         sumdiv += *fp;
1324                 }
1325                 if ((sumdiv != 0.0f) && (sumdiv < 1.0f - eps || sumdiv > 1.0f + eps)) {
1326                         /* is normalizing needed? */
1327                         fp = sum;
1328                         for (i = istart; i <= iend; i++, fp++) {
1329                                 *fp /= sumdiv;
1330                         }
1331                 }
1332
1333                 zero_v3(coord_fp);
1334
1335                 /* one! (1.0) real point */
1336                 fp = sum;
1337                 bp = nu->bp + istart - 1;
1338                 for (i = istart; i <= iend; i++, fp++) {
1339                         if (i >= nu->pntsu)
1340                                 bp = nu->bp + (i - nu->pntsu);
1341                         else
1342                                 bp++;
1343
1344                         if (*fp != 0.0f) {
1345                                 madd_v3_v3fl(coord_fp, bp->vec, *fp);
1346
1347                                 if (tilt_fp)
1348                                         (*tilt_fp) += (*fp) * bp->alfa;
1349
1350                                 if (radius_fp)
1351                                         (*radius_fp) += (*fp) * bp->radius;
1352
1353                                 if (weight_fp)
1354                                         (*weight_fp) += (*fp) * bp->weight;
1355                         }
1356                 }
1357
1358                 coord_fp = POINTER_OFFSET(coord_fp, stride);
1359
1360                 if (tilt_fp)
1361                         tilt_fp = POINTER_OFFSET(tilt_fp, stride);
1362                 if (radius_fp)
1363                         radius_fp = POINTER_OFFSET(radius_fp, stride);
1364                 if (weight_fp)
1365                         weight_fp = POINTER_OFFSET(weight_fp, stride);
1366
1367                 u += ustep;
1368         }
1369
1370         /* free */
1371         MEM_freeN(sum);
1372         MEM_freeN(basisu);
1373 }
1374
1375 /**
1376  * Calculate the length for arrays filled in by #BKE_curve_calc_coords_axis.
1377  */
1378 unsigned int BKE_curve_calc_coords_axis_len(
1379         const unsigned int bezt_array_len, const unsigned int resolu,
1380         const bool is_cyclic, const bool use_cyclic_duplicate_endpoint)
1381 {
1382         const unsigned int segments = bezt_array_len - (is_cyclic ?  0 : 1);
1383         const unsigned int points_len = (segments * resolu) + (is_cyclic ? (use_cyclic_duplicate_endpoint) : 1);
1384         return points_len;
1385 }
1386
1387 /**
1388  * Calculate an array for the entire curve (cyclic or non-cyclic).
1389  * \note Call for each axis.
1390  *
1391  * \param use_cyclic_duplicate_endpoint: Duplicate values at the beginning & end of the array.
1392  */
1393 void BKE_curve_calc_coords_axis(
1394         const BezTriple *bezt_array, const unsigned int bezt_array_len, const unsigned int resolu,
1395         const bool is_cyclic, const bool use_cyclic_duplicate_endpoint,
1396         /* array params */
1397         const unsigned int axis, const unsigned int stride,
1398         float *r_points)
1399 {
1400         const unsigned int points_len = BKE_curve_calc_coords_axis_len(
1401                 bezt_array_len, resolu, is_cyclic, use_cyclic_duplicate_endpoint);
1402         float *r_points_offset = r_points;
1403
1404         const unsigned int resolu_stride = resolu * stride;
1405         const unsigned int bezt_array_last = bezt_array_len - 1;
1406
1407         for (unsigned int i = 0; i < bezt_array_last; i++) {
1408                 const BezTriple *bezt_curr = &bezt_array[i];
1409                 const BezTriple *bezt_next = &bezt_array[i + 1];
1410                 BKE_curve_forward_diff_bezier(
1411                         bezt_curr->vec[1][axis], bezt_curr->vec[2][axis],
1412                         bezt_next->vec[0][axis], bezt_next->vec[1][axis],
1413                         r_points_offset, (int)resolu, stride);
1414                 r_points_offset = POINTER_OFFSET(r_points_offset, resolu_stride);
1415         }
1416
1417         if (is_cyclic) {
1418                 const BezTriple *bezt_curr = &bezt_array[bezt_array_last];
1419                 const BezTriple *bezt_next = &bezt_array[0];
1420                 BKE_curve_forward_diff_bezier(
1421                         bezt_curr->vec[1][axis], bezt_curr->vec[2][axis],
1422                         bezt_next->vec[0][axis], bezt_next->vec[1][axis],
1423                         r_points_offset, (int)resolu, stride);
1424                 r_points_offset = POINTER_OFFSET(r_points_offset, resolu_stride);
1425                 if (use_cyclic_duplicate_endpoint) {
1426                         *r_points_offset = *r_points;
1427                         r_points_offset = POINTER_OFFSET(r_points_offset, stride);
1428                 }
1429         }
1430         else {
1431                 float *r_points_last = POINTER_OFFSET(r_points, bezt_array_last * resolu_stride);
1432                 *r_points_last = bezt_array[bezt_array_last].vec[1][axis];
1433                 r_points_offset = POINTER_OFFSET(r_points_offset, stride);
1434         }
1435
1436         BLI_assert(POINTER_OFFSET(r_points, points_len * stride) == r_points_offset);
1437         UNUSED_VARS_NDEBUG(points_len);
1438 }
1439
1440 /* forward differencing method for bezier curve */
1441 void BKE_curve_forward_diff_bezier(float q0, float q1, float q2, float q3, float *p, int it, int stride)
1442 {
1443         float rt0, rt1, rt2, rt3, f;
1444         int a;
1445
1446         f = (float)it;
1447         rt0 = q0;
1448         rt1 = 3.0f * (q1 - q0) / f;
1449         f *= f;
1450         rt2 = 3.0f * (q0 - 2.0f * q1 + q2) / f;
1451         f *= it;
1452         rt3 = (q3 - q0 + 3.0f * (q1 - q2)) / f;
1453
1454         q0 = rt0;
1455         q1 = rt1 + rt2 + rt3;
1456         q2 = 2 * rt2 + 6 * rt3;
1457         q3 = 6 * rt3;
1458
1459         for (a = 0; a <= it; a++) {
1460                 *p = q0;
1461                 p = POINTER_OFFSET(p, stride);
1462                 q0 += q1;
1463                 q1 += q2;
1464                 q2 += q3;
1465         }
1466 }
1467
1468 /* forward differencing method for first derivative of cubic bezier curve */
1469 void BKE_curve_forward_diff_tangent_bezier(float q0, float q1, float q2, float q3, float *p, int it, int stride)
1470 {
1471         float rt0, rt1, rt2, f;
1472         int a;
1473
1474         f = 1.0f / (float)it;
1475
1476         rt0 = 3.0f * (q1 - q0);
1477         rt1 = f * (3.0f * (q3 - q0) + 9.0f * (q1 - q2));
1478         rt2 = 6.0f * (q0 + q2) - 12.0f * q1;
1479
1480         q0 = rt0;
1481         q1 = f * (rt1 + rt2);
1482         q2 = 2.0f * f * rt1;
1483
1484         for (a = 0; a <= it; a++) {
1485                 *p = q0;
1486                 p = POINTER_OFFSET(p, stride);
1487                 q0 += q1;
1488                 q1 += q2;
1489         }
1490 }
1491
1492 static void forward_diff_bezier_cotangent(const float p0[3], const float p1[3], const float p2[3], const float p3[3],
1493                                           float p[3], int it, int stride)
1494 {
1495         /* note that these are not perpendicular to the curve
1496          * they need to be rotated for this,
1497          *
1498          * This could also be optimized like BKE_curve_forward_diff_bezier */
1499         int a;
1500         for (a = 0; a <= it; a++) {
1501                 float t = (float)a / (float)it;
1502
1503                 int i;
1504                 for (i = 0; i < 3; i++) {
1505                         p[i] = (-6.0f  * t +  6.0f) * p0[i] +
1506                                ( 18.0f * t - 12.0f) * p1[i] +
1507                                (-18.0f * t +  6.0f) * p2[i] +
1508                                ( 6.0f  * t)         * p3[i];
1509                 }
1510                 normalize_v3(p);
1511                 p = POINTER_OFFSET(p, stride);
1512         }
1513 }
1514
1515 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
1516
1517 float *BKE_curve_surf_make_orco(Object *ob)
1518 {
1519         /* Note: this function is used in convertblender only atm, so
1520          * suppose nonzero curve's render resolution should always be used */
1521         Curve *cu = ob->data;
1522         Nurb *nu;
1523         int a, b, tot = 0;
1524         int sizeu, sizev;
1525         int resolu, resolv;
1526         float *fp, *coord_array;
1527
1528         /* first calculate the size of the datablock */
1529         nu = cu->nurb.first;
1530         while (nu) {
1531                 /* as we want to avoid the seam in a cyclic nurbs
1532                  * texture wrapping, reserve extra orco data space to save these extra needed
1533                  * vertex based UV coordinates for the meridian vertices.
1534                  * Vertices on the 0/2pi boundary are not duplicated inside the displist but later in
1535                  * the renderface/vert construction.
1536                  *
1537                  * See also convertblender.c: init_render_surf()
1538                  */
1539
1540                 resolu = cu->resolu_ren ? cu->resolu_ren : nu->resolu;
1541                 resolv = cu->resolv_ren ? cu->resolv_ren : nu->resolv;
1542
1543                 sizeu = nu->pntsu * resolu;
1544                 sizev = nu->pntsv * resolv;
1545                 if (nu->flagu & CU_NURB_CYCLIC) sizeu++;
1546                 if (nu->flagv & CU_NURB_CYCLIC) sizev++;
1547                 if (nu->pntsv > 1) tot += sizeu * sizev;
1548
1549                 nu = nu->next;
1550         }
1551         /* makeNurbfaces wants zeros */
1552         fp = coord_array = MEM_calloc_arrayN(tot, 3 * sizeof(float), "make_orco");
1553
1554         nu = cu->nurb.first;
1555         while (nu) {
1556                 resolu = cu->resolu_ren ? cu->resolu_ren : nu->resolu;
1557                 resolv = cu->resolv_ren ? cu->resolv_ren : nu->resolv;
1558
1559                 if (nu->pntsv > 1) {
1560                         sizeu = nu->pntsu * resolu;
1561                         sizev = nu->pntsv * resolv;
1562
1563                         if (nu->flagu & CU_NURB_CYCLIC)
1564                                 sizeu++;
1565                         if (nu->flagv & CU_NURB_CYCLIC)
1566                                 sizev++;
1567
1568                         if (cu->flag & CU_UV_ORCO) {
1569                                 for (b = 0; b < sizeu; b++) {
1570                                         for (a = 0; a < sizev; a++) {
1571
1572                                                 if (sizev < 2)
1573                                                         fp[0] = 0.0f;
1574                                                 else
1575                                                         fp[0] = -1.0f + 2.0f * ((float)a) / (sizev - 1);
1576
1577                                                 if (sizeu < 2)
1578                                                         fp[1] = 0.0f;
1579                                                 else
1580                                                         fp[1] = -1.0f + 2.0f * ((float)b) / (sizeu - 1);
1581
1582                                                 fp[2] = 0.0;
1583
1584                                                 fp += 3;
1585                                         }
1586                                 }
1587                         }
1588                         else {
1589                                 int size = (nu->pntsu * resolu) * (nu->pntsv * resolv) * 3 * sizeof(float);
1590                                 float *_tdata = MEM_mallocN(size, "temp data");
1591                                 float *tdata = _tdata;
1592
1593                                 BKE_nurb_makeFaces(nu, tdata, 0, resolu, resolv);
1594
1595                                 for (b = 0; b < sizeu; b++) {
1596                                         int use_b = b;
1597                                         if (b == sizeu - 1 && (nu->flagu & CU_NURB_CYCLIC))
1598                                                 use_b = false;
1599
1600                                         for (a = 0; a < sizev; a++) {
1601                                                 int use_a = a;
1602                                                 if (a == sizev - 1 && (nu->flagv & CU_NURB_CYCLIC))
1603                                                         use_a = false;
1604
1605                                                 tdata = _tdata + 3 * (use_b * (nu->pntsv * resolv) + use_a);
1606
1607                                                 fp[0] = (tdata[0] - cu->loc[0]) / cu->size[0];
1608                                                 fp[1] = (tdata[1] - cu->loc[1]) / cu->size[1];
1609                                                 fp[2] = (tdata[2] - cu->loc[2]) / cu->size[2];
1610                                                 fp += 3;
1611                                         }
1612                                 }
1613
1614                                 MEM_freeN(_tdata);
1615                         }
1616                 }
1617                 nu = nu->next;
1618         }
1619
1620         return coord_array;
1621 }
1622
1623
1624 /* NOTE: This routine is tied to the order of vertex
1625  * built by displist and as passed to the renderer.
1626  */
1627 float *BKE_curve_make_orco(const EvaluationContext *eval_ctx, Scene *scene, Object *ob, int *r_numVerts)
1628 {
1629         Curve *cu = ob->data;
1630         DispList *dl;
1631         int u, v, numVerts;
1632         float *fp, *coord_array;
1633         ListBase disp = {NULL, NULL};
1634
1635         BKE_displist_make_curveTypes_forOrco(eval_ctx, scene, ob, &disp);
1636
1637         numVerts = 0;
1638         for (dl = disp.first; dl; dl = dl->next) {
1639                 if (dl->type == DL_INDEX3) {
1640                         numVerts += dl->nr;
1641                 }
1642                 else if (dl->type == DL_SURF) {
1643                         /* convertblender.c uses the Surface code for creating renderfaces when cyclic U only
1644                          * (closed circle beveling)
1645                          */
1646                         if (dl->flag & DL_CYCL_U) {
1647                                 if (dl->flag & DL_CYCL_V)
1648                                         numVerts += (dl->parts + 1) * (dl->nr + 1);
1649                                 else
1650                                         numVerts += dl->parts * (dl->nr + 1);
1651                         }
1652                         else if (dl->flag & DL_CYCL_V) {
1653                                 numVerts += (dl->parts + 1) * dl->nr;
1654                         }
1655                         else
1656                                 numVerts += dl->parts * dl->nr;
1657                 }
1658         }
1659
1660         if (r_numVerts)
1661                 *r_numVerts = numVerts;
1662
1663         fp = coord_array = MEM_malloc_arrayN(numVerts, 3 * sizeof(float), "cu_orco");
1664         for (dl = disp.first; dl; dl = dl->next) {
1665                 if (dl->type == DL_INDEX3) {
1666                         for (u = 0; u < dl->nr; u++, fp += 3) {
1667                                 if (cu->flag & CU_UV_ORCO) {
1668                                         fp[0] = 2.0f * u / (dl->nr - 1) - 1.0f;
1669                                         fp[1] = 0.0;
1670                                         fp[2] = 0.0;
1671                                 }
1672                                 else {
1673                                         copy_v3_v3(fp, &dl->verts[u * 3]);
1674
1675                                         fp[0] = (fp[0] - cu->loc[0]) / cu->size[0];
1676                                         fp[1] = (fp[1] - cu->loc[1]) / cu->size[1];
1677                                         fp[2] = (fp[2] - cu->loc[2]) / cu->size[2];
1678                                 }
1679                         }
1680                 }
1681                 else if (dl->type == DL_SURF) {
1682                         int sizeu = dl->nr, sizev = dl->parts;
1683
1684                         /* exception as handled in convertblender.c too */
1685                         if (dl->flag & DL_CYCL_U) {
1686                                 sizeu++;
1687                                 if (dl->flag & DL_CYCL_V)
1688                                         sizev++;
1689                         }
1690                         else if (dl->flag & DL_CYCL_V) {
1691                                 sizev++;
1692                         }
1693
1694                         for (u = 0; u < sizev; u++) {
1695                                 for (v = 0; v < sizeu; v++, fp += 3) {
1696                                         if (cu->flag & CU_UV_ORCO) {
1697                                                 fp[0] = 2.0f * u / (sizev - 1) - 1.0f;
1698                                                 fp[1] = 2.0f * v / (sizeu - 1) - 1.0f;
1699                                                 fp[2] = 0.0;
1700                                         }
1701                                         else {
1702                                                 const float *vert;
1703                                                 int realv = v % dl->nr;
1704                                                 int realu = u % dl->parts;
1705
1706                                                 vert = dl->verts + 3 * (dl->nr * realu + realv);
1707                                                 copy_v3_v3(fp, vert);
1708
1709                                                 fp[0] = (fp[0] - cu->loc[0]) / cu->size[0];
1710                                                 fp[1] = (fp[1] - cu->loc[1]) / cu->size[1];
1711                                                 fp[2] = (fp[2] - cu->loc[2]) / cu->size[2];
1712                                         }
1713                                 }
1714                         }
1715                 }
1716         }
1717
1718         BKE_displist_free(&disp);
1719
1720         return coord_array;
1721 }
1722
1723
1724 /* ***************** BEVEL ****************** */
1725
1726 void BKE_curve_bevel_make(
1727         const EvaluationContext *eval_ctx, Scene *scene, Object *ob, ListBase *disp,
1728         const bool for_render, const bool use_render_resolution)
1729 {
1730         DispList *dl, *dlnew;
1731         Curve *bevcu, *cu;
1732         float *fp, facx, facy, angle, dangle;
1733         int nr, a;
1734
1735         cu = ob->data;
1736         BLI_listbase_clear(disp);
1737
1738         /* if a font object is being edited, then do nothing */
1739 // XXX  if ( ob == obedit && ob->type == OB_FONT ) return;
1740
1741         if (cu->bevobj) {
1742                 if (cu->bevobj->type != OB_CURVE)
1743                         return;
1744
1745                 bevcu = cu->bevobj->data;
1746                 if (bevcu->ext1 == 0.0f && bevcu->ext2 == 0.0f) {
1747                         ListBase bevdisp = {NULL, NULL};
1748                         facx = cu->bevobj->size[0];
1749                         facy = cu->bevobj->size[1];
1750
1751                         if (for_render) {
1752                                 BKE_displist_make_curveTypes_forRender(eval_ctx, scene, cu->bevobj, &bevdisp, NULL, false, use_render_resolution);
1753                                 dl = bevdisp.first;
1754                         }
1755                         else if (cu->bevobj->curve_cache) {
1756                                 dl = cu->bevobj->curve_cache->disp.first;
1757                         }
1758                         else {
1759                                 BLI_assert(cu->bevobj->curve_cache != NULL);
1760                                 dl = NULL;
1761                         }
1762
1763                         while (dl) {
1764                                 if (ELEM(dl->type, DL_POLY, DL_SEGM)) {
1765                                         dlnew = MEM_mallocN(sizeof(DispList), "makebevelcurve1");
1766                                         *dlnew = *dl;
1767                                         dlnew->verts = MEM_malloc_arrayN(dl->parts * dl->nr, 3 * sizeof(float), "makebevelcurve1");
1768                                         memcpy(dlnew->verts, dl->verts, 3 * sizeof(float) * dl->parts * dl->nr);
1769
1770                                         if (dlnew->type == DL_SEGM)
1771                                                 dlnew->flag |= (DL_FRONT_CURVE | DL_BACK_CURVE);
1772
1773                                         BLI_addtail(disp, dlnew);
1774                                         fp = dlnew->verts;
1775                                         nr = dlnew->parts * dlnew->nr;
1776                                         while (nr--) {
1777                                                 fp[2] = fp[1] * facy;
1778                                                 fp[1] = -fp[0] * facx;
1779                                                 fp[0] = 0.0;
1780                                                 fp += 3;
1781                                         }
1782                                 }
1783                                 dl = dl->next;
1784                         }
1785
1786                         BKE_displist_free(&bevdisp);
1787                 }
1788         }
1789         else if (cu->ext1 == 0.0f && cu->ext2 == 0.0f) {
1790                 /* pass */
1791         }
1792         else if (cu->ext2 == 0.0f) {
1793                 dl = MEM_callocN(sizeof(DispList), "makebevelcurve2");
1794                 dl->verts = MEM_malloc_arrayN(2, sizeof(float[3]), "makebevelcurve2");
1795                 BLI_addtail(disp, dl);
1796                 dl->type = DL_SEGM;
1797                 dl->parts = 1;
1798                 dl->flag = DL_FRONT_CURVE | DL_BACK_CURVE;
1799                 dl->nr = 2;
1800
1801                 fp = dl->verts;
1802                 fp[0] = fp[1] = 0.0;
1803                 fp[2] = -cu->ext1;
1804                 fp[3] = fp[4] = 0.0;
1805                 fp[5] = cu->ext1;
1806         }
1807         else if ((cu->flag & (CU_FRONT | CU_BACK)) == 0 && cu->ext1 == 0.0f) {  /* we make a full round bevel in that case */
1808                 nr = 4 + 2 * cu->bevresol;
1809
1810                 dl = MEM_callocN(sizeof(DispList), "makebevelcurve p1");
1811                 dl->verts = MEM_malloc_arrayN(nr, sizeof(float[3]), "makebevelcurve p1");
1812                 BLI_addtail(disp, dl);
1813                 dl->type = DL_POLY;
1814                 dl->parts = 1;
1815                 dl->flag = DL_BACK_CURVE;
1816                 dl->nr = nr;
1817
1818                 /* a circle */
1819                 fp = dl->verts;
1820                 dangle = (2.0f * (float)M_PI / (nr));
1821                 angle = -(nr - 1) * dangle;
1822
1823                 for (a = 0; a < nr; a++) {
1824                         fp[0] = 0.0;
1825                         fp[1] = (cosf(angle) * (cu->ext2));
1826                         fp[2] = (sinf(angle) * (cu->ext2)) - cu->ext1;
1827                         angle += dangle;
1828                         fp += 3;
1829                 }
1830         }
1831         else {
1832                 short dnr;
1833
1834                 /* bevel now in three parts, for proper vertex normals */
1835                 /* part 1, back */
1836
1837                 if ((cu->flag & CU_BACK) || !(cu->flag & CU_FRONT)) {
1838                         dnr = nr = 2 + cu->bevresol;
1839                         if ((cu->flag & (CU_FRONT | CU_BACK)) == 0) {
1840                                 nr = 3 + 2 * cu->bevresol;
1841                         }
1842                         dl = MEM_callocN(sizeof(DispList), "makebevelcurve p1");
1843                         dl->verts = MEM_malloc_arrayN(nr, sizeof(float[3]), "makebevelcurve p1");
1844                         BLI_addtail(disp, dl);
1845                         dl->type = DL_SEGM;
1846                         dl->parts = 1;
1847                         dl->flag = DL_BACK_CURVE;
1848                         dl->nr = nr;
1849
1850                         /* half a circle */
1851                         fp = dl->verts;
1852                         dangle = ((float)M_PI_2 / (dnr - 1));
1853                         angle = -(nr - 1) * dangle;
1854
1855                         for (a = 0; a < nr; a++) {
1856                                 fp[0] = 0.0;
1857                                 fp[1] = (float)(cosf(angle) * (cu->ext2));
1858                                 fp[2] = (float)(sinf(angle) * (cu->ext2)) - cu->ext1;
1859                                 angle += dangle;
1860                                 fp += 3;
1861                         }
1862                 }
1863
1864                 /* part 2, sidefaces */
1865                 if (cu->ext1 != 0.0f) {
1866                         nr = 2;
1867
1868                         dl = MEM_callocN(sizeof(DispList), "makebevelcurve p2");
1869                         dl->verts = MEM_malloc_arrayN(nr, sizeof(float[3]), "makebevelcurve p2");
1870                         BLI_addtail(disp, dl);
1871                         dl->type = DL_SEGM;
1872                         dl->parts = 1;
1873                         dl->nr = nr;
1874
1875                         fp = dl->verts;
1876                         fp[1] = cu->ext2;
1877                         fp[2] = -cu->ext1;
1878                         fp[4] = cu->ext2;
1879                         fp[5] = cu->ext1;
1880
1881                         if ((cu->flag & (CU_FRONT | CU_BACK)) == 0) {
1882                                 dl = MEM_dupallocN(dl);
1883                                 dl->verts = MEM_dupallocN(dl->verts);
1884                                 BLI_addtail(disp, dl);
1885
1886                                 fp = dl->verts;
1887                                 fp[1] = -fp[1];
1888                                 fp[2] = -fp[2];
1889                                 fp[4] = -fp[4];
1890                                 fp[5] = -fp[5];
1891                         }
1892                 }
1893
1894                 /* part 3, front */
1895                 if ((cu->flag & CU_FRONT) || !(cu->flag & CU_BACK)) {
1896                         dnr = nr = 2 + cu->bevresol;
1897                         if ((cu->flag & (CU_FRONT | CU_BACK)) == 0) {
1898                                 nr = 3 + 2 * cu->bevresol;
1899                         }
1900                         dl = MEM_callocN(sizeof(DispList), "makebevelcurve p3");
1901                         dl->verts = MEM_malloc_arrayN(nr, sizeof(float[3]), "makebevelcurve p3");
1902                         BLI_addtail(disp, dl);
1903                         dl->type = DL_SEGM;
1904                         dl->flag = DL_FRONT_CURVE;
1905                         dl->parts = 1;
1906                         dl->nr = nr;
1907
1908                         /* half a circle */
1909                         fp = dl->verts;
1910                         angle = 0.0;
1911                         dangle = ((float)M_PI_2 / (dnr - 1));
1912
1913                         for (a = 0; a < nr; a++) {
1914                                 fp[0] = 0.0;
1915                                 fp[1] = (float)(cosf(angle) * (cu->ext2));
1916                                 fp[2] = (float)(sinf(angle) * (cu->ext2)) + cu->ext1;
1917                                 angle += dangle;
1918                                 fp += 3;
1919                         }
1920                 }
1921         }
1922 }
1923
1924 static int cu_isectLL(const float v1[3], const float v2[3], const float v3[3], const float v4[3],
1925                       short cox, short coy,
1926                       float *lambda, float *mu, float vec[3])
1927 {
1928         /* return:
1929          * -1: collinear
1930          *  0: no intersection of segments
1931          *  1: exact intersection of segments
1932          *  2: cross-intersection of segments
1933          */
1934         float deler;
1935
1936         deler = (v1[cox] - v2[cox]) * (v3[coy] - v4[coy]) - (v3[cox] - v4[cox]) * (v1[coy] - v2[coy]);
1937         if (deler == 0.0f)
1938                 return -1;
1939
1940         *lambda = (v1[coy] - v3[coy]) * (v3[cox] - v4[cox]) - (v1[cox] - v3[cox]) * (v3[coy] - v4[coy]);
1941         *lambda = -(*lambda / deler);
1942
1943         deler = v3[coy] - v4[coy];
1944         if (deler == 0) {
1945                 deler = v3[cox] - v4[cox];
1946                 *mu = -(*lambda * (v2[cox] - v1[cox]) + v1[cox] - v3[cox]) / deler;
1947         }
1948         else {
1949                 *mu = -(*lambda * (v2[coy] - v1[coy]) + v1[coy] - v3[coy]) / deler;
1950         }
1951         vec[cox] = *lambda * (v2[cox] - v1[cox]) + v1[cox];
1952         vec[coy] = *lambda * (v2[coy] - v1[coy]) + v1[coy];
1953
1954         if (*lambda >= 0.0f && *lambda <= 1.0f && *mu >= 0.0f && *mu <= 1.0f) {
1955                 if (*lambda == 0.0f || *lambda == 1.0f || *mu == 0.0f || *mu == 1.0f)
1956                         return 1;
1957                 return 2;
1958         }
1959         return 0;
1960 }
1961
1962
1963 static bool bevelinside(BevList *bl1, BevList *bl2)
1964 {
1965         /* is bl2 INSIDE bl1 ? with left-right method and "lambda's" */
1966         /* returns '1' if correct hole  */
1967         BevPoint *bevp, *prevbevp;
1968         float min, max, vec[3], hvec1[3], hvec2[3], lab, mu;
1969         int nr, links = 0, rechts = 0, mode;
1970
1971         /* take first vertex of possible hole */
1972
1973         bevp = bl2->bevpoints;
1974         hvec1[0] = bevp->vec[0];
1975         hvec1[1] = bevp->vec[1];
1976         hvec1[2] = 0.0;
1977         copy_v3_v3(hvec2, hvec1);
1978         hvec2[0] += 1000;
1979
1980         /* test it with all edges of potential surounding poly */
1981         /* count number of transitions left-right  */
1982
1983         bevp = bl1->bevpoints;
1984         nr = bl1->nr;
1985         prevbevp = bevp + (nr - 1);
1986
1987         while (nr--) {
1988                 min = prevbevp->vec[1];
1989                 max = bevp->vec[1];
1990                 if (max < min) {
1991                         min = max;
1992                         max = prevbevp->vec[1];
1993                 }
1994                 if (min != max) {
1995                         if (min <= hvec1[1] && max >= hvec1[1]) {
1996                                 /* there's a transition, calc intersection point */
1997                                 mode = cu_isectLL(prevbevp->vec, bevp->vec, hvec1, hvec2, 0, 1, &lab, &mu, vec);
1998                                 /* if lab==0.0 or lab==1.0 then the edge intersects exactly a transition
1999                                  * only allow for one situation: we choose lab= 1.0
2000                                  */
2001                                 if (mode >= 0 && lab != 0.0f) {
2002                                         if (vec[0] < hvec1[0]) links++;
2003                                         else rechts++;
2004                                 }
2005                         }
2006                 }
2007                 prevbevp = bevp;
2008                 bevp++;
2009         }
2010
2011         return (links & 1) && (rechts & 1);
2012 }
2013
2014
2015 struct BevelSort {
2016         BevList *bl;
2017         float left;
2018         int dir;
2019 };
2020
2021 static int vergxcobev(const void *a1, const void *a2)
2022 {
2023         const struct BevelSort *x1 = a1, *x2 = a2;
2024
2025         if (x1->left > x2->left)
2026                 return 1;
2027         else if (x1->left < x2->left)
2028                 return -1;
2029         return 0;
2030 }
2031
2032 /* this function cannot be replaced with atan2, but why? */
2033
2034 static void calc_bevel_sin_cos(float x1, float y1, float x2, float y2,
2035                                float *r_sina, float *r_cosa)
2036 {
2037         float t01, t02, x3, y3;
2038
2039         t01 = sqrtf(x1 * x1 + y1 * y1);
2040         t02 = sqrtf(x2 * x2 + y2 * y2);
2041         if (t01 == 0.0f)
2042                 t01 = 1.0f;
2043         if (t02 == 0.0f)
2044                 t02 = 1.0f;
2045
2046         x1 /= t01;
2047         y1 /= t01;
2048         x2 /= t02;
2049         y2 /= t02;
2050
2051         t02 = x1 * x2 + y1 * y2;
2052         if (fabsf(t02) >= 1.0f)
2053                 t02 = M_PI_2;
2054         else
2055                 t02 = (saacos(t02)) / 2.0f;
2056
2057         t02 = sinf(t02);
2058         if (t02 == 0.0f)
2059                 t02 = 1.0f;
2060
2061         x3 = x1 - x2;
2062         y3 = y1 - y2;
2063         if (x3 == 0 && y3 == 0) {
2064                 x3 = y1;
2065                 y3 = -x1;
2066         }
2067         else {
2068                 t01 = sqrtf(x3 * x3 + y3 * y3);
2069                 x3 /= t01;
2070                 y3 /= t01;
2071         }
2072
2073         *r_sina = -y3 / t02;
2074         *r_cosa =  x3 / t02;
2075
2076 }
2077
2078 static void alfa_bezpart(BezTriple *prevbezt, BezTriple *bezt, Nurb *nu, float *tilt_array, float *radius_array,
2079                          float *weight_array, int resolu, int stride)
2080 {
2081         BezTriple *pprev, *next, *last;
2082         float fac, dfac, t[4];
2083         int a;
2084
2085         if (tilt_array == NULL && radius_array == NULL)
2086                 return;
2087
2088         last = nu->bezt + (nu->pntsu - 1);
2089
2090         /* returns a point */
2091         if (prevbezt == nu->bezt) {
2092                 if (nu->flagu & CU_NURB_CYCLIC)
2093                         pprev = last;
2094                 else
2095                         pprev = prevbezt;
2096         }
2097         else
2098                 pprev = prevbezt - 1;
2099
2100         /* next point */
2101         if (bezt == last) {
2102                 if (nu->flagu & CU_NURB_CYCLIC)
2103                         next = nu->bezt;
2104                 else
2105                         next = bezt;
2106         }
2107         else
2108                 next = bezt + 1;
2109
2110         fac = 0.0;
2111         dfac = 1.0f / (float)resolu;
2112
2113         for (a = 0; a < resolu; a++, fac += dfac) {
2114                 if (tilt_array) {
2115                         if (nu->tilt_interp == KEY_CU_EASE) { /* May as well support for tilt also 2.47 ease interp */
2116                                 *tilt_array = prevbezt->alfa +
2117                                         (bezt->alfa - prevbezt->alfa) * (3.0f * fac * fac - 2.0f * fac * fac * fac);
2118                         }
2119                         else {
2120                                 key_curve_position_weights(fac, t, nu->tilt_interp);
2121                                 *tilt_array = t[0] * pprev->alfa + t[1] * prevbezt->alfa + t[2] * bezt->alfa + t[3] * next->alfa;
2122                         }
2123
2124                         tilt_array = POINTER_OFFSET(tilt_array, stride);
2125                 }
2126
2127                 if (radius_array) {
2128                         if (nu->radius_interp == KEY_CU_EASE) {
2129                                 /* Support 2.47 ease interp
2130                                  * Note! - this only takes the 2 points into account,
2131                                  * giving much more localized results to changes in radius, sometimes you want that */
2132                                 *radius_array = prevbezt->radius +
2133                                         (bezt->radius - prevbezt->radius) * (3.0f * fac * fac - 2.0f * fac * fac * fac);
2134                         }
2135                         else {
2136
2137                                 /* reuse interpolation from tilt if we can */
2138                                 if (tilt_array == NULL || nu->tilt_interp != nu->radius_interp) {
2139                                         key_curve_position_weights(fac, t, nu->radius_interp);
2140                                 }
2141                                 *radius_array = 
2142                                         t[0] * pprev->radius + t[1] * prevbezt->radius +
2143                                         t[2] * bezt->radius + t[3] * next->radius;
2144                         }
2145
2146                         radius_array = POINTER_OFFSET(radius_array, stride);
2147                 }
2148
2149                 if (weight_array) {
2150                         /* basic interpolation for now, could copy tilt interp too  */
2151                         *weight_array = 
2152                                 prevbezt->weight +
2153                                 (bezt->weight - prevbezt->weight) * (3.0f * fac * fac - 2.0f * fac * fac * fac);
2154
2155                         weight_array = POINTER_OFFSET(weight_array, stride);
2156                 }
2157         }
2158 }
2159
2160 /* make_bevel_list_3D_* funcs, at a minimum these must
2161  * fill in the bezp->quat and bezp->dir values */
2162
2163 /* utility for make_bevel_list_3D_* funcs */
2164 static void bevel_list_calc_bisect(BevList *bl)
2165 {
2166         BevPoint *bevp2, *bevp1, *bevp0;
2167         int nr;
2168         bool is_cyclic = bl->poly != -1;
2169
2170         if (is_cyclic) {
2171                 bevp2 = bl->bevpoints;
2172                 bevp1 = bevp2 + (bl->nr - 1);
2173                 bevp0 = bevp1 - 1;
2174                 nr = bl->nr;
2175         }
2176         else {
2177                 /* If spline is not cyclic, direction of first and
2178                  * last bevel points matches direction of CV handle.
2179                  *
2180                  * This is getting calculated earlier when we know
2181                  * CV's handles and here we might simply skip evaluation
2182                  * of direction for this guys.
2183                  */
2184
2185                 bevp0 = bl->bevpoints;
2186                 bevp1 = bevp0 + 1;
2187                 bevp2 = bevp1 + 1;
2188
2189                 nr = bl->nr - 2;
2190         }
2191
2192         while (nr--) {
2193                 /* totally simple */
2194                 bisect_v3_v3v3v3(bevp1->dir, bevp0->vec, bevp1->vec, bevp2->vec);
2195
2196                 bevp0 = bevp1;
2197                 bevp1 = bevp2;
2198                 bevp2++;
2199         }
2200 }
2201 static void bevel_list_flip_tangents(BevList *bl)
2202 {
2203         BevPoint *bevp2, *bevp1, *bevp0;
2204         int nr;
2205
2206         bevp2 = bl->bevpoints;
2207         bevp1 = bevp2 + (bl->nr - 1);
2208         bevp0 = bevp1 - 1;
2209
2210         nr = bl->nr;
2211         while (nr--) {
2212                 if (angle_normalized_v3v3(bevp0->tan, bevp1->tan) > DEG2RADF(90.0f))
2213                         negate_v3(bevp1->tan);
2214
2215                 bevp0 = bevp1;
2216                 bevp1 = bevp2;
2217                 bevp2++;
2218         }
2219 }
2220 /* apply user tilt */
2221 static void bevel_list_apply_tilt(BevList *bl)
2222 {
2223         BevPoint *bevp2, *bevp1;
2224         int nr;
2225         float q[4];
2226
2227         bevp2 = bl->bevpoints;
2228         bevp1 = bevp2 + (bl->nr - 1);
2229
2230         nr = bl->nr;
2231         while (nr--) {
2232                 axis_angle_to_quat(q, bevp1->dir, bevp1->alfa);
2233                 mul_qt_qtqt(bevp1->quat, q, bevp1->quat);
2234                 normalize_qt(bevp1->quat);
2235
2236                 bevp1 = bevp2;
2237                 bevp2++;
2238         }
2239 }
2240 /* smooth quats, this function should be optimized, it can get slow with many iterations. */
2241 static void bevel_list_smooth(BevList *bl, int smooth_iter)
2242 {
2243         BevPoint *bevp2, *bevp1, *bevp0;
2244         int nr;
2245
2246         float q[4];
2247         float bevp0_quat[4];
2248         int a;
2249
2250         for (a = 0; a < smooth_iter; a++) {
2251                 bevp2 = bl->bevpoints;
2252                 bevp1 = bevp2 + (bl->nr - 1);
2253                 bevp0 = bevp1 - 1;
2254
2255                 nr = bl->nr;
2256
2257                 if (bl->poly == -1) { /* check its not cyclic */
2258                         /* skip the first point */
2259                         /* bevp0 = bevp1; */
2260                         bevp1 = bevp2;
2261                         bevp2++;
2262                         nr--;
2263
2264                         bevp0 = bevp1;
2265                         bevp1 = bevp2;
2266                         bevp2++;
2267                         nr--;
2268                 }
2269
2270                 copy_qt_qt(bevp0_quat, bevp0->quat);
2271
2272                 while (nr--) {
2273                         /* interpolate quats */
2274                         float zaxis[3] = {0, 0, 1}, cross[3], q2[4];
2275                         interp_qt_qtqt(q, bevp0_quat, bevp2->quat, 0.5);
2276                         normalize_qt(q);
2277
2278                         mul_qt_v3(q, zaxis);
2279                         cross_v3_v3v3(cross, zaxis, bevp1->dir);
2280                         axis_angle_to_quat(q2, cross, angle_normalized_v3v3(zaxis, bevp1->dir));
2281                         normalize_qt(q2);
2282
2283                         copy_qt_qt(bevp0_quat, bevp1->quat);
2284                         mul_qt_qtqt(q, q2, q);
2285                         interp_qt_qtqt(bevp1->quat, bevp1->quat, q, 0.5);
2286                         normalize_qt(bevp1->quat);
2287
2288                         /* bevp0 = bevp1; */ /* UNUSED */
2289                         bevp1 = bevp2;
2290                         bevp2++;
2291                 }
2292         }
2293 }
2294
2295 static void make_bevel_list_3D_zup(BevList *bl)
2296 {
2297         BevPoint *bevp = bl->bevpoints;
2298         int nr = bl->nr;
2299
2300         bevel_list_calc_bisect(bl);
2301
2302         while (nr--) {
2303                 vec_to_quat(bevp->quat, bevp->dir, 5, 1);
2304                 bevp++;
2305         }
2306 }
2307
2308 static void minimum_twist_between_two_points(BevPoint *current_point, BevPoint *previous_point)
2309 {
2310         float angle = angle_normalized_v3v3(previous_point->dir, current_point->dir);
2311         float q[4];
2312
2313         if (angle > 0.0f) { /* otherwise we can keep as is */
2314                 float cross_tmp[3];
2315                 cross_v3_v3v3(cross_tmp, previous_point->dir, current_point->dir);
2316                 axis_angle_to_quat(q, cross_tmp, angle);
2317                 mul_qt_qtqt(current_point->quat, q, previous_point->quat);
2318         }
2319         else {
2320                 copy_qt_qt(current_point->quat, previous_point->quat);
2321         }
2322 }
2323
2324 static void make_bevel_list_3D_minimum_twist(BevList *bl)
2325 {
2326         BevPoint *bevp2, *bevp1, *bevp0; /* standard for all make_bevel_list_3D_* funcs */
2327         int nr;
2328         float q[4];
2329
2330         bevel_list_calc_bisect(bl);
2331
2332         bevp2 = bl->bevpoints;
2333         bevp1 = bevp2 + (bl->nr - 1);
2334         bevp0 = bevp1 - 1;
2335
2336         nr = bl->nr;
2337         while (nr--) {
2338
2339                 if (nr + 4 > bl->nr) { /* first time and second time, otherwise first point adjusts last */
2340                         vec_to_quat(bevp1->quat, bevp1->dir, 5, 1);
2341                 }
2342                 else {
2343                         minimum_twist_between_two_points(bevp1, bevp0);
2344                 }
2345
2346                 bevp0 = bevp1;
2347                 bevp1 = bevp2;
2348                 bevp2++;
2349         }
2350
2351         if (bl->poly != -1) { /* check for cyclic */
2352
2353                 /* Need to correct for the start/end points not matching
2354                  * do this by calculating the tilt angle difference, then apply
2355                  * the rotation gradually over the entire curve
2356                  *
2357                  * note that the split is between last and second last, rather than first/last as youd expect.
2358                  *
2359                  * real order is like this
2360                  * 0,1,2,3,4 --> 1,2,3,4,0
2361                  *
2362                  * this is why we compare last with second last
2363                  * */
2364                 float vec_1[3] = {0, 1, 0}, vec_2[3] = {0, 1, 0}, angle, ang_fac, cross_tmp[3];
2365
2366                 BevPoint *bevp_first;
2367                 BevPoint *bevp_last;
2368
2369
2370                 bevp_first = bl->bevpoints;
2371                 bevp_first += bl->nr - 1;
2372                 bevp_last = bevp_first;
2373                 bevp_last--;
2374
2375                 /* quats and vec's are normalized, should not need to re-normalize */
2376                 mul_qt_v3(bevp_first->quat, vec_1);
2377                 mul_qt_v3(bevp_last->quat, vec_2);
2378                 normalize_v3(vec_1);
2379                 normalize_v3(vec_2);
2380
2381                 /* align the vector, can avoid this and it looks 98% OK but
2382                  * better to align the angle quat roll's before comparing */
2383                 {
2384                         cross_v3_v3v3(cross_tmp, bevp_last->dir, bevp_first->dir);
2385                         angle = angle_normalized_v3v3(bevp_first->dir, bevp_last->dir);
2386                         axis_angle_to_quat(q, cross_tmp, angle);
2387                         mul_qt_v3(q, vec_2);
2388                 }
2389
2390                 angle = angle_normalized_v3v3(vec_1, vec_2);
2391
2392                 /* flip rotation if needs be */
2393                 cross_v3_v3v3(cross_tmp, vec_1, vec_2);
2394                 normalize_v3(cross_tmp);
2395                 if (angle_normalized_v3v3(bevp_first->dir, cross_tmp) < DEG2RADF(90.0f))
2396                         angle = -angle;
2397
2398                 bevp2 = bl->bevpoints;
2399                 bevp1 = bevp2 + (bl->nr - 1);
2400                 bevp0 = bevp1 - 1;
2401
2402                 nr = bl->nr;
2403                 while (nr--) {
2404                         ang_fac = angle * (1.0f - ((float)nr / bl->nr)); /* also works */
2405
2406                         axis_angle_to_quat(q, bevp1->dir, ang_fac);
2407                         mul_qt_qtqt(bevp1->quat, q, bevp1->quat);
2408
2409                         bevp0 = bevp1;
2410                         bevp1 = bevp2;
2411                         bevp2++;
2412                 }
2413         }
2414         else {
2415                 /* Need to correct quat for the first/last point,
2416                  * this is so because previously it was only calculated
2417                  * using it's own direction, which might not correspond
2418                  * the twist of neighbor point.
2419                  */
2420                 bevp1 = bl->bevpoints;
2421                 bevp0 = bevp1 + 1;
2422                 minimum_twist_between_two_points(bevp1, bevp0);
2423
2424                 bevp2 = bl->bevpoints;
2425                 bevp1 = bevp2 + (bl->nr - 1);
2426                 bevp0 = bevp1 - 1;
2427                 minimum_twist_between_two_points(bevp1, bevp0);
2428         }
2429 }
2430
2431 static void make_bevel_list_3D_tangent(BevList *bl)
2432 {
2433         BevPoint *bevp2, *bevp1, *bevp0; /* standard for all make_bevel_list_3D_* funcs */
2434         int nr;
2435
2436         float bevp0_tan[3];
2437
2438         bevel_list_calc_bisect(bl);
2439         bevel_list_flip_tangents(bl);
2440
2441         /* correct the tangents */
2442         bevp2 = bl->bevpoints;
2443         bevp1 = bevp2 + (bl->nr - 1);
2444         bevp0 = bevp1 - 1;
2445
2446         nr = bl->nr;
2447         while (nr--) {
2448                 float cross_tmp[3];
2449                 cross_v3_v3v3(cross_tmp, bevp1->tan, bevp1->dir);
2450                 cross_v3_v3v3(bevp1->tan, cross_tmp, bevp1->dir);
2451                 normalize_v3(bevp1->tan);
2452
2453                 bevp0 = bevp1;
2454                 bevp1 = bevp2;
2455                 bevp2++;
2456         }
2457
2458
2459         /* now for the real twist calc */
2460         bevp2 = bl->bevpoints;
2461         bevp1 = bevp2 + (bl->nr - 1);
2462         bevp0 = bevp1 - 1;
2463
2464         copy_v3_v3(bevp0_tan, bevp0->tan);
2465
2466         nr = bl->nr;
2467         while (nr--) {
2468                 /* make perpendicular, modify tan in place, is ok */
2469                 float cross_tmp[3];
2470                 float zero[3] = {0, 0, 0};
2471
2472                 cross_v3_v3v3(cross_tmp, bevp1->tan, bevp1->dir);
2473                 normalize_v3(cross_tmp);
2474                 tri_to_quat(bevp1->quat, zero, cross_tmp, bevp1->tan); /* XXX - could be faster */
2475
2476                 /* bevp0 = bevp1; */ /* UNUSED */
2477                 bevp1 = bevp2;
2478                 bevp2++;
2479         }
2480 }
2481
2482 static void make_bevel_list_3D(BevList *bl, int smooth_iter, int twist_mode)
2483 {
2484         switch (twist_mode) {
2485                 case CU_TWIST_TANGENT:
2486                         make_bevel_list_3D_tangent(bl);
2487                         break;
2488                 case CU_TWIST_MINIMUM:
2489                         make_bevel_list_3D_minimum_twist(bl);
2490                         break;
2491                 default: /* CU_TWIST_Z_UP default, pre 2.49c */
2492                         make_bevel_list_3D_zup(bl);
2493                         break;
2494         }
2495
2496         if (smooth_iter)
2497                 bevel_list_smooth(bl, smooth_iter);
2498
2499         bevel_list_apply_tilt(bl);
2500 }
2501
2502 /* only for 2 points */
2503 static void make_bevel_list_segment_3D(BevList *bl)
2504 {
2505         float q[4];
2506
2507         BevPoint *bevp2 = bl->bevpoints;
2508         BevPoint *bevp1 = bevp2 + 1;
2509
2510         /* simple quat/dir */
2511         sub_v3_v3v3(bevp1->dir, bevp1->vec, bevp2->vec);
2512         normalize_v3(bevp1->dir);
2513
2514         vec_to_quat(bevp1->quat, bevp1->dir, 5, 1);
2515
2516         axis_angle_to_quat(q, bevp1->dir, bevp1->alfa);
2517         mul_qt_qtqt(bevp1->quat, q, bevp1->quat);
2518         normalize_qt(bevp1->quat);
2519         copy_v3_v3(bevp2->dir, bevp1->dir);
2520         copy_qt_qt(bevp2->quat, bevp1->quat);
2521 }
2522
2523 /* only for 2 points */
2524 static void make_bevel_list_segment_2D(BevList *bl)
2525 {
2526         BevPoint *bevp2 = bl->bevpoints;
2527         BevPoint *bevp1 = bevp2 + 1;
2528
2529         const float x1 = bevp1->vec[0] - bevp2->vec[0];
2530         const float y1 = bevp1->vec[1] - bevp2->vec[1];
2531
2532         calc_bevel_sin_cos(x1, y1, -x1, -y1, &(bevp1->sina), &(bevp1->cosa));
2533         bevp2->sina = bevp1->sina;
2534         bevp2->cosa = bevp1->cosa;
2535
2536         /* fill in dir & quat */
2537         make_bevel_list_segment_3D(bl);
2538 }
2539
2540 static void make_bevel_list_2D(BevList *bl)
2541 {
2542         /* note: bevp->dir and bevp->quat are not needed for beveling but are
2543          * used when making a path from a 2D curve, therefor they need to be set - Campbell */
2544
2545         BevPoint *bevp0, *bevp1, *bevp2;
2546         int nr;
2547
2548         if (bl->poly != -1) {
2549                 bevp2 = bl->bevpoints;
2550                 bevp1 = bevp2 + (bl->nr - 1);
2551                 bevp0 = bevp1 - 1;
2552                 nr = bl->nr;
2553         }
2554         else {
2555                 bevp0 = bl->bevpoints;
2556                 bevp1 = bevp0 + 1;
2557                 bevp2 = bevp1 + 1;
2558
2559                 nr = bl->nr - 2;
2560         }
2561
2562         while (nr--) {
2563                 const float x1 = bevp1->vec[0] - bevp0->vec[0];
2564                 const float x2 = bevp1->vec[0] - bevp2->vec[0];
2565                 const float y1 = bevp1->vec[1] - bevp0->vec[1];
2566                 const float y2 = bevp1->vec[1] - bevp2->vec[1];
2567
2568                 calc_bevel_sin_cos(x1, y1, x2, y2, &(bevp1->sina), &(bevp1->cosa));
2569
2570                 /* from: make_bevel_list_3D_zup, could call but avoid a second loop.
2571                  * no need for tricky tilt calculation as with 3D curves */
2572                 bisect_v3_v3v3v3(bevp1->dir, bevp0->vec, bevp1->vec, bevp2->vec);
2573                 vec_to_quat(bevp1->quat, bevp1->dir, 5, 1);
2574                 /* done with inline make_bevel_list_3D_zup */
2575
2576                 bevp0 = bevp1;
2577                 bevp1 = bevp2;
2578                 bevp2++;
2579         }
2580
2581         /* correct non-cyclic cases */
2582         if (bl->poly == -1) {
2583                 BevPoint *bevp;
2584                 float angle;
2585
2586                 /* first */
2587                 bevp = bl->bevpoints;
2588                 angle = atan2f(bevp->dir[0], bevp->dir[1]) - (float)M_PI_2;
2589                 bevp->sina = sinf(angle);
2590                 bevp->cosa = cosf(angle);
2591                 vec_to_quat(bevp->quat, bevp->dir, 5, 1);
2592
2593                 /* last */
2594                 bevp = bl->bevpoints;
2595                 bevp += (bl->nr - 1);
2596                 angle = atan2f(bevp->dir[0], bevp->dir[1]) - (float)M_PI_2;
2597                 bevp->sina = sinf(angle);
2598                 bevp->cosa = cosf(angle);
2599                 vec_to_quat(bevp->quat, bevp->dir, 5, 1);
2600         }
2601 }
2602
2603 static void bevlist_firstlast_direction_calc_from_bpoint(Nurb *nu, BevList *bl)
2604 {
2605         if (nu->pntsu > 1) {
2606                 BPoint *first_bp = nu->bp, *last_bp = nu->bp + (nu->pntsu - 1);
2607                 BevPoint *first_bevp, *last_bevp;
2608
2609                 first_bevp = bl->bevpoints;
2610                 last_bevp = first_bevp + (bl->nr - 1);
2611
2612                 sub_v3_v3v3(first_bevp->dir, (first_bp + 1)->vec, first_bp->vec);
2613                 normalize_v3(first_bevp->dir);
2614
2615                 sub_v3_v3v3(last_bevp->dir, last_bp->vec, (last_bp - 1)->vec);
2616                 normalize_v3(last_bevp->dir);
2617         }
2618 }
2619
2620 void BKE_curve_bevelList_free(ListBase *bev)
2621 {
2622         BevList *bl, *blnext;
2623         for (bl = bev->first; bl != NULL; bl = blnext) {
2624                 blnext = bl->next;
2625                 if (bl->seglen != NULL) {
2626                         MEM_freeN(bl->seglen);
2627                 }
2628                 if (bl->segbevcount != NULL) {
2629                         MEM_freeN(bl->segbevcount);
2630                 }
2631                 if (bl->bevpoints != NULL) {
2632                         MEM_freeN(bl->bevpoints);
2633                 }
2634                 MEM_freeN(bl);
2635         }
2636
2637         BLI_listbase_clear(bev);
2638 }
2639
2640 void BKE_curve_bevelList_make(Object *ob, ListBase *nurbs, bool for_render)
2641 {
2642         /*
2643          * - convert all curves to polys, with indication of resol and flags for double-vertices
2644          * - possibly; do a smart vertice removal (in case Nurb)
2645          * - separate in individual blocks with BoundBox
2646          * - AutoHole detection
2647          */
2648
2649         /* this function needs an object, because of tflag and upflag */
2650         Curve *cu = ob->data;
2651         Nurb *nu;
2652         BezTriple *bezt, *prevbezt;
2653         BPoint *bp;
2654         BevList *bl, *blnew, *blnext;
2655         BevPoint *bevp2, *bevp1 = NULL, *bevp0;
2656         const float treshold = 0.00001f;
2657         float min, inp;
2658         float *seglen = NULL;
2659         struct BevelSort *sortdata, *sd, *sd1;
2660         int a, b, nr, poly, resolu = 0, len = 0, segcount;
2661         int *segbevcount;
2662         bool do_tilt, do_radius, do_weight;
2663         bool is_editmode = false;
2664         ListBase *bev;
2665
2666         /* segbevcount alsp requires seglen. */
2667         const bool need_seglen =
2668                 ELEM(cu->bevfac1_mapping, CU_BEVFAC_MAP_SEGMENT, CU_BEVFAC_MAP_SPLINE) ||
2669                 ELEM(cu->bevfac2_mapping, CU_BEVFAC_MAP_SEGMENT, CU_BEVFAC_MAP_SPLINE);
2670
2671
2672         bev = &ob->curve_cache->bev;
2673
2674         /* do we need to calculate the radius for each point? */
2675         /* do_radius = (cu->bevobj || cu->taperobj || (cu->flag & CU_FRONT) || (cu->flag & CU_BACK)) ? 0 : 1; */
2676
2677         /* STEP 1: MAKE POLYS  */
2678
2679         BKE_curve_bevelList_free(&ob->curve_cache->bev);
2680         nu = nurbs->first;
2681         if (cu->editnurb && ob->type != OB_FONT) {
2682                 is_editmode = 1;
2683         }
2684
2685         for (; nu; nu = nu->next) {
2686                 
2687                 if (nu->hide && is_editmode)
2688                         continue;
2689                 
2690                 /* check if we will calculate tilt data */
2691                 do_tilt = CU_DO_TILT(cu, nu);
2692                 do_radius = CU_DO_RADIUS(cu, nu); /* normal display uses the radius, better just to calculate them */
2693                 do_weight = true;
2694
2695                 /* check we are a single point? also check we are not a surface and that the orderu is sane,
2696                  * enforced in the UI but can go wrong possibly */
2697                 if (!BKE_nurb_check_valid_u(nu)) {
2698                         bl = MEM_callocN(sizeof(BevList), "makeBevelList1");
2699                         bl->bevpoints = MEM_calloc_arrayN(1, sizeof(BevPoint), "makeBevelPoints1");
2700                         BLI_addtail(bev, bl);
2701                         bl->nr = 0;
2702                         bl->charidx = nu->charidx;
2703                 }
2704                 else {
2705                         BevPoint *bevp;
2706
2707                         if (for_render && cu->resolu_ren != 0)
2708                                 resolu = cu->resolu_ren;
2709                         else
2710                                 resolu = nu->resolu;
2711
2712                         segcount = SEGMENTSU(nu);
2713
2714                         if (nu->type == CU_POLY) {
2715                                 len = nu->pntsu;
2716                                 bl = MEM_callocN(sizeof(BevList), "makeBevelList2");
2717                                 bl->bevpoints = MEM_calloc_arrayN(len, sizeof(BevPoint), "makeBevelPoints2");
2718                                 if (need_seglen && (nu->flagu & CU_NURB_CYCLIC) == 0) {
2719                                         bl->seglen = MEM_malloc_arrayN(segcount, sizeof(float), "makeBevelList2_seglen");
2720                                         bl->segbevcount = MEM_malloc_arrayN(segcount, sizeof(int), "makeBevelList2_segbevcount");
2721                                 }
2722                                 BLI_addtail(bev, bl);
2723
2724                                 bl->poly = (nu->flagu & CU_NURB_CYCLIC) ? 0 : -1;
2725                                 bl->nr = len;
2726                                 bl->dupe_nr = 0;
2727                                 bl->charidx = nu->charidx;
2728                                 bevp = bl->bevpoints;
2729                                 bevp->offset = 0;
2730                                 bp = nu->bp;
2731                                 seglen = bl->seglen;
2732                                 segbevcount = bl->segbevcount;
2733
2734                                 while (len--) {
2735                                         copy_v3_v3(bevp->vec, bp->vec);
2736                                         bevp->alfa = bp->alfa;
2737                                         bevp->radius = bp->radius;
2738                                         bevp->weight = bp->weight;
2739                                         bevp->split_tag = true;
2740                                         bp++;
2741                                         if (seglen != NULL && len != 0) {
2742                                                 *seglen = len_v3v3(bevp->vec, bp->vec);
2743                                                 bevp++;
2744                                                 bevp->offset = *seglen;
2745                                                 if (*seglen > treshold) *segbevcount = 1;
2746                                                 else *segbevcount = 0;
2747                                                 seglen++;
2748                                                 segbevcount++;
2749                                         }
2750                                         else {
2751                                                 bevp++;
2752                                         }
2753                                 }
2754
2755                                 if ((nu->flagu & CU_NURB_CYCLIC) == 0) {
2756                                         bevlist_firstlast_direction_calc_from_bpoint(nu, bl);
2757                                 }
2758                         }
2759                         else if (nu->type == CU_BEZIER) {
2760                                 /* in case last point is not cyclic */
2761                                 len = segcount * resolu + 1;
2762
2763                                 bl = MEM_callocN(sizeof(BevList), "makeBevelBPoints");
2764                                 bl->bevpoints = MEM_calloc_arrayN(len, sizeof(BevPoint), "makeBevelBPointsPoints");
2765                                 if (need_seglen && (nu->flagu & CU_NURB_CYCLIC) == 0) {
2766                                         bl->seglen = MEM_malloc_arrayN(segcount, sizeof(float), "makeBevelBPoints_seglen");
2767                                         bl->segbevcount = MEM_malloc_arrayN(segcount, sizeof(int), "makeBevelBPoints_segbevcount");
2768                                 }
2769                                 BLI_addtail(bev, bl);
2770
2771                                 bl->poly = (nu->flagu & CU_NURB_CYCLIC) ? 0 : -1;
2772                                 bl->charidx = nu->charidx;
2773
2774                                 bevp = bl->bevpoints;
2775                                 seglen = bl->seglen;
2776                                 segbevcount = bl->segbevcount;
2777
2778                                 bevp->offset = 0;
2779                                 if (seglen != NULL) {
2780                                         *seglen = 0;
2781                                         *segbevcount = 0;
2782                                 }
2783
2784                                 a = nu->pntsu - 1;
2785                                 bezt = nu->bezt;
2786                                 if (nu->flagu & CU_NURB_CYCLIC) {
2787                                         a++;
2788                                         prevbezt = nu->bezt + (nu->pntsu - 1);
2789                                 }
2790                                 else {
2791                                         prevbezt = bezt;
2792                                         bezt++;
2793                                 }
2794
2795                                 sub_v3_v3v3(bevp->dir, prevbezt->vec[2], prevbezt->vec[1]);
2796                                 normalize_v3(bevp->dir);
2797
2798                                 BLI_assert(segcount >= a);
2799
2800                                 while (a--) {
2801                                         if (prevbezt->h2 == HD_VECT && bezt->h1 == HD_VECT) {
2802
2803                                                 copy_v3_v3(bevp->vec, prevbezt->vec[1]);
2804                                                 bevp->alfa = prevbezt->alfa;
2805                                                 bevp->radius = prevbezt->radius;
2806                                                 bevp->weight = prevbezt->weight;
2807                                                 bevp->split_tag = true;
2808                                                 bevp->dupe_tag = false;
2809                                                 bevp++;
2810                                                 bl->nr++;
2811                                                 bl->dupe_nr = 1;
2812                                                 if (seglen != NULL) {
2813                                                         *seglen = len_v3v3(prevbezt->vec[1], bezt->vec[1]);
2814                                                         bevp->offset = *seglen;
2815                                                         seglen++;
2816                                                         /* match segbevcount to the cleaned up bevel lists (see STEP 2) */
2817                                                         if (bevp->offset > treshold) *segbevcount = 1;
2818                                                         segbevcount++;
2819                                                 }
2820                                         }
2821                                         else {
2822                                                 /* always do all three, to prevent data hanging around */
2823                                                 int j;
2824
2825                                                 /* BevPoint must stay aligned to 4 so sizeof(BevPoint)/sizeof(float) works */
2826                                                 for (j = 0; j < 3; j++) {
2827                                                         BKE_curve_forward_diff_bezier(prevbezt->vec[1][j],  prevbezt->vec[2][j],
2828                                                                                       bezt->vec[0][j],      bezt->vec[1][j],
2829                                                                                       &(bevp->vec[j]), resolu, sizeof(BevPoint));
2830                                                 }
2831
2832                                                 /* if both arrays are NULL do nothiong */
2833                                                 alfa_bezpart(prevbezt, bezt, nu,
2834                                                              do_tilt    ? &bevp->alfa : NULL,
2835                                                              do_radius  ? &bevp->radius : NULL,
2836                                                              do_weight  ? &bevp->weight : NULL,
2837                                                              resolu, sizeof(BevPoint));
2838
2839
2840                                                 if (cu->twist_mode == CU_TWIST_TANGENT) {
2841                                                         forward_diff_bezier_cotangent(prevbezt->vec[1], prevbezt->vec[2],
2842                                                                                       bezt->vec[0],     bezt->vec[1],
2843                                                                                       bevp->tan, resolu, sizeof(BevPoint));
2844                                                 }
2845
2846                                                 /* indicate with handlecodes double points */
2847                                                 if (prevbezt->h1 == prevbezt->h2) {
2848                                                         if (prevbezt->h1 == 0 || prevbezt->h1 == HD_VECT)
2849                                                                 bevp->split_tag = true;
2850                                                 }
2851                                                 else {
2852                                                         if (prevbezt->h1 == 0 || prevbezt->h1 == HD_VECT)
2853                                                                 bevp->split_tag = true;
2854                                                         else if (prevbezt->h2 == 0 || prevbezt->h2 == HD_VECT)
2855                                                                 bevp->split_tag = true;
2856                                                 }
2857
2858                                                 /* seglen */
2859                                                 if (seglen != NULL) {
2860                                                         *seglen = 0;
2861                                                         *segbevcount = 0;
2862                                                         for (j = 0; j < resolu; j++) {
2863                                                                 bevp0 = bevp;
2864                                                                 bevp++;
2865                                                                 bevp->offset = len_v3v3(bevp0->vec, bevp->vec);
2866                                                                 /* match seglen and segbevcount to the cleaned up bevel lists (see STEP 2) */
2867                                                                 if (bevp->offset > treshold) {
2868                                                                         *seglen += bevp->offset;
2869                                                                         *segbevcount += 1;
2870                                                                 }
2871                                                         }
2872                                                         seglen++;
2873                                                         segbevcount++;
2874                                                 }
2875                                                 else {
2876                                                         bevp += resolu;
2877                                                 }
2878                                                 bl->nr += resolu;
2879                                         }
2880                                         prevbezt = bezt;
2881                                         bezt++;
2882                                 }
2883
2884                                 if ((nu->flagu & CU_NURB_CYCLIC) == 0) {      /* not cyclic: endpoint */
2885                                         copy_v3_v3(bevp->vec, prevbezt->vec[1]);
2886                                         bevp->alfa = prevbezt->alfa;
2887                                         bevp->radius = prevbezt->radius;
2888                                         bevp->weight = prevbezt->weight;
2889
2890                                         sub_v3_v3v3(bevp->dir, prevbezt->vec[1], prevbezt->vec[0]);
2891                                         normalize_v3(bevp->dir);
2892
2893                                         bl->nr++;
2894                                 }
2895                         }
2896                         else if (nu->type == CU_NURBS) {
2897                                 if (nu->pntsv == 1) {
2898                                         len = (resolu * segcount);
2899
2900                                         bl = MEM_callocN(sizeof(BevList), "makeBevelList3");
2901                                         bl->bevpoints = MEM_calloc_arrayN(len, sizeof(BevPoint), "makeBevelPoints3");
2902                                         if (need_seglen && (nu->flagu & CU_NURB_CYCLIC) == 0) {
2903                                                 bl->seglen = MEM_malloc_arrayN(segcount, sizeof(float), "makeBevelList3_seglen");
2904                                                 bl->segbevcount = MEM_malloc_arrayN(segcount, sizeof(int), "makeBevelList3_segbevcount");
2905                                         }
2906                                         BLI_addtail(bev, bl);
2907                                         bl->nr = len;
2908                                         bl->dupe_nr = 0;
2909                                         bl->poly = (nu->flagu & CU_NURB_CYCLIC) ? 0 : -1;
2910                                         bl->charidx = nu->charidx;
2911
2912                                         bevp = bl->bevpoints;
2913                                         seglen = bl->seglen;
2914                                         segbevcount = bl->segbevcount;
2915
2916                                         BKE_nurb_makeCurve(nu, &bevp->vec[0],
2917                                                            do_tilt      ? &bevp->alfa : NULL,
2918                                                            do_radius    ? &bevp->radius : NULL,
2919                                                            do_weight    ? &bevp->weight : NULL,
2920                                                            resolu, sizeof(BevPoint));
2921
2922                                         /* match seglen and segbevcount to the cleaned up bevel lists (see STEP 2) */
2923                                         if (seglen != NULL) {
2924                                                 nr = segcount;
2925                                                 bevp0 = bevp;
2926                                                 bevp++;
2927                                                 while (nr) {
2928                                                         int j;
2929                                                         *seglen = 0;
2930                                                         *segbevcount = 0;
2931                                                         /* We keep last bevel segment zero-length. */
2932                                                         for (j = 0; j < ((nr == 1) ? (resolu - 1) : resolu); j++) {
2933                                                                 bevp->offset = len_v3v3(bevp0->vec, bevp->vec);
2934                                                                 if (bevp->offset > treshold) {
2935                                                                         *seglen += bevp->offset;
2936                                                                         *segbevcount += 1;
2937                                                                 }
2938                                                                 bevp0 = bevp;
2939                                                                 bevp++;
2940                                                         }
2941                                                         seglen++;
2942                                                         segbevcount++;
2943                                                         nr--;
2944                                                 }
2945                                         }
2946
2947                                         if ((nu->flagu & CU_NURB_CYCLIC) == 0) {
2948                                                 bevlist_firstlast_direction_calc_from_bpoint(nu, bl);
2949                                         }
2950                                 }
2951                         }
2952                 }
2953         }
2954
2955         /* STEP 2: DOUBLE POINTS AND AUTOMATIC RESOLUTION, REDUCE DATABLOCKS */
2956         bl = bev->first;
2957         while (bl) {
2958                 if (bl->nr) { /* null bevel items come from single points */
2959                         bool is_cyclic = bl->poly != -1;
2960                         nr = bl->nr;
2961                         if (is_cyclic) {
2962                                 bevp1 = bl->bevpoints;
2963                                 bevp0 = bevp1 + (nr - 1);
2964                         }
2965                         else {
2966                                 bevp0 = bl->bevpoints;
2967                                 bevp0->offset = 0;
2968                                 bevp1 = bevp0 + 1;
2969                         }
2970                         nr--;
2971                         while (nr--) {
2972                                 if (seglen != NULL) {
2973                                         if (fabsf(bevp1->offset) < treshold) {
2974                                                 bevp0->dupe_tag = true;
2975                                                 bl->dupe_nr++;
2976                                         }
2977                                 }
2978                                 else {
2979                                         if (fabsf(bevp0->vec[0] - bevp1->vec[0]) < 0.00001f) {
2980                                                 if (fabsf(bevp0->vec[1] - bevp1->vec[1]) < 0.00001f) {
2981                                                         if (fabsf(bevp0->vec[2] - bevp1->vec[2]) < 0.00001f) {
2982                                                                 bevp0->dupe_tag = true;
2983                                                                 bl->dupe_nr++;
2984                                                         }
2985                                                 }
2986                                         }
2987                                 }
2988                                 bevp0 = bevp1;
2989                                 bevp1++;
2990                         }
2991                 }
2992                 bl = bl->next;
2993         }
2994         bl = bev->first;
2995         while (bl) {
2996                 blnext = bl->next;
2997                 if (bl->nr && bl->dupe_nr) {
2998                         nr = bl->nr - bl->dupe_nr + 1;  /* +1 because vectorbezier sets flag too */
2999                         blnew = MEM_callocN(sizeof(BevList), "makeBevelList4");
3000                         memcpy(blnew, bl, sizeof(BevList));
3001                         blnew->bevpoints = MEM_calloc_arrayN(nr, sizeof(BevPoint), "makeBevelPoints4");
3002                         if (!blnew->bevpoints) {
3003                                 MEM_freeN(blnew);
3004                                 break;
3005                         }
3006                         blnew->segbevcount = bl->segbevcount;
3007                         blnew->seglen = bl->seglen;
3008                         blnew->nr = 0;
3009                         BLI_remlink(bev, bl);
3010                         BLI_insertlinkbefore(bev, blnext, blnew);    /* to make sure bevlijst is tuned with nurblist */
3011                         bevp0 = bl->bevpoints;
3012                         bevp1 = blnew->bevpoints;
3013                         nr = bl->nr;
3014                         while (nr--) {
3015                                 if (bevp0->dupe_tag == 0) {
3016                                         memcpy(bevp1, bevp0, sizeof(BevPoint));
3017                                         bevp1++;
3018                                         blnew->nr++;
3019                                 }
3020                                 bevp0++;
3021                         }
3022                         if (bl->bevpoints != NULL) {
3023                                 MEM_freeN(bl->bevpoints);
3024                         }
3025                         MEM_freeN(bl);
3026                         blnew->dupe_nr = 0;
3027                 }
3028                 bl = blnext;
3029         }
3030
3031         /* STEP 3: POLYS COUNT AND AUTOHOLE */
3032         bl = bev->first;
3033         poly = 0;
3034         while (bl) {
3035                 if (bl->nr && bl->poly >= 0) {
3036                         poly++;
3037                         bl->poly = poly;
3038                         bl->hole = 0;
3039                 }
3040                 bl = bl->next;
3041         }
3042
3043         /* find extreme left points, also test (turning) direction */
3044         if (poly > 0) {
3045                 sd = sortdata = MEM_malloc_arrayN(poly, sizeof(struct BevelSort), "makeBevelList5");
3046                 bl = bev->first;
3047                 while (bl) {
3048                         if (bl->poly > 0) {
3049                                 BevPoint *bevp;
3050
3051                                 min = 300000.0;
3052                                 bevp = bl->bevpoints;
3053                                 nr = bl->nr;
3054                                 while (nr--) {
3055                                         if (min > bevp->vec[0]) {
3056                                                 min = bevp->vec[0];
3057                                                 bevp1 = bevp;
3058                                         }
3059                                         bevp++;
3060                                 }
3061                                 sd->bl = bl;
3062                                 sd->left = min;
3063
3064                                 bevp = bl->bevpoints;
3065                                 if (bevp1 == bevp)
3066                                         bevp0 = bevp + (bl->nr - 1);
3067                                 else
3068<