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