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