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