source/blender/editors/sculpt_paint/paint_image.c

   1 /*
   2  * $Id$
   3  * imagepaint.c
   4  *
   5  * Functions to paint images in 2D and 3D.
   6  *
   7  * ***** BEGIN GPL LICENSE BLOCK *****
   8  *
   9  * This program is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU General Public License
  11  * as published by the Free Software Foundation; either version 2
  12  * of the License, or (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * along with this program; if not, write to the Free Software Foundation,
  20  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  21  *
  22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  23  * All rights reserved.
  24  *
  25  * The Original Code is: some of this file.
  26  *
  27  * Contributor(s): Jens Ole Wund (bjornmose), Campbell Barton (ideasman42)
  28  *
  29  * ***** END GPL LICENSE BLOCK *****
  30  */
  31
  32 /** \file blender/editors/sculpt_paint/paint_image.c
  33  *  \ingroup edsculpt
  34  */
  35
  36
  37 #include <float.h>
  38 #include <string.h>
  39 #include <stdio.h>
  40 #include <math.h>
  41
  42 #include "MEM_guardedalloc.h"
  43
  44 #ifdef WIN32
  45 #include "BLI_winstuff.h"
  46 #endif
  47 #include "BLI_math.h"
  48 #include "BLI_blenlib.h"
  49 #include "BLI_dynstr.h"
  50 #include "BLI_linklist.h"
  51 #include "BLI_memarena.h"
  52 #include "BLI_threads.h"
  53 #include "BLI_utildefines.h"
  54
  55 #include "PIL_time.h"
  56
  57 #include "IMB_imbuf.h"
  58 #include "IMB_imbuf_types.h"
  59
  60 #include "DNA_brush_types.h"
  61 #include "DNA_mesh_types.h"
  62 #include "DNA_meshdata_types.h"
  63 #include "DNA_node_types.h"
  64 #include "DNA_object_types.h"
  65 #include "DNA_scene_types.h"
  66 #include "DNA_texture_types.h"
  67
  68 #include "BKE_context.h"
  69 #include "BKE_depsgraph.h"
  70 #include "BKE_DerivedMesh.h"
  71 #include "BKE_idprop.h"
  72 #include "BKE_brush.h"
  73 #include "BKE_image.h"
  74 #include "BKE_library.h"
  75 #include "BKE_main.h"
  76 #include "BKE_mesh.h"
  77 #include "BKE_node.h"
  78 #include "BKE_object.h"
  79 #include "BKE_paint.h"
  80 #include "BKE_report.h"
  81
  82 #include "BIF_gl.h"
  83 #include "BIF_glutil.h"
  84
  85 #include "UI_view2d.h"
  86
  87 #include "ED_image.h"
  88 #include "ED_screen.h"
  89 #include "ED_sculpt.h"
  90 #include "ED_view3d.h"
  91
  92 #include "WM_api.h"
  93 #include "WM_types.h"
  94
  95 #include "RNA_access.h"
  96 #include "RNA_define.h"
  97 #include "RNA_enum_types.h"
  98
  99 #include "GPU_draw.h"
 100
 101 #include "paint_intern.h"
 102
 103 /* Defines and Structs */
 104
 105 #define IMAPAINT_CHAR_TO_FLOAT(c) ((c)/255.0f)
 106
 107 #define IMAPAINT_FLOAT_RGB_TO_CHAR(c, f) { (c)[0]=FTOCHAR((f)[0]); (c)[1]=FTOCHAR((f)[1]); (c)[2]=FTOCHAR((f)[2]); }
 108 #define IMAPAINT_FLOAT_RGBA_TO_CHAR(c, f) { (c)[0]=FTOCHAR((f)[0]); (c)[1]=FTOCHAR((f)[1]); (c)[2]=FTOCHAR((f)[2]); (c)[3]=FTOCHAR((f)[3]); }
 109
 110 #define IMAPAINT_CHAR_RGB_TO_FLOAT(f, c) { (f)[0]=IMAPAINT_CHAR_TO_FLOAT((c)[0]); (f)[1]=IMAPAINT_CHAR_TO_FLOAT((c)[1]); (f)[2]=IMAPAINT_CHAR_TO_FLOAT((c)[2]); }
 111 #define IMAPAINT_CHAR_RGBA_TO_FLOAT(f, c) { (f)[0]=IMAPAINT_CHAR_TO_FLOAT((c)[0]); (f)[1]=IMAPAINT_CHAR_TO_FLOAT((c)[1]); (f)[2]=IMAPAINT_CHAR_TO_FLOAT((c)[2]); (f)[3]=IMAPAINT_CHAR_TO_FLOAT((c)[3]); }
 112 #define IMAPAINT_FLOAT_RGB_COPY(a, b) VECCOPY(a, b)
 113
 114 #define IMAPAINT_TILE_BITS                      6
 115 #define IMAPAINT_TILE_SIZE                      (1 << IMAPAINT_TILE_BITS)
 116 #define IMAPAINT_TILE_NUMBER(size)      (((size)+IMAPAINT_TILE_SIZE-1) >> IMAPAINT_TILE_BITS)
 117
 118 static void imapaint_image_update(SpaceImage *sima, Image *image, ImBuf *ibuf, short texpaint);
 119
 120
 121 typedef struct ImagePaintState {
 122         SpaceImage *sima;
 123         View2D *v2d;
 124         Scene *scene;
 125         bScreen *screen;
 126
 127         Brush *brush;
 128         short tool, blend;
 129         Image *image;
 130         ImBuf *canvas;
 131         ImBuf *clonecanvas;
 132         short clonefreefloat;
 133         char *warnpackedfile;
 134         char *warnmultifile;
 135
 136         /* texture paint only */
 137         Object *ob;
 138         Mesh *me;
 139         int faceindex;
 140         float uv[2];
 141 } ImagePaintState;
 142
 143 typedef struct ImagePaintPartialRedraw {
 144         int x1, y1, x2, y2;
 145         int enabled;
 146 } ImagePaintPartialRedraw;
 147
 148 typedef struct ImagePaintRegion {
 149         int destx, desty;
 150         int srcx, srcy;
 151         int width, height;
 152 } ImagePaintRegion;
 153
 154 /* ProjectionPaint defines */
 155
 156 /* approx the number of buckets to have under the brush,
 157  * used with the brush size to set the ps->buckets_x and ps->buckets_y value.
 158  *
 159  * When 3 - a brush should have ~9 buckets under it at once
 160  * ...this helps for threading while painting as well as
 161  * avoiding initializing pixels that wont touch the brush */
 162 #define PROJ_BUCKET_BRUSH_DIV 4
 163
 164 #define PROJ_BUCKET_RECT_MIN 4
 165 #define PROJ_BUCKET_RECT_MAX 256
 166
 167 #define PROJ_BOUNDBOX_DIV 8
 168 #define PROJ_BOUNDBOX_SQUARED  (PROJ_BOUNDBOX_DIV * PROJ_BOUNDBOX_DIV)
 169
 170 //#define PROJ_DEBUG_PAINT 1
 171 //#define PROJ_DEBUG_NOSEAMBLEED 1
 172 //#define PROJ_DEBUG_PRINT_CLIP 1
 173 #define PROJ_DEBUG_WINCLIP 1
 174
 175 /* projectFaceSeamFlags options */
 176 //#define PROJ_FACE_IGNORE      (1<<0)  /* When the face is hidden, backfacing or occluded */
 177 //#define PROJ_FACE_INIT        (1<<1)  /* When we have initialized the faces data */
 178 #define PROJ_FACE_SEAM1 (1<<0)  /* If this face has a seam on any of its edges */
 179 #define PROJ_FACE_SEAM2 (1<<1)
 180 #define PROJ_FACE_SEAM3 (1<<2)
 181 #define PROJ_FACE_SEAM4 (1<<3)
 182
 183 #define PROJ_FACE_NOSEAM1       (1<<4)
 184 #define PROJ_FACE_NOSEAM2       (1<<5)
 185 #define PROJ_FACE_NOSEAM3       (1<<6)
 186 #define PROJ_FACE_NOSEAM4       (1<<7)
 187
 188 #define PROJ_SRC_VIEW           1
 189 #define PROJ_SRC_IMAGE_CAM      2
 190 #define PROJ_SRC_IMAGE_VIEW     3
 191
 192 #define PROJ_VIEW_DATA_ID "view_data"
 193 #define PROJ_VIEW_DATA_SIZE (4*4 + 4*4 + 3) /* viewmat + winmat + clipsta + clipend + is_ortho */
 194
 195
 196 /* a slightly scaled down face is used to get fake 3D location for edge pixels in the seams
 197  * as this number approaches  1.0f the likelihood increases of float precision errors where
 198  * it is occluded by an adjacent face */
 199 #define PROJ_FACE_SCALE_SEAM    0.99f
 200
 201 #define PROJ_BUCKET_NULL                0
 202 #define PROJ_BUCKET_INIT                (1<<0)
 203 // #define PROJ_BUCKET_CLONE_INIT       (1<<1)
 204
 205 /* used for testing doubles, if a point is on a line etc */
 206 #define PROJ_GEOM_TOLERANCE 0.00075f
 207
 208 /* vert flags */
 209 #define PROJ_VERT_CULL 1
 210
 211 #define PI_80_DEG ((M_PI_2 / 9) * 8)
 212
 213 /* This is mainly a convenience struct used so we can keep an array of images we use
 214  * Thir imbufs, etc, in 1 array, When using threads this array is copied for each thread
 215  * because 'partRedrawRect' and 'touch' values would not be thread safe */
 216 typedef struct ProjPaintImage {
 217         Image *ima;
 218         ImBuf *ibuf;
 219         ImagePaintPartialRedraw *partRedrawRect;
 220         void **undoRect; /* only used to build undo tiles after painting */
 221         int touch;
 222 } ProjPaintImage;
 223
 224 /* Main projection painting struct passed to all projection painting functions */
 225 typedef struct ProjPaintState {
 226         View3D *v3d;
 227         RegionView3D *rv3d;
 228         ARegion *ar;
 229         Scene *scene;
 230         int source; /* PROJ_SRC_**** */
 231
 232         Brush *brush;
 233         short tool, blend;
 234         Object *ob;
 235         /* end similarities with ImagePaintState */
 236
 237         DerivedMesh    *dm;
 238         int                     dm_totface;
 239         int                     dm_totvert;
 240         int                             dm_release;
 241
 242         MVert              *dm_mvert;
 243         MFace              *dm_mface;
 244         MTFace             *dm_mtface;
 245         MTFace             *dm_mtface_clone;    /* other UV layer, use for cloning between layers */
 246         MTFace             *dm_mtface_stencil;
 247
 248         /* projection painting only */
 249         MemArena *arena_mt[BLENDER_MAX_THREADS];/* for multithreading, the first item is sometimes used for non threaded cases too */
 250         LinkNode **bucketRect;                          /* screen sized 2D array, each pixel has a linked list of ProjPixel's */
 251         LinkNode **bucketFaces;                         /* bucketRect aligned array linkList of faces overlapping each bucket */
 252         unsigned char *bucketFlags;                                     /* store if the bucks have been initialized  */
 253 #ifndef PROJ_DEBUG_NOSEAMBLEED
 254         char *faceSeamFlags;                            /* store info about faces, if they are initialized etc*/
 255         float (*faceSeamUVs)[4][2];                     /* expanded UVs for faces to use as seams */
 256         LinkNode **vertFaces;                           /* Only needed for when seam_bleed_px is enabled, use to find UV seams */
 257 #endif
 258         char *vertFlags;                                        /* store options per vert, now only store if the vert is pointing away from the view */
 259         int buckets_x;                                          /* The size of the bucket grid, the grid span's screenMin/screenMax so you can paint outsize the screen or with 2 brushes at once */
 260         int buckets_y;
 261
 262         ProjPaintImage *projImages;
 263
 264         int image_tot;                          /* size of projectImages array */
 265
 266         float (*screenCoords)[4];       /* verts projected into floating point screen space */
 267
 268         float screenMin[2];                     /* 2D bounds for mesh verts on the screen's plane (screenspace) */
 269         float screenMax[2];
 270         float screen_width;                     /* Calculated from screenMin & screenMax */
 271         float screen_height;
 272         int winx, winy;                         /* from the carea or from the projection render */
 273
 274         /* options for projection painting */
 275         int do_layer_clone;
 276         int do_layer_stencil;
 277         int do_layer_stencil_inv;
 278
 279         short do_occlude;                       /* Use raytraced occlusion? - ortherwise will paint right through to the back*/
 280         short do_backfacecull;  /* ignore faces with normals pointing away, skips a lot of raycasts if your normals are correctly flipped */
 281         short do_mask_normal;                   /* mask out pixels based on their normals */
 282         float normal_angle;                             /* what angle to mask at*/
 283         float normal_angle_inner;
 284         float normal_angle_range;               /* difference between normal_angle and normal_angle_inner, for easy access */
 285
 286         short is_ortho;
 287         short is_airbrush;                                      /* only to avoid using (ps.brush->flag & BRUSH_AIRBRUSH) */
 288         short is_texbrush;                                      /* only to avoid running  */
 289 #ifndef PROJ_DEBUG_NOSEAMBLEED
 290         float seam_bleed_px;
 291 #endif
 292         /* clone vars */
 293         float cloneOffset[2];
 294
 295         float projectMat[4][4];         /* Projection matrix, use for getting screen coords */
 296         float viewDir[3];                       /* View vector, use for do_backfacecull and for ray casting with an ortho viewport  */
 297         float viewPos[3];                       /* View location in object relative 3D space, so can compare to verts  */
 298         float clipsta, clipend;
 299
 300         /* reproject vars */
 301         Image *reproject_image;
 302         ImBuf *reproject_ibuf;
 303
 304
 305         /* threads */
 306         int thread_tot;
 307         int bucketMin[2];
 308         int bucketMax[2];
 309         int context_bucket_x, context_bucket_y; /* must lock threads while accessing these */
 310 } ProjPaintState;
 311
 312 typedef union pixelPointer
 313 {
 314         float *f_pt;                    /* float buffer */
 315         unsigned int *uint_pt; /* 2 ways to access a char buffer */
 316         unsigned char *ch_pt;
 317 } PixelPointer;
 318
 319 typedef union pixelStore
 320 {
 321         unsigned char ch[4];
 322         unsigned int uint;
 323         float f[4];
 324 } PixelStore;
 325
 326 typedef struct ProjPixel {
 327         float projCoSS[2]; /* the floating point screen projection of this pixel */
 328
 329         /* Only used when the airbrush is disabled.
 330          * Store the max mask value to avoid painting over an area with a lower opacity
 331          * with an advantage that we can avoid touching the pixel at all, if the
 332          * new mask value is lower then mask_max */
 333         unsigned short mask_max;
 334
 335         /* for various reasons we may want to mask out painting onto this pixel */
 336         unsigned short mask;
 337
 338         short x_px, y_px;
 339
 340         PixelStore origColor;
 341         PixelStore newColor;
 342         PixelPointer pixel;
 343
 344         short image_index; /* if anyone wants to paint onto more then 32768 images they can bite me */
 345         unsigned char bb_cell_index;
 346 } ProjPixel;
 347
 348 typedef struct ProjPixelClone {
 349         struct ProjPixel __pp;
 350         PixelStore clonepx;
 351 } ProjPixelClone;
 352
 353 /* Finish projection painting structs */
 354
 355 typedef struct UndoImageTile {
 356         struct UndoImageTile *next, *prev;
 357
 358         char idname[MAX_ID_NAME];       /* name instead of pointer*/
 359
 360         void *rect;
 361         int x, y;
 362 } UndoImageTile;
 363
 364 static ImagePaintPartialRedraw imapaintpartial = {0, 0, 0, 0, 0};
 365
 366 /* UNDO */
 367
 368 static void undo_copy_tile(UndoImageTile *tile, ImBuf *tmpibuf, ImBuf *ibuf, int restore)
 369 {
 370         /* copy or swap contents of tile->rect and region in ibuf->rect */
 371         IMB_rectcpy(tmpibuf, ibuf, 0, 0, tile->x*IMAPAINT_TILE_SIZE,
 372                 tile->y*IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE);
 373
 374         if(ibuf->rect_float) {
 375                 SWAP(void*, tmpibuf->rect_float, tile->rect);
 376         } else {
 377                 SWAP(void*, tmpibuf->rect, tile->rect);
 378         }
 379
 380         if(restore)
 381                 IMB_rectcpy(ibuf, tmpibuf, tile->x*IMAPAINT_TILE_SIZE,
 382                         tile->y*IMAPAINT_TILE_SIZE, 0, 0, IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE);
 383 }
 384
 385 static void *image_undo_push_tile(Image *ima, ImBuf *ibuf, ImBuf **tmpibuf, int x_tile, int y_tile)
 386 {
 387         ListBase *lb= undo_paint_push_get_list(UNDO_PAINT_IMAGE);
 388         UndoImageTile *tile;
 389         int allocsize;
 390
 391         for(tile=lb->first; tile; tile=tile->next)
 392                 if(tile->x == x_tile && tile->y == y_tile && strcmp(tile->idname, ima->id.name)==0)
 393                         return tile->rect;
 394
 395         if (*tmpibuf==NULL)
 396                 *tmpibuf = IMB_allocImBuf(IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, 32, IB_rectfloat|IB_rect);
 397
 398         tile= MEM_callocN(sizeof(UndoImageTile), "UndoImageTile");
 399         strcpy(tile->idname, ima->id.name);
 400         tile->x= x_tile;
 401         tile->y= y_tile;
 402
 403         allocsize= IMAPAINT_TILE_SIZE*IMAPAINT_TILE_SIZE*4;
 404         allocsize *= (ibuf->rect_float)? sizeof(float): sizeof(char);
 405         tile->rect= MEM_mapallocN(allocsize, "UndeImageTile.rect");
 406
 407         undo_copy_tile(tile, *tmpibuf, ibuf, 0);
 408         undo_paint_push_count_alloc(UNDO_PAINT_IMAGE, allocsize);
 409
 410         BLI_addtail(lb, tile);
 411
 412         return tile->rect;
 413 }
 414
 415 static void image_undo_restore(bContext *C, ListBase *lb)
 416 {
 417         Main *bmain= CTX_data_main(C);
 418         Image *ima = NULL;
 419         ImBuf *ibuf, *tmpibuf;
 420         UndoImageTile *tile;
 421
 422         tmpibuf= IMB_allocImBuf(IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, 32,
 423                                                         IB_rectfloat|IB_rect);
 424
 425         for(tile=lb->first; tile; tile=tile->next) {
 426                 /* find image based on name, pointer becomes invalid with global undo */
 427                 if(ima && strcmp(tile->idname, ima->id.name)==0);
 428                 else {
 429                         for(ima=bmain->image.first; ima; ima=ima->id.next)
 430                                 if(strcmp(tile->idname, ima->id.name)==0)
 431                                         break;
 432                 }
 433
 434                 ibuf= BKE_image_get_ibuf(ima, NULL);
 435
 436                 if (!ima || !ibuf || !(ibuf->rect || ibuf->rect_float))
 437                         continue;
 438
 439                 undo_copy_tile(tile, tmpibuf, ibuf, 1);
 440
 441                 GPU_free_image(ima); /* force OpenGL reload */
 442                 if(ibuf->rect_float)
 443                         ibuf->userflags |= IB_RECT_INVALID; /* force recreate of char rect */
 444                 if(ibuf->mipmap[0])
 445                         ibuf->userflags |= IB_MIPMAP_INVALID; /* force mipmap recreatiom */
 446
 447         }
 448
 449         IMB_freeImBuf(tmpibuf);
 450 }
 451
 452 static void image_undo_free(ListBase *lb)
 453 {
 454         UndoImageTile *tile;
 455
 456         for(tile=lb->first; tile; tile=tile->next)
 457                 MEM_freeN(tile->rect);
 458 }
 459
 460 /* fast projection bucket array lookup, use the safe version for bound checking  */
 461 static int project_bucket_offset(const ProjPaintState *ps, const float projCoSS[2])
 462 {
 463         /* If we were not dealing with screenspace 2D coords we could simple do...
 464          * ps->bucketRect[x + (y*ps->buckets_y)] */
 465
 466         /* please explain?
 467          * projCoSS[0] - ps->screenMin[0]       : zero origin
 468          * ... / ps->screen_width                               : range from 0.0 to 1.0
 469          * ... * ps->buckets_x          : use as a bucket index
 470          *
 471          * Second multiplication does similar but for vertical offset
 472          */
 473         return  (       (int)(((projCoSS[0] - ps->screenMin[0]) / ps->screen_width)  * ps->buckets_x)) +
 474                 (       (       (int)(((projCoSS[1] - ps->screenMin[1])  / ps->screen_height) * ps->buckets_y)) * ps->buckets_x);
 475 }
 476
 477 static int project_bucket_offset_safe(const ProjPaintState *ps, const float projCoSS[2])
 478 {
 479         int bucket_index = project_bucket_offset(ps, projCoSS);
 480
 481         if (bucket_index < 0 || bucket_index >= ps->buckets_x*ps->buckets_y) {
 482                 return -1;
 483         }
 484         else {
 485                 return bucket_index;
 486         }
 487 }
 488
 489 /* still use 2D X,Y space but this works for verts transformed by a perspective matrix, using their 4th component as a weight */
 490 static void barycentric_weights_v2_persp(float v1[4], float v2[4], float v3[4], float co[2], float w[3])
 491 {
 492         float wtot_inv, wtot;
 493
 494         w[0] = area_tri_signed_v2(v2, v3, co) / v1[3];
 495         w[1] = area_tri_signed_v2(v3, v1, co) / v2[3];
 496         w[2] = area_tri_signed_v2(v1, v2, co) / v3[3];
 497         wtot = w[0]+w[1]+w[2];
 498
 499         if (wtot != 0.0f) {
 500                 wtot_inv = 1.0f/wtot;
 501
 502                 w[0] = w[0]*wtot_inv;
 503                 w[1] = w[1]*wtot_inv;
 504                 w[2] = w[2]*wtot_inv;
 505         }
 506         else /* dummy values for zero area face */
 507                 w[0] = w[1] = w[2] = 1.0f/3.0f;
 508 }
 509
 510 static float VecZDepthOrtho(float pt[2], float v1[3], float v2[3], float v3[3], float w[3])
 511 {
 512         barycentric_weights_v2(v1, v2, v3, pt, w);
 513         return (v1[2]*w[0]) + (v2[2]*w[1]) + (v3[2]*w[2]);
 514 }
 515
 516 static float VecZDepthPersp(float pt[2], float v1[4], float v2[4], float v3[4], float w[3])
 517 {
 518         float wtot_inv, wtot;
 519         float w_tmp[3];
 520
 521         barycentric_weights_v2_persp(v1, v2, v3, pt, w);
 522         /* for the depth we need the weights to match what
 523          * barycentric_weights_v2 would return, in this case its easiest just to
 524          * undo the 4th axis division and make it unit-sum
 525          *
 526          * don't call barycentric_weights_v2() becaue our callers expect 'w'
 527          * to be weighted from the perspective */
 528         w_tmp[0]= w[0] * v1[3];
 529         w_tmp[1]= w[1] * v2[3];
 530         w_tmp[2]= w[2] * v3[3];
 531
 532         wtot = w_tmp[0]+w_tmp[1]+w_tmp[2];
 533
 534         if (wtot != 0.0f) {
 535                 wtot_inv = 1.0f/wtot;
 536
 537                 w_tmp[0] = w_tmp[0]*wtot_inv;
 538                 w_tmp[1] = w_tmp[1]*wtot_inv;
 539                 w_tmp[2] = w_tmp[2]*wtot_inv;
 540         }
 541         else /* dummy values for zero area face */
 542                 w_tmp[0] = w_tmp[1] = w_tmp[2] = 1.0f/3.0f;
 543         /* done mimicing barycentric_weights_v2() */
 544
 545         return (v1[2]*w_tmp[0]) + (v2[2]*w_tmp[1]) + (v3[2]*w_tmp[2]);
 546 }
 547
 548
 549 /* Return the top-most face index that the screen space coord 'pt' touches (or -1) */
 550 static int project_paint_PickFace(const ProjPaintState *ps, float pt[2], float w[3], int *side)
 551 {
 552         LinkNode *node;
 553         float w_tmp[3];
 554         float *v1, *v2, *v3, *v4;
 555         int bucket_index;
 556         int face_index;
 557         int best_side = -1;
 558         int best_face_index = -1;
 559         float z_depth_best = FLT_MAX, z_depth;
 560         MFace *mf;
 561
 562         bucket_index = project_bucket_offset_safe(ps, pt);
 563         if (bucket_index==-1)
 564                 return -1;
 565
 566
 567
 568         /* we could return 0 for 1 face buckets, as long as this function assumes
 569          * that the point its testing is only every originated from an existing face */
 570
 571         for (node= ps->bucketFaces[bucket_index]; node; node= node->next) {
 572                 face_index = GET_INT_FROM_POINTER(node->link);
 573                 mf= ps->dm_mface + face_index;
 574
 575                 v1= ps->screenCoords[mf->v1];
 576                 v2= ps->screenCoords[mf->v2];
 577                 v3= ps->screenCoords[mf->v3];
 578
 579                 if (isect_point_tri_v2(pt, v1, v2, v3)) {
 580                         if (ps->is_ortho)       z_depth= VecZDepthOrtho(pt, v1, v2, v3, w_tmp);
 581                         else                            z_depth= VecZDepthPersp(pt, v1, v2, v3, w_tmp);
 582
 583                         if (z_depth < z_depth_best) {
 584                                 best_face_index = face_index;
 585                                 best_side = 0;
 586                                 z_depth_best = z_depth;
 587                                 VECCOPY(w, w_tmp);
 588                         }
 589                 }
 590                 else if (mf->v4) {
 591                         v4= ps->screenCoords[mf->v4];
 592
 593                         if (isect_point_tri_v2(pt, v1, v3, v4)) {
 594                                 if (ps->is_ortho)       z_depth= VecZDepthOrtho(pt, v1, v3, v4, w_tmp);
 595                                 else                            z_depth= VecZDepthPersp(pt, v1, v3, v4, w_tmp);
 596
 597                                 if (z_depth < z_depth_best) {
 598                                         best_face_index = face_index;
 599                                         best_side= 1;
 600                                         z_depth_best = z_depth;
 601                                         VECCOPY(w, w_tmp);
 602                                 }
 603                         }
 604                 }
 605         }
 606
 607         *side = best_side;
 608         return best_face_index; /* will be -1 or a valid face */
 609 }
 610
 611 /* Converts a uv coord into a pixel location wrapping if the uv is outside 0-1 range */
 612 static void uvco_to_wrapped_pxco(float uv[2], int ibuf_x, int ibuf_y, float *x, float *y)
 613 {
 614         /* use */
 615         *x = (float)fmodf(uv[0], 1.0f);
 616         *y = (float)fmodf(uv[1], 1.0f);
 617
 618         if (*x < 0.0f) *x += 1.0f;
 619         if (*y < 0.0f) *y += 1.0f;
 620
 621         *x = *x * ibuf_x - 0.5f;
 622         *y = *y * ibuf_y - 0.5f;
 623 }
 624
 625 /* Set the top-most face color that the screen space coord 'pt' touches (or return 0 if none touch) */
 626 static int project_paint_PickColor(const ProjPaintState *ps, float pt[2], float *rgba_fp, unsigned char *rgba, const int interp)
 627 {
 628         float w[3], uv[2];
 629         int side;
 630         int face_index;
 631         MTFace *tf;
 632         ImBuf *ibuf;
 633         int xi, yi;
 634
 635
 636         face_index = project_paint_PickFace(ps, pt, w, &side);
 637
 638         if (face_index == -1)
 639                 return 0;
 640
 641         tf = ps->dm_mtface + face_index;
 642
 643         if (side == 0) {
 644                 interp_v2_v2v2v2(uv, tf->uv[0], tf->uv[1], tf->uv[2], w);
 645         }
 646         else { /* QUAD */
 647                 interp_v2_v2v2v2(uv, tf->uv[0], tf->uv[2], tf->uv[3], w);
 648         }
 649
 650         ibuf = tf->tpage->ibufs.first; /* we must have got the imbuf before getting here */
 651         if (!ibuf) return 0;
 652
 653         if (interp) {
 654                 float x, y;
 655                 uvco_to_wrapped_pxco(uv, ibuf->x, ibuf->y, &x, &y);
 656
 657                 if (ibuf->rect_float) {
 658                         if (rgba_fp) {
 659                                 bilinear_interpolation_color_wrap(ibuf, NULL, rgba_fp, x, y);
 660                         }
 661                         else {
 662                                 float rgba_tmp_f[4];
 663                                 bilinear_interpolation_color_wrap(ibuf, NULL, rgba_tmp_f, x, y);
 664                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(rgba, rgba_tmp_f);
 665                         }
 666                 }
 667                 else {
 668                         if (rgba) {
 669                                 bilinear_interpolation_color_wrap(ibuf, rgba, NULL, x, y);
 670                         }
 671                         else {
 672                                 unsigned char rgba_tmp[4];
 673                                 bilinear_interpolation_color_wrap(ibuf, rgba_tmp, NULL, x, y);
 674                                 IMAPAINT_CHAR_RGBA_TO_FLOAT(rgba_fp, rgba_tmp);
 675                         }
 676                 }
 677         }
 678         else {
 679                 //xi = (int)((uv[0]*ibuf->x) + 0.5f);
 680                 //yi = (int)((uv[1]*ibuf->y) + 0.5f);
 681                 //if (xi<0 || xi>=ibuf->x  ||  yi<0 || yi>=ibuf->y) return 0;
 682
 683                 /* wrap */
 684                 xi = ((int)(uv[0]*ibuf->x)) % ibuf->x;
 685                 if (xi<0) xi += ibuf->x;
 686                 yi = ((int)(uv[1]*ibuf->y)) % ibuf->y;
 687                 if (yi<0) yi += ibuf->y;
 688
 689
 690                 if (rgba) {
 691                         if (ibuf->rect_float) {
 692                                 float *rgba_tmp_fp = ibuf->rect_float + (xi + yi * ibuf->x * 4);
 693                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(rgba, rgba_tmp_fp);
 694                         }
 695                         else {
 696                                 *((unsigned int *)rgba) = *(unsigned int *)(((char *)ibuf->rect) + ((xi + yi * ibuf->x) * 4));
 697                         }
 698                 }
 699
 700                 if (rgba_fp) {
 701                         if (ibuf->rect_float) {
 702                                 QUATCOPY(rgba_fp, ((float *)ibuf->rect_float + ((xi + yi * ibuf->x) * 4)));
 703                         }
 704                         else {
 705                                 char *tmp_ch= ((char *)ibuf->rect) + ((xi + yi * ibuf->x) * 4);
 706                                 IMAPAINT_CHAR_RGBA_TO_FLOAT(rgba_fp, tmp_ch);
 707                         }
 708                 }
 709         }
 710         return 1;
 711 }
 712
 713 /* Check if 'pt' is infront of the 3 verts on the Z axis (used for screenspace occlusuion test)
 714  * return...
 715  *  0   : no occlusion
 716  * -1   : no occlusion but 2D intersection is true (avoid testing the other half of a quad)
 717  *  1   : occluded
 718         2       : occluded with w[3] weights set (need to know in some cases) */
 719
 720 static int project_paint_occlude_ptv(float pt[3], float v1[4], float v2[4], float v3[4], float w[3], int is_ortho)
 721 {
 722         /* if all are behind us, return false */
 723         if(v1[2] > pt[2] && v2[2] > pt[2] && v3[2] > pt[2])
 724                 return 0;
 725
 726         /* do a 2D point in try intersection */
 727         if (!isect_point_tri_v2(pt, v1, v2, v3))
 728                 return 0; /* we know there is  */
 729
 730
 731         /* From here on we know there IS an intersection */
 732         /* if ALL of the verts are infront of us then we know it intersects ? */
 733         if(v1[2] < pt[2] && v2[2] < pt[2] && v3[2] < pt[2]) {
 734                 return 1;
 735         }
 736         else {
 737                 /* we intersect? - find the exact depth at the point of intersection */
 738                 /* Is this point is occluded by another face? */
 739                 if (is_ortho) {
 740                         if (VecZDepthOrtho(pt, v1, v2, v3, w) < pt[2]) return 2;
 741                 }
 742                 else {
 743                         if (VecZDepthPersp(pt, v1, v2, v3, w) < pt[2]) return 2;
 744                 }
 745         }
 746         return -1;
 747 }
 748
 749
 750 static int project_paint_occlude_ptv_clip(
 751                 const ProjPaintState *ps, const MFace *mf,
 752                 float pt[3], float v1[4], float v2[4], float v3[4],
 753                 const int side )
 754 {
 755         float w[3], wco[3];
 756         int ret = project_paint_occlude_ptv(pt, v1, v2, v3, w, ps->is_ortho);
 757
 758         if (ret <= 0)
 759                 return ret;
 760
 761         if (ret==1) { /* weights not calculated */
 762                 if (ps->is_ortho)       barycentric_weights_v2(v1, v2, v3, pt, w);
 763                 else                            barycentric_weights_v2_persp(v1, v2, v3, pt, w);
 764         }
 765
 766         /* Test if we're in the clipped area, */
 767         if (side)       interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v3].co, ps->dm_mvert[mf->v4].co, w);
 768         else            interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, w);
 769
 770         if(!ED_view3d_test_clipping(ps->rv3d, wco, 1)) {
 771                 return 1;
 772         }
 773
 774         return -1;
 775 }
 776
 777
 778 /* Check if a screenspace location is occluded by any other faces
 779  * check, pixelScreenCo must be in screenspace, its Z-Depth only needs to be used for comparison
 780  * and dosn't need to be correct in relation to X and Y coords (this is the case in perspective view) */
 781 static int project_bucket_point_occluded(const ProjPaintState *ps, LinkNode *bucketFace, const int orig_face, float pixelScreenCo[4])
 782 {
 783         MFace *mf;
 784         int face_index;
 785         int isect_ret;
 786         float w[3]; /* not needed when clipping */
 787         const short do_clip= ps->rv3d ? ps->rv3d->rflag & RV3D_CLIPPING : 0;
 788
 789         /* we could return 0 for 1 face buckets, as long as this function assumes
 790          * that the point its testing is only every originated from an existing face */
 791
 792         for (; bucketFace; bucketFace = bucketFace->next) {
 793                 face_index = GET_INT_FROM_POINTER(bucketFace->link);
 794
 795                 if (orig_face != face_index) {
 796                         mf = ps->dm_mface + face_index;
 797                         if(do_clip)
 798                                 isect_ret = project_paint_occlude_ptv_clip(ps, mf, pixelScreenCo, ps->screenCoords[mf->v1], ps->screenCoords[mf->v2], ps->screenCoords[mf->v3], 0);
 799                         else
 800                                 isect_ret = project_paint_occlude_ptv(pixelScreenCo, ps->screenCoords[mf->v1], ps->screenCoords[mf->v2], ps->screenCoords[mf->v3], w, ps->is_ortho);
 801
 802                         /* Note, if isect_ret==-1 then we dont want to test the other side of the quad */
 803                         if (isect_ret==0 && mf->v4) {
 804                                 if(do_clip)
 805                                         isect_ret = project_paint_occlude_ptv_clip(ps, mf, pixelScreenCo, ps->screenCoords[mf->v1], ps->screenCoords[mf->v3], ps->screenCoords[mf->v4], 1);
 806                                 else
 807                                         isect_ret = project_paint_occlude_ptv(pixelScreenCo, ps->screenCoords[mf->v1], ps->screenCoords[mf->v3], ps->screenCoords[mf->v4], w, ps->is_ortho);
 808                         }
 809                         if (isect_ret>=1) {
 810                                 /* TODO - we may want to cache the first hit,
 811                                  * it is not possible to swap the face order in the list anymore */
 812                                 return 1;
 813                         }
 814                 }
 815         }
 816         return 0;
 817 }
 818
 819 /* basic line intersection, could move to math_geom.c, 2 points with a horiz line
 820  * 1 for an intersection, 2 if the first point is aligned, 3 if the second point is aligned */
 821 #define ISECT_TRUE 1
 822 #define ISECT_TRUE_P1 2
 823 #define ISECT_TRUE_P2 3
 824 static int line_isect_y(const float p1[2], const float p2[2], const float y_level, float *x_isect)
 825 {
 826         float y_diff;
 827
 828         if (y_level==p1[1]) { /* are we touching the first point? - no interpolation needed */
 829                 *x_isect = p1[0];
 830                 return ISECT_TRUE_P1;
 831         }
 832         if (y_level==p2[1]) { /* are we touching the second point? - no interpolation needed */
 833                 *x_isect = p2[0];
 834                 return ISECT_TRUE_P2;
 835         }
 836
 837         y_diff= fabsf(p1[1]-p2[1]); /* yuck, horizontal line, we cant do much here */
 838
 839         if (y_diff < 0.000001f) {
 840                 *x_isect = (p1[0]+p2[0]) * 0.5f;
 841                 return ISECT_TRUE;
 842         }
 843
 844         if (p1[1] > y_level && p2[1] < y_level) {
 845                 *x_isect = (p2[0]*(p1[1]-y_level) + p1[0]*(y_level-p2[1])) / y_diff;  /*(p1[1]-p2[1]);*/
 846                 return ISECT_TRUE;
 847         }
 848         else if (p1[1] < y_level && p2[1] > y_level) {
 849                 *x_isect = (p2[0]*(y_level-p1[1]) + p1[0]*(p2[1]-y_level)) / y_diff;  /*(p2[1]-p1[1]);*/
 850                 return ISECT_TRUE;
 851         }
 852         else {
 853                 return 0;
 854         }
 855 }
 856
 857 static int line_isect_x(const float p1[2], const float p2[2], const float x_level, float *y_isect)
 858 {
 859         float x_diff;
 860
 861         if (x_level==p1[0]) { /* are we touching the first point? - no interpolation needed */
 862                 *y_isect = p1[1];
 863                 return ISECT_TRUE_P1;
 864         }
 865         if (x_level==p2[0]) { /* are we touching the second point? - no interpolation needed */
 866                 *y_isect = p2[1];
 867                 return ISECT_TRUE_P2;
 868         }
 869
 870         x_diff= fabsf(p1[0]-p2[0]); /* yuck, horizontal line, we cant do much here */
 871
 872         if (x_diff < 0.000001f) { /* yuck, vertical line, we cant do much here */
 873                 *y_isect = (p1[0]+p2[0]) * 0.5f;
 874                 return ISECT_TRUE;
 875         }
 876
 877         if (p1[0] > x_level && p2[0] < x_level) {
 878                 *y_isect = (p2[1]*(p1[0]-x_level) + p1[1]*(x_level-p2[0])) / x_diff; /*(p1[0]-p2[0]);*/
 879                 return ISECT_TRUE;
 880         }
 881         else if (p1[0] < x_level && p2[0] > x_level) {
 882                 *y_isect = (p2[1]*(x_level-p1[0]) + p1[1]*(p2[0]-x_level)) / x_diff; /*(p2[0]-p1[0]);*/
 883                 return ISECT_TRUE;
 884         }
 885         else {
 886                 return 0;
 887         }
 888 }
 889
 890 /* simple func use for comparing UV locations to check if there are seams.
 891  * Its possible this gives incorrect results, when the UVs for 1 face go into the next
 892  * tile, but do not do this for the adjacent face, it could return a false positive.
 893  * This is so unlikely that Id not worry about it. */
 894 #ifndef PROJ_DEBUG_NOSEAMBLEED
 895 static int cmp_uv(const float vec2a[2], const float vec2b[2])
 896 {
 897         /* if the UV's are not between 0.0 and 1.0 */
 898         float xa = (float)fmodf(vec2a[0], 1.0f);
 899         float ya = (float)fmodf(vec2a[1], 1.0f);
 900
 901         float xb = (float)fmodf(vec2b[0], 1.0f);
 902         float yb = (float)fmodf(vec2b[1], 1.0f);
 903
 904         if (xa < 0.0f) xa += 1.0f;
 905         if (ya < 0.0f) ya += 1.0f;
 906
 907         if (xb < 0.0f) xb += 1.0f;
 908         if (yb < 0.0f) yb += 1.0f;
 909
 910         return ((fabsf(xa-xb) < PROJ_GEOM_TOLERANCE) && (fabsf(ya-yb) < PROJ_GEOM_TOLERANCE)) ? 1:0;
 911 }
 912 #endif
 913
 914 /* set min_px and max_px to the image space bounds of the UV coords
 915  * return zero if there is no area in the returned rectangle */
 916 #ifndef PROJ_DEBUG_NOSEAMBLEED
 917 static int pixel_bounds_uv(
 918                 const float uv1[2], const float uv2[2], const float uv3[2], const float uv4[2],
 919                 rcti *bounds_px,
 920                 const int ibuf_x, const int ibuf_y,
 921                 int is_quad
 922 ) {
 923         float min_uv[2], max_uv[2]; /* UV bounds */
 924
 925         INIT_MINMAX2(min_uv, max_uv);
 926
 927         DO_MINMAX2(uv1, min_uv, max_uv);
 928         DO_MINMAX2(uv2, min_uv, max_uv);
 929         DO_MINMAX2(uv3, min_uv, max_uv);
 930         if (is_quad)
 931                 DO_MINMAX2(uv4, min_uv, max_uv);
 932
 933         bounds_px->xmin = (int)(ibuf_x * min_uv[0]);
 934         bounds_px->ymin = (int)(ibuf_y * min_uv[1]);
 935
 936         bounds_px->xmax = (int)(ibuf_x * max_uv[0]) +1;
 937         bounds_px->ymax = (int)(ibuf_y * max_uv[1]) +1;
 938
 939         /*printf("%d %d %d %d \n", min_px[0], min_px[1], max_px[0], max_px[1]);*/
 940
 941         /* face uses no UV area when quantized to pixels? */
 942         return (bounds_px->xmin == bounds_px->xmax || bounds_px->ymin == bounds_px->ymax) ? 0 : 1;
 943 }
 944 #endif
 945
 946 static int pixel_bounds_array(float (* uv)[2], rcti *bounds_px, const int ibuf_x, const int ibuf_y, int tot)
 947 {
 948         float min_uv[2], max_uv[2]; /* UV bounds */
 949
 950         if (tot==0) {
 951                 return 0;
 952         }
 953
 954         INIT_MINMAX2(min_uv, max_uv);
 955
 956         while (tot--) {
 957                 DO_MINMAX2((*uv), min_uv, max_uv);
 958                 uv++;
 959         }
 960
 961         bounds_px->xmin = (int)(ibuf_x * min_uv[0]);
 962         bounds_px->ymin = (int)(ibuf_y * min_uv[1]);
 963
 964         bounds_px->xmax = (int)(ibuf_x * max_uv[0]) +1;
 965         bounds_px->ymax = (int)(ibuf_y * max_uv[1]) +1;
 966
 967         /*printf("%d %d %d %d \n", min_px[0], min_px[1], max_px[0], max_px[1]);*/
 968
 969         /* face uses no UV area when quantized to pixels? */
 970         return (bounds_px->xmin == bounds_px->xmax || bounds_px->ymin == bounds_px->ymax) ? 0 : 1;
 971 }
 972
 973 #ifndef PROJ_DEBUG_NOSEAMBLEED
 974
 975 /* This function returns 1 if this face has a seam along the 2 face-vert indices
 976  * 'orig_i1_fidx' and 'orig_i2_fidx' */
 977 static int check_seam(const ProjPaintState *ps, const int orig_face, const int orig_i1_fidx, const int orig_i2_fidx, int *other_face, int *orig_fidx)
 978 {
 979         LinkNode *node;
 980         int face_index;
 981         unsigned int i1, i2;
 982         int i1_fidx = -1, i2_fidx = -1; /* index in face */
 983         MFace *mf;
 984         MTFace *tf;
 985         const MFace *orig_mf = ps->dm_mface + orig_face;
 986         const MTFace *orig_tf = ps->dm_mtface + orig_face;
 987
 988         /* vert indices from face vert order indices */
 989         i1 = (*(&orig_mf->v1 + orig_i1_fidx));
 990         i2 = (*(&orig_mf->v1 + orig_i2_fidx));
 991
 992         for (node = ps->vertFaces[i1]; node; node = node->next) {
 993                 face_index = GET_INT_FROM_POINTER(node->link);
 994
 995                 if (face_index != orig_face) {
 996                         mf = ps->dm_mface + face_index;
 997                         /* could check if the 2 faces images match here,
 998                          * but then there wouldn't be a way to return the opposite face's info */
 999
1000
1001                         /* We need to know the order of the verts in the adjacent face
1002                          * set the i1_fidx and i2_fidx to (0,1,2,3) */
1003                         if              (mf->v1==i1)                    i1_fidx = 0;
1004                         else if (mf->v2==i1)                    i1_fidx = 1;
1005                         else if (mf->v3==i1)                    i1_fidx = 2;
1006                         else if (mf->v4 && mf->v4==i1)  i1_fidx = 3;
1007
1008                         if              (mf->v1==i2)                    i2_fidx = 0;
1009                         else if (mf->v2==i2)                    i2_fidx = 1;
1010                         else if (mf->v3==i2)                    i2_fidx = 2;
1011                         else if (mf->v4 && mf->v4==i2)  i2_fidx = 3;
1012
1013                         /* Only need to check if 'i2_fidx' is valid because we know i1_fidx is the same vert on both faces */
1014                         if (i2_fidx != -1) {
1015                                 /* This IS an adjacent face!, now lets check if the UVs are ok */
1016                                 tf = ps->dm_mtface + face_index;
1017
1018                                 /* set up the other face */
1019                                 *other_face = face_index;
1020                                 *orig_fidx = (i1_fidx < i2_fidx) ? i1_fidx : i2_fidx;
1021
1022                                 /* first test if they have the same image */
1023                                 if (    (orig_tf->tpage == tf->tpage) &&
1024                                                 cmp_uv(orig_tf->uv[orig_i1_fidx], tf->uv[i1_fidx]) &&
1025                                                 cmp_uv(orig_tf->uv[orig_i2_fidx], tf->uv[i2_fidx]) )
1026                                 {
1027                                         // printf("SEAM (NONE)\n");
1028                                         return 0;
1029
1030                                 }
1031                                 else {
1032                                         // printf("SEAM (UV GAP)\n");
1033                                         return 1;
1034                                 }
1035                         }
1036                 }
1037         }
1038         // printf("SEAM (NO FACE)\n");
1039         *other_face = -1;
1040         return 1;
1041 }
1042
1043 /* Calculate outset UV's, this is not the same as simply scaling the UVs,
1044  * since the outset coords are a margin that keep an even distance from the original UV's,
1045  * note that the image aspect is taken into account */
1046 static void uv_image_outset(float (*orig_uv)[2], float (*outset_uv)[2], const float scaler, const int ibuf_x, const int ibuf_y, const int is_quad)
1047 {
1048         float a1, a2, a3, a4=0.0f;
1049         float puv[4][2]; /* pixelspace uv's */
1050         float no1[2], no2[2], no3[2], no4[2]; /* normals */
1051         float dir1[2], dir2[2], dir3[2], dir4[2];
1052         float ibuf_inv[2];
1053
1054         ibuf_inv[0]= 1.0f / (float)ibuf_x;
1055         ibuf_inv[1]= 1.0f / (float)ibuf_y;
1056
1057         /* make UV's in pixel space so we can */
1058         puv[0][0] = orig_uv[0][0] * ibuf_x;
1059         puv[0][1] = orig_uv[0][1] * ibuf_y;
1060
1061         puv[1][0] = orig_uv[1][0] * ibuf_x;
1062         puv[1][1] = orig_uv[1][1] * ibuf_y;
1063
1064         puv[2][0] = orig_uv[2][0] * ibuf_x;
1065         puv[2][1] = orig_uv[2][1] * ibuf_y;
1066
1067         if (is_quad) {
1068                 puv[3][0] = orig_uv[3][0] * ibuf_x;
1069                 puv[3][1] = orig_uv[3][1] * ibuf_y;
1070         }
1071
1072         /* face edge directions */
1073         sub_v2_v2v2(dir1, puv[1], puv[0]);
1074         sub_v2_v2v2(dir2, puv[2], puv[1]);
1075         normalize_v2(dir1);
1076         normalize_v2(dir2);
1077
1078         if (is_quad) {
1079                 sub_v2_v2v2(dir3, puv[3], puv[2]);
1080                 sub_v2_v2v2(dir4, puv[0], puv[3]);
1081                 normalize_v2(dir3);
1082                 normalize_v2(dir4);
1083         }
1084         else {
1085                 sub_v2_v2v2(dir3, puv[0], puv[2]);
1086                 normalize_v2(dir3);
1087         }
1088
1089         /* TODO - angle_normalized_v2v2(...) * (M_PI/180.0f)
1090          * This is incorrect. Its already given radians but without it wont work.
1091          * need to look into a fix - campbell */
1092         if (is_quad) {
1093                 a1 = shell_angle_to_dist(angle_normalized_v2v2(dir4, dir1) * ((float)M_PI/180.0f));
1094                 a2 = shell_angle_to_dist(angle_normalized_v2v2(dir1, dir2) * ((float)M_PI/180.0f));
1095                 a3 = shell_angle_to_dist(angle_normalized_v2v2(dir2, dir3) * ((float)M_PI/180.0f));
1096                 a4 = shell_angle_to_dist(angle_normalized_v2v2(dir3, dir4) * ((float)M_PI/180.0f));
1097         }
1098         else {
1099                 a1 = shell_angle_to_dist(angle_normalized_v2v2(dir3, dir1) * ((float)M_PI/180.0f));
1100                 a2 = shell_angle_to_dist(angle_normalized_v2v2(dir1, dir2) * ((float)M_PI/180.0f));
1101                 a3 = shell_angle_to_dist(angle_normalized_v2v2(dir2, dir3) * ((float)M_PI/180.0f));
1102         }
1103
1104         if (is_quad) {
1105                 sub_v2_v2v2(no1, dir4, dir1);
1106                 sub_v2_v2v2(no2, dir1, dir2);
1107                 sub_v2_v2v2(no3, dir2, dir3);
1108                 sub_v2_v2v2(no4, dir3, dir4);
1109                 normalize_v2(no1);
1110                 normalize_v2(no2);
1111                 normalize_v2(no3);
1112                 normalize_v2(no4);
1113                 mul_v2_fl(no1, a1*scaler);
1114                 mul_v2_fl(no2, a2*scaler);
1115                 mul_v2_fl(no3, a3*scaler);
1116                 mul_v2_fl(no4, a4*scaler);
1117                 add_v2_v2v2(outset_uv[0], puv[0], no1);
1118                 add_v2_v2v2(outset_uv[1], puv[1], no2);
1119                 add_v2_v2v2(outset_uv[2], puv[2], no3);
1120                 add_v2_v2v2(outset_uv[3], puv[3], no4);
1121                 mul_v2_v2(outset_uv[0], ibuf_inv);
1122                 mul_v2_v2(outset_uv[1], ibuf_inv);
1123                 mul_v2_v2(outset_uv[2], ibuf_inv);
1124                 mul_v2_v2(outset_uv[3], ibuf_inv);
1125         }
1126         else {
1127                 sub_v2_v2v2(no1, dir3, dir1);
1128                 sub_v2_v2v2(no2, dir1, dir2);
1129                 sub_v2_v2v2(no3, dir2, dir3);
1130                 normalize_v2(no1);
1131                 normalize_v2(no2);
1132                 normalize_v2(no3);
1133                 mul_v2_fl(no1, a1*scaler);
1134                 mul_v2_fl(no2, a2*scaler);
1135                 mul_v2_fl(no3, a3*scaler);
1136                 add_v2_v2v2(outset_uv[0], puv[0], no1);
1137                 add_v2_v2v2(outset_uv[1], puv[1], no2);
1138                 add_v2_v2v2(outset_uv[2], puv[2], no3);
1139
1140                 mul_v2_v2(outset_uv[0], ibuf_inv);
1141                 mul_v2_v2(outset_uv[1], ibuf_inv);
1142                 mul_v2_v2(outset_uv[2], ibuf_inv);
1143         }
1144 }
1145
1146 /*
1147  * Be tricky with flags, first 4 bits are PROJ_FACE_SEAM1 to 4, last 4 bits are PROJ_FACE_NOSEAM1 to 4
1148  * 1<<i - where i is (0-3)
1149  *
1150  * If we're multithreadng, make sure threads are locked when this is called
1151  */
1152 static void project_face_seams_init(const ProjPaintState *ps, const int face_index, const int is_quad)
1153 {
1154         int other_face, other_fidx; /* vars for the other face, we also set its flag */
1155         int fidx1 = is_quad ? 3 : 2;
1156         int fidx2 = 0; /* next fidx in the face (0,1,2,3) -> (1,2,3,0) or (0,1,2) -> (1,2,0) for a tri */
1157
1158         do {
1159                 if ((ps->faceSeamFlags[face_index] & (1<<fidx1|16<<fidx1)) == 0) {
1160                         if (check_seam(ps, face_index, fidx1, fidx2, &other_face, &other_fidx)) {
1161                                 ps->faceSeamFlags[face_index] |= 1<<fidx1;
1162                                 if (other_face != -1)
1163                                         ps->faceSeamFlags[other_face] |= 1<<other_fidx;
1164                         }
1165                         else {
1166                                 ps->faceSeamFlags[face_index] |= 16<<fidx1;
1167                                 if (other_face != -1)
1168                                         ps->faceSeamFlags[other_face] |= 16<<other_fidx; /* second 4 bits for disabled */
1169                         }
1170                 }
1171
1172                 fidx2 = fidx1;
1173         } while (fidx1--);
1174 }
1175 #endif // PROJ_DEBUG_NOSEAMBLEED
1176
1177
1178 /* Converts a UV location to a 3D screenspace location
1179  * Takes a 'uv' and 3 UV coords, and sets the values of pixelScreenCo
1180  *
1181  * This is used for finding a pixels location in screenspace for painting */
1182 static void screen_px_from_ortho(
1183                 float uv[2],
1184                 float v1co[3], float v2co[3], float v3co[3], /* Screenspace coords */
1185                 float uv1co[2], float uv2co[2], float uv3co[2],
1186                 float pixelScreenCo[4],
1187                 float w[3])
1188 {
1189         barycentric_weights_v2(uv1co, uv2co, uv3co, uv, w);
1190         interp_v3_v3v3v3(pixelScreenCo, v1co, v2co, v3co, w);
1191 }
1192
1193 /* same as screen_px_from_ortho except we need to take into account
1194  * the perspective W coord for each vert */
1195 static void screen_px_from_persp(
1196                 float uv[2],
1197                 float v1co[4], float v2co[4], float v3co[4], /* screenspace coords */
1198                 float uv1co[2], float uv2co[2], float uv3co[2],
1199                 float pixelScreenCo[4],
1200                 float w[3])
1201 {
1202
1203         float wtot_inv, wtot;
1204         barycentric_weights_v2(uv1co, uv2co, uv3co, uv, w);
1205
1206         /* re-weight from the 4th coord of each screen vert */
1207         w[0] *= v1co[3];
1208         w[1] *= v2co[3];
1209         w[2] *= v3co[3];
1210
1211         wtot = w[0]+w[1]+w[2];
1212
1213         if (wtot > 0.0f) {
1214                 wtot_inv = 1.0f / wtot;
1215                 w[0] *= wtot_inv;
1216                 w[1] *= wtot_inv;
1217                 w[2] *= wtot_inv;
1218         }
1219         else {
1220                 w[0] = w[1] = w[2] = 1.0f/3.0f; /* dummy values for zero area face */
1221         }
1222         /* done re-weighting */
1223
1224         interp_v3_v3v3v3(pixelScreenCo, v1co, v2co, v3co, w);
1225 }
1226
1227 static void project_face_pixel(const MTFace *tf_other, ImBuf *ibuf_other, const float w[3], int side, unsigned char rgba_ub[4], float rgba_f[4])
1228 {
1229         float *uvCo1, *uvCo2, *uvCo3;
1230         float uv_other[2], x, y;
1231
1232         uvCo1 =  (float *)tf_other->uv[0];
1233         if (side==1) {
1234                 uvCo2 =  (float *)tf_other->uv[2];
1235                 uvCo3 =  (float *)tf_other->uv[3];
1236         }
1237         else {
1238                 uvCo2 =  (float *)tf_other->uv[1];
1239                 uvCo3 =  (float *)tf_other->uv[2];
1240         }
1241
1242         interp_v2_v2v2v2(uv_other, uvCo1, uvCo2, uvCo3, (float*)w);
1243
1244         /* use */
1245         uvco_to_wrapped_pxco(uv_other, ibuf_other->x, ibuf_other->y, &x, &y);
1246
1247
1248         if (ibuf_other->rect_float) { /* from float to float */
1249                 bilinear_interpolation_color_wrap(ibuf_other, NULL, rgba_f, x, y);
1250         }
1251         else { /* from char to float */
1252                 bilinear_interpolation_color_wrap(ibuf_other, rgba_ub, NULL, x, y);
1253         }
1254
1255 }
1256
1257 /* run this outside project_paint_uvpixel_init since pixels with mask 0 dont need init */
1258 static float project_paint_uvpixel_mask(
1259                 const ProjPaintState *ps,
1260                 const int face_index,
1261                 const int side,
1262                 const float w[3])
1263 {
1264         float mask;
1265
1266         /* Image Mask */
1267         if (ps->do_layer_stencil) {
1268                 /* another UV layers image is masking this one's */
1269                 ImBuf *ibuf_other;
1270                 const MTFace *tf_other = ps->dm_mtface_stencil + face_index;
1271
1272                 if (tf_other->tpage && (ibuf_other = BKE_image_get_ibuf(tf_other->tpage, NULL))) {
1273                         /* BKE_image_get_ibuf - TODO - this may be slow */
1274                         unsigned char rgba_ub[4];
1275                         float rgba_f[4];
1276
1277                         project_face_pixel(tf_other, ibuf_other, w, side, rgba_ub, rgba_f);
1278
1279                         if (ibuf_other->rect_float) { /* from float to float */
1280                                 mask = ((rgba_f[0]+rgba_f[1]+rgba_f[2])/3.0f) * rgba_f[3];
1281                         }
1282                         else { /* from char to float */
1283                                 mask = ((rgba_ub[0]+rgba_ub[1]+rgba_ub[2])/(256*3.0f)) * (rgba_ub[3]/256.0f);
1284                         }
1285
1286                         if (!ps->do_layer_stencil_inv) /* matching the gimps layer mask black/white rules, white==full opacity */
1287                                 mask = (1.0f - mask);
1288
1289                         if (mask == 0.0f) {
1290                                 return 0.0f;
1291                         }
1292                 }
1293                 else {
1294                         return 0.0f;
1295                 }
1296         } else {
1297                 mask = 1.0f;
1298         }
1299
1300         /* calculate mask */
1301         if (ps->do_mask_normal) {
1302                 MFace *mf = ps->dm_mface + face_index;
1303                 short *no1, *no2, *no3;
1304                 float no[3], angle;
1305                 no1 = ps->dm_mvert[mf->v1].no;
1306                 if (side==1) {
1307                         no2 = ps->dm_mvert[mf->v3].no;
1308                         no3 = ps->dm_mvert[mf->v4].no;
1309                 }
1310                 else {
1311                         no2 = ps->dm_mvert[mf->v2].no;
1312                         no3 = ps->dm_mvert[mf->v3].no;
1313                 }
1314
1315                 no[0] = w[0]*no1[0] + w[1]*no2[0] + w[2]*no3[0];
1316                 no[1] = w[0]*no1[1] + w[1]*no2[1] + w[2]*no3[1];
1317                 no[2] = w[0]*no1[2] + w[1]*no2[2] + w[2]*no3[2];
1318                 normalize_v3(no);
1319
1320                 /* now we can use the normal as a mask */
1321                 if (ps->is_ortho) {
1322                         angle = angle_normalized_v3v3((float *)ps->viewDir, no);
1323                 }
1324                 else {
1325                         /* Annoying but for the perspective view we need to get the pixels location in 3D space :/ */
1326                         float viewDirPersp[3];
1327                         float *co1, *co2, *co3;
1328                         co1 = ps->dm_mvert[mf->v1].co;
1329                         if (side==1) {
1330                                 co2 = ps->dm_mvert[mf->v3].co;
1331                                 co3 = ps->dm_mvert[mf->v4].co;
1332                         }
1333                         else {
1334                                 co2 = ps->dm_mvert[mf->v2].co;
1335                                 co3 = ps->dm_mvert[mf->v3].co;
1336                         }
1337
1338                         /* Get the direction from the viewPoint to the pixel and normalize */
1339                         viewDirPersp[0] = (ps->viewPos[0] - (w[0]*co1[0] + w[1]*co2[0] + w[2]*co3[0]));
1340                         viewDirPersp[1] = (ps->viewPos[1] - (w[0]*co1[1] + w[1]*co2[1] + w[2]*co3[1]));
1341                         viewDirPersp[2] = (ps->viewPos[2] - (w[0]*co1[2] + w[1]*co2[2] + w[2]*co3[2]));
1342                         normalize_v3(viewDirPersp);
1343
1344                         angle = angle_normalized_v3v3(viewDirPersp, no);
1345                 }
1346
1347                 if (angle >= ps->normal_angle) {
1348                         return 0.0f; /* outsize the normal limit*/
1349                 }
1350                 else if (angle > ps->normal_angle_inner) {
1351                         mask *= (ps->normal_angle - angle) / ps->normal_angle_range;
1352                 } /* otherwise no mask normal is needed, were within the limit */
1353         }
1354
1355         // This only works when the opacity dosnt change while painting, stylus pressure messes with this
1356         // so dont use it.
1357         // if (ps->is_airbrush==0) mask *= brush_alpha(ps->brush);
1358
1359         return mask;
1360 }
1361
1362 /* run this function when we know a bucket's, face's pixel can be initialized,
1363  * return the ProjPixel which is added to 'ps->bucketRect[bucket_index]' */
1364 static ProjPixel *project_paint_uvpixel_init(
1365                 const ProjPaintState *ps,
1366                 MemArena *arena,
1367                 const ImBuf *ibuf,
1368                 short x_px, short y_px,
1369                 const float mask,
1370                 const int face_index,
1371                 const int image_index,
1372                 const float pixelScreenCo[4],
1373                 const int side,
1374                 const float w[3])
1375 {
1376         ProjPixel *projPixel;
1377         short size;
1378
1379         /* wrap pixel location */
1380         x_px = x_px % ibuf->x;
1381         if (x_px<0) x_px += ibuf->x;
1382         y_px = y_px % ibuf->y;
1383         if (y_px<0) y_px += ibuf->y;
1384
1385         if (ps->tool==PAINT_TOOL_CLONE) {
1386                 size = sizeof(ProjPixelClone);
1387         }
1388         else if (ps->tool==PAINT_TOOL_SMEAR) {
1389                 size = sizeof(ProjPixelClone);
1390         }
1391         else {
1392                 size = sizeof(ProjPixel);
1393         }
1394
1395         projPixel = (ProjPixel *)BLI_memarena_alloc(arena, size);
1396         //memset(projPixel, 0, size);
1397
1398         if (ibuf->rect_float) {
1399                 projPixel->pixel.f_pt = (float *)ibuf->rect_float + ((x_px + y_px * ibuf->x) * 4);
1400                 projPixel->origColor.f[0] = projPixel->newColor.f[0] = projPixel->pixel.f_pt[0];
1401                 projPixel->origColor.f[1] = projPixel->newColor.f[1] = projPixel->pixel.f_pt[1];
1402                 projPixel->origColor.f[2] = projPixel->newColor.f[2] = projPixel->pixel.f_pt[2];
1403                 projPixel->origColor.f[3] = projPixel->newColor.f[3] = projPixel->pixel.f_pt[3];
1404         }
1405         else {
1406                 projPixel->pixel.ch_pt = ((unsigned char *)ibuf->rect + ((x_px + y_px * ibuf->x) * 4));
1407                 projPixel->origColor.uint = projPixel->newColor.uint = *projPixel->pixel.uint_pt;
1408         }
1409
1410         /* screenspace unclamped, we could keep its z and w values but dont need them at the moment */
1411         VECCOPY2D(projPixel->projCoSS, pixelScreenCo);
1412
1413         projPixel->x_px = x_px;
1414         projPixel->y_px = y_px;
1415
1416         projPixel->mask = (unsigned short)(mask * 65535);
1417         projPixel->mask_max = 0;
1418
1419         /* which bounding box cell are we in?, needed for undo */
1420         projPixel->bb_cell_index = ((int)(((float)x_px/(float)ibuf->x) * PROJ_BOUNDBOX_DIV)) + ((int)(((float)y_px/(float)ibuf->y) * PROJ_BOUNDBOX_DIV)) * PROJ_BOUNDBOX_DIV ;
1421
1422         /* done with view3d_project_float inline */
1423         if (ps->tool==PAINT_TOOL_CLONE) {
1424                 if (ps->dm_mtface_clone) {
1425                         ImBuf *ibuf_other;
1426                         const MTFace *tf_other = ps->dm_mtface_clone + face_index;
1427
1428                         if (tf_other->tpage && (ibuf_other = BKE_image_get_ibuf(tf_other->tpage, NULL))) {
1429                                 /* BKE_image_get_ibuf - TODO - this may be slow */
1430
1431                                 if (ibuf->rect_float) {
1432                                         if (ibuf_other->rect_float) { /* from float to float */
1433                                                 project_face_pixel(tf_other, ibuf_other, w, side, NULL, ((ProjPixelClone *)projPixel)->clonepx.f);
1434                                         }
1435                                         else { /* from char to float */
1436                                                 unsigned char rgba_ub[4];
1437                                                 project_face_pixel(tf_other, ibuf_other, w, side, rgba_ub, NULL);
1438                                                 IMAPAINT_CHAR_RGBA_TO_FLOAT(((ProjPixelClone *)projPixel)->clonepx.f, rgba_ub);
1439                                         }
1440                                 }
1441                                 else {
1442                                         if (ibuf_other->rect_float) { /* float to char */
1443                                                 float rgba[4];
1444                                                 project_face_pixel(tf_other, ibuf_other, w, side, NULL, rgba);
1445                                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(((ProjPixelClone *)projPixel)->clonepx.ch, rgba)
1446                                         }
1447                                         else { /* char to char */
1448                                                 project_face_pixel(tf_other, ibuf_other, w, side, ((ProjPixelClone *)projPixel)->clonepx.ch, NULL);
1449                                         }
1450                                 }
1451                         }
1452                         else {
1453                                 if (ibuf->rect_float) {
1454                                         ((ProjPixelClone *)projPixel)->clonepx.f[3] = 0;
1455                                 }
1456                                 else {
1457                                         ((ProjPixelClone *)projPixel)->clonepx.ch[3] = 0;
1458                                 }
1459                         }
1460
1461                 }
1462                 else {
1463                         float co[2];
1464                         sub_v2_v2v2(co, projPixel->projCoSS, (float *)ps->cloneOffset);
1465
1466                         /* no need to initialize the bucket, we're only checking buckets faces and for this
1467                          * the faces are already initialized in project_paint_delayed_face_init(...) */
1468                         if (ibuf->rect_float) {
1469                                 if (!project_paint_PickColor(ps, co, ((ProjPixelClone *)projPixel)->clonepx.f, NULL, 1)) {
1470                                         ((ProjPixelClone *)projPixel)->clonepx.f[3] = 0; /* zero alpha - ignore */
1471                                 }
1472                         }
1473                         else {
1474                                 if (!project_paint_PickColor(ps, co, NULL, ((ProjPixelClone *)projPixel)->clonepx.ch, 1)) {
1475                                         ((ProjPixelClone *)projPixel)->clonepx.ch[3] = 0; /* zero alpha - ignore */
1476                                 }
1477                         }
1478                 }
1479         }
1480
1481 #ifdef PROJ_DEBUG_PAINT
1482         if (ibuf->rect_float)   projPixel->pixel.f_pt[0] = 0;
1483         else                                    projPixel->pixel.ch_pt[0] = 0;
1484 #endif
1485         projPixel->image_index = image_index;
1486
1487         return projPixel;
1488 }
1489
1490 static int line_clip_rect2f(
1491                 rctf *rect,
1492                 const float l1[2], const float l2[2],
1493                 float l1_clip[2], float l2_clip[2])
1494 {
1495         /* first account for horizontal, then vertical lines */
1496         /* horiz */
1497         if (fabsf(l1[1]-l2[1]) < PROJ_GEOM_TOLERANCE) {
1498                 /* is the line out of range on its Y axis? */
1499                 if (l1[1] < rect->ymin || l1[1] > rect->ymax) {
1500                         return 0;
1501                 }
1502                 /* line is out of range on its X axis */
1503                 if ((l1[0] < rect->xmin && l2[0] < rect->xmin) || (l1[0] > rect->xmax && l2[0] > rect->xmax)) {
1504                         return 0;
1505                 }
1506
1507
1508                 if (fabsf(l1[0]-l2[0]) < PROJ_GEOM_TOLERANCE) { /* this is a single point  (or close to)*/
1509                         if (BLI_in_rctf(rect, l1[0], l1[1])) {
1510                                 VECCOPY2D(l1_clip, l1);
1511                                 VECCOPY2D(l2_clip, l2);
1512                                 return 1;
1513                         }
1514                         else {
1515                                 return 0;
1516                         }
1517                 }
1518
1519                 VECCOPY2D(l1_clip, l1);
1520                 VECCOPY2D(l2_clip, l2);
1521                 CLAMP(l1_clip[0], rect->xmin, rect->xmax);
1522                 CLAMP(l2_clip[0], rect->xmin, rect->xmax);
1523                 return 1;
1524         }
1525         else if (fabsf(l1[0]-l2[0]) < PROJ_GEOM_TOLERANCE) {
1526                 /* is the line out of range on its X axis? */
1527                 if (l1[0] < rect->xmin || l1[0] > rect->xmax) {
1528                         return 0;
1529                 }
1530
1531                 /* line is out of range on its Y axis */
1532                 if ((l1[1] < rect->ymin && l2[1] < rect->ymin) || (l1[1] > rect->ymax && l2[1] > rect->ymax)) {
1533                         return 0;
1534                 }
1535
1536                 if (fabsf(l1[1]-l2[1]) < PROJ_GEOM_TOLERANCE) { /* this is a single point  (or close to)*/
1537                         if (BLI_in_rctf(rect, l1[0], l1[1])) {
1538                                 VECCOPY2D(l1_clip, l1);
1539                                 VECCOPY2D(l2_clip, l2);
1540                                 return 1;
1541                         }
1542                         else {
1543                                 return 0;
1544                         }
1545                 }
1546
1547                 VECCOPY2D(l1_clip, l1);
1548                 VECCOPY2D(l2_clip, l2);
1549                 CLAMP(l1_clip[1], rect->ymin, rect->ymax);
1550                 CLAMP(l2_clip[1], rect->ymin, rect->ymax);
1551                 return 1;
1552         }
1553         else {
1554                 float isect;
1555                 short ok1 = 0;
1556                 short ok2 = 0;
1557
1558                 /* Done with vertical lines */
1559
1560                 /* are either of the points inside the rectangle ? */
1561                 if (BLI_in_rctf(rect, l1[0], l1[1])) {
1562                         VECCOPY2D(l1_clip, l1);
1563                         ok1 = 1;
1564                 }
1565
1566                 if (BLI_in_rctf(rect, l2[0], l2[1])) {
1567                         VECCOPY2D(l2_clip, l2);
1568                         ok2 = 1;
1569                 }
1570
1571                 /* line inside rect */
1572                 if (ok1 && ok2) return 1;
1573
1574                 /* top/bottom */
1575                 if (line_isect_y(l1, l2, rect->ymin, &isect) && (isect >= rect->xmin) && (isect <= rect->xmax)) {
1576                         if (l1[1] < l2[1]) { /* line 1 is outside */
1577                                 l1_clip[0] = isect;
1578                                 l1_clip[1] = rect->ymin;
1579                                 ok1 = 1;
1580                         }
1581                         else {
1582                                 l2_clip[0] = isect;
1583                                 l2_clip[1] = rect->ymin;
1584                                 ok2 = 2;
1585                         }
1586                 }
1587
1588                 if (ok1 && ok2) return 1;
1589
1590                 if (line_isect_y(l1, l2, rect->ymax, &isect) && (isect >= rect->xmin) && (isect <= rect->xmax)) {
1591                         if (l1[1] > l2[1]) { /* line 1 is outside */
1592                                 l1_clip[0] = isect;
1593                                 l1_clip[1] = rect->ymax;
1594                                 ok1 = 1;
1595                         }
1596                         else {
1597                                 l2_clip[0] = isect;
1598                                 l2_clip[1] = rect->ymax;
1599                                 ok2 = 2;
1600                         }
1601                 }
1602
1603                 if (ok1 && ok2) return 1;
1604
1605                 /* left/right */
1606                 if (line_isect_x(l1, l2, rect->xmin, &isect) && (isect >= rect->ymin) && (isect <= rect->ymax)) {
1607                         if (l1[0] < l2[0]) { /* line 1 is outside */
1608                                 l1_clip[0] = rect->xmin;
1609                                 l1_clip[1] = isect;
1610                                 ok1 = 1;
1611                         }
1612                         else {
1613                                 l2_clip[0] = rect->xmin;
1614                                 l2_clip[1] = isect;
1615                                 ok2 = 2;
1616                         }
1617                 }
1618
1619                 if (ok1 && ok2) return 1;
1620
1621                 if (line_isect_x(l1, l2, rect->xmax, &isect) && (isect >= rect->ymin) && (isect <= rect->ymax)) {
1622                         if (l1[0] > l2[0]) { /* line 1 is outside */
1623                                 l1_clip[0] = rect->xmax;
1624                                 l1_clip[1] = isect;
1625                                 ok1 = 1;
1626                         }
1627                         else {
1628                                 l2_clip[0] = rect->xmax;
1629                                 l2_clip[1] = isect;
1630                                 ok2 = 2;
1631                         }
1632                 }
1633
1634                 if (ok1 && ok2) {
1635                         return 1;
1636                 }
1637                 else {
1638                         return 0;
1639                 }
1640         }
1641 }
1642
1643
1644
1645 /* scale the quad & tri about its center
1646  * scaling by PROJ_FACE_SCALE_SEAM (0.99x) is used for getting fake UV pixel coords that are on the
1647  * edge of the face but slightly inside it occlusion tests dont return hits on adjacent faces */
1648 #ifndef PROJ_DEBUG_NOSEAMBLEED
1649 static void scale_quad(float insetCos[4][3], float *origCos[4], const float inset)
1650 {
1651         float cent[3];
1652         cent[0] = (origCos[0][0] + origCos[1][0] + origCos[2][0] + origCos[3][0]) / 4.0f;
1653         cent[1] = (origCos[0][1] + origCos[1][1] + origCos[2][1] + origCos[3][1]) / 4.0f;
1654         cent[2] = (origCos[0][2] + origCos[1][2] + origCos[2][2] + origCos[3][2]) / 4.0f;
1655
1656         sub_v3_v3v3(insetCos[0], origCos[0], cent);
1657         sub_v3_v3v3(insetCos[1], origCos[1], cent);
1658         sub_v3_v3v3(insetCos[2], origCos[2], cent);
1659         sub_v3_v3v3(insetCos[3], origCos[3], cent);
1660
1661         mul_v3_fl(insetCos[0], inset);
1662         mul_v3_fl(insetCos[1], inset);
1663         mul_v3_fl(insetCos[2], inset);
1664         mul_v3_fl(insetCos[3], inset);
1665
1666         add_v3_v3(insetCos[0], cent);
1667         add_v3_v3(insetCos[1], cent);
1668         add_v3_v3(insetCos[2], cent);
1669         add_v3_v3(insetCos[3], cent);
1670 }
1671
1672
1673 static void scale_tri(float insetCos[4][3], float *origCos[4], const float inset)
1674 {
1675         float cent[3];
1676         cent[0] = (origCos[0][0] + origCos[1][0] + origCos[2][0]) / 3.0f;
1677         cent[1] = (origCos[0][1] + origCos[1][1] + origCos[2][1]) / 3.0f;
1678         cent[2] = (origCos[0][2] + origCos[1][2] + origCos[2][2]) / 3.0f;
1679
1680         sub_v3_v3v3(insetCos[0], origCos[0], cent);
1681         sub_v3_v3v3(insetCos[1], origCos[1], cent);
1682         sub_v3_v3v3(insetCos[2], origCos[2], cent);
1683
1684         mul_v3_fl(insetCos[0], inset);
1685         mul_v3_fl(insetCos[1], inset);
1686         mul_v3_fl(insetCos[2], inset);
1687
1688         add_v3_v3(insetCos[0], cent);
1689         add_v3_v3(insetCos[1], cent);
1690         add_v3_v3(insetCos[2], cent);
1691 }
1692 #endif //PROJ_DEBUG_NOSEAMBLEED
1693
1694 static float Vec2Lenf_nosqrt(const float *v1, const float *v2)
1695 {
1696         float x, y;
1697
1698         x = v1[0]-v2[0];
1699         y = v1[1]-v2[1];
1700         return x*x+y*y;
1701 }
1702
1703 static float Vec2Lenf_nosqrt_other(const float *v1, const float v2_1, const float v2_2)
1704 {
1705         float x, y;
1706
1707         x = v1[0]-v2_1;
1708         y = v1[1]-v2_2;
1709         return x*x+y*y;
1710 }
1711
1712 /* note, use a squared value so we can use Vec2Lenf_nosqrt
1713  * be sure that you have done a bounds check first or this may fail */
1714 /* only give bucket_bounds as an arg because we need it elsewhere */
1715 static int project_bucket_isect_circle(const float cent[2], const float radius_squared, rctf *bucket_bounds)
1716 {
1717
1718         /* Would normally to a simple intersection test, however we know the bounds of these 2 already intersect
1719          * so we only need to test if the center is inside the vertical or horizontal bounds on either axis,
1720          * this is even less work then an intersection test
1721          *
1722         if (BLI_in_rctf(bucket_bounds, cent[0], cent[1]))
1723                 return 1;
1724          */
1725
1726         if((bucket_bounds->xmin <= cent[0] && bucket_bounds->xmax >= cent[0]) || (bucket_bounds->ymin <= cent[1] && bucket_bounds->ymax >= cent[1]) ) {
1727                 return 1;
1728         }
1729
1730         /* out of bounds left */
1731         if (cent[0] < bucket_bounds->xmin) {
1732                 /* lower left out of radius test */
1733                 if (cent[1] < bucket_bounds->ymin) {
1734                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmin, bucket_bounds->ymin) < radius_squared) ? 1 : 0;
1735                 }
1736                 /* top left test */
1737                 else if (cent[1] > bucket_bounds->ymax) {
1738                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmin, bucket_bounds->ymax) < radius_squared) ? 1 : 0;
1739                 }
1740         }
1741         else if (cent[0] > bucket_bounds->xmax) {
1742                 /* lower right out of radius test */
1743                 if (cent[1] < bucket_bounds->ymin) {
1744                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmax, bucket_bounds->ymin) < radius_squared) ? 1 : 0;
1745                 }
1746                 /* top right test */
1747                 else if (cent[1] > bucket_bounds->ymax) {
1748                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmax, bucket_bounds->ymax) < radius_squared) ? 1 : 0;
1749                 }
1750         }
1751
1752         return 0;
1753 }
1754
1755
1756
1757 /* Note for rect_to_uvspace_ortho() and rect_to_uvspace_persp()
1758  * in ortho view this function gives good results when bucket_bounds are outside the triangle
1759  * however in some cases, perspective view will mess up with faces that have minimal screenspace area (viewed from the side)
1760  *
1761  * for this reason its not relyable in this case so we'll use the Simple Barycentric' funcs that only account for points inside the triangle.
1762  * however switching back to this for ortho is always an option */
1763
1764 static void rect_to_uvspace_ortho(
1765                 rctf *bucket_bounds,
1766                 float *v1coSS, float *v2coSS, float *v3coSS,
1767                 float *uv1co, float *uv2co, float *uv3co,
1768                 float bucket_bounds_uv[4][2],
1769                 const int flip)
1770 {
1771         float uv[2];
1772         float w[3];
1773
1774         /* get the UV space bounding box */
1775         uv[0] = bucket_bounds->xmax;
1776         uv[1] = bucket_bounds->ymin;
1777         barycentric_weights_v2(v1coSS, v2coSS, v3coSS, uv, w);
1778         interp_v2_v2v2v2(bucket_bounds_uv[flip?3:0], uv1co, uv2co, uv3co, w);
1779
1780         //uv[0] = bucket_bounds->xmax; // set above
1781         uv[1] = bucket_bounds->ymax;
1782         barycentric_weights_v2(v1coSS, v2coSS, v3coSS, uv, w);
1783         interp_v2_v2v2v2(bucket_bounds_uv[flip?2:1], uv1co, uv2co, uv3co, w);
1784
1785         uv[0] = bucket_bounds->xmin;
1786         //uv[1] = bucket_bounds->ymax; // set above
1787         barycentric_weights_v2(v1coSS, v2coSS, v3coSS, uv, w);
1788         interp_v2_v2v2v2(bucket_bounds_uv[flip?1:2], uv1co, uv2co, uv3co, w);
1789
1790         //uv[0] = bucket_bounds->xmin; // set above
1791         uv[1] = bucket_bounds->ymin;
1792         barycentric_weights_v2(v1coSS, v2coSS, v3coSS, uv, w);
1793         interp_v2_v2v2v2(bucket_bounds_uv[flip?0:3], uv1co, uv2co, uv3co, w);
1794 }
1795
1796 /* same as above but use barycentric_weights_v2_persp */
1797 static void rect_to_uvspace_persp(
1798                 rctf *bucket_bounds,
1799                 float *v1coSS, float *v2coSS, float *v3coSS,
1800                 float *uv1co, float *uv2co, float *uv3co,
1801                 float bucket_bounds_uv[4][2],
1802                 const int flip
1803         )
1804 {
1805         float uv[2];
1806         float w[3];
1807
1808         /* get the UV space bounding box */
1809         uv[0] = bucket_bounds->xmax;
1810         uv[1] = bucket_bounds->ymin;
1811         barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, uv, w);
1812         interp_v2_v2v2v2(bucket_bounds_uv[flip?3:0], uv1co, uv2co, uv3co, w);
1813
1814         //uv[0] = bucket_bounds->xmax; // set above
1815         uv[1] = bucket_bounds->ymax;
1816         barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, uv, w);
1817         interp_v2_v2v2v2(bucket_bounds_uv[flip?2:1], uv1co, uv2co, uv3co, w);
1818
1819         uv[0] = bucket_bounds->xmin;
1820         //uv[1] = bucket_bounds->ymax; // set above
1821         barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, uv, w);
1822         interp_v2_v2v2v2(bucket_bounds_uv[flip?1:2], uv1co, uv2co, uv3co, w);
1823
1824         //uv[0] = bucket_bounds->xmin; // set above
1825         uv[1] = bucket_bounds->ymin;
1826         barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, uv, w);
1827         interp_v2_v2v2v2(bucket_bounds_uv[flip?0:3], uv1co, uv2co, uv3co, w);
1828 }
1829
1830 /* This works as we need it to but we can save a few steps and not use it */
1831
1832 #if 0
1833 static float angle_2d_clockwise(const float p1[2], const float p2[2], const float p3[2])
1834 {
1835         float v1[2], v2[2];
1836
1837         v1[0] = p1[0]-p2[0];    v1[1] = p1[1]-p2[1];
1838         v2[0] = p3[0]-p2[0];    v2[1] = p3[1]-p2[1];
1839
1840         return -atan2(v1[0]*v2[1] - v1[1]*v2[0], v1[0]*v2[0]+v1[1]*v2[1]);
1841 }
1842 #endif
1843
1844 #define ISECT_1 (1)
1845 #define ISECT_2 (1<<1)
1846 #define ISECT_3 (1<<2)
1847 #define ISECT_4 (1<<3)
1848 #define ISECT_ALL3 ((1<<3)-1)
1849 #define ISECT_ALL4 ((1<<4)-1)
1850
1851 /* limit must be a fraction over 1.0f */
1852 static int IsectPT2Df_limit(float pt[2], float v1[2], float v2[2], float v3[2], float limit)
1853 {
1854         return ((area_tri_v2(pt,v1,v2) + area_tri_v2(pt,v2,v3) + area_tri_v2(pt,v3,v1)) / (area_tri_v2(v1,v2,v3))) < limit;
1855 }
1856
1857 /* Clip the face by a bucket and set the uv-space bucket_bounds_uv
1858  * so we have the clipped UV's to do pixel intersection tests with
1859  * */
1860 static int float_z_sort_flip(const void *p1, const void *p2) {
1861         return (((float *)p1)[2] < ((float *)p2)[2] ? 1:-1);
1862 }
1863
1864 static int float_z_sort(const void *p1, const void *p2) {
1865         return (((float *)p1)[2] < ((float *)p2)[2] ?-1:1);
1866 }
1867
1868 static void project_bucket_clip_face(
1869                 const int is_ortho,
1870                 rctf *bucket_bounds,
1871                 float *v1coSS, float *v2coSS, float *v3coSS,
1872                 float *uv1co, float *uv2co, float *uv3co,
1873                 float bucket_bounds_uv[8][2],
1874                 int *tot)
1875 {
1876         int inside_bucket_flag = 0;
1877         int inside_face_flag = 0;
1878         const int flip = ((line_point_side_v2(v1coSS, v2coSS, v3coSS) > 0.0f) != (line_point_side_v2(uv1co, uv2co, uv3co) > 0.0f));
1879
1880         float bucket_bounds_ss[4][2];
1881
1882         /* get the UV space bounding box */
1883         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v1coSS[0], v1coSS[1]);
1884         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v2coSS[0], v2coSS[1])          << 1;
1885         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v3coSS[0], v3coSS[1])          << 2;
1886
1887         if (inside_bucket_flag == ISECT_ALL3) {
1888                 /* all screenspace points are inside the bucket bounding box, this means we dont need to clip and can simply return the UVs */
1889                 if (flip) { /* facing the back? */
1890                         VECCOPY2D(bucket_bounds_uv[0], uv3co);
1891                         VECCOPY2D(bucket_bounds_uv[1], uv2co);
1892                         VECCOPY2D(bucket_bounds_uv[2], uv1co);
1893                 }
1894                 else {
1895                         VECCOPY2D(bucket_bounds_uv[0], uv1co);
1896                         VECCOPY2D(bucket_bounds_uv[1], uv2co);
1897                         VECCOPY2D(bucket_bounds_uv[2], uv3co);
1898                 }
1899
1900                 *tot = 3;
1901                 return;
1902         }
1903
1904         /* get the UV space bounding box */
1905         /* use IsectPT2Df_limit here so we catch points are are touching the tri edge (or a small fraction over) */
1906         bucket_bounds_ss[0][0] = bucket_bounds->xmax;
1907         bucket_bounds_ss[0][1] = bucket_bounds->ymin;
1908         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[0], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_1 : 0);
1909
1910         bucket_bounds_ss[1][0] = bucket_bounds->xmax;
1911         bucket_bounds_ss[1][1] = bucket_bounds->ymax;
1912         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[1], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_2 : 0);
1913
1914         bucket_bounds_ss[2][0] = bucket_bounds->xmin;
1915         bucket_bounds_ss[2][1] = bucket_bounds->ymax;
1916         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[2], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_3 : 0);
1917
1918         bucket_bounds_ss[3][0] = bucket_bounds->xmin;
1919         bucket_bounds_ss[3][1] = bucket_bounds->ymin;
1920         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[3], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_4 : 0);
1921
1922         if (inside_face_flag == ISECT_ALL4) {
1923                 /* bucket is totally inside the screenspace face, we can safely use weights */
1924
1925                 if (is_ortho)   rect_to_uvspace_ortho(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, bucket_bounds_uv, flip);
1926                 else                    rect_to_uvspace_persp(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, bucket_bounds_uv, flip);
1927
1928                 *tot = 4;
1929                 return;
1930         }
1931         else {
1932                 /* The Complicated Case!
1933                  *
1934                  * The 2 cases above are where the face is inside the bucket or the bucket is inside the face.
1935                  *
1936                  * we need to make a convex polyline from the intersection between the screenspace face
1937                  * and the bucket bounds.
1938                  *
1939                  * There are a number of ways this could be done, currently it just collects all intersecting verts,
1940                  * and line intersections,  then sorts them clockwise, this is a lot easier then evaluating the geometry to
1941                  * do a correct clipping on both shapes. */
1942
1943
1944                 /* add a bunch of points, we know must make up the convex hull which is the clipped rect and triangle */
1945
1946
1947
1948                 /* Maximum possible 6 intersections when using a rectangle and triangle */
1949                 float isectVCosSS[8][3]; /* The 3rd float is used to store angle for qsort(), NOT as a Z location */
1950                 float v1_clipSS[2], v2_clipSS[2];
1951                 float w[3];
1952
1953                 /* calc center*/
1954                 float cent[2] = {0.0f, 0.0f};
1955                 /*float up[2] = {0.0f, 1.0f};*/
1956                 int i;
1957                 short doubles;
1958
1959                 (*tot) = 0;
1960
1961                 if (inside_face_flag & ISECT_1) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[0]); (*tot)++; }
1962                 if (inside_face_flag & ISECT_2) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[1]); (*tot)++; }
1963                 if (inside_face_flag & ISECT_3) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[2]); (*tot)++; }
1964                 if (inside_face_flag & ISECT_4) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[3]); (*tot)++; }
1965
1966                 if (inside_bucket_flag & ISECT_1) {     VECCOPY2D(isectVCosSS[*tot], v1coSS); (*tot)++; }
1967                 if (inside_bucket_flag & ISECT_2) {     VECCOPY2D(isectVCosSS[*tot], v2coSS); (*tot)++; }
1968                 if (inside_bucket_flag & ISECT_3) {     VECCOPY2D(isectVCosSS[*tot], v3coSS); (*tot)++; }
1969
1970                 if ((inside_bucket_flag & (ISECT_1|ISECT_2)) != (ISECT_1|ISECT_2)) {
1971                         if (line_clip_rect2f(bucket_bounds, v1coSS, v2coSS, v1_clipSS, v2_clipSS)) {
1972                                 if ((inside_bucket_flag & ISECT_1)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
1973                                 if ((inside_bucket_flag & ISECT_2)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
1974                         }
1975                 }
1976
1977                 if ((inside_bucket_flag & (ISECT_2|ISECT_3)) != (ISECT_2|ISECT_3)) {
1978                         if (line_clip_rect2f(bucket_bounds, v2coSS, v3coSS, v1_clipSS, v2_clipSS)) {
1979                                 if ((inside_bucket_flag & ISECT_2)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
1980                                 if ((inside_bucket_flag & ISECT_3)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
1981                         }
1982                 }
1983
1984                 if ((inside_bucket_flag & (ISECT_3|ISECT_1)) != (ISECT_3|ISECT_1)) {
1985                         if (line_clip_rect2f(bucket_bounds, v3coSS, v1coSS, v1_clipSS, v2_clipSS)) {
1986                                 if ((inside_bucket_flag & ISECT_3)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
1987                                 if ((inside_bucket_flag & ISECT_1)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
1988                         }
1989                 }
1990
1991
1992                 if ((*tot) < 3) { /* no intersections to speak of */
1993                         *tot = 0;
1994                         return;
1995                 }
1996
1997                 /* now we have all points we need, collect their angles and sort them clockwise */
1998
1999                 for(i=0; i<(*tot); i++) {
2000                         cent[0] += isectVCosSS[i][0];
2001                         cent[1] += isectVCosSS[i][1];
2002                 }
2003                 cent[0] = cent[0] / (float)(*tot);
2004                 cent[1] = cent[1] / (float)(*tot);
2005
2006
2007
2008                 /* Collect angles for every point around the center point */
2009
2010
2011 #if 0   /* uses a few more cycles then the above loop */
2012                 for(i=0; i<(*tot); i++) {
2013                         isectVCosSS[i][2] = angle_2d_clockwise(up, cent, isectVCosSS[i]);
2014                 }
2015 #endif
2016
2017                 v1_clipSS[0] = cent[0]; /* Abuse this var for the loop below */
2018                 v1_clipSS[1] = cent[1] + 1.0f;
2019
2020                 for(i=0; i<(*tot); i++) {
2021                         v2_clipSS[0] = isectVCosSS[i][0] - cent[0];
2022                         v2_clipSS[1] = isectVCosSS[i][1] - cent[1];
2023                         isectVCosSS[i][2] = atan2f(v1_clipSS[0]*v2_clipSS[1] - v1_clipSS[1]*v2_clipSS[0], v1_clipSS[0]*v2_clipSS[0]+v1_clipSS[1]*v2_clipSS[1]);
2024                 }
2025
2026                 if (flip)       qsort(isectVCosSS, *tot, sizeof(float)*3, float_z_sort_flip);
2027                 else            qsort(isectVCosSS, *tot, sizeof(float)*3, float_z_sort);
2028
2029                 /* remove doubles */
2030                 /* first/last check */
2031                 if (fabsf(isectVCosSS[0][0]-isectVCosSS[(*tot)-1][0]) < PROJ_GEOM_TOLERANCE &&  fabsf(isectVCosSS[0][1]-isectVCosSS[(*tot)-1][1]) < PROJ_GEOM_TOLERANCE) {
2032                         (*tot)--;
2033                 }
2034
2035                 /* its possible there is only a few left after remove doubles */
2036                 if ((*tot) < 3) {
2037                         // printf("removed too many doubles A\n");
2038                         *tot = 0;
2039                         return;
2040                 }
2041
2042                 doubles = TRUE;
2043                 while (doubles==TRUE) {
2044                         doubles = FALSE;
2045                         for(i=1; i<(*tot); i++) {
2046                                 if (fabsf(isectVCosSS[i-1][0]-isectVCosSS[i][0]) < PROJ_GEOM_TOLERANCE &&
2047                                         fabsf(isectVCosSS[i-1][1]-isectVCosSS[i][1]) < PROJ_GEOM_TOLERANCE)
2048                                 {
2049                                         int j;
2050                                         for(j=i+1; j<(*tot); j++) {
2051                                                 isectVCosSS[j-1][0] = isectVCosSS[j][0];
2052                                                 isectVCosSS[j-1][1] = isectVCosSS[j][1];
2053                                         }
2054                                         doubles = TRUE; /* keep looking for more doubles */
2055                                         (*tot)--;
2056                                 }
2057                         }
2058                 }
2059
2060                 /* its possible there is only a few left after remove doubles */
2061                 if ((*tot) < 3) {
2062                         // printf("removed too many doubles B\n");
2063                         *tot = 0;
2064                         return;
2065                 }
2066
2067
2068                 if (is_ortho) {
2069                         for(i=0; i<(*tot); i++) {
2070                                 barycentric_weights_v2(v1coSS, v2coSS, v3coSS, isectVCosSS[i], w);
2071                                 interp_v2_v2v2v2(bucket_bounds_uv[i], uv1co, uv2co, uv3co, w);
2072                         }
2073                 }
2074                 else {
2075                         for(i=0; i<(*tot); i++) {
2076                                 barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, isectVCosSS[i], w);
2077                                 interp_v2_v2v2v2(bucket_bounds_uv[i], uv1co, uv2co, uv3co, w);
2078                         }
2079                 }
2080         }
2081
2082 #ifdef PROJ_DEBUG_PRINT_CLIP
2083         /* include this at the bottom of the above function to debug the output */
2084
2085         {
2086                 /* If there are ever any problems, */
2087                 float test_uv[4][2];
2088                 int i;
2089                 if (is_ortho)   rect_to_uvspace_ortho(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, test_uv, flip);
2090                 else                            rect_to_uvspace_persp(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, test_uv, flip);
2091                 printf("(  [(%f,%f), (%f,%f), (%f,%f), (%f,%f)], ", test_uv[0][0], test_uv[0][1],   test_uv[1][0], test_uv[1][1],    test_uv[2][0], test_uv[2][1],    test_uv[3][0], test_uv[3][1]);
2092
2093                 printf("  [(%f,%f), (%f,%f), (%f,%f)], ", uv1co[0], uv1co[1],   uv2co[0], uv2co[1],    uv3co[0], uv3co[1]);
2094
2095                 printf("[");
2096                 for (i=0; i < (*tot); i++) {
2097                         printf("(%f, %f),", bucket_bounds_uv[i][0], bucket_bounds_uv[i][1]);
2098                 }
2099                 printf("]),\\\n");
2100         }
2101 #endif
2102 }
2103
2104         /*
2105 # This script creates faces in a blender scene from printed data above.
2106
2107 project_ls = [
2108 ...(output from above block)...
2109 ]
2110
2111 from Blender import Scene, Mesh, Window, sys, Mathutils
2112
2113 import bpy
2114
2115 V = Mathutils.Vector
2116
2117 def main():
2118         sce = bpy.data.scenes.active
2119
2120         for item in project_ls:
2121                 bb = item[0]
2122                 uv = item[1]
2123                 poly = item[2]
2124
2125                 me = bpy.data.meshes.new()
2126                 ob = sce.objects.new(me)
2127
2128                 me.verts.extend([V(bb[0]).resize3D(), V(bb[1]).resize3D(), V(bb[2]).resize3D(), V(bb[3]).resize3D()])
2129                 me.faces.extend([(0,1,2,3),])
2130                 me.verts.extend([V(uv[0]).resize3D(), V(uv[1]).resize3D(), V(uv[2]).resize3D()])
2131                 me.faces.extend([(4,5,6),])
2132
2133                 vs = [V(p).resize3D() for p in poly]
2134                 print len(vs)
2135                 l = len(me.verts)
2136                 me.verts.extend(vs)
2137
2138                 i = l
2139                 while i < len(me.verts):
2140                         ii = i+1
2141                         if ii==len(me.verts):
2142                                 ii = l
2143                         me.edges.extend([i, ii])
2144                         i+=1
2145
2146 if __name__ == '__main__':
2147         main()
2148  */
2149
2150
2151 #undef ISECT_1
2152 #undef ISECT_2
2153 #undef ISECT_3
2154 #undef ISECT_4
2155 #undef ISECT_ALL3
2156 #undef ISECT_ALL4
2157
2158
2159 /* checks if pt is inside a convex 2D polyline, the polyline must be ordered rotating clockwise
2160  * otherwise it would have to test for mixed (line_point_side_v2 > 0.0f) cases */
2161 static int IsectPoly2Df(const float pt[2], float uv[][2], const int tot)
2162 {
2163         int i;
2164         if (line_point_side_v2(uv[tot-1], uv[0], pt) < 0.0f)
2165                 return 0;
2166
2167         for (i=1; i<tot; i++) {
2168                 if (line_point_side_v2(uv[i-1], uv[i], pt) < 0.0f)
2169                         return 0;
2170
2171         }
2172
2173         return 1;
2174 }
2175 static int IsectPoly2Df_twoside(const float pt[2], float uv[][2], const int tot)
2176 {
2177         int i;
2178         int side = (line_point_side_v2(uv[tot-1], uv[0], pt) > 0.0f);
2179
2180         for (i=1; i<tot; i++) {
2181                 if ((line_point_side_v2(uv[i-1], uv[i], pt) > 0.0f) != side)
2182                         return 0;
2183
2184         }
2185
2186         return 1;
2187 }
2188
2189 /* One of the most important function for projectiopn painting, since it selects the pixels to be added into each bucket.
2190  * initialize pixels from this face where it intersects with the bucket_index, optionally initialize pixels for removing seams */
2191 static void project_paint_face_init(const ProjPaintState *ps, const int thread_index, const int bucket_index, const int face_index, const int image_index, rctf *bucket_bounds, const ImBuf *ibuf, const short clamp_u, const short clamp_v)
2192 {
2193         /* Projection vars, to get the 3D locations into screen space  */
2194         MemArena *arena = ps->arena_mt[thread_index];
2195         LinkNode **bucketPixelNodes = ps->bucketRect + bucket_index;
2196         LinkNode *bucketFaceNodes = ps->bucketFaces[bucket_index];
2197
2198         const MFace *mf = ps->dm_mface + face_index;
2199         const MTFace *tf = ps->dm_mtface + face_index;
2200
2201         /* UV/pixel seeking data */
2202         int x; /* Image X-Pixel */
2203         int y;/* Image Y-Pixel */
2204         float mask;
2205         float uv[2]; /* Image floating point UV - same as x, y but from 0.0-1.0 */
2206
2207         int side;
2208         float *v1coSS, *v2coSS, *v3coSS; /* vert co screen-space, these will be assigned to mf->v1,2,3 or mf->v1,3,4 */
2209
2210         float *vCo[4]; /* vertex screenspace coords */
2211
2212         float w[3], wco[3];
2213
2214         float *uv1co, *uv2co, *uv3co; /* for convenience only, these will be assigned to tf->uv[0],1,2 or tf->uv[0],2,3 */
2215         float pixelScreenCo[4];
2216
2217         rcti bounds_px; /* ispace bounds */
2218         /* vars for getting uvspace bounds */
2219
2220         float tf_uv_pxoffset[4][2]; /* bucket bounds in UV space so we can init pixels only for this face,  */
2221         float xhalfpx, yhalfpx;
2222         const float ibuf_xf = (float)ibuf->x, ibuf_yf = (float)ibuf->y;
2223
2224         int has_x_isect = 0, has_isect = 0; /* for early loop exit */
2225
2226         int i1, i2, i3;
2227
2228         float uv_clip[8][2];
2229         int uv_clip_tot;
2230         const short is_ortho = ps->is_ortho;
2231         const short do_backfacecull = ps->do_backfacecull;
2232         const short do_clip= ps->rv3d ? ps->rv3d->rflag & RV3D_CLIPPING : 0;
2233
2234         vCo[0] = ps->dm_mvert[mf->v1].co;
2235         vCo[1] = ps->dm_mvert[mf->v2].co;
2236         vCo[2] = ps->dm_mvert[mf->v3].co;
2237
2238
2239         /* Use tf_uv_pxoffset instead of tf->uv so we can offset the UV half a pixel
2240          * this is done so we can avoid offseting all the pixels by 0.5 which causes
2241          * problems when wrapping negative coords */
2242         xhalfpx = (0.5f+   (PROJ_GEOM_TOLERANCE/3.0f)   ) / ibuf_xf;
2243         yhalfpx = (0.5f+   (PROJ_GEOM_TOLERANCE/4.0f)   ) / ibuf_yf;
2244
2245         /* Note about (PROJ_GEOM_TOLERANCE/x) above...
2246           Needed to add this offset since UV coords are often quads aligned to pixels.
2247           In this case pixels can be exactly between 2 triangles causing nasty
2248           artifacts.
2249
2250           This workaround can be removed and painting will still work on most cases
2251           but since the first thing most people try is painting onto a quad- better make it work.
2252          */
2253
2254
2255
2256         tf_uv_pxoffset[0][0] = tf->uv[0][0] - xhalfpx;
2257         tf_uv_pxoffset[0][1] = tf->uv[0][1] - yhalfpx;
2258
2259         tf_uv_pxoffset[1][0] = tf->uv[1][0] - xhalfpx;
2260         tf_uv_pxoffset[1][1] = tf->uv[1][1] - yhalfpx;
2261
2262         tf_uv_pxoffset[2][0] = tf->uv[2][0] - xhalfpx;
2263         tf_uv_pxoffset[2][1] = tf->uv[2][1] - yhalfpx;
2264
2265         if (mf->v4) {
2266                 vCo[3] = ps->dm_mvert[ mf->v4 ].co;
2267
2268                 tf_uv_pxoffset[3][0] = tf->uv[3][0] - xhalfpx;
2269                 tf_uv_pxoffset[3][1] = tf->uv[3][1] - yhalfpx;
2270                 side = 1;
2271         }
2272         else {
2273                 side = 0;
2274         }
2275
2276         do {
2277                 if (side==1) {
2278                         i1=0; i2=2; i3=3;
2279                 }
2280                 else {
2281                         i1=0; i2=1; i3=2;
2282                 }
2283
2284                 uv1co = tf_uv_pxoffset[i1]; // was tf->uv[i1];
2285                 uv2co = tf_uv_pxoffset[i2]; // was tf->uv[i2];
2286                 uv3co = tf_uv_pxoffset[i3]; // was tf->uv[i3];
2287
2288                 v1coSS = ps->screenCoords[ (*(&mf->v1 + i1)) ];
2289                 v2coSS = ps->screenCoords[ (*(&mf->v1 + i2)) ];
2290                 v3coSS = ps->screenCoords[ (*(&mf->v1 + i3)) ];
2291
2292                 /* This funtion gives is a concave polyline in UV space from the clipped quad and tri*/
2293                 project_bucket_clip_face(
2294                                 is_ortho, bucket_bounds,
2295                                 v1coSS, v2coSS, v3coSS,
2296                                 uv1co, uv2co, uv3co,
2297                                 uv_clip, &uv_clip_tot
2298                 );
2299
2300                 /* sometimes this happens, better just allow for 8 intersectiosn even though there should be max 6 */
2301                 /*
2302                 if (uv_clip_tot>6) {
2303                         printf("this should never happen! %d\n", uv_clip_tot);
2304                 }*/
2305
2306
2307                 if (pixel_bounds_array(uv_clip, &bounds_px, ibuf->x, ibuf->y, uv_clip_tot)) {
2308
2309                         if(clamp_u) {
2310                                 CLAMP(bounds_px.xmin, 0, ibuf->x);
2311                                 CLAMP(bounds_px.xmax, 0, ibuf->x);
2312                         }
2313
2314                         if(clamp_v) {
2315                                 CLAMP(bounds_px.ymin, 0, ibuf->y);
2316                                 CLAMP(bounds_px.ymax, 0, ibuf->y);
2317                         }
2318
2319                         /* clip face and */
2320
2321                         has_isect = 0;
2322                         for (y = bounds_px.ymin; y < bounds_px.ymax; y++) {
2323                                 //uv[1] = (((float)y) + 0.5f) / (float)ibuf->y;
2324                                 uv[1] = (float)y / ibuf_yf; /* use pixel offset UV coords instead */
2325
2326                                 has_x_isect = 0;
2327                                 for (x = bounds_px.xmin; x < bounds_px.xmax; x++) {
2328                                         //uv[0] = (((float)x) + 0.5f) / ibuf->x;
2329                                         uv[0] = (float)x / ibuf_xf; /* use pixel offset UV coords instead */
2330
2331                                         /* Note about IsectPoly2Df_twoside, checking the face or uv flipping doesnt work,
2332                                          * could check the poly direction but better to do this */
2333                                         if(     (do_backfacecull                && IsectPoly2Df(uv, uv_clip, uv_clip_tot)) ||
2334                                                 (do_backfacecull==0             && IsectPoly2Df_twoside(uv, uv_clip, uv_clip_tot))) {
2335
2336                                                 has_x_isect = has_isect = 1;
2337
2338                                                 if (is_ortho)   screen_px_from_ortho(uv, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, pixelScreenCo, w);
2339                                                 else                    screen_px_from_persp(uv, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, pixelScreenCo, w);
2340
2341                                                 /* a pitty we need to get the worldspace pixel location here */
2342                                                 if(do_clip) {
2343                                                         interp_v3_v3v3v3(wco, ps->dm_mvert[ (*(&mf->v1 + i1)) ].co, ps->dm_mvert[ (*(&mf->v1 + i2)) ].co, ps->dm_mvert[ (*(&mf->v1 + i3)) ].co, w);
2344                                                         if(ED_view3d_test_clipping(ps->rv3d, wco, 1)) {
2345                                                                 continue; /* Watch out that no code below this needs to run */
2346                                                         }
2347                                                 }
2348
2349                                                 /* Is this UV visible from the view? - raytrace */
2350                                                 /* project_paint_PickFace is less complex, use for testing */
2351                                                 //if (project_paint_PickFace(ps, pixelScreenCo, w, &side) == face_index) {
2352                                                 if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucketFaceNodes, face_index, pixelScreenCo)) {
2353
2354                                                         mask = project_paint_uvpixel_mask(ps, face_index, side, w);
2355
2356                                                         if (mask > 0.0f) {
2357                                                                 BLI_linklist_prepend_arena(
2358                                                                         bucketPixelNodes,
2359                                                                         project_paint_uvpixel_init(ps, arena, ibuf, x, y, mask, face_index, image_index, pixelScreenCo, side, w),
2360                                                                         arena
2361                                                                 );
2362                                                         }
2363                                                 }
2364
2365                                         }
2366 //#if 0
2367                                         else if (has_x_isect) {
2368                                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2369                                                 break;
2370                                         }
2371 //#endif
2372                                 }
2373
2374
2375 #if 0                   /* TODO - investigate why this dosnt work sometimes! it should! */
2376                                 /* no intersection for this entire row, after some intersection above means we can quit now */
2377                                 if (has_x_isect==0 && has_isect) {
2378                                         break;
2379                                 }
2380 #endif
2381                         }
2382                 }
2383         } while(side--);
2384
2385
2386
2387 #ifndef PROJ_DEBUG_NOSEAMBLEED
2388         if (ps->seam_bleed_px > 0.0f) {
2389                 int face_seam_flag;
2390
2391                 if (ps->thread_tot > 1)
2392                         BLI_lock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2393
2394                 face_seam_flag = ps->faceSeamFlags[face_index];
2395
2396                 /* are any of our edges un-initialized? */
2397                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_NOSEAM1))==0 ||
2398                         (face_seam_flag & (PROJ_FACE_SEAM2|PROJ_FACE_NOSEAM2))==0 ||
2399                         (face_seam_flag & (PROJ_FACE_SEAM3|PROJ_FACE_NOSEAM3))==0 ||
2400                         (face_seam_flag & (PROJ_FACE_SEAM4|PROJ_FACE_NOSEAM4))==0
2401                 ) {
2402                         project_face_seams_init(ps, face_index, mf->v4);
2403                         face_seam_flag = ps->faceSeamFlags[face_index];
2404                         //printf("seams - %d %d %d %d\n", flag&PROJ_FACE_SEAM1, flag&PROJ_FACE_SEAM2, flag&PROJ_FACE_SEAM3, flag&PROJ_FACE_SEAM4);
2405                 }
2406
2407                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_SEAM2|PROJ_FACE_SEAM3|PROJ_FACE_SEAM4))==0) {
2408
2409                         if (ps->thread_tot > 1)
2410                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2411
2412                 }
2413                 else {
2414                         /* we have a seam - deal with it! */
2415
2416                         /* Now create new UV's for the seam face */
2417                         float (*outset_uv)[2] = ps->faceSeamUVs[face_index];
2418                         float insetCos[4][3]; /* inset face coords.  NOTE!!! ScreenSace for ortho, Worldspace in prespective view */
2419
2420                         float fac;
2421                         float *vCoSS[4]; /* vertex screenspace coords */
2422
2423                         float bucket_clip_edges[2][2]; /* store the screenspace coords of the face, clipped by the bucket's screen aligned rectangle */
2424                         float edge_verts_inset_clip[2][3];
2425                         int fidx1, fidx2; /* face edge pairs - loop throuh these ((0,1), (1,2), (2,3), (3,0)) or ((0,1), (1,2), (2,0)) for a tri */
2426
2427                         float seam_subsection[4][2];
2428                         float fac1, fac2, ftot;
2429
2430
2431                         if (outset_uv[0][0]==FLT_MAX) /* first time initialize */
2432                                 uv_image_outset(tf_uv_pxoffset, outset_uv, ps->seam_bleed_px, ibuf->x, ibuf->y, mf->v4);
2433
2434                         /* ps->faceSeamUVs cant be modified when threading, now this is done we can unlock */
2435                         if (ps->thread_tot > 1)
2436                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2437
2438                         vCoSS[0] = ps->screenCoords[mf->v1];
2439                         vCoSS[1] = ps->screenCoords[mf->v2];
2440                         vCoSS[2] = ps->screenCoords[mf->v3];
2441                         if (mf->v4)
2442                                 vCoSS[3] = ps->screenCoords[ mf->v4 ];
2443
2444                         /* PROJ_FACE_SCALE_SEAM must be slightly less then 1.0f */
2445                         if (is_ortho) {
2446                                 if (mf->v4)     scale_quad(insetCos, vCoSS, PROJ_FACE_SCALE_SEAM);
2447                                 else            scale_tri(insetCos, vCoSS, PROJ_FACE_SCALE_SEAM);
2448                         }
2449                         else {
2450                                 if (mf->v4)     scale_quad(insetCos, vCo, PROJ_FACE_SCALE_SEAM);
2451                                 else            scale_tri(insetCos, vCo, PROJ_FACE_SCALE_SEAM);
2452                         }
2453
2454                         side = 0; /* for triangles this wont need to change */
2455
2456                         for (fidx1 = 0; fidx1 < (mf->v4 ? 4 : 3); fidx1++) {
2457                                 if (mf->v4)             fidx2 = (fidx1==3) ? 0 : fidx1+1; /* next fidx in the face (0,1,2,3) -> (1,2,3,0) */
2458                                 else                    fidx2 = (fidx1==2) ? 0 : fidx1+1; /* next fidx in the face (0,1,2) -> (1,2,0) */
2459
2460                                 if (    (face_seam_flag & (1<<fidx1)) && /* 1<<fidx1 -> PROJ_FACE_SEAM# */
2461                                                 line_clip_rect2f(bucket_bounds, vCoSS[fidx1], vCoSS[fidx2], bucket_clip_edges[0], bucket_clip_edges[1])
2462                                 ) {
2463
2464                                         ftot = len_v2v2(vCoSS[fidx1], vCoSS[fidx2]); /* screenspace edge length */
2465
2466                                         if (ftot > 0.0f) { /* avoid div by zero */
2467                                                 if (mf->v4) {
2468                                                         if (fidx1==2 || fidx2==2)       side= 1;
2469                                                         else                                            side= 0;
2470                                                 }
2471
2472                                                 fac1 = len_v2v2(vCoSS[fidx1], bucket_clip_edges[0]) / ftot;
2473                                                 fac2 = len_v2v2(vCoSS[fidx1], bucket_clip_edges[1]) / ftot;
2474
2475                                                 interp_v2_v2v2(seam_subsection[0], tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2], fac1);
2476                                                 interp_v2_v2v2(seam_subsection[1], tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2], fac2);
2477
2478                                                 interp_v2_v2v2(seam_subsection[2], outset_uv[fidx1], outset_uv[fidx2], fac2);
2479                                                 interp_v2_v2v2(seam_subsection[3], outset_uv[fidx1], outset_uv[fidx2], fac1);
2480
2481                                                 /* if the bucket_clip_edges values Z values was kept we could avoid this
2482                                                  * Inset needs to be added so occlusion tests wont hit adjacent faces */
2483                                                 interp_v3_v3v3(edge_verts_inset_clip[0], insetCos[fidx1], insetCos[fidx2], fac1);
2484                                                 interp_v3_v3v3(edge_verts_inset_clip[1], insetCos[fidx1], insetCos[fidx2], fac2);
2485
2486
2487                                                 if (pixel_bounds_uv(seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3], &bounds_px, ibuf->x, ibuf->y, 1)) {
2488                                                         /* bounds between the seam rect and the uvspace bucket pixels */
2489
2490                                                         has_isect = 0;
2491                                                         for (y = bounds_px.ymin; y < bounds_px.ymax; y++) {
2492                                                                 // uv[1] = (((float)y) + 0.5f) / (float)ibuf->y;
2493                                                                 uv[1] = (float)y / ibuf_yf; /* use offset uvs instead */
2494
2495                                                                 has_x_isect = 0;
2496                                                                 for (x = bounds_px.xmin; x < bounds_px.xmax; x++) {
2497                                                                         //uv[0] = (((float)x) + 0.5f) / (float)ibuf->x;
2498                                                                         uv[0] = (float)x / ibuf_xf; /* use offset uvs instead */
2499
2500                                                                         /* test we're inside uvspace bucket and triangle bounds */
2501                                                                         if (isect_point_quad_v2(uv, seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3])) {
2502
2503                                                                                 /* We need to find the closest point along the face edge,
2504                                                                                  * getting the screen_px_from_*** wont work because our actual location
2505                                                                                  * is not relevent, since we are outside the face, Use VecLerpf to find
2506                                                                                  * our location on the side of the face's UV */
2507                                                                                 /*
2508                                                                                 if (is_ortho)   screen_px_from_ortho(ps, uv, v1co, v2co, v3co, uv1co, uv2co, uv3co, pixelScreenCo);
2509                                                                                 else                                    screen_px_from_persp(ps, uv, v1co, v2co, v3co, uv1co, uv2co, uv3co, pixelScreenCo);
2510                                                                                 */
2511
2512                                                                                 /* Since this is a seam we need to work out where on the line this pixel is */
2513                                                                                 //fac = line_point_factor_v2(uv, uv_seam_quad[0], uv_seam_quad[1]);
2514
2515                                                                                 fac = line_point_factor_v2(uv, seam_subsection[0], seam_subsection[1]);
2516                                                                                 if (fac < 0.0f)         { VECCOPY(pixelScreenCo, edge_verts_inset_clip[0]); }
2517                                                                                 else if (fac > 1.0f)    { VECCOPY(pixelScreenCo, edge_verts_inset_clip[1]); }
2518                                                                                 else                            { interp_v3_v3v3(pixelScreenCo, edge_verts_inset_clip[0], edge_verts_inset_clip[1], fac); }
2519
2520                                                                                 if (!is_ortho) {
2521                                                                                         pixelScreenCo[3] = 1.0f;
2522                                                                                         mul_m4_v4((float(*)[4])ps->projectMat, pixelScreenCo); /* cast because of const */
2523                                                                                         pixelScreenCo[0] = (float)(ps->winx/2.0f)+(ps->winx/2.0f)*pixelScreenCo[0]/pixelScreenCo[3];
2524                                                                                         pixelScreenCo[1] = (float)(ps->winy/2.0f)+(ps->winy/2.0f)*pixelScreenCo[1]/pixelScreenCo[3];
2525                                                                                         pixelScreenCo[2] = pixelScreenCo[2]/pixelScreenCo[3]; /* Use the depth for bucket point occlusion */
2526                                                                                 }
2527
2528                                                                                 if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucketFaceNodes, face_index, pixelScreenCo)) {
2529
2530                                                                                         /* Only bother calculating the weights if we intersect */
2531                                                                                         if (ps->do_mask_normal || ps->dm_mtface_clone) {
2532 #if 1
2533                                                                                                 /* get the UV on the line since we want to copy the pixels from there for bleeding */
2534                                                                                                 float uv_close[2];
2535                                                                                                 float fac= closest_to_line_v2(uv_close, uv, tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2]);
2536                                                                                                 if              (fac < 0.0f) copy_v2_v2(uv_close, tf_uv_pxoffset[fidx1]);
2537                                                                                                 else if (fac > 1.0f) copy_v2_v2(uv_close, tf_uv_pxoffset[fidx2]);
2538
2539                                                                                                 if (side) {
2540                                                                                                         barycentric_weights_v2(tf_uv_pxoffset[0], tf_uv_pxoffset[2], tf_uv_pxoffset[3], uv_close, w);
2541                                                                                                 }
2542                                                                                                 else {
2543                                                                                                         barycentric_weights_v2(tf_uv_pxoffset[0], tf_uv_pxoffset[1], tf_uv_pxoffset[2], uv_close, w);
2544                                                                                                 }
2545 #else                                                                                   /* this is buggy with quads, dont use for now */
2546
2547                                                                                                 /* Cheat, we know where we are along the edge so work out the weights from that */
2548                                                                                                 fac = fac1 + (fac * (fac2-fac1));
2549
2550                                                                                                 w[0]=w[1]=w[2]= 0.0;
2551                                                                                                 if (side) {
2552                                                                                                         w[fidx1?fidx1-1:0] = 1.0f-fac;
2553                                                                                                         w[fidx2?fidx2-1:0] = fac;
2554                                                                                                 }
2555                                                                                                 else {
2556                                                                                                         w[fidx1] = 1.0f-fac;
2557                                                                                                         w[fidx2] = fac;
2558                                                                                                 }
2559 #endif
2560                                                                                         }
2561
2562                                                                                         /* a pitty we need to get the worldspace pixel location here */
2563                                                                                         if(do_clip) {
2564                                                                                                 if (side)       interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v3].co, ps->dm_mvert[mf->v4].co, w);
2565                                                                                                 else            interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, w);
2566
2567                                                                                                 if(ED_view3d_test_clipping(ps->rv3d, wco, 1)) {
2568                                                                                                         continue; /* Watch out that no code below this needs to run */
2569                                                                                                 }
2570                                                                                         }
2571
2572                                                                                         mask = project_paint_uvpixel_mask(ps, face_index, side, w);
2573
2574                                                                                         if (mask > 0.0f) {
2575                                                                                                 BLI_linklist_prepend_arena(
2576                                                                                                         bucketPixelNodes,
2577                                                                                                         project_paint_uvpixel_init(ps, arena, ibuf, x, y, mask, face_index, image_index, pixelScreenCo, side, w),
2578                                                                                                         arena
2579                                                                                                 );
2580                                                                                         }
2581
2582                                                                                 }
2583                                                                         }
2584                                                                         else if (has_x_isect) {
2585                                                                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2586                                                                                 break;
2587                                                                         }
2588                                                                 }
2589
2590 #if 0                                                   /* TODO - investigate why this dosnt work sometimes! it should! */
2591                                                                 /* no intersection for this entire row, after some intersection above means we can quit now */
2592                                                                 if (has_x_isect==0 && has_isect) {
2593                                                                         break;
2594                                                                 }
2595 #endif
2596                                                         }
2597                                                 }
2598                                         }
2599                                 }
2600                         }
2601                 }
2602         }
2603 #endif // PROJ_DEBUG_NOSEAMBLEED
2604 }
2605
2606
2607 /* takes floating point screenspace min/max and returns int min/max to be used as indices for ps->bucketRect, ps->bucketFlags */
2608 static void project_paint_bucket_bounds(const ProjPaintState *ps, const float min[2], const float max[2], int bucketMin[2], int bucketMax[2])
2609 {
2610         /* divide by bucketWidth & bucketHeight so the bounds are offset in bucket grid units */
2611         /* XXX: the offset of 0.5 is always truncated to zero and the offset of 1.5f is always truncated to 1, is this really correct?? - jwilkins */
2612         bucketMin[0] = (int)((int)(((float)(min[0] - ps->screenMin[0]) / ps->screen_width) * ps->buckets_x) + 0.5f); /* these offsets of 0.5 and 1.5 seem odd but they are correct */
2613         bucketMin[1] = (int)((int)(((float)(min[1] - ps->screenMin[1]) / ps->screen_height) * ps->buckets_y) + 0.5f);
2614
2615         bucketMax[0] = (int)((int)(((float)(max[0] - ps->screenMin[0]) / ps->screen_width) * ps->buckets_x) + 1.5f);
2616         bucketMax[1] = (int)((int)(((float)(max[1] - ps->screenMin[1]) / ps->screen_height) * ps->buckets_y) + 1.5f);
2617
2618         /* incase the rect is outside the mesh 2d bounds */
2619         CLAMP(bucketMin[0], 0, ps->buckets_x);
2620         CLAMP(bucketMin[1], 0, ps->buckets_y);
2621
2622         CLAMP(bucketMax[0], 0, ps->buckets_x);
2623         CLAMP(bucketMax[1], 0, ps->buckets_y);
2624 }
2625
2626 /* set bucket_bounds to a screen space-aligned floating point bound-box */
2627 static void project_bucket_bounds(const ProjPaintState *ps, const int bucket_x, const int bucket_y, rctf *bucket_bounds)
2628 {
2629         bucket_bounds->xmin =   ps->screenMin[0]+((bucket_x)*(ps->screen_width / ps->buckets_x));               /* left */
2630         bucket_bounds->xmax =   ps->screenMin[0]+((bucket_x+1)*(ps->screen_width / ps->buckets_x));     /* right */
2631
2632         bucket_bounds->ymin =   ps->screenMin[1]+((bucket_y)*(ps->screen_height / ps->buckets_y));              /* bottom */
2633         bucket_bounds->ymax =   ps->screenMin[1]+((bucket_y+1)*(ps->screen_height  / ps->buckets_y));   /* top */
2634 }
2635
2636 /* Fill this bucket with pixels from the faces that intersect it.
2637  *
2638  * have bucket_bounds as an argument so we don;t need to give bucket_x/y the rect function needs */
2639 static void project_bucket_init(const ProjPaintState *ps, const int thread_index, const int bucket_index, rctf *bucket_bounds)
2640 {
2641         LinkNode *node;
2642         int face_index, image_index=0;
2643         ImBuf *ibuf = NULL;
2644         Image *ima = NULL;
2645         MTFace *tf;
2646
2647         Image *tpage_last = NULL;
2648
2649
2650         if (ps->image_tot==1) {
2651                 /* Simple loop, no context switching */
2652                 ibuf = ps->projImages[0].ibuf;
2653                 ima = ps->projImages[0].ima;
2654
2655                 for (node = ps->bucketFaces[bucket_index]; node; node= node->next) {
2656                         project_paint_face_init(ps, thread_index, bucket_index, GET_INT_FROM_POINTER(node->link), 0, bucket_bounds, ibuf, ima->tpageflag & IMA_CLAMP_U, ima->tpageflag & IMA_CLAMP_V);
2657                 }
2658         }
2659         else {
2660
2661                 /* More complicated loop, switch between images */
2662                 for (node = ps->bucketFaces[bucket_index]; node; node= node->next) {
2663                         face_index = GET_INT_FROM_POINTER(node->link);
2664
2665                         /* Image context switching */
2666                         tf = ps->dm_mtface+face_index;
2667                         if (tpage_last != tf->tpage) {
2668                                 tpage_last = tf->tpage;
2669
2670                                 image_index = -1; /* sanity check */
2671
2672                                 for (image_index=0; image_index < ps->image_tot; image_index++) {
2673                                         if (ps->projImages[image_index].ima == tpage_last) {
2674                                                 ibuf = ps->projImages[image_index].ibuf;
2675                                                 ima = ps->projImages[image_index].ima;
2676                                                 break;
2677                                         }
2678                                 }
2679                         }
2680                         /* context switching done */
2681
2682                         project_paint_face_init(ps, thread_index, bucket_index, face_index, image_index, bucket_bounds, ibuf, ima->tpageflag & IMA_CLAMP_U, ima->tpageflag & IMA_CLAMP_V);
2683                 }
2684         }
2685
2686         ps->bucketFlags[bucket_index] |= PROJ_BUCKET_INIT;
2687 }
2688
2689
2690 /* We want to know if a bucket and a face overlap in screen-space
2691  *
2692  * Note, if this ever returns false positives its not that bad, since a face in the bounding area will have its pixels
2693  * calculated when it might not be needed later, (at the moment at least)
2694  * obviously it shouldn't have bugs though */
2695
2696 static int project_bucket_face_isect(ProjPaintState *ps, int bucket_x, int bucket_y, const MFace *mf)
2697 {
2698         /* TODO - replace this with a tricker method that uses sideofline for all screenCoords's edges against the closest bucket corner */
2699         rctf bucket_bounds;
2700         float p1[2], p2[2], p3[2], p4[2];
2701         float *v, *v1,*v2,*v3,*v4=NULL;
2702         int fidx;
2703
2704         project_bucket_bounds(ps, bucket_x, bucket_y, &bucket_bounds);
2705
2706         /* Is one of the faces verts in the bucket bounds? */
2707
2708         fidx = mf->v4 ? 3:2;
2709         do {
2710                 v = ps->screenCoords[ (*(&mf->v1 + fidx)) ];
2711                 if (BLI_in_rctf(&bucket_bounds, v[0], v[1])) {
2712                         return 1;
2713                 }
2714         } while (fidx--);
2715
2716         v1 = ps->screenCoords[mf->v1];
2717         v2 = ps->screenCoords[mf->v2];
2718         v3 = ps->screenCoords[mf->v3];
2719         if (mf->v4) {
2720                 v4 = ps->screenCoords[mf->v4];
2721         }
2722
2723         p1[0] = bucket_bounds.xmin; p1[1] = bucket_bounds.ymin;
2724         p2[0] = bucket_bounds.xmin;     p2[1] = bucket_bounds.ymax;
2725         p3[0] = bucket_bounds.xmax;     p3[1] = bucket_bounds.ymax;
2726         p4[0] = bucket_bounds.xmax;     p4[1] = bucket_bounds.ymin;
2727
2728         if (mf->v4) {
2729                 if(     isect_point_quad_v2(p1, v1, v2, v3, v4) || isect_point_quad_v2(p2, v1, v2, v3, v4) || isect_point_quad_v2(p3, v1, v2, v3, v4) || isect_point_quad_v2(p4, v1, v2, v3, v4) ||
2730                         /* we can avoid testing v3,v1 because another intersection MUST exist if this intersects */
2731                         (isect_line_line_v2(p1, p2, v1, v2) || isect_line_line_v2(p1, p2, v2, v3) || isect_line_line_v2(p1, p2, v3, v4)) ||
2732                         (isect_line_line_v2(p2, p3, v1, v2) || isect_line_line_v2(p2, p3, v2, v3) || isect_line_line_v2(p2, p3, v3, v4)) ||
2733                         (isect_line_line_v2(p3, p4, v1, v2) || isect_line_line_v2(p3, p4, v2, v3) || isect_line_line_v2(p3, p4, v3, v4)) ||
2734                         (isect_line_line_v2(p4, p1, v1, v2) || isect_line_line_v2(p4, p1, v2, v3) || isect_line_line_v2(p4, p1, v3, v4))
2735                 ) {
2736                         return 1;
2737                 }
2738         }
2739         else {
2740                 if(     isect_point_tri_v2(p1, v1, v2, v3) || isect_point_tri_v2(p2, v1, v2, v3) || isect_point_tri_v2(p3, v1, v2, v3) || isect_point_tri_v2(p4, v1, v2, v3) ||
2741                         /* we can avoid testing v3,v1 because another intersection MUST exist if this intersects */
2742                         (isect_line_line_v2(p1, p2, v1, v2) || isect_line_line_v2(p1, p2, v2, v3)) ||
2743                         (isect_line_line_v2(p2, p3, v1, v2) || isect_line_line_v2(p2, p3, v2, v3)) ||
2744                         (isect_line_line_v2(p3, p4, v1, v2) || isect_line_line_v2(p3, p4, v2, v3)) ||
2745                         (isect_line_line_v2(p4, p1, v1, v2) || isect_line_line_v2(p4, p1, v2, v3))
2746                 ) {
2747                         return 1;
2748                 }
2749         }
2750
2751         return 0;
2752 }
2753
2754 /* Add faces to the bucket but dont initialize its pixels
2755  * TODO - when painting occluded, sort the faces on their min-Z and only add faces that faces that are not occluded */
2756 static void project_paint_delayed_face_init(ProjPaintState *ps, const MFace *mf, const int face_index)
2757 {
2758         float min[2], max[2], *vCoSS;
2759         int bucketMin[2], bucketMax[2]; /* for  ps->bucketRect indexing */
2760         int fidx, bucket_x, bucket_y;
2761         int has_x_isect = -1, has_isect = 0; /* for early loop exit */
2762         MemArena *arena = ps->arena_mt[0]; /* just use the first thread arena since threading has not started yet */
2763
2764         INIT_MINMAX2(min, max);
2765
2766         fidx = mf->v4 ? 3:2;
2767         do {
2768                 vCoSS = ps->screenCoords[ *(&mf->v1 + fidx) ];
2769                 DO_MINMAX2(vCoSS, min, max);
2770         } while (fidx--);
2771
2772         project_paint_bucket_bounds(ps, min, max, bucketMin, bucketMax);
2773
2774         for (bucket_y = bucketMin[1]; bucket_y < bucketMax[1]; bucket_y++) {
2775                 has_x_isect = 0;
2776                 for (bucket_x = bucketMin[0]; bucket_x < bucketMax[0]; bucket_x++) {