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