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