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