falloff option for mask layers
[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 *BLI_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 BLI_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->buckets_x = 0;
306         layer->buckets_y = 0;
307
308         layer->buckets_xy_scalar[0] = 0.0f;
309         layer->buckets_xy_scalar[1] = 0.0f;
310
311         layer->buckets_face = NULL;
312 }
313
314 static void layer_bucket_init(MaskRasterLayer *layer, const float pixel_size)
315 {
316         MemArena *arena = BLI_memarena_new(1 << 16, __func__);
317
318         const float bucket_dim_x = layer->bounds.xmax - layer->bounds.xmin;
319         const float bucket_dim_y = layer->bounds.ymax - layer->bounds.ymin;
320
321         layer->buckets_x = (bucket_dim_x / pixel_size) / (float)BUCKET_PIXELS_PER_CELL;
322         layer->buckets_y = (bucket_dim_y / pixel_size) / (float)BUCKET_PIXELS_PER_CELL;
323
324 //              printf("bucket size %ux%u\n", layer->buckets_x, layer->buckets_y);
325
326         CLAMP(layer->buckets_x, 8, 512);
327         CLAMP(layer->buckets_y, 8, 512);
328
329         layer->buckets_xy_scalar[0] = (1.0f / (bucket_dim_x + FLT_EPSILON)) * layer->buckets_x;
330         layer->buckets_xy_scalar[1] = (1.0f / (bucket_dim_y + FLT_EPSILON)) * layer->buckets_y;
331
332         {
333                 /* width and height of each bucket */
334                 const float bucket_size_x = (bucket_dim_x + FLT_EPSILON) / layer->buckets_x;
335                 const float bucket_size_y = (bucket_dim_y + FLT_EPSILON) / layer->buckets_y;
336                 const float bucket_max_rad = (maxf(bucket_size_x, bucket_size_y) * M_SQRT2) + FLT_EPSILON;
337                 const float bucket_max_rad_squared = bucket_max_rad * bucket_max_rad;
338
339                 unsigned int *face = &layer->face_array[0][0];
340                 float (*cos)[3] = layer->face_coords;
341
342                 const unsigned int  bucket_tot = layer->buckets_x * layer->buckets_y;
343                 LinkNode     **bucketstore     = MEM_callocN(bucket_tot * sizeof(LinkNode *),  __func__);
344                 unsigned int  *bucketstore_tot = MEM_callocN(bucket_tot * sizeof(unsigned int), __func__);
345
346                 unsigned int face_index;
347
348                 for (face_index = 0; face_index < layer->face_tot; face_index++, face += 4) {
349                         float xmin;
350                         float xmax;
351                         float ymin;
352                         float ymax;
353
354                         if (face[3] == TRI_VERT) {
355                                 const float *v1 = cos[face[0]];
356                                 const float *v2 = cos[face[1]];
357                                 const float *v3 = cos[face[2]];
358
359                                 xmin = fminf(v1[0], fminf(v2[0], v3[0]));
360                                 xmax = fmaxf(v1[0], fmaxf(v2[0], v3[0]));
361                                 ymin = fminf(v1[1], fminf(v2[1], v3[1]));
362                                 ymax = fmaxf(v1[1], fmaxf(v2[1], v3[1]));
363                         }
364                         else {
365                                 const float *v1 = cos[face[0]];
366                                 const float *v2 = cos[face[1]];
367                                 const float *v3 = cos[face[2]];
368                                 const float *v4 = cos[face[3]];
369
370                                 xmin = fminf(v1[0], fminf(v2[0], fminf(v3[0], v4[0])));
371                                 xmax = fmaxf(v1[0], fmaxf(v2[0], fmaxf(v3[0], v4[0])));
372                                 ymin = fminf(v1[1], fminf(v2[1], fminf(v3[1], v4[1])));
373                                 ymax = fmaxf(v1[1], fmaxf(v2[1], fmaxf(v3[1], v4[1])));
374                         }
375
376
377                         /* not essential but may as will skip any faces outside the view */
378                         if (!((xmax < 0.0f) || (ymax < 0.0f) || (xmin > 1.0f) || (ymin > 1.0f))) {
379
380                                 CLAMP(xmin, 0.0f,  1.0f);
381                                 CLAMP(ymin, 0.0f,  1.0f);
382                                 CLAMP(xmax, 0.0f,  1.0f);
383                                 CLAMP(ymax, 0.0f,  1.0f);
384
385                                 {
386                                         const unsigned int xi_min = (unsigned int) ((xmin - layer->bounds.xmin) * layer->buckets_xy_scalar[0]);
387                                         const unsigned int xi_max = (unsigned int) ((xmax - layer->bounds.xmin) * layer->buckets_xy_scalar[0]);
388                                         const unsigned int yi_min = (unsigned int) ((ymin - layer->bounds.ymin) * layer->buckets_xy_scalar[1]);
389                                         const unsigned int yi_max = (unsigned int) ((ymax - layer->bounds.ymin) * layer->buckets_xy_scalar[1]);
390                                         void *face_index_void = SET_UINT_IN_POINTER(face_index);
391
392                                         unsigned int xi, yi;
393
394                                         for (yi = yi_min; yi <= yi_max; yi++) {
395                                                 unsigned int bucket_index = (layer->buckets_x * yi) + xi_min;
396                                                 for (xi = xi_min; xi <= xi_max; xi++, bucket_index++) {
397                                                         // unsigned int bucket_index = (layer->buckets_x * yi) + xi; /* correct but do in outer loop */
398
399                                                         BLI_assert(xi < layer->buckets_x);
400                                                         BLI_assert(yi < layer->buckets_y);
401                                                         BLI_assert(bucket_index < bucket_tot);
402
403                                                         /* check if the bucket intersects with the face */
404                                                         /* note: there is a tradeoff here since checking box/tri intersections isn't
405                                                          * as optimal as it could be, but checking pixels against faces they will never intersect
406                                                          * with is likely the greater slowdown here - so check if the cell intersects the face */
407                                                         if (layer_bucket_isect_test(layer, face_index,
408                                                                                     xi, yi,
409                                                                                     bucket_size_x, bucket_size_y,
410                                                                                     bucket_max_rad_squared))
411                                                         {
412                                                                 BLI_linklist_prepend_arena(&bucketstore[bucket_index], face_index_void, arena);
413                                                                 bucketstore_tot[bucket_index]++;
414                                                         }
415                                                 }
416                                         }
417                                 }
418                         }
419                 }
420
421                 if (1) {
422                         /* now convert linknodes into arrays for faster per pixel access */
423                         unsigned int  **buckets_face = MEM_mallocN(bucket_tot * sizeof(unsigned int **), __func__);
424                         unsigned int bucket_index;
425
426                         for (bucket_index = 0; bucket_index < bucket_tot; bucket_index++) {
427                                 if (bucketstore_tot[bucket_index]) {
428                                         unsigned int  *bucket = MEM_mallocN((bucketstore_tot[bucket_index] + 1) * sizeof(unsigned int),
429                                                                             __func__);
430                                         LinkNode *bucket_node;
431
432                                         buckets_face[bucket_index] = bucket;
433
434                                         for (bucket_node = bucketstore[bucket_index]; bucket_node; bucket_node = bucket_node->next) {
435                                                 *bucket = GET_UINT_FROM_POINTER(bucket_node->link);
436                                                 bucket++;
437                                         }
438                                         *bucket = TRI_TERMINATOR_ID;
439                                 }
440                                 else {
441                                         buckets_face[bucket_index] = NULL;
442                                 }
443                         }
444
445                         layer->buckets_face = buckets_face;
446                 }
447
448                 MEM_freeN(bucketstore);
449                 MEM_freeN(bucketstore_tot);
450         }
451
452         BLI_memarena_free(arena);
453 }
454
455 void BLI_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mask,
456                                    const int width, const int height,
457                                    const short do_aspect_correct, const short do_mask_aa,
458                                    const short do_feather)
459 {
460         const rctf default_bounds = {0.0f, 1.0f, 0.0f, 1.0f};
461         const int resol = SPLINE_RESOL;  /* TODO: real size */
462         const float pixel_size = 1.0f / MIN2(width, height);
463
464         const float zvec[3] = {0.0f, 0.0f, 1.0f};
465         MaskLayer *masklay;
466         unsigned int masklay_index;
467
468         mr_handle->layers_tot = BLI_countlist(&mask->masklayers);
469         mr_handle->layers = MEM_mallocN(sizeof(MaskRasterLayer) * mr_handle->layers_tot, STRINGIFY(MaskRasterLayer));
470         BLI_rctf_init_minmax(&mr_handle->bounds);
471
472         for (masklay = mask->masklayers.first, masklay_index = 0; masklay; masklay = masklay->next, masklay_index++) {
473
474                 const unsigned int tot_splines = BLI_countlist(&masklay->splines);
475                 /* we need to store vertex ranges for open splines for filling */
476                 MaskRasterSplineInfo *open_spline_ranges = MEM_callocN(sizeof(*open_spline_ranges) * tot_splines, __func__);
477                 unsigned int   open_spline_index = 0;
478
479                 MaskSpline *spline;
480
481                 /* scanfill */
482                 ScanFillContext sf_ctx;
483                 ScanFillVert *sf_vert = NULL;
484                 ScanFillVert *sf_vert_next = NULL;
485                 ScanFillFace *sf_tri;
486
487                 unsigned int sf_vert_tot = 0;
488                 unsigned int tot_feather_quads = 0;
489
490                 if (masklay->restrictflag & MASK_RESTRICT_RENDER) {
491                         continue;
492                 }
493
494                 BLI_scanfill_begin(&sf_ctx);
495
496                 for (spline = masklay->splines.first; spline; spline = spline->next) {
497                         const unsigned int is_cyclic = (spline->flag & MASK_SPLINE_CYCLIC) != 0;
498                         const unsigned int is_fill = (spline->flag & MASK_SPLINE_NOFILL) == 0;
499
500                         float (*diff_points)[2];
501                         int tot_diff_point;
502
503                         float (*diff_feather_points)[2];
504                         int tot_diff_feather_points;
505
506                         diff_points = BKE_mask_spline_differentiate_with_resolution_ex(
507                                           spline, resol, &tot_diff_point);
508
509                         if (do_feather) {
510                                 diff_feather_points = BKE_mask_spline_feather_differentiated_points_with_resolution_ex(
511                                                           spline, resol, &tot_diff_feather_points);
512                         }
513                         else {
514                                 tot_diff_feather_points = 0;
515                                 diff_feather_points = NULL;
516                         }
517
518                         if (tot_diff_point > 3) {
519                                 ScanFillVert *sf_vert_prev;
520                                 int j;
521
522                                 float co[3];
523                                 co[2] = 0.0f;
524
525                                 if (do_aspect_correct) {
526                                         if (width != height) {
527                                                 float *fp;
528                                                 float *ffp;
529                                                 int i;
530                                                 float asp;
531
532                                                 if (width < height) {
533                                                         fp = &diff_points[0][0];
534                                                         ffp = tot_diff_feather_points ? &diff_feather_points[0][0] : NULL;
535                                                         asp = (float)width / (float)height;
536                                                 }
537                                                 else {
538                                                         fp = &diff_points[0][1];
539                                                         ffp = tot_diff_feather_points ? &diff_feather_points[0][1] : NULL;
540                                                         asp = (float)height / (float)width;
541                                                 }
542
543                                                 for (i = 0; i < tot_diff_point; i++, fp += 2) {
544                                                         (*fp) = (((*fp) - 0.5f) / asp) + 0.5f;
545                                                 }
546
547                                                 if (tot_diff_feather_points) {
548                                                         for (i = 0; i < tot_diff_feather_points; i++, ffp += 2) {
549                                                                 (*ffp) = (((*ffp) - 0.5f) / asp) + 0.5f;
550                                                         }
551                                                 }
552                                         }
553                                 }
554
555                                 /* fake aa, using small feather */
556                                 if (do_mask_aa == TRUE) {
557                                         if (do_feather == FALSE) {
558                                                 tot_diff_feather_points = tot_diff_point;
559                                                 diff_feather_points = MEM_mallocN(sizeof(*diff_feather_points) * tot_diff_feather_points,
560                                                                                   __func__);
561                                                 /* add single pixel feather */
562                                                 maskrasterize_spline_differentiate_point_outset(diff_feather_points, diff_points,
563                                                                                                tot_diff_point, pixel_size, FALSE);
564                                         }
565                                         else {
566                                                 /* ensure single pixel feather, on any zero feather areas */
567                                                 maskrasterize_spline_differentiate_point_outset(diff_feather_points, diff_points,
568                                                                                                tot_diff_point, pixel_size, TRUE);
569                                         }
570                                 }
571
572                                 if (is_fill) {
573                                         copy_v2_v2(co, diff_points[0]);
574                                         sf_vert_prev = BLI_scanfill_vert_add(&sf_ctx, co);
575                                         sf_vert_prev->tmp.u = sf_vert_tot;
576                                         sf_vert_prev->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
577                                         sf_vert_tot++;
578
579                                         /* TODO, an alternate functions so we can avoid double vector copy! */
580                                         for (j = 1; j < tot_diff_point; j++) {
581                                                 copy_v2_v2(co, diff_points[j]);
582                                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
583                                                 sf_vert->tmp.u = sf_vert_tot;
584                                                 sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
585                                                 sf_vert_tot++;
586                                         }
587
588                                         sf_vert = sf_vert_prev;
589                                         sf_vert_prev = sf_ctx.fillvertbase.last;
590
591                                         for (j = 0; j < tot_diff_point; j++) {
592                                                 ScanFillEdge *sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
593                                                 sf_edge->tmp.c = SF_EDGE_IS_BOUNDARY;
594
595                                                 sf_vert_prev = sf_vert;
596                                                 sf_vert = sf_vert->next;
597                                         }
598
599                                         if (diff_feather_points) {
600                                                 float co_feather[3];
601                                                 co_feather[2] = 1.0f;
602
603                                                 BLI_assert(tot_diff_feather_points == tot_diff_point);
604
605                                                 /* note: only added for convenience, we don't infact use these to scanfill,
606                                                  * only to create feather faces after scanfill */
607                                                 for (j = 0; j < tot_diff_feather_points; j++) {
608                                                         copy_v2_v2(co_feather, diff_feather_points[j]);
609                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
610
611                                                         /* no need for these attrs */
612         #if 0
613                                                         sf_vert->tmp.u = sf_vert_tot;
614                                                         sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
615         #endif
616                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
617                                                         sf_vert_tot++;
618                                                 }
619
620                                                 if (diff_feather_points) {
621                                                         MEM_freeN(diff_feather_points);
622                                                 }
623
624                                                 tot_feather_quads += tot_diff_point;
625                                         }
626                                 }
627                                 else {
628                                         /* unfilled spline */
629                                         if (diff_feather_points) {
630
631                                                 float co_diff[3];
632
633                                                 float co_feather[3];
634                                                 co_feather[2] = 1.0f;
635
636                                                 open_spline_ranges[open_spline_index].vertex_offset = sf_vert_tot;
637                                                 open_spline_ranges[open_spline_index].vertex_total = tot_diff_point;
638                                                 open_spline_ranges[open_spline_index].is_cyclic = is_cyclic;
639                                                 open_spline_index++;
640
641
642                                                 /* TODO, an alternate functions so we can avoid double vector copy! */
643                                                 for (j = 0; j < tot_diff_point; j++) {
644
645                                                         /* center vert */
646                                                         copy_v2_v2(co, diff_points[j]);
647                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
648                                                         sf_vert->tmp.u = sf_vert_tot;
649                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
650                                                         sf_vert_tot++;
651
652
653                                                         /* feather vert A */
654                                                         copy_v2_v2(co_feather, diff_feather_points[j]);
655                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
656                                                         sf_vert->tmp.u = sf_vert_tot;
657                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
658                                                         sf_vert_tot++;
659
660
661                                                         /* feather vert B */
662                                                         sub_v2_v2v2(co_diff, co, co_feather);
663                                                         add_v2_v2v2(co_feather, co, co_diff);
664                                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
665                                                         sf_vert->tmp.u = sf_vert_tot;
666                                                         sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
667                                                         sf_vert_tot++;
668
669                                                         tot_feather_quads += 2;
670                                                 }
671
672                                                 if (!is_cyclic) {
673                                                         tot_feather_quads -= 2;
674                                                 }
675
676                                                 MEM_freeN(diff_feather_points);
677
678                                                 /* ack these are infact tris, but they are extra faces so no matter,
679                                                  * +1 becausing adding one vert results in 2 tris (joining the existing endpoints)
680                                                  */
681                                                 // tot_feather_quads + ((SPLINE_RESOL_CAP + 1) * 2);
682
683                                         }
684                                 }
685                         }
686
687                         if (diff_points) {
688                                 MEM_freeN(diff_points);
689                         }
690                 }
691
692                 if (sf_ctx.fillvertbase.first) {
693                         unsigned int (*face_array)[4], *face;  /* access coords */
694                         float        (*face_coords)[3], *cos; /* xy, z 0-1 (1.0 == filled) */
695                         int sf_tri_tot;
696                         rctf bounds;
697                         int face_index;
698
699                         /* now we have all the splines */
700                         face_coords = MEM_mallocN((sizeof(float) * 3) * sf_vert_tot, "maskrast_face_coords");
701
702                         /* init bounds */
703                         BLI_rctf_init_minmax(&bounds);
704
705                         /* coords */
706                         cos = (float *)face_coords;
707                         for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert_next) {
708                                 sf_vert_next = sf_vert->next;
709                                 copy_v3_v3(cos, sf_vert->co);
710
711                                 /* remove so as not to interfear with fill (called after) */
712                                 if (sf_vert->keyindex == SF_KEYINDEX_TEMP_ID) {
713                                         BLI_remlink(&sf_ctx.fillvertbase, sf_vert);
714                                 }
715
716                                 /* bounds */
717                                 BLI_rctf_do_minmax_v(&bounds, cos);
718
719                                 cos += 3;
720                         }
721
722                         /* main scanfill */
723                         sf_tri_tot = BLI_scanfill_calc_ex(&sf_ctx, FALSE, zvec);
724
725                         face_array = MEM_mallocN(sizeof(*face_array) * (sf_tri_tot + tot_feather_quads), "maskrast_face_index");
726
727                         /* tri's */
728                         face = (unsigned int *)face_array;
729                         for (sf_tri = sf_ctx.fillfacebase.first, face_index = 0; sf_tri; sf_tri = sf_tri->next, face_index++) {
730                                 *(face++) = sf_tri->v1->tmp.u;
731                                 *(face++) = sf_tri->v2->tmp.u;
732                                 *(face++) = sf_tri->v3->tmp.u;
733                                 *(face++) = TRI_VERT;
734                         }
735
736                         /* start of feather faces... if we have this set,
737                          * 'face_index' is kept from loop above */
738
739                         BLI_assert(face_index == sf_tri_tot);
740
741                         if (tot_feather_quads) {
742                                 ScanFillEdge *sf_edge;
743
744                                 for (sf_edge = sf_ctx.filledgebase.first; sf_edge; sf_edge = sf_edge->next) {
745                                         if (sf_edge->tmp.c == SF_EDGE_IS_BOUNDARY) {
746                                                 *(face++) = sf_edge->v1->tmp.u;
747                                                 *(face++) = sf_edge->v2->tmp.u;
748                                                 *(face++) = sf_edge->v2->keyindex;
749                                                 *(face++) = sf_edge->v1->keyindex;
750
751                                                 face_index++;
752                                         }
753                                 }
754                         }
755
756                         /* feather only splines */
757                         while (open_spline_index > 0) {
758                                 unsigned int start_vidx          = open_spline_ranges[--open_spline_index].vertex_offset;
759                                 unsigned int tot_diff_point_sub1 = open_spline_ranges[  open_spline_index].vertex_total - 1;
760                                 unsigned int k, j;
761
762                                 j = start_vidx;
763
764                                 /* subtract one since we reference next vertex triple */
765                                 for (k = 0; k < tot_diff_point_sub1; k++, j += 3) {
766
767                                         BLI_assert(j == start_vidx + (k * 3));
768
769                                         *(face++) = j + 3; /* next span */ /* z 1 */
770                                         *(face++) = j + 0;                 /* z 1 */
771                                         *(face++) = j + 1;                 /* z 0 */
772                                         *(face++) = j + 4; /* next span */ /* z 0 */
773
774                                         face_index++;
775
776                                         *(face++) = j + 0;                 /* z 1 */
777                                         *(face++) = j + 3; /* next span */ /* z 1 */
778                                         *(face++) = j + 5; /* next span */ /* z 0 */
779                                         *(face++) = j + 2;                 /* z 0 */
780
781                                         face_index++;
782                                 }
783
784                                 if (open_spline_ranges[open_spline_index].is_cyclic) {
785                                         *(face++) = start_vidx + 0; /* next span */ /* z 1 */
786                                         *(face++) = j          + 0;                 /* z 1 */
787                                         *(face++) = j          + 1;                 /* z 0 */
788                                         *(face++) = start_vidx + 1; /* next span */ /* z 0 */
789
790                                         face_index++;
791
792                                         *(face++) = j          + 0;                 /* z 1 */
793                                         *(face++) = start_vidx + 0; /* next span */ /* z 1 */
794                                         *(face++) = start_vidx + 2; /* next span */ /* z 0 */
795                                         *(face++) = j          + 2;                 /* z 0 */
796
797                                         face_index++;
798                                 }
799                         }
800
801                         MEM_freeN(open_spline_ranges);
802
803                         // fprintf(stderr, "%d %d\n", face_index, sf_face_tot + tot_feather_quads);
804
805                         BLI_assert(face_index == sf_tri_tot + tot_feather_quads);
806
807                         {
808                                 MaskRasterLayer *layer = &mr_handle->layers[masklay_index];
809
810                                 if (BLI_rctf_isect(&default_bounds, &bounds, &bounds)) {
811                                         layer->face_tot = sf_tri_tot + tot_feather_quads;
812                                         layer->face_coords = face_coords;
813                                         layer->face_array  = face_array;
814                                         layer->bounds = bounds;
815
816                                         layer_bucket_init(layer, pixel_size);
817
818                                         BLI_rctf_union(&mr_handle->bounds, &bounds);
819                                 }
820                                 else {
821                                         MEM_freeN(face_coords);
822                                         MEM_freeN(face_array);
823
824                                         layer->face_tot = 0;
825                                         layer->face_coords = NULL;
826                                         layer->face_array  = NULL;
827
828                                         layer_bucket_init_dummy(layer);
829
830                                         BLI_rctf_init(&layer->bounds, -1.0f, -1.0f, -1.0f, -1.0f);
831                                 }
832
833                                 /* copy as-is */
834                                 layer->alpha = masklay->alpha;
835                                 layer->blend = masklay->blend;
836                                 layer->blend_flag = masklay->blend_flag;
837                                 layer->falloff = masklay->falloff;
838                         }
839
840                         /* printf("tris %d, feather tris %d\n", sf_tri_tot, tot_feather_quads); */
841                 }
842
843                 /* add trianges */
844                 BLI_scanfill_end(&sf_ctx);
845         }
846 }
847
848
849 /* --------------------------------------------------------------------- */
850 /* functions that run inside the sampling thread (keep fast!)            */
851 /* --------------------------------------------------------------------- */
852
853 /* 2D ray test */
854 static float maskrasterize_layer_z_depth_tri(const float pt[2],
855                                              const float v1[3], const float v2[3], const float v3[3])
856 {
857         float w[3];
858         barycentric_weights_v2(v1, v2, v3, pt, w);
859         return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]);
860 }
861
862 #if 0
863 static float maskrasterize_layer_z_depth_quad(const float pt[2],
864                                               const float v1[3], const float v2[3], const float v3[3], const float v4[3])
865 {
866         float w[4];
867         barycentric_weights_v2_quad(v1, v2, v3, v4, pt, w);
868         return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]) + (v4[2] * w[3]);
869 }
870 #endif
871
872 static float maskrasterize_layer_isect(unsigned int *face, float (*cos)[3], const float dist_orig, const float xy[2])
873 {
874         /* we always cast from same place only need xy */
875         if (face[3] == TRI_VERT) {
876                 /* --- tri --- */
877
878 #if 0
879                 /* not essential but avoids unneeded extra lookups */
880                 if ((cos[0][2] < dist_orig) ||
881                     (cos[1][2] < dist_orig) ||
882                     (cos[2][2] < dist_orig))
883                 {
884                         if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
885                                 /* we know all tris are close for now */
886                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[1]], cos[face[2]]);
887                         }
888                 }
889 #else
890                 /* we know all tris are close for now */
891                 if (1) {
892                         if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
893                                 return 0.0f;
894                         }
895                 }
896 #endif
897         }
898         else {
899                 /* --- quad --- */
900
901                 /* not essential but avoids unneeded extra lookups */
902                 if ((cos[0][2] < dist_orig) ||
903                     (cos[1][2] < dist_orig) ||
904                     (cos[2][2] < dist_orig) ||
905                     (cos[3][2] < dist_orig))
906                 {
907
908                         /* needs work */
909 #if 0
910                         if (isect_point_quad_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]], cos[face[3]])) {
911                                 return maskrasterize_layer_z_depth_quad(xy, cos[face[0]], cos[face[1]], cos[face[2]], cos[face[3]]);
912                         }
913 #elif 1
914                         if (isect_point_tri_v2(xy, cos[face[0]], cos[face[1]], cos[face[2]])) {
915                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[1]], cos[face[2]]);
916                         }
917                         else if (isect_point_tri_v2(xy, cos[face[0]], cos[face[2]], cos[face[3]])) {
918                                 return maskrasterize_layer_z_depth_tri(xy, cos[face[0]], cos[face[2]], cos[face[3]]);
919                         }
920 #else
921                         /* cheat - we know first 2 verts are z0.0f and second 2 are z 1.0f */
922                         /* ... worth looking into */
923 #endif
924                 }
925         }
926
927         return 1.0f;
928 }
929
930 BLI_INLINE unsigned int layer_bucket_index_from_xy(MaskRasterLayer *layer, const float xy[2])
931 {
932         BLI_assert(BLI_in_rctf_v(&layer->bounds, xy));
933
934         return ( (unsigned int)((xy[0] - layer->bounds.xmin) * layer->buckets_xy_scalar[0])) +
935                (((unsigned int)((xy[1] - layer->bounds.ymin) * layer->buckets_xy_scalar[1])) * layer->buckets_x);
936 }
937
938 static float layer_bucket_depth_from_xy(MaskRasterLayer *layer, const float xy[2])
939 {
940         unsigned int index = layer_bucket_index_from_xy(layer, xy);
941         unsigned int *face_index = layer->buckets_face[index];
942
943         if (face_index) {
944                 unsigned int (*face_array)[4] = layer->face_array;
945                 float        (*cos)[3]        = layer->face_coords;
946                 float best_dist = 1.0f;
947                 while (*face_index != TRI_TERMINATOR_ID) {
948                         const float test_dist = maskrasterize_layer_isect(face_array[*face_index], cos, best_dist, xy);
949                         if (test_dist < best_dist) {
950                                 best_dist = test_dist;
951                                 /* comparing with 0.0f is OK here because triangles are always zero depth */
952                                 if (best_dist == 0.0f) {
953                                         /* bail early, we're as close as possible */
954                                         return 0.0f;
955                                 }
956                         }
957                         face_index++;
958                 }
959                 return best_dist;
960         }
961         else {
962                 return 1.0f;
963         }
964 }
965
966 float BLI_maskrasterize_handle_sample(MaskRasterHandle *mr_handle, const float xy[2])
967 {
968         /* can't do this because some layers may invert */
969         /* if (BLI_in_rctf_v(&mr_handle->bounds, xy)) */
970
971         const unsigned int layers_tot = mr_handle->layers_tot;
972         unsigned int i;
973         MaskRasterLayer *layer = mr_handle->layers;
974
975         /* return value */
976         float value = 0.0f;
977
978         for (i = 0; i < layers_tot; i++, layer++) {
979                 float value_layer;
980
981                 if (BLI_in_rctf_v(&layer->bounds, xy)) {
982                         float val = 1.0f - layer_bucket_depth_from_xy(layer, xy);
983
984                         switch (layer->falloff) {
985                                 case PROP_SMOOTH:
986                                         /* ease - gives less hard lines for dilate/erode feather */
987                                         val = (3.0f * val * val - 2.0f * val * val * val);
988                                         break;
989                                 case PROP_SPHERE:
990                                         val = sqrtf(2.0f * val - val * val);
991                                         break;
992                                 case PROP_ROOT:
993                                         val = sqrtf(val);
994                                         break;
995                                 case PROP_SHARP:
996                                         val = val * val;
997                                         break;
998                                 case PROP_LIN:
999                                 default:
1000                                         /* nothing */
1001                                         break;
1002                         }
1003
1004                         value_layer = val * layer->alpha;
1005                 }
1006                 else {
1007                         value_layer = 0.0f;
1008                 }
1009
1010                 if (layer->blend_flag & MASK_BLENDFLAG_INVERT) {
1011                         value_layer = 1.0f - value_layer;
1012                 }
1013
1014                 switch (layer->blend) {
1015                         case MASK_BLEND_SUBTRACT:
1016                         {
1017                                 value -= value_layer;
1018                                 break;
1019                         }
1020                         case MASK_BLEND_ADD:
1021                         default:
1022                         {
1023                                 value += value_layer;
1024                                 break;
1025                         }
1026                 }
1027         }
1028
1029         return CLAMPIS(value, 0.0f, 1.0f);
1030 }
1031
1032 #endif /* USE_RASKTER */