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