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