Color management fixes
[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_inv[2] = {1.0f / (float)ibuf_x, 1.0f / (float)ibuf_y};
1005         
1006         /* make UV's in pixel space so we can */
1007         puv[0][0] = orig_uv[0][0] * ibuf_x;
1008         puv[0][1] = orig_uv[0][1] * ibuf_y;
1009         
1010         puv[1][0] = orig_uv[1][0] * ibuf_x;
1011         puv[1][1] = orig_uv[1][1] * ibuf_y;
1012         
1013         puv[2][0] = orig_uv[2][0] * ibuf_x;
1014         puv[2][1] = orig_uv[2][1] * ibuf_y;
1015         
1016         if (is_quad) {
1017                 puv[3][0] = orig_uv[3][0] * ibuf_x;
1018                 puv[3][1] = orig_uv[3][1] * ibuf_y;
1019         }
1020         
1021         /* face edge directions */
1022         sub_v2_v2v2(dir1, puv[1], puv[0]);
1023         sub_v2_v2v2(dir2, puv[2], puv[1]);
1024         normalize_v2(dir1);
1025         normalize_v2(dir2);
1026         
1027         if (is_quad) {
1028                 sub_v2_v2v2(dir3, puv[3], puv[2]);
1029                 sub_v2_v2v2(dir4, puv[0], puv[3]);
1030                 normalize_v2(dir3);
1031                 normalize_v2(dir4);
1032         }
1033         else {
1034                 sub_v2_v2v2(dir3, puv[0], puv[2]);
1035                 normalize_v2(dir3);
1036         }
1037
1038         /* TODO - angle_normalized_v2v2(...) * (M_PI/180.0f)
1039          * This is incorrect. Its already given radians but without it wont work.
1040          * need to look into a fix - campbell */
1041         if (is_quad) {
1042                 a1 = shell_angle_to_dist(angle_normalized_v2v2(dir4, dir1) * (M_PI/180.0f));
1043                 a2 = shell_angle_to_dist(angle_normalized_v2v2(dir1, dir2) * (M_PI/180.0f));
1044                 a3 = shell_angle_to_dist(angle_normalized_v2v2(dir2, dir3) * (M_PI/180.0f));
1045                 a4 = shell_angle_to_dist(angle_normalized_v2v2(dir3, dir4) * (M_PI/180.0f));
1046         }
1047         else {
1048                 a1 = shell_angle_to_dist(angle_normalized_v2v2(dir3, dir1) * (M_PI/180.0f));
1049                 a2 = shell_angle_to_dist(angle_normalized_v2v2(dir1, dir2) * (M_PI/180.0f));
1050                 a3 = shell_angle_to_dist(angle_normalized_v2v2(dir2, dir3) * (M_PI/180.0f));
1051         }
1052         
1053         if (is_quad) {
1054                 sub_v2_v2v2(no1, dir4, dir1);
1055                 sub_v2_v2v2(no2, dir1, dir2);
1056                 sub_v2_v2v2(no3, dir2, dir3);
1057                 sub_v2_v2v2(no4, dir3, dir4);
1058                 normalize_v2(no1);
1059                 normalize_v2(no2);
1060                 normalize_v2(no3);
1061                 normalize_v2(no4);
1062                 mul_v2_fl(no1, a1*scaler);
1063                 mul_v2_fl(no2, a2*scaler);
1064                 mul_v2_fl(no3, a3*scaler);
1065                 mul_v2_fl(no4, a4*scaler);
1066                 add_v2_v2v2(outset_uv[0], puv[0], no1);
1067                 add_v2_v2v2(outset_uv[1], puv[1], no2);
1068                 add_v2_v2v2(outset_uv[2], puv[2], no3);
1069                 add_v2_v2v2(outset_uv[3], puv[3], no4);
1070                 mul_v2_v2(outset_uv[0], ibuf_inv);
1071                 mul_v2_v2(outset_uv[1], ibuf_inv);
1072                 mul_v2_v2(outset_uv[2], ibuf_inv);
1073                 mul_v2_v2(outset_uv[3], ibuf_inv);
1074         }
1075         else {
1076                 sub_v2_v2v2(no1, dir3, dir1);
1077                 sub_v2_v2v2(no2, dir1, dir2);
1078                 sub_v2_v2v2(no3, dir2, dir3);
1079                 normalize_v2(no1);
1080                 normalize_v2(no2);
1081                 normalize_v2(no3);
1082                 mul_v2_fl(no1, a1*scaler);
1083                 mul_v2_fl(no2, a2*scaler);
1084                 mul_v2_fl(no3, a3*scaler);
1085                 add_v2_v2v2(outset_uv[0], puv[0], no1);
1086                 add_v2_v2v2(outset_uv[1], puv[1], no2);
1087                 add_v2_v2v2(outset_uv[2], puv[2], no3);
1088
1089                 mul_v2_v2(outset_uv[0], ibuf_inv);
1090                 mul_v2_v2(outset_uv[1], ibuf_inv);
1091                 mul_v2_v2(outset_uv[2], ibuf_inv);
1092         }
1093 }
1094
1095 /* 
1096  * Be tricky with flags, first 4 bits are PROJ_FACE_SEAM1 to 4, last 4 bits are PROJ_FACE_NOSEAM1 to 4
1097  * 1<<i - where i is (0-3) 
1098  * 
1099  * If we're multithreadng, make sure threads are locked when this is called
1100  */
1101 static void project_face_seams_init(const ProjPaintState *ps, const int face_index, const int is_quad)
1102 {
1103         int other_face, other_fidx; /* vars for the other face, we also set its flag */
1104         int fidx1 = is_quad ? 3 : 2;
1105         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 */
1106         
1107         do {
1108                 if ((ps->faceSeamFlags[face_index] & (1<<fidx1|16<<fidx1)) == 0) {
1109                         if (check_seam(ps, face_index, fidx1, fidx2, &other_face, &other_fidx)) {
1110                                 ps->faceSeamFlags[face_index] |= 1<<fidx1;
1111                                 if (other_face != -1)
1112                                         ps->faceSeamFlags[other_face] |= 1<<other_fidx;
1113                         }
1114                         else {
1115                                 ps->faceSeamFlags[face_index] |= 16<<fidx1;
1116                                 if (other_face != -1)
1117                                         ps->faceSeamFlags[other_face] |= 16<<other_fidx; /* second 4 bits for disabled */
1118                         }
1119                 }
1120                 
1121                 fidx2 = fidx1;
1122         } while (fidx1--);
1123 }
1124 #endif // PROJ_DEBUG_NOSEAMBLEED
1125
1126
1127 /* TODO - move to arithb.c */
1128
1129 /* little sister we only need to know lambda */
1130 static float lambda_cp_line2(const float p[2], const float l1[2], const float l2[2])
1131 {
1132         float h[2], u[2];
1133         
1134         u[0] = l2[0] - l1[0];
1135         u[1] = l2[1] - l1[1];
1136
1137         h[0] = p[0] - l1[0];
1138         h[1] = p[1] - l1[1];
1139         
1140         return(dot_v2v2(u, h)/dot_v2v2(u, u));
1141 }
1142
1143
1144 /* Converts a UV location to a 3D screenspace location
1145  * Takes a 'uv' and 3 UV coords, and sets the values of pixelScreenCo
1146  * 
1147  * This is used for finding a pixels location in screenspace for painting */
1148 static void screen_px_from_ortho(
1149                 float uv[2],
1150                 float v1co[3], float v2co[3], float v3co[3], /* Screenspace coords */
1151                 float uv1co[2], float uv2co[2], float uv3co[2],
1152                 float pixelScreenCo[4],
1153                 float w[3])
1154 {
1155         barycentric_weights_v2(uv1co, uv2co, uv3co, uv, w);
1156         interp_v3_v3v3v3(pixelScreenCo, v1co, v2co, v3co, w);
1157 }
1158
1159 /* same as screen_px_from_ortho except we need to take into account
1160  * the perspective W coord for each vert */
1161 static void screen_px_from_persp(
1162                 float uv[2],
1163                 float v1co[3], float v2co[3], float v3co[3], /* screenspace coords */
1164                 float uv1co[2], float uv2co[2], float uv3co[2],
1165                 float pixelScreenCo[4],
1166                 float w[3])
1167 {
1168
1169         float wtot_inv, wtot;
1170         barycentric_weights_v2(uv1co, uv2co, uv3co, uv, w);
1171         
1172         /* re-weight from the 4th coord of each screen vert */
1173         w[0] *= v1co[3];
1174         w[1] *= v2co[3];
1175         w[2] *= v3co[3];
1176         
1177         wtot = w[0]+w[1]+w[2];
1178         
1179         if (wtot > 0.0f) {
1180                 wtot_inv = 1.0f / wtot;
1181                 w[0] *= wtot_inv;
1182                 w[1] *= wtot_inv;
1183                 w[2] *= wtot_inv;
1184         }
1185         else {
1186                 w[0] = w[1] = w[2] = 1.0/3.0; /* dummy values for zero area face */
1187         }
1188         /* done re-weighting */
1189         
1190         interp_v3_v3v3v3(pixelScreenCo, v1co, v2co, v3co, w);
1191 }
1192
1193 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])
1194 {
1195         float *uvCo1, *uvCo2, *uvCo3;
1196         float uv_other[2], x, y;
1197         
1198         uvCo1 =  (float *)tf_other->uv[0];
1199         if (side==1) {
1200                 uvCo2 =  (float *)tf_other->uv[2];
1201                 uvCo3 =  (float *)tf_other->uv[3];
1202         }
1203         else {
1204                 uvCo2 =  (float *)tf_other->uv[1];
1205                 uvCo3 =  (float *)tf_other->uv[2];
1206         }
1207         
1208         interp_v2_v2v2v2(uv_other, uvCo1, uvCo2, uvCo3, (float*)w);
1209         
1210         /* use */
1211         uvco_to_wrapped_pxco(uv_other, ibuf_other->x, ibuf_other->y, &x, &y);
1212         
1213         
1214         if (ibuf_other->rect_float) { /* from float to float */
1215                 bilinear_interpolation_color_wrap(ibuf_other, NULL, rgba_f, x, y);
1216         }
1217         else { /* from char to float */
1218                 bilinear_interpolation_color_wrap(ibuf_other, rgba_ub, NULL, x, y);
1219         }
1220                 
1221 }
1222
1223 /* run this outside project_paint_uvpixel_init since pixels with mask 0 dont need init */
1224 float project_paint_uvpixel_mask(
1225                 const ProjPaintState *ps,
1226                 const int face_index,
1227                 const int side,
1228                 const float w[3])
1229 {
1230         float mask;
1231         
1232         /* Image Mask */
1233         if (ps->do_layer_stencil) {
1234                 /* another UV layers image is masking this one's */
1235                 ImBuf *ibuf_other;
1236                 const MTFace *tf_other = ps->dm_mtface_stencil + face_index;
1237                 
1238                 if (tf_other->tpage && (ibuf_other = BKE_image_get_ibuf(tf_other->tpage, NULL))) {
1239                         /* BKE_image_get_ibuf - TODO - this may be slow */
1240                         unsigned char rgba_ub[4];
1241                         float rgba_f[4];
1242                         
1243                         project_face_pixel(tf_other, ibuf_other, w, side, rgba_ub, rgba_f);
1244                         
1245                         if (ibuf_other->rect_float) { /* from float to float */
1246                                 mask = ((rgba_f[0]+rgba_f[1]+rgba_f[2])/3.0f) * rgba_f[3];
1247                         }
1248                         else { /* from char to float */
1249                                 mask = ((rgba_ub[0]+rgba_ub[1]+rgba_ub[2])/(256*3.0f)) * (rgba_ub[3]/256.0f);
1250                         }
1251                         
1252                         if (!ps->do_layer_stencil_inv) /* matching the gimps layer mask black/white rules, white==full opacity */
1253                                 mask = (1.0f - mask);
1254
1255                         if (mask == 0.0f) {
1256                                 return 0.0f;
1257                         }
1258                 }
1259                 else {
1260                         return 0.0f;
1261                 }
1262         } else {
1263                 mask = 1.0f;
1264         }
1265         
1266         /* calculate mask */
1267         if (ps->do_mask_normal) {
1268                 MFace *mf = ps->dm_mface + face_index;
1269                 short *no1, *no2, *no3;
1270                 float no[3], angle;
1271                 no1 = ps->dm_mvert[mf->v1].no;
1272                 if (side==1) {
1273                         no2 = ps->dm_mvert[mf->v3].no;
1274                         no3 = ps->dm_mvert[mf->v4].no;
1275                 }
1276                 else {
1277                         no2 = ps->dm_mvert[mf->v2].no;
1278                         no3 = ps->dm_mvert[mf->v3].no;
1279                 }
1280                 
1281                 no[0] = w[0]*no1[0] + w[1]*no2[0] + w[2]*no3[0];
1282                 no[1] = w[0]*no1[1] + w[1]*no2[1] + w[2]*no3[1];
1283                 no[2] = w[0]*no1[2] + w[1]*no2[2] + w[2]*no3[2];
1284                 normalize_v3(no);
1285                 
1286                 /* now we can use the normal as a mask */
1287                 if (ps->is_ortho) {
1288                         angle = angle_normalized_v3v3((float *)ps->viewDir, no);
1289                 }
1290                 else {
1291                         /* Annoying but for the perspective view we need to get the pixels location in 3D space :/ */
1292                         float viewDirPersp[3];
1293                         float *co1, *co2, *co3;
1294                         co1 = ps->dm_mvert[mf->v1].co;
1295                         if (side==1) {
1296                                 co2 = ps->dm_mvert[mf->v3].co;
1297                                 co3 = ps->dm_mvert[mf->v4].co;
1298                         }
1299                         else {
1300                                 co2 = ps->dm_mvert[mf->v2].co;
1301                                 co3 = ps->dm_mvert[mf->v3].co;
1302                         }
1303
1304                         /* Get the direction from the viewPoint to the pixel and normalize */
1305                         viewDirPersp[0] = (ps->viewPos[0] - (w[0]*co1[0] + w[1]*co2[0] + w[2]*co3[0]));
1306                         viewDirPersp[1] = (ps->viewPos[1] - (w[0]*co1[1] + w[1]*co2[1] + w[2]*co3[1]));
1307                         viewDirPersp[2] = (ps->viewPos[2] - (w[0]*co1[2] + w[1]*co2[2] + w[2]*co3[2]));
1308                         normalize_v3(viewDirPersp);
1309                         
1310                         angle = angle_normalized_v3v3(viewDirPersp, no);
1311                 }
1312                 
1313                 if (angle >= ps->normal_angle) {
1314                         return 0.0f; /* outsize the normal limit*/
1315                 }
1316                 else if (angle > ps->normal_angle_inner) {
1317                         mask *= (ps->normal_angle - angle) / ps->normal_angle_range;
1318                 } /* otherwise no mask normal is needed, were within the limit */
1319         }
1320         
1321         // This only works when the opacity dosnt change while painting, stylus pressure messes with this
1322         // so dont use it.
1323         // if (ps->is_airbrush==0) mask *= ps->brush->alpha;
1324         
1325         return mask;
1326 }
1327
1328 /* run this function when we know a bucket's, face's pixel can be initialized,
1329  * return the ProjPixel which is added to 'ps->bucketRect[bucket_index]' */
1330 static ProjPixel *project_paint_uvpixel_init(
1331                 const ProjPaintState *ps,
1332                 MemArena *arena,
1333                 const ImBuf *ibuf,
1334                 short x_px, short y_px,
1335                 const float mask,
1336                 const int face_index,
1337                 const int image_index,
1338                 const float pixelScreenCo[4],
1339                 const int side,
1340                 const float w[3])
1341 {
1342         ProjPixel *projPixel;
1343         short size;
1344         
1345         /* wrap pixel location */
1346         x_px = x_px % ibuf->x;
1347         if (x_px<0) x_px += ibuf->x;
1348         y_px = y_px % ibuf->y;
1349         if (y_px<0) y_px += ibuf->y;
1350         
1351         if (ps->tool==PAINT_TOOL_CLONE) {
1352                 size = sizeof(ProjPixelClone);
1353         }
1354         else if (ps->tool==PAINT_TOOL_SMEAR) {
1355                 size = sizeof(ProjPixelClone);
1356         }
1357         else {
1358                 size = sizeof(ProjPixel);
1359         }
1360         
1361         projPixel = (ProjPixel *)BLI_memarena_alloc(arena, size);
1362         //memset(projPixel, 0, size);
1363         
1364         if (ibuf->rect_float) {
1365                 projPixel->pixel.f_pt = (float *)ibuf->rect_float + ((x_px + y_px * ibuf->x) * 4);
1366                 projPixel->origColor.f[0] = projPixel->newColor.f[0] = projPixel->pixel.f_pt[0];  
1367                 projPixel->origColor.f[1] = projPixel->newColor.f[1] = projPixel->pixel.f_pt[1];  
1368                 projPixel->origColor.f[2] = projPixel->newColor.f[2] = projPixel->pixel.f_pt[2];  
1369                 projPixel->origColor.f[3] = projPixel->newColor.f[3] = projPixel->pixel.f_pt[3];  
1370         }
1371         else {
1372                 projPixel->pixel.ch_pt = ((unsigned char *)ibuf->rect + ((x_px + y_px * ibuf->x) * 4));
1373                 projPixel->origColor.uint = projPixel->newColor.uint = *projPixel->pixel.uint_pt;
1374         }
1375         
1376         /* screenspace unclamped, we could keep its z and w values but dont need them at the moment */
1377         VECCOPY2D(projPixel->projCoSS, pixelScreenCo);
1378         
1379         projPixel->x_px = x_px;
1380         projPixel->y_px = y_px;
1381         
1382         projPixel->mask = (unsigned short)(mask * 65535);
1383         projPixel->mask_max = 0;
1384         
1385         /* which bounding box cell are we in?, needed for undo */
1386         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 ;
1387         
1388         /* done with view3d_project_float inline */
1389         if (ps->tool==PAINT_TOOL_CLONE) {
1390                 if (ps->dm_mtface_clone) {
1391                         ImBuf *ibuf_other;
1392                         const MTFace *tf_other = ps->dm_mtface_clone + face_index;
1393                         
1394                         if (tf_other->tpage && (ibuf_other = BKE_image_get_ibuf(tf_other->tpage, NULL))) {
1395                                 /* BKE_image_get_ibuf - TODO - this may be slow */
1396                                 
1397                                 if (ibuf->rect_float) {
1398                                         if (ibuf_other->rect_float) { /* from float to float */
1399                                                 project_face_pixel(tf_other, ibuf_other, w, side, NULL, ((ProjPixelClone *)projPixel)->clonepx.f);
1400                                         }
1401                                         else { /* from char to float */
1402                                                 unsigned char rgba_ub[4];
1403                                                 project_face_pixel(tf_other, ibuf_other, w, side, rgba_ub, NULL);
1404                                                 IMAPAINT_CHAR_RGBA_TO_FLOAT(((ProjPixelClone *)projPixel)->clonepx.f, rgba_ub);
1405                                         }
1406                                 }
1407                                 else {
1408                                         if (ibuf_other->rect_float) { /* float to char */
1409                                                 float rgba[4];
1410                                                 project_face_pixel(tf_other, ibuf_other, w, side, NULL, rgba);
1411                                                 IMAPAINT_FLOAT_RGBA_TO_CHAR(((ProjPixelClone *)projPixel)->clonepx.ch, rgba)
1412                                         }
1413                                         else { /* char to char */
1414                                                 project_face_pixel(tf_other, ibuf_other, w, side, ((ProjPixelClone *)projPixel)->clonepx.ch, NULL);
1415                                         }
1416                                 }
1417                         }
1418                         else {
1419                                 if (ibuf->rect_float) {
1420                                         ((ProjPixelClone *)projPixel)->clonepx.f[3] = 0;
1421                                 }
1422                                 else {
1423                                         ((ProjPixelClone *)projPixel)->clonepx.ch[3] = 0;
1424                                 }
1425                         }
1426                         
1427                 }
1428                 else {
1429                         float co[2];
1430                         sub_v2_v2v2(co, projPixel->projCoSS, (float *)ps->cloneOffset);
1431                         
1432                         /* no need to initialize the bucket, we're only checking buckets faces and for this
1433                          * the faces are alredy initialized in project_paint_delayed_face_init(...) */
1434                         if (ibuf->rect_float) {
1435                                 if (!project_paint_PickColor(ps, co, ((ProjPixelClone *)projPixel)->clonepx.f, NULL, 1)) {
1436                                         ((ProjPixelClone *)projPixel)->clonepx.f[3] = 0; /* zero alpha - ignore */
1437                                 }
1438                         }
1439                         else {
1440                                 if (!project_paint_PickColor(ps, co, NULL, ((ProjPixelClone *)projPixel)->clonepx.ch, 1)) {
1441                                         ((ProjPixelClone *)projPixel)->clonepx.ch[3] = 0; /* zero alpha - ignore */
1442                                 }
1443                         }
1444                 }
1445         }
1446         
1447 #ifdef PROJ_DEBUG_PAINT
1448         if (ibuf->rect_float)   projPixel->pixel.f_pt[0] = 0;
1449         else                                    projPixel->pixel.ch_pt[0] = 0;
1450 #endif
1451         projPixel->image_index = image_index;
1452         
1453         return projPixel;
1454 }
1455
1456 static int line_clip_rect2f(
1457                 rctf *rect,
1458                 const float l1[2], const float l2[2],
1459                 float l1_clip[2], float l2_clip[2])
1460 {
1461         /* first account for horizontal, then vertical lines */
1462         /* horiz */
1463         if (fabsf(l1[1]-l2[1]) < PROJ_GEOM_TOLERANCE) {
1464                 /* is the line out of range on its Y axis? */
1465                 if (l1[1] < rect->ymin || l1[1] > rect->ymax) {
1466                         return 0;
1467                 }
1468                 /* line is out of range on its X axis */
1469                 if ((l1[0] < rect->xmin && l2[0] < rect->xmin) || (l1[0] > rect->xmax && l2[0] > rect->xmax)) {
1470                         return 0;
1471                 }
1472                 
1473                 
1474                 if (fabsf(l1[0]-l2[0]) < PROJ_GEOM_TOLERANCE) { /* this is a single point  (or close to)*/
1475                         if (BLI_in_rctf(rect, l1[0], l1[1])) {
1476                                 VECCOPY2D(l1_clip, l1);
1477                                 VECCOPY2D(l2_clip, l2);
1478                                 return 1;
1479                         }
1480                         else {
1481                                 return 0;
1482                         }
1483                 }
1484                 
1485                 VECCOPY2D(l1_clip, l1);
1486                 VECCOPY2D(l2_clip, l2);
1487                 CLAMP(l1_clip[0], rect->xmin, rect->xmax);
1488                 CLAMP(l2_clip[0], rect->xmin, rect->xmax);
1489                 return 1;
1490         }
1491         else if (fabsf(l1[0]-l2[0]) < PROJ_GEOM_TOLERANCE) {
1492                 /* is the line out of range on its X axis? */
1493                 if (l1[0] < rect->xmin || l1[0] > rect->xmax) {
1494                         return 0;
1495                 }
1496                 
1497                 /* line is out of range on its Y axis */
1498                 if ((l1[1] < rect->ymin && l2[1] < rect->ymin) || (l1[1] > rect->ymax && l2[1] > rect->ymax)) {
1499                         return 0;
1500                 }
1501                 
1502                 if (fabsf(l1[1]-l2[1]) < PROJ_GEOM_TOLERANCE) { /* this is a single point  (or close to)*/
1503                         if (BLI_in_rctf(rect, l1[0], l1[1])) {
1504                                 VECCOPY2D(l1_clip, l1);
1505                                 VECCOPY2D(l2_clip, l2);
1506                                 return 1;
1507                         }
1508                         else {
1509                                 return 0;
1510                         }
1511                 }
1512                 
1513                 VECCOPY2D(l1_clip, l1);
1514                 VECCOPY2D(l2_clip, l2);
1515                 CLAMP(l1_clip[1], rect->ymin, rect->ymax);
1516                 CLAMP(l2_clip[1], rect->ymin, rect->ymax);
1517                 return 1;
1518         }
1519         else {
1520                 float isect;
1521                 short ok1 = 0;
1522                 short ok2 = 0;
1523                 
1524                 /* Done with vertical lines */
1525                 
1526                 /* are either of the points inside the rectangle ? */
1527                 if (BLI_in_rctf(rect, l1[0], l1[1])) {
1528                         VECCOPY2D(l1_clip, l1);
1529                         ok1 = 1;
1530                 }
1531                 
1532                 if (BLI_in_rctf(rect, l2[0], l2[1])) {
1533                         VECCOPY2D(l2_clip, l2);
1534                         ok2 = 1;
1535                 }
1536                 
1537                 /* line inside rect */
1538                 if (ok1 && ok2) return 1;
1539                 
1540                 /* top/bottom */
1541                 if (line_isect_y(l1, l2, rect->ymin, &isect) && (isect >= rect->xmin) && (isect <= rect->xmax)) {
1542                         if (l1[1] < l2[1]) { /* line 1 is outside */
1543                                 l1_clip[0] = isect;
1544                                 l1_clip[1] = rect->ymin;
1545                                 ok1 = 1;
1546                         }
1547                         else {
1548                                 l2_clip[0] = isect;
1549                                 l2_clip[1] = rect->ymin;
1550                                 ok2 = 2;
1551                         }
1552                 }
1553                 
1554                 if (ok1 && ok2) return 1;
1555                 
1556                 if (line_isect_y(l1, l2, rect->ymax, &isect) && (isect >= rect->xmin) && (isect <= rect->xmax)) {
1557                         if (l1[1] > l2[1]) { /* line 1 is outside */
1558                                 l1_clip[0] = isect;
1559                                 l1_clip[1] = rect->ymax;
1560                                 ok1 = 1;
1561                         }
1562                         else {
1563                                 l2_clip[0] = isect;
1564                                 l2_clip[1] = rect->ymax;
1565                                 ok2 = 2;
1566                         }
1567                 }
1568                 
1569                 if (ok1 && ok2) return 1;
1570                 
1571                 /* left/right */
1572                 if (line_isect_x(l1, l2, rect->xmin, &isect) && (isect >= rect->ymin) && (isect <= rect->ymax)) {
1573                         if (l1[0] < l2[0]) { /* line 1 is outside */
1574                                 l1_clip[0] = rect->xmin;
1575                                 l1_clip[1] = isect;
1576                                 ok1 = 1;
1577                         }
1578                         else {
1579                                 l2_clip[0] = rect->xmin;
1580                                 l2_clip[1] = isect;
1581                                 ok2 = 2;
1582                         }
1583                 }
1584         
1585                 if (ok1 && ok2) return 1;
1586                 
1587                 if (line_isect_x(l1, l2, rect->xmax, &isect) && (isect >= rect->ymin) && (isect <= rect->ymax)) {
1588                         if (l1[0] > l2[0]) { /* line 1 is outside */
1589                                 l1_clip[0] = rect->xmax;
1590                                 l1_clip[1] = isect;
1591                                 ok1 = 1;
1592                         }
1593                         else {
1594                                 l2_clip[0] = rect->xmax;
1595                                 l2_clip[1] = isect;
1596                                 ok2 = 2;
1597                         }
1598                 }
1599                 
1600                 if (ok1 && ok2) {
1601                         return 1;
1602                 }
1603                 else {
1604                         return 0;
1605                 }
1606         }
1607 }
1608
1609
1610
1611 /* scale the quad & tri about its center
1612  * scaling by PROJ_FACE_SCALE_SEAM (0.99x) is used for getting fake UV pixel coords that are on the
1613  * edge of the face but slightly inside it occlusion tests dont return hits on adjacent faces */
1614 static void scale_quad(float insetCos[4][3], float *origCos[4], const float inset)
1615 {
1616         float cent[3];
1617         cent[0] = (origCos[0][0] + origCos[1][0] + origCos[2][0] + origCos[3][0]) / 4.0f;
1618         cent[1] = (origCos[0][1] + origCos[1][1] + origCos[2][1] + origCos[3][1]) / 4.0f;
1619         cent[2] = (origCos[0][2] + origCos[1][2] + origCos[2][2] + origCos[3][2]) / 4.0f;
1620         
1621         sub_v3_v3v3(insetCos[0], origCos[0], cent);
1622         sub_v3_v3v3(insetCos[1], origCos[1], cent);
1623         sub_v3_v3v3(insetCos[2], origCos[2], cent);
1624         sub_v3_v3v3(insetCos[3], origCos[3], cent);
1625         
1626         mul_v3_fl(insetCos[0], inset);
1627         mul_v3_fl(insetCos[1], inset);
1628         mul_v3_fl(insetCos[2], inset);
1629         mul_v3_fl(insetCos[3], inset);
1630         
1631         add_v3_v3v3(insetCos[0], insetCos[0], cent);
1632         add_v3_v3v3(insetCos[1], insetCos[1], cent);
1633         add_v3_v3v3(insetCos[2], insetCos[2], cent);
1634         add_v3_v3v3(insetCos[3], insetCos[3], cent);
1635 }
1636
1637
1638 static void scale_tri(float insetCos[4][3], float *origCos[4], const float inset)
1639 {
1640         float cent[3];
1641         cent[0] = (origCos[0][0] + origCos[1][0] + origCos[2][0]) / 3.0f;
1642         cent[1] = (origCos[0][1] + origCos[1][1] + origCos[2][1]) / 3.0f;
1643         cent[2] = (origCos[0][2] + origCos[1][2] + origCos[2][2]) / 3.0f;
1644         
1645         sub_v3_v3v3(insetCos[0], origCos[0], cent);
1646         sub_v3_v3v3(insetCos[1], origCos[1], cent);
1647         sub_v3_v3v3(insetCos[2], origCos[2], cent);
1648         
1649         mul_v3_fl(insetCos[0], inset);
1650         mul_v3_fl(insetCos[1], inset);
1651         mul_v3_fl(insetCos[2], inset);
1652         
1653         add_v3_v3v3(insetCos[0], insetCos[0], cent);
1654         add_v3_v3v3(insetCos[1], insetCos[1], cent);
1655         add_v3_v3v3(insetCos[2], insetCos[2], cent);
1656 }
1657
1658
1659 static float Vec2Lenf_nosqrt(const float *v1, const float *v2)
1660 {
1661         float x, y;
1662
1663         x = v1[0]-v2[0];
1664         y = v1[1]-v2[1];
1665         return x*x+y*y;
1666 }
1667
1668 static float Vec2Lenf_nosqrt_other(const float *v1, const float v2_1, const float v2_2)
1669 {
1670         float x, y;
1671
1672         x = v1[0]-v2_1;
1673         y = v1[1]-v2_2;
1674         return x*x+y*y;
1675 }
1676
1677 /* note, use a squared value so we can use Vec2Lenf_nosqrt
1678  * be sure that you have done a bounds check first or this may fail */
1679 /* only give bucket_bounds as an arg because we need it elsewhere */
1680 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)
1681 {
1682          
1683         /* Would normally to a simple intersection test, however we know the bounds of these 2 alredy intersect 
1684          * so we only need to test if the center is inside the vertical or horizontal bounds on either axis,
1685          * this is even less work then an intersection test
1686          * 
1687         if (BLI_in_rctf(bucket_bounds, cent[0], cent[1]))
1688                 return 1;
1689          */
1690         
1691         if((bucket_bounds->xmin <= cent[0] && bucket_bounds->xmax >= cent[0]) || (bucket_bounds->ymin <= cent[1] && bucket_bounds->ymax >= cent[1]) ) {
1692            return 1;
1693         }
1694         
1695         /* out of bounds left */
1696         if (cent[0] < bucket_bounds->xmin) {
1697                 /* lower left out of radius test */
1698                 if (cent[1] < bucket_bounds->ymin) {
1699                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmin, bucket_bounds->ymin) < radius_squared) ? 1 : 0;
1700                 } 
1701                 /* top left test */
1702                 else if (cent[1] > bucket_bounds->ymax) {
1703                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmin, bucket_bounds->ymax) < radius_squared) ? 1 : 0;
1704                 }
1705         }
1706         else if (cent[0] > bucket_bounds->xmax) {
1707                 /* lower right out of radius test */
1708                 if (cent[1] < bucket_bounds->ymin) {
1709                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmax, bucket_bounds->ymin) < radius_squared) ? 1 : 0;
1710                 } 
1711                 /* top right test */
1712                 else if (cent[1] > bucket_bounds->ymax) {
1713                         return (Vec2Lenf_nosqrt_other(cent, bucket_bounds->xmax, bucket_bounds->ymax) < radius_squared) ? 1 : 0;
1714                 }
1715         }
1716         
1717         return 0;
1718 }
1719
1720
1721
1722 /* Note for rect_to_uvspace_ortho() and rect_to_uvspace_persp()
1723  * in ortho view this function gives good results when bucket_bounds are outside the triangle
1724  * however in some cases, perspective view will mess up with faces that have minimal screenspace area (viewed from the side)
1725  * 
1726  * 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.
1727  * however switching back to this for ortho is always an option */
1728
1729 static void rect_to_uvspace_ortho(
1730                 rctf *bucket_bounds,
1731                 float *v1coSS, float *v2coSS, float *v3coSS,
1732                 float *uv1co, float *uv2co, float *uv3co,
1733                 float bucket_bounds_uv[4][2],
1734                 const int flip)
1735 {
1736         float uv[2];
1737         float w[3];
1738         
1739         /* get the UV space bounding box */
1740         uv[0] = bucket_bounds->xmax;
1741         uv[1] = bucket_bounds->ymin;
1742         barycentric_weights_v2(v1coSS, v2coSS, v3coSS, uv, w);
1743         interp_v2_v2v2v2(bucket_bounds_uv[flip?3:0], uv1co, uv2co, uv3co, w);
1744
1745         //uv[0] = bucket_bounds->xmax; // set above
1746         uv[1] = bucket_bounds->ymax;
1747         barycentric_weights_v2(v1coSS, v2coSS, v3coSS, uv, w);
1748         interp_v2_v2v2v2(bucket_bounds_uv[flip?2:1], uv1co, uv2co, uv3co, w);
1749
1750         uv[0] = bucket_bounds->xmin;
1751         //uv[1] = bucket_bounds->ymax; // set above
1752         barycentric_weights_v2(v1coSS, v2coSS, v3coSS, uv, w);
1753         interp_v2_v2v2v2(bucket_bounds_uv[flip?1:2], uv1co, uv2co, uv3co, w);
1754
1755         //uv[0] = bucket_bounds->xmin; // set above
1756         uv[1] = bucket_bounds->ymin;
1757         barycentric_weights_v2(v1coSS, v2coSS, v3coSS, uv, w);
1758         interp_v2_v2v2v2(bucket_bounds_uv[flip?0:3], uv1co, uv2co, uv3co, w);
1759 }
1760
1761 /* same as above but use barycentric_weights_v2_persp */
1762 static void rect_to_uvspace_persp(
1763                 rctf *bucket_bounds,
1764                 float *v1coSS, float *v2coSS, float *v3coSS,
1765                 float *uv1co, float *uv2co, float *uv3co,
1766                 float bucket_bounds_uv[4][2],
1767                 const int flip
1768         )
1769 {
1770         float uv[2];
1771         float w[3];
1772         
1773         /* get the UV space bounding box */
1774         uv[0] = bucket_bounds->xmax;
1775         uv[1] = bucket_bounds->ymin;
1776         barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, uv, w);
1777         interp_v2_v2v2v2(bucket_bounds_uv[flip?3:0], uv1co, uv2co, uv3co, w);
1778
1779         //uv[0] = bucket_bounds->xmax; // set above
1780         uv[1] = bucket_bounds->ymax;
1781         barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, uv, w);
1782         interp_v2_v2v2v2(bucket_bounds_uv[flip?2:1], uv1co, uv2co, uv3co, w);
1783
1784         uv[0] = bucket_bounds->xmin;
1785         //uv[1] = bucket_bounds->ymax; // set above
1786         barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, uv, w);
1787         interp_v2_v2v2v2(bucket_bounds_uv[flip?1:2], uv1co, uv2co, uv3co, w);
1788
1789         //uv[0] = bucket_bounds->xmin; // set above
1790         uv[1] = bucket_bounds->ymin;
1791         barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, uv, w);
1792         interp_v2_v2v2v2(bucket_bounds_uv[flip?0:3], uv1co, uv2co, uv3co, w);
1793 }
1794
1795 /* This works as we need it to but we can save a few steps and not use it */
1796
1797 #if 0
1798 static float angle_2d_clockwise(const float p1[2], const float p2[2], const float p3[2])
1799 {
1800         float v1[2], v2[2];
1801         
1802         v1[0] = p1[0]-p2[0];    v1[1] = p1[1]-p2[1];
1803         v2[0] = p3[0]-p2[0];    v2[1] = p3[1]-p2[1];
1804         
1805         return -atan2(v1[0]*v2[1] - v1[1]*v2[0], v1[0]*v2[0]+v1[1]*v2[1]);
1806 }
1807 #endif
1808
1809 #define ISECT_1 (1)
1810 #define ISECT_2 (1<<1)
1811 #define ISECT_3 (1<<2)
1812 #define ISECT_4 (1<<3)
1813 #define ISECT_ALL3 ((1<<3)-1)
1814 #define ISECT_ALL4 ((1<<4)-1)
1815
1816 /* limit must be a fraction over 1.0f */
1817 static int IsectPT2Df_limit(float pt[2], float v1[2], float v2[2], float v3[2], float limit)
1818 {
1819         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;
1820 }
1821
1822 /* Clip the face by a bucket and set the uv-space bucket_bounds_uv
1823  * so we have the clipped UV's to do pixel intersection tests with 
1824  * */
1825 static int float_z_sort_flip(const void *p1, const void *p2) {
1826         return (((float *)p1)[2] < ((float *)p2)[2] ? 1:-1);
1827 }
1828
1829 static int float_z_sort(const void *p1, const void *p2) {
1830         return (((float *)p1)[2] < ((float *)p2)[2] ?-1:1);
1831 }
1832
1833 static void project_bucket_clip_face(
1834                 const int is_ortho,
1835                 rctf *bucket_bounds,
1836                 float *v1coSS, float *v2coSS, float *v3coSS,
1837                 float *uv1co, float *uv2co, float *uv3co,
1838                 float bucket_bounds_uv[8][2],
1839                 int *tot)
1840 {
1841         int inside_bucket_flag = 0;
1842         int inside_face_flag = 0;
1843         const int flip = ((SIDE_OF_LINE(v1coSS, v2coSS, v3coSS) > 0.0f) != (SIDE_OF_LINE(uv1co, uv2co, uv3co) > 0.0f));
1844         
1845         float bucket_bounds_ss[4][2];
1846
1847         /* get the UV space bounding box */
1848         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v1coSS[0], v1coSS[1]);
1849         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v2coSS[0], v2coSS[1])          << 1;
1850         inside_bucket_flag |= BLI_in_rctf(bucket_bounds, v3coSS[0], v3coSS[1])          << 2;
1851         
1852         if (inside_bucket_flag == ISECT_ALL3) {
1853                 /* all screenspace points are inside the bucket bounding box, this means we dont need to clip and can simply return the UVs */
1854                 if (flip) { /* facing the back? */
1855                         VECCOPY2D(bucket_bounds_uv[0], uv3co);
1856                         VECCOPY2D(bucket_bounds_uv[1], uv2co);
1857                         VECCOPY2D(bucket_bounds_uv[2], uv1co);
1858                 }
1859                 else {
1860                         VECCOPY2D(bucket_bounds_uv[0], uv1co);
1861                         VECCOPY2D(bucket_bounds_uv[1], uv2co);
1862                         VECCOPY2D(bucket_bounds_uv[2], uv3co);
1863                 }
1864                 
1865                 *tot = 3; 
1866                 return;
1867         }
1868         
1869         /* get the UV space bounding box */
1870         /* use IsectPT2Df_limit here so we catch points are are touching the tri edge (or a small fraction over) */
1871         bucket_bounds_ss[0][0] = bucket_bounds->xmax;
1872         bucket_bounds_ss[0][1] = bucket_bounds->ymin;
1873         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[0], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_1 : 0);
1874         
1875         bucket_bounds_ss[1][0] = bucket_bounds->xmax;
1876         bucket_bounds_ss[1][1] = bucket_bounds->ymax;
1877         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[1], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_2 : 0);
1878
1879         bucket_bounds_ss[2][0] = bucket_bounds->xmin;
1880         bucket_bounds_ss[2][1] = bucket_bounds->ymax;
1881         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[2], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_3 : 0);
1882
1883         bucket_bounds_ss[3][0] = bucket_bounds->xmin;
1884         bucket_bounds_ss[3][1] = bucket_bounds->ymin;
1885         inside_face_flag |= (IsectPT2Df_limit(bucket_bounds_ss[3], v1coSS, v2coSS, v3coSS, 1+PROJ_GEOM_TOLERANCE) ? ISECT_4 : 0);
1886         
1887         if (inside_face_flag == ISECT_ALL4) {
1888                 /* bucket is totally inside the screenspace face, we can safely use weights */
1889                 
1890                 if (is_ortho)   rect_to_uvspace_ortho(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, bucket_bounds_uv, flip);
1891                 else                    rect_to_uvspace_persp(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, bucket_bounds_uv, flip);
1892                 
1893                 *tot = 4;
1894                 return;
1895         }
1896         else {
1897                 /* The Complicated Case! 
1898                  * 
1899                  * The 2 cases above are where the face is inside the bucket or the bucket is inside the face.
1900                  * 
1901                  * we need to make a convex polyline from the intersection between the screenspace face
1902                  * and the bucket bounds.
1903                  * 
1904                  * There are a number of ways this could be done, currently it just collects all intersecting verts,
1905                  * and line intersections,  then sorts them clockwise, this is a lot easier then evaluating the geometry to
1906                  * do a correct clipping on both shapes. */
1907                 
1908                 
1909                 /* add a bunch of points, we know must make up the convex hull which is the clipped rect and triangle */
1910                 
1911                 
1912                 
1913                 /* Maximum possible 6 intersections when using a rectangle and triangle */
1914                 float isectVCosSS[8][3]; /* The 3rd float is used to store angle for qsort(), NOT as a Z location */
1915                 float v1_clipSS[2], v2_clipSS[2];
1916                 float w[3];
1917                 
1918                 /* calc center*/
1919                 float cent[2] = {0.0f, 0.0f};
1920                 /*float up[2] = {0.0f, 1.0f};*/
1921                 int i;
1922                 short doubles;
1923                 
1924                 (*tot) = 0;
1925                 
1926                 if (inside_face_flag & ISECT_1) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[0]); (*tot)++; }
1927                 if (inside_face_flag & ISECT_2) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[1]); (*tot)++; }
1928                 if (inside_face_flag & ISECT_3) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[2]); (*tot)++; }
1929                 if (inside_face_flag & ISECT_4) { VECCOPY2D(isectVCosSS[*tot], bucket_bounds_ss[3]); (*tot)++; }
1930                 
1931                 if (inside_bucket_flag & ISECT_1) {     VECCOPY2D(isectVCosSS[*tot], v1coSS); (*tot)++; }
1932                 if (inside_bucket_flag & ISECT_2) {     VECCOPY2D(isectVCosSS[*tot], v2coSS); (*tot)++; }
1933                 if (inside_bucket_flag & ISECT_3) {     VECCOPY2D(isectVCosSS[*tot], v3coSS); (*tot)++; }
1934                 
1935                 if ((inside_bucket_flag & (ISECT_1|ISECT_2)) != (ISECT_1|ISECT_2)) {
1936                         if (line_clip_rect2f(bucket_bounds, v1coSS, v2coSS, v1_clipSS, v2_clipSS)) {
1937                                 if ((inside_bucket_flag & ISECT_1)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
1938                                 if ((inside_bucket_flag & ISECT_2)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
1939                         }
1940                 }
1941                 
1942                 if ((inside_bucket_flag & (ISECT_2|ISECT_3)) != (ISECT_2|ISECT_3)) {
1943                         if (line_clip_rect2f(bucket_bounds, v2coSS, v3coSS, v1_clipSS, v2_clipSS)) {
1944                                 if ((inside_bucket_flag & ISECT_2)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
1945                                 if ((inside_bucket_flag & ISECT_3)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
1946                         }
1947                 }       
1948                 
1949                 if ((inside_bucket_flag & (ISECT_3|ISECT_1)) != (ISECT_3|ISECT_1)) {
1950                         if (line_clip_rect2f(bucket_bounds, v3coSS, v1coSS, v1_clipSS, v2_clipSS)) {
1951                                 if ((inside_bucket_flag & ISECT_3)==0) { VECCOPY2D(isectVCosSS[*tot], v1_clipSS); (*tot)++; }
1952                                 if ((inside_bucket_flag & ISECT_1)==0) { VECCOPY2D(isectVCosSS[*tot], v2_clipSS); (*tot)++; }
1953                         }
1954                 }
1955                 
1956                 
1957                 if ((*tot) < 3) { /* no intersections to speak of */
1958                         *tot = 0;
1959                         return;
1960                 }
1961         
1962                 /* now we have all points we need, collect their angles and sort them clockwise */
1963                 
1964                 for(i=0; i<(*tot); i++) {
1965                         cent[0] += isectVCosSS[i][0];
1966                         cent[1] += isectVCosSS[i][1];
1967                 }
1968                 cent[0] = cent[0] / (float)(*tot);
1969                 cent[1] = cent[1] / (float)(*tot);
1970                 
1971                 
1972                 
1973                 /* Collect angles for every point around the center point */
1974
1975                 
1976 #if 0   /* uses a few more cycles then the above loop */
1977                 for(i=0; i<(*tot); i++) {
1978                         isectVCosSS[i][2] = angle_2d_clockwise(up, cent, isectVCosSS[i]);
1979                 }
1980 #endif
1981
1982                 v1_clipSS[0] = cent[0]; /* Abuse this var for the loop below */
1983                 v1_clipSS[1] = cent[1] + 1.0f;
1984                 
1985                 for(i=0; i<(*tot); i++) {
1986                         v2_clipSS[0] = isectVCosSS[i][0] - cent[0];
1987                         v2_clipSS[1] = isectVCosSS[i][1] - cent[1];
1988                         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]); 
1989                 }
1990                 
1991                 if (flip)       qsort(isectVCosSS, *tot, sizeof(float)*3, float_z_sort_flip);
1992                 else            qsort(isectVCosSS, *tot, sizeof(float)*3, float_z_sort);
1993                 
1994                 /* remove doubles */
1995                 /* first/last check */
1996                 if (fabsf(isectVCosSS[0][0]-isectVCosSS[(*tot)-1][0]) < PROJ_GEOM_TOLERANCE &&  fabsf(isectVCosSS[0][1]-isectVCosSS[(*tot)-1][1]) < PROJ_GEOM_TOLERANCE) {
1997                         (*tot)--;
1998                 }
1999                 
2000                 /* its possible there is only a few left after remove doubles */
2001                 if ((*tot) < 3) {
2002                         // printf("removed too many doubles A\n");
2003                         *tot = 0;
2004                         return;
2005                 }
2006                 
2007                 doubles = TRUE;
2008                 while (doubles==TRUE) {
2009                         doubles = FALSE;
2010                         for(i=1; i<(*tot); i++) {
2011                                 if (fabsf(isectVCosSS[i-1][0]-isectVCosSS[i][0]) < PROJ_GEOM_TOLERANCE &&
2012                                         fabsf(isectVCosSS[i-1][1]-isectVCosSS[i][1]) < PROJ_GEOM_TOLERANCE)
2013                                 {
2014                                         int j;
2015                                         for(j=i+1; j<(*tot); j++) {
2016                                                 isectVCosSS[j-1][0] = isectVCosSS[j][0]; 
2017                                                 isectVCosSS[j-1][1] = isectVCosSS[j][1]; 
2018                                         }
2019                                         doubles = TRUE; /* keep looking for more doubles */
2020                                         (*tot)--;
2021                                 }
2022                         }
2023                 }
2024                 
2025                 /* its possible there is only a few left after remove doubles */
2026                 if ((*tot) < 3) {
2027                         // printf("removed too many doubles B\n");
2028                         *tot = 0;
2029                         return;
2030                 }
2031                 
2032                 
2033                 if (is_ortho) {
2034                         for(i=0; i<(*tot); i++) {
2035                                 barycentric_weights_v2(v1coSS, v2coSS, v3coSS, isectVCosSS[i], w);
2036                                 interp_v2_v2v2v2(bucket_bounds_uv[i], uv1co, uv2co, uv3co, w);
2037                         }
2038                 }
2039                 else {
2040                         for(i=0; i<(*tot); i++) {
2041                                 barycentric_weights_v2_persp(v1coSS, v2coSS, v3coSS, isectVCosSS[i], w);
2042                                 interp_v2_v2v2v2(bucket_bounds_uv[i], uv1co, uv2co, uv3co, w);
2043                         }
2044                 }
2045         }
2046
2047 #ifdef PROJ_DEBUG_PRINT_CLIP
2048         /* include this at the bottom of the above function to debug the output */
2049
2050         {
2051                 /* If there are ever any problems, */
2052                 float test_uv[4][2];
2053                 int i;
2054                 if (is_ortho)   rect_to_uvspace_ortho(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, test_uv, flip);
2055                 else                            rect_to_uvspace_persp(bucket_bounds, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, test_uv, flip);
2056                 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]);
2057                 
2058                 printf("  [(%f,%f), (%f,%f), (%f,%f)], ", uv1co[0], uv1co[1],   uv2co[0], uv2co[1],    uv3co[0], uv3co[1]);
2059                 
2060                 printf("[");
2061                 for (i=0; i < (*tot); i++) {
2062                         printf("(%f, %f),", bucket_bounds_uv[i][0], bucket_bounds_uv[i][1]);
2063                 }
2064                 printf("]),\\\n");
2065         }
2066 #endif
2067 }
2068
2069         /*
2070 # This script creates faces in a blender scene from printed data above.
2071
2072 project_ls = [
2073 ...(output from above block)...
2074 ]
2075  
2076 from Blender import Scene, Mesh, Window, sys, Mathutils
2077
2078 import bpy
2079
2080 V = Mathutils.Vector
2081
2082 def main():
2083         sce = bpy.data.scenes.active
2084         
2085         for item in project_ls:
2086                 bb = item[0]
2087                 uv = item[1]
2088                 poly = item[2]
2089                 
2090                 me = bpy.data.meshes.new()
2091                 ob = sce.objects.new(me)
2092                 
2093                 me.verts.extend([V(bb[0]).resize3D(), V(bb[1]).resize3D(), V(bb[2]).resize3D(), V(bb[3]).resize3D()])
2094                 me.faces.extend([(0,1,2,3),])
2095                 me.verts.extend([V(uv[0]).resize3D(), V(uv[1]).resize3D(), V(uv[2]).resize3D()])
2096                 me.faces.extend([(4,5,6),])
2097                 
2098                 vs = [V(p).resize3D() for p in poly]
2099                 print len(vs)
2100                 l = len(me.verts)
2101                 me.verts.extend(vs)
2102                 
2103                 i = l
2104                 while i < len(me.verts):
2105                         ii = i+1
2106                         if ii==len(me.verts):
2107                                 ii = l
2108                         me.edges.extend([i, ii])
2109                         i+=1
2110
2111 if __name__ == '__main__':
2112         main()
2113  */     
2114
2115
2116 #undef ISECT_1
2117 #undef ISECT_2
2118 #undef ISECT_3
2119 #undef ISECT_4
2120 #undef ISECT_ALL3
2121 #undef ISECT_ALL4
2122
2123         
2124 /* checks if pt is inside a convex 2D polyline, the polyline must be ordered rotating clockwise
2125  * otherwise it would have to test for mixed (SIDE_OF_LINE > 0.0f) cases */
2126 int IsectPoly2Df(const float pt[2], float uv[][2], const int tot)
2127 {
2128         int i;
2129         if (SIDE_OF_LINE(uv[tot-1], uv[0], pt) < 0.0f)
2130                 return 0;
2131         
2132         for (i=1; i<tot; i++) {
2133                 if (SIDE_OF_LINE(uv[i-1], uv[i], pt) < 0.0f)
2134                         return 0;
2135                 
2136         }
2137         
2138         return 1;
2139 }
2140 static int IsectPoly2Df_twoside(const float pt[2], float uv[][2], const int tot)
2141 {
2142         int i;
2143         int side = (SIDE_OF_LINE(uv[tot-1], uv[0], pt) > 0.0f);
2144         
2145         for (i=1; i<tot; i++) {
2146                 if ((SIDE_OF_LINE(uv[i-1], uv[i], pt) > 0.0f) != side)
2147                         return 0;
2148                 
2149         }
2150         
2151         return 1;
2152 }
2153
2154 /* One of the most important function for projectiopn painting, since it selects the pixels to be added into each bucket.
2155  * initialize pixels from this face where it intersects with the bucket_index, optionally initialize pixels for removing seams */
2156 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)
2157 {
2158         /* Projection vars, to get the 3D locations into screen space  */
2159         MemArena *arena = ps->arena_mt[thread_index];
2160         LinkNode **bucketPixelNodes = ps->bucketRect + bucket_index;
2161         LinkNode *bucketFaceNodes = ps->bucketFaces[bucket_index];
2162         
2163         const MFace *mf = ps->dm_mface + face_index;
2164         const MTFace *tf = ps->dm_mtface + face_index;
2165         
2166         /* UV/pixel seeking data */
2167         int x; /* Image X-Pixel */
2168         int y;/* Image Y-Pixel */
2169         float mask;
2170         float uv[2]; /* Image floating point UV - same as x, y but from 0.0-1.0 */
2171         
2172         int side;
2173         float *v1coSS, *v2coSS, *v3coSS; /* vert co screen-space, these will be assigned to mf->v1,2,3 or mf->v1,3,4 */
2174         
2175         float *vCo[4]; /* vertex screenspace coords */
2176         
2177         float w[3], wco[3];
2178         
2179         float *uv1co, *uv2co, *uv3co; /* for convenience only, these will be assigned to tf->uv[0],1,2 or tf->uv[0],2,3 */
2180         float pixelScreenCo[4];
2181         
2182         rcti bounds_px; /* ispace bounds */
2183         /* vars for getting uvspace bounds */
2184         
2185         float tf_uv_pxoffset[4][2]; /* bucket bounds in UV space so we can init pixels only for this face,  */
2186         float xhalfpx, yhalfpx;
2187         const float ibuf_xf = ibuf->x, ibuf_yf = ibuf->y;
2188         
2189         int has_x_isect = 0, has_isect = 0; /* for early loop exit */
2190         
2191         int i1, i2, i3;
2192         
2193         float uv_clip[8][2];
2194         int uv_clip_tot;
2195         const short is_ortho = ps->is_ortho;
2196         const short do_backfacecull = ps->do_backfacecull;
2197         
2198         vCo[0] = ps->dm_mvert[mf->v1].co;
2199         vCo[1] = ps->dm_mvert[mf->v2].co;
2200         vCo[2] = ps->dm_mvert[mf->v3].co;
2201         
2202         
2203         /* Use tf_uv_pxoffset instead of tf->uv so we can offset the UV half a pixel
2204          * this is done so we can avoid offseting all the pixels by 0.5 which causes
2205          * problems when wrapping negative coords */
2206         xhalfpx = (0.5f+   (PROJ_GEOM_TOLERANCE/3.0f)   ) / ibuf_xf;
2207         yhalfpx = (0.5f+   (PROJ_GEOM_TOLERANCE/4.0f)   ) / ibuf_yf;
2208         
2209         /* Note about (PROJ_GEOM_TOLERANCE/x) above...
2210           Needed to add this offset since UV coords are often quads aligned to pixels.
2211           In this case pixels can be exactly between 2 triangles causing nasty
2212           artifacts.
2213           
2214           This workaround can be removed and painting will still work on most cases
2215           but since the first thing most people try is painting onto a quad- better make it work.
2216          */
2217
2218
2219
2220         tf_uv_pxoffset[0][0] = tf->uv[0][0] - xhalfpx;
2221         tf_uv_pxoffset[0][1] = tf->uv[0][1] - yhalfpx;
2222
2223         tf_uv_pxoffset[1][0] = tf->uv[1][0] - xhalfpx;
2224         tf_uv_pxoffset[1][1] = tf->uv[1][1] - yhalfpx;
2225         
2226         tf_uv_pxoffset[2][0] = tf->uv[2][0] - xhalfpx;
2227         tf_uv_pxoffset[2][1] = tf->uv[2][1] - yhalfpx;  
2228         
2229         if (mf->v4) {
2230                 vCo[3] = ps->dm_mvert[ mf->v4 ].co;
2231                 
2232                 tf_uv_pxoffset[3][0] = tf->uv[3][0] - xhalfpx;
2233                 tf_uv_pxoffset[3][1] = tf->uv[3][1] - yhalfpx;
2234                 side = 1;
2235         }
2236         else {
2237                 side = 0;
2238         }
2239         
2240         do {
2241                 if (side==1) {
2242                         i1=0; i2=2; i3=3;
2243                 }
2244                 else {
2245                         i1=0; i2=1; i3=2;
2246                 }
2247                 
2248                 uv1co = tf_uv_pxoffset[i1]; // was tf->uv[i1];
2249                 uv2co = tf_uv_pxoffset[i2]; // was tf->uv[i2];
2250                 uv3co = tf_uv_pxoffset[i3]; // was tf->uv[i3];
2251
2252                 v1coSS = ps->screenCoords[ (*(&mf->v1 + i1)) ];
2253                 v2coSS = ps->screenCoords[ (*(&mf->v1 + i2)) ];
2254                 v3coSS = ps->screenCoords[ (*(&mf->v1 + i3)) ];
2255                 
2256                 /* This funtion gives is a concave polyline in UV space from the clipped quad and tri*/
2257                 project_bucket_clip_face(
2258                                 is_ortho, bucket_bounds,
2259                                 v1coSS, v2coSS, v3coSS,
2260                                 uv1co, uv2co, uv3co,
2261                                 uv_clip, &uv_clip_tot
2262                 );
2263
2264                 /* sometimes this happens, better just allow for 8 intersectiosn even though there should be max 6 */
2265                 /*
2266                 if (uv_clip_tot>6) {
2267                         printf("this should never happen! %d\n", uv_clip_tot);
2268                 }*/
2269                 
2270
2271                 if (pixel_bounds_array(uv_clip, &bounds_px, ibuf->x, ibuf->y, uv_clip_tot)) {
2272                         
2273                         /* clip face and */
2274                         
2275                         has_isect = 0;
2276                         for (y = bounds_px.ymin; y < bounds_px.ymax; y++) {
2277                                 //uv[1] = (((float)y) + 0.5f) / (float)ibuf->y;
2278                                 uv[1] = (float)y / ibuf_yf; /* use pixel offset UV coords instead */
2279                                 
2280                                 has_x_isect = 0;
2281                                 for (x = bounds_px.xmin; x < bounds_px.xmax; x++) {
2282                                         //uv[0] = (((float)x) + 0.5f) / ibuf->x;
2283                                         uv[0] = (float)x / ibuf_xf; /* use pixel offset UV coords instead */
2284                                         
2285                                         /* Note about IsectPoly2Df_twoside, checking the face or uv flipping doesnt work,
2286                                          * could check the poly direction but better to do this */
2287                                         if(     (do_backfacecull                && IsectPoly2Df(uv, uv_clip, uv_clip_tot)) ||
2288                                                 (do_backfacecull==0             && IsectPoly2Df_twoside(uv, uv_clip, uv_clip_tot))) {
2289                                                 
2290                                                 has_x_isect = has_isect = 1;
2291                                                 
2292                                                 if (is_ortho)   screen_px_from_ortho(uv, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, pixelScreenCo, w);
2293                                                 else                    screen_px_from_persp(uv, v1coSS, v2coSS, v3coSS, uv1co, uv2co, uv3co, pixelScreenCo, w);
2294                                                 
2295                                                 /* a pitty we need to get the worldspace pixel location here */
2296                                                 if(ps->rv3d->rflag & RV3D_CLIPPING) {
2297                                                         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);
2298                                                         if(view3d_test_clipping(ps->rv3d, wco, 1)) {
2299                                                                 continue; /* Watch out that no code below this needs to run */
2300                                                         }
2301                                                 }
2302                                                 
2303                                                 /* Is this UV visible from the view? - raytrace */
2304                                                 /* project_paint_PickFace is less complex, use for testing */
2305                                                 //if (project_paint_PickFace(ps, pixelScreenCo, w, &side) == face_index) {
2306                                                 if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucketFaceNodes, face_index, pixelScreenCo)) {
2307                                                         
2308                                                         mask = project_paint_uvpixel_mask(ps, face_index, side, w);
2309                                                         
2310                                                         if (mask > 0.0f) {
2311                                                                 BLI_linklist_prepend_arena(
2312                                                                         bucketPixelNodes,
2313                                                                         project_paint_uvpixel_init(ps, arena, ibuf, x, y, mask, face_index, image_index, pixelScreenCo, side, w),
2314                                                                         arena
2315                                                                 );
2316                                                         }
2317                                                 }
2318                                                 
2319                                         }
2320 //#if 0
2321                                         else if (has_x_isect) {
2322                                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2323                                                 break;
2324                                         }
2325 //#endif
2326                                 }
2327                                 
2328                                 
2329 #if 0                   /* TODO - investigate why this dosnt work sometimes! it should! */
2330                                 /* no intersection for this entire row, after some intersection above means we can quit now */
2331                                 if (has_x_isect==0 && has_isect) { 
2332                                         break;
2333                                 }
2334 #endif
2335                         }
2336                 }
2337         } while(side--);
2338
2339         
2340         
2341 #ifndef PROJ_DEBUG_NOSEAMBLEED
2342         if (ps->seam_bleed_px > 0.0f) {
2343                 int face_seam_flag;
2344                 
2345                 if (ps->thread_tot > 1)
2346                         BLI_lock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2347                 
2348                 face_seam_flag = ps->faceSeamFlags[face_index];
2349                 
2350                 /* are any of our edges un-initialized? */
2351                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_NOSEAM1))==0 || 
2352                         (face_seam_flag & (PROJ_FACE_SEAM2|PROJ_FACE_NOSEAM2))==0 || 
2353                         (face_seam_flag & (PROJ_FACE_SEAM3|PROJ_FACE_NOSEAM3))==0 || 
2354                         (face_seam_flag & (PROJ_FACE_SEAM4|PROJ_FACE_NOSEAM4))==0
2355                 ) {
2356                         project_face_seams_init(ps, face_index, mf->v4);
2357                         face_seam_flag = ps->faceSeamFlags[face_index];
2358                         //printf("seams - %d %d %d %d\n", flag&PROJ_FACE_SEAM1, flag&PROJ_FACE_SEAM2, flag&PROJ_FACE_SEAM3, flag&PROJ_FACE_SEAM4);
2359                 }
2360                 
2361                 if ((face_seam_flag & (PROJ_FACE_SEAM1|PROJ_FACE_SEAM2|PROJ_FACE_SEAM3|PROJ_FACE_SEAM4))==0) {
2362                         
2363                         if (ps->thread_tot > 1)
2364                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2365                         
2366                 }
2367                 else {
2368                         /* we have a seam - deal with it! */
2369                         
2370                         /* Now create new UV's for the seam face */
2371                         float (*outset_uv)[2] = ps->faceSeamUVs[face_index];
2372                         float insetCos[4][3]; /* inset face coords.  NOTE!!! ScreenSace for ortho, Worldspace in prespective view */
2373
2374                         float fac;
2375                         float *vCoSS[4]; /* vertex screenspace coords */
2376                         
2377                         float bucket_clip_edges[2][2]; /* store the screenspace coords of the face, clipped by the bucket's screen aligned rectangle */
2378                         float edge_verts_inset_clip[2][3];
2379                         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 */
2380                         
2381                         float seam_subsection[4][2];
2382                         float fac1, fac2, ftot;
2383                         
2384                         
2385                         if (outset_uv[0][0]==FLT_MAX) /* first time initialize */
2386                                 uv_image_outset(tf_uv_pxoffset, outset_uv, ps->seam_bleed_px, ibuf->x, ibuf->y, mf->v4);
2387                         
2388                         /* ps->faceSeamUVs cant be modified when threading, now this is done we can unlock */
2389                         if (ps->thread_tot > 1)
2390                                 BLI_unlock_thread(LOCK_CUSTOM1); /* Other threads could be modifying these vars */
2391                         
2392                         vCoSS[0] = ps->screenCoords[mf->v1];
2393                         vCoSS[1] = ps->screenCoords[mf->v2];
2394                         vCoSS[2] = ps->screenCoords[mf->v3];
2395                         if (mf->v4)
2396                                 vCoSS[3] = ps->screenCoords[ mf->v4 ];
2397                         
2398                         /* PROJ_FACE_SCALE_SEAM must be slightly less then 1.0f */
2399                         if (is_ortho) {
2400                                 if (mf->v4)     scale_quad(insetCos, vCoSS, PROJ_FACE_SCALE_SEAM);
2401                                 else            scale_tri(insetCos, vCoSS, PROJ_FACE_SCALE_SEAM);
2402                         }
2403                         else {
2404                                 if (mf->v4)     scale_quad(insetCos, vCo, PROJ_FACE_SCALE_SEAM);
2405                                 else            scale_tri(insetCos, vCo, PROJ_FACE_SCALE_SEAM);
2406                         }
2407                         
2408                         side = 0; /* for triangles this wont need to change */
2409                         
2410                         for (fidx1 = 0; fidx1 < (mf->v4 ? 4 : 3); fidx1++) {
2411                                 if (mf->v4)             fidx2 = (fidx1==3) ? 0 : fidx1+1; /* next fidx in the face (0,1,2,3) -> (1,2,3,0) */
2412                                 else                    fidx2 = (fidx1==2) ? 0 : fidx1+1; /* next fidx in the face (0,1,2) -> (1,2,0) */
2413                                 
2414                                 if (    (face_seam_flag & (1<<fidx1)) && /* 1<<fidx1 -> PROJ_FACE_SEAM# */
2415                                                 line_clip_rect2f(bucket_bounds, vCoSS[fidx1], vCoSS[fidx2], bucket_clip_edges[0], bucket_clip_edges[1])
2416                                 ) {
2417
2418                                         ftot = len_v2v2(vCoSS[fidx1], vCoSS[fidx2]); /* screenspace edge length */
2419                                         
2420                                         if (ftot > 0.0f) { /* avoid div by zero */
2421                                                 if (mf->v4) {
2422                                                         if (fidx1==2 || fidx2==2)       side= 1;
2423                                                         else                                            side= 0;
2424                                                 }
2425                                                 
2426                                                 fac1 = len_v2v2(vCoSS[fidx1], bucket_clip_edges[0]) / ftot;
2427                                                 fac2 = len_v2v2(vCoSS[fidx1], bucket_clip_edges[1]) / ftot;
2428                                                 
2429                                                 interp_v2_v2v2(seam_subsection[0], tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2], fac1);
2430                                                 interp_v2_v2v2(seam_subsection[1], tf_uv_pxoffset[fidx1], tf_uv_pxoffset[fidx2], fac2);
2431
2432                                                 interp_v2_v2v2(seam_subsection[2], outset_uv[fidx1], outset_uv[fidx2], fac2);
2433                                                 interp_v2_v2v2(seam_subsection[3], outset_uv[fidx1], outset_uv[fidx2], fac1);
2434                                                 
2435                                                 /* if the bucket_clip_edges values Z values was kept we could avoid this
2436                                                  * Inset needs to be added so occlusion tests wont hit adjacent faces */
2437                                                 interp_v3_v3v3(edge_verts_inset_clip[0], insetCos[fidx1], insetCos[fidx2], fac1);
2438                                                 interp_v3_v3v3(edge_verts_inset_clip[1], insetCos[fidx1], insetCos[fidx2], fac2);
2439                                                 
2440
2441                                                 if (pixel_bounds_uv(seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3], &bounds_px, ibuf->x, ibuf->y, 1)) {
2442                                                         /* bounds between the seam rect and the uvspace bucket pixels */
2443                                                         
2444                                                         has_isect = 0;
2445                                                         for (y = bounds_px.ymin; y < bounds_px.ymax; y++) {
2446                                                                 // uv[1] = (((float)y) + 0.5f) / (float)ibuf->y;
2447                                                                 uv[1] = (float)y / ibuf_yf; /* use offset uvs instead */
2448                                                                 
2449                                                                 has_x_isect = 0;
2450                                                                 for (x = bounds_px.xmin; x < bounds_px.xmax; x++) {
2451                                                                         //uv[0] = (((float)x) + 0.5f) / (float)ibuf->x;
2452                                                                         uv[0] = (float)x / ibuf_xf; /* use offset uvs instead */
2453                                                                         
2454                                                                         /* test we're inside uvspace bucket and triangle bounds */
2455                                                                         if (isect_point_quad_v2(uv, seam_subsection[0], seam_subsection[1], seam_subsection[2], seam_subsection[3])) {
2456                                                                                 
2457                                                                                 /* We need to find the closest point along the face edge,
2458                                                                                  * getting the screen_px_from_*** wont work because our actual location
2459                                                                                  * is not relevent, since we are outside the face, Use VecLerpf to find
2460                                                                                  * our location on the side of the face's UV */
2461                                                                                 /*
2462                                                                                 if (is_ortho)   screen_px_from_ortho(ps, uv, v1co, v2co, v3co, uv1co, uv2co, uv3co, pixelScreenCo);
2463                                                                                 else                                    screen_px_from_persp(ps, uv, v1co, v2co, v3co, uv1co, uv2co, uv3co, pixelScreenCo);
2464                                                                                 */
2465                                                                                 
2466                                                                                 /* Since this is a seam we need to work out where on the line this pixel is */
2467                                                                                 //fac = lambda_cp_line2(uv, uv_seam_quad[0], uv_seam_quad[1]);
2468                                                                                 
2469                                                                                 fac = lambda_cp_line2(uv, seam_subsection[0], seam_subsection[1]);
2470                                                                                 if (fac < 0.0f)         { VECCOPY(pixelScreenCo, edge_verts_inset_clip[0]); }
2471                                                                                 else if (fac > 1.0f)    { VECCOPY(pixelScreenCo, edge_verts_inset_clip[1]); }
2472                                                                                 else                            { interp_v3_v3v3(pixelScreenCo, edge_verts_inset_clip[0], edge_verts_inset_clip[1], fac); }
2473                                                                                 
2474                                                                                 if (!is_ortho) {
2475                                                                                         pixelScreenCo[3] = 1.0f;
2476                                                                                         mul_m4_v4((float(*)[4])ps->projectMat, pixelScreenCo); /* cast because of const */
2477                                                                                         pixelScreenCo[0] = (float)(ps->ar->winx/2.0f)+(ps->ar->winx/2.0f)*pixelScreenCo[0]/pixelScreenCo[3];    
2478                                                                                         pixelScreenCo[1] = (float)(ps->ar->winy/2.0f)+(ps->ar->winy/2.0f)*pixelScreenCo[1]/pixelScreenCo[3];
2479                                                                                         pixelScreenCo[2] = pixelScreenCo[2]/pixelScreenCo[3]; /* Use the depth for bucket point occlusion */
2480                                                                                 }
2481                                                                                 
2482                                                                                 if (ps->do_occlude==0 || !project_bucket_point_occluded(ps, bucketFaceNodes, face_index, pixelScreenCo)) {
2483                                                                                         
2484                                                                                         /* Only bother calculating the weights if we intersect */
2485                                                                                         if (ps->do_mask_normal || ps->dm_mtface_clone) {
2486 #if 0
2487                                                                                                 /* This is not QUITE correct since UV is not inside the UV's but good enough for seams */
2488                                                                                                 if (side) {
2489                                                                                                         barycentric_weights_v2(tf_uv_pxoffset[0], tf_uv_pxoffset[2], tf_uv_pxoffset[3], uv, w);
2490                                                                                                 }
2491                                                                                                 else {
2492                                                                                                         barycentric_weights_v2(tf_uv_pxoffset[0], tf_uv_pxoffset[1], tf_uv_pxoffset[2], uv, w);
2493                                                                                                 }
2494 #endif
2495 #if 1
2496                                                                                                 /* Cheat, we know where we are along the edge so work out the weights from that */
2497                                                                                                 fac = fac1 + (fac * (fac2-fac1));
2498                                                                                                 w[0]=w[1]=w[2]= 0.0;
2499                                                                                                 if (side) {
2500                                                                                                         w[fidx1?fidx1-1:0] = fac;
2501                                                                                                         w[fidx2?fidx2-1:0] = 1.0-fac;
2502                                                                                                 }
2503                                                                                                 else {
2504                                                                                                         w[fidx1] = fac;
2505                                                                                                         w[fidx2] = 1.0-fac;
2506                                                                                                 }
2507 #endif
2508                                                                                         }
2509                                                                                         
2510                                                                                         /* a pitty we need to get the worldspace pixel location here */
2511                                                                                         if(ps->rv3d->rflag & RV3D_CLIPPING) {
2512                                                                                                 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);
2513                                                                                                 else            interp_v3_v3v3v3(wco, ps->dm_mvert[mf->v1].co, ps->dm_mvert[mf->v2].co, ps->dm_mvert[mf->v3].co, w);
2514
2515                                                                                                 if(view3d_test_clipping(ps->rv3d, wco, 1)) {
2516                                                                                                         continue; /* Watch out that no code below this needs to run */
2517                                                                                                 }
2518                                                                                         }
2519                                                                                         
2520                                                                                         mask = project_paint_uvpixel_mask(ps, face_index, side, w);
2521                                                                                         
2522                                                                                         if (mask > 0.0f) {
2523                                                                                                 BLI_linklist_prepend_arena(
2524                                                                                                         bucketPixelNodes,
2525                                                                                                         project_paint_uvpixel_init(ps, arena, ibuf, x, y, mask, face_index, image_index, pixelScreenCo, side, w),
2526                                                                                                         arena
2527                                                                                                 );
2528                                                                                         }
2529                                                                                         
2530                                                                                 }
2531                                                                         }
2532                                                                         else if (has_x_isect) {
2533                                                                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2534                                                                                 break;
2535                                                                         }
2536                                                                 }
2537                                                                 
2538 #if 0                                                   /* TODO - investigate why this dosnt work sometimes! it should! */
2539                                                                 /* no intersection for this entire row, after some intersection above means we can quit now */
2540                                                                 if (has_x_isect==0 && has_isect) { 
2541                                                                         break;
2542                                                                 }
2543 #endif
2544                                                         }
2545                                                 }
2546                                         }
2547                                 }
2548                         }
2549                 }
2550         }
2551 #endif // PROJ_DEBUG_NOSEAMBLEED
2552 }
2553
2554
2555 /* takes floating point screenspace min/max and returns int min/max to be used as indicies for ps->bucketRect, ps->bucketFlags */
2556 static void project_paint_bucket_bounds(const ProjPaintState *ps, const float min[2], const float max[2], int bucketMin[2], int bucketMax[2])
2557 {
2558         /* divide by bucketWidth & bucketHeight so the bounds are offset in bucket grid units */
2559         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 */
2560         bucketMin[1] = (int)(((float)(min[1] - ps->screenMin[1]) / ps->screen_height) * ps->buckets_y) + 0.5f;
2561         
2562         bucketMax[0] = (int)(((float)(max[0] - ps->screenMin[0]) / ps->screen_width) * ps->buckets_x) + 1.5f;
2563         bucketMax[1] = (int)(((float)(max[1] - ps->screenMin[1]) / ps->screen_height) * ps->buckets_y) + 1.5f;  
2564         
2565         /* incase the rect is outside the mesh 2d bounds */
2566         CLAMP(bucketMin[0], 0, ps->buckets_x);
2567         CLAMP(bucketMin[1], 0, ps->buckets_y);
2568         
2569         CLAMP(bucketMax[0], 0, ps->buckets_x);
2570         CLAMP(bucketMax[1], 0, ps->buckets_y);
2571 }
2572
2573 /* set bucket_bounds to a screen space-aligned floating point bound-box */
2574 static void project_bucket_bounds(const ProjPaintState *ps, const int bucket_x, const int bucket_y, rctf *bucket_bounds)
2575 {
2576         bucket_bounds->xmin =   ps->screenMin[0]+((bucket_x)*(ps->screen_width / ps->buckets_x));               /* left */
2577         bucket_bounds->xmax =   ps->screenMin[0]+((bucket_x+1)*(ps->screen_width / ps->buckets_x));     /* right */
2578         
2579         bucket_bounds->ymin =   ps->screenMin[1]+((bucket_y)*(ps->screen_height / ps->buckets_y));              /* bottom */
2580         bucket_bounds->ymax =   ps->screenMin[1]+((bucket_y+1)*(ps->screen_height  / ps->buckets_y));   /* top */
2581 }
2582
2583 /* Fill this bucket with pixels from the faces that intersect it.
2584  * 
2585  * have bucket_bounds as an argument so we don;t need to give bucket_x/y the rect function needs */
2586 static void project_bucket_init(const ProjPaintState *ps, const int thread_index, const int bucket_index, rctf *bucket_bounds)
2587 {
2588         LinkNode *node;
2589         int face_index, image_index=0;
2590         ImBuf *ibuf = NULL;
2591         MTFace *tf;
2592         
2593         Image *tpage_last = NULL;
2594         
2595
2596         if (ps->image_tot==1) {
2597                 /* Simple loop, no context switching */
2598                 ibuf = ps->projImages[0].ibuf;
2599                 
2600                 for (node = ps->bucketFaces[bucket_index]; node; node= node->next) { 
2601                         project_paint_face_init(ps, thread_index, bucket_index, GET_INT_FROM_POINTER(node->link), 0, bucket_bounds, ibuf);
2602                 }
2603         }
2604         else {
2605                 
2606                 /* More complicated loop, switch between images */
2607                 for (node = ps->bucketFaces[bucket_index]; node; node= node->next) {
2608                         face_index = GET_INT_FROM_POINTER(node->link);
2609                                 
2610                         /* Image context switching */
2611                         tf = ps->dm_mtface+face_index;
2612                         if (tpage_last != tf->tpage) {
2613                                 tpage_last = tf->tpage;
2614                                 
2615                                 image_index = -1; /* sanity check */
2616                                 
2617                                 for (image_index=0; image_index < ps->image_tot; image_index++) {
2618                                         if (ps->projImages[image_index].ima == tpage_last) {
2619                                                 ibuf = ps->projImages[image_index].ibuf;
2620                                                 break;
2621                                         }
2622                                 }
2623                         }
2624                         /* context switching done */
2625                         
2626                         project_paint_face_init(ps, thread_index, bucket_index, face_index, image_index, bucket_bounds, ibuf);
2627                         
2628                 }
2629         }
2630         
2631         ps->bucketFlags[bucket_index] |= PROJ_BUCKET_INIT;
2632 }
2633
2634
2635 /* We want to know if a bucket and a face overlap in screen-space
2636  * 
2637  * Note, if this ever returns false positives its not that bad, since a face in the bounding area will have its pixels
2638  * calculated when it might not be needed later, (at the moment at least)
2639  * obviously it shouldn't have bugs though */
2640
2641 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)
2642 {
2643         /* TODO - replace this with a tricker method that uses sideofline for all screenCoords's edges against the closest bucket corner */
2644         rctf bucket_bounds;
2645         float p1[2], p2[2], p3[2], p4[2];
2646         float *v, *v1,*v2,*v3,*v4=NULL;
2647         int fidx;
2648         
2649         project_bucket_bounds(ps, bucket_x, bucket_y, &bucket_bounds);
2650         
2651         /* Is one of the faces verts in the bucket bounds? */
2652         
2653         fidx = mf->v4 ? 3:2;
2654         do {
2655                 v = ps->screenCoords[ (*(&mf->v1 + fidx)) ];
2656                 if (BLI_in_rctf(&bucket_bounds, v[0], v[1])) {
2657                         return 1;
2658                 }
2659         } while (fidx--);
2660         
2661         v1 = ps->screenCoords[mf->v1];
2662         v2 = ps->screenCoords[mf->v2];
2663         v3 = ps->screenCoords[mf->v3];
2664         if (mf->v4) {
2665                 v4 = ps->screenCoords[mf->v4];
2666         }
2667         
2668         p1[0] = bucket_bounds.xmin; p1[1] = bucket_bounds.ymin;
2669         p2[0] = bucket_bounds.xmin;     p2[1] = bucket_bounds.ymax;
2670         p3[0] = bucket_bounds.xmax;     p3[1] = bucket_bounds.ymax;
2671         p4[0] = bucket_bounds.xmax;     p4[1] = bucket_bounds.ymin;
2672                 
2673         if (mf->v4) {
2674                 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) ||
2675                         /* we can avoid testing v3,v1 because another intersection MUST exist if this intersects */
2676                         (isect_line_line_v2(p1, p2, v1, v2) || isect_line_line_v2(p1, p2, v2, v3) || isect_line_line_v2(p1, p2, v3, v4)) ||
2677                         (isect_line_line_v2(p2, p3, v1, v2) || isect_line_line_v2(p2, p3, v2, v3) || isect_line_line_v2(p2, p3, v3, v4)) ||
2678                         (isect_line_line_v2(p3, p4, v1, v2) || isect_line_line_v2(p3, p4, v2, v3) || isect_line_line_v2(p3, p4, v3, v4)) ||
2679                         (isect_line_line_v2(p4, p1, v1, v2) || isect_line_line_v2(p4, p1, v2, v3) || isect_line_line_v2(p4, p1, v3, v4))
2680                 ) {
2681                         return 1;
2682                 }
2683         }
2684         else {
2685                 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) ||
2686                         /* we can avoid testing v3,v1 because another intersection MUST exist if this intersects */
2687                         (isect_line_line_v2(p1, p2, v1, v2) || isect_line_line_v2(p1, p2, v2, v3)) ||
2688                         (isect_line_line_v2(p2, p3, v1, v2) || isect_line_line_v2(p2, p3, v2, v3)) ||
2689                         (isect_line_line_v2(p3, p4, v1, v2) || isect_line_line_v2(p3, p4, v2, v3)) ||
2690                         (isect_line_line_v2(p4, p1, v1, v2) || isect_line_line_v2(p4, p1, v2, v3))
2691                 ) {
2692                         return 1;
2693                 }
2694         }
2695
2696         return 0;
2697 }
2698
2699 /* Add faces to the bucket but dont initialize its pixels
2700  * TODO - when painting occluded, sort the faces on their min-Z and only add faces that faces that are not occluded */
2701 static void project_paint_delayed_face_init(ProjPaintState *ps, const MFace *mf, const MTFace *tf, const int face_index)
2702 {
2703         float min[2], max[2], *vCoSS;
2704         int bucketMin[2], bucketMax[2]; /* for  ps->bucketRect indexing */
2705         int fidx, bucket_x, bucket_y, bucket_index;
2706         int has_x_isect = -1, has_isect = 0; /* for early loop exit */
2707         MemArena *arena = ps->arena_mt[0]; /* just use the first thread arena since threading has not started yet */
2708         
2709         INIT_MINMAX2(min, max);
2710         
2711         fidx = mf->v4 ? 3:2;
2712         do {
2713                 vCoSS = ps->screenCoords[ *(&mf->v1 + fidx) ];
2714                 DO_MINMAX2(vCoSS, min, max);
2715         } while (fidx--);
2716         
2717         project_paint_bucket_bounds(ps, min, max, bucketMin, bucketMax);
2718         
2719         for (bucket_y = bucketMin[1]; bucket_y < bucketMax[1]; bucket_y++) {
2720                 has_x_isect = 0;
2721                 for (bucket_x = bucketMin[0]; bucket_x < bucketMax[0]; bucket_x++) {
2722                         
2723                         bucket_index = bucket_x + (bucket_y * ps->buckets_x);
2724                         
2725                         if (project_bucket_face_isect(ps, min, max, bucket_x, bucket_y, bucket_index, mf)) {
2726                                 BLI_linklist_prepend_arena(
2727                                         &ps->bucketFaces[ bucket_index ],
2728                                         SET_INT_IN_POINTER(face_index), /* cast to a pointer to shut up the compiler */
2729                                         arena
2730                                 );
2731                                 
2732                                 has_x_isect = has_isect = 1;
2733                         }
2734                         else if (has_x_isect) {
2735                                 /* assuming the face is not a bow-tie - we know we cant intersect again on the X */
2736                                 break;
2737                         }
2738                 }
2739                 
2740                 /* no intersection for this entire row, after some intersection above means we can quit now */
2741                 if (has_x_isect==0 && has_isect) { 
2742                         break;
2743                 }
2744         }
2745         
2746 #ifndef PROJ_DEBUG_NOSEAMBLEED
2747         if (ps->seam_bleed_px > 0.0f) {
2748                 if (!mf->v4) {
2749                         ps->faceSeamFlags[face_index] |= PROJ_FACE_NOSEAM4; /* so this wont show up as an untagged edge */
2750                 }
2751                 **ps->faceSeamUVs[face_index] = FLT_MAX; /* set as uninitialized */
2752         }
2753 #endif
2754 }
2755
2756 /* run once per stroke before projection painting */
2757 static void project_paint_begin(ProjPaintState *ps)
2758 {       
2759         /* Viewport vars */
2760         float mat[3][3];
2761         
2762         float no[3];
2763         
2764         float (*projScreenCo)[4]; /* Note, we could have 4D vectors are only needed for */
2765         float projMargin;
2766         /* Image Vars - keep track of images we have used */
2767         LinkNode *image_LinkList = NULL;
2768         LinkNode *node;
2769         
2770         ProjPaintImage *projIma;
2771         Image *tpage_last = NULL;
2772         
2773         /* Face vars */
2774         MFace *mf;
2775         MTFace *tf;
2776         
2777         int a, i; /* generic looping vars */
2778         int image_index = -1, face_index;
2779         
2780         MemArena *arena; /* at the moment this is just ps->arena_mt[0], but use this to show were not multithreading */
2781         
2782         /* ---- end defines ---- */
2783         
2784         ED_view3d_local_clipping(ps->rv3d, ps->ob->obmat); /* faster clipping lookups */
2785
2786         /* paint onto the derived mesh */
2787         
2788         /* Workaround for subsurf selection, try the display mesh first */
2789         if(ps->ob->derivedFinal && CustomData_has_layer( &ps->ob->derivedFinal->faceData, CD_MTFACE)) {
2790                 ps->dm = ps->ob->derivedFinal;
2791                 ps->dm_release= FALSE;
2792         }
2793         else {
2794                 ps->dm = mesh_get_derived_final(ps->scene, ps->ob, ps->v3d->customdata_mask);
2795                 ps->dm_release= TRUE;
2796         }
2797         
2798         if ( !CustomData_has_layer( &ps->dm->faceData, CD_MTFACE) ) {
2799                 
2800                 if(ps->dm_release)
2801                         ps->dm->release(ps->dm);
2802                 
2803                 ps->dm = NULL;
2804                 return; 
2805         }
2806         
2807         ps->dm_mvert = ps->dm->getVertArray(ps->dm);
2808         ps->dm_mface = ps->dm->getFaceArray(ps->dm);
2809         ps->dm_mtface= ps->dm->getFaceDataArray(ps->dm, CD_MTFACE);
2810         
2811         ps->dm_totvert = ps->dm->getNumVerts(ps->dm);
2812         ps->dm_totface = ps->dm->getNumFaces(ps->dm);
2813         
2814         /* use clone mtface? */
2815         
2816         
2817         /* Note, use the original mesh for getting the clone and mask layer index
2818          * this avoids re-generating the derived mesh just to get the new index */
2819         if (ps->do_layer_clone) {
2820                 //int layer_num = CustomData_get_clone_layer(&ps->dm->faceData, CD_MTFACE);
2821                 int layer_num = CustomData_get_clone_layer(&((Mesh *)ps->ob->data)->fdata, CD_MTFACE);
2822                 if (layer_num != -1)
2823                         ps->dm_mtface_clone = CustomData_get_layer_n(&ps->dm->faceData, CD_MTFACE, layer_num);
2824                 
2825                 if (ps->dm_mtface_clone==NULL || ps->dm_mtface_clone==ps->dm_mtface) {
2826                         ps->do_layer_clone = 0;
2827                         ps->dm_mtface_clone= NULL;
2828                 }
2829         }
2830         
2831         if (ps->do_layer_stencil) {
2832                 //int layer_num = CustomData_get_stencil_layer(&ps->dm->faceData, CD_MTFACE);
2833                 int layer_num = CustomData_get_stencil_layer(&((Mesh *)ps->ob->data)->fdata, CD_MTFACE);
2834                 if (layer_num != -1)
2835                         ps->dm_mtface_stencil = CustomData_get_layer_n(&ps->dm->faceData, CD_MTFACE, layer_num);
2836                 
2837                 if (ps->dm_mtface_stencil==NULL || ps->dm_mtface_stencil==ps->dm_mtface) {
2838                         ps->do_layer_stencil = 0;
2839                         ps->dm_mtface_stencil = NULL;
2840                 }
2841         }
2842         
2843
2844         
2845         ps->viewDir[0] = 0.0f;
2846         ps->viewDir[1] = 0.0f;
2847         ps->viewDir[2] = 1.0f;
2848