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