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