more minor speedups for new mask rasterizer
[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
36 #include "BLI_utildefines.h"
37 #include "BLI_scanfill.h"
38 #include "BLI_memarena.h"
39
40 #include "BLI_math.h"
41 #include "BLI_rect.h"
42 #include "BLI_listbase.h"
43 #include "BLI_linklist.h"
44
45 #include "BKE_mask.h"
46
47 #ifndef USE_RASKTER
48
49 /**
50  * A single #MaskRasterHandle contains multile #MaskRasterLayer's,
51  * each #MaskRasterLayer does its own lookup which contributes to
52  * the final pixel with its own blending mode and the final pixel is blended between these.
53  */
54
55 /* internal use only */
56 typedef struct MaskRasterLayer {
57         /* geometry */
58         unsigned int   tri_tot;
59         unsigned int (*tri_array)[4];  /* access coords tri/quad */
60         float        (*tri_coords)[3]; /* xy, z 0-1 (1.0 == filled) */
61
62
63         /* 2d bounds (to quickly skip raytree lookup) */
64         rctf bounds;
65
66
67         /* buckets */
68         unsigned int **buckets_tri;
69         /* cache divide and subtract */
70         float buckets_xy_scalar[2]; /* 1.0 / (buckets_width + FLT_EPSILON) */
71         unsigned int buckets_x;
72         unsigned int buckets_y;
73
74
75         /* copied direct from #MaskLayer.--- */
76         /* blending options */
77         float  alpha;
78         char   blend;
79         char   blend_flag;
80
81 } MaskRasterLayer;
82
83 static void layer_bucket_init(MaskRasterLayer *layer);
84
85 /**
86  * opaque local struct for mask pixel lookup, each MaskLayer needs one of these
87  */
88 struct MaskRasterHandle {
89         MaskRasterLayer *layers;
90         unsigned int     layers_tot;
91
92         /* 2d bounds (to quickly skip raytree lookup) */
93         rctf bounds;
94 };
95
96 MaskRasterHandle *BLI_maskrasterize_handle_new(void)
97 {
98         MaskRasterHandle *mr_handle;
99
100         mr_handle = MEM_callocN(sizeof(MaskRasterHandle), STRINGIFY(MaskRasterHandle));
101
102         return mr_handle;
103 }
104
105 void BLI_maskrasterize_handle_free(MaskRasterHandle *mr_handle)
106 {
107         const unsigned int layers_tot = mr_handle->layers_tot;
108         unsigned int i;
109         MaskRasterLayer *raslayers = mr_handle->layers;
110
111         /* raycast vars */
112         for (i = 0; i < layers_tot; i++, raslayers++) {
113
114                 if (raslayers->tri_array) {
115                         MEM_freeN(raslayers->tri_array);
116                 }
117
118                 if (raslayers->tri_coords) {
119                         MEM_freeN(raslayers->tri_coords);
120                 }
121
122                 if (raslayers->buckets_tri) {
123                         const unsigned int   bucket_tot = raslayers->buckets_x * raslayers->buckets_y;
124                         unsigned int bucket_index;
125                         for (bucket_index = 0; bucket_index < bucket_tot; bucket_index++) {
126                                 unsigned int *tri_index = raslayers->buckets_tri[bucket_index];
127                                 if (tri_index) {
128                                         MEM_freeN(tri_index);
129                                 }
130                         }
131
132                         MEM_freeN(raslayers->buckets_tri);
133                 }
134         }
135
136         MEM_freeN(mr_handle->layers);
137         MEM_freeN(mr_handle);
138 }
139
140 #define RESOL 32
141
142 #define PRINT_MASK_DEBUG printf
143
144 #define SF_EDGE_IS_BOUNDARY 0xff
145
146 #define SF_KEYINDEX_TEMP_ID ((unsigned int) -1)
147 #define TRI_TERMINATOR_ID   ((unsigned int) -1)
148
149
150 void maskrasterize_spline_differentiate_point_inset(float (*diff_feather_points)[2], float (*diff_points)[2],
151                                                     const unsigned int tot_diff_point, const float ofs,
152                                                     const short do_test)
153 {
154         unsigned int k_prev = tot_diff_point - 2;
155         unsigned int k_curr = tot_diff_point - 1;
156         unsigned int k_next = 0;
157
158         unsigned int k;
159
160         float d_prev[2];
161         float d_next[2];
162         float d[2];
163
164         const float *co_prev;
165         const float *co_curr;
166         const float *co_next;
167
168         const float ofs_squared = ofs * ofs;
169
170         co_prev = diff_points[k_prev];
171         co_curr = diff_points[k_curr];
172         co_next = diff_points[k_next];
173
174         /* precalc */
175         sub_v2_v2v2(d_prev, co_prev, co_curr);
176         normalize_v2(d_prev);
177
178         for (k = 0; k < tot_diff_point; k++) {
179
180                 co_prev = diff_points[k_prev];
181                 co_curr = diff_points[k_curr];
182                 co_next = diff_points[k_next];
183
184                 /* sub_v2_v2v2(d_prev, co_prev, co_curr); */ /* precalc */
185                 sub_v2_v2v2(d_next, co_curr, co_next);
186
187                 /* normalize_v2(d_prev); */ /* precalc */
188                 normalize_v2(d_next);
189
190                 if ((do_test == FALSE) ||
191                     (len_squared_v2v2(diff_feather_points[k], diff_points[k]) < ofs_squared))
192                 {
193
194                         add_v2_v2v2(d, d_prev, d_next);
195
196                         normalize_v2(d);
197
198                         diff_feather_points[k][0] = diff_points[k][0] + ( d[1] * ofs);
199                         diff_feather_points[k][1] = diff_points[k][1] + (-d[0] * ofs);
200                 }
201
202                 /* use next iter */
203                 copy_v2_v2(d_prev, d_next);
204
205                 k_prev = k_curr;
206                 k_curr = k_next;
207                 k_next++;
208         }
209 }
210
211 #define TRI_VERT ((unsigned int) -1)
212
213 void BLI_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mask,
214                                    const int width, const int height,
215                                    const short do_aspect_correct, const short do_mask_aa,
216                                    const short do_feather)
217 {
218         /* TODO: real size */
219         const int resol = RESOL;
220         const float aa_filter_size = 1.0f / MIN2(width, height);
221
222         const float zvec[3] = {0.0f, 0.0f, 1.0f};
223         MaskLayer *masklay;
224         unsigned int masklay_index;
225
226         mr_handle->layers_tot = BLI_countlist(&mask->masklayers);
227         mr_handle->layers = MEM_mallocN(sizeof(MaskRasterLayer) * mr_handle->layers_tot, STRINGIFY(MaskRasterLayer));
228         BLI_rctf_init_minmax(&mr_handle->bounds);
229
230         for (masklay = mask->masklayers.first, masklay_index = 0; masklay; masklay = masklay->next, masklay_index++) {
231
232                 MaskSpline *spline;
233
234                 /* scanfill */
235                 ScanFillContext sf_ctx;
236                 ScanFillVert *sf_vert = NULL;
237                 ScanFillVert *sf_vert_next = NULL;
238                 ScanFillFace *sf_tri;
239
240                 unsigned int sf_vert_tot = 0;
241                 unsigned int tot_feather_quads = 0;
242
243                 if (masklay->restrictflag & MASK_RESTRICT_RENDER) {
244                         continue;
245                 }
246
247                 BLI_scanfill_begin(&sf_ctx);
248
249                 for (spline = masklay->splines.first; spline; spline = spline->next) {
250
251                         float (*diff_points)[2];
252                         int tot_diff_point;
253
254                         float (*diff_feather_points)[2];
255                         int tot_diff_feather_points;
256
257                         diff_points = BKE_mask_spline_differentiate_with_resolution_ex(spline, resol, &tot_diff_point);
258
259                         /* dont ch*/
260                         if (do_feather) {
261                                 diff_feather_points = BKE_mask_spline_feather_differentiated_points_with_resolution_ex(spline, resol, &tot_diff_feather_points);
262                         }
263                         else {
264                                 tot_diff_feather_points = 0;
265                                 diff_feather_points = NULL;
266                         }
267
268                         if (tot_diff_point > 3) {
269                                 ScanFillVert *sf_vert_prev;
270                                 int j;
271
272                                 float co[3];
273                                 co[2] = 0.0f;
274
275                                 if (do_aspect_correct) {
276                                         if (width != height) {
277                                                 float *fp;
278                                                 float *ffp;
279                                                 int i;
280                                                 float asp;
281
282                                                 if (width < height) {
283                                                         fp = &diff_points[0][0];
284                                                         ffp = tot_diff_feather_points ? &diff_feather_points[0][0] : NULL;
285                                                         asp = (float)width / (float)height;
286                                                 }
287                                                 else {
288                                                         fp = &diff_points[0][1];
289                                                         ffp = tot_diff_feather_points ? &diff_feather_points[0][1] : NULL;
290                                                         asp = (float)height / (float)width;
291                                                 }
292
293                                                 for (i = 0; i < tot_diff_point; i++, fp += 2) {
294                                                         (*fp) = (((*fp) - 0.5f) / asp) + 0.5f;
295                                                 }
296
297                                                 if (tot_diff_feather_points) {
298                                                         for (i = 0; i < tot_diff_feather_points; i++, ffp += 2) {
299                                                                 (*ffp) = (((*ffp) - 0.5f) / asp) + 0.5f;
300                                                         }
301                                                 }
302                                         }
303                                 }
304
305                                 /* fake aa, using small feather */
306                                 if (do_mask_aa == TRUE) {
307                                         if (do_feather == FALSE) {
308                                                 tot_diff_feather_points = tot_diff_point;
309                                                 diff_feather_points = MEM_mallocN(sizeof(*diff_feather_points) * tot_diff_feather_points, __func__);
310                                                 /* add single pixel feather */
311                                                 maskrasterize_spline_differentiate_point_inset(diff_feather_points, diff_points,
312                                                                                                tot_diff_point, aa_filter_size, FALSE);
313                                         }
314                                         else {
315                                                 /* ensure single pixel feather, on any zero feather areas */
316                                                 maskrasterize_spline_differentiate_point_inset(diff_feather_points, diff_points,
317                                                                                                tot_diff_point, aa_filter_size, TRUE);
318                                         }
319                                 }
320
321                                 copy_v2_v2(co, diff_points[0]);
322                                 sf_vert_prev = BLI_scanfill_vert_add(&sf_ctx, co);
323                                 sf_vert_prev->tmp.u = sf_vert_tot;
324                                 sf_vert_prev->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
325                                 sf_vert_tot++;
326
327                                 /* TODO, an alternate functions so we can avoid double vector copy! */
328                                 for (j = 1; j < tot_diff_point; j++) {
329                                         copy_v2_v2(co, diff_points[j]);
330                                         sf_vert = BLI_scanfill_vert_add(&sf_ctx, co);
331                                         sf_vert->tmp.u = sf_vert_tot;
332                                         sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
333                                         sf_vert_tot++;
334                                 }
335
336                                 sf_vert = sf_vert_prev;
337                                 sf_vert_prev = sf_ctx.fillvertbase.last;
338
339                                 for (j = 0; j < tot_diff_point; j++) {
340                                         ScanFillEdge *sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
341                                         sf_edge->tmp.c = SF_EDGE_IS_BOUNDARY;
342
343                                         sf_vert_prev = sf_vert;
344                                         sf_vert = sf_vert->next;
345                                 }
346
347                                 if (diff_feather_points) {
348                                         float co_feather[3];
349                                         co_feather[2] = 1.0f;
350
351                                         BLI_assert(tot_diff_feather_points == tot_diff_point);
352
353                                         /* note: only added for convenience, we dont infact use these to scanfill,
354                                          * only to create feather faces after scanfill */
355                                         for (j = 0; j < tot_diff_feather_points; j++) {
356                                                 copy_v2_v2(co_feather, diff_feather_points[j]);
357                                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, co_feather);
358
359                                                 /* no need for these attrs */
360 #if 0
361                                                 sf_vert->tmp.u = sf_vert_tot;
362                                                 sf_vert->keyindex = sf_vert_tot + tot_diff_point; /* absolute index of feather vert */
363 #endif
364                                                 sf_vert->keyindex = SF_KEYINDEX_TEMP_ID;
365                                                 sf_vert_tot++;
366                                         }
367
368                                         if (diff_feather_points) {
369                                                 MEM_freeN(diff_feather_points);
370                                         }
371
372                                         tot_feather_quads += tot_diff_point;
373                                 }
374                         }
375
376                         if (diff_points) {
377                                 MEM_freeN(diff_points);
378                         }
379                 }
380
381                 if (sf_ctx.fillvertbase.first) {
382                         unsigned int (*tri_array)[4], *tri;  /* access coords */
383                         float        (*tri_coords)[3], *cos; /* xy, z 0-1 (1.0 == filled) */
384                         int sf_tri_tot;
385                         rctf bounds;
386                         int tri_index;
387
388                         float bvhcos[4][3];
389
390                         /* now we have all the splines */
391                         tri_coords = MEM_mallocN((sizeof(float) * 3) * sf_vert_tot, "maskrast_tri_coords");
392
393                         /* init bounds */
394                         BLI_rctf_init_minmax(&bounds);
395
396                         /* coords */
397                         cos = (float *)tri_coords;
398                         for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert_next) {
399                                 sf_vert_next = sf_vert->next;
400                                 copy_v3_v3(cos, sf_vert->co);
401
402                                 /* remove so as not to interfear with fill (called after) */
403                                 if (sf_vert->keyindex == SF_KEYINDEX_TEMP_ID) {
404                                         BLI_remlink(&sf_ctx.fillvertbase, sf_vert);
405                                 }
406
407                                 /* bounds */
408                                 BLI_rctf_do_minmax_v(&bounds, cos);
409
410                                 cos += 3;
411                         }
412
413                         /* main scanfill */
414                         sf_tri_tot = BLI_scanfill_calc_ex(&sf_ctx, FALSE, zvec);
415
416                         tri_array = MEM_mallocN(sizeof(*tri_array) * (sf_tri_tot + tot_feather_quads), "maskrast_tri_index");
417
418                         /* tri's */
419                         tri = (unsigned int *)tri_array;
420                         for (sf_tri = sf_ctx.fillfacebase.first, tri_index = 0; sf_tri; sf_tri = sf_tri->next, tri_index++) {
421                                 *(tri++) = sf_tri->v1->tmp.u;
422                                 *(tri++) = sf_tri->v2->tmp.u;
423                                 *(tri++) = sf_tri->v3->tmp.u;
424                                 *(tri++) = TRI_VERT;
425                         }
426
427                         /* start of feather faces... if we have this set,
428                          * 'tri_index' is kept from loop above */
429
430                         BLI_assert(tri_index == sf_tri_tot);
431
432                         if (tot_feather_quads) {
433                                 ScanFillEdge *sf_edge;
434
435                                 for (sf_edge = sf_ctx.filledgebase.first; sf_edge; sf_edge = sf_edge->next) {
436                                         if (sf_edge->tmp.c == SF_EDGE_IS_BOUNDARY) {
437                                                 *(tri++) = sf_edge->v1->tmp.u;
438                                                 *(tri++) = sf_edge->v2->tmp.u;
439                                                 *(tri++) = sf_edge->v2->keyindex;
440                                                 *(tri++) = sf_edge->v1->keyindex;
441
442                                                 copy_v3_v3(bvhcos[0], tri_coords[*(tri - 4)]);
443                                                 copy_v3_v3(bvhcos[1], tri_coords[*(tri - 3)]);
444                                                 copy_v3_v3(bvhcos[2], tri_coords[*(tri - 2)]);
445                                                 copy_v3_v3(bvhcos[3], tri_coords[*(tri - 1)]);
446
447                                                 tri_index++;
448                                         }
449                                 }
450                         }
451
452                         fprintf(stderr, "%d %d\n", tri_index, sf_tri_tot + tot_feather_quads);
453
454                         BLI_assert(tri_index == sf_tri_tot + tot_feather_quads);
455
456                         {
457                                 MaskRasterLayer *raslayer = &mr_handle->layers[masklay_index];
458
459                                 raslayer->tri_tot = sf_tri_tot + tot_feather_quads;
460                                 raslayer->tri_coords = tri_coords;
461                                 raslayer->tri_array  = tri_array;
462                                 raslayer->bounds  = bounds;
463
464                                 /* copy as-is */
465                                 raslayer->alpha = masklay->alpha;
466                                 raslayer->blend = masklay->blend;
467                                 raslayer->blend_flag = masklay->blend_flag;
468
469                                 layer_bucket_init(raslayer);
470
471                                 BLI_union_rctf(&mr_handle->bounds, &bounds);
472                         }
473
474                         PRINT_MASK_DEBUG("tris %d, feather tris %d\n", sf_tri_tot, tot_feather_quads);
475                 }
476
477                 /* add trianges */
478                 BLI_scanfill_end(&sf_ctx);
479         }
480 }
481
482 /* 2D ray test */
483 static float maskrasterize_layer_z_depth_tri(const float pt[2],
484                                              const float v1[3], const float v2[3], const float v3[3])
485 {
486         float w[3];
487         barycentric_weights_v2(v1, v2, v3, pt, w);
488         return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]);
489 }
490
491 #if 0
492 static float maskrasterize_layer_z_depth_quad(const float pt[2],
493                                               const float v1[3], const float v2[3], const float v3[3], const float v4[3])
494 {
495         float w[4];
496         barycentric_weights_v2_quad(v1, v2, v3, v4, pt, w);
497         return (v1[2] * w[0]) + (v2[2] * w[1]) + (v3[2] * w[2]) + (v4[2] * w[3]);
498 }
499 #endif
500
501 static float maskrasterize_layer_isect(unsigned int *tri, float (*cos)[3], const float dist_orig, const float xy[2])
502 {
503         /* we always cast from same place only need xy */
504         if (tri[3] == TRI_VERT) {
505                 /* --- tri --- */
506
507 #if 0
508                 /* not essential but avoids unneeded extra lookups */
509                 if ((cos[0][2] < dist_orig) ||
510                     (cos[1][2] < dist_orig) ||
511                     (cos[2][2] < dist_orig))
512                 {
513                         if (isect_point_tri_v2(xy, cos[tri[0]], cos[tri[1]], cos[tri[2]])) {
514                                 /* we know all tris are close for now */
515                                 return maskrasterize_layer_z_depth_tri(xy, cos[tri[0]], cos[tri[1]], cos[tri[2]]);
516                         }
517                 }
518 #else
519         /* we know all tris are close for now */
520                 if (1) {
521                         if (isect_point_tri_v2(xy, cos[tri[0]], cos[tri[1]], cos[tri[2]])) {
522                                 return 0.0f;
523                         }
524                 }
525 #endif
526         }
527         else {
528                 /* --- quad --- */
529
530                 /* not essential but avoids unneeded extra lookups */
531                 if ((cos[0][2] < dist_orig) ||
532                     (cos[1][2] < dist_orig) ||
533                     (cos[2][2] < dist_orig) ||
534                     (cos[3][2] < dist_orig))
535                 {
536
537                         /* needs work */
538 #if 0
539                         if (isect_point_quad_v2(xy, cos[tri[0]], cos[tri[1]], cos[tri[2]], cos[tri[3]])) {
540                                 return maskrasterize_layer_z_depth_quad(xy, cos[tri[0]], cos[tri[1]], cos[tri[2]], cos[tri[3]]);
541                         }
542 #elif 1
543                         if (isect_point_tri_v2(xy, cos[tri[0]], cos[tri[1]], cos[tri[2]])) {
544                                 return maskrasterize_layer_z_depth_tri(xy, cos[tri[0]], cos[tri[1]], cos[tri[2]]);
545                         }
546                         else if (isect_point_tri_v2(xy, cos[tri[0]], cos[tri[2]], cos[tri[3]])) {
547                                 return maskrasterize_layer_z_depth_tri(xy, cos[tri[0]], cos[tri[2]], cos[tri[3]]);
548                         }
549 #else
550                         /* cheat - we know first 2 verts are z0.0f and second 2 are z 1.0f */
551                         /* ... worth looking into */
552 #endif
553                 }
554         }
555
556         return 1.0f;
557 }
558
559 static void layer_bucket_init(MaskRasterLayer *layer)
560 {
561         MemArena *arena = BLI_memarena_new(1 << 16, __func__);
562
563         /* TODO - calculate best bucket size */
564         layer->buckets_x = 256;
565         layer->buckets_y = 256;
566
567         layer->buckets_xy_scalar[0] = (1.0f / ((layer->bounds.xmax - layer->bounds.xmin) + FLT_EPSILON)) * layer->buckets_x;
568         layer->buckets_xy_scalar[1] = (1.0f / ((layer->bounds.ymax - layer->bounds.ymin) + FLT_EPSILON)) * layer->buckets_y;
569
570         {
571                 unsigned int *tri = &layer->tri_array[0][0];
572                 float (*cos)[3] = layer->tri_coords;
573
574                 const unsigned int   bucket_tot = layer->buckets_x * layer->buckets_y;
575                 LinkNode     **bucketstore     = MEM_callocN(bucket_tot * sizeof(LinkNode *),  __func__);
576                 unsigned int  *bucketstore_tot = MEM_callocN(bucket_tot * sizeof(unsigned int), __func__);
577
578                 unsigned int tri_index;
579
580                 for (tri_index = 0; tri_index < layer->tri_tot; tri_index++, tri += 4) {
581                         float xmin;
582                         float xmax;
583                         float ymin;
584                         float ymax;
585
586                         if (tri[3] == TRI_VERT) {
587                                 const float *v1 = cos[tri[0]];
588                                 const float *v2 = cos[tri[1]];
589                                 const float *v3 = cos[tri[2]];
590
591                                 xmin = fminf(v1[0], fminf(v2[0], v3[0]));
592                                 xmax = fmaxf(v1[0], fmaxf(v2[0], v3[0]));
593                                 ymin = fminf(v1[1], fminf(v2[1], v3[1]));
594                                 ymax = fmaxf(v1[1], fmaxf(v2[1], v3[1]));
595                         }
596                         else {
597                                 const float *v1 = cos[tri[0]];
598                                 const float *v2 = cos[tri[1]];
599                                 const float *v3 = cos[tri[2]];
600                                 const float *v4 = cos[tri[3]];
601
602                                 xmin = fminf(v1[0], fminf(v2[0], fminf(v3[0], v4[0])));
603                                 xmax = fmaxf(v1[0], fmaxf(v2[0], fmaxf(v3[0], v4[0])));
604                                 ymin = fminf(v1[1], fminf(v2[1], fminf(v3[1], v4[1])));
605                                 ymax = fmaxf(v1[1], fmaxf(v2[1], fmaxf(v3[1], v4[1])));
606                         }
607
608
609                         /* not essential but may as will skip any faces outside the view */
610                         if (!((xmax < 0.0f) || (ymax < 0.0f) || (xmin > 1.0f) || (ymin > 1.0f))) {
611                                 const unsigned int xi_min = (unsigned int) ((xmin - layer->bounds.xmin) * layer->buckets_xy_scalar[0]);
612                                 const unsigned int xi_max = (unsigned int) ((xmax - layer->bounds.xmin) * layer->buckets_xy_scalar[0]);
613                                 const unsigned int yi_min = (unsigned int) ((ymin - layer->bounds.ymin) * layer->buckets_xy_scalar[1]);
614                                 const unsigned int yi_max = (unsigned int) ((ymax - layer->bounds.ymin) * layer->buckets_xy_scalar[1]);
615
616                                 unsigned int xi, yi;
617
618                                 for (xi = xi_min; xi <= xi_max; xi++) {
619                                         for (yi = yi_min; yi <= yi_max; yi++) {
620                                                 unsigned int bucket_index = (layer->buckets_x * yi) + xi;
621
622                                                 BLI_assert(xi < layer->buckets_x);
623                                                 BLI_assert(yi < layer->buckets_y);
624                                                 BLI_assert(bucket_index < bucket_tot);
625
626                                                 BLI_linklist_prepend_arena(&bucketstore[bucket_index],
627                                                    SET_UINT_IN_POINTER(tri_index),
628                                                    arena);
629
630                                                 bucketstore_tot[bucket_index]++;
631                                         }
632                                 }
633                         }
634                 }
635
636                 if (1) {
637             /* now convert linknodes into arrays for faster per pixel access */
638                         unsigned int  **buckets_tri = MEM_mallocN(bucket_tot * sizeof(unsigned int **), __func__);
639                         unsigned int bucket_index;
640
641                         for (bucket_index = 0; bucket_index < bucket_tot; bucket_index++) {
642                                 if (bucketstore_tot[bucket_index]) {
643                                         unsigned int  *bucket = MEM_mallocN((bucketstore_tot[bucket_index] + 1) * sizeof(unsigned int), __func__);
644                                         LinkNode *bucket_node;
645
646                                         buckets_tri[bucket_index] = bucket;
647
648                                         for (bucket_node = bucketstore[bucket_index]; bucket_node; bucket_node = bucket_node->next) {
649                                                 *bucket = GET_UINT_FROM_POINTER(bucket_node->link);
650                                                 bucket++;
651                                         }
652                                         *bucket = TRI_TERMINATOR_ID;
653                                 }
654                                 else {
655                                         buckets_tri[bucket_index] = NULL;
656                                 }
657                         }
658
659                         layer->buckets_tri = buckets_tri;
660                 }
661
662                 MEM_freeN(bucketstore);
663                 MEM_freeN(bucketstore_tot);
664         }
665
666         BLI_memarena_free(arena);
667 }
668
669 static unsigned int layer_bucket_index_from_xy(MaskRasterLayer *layer, const float xy[2])
670 {
671         BLI_assert(BLI_in_rctf_v(&layer->bounds, xy));
672
673         return ( (unsigned int)((xy[0] - layer->bounds.xmin) * layer->buckets_xy_scalar[0])) +
674                (((unsigned int)((xy[1] - layer->bounds.ymin) * layer->buckets_xy_scalar[1])) * layer->buckets_x);
675 }
676
677 static float layer_bucket_depth_from_xy(MaskRasterLayer *layer, const float xy[2])
678 {
679         unsigned int index = layer_bucket_index_from_xy(layer, xy);
680         unsigned int *tri_index = layer->buckets_tri[index];
681
682         if (tri_index) {
683                 float (*cos)[3] = layer->tri_coords;
684                 float best_dist = 1.0f;
685                 float test_dist;
686                 while (*tri_index != TRI_TERMINATOR_ID) {
687                         unsigned int *tri = layer->tri_array[*tri_index];
688                         if ((test_dist = maskrasterize_layer_isect(tri, cos, best_dist, xy)) < best_dist) {
689                                 best_dist = test_dist;
690                 /* comparing with 0.0f is OK here because triangles are always zero depth */
691                                 if (best_dist == 0.0f) {
692                     /* bail early, we're as close as possible  */
693                                         return 0.0f;
694                                 }
695                         }
696                         tri_index++;
697                 }
698                 return best_dist;
699         }
700         else {
701                 return 1.0f;
702         }
703 }
704
705
706 float BLI_maskrasterize_handle_sample(MaskRasterHandle *mr_handle, const float xy[2])
707 {
708         if (BLI_in_rctf_v(&mr_handle->bounds, xy)) {
709                 const unsigned int layers_tot = mr_handle->layers_tot;
710                 unsigned int i;
711                 MaskRasterLayer *layer = mr_handle->layers;
712
713                 /* raycast vars*/
714
715                 /* return */
716                 float value = 0.0f;
717
718                 for (i = 0; i < layers_tot; i++, layer++) {
719                         if (BLI_in_rctf_v(&layer->bounds, xy)) {
720                 /* --- hit (start) --- */
721                 const float dist = 1.0f - layer_bucket_depth_from_xy(layer, xy);
722                 const float dist_ease = (3.0f * dist * dist - 2.0f * dist * dist * dist);
723
724                 float v;
725                 /* apply alpha */
726                 v = dist_ease * layer->alpha;
727
728                 if (layer->blend_flag & MASK_BLENDFLAG_INVERT) {
729                     v = 1.0f - v;
730                 }
731
732                 switch (layer->blend) {
733                     case MASK_BLEND_SUBTRACT:
734                     {
735                         value -= v;
736                         break;
737                     }
738                     case MASK_BLEND_ADD:
739                     default:
740                     {
741                         value += v;
742                         break;
743                     }
744                 }
745                                 /* --- hit (end) --- */
746
747                         }
748                 }
749
750                 return CLAMPIS(value, 0.0f, 1.0f);
751         }
752         else {
753                 return 0.0f;
754         }
755 }
756
757 #endif /* USE_RASKTER */