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