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