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