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