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