cf6f1fdeec1f98514567ec3379ac5f227dacc2bf
[blender.git] / source / blender / blenkernel / intern / displist.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>
25 #include <stdio.h>
26 #include <string.h>
27
28 #include "MEM_guardedalloc.h"
29
30 #include "DNA_curve_types.h"
31 #include "DNA_mesh_types.h"
32 #include "DNA_scene_types.h"
33 #include "DNA_object_types.h"
34 #include "DNA_vfont_types.h"
35
36 #include "BLI_blenlib.h"
37 #include "BLI_memarena.h"
38 #include "BLI_math.h"
39 #include "BLI_scanfill.h"
40 #include "BLI_utildefines.h"
41 #include "BLI_linklist.h"
42
43 #include "BKE_displist.h"
44 #include "BKE_cdderivedmesh.h"
45 #include "BKE_object.h"
46 #include "BKE_library.h"
47 #include "BKE_mball.h"
48 #include "BKE_mball_tessellate.h"
49 #include "BKE_mesh.h"
50 #include "BKE_curve.h"
51 #include "BKE_key.h"
52 #include "BKE_anim.h"
53 #include "BKE_font.h"
54 #include "BKE_lattice.h"
55 #include "BKE_modifier.h"
56
57 #include "BLI_sys_types.h"  // for intptr_t support
58
59 #include "DEG_depsgraph.h"
60 #include "DEG_depsgraph_query.h"
61
62 static void boundbox_displist_object(Object *ob);
63
64 void BKE_displist_elem_free(DispList *dl)
65 {
66   if (dl) {
67     if (dl->verts) {
68       MEM_freeN(dl->verts);
69     }
70     if (dl->nors) {
71       MEM_freeN(dl->nors);
72     }
73     if (dl->index) {
74       MEM_freeN(dl->index);
75     }
76     if (dl->bevel_split) {
77       MEM_freeN(dl->bevel_split);
78     }
79     MEM_freeN(dl);
80   }
81 }
82
83 void BKE_displist_free(ListBase *lb)
84 {
85   DispList *dl;
86
87   while ((dl = BLI_pophead(lb))) {
88     BKE_displist_elem_free(dl);
89   }
90 }
91
92 DispList *BKE_displist_find_or_create(ListBase *lb, int type)
93 {
94   DispList *dl;
95
96   dl = lb->first;
97   while (dl) {
98     if (dl->type == type) {
99       return dl;
100     }
101     dl = dl->next;
102   }
103
104   dl = MEM_callocN(sizeof(DispList), "find_disp");
105   dl->type = type;
106   BLI_addtail(lb, dl);
107
108   return dl;
109 }
110
111 DispList *BKE_displist_find(ListBase *lb, int type)
112 {
113   DispList *dl;
114
115   dl = lb->first;
116   while (dl) {
117     if (dl->type == type) {
118       return dl;
119     }
120     dl = dl->next;
121   }
122
123   return NULL;
124 }
125
126 bool BKE_displist_has_faces(ListBase *lb)
127 {
128   DispList *dl;
129
130   for (dl = lb->first; dl; dl = dl->next) {
131     if (ELEM(dl->type, DL_INDEX3, DL_INDEX4, DL_SURF)) {
132       return true;
133     }
134   }
135
136   return false;
137 }
138
139 void BKE_displist_copy(ListBase *lbn, ListBase *lb)
140 {
141   DispList *dln, *dl;
142
143   BKE_displist_free(lbn);
144
145   dl = lb->first;
146   while (dl) {
147     dln = MEM_dupallocN(dl);
148     BLI_addtail(lbn, dln);
149     dln->verts = MEM_dupallocN(dl->verts);
150     dln->nors = MEM_dupallocN(dl->nors);
151     dln->index = MEM_dupallocN(dl->index);
152
153     if (dl->bevel_split) {
154       dln->bevel_split = MEM_dupallocN(dl->bevel_split);
155     }
156
157     dl = dl->next;
158   }
159 }
160
161 void BKE_displist_normals_add(ListBase *lb)
162 {
163   DispList *dl = NULL;
164   float *vdata, *ndata, nor[3];
165   float *v1, *v2, *v3, *v4;
166   float *n1, *n2, *n3, *n4;
167   int a, b, p1, p2, p3, p4;
168
169   dl = lb->first;
170
171   while (dl) {
172     if (dl->type == DL_INDEX3) {
173       if (dl->nors == NULL) {
174         dl->nors = MEM_callocN(sizeof(float) * 3, "dlnors");
175
176         if (dl->flag & DL_BACK_CURVE) {
177           dl->nors[2] = -1.0f;
178         }
179         else {
180           dl->nors[2] = 1.0f;
181         }
182       }
183     }
184     else if (dl->type == DL_SURF) {
185       if (dl->nors == NULL) {
186         dl->nors = MEM_callocN(sizeof(float) * 3 * dl->nr * dl->parts, "dlnors");
187
188         vdata = dl->verts;
189         ndata = dl->nors;
190
191         for (a = 0; a < dl->parts; a++) {
192
193           if (BKE_displist_surfindex_get(dl, a, &b, &p1, &p2, &p3, &p4) == 0) {
194             break;
195           }
196
197           v1 = vdata + 3 * p1;
198           n1 = ndata + 3 * p1;
199           v2 = vdata + 3 * p2;
200           n2 = ndata + 3 * p2;
201           v3 = vdata + 3 * p3;
202           n3 = ndata + 3 * p3;
203           v4 = vdata + 3 * p4;
204           n4 = ndata + 3 * p4;
205
206           for (; b < dl->nr; b++) {
207             normal_quad_v3(nor, v1, v3, v4, v2);
208
209             add_v3_v3(n1, nor);
210             add_v3_v3(n2, nor);
211             add_v3_v3(n3, nor);
212             add_v3_v3(n4, nor);
213
214             v2 = v1;
215             v1 += 3;
216             v4 = v3;
217             v3 += 3;
218             n2 = n1;
219             n1 += 3;
220             n4 = n3;
221             n3 += 3;
222           }
223         }
224         a = dl->parts * dl->nr;
225         v1 = ndata;
226         while (a--) {
227           normalize_v3(v1);
228           v1 += 3;
229         }
230       }
231     }
232     dl = dl->next;
233   }
234 }
235
236 void BKE_displist_count(ListBase *lb, int *totvert, int *totface, int *tottri)
237 {
238   DispList *dl;
239
240   for (dl = lb->first; dl; dl = dl->next) {
241     int vert_tot = 0;
242     int face_tot = 0;
243     int tri_tot = 0;
244     bool cyclic_u = dl->flag & DL_CYCL_U;
245     bool cyclic_v = dl->flag & DL_CYCL_V;
246
247     switch (dl->type) {
248       case DL_SURF: {
249         int segments_u = dl->nr - (cyclic_u == false);
250         int segments_v = dl->parts - (cyclic_v == false);
251         vert_tot = dl->nr * dl->parts;
252         face_tot = segments_u * segments_v;
253         tri_tot = face_tot * 2;
254         break;
255       }
256       case DL_INDEX3: {
257         vert_tot = dl->nr;
258         face_tot = dl->parts;
259         tri_tot = face_tot;
260         break;
261       }
262       case DL_INDEX4: {
263         vert_tot = dl->nr;
264         face_tot = dl->parts;
265         tri_tot = face_tot * 2;
266         break;
267       }
268       case DL_POLY:
269       case DL_SEGM: {
270         vert_tot = dl->nr * dl->parts;
271         break;
272       }
273     }
274
275     *totvert += vert_tot;
276     *totface += face_tot;
277     *tottri += tri_tot;
278   }
279 }
280
281 bool BKE_displist_surfindex_get(DispList *dl, int a, int *b, int *p1, int *p2, int *p3, int *p4)
282 {
283   if ((dl->flag & DL_CYCL_V) == 0 && a == (dl->parts) - 1) {
284     return false;
285   }
286
287   if (dl->flag & DL_CYCL_U) {
288     (*p1) = dl->nr * a;
289     (*p2) = (*p1) + dl->nr - 1;
290     (*p3) = (*p1) + dl->nr;
291     (*p4) = (*p2) + dl->nr;
292     (*b) = 0;
293   }
294   else {
295     (*p2) = dl->nr * a;
296     (*p1) = (*p2) + 1;
297     (*p4) = (*p2) + dl->nr;
298     (*p3) = (*p1) + dl->nr;
299     (*b) = 1;
300   }
301
302   if ((dl->flag & DL_CYCL_V) && a == dl->parts - 1) {
303     (*p3) -= dl->nr * dl->parts;
304     (*p4) -= dl->nr * dl->parts;
305   }
306
307   return true;
308 }
309
310 /* ****************** make displists ********************* */
311 #ifdef __INTEL_COMPILER
312 /* ICC with the optimization -02 causes crashes. */
313 #  pragma intel optimization_level 1
314 #endif
315 static void curve_to_displist(Curve *cu,
316                               ListBase *nubase,
317                               ListBase *dispbase,
318                               const bool for_render)
319 {
320   Nurb *nu;
321   DispList *dl;
322   BezTriple *bezt, *prevbezt;
323   BPoint *bp;
324   float *data;
325   int a, len, resolu;
326   const bool editmode = (!for_render && (cu->editnurb || cu->editfont));
327
328   nu = nubase->first;
329   while (nu) {
330     if (nu->hide == 0 || editmode == false) {
331       if (for_render && cu->resolu_ren != 0) {
332         resolu = cu->resolu_ren;
333       }
334       else {
335         resolu = nu->resolu;
336       }
337
338       if (!BKE_nurb_check_valid_u(nu)) {
339         /* pass */
340       }
341       else if (nu->type == CU_BEZIER) {
342         /* count */
343         len = 0;
344         a = nu->pntsu - 1;
345         if (nu->flagu & CU_NURB_CYCLIC) {
346           a++;
347         }
348
349         prevbezt = nu->bezt;
350         bezt = prevbezt + 1;
351         while (a--) {
352           if (a == 0 && (nu->flagu & CU_NURB_CYCLIC)) {
353             bezt = nu->bezt;
354           }
355
356           if (prevbezt->h2 == HD_VECT && bezt->h1 == HD_VECT) {
357             len++;
358           }
359           else {
360             len += resolu;
361           }
362
363           if (a == 0 && (nu->flagu & CU_NURB_CYCLIC) == 0) {
364             len++;
365           }
366
367           prevbezt = bezt;
368           bezt++;
369         }
370
371         dl = MEM_callocN(sizeof(DispList), "makeDispListbez");
372         /* len+1 because of 'forward_diff_bezier' function */
373         dl->verts = MEM_mallocN((len + 1) * sizeof(float[3]), "dlverts");
374         BLI_addtail(dispbase, dl);
375         dl->parts = 1;
376         dl->nr = len;
377         dl->col = nu->mat_nr;
378         dl->charidx = nu->charidx;
379
380         data = dl->verts;
381
382         /* check that (len != 2) so we don't immediately loop back on ourselves */
383         if (nu->flagu & CU_NURB_CYCLIC && (dl->nr != 2)) {
384           dl->type = DL_POLY;
385           a = nu->pntsu;
386         }
387         else {
388           dl->type = DL_SEGM;
389           a = nu->pntsu - 1;
390         }
391
392         prevbezt = nu->bezt;
393         bezt = prevbezt + 1;
394
395         while (a--) {
396           if (a == 0 && dl->type == DL_POLY) {
397             bezt = nu->bezt;
398           }
399
400           if (prevbezt->h2 == HD_VECT && bezt->h1 == HD_VECT) {
401             copy_v3_v3(data, prevbezt->vec[1]);
402             data += 3;
403           }
404           else {
405             int j;
406             for (j = 0; j < 3; j++) {
407               BKE_curve_forward_diff_bezier(prevbezt->vec[1][j],
408                                             prevbezt->vec[2][j],
409                                             bezt->vec[0][j],
410                                             bezt->vec[1][j],
411                                             data + j,
412                                             resolu,
413                                             3 * sizeof(float));
414             }
415
416             data += 3 * resolu;
417           }
418
419           if (a == 0 && dl->type == DL_SEGM) {
420             copy_v3_v3(data, bezt->vec[1]);
421           }
422
423           prevbezt = bezt;
424           bezt++;
425         }
426       }
427       else if (nu->type == CU_NURBS) {
428         len = (resolu * SEGMENTSU(nu));
429
430         dl = MEM_callocN(sizeof(DispList), "makeDispListsurf");
431         dl->verts = MEM_mallocN(len * sizeof(float[3]), "dlverts");
432         BLI_addtail(dispbase, dl);
433         dl->parts = 1;
434
435         dl->nr = len;
436         dl->col = nu->mat_nr;
437         dl->charidx = nu->charidx;
438
439         data = dl->verts;
440         if (nu->flagu & CU_NURB_CYCLIC) {
441           dl->type = DL_POLY;
442         }
443         else {
444           dl->type = DL_SEGM;
445         }
446         BKE_nurb_makeCurve(nu, data, NULL, NULL, NULL, resolu, 3 * sizeof(float));
447       }
448       else if (nu->type == CU_POLY) {
449         len = nu->pntsu;
450         dl = MEM_callocN(sizeof(DispList), "makeDispListpoly");
451         dl->verts = MEM_mallocN(len * sizeof(float[3]), "dlverts");
452         BLI_addtail(dispbase, dl);
453         dl->parts = 1;
454         dl->nr = len;
455         dl->col = nu->mat_nr;
456         dl->charidx = nu->charidx;
457
458         data = dl->verts;
459         if ((nu->flagu & CU_NURB_CYCLIC) && (dl->nr != 2)) {
460           dl->type = DL_POLY;
461         }
462         else {
463           dl->type = DL_SEGM;
464         }
465
466         a = len;
467         bp = nu->bp;
468         while (a--) {
469           copy_v3_v3(data, bp->vec);
470           bp++;
471           data += 3;
472         }
473       }
474     }
475     nu = nu->next;
476   }
477 }
478
479 /**
480  * \param normal_proj: Optional normal thats used to project the scanfill verts into 2d coords.
481  * Pass this along if known since it saves time calculating the normal.
482  * \param flipnormal: Flip the normal (same as passing \a normal_proj negated)
483  */
484 void BKE_displist_fill(ListBase *dispbase,
485                        ListBase *to,
486                        const float normal_proj[3],
487                        const bool flipnormal)
488 {
489   ScanFillContext sf_ctx;
490   ScanFillVert *sf_vert, *sf_vert_new, *sf_vert_last;
491   ScanFillFace *sf_tri;
492   MemArena *sf_arena;
493   DispList *dlnew = NULL, *dl;
494   float *f1;
495   int colnr = 0, charidx = 0, cont = 1, tot, a, *index, nextcol = 0;
496   int totvert;
497   const int scanfill_flag = BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_POLYS |
498                             BLI_SCANFILL_CALC_HOLES;
499
500   if (dispbase == NULL) {
501     return;
502   }
503   if (BLI_listbase_is_empty(dispbase)) {
504     return;
505   }
506
507   sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
508
509   while (cont) {
510     int dl_flag_accum = 0;
511     cont = 0;
512     totvert = 0;
513     nextcol = 0;
514
515     BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
516
517     dl = dispbase->first;
518     while (dl) {
519       if (dl->type == DL_POLY) {
520         if (charidx < dl->charidx) {
521           cont = 1;
522         }
523         else if (charidx == dl->charidx) { /* character with needed index */
524           if (colnr == dl->col) {
525
526             sf_ctx.poly_nr++;
527
528             /* make editverts and edges */
529             f1 = dl->verts;
530             a = dl->nr;
531             sf_vert = sf_vert_new = NULL;
532
533             while (a--) {
534               sf_vert_last = sf_vert;
535
536               sf_vert = BLI_scanfill_vert_add(&sf_ctx, f1);
537               totvert++;
538
539               if (sf_vert_last == NULL) {
540                 sf_vert_new = sf_vert;
541               }
542               else {
543                 BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
544               }
545               f1 += 3;
546             }
547
548             if (sf_vert != NULL && sf_vert_new != NULL) {
549               BLI_scanfill_edge_add(&sf_ctx, sf_vert, sf_vert_new);
550             }
551           }
552           else if (colnr < dl->col) {
553             /* got poly with next material at current char */
554             cont = 1;
555             nextcol = 1;
556           }
557         }
558         dl_flag_accum |= dl->flag;
559       }
560       dl = dl->next;
561     }
562
563     /* XXX (obedit && obedit->actcol) ? (obedit->actcol - 1) : 0)) { */
564     if (totvert && (tot = BLI_scanfill_calc_ex(&sf_ctx, scanfill_flag, normal_proj))) {
565       if (tot) {
566         dlnew = MEM_callocN(sizeof(DispList), "filldisplist");
567         dlnew->type = DL_INDEX3;
568         dlnew->flag = (dl_flag_accum & (DL_BACK_CURVE | DL_FRONT_CURVE));
569         dlnew->col = colnr;
570         dlnew->nr = totvert;
571         dlnew->parts = tot;
572
573         dlnew->index = MEM_mallocN(tot * 3 * sizeof(int), "dlindex");
574         dlnew->verts = MEM_mallocN(totvert * 3 * sizeof(float), "dlverts");
575
576         /* vert data */
577         f1 = dlnew->verts;
578         totvert = 0;
579
580         for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert->next) {
581           copy_v3_v3(f1, sf_vert->co);
582           f1 += 3;
583
584           /* index number */
585           sf_vert->tmp.i = totvert;
586           totvert++;
587         }
588
589         /* index data */
590
591         index = dlnew->index;
592         for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
593           index[0] = sf_tri->v1->tmp.i;
594           index[1] = sf_tri->v2->tmp.i;
595           index[2] = sf_tri->v3->tmp.i;
596
597           if (flipnormal) {
598             SWAP(int, index[0], index[2]);
599           }
600
601           index += 3;
602         }
603       }
604
605       BLI_addhead(to, dlnew);
606     }
607     BLI_scanfill_end_arena(&sf_ctx, sf_arena);
608
609     if (nextcol) {
610       /* stay at current char but fill polys with next material */
611       colnr++;
612     }
613     else {
614       /* switch to next char and start filling from first material */
615       charidx++;
616       colnr = 0;
617     }
618   }
619
620   BLI_memarena_free(sf_arena);
621
622   /* do not free polys, needed for wireframe display */
623 }
624
625 static void bevels_to_filledpoly(Curve *cu, ListBase *dispbase)
626 {
627   const float z_up[3] = {0.0f, 0.0f, 1.0f};
628   ListBase front, back;
629   DispList *dl, *dlnew;
630   float *fp, *fp1;
631   int a, dpoly;
632
633   BLI_listbase_clear(&front);
634   BLI_listbase_clear(&back);
635
636   dl = dispbase->first;
637   while (dl) {
638     if (dl->type == DL_SURF) {
639       if ((dl->flag & DL_CYCL_V) && (dl->flag & DL_CYCL_U) == 0) {
640         if ((cu->flag & CU_BACK) && (dl->flag & DL_BACK_CURVE)) {
641           dlnew = MEM_callocN(sizeof(DispList), "filldisp");
642           BLI_addtail(&front, dlnew);
643           dlnew->verts = fp1 = MEM_mallocN(sizeof(float) * 3 * dl->parts, "filldisp1");
644           dlnew->nr = dl->parts;
645           dlnew->parts = 1;
646           dlnew->type = DL_POLY;
647           dlnew->flag = DL_BACK_CURVE;
648           dlnew->col = dl->col;
649           dlnew->charidx = dl->charidx;
650
651           fp = dl->verts;
652           dpoly = 3 * dl->nr;
653
654           a = dl->parts;
655           while (a--) {
656             copy_v3_v3(fp1, fp);
657             fp1 += 3;
658             fp += dpoly;
659           }
660         }
661         if ((cu->flag & CU_FRONT) && (dl->flag & DL_FRONT_CURVE)) {
662           dlnew = MEM_callocN(sizeof(DispList), "filldisp");
663           BLI_addtail(&back, dlnew);
664           dlnew->verts = fp1 = MEM_mallocN(sizeof(float) * 3 * dl->parts, "filldisp1");
665           dlnew->nr = dl->parts;
666           dlnew->parts = 1;
667           dlnew->type = DL_POLY;
668           dlnew->flag = DL_FRONT_CURVE;
669           dlnew->col = dl->col;
670           dlnew->charidx = dl->charidx;
671
672           fp = dl->verts + 3 * (dl->nr - 1);
673           dpoly = 3 * dl->nr;
674
675           a = dl->parts;
676           while (a--) {
677             copy_v3_v3(fp1, fp);
678             fp1 += 3;
679             fp += dpoly;
680           }
681         }
682       }
683     }
684     dl = dl->next;
685   }
686
687   BKE_displist_fill(&front, dispbase, z_up, true);
688   BKE_displist_fill(&back, dispbase, z_up, false);
689
690   BKE_displist_free(&front);
691   BKE_displist_free(&back);
692
693   BKE_displist_fill(dispbase, dispbase, z_up, false);
694 }
695
696 static void curve_to_filledpoly(Curve *cu, ListBase *UNUSED(nurb), ListBase *dispbase)
697 {
698   if (!CU_DO_2DFILL(cu)) {
699     return;
700   }
701
702   if (dispbase->first && ((DispList *)dispbase->first)->type == DL_SURF) {
703     bevels_to_filledpoly(cu, dispbase);
704   }
705   else {
706     const float z_up[3] = {0.0f, 0.0f, 1.0f};
707     BKE_displist_fill(dispbase, dispbase, z_up, false);
708   }
709 }
710
711 /* taper rules:
712  * - only 1 curve
713  * - first point left, last point right
714  * - based on subdivided points in original curve, not on points in taper curve (still)
715  */
716 static float displist_calc_taper(Depsgraph *depsgraph, Scene *scene, Object *taperobj, float fac)
717 {
718   DispList *dl;
719
720   if (taperobj == NULL || taperobj->type != OB_CURVE) {
721     return 1.0;
722   }
723
724   dl = taperobj->runtime.curve_cache ? taperobj->runtime.curve_cache->disp.first : NULL;
725   if (dl == NULL) {
726     BKE_displist_make_curveTypes(depsgraph, scene, taperobj, false, false);
727     dl = taperobj->runtime.curve_cache->disp.first;
728   }
729   if (dl) {
730     float minx, dx, *fp;
731     int a;
732
733     /* horizontal size */
734     minx = dl->verts[0];
735     dx = dl->verts[3 * (dl->nr - 1)] - minx;
736     if (dx > 0.0f) {
737       fp = dl->verts;
738       for (a = 0; a < dl->nr; a++, fp += 3) {
739         if ((fp[0] - minx) / dx >= fac) {
740           /* interpolate with prev */
741           if (a > 0) {
742             float fac1 = (fp[-3] - minx) / dx;
743             float fac2 = (fp[0] - minx) / dx;
744             if (fac1 != fac2) {
745               return fp[1] * (fac1 - fac) / (fac1 - fac2) + fp[-2] * (fac - fac2) / (fac1 - fac2);
746             }
747           }
748           return fp[1];
749         }
750       }
751       return fp[-2];  // last y coord
752     }
753   }
754
755   return 1.0;
756 }
757
758 float BKE_displist_calc_taper(
759     Depsgraph *depsgraph, Scene *scene, Object *taperobj, int cur, int tot)
760 {
761   float fac = ((float)cur) / (float)(tot - 1);
762
763   return displist_calc_taper(depsgraph, scene, taperobj, fac);
764 }
765
766 void BKE_displist_make_mball(Depsgraph *depsgraph, Scene *scene, Object *ob)
767 {
768   if (!ob || ob->type != OB_MBALL) {
769     return;
770   }
771
772   if (ob == BKE_mball_basis_find(scene, ob)) {
773     if (ob->runtime.curve_cache) {
774       BKE_displist_free(&(ob->runtime.curve_cache->disp));
775     }
776     else {
777       ob->runtime.curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for MBall");
778     }
779
780     BKE_mball_polygonize(depsgraph, scene, ob, &ob->runtime.curve_cache->disp);
781     BKE_mball_texspace_calc(ob);
782
783     object_deform_mball(ob, &ob->runtime.curve_cache->disp);
784
785     /* NOP for MBALLs anyway... */
786     boundbox_displist_object(ob);
787   }
788 }
789
790 void BKE_displist_make_mball_forRender(Depsgraph *depsgraph,
791                                        Scene *scene,
792                                        Object *ob,
793                                        ListBase *dispbase)
794 {
795   BKE_mball_polygonize(depsgraph, scene, ob, dispbase);
796   BKE_mball_texspace_calc(ob);
797
798   object_deform_mball(ob, dispbase);
799 }
800
801 static ModifierData *curve_get_tessellate_point(Scene *scene,
802                                                 Object *ob,
803                                                 const bool for_render,
804                                                 const bool editmode)
805 {
806   VirtualModifierData virtualModifierData;
807   ModifierData *md = modifiers_getVirtualModifierList(ob, &virtualModifierData);
808   ModifierData *pretessellatePoint;
809   int required_mode;
810
811   if (for_render) {
812     required_mode = eModifierMode_Render;
813   }
814   else {
815     required_mode = eModifierMode_Realtime;
816   }
817
818   if (editmode) {
819     required_mode |= eModifierMode_Editmode;
820   }
821
822   pretessellatePoint = NULL;
823   for (; md; md = md->next) {
824     const ModifierTypeInfo *mti = modifierType_getInfo(md->type);
825
826     if (!modifier_isEnabled(scene, md, required_mode)) {
827       continue;
828     }
829     if (mti->type == eModifierTypeType_Constructive) {
830       return pretessellatePoint;
831     }
832
833     if (ELEM(md->type, eModifierType_Hook, eModifierType_Softbody, eModifierType_MeshDeform)) {
834       pretessellatePoint = md;
835
836       /* this modifiers are moving point of tessellation automatically
837        * (some of them even can't be applied on tessellated curve), set flag
838        * for information button in modifier's header
839        */
840       md->mode |= eModifierMode_ApplyOnSpline;
841     }
842     else if (md->mode & eModifierMode_ApplyOnSpline) {
843       pretessellatePoint = md;
844     }
845   }
846
847   return pretessellatePoint;
848 }
849
850 static void curve_calc_modifiers_pre(
851     Depsgraph *depsgraph, Scene *scene, Object *ob, ListBase *nurb, const bool for_render)
852 {
853   VirtualModifierData virtualModifierData;
854   ModifierData *md = modifiers_getVirtualModifierList(ob, &virtualModifierData);
855   ModifierData *pretessellatePoint;
856   Curve *cu = ob->data;
857   int numElems = 0, numVerts = 0;
858   const bool editmode = (!for_render && (cu->editnurb || cu->editfont));
859   ModifierApplyFlag app_flag = 0;
860   float(*deformedVerts)[3] = NULL;
861   float *keyVerts = NULL;
862   int required_mode;
863
864   modifiers_clearErrors(ob);
865
866   if (editmode) {
867     app_flag |= MOD_APPLY_USECACHE;
868   }
869   if (for_render) {
870     app_flag |= MOD_APPLY_RENDER;
871     required_mode = eModifierMode_Render;
872   }
873   else {
874     required_mode = eModifierMode_Realtime;
875   }
876
877   const ModifierEvalContext mectx = {depsgraph, ob, app_flag};
878
879   pretessellatePoint = curve_get_tessellate_point(scene, ob, for_render, editmode);
880
881   if (editmode) {
882     required_mode |= eModifierMode_Editmode;
883   }
884
885   if (!editmode) {
886     keyVerts = BKE_key_evaluate_object(ob, &numElems);
887
888     if (keyVerts) {
889       BLI_assert(BKE_keyblock_curve_element_count(nurb) == numElems);
890
891       /* split coords from key data, the latter also includes
892        * tilts, which is passed through in the modifier stack.
893        * this is also the reason curves do not use a virtual
894        * shape key modifier yet. */
895       deformedVerts = BKE_curve_nurbs_keyVertexCos_get(nurb, keyVerts);
896       numVerts = BKE_nurbList_verts_count(nurb);
897     }
898   }
899
900   if (pretessellatePoint) {
901     for (; md; md = md->next) {
902       const ModifierTypeInfo *mti = modifierType_getInfo(md->type);
903
904       if (!modifier_isEnabled(scene, md, required_mode)) {
905         continue;
906       }
907       if (mti->type != eModifierTypeType_OnlyDeform) {
908         continue;
909       }
910
911       if (!deformedVerts) {
912         deformedVerts = BKE_curve_nurbs_vertexCos_get(nurb, &numVerts);
913       }
914
915       mti->deformVerts(md, &mectx, NULL, deformedVerts, numVerts);
916
917       if (md == pretessellatePoint) {
918         break;
919       }
920     }
921   }
922
923   if (deformedVerts) {
924     BK_curve_nurbs_vertexCos_apply(nurb, deformedVerts);
925     MEM_freeN(deformedVerts);
926   }
927   if (keyVerts) { /* these are not passed through modifier stack */
928     BKE_curve_nurbs_keyVertexTilts_apply(nurb, keyVerts);
929   }
930
931   if (keyVerts) {
932     MEM_freeN(keyVerts);
933   }
934 }
935
936 static float (*displist_get_allverts(ListBase *dispbase, int *totvert))[3]
937 {
938   DispList *dl;
939   float(*allverts)[3], *fp;
940
941   *totvert = 0;
942
943   for (dl = dispbase->first; dl; dl = dl->next) {
944     *totvert += (dl->type == DL_INDEX3) ? dl->nr : dl->parts * dl->nr;
945   }
946
947   allverts = MEM_mallocN((*totvert) * sizeof(float) * 3, "displist_get_allverts allverts");
948   fp = (float *)allverts;
949   for (dl = dispbase->first; dl; dl = dl->next) {
950     int offs = 3 * ((dl->type == DL_INDEX3) ? dl->nr : dl->parts * dl->nr);
951     memcpy(fp, dl->verts, sizeof(float) * offs);
952     fp += offs;
953   }
954
955   return allverts;
956 }
957
958 static void displist_apply_allverts(ListBase *dispbase, float (*allverts)[3])
959 {
960   DispList *dl;
961   const float *fp;
962
963   fp = (float *)allverts;
964   for (dl = dispbase->first; dl; dl = dl->next) {
965     int offs = 3 * ((dl->type == DL_INDEX3) ? dl->nr : dl->parts * dl->nr);
966     memcpy(dl->verts, fp, sizeof(float) * offs);
967     fp += offs;
968   }
969 }
970
971 static void curve_calc_modifiers_post(Depsgraph *depsgraph,
972                                       Scene *scene,
973                                       Object *ob,
974                                       ListBase *nurb,
975                                       ListBase *dispbase,
976                                       Mesh **r_final,
977                                       const bool for_render)
978 {
979   VirtualModifierData virtualModifierData;
980   ModifierData *md = modifiers_getVirtualModifierList(ob, &virtualModifierData);
981   ModifierData *pretessellatePoint;
982   Curve *cu = ob->data;
983   int required_mode = 0, totvert = 0;
984   const bool editmode = (!for_render && (cu->editnurb || cu->editfont));
985   Mesh *modified = NULL, *mesh_applied;
986   float(*vertCos)[3] = NULL;
987   int useCache = !for_render;
988   ModifierApplyFlag app_flag = 0;
989
990   if (for_render) {
991     app_flag |= MOD_APPLY_RENDER;
992     required_mode = eModifierMode_Render;
993   }
994   else {
995     required_mode = eModifierMode_Realtime;
996   }
997
998   const ModifierEvalContext mectx_deform = {
999       depsgraph, ob, editmode ? app_flag | MOD_APPLY_USECACHE : app_flag};
1000   const ModifierEvalContext mectx_apply = {
1001       depsgraph, ob, useCache ? app_flag | MOD_APPLY_USECACHE : app_flag};
1002
1003   pretessellatePoint = curve_get_tessellate_point(scene, ob, for_render, editmode);
1004
1005   if (editmode) {
1006     required_mode |= eModifierMode_Editmode;
1007   }
1008
1009   if (pretessellatePoint) {
1010     md = pretessellatePoint->next;
1011   }
1012
1013   if (r_final && *r_final) {
1014     BKE_id_free(NULL, *r_final);
1015   }
1016
1017   for (; md; md = md->next) {
1018     const ModifierTypeInfo *mti = modifierType_getInfo(md->type);
1019
1020     if (!modifier_isEnabled(scene, md, required_mode)) {
1021       continue;
1022     }
1023
1024     /* If we need normals, no choice, have to convert to mesh now. */
1025     bool need_normal = mti->dependsOnNormals != NULL && mti->dependsOnNormals(md);
1026     /* XXX 2.8 : now that batch cache is stored inside the ob->data
1027      * we need to create a Mesh for each curve that uses modifiers. */
1028     if (modified == NULL /* && need_normal */) {
1029       if (vertCos != NULL) {
1030         displist_apply_allverts(dispbase, vertCos);
1031       }
1032
1033       if (ELEM(ob->type, OB_CURVE, OB_FONT) && (cu->flag & CU_DEFORM_FILL)) {
1034         curve_to_filledpoly(cu, nurb, dispbase);
1035       }
1036
1037       modified = BKE_mesh_new_nomain_from_curve_displist(ob, dispbase);
1038     }
1039
1040     if (mti->type == eModifierTypeType_OnlyDeform ||
1041         (mti->type == eModifierTypeType_DeformOrConstruct && !modified)) {
1042       if (modified) {
1043         if (!vertCos) {
1044           vertCos = BKE_mesh_vertexCos_get(modified, &totvert);
1045         }
1046         if (need_normal) {
1047           BKE_mesh_ensure_normals(modified);
1048         }
1049         mti->deformVerts(md, &mectx_deform, modified, vertCos, totvert);
1050       }
1051       else {
1052         if (!vertCos) {
1053           vertCos = displist_get_allverts(dispbase, &totvert);
1054         }
1055         mti->deformVerts(md, &mectx_deform, NULL, vertCos, totvert);
1056       }
1057     }
1058     else {
1059       if (!r_final) {
1060         /* makeDisplistCurveTypes could be used for beveling, where derived mesh
1061          * is totally unnecessary, so we could stop modifiers applying
1062          * when we found constructive modifier but derived mesh is unwanted result
1063          */
1064         break;
1065       }
1066
1067       if (modified) {
1068         if (vertCos) {
1069           Mesh *temp_mesh;
1070           BKE_id_copy_ex(NULL, &modified->id, (ID **)&temp_mesh, LIB_ID_COPY_LOCALIZE);
1071           BKE_id_free(NULL, modified);
1072           modified = temp_mesh;
1073
1074           BKE_mesh_apply_vert_coords(modified, vertCos);
1075         }
1076       }
1077       else {
1078         if (vertCos) {
1079           displist_apply_allverts(dispbase, vertCos);
1080         }
1081
1082         if (ELEM(ob->type, OB_CURVE, OB_FONT) && (cu->flag & CU_DEFORM_FILL)) {
1083           curve_to_filledpoly(cu, nurb, dispbase);
1084         }
1085
1086         modified = BKE_mesh_new_nomain_from_curve_displist(ob, dispbase);
1087       }
1088
1089       if (vertCos) {
1090         /* Vertex coordinates were applied to necessary data, could free it */
1091         MEM_freeN(vertCos);
1092         vertCos = NULL;
1093       }
1094
1095       if (need_normal) {
1096         BKE_mesh_ensure_normals(modified);
1097       }
1098       mesh_applied = mti->applyModifier(md, &mectx_apply, modified);
1099
1100       if (mesh_applied) {
1101         /* Modifier returned a new derived mesh */
1102
1103         if (modified && modified != mesh_applied) { /* Modifier  */
1104           BKE_id_free(NULL, modified);
1105         }
1106         modified = mesh_applied;
1107       }
1108     }
1109   }
1110
1111   if (vertCos) {
1112     if (modified) {
1113       Mesh *temp_mesh;
1114       BKE_id_copy_ex(NULL, &modified->id, (ID **)&temp_mesh, LIB_ID_COPY_LOCALIZE);
1115       BKE_id_free(NULL, modified);
1116       modified = temp_mesh;
1117
1118       BKE_mesh_apply_vert_coords(modified, vertCos);
1119       BKE_mesh_calc_normals_mapping_simple(modified);
1120
1121       MEM_freeN(vertCos);
1122     }
1123     else {
1124       displist_apply_allverts(dispbase, vertCos);
1125       MEM_freeN(vertCos);
1126       vertCos = NULL;
1127     }
1128   }
1129
1130   if (r_final) {
1131     if (modified) {
1132       /* see: mesh_calc_modifiers */
1133       if (modified->totface == 0) {
1134         BKE_mesh_tessface_calc(modified);
1135       }
1136       /* Even if tessellation is not needed, some modifiers might have modified CD layers
1137        * (like mloopcol or mloopuv), hence we have to update those. */
1138       else if (modified->runtime.cd_dirty_vert & CD_MASK_TESSLOOPNORMAL) {
1139         BKE_mesh_tessface_calc(modified);
1140       }
1141
1142       /* XXX2.8(Sybren): make sure the face normals are recalculated as well */
1143       BKE_mesh_ensure_normals(modified);
1144
1145       /* Special tweaks, needed since neither BKE_mesh_new_nomain_from_template() nor
1146        * BKE_mesh_new_nomain_from_curve_displist() properly duplicate mat info...
1147        */
1148       BLI_strncpy(modified->id.name, cu->id.name, sizeof(modified->id.name));
1149       *((short *)modified->id.name) = ID_ME;
1150       MEM_SAFE_FREE(modified->mat);
1151       /* Set flag which makes it easier to see what's going on in a debugger. */
1152       modified->id.tag |= LIB_TAG_COPIED_ON_WRITE_EVAL_RESULT;
1153       modified->mat = MEM_dupallocN(cu->mat);
1154       modified->totcol = cu->totcol;
1155
1156       (*r_final) = modified;
1157     }
1158     else {
1159       (*r_final) = NULL;
1160     }
1161   }
1162   else if (modified != NULL) {
1163     /* Prety stupid to generate that whole mesh if it's unused, yet we have to free it. */
1164     BKE_id_free(NULL, modified);
1165   }
1166 }
1167
1168 static void displist_surf_indices(DispList *dl)
1169 {
1170   int a, b, p1, p2, p3, p4;
1171   int *index;
1172
1173   dl->totindex = 0;
1174
1175   index = dl->index = MEM_mallocN(4 * sizeof(int) * (dl->parts + 1) * (dl->nr + 1),
1176                                   "index array nurbs");
1177
1178   for (a = 0; a < dl->parts; a++) {
1179
1180     if (BKE_displist_surfindex_get(dl, a, &b, &p1, &p2, &p3, &p4) == 0) {
1181       break;
1182     }
1183
1184     for (; b < dl->nr; b++, index += 4) {
1185       index[0] = p1;
1186       index[1] = p2;
1187       index[2] = p4;
1188       index[3] = p3;
1189
1190       dl->totindex++;
1191
1192       p2 = p1;
1193       p1++;
1194       p4 = p3;
1195       p3++;
1196     }
1197   }
1198 }
1199
1200 void BKE_displist_make_surf(Depsgraph *depsgraph,
1201                             Scene *scene,
1202                             Object *ob,
1203                             ListBase *dispbase,
1204                             Mesh **r_final,
1205                             const bool for_render,
1206                             const bool for_orco)
1207 {
1208   ListBase nubase = {NULL, NULL};
1209   Nurb *nu;
1210   Curve *cu = ob->data;
1211   DispList *dl;
1212   float *data;
1213   int len;
1214
1215   if (!for_render && cu->editnurb) {
1216     BKE_nurbList_duplicate(&nubase, BKE_curve_editNurbs_get(cu));
1217   }
1218   else {
1219     BKE_nurbList_duplicate(&nubase, &cu->nurb);
1220   }
1221
1222   if (!for_orco) {
1223     curve_calc_modifiers_pre(depsgraph, scene, ob, &nubase, for_render);
1224   }
1225
1226   for (nu = nubase.first; nu; nu = nu->next) {
1227     if ((for_render || nu->hide == 0) && BKE_nurb_check_valid_uv(nu)) {
1228       int resolu = nu->resolu, resolv = nu->resolv;
1229
1230       if (for_render) {
1231         if (cu->resolu_ren) {
1232           resolu = cu->resolu_ren;
1233         }
1234         if (cu->resolv_ren) {
1235           resolv = cu->resolv_ren;
1236         }
1237       }
1238
1239       if (nu->pntsv == 1) {
1240         len = SEGMENTSU(nu) * resolu;
1241
1242         dl = MEM_callocN(sizeof(DispList), "makeDispListsurf");
1243         dl->verts = MEM_mallocN(len * sizeof(float[3]), "dlverts");
1244
1245         BLI_addtail(dispbase, dl);
1246         dl->parts = 1;
1247         dl->nr = len;
1248         dl->col = nu->mat_nr;
1249         dl->charidx = nu->charidx;
1250
1251         /* dl->rt will be used as flag for render face and */
1252         /* CU_2D conflicts with R_NOPUNOFLIP */
1253         dl->rt = nu->flag & ~CU_2D;
1254
1255         data = dl->verts;
1256         if (nu->flagu & CU_NURB_CYCLIC) {
1257           dl->type = DL_POLY;
1258         }
1259         else {
1260           dl->type = DL_SEGM;
1261         }
1262
1263         BKE_nurb_makeCurve(nu, data, NULL, NULL, NULL, resolu, 3 * sizeof(float));
1264       }
1265       else {
1266         len = (nu->pntsu * resolu) * (nu->pntsv * resolv);
1267
1268         dl = MEM_callocN(sizeof(DispList), "makeDispListsurf");
1269         dl->verts = MEM_mallocN(len * sizeof(float[3]), "dlverts");
1270         BLI_addtail(dispbase, dl);
1271
1272         dl->col = nu->mat_nr;
1273         dl->charidx = nu->charidx;
1274
1275         /* dl->rt will be used as flag for render face and */
1276         /* CU_2D conflicts with R_NOPUNOFLIP */
1277         dl->rt = nu->flag & ~CU_2D;
1278
1279         data = dl->verts;
1280         dl->type = DL_SURF;
1281
1282         dl->parts = (nu->pntsu * resolu); /* in reverse, because makeNurbfaces works that way */
1283         dl->nr = (nu->pntsv * resolv);
1284         if (nu->flagv & CU_NURB_CYCLIC) {
1285           dl->flag |= DL_CYCL_U; /* reverse too! */
1286         }
1287         if (nu->flagu & CU_NURB_CYCLIC) {
1288           dl->flag |= DL_CYCL_V;
1289         }
1290
1291         BKE_nurb_makeFaces(nu, data, 0, resolu, resolv);
1292
1293         /* gl array drawing: using indices */
1294         displist_surf_indices(dl);
1295       }
1296     }
1297   }
1298
1299   if (!for_orco) {
1300     BKE_nurbList_duplicate(&ob->runtime.curve_cache->deformed_nurbs, &nubase);
1301     curve_calc_modifiers_post(depsgraph, scene, ob, &nubase, dispbase, r_final, for_render);
1302   }
1303
1304   BKE_nurbList_free(&nubase);
1305 }
1306
1307 static void rotateBevelPiece(Curve *cu,
1308                              BevPoint *bevp,
1309                              BevPoint *nbevp,
1310                              DispList *dlb,
1311                              float bev_blend,
1312                              float widfac,
1313                              float fac,
1314                              float **r_data)
1315 {
1316   float *fp, *data = *r_data;
1317   int b;
1318
1319   fp = dlb->verts;
1320   for (b = 0; b < dlb->nr; b++, fp += 3, data += 3) {
1321     if (cu->flag & CU_3D) {
1322       float vec[3], quat[4];
1323
1324       vec[0] = fp[1] + widfac;
1325       vec[1] = fp[2];
1326       vec[2] = 0.0;
1327
1328       if (nbevp == NULL) {
1329         copy_v3_v3(data, bevp->vec);
1330         copy_qt_qt(quat, bevp->quat);
1331       }
1332       else {
1333         interp_v3_v3v3(data, bevp->vec, nbevp->vec, bev_blend);
1334         interp_qt_qtqt(quat, bevp->quat, nbevp->quat, bev_blend);
1335       }
1336
1337       mul_qt_v3(quat, vec);
1338
1339       data[0] += fac * vec[0];
1340       data[1] += fac * vec[1];
1341       data[2] += fac * vec[2];
1342     }
1343     else {
1344       float sina, cosa;
1345
1346       if (nbevp == NULL) {
1347         copy_v3_v3(data, bevp->vec);
1348         sina = bevp->sina;
1349         cosa = bevp->cosa;
1350       }
1351       else {
1352         interp_v3_v3v3(data, bevp->vec, nbevp->vec, bev_blend);
1353
1354         /* perhaps we need to interpolate angles instead. but the thing is
1355          * cosa and sina are not actually sine and cosine
1356          */
1357         sina = nbevp->sina * bev_blend + bevp->sina * (1.0f - bev_blend);
1358         cosa = nbevp->cosa * bev_blend + bevp->cosa * (1.0f - bev_blend);
1359       }
1360
1361       data[0] += fac * (widfac + fp[1]) * sina;
1362       data[1] += fac * (widfac + fp[1]) * cosa;
1363       data[2] += fac * fp[2];
1364     }
1365   }
1366
1367   *r_data = data;
1368 }
1369
1370 static void fillBevelCap(Nurb *nu, DispList *dlb, float *prev_fp, ListBase *dispbase)
1371 {
1372   DispList *dl;
1373
1374   dl = MEM_callocN(sizeof(DispList), "makeDispListbev2");
1375   dl->verts = MEM_mallocN(sizeof(float[3]) * dlb->nr, "dlverts");
1376   memcpy(dl->verts, prev_fp, 3 * sizeof(float) * dlb->nr);
1377
1378   dl->type = DL_POLY;
1379
1380   dl->parts = 1;
1381   dl->nr = dlb->nr;
1382   dl->col = nu->mat_nr;
1383   dl->charidx = nu->charidx;
1384
1385   /* dl->rt will be used as flag for render face and */
1386   /* CU_2D conflicts with R_NOPUNOFLIP */
1387   dl->rt = nu->flag & ~CU_2D;
1388
1389   BLI_addtail(dispbase, dl);
1390 }
1391
1392 static void calc_bevfac_segment_mapping(
1393     BevList *bl, float bevfac, float spline_length, int *r_bev, float *r_blend)
1394 {
1395   float normlen, normsum = 0.0f;
1396   float *seglen = bl->seglen;
1397   int *segbevcount = bl->segbevcount;
1398   int bevcount = 0, nr = bl->nr;
1399
1400   float bev_fl = bevfac * (bl->nr - 1);
1401   *r_bev = (int)bev_fl;
1402
1403   while (bevcount < nr - 1) {
1404     normlen = *seglen / spline_length;
1405     if (normsum + normlen > bevfac) {
1406       bev_fl = bevcount + (bevfac - normsum) / normlen * *segbevcount;
1407       *r_bev = (int)bev_fl;
1408       *r_blend = bev_fl - *r_bev;
1409       break;
1410     }
1411     normsum += normlen;
1412     bevcount += *segbevcount;
1413     segbevcount++;
1414     seglen++;
1415   }
1416 }
1417
1418 static void calc_bevfac_spline_mapping(
1419     BevList *bl, float bevfac, float spline_length, int *r_bev, float *r_blend)
1420 {
1421   const float len_target = bevfac * spline_length;
1422   BevPoint *bevp = bl->bevpoints;
1423   float len_next = 0.0f, len = 0.0f;
1424   int i = 0, nr = bl->nr;
1425
1426   while (nr--) {
1427     bevp++;
1428     len_next = len + bevp->offset;
1429     if (len_next > len_target) {
1430       break;
1431     }
1432     len = len_next;
1433     i++;
1434   }
1435
1436   *r_bev = i;
1437   *r_blend = (len_target - len) / bevp->offset;
1438 }
1439
1440 static void calc_bevfac_mapping_default(
1441     BevList *bl, int *r_start, float *r_firstblend, int *r_steps, float *r_lastblend)
1442 {
1443   *r_start = 0;
1444   *r_steps = bl->nr;
1445   *r_firstblend = 1.0f;
1446   *r_lastblend = 1.0f;
1447 }
1448
1449 static void calc_bevfac_mapping(Curve *cu,
1450                                 BevList *bl,
1451                                 Nurb *nu,
1452                                 int *r_start,
1453                                 float *r_firstblend,
1454                                 int *r_steps,
1455                                 float *r_lastblend)
1456 {
1457   float tmpf, total_length = 0.0f;
1458   int end = 0, i;
1459
1460   if ((BKE_nurb_check_valid_u(nu) == false) ||
1461       /* not essential, but skips unnecessary calculation */
1462       (min_ff(cu->bevfac1, cu->bevfac2) == 0.0f && max_ff(cu->bevfac1, cu->bevfac2) == 1.0f)) {
1463     calc_bevfac_mapping_default(bl, r_start, r_firstblend, r_steps, r_lastblend);
1464     return;
1465   }
1466
1467   if (ELEM(cu->bevfac1_mapping, CU_BEVFAC_MAP_SEGMENT, CU_BEVFAC_MAP_SPLINE) ||
1468       ELEM(cu->bevfac2_mapping, CU_BEVFAC_MAP_SEGMENT, CU_BEVFAC_MAP_SPLINE)) {
1469     for (i = 0; i < SEGMENTSU(nu); i++) {
1470       total_length += bl->seglen[i];
1471     }
1472   }
1473
1474   switch (cu->bevfac1_mapping) {
1475     case CU_BEVFAC_MAP_RESOLU: {
1476       const float start_fl = cu->bevfac1 * (bl->nr - 1);
1477       *r_start = (int)start_fl;
1478       *r_firstblend = 1.0f - (start_fl - (*r_start));
1479       break;
1480     }
1481     case CU_BEVFAC_MAP_SEGMENT: {
1482       calc_bevfac_segment_mapping(bl, cu->bevfac1, total_length, r_start, r_firstblend);
1483       *r_firstblend = 1.0f - *r_firstblend;
1484       break;
1485     }
1486     case CU_BEVFAC_MAP_SPLINE: {
1487       calc_bevfac_spline_mapping(bl, cu->bevfac1, total_length, r_start, r_firstblend);
1488       *r_firstblend = 1.0f - *r_firstblend;
1489       break;
1490     }
1491   }
1492
1493   switch (cu->bevfac2_mapping) {
1494     case CU_BEVFAC_MAP_RESOLU: {
1495       const float end_fl = cu->bevfac2 * (bl->nr - 1);
1496       end = (int)end_fl;
1497
1498       *r_steps = 2 + end - *r_start;
1499       *r_lastblend = end_fl - end;
1500       break;
1501     }
1502     case CU_BEVFAC_MAP_SEGMENT: {
1503       calc_bevfac_segment_mapping(bl, cu->bevfac2, total_length, &end, r_lastblend);
1504       *r_steps = end - *r_start + 2;
1505       break;
1506     }
1507     case CU_BEVFAC_MAP_SPLINE: {
1508       calc_bevfac_spline_mapping(bl, cu->bevfac2, total_length, &end, r_lastblend);
1509       *r_steps = end - *r_start + 2;
1510       break;
1511     }
1512   }
1513
1514   if (end < *r_start || (end == *r_start && *r_lastblend < 1.0f - *r_firstblend)) {
1515     SWAP(int, *r_start, end);
1516     tmpf = *r_lastblend;
1517     *r_lastblend = 1.0f - *r_firstblend;
1518     *r_firstblend = 1.0f - tmpf;
1519     *r_steps = end - *r_start + 2;
1520   }
1521
1522   if (*r_start + *r_steps > bl->nr) {
1523     *r_steps = bl->nr - *r_start;
1524     *r_lastblend = 1.0f;
1525   }
1526 }
1527
1528 static void do_makeDispListCurveTypes(Depsgraph *depsgraph,
1529                                       Scene *scene,
1530                                       Object *ob,
1531                                       ListBase *dispbase,
1532                                       const bool for_render,
1533                                       const bool for_orco,
1534                                       Mesh **r_final)
1535 {
1536   Curve *cu = ob->data;
1537
1538   /* we do allow duplis... this is only displist on curve level */
1539   if (!ELEM(ob->type, OB_SURF, OB_CURVE, OB_FONT)) {
1540     return;
1541   }
1542
1543   if (ob->type == OB_SURF) {
1544     BKE_displist_make_surf(depsgraph, scene, ob, dispbase, r_final, for_render, for_orco);
1545   }
1546   else if (ELEM(ob->type, OB_CURVE, OB_FONT)) {
1547     ListBase dlbev;
1548     ListBase nubase = {NULL, NULL};
1549
1550     BKE_curve_bevelList_free(&ob->runtime.curve_cache->bev);
1551
1552     /* We only re-evaluate path if evaluation is not happening for orco.
1553      * If the calculation happens for orco, we should never free data which
1554      * was needed before and only not needed for orco calculation.
1555      */
1556     if (!for_orco) {
1557       if (ob->runtime.curve_cache->path) {
1558         free_path(ob->runtime.curve_cache->path);
1559       }
1560       ob->runtime.curve_cache->path = NULL;
1561     }
1562
1563     if (ob->type == OB_FONT) {
1564       BKE_vfont_to_curve_nubase(ob, FO_EDIT, &nubase);
1565     }
1566     else {
1567       BKE_nurbList_duplicate(&nubase, BKE_curve_nurbs_get(cu));
1568     }
1569
1570     if (!for_orco) {
1571       curve_calc_modifiers_pre(depsgraph, scene, ob, &nubase, for_render);
1572     }
1573
1574     BKE_curve_bevelList_make(ob, &nubase, for_render);
1575
1576     /* If curve has no bevel will return nothing */
1577     BKE_curve_bevel_make(ob, &dlbev);
1578
1579     /* no bevel or extrude, and no width correction? */
1580     if (!dlbev.first && cu->width == 1.0f) {
1581       curve_to_displist(cu, &nubase, dispbase, for_render);
1582     }
1583     else {
1584       float widfac = cu->width - 1.0f;
1585       BevList *bl = ob->runtime.curve_cache->bev.first;
1586       Nurb *nu = nubase.first;
1587
1588       for (; bl && nu; bl = bl->next, nu = nu->next) {
1589         DispList *dl;
1590         float *data;
1591         int a;
1592
1593         if (bl->nr) { /* blank bevel lists can happen */
1594
1595           /* exception handling; curve without bevel or extrude, with width correction */
1596           if (BLI_listbase_is_empty(&dlbev)) {
1597             BevPoint *bevp;
1598             dl = MEM_callocN(sizeof(DispList), "makeDispListbev");
1599             dl->verts = MEM_mallocN(sizeof(float[3]) * bl->nr, "dlverts");
1600             BLI_addtail(dispbase, dl);
1601
1602             if (bl->poly != -1) {
1603               dl->type = DL_POLY;
1604             }
1605             else {
1606               dl->type = DL_SEGM;
1607             }
1608
1609             if (dl->type == DL_SEGM) {
1610               dl->flag = (DL_FRONT_CURVE | DL_BACK_CURVE);
1611             }
1612
1613             dl->parts = 1;
1614             dl->nr = bl->nr;
1615             dl->col = nu->mat_nr;
1616             dl->charidx = nu->charidx;
1617
1618             /* dl->rt will be used as flag for render face and */
1619             /* CU_2D conflicts with R_NOPUNOFLIP */
1620             dl->rt = nu->flag & ~CU_2D;
1621
1622             a = dl->nr;
1623             bevp = bl->bevpoints;
1624             data = dl->verts;
1625             while (a--) {
1626               data[0] = bevp->vec[0] + widfac * bevp->sina;
1627               data[1] = bevp->vec[1] + widfac * bevp->cosa;
1628               data[2] = bevp->vec[2];
1629               bevp++;
1630               data += 3;
1631             }
1632           }
1633           else {
1634             DispList *dlb;
1635             ListBase bottom_capbase = {NULL, NULL};
1636             ListBase top_capbase = {NULL, NULL};
1637             float bottom_no[3] = {0.0f};
1638             float top_no[3] = {0.0f};
1639             float firstblend = 0.0f, lastblend = 0.0f;
1640             int i, start, steps = 0;
1641
1642             if (nu->flagu & CU_NURB_CYCLIC) {
1643               calc_bevfac_mapping_default(bl, &start, &firstblend, &steps, &lastblend);
1644             }
1645             else {
1646               if (fabsf(cu->bevfac2 - cu->bevfac1) < FLT_EPSILON) {
1647                 continue;
1648               }
1649
1650               calc_bevfac_mapping(cu, bl, nu, &start, &firstblend, &steps, &lastblend);
1651             }
1652
1653             for (dlb = dlbev.first; dlb; dlb = dlb->next) {
1654               BevPoint *bevp_first, *bevp_last;
1655               BevPoint *bevp;
1656
1657               /* for each part of the bevel use a separate displblock */
1658               dl = MEM_callocN(sizeof(DispList), "makeDispListbev1");
1659               dl->verts = data = MEM_mallocN(sizeof(float[3]) * dlb->nr * steps, "dlverts");
1660               BLI_addtail(dispbase, dl);
1661
1662               dl->type = DL_SURF;
1663
1664               dl->flag = dlb->flag & (DL_FRONT_CURVE | DL_BACK_CURVE);
1665               if (dlb->type == DL_POLY) {
1666                 dl->flag |= DL_CYCL_U;
1667               }
1668               if ((bl->poly >= 0) && (steps > 2)) {
1669                 dl->flag |= DL_CYCL_V;
1670               }
1671
1672               dl->parts = steps;
1673               dl->nr = dlb->nr;
1674               dl->col = nu->mat_nr;
1675               dl->charidx = nu->charidx;
1676
1677               /* dl->rt will be used as flag for render face and */
1678               /* CU_2D conflicts with R_NOPUNOFLIP */
1679               dl->rt = nu->flag & ~CU_2D;
1680
1681               dl->bevel_split = BLI_BITMAP_NEW(steps, "bevel_split");
1682
1683               /* for each point of poly make a bevel piece */
1684               bevp_first = bl->bevpoints;
1685               bevp_last = &bl->bevpoints[bl->nr - 1];
1686               bevp = &bl->bevpoints[start];
1687               for (i = start, a = 0; a < steps; i++, bevp++, a++) {
1688                 float fac = 1.0;
1689                 float *cur_data = data;
1690
1691                 if (cu->taperobj == NULL) {
1692                   fac = bevp->radius;
1693                 }
1694                 else {
1695                   float len, taper_fac;
1696
1697                   if (cu->flag & CU_MAP_TAPER) {
1698                     len = (steps - 3) + firstblend + lastblend;
1699
1700                     if (a == 0) {
1701                       taper_fac = 0.0f;
1702                     }
1703                     else if (a == steps - 1) {
1704                       taper_fac = 1.0f;
1705                     }
1706                     else {
1707                       taper_fac = ((float)a - (1.0f - firstblend)) / len;
1708                     }
1709                   }
1710                   else {
1711                     len = bl->nr - 1;
1712                     taper_fac = (float)i / len;
1713
1714                     if (a == 0) {
1715                       taper_fac += (1.0f - firstblend) / len;
1716                     }
1717                     else if (a == steps - 1) {
1718                       taper_fac -= (1.0f - lastblend) / len;
1719                     }
1720                   }
1721
1722                   fac = displist_calc_taper(depsgraph, scene, cu->taperobj, taper_fac);
1723                 }
1724
1725                 if (bevp->split_tag) {
1726                   BLI_BITMAP_ENABLE(dl->bevel_split, a);
1727                 }
1728
1729                 /* rotate bevel piece and write in data */
1730                 if ((a == 0) && (bevp != bevp_last)) {
1731                   rotateBevelPiece(cu, bevp, bevp + 1, dlb, 1.0f - firstblend, widfac, fac, &data);
1732                 }
1733                 else if ((a == steps - 1) && (bevp != bevp_first)) {
1734                   rotateBevelPiece(cu, bevp, bevp - 1, dlb, 1.0f - lastblend, widfac, fac, &data);
1735                 }
1736                 else {
1737                   rotateBevelPiece(cu, bevp, NULL, dlb, 0.0f, widfac, fac, &data);
1738                 }
1739
1740                 if (cu->bevobj && (cu->flag & CU_FILL_CAPS) && !(nu->flagu & CU_NURB_CYCLIC)) {
1741                   if (a == 1) {
1742                     fillBevelCap(nu, dlb, cur_data - 3 * dlb->nr, &bottom_capbase);
1743                     negate_v3_v3(bottom_no, bevp->dir);
1744                   }
1745                   if (a == steps - 1) {
1746                     fillBevelCap(nu, dlb, cur_data, &top_capbase);
1747                     copy_v3_v3(top_no, bevp->dir);
1748                   }
1749                 }
1750               }
1751
1752               /* gl array drawing: using indices */
1753               displist_surf_indices(dl);
1754             }
1755
1756             if (bottom_capbase.first) {
1757               BKE_displist_fill(&bottom_capbase, dispbase, bottom_no, false);
1758               BKE_displist_fill(&top_capbase, dispbase, top_no, false);
1759               BKE_displist_free(&bottom_capbase);
1760               BKE_displist_free(&top_capbase);
1761             }
1762           }
1763         }
1764       }
1765       BKE_displist_free(&dlbev);
1766     }
1767
1768     if (!(cu->flag & CU_DEFORM_FILL)) {
1769       curve_to_filledpoly(cu, &nubase, dispbase);
1770     }
1771
1772     if (!for_orco) {
1773       if ((cu->flag & CU_PATH) ||
1774           DEG_get_eval_flags_for_id(depsgraph, &ob->id) & DAG_EVAL_NEED_CURVE_PATH) {
1775         calc_curvepath(ob, &nubase);
1776       }
1777     }
1778
1779     if (!for_orco) {
1780       BKE_nurbList_duplicate(&ob->runtime.curve_cache->deformed_nurbs, &nubase);
1781       curve_calc_modifiers_post(depsgraph, scene, ob, &nubase, dispbase, r_final, for_render);
1782     }
1783
1784     if (cu->flag & CU_DEFORM_FILL && !ob->runtime.mesh_eval) {
1785       curve_to_filledpoly(cu, &nubase, dispbase);
1786     }
1787
1788     BKE_nurbList_free(&nubase);
1789   }
1790 }
1791
1792 void BKE_displist_make_curveTypes(
1793     Depsgraph *depsgraph, Scene *scene, Object *ob, const bool for_render, const bool for_orco)
1794 {
1795   ListBase *dispbase;
1796
1797   /* The same check for duplis as in do_makeDispListCurveTypes.
1798    * Happens when curve used for constraint/bevel was converted to mesh.
1799    * check there is still needed for render displist and orco displists. */
1800   if (!ELEM(ob->type, OB_SURF, OB_CURVE, OB_FONT)) {
1801     return;
1802   }
1803
1804   BKE_object_free_derived_caches(ob);
1805
1806   if (!ob->runtime.curve_cache) {
1807     ob->runtime.curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for curve types");
1808   }
1809
1810   dispbase = &(ob->runtime.curve_cache->disp);
1811
1812   do_makeDispListCurveTypes(
1813       depsgraph, scene, ob, dispbase, for_render, for_orco, &ob->runtime.mesh_eval);
1814
1815   if (ob->runtime.mesh_eval != NULL) {
1816     ob->runtime.mesh_eval->id.tag |= LIB_TAG_COPIED_ON_WRITE_EVAL_RESULT;
1817     ob->runtime.is_mesh_eval_owned = true;
1818   }
1819
1820   boundbox_displist_object(ob);
1821 }
1822
1823 void BKE_displist_make_curveTypes_forRender(Depsgraph *depsgraph,
1824                                             Scene *scene,
1825                                             Object *ob,
1826                                             ListBase *dispbase,
1827                                             Mesh **r_final,
1828                                             const bool for_orco)
1829 {
1830   if (ob->runtime.curve_cache == NULL) {
1831     ob->runtime.curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for Curve");
1832   }
1833
1834   do_makeDispListCurveTypes(depsgraph, scene, ob, dispbase, true, for_orco, r_final);
1835 }
1836
1837 void BKE_displist_minmax(ListBase *dispbase, float min[3], float max[3])
1838 {
1839   DispList *dl;
1840   const float *vert;
1841   int a, tot = 0;
1842   int doit = 0;
1843
1844   for (dl = dispbase->first; dl; dl = dl->next) {
1845     tot = (dl->type == DL_INDEX3) ? dl->nr : dl->nr * dl->parts;
1846     vert = dl->verts;
1847     for (a = 0; a < tot; a++, vert += 3) {
1848       minmax_v3v3_v3(min, max, vert);
1849     }
1850     doit |= (tot != 0);
1851   }
1852
1853   if (!doit) {
1854     /* there's no geometry in displist, use zero-sized boundbox */
1855     zero_v3(min);
1856     zero_v3(max);
1857   }
1858 }
1859
1860 /* this is confusing, there's also min_max_object, appplying the obmat... */
1861 static void boundbox_displist_object(Object *ob)
1862 {
1863   if (ELEM(ob->type, OB_CURVE, OB_SURF, OB_FONT)) {
1864     /* Curve's BB is already calculated as a part of modifier stack,
1865      * here we only calculate object BB based on final display list.
1866      */
1867
1868     /* object's BB is calculated from final displist */
1869     if (ob->runtime.bb == NULL) {
1870       ob->runtime.bb = MEM_callocN(sizeof(BoundBox), "boundbox");
1871     }
1872
1873     if (ob->runtime.mesh_eval) {
1874       BKE_object_boundbox_calc_from_mesh(ob, ob->runtime.mesh_eval);
1875     }
1876     else {
1877       float min[3], max[3];
1878
1879       INIT_MINMAX(min, max);
1880       BKE_displist_minmax(&ob->runtime.curve_cache->disp, min, max);
1881       BKE_boundbox_init_from_minmax(ob->runtime.bb, min, max);
1882
1883       ob->runtime.bb->flag &= ~BOUNDBOX_DIRTY;
1884     }
1885   }
1886 }