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