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