Sequencer: fix for wrong color space sequencer effects were working in
[blender.git] / source / blender / blenkernel / intern / mask_evaluate.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  *                 Campbell Barton
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/mask_evaluate.c
29  *  \ingroup bke
30  *
31  * Functions for evaluating the mask beziers into points for the outline and feather.
32  */
33
34 #include <stddef.h>
35 #include <string.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_utildefines.h"
40 #include "BLI_path_util.h"
41 #include "BLI_string.h"
42 #include "BLI_listbase.h"
43 #include "BLI_math.h"
44
45 #include "DNA_mask_types.h"
46 #include "DNA_node_types.h"
47 #include "DNA_scene_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_screen_types.h"
50 #include "DNA_space_types.h"
51 #include "DNA_movieclip_types.h"
52 #include "DNA_tracking_types.h"
53 #include "DNA_sequence_types.h"
54
55 #include "BKE_curve.h"
56 #include "BKE_global.h"
57 #include "BKE_library.h"
58 #include "BKE_main.h"
59 #include "BKE_mask.h"
60 #include "BKE_node.h"
61 #include "BKE_sequencer.h"
62 #include "BKE_tracking.h"
63 #include "BKE_movieclip.h"
64 #include "BKE_utildefines.h"
65
66
67 unsigned int BKE_mask_spline_resolution(MaskSpline *spline, int width, int height)
68 {
69         float max_segment = 0.01f;
70         unsigned int i, resol = 1;
71
72         if (width != 0 && height != 0) {
73                 if (width >= height)
74                         max_segment = 1.0f / (float) width;
75                 else
76                         max_segment = 1.0f / (float) height;
77         }
78
79         for (i = 0; i < spline->tot_point; i++) {
80                 MaskSplinePoint *point = &spline->points[i];
81                 BezTriple *bezt, *bezt_next;
82                 float a, b, c, len;
83                 unsigned int cur_resol;
84
85                 bezt = &point->bezt;
86                 bezt_next = BKE_mask_spline_point_next_bezt(spline, spline->points, point);
87
88                 if (bezt_next == NULL) {
89                         break;
90                 }
91
92                 a = len_v3v3(bezt->vec[1], bezt->vec[2]);
93                 b = len_v3v3(bezt->vec[2], bezt_next->vec[0]);
94                 c = len_v3v3(bezt_next->vec[0], bezt_next->vec[1]);
95
96                 len = a + b + c;
97                 cur_resol = len / max_segment;
98
99                 resol = MAX2(resol, cur_resol);
100
101                 if (resol >= MASK_RESOL_MAX) {
102                         break;
103                 }
104         }
105
106         return CLAMPIS(resol, 1, MASK_RESOL_MAX);
107 }
108
109 unsigned int BKE_mask_spline_feather_resolution(MaskSpline *spline, int width, int height)
110 {
111         const float max_segment = 0.005;
112         unsigned int resol = BKE_mask_spline_resolution(spline, width, height);
113         float max_jump = 0.0f;
114         int i;
115
116         /* avoid checking the featrher if we already hit the maximum value */
117         if (resol >= MASK_RESOL_MAX) {
118                 return MASK_RESOL_MAX;
119         }
120
121         for (i = 0; i < spline->tot_point; i++) {
122                 MaskSplinePoint *point = &spline->points[i];
123                 float prev_u, prev_w;
124                 int j;
125
126                 prev_u = 0.0f;
127                 prev_w = point->bezt.weight;
128
129                 for (j = 0; j < point->tot_uw; j++) {
130                         const float w_diff = (point->uw[j].w - prev_w);
131                         const float u_diff = (point->uw[j].u - prev_u);
132
133                         /* avoid divide by zero and very high values,
134                          * though these get clamped eventually */
135                         if (u_diff > FLT_EPSILON) {
136                                 float jump = fabsf(w_diff / u_diff);
137
138                                 max_jump = MAX2(max_jump, jump);
139                         }
140
141                         prev_u = point->uw[j].u;
142                         prev_w = point->uw[j].w;
143                 }
144         }
145
146         resol += max_jump / max_segment;
147
148         return CLAMPIS(resol, 1, MASK_RESOL_MAX);
149 }
150
151 int BKE_mask_spline_differentiate_calc_total(const MaskSpline *spline, const unsigned int resol)
152 {
153         if (spline->flag & MASK_SPLINE_CYCLIC) {
154                 return spline->tot_point * resol;
155         }
156         else {
157                 return ((spline->tot_point - 1) * resol) + 1;
158         }
159 }
160
161 float (*BKE_mask_spline_differentiate_with_resolution_ex(MaskSpline *spline,
162                                                          int *tot_diff_point,
163                                                          const unsigned int resol
164                                                          ))[2]
165 {
166         MaskSplinePoint *points_array = BKE_mask_spline_point_array(spline);
167
168         MaskSplinePoint *point, *prev;
169         float (*diff_points)[2], (*fp)[2];
170         const int tot = BKE_mask_spline_differentiate_calc_total(spline, resol);
171         int a;
172
173         if (spline->tot_point <= 1) {
174                 /* nothing to differentiate */
175                 *tot_diff_point = 0;
176                 return NULL;
177         }
178
179         /* len+1 because of 'forward_diff_bezier' function */
180         *tot_diff_point = tot;
181         diff_points = fp = MEM_mallocN((tot + 1) * sizeof(*diff_points), "mask spline vets");
182
183         a = spline->tot_point - 1;
184         if (spline->flag & MASK_SPLINE_CYCLIC)
185                 a++;
186
187         prev = points_array;
188         point = prev + 1;
189
190         while (a--) {
191                 BezTriple *prevbezt;
192                 BezTriple *bezt;
193                 int j;
194
195                 if (a == 0 && (spline->flag & MASK_SPLINE_CYCLIC))
196                         point = points_array;
197
198                 prevbezt = &prev->bezt;
199                 bezt = &point->bezt;
200
201                 for (j = 0; j < 2; j++) {
202                         BKE_curve_forward_diff_bezier(prevbezt->vec[1][j], prevbezt->vec[2][j],
203                                                       bezt->vec[0][j], bezt->vec[1][j],
204                                                       &(*fp)[j], resol, 2 * sizeof(float));
205                 }
206
207                 fp += resol;
208
209                 if (a == 0 && (spline->flag & MASK_SPLINE_CYCLIC) == 0) {
210                         copy_v2_v2(*fp, bezt->vec[1]);
211                 }
212
213                 prev = point;
214                 point++;
215         }
216
217         return diff_points;
218 }
219
220 float (*BKE_mask_spline_differentiate_with_resolution(MaskSpline *spline, int width, int height,
221                                                       int *tot_diff_point
222                                                       ))[2]
223 {
224         int unsigned resol = BKE_mask_spline_resolution(spline, width, height);
225
226         return BKE_mask_spline_differentiate_with_resolution_ex(spline, tot_diff_point, resol);
227 }
228
229 float (*BKE_mask_spline_differentiate(MaskSpline *spline, int *tot_diff_point))[2]
230 {
231         return BKE_mask_spline_differentiate_with_resolution(spline, 0, 0, tot_diff_point);
232 }
233
234 /* ** feather points self-intersection collapse routine ** */
235
236 typedef struct FeatherEdgesBucket {
237         int tot_segment;
238         int (*segments)[2];
239         int alloc_segment;
240 } FeatherEdgesBucket;
241
242 static void feather_bucket_add_edge(FeatherEdgesBucket *bucket, int start, int end)
243 {
244         const int alloc_delta = 256;
245
246         if (bucket->tot_segment >= bucket->alloc_segment) {
247                 if (!bucket->segments) {
248                         bucket->segments = MEM_callocN(alloc_delta * sizeof(*bucket->segments), "feather bucket segments");
249                 }
250                 else {
251                         bucket->segments = MEM_reallocN(bucket->segments,
252                                         (alloc_delta + bucket->tot_segment) * sizeof(*bucket->segments));
253                 }
254
255                 bucket->alloc_segment += alloc_delta;
256         }
257
258         bucket->segments[bucket->tot_segment][0] = start;
259         bucket->segments[bucket->tot_segment][1] = end;
260
261         bucket->tot_segment++;
262 }
263
264 static void feather_bucket_check_intersect(float (*feather_points)[2], int tot_feather_point, FeatherEdgesBucket *bucket,
265                                            int cur_a, int cur_b)
266 {
267         int i;
268
269         float *v1 = (float *) feather_points[cur_a];
270         float *v2 = (float *) feather_points[cur_b];
271
272         for (i = 0; i < bucket->tot_segment; i++) {
273                 int check_a = bucket->segments[i][0];
274                 int check_b = bucket->segments[i][1];
275
276                 float *v3 = (float *) feather_points[check_a];
277                 float *v4 = (float *) feather_points[check_b];
278
279                 if (check_a >= cur_a - 1 || cur_b == check_a)
280                         continue;
281
282                 if (isect_seg_seg_v2(v1, v2, v3, v4)) {
283                         int k;
284                         float p[2];
285                         float min_a[2], max_a[2];
286                         float min_b[2], max_b[2];
287
288                         isect_seg_seg_v2_point(v1, v2, v3, v4, p);
289
290                         INIT_MINMAX2(min_a, max_a);
291                         INIT_MINMAX2(min_b, max_b);
292
293                         /* collapse loop with smaller AABB */
294                         for (k = 0; k < tot_feather_point; k++) {
295                                 if (k >= check_b && k <= cur_a) {
296                                         DO_MINMAX2(feather_points[k], min_a, max_a);
297                                 }
298                                 else {
299                                         DO_MINMAX2(feather_points[k], min_b, max_b);
300                                 }
301                         }
302
303                         if (max_a[0] - min_a[0] < max_b[0] - min_b[0] ||
304                             max_a[1] - min_a[1] < max_b[1] - min_b[1])
305                         {
306                                 for (k = check_b; k <= cur_a; k++) {
307                                         copy_v2_v2(feather_points[k], p);
308                                 }
309                         }
310                         else {
311                                 for (k = 0; k <= check_a; k++) {
312                                         copy_v2_v2(feather_points[k], p);
313                                 }
314
315                                 if (cur_b != 0) {
316                                         for (k = cur_b; k < tot_feather_point; k++) {
317                                                 copy_v2_v2(feather_points[k], p);
318                                         }
319                                 }
320                         }
321                 }
322         }
323 }
324
325 static int feather_bucket_index_from_coord(float co[2], const float min[2], const float bucket_scale[2],
326                                            const int buckets_per_side)
327 {
328         int x = (int) ((co[0] - min[0]) * bucket_scale[0]);
329         int y = (int) ((co[1] - min[1]) * bucket_scale[1]);
330
331         if (x == buckets_per_side)
332                 x--;
333
334         if (y == buckets_per_side)
335                 y--;
336
337         return y * buckets_per_side + x;
338 }
339
340 static void feather_bucket_get_diagonal(FeatherEdgesBucket *buckets, int start_bucket_index, int end_bucket_index,
341                                         int buckets_per_side, FeatherEdgesBucket **diagonal_bucket_a_r,
342                                         FeatherEdgesBucket **diagonal_bucket_b_r)
343 {
344         int start_bucket_x = start_bucket_index % buckets_per_side;
345         int start_bucket_y = start_bucket_index / buckets_per_side;
346
347         int end_bucket_x = end_bucket_index % buckets_per_side;
348         int end_bucket_y = end_bucket_index / buckets_per_side;
349
350         int diagonal_bucket_a_index = start_bucket_y * buckets_per_side + end_bucket_x;
351         int diagonal_bucket_b_index = end_bucket_y * buckets_per_side + start_bucket_x;
352
353         *diagonal_bucket_a_r = &buckets[diagonal_bucket_a_index];
354         *diagonal_bucket_b_r = &buckets[diagonal_bucket_b_index];
355 }
356
357 void BKE_mask_spline_feather_collapse_inner_loops(MaskSpline *spline, float (*feather_points)[2], const int tot_feather_point)
358 {
359 #define BUCKET_INDEX(co) \
360         feather_bucket_index_from_coord(co, min, bucket_scale, buckets_per_side)
361
362         int buckets_per_side, tot_bucket;
363         float bucket_size, bucket_scale[2];
364
365         FeatherEdgesBucket *buckets;
366
367         int i;
368         float min[2], max[2];
369         float max_delta_x = -1.0f, max_delta_y = -1.0f, max_delta;
370
371         if (tot_feather_point < 4) {
372                 /* self-intersection works only for quads at least,
373                  * in other cases polygon can't be self-intersecting anyway
374                  */
375
376                 return;
377         }
378
379         /* find min/max corners of mask to build buckets in that space */
380         INIT_MINMAX2(min, max);
381
382         for (i = 0; i < tot_feather_point; i++) {
383                 int next = i + 1;
384                 float delta;
385
386                 DO_MINMAX2(feather_points[i], min, max);
387
388                 if (next == tot_feather_point) {
389                         if (spline->flag & MASK_SPLINE_CYCLIC)
390                                 next = 0;
391                         else
392                                 break;
393                 }
394
395                 delta = fabsf(feather_points[i][0] - feather_points[next][0]);
396                 if (delta > max_delta_x)
397                         max_delta_x = delta;
398
399                 delta = fabsf(feather_points[i][1] - feather_points[next][1]);
400                 if (delta > max_delta_y)
401                         max_delta_y = delta;
402         }
403
404         /* prevent divisionsby zero by ensuring bounding box is not collapsed */
405         if (max[0] - min[0] < FLT_EPSILON) {
406                 max[0] += 0.01f;
407                 min[0] -= 0.01f;
408         }
409
410         if (max[1] - min[1] < FLT_EPSILON) {
411                 max[1] += 0.01f;
412                 min[1] -= 0.01f;
413         }
414
415         /* use dynamically calculated buckets per side, so we likely wouldn't
416          * run into a situation when segment doesn't fit two buckets which is
417          * pain collecting candidates for intersection
418          */
419
420         max_delta_x /= max[0] - min[0];
421         max_delta_y /= max[1] - min[1];
422
423         max_delta = MAX2(max_delta_x, max_delta_y);
424
425         buckets_per_side = MIN2(512, 0.9f / max_delta);
426
427         if (buckets_per_side == 0) {
428                 /* happens when some segment fills the whole bounding box across some of dimension */
429
430                 buckets_per_side = 1;
431         }
432
433         tot_bucket = buckets_per_side * buckets_per_side;
434         bucket_size = 1.0f / buckets_per_side;
435
436         /* pre-compute multipliers, to save mathematical operations in loops */
437         bucket_scale[0] = 1.0f / ((max[0] - min[0]) * bucket_size);
438         bucket_scale[1] = 1.0f / ((max[1] - min[1]) * bucket_size);
439
440         /* fill in buckets' edges */
441         buckets = MEM_callocN(sizeof(FeatherEdgesBucket) * tot_bucket, "feather buckets");
442
443         for (i = 0; i < tot_feather_point; i++) {
444                 int start = i, end = i + 1;
445                 int start_bucket_index, end_bucket_index;
446
447                 if (end == tot_feather_point) {
448                         if (spline->flag & MASK_SPLINE_CYCLIC)
449                                 end = 0;
450                         else
451                                 break;
452                 }
453
454                 start_bucket_index = BUCKET_INDEX(feather_points[start]);
455                 end_bucket_index = BUCKET_INDEX(feather_points[end]);
456
457                 feather_bucket_add_edge(&buckets[start_bucket_index], start, end);
458
459                 if (start_bucket_index != end_bucket_index) {
460                         FeatherEdgesBucket *end_bucket = &buckets[end_bucket_index];
461                         FeatherEdgesBucket *diagonal_bucket_a, *diagonal_bucket_b;
462
463                         feather_bucket_get_diagonal(buckets, start_bucket_index, end_bucket_index, buckets_per_side,
464                                                     &diagonal_bucket_a, &diagonal_bucket_b);
465
466                         feather_bucket_add_edge(end_bucket, start, end);
467                         feather_bucket_add_edge(diagonal_bucket_a, start, end);
468                         feather_bucket_add_edge(diagonal_bucket_a, start, end);
469                 }
470         }
471
472         /* check all edges for intersection with edges from their buckets */
473         for (i = 0; i < tot_feather_point; i++) {
474                 int cur_a = i, cur_b = i + 1;
475                 int start_bucket_index, end_bucket_index;
476
477                 FeatherEdgesBucket *start_bucket;
478
479                 if (cur_b == tot_feather_point)
480                         cur_b = 0;
481
482                 start_bucket_index = BUCKET_INDEX(feather_points[cur_a]);
483                 end_bucket_index = BUCKET_INDEX(feather_points[cur_b]);
484
485                 start_bucket = &buckets[start_bucket_index];
486
487                 feather_bucket_check_intersect(feather_points, tot_feather_point, start_bucket, cur_a, cur_b);
488
489                 if (start_bucket_index != end_bucket_index) {
490                         FeatherEdgesBucket *end_bucket = &buckets[end_bucket_index];
491                         FeatherEdgesBucket *diagonal_bucket_a, *diagonal_bucket_b;
492
493                         feather_bucket_get_diagonal(buckets, start_bucket_index, end_bucket_index, buckets_per_side,
494                                                     &diagonal_bucket_a, &diagonal_bucket_b);
495
496                         feather_bucket_check_intersect(feather_points, tot_feather_point, end_bucket, cur_a, cur_b);
497                         feather_bucket_check_intersect(feather_points, tot_feather_point, diagonal_bucket_a, cur_a, cur_b);
498                         feather_bucket_check_intersect(feather_points, tot_feather_point, diagonal_bucket_b, cur_a, cur_b);
499                 }
500         }
501
502         /* free buckets */
503         for (i = 0; i < tot_bucket; i++) {
504                 if (buckets[i].segments)
505                         MEM_freeN(buckets[i].segments);
506         }
507
508         MEM_freeN(buckets);
509
510 #undef BUCKET_INDEX
511 }
512
513 /**
514  * values align with #BKE_mask_spline_differentiate_with_resolution_ex
515  * when \a resol arguments match.
516  */
517 float (*BKE_mask_spline_feather_differentiated_points_with_resolution_ex(MaskSpline *spline,
518                                                                          int *tot_feather_point,
519                                                                          const unsigned int resol,
520                                                                          const int do_feather_isect
521                                                                          ))[2]
522 {
523         MaskSplinePoint *points_array = BKE_mask_spline_point_array(spline);
524         MaskSplinePoint *point, *prev;
525         float (*feather)[2], (*fp)[2];
526
527         const int tot = BKE_mask_spline_differentiate_calc_total(spline, resol);
528         int a;
529
530         /* tot+1 because of 'forward_diff_bezier' function */
531         feather = fp = MEM_mallocN((tot + 1) * sizeof(*feather), "mask spline feather diff points");
532
533         a = spline->tot_point - 1;
534         if (spline->flag & MASK_SPLINE_CYCLIC)
535                 a++;
536
537         prev = points_array;
538         point = prev + 1;
539
540         while (a--) {
541                 /* BezTriple *prevbezt; */  /* UNUSED */
542                 /* BezTriple *bezt; */      /* UNUSED */
543                 int j;
544
545                 if (a == 0 && (spline->flag & MASK_SPLINE_CYCLIC))
546                         point = points_array;
547
548
549                 /* prevbezt = &prev->bezt; */
550                 /* bezt = &point->bezt; */
551
552                 for (j = 0; j < resol; j++, fp++) {
553                         float u = (float) j / resol, weight;
554                         float co[2], n[2];
555
556                         /* TODO - these calls all calculate similar things
557                          * could be unified for some speed */
558                         BKE_mask_point_segment_co(spline, prev, u, co);
559                         BKE_mask_point_normal(spline, prev, u, n);
560                         weight = BKE_mask_point_weight(spline, prev, u);
561
562                         madd_v2_v2v2fl(*fp, co, n, weight);
563                 }
564
565                 if (a == 0 && (spline->flag & MASK_SPLINE_CYCLIC) == 0) {
566                         float u = 1.0f, weight;
567                         float co[2], n[2];
568
569                         BKE_mask_point_segment_co(spline, prev, u, co);
570                         BKE_mask_point_normal(spline, prev, u, n);
571                         weight = BKE_mask_point_weight(spline, prev, u);
572
573                         madd_v2_v2v2fl(*fp, co, n, weight);
574                 }
575
576                 prev = point;
577                 point++;
578         }
579
580         *tot_feather_point = tot;
581
582         if ((spline->flag & MASK_SPLINE_NOINTERSECT) && do_feather_isect) {
583                 BKE_mask_spline_feather_collapse_inner_loops(spline, feather, tot);
584         }
585
586         return feather;
587 }
588
589 float (*BKE_mask_spline_feather_differentiated_points_with_resolution(MaskSpline *spline, int width, int height,
590                                                                       int *tot_feather_point, const int do_feather_isect))[2]
591 {
592         unsigned int resol = BKE_mask_spline_feather_resolution(spline, width, height);
593
594         return BKE_mask_spline_feather_differentiated_points_with_resolution_ex(spline, tot_feather_point, resol, do_feather_isect);
595 }
596
597 float (*BKE_mask_spline_feather_differentiated_points(MaskSpline *spline, int *tot_feather_point))[2]
598 {
599         return BKE_mask_spline_feather_differentiated_points_with_resolution(spline, 0, 0, tot_feather_point, TRUE);
600 }
601
602 float (*BKE_mask_spline_feather_points(MaskSpline *spline, int *tot_feather_point))[2]
603 {
604         MaskSplinePoint *points_array = BKE_mask_spline_point_array(spline);
605
606         int i, tot = 0;
607         float (*feather)[2], (*fp)[2];
608
609         /* count */
610         for (i = 0; i < spline->tot_point; i++) {
611                 MaskSplinePoint *point = &points_array[i];
612
613                 tot += point->tot_uw + 1;
614         }
615
616         /* create data */
617         feather = fp = MEM_mallocN(tot * sizeof(*feather), "mask spline feather points");
618
619         for (i = 0; i < spline->tot_point; i++) {
620                 MaskSplinePoint *point = &points_array[i];
621                 BezTriple *bezt = &point->bezt;
622                 float weight, n[2];
623                 int j;
624
625                 BKE_mask_point_normal(spline, point, 0.0f, n);
626                 weight = BKE_mask_point_weight(spline, point, 0.0f);
627
628                 madd_v2_v2v2fl(*fp, bezt->vec[1], n, weight);
629                 fp++;
630
631                 for (j = 0; j < point->tot_uw; j++) {
632                         float u = point->uw[j].u;
633                         float co[2];
634
635                         BKE_mask_point_segment_co(spline, point, u, co);
636                         BKE_mask_point_normal(spline, point, u, n);
637                         weight = BKE_mask_point_weight(spline, point, u);
638
639                         madd_v2_v2v2fl(*fp, co, n, weight);
640                         fp++;
641                 }
642         }
643
644         *tot_feather_point = tot;
645
646         return feather;
647 }