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