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