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