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