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