multi-threaded sequencer buffer calculation for masks.
[blender.git] / source / blender / blenkernel / intern / mask_rasterize.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  *                 Campbell Barton
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/blenkernel/intern/mask_rasterize.c
28  *  \ingroup bke
29  */
30
31 #include "MEM_guardedalloc.h"
32
33 #include "DNA_vec_types.h"
34 #include "DNA_mask_types.h"
35 #include "DNA_scene_types.h"
36
37 #include "BLI_utildefines.h"
38 #include "BLI_scanfill.h"
39 #include "BLI_memarena.h"
40
41 #include "BLI_math.h"
42 #include "BLI_rect.h"
43 #include "BLI_listbase.h"
44 #include "BLI_linklist.h"
45
46 #include "BKE_mask.h"
47
48 /* this is rather and annoying hack, use define to isolate it.
49  * problem is caused by scanfill removing edges on us. */
50 #define USE_SCANFILL_EDGE_WORKAROUND
51
52 #define SPLINE_RESOL_CAP_PER_PIXEL 2
53 #define SPLINE_RESOL_CAP_MIN 8
54 #define SPLINE_RESOL_CAP_MAX 64
55
56 /* found this gives best performance for high detail masks, values between 2 and 8 work best */
57 #define BUCKET_PIXELS_PER_CELL 4
58
59 #define SF_EDGE_IS_BOUNDARY 0xff
60 #define SF_KEYINDEX_TEMP_ID ((unsigned int) -1)
61
62 #define TRI_TERMINATOR_ID   ((unsigned int) -1)
63 #define TRI_VERT            ((unsigned int) -1)
64
65 /* for debugging add... */
66 #ifndef NDEBUG
67 /*      printf("%u %u %u %u\n", _t[0], _t[1], _t[2], _t[3]); \ */
68 #  define FACE_ASSERT(face, vert_max)                    \
69 {                                                        \
70         unsigned int *_t = face;                             \
71         BLI_assert(_t[0] < vert_max);                        \
72         BLI_assert(_t[1] < vert_max);                        \
73         BLI_assert(_t[2] < vert_max);                        \
74         BLI_assert(_t[3] < vert_max || _t[3] == TRI_VERT);   \
75 } (void)0
76 #else
77    /* do nothing */
78 #  define FACE_ASSERT(face, vert_max)
79 #endif
80
81 static void rotate_point_v2(float r_p[2], const float p[2], const float cent[2], const float angle, const float asp[2])
82 {
83         const float s = sinf(angle);
84         const float c = cosf(angle);
85         float p_new[2];
86
87         /* translate point back to origin */
88         r_p[0] = (p[0] - cent[0]) / asp[0];
89         r_p[1] = (p[1] - cent[1]) / asp[1];
90
91         /* rotate point */
92         p_new[0] = ((r_p[0] * c) - (r_p[1] * s)) * asp[0];
93         p_new[1] = ((r_p[0] * s) + (r_p[1] * c)) * asp[1];
94
95         /* translate point back */
96         r_p[0] = p_new[0] + cent[0];
97         r_p[1] = p_new[1] + cent[1];
98 }
99
100 BLI_INLINE unsigned int clampis_uint(const unsigned int v, const unsigned int min, const unsigned int max)
101 {
102         return v < min ? min : (v > max ? max : v);
103 }
104
105 /* --------------------------------------------------------------------- */
106 /* local structs for mask rasterizeing                                   */
107 /* --------------------------------------------------------------------- */
108
109 /**
110  * A single #MaskRasterHandle contains multiple #MaskRasterLayer's,
111  * each #MaskRasterLayer does its own lookup which contributes to
112  * the final pixel with its own blending mode and the final pixel
113  * is blended between these.
114  */
115
116 /* internal use only */
117 typedef struct MaskRasterLayer {
118         /* geometry */
119         unsigned int   face_tot;
120         unsigned int (*face_array)[4];  /* access coords tri/quad */
121         float        (*face_coords)[3]; /* xy, z 0-1 (1.0 == filled) */
122
123
124         /* 2d bounds (to quickly skip bucket lookup) */
125         rctf bounds;
126
127
128         /* buckets */
129         unsigned int **buckets_face;
130         /* cache divide and subtract */
131         float buckets_xy_scalar[2]; /* (1.0 / (buckets_width + FLT_EPSILON)) * buckets_x */
132         unsigned int buckets_x;
133         unsigned int buckets_y;
134
135
136         /* copied direct from #MaskLayer.--- */
137         /* blending options */
138         float  alpha;
139         char   blend;
140         char   blend_flag;
141         char   falloff;
142
143 } MaskRasterLayer;
144
145 typedef struct MaskRasterSplineInfo {
146         /* body of the spline */
147         unsigned int vertex_offset;
148         unsigned int vertex_total;
149
150         /* capping for non-filled, non cyclic splines */
151         unsigned int vertex_total_cap_head;
152         unsigned int vertex_total_cap_tail;
153
154         unsigned int is_cyclic;
155 } MaskRasterSplineInfo;
156
157 /**
158  * opaque local struct for mask pixel lookup, each MaskLayer needs one of these
159  */
160 struct MaskRasterHandle {
161         MaskRasterLayer *layers;
162         unsigned int     layers_tot;
163
164         /* 2d bounds (to quickly skip bucket lookup) */
165         rctf bounds;
166 };
167
168 /* --------------------------------------------------------------------- */
169 /* alloc / free functions                                                */
170 /* --------------------------------------------------------------------- */
171
172 MaskRasterHandle *BKE_maskrasterize_handle_new(void)
173 {
174         MaskRasterHandle *mr_handle;
175
176         mr_handle = MEM_callocN(sizeof(MaskRasterHandle), STRINGIFY(MaskRasterHandle));
177
178         return mr_handle;
179 }
180
181 void BKE_maskrasterize_handle_free(MaskRasterHandle *mr_handle)
182 {
183         const unsigned int layers_tot = mr_handle->layers_tot;
184         unsigned int i;
185         MaskRasterLayer *layer = mr_handle->layers;
186
187         for (i = 0; i < layers_tot; i++, layer++) {
188
189                 if (layer->face_array) {
190                         MEM_freeN(layer->face_array);
191                 }
192
193                 if (layer->face_coords) {
194                         MEM_freeN(layer->face_coords);
195                 }
196
197                 if (layer->buckets_face) {
198                         const unsigned int   bucket_tot = layer->buckets_x * layer->buckets_y;
199                         unsigned int bucket_index;
200                         for (bucket_index = 0; bucket_index < bucket_tot; bucket_index++) {
201                                 unsigned int *face_index = layer->buckets_face[bucket_index];
202                                 if (face_index) {
203                                         MEM_freeN(face_index);
204                                 }
205                         }
206
207                         MEM_freeN(layer->buckets_face);
208                 }
209         }
210
211         MEM_freeN(mr_handle->layers);
212         MEM_freeN(mr_handle);
213 }
214
215
216 void maskrasterize_spline_differentiate_point_outset(float (*diff_feather_points)[2], float (*diff_points)[2],
217                                                      const unsigned int tot_diff_point, const float ofs,
218                                                      const short do_test)
219 {
220         unsigned int k_prev = tot_diff_point - 2;
221         unsigned int k_curr = tot_diff_point - 1;
222         unsigned int k_next = 0;
223
224         unsigned int k;
225
226         float d_prev[2];
227         float d_next[2];
228         float d[2];
229
230         const float *co_prev;
231         const float *co_curr;
232         const float *co_next;
233
234         const float ofs_squared = ofs * ofs;
235
236         co_prev = diff_points[k_prev];
237         co_curr = diff_points[k_curr];
238         co_next = diff_points[k_next];
239
240         /* precalc */
241         sub_v2_v2v2(d_prev, co_prev, co_curr);
242         normalize_v2(d_prev);
243
244         for (k = 0; k < tot_diff_point; k++) {
245
246                 /* co_prev = diff_points[k_prev]; */ /* precalc */
247                 co_curr = diff_points[k_curr];
248                 co_next = diff_points[k_next];
249
250                 /* sub_v2_v2v2(d_prev, co_prev, co_curr); */ /* precalc */
251                 sub_v2_v2v2(d_next, co_curr, co_next);
252
253                 /* normalize_v2(d_prev); */ /* precalc */
254                 normalize_v2(d_next);
255
256                 if ((do_test == FALSE) ||
257                     (len_squared_v2v2(diff_feather_points[k], diff_points[k]) < ofs_squared))
258                 {
259
260                         add_v2_v2v2(d, d_prev, d_next);
261
262                         normalize_v2(d);
263
264                         diff_feather_points[k][0] = diff_points[k][0] + ( d[1] * ofs);
265                         diff_feather_points[k][1] = diff_points[k][1] + (-d[0] * ofs);
266                 }
267
268                 /* use next iter */
269                 copy_v2_v2(d_prev, d_next);
270
271                 /* k_prev = k_curr; */ /* precalc */
272                 k_curr = k_next;
273                 k_next++;
274         }
275 }
276
277 /* this function is not exact, sometimes it returns false positives,
278  * the main point of it is to clear out _almost_ all bucket/face non-intersections,
279  * returning TRUE in corner cases is ok but missing an intersection is NOT.
280  *
281  * method used
282  * - check if the center of the buckets bounding box is intersecting the face
283  * - if not get the max radius to a corner of the bucket and see how close we
284  *   are to any of the triangle edges.
285  */
286 static int layer_bucket_isect_test(MaskRasterLayer *layer, unsigned int face_index,
287                                    const unsigned int bucket_x, const unsigned int bucket_y,
288                                    const float bucket_size_x, const float bucket_size_y,
289                                    const float bucket_max_rad_squared)
290 {
291         unsigned int *face = layer->face_array[face_index];
292         float (*cos)[3] = layer->face_coords;
293
294         const float xmin = layer->bounds.xmin + (bucket_size_x * bucket_x);
295         const float ymin = layer->bounds.ymin + (bucket_size_y * bucket_y);
296         const float xmax = xmin + bucket_size_x;
297         const float ymax = ymin + bucket_size_y;
298
299         const float cent[2] = {(xmin + xmax) * 0.5f,
300                                (ymin + ymax) * 0.5f};
301
302         if (face[3] == TRI_VERT) {
303                 const float *v1 = cos[face[0]];
304                 const float *v2 = cos[face[1]];
305                 const float *v3 = cos[face[2]];
306
307                 if (isect_point_tri_v2(cent, v1, v2, v3)) {
308                         return TRUE;
309                 }
310                 else {
311                         if ((dist_squared_to_line_segment_v2(cent, v1, v2) < bucket_max_rad_squared) ||
312                                 (dist_squared_to_line_segment_v2(cent, v2, v3) < bucket_max_rad_squared) ||
313                                 (dist_squared_to_line_segment_v2(cent, v3, v1) < bucket_max_rad_squared))
314                         {
315                                 return TRUE;
316                         }
317                         else {
318                                 // printf("skip tri\n");
319                                 return FALSE;
320                         }
321                 }
322
323         }
324         else {
325                 const float *v1 = cos[face[0]];
326                 const float *v2 = cos[face[1]];
327                 const float *v3 = cos[face[2]];
328                 const float *v4 = cos[face[3]];
329
330                 if (isect_point_tri_v2(cent, v1, v2, v3)) {
331                         return TRUE;
332                 }
333                 else if (isect_point_tri_v2(cent, v1, v3, v4)) {
334                         return TRUE;
335                 }
336                 else {
337                         if ((dist_squared_to_line_segment_v2(cent, v1, v2) < bucket_max_rad_squared) ||
338                             (dist_squared_to_line_segment_v2(cent, v2, v3) < bucket_max_rad_squared) ||
339                             (dist_squared_to_line_segment_v2(cent, v3, v4) < bucket_max_rad_squared) ||
340                             (dist_squared_to_line_segment_v2(cent, v4, v1) < bucket_max_rad_squared))
341                         {
342                                 return TRUE;
343                         }
344                         else {
345                                 // printf("skip quad\n");
346                                 return FALSE;
347                         }
348                 }
349         }
350 }
351
352 static void layer_bucket_init_dummy(MaskRasterLayer *layer)
353 {
354         layer->face_tot = 0;
355         layer->face_coords = NULL;
356         layer->face_array  = NULL;
357
358         layer->buckets_x = 0;
359         layer->buckets_y = 0;
360
361         layer->buckets_xy_scalar[0] = 0.0f;
362         layer->buckets_xy_scalar[1] = 0.0f;
363
364         layer->buckets_face = NULL;
365
366         BLI_rctf_init(&layer->bounds, -1.0f, -1.0f, -1.0f, -1.0f);
367 }
368
369 static void layer_bucket_init(MaskRasterLayer *layer, const float pixel_size)
370 {
371         MemArena *arena = BLI_memarena_new(1 << 16, __func__);
372
373         const float bucket_dim_x = layer->bounds.xmax - layer->bounds.xmin;
374         const float bucket_dim_y = layer->bounds.ymax - layer->bounds.ymin;
375
376         layer->buckets_x = (bucket_dim_x / pixel_size) / (float)BUCKET_PIXELS_PER_CELL;
377         layer->buckets_y = (bucket_dim_y / pixel_size) / (float)BUCKET_PIXELS_PER_CELL;
378
379 //              printf("bucket size %ux%u\n", layer->buckets_x, layer->buckets_y);
380
381         CLAMP(layer->buckets_x, 8, 512);
382         CLAMP(layer->buckets_y, 8, 512);
383
384         layer->buckets_xy_scalar[0] = (1.0f / (bucket_dim_x + FLT_EPSILON)) * layer->buckets_x;
385         layer->buckets_xy_scalar[1] = (1.0f / (bucket_dim_y + FLT_EPSILON)) * layer->buckets_y;
386
387         {
388                 /* width and height of each bucket */
389                 const float bucket_size_x = (bucket_dim_x + FLT_EPSILON) / layer->buckets_x;
390                 const float bucket_size_y = (bucket_dim_y + FLT_EPSILON) / layer->buckets_y;
391                 const float bucket_max_rad = (maxf(bucket_size_x, bucket_size_y) * M_SQRT2) + FLT_EPSILON;
392                 const float bucket_max_rad_squared = bucket_max_rad * bucket_max_rad;
393
394                 unsigned int *face = &layer->face_array[0][0];
395                 float (*cos)[3] = layer->face_coords;
396
397                 const unsigned int  bucket_tot = layer->buckets_x * layer->buckets_y;
398                 LinkNode     **bucketstore     = MEM_callocN(bucket_tot * sizeof(LinkNode *),  __func__);
399                 unsigned int  *bucketstore_tot = MEM_callocN(bucket_tot * sizeof(unsigned int), __func__);
400
401                 unsigned int face_index;
402
403                 for (face_index = 0; face_index < layer->face_tot; face_index++, face += 4) {
404                         float xmin;
405                         float xmax;
406                         float ymin;
407                         float ymax;
408
409                         if (face[3] == TRI_VERT) {
410                                 const float *v1 = cos[face[0]];
411                                 const float *v2 = cos[face[1]];
412                                 const float *v3 = cos[face[2]];
413
414                                 xmin = minf(v1[0], minf(v2[0], v3[0]));
415                                 xmax = maxf(v1[0], maxf(v2[0], v3[0]));
416                                 ymin = minf(v1[1], minf(v2[1], v3[1]));
417                                 ymax = maxf(v1[1], maxf(v2[1], v3[1]));
418                         }
419                         else {
420                                 const float *v1 = cos[face[0]];
421                                 const float *v2 = cos[face[1]];
422                                 const float *v3 = cos[face[2]];
423                                 const float *v4 = cos[face[3]];
424
425                                 xmin = minf(v1[0], minf(v2[0], minf(v3[0], v4[0])));
426                                 xmax = maxf(v1[0], maxf(v2[0], maxf(v3[0], v4[0])));
427                                 ymin = minf(v1[1], minf(v2[1], minf(v3[1], v4[1])));
428                                 ymax = maxf(v1[1], maxf(v2[1], maxf(v3[1], v4[1])));
429                         }
430
431
432                         /* not essential but may as will skip any faces outside the view */
433                         if (!((xmax < 0.0f) || (ymax < 0.0f) || (xmin > 1.0f) || (ymin > 1.0f))) {
434
435                                 CLAMP(xmin, 0.0f,  1.0f);
436                                 CLAMP(ymin, 0.0f,  1.0f);
437                                 CLAMP(xmax, 0.0f,  1.0f);
438                                 CLAMP(ymax, 0.0f,  1.0f);
439
440                                 {
441                                         unsigned int xi_min = (unsigned int) ((xmin - layer->bounds.xmin) * layer->buckets_xy_scalar[0]);
442                                         unsigned int xi_max = (unsigned int) ((xmax - layer->bounds.xmin) * layer->buckets_xy_scalar[0]);
443                                         unsigned int yi_min = (unsigned int) ((ymin - layer->bounds.ymin) * layer->buckets_xy_scalar[1]);
444                                         unsigned int yi_max = (unsigned int) ((ymax - layer->bounds.ymin) * layer->buckets_xy_scalar[1]);
445                                         void *face_index_void = SET_UINT_IN_POINTER(face_index);
446
447                                         unsigned int xi, yi;
448
449                                         /* this should _almost_ never happen but since it can in extreme cases,
450                                          * we have to clamp the values or we overrun the buffer and crash */
451                                         CLAMP(xi_min, 0, layer->buckets_x - 1);
452                                         CLAMP(xi_max, 0, layer->buckets_x - 1);
453                                         CLAMP(yi_min, 0, layer->buckets_y - 1);
454                                         CLAMP(yi_max, 0, layer->buckets_y - 1);
455
456                                         for (yi = yi_min; yi <= yi_max; yi++) {
457                                                 unsigned int bucket_index = (layer->buckets_x * yi) + xi_min;
458                                                 for (xi = xi_min; xi <= xi_max; xi++, bucket_index++) {
459                                                         // unsigned int bucket_index = (layer->buckets_x * yi) + xi; /* correct but do in outer loop */
460
461                                                         BLI_assert(xi < layer->buckets_x);
462                                                         BLI_assert(yi < layer->buckets_y);
463                                                         BLI_assert(bucket_index < bucket_tot);
464
465                                                         /* check if the bucket intersects with the face */
466                                                         /* note: there is a tradeoff here since checking box/tri intersections isn't
467                                                          * as optimal as it could be, but checking pixels against faces they will never intersect
468                                                          * with is likely the greater slowdown here - so check if the cell intersects the face */
469                                                         if (layer_bucket_isect_test(layer, face_index,
470                                                                                     xi, yi,
471                                                                                     bucket_size_x, bucket_size_y,
472                                                                                     bucket_max_rad_squared))
473                                                         {
474                                                                 BLI_linklist_prepend_arena(&bucketstore[bucket_index], face_index_void, arena);
475                                                                 bucketstore_tot[bucket_index]++;
476                                                         }
477                                                 }
478                                         }
479                                 }
480                         }
481                 }
482
483                 if (1) {
484                         /* now convert linknodes into arrays for faster per pixel access */
485                         unsigned int  **buckets_face = MEM_mallocN(bucket_tot * sizeof(unsigned int **), __func__);
486                         unsigned int bucket_index;
487
488                         for (bucket_index = 0; bucket_index < bucket_tot; bucket_index++) {
489                                 if (bucketstore_tot[bucket_index]) {
490                                         unsigned int  *bucket = MEM_mallocN((bucketstore_tot[bucket_index] + 1) * sizeof(unsigned int),
491                                                                             __func__);
492                                         LinkNode *bucket_node;
493
494                                         buckets_face[bucket_index] = bucket;
495
496                                         for (bucket_node = bucketstore[bucket_index]; bucket_node; bucket_node = bucket_node->next) {
497                                                 *bucket = GET_UINT_FROM_POINTER(bucket_node->link);
498                                                 bucket++;
499                                         }
500                                         *bucket = TRI_TERMINATOR_ID;
501                                 }
502                                 else {
503                                         buckets_face[bucket_index] = NULL;
504                                 }
505                         }
506
507                         layer->buckets_face = buckets_face;
508                 }
509
510                 MEM_freeN(bucketstore);
511                 MEM_freeN(bucketstore_tot);
512         }
513
514         BLI_memarena_free(arena);
515 }
516
517 void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mask,
518                                    const int width, const int height,
519                                    const short do_aspect_correct, const short do_mask_aa,
520                                    const short do_feather)
521 {
522         const rctf default_bounds = {0.0f, 1.0f, 0.0f, 1.0f};
523         const float pixel_size = 1.0f / MIN2(width, height);
524         const float asp_xy[2] = {(do_aspect_correct && width > height) ? (float)height / (float)width  : 1.0f,
525                                  (do_aspect_correct && width < height) ? (float)width  / (float)height : 1.0f};
526
527         const float zvec[3] = {0.0f, 0.0f, 1.0f};
528         MaskLayer *masklay;
529         unsigned int masklay_index;
530
531         mr_handle->layers_tot = BLI_countlist(&mask->masklayers);
532         mr_handle->layers = MEM_mallocN(sizeof(MaskRasterLayer) * mr_handle->layers_tot, STRINGIFY(MaskRasterLayer));
533         BLI_rctf_init_minmax(&mr_handle->bounds);
534
535         for (masklay = mask->masklayers.first, masklay_index = 0; masklay; masklay = masklay->next, masklay_index++) {
536
537                 /* we need to store vertex ranges for open splines for filling */
538                 unsigned int tot_splines;
539                 MaskRasterSplineInfo *open_spline_ranges;
540                 unsigned int   open_spline_index = 0;
541
542                 MaskSpline *spline;
543
544                 /* scanfill */
545                 ScanFillContext sf_ctx;
546                 ScanFillVert *sf_vert = NULL;
547                 ScanFillVert *sf_vert_next = NULL;
548                 ScanFillFace *sf_tri;
549
550                 unsigned int sf_vert_tot = 0;
551                 unsigned int tot_feather_quads = 0;
552
553 #ifdef USE_SCANFILL_EDGE_WORKAROUND
554                 unsigned int tot_boundary_used = 0;
555                 unsigned int tot_boundary_found = 0;
556 #endif
557
558                 if (masklay->restrictflag & MASK_RESTRICT_RENDER) {
559                         /* skip the layer */
560                         mr_handle->layers_tot--;
561                         masklay_index--;
562                         continue;
563                 }
564
565                 tot_splines = BLI_countlist(&masklay->splines);
566                 open_spline_ranges = MEM_callocN(sizeof(*open_spline_ranges) * tot_splines, __func__);
567
568                 BLI_scanfill_begin(&sf_ctx);
569
570                 for (spline = masklay->splines.first; spline; spline = spline->next) {
571                         const unsigned int is_cyclic = (spline->flag & MASK_SPLINE_CYCLIC) != 0;
572                         const unsigned int is_fill = (spline->flag & MASK_SPLINE_NOFILL) == 0;
573
574                         float (*diff_points)[2];
575                         int tot_diff_point;
576
577                         float (*diff_feather_points)[2];
578                         int tot_diff_feather_points;
579
580                         const int resol_a = BKE_mask_spline_resolution(spline, width, height) / 4;
581                         const int resol_b = BKE_mask_spline_feather_resolution(spline, width, height) / 4;
582                         const int resol = CLAMPIS(MAX2(resol_a, resol_b), 4, 512);
583
584                         diff_points = BKE_mask_spline_differentiate_with_resolution_ex(
585                                           spline, &tot_diff_point, resol);
586
587                         if (do_feather) {
588                                 diff_feather_points = BKE_mask_spline_feather_differentiated_points_with_resolution_ex(
589                                                           spline, &tot_diff_feather_points, resol, TRUE);
590                                 BLI_assert(diff_feather_points);
591                         }
592                         else {
593                                 tot_diff_feather_points = 0;
594                                 diff_feather_points = NULL;
595                         }
596
597                         if (tot_diff_point > 3) {
598                                 ScanFillVert *sf_vert_prev;
599                                 int j;
600
601                                 float co[3];
602                                 co[2] = 0.0f;
603
604                                 if (do_aspect_correct) {
605                                         if (width != height) {
606                                                 float *fp;
607                                                 float *ffp;
608                                                 int i;
609                                                 float asp;
610
611                                                 if (width < height) {
612                                                         fp = &diff_points[0][0];
613                                                         ffp = tot_diff_feather_points ? &diff_feather_points[0][0] : NULL;
614                                                         asp = (float)width / (float)height;
615                                                 }
616                                                 else {
617                                                         fp = &diff_points[0][1];
618                                                         ffp = tot_diff_feather_points ? &diff_feather_points[0][1] : NULL;
619                                                         asp = (float)height / (float)width;
620                                                 }
621
622                                                 for (i = 0; i < tot_diff_point; i++, fp += 2) {
623                                                         (*fp) = (((*fp) - 0.5f) / asp) + 0.5f;
624                                                 }
625
626                                                 if (tot_diff_feather_points) {
627                                                         for (i = 0; i < tot_diff_feather_points; i++, ffp += 2) {
628                                                                 (*ffp) = (((*ffp) - 0.5f) / asp) + 0.5f;
629                                                         }
630                                                 }
631                                         }
632                                 }
633
634                                 /* fake aa, using small feather */
635                                 if (do_mask_aa == TRUE) {
636                                         if (do_feather == FALSE) {
637                                                 tot_diff_feather_points = tot_diff_point;
638                                                 diff_feather_points = MEM_mallocN(sizeof(*diff_feather_points) * tot_diff_feather_points,
639                                                                                   __func__);
640                                                 /* add single pixel feather */
641                                                 maskrasterize_spline_differentiate_point_outset(diff_feather_points, diff_points,
642                                                                                                tot_diff_point, pixel_size, FALSE);
643                                         }
644                                         else {
645                                                 /* ensure single pixel feather, on any zero feather areas */
646                                                 maskrasterize_spline_differentiate_point_outset(diff_feather_points, diff_points,
647                                                                                                tot_diff_point, pixel_size, TRUE);
648                                         }
649                                 }
650
651                                 if (is_fill) {
652                                         copy_v2_v2(co, diff_points[0]);
653                                         sf_vert_prev = BLI_scanfill_vert_add(&sf_ctx, co);
654                                         sf_vert_prev->tmp.u = sf_vert_tot;
655                                         sf_vert_prev->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
656                                         sf_vert_tot++;
657
658                                         /* TODO, an alternate functions so we can avoid double vector copy! */
659                                         for (j = 1; j < tot_diff_point; j++) {
660                                                 copy_v2_v2(co, diff_points[j]);
661                                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
662                                                 sf_vert->tmp.u = sf_vert_tot;
663                                                 sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
664                                                 sf_vert_tot++;
665                                         }
666
667                                         sf_vert = sf_vert_prev;
668                                         sf_vert_prev = sf_ctx.fillvertbase.last;
669
670                                         for (j = 0; j < tot_diff_point; j++) {
671                                                 ScanFillEdge *sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
672
673 #ifdef USE_SCANFILL_EDGE_WORKAROUND
674                                                 if (diff_feather_points) {
675                                                         sf_edge->tmp.c = SF_EDGE_IS_BOUNDARY;
676                                                         tot_boundary_used++;
677                                                 }
678 #else
679                                                 (void)sf_edge;
680 #endif
681                                                 sf_vert_prev = sf_vert;
682                                                 sf_vert = sf_vert->next;
683                                         }
684
685                                         if (diff_feather_points) {
686                                                 float co_feather[3];
687                                                 co_feather[2] = 1.0f;
688
689                                                 BLI_assert(tot_diff_feather_points == tot_diff_point);
690
691                                                 /* note: only added for convenience, we don't infact use these to scanfill,
692                                                  * only to create feather faces after scanfill */
693                                                 for (j = 0; j < tot_diff_feather_points; j++) {
694                                                         copy_v2_v2(co_feather, diff_feather_points[j]);
695                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
696
697                                                         /* no need for these attrs */
698         #if 0
699                                                         sf_vert->tmp.u = sf_vert_tot;
700                                                         sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
701         #endif
702                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
703                                                         sf_vert_tot++;
704                                                 }
705
706                                                 tot_feather_quads += tot_diff_point;
707                                         }
708                                 }
709                                 else {
710                                         /* unfilled spline */
711                                         if (diff_feather_points) {
712
713                                                 float co_diff[3];
714
715                                                 float co_feather[3];
716                                                 co_feather[2] = 1.0f;
717
718                                                 open_spline_ranges[open_spline_index].vertex_offset = sf_vert_tot;
719                                                 open_spline_ranges[open_spline_index].vertex_total = tot_diff_point;
720
721                                                 /* TODO, an alternate functions so we can avoid double vector copy! */
722                                                 for (j = 0; j < tot_diff_point; j++) {
723
724                                                         /* center vert */
725                                                         copy_v2_v2(co, diff_points[j]);
726                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
727                                                         sf_vert->tmp.u = sf_vert_tot;
728                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
729                                                         sf_vert_tot++;
730
731
732                                                         /* feather vert A */
733                                                         copy_v2_v2(co_feather, diff_feather_points[j]);
734                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
735                                                         sf_vert->tmp.u = sf_vert_tot;
736                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
737                                                         sf_vert_tot++;
738
739
740                                                         /* feather vert B */
741                                                         sub_v2_v2v2(co_diff, co, co_feather);
742                                                         add_v2_v2v2(co_feather, co, co_diff);
743                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
744                                                         sf_vert->tmp.u = sf_vert_tot;
745                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
746                                                         sf_vert_tot++;
747
748                                                         tot_feather_quads += 2;
749                                                 }
750
751                                                 if (!is_cyclic) {
752                                                         tot_feather_quads -= 2;
753                                                 }
754
755                                                 /* cap ends */
756
757                                                 /* dummy init value */
758                                                 open_spline_ranges[open_spline_index].vertex_total_cap_head = 0;
759                                                 open_spline_ranges[open_spline_index].vertex_total_cap_tail = 0;
760
761                                                 if (!is_cyclic) {
762                                                         float *fp_cent;
763                                                         float *fp_turn;
764
765                                                         unsigned int k;
766
767                                                         fp_cent = diff_points[0];
768                                                         fp_turn = diff_feather_points[0];
769
770 #define CALC_CAP_RESOL                                                                      \
771         clampis_uint((len_v2v2(fp_cent, fp_turn) / (pixel_size * SPLINE_RESOL_CAP_PER_PIXEL)),  \
772                      SPLINE_RESOL_CAP_MIN,                                                      \
773                      SPLINE_RESOL_CAP_MAX)
774
775                                                         {
776                                                                 const unsigned int vertex_total_cap = CALC_CAP_RESOL;
777
778                                                                 for (k = 1; k < vertex_total_cap; k++) {
779                                                                         const float angle = (float)k * (1.0f / vertex_total_cap) * (float)M_PI;
780                                                                         rotate_point_v2(co_feather, fp_turn, fp_cent, angle, asp_xy);
781
782                                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
783                                                                         sf_vert->tmp.u = sf_vert_tot;
784                                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
785                                                                         sf_vert_tot++;
786                                                                 }
787                                                                 tot_feather_quads += vertex_total_cap;
788
789                                                                 open_spline_ranges[open_spline_index].vertex_total_cap_head = vertex_total_cap;
790                                                         }
791
792                                                         fp_cent = diff_points[tot_diff_point - 1];
793                                                         fp_turn = diff_feather_points[tot_diff_point - 1];
794
795                                                         {
796                                                                 const unsigned int vertex_total_cap = CALC_CAP_RESOL;
797
798                                                                 for (k = 1; k < vertex_total_cap; k++) {
799                                                                         const float angle = (float)k * (1.0f / vertex_total_cap) * (float)M_PI;
800                                                                         rotate_point_v2(co_feather, fp_turn, fp_cent, -angle, asp_xy);
801
802                                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
803                                                                         sf_vert->tmp.u = sf_vert_tot;
804                                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
805                                                                         sf_vert_tot++;
806                                                                 }
807                                                                 tot_feather_quads += vertex_total_cap;
808
809                                                                 open_spline_ranges[open_spline_index].vertex_total_cap_tail = vertex_total_cap;
810                                                         }
811                                                 }
812
813                                                 open_spline_ranges[open_spline_index].is_cyclic = is_cyclic;
814                                                 open_spline_index++;
815
816 #undef CALC_CAP_RESOL
817                                                 /* end capping */
818
819                                         }
820                                 }
821                         }
822
823                         if (diff_points) {
824                                 MEM_freeN(diff_points);
825                         }
826
827                         if (diff_feather_points) {
828                                 MEM_freeN(diff_feather_points);
829                         }
830                 }
831
832                 {
833                         unsigned int (*face_array)[4], *face;  /* access coords */
834                         float        (*face_coords)[3], *cos; /* xy, z 0-1 (1.0 == filled) */
835                         int sf_tri_tot;
836                         rctf bounds;
837                         int face_index;
838
839                         /* now we have all the splines */
840                         face_coords = MEM_mallocN((sizeof(float) * 3) * sf_vert_tot, "maskrast_face_coords");
841
842                         /* init bounds */
843                         BLI_rctf_init_minmax(&bounds);
844
845                         /* coords */
846                         cos = (float *)face_coords;
847                         for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert_next) {
848                                 sf_vert_next = sf_vert->next;
849                                 copy_v3_v3(cos, sf_vert->co);
850
851                                 /* remove so as not to interfere with fill (called after) */
852                                 if (sf_vert->keyindex == SF_KEYINDEX_TEMP_ID) {
853                                         BLI_remlink(&sf_ctx.fillvertbase, sf_vert);
854                                 }
855
856                                 /* bounds */
857                                 BLI_rctf_do_minmax_v(&bounds, cos);
858
859                                 cos += 3;
860                         }
861
862                         /* main scan-fill */
863                         sf_tri_tot = BLI_scanfill_calc_ex(&sf_ctx, FALSE, zvec);
864
865                         face_array = MEM_mallocN(sizeof(*face_array) * (sf_tri_tot + tot_feather_quads), "maskrast_face_index");
866                         face_index = 0;
867
868                         /* faces */
869                         face = (unsigned int *)face_array;
870                         for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
871                                 *(face++) = sf_tri->v3->tmp.u;
872                                 *(face++) = sf_tri->v2->tmp.u;
873                                 *(face++) = sf_tri->v1->tmp.u;
874                                 *(face++) = TRI_VERT;
875                                 face_index++;
876                                 FACE_ASSERT(face - 4, sf_vert_tot);
877                         }
878
879                         /* start of feather faces... if we have this set,
880                          * 'face_index' is kept from loop above */
881
882                         BLI_assert(face_index == sf_tri_tot);
883
884                         if (tot_feather_quads) {
885                                 ScanFillEdge *sf_edge;
886
887                                 for (sf_edge = sf_ctx.filledgebase.first; sf_edge; sf_edge = sf_edge->next) {
888                                         if (sf_edge->tmp.c == SF_EDGE_IS_BOUNDARY) {
889                                                 *(face++) = sf_edge->v1->tmp.u;
890                                                 *(face++) = sf_edge->v2->tmp.u;
891                                                 *(face++) = sf_edge->v2->keyindex;
892                                                 *(face++) = sf_edge->v1->keyindex;
893                                                 face_index++;
894                                                 FACE_ASSERT(face - 4, sf_vert_tot);
895
896 #ifdef USE_SCANFILL_EDGE_WORKAROUND
897                                                 tot_boundary_found++;
898 #endif
899                                         }
900                                 }
901                         }
902
903 #ifdef USE_SCANFILL_EDGE_WORKAROUND
904                         if (tot_boundary_found != tot_boundary_used) {
905                                 BLI_assert(tot_boundary_found < tot_boundary_used);
906                         }
907 #endif
908
909                         /* feather only splines */
910                         while (open_spline_index > 0) {
911                                 const unsigned int vertex_offset         = open_spline_ranges[--open_spline_index].vertex_offset;
912                                 unsigned int       vertex_total          = open_spline_ranges[  open_spline_index].vertex_total;
913                                 unsigned int       vertex_total_cap_head = open_spline_ranges[  open_spline_index].vertex_total_cap_head;
914                                 unsigned int       vertex_total_cap_tail = open_spline_ranges[  open_spline_index].vertex_total_cap_tail;
915                                 unsigned int k, j;
916
917                                 j = vertex_offset;
918
919                                 /* subtract one since we reference next vertex triple */
920                                 for (k = 0; k < vertex_total - 1; k++, j += 3) {
921
922                                         BLI_assert(j == vertex_offset + (k * 3));
923
924                                         *(face++) = j + 3; /* next span */ /* z 1 */
925                                         *(face++) = j + 0;                 /* z 1 */
926                                         *(face++) = j + 1;                 /* z 0 */
927                                         *(face++) = j + 4; /* next span */ /* z 0 */
928                                         face_index++;
929                                         FACE_ASSERT(face - 4, sf_vert_tot);
930
931                                         *(face++) = j + 0;                 /* z 1 */
932                                         *(face++) = j + 3; /* next span */ /* z 1 */
933                                         *(face++) = j + 5; /* next span */ /* z 0 */
934                                         *(face++) = j + 2;                 /* z 0 */
935                                         face_index++;
936                                         FACE_ASSERT(face - 4, sf_vert_tot);
937                                 }
938
939                                 if (open_spline_ranges[open_spline_index].is_cyclic) {
940                                         *(face++) = vertex_offset + 0; /* next span */ /* z 1 */
941                                         *(face++) = j             + 0;                 /* z 1 */
942                                         *(face++) = j             + 1;                 /* z 0 */
943                                         *(face++) = vertex_offset + 1; /* next span */ /* z 0 */
944                                         face_index++;
945                                         FACE_ASSERT(face - 4, sf_vert_tot);
946
947                                         *(face++) = j          + 0;                    /* z 1 */
948                                         *(face++) = vertex_offset + 0; /* next span */ /* z 1 */
949                                         *(face++) = vertex_offset + 2; /* next span */ /* z 0 */
950                                         *(face++) = j          + 2;                    /* z 0 */
951                                         face_index++;
952                                         FACE_ASSERT(face - 4, sf_vert_tot);
953                                 }
954                                 else {
955                                         unsigned int midvidx = vertex_offset;
956
957                                         /***************
958                                          * cap end 'a' */
959                                         j = midvidx + (vertex_total * 3);
960
961                                         for (k = 0; k < vertex_total_cap_head - 2; k++, j++) {
962                                                 *(face++) = midvidx + 0;  /* z 1 */
963                                                 *(face++) = midvidx + 0;  /* z 1 */
964                                                 *(face++) = j + 0;        /* z 0 */
965                                                 *(face++) = j + 1;        /* z 0 */
966                                                 face_index++;
967                                                 FACE_ASSERT(face - 4, sf_vert_tot);
968                                         }
969
970                                         j = vertex_offset + (vertex_total * 3);
971
972                                         /* 2 tris that join the original */
973                                         *(face++) = midvidx + 0;  /* z 1 */
974                                         *(face++) = midvidx + 0;  /* z 1 */
975                                         *(face++) = midvidx + 1;  /* z 0 */
976                                         *(face++) = j + 0;        /* z 0 */
977                                         face_index++;
978                                         FACE_ASSERT(face - 4, sf_vert_tot);
979
980                                         *(face++) = midvidx + 0;                    /* z 1 */
981                                         *(face++) = midvidx + 0;                    /* z 1 */
982                                         *(face++) = j + vertex_total_cap_head - 2;  /* z 0 */
983                                         *(face++) = midvidx + 2;                    /* z 0 */
984                                         face_index++;
985                                         FACE_ASSERT(face - 4, sf_vert_tot);
986
987
988                                         /***************
989                                          * cap end 'b' */
990                                         /* ... same as previous but v 2-3 flipped, and different initial offsets */
991
992                                         j = vertex_offset + (vertex_total * 3) + (vertex_total_cap_head - 1);
993
994                                         midvidx = vertex_offset + (vertex_total * 3) - 3;
995
996                                         for (k = 0; k < vertex_total_cap_tail - 2; k++, j++) {
997                                                 *(face++) = midvidx;  /* z 1 */
998                                                 *(face++) = midvidx;  /* z 1 */
999                                                 *(face++) = j + 1;    /* z 0 */
1000                                                 *(face++) = j + 0;    /* z 0 */
1001                                                 face_index++;
1002                                                 FACE_ASSERT(face - 4, sf_vert_tot);
1003                                         }
1004
1005                                         j = vertex_offset + (vertex_total * 3) + (vertex_total_cap_head - 1);
1006
1007                                         /* 2 tris that join the original */
1008                                         *(face++) = midvidx + 0;  /* z 1 */
1009                                         *(face++) = midvidx + 0;  /* z 1 */
1010                                         *(face++) = j + 0;        /* z 0 */
1011                                         *(face++) = midvidx + 1;  /* z 0 */
1012                                         face_index++;
1013                                         FACE_ASSERT(face - 4, sf_vert_tot);
1014
1015                                         *(face++) = midvidx + 0;                    /* z 1 */
1016                                         *(face++) = midvidx + 0;                    /* z 1 */
1017                                         *(face++) = midvidx + 2;                    /* z 0 */
1018                                         *(face++) = j + vertex_total_cap_tail - 2;  /* z 0 */
1019                                         face_index++;
1020                                         FACE_ASSERT(face - 4, sf_vert_tot);
1021
1022                                 }
1023                         }
1024
1025                         MEM_freeN(open_spline_ranges);
1026
1027 //                      fprintf(stderr, "%u %u (%u %u), %u\n", face_index, sf_tri_tot + tot_feather_quads, sf_tri_tot, tot_feather_quads, tot_boundary_used - tot_boundary_found);
1028
1029 #ifdef USE_SCANFILL_EDGE_WORKAROUND
1030                         BLI_assert(face_index + (tot_boundary_used - tot_boundary_found) == sf_tri_tot + tot_feather_quads);
1031 #else
1032                         BLI_assert(face_index == sf_tri_tot + tot_feather_quads);
1033 #endif
1034                         {
1035                                 MaskRasterLayer *layer = &mr_handle->layers[masklay_index];
1036
1037                                 if (BLI_rctf_isect(&default_bounds, &bounds, &bounds)) {
1038 #ifdef USE_SCANFILL_EDGE_WORKAROUND
1039                                         layer->face_tot = (sf_tri_tot + tot_feather_quads) - (tot_boundary_used - tot_boundary_found);
1040 #else
1041                                         layer->face_tot = (sf_tri_tot + tot_feather_quads);
1042 #endif
1043                                         layer->face_coords = face_coords;
1044                                         layer->face_array  = face_array;
1045                                         layer->bounds = bounds;
1046
1047                                         layer_bucket_init(layer, pixel_size);
1048
1049                                         BLI_rctf_union(&mr_handle->bounds, &bounds);
1050                                 }
1051                                 else {
1052                                         MEM_freeN(face_coords);
1053                                         MEM_freeN(face_array);
1054
1055                                         layer_bucket_init_dummy(layer);
1056                                 }
1057
1058                                 /* copy as-is */
1059                                 layer->alpha = masklay->alpha;
1060                                 layer->blend = masklay->blend;
1061                                 layer->blend_flag = masklay->blend_flag;
1062                                 layer->falloff = masklay->falloff;
1063                         }
1064
1065                         /* printf("tris %d, feather tris %d\n", sf_tri_tot, tot_feather_quads); */
1066                 }
1067
1068                 /* add trianges */
1069                 BLI_scanfill_end(&sf_ctx);
1070         }
1071 }
1072
1073
1074 /* --------------------------------------------------------------------- */
1075 /* functions that run inside the sampling thread (keep fast!)            */
1076 /* --------------------------------------------------------------------- */
1077
1078 /* 2D ray test */
1079 #if 0
1080 static float maskrasterize_layer_z_depth_tri(const float pt[2],
1081                                              const float v1[3], const float v2[3], const float v3[3])
1082 {
1083         float w[3];
1084         barycentric_weights_v2(v1, v2, v3, pt, w);
1085         return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]);
1086 }
1087 #endif
1088
1089 #if 1
1090 static float maskrasterize_layer_z_depth_quad(const float pt[2],
1091                                               const float v1[3], const float v2[3], const float v3[3], const float v4[3])
1092 {
1093         float w[4];
1094         barycentric_weights_v2_quad(v1, v2, v3, v4, pt, w);
1095         //return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]) + (v4[2] * w[3]);
1096         return w[2] + w[3];  /* we can make this assumption for small speedup */
1097 }
1098 #endif
1099
1100 static float maskrasterize_layer_isect(unsigned int *face, float (*cos)[3], const float dist_orig, const float xy[2])
1101 {
1102         /* we always cast from same place only need xy */
1103         if (face[3] == TRI_VERT) {
1104                 /* --- tri --- */
1105
1106 #if 0
1107                 /* not essential but avoids unneeded extra lookups */
1108                 if ((cos[0][2] < dist_orig) ||
1109                     (cos[1][2] < dist_orig) ||
1110                     (cos[2][2] < dist_orig))
1111                 {
1112                         if (isect_point_tri_v2_cw(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
1113                                 /* we know all tris are close for now */
1114                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[1]], cos[face[2]]);
1115                         }
1116                 }
1117 #else
1118                 /* we know all tris are close for now */
1119                 if (1) {
1120                         if (isect_point_tri_v2_cw(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
1121                                 return 0.0f;
1122                         }
1123                 }
1124 #endif
1125         }
1126         else {
1127                 /* --- quad --- */
1128
1129                 /* not essential but avoids unneeded extra lookups */
1130                 if ((cos[0][2] < dist_orig) ||
1131                     (cos[1][2] < dist_orig) ||
1132                     (cos[2][2] < dist_orig) ||
1133                     (cos[3][2] < dist_orig))
1134                 {
1135
1136                         /* needs work */
1137 #if 1
1138                         /* quad check fails for bowtie, so keep using 2 tri checks */
1139                         //if (isect_point_quad_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]], cos[face[3]]))
1140                         if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]]) ||
1141                             isect_point_tri_v2(xy, cos[face[0]], cos[face[2]], cos[face[3]]))
1142                         {
1143                                 return maskrasterize_layer_z_depth_quad(xy, cos[face[0]], cos[face[1]], cos[face[2]], cos[face[3]]);
1144                         }
1145 #elif 1
1146                         /* don't use isect_point_tri_v2_cw because we could have bowtie quads */
1147
1148                         if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
1149                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[1]], cos[face[2]]);
1150                         }
1151                         else if (isect_point_tri_v2(xy, cos[face[0]], cos[face[2]], cos[face[3]])) {
1152                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[2]], cos[face[3]]);
1153                         }
1154 #else
1155                         /* cheat - we know first 2 verts are z0.0f and second 2 are z 1.0f */
1156                         /* ... worth looking into */
1157 #endif
1158                 }
1159         }
1160
1161         return 1.0f;
1162 }
1163
1164 BLI_INLINE unsigned int layer_bucket_index_from_xy(MaskRasterLayer *layer, const float xy[2])
1165 {
1166         BLI_assert(BLI_in_rctf_v(&layer->bounds, xy));
1167
1168         return ( (unsigned int)((xy[0] - layer->bounds.xmin) * layer->buckets_xy_scalar[0])) +
1169                (((unsigned int)((xy[1] - layer->bounds.ymin) * layer->buckets_xy_scalar[1])) * layer->buckets_x);
1170 }
1171
1172 static float layer_bucket_depth_from_xy(MaskRasterLayer *layer, const float xy[2])
1173 {
1174         unsigned int index = layer_bucket_index_from_xy(layer, xy);
1175         unsigned int *face_index = layer->buckets_face[index];
1176
1177         if (face_index) {
1178                 unsigned int (*face_array)[4] = layer->face_array;
1179                 float        (*cos)[3]        = layer->face_coords;
1180                 float best_dist = 1.0f;
1181                 while (*face_index != TRI_TERMINATOR_ID) {
1182                         const float test_dist = maskrasterize_layer_isect(face_array[*face_index], cos, best_dist, xy);
1183                         if (test_dist < best_dist) {
1184                                 best_dist = test_dist;
1185                                 /* comparing with 0.0f is OK here because triangles are always zero depth */
1186                                 if (best_dist == 0.0f) {
1187                                         /* bail early, we're as close as possible */
1188                                         return 0.0f;
1189                                 }
1190                         }
1191                         face_index++;
1192                 }
1193                 return best_dist;
1194         }
1195         else {
1196                 return 1.0f;
1197         }
1198 }
1199
1200 float BKE_maskrasterize_handle_sample(MaskRasterHandle *mr_handle, const float xy[2])
1201 {
1202         /* can't do this because some layers may invert */
1203         /* if (BLI_in_rctf_v(&mr_handle->bounds, xy)) */
1204
1205         const unsigned int layers_tot = mr_handle->layers_tot;
1206         unsigned int i;
1207         MaskRasterLayer *layer = mr_handle->layers;
1208
1209         /* return value */
1210         float value = 0.0f;
1211
1212         for (i = 0; i < layers_tot; i++, layer++) {
1213                 float value_layer;
1214
1215                 /* also used as signal for unused layer (when render is disabled) */
1216                 if (layer->alpha != 0.0f && BLI_in_rctf_v(&layer->bounds, xy)) {
1217                         value_layer = 1.0f - layer_bucket_depth_from_xy(layer, xy);
1218
1219                         switch (layer->falloff) {
1220                                 case PROP_SMOOTH:
1221                                         /* ease - gives less hard lines for dilate/erode feather */
1222                                         value_layer = (3.0f * value_layer * value_layer - 2.0f * value_layer * value_layer * value_layer);
1223                                         break;
1224                                 case PROP_SPHERE:
1225                                         value_layer = sqrtf(2.0f * value_layer - value_layer * value_layer);
1226                                         break;
1227                                 case PROP_ROOT:
1228                                         value_layer = sqrtf(value_layer);
1229                                         break;
1230                                 case PROP_SHARP:
1231                                         value_layer = value_layer * value_layer;
1232                                         break;
1233                                 case PROP_LIN:
1234                                 default:
1235                                         /* nothing */
1236                                         break;
1237                         }
1238
1239                         if (layer->blend != MASK_BLEND_REPLACE) {
1240                                 value_layer *= layer->alpha;
1241                         }
1242                 }
1243                 else {
1244                         value_layer = 0.0f;
1245                 }
1246
1247                 if (layer->blend_flag & MASK_BLENDFLAG_INVERT) {
1248                         value_layer = 1.0f - value_layer;
1249                 }
1250
1251                 switch (layer->blend) {
1252                         case MASK_BLEND_MERGE:
1253                                 value += value_layer * (1.0f - value);
1254                                 break;
1255                         case MASK_BLEND_ADD:
1256                                 value += value_layer;
1257                                 break;
1258                         case MASK_BLEND_SUBTRACT:
1259                                 value -= value_layer;
1260                                 break;
1261                         case MASK_BLEND_LIGHTEN:
1262                                 value = maxf(value, value_layer);
1263                                 break;
1264                         case MASK_BLEND_DARKEN:
1265                                 value = minf(value, value_layer);
1266                                 break;
1267                         case MASK_BLEND_MUL:
1268                                 value *= value_layer;
1269                                 break;
1270                         case MASK_BLEND_REPLACE:
1271                                 value = (value * (1.0f - layer->alpha)) + (value_layer * layer->alpha);
1272                                 break;
1273                         case MASK_BLEND_DIFFERENCE:
1274                                 value = fabsf(value - value_layer);
1275                                 break;
1276                         default: /* same as add */
1277                                 BLI_assert(0);
1278                                 value += value_layer;
1279                                 break;
1280                 }
1281
1282                 /* clamp after applying each layer so we don't get
1283                  * issues subtracting after accumulating over 1.0f */
1284                 CLAMP(value, 0.0f, 1.0f);
1285         }
1286
1287         return value;
1288 }
1289
1290 /**
1291  * \brief Rasterize a buffer from a single mask
1292  *
1293  * We could get some speedup by inlining #BKE_maskrasterize_handle_sample
1294  * and calculating each layer then blending buffers, but this function is only
1295  * used by the sequencer - so better have the caller thread.
1296  *
1297  * Since #BKE_maskrasterize_handle_sample is used threaded elsewhere,
1298  * we can simply use openmp here for some speedup.
1299  */
1300 void BKE_maskrasterize_buffer(MaskRasterHandle *mr_handle,
1301                               const unsigned int width, const unsigned int height,
1302                               float *buffer)
1303 {
1304         unsigned int y;
1305
1306 #pragma omp parallel for private(y)
1307         for (y = 0; y < height; y++) {
1308                 unsigned int i = y * width;
1309                 unsigned int x;
1310                 float xy[2];
1311                 xy[1] = (float)y / (float)height;
1312                 for (x = 0; x < width; x++, i++) {
1313                         xy[0] = (float)x / (float)width;
1314
1315                         buffer[i] = BKE_maskrasterize_handle_sample(mr_handle, xy);
1316                 }
1317         }
1318 }