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