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