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