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