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