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