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