GPencil: Split Curve geometry functions to new file
[blender.git] / source / blender / blenkernel / intern / gpencil_geom.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) 2008, Blender Foundation
17  * This is a new part of Blender
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include <math.h>
25 #include <stddef.h>
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "CLG_log.h"
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_blenlib.h"
35 #include "BLI_math_vector.h"
36 #include "BLI_polyfill_2d.h"
37
38 #include "DNA_gpencil_types.h"
39 #include "DNA_meshdata_types.h"
40
41 #include "BKE_deform.h"
42 #include "BKE_gpencil.h"
43 #include "BKE_gpencil_geom.h"
44 #include "BKE_object.h"
45
46 #include "DEG_depsgraph_query.h"
47
48 /* GP Object - Boundbox Support */
49 /**
50  * Get min/max coordinate bounds for single stroke
51  * \return Returns whether we found any selected points
52  */
53 bool BKE_gpencil_stroke_minmax(const bGPDstroke *gps,
54                                const bool use_select,
55                                float r_min[3],
56                                float r_max[3])
57 {
58   const bGPDspoint *pt;
59   int i;
60   bool changed = false;
61
62   if (ELEM(NULL, gps, r_min, r_max)) {
63     return false;
64   }
65
66   for (i = 0, pt = gps->points; i < gps->totpoints; i++, pt++) {
67     if ((use_select == false) || (pt->flag & GP_SPOINT_SELECT)) {
68       minmax_v3v3_v3(r_min, r_max, &pt->x);
69       changed = true;
70     }
71   }
72   return changed;
73 }
74
75 /* get min/max bounds of all strokes in GP datablock */
76 bool BKE_gpencil_data_minmax(const bGPdata *gpd, float r_min[3], float r_max[3])
77 {
78   bool changed = false;
79
80   INIT_MINMAX(r_min, r_max);
81
82   if (gpd == NULL) {
83     return changed;
84   }
85
86   LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
87     bGPDframe *gpf = gpl->actframe;
88
89     if (gpf != NULL) {
90       LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
91         changed = BKE_gpencil_stroke_minmax(gps, false, r_min, r_max);
92       }
93     }
94   }
95
96   return changed;
97 }
98
99 /* compute center of bounding box */
100 void BKE_gpencil_centroid_3d(bGPdata *gpd, float r_centroid[3])
101 {
102   float min[3], max[3], tot[3];
103
104   BKE_gpencil_data_minmax(gpd, min, max);
105
106   add_v3_v3v3(tot, min, max);
107   mul_v3_v3fl(r_centroid, tot, 0.5f);
108 }
109
110 /* Compute stroke bounding box. */
111 void BKE_gpencil_stroke_boundingbox_calc(bGPDstroke *gps)
112 {
113   INIT_MINMAX(gps->boundbox_min, gps->boundbox_max);
114   BKE_gpencil_stroke_minmax(gps, false, gps->boundbox_min, gps->boundbox_max);
115 }
116
117 /* create bounding box values */
118 static void boundbox_gpencil(Object *ob)
119 {
120   BoundBox *bb;
121   bGPdata *gpd;
122   float min[3], max[3];
123
124   if (ob->runtime.bb == NULL) {
125     ob->runtime.bb = MEM_callocN(sizeof(BoundBox), "GPencil boundbox");
126   }
127
128   bb = ob->runtime.bb;
129   gpd = ob->data;
130
131   if (!BKE_gpencil_data_minmax(gpd, min, max)) {
132     min[0] = min[1] = min[2] = -1.0f;
133     max[0] = max[1] = max[2] = 1.0f;
134   }
135
136   BKE_boundbox_init_from_minmax(bb, min, max);
137
138   bb->flag &= ~BOUNDBOX_DIRTY;
139 }
140
141 /* get bounding box */
142 BoundBox *BKE_gpencil_boundbox_get(Object *ob)
143 {
144   if (ELEM(NULL, ob, ob->data)) {
145     return NULL;
146   }
147
148   bGPdata *gpd = (bGPdata *)ob->data;
149   if ((ob->runtime.bb) && ((gpd->flag & GP_DATA_CACHE_IS_DIRTY) == 0)) {
150     return ob->runtime.bb;
151   }
152
153   boundbox_gpencil(ob);
154
155   return ob->runtime.bb;
156 }
157
158 /* ************************************************** */
159
160 static int stroke_march_next_point(const bGPDstroke *gps,
161                                    const int index_next_pt,
162                                    const float *current,
163                                    const float dist,
164                                    float *result,
165                                    float *pressure,
166                                    float *strength,
167                                    float *vert_color,
168                                    float *ratio_result,
169                                    int *index_from,
170                                    int *index_to)
171 {
172   float remaining_till_next = 0.0f;
173   float remaining_march = dist;
174   float step_start[3];
175   float point[3];
176   int next_point_index = index_next_pt;
177   bGPDspoint *pt = NULL;
178
179   if (!(next_point_index < gps->totpoints)) {
180     return -1;
181   }
182
183   copy_v3_v3(step_start, current);
184   pt = &gps->points[next_point_index];
185   copy_v3_v3(point, &pt->x);
186   remaining_till_next = len_v3v3(point, step_start);
187
188   while (remaining_till_next < remaining_march) {
189     remaining_march -= remaining_till_next;
190     pt = &gps->points[next_point_index];
191     copy_v3_v3(point, &pt->x);
192     copy_v3_v3(step_start, point);
193     next_point_index++;
194     if (!(next_point_index < gps->totpoints)) {
195       next_point_index = gps->totpoints - 1;
196       break;
197     }
198     pt = &gps->points[next_point_index];
199     copy_v3_v3(point, &pt->x);
200     remaining_till_next = len_v3v3(point, step_start);
201   }
202   if (remaining_till_next < remaining_march) {
203     pt = &gps->points[next_point_index];
204     copy_v3_v3(result, &pt->x);
205     *pressure = gps->points[next_point_index].pressure;
206     *strength = gps->points[next_point_index].strength;
207     memcpy(vert_color, gps->points[next_point_index].vert_color, sizeof(float) * 4);
208
209     *index_from = next_point_index - 1;
210     *index_to = next_point_index;
211     *ratio_result = 1.0f;
212
213     return 0;
214   }
215   else {
216     float ratio = remaining_march / remaining_till_next;
217     interp_v3_v3v3(result, step_start, point, ratio);
218     *pressure = interpf(
219         gps->points[next_point_index].pressure, gps->points[next_point_index - 1].pressure, ratio);
220     *strength = interpf(
221         gps->points[next_point_index].strength, gps->points[next_point_index - 1].strength, ratio);
222     interp_v4_v4v4(vert_color,
223                    gps->points[next_point_index - 1].vert_color,
224                    gps->points[next_point_index].vert_color,
225                    ratio);
226
227     *index_from = next_point_index - 1;
228     *index_to = next_point_index;
229     *ratio_result = ratio;
230
231     return next_point_index;
232   }
233 }
234
235 static int stroke_march_next_point_no_interp(const bGPDstroke *gps,
236                                              const int index_next_pt,
237                                              const float *current,
238                                              const float dist,
239                                              float *result)
240 {
241   float remaining_till_next = 0.0f;
242   float remaining_march = dist;
243   float step_start[3];
244   float point[3];
245   int next_point_index = index_next_pt;
246   bGPDspoint *pt = NULL;
247
248   if (!(next_point_index < gps->totpoints)) {
249     return -1;
250   }
251
252   copy_v3_v3(step_start, current);
253   pt = &gps->points[next_point_index];
254   copy_v3_v3(point, &pt->x);
255   remaining_till_next = len_v3v3(point, step_start);
256
257   while (remaining_till_next < remaining_march) {
258     remaining_march -= remaining_till_next;
259     pt = &gps->points[next_point_index];
260     copy_v3_v3(point, &pt->x);
261     copy_v3_v3(step_start, point);
262     next_point_index++;
263     if (!(next_point_index < gps->totpoints)) {
264       next_point_index = gps->totpoints - 1;
265       break;
266     }
267     pt = &gps->points[next_point_index];
268     copy_v3_v3(point, &pt->x);
269     remaining_till_next = len_v3v3(point, step_start);
270   }
271   if (remaining_till_next < remaining_march) {
272     pt = &gps->points[next_point_index];
273     copy_v3_v3(result, &pt->x);
274     return 0;
275   }
276   else {
277     float ratio = remaining_march / remaining_till_next;
278     interp_v3_v3v3(result, step_start, point, ratio);
279     return next_point_index;
280   }
281 }
282
283 static int stroke_march_count(const bGPDstroke *gps, const float dist)
284 {
285   int point_count = 0;
286   float point[3];
287   int next_point_index = 1;
288   bGPDspoint *pt = NULL;
289
290   pt = &gps->points[0];
291   copy_v3_v3(point, &pt->x);
292   point_count++;
293
294   while ((next_point_index = stroke_march_next_point_no_interp(
295               gps, next_point_index, point, dist, point)) > -1) {
296     point_count++;
297     if (next_point_index == 0) {
298       break; /* last point finished */
299     }
300   }
301   return point_count;
302 }
303
304 static void stroke_defvert_create_nr_list(MDeformVert *dv_list,
305                                           int count,
306                                           ListBase *result,
307                                           int *totweight)
308 {
309   LinkData *ld;
310   MDeformVert *dv;
311   MDeformWeight *dw;
312   int i, j;
313   int tw = 0;
314   for (i = 0; i < count; i++) {
315     dv = &dv_list[i];
316
317     /* find def_nr in list, if not exist, then create one */
318     for (j = 0; j < dv->totweight; j++) {
319       bool found = false;
320       dw = &dv->dw[j];
321       for (ld = result->first; ld; ld = ld->next) {
322         if (ld->data == POINTER_FROM_INT(dw->def_nr)) {
323           found = true;
324           break;
325         }
326       }
327       if (!found) {
328         ld = MEM_callocN(sizeof(LinkData), "def_nr_item");
329         ld->data = POINTER_FROM_INT(dw->def_nr);
330         BLI_addtail(result, ld);
331         tw++;
332       }
333     }
334   }
335
336   *totweight = tw;
337 }
338
339 static MDeformVert *stroke_defvert_new_count(int count, int totweight, ListBase *def_nr_list)
340 {
341   int i, j;
342   LinkData *ld;
343   MDeformVert *dst = MEM_mallocN(count * sizeof(MDeformVert), "new_deformVert");
344
345   for (i = 0; i < count; i++) {
346     dst[i].dw = MEM_mallocN(sizeof(MDeformWeight) * totweight, "new_deformWeight");
347     dst[i].totweight = totweight;
348     j = 0;
349     /* re-assign deform groups */
350     for (ld = def_nr_list->first; ld; ld = ld->next) {
351       dst[i].dw[j].def_nr = POINTER_AS_INT(ld->data);
352       j++;
353     }
354   }
355
356   return dst;
357 }
358
359 static void stroke_interpolate_deform_weights(
360     bGPDstroke *gps, int index_from, int index_to, float ratio, MDeformVert *vert)
361 {
362   const MDeformVert *vl = &gps->dvert[index_from];
363   const MDeformVert *vr = &gps->dvert[index_to];
364   int i;
365
366   for (i = 0; i < vert->totweight; i++) {
367     float wl = BKE_defvert_find_weight(vl, vert->dw[i].def_nr);
368     float wr = BKE_defvert_find_weight(vr, vert->dw[i].def_nr);
369     vert->dw[i].weight = interpf(wr, wl, ratio);
370   }
371 }
372
373 /**
374  * Resample a stroke
375  * \param gps: Stroke to sample
376  * \param dist: Distance of one segment
377  */
378 bool BKE_gpencil_stroke_sample(bGPDstroke *gps, const float dist, const bool select)
379 {
380   bGPDspoint *pt = gps->points;
381   bGPDspoint *pt1 = NULL;
382   bGPDspoint *pt2 = NULL;
383   int i;
384   LinkData *ld;
385   ListBase def_nr_list = {0};
386
387   if (gps->totpoints < 2 || dist < FLT_EPSILON) {
388     return false;
389   }
390   /* TODO: Implement feature point preservation. */
391   int count = stroke_march_count(gps, dist);
392
393   bGPDspoint *new_pt = MEM_callocN(sizeof(bGPDspoint) * count, "gp_stroke_points_sampled");
394   MDeformVert *new_dv = NULL;
395
396   int result_totweight;
397
398   if (gps->dvert != NULL) {
399     stroke_defvert_create_nr_list(gps->dvert, gps->totpoints, &def_nr_list, &result_totweight);
400     new_dv = stroke_defvert_new_count(count, result_totweight, &def_nr_list);
401   }
402
403   int next_point_index = 1;
404   i = 0;
405   float pressure, strength, ratio_result;
406   float vert_color[4];
407   int index_from, index_to;
408   float last_coord[3];
409
410   /*  1st point is always at the start */
411   pt1 = &gps->points[0];
412   copy_v3_v3(last_coord, &pt1->x);
413   pt2 = &new_pt[i];
414   copy_v3_v3(&pt2->x, last_coord);
415   new_pt[i].pressure = pt[0].pressure;
416   new_pt[i].strength = pt[0].strength;
417   memcpy(new_pt[i].vert_color, pt[0].vert_color, sizeof(float) * 4);
418   if (select) {
419     new_pt[i].flag |= GP_SPOINT_SELECT;
420   }
421   i++;
422
423   if (new_dv) {
424     stroke_interpolate_deform_weights(gps, 0, 0, 0, &new_dv[0]);
425   }
426
427   /* The rest. */
428   while ((next_point_index = stroke_march_next_point(gps,
429                                                      next_point_index,
430                                                      last_coord,
431                                                      dist,
432                                                      last_coord,
433                                                      &pressure,
434                                                      &strength,
435                                                      vert_color,
436                                                      &ratio_result,
437                                                      &index_from,
438                                                      &index_to)) > -1) {
439     pt2 = &new_pt[i];
440     copy_v3_v3(&pt2->x, last_coord);
441     new_pt[i].pressure = pressure;
442     new_pt[i].strength = strength;
443     memcpy(new_pt[i].vert_color, vert_color, sizeof(float) * 4);
444     if (select) {
445       new_pt[i].flag |= GP_SPOINT_SELECT;
446     }
447
448     if (new_dv) {
449       stroke_interpolate_deform_weights(gps, index_from, index_to, ratio_result, &new_dv[i]);
450     }
451
452     i++;
453     if (next_point_index == 0) {
454       break; /* last point finished */
455     }
456   }
457
458   gps->points = new_pt;
459   /* Free original vertex list. */
460   MEM_freeN(pt);
461
462   if (new_dv) {
463     /* Free original weight data. */
464     BKE_gpencil_free_stroke_weights(gps);
465     MEM_freeN(gps->dvert);
466     while ((ld = BLI_pophead(&def_nr_list))) {
467       MEM_freeN(ld);
468     }
469
470     gps->dvert = new_dv;
471   }
472
473   gps->totpoints = i;
474
475   /* Calc geometry data. */
476   BKE_gpencil_stroke_geometry_update(gps);
477
478   return true;
479 }
480
481 /**
482  * Backbone stretch similar to Freestyle.
483  * \param gps: Stroke to sample
484  * \param dist: Distance of one segment
485  * \param tip_length: Ignore tip jittering, set zero to use default value.
486  */
487 bool BKE_gpencil_stroke_stretch(bGPDstroke *gps, const float dist, const float tip_length)
488 {
489   bGPDspoint *pt = gps->points, *last_pt, *second_last, *next_pt;
490   int i;
491   float threshold = (tip_length == 0 ? 0.001f : tip_length);
492
493   if (gps->totpoints < 2 || dist < FLT_EPSILON) {
494     return false;
495   }
496
497   last_pt = &pt[gps->totpoints - 1];
498   second_last = &pt[gps->totpoints - 2];
499   next_pt = &pt[1];
500
501   float len1 = 0.0f;
502   float len2 = 0.0f;
503
504   i = 1;
505   while (len1 < threshold && gps->totpoints > i) {
506     next_pt = &pt[i];
507     len1 = len_v3v3(&next_pt->x, &pt->x);
508     i++;
509   }
510
511   i = 2;
512   while (len2 < threshold && gps->totpoints >= i) {
513     second_last = &pt[gps->totpoints - i];
514     len2 = len_v3v3(&last_pt->x, &second_last->x);
515     i++;
516   }
517
518   float extend1 = (len1 + dist) / len1;
519   float extend2 = (len2 + dist) / len2;
520
521   float result1[3], result2[3];
522
523   interp_v3_v3v3(result1, &next_pt->x, &pt->x, extend1);
524   interp_v3_v3v3(result2, &second_last->x, &last_pt->x, extend2);
525
526   copy_v3_v3(&pt->x, result1);
527   copy_v3_v3(&last_pt->x, result2);
528
529   return true;
530 }
531
532 /**
533  * Trim stroke to needed segments
534  * \param gps: Target stroke
535  * \param index_from: the index of the first point to be used in the trimmed result
536  * \param index_to: the index of the last point to be used in the trimmed result
537  */
538 bool BKE_gpencil_stroke_trim_points(bGPDstroke *gps, const int index_from, const int index_to)
539 {
540   bGPDspoint *pt = gps->points, *new_pt;
541   MDeformVert *dv, *new_dv;
542
543   const int new_count = index_to - index_from + 1;
544
545   if (new_count >= gps->totpoints) {
546     return false;
547   }
548
549   if (new_count == 1) {
550     BKE_gpencil_free_stroke_weights(gps);
551     MEM_freeN(gps->points);
552     gps->points = NULL;
553     gps->dvert = NULL;
554     gps->totpoints = 0;
555     return false;
556   }
557
558   new_pt = MEM_callocN(sizeof(bGPDspoint) * new_count, "gp_stroke_points_trimmed");
559
560   for (int i = 0; i < new_count; i++) {
561     memcpy(&new_pt[i], &pt[i + index_from], sizeof(bGPDspoint));
562   }
563
564   if (gps->dvert) {
565     new_dv = MEM_callocN(sizeof(MDeformVert) * new_count, "gp_stroke_dverts_trimmed");
566     for (int i = 0; i < new_count; i++) {
567       dv = &gps->dvert[i + index_from];
568       new_dv[i].flag = dv->flag;
569       new_dv[i].totweight = dv->totweight;
570       new_dv[i].dw = MEM_callocN(sizeof(MDeformWeight) * dv->totweight,
571                                  "gp_stroke_dverts_dw_trimmed");
572       for (int j = 0; j < dv->totweight; j++) {
573         new_dv[i].dw[j].weight = dv->dw[j].weight;
574         new_dv[i].dw[j].def_nr = dv->dw[j].def_nr;
575       }
576     }
577     MEM_freeN(gps->dvert);
578     gps->dvert = new_dv;
579   }
580
581   MEM_freeN(gps->points);
582   gps->points = new_pt;
583   gps->totpoints = new_count;
584
585   return true;
586 }
587
588 bool BKE_gpencil_stroke_split(bGPDframe *gpf,
589                               bGPDstroke *gps,
590                               const int before_index,
591                               bGPDstroke **remaining_gps)
592 {
593   bGPDstroke *new_gps;
594   bGPDspoint *pt = gps->points, *new_pt;
595   MDeformVert *dv, *new_dv;
596
597   if (before_index >= gps->totpoints || before_index == 0) {
598     return false;
599   }
600
601   const int new_count = gps->totpoints - before_index;
602   const int old_count = before_index;
603
604   /* Handle remaining segments first. */
605
606   new_gps = BKE_gpencil_stroke_add_existing_style(
607       gpf, gps, gps->mat_nr, new_count, gps->thickness);
608
609   new_pt = new_gps->points; /* Allocated from above. */
610
611   for (int i = 0; i < new_count; i++) {
612     memcpy(&new_pt[i], &pt[i + before_index], sizeof(bGPDspoint));
613   }
614
615   if (gps->dvert) {
616     new_dv = MEM_callocN(sizeof(MDeformVert) * new_count,
617                          "gp_stroke_dverts_remaining(MDeformVert)");
618     for (int i = 0; i < new_count; i++) {
619       dv = &gps->dvert[i + before_index];
620       new_dv[i].flag = dv->flag;
621       new_dv[i].totweight = dv->totweight;
622       new_dv[i].dw = MEM_callocN(sizeof(MDeformWeight) * dv->totweight,
623                                  "gp_stroke_dverts_dw_remaining(MDeformWeight)");
624       for (int j = 0; j < dv->totweight; j++) {
625         new_dv[i].dw[j].weight = dv->dw[j].weight;
626         new_dv[i].dw[j].def_nr = dv->dw[j].def_nr;
627       }
628     }
629     new_gps->dvert = new_dv;
630   }
631
632   (*remaining_gps) = new_gps;
633
634   /* Trim the original stroke into a shorter one.
635    * Keep the end point. */
636
637   BKE_gpencil_stroke_trim_points(gps, 0, old_count);
638   BKE_gpencil_stroke_geometry_update(gps);
639   return true;
640 }
641
642 /**
643  * Shrink the stroke by length.
644  * \param gps: Stroke to shrink
645  * \param dist: delta length
646  */
647 bool BKE_gpencil_stroke_shrink(bGPDstroke *gps, const float dist)
648 {
649   bGPDspoint *pt = gps->points, *second_last;
650   int i;
651
652   if (gps->totpoints < 2 || dist < FLT_EPSILON) {
653     return false;
654   }
655
656   second_last = &pt[gps->totpoints - 2];
657
658   float len1, this_len1, cut_len1;
659   float len2, this_len2, cut_len2;
660   int index_start, index_end;
661
662   len1 = len2 = this_len1 = this_len2 = cut_len1 = cut_len2 = 0.0f;
663
664   i = 1;
665   while (len1 < dist && gps->totpoints > i - 1) {
666     this_len1 = len_v3v3(&pt[i].x, &pt[i + 1].x);
667     len1 += this_len1;
668     cut_len1 = len1 - dist;
669     i++;
670   }
671   index_start = i - 2;
672
673   i = 2;
674   while (len2 < dist && gps->totpoints >= i) {
675     second_last = &pt[gps->totpoints - i];
676     this_len2 = len_v3v3(&second_last[1].x, &second_last->x);
677     len2 += this_len2;
678     cut_len2 = len2 - dist;
679     i++;
680   }
681   index_end = gps->totpoints - i + 2;
682
683   if (len1 < dist || len2 < dist || index_end <= index_start) {
684     index_start = index_end = 0; /* empty stroke */
685   }
686
687   if ((index_end == index_start + 1) && (cut_len1 + cut_len2 > 1.0f)) {
688     index_start = index_end = 0; /* no length left to cut */
689   }
690
691   BKE_gpencil_stroke_trim_points(gps, index_start, index_end);
692
693   if (gps->totpoints == 0) {
694     return false;
695   }
696
697   pt = gps->points;
698
699   float cut1 = cut_len1 / this_len1;
700   float cut2 = cut_len2 / this_len2;
701
702   float result1[3], result2[3];
703
704   interp_v3_v3v3(result1, &pt[1].x, &pt[0].x, cut1);
705   interp_v3_v3v3(result2, &pt[gps->totpoints - 2].x, &pt[gps->totpoints - 1].x, cut2);
706
707   copy_v3_v3(&pt[0].x, result1);
708   copy_v3_v3(&pt[gps->totpoints - 1].x, result2);
709
710   return true;
711 }
712
713 /**
714  * Apply smooth to stroke point
715  * \param gps: Stroke to smooth
716  * \param i: Point index
717  * \param inf: Amount of smoothing to apply
718  */
719 bool BKE_gpencil_stroke_smooth(bGPDstroke *gps, int i, float inf)
720 {
721   bGPDspoint *pt = &gps->points[i];
722   float sco[3] = {0.0f};
723
724   /* Do nothing if not enough points to smooth out */
725   if (gps->totpoints <= 2) {
726     return false;
727   }
728
729   /* Only affect endpoints by a fraction of the normal strength,
730    * to prevent the stroke from shrinking too much
731    */
732   if ((i == 0) || (i == gps->totpoints - 1)) {
733     inf *= 0.1f;
734   }
735
736   /* Compute smoothed coordinate by taking the ones nearby */
737   /* XXX: This is potentially slow,
738    *      and suffers from accumulation error as earlier points are handled before later ones. */
739   {
740     /* XXX: this is hardcoded to look at 2 points on either side of the current one
741      * (i.e. 5 items total). */
742     const int steps = 2;
743     const float average_fac = 1.0f / (float)(steps * 2 + 1);
744     int step;
745
746     /* add the point itself */
747     madd_v3_v3fl(sco, &pt->x, average_fac);
748
749     /* n-steps before/after current point */
750     /* XXX: review how the endpoints are treated by this algorithm. */
751     /* XXX: falloff measures should also introduce some weighting variations,
752      *      so that further-out points get less weight. */
753     for (step = 1; step <= steps; step++) {
754       bGPDspoint *pt1, *pt2;
755       int before = i - step;
756       int after = i + step;
757
758       CLAMP_MIN(before, 0);
759       CLAMP_MAX(after, gps->totpoints - 1);
760
761       pt1 = &gps->points[before];
762       pt2 = &gps->points[after];
763
764       /* add both these points to the average-sum (s += p[i]/n) */
765       madd_v3_v3fl(sco, &pt1->x, average_fac);
766       madd_v3_v3fl(sco, &pt2->x, average_fac);
767     }
768   }
769
770   /* Based on influence factor, blend between original and optimal smoothed coordinate */
771   interp_v3_v3v3(&pt->x, &pt->x, sco, inf);
772
773   return true;
774 }
775
776 /**
777  * Apply smooth for strength to stroke point */
778 bool BKE_gpencil_stroke_smooth_strength(bGPDstroke *gps, int point_index, float influence)
779 {
780   bGPDspoint *ptb = &gps->points[point_index];
781
782   /* Do nothing if not enough points */
783   if ((gps->totpoints <= 2) || (point_index < 1)) {
784     return false;
785   }
786   /* Only affect endpoints by a fraction of the normal influence */
787   float inf = influence;
788   if ((point_index == 0) || (point_index == gps->totpoints - 1)) {
789     inf *= 0.01f;
790   }
791   /* Limit max influence to reduce pop effect. */
792   CLAMP_MAX(inf, 0.98f);
793
794   float total = 0.0f;
795   float max_strength = 0.0f;
796   const int steps = 4;
797   const float average_fac = 1.0f / (float)(steps * 2 + 1);
798   int step;
799
800   /* add the point itself */
801   total += ptb->strength * average_fac;
802   max_strength = ptb->strength;
803
804   /* n-steps before/after current point */
805   for (step = 1; step <= steps; step++) {
806     bGPDspoint *pt1, *pt2;
807     int before = point_index - step;
808     int after = point_index + step;
809
810     CLAMP_MIN(before, 0);
811     CLAMP_MAX(after, gps->totpoints - 1);
812
813     pt1 = &gps->points[before];
814     pt2 = &gps->points[after];
815
816     /* add both these points to the average-sum (s += p[i]/n) */
817     total += pt1->strength * average_fac;
818     total += pt2->strength * average_fac;
819     /* Save max value. */
820     if (max_strength < pt1->strength) {
821       max_strength = pt1->strength;
822     }
823     if (max_strength < pt2->strength) {
824       max_strength = pt2->strength;
825     }
826   }
827
828   /* Based on influence factor, blend between original and optimal smoothed value. */
829   ptb->strength = interpf(ptb->strength, total, inf);
830   /* Clamp to maximum stroke strength to avoid weird results. */
831   CLAMP_MAX(ptb->strength, max_strength);
832
833   return true;
834 }
835
836 /**
837  * Apply smooth for thickness to stroke point (use pressure) */
838 bool BKE_gpencil_stroke_smooth_thickness(bGPDstroke *gps, int point_index, float influence)
839 {
840   bGPDspoint *ptb = &gps->points[point_index];
841
842   /* Do nothing if not enough points */
843   if ((gps->totpoints <= 2) || (point_index < 1)) {
844     return false;
845   }
846   /* Only affect endpoints by a fraction of the normal influence */
847   float inf = influence;
848   if ((point_index == 0) || (point_index == gps->totpoints - 1)) {
849     inf *= 0.01f;
850   }
851   /* Limit max influence to reduce pop effect. */
852   CLAMP_MAX(inf, 0.98f);
853
854   float total = 0.0f;
855   float max_pressure = 0.0f;
856   const int steps = 4;
857   const float average_fac = 1.0f / (float)(steps * 2 + 1);
858   int step;
859
860   /* add the point itself */
861   total += ptb->pressure * average_fac;
862   max_pressure = ptb->pressure;
863
864   /* n-steps before/after current point */
865   for (step = 1; step <= steps; step++) {
866     bGPDspoint *pt1, *pt2;
867     int before = point_index - step;
868     int after = point_index + step;
869
870     CLAMP_MIN(before, 0);
871     CLAMP_MAX(after, gps->totpoints - 1);
872
873     pt1 = &gps->points[before];
874     pt2 = &gps->points[after];
875
876     /* add both these points to the average-sum (s += p[i]/n) */
877     total += pt1->pressure * average_fac;
878     total += pt2->pressure * average_fac;
879     /* Save max value. */
880     if (max_pressure < pt1->pressure) {
881       max_pressure = pt1->pressure;
882     }
883     if (max_pressure < pt2->pressure) {
884       max_pressure = pt2->pressure;
885     }
886   }
887
888   /* Based on influence factor, blend between original and optimal smoothed value. */
889   ptb->pressure = interpf(ptb->pressure, total, inf);
890   /* Clamp to maximum stroke thickness to avoid weird results. */
891   CLAMP_MAX(ptb->pressure, max_pressure);
892   return true;
893 }
894
895 /**
896  * Apply smooth for UV rotation to stroke point (use pressure).
897  */
898 bool BKE_gpencil_stroke_smooth_uv(bGPDstroke *gps, int point_index, float influence)
899 {
900   bGPDspoint *ptb = &gps->points[point_index];
901
902   /* Do nothing if not enough points */
903   if (gps->totpoints <= 2) {
904     return false;
905   }
906
907   /* Compute theoretical optimal value */
908   bGPDspoint *pta, *ptc;
909   int before = point_index - 1;
910   int after = point_index + 1;
911
912   CLAMP_MIN(before, 0);
913   CLAMP_MAX(after, gps->totpoints - 1);
914
915   pta = &gps->points[before];
916   ptc = &gps->points[after];
917
918   /* the optimal value is the corresponding to the interpolation of the pressure
919    * at the distance of point b
920    */
921   float fac = line_point_factor_v3(&ptb->x, &pta->x, &ptc->x);
922   /* sometimes the factor can be wrong due stroke geometry, so use middle point */
923   if ((fac < 0.0f) || (fac > 1.0f)) {
924     fac = 0.5f;
925   }
926   float optimal = interpf(ptc->uv_rot, pta->uv_rot, fac);
927
928   /* Based on influence factor, blend between original and optimal */
929   ptb->uv_rot = interpf(optimal, ptb->uv_rot, influence);
930   CLAMP(ptb->uv_rot, -M_PI_2, M_PI_2);
931
932   return true;
933 }
934 /* Get points of stroke always flat to view not affected by camera view or view position */
935 void BKE_gpencil_stroke_2d_flat(const bGPDspoint *points,
936                                 int totpoints,
937                                 float (*points2d)[2],
938                                 int *r_direction)
939 {
940   BLI_assert(totpoints >= 2);
941
942   const bGPDspoint *pt0 = &points[0];
943   const bGPDspoint *pt1 = &points[1];
944   const bGPDspoint *pt3 = &points[(int)(totpoints * 0.75)];
945
946   float locx[3];
947   float locy[3];
948   float loc3[3];
949   float normal[3];
950
951   /* local X axis (p0 -> p1) */
952   sub_v3_v3v3(locx, &pt1->x, &pt0->x);
953
954   /* point vector at 3/4 */
955   float v3[3];
956   if (totpoints == 2) {
957     mul_v3_v3fl(v3, &pt3->x, 0.001f);
958   }
959   else {
960     copy_v3_v3(v3, &pt3->x);
961   }
962
963   sub_v3_v3v3(loc3, v3, &pt0->x);
964
965   /* vector orthogonal to polygon plane */
966   cross_v3_v3v3(normal, locx, loc3);
967
968   /* local Y axis (cross to normal/x axis) */
969   cross_v3_v3v3(locy, normal, locx);
970
971   /* Normalize vectors */
972   normalize_v3(locx);
973   normalize_v3(locy);
974
975   /* Get all points in local space */
976   for (int i = 0; i < totpoints; i++) {
977     const bGPDspoint *pt = &points[i];
978     float loc[3];
979
980     /* Get local space using first point as origin */
981     sub_v3_v3v3(loc, &pt->x, &pt0->x);
982
983     points2d[i][0] = dot_v3v3(loc, locx);
984     points2d[i][1] = dot_v3v3(loc, locy);
985   }
986
987   /* Concave (-1), Convex (1), or Autodetect (0)? */
988   *r_direction = (int)locy[2];
989 }
990
991 /* Get points of stroke always flat to view not affected by camera view or view position
992  * using another stroke as reference
993  */
994 void BKE_gpencil_stroke_2d_flat_ref(const bGPDspoint *ref_points,
995                                     int ref_totpoints,
996                                     const bGPDspoint *points,
997                                     int totpoints,
998                                     float (*points2d)[2],
999                                     const float scale,
1000                                     int *r_direction)
1001 {
1002   BLI_assert(totpoints >= 2);
1003
1004   const bGPDspoint *pt0 = &ref_points[0];
1005   const bGPDspoint *pt1 = &ref_points[1];
1006   const bGPDspoint *pt3 = &ref_points[(int)(ref_totpoints * 0.75)];
1007
1008   float locx[3];
1009   float locy[3];
1010   float loc3[3];
1011   float normal[3];
1012
1013   /* local X axis (p0 -> p1) */
1014   sub_v3_v3v3(locx, &pt1->x, &pt0->x);
1015
1016   /* point vector at 3/4 */
1017   float v3[3];
1018   if (totpoints == 2) {
1019     mul_v3_v3fl(v3, &pt3->x, 0.001f);
1020   }
1021   else {
1022     copy_v3_v3(v3, &pt3->x);
1023   }
1024
1025   sub_v3_v3v3(loc3, v3, &pt0->x);
1026
1027   /* vector orthogonal to polygon plane */
1028   cross_v3_v3v3(normal, locx, loc3);
1029
1030   /* local Y axis (cross to normal/x axis) */
1031   cross_v3_v3v3(locy, normal, locx);
1032
1033   /* Normalize vectors */
1034   normalize_v3(locx);
1035   normalize_v3(locy);
1036
1037   /* Get all points in local space */
1038   for (int i = 0; i < totpoints; i++) {
1039     const bGPDspoint *pt = &points[i];
1040     float loc[3];
1041     float v1[3];
1042     float vn[3] = {0.0f, 0.0f, 0.0f};
1043
1044     /* apply scale to extremes of the stroke to get better collision detection
1045      * the scale is divided to get more control in the UI parameter
1046      */
1047     /* first point */
1048     if (i == 0) {
1049       const bGPDspoint *pt_next = &points[i + 1];
1050       sub_v3_v3v3(vn, &pt->x, &pt_next->x);
1051       normalize_v3(vn);
1052       mul_v3_fl(vn, scale / 10.0f);
1053       add_v3_v3v3(v1, &pt->x, vn);
1054     }
1055     /* last point */
1056     else if (i == totpoints - 1) {
1057       const bGPDspoint *pt_prev = &points[i - 1];
1058       sub_v3_v3v3(vn, &pt->x, &pt_prev->x);
1059       normalize_v3(vn);
1060       mul_v3_fl(vn, scale / 10.0f);
1061       add_v3_v3v3(v1, &pt->x, vn);
1062     }
1063     else {
1064       copy_v3_v3(v1, &pt->x);
1065     }
1066
1067     /* Get local space using first point as origin (ref stroke) */
1068     sub_v3_v3v3(loc, v1, &pt0->x);
1069
1070     points2d[i][0] = dot_v3v3(loc, locx);
1071     points2d[i][1] = dot_v3v3(loc, locy);
1072   }
1073
1074   /* Concave (-1), Convex (1), or Autodetect (0)? */
1075   *r_direction = (int)locy[2];
1076 }
1077
1078 /* calc texture coordinates using flat projected points */
1079 static void gpencil_calc_stroke_fill_uv(const float (*points2d)[2],
1080                                         bGPDstroke *gps,
1081                                         const float minv[2],
1082                                         float maxv[2],
1083                                         float (*r_uv)[2])
1084 {
1085   const float s = sin(gps->uv_rotation);
1086   const float c = cos(gps->uv_rotation);
1087
1088   /* Calc center for rotation. */
1089   float center[2] = {0.5f, 0.5f};
1090   float d[2];
1091   d[0] = maxv[0] - minv[0];
1092   d[1] = maxv[1] - minv[1];
1093   for (int i = 0; i < gps->totpoints; i++) {
1094     r_uv[i][0] = (points2d[i][0] - minv[0]) / d[0];
1095     r_uv[i][1] = (points2d[i][1] - minv[1]) / d[1];
1096
1097     /* Apply translation. */
1098     add_v2_v2(r_uv[i], gps->uv_translation);
1099
1100     /* Apply Rotation. */
1101     r_uv[i][0] -= center[0];
1102     r_uv[i][1] -= center[1];
1103
1104     float x = r_uv[i][0] * c - r_uv[i][1] * s;
1105     float y = r_uv[i][0] * s + r_uv[i][1] * c;
1106
1107     r_uv[i][0] = x + center[0];
1108     r_uv[i][1] = y + center[1];
1109
1110     /* Apply scale. */
1111     if (gps->uv_scale != 0.0f) {
1112       mul_v2_fl(r_uv[i], 1.0f / gps->uv_scale);
1113     }
1114   }
1115 }
1116
1117 /* Triangulate stroke for high quality fill (this is done only if cache is null or stroke was
1118  * modified) */
1119 void BKE_gpencil_stroke_fill_triangulate(bGPDstroke *gps)
1120 {
1121   BLI_assert(gps->totpoints >= 3);
1122
1123   /* allocate memory for temporary areas */
1124   gps->tot_triangles = gps->totpoints - 2;
1125   uint(*tmp_triangles)[3] = MEM_mallocN(sizeof(*tmp_triangles) * gps->tot_triangles,
1126                                         "GP Stroke temp triangulation");
1127   float(*points2d)[2] = MEM_mallocN(sizeof(*points2d) * gps->totpoints,
1128                                     "GP Stroke temp 2d points");
1129   float(*uv)[2] = MEM_mallocN(sizeof(*uv) * gps->totpoints, "GP Stroke temp 2d uv data");
1130
1131   int direction = 0;
1132
1133   /* convert to 2d and triangulate */
1134   BKE_gpencil_stroke_2d_flat(gps->points, gps->totpoints, points2d, &direction);
1135   BLI_polyfill_calc(points2d, (uint)gps->totpoints, direction, tmp_triangles);
1136
1137   /* calc texture coordinates automatically */
1138   float minv[2];
1139   float maxv[2];
1140   /* first needs bounding box data */
1141   ARRAY_SET_ITEMS(minv, -1.0f, -1.0f);
1142   ARRAY_SET_ITEMS(maxv, 1.0f, 1.0f);
1143
1144   /* calc uv data */
1145   gpencil_calc_stroke_fill_uv(points2d, gps, minv, maxv, uv);
1146
1147   /* Save triangulation data. */
1148   if (gps->tot_triangles > 0) {
1149     MEM_SAFE_FREE(gps->triangles);
1150     gps->triangles = MEM_callocN(sizeof(*gps->triangles) * gps->tot_triangles,
1151                                  "GP Stroke triangulation");
1152
1153     for (int i = 0; i < gps->tot_triangles; i++) {
1154       memcpy(gps->triangles[i].verts, tmp_triangles[i], sizeof(uint[3]));
1155     }
1156
1157     /* Copy UVs to bGPDspoint. */
1158     for (int i = 0; i < gps->totpoints; i++) {
1159       copy_v2_v2(gps->points[i].uv_fill, uv[i]);
1160     }
1161   }
1162   else {
1163     /* No triangles needed - Free anything allocated previously */
1164     if (gps->triangles) {
1165       MEM_freeN(gps->triangles);
1166     }
1167
1168     gps->triangles = NULL;
1169   }
1170
1171   /* clear memory */
1172   MEM_SAFE_FREE(tmp_triangles);
1173   MEM_SAFE_FREE(points2d);
1174   MEM_SAFE_FREE(uv);
1175 }
1176
1177 /* texture coordinate utilities */
1178 void BKE_gpencil_stroke_uv_update(bGPDstroke *gps)
1179 {
1180   if (gps == NULL || gps->totpoints == 0) {
1181     return;
1182   }
1183
1184   bGPDspoint *pt = gps->points;
1185   float totlen = 0.0f;
1186   pt[0].uv_fac = totlen;
1187   for (int i = 1; i < gps->totpoints; i++) {
1188     totlen += len_v3v3(&pt[i - 1].x, &pt[i].x);
1189     pt[i].uv_fac = totlen;
1190   }
1191 }
1192
1193 /* Recalc the internal geometry caches for fill and uvs. */
1194 void BKE_gpencil_stroke_geometry_update(bGPDstroke *gps)
1195 {
1196   if (gps == NULL) {
1197     return;
1198   }
1199
1200   if (gps->totpoints > 2) {
1201     BKE_gpencil_stroke_fill_triangulate(gps);
1202   }
1203   else {
1204     gps->tot_triangles = 0;
1205     MEM_SAFE_FREE(gps->triangles);
1206   }
1207
1208   /* calc uv data along the stroke */
1209   BKE_gpencil_stroke_uv_update(gps);
1210
1211   /* Calc stroke bounding box. */
1212   BKE_gpencil_stroke_boundingbox_calc(gps);
1213 }
1214
1215 float BKE_gpencil_stroke_length(const bGPDstroke *gps, bool use_3d)
1216 {
1217   if (!gps->points || gps->totpoints < 2) {
1218     return 0.0f;
1219   }
1220   float *last_pt = &gps->points[0].x;
1221   int i;
1222   bGPDspoint *pt;
1223   float total_length = 0.0f;
1224   for (i = 1; i < gps->totpoints; i++) {
1225     pt = &gps->points[i];
1226     if (use_3d) {
1227       total_length += len_v3v3(&pt->x, last_pt);
1228     }
1229     else {
1230       total_length += len_v2v2(&pt->x, last_pt);
1231     }
1232     last_pt = &pt->x;
1233   }
1234   return total_length;
1235 }
1236
1237 /**
1238  * Trim stroke to the first intersection or loop
1239  * \param gps: Stroke data
1240  */
1241 bool BKE_gpencil_stroke_trim(bGPDstroke *gps)
1242 {
1243   if (gps->totpoints < 4) {
1244     return false;
1245   }
1246   bool intersect = false;
1247   int start, end;
1248   float point[3];
1249   /* loop segments from start until we have an intersection */
1250   for (int i = 0; i < gps->totpoints - 2; i++) {
1251     start = i;
1252     bGPDspoint *a = &gps->points[start];
1253     bGPDspoint *b = &gps->points[start + 1];
1254     for (int j = start + 2; j < gps->totpoints - 1; j++) {
1255       end = j + 1;
1256       bGPDspoint *c = &gps->points[j];
1257       bGPDspoint *d = &gps->points[end];
1258       float pointb[3];
1259       /* get intersection */
1260       if (isect_line_line_v3(&a->x, &b->x, &c->x, &d->x, point, pointb)) {
1261         if (len_v3(point) > 0.0f) {
1262           float closest[3];
1263           /* check intersection is on both lines */
1264           float lambda = closest_to_line_v3(closest, point, &a->x, &b->x);
1265           if ((lambda <= 0.0f) || (lambda >= 1.0f)) {
1266             continue;
1267           }
1268           lambda = closest_to_line_v3(closest, point, &c->x, &d->x);
1269           if ((lambda <= 0.0f) || (lambda >= 1.0f)) {
1270             continue;
1271           }
1272           else {
1273             intersect = true;
1274             break;
1275           }
1276         }
1277       }
1278     }
1279     if (intersect) {
1280       break;
1281     }
1282   }
1283
1284   /* trim unwanted points */
1285   if (intersect) {
1286
1287     /* save points */
1288     bGPDspoint *old_points = MEM_dupallocN(gps->points);
1289     MDeformVert *old_dvert = NULL;
1290     MDeformVert *dvert_src = NULL;
1291
1292     if (gps->dvert != NULL) {
1293       old_dvert = MEM_dupallocN(gps->dvert);
1294     }
1295
1296     /* resize gps */
1297     int newtot = end - start + 1;
1298
1299     gps->points = MEM_recallocN(gps->points, sizeof(*gps->points) * newtot);
1300     if (gps->dvert != NULL) {
1301       gps->dvert = MEM_recallocN(gps->dvert, sizeof(*gps->dvert) * newtot);
1302     }
1303
1304     for (int i = 0; i < newtot; i++) {
1305       int idx = start + i;
1306       bGPDspoint *pt_src = &old_points[idx];
1307       bGPDspoint *pt_new = &gps->points[i];
1308       memcpy(pt_new, pt_src, sizeof(bGPDspoint));
1309       if (gps->dvert != NULL) {
1310         dvert_src = &old_dvert[idx];
1311         MDeformVert *dvert = &gps->dvert[i];
1312         memcpy(dvert, dvert_src, sizeof(MDeformVert));
1313         if (dvert_src->dw) {
1314           memcpy(dvert->dw, dvert_src->dw, sizeof(MDeformWeight));
1315         }
1316       }
1317       if (idx == start || idx == end) {
1318         copy_v3_v3(&pt_new->x, point);
1319       }
1320     }
1321
1322     gps->totpoints = newtot;
1323
1324     MEM_SAFE_FREE(old_points);
1325     MEM_SAFE_FREE(old_dvert);
1326   }
1327
1328   BKE_gpencil_stroke_geometry_update(gps);
1329
1330   return intersect;
1331 }
1332
1333 /**
1334  * Close stroke
1335  * \param gps: Stroke to close
1336  */
1337 bool BKE_gpencil_stroke_close(bGPDstroke *gps)
1338 {
1339   bGPDspoint *pt1 = NULL;
1340   bGPDspoint *pt2 = NULL;
1341
1342   /* Only can close a stroke with 3 points or more. */
1343   if (gps->totpoints < 3) {
1344     return false;
1345   }
1346
1347   /* Calc average distance between points to get same level of sampling. */
1348   float dist_tot = 0.0f;
1349   for (int i = 0; i < gps->totpoints - 1; i++) {
1350     pt1 = &gps->points[i];
1351     pt2 = &gps->points[i + 1];
1352     dist_tot += len_v3v3(&pt1->x, &pt2->x);
1353   }
1354   /* Calc the average distance. */
1355   float dist_avg = dist_tot / (gps->totpoints - 1);
1356
1357   /* Calc distance between last and first point. */
1358   pt1 = &gps->points[gps->totpoints - 1];
1359   pt2 = &gps->points[0];
1360   float dist_close = len_v3v3(&pt1->x, &pt2->x);
1361
1362   /* if the distance to close is very small, don't need add points and just enable cyclic. */
1363   if (dist_close <= dist_avg) {
1364     gps->flag |= GP_STROKE_CYCLIC;
1365     return true;
1366   }
1367
1368   /* Calc number of points required using the average distance. */
1369   int tot_newpoints = MAX2(dist_close / dist_avg, 1);
1370
1371   /* Resize stroke array. */
1372   int old_tot = gps->totpoints;
1373   gps->totpoints += tot_newpoints;
1374   gps->points = MEM_recallocN(gps->points, sizeof(*gps->points) * gps->totpoints);
1375   if (gps->dvert != NULL) {
1376     gps->dvert = MEM_recallocN(gps->dvert, sizeof(*gps->dvert) * gps->totpoints);
1377   }
1378
1379   /* Generate new points */
1380   pt1 = &gps->points[old_tot - 1];
1381   pt2 = &gps->points[0];
1382   bGPDspoint *pt = &gps->points[old_tot];
1383   for (int i = 1; i < tot_newpoints + 1; i++, pt++) {
1384     float step = (tot_newpoints > 1) ? ((float)i / (float)tot_newpoints) : 0.99f;
1385     /* Clamp last point to be near, but not on top of first point. */
1386     if ((tot_newpoints > 1) && (i == tot_newpoints)) {
1387       step *= 0.99f;
1388     }
1389
1390     /* Average point. */
1391     interp_v3_v3v3(&pt->x, &pt1->x, &pt2->x, step);
1392     pt->pressure = interpf(pt2->pressure, pt1->pressure, step);
1393     pt->strength = interpf(pt2->strength, pt1->strength, step);
1394     pt->flag = 0;
1395     interp_v4_v4v4(pt->vert_color, pt1->vert_color, pt2->vert_color, step);
1396
1397     /* Set weights. */
1398     if (gps->dvert != NULL) {
1399       MDeformVert *dvert1 = &gps->dvert[old_tot - 1];
1400       MDeformWeight *dw1 = BKE_defvert_ensure_index(dvert1, 0);
1401       float weight_1 = dw1 ? dw1->weight : 0.0f;
1402
1403       MDeformVert *dvert2 = &gps->dvert[0];
1404       MDeformWeight *dw2 = BKE_defvert_ensure_index(dvert2, 0);
1405       float weight_2 = dw2 ? dw2->weight : 0.0f;
1406
1407       MDeformVert *dvert_final = &gps->dvert[old_tot + i - 1];
1408       dvert_final->totweight = 0;
1409       MDeformWeight *dw = BKE_defvert_ensure_index(dvert_final, 0);
1410       if (dvert_final->dw) {
1411         dw->weight = interpf(weight_2, weight_1, step);
1412       }
1413     }
1414   }
1415
1416   /* Enable cyclic flag. */
1417   gps->flag |= GP_STROKE_CYCLIC;
1418
1419   return true;
1420 }
1421 /* Dissolve points in stroke */
1422 void BKE_gpencil_dissolve_points(bGPDframe *gpf, bGPDstroke *gps, const short tag)
1423 {
1424   bGPDspoint *pt;
1425   MDeformVert *dvert = NULL;
1426   int i;
1427
1428   int tot = gps->totpoints; /* number of points in new buffer */
1429   /* first pass: count points to remove */
1430   /* Count how many points are selected (i.e. how many to remove) */
1431   for (i = 0, pt = gps->points; i < gps->totpoints; i++, pt++) {
1432     if (pt->flag & tag) {
1433       /* selected point - one of the points to remove */
1434       tot--;
1435     }
1436   }
1437
1438   /* if no points are left, we simply delete the entire stroke */
1439   if (tot <= 0) {
1440     /* remove the entire stroke */
1441     if (gps->points) {
1442       MEM_freeN(gps->points);
1443     }
1444     if (gps->dvert) {
1445       BKE_gpencil_free_stroke_weights(gps);
1446       MEM_freeN(gps->dvert);
1447     }
1448     if (gps->triangles) {
1449       MEM_freeN(gps->triangles);
1450     }
1451     BLI_freelinkN(&gpf->strokes, gps);
1452   }
1453   else {
1454     /* just copy all points to keep into a smaller buffer */
1455     bGPDspoint *new_points = MEM_callocN(sizeof(bGPDspoint) * tot, "new gp stroke points copy");
1456     bGPDspoint *npt = new_points;
1457
1458     MDeformVert *new_dvert = NULL;
1459     MDeformVert *ndvert = NULL;
1460
1461     if (gps->dvert != NULL) {
1462       new_dvert = MEM_callocN(sizeof(MDeformVert) * tot, "new gp stroke weights copy");
1463       ndvert = new_dvert;
1464     }
1465
1466     (gps->dvert != NULL) ? dvert = gps->dvert : NULL;
1467     for (i = 0, pt = gps->points; i < gps->totpoints; i++, pt++) {
1468       if ((pt->flag & tag) == 0) {
1469         *npt = *pt;
1470         npt++;
1471
1472         if (gps->dvert != NULL) {
1473           *ndvert = *dvert;
1474           ndvert->dw = MEM_dupallocN(dvert->dw);
1475           ndvert++;
1476         }
1477       }
1478       if (gps->dvert != NULL) {
1479         dvert++;
1480       }
1481     }
1482
1483     /* free the old buffer */
1484     if (gps->points) {
1485       MEM_freeN(gps->points);
1486     }
1487     if (gps->dvert) {
1488       BKE_gpencil_free_stroke_weights(gps);
1489       MEM_freeN(gps->dvert);
1490     }
1491
1492     /* save the new buffer */
1493     gps->points = new_points;
1494     gps->dvert = new_dvert;
1495     gps->totpoints = tot;
1496
1497     /* triangles cache needs to be recalculated */
1498     BKE_gpencil_stroke_geometry_update(gps);
1499   }
1500 }
1501
1502 /* Merge by distance ------------------------------------- */
1503 /* Reduce a series of points when the distance is below a threshold.
1504  * Special case for first and last points (both are keeped) for other points,
1505  * the merge point always is at first point.
1506  * \param gpf: Grease Pencil frame
1507  * \param gps: Grease Pencil stroke
1508  * \param threshold: Distance between points
1509  * \param use_unselected: Set to true to analyze all stroke and not only selected points
1510  */
1511 void BKE_gpencil_stroke_merge_distance(bGPDframe *gpf,
1512                                        bGPDstroke *gps,
1513                                        const float threshold,
1514                                        const bool use_unselected)
1515 {
1516   bGPDspoint *pt = NULL;
1517   bGPDspoint *pt_next = NULL;
1518   float tagged = false;
1519   /* Use square distance to speed up loop */
1520   const float th_square = threshold * threshold;
1521   /* Need to have something to merge. */
1522   if (gps->totpoints < 2) {
1523     return;
1524   }
1525   int i = 0;
1526   int step = 1;
1527   while ((i < gps->totpoints - 1) && (i + step < gps->totpoints)) {
1528     pt = &gps->points[i];
1529     if (pt->flag & GP_SPOINT_TAG) {
1530       i++;
1531       step = 1;
1532       continue;
1533     }
1534     pt_next = &gps->points[i + step];
1535     /* Do not recalc tagged points. */
1536     if (pt_next->flag & GP_SPOINT_TAG) {
1537       step++;
1538       continue;
1539     }
1540     /* Check if contiguous points are selected. */
1541     if (!use_unselected) {
1542       if (((pt->flag & GP_SPOINT_SELECT) == 0) || ((pt_next->flag & GP_SPOINT_SELECT) == 0)) {
1543         i++;
1544         step = 1;
1545         continue;
1546       }
1547     }
1548     float len_square = len_squared_v3v3(&pt->x, &pt_next->x);
1549     if (len_square <= th_square) {
1550       tagged = true;
1551       if (i != gps->totpoints - 1) {
1552         /* Tag second point for delete. */
1553         pt_next->flag |= GP_SPOINT_TAG;
1554       }
1555       else {
1556         pt->flag |= GP_SPOINT_TAG;
1557       }
1558       /* Jump to next pair of points, keeping first point segment equals.*/
1559       step++;
1560     }
1561     else {
1562       /* Analyze next point. */
1563       i++;
1564       step = 1;
1565     }
1566   }
1567
1568   /* Always untag extremes. */
1569   pt = &gps->points[0];
1570   pt->flag &= ~GP_SPOINT_TAG;
1571   pt = &gps->points[gps->totpoints - 1];
1572   pt->flag &= ~GP_SPOINT_TAG;
1573
1574   /* Dissolve tagged points */
1575   if (tagged) {
1576     BKE_gpencil_dissolve_points(gpf, gps, GP_SPOINT_TAG);
1577   }
1578
1579   /* Calc geometry data. */
1580   BKE_gpencil_stroke_geometry_update(gps);
1581 }
1582
1583 /* Apply Transforms */
1584 void BKE_gpencil_transform(bGPdata *gpd, float mat[4][4])
1585 {
1586   if (gpd == NULL) {
1587     return;
1588   }
1589
1590   const float scalef = mat4_to_scale(mat);
1591   LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
1592     /* FIXME: For now, we just skip parented layers.
1593      * Otherwise, we have to update each frame to find
1594      * the current parent position/effects.
1595      */
1596     if (gpl->parent) {
1597       continue;
1598     }
1599
1600     LISTBASE_FOREACH (bGPDframe *, gpf, &gpl->frames) {
1601       LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
1602         bGPDspoint *pt;
1603         int i;
1604
1605         for (pt = gps->points, i = 0; i < gps->totpoints; pt++, i++) {
1606           mul_m4_v3(mat, &pt->x);
1607           pt->pressure *= scalef;
1608         }
1609
1610         /* Distortion may mean we need to re-triangulate. */
1611         BKE_gpencil_stroke_geometry_update(gps);
1612       }
1613     }
1614   }
1615 }
1616 /** \} */