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