7b84abc3d36302c771e02ad356c92c5c814fbd44
[blender.git] / source / blender / blenkernel / intern / mask_rasterize.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2012 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation,
22  *                 Campbell Barton
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/blenkernel/intern/mask_rasterize.c
28  *  \ingroup bke
29  */
30
31 #include "MEM_guardedalloc.h"
32
33 #include "DNA_vec_types.h"
34 #include "DNA_mask_types.h"
35 #include "DNA_scene_types.h"
36
37 #include "BLI_utildefines.h"
38 #include "BLI_scanfill.h"
39 #include "BLI_memarena.h"
40
41 #include "BLI_math.h"
42 #include "BLI_rect.h"
43 #include "BLI_listbase.h"
44 #include "BLI_linklist.h"
45
46 #include "BKE_mask.h"
47
48 #ifndef USE_RASKTER
49
50 #define SPLINE_RESOL_CAP 32
51 #define SPLINE_RESOL 32
52 #define BUCKET_PIXELS_PER_CELL 8
53
54 #define SF_EDGE_IS_BOUNDARY 0xff
55 #define SF_KEYINDEX_TEMP_ID ((unsigned int) -1)
56
57 #define TRI_TERMINATOR_ID   ((unsigned int) -1)
58 #define TRI_VERT            ((unsigned int) -1)
59
60
61 /* --------------------------------------------------------------------- */
62 /* local structs for mask rasterizeing                                   */
63 /* --------------------------------------------------------------------- */
64
65 /**
66  * A single #MaskRasterHandle contains multile #MaskRasterLayer's,
67  * each #MaskRasterLayer does its own lookup which contributes to
68  * the final pixel with its own blending mode and the final pixel
69  * is blended between these.
70  */
71
72 /* internal use only */
73 typedef struct MaskRasterLayer {
74         /* geometry */
75         unsigned int   face_tot;
76         unsigned int (*face_array)[4];  /* access coords tri/quad */
77         float        (*face_coords)[3]; /* xy, z 0-1 (1.0 == filled) */
78
79
80         /* 2d bounds (to quickly skip bucket lookup) */
81         rctf bounds;
82
83
84         /* buckets */
85         unsigned int **buckets_face;
86         /* cache divide and subtract */
87         float buckets_xy_scalar[2]; /* (1.0 / (buckets_width + FLT_EPSILON)) * buckets_x */
88         unsigned int buckets_x;
89         unsigned int buckets_y;
90
91
92         /* copied direct from #MaskLayer.--- */
93         /* blending options */
94         float  alpha;
95         char   blend;
96         char   blend_flag;
97         char   falloff;
98
99 } MaskRasterLayer;
100
101 typedef struct MaskRasterSplineInfo {
102         unsigned int vertex_offset;
103         unsigned int vertex_total;
104         unsigned int is_cyclic;
105 } MaskRasterSplineInfo;
106
107 /**
108  * opaque local struct for mask pixel lookup, each MaskLayer needs one of these
109  */
110 struct MaskRasterHandle {
111         MaskRasterLayer *layers;
112         unsigned int     layers_tot;
113
114         /* 2d bounds (to quickly skip bucket lookup) */
115         rctf bounds;
116 };
117
118 /* --------------------------------------------------------------------- */
119 /* alloc / free functions                                                */
120 /* --------------------------------------------------------------------- */
121
122 MaskRasterHandle *BKE_maskrasterize_handle_new(void)
123 {
124         MaskRasterHandle *mr_handle;
125
126         mr_handle = MEM_callocN(sizeof(MaskRasterHandle), STRINGIFY(MaskRasterHandle));
127
128         return mr_handle;
129 }
130
131 void BKE_maskrasterize_handle_free(MaskRasterHandle *mr_handle)
132 {
133         const unsigned int layers_tot = mr_handle->layers_tot;
134         unsigned int i;
135         MaskRasterLayer *layer = mr_handle->layers;
136
137         /* raycast vars */
138         for (i = 0; i < layers_tot; i++, layer++) {
139
140                 if (layer->face_array) {
141                         MEM_freeN(layer->face_array);
142                 }
143
144                 if (layer->face_coords) {
145                         MEM_freeN(layer->face_coords);
146                 }
147
148                 if (layer->buckets_face) {
149                         const unsigned int   bucket_tot = layer->buckets_x * layer->buckets_y;
150                         unsigned int bucket_index;
151                         for (bucket_index = 0; bucket_index < bucket_tot; bucket_index++) {
152                                 unsigned int *face_index = layer->buckets_face[bucket_index];
153                                 if (face_index) {
154                                         MEM_freeN(face_index);
155                                 }
156                         }
157
158                         MEM_freeN(layer->buckets_face);
159                 }
160         }
161
162         MEM_freeN(mr_handle->layers);
163         MEM_freeN(mr_handle);
164 }
165
166
167 void maskrasterize_spline_differentiate_point_outset(float (*diff_feather_points)[2], float (*diff_points)[2],
168                                                      const unsigned int tot_diff_point, const float ofs,
169                                                      const short do_test)
170 {
171         unsigned int k_prev = tot_diff_point - 2;
172         unsigned int k_curr = tot_diff_point - 1;
173         unsigned int k_next = 0;
174
175         unsigned int k;
176
177         float d_prev[2];
178         float d_next[2];
179         float d[2];
180
181         const float *co_prev;
182         const float *co_curr;
183         const float *co_next;
184
185         const float ofs_squared = ofs * ofs;
186
187         co_prev = diff_points[k_prev];
188         co_curr = diff_points[k_curr];
189         co_next = diff_points[k_next];
190
191         /* precalc */
192         sub_v2_v2v2(d_prev, co_prev, co_curr);
193         normalize_v2(d_prev);
194
195         for (k = 0; k < tot_diff_point; k++) {
196
197                 /* co_prev = diff_points[k_prev]; */ /* precalc */
198                 co_curr = diff_points[k_curr];
199                 co_next = diff_points[k_next];
200
201                 /* sub_v2_v2v2(d_prev, co_prev, co_curr); */ /* precalc */
202                 sub_v2_v2v2(d_next, co_curr, co_next);
203
204                 /* normalize_v2(d_prev); */ /* precalc */
205                 normalize_v2(d_next);
206
207                 if ((do_test == FALSE) ||
208                     (len_squared_v2v2(diff_feather_points[k], diff_points[k]) < ofs_squared))
209                 {
210
211                         add_v2_v2v2(d, d_prev, d_next);
212
213                         normalize_v2(d);
214
215                         diff_feather_points[k][0] = diff_points[k][0] + ( d[1] * ofs);
216                         diff_feather_points[k][1] = diff_points[k][1] + (-d[0] * ofs);
217                 }
218
219                 /* use next iter */
220                 copy_v2_v2(d_prev, d_next);
221
222                 /* k_prev = k_curr; */ /* precalc */
223                 k_curr = k_next;
224                 k_next++;
225         }
226 }
227
228 /* this function is not exact, sometimes it retuns false positives,
229  * the main point of it is to clear out _almost_ all bucket/face non-intersections,
230  * returning TRUE in corner cases is ok but missing an intersection is NOT.
231  *
232  * method used
233  * - check if the center of the buckets bounding box is intersecting the face
234  * - if not get the max radius to a corner of the bucket and see how close we
235  *   are to any of the triangle edges.
236  */
237 static int layer_bucket_isect_test(MaskRasterLayer *layer, unsigned int face_index,
238                                    const unsigned int bucket_x, const unsigned int bucket_y,
239                                    const float bucket_size_x, const float bucket_size_y,
240                                    const float bucket_max_rad_squared)
241 {
242         unsigned int *face = layer->face_array[face_index];
243         float (*cos)[3] = layer->face_coords;
244
245         const float xmin = layer->bounds.xmin + (bucket_size_x * bucket_x);
246         const float ymin = layer->bounds.ymin + (bucket_size_y * bucket_y);
247         const float xmax = xmin + bucket_size_x;
248         const float ymax = ymin + bucket_size_y;
249
250         const float cent[2] = {(xmin + xmax) * 0.5f,
251                                (ymin + ymax) * 0.5f};
252
253         if (face[3] == TRI_VERT) {
254                 const float *v1 = cos[face[0]];
255                 const float *v2 = cos[face[1]];
256                 const float *v3 = cos[face[2]];
257
258                 if (isect_point_tri_v2(cent, v1, v2, v3)) {
259                         return TRUE;
260                 }
261                 else {
262                         if ((dist_squared_to_line_segment_v2(cent, v1, v2) < bucket_max_rad_squared) ||
263                                 (dist_squared_to_line_segment_v2(cent, v2, v3) < bucket_max_rad_squared) ||
264                                 (dist_squared_to_line_segment_v2(cent, v3, v1) < bucket_max_rad_squared))
265                         {
266                                 return TRUE;
267                         }
268                         else {
269                                 // printf("skip tri\n");
270                                 return FALSE;
271                         }
272                 }
273
274         }
275         else {
276                 const float *v1 = cos[face[0]];
277                 const float *v2 = cos[face[1]];
278                 const float *v3 = cos[face[2]];
279                 const float *v4 = cos[face[3]];
280
281                 if (isect_point_tri_v2(cent, v1, v2, v3)) {
282                         return TRUE;
283                 }
284                 else if (isect_point_tri_v2(cent, v1, v3, v4)) {
285                         return TRUE;
286                 }
287                 else {
288                         if ((dist_squared_to_line_segment_v2(cent, v1, v2) < bucket_max_rad_squared) ||
289                             (dist_squared_to_line_segment_v2(cent, v2, v3) < bucket_max_rad_squared) ||
290                             (dist_squared_to_line_segment_v2(cent, v3, v4) < bucket_max_rad_squared) ||
291                             (dist_squared_to_line_segment_v2(cent, v4, v1) < bucket_max_rad_squared))
292                         {
293                                 return TRUE;
294                         }
295                         else {
296                                 // printf("skip quad\n");
297                                 return FALSE;
298                         }
299                 }
300         }
301 }
302
303 static void layer_bucket_init_dummy(MaskRasterLayer *layer)
304 {
305         layer->face_tot = 0;
306         layer->face_coords = NULL;
307         layer->face_array  = NULL;
308
309         layer->buckets_x = 0;
310         layer->buckets_y = 0;
311
312         layer->buckets_xy_scalar[0] = 0.0f;
313         layer->buckets_xy_scalar[1] = 0.0f;
314
315         layer->buckets_face = NULL;
316
317         BLI_rctf_init(&layer->bounds, -1.0f, -1.0f, -1.0f, -1.0f);
318 }
319
320 static void layer_bucket_init(MaskRasterLayer *layer, const float pixel_size)
321 {
322         MemArena *arena = BLI_memarena_new(1 << 16, __func__);
323
324         const float bucket_dim_x = layer->bounds.xmax - layer->bounds.xmin;
325         const float bucket_dim_y = layer->bounds.ymax - layer->bounds.ymin;
326
327         layer->buckets_x = (bucket_dim_x / pixel_size) / (float)BUCKET_PIXELS_PER_CELL;
328         layer->buckets_y = (bucket_dim_y / pixel_size) / (float)BUCKET_PIXELS_PER_CELL;
329
330 //              printf("bucket size %ux%u\n", layer->buckets_x, layer->buckets_y);
331
332         CLAMP(layer->buckets_x, 8, 512);
333         CLAMP(layer->buckets_y, 8, 512);
334
335         layer->buckets_xy_scalar[0] = (1.0f / (bucket_dim_x + FLT_EPSILON)) * layer->buckets_x;
336         layer->buckets_xy_scalar[1] = (1.0f / (bucket_dim_y + FLT_EPSILON)) * layer->buckets_y;
337
338         {
339                 /* width and height of each bucket */
340                 const float bucket_size_x = (bucket_dim_x + FLT_EPSILON) / layer->buckets_x;
341                 const float bucket_size_y = (bucket_dim_y + FLT_EPSILON) / layer->buckets_y;
342                 const float bucket_max_rad = (maxf(bucket_size_x, bucket_size_y) * M_SQRT2) + FLT_EPSILON;
343                 const float bucket_max_rad_squared = bucket_max_rad * bucket_max_rad;
344
345                 unsigned int *face = &layer->face_array[0][0];
346                 float (*cos)[3] = layer->face_coords;
347
348                 const unsigned int  bucket_tot = layer->buckets_x * layer->buckets_y;
349                 LinkNode     **bucketstore     = MEM_callocN(bucket_tot * sizeof(LinkNode *),  __func__);
350                 unsigned int  *bucketstore_tot = MEM_callocN(bucket_tot * sizeof(unsigned int), __func__);
351
352                 unsigned int face_index;
353
354                 for (face_index = 0; face_index < layer->face_tot; face_index++, face += 4) {
355                         float xmin;
356                         float xmax;
357                         float ymin;
358                         float ymax;
359
360                         if (face[3] == TRI_VERT) {
361                                 const float *v1 = cos[face[0]];
362                                 const float *v2 = cos[face[1]];
363                                 const float *v3 = cos[face[2]];
364
365                                 xmin = minf(v1[0], minf(v2[0], v3[0]));
366                                 xmax = maxf(v1[0], maxf(v2[0], v3[0]));
367                                 ymin = minf(v1[1], minf(v2[1], v3[1]));
368                                 ymax = maxf(v1[1], maxf(v2[1], v3[1]));
369                         }
370                         else {
371                                 const float *v1 = cos[face[0]];
372                                 const float *v2 = cos[face[1]];
373                                 const float *v3 = cos[face[2]];
374                                 const float *v4 = cos[face[3]];
375
376                                 xmin = minf(v1[0], minf(v2[0], minf(v3[0], v4[0])));
377                                 xmax = maxf(v1[0], maxf(v2[0], maxf(v3[0], v4[0])));
378                                 ymin = minf(v1[1], minf(v2[1], minf(v3[1], v4[1])));
379                                 ymax = maxf(v1[1], maxf(v2[1], maxf(v3[1], v4[1])));
380                         }
381
382
383                         /* not essential but may as will skip any faces outside the view */
384                         if (!((xmax < 0.0f) || (ymax < 0.0f) || (xmin > 1.0f) || (ymin > 1.0f))) {
385
386                                 CLAMP(xmin, 0.0f,  1.0f);
387                                 CLAMP(ymin, 0.0f,  1.0f);
388                                 CLAMP(xmax, 0.0f,  1.0f);
389                                 CLAMP(ymax, 0.0f,  1.0f);
390
391                                 {
392                                         unsigned int xi_min = (unsigned int) ((xmin - layer->bounds.xmin) * layer->buckets_xy_scalar[0]);
393                                         unsigned int xi_max = (unsigned int) ((xmax - layer->bounds.xmin) * layer->buckets_xy_scalar[0]);
394                                         unsigned int yi_min = (unsigned int) ((ymin - layer->bounds.ymin) * layer->buckets_xy_scalar[1]);
395                                         unsigned int yi_max = (unsigned int) ((ymax - layer->bounds.ymin) * layer->buckets_xy_scalar[1]);
396                                         void *face_index_void = SET_UINT_IN_POINTER(face_index);
397
398                                         unsigned int xi, yi;
399
400                                         /* this should _almost_ never happen but since it can in extreme cases,
401                                          * we have to clamp the values or we overrun the buffer and crash */
402                                         CLAMP(xi_min, 0, layer->buckets_x - 1);
403                                         CLAMP(xi_max, 0, layer->buckets_x - 1);
404                                         CLAMP(yi_min, 0, layer->buckets_y - 1);
405                                         CLAMP(yi_max, 0, layer->buckets_y - 1);
406
407                                         for (yi = yi_min; yi <= yi_max; yi++) {
408                                                 unsigned int bucket_index = (layer->buckets_x * yi) + xi_min;
409                                                 for (xi = xi_min; xi <= xi_max; xi++, bucket_index++) {
410                                                         // unsigned int bucket_index = (layer->buckets_x * yi) + xi; /* correct but do in outer loop */
411
412                                                         BLI_assert(xi < layer->buckets_x);
413                                                         BLI_assert(yi < layer->buckets_y);
414                                                         BLI_assert(bucket_index < bucket_tot);
415
416                                                         /* check if the bucket intersects with the face */
417                                                         /* note: there is a tradeoff here since checking box/tri intersections isn't
418                                                          * as optimal as it could be, but checking pixels against faces they will never intersect
419                                                          * with is likely the greater slowdown here - so check if the cell intersects the face */
420                                                         if (layer_bucket_isect_test(layer, face_index,
421                                                                                     xi, yi,
422                                                                                     bucket_size_x, bucket_size_y,
423                                                                                     bucket_max_rad_squared))
424                                                         {
425                                                                 BLI_linklist_prepend_arena(&bucketstore[bucket_index], face_index_void, arena);
426                                                                 bucketstore_tot[bucket_index]++;
427                                                         }
428                                                 }
429                                         }
430                                 }
431                         }
432                 }
433
434                 if (1) {
435                         /* now convert linknodes into arrays for faster per pixel access */
436                         unsigned int  **buckets_face = MEM_mallocN(bucket_tot * sizeof(unsigned int **), __func__);
437                         unsigned int bucket_index;
438
439                         for (bucket_index = 0; bucket_index < bucket_tot; bucket_index++) {
440                                 if (bucketstore_tot[bucket_index]) {
441                                         unsigned int  *bucket = MEM_mallocN((bucketstore_tot[bucket_index] + 1) * sizeof(unsigned int),
442                                                                             __func__);
443                                         LinkNode *bucket_node;
444
445                                         buckets_face[bucket_index] = bucket;
446
447                                         for (bucket_node = bucketstore[bucket_index]; bucket_node; bucket_node = bucket_node->next) {
448                                                 *bucket = GET_UINT_FROM_POINTER(bucket_node->link);
449                                                 bucket++;
450                                         }
451                                         *bucket = TRI_TERMINATOR_ID;
452                                 }
453                                 else {
454                                         buckets_face[bucket_index] = NULL;
455                                 }
456                         }
457
458                         layer->buckets_face = buckets_face;
459                 }
460
461                 MEM_freeN(bucketstore);
462                 MEM_freeN(bucketstore_tot);
463         }
464
465         BLI_memarena_free(arena);
466 }
467
468 void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mask,
469                                    const int width, const int height,
470                                    const short do_aspect_correct, const short do_mask_aa,
471                                    const short do_feather)
472 {
473         const rctf default_bounds = {0.0f, 1.0f, 0.0f, 1.0f};
474         const float pixel_size = 1.0f / MIN2(width, height);
475
476         const float zvec[3] = {0.0f, 0.0f, 1.0f};
477         MaskLayer *masklay;
478         unsigned int masklay_index;
479
480         mr_handle->layers_tot = BLI_countlist(&mask->masklayers);
481         mr_handle->layers = MEM_mallocN(sizeof(MaskRasterLayer) * mr_handle->layers_tot, STRINGIFY(MaskRasterLayer));
482         BLI_rctf_init_minmax(&mr_handle->bounds);
483
484         for (masklay = mask->masklayers.first, masklay_index = 0; masklay; masklay = masklay->next, masklay_index++) {
485
486                 /* we need to store vertex ranges for open splines for filling */
487                 unsigned int tot_splines;
488                 MaskRasterSplineInfo *open_spline_ranges;
489                 unsigned int   open_spline_index = 0;
490
491                 MaskSpline *spline;
492
493                 /* scanfill */
494                 ScanFillContext sf_ctx;
495                 ScanFillVert *sf_vert = NULL;
496                 ScanFillVert *sf_vert_next = NULL;
497                 ScanFillFace *sf_tri;
498
499                 unsigned int sf_vert_tot = 0;
500                 unsigned int tot_feather_quads = 0;
501
502                 if (masklay->restrictflag & MASK_RESTRICT_RENDER || masklay->alpha == 0.0f) {
503                         MaskRasterLayer *layer = &mr_handle->layers[masklay_index];
504                         layer_bucket_init_dummy(layer);
505                         layer->alpha = 0.0f; /* signal to skip this layer */
506                         continue;
507                 }
508
509                 tot_splines = BLI_countlist(&masklay->splines);
510                 open_spline_ranges = MEM_callocN(sizeof(*open_spline_ranges) * tot_splines, __func__);
511
512                 BLI_scanfill_begin(&sf_ctx);
513
514                 for (spline = masklay->splines.first; spline; spline = spline->next) {
515                         const unsigned int is_cyclic = (spline->flag & MASK_SPLINE_CYCLIC) != 0;
516                         const unsigned int is_fill = (spline->flag & MASK_SPLINE_NOFILL) == 0;
517
518                         float (*diff_points)[2];
519                         int tot_diff_point;
520
521                         float (*diff_feather_points)[2];
522                         int tot_diff_feather_points;
523
524                         const int resol_a = BKE_mask_spline_resolution(spline, width, height) / 4;
525                         const int resol_b = BKE_mask_spline_feather_resolution(spline, width, height) / 4;
526                         const int resol = CLAMPIS(MAX2(resol_a, resol_b), 4, 512);
527
528                         diff_points = BKE_mask_spline_differentiate_with_resolution_ex(
529                                           spline, resol, &tot_diff_point);
530
531                         if (do_feather) {
532                                 diff_feather_points = BKE_mask_spline_feather_differentiated_points_with_resolution_ex(
533                                                           spline, resol, &tot_diff_feather_points);
534                         }
535                         else {
536                                 tot_diff_feather_points = 0;
537                                 diff_feather_points = NULL;
538                         }
539
540                         if (tot_diff_point > 3) {
541                                 ScanFillVert *sf_vert_prev;
542                                 int j;
543
544                                 float co[3];
545                                 co[2] = 0.0f;
546
547                                 if (do_aspect_correct) {
548                                         if (width != height) {
549                                                 float *fp;
550                                                 float *ffp;
551                                                 int i;
552                                                 float asp;
553
554                                                 if (width < height) {
555                                                         fp = &diff_points[0][0];
556                                                         ffp = tot_diff_feather_points ? &diff_feather_points[0][0] : NULL;
557                                                         asp = (float)width / (float)height;
558                                                 }
559                                                 else {
560                                                         fp = &diff_points[0][1];
561                                                         ffp = tot_diff_feather_points ? &diff_feather_points[0][1] : NULL;
562                                                         asp = (float)height / (float)width;
563                                                 }
564
565                                                 for (i = 0; i < tot_diff_point; i++, fp += 2) {
566                                                         (*fp) = (((*fp) - 0.5f) / asp) + 0.5f;
567                                                 }
568
569                                                 if (tot_diff_feather_points) {
570                                                         for (i = 0; i < tot_diff_feather_points; i++, ffp += 2) {
571                                                                 (*ffp) = (((*ffp) - 0.5f) / asp) + 0.5f;
572                                                         }
573                                                 }
574                                         }
575                                 }
576
577                                 /* fake aa, using small feather */
578                                 if (do_mask_aa == TRUE) {
579                                         if (do_feather == FALSE) {
580                                                 tot_diff_feather_points = tot_diff_point;
581                                                 diff_feather_points = MEM_mallocN(sizeof(*diff_feather_points) * tot_diff_feather_points,
582                                                                                   __func__);
583                                                 /* add single pixel feather */
584                                                 maskrasterize_spline_differentiate_point_outset(diff_feather_points, diff_points,
585                                                                                                tot_diff_point, pixel_size, FALSE);
586                                         }
587                                         else {
588                                                 /* ensure single pixel feather, on any zero feather areas */
589                                                 maskrasterize_spline_differentiate_point_outset(diff_feather_points, diff_points,
590                                                                                                tot_diff_point, pixel_size, TRUE);
591                                         }
592                                 }
593
594                                 if (is_fill) {
595                                         copy_v2_v2(co, diff_points[0]);
596                                         sf_vert_prev = BLI_scanfill_vert_add(&sf_ctx, co);
597                                         sf_vert_prev->tmp.u = sf_vert_tot;
598                                         sf_vert_prev->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
599                                         sf_vert_tot++;
600
601                                         /* TODO, an alternate functions so we can avoid double vector copy! */
602                                         for (j = 1; j < tot_diff_point; j++) {
603                                                 copy_v2_v2(co, diff_points[j]);
604                                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
605                                                 sf_vert->tmp.u = sf_vert_tot;
606                                                 sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
607                                                 sf_vert_tot++;
608                                         }
609
610                                         sf_vert = sf_vert_prev;
611                                         sf_vert_prev = sf_ctx.fillvertbase.last;
612
613                                         for (j = 0; j < tot_diff_point; j++) {
614                                                 ScanFillEdge *sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
615                                                 sf_edge->tmp.c = SF_EDGE_IS_BOUNDARY;
616
617                                                 sf_vert_prev = sf_vert;
618                                                 sf_vert = sf_vert->next;
619                                         }
620
621                                         if (diff_feather_points) {
622                                                 float co_feather[3];
623                                                 co_feather[2] = 1.0f;
624
625                                                 BLI_assert(tot_diff_feather_points == tot_diff_point);
626
627                                                 /* note: only added for convenience, we don't infact use these to scanfill,
628                                                  * only to create feather faces after scanfill */
629                                                 for (j = 0; j < tot_diff_feather_points; j++) {
630                                                         copy_v2_v2(co_feather, diff_feather_points[j]);
631                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
632
633                                                         /* no need for these attrs */
634         #if 0
635                                                         sf_vert->tmp.u = sf_vert_tot;
636                                                         sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
637         #endif
638                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
639                                                         sf_vert_tot++;
640                                                 }
641
642                                                 tot_feather_quads += tot_diff_point;
643                                         }
644                                 }
645                                 else {
646                                         /* unfilled spline */
647                                         if (diff_feather_points) {
648
649                                                 float co_diff[3];
650
651                                                 float co_feather[3];
652                                                 co_feather[2] = 1.0f;
653
654                                                 open_spline_ranges[open_spline_index].vertex_offset = sf_vert_tot;
655                                                 open_spline_ranges[open_spline_index].vertex_total = tot_diff_point;
656                                                 open_spline_ranges[open_spline_index].is_cyclic = is_cyclic;
657                                                 open_spline_index++;
658
659
660                                                 /* TODO, an alternate functions so we can avoid double vector copy! */
661                                                 for (j = 0; j < tot_diff_point; j++) {
662
663                                                         /* center vert */
664                                                         copy_v2_v2(co, diff_points[j]);
665                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
666                                                         sf_vert->tmp.u = sf_vert_tot;
667                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
668                                                         sf_vert_tot++;
669
670
671                                                         /* feather vert A */
672                                                         copy_v2_v2(co_feather, diff_feather_points[j]);
673                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
674                                                         sf_vert->tmp.u = sf_vert_tot;
675                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
676                                                         sf_vert_tot++;
677
678
679                                                         /* feather vert B */
680                                                         sub_v2_v2v2(co_diff, co, co_feather);
681                                                         add_v2_v2v2(co_feather, co, co_diff);
682                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
683                                                         sf_vert->tmp.u = sf_vert_tot;
684                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
685                                                         sf_vert_tot++;
686
687                                                         tot_feather_quads += 2;
688                                                 }
689
690                                                 if (!is_cyclic) {
691                                                         tot_feather_quads -= 2;
692                                                 }
693
694                                                 /* ack these are infact tris, but they are extra faces so no matter,
695                                                  * +1 becausing adding one vert results in 2 tris (joining the existing endpoints)
696                                                  */
697                                                 // tot_feather_quads + ((SPLINE_RESOL_CAP + 1) * 2);
698
699                                         }
700                                 }
701                         }
702
703                         if (diff_points) {
704                                 MEM_freeN(diff_points);
705                         }
706
707                         if (diff_feather_points) {
708                                 MEM_freeN(diff_feather_points);
709                         }
710                 }
711
712                 {
713                         unsigned int (*face_array)[4], *face;  /* access coords */
714                         float        (*face_coords)[3], *cos; /* xy, z 0-1 (1.0 == filled) */
715                         int sf_tri_tot;
716                         rctf bounds;
717                         int face_index;
718
719                         /* now we have all the splines */
720                         face_coords = MEM_mallocN((sizeof(float) * 3) * sf_vert_tot, "maskrast_face_coords");
721
722                         /* init bounds */
723                         BLI_rctf_init_minmax(&bounds);
724
725                         /* coords */
726                         cos = (float *)face_coords;
727                         for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert_next) {
728                                 sf_vert_next = sf_vert->next;
729                                 copy_v3_v3(cos, sf_vert->co);
730
731                                 /* remove so as not to interfear with fill (called after) */
732                                 if (sf_vert->keyindex == SF_KEYINDEX_TEMP_ID) {
733                                         BLI_remlink(&sf_ctx.fillvertbase, sf_vert);
734                                 }
735
736                                 /* bounds */
737                                 BLI_rctf_do_minmax_v(&bounds, cos);
738
739                                 cos += 3;
740                         }
741
742                         /* main scanfill */
743                         sf_tri_tot = BLI_scanfill_calc_ex(&sf_ctx, FALSE, zvec);
744
745                         face_array = MEM_mallocN(sizeof(*face_array) * (sf_tri_tot + tot_feather_quads), "maskrast_face_index");
746
747                         /* tri's */
748                         face = (unsigned int *)face_array;
749                         for (sf_tri = sf_ctx.fillfacebase.first, face_index = 0; sf_tri; sf_tri = sf_tri->next, face_index++) {
750                                 *(face++) = sf_tri->v3->tmp.u;
751                                 *(face++) = sf_tri->v2->tmp.u;
752                                 *(face++) = sf_tri->v1->tmp.u;
753                                 *(face++) = TRI_VERT;
754                         }
755
756                         /* start of feather faces... if we have this set,
757                          * 'face_index' is kept from loop above */
758
759                         BLI_assert(face_index == sf_tri_tot);
760
761                         if (tot_feather_quads) {
762                                 ScanFillEdge *sf_edge;
763
764                                 for (sf_edge = sf_ctx.filledgebase.first; sf_edge; sf_edge = sf_edge->next) {
765                                         if (sf_edge->tmp.c == SF_EDGE_IS_BOUNDARY) {
766                                                 *(face++) = sf_edge->v1->tmp.u;
767                                                 *(face++) = sf_edge->v2->tmp.u;
768                                                 *(face++) = sf_edge->v2->keyindex;
769                                                 *(face++) = sf_edge->v1->keyindex;
770
771                                                 face_index++;
772                                         }
773                                 }
774                         }
775
776                         /* feather only splines */
777                         while (open_spline_index > 0) {
778                                 unsigned int start_vidx          = open_spline_ranges[--open_spline_index].vertex_offset;
779                                 unsigned int tot_diff_point_sub1 = open_spline_ranges[  open_spline_index].vertex_total - 1;
780                                 unsigned int k, j;
781
782                                 j = start_vidx;
783
784                                 /* subtract one since we reference next vertex triple */
785                                 for (k = 0; k < tot_diff_point_sub1; k++, j += 3) {
786
787                                         BLI_assert(j == start_vidx + (k * 3));
788
789                                         *(face++) = j + 3; /* next span */ /* z 1 */
790                                         *(face++) = j + 0;                 /* z 1 */
791                                         *(face++) = j + 1;                 /* z 0 */
792                                         *(face++) = j + 4; /* next span */ /* z 0 */
793
794                                         face_index++;
795
796                                         *(face++) = j + 0;                 /* z 1 */
797                                         *(face++) = j + 3; /* next span */ /* z 1 */
798                                         *(face++) = j + 5; /* next span */ /* z 0 */
799                                         *(face++) = j + 2;                 /* z 0 */
800
801                                         face_index++;
802                                 }
803
804                                 if (open_spline_ranges[open_spline_index].is_cyclic) {
805                                         *(face++) = start_vidx + 0; /* next span */ /* z 1 */
806                                         *(face++) = j          + 0;                 /* z 1 */
807                                         *(face++) = j          + 1;                 /* z 0 */
808                                         *(face++) = start_vidx + 1; /* next span */ /* z 0 */
809
810                                         face_index++;
811
812                                         *(face++) = j          + 0;                 /* z 1 */
813                                         *(face++) = start_vidx + 0; /* next span */ /* z 1 */
814                                         *(face++) = start_vidx + 2; /* next span */ /* z 0 */
815                                         *(face++) = j          + 2;                 /* z 0 */
816
817                                         face_index++;
818                                 }
819                         }
820
821                         MEM_freeN(open_spline_ranges);
822
823                         // fprintf(stderr, "%d %d\n", face_index, sf_face_tot + tot_feather_quads);
824
825                         BLI_assert(face_index == sf_tri_tot + tot_feather_quads);
826
827                         {
828                                 MaskRasterLayer *layer = &mr_handle->layers[masklay_index];
829
830                                 if (BLI_rctf_isect(&default_bounds, &bounds, &bounds)) {
831                                         layer->face_tot = sf_tri_tot + tot_feather_quads;
832                                         layer->face_coords = face_coords;
833                                         layer->face_array  = face_array;
834                                         layer->bounds = bounds;
835
836                                         layer_bucket_init(layer, pixel_size);
837
838                                         BLI_rctf_union(&mr_handle->bounds, &bounds);
839                                 }
840                                 else {
841                                         MEM_freeN(face_coords);
842                                         MEM_freeN(face_array);
843
844                                         layer_bucket_init_dummy(layer);
845                                 }
846
847                                 /* copy as-is */
848                                 layer->alpha = masklay->alpha;
849                                 layer->blend = masklay->blend;
850                                 layer->blend_flag = masklay->blend_flag;
851                                 layer->falloff = masklay->falloff;
852                         }
853
854                         /* printf("tris %d, feather tris %d\n", sf_tri_tot, tot_feather_quads); */
855                 }
856
857                 /* add trianges */
858                 BLI_scanfill_end(&sf_ctx);
859         }
860 }
861
862
863 /* --------------------------------------------------------------------- */
864 /* functions that run inside the sampling thread (keep fast!)            */
865 /* --------------------------------------------------------------------- */
866
867 /* 2D ray test */
868 #if 0
869 static float maskrasterize_layer_z_depth_tri(const float pt[2],
870                                              const float v1[3], const float v2[3], const float v3[3])
871 {
872         float w[3];
873         barycentric_weights_v2(v1, v2, v3, pt, w);
874         return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]);
875 }
876 #endif
877
878 #if 1
879 static float maskrasterize_layer_z_depth_quad(const float pt[2],
880                                               const float v1[3], const float v2[3], const float v3[3], const float v4[3])
881 {
882         float w[4];
883         barycentric_weights_v2_quad(v1, v2, v3, v4, pt, w);
884         //return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]) + (v4[2] * w[3]);
885         return w[2] + w[3];  /* we can make this assumption for small speedup */
886 }
887 #endif
888
889 static float maskrasterize_layer_isect(unsigned int *face, float (*cos)[3], const float dist_orig, const float xy[2])
890 {
891         /* we always cast from same place only need xy */
892         if (face[3] == TRI_VERT) {
893                 /* --- tri --- */
894
895 #if 0
896                 /* not essential but avoids unneeded extra lookups */
897                 if ((cos[0][2] < dist_orig) ||
898                     (cos[1][2] < dist_orig) ||
899                     (cos[2][2] < dist_orig))
900                 {
901                         if (isect_point_tri_v2_cw(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
902                                 /* we know all tris are close for now */
903                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[1]], cos[face[2]]);
904                         }
905                 }
906 #else
907                 /* we know all tris are close for now */
908                 if (1) {
909                         if (isect_point_tri_v2_cw(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
910                                 return 0.0f;
911                         }
912                 }
913 #endif
914         }
915         else {
916                 /* --- quad --- */
917
918                 /* not essential but avoids unneeded extra lookups */
919                 if ((cos[0][2] < dist_orig) ||
920                     (cos[1][2] < dist_orig) ||
921                     (cos[2][2] < dist_orig) ||
922                     (cos[3][2] < dist_orig))
923                 {
924
925                         /* needs work */
926 #if 1
927                         /* quad check fails for bowtie, so keep using 2 tri checks */
928                         //if (isect_point_quad_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]], cos[face[3]]))
929                         if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]]) ||
930                             isect_point_tri_v2(xy, cos[face[0]], cos[face[2]], cos[face[3]]))
931                         {
932                                 return maskrasterize_layer_z_depth_quad(xy, cos[face[0]], cos[face[1]], cos[face[2]], cos[face[3]]);
933                         }
934 #elif 1
935                         /* don't use isect_point_tri_v2_cw because we could have bowtie quads */
936
937                         if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
938                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[1]], cos[face[2]]);
939                         }
940                         else if (isect_point_tri_v2(xy, cos[face[0]], cos[face[2]], cos[face[3]])) {
941                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[2]], cos[face[3]]);
942                         }
943 #else
944                         /* cheat - we know first 2 verts are z0.0f and second 2 are z 1.0f */
945                         /* ... worth looking into */
946 #endif
947                 }
948         }
949
950         return 1.0f;
951 }
952
953 BLI_INLINE unsigned int layer_bucket_index_from_xy(MaskRasterLayer *layer, const float xy[2])
954 {
955         BLI_assert(BLI_in_rctf_v(&layer->bounds, xy));
956
957         return ( (unsigned int)((xy[0] - layer->bounds.xmin) * layer->buckets_xy_scalar[0])) +
958                (((unsigned int)((xy[1] - layer->bounds.ymin) * layer->buckets_xy_scalar[1])) * layer->buckets_x);
959 }
960
961 static float layer_bucket_depth_from_xy(MaskRasterLayer *layer, const float xy[2])
962 {
963         unsigned int index = layer_bucket_index_from_xy(layer, xy);
964         unsigned int *face_index = layer->buckets_face[index];
965
966         if (face_index) {
967                 unsigned int (*face_array)[4] = layer->face_array;
968                 float        (*cos)[3]        = layer->face_coords;
969                 float best_dist = 1.0f;
970                 while (*face_index != TRI_TERMINATOR_ID) {
971                         const float test_dist = maskrasterize_layer_isect(face_array[*face_index], cos, best_dist, xy);
972                         if (test_dist < best_dist) {
973                                 best_dist = test_dist;
974                                 /* comparing with 0.0f is OK here because triangles are always zero depth */
975                                 if (best_dist == 0.0f) {
976                                         /* bail early, we're as close as possible */
977                                         return 0.0f;
978                                 }
979                         }
980                         face_index++;
981                 }
982                 return best_dist;
983         }
984         else {
985                 return 1.0f;
986         }
987 }
988
989 float BKE_maskrasterize_handle_sample(MaskRasterHandle *mr_handle, const float xy[2])
990 {
991         /* can't do this because some layers may invert */
992         /* if (BLI_in_rctf_v(&mr_handle->bounds, xy)) */
993
994         const unsigned int layers_tot = mr_handle->layers_tot;
995         unsigned int i;
996         MaskRasterLayer *layer = mr_handle->layers;
997
998         /* return value */
999         float value = 0.0f;
1000
1001         for (i = 0; i < layers_tot; i++, layer++) {
1002                 float value_layer;
1003
1004                 /* also used as signal for unused layer (when render is disabled) */
1005                 if (layer->alpha == 0.0f) {
1006                         continue;
1007                 }
1008
1009                 if (BLI_in_rctf_v(&layer->bounds, xy)) {
1010                         value_layer = 1.0f - layer_bucket_depth_from_xy(layer, xy);
1011
1012                         switch (layer->falloff) {
1013                                 case PROP_SMOOTH:
1014                                         /* ease - gives less hard lines for dilate/erode feather */
1015                                         value_layer = (3.0f * value_layer * value_layer - 2.0f * value_layer * value_layer * value_layer);
1016                                         break;
1017                                 case PROP_SPHERE:
1018                                         value_layer = sqrtf(2.0f * value_layer - value_layer * value_layer);
1019                                         break;
1020                                 case PROP_ROOT:
1021                                         value_layer = sqrtf(value_layer);
1022                                         break;
1023                                 case PROP_SHARP:
1024                                         value_layer = value_layer * value_layer;
1025                                         break;
1026                                 case PROP_LIN:
1027                                 default:
1028                                         /* nothing */
1029                                         break;
1030                         }
1031
1032                         if (layer->blend != MASK_BLEND_REPLACE) {
1033                                 value_layer *= layer->alpha;
1034                         }
1035                 }
1036                 else {
1037                         value_layer = 0.0f;
1038                 }
1039
1040                 if (layer->blend_flag & MASK_BLENDFLAG_INVERT) {
1041                         value_layer = 1.0f - value_layer;
1042                 }
1043
1044                 switch (layer->blend) {
1045                         case MASK_BLEND_ADD:
1046                                 value += value_layer;
1047                                 break;
1048                         case MASK_BLEND_SUBTRACT:
1049                                 value -= value_layer;
1050                                 break;
1051                         case MASK_BLEND_LIGHTEN:
1052                                 value = maxf(value, value_layer);
1053                                 break;
1054                         case MASK_BLEND_DARKEN:
1055                                 value = minf(value, value_layer);
1056                                 break;
1057                         case MASK_BLEND_MUL:
1058                                 value *= value_layer;
1059                                 break;
1060                         case MASK_BLEND_REPLACE:
1061                                 value = (value * (1.0f - layer->alpha)) + (value_layer * layer->alpha);
1062                                 break;
1063                         default: /* same as add */
1064                                 BLI_assert(0);
1065                                 value += value_layer;
1066                                 break;
1067                 }
1068         }
1069
1070         return CLAMPIS(value, 0.0f, 1.0f);
1071 }
1072
1073 #endif /* USE_RASKTER */