Merging r49622 through r49623 from trunk into soc-2011-tomato
[blender.git] / source / blender / blenkernel / intern / mask.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2012 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation,
22  *                 Sergey Sharybin
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/blenkernel/intern/mask.c
28  *  \ingroup bke
29  */
30
31 #include <stddef.h>
32 #include <string.h>
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_utildefines.h"
37 #include "BLI_path_util.h"
38 #include "BLI_string.h"
39 #include "BLI_listbase.h"
40 #include "BLI_math.h"
41
42 #include "DNA_mask_types.h"
43 #include "DNA_scene_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_screen_types.h"
46 #include "DNA_space_types.h"
47 #include "DNA_movieclip_types.h"
48 #include "DNA_tracking_types.h"
49
50 #include "BKE_curve.h"
51 #include "BKE_global.h"
52 #include "BKE_library.h"
53 #include "BKE_main.h"
54 #include "BKE_mask.h"
55 #include "BKE_tracking.h"
56 #include "BKE_movieclip.h"
57 #include "BKE_utildefines.h"
58
59 static MaskSplinePoint *mask_spline_point_next(MaskSpline *spline, MaskSplinePoint *points_array, MaskSplinePoint *point)
60 {
61         if (point == &points_array[spline->tot_point - 1]) {
62                 if (spline->flag & MASK_SPLINE_CYCLIC) {
63                         return &points_array[0];
64                 }
65                 else {
66                         return NULL;
67                 }
68         }
69         else {
70                 return point + 1;
71         }
72 }
73
74 static MaskSplinePoint *mask_spline_point_prev(MaskSpline *spline, MaskSplinePoint *points_array, MaskSplinePoint *point)
75 {
76         if (point == points_array) {
77                 if (spline->flag & MASK_SPLINE_CYCLIC) {
78                         return &points_array[spline->tot_point - 1];
79                 }
80                 else {
81                         return NULL;
82                 }
83         }
84         else {
85                 return point - 1;
86         }
87 }
88
89 static BezTriple *mask_spline_point_next_bezt(MaskSpline *spline, MaskSplinePoint *points_array, MaskSplinePoint *point)
90 {
91         if (point == &points_array[spline->tot_point - 1]) {
92                 if (spline->flag & MASK_SPLINE_CYCLIC) {
93                         return &(points_array[0].bezt);
94                 }
95                 else {
96                         return NULL;
97                 }
98         }
99         else {
100                 return &((point + 1))->bezt;
101         }
102 }
103
104 #if 0
105 static BezTriple *mask_spline_point_prev_bezt(MaskSpline *spline, MaskSplinePoint *points_array, MaskSplinePoint *point)
106 {
107         if (point == points_array) {
108                 if (spline->flag & MASK_SPLINE_CYCLIC) {
109                         return &(points_array[0].bezt);
110                 }
111                 else {
112                         return NULL;
113                 }
114         }
115         else {
116                 return &((point - 1))->bezt;
117         }
118 }
119 #endif
120
121 MaskSplinePoint *BKE_mask_spline_point_array(MaskSpline *spline)
122 {
123         return spline->points_deform ? spline->points_deform : spline->points;
124 }
125
126 MaskSplinePoint *BKE_mask_spline_point_array_from_point(MaskSpline *spline, MaskSplinePoint *point_ref)
127 {
128         if ((point_ref >= spline->points) && (point_ref < &spline->points[spline->tot_point])) {
129                 return spline->points;
130         }
131
132         if ((point_ref >= spline->points_deform) && (point_ref < &spline->points_deform[spline->tot_point])) {
133                 return spline->points_deform;
134         }
135
136         BLI_assert(!"wrong array");
137         return NULL;
138 }
139
140 /* mask layers */
141
142 MaskLayer *BKE_mask_layer_new(Mask *mask, const char *name)
143 {
144         MaskLayer *masklay = MEM_callocN(sizeof(MaskLayer), __func__);
145
146         if (name && name[0])
147                 BLI_strncpy(masklay->name, name, sizeof(masklay->name));
148         else
149                 strcpy(masklay->name, "MaskLayer");
150
151         BLI_addtail(&mask->masklayers, masklay);
152
153         BKE_mask_layer_unique_name(mask, masklay);
154
155         mask->masklay_tot++;
156
157         masklay->blend = MASK_BLEND_MERGE;
158         masklay->alpha = 1.0f;
159
160         return masklay;
161 }
162
163 /* note: may still be hidden, caller needs to check */
164 MaskLayer *BKE_mask_layer_active(Mask *mask)
165 {
166         return BLI_findlink(&mask->masklayers, mask->masklay_act);
167 }
168
169 void BKE_mask_layer_active_set(Mask *mask, MaskLayer *masklay)
170 {
171         mask->masklay_act = BLI_findindex(&mask->masklayers, masklay);
172 }
173
174 void BKE_mask_layer_remove(Mask *mask, MaskLayer *masklay)
175 {
176         BLI_remlink(&mask->masklayers, masklay);
177         BKE_mask_layer_free(masklay);
178
179         mask->masklay_tot--;
180
181         if (mask->masklay_act >= mask->masklay_tot)
182                 mask->masklay_act = mask->masklay_tot - 1;
183 }
184
185 void BKE_mask_layer_unique_name(Mask *mask, MaskLayer *masklay)
186 {
187         BLI_uniquename(&mask->masklayers, masklay, "MaskLayer", '.', offsetof(MaskLayer, name), sizeof(masklay->name));
188 }
189
190 MaskLayer *BKE_mask_layer_copy(MaskLayer *masklay)
191 {
192         MaskLayer *masklay_new;
193         MaskSpline *spline;
194
195         masklay_new = MEM_callocN(sizeof(MaskLayer), "new mask layer");
196
197         BLI_strncpy(masklay_new->name, masklay->name, sizeof(masklay_new->name));
198
199         masklay_new->alpha = masklay->alpha;
200         masklay_new->blend = masklay->blend;
201         masklay_new->blend_flag = masklay->blend_flag;
202         masklay_new->flag = masklay->flag;
203         masklay_new->restrictflag = masklay->restrictflag;
204
205         for (spline = masklay->splines.first; spline; spline = spline->next) {
206                 MaskSpline *spline_new = BKE_mask_spline_copy(spline);
207
208                 BLI_addtail(&masklay_new->splines, spline_new);
209         }
210
211         /* correct animation */
212         if (masklay->splines_shapes.first) {
213                 MaskLayerShape *masklay_shape;
214                 MaskLayerShape *masklay_shape_new;
215
216                 for (masklay_shape = masklay->splines_shapes.first;
217                      masklay_shape;
218                      masklay_shape = masklay_shape->next)
219                 {
220                         masklay_shape_new = MEM_callocN(sizeof(MaskLayerShape), "new mask layer shape");
221
222                         masklay_shape_new->data = MEM_dupallocN(masklay_shape->data);
223                         masklay_shape_new->tot_vert = masklay_shape->tot_vert;
224                         masklay_shape_new->flag = masklay_shape->flag;
225                         masklay_shape_new->frame = masklay_shape->frame;
226
227                         BLI_addtail(&masklay_new->splines_shapes, masklay_shape_new);
228                 }
229         }
230
231         return masklay_new;
232 }
233
234 void BKE_mask_layer_copy_list(ListBase *masklayers_new, ListBase *masklayers)
235 {
236         MaskLayer *layer;
237
238         for (layer = masklayers->first; layer; layer = layer->next) {
239                 MaskLayer *layer_new = BKE_mask_layer_copy(layer);
240
241                 BLI_addtail(masklayers_new, layer_new);
242         }
243 }
244
245 /* splines */
246
247 MaskSpline *BKE_mask_spline_add(MaskLayer *masklay)
248 {
249         MaskSpline *spline;
250
251         spline = MEM_callocN(sizeof(MaskSpline), "new mask spline");
252         BLI_addtail(&masklay->splines, spline);
253
254         /* spline shall have one point at least */
255         spline->points = MEM_callocN(sizeof(MaskSplinePoint), "new mask spline point");
256         spline->tot_point = 1;
257
258         /* cyclic shapes are more usually used */
259         // spline->flag |= MASK_SPLINE_CYCLIC; // disable because its not so nice for drawing. could be done differently
260
261         spline->weight_interp = MASK_SPLINE_INTERP_EASE;
262
263         BKE_mask_parent_init(&spline->parent);
264
265         return spline;
266 }
267
268 unsigned int BKE_mask_spline_resolution(MaskSpline *spline, int width, int height)
269 {
270         float max_segment = 0.01f;
271         unsigned int i, resol = 1;
272
273         if (width != 0 && height != 0) {
274                 if (width >= height)
275                         max_segment = 1.0f / (float) width;
276                 else
277                         max_segment = 1.0f / (float) height;
278         }
279
280         for (i = 0; i < spline->tot_point; i++) {
281                 MaskSplinePoint *point = &spline->points[i];
282                 BezTriple *bezt, *bezt_next;
283                 float a, b, c, len;
284                 unsigned int cur_resol;
285
286                 bezt = &point->bezt;
287                 bezt_next = mask_spline_point_next_bezt(spline, spline->points, point);
288
289                 if (bezt_next == NULL) {
290                         break;
291                 }
292
293                 a = len_v3v3(bezt->vec[1], bezt->vec[2]);
294                 b = len_v3v3(bezt->vec[2], bezt_next->vec[0]);
295                 c = len_v3v3(bezt_next->vec[0], bezt_next->vec[1]);
296
297                 len = a + b + c;
298                 cur_resol = len / max_segment;
299
300                 resol = MAX2(resol, cur_resol);
301
302                 if (resol >= MASK_RESOL_MAX) {
303                         break;
304                 }
305         }
306
307         return CLAMPIS(resol, 1, MASK_RESOL_MAX);
308 }
309
310 unsigned int BKE_mask_spline_feather_resolution(MaskSpline *spline, int width, int height)
311 {
312         const float max_segment = 0.005;
313         unsigned int resol = BKE_mask_spline_resolution(spline, width, height);
314         float max_jump = 0.0f;
315         int i;
316
317         /* avoid checking the featrher if we already hit the maximum value */
318         if (resol >= MASK_RESOL_MAX) {
319                 return MASK_RESOL_MAX;
320         }
321
322         for (i = 0; i < spline->tot_point; i++) {
323                 MaskSplinePoint *point = &spline->points[i];
324                 float prev_u, prev_w;
325                 int j;
326
327                 prev_u = 0.0f;
328                 prev_w = point->bezt.weight;
329
330                 for (j = 0; j < point->tot_uw; j++) {
331                         const float w_diff = (point->uw[j].w - prev_w);
332                         const float u_diff = (point->uw[j].u - prev_u);
333
334                         /* avoid divide by zero and very high values,
335                          * though these get clamped eventually */
336                         if (u_diff > FLT_EPSILON) {
337                                 float jump = fabsf(w_diff / u_diff);
338
339                                 max_jump = MAX2(max_jump, jump);
340                         }
341
342                         prev_u = point->uw[j].u;
343                         prev_w = point->uw[j].w;
344                 }
345         }
346
347         resol += max_jump / max_segment;
348
349         return CLAMPIS(resol, 1, MASK_RESOL_MAX);
350 }
351
352 int BKE_mask_spline_differentiate_calc_total(const MaskSpline *spline, const unsigned int resol)
353 {
354         if (spline->flag & MASK_SPLINE_CYCLIC) {
355                 return spline->tot_point * resol;
356         }
357         else {
358                 return ((spline->tot_point - 1) * resol) + 1;
359         }
360 }
361
362 float (*BKE_mask_spline_differentiate_with_resolution_ex(MaskSpline *spline,
363                                                          int *tot_diff_point,
364                                                          const unsigned int resol
365                                                          ))[2]
366 {
367         MaskSplinePoint *points_array = BKE_mask_spline_point_array(spline);
368
369         MaskSplinePoint *point, *prev;
370         float (*diff_points)[2], (*fp)[2];
371         const int tot = BKE_mask_spline_differentiate_calc_total(spline, resol);
372         int a;
373
374         if (spline->tot_point <= 1) {
375                 /* nothing to differentiate */
376                 *tot_diff_point = 0;
377                 return NULL;
378         }
379
380         /* len+1 because of 'forward_diff_bezier' function */
381         *tot_diff_point = tot;
382         diff_points = fp = MEM_mallocN((tot + 1) * sizeof(*diff_points), "mask spline vets");
383
384         a = spline->tot_point - 1;
385         if (spline->flag & MASK_SPLINE_CYCLIC)
386                 a++;
387
388         prev = points_array;
389         point = prev + 1;
390
391         while (a--) {
392                 BezTriple *prevbezt;
393                 BezTriple *bezt;
394                 int j;
395
396                 if (a == 0 && (spline->flag & MASK_SPLINE_CYCLIC))
397                         point = points_array;
398
399                 prevbezt = &prev->bezt;
400                 bezt = &point->bezt;
401
402                 for (j = 0; j < 2; j++) {
403                         BKE_curve_forward_diff_bezier(prevbezt->vec[1][j], prevbezt->vec[2][j],
404                                                       bezt->vec[0][j], bezt->vec[1][j],
405                                                       &(*fp)[j], resol, 2 * sizeof(float));
406                 }
407
408                 fp += resol;
409
410                 if (a == 0 && (spline->flag & MASK_SPLINE_CYCLIC) == 0) {
411                         copy_v2_v2(*fp, bezt->vec[1]);
412                 }
413
414                 prev = point;
415                 point++;
416         }
417
418         return diff_points;
419 }
420
421 float (*BKE_mask_spline_differentiate_with_resolution(MaskSpline *spline, int width, int height,
422                                                       int *tot_diff_point
423                                                       ))[2]
424 {
425         int unsigned resol = BKE_mask_spline_resolution(spline, width, height);
426
427         return BKE_mask_spline_differentiate_with_resolution_ex(spline, tot_diff_point, resol);
428 }
429
430 float (*BKE_mask_spline_differentiate(MaskSpline *spline, int *tot_diff_point))[2]
431 {
432         return BKE_mask_spline_differentiate_with_resolution(spline, 0, 0, tot_diff_point);
433 }
434
435 /* ** feather points self-intersection collapse routine ** */
436
437 typedef struct FeatherEdgesBucket {
438         int tot_segment;
439         int (*segments)[2];
440         int alloc_segment;
441 } FeatherEdgesBucket;
442
443 static void feather_bucket_add_edge(FeatherEdgesBucket *bucket, int start, int end)
444 {
445         const int alloc_delta = 256;
446
447         if (bucket->tot_segment >= bucket->alloc_segment) {
448                 if (!bucket->segments) {
449                         bucket->segments = MEM_callocN(alloc_delta * sizeof(*bucket->segments), "feather bucket segments");
450                 }
451                 else {
452                         bucket->segments = MEM_reallocN(bucket->segments,
453                                         (alloc_delta + bucket->tot_segment) * sizeof(*bucket->segments));
454                 }
455
456                 bucket->alloc_segment += alloc_delta;
457         }
458
459         bucket->segments[bucket->tot_segment][0] = start;
460         bucket->segments[bucket->tot_segment][1] = end;
461
462         bucket->tot_segment++;
463 }
464
465 static void feather_bucket_check_intersect(float (*feather_points)[2], int tot_feather_point, FeatherEdgesBucket *bucket,
466                                            int cur_a, int cur_b)
467 {
468         int i;
469
470         float *v1 = (float *) feather_points[cur_a];
471         float *v2 = (float *) feather_points[cur_b];
472
473         for (i = 0; i < bucket->tot_segment; i++) {
474                 int check_a = bucket->segments[i][0];
475                 int check_b = bucket->segments[i][1];
476
477                 float *v3 = (float *) feather_points[check_a];
478                 float *v4 = (float *) feather_points[check_b];
479
480                 if (check_a >= cur_a - 1 || cur_b == check_a)
481                         continue;
482
483                 if (isect_seg_seg_v2(v1, v2, v3, v4)) {
484                         int k;
485                         float p[2];
486                         float min_a[2], max_a[2];
487                         float min_b[2], max_b[2];
488
489                         isect_seg_seg_v2_point(v1, v2, v3, v4, p);
490
491                         INIT_MINMAX2(min_a, max_a);
492                         INIT_MINMAX2(min_b, max_b);
493
494                         /* collapse loop with smaller AABB */
495                         for (k = 0; k < tot_feather_point; k++) {
496                                 if (k >= check_b && k <= cur_a) {
497                                         DO_MINMAX2(feather_points[k], min_a, max_a);
498                                 }
499                                 else {
500                                         DO_MINMAX2(feather_points[k], min_b, max_b);
501                                 }
502                         }
503
504                         if (max_a[0] - min_a[0] < max_b[0] - min_b[0] ||
505                             max_a[1] - min_a[1] < max_b[1] - min_b[1])
506                         {
507                                 for (k = check_b; k <= cur_a; k++) {
508                                         copy_v2_v2(feather_points[k], p);
509                                 }
510                         }
511                         else {
512                                 for (k = 0; k <= check_a; k++) {
513                                         copy_v2_v2(feather_points[k], p);
514                                 }
515
516                                 if (cur_b != 0) {
517                                         for (k = cur_b; k < tot_feather_point; k++) {
518                                                 copy_v2_v2(feather_points[k], p);
519                                         }
520                                 }
521                         }
522                 }
523         }
524 }
525
526 static int feather_bucket_index_from_coord(float co[2], const float min[2], const float bucket_scale[2],
527                                            const int buckets_per_side)
528 {
529         int x = (int) ((co[0] - min[0]) * bucket_scale[0]);
530         int y = (int) ((co[1] - min[1]) * bucket_scale[1]);
531
532         if (x == buckets_per_side)
533                 x--;
534
535         if (y == buckets_per_side)
536                 y--;
537
538         return y * buckets_per_side + x;
539 }
540
541 static void feather_bucket_get_diagonal(FeatherEdgesBucket *buckets, int start_bucket_index, int end_bucket_index,
542                                         int buckets_per_side, FeatherEdgesBucket **diagonal_bucket_a_r,
543                                         FeatherEdgesBucket **diagonal_bucket_b_r)
544 {
545         int start_bucket_x = start_bucket_index % buckets_per_side;
546         int start_bucket_y = start_bucket_index / buckets_per_side;
547
548         int end_bucket_x = end_bucket_index % buckets_per_side;
549         int end_bucket_y = end_bucket_index / buckets_per_side;
550
551         int diagonal_bucket_a_index = start_bucket_y * buckets_per_side + end_bucket_x;
552         int diagonal_bucket_b_index = end_bucket_y * buckets_per_side + start_bucket_x;
553
554         *diagonal_bucket_a_r = &buckets[diagonal_bucket_a_index];
555         *diagonal_bucket_b_r = &buckets[diagonal_bucket_b_index];
556 }
557
558 static void spline_feather_collapse_inner_loops(MaskSpline *spline, float (*feather_points)[2], int tot_feather_point)
559 {
560 #define BUCKET_INDEX(co) \
561         feather_bucket_index_from_coord(co, min, bucket_scale, buckets_per_side)
562
563         int buckets_per_side, tot_bucket;
564         float bucket_size, bucket_scale[2];
565
566         FeatherEdgesBucket *buckets;
567
568         int i;
569         float min[2], max[2];
570         float max_delta_x = -1.0f, max_delta_y = -1.0f, max_delta;
571
572         if (tot_feather_point < 4) {
573                 /* self-intersection works only for quads at least,
574                  * in other cases polygon can't be self-intersecting anyway
575                  */
576
577                 return;
578         }
579
580         /* find min/max corners of mask to build buckets in that space */
581         INIT_MINMAX2(min, max);
582
583         for (i = 0; i < tot_feather_point; i++) {
584                 int next = i + 1;
585                 float delta;
586
587                 DO_MINMAX2(feather_points[i], min, max);
588
589                 if (next == tot_feather_point) {
590                         if (spline->flag & MASK_SPLINE_CYCLIC)
591                                 next = 0;
592                         else
593                                 break;
594                 }
595
596                 delta = fabsf(feather_points[i][0] - feather_points[next][0]);
597                 if (delta > max_delta_x)
598                         max_delta_x = delta;
599
600                 delta = fabsf(feather_points[i][1] - feather_points[next][1]);
601                 if (delta > max_delta_y)
602                         max_delta_y = delta;
603         }
604
605         /* prevent divisionsby zero by ensuring bounding box is not collapsed */
606         if (max[0] - min[0] < FLT_EPSILON) {
607                 max[0] += 0.01f;
608                 min[0] -= 0.01f;
609         }
610
611         if (max[1] - min[1] < FLT_EPSILON) {
612                 max[1] += 0.01f;
613                 min[1] -= 0.01f;
614         }
615
616         /* use dynamically calculated buckets per side, so we likely wouldn't
617          * run into a situation when segment doesn't fit two buckets which is
618          * pain collecting candidates for intersection
619          */
620
621         max_delta_x /= max[0] - min[0];
622         max_delta_y /= max[1] - min[1];
623
624         max_delta = MAX2(max_delta_x, max_delta_y);
625
626         buckets_per_side = MIN2(512, 0.9f / max_delta);
627
628         if (buckets_per_side == 0) {
629                 /* happens when some segment fills the whole bounding box across some of dimension */
630
631                 buckets_per_side = 1;
632         }
633
634         tot_bucket = buckets_per_side * buckets_per_side;
635         bucket_size = 1.0f / buckets_per_side;
636
637         /* pre-compute multipliers, to save mathematical operations in loops */
638         bucket_scale[0] = 1.0f / ((max[0] - min[0]) * bucket_size);
639         bucket_scale[1] = 1.0f / ((max[1] - min[1]) * bucket_size);
640
641         /* fill in buckets' edges */
642         buckets = MEM_callocN(sizeof(FeatherEdgesBucket) * tot_bucket, "feather buckets");
643
644         for (i = 0; i < tot_feather_point; i++) {
645                 int start = i, end = i + 1;
646                 int start_bucket_index, end_bucket_index;
647
648                 if (end == tot_feather_point) {
649                         if (spline->flag & MASK_SPLINE_CYCLIC)
650                                 end = 0;
651                         else
652                                 break;
653                 }
654
655                 start_bucket_index = BUCKET_INDEX(feather_points[start]);
656                 end_bucket_index = BUCKET_INDEX(feather_points[end]);
657
658                 feather_bucket_add_edge(&buckets[start_bucket_index], start, end);
659
660                 if (start_bucket_index != end_bucket_index) {
661                         FeatherEdgesBucket *end_bucket = &buckets[end_bucket_index];
662                         FeatherEdgesBucket *diagonal_bucket_a, *diagonal_bucket_b;
663
664                         feather_bucket_get_diagonal(buckets, start_bucket_index, end_bucket_index, buckets_per_side,
665                                                     &diagonal_bucket_a, &diagonal_bucket_b);
666
667                         feather_bucket_add_edge(end_bucket, start, end);
668                         feather_bucket_add_edge(diagonal_bucket_a, start, end);
669                         feather_bucket_add_edge(diagonal_bucket_a, start, end);
670                 }
671         }
672
673         /* check all edges for intersection with edges from their buckets */
674         for (i = 0; i < tot_feather_point; i++) {
675                 int cur_a = i, cur_b = i + 1;
676                 int start_bucket_index, end_bucket_index;
677
678                 FeatherEdgesBucket *start_bucket;
679
680                 if (cur_b == tot_feather_point)
681                         cur_b = 0;
682
683                 start_bucket_index = BUCKET_INDEX(feather_points[cur_a]);
684                 end_bucket_index = BUCKET_INDEX(feather_points[cur_b]);
685
686                 start_bucket = &buckets[start_bucket_index];
687
688                 feather_bucket_check_intersect(feather_points, tot_feather_point, start_bucket, cur_a, cur_b);
689
690                 if (start_bucket_index != end_bucket_index) {
691                         FeatherEdgesBucket *end_bucket = &buckets[end_bucket_index];
692                         FeatherEdgesBucket *diagonal_bucket_a, *diagonal_bucket_b;
693
694                         feather_bucket_get_diagonal(buckets, start_bucket_index, end_bucket_index, buckets_per_side,
695                                                     &diagonal_bucket_a, &diagonal_bucket_b);
696
697                         feather_bucket_check_intersect(feather_points, tot_feather_point, end_bucket, cur_a, cur_b);
698                         feather_bucket_check_intersect(feather_points, tot_feather_point, diagonal_bucket_a, cur_a, cur_b);
699                         feather_bucket_check_intersect(feather_points, tot_feather_point, diagonal_bucket_b, cur_a, cur_b);
700                 }
701         }
702
703         /* free buckets */
704         for (i = 0; i < tot_bucket; i++) {
705                 if (buckets[i].segments)
706                         MEM_freeN(buckets[i].segments);
707         }
708
709         MEM_freeN(buckets);
710
711 #undef BUCKET_INDEX
712 }
713
714 /**
715  * values align with #BKE_mask_spline_differentiate_with_resolution_ex
716  * when \a resol arguments match.
717  */
718 float (*BKE_mask_spline_feather_differentiated_points_with_resolution_ex(MaskSpline *spline,
719                                                                          int *tot_feather_point,
720                                                                          const unsigned int resol
721                                                                          ))[2]
722 {
723         MaskSplinePoint *points_array = BKE_mask_spline_point_array(spline);
724         MaskSplinePoint *point, *prev;
725         float (*feather)[2], (*fp)[2];
726
727         const int tot = BKE_mask_spline_differentiate_calc_total(spline, resol);
728         int a;
729
730         /* tot+1 because of 'forward_diff_bezier' function */
731         feather = fp = MEM_mallocN((tot + 1) * sizeof(*feather), "mask spline feather diff points");
732
733         a = spline->tot_point - 1;
734         if (spline->flag & MASK_SPLINE_CYCLIC)
735                 a++;
736
737         prev = points_array;
738         point = prev + 1;
739
740         while (a--) {
741                 /* BezTriple *prevbezt; */  /* UNUSED */
742                 /* BezTriple *bezt; */      /* UNUSED */
743                 int j;
744
745                 if (a == 0 && (spline->flag & MASK_SPLINE_CYCLIC))
746                         point = points_array;
747
748
749                 /* prevbezt = &prev->bezt; */
750                 /* bezt = &point->bezt; */
751
752                 for (j = 0; j < resol; j++, fp++) {
753                         float u = (float) j / resol, weight;
754                         float co[2], n[2];
755
756                         /* TODO - these calls all calculate similar things
757                          * could be unified for some speed */
758                         BKE_mask_point_segment_co(spline, prev, u, co);
759                         BKE_mask_point_normal(spline, prev, u, n);
760                         weight = BKE_mask_point_weight(spline, prev, u);
761
762                         madd_v2_v2v2fl(*fp, co, n, weight);
763                 }
764
765                 if (a == 0 && (spline->flag & MASK_SPLINE_CYCLIC) == 0) {
766                         float u = 1.0f, weight;
767                         float co[2], n[2];
768
769                         BKE_mask_point_segment_co(spline, prev, u, co);
770                         BKE_mask_point_normal(spline, prev, u, n);
771                         weight = BKE_mask_point_weight(spline, prev, u);
772
773                         madd_v2_v2v2fl(*fp, co, n, weight);
774                 }
775
776                 prev = point;
777                 point++;
778         }
779
780         *tot_feather_point = tot;
781
782         if (spline->flag & MASK_SPLINE_NOINTERSECT)
783                 spline_feather_collapse_inner_loops(spline, feather, tot);
784
785         return feather;
786 }
787
788 float (*BKE_mask_spline_feather_differentiated_points_with_resolution(MaskSpline *spline, int width, int height,
789                                                                       int *tot_feather_point))[2]
790 {
791         unsigned int resol = BKE_mask_spline_feather_resolution(spline, width, height);
792
793         return BKE_mask_spline_feather_differentiated_points_with_resolution_ex(spline, tot_feather_point, resol);
794 }
795
796 float (*BKE_mask_spline_feather_differentiated_points(MaskSpline *spline, int *tot_feather_point))[2]
797 {
798         return BKE_mask_spline_feather_differentiated_points_with_resolution(spline, 0, 0, tot_feather_point);
799 }
800
801 float (*BKE_mask_spline_feather_points(MaskSpline *spline, int *tot_feather_point))[2]
802 {
803         MaskSplinePoint *points_array = BKE_mask_spline_point_array(spline);
804
805         int i, tot = 0;
806         float (*feather)[2], (*fp)[2];
807
808         /* count */
809         for (i = 0; i < spline->tot_point; i++) {
810                 MaskSplinePoint *point = &points_array[i];
811
812                 tot += point->tot_uw + 1;
813         }
814
815         /* create data */
816         feather = fp = MEM_mallocN(tot * sizeof(*feather), "mask spline feather points");
817
818         for (i = 0; i < spline->tot_point; i++) {
819                 MaskSplinePoint *point = &points_array[i];
820                 BezTriple *bezt = &point->bezt;
821                 float weight, n[2];
822                 int j;
823
824                 BKE_mask_point_normal(spline, point, 0.0f, n);
825                 weight = BKE_mask_point_weight(spline, point, 0.0f);
826
827                 madd_v2_v2v2fl(*fp, bezt->vec[1], n, weight);
828                 fp++;
829
830                 for (j = 0; j < point->tot_uw; j++) {
831                         float u = point->uw[j].u;
832                         float co[2];
833
834                         BKE_mask_point_segment_co(spline, point, u, co);
835                         BKE_mask_point_normal(spline, point, u, n);
836                         weight = BKE_mask_point_weight(spline, point, u);
837
838                         madd_v2_v2v2fl(*fp, co, n, weight);
839                         fp++;
840                 }
841         }
842
843         *tot_feather_point = tot;
844
845         return feather;
846 }
847
848 void BKE_mask_point_direction_switch(MaskSplinePoint *point)
849 {
850         const int tot_uw = point->tot_uw;
851         const int tot_uw_half = tot_uw / 2;
852         int i;
853
854         float co_tmp[2];
855
856         /* swap handles */
857         copy_v2_v2(co_tmp, point->bezt.vec[0]);
858         copy_v2_v2(point->bezt.vec[0], point->bezt.vec[2]);
859         copy_v2_v2(point->bezt.vec[2], co_tmp);
860         /* in this case the flags are unlikely to be different but swap anyway */
861         SWAP(char, point->bezt.f1, point->bezt.f3);
862         SWAP(char, point->bezt.h1, point->bezt.h2);
863
864
865         /* swap UW's */
866         if (tot_uw > 1) {
867                 /* count */
868                 for (i = 0; i < tot_uw_half; i++) {
869                         MaskSplinePointUW *uw_a = &point->uw[i];
870                         MaskSplinePointUW *uw_b = &point->uw[tot_uw - (i + 1)];
871                         SWAP(MaskSplinePointUW, *uw_a, *uw_b);
872                 }
873         }
874
875         for (i = 0; i < tot_uw; i++) {
876                 MaskSplinePointUW *uw = &point->uw[i];
877                 uw->u = 1.0f - uw->u;
878         }
879 }
880
881 void BKE_mask_spline_direction_switch(MaskLayer *masklay, MaskSpline *spline)
882 {
883         const int tot_point = spline->tot_point;
884         const int tot_point_half = tot_point / 2;
885         int i, i_prev;
886
887         if (tot_point < 2) {
888                 return;
889         }
890
891         /* count */
892         for (i = 0; i < tot_point_half; i++) {
893                 MaskSplinePoint *point_a = &spline->points[i];
894                 MaskSplinePoint *point_b = &spline->points[tot_point - (i + 1)];
895                 SWAP(MaskSplinePoint, *point_a, *point_b);
896         }
897
898         /* correct UW's */
899         i_prev = tot_point - 1;
900         for (i = 0; i < tot_point; i++) {
901
902                 BKE_mask_point_direction_switch(&spline->points[i]);
903
904                 SWAP(MaskSplinePointUW *, spline->points[i].uw,     spline->points[i_prev].uw);
905                 SWAP(int,                 spline->points[i].tot_uw, spline->points[i_prev].tot_uw);
906
907                 i_prev = i;
908         }
909
910         /* correct animation */
911         if (masklay->splines_shapes.first) {
912                 MaskLayerShape *masklay_shape;
913
914                 const int spline_index = BKE_mask_layer_shape_spline_to_index(masklay, spline);
915
916                 for (masklay_shape = masklay->splines_shapes.first;
917                      masklay_shape;
918                      masklay_shape = masklay_shape->next)
919                 {
920                         MaskLayerShapeElem *fp_arr = (MaskLayerShapeElem *)masklay_shape->data;
921
922                         for (i = 0; i < tot_point_half; i++) {
923                                 MaskLayerShapeElem *fp_a = &fp_arr[spline_index +              (i)     ];
924                                 MaskLayerShapeElem *fp_b = &fp_arr[spline_index + (tot_point - (i + 1))];
925                                 SWAP(MaskLayerShapeElem, *fp_a, *fp_b);
926                         }
927                 }
928         }
929 }
930
931
932 float BKE_mask_spline_project_co(MaskSpline *spline, MaskSplinePoint *point,
933                                  float start_u, const float co[2], const eMaskSign sign)
934 {
935         const float proj_eps         = 1e-3;
936         const float proj_eps_squared = proj_eps * proj_eps;
937         const int N = 1000;
938         float u = -1.0f, du = 1.0f / N, u1 = start_u, u2 = start_u;
939         float ang = -1.0f;
940
941         BLI_assert(ABS(sign) <= 1); /* (-1, 0, 1) */
942
943         while (u1 > 0.0f || u2 < 1.0f) {
944                 float n1[2], n2[2], co1[2], co2[2];
945                 float v1[2], v2[2];
946                 float ang1, ang2;
947
948                 if (u1 >= 0.0f) {
949                         BKE_mask_point_segment_co(spline, point, u1, co1);
950                         BKE_mask_point_normal(spline, point, u1, n1);
951                         sub_v2_v2v2(v1, co, co1);
952
953                         if ((sign == MASK_PROJ_ANY) ||
954                             ((sign == MASK_PROJ_NEG) && (dot_v2v2(v1, n1) <= 0.0f)) ||
955                             ((sign == MASK_PROJ_POS) && (dot_v2v2(v1, n1) >= 0.0f)))
956                         {
957
958                                 if (len_squared_v2(v1) > proj_eps_squared) {
959                                         ang1 = angle_v2v2(v1, n1);
960                                         if (ang1 > M_PI / 2.0f)
961                                                 ang1 = M_PI  - ang1;
962
963                                         if (ang < 0.0f || ang1 < ang) {
964                                                 ang = ang1;
965                                                 u = u1;
966                                         }
967                                 }
968                                 else {
969                                         u = u1;
970                                         break;
971                                 }
972                         }
973                 }
974
975                 if (u2 <= 1.0f) {
976                         BKE_mask_point_segment_co(spline, point, u2, co2);
977                         BKE_mask_point_normal(spline, point, u2, n2);
978                         sub_v2_v2v2(v2, co, co2);
979
980                         if ((sign == MASK_PROJ_ANY) ||
981                             ((sign == MASK_PROJ_NEG) && (dot_v2v2(v2, n2) <= 0.0f)) ||
982                             ((sign == MASK_PROJ_POS) && (dot_v2v2(v2, n2) >= 0.0f)))
983                         {
984
985                                 if (len_squared_v2(v2) > proj_eps_squared) {
986                                         ang2 = angle_v2v2(v2, n2);
987                                         if (ang2 > M_PI / 2.0f)
988                                                 ang2 = M_PI  - ang2;
989
990                                         if (ang2 < ang) {
991                                                 ang = ang2;
992                                                 u = u2;
993                                         }
994                                 }
995                                 else {
996                                         u = u2;
997                                         break;
998                                 }
999                         }
1000                 }
1001
1002                 u1 -= du;
1003                 u2 += du;
1004         }
1005
1006         return u;
1007 }
1008
1009 /* point */
1010
1011 int BKE_mask_point_has_handle(MaskSplinePoint *point)
1012 {
1013         BezTriple *bezt = &point->bezt;
1014
1015         return bezt->h1 == HD_ALIGN;
1016 }
1017
1018 void BKE_mask_point_handle(MaskSplinePoint *point, float handle[2])
1019 {
1020         float vec[2];
1021
1022         sub_v2_v2v2(vec, point->bezt.vec[0], point->bezt.vec[1]);
1023
1024         handle[0] = (point->bezt.vec[1][0] + vec[1]);
1025         handle[1] = (point->bezt.vec[1][1] - vec[0]);
1026 }
1027
1028 void BKE_mask_point_set_handle(MaskSplinePoint *point, float loc[2], int keep_direction,
1029                                float orig_handle[2], float orig_vec[3][3])
1030 {
1031         BezTriple *bezt = &point->bezt;
1032         float v1[2], v2[2], vec[2];
1033
1034         if (keep_direction) {
1035                 sub_v2_v2v2(v1, loc, orig_vec[1]);
1036                 sub_v2_v2v2(v2, orig_handle, orig_vec[1]);
1037
1038                 project_v2_v2v2(vec, v1, v2);
1039
1040                 if (dot_v2v2(v2, vec) > 0) {
1041                         float len = len_v2(vec);
1042
1043                         sub_v2_v2v2(v1, orig_vec[0], orig_vec[1]);
1044
1045                         mul_v2_fl(v1, len / len_v2(v1));
1046
1047                         add_v2_v2v2(bezt->vec[0], bezt->vec[1], v1);
1048                         sub_v2_v2v2(bezt->vec[2], bezt->vec[1], v1);
1049                 }
1050                 else {
1051                         copy_v3_v3(bezt->vec[0], bezt->vec[1]);
1052                         copy_v3_v3(bezt->vec[2], bezt->vec[1]);
1053                 }
1054         }
1055         else {
1056                 sub_v2_v2v2(v1, loc, bezt->vec[1]);
1057
1058                 v2[0] = -v1[1];
1059                 v2[1] =  v1[0];
1060
1061                 add_v2_v2v2(bezt->vec[0], bezt->vec[1], v2);
1062                 sub_v2_v2v2(bezt->vec[2], bezt->vec[1], v2);
1063         }
1064 }
1065
1066 float *BKE_mask_point_segment_feather_diff_with_resolution(MaskSpline *spline, MaskSplinePoint *point,
1067                                                            int width, int height,
1068                                                            unsigned int *tot_feather_point)
1069 {
1070         float *feather, *fp;
1071         unsigned int resol = BKE_mask_spline_feather_resolution(spline, width, height);
1072         unsigned int i;
1073
1074         feather = fp = MEM_callocN(2 * resol * sizeof(float), "mask point spline feather diff points");
1075
1076         for (i = 0; i < resol; i++, fp += 2) {
1077                 float u = (float)(i % resol) / resol, weight;
1078                 float co[2], n[2];
1079
1080                 BKE_mask_point_segment_co(spline, point, u, co);
1081                 BKE_mask_point_normal(spline, point, u, n);
1082                 weight = BKE_mask_point_weight(spline, point, u);
1083
1084                 fp[0] = co[0] + n[0] * weight;
1085                 fp[1] = co[1] + n[1] * weight;
1086         }
1087
1088         *tot_feather_point = resol;
1089
1090         return feather;
1091 }
1092
1093 float *BKE_mask_point_segment_feather_diff(MaskSpline *spline, MaskSplinePoint *point, unsigned int *tot_feather_point)
1094 {
1095         return BKE_mask_point_segment_feather_diff_with_resolution(spline, point, 0, 0, tot_feather_point);
1096 }
1097
1098 float *BKE_mask_point_segment_diff_with_resolution(MaskSpline *spline, MaskSplinePoint *point,
1099                                                    int width, int height, unsigned int *tot_diff_point)
1100 {
1101         MaskSplinePoint *points_array = BKE_mask_spline_point_array_from_point(spline, point);
1102
1103         BezTriple *bezt, *bezt_next;
1104         float *diff_points, *fp;
1105         int j, resol = BKE_mask_spline_resolution(spline, width, height);
1106
1107         bezt = &point->bezt;
1108         bezt_next = mask_spline_point_next_bezt(spline, points_array, point);
1109
1110         if (!bezt_next)
1111                 return NULL;
1112
1113         /* resol+1 because of 'forward_diff_bezier' function */
1114         *tot_diff_point = resol + 1;
1115         diff_points = fp = MEM_callocN((resol + 1) * 2 * sizeof(float), "mask segment vets");
1116
1117         for (j = 0; j < 2; j++) {
1118                 BKE_curve_forward_diff_bezier(bezt->vec[1][j], bezt->vec[2][j],
1119                                               bezt_next->vec[0][j], bezt_next->vec[1][j],
1120                                               fp + j, resol, 2 * sizeof(float));
1121         }
1122
1123         copy_v2_v2(fp + 2 * resol, bezt_next->vec[1]);
1124
1125         return diff_points;
1126 }
1127
1128 float *BKE_mask_point_segment_diff(MaskSpline *spline, MaskSplinePoint *point, unsigned int *tot_diff_point)
1129 {
1130         return BKE_mask_point_segment_diff_with_resolution(spline, point, 0, 0, tot_diff_point);
1131 }
1132
1133 void BKE_mask_point_segment_co(MaskSpline *spline, MaskSplinePoint *point, float u, float co[2])
1134 {
1135         MaskSplinePoint *points_array = BKE_mask_spline_point_array_from_point(spline, point);
1136
1137         BezTriple *bezt = &point->bezt, *bezt_next;
1138         float q0[2], q1[2], q2[2], r0[2], r1[2];
1139
1140         bezt_next = mask_spline_point_next_bezt(spline, points_array, point);
1141
1142         if (!bezt_next) {
1143                 copy_v2_v2(co, bezt->vec[1]);
1144                 return;
1145         }
1146
1147         interp_v2_v2v2(q0, bezt->vec[1], bezt->vec[2], u);
1148         interp_v2_v2v2(q1, bezt->vec[2], bezt_next->vec[0], u);
1149         interp_v2_v2v2(q2, bezt_next->vec[0], bezt_next->vec[1], u);
1150
1151         interp_v2_v2v2(r0, q0, q1, u);
1152         interp_v2_v2v2(r1, q1, q2, u);
1153
1154         interp_v2_v2v2(co, r0, r1, u);
1155 }
1156
1157 void BKE_mask_point_normal(MaskSpline *spline, MaskSplinePoint *point, float u, float n[2])
1158 {
1159         MaskSplinePoint *points_array = BKE_mask_spline_point_array_from_point(spline, point);
1160
1161         BezTriple *bezt = &point->bezt, *bezt_next;
1162         float q0[2], q1[2], q2[2], r0[2], r1[2], vec[2];
1163
1164         bezt_next = mask_spline_point_next_bezt(spline, points_array, point);
1165
1166         if (!bezt_next) {
1167                 BKE_mask_point_handle(point, vec);
1168
1169                 sub_v2_v2v2(n, vec, bezt->vec[1]);
1170                 normalize_v2(n);
1171                 return;
1172         }
1173
1174         interp_v2_v2v2(q0, bezt->vec[1], bezt->vec[2], u);
1175         interp_v2_v2v2(q1, bezt->vec[2], bezt_next->vec[0], u);
1176         interp_v2_v2v2(q2, bezt_next->vec[0], bezt_next->vec[1], u);
1177
1178         interp_v2_v2v2(r0, q0, q1, u);
1179         interp_v2_v2v2(r1, q1, q2, u);
1180
1181         sub_v2_v2v2(vec, r1, r0);
1182
1183         n[0] = -vec[1];
1184         n[1] =  vec[0];
1185
1186         normalize_v2(n);
1187 }
1188
1189 static float mask_point_interp_weight(BezTriple *bezt, BezTriple *bezt_next, const float u)
1190 {
1191         return (bezt->weight * (1.0f - u)) + (bezt_next->weight * u);
1192 }
1193
1194 float BKE_mask_point_weight_scalar(MaskSpline *spline, MaskSplinePoint *point, const float u)
1195 {
1196         MaskSplinePoint *points_array = BKE_mask_spline_point_array_from_point(spline, point);
1197         BezTriple *bezt = &point->bezt, *bezt_next;
1198
1199         bezt_next = mask_spline_point_next_bezt(spline, points_array, point);
1200
1201         if (!bezt_next) {
1202                 return bezt->weight;
1203         }
1204         else if (u <= 0.0) {
1205                 return bezt->weight;
1206         }
1207         else if (u >= 1.0f) {
1208                 return bezt_next->weight;
1209         }
1210         else {
1211                 return mask_point_interp_weight(bezt, bezt_next, u);
1212         }
1213 }
1214
1215 float BKE_mask_point_weight(MaskSpline *spline, MaskSplinePoint *point, const float u)
1216 {
1217         MaskSplinePoint *points_array = BKE_mask_spline_point_array_from_point(spline, point);
1218         BezTriple *bezt = &point->bezt, *bezt_next;
1219
1220         bezt_next = mask_spline_point_next_bezt(spline, points_array, point);
1221
1222         if (!bezt_next) {
1223                 return bezt->weight;
1224         }
1225         else if (u <= 0.0) {
1226                 return bezt->weight;
1227         }
1228         else if (u >= 1.0f) {
1229                 return bezt_next->weight;
1230         }
1231         else {
1232                 float cur_u = 0.0f, cur_w = 0.0f, next_u = 0.0f, next_w = 0.0f, fac; /* Quite warnings */
1233                 int i;
1234
1235                 for (i = 0; i < point->tot_uw + 1; i++) {
1236
1237                         if (i == 0) {
1238                                 cur_u = 0.0f;
1239                                 cur_w = 1.0f; /* mask_point_interp_weight will scale it */
1240                         }
1241                         else {
1242                                 cur_u = point->uw[i - 1].u;
1243                                 cur_w = point->uw[i - 1].w;
1244                         }
1245
1246                         if (i == point->tot_uw) {
1247                                 next_u = 1.0f;
1248                                 next_w = 1.0f; /* mask_point_interp_weight will scale it */
1249                         }
1250                         else {
1251                                 next_u = point->uw[i].u;
1252                                 next_w = point->uw[i].w;
1253                         }
1254
1255                         if (u >= cur_u && u <= next_u) {
1256                                 break;
1257                         }
1258                 }
1259
1260                 fac = (u - cur_u) / (next_u - cur_u);
1261
1262                 cur_w  *= mask_point_interp_weight(bezt, bezt_next, cur_u);
1263                 next_w *= mask_point_interp_weight(bezt, bezt_next, next_u);
1264
1265                 if (spline->weight_interp == MASK_SPLINE_INTERP_EASE) {
1266                         return cur_w + (next_w - cur_w) * (3.0f * fac * fac - 2.0f * fac * fac * fac);
1267                 }
1268                 else {
1269                         return (1.0f - fac) * cur_w + fac * next_w;
1270                 }
1271         }
1272 }
1273
1274 MaskSplinePointUW *BKE_mask_point_sort_uw(MaskSplinePoint *point, MaskSplinePointUW *uw)
1275 {
1276         if (point->tot_uw > 1) {
1277                 int idx = uw - point->uw;
1278
1279                 if (idx > 0 && point->uw[idx - 1].u > uw->u) {
1280                         while (idx > 0 && point->uw[idx - 1].u > point->uw[idx].u) {
1281                                 SWAP(MaskSplinePointUW, point->uw[idx - 1], point->uw[idx]);
1282                                 idx--;
1283                         }
1284                 }
1285
1286                 if (idx < point->tot_uw - 1 && point->uw[idx + 1].u < uw->u) {
1287                         while (idx < point->tot_uw - 1 && point->uw[idx + 1].u < point->uw[idx].u) {
1288                                 SWAP(MaskSplinePointUW, point->uw[idx + 1], point->uw[idx]);
1289                                 idx++;
1290                         }
1291                 }
1292
1293                 return &point->uw[idx];
1294         }
1295
1296         return uw;
1297 }
1298
1299 void BKE_mask_point_add_uw(MaskSplinePoint *point, float u, float w)
1300 {
1301         if (!point->uw)
1302                 point->uw = MEM_mallocN(sizeof(*point->uw), "mask point uw");
1303         else
1304                 point->uw = MEM_reallocN(point->uw, (point->tot_uw + 1) * sizeof(*point->uw));
1305
1306         point->uw[point->tot_uw].u = u;
1307         point->uw[point->tot_uw].w = w;
1308         point->uw[point->tot_uw].flag = 0;
1309
1310         point->tot_uw++;
1311
1312         BKE_mask_point_sort_uw(point, &point->uw[point->tot_uw - 1]);
1313 }
1314
1315 void BKE_mask_point_select_set(MaskSplinePoint *point, const short do_select)
1316 {
1317         int i;
1318
1319         if (do_select) {
1320                 MASKPOINT_SEL_ALL(point);
1321         }
1322         else {
1323                 MASKPOINT_DESEL_ALL(point);
1324         }
1325
1326         for (i = 0; i < point->tot_uw; i++) {
1327                 if (do_select) {
1328                         point->uw[i].flag |= SELECT;
1329                 }
1330                 else {
1331                         point->uw[i].flag &= ~SELECT;
1332                 }
1333         }
1334 }
1335
1336 void BKE_mask_point_select_set_handle(MaskSplinePoint *point, const short do_select)
1337 {
1338         if (do_select) {
1339                 MASKPOINT_SEL_HANDLE(point);
1340         }
1341         else {
1342                 MASKPOINT_DESEL_HANDLE(point);
1343         }
1344 }
1345
1346 /* only mask block itself */
1347 static Mask *mask_alloc(const char *name)
1348 {
1349         Mask *mask;
1350
1351         mask = BKE_libblock_alloc(&G.main->mask, ID_MSK, name);
1352
1353         mask->id.flag |= LIB_FAKEUSER;
1354
1355         return mask;
1356 }
1357
1358 Mask *BKE_mask_new(const char *name)
1359 {
1360         Mask *mask;
1361         char mask_name[MAX_ID_NAME - 2];
1362
1363         if (name && name[0])
1364                 BLI_strncpy(mask_name, name, sizeof(mask_name));
1365         else
1366                 strcpy(mask_name, "Mask");
1367
1368         mask = mask_alloc(mask_name);
1369
1370         /* arbitrary defaults */
1371         mask->sfra = 1;
1372         mask->efra = 100;
1373
1374         return mask;
1375 }
1376
1377 Mask *BKE_mask_copy_nolib(Mask *mask)
1378 {
1379         Mask *mask_new;
1380
1381         mask_new = MEM_dupallocN(mask);
1382
1383         /*take care here! - we may want to copy anim data  */
1384         mask_new->adt = NULL;
1385
1386         mask_new->masklayers.first = NULL;
1387         mask_new->masklayers.last = NULL;
1388
1389         BKE_mask_layer_copy_list(&mask_new->masklayers, &mask->masklayers);
1390
1391         /* enable fake user by default */
1392         if (!(mask_new->id.flag & LIB_FAKEUSER)) {
1393                 mask_new->id.flag |= LIB_FAKEUSER;
1394                 mask_new->id.us++;
1395         }
1396
1397         return mask_new;
1398 }
1399
1400 Mask *BKE_mask_copy(Mask *mask)
1401 {
1402         Mask *mask_new;
1403
1404         mask_new = BKE_libblock_copy(&mask->id);
1405
1406         mask_new->masklayers.first = NULL;
1407         mask_new->masklayers.last = NULL;
1408
1409         BKE_mask_layer_copy_list(&mask_new->masklayers, &mask->masklayers);
1410
1411         /* enable fake user by default */
1412         if (!(mask_new->id.flag & LIB_FAKEUSER)) {
1413                 mask_new->id.flag |= LIB_FAKEUSER;
1414                 mask_new->id.us++;
1415         }
1416
1417         return mask_new;
1418 }
1419
1420 void BKE_mask_point_free(MaskSplinePoint *point)
1421 {
1422         if (point->uw)
1423                 MEM_freeN(point->uw);
1424 }
1425
1426 void BKE_mask_spline_free(MaskSpline *spline)
1427 {
1428         int i = 0;
1429
1430         for (i = 0; i < spline->tot_point; i++) {
1431                 MaskSplinePoint *point;
1432                 point = &spline->points[i];
1433                 BKE_mask_point_free(point);
1434
1435                 if (spline->points_deform) {
1436                         point = &spline->points_deform[i];
1437                         BKE_mask_point_free(point);
1438                 }
1439         }
1440
1441         MEM_freeN(spline->points);
1442
1443         if (spline->points_deform) {
1444                 MEM_freeN(spline->points_deform);
1445         }
1446
1447         MEM_freeN(spline);
1448 }
1449
1450 static MaskSplinePoint *mask_spline_points_copy(MaskSplinePoint *points, int tot_point)
1451 {
1452         MaskSplinePoint *npoints;
1453         int i;
1454
1455         npoints = MEM_dupallocN(points);
1456
1457         for (i = 0; i < tot_point; i++) {
1458                 MaskSplinePoint *point = &npoints[i];
1459
1460                 if (point->uw)
1461                         point->uw = MEM_dupallocN(point->uw);
1462         }
1463
1464         return npoints;
1465 }
1466
1467 MaskSpline *BKE_mask_spline_copy(MaskSpline *spline)
1468 {
1469         MaskSpline *nspline = MEM_callocN(sizeof(MaskSpline), "new spline");
1470
1471         *nspline = *spline;
1472
1473         nspline->points_deform = NULL;
1474         nspline->points = mask_spline_points_copy(spline->points, spline->tot_point);
1475
1476         if (spline->points_deform) {
1477                 nspline->points_deform = mask_spline_points_copy(spline->points_deform, spline->tot_point);
1478         }
1479
1480         return nspline;
1481 }
1482
1483 /* note: does NOT add to the list */
1484 MaskLayerShape *BKE_mask_layer_shape_alloc(MaskLayer *masklay, const int frame)
1485 {
1486         MaskLayerShape *masklay_shape;
1487         int tot_vert = BKE_mask_layer_shape_totvert(masklay);
1488
1489         masklay_shape = MEM_mallocN(sizeof(MaskLayerShape), __func__);
1490         masklay_shape->frame = frame;
1491         masklay_shape->tot_vert = tot_vert;
1492         masklay_shape->data = MEM_mallocN(tot_vert * sizeof(float) * MASK_OBJECT_SHAPE_ELEM_SIZE, __func__);
1493
1494         return masklay_shape;
1495 }
1496
1497 void BKE_mask_layer_shape_free(MaskLayerShape *masklay_shape)
1498 {
1499         if (masklay_shape->data) {
1500                 MEM_freeN(masklay_shape->data);
1501         }
1502
1503         MEM_freeN(masklay_shape);
1504 }
1505
1506 /** \brief Free all animation keys for a mask layer
1507  */
1508 void BKE_mask_layer_free_shapes(MaskLayer *masklay)
1509 {
1510         MaskLayerShape *masklay_shape;
1511
1512         /* free animation data */
1513         masklay_shape = masklay->splines_shapes.first;
1514         while (masklay_shape) {
1515                 MaskLayerShape *next_masklay_shape = masklay_shape->next;
1516
1517                 BLI_remlink(&masklay->splines_shapes, masklay_shape);
1518                 BKE_mask_layer_shape_free(masklay_shape);
1519
1520                 masklay_shape = next_masklay_shape;
1521         }
1522 }
1523
1524 void BKE_mask_layer_free(MaskLayer *masklay)
1525 {
1526         MaskSpline *spline;
1527
1528         /* free splines */
1529         spline = masklay->splines.first;
1530         while (spline) {
1531                 MaskSpline *next_spline = spline->next;
1532
1533                 BLI_remlink(&masklay->splines, spline);
1534                 BKE_mask_spline_free(spline);
1535
1536                 spline = next_spline;
1537         }
1538
1539         /* free animation data */
1540         BKE_mask_layer_free_shapes(masklay);
1541
1542         MEM_freeN(masklay);
1543 }
1544
1545 void BKE_mask_layer_free_list(ListBase *masklayers)
1546 {
1547         MaskLayer *masklay = masklayers->first;
1548
1549         while (masklay) {
1550                 MaskLayer *masklay_next = masklay->next;
1551
1552                 BLI_remlink(masklayers, masklay);
1553                 BKE_mask_layer_free(masklay);
1554
1555                 masklay = masklay_next;
1556         }
1557 }
1558
1559 void BKE_mask_free(Mask *mask)
1560 {
1561         BKE_mask_layer_free_list(&mask->masklayers);
1562 }
1563
1564 void BKE_mask_unlink(Main *bmain, Mask *mask)
1565 {
1566         bScreen *scr;
1567         ScrArea *area;
1568         SpaceLink *sl;
1569
1570         for (scr = bmain->screen.first; scr; scr = scr->id.next) {
1571                 for (area = scr->areabase.first; area; area = area->next) {
1572                         for (sl = area->spacedata.first; sl; sl = sl->next) {
1573                                 if (sl->spacetype == SPACE_CLIP) {
1574                                         SpaceClip *sc = (SpaceClip *) sl;
1575
1576                                         if (sc->mask_info.mask == mask)
1577                                                 sc->mask_info.mask = NULL;
1578                                 }
1579                         }
1580                 }
1581         }
1582
1583         mask->id.us = 0;
1584 }
1585
1586 void BKE_mask_coord_from_frame(float r_co[2], const float co[2], const float frame_size[2])
1587 {
1588         if (frame_size[0] == frame_size[1]) {
1589                 r_co[0] = co[0];
1590                 r_co[1] = co[1];
1591         }
1592         else if (frame_size[0] < frame_size[1]) {
1593                 r_co[0] = ((co[0] - 0.5f) * (frame_size[0] / frame_size[1])) + 0.5f;
1594                 r_co[1] = co[1];
1595         }
1596         else { /* (frame_size[0] > frame_size[1]) */
1597                 r_co[0] = co[0];
1598                 r_co[1] = ((co[1] - 0.5f) * (frame_size[1] / frame_size[0])) + 0.5f;
1599         }
1600 }
1601 void BKE_mask_coord_from_movieclip(MovieClip *clip, MovieClipUser *user, float r_co[2], const float co[2])
1602 {
1603         int width, height;
1604         float frame_size[2];
1605
1606         /* scaling for the clip */
1607         BKE_movieclip_get_size(clip, user, &width, &height);
1608
1609         frame_size[0] = (float)width;
1610         frame_size[1] = (float)height;
1611
1612         BKE_mask_coord_from_frame(r_co, co, frame_size);
1613 }
1614
1615 /* as above but divide */
1616 void BKE_mask_coord_to_frame(float r_co[2], const float co[2], const float frame_size[2])
1617 {
1618         if (frame_size[0] == frame_size[1]) {
1619                 r_co[0] = co[0];
1620                 r_co[1] = co[1];
1621         }
1622         else if (frame_size[0] < frame_size[1]) {
1623                 r_co[0] = ((co[0] - 0.5f) / (frame_size[0] / frame_size[1])) + 0.5f;
1624                 r_co[1] = co[1];
1625         }
1626         else { /* (frame_size[0] > frame_size[1]) */
1627                 r_co[0] = co[0];
1628                 r_co[1] = ((co[1] - 0.5f) / (frame_size[1] / frame_size[0])) + 0.5f;
1629         }
1630 }
1631 void BKE_mask_coord_to_movieclip(MovieClip *clip, MovieClipUser *user, float r_co[2], const float co[2])
1632 {
1633         int width, height;
1634         float frame_size[2];
1635
1636         /* scaling for the clip */
1637         BKE_movieclip_get_size(clip, user, &width, &height);
1638
1639         frame_size[0] = (float)width;
1640         frame_size[1] = (float)height;
1641
1642         BKE_mask_coord_to_frame(r_co, co, frame_size);
1643 }
1644
1645 static int BKE_mask_evaluate_parent(MaskParent *parent, float ctime, float r_co[2])
1646 {
1647         if (!parent)
1648                 return FALSE;
1649
1650         if (parent->id_type == ID_MC) {
1651                 if (parent->id) {
1652                         MovieClip *clip = (MovieClip *) parent->id;
1653                         MovieTracking *tracking = (MovieTracking *) &clip->tracking;
1654                         MovieTrackingObject *ob = BKE_tracking_object_get_named(tracking, parent->parent);
1655
1656                         if (ob) {
1657                                 MovieTrackingTrack *track = BKE_tracking_track_get_named(tracking, ob, parent->sub_parent);
1658                                 float clip_framenr = BKE_movieclip_remap_scene_to_clip_frame(clip, ctime);
1659
1660                                 MovieClipUser user = {0};
1661                                 user.framenr = ctime;
1662
1663                                 if (track) {
1664                                         float marker_pos_ofs[2];
1665                                         BKE_tracking_marker_get_subframe_position(track, clip_framenr, marker_pos_ofs);
1666                                         BKE_mask_coord_from_movieclip(clip, &user, r_co, marker_pos_ofs);
1667
1668                                         return TRUE;
1669                                 }
1670                         }
1671                 }
1672         }
1673
1674         return FALSE;
1675 }
1676
1677 int BKE_mask_evaluate_parent_delta(MaskParent *parent, float ctime, float r_delta[2])
1678 {
1679         float parent_co[2];
1680
1681         if (BKE_mask_evaluate_parent(parent, ctime, parent_co)) {
1682                 sub_v2_v2v2(r_delta, parent_co, parent->parent_orig);
1683                 return TRUE;
1684         }
1685         else {
1686                 return FALSE;
1687         }
1688 }
1689
1690 static void mask_calc_point_handle(MaskSplinePoint *point, MaskSplinePoint *point_prev, MaskSplinePoint *point_next)
1691 {
1692         BezTriple *bezt = &point->bezt;
1693         BezTriple *bezt_prev = NULL, *bezt_next = NULL;
1694         //int handle_type = bezt->h1;
1695
1696         if (point_prev)
1697                 bezt_prev = &point_prev->bezt;
1698
1699         if (point_next)
1700                 bezt_next = &point_next->bezt;
1701
1702 #if 1
1703         if (bezt_prev || bezt_next) {
1704                 BKE_nurb_handle_calc(bezt, bezt_prev, bezt_next, 0);
1705         }
1706 #else
1707         if (handle_type == HD_VECT) {
1708                 BKE_nurb_handle_calc(bezt, bezt_prev, bezt_next, 0);
1709         }
1710         else if (handle_type == HD_AUTO) {
1711                 BKE_nurb_handle_calc(bezt, bezt_prev, bezt_next, 0);
1712         }
1713         else if (handle_type == HD_ALIGN) {
1714                 float v1[3], v2[3];
1715                 float vec[3], h[3];
1716
1717                 sub_v3_v3v3(v1, bezt->vec[0], bezt->vec[1]);
1718                 sub_v3_v3v3(v2, bezt->vec[2], bezt->vec[1]);
1719                 add_v3_v3v3(vec, v1, v2);
1720
1721                 if (len_v3(vec) > 1e-3) {
1722                         h[0] = vec[1];
1723                         h[1] = -vec[0];
1724                         h[2] = 0.0f;
1725                 }
1726                 else {
1727                         copy_v3_v3(h, v1);
1728                 }
1729
1730                 add_v3_v3v3(bezt->vec[0], bezt->vec[1], h);
1731                 sub_v3_v3v3(bezt->vec[2], bezt->vec[1], h);
1732         }
1733 #endif
1734 }
1735
1736 void BKE_mask_get_handle_point_adjacent(MaskSpline *spline, MaskSplinePoint *point,
1737                                         MaskSplinePoint **r_point_prev, MaskSplinePoint **r_point_next)
1738 {
1739         /* TODO, could avoid calling this at such low level */
1740         MaskSplinePoint *points_array = BKE_mask_spline_point_array_from_point(spline, point);
1741
1742         *r_point_prev = mask_spline_point_prev(spline, points_array, point);
1743         *r_point_next = mask_spline_point_next(spline, points_array, point);
1744 }
1745
1746 /* calculates the tanget of a point by its previous and next
1747  * (ignoring handles - as if its a poly line) */
1748 void BKE_mask_calc_tangent_polyline(MaskSpline *spline, MaskSplinePoint *point, float t[2])
1749 {
1750         float tvec_a[2], tvec_b[2];
1751
1752         MaskSplinePoint *point_prev, *point_next;
1753
1754         BKE_mask_get_handle_point_adjacent(spline, point,
1755                                            &point_prev, &point_next);
1756
1757         if (point_prev) {
1758                 sub_v2_v2v2(tvec_a, point->bezt.vec[1], point_prev->bezt.vec[1]);
1759                 normalize_v2(tvec_a);
1760         }
1761         else {
1762                 zero_v2(tvec_a);
1763         }
1764
1765         if (point_next) {
1766                 sub_v2_v2v2(tvec_b, point_next->bezt.vec[1], point->bezt.vec[1]);
1767                 normalize_v2(tvec_b);
1768         }
1769         else {
1770                 zero_v2(tvec_b);
1771         }
1772
1773         add_v2_v2v2(t, tvec_a, tvec_b);
1774         normalize_v2(t);
1775 }
1776
1777 void BKE_mask_calc_handle_point(MaskSpline *spline, MaskSplinePoint *point)
1778 {
1779         MaskSplinePoint *point_prev, *point_next;
1780
1781         BKE_mask_get_handle_point_adjacent(spline, point,
1782                                            &point_prev, &point_next);
1783
1784         mask_calc_point_handle(point, point_prev, point_next);
1785 }
1786
1787 static void enforce_dist_v2_v2fl(float v1[2], const float v2[2], const float dist)
1788 {
1789         if (!equals_v2v2(v2, v1)) {
1790                 float nor[2];
1791
1792                 sub_v2_v2v2(nor, v1, v2);
1793                 normalize_v2(nor);
1794                 madd_v2_v2v2fl(v1, v2, nor, dist);
1795         }
1796 }
1797
1798 void BKE_mask_calc_handle_adjacent_interp(MaskSpline *spline, MaskSplinePoint *point, const float u)
1799 {
1800         /* TODO! - make this interpolate between siblings - not always midpoint! */
1801         int length_tot = 0;
1802         float length_average = 0.0f;
1803         float weight_average = 0.0f;
1804
1805
1806         MaskSplinePoint *point_prev, *point_next;
1807
1808         BLI_assert(u >= 0.0f && u <= 1.0f);
1809
1810         BKE_mask_get_handle_point_adjacent(spline, point,
1811                                            &point_prev, &point_next);
1812
1813         if (point_prev && point_next) {
1814                 length_average = ((len_v2v2(point_prev->bezt.vec[0], point_prev->bezt.vec[1]) * (1.0f - u)) +
1815                                   (len_v2v2(point_next->bezt.vec[2], point_next->bezt.vec[1]) * u));
1816
1817                 weight_average = (point_prev->bezt.weight * (1.0f - u) +
1818                                   point_next->bezt.weight * u);
1819                 length_tot = 1;
1820         }
1821         else {
1822                 if (point_prev) {
1823                         length_average += len_v2v2(point_prev->bezt.vec[0], point_prev->bezt.vec[1]);
1824                         weight_average += point_prev->bezt.weight;
1825                         length_tot++;
1826                 }
1827
1828                 if (point_next) {
1829                         length_average += len_v2v2(point_next->bezt.vec[2], point_next->bezt.vec[1]);
1830                         weight_average += point_next->bezt.weight;
1831                         length_tot++;
1832                 }
1833         }
1834
1835         if (length_tot) {
1836                 length_average /= (float)length_tot;
1837                 weight_average /= (float)length_tot;
1838
1839                 enforce_dist_v2_v2fl(point->bezt.vec[0], point->bezt.vec[1], length_average);
1840                 enforce_dist_v2_v2fl(point->bezt.vec[2], point->bezt.vec[1], length_average);
1841                 point->bezt.weight = weight_average;
1842         }
1843 }
1844
1845
1846 /**
1847  * \brief Resets auto handles even for non-auto bezier points
1848  *
1849  * Useful for giving sane defaults.
1850  */
1851 void BKE_mask_calc_handle_point_auto(MaskSpline *spline, MaskSplinePoint *point,
1852                                      const short do_recalc_length)
1853 {
1854         MaskSplinePoint *point_prev, *point_next;
1855         const char h_back[2] = {point->bezt.h1, point->bezt.h2};
1856         const float length_average = (do_recalc_length) ? 0.0f /* dummy value */ :
1857                                      (len_v3v3(point->bezt.vec[0], point->bezt.vec[1]) +
1858                                       len_v3v3(point->bezt.vec[1], point->bezt.vec[2])) / 2.0f;
1859
1860         BKE_mask_get_handle_point_adjacent(spline, point,
1861                                            &point_prev, &point_next);
1862
1863         point->bezt.h1 = HD_AUTO;
1864         point->bezt.h2 = HD_AUTO;
1865         mask_calc_point_handle(point, point_prev, point_next);
1866
1867         point->bezt.h1 = h_back[0];
1868         point->bezt.h2 = h_back[1];
1869
1870         /* preserve length by applying it back */
1871         if (do_recalc_length == FALSE) {
1872                 enforce_dist_v2_v2fl(point->bezt.vec[0], point->bezt.vec[1], length_average);
1873                 enforce_dist_v2_v2fl(point->bezt.vec[2], point->bezt.vec[1], length_average);
1874         }
1875 }
1876
1877 void BKE_mask_layer_calc_handles(MaskLayer *masklay)
1878 {
1879         MaskSpline *spline;
1880         for (spline = masklay->splines.first; spline; spline = spline->next) {
1881                 int i;
1882                 for (i = 0; i < spline->tot_point; i++) {
1883                         BKE_mask_calc_handle_point(spline, &spline->points[i]);
1884                 }
1885         }
1886 }
1887
1888 void BKE_mask_layer_calc_handles_deform(MaskLayer *masklay)
1889 {
1890         MaskSpline *spline;
1891         for (spline = masklay->splines.first; spline; spline = spline->next) {
1892                 int i;
1893                 for (i = 0; i < spline->tot_point; i++) {
1894                         BKE_mask_calc_handle_point(spline, &spline->points_deform[i]);
1895                 }
1896         }
1897 }
1898
1899 void BKE_mask_calc_handles(Mask *mask)
1900 {
1901         MaskLayer *masklay;
1902         for (masklay = mask->masklayers.first; masklay; masklay = masklay->next) {
1903                 BKE_mask_layer_calc_handles(masklay);
1904         }
1905 }
1906
1907 void BKE_mask_update_deform(Mask *mask)
1908 {
1909         MaskLayer *masklay;
1910
1911         for (masklay = mask->masklayers.first; masklay; masklay = masklay->next) {
1912                 MaskSpline *spline;
1913
1914                 for (spline = masklay->splines.first; spline; spline = spline->next) {
1915                         int i;
1916
1917                         for (i = 0; i < spline->tot_point; i++) {
1918                                 const int i_prev = (i - 1) % spline->tot_point;
1919                                 const int i_next = (i + 1) % spline->tot_point;
1920
1921                                 BezTriple *bezt_prev = &spline->points[i_prev].bezt;
1922                                 BezTriple *bezt      = &spline->points[i].bezt;
1923                                 BezTriple *bezt_next = &spline->points[i_next].bezt;
1924
1925                                 BezTriple *bezt_def_prev = &spline->points_deform[i_prev].bezt;
1926                                 BezTriple *bezt_def      = &spline->points_deform[i].bezt;
1927                                 BezTriple *bezt_def_next = &spline->points_deform[i_next].bezt;
1928
1929                                 float w_src[4];
1930                                 int j;
1931
1932                                 for (j = 0; j <= 2; j += 2) { /* (0, 2) */
1933                                         printf("--- %d %d, %d, %d\n", i, j, i_prev, i_next);
1934                                         barycentric_weights_v2(bezt_prev->vec[1], bezt->vec[1], bezt_next->vec[1],
1935                                                                bezt->vec[j], w_src);
1936                                         interp_v3_v3v3v3(bezt_def->vec[j],
1937                                                          bezt_def_prev->vec[1], bezt_def->vec[1], bezt_def_next->vec[1], w_src);
1938                                 }
1939                         }
1940                 }
1941         }
1942 }
1943
1944 void BKE_mask_spline_ensure_deform(MaskSpline *spline)
1945 {
1946         int allocated_points = (MEM_allocN_len(spline->points_deform) / sizeof(*spline->points_deform));
1947         // printf("SPLINE ALLOC %p %d\n", spline->points_deform, allocated_points);
1948
1949         if (spline->points_deform == NULL || allocated_points != spline->tot_point) {
1950                 // printf("alloc new deform spline\n");
1951
1952                 if (spline->points_deform) {
1953                         int i;
1954
1955                         for (i = 0; i < allocated_points; i++) {
1956                                 MaskSplinePoint *point = &spline->points_deform[i];
1957                                 BKE_mask_point_free(point);
1958                         }
1959
1960                         MEM_freeN(spline->points_deform);
1961                 }
1962
1963                 spline->points_deform = MEM_callocN(sizeof(*spline->points_deform) * spline->tot_point, __func__);
1964         }
1965         else {
1966                 // printf("alloc spline done\n");
1967         }
1968 }
1969
1970 void BKE_mask_layer_evaluate(MaskLayer *masklay, const float ctime, const int do_newframe)
1971 {
1972         /* animation if available */
1973         if (do_newframe) {
1974                 MaskLayerShape *masklay_shape_a;
1975                 MaskLayerShape *masklay_shape_b;
1976                 int found;
1977
1978                 if ((found = BKE_mask_layer_shape_find_frame_range(masklay, ctime,
1979                                                                    &masklay_shape_a, &masklay_shape_b)))
1980                 {
1981                         if (found == 1) {
1982 #if 0
1983                                 printf("%s: exact %d %d (%d)\n", __func__, (int)ctime, BLI_countlist(&masklay->splines_shapes),
1984                                        masklay_shape_a->frame);
1985 #endif
1986
1987                                 BKE_mask_layer_shape_to_mask(masklay, masklay_shape_a);
1988                         }
1989                         else if (found == 2) {
1990                                 float w = masklay_shape_b->frame - masklay_shape_a->frame;
1991 #if 0
1992                                 printf("%s: tween %d %d (%d %d)\n", __func__, (int)ctime, BLI_countlist(&masklay->splines_shapes),
1993                                        masklay_shape_a->frame, masklay_shape_b->frame);
1994 #endif
1995                                 BKE_mask_layer_shape_to_mask_interp(masklay, masklay_shape_a, masklay_shape_b,
1996                                                                     (ctime - masklay_shape_a->frame) / w);
1997                         }
1998                         else {
1999                                 /* always fail, should never happen */
2000                                 BLI_assert(found == 2);
2001                         }
2002                 }
2003         }
2004         /* animation done... */
2005
2006         BKE_mask_layer_calc_handles(masklay);
2007
2008         /* update deform */
2009         {
2010                 MaskSpline *spline;
2011
2012                 for (spline = masklay->splines.first; spline; spline = spline->next) {
2013                         int i;
2014                         int has_auto = FALSE;
2015
2016                         BKE_mask_spline_ensure_deform(spline);
2017
2018                         for (i = 0; i < spline->tot_point; i++) {
2019                                 MaskSplinePoint *point = &spline->points[i];
2020                                 MaskSplinePoint *point_deform = &spline->points_deform[i];
2021                                 float delta[2];
2022
2023                                 BKE_mask_point_free(point_deform);
2024
2025                                 *point_deform = *point;
2026                                 point_deform->uw = point->uw ? MEM_dupallocN(point->uw) : NULL;
2027
2028                                 if (BKE_mask_evaluate_parent_delta(&point->parent, ctime, delta)) {
2029                                         add_v2_v2(point_deform->bezt.vec[0], delta);
2030                                         add_v2_v2(point_deform->bezt.vec[1], delta);
2031                                         add_v2_v2(point_deform->bezt.vec[2], delta);
2032                                 }
2033
2034                                 if (point->bezt.h1 == HD_AUTO) {
2035                                         has_auto = TRUE;
2036                                 }
2037                         }
2038
2039                         /* if the spline has auto handles, these need to be recalculated after deformation */
2040                         if (has_auto) {
2041                                 for (i = 0; i < spline->tot_point; i++) {
2042                                         MaskSplinePoint *point_deform = &spline->points_deform[i];
2043                                         if (point_deform->bezt.h1 == HD_AUTO) {
2044                                                 BKE_mask_calc_handle_point(spline, point_deform);
2045                                         }
2046                                 }
2047                         }
2048                         /* end extra calc handles loop */
2049                 }
2050         }
2051 }
2052
2053 void BKE_mask_evaluate(Mask *mask, const float ctime, const int do_newframe)
2054 {
2055         MaskLayer *masklay;
2056
2057         for (masklay = mask->masklayers.first; masklay; masklay = masklay->next) {
2058                 BKE_mask_layer_evaluate(masklay, ctime, do_newframe);
2059         }
2060 }
2061
2062 /* the purpose of this function is to ensure spline->points_deform is never out of date.
2063  * for now re-evaluate all. eventually this might work differently */
2064 void BKE_mask_update_display(Mask *mask, float ctime)
2065 {
2066 #if 0
2067         MaskLayer *masklay;
2068
2069         for (masklay = mask->masklayers.first; masklay; masklay = masklay->next) {
2070                 MaskSpline *spline;
2071
2072                 for (spline = masklay->splines.first; spline; spline = spline->next) {
2073                         if (spline->points_deform) {
2074                                 int i = 0;
2075
2076                                 for (i = 0; i < spline->tot_point; i++) {
2077                                         MaskSplinePoint *point;
2078
2079                                         if (spline->points_deform) {
2080                                                 point = &spline->points_deform[i];
2081                                                 BKE_mask_point_free(point);
2082                                         }
2083                                 }
2084                                 if (spline->points_deform) {
2085                                         MEM_freeN(spline->points_deform);
2086                                 }
2087
2088                                 spline->points_deform = NULL;
2089                         }
2090                 }
2091         }
2092 #endif
2093
2094         BKE_mask_evaluate(mask, ctime, FALSE);
2095 }
2096
2097 void BKE_mask_evaluate_all_masks(Main *bmain, float ctime, const int do_newframe)
2098 {
2099         Mask *mask;
2100
2101         for (mask = bmain->mask.first; mask; mask = mask->id.next) {
2102                 BKE_mask_evaluate(mask, ctime, do_newframe);
2103         }
2104 }
2105
2106 void BKE_mask_update_scene(Main *bmain, Scene *scene, const int do_newframe)
2107 {
2108         Mask *mask;
2109
2110         for (mask = bmain->mask.first; mask; mask = mask->id.next) {
2111                 if (mask->id.flag & LIB_ID_RECALC) {
2112                         BKE_mask_evaluate_all_masks(bmain, CFRA, do_newframe);
2113                 }
2114         }
2115 }
2116
2117 void BKE_mask_parent_init(MaskParent *parent)
2118 {
2119         parent->id_type = ID_MC;
2120 }
2121
2122
2123 /* *** own animation/shapekey implimentation ***
2124  * BKE_mask_layer_shape_XXX */
2125
2126 int BKE_mask_layer_shape_totvert(MaskLayer *masklay)
2127 {
2128         int tot = 0;
2129         MaskSpline *spline;
2130
2131         for (spline = masklay->splines.first; spline; spline = spline->next) {
2132                 tot += spline->tot_point;
2133         }
2134
2135         return tot;
2136 }
2137
2138 static void mask_layer_shape_from_mask_point(BezTriple *bezt, float fp[MASK_OBJECT_SHAPE_ELEM_SIZE])
2139 {
2140         copy_v2_v2(&fp[0], bezt->vec[0]);
2141         copy_v2_v2(&fp[2], bezt->vec[1]);
2142         copy_v2_v2(&fp[4], bezt->vec[2]);
2143         fp[6] = bezt->weight;
2144         fp[7] = bezt->radius;
2145 }
2146
2147 static void mask_layer_shape_to_mask_point(BezTriple *bezt, float fp[MASK_OBJECT_SHAPE_ELEM_SIZE])
2148 {
2149         copy_v2_v2(bezt->vec[0], &fp[0]);
2150         copy_v2_v2(bezt->vec[1], &fp[2]);
2151         copy_v2_v2(bezt->vec[2], &fp[4]);
2152         bezt->weight = fp[6];
2153         bezt->radius = fp[7];
2154 }
2155
2156 /* these functions match. copy is swapped */
2157 void BKE_mask_layer_shape_from_mask(MaskLayer *masklay, MaskLayerShape *masklay_shape)
2158 {
2159         int tot = BKE_mask_layer_shape_totvert(masklay);
2160
2161         if (masklay_shape->tot_vert == tot) {
2162                 float *fp = masklay_shape->data;
2163
2164                 MaskSpline *spline;
2165                 for (spline = masklay->splines.first; spline; spline = spline->next) {
2166                         int i;
2167                         for (i = 0; i < spline->tot_point; i++) {
2168                                 mask_layer_shape_from_mask_point(&spline->points[i].bezt, fp);
2169                                 fp += MASK_OBJECT_SHAPE_ELEM_SIZE;
2170                         }
2171                 }
2172         }
2173         else {
2174                 printf("%s: vert mismatch %d != %d (frame %d)\n",
2175                        __func__, masklay_shape->tot_vert, tot, masklay_shape->frame);
2176         }
2177 }
2178
2179 void BKE_mask_layer_shape_to_mask(MaskLayer *masklay, MaskLayerShape *masklay_shape)
2180 {
2181         int tot = BKE_mask_layer_shape_totvert(masklay);
2182
2183         if (masklay_shape->tot_vert == tot) {
2184                 float *fp = masklay_shape->data;
2185
2186                 MaskSpline *spline;
2187                 for (spline = masklay->splines.first; spline; spline = spline->next) {
2188                         int i;
2189                         for (i = 0; i < spline->tot_point; i++) {
2190                                 mask_layer_shape_to_mask_point(&spline->points[i].bezt, fp);
2191                                 fp += MASK_OBJECT_SHAPE_ELEM_SIZE;
2192                         }
2193                 }
2194         }
2195         else {
2196                 printf("%s: vert mismatch %d != %d (frame %d)\n",
2197                        __func__, masklay_shape->tot_vert, tot, masklay_shape->frame);
2198         }
2199 }
2200
2201 BLI_INLINE void interp_v2_v2v2_flfl(float target[2], const float a[2], const float b[2],
2202                                     const float t, const float s)
2203 {
2204         target[0] = s * a[0] + t * b[0];
2205         target[1] = s * a[1] + t * b[1];
2206 }
2207
2208 /* linear interpolation only */
2209 void BKE_mask_layer_shape_to_mask_interp(MaskLayer *masklay,
2210                                          MaskLayerShape *masklay_shape_a,
2211                                          MaskLayerShape *masklay_shape_b,
2212                                          const float fac)
2213 {
2214         int tot = BKE_mask_layer_shape_totvert(masklay);
2215         if (masklay_shape_a->tot_vert == tot && masklay_shape_b->tot_vert == tot) {
2216                 float *fp_a = masklay_shape_a->data;
2217                 float *fp_b = masklay_shape_b->data;
2218                 const float ifac = 1.0f - fac;
2219
2220                 MaskSpline *spline;
2221                 for (spline = masklay->splines.first; spline; spline = spline->next) {
2222                         int i;
2223                         for (i = 0; i < spline->tot_point; i++) {
2224                                 BezTriple *bezt = &spline->points[i].bezt;
2225                                 /* *** BKE_mask_layer_shape_from_mask - swapped *** */
2226                                 interp_v2_v2v2_flfl(bezt->vec[0], fp_a, fp_b, fac, ifac); fp_a += 2; fp_b += 2;
2227                                 interp_v2_v2v2_flfl(bezt->vec[1], fp_a, fp_b, fac, ifac); fp_a += 2; fp_b += 2;
2228                                 interp_v2_v2v2_flfl(bezt->vec[2], fp_a, fp_b, fac, ifac); fp_a += 2; fp_b += 2;
2229                                 bezt->weight = (fp_a[0] * ifac) + (fp_b[0] * fac);
2230                                 bezt->radius = (fp_a[1] * ifac) + (fp_b[1] * fac); fp_a += 2; fp_b += 2;
2231                         }
2232                 }
2233         }
2234         else {
2235                 printf("%s: vert mismatch %d != %d != %d (frame %d - %d)\n",
2236                        __func__, masklay_shape_a->tot_vert, masklay_shape_b->tot_vert, tot,
2237                        masklay_shape_a->frame, masklay_shape_b->frame);
2238         }
2239 }
2240
2241 MaskLayerShape *BKE_mask_layer_shape_find_frame(MaskLayer *masklay, const int frame)
2242 {
2243         MaskLayerShape *masklay_shape;
2244
2245         for (masklay_shape = masklay->splines_shapes.first;
2246              masklay_shape;
2247              masklay_shape = masklay_shape->next)
2248         {
2249                 if (frame == masklay_shape->frame) {
2250                         return masklay_shape;
2251                 }
2252                 else if (frame < masklay_shape->frame) {
2253                         break;
2254                 }
2255         }
2256
2257         return NULL;
2258 }
2259
2260 /* when returning 2 - the frame isnt found but before/after frames are */
2261 int BKE_mask_layer_shape_find_frame_range(MaskLayer *masklay, const float frame,
2262                                           MaskLayerShape **r_masklay_shape_a,
2263                                           MaskLayerShape **r_masklay_shape_b)
2264 {
2265         MaskLayerShape *masklay_shape;
2266
2267         for (masklay_shape = masklay->splines_shapes.first;
2268              masklay_shape;
2269              masklay_shape = masklay_shape->next)
2270         {
2271                 if (frame == masklay_shape->frame) {
2272                         *r_masklay_shape_a = masklay_shape;
2273                         *r_masklay_shape_b = NULL;
2274                         return 1;
2275                 }
2276                 else if (frame < masklay_shape->frame) {
2277                         if (masklay_shape->prev) {
2278                                 *r_masklay_shape_a = masklay_shape->prev;
2279                                 *r_masklay_shape_b = masklay_shape;
2280                                 return 2;
2281                         }
2282                         else {
2283                                 *r_masklay_shape_a = masklay_shape;
2284                                 *r_masklay_shape_b = NULL;
2285                                 return 1;
2286                         }
2287                 }
2288         }
2289
2290         if ((masklay_shape = masklay->splines_shapes.last)) {
2291                 *r_masklay_shape_a = masklay_shape;
2292                 *r_masklay_shape_b = NULL;
2293                 return 1;
2294         }
2295         else {
2296                 *r_masklay_shape_a = NULL;
2297                 *r_masklay_shape_b = NULL;
2298
2299                 return 0;
2300         }
2301 }
2302
2303 MaskLayerShape *BKE_mask_layer_shape_varify_frame(MaskLayer *masklay, const int frame)
2304 {
2305         MaskLayerShape *masklay_shape;
2306
2307         masklay_shape = BKE_mask_layer_shape_find_frame(masklay, frame);
2308
2309         if (masklay_shape == NULL) {
2310                 masklay_shape = BKE_mask_layer_shape_alloc(masklay, frame);
2311                 BLI_addtail(&masklay->splines_shapes, masklay_shape);
2312                 BKE_mask_layer_shape_sort(masklay);
2313         }
2314
2315 #if 0
2316         {
2317                 MaskLayerShape *masklay_shape;
2318                 int i = 0;
2319                 for (masklay_shape = masklay->splines_shapes.first;
2320                      masklay_shape;
2321                      masklay_shape = masklay_shape->next)
2322                 {
2323                         printf("mask %d, %d\n", i++, masklay_shape->frame);
2324                 }
2325         }
2326 #endif
2327
2328         return masklay_shape;
2329 }
2330
2331 MaskLayerShape *BKE_mask_layer_shape_duplicate(MaskLayerShape *masklay_shape)
2332 {
2333         MaskLayerShape *masklay_shape_copy;
2334
2335         masklay_shape_copy = MEM_dupallocN(masklay_shape);
2336
2337         if (LIKELY(masklay_shape_copy->data)) {
2338                 masklay_shape_copy->data = MEM_dupallocN(masklay_shape_copy->data);
2339         }
2340
2341         return masklay_shape_copy;
2342 }
2343
2344 void BKE_mask_layer_shape_unlink(MaskLayer *masklay, MaskLayerShape *masklay_shape)
2345 {
2346         BLI_remlink(&masklay->splines_shapes, masklay_shape);
2347
2348         BKE_mask_layer_shape_free(masklay_shape);
2349 }
2350
2351 static int mask_layer_shape_sort_cb(void *masklay_shape_a_ptr, void *masklay_shape_b_ptr)
2352 {
2353         MaskLayerShape *masklay_shape_a = (MaskLayerShape *)masklay_shape_a_ptr;
2354         MaskLayerShape *masklay_shape_b = (MaskLayerShape *)masklay_shape_b_ptr;
2355
2356         if      (masklay_shape_a->frame < masklay_shape_b->frame)  return -1;
2357         else if (masklay_shape_a->frame > masklay_shape_b->frame)  return  1;
2358         else                                                       return  0;
2359 }
2360
2361 void BKE_mask_layer_shape_sort(MaskLayer *masklay)
2362 {
2363         BLI_sortlist(&masklay->splines_shapes, mask_layer_shape_sort_cb);
2364 }
2365
2366 int BKE_mask_layer_shape_spline_from_index(MaskLayer *masklay, int index,
2367                                            MaskSpline **r_masklay_shape, int *r_index)
2368 {
2369         MaskSpline *spline;
2370
2371         for (spline = masklay->splines.first; spline; spline = spline->next) {
2372                 if (index < spline->tot_point) {
2373                         *r_masklay_shape = spline;
2374                         *r_index = index;
2375                         return TRUE;
2376                 }
2377                 index -= spline->tot_point;
2378         }
2379
2380         return FALSE;
2381 }
2382
2383 int BKE_mask_layer_shape_spline_to_index(MaskLayer *masklay, MaskSpline *spline)
2384 {
2385         MaskSpline *spline_iter;
2386         int i_abs = 0;
2387         for (spline_iter = masklay->splines.first;
2388              spline_iter && spline_iter != spline;
2389              i_abs += spline_iter->tot_point, spline_iter = spline_iter->next)
2390         {
2391                 /* pass */
2392         }
2393
2394         return i_abs;
2395 }
2396
2397 /* basic 2D interpolation functions, could make more comprehensive later */
2398 static void interp_weights_uv_v2_calc(float r_uv[2], const float pt[2], const float pt_a[2], const float pt_b[2])
2399 {
2400         float pt_on_line[2];
2401         r_uv[0] = closest_to_line_v2(pt_on_line, pt, pt_a, pt_b);
2402         r_uv[1] = (len_v2v2(pt_on_line, pt) / len_v2v2(pt_a, pt_b)) *
2403                   ((line_point_side_v2(pt_a, pt_b, pt) < 0.0f) ? -1.0 : 1.0);  /* this line only sets the sign */
2404 }
2405
2406
2407 static void interp_weights_uv_v2_apply(const float uv[2], float r_pt[2], const float pt_a[2], const float pt_b[2])
2408 {
2409         const float dvec[2] = {pt_b[0] - pt_a[0],
2410                                pt_b[1] - pt_a[1]};
2411
2412         /* u */
2413         madd_v2_v2v2fl(r_pt, pt_a, dvec, uv[0]);
2414
2415         /* v */
2416         r_pt[0] += -dvec[1] * uv[1];
2417         r_pt[1] +=  dvec[0] * uv[1];
2418 }
2419
2420 /* when a now points added - resize all shapekey array  */
2421 void BKE_mask_layer_shape_changed_add(MaskLayer *masklay, int index,
2422                                       int do_init, int do_init_interpolate)
2423 {
2424         MaskLayerShape *masklay_shape;
2425
2426         /* spline index from masklay */
2427         MaskSpline *spline;
2428         int spline_point_index;
2429
2430         if (BKE_mask_layer_shape_spline_from_index(masklay, index,
2431                                                    &spline, &spline_point_index))
2432         {
2433                 /* sanity check */
2434                 /* the point has already been removed in this array so subtract one when comparing with the shapes */
2435                 int tot = BKE_mask_layer_shape_totvert(masklay) - 1;
2436
2437                 /* for interpolation */
2438                 /* TODO - assumes closed curve for now */
2439                 float uv[3][2]; /* 3x 2D handles */
2440                 const int pi_curr =   spline_point_index;
2441                 const int pi_prev = ((spline_point_index - 1) + spline->tot_point) % spline->tot_point;
2442                 const int pi_next =  (spline_point_index + 1)                      % spline->tot_point;
2443
2444                 const int index_offset = index - spline_point_index;
2445                 /* const int pi_curr_abs = index; */
2446                 const int pi_prev_abs = pi_prev + index_offset;
2447                 const int pi_next_abs = pi_next + index_offset;
2448
2449                 int i;
2450                 if (do_init_interpolate) {
2451                         for (i = 0; i < 3; i++) {
2452                                 interp_weights_uv_v2_calc(uv[i],
2453                                                           spline->points[pi_curr].bezt.vec[i],
2454                                                           spline->points[pi_prev].bezt.vec[i],
2455                                                           spline->points[pi_next].bezt.vec[i]);
2456                         }
2457                 }
2458
2459                 for (masklay_shape = masklay->splines_shapes.first;
2460                      masklay_shape;
2461                      masklay_shape = masklay_shape->next)
2462                 {
2463                         if (tot == masklay_shape->tot_vert) {
2464                                 float *data_resized;
2465
2466                                 masklay_shape->tot_vert++;
2467                                 data_resized = MEM_mallocN(masklay_shape->tot_vert * sizeof(float) * MASK_OBJECT_SHAPE_ELEM_SIZE, __func__);
2468                                 if (index > 0) {
2469                                         memcpy(data_resized,
2470                                                masklay_shape->data,
2471                                                index * sizeof(float) * MASK_OBJECT_SHAPE_ELEM_SIZE);
2472                                 }
2473
2474                                 if (index != masklay_shape->tot_vert - 1) {
2475                                         memcpy(&data_resized[(index + 1) * MASK_OBJECT_SHAPE_ELEM_SIZE],
2476                                                masklay_shape->data + (index * MASK_OBJECT_SHAPE_ELEM_SIZE),
2477                                                (masklay_shape->tot_vert - (index + 1)) * sizeof(float) * MASK_OBJECT_SHAPE_ELEM_SIZE);
2478                                 }
2479
2480                                 if (do_init) {
2481                                         float *fp = &data_resized[index * MASK_OBJECT_SHAPE_ELEM_SIZE];
2482
2483                                         mask_layer_shape_from_mask_point(&spline->points[spline_point_index].bezt, fp);
2484
2485                                         if (do_init_interpolate && spline->tot_point > 2) {
2486                                                 for (i = 0; i < 3; i++) {
2487                                                         interp_weights_uv_v2_apply(uv[i],
2488                                                                                    &fp[i * 2],
2489                                                                                    &data_resized[(pi_prev_abs * MASK_OBJECT_SHAPE_ELEM_SIZE) + (i * 2)],
2490                                                                                    &data_resized[(pi_next_abs * MASK_OBJECT_SHAPE_ELEM_SIZE) + (i * 2)]);
2491                                                 }
2492                                         }
2493                                 }
2494                                 else {
2495                                         memset(&data_resized[index * MASK_OBJECT_SHAPE_ELEM_SIZE],
2496                                                0,
2497                                                sizeof(float) * MASK_OBJECT_SHAPE_ELEM_SIZE);
2498                                 }
2499
2500                                 MEM_freeN(masklay_shape->data);
2501                                 masklay_shape->data = data_resized;
2502                         }
2503                         else {
2504                                 printf("%s: vert mismatch %d != %d (frame %d)\n",
2505                                        __func__, masklay_shape->tot_vert, tot, masklay_shape->frame);
2506                         }
2507                 }
2508         }
2509 }
2510
2511
2512 /* move array to account for removed point */
2513 void BKE_mask_layer_shape_changed_remove(MaskLayer *masklay, int index, int count)
2514 {
2515         MaskLayerShape *masklay_shape;
2516
2517         /* the point has already been removed in this array so add one when comparing with the shapes */
2518         int tot = BKE_mask_layer_shape_totvert(masklay);
2519
2520         for (masklay_shape = masklay->splines_shapes.first;
2521              masklay_shape;
2522              masklay_shape = masklay_shape->next)
2523         {
2524                 if (tot == masklay_shape->tot_vert - count) {
2525                         float *data_resized;
2526
2527                         masklay_shape->tot_vert -= count;
2528                         data_resized = MEM_mallocN(masklay_shape->tot_vert * sizeof(float) * MASK_OBJECT_SHAPE_ELEM_SIZE, __func__);
2529                         if (index > 0) {
2530                                 memcpy(data_resized,
2531                                        masklay_shape->data,
2532                                        index * sizeof(float) * MASK_OBJECT_SHAPE_ELEM_SIZE);
2533                         }
2534
2535                         if (index != masklay_shape->tot_vert) {
2536                                 memcpy(&data_resized[index * MASK_OBJECT_SHAPE_ELEM_SIZE],
2537                                        masklay_shape->data + ((index + count) * MASK_OBJECT_SHAPE_ELEM_SIZE),
2538                                        (masklay_shape->tot_vert - index) * sizeof(float) * MASK_OBJECT_SHAPE_ELEM_SIZE);
2539                         }
2540
2541                         MEM_freeN(masklay_shape->data);
2542                         masklay_shape->data = data_resized;
2543                 }
2544                 else {
2545                         printf("%s: vert mismatch %d != %d (frame %d)\n",
2546                                __func__, masklay_shape->tot_vert - count, tot, masklay_shape->frame);
2547                 }
2548         }
2549 }
2550
2551 int BKE_mask_get_duration(Mask *mask)
2552 {
2553         return maxi(1, mask->efra - mask->sfra);
2554 }