swap BMLoopCol r/b color, requires subversion bump.
[blender.git] / source / blender / blenkernel / intern / dynamicpaint.c
1 /**
2 ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * Contributor(s): Miika Hämäläinen
10  *
11  * ***** END GPL LICENSE BLOCK *****
12  */
13
14
15 #include "MEM_guardedalloc.h"
16
17 #include <math.h>
18 #include <stdio.h>
19
20 #include "BLI_blenlib.h"
21 #include "BLI_math.h"
22 #include "BLI_kdtree.h"
23 #include "BLI_threads.h"
24 #include "BLI_utildefines.h"
25
26 #include "DNA_anim_types.h"
27 #include "DNA_constraint_types.h"
28 #include "DNA_dynamicpaint_types.h"
29 #include "DNA_group_types.h" /*GroupObject*/
30 #include "DNA_material_types.h"
31 #include "DNA_mesh_types.h"
32 #include "DNA_meshdata_types.h"
33 #include "DNA_modifier_types.h"
34 #include "DNA_object_types.h"
35 #include "DNA_scene_types.h"
36 #include "DNA_space_types.h"
37 #include "DNA_texture_types.h"
38
39 #include "BKE_animsys.h"
40 #include "BKE_bvhutils.h"       /* bvh tree     */
41 #include "BKE_blender.h"
42 #include "BKE_cdderivedmesh.h"
43 #include "BKE_constraint.h"
44 #include "BKE_context.h"
45 #include "BKE_customdata.h"
46 #include "BKE_colortools.h"
47 #include "BKE_deform.h"
48 #include "BKE_depsgraph.h"
49 #include "BKE_DerivedMesh.h"
50 #include "BKE_dynamicpaint.h"
51 #include "BKE_effect.h"
52 #include "BKE_global.h"
53 #include "BKE_image.h"
54 #include "BKE_main.h"
55 #include "BKE_material.h"
56 #include "BKE_modifier.h"
57 #include "BKE_object.h"
58 #include "BKE_particle.h"
59 #include "BKE_pointcache.h"
60 #include "BKE_scene.h"
61 #include "BKE_texture.h"
62
63 #include "RNA_access.h"
64 #include "RNA_define.h"
65 #include "RNA_enum_types.h"
66
67 /* for image output     */
68 #include "IMB_imbuf_types.h"
69 #include "IMB_imbuf.h"
70
71 /* to read material/texture color       */
72 #include "RE_render_ext.h"
73 #include "RE_shader_ext.h"
74
75 #ifdef _OPENMP
76 #include <omp.h>
77 #endif
78
79 /* precalculated gaussian factors for 5x super sampling */
80 static float gaussianFactors[5] = {     0.996849f,
81                                                                 0.596145f,
82                                                                 0.596145f,
83                                                                 0.596145f,
84                                                                 0.524141f};
85 static float gaussianTotal = 3.309425f;
86
87 /* UV Image neighboring pixel table x and y list */
88 static int neighX[8] = {1,1,0,-1,-1,-1, 0, 1};
89 static int neighY[8] = {0,1,1, 1, 0,-1,-1,-1};
90
91 /* subframe_updateObject() flags */
92 #define UPDATE_PARENTS (1<<0)
93 #define UPDATE_MESH (1<<1)
94 #define UPDATE_EVERYTHING (UPDATE_PARENTS|UPDATE_MESH)
95 /* surface_getBrushFlags() return vals */
96 #define BRUSH_USES_VELOCITY (1<<0)
97 /* brush mesh raycast status */
98 #define HIT_VOLUME 1
99 #define HIT_PROXIMITY 2
100 /* dynamicPaint_findNeighbourPixel() return codes */
101 #define NOT_FOUND -1
102 #define ON_MESH_EDGE -2
103 #define OUT_OF_TEXTURE -3
104 /* paint effect default movement per frame in global units */
105 #define EFF_MOVEMENT_PER_FRAME 0.05f
106 /* initial wave time factor */
107 #define WAVE_TIME_FAC (1.0f/24.f)
108 #define CANVAS_REL_SIZE 5.0f
109 /* drying limits */
110 #define MIN_WETNESS 0.001f
111 #define MAX_WETNESS 5.0f
112 /* dissolve macro */
113 #define VALUE_DISSOLVE(VALUE, TIME, SCALE, LOG) (VALUE) = (LOG) ? (VALUE) * (pow(MIN_WETNESS,1.0f/(1.2f*((float)(TIME))/(SCALE)))) : (VALUE) - 1.0f/(TIME)*(SCALE)
114
115 /***************************** Internal Structs ***************************/
116
117 typedef struct Bounds2D {
118         float min[2], max[2];
119 } Bounds2D;
120
121 typedef struct Bounds3D {
122         int valid;
123         float min[3], max[3];
124 } Bounds3D;
125
126 typedef struct VolumeGrid {
127         int dim[3];
128         Bounds3D grid_bounds; /* whole grid bounds */
129
130         Bounds3D *bounds;       /* (x*y*z) precalculated grid cell bounds */
131         int *s_pos; /* (x*y*z) t_index begin id */
132         int *s_num; /* (x*y*z) number of t_index points */
133         int *t_index; /* actual surface point index,
134                                                    access: (s_pos+s_num) */
135 } VolumeGrid;
136
137 typedef struct Vec3f {
138         float v[3];
139 } Vec3f;
140
141 typedef struct BakeAdjPoint {
142         float dir[3];   /* vector pointing towards this neighbor */
143         float dist;             /* distance to */
144 } BakeAdjPoint;
145
146 /* Surface data used while processing a frame   */
147 typedef struct PaintBakeNormal {
148         float invNorm[3];  /* current pixel world-space inverted normal */
149         float normal_scale; /* normal directional scale for displace mapping */
150 } PaintBakeNormal;
151
152 /* Temp surface data used to process a frame */
153 typedef struct PaintBakeData {
154         /* point space data */
155         PaintBakeNormal *bNormal;
156         int *s_pos;     /* index to start reading point sample realCoord */
157         int *s_num;     /* num of realCoord samples */
158         Vec3f *realCoord;  /* current pixel center world-space coordinates for each sample
159                             *  ordered as (s_pos+s_num)*/
160         Bounds3D mesh_bounds;
161
162         /* adjacency info */
163         BakeAdjPoint *bNeighs; /* current global neighbor distances and directions, if required */
164         double average_dist;
165         /* space partitioning */
166         VolumeGrid *grid;               /* space partitioning grid to optimize brush checks */
167
168         /* velocity and movement */
169         Vec3f *velocity;                /* speed vector in global space movement per frame, if required */
170         Vec3f *prev_velocity;
171         float *brush_velocity;  /* special temp data for post-p velocity based brushes like smudge
172                                                         *  3 float dir vec + 1 float str */
173         MVert *prev_verts;              /* copy of previous frame vertices. used to observe surface movement */
174         float prev_obmat[4][4]; /* previous frame object matrix */
175         int clear;                              /* flag to check if surface was cleared/reset -> have to redo velocity etc. */
176
177 } PaintBakeData;
178
179 /* UV Image sequence format point       */
180 typedef struct PaintUVPoint {
181         /* Pixel / mesh data */
182         unsigned int face_index, pixel_index;   /* face index on domain derived mesh */
183         unsigned int v1, v2, v3;                                /* vertex indexes */
184
185         unsigned int neighbour_pixel;   /* If this pixel isn't uv mapped to any face,
186                                                                            but it's neighboring pixel is */
187         short quad;
188 } PaintUVPoint;
189
190 typedef struct ImgSeqFormatData {
191         PaintUVPoint *uv_p;
192         Vec3f *barycentricWeights;              /* b-weights for all pixel samples */
193 } ImgSeqFormatData;
194
195 /* adjacency data flags */
196 #define ADJ_ON_MESH_EDGE (1<<0)
197
198 typedef struct PaintAdjData {
199         int *n_target;          /* array of neighboring point indexes,
200                                                                for single sample use (n_index+neigh_num) */
201         int *n_index;           /* index to start reading n_target for each point */
202         int *n_num;             /* num of neighs for each point */
203         int *flags;             /* vertex adjacency flags */
204         int total_targets; /* size of n_target */
205 } PaintAdjData;
206
207 /***************************** General Utils ******************************/
208
209 /* Set canvas error string to display at the bake report */
210 static int setError(DynamicPaintCanvasSettings *canvas, const char *string)
211 {
212         /* Add error to canvas ui info label */
213         BLI_strncpy(canvas->error, string, sizeof(canvas->error));
214         return 0;
215 }
216
217 /* Get number of surface points for cached types */
218 static int dynamicPaint_surfaceNumOfPoints(DynamicPaintSurface *surface)
219 {
220         if (surface->format == MOD_DPAINT_SURFACE_F_PTEX) {
221                 return 0; /* not supported atm */
222         }
223         else if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
224                 if (!surface->canvas->dm) return 0; /* invalid derived mesh */
225                 return surface->canvas->dm->getNumVerts(surface->canvas->dm);
226         }
227         else
228                 return 0;
229 }
230
231 /* checks whether surface's format/type has realtime preview */
232 int dynamicPaint_surfaceHasColorPreview(DynamicPaintSurface *surface)
233 {
234         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) return 0;
235         else if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
236                 if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE ||
237                         surface->type == MOD_DPAINT_SURFACE_T_WAVE) return 0;
238                 else return 1;
239         }
240         else return 1;
241 }
242
243 /* get currently active surface (in user interface) */
244 struct DynamicPaintSurface *get_activeSurface(DynamicPaintCanvasSettings *canvas)
245 {
246         DynamicPaintSurface *surface = canvas->surfaces.first;
247         int i;
248
249         for(i=0; surface; surface=surface->next) {
250                 if(i == canvas->active_sur)
251                         return surface;
252                 i++;
253         }
254         return NULL;
255 }
256
257 /* set preview to first previewable surface */
258 void dynamicPaint_resetPreview(DynamicPaintCanvasSettings *canvas)
259 {
260         DynamicPaintSurface *surface = canvas->surfaces.first;
261         int done=0;
262
263         for(; surface; surface=surface->next) {
264                 if (!done && dynamicPaint_surfaceHasColorPreview(surface)) {
265                         surface->flags |= MOD_DPAINT_PREVIEW;
266                         done=1;
267                 }
268                 else
269                         surface->flags &= ~MOD_DPAINT_PREVIEW;
270         }
271 }
272
273 /* set preview to defined surface */
274 static void dynamicPaint_setPreview(DynamicPaintSurface *t_surface)
275 {
276         DynamicPaintSurface *surface = t_surface->canvas->surfaces.first;
277         for(; surface; surface=surface->next) {
278                 if (surface == t_surface)
279                         surface->flags |= MOD_DPAINT_PREVIEW;
280                 else
281                         surface->flags &= ~MOD_DPAINT_PREVIEW;
282         }
283 }
284
285 int dynamicPaint_outputLayerExists(struct DynamicPaintSurface *surface, Object *ob, int output)
286 {
287         char *name;
288
289         if (output == 0)
290                 name = surface->output_name;
291         else if (output == 1)
292                 name = surface->output_name2;
293         else
294                 return 0;
295
296         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
297                 if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
298                         Mesh *me = ob->data;
299                         return (CustomData_get_named_layer_index(&me->fdata, CD_MCOL, name) != -1);
300                 }
301                 else if (surface->type == MOD_DPAINT_SURFACE_T_WEIGHT)
302                         return (defgroup_name_index(ob, surface->output_name) != -1);
303         }
304
305         return 0;
306 }
307
308 static int surface_duplicateOutputExists(void *arg, const char *name)
309 {
310         DynamicPaintSurface *t_surface = (DynamicPaintSurface*)arg;
311         DynamicPaintSurface *surface = t_surface->canvas->surfaces.first;
312
313         for(; surface; surface=surface->next) {
314                 if (surface!=t_surface && surface->type==t_surface->type &&
315                         surface->format==t_surface->format) {
316                         if (surface->output_name[0]!='\0' && !BLI_path_cmp(name, surface->output_name)) return 1;
317                         if (surface->output_name2[0]!='\0' && !BLI_path_cmp(name, surface->output_name2)) return 1;
318                 }
319         }
320         return 0;
321 }
322
323 static void surface_setUniqueOutputName(DynamicPaintSurface *surface, char *basename, int output)
324 {
325         char name[64];
326         BLI_strncpy(name, basename, sizeof(name)); /* in case basename is surface->name use a copy */
327         if (!output)
328                 BLI_uniquename_cb(surface_duplicateOutputExists, surface, name, '.', surface->output_name, sizeof(surface->output_name));
329         if (output)
330                 BLI_uniquename_cb(surface_duplicateOutputExists, surface, name, '.', surface->output_name2, sizeof(surface->output_name2));
331 }
332
333
334 static int surface_duplicateNameExists(void *arg, const char *name)
335 {
336         DynamicPaintSurface *t_surface = (DynamicPaintSurface*)arg;
337         DynamicPaintSurface *surface = t_surface->canvas->surfaces.first;
338
339         for(; surface; surface=surface->next) {
340                 if (surface!=t_surface && !strcmp(name, surface->name)) return 1;
341         }
342         return 0;
343 }
344
345 void dynamicPaintSurface_setUniqueName(DynamicPaintSurface *surface, const char *basename)
346 {
347         char name[64];
348         BLI_strncpy(name, basename, sizeof(name)); /* in case basename is surface->name use a copy */
349         BLI_uniquename_cb(surface_duplicateNameExists, surface, name, '.', surface->name, sizeof(surface->name));
350 }
351
352
353 /* change surface data to defaults on new type */
354 void dynamicPaintSurface_updateType(struct DynamicPaintSurface *surface)
355 {
356         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
357                 surface->output_name[0]='\0';
358                 surface->output_name2[0]='\0';
359                 surface->flags |= MOD_DPAINT_ANTIALIAS;
360                 surface->depth_clamp = 1.0f;
361         }
362         else {
363                 strcpy(surface->output_name, "dp_");
364                 strcpy(surface->output_name2, surface->output_name);
365                 surface->flags &= ~MOD_DPAINT_ANTIALIAS;
366                 surface->depth_clamp = 0.0f;
367         }
368
369         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
370                 strcat(surface->output_name,"paintmap");
371                 strcat(surface->output_name2,"wetmap");
372                 surface_setUniqueOutputName(surface, surface->output_name2, 1);
373         }
374         else if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE) {
375                 strcat(surface->output_name,"displace");
376         }
377         else if (surface->type == MOD_DPAINT_SURFACE_T_WEIGHT) {
378                 strcat(surface->output_name,"weight");
379         }
380         else if (surface->type == MOD_DPAINT_SURFACE_T_WAVE) {
381                 strcat(surface->output_name,"wave");
382         }
383
384         surface_setUniqueOutputName(surface, surface->output_name, 0);
385
386         /* update preview */
387         if (dynamicPaint_surfaceHasColorPreview(surface))
388                 dynamicPaint_setPreview(surface);
389         else
390                 dynamicPaint_resetPreview(surface->canvas);
391 }
392
393 static int surface_totalSamples(DynamicPaintSurface *surface)
394 {
395         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ &&
396                 surface->flags & MOD_DPAINT_ANTIALIAS)
397                 return (surface->data->total_points*5);
398         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX &&
399                 surface->flags & MOD_DPAINT_ANTIALIAS && surface->data->adj_data)
400                 return (surface->data->total_points+surface->data->adj_data->total_targets);
401
402         return surface->data->total_points;
403 }
404
405 static void blendColors(float t_color[3], float t_alpha, float s_color[3], float s_alpha, float result[4])
406 {
407         int i;
408         float i_alpha = 1.0f - s_alpha;
409         float f_alpha = t_alpha*i_alpha + s_alpha;
410
411         /* blend colors */
412         if (f_alpha) {
413                 for (i=0; i<3; i++) {
414                         result[i] = (t_color[i]*t_alpha*i_alpha + s_color[i]*s_alpha)/f_alpha;
415                 }
416         }
417         else {
418                 copy_v3_v3(result, t_color);
419         }
420         /* return final alpha */
421         result[3] = f_alpha;
422 }
423
424 /* Mix two alpha weighed colors by a defined ratio. output is saved at a_color */
425 static float mixColors(float a_color[3], float a_weight, float b_color[3], float b_weight, float ratio)
426 {
427         float weight_ratio, factor;
428         if (b_weight) {
429                 /* if first value has no weight just use b_color */
430                 if (!a_weight) {
431                         copy_v3_v3(a_color, b_color);
432                         return b_weight*ratio;
433                 }
434                 weight_ratio = b_weight/(a_weight+b_weight);
435         }
436         else return a_weight*(1.0f-ratio);
437
438         /* calculate final interpolation factor */
439         if (ratio<=0.5f) {
440                 factor = weight_ratio*(ratio*2.0f);
441         }
442         else {
443                 ratio = (ratio*2.0f - 1.0f);
444                 factor = weight_ratio*(1.0f-ratio) + ratio;
445         }
446         /* mix final color */
447         interp_v3_v3v3(a_color, a_color, b_color, factor);
448         return (1.0f-factor)*a_weight + factor*b_weight;
449 }
450
451 /* set "ignore cache" flag for all caches on this object */
452 static void object_cacheIgnoreClear(Object *ob, int state)
453 {
454         ListBase pidlist;
455         PTCacheID *pid;
456         BKE_ptcache_ids_from_object(&pidlist, ob, NULL, 0);
457
458         for(pid=pidlist.first; pid; pid=pid->next) {
459                 if(pid->cache) {
460                         if (state)
461                                 pid->cache->flag |= PTCACHE_IGNORE_CLEAR;
462                         else
463                                 pid->cache->flag &= ~PTCACHE_IGNORE_CLEAR;
464                 }
465         }
466
467         BLI_freelistN(&pidlist);
468 }
469
470 static int subframe_updateObject(Scene *scene, Object *ob, int flags, float frame)
471 {
472         DynamicPaintModifierData *pmd = (DynamicPaintModifierData *)modifiers_findByType(ob, eModifierType_DynamicPaint);
473         bConstraint *con;
474
475         /* if other is dynamic paint canvas, dont update */
476         if (pmd && pmd->canvas)
477                 return 1;
478
479         /* if object has parents, update them too */
480         if (flags & UPDATE_PARENTS) {
481                 int is_canvas = 0;
482                 if (ob->parent) is_canvas += subframe_updateObject(scene, ob->parent, 0, frame);
483                 if (ob->track) is_canvas += subframe_updateObject(scene, ob->track, 0, frame);
484
485                 /* skip subframe if object is parented
486                 *  to vertex of a dynamic paint canvas */
487                 if (is_canvas && (ob->partype == PARVERT1 || ob->partype == PARVERT3))
488                         return 0;
489
490                 /* also update constraint targets */
491                 for (con = ob->constraints.first; con; con=con->next) {
492                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
493                         ListBase targets = {NULL, NULL};
494
495                         if (cti && cti->get_constraint_targets) {
496                                 bConstraintTarget *ct;
497                                 cti->get_constraint_targets(con, &targets);
498                                 for (ct= targets.first; ct; ct= ct->next) {
499                                         if (ct->tar)
500                                                 subframe_updateObject(scene, ct->tar, 0, frame);
501                                 }
502                                 /* free temp targets */
503                                 if (cti->flush_constraint_targets)
504                                         cti->flush_constraint_targets(con, &targets, 0);
505                         }
506                 }
507         }
508         /* for curve following objects, parented curve has to be updated too */
509         if(ob->type==OB_CURVE) {
510                 Curve *cu= ob->data;
511                 BKE_animsys_evaluate_animdata(scene, &cu->id, cu->adt, frame, ADT_RECALC_ANIM);
512         }
513
514         ob->recalc |= OB_RECALC_ALL;
515         BKE_animsys_evaluate_animdata(scene, &ob->id, ob->adt, frame, ADT_RECALC_ANIM);
516         if (flags & UPDATE_MESH) {
517                 /* ignore cache clear during subframe updates
518                 *  to not mess up cache validity */
519                 object_cacheIgnoreClear(ob, 1);
520                 object_handle_update(scene, ob);
521                 object_cacheIgnoreClear(ob, 0);
522         }
523         else
524                 where_is_object_time(scene, ob, frame);
525
526         return 0;
527 }
528
529 static void scene_setSubframe(Scene *scene, float subframe)
530 {
531         /* dynamic paint subframes must be done on previous frame */
532         scene->r.cfra -= 1;
533         scene->r.subframe = subframe;
534 }
535
536 static int surface_getBrushFlags(DynamicPaintSurface *surface, Scene *scene)
537 {
538         Base *base = NULL;
539         GroupObject *go = NULL; 
540         Object *brushObj = NULL;
541         ModifierData *md = NULL;
542
543         int flags = 0;
544
545         if(surface->brush_group)
546                 go = surface->brush_group->gobject.first;
547         else
548                 base = scene->base.first;
549
550         while (base || go)
551         {
552                 brushObj = NULL;
553
554                 /* select object */
555                 if(surface->brush_group) {                                              
556                         if(go->ob)      brushObj = go->ob;                                      
557                 }                                       
558                 else                                            
559                         brushObj = base->object;
560
561                 if(!brushObj)                                   
562                 {
563                         if(surface->brush_group) go = go->next;
564                         else base= base->next;                                  
565                         continue;                       
566                 }
567
568                 if(surface->brush_group)
569                         go = go->next;
570                 else
571                         base= base->next;
572
573                 md = modifiers_findByType(brushObj, eModifierType_DynamicPaint);
574                 if(md && md->mode & (eModifierMode_Realtime | eModifierMode_Render))                                    
575                 {
576                         DynamicPaintModifierData *pmd2 = (DynamicPaintModifierData *)md;
577
578                         if (pmd2->brush)
579                         {
580                                 DynamicPaintBrushSettings *brush = pmd2->brush;
581
582                                 if (brush->flags & MOD_DPAINT_USES_VELOCITY)
583                                         flags |= BRUSH_USES_VELOCITY;
584                         }
585                 }
586         }
587
588         return flags;
589 }
590
591 static int brush_usesMaterial(DynamicPaintBrushSettings *brush, Scene *scene)
592 {
593         return ((brush->flags & MOD_DPAINT_USE_MATERIAL) && (!strcmp(scene->r.engine, "BLENDER_RENDER")));
594 }
595
596 /* check whether two bounds intersect */
597 static int boundsIntersect(Bounds3D *b1, Bounds3D *b2)
598 {
599         int i=2;
600         if (!b1->valid || !b2->valid) return 0;
601         for (; i>=0; i-=1)
602                 if (!(b1->min[i] <= b2->max[i] && b1->max[i] >= b2->min[i])) return 0;
603         return 1;
604 }
605
606 /* check whether two bounds intersect inside defined proximity */
607 static int boundsIntersectDist(Bounds3D *b1, Bounds3D *b2, float dist)
608 {
609         int i=2;
610         if (!b1->valid || !b2->valid) return 0;
611         for (; i>=0; i-=1)
612                 if (!(b1->min[i] <= (b2->max[i]+dist) && b1->max[i] >= (b2->min[i]-dist))) return 0;
613         return 1;
614 }
615
616 /* check whether bounds intersects a point with given radius */
617 static int boundIntersectPoint(Bounds3D *b, float point[3], float radius)
618 {
619         int i=2;
620         if (!b->valid) return 0;
621         for (; i>=0; i-=1)
622                 if (!(b->min[i] <= (point[i]+radius) && b->max[i] >= (point[i]-radius))) return 0;
623         return 1;
624 }
625
626 /* expand bounds by a new point */
627 static void boundInsert(Bounds3D *b, float point[3])
628 {
629         int i=2;
630         if (!b->valid) {
631                 copy_v3_v3(b->min, point);
632                 copy_v3_v3(b->max, point);
633                 b->valid = 1;
634         }
635         else {
636                 for (; i>=0; i-=1) {
637                         if (point[i] < b->min[i]) b->min[i]=point[i];
638                         if (point[i] > b->max[i]) b->max[i]=point[i];
639                 }
640         }
641 }
642
643 float getSurfaceDimension(PaintSurfaceData *sData)
644 {
645         Bounds3D *mb = &sData->bData->mesh_bounds;
646         return MAX3((mb->max[0]-mb->min[0]), (mb->max[1]-mb->min[1]), (mb->max[2]-mb->min[2]));
647 }
648
649 static void freeGrid(PaintSurfaceData *data)
650 {
651         PaintBakeData *bData = data->bData;
652         VolumeGrid *grid = bData->grid;
653
654         if (grid->bounds) MEM_freeN(grid->bounds);
655         if (grid->s_pos) MEM_freeN(grid->s_pos);
656         if (grid->s_num) MEM_freeN(grid->s_num);
657         if (grid->t_index) MEM_freeN(grid->t_index);
658
659         MEM_freeN(bData->grid);
660         bData->grid = NULL;
661 }
662
663 static void surfaceGenerateGrid(struct DynamicPaintSurface *surface)
664 {
665         PaintSurfaceData *sData = surface->data;
666         PaintBakeData *bData = sData->bData;
667         Bounds3D *grid_bounds;
668         VolumeGrid *grid;
669         int grid_cells, axis = 3;
670         int *temp_t_index = NULL;
671         int *temp_s_num = NULL;
672
673 #ifdef _OPENMP
674         int num_of_threads = omp_get_max_threads();
675 #else
676         int num_of_threads = 1;
677 #endif
678
679         if (bData->grid)
680                 freeGrid(sData);
681
682         /* allocate separate bounds for each thread */
683         grid_bounds = MEM_callocN(sizeof(Bounds3D)*num_of_threads, "Grid Bounds");
684         bData->grid = MEM_callocN(sizeof(VolumeGrid), "Surface Grid");
685         grid = bData->grid;
686
687         if (grid && grid_bounds) {
688                 int i, error = 0;
689                 float dim_factor, volume, dim[3];
690                 float td[3];
691                 float min_dim;
692
693                 /* calculate canvas dimensions */
694                 #pragma omp parallel for schedule(static)
695                 for (i=0; i<sData->total_points; i++) {
696                         #ifdef _OPENMP
697                         int id = omp_get_thread_num();
698                         boundInsert(&grid_bounds[id], (bData->realCoord[bData->s_pos[i]].v));
699                         #else
700                         boundInsert(&grid_bounds[0], (bData->realCoord[bData->s_pos[i]].v));
701                         #endif
702                 }
703
704                 /* get final dimensions */
705                 for (i=0; i<num_of_threads; i++) {
706                         boundInsert(&grid->grid_bounds, grid_bounds[i].min);
707                         boundInsert(&grid->grid_bounds, grid_bounds[i].max);
708                 }
709
710                 /* get dimensions */
711                 sub_v3_v3v3(dim, grid->grid_bounds.max, grid->grid_bounds.min);
712                 copy_v3_v3(td, dim);
713                 min_dim = MAX3(td[0],td[1],td[2]) / 1000.f;
714
715                 /* deactivate zero axises */
716                 for (i=0; i<3; i++) {
717                         if (td[i]<min_dim) {td[i]=1.0f; axis-=1;}
718                 }
719
720                 if (axis == 0 || MAX3(td[0],td[1],td[2]) < 0.0001f) {
721                         MEM_freeN(grid_bounds);
722                         MEM_freeN(bData->grid);
723                         bData->grid = NULL;
724                         return;
725                 }
726
727                 /* now calculate grid volume/area/width depending on num of active axis */
728                 volume = td[0]*td[1]*td[2];
729
730                 /* determine final grid size by trying to fit average 10.000 points per grid cell */
731                 dim_factor = (float)pow(volume / ((double)sData->total_points / 10000.0), 1.0/(double)axis);
732
733                 /* define final grid size using dim_factor, use min 3 for active axises */
734                 for (i=0; i<3; i++) {
735                         grid->dim[i] = (int)floor(td[i] / dim_factor);
736                         CLAMP(grid->dim[i], (dim[i]>=min_dim) ? 3 : 1, 100);
737                 }
738                 grid_cells = grid->dim[0]*grid->dim[1]*grid->dim[2];
739
740                 /* allocate memory for grids */
741                 grid->bounds = MEM_callocN(sizeof(Bounds3D) * grid_cells, "Surface Grid Bounds");
742                 grid->s_pos = MEM_callocN(sizeof(int) * grid_cells, "Surface Grid Position");
743                 grid->s_num = MEM_callocN(sizeof(int) * grid_cells*num_of_threads, "Surface Grid Points");
744                 temp_s_num = MEM_callocN(sizeof(int) * grid_cells, "Temp Surface Grid Points");
745                 grid->t_index = MEM_callocN(sizeof(int) * sData->total_points, "Surface Grid Target Ids");
746                 temp_t_index = MEM_callocN(sizeof(int) * sData->total_points, "Temp Surface Grid Target Ids");
747
748                 /* in case of an allocation failure abort here */
749                 if (!grid->bounds || !grid->s_pos || !grid->s_num || !grid->t_index || !temp_s_num || !temp_t_index)
750                         error = 1;
751
752                 if (!error) {
753                         /* calculate number of points withing each cell */
754                         #pragma omp parallel for schedule(static)
755                         for (i=0; i<sData->total_points; i++) {
756                                 int co[3], j;
757                                 for (j=0; j<3; j++) {
758                                         co[j] = (int)floor((bData->realCoord[bData->s_pos[i]].v[j] - grid->grid_bounds.min[j])/dim[j]*grid->dim[j]);
759                                         CLAMP(co[j], 0, grid->dim[j]-1);
760                                 }
761
762                                 temp_t_index[i] = co[0] + co[1] * grid->dim[0] + co[2] * grid->dim[0]*grid->dim[1];
763                                 #ifdef _OPENMP
764                                 grid->s_num[temp_t_index[i]+omp_get_thread_num()*grid_cells]++;
765                                 #else
766                                 grid->s_num[temp_t_index[i]]++;
767                                 #endif
768                         }
769
770                         /* for first cell only calc s_num */
771                         for (i=1; i<num_of_threads; i++) {
772                                 grid->s_num[0] += grid->s_num[i*grid_cells];
773                         }
774
775                         /* calculate grid indexes */
776                         for (i=1; i<grid_cells; i++) {
777                                 int id;
778                                 for (id=1; id<num_of_threads; id++) {
779                                         grid->s_num[i] += grid->s_num[i+id*grid_cells];
780                                 }
781                                 grid->s_pos[i] = grid->s_pos[i-1] + grid->s_num[i-1];
782                         }
783
784                         /* save point indexes to final array */
785                         for (i=0; i<sData->total_points; i++) {
786                                 int pos = grid->s_pos[temp_t_index[i]] + temp_s_num[temp_t_index[i]];
787                                 grid->t_index[pos] = i;
788
789                                 temp_s_num[temp_t_index[i]]++;
790                         }
791
792                         /* calculate cell bounds */
793                         {
794                                 int x;
795                                 #pragma omp parallel for schedule(static)
796                                 for (x=0; x<grid->dim[0]; x++) {
797                                         int y;
798                                         for (y=0; y<grid->dim[1]; y++) {
799                                                 int z;
800                                                 for (z=0; z<grid->dim[2]; z++) {
801                                                         int j, b_index = x + y * grid->dim[0] + z * grid->dim[0]*grid->dim[1];
802                                                         /* set bounds */
803                                                         for (j=0; j<3; j++) {
804                                                                 int s = (j==0) ? x : ((j==1) ? y : z);
805                                                                 grid->bounds[b_index].min[j] = grid->grid_bounds.min[j] + dim[j]/grid->dim[j]*s;
806                                                                 grid->bounds[b_index].max[j] = grid->grid_bounds.min[j] + dim[j]/grid->dim[j]*(s+1);
807                                                         }
808                                                         grid->bounds[b_index].valid = 1;
809                                                 }
810                                         }
811                                 }
812                         }
813                 }
814
815                 if (temp_s_num) MEM_freeN(temp_s_num);
816                 if (temp_t_index) MEM_freeN(temp_t_index);
817
818                 /* free per thread s_num values */
819                 grid->s_num = MEM_reallocN(grid->s_num, sizeof(int) * grid_cells);
820
821                 if (error || !grid->s_num) {
822                         setError(surface->canvas, "Not enough free memory.");
823                         freeGrid(sData);
824                 }
825         }
826
827         if (grid_bounds) MEM_freeN(grid_bounds);
828 }
829
830 /***************************** Freeing data ******************************/
831
832 /* Free brush data */
833 void dynamicPaint_freeBrush(struct DynamicPaintModifierData *pmd)
834 {
835         if(pmd->brush) {
836                 if(pmd->brush->dm)
837                         pmd->brush->dm->release(pmd->brush->dm);
838                 pmd->brush->dm = NULL;
839
840                 if(pmd->brush->paint_ramp)
841                          MEM_freeN(pmd->brush->paint_ramp);
842                 pmd->brush->paint_ramp = NULL;
843                 if(pmd->brush->vel_ramp)
844                          MEM_freeN(pmd->brush->vel_ramp);
845                 pmd->brush->vel_ramp = NULL;
846
847                 MEM_freeN(pmd->brush);
848                 pmd->brush = NULL;
849         }
850 }
851
852 static void dynamicPaint_freeAdjData(PaintSurfaceData *data)
853 {
854         if (data->adj_data) {
855                 if (data->adj_data->n_index) MEM_freeN(data->adj_data->n_index);
856                 if (data->adj_data->n_num) MEM_freeN(data->adj_data->n_num);
857                 if (data->adj_data->n_target) MEM_freeN(data->adj_data->n_target);
858                 if (data->adj_data->flags) MEM_freeN(data->adj_data->flags);
859                 MEM_freeN(data->adj_data);
860                 data->adj_data = NULL;
861         }
862 }
863
864 static void free_bakeData(PaintSurfaceData *data)
865 {
866         PaintBakeData *bData = data->bData;
867         if (bData) {
868                 if (bData->bNormal) MEM_freeN(bData->bNormal);
869                 if (bData->s_pos) MEM_freeN(bData->s_pos);
870                 if (bData->s_num) MEM_freeN(bData->s_num);
871                 if (bData->realCoord) MEM_freeN(bData->realCoord);
872                 if (bData->bNeighs) MEM_freeN(bData->bNeighs);
873                 if (bData->grid) freeGrid(data);
874                 if (bData->prev_verts) MEM_freeN(bData->prev_verts);
875                 if (bData->velocity) MEM_freeN(bData->velocity);
876                 if (bData->prev_velocity) MEM_freeN(bData->prev_velocity);
877
878                 MEM_freeN(data->bData);
879                 data->bData = NULL;
880         }
881 }
882
883 /* free surface data if it's not used anymore */
884 void surface_freeUnusedData(DynamicPaintSurface *surface)
885 {
886         if (!surface->data) return;
887
888         /* free bakedata if not active or surface is baked */
889         if (!(surface->flags & MOD_DPAINT_ACTIVE) ||
890                 (surface->pointcache && surface->pointcache->flag & PTCACHE_BAKED))
891                 free_bakeData(surface->data);
892 }
893
894 void dynamicPaint_freeSurfaceData(DynamicPaintSurface *surface)
895 {
896         PaintSurfaceData *data = surface->data;
897         if (!data) return;
898         if (data->format_data) {
899                 /* format specific free */
900                 if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
901                         ImgSeqFormatData *format_data = (ImgSeqFormatData*)data->format_data;
902                         if (format_data->uv_p)
903                                 MEM_freeN(format_data->uv_p);
904                         if (format_data->barycentricWeights)
905                                 MEM_freeN(format_data->barycentricWeights);
906                 }
907                 MEM_freeN(data->format_data);
908         }
909         /* type data */
910         if (data->type_data) MEM_freeN(data->type_data);
911         dynamicPaint_freeAdjData(data);
912         /* bake data */
913         free_bakeData(data);
914
915         MEM_freeN(surface->data);
916         surface->data = NULL;
917 }
918
919 void dynamicPaint_freeSurface(DynamicPaintSurface *surface)
920 {
921         /* point cache */
922         BKE_ptcache_free_list(&(surface->ptcaches));
923         surface->pointcache = NULL;
924
925         if(surface->effector_weights)
926                 MEM_freeN(surface->effector_weights);
927         surface->effector_weights = NULL;
928
929         BLI_remlink(&(surface->canvas->surfaces), surface);
930         dynamicPaint_freeSurfaceData(surface);
931         MEM_freeN(surface);
932 }
933
934 /* Free canvas data */
935 void dynamicPaint_freeCanvas(DynamicPaintModifierData *pmd)
936 {
937         if(pmd->canvas) {
938                 /* Free surface data */
939                 DynamicPaintSurface *surface = pmd->canvas->surfaces.first;
940                 DynamicPaintSurface *next_surface = NULL;
941
942                 while (surface) {
943                         next_surface = surface->next;
944                         dynamicPaint_freeSurface(surface);
945                         surface = next_surface;
946                 }
947
948                 /* free dm copy */
949                 if (pmd->canvas->dm)
950                         pmd->canvas->dm->release(pmd->canvas->dm);
951                 pmd->canvas->dm = NULL;
952
953                 MEM_freeN(pmd->canvas);
954                 pmd->canvas = NULL;
955         }
956 }
957
958 /* Free whole dp modifier */
959 void dynamicPaint_Modifier_free(struct DynamicPaintModifierData *pmd)
960 {
961         if(pmd) {
962                 dynamicPaint_freeCanvas(pmd);
963                 dynamicPaint_freeBrush(pmd);
964         }
965 }
966
967
968 /***************************** Initialize and reset ******************************/
969
970 /*
971 *       Creates a new surface and adds it to the list
972 *       If scene is null, frame range of 1-250 is used
973 *       A pointer to this surface is returned
974 */
975 struct DynamicPaintSurface *dynamicPaint_createNewSurface(DynamicPaintCanvasSettings *canvas, Scene *scene)
976 {
977         DynamicPaintSurface *surface= MEM_callocN(sizeof(DynamicPaintSurface), "DynamicPaintSurface");
978         if (!surface) return NULL;
979
980         surface->canvas = canvas;
981         surface->format = MOD_DPAINT_SURFACE_F_VERTEX;
982         surface->type = MOD_DPAINT_SURFACE_T_PAINT;
983
984         /* cache */
985         surface->pointcache = BKE_ptcache_add(&(surface->ptcaches));
986         surface->pointcache->flag |= PTCACHE_DISK_CACHE;
987         surface->pointcache->step = 1;
988
989         /* Set initial values */
990         surface->flags = MOD_DPAINT_ANTIALIAS | MOD_DPAINT_MULALPHA | MOD_DPAINT_DRY_LOG | MOD_DPAINT_DISSOLVE_LOG |
991                                          MOD_DPAINT_ACTIVE | MOD_DPAINT_PREVIEW | MOD_DPAINT_OUT1 | MOD_DPAINT_USE_DRYING;
992         surface->effect = 0;
993         surface->effect_ui = 1;
994
995         surface->diss_speed = 250;
996         surface->dry_speed = 500;
997         surface->color_dry_threshold = 1.0f;
998         surface->depth_clamp = 0.0f;
999         surface->disp_factor = 1.0f;
1000         surface->disp_type = MOD_DPAINT_DISP_DISPLACE;
1001         surface->image_fileformat = MOD_DPAINT_IMGFORMAT_PNG;
1002
1003         surface->influence_scale = 1.0f;
1004         surface->radius_scale = 1.0f;
1005
1006         surface->init_color[0] = 1.0f;
1007         surface->init_color[1] = 1.0f;
1008         surface->init_color[2] = 1.0f;
1009         surface->init_color[3] = 1.0f;
1010
1011         surface->image_resolution = 256;
1012         surface->substeps = 0;
1013
1014         if (scene) {
1015                 surface->start_frame = scene->r.sfra;
1016                 surface->end_frame = scene->r.efra;
1017         }
1018         else {
1019                 surface->start_frame = 1;
1020                 surface->end_frame = 250;
1021         }
1022
1023         surface->spread_speed = 1.0f;
1024         surface->color_spread_speed = 1.0f;
1025         surface->shrink_speed = 1.0f;
1026
1027         surface->wave_damping = 0.04f;
1028         surface->wave_speed = 1.0f;
1029         surface->wave_timescale = 1.0f;
1030         surface->wave_spring = 0.20f;
1031
1032         modifier_path_init(surface->image_output_path, sizeof(surface->image_output_path), "cache_dynamicpaint");
1033
1034         dynamicPaintSurface_setUniqueName(surface, "Surface");
1035
1036         surface->effector_weights = BKE_add_effector_weights(NULL);
1037
1038         dynamicPaintSurface_updateType(surface);
1039
1040         BLI_addtail(&canvas->surfaces, surface);
1041
1042         return surface;
1043 }
1044
1045 /*
1046 *       Initialize modifier data
1047 */
1048 int dynamicPaint_createType(struct DynamicPaintModifierData *pmd, int type, struct Scene *scene)
1049 {
1050         if(pmd) {
1051                 if(type == MOD_DYNAMICPAINT_TYPE_CANVAS) {
1052                         DynamicPaintCanvasSettings *canvas;
1053                         if(pmd->canvas)
1054                                 dynamicPaint_freeCanvas(pmd);
1055
1056                         canvas = pmd->canvas = MEM_callocN(sizeof(DynamicPaintCanvasSettings), "DynamicPaint Canvas");
1057                         if (!canvas)
1058                                 return 0;
1059                         canvas->pmd = pmd;
1060                         canvas->dm = NULL;
1061
1062                         /* Create one surface */
1063                         if (!dynamicPaint_createNewSurface(canvas, scene))
1064                                 return 0;
1065
1066                 }
1067                 else if(type == MOD_DYNAMICPAINT_TYPE_BRUSH) {
1068                         DynamicPaintBrushSettings *brush;
1069                         if(pmd->brush)
1070                                 dynamicPaint_freeBrush(pmd);
1071
1072                         brush = pmd->brush = MEM_callocN(sizeof(DynamicPaintBrushSettings), "DynamicPaint Paint");
1073                         if (!brush)
1074                                 return 0;
1075                         brush->pmd = pmd;
1076
1077                         brush->psys = NULL;
1078
1079                         brush->flags = MOD_DPAINT_ABS_ALPHA | MOD_DPAINT_RAMP_ALPHA;
1080                         brush->collision = MOD_DPAINT_COL_VOLUME;
1081                         
1082                         brush->mat = NULL;
1083                         brush->r = 0.15f;
1084                         brush->g = 0.4f;
1085                         brush->b = 0.8f;
1086                         brush->alpha = 1.0f;
1087                         brush->wetness = 1.0f;
1088
1089                         brush->paint_distance = 1.0f;
1090                         brush->proximity_falloff = MOD_DPAINT_PRFALL_SMOOTH;
1091
1092                         brush->particle_radius = 0.2f;
1093                         brush->particle_smooth = 0.05f;
1094
1095                         brush->wave_type = MOD_DPAINT_WAVEB_CHANGE;
1096                         brush->wave_factor = 1.0f;
1097                         brush->wave_clamp = 0.0f;
1098                         brush->smudge_strength = 0.3f;
1099                         brush->max_velocity = 1.0f;
1100
1101                         brush->dm = NULL;
1102
1103                         /* Paint proximity falloff colorramp. */
1104                         {
1105                                 CBData *ramp;
1106
1107                                 brush->paint_ramp = add_colorband(0);
1108                                 if (!brush->paint_ramp)
1109                                         return 0;
1110                                 ramp = brush->paint_ramp->data;
1111                                 /* Add default smooth-falloff ramp.     */
1112                                 ramp[0].r = ramp[0].g = ramp[0].b = ramp[0].a = 1.0f;
1113                                 ramp[0].pos = 0.0f;
1114                                 ramp[1].r = ramp[1].g = ramp[1].b = ramp[1].pos = 1.0f;
1115                                 ramp[1].a = 0.0f;
1116                                 pmd->brush->paint_ramp->tot = 2;
1117                         }
1118
1119                         /* Brush velocity ramp. */
1120                         {
1121                                 CBData *ramp;
1122
1123                                 brush->vel_ramp = add_colorband(0);
1124                                 if (!brush->vel_ramp)
1125                                         return 0;
1126                                 ramp = brush->vel_ramp->data;
1127                                 ramp[0].r = ramp[0].g = ramp[0].b = ramp[0].a = ramp[0].pos = 0.0f;
1128                                 ramp[1].r = ramp[1].g = ramp[1].b = ramp[1].a = ramp[1].pos = 1.0f;
1129                                 brush->paint_ramp->tot = 2;
1130                         }
1131                 }
1132         }
1133         else
1134                 return 0;
1135
1136         return 1;
1137 }
1138
1139 void dynamicPaint_Modifier_copy(struct DynamicPaintModifierData *pmd, struct DynamicPaintModifierData *tpmd)
1140 {
1141         /* Init modifier        */
1142         tpmd->type = pmd->type;
1143         if (pmd->canvas)
1144                 dynamicPaint_createType(tpmd, MOD_DYNAMICPAINT_TYPE_CANVAS, NULL);
1145         if (pmd->brush)
1146                 dynamicPaint_createType(tpmd, MOD_DYNAMICPAINT_TYPE_BRUSH, NULL);
1147
1148         /* Copy data    */
1149         if (tpmd->canvas) {
1150                 tpmd->canvas->pmd = tpmd;
1151
1152         } else if (tpmd->brush) {
1153                 DynamicPaintBrushSettings *brush = pmd->brush, *t_brush = tpmd->brush;
1154                 t_brush->pmd = tpmd;
1155
1156                 t_brush->flags = brush->flags;
1157                 t_brush->collision = brush->collision;
1158
1159                 t_brush->mat = brush->mat;
1160                 t_brush->r = brush->r;
1161                 t_brush->g = brush->g;
1162                 t_brush->b = brush->b;
1163                 t_brush->alpha = brush->alpha;
1164                 t_brush->wetness = brush->wetness;
1165
1166                 t_brush->particle_radius = brush->particle_radius;
1167                 t_brush->particle_smooth = brush->particle_smooth;
1168                 t_brush->paint_distance = brush->paint_distance;
1169                 t_brush->psys = brush->psys;
1170
1171                 if (brush->paint_ramp)
1172                         memcpy(t_brush->paint_ramp, brush->paint_ramp, sizeof(ColorBand));
1173                 if (brush->vel_ramp)
1174                         memcpy(t_brush->vel_ramp, brush->vel_ramp, sizeof(ColorBand));
1175
1176                 t_brush->proximity_falloff = brush->proximity_falloff;
1177                 t_brush->wave_type = brush->wave_type;
1178                 t_brush->ray_dir = brush->ray_dir;
1179
1180                 t_brush->wave_factor = brush->wave_factor;
1181                 t_brush->wave_clamp = brush->wave_clamp;
1182                 t_brush->max_velocity = brush->max_velocity;
1183                 t_brush->smudge_strength = brush->smudge_strength;
1184         }
1185 }
1186
1187 /* allocates surface data depending on surface type */
1188 static void dynamicPaint_allocateSurfaceType(DynamicPaintSurface *surface)
1189 {
1190         PaintSurfaceData *sData = surface->data;
1191
1192         switch (surface->type) {
1193                 case MOD_DPAINT_SURFACE_T_PAINT:
1194                         sData->type_data = MEM_callocN(sizeof(PaintPoint)*sData->total_points, "DynamicPaintSurface Data");
1195                         break;
1196                 case MOD_DPAINT_SURFACE_T_DISPLACE:
1197                         sData->type_data = MEM_callocN(sizeof(float)*sData->total_points, "DynamicPaintSurface DepthData");
1198                         break;
1199                 case MOD_DPAINT_SURFACE_T_WEIGHT:
1200                         sData->type_data = MEM_callocN(sizeof(float)*sData->total_points, "DynamicPaintSurface WeightData");
1201                         break;
1202                 case MOD_DPAINT_SURFACE_T_WAVE:
1203                         sData->type_data = MEM_callocN(sizeof(PaintWavePoint)*sData->total_points, "DynamicPaintSurface WaveData");
1204                         break;
1205         }
1206
1207         if (sData->type_data == NULL) setError(surface->canvas, "Not enough free memory!");
1208 }
1209
1210 static int surface_usesAdjDistance(DynamicPaintSurface *surface)
1211 {
1212         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT && surface->effect) return 1;
1213         if (surface->type == MOD_DPAINT_SURFACE_T_WAVE) return 1;
1214         return 0;
1215 }
1216
1217 static int surface_usesAdjData(DynamicPaintSurface *surface)
1218 {
1219         if (surface_usesAdjDistance(surface)) return 1;
1220         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX &&
1221                 surface->flags & MOD_DPAINT_ANTIALIAS) return 1;
1222
1223         return 0;
1224 }
1225
1226 /* initialize surface adjacency data */
1227 static void dynamicPaint_initAdjacencyData(DynamicPaintSurface *surface, int force_init)
1228 {
1229         PaintSurfaceData *sData = surface->data;
1230         DerivedMesh *dm = surface->canvas->dm;
1231         PaintAdjData *ad;
1232         int *temp_data;
1233         int neigh_points = 0;
1234
1235         if (!surface_usesAdjData(surface) && !force_init) return;
1236
1237         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1238                 /* For vertex format, neighbors are connected by edges */
1239                 neigh_points = 2*dm->getNumEdges(dm);
1240         }
1241         else if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ)
1242                 neigh_points = sData->total_points*8;
1243
1244         if (!neigh_points) return;
1245
1246         /* allocate memory */
1247         ad = sData->adj_data = MEM_callocN(sizeof(PaintAdjData), "Surface Adj Data");
1248         if (!ad) return;
1249         ad->n_index = MEM_callocN(sizeof(int)*sData->total_points, "Surface Adj Index");
1250         ad->n_num = MEM_callocN(sizeof(int)*sData->total_points, "Surface Adj Counts");
1251         temp_data = MEM_callocN(sizeof(int)*sData->total_points, "Temp Adj Data");
1252         ad->n_target = MEM_callocN(sizeof(int)*neigh_points, "Surface Adj Targets");
1253         ad->flags = MEM_callocN(sizeof(int)*sData->total_points, "Surface Adj Flags");
1254         ad->total_targets = neigh_points;
1255
1256         /* in case of allocation error, free memory */
1257         if (!ad->n_index || !ad->n_num || !ad->n_target || !temp_data) {
1258                 dynamicPaint_freeAdjData(sData);
1259                 if (temp_data) MEM_freeN(temp_data);
1260                 setError(surface->canvas, "Not enough free memory.");
1261                 return;
1262         }
1263
1264         if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1265                 int i;
1266                 int n_pos;
1267
1268                 /* For vertex format, count every vertex that is connected by an edge */
1269                 int numOfEdges = dm->getNumEdges(dm);
1270                 int numOfPolys = dm->getNumPolys(dm);
1271                 struct MEdge *edge =  dm->getEdgeArray(dm);
1272                 struct MPoly *mpoly = dm->getPolyArray(dm);
1273                 struct MLoop *mloop = dm->getLoopArray(dm);
1274
1275                 /* count number of edges per vertex */
1276                 for (i=0; i<numOfEdges; i++) {
1277                         ad->n_num[edge[i].v1]++;
1278                         ad->n_num[edge[i].v2]++;
1279
1280                         temp_data[edge[i].v1]++;
1281                         temp_data[edge[i].v2]++;
1282                 }
1283
1284                 /* also add number of vertices to temp_data
1285                 *  to locate points on "mesh edge" */
1286                 for (i=0; i<numOfPolys; i++) {
1287                         int j=0;
1288                         for (; j<mpoly[i].totloop; j++) {
1289                                 temp_data[mloop[mpoly[i].loopstart + j].v]++;
1290                         }
1291                 }
1292
1293                 /* now check if total number of edges+faces for
1294                 *  each vertex is even, if not -> vertex is on mesh edge */
1295                 for (i=0; i<sData->total_points; i++) {
1296                         if ((temp_data[i]%2) ||
1297                                 temp_data[i] < 4)
1298                                 ad->flags[i] |= ADJ_ON_MESH_EDGE;
1299                                 
1300                         /* reset temp data */ 
1301                         temp_data[i] = 0;
1302                 }
1303
1304                 /* order n_index array */
1305                 n_pos = 0;
1306                 for (i=0; i<sData->total_points; i++) {
1307                         ad->n_index[i] = n_pos;
1308                         n_pos += ad->n_num[i];
1309                 }
1310
1311                 /* and now add neighbor data using that info */
1312                 for (i=0; i<numOfEdges; i++) {
1313                         /* first vertex */
1314                         int index = edge[i].v1;
1315                         n_pos = ad->n_index[index]+temp_data[index];
1316                         ad->n_target[n_pos] = edge[i].v2;
1317                         temp_data[index]++;
1318
1319                         /* second vertex */
1320                         index = edge[i].v2;
1321                         n_pos = ad->n_index[index]+temp_data[index];
1322                         ad->n_target[n_pos] = edge[i].v1;
1323                         temp_data[index]++;
1324                 }
1325         }
1326         else if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
1327                 /* for image sequences, only allocate memory.
1328                 *  bake initialization takes care of rest */
1329         }
1330
1331         MEM_freeN(temp_data);
1332 }
1333
1334 void dynamicPaint_setInitialColor(DynamicPaintSurface *surface)
1335 {
1336         PaintSurfaceData *sData = surface->data;
1337         PaintPoint* pPoint = (PaintPoint*)sData->type_data;
1338         DerivedMesh *dm = surface->canvas->dm;
1339         int i;
1340
1341         if (surface->type != MOD_DPAINT_SURFACE_T_PAINT)
1342                 return;
1343
1344         if (surface->init_color_type == MOD_DPAINT_INITIAL_NONE)
1345                 return;
1346         /* Single color */
1347         else if (surface->init_color_type == MOD_DPAINT_INITIAL_COLOR) {
1348                 /* apply color to every surface point */
1349                 #pragma omp parallel for schedule(static)
1350                 for (i=0; i<sData->total_points; i++) {
1351                         copy_v3_v3(pPoint[i].color, surface->init_color);
1352                         pPoint[i].alpha = surface->init_color[3];
1353                 }
1354         }
1355         /* UV mapped texture */
1356         else if (surface->init_color_type == MOD_DPAINT_INITIAL_TEXTURE) {
1357                 Tex *tex = surface->init_texture;
1358                 MTFace *tface;
1359                 MFace *mface = dm->getTessFaceArray(dm);
1360                 int numOfFaces = dm->getNumTessFaces(dm);
1361                 char uvname[MAX_CUSTOMDATA_LAYER_NAME];
1362
1363                 if (!tex) return;
1364
1365                 /* get uv map */
1366                 CustomData_validate_layer_name(&dm->faceData, CD_MTFACE, surface->init_layername, uvname);
1367                 tface = CustomData_get_layer_named(&dm->faceData, CD_MTFACE, uvname);
1368                 if (!tface) return;
1369
1370                 /* for vertex surface loop through tfaces and find uv color
1371                 *  that provides highest alpha */
1372                 if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1373                         #pragma omp parallel for schedule(static)
1374                         for (i=0; i<numOfFaces; i++) {
1375                                 int numOfVert = (mface[i].v4) ? 4 : 3;
1376                                 float uv[3] = {0.0f};
1377                                 int j;
1378                                 for (j=0; j<numOfVert; j++) {
1379                                         TexResult texres = {0};
1380                                         unsigned int *vert = (&mface[i].v1)+j;
1381
1382                                         /* remap to -1.0 to 1.0 */
1383                                         uv[0] = tface[i].uv[j][0]*2.0f - 1.0f;
1384                                         uv[1] = tface[i].uv[j][1]*2.0f - 1.0f;
1385
1386                                         multitex_ext_safe(tex, uv, &texres);
1387
1388                                         if (texres.tin > pPoint[*vert].alpha) {
1389                                                 copy_v3_v3(pPoint[*vert].color, &texres.tr);
1390                                                 pPoint[*vert].alpha = texres.tin;
1391                                         }
1392                                 }
1393                         }
1394                 }
1395                 else if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
1396                         ImgSeqFormatData *f_data = (ImgSeqFormatData*)sData->format_data;
1397                         int samples = (surface->flags & MOD_DPAINT_ANTIALIAS) ? 5 : 1;
1398
1399                         #pragma omp parallel for schedule(static)
1400                         for (i=0; i<sData->total_points; i++) {
1401                                 float uv[9] = {0.0f};
1402                                 float uv_final[3] = {0.0f};
1403                                 int j;
1404                                 TexResult texres = {0};
1405
1406                                 /* collect all uvs */
1407                                 for (j=0; j<3; j++) {
1408                                         int v=(f_data->uv_p[i].quad && j>0) ? j+1 : j;
1409                                         copy_v2_v2(&uv[j*3], tface[f_data->uv_p[i].face_index].uv[v]);
1410                                 }
1411
1412                                 /* interpolate final uv pos */
1413                                 interp_v3_v3v3v3(       uv_final, &uv[0], &uv[3], &uv[6],
1414                                         f_data->barycentricWeights[i*samples].v);
1415                                 /* remap to -1.0 to 1.0 */
1416                                 uv_final[0] = uv_final[0]*2.0f - 1.0f;
1417                                 uv_final[1] = uv_final[1]*2.0f - 1.0f;
1418                                         
1419                                 multitex_ext_safe(tex, uv_final, &texres);
1420
1421                                 /* apply color */
1422                                 copy_v3_v3(pPoint[i].color, &texres.tr);
1423                                 pPoint[i].alpha = texres.tin;
1424                         }
1425                 }
1426         }
1427         /* vertex color layer */
1428         else if (surface->init_color_type == MOD_DPAINT_INITIAL_VERTEXCOLOR) {
1429
1430                 /* for vertex surface, just copy colors from mcol */
1431                 if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1432                         MLoop *mloop = dm->getLoopArray(dm);
1433                         int numOfLoops = dm->getNumLoops(dm);
1434                         MCol *col = CustomData_get_layer_named(&dm->loopData, CD_MLOOPCOL, surface->init_layername);
1435                         if (!col) return;
1436
1437                         #pragma omp parallel for schedule(static)
1438                         for (i=0; i<numOfLoops; i++) {
1439                                 pPoint[mloop[i].v].color[0] = 1.0f/255.f*(float)col[i].b;
1440                                 pPoint[mloop[i].v].color[1] = 1.0f/255.f*(float)col[i].g;
1441                                 pPoint[mloop[i].v].color[2] = 1.0f/255.f*(float)col[i].r;
1442                                 pPoint[mloop[i].v].alpha = 1.0f/255.f*(float)col[i].a;
1443                         }
1444                 }
1445                 else if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) {
1446                         ImgSeqFormatData *f_data = (ImgSeqFormatData*)sData->format_data;
1447                         int samples = (surface->flags & MOD_DPAINT_ANTIALIAS) ? 5 : 1;
1448                         MCol *col = CustomData_get_layer_named(&dm->faceData, CD_MCOL, surface->init_layername);
1449                         if (!col) return;
1450
1451                         #pragma omp parallel for schedule(static)
1452                         for (i=0; i<sData->total_points; i++) {
1453                                 int face_ind = f_data->uv_p[i].face_index;
1454                                 float colors[3][4] = {{0.0f,0.0f,0.0f,0.0f}};
1455                                 float final_color[4];
1456                                 int j;
1457                                 /* collect color values */
1458                                 for (j=0; j<3; j++) {
1459                                         int v=(f_data->uv_p[i].quad && j>0) ? j+1 : j;
1460                                         colors[j][0] = 1.0f/255.f*(float)col[face_ind*4+v].b;
1461                                         colors[j][1] = 1.0f/255.f*(float)col[face_ind*4+v].g;
1462                                         colors[j][2] = 1.0f/255.f*(float)col[face_ind*4+v].r;
1463                                         colors[j][3] = 1.0f/255.f*(float)col[face_ind*4+v].a;
1464                                 }
1465                                 
1466                                 /* interpolate final color */
1467                                 interp_v4_v4v4v4(       final_color, colors[0], colors[1], colors[2],
1468                                                 f_data->barycentricWeights[i*samples].v);
1469
1470                                 copy_v3_v3(pPoint[i].color, final_color);
1471                                 pPoint[i].alpha = final_color[3];
1472                         }
1473                 }
1474         }
1475 }
1476
1477 /* clears surface data back to zero */
1478 void dynamicPaint_clearSurface(DynamicPaintSurface *surface)
1479 {
1480         PaintSurfaceData *sData = surface->data;
1481         if (sData && sData->type_data) {
1482                 unsigned int data_size;
1483
1484                 if (surface->type == MOD_DPAINT_SURFACE_T_PAINT)
1485                         data_size = sizeof(PaintPoint);
1486                 else if (surface->type == MOD_DPAINT_SURFACE_T_WAVE)
1487                         data_size = sizeof(PaintWavePoint);
1488                 else
1489                         data_size = sizeof(float);
1490
1491                 memset(sData->type_data, 0, data_size * sData->total_points);
1492
1493                 /* set initial color */
1494                 if (surface->type == MOD_DPAINT_SURFACE_T_PAINT)
1495                         dynamicPaint_setInitialColor(surface);
1496
1497                 if (sData->bData)
1498                         sData->bData->clear = 1;
1499         }
1500 }
1501
1502 /* completely (re)initializes surface (only for point cache types)*/
1503 int dynamicPaint_resetSurface(DynamicPaintSurface *surface)
1504 {
1505         int numOfPoints = dynamicPaint_surfaceNumOfPoints(surface);
1506         /* free existing data */
1507         if (surface->data) dynamicPaint_freeSurfaceData(surface);
1508
1509         /* dont reallocate for image sequence types. they get handled only on bake */
1510         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) return 1;
1511         if (numOfPoints < 1) return 0;
1512
1513         /* allocate memory */
1514         surface->data = MEM_callocN(sizeof(PaintSurfaceData), "PaintSurfaceData");
1515         if (!surface->data) return 0;
1516
1517         /* allocate data depending on surface type and format */
1518         surface->data->total_points = numOfPoints;
1519         dynamicPaint_allocateSurfaceType(surface);
1520         dynamicPaint_initAdjacencyData(surface, 0);
1521
1522         /* set initial color */
1523         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT)
1524                 dynamicPaint_setInitialColor(surface);
1525
1526         return 1;
1527 }
1528
1529 /* make sure allocated surface size matches current requirements */
1530 static int dynamicPaint_checkSurfaceData(DynamicPaintSurface *surface)
1531 {
1532         if (!surface->data || ((dynamicPaint_surfaceNumOfPoints(surface) != surface->data->total_points))) {
1533                 return dynamicPaint_resetSurface(surface);
1534         }
1535         return 1;
1536 }
1537
1538
1539 /***************************** Modifier processing ******************************/
1540
1541
1542 /* apply displacing vertex surface to the derived mesh */
1543 static void dynamicPaint_applySurfaceDisplace(DynamicPaintSurface *surface, DerivedMesh *result)
1544 {
1545         PaintSurfaceData *sData = surface->data;
1546
1547         if (!sData || surface->format != MOD_DPAINT_SURFACE_F_VERTEX) return;
1548
1549         /* displace paint */
1550         if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE) {
1551                 MVert *mvert = result->getVertArray(result);
1552                 int i;
1553                 float* value = (float*)sData->type_data;
1554
1555                 #pragma omp parallel for schedule(static)
1556                 for (i=0; i<sData->total_points; i++) {
1557                         float normal[3], val=value[i]*surface->disp_factor;
1558                         normal_short_to_float_v3(normal, mvert[i].no);
1559                         normalize_v3(normal);
1560
1561                         mvert[i].co[0] -= normal[0]*val;
1562                         mvert[i].co[1] -= normal[1]*val;
1563                         mvert[i].co[2] -= normal[2]*val;
1564                 }
1565         }
1566 }
1567
1568 /*
1569 *       Apply canvas data to the object derived mesh
1570 */
1571 static struct DerivedMesh *dynamicPaint_Modifier_apply(DynamicPaintModifierData *pmd,
1572                                                        Object *ob,
1573                                                        DerivedMesh *dm)
1574 {       
1575         DerivedMesh *result = CDDM_copy(dm);
1576
1577         if(pmd->canvas && !(pmd->canvas->flags & MOD_DPAINT_BAKING)) {
1578
1579                 DynamicPaintSurface *surface = pmd->canvas->surfaces.first;
1580                 int update_normals = 0;
1581
1582                 /* loop through surfaces */
1583                 for (; surface; surface=surface->next) {
1584                         PaintSurfaceData *sData = surface->data;
1585
1586                         if (surface && surface->format != MOD_DPAINT_SURFACE_F_IMAGESEQ && sData) {
1587                                 if (!(surface->flags & (MOD_DPAINT_ACTIVE))) continue;
1588
1589                                 /* process vertex surface previews */
1590                                 if (surface->format == MOD_DPAINT_SURFACE_F_VERTEX) {
1591
1592                                         /* vertex color paint */
1593                                         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
1594
1595                                                 int i;
1596                                                 PaintPoint* pPoint = (PaintPoint*)sData->type_data;
1597                                                 MLoopCol *col = NULL;
1598                                                 MLoop *mloop = CDDM_get_loops(result);
1599                                                 int totloop = result->numLoopData;
1600
1601                                                 /* paint is stored on dry and wet layers, so mix final color first */
1602                                                 float *fcolor = MEM_callocN(sizeof(float)*sData->total_points*4, "Temp paint color");
1603
1604                                                 #pragma omp parallel for schedule(static)
1605                                                 for (i=0; i<sData->total_points; i++) {
1606                                                         /* blend dry and wet layer */
1607                                                         blendColors(pPoint[i].color, pPoint[i].alpha, pPoint[i].e_color, pPoint[i].e_alpha, &fcolor[i*4]);
1608                                                 }
1609
1610                                                 /* viewport preview */
1611                                                 if (surface->flags & MOD_DPAINT_PREVIEW) {
1612                                                         MPoly *mp = CDDM_get_polys(result);
1613                                                         int totpoly = result->numPolyData;
1614
1615                                                         /* XXX We have to create a CD_WEIGHT_MCOL, else it might sigsev
1616                                                          *     (after a SubSurf mod, eg)... */
1617                                                         if(!result->getTessFaceDataArray(result, CD_WEIGHT_MCOL)) {
1618                                                                 int numFaces = result->getNumTessFaces(result);
1619                                                                 CustomData_add_layer(&result->faceData, CD_WEIGHT_MCOL, CD_CALLOC, NULL, numFaces);
1620                                                         }
1621
1622                                                         /* Save preview results to weight layer to be
1623                                                         *   able to share same drawing methods */
1624                                                         col = CustomData_get_layer(&result->loopData, CD_WEIGHT_MLOOPCOL);
1625                                                         if (!col) col = CustomData_add_layer(&result->loopData, CD_WEIGHT_MLOOPCOL, CD_CALLOC, NULL, totloop);
1626
1627                                                         if (col) {
1628                                                                 #pragma omp parallel for schedule(static)
1629                                                                 for (i=0; i<totpoly; i++) {
1630                                                                         int j=0;
1631                                                                         Material *material = give_current_material(ob, mp[i].mat_nr+1);
1632
1633                                                                         for (; j<mp[i].totloop; j++) {
1634                                                                                 int l_index = mp[i].loopstart + j;
1635                                                                                 int v_index = mloop[l_index].v;
1636
1637                                                                                 if (surface->preview_id == MOD_DPAINT_SURFACE_PREV_PAINT) {
1638                                                                                         float c[3];
1639                                                                                         v_index *= 4;
1640
1641                                                                                         /* Apply material color as base vertex color for preview */
1642                                                                                         col[l_index].a = 255;
1643                                                                                         if (material) {
1644                                                                                                 c[0] = material->r;
1645                                                                                                 c[1] = material->g;
1646                                                                                                 c[2] = material->b;
1647                                                                                         }
1648                                                                                         else { /* default grey */
1649                                                                                                 c[0] = 0.65f;
1650                                                                                                 c[1] = 0.65f;
1651                                                                                                 c[2] = 0.65f;
1652                                                                                         }
1653                                                                                         /* mix surface color */
1654                                                                                         interp_v3_v3v3(c, c, &fcolor[v_index], fcolor[v_index+3]);
1655
1656                                                                                         rgb_float_to_uchar((unsigned char *)&col[l_index].r, c);
1657                                                                                 }
1658                                                                                 else {
1659                                                                                         col[l_index].r =
1660                                                                                         col[l_index].g =
1661                                                                                         col[l_index].b = FTOCHAR(pPoint[v_index].wetness);
1662                                                                                         col[l_index].a = 255;
1663                                                                                 }
1664                                                                         }
1665                                                                 }
1666                                                         }
1667                                                 }
1668
1669
1670                                                 /* save layer data to output layer */
1671
1672                                                 /* paint layer */
1673                                                 col = CustomData_get_layer_named(&result->loopData, CD_MLOOPCOL, surface->output_name);
1674                                                 /* if output layer is lost from a constructive modifier, re-add it */
1675                                                 if (!col && dynamicPaint_outputLayerExists(surface, ob, 0))
1676                                                         col = CustomData_add_layer_named(&result->loopData, CD_MLOOPCOL, CD_CALLOC, NULL, totloop, surface->output_name);
1677                                                 /* apply color */
1678                                                 if (col) {
1679                                                         #pragma omp parallel for schedule(static)
1680                                                         for (i=0; i<totloop; i++) {
1681                                                                 int index = mloop[i].v*4;
1682                                                                 rgb_float_to_uchar((unsigned char *)&col[i].r, &fcolor[index]);
1683                                                                 col[i].a = FTOCHAR(fcolor[index+3]); /* IS THIS NEEDED? */
1684                                                         }
1685                                                 }
1686                                                 
1687                                                 MEM_freeN(fcolor);
1688
1689                                                 /* wet layer */
1690                                                 col = CustomData_get_layer_named(&result->loopData, CD_MLOOPCOL, surface->output_name2);
1691                                                 /* if output layer is lost from a constructive modifier, re-add it */
1692                                                 if (!col && dynamicPaint_outputLayerExists(surface, ob, 1))
1693                                                         col = CustomData_add_layer_named(&result->loopData, CD_MLOOPCOL, CD_CALLOC, NULL, totloop, surface->output_name2);
1694                                                 /* apply color */
1695                                                 if (col) {
1696                                                         #pragma omp parallel for schedule(static)
1697                                                         for (i=0; i<totloop; i++) {
1698                                                                 int index = mloop[i].v;
1699                                                                 col[i].r =
1700                                                                 col[i].g =
1701                                                                 col[i].b = FTOCHAR(pPoint[index].wetness);
1702                                                                 col[i].a = 255;
1703                                                         }
1704                                                 }
1705                                         }
1706                                         /* vertex group paint */
1707                                         else if (surface->type == MOD_DPAINT_SURFACE_T_WEIGHT) {
1708                                                 int defgrp_index = defgroup_name_index(ob, surface->output_name);
1709                                                 MDeformVert *dvert = result->getVertDataArray(result, CD_MDEFORMVERT);
1710                                                 float *weight = (float*)sData->type_data;
1711
1712                                                 /* viewport preview */
1713                                                 if (surface->flags & MOD_DPAINT_PREVIEW) {
1714                                                         /* Save preview results to weight layer to be
1715                                                         *   able to share same drawing methods */
1716                                                         DM_update_weight_mcol(ob, result, 0, weight, 0, NULL);
1717                                                 }
1718
1719                                                 /* apply weights into a vertex group, if doesnt exists add a new layer */
1720                                                 if (defgrp_index >= 0 && !dvert && (surface->output_name[0] != '\0'))
1721                                                         dvert = CustomData_add_layer_named(&result->vertData, CD_MDEFORMVERT, CD_CALLOC,
1722                                                                                                                                 NULL, sData->total_points, surface->output_name);
1723                                                 if (defgrp_index >= 0 && dvert) {
1724                                                         int i;
1725                                                         for(i=0; i<sData->total_points; i++) {
1726                                                                 MDeformVert *dv= &dvert[i];
1727                                                                 MDeformWeight *def_weight = defvert_find_index(dv, defgrp_index);
1728
1729                                                                 /* skip if weight value is 0 and no existing weight is found */
1730                                                                 if ((def_weight != NULL) || (weight[i] != 0.0f)) {
1731
1732                                                                         /* if not found, add a weight for it */
1733                                                                         if (def_weight == NULL) {
1734                                                                                 def_weight= defvert_verify_index(dv, defgrp_index);
1735                                                                         }
1736
1737                                                                         /* set weight value */
1738                                                                         def_weight->weight = weight[i];
1739                                                                 }
1740                                                         }
1741                                                 }
1742                                         }
1743                                         /* wave simulation */
1744                                         else if (surface->type == MOD_DPAINT_SURFACE_T_WAVE) {
1745                                                 MVert *mvert = result->getVertArray(result);
1746                                                 int i;
1747                                                 PaintWavePoint* wPoint = (PaintWavePoint*)sData->type_data;
1748
1749                                                 #pragma omp parallel for schedule(static)
1750                                                 for (i=0; i<sData->total_points; i++) {
1751                                                         float normal[3];
1752                                                         normal_short_to_float_v3(normal, mvert[i].no);
1753                                                         madd_v3_v3fl(mvert[i].co, normal, wPoint[i].height);
1754                                                 }
1755                                                 update_normals = 1;
1756                                         }
1757
1758                                         /* displace */
1759                                         if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE) {
1760                                                 dynamicPaint_applySurfaceDisplace(surface, result);
1761                                                 update_normals = 1;
1762                                         }
1763                                 }
1764                         }
1765                 }
1766
1767                 if (update_normals)
1768                         CDDM_calc_normals(result);
1769         }
1770         /* make a copy of dm to use as brush data */
1771         if (pmd->brush) {
1772                 if (pmd->brush->dm) pmd->brush->dm->release(pmd->brush->dm);
1773                 pmd->brush->dm = CDDM_copy(result);
1774         }
1775
1776         return result;
1777 }
1778
1779 /* update cache frame range */
1780 void dynamicPaint_cacheUpdateFrames(DynamicPaintSurface *surface)
1781 {
1782         if (surface->pointcache) {
1783                 surface->pointcache->startframe = surface->start_frame;
1784                 surface->pointcache->endframe = surface->end_frame;
1785         }
1786 }
1787
1788 void canvas_copyDerivedMesh(DynamicPaintCanvasSettings *canvas, DerivedMesh *dm)
1789 {
1790         if (canvas->dm) canvas->dm->release(canvas->dm);
1791         canvas->dm = CDDM_copy(dm);
1792 }
1793
1794 /*
1795 *       Updates derived mesh copy and processes dynamic paint step / caches.
1796 */
1797 static void dynamicPaint_frameUpdate(DynamicPaintModifierData *pmd, Scene *scene, Object *ob, DerivedMesh *dm)
1798 {
1799         if(pmd->canvas) {
1800                 DynamicPaintCanvasSettings *canvas = pmd->canvas;
1801                 DynamicPaintSurface *surface = canvas->surfaces.first;
1802
1803                 /* update derived mesh copy */
1804                 canvas_copyDerivedMesh(canvas, dm);
1805
1806                 /* in case image sequence baking, stop here */
1807                 if (canvas->flags & MOD_DPAINT_BAKING) return;
1808
1809                 /* loop through surfaces */
1810                 for (; surface; surface=surface->next) {
1811                         int current_frame = (int)scene->r.cfra;
1812
1813                         /* free bake data if not required anymore */
1814                         surface_freeUnusedData(surface);
1815
1816                         /* image sequences are handled by bake operator */
1817                         if (surface->format == MOD_DPAINT_SURFACE_F_IMAGESEQ) continue;
1818                         if (!(surface->flags & MOD_DPAINT_ACTIVE)) continue;
1819
1820                         /* make sure surface is valid */
1821                         if (!dynamicPaint_checkSurfaceData(surface)) continue;
1822
1823                         /* limit frame range */
1824                         CLAMP(current_frame, surface->start_frame, surface->end_frame);
1825
1826                         if (current_frame != surface->current_frame || (int)scene->r.cfra == surface->start_frame) {
1827                                 PointCache *cache = surface->pointcache;
1828                                 PTCacheID pid;
1829                                 surface->current_frame = current_frame;
1830
1831                                 /* read point cache */
1832                                 BKE_ptcache_id_from_dynamicpaint(&pid, ob, surface);
1833                                 pid.cache->startframe = surface->start_frame;
1834                                 pid.cache->endframe = surface->end_frame;
1835                                 BKE_ptcache_id_time(&pid, scene, (float)scene->r.cfra, NULL, NULL, NULL);
1836
1837                                 /* reset non-baked cache at first frame */
1838                                 if((int)scene->r.cfra == surface->start_frame && !(cache->flag & PTCACHE_BAKED))
1839                                 {
1840                                         cache->flag |= PTCACHE_REDO_NEEDED;
1841                                         BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
1842                                         cache->flag &= ~PTCACHE_REDO_NEEDED;
1843                                 }
1844
1845                                 /* try to read from cache */
1846                                 if(BKE_ptcache_read(&pid, (float)scene->r.cfra)) {
1847                                         BKE_ptcache_validate(cache, (int)scene->r.cfra);
1848                                 }
1849                                 /* if read failed and we're on surface range do recalculate */
1850                                 else if ((int)scene->r.cfra == current_frame
1851                                         && !(cache->flag & PTCACHE_BAKED)) {
1852                                         /* calculate surface frame */
1853                                         canvas->flags |= MOD_DPAINT_BAKING;
1854                                         dynamicPaint_calculateFrame(surface, scene, ob, current_frame);
1855                                         canvas->flags &= ~MOD_DPAINT_BAKING;
1856
1857                                         /* restore canvas derivedmesh if required */
1858                                         if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE &&
1859                                                 surface->flags & MOD_DPAINT_DISP_INCREMENTAL && surface->next)
1860                                                 canvas_copyDerivedMesh(canvas, dm);
1861
1862                                         BKE_ptcache_validate(cache, surface->current_frame);
1863                                         BKE_ptcache_write(&pid, surface->current_frame);
1864                                 }
1865                         }
1866                 }
1867         }
1868 }
1869
1870 /* Modifier call. Processes dynamic paint modifier step. */
1871 struct DerivedMesh *dynamicPaint_Modifier_do(DynamicPaintModifierData *pmd, Scene *scene, Object *ob, DerivedMesh *dm)
1872 {       
1873         /* For now generate tessfaces in every case
1874         *  XXX - move/remove when most of dpaint functions are converted to use bmesh types */
1875         DM_ensure_tessface(dm);
1876
1877         /* Update canvas data for a new frame */
1878         dynamicPaint_frameUpdate(pmd, scene, ob, dm);
1879
1880         /* Return output mesh */
1881         return dynamicPaint_Modifier_apply(pmd, ob, dm);
1882 }
1883
1884
1885 /***************************** Image Sequence / UV Image Surface Calls ******************************/
1886
1887 /*
1888 *       Tries to find the neighboring pixel in given (uv space) direction.
1889 *       Result is used by effect system to move paint on the surface.
1890 *
1891 *   px,py : origin pixel x and y
1892 *       n_index : lookup direction index (use neighX,neighY to get final index)
1893 */
1894 static int dynamicPaint_findNeighbourPixel(PaintUVPoint *tempPoints, DerivedMesh *dm,
1895                                            const char *uvname, int w, int h, int px, int py, int n_index)
1896 {
1897         /* Note: Current method only uses polygon edges to detect neighboring pixels.
1898         *  -> It doesn't always lead to the optimum pixel but is accurate enough
1899         *  and faster/simplier than including possible face tip point links)
1900         */
1901
1902         int x,y;
1903         PaintUVPoint *tPoint = NULL;
1904         PaintUVPoint *cPoint = NULL;
1905
1906         /* shift position by given n_index */
1907         x = px + neighX[n_index];
1908         y = py + neighY[n_index];
1909
1910         if (x<0 || x>=w) return OUT_OF_TEXTURE;
1911         if (y<0 || y>=h) return OUT_OF_TEXTURE;
1912
1913         tPoint = &tempPoints[x+w*y];            /* UV neighbor */
1914         cPoint = &tempPoints[px+w*py];          /* Origin point */
1915
1916         /*
1917         *       Check if shifted point is on same face -> it's a correct neighbor
1918         *   (and if it isn't marked as an "edge pixel")
1919         */
1920         if ((tPoint->face_index == cPoint->face_index) && (tPoint->neighbour_pixel == -1))
1921                 return (x+w*y);
1922
1923         /*
1924         *       Even if shifted point is on another face
1925         *       -> use this point.
1926         *       
1927         *       !! Replace with "is uv faces linked" check !!
1928         *       This should work fine as long as uv island
1929         *       margin is > 1 pixel.
1930         */
1931         if ((tPoint->face_index != -1) && (tPoint->neighbour_pixel == -1)) {
1932                 return (x+w*y);
1933         }
1934
1935         /*
1936         *       If we get here, the actual neighboring pixel
1937         *       is located on a non-linked uv face, and we have to find
1938         *       it's "real" position.
1939         *
1940         *       Simple neighboring face finding algorithm:
1941         *       - find closest uv edge to shifted pixel and get
1942         *         the another face that shares that edge
1943         *       - find corresponding position of that new face edge
1944         *         in uv space
1945         *
1946         *       TODO: Implement something more accurate / optimized?
1947         */
1948         {
1949                 int numOfFaces = dm->getNumTessFaces(dm);
1950                 MFace *mface = dm->getTessFaceArray(dm);
1951                 MTFace *tface =  CustomData_get_layer_named(&dm->faceData, CD_MTFACE, uvname);
1952
1953                 /* Get closest edge to that subpixel on UV map  */
1954                 {
1955                         float pixel[2], dist, t_dist;
1956                         int i, uindex[3], edge1_index, edge2_index,
1957                                 e1_index, e2_index, target_face;
1958                         float closest_point[2], lambda, dir_vec[2];
1959                         int target_uv1, target_uv2, final_pixel[2], final_index;
1960
1961                         float *s_uv1, *s_uv2, *t_uv1, *t_uv2;
1962
1963                         pixel[0] = ((float)(px + neighX[n_index]) + 0.5f) / (float)w;
1964                         pixel[1] = ((float)(py + neighY[n_index]) + 0.5f) / (float)h;
1965
1966                         /* Get uv indexes for current face part */
1967                         if (cPoint->quad) {
1968                                 uindex[0] = 0; uindex[1] = 2; uindex[2] = 3;
1969                         }
1970                         else {
1971                                 uindex[0] = 0; uindex[1] = 1; uindex[2] = 2;
1972                         }
1973
1974                         /*
1975                         *       Find closest edge to that pixel
1976                         */
1977                         /* Dist to first edge   */
1978                         e1_index = cPoint->v1; e2_index = cPoint->v2; edge1_index = uindex[0]; edge2_index = uindex[1];
1979                         dist = dist_to_line_segment_v2(pixel, tface[cPoint->face_index].uv[edge1_index], tface[cPoint->face_index].uv[edge2_index]);
1980
1981                         /* Dist to second edge  */
1982                         t_dist = dist_to_line_segment_v2(pixel, tface[cPoint->face_index].uv[uindex[1]], tface[cPoint->face_index].uv[uindex[2]]);
1983                         if (t_dist < dist) {e1_index = cPoint->v2; e2_index = cPoint->v3; edge1_index = uindex[1]; edge2_index = uindex[2]; dist = t_dist;}
1984
1985                         /* Dist to third edge   */
1986                         t_dist = dist_to_line_segment_v2(pixel, tface[cPoint->face_index].uv[uindex[2]], tface[cPoint->face_index].uv[uindex[0]]);
1987                         if (t_dist < dist) {e1_index = cPoint->v3; e2_index = cPoint->v1;  edge1_index = uindex[2]; edge2_index = uindex[0]; dist = t_dist;}
1988
1989
1990                         /*
1991                         *       Now find another face that is linked to that edge
1992                         */
1993                         target_face = -1;
1994
1995                         for (i=0; i<numOfFaces; i++) {
1996                                 /*
1997                                 *       Check if both edge vertices share this face
1998                                 */
1999                                 int v4 = (mface[i].v4) ? mface[i].v4 : -1;
2000
2001                                 if ((e1_index == mface[i].v1 || e1_index == mface[i].v2 || e1_index == mface[i].v3 || e1_index == v4) &&
2002                                         (e2_index == mface[i].v1 || e2_index == mface[i].v2 || e2_index == mface[i].v3 || e2_index == v4)) {
2003                                         if (i == cPoint->face_index) continue;
2004
2005                                         target_face = i;
2006
2007                                         /*
2008                                         *       Get edge UV index
2009                                         */
2010                                         if (e1_index == mface[i].v1) target_uv1 = 0;
2011                                         else if (e1_index == mface[i].v2) target_uv1 = 1;
2012                                         else if (e1_index == mface[i].v3) target_uv1 = 2;
2013                                         else target_uv1 = 3;
2014
2015                                         if (e2_index == mface[i].v1) target_uv2 = 0;
2016                                         else if (e2_index == mface[i].v2) target_uv2 = 1;
2017                                         else if (e2_index == mface[i].v3) target_uv2 = 2;
2018                                         else target_uv2 = 3;
2019
2020                                         break;
2021                                 }
2022                         }
2023
2024                         /* If none found pixel is on mesh edge  */
2025                         if (target_face == -1) return ON_MESH_EDGE;
2026
2027                         /*
2028                         *       If target face is connected in UV space as well, just use original index
2029                         */
2030                         s_uv1 = (float *)tface[cPoint->face_index].uv[edge1_index];
2031                         s_uv2 = (float *)tface[cPoint->face_index].uv[edge2_index];
2032                         t_uv1 = (float *)tface[target_face].uv[target_uv1];
2033                         t_uv2 = (float *)tface[target_face].uv[target_uv2];
2034
2035                         //printf("connected UV : %f,%f & %f,%f - %f,%f & %f,%f\n", s_uv1[0], s_uv1[1], s_uv2[0], s_uv2[1], t_uv1[0], t_uv1[1], t_uv2[0], t_uv2[1]);
2036
2037                         if (((s_uv1[0] == t_uv1[0] && s_uv1[1] == t_uv1[1]) &&
2038                                  (s_uv2[0] == t_uv2[0] && s_uv2[1] == t_uv2[1]) ) ||
2039                                 ((s_uv2[0] == t_uv1[0] && s_uv2[1] == t_uv1[1]) &&
2040                                  (s_uv1[0] == t_uv2[0] && s_uv1[1] == t_uv2[1]) )) return ((px+neighX[n_index]) + w*(py+neighY[n_index]));
2041
2042                         /*
2043                         *       Find a point that is relatively at same edge position
2044                         *       on this other face UV
2045                         */
2046                         lambda = closest_to_line_v2(closest_point, pixel, tface[cPoint->face_index].uv[edge1_index], tface[cPoint->face_index].uv[edge2_index]);
2047                         if (lambda < 0.0f) lambda = 0.0f;
2048                         if (lambda > 1.0f) lambda = 1.0f;
2049
2050                         sub_v2_v2v2(dir_vec, tface[target_face].uv[target_uv2], tface[target_face].uv[target_uv1]);
2051
2052                         mul_v2_fl(dir_vec, lambda);
2053
2054                         copy_v2_v2(pixel, tface[target_face].uv[target_uv1]);
2055                         add_v2_v2(pixel, dir_vec);
2056                         pixel[0] = (pixel[0] * (float)w) - 0.5f;
2057                         pixel[1] = (pixel[1] * (float)h) - 0.5f;
2058
2059                         final_pixel[0] = (int)floor(pixel[0]);
2060                         final_pixel[1] = (int)floor(pixel[1]);
2061
2062                         /* If current pixel uv is outside of texture    */
2063                         if (final_pixel[0] < 0 || final_pixel[0] >= w) return OUT_OF_TEXTURE;
2064                         if (final_pixel[1] < 0 || final_pixel[1] >= h) return OUT_OF_TEXTURE;
2065
2066                         final_index = final_pixel[0] + w * final_pixel[1];
2067
2068                         /* If we ended up to our origin point ( mesh has smaller than pixel sized faces)        */
2069                         if (final_index == (px+w*py)) return NOT_FOUND;
2070                         /* If found pixel still lies on wrong face ( mesh has smaller than pixel sized faces)   */
2071                         if (tempPoints[final_index].face_index != target_face) return NOT_FOUND;
2072
2073                         /*
2074                         *       If final point is an "edge pixel", use it's "real" neighbor instead
2075                         */
2076                         if (tempPoints[final_index].neighbour_pixel != -1) final_index = cPoint->neighbour_pixel;
2077
2078                         return final_index;
2079                 }
2080         }
2081 }
2082
2083 /*
2084 *       Create a surface for uv image sequence format
2085 */
2086 int dynamicPaint_createUVSurface(DynamicPaintSurface *surface)
2087 {
2088         /* Antialias jitter point relative coords       */
2089         float jitter5sample[10] =  {0.0f, 0.0f,
2090                                                         -0.2f, -0.4f,
2091                                                         0.2f, 0.4f,
2092                                                         0.4f, -0.2f,
2093                                                         -0.4f, 0.3f};
2094         int ty;
2095         int w,h;
2096         int numOfFaces;
2097         char uvname[MAX_CUSTOMDATA_LAYER_NAME];
2098         int active_points = 0;
2099         int error = 0;
2100
2101         PaintSurfaceData *sData;
2102         DynamicPaintCanvasSettings *canvas = surface->canvas;
2103         DerivedMesh *dm = canvas->dm;
2104
2105         PaintUVPoint *tempPoints = NULL;
2106         Vec3f *tempWeights = NULL;
2107         MFace *mface = NULL;
2108         MTFace *tface = NULL;
2109         Bounds2D *faceBB = NULL;
2110         int *final_index;
2111         int aa_samples;
2112
2113         if (!dm) return setError(canvas, "Canvas mesh not updated.");
2114         if (surface->format != MOD_DPAINT_SURFACE_F_IMAGESEQ) return setError(canvas, "Can't bake non-\"image sequence\" formats.");
2115
2116         numOfFaces = dm->getNumTessFaces(dm);
2117         mface = dm->getTessFaceArray(dm);
2118
2119         /* get uv map */
2120         CustomData_validate_layer_name(&dm->faceData, CD_MTFACE, surface->uvlayer_name, uvname);
2121         tface = CustomData_get_layer_named(&dm->faceData, CD_MTFACE, uvname);
2122
2123         /* Check for validity   */
2124         if (!tface) return setError(canvas, "No UV data on canvas.");
2125         if (surface->image_resolution < 16 || surface->image_resolution > 8192) return setError(canvas, "Invalid resolution.");
2126
2127         w = h = surface->image_resolution;
2128
2129         /*
2130         *       Start generating the surface
2131         */
2132         printf("DynamicPaint: Preparing UV surface of %ix%i pixels and %i faces.\n", w, h, numOfFaces);
2133
2134         /* Init data struct */
2135         if (surface->data) dynamicPaint_freeSurfaceData(surface);
2136         sData = surface->data = MEM_callocN(sizeof(PaintSurfaceData), "PaintSurfaceData");
2137         if (!surface->data) return setError(canvas, "Not enough free memory.");
2138
2139         aa_samples = (surface->flags & MOD_DPAINT_ANTIALIAS) ? 5 : 1;
2140         tempPoints = (struct PaintUVPoint *) MEM_callocN(w*h*sizeof(struct PaintUVPoint), "Temp PaintUVPoint");
2141         if (!tempPoints) error=1;
2142
2143         final_index = (int *) MEM_callocN(w*h*sizeof(int), "Temp UV Final Indexes");
2144         if (!final_index) error=1;
2145
2146         tempWeights = (struct Vec3f *) MEM_mallocN(w*h*aa_samples*sizeof(struct Vec3f), "Temp bWeights");
2147         if (!tempWeights) error=1;
2148
2149         /*
2150         *       Generate a temporary bounding box array for UV faces to optimize
2151         *       the pixel-inside-a-face search.
2152         */
2153         if (!error) {
2154                 faceBB = (struct Bounds2D *) MEM_mallocN(numOfFaces*sizeof(struct Bounds2D), "MPCanvasFaceBB");
2155                 if (!faceBB) error=1;
2156         }
2157
2158         if (!error)
2159         for (ty=0; ty<numOfFaces; ty++) {
2160                 int numOfVert = (mface[ty].v4) ? 4 : 3;
2161                 int i;
2162
2163                 copy_v2_v2(faceBB[ty].min, tface[ty].uv[0]);
2164                 copy_v2_v2(faceBB[ty].max, tface[ty].uv[0]);
2165
2166                 for (i = 1; i<numOfVert; i++) {
2167                         if (tface[ty].uv[i][0] < faceBB[ty].min[0]) faceBB[ty].min[0] = tface[ty].uv[i][0];
2168                         if (tface[ty].uv[i][1] < faceBB[ty].min[1]) faceBB[ty].min[1] = tface[ty].uv[i][1];
2169                         if (tface[ty].uv[i][0] > faceBB[ty].max[0]) faceBB[ty].max[0] = tface[ty].uv[i][0];
2170                         if (tface[ty].uv[i][1] > faceBB[ty].max[1]) faceBB[ty].max[1] = tface[ty].uv[i][1];
2171
2172                 }
2173         }
2174
2175         /*
2176         *       Loop through every pixel and check
2177         *       if pixel is uv-mapped on a canvas face.
2178         */
2179         if (!error) {
2180                 #pragma omp parallel for schedule(static)
2181                 for (ty = 0; ty < h; ty++)
2182                 {
2183                         int tx;
2184                         for (tx = 0; tx < w; tx++)
2185                         {
2186                                 int i, sample;
2187                                 int index = tx+w*ty;
2188                                 PaintUVPoint *tPoint = (&tempPoints[index]);
2189
2190                                 short isInside = 0;     /* if point is inside a uv face */
2191
2192                                 float d1[2], d2[2], d3[2], point[5][2];
2193                                 float dot00,dot01,dot02,dot11,dot12, invDenom, u,v;
2194
2195                                 /* Init per pixel settings */
2196                                 tPoint->face_index = -1;
2197                                 tPoint->neighbour_pixel = -1;
2198                                 tPoint->pixel_index = index;
2199
2200                                 /* Actual pixel center, used when collision is found    */
2201                                 point[0][0] = ((float)tx + 0.5f) / w;
2202                                 point[0][1] = ((float)ty + 0.5f) / h;
2203
2204                                 /*
2205                                 * A pixel middle sample isn't enough to find very narrow polygons
2206                                 * So using 4 samples of each corner too
2207                                 */
2208                                 point[1][0] = ((float)tx) / w;
2209                                 point[1][1] = ((float)ty) / h;
2210
2211                                 point[2][0] = ((float)tx+1) / w;
2212                                 point[2][1] = ((float)ty) / h;
2213
2214                                 point[3][0] = ((float)tx) / w;
2215                                 point[3][1] = ((float)ty+1) / h;
2216
2217                                 point[4][0] = ((float)tx+1) / w;
2218                                 point[4][1] = ((float)ty+1) / h;
2219
2220
2221                                 /* Loop through samples, starting from middle point     */
2222                                 for (sample=0; sample<5; sample++) {
2223                                         
2224                                         /* Loop through every face in the mesh  */
2225                                         for (i=0; i<numOfFaces; i++) {
2226
2227                                                 /* Check uv bb  */
2228                                                 if (faceBB[i].min[0] > (point[sample][0])) continue;
2229                                                 if (faceBB[i].min[1] > (point[sample][1])) continue;
2230                                                 if (faceBB[i].max[0] < (point[sample][0])) continue;
2231                                                 if (faceBB[i].max[1] < (point[sample][1])) continue;
2232
2233                                                 /*  Calculate point inside a triangle check
2234                                                 *       for uv0,1,2 */
2235                                                 sub_v2_v2v2(d1,  tface[i].uv[2], tface[i].uv[0]);       // uv2 - uv0
2236                                                 sub_v2_v2v2(d2,  tface[i].uv[1], tface[i].uv[0]);       // uv1 - uv0
2237                                                 sub_v2_v2v2(d3,  point[sample], tface[i].uv[0]);        // point - uv0
2238
2239                                                 dot00 = d1[0]*d1[0] + d1[1]*d1[1];
2240                                                 dot01 = d1[0]*d2[0] + d1[1]*d2[1];
2241                                                 dot02 = d1[0]*d3[0] + d1[1]*d3[1];
2242                                                 dot11 = d2[0]*d2[0] + d2[1]*d2[1];
2243                                                 dot12 = d2[0]*d3[0] + d2[1]*d3[1];
2244
2245                                                 invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
2246                                                 u = (dot11 * dot02 - dot01 * dot12) * invDenom;
2247                                                 v = (dot00 * dot12 - dot01 * dot02) * invDenom;
2248
2249                                                 if ((u > 0) && (v > 0) && (u + v < 1)) {isInside=1;} /* is inside a triangle */
2250
2251                                                 /*  If collision wasn't found but the face is a quad
2252                                                 *       do another check for the second half */
2253                                                 if ((!isInside) && mface[i].v4)
2254                                                 {
2255
2256                                                         /* change d2 to test the other half     */
2257                                                         sub_v2_v2v2(d2,  tface[i].uv[3], tface[i].uv[0]);       // uv3 - uv0
2258
2259                                                         /* test again   */
2260                                                         dot00 = d1[0]*d1[0] + d1[1]*d1[1];
2261                                                         dot01 = d1[0]*d2[0] + d1[1]*d2[1];
2262                                                         dot02 = d1[0]*d3[0] + d1[1]*d3[1];
2263                                                         dot11 = d2[0]*d2[0] + d2[1]*d2[1];
2264                                                         dot12 = d2[0]*d3[0] + d2[1]*d3[1];
2265
2266                                                         invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
2267                                                         u = (dot11 * dot02 - dot01 * dot12) * invDenom;
2268                                                         v = (dot00 * dot12 - dot01 * dot02) * invDenom;
2269
2270                                                         if ((u > 0) && (v > 0) && (u + v < 1)) {isInside=2;} /* is inside the second half of the quad */
2271
2272                                                 }
2273
2274                                                 /*
2275                                                 *       If point was inside the face
2276                                                 */
2277                                                 if (isInside != 0) {
2278
2279                                                         float uv1co[2], uv2co[2], uv3co[2], uv[2];
2280                                                         int j;
2281
2282                                                         /* Get triagnle uvs     */
2283                                                         if (isInside==1) {
2284                                                                 copy_v2_v2(uv1co, tface[i].uv[0]);
2285                                                                 copy_v2_v2(uv2co, tface[i].uv[1]);
2286                                                                 copy_v2_v2(uv3co, tface[i].uv[2]);
2287                                                         }
2288                                                         else {
2289                                                                 copy_v2_v2(uv1co, tface[i].uv[0]);
2290                                                                 copy_v2_v2(uv2co, tface[i].uv[2]);
2291                                                                 copy_v2_v2(uv3co, tface[i].uv[3]);
2292                                                         }
2293
2294                                                         /* Add b-weights per anti-aliasing sample       */
2295                                                         for (j=0; j<aa_samples; j++) {
2296                                                                 uv[0] = point[0][0] + jitter5sample[j*2] / w;
2297                                                                 uv[1] = point[0][1] + jitter5sample[j*2+1] / h;
2298
2299                                                                 barycentric_weights_v2(uv1co, uv2co, uv3co, uv, tempWeights[index*aa_samples+j].v);
2300                                                         }
2301
2302                                                         /* Set surface point face values        */
2303                                                         tPoint->face_index = i;                                                 /* face index */
2304                                                         tPoint->quad = (isInside == 2) ? 1 : 0;         /* quad or tri part*/
2305
2306                                                         /* save vertex indexes  */
2307                                                         tPoint->v1 = mface[i].v1;
2308                                                         tPoint->v2 = (isInside == 2) ? mface[i].v3 : mface[i].v2;
2309                                                         tPoint->v3 = (isInside == 2) ? mface[i].v4 : mface[i].v3;
2310
2311                                                         sample = 5;     /* make sure we exit sample loop as well */
2312                                                         break;
2313                                                 }
2314                                         }
2315                                 } /* sample loop */
2316                         }
2317                 }
2318
2319                 /*
2320                 *       Now loop through every pixel that was left without index
2321                 *       and find if they have neighboring pixels that have an index.
2322                 *       If so use that polygon as pixel surface.
2323                 *       (To avoid seams on uv island edges)
2324                 */
2325                 #pragma omp parallel for schedule(static)
2326                 for (ty = 0; ty < h; ty++)
2327                 {
2328                         int tx;
2329                         for (tx = 0; tx < w; tx++)
2330                         {
2331                                 int index = tx+w*ty;
2332                                 PaintUVPoint *tPoint = (&tempPoints[index]);
2333
2334                                 /* If point isnt't on canvas mesh       */
2335                                 if (tPoint->face_index == -1) {
2336                                         int u_min, u_max, v_min, v_max;
2337                                         int u,v, ind;
2338                                         float point[2];
2339
2340                                         /* get loop area        */
2341                                         u_min = (tx > 0) ? -1 : 0;
2342                                         u_max = (tx < (w-1)) ? 1 : 0;
2343                                         v_min = (ty > 0) ? -1 : 0;
2344                                         v_max = (ty < (h-1)) ? 1 : 0;
2345
2346                                         point[0] = ((float)tx + 0.5f) / w;
2347                                         point[1] = ((float)ty + 0.5f) / h;
2348
2349                                         /* search through defined area for neighbor     */
2350                                         for (u=u_min; u<=u_max; u++)
2351                                                 for (v=v_min; v<=v_max; v++) {
2352                                                         /* if not this pixel itself     */
2353                                                         if (u!=0 || v!=0) {
2354                                                                 ind = (tx+u)+w*(ty+v);
2355
2356                                                                 /* if neighbor has index        */
2357                                                                 if (tempPoints[ind].face_index != -1) {
2358
2359                                                                         float uv1co[2], uv2co[2], uv3co[2], uv[2];
2360                                                                         int i = tempPoints[ind].face_index, j;
2361
2362                                                                         /* Now calculate pixel data for this pixel as it was on polygon surface */
2363                                                                         if (!tempPoints[ind].quad) {
2364                                                                                 copy_v2_v2(uv1co, tface[i].uv[0]);
2365                                                                                 copy_v2_v2(uv2co, tface[i].uv[1]);
2366                                                                                 copy_v2_v2(uv3co, tface[i].uv[2]);
2367                                                                         }
2368                                                                         else {
2369                                                                                 copy_v2_v2(uv1co, tface[i].uv[0]);
2370                                                                                 copy_v2_v2(uv2co, tface[i].uv[2]);
2371                                                                                 copy_v2_v2(uv3co, tface[i].uv[3]);
2372                                                                         }
2373
2374                                                                         /* Add b-weights per anti-aliasing sample       */
2375                                                                         for (j=0; j<aa_samples; j++) {
2376
2377                                                                                 uv[0] = point[0] + jitter5sample[j*2] / w;
2378                                                                                 uv[1] = point[1] + jitter5sample[j*2+1] / h;
2379                                                                                 barycentric_weights_v2(uv1co, uv2co, uv3co, uv, tempWeights[index*aa_samples+j].v);
2380                                                                         }
2381
2382                                                                         /* Set values   */
2383                                                                         tPoint->neighbour_pixel = ind;                          // face index
2384                                                                         tPoint->quad = tempPoints[ind].quad;            // quad or tri
2385
2386                                                                         /* save vertex indexes  */
2387                                                                         tPoint->v1 = mface[i].v1;
2388                                                                         tPoint->v2 = (tPoint->quad) ? mface[i].v3 : mface[i].v2;
2389                                                                         tPoint->v3 = (tPoint->quad) ? mface[i].v4 : mface[i].v3;
2390
2391                                                                         u = u_max + 1;  /* make sure we exit outer loop as well */
2392                                                                         break;
2393                                                                 }
2394                                                 }
2395                                         }
2396                                 }
2397                         }
2398                 }
2399
2400                 /*
2401                 *       When base loop is over convert found neighbor indexes to real ones
2402                 *       Also count the final number of active surface points
2403                 */
2404                 for (ty = 0; ty < h; ty++)
2405                 {
2406                         int tx;
2407                         for (tx = 0; tx < w; tx++)
2408                         {
2409                                 int index = tx+w*ty;
2410                                 PaintUVPoint *tPoint = (&tempPoints[index]);
2411
2412                                 if (tPoint->face_index == -1 && tPoint->neighbour_pixel != -1) tPoint->face_index = tempPoints[tPoint->neighbour_pixel].face_index;
2413                                 if (tPoint->face_index != -1) active_points++;
2414                         }
2415                 }
2416
2417                 /*      Generate surface adjacency data. */
2418                 {
2419                         int i, cursor=0;
2420
2421                         /* Create a temporary array of final indexes (before unassigned
2422                         *  pixels have been dropped) */
2423                         for (i=0; i<w*h; i++) {
2424                                 if (tempPoints[i].face_index != -1) {
2425                                         final_index[i] = cursor;
2426                                         cursor++;
2427                                 }
2428                         }
2429                         /* allocate memory */
2430                         sData->total_points = w*h;
2431                         dynamicPaint_initAdjacencyData(surface, 1);
2432
2433                         if (sData->adj_data) {
2434                                 PaintAdjData *ed = sData->adj_data;
2435                                 unsigned int n_pos = 0;
2436                                 for (ty = 0; ty < h; ty++)
2437                                 {
2438                                         int tx;
2439                                         for (tx = 0; tx < w; tx++)
2440                                         {
2441                                                 int i, index = tx+w*ty;
2442
2443                                                 if (tempPoints[index].face_index != -1) {
2444                                                         ed->n_index[final_index[index]] = n_pos;
2445                                                         ed->n_num[final_index[index]] = 0;
2446
2447                                                         for (i=0; i<8; i++) {
2448
2449                                                                 /* Try to find a neighboring pixel in defined direction
2450                                                                 *  If not found, -1 is returned */
2451                                                                 int n_target = dynamicPaint_findNeighbourPixel(tempPoints, dm, uvname, w, h, tx, ty, i);
2452
2453                                                                 if (n_target >= 0) {
2454                                                                         ed->n_target[n_pos] = final_index[n_target];
2455                                                                         ed->n_num[final_index[index]]++;
2456                                                                         n_pos++;
2457                                                                 }
2458                                                                 else if (n_target == ON_MESH_EDGE || n_target == OUT_OF_TEXTURE) {
2459                                                                         ed->flags[final_index[index]] |= ADJ_ON_MESH_EDGE;
2460                                                                 }
2461                                                         }
2462                                                 }
2463                                         }
2464                                 }
2465                         }
2466                 }
2467
2468                 /* Create final surface data without inactive points */
2469                 {
2470                         ImgSeqFormatData *f_data = MEM_callocN(sizeof(struct ImgSeqFormatData), "ImgSeqFormatData");
2471                         if (f_data) {
2472                                 f_data->uv_p = MEM_callocN(active_points*sizeof(struct PaintUVPoint), "PaintUVPoint");
2473                                 f_data->barycentricWeights = MEM_callocN(active_points*aa_samples*sizeof(struct Vec3f), "PaintUVPoint");
2474
2475                                 if (!f_data->uv_p || !f_data->barycentricWeights) error=1;
2476                         }
2477                         else error=1;
2478
2479                         sData->total_points = active_points;
2480                         
2481                         /* in case of allocation error, free everything */
2482                         if (error) {
2483                                 if (f_data) {
2484                                         if (f_data->uv_p) MEM_freeN(f_data->uv_p);
2485                                         if (f_data->barycentricWeights) MEM_freeN(f_data->barycentricWeights);
2486                                         MEM_freeN(f_data);
2487                                 }
2488                         }
2489                         else {
2490                                 int index, cursor = 0;
2491                                 sData->total_points = active_points;
2492                                 sData->format_data = f_data;
2493
2494                                 for(index = 0; index < (w*h); index++) {
2495                                         if (tempPoints[index].face_index != -1) {
2496                                                 memcpy(&f_data->uv_p[cursor], &tempPoints[index], sizeof(PaintUVPoint));
2497                                                 memcpy(&f_data->barycentricWeights[cursor*aa_samples], &tempWeights[index*aa_samples], sizeof(Vec3f)*aa_samples);
2498                                                 cursor++;
2499                                         }
2500                                 }
2501                         }
2502                 }
2503         }
2504         if (error==1) setError(canvas, "Not enough free memory.");
2505
2506         if (faceBB) MEM_freeN(faceBB);
2507         if (tempPoints) MEM_freeN(tempPoints);
2508         if (tempWeights) MEM_freeN(tempWeights);
2509         if (final_index) MEM_freeN(final_index);
2510
2511         /* Init surface type data */
2512         if (!error) {
2513                 dynamicPaint_allocateSurfaceType(surface);
2514
2515 #if 0
2516                 /*  -----------------------------------------------------------------
2517                 *       For debug, output pixel statuses to the color map
2518                 *       -----------------------------------------------------------------*/
2519                 #pragma omp parallel for schedule(static)
2520                 for (index = 0; index < sData->total_points; index++)
2521                 {
2522                         ImgSeqFormatData *f_data = (ImgSeqFormatData*)sData->format_data;
2523                         PaintUVPoint *uvPoint = &((PaintUVPoint*)f_data->uv_p)[index];
2524                         PaintPoint *pPoint = &((PaintPoint*)sData->type_data)[index];
2525                         pPoint->alpha=1.0f;
2526
2527                         /* Every pixel that is assigned as "edge pixel" gets blue color */
2528                         if (uvPoint->neighbour_pixel != -1) pPoint->color[2] = 1.0f;
2529                         /* and every pixel that finally got an polygon gets red color   */
2530                         if (uvPoint->face_index != -1) pPoint->color[0] = 1.0f;
2531                         /* green color shows pixel face index hash      */
2532                         if (uvPoint->face_index != -1) pPoint->color[1] = (float)(uvPoint->face_index % 255)/256.0f;
2533                 }
2534
2535 #endif
2536                 dynamicPaint_setInitialColor(surface);
2537         }
2538
2539         return (error == 0);
2540 }
2541
2542 /*
2543 *       Outputs an image file from uv surface data.
2544 */
2545 void dynamicPaint_outputSurfaceImage(DynamicPaintSurface *surface, char* filename, short output_layer)
2546 {
2547         int index;
2548         ImBuf* ibuf = NULL;
2549         PaintSurfaceData *sData = surface->data;
2550         ImgSeqFormatData *f_data = (ImgSeqFormatData*)sData->format_data;
2551         /* OpenEXR or PNG       */
2552         int format = (surface->image_fileformat & MOD_DPAINT_IMGFORMAT_OPENEXR) ? R_IMF_IMTYPE_OPENEXR : R_IMF_IMTYPE_PNG;
2553         char output_file[FILE_MAX];
2554
2555         if (!sData || !sData->type_data) {setError(surface->canvas, "Image save failed: Invalid surface.");return;}
2556         /* if selected format is openexr, but current build doesnt support one */
2557         #ifndef WITH_OPENEXR
2558         if (format == R_IMF_IMTYPE_OPENEXR) format = R_IMF_IMTYPE_PNG;
2559         #endif
2560         BLI_strncpy(output_file, filename, sizeof(output_file));
2561         BKE_add_image_extension(output_file, format);
2562
2563         /* Validate output file path    */
2564         BLI_path_abs(output_file, G.main->name);
2565         BLI_make_existing_file(output_file);
2566
2567         /* Init image buffer    */
2568         ibuf = IMB_allocImBuf(surface->image_resolution, surface->image_resolution, 32, IB_rectfloat);
2569         if (ibuf == NULL) {setError(surface->canvas, "Image save failed: Not enough free memory.");return;}
2570
2571         #pragma omp parallel for schedule(static)
2572         for (index = 0; index < sData->total_points; index++)
2573         {
2574                 int pos=f_data->uv_p[index].pixel_index*4;      /* image buffer position */
2575
2576                 /* Set values of preferred type */
2577                 if (output_layer == 1) {
2578                         /* wetmap */
2579                         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
2580                                 PaintPoint *point = &((PaintPoint*)sData->type_data)[index];
2581                                 float value = (point->wetness > 1.0f) ? 1.0f : point->wetness;
2582
2583                                 ibuf->rect_float[pos]=value;
2584                                 ibuf->rect_float[pos+1]=value;
2585                                 ibuf->rect_float[pos+2]=value;
2586                                 ibuf->rect_float[pos+3]=1.0f;
2587                         }
2588                 }
2589                 else if (output_layer == 0) {
2590                         /* Paintmap */
2591                         if (surface->type == MOD_DPAINT_SURFACE_T_PAINT) {
2592                                 PaintPoint *point = &((PaintPoint*)sData->type_data)[index];
2593
2594                                 /* blend wet and dry layers */
2595                                 blendColors(point->color, point->alpha, point->e_color, point->e_alpha, &ibuf->rect_float[pos]);
2596
2597                                 /* Multiply color by alpha if enabled   */
2598                                 if (surface->flags & MOD_DPAINT_MULALPHA) {
2599                                         ibuf->rect_float[pos]   *= ibuf->rect_float[pos+3];
2600                                         ibuf->rect_float[pos+1] *= ibuf->rect_float[pos+3];
2601                                         ibuf->rect_float[pos+2] *= ibuf->rect_float[pos+3];
2602                                 }
2603                         }
2604                         /* displace */
2605                         else if (surface->type == MOD_DPAINT_SURFACE_T_DISPLACE) {
2606                                 float depth = ((float*)sData->type_data)[index];
2607                                 if (surface->depth_clamp)
2608                                         depth /= surface->depth_clamp;
2609
2610                                 if (surface->disp_type == MOD_DPAINT_DISP_DISPLACE) {
2611                                         depth = (0.5f - depth/2.0f);
2612                                 }
2613
2614                                 CLAMP(depth, 0.0f, 1.0f);
2615
2616                                 ibuf->rect_float[pos]=depth;
2617                                 ibuf->rect_float[pos+1]=depth;
2618                                 ibuf->rect_float[pos+2]=depth;
2619                                 ibuf->rect_float[pos+3]=1.0f;
2620                         }
2621                         /* waves */
2622                         else if (surface->type == MOD_DPAINT_SURFACE_T_WAVE) {
2623                                 PaintWavePoint *wPoint = &((PaintWavePoint*)sData->type_data)[index];
2624                                 float depth = wPoint->height;
2625                                 if (surface->depth_clamp)
2626                                                 depth /= surface->depth_clamp;
2627                                 depth = (0.5f + depth/2.0f);
2628                                 CLAMP(depth, 0.0f, 1.0f);
2629
2630                                 ibuf->rect_float[pos]=depth;
2631                                 ibuf->rect_float[pos+1]=depth;
2632                                 ibuf->rect_float[pos+2]=depth;
2633                                 ibuf->rect_float[pos+3]=1.0f;
2634                         }
2635                 }
2636         }
2637
2638         /* Set output format, png in case exr isnt supported */
2639         ibuf->ftype= PNG|95;
2640 #ifdef WITH_OPENEXR
2641         if (format == R_IMF_IMTYPE_OPENEXR) {   /* OpenEXR 32-bit float */
2642                 ibuf->ftype = OPENEXR | OPENEXR_COMPRESS;
2643         }
2644 #endif
2645
2646         /* Save image */
2647         IMB_saveiff(ibuf, output_file, IB_rectfloat);
2648         IMB_freeImBuf(ibuf);
2649 }
2650
2651
2652 /***************************** Material / Texture Sampling ******************************/
2653
2654 /* stores a copy of required materials to allow doing adjustments
2655 *  without interfering the render/preview */
2656 typedef struct BrushMaterials {
2657         Material *mat;
2658         Material **ob_mats;
2659         int tot;
2660 } BrushMaterials;
2661
2662 /* Initialize materials for brush object:
2663 *  Calculates inverse matrices for linked objects, updates
2664 *  volume caches etc. */
2665 static void dynamicPaint_updateBrushMaterials(Object *brushOb, Material *ui_mat, Scene *scene, BrushMaterials *bMats)
2666 {
2667         /* Calculate inverse transformation matrix
2668         *  for this object */
2669         invert_m4_m4(brushOb->imat, brushOb->obmat);
2670         copy_m4_m4(brushOb->imat_ren, brushOb->imat);
2671
2672         /* Now process every material linked to this brush object */
2673         if ((ui_mat == NULL) && brushOb->mat && brushOb->totcol) {
2674                 int i, tot=(*give_totcolp(brushOb));
2675
2676                 /* allocate material pointer array */
2677                 if (tot) {
2678                         bMats->ob_mats = MEM_callocN(sizeof(Material*)*(tot), "BrushMaterials");
2679                         for (i=0; i<tot; i++) {
2680                                 bMats->ob_mats[i] = RE_init_sample_material(give_current_material(brushOb,(i+1)), scene);
2681                         }
2682                 }
2683                 bMats->tot = tot;
2684         }
2685         else {
2686                 bMats->mat = RE_init_sample_material(ui_mat, scene);
2687         }
2688 }
2689
2690 /* free all data allocated by dynamicPaint_updateBrushMaterials() */
2691 static void dynamicPaint_freeBrushMaterials(BrushMaterials *bMats)
2692 {
2693         /* Now process every material linked to this brush object */
2694         if (bMats->ob_mats) {
2695                 int i;
2696                 for (i=0; i<bMats->tot; i++) {
2697                         RE_free_sample_material(bMats->ob_mats[i]);
2698                 }
2699                 MEM_freeN(bMats->ob_mats);
2700         }
2701         else if (bMats->mat) {
2702                 RE_free_sample_material(bMats->mat);
2703         }
2704 }
2705
2706 /*
2707 *       Get material diffuse color and alpha (including linked textures) in given coordinates
2708 */
2709 void dynamicPaint_doMaterialTex(BrushMaterials *bMats, float color[3], float *alpha, Object *brushOb, const float volume_co[3], const float surface_co[3], int faceIndex, short isQuad, DerivedMesh *orcoDm)
2710 {
2711         Material *mat = bMats->mat;
2712         MFace *mface = orcoDm->getTessFaceArray(orcoDm);
2713
2714         /* If no material defined, use the one assigned to the mesh face */
2715         if (mat == NULL) {
2716                 if (bMats->ob_mats) {
2717                         int mat_nr = mface[faceIndex].mat_nr;
2718                         if (mat_nr >= (*give_totcolp(brushOb))) return;
2719                         mat = bMats->ob_mats[mat_nr];
2720                         if (mat == NULL) return;        /* No material assigned */
2721                 }
2722                 else return;
2723         }
2724
2725         RE_sample_material_color(mat, color, alpha, volume_co, surface_co, faceIndex, isQuad, orcoDm, brushOb);
2726 }
2727
2728
2729 /***************************** Ray / Nearest Point Utils ******************************/
2730
2731
2732 /*  A modified callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
2733 *   userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
2734 *  
2735 *       To optimize brush detection speed this doesn't calculate hit coordinates or normal.
2736 *       If ray hit the second half of a quad, no[0] is set to 1.0f.
2737 */
2738 static void mesh_faces_spherecast_dp(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
2739 {
2740         const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
2741         MVert *vert     = data->vert;
2742         MFace *face = data->face + index;
2743         short quad = 0;
2744
2745         float *t0, *t1, *t2, *t3;
2746         t0 = vert[ face->v1 ].co;
2747         t1 = vert[ face->v2 ].co;
2748         t2 = vert[ face->v3 ].co;
2749         t3 = face->v4 ? vert[ face->v4].co : NULL;
2750
2751         do
2752         {       
2753                 float dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
2754
2755                 if(dist >= 0 && dist < hit->dist)
2756                 {
2757                         hit->index = index;
2758                         hit->dist = dist;
2759                         hit->no[0] = (quad) ? 1.0f : 0.0f;
2760                 }
2761
2762                 t1 = t2;
2763                 t2 = t3;
2764                 t3 = NULL;
2765                 quad = 1;
2766
2767         } while(t2);
2768 }
2769
2770 /* A modified callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
2771 *  userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
2772 *  
2773 *       To optimize brush detection speed this doesn't calculate hit normal.
2774 *       If ray hit the second half of a quad, no[0] is set to 1.0f, else 0.0f
2775 */
2776 static void mesh_faces_nearest_point_dp(void *userdata, int index, const float *co, BVHTreeNearest *nearest)
2777 {
2778         const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
2779         MVert *vert     = data->vert;
2780         MFace *face = data->face + index;
2781         short quad = 0;
2782
2783         float *t0, *t1, *t2, *t3;
2784         t0 = vert[ face->v1 ].co;
2785         t1 = vert[ face->v2 ].co;
2786         t2 = vert[ face->v3 ].co;
2787         t3 = face->v4 ? vert[ face->v4].co : NULL;
2788
2789         do
2790         {       
2791                 float nearest_tmp[3], dist;
2792                 int vertex, edge;
2793                 
2794                 dist = nearest_point_in_tri_surface(t0, t1, t2, co, &vertex, &edge, nearest_tmp);
2795                 if(dist < nearest->dist)
2796                 {
2797                         nearest->index = index;
2798                         nearest->dist = dist;
2799                         copy_v3_v3(nearest->co, nearest_tmp);
2800                         nearest->no[0] = (quad) ? 1.0f : 0.0f;
2801                 }
2802
2803                 t1 = t2;
2804                 t2 =&n