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