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