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