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