svn merge https://svn.blender.org/svnroot/bf-blender/trunk/blender -r17443:HEAD
[blender.git] / source / blender / src / imagepaint.c
1 /**
2  * $Id$
3  * imagepaint.c
4  *
5  * Functions to paint images in 2D and 3D.
6  * 
7  * ***** BEGIN GPL LICENSE BLOCK *****
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA        02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: some of this file.
27  *
28  * Contributor(s): Jens Ole Wund (bjornmose), Campbell Barton (ideasman42)
29  *
30  * ***** END GPL LICENSE BLOCK *****
31  */
32
33 #include <string.h>
34 #include <stdio.h>
35 #include <math.h>
36
37 #ifdef HAVE_CONFIG_H
38 #include <config.h>
39 #endif
40
41 #include "MEM_guardedalloc.h"
42
43 #ifdef WIN32
44 #include "BLI_winstuff.h"
45 #endif
46 #include "BLI_arithb.h"
47 #include "BLI_blenlib.h"
48 #include "BLI_dynstr.h"
49 #include "BLI_linklist.h"
50 #include "BLI_memarena.h"
51 #include "PIL_time.h"
52 #include "BLI_threads.h"
53
54 #include "IMB_imbuf.h"
55 #include "IMB_imbuf_types.h"
56
57 #include "DNA_brush_types.h"
58 #include "DNA_image_types.h"
59 #include "DNA_mesh_types.h"
60 #include "DNA_meshdata_types.h"
61 #include "DNA_node_types.h"
62 #include "DNA_object_types.h"
63 #include "DNA_scene_types.h"
64 #include "DNA_screen_types.h"
65 #include "DNA_space_types.h"
66 #include "DNA_userdef_types.h"
67 #include "DNA_view3d_types.h"
68 #include "DNA_gpencil_types.h"
69
70 #include "BKE_brush.h"
71 #include "BKE_global.h"
72 #include "BKE_image.h"
73 #include "BKE_main.h"
74 #include "BKE_mesh.h"
75 #include "BKE_node.h"
76 #include "BKE_utildefines.h"
77 #include "BKE_DerivedMesh.h"
78
79 #include "BIF_interface.h"
80 #include "BIF_mywindow.h"
81 #include "BIF_screen.h"
82 #include "BIF_space.h"
83 #include "BIF_toolbox.h"
84
85 #include "BIF_editview.h" /* only for mouse_cursor - could remove this later */
86
87 #include "BSE_drawipo.h"
88 #include "BSE_node.h"
89 #include "BSE_trans_types.h"
90 #include "BSE_view.h"
91
92 #include "BDR_imagepaint.h"
93 #include "BDR_vpaint.h"
94 #include "BDR_gpencil.h"
95 #include "GPU_draw.h"
96
97 #include "GHOST_Types.h"
98
99 #include "blendef.h"
100 #include "butspace.h"
101 #include "mydevice.h"
102
103 /* Defines and Structs */
104
105 #define IMAPAINT_CHAR_TO_FLOAT(c) ((c)/255.0f)
106
107 #define IMAPAINT_FLOAT_RGB_TO_CHAR(c, f) { (c)[0]=FTOCHAR((f)[0]); (c)[1]=FTOCHAR((f)[1]); (c)[2]=FTOCHAR((f)[2]); }
108 #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]); }
109
110 #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]); }
111 #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]); }
112 #define IMAPAINT_FLOAT_RGB_COPY(a, b) VECCOPY(a, b)
113
114 #define IMAPAINT_TILE_BITS                      6
115 #define IMAPAINT_TILE_SIZE                      (1 << IMAPAINT_TILE_BITS)
116 #define IMAPAINT_TILE_NUMBER(size)      (((size)+IMAPAINT_TILE_SIZE-1) >> IMAPAINT_TILE_BITS)
117
118 #define MAXUNDONAME     64
119
120 typedef struct ImagePaintState {
121         Brush *brush;
122         short tool, blend;
123         Image *image;
124         ImBuf *canvas;
125         ImBuf *clonecanvas;
126         short clonefreefloat;
127         char *warnpackedfile;
128         char *warnmultifile;
129
130         /* texture paint only */
131         Object *ob;
132         Mesh *me;
133         int faceindex;
134         float uv[2];
135 } ImagePaintState;
136
137 typedef struct ImagePaintPartialRedraw {
138         int x1, y1, x2, y2;
139         int enabled;
140 } ImagePaintPartialRedraw;
141
142 /* testing options */
143 #define PROJ_BUCKET_DIV 128 /* TODO - test other values, this is a guess, seems ok */
144 #define PROJ_BOUNDBOX_DIV 6 /* TODO - test other values, this is a guess, seems ok */
145 #define PROJ_BOUNDBOX_SQUARED  (PROJ_BOUNDBOX_DIV * PROJ_BOUNDBOX_DIV)
146
147 //#define PROJ_DEBUG_PAINT 1
148 #define PROJ_DEBUG_NOSCANLINE 1
149 //#define PROJ_DEBUG_NOSEAMBLEED 1
150 //#define PROJ_DEBUG_PRINT_THREADS 1
151
152 /* projectFaceSeamFlags options */
153 //#define PROJ_FACE_IGNORE      1<<0    /* When the face is hidden, backfacing or occluded */
154 //#define PROJ_FACE_INIT        1<<1    /* When we have initialized the faces data */
155 #define PROJ_FACE_SEAM1 1<<0    /* If this face has a seam on any of its edges */
156 #define PROJ_FACE_SEAM2 1<<1
157 #define PROJ_FACE_SEAM3 1<<2
158 #define PROJ_FACE_SEAM4 1<<3
159
160 #define PROJ_FACE_NOSEAM1       1<<4
161 #define PROJ_FACE_NOSEAM2       1<<5
162 #define PROJ_FACE_NOSEAM3       1<<6
163 #define PROJ_FACE_NOSEAM4       1<<7
164
165 #define PROJ_BUCKET_NULL                0
166 #define PROJ_BUCKET_INIT                1<<0
167 // #define PROJ_BUCKET_CLONE_INIT       1<<1
168
169 /* only for readability */
170 #define PROJ_BUCKET_LEFT        0
171 #define PROJ_BUCKET_RIGHT       1
172 #define PROJ_BUCKET_BOTTOM      2
173 #define PROJ_BUCKET_TOP         3
174
175 typedef struct ProjectPaintImage {
176         Image *ima;
177         ImBuf *ibuf;
178         ImagePaintPartialRedraw *partRedrawRect;
179         struct UndoTile **undoRect; /* only used to build undo tiles after painting */
180         int touch;
181 } ProjectPaintImage;
182
183 typedef struct ProjectPaintState {
184         Brush *brush;
185         short tool, blend;
186         Object *ob;
187         /* end similarities with ImagePaintState */
188         
189         DerivedMesh    *dm;
190         int                     dm_totface;
191         int                     dm_totvert;
192         
193         MVert              *dm_mvert;
194         MFace              *dm_mface;
195         MTFace             *dm_mtface;
196         
197         /* projection painting only */
198         MemArena *arena;                        /* use for alocating many pixel structs and link-lists */
199         MemArena *arena_mt[BLENDER_MAX_THREADS];                /* Same as above but use for multithreading */
200         LinkNode **bucketRect;                          /* screen sized 2D array, each pixel has a linked list of ProjectPixel's */
201         LinkNode **bucketFaces;                         /* bucketRect alligned array linkList of faces overlapping each bucket */
202         char *bucketFlags;                                      /* store if the bucks have been initialized  */
203 #ifndef PROJ_DEBUG_NOSEAMBLEED
204         char *faceSeamFlags;                            /* store info about faces, if they are initialized etc*/
205         float (*faceSeamUVs)[4][2];                     /* expanded UVs for faces to use as seams */
206         LinkNode **vertFaces;                           /* Only needed for when seam_bleed_px is enabled, use to find UV seams */
207 #endif
208         int buckets_x;                                          /* The size of the bucket grid, the grid span's screen_min/screen_max so you can paint outsize the screen or with 2 brushes at once */
209         int buckets_y;
210         
211         ProjectPaintImage *projImages;
212         
213         int image_tot;                          /* size of projectImages array */
214         
215         float (*screenCoords)[4];       /* verts projected into floating point screen space */
216         
217         /* options for projection painting */
218         short do_occlude;                       /* Use raytraced occlusion? - ortherwise will paint right through to the back*/
219         short do_backfacecull;  /* ignore faces with normals pointing away, skips a lot of raycasts if your normals are correctly flipped */
220         short is_ortho;
221 #ifndef PROJ_DEBUG_NOSEAMBLEED
222         float seam_bleed_px;
223 #endif
224         /* clone vars */
225         float clone_offset[2];
226         
227         
228         float projectMat[4][4];         /* Projection matrix, use for getting screen coords */
229         float viewMat[4][4];
230         float viewDir[3];                       /* View vector, use for do_backfacecull and for ray casting with an ortho viewport  */
231         
232         float screen_min[2];                    /* 2D bounds for mesh verts on the screen's plane (screenspace) */
233         float screen_max[2]; 
234         float screen_width;                     /* Calculated from screen_min & screen_max */
235         float screen_height;
236         
237         /* threads */
238         int thread_tot;
239         int bucket_min[2];
240         int bucket_max[2];
241         int context_bucket_x, context_bucket_y; /* must lock threads while accessing these */
242 } ProjectPaintState;
243
244 #ifndef PROJ_DEBUG_NOSCANLINE
245 typedef struct ProjectScanline {
246         int v[3]; /* verts for this scanline, 0,1,2 or 0,2,3 */
247         float x_limits[2]; /* UV min|max for this scanline */
248 } ProjectScanline;
249 #endif
250
251 typedef struct ProjectPixel {
252         float projCo2D[2]; /* the floating point screen projection of this pixel */
253         char origColor[4];
254         short x_px, y_px;
255         void *pixel;
256         short image_index; /* if anyone wants to paint onto more then 32000 images they can bite me */
257         short bb_cell_index;
258 } ProjectPixel;
259
260 typedef struct ProjectPixelClone {
261         struct ProjectPixel __pp;
262         char clonepx[4];
263 } ProjectPixelClone;
264
265 typedef struct ProjectPixelCloneFloat {
266         struct ProjectPixel __pp;
267         float clonepx[4];
268 } ProjectPixelCloneFloat;
269
270 /* Finish projection painting structs */
271
272
273 typedef struct UndoTile {
274         struct UndoTile *next, *prev;
275         ID id;
276         void *rect;
277         int x, y;
278 } UndoTile;
279
280 typedef struct UndoElem {
281         struct UndoElem *next, *prev;
282         char name[MAXUNDONAME];
283         unsigned long undosize;
284
285         ImBuf *ibuf;
286         ListBase tiles;
287 } UndoElem;
288
289 static ListBase undobase = {NULL, NULL};
290 static UndoElem *curundo = NULL;
291 static ImagePaintPartialRedraw imapaintpartial = {0, 0, 0, 0, 0};
292
293 /* UNDO */
294
295 /* internal functions */
296
297 static void undo_copy_tile(UndoTile *tile, ImBuf *tmpibuf, ImBuf *ibuf, int restore)
298 {
299         /* copy or swap contents of tile->rect and region in ibuf->rect */
300         IMB_rectcpy(tmpibuf, ibuf, 0, 0, tile->x*IMAPAINT_TILE_SIZE,
301                 tile->y*IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE);
302
303         if(ibuf->rect_float) {
304                 SWAP(void*, tmpibuf->rect_float, tile->rect);
305         } else {
306                 SWAP(void*, tmpibuf->rect, tile->rect);
307         }
308         
309         if(restore)
310                 IMB_rectcpy(ibuf, tmpibuf, tile->x*IMAPAINT_TILE_SIZE,
311                         tile->y*IMAPAINT_TILE_SIZE, 0, 0, IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE);
312 }
313
314 static UndoTile *undo_init_tile(ID *id, ImBuf *ibuf, ImBuf **tmpibuf, int x_tile, int y_tile)
315 {
316         UndoTile *tile;
317         int allocsize;
318         
319         if (*tmpibuf==NULL)
320                 *tmpibuf = IMB_allocImBuf(IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, 32, IB_rectfloat|IB_rect, 0);
321         
322         tile= MEM_callocN(sizeof(UndoTile), "ImaUndoTile");
323         tile->id= *id;
324         tile->x= x_tile;
325         tile->y= y_tile;
326
327         allocsize= IMAPAINT_TILE_SIZE*IMAPAINT_TILE_SIZE*4;
328         allocsize *= (ibuf->rect_float)? sizeof(float): sizeof(char);
329         tile->rect= MEM_mapallocN(allocsize, "ImaUndoRect");
330
331         undo_copy_tile(tile, *tmpibuf, ibuf, 0);
332         curundo->undosize += allocsize;
333
334         BLI_addtail(&curundo->tiles, tile);
335         
336         return tile;
337 }
338
339 static void undo_restore(UndoElem *undo)
340 {
341         Image *ima = NULL;
342         ImBuf *ibuf, *tmpibuf;
343         UndoTile *tile;
344
345         if(!undo)
346                 return;
347
348         tmpibuf= IMB_allocImBuf(IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, 32,
349                                 IB_rectfloat|IB_rect, 0);
350         
351         for(tile=undo->tiles.first; tile; tile=tile->next) {
352                 /* find image based on name, pointer becomes invalid with global undo */
353                 if(ima && strcmp(tile->id.name, ima->id.name)==0);
354                 else {
355                         for(ima=G.main->image.first; ima; ima=ima->id.next)
356                                 if(strcmp(tile->id.name, ima->id.name)==0)
357                                         break;
358                 }
359
360                 ibuf= BKE_image_get_ibuf(ima, NULL);
361
362                 if (!ima || !ibuf || !(ibuf->rect || ibuf->rect_float))
363                         continue;
364
365                 undo_copy_tile(tile, tmpibuf, ibuf, 1);
366
367                 GPU_free_image(ima); /* force OpenGL reload */
368                 if(ibuf->rect_float)
369                         imb_freerectImBuf(ibuf); /* force recreate of char rect */
370         }
371
372         IMB_freeImBuf(tmpibuf);
373 }
374
375 static void undo_free(UndoElem *undo)
376 {
377         UndoTile *tile;
378
379         for(tile=undo->tiles.first; tile; tile=tile->next)
380                 MEM_freeN(tile->rect);
381         BLI_freelistN(&undo->tiles);
382 }
383
384 static void undo_imagepaint_push_begin(char *name)
385 {
386         UndoElem *uel;
387         int nr;
388         
389         /* Undo push is split up in begin and end, the reason is that as painting
390          * happens more tiles are added to the list, and at the very end we know
391          * how much memory the undo used to remove old undo elements */
392
393         /* remove all undos after (also when curundo==NULL) */
394         while(undobase.last != curundo) {
395                 uel= undobase.last;
396                 undo_free(uel);
397                 BLI_freelinkN(&undobase, uel);
398         }
399         
400         /* make new */
401         curundo= uel= MEM_callocN(sizeof(UndoElem), "undo file");
402         BLI_addtail(&undobase, uel);
403
404         /* name can be a dynamic string */
405         strncpy(uel->name, name, MAXUNDONAME-1);
406         
407         /* limit amount to the maximum amount*/
408         nr= 0;
409         uel= undobase.last;
410         while(uel) {
411                 nr++;
412                 if(nr==U.undosteps) break;
413                 uel= uel->prev;
414         }
415         if(uel) {
416                 while(undobase.first!=uel) {
417                         UndoElem *first= undobase.first;
418                         undo_free(first);
419                         BLI_freelinkN(&undobase, first);
420                 }
421         }
422 }
423
424 static void undo_imagepaint_push_end()
425 {
426         UndoElem *uel;
427         unsigned long totmem, maxmem;
428
429         if(U.undomemory != 0) {
430                 /* limit to maximum memory (afterwards, we can't know in advance) */
431                 totmem= 0;
432                 maxmem= ((unsigned long)U.undomemory)*1024*1024;
433
434                 uel= undobase.last;
435                 while(uel) {
436                         totmem+= uel->undosize;
437                         if(totmem>maxmem) break;
438                         uel= uel->prev;
439                 }
440
441                 if(uel) {
442                         while(undobase.first!=uel) {
443                                 UndoElem *first= undobase.first;
444                                 undo_free(first);
445                                 BLI_freelinkN(&undobase, first);
446                         }
447                 }
448         }
449 }
450
451
452 static int project_paint_BucketOffset(ProjectPaintState *ps, float projCo2D[2])
453 {
454         /* If we were not dealing with screenspace 2D coords we could simple do...
455          * ps->bucketRect[x + (y*ps->buckets_y)] */
456         
457         /* please explain?
458          * projCo2D[0] - ps->screen_min[0]      : zero origin
459          * ... / ps->screen_width                               : range from 0.0 to 1.0
460          * ... * ps->buckets_x          : use as a bucket index
461          *
462          * Second multiplication does similar but for vertical offset
463          */
464         return  (       (int)(( (projCo2D[0] - ps->screen_min[0]) / ps->screen_width)  * ps->buckets_x)) + 
465                 (       (       (int)(( (projCo2D[1] - ps->screen_min[1])  / ps->screen_height) * ps->buckets_y)) * ps->buckets_x );
466 }
467
468 static int project_paint_BucketOffsetSafe(ProjectPaintState *ps, float projCo2D[2])
469 {
470         int bucket_index = project_paint_BucketOffset(ps, projCo2D);
471         
472         if (bucket_index < 0 || bucket_index >= ps->buckets_x*ps->buckets_y) {  
473                 return -1;
474         } else {
475                 return bucket_index;
476         }
477 }
478
479 /* The point must be inside the triangle */
480 static void BarycentricWeightsSimple2f(float v1[2], float v2[2], float v3[2], float pt[2], float w[3]) {
481         float wtot;
482         w[0] = AreaF2Dfl(v2, v3, pt);
483         w[1] = AreaF2Dfl(v3, v1, pt);
484         w[2] = AreaF2Dfl(v1, v2, pt);
485         wtot = w[0]+w[1]+w[2];
486         if (wtot > 0.0) { /* just incase */
487                 w[0]/=wtot;
488                 w[1]/=wtot;
489                 w[2]/=wtot;
490         } else {
491                 w[0] = w[1] = w[2] = 1.0/3.0; /* dummy values for zero area face */
492         }
493 }
494
495 /* also works for points outside the triangle */
496 #define SIDE_OF_LINE(pa,pb,pp)  ((pa[0]-pp[0])*(pb[1]-pp[1]))-((pb[0]-pp[0])*(pa[1]-pp[1]))
497 static void BarycentricWeights2f(float v1[2], float v2[2], float v3[2], float pt[2], float w[3]) {
498         float wtot = AreaF2Dfl(v1, v2, v3);
499         if (wtot > 0.0) {
500                 w[0] = AreaF2Dfl(v2, v3, pt);
501                 w[1] = AreaF2Dfl(v3, v1, pt);
502                 w[2] = AreaF2Dfl(v1, v2, pt);
503                 
504                 /* negate weights when 'pt' is on the outer side of the the triangles edge */
505                 if ((SIDE_OF_LINE(v2,v3, pt)>0.0) != (SIDE_OF_LINE(v2,v3, v1)>0.0))     w[0]/= -wtot;
506                 else                                                                                                                            w[0]/=  wtot;
507
508                 if ((SIDE_OF_LINE(v3,v1, pt)>0.0) != (SIDE_OF_LINE(v3,v1, v2)>0.0))     w[1]/= -wtot;
509                 else                                                                                                                            w[1]/=  wtot;
510
511                 if ((SIDE_OF_LINE(v1,v2, pt)>0.0) != (SIDE_OF_LINE(v1,v2, v3)>0.0))     w[2]/= -wtot;
512                 else                                                                                                                            w[2]/=  wtot;
513         } else {
514                 w[0] = w[1] = w[2] = 1.0/3.0; /* dummy values for zero area face */
515         }
516 }
517
518 /* still use 2D X,Y space but this works for verts transformed by a perspective matrix, using their 4th component as a weight */
519
520 static void BarycentricWeightsPersp2f(float v1[4], float v2[4], float v3[4], float pt[2], float w[3]) {
521         float persp_tot;
522         BarycentricWeights2f(v1,v2,v3,pt,w);
523         
524         w[0] /= v1[3];
525         w[1] /= v2[3];
526         w[2] /= v3[3];
527         
528         persp_tot = w[0]+w[1]+w[2];
529         
530         w[0] /= persp_tot;
531         w[1] /= persp_tot;
532         w[2] /= persp_tot;
533 }
534
535 static void BarycentricWeightsSimplePersp2f(float v1[4], float v2[4], float v3[4], float pt[2], float w[3]) {
536         float persp_tot;
537         BarycentricWeightsSimple2f(v1,v2,v3,pt,w);
538         
539         w[0] /= v1[3];
540         w[1] /= v2[3];
541         w[2] /= v3[3];
542         
543         persp_tot = w[0]+w[1]+w[2];
544         
545         w[0] /= persp_tot;
546         w[1] /= persp_tot;
547         w[2] /= persp_tot;
548 }
549
550 static float tri_depth_2d(float v1[3], float v2[3], float v3[3], float pt[2], float w[3])
551 {
552         BarycentricWeightsSimple2f(v1,v2,v3,pt,w);
553         return (v1[2]*w[0]) + (v2[2]*w[1]) + (v3[2]*w[2]);
554 }
555
556
557 /* return the topmost face  in screen coords index or -1
558  * bucket_index can be -1 if we dont know it to begin with */
559 static int project_paint_PickFace(ProjectPaintState *ps, float pt[2], float w[3], int *side) {
560         LinkNode *node;
561         float w_tmp[3];
562         float *v1, *v2, *v3, *v4;
563         int bucket_index;
564         int face_index;
565         int best_side = -1;
566         int best_face_index = -1;
567         float z_depth_best = MAXFLOAT, z_depth;
568         MFace *mf;
569         
570         bucket_index = project_paint_BucketOffsetSafe(ps, pt);
571         if (bucket_index==-1)
572                 return -1;
573         
574         node = ps->bucketFaces[bucket_index];
575         
576         /* we could return 0 for 1 face buckets, as long as this function assumes
577          * that the point its testing is only every originated from an existing face */
578         
579         while (node) {
580                 face_index = (int)node->link;
581                 mf = ps->dm_mface + face_index;
582                 
583                 v1 = ps->screenCoords[mf->v1];
584                 v2 = ps->screenCoords[mf->v2];
585                 v3 = ps->screenCoords[mf->v3];
586                 
587                 if ( IsectPT2Df(pt, v1, v2, v3) ) {
588                         z_depth = tri_depth_2d(v1,v2,v3,pt,w_tmp);
589                         if (z_depth < z_depth_best) {
590                                 best_face_index = face_index;
591                                 best_side = 0;
592                                 z_depth_best = z_depth;
593                                 VECCOPY(w, w_tmp);
594                         }
595                 } else if (mf->v4) {
596                         v4 = ps->screenCoords[mf->v4];
597                         
598                         if ( IsectPT2Df(pt, v1, v3, v4) ) {
599                                 z_depth = tri_depth_2d(v1,v3,v4,pt,w_tmp);
600                                 if (z_depth < z_depth_best) {
601                                         best_face_index = face_index;
602                                         best_side = 1;
603                                         z_depth_best = z_depth;
604                                         VECCOPY(w, w_tmp);
605                                 }
606                         }
607                 }
608                 
609                 node = node->next;
610         }
611         
612         *side = best_side;
613         return best_face_index; /* will be -1 or a valid face */
614 }
615
616 /**************************************************************************
617 *                            INTERPOLATIONS 
618 *
619 * Reference and docs:
620 * http://wiki.blender.org/index.php/User:Damiles#Interpolations_Algorithms
621 ***************************************************************************/
622
623 /* BICUBIC Interpolation functions */
624 /*  More info: http://wiki.blender.org/index.php/User:Damiles#Bicubic_pixel_interpolation
625 */
626 /* function assumes out to be zero'ed, only does RGBA */
627 static float P(float k){
628         return (float)(1.0f/6.0f)*( pow( MAX2(k+2.0f,0) , 3.0f ) - 4.0f * pow( MAX2(k+1.0f,0) , 3.0f ) + 6.0f * pow( MAX2(k,0) , 3.0f ) - 4.0f * pow( MAX2(k-1.0f,0) , 3.0f));
629 }
630
631 static void bicubic_interpolation_px(ImBuf *in, float x, float y, float rgba_fp[4], char rgba[4])
632 {
633         int i,j,n,m,x1,y1;
634         unsigned char *dataI;
635         float a,b,w,wx,wy[4], outR,outG,outB,outA,*dataF;
636         int do_rect=0, do_float=0;
637
638         if (in == NULL) return;
639         if (in->rect == NULL && in->rect_float == NULL) return;
640
641         if (in->rect_float)     do_float = 1;
642         else                            do_rect = 1;
643         
644         i= (int)floor(x);
645         j= (int)floor(y);
646         a= x - i;
647         b= y - j;
648
649         outR= 0.0f;
650         outG= 0.0f;
651         outB= 0.0f;
652         outA= 0.0f;
653         
654         /* avoid calling multiple times */
655         wy[0] = P(b-(-1));
656         wy[1] = P(b-  0);
657         wy[2] = P(b-  1);
658         wy[3] = P(b-  2);
659         
660         for(n= -1; n<= 2; n++){
661                 x1= i+n;
662                 if (x1>0 && x1 < in->x) {
663                         wx = P(n-a);
664                         for(m= -1; m<= 2; m++){
665                                 y1= j+m;
666                                 if (y1>0 && y1<in->y) {
667                                         /* normally we could do this */
668                                         /* w = P(n-a) * P(b-m); */
669                                         /* except that would call P() 16 times per pixel therefor pow() 64 times, better precalc these */
670                                         w = wx * wy[m+1];
671                                         
672                                         if (do_float) {
673                                                 dataF= in->rect_float + in->x * y1 * 4 + 4*x1;
674                                                 outR+= dataF[0] * w;
675                                                 outG+= dataF[1] * w;
676                                                 outB+= dataF[2] * w;
677                                                 outA+= dataF[3] * w;
678                                         }
679                                         if (do_rect) {
680                                                 dataI= (unsigned char*)in->rect + in->x * y1 * 4 + 4*x1;
681                                                 outR+= dataI[0] * w;
682                                                 outG+= dataI[1] * w;
683                                                 outB+= dataI[2] * w;
684                                                 outA+= dataI[3] * w;
685                                         }
686                                 }
687                         }
688                 }
689         }
690         if (do_rect) {
691                 rgba[0]= (int)outR;
692                 rgba[1]= (int)outG;
693                 rgba[2]= (int)outB;
694                 rgba[3]= (int)outA;
695         }
696         if (do_float) {
697                 rgba_fp[0]= outR;
698                 rgba_fp[1]= outG;
699                 rgba_fp[2]= outB;
700                 rgba_fp[3]= outA;
701         }
702 }
703
704 /* bucket_index is optional, since in some cases we know it */
705 /* TODO FLOAT */ /* add a function that does this for float buffers */
706 static int project_paint_PickColor(ProjectPaintState *ps, float pt[2], float *rgba_fp, char *rgba, int interp)
707 {
708         float w[3], uv[2];
709         int side;
710         int face_index;
711         MTFace *tf;
712         ImBuf *ibuf;
713         int xi,yi;
714         
715         
716         face_index = project_paint_PickFace(ps,pt,w, &side);
717         
718         if (face_index == -1)
719                 return 0;
720         
721         tf = ps->dm_mtface + face_index;
722         
723         if (side==0) {
724                 uv[0] = tf->uv[0][0]*w[0] + tf->uv[1][0]*w[1] + tf->uv[2][0]*w[2];
725                 uv[1] = tf->uv[0][1]*w[0] + tf->uv[1][1]*w[1] + tf->uv[2][1]*w[2];
726         } else { /* QUAD */
727                 uv[0] = tf->uv[0][0]*w[0] + tf->uv[2][0]*w[1] + tf->uv[3][0]*w[2];
728                 uv[1] = tf->uv[0][1]*w[0] + tf->uv[2][1]*w[1] + tf->uv[3][1]*w[2];
729         }
730         
731         ibuf = BKE_image_get_ibuf((Image *)tf->tpage, NULL); /* TODO - this may be slow */
732         
733
734         
735         if (interp) {
736                 float x,y;
737                 /* use */
738                 x = (float)fmod(uv[0], 1.0);
739                 y = (float)fmod(uv[1], 1.0);
740                 
741                 if (x < 0.0) x += 1.0;
742                 if (y < 0.0) y += 1.0;
743                 
744                 x *= ibuf->x;
745                 y *= ibuf->y;
746                 
747                 if (ibuf->rect_float) {
748                         if (rgba_fp) {
749                                 bicubic_interpolation_px(ibuf, x, y, rgba_fp, NULL);
750                         } else {
751                                 float rgba_tmp_fp[4];
752                                 bicubic_interpolation_px(ibuf, x, y, rgba_tmp_fp, NULL);
753                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(rgba, rgba_tmp_fp);
754                         }
755                 } else {
756                         if (rgba) {
757                                 bicubic_interpolation_px(ibuf, x, y, NULL, rgba);
758                         } else {
759                                 char rgba_tmp[4];
760                                 bicubic_interpolation_px(ibuf, x, y, NULL, rgba_tmp);
761                                 IMAPAINT_CHAR_RGBA_TO_FLOAT( rgba_fp,  rgba_tmp);
762                         }
763                 }
764         } else {
765                 xi = uv[0]*ibuf->x;
766                 yi = uv[1]*ibuf->y;
767                 
768                 //if (xi<0 || xi>=ibuf->x  ||  yi<0 || yi>=ibuf->y) return 0;
769                 
770                 /* wrap */
771                 xi = ((int)(uv[0]*ibuf->x)) % ibuf->x;
772                 if (xi<0) xi += ibuf->x;
773                 yi = ((int)(uv[1]*ibuf->y)) % ibuf->y;
774                 if (yi<0) yi += ibuf->y;
775                 
776                 
777                 if (rgba) {
778                         if (ibuf->rect_float) {
779                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(rgba, ((( float * ) ibuf->rect_float) + (( xi + yi * ibuf->x ) * 4)));
780                         } else {
781                                 *((unsigned int *)rgba) = *(unsigned int *) ((( char * ) ibuf->rect) + (( xi + yi * ibuf->x ) * 4));
782                         }
783                 }
784                 
785                 if (rgba_fp) {
786                         if (ibuf->rect_float) {
787                                 QUATCOPY(rgba_fp, ((( float * ) ibuf->rect_float) + (( xi + yi * ibuf->x ) * 4)));
788                         } else {
789                                 IMAPAINT_CHAR_RGBA_TO_FLOAT( rgba_fp,  ((( char * ) ibuf->rect) + (( xi + yi * ibuf->x ) * 4)));
790                         }
791                 }
792         }
793         return 1;
794 }
795
796 /* return...
797  * 0    : no occlusion
798  * -1   : no occlusion but 2D intersection is true (avoid testing the other half of a quad)
799  * 1    : occluded */
800
801 static int project_paint_PointOcclude(float pt[3], float v1[3], float v2[3], float v3[3])
802 {
803         /* if all are behind us, return false */
804         if(v1[2] > pt[2] && v2[2] > pt[2] && v3[2] > pt[2])
805                 return 0;
806                 
807         /* do a 2D point in try intersection */
808         if ( !IsectPT2Df(pt, v1, v2, v3) )
809                 return 0; /* we know there is  */
810         
811         /* From here on we know there IS an intersection */
812         
813         /* if ALL of the verts are infront of us then we know it intersects ? */
814         if(     v1[2] < pt[2] && v2[2] < pt[2] && v3[2] < pt[2]) {
815                 return 1;
816         } else {
817                 float w[3];
818                 /* we intersect? - find the exact depth at the point of intersection */
819                 if (tri_depth_2d(v1,v2,v3,pt,w) < pt[2]) {
820                         return 1; /* This point is occluded by another face */
821                 }
822         }
823         return -1;
824 }
825
826
827 /* check, pixelScreenCo must be in screenspace, its Z-Depth only needs to be used for comparison */
828 static int project_bucket_point_occluded(ProjectPaintState *ps, int bucket_index, int orig_face, float pixelScreenCo[4])
829 {
830         LinkNode *node = ps->bucketFaces[bucket_index];
831         MFace *mf;
832         int face_index;
833         int isect_ret;
834         
835         /* we could return 0 for 1 face buckets, as long as this function assumes
836          * that the point its testing is only every originated from an existing face */
837         
838         while (node) {
839                 face_index = (int)node->link;
840                 
841                 if (orig_face != face_index) {
842                         
843                         mf = ps->dm_mface + face_index;
844                         
845                         isect_ret = project_paint_PointOcclude(
846                                         pixelScreenCo,
847                                         ps->screenCoords[mf->v1],
848                                         ps->screenCoords[mf->v2],
849                                         ps->screenCoords[mf->v3]);
850                         
851                         /* Note, if isect_ret==-1 then we dont want to test the other side of the quad */
852                         if (isect_ret==0 && mf->v4) {
853                                 isect_ret = project_paint_PointOcclude(
854                                                 pixelScreenCo,
855                                                 ps->screenCoords[mf->v1],
856                                                 ps->screenCoords[mf->v3],
857                                                 ps->screenCoords[mf->v4]);
858                         }
859                         
860                         if (isect_ret==1) {
861 #if 0
862                                 /* Cheap Optimization!
863                                  * This function runs for every UV Screen pixel,
864                                  * therefor swapping the swapping the faces for this buckets list helps because
865                                  * the next ~5 to ~200 runs will can hit the first face each time. */
866                                 if (ps->bucketFaces[bucket_index] != node) {
867                                         /* SWAP(void *, ps->bucketFaces[bucket_index]->link, node->link); */
868                                         
869                                         /* dont need to use swap since we alredy have face_index */
870                                         node->link = ps->bucketFaces[bucket_index]->link; /* move the value item to the current value */
871                                         ps->bucketFaces[bucket_index]->link = (void *) face_index;
872                                         
873                                         /*printf("swapping %d %d\n", (int)node->link, face_index);*/
874                                 } /*else {
875                                         printf("first hit %d\n", face_index);
876                                 }*/
877 #endif
878                                 return 1; 
879                         }
880                 }
881                 node = node->next;
882         }
883         
884         return 0;
885 }
886
887 /* basic line intersection, could move to arithb.c, 2 points with a horiz line
888  * 1 for an intersection, 2 if the first point is aligned, 3 if the second point is aligned */
889 #define ISECT_TRUE 1
890 #define ISECT_TRUE_P1 2
891 #define ISECT_TRUE_P2 3
892 static int line_isect_y(float p1[2], float p2[2], float y_level, float *x_isect)
893 {
894         if (y_level==p1[1]) {
895                 *x_isect = p1[0];
896                 return ISECT_TRUE_P1;
897         }
898         if (y_level==p2[1]) {
899                 *x_isect = p2[0];
900                 return ISECT_TRUE_P2;
901         }
902         
903         if (p1[1] > y_level && p2[1] < y_level) {
904                 *x_isect = (p2[0]*(p1[1]-y_level) + p1[0]*(y_level-p2[1])) / (p1[1]-p2[1]);
905                 return ISECT_TRUE;
906         } else if (p1[1] < y_level && p2[1] > y_level) {
907                 *x_isect = (p2[0]*(y_level-p1[1]) + p1[0]*(p2[1]-y_level)) / (p2[1]-p1[1]);
908                 return ISECT_TRUE;
909         } else {
910                 return 0;
911         }
912 }
913
914 static int line_isect_x(float p1[2], float p2[2], float x_level, float *y_isect)
915 {
916         if (x_level==p1[0]) {
917                 *y_isect = p1[1];
918                 return ISECT_TRUE_P1;
919         }
920         if (x_level==p2[0]) {
921                 *y_isect = p2[1];
922                 return ISECT_TRUE_P2;
923         }
924         
925         if (p1[0] > x_level && p2[0] < x_level) {
926                 *y_isect = (p2[1]*(p1[0]-x_level) + p1[1]*(x_level-p2[0])) / (p1[0]-p2[0]);
927                 return ISECT_TRUE;
928         } else if (p1[0] < x_level && p2[0] > x_level) {
929                 *y_isect = (p2[1]*(x_level-p1[0]) + p1[1]*(p2[0]-x_level)) / (p2[0]-p1[0]);
930                 return ISECT_TRUE;
931         } else {
932                 return 0;
933         }
934 }
935
936 #ifndef PROJ_DEBUG_NOSCANLINE
937 static int project_face_scanline(ProjectScanline *sc, float y_level, float v1[2], float v2[2], float v3[2], float v4[2])
938 {       
939         /* Create a scanlines for the face at this Y level 
940          * triangles will only ever have 1 scanline, quads may have 2 */
941         int totscanlines = 0;
942         short i1=0,i2=0,i3=0;
943         
944         if (v4) { /* This is a quad?*/
945                 int i4=0, i_mid=0;
946                 float xi1, xi2, xi3, xi4, xi_mid;
947                                 
948                 i1 = line_isect_y(v1, v2, y_level, &xi1);
949                 if (i1 != ISECT_TRUE_P2) /* rare cases we could be on the line, in these cases we dont want to intersect with the same point twice */
950                         i2 = line_isect_y(v2, v3, y_level, &xi2);
951                 
952                 if (i1 && i2) { /* both the first 2 edges intersect, this means the second half of the quad wont intersect */
953                         sc->v[0] = 0;
954                         sc->v[1] = 1;
955                         sc->v[2] = 2;
956                         sc->x_limits[0] = MIN2(xi1, xi2);
957                         sc->x_limits[1] = MAX2(xi1, xi2);
958                         totscanlines = 1;
959                 } else {
960                         if (i2 != ISECT_TRUE_P2) 
961                                 i3 = line_isect_y(v3, v4, y_level, &xi3);
962                         if (i1 != ISECT_TRUE_P1 && i3 != ISECT_TRUE_P2) 
963                                 i4 = line_isect_y(v4, v1, y_level, &xi4);
964                         
965                         if (i3 && i4) { /* second 2 edges only intersect, same as above */
966                                 sc->v[0] = 0;
967                                 sc->v[1] = 2;
968                                 sc->v[2] = 3;
969                                 sc->x_limits[0] = MIN2(xi3, xi4);
970                                 sc->x_limits[1] = MAX2(xi3, xi4);
971                                 totscanlines = 1;
972                         } else {
973                                 /* OK - we have a not-so-simple case, both sides of the quad intersect.
974                                  * Will need to have 2 scanlines */
975                                 if ((i1||i2) && (i3||i4)) {
976                                         i_mid = line_isect_y(v1, v3, y_level, &xi_mid);
977                                         /* it would be very rare this would be false, but possible */
978                                         sc->v[0] = 0;
979                                         sc->v[1] = 1;
980                                         sc->v[2] = 2;
981                                         sc->x_limits[0] = MIN2((i1?xi1:xi2), xi_mid);
982                                         sc->x_limits[1] = MAX2((i1?xi1:xi2), xi_mid);
983                                         
984                                         sc++;
985                                         sc->v[0] = 0;
986                                         sc->v[1] = 2;
987                                         sc->v[2] = 3;
988                                         sc->x_limits[0] = MIN2((i3?xi3:xi4), xi_mid);
989                                         sc->x_limits[1PROJ_DEBUG_NOSEAMBLEED] = MAX2((i3?xi3:xi4), xi_mid);
990                                         
991                                         totscanlines = 2;
992                                 }
993                         }
994                 }
995         } else { /* triangle */
996                 int i = 0;
997                 
998                 i1 = line_isect_y(v1, v2, y_level, &sc->x_limits[0]);
999                 if (i1) i++;
1000                 
1001                 if (i1 != ISECT_TRUE_P2) {
1002                         i2 = line_isect_y(v2, v3, y_level, &sc->x_limits[i]);
1003                         if (i2) i++;
1004                 }
1005                 
1006                 /* if the triangle intersects then the first 2 lines must */
1007                 if (i!=0) {
1008                         if (i!=2) {
1009                                 /* if we are here then this really should not fail since 2 edges MUST intersect  */
1010                                 if (i1 != ISECT_TRUE_P1 && i2 != ISECT_TRUE_P2) {
1011                                         i3 = line_isect_y(v3, v1, y_level, &sc->x_limits[i]);
1012                                         if (i3) i++;
1013                                         
1014                                 }
1015                         }
1016                         
1017                         if (i==2) {
1018                                 if (sc->x_limits[0] > sc->x_limits[1]) {
1019                                         SWAP(float, sc->x_limits[0], sc->x_limits[1]);
1020                                 }
1021                                 sc->v[0] = 0;
1022                                 sc->v[1] = 1;
1023                                 sc->v[2] = 2;
1024                                 totscanlines = 1;
1025                         }
1026                 }
1027         }
1028         /* done setting up scanlines */
1029         return totscanlines;
1030 }
1031 #endif // PROJ_DEBUG_NOSCANLINE
1032
1033 static int cmp_uv(float vec2a[2], float vec2b[2])
1034 {
1035         return ((fabs(vec2a[0]-vec2b[0]) < 0.0001) && (fabs(vec2a[1]-vec2b[1]) < 0.0001)) ? 1:0;
1036 }
1037
1038
1039 /* return zero if there is no area in the returned rectangle */
1040 static int uv_image_rect(float uv1[2], float uv2[2], float uv3[2], float uv4[2], int min_px[2], int max_px[2], int x_px, int y_px, int is_quad)
1041 {
1042         float min_uv[2], max_uv[2]; /* UV bounds */
1043         
1044         INIT_MINMAX2(min_uv, max_uv);
1045         
1046         DO_MINMAX2(uv1, min_uv, max_uv);
1047         DO_MINMAX2(uv2, min_uv, max_uv);
1048         DO_MINMAX2(uv3, min_uv, max_uv);
1049         if (is_quad)
1050                 DO_MINMAX2(uv4, min_uv, max_uv);
1051         
1052         min_px[0] = (int)(x_px * min_uv[0]);
1053         min_px[1] = (int)(y_px * min_uv[1]);
1054         
1055         max_px[0] = (int)(x_px * max_uv[0]) +1;
1056         max_px[1] = (int)(y_px * max_uv[1]) +1;
1057         
1058         /*printf("%d %d %d %d \n", min_px[0], min_px[1], max_px[0], max_px[1]);*/
1059         
1060         /* face uses no UV area when quantized to pixels? */
1061         return (min_px[0] == max_px[0] || min_px[1] == max_px[1]) ? 0 : 1;
1062 }
1063
1064 #ifndef PROJ_DEBUG_NOSEAMBLEED
1065 /* TODO - set the seam flag on the other face to avoid double lookups */
1066 static int check_seam(ProjectPaintState *ps, int orig_face, int orig_i1_fidx, int orig_i2_fidx, int *other_face, int *orig_fidx)
1067 {
1068         LinkNode *node;
1069         int face_index;
1070         int i, i1, i2;
1071         int i1_fidx = -1, i2_fidx = -1; /* indexi in face */
1072         MFace *orig_mf, *mf;
1073         MTFace *orig_tf, *tf;
1074         
1075         orig_mf = ps->dm_mface + orig_face;
1076         orig_tf = ps->dm_mtface + orig_face;
1077         
1078         /* vert indicies from face vert order indicies */
1079         i1 = (*(&orig_mf->v1 + orig_i1_fidx));
1080         i2 = (*(&orig_mf->v1 + orig_i2_fidx));
1081         
1082         for (node = ps->vertFaces[i1]; node; node = node->next) {
1083                 face_index = (int)node->link;
1084                 if (face_index != orig_face) {
1085                         mf = ps->dm_mface + face_index;
1086                         
1087                         /* We need to know the order of the verts in the adjacent face 
1088                          * set the i1_fidx and i2_fidx to (0,1,2,3) */
1089                         i = mf->v4 ? 3:2;
1090                         do {
1091                                 if (i1 == (*(&mf->v1 + i))) {
1092                                         i1_fidx = i;
1093                                 } else if (i2 == (*(&mf->v1 + i))) {
1094                                         i2_fidx = i;
1095                                 }
1096                                 
1097                         } while (i--);
1098                         
1099                         if (i2_fidx != -1) {
1100                                 /* This IS an adjacent face!, now lets check if the UVs are ok */
1101                                 
1102
1103                                 
1104                                 tf = ps->dm_mtface + face_index;
1105                                 
1106                                 /* set up the other face */
1107                                 *other_face = face_index;
1108                                 *orig_fidx = (i1_fidx < i2_fidx) ? i1_fidx : i2_fidx;
1109                                 
1110                                 /* first test if they have the same image */
1111                                 if (    (orig_tf->tpage == tf->tpage) &&
1112                                                 cmp_uv(orig_tf->uv[orig_i1_fidx], tf->uv[i1_fidx]) &&
1113                                                 cmp_uv(orig_tf->uv[orig_i2_fidx], tf->uv[i2_fidx]) )
1114                                 {
1115                                         // printf("SEAM (NONE)\n");
1116                                         return 0;
1117                                         
1118                                 } else {
1119                                         // printf("SEAM (UV GAP)\n");
1120                                         return 1;
1121                                 }
1122                         }
1123                 }
1124         }
1125         // printf("SEAM (NO FACE)\n");
1126         *other_face = -1;
1127         return 1;
1128 }
1129
1130
1131 static float angleToLength(float angle)
1132 {
1133         float x,y, fac;
1134         
1135         // Alredy accounted for
1136         if (angle < 0.000001)
1137                 return 1.0;
1138         
1139         angle = (2.0*M_PI/360.0) * angle;
1140         x = cos(angle);
1141         y = sin(angle);
1142         
1143         // print "YX", x,y
1144         // 0 d is hoz to the right.
1145         // 90d is vert upward.
1146         fac = 1.0/x;
1147         x = x*fac;
1148         y = y*fac;
1149         return sqrt((x*x)+(y*y));
1150 }
1151
1152 /* takes a faces UV's and assigns outset coords to outset_uv */
1153 static void uv_image_outset(float (*orig_uv)[2], float (*outset_uv)[2], float scaler, int x_px, int y_px, int is_quad)
1154 {
1155         float a1,a2,a3,a4=0.0;
1156         float puv[4][2]; /* pixelspace uv's */
1157         float no1[2], no2[2], no3[2], no4[2]; /* normals */
1158         float dir1[2], dir2[2], dir3[2], dir4[2];
1159         
1160         /* make UV's in pixel space so we can */
1161         puv[0][0] = orig_uv[0][0] * x_px;
1162         puv[0][1] = orig_uv[0][1] * y_px;
1163         
1164         puv[1][0] = orig_uv[1][0] * x_px;
1165         puv[1][1] = orig_uv[1][1] * y_px;
1166         
1167         puv[2][0] = orig_uv[2][0] * x_px;
1168         puv[2][1] = orig_uv[2][1] * y_px;
1169         
1170         if (is_quad) {
1171                 puv[3][0] = orig_uv[3][0] * x_px;
1172                 puv[3][1] = orig_uv[3][1] * y_px;
1173         }
1174         
1175         /* face edge directions */
1176         Vec2Subf(dir1, puv[1], puv[0]);
1177         Vec2Subf(dir2, puv[2], puv[1]);
1178         Normalize2(dir1);
1179         Normalize2(dir2);
1180         
1181         if (is_quad) {
1182                 Vec2Subf(dir3, puv[3], puv[2]);
1183                 Vec2Subf(dir4, puv[0], puv[3]);
1184                 Normalize2(dir3);
1185                 Normalize2(dir4);
1186         } else {
1187                 Vec2Subf(dir3, puv[0], puv[2]);
1188                 Normalize2(dir3);
1189         }
1190         
1191         if (is_quad) {
1192                 a1 = NormalizedVecAngle2_2D(dir4, dir1);
1193                 a2 = NormalizedVecAngle2_2D(dir1, dir2);
1194                 a3 = NormalizedVecAngle2_2D(dir2, dir3);
1195                 a4 = NormalizedVecAngle2_2D(dir3, dir4);
1196         } else {
1197                 a1 = NormalizedVecAngle2_2D(dir3, dir1);
1198                 a2 = NormalizedVecAngle2_2D(dir1, dir2);
1199                 a3 = NormalizedVecAngle2_2D(dir2, dir3);
1200         }
1201         
1202         a1 = angleToLength(a1);
1203         a2 = angleToLength(a2);
1204         a3 = angleToLength(a3);
1205         if (is_quad)
1206                 a4 = angleToLength(a4);
1207         
1208         if (is_quad) {
1209                 Vec2Subf(no1, dir4, dir1);
1210                 Vec2Subf(no2, dir1, dir2);
1211                 Vec2Subf(no3, dir2, dir3);
1212                 Vec2Subf(no4, dir3, dir4);
1213                 Normalize2(no1);
1214                 Normalize2(no2);
1215                 Normalize2(no3);
1216                 Normalize2(no4);
1217                 Vec2Mulf(no1, a1*scaler);
1218                 Vec2Mulf(no2, a2*scaler);
1219                 Vec2Mulf(no3, a3*scaler);
1220                 Vec2Mulf(no4, a4*scaler);
1221                 Vec2Addf(outset_uv[0], puv[0], no1);
1222                 Vec2Addf(outset_uv[1], puv[1], no2);
1223                 Vec2Addf(outset_uv[2], puv[2], no3);
1224                 Vec2Addf(outset_uv[3], puv[3], no4);
1225                 outset_uv[0][0] /= x_px;
1226                 outset_uv[0][1] /= y_px;
1227                 
1228                 outset_uv[1][0] /= x_px;
1229                 outset_uv[1][1] /= y_px;
1230                 
1231                 outset_uv[2][0] /= x_px;
1232                 outset_uv[2][1] /= y_px;
1233                 
1234                 outset_uv[3][0] /= x_px;
1235                 outset_uv[3][1] /= y_px;
1236         } else {
1237                 Vec2Subf(no1, dir3, dir1);
1238                 Vec2Subf(no2, dir1, dir2);
1239                 Vec2Subf(no3, dir2, dir3);
1240                 Normalize2(no1);
1241                 Normalize2(no2);
1242                 Normalize2(no3);
1243                 Vec2Mulf(no1, a1*scaler);
1244                 Vec2Mulf(no2, a2*scaler);
1245                 Vec2Mulf(no3, a3*scaler);
1246                 Vec2Addf(outset_uv[0], puv[0], no1);
1247                 Vec2Addf(outset_uv[1], puv[1], no2);
1248                 Vec2Addf(outset_uv[2], puv[2], no3);
1249                 outset_uv[0][0] /= x_px;
1250                 outset_uv[0][1] /= y_px;
1251                 
1252                 outset_uv[1][0] /= x_px;
1253                 outset_uv[1][1] /= y_px;
1254                 
1255                 outset_uv[2][0] /= x_px;
1256                 outset_uv[2][1] /= y_px;
1257         }
1258 }
1259
1260 /* 
1261  * Be tricky with flags, first 4 bits are PROJ_FACE_SEAM1 to 4, last 4 bits are PROJ_FACE_NOSEAM1 to 4
1262  * 1<<i - where i is (0-3) 
1263  * 
1264  * If we're multithreadng, make sure threads are locked when this is called
1265  */
1266 static void project_face_seams_init(ProjectPaintState *ps, int face_index, int is_quad)
1267 {
1268         int other_face, other_fidx; /* vars for the other face, we also set its flag */
1269         int fidx1, fidx2;
1270         
1271         fidx1 = is_quad ? 3 : 2;
1272         do {
1273                 if (is_quad)
1274                         fidx2 = (fidx1==3) ? 0 : fidx1+1; /* next fidx in the face (0,1,2,3) -> (1,2,3,0) */
1275                 else
1276                         fidx2 = (fidx1==2) ? 0 : fidx1+1; /* next fidx in the face (0,1,2) -> (1,2,0) */
1277                 
1278                 if ((ps->faceSeamFlags[face_index] & (1<<fidx1|16<<fidx1)) == 0) {
1279                         if (check_seam(ps, face_index, fidx1,fidx2, &other_face, &other_fidx)) {
1280                                 ps->faceSeamFlags[face_index] |= 1<<fidx1;
1281                                 if (other_face != -1)
1282                                         ps->faceSeamFlags[other_face] |= 1<<other_fidx;
1283                         } else {
1284                                 ps->faceSeamFlags[face_index] |= 16<<fidx1;
1285                                 if (other_face != -1)
1286                                         ps->faceSeamFlags[other_face] |= 16<<other_fidx; /* second 4 bits for disabled */
1287                         }
1288                 }
1289         } while (fidx1--);
1290 }
1291 #endif // PROJ_DEBUG_NOSEAMBLEED
1292
1293
1294 /* TODO - move to arithb.c */
1295
1296 /* little sister we only need to know lambda */
1297 static float lambda_cp_line2(float p[2], float l1[2], float l2[2])
1298 {
1299         float h[2],u[2];
1300         Vec2Subf(u, l2, l1);
1301         Vec2Subf(h, p, l1);
1302         return(Inp2f(u,h)/Inp2f(u,u));
1303 }
1304
1305 static void screen_px_from_ortho(
1306                 ProjectPaintState *ps, float uv[2],
1307                 float v1co[3], float v2co[3], float v3co[3], /* Screenspace coords */
1308                 float uv1co[2], float uv2co[2], float uv3co[2],
1309                 float pixelScreenCo[4] )
1310 {
1311         float w[3];
1312         BarycentricWeightsSimple2f(uv1co,uv2co,uv3co,uv,w);
1313         pixelScreenCo[0] = v1co[0]*w[0] + v2co[0]*w[1] + v3co[0]*w[2];
1314         pixelScreenCo[1] = v1co[1]*w[0] + v2co[1]*w[1] + v3co[1]*w[2];
1315         pixelScreenCo[2] = v1co[2]*w[0] + v2co[2]*w[1] + v3co[2]*w[2];  
1316 }
1317
1318 static void screen_px_from_persp(
1319                 ProjectPaintState *ps, float uv[2],
1320                 float v1co[3], float v2co[3], float v3co[3], /* Worldspace coords */
1321                 float uv1co[2], float uv2co[2], float uv3co[2],
1322                 float pixelScreenCo[4])
1323 {
1324         float w[3];
1325         BarycentricWeightsSimple2f(uv1co,uv2co,uv3co,uv,w);
1326         pixelScreenCo[0] = v1co[0]*w[0] + v2co[0]*w[1] + v3co[0]*w[2];
1327         pixelScreenCo[1] = v1co[1]*w[0] + v2co[1]*w[1] + v3co[1]*w[2];
1328         pixelScreenCo[2] = v1co[2]*w[0] + v2co[2]*w[1] + v3co[2]*w[2];
1329         pixelScreenCo[3] = 1.0;
1330         
1331         Mat4MulVec4fl(ps->projectMat, pixelScreenCo);
1332         
1333         // if( pixelScreenCo[3] > 0.001 ) { ??? TODO
1334         /* screen space, not clamped */
1335         pixelScreenCo[0] = (float)(curarea->winx/2.0)+(curarea->winx/2.0)*pixelScreenCo[0]/pixelScreenCo[3];    
1336         pixelScreenCo[1] = (float)(curarea->winy/2.0)+(curarea->winy/2.0)*pixelScreenCo[1]/pixelScreenCo[3];
1337         pixelScreenCo[2] = pixelScreenCo[2]/pixelScreenCo[3]; /* Use the depth for bucket point occlusion */
1338 }
1339
1340
1341 /* Only run this function once for new ProjectPixelClone's */
1342 #define pixel_size 4
1343
1344 static void project_paint_uvpixel_init(ProjectPaintState *ps, int thread_index, ImBuf *ibuf, short x, short y, int bucket_index, int face_index, int image_index, float pixelScreenCo[4])
1345 {
1346         ProjectPixel *projPixel;
1347         short size;
1348         
1349         // printf("adding px (%d %d), (%f %f)\n", x,y,uv[0],uv[1]);
1350         
1351         
1352         /* Use screen_min to make (0,0) the bottom left of the bounds 
1353          * Then this can be used to index the bucket array */
1354         
1355         /* Is this UV visible from the view? - raytrace */
1356         /* project_paint_PickFace is less complex, use for testing */
1357         //if (project_paint_PickFace(ps, pixelScreenCo, w, &side) == face_index) {
1358         if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucket_index, face_index, pixelScreenCo)) {
1359                 
1360                 /* wrap pixel location */
1361                 // printf(" %d %d", x, y);
1362                 x = x % ibuf->x;
1363                 if (x<0) x += ibuf->x;
1364                 y = y % ibuf->y;
1365                 if (y<0) y += ibuf->y;
1366                 // printf(" %d %d\n", x, y);
1367                 
1368                 
1369                 if (ps->tool==PAINT_TOOL_CLONE) {
1370                         if (ibuf->rect_float) {
1371                                 size = sizeof(ProjectPixelCloneFloat);
1372                         } else {
1373                                 size = sizeof(ProjectPixelClone);
1374                         }
1375                 } else if (ps->tool==PAINT_TOOL_SMEAR) {
1376                         size = sizeof(ProjectPixelClone);
1377                 } else {
1378                         size = sizeof(ProjectPixel);
1379                 }
1380                 
1381                 projPixel = (ProjectPixel *)BLI_memarena_alloc(ps->arena_mt[thread_index], size);
1382                 
1383                 if (ibuf->rect_float) {
1384                         projPixel->pixel = (void *) ((( float * ) ibuf->rect_float) + (( x + y * ibuf->x ) * pixel_size));
1385                         /* TODO float support for origColor */
1386                 } else {
1387                         projPixel->pixel = (void *) ((( char * ) ibuf->rect) + (( x + y * ibuf->x ) * pixel_size));
1388                         *((unsigned int *)projPixel->origColor) = *((unsigned int *)projPixel->pixel);
1389                 }
1390                 
1391                 VECCOPY2D(projPixel->projCo2D, pixelScreenCo);
1392                 
1393                 projPixel->x_px = x;
1394                 projPixel->y_px = y;
1395                 
1396                 /* which bounding box cell are we in? */
1397                 projPixel->bb_cell_index = ((int)((((float)x)/((float)ibuf->x)) * PROJ_BOUNDBOX_DIV)) + ((int)((((float)y)/((float)ibuf->y)) * PROJ_BOUNDBOX_DIV)) * PROJ_BOUNDBOX_DIV ;
1398                 
1399                 /* done with view3d_project_float inline */
1400                 if (ps->tool==PAINT_TOOL_CLONE) {
1401                         float co[2];
1402                         
1403                         /* Initialize clone pixels - note that this is a bit of a waste since some of these are being indirectly initialized :/ */
1404                         /* TODO - possibly only run this for directly ativated buckets when cloning */
1405                         Vec2Subf(co, projPixel->projCo2D, ps->clone_offset);
1406                         
1407                         /* no need to initialize the bucket, we're only checking buckets faces and for this
1408                          * the faces are alredy initialized in project_paint_delayed_face_init(...) */
1409                         if (ibuf->rect_float) {
1410                                 if (!project_paint_PickColor(ps, co, ((ProjectPixelCloneFloat *)projPixel)->clonepx, NULL, 1)) {
1411                                         ((ProjectPixelCloneFloat *)projPixel)->clonepx[3] = 0; /* zero alpha - ignore */
1412                                 }
1413                         } else {
1414                                 if (!project_paint_PickColor(ps, co, NULL, ((ProjectPixelClone *)projPixel)->clonepx, 1)) {
1415                                         ((ProjectPixelClone *)projPixel)->clonepx[3] = 0; /* zero alpha - ignore */
1416                                 }
1417                         }
1418                 }
1419                 
1420                 /* screenspace unclamped */
1421                 
1422 #ifdef PROJ_DEBUG_PAINT
1423                 if (ibuf->rect_float)   ((float *)projPixel->pixel)[1] = 0;
1424                 else                                    ((char *)projPixel->pixel)[1] = 0;
1425 #endif
1426                 projPixel->image_index = image_index;
1427                 
1428                 BLI_linklist_prepend_arena(
1429                         &ps->bucketRect[ bucket_index ],
1430                         projPixel,
1431                         ps->arena_mt[thread_index]
1432                 );
1433         }
1434 }
1435
1436 static void uvpixel_rect_intersect(int min_target[2], int max_target[2],  int min_a[2], int max_a[2],  int min_b[2], int max_b[2])
1437 {
1438         min_target[0] = MAX2(min_a[0], min_b[0]);
1439         min_target[1] = MAX2(min_a[1], min_b[1]);
1440         
1441         max_target[0] = MIN2(max_a[0], max_b[0]);
1442         max_target[1] = MIN2(max_a[1], max_b[1]);
1443 }
1444
1445 static int line_clip_rect2f(float rect[4], float l1[2], float l2[2], float l1_clip[2], float l2_clip[2])
1446 {
1447         float isect;
1448         short ok1 = 0;
1449         short ok2 = 0;
1450         
1451         /* are either of the points inside the rectangle ? */
1452         if (    l1[1] >= rect[PROJ_BUCKET_BOTTOM] &&    l1[1] <= rect[PROJ_BUCKET_TOP] &&
1453                         l1[0] >= rect[PROJ_BUCKET_LEFT] &&              l1[0] <= rect[PROJ_BUCKET_RIGHT]
1454         ) {
1455                 VECCOPY2D(l1_clip, l1);
1456                 ok1 = 1;
1457         }
1458         
1459         if (    l2[1] >= rect[PROJ_BUCKET_BOTTOM] &&    l2[1] <= rect[PROJ_BUCKET_TOP] &&
1460                         l2[0] >= rect[PROJ_BUCKET_LEFT] &&              l2[0] <= rect[PROJ_BUCKET_RIGHT]
1461         ) {
1462                 VECCOPY2D(l2_clip, l2);
1463                 ok2 = 1;
1464         }
1465         
1466         /* line inside rect */
1467         if (ok1 && ok2) {
1468                 return 1;
1469         }
1470         
1471         /* top/bottom */
1472         if (line_isect_y(l1,l2, rect[PROJ_BUCKET_BOTTOM], &isect) && (isect > rect[PROJ_BUCKET_LEFT]) && (isect < rect[PROJ_BUCKET_RIGHT])) {
1473                 if (l1[1] < l2[1]) { /* line 1 is outside */
1474                         l1_clip[0] = isect;
1475                         l1_clip[1] = rect[PROJ_BUCKET_BOTTOM];
1476                         ok1 = 1;
1477                 } else {
1478                         l2_clip[0] = isect;
1479                         l2_clip[1] = rect[PROJ_BUCKET_BOTTOM];
1480                         ok2 = 2;
1481                 }
1482         }
1483         if (line_isect_y(l1,l2, rect[PROJ_BUCKET_TOP], &isect) && (isect > rect[PROJ_BUCKET_LEFT]) && (isect < rect[PROJ_BUCKET_RIGHT])) {
1484                 if (l1[1] > l2[1]) { /* line 1 is outside */
1485                         l1_clip[0] = isect;
1486                         l1_clip[1] = rect[PROJ_BUCKET_TOP];
1487                         ok1 = 1;
1488                 } else {
1489                         l2_clip[0] = isect;
1490                         l2_clip[1] = rect[PROJ_BUCKET_TOP];
1491                         ok2 = 2;
1492                 }
1493         }
1494         
1495         /* left/right */
1496         if (line_isect_x(l1,l2, rect[PROJ_BUCKET_LEFT], &isect) && (isect > rect[PROJ_BUCKET_BOTTOM]) && (isect < rect[PROJ_BUCKET_TOP])) {
1497                 if (l1[0] < l2[0]) { /* line 1 is outside */
1498                         l1_clip[0] = rect[PROJ_BUCKET_LEFT];
1499                         l1_clip[1] = isect;
1500                         ok1 = 1;
1501                 } else {
1502                         l2_clip[0] = rect[PROJ_BUCKET_LEFT];
1503                         l2_clip[1] = isect;
1504                         ok2 = 2;
1505                 }
1506         }
1507         if (line_isect_x(l1,l2, rect[PROJ_BUCKET_RIGHT], &isect) && (isect > rect[PROJ_BUCKET_BOTTOM]) && (isect < rect[PROJ_BUCKET_TOP])) {
1508                 if (l1[0] > l2[0]) { /* line 1 is outside */
1509                         l1_clip[0] = rect[PROJ_BUCKET_RIGHT];
1510                         l1_clip[1] = isect;
1511                         ok1 = 1;
1512                 } else {
1513                         l2_clip[0] = rect[PROJ_BUCKET_RIGHT];
1514                         l2_clip[1] = isect;
1515                         ok2 = 2;
1516                 }
1517         }
1518         
1519         if (ok1 && ok2) {
1520                 return 1;
1521         } else {
1522                 return 0;
1523         }
1524 }
1525
1526
1527
1528 /* scale the quad & tri about its center
1529  * scaling by 0.99999 is used for getting fake UV pixel coords that are on the
1530  * edge of the face but slightly inside it occlusion tests dont return hits on adjacent faces */
1531 static void scale_quad(float *origCos[4], float insetCos[4][3], float inset)
1532 {
1533         float cent[3];
1534         cent[0] = (origCos[0][0] + origCos[1][0] + origCos[2][0] + origCos[3][0]) / 4.0;
1535         cent[1] = (origCos[0][1] + origCos[1][1] + origCos[2][1] + origCos[3][1]) / 4.0;
1536         cent[2] = (origCos[0][2] + origCos[1][2] + origCos[2][2] + origCos[3][2]) / 4.0;
1537         
1538         VecSubf(insetCos[0], origCos[0], cent);
1539         VecSubf(insetCos[1], origCos[1], cent);
1540         VecSubf(insetCos[2], origCos[2], cent);
1541         VecSubf(insetCos[3], origCos[3], cent);
1542         
1543         VecMulf(insetCos[0], inset);
1544         VecMulf(insetCos[1], inset);
1545         VecMulf(insetCos[2], inset);
1546         VecMulf(insetCos[3], inset);
1547         
1548         VecAddf(insetCos[0], insetCos[0], cent);
1549         VecAddf(insetCos[1], insetCos[1], cent);
1550         VecAddf(insetCos[2], insetCos[2], cent);
1551         VecAddf(insetCos[3], insetCos[3], cent);
1552 }
1553
1554 static void scale_tri(float *origCos[4], float insetCos[4][3], float inset)
1555 {
1556         float cent[3];
1557         cent[0] = (origCos[0][0] + origCos[1][0] + origCos[2][0]) / 3.0;
1558         cent[1] = (origCos[0][1] + origCos[1][1] + origCos[2][1]) / 3.0;
1559         cent[2] = (origCos[0][2] + origCos[1][2] + origCos[2][2]) / 3.0;
1560         
1561         VecSubf(insetCos[0], origCos[0], cent);
1562         VecSubf(insetCos[1], origCos[1], cent);
1563         VecSubf(insetCos[2], origCos[2], cent);
1564         
1565         VecMulf(insetCos[0], inset);
1566         VecMulf(insetCos[1], inset);
1567         VecMulf(insetCos[2], inset);
1568         
1569         VecAddf(insetCos[0], insetCos[0], cent);
1570         VecAddf(insetCos[1], insetCos[1], cent);
1571         VecAddf(insetCos[2], insetCos[2], cent);
1572 }
1573
1574 static void rect_to_uvspace(
1575                 ProjectPaintState *ps, float bucket_bounds[4],
1576                 float *v1coSS, float *v2coSS, float *v3coSS,
1577                 float *uv1co, float *uv2co, float *uv3co,
1578                 float bucket_bounds_uv[4][2]
1579         )
1580 {
1581         float uv[2];
1582         float w[3];
1583         
1584         /* get the UV space bounding box */
1585         uv[0] = bucket_bounds[PROJ_BUCKET_RIGHT];
1586         uv[1] = bucket_bounds[PROJ_BUCKET_BOTTOM];
1587         if (ps->is_ortho)       BarycentricWeights2f(v1coSS, v2coSS, v3coSS, uv, w);    
1588         else                                    BarycentricWeightsPersp2f(v1coSS, v2coSS, v3coSS, uv, w);       
1589         bucket_bounds_uv[0][0] = uv1co[0]*w[0] + uv2co[0]*w[1] + uv3co[0]*w[2];
1590         bucket_bounds_uv[0][1] = uv1co[1]*w[0] + uv2co[1]*w[1] + uv3co[1]*w[2];
1591         
1592         //uv[0] = bucket_bounds[PROJ_BUCKET_RIGHT]; // set above
1593         uv[1] = bucket_bounds[PROJ_BUCKET_TOP];
1594         if (ps->is_ortho)       BarycentricWeights2f(v1coSS, v2coSS, v3coSS, uv, w);
1595         else                                    BarycentricWeightsPersp2f(v1coSS, v2coSS, v3coSS, uv, w);
1596         bucket_bounds_uv[1][0] = uv1co[0]*w[0] + uv2co[0]*w[1] + uv3co[0]*w[2];
1597         bucket_bounds_uv[1][1] = uv1co[1]*w[0] + uv2co[1]*w[1] + uv3co[1]*w[2];
1598         
1599         
1600         uv[0] = bucket_bounds[PROJ_BUCKET_LEFT];
1601         //uv[1] = bucket_bounds[PROJ_BUCKET_TOP]; // set above
1602         if (ps->is_ortho)       BarycentricWeights2f(v1coSS, v2coSS, v3coSS, uv, w);
1603         else                    BarycentricWeightsPersp2f(v1coSS, v2coSS, v3coSS, uv, w);
1604         bucket_bounds_uv[2][0] = uv1co[0]*w[0] + uv2co[0]*w[1] + uv3co[0]*w[2];
1605         bucket_bounds_uv[2][1] = uv1co[1]*w[0] + uv2co[1]*w[1] + uv3co[1]*w[2];
1606         
1607         //uv[0] = bucket_bounds[PROJ_BUCKET_LEFT]; // set above
1608         uv[1] = bucket_bounds[PROJ_BUCKET_BOTTOM];
1609         if (ps->is_ortho)       BarycentricWeights2f(v1coSS, v2coSS, v3coSS, uv, w);
1610         else                                    BarycentricWeightsPersp2f(v1coSS, v2coSS, v3coSS, uv, w);
1611         bucket_bounds_uv[3][0] = uv1co[0]*w[0] + uv2co[0]*w[1] + uv3co[0]*w[2];
1612         bucket_bounds_uv[3][1] = uv1co[1]*w[0] + uv2co[1]*w[1] + uv3co[1]*w[2]; 
1613 }
1614
1615
1616 /* initialize pixels from this face where it intersects with the bucket_index, initialize pixels for removing seams */
1617 static void project_paint_face_init(ProjectPaintState *ps, int thread_index, int bucket_index, int face_index, int image_index, float bucket_bounds[4], ImBuf *ibuf)
1618 {
1619         /* Projection vars, to get the 3D locations into screen space  */
1620         
1621         MFace *mf = ps->dm_mface + face_index;
1622         MTFace *tf = ps->dm_mtface + face_index;
1623         
1624         /* UV/pixel seeking data */
1625         int x; /* Image X-Pixel */
1626         int y;/* Image Y-Pixel */
1627         float uv[2]; /* Image floating point UV - same as x,y but from 0.0-1.0 */
1628         
1629         int min_px[2], max_px[2]; /* UV Bounds converted to int's for pixel */
1630         int min_px_tf[2], max_px_tf[2]; /* UV Bounds converted to int's for pixel */
1631         int min_px_bucket[2], max_px_bucket[2]; /* Bucket Bounds converted to int's for pixel */
1632         float *v1coSS, *v2coSS, *v3coSS; /* vert co screen-space, these will be assigned to mf->v1,2,3 or mf->v1,3,4 */
1633         
1634         float *vCo[4]; /* vertex screenspace coords */
1635         
1636         float *uv1co, *uv2co, *uv3co; /* for convenience only, these will be assigned to tf->uv[0],1,2 or tf->uv[0],2,3 */
1637         float pixelScreenCo[4];
1638         int i;
1639         
1640         /* vars for getting uvspace bounds */
1641         float bucket_bounds_uv[4][2]; /* bucket bounds in UV space so we can init pixels only for this face,  */
1642         
1643         float tf_uv_pxoffset[4][2]; /* bucket bounds in UV space so we can init pixels only for this face,  */
1644         float xhalfpx, yhalfpx;
1645         float ibuf_xf = ibuf->x, ibuf_yf = ibuf->y;
1646         
1647         int i1,i2,i3;
1648         
1649         /* scanlines since quads can have 2 triangles intersecting the same vertical location */
1650 #ifndef PROJ_DEBUG_NOSCANLINE 
1651         ProjectScanline scanlines[2];
1652         ProjectScanline *sc;
1653         int totscanlines; /* can only be 1 or 2, oh well */
1654 #endif
1655
1656         vCo[0] = ps->dm_mvert[ (*(&mf->v1    )) ].co;
1657         vCo[1] = ps->dm_mvert[ (*(&mf->v1 + 1)) ].co;
1658         vCo[2] = ps->dm_mvert[ (*(&mf->v1 + 2)) ].co;
1659         
1660         
1661         
1662         xhalfpx = 0.5 / ibuf_xf;
1663         yhalfpx = 0.5 / ibuf_yf;
1664         
1665         tf_uv_pxoffset[0][0] = tf->uv[0][0] - xhalfpx;
1666         tf_uv_pxoffset[0][1] = tf->uv[0][1] - yhalfpx;
1667
1668         tf_uv_pxoffset[1][0] = tf->uv[1][0] - xhalfpx;
1669         tf_uv_pxoffset[1][1] = tf->uv[1][1] - yhalfpx;
1670         
1671         tf_uv_pxoffset[2][0] = tf->uv[2][0] - xhalfpx;
1672         tf_uv_pxoffset[2][1] = tf->uv[2][1] - yhalfpx;  
1673         
1674         if (mf->v4) {
1675                 vCo[3] = ps->dm_mvert[ (*(&mf->v1 + 3)) ].co;
1676                 
1677                 tf_uv_pxoffset[3][0] = tf->uv[3][0] - xhalfpx;
1678                 tf_uv_pxoffset[3][1] = tf->uv[3][1] - yhalfpx;
1679                 i = 1;
1680         } else {
1681                 i = 0;
1682         }
1683         
1684         do {
1685                 if (i==1) {
1686                         i1=0; i2=2; i3=3;
1687                 } else {
1688                         i1=0; i2=1; i3=2;
1689                 }
1690                 
1691                 uv1co = tf_uv_pxoffset[i1]; // was tf->uv[i1];
1692                 uv2co = tf_uv_pxoffset[i2]; // was tf->uv[i2];
1693                 uv3co = tf_uv_pxoffset[i3]; // was tf->uv[i3];
1694
1695                 v1coSS = ps->screenCoords[ (*(&mf->v1 + i1)) ];
1696                 v2coSS = ps->screenCoords[ (*(&mf->v1 + i2)) ];
1697                 v3coSS = ps->screenCoords[ (*(&mf->v1 + i3)) ];
1698                 
1699                 rect_to_uvspace(ps, bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, bucket_bounds_uv);
1700                 
1701                 //printf("Bounds: %f | %f | %f | %f\n", bucket_bounds[0], bucket_bounds[1], bucket_bounds[2], bucket_bounds[3]);
1702
1703                 if (    uv_image_rect(uv1co, uv2co, uv3co, NULL, min_px_tf, max_px_tf, ibuf->x, ibuf->y, 0) && 
1704                                 uv_image_rect(bucket_bounds_uv[0], bucket_bounds_uv[1], bucket_bounds_uv[2], bucket_bounds_uv[3], min_px_bucket, max_px_bucket, ibuf->x, ibuf->y, 1) )
1705                 {
1706                         
1707                         uvpixel_rect_intersect(min_px, max_px, min_px_bucket, max_px_bucket, min_px_tf, max_px_tf);
1708                         
1709                         /* clip face and */
1710
1711
1712                         for (y = min_px[1]; y < max_px[1]; y++) {
1713                                 //uv[1] = (((float)y) + 0.5) / (float)ibuf->y;
1714                                 uv[1] = (float)y / ibuf_yf; /* use pixel offset UV coords instead */
1715                                 for (x = min_px[0]; x < max_px[0]; x++) {
1716                                         //uv[0] = (((float)x) + 0.5) / ibuf->x;
1717                                         uv[0] = (float)x / ibuf_xf; /* use pixel offset UV coords instead */
1718                                         
1719                                         /* test we're inside uvspace bucket and triangle bounds */
1720                                         if (    IsectPQ2Df(uv, bucket_bounds_uv[0], bucket_bounds_uv[1], bucket_bounds_uv[2], bucket_bounds_uv[3]) &&
1721                                                         IsectPT2Df(uv, uv1co, uv2co, uv3co) ) {
1722                                                 
1723                                                 if (ps->is_ortho) {
1724                                                         screen_px_from_ortho(ps, uv, v1coSS,v2coSS,v3coSS, uv1co,uv2co,uv3co, pixelScreenCo);
1725                                                 } else {
1726                                                         screen_px_from_persp(ps, uv, vCo[i1],vCo[i2],vCo[i3], uv1co,uv2co,uv3co, pixelScreenCo);
1727                                                 }
1728                                                 
1729                                                 project_paint_uvpixel_init(ps, thread_index, ibuf, x, y, bucket_index, face_index, image_index, pixelScreenCo);
1730                                         }
1731                                 }
1732                         }
1733                 }
1734         } while(i--);
1735 #ifndef PROJ_DEBUG_NOSEAMBLEED
1736         if (ps->seam_bleed_px > 0.0) {
1737                 int face_seam_flag;
1738                 
1739                 if (ps->thread_tot > 1)
1740                         BLI_lock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
1741                 
1742                 face_seam_flag = ps->faceSeamFlags[face_index];
1743                 
1744                 /* are any of our edges un-initialized? */
1745                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_NOSEAM1))==0 || 
1746                         (face_seam_flag & (PROJ_FACE_SEAM2|PROJ_FACE_NOSEAM2))==0 || 
1747                         (face_seam_flag & (PROJ_FACE_SEAM3|PROJ_FACE_NOSEAM3))==0 || 
1748                         (face_seam_flag & (PROJ_FACE_SEAM4|PROJ_FACE_NOSEAM4))==0
1749                 ) {
1750                         project_face_seams_init(ps, face_index, mf->v4);
1751                         face_seam_flag = ps->faceSeamFlags[face_index];
1752                         //printf("seams - %d %d %d %d\n", flag&PROJ_FACE_SEAM1, flag&PROJ_FACE_SEAM2, flag&PROJ_FACE_SEAM3, flag&PROJ_FACE_SEAM4);
1753                 }
1754                 
1755                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_SEAM2|PROJ_FACE_SEAM3|PROJ_FACE_SEAM4))==0) {
1756                         
1757                         if (ps->thread_tot > 1)
1758                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
1759                         
1760                 } else {
1761                         /* we have a seam - deal with it! */
1762                         
1763                         /* Now create new UV's for the seam face */
1764                         float (*outset_uv)[2];
1765                         float insetCos[4][3]; /* inset face coords.  NOTE!!! ScreenSace for ortho, Worldspace in prespective view */
1766
1767                         float *uv_seam_quad[4];
1768                         float fac;
1769                         float *vCoSS[4]; /* vertex screenspace coords */
1770                         
1771                         float bucket_clip_edges[2][2]; /* store the screenspace coords of the face, clipped by the bucket's screen aligned rectangle */
1772                         float edge_verts_inset_clip[2][3];
1773                         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 */
1774                         
1775                         float seam_subsection[4][2];
1776                         float fac1, fac2, ftot;
1777                         
1778                         outset_uv = ps->faceSeamUVs[face_index];
1779                         
1780                         if (outset_uv[0][0]==MAXFLOAT) /* first time initialize */
1781                                 uv_image_outset(tf_uv_pxoffset, outset_uv, ps->seam_bleed_px, ibuf->x, ibuf->y, mf->v4);
1782                         
1783                         /* ps->faceSeamUVs cant be modified when threading, now this is done we can unlock */
1784                         if (ps->thread_tot > 1)
1785                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
1786                         
1787                         vCoSS[0] = ps->screenCoords[ mf->v1 ];
1788                         vCoSS[1] = ps->screenCoords[ mf->v2 ];
1789                         vCoSS[2] = ps->screenCoords[ mf->v3 ];
1790                         if (mf->v4)
1791                                 vCoSS[3] = ps->screenCoords[ mf->v4 ];
1792                         
1793                         if (ps->is_ortho) {
1794                                 if (mf->v4)     scale_quad(vCoSS, insetCos, 0.99999);
1795                                 else            scale_tri(vCoSS, insetCos, 0.99999);
1796                         } else {
1797                                 if (mf->v4)     scale_quad(vCo, insetCos, 0.99999);
1798                                 else            scale_tri(vCo, insetCos, 0.99999);
1799                         }
1800                         
1801                         for (fidx1 = 0; fidx1 < (mf->v4 ? 4 : 3); fidx1++) {
1802                                 if (mf->v4)             fidx2 = (fidx1==3) ? 0 : fidx1+1; /* next fidx in the face (0,1,2,3) -> (1,2,3,0) */
1803                                 else                    fidx2 = (fidx1==2) ? 0 : fidx1+1; /* next fidx in the face (0,1,2) -> (1,2,0) */
1804                                 
1805                                 if (    (face_seam_flag & (1<<fidx1) ) && /* 1<<fidx1 -> PROJ_FACE_SEAM# */
1806                                                 line_clip_rect2f(bucket_bounds, vCoSS[fidx1], vCoSS[fidx2], bucket_clip_edges[0], bucket_clip_edges[1])
1807                                 ) {
1808
1809                                         ftot = Vec2Lenf(vCoSS[fidx1], vCoSS[fidx2]); /* screenspace edge length */
1810                                         
1811                                         if (ftot > 0.0) { /* avoid div by zero */
1812                                                 
1813                                                 fac1 = Vec2Lenf(vCoSS[fidx1], bucket_clip_edges[0]) / ftot;
1814                                                 fac2 = Vec2Lenf(vCoSS[fidx1], bucket_clip_edges[1]) / ftot;
1815                                                 
1816                                                 uv_seam_quad[0] = tf_uv_pxoffset[fidx1];
1817                                                 uv_seam_quad[1] = tf_uv_pxoffset[fidx2];
1818                                                 uv_seam_quad[2] = outset_uv[fidx2];
1819                                                 uv_seam_quad[3] = outset_uv[fidx1];
1820                                                 
1821                                                 Vec2Lerpf(seam_subsection[0], uv_seam_quad[0], uv_seam_quad[1], fac1);
1822                                                 Vec2Lerpf(seam_subsection[1], uv_seam_quad[0], uv_seam_quad[1], fac2);
1823                                                 
1824                                                 Vec2Lerpf(seam_subsection[2], uv_seam_quad[3], uv_seam_quad[2], fac2);
1825                                                 Vec2Lerpf(seam_subsection[3], uv_seam_quad[3], uv_seam_quad[2], fac1);
1826                                                 
1827                                                 /* if the bucket_clip_edges values Z values was kept we could avoid this
1828                                                  * Inset needs to be added so occlusion tests wont hit adjacent faces */
1829                                                 VecLerpf(edge_verts_inset_clip[0], insetCos[fidx1], insetCos[fidx2], fac1);
1830                                                 VecLerpf(edge_verts_inset_clip[1], insetCos[fidx1], insetCos[fidx2], fac2);
1831                                                 
1832
1833                                                 if (uv_image_rect(seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3], min_px, max_px, ibuf->x, ibuf->y, 1)) {
1834                                                         /* bounds between the seam rect and the uvspace bucket pixels */
1835                                                 
1836                                                         for (y = min_px[1]; y < max_px[1]; y++) {
1837                                                                 // uv[1] = (((float)y) + 0.5) / (float)ibuf->y;
1838                                                                 uv[1] = (float)y / ibuf_yf; /* use offset uvs instead */
1839                                                                 for (x = min_px[0]; x < max_px[0]; x++) {
1840                                                                         //uv[0] = (((float)x) + 0.5) / (float)ibuf->x;
1841                                                                         uv[0] = (float)x / ibuf_xf; /* use offset uvs instead */
1842                                                                         
1843                                                                         /* test we're inside uvspace bucket and triangle bounds */
1844                                                                         if (    IsectPQ2Df(uv, seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3]) ) {
1845                                                                                 
1846                                                                                 /* We need to find the closest point along the face edge,
1847                                                                                  * getting the screen_px_from_*** wont work because our actual location
1848                                                                                  * is not relevent, since we are outside the face, Use VecLerpf to find
1849                                                                                  * our location on the side of the face's UV */
1850                                                                                 /*
1851                                                                                 if (ps->is_ortho)       screen_px_from_ortho(ps, uv, v1co,v2co,v3co, uv1co,uv2co,uv3co, pixelScreenCo);
1852                                                                                 else                                    screen_px_from_persp(ps, uv, v1co,v2co,v3co, uv1co,uv2co,uv3co, pixelScreenCo);
1853                                                                                 */
1854                                                                                 
1855                                                                                 /* Since this is a seam we need to work out where on the line this pixel is */
1856                                                                                 //fac = lambda_cp_line2(uv, uv_seam_quad[0], uv_seam_quad[1]);
1857                                                                                 
1858                                                                                 fac = lambda_cp_line2(uv, seam_subsection[0], seam_subsection[1]);
1859                                                                                 if (fac < 0.0)          { VECCOPY(pixelScreenCo, edge_verts_inset_clip[0]); }
1860                                                                                 else if (fac > 1.0)     { VECCOPY(pixelScreenCo, edge_verts_inset_clip[1]); }
1861                                                                                 else                            { VecLerpf(pixelScreenCo, edge_verts_inset_clip[0], edge_verts_inset_clip[1], fac); }
1862                                                                                 
1863                                                                                 if (!ps->is_ortho) {
1864                                                                                         pixelScreenCo[3] = 1.0;
1865                                                                                         Mat4MulVec4fl(ps->projectMat, pixelScreenCo);
1866                                                                                         pixelScreenCo[0] = (float)(curarea->winx/2.0)+(curarea->winx/2.0)*pixelScreenCo[0]/pixelScreenCo[3];    
1867                                                                                         pixelScreenCo[1] = (float)(curarea->winy/2.0)+(curarea->winy/2.0)*pixelScreenCo[1]/pixelScreenCo[3];
1868                                                                                         pixelScreenCo[2] = pixelScreenCo[2]/pixelScreenCo[3]; /* Use the depth for bucket point occlusion */
1869                                                                                 }
1870                                                                                 
1871                                                                                 project_paint_uvpixel_init(ps, thread_index, ibuf, x, y, bucket_index, face_index, image_index, pixelScreenCo);
1872                                                                         }
1873                                                                 }
1874                                                         }
1875                                                 }
1876                                         }
1877                                 }
1878                         }
1879                 }
1880         }
1881 #endif // PROJ_DEBUG_NOSEAMBLEED
1882 }
1883
1884
1885 /* takes floating point screenspace min/max and returns int min/max to be used as indicies for ps->bucketRect, ps->bucketFlags */
1886 static void project_paint_rect(ProjectPaintState *ps, float min[2], float max[2], int bucket_min[2], int bucket_max[2])
1887 {
1888         /* divide by bucketWidth & bucketHeight so the bounds are offset in bucket grid units */
1889         bucket_min[0] = (int)(((float)(min[0] - ps->screen_min[0]) / ps->screen_width) * ps->buckets_x) + 0.5; /* these offsets of 0.5 and 1.5 seem odd but they are correct */
1890         bucket_min[1] = (int)(((float)(min[1] - ps->screen_min[1]) / ps->screen_height) * ps->buckets_y) + 0.5;
1891         
1892         bucket_max[0] = (int)(((float)(max[0] - ps->screen_min[0]) / ps->screen_width) * ps->buckets_x) + 1.5;
1893         bucket_max[1] = (int)(((float)(max[1] - ps->screen_min[1]) / ps->screen_height) * ps->buckets_y) + 1.5; 
1894         
1895         /* incase the rect is outside the mesh 2d bounds */
1896         CLAMP(bucket_min[0], 0, ps->buckets_x);
1897         CLAMP(bucket_min[1], 0, ps->buckets_y);
1898         
1899         CLAMP(bucket_max[0], 0, ps->buckets_x);
1900         CLAMP(bucket_max[1], 0, ps->buckets_y);
1901 }
1902
1903 static void project_bucket_bounds(ProjectPaintState *ps, int bucket_x, int bucket_y, float bucket_bounds[4])
1904 {
1905         bucket_bounds[ PROJ_BUCKET_LEFT ] =             ps->screen_min[0]+((bucket_x)*(ps->screen_width / ps->buckets_x));              /* left */
1906         bucket_bounds[ PROJ_BUCKET_RIGHT ] =    ps->screen_min[0]+((bucket_x+1)*(ps->screen_width / ps->buckets_x));    /* right */
1907         
1908         bucket_bounds[ PROJ_BUCKET_BOTTOM ] =   ps->screen_min[1]+((bucket_y)*(ps->screen_height / ps->buckets_y));             /* bottom */
1909         bucket_bounds[ PROJ_BUCKET_TOP ] =              ps->screen_min[1]+((bucket_y+1)*(ps->screen_height  / ps->buckets_y));  /* top */
1910 }
1911
1912 /* have bucket_bounds as an arg so we dont need to give bucket_x/y the rect function need */
1913 static void project_paint_bucket_init(ProjectPaintState *ps, int thread_index, int bucket_index, float bucket_bounds[4])
1914 {
1915         LinkNode *node;
1916         int face_index, image_index;
1917         ImBuf *ibuf;
1918         MTFace *tf;
1919         
1920         Image *tpage_last = NULL;
1921         int tpage_index;
1922         
1923         if ((node = ps->bucketFaces[bucket_index])) {
1924                 do {
1925                         face_index = (int)node->link;
1926                                 
1927                         /* Image context switching */
1928                         tf = ps->dm_mtface+face_index;
1929                         if (tpage_last != tf->tpage) {
1930                                 tpage_last = tf->tpage;
1931                                 
1932                                 image_index = -1; /* sanity check */
1933                                 
1934                                 for (tpage_index=0; tpage_index < ps->image_tot; tpage_index++) {
1935                                         if (ps->projImages[tpage_index].ima == tpage_last) {
1936                                                 image_index = tpage_index;
1937                                                 break;
1938                                         }
1939                                 }
1940                                 
1941                                 if (image_index==-1) {
1942                                         printf("Error, should never happen!\n");
1943                                         return;
1944                                 }
1945                                 
1946                                 ibuf = ps->projImages[image_index].ibuf;
1947                         }
1948                         project_paint_face_init(ps, thread_index, bucket_index, face_index, image_index, bucket_bounds, ibuf);
1949                         
1950                         node = node->next;
1951                 } while (node);
1952         }
1953         
1954         ps->bucketFlags[bucket_index] |= PROJ_BUCKET_INIT; 
1955 }
1956
1957
1958 /* We want to know if a bucket and a face overlap in screenspace
1959  * 
1960  * Note, if this ever returns false positives its not that bad, since a face in the bounding area will have its pixels
1961  * calculated when it might not be needed later, (at the moment at least)
1962  * obviously it shouldnt have bugs though */
1963
1964 static int project_bucket_face_isect(ProjectPaintState *ps, float min[2], float max[2], int bucket_x, int bucket_y, int bucket_index, MFace *mf)
1965 {
1966         /* TODO - replace this with a tricker method that uses sideofline for all screenCoords's edges against the closest bucket corner */
1967         float bucket_bounds[4];
1968         float p1[2], p2[2], p3[2], p4[2];
1969         float *v, *v1,*v2,*v3,*v4;
1970         int i;
1971         
1972         project_bucket_bounds(ps, bucket_x, bucket_y, bucket_bounds);
1973         
1974         /* Is one of the faces verts in the bucket bounds? */
1975         
1976         i = mf->v4 ? 3:2;
1977         do {
1978                 v = ps->screenCoords[ (*(&mf->v1 + i)) ];
1979                 
1980                 if ((v[0] > bucket_bounds[PROJ_BUCKET_LEFT]) &&
1981                         (v[0] < bucket_bounds[PROJ_BUCKET_RIGHT]) &&
1982                         (v[1] > bucket_bounds[PROJ_BUCKET_BOTTOM]) &&
1983                         (v[1] < bucket_bounds[PROJ_BUCKET_TOP]) )
1984                 {
1985                         return 1;
1986                 }
1987         } while (i--);
1988                 
1989         v1 = ps->screenCoords[mf->v1];
1990         v2 = ps->screenCoords[mf->v2];
1991         v3 = ps->screenCoords[mf->v3];
1992         if (mf->v4) {
1993                 v4 = ps->screenCoords[mf->v4];
1994         }
1995         
1996         p1[0] = bucket_bounds[PROJ_BUCKET_LEFT];        p1[1] = bucket_bounds[PROJ_BUCKET_BOTTOM];
1997         p2[0] = bucket_bounds[PROJ_BUCKET_LEFT];        p2[1] = bucket_bounds[PROJ_BUCKET_TOP];
1998         p3[0] = bucket_bounds[PROJ_BUCKET_RIGHT];       p3[1] = bucket_bounds[PROJ_BUCKET_TOP];
1999         p4[0] = bucket_bounds[PROJ_BUCKET_RIGHT];       p4[1] = bucket_bounds[PROJ_BUCKET_BOTTOM];
2000                 
2001         if (mf->v4) {
2002                 if(     IsectPQ2Df(p1, v1, v2, v3, v4) || IsectPQ2Df(p2, v1, v2, v3, v4) || IsectPQ2Df(p3, v1, v2, v3, v4) || IsectPQ2Df(p4, v1, v2, v3, v4) ||
2003                         /* we can avoid testing v3,v1 because another intersection MUST exist if this intersects */
2004                         (IsectLL2Df(p1,p2, v1, v2) || IsectLL2Df(p1,p2, v2, v3) || IsectLL2Df(p1,p2, v3, v4)) ||
2005                         (IsectLL2Df(p2,p3, v1, v2) || IsectLL2Df(p2,p3, v2, v3) || IsectLL2Df(p2,p3, v3, v4)) ||
2006                         (IsectLL2Df(p3,p4, v1, v2) || IsectLL2Df(p3,p4, v2, v3) || IsectLL2Df(p3,p4, v3, v4)) ||
2007                         (IsectLL2Df(p4,p1, v1, v2) || IsectLL2Df(p4,p1, v2, v3) || IsectLL2Df(p4,p1, v3, v4))
2008                 ) {
2009                         return 1;
2010                 }
2011         } else {
2012                 if(     IsectPT2Df(p1, v1, v2, v3) || IsectPT2Df(p2, v1, v2, v3) || IsectPT2Df(p3, v1, v2, v3) || IsectPT2Df(p4, v1, v2, v3) ||
2013                         /* we can avoid testing v3,v1 because another intersection MUST exist if this intersects */
2014                         (IsectLL2Df(p1,p2, v1, v2) || IsectLL2Df(p1,p2, v2, v3)) ||
2015                         (IsectLL2Df(p2,p3, v1, v2) || IsectLL2Df(p2,p3, v2, v3)) ||
2016                         (IsectLL2Df(p3,p4, v1, v2) || IsectLL2Df(p3,p4, v2, v3)) ||
2017                         (IsectLL2Df(p4,p1, v1, v2) || IsectLL2Df(p4,p1, v2, v3))
2018                 ) {
2019                         return 1;
2020                 }
2021         }
2022
2023         return 0;
2024 }
2025
2026 static void project_paint_delayed_face_init(ProjectPaintState *ps, MFace *mf, MTFace *tf, int face_index)
2027 {
2028         float min[2], max[2];
2029         int bucket_min[2], bucket_max[2]; /* for  ps->bucketRect indexing */
2030         int i, a, bucket_x, bucket_y, bucket_index;
2031         
2032         int has_x_isect = -1, has_isect = -1; /* for early loop exit */
2033         
2034         INIT_MINMAX2(min,max);
2035         
2036         i = mf->v4 ? 3:2;
2037         do {
2038                 a = (*(&mf->v1 + i)); /* vertex index */
2039                 
2040                 DO_MINMAX2(ps->screenCoords[ a ], min, max);
2041                 
2042 #ifndef PROJ_DEBUG_NOSEAMBLEED
2043                 /* add face user if we have bleed enabled, set the UV seam flags later */
2044                 if (ps->seam_bleed_px > 0.0) {
2045                         BLI_linklist_prepend_arena(
2046                                 &ps->vertFaces[ a ],
2047                                 (void *)face_index, /* cast to a pointer to shut up the compiler */
2048                                 ps->arena
2049                         );
2050                 }
2051 #endif
2052         } while (i--);
2053         
2054         project_paint_rect(ps, min, max, bucket_min, bucket_max);
2055         
2056         for (bucket_y = bucket_min[1]; bucket_y < bucket_max[1]; bucket_y++) {
2057                 has_x_isect = 0;
2058                 for (bucket_x = bucket_min[0]; bucket_x < bucket_max[0]; bucket_x++) {
2059                         
2060                         bucket_index = bucket_x + (bucket_y * ps->buckets_x);
2061                         
2062                         if (project_bucket_face_isect(ps, min, max, bucket_x, bucket_y, bucket_index, mf)) {
2063                                 BLI_linklist_prepend_arena(
2064                                         &ps->bucketFaces[ bucket_index ],
2065                                         (void *)face_index, /* cast to a pointer to shut up the compiler */
2066                                         ps->arena
2067                                 );
2068                                 
2069                                 has_x_isect = has_isect = 1;
2070                         } else if (has_x_isect) {
2071                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2072                                 break;
2073                         }
2074                 }
2075                 
2076                 /* no intersection for this entire row, after some intersection above means we can quit now */
2077                 if (has_x_isect==0 && has_isect) { 
2078                         break;
2079                 }
2080         }
2081         
2082 #ifndef PROJ_DEBUG_NOSEAMBLEED
2083         if (ps->seam_bleed_px > 0.0) {
2084                 if (!mf->v4) {
2085                         ps->faceSeamFlags[face_index] |= PROJ_FACE_NOSEAM4; /* so this wont show up as an untagged egde */
2086                 }
2087                 **ps->faceSeamUVs[face_index] = MAXFLOAT; /* set as uninitialized */
2088         }
2089 #endif
2090 }
2091
2092 static void project_paint_begin( ProjectPaintState *ps, short mval[2])
2093 {       
2094         /* Viewport vars */
2095         float mat[3][3];
2096         float f_no[3];
2097         float viewPos[3]; /* for projection only - view location */
2098         
2099         float (*projScreenCo)[4]; /* Note, we could have 4D vectors are only needed for */
2100         float projMargin;
2101         /* Image Vars - keep track of images we have used */
2102         LinkNode *image_LinkList = NULL;
2103         LinkNode *node;
2104         
2105         ProjectPaintImage *projIma;
2106         Image *tpage_last = NULL;
2107         ImBuf *ibuf = NULL;
2108         
2109         /* Face vars */
2110         MFace *mf;
2111         MTFace *tf;
2112         
2113         int a, i; /* generic looping vars */
2114         int image_index;
2115         
2116         /* memory sized to add to arena size */
2117         int tot_bucketMem=0;
2118         int tot_faceSeamFlagMem=0;
2119         int tot_faceSeamUVMem=0;
2120         int tot_faceListMem=0;
2121         int tot_bucketFlagMem=0;
2122         int tot_bucketVertFacesMem=0;
2123
2124         /* ---- end defines ---- */
2125         
2126         /* paint onto the derived mesh
2127          * note get_viewedit_datamask checks for paint mode and will always give UVs */
2128         ps->dm = mesh_get_derived_final(ps->ob, get_viewedit_datamask());
2129         
2130         ps->dm_mvert = ps->dm->getVertArray( ps->dm );
2131         ps->dm_mface = ps->dm->getFaceArray( ps->dm );
2132         ps->dm_mtface= ps->dm->getFaceDataArray( ps->dm, CD_MTFACE );
2133         
2134         ps->dm_totvert = ps->dm->getNumVerts( ps->dm );
2135         ps->dm_totface = ps->dm->getNumFaces( ps->dm );
2136         
2137         ps->buckets_x = G.rt ? G.rt : PROJ_BUCKET_DIV;
2138         ps->buckets_y = G.rt ? G.rt : PROJ_BUCKET_DIV;
2139         
2140         ps->viewDir[0] = 0.0;
2141         ps->viewDir[1] = 0.0;
2142         ps->viewDir[2] = 1.0;
2143         
2144         view3d_get_object_project_mat(curarea, ps->ob, ps->projectMat, ps->viewMat);
2145         
2146         tot_bucketMem =                         sizeof(LinkNode *) * ps->buckets_x * ps->buckets_y;
2147         tot_faceListMem =                       sizeof(LinkNode *) * ps->buckets_x * ps->buckets_y;
2148         
2149         tot_bucketFlagMem =                     sizeof(char) * ps->buckets_x * ps->buckets_y;
2150 #ifndef PROJ_DEBUG_NOSEAMBLEED
2151         if (ps->seam_bleed_px > 0.0) { /* UV Seams for bleeding */
2152                 tot_bucketVertFacesMem =        sizeof(LinkNode *) * ps->dm_totvert;
2153                 tot_faceSeamFlagMem =           sizeof(char) * ps->dm_totface;
2154                 tot_faceSeamUVMem =                     sizeof(float) * ps->dm_totface * 8;
2155         }
2156 #endif
2157         
2158         /* BLI_memarena_new uses calloc */
2159         ps->arena =
2160                 BLI_memarena_new(       tot_bucketMem +
2161                                                         tot_faceListMem +
2162                                                         tot_faceSeamFlagMem +
2163                                                         tot_faceSeamUVMem +
2164                                                         tot_bucketVertFacesMem + (1<<18));
2165         
2166         BLI_memarena_use_calloc(ps->arena);
2167         
2168         ps->bucketRect = (LinkNode **)BLI_memarena_alloc( ps->arena, tot_bucketMem);
2169         ps->bucketFaces= (LinkNode **)BLI_memarena_alloc( ps->arena, tot_faceListMem);
2170         
2171         ps->bucketFlags= (char *)BLI_memarena_alloc( ps->arena, tot_bucketFlagMem);
2172 #ifndef PROJ_DEBUG_NOSEAMBLEED
2173         if (ps->seam_bleed_px > 0.0) {
2174                 ps->vertFaces= (LinkNode **)BLI_memarena_alloc( ps->arena, tot_bucketVertFacesMem);
2175                 ps->faceSeamFlags = (char *)BLI_memarena_alloc( ps->arena, tot_faceSeamFlagMem);
2176                 ps->faceSeamUVs= BLI_memarena_alloc( ps->arena, tot_faceSeamUVMem);
2177         }
2178 #endif
2179         
2180         // calloced - memset(ps->bucketRect,            0, tot_bucketMem);
2181         // calloced -  memset(ps->bucketFaces,          0, tot_faceListMem);
2182         // calloced - memset(ps->bucketFlags,   0, tot_bucketFlagMem);
2183 #ifndef PROJ_DEBUG_NOSEAMBLEED
2184         // calloced - memset(ps->faceSeamFlags,0, tot_faceSeamFlagMem);
2185         
2186         // calloced - if (ps->seam_bleed_px > 0.0) {
2187                 // calloced - memset(ps->vertFaces,     0, tot_bucketVertFacesMem);
2188                 /* TODO dosnt need zeroing? */
2189                 // calloced - memset(ps->faceSeamUVs,   0, tot_faceSeamUVMem);
2190         // calloced - }
2191 #endif
2192         
2193         /* Thread stuff */
2194         if (G.scene->r.mode & R_FIXED_THREADS) {
2195                 ps->thread_tot = G.scene->r.threads;
2196         } else {
2197                 ps->thread_tot = BLI_system_thread_count();
2198         }
2199         
2200         for (a=0; a<ps->thread_tot; a++) {
2201                 ps->arena_mt[a] = BLI_memarena_new(1<<16);
2202         }
2203         
2204         Mat4Invert(ps->ob->imat, ps->ob->obmat);
2205         
2206         Mat3CpyMat4(mat, G.vd->viewinv);
2207         Mat3MulVecfl(mat, ps->viewDir);
2208         Mat3CpyMat4(mat, ps->ob->imat);
2209         Mat3MulVecfl(mat, ps->viewDir);
2210         
2211         /* calculate vert screen coords */
2212         ps->screenCoords = BLI_memarena_alloc( ps->arena, sizeof(float) * ps->dm_totvert * 4);
2213         projScreenCo = ps->screenCoords;
2214         
2215         /* TODO - check cameras mode too */
2216         if (G.vd->persp == V3D_ORTHO) {
2217                 ps->is_ortho = 1;
2218         }
2219         
2220         INIT_MINMAX2(ps->screen_min, ps->screen_max);
2221
2222         if (ps->is_ortho) {
2223                 for(a=0; a < ps->dm_totvert; a++, projScreenCo++) {
2224                         VECCOPY((*projScreenCo), ps->dm_mvert[a].co);
2225                         Mat4MulVecfl(ps->projectMat, (*projScreenCo));
2226
2227                         /* screen space, not clamped */
2228                         (*projScreenCo)[0] = (float)(curarea->winx/2.0)+(curarea->winx/2.0)*(*projScreenCo)[0];
2229                         (*projScreenCo)[1] = (float)(curarea->winy/2.0)+(curarea->winy/2.0)*(*projScreenCo)[1];
2230                         DO_MINMAX2((*projScreenCo), ps->screen_min, ps->screen_max);
2231                 }
2232         } else {
2233                 for(a=0; a < ps->dm_totvert; a++, projScreenCo++) {
2234                         VECCOPY((*projScreenCo), ps->dm_mvert[a].co);
2235                         (*projScreenCo)[3] = 1.0;
2236
2237                         Mat4MulVec4fl(ps->projectMat, (*projScreenCo));
2238
2239                         if( (*projScreenCo)[3] > 0.001 ) {
2240                                 /* screen space, not clamped */
2241                                 (*projScreenCo)[0] = (float)(curarea->winx/2.0)+(curarea->winx/2.0)*(*projScreenCo)[0]/(*projScreenCo)[3];
2242                                 (*projScreenCo)[1] = (float)(curarea->winy/2.0)+(curarea->winy/2.0)*(*projScreenCo)[1]/(*projScreenCo)[3];
2243                                 (*projScreenCo)[2] = (*projScreenCo)[2]/(*projScreenCo)[3]; /* Use the depth for bucket point occlusion */
2244                                 DO_MINMAX2((*projScreenCo), ps->screen_min, ps->screen_max);
2245                         } else {
2246                                 /* TODO - deal with cases where 1 side of a face goes behind the view ? */
2247                                 (*projScreenCo)[0] = MAXFLOAT;
2248                         }
2249                 }
2250         }
2251
2252         /* setup clone offset */
2253         if (ps->tool == PAINT_TOOL_CLONE) {
2254                 float projCo[4];
2255                 float *curs= give_cursor();
2256                 VECCOPY(projCo, curs);
2257                 Mat4MulVecfl(ps->ob->imat, projCo);
2258                 
2259                 projCo[3] = 1.0;
2260                 Mat4MulVec4fl(ps->projectMat, projCo);
2261                 ps->clone_offset[0] = mval[0] - ((float)(curarea->winx/2.0)+(curarea->winx/2.0)*projCo[0]/projCo[3]);
2262                 ps->clone_offset[1] = mval[1] - ((float)(curarea->winy/2.0)+(curarea->winy/2.0)*projCo[1]/projCo[3]);
2263                 
2264                 // printf("%f %f   %f %f %f\n", ps->clone_offset[0], ps->clone_offset[1], curs[0], curs[1], curs[2]);
2265                 
2266         }
2267         
2268         /* If this border is not added we get artifacts for faces that
2269          * have a paralelle edge and at the bounds of the the 2D projected verts eg
2270          * - a simgle screen aligned quad */
2271         projMargin = (ps->screen_max[0] - ps->screen_min[0]) * 0.000001;
2272         ps->screen_max[0] += projMargin;
2273         ps->screen_min[0] -= projMargin;
2274         projMargin = (ps->screen_max[1] - ps->screen_min[1]) * 0.000001;
2275         ps->screen_max[1] += projMargin;
2276         ps->screen_min[1] -= projMargin;
2277         
2278         
2279         /* only for convenience */
2280         ps->screen_width  = ps->screen_max[0] - ps->screen_min[0];
2281         ps->screen_height = ps->screen_max[1] - ps->screen_min[1];
2282         
2283         if (!ps->is_ortho) {
2284                 /* get the view direction relative to the objects matrix */
2285                 float imat[3][3];
2286                 VECCOPY(viewPos, G.vd->viewinv[3]);
2287                 Mat3CpyMat4(imat, ps->ob->imat);
2288                 Mat3MulVecfl(imat, viewPos);
2289                 VecAddf(viewPos, viewPos, ps->ob->imat[3]);
2290         }
2291         
2292         for( a = 0, tf = ps->dm_mtface, mf = ps->dm_mface; a < ps->dm_totface; mf++, tf++, a++ ) {
2293                 if (tf->tpage && ((G.f & G_FACESELECT)==0 || mf->flag & ME_FACE_SEL)) {
2294
2295                         if (!ps->is_ortho) {
2296                                 if (    ps->screenCoords[mf->v1][0]==MAXFLOAT ||
2297                                                 ps->screenCoords[mf->v2][0]==MAXFLOAT ||
2298                                                 ps->screenCoords[mf->v3][0]==MAXFLOAT ||
2299                                                 (mf->v4 && ps->screenCoords[mf->v4][0]==MAXFLOAT)
2300                                 ) {
2301                                         continue;
2302                                 }
2303                         }
2304
2305                         if (ps->do_backfacecull) {
2306                                 /* TODO - we dont really need the normal, just the direction, save a sqrt? */
2307                                 if (mf->v4)     CalcNormFloat4(ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, ps->dm_mvert[mf->v4].co, f_no);
2308                                 else            CalcNormFloat(ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, f_no);
2309                                 
2310                                 if (ps->is_ortho) {
2311                                         if (Inpf(f_no, ps->viewDir) < 0) {
2312                                                 continue;
2313                                         }
2314                                 } else {
2315                                         float faceDir[3] = {0,0,0};
2316                                         if (mf->v4)     {
2317                                                 VecAddf(faceDir, faceDir, ps->dm_mvert[mf->v1].co);
2318                                                 VecAddf(faceDir, faceDir, ps->dm_mvert[mf->v2].co);
2319                                                 VecAddf(faceDir, faceDir, ps->dm_mvert[mf->v3].co);
2320                                                 VecAddf(faceDir, faceDir, ps->dm_mvert[mf->v4].co);
2321                                                 VecMulf(faceDir, 1.0/4.0);
2322                                         } else {
2323                                                 VecAddf(faceDir, faceDir, ps->dm_mvert[mf->v1].co);
2324                                                 VecAddf(faceDir, faceDir, ps->dm_mvert[mf->v2].co);
2325                                                 VecAddf(faceDir, faceDir, ps->dm_mvert[mf->v3].co);
2326                                                 VecMulf(faceDir, 1.0/3.0);
2327                                         }
2328                                         
2329                                         VecSubf(faceDir, viewPos, faceDir);
2330                                         
2331                                         if (Inpf(f_no, faceDir) < 0) {
2332                                                 continue;
2333                                         }
2334                                 }
2335                         }
2336                         
2337                         if (tpage_last != tf->tpage) {
2338                                 ibuf= BKE_image_get_ibuf((Image *)tf->tpage, NULL);
2339                                 
2340                                 if (ibuf) {
2341                                         image_index = BLI_linklist_index(image_LinkList, tf->tpage);
2342                                         
2343                                         if (image_index==-1) { /* MemArena dosnt have an append func */
2344                                                 BLI_linklist_append(&image_LinkList, tf->tpage);
2345                                                 image_index = ps->image_tot;
2346                                                 ps->image_tot++;
2347                                         }
2348                                 }
2349                                 
2350                                 tpage_last = tf->tpage;
2351                         }
2352                         
2353                         if (ibuf) {
2354                                 /* Initialize the faces screen pixels */
2355                                 /* Add this to a list to initialize later */
2356                                 project_paint_delayed_face_init(ps, mf, tf, a);
2357                         }
2358                 }
2359         }
2360         
2361         /* build an array of images we use*/
2362         projIma = ps->projImages = (ProjectPaintImage *)BLI_memarena_alloc( ps->arena, sizeof(ProjectPaintImage) * ps->image_tot);
2363         
2364         for (node= image_LinkList, i=0; node; node= node->next, i++, projIma++) {
2365                 projIma->ima = node->link;
2366                 // calloced - projIma->touch = 0;
2367                 projIma->ibuf = BKE_image_get_ibuf(projIma->ima, NULL);
2368                 projIma->partRedrawRect =  BLI_memarena_alloc( ps->arena, sizeof(ImagePaintPartialRedraw) * PROJ_BOUNDBOX_SQUARED);
2369                 // calloced - memset(projIma->partRedrawRect, 0, sizeof(ImagePaintPartialRedraw) * PROJ_BOUNDBOX_SQUARED);
2370         }
2371         
2372         /* we have built the array, discard the linked list */
2373         BLI_linklist_free(image_LinkList, NULL);
2374 }
2375
2376 static void project_paint_end( ProjectPaintState *ps )
2377 {
2378         int a;
2379         
2380         /* build undo data from original pixel colors */
2381         if(U.uiflag & USER_GLOBALUNDO) {
2382                 ProjectPixel *projPixel;
2383                 ImBuf *tmpibuf = NULL;
2384                 LinkNode *pixel_node;
2385                 UndoTile *tile;
2386                 
2387                 int bucket_index = (ps->buckets_x * ps->buckets_y) - 1; /* we could get an X/Y but easier to loop through all possible buckets */
2388                 int tile_index;
2389                 int x_round, y_round;
2390                 int x_tile, y_tile;
2391                 
2392                 /* context */
2393                 ProjectPaintImage *last_projIma;
2394                 int last_image_index = -1;
2395                 int last_tile_width;
2396                 
2397                 for(a=0, last_projIma=ps->projImages; a < ps->image_tot; a++, last_projIma++) {
2398                         last_projIma = &(ps->projImages[a]);
2399                         last_projIma->undoRect = (UndoTile **) BLI_memarena_alloc(ps->arena, sizeof(UndoTile **) * IMAPAINT_TILE_NUMBER(last_projIma->ibuf->x) * IMAPAINT_TILE_NUMBER(last_projIma->ibuf->y)); 
2400                 }
2401                 
2402                 do {
2403                         if ((pixel_node = ps->bucketRect[bucket_index])) {
2404                                 
2405                                 /* loop through all pixels */
2406                                 while (pixel_node) {
2407                                         /* ok we have a pixel, was it modified? */
2408                                         projPixel = (ProjectPixel *)pixel_node->link;
2409                                         
2410                                         /* TODO - support float */
2411                                         if (*((unsigned int *)projPixel->origColor) != *((unsigned int *)projPixel->pixel)) {
2412                                                 
2413                                                 if (last_image_index != projPixel->image_index) {
2414                                                         /* set the context */
2415                                                         last_image_index =      projPixel->image_index;
2416                                                         last_projIma =          ps->projImages + last_image_index;
2417                                                         last_tile_width =       IMAPAINT_TILE_NUMBER(last_projIma->ibuf->x);
2418                                                 }
2419                                                 
2420                                                 x_tile =  projPixel->x_px >> IMAPAINT_TILE_BITS;
2421                                                 y_tile =  projPixel->y_px >> IMAPAINT_TILE_BITS;
2422                                                 
2423                                                 x_round = x_tile * IMAPAINT_TILE_SIZE;
2424                                                 y_round = y_tile * IMAPAINT_TILE_SIZE;
2425                                                 
2426                                                 tile_index = x_tile + y_tile * last_tile_width;
2427                                                 
2428                                                 if (last_projIma->undoRect[tile_index]==NULL) {
2429                                                         /* add the undo tile from the modified image, then write the original colors back into it */
2430                                                         tile = last_projIma->undoRect[tile_index] = undo_init_tile(&last_projIma->ima->id, last_projIma->ibuf, &tmpibuf, x_tile, y_tile);
2431                                                 } else {
2432                                                         tile = last_projIma->undoRect[tile_index];
2433                                                 }
2434                                                 
2435                                                 /* This is a BIT ODD, but overwrite the undo tiles image info with this pixels original color
2436                                                  * because allocating the tiles allong the way slows down painting */
2437                                                 /* TODO float buffer */
2438                                                 ((unsigned int *)tile->rect)[ (projPixel->x_px - x_round) + (projPixel->y_px - y_round) * IMAPAINT_TILE_SIZE ] = *((unsigned int *)projPixel->origColor);                                               
2439                                         }
2440                                         
2441                                         pixel_node = pixel_node->next;
2442                                 }
2443                         }
2444                 } while(bucket_index--);
2445                 
2446                 if (tmpibuf)
2447                         IMB_freeImBuf(tmpibuf);
2448         }
2449         /* done calculating undo data */
2450         
2451         
2452         BLI_memarena_free(ps->arena);
2453         
2454         for (a=0; a<ps->thread_tot; a++) {
2455                 BLI_memarena_free(ps->arena_mt[a]);
2456         }
2457         
2458         ps->dm->release(ps->dm);
2459 }
2460
2461
2462 /* external functions */
2463
2464 /* 1= an undo, -1 is a redo. */
2465 void undo_imagepaint_step(int step)
2466 {
2467         UndoElem *undo;
2468
2469         if(step==1) {
2470                 if(curundo==NULL) error("No more steps to undo");
2471                 else {
2472                         if(G.f & G_DEBUG) printf("undo %s\n", curundo->name);
2473                         undo_restore(curundo);
2474                         curundo= curundo->prev;
2475                 }
2476         }
2477         else if(step==-1) {
2478                 if((curundo!=NULL && curundo->next==NULL) || undobase.first==NULL) error("No more steps to redo");
2479                 else {
2480                         undo= (curundo && curundo->next)? curundo->next: undobase.first;
2481                         undo_restore(undo);
2482                         curundo= undo;
2483                         if(G.f & G_DEBUG) printf("redo %s\n", undo->name);
2484                 }
2485         }
2486
2487         allqueue(REDRAWVIEW3D, 0);
2488         allqueue(REDRAWIMAGE, 0);
2489 }
2490
2491 void undo_imagepaint_clear(void)
2492 {
2493         UndoElem *uel;
2494         
2495         uel= undobase.first;
2496         while(uel) {
2497                 undo_free(uel);
2498                 uel= uel->next;
2499         }
2500
2501         BLI_freelistN(&undobase);
2502         curundo= NULL;
2503 }
2504
2505 /* Imagepaint Partial Redraw & Dirty Region */
2506
2507 static void imapaint_clear_partial_redraw()
2508 {
2509         memset(&imapaintpartial, 0, sizeof(imapaintpartial));
2510 }
2511
2512 static void imapaint_dirty_region(Image *ima, ImBuf *ibuf, int x, int y, int w, int h)
2513 {
2514         ImBuf *tmpibuf = NULL;
2515         UndoTile *tile;
2516         int srcx= 0, srcy= 0, origx;
2517
2518         IMB_rectclip(ibuf, NULL, &x, &y, &srcx, &srcy, &w, &h);
2519
2520         if (w == 0 || h == 0)
2521                 return;
2522         
2523         if (!imapaintpartial.enabled) {
2524                 imapaintpartial.x1 = x;
2525                 imapaintpartial.y1 = y;
2526                 imapaintpartial.x2 = x+w;
2527                 imapaintpartial.y2 = y+h;
2528                 imapaintpartial.enabled = 1;
2529         }
2530         else {
2531                 imapaintpartial.x1 = MIN2(imapaintpartial.x1, x);
2532                 imapaintpartial.y1 = MIN2(imapaintpartial.y1, y);
2533                 imapaintpartial.x2 = MAX2(imapaintpartial.x2, x+w);
2534                 imapaintpartial.y2 = MAX2(imapaintpartial.y2, y+h);
2535         }
2536
2537         w = ((x + w - 1) >> IMAPAINT_TILE_BITS);
2538         h = ((y + h - 1) >> IMAPAINT_TILE_BITS);
2539         origx = (x >> IMAPAINT_TILE_BITS);
2540         y = (y >> IMAPAINT_TILE_BITS);
2541         
2542         for (; y <= h; y++) {
2543                 for (x=origx; x <= w; x++) {
2544                         for(tile=curundo->tiles.first; tile; tile=tile->next)
2545                                 if(tile->x == x && tile->y == y && strcmp(tile->id.name, ima->id.name)==0)
2546                                         break;
2547
2548                         if(!tile) {
2549                                 undo_init_tile(&ima->id, ibuf, &tmpibuf, x, y);
2550                         }
2551                 }
2552         }
2553
2554         ibuf->userflags |= IB_BITMAPDIRTY;
2555         
2556         if (tmpibuf)
2557                 IMB_freeImBuf(tmpibuf);
2558 }
2559
2560 static void imapaint_image_update(Image *image, ImBuf *ibuf, short texpaint)
2561 {
2562         if(ibuf->rect_float)
2563                 imb_freerectImBuf(ibuf); /* force recreate of char rect */ /* TODO - should just update a portion from imapaintpartial! */
2564         if(ibuf->mipmap[0])
2565                 imb_freemipmapImBuf(ibuf);
2566
2567         /* todo: should set_tpage create ->rect? */
2568         if(texpaint || G.sima->lock) {
2569                 int w = imapaintpartial.x2 - imapaintpartial.x1;
2570                 int h = imapaintpartial.y2 - imapaintpartial.y1;
2571                 // printf("%d, %d, \n", w, h);
2572                 GPU_paint_update_image(image, imapaintpartial.x1, imapaintpartial.y1, w, h);
2573         }
2574 }
2575
2576 /* note; gets called for both 2d image paint and 3d texture paint. in the
2577    latter case image may be NULL and G.sima may not exist */
2578 static void imapaint_redraw(int final, int texpaint, Image *image)
2579 {
2580         if(final) {
2581                 if(texpaint)
2582                         allqueue(REDRAWIMAGE, 0);
2583                 else if(!G.sima->lock) {
2584                         if(image)
2585                                 GPU_free_image(image); /* force OpenGL reload */
2586                         allqueue(REDRAWVIEW3D, 0);
2587                 }
2588                 allqueue(REDRAWHEADERS, 0);
2589                 
2590                 if(!texpaint && image) {
2591                         /* after paint, tag Image or RenderResult nodes changed */
2592                         if(G.scene->nodetree) {
2593                                 imagepaint_composite_tags(G.scene->nodetree, image, &G.sima->iuser);
2594                         }
2595                         /* signal composite (hurmf, need an allqueue?) */
2596                         if(G.sima->lock) {
2597                                 ScrArea *sa;
2598                                 for(sa=G.curscreen->areabase.first; sa; sa= sa->next) {
2599                                         if(sa->spacetype==SPACE_NODE) {
2600                                                 if(((SpaceNode *)sa->spacedata.first)->treetype==NTREE_COMPOSIT) {
2601                                                         addqueue(sa->win, UI_BUT_EVENT, B_NODE_TREE_EXEC);
2602                                                         break;
2603                                                 }
2604                                         }
2605                                 }
2606                         }
2607                 }               
2608         }
2609         else if(!texpaint && G.sima->lock)
2610                 force_draw_plus(SPACE_VIEW3D, 0);
2611         else
2612                 force_draw(0);
2613 }
2614
2615 /* Image Paint Operations */
2616
2617 static void imapaint_ibuf_get_set_rgb(ImBuf *ibuf, int x, int y, short torus, short set, float *rgb)
2618 {
2619         if (torus) {
2620                 x %= ibuf->x;
2621                 if (x < 0) x += ibuf->x;
2622                 y %= ibuf->y;
2623                 if (y < 0) y += ibuf->y;
2624         }
2625
2626         if (ibuf->rect_float) {
2627                 float *rrgbf = ibuf->rect_float + (ibuf->x*y + x)*4;
2628
2629                 if (set) IMAPAINT_FLOAT_RGB_COPY(rrgbf, rgb)
2630                 else IMAPAINT_FLOAT_RGB_COPY(rgb, rrgbf)
2631         }
2632         else {
2633                 char *rrgb = (char*)ibuf->rect + (ibuf->x*y + x)*4;
2634
2635                 if (set) IMAPAINT_FLOAT_RGB_TO_CHAR(rrgb, rgb)
2636                 else IMAPAINT_CHAR_RGB_TO_FLOAT(rgb, rrgb)
2637         }
2638 }
2639
2640 static int imapaint_ibuf_add_if(ImBuf *ibuf, unsigned int x, unsigned int y, float *outrgb, short torus)
2641 {
2642         float inrgb[3];
2643
2644         if ((x >= ibuf->x) || (y >= ibuf->y)) {
2645                 if (torus) imapaint_ibuf_get_set_rgb(ibuf, x, y, 1, 0, inrgb);
2646                 else return 0;
2647         }
2648         else imapaint_ibuf_get_set_rgb(ibuf, x, y, 0, 0, inrgb);
2649
2650         outrgb[0] += inrgb[0];
2651         outrgb[1] += inrgb[1];
2652         outrgb[2] += inrgb[2];
2653
2654         return 1;
2655 }
2656
2657 static void imapaint_lift_soften(ImBuf *ibuf, ImBuf *ibufb, int *pos, short torus)
2658 {
2659         int x, y, count, xi, yi, xo, yo;
2660         int out_off[2], in_off[2], dim[2];
2661         float outrgb[3];
2662
2663         dim[0] = ibufb->x;
2664         dim[1] = ibufb->y;
2665         in_off[0] = pos[0];
2666         in_off[1] = pos[1];
2667         out_off[0] = out_off[1] = 0;
2668
2669         if (!torus) {
2670                 IMB_rectclip(ibuf, ibufb, &in_off[0], &in_off[1], &out_off[0],
2671                         &out_off[1], &dim[0], &dim[1]);
2672
2673                 if ((dim[0] == 0) || (dim[1] == 0))
2674                         return;
2675         }
2676
2677         for (y=0; y < dim[1]; y++) {
2678                 for (x=0; x < dim[0]; x++) {
2679                         /* get input pixel */
2680                         xi = in_off[0] + x;
2681                         yi = in_off[1] + y;
2682
2683                         count = 1;
2684                         imapaint_ibuf_get_set_rgb(ibuf, xi, yi, torus, 0, outrgb);
2685
2686                         count += imapaint_ibuf_add_if(ibuf, xi-1, yi-1, outrgb, torus);
2687                         count += imapaint_ibuf_add_if(ibuf, xi-1, yi  , outrgb, torus);
2688                         count += imapaint_ibuf_add_if(ibuf, xi-1, yi+1, outrgb, torus);
2689
2690                         count += imapaint_ibuf_add_if(ibuf, xi  , yi-1, outrgb, torus);
2691                         count += imapaint_ibuf_add_if(ibuf, xi  , yi+1, outrgb, torus);
2692
2693                         count += imapaint_ibuf_add_if(ibuf, xi+1, yi-1, outrgb, torus);
2694                         count += imapaint_ibuf_add_if(ibuf, xi+1, yi  , outrgb, torus);
2695                         count += imapaint_ibuf_add_if(ibuf, xi+1, yi+1, outrgb, torus);
2696
2697                         outrgb[0] /= count;
2698                         outrgb[1] /= count;
2699                         outrgb[2] /= count;
2700
2701                         /* write into brush buffer */
2702                         xo = out_off[0] + x;
2703                         yo = out_off[1] + y;
2704                         imapaint_ibuf_get_set_rgb(ibufb, xo, yo, 0, 1, outrgb);
2705                 }
2706         }
2707 }
2708
2709 static void imapaint_lift_smear(ImBuf *ibuf, ImBuf *ibufb, int *pos)
2710 {
2711         IMB_rectblend_torus(ibufb, ibuf, 0, 0, pos[0], pos[1],
2712                 ibufb->x, ibufb->y, IMB_BLEND_COPY_RGB);
2713 }
2714
2715 static ImBuf *imapaint_lift_clone(ImBuf *ibuf, ImBuf *ibufb, int *pos)
2716 {
2717         /* note: allocImbuf returns zero'd memory, so regions outside image will
2718            have zero alpha, and hence not be blended onto the image */
2719         int w=ibufb->x, h=ibufb->y, destx=0, desty=0, srcx=pos[0], srcy=pos[1];
2720         ImBuf *clonebuf= IMB_allocImBuf(w, h, ibufb->depth, ibufb->flags, 0);
2721
2722         IMB_rectclip(clonebuf, ibuf, &destx, &desty, &srcx, &srcy, &w, &h);
2723         IMB_rectblend(clonebuf, ibuf, destx, desty, srcx, srcy, w, h,
2724                 IMB_BLEND_COPY_RGB);
2725         IMB_rectblend(clonebuf, ibufb, destx, desty, destx, desty, w, h,
2726                 IMB_BLEND_COPY_ALPHA);
2727
2728         return clonebuf;
2729 }
2730
2731 static void imapaint_convert_brushco(ImBuf *ibufb, float *pos, int *ipos)
2732 {
2733         ipos[0]= (int)(pos[0] - ibufb->x/2);
2734         ipos[1]= (int)(pos[1] - ibufb->y/2);
2735 }
2736
2737 /* dosnt run for projection painting
2738  * only the old style painting in the 3d view */
2739 static int imapaint_paint_op(void *state, ImBuf *ibufb, float *lastpos, float *pos)
2740 {
2741         ImagePaintState *s= ((ImagePaintState*)state);
2742         ImBuf *clonebuf= NULL;
2743         short torus= s->brush->flag & BRUSH_TORUS;
2744         short blend= s->blend;
2745         float *offset= s->brush->clone.offset;
2746         float liftpos[2];
2747         int bpos[2], blastpos[2], bliftpos[2];
2748
2749         imapaint_convert_brushco(ibufb, pos, bpos);
2750
2751         /* lift from canvas */
2752         if(s->tool == PAINT_TOOL_SOFTEN) {
2753                 imapaint_lift_soften(s->canvas, ibufb, bpos, torus);
2754         }
2755         else if(s->tool == PAINT_TOOL_SMEAR) {
2756                 if (lastpos[0]==pos[0] && lastpos[1]==pos[1])
2757                         return 0;
2758
2759                 imapaint_convert_brushco(ibufb, lastpos, blastpos);
2760                 imapaint_lift_smear(s->canvas, ibufb, blastpos);
2761         }
2762         else if(s->tool == PAINT_TOOL_CLONE && s->clonecanvas) {
2763                 liftpos[0]= pos[0] - offset[0]*s->canvas->x;
2764                 liftpos[1]= pos[1] - offset[1]*s->canvas->y;
2765
2766                 imapaint_convert_brushco(ibufb, liftpos, bliftpos);
2767                 clonebuf= imapaint_lift_clone(s->clonecanvas, ibufb, bliftpos);
2768         }
2769
2770         imapaint_dirty_region(s->image, s->canvas, bpos[0], bpos[1], ibufb->x, ibufb->y);
2771
2772         /* blend into canvas */
2773         if(torus)
2774                 IMB_rectblend_torus(s->canvas, (clonebuf)? clonebuf: ibufb,
2775                         bpos[0], bpos[1], 0, 0, ibufb->x, ibufb->y, blend);
2776         else
2777                 IMB_rectblend(s->canvas, (clonebuf)? clonebuf: ibufb,
2778                         bpos[0], bpos[1], 0, 0, ibufb->x, ibufb->y, blend);
2779                         
2780         if(clonebuf) IMB_freeImBuf(clonebuf);
2781
2782         return 1;
2783 }
2784
2785 /* 2D ImagePaint */
2786
2787 static void imapaint_compute_uvco(short *mval, float *uv)
2788 {
2789         areamouseco_to_ipoco(G.v2d, mval, &uv[0], &uv[1]);
2790 }
2791
2792 /* 3D TexturePaint */
2793
2794 int facesel_face_pick(Mesh *me, short *mval, unsigned int *index, short rect);
2795 void texpaint_pick_uv(Object *ob, Mesh *mesh, unsigned int faceindex, short *xy, float *mousepos);
2796
2797 static int texpaint_break_stroke(float *prevuv, float *fwuv, float *bkuv, float *uv)
2798 {
2799         float d1[2], d2[2];
2800         float mismatch = Vec2Lenf(fwuv, uv);
2801         float len1 = Vec2Lenf(prevuv, fwuv);
2802         float len2 = Vec2Lenf(bkuv, uv);
2803
2804         Vec2Subf(d1, fwuv, prevuv);
2805         Vec2Subf(d2, uv, bkuv);
2806
2807         return ((Inp2f(d1, d2) < 0.0f) || (mismatch > MAX2(len1, len2)*2));
2808 }
2809
2810 /* ImagePaint Common */
2811
2812 static int imapaint_canvas_set(ImagePaintState *s, Image *ima)
2813 {
2814         ImBuf *ibuf= BKE_image_get_ibuf(ima, G.sima?&G.sima->iuser:NULL);
2815         
2816         /* verify that we can paint and set canvas */
2817         if(ima->packedfile && ima->rr) {
2818                 s->warnpackedfile = ima->id.name + 2;
2819                 return 0;
2820         }       
2821         else if(ibuf && ibuf->channels!=4) {
2822                 s->warnmultifile = ima->id.name + 2;
2823                 return 0;
2824         }
2825         else if(!ima || !ibuf || !(ibuf->rect || ibuf->rect_float))
2826                 return 0;
2827
2828         s->image= ima;
2829         s->canvas= ibuf;
2830
2831         /* set clone canvas */
2832         if(s->tool == PAINT_TOOL_CLONE) {
2833                 ima= s->brush->clone.image;
2834                 ibuf= BKE_image_get_ibuf(ima, G.sima?&G.sima->iuser:NULL);
2835                 
2836                 if(!ima || !ibuf || !(ibuf->rect || ibuf->rect_float))
2837                         return 0;
2838
2839                 s->clonecanvas= ibuf;
2840
2841                 if(s->canvas->rect_float && !s->clonecanvas->rect_float) {
2842                         /* temporarily add float rect for cloning */
2843                         IMB_float_from_rect(s->clonecanvas);
2844                         s->clonefreefloat= 1;
2845                 }
2846                 else if(!s->canvas->rect_float && !s->clonecanvas->rect)
2847                         IMB_rect_from_float(s->clonecanvas);
2848         }
2849
2850         return 1;
2851 }
2852
2853 static void imapaint_canvas_free(ImagePaintState *s)
2854 {
2855         if (s->clonefreefloat)
2856                 imb_freerectfloatImBuf(s->clonecanvas);
2857 }
2858
2859 static int imapaint_paint_sub_stroke(ImagePaintState *s, BrushPainter *painter, Image *image, short texpaint, float *uv, double time, int update, float pressure)
2860 {
2861         ImBuf *ibuf= BKE_image_get_ibuf(image, G.sima?&G.sima->iuser:NULL);
2862         float pos[2];
2863
2864         if(!ibuf)
2865                 return 0;
2866
2867         pos[0] = uv[0]*ibuf->x;
2868         pos[1] = uv[1]*ibuf->y;
2869
2870         brush_painter_require_imbuf(painter, ((ibuf->rect_float)? 1: 0), 0, 0);
2871
2872         if (brush_painter_paint(painter, imapaint_paint_op, pos, time, pressure, s)) {
2873                 if (update)
2874                         imapaint_image_update(image, ibuf, texpaint);
2875                 return 1;
2876         }
2877         else return 0;
2878 }
2879
2880 static float Vec2Lenf_nosqrt(float *v1, float *v2)
2881 {
2882         float x, y;
2883
2884         x = v1[0]-v2[0];
2885         y = v1[1]-v2[1];
2886         return x*x+y*y;
2887 }
2888
2889 static float Vec2Lenf_nosqrt_other(float *v1, float v2_1, float v2_2)
2890 {
2891         float x, y;
2892
2893         x = v1[0]-v2_1;
2894         y = v1[1]-v2_2;
2895         return x*x+y*y;
2896 }
2897
2898 /* note, use a squared value so we can use Vec2Lenf_nosqrt
2899  * be sure that you have done a bounds check first or this may fail */
2900 /* only give bucket_bounds as an arg because we need it elsewhere */
2901 static int project_bucket_circle_isect(ProjectPaintState *ps, int bucket_x, int bucket_y, float cent[2], float radius_squared, float bucket_bounds[4])
2902 {
2903         // printf("%d %d - %f %f %f %f - %f %f \n", bucket_x, bucket_y, bucket_bounds[0], bucket_bounds[1], bucket_bounds[2], bucket_bounds[3], cent[0], cent[1]);
2904
2905         /* first check if we are INSIDE the bucket */
2906         /* if ( bucket_bounds[PROJ_BUCKET_LEFT] <=      cent[0] &&
2907                         bucket_bounds[PROJ_BUCKET_RIGHT] >=     cent[0] &&
2908                         bucket_bounds[PROJ_BUCKET_BOTTOM] <=    cent[1] &&
2909                         bucket_bounds[PROJ_BUCKET_TOP] >=       cent[1] )
2910         {
2911                 return 1;
2912         }*/
2913         
2914         /* Would normally to a simple intersection test, however we know the bounds of these 2 alredy intersect 
2915          * so we only need to test if the center is inside the vertical or horizontal bounds on either axis,
2916          * this is even less work then an intersection test */
2917         if (  ( bucket_bounds[PROJ_BUCKET_LEFT] <=              cent[0] &&
2918                         bucket_bounds[PROJ_BUCKET_RIGHT] >=             cent[0]) ||
2919                   (     bucket_bounds[PROJ_BUCKET_BOTTOM] <=    cent[1] &&
2920                         bucket_bounds[PROJ_BUCKET_TOP] >=               cent[1]) )
2921         {
2922                 return 1;
2923         }
2924          
2925         /* out of bounds left */
2926         if (cent[0] < bucket_bounds[PROJ_BUCKET_LEFT]) {
2927                 /* lower left out of radius test */
2928                 if (cent[1] < bucket_bounds[PROJ_BUCKET_BOTTOM]) {
2929                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds[PROJ_BUCKET_LEFT], bucket_bounds[PROJ_BUCKET_BOTTOM]) < radius_squared) ? 1 : 0;
2930                 } 
2931                 /* top left test */
2932                 else if (cent[1] > bucket_bounds[PROJ_BUCKET_TOP]) {
2933                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds[PROJ_BUCKET_LEFT], bucket_bounds[PROJ_BUCKET_TOP]) < radius_squared) ? 1 : 0;
2934                 }
2935         }
2936         else if (cent[0] > bucket_bounds[PROJ_BUCKET_RIGHT]) {
2937                 /* lower right out of radius test */
2938                 if (cent[1] < bucket_bounds[PROJ_BUCKET_BOTTOM]) {
2939                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds[PROJ_BUCKET_RIGHT], bucket_bounds[PROJ_BUCKET_BOTTOM]) < radius_squared) ? 1 : 0;
2940                 } 
2941                 /* top right test */
2942                 else if (cent[1] > bucket_bounds[PROJ_BUCKET_TOP]) {
2943                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds[PROJ_BUCKET_RIGHT], bucket_bounds[PROJ_BUCKET_TOP]) < radius_squared) ? 1 : 0;
2944                 }
2945         }
2946         
2947         return 0;
2948 }
2949
2950 static void partial_redraw_array_init(ImagePaintPartialRedraw *pr)
2951 {
2952         int tot = PROJ_BOUNDBOX_SQUARED;
2953         while (tot--) {
2954                 pr->x1 = 10000000;
2955                 pr->y1 = 10000000;
2956                 
2957                 pr->x2 = -1;
2958                 pr->y2 = -1;
2959                 
2960                 pr->enabled = 1;
2961                 
2962                 pr++;
2963         }
2964 }
2965
2966 static void partial_redraw_array_merge(ImagePaintPartialRedraw *pr, ImagePaintPartialRedraw *pr_other, int tot)
2967 {
2968         while (tot--) {
2969                 pr->x1 = MIN2(pr->x1, pr_other->x1);
2970                 pr->y1 = MIN2(pr->y1, pr_other->y1);
2971                 
2972                 pr->x2 = MAX2(pr->x2, pr_other->x2);
2973                 pr->y2 = MAX2(pr->y2, pr_other->y2);
2974                 
2975                 pr++; pr_other++;
2976         }
2977 }
2978
2979 /* Loop over all images on this mesh and update any we have touched */
2980 static int imapaint_refresh_tagged(ProjectPaintState *ps)
2981 {
2982         ImagePaintPartialRedraw *pr;
2983         ProjectPaintImage *projIma;
2984         int a,i;
2985         int redraw = 0;
2986         
2987         
2988         for (a=0, projIma=ps->projImages; a < ps->image_tot; a++, projIma++) {
2989                 if (projIma->touch) {
2990                         /* look over each bound cell */
2991                         for (i=0; i<PROJ_BOUNDBOX_SQUARED; i++) {
2992                                 pr = &(projIma->partRedrawRect[i]);
2993                                 if (pr->x2 != -1) { /* TODO - use 'enabled' ? */
2994                                         imapaintpartial = *pr;
2995                                         imapaint_image_update(projIma->ima, projIma->ibuf, 1 /*texpaint*/ );
2996                                         redraw = 1;
2997                                 }
2998                         }
2999                         
3000                         projIma->touch = 0; /* clear for reuse */
3001                 }
3002         }
3003         
3004         return redraw;
3005 }
3006
3007 static int bucket_iter_init(ProjectPaintState *ps, float mval_f[2])
3008 {
3009         float min_brush[2], max_brush[2];
3010         
3011         min_brush[0] = mval_f[0] - (ps->brush->size/2);
3012         min_brush[1] = mval_f[1] - (ps->brush->size/2);
3013         
3014         max_brush[0] = mval_f[0] + (ps->brush->size/2);
3015         max_brush[1] = mval_f[1] + (ps->brush->size/2);
3016         
3017         /* offset to make this a valid bucket index */
3018         project_paint_rect(ps, min_brush, max_brush, ps->bucket_min, ps->bucket_max);
3019         
3020         /* mouse outside the model areas? */
3021         if (ps->bucket_min[0]==ps->bucket_max[0] || ps->bucket_min[1]==ps->bucket_max[1]) {
3022                 return 0;
3023         }
3024         
3025         ps->context_bucket_x = ps->bucket_min[0];
3026         ps->context_bucket_y = ps->bucket_min[1];
3027 #ifdef PROJ_DEBUG_PRINT_THREADS
3028         printf("Initializing Values %d %d!", ps->bucket_min[0], ps->bucket_min[1]);
3029 #endif
3030         return 1;
3031 }
3032
3033 static int bucket_iter_next(ProjectPaintState *ps, int *bucket_index, float bucket_bounds[4], float mval_f[2])
3034 {
3035         if (ps->thread_tot > 1)
3036                 BLI_lock_thread(LOCK_CUSTOM1);
3037         
3038         //printf("%d %d \n", ps->context_bucket_x, ps->context_bucket_y);
3039         
3040         for ( ; ps->context_bucket_y < ps->bucket_max[1]; ps->context_bucket_y++) {
3041                 for ( ; ps->context_bucket_x < ps->bucket_max[0]; ps->context_bucket_x++) {
3042                         
3043                         /* use bucket_bounds for project_bucket_circle_isect and project_paint_bucket_init*/
3044                         project_bucket_bounds(ps, ps->context_bucket_x, ps->context_bucket_y, bucket_bounds);
3045                         
3046                         if (project_bucket_circle_isect(ps, ps->context_bucket_x, ps->context_bucket_y, mval_f, ps->brush->size * ps->brush->size, bucket_bounds)) {
3047                                 *bucket_index = ps->context_bucket_x + (ps->context_bucket_y * ps->buckets_x);
3048 #ifdef PROJ_DEBUG_PRINT_THREADS
3049                                 printf(" --- %d %d \n", ps->context_bucket_x, ps->context_bucket_y);
3050 #endif
3051                                 ps->context_bucket_x++;
3052                                 
3053                                 if (ps->thread_tot > 1)
3054                                         BLI_unlock_thread(LOCK_CUSTOM1);
3055                                 
3056                                 return 1;
3057                         }
3058                 }
3059                 ps->context_bucket_x = ps->bucket_min[0];
3060         }
3061         
3062         if (ps->thread_tot > 1)
3063                 BLI_unlock_thread(LOCK_CUSTOM1);
3064         return 0;
3065 }
3066
3067 static int imapaint_paint_sub_stroke_project(
3068                                 ProjectPaintState *ps,
3069                                 BrushPainter *painter,
3070                                 short prevmval[2],
3071                                 short mval[2],
3072                             &