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_object_types.h"
33 #include "DNA_scene_types.h"
34 #include "DNA_vfont_types.h"
35 
36 #include "BLI_bitmap.h"
37 #include "BLI_linklist.h"
38 #include "BLI_listbase.h"
39 #include "BLI_math.h"
40 #include "BLI_memarena.h"
41 #include "BLI_scanfill.h"
42 #include "BLI_string.h"
43 #include "BLI_utildefines.h"
44 
45 #include "BKE_anim_path.h"
46 #include "BKE_curve.h"
47 #include "BKE_displist.h"
48 #include "BKE_font.h"
49 #include "BKE_key.h"
50 #include "BKE_lattice.h"
51 #include "BKE_lib_id.h"
52 #include "BKE_mball.h"
53 #include "BKE_mball_tessellate.h"
54 #include "BKE_mesh.h"
55 #include "BKE_modifier.h"
56 #include "BKE_object.h"
57 
58 #include "BLI_sys_types.h"  // for intptr_t support
59 
60 #include "DEG_depsgraph.h"
61 #include "DEG_depsgraph_query.h"
62 
63 static void boundbox_displist_object(Object *ob);
64 
BKE_displist_elem_free(DispList * dl)65 void BKE_displist_elem_free(DispList *dl)
66 {
67   if (dl) {
68     if (dl->verts) {
69       MEM_freeN(dl->verts);
70     }
71     if (dl->nors) {
72       MEM_freeN(dl->nors);
73     }
74     if (dl->index) {
75       MEM_freeN(dl->index);
76     }
77     if (dl->bevel_split) {
78       MEM_freeN(dl->bevel_split);
79     }
80     MEM_freeN(dl);
81   }
82 }
83 
BKE_displist_free(ListBase * lb)84 void BKE_displist_free(ListBase *lb)
85 {
86   DispList *dl;
87 
88   while ((dl = BLI_pophead(lb))) {
89     BKE_displist_elem_free(dl);
90   }
91 }
92 
BKE_displist_find_or_create(ListBase * lb,int type)93 DispList *BKE_displist_find_or_create(ListBase *lb, int type)
94 {
95   DispList *dl;
96 
97   dl = lb->first;
98   while (dl) {
99     if (dl->type == type) {
100       return dl;
101     }
102     dl = dl->next;
103   }
104 
105   dl = MEM_callocN(sizeof(DispList), "find_disp");
106   dl->type = type;
107   BLI_addtail(lb, dl);
108 
109   return dl;
110 }
111 
BKE_displist_find(ListBase * lb,int type)112 DispList *BKE_displist_find(ListBase *lb, int type)
113 {
114   DispList *dl;
115 
116   dl = lb->first;
117   while (dl) {
118     if (dl->type == type) {
119       return dl;
120     }
121     dl = dl->next;
122   }
123 
124   return NULL;
125 }
126 
BKE_displist_has_faces(ListBase * lb)127 bool BKE_displist_has_faces(ListBase *lb)
128 {
129   DispList *dl;
130 
131   for (dl = lb->first; dl; dl = dl->next) {
132     if (ELEM(dl->type, DL_INDEX3, DL_INDEX4, DL_SURF)) {
133       return true;
134     }
135   }
136 
137   return false;
138 }
139 
BKE_displist_copy(ListBase * lbn,ListBase * lb)140 void BKE_displist_copy(ListBase *lbn, ListBase *lb)
141 {
142   DispList *dln, *dl;
143 
144   BKE_displist_free(lbn);
145 
146   dl = lb->first;
147   while (dl) {
148     dln = MEM_dupallocN(dl);
149     BLI_addtail(lbn, dln);
150     dln->verts = MEM_dupallocN(dl->verts);
151     dln->nors = MEM_dupallocN(dl->nors);
152     dln->index = MEM_dupallocN(dl->index);
153 
154     if (dl->bevel_split) {
155       dln->bevel_split = MEM_dupallocN(dl->bevel_split);
156     }
157 
158     dl = dl->next;
159   }
160 }
161 
BKE_displist_normals_add(ListBase * lb)162 void BKE_displist_normals_add(ListBase *lb)
163 {
164   DispList *dl = NULL;
165   float *vdata, *ndata, nor[3];
166   float *v1, *v2, *v3, *v4;
167   float *n1, *n2, *n3, *n4;
168   int a, b, p1, p2, p3, p4;
169 
170   dl = lb->first;
171 
172   while (dl) {
173     if (dl->type == DL_INDEX3) {
174       if (dl->nors == NULL) {
175         dl->nors = MEM_callocN(sizeof(float[3]), "dlnors");
176 
177         if (dl->flag & DL_BACK_CURVE) {
178           dl->nors[2] = -1.0f;
179         }
180         else {
181           dl->nors[2] = 1.0f;
182         }
183       }
184     }
185     else if (dl->type == DL_SURF) {
186       if (dl->nors == NULL) {
187         dl->nors = MEM_callocN(sizeof(float[3]) * dl->nr * dl->parts, "dlnors");
188 
189         vdata = dl->verts;
190         ndata = dl->nors;
191 
192         for (a = 0; a < dl->parts; a++) {
193 
194           if (BKE_displist_surfindex_get(dl, a, &b, &p1, &p2, &p3, &p4) == 0) {
195             break;
196           }
197 
198           v1 = vdata + 3 * p1;
199           n1 = ndata + 3 * p1;
200           v2 = vdata + 3 * p2;
201           n2 = ndata + 3 * p2;
202           v3 = vdata + 3 * p3;
203           n3 = ndata + 3 * p3;
204           v4 = vdata + 3 * p4;
205           n4 = ndata + 3 * p4;
206 
207           for (; b < dl->nr; b++) {
208             normal_quad_v3(nor, v1, v3, v4, v2);
209 
210             add_v3_v3(n1, nor);
211             add_v3_v3(n2, nor);
212             add_v3_v3(n3, nor);
213             add_v3_v3(n4, nor);
214 
215             v2 = v1;
216             v1 += 3;
217             v4 = v3;
218             v3 += 3;
219             n2 = n1;
220             n1 += 3;
221             n4 = n3;
222             n3 += 3;
223           }
224         }
225         a = dl->parts * dl->nr;
226         v1 = ndata;
227         while (a--) {
228           normalize_v3(v1);
229           v1 += 3;
230         }
231       }
232     }
233     dl = dl->next;
234   }
235 }
236 
BKE_displist_count(ListBase * lb,int * totvert,int * totface,int * tottri)237 void BKE_displist_count(ListBase *lb, int *totvert, int *totface, int *tottri)
238 {
239   DispList *dl;
240 
241   for (dl = lb->first; dl; dl = dl->next) {
242     int vert_tot = 0;
243     int face_tot = 0;
244     int tri_tot = 0;
245     bool cyclic_u = dl->flag & DL_CYCL_U;
246     bool cyclic_v = dl->flag & DL_CYCL_V;
247 
248     switch (dl->type) {
249       case DL_SURF: {
250         int segments_u = dl->nr - (cyclic_u == false);
251         int segments_v = dl->parts - (cyclic_v == false);
252         vert_tot = dl->nr * dl->parts;
253         face_tot = segments_u * segments_v;
254         tri_tot = face_tot * 2;
255         break;
256       }
257       case DL_INDEX3: {
258         vert_tot = dl->nr;
259         face_tot = dl->parts;
260         tri_tot = face_tot;
261         break;
262       }
263       case DL_INDEX4: {
264         vert_tot = dl->nr;
265         face_tot = dl->parts;
266         tri_tot = face_tot * 2;
267         break;
268       }
269       case DL_POLY:
270       case DL_SEGM: {
271         vert_tot = dl->nr * dl->parts;
272         break;
273       }
274     }
275 
276     *totvert += vert_tot;
277     *totface += face_tot;
278     *tottri += tri_tot;
279   }
280 }
281 
BKE_displist_surfindex_get(DispList * dl,int a,int * b,int * p1,int * p2,int * p3,int * p4)282 bool BKE_displist_surfindex_get(DispList *dl, int a, int *b, int *p1, int *p2, int *p3, int *p4)
283 {
284   if ((dl->flag & DL_CYCL_V) == 0 && a == (dl->parts) - 1) {
285     return false;
286   }
287 
288   if (dl->flag & DL_CYCL_U) {
289     (*p1) = dl->nr * a;
290     (*p2) = (*p1) + dl->nr - 1;
291     (*p3) = (*p1) + dl->nr;
292     (*p4) = (*p2) + dl->nr;
293     (*b) = 0;
294   }
295   else {
296     (*p2) = dl->nr * a;
297     (*p1) = (*p2) + 1;
298     (*p4) = (*p2) + dl->nr;
299     (*p3) = (*p1) + dl->nr;
300     (*b) = 1;
301   }
302 
303   if ((dl->flag & DL_CYCL_V) && a == dl->parts - 1) {
304     (*p3) -= dl->nr * dl->parts;
305     (*p4) -= dl->nr * dl->parts;
306   }
307 
308   return true;
309 }
310 
311 /* ****************** make displists ********************* */
312 #ifdef __INTEL_COMPILER
313 /* ICC with the optimization -02 causes crashes. */
314 #  pragma intel optimization_level 1
315 #endif
curve_to_displist(Curve * cu,ListBase * nubase,ListBase * dispbase,const bool for_render)316 static void curve_to_displist(Curve *cu,
317                               ListBase *nubase,
318                               ListBase *dispbase,
319                               const bool for_render)
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 (for_render && 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                                             sizeof(float[3]));
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, sizeof(float[3]));
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 that's 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  */
BKE_displist_fill(ListBase * dispbase,ListBase * to,const float normal_proj[3],const bool flipnormal)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(sizeof(int[3]) * tot, "dlindex");
575         dlnew->verts = MEM_mallocN(sizeof(float[3]) * totvert, "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 
bevels_to_filledpoly(Curve * cu,ListBase * dispbase)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 
curve_to_filledpoly(Curve * cu,ListBase * UNUSED (nurb),ListBase * dispbase)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  */
displist_calc_taper(Depsgraph * depsgraph,Scene * scene,Object * taperobj,float fac)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);
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 
BKE_displist_calc_taper(Depsgraph * depsgraph,Scene * scene,Object * taperobj,int cur,int tot)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 
BKE_displist_make_mball(Depsgraph * depsgraph,Scene * scene,Object * ob)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 
BKE_displist_make_mball_forRender(Depsgraph * depsgraph,Scene * scene,Object * ob,ListBase * dispbase)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 
curve_get_tessellate_point(Scene * scene,Object * ob,const bool for_render,const bool editmode)802 static ModifierData *curve_get_tessellate_point(Scene *scene,
803                                                 Object *ob,
804                                                 const bool for_render,
805                                                 const bool editmode)
806 {
807   VirtualModifierData virtualModifierData;
808   ModifierData *md = BKE_modifiers_get_virtual_modifierlist(ob, &virtualModifierData);
809   ModifierData *pretessellatePoint;
810   int required_mode;
811 
812   if (for_render) {
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 = BKE_modifier_get_info(md->type);
826 
827     if (!BKE_modifier_is_enabled(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 /* Return true if any modifier was applied. */
curve_calc_modifiers_pre(Depsgraph * depsgraph,Scene * scene,Object * ob,ListBase * nurb,const bool for_render)852 static bool curve_calc_modifiers_pre(
853     Depsgraph *depsgraph, Scene *scene, Object *ob, ListBase *nurb, const bool for_render)
854 {
855   VirtualModifierData virtualModifierData;
856   ModifierData *md = BKE_modifiers_get_virtual_modifierlist(ob, &virtualModifierData);
857   ModifierData *pretessellatePoint;
858   Curve *cu = ob->data;
859   int numElems = 0, numVerts = 0;
860   const bool editmode = (!for_render && (cu->editnurb || cu->editfont));
861   ModifierApplyFlag apply_flag = 0;
862   float(*deformedVerts)[3] = NULL;
863   float *keyVerts = NULL;
864   int required_mode;
865   bool modified = false;
866 
867   BKE_modifiers_clear_errors(ob);
868 
869   if (editmode) {
870     apply_flag |= MOD_APPLY_USECACHE;
871   }
872   if (for_render) {
873     apply_flag |= MOD_APPLY_RENDER;
874     required_mode = eModifierMode_Render;
875   }
876   else {
877     required_mode = eModifierMode_Realtime;
878   }
879 
880   const ModifierEvalContext mectx = {depsgraph, ob, apply_flag};
881 
882   pretessellatePoint = curve_get_tessellate_point(scene, ob, for_render, editmode);
883 
884   if (editmode) {
885     required_mode |= eModifierMode_Editmode;
886   }
887 
888   if (!editmode) {
889     keyVerts = BKE_key_evaluate_object(ob, &numElems);
890 
891     if (keyVerts) {
892       BLI_assert(BKE_keyblock_curve_element_count(nurb) == numElems);
893 
894       /* split coords from key data, the latter also includes
895        * tilts, which is passed through in the modifier stack.
896        * this is also the reason curves do not use a virtual
897        * shape key modifier yet. */
898       deformedVerts = BKE_curve_nurbs_key_vert_coords_alloc(nurb, keyVerts, &numVerts);
899     }
900   }
901 
902   if (pretessellatePoint) {
903     for (; md; md = md->next) {
904       const ModifierTypeInfo *mti = BKE_modifier_get_info(md->type);
905 
906       if (!BKE_modifier_is_enabled(scene, md, required_mode)) {
907         continue;
908       }
909       if (mti->type != eModifierTypeType_OnlyDeform) {
910         continue;
911       }
912 
913       if (!deformedVerts) {
914         deformedVerts = BKE_curve_nurbs_vert_coords_alloc(nurb, &numVerts);
915       }
916 
917       mti->deformVerts(md, &mectx, NULL, deformedVerts, numVerts);
918       modified = true;
919 
920       if (md == pretessellatePoint) {
921         break;
922       }
923     }
924   }
925 
926   if (deformedVerts) {
927     BKE_curve_nurbs_vert_coords_apply(nurb, deformedVerts, false);
928     MEM_freeN(deformedVerts);
929   }
930   if (keyVerts) { /* these are not passed through modifier stack */
931     BKE_curve_nurbs_key_vert_tilts_apply(nurb, keyVerts);
932   }
933 
934   if (keyVerts) {
935     MEM_freeN(keyVerts);
936   }
937   return modified;
938 }
939 
displist_vert_coords_alloc(ListBase * dispbase,int * r_vert_len)940 static float (*displist_vert_coords_alloc(ListBase *dispbase, int *r_vert_len))[3]
941 {
942   DispList *dl;
943   float(*allverts)[3], *fp;
944 
945   *r_vert_len = 0;
946 
947   for (dl = dispbase->first; dl; dl = dl->next) {
948     *r_vert_len += (dl->type == DL_INDEX3) ? dl->nr : dl->parts * dl->nr;
949   }
950 
951   allverts = MEM_mallocN(sizeof(float[3]) * (*r_vert_len), "displist_vert_coords_alloc allverts");
952   fp = (float *)allverts;
953   for (dl = dispbase->first; dl; dl = dl->next) {
954     int offs = 3 * ((dl->type == DL_INDEX3) ? dl->nr : dl->parts * dl->nr);
955     memcpy(fp, dl->verts, sizeof(float) * offs);
956     fp += offs;
957   }
958 
959   return allverts;
960 }
961 
displist_vert_coords_apply(ListBase * dispbase,float (* allverts)[3])962 static void displist_vert_coords_apply(ListBase *dispbase, float (*allverts)[3])
963 {
964   DispList *dl;
965   const float *fp;
966 
967   fp = (float *)allverts;
968   for (dl = dispbase->first; dl; dl = dl->next) {
969     int offs = 3 * ((dl->type == DL_INDEX3) ? dl->nr : dl->parts * dl->nr);
970     memcpy(dl->verts, fp, sizeof(float) * offs);
971     fp += offs;
972   }
973 }
974 
curve_calc_modifiers_post(Depsgraph * depsgraph,Scene * scene,Object * ob,ListBase * nurb,ListBase * dispbase,Mesh ** r_final,const bool for_render,const bool force_mesh_conversion)975 static void curve_calc_modifiers_post(Depsgraph *depsgraph,
976                                       Scene *scene,
977                                       Object *ob,
978                                       ListBase *nurb,
979                                       ListBase *dispbase,
980                                       Mesh **r_final,
981                                       const bool for_render,
982                                       const bool force_mesh_conversion)
983 {
984   VirtualModifierData virtualModifierData;
985   ModifierData *md = BKE_modifiers_get_virtual_modifierlist(ob, &virtualModifierData);
986   ModifierData *pretessellatePoint;
987   Curve *cu = ob->data;
988   int required_mode = 0, totvert = 0;
989   const bool editmode = (!for_render && (cu->editnurb || cu->editfont));
990   Mesh *modified = NULL, *mesh_applied;
991   float(*vertCos)[3] = NULL;
992   int useCache = !for_render;
993   ModifierApplyFlag apply_flag = 0;
994 
995   if (for_render) {
996     apply_flag |= MOD_APPLY_RENDER;
997     required_mode = eModifierMode_Render;
998   }
999   else {
1000     required_mode = eModifierMode_Realtime;
1001   }
1002 
1003   const ModifierEvalContext mectx_deform = {
1004       depsgraph, ob, editmode ? apply_flag | MOD_APPLY_USECACHE : apply_flag};
1005   const ModifierEvalContext mectx_apply = {
1006       depsgraph, ob, useCache ? apply_flag | MOD_APPLY_USECACHE : apply_flag};
1007 
1008   pretessellatePoint = curve_get_tessellate_point(scene, ob, for_render, editmode);
1009 
1010   if (editmode) {
1011     required_mode |= eModifierMode_Editmode;
1012   }
1013 
1014   if (pretessellatePoint) {
1015     md = pretessellatePoint->next;
1016   }
1017 
1018   if (r_final && *r_final) {
1019     BKE_id_free(NULL, *r_final);
1020   }
1021 
1022   for (; md; md = md->next) {
1023     const ModifierTypeInfo *mti = BKE_modifier_get_info(md->type);
1024 
1025     if (!BKE_modifier_is_enabled(scene, md, required_mode)) {
1026       continue;
1027     }
1028 
1029     /* If we need normals, no choice, have to convert to mesh now. */
1030     bool need_normal = mti->dependsOnNormals != NULL && mti->dependsOnNormals(md);
1031     /* XXX 2.8 : now that batch cache is stored inside the ob->data
1032      * we need to create a Mesh for each curve that uses modifiers. */
1033     if (modified == NULL /* && need_normal */) {
1034       if (vertCos != NULL) {
1035         displist_vert_coords_apply(dispbase, vertCos);
1036       }
1037 
1038       if (ELEM(ob->type, OB_CURVE, OB_FONT) && (cu->flag & CU_DEFORM_FILL)) {
1039         curve_to_filledpoly(cu, nurb, dispbase);
1040       }
1041 
1042       modified = BKE_mesh_new_nomain_from_curve_displist(ob, dispbase);
1043     }
1044 
1045     if (mti->type == eModifierTypeType_OnlyDeform ||
1046         (mti->type == eModifierTypeType_DeformOrConstruct && !modified)) {
1047       if (modified) {
1048         if (!vertCos) {
1049           vertCos = BKE_mesh_vert_coords_alloc(modified, &totvert);
1050         }
1051         if (need_normal) {
1052           BKE_mesh_ensure_normals(modified);
1053         }
1054         mti->deformVerts(md, &mectx_deform, modified, vertCos, totvert);
1055       }
1056       else {
1057         if (!vertCos) {
1058           vertCos = displist_vert_coords_alloc(dispbase, &totvert);
1059         }
1060         mti->deformVerts(md, &mectx_deform, NULL, vertCos, totvert);
1061       }
1062     }
1063     else {
1064       if (!r_final) {
1065         /* makeDisplistCurveTypes could be used for beveling, where derived mesh
1066          * is totally unnecessary, so we could stop modifiers applying
1067          * when we found constructive modifier but derived mesh is unwanted result
1068          */
1069         break;
1070       }
1071 
1072       if (modified) {
1073         if (vertCos) {
1074           Mesh *temp_mesh = (Mesh *)BKE_id_copy_ex(
1075               NULL, &modified->id, NULL, LIB_ID_COPY_LOCALIZE);
1076           BKE_id_free(NULL, modified);
1077           modified = temp_mesh;
1078 
1079           BKE_mesh_vert_coords_apply(modified, vertCos);
1080         }
1081       }
1082       else {
1083         if (vertCos) {
1084           displist_vert_coords_apply(dispbase, vertCos);
1085         }
1086 
1087         if (ELEM(ob->type, OB_CURVE, OB_FONT) && (cu->flag & CU_DEFORM_FILL)) {
1088           curve_to_filledpoly(cu, nurb, dispbase);
1089         }
1090 
1091         modified = BKE_mesh_new_nomain_from_curve_displist(ob, dispbase);
1092       }
1093 
1094       if (vertCos) {
1095         /* Vertex coordinates were applied to necessary data, could free it */
1096         MEM_freeN(vertCos);
1097         vertCos = NULL;
1098       }
1099 
1100       if (need_normal) {
1101         BKE_mesh_ensure_normals(modified);
1102       }
1103       mesh_applied = mti->modifyMesh(md, &mectx_apply, modified);
1104 
1105       if (mesh_applied) {
1106         /* Modifier returned a new derived mesh */
1107 
1108         if (modified && modified != mesh_applied) { /* Modifier  */
1109           BKE_id_free(NULL, modified);
1110         }
1111         modified = mesh_applied;
1112       }
1113     }
1114   }
1115 
1116   if (vertCos) {
1117     if (modified) {
1118       Mesh *temp_mesh = (Mesh *)BKE_id_copy_ex(NULL, &modified->id, NULL, LIB_ID_COPY_LOCALIZE);
1119       BKE_id_free(NULL, modified);
1120       modified = temp_mesh;
1121 
1122       BKE_mesh_vert_coords_apply(modified, vertCos);
1123       BKE_mesh_calc_normals_mapping_simple(modified);
1124 
1125       MEM_freeN(vertCos);
1126     }
1127     else {
1128       displist_vert_coords_apply(dispbase, vertCos);
1129       MEM_freeN(vertCos);
1130       vertCos = NULL;
1131     }
1132   }
1133 
1134   if (r_final) {
1135     if (force_mesh_conversion && !modified) {
1136       /* XXX 2.8 : This is a workaround for by some deeper technical debts:
1137        * - DRW Batch cache is stored inside the ob->data.
1138        * - Curve data is not COWed for instances that use different modifiers.
1139        * This can causes the modifiers to be applied on all user of the same data-block
1140        * (see T71055)
1141        *
1142        * The easy workaround is to force to generate a Mesh that will be used for display data
1143        * since a Mesh output is already used for generative modifiers.
1144        * However it does not fix problems with actual edit data still being shared.
1145        *
1146        * The right solution would be to COW the Curve data block at the input of the modifier
1147        * stack just like what the mesh modifier does.
1148        * */
1149       modified = BKE_mesh_new_nomain_from_curve_displist(ob, dispbase);
1150     }
1151 
1152     if (modified) {
1153 
1154       /* XXX2.8(Sybren): make sure the face normals are recalculated as well */
1155       BKE_mesh_ensure_normals(modified);
1156 
1157       /* Special tweaks, needed since neither BKE_mesh_new_nomain_from_template() nor
1158        * BKE_mesh_new_nomain_from_curve_displist() properly duplicate mat info...
1159        */
1160       BLI_strncpy(modified->id.name, cu->id.name, sizeof(modified->id.name));
1161       *((short *)modified->id.name) = ID_ME;
1162       MEM_SAFE_FREE(modified->mat);
1163       /* Set flag which makes it easier to see what's going on in a debugger. */
1164       modified->id.tag |= LIB_TAG_COPIED_ON_WRITE_EVAL_RESULT;
1165       modified->mat = MEM_dupallocN(cu->mat);
1166       modified->totcol = cu->totcol;
1167 
1168       (*r_final) = modified;
1169     }
1170     else {
1171       (*r_final) = NULL;
1172     }
1173   }
1174   else if (modified != NULL) {
1175     /* Pretty stupid to generate that whole mesh if it's unused, yet we have to free it. */
1176     BKE_id_free(NULL, modified);
1177   }
1178 }
1179 
displist_surf_indices(DispList * dl)1180 static void displist_surf_indices(DispList *dl)
1181 {
1182   int a, b, p1, p2, p3, p4;
1183   int *index;
1184 
1185   dl->totindex = 0;
1186 
1187   index = dl->index = MEM_mallocN(sizeof(int[4]) * (dl->parts + 1) * (dl->nr + 1),
1188                                   "index array nurbs");
1189 
1190   for (a = 0; a < dl->parts; a++) {
1191 
1192     if (BKE_displist_surfindex_get(dl, a, &b, &p1, &p2, &p3, &p4) == 0) {
1193       break;
1194     }
1195 
1196     for (; b < dl->nr; b++, index += 4) {
1197       index[0] = p1;
1198       index[1] = p2;
1199       index[2] = p4;
1200       index[3] = p3;
1201 
1202       dl->totindex++;
1203 
1204       p2 = p1;
1205       p1++;
1206       p4 = p3;
1207       p3++;
1208     }
1209   }
1210 }
1211 
BKE_displist_make_surf(Depsgraph * depsgraph,Scene * scene,Object * ob,ListBase * dispbase,Mesh ** r_final,const bool for_render,const bool for_orco)1212 void BKE_displist_make_surf(Depsgraph *depsgraph,
1213                             Scene *scene,
1214                             Object *ob,
1215                             ListBase *dispbase,
1216                             Mesh **r_final,
1217                             const bool for_render,
1218                             const bool for_orco)
1219 {
1220   ListBase nubase = {NULL, NULL};
1221   Nurb *nu;
1222   Curve *cu = ob->data;
1223   DispList *dl;
1224   float *data;
1225   int len;
1226   bool force_mesh_conversion = false;
1227 
1228   if (!for_render && cu->editnurb) {
1229     BKE_nurbList_duplicate(&nubase, BKE_curve_editNurbs_get(cu));
1230   }
1231   else {
1232     BKE_nurbList_duplicate(&nubase, &cu->nurb);
1233   }
1234 
1235   if (!for_orco) {
1236     force_mesh_conversion = curve_calc_modifiers_pre(depsgraph, scene, ob, &nubase, for_render);
1237   }
1238 
1239   for (nu = nubase.first; nu; nu = nu->next) {
1240     if ((for_render || nu->hide == 0) && BKE_nurb_check_valid_uv(nu)) {
1241       int resolu = nu->resolu, resolv = nu->resolv;
1242 
1243       if (for_render) {
1244         if (cu->resolu_ren) {
1245           resolu = cu->resolu_ren;
1246         }
1247         if (cu->resolv_ren) {
1248           resolv = cu->resolv_ren;
1249         }
1250       }
1251 
1252       if (nu->pntsv == 1) {
1253         len = SEGMENTSU(nu) * resolu;
1254 
1255         dl = MEM_callocN(sizeof(DispList), "makeDispListsurf");
1256         dl->verts = MEM_mallocN(len * sizeof(float[3]), "dlverts");
1257 
1258         BLI_addtail(dispbase, dl);
1259         dl->parts = 1;
1260         dl->nr = len;
1261         dl->col = nu->mat_nr;
1262         dl->charidx = nu->charidx;
1263 
1264         /* dl->rt will be used as flag for render face and */
1265         /* CU_2D conflicts with R_NOPUNOFLIP */
1266         dl->rt = nu->flag & ~CU_2D;
1267 
1268         data = dl->verts;
1269         if (nu->flagu & CU_NURB_CYCLIC) {
1270           dl->type = DL_POLY;
1271         }
1272         else {
1273           dl->type = DL_SEGM;
1274         }
1275 
1276         BKE_nurb_makeCurve(nu, data, NULL, NULL, NULL, resolu, sizeof(float[3]));
1277       }
1278       else {
1279         len = (nu->pntsu * resolu) * (nu->pntsv * resolv);
1280 
1281         dl = MEM_callocN(sizeof(DispList), "makeDispListsurf");
1282         dl->verts = MEM_mallocN(len * sizeof(float[3]), "dlverts");
1283         BLI_addtail(dispbase, dl);
1284 
1285         dl->col = nu->mat_nr;
1286         dl->charidx = nu->charidx;
1287 
1288         /* dl->rt will be used as flag for render face and */
1289         /* CU_2D conflicts with R_NOPUNOFLIP */
1290         dl->rt = nu->flag & ~CU_2D;
1291 
1292         data = dl->verts;
1293         dl->type = DL_SURF;
1294 
1295         dl->parts = (nu->pntsu * resolu); /* in reverse, because makeNurbfaces works that way */
1296         dl->nr = (nu->pntsv * resolv);
1297         if (nu->flagv & CU_NURB_CYCLIC) {
1298           dl->flag |= DL_CYCL_U; /* reverse too! */
1299         }
1300         if (nu->flagu & CU_NURB_CYCLIC) {
1301           dl->flag |= DL_CYCL_V;
1302         }
1303 
1304         BKE_nurb_makeFaces(nu, data, 0, resolu, resolv);
1305 
1306         /* gl array drawing: using indices */
1307         displist_surf_indices(dl);
1308       }
1309     }
1310   }
1311 
1312   if (!for_orco) {
1313     BKE_nurbList_duplicate(&ob->runtime.curve_cache->deformed_nurbs, &nubase);
1314     curve_calc_modifiers_post(
1315         depsgraph, scene, ob, &nubase, dispbase, r_final, for_render, force_mesh_conversion);
1316   }
1317 
1318   BKE_nurbList_free(&nubase);
1319 }
1320 
rotateBevelPiece(Curve * cu,BevPoint * bevp,BevPoint * nbevp,DispList * dlb,float bev_blend,float widfac,float fac,float ** r_data)1321 static void rotateBevelPiece(Curve *cu,
1322                              BevPoint *bevp,
1323                              BevPoint *nbevp,
1324                              DispList *dlb,
1325                              float bev_blend,
1326                              float widfac,
1327                              float fac,
1328                              float **r_data)
1329 {
1330   float *fp, *data = *r_data;
1331   int b;
1332 
1333   fp = dlb->verts;
1334   for (b = 0; b < dlb->nr; b++, fp += 3, data += 3) {
1335     if (cu->flag & CU_3D) {
1336       float vec[3], quat[4];
1337 
1338       vec[0] = fp[1] + widfac;
1339       vec[1] = fp[2];
1340       vec[2] = 0.0;
1341 
1342       if (nbevp == NULL) {
1343         copy_v3_v3(data, bevp->vec);
1344         copy_qt_qt(quat, bevp->quat);
1345       }
1346       else {
1347         interp_v3_v3v3(data, bevp->vec, nbevp->vec, bev_blend);
1348         interp_qt_qtqt(quat, bevp->quat, nbevp->quat, bev_blend);
1349       }
1350 
1351       mul_qt_v3(quat, vec);
1352 
1353       data[0] += fac * vec[0];
1354       data[1] += fac * vec[1];
1355       data[2] += fac * vec[2];
1356     }
1357     else {
1358       float sina, cosa;
1359 
1360       if (nbevp == NULL) {
1361         copy_v3_v3(data, bevp->vec);
1362         sina = bevp->sina;
1363         cosa = bevp->cosa;
1364       }
1365       else {
1366         interp_v3_v3v3(data, bevp->vec, nbevp->vec, bev_blend);
1367 
1368         /* perhaps we need to interpolate angles instead. but the thing is
1369          * cosa and sina are not actually sine and cosine
1370          */
1371         sina = nbevp->sina * bev_blend + bevp->sina * (1.0f - bev_blend);
1372         cosa = nbevp->cosa * bev_blend + bevp->cosa * (1.0f - bev_blend);
1373       }
1374 
1375       data[0] += fac * (widfac + fp[1]) * sina;
1376       data[1] += fac * (widfac + fp[1]) * cosa;
1377       data[2] += fac * fp[2];
1378     }
1379   }
1380 
1381   *r_data = data;
1382 }
1383 
fillBevelCap(Nurb * nu,DispList * dlb,float * prev_fp,ListBase * dispbase)1384 static void fillBevelCap(Nurb *nu, DispList *dlb, float *prev_fp, ListBase *dispbase)
1385 {
1386   DispList *dl;
1387 
1388   dl = MEM_callocN(sizeof(DispList), "makeDispListbev2");
1389   dl->verts = MEM_mallocN(sizeof(float[3]) * dlb->nr, "dlverts");
1390   memcpy(dl->verts, prev_fp, sizeof(float[3]) * dlb->nr);
1391 
1392   dl->type = DL_POLY;
1393 
1394   dl->parts = 1;
1395   dl->nr = dlb->nr;
1396   dl->col = nu->mat_nr;
1397   dl->charidx = nu->charidx;
1398 
1399   /* dl->rt will be used as flag for render face and */
1400   /* CU_2D conflicts with R_NOPUNOFLIP */
1401   dl->rt = nu->flag & ~CU_2D;
1402 
1403   BLI_addtail(dispbase, dl);
1404 }
1405 
calc_bevfac_segment_mapping(BevList * bl,float bevfac,float spline_length,int * r_bev,float * r_blend)1406 static void calc_bevfac_segment_mapping(
1407     BevList *bl, float bevfac, float spline_length, int *r_bev, float *r_blend)
1408 {
1409   float normlen, normsum = 0.0f;
1410   float *seglen = bl->seglen;
1411   int *segbevcount = bl->segbevcount;
1412   int bevcount = 0, nr = bl->nr;
1413 
1414   float bev_fl = bevfac * (bl->nr - 1);
1415   *r_bev = (int)bev_fl;
1416 
1417   while (bevcount < nr - 1) {
1418     normlen = *seglen / spline_length;
1419     if (normsum + normlen > bevfac) {
1420       bev_fl = bevcount + (bevfac - normsum) / normlen * *segbevcount;
1421       *r_bev = (int)bev_fl;
1422       *r_blend = bev_fl - *r_bev;
1423       break;
1424     }
1425     normsum += normlen;
1426     bevcount += *segbevcount;
1427     segbevcount++;
1428     seglen++;
1429   }
1430 }
1431 
calc_bevfac_spline_mapping(BevList * bl,float bevfac,float spline_length,int * r_bev,float * r_blend)1432 static void calc_bevfac_spline_mapping(
1433     BevList *bl, float bevfac, float spline_length, int *r_bev, float *r_blend)
1434 {
1435   const float len_target = bevfac * spline_length;
1436   BevPoint *bevp = bl->bevpoints;
1437   float len_next = 0.0f, len = 0.0f;
1438   int i = 0, nr = bl->nr;
1439 
1440   while (nr--) {
1441     bevp++;
1442     len_next = len + bevp->offset;
1443     if (len_next > len_target) {
1444       break;
1445     }
1446     len = len_next;
1447     i++;
1448   }
1449 
1450   *r_bev = i;
1451   *r_blend = (len_target - len) / bevp->offset;
1452 }
1453 
calc_bevfac_mapping_default(BevList * bl,int * r_start,float * r_firstblend,int * r_steps,float * r_lastblend)1454 static void calc_bevfac_mapping_default(
1455     BevList *bl, int *r_start, float *r_firstblend, int *r_steps, float *r_lastblend)
1456 {
1457   *r_start = 0;
1458   *r_steps = bl->nr;
1459   *r_firstblend = 1.0f;
1460   *r_lastblend = 1.0f;
1461 }
1462 
calc_bevfac_mapping(Curve * cu,BevList * bl,Nurb * nu,int * r_start,float * r_firstblend,int * r_steps,float * r_lastblend)1463 static void calc_bevfac_mapping(Curve *cu,
1464                                 BevList *bl,
1465                                 Nurb *nu,
1466                                 int *r_start,
1467                                 float *r_firstblend,
1468                                 int *r_steps,
1469                                 float *r_lastblend)
1470 {
1471   float tmpf, total_length = 0.0f;
1472   int end = 0, i;
1473 
1474   if ((BKE_nurb_check_valid_u(nu) == false) ||
1475       /* not essential, but skips unnecessary calculation */
1476       (min_ff(cu->bevfac1, cu->bevfac2) == 0.0f && max_ff(cu->bevfac1, cu->bevfac2) == 1.0f)) {
1477     calc_bevfac_mapping_default(bl, r_start, r_firstblend, r_steps, r_lastblend);
1478     return;
1479   }
1480 
1481   if (ELEM(cu->bevfac1_mapping, CU_BEVFAC_MAP_SEGMENT, CU_BEVFAC_MAP_SPLINE) ||
1482       ELEM(cu->bevfac2_mapping, CU_BEVFAC_MAP_SEGMENT, CU_BEVFAC_MAP_SPLINE)) {
1483     for (i = 0; i < SEGMENTSU(nu); i++) {
1484       total_length += bl->seglen[i];
1485     }
1486   }
1487 
1488   switch (cu->bevfac1_mapping) {
1489     case CU_BEVFAC_MAP_RESOLU: {
1490       const float start_fl = cu->bevfac1 * (bl->nr - 1);
1491       *r_start = (int)start_fl;
1492       *r_firstblend = 1.0f - (start_fl - (*r_start));
1493       break;
1494     }
1495     case CU_BEVFAC_MAP_SEGMENT: {
1496       calc_bevfac_segment_mapping(bl, cu->bevfac1, total_length, r_start, r_firstblend);
1497       *r_firstblend = 1.0f - *r_firstblend;
1498       break;
1499     }
1500     case CU_BEVFAC_MAP_SPLINE: {
1501       calc_bevfac_spline_mapping(bl, cu->bevfac1, total_length, r_start, r_firstblend);
1502       *r_firstblend = 1.0f - *r_firstblend;
1503       break;
1504     }
1505   }
1506 
1507   switch (cu->bevfac2_mapping) {
1508     case CU_BEVFAC_MAP_RESOLU: {
1509       const float end_fl = cu->bevfac2 * (bl->nr - 1);
1510       end = (int)end_fl;
1511 
1512       *r_steps = 2 + end - *r_start;
1513       *r_lastblend = end_fl - end;
1514       break;
1515     }
1516     case CU_BEVFAC_MAP_SEGMENT: {
1517       calc_bevfac_segment_mapping(bl, cu->bevfac2, total_length, &end, r_lastblend);
1518       *r_steps = end - *r_start + 2;
1519       break;
1520     }
1521     case CU_BEVFAC_MAP_SPLINE: {
1522       calc_bevfac_spline_mapping(bl, cu->bevfac2, total_length, &end, r_lastblend);
1523       *r_steps = end - *r_start + 2;
1524       break;
1525     }
1526   }
1527 
1528   if (end < *r_start || (end == *r_start && *r_lastblend < 1.0f - *r_firstblend)) {
1529     SWAP(int, *r_start, end);
1530     tmpf = *r_lastblend;
1531     *r_lastblend = 1.0f - *r_firstblend;
1532     *r_firstblend = 1.0f - tmpf;
1533     *r_steps = end - *r_start + 2;
1534   }
1535 
1536   if (*r_start + *r_steps > bl->nr) {
1537     *r_steps = bl->nr - *r_start;
1538     *r_lastblend = 1.0f;
1539   }
1540 }
1541 
do_makeDispListCurveTypes(Depsgraph * depsgraph,Scene * scene,Object * ob,ListBase * dispbase,const bool for_render,const bool for_orco,Mesh ** r_final)1542 static void do_makeDispListCurveTypes(Depsgraph *depsgraph,
1543                                       Scene *scene,
1544                                       Object *ob,
1545                                       ListBase *dispbase,
1546                                       const bool for_render,
1547                                       const bool for_orco,
1548                                       Mesh **r_final)
1549 {
1550   Curve *cu = ob->data;
1551 
1552   /* we do allow duplis... this is only displist on curve level */
1553   if (!ELEM(ob->type, OB_SURF, OB_CURVE, OB_FONT)) {
1554     return;
1555   }
1556 
1557   if (ob->type == OB_SURF) {
1558     BKE_displist_make_surf(depsgraph, scene, ob, dispbase, r_final, for_render, for_orco);
1559   }
1560   else if (ELEM(ob->type, OB_CURVE, OB_FONT)) {
1561     ListBase dlbev;
1562     ListBase nubase = {NULL, NULL};
1563     bool force_mesh_conversion = false;
1564 
1565     BKE_curve_bevelList_free(&ob->runtime.curve_cache->bev);
1566 
1567     /* We only re-evaluate path if evaluation is not happening for orco.
1568      * If the calculation happens for orco, we should never free data which
1569      * was needed before and only not needed for orco calculation.
1570      */
1571     if (!for_orco) {
1572       if (ob->runtime.curve_cache->path) {
1573         free_path(ob->runtime.curve_cache->path);
1574       }
1575       ob->runtime.curve_cache->path = NULL;
1576     }
1577 
1578     if (ob->type == OB_FONT) {
1579       BKE_vfont_to_curve_nubase(ob, FO_EDIT, &nubase);
1580     }
1581     else {
1582       BKE_nurbList_duplicate(&nubase, BKE_curve_nurbs_get(cu));
1583     }
1584 
1585     if (!for_orco) {
1586       force_mesh_conversion = curve_calc_modifiers_pre(depsgraph, scene, ob, &nubase, for_render);
1587     }
1588 
1589     BKE_curve_bevelList_make(ob, &nubase, for_render);
1590 
1591     /* If curve has no bevel will return nothing */
1592     BKE_curve_bevel_make(ob, &dlbev);
1593 
1594     /* no bevel or extrude, and no width correction? */
1595     if (!dlbev.first && cu->width == 1.0f) {
1596       curve_to_displist(cu, &nubase, dispbase, for_render);
1597     }
1598     else {
1599       float widfac = cu->width - 1.0f;
1600       BevList *bl = ob->runtime.curve_cache->bev.first;
1601       Nurb *nu = nubase.first;
1602 
1603       for (; bl && nu; bl = bl->next, nu = nu->next) {
1604         DispList *dl;
1605         float *data;
1606         int a;
1607 
1608         if (bl->nr) { /* blank bevel lists can happen */
1609 
1610           /* exception handling; curve without bevel or extrude, with width correction */
1611           if (BLI_listbase_is_empty(&dlbev)) {
1612             BevPoint *bevp;
1613             dl = MEM_callocN(sizeof(DispList), "makeDispListbev");
1614             dl->verts = MEM_mallocN(sizeof(float[3]) * bl->nr, "dlverts");
1615             BLI_addtail(dispbase, dl);
1616 
1617             if (bl->poly != -1) {
1618               dl->type = DL_POLY;
1619             }
1620             else {
1621               dl->type = DL_SEGM;
1622             }
1623 
1624             if (dl->type == DL_SEGM) {
1625               dl->flag = (DL_FRONT_CURVE | DL_BACK_CURVE);
1626             }
1627 
1628             dl->parts = 1;
1629             dl->nr = bl->nr;
1630             dl->col = nu->mat_nr;
1631             dl->charidx = nu->charidx;
1632 
1633             /* dl->rt will be used as flag for render face and */
1634             /* CU_2D conflicts with R_NOPUNOFLIP */
1635             dl->rt = nu->flag & ~CU_2D;
1636 
1637             a = dl->nr;
1638             bevp = bl->bevpoints;
1639             data = dl->verts;
1640             while (a--) {
1641               data[0] = bevp->vec[0] + widfac * bevp->sina;
1642               data[1] = bevp->vec[1] + widfac * bevp->cosa;
1643               data[2] = bevp->vec[2];
1644               bevp++;
1645               data += 3;
1646             }
1647           }
1648           else {
1649             DispList *dlb;
1650             ListBase bottom_capbase = {NULL, NULL};
1651             ListBase top_capbase = {NULL, NULL};
1652             float bottom_no[3] = {0.0f};
1653             float top_no[3] = {0.0f};
1654             float firstblend = 0.0f, lastblend = 0.0f;
1655             int i, start, steps = 0;
1656 
1657             if (nu->flagu & CU_NURB_CYCLIC) {
1658               calc_bevfac_mapping_default(bl, &start, &firstblend, &steps, &lastblend);
1659             }
1660             else {
1661               if (fabsf(cu->bevfac2 - cu->bevfac1) < FLT_EPSILON) {
1662                 continue;
1663               }
1664 
1665               calc_bevfac_mapping(cu, bl, nu, &start, &firstblend, &steps, &lastblend);
1666             }
1667 
1668             for (dlb = dlbev.first; dlb; dlb = dlb->next) {
1669               BevPoint *bevp_first, *bevp_last;
1670               BevPoint *bevp;
1671 
1672               /* for each part of the bevel use a separate displblock */
1673               dl = MEM_callocN(sizeof(DispList), "makeDispListbev1");
1674               dl->verts = data = MEM_mallocN(sizeof(float[3]) * dlb->nr * steps, "dlverts");
1675               BLI_addtail(dispbase, dl);
1676 
1677               dl->type = DL_SURF;
1678 
1679               dl->flag = dlb->flag & (DL_FRONT_CURVE | DL_BACK_CURVE);
1680               if (dlb->type == DL_POLY) {
1681                 dl->flag |= DL_CYCL_U;
1682               }
1683               if ((bl->poly >= 0) && (steps > 2)) {
1684                 dl->flag |= DL_CYCL_V;
1685               }
1686 
1687               dl->parts = steps;
1688               dl->nr = dlb->nr;
1689               dl->col = nu->mat_nr;
1690               dl->charidx = nu->charidx;
1691 
1692               /* dl->rt will be used as flag for render face and */
1693               /* CU_2D conflicts with R_NOPUNOFLIP */
1694               dl->rt = nu->flag & ~CU_2D;
1695 
1696               dl->bevel_split = BLI_BITMAP_NEW(steps, "bevel_split");
1697 
1698               /* for each point of poly make a bevel piece */
1699               bevp_first = bl->bevpoints;
1700               bevp_last = &bl->bevpoints[bl->nr - 1];
1701               bevp = &bl->bevpoints[start];
1702               for (i = start, a = 0; a < steps; i++, bevp++, a++) {
1703                 float fac = 1.0;
1704                 float *cur_data = data;
1705 
1706                 if (cu->taperobj == NULL) {
1707                   fac = bevp->radius;
1708                 }
1709                 else {
1710                   float len, taper_fac;
1711 
1712                   if (cu->flag & CU_MAP_TAPER) {
1713                     len = (steps - 3) + firstblend + lastblend;
1714 
1715                     if (a == 0) {
1716                       taper_fac = 0.0f;
1717                     }
1718                     else if (a == steps - 1) {
1719                       taper_fac = 1.0f;
1720                     }
1721                     else {
1722                       taper_fac = ((float)a - (1.0f - firstblend)) / len;
1723                     }
1724                   }
1725                   else {
1726                     len = bl->nr - 1;
1727                     taper_fac = (float)i / len;
1728 
1729                     if (a == 0) {
1730                       taper_fac += (1.0f - firstblend) / len;
1731                     }
1732                     else if (a == steps - 1) {
1733                       taper_fac -= (1.0f - lastblend) / len;
1734                     }
1735                   }
1736 
1737                   fac = displist_calc_taper(depsgraph, scene, cu->taperobj, taper_fac);
1738                 }
1739 
1740                 if (bevp->split_tag) {
1741                   BLI_BITMAP_ENABLE(dl->bevel_split, a);
1742                 }
1743 
1744                 /* rotate bevel piece and write in data */
1745                 if ((a == 0) && (bevp != bevp_last)) {
1746                   rotateBevelPiece(cu, bevp, bevp + 1, dlb, 1.0f - firstblend, widfac, fac, &data);
1747                 }
1748                 else if ((a == steps - 1) && (bevp != bevp_first)) {
1749                   rotateBevelPiece(cu, bevp, bevp - 1, dlb, 1.0f - lastblend, widfac, fac, &data);
1750                 }
1751                 else {
1752                   rotateBevelPiece(cu, bevp, NULL, dlb, 0.0f, widfac, fac, &data);
1753                 }
1754 
1755                 if ((cu->flag & CU_FILL_CAPS) && !(nu->flagu & CU_NURB_CYCLIC)) {
1756                   if (a == 1) {
1757                     fillBevelCap(nu, dlb, cur_data - 3 * dlb->nr, &bottom_capbase);
1758                     copy_v3_v3(bottom_no, bevp->dir);
1759                   }
1760                   if (a == steps - 1) {
1761                     fillBevelCap(nu, dlb, cur_data, &top_capbase);
1762                     negate_v3_v3(top_no, bevp->dir);
1763                   }
1764                 }
1765               }
1766 
1767               /* gl array drawing: using indices */
1768               displist_surf_indices(dl);
1769             }
1770 
1771             if (bottom_capbase.first) {
1772               BKE_displist_fill(&bottom_capbase, dispbase, bottom_no, false);
1773               BKE_displist_fill(&top_capbase, dispbase, top_no, false);
1774               BKE_displist_free(&bottom_capbase);
1775               BKE_displist_free(&top_capbase);
1776             }
1777           }
1778         }
1779       }
1780       BKE_displist_free(&dlbev);
1781     }
1782 
1783     if (!(cu->flag & CU_DEFORM_FILL)) {
1784       curve_to_filledpoly(cu, &nubase, dispbase);
1785     }
1786 
1787     if (!for_orco) {
1788       if ((cu->flag & CU_PATH) ||
1789           DEG_get_eval_flags_for_id(depsgraph, &ob->id) & DAG_EVAL_NEED_CURVE_PATH) {
1790         calc_curvepath(ob, &nubase);
1791       }
1792     }
1793 
1794     if (!for_orco) {
1795       BKE_nurbList_duplicate(&ob->runtime.curve_cache->deformed_nurbs, &nubase);
1796       curve_calc_modifiers_post(
1797           depsgraph, scene, ob, &nubase, dispbase, r_final, for_render, force_mesh_conversion);
1798     }
1799 
1800     if (cu->flag & CU_DEFORM_FILL && !ob->runtime.data_eval) {
1801       curve_to_filledpoly(cu, &nubase, dispbase);
1802     }
1803 
1804     BKE_nurbList_free(&nubase);
1805   }
1806 }
1807 
BKE_displist_make_curveTypes(Depsgraph * depsgraph,Scene * scene,Object * ob,const bool for_render,const bool for_orco)1808 void BKE_displist_make_curveTypes(
1809     Depsgraph *depsgraph, Scene *scene, Object *ob, const bool for_render, const bool for_orco)
1810 {
1811   ListBase *dispbase;
1812 
1813   /* The same check for duplis as in do_makeDispListCurveTypes.
1814    * Happens when curve used for constraint/bevel was converted to mesh.
1815    * check there is still needed for render displist and orco displists. */
1816   if (!ELEM(ob->type, OB_SURF, OB_CURVE, OB_FONT)) {
1817     return;
1818   }
1819 
1820   BKE_object_free_derived_caches(ob);
1821 
1822   if (!ob->runtime.curve_cache) {
1823     ob->runtime.curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for curve types");
1824   }
1825 
1826   dispbase = &(ob->runtime.curve_cache->disp);
1827 
1828   Mesh *mesh_eval = NULL;
1829   do_makeDispListCurveTypes(depsgraph, scene, ob, dispbase, for_render, for_orco, &mesh_eval);
1830 
1831   if (mesh_eval != NULL) {
1832     BKE_object_eval_assign_data(ob, &mesh_eval->id, true);
1833   }
1834 
1835   boundbox_displist_object(ob);
1836 }
1837 
BKE_displist_make_curveTypes_forRender(Depsgraph * depsgraph,Scene * scene,Object * ob,ListBase * dispbase,Mesh ** r_final,const bool for_orco)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 {
1845   if (ob->runtime.curve_cache == NULL) {
1846     ob->runtime.curve_cache = MEM_callocN(sizeof(CurveCache), "CurveCache for Curve");
1847   }
1848 
1849   do_makeDispListCurveTypes(depsgraph, scene, ob, dispbase, true, for_orco, r_final);
1850 }
1851 
BKE_displist_minmax(ListBase * dispbase,float min[3],float max[3])1852 void BKE_displist_minmax(ListBase *dispbase, float min[3], float max[3])
1853 {
1854   DispList *dl;
1855   const float *vert;
1856   int a, tot = 0;
1857   int doit = 0;
1858 
1859   for (dl = dispbase->first; dl; dl = dl->next) {
1860     tot = (dl->type == DL_INDEX3) ? dl->nr : dl->nr * dl->parts;
1861     vert = dl->verts;
1862     for (a = 0; a < tot; a++, vert += 3) {
1863       minmax_v3v3_v3(min, max, vert);
1864     }
1865     doit |= (tot != 0);
1866   }
1867 
1868   if (!doit) {
1869     /* there's no geometry in displist, use zero-sized boundbox */
1870     zero_v3(min);
1871     zero_v3(max);
1872   }
1873 }
1874 
1875 /* this is confusing, there's also min_max_object, applying the obmat... */
boundbox_displist_object(Object * ob)1876 static void boundbox_displist_object(Object *ob)
1877 {
1878   if (ELEM(ob->type, OB_CURVE, OB_SURF, OB_FONT)) {
1879     /* Curve's BB is already calculated as a part of modifier stack,
1880      * here we only calculate object BB based on final display list.
1881      */
1882 
1883     /* object's BB is calculated from final displist */
1884     if (ob->runtime.bb == NULL) {
1885       ob->runtime.bb = MEM_callocN(sizeof(BoundBox), "boundbox");
1886     }
1887 
1888     Mesh *mesh_eval = BKE_object_get_evaluated_mesh(ob);
1889     if (mesh_eval) {
1890       BKE_object_boundbox_calc_from_mesh(ob, mesh_eval);
1891     }
1892     else {
1893       float min[3], max[3];
1894 
1895       INIT_MINMAX(min, max);
1896       BKE_displist_minmax(&ob->runtime.curve_cache->disp, min, max);
1897       BKE_boundbox_init_from_minmax(ob->runtime.bb, min, max);
1898 
1899       ob->runtime.bb->flag &= ~BOUNDBOX_DIRTY;
1900     }
1901   }
1902 }
1903