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