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