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