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