ok, apparently didn't commit this either. apparently includes a merge with trunk...
[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_math.h"
44 #include "BLI_blenlib.h"
45 #include "BLI_dynstr.h"
46 #include "BLI_linklist.h"
47 #include "BLI_memarena.h"
48 #include "PIL_time.h"
49 #include "BLI_threads.h"
50
51 #include "IMB_imbuf.h"
52 #include "IMB_imbuf_types.h"
53
54 #include "DNA_brush_types.h"
55 #include "DNA_image_types.h"
56 #include "DNA_mesh_types.h"
57 #include "DNA_meshdata_types.h"
58 #include "DNA_node_types.h"
59 #include "DNA_object_types.h"
60 #include "DNA_scene_types.h"
61 #include "DNA_screen_types.h"
62 #include "DNA_space_types.h"
63 #include "DNA_userdef_types.h"
64 #include "DNA_view3d_types.h"
65 #include "DNA_windowmanager_types.h"
66
67 #include "BKE_context.h"
68 #include "BKE_brush.h"
69 #include "BKE_global.h"
70 #include "BKE_image.h"
71 #include "BKE_main.h"
72 #include "BKE_mesh.h"
73 #include "BKE_node.h"
74 #include "BKE_paint.h"
75 #include "BKE_utildefines.h"
76 #include "BKE_DerivedMesh.h"
77 #include "BKE_report.h"
78 #include "BKE_depsgraph.h"
79
80 #include "BIF_gl.h"
81 #include "BIF_glutil.h"
82
83 #include "UI_interface.h"
84 #include "UI_view2d.h"
85
86 #include "ED_image.h"
87 #include "ED_object.h"
88 #include "ED_screen.h"
89 #include "ED_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 (isect_point_tri_v2(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 (isect_point_tri_v2(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                 interp_v2_v2v2v2(uv, tf->uv[0], tf->uv[1], tf->uv[2], w);
738         }
739         else { /* QUAD */
740                 interp_v2_v2v2v2(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 (!isect_point_tri_v2(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)       interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v3].co, ps->dm_mvert[mf->v4].co, w);
862         else            interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, w);
863         
864         if(!view3d_test_clipping(ps->rv3d, wco, 1)) {
865                 return 1;
866         }
867         
868         return -1;
869 }
870
871
872 /* Check if a screenspace location is occluded by any other faces
873  * check, pixelScreenCo must be in screenspace, its Z-Depth only needs to be used for comparison
874  * and dosn't need to be correct in relation to X and Y coords (this is the case in perspective view) */
875 static int project_bucket_point_occluded(const ProjPaintState *ps, LinkNode *bucketFace, const int orig_face, float pixelScreenCo[4])
876 {
877         MFace *mf;
878         int face_index;
879         int isect_ret;
880         float w[3]; /* not needed when clipping */
881         
882         /* we could return 0 for 1 face buckets, as long as this function assumes
883          * that the point its testing is only every originated from an existing face */
884
885         for (; bucketFace; bucketFace = bucketFace->next) {
886                 face_index = GET_INT_FROM_POINTER(bucketFace->link);
887
888                 if (orig_face != face_index) {
889                         mf = ps->dm_mface + face_index;
890                         if(ps->rv3d->rflag & RV3D_CLIPPING)
891                                 isect_ret = project_paint_occlude_ptv_clip(ps, mf, pixelScreenCo, ps->screenCoords[mf->v1], ps->screenCoords[mf->v2], ps->screenCoords[mf->v3], 0);
892                         else
893                                 isect_ret = project_paint_occlude_ptv(pixelScreenCo, ps->screenCoords[mf->v1], ps->screenCoords[mf->v2], ps->screenCoords[mf->v3], w, ps->is_ortho);
894
895                         /* Note, if isect_ret==-1 then we dont want to test the other side of the quad */
896                         if (isect_ret==0 && mf->v4) {
897                                 if(ps->rv3d->rflag & RV3D_CLIPPING)
898                                         isect_ret = project_paint_occlude_ptv_clip(ps, mf, pixelScreenCo, ps->screenCoords[mf->v1], ps->screenCoords[mf->v3], ps->screenCoords[mf->v4], 1);
899                                 else
900                                         isect_ret = project_paint_occlude_ptv(pixelScreenCo, ps->screenCoords[mf->v1], ps->screenCoords[mf->v3], ps->screenCoords[mf->v4], w, ps->is_ortho);
901                         }
902                         if (isect_ret>=1) {
903                                 /* TODO - we may want to cache the first hit,
904                                  * it is not possible to swap the face order in the list anymore */
905                                 return 1;
906                         }
907                 }
908         }
909         return 0;
910 }
911
912 /* basic line intersection, could move to arithb.c, 2 points with a horiz line
913  * 1 for an intersection, 2 if the first point is aligned, 3 if the second point is aligned */
914 #define ISECT_TRUE 1
915 #define ISECT_TRUE_P1 2
916 #define ISECT_TRUE_P2 3
917 static int line_isect_y(const float p1[2], const float p2[2], const float y_level, float *x_isect)
918 {
919         float y_diff;
920         
921         if (y_level==p1[1]) { /* are we touching the first point? - no interpolation needed */
922                 *x_isect = p1[0];
923                 return ISECT_TRUE_P1;
924         }
925         if (y_level==p2[1]) { /* are we touching the second point? - no interpolation needed */
926                 *x_isect = p2[0];
927                 return ISECT_TRUE_P2;
928         }
929         
930         y_diff= fabsf(p1[1]-p2[1]); /* yuck, horizontal line, we cant do much here */
931         
932         if (y_diff < 0.000001f) {
933                 *x_isect = (p1[0]+p2[0]) * 0.5f;
934                 return ISECT_TRUE;              
935         }
936         
937         if (p1[1] > y_level && p2[1] < y_level) {
938                 *x_isect = (p2[0]*(p1[1]-y_level) + p1[0]*(y_level-p2[1])) / y_diff;  /*(p1[1]-p2[1]);*/
939                 return ISECT_TRUE;
940         }
941         else if (p1[1] < y_level && p2[1] > y_level) {
942                 *x_isect = (p2[0]*(y_level-p1[1]) + p1[0]*(p2[1]-y_level)) / y_diff;  /*(p2[1]-p1[1]);*/
943                 return ISECT_TRUE;
944         }
945         else {
946                 return 0;
947         }
948 }
949
950 static int line_isect_x(const float p1[2], const float p2[2], const float x_level, float *y_isect)
951 {
952         float x_diff;
953         
954         if (x_level==p1[0]) { /* are we touching the first point? - no interpolation needed */
955                 *y_isect = p1[1];
956                 return ISECT_TRUE_P1;
957         }
958         if (x_level==p2[0]) { /* are we touching the second point? - no interpolation needed */
959                 *y_isect = p2[1];
960                 return ISECT_TRUE_P2;
961         }
962         
963         x_diff= fabsf(p1[0]-p2[0]); /* yuck, horizontal line, we cant do much here */
964         
965         if (x_diff < 0.000001) { /* yuck, vertical line, we cant do much here */
966                 *y_isect = (p1[0]+p2[0]) * 0.5f;
967                 return ISECT_TRUE;              
968         }
969         
970         if (p1[0] > x_level && p2[0] < x_level) {
971                 *y_isect = (p2[1]*(p1[0]-x_level) + p1[1]*(x_level-p2[0])) / x_diff; /*(p1[0]-p2[0]);*/
972                 return ISECT_TRUE;
973         }
974         else if (p1[0] < x_level && p2[0] > x_level) {
975                 *y_isect = (p2[1]*(x_level-p1[0]) + p1[1]*(p2[0]-x_level)) / x_diff; /*(p2[0]-p1[0]);*/
976                 return ISECT_TRUE;
977         }
978         else {
979                 return 0;
980         }
981 }
982
983 /* simple func use for comparing UV locations to check if there are seams.
984  * Its possible this gives incorrect results, when the UVs for 1 face go into the next 
985  * tile, but do not do this for the adjacent face, it could return a false positive.
986  * This is so unlikely that Id not worry about it. */
987 #ifndef PROJ_DEBUG_NOSEAMBLEED
988 static int cmp_uv(const float vec2a[2], const float vec2b[2])
989 {
990         /* if the UV's are not between 0.0 and 1.0 */
991         float xa = (float)fmodf(vec2a[0], 1.0f);
992         float ya = (float)fmodf(vec2a[1], 1.0f);
993         
994         float xb = (float)fmodf(vec2b[0], 1.0f);
995         float yb = (float)fmodf(vec2b[1], 1.0f);        
996         
997         if (xa < 0.0f) xa += 1.0f;
998         if (ya < 0.0f) ya += 1.0f;
999         
1000         if (xb < 0.0f) xb += 1.0f;
1001         if (yb < 0.0f) yb += 1.0f;
1002         
1003         return ((fabsf(xa-xb) < PROJ_GEOM_TOLERANCE) && (fabsf(ya-yb) < PROJ_GEOM_TOLERANCE)) ? 1:0;
1004 }
1005 #endif
1006
1007 /* set min_px and max_px to the image space bounds of the UV coords 
1008  * return zero if there is no area in the returned rectangle */
1009 #ifndef PROJ_DEBUG_NOSEAMBLEED
1010 static int pixel_bounds_uv(
1011                 const float uv1[2], const float uv2[2], const float uv3[2], const float uv4[2],
1012                 rcti *bounds_px,
1013                 const int ibuf_x, const int ibuf_y,
1014                 int is_quad
1015 ) {
1016         float min_uv[2], max_uv[2]; /* UV bounds */
1017         
1018         INIT_MINMAX2(min_uv, max_uv);
1019         
1020         DO_MINMAX2(uv1, min_uv, max_uv);
1021         DO_MINMAX2(uv2, min_uv, max_uv);
1022         DO_MINMAX2(uv3, min_uv, max_uv);
1023         if (is_quad)
1024                 DO_MINMAX2(uv4, min_uv, max_uv);
1025         
1026         bounds_px->xmin = (int)(ibuf_x * min_uv[0]);
1027         bounds_px->ymin = (int)(ibuf_y * min_uv[1]);
1028         
1029         bounds_px->xmax = (int)(ibuf_x * max_uv[0]) +1;
1030         bounds_px->ymax = (int)(ibuf_y * max_uv[1]) +1;
1031         
1032         /*printf("%d %d %d %d \n", min_px[0], min_px[1], max_px[0], max_px[1]);*/
1033         
1034         /* face uses no UV area when quantized to pixels? */
1035         return (bounds_px->xmin == bounds_px->xmax || bounds_px->ymin == bounds_px->ymax) ? 0 : 1;
1036 }
1037 #endif
1038
1039 static int pixel_bounds_array(float (* uv)[2], rcti *bounds_px, const int ibuf_x, const int ibuf_y, int tot)
1040 {
1041         float min_uv[2], max_uv[2]; /* UV bounds */
1042         
1043         if (tot==0) {
1044                 return 0;
1045         }
1046         
1047         INIT_MINMAX2(min_uv, max_uv);
1048         
1049         while (tot--) {
1050                 DO_MINMAX2((*uv), min_uv, max_uv);
1051                 uv++;
1052         }
1053         
1054         bounds_px->xmin = (int)(ibuf_x * min_uv[0]);
1055         bounds_px->ymin = (int)(ibuf_y * min_uv[1]);
1056         
1057         bounds_px->xmax = (int)(ibuf_x * max_uv[0]) +1;
1058         bounds_px->ymax = (int)(ibuf_y * max_uv[1]) +1;
1059         
1060         /*printf("%d %d %d %d \n", min_px[0], min_px[1], max_px[0], max_px[1]);*/
1061         
1062         /* face uses no UV area when quantized to pixels? */
1063         return (bounds_px->xmin == bounds_px->xmax || bounds_px->ymin == bounds_px->ymax) ? 0 : 1;
1064 }
1065
1066 #ifndef PROJ_DEBUG_NOSEAMBLEED
1067
1068 /* This function returns 1 if this face has a seam along the 2 face-vert indicies
1069  * 'orig_i1_fidx' and 'orig_i2_fidx' */
1070 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)
1071 {
1072         LinkNode *node;
1073         int face_index;
1074         int i1, i2;
1075         int i1_fidx = -1, i2_fidx = -1; /* index in face */
1076         MFace *mf;
1077         MTFace *tf;
1078         const MFace *orig_mf = ps->dm_mface + orig_face;  
1079         const MTFace *orig_tf = ps->dm_mtface + orig_face;
1080         
1081         /* vert indicies from face vert order indicies */
1082         i1 = (*(&orig_mf->v1 + orig_i1_fidx));
1083         i2 = (*(&orig_mf->v1 + orig_i2_fidx));
1084         
1085         for (node = ps->vertFaces[i1]; node; node = node->next) {
1086                 face_index = GET_INT_FROM_POINTER(node->link);
1087
1088                 if (face_index != orig_face) {
1089                         mf = ps->dm_mface + face_index;
1090                         /* could check if the 2 faces images match here,
1091                          * but then there wouldn't be a way to return the opposite face's info */
1092                         
1093                         
1094                         /* We need to know the order of the verts in the adjacent face 
1095                          * set the i1_fidx and i2_fidx to (0,1,2,3) */
1096                         if              (mf->v1==i1)                    i1_fidx = 0;
1097                         else if (mf->v2==i1)                    i1_fidx = 1;
1098                         else if (mf->v3==i1)                    i1_fidx = 2;
1099                         else if (mf->v4 && mf->v4==i1)  i1_fidx = 3;
1100                         
1101                         if              (mf->v1==i2)                    i2_fidx = 0;
1102                         else if (mf->v2==i2)                    i2_fidx = 1;
1103                         else if (mf->v3==i2)                    i2_fidx = 2;
1104                         else if (mf->v4 && mf->v4==i2)  i2_fidx = 3;
1105                         
1106                         /* Only need to check if 'i2_fidx' is valid because we know i1_fidx is the same vert on both faces */
1107                         if (i2_fidx != -1) {
1108                                 /* This IS an adjacent face!, now lets check if the UVs are ok */
1109                                 tf = ps->dm_mtface + face_index;
1110                                 
1111                                 /* set up the other face */
1112                                 *other_face = face_index;
1113                                 *orig_fidx = (i1_fidx < i2_fidx) ? i1_fidx : i2_fidx;
1114                                 
1115                                 /* first test if they have the same image */
1116                                 if (    (orig_tf->tpage == tf->tpage) &&
1117                                                 cmp_uv(orig_tf->uv[orig_i1_fidx], tf->uv[i1_fidx]) &&
1118                                                 cmp_uv(orig_tf->uv[orig_i2_fidx], tf->uv[i2_fidx]) )
1119                                 {
1120                                         // printf("SEAM (NONE)\n");
1121                                         return 0;
1122                                         
1123                                 }
1124                                 else {
1125                                         // printf("SEAM (UV GAP)\n");
1126                                         return 1;
1127                                 }
1128                         }
1129                 }
1130         }
1131         // printf("SEAM (NO FACE)\n");
1132         *other_face = -1;
1133         return 1;
1134 }
1135
1136 /* Calculate outset UV's, this is not the same as simply scaling the UVs,
1137  * since the outset coords are a margin that keep an even distance from the original UV's,
1138  * note that the image aspect is taken into account */
1139 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)
1140 {
1141         float a1, a2, a3, a4=0.0f;
1142         float puv[4][2]; /* pixelspace uv's */
1143         float no1[2], no2[2], no3[2], no4[2]; /* normals */
1144         float dir1[2], dir2[2], dir3[2], dir4[2];
1145         float ibuf_x_inv = 1.0f / (float)ibuf_x; 
1146         float ibuf_y_inv = 1.0f / (float)ibuf_y; 
1147         
1148         /* make UV's in pixel space so we can */
1149         puv[0][0] = orig_uv[0][0] * ibuf_x;
1150         puv[0][1] = orig_uv[0][1] * ibuf_y;
1151         
1152         puv[1][0] = orig_uv[1][0] * ibuf_x;
1153         puv[1][1] = orig_uv[1][1] * ibuf_y;
1154         
1155         puv[2][0] = orig_uv[2][0] * ibuf_x;
1156         puv[2][1] = orig_uv[2][1] * ibuf_y;
1157         
1158         if (is_quad) {
1159                 puv[3][0] = orig_uv[3][0] * ibuf_x;
1160                 puv[3][1] = orig_uv[3][1] * ibuf_y;
1161         }
1162         
1163         /* face edge directions */
1164         sub_v2_v2v2(dir1, puv[1], puv[0]);
1165         sub_v2_v2v2(dir2, puv[2], puv[1]);
1166         normalize_v2(dir1);
1167         normalize_v2(dir2);
1168         
1169         if (is_quad) {
1170                 sub_v2_v2v2(dir3, puv[3], puv[2]);
1171                 sub_v2_v2v2(dir4, puv[0], puv[3]);
1172                 normalize_v2(dir3);
1173                 normalize_v2(dir4);
1174         }
1175         else {
1176                 sub_v2_v2v2(dir3, puv[0], puv[2]);
1177                 normalize_v2(dir3);
1178         }
1179         
1180         if (is_quad) {
1181                 a1 = shell_angle_to_dist(angle_normalized_v2v2(dir4, dir1));
1182                 a2 = shell_angle_to_dist(angle_normalized_v2v2(dir1, dir2));
1183                 a3 = shell_angle_to_dist(angle_normalized_v2v2(dir2, dir3));
1184                 a4 = shell_angle_to_dist(angle_normalized_v2v2(dir3, dir4));
1185         }
1186         else {
1187                 a1 = shell_angle_to_dist(angle_normalized_v2v2(dir3, dir1));
1188                 a2 = shell_angle_to_dist(angle_normalized_v2v2(dir1, dir2));
1189                 a3 = shell_angle_to_dist(angle_normalized_v2v2(dir2, dir3));
1190         }
1191         
1192         if (is_quad) {
1193                 sub_v2_v2v2(no1, dir4, dir1);
1194                 sub_v2_v2v2(no2, dir1, dir2);
1195                 sub_v2_v2v2(no3, dir2, dir3);
1196                 sub_v2_v2v2(no4, dir3, dir4);
1197                 normalize_v2(no1);
1198                 normalize_v2(no2);
1199                 normalize_v2(no3);
1200                 normalize_v2(no4);
1201                 mul_v2_fl(no1, a1*scaler);
1202                 mul_v2_fl(no2, a2*scaler);
1203                 mul_v2_fl(no3, a3*scaler);
1204                 mul_v2_fl(no4, a4*scaler);
1205                 add_v2_v2v2(outset_uv[0], puv[0], no1);
1206                 add_v2_v2v2(outset_uv[1], puv[1], no2);
1207                 add_v2_v2v2(outset_uv[2], puv[2], no3);
1208                 add_v2_v2v2(outset_uv[3], puv[3], no4);
1209                 outset_uv[0][0] *= ibuf_x_inv;
1210                 outset_uv[0][1] *= ibuf_y_inv;
1211                 
1212                 outset_uv[1][0] *= ibuf_x_inv;
1213                 outset_uv[1][1] *= ibuf_y_inv;
1214                 
1215                 outset_uv[2][0] *= ibuf_x_inv;
1216                 outset_uv[2][1] *= ibuf_y_inv;
1217                 
1218                 outset_uv[3][0] *= ibuf_x_inv;
1219                 outset_uv[3][1] *= ibuf_y_inv;
1220         }
1221         else {
1222                 sub_v2_v2v2(no1, dir3, dir1);
1223                 sub_v2_v2v2(no2, dir1, dir2);
1224                 sub_v2_v2v2(no3, dir2, dir3);
1225                 normalize_v2(no1);
1226                 normalize_v2(no2);
1227                 normalize_v2(no3);
1228                 mul_v2_fl(no1, a1*scaler);
1229                 mul_v2_fl(no2, a2*scaler);
1230                 mul_v2_fl(no3, a3*scaler);
1231                 add_v2_v2v2(outset_uv[0], puv[0], no1);
1232                 add_v2_v2v2(outset_uv[1], puv[1], no2);
1233                 add_v2_v2v2(outset_uv[2], puv[2], no3);
1234                 outset_uv[0][0] *= ibuf_x_inv;
1235                 outset_uv[0][1] *= ibuf_y_inv;
1236                 
1237                 outset_uv[1][0] *= ibuf_x_inv;
1238                 outset_uv[1][1] *= ibuf_y_inv;
1239                 
1240                 outset_uv[2][0] *= ibuf_x_inv;
1241                 outset_uv[2][1] *= ibuf_y_inv;
1242         }
1243 }
1244
1245 /* 
1246  * Be tricky with flags, first 4 bits are PROJ_FACE_SEAM1 to 4, last 4 bits are PROJ_FACE_NOSEAM1 to 4
1247  * 1<<i - where i is (0-3) 
1248  * 
1249  * If we're multithreadng, make sure threads are locked when this is called
1250  */
1251 static void project_face_seams_init(const ProjPaintState *ps, const int face_index, const int is_quad)
1252 {
1253         int other_face, other_fidx; /* vars for the other face, we also set its flag */
1254         int fidx1 = is_quad ? 3 : 2;
1255         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 */
1256         
1257         do {
1258                 if ((ps->faceSeamFlags[face_index] & (1<<fidx1|16<<fidx1)) == 0) {
1259                         if (check_seam(ps, face_index, fidx1, fidx2, &other_face, &other_fidx)) {
1260                                 ps->faceSeamFlags[face_index] |= 1<<fidx1;
1261                                 if (other_face != -1)
1262                                         ps->faceSeamFlags[other_face] |= 1<<other_fidx;
1263                         }
1264                         else {
1265                                 ps->faceSeamFlags[face_index] |= 16<<fidx1;
1266                                 if (other_face != -1)
1267                                         ps->faceSeamFlags[other_face] |= 16<<other_fidx; /* second 4 bits for disabled */
1268                         }
1269                 }
1270                 
1271                 fidx2 = fidx1;
1272         } while (fidx1--);
1273 }
1274 #endif // PROJ_DEBUG_NOSEAMBLEED
1275
1276
1277 /* TODO - move to arithb.c */
1278
1279 /* little sister we only need to know lambda */
1280 static float lambda_cp_line2(const float p[2], const float l1[2], const float l2[2])
1281 {
1282         float h[2], u[2];
1283         
1284         u[0] = l2[0] - l1[0];
1285         u[1] = l2[1] - l1[1];
1286
1287         h[0] = p[0] - l1[0];
1288         h[1] = p[1] - l1[1];
1289         
1290         return(dot_v2v2(u, h)/dot_v2v2(u, u));
1291 }
1292
1293
1294 /* Converts a UV location to a 3D screenspace location
1295  * Takes a 'uv' and 3 UV coords, and sets the values of pixelScreenCo
1296  * 
1297  * This is used for finding a pixels location in screenspace for painting */
1298 static void screen_px_from_ortho(
1299                 float uv[2],
1300                 float v1co[3], float v2co[3], float v3co[3], /* Screenspace coords */
1301                 float uv1co[2], float uv2co[2], float uv3co[2],
1302                 float pixelScreenCo[4],
1303                 float w[3])
1304 {
1305         BarycentricWeights2f(uv, uv1co, uv2co, uv3co, w);
1306         interp_v3_v3v3v3(pixelScreenCo, v1co, v2co, v3co, w);
1307 }
1308
1309 /* same as screen_px_from_ortho except we need to take into account
1310  * the perspective W coord for each vert */
1311 static void screen_px_from_persp(
1312                 float uv[2],
1313                 float v1co[3], float v2co[3], float v3co[3], /* screenspace coords */
1314                 float uv1co[2], float uv2co[2], float uv3co[2],
1315                 float pixelScreenCo[4],
1316                 float w[3])
1317 {
1318
1319         float wtot_inv, wtot;
1320         BarycentricWeights2f(uv, uv1co, uv2co, uv3co, w);
1321         
1322         /* re-weight from the 4th coord of each screen vert */
1323         w[0] *= v1co[3];
1324         w[1] *= v2co[3];
1325         w[2] *= v3co[3];
1326         
1327         wtot = w[0]+w[1]+w[2];
1328         
1329         if (wtot > 0.0f) {
1330                 wtot_inv = 1.0f / wtot;
1331                 w[0] *= wtot_inv;
1332                 w[1] *= wtot_inv;
1333                 w[2] *= wtot_inv;
1334         }
1335         else {
1336                 w[0] = w[1] = w[2] = 1.0/3.0; /* dummy values for zero area face */
1337         }
1338         /* done re-weighting */
1339         
1340         interp_v3_v3v3v3(pixelScreenCo, v1co, v2co, v3co, w);
1341 }
1342
1343 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])
1344 {
1345         float *uvCo1, *uvCo2, *uvCo3;
1346         float uv_other[2], x, y;
1347         
1348         uvCo1 =  (float *)tf_other->uv[0];
1349         if (side==1) {
1350                 uvCo2 =  (float *)tf_other->uv[2];
1351                 uvCo3 =  (float *)tf_other->uv[3];
1352         }
1353         else {
1354                 uvCo2 =  (float *)tf_other->uv[1];
1355                 uvCo3 =  (float *)tf_other->uv[2];
1356         }
1357         
1358         interp_v2_v2v2v2(uv_other, uvCo1, uvCo2, uvCo3, (float*)w);
1359         
1360         /* use */
1361         uvco_to_wrapped_pxco(uv_other, ibuf_other->x, ibuf_other->y, &x, &y);
1362         
1363         
1364         if (ibuf_other->rect_float) { /* from float to float */
1365                 bilinear_interpolation_color_wrap(ibuf_other, NULL, rgba_f, x, y);
1366         }
1367         else { /* from char to float */
1368                 bilinear_interpolation_color_wrap(ibuf_other, rgba_ub, NULL, x, y);
1369         }
1370                 
1371 }
1372
1373 /* run this outside project_paint_uvpixel_init since pixels with mask 0 dont need init */
1374 float project_paint_uvpixel_mask(
1375                 const ProjPaintState *ps,
1376                 const int face_index,
1377                 const int side,
1378                 const float w[3])
1379 {
1380         float mask;
1381         
1382         /* Image Mask */
1383         if (ps->do_layer_mask) {
1384                 /* another UV layers image is masking this one's */
1385                 ImBuf *ibuf_other;
1386                 const MTFace *tf_other = ps->dm_mtface_mask + face_index;
1387                 
1388                 if (tf_other->tpage && (ibuf_other = BKE_image_get_ibuf(tf_other->tpage, NULL))) {
1389                         /* BKE_image_get_ibuf - TODO - this may be slow */
1390                         unsigned char rgba_ub[4];
1391                         float rgba_f[4];
1392                         
1393                         project_face_pixel(tf_other, ibuf_other, w, side, rgba_ub, rgba_f);
1394                         
1395                         if (ibuf_other->rect_float) { /* from float to float */
1396                                 mask = ((rgba_f[0]+rgba_f[1]+rgba_f[2])/3.0f) * rgba_f[3];
1397                         }
1398                         else { /* from char to float */
1399                                 mask = ((rgba_ub[0]+rgba_ub[1]+rgba_ub[2])/(256*3.0f)) * (rgba_ub[3]/256.0f);
1400                         }
1401                         
1402                         if (!ps->do_layer_mask_inv) /* matching the gimps layer mask black/white rules, white==full opacity */
1403                                 mask = (1.0f - mask);
1404
1405                         if (mask == 0.0f) {
1406                                 return 0.0f;
1407                         }
1408                 }
1409                 else {
1410                         return 0.0f;
1411                 }
1412         } else {
1413                 mask = 1.0f;
1414         }
1415         
1416         /* calculate mask */
1417         if (ps->do_mask_normal) {
1418                 MFace *mf = ps->dm_mface + face_index;
1419                 short *no1, *no2, *no3;
1420                 float no[3], angle;
1421                 no1 = ps->dm_mvert[mf->v1].no;
1422                 if (side==1) {
1423                         no2 = ps->dm_mvert[mf->v3].no;
1424                         no3 = ps->dm_mvert[mf->v4].no;
1425                 }
1426                 else {
1427                         no2 = ps->dm_mvert[mf->v2].no;
1428                         no3 = ps->dm_mvert[mf->v3].no;
1429                 }
1430                 
1431                 no[0] = w[0]*no1[0] + w[1]*no2[0] + w[2]*no3[0];
1432                 no[1] = w[0]*no1[1] + w[1]*no2[1] + w[2]*no3[1];
1433                 no[2] = w[0]*no1[2] + w[1]*no2[2] + w[2]*no3[2];
1434                 normalize_v3(no);
1435                 
1436                 /* now we can use the normal as a mask */
1437                 if (ps->is_ortho) {
1438                         angle = angle_normalized_v3v3((float *)ps->viewDir, no);
1439                 }
1440                 else {
1441                         /* Annoying but for the perspective view we need to get the pixels location in 3D space :/ */
1442                         float viewDirPersp[3];
1443                         float *co1, *co2, *co3;
1444                         co1 = ps->dm_mvert[mf->v1].co;
1445                         if (side==1) {
1446                                 co2 = ps->dm_mvert[mf->v3].co;
1447                                 co3 = ps->dm_mvert[mf->v4].co;
1448                         }
1449                         else {
1450                                 co2 = ps->dm_mvert[mf->v2].co;
1451                                 co3 = ps->dm_mvert[mf->v3].co;
1452                         }
1453
1454                         /* Get the direction from the viewPoint to the pixel and normalize */
1455                         viewDirPersp[0] = (ps->viewPos[0] - (w[0]*co1[0] + w[1]*co2[0] + w[2]*co3[0]));
1456                         viewDirPersp[1] = (ps->viewPos[1] - (w[0]*co1[1] + w[1]*co2[1] + w[2]*co3[1]));
1457                         viewDirPersp[2] = (ps->viewPos[2] - (w[0]*co1[2] + w[1]*co2[2] + w[2]*co3[2]));
1458                         normalize_v3(viewDirPersp);
1459                         
1460                         angle = angle_normalized_v3v3(viewDirPersp, no);
1461                 }
1462                 
1463                 if (angle >= ps->normal_angle) {
1464                         return 0.0f; /* outsize the normal limit*/
1465                 }
1466                 else if (angle > ps->normal_angle_inner) {
1467                         mask *= (ps->normal_angle - angle) / ps->normal_angle_range;
1468                 } /* otherwise no mask normal is needed, were within the limit */
1469         }
1470         
1471         // This only works when the opacity dosnt change while painting, stylus pressure messes with this
1472         // so dont use it.
1473         // if (ps->is_airbrush==0) mask *= ps->brush->alpha;
1474         
1475         return mask;
1476 }
1477
1478 /* run this function when we know a bucket's, face's pixel can be initialized,
1479  * return the ProjPixel which is added to 'ps->bucketRect[bucket_index]' */
1480 static ProjPixel *project_paint_uvpixel_init(
1481                 const ProjPaintState *ps,
1482                 MemArena *arena,
1483                 const ImBuf *ibuf,
1484                 short x_px, short y_px,
1485                 const float mask,
1486                 const int face_index,
1487                 const int image_index,
1488                 const float pixelScreenCo[4],
1489                 const int side,
1490                 const float w[3])
1491 {
1492         ProjPixel *projPixel;
1493         short size;
1494         
1495         /* wrap pixel location */
1496         x_px = x_px % ibuf->x;
1497         if (x_px<0) x_px += ibuf->x;
1498         y_px = y_px % ibuf->y;
1499         if (y_px<0) y_px += ibuf->y;
1500         
1501         if (ps->tool==PAINT_TOOL_CLONE) {
1502                 size = sizeof(ProjPixelClone);
1503         }
1504         else if (ps->tool==PAINT_TOOL_SMEAR) {
1505                 size = sizeof(ProjPixelClone);
1506         }
1507         else {
1508                 size = sizeof(ProjPixel);
1509         }
1510         
1511         projPixel = (ProjPixel *)BLI_memarena_alloc(arena, size);
1512         //memset(projPixel, 0, size);
1513         
1514         if (ibuf->rect_float) {
1515                 projPixel->pixel.f_pt = (float *)ibuf->rect_float + ((x_px + y_px * ibuf->x) * 4);
1516                 projPixel->origColor.f[0] = projPixel->newColor.f[0] = projPixel->pixel.f_pt[0];  
1517                 projPixel->origColor.f[1] = projPixel->newColor.f[1] = projPixel->pixel.f_pt[1];  
1518                 projPixel->origColor.f[2] = projPixel->newColor.f[2] = projPixel->pixel.f_pt[2];  
1519                 projPixel->origColor.f[3] = projPixel->newColor.f[3] = projPixel->pixel.f_pt[3];  
1520         }
1521         else {
1522                 projPixel->pixel.ch_pt = ((unsigned char *)ibuf->rect + ((x_px + y_px * ibuf->x) * 4));
1523                 projPixel->origColor.uint = projPixel->newColor.uint = *projPixel->pixel.uint_pt;
1524         }
1525         
1526         /* screenspace unclamped, we could keep its z and w values but dont need them at the moment */
1527         VECCOPY2D(projPixel->projCoSS, pixelScreenCo);
1528         
1529         projPixel->x_px = x_px;
1530         projPixel->y_px = y_px;
1531         
1532         projPixel->mask = (unsigned short)(mask * 65535);
1533         projPixel->mask_max = 0;
1534         
1535         /* which bounding box cell are we in?, needed for undo */
1536         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 ;
1537         
1538         /* done with view3d_project_float inline */
1539         if (ps->tool==PAINT_TOOL_CLONE) {
1540                 if (ps->dm_mtface_clone) {
1541                         ImBuf *ibuf_other;
1542                         const MTFace *tf_other = ps->dm_mtface_clone + face_index;
1543                         
1544                         if (tf_other->tpage && (ibuf_other = BKE_image_get_ibuf(tf_other->tpage, NULL))) {
1545                                 /* BKE_image_get_ibuf - TODO - this may be slow */
1546                                 
1547                                 if (ibuf->rect_float) {
1548                                         if (ibuf_other->rect_float) { /* from float to float */
1549                                                 project_face_pixel(tf_other, ibuf_other, w, side, NULL, ((ProjPixelClone *)projPixel)->clonepx.f);
1550                                         }
1551                                         else { /* from char to float */
1552                                                 unsigned char rgba_ub[4];
1553                                                 project_face_pixel(tf_other, ibuf_other, w, side, rgba_ub, NULL);
1554                                                 IMAPAINT_CHAR_RGBA_TO_FLOAT(((ProjPixelClone *)projPixel)->clonepx.f, rgba_ub);
1555                                         }
1556                                 }
1557                                 else {
1558                                         if (ibuf_other->rect_float) { /* float to char */
1559                                                 float rgba[4];
1560                                                 project_face_pixel(tf_other, ibuf_other, w, side, NULL, rgba);
1561                                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(((ProjPixelClone *)projPixel)->clonepx.ch, rgba)
1562                                         }
1563                                         else { /* char to char */
1564                                                 project_face_pixel(tf_other, ibuf_other, w, side, ((ProjPixelClone *)projPixel)->clonepx.ch, NULL);
1565                                         }
1566                                 }
1567                         }
1568                         else {
1569                                 if (ibuf->rect_float) {
1570                                         ((ProjPixelClone *)projPixel)->clonepx.f[3] = 0;
1571                                 }
1572                                 else {
1573                                         ((ProjPixelClone *)projPixel)->clonepx.ch[3] = 0;
1574                                 }
1575                         }
1576                         
1577                 }
1578                 else {
1579                         float co[2];
1580                         sub_v2_v2v2(co, projPixel->projCoSS, (float *)ps->cloneOffset);
1581                         
1582                         /* no need to initialize the bucket, we're only checking buckets faces and for this
1583                          * the faces are alredy initialized in project_paint_delayed_face_init(...) */
1584                         if (ibuf->rect_float) {
1585                                 if (!project_paint_PickColor(ps, co, ((ProjPixelClone *)projPixel)->clonepx.f, NULL, 1)) {
1586                                         ((ProjPixelClone *)projPixel)->clonepx.f[3] = 0; /* zero alpha - ignore */
1587                                 }
1588                         }
1589                         else {
1590                                 if (!project_paint_PickColor(ps, co, NULL, ((ProjPixelClone *)projPixel)->clonepx.ch, 1)) {
1591                                         ((ProjPixelClone *)projPixel)->clonepx.ch[3] = 0; /* zero alpha - ignore */
1592                                 }
1593                         }
1594                 }
1595         }
1596         
1597 #ifdef PROJ_DEBUG_PAINT
1598         if (ibuf->rect_float)   projPixel->pixel.f_pt[0] = 0;
1599         else                                    projPixel->pixel.ch_pt[0] = 0;
1600 #endif
1601         projPixel->image_index = image_index;
1602         
1603         return projPixel;
1604 }
1605
1606 static int line_clip_rect2f(
1607                 rctf *rect,
1608                 const float l1[2], const float l2[2],
1609                 float l1_clip[2], float l2_clip[2])
1610 {
1611         /* first account for horizontal, then vertical lines */
1612         /* horiz */
1613         if (fabsf(l1[1]-l2[1]) < PROJ_GEOM_TOLERANCE) {
1614                 /* is the line out of range on its Y axis? */
1615                 if (l1[1] < rect->ymin || l1[1] > rect->ymax) {
1616                         return 0;
1617                 }
1618                 /* line is out of range on its X axis */
1619                 if ((l1[0] < rect->xmin && l2[0] < rect->xmin) || (l1[0] > rect->xmax && l2[0] > rect->xmax)) {
1620                         return 0;
1621                 }
1622                 
1623                 
1624                 if (fabsf(l1[0]-l2[0]) < PROJ_GEOM_TOLERANCE) { /* this is a single point  (or close to)*/
1625                         if (BLI_in_rctf(rect, l1[0], l1[1])) {
1626                                 VECCOPY2D(l1_clip, l1);
1627                                 VECCOPY2D(l2_clip, l2);
1628                                 return 1;
1629                         }
1630                         else {
1631                                 return 0;
1632                         }
1633                 }
1634                 
1635                 VECCOPY2D(l1_clip, l1);
1636                 VECCOPY2D(l2_clip, l2);
1637                 CLAMP(l1_clip[0], rect->xmin, rect->xmax);
1638                 CLAMP(l2_clip[0], rect->xmin, rect->xmax);
1639                 return 1;
1640         }
1641         else if (fabsf(l1[0]-l2[0]) < PROJ_GEOM_TOLERANCE) {
1642                 /* is the line out of range on its X axis? */
1643                 if (l1[0] < rect->xmin || l1[0] > rect->xmax) {
1644                         return 0;
1645                 }
1646                 
1647                 /* line is out of range on its Y axis */
1648                 if ((l1[1] < rect->ymin && l2[1] < rect->ymin) || (l1[1] > rect->ymax && l2[1] > rect->ymax)) {
1649                         return 0;
1650                 }
1651                 
1652                 if (fabsf(l1[1]-l2[1]) < PROJ_GEOM_TOLERANCE) { /* this is a single point  (or close to)*/
1653                         if (BLI_in_rctf(rect, l1[0], l1[1])) {
1654                                 VECCOPY2D(l1_clip, l1);
1655                                 VECCOPY2D(l2_clip, l2);
1656                                 return 1;
1657                         }
1658                         else {
1659                                 return 0;
1660                         }
1661                 }
1662                 
1663                 VECCOPY2D(l1_clip, l1);
1664                 VECCOPY2D(l2_clip, l2);
1665                 CLAMP(l1_clip[1], rect->ymin, rect->ymax);
1666                 CLAMP(l2_clip[1], rect->ymin, rect->ymax);
1667                 return 1;
1668         }
1669         else {
1670                 float isect;
1671                 short ok1 = 0;
1672                 short ok2 = 0;
1673                 
1674                 /* Done with vertical lines */
1675                 
1676                 /* are either of the points inside the rectangle ? */
1677                 if (BLI_in_rctf(rect, l1[0], l1[1])) {
1678                         VECCOPY2D(l1_clip, l1);
1679                         ok1 = 1;
1680                 }
1681                 
1682                 if (BLI_in_rctf(rect, l2[0], l2[1])) {
1683                         VECCOPY2D(l2_clip, l2);
1684                         ok2 = 1;
1685                 }
1686                 
1687                 /* line inside rect */
1688                 if (ok1 && ok2) return 1;
1689                 
1690                 /* top/bottom */
1691                 if (line_isect_y(l1, l2, rect->ymin, &isect) && (isect >= rect->xmin) && (isect <= rect->xmax)) {
1692                         if (l1[1] < l2[1]) { /* line 1 is outside */
1693                                 l1_clip[0] = isect;
1694                                 l1_clip[1] = rect->ymin;
1695                                 ok1 = 1;
1696                         }
1697                         else {
1698                                 l2_clip[0] = isect;
1699                                 l2_clip[1] = rect->ymin;
1700                                 ok2 = 2;
1701                         }
1702                 }
1703                 
1704                 if (ok1 && ok2) return 1;
1705                 
1706                 if (line_isect_y(l1, l2, rect->ymax, &isect) && (isect >= rect->xmin) && (isect <= rect->xmax)) {
1707                         if (l1[1] > l2[1]) { /* line 1 is outside */
1708                                 l1_clip[0] = isect;
1709                                 l1_clip[1] = rect->ymax;
1710                                 ok1 = 1;
1711                         }
1712                         else {
1713                                 l2_clip[0] = isect;
1714                                 l2_clip[1] = rect->ymax;
1715                                 ok2 = 2;
1716                         }
1717                 }
1718                 
1719                 if (ok1 && ok2) return 1;
1720                 
1721                 /* left/right */
1722                 if (line_isect_x(l1, l2, rect->xmin, &isect) && (isect >= rect->ymin) && (isect <= rect->ymax)) {
1723                         if (l1[0] < l2[0]) { /* line 1 is outside */
1724                                 l1_clip[0] = rect->xmin;
1725                                 l1_clip[1] = isect;
1726                                 ok1 = 1;
1727                         }
1728                         else {
1729                                 l2_clip[0] = rect->xmin;
1730                                 l2_clip[1] = isect;
1731                                 ok2 = 2;
1732                         }
1733                 }
1734         
1735                 if (ok1 && ok2) return 1;
1736                 
1737                 if (line_isect_x(l1, l2, rect->xmax, &isect) && (isect >= rect->ymin) && (isect <= rect->ymax)) {
1738                         if (l1[0] > l2[0]) { /* line 1 is outside */
1739                                 l1_clip[0] = rect->xmax;
1740                                 l1_clip[1] = isect;
1741                                 ok1 = 1;
1742                         }
1743                         else {
1744                                 l2_clip[0] = rect->xmax;
1745                                 l2_clip[1] = isect;
1746                                 ok2 = 2;
1747                         }
1748                 }
1749                 
1750                 if (ok1 && ok2) {
1751                         return 1;
1752                 }
1753                 else {
1754                         return 0;
1755                 }
1756         }
1757 }
1758
1759
1760
1761 /* scale the quad & tri about its center
1762  * scaling by PROJ_FACE_SCALE_SEAM (0.99x) is used for getting fake UV pixel coords that are on the
1763  * edge of the face but slightly inside it occlusion tests dont return hits on adjacent faces */
1764 static void scale_quad(float insetCos[4][3], float *origCos[4], const float inset)
1765 {
1766         float cent[3];
1767         cent[0] = (origCos[0][0] + origCos[1][0] + origCos[2][0] + origCos[3][0]) / 4.0f;
1768         cent[1] = (origCos[0][1] + origCos[1][1] + origCos[2][1] + origCos[3][1]) / 4.0f;
1769         cent[2] = (origCos[0][2] + origCos[1][2] + origCos[2][2] + origCos[3][2]) / 4.0f;
1770         
1771         sub_v3_v3v3(insetCos[0], origCos[0], cent);
1772         sub_v3_v3v3(insetCos[1], origCos[1], cent);
1773         sub_v3_v3v3(insetCos[2], origCos[2], cent);
1774         sub_v3_v3v3(insetCos[3], origCos[3], cent);
1775         
1776         mul_v3_fl(insetCos[0], inset);
1777         mul_v3_fl(insetCos[1], inset);
1778         mul_v3_fl(insetCos[2], inset);
1779         mul_v3_fl(insetCos[3], inset);
1780         
1781         add_v3_v3v3(insetCos[0], insetCos[0], cent);
1782         add_v3_v3v3(insetCos[1], insetCos[1], cent);
1783         add_v3_v3v3(insetCos[2], insetCos[2], cent);
1784         add_v3_v3v3(insetCos[3], insetCos[3], cent);
1785 }
1786
1787
1788 static void scale_tri(float insetCos[4][3], float *origCos[4], const float inset)
1789 {
1790         float cent[3];
1791         cent[0] = (origCos[0][0] + origCos[1][0] + origCos[2][0]) / 3.0f;
1792         cent[1] = (origCos[0][1] + origCos[1][1] + origCos[2][1]) / 3.0f;
1793         cent[2] = (origCos[0][2] + origCos[1][2] + origCos[2][2]) / 3.0f;
1794         
1795         sub_v3_v3v3(insetCos[0], origCos[0], cent);
1796         sub_v3_v3v3(insetCos[1], origCos[1], cent);
1797         sub_v3_v3v3(insetCos[2], origCos[2], cent);
1798         
1799         mul_v3_fl(insetCos[0], inset);
1800         mul_v3_fl(insetCos[1], inset);
1801         mul_v3_fl(insetCos[2], inset);
1802         
1803         add_v3_v3v3(insetCos[0], insetCos[0], cent);
1804         add_v3_v3v3(insetCos[1], insetCos[1], cent);
1805         add_v3_v3v3(insetCos[2], insetCos[2], cent);
1806 }
1807
1808
1809 static float Vec2Lenf_nosqrt(const float *v1, const float *v2)
1810 {
1811         float x, y;
1812
1813         x = v1[0]-v2[0];
1814         y = v1[1]-v2[1];
1815         return x*x+y*y;
1816 }
1817
1818 static float Vec2Lenf_nosqrt_other(const float *v1, const float v2_1, const float v2_2)
1819 {
1820         float x, y;
1821
1822         x = v1[0]-v2_1;
1823         y = v1[1]-v2_2;
1824         return x*x+y*y;
1825 }
1826
1827 /* note, use a squared value so we can use Vec2Lenf_nosqrt
1828  * be sure that you have done a bounds check first or this may fail */
1829 /* only give bucket_bounds as an arg because we need it elsewhere */
1830 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)
1831 {
1832          
1833         /* Would normally to a simple intersection test, however we know the bounds of these 2 alredy intersect 
1834          * so we only need to test if the center is inside the vertical or horizontal bounds on either axis,
1835          * this is even less work then an intersection test
1836          * 
1837         if (BLI_in_rctf(bucket_bounds, cent[0], cent[1]))
1838                 return 1;
1839          */
1840         
1841         if((bucket_bounds->xmin <= cent[0] && bucket_bounds->xmax >= cent[0]) || (bucket_bounds->ymin <= cent[1] && bucket_bounds->ymax >= cent[1]) ) {
1842            return 1;
1843         }
1844         
1845         /* out of bounds left */
1846         if (cent[0] < bucket_bounds->xmin) {
1847                 /* lower left out of radius test */
1848                 if (cent[1] < bucket_bounds->ymin) {
1849                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmin, bucket_bounds->ymin) < radius_squared) ? 1 : 0;
1850                 } 
1851                 /* top left test */
1852                 else if (cent[1] > bucket_bounds->ymax) {
1853                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmin, bucket_bounds->ymax) < radius_squared) ? 1 : 0;
1854                 }
1855         }
1856         else if (cent[0] > bucket_bounds->xmax) {
1857                 /* lower right out of radius test */
1858                 if (cent[1] < bucket_bounds->ymin) {
1859                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmax, bucket_bounds->ymin) < radius_squared) ? 1 : 0;
1860                 } 
1861                 /* top right test */
1862                 else if (cent[1] > bucket_bounds->ymax) {
1863                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmax, bucket_bounds->ymax) < radius_squared) ? 1 : 0;
1864                 }
1865         }
1866         
1867         return 0;
1868 }
1869
1870
1871
1872 /* Note for rect_to_uvspace_ortho() and rect_to_uvspace_persp()
1873  * in ortho view this function gives good results when bucket_bounds are outside the triangle
1874  * however in some cases, perspective view will mess up with faces that have minimal screenspace area (viewed from the side)
1875  * 
1876  * 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.
1877  * however switching back to this for ortho is always an option */
1878
1879 static void rect_to_uvspace_ortho(
1880                 rctf *bucket_bounds,
1881                 float *v1coSS, float *v2coSS, float *v3coSS,
1882                 float *uv1co, float *uv2co, float *uv3co,
1883                 float bucket_bounds_uv[4][2],
1884                 const int flip)
1885 {
1886         float uv[2];
1887         float w[3];
1888         
1889         /* get the UV space bounding box */
1890         uv[0] = bucket_bounds->xmax;
1891         uv[1] = bucket_bounds->ymin;
1892         BarycentricWeights2f(uv, v1coSS, v2coSS, v3coSS, w);
1893         interp_v2_v2v2v2(bucket_bounds_uv[flip?3:0], uv1co, uv2co, uv3co, w);
1894
1895         //uv[0] = bucket_bounds->xmax; // set above
1896         uv[1] = bucket_bounds->ymax;
1897         BarycentricWeights2f(uv, v1coSS, v2coSS, v3coSS, w);
1898         interp_v2_v2v2v2(bucket_bounds_uv[flip?2:1], uv1co, uv2co, uv3co, w);
1899
1900         uv[0] = bucket_bounds->xmin;
1901         //uv[1] = bucket_bounds->ymax; // set above
1902         BarycentricWeights2f(uv, v1coSS, v2coSS, v3coSS, w);
1903         interp_v2_v2v2v2(bucket_bounds_uv[flip?1:2], uv1co, uv2co, uv3co, w);
1904
1905         //uv[0] = bucket_bounds->xmin; // set above
1906         uv[1] = bucket_bounds->ymin;
1907         BarycentricWeights2f(uv, v1coSS, v2coSS, v3coSS, w);
1908         interp_v2_v2v2v2(bucket_bounds_uv[flip?0:3], uv1co, uv2co, uv3co, w);
1909 }
1910
1911 /* same as above but use BarycentricWeightsPersp2f */
1912 static void rect_to_uvspace_persp(
1913                 rctf *bucket_bounds,
1914                 float *v1coSS, float *v2coSS, float *v3coSS,
1915                 float *uv1co, float *uv2co, float *uv3co,
1916                 float bucket_bounds_uv[4][2],
1917                 const int flip
1918         )
1919 {
1920         float uv[2];
1921         float w[3];
1922         
1923         /* get the UV space bounding box */
1924         uv[0] = bucket_bounds->xmax;
1925         uv[1] = bucket_bounds->ymin;
1926         BarycentricWeightsPersp2f(uv, v1coSS, v2coSS, v3coSS, w);
1927         interp_v2_v2v2v2(bucket_bounds_uv[flip?3:0], uv1co, uv2co, uv3co, w);
1928
1929         //uv[0] = bucket_bounds->xmax; // set above
1930         uv[1] = bucket_bounds->ymax;
1931         BarycentricWeightsPersp2f(uv, v1coSS, v2coSS, v3coSS, w);
1932         interp_v2_v2v2v2(bucket_bounds_uv[flip?2:1], uv1co, uv2co, uv3co, w);
1933
1934         uv[0] = bucket_bounds->xmin;
1935         //uv[1] = bucket_bounds->ymax; // set above
1936         BarycentricWeightsPersp2f(uv, v1coSS, v2coSS, v3coSS, w);
1937         interp_v2_v2v2v2(bucket_bounds_uv[flip?1:2], uv1co, uv2co, uv3co, w);
1938
1939         //uv[0] = bucket_bounds->xmin; // set above
1940         uv[1] = bucket_bounds->ymin;
1941         BarycentricWeightsPersp2f(uv, v1coSS, v2coSS, v3coSS, w);
1942         interp_v2_v2v2v2(bucket_bounds_uv[flip?0:3], uv1co, uv2co, uv3co, w);
1943 }
1944
1945 /* This works as we need it to but we can save a few steps and not use it */
1946
1947 #if 0
1948 static float angle_2d_clockwise(const float p1[2], const float p2[2], const float p3[2])
1949 {
1950         float v1[2], v2[2];
1951         
1952         v1[0] = p1[0]-p2[0];    v1[1] = p1[1]-p2[1];
1953         v2[0] = p3[0]-p2[0];    v2[1] = p3[1]-p2[1];
1954         
1955         return -atan2(v1[0]*v2[1] - v1[1]*v2[0], v1[0]*v2[0]+v1[1]*v2[1]);
1956 }
1957 #endif
1958
1959 #define ISECT_1 (1)
1960 #define ISECT_2 (1<<1)
1961 #define ISECT_3 (1<<2)
1962 #define ISECT_4 (1<<3)
1963 #define ISECT_ALL3 ((1<<3)-1)
1964 #define ISECT_ALL4 ((1<<4)-1)
1965
1966 /* limit must be a fraction over 1.0f */
1967 static int IsectPT2Df_limit(float pt[2], float v1[2], float v2[2], float v3[2], float limit)
1968 {
1969         return ((area_tri_v2(pt,v1,v2) + area_tri_v2(pt,v2,v3) + area_tri_v2(pt,v3,v1)) / (area_tri_v2(v1,v2,v3))) < limit;
1970 }
1971
1972 /* Clip the face by a bucket and set the uv-space bucket_bounds_uv
1973  * so we have the clipped UV's to do pixel intersection tests with 
1974  * */
1975 static int float_z_sort_flip(const void *p1, const void *p2) {
1976         return (((float *)p1)[2] < ((float *)p2)[2] ? 1:-1);
1977 }
1978
1979 static int float_z_sort(const void *p1, const void *p2) {
1980         return (((float *)p1)[2] < ((float *)p2)[2] ?-1:1);
1981 }
1982
1983 static void project_bucket_clip_face(
1984                 const int is_ortho,
1985                 rctf *bucket_bounds,
1986                 float *v1coSS, float *v2coSS, float *v3coSS,
1987                 float *uv1co, float *uv2co, float *uv3co,
1988                 float bucket_bounds_uv[8][2],
1989                 int *tot)
1990 {
1991         int inside_bucket_flag = 0;
1992         int inside_face_flag = 0;
1993         const int flip = ((SIDE_OF_LINE(v1coSS, v2coSS, v3coSS) > 0.0f) != (SIDE_OF_LINE(uv1co, uv2co, uv3co) > 0.0f));
1994         
1995         float bucket_bounds_ss[4][2];
1996
1997         /* get the UV space bounding box */
1998         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v1coSS[0], v1coSS[1]);
1999         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v2coSS[0], v2coSS[1])          << 1;
2000         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v3coSS[0], v3coSS[1])          << 2;
2001         
2002         if (inside_bucket_flag == ISECT_ALL3) {
2003                 /* all screenspace points are inside the bucket bounding box, this means we dont need to clip and can simply return the UVs */
2004                 if (flip) { /* facing the back? */
2005                         VECCOPY2D(bucket_bounds_uv[0], uv3co);
2006                         VECCOPY2D(bucket_bounds_uv[1], uv2co);
2007                         VECCOPY2D(bucket_bounds_uv[2], uv1co);
2008                 }
2009                 else {
2010                         VECCOPY2D(bucket_bounds_uv[0], uv1co);
2011                         VECCOPY2D(bucket_bounds_uv[1], uv2co);
2012                         VECCOPY2D(bucket_bounds_uv[2], uv3co);
2013                 }
2014                 
2015                 *tot = 3; 
2016                 return;
2017         }
2018         
2019         /* get the UV space bounding box */
2020         /* use IsectPT2Df_limit here so we catch points are are touching the tri edge (or a small fraction over) */
2021         bucket_bounds_ss[0][0] = bucket_bounds->xmax;
2022         bucket_bounds_ss[0][1] = bucket_bounds->ymin;
2023         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[0], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_1 : 0);
2024         
2025         bucket_bounds_ss[1][0] = bucket_bounds->xmax;
2026         bucket_bounds_ss[1][1] = bucket_bounds->ymax;
2027         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[1], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_2 : 0);
2028
2029         bucket_bounds_ss[2][0] = bucket_bounds->xmin;
2030         bucket_bounds_ss[2][1] = bucket_bounds->ymax;
2031         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[2], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_3 : 0);
2032
2033         bucket_bounds_ss[3][0] = bucket_bounds->xmin;
2034         bucket_bounds_ss[3][1] = bucket_bounds->ymin;
2035         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[3], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_4 : 0);
2036         
2037         if (inside_face_flag == ISECT_ALL4) {
2038                 /* bucket is totally inside the screenspace face, we can safely use weights */
2039                 
2040                 if (is_ortho)   rect_to_uvspace_ortho(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, bucket_bounds_uv, flip);
2041                 else                    rect_to_uvspace_persp(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, bucket_bounds_uv, flip);
2042                 
2043                 *tot = 4;
2044                 return;
2045         }
2046         else {
2047                 /* The Complicated Case! 
2048                  * 
2049                  * The 2 cases above are where the face is inside the bucket or the bucket is inside the face.
2050                  * 
2051                  * we need to make a convex polyline from the intersection between the screenspace face
2052                  * and the bucket bounds.
2053                  * 
2054                  * There are a number of ways this could be done, currently it just collects all intersecting verts,
2055                  * and line intersections,  then sorts them clockwise, this is a lot easier then evaluating the geometry to
2056                  * do a correct clipping on both shapes. */
2057                 
2058                 
2059                 /* add a bunch of points, we know must make up the convex hull which is the clipped rect and triangle */
2060                 
2061                 
2062                 
2063                 /* Maximum possible 6 intersections when using a rectangle and triangle */
2064                 float isectVCosSS[8][3]; /* The 3rd float is used to store angle for qsort(), NOT as a Z location */
2065                 float v1_clipSS[2], v2_clipSS[2];
2066                 float w[3];
2067                 
2068                 /* calc center*/
2069                 float cent[2] = {0.0f, 0.0f};
2070                 /*float up[2] = {0.0f, 1.0f};*/
2071                 int i;
2072                 short doubles;
2073                 
2074                 (*tot) = 0;
2075                 
2076                 if (inside_face_flag & ISECT_1) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[0]); (*tot)++; }
2077                 if (inside_face_flag & ISECT_2) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[1]); (*tot)++; }
2078                 if (inside_face_flag & ISECT_3) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[2]); (*tot)++; }
2079                 if (inside_face_flag & ISECT_4) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[3]); (*tot)++; }
2080                 
2081                 if (inside_bucket_flag & ISECT_1) {     VECCOPY2D(isectVCosSS[*tot], v1coSS); (*tot)++; }
2082                 if (inside_bucket_flag & ISECT_2) {     VECCOPY2D(isectVCosSS[*tot], v2coSS); (*tot)++; }
2083                 if (inside_bucket_flag & ISECT_3) {     VECCOPY2D(isectVCosSS[*tot], v3coSS); (*tot)++; }
2084                 
2085                 if ((inside_bucket_flag & (ISECT_1|ISECT_2)) != (ISECT_1|ISECT_2)) {
2086                         if (line_clip_rect2f(bucket_bounds, v1coSS, v2coSS, v1_clipSS, v2_clipSS)) {
2087                                 if ((inside_bucket_flag & ISECT_1)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
2088                                 if ((inside_bucket_flag & ISECT_2)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
2089                         }
2090                 }
2091                 
2092                 if ((inside_bucket_flag & (ISECT_2|ISECT_3)) != (ISECT_2|ISECT_3)) {
2093                         if (line_clip_rect2f(bucket_bounds, v2coSS, v3coSS, v1_clipSS, v2_clipSS)) {
2094                                 if ((inside_bucket_flag & ISECT_2)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
2095                                 if ((inside_bucket_flag & ISECT_3)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
2096                         }
2097                 }       
2098                 
2099                 if ((inside_bucket_flag & (ISECT_3|ISECT_1)) != (ISECT_3|ISECT_1)) {
2100                         if (line_clip_rect2f(bucket_bounds, v3coSS, v1coSS, v1_clipSS, v2_clipSS)) {
2101                                 if ((inside_bucket_flag & ISECT_3)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
2102                                 if ((inside_bucket_flag & ISECT_1)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
2103                         }
2104                 }
2105                 
2106                 
2107                 if ((*tot) < 3) { /* no intersections to speak of */
2108                         *tot = 0;
2109                         return;
2110                 }
2111         
2112                 /* now we have all points we need, collect their angles and sort them clockwise */
2113                 
2114                 for(i=0; i<(*tot); i++) {
2115                         cent[0] += isectVCosSS[i][0];
2116                         cent[1] += isectVCosSS[i][1];
2117                 }
2118                 cent[0] = cent[0] / (float)(*tot);
2119                 cent[1] = cent[1] / (float)(*tot);
2120                 
2121                 
2122                 
2123                 /* Collect angles for every point around the center point */
2124
2125                 
2126 #if 0   /* uses a few more cycles then the above loop */
2127                 for(i=0; i<(*tot); i++) {
2128                         isectVCosSS[i][2] = angle_2d_clockwise(up, cent, isectVCosSS[i]);
2129                 }
2130 #endif
2131
2132                 v1_clipSS[0] = cent[0]; /* Abuse this var for the loop below */
2133                 v1_clipSS[1] = cent[1] + 1.0f;
2134                 
2135                 for(i=0; i<(*tot); i++) {
2136                         v2_clipSS[0] = isectVCosSS[i][0] - cent[0];
2137                         v2_clipSS[1] = isectVCosSS[i][1] - cent[1];
2138                         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]); 
2139                 }
2140                 
2141                 if (flip)       qsort(isectVCosSS, *tot, sizeof(float)*3, float_z_sort_flip);
2142                 else            qsort(isectVCosSS, *tot, sizeof(float)*3, float_z_sort);
2143                 
2144                 /* remove doubles */
2145                 /* first/last check */
2146                 if (fabsf(isectVCosSS[0][0]-isectVCosSS[(*tot)-1][0]) < PROJ_GEOM_TOLERANCE &&  fabsf(isectVCosSS[0][1]-isectVCosSS[(*tot)-1][1]) < PROJ_GEOM_TOLERANCE) {
2147                         (*tot)--;
2148                 }
2149                 
2150                 /* its possible there is only a few left after remove doubles */
2151                 if ((*tot) < 3) {
2152                         // printf("removed too many doubles A\n");
2153                         *tot = 0;
2154                         return;
2155                 }
2156                 
2157                 doubles = TRUE;
2158                 while (doubles==TRUE) {
2159                         doubles = FALSE;
2160                         for(i=1; i<(*tot); i++) {
2161                                 if (fabsf(isectVCosSS[i-1][0]-isectVCosSS[i][0]) < PROJ_GEOM_TOLERANCE &&
2162                                         fabsf(isectVCosSS[i-1][1]-isectVCosSS[i][1]) < PROJ_GEOM_TOLERANCE)
2163                                 {
2164                                         int j;
2165                                         for(j=i+1; j<(*tot); j++) {
2166                                                 isectVCosSS[j-1][0] = isectVCosSS[j][0]; 
2167                                                 isectVCosSS[j-1][1] = isectVCosSS[j][1]; 
2168                                         }
2169                                         doubles = TRUE; /* keep looking for more doubles */
2170                                         (*tot)--;
2171                                 }
2172                         }
2173                 }
2174                 
2175                 /* its possible there is only a few left after remove doubles */
2176                 if ((*tot) < 3) {
2177                         // printf("removed too many doubles B\n");
2178                         *tot = 0;
2179                         return;
2180                 }
2181                 
2182                 
2183                 if (is_ortho) {
2184                         for(i=0; i<(*tot); i++) {
2185                                 BarycentricWeights2f(isectVCosSS[i], v1coSS, v2coSS, v3coSS, w);
2186                                 interp_v2_v2v2v2(bucket_bounds_uv[i], uv1co, uv2co, uv3co, w);
2187                         }
2188                 }
2189                 else {
2190                         for(i=0; i<(*tot); i++) {
2191                                 BarycentricWeightsPersp2f(isectVCosSS[i], v1coSS, v2coSS, v3coSS, w);
2192                                 interp_v2_v2v2v2(bucket_bounds_uv[i], uv1co, uv2co, uv3co, w);
2193                         }
2194                 }
2195         }
2196
2197 #ifdef PROJ_DEBUG_PRINT_CLIP
2198         /* include this at the bottom of the above function to debug the output */
2199
2200         {
2201                 /* If there are ever any problems, */
2202                 float test_uv[4][2];
2203                 int i;
2204                 if (is_ortho)   rect_to_uvspace_ortho(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, test_uv, flip);
2205                 else                            rect_to_uvspace_persp(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, test_uv, flip);
2206                 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]);
2207                 
2208                 printf("  [(%f,%f), (%f,%f), (%f,%f)], ", uv1co[0], uv1co[1],   uv2co[0], uv2co[1],    uv3co[0], uv3co[1]);
2209                 
2210                 printf("[");
2211                 for (i=0; i < (*tot); i++) {
2212                         printf("(%f, %f),", bucket_bounds_uv[i][0], bucket_bounds_uv[i][1]);
2213                 }
2214                 printf("]),\\\n");
2215         }
2216 #endif
2217 }
2218
2219         /*
2220 # This script creates faces in a blender scene from printed data above.
2221
2222 project_ls = [
2223 ...(output from above block)...
2224 ]
2225  
2226 from Blender import Scene, Mesh, Window, sys, Mathutils
2227
2228 import bpy
2229
2230 V = Mathutils.Vector
2231
2232 def main():
2233         sce = bpy.data.scenes.active
2234         
2235         for item in project_ls:
2236                 bb = item[0]
2237                 uv = item[1]
2238                 poly = item[2]
2239                 
2240                 me = bpy.data.meshes.new()
2241                 ob = sce.objects.new(me)
2242                 
2243                 me.verts.extend([V(bb[0]).resize3D(), V(bb[1]).resize3D(), V(bb[2]).resize3D(), V(bb[3]).resize3D()])
2244                 me.faces.extend([(0,1,2,3),])
2245                 me.verts.extend([V(uv[0]).resize3D(), V(uv[1]).resize3D(), V(uv[2]).resize3D()])
2246                 me.faces.extend([(4,5,6),])
2247                 
2248                 vs = [V(p).resize3D() for p in poly]
2249                 print len(vs)
2250                 l = len(me.verts)
2251                 me.verts.extend(vs)
2252                 
2253                 i = l
2254                 while i < len(me.verts):
2255                         ii = i+1
2256                         if ii==len(me.verts):
2257                                 ii = l
2258                         me.edges.extend([i, ii])
2259                         i+=1
2260
2261 if __name__ == '__main__':
2262         main()
2263  */     
2264
2265
2266 #undef ISECT_1
2267 #undef ISECT_2
2268 #undef ISECT_3
2269 #undef ISECT_4
2270 #undef ISECT_ALL3
2271 #undef ISECT_ALL4
2272
2273         
2274 /* checks if pt is inside a convex 2D polyline, the polyline must be ordered rotating clockwise
2275  * otherwise it would have to test for mixed (SIDE_OF_LINE > 0.0f) cases */
2276 int IsectPoly2Df(const float pt[2], float uv[][2], const int tot)
2277 {
2278         int i;
2279         if (SIDE_OF_LINE(uv[tot-1], uv[0], pt) < 0.0f)
2280                 return 0;
2281         
2282         for (i=1; i<tot; i++) {
2283                 if (SIDE_OF_LINE(uv[i-1], uv[i], pt) < 0.0f)
2284                         return 0;
2285                 
2286         }
2287         
2288         return 1;
2289 }
2290 static int IsectPoly2Df_twoside(const float pt[2], float uv[][2], const int tot)
2291 {
2292         int i;
2293         int side = (SIDE_OF_LINE(uv[tot-1], uv[0], pt) > 0.0f);
2294         
2295         for (i=1; i<tot; i++) {
2296                 if ((SIDE_OF_LINE(uv[i-1], uv[i], pt) > 0.0f) != side)
2297                         return 0;
2298                 
2299         }
2300         
2301         return 1;
2302 }
2303
2304 /* One of the most important function for projectiopn painting, since it selects the pixels to be added into each bucket.
2305  * initialize pixels from this face where it intersects with the bucket_index, optionally initialize pixels for removing seams */
2306 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)
2307 {
2308         /* Projection vars, to get the 3D locations into screen space  */
2309         MemArena *arena = ps->arena_mt[thread_index];
2310         LinkNode **bucketPixelNodes = ps->bucketRect + bucket_index;
2311         LinkNode *bucketFaceNodes = ps->bucketFaces[bucket_index];
2312         
2313         const MFace *mf = ps->dm_mface + face_index;
2314         const MTFace *tf = ps->dm_mtface + face_index;
2315         
2316         /* UV/pixel seeking data */
2317         int x; /* Image X-Pixel */
2318         int y;/* Image Y-Pixel */
2319         float mask;
2320         float uv[2]; /* Image floating point UV - same as x, y but from 0.0-1.0 */
2321         
2322         int side;
2323         float *v1coSS, *v2coSS, *v3coSS; /* vert co screen-space, these will be assigned to mf->v1,2,3 or mf->v1,3,4 */
2324         
2325         float *vCo[4]; /* vertex screenspace coords */
2326         
2327         float w[3], wco[3];
2328         
2329         float *uv1co, *uv2co, *uv3co; /* for convenience only, these will be assigned to tf->uv[0],1,2 or tf->uv[0],2,3 */
2330         float pixelScreenCo[4];
2331         
2332         rcti bounds_px; /* ispace bounds */
2333         /* vars for getting uvspace bounds */
2334         
2335         float tf_uv_pxoffset[4][2]; /* bucket bounds in UV space so we can init pixels only for this face,  */
2336         float xhalfpx, yhalfpx;
2337         const float ibuf_xf = ibuf->x, ibuf_yf = ibuf->y;
2338         
2339         int has_x_isect = 0, has_isect = 0; /* for early loop exit */
2340         
2341         int i1, i2, i3;
2342         
2343         float uv_clip[8][2];
2344         int uv_clip_tot;
2345         const short is_ortho = ps->is_ortho;
2346         const short do_backfacecull = ps->do_backfacecull;
2347         
2348         vCo[0] = ps->dm_mvert[mf->v1].co;
2349         vCo[1] = ps->dm_mvert[mf->v2].co;
2350         vCo[2] = ps->dm_mvert[mf->v3].co;
2351         
2352         
2353         /* Use tf_uv_pxoffset instead of tf->uv so we can offset the UV half a pixel
2354          * this is done so we can avoid offseting all the pixels by 0.5 which causes
2355          * problems when wrapping negative coords */
2356         xhalfpx = (0.5f+   (PROJ_GEOM_TOLERANCE/3.0f)   ) / ibuf_xf;
2357         yhalfpx = (0.5f+   (PROJ_GEOM_TOLERANCE/4.0f)   ) / ibuf_yf;
2358         
2359         /* Note about (PROJ_GEOM_TOLERANCE/x) above...
2360           Needed to add this offset since UV coords are often quads aligned to pixels.
2361           In this case pixels can be exactly between 2 triangles causing nasty
2362           artifacts.
2363           
2364           This workaround can be removed and painting will still work on most cases
2365           but since the first thing most people try is painting onto a quad- better make it work.
2366          */
2367
2368
2369
2370         tf_uv_pxoffset[0][0] = tf->uv[0][0] - xhalfpx;
2371         tf_uv_pxoffset[0][1] = tf->uv[0][1] - yhalfpx;
2372
2373         tf_uv_pxoffset[1][0] = tf->uv[1][0] - xhalfpx;
2374         tf_uv_pxoffset[1][1] = tf->uv[1][1] - yhalfpx;
2375         
2376         tf_uv_pxoffset[2][0] = tf->uv[2][0] - xhalfpx;
2377         tf_uv_pxoffset[2][1] = tf->uv[2][1] - yhalfpx;  
2378         
2379         if (mf->v4) {
2380                 vCo[3] = ps->dm_mvert[ mf->v4 ].co;
2381                 
2382                 tf_uv_pxoffset[3][0] = tf->uv[3][0] - xhalfpx;
2383                 tf_uv_pxoffset[3][1] = tf->uv[3][1] - yhalfpx;
2384                 side = 1;
2385         }
2386         else {
2387                 side = 0;
2388         }
2389         
2390         do {
2391                 if (side==1) {
2392                         i1=0; i2=2; i3=3;
2393                 }
2394                 else {
2395                         i1=0; i2=1; i3=2;
2396                 }
2397                 
2398                 uv1co = tf_uv_pxoffset[i1]; // was tf->uv[i1];
2399                 uv2co = tf_uv_pxoffset[i2]; // was tf->uv[i2];
2400                 uv3co = tf_uv_pxoffset[i3]; // was tf->uv[i3];
2401
2402                 v1coSS = ps->screenCoords[ (*(&mf->v1 + i1)) ];
2403                 v2coSS = ps->screenCoords[ (*(&mf->v1 + i2)) ];
2404                 v3coSS = ps->screenCoords[ (*(&mf->v1 + i3)) ];
2405                 
2406                 /* This funtion gives is a concave polyline in UV space from the clipped quad and tri*/
2407                 project_bucket_clip_face(
2408                                 is_ortho, bucket_bounds,
2409                                 v1coSS, v2coSS, v3coSS,
2410                                 uv1co, uv2co, uv3co,
2411                                 uv_clip, &uv_clip_tot
2412                 );
2413
2414                 /* sometimes this happens, better just allow for 8 intersectiosn even though there should be max 6 */
2415                 /*
2416                 if (uv_clip_tot>6) {
2417                         printf("this should never happen! %d\n", uv_clip_tot);
2418                 }*/
2419                 
2420
2421                 if (pixel_bounds_array(uv_clip, &bounds_px, ibuf->x, ibuf->y, uv_clip_tot)) {
2422                         
2423                         /* clip face and */
2424                         
2425                         has_isect = 0;
2426                         for (y = bounds_px.ymin; y < bounds_px.ymax; y++) {
2427                                 //uv[1] = (((float)y) + 0.5f) / (float)ibuf->y;
2428                                 uv[1] = (float)y / ibuf_yf; /* use pixel offset UV coords instead */
2429                                 
2430                                 has_x_isect = 0;
2431                                 for (x = bounds_px.xmin; x < bounds_px.xmax; x++) {
2432                                         //uv[0] = (((float)x) + 0.5f) / ibuf->x;
2433                                         uv[0] = (float)x / ibuf_xf; /* use pixel offset UV coords instead */
2434                                         
2435                                         /* Note about IsectPoly2Df_twoside, checking the face or uv flipping doesnt work,
2436                                          * could check the poly direction but better to do this */
2437                                         if(     (do_backfacecull                && IsectPoly2Df(uv, uv_clip, uv_clip_tot)) ||
2438                                                 (do_backfacecull==0             && IsectPoly2Df_twoside(uv, uv_clip, uv_clip_tot))) {
2439                                                 
2440                                                 has_x_isect = has_isect = 1;
2441                                                 
2442                                                 if (is_ortho)   screen_px_from_ortho(uv, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, pixelScreenCo, w);
2443                                                 else                    screen_px_from_persp(uv, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, pixelScreenCo, w);
2444                                                 
2445                                                 /* a pitty we need to get the worldspace pixel location here */
2446                                                 if(ps->rv3d->rflag & RV3D_CLIPPING) {
2447                                                         interp_v3_v3v3v3(wco, ps->dm_mvert[ (*(&mf->v1 + i1)) ].co, ps->dm_mvert[ (*(&mf->v1 + i2)) ].co, ps->dm_mvert[ (*(&mf->v1 + i3)) ].co, w);
2448                                                         if(view3d_test_clipping(ps->rv3d, wco, 1)) {
2449                                                                 continue; /* Watch out that no code below this needs to run */
2450                                                         }
2451                                                 }
2452                                                 
2453                                                 /* Is this UV visible from the view? - raytrace */
2454                                                 /* project_paint_PickFace is less complex, use for testing */
2455                                                 //if (project_paint_PickFace(ps, pixelScreenCo, w, &side) == face_index) {
2456                                                 if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucketFaceNodes, face_index, pixelScreenCo)) {
2457                                                         
2458                                                         mask = project_paint_uvpixel_mask(ps, face_index, side, w);
2459                                                         
2460                                                         if (mask > 0.0f) {
2461                                                                 BLI_linklist_prepend_arena(
2462                                                                         bucketPixelNodes,
2463                                                                         project_paint_uvpixel_init(ps, arena, ibuf, x, y, mask, face_index, image_index, pixelScreenCo, side, w),
2464                                                                         arena
2465                                                                 );
2466                                                         }
2467                                                 }
2468                                                 
2469                                         }
2470 //#if 0
2471                                         else if (has_x_isect) {
2472                                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2473                                                 break;
2474                                         }
2475 //#endif
2476                                 }
2477                                 
2478                                 
2479 #if 0                   /* TODO - investigate why this dosnt work sometimes! it should! */
2480                                 /* no intersection for this entire row, after some intersection above means we can quit now */
2481                                 if (has_x_isect==0 && has_isect) { 
2482                                         break;
2483                                 }
2484 #endif
2485                         }
2486                 }
2487         } while(side--);
2488
2489         
2490         
2491 #ifndef PROJ_DEBUG_NOSEAMBLEED
2492         if (ps->seam_bleed_px > 0.0f) {
2493                 int face_seam_flag;
2494                 
2495                 if (ps->thread_tot > 1)
2496                         BLI_lock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2497                 
2498                 face_seam_flag = ps->faceSeamFlags[face_index];
2499                 
2500                 /* are any of our edges un-initialized? */
2501                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_NOSEAM1))==0 || 
2502                         (face_seam_flag & (PROJ_FACE_SEAM2|PROJ_FACE_NOSEAM2))==0 || 
2503                         (face_seam_flag & (PROJ_FACE_SEAM3|PROJ_FACE_NOSEAM3))==0 || 
2504                         (face_seam_flag & (PROJ_FACE_SEAM4|PROJ_FACE_NOSEAM4))==0
2505                 ) {
2506                         project_face_seams_init(ps, face_index, mf->v4);
2507                         face_seam_flag = ps->faceSeamFlags[face_index];
2508                         //printf("seams - %d %d %d %d\n", flag&PROJ_FACE_SEAM1, flag&PROJ_FACE_SEAM2, flag&PROJ_FACE_SEAM3, flag&PROJ_FACE_SEAM4);
2509                 }
2510                 
2511                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_SEAM2|PROJ_FACE_SEAM3|PROJ_FACE_SEAM4))==0) {
2512                         
2513                         if (ps->thread_tot > 1)
2514                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2515                         
2516                 }
2517                 else {
2518                         /* we have a seam - deal with it! */
2519                         
2520                         /* Now create new UV's for the seam face */
2521                         float (*outset_uv)[2] = ps->faceSeamUVs[face_index];
2522                         float insetCos[4][3]; /* inset face coords.  NOTE!!! ScreenSace for ortho, Worldspace in prespective view */
2523
2524                         float fac;
2525                         float *vCoSS[4]; /* vertex screenspace coords */
2526                         
2527                         float bucket_clip_edges[2][2]; /* store the screenspace coords of the face, clipped by the bucket's screen aligned rectangle */
2528                         float edge_verts_inset_clip[2][3];
2529                         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 */
2530                         
2531                         float seam_subsection[4][2];
2532                         float fac1, fac2, ftot;
2533                         
2534                         
2535                         if (outset_uv[0][0]==FLT_MAX) /* first time initialize */
2536                                 uv_image_outset(tf_uv_pxoffset, outset_uv, ps->seam_bleed_px, ibuf->x, ibuf->y, mf->v4);
2537                         
2538                         /* ps->faceSeamUVs cant be modified when threading, now this is done we can unlock */
2539                         if (ps->thread_tot > 1)
2540                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2541                         
2542                         vCoSS[0] = ps->screenCoords[mf->v1];
2543                         vCoSS[1] = ps->screenCoords[mf->v2];
2544                         vCoSS[2] = ps->screenCoords[mf->v3];
2545                         if (mf->v4)
2546                                 vCoSS[3] = ps->screenCoords[ mf->v4 ];
2547                         
2548                         /* PROJ_FACE_SCALE_SEAM must be slightly less then 1.0f */
2549                         if (is_ortho) {
2550                                 if (mf->v4)     scale_quad(insetCos, vCoSS, PROJ_FACE_SCALE_SEAM);
2551                                 else            scale_tri(insetCos, vCoSS, PROJ_FACE_SCALE_SEAM);
2552                         }
2553                         else {
2554                                 if (mf->v4)     scale_quad(insetCos, vCo, PROJ_FACE_SCALE_SEAM);
2555                                 else            scale_tri(insetCos, vCo, PROJ_FACE_SCALE_SEAM);
2556                         }
2557                         
2558                         side = 0; /* for triangles this wont need to change */
2559                         
2560                         for (fidx1 = 0; fidx1 < (mf->v4 ? 4 : 3); fidx1++) {
2561                                 if (mf->v4)             fidx2 = (fidx1==3) ? 0 : fidx1+1; /* next fidx in the face (0,1,2,3) -> (1,2,3,0) */
2562                                 else                    fidx2 = (fidx1==2) ? 0 : fidx1+1; /* next fidx in the face (0,1,2) -> (1,2,0) */
2563                                 
2564                                 if (    (face_seam_flag & (1<<fidx1)) && /* 1<<fidx1 -> PROJ_FACE_SEAM# */
2565                                                 line_clip_rect2f(bucket_bounds, vCoSS[fidx1], vCoSS[fidx2], bucket_clip_edges[0], bucket_clip_edges[1])
2566                                 ) {
2567
2568                                         ftot = len_v2v2(vCoSS[fidx1], vCoSS[fidx2]); /* screenspace edge length */
2569                                         
2570                                         if (ftot > 0.0f) { /* avoid div by zero */
2571                                                 if (mf->v4) {
2572                                                         if (fidx1==2 || fidx2==2)       side= 1;
2573                                                         else                                            side= 0;
2574                                                 }
2575                                                 
2576                                                 fac1 = len_v2v2(vCoSS[fidx1], bucket_clip_edges[0]) / ftot;
2577                                                 fac2 = len_v2v2(vCoSS[fidx1], bucket_clip_edges[1]) / ftot;
2578                                                 
2579                                                 interp_v2_v2v2(seam_subsection[0], tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2], fac1);
2580                                                 interp_v2_v2v2(seam_subsection[1], tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2], fac2);
2581
2582                                                 interp_v2_v2v2(seam_subsection[2], outset_uv[fidx1], outset_uv[fidx2], fac2);
2583                                                 interp_v2_v2v2(seam_subsection[3], outset_uv[fidx1], outset_uv[fidx2], fac1);
2584                                                 
2585                                                 /* if the bucket_clip_edges values Z values was kept we could avoid this
2586                                                  * Inset needs to be added so occlusion tests wont hit adjacent faces */
2587                                                 interp_v3_v3v3(edge_verts_inset_clip[0], insetCos[fidx1], insetCos[fidx2], fac1);
2588                                                 interp_v3_v3v3(edge_verts_inset_clip[1], insetCos[fidx1], insetCos[fidx2], fac2);
2589                                                 
2590
2591                                                 if (pixel_bounds_uv(seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3], &bounds_px, ibuf->x, ibuf->y, 1)) {
2592                                                         /* bounds between the seam rect and the uvspace bucket pixels */
2593                                                         
2594                                                         has_isect = 0;
2595                                                         for (y = bounds_px.ymin; y < bounds_px.ymax; y++) {
2596                                                                 // uv[1] = (((float)y) + 0.5f) / (float)ibuf->y;
2597                                                                 uv[1] = (float)y / ibuf_yf; /* use offset uvs instead */
2598                                                                 
2599                                                                 has_x_isect = 0;
2600                                                                 for (x = bounds_px.xmin; x < bounds_px.xmax; x++) {
2601                                                                         //uv[0] = (((float)x) + 0.5f) / (float)ibuf->x;
2602                                                                         uv[0] = (float)x / ibuf_xf; /* use offset uvs instead */
2603                                                                         
2604                                                                         /* test we're inside uvspace bucket and triangle bounds */
2605                                                                         if (isect_point_quad_v2(uv, seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3])) {
2606                                                                                 
2607                                                                                 /* We need to find the closest point along the face edge,
2608                                                                                  * getting the screen_px_from_*** wont work because our actual location
2609                                                                                  * is not relevent, since we are outside the face, Use VecLerpf to find
2610                                                                                  * our location on the side of the face's UV */
2611                                                                                 /*
2612                                                                                 if (is_ortho)   screen_px_from_ortho(ps, uv, v1co, v2co, v3co, uv1co, uv2co, uv3co, pixelScreenCo);
2613                                                                                 else                                    screen_px_from_persp(ps, uv, v1co, v2co, v3co, uv1co, uv2co, uv3co, pixelScreenCo);
2614                                                                                 */
2615                                                                                 
2616                                                                                 /* Since this is a seam we need to work out where on the line this pixel is */
2617                                                                                 //fac = lambda_cp_line2(uv, uv_seam_quad[0], uv_seam_quad[1]);
2618                                                                                 
2619                                                                                 fac = lambda_cp_line2(uv, seam_subsection[0], seam_subsection[1]);
2620                                                                                 if (fac < 0.0f)         { VECCOPY(pixelScreenCo, edge_verts_inset_clip[0]); }
2621                                                                                 else if (fac > 1.0f)    { VECCOPY(pixelScreenCo, edge_verts_inset_clip[1]); }
2622                                                                                 else                            { interp_v3_v3v3(pixelScreenCo, edge_verts_inset_clip[0], edge_verts_inset_clip[1], fac); }
2623                                                                                 
2624                                                                                 if (!is_ortho) {
2625                                                                                         pixelScreenCo[3] = 1.0f;
2626                                                                                         mul_m4_v4((float(*)[4])ps->projectMat, pixelScreenCo); /* cast because of const */
2627                                                                                         pixelScreenCo[0] = (float)(ps->ar->winx/2.0f)+(ps->ar->winx/2.0f)*pixelScreenCo[0]/pixelScreenCo[3];    
2628                                                                                         pixelScreenCo[1] = (float)(ps->ar->winy/2.0f)+(ps->ar->winy/2.0f)*pixelScreenCo[1]/pixelScreenCo[3];
2629                                                                                         pixelScreenCo[2] = pixelScreenCo[2]/pixelScreenCo[3]; /* Use the depth for bucket point occlusion */
2630                                                                                 }
2631                                                                                 
2632                                                                                 if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucketFaceNodes, face_index, pixelScreenCo)) {
2633                                                                                         
2634                                                                                         /* Only bother calculating the weights if we intersect */
2635                                                                                         if (ps->do_mask_normal || ps->dm_mtface_clone) {
2636 #if 0
2637                                                                                                 /* This is not QUITE correct since UV is not inside the UV's but good enough for seams */
2638                                                                                                 if (side) {
2639                                                                                                         BarycentricWeights2f(uv, tf_uv_pxoffset[0], tf_uv_pxoffset[2], tf_uv_pxoffset[3], w);
2640                                                                                                 }
2641                                                                                                 else {
2642                                                                                                         BarycentricWeights2f(uv, tf_uv_pxoffset[0], tf_uv_pxoffset[1], tf_uv_pxoffset[2], w);
2643                                                                                                 }
2644 #endif
2645 #if 1
2646                                                                                                 /* Cheat, we know where we are along the edge so work out the weights from that */
2647                                                                                                 fac = fac1 + (fac * (fac2-fac1));
2648                                                                                                 w[0]=w[1]=w[2]= 0.0;
2649                                                                                                 if (side) {
2650                                                                                                         w[fidx1?fidx1-1:0] = fac;
2651                                                                                                         w[fidx2?fidx2-1:0] = 1.0-fac;
2652                                                                                                 }
2653                                                                                                 else {
2654                                                                                                         w[fidx1] = fac;
2655                                                                                                         w[fidx2] = 1.0-fac;
2656                                                                                                 }
2657 #endif
2658                                                                                         }
2659                                                                                         
2660                                                                                         /* a pitty we need to get the worldspace pixel location here */
2661                                                                                         if(ps->rv3d->rflag & RV3D_CLIPPING) {
2662                                                                                                 if (side)       interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v3].co, ps->dm_mvert[mf->v4].co, w);
2663                                                                                                 else            interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, w);
2664
2665                                                                                                 if(view3d_test_clipping(ps->rv3d, wco, 1)) {
2666                                                                                                         continue; /* Watch out that no code below this needs to run */
2667                                                                                                 }
2668                                                                                         }
2669                                                                                         
2670                                                                                         mask = project_paint_uvpixel_mask(ps, face_index, side, w);
2671                                                                                         
2672                                                                                         if (mask > 0.0f) {
2673                                                                                                 BLI_linklist_prepend_arena(
2674                                                                                                         bucketPixelNodes,
2675                                                                                                         project_paint_uvpixel_init(ps, arena, ibuf, x, y, mask, face_index, image_index, pixelScreenCo, side, w),
2676                                                                                                         arena
2677                                                                                                 );
2678                                                                                         }
2679                                                                                         
2680                                                                                 }
2681                                                                         }
2682                                                                         else if (has_x_isect) {
2683                                                                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2684                                                                                 break;
2685                                                                         }
2686                                                                 }
2687                                                                 
2688 #if 0                                                   /* TODO - investigate why this dosnt work sometimes! it should! */
2689                                                                 /* no intersection for this entire row, after some intersection above means we can quit now */
2690                                                                 if (has_x_isect==0 && has_isect) { 
2691                                                                         break;
2692                                                                 }
2693 #endif
2694                                                         }
2695                                                 }
2696                                         }
2697                                 }
2698                         }
2699                 }
2700         }
2701 #endif // PROJ_DEBUG_NOSEAMBLEED
2702 }
2703
2704
2705 /* takes floating point screenspace min/max and returns int min/max to be used as indicies for ps->bucketRect, ps->bucketFlags */
2706 static void project_paint_bucket_bounds(const ProjPaintState *ps, const float min[2], const float max[2], int bucketMin[2], int bucketMax[2])
2707 {
2708         /* divide by bucketWidth & bucketHeight so the bounds are offset in bucket grid units */
2709         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 */
2710         bucketMin[1] = (int)(((float)(min[1] - ps->screenMin[1]) / ps->screen_height) * ps->buckets_y) + 0.5f;
2711         
2712         bucketMax[0] = (int)(((float)(max[0] - ps->screenMin[0]) / ps->screen_width) * ps->buckets_x) + 1.5f;
2713         bucketMax[1] = (int)(((float)(max[1] - ps->screenMin[1]) / ps->screen_height) * ps->buckets_y) + 1.5f;  
2714         
2715         /* incase the rect is outside the mesh 2d bounds */
2716         CLAMP(bucketMin[0], 0, ps->buckets_x);
2717         CLAMP(bucketMin[1], 0, ps->buckets_y);
2718         
2719         CLAMP(bucketMax[0], 0, ps->buckets_x);
2720         CLAMP(bucketMax[1], 0, ps->buckets_y);
2721 }
2722
2723 /* set bucket_bounds to a screen space-aligned floating point bound-box */
2724 static void project_bucket_bounds(const ProjPaintState *ps, const int bucket_x, const int bucket_y, rctf *bucket_bounds)
2725 {
2726         bucket_bounds->xmin =   ps->screenMin[0]+((bucket_x)*(ps->screen_width / ps->buckets_x));               /* left */
2727         bucket_bounds->xmax =   ps->screenMin[0]+((bucket_x+1)*(ps->screen_width / ps->buckets_x));     /* right */
2728         
2729         bucket_bounds->ymin =   ps->screenMin[1]+((bucket_y)*(ps->screen_height / ps->buckets_y));              /* bottom */
2730         bucket_bounds->ymax =   ps->screenMin[1]+((bucket_y+1)*(ps->screen_height  / ps->buckets_y));   /* top */
2731 }
2732
2733 /* Fill this bucket with pixels from the faces that intersect it.
2734  * 
2735  * have bucket_bounds as an argument so we don;t need to give bucket_x/y the rect function needs */
2736 static void project_bucket_init(const ProjPaintState *ps, const int thread_index, const int bucket_index, rctf *bucket_bounds)
2737 {
2738         LinkNode *node;
2739         int face_index, image_index=0;
2740         ImBuf *ibuf = NULL;
2741         MTFace *tf;
2742         
2743         Image *tpage_last = NULL;
2744         
2745
2746         if (ps->image_tot==1) {
2747                 /* Simple loop, no context switching */
2748                 ibuf = ps->projImages[0].ibuf;
2749                 
2750                 for (node = ps->bucketFaces[bucket_index]; node; node= node->next) { 
2751                         project_paint_face_init(ps, thread_index, bucket_index, GET_INT_FROM_POINTER(node->link), 0, bucket_bounds, ibuf);
2752                 }
2753         }
2754         else {
2755                 
2756                 /* More complicated loop, switch between images */
2757                 for (node = ps->bucketFaces[bucket_index]; node; node= node->next) {
2758                         face_index = GET_INT_FROM_POINTER(node->link);
2759                                 
2760                         /* Image context switching */
2761                         tf = ps->dm_mtface+face_index;
2762                         if (tpage_last != tf->tpage) {
2763                                 tpage_last = tf->tpage;
2764                                 
2765                                 image_index = -1; /* sanity check */
2766                                 
2767                                 for (image_index=0; image_index < ps->image_tot; image_index++) {
2768                                         if (ps->projImages[image_index].ima == tpage_last) {
2769                                                 ibuf = ps->projImages[image_index].ibuf;
2770                                                 break;
2771                                         }
2772                                 }
2773                         }
2774                         /* context switching done */
2775                         
2776                         project_paint_face_init(ps, thread_index, bucket_index, face_index, image_index, bucket_bounds, ibuf);
2777                         
2778                 }
2779         }
2780         
2781         ps->bucketFlags[bucket_index] |= PROJ_BUCKET_INIT;
2782 }
2783
2784
2785 /* We want to know if a bucket and a face overlap in screen-space
2786  * 
2787  * Note, if this ever returns false positives its not that bad, since a face in the bounding area will have its pixels
2788  * calculated when it might not be needed later, (at the moment at least)
2789  * obviously it shouldn't have bugs though */
2790
2791 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)
2792 {
2793         /* TODO - replace this with a tricker method that uses sideofline for all screenCoords's edges against the closest bucket corner */
2794         rctf bucket_bounds;
2795         float p1[2], p2[2], p3[2], p4[2];
2796         float *v, *v1,*v2,*v3,*v4=NULL;
2797         int fidx;
2798         
2799         project_bucket_bounds(ps, bucket_x, bucket_y, &bucket_bounds);
2800         
2801         /* Is one of the faces verts in the bucket bounds? */
2802         
2803         fidx = mf->v4 ? 3:2;
2804         do {
2805                 v = ps->screenCoords[ (*(&mf->v1 + fidx)) ];