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