Cleanup: style, use braces for blenkernel
[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           }
494           if (xi_max >= layer->buckets_x) {
495             xi_max = layer->buckets_x - 1;
496           }
497           if (yi_min >= layer->buckets_y) {
498             yi_min = layer->buckets_y - 1;
499           }
500           if (yi_max >= layer->buckets_y) {
501             yi_max = layer->buckets_y - 1;
502           }
503
504           for (yi = yi_min; yi <= yi_max; yi++) {
505             unsigned int bucket_index = (layer->buckets_x * yi) + xi_min;
506             for (xi = xi_min; xi <= xi_max; xi++, bucket_index++) {
507               // unsigned int bucket_index = (layer->buckets_x * yi) + xi; /* correct but do in outer loop */
508
509               BLI_assert(xi < layer->buckets_x);
510               BLI_assert(yi < layer->buckets_y);
511               BLI_assert(bucket_index < bucket_tot);
512
513               /* check if the bucket intersects with the face */
514               /* note: there is a trade off here since checking box/tri intersections isn't
515                * as optimal as it could be, but checking pixels against faces they will never intersect
516                * with is likely the greater slowdown here - so check if the cell intersects the face */
517               if (layer_bucket_isect_test(layer,
518                                           face_index,
519                                           xi,
520                                           yi,
521                                           bucket_size_x,
522                                           bucket_size_y,
523                                           bucket_max_rad_squared)) {
524                 BLI_linklist_prepend_arena(&bucketstore[bucket_index], face_index_void, arena);
525                 bucketstore_tot[bucket_index]++;
526               }
527             }
528           }
529         }
530       }
531     }
532
533     if (1) {
534       /* now convert linknodes into arrays for faster per pixel access */
535       unsigned int **buckets_face = MEM_mallocN(bucket_tot * sizeof(*buckets_face), __func__);
536       unsigned int bucket_index;
537
538       for (bucket_index = 0; bucket_index < bucket_tot; bucket_index++) {
539         if (bucketstore_tot[bucket_index]) {
540           unsigned int *bucket = MEM_mallocN(
541               (bucketstore_tot[bucket_index] + 1) * sizeof(unsigned int), __func__);
542           LinkNode *bucket_node;
543
544           buckets_face[bucket_index] = bucket;
545
546           for (bucket_node = bucketstore[bucket_index]; bucket_node;
547                bucket_node = bucket_node->next) {
548             *bucket = POINTER_AS_UINT(bucket_node->link);
549             bucket++;
550           }
551           *bucket = TRI_TERMINATOR_ID;
552         }
553         else {
554           buckets_face[bucket_index] = NULL;
555         }
556       }
557
558       layer->buckets_face = buckets_face;
559     }
560
561     MEM_freeN(bucketstore);
562     MEM_freeN(bucketstore_tot);
563   }
564
565   BLI_memarena_free(arena);
566 }
567
568 void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle,
569                                    struct Mask *mask,
570                                    const int width,
571                                    const int height,
572                                    const bool do_aspect_correct,
573                                    const bool do_mask_aa,
574                                    const bool do_feather)
575 {
576   const rctf default_bounds = {0.0f, 1.0f, 0.0f, 1.0f};
577   const float pixel_size = 1.0f / (float)min_ii(width, height);
578   const float asp_xy[2] = {
579       (do_aspect_correct && width > height) ? (float)height / (float)width : 1.0f,
580       (do_aspect_correct && width < height) ? (float)width / (float)height : 1.0f};
581
582   const float zvec[3] = {0.0f, 0.0f, 1.0f};
583   MaskLayer *masklay;
584   unsigned int masklay_index;
585   MemArena *sf_arena;
586
587   mr_handle->layers_tot = (unsigned int)BLI_listbase_count(&mask->masklayers);
588   mr_handle->layers = MEM_mallocN(sizeof(MaskRasterLayer) * mr_handle->layers_tot,
589                                   "MaskRasterLayer");
590   BLI_rctf_init_minmax(&mr_handle->bounds);
591
592   sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
593
594   for (masklay = mask->masklayers.first, masklay_index = 0; masklay;
595        masklay = masklay->next, masklay_index++) {
596
597     /* we need to store vertex ranges for open splines for filling */
598     unsigned int tot_splines;
599     MaskRasterSplineInfo *open_spline_ranges;
600     unsigned int open_spline_index = 0;
601
602     MaskSpline *spline;
603
604     /* scanfill */
605     ScanFillContext sf_ctx;
606     ScanFillVert *sf_vert = NULL;
607     ScanFillVert *sf_vert_next = NULL;
608     ScanFillFace *sf_tri;
609
610     unsigned int sf_vert_tot = 0;
611     unsigned int tot_feather_quads = 0;
612
613 #ifdef USE_SCANFILL_EDGE_WORKAROUND
614     unsigned int tot_boundary_used = 0;
615     unsigned int tot_boundary_found = 0;
616 #endif
617
618     if (masklay->restrictflag & MASK_RESTRICT_RENDER) {
619       /* skip the layer */
620       mr_handle->layers_tot--;
621       masklay_index--;
622       continue;
623     }
624
625     tot_splines = (unsigned int)BLI_listbase_count(&masklay->splines);
626     open_spline_ranges = MEM_callocN(sizeof(*open_spline_ranges) * tot_splines, __func__);
627
628     BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
629
630     for (spline = masklay->splines.first; spline; spline = spline->next) {
631       const bool is_cyclic = (spline->flag & MASK_SPLINE_CYCLIC) != 0;
632       const bool is_fill = (spline->flag & MASK_SPLINE_NOFILL) == 0;
633
634       float(*diff_points)[2];
635       unsigned int tot_diff_point;
636
637       float(*diff_feather_points)[2];
638       float(*diff_feather_points_flip)[2];
639       unsigned int tot_diff_feather_points;
640
641       const unsigned int resol_a = BKE_mask_spline_resolution(spline, width, height) / 4;
642       const unsigned int resol_b = BKE_mask_spline_feather_resolution(spline, width, height) / 4;
643       const unsigned int resol = CLAMPIS(MAX2(resol_a, resol_b), 4, 512);
644
645       diff_points = BKE_mask_spline_differentiate_with_resolution(spline, &tot_diff_point, resol);
646
647       if (do_feather) {
648         diff_feather_points = BKE_mask_spline_feather_differentiated_points_with_resolution(
649             spline, &tot_diff_feather_points, resol, false);
650         BLI_assert(diff_feather_points);
651       }
652       else {
653         tot_diff_feather_points = 0;
654         diff_feather_points = NULL;
655       }
656
657       if (tot_diff_point > 3) {
658         ScanFillVert *sf_vert_prev;
659         unsigned int j;
660
661         float co[3];
662         co[2] = 0.0f;
663
664         sf_ctx.poly_nr++;
665
666         if (do_aspect_correct) {
667           if (width != height) {
668             float *fp;
669             float *ffp;
670             unsigned int i;
671             float asp;
672
673             if (width < height) {
674               fp = &diff_points[0][0];
675               ffp = tot_diff_feather_points ? &diff_feather_points[0][0] : NULL;
676               asp = (float)width / (float)height;
677             }
678             else {
679               fp = &diff_points[0][1];
680               ffp = tot_diff_feather_points ? &diff_feather_points[0][1] : NULL;
681               asp = (float)height / (float)width;
682             }
683
684             for (i = 0; i < tot_diff_point; i++, fp += 2) {
685               (*fp) = (((*fp) - 0.5f) / asp) + 0.5f;
686             }
687
688             if (tot_diff_feather_points) {
689               for (i = 0; i < tot_diff_feather_points; i++, ffp += 2) {
690                 (*ffp) = (((*ffp) - 0.5f) / asp) + 0.5f;
691               }
692             }
693           }
694         }
695
696         /* fake aa, using small feather */
697         if (do_mask_aa == true) {
698           if (do_feather == false) {
699             tot_diff_feather_points = tot_diff_point;
700             diff_feather_points = MEM_mallocN(
701                 sizeof(*diff_feather_points) * (size_t)tot_diff_feather_points, __func__);
702             /* add single pixel feather */
703             maskrasterize_spline_differentiate_point_outset(
704                 diff_feather_points, diff_points, tot_diff_point, pixel_size, false);
705           }
706           else {
707             /* ensure single pixel feather, on any zero feather areas */
708             maskrasterize_spline_differentiate_point_outset(
709                 diff_feather_points, diff_points, tot_diff_point, pixel_size, true);
710           }
711         }
712
713         if (is_fill) {
714           /* applt intersections depending on fill settings */
715           if (spline->flag & MASK_SPLINE_NOINTERSECT) {
716             BKE_mask_spline_feather_collapse_inner_loops(
717                 spline, diff_feather_points, tot_diff_feather_points);
718           }
719
720           copy_v2_v2(co, diff_points[0]);
721           sf_vert_prev = BLI_scanfill_vert_add(&sf_ctx, co);
722           sf_vert_prev->tmp.u = sf_vert_tot;
723           sf_vert_prev->keyindex = sf_vert_tot +
724                                    tot_diff_point; /* absolute index of feather vert */
725           sf_vert_tot++;
726
727           /* TODO, an alternate functions so we can avoid double vector copy! */
728           for (j = 1; j < tot_diff_point; j++) {
729             copy_v2_v2(co, diff_points[j]);
730             sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
731             sf_vert->tmp.u = sf_vert_tot;
732             sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
733             sf_vert_tot++;
734           }
735
736           sf_vert = sf_vert_prev;
737           sf_vert_prev = sf_ctx.fillvertbase.last;
738
739           for (j = 0; j < tot_diff_point; j++) {
740             ScanFillEdge *sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
741
742 #ifdef USE_SCANFILL_EDGE_WORKAROUND
743             if (diff_feather_points) {
744               sf_edge->tmp.c = SF_EDGE_IS_BOUNDARY;
745               tot_boundary_used++;
746             }
747 #else
748             (void)sf_edge;
749 #endif
750             sf_vert_prev = sf_vert;
751             sf_vert = sf_vert->next;
752           }
753
754           if (diff_feather_points) {
755             float co_feather[3];
756             co_feather[2] = 1.0f;
757
758             BLI_assert(tot_diff_feather_points == tot_diff_point);
759
760             /* note: only added for convenience, we don't infact use these to scanfill,
761              * only to create feather faces after scanfill */
762             for (j = 0; j < tot_diff_feather_points; j++) {
763               copy_v2_v2(co_feather, diff_feather_points[j]);
764               sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
765               sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
766               sf_vert_tot++;
767             }
768
769             tot_feather_quads += tot_diff_point;
770           }
771         }
772         else {
773           /* unfilled spline */
774           if (diff_feather_points) {
775
776             float co_diff[2];
777
778             float co_feather[3];
779             co_feather[2] = 1.0f;
780
781             if (spline->flag & MASK_SPLINE_NOINTERSECT) {
782               diff_feather_points_flip = MEM_mallocN(sizeof(float) * 2 * tot_diff_feather_points,
783                                                      "diff_feather_points_flip");
784
785               for (j = 0; j < tot_diff_point; j++) {
786                 sub_v2_v2v2(co_diff, diff_points[j], diff_feather_points[j]);
787                 add_v2_v2v2(diff_feather_points_flip[j], diff_points[j], co_diff);
788               }
789
790               BKE_mask_spline_feather_collapse_inner_loops(
791                   spline, diff_feather_points, tot_diff_feather_points);
792               BKE_mask_spline_feather_collapse_inner_loops(
793                   spline, diff_feather_points_flip, tot_diff_feather_points);
794             }
795             else {
796               diff_feather_points_flip = NULL;
797             }
798
799             open_spline_ranges[open_spline_index].vertex_offset = sf_vert_tot;
800             open_spline_ranges[open_spline_index].vertex_total = tot_diff_point;
801
802             /* TODO, an alternate functions so we can avoid double vector copy! */
803             for (j = 0; j < tot_diff_point; j++) {
804
805               /* center vert */
806               copy_v2_v2(co, diff_points[j]);
807               sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
808               sf_vert->tmp.u = sf_vert_tot;
809               sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
810               sf_vert_tot++;
811
812               /* feather vert A */
813               copy_v2_v2(co_feather, diff_feather_points[j]);
814               sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
815               sf_vert->tmp.u = sf_vert_tot;
816               sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
817               sf_vert_tot++;
818
819               /* feather vert B */
820               if (diff_feather_points_flip) {
821                 copy_v2_v2(co_feather, diff_feather_points_flip[j]);
822               }
823               else {
824                 sub_v2_v2v2(co_diff, co, co_feather);
825                 add_v2_v2v2(co_feather, co, co_diff);
826               }
827
828               sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
829               sf_vert->tmp.u = sf_vert_tot;
830               sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
831               sf_vert_tot++;
832
833               tot_feather_quads += 2;
834             }
835
836             if (!is_cyclic) {
837               tot_feather_quads -= 2;
838             }
839
840             if (diff_feather_points_flip) {
841               MEM_freeN(diff_feather_points_flip);
842               diff_feather_points_flip = NULL;
843             }
844
845             /* cap ends */
846
847             /* dummy init value */
848             open_spline_ranges[open_spline_index].vertex_total_cap_head = 0;
849             open_spline_ranges[open_spline_index].vertex_total_cap_tail = 0;
850
851             if (!is_cyclic) {
852               const float *fp_cent;
853               const float *fp_turn;
854
855               unsigned int k;
856
857               fp_cent = diff_points[0];
858               fp_turn = diff_feather_points[0];
859
860 #define CALC_CAP_RESOL \
861   clampis_uint( \
862       (unsigned int)(len_v2v2(fp_cent, fp_turn) / (pixel_size * SPLINE_RESOL_CAP_PER_PIXEL)), \
863       SPLINE_RESOL_CAP_MIN, \
864       SPLINE_RESOL_CAP_MAX)
865
866               {
867                 const unsigned int vertex_total_cap = CALC_CAP_RESOL;
868
869                 for (k = 1; k < vertex_total_cap; k++) {
870                   const float angle = (float)k * (1.0f / (float)vertex_total_cap) * (float)M_PI;
871                   rotate_point_v2(co_feather, fp_turn, fp_cent, angle, asp_xy);
872
873                   sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
874                   sf_vert->tmp.u = sf_vert_tot;
875                   sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
876                   sf_vert_tot++;
877                 }
878                 tot_feather_quads += vertex_total_cap;
879
880                 open_spline_ranges[open_spline_index].vertex_total_cap_head = vertex_total_cap;
881               }
882
883               fp_cent = diff_points[tot_diff_point - 1];
884               fp_turn = diff_feather_points[tot_diff_point - 1];
885
886               {
887                 const unsigned int vertex_total_cap = CALC_CAP_RESOL;
888
889                 for (k = 1; k < vertex_total_cap; k++) {
890                   const float angle = (float)k * (1.0f / (float)vertex_total_cap) * (float)M_PI;
891                   rotate_point_v2(co_feather, fp_turn, fp_cent, -angle, asp_xy);
892
893                   sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
894                   sf_vert->tmp.u = sf_vert_tot;
895                   sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
896                   sf_vert_tot++;
897                 }
898                 tot_feather_quads += vertex_total_cap;
899
900                 open_spline_ranges[open_spline_index].vertex_total_cap_tail = vertex_total_cap;
901               }
902             }
903
904             open_spline_ranges[open_spline_index].is_cyclic = is_cyclic;
905             open_spline_index++;
906
907 #undef CALC_CAP_RESOL
908             /* end capping */
909           }
910         }
911       }
912
913       if (diff_points) {
914         MEM_freeN(diff_points);
915       }
916
917       if (diff_feather_points) {
918         MEM_freeN(diff_feather_points);
919       }
920     }
921
922     {
923       unsigned int(*face_array)[4], *face; /* access coords */
924       float(*face_coords)[3], *cos;        /* xy, z 0-1 (1.0 == filled) */
925       unsigned int sf_tri_tot;
926       rctf bounds;
927       unsigned int face_index;
928       int scanfill_flag = 0;
929
930       bool is_isect = false;
931       ListBase isect_remvertbase = {NULL, NULL};
932       ListBase isect_remedgebase = {NULL, NULL};
933
934       /* now we have all the splines */
935       face_coords = MEM_mallocN((sizeof(float) * 3) * sf_vert_tot, "maskrast_face_coords");
936
937       /* init bounds */
938       BLI_rctf_init_minmax(&bounds);
939
940       /* coords */
941       cos = (float *)face_coords;
942       for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert_next) {
943         sf_vert_next = sf_vert->next;
944         copy_v3_v3(cos, sf_vert->co);
945
946         /* remove so as not to interfere with fill (called after) */
947         if (sf_vert->keyindex == SF_KEYINDEX_TEMP_ID) {
948           BLI_remlink(&sf_ctx.fillvertbase, sf_vert);
949         }
950
951         /* bounds */
952         BLI_rctf_do_minmax_v(&bounds, cos);
953
954         cos += 3;
955       }
956
957       /* --- inefficient self-intersect case --- */
958       /* if self intersections are found, its too trickty to attempt to map vertices
959        * so just realloc and add entirely new vertices - the result of the self-intersect check
960        */
961       if ((masklay->flag & MASK_LAYERFLAG_FILL_OVERLAP) &&
962           (is_isect = BLI_scanfill_calc_self_isect(
963                &sf_ctx, &isect_remvertbase, &isect_remedgebase))) {
964         unsigned int sf_vert_tot_isect = (unsigned int)BLI_listbase_count(&sf_ctx.fillvertbase);
965         unsigned int i = sf_vert_tot;
966
967         face_coords = MEM_reallocN(face_coords,
968                                    sizeof(float[3]) * (sf_vert_tot + sf_vert_tot_isect));
969
970         cos = (float *)&face_coords[sf_vert_tot][0];
971
972         for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert->next) {
973           copy_v3_v3(cos, sf_vert->co);
974           sf_vert->tmp.u = i++;
975           cos += 3;
976         }
977
978         sf_vert_tot += sf_vert_tot_isect;
979
980         /* we need to calc polys after self intersect */
981         scanfill_flag |= BLI_SCANFILL_CALC_POLYS;
982       }
983       /* --- end inefficient code --- */
984
985       /* main scan-fill */
986       if ((masklay->flag & MASK_LAYERFLAG_FILL_DISCRETE) == 0) {
987         scanfill_flag |= BLI_SCANFILL_CALC_HOLES;
988       }
989
990       sf_tri_tot = (unsigned int)BLI_scanfill_calc_ex(&sf_ctx, scanfill_flag, zvec);
991
992       if (is_isect) {
993         /* add removed data back, we only need edges for feather,
994          * but add verts back so they get freed along with others */
995         BLI_movelisttolist(&sf_ctx.fillvertbase, &isect_remvertbase);
996         BLI_movelisttolist(&sf_ctx.filledgebase, &isect_remedgebase);
997       }
998
999       face_array = MEM_mallocN(sizeof(*face_array) *
1000                                    ((size_t)sf_tri_tot + (size_t)tot_feather_quads),
1001                                "maskrast_face_index");
1002       face_index = 0;
1003
1004       /* faces */
1005       face = (unsigned int *)face_array;
1006       for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
1007         *(face++) = sf_tri->v3->tmp.u;
1008         *(face++) = sf_tri->v2->tmp.u;
1009         *(face++) = sf_tri->v1->tmp.u;
1010         *(face++) = TRI_VERT;
1011         face_index++;
1012         FACE_ASSERT(face - 4, sf_vert_tot);
1013       }
1014
1015       /* start of feather faces... if we have this set,
1016        * 'face_index' is kept from loop above */
1017
1018       BLI_assert(face_index == sf_tri_tot);
1019
1020       if (tot_feather_quads) {
1021         ScanFillEdge *sf_edge;
1022
1023         for (sf_edge = sf_ctx.filledgebase.first; sf_edge; sf_edge = sf_edge->next) {
1024           if (sf_edge->tmp.c == SF_EDGE_IS_BOUNDARY) {
1025             *(face++) = sf_edge->v1->tmp.u;
1026             *(face++) = sf_edge->v2->tmp.u;
1027             *(face++) = sf_edge->v2->keyindex;
1028             *(face++) = sf_edge->v1->keyindex;
1029             face_index++;
1030             FACE_ASSERT(face - 4, sf_vert_tot);
1031
1032 #ifdef USE_SCANFILL_EDGE_WORKAROUND
1033             tot_boundary_found++;
1034 #endif
1035           }
1036         }
1037       }
1038
1039 #ifdef USE_SCANFILL_EDGE_WORKAROUND
1040       if (tot_boundary_found != tot_boundary_used) {
1041         BLI_assert(tot_boundary_found < tot_boundary_used);
1042       }
1043 #endif
1044
1045       /* feather only splines */
1046       while (open_spline_index > 0) {
1047         const unsigned int vertex_offset = open_spline_ranges[--open_spline_index].vertex_offset;
1048         unsigned int vertex_total = open_spline_ranges[open_spline_index].vertex_total;
1049         unsigned int vertex_total_cap_head =
1050             open_spline_ranges[open_spline_index].vertex_total_cap_head;
1051         unsigned int vertex_total_cap_tail =
1052             open_spline_ranges[open_spline_index].vertex_total_cap_tail;
1053         unsigned int k, j;
1054
1055         j = vertex_offset;
1056
1057         /* subtract one since we reference next vertex triple */
1058         for (k = 0; k < vertex_total - 1; k++, j += 3) {
1059
1060           BLI_assert(j == vertex_offset + (k * 3));
1061
1062           *(face++) = j + 3; /* next span */ /* z 1 */
1063           *(face++) = j + 0;                 /* z 1 */
1064           *(face++) = j + 1;                 /* z 0 */
1065           *(face++) = j + 4; /* next span */ /* z 0 */
1066           face_index++;
1067           FACE_ASSERT(face - 4, sf_vert_tot);
1068
1069           *(face++) = j + 0;                 /* z 1 */
1070           *(face++) = j + 3; /* next span */ /* z 1 */
1071           *(face++) = j + 5; /* next span */ /* z 0 */
1072           *(face++) = j + 2;                 /* z 0 */
1073           face_index++;
1074           FACE_ASSERT(face - 4, sf_vert_tot);
1075         }
1076
1077         if (open_spline_ranges[open_spline_index].is_cyclic) {
1078           *(face++) = vertex_offset + 0; /* next span */ /* z 1 */
1079           *(face++) = j + 0;                             /* z 1 */
1080           *(face++) = j + 1;                             /* z 0 */
1081           *(face++) = vertex_offset + 1; /* next span */ /* z 0 */
1082           face_index++;
1083           FACE_ASSERT(face - 4, sf_vert_tot);
1084
1085           *(face++) = j + 0;                             /* z 1 */
1086           *(face++) = vertex_offset + 0; /* next span */ /* z 1 */
1087           *(face++) = vertex_offset + 2; /* next span */ /* z 0 */
1088           *(face++) = j + 2;                             /* z 0 */
1089           face_index++;
1090           FACE_ASSERT(face - 4, sf_vert_tot);
1091         }
1092         else {
1093           unsigned int midvidx = vertex_offset;
1094
1095           /***************
1096            * cap end 'a' */
1097           j = midvidx + (vertex_total * 3);
1098
1099           for (k = 0; k < vertex_total_cap_head - 2; k++, j++) {
1100             *(face++) = midvidx + 0; /* z 1 */
1101             *(face++) = midvidx + 0; /* z 1 */
1102             *(face++) = j + 0;       /* z 0 */
1103             *(face++) = j + 1;       /* z 0 */
1104             face_index++;
1105             FACE_ASSERT(face - 4, sf_vert_tot);
1106           }
1107
1108           j = vertex_offset + (vertex_total * 3);
1109
1110           /* 2 tris that join the original */
1111           *(face++) = midvidx + 0; /* z 1 */
1112           *(face++) = midvidx + 0; /* z 1 */
1113           *(face++) = midvidx + 1; /* z 0 */
1114           *(face++) = j + 0;       /* z 0 */
1115           face_index++;
1116           FACE_ASSERT(face - 4, sf_vert_tot);
1117
1118           *(face++) = midvidx + 0;                   /* z 1 */
1119           *(face++) = midvidx + 0;                   /* z 1 */
1120           *(face++) = j + vertex_total_cap_head - 2; /* z 0 */
1121           *(face++) = midvidx + 2;                   /* z 0 */
1122           face_index++;
1123           FACE_ASSERT(face - 4, sf_vert_tot);
1124
1125           /***************
1126            * cap end 'b' */
1127           /* ... same as previous but v 2-3 flipped, and different initial offsets */
1128
1129           j = vertex_offset + (vertex_total * 3) + (vertex_total_cap_head - 1);
1130
1131           midvidx = vertex_offset + (vertex_total * 3) - 3;
1132
1133           for (k = 0; k < vertex_total_cap_tail - 2; k++, j++) {
1134             *(face++) = midvidx; /* z 1 */
1135             *(face++) = midvidx; /* z 1 */
1136             *(face++) = j + 1;   /* z 0 */
1137             *(face++) = j + 0;   /* z 0 */
1138             face_index++;
1139             FACE_ASSERT(face - 4, sf_vert_tot);
1140           }
1141
1142           j = vertex_offset + (vertex_total * 3) + (vertex_total_cap_head - 1);
1143
1144           /* 2 tris that join the original */
1145           *(face++) = midvidx + 0; /* z 1 */
1146           *(face++) = midvidx + 0; /* z 1 */
1147           *(face++) = j + 0;       /* z 0 */
1148           *(face++) = midvidx + 1; /* z 0 */
1149           face_index++;
1150           FACE_ASSERT(face - 4, sf_vert_tot);
1151
1152           *(face++) = midvidx + 0;                   /* z 1 */
1153           *(face++) = midvidx + 0;                   /* z 1 */
1154           *(face++) = midvidx + 2;                   /* z 0 */
1155           *(face++) = j + vertex_total_cap_tail - 2; /* z 0 */
1156           face_index++;
1157           FACE_ASSERT(face - 4, sf_vert_tot);
1158         }
1159       }
1160
1161       MEM_freeN(open_spline_ranges);
1162
1163       //          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);
1164
1165 #ifdef USE_SCANFILL_EDGE_WORKAROUND
1166       BLI_assert(face_index + (tot_boundary_used - tot_boundary_found) ==
1167                  sf_tri_tot + tot_feather_quads);
1168 #else
1169       BLI_assert(face_index == sf_tri_tot + tot_feather_quads);
1170 #endif
1171       {
1172         MaskRasterLayer *layer = &mr_handle->layers[masklay_index];
1173
1174         if (BLI_rctf_isect(&default_bounds, &bounds, &bounds)) {
1175 #ifdef USE_SCANFILL_EDGE_WORKAROUND
1176           layer->face_tot = (sf_tri_tot + tot_feather_quads) -
1177                             (tot_boundary_used - tot_boundary_found);
1178 #else
1179           layer->face_tot = (sf_tri_tot + tot_feather_quads);
1180 #endif
1181           layer->face_coords = face_coords;
1182           layer->face_array = face_array;
1183           layer->bounds = bounds;
1184
1185           layer_bucket_init(layer, pixel_size);
1186
1187           BLI_rctf_union(&mr_handle->bounds, &bounds);
1188         }
1189         else {
1190           MEM_freeN(face_coords);
1191           MEM_freeN(face_array);
1192
1193           layer_bucket_init_dummy(layer);
1194         }
1195
1196         /* copy as-is */
1197         layer->alpha = masklay->alpha;
1198         layer->blend = masklay->blend;
1199         layer->blend_flag = masklay->blend_flag;
1200         layer->falloff = masklay->falloff;
1201       }
1202
1203       /* printf("tris %d, feather tris %d\n", sf_tri_tot, tot_feather_quads); */
1204     }
1205
1206     /* add trianges */
1207     BLI_scanfill_end_arena(&sf_ctx, sf_arena);
1208   }
1209
1210   BLI_memarena_free(sf_arena);
1211 }
1212
1213 /* --------------------------------------------------------------------- */
1214 /* functions that run inside the sampling thread (keep fast!)            */
1215 /* --------------------------------------------------------------------- */
1216
1217 /* 2D ray test */
1218 #if 0
1219 static float maskrasterize_layer_z_depth_tri(const float pt[2],
1220                                              const float v1[3],
1221                                              const float v2[3],
1222                                              const float v3[3])
1223 {
1224   float w[3];
1225   barycentric_weights_v2(v1, v2, v3, pt, w);
1226   return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]);
1227 }
1228 #endif
1229
1230 static float maskrasterize_layer_z_depth_quad(
1231     const float pt[2], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
1232 {
1233   float w[4];
1234   barycentric_weights_v2_quad(v1, v2, v3, v4, pt, w);
1235   //return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]) + (v4[2] * w[3]);
1236   return w[2] + w[3]; /* we can make this assumption for small speedup */
1237 }
1238
1239 static float maskrasterize_layer_isect(unsigned int *face,
1240                                        float (*cos)[3],
1241                                        const float dist_orig,
1242                                        const float xy[2])
1243 {
1244   /* we always cast from same place only need xy */
1245   if (face[3] == TRI_VERT) {
1246     /* --- tri --- */
1247
1248 #if 0
1249     /* not essential but avoids unneeded extra lookups */
1250     if ((cos[0][2] < dist_orig) || (cos[1][2] < dist_orig) || (cos[2][2] < dist_orig)) {
1251       if (isect_point_tri_v2_cw(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
1252         /* we know all tris are close for now */
1253         return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[1]], cos[face[2]]);
1254       }
1255     }
1256 #else
1257     /* we know all tris are close for now */
1258     if (isect_point_tri_v2_cw(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
1259       return 0.0f;
1260     }
1261 #endif
1262   }
1263   else {
1264     /* --- quad --- */
1265
1266     /* not essential but avoids unneeded extra lookups */
1267     if ((cos[0][2] < dist_orig) || (cos[1][2] < dist_orig) || (cos[2][2] < dist_orig) ||
1268         (cos[3][2] < dist_orig)) {
1269
1270       /* needs work */
1271 #if 1
1272       /* quad check fails for bow-tie, so keep using 2 tri checks */
1273       //if (isect_point_quad_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]], cos[face[3]]))
1274       if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]]) ||
1275           isect_point_tri_v2(xy, cos[face[0]], cos[face[2]], cos[face[3]])) {
1276         return maskrasterize_layer_z_depth_quad(
1277             xy, cos[face[0]], cos[face[1]], cos[face[2]], cos[face[3]]);
1278       }
1279 #elif 1
1280       /* don't use isect_point_tri_v2_cw because we could have bow-tie quads */
1281
1282       if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
1283         return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[1]], cos[face[2]]);
1284       }
1285       else if (isect_point_tri_v2(xy, cos[face[0]], cos[face[2]], cos[face[3]])) {
1286         return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[2]], cos[face[3]]);
1287       }
1288 #else
1289       /* cheat - we know first 2 verts are z0.0f and second 2 are z 1.0f */
1290       /* ... worth looking into */
1291 #endif
1292     }
1293   }
1294
1295   return 1.0f;
1296 }
1297
1298 BLI_INLINE unsigned int layer_bucket_index_from_xy(MaskRasterLayer *layer, const float xy[2])
1299 {
1300   BLI_assert(BLI_rctf_isect_pt_v(&layer->bounds, xy));
1301
1302   return ((unsigned int)((xy[0] - layer->bounds.xmin) * layer->buckets_xy_scalar[0])) +
1303          (((unsigned int)((xy[1] - layer->bounds.ymin) * layer->buckets_xy_scalar[1])) *
1304           layer->buckets_x);
1305 }
1306
1307 static float layer_bucket_depth_from_xy(MaskRasterLayer *layer, const float xy[2])
1308 {
1309   unsigned int index = layer_bucket_index_from_xy(layer, xy);
1310   unsigned int *face_index = layer->buckets_face[index];
1311
1312   if (face_index) {
1313     unsigned int(*face_array)[4] = layer->face_array;
1314     float(*cos)[3] = layer->face_coords;
1315     float best_dist = 1.0f;
1316     while (*face_index != TRI_TERMINATOR_ID) {
1317       const float test_dist = maskrasterize_layer_isect(
1318           face_array[*face_index], cos, best_dist, xy);
1319       if (test_dist < best_dist) {
1320         best_dist = test_dist;
1321         /* comparing with 0.0f is OK here because triangles are always zero depth */
1322         if (best_dist == 0.0f) {
1323           /* bail early, we're as close as possible */
1324           return 0.0f;
1325         }
1326       }
1327       face_index++;
1328     }
1329     return best_dist;
1330   }
1331   else {
1332     return 1.0f;
1333   }
1334 }
1335
1336 float BKE_maskrasterize_handle_sample(MaskRasterHandle *mr_handle, const float xy[2])
1337 {
1338   /* can't do this because some layers may invert */
1339   /* if (BLI_rctf_isect_pt_v(&mr_handle->bounds, xy)) */
1340
1341   const unsigned int layers_tot = mr_handle->layers_tot;
1342   unsigned int i;
1343   MaskRasterLayer *layer = mr_handle->layers;
1344
1345   /* return value */
1346   float value = 0.0f;
1347
1348   for (i = 0; i < layers_tot; i++, layer++) {
1349     float value_layer;
1350
1351     /* also used as signal for unused layer (when render is disabled) */
1352     if (layer->alpha != 0.0f && BLI_rctf_isect_pt_v(&layer->bounds, xy)) {
1353       value_layer = 1.0f - layer_bucket_depth_from_xy(layer, xy);
1354
1355       switch (layer->falloff) {
1356         case PROP_SMOOTH:
1357           /* ease - gives less hard lines for dilate/erode feather */
1358           value_layer = (3.0f * value_layer * value_layer -
1359                          2.0f * value_layer * value_layer * value_layer);
1360           break;
1361         case PROP_SPHERE:
1362           value_layer = sqrtf(2.0f * value_layer - value_layer * value_layer);
1363           break;
1364         case PROP_ROOT:
1365           value_layer = sqrtf(value_layer);
1366           break;
1367         case PROP_SHARP:
1368           value_layer = value_layer * value_layer;
1369           break;
1370         case PROP_INVSQUARE:
1371           value_layer = value_layer * (2.0f - value_layer);
1372           break;
1373         case PROP_LIN:
1374         default:
1375           /* nothing */
1376           break;
1377       }
1378
1379       if (layer->blend != MASK_BLEND_REPLACE) {
1380         value_layer *= layer->alpha;
1381       }
1382     }
1383     else {
1384       value_layer = 0.0f;
1385     }
1386
1387     if (layer->blend_flag & MASK_BLENDFLAG_INVERT) {
1388       value_layer = 1.0f - value_layer;
1389     }
1390
1391     switch (layer->blend) {
1392       case MASK_BLEND_MERGE_ADD:
1393         value += value_layer * (1.0f - value);
1394         break;
1395       case MASK_BLEND_MERGE_SUBTRACT:
1396         value -= value_layer * value;
1397         break;
1398       case MASK_BLEND_ADD:
1399         value += value_layer;
1400         break;
1401       case MASK_BLEND_SUBTRACT:
1402         value -= value_layer;
1403         break;
1404       case MASK_BLEND_LIGHTEN:
1405         value = max_ff(value, value_layer);
1406         break;
1407       case MASK_BLEND_DARKEN:
1408         value = min_ff(value, value_layer);
1409         break;
1410       case MASK_BLEND_MUL:
1411         value *= value_layer;
1412         break;
1413       case MASK_BLEND_REPLACE:
1414         value = (value * (1.0f - layer->alpha)) + (value_layer * layer->alpha);
1415         break;
1416       case MASK_BLEND_DIFFERENCE:
1417         value = fabsf(value - value_layer);
1418         break;
1419       default: /* same as add */
1420         CLOG_ERROR(&LOG, "unhandled blend type: %d", layer->blend);
1421         BLI_assert(0);
1422         value += value_layer;
1423         break;
1424     }
1425
1426     /* clamp after applying each layer so we don't get
1427      * issues subtracting after accumulating over 1.0f */
1428     CLAMP(value, 0.0f, 1.0f);
1429   }
1430
1431   return value;
1432 }
1433
1434 typedef struct MaskRasterizeBufferData {
1435   MaskRasterHandle *mr_handle;
1436   float x_inv, y_inv;
1437   float x_px_ofs, y_px_ofs;
1438   uint width;
1439
1440   float *buffer;
1441 } MaskRasterizeBufferData;
1442
1443 static void maskrasterize_buffer_cb(void *__restrict userdata,
1444                                     const int y,
1445                                     const ParallelRangeTLS *__restrict UNUSED(tls))
1446 {
1447   MaskRasterizeBufferData *data = userdata;
1448
1449   MaskRasterHandle *mr_handle = data->mr_handle;
1450   float *buffer = data->buffer;
1451
1452   const uint width = data->width;
1453   const float x_inv = data->x_inv;
1454   const float x_px_ofs = data->x_px_ofs;
1455
1456   uint i = (uint)y * width;
1457   float xy[2];
1458   xy[1] = ((float)y * data->y_inv) + data->y_px_ofs;
1459   for (uint x = 0; x < width; x++, i++) {
1460     xy[0] = ((float)x * x_inv) + x_px_ofs;
1461
1462     buffer[i] = BKE_maskrasterize_handle_sample(mr_handle, xy);
1463   }
1464 }
1465
1466 /**
1467  * \brief Rasterize a buffer from a single mask (threaded execution).
1468  */
1469 void BKE_maskrasterize_buffer(MaskRasterHandle *mr_handle,
1470                               const unsigned int width,
1471                               const unsigned int height,
1472                               float *buffer)
1473 {
1474   const float x_inv = 1.0f / (float)width;
1475   const float y_inv = 1.0f / (float)height;
1476
1477   MaskRasterizeBufferData data = {
1478       .mr_handle = mr_handle,
1479       .x_inv = x_inv,
1480       .y_inv = y_inv,
1481       .x_px_ofs = x_inv * 0.5f,
1482       .y_px_ofs = y_inv * 0.5f,
1483       .width = width,
1484       .buffer = buffer,
1485   };
1486   ParallelRangeSettings settings;
1487   BLI_parallel_range_settings_defaults(&settings);
1488   settings.use_threading = ((size_t)height * width > 10000);
1489   BLI_task_parallel_range(0, (int)height, &data, maskrasterize_buffer_cb, &settings);
1490 }