Copying scripts from 2.4x without 2.5x changes
[blender.git] / source / blender / editors / sculpt_paint / paint_image.c
1 /**
2  * $Id$
3  * imagepaint.c
4  *
5  * Functions to paint images in 2D and 3D.
6  * 
7  * ***** BEGIN GPL LICENSE BLOCK *****
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA        02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: some of this file.
27  *
28  * Contributor(s): Jens Ole Wund (bjornmose), Campbell Barton (ideasman42)
29  *
30  * ***** END GPL LICENSE BLOCK *****
31  */
32
33 #include <float.h>
34 #include <string.h>
35 #include <stdio.h>
36 #include <math.h>
37
38 #include "MEM_guardedalloc.h"
39
40 #ifdef WIN32
41 #include "BLI_winstuff.h"
42 #endif
43 #include "BLI_arithb.h"
44 #include "BLI_blenlib.h"
45 #include "BLI_dynstr.h"
46 #include "BLI_linklist.h"
47 #include "BLI_memarena.h"
48 #include "PIL_time.h"
49 #include "BLI_threads.h"
50
51 #include "IMB_imbuf.h"
52 #include "IMB_imbuf_types.h"
53
54 #include "DNA_brush_types.h"
55 #include "DNA_image_types.h"
56 #include "DNA_mesh_types.h"
57 #include "DNA_meshdata_types.h"
58 #include "DNA_node_types.h"
59 #include "DNA_object_types.h"
60 #include "DNA_scene_types.h"
61 #include "DNA_screen_types.h"
62 #include "DNA_space_types.h"
63 #include "DNA_userdef_types.h"
64 #include "DNA_view3d_types.h"
65 #include "DNA_windowmanager_types.h"
66
67 #include "BKE_context.h"
68 #include "BKE_brush.h"
69 #include "BKE_global.h"
70 #include "BKE_image.h"
71 #include "BKE_main.h"
72 #include "BKE_mesh.h"
73 #include "BKE_node.h"
74 #include "BKE_paint.h"
75 #include "BKE_utildefines.h"
76 #include "BKE_DerivedMesh.h"
77 #include "BKE_report.h"
78 #include "BKE_depsgraph.h"
79
80 #include "BIF_gl.h"
81 #include "BIF_glutil.h"
82
83 #include "UI_interface.h"
84 #include "UI_view2d.h"
85
86 #include "ED_image.h"
87 #include "ED_object.h"
88 #include "ED_screen.h"
89 #include "ED_view3d.h"
90
91 #include "WM_api.h"
92 #include "WM_types.h"
93
94 #include "RNA_access.h"
95 #include "RNA_define.h"
96
97 #include "GPU_draw.h"
98
99 #include "paint_intern.h"
100
101 /* Defines and Structs */
102
103 #define IMAPAINT_CHAR_TO_FLOAT(c) ((c)/255.0f)
104
105 #define IMAPAINT_FLOAT_RGB_TO_CHAR(c, f) { (c)[0]=FTOCHAR((f)[0]); (c)[1]=FTOCHAR((f)[1]); (c)[2]=FTOCHAR((f)[2]); }
106 #define IMAPAINT_FLOAT_RGBA_TO_CHAR(c, f) { (c)[0]=FTOCHAR((f)[0]); (c)[1]=FTOCHAR((f)[1]); (c)[2]=FTOCHAR((f)[2]); (c)[3]=FTOCHAR((f)[3]); }
107
108 #define IMAPAINT_CHAR_RGB_TO_FLOAT(f, c) { (f)[0]=IMAPAINT_CHAR_TO_FLOAT((c)[0]); (f)[1]=IMAPAINT_CHAR_TO_FLOAT((c)[1]); (f)[2]=IMAPAINT_CHAR_TO_FLOAT((c)[2]); }
109 #define IMAPAINT_CHAR_RGBA_TO_FLOAT(f, c) { (f)[0]=IMAPAINT_CHAR_TO_FLOAT((c)[0]); (f)[1]=IMAPAINT_CHAR_TO_FLOAT((c)[1]); (f)[2]=IMAPAINT_CHAR_TO_FLOAT((c)[2]); (f)[3]=IMAPAINT_CHAR_TO_FLOAT((c)[3]); }
110 #define IMAPAINT_FLOAT_RGB_COPY(a, b) VECCOPY(a, b)
111
112 #define IMAPAINT_TILE_BITS                      6
113 #define IMAPAINT_TILE_SIZE                      (1 << IMAPAINT_TILE_BITS)
114 #define IMAPAINT_TILE_NUMBER(size)      (((size)+IMAPAINT_TILE_SIZE-1) >> IMAPAINT_TILE_BITS)
115
116 #define MAXUNDONAME     64
117
118 static void imapaint_image_update(SpaceImage *sima, Image *image, ImBuf *ibuf, short texpaint);
119
120
121 typedef struct ImagePaintState {
122         SpaceImage *sima;
123         View2D *v2d;
124         Scene *scene;
125         bScreen *screen;
126
127         Brush *brush;
128         short tool, blend;
129         Image *image;
130         ImBuf *canvas;
131         ImBuf *clonecanvas;
132         short clonefreefloat;
133         char *warnpackedfile;
134         char *warnmultifile;
135
136         /* texture paint only */
137         Object *ob;
138         Mesh *me;
139         int faceindex;
140         float uv[2];
141 } ImagePaintState;
142
143 typedef struct ImagePaintPartialRedraw {
144         int x1, y1, x2, y2;
145         int enabled;
146 } ImagePaintPartialRedraw;
147
148
149 /* ProjectionPaint defines */
150
151 /* approx the number of buckets to have under the brush,
152  * used with the brush size to set the ps->buckets_x and ps->buckets_y value.
153  * 
154  * When 3 - a brush should have ~9 buckets under it at once
155  * ...this helps for threading while painting as well as
156  * avoiding initializing pixels that wont touch the brush */
157 #define PROJ_BUCKET_BRUSH_DIV 4
158
159 #define PROJ_BUCKET_RECT_MIN 4
160 #define PROJ_BUCKET_RECT_MAX 256
161
162 #define PROJ_BOUNDBOX_DIV 8
163 #define PROJ_BOUNDBOX_SQUARED  (PROJ_BOUNDBOX_DIV * PROJ_BOUNDBOX_DIV)
164
165 //#define PROJ_DEBUG_PAINT 1
166 //#define PROJ_DEBUG_NOSEAMBLEED 1
167 //#define PROJ_DEBUG_PRINT_CLIP 1
168 #define PROJ_DEBUG_WINCLIP 1
169
170 /* projectFaceSeamFlags options */
171 //#define PROJ_FACE_IGNORE      1<<0    /* When the face is hidden, backfacing or occluded */
172 //#define PROJ_FACE_INIT        1<<1    /* When we have initialized the faces data */
173 #define PROJ_FACE_SEAM1 1<<0    /* If this face has a seam on any of its edges */
174 #define PROJ_FACE_SEAM2 1<<1
175 #define PROJ_FACE_SEAM3 1<<2
176 #define PROJ_FACE_SEAM4 1<<3
177
178 #define PROJ_FACE_NOSEAM1       1<<4
179 #define PROJ_FACE_NOSEAM2       1<<5
180 #define PROJ_FACE_NOSEAM3       1<<6
181 #define PROJ_FACE_NOSEAM4       1<<7
182
183 /* a slightly scaled down face is used to get fake 3D location for edge pixels in the seams
184  * as this number approaches  1.0f the likelihood increases of float precision errors where
185  * it is occluded by an adjacent face */
186 #define PROJ_FACE_SCALE_SEAM    0.99f
187
188 #define PROJ_BUCKET_NULL                0
189 #define PROJ_BUCKET_INIT                1<<0
190 // #define PROJ_BUCKET_CLONE_INIT       1<<1
191
192 /* used for testing doubles, if a point is on a line etc */
193 #define PROJ_GEOM_TOLERANCE 0.00075f
194
195 /* vert flags */
196 #define PROJ_VERT_CULL 1
197
198 #define PI_80_DEG ((M_PI_2 / 9) * 8)
199
200 /* This is mainly a convenience struct used so we can keep an array of images we use
201  * Thir imbufs, etc, in 1 array, When using threads this array is copied for each thread
202  * because 'partRedrawRect' and 'touch' values would not be thread safe */
203 typedef struct ProjPaintImage {
204         Image *ima;
205         ImBuf *ibuf;
206         ImagePaintPartialRedraw *partRedrawRect;
207         struct UndoTile **undoRect; /* only used to build undo tiles after painting */
208         int touch;
209 } ProjPaintImage;
210
211 /* Main projection painting struct passed to all projection painting functions */
212 typedef struct ProjPaintState {
213         View3D *v3d;
214         RegionView3D *rv3d;
215         ARegion *ar;
216         Scene *scene;
217
218         Brush *brush;
219         short tool, blend;
220         Object *ob;
221         /* end similarities with ImagePaintState */
222         
223         DerivedMesh    *dm;
224         int                     dm_totface;
225         int                     dm_totvert;
226         
227         MVert              *dm_mvert;
228         MFace              *dm_mface;
229         MTFace             *dm_mtface;
230         MTFace             *dm_mtface_clone;    /* other UV layer, use for cloning between layers */
231         MTFace             *dm_mtface_mask;
232         
233         /* projection painting only */
234         MemArena *arena_mt[BLENDER_MAX_THREADS];/* for multithreading, the first item is sometimes used for non threaded cases too */
235         LinkNode **bucketRect;                          /* screen sized 2D array, each pixel has a linked list of ProjPixel's */
236         LinkNode **bucketFaces;                         /* bucketRect aligned array linkList of faces overlapping each bucket */
237         unsigned char *bucketFlags;                                     /* store if the bucks have been initialized  */
238 #ifndef PROJ_DEBUG_NOSEAMBLEED
239         char *faceSeamFlags;                            /* store info about faces, if they are initialized etc*/
240         float (*faceSeamUVs)[4][2];                     /* expanded UVs for faces to use as seams */
241         LinkNode **vertFaces;                           /* Only needed for when seam_bleed_px is enabled, use to find UV seams */
242 #endif
243         char *vertFlags;                                        /* store options per vert, now only store if the vert is pointing away from the view */
244         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 */
245         int buckets_y;
246         
247         ProjPaintImage *projImages;
248         
249         int image_tot;                          /* size of projectImages array */
250         
251         float (*screenCoords)[4];       /* verts projected into floating point screen space */
252         
253         float screenMin[2];                     /* 2D bounds for mesh verts on the screen's plane (screenspace) */
254         float screenMax[2]; 
255         float screen_width;                     /* Calculated from screenMin & screenMax */
256         float screen_height;
257         
258         /* options for projection painting */
259         int do_layer_clone;
260         int do_layer_mask;
261         int do_layer_mask_inv;
262         
263         short do_occlude;                       /* Use raytraced occlusion? - ortherwise will paint right through to the back*/
264         short do_backfacecull;  /* ignore faces with normals pointing away, skips a lot of raycasts if your normals are correctly flipped */
265         short do_mask_normal;                   /* mask out pixels based on their normals */
266         float normal_angle;                             /* what angle to mask at*/
267         float normal_angle_inner;
268         float normal_angle_range;               /* difference between normal_angle and normal_angle_inner, for easy access */
269         
270         short is_ortho;
271         short is_airbrush;                                      /* only to avoid using (ps.brush->flag & BRUSH_AIRBRUSH) */
272         short is_texbrush;                                      /* only to avoid running  */
273 #ifndef PROJ_DEBUG_NOSEAMBLEED
274         float seam_bleed_px;
275 #endif
276         /* clone vars */
277         float cloneOffset[2];
278         
279         float projectMat[4][4];         /* Projection matrix, use for getting screen coords */
280         float viewDir[3];                       /* View vector, use for do_backfacecull and for ray casting with an ortho viewport  */
281         float viewPos[3];                       /* View location in object relative 3D space, so can compare to verts  */
282         float clipsta, clipend;
283         
284         /* threads */
285         int thread_tot;
286         int bucketMin[2];
287         int bucketMax[2];
288         int context_bucket_x, context_bucket_y; /* must lock threads while accessing these */
289 } ProjPaintState;
290
291 typedef union pixelPointer
292 {
293         float *f_pt;                    /* float buffer */
294         unsigned int *uint_pt; /* 2 ways to access a char buffer */
295         unsigned char *ch_pt;
296 } PixelPointer;
297
298 typedef union pixelStore
299 {
300         unsigned char ch[4];
301         unsigned int uint;
302         float f[4];
303 } PixelStore;
304
305 typedef struct ProjPixel {
306         float projCoSS[2]; /* the floating point screen projection of this pixel */
307         
308         /* Only used when the airbrush is disabled.
309          * Store the max mask value to avoid painting over an area with a lower opacity
310          * with an advantage that we can avoid touching the pixel at all, if the 
311          * new mask value is lower then mask_max */
312         unsigned short mask_max;
313         
314         /* for various reasons we may want to mask out painting onto this pixel */
315         unsigned short mask;
316         
317         short x_px, y_px;
318         
319         PixelStore origColor;
320         PixelStore newColor;
321         PixelPointer pixel;
322         
323         short image_index; /* if anyone wants to paint onto more then 32768 images they can bite me */
324         unsigned char bb_cell_index;
325 } ProjPixel;
326
327 typedef struct ProjPixelClone {
328         struct ProjPixel __pp;
329         PixelStore clonepx;
330 } ProjPixelClone;
331
332 /* Finish projection painting structs */
333
334
335 typedef struct UndoTile {
336         struct UndoTile *next, *prev;
337         ID id;
338         void *rect;
339         int x, y;
340 } UndoTile;
341
342 typedef struct UndoElem {
343         struct UndoElem *next, *prev;
344         char name[MAXUNDONAME];
345         uintptr_t undosize;
346
347         ImBuf *ibuf;
348         ListBase tiles;
349 } UndoElem;
350
351 static ListBase undobase = {NULL, NULL};
352 static UndoElem *curundo = NULL;
353 static ImagePaintPartialRedraw imapaintpartial = {0, 0, 0, 0, 0};
354
355 /* UNDO */
356
357 /* internal functions */
358
359 static void undo_copy_tile(UndoTile *tile, ImBuf *tmpibuf, ImBuf *ibuf, int restore)
360 {
361         /* copy or swap contents of tile->rect and region in ibuf->rect */
362         IMB_rectcpy(tmpibuf, ibuf, 0, 0, tile->x*IMAPAINT_TILE_SIZE,
363                 tile->y*IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE);
364
365         if(ibuf->rect_float) {
366                 SWAP(void*, tmpibuf->rect_float, tile->rect);
367         } else {
368                 SWAP(void*, tmpibuf->rect, tile->rect);
369         }
370         
371         if(restore)
372                 IMB_rectcpy(ibuf, tmpibuf, tile->x*IMAPAINT_TILE_SIZE,
373                         tile->y*IMAPAINT_TILE_SIZE, 0, 0, IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE);
374 }
375
376 static UndoTile *undo_init_tile(ID *id, ImBuf *ibuf, ImBuf **tmpibuf, int x_tile, int y_tile)
377 {
378         UndoTile *tile;
379         int allocsize;
380         
381         if (*tmpibuf==NULL)
382                 *tmpibuf = IMB_allocImBuf(IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, 32, IB_rectfloat|IB_rect, 0);
383         
384         tile= MEM_callocN(sizeof(UndoTile), "ImaUndoTile");
385         tile->id= *id;
386         tile->x= x_tile;
387         tile->y= y_tile;
388
389         allocsize= IMAPAINT_TILE_SIZE*IMAPAINT_TILE_SIZE*4;
390         allocsize *= (ibuf->rect_float)? sizeof(float): sizeof(char);
391         tile->rect= MEM_mapallocN(allocsize, "ImaUndoRect");
392
393         undo_copy_tile(tile, *tmpibuf, ibuf, 0);
394         curundo->undosize += allocsize;
395
396         BLI_addtail(&curundo->tiles, tile);
397         
398         return tile;
399 }
400
401 static void undo_restore(UndoElem *undo)
402 {
403         Image *ima = NULL;
404         ImBuf *ibuf, *tmpibuf;
405         UndoTile *tile;
406
407         if(!undo)
408                 return;
409
410         tmpibuf= IMB_allocImBuf(IMAPAINT_TILE_SIZE, IMAPAINT_TILE_SIZE, 32,
411                                 IB_rectfloat|IB_rect, 0);
412         
413         for(tile=undo->tiles.first; tile; tile=tile->next) {
414                 /* find image based on name, pointer becomes invalid with global undo */
415                 if(ima && strcmp(tile->id.name, ima->id.name)==0);
416                 else {
417                         for(ima=G.main->image.first; ima; ima=ima->id.next)
418                                 if(strcmp(tile->id.name, ima->id.name)==0)
419                                         break;
420                 }
421
422                 ibuf= BKE_image_get_ibuf(ima, NULL);
423
424                 if (!ima || !ibuf || !(ibuf->rect || ibuf->rect_float))
425                         continue;
426
427                 undo_copy_tile(tile, tmpibuf, ibuf, 1);
428
429                 GPU_free_image(ima); /* force OpenGL reload */
430                 if(ibuf->rect_float)
431                         imb_freerectImBuf(ibuf); /* force recreate of char rect */
432         }
433
434         IMB_freeImBuf(tmpibuf);
435 }
436
437 static void undo_free(UndoElem *undo)
438 {
439         UndoTile *tile;
440
441         for(tile=undo->tiles.first; tile; tile=tile->next)
442                 MEM_freeN(tile->rect);
443         BLI_freelistN(&undo->tiles);
444 }
445
446 static void undo_imagepaint_push_begin(char *name)
447 {
448         UndoElem *uel;
449         int nr;
450         
451         /* Undo push is split up in begin and end, the reason is that as painting
452          * happens more tiles are added to the list, and at the very end we know
453          * how much memory the undo used to remove old undo elements */
454
455         /* remove all undos after (also when curundo==NULL) */
456         while(undobase.last != curundo) {
457                 uel= undobase.last;
458                 undo_free(uel);
459                 BLI_freelinkN(&undobase, uel);
460         }
461         
462         /* make new */
463         curundo= uel= MEM_callocN(sizeof(UndoElem), "undo file");
464         BLI_addtail(&undobase, uel);
465
466         /* name can be a dynamic string */
467         strncpy(uel->name, name, MAXUNDONAME-1);
468         
469         /* limit amount to the maximum amount*/
470         nr= 0;
471         uel= undobase.last;
472         while(uel) {
473                 nr++;
474                 if(nr==U.undosteps) break;
475                 uel= uel->prev;
476         }
477         if(uel) {
478                 while(undobase.first!=uel) {
479                         UndoElem *first= undobase.first;
480                         undo_free(first);
481                         BLI_freelinkN(&undobase, first);
482                 }
483         }
484 }
485
486 static void undo_imagepaint_push_end()
487 {
488         UndoElem *uel;
489         uintptr_t totmem, maxmem;
490
491         if(U.undomemory != 0) {
492                 /* limit to maximum memory (afterwards, we can't know in advance) */
493                 totmem= 0;
494                 maxmem= ((uintptr_t)U.undomemory)*1024*1024;
495
496                 uel= undobase.last;
497                 while(uel) {
498                         totmem+= uel->undosize;
499                         if(totmem>maxmem) break;
500                         uel= uel->prev;
501                 }
502
503                 if(uel) {
504                         while(undobase.first!=uel) {
505                                 UndoElem *first= undobase.first;
506                                 undo_free(first);
507                                 BLI_freelinkN(&undobase, first);
508                         }
509                 }
510         }
511 }
512
513 void undo_imagepaint_step(int step)
514 {
515         UndoElem *undo;
516
517         if(step==1) {
518                 if(curundo==NULL);
519                 else {
520                         if(G.f & G_DEBUG) printf("undo %s\n", curundo->name);
521                         undo_restore(curundo);
522                         curundo= curundo->prev;
523                 }
524         }
525         else if(step==-1) {
526                 if((curundo!=NULL && curundo->next==NULL) || undobase.first==NULL);
527                 else {
528                         undo= (curundo && curundo->next)? curundo->next: undobase.first;
529                         undo_restore(undo);
530                         curundo= undo;
531                         if(G.f & G_DEBUG) printf("redo %s\n", undo->name);
532                 }
533         }
534 }
535
536 void undo_imagepaint_clear(void)
537 {
538         UndoElem *uel;
539         
540         uel= undobase.first;
541         while(uel) {
542                 undo_free(uel);
543                 uel= uel->next;
544         }
545
546         BLI_freelistN(&undobase);
547         curundo= NULL;
548 }
549
550 /* fast projection bucket array lookup, use the safe version for bound checking  */
551 static int project_bucket_offset(const ProjPaintState *ps, const float projCoSS[2])
552 {
553         /* If we were not dealing with screenspace 2D coords we could simple do...
554          * ps->bucketRect[x + (y*ps->buckets_y)] */
555         
556         /* please explain?
557          * projCoSS[0] - ps->screenMin[0]       : zero origin
558          * ... / ps->screen_width                               : range from 0.0 to 1.0
559          * ... * ps->buckets_x          : use as a bucket index
560          *
561          * Second multiplication does similar but for vertical offset
562          */
563         return  (       (int)(((projCoSS[0] - ps->screenMin[0]) / ps->screen_width)  * ps->buckets_x)) + 
564                 (       (       (int)(((projCoSS[1] - ps->screenMin[1])  / ps->screen_height) * ps->buckets_y)) * ps->buckets_x);
565 }
566
567 static int project_bucket_offset_safe(const ProjPaintState *ps, const float projCoSS[2])
568 {
569         int bucket_index = project_bucket_offset(ps, projCoSS);
570         
571         if (bucket_index < 0 || bucket_index >= ps->buckets_x*ps->buckets_y) {  
572                 return -1;
573         }
574         else {
575                 return bucket_index;
576         }
577 }
578
579 #define SIDE_OF_LINE(pa, pb, pp)        ((pa[0]-pp[0])*(pb[1]-pp[1]))-((pb[0]-pp[0])*(pa[1]-pp[1]))
580
581 static float AreaSignedF2Dfl(float *v1, float *v2, float *v3)
582 {
583    return (float)(0.5f*((v1[0]-v2[0])*(v2[1]-v3[1]) +
584 (v1[1]-v2[1])*(v3[0]-v2[0])));
585 }
586
587 static void BarycentricWeights2f(float pt[2], float v1[2], float v2[2], float v3[2], float w[3])
588 {
589    float wtot_inv, wtot;
590
591    w[0] = AreaSignedF2Dfl(v2, v3, pt);
592    w[1] = AreaSignedF2Dfl(v3, v1, pt);
593    w[2] = AreaSignedF2Dfl(v1, v2, pt);
594    wtot = w[0]+w[1]+w[2];
595
596    if (wtot != 0.0f) {
597        wtot_inv = 1.0f/wtot;
598
599        w[0] = w[0]*wtot_inv;
600        w[1] = w[1]*wtot_inv;
601        w[2] = w[2]*wtot_inv;
602    }
603    else /* dummy values for zero area face */
604        w[0] = w[1] = w[2] = 1.0f/3.0f;
605 }
606
607 /* still use 2D X,Y space but this works for verts transformed by a perspective matrix, using their 4th component as a weight */
608 static void BarycentricWeightsPersp2f(float pt[2], float v1[4], float v2[4], float v3[4], float w[3])
609 {
610    float wtot_inv, wtot;
611
612    w[0] = AreaSignedF2Dfl(v2, v3, pt) / v1[3];
613    w[1] = AreaSignedF2Dfl(v3, v1, pt) / v2[3];
614    w[2] = AreaSignedF2Dfl(v1, v2, pt) / v3[3];
615    wtot = w[0]+w[1]+w[2];
616
617    if (wtot != 0.0f) {
618        wtot_inv = 1.0f/wtot;
619
620        w[0] = w[0]*wtot_inv;
621        w[1] = w[1]*wtot_inv;
622        w[2] = w[2]*wtot_inv;
623    }
624    else /* dummy values for zero area face */
625        w[0] = w[1] = w[2] = 1.0f/3.0f;
626 }
627
628 static float VecZDepthOrtho(float pt[2], float v1[3], float v2[3], float v3[3], float w[3])
629 {
630         BarycentricWeights2f(pt, v1, v2, v3, w);
631         return (v1[2]*w[0]) + (v2[2]*w[1]) + (v3[2]*w[2]);
632 }
633
634 static float VecZDepthPersp(float pt[2], float v1[3], float v2[3], float v3[3], float w[3])
635 {
636         BarycentricWeightsPersp2f(pt, v1, v2, v3, w);
637         return (v1[2]*w[0]) + (v2[2]*w[1]) + (v3[2]*w[2]);
638 }
639
640
641 /* Return the top-most face index that the screen space coord 'pt' touches (or -1) */
642 static int project_paint_PickFace(const ProjPaintState *ps, float pt[2], float w[3], int *side)
643 {
644         LinkNode *node;
645         float w_tmp[3];
646         float *v1, *v2, *v3, *v4;
647         int bucket_index;
648         int face_index;
649         int best_side = -1;
650         int best_face_index = -1;
651         float z_depth_best = FLT_MAX, z_depth;
652         MFace *mf;
653         
654         bucket_index = project_bucket_offset_safe(ps, pt);
655         if (bucket_index==-1)
656                 return -1;
657         
658         
659         
660         /* we could return 0 for 1 face buckets, as long as this function assumes
661          * that the point its testing is only every originated from an existing face */
662         
663         for (node= ps->bucketFaces[bucket_index]; node; node= node->next) {
664                 face_index = GET_INT_FROM_POINTER(node->link);
665                 mf= ps->dm_mface + face_index;
666                 
667                 v1= ps->screenCoords[mf->v1];
668                 v2= ps->screenCoords[mf->v2];
669                 v3= ps->screenCoords[mf->v3];
670                 
671                 if (IsectPT2Df(pt, v1, v2, v3)) {
672                         if (ps->is_ortho)       z_depth= VecZDepthOrtho(pt, v1, v2, v3, w_tmp);
673                         else                            z_depth= VecZDepthPersp(pt, v1, v2, v3, w_tmp);
674                         
675                         if (z_depth < z_depth_best) {
676                                 best_face_index = face_index;
677                                 best_side = 0;
678                                 z_depth_best = z_depth;
679                                 VECCOPY(w, w_tmp);
680                         }
681                 }
682                 else if (mf->v4) {
683                         v4= ps->screenCoords[mf->v4];
684                         
685                         if (IsectPT2Df(pt, v1, v3, v4)) {
686                                 if (ps->is_ortho)       z_depth= VecZDepthOrtho(pt, v1, v3, v4, w_tmp);
687                                 else                            z_depth= VecZDepthPersp(pt, v1, v3, v4, w_tmp);
688
689                                 if (z_depth < z_depth_best) {
690                                         best_face_index = face_index;
691                                         best_side= 1;
692                                         z_depth_best = z_depth;
693                                         VECCOPY(w, w_tmp);
694                                 }
695                         }
696                 }
697         }
698         
699         *side = best_side;
700         return best_face_index; /* will be -1 or a valid face */
701 }
702
703 /* Converts a uv coord into a pixel location wrapping if the uv is outside 0-1 range */
704 static void uvco_to_wrapped_pxco(float uv[2], int ibuf_x, int ibuf_y, float *x, float *y)
705 {
706         /* use */
707         *x = (float)fmodf(uv[0], 1.0f);
708         *y = (float)fmodf(uv[1], 1.0f);
709         
710         if (*x < 0.0f) *x += 1.0f;
711         if (*y < 0.0f) *y += 1.0f;
712         
713         *x = *x * ibuf_x - 0.5f;
714         *y = *y * ibuf_y - 0.5f;
715 }
716
717 /* Set the top-most face color that the screen space coord 'pt' touches (or return 0 if none touch) */
718 static int project_paint_PickColor(const ProjPaintState *ps, float pt[2], float *rgba_fp, unsigned char *rgba, const int interp)
719 {
720         float w[3], uv[2];
721         int side;
722         int face_index;
723         MTFace *tf;
724         ImBuf *ibuf;
725         int xi, yi;
726         
727         
728         face_index = project_paint_PickFace(ps, pt, w, &side);
729         
730         if (face_index == -1)
731                 return 0;
732         
733         tf = ps->dm_mtface + face_index;
734         
735         if (side == 0) {
736                 Vec2Lerp3f(uv, tf->uv[0], tf->uv[1], tf->uv[2], w);
737         }
738         else { /* QUAD */
739                 Vec2Lerp3f(uv, tf->uv[0], tf->uv[2], tf->uv[3], w);
740         }
741         
742         ibuf = tf->tpage->ibufs.first; /* we must have got the imbuf before getting here */
743         if (!ibuf) return 0;
744         
745         if (interp) {
746                 float x, y;
747                 uvco_to_wrapped_pxco(uv, ibuf->x, ibuf->y, &x, &y);
748                 
749                 if (ibuf->rect_float) {
750                         if (rgba_fp) {
751                                 bilinear_interpolation_color_wrap(ibuf, NULL, rgba_fp, x, y);
752                         }
753                         else {
754                                 float rgba_tmp_f[4];
755                                 bilinear_interpolation_color_wrap(ibuf, NULL, rgba_tmp_f, x, y);
756                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(rgba, rgba_tmp_f);
757                         }
758                 }
759                 else {
760                         if (rgba) {
761                                 bilinear_interpolation_color_wrap(ibuf, rgba, NULL, x, y);
762                         }
763                         else {
764                                 unsigned char rgba_tmp[4];
765                                 bilinear_interpolation_color_wrap(ibuf, rgba_tmp, NULL, x, y);
766                                 IMAPAINT_CHAR_RGBA_TO_FLOAT(rgba_fp, rgba_tmp);
767                         }
768                 }
769         }
770         else {
771                 xi = (uv[0]*ibuf->x) + 0.5f;
772                 yi = (uv[1]*ibuf->y) + 0.5f;
773                 
774                 //if (xi<0 || xi>=ibuf->x  ||  yi<0 || yi>=ibuf->y) return 0;
775                 
776                 /* wrap */
777                 xi = ((int)(uv[0]*ibuf->x)) % ibuf->x;
778                 if (xi<0) xi += ibuf->x;
779                 yi = ((int)(uv[1]*ibuf->y)) % ibuf->y;
780                 if (yi<0) yi += ibuf->y;
781                 
782                 
783                 if (rgba) {
784                         if (ibuf->rect_float) {
785                                 float *rgba_tmp_fp = ibuf->rect_float + (xi + yi * ibuf->x * 4);
786                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(rgba, rgba_tmp_fp);
787                         }
788                         else {
789                                 *((unsigned int *)rgba) = *(unsigned int *)(((char *)ibuf->rect) + ((xi + yi * ibuf->x) * 4));
790                         }
791                 }
792                 
793                 if (rgba_fp) {
794                         if (ibuf->rect_float) {
795                                 QUATCOPY(rgba_fp, ((float *)ibuf->rect_float + ((xi + yi * ibuf->x) * 4)));
796                         }
797                         else {
798                                 char *tmp_ch= ((char *)ibuf->rect) + ((xi + yi * ibuf->x) * 4);
799                                 IMAPAINT_CHAR_RGBA_TO_FLOAT(rgba_fp, tmp_ch);
800                         }
801                 }
802         }
803         return 1;
804 }
805
806 /* Check if 'pt' is infront of the 3 verts on the Z axis (used for screenspace occlusuion test)
807  * return...
808  *  0   : no occlusion
809  * -1   : no occlusion but 2D intersection is true (avoid testing the other half of a quad)
810  *  1   : occluded
811     2   : occluded with w[3] weights set (need to know in some cases) */
812
813 static int project_paint_occlude_ptv(float pt[3], float v1[3], float v2[3], float v3[3], float w[3], int is_ortho)
814 {
815         /* if all are behind us, return false */
816         if(v1[2] > pt[2] && v2[2] > pt[2] && v3[2] > pt[2])
817                 return 0;
818                 
819         /* do a 2D point in try intersection */
820         if (!IsectPT2Df(pt, v1, v2, v3))
821                 return 0; /* we know there is  */
822         
823
824         /* From here on we know there IS an intersection */
825         /* if ALL of the verts are infront of us then we know it intersects ? */
826         if(v1[2] < pt[2] && v2[2] < pt[2] && v3[2] < pt[2]) {
827                 return 1;
828         }
829         else {
830                 /* we intersect? - find the exact depth at the point of intersection */
831                 /* Is this point is occluded by another face? */
832                 if (is_ortho) {
833                         if (VecZDepthOrtho(pt, v1, v2, v3, w) < pt[2]) return 2;
834                 }
835                 else {
836                         if (VecZDepthPersp(pt, v1, v2, v3, w) < pt[2]) return 2;
837                 }
838         }
839         return -1;
840 }
841
842
843 static int project_paint_occlude_ptv_clip(
844                 const ProjPaintState *ps, const MFace *mf,
845                 float pt[3], float v1[3], float v2[3], float v3[3],
846                 const int side )
847 {
848         float w[3], wco[3];
849         int ret = project_paint_occlude_ptv(pt, v1, v2, v3, w, ps->is_ortho);
850
851         if (ret <= 0)
852                 return ret;
853
854         if (ret==1) { /* weights not calculated */
855                 if (ps->is_ortho)       BarycentricWeights2f(pt, v1, v2, v3, w);
856                 else                            BarycentricWeightsPersp2f(pt, v1, v2, v3, w);
857         }
858
859         /* Test if we're in the clipped area, */
860         if (side)       VecLerp3f(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v3].co, ps->dm_mvert[mf->v4].co, w);
861         else            VecLerp3f(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, w);
862         
863         Mat4MulVecfl(ps->ob->obmat, wco);
864         if(!view3d_test_clipping(ps->rv3d, wco)) {
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         Vec2Subf(dir1, puv[1], puv[0]);
1165         Vec2Subf(dir2, puv[2], puv[1]);
1166         Normalize2(dir1);
1167         Normalize2(dir2);
1168         
1169         if (is_quad) {
1170                 Vec2Subf(dir3, puv[3], puv[2]);
1171                 Vec2Subf(dir4, puv[0], puv[3]);
1172                 Normalize2(dir3);
1173                 Normalize2(dir4);
1174         }
1175         else {
1176                 Vec2Subf(dir3, puv[0], puv[2]);
1177                 Normalize2(dir3);
1178         }
1179         
1180         if (is_quad) {
1181                 a1 = AngleToLength(NormalizedVecAngle2_2D(dir4, dir1));
1182                 a2 = AngleToLength(NormalizedVecAngle2_2D(dir1, dir2));
1183                 a3 = AngleToLength(NormalizedVecAngle2_2D(dir2, dir3));
1184                 a4 = AngleToLength(NormalizedVecAngle2_2D(dir3, dir4));
1185         }
1186         else {
1187                 a1 = AngleToLength(NormalizedVecAngle2_2D(dir3, dir1));
1188                 a2 = AngleToLength(NormalizedVecAngle2_2D(dir1, dir2));
1189                 a3 = AngleToLength(NormalizedVecAngle2_2D(dir2, dir3));
1190         }
1191         
1192         if (is_quad) {
1193                 Vec2Subf(no1, dir4, dir1);
1194                 Vec2Subf(no2, dir1, dir2);
1195                 Vec2Subf(no3, dir2, dir3);
1196                 Vec2Subf(no4, dir3, dir4);
1197                 Normalize2(no1);
1198                 Normalize2(no2);
1199                 Normalize2(no3);
1200                 Normalize2(no4);
1201                 Vec2Mulf(no1, a1*scaler);
1202                 Vec2Mulf(no2, a2*scaler);
1203                 Vec2Mulf(no3, a3*scaler);
1204                 Vec2Mulf(no4, a4*scaler);
1205                 Vec2Addf(outset_uv[0], puv[0], no1);
1206                 Vec2Addf(outset_uv[1], puv[1], no2);
1207                 Vec2Addf(outset_uv[2], puv[2], no3);
1208                 Vec2Addf(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                 Vec2Subf(no1, dir3, dir1);
1223                 Vec2Subf(no2, dir1, dir2);
1224                 Vec2Subf(no3, dir2, dir3);
1225                 Normalize2(no1);
1226                 Normalize2(no2);
1227                 Normalize2(no3);
1228                 Vec2Mulf(no1, a1*scaler);
1229                 Vec2Mulf(no2, a2*scaler);
1230                 Vec2Mulf(no3, a3*scaler);
1231                 Vec2Addf(outset_uv[0], puv[0], no1);
1232                 Vec2Addf(outset_uv[1], puv[1], no2);
1233                 Vec2Addf(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(Inp2f(u, h)/Inp2f(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         VecLerp3f(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         VecLerp3f(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         Vec2Lerp3f(uv_other, uvCo1, uvCo2, uvCo3, 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(no);
1435                 
1436                 /* now we can use the normal as a mask */
1437                 if (ps->is_ortho) {
1438                         angle = NormalizedVecAngle2((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(viewDirPersp);
1459                         
1460                         angle = NormalizedVecAngle2(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                         Vec2Subf(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         VecSubf(insetCos[0], origCos[0], cent);
1772         VecSubf(insetCos[1], origCos[1], cent);
1773         VecSubf(insetCos[2], origCos[2], cent);
1774         VecSubf(insetCos[3], origCos[3], cent);
1775         
1776         VecMulf(insetCos[0], inset);
1777         VecMulf(insetCos[1], inset);
1778         VecMulf(insetCos[2], inset);
1779         VecMulf(insetCos[3], inset);
1780         
1781         VecAddf(insetCos[0], insetCos[0], cent);
1782         VecAddf(insetCos[1], insetCos[1], cent);
1783         VecAddf(insetCos[2], insetCos[2], cent);
1784         VecAddf(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         VecSubf(insetCos[0], origCos[0], cent);
1796         VecSubf(insetCos[1], origCos[1], cent);
1797         VecSubf(insetCos[2], origCos[2], cent);
1798         
1799         VecMulf(insetCos[0], inset);
1800         VecMulf(insetCos[1], inset);
1801         VecMulf(insetCos[2], inset);
1802         
1803         VecAddf(insetCos[0], insetCos[0], cent);
1804         VecAddf(insetCos[1], insetCos[1], cent);
1805         VecAddf(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         Vec2Lerp3f(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         Vec2Lerp3f(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         Vec2Lerp3f(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         Vec2Lerp3f(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         Vec2Lerp3f(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         Vec2Lerp3f(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         Vec2Lerp3f(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         Vec2Lerp3f(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 ((AreaF2Dfl(pt,v1,v2) + AreaF2Dfl(pt,v2,v3) + AreaF2Dfl(pt,v3,v1)) / (AreaF2Dfl(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                                 Vec2Lerp3f(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                                 Vec2Lerp3f(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                                                         VecLerp3f(wco, ps->dm_mvert[ (*(&mf->v1 + i1)) ].co, ps->dm_mvert[ (*(&mf->v1 + i2)) ].co, ps->dm_mvert[ (*(&mf->v1 + i3)) ].co, w);
2448                                                         Mat4MulVecfl(ps->ob->obmat, wco);
2449                                                         if(view3d_test_clipping(ps->rv3d, wco)) {
2450                                                                 continue; /* Watch out that no code below this needs to run */
2451                                                         }
2452                                                 }
2453                                                 
2454                                                 /* Is this UV visible from the view? - raytrace */
2455                                                 /* project_paint_PickFace is less complex, use for testing */
2456                                                 //if (project_paint_PickFace(ps, pixelScreenCo, w, &side) == face_index) {
2457                                                 if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucketFaceNodes, face_index, pixelScreenCo)) {
2458                                                         
2459                                                         mask = project_paint_uvpixel_mask(ps, face_index, side, w);
2460                                                         
2461                                                         if (mask > 0.0f) {
2462                                                                 BLI_linklist_prepend_arena(
2463                                                                         bucketPixelNodes,
2464                                                                         project_paint_uvpixel_init(ps, arena, ibuf, x, y, mask, face_index, image_index, pixelScreenCo, side, w),
2465                                                                         arena
2466                                                                 );
2467                                                         }
2468                                                 }
2469                                                 
2470                                         }
2471 //#if 0
2472                                         else if (has_x_isect) {
2473                                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2474                                                 break;
2475                                         }
2476 //#endif
2477                                 }
2478                                 
2479                                 
2480 #if 0                   /* TODO - investigate why this dosnt work sometimes! it should! */
2481                                 /* no intersection for this entire row, after some intersection above means we can quit now */
2482                                 if (has_x_isect==0 && has_isect) { 
2483                                         break;
2484                                 }
2485 #endif
2486                         }
2487                 }
2488         } while(side--);
2489
2490         
2491         
2492 #ifndef PROJ_DEBUG_NOSEAMBLEED
2493         if (ps->seam_bleed_px > 0.0f) {
2494                 int face_seam_flag;
2495                 
2496                 if (ps->thread_tot > 1)
2497                         BLI_lock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2498                 
2499                 face_seam_flag = ps->faceSeamFlags[face_index];
2500                 
2501                 /* are any of our edges un-initialized? */
2502                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_NOSEAM1))==0 || 
2503                         (face_seam_flag & (PROJ_FACE_SEAM2|PROJ_FACE_NOSEAM2))==0 || 
2504                         (face_seam_flag & (PROJ_FACE_SEAM3|PROJ_FACE_NOSEAM3))==0 || 
2505                         (face_seam_flag & (PROJ_FACE_SEAM4|PROJ_FACE_NOSEAM4))==0
2506                 ) {
2507                         project_face_seams_init(ps, face_index, mf->v4);
2508                         face_seam_flag = ps->faceSeamFlags[face_index];
2509                         //printf("seams - %d %d %d %d\n", flag&PROJ_FACE_SEAM1, flag&PROJ_FACE_SEAM2, flag&PROJ_FACE_SEAM3, flag&PROJ_FACE_SEAM4);
2510                 }
2511                 
2512                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_SEAM2|PROJ_FACE_SEAM3|PROJ_FACE_SEAM4))==0) {
2513                         
2514                         if (ps->thread_tot > 1)
2515                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2516                         
2517                 }
2518                 else {
2519                         /* we have a seam - deal with it! */
2520                         
2521                         /* Now create new UV's for the seam face */
2522                         float (*outset_uv)[2] = ps->faceSeamUVs[face_index];
2523                         float insetCos[4][3]; /* inset face coords.  NOTE!!! ScreenSace for ortho, Worldspace in prespective view */
2524
2525                         float fac;
2526                         float *vCoSS[4]; /* vertex screenspace coords */
2527                         
2528                         float bucket_clip_edges[2][2]; /* store the screenspace coords of the face, clipped by the bucket's screen aligned rectangle */
2529                         float edge_verts_inset_clip[2][3];
2530                         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 */
2531                         
2532                         float seam_subsection[4][2];
2533                         float fac1, fac2, ftot;
2534                         
2535                         
2536                         if (outset_uv[0][0]==FLT_MAX) /* first time initialize */
2537                                 uv_image_outset(tf_uv_pxoffset, outset_uv, ps->seam_bleed_px, ibuf->x, ibuf->y, mf->v4);
2538                         
2539                         /* ps->faceSeamUVs cant be modified when threading, now this is done we can unlock */
2540                         if (ps->thread_tot > 1)
2541                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2542                         
2543                         vCoSS[0] = ps->screenCoords[mf->v1];
2544                         vCoSS[1] = ps->screenCoords[mf->v2];
2545                         vCoSS[2] = ps->screenCoords[mf->v3];
2546                         if (mf->v4)
2547                                 vCoSS[3] = ps->screenCoords[ mf->v4 ];
2548                         
2549                         /* PROJ_FACE_SCALE_SEAM must be slightly less then 1.0f */
2550                         if (is_ortho) {
2551                                 if (mf->v4)     scale_quad(insetCos, vCoSS, PROJ_FACE_SCALE_SEAM);
2552                                 else            scale_tri(insetCos, vCoSS, PROJ_FACE_SCALE_SEAM);
2553                         }
2554                         else {
2555                                 if (mf->v4)     scale_quad(insetCos, vCo, PROJ_FACE_SCALE_SEAM);
2556                                 else            scale_tri(insetCos, vCo, PROJ_FACE_SCALE_SEAM);
2557                         }
2558                         
2559                         side = 0; /* for triangles this wont need to change */
2560                         
2561                         for (fidx1 = 0; fidx1 < (mf->v4 ? 4 : 3); fidx1++) {
2562                                 if (mf->v4)             fidx2 = (fidx1==3) ? 0 : fidx1+1; /* next fidx in the face (0,1,2,3) -> (1,2,3,0) */
2563                                 else                    fidx2 = (fidx1==2) ? 0 : fidx1+1; /* next fidx in the face (0,1,2) -> (1,2,0) */
2564                                 
2565                                 if (    (face_seam_flag & (1<<fidx1)) && /* 1<<fidx1 -> PROJ_FACE_SEAM# */
2566                                                 line_clip_rect2f(bucket_bounds, vCoSS[fidx1], vCoSS[fidx2], bucket_clip_edges[0], bucket_clip_edges[1])
2567                                 ) {
2568
2569                                         ftot = Vec2Lenf(vCoSS[fidx1], vCoSS[fidx2]); /* screenspace edge length */
2570                                         
2571                                         if (ftot > 0.0f) { /* avoid div by zero */
2572                                                 if (mf->v4) {
2573                                                         if (fidx1==2 || fidx2==2)       side= 1;
2574                                                         else                                            side= 0;
2575                                                 }
2576                                                 
2577                                                 fac1 = Vec2Lenf(vCoSS[fidx1], bucket_clip_edges[0]) / ftot;
2578                                                 fac2 = Vec2Lenf(vCoSS[fidx1], bucket_clip_edges[1]) / ftot;
2579                                                 
2580                                                 Vec2Lerpf(seam_subsection[0], tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2], fac1);
2581                                                 Vec2Lerpf(seam_subsection[1], tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2], fac2);
2582
2583                                                 Vec2Lerpf(seam_subsection[2], outset_uv[fidx1], outset_uv[fidx2], fac2);
2584                                                 Vec2Lerpf(seam_subsection[3], outset_uv[fidx1], outset_uv[fidx2], fac1);
2585                                                 
2586                                                 /* if the bucket_clip_edges values Z values was kept we could avoid this
2587                                                  * Inset needs to be added so occlusion tests wont hit adjacent faces */
2588                                                 VecLerpf(edge_verts_inset_clip[0], insetCos[fidx1], insetCos[fidx2], fac1);
2589                                                 VecLerpf(edge_verts_inset_clip[1], insetCos[fidx1], insetCos[fidx2], fac2);
2590                                                 
2591
2592                                                 if (pixel_bounds_uv(seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3], &bounds_px, ibuf->x, ibuf->y, 1)) {
2593                                                         /* bounds between the seam rect and the uvspace bucket pixels */
2594                                                         
2595                                                         has_isect = 0;
2596                                                         for (y = bounds_px.ymin; y < bounds_px.ymax; y++) {
2597                                                                 // uv[1] = (((float)y) + 0.5f) / (float)ibuf->y;
2598                                                                 uv[1] = (float)y / ibuf_yf; /* use offset uvs instead */
2599                                                                 
2600                                                                 has_x_isect = 0;
2601                                                                 for (x = bounds_px.xmin; x < bounds_px.xmax; x++) {
2602                                                                         //uv[0] = (((float)x) + 0.5f) / (float)ibuf->x;
2603                                                                         uv[0] = (float)x / ibuf_xf; /* use offset uvs instead */
2604                                                                         
2605                                                                         /* test we're inside uvspace bucket and triangle bounds */
2606                                                                         if (IsectPQ2Df(uv, seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3])) {
2607                                                                                 
2608                                                                                 /* We need to find the closest point along the face edge,
2609                                                                                  * getting the screen_px_from_*** wont work because our actual location
2610                                                                                  * is not relevent, since we are outside the face, Use VecLerpf to find
2611                                                                                  * our location on the side of the face's UV */
2612                                                                                 /*
2613                                                                                 if (is_ortho)   screen_px_from_ortho(ps, uv, v1co, v2co, v3co, uv1co, uv2co, uv3co, pixelScreenCo);
2614                                                                                 else                                    screen_px_from_persp(ps, uv, v1co, v2co, v3co, uv1co, uv2co, uv3co, pixelScreenCo);
2615                                                                                 */
2616                                                                                 
2617                                                                                 /* Since this is a seam we need to work out where on the line this pixel is */
2618                                                                                 //fac = lambda_cp_line2(uv, uv_seam_quad[0], uv_seam_quad[1]);
2619                                                                                 
2620                                                                                 fac = lambda_cp_line2(uv, seam_subsection[0], seam_subsection[1]);
2621                                                                                 if (fac < 0.0f)         { VECCOPY(pixelScreenCo, edge_verts_inset_clip[0]); }
2622                                                                                 else if (fac > 1.0f)    { VECCOPY(pixelScreenCo, edge_verts_inset_clip[1]); }
2623                                                                                 else                            { VecLerpf(pixelScreenCo, edge_verts_inset_clip[0], edge_verts_inset_clip[1], fac); }
2624                                                                                 
2625                                                                                 if (!is_ortho) {
2626                                                                                         pixelScreenCo[3] = 1.0f;
2627                                                                                         Mat4MulVec4fl((float(*)[4])ps->projectMat, pixelScreenCo); /* cast because of const */
2628                                                                                         pixelScreenCo[0] = (float)(ps->ar->winx/2.0f)+(ps->ar->winx/2.0f)*pixelScreenCo[0]/pixelScreenCo[3];    
2629                                                                                         pixelScreenCo[1] = (float)(ps->ar->winy/2.0f)+(ps->ar->winy/2.0f)*pixelScreenCo[1]/pixelScreenCo[3];
2630                                                                                         pixelScreenCo[2] = pixelScreenCo[2]/pixelScreenCo[3]; /* Use the depth for bucket point occlusion */
2631                                                                                 }
2632                                                                                 
2633                                                                                 if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucketFaceNodes, face_index, pixelScreenCo)) {
2634                                                                                         
2635                                                                                         /* Only bother calculating the weights if we intersect */
2636                                                                                         if (ps->do_mask_normal || ps->dm_mtface_clone) {
2637 #if 0
2638                                                                                                 /* This is not QUITE correct since UV is not inside the UV's but good enough for seams */
2639                                                                                                 if (side) {
2640                                                                                                         BarycentricWeights2f(uv, tf_uv_pxoffset[0], tf_uv_pxoffset[2], tf_uv_pxoffset[3], w);
2641                                                                                                 }
2642                                                                                                 else {
2643                                                                                                         BarycentricWeights2f(uv, tf_uv_pxoffset[0], tf_uv_pxoffset[1], tf_uv_pxoffset[2], w);
2644                                                                                                 }
2645 #endif
2646 #if 1
2647                                                                                                 /* Cheat, we know where we are along the edge so work out the weights from that */
2648                                                                                                 fac = fac1 + (fac * (fac2-fac1));
2649                                                                                                 w[0]=w[1]=w[2]= 0.0;
2650                                                                                                 if (side) {
2651                                                                                                         w[fidx1?fidx1-1:0] = fac;
2652                                                                                                         w[fidx2?fidx2-1:0] = 1.0-fac;
2653                                                                                                 }
2654                                                                                                 else {
2655                                                                                                         w[fidx1] = fac;
2656                                                                                                         w[fidx2] = 1.0-fac;
2657                                                                                                 }
2658 #endif
2659                                                                                         }
2660                                                                                         
2661                                                                                         /* a pitty we need to get the worldspace pixel location here */
2662                                                                                         if(ps->rv3d->rflag & RV3D_CLIPPING) {
2663                                                                                                 if (side)       VecLerp3f(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v3].co, ps->dm_mvert[mf->v4].co, w);
2664                                                                                                 else            VecLerp3f(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, w);
2665                                                                                                 
2666                                                                                                 Mat4MulVecfl(ps->ob->obmat, wco);
2667                                                                                                 if(view3d_test_clipping(ps->rv3d, wco)) {
2668                                                                                                         continue; /* Watch out that no code below this needs to run */
2669                                                                                                 }
2670                                                                                         }
2671                                                                                         
2672                                                                                         mask = project_paint_uvpixel_mask(ps, face_index, side, w);
2673                                                                                         
2674                                                                                         if (mask > 0.0f) {
2675                                                                                                 BLI_linklist_prepend_arena(
2676                                                                                                         bucketPixelNodes,
2677                                                                                                         project_paint_uvpixel_init(ps, arena, ibuf, x, y, mask, face_index, image_index, pixelScreenCo, side, w),
2678                                                                                                         arena
2679                                                                                                 );
2680                                                                                         }
2681                                                                                         
2682                                                                                 }
2683                                                                         }
2684                                                                         else if (has_x_isect) {
2685                                                                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2686                                                                                 break;
2687                                                                         }
2688                                                                 }
2689                                                                 
2690 #if 0                                                   /* TODO - investigate why this dosnt work sometimes! it should! */
2691                                                                 /* no intersection for this entire row, after some intersection above means we can quit now */
2692                                                                 if (has_x_isect==0 && has_isect) { 
2693                                                                         break;
2694                                                                 }
2695 #endif
2696                                                         }
2697                                                 }
2698                                         }
2699                                 }
2700                         }
2701                 }
2702         }
2703 #endif // PROJ_DEBUG_NOSEAMBLEED
2704 }
2705
2706
2707 /* takes floating point screenspace min/max and returns int min/max to be used as indicies for ps->bucketRect, ps->bucketFlags */
2708 static void project_paint_bucket_bounds(const ProjPaintState *ps, const float min[2], const float max[2], int bucketMin[2], int bucketMax[2])
2709 {
2710         /* divide by bucketWidth & bucketHeight so the bounds are offset in bucket grid units */
2711         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 */
2712         bucketMin[1] = (int)(((float)(min[1] - ps->screenMin[1]) / ps->screen_height) * ps->buckets_y) + 0.5f;
2713         
2714         bucketMax[0] = (int)(((float)(max[0] - ps->screenMin[0]) / ps->screen_width) * ps->buckets_x) + 1.5f;
2715         bucketMax[1] = (int)(((float)(max[1] - ps->screenMin[1]) / ps->screen_height) * ps->buckets_y) + 1.5f;  
2716         
2717         /* incase the rect is outside the mesh 2d bounds */
2718         CLAMP(bucketMin[0], 0, ps->buckets_x);
2719         CLAMP(bucketMin[1], 0, ps->buckets_y);
2720         
2721         CLAMP(bucketMax[0], 0, ps->buckets_x);
2722         CLAMP(bucketMax[1], 0, ps->buckets_y);
2723 }
2724
2725 /* set bucket_bounds to a screen space-aligned floating point bound-box */
2726 static void project_bucket_bounds(const ProjPaintState *ps, const int bucket_x, const int bucket_y, rctf *bucket_bounds)
2727 {
2728         bucket_bounds->xmin =   ps->screenMin[0]+((bucket_x)*(ps->screen_width / ps->buckets_x));               /* left */
2729         bucket_bounds->xmax =   ps->screenMin[0]+((bucket_x+1)*(ps->screen_width / ps->buckets_x));     /* right */
2730         
2731         bucket_bounds->ymin =   ps->screenMin[1]+((bucket_y)*(ps->screen_height / ps->buckets_y));              /* bottom */
2732         bucket_bounds->ymax =   ps->screenMin[1]+((bucket_y+1)*(ps->screen_height  / ps->buckets_y));   /* top */
2733 }
2734
2735 /* Fill this bucket with pixels from the faces that intersect it.
2736  * 
2737  * have bucket_bounds as an argument so we don;t need to give bucket_x/y the rect function needs */
2738 static void project_bucket_init(const ProjPaintState *ps, const int thread_index, const int bucket_index, rctf *bucket_bounds)
2739 {
2740         LinkNode *node;
2741         int face_index, image_index=0;
2742         ImBuf *ibuf = NULL;
2743         MTFace *tf;
2744         
2745         Image *tpage_last = NULL;
2746         
2747
2748         if (ps->image_tot==1) {
2749                 /* Simple loop, no context switching */
2750                 ibuf = ps->projImages[0].ibuf;
2751                 
2752                 for (node = ps->bucketFaces[bucket_index]; node; node= node->next) { 
2753                         project_paint_face_init(ps, thread_index, bucket_index, GET_INT_FROM_POINTER(node->link), 0, bucket_bounds, ibuf);
2754                 }
2755         }
2756         else {
2757                 
2758                 /* More complicated loop, switch between images */
2759                 for (node = ps->bucketFaces[bucket_index]; node; node= node->next) {
2760                         face_index = GET_INT_FROM_POINTER(node->link);
2761                                 
2762                         /* Image context switching */
2763                         tf = ps->dm_mtface+face_index;
2764                         if (tpage_last != tf->tpage) {
2765                                 tpage_last = tf->tpage;
2766                                 
2767                                 image_index = -1; /* sanity check */
2768                                 
2769                                 for (image_index=0; image_index < ps->image_tot; image_index++) {
2770                                         if (ps->projImages[image_index].ima == tpage_last) {
2771                                                 ibuf = ps->projImages[image_index].ibuf;
2772                                                 break;
2773                                         }
2774                                 }
2775                         }
2776                         /* context switching done */
2777                         
2778                         project_paint_face_init(ps, thread_index, bucket_index, face_index, image_index, bucket_bounds, ibuf);
2779                         
2780                 }
2781         }
2782         
2783         ps->bucketFlags[bucket_index] |= PROJ_BUCKET_INIT;
2784 }
2785
2786
2787 /* We want to know if a bucket and a face overlap in screen-space
2788  * 
2789  * Note, if this ever returns false positives its not that bad, since a face in the bounding area will have its pixels
2790  * calculated when it might not be needed later, (at the moment at least)
2791  * obviously it shouldn't have bugs though */
2792
2793 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)
2794 {
2795         /* TODO - replace this with a tricker method that uses sideofline for all screenCoords's edges against the closest bucket corner */
2796         rctf bucket_bounds;
2797         float p1[2], p2[2], p3[2], p4[2];
2798         float *v, *v1,*v2,*v3,*v4=NULL;
2799         int fidx;
2800         
2801         project_bucket_bounds(ps, bucket_x, bucket_y, &bucket_bounds);
2802         
2803         /* Is one of the faces verts in the bucket bounds? */
2804         
2805         fidx = mf->v4 ? 3:2;
2806         do {
2807                 v = ps->screenCoords[ (*(&mf->v1 + fidx)) ];
2808                 if (BLI_in_rctf(&bucket_bounds, v[0], v[1])) {
2809                         return 1;
2810                 }
2811         } while (fidx--);
2812         
2813         v1 = ps->screenCoords[mf->v1];
2814         v2 = ps->screenCoords[mf->v2];
2815         v3 = ps->screenCoords[mf->v3];
2816         if (mf->v4) {
2817                 v4 = ps->screenCoords[mf->v4];
2818         }
2819         
2820         p1[0] = bucket_bounds.xmin; p1[1] = bucket_bounds.ymin;
2821         p2[0] = bucket_bounds.xmin;     p2[1] = bucket_bounds.ymax;
2822         p3[0] = bucket_bounds.xmax;     p3[1] = bucket_bounds.ymax;
2823         p4[0] = bucket_bounds.xmax;     p4[1] = bucket_bounds.ymin;
2824                 
2825         if (mf->v4) {
2826                 if(     IsectPQ2Df(p1, v1, v2, v3, v4) || IsectPQ2Df(p2, v1, v2, v3, v4) || IsectPQ2Df(p3, v1, v2, v3, v4) || IsectPQ2Df(p4, v1, v2, v3, v4) ||
2827                         /* we can avoid testing v3,v1 because another intersection MUST exist if this intersects */
2828                         (IsectLL2Df(p1, p2, v1, v2) || IsectLL2Df(p1, p2, v2, v3) || IsectLL2Df(p1, p2, v3, v4)) ||
2829                         (IsectLL2Df(p2, p3, v1, v2) || IsectLL2Df(p2, p3, v2, v3) || IsectLL2Df(p2, p3, v3, v4)) ||
2830                         (IsectLL2Df(p3, p4, v1, v2) || IsectLL2Df(p3, p4, v2, v3) || IsectLL2Df(p3, p4, v3, v4)) ||
2831                         (IsectLL2Df(p4, p1, v1, v2) || IsectLL2Df(p4, p1, v2, v3) || IsectLL2Df(p4, p1, v3, v4))
2832                 ) {
2833                         return 1;
2834                 }
2835         }
2836         else {
2837                 if(     IsectPT2Df(p1, v1, v2, v3) || IsectPT2Df(p2, v1, v2, v3) || IsectPT2Df(p3, v1, v2, v3) || IsectPT2Df(p4, v1, v2, v3) ||
2838                         /* we can avoid testing v3,v1 because another intersection MUST exist if this intersects */
2839                         (IsectLL2Df(p1, p2, v1, v2) || IsectLL2Df(p1, p2, v2, v3)) ||
2840                         (IsectLL2Df(p2, p3, v1, v2) || IsectLL2Df(p2, p3, v2, v3)) ||
2841                         (IsectLL2Df(p3, p4, v1, v2) || IsectLL2Df(p3, p4, v2, v3)) ||
2842                         (IsectLL2Df(p4, p1, v1, v2) || IsectLL2Df(p4, p1, v2, v3))
2843                 ) {
2844                         return 1;
2845                 }
2846         }
2847
2848         return 0;
2849 }
2850
2851 /* Add faces to the bucket but dont initialize its pixels
2852  * TODO - when painting occluded, sort the faces on their min-Z and only add faces that faces that are not occluded */
2853 static void project_paint_delayed_face_init(ProjPaintState *ps, const MFace *mf, const MTFace *tf, const int face_index)
2854 {
2855         float min[2], max[2], *vCoSS;
2856         int bucketMin[2], bucketMax[2]; /* for  ps->bucketRect indexing */
2857         int fidx, bucket_x, bucket_y, bucket_index;
2858         int has_x_isect = -1, has_isect = 0; /* for early loop exit */
2859         MemArena *arena = ps->arena_mt[0]; /* just use the first thread arena since threading has not started yet */
2860         
2861         INIT_MINMAX2(min, max);
2862         
2863         fidx = mf->v4 ? 3:2;
2864         do {
2865                 vCoSS = ps->screenCoords[ *(&mf->v1 + fidx) ];