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