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