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