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