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