Pose brush: Smooth Iterations Brush Property
[blender.git] / source / blender / editors / sculpt_paint / sculpt.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  * The Original Code is Copyright (C) 2006 by Nicholas Bishop
17  * All rights reserved.
18  * Implements the Sculpt Mode tools
19  */
20
21 /** \file
22  * \ingroup edsculpt
23  */
24
25 #include "MEM_guardedalloc.h"
26
27 #include "BLI_math.h"
28 #include "BLI_blenlib.h"
29 #include "BLI_dial_2d.h"
30 #include "BLI_gsqueue.h"
31 #include "BLI_ghash.h"
32 #include "BLI_hash.h"
33 #include "BLI_task.h"
34 #include "BLI_utildefines.h"
35
36 #include "BLT_translation.h"
37
38 #include "DNA_customdata_types.h"
39 #include "DNA_mesh_types.h"
40 #include "DNA_meshdata_types.h"
41 #include "DNA_node_types.h"
42 #include "DNA_object_types.h"
43 #include "DNA_scene_types.h"
44 #include "DNA_brush_types.h"
45
46 #include "BKE_brush.h"
47 #include "BKE_ccg.h"
48 #include "BKE_colortools.h"
49 #include "BKE_context.h"
50 #include "BKE_image.h"
51 #include "BKE_key.h"
52 #include "BKE_library.h"
53 #include "BKE_main.h"
54 #include "BKE_mesh.h"
55 #include "BKE_mesh_mapping.h"
56 #include "BKE_mirror.h"
57 #include "BKE_modifier.h"
58 #include "BKE_multires.h"
59 #include "BKE_node.h"
60 #include "BKE_object.h"
61 #include "BKE_paint.h"
62 #include "BKE_particle.h"
63 #include "BKE_pbvh.h"
64 #include "BKE_pointcache.h"
65 #include "BKE_report.h"
66 #include "BKE_scene.h"
67 #include "BKE_screen.h"
68 #include "BKE_subdiv_ccg.h"
69 #include "BKE_subsurf.h"
70
71 #include "DEG_depsgraph.h"
72
73 #include "WM_api.h"
74 #include "WM_types.h"
75 #include "WM_message.h"
76 #include "WM_toolsystem.h"
77
78 #include "ED_sculpt.h"
79 #include "ED_object.h"
80 #include "ED_screen.h"
81 #include "ED_view3d.h"
82 #include "paint_intern.h"
83 #include "sculpt_intern.h"
84
85 #include "RNA_access.h"
86 #include "RNA_define.h"
87
88 #include "UI_interface.h"
89 #include "UI_resources.h"
90
91 #include "bmesh.h"
92 #include "bmesh_tools.h"
93
94 #include <math.h>
95 #include <stdlib.h>
96 #include <string.h>
97
98 /* Sculpt PBVH abstraction API
99  *
100  * This is read-only, for writing use PBVH vertex iterators. There vd.index matches
101  * the indices used here.
102  *
103  * For multires, the same vertex in multiple grids is counted multiple times, with
104  * different index for each grid. */
105
106 static void sculpt_vertex_random_access_init(SculptSession *ss)
107 {
108   if (BKE_pbvh_type(ss->pbvh) == PBVH_BMESH) {
109     BM_mesh_elem_index_ensure(ss->bm, BM_VERT);
110   }
111 }
112
113 static int sculpt_vertex_count_get(SculptSession *ss)
114 {
115   switch (BKE_pbvh_type(ss->pbvh)) {
116     case PBVH_FACES:
117       return ss->totvert;
118     case PBVH_BMESH:
119       return BM_mesh_elem_count(BKE_pbvh_get_bmesh(ss->pbvh), BM_VERT);
120     case PBVH_GRIDS:
121       return BKE_pbvh_get_grid_num_vertices(ss->pbvh);
122   }
123
124   return 0;
125 }
126
127 const float *sculpt_vertex_co_get(SculptSession *ss, int index)
128 {
129   switch (BKE_pbvh_type(ss->pbvh)) {
130     case PBVH_FACES:
131       return ss->mvert[index].co;
132     case PBVH_BMESH:
133       return BM_vert_at_index(BKE_pbvh_get_bmesh(ss->pbvh), index)->co;
134     case PBVH_GRIDS: {
135       const CCGKey *key = BKE_pbvh_get_grid_key(ss->pbvh);
136       const int grid_index = index / key->grid_area;
137       const int vertex_index = index - grid_index * key->grid_area;
138       CCGElem *elem = BKE_pbvh_get_grids(ss->pbvh)[grid_index];
139       return CCG_elem_co(key, CCG_elem_offset(key, elem, vertex_index));
140     }
141   }
142   return NULL;
143 }
144
145 static void sculpt_vertex_normal_get(SculptSession *ss, int index, float no[3])
146 {
147   switch (BKE_pbvh_type(ss->pbvh)) {
148     case PBVH_FACES:
149       normal_short_to_float_v3(no, ss->mvert[index].no);
150       return;
151     case PBVH_BMESH:
152       copy_v3_v3(no, BM_vert_at_index(BKE_pbvh_get_bmesh(ss->pbvh), index)->no);
153       break;
154     case PBVH_GRIDS: {
155       const CCGKey *key = BKE_pbvh_get_grid_key(ss->pbvh);
156       const int grid_index = index / key->grid_area;
157       const int vertex_index = index - grid_index * key->grid_area;
158       CCGElem *elem = BKE_pbvh_get_grids(ss->pbvh)[grid_index];
159       copy_v3_v3(no, CCG_elem_no(key, CCG_elem_offset(key, elem, vertex_index)));
160       break;
161     }
162   }
163 }
164
165 static float sculpt_vertex_mask_get(SculptSession *ss, int index)
166 {
167   BMVert *v;
168   float *mask;
169   switch (BKE_pbvh_type(ss->pbvh)) {
170     case PBVH_FACES:
171       return ss->vmask[index];
172     case PBVH_BMESH:
173       v = BM_vert_at_index(BKE_pbvh_get_bmesh(ss->pbvh), index);
174       mask = BM_ELEM_CD_GET_VOID_P(v, CustomData_get_offset(&ss->bm->vdata, CD_PAINT_MASK));
175       return *mask;
176     case PBVH_GRIDS: {
177       const CCGKey *key = BKE_pbvh_get_grid_key(ss->pbvh);
178       const int grid_index = index / key->grid_area;
179       const int vertex_index = index - grid_index * key->grid_area;
180       CCGElem *elem = BKE_pbvh_get_grids(ss->pbvh)[grid_index];
181       return *CCG_elem_mask(key, CCG_elem_offset(key, elem, vertex_index));
182     }
183   }
184
185   return 0.0f;
186 }
187
188 static int sculpt_active_vertex_get(SculptSession *ss)
189 {
190   switch (BKE_pbvh_type(ss->pbvh)) {
191     case PBVH_FACES:
192       return ss->active_vertex_index;
193     case PBVH_BMESH:
194       return ss->active_vertex_index;
195     case PBVH_GRIDS:
196       return ss->active_vertex_index;
197   }
198
199   return 0;
200 }
201
202 static const float *sculpt_active_vertex_co_get(SculptSession *ss)
203 {
204   return sculpt_vertex_co_get(ss, sculpt_active_vertex_get(ss));
205 }
206
207 static void sculpt_active_vertex_normal_get(SculptSession *ss, float normal[3])
208 {
209   sculpt_vertex_normal_get(ss, sculpt_active_vertex_get(ss), normal);
210 }
211
212 #define SCULPT_VERTEX_NEIGHBOR_FIXED_CAPACITY 256
213
214 typedef struct SculptVertexNeighborIter {
215   /* Storage */
216   int *neighbors;
217   int size;
218   int capacity;
219   int neighbors_fixed[SCULPT_VERTEX_NEIGHBOR_FIXED_CAPACITY];
220
221   /* Internal iterator. */
222   int num_duplicates;
223   int i;
224
225   /* Public */
226   int index;
227   bool is_duplicate;
228 } SculptVertexNeighborIter;
229
230 static void sculpt_vertex_neighbor_add(SculptVertexNeighborIter *iter, int neighbor_index)
231 {
232   for (int i = 0; i < iter->size; i++) {
233     if (iter->neighbors[i] == neighbor_index) {
234       return;
235     }
236   }
237
238   if (iter->size >= iter->capacity) {
239     iter->capacity += SCULPT_VERTEX_NEIGHBOR_FIXED_CAPACITY;
240
241     if (iter->neighbors == iter->neighbors_fixed) {
242       iter->neighbors = MEM_mallocN(iter->capacity * sizeof(int), "neighbor array");
243       memcpy(iter->neighbors, iter->neighbors_fixed, sizeof(int) * iter->size);
244     }
245     else {
246       iter->neighbors = MEM_reallocN_id(
247           iter->neighbors, iter->capacity * sizeof(int), "neighbor array");
248     }
249   }
250
251   iter->neighbors[iter->size] = neighbor_index;
252   iter->size++;
253 }
254
255 static void sculpt_vertex_neighbors_get_bmesh(SculptSession *ss,
256                                               int index,
257                                               SculptVertexNeighborIter *iter)
258 {
259   BMVert *v = BM_vert_at_index(ss->bm, index);
260   BMIter liter;
261   BMLoop *l;
262   iter->size = 0;
263   iter->num_duplicates = 0;
264   iter->capacity = SCULPT_VERTEX_NEIGHBOR_FIXED_CAPACITY;
265   iter->neighbors = iter->neighbors_fixed;
266
267   int i = 0;
268   BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
269     const BMVert *adj_v[2] = {l->prev->v, l->next->v};
270     for (i = 0; i < ARRAY_SIZE(adj_v); i++) {
271       const BMVert *v_other = adj_v[i];
272       if (BM_elem_index_get(v_other) != (int)index) {
273         sculpt_vertex_neighbor_add(iter, BM_elem_index_get(v_other));
274       }
275     }
276   }
277 }
278
279 static void sculpt_vertex_neighbors_get_faces(SculptSession *ss,
280                                               int index,
281                                               SculptVertexNeighborIter *iter)
282 {
283   int i;
284   MeshElemMap *vert_map = &ss->pmap[(int)index];
285   iter->size = 0;
286   iter->num_duplicates = 0;
287   iter->capacity = SCULPT_VERTEX_NEIGHBOR_FIXED_CAPACITY;
288   iter->neighbors = iter->neighbors_fixed;
289
290   for (i = 0; i < ss->pmap[(int)index].count; i++) {
291     const MPoly *p = &ss->mpoly[vert_map->indices[i]];
292     unsigned f_adj_v[2];
293     if (poly_get_adj_loops_from_vert(p, ss->mloop, (int)index, f_adj_v) != -1) {
294       int j;
295       for (j = 0; j < ARRAY_SIZE(f_adj_v); j += 1) {
296         if (f_adj_v[j] != (int)index) {
297           sculpt_vertex_neighbor_add(iter, f_adj_v[j]);
298         }
299       }
300     }
301   }
302 }
303
304 static void sculpt_vertex_neighbors_get_grids(SculptSession *ss,
305                                               const int index,
306                                               const bool include_duplicates,
307                                               SculptVertexNeighborIter *iter)
308 {
309   /* TODO: optimize this. We could fill SculptVertexNeighborIter directly,
310    * maybe provide coordinate and mask pointers directly rather than converting
311    * back and forth between CCGElem and global index. */
312   const CCGKey *key = BKE_pbvh_get_grid_key(ss->pbvh);
313   const int grid_index = index / key->grid_area;
314   const int vertex_index = index - grid_index * key->grid_area;
315
316   SubdivCCGCoord coord = {.grid_index = grid_index,
317                           .x = vertex_index % key->grid_size,
318                           .y = vertex_index / key->grid_size};
319
320   SubdivCCGNeighbors neighbors;
321   BKE_subdiv_ccg_neighbor_coords_get(ss->subdiv_ccg, &coord, include_duplicates, &neighbors);
322
323   iter->size = 0;
324   iter->num_duplicates = neighbors.num_duplicates;
325   iter->capacity = SCULPT_VERTEX_NEIGHBOR_FIXED_CAPACITY;
326   iter->neighbors = iter->neighbors_fixed;
327
328   for (int i = 0; i < neighbors.size; i++) {
329     sculpt_vertex_neighbor_add(iter,
330                                neighbors.coords[i].grid_index * key->grid_area +
331                                    neighbors.coords[i].y * key->grid_size + neighbors.coords[i].x);
332   }
333
334   if (neighbors.coords != neighbors.coords_fixed) {
335     MEM_freeN(neighbors.coords);
336   }
337 }
338
339 static void sculpt_vertex_neighbors_get(SculptSession *ss,
340                                         const int index,
341                                         const bool include_duplicates,
342                                         SculptVertexNeighborIter *iter)
343 {
344   switch (BKE_pbvh_type(ss->pbvh)) {
345     case PBVH_FACES:
346       sculpt_vertex_neighbors_get_faces(ss, index, iter);
347       return;
348     case PBVH_BMESH:
349       sculpt_vertex_neighbors_get_bmesh(ss, index, iter);
350       return;
351     case PBVH_GRIDS:
352       sculpt_vertex_neighbors_get_grids(ss, index, include_duplicates, iter);
353       return;
354   }
355 }
356
357 /* Iterator over neighboring vertices. */
358 #define sculpt_vertex_neighbors_iter_begin(ss, v_index, neighbor_iterator) \
359   sculpt_vertex_neighbors_get(ss, v_index, false, &neighbor_iterator); \
360   for (neighbor_iterator.i = 0; neighbor_iterator.i < neighbor_iterator.size; \
361        neighbor_iterator.i++) { \
362     neighbor_iterator.index = ni.neighbors[ni.i];
363
364 /* Iterate over neighboring and duplicate vertices (for PBVH_GRIDS). Duplicates come
365  * first since they are nearest for floodfill. */
366 #define sculpt_vertex_duplicates_and_neighbors_iter_begin(ss, v_index, neighbor_iterator) \
367   sculpt_vertex_neighbors_get(ss, v_index, true, &neighbor_iterator); \
368   for (neighbor_iterator.i = neighbor_iterator.size - 1; neighbor_iterator.i >= 0; \
369        neighbor_iterator.i--) { \
370     neighbor_iterator.index = ni.neighbors[ni.i]; \
371     neighbor_iterator.is_duplicate = (ni.i >= \
372                                       neighbor_iterator.size - neighbor_iterator.num_duplicates);
373
374 #define sculpt_vertex_neighbors_iter_end(neighbor_iterator) \
375   } \
376   if (neighbor_iterator.neighbors != neighbor_iterator.neighbors_fixed) { \
377     MEM_freeN(neighbor_iterator.neighbors); \
378   } \
379   ((void)0)
380
381 /* Utils */
382 static bool check_vertex_pivot_symmetry(const float vco[3], const float pco[3], const char symm)
383 {
384   bool is_in_symmetry_area = true;
385   for (int i = 0; i < 3; i++) {
386     char symm_it = 1 << i;
387     if (symm & symm_it) {
388       if (pco[i] == 0.0f) {
389         if (vco[i] > 0.0f) {
390           is_in_symmetry_area = false;
391         }
392       }
393       if (vco[i] * pco[i] < 0.0f) {
394         is_in_symmetry_area = false;
395       }
396     }
397   }
398   return is_in_symmetry_area;
399 }
400
401 typedef struct NearestVertexTLSData {
402   int nearest_vertex_index;
403   float nearest_vertex_distance_squared;
404 } NearestVertexTLSData;
405
406 static void do_nearest_vertex_get_task_cb(void *__restrict userdata,
407                                           const int n,
408                                           const TaskParallelTLS *__restrict tls)
409 {
410   SculptThreadedTaskData *data = userdata;
411   SculptSession *ss = data->ob->sculpt;
412   NearestVertexTLSData *nvtd = tls->userdata_chunk;
413   PBVHVertexIter vd;
414
415   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
416   {
417     float distance_squared = len_squared_v3v3(vd.co, data->nearest_vertex_search_co);
418     if (distance_squared < nvtd->nearest_vertex_distance_squared &&
419         distance_squared < data->max_distance_squared) {
420       nvtd->nearest_vertex_index = vd.index;
421       nvtd->nearest_vertex_distance_squared = distance_squared;
422     }
423   }
424   BKE_pbvh_vertex_iter_end;
425 }
426
427 static void nearest_vertex_get_reduce(const void *__restrict UNUSED(userdata),
428                                       void *__restrict chunk_join,
429                                       void *__restrict chunk)
430 {
431   NearestVertexTLSData *join = chunk_join;
432   NearestVertexTLSData *nvtd = chunk;
433   if (join->nearest_vertex_index == -1) {
434     join->nearest_vertex_index = nvtd->nearest_vertex_index;
435     join->nearest_vertex_distance_squared = nvtd->nearest_vertex_distance_squared;
436   }
437   else if (nvtd->nearest_vertex_distance_squared < join->nearest_vertex_distance_squared) {
438     join->nearest_vertex_index = nvtd->nearest_vertex_index;
439     join->nearest_vertex_distance_squared = nvtd->nearest_vertex_distance_squared;
440   }
441 }
442
443 static int sculpt_nearest_vertex_get(
444     Sculpt *sd, Object *ob, float co[3], float max_distance, bool use_original)
445 {
446   SculptSession *ss = ob->sculpt;
447   PBVHNode **nodes = NULL;
448   int totnode;
449   SculptSearchSphereData data = {
450       .ss = ss,
451       .sd = sd,
452       .radius_squared = max_distance * max_distance,
453       .original = use_original,
454       .center = co,
455   };
456   BKE_pbvh_search_gather(ss->pbvh, sculpt_search_sphere_cb, &data, &nodes, &totnode);
457   if (totnode == 0) {
458     return -1;
459   }
460
461   SculptThreadedTaskData task_data = {
462       .sd = sd,
463       .ob = ob,
464       .nodes = nodes,
465       .max_distance_squared = max_distance * max_distance,
466   };
467
468   copy_v3_v3(task_data.nearest_vertex_search_co, co);
469   NearestVertexTLSData nvtd;
470   nvtd.nearest_vertex_index = -1;
471   nvtd.nearest_vertex_distance_squared = FLT_MAX;
472
473   PBVHParallelSettings settings;
474   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
475   settings.func_reduce = nearest_vertex_get_reduce;
476   settings.userdata_chunk = &nvtd;
477   settings.userdata_chunk_size = sizeof(NearestVertexTLSData);
478   BKE_pbvh_parallel_range(0, totnode, &task_data, do_nearest_vertex_get_task_cb, &settings);
479
480   MEM_SAFE_FREE(nodes);
481
482   return nvtd.nearest_vertex_index;
483 }
484
485 static bool is_symmetry_iteration_valid(char i, char symm)
486 {
487   return i == 0 || (symm & i && (symm != 5 || i != 3) && (symm != 6 || (i != 3 && i != 5)));
488 }
489
490 /* Checks if a vertex is inside the brush radius from any of its mirrored axis */
491 static bool sculpt_is_vertex_inside_brush_radius_symm(const float vertex[3],
492                                                       const float br_co[3],
493                                                       float radius,
494                                                       char symm)
495 {
496   for (char i = 0; i <= symm; ++i) {
497     if (is_symmetry_iteration_valid(i, symm)) {
498       float location[3];
499       flip_v3_v3(location, br_co, (char)i);
500       if (len_squared_v3v3(location, vertex) < radius * radius) {
501         return true;
502       }
503     }
504   }
505   return false;
506 }
507
508 /* Sculpt Flood Fill API
509  *
510  * Iterate over connected vertices, starting from one or more initial vertices. */
511
512 typedef struct SculptFloodFill {
513   GSQueue *queue;
514   char *visited_vertices;
515 } SculptFloodFill;
516
517 static void sculpt_floodfill_init(SculptSession *ss, SculptFloodFill *flood)
518 {
519   int vertex_count = sculpt_vertex_count_get(ss);
520   sculpt_vertex_random_access_init(ss);
521
522   flood->queue = BLI_gsqueue_new(sizeof(int));
523   flood->visited_vertices = MEM_callocN(vertex_count * sizeof(char), "visited vertices");
524 }
525
526 static void sculpt_floodfill_add_initial(SculptFloodFill *flood, int index)
527 {
528   BLI_gsqueue_push(flood->queue, &index);
529 }
530
531 static void sculpt_floodfill_add_active(
532     Sculpt *sd, Object *ob, SculptSession *ss, SculptFloodFill *flood, float radius)
533 {
534   /* Add active vertex and symmetric vertices to the queue. */
535   const char symm = sd->paint.symmetry_flags & PAINT_SYMM_AXIS_ALL;
536   for (char i = 0; i <= symm; ++i) {
537     if (is_symmetry_iteration_valid(i, symm)) {
538       int v = -1;
539       if (i == 0) {
540         v = sculpt_active_vertex_get(ss);
541       }
542       else if (radius > 0.0f) {
543         float radius_squared = (radius == FLT_MAX) ? FLT_MAX : radius * radius;
544         float location[3];
545         flip_v3_v3(location, sculpt_active_vertex_co_get(ss), i);
546         v = sculpt_nearest_vertex_get(sd, ob, location, radius_squared, false);
547       }
548       if (v != -1) {
549         sculpt_floodfill_add_initial(flood, v);
550       }
551     }
552   }
553 }
554
555 static void sculpt_floodfill_execute(
556     SculptSession *ss,
557     SculptFloodFill *flood,
558     bool (*func)(SculptSession *ss, int from_v, int to_v, bool is_duplicate, void *userdata),
559     void *userdata)
560 {
561   while (!BLI_gsqueue_is_empty(flood->queue)) {
562     int from_v;
563     BLI_gsqueue_pop(flood->queue, &from_v);
564     SculptVertexNeighborIter ni;
565     sculpt_vertex_duplicates_and_neighbors_iter_begin(ss, from_v, ni)
566     {
567       const int to_v = ni.index;
568       if (flood->visited_vertices[to_v] == 0) {
569         flood->visited_vertices[to_v] = 1;
570
571         if (func(ss, from_v, to_v, ni.is_duplicate, userdata)) {
572           BLI_gsqueue_push(flood->queue, &to_v);
573         }
574       }
575     }
576     sculpt_vertex_neighbors_iter_end(ni);
577   }
578 }
579
580 static void sculpt_floodfill_free(SculptFloodFill *flood)
581 {
582   MEM_SAFE_FREE(flood->visited_vertices);
583   BLI_gsqueue_free(flood->queue);
584   flood->queue = NULL;
585 }
586
587 /** \name Tool Capabilities
588  *
589  * Avoid duplicate checks, internal logic only,
590  * share logic with #rna_def_sculpt_capabilities where possible.
591  *
592  * \{ */
593
594 /* Check if there are any active modifiers in stack
595  * (used for flushing updates at enter/exit sculpt mode) */
596 static bool sculpt_has_active_modifiers(Scene *scene, Object *ob)
597 {
598   ModifierData *md;
599   VirtualModifierData virtualModifierData;
600
601   md = modifiers_getVirtualModifierList(ob, &virtualModifierData);
602
603   /* exception for shape keys because we can edit those */
604   for (; md; md = md->next) {
605     if (modifier_isEnabled(scene, md, eModifierMode_Realtime)) {
606       return 1;
607     }
608   }
609
610   return 0;
611 }
612
613 static bool sculpt_tool_needs_original(const char sculpt_tool)
614 {
615   return ELEM(sculpt_tool,
616               SCULPT_TOOL_GRAB,
617               SCULPT_TOOL_ROTATE,
618               SCULPT_TOOL_THUMB,
619               SCULPT_TOOL_LAYER,
620               SCULPT_TOOL_DRAW_SHARP,
621               SCULPT_TOOL_ELASTIC_DEFORM,
622               SCULPT_TOOL_POSE);
623 }
624
625 static bool sculpt_tool_is_proxy_used(const char sculpt_tool)
626 {
627   return ELEM(sculpt_tool, SCULPT_TOOL_SMOOTH, SCULPT_TOOL_LAYER, SCULPT_TOOL_POSE);
628 }
629
630 static bool sculpt_brush_use_topology_rake(const SculptSession *ss, const Brush *brush)
631 {
632   return SCULPT_TOOL_HAS_TOPOLOGY_RAKE(brush->sculpt_tool) &&
633          (brush->topology_rake_factor > 0.0f) && (ss->bm != NULL);
634 }
635
636 /**
637  * Test whether the #StrokeCache.sculpt_normal needs update in #do_brush_action
638  */
639 static int sculpt_brush_needs_normal(const SculptSession *ss, const Brush *brush)
640 {
641   return ((SCULPT_TOOL_HAS_NORMAL_WEIGHT(brush->sculpt_tool) &&
642            (ss->cache->normal_weight > 0.0f)) ||
643
644           ELEM(brush->sculpt_tool,
645                SCULPT_TOOL_BLOB,
646                SCULPT_TOOL_CREASE,
647                SCULPT_TOOL_DRAW,
648                SCULPT_TOOL_DRAW_SHARP,
649                SCULPT_TOOL_LAYER,
650                SCULPT_TOOL_NUDGE,
651                SCULPT_TOOL_ROTATE,
652                SCULPT_TOOL_ELASTIC_DEFORM,
653                SCULPT_TOOL_THUMB) ||
654
655           (brush->mtex.brush_map_mode == MTEX_MAP_MODE_AREA)) ||
656          sculpt_brush_use_topology_rake(ss, brush);
657 }
658 /** \} */
659
660 static bool sculpt_brush_needs_rake_rotation(const Brush *brush)
661 {
662   return SCULPT_TOOL_HAS_RAKE(brush->sculpt_tool) && (brush->rake_factor != 0.0f);
663 }
664
665 typedef enum StrokeFlags {
666   CLIP_X = 1,
667   CLIP_Y = 2,
668   CLIP_Z = 4,
669 } StrokeFlags;
670
671 /************** Access to original unmodified vertex data *************/
672
673 typedef struct {
674   BMLog *bm_log;
675
676   SculptUndoNode *unode;
677   float (*coords)[3];
678   short (*normals)[3];
679   const float *vmasks;
680
681   /* Original coordinate, normal, and mask */
682   const float *co;
683   const short *no;
684   float mask;
685 } SculptOrigVertData;
686
687 /* Initialize a SculptOrigVertData for accessing original vertex data;
688  * handles BMesh, mesh, and multires */
689 static void sculpt_orig_vert_data_unode_init(SculptOrigVertData *data,
690                                              Object *ob,
691                                              SculptUndoNode *unode)
692 {
693   SculptSession *ss = ob->sculpt;
694   BMesh *bm = ss->bm;
695
696   memset(data, 0, sizeof(*data));
697   data->unode = unode;
698
699   if (bm) {
700     data->bm_log = ss->bm_log;
701   }
702   else {
703     data->coords = data->unode->co;
704     data->normals = data->unode->no;
705     data->vmasks = data->unode->mask;
706   }
707 }
708
709 /* Initialize a SculptOrigVertData for accessing original vertex data;
710  * handles BMesh, mesh, and multires */
711 static void sculpt_orig_vert_data_init(SculptOrigVertData *data, Object *ob, PBVHNode *node)
712 {
713   SculptUndoNode *unode;
714   unode = sculpt_undo_push_node(ob, node, SCULPT_UNDO_COORDS);
715   sculpt_orig_vert_data_unode_init(data, ob, unode);
716 }
717
718 /* Update a SculptOrigVertData for a particular vertex from the PBVH
719  * iterator */
720 static void sculpt_orig_vert_data_update(SculptOrigVertData *orig_data, PBVHVertexIter *iter)
721 {
722   if (orig_data->unode->type == SCULPT_UNDO_COORDS) {
723     if (orig_data->bm_log) {
724       BM_log_original_vert_data(orig_data->bm_log, iter->bm_vert, &orig_data->co, &orig_data->no);
725     }
726     else {
727       orig_data->co = orig_data->coords[iter->i];
728       orig_data->no = orig_data->normals[iter->i];
729     }
730   }
731   else if (orig_data->unode->type == SCULPT_UNDO_MASK) {
732     if (orig_data->bm_log) {
733       orig_data->mask = BM_log_original_mask(orig_data->bm_log, iter->bm_vert);
734     }
735     else {
736       orig_data->mask = orig_data->vmasks[iter->i];
737     }
738   }
739 }
740
741 static void sculpt_rake_data_update(struct SculptRakeData *srd, const float co[3])
742 {
743   float rake_dist = len_v3v3(srd->follow_co, co);
744   if (rake_dist > srd->follow_dist) {
745     interp_v3_v3v3(srd->follow_co, srd->follow_co, co, rake_dist - srd->follow_dist);
746   }
747 }
748
749 static void sculpt_rake_rotate(const SculptSession *ss,
750                                const float sculpt_co[3],
751                                const float v_co[3],
752                                float factor,
753                                float r_delta[3])
754 {
755   float vec_rot[3];
756
757 #if 0
758   /* lerp */
759   sub_v3_v3v3(vec_rot, v_co, sculpt_co);
760   mul_qt_v3(ss->cache->rake_rotation_symmetry, vec_rot);
761   add_v3_v3(vec_rot, sculpt_co);
762   sub_v3_v3v3(r_delta, vec_rot, v_co);
763   mul_v3_fl(r_delta, factor);
764 #else
765   /* slerp */
766   float q_interp[4];
767   sub_v3_v3v3(vec_rot, v_co, sculpt_co);
768
769   copy_qt_qt(q_interp, ss->cache->rake_rotation_symmetry);
770   pow_qt_fl_normalized(q_interp, factor);
771   mul_qt_v3(q_interp, vec_rot);
772
773   add_v3_v3(vec_rot, sculpt_co);
774   sub_v3_v3v3(r_delta, vec_rot, v_co);
775 #endif
776 }
777
778 /**
779  * Align the grab delta to the brush normal.
780  *
781  * \param grab_delta: Typically from `ss->cache->grab_delta_symmetry`.
782  */
783 static void sculpt_project_v3_normal_align(SculptSession *ss,
784                                            const float normal_weight,
785                                            float grab_delta[3])
786 {
787   /* signed to support grabbing in (to make a hole) as well as out. */
788   const float len_signed = dot_v3v3(ss->cache->sculpt_normal_symm, grab_delta);
789
790   /* this scale effectively projects the offset so dragging follows the cursor,
791    * as the normal points towards the view, the scale increases. */
792   float len_view_scale;
793   {
794     float view_aligned_normal[3];
795     project_plane_v3_v3v3(
796         view_aligned_normal, ss->cache->sculpt_normal_symm, ss->cache->view_normal);
797     len_view_scale = fabsf(dot_v3v3(view_aligned_normal, ss->cache->sculpt_normal_symm));
798     len_view_scale = (len_view_scale > FLT_EPSILON) ? 1.0f / len_view_scale : 1.0f;
799   }
800
801   mul_v3_fl(grab_delta, 1.0f - normal_weight);
802   madd_v3_v3fl(
803       grab_delta, ss->cache->sculpt_normal_symm, (len_signed * normal_weight) * len_view_scale);
804 }
805
806 /** \name SculptProjectVector
807  *
808  * Fast-path for #project_plane_v3_v3v3
809  *
810  * \{ */
811
812 typedef struct SculptProjectVector {
813   float plane[3];
814   float len_sq;
815   float len_sq_inv_neg;
816   bool is_valid;
817
818 } SculptProjectVector;
819
820 /**
821  * \param plane: Direction, can be any length.
822  */
823 static void sculpt_project_v3_cache_init(SculptProjectVector *spvc, const float plane[3])
824 {
825   copy_v3_v3(spvc->plane, plane);
826   spvc->len_sq = len_squared_v3(spvc->plane);
827   spvc->is_valid = (spvc->len_sq > FLT_EPSILON);
828   spvc->len_sq_inv_neg = (spvc->is_valid) ? -1.0f / spvc->len_sq : 0.0f;
829 }
830
831 /**
832  * Calculate the projection.
833  */
834 static void sculpt_project_v3(const SculptProjectVector *spvc, const float vec[3], float r_vec[3])
835 {
836 #if 0
837   project_plane_v3_v3v3(r_vec, vec, spvc->plane);
838 #else
839   /* inline the projection, cache `-1.0 / dot_v3_v3(v_proj, v_proj)` */
840   madd_v3_v3fl(r_vec, spvc->plane, dot_v3v3(vec, spvc->plane) * spvc->len_sq_inv_neg);
841 #endif
842 }
843
844 /** \} */
845
846 /**********************************************************************/
847
848 /* Returns true if the stroke will use dynamic topology, false
849  * otherwise.
850  *
851  * Factors: some brushes like grab cannot do dynamic topology.
852  * Others, like smooth, are better without. Same goes for alt-
853  * key smoothing. */
854 static bool sculpt_stroke_is_dynamic_topology(const SculptSession *ss, const Brush *brush)
855 {
856   return ((BKE_pbvh_type(ss->pbvh) == PBVH_BMESH) &&
857
858           (!ss->cache || (!ss->cache->alt_smooth)) &&
859
860           /* Requires mesh restore, which doesn't work with
861            * dynamic-topology */
862           !(brush->flag & BRUSH_ANCHORED) && !(brush->flag & BRUSH_DRAG_DOT) &&
863
864           SCULPT_TOOL_HAS_DYNTOPO(brush->sculpt_tool));
865 }
866
867 /*** paint mesh ***/
868
869 static void paint_mesh_restore_co_task_cb(void *__restrict userdata,
870                                           const int n,
871                                           const TaskParallelTLS *__restrict UNUSED(tls))
872 {
873   SculptThreadedTaskData *data = userdata;
874   SculptSession *ss = data->ob->sculpt;
875
876   SculptUndoNode *unode;
877   SculptUndoType type = (data->brush->sculpt_tool == SCULPT_TOOL_MASK ? SCULPT_UNDO_MASK :
878                                                                         SCULPT_UNDO_COORDS);
879
880   if (ss->bm) {
881     unode = sculpt_undo_push_node(data->ob, data->nodes[n], type);
882   }
883   else {
884     unode = sculpt_undo_get_node(data->nodes[n]);
885   }
886
887   if (unode) {
888     PBVHVertexIter vd;
889     SculptOrigVertData orig_data;
890
891     sculpt_orig_vert_data_unode_init(&orig_data, data->ob, unode);
892
893     BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
894     {
895       sculpt_orig_vert_data_update(&orig_data, &vd);
896
897       if (orig_data.unode->type == SCULPT_UNDO_COORDS) {
898         copy_v3_v3(vd.co, orig_data.co);
899         if (vd.no) {
900           copy_v3_v3_short(vd.no, orig_data.no);
901         }
902         else {
903           normal_short_to_float_v3(vd.fno, orig_data.no);
904         }
905       }
906       else if (orig_data.unode->type == SCULPT_UNDO_MASK) {
907         *vd.mask = orig_data.mask;
908       }
909
910       if (vd.mvert) {
911         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
912       }
913     }
914     BKE_pbvh_vertex_iter_end;
915
916     BKE_pbvh_node_mark_update(data->nodes[n]);
917   }
918 }
919
920 static void paint_mesh_restore_co(Sculpt *sd, Object *ob)
921 {
922   SculptSession *ss = ob->sculpt;
923   Brush *brush = BKE_paint_brush(&sd->paint);
924
925   PBVHNode **nodes;
926   int totnode;
927
928   BKE_pbvh_search_gather(ss->pbvh, NULL, NULL, &nodes, &totnode);
929
930   /**
931    * Disable OpenMP when dynamic-topology is enabled. Otherwise, new entries might be inserted by
932    * #sculpt_undo_push_node() into the GHash used internally by #BM_log_original_vert_co()
933    * by a different thread. See T33787. */
934   SculptThreadedTaskData data = {
935       .sd = sd,
936       .ob = ob,
937       .brush = brush,
938       .nodes = nodes,
939   };
940
941   PBVHParallelSettings settings;
942   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP) && !ss->bm, totnode);
943   BKE_pbvh_parallel_range(0, totnode, &data, paint_mesh_restore_co_task_cb, &settings);
944
945   MEM_SAFE_FREE(nodes);
946 }
947
948 /*** BVH Tree ***/
949
950 static void sculpt_extend_redraw_rect_previous(Object *ob, rcti *rect)
951 {
952   /* expand redraw rect with redraw rect from previous step to
953    * prevent partial-redraw issues caused by fast strokes. This is
954    * needed here (not in sculpt_flush_update) as it was before
955    * because redraw rectangle should be the same in both of
956    * optimized PBVH draw function and 3d view redraw (if not -- some
957    * mesh parts could disappear from screen (sergey) */
958   SculptSession *ss = ob->sculpt;
959
960   if (ss->cache) {
961     if (!BLI_rcti_is_empty(&ss->cache->previous_r)) {
962       BLI_rcti_union(rect, &ss->cache->previous_r);
963     }
964   }
965 }
966
967 /* Get a screen-space rectangle of the modified area */
968 bool sculpt_get_redraw_rect(ARegion *ar, RegionView3D *rv3d, Object *ob, rcti *rect)
969 {
970   PBVH *pbvh = ob->sculpt->pbvh;
971   float bb_min[3], bb_max[3];
972
973   if (!pbvh) {
974     return 0;
975   }
976
977   BKE_pbvh_redraw_BB(pbvh, bb_min, bb_max);
978
979   /* convert 3D bounding box to screen space */
980   if (!paint_convert_bb_to_rect(rect, bb_min, bb_max, ar, rv3d, ob)) {
981     return 0;
982   }
983
984   return 1;
985 }
986
987 void ED_sculpt_redraw_planes_get(float planes[4][4], ARegion *ar, Object *ob)
988 {
989   PBVH *pbvh = ob->sculpt->pbvh;
990   /* copy here, original will be used below */
991   rcti rect = ob->sculpt->cache->current_r;
992
993   sculpt_extend_redraw_rect_previous(ob, &rect);
994
995   paint_calc_redraw_planes(planes, ar, ob, &rect);
996
997   /* we will draw this rect, so now we can set it as the previous partial rect.
998    * Note that we don't update with the union of previous/current (rect), only with
999    * the current. Thus we avoid the rectangle needlessly growing to include
1000    * all the stroke area */
1001   ob->sculpt->cache->previous_r = ob->sculpt->cache->current_r;
1002
1003   /* clear redraw flag from nodes */
1004   if (pbvh) {
1005     BKE_pbvh_update_bounds(pbvh, PBVH_UpdateRedraw);
1006   }
1007 }
1008
1009 /************************ Brush Testing *******************/
1010
1011 void sculpt_brush_test_init(SculptSession *ss, SculptBrushTest *test)
1012 {
1013   RegionView3D *rv3d = ss->cache ? ss->cache->vc->rv3d : ss->rv3d;
1014
1015   test->radius_squared = ss->cache ? ss->cache->radius_squared :
1016                                      ss->cursor_radius * ss->cursor_radius;
1017   if (ss->cache) {
1018     copy_v3_v3(test->location, ss->cache->location);
1019     test->mirror_symmetry_pass = ss->cache->mirror_symmetry_pass;
1020   }
1021   else {
1022     copy_v3_v3(test->location, ss->cursor_location);
1023     test->mirror_symmetry_pass = 0;
1024   }
1025
1026   test->dist = 0.0f; /* just for initialize */
1027
1028   /* Only for 2D projection. */
1029   zero_v4(test->plane_view);
1030   zero_v4(test->plane_tool);
1031
1032   test->mirror_symmetry_pass = ss->cache ? ss->cache->mirror_symmetry_pass : 0;
1033
1034   if (rv3d->rflag & RV3D_CLIPPING) {
1035     test->clip_rv3d = rv3d;
1036   }
1037   else {
1038     test->clip_rv3d = NULL;
1039   }
1040 }
1041
1042 BLI_INLINE bool sculpt_brush_test_clipping(const SculptBrushTest *test, const float co[3])
1043 {
1044   RegionView3D *rv3d = test->clip_rv3d;
1045   if (!rv3d) {
1046     return false;
1047   }
1048   float symm_co[3];
1049   flip_v3_v3(symm_co, co, test->mirror_symmetry_pass);
1050   return ED_view3d_clipping_test(rv3d, symm_co, true);
1051 }
1052
1053 bool sculpt_brush_test_sphere(SculptBrushTest *test, const float co[3])
1054 {
1055   float distsq = len_squared_v3v3(co, test->location);
1056
1057   if (distsq <= test->radius_squared) {
1058     if (sculpt_brush_test_clipping(test, co)) {
1059       return 0;
1060     }
1061     test->dist = sqrtf(distsq);
1062     return 1;
1063   }
1064   else {
1065     return 0;
1066   }
1067 }
1068
1069 bool sculpt_brush_test_sphere_sq(SculptBrushTest *test, const float co[3])
1070 {
1071   float distsq = len_squared_v3v3(co, test->location);
1072
1073   if (distsq <= test->radius_squared) {
1074     if (sculpt_brush_test_clipping(test, co)) {
1075       return 0;
1076     }
1077     test->dist = distsq;
1078     return 1;
1079   }
1080   else {
1081     return 0;
1082   }
1083 }
1084
1085 bool sculpt_brush_test_sphere_fast(const SculptBrushTest *test, const float co[3])
1086 {
1087   if (sculpt_brush_test_clipping(test, co)) {
1088     return 0;
1089   }
1090   return len_squared_v3v3(co, test->location) <= test->radius_squared;
1091 }
1092
1093 bool sculpt_brush_test_circle_sq(SculptBrushTest *test, const float co[3])
1094 {
1095   float co_proj[3];
1096   closest_to_plane_normalized_v3(co_proj, test->plane_view, co);
1097   float distsq = len_squared_v3v3(co_proj, test->location);
1098
1099   if (distsq <= test->radius_squared) {
1100     if (sculpt_brush_test_clipping(test, co)) {
1101       return 0;
1102     }
1103     test->dist = distsq;
1104     return 1;
1105   }
1106   else {
1107     return 0;
1108   }
1109 }
1110
1111 bool sculpt_brush_test_cube(SculptBrushTest *test, const float co[3], float local[4][4])
1112 {
1113   float side = M_SQRT1_2;
1114   float local_co[3];
1115
1116   if (sculpt_brush_test_clipping(test, co)) {
1117     return 0;
1118   }
1119
1120   mul_v3_m4v3(local_co, local, co);
1121
1122   local_co[0] = fabsf(local_co[0]);
1123   local_co[1] = fabsf(local_co[1]);
1124   local_co[2] = fabsf(local_co[2]);
1125
1126   const float p = 8.0f;
1127   if (local_co[0] <= side && local_co[1] <= side && local_co[2] <= side) {
1128     test->dist = ((powf(local_co[0], p) + powf(local_co[1], p) + powf(local_co[2], p)) /
1129                   powf(side, p));
1130
1131     return 1;
1132   }
1133   else {
1134     return 0;
1135   }
1136 }
1137
1138 SculptBrushTestFn sculpt_brush_test_init_with_falloff_shape(SculptSession *ss,
1139                                                             SculptBrushTest *test,
1140                                                             char falloff_shape)
1141 {
1142   sculpt_brush_test_init(ss, test);
1143   SculptBrushTestFn sculpt_brush_test_sq_fn;
1144   if (falloff_shape == PAINT_FALLOFF_SHAPE_SPHERE) {
1145     sculpt_brush_test_sq_fn = sculpt_brush_test_sphere_sq;
1146   }
1147   else {
1148     /* PAINT_FALLOFF_SHAPE_TUBE */
1149     plane_from_point_normal_v3(test->plane_view, test->location, ss->cache->view_normal);
1150     sculpt_brush_test_sq_fn = sculpt_brush_test_circle_sq;
1151   }
1152   return sculpt_brush_test_sq_fn;
1153 }
1154
1155 const float *sculpt_brush_frontface_normal_from_falloff_shape(SculptSession *ss,
1156                                                               char falloff_shape)
1157 {
1158   if (falloff_shape == PAINT_FALLOFF_SHAPE_SPHERE) {
1159     return ss->cache->sculpt_normal_symm;
1160   }
1161   else {
1162     /* PAINT_FALLOFF_SHAPE_TUBE */
1163     return ss->cache->view_normal;
1164   }
1165 }
1166
1167 static float frontface(const Brush *br,
1168                        const float sculpt_normal[3],
1169                        const short no[3],
1170                        const float fno[3])
1171 {
1172   if (br->flag & BRUSH_FRONTFACE) {
1173     float dot;
1174
1175     if (no) {
1176       float tmp[3];
1177
1178       normal_short_to_float_v3(tmp, no);
1179       dot = dot_v3v3(tmp, sculpt_normal);
1180     }
1181     else {
1182       dot = dot_v3v3(fno, sculpt_normal);
1183     }
1184     return dot > 0 ? dot : 0;
1185   }
1186   else {
1187     return 1;
1188   }
1189 }
1190
1191 #if 0
1192
1193 static bool sculpt_brush_test_cyl(SculptBrushTest *test,
1194                                   float co[3],
1195                                   float location[3],
1196                                   const float area_no[3])
1197 {
1198   if (sculpt_brush_test_sphere_fast(test, co)) {
1199     float t1[3], t2[3], t3[3], dist;
1200
1201     sub_v3_v3v3(t1, location, co);
1202     sub_v3_v3v3(t2, x2, location);
1203
1204     cross_v3_v3v3(t3, area_no, t1);
1205
1206     dist = len_v3(t3) / len_v3(t2);
1207
1208     test->dist = dist;
1209
1210     return 1;
1211   }
1212
1213   return 0;
1214 }
1215
1216 #endif
1217
1218 /* Automasking */
1219
1220 static bool sculpt_automasking_enabled(SculptSession *ss, const Brush *br)
1221 {
1222   if (sculpt_stroke_is_dynamic_topology(ss, br)) {
1223     return false;
1224   }
1225   if (br->automasking_flags & BRUSH_AUTOMASKING_TOPOLOGY) {
1226     return true;
1227   }
1228   return false;
1229 }
1230
1231 static float sculpt_automasking_factor_get(SculptSession *ss, int vert)
1232 {
1233   if (ss->cache->automask) {
1234     return ss->cache->automask[vert];
1235   }
1236   else {
1237     return 1.0f;
1238   }
1239 }
1240
1241 static void sculpt_automasking_end(Object *ob)
1242 {
1243   SculptSession *ss = ob->sculpt;
1244   if (ss->cache && ss->cache->automask) {
1245     MEM_freeN(ss->cache->automask);
1246   }
1247 }
1248
1249 static bool sculpt_automasking_is_constrained_by_radius(Brush *br)
1250 {
1251   /* 2D falloff is not constrained by radius */
1252   if (br->falloff_shape == PAINT_FALLOFF_SHAPE_TUBE) {
1253     return false;
1254   }
1255
1256   if (ELEM(br->sculpt_tool, SCULPT_TOOL_GRAB, SCULPT_TOOL_THUMB)) {
1257     return true;
1258   }
1259   return false;
1260 }
1261
1262 typedef struct AutomaskFloodFillData {
1263   float *automask_factor;
1264   float radius;
1265   bool use_radius;
1266   float location[3];
1267   char symm;
1268 } AutomaskFloodFillData;
1269
1270 static bool automask_floodfill_cb(
1271     SculptSession *ss, int UNUSED(from_v), int to_v, bool UNUSED(is_duplicate), void *userdata)
1272 {
1273   AutomaskFloodFillData *data = userdata;
1274
1275   data->automask_factor[to_v] = 1.0f;
1276   return (!data->use_radius ||
1277           sculpt_is_vertex_inside_brush_radius_symm(
1278               sculpt_vertex_co_get(ss, to_v), data->location, data->radius, data->symm));
1279 }
1280
1281 static float *sculpt_topology_automasking_init(Sculpt *sd, Object *ob, float *automask_factor)
1282 {
1283   SculptSession *ss = ob->sculpt;
1284   Brush *brush = BKE_paint_brush(&sd->paint);
1285
1286   if (!sculpt_automasking_enabled(ss, brush)) {
1287     return NULL;
1288   }
1289
1290   if (BKE_pbvh_type(ss->pbvh) == PBVH_FACES && !ss->pmap) {
1291     BLI_assert(!"Topology masking: pmap missing");
1292     return NULL;
1293   }
1294
1295   /* Flood fill automask to connected vertices. Limited to vertices inside
1296    * the brush radius if the tool requires it */
1297   SculptFloodFill flood;
1298   sculpt_floodfill_init(ss, &flood);
1299   sculpt_floodfill_add_active(sd, ob, ss, &flood, ss->cache->radius);
1300
1301   AutomaskFloodFillData fdata = {
1302       .automask_factor = automask_factor,
1303       .radius = ss->cache->radius,
1304       .use_radius = sculpt_automasking_is_constrained_by_radius(brush),
1305       .symm = sd->paint.symmetry_flags & PAINT_SYMM_AXIS_ALL,
1306   };
1307   copy_v3_v3(fdata.location, sculpt_active_vertex_co_get(ss));
1308   sculpt_floodfill_execute(ss, &flood, automask_floodfill_cb, &fdata);
1309   sculpt_floodfill_free(&flood);
1310
1311   return automask_factor;
1312 }
1313
1314 static void sculpt_automasking_init(Sculpt *sd, Object *ob)
1315 {
1316   SculptSession *ss = ob->sculpt;
1317   Brush *brush = BKE_paint_brush(&sd->paint);
1318
1319   ss->cache->automask = MEM_callocN(sizeof(float) * sculpt_vertex_count_get(ss),
1320                                     "automask_factor");
1321
1322   if (brush->automasking_flags & BRUSH_AUTOMASKING_TOPOLOGY) {
1323     sculpt_vertex_random_access_init(ss);
1324     sculpt_topology_automasking_init(sd, ob, ss->cache->automask);
1325   }
1326 }
1327
1328 /* ===== Sculpting =====
1329  */
1330 static void flip_v3(float v[3], const char symm)
1331 {
1332   flip_v3_v3(v, v, symm);
1333 }
1334
1335 static float calc_overlap(StrokeCache *cache, const char symm, const char axis, const float angle)
1336 {
1337   float mirror[3];
1338   float distsq;
1339
1340   /* flip_v3_v3(mirror, cache->traced_location, symm); */
1341   flip_v3_v3(mirror, cache->true_location, symm);
1342
1343   if (axis != 0) {
1344     float mat[3][3];
1345     axis_angle_to_mat3_single(mat, axis, angle);
1346     mul_m3_v3(mat, mirror);
1347   }
1348
1349   /* distsq = len_squared_v3v3(mirror, cache->traced_location); */
1350   distsq = len_squared_v3v3(mirror, cache->true_location);
1351
1352   if (distsq <= 4.0f * (cache->radius_squared)) {
1353     return (2.0f * (cache->radius) - sqrtf(distsq)) / (2.0f * (cache->radius));
1354   }
1355   else {
1356     return 0;
1357   }
1358 }
1359
1360 static float calc_radial_symmetry_feather(Sculpt *sd,
1361                                           StrokeCache *cache,
1362                                           const char symm,
1363                                           const char axis)
1364 {
1365   int i;
1366   float overlap;
1367
1368   overlap = 0;
1369   for (i = 1; i < sd->radial_symm[axis - 'X']; i++) {
1370     const float angle = 2 * M_PI * i / sd->radial_symm[axis - 'X'];
1371     overlap += calc_overlap(cache, symm, axis, angle);
1372   }
1373
1374   return overlap;
1375 }
1376
1377 static float calc_symmetry_feather(Sculpt *sd, StrokeCache *cache)
1378 {
1379   if (sd->paint.symmetry_flags & PAINT_SYMMETRY_FEATHER) {
1380     float overlap;
1381     int symm = cache->symmetry;
1382     int i;
1383
1384     overlap = 0;
1385     for (i = 0; i <= symm; i++) {
1386       if (i == 0 || (symm & i && (symm != 5 || i != 3) && (symm != 6 || (i != 3 && i != 5)))) {
1387
1388         overlap += calc_overlap(cache, i, 0, 0);
1389
1390         overlap += calc_radial_symmetry_feather(sd, cache, i, 'X');
1391         overlap += calc_radial_symmetry_feather(sd, cache, i, 'Y');
1392         overlap += calc_radial_symmetry_feather(sd, cache, i, 'Z');
1393       }
1394     }
1395
1396     return 1 / overlap;
1397   }
1398   else {
1399     return 1;
1400   }
1401 }
1402
1403 /** \name Calculate Normal and Center
1404  *
1405  * Calculate geometry surrounding the brush center.
1406  * (optionally using original coordinates).
1407  *
1408  * Functions are:
1409  * - #calc_area_center
1410  * - #calc_area_normal
1411  * - #calc_area_normal_and_center
1412  *
1413  * \note These are all _very_ similar, when changing one, check others.
1414  * \{ */
1415
1416 typedef struct AreaNormalCenterTLSData {
1417   /* 0=towards view, 1=flipped */
1418   float area_cos[2][3];
1419   float area_nos[2][3];
1420   int area_count[2];
1421 } AreaNormalCenterTLSData;
1422
1423 static void calc_area_normal_and_center_task_cb(void *__restrict userdata,
1424                                                 const int n,
1425                                                 const TaskParallelTLS *__restrict tls)
1426 {
1427   SculptThreadedTaskData *data = userdata;
1428   SculptSession *ss = data->ob->sculpt;
1429   AreaNormalCenterTLSData *anctd = tls->userdata_chunk;
1430   const bool use_area_nos = data->use_area_nos;
1431   const bool use_area_cos = data->use_area_cos;
1432
1433   PBVHVertexIter vd;
1434   SculptUndoNode *unode = NULL;
1435
1436   bool use_original = false;
1437
1438   if (ss->cache && ss->cache->original) {
1439     unode = sculpt_undo_push_node(data->ob, data->nodes[n], SCULPT_UNDO_COORDS);
1440     use_original = (unode->co || unode->bm_entry);
1441   }
1442
1443   SculptBrushTest test;
1444   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
1445       ss, &test, data->brush->falloff_shape);
1446
1447   /* Update the test radius to sample the normal using the normal radius of the brush */
1448   if (data->brush->ob_mode == OB_MODE_SCULPT) {
1449     float test_radius = sqrtf(test.radius_squared);
1450     /* Layer brush produces artifacts with normal radius */
1451     if (!(ss->cache && data->brush->sculpt_tool == SCULPT_TOOL_LAYER)) {
1452       test_radius *= data->brush->normal_radius_factor;
1453     }
1454     test.radius_squared = test_radius * test_radius;
1455   }
1456
1457   /* when the mesh is edited we can't rely on original coords
1458    * (original mesh may not even have verts in brush radius) */
1459   if (use_original && data->has_bm_orco) {
1460     float(*orco_coords)[3];
1461     int(*orco_tris)[3];
1462     int orco_tris_num;
1463     int i;
1464
1465     BKE_pbvh_node_get_bm_orco_data(data->nodes[n], &orco_tris, &orco_tris_num, &orco_coords);
1466
1467     for (i = 0; i < orco_tris_num; i++) {
1468       const float *co_tri[3] = {
1469           orco_coords[orco_tris[i][0]],
1470           orco_coords[orco_tris[i][1]],
1471           orco_coords[orco_tris[i][2]],
1472       };
1473       float co[3];
1474
1475       closest_on_tri_to_point_v3(co, test.location, UNPACK3(co_tri));
1476
1477       if (sculpt_brush_test_sq_fn(&test, co)) {
1478         float no[3];
1479         int flip_index;
1480
1481         normal_tri_v3(no, UNPACK3(co_tri));
1482
1483         flip_index = (dot_v3v3(ss->cache->view_normal, no) <= 0.0f);
1484         if (use_area_cos) {
1485           add_v3_v3(anctd->area_cos[flip_index], co);
1486         }
1487         if (use_area_nos) {
1488           add_v3_v3(anctd->area_nos[flip_index], no);
1489         }
1490         anctd->area_count[flip_index] += 1;
1491       }
1492     }
1493   }
1494   else {
1495     BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
1496     {
1497       const float *co;
1498       const short *no_s; /* bm_vert only */
1499
1500       if (use_original) {
1501         if (unode->bm_entry) {
1502           BM_log_original_vert_data(ss->bm_log, vd.bm_vert, &co, &no_s);
1503         }
1504         else {
1505           co = unode->co[vd.i];
1506           no_s = unode->no[vd.i];
1507         }
1508       }
1509       else {
1510         co = vd.co;
1511       }
1512
1513       if (sculpt_brush_test_sq_fn(&test, co)) {
1514         float no_buf[3];
1515         const float *no;
1516         int flip_index;
1517
1518         data->any_vertex_sampled = true;
1519
1520         if (use_original) {
1521           normal_short_to_float_v3(no_buf, no_s);
1522           no = no_buf;
1523         }
1524         else {
1525           if (vd.no) {
1526             normal_short_to_float_v3(no_buf, vd.no);
1527             no = no_buf;
1528           }
1529           else {
1530             no = vd.fno;
1531           }
1532         }
1533
1534         flip_index = (dot_v3v3(ss->cache ? ss->cache->view_normal : ss->cursor_view_normal, no) <=
1535                       0.0f);
1536         if (use_area_cos) {
1537           add_v3_v3(anctd->area_cos[flip_index], co);
1538         }
1539         if (use_area_nos) {
1540           add_v3_v3(anctd->area_nos[flip_index], no);
1541         }
1542         anctd->area_count[flip_index] += 1;
1543       }
1544     }
1545     BKE_pbvh_vertex_iter_end;
1546   }
1547 }
1548
1549 static void calc_area_normal_and_center_reduce(const void *__restrict UNUSED(userdata),
1550                                                void *__restrict chunk_join,
1551                                                void *__restrict chunk)
1552 {
1553   AreaNormalCenterTLSData *join = chunk_join;
1554   AreaNormalCenterTLSData *anctd = chunk;
1555
1556   /* for flatten center */
1557   add_v3_v3(join->area_cos[0], anctd->area_cos[0]);
1558   add_v3_v3(join->area_cos[1], anctd->area_cos[1]);
1559
1560   /* for area normal */
1561   add_v3_v3(join->area_nos[0], anctd->area_nos[0]);
1562   add_v3_v3(join->area_nos[1], anctd->area_nos[1]);
1563
1564   /* weights */
1565   join->area_count[0] += anctd->area_count[0];
1566   join->area_count[1] += anctd->area_count[1];
1567 }
1568
1569 static void calc_area_center(
1570     Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode, float r_area_co[3])
1571 {
1572   const Brush *brush = BKE_paint_brush(&sd->paint);
1573   SculptSession *ss = ob->sculpt;
1574   const bool has_bm_orco = ss->bm && sculpt_stroke_is_dynamic_topology(ss, brush);
1575   int n;
1576
1577   /* Intentionally set 'sd' to NULL since we share logic with vertex paint. */
1578   SculptThreadedTaskData data = {
1579       .sd = NULL,
1580       .ob = ob,
1581       .brush = brush,
1582       .nodes = nodes,
1583       .totnode = totnode,
1584       .has_bm_orco = has_bm_orco,
1585       .use_area_cos = true,
1586   };
1587
1588   AreaNormalCenterTLSData anctd = {{{0}}};
1589
1590   PBVHParallelSettings settings;
1591   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
1592   settings.func_reduce = calc_area_normal_and_center_reduce;
1593   settings.userdata_chunk = &anctd;
1594   settings.userdata_chunk_size = sizeof(AreaNormalCenterTLSData);
1595   BKE_pbvh_parallel_range(0, totnode, &data, calc_area_normal_and_center_task_cb, &settings);
1596
1597   /* for flatten center */
1598   for (n = 0; n < ARRAY_SIZE(anctd.area_cos); n++) {
1599     if (anctd.area_count[n] != 0) {
1600       mul_v3_v3fl(r_area_co, anctd.area_cos[n], 1.0f / anctd.area_count[n]);
1601       break;
1602     }
1603   }
1604   if (n == 2) {
1605     zero_v3(r_area_co);
1606   }
1607 }
1608
1609 static void calc_area_normal(
1610     Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode, float r_area_no[3])
1611 {
1612   const Brush *brush = BKE_paint_brush(&sd->paint);
1613   bool use_threading = (sd->flags & SCULPT_USE_OPENMP);
1614   sculpt_pbvh_calc_area_normal(brush, ob, nodes, totnode, use_threading, r_area_no);
1615 }
1616
1617 /* expose 'calc_area_normal' externally. */
1618 bool sculpt_pbvh_calc_area_normal(const Brush *brush,
1619                                   Object *ob,
1620                                   PBVHNode **nodes,
1621                                   int totnode,
1622                                   bool use_threading,
1623                                   float r_area_no[3])
1624 {
1625   SculptSession *ss = ob->sculpt;
1626   const bool has_bm_orco = ss->bm && sculpt_stroke_is_dynamic_topology(ss, brush);
1627
1628   /* Intentionally set 'sd' to NULL since this is used for vertex paint too. */
1629   SculptThreadedTaskData data = {
1630       .sd = NULL,
1631       .ob = ob,
1632       .brush = brush,
1633       .nodes = nodes,
1634       .totnode = totnode,
1635       .has_bm_orco = has_bm_orco,
1636       .use_area_nos = true,
1637       .any_vertex_sampled = false,
1638   };
1639
1640   AreaNormalCenterTLSData anctd = {{{0}}};
1641
1642   PBVHParallelSettings settings;
1643   BKE_pbvh_parallel_range_settings(&settings, use_threading, totnode);
1644   settings.func_reduce = calc_area_normal_and_center_reduce;
1645   settings.userdata_chunk = &anctd;
1646   settings.userdata_chunk_size = sizeof(AreaNormalCenterTLSData);
1647   BKE_pbvh_parallel_range(0, totnode, &data, calc_area_normal_and_center_task_cb, &settings);
1648
1649   /* for area normal */
1650   for (int i = 0; i < ARRAY_SIZE(anctd.area_nos); i++) {
1651     if (normalize_v3_v3(r_area_no, anctd.area_nos[i]) != 0.0f) {
1652       break;
1653     }
1654   }
1655
1656   return data.any_vertex_sampled;
1657 }
1658
1659 /* this calculates flatten center and area normal together,
1660  * amortizing the memory bandwidth and loop overhead to calculate both at the same time */
1661 static void calc_area_normal_and_center(
1662     Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode, float r_area_no[3], float r_area_co[3])
1663 {
1664   const Brush *brush = BKE_paint_brush(&sd->paint);
1665   SculptSession *ss = ob->sculpt;
1666   const bool has_bm_orco = ss->bm && sculpt_stroke_is_dynamic_topology(ss, brush);
1667   int n;
1668
1669   /* Intentionally set 'sd' to NULL since this is used for vertex paint too. */
1670   SculptThreadedTaskData data = {
1671       .sd = NULL,
1672       .ob = ob,
1673       .brush = brush,
1674       .nodes = nodes,
1675       .totnode = totnode,
1676       .has_bm_orco = has_bm_orco,
1677       .use_area_cos = true,
1678       .use_area_nos = true,
1679   };
1680
1681   AreaNormalCenterTLSData anctd = {{{0}}};
1682
1683   PBVHParallelSettings settings;
1684   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
1685   settings.func_reduce = calc_area_normal_and_center_reduce;
1686   settings.userdata_chunk = &anctd;
1687   settings.userdata_chunk_size = sizeof(AreaNormalCenterTLSData);
1688   BKE_pbvh_parallel_range(0, totnode, &data, calc_area_normal_and_center_task_cb, &settings);
1689
1690   /* for flatten center */
1691   for (n = 0; n < ARRAY_SIZE(anctd.area_cos); n++) {
1692     if (anctd.area_count[n] != 0) {
1693       mul_v3_v3fl(r_area_co, anctd.area_cos[n], 1.0f / anctd.area_count[n]);
1694       break;
1695     }
1696   }
1697   if (n == 2) {
1698     zero_v3(r_area_co);
1699   }
1700
1701   /* for area normal */
1702   for (n = 0; n < ARRAY_SIZE(anctd.area_nos); n++) {
1703     if (normalize_v3_v3(r_area_no, anctd.area_nos[n]) != 0.0f) {
1704       break;
1705     }
1706   }
1707 }
1708
1709 /** \} */
1710
1711 /* Return modified brush strength. Includes the direction of the brush, positive
1712  * values pull vertices, negative values push. Uses tablet pressure and a
1713  * special multiplier found experimentally to scale the strength factor. */
1714 static float brush_strength(const Sculpt *sd,
1715                             const StrokeCache *cache,
1716                             const float feather,
1717                             const UnifiedPaintSettings *ups)
1718 {
1719   const Scene *scene = cache->vc->scene;
1720   const Brush *brush = BKE_paint_brush((Paint *)&sd->paint);
1721
1722   /* Primary strength input; square it to make lower values more sensitive */
1723   const float root_alpha = BKE_brush_alpha_get(scene, brush);
1724   float alpha = root_alpha * root_alpha;
1725   float dir = (brush->flag & BRUSH_DIR_IN) ? -1 : 1;
1726   float pressure = BKE_brush_use_alpha_pressure(scene, brush) ? cache->pressure : 1;
1727   float pen_flip = cache->pen_flip ? -1 : 1;
1728   float invert = cache->invert ? -1 : 1;
1729   float overlap = ups->overlap_factor;
1730   /* spacing is integer percentage of radius, divide by 50 to get
1731    * normalized diameter */
1732
1733   float flip = dir * invert * pen_flip;
1734
1735   /* Pressure final value after being tweaked depending on the brush */
1736   float final_pressure;
1737
1738   switch (brush->sculpt_tool) {
1739     case SCULPT_TOOL_CLAY:
1740       overlap = (1.0f + overlap) / 2.0f;
1741       return 0.25f * alpha * flip * pressure * overlap * feather;
1742     case SCULPT_TOOL_DRAW:
1743     case SCULPT_TOOL_DRAW_SHARP:
1744     case SCULPT_TOOL_LAYER:
1745       return alpha * flip * pressure * overlap * feather;
1746     case SCULPT_TOOL_CLAY_STRIPS:
1747       /* Clay Strips needs less strength to compensate the curve */
1748       final_pressure = pressure * pressure * pressure;
1749       return alpha * flip * final_pressure * overlap * feather * 0.3f;
1750
1751     case SCULPT_TOOL_MASK:
1752       overlap = (1 + overlap) / 2;
1753       switch ((BrushMaskTool)brush->mask_tool) {
1754         case BRUSH_MASK_DRAW:
1755           return alpha * flip * pressure * overlap * feather;
1756         case BRUSH_MASK_SMOOTH:
1757           return alpha * pressure * feather;
1758       }
1759       BLI_assert(!"Not supposed to happen");
1760       return 0.0f;
1761
1762     case SCULPT_TOOL_CREASE:
1763     case SCULPT_TOOL_BLOB:
1764       return alpha * flip * pressure * overlap * feather;
1765
1766     case SCULPT_TOOL_INFLATE:
1767       if (flip > 0) {
1768         return 0.250f * alpha * flip * pressure * overlap * feather;
1769       }
1770       else {
1771         return 0.125f * alpha * flip * pressure * overlap * feather;
1772       }
1773
1774     case SCULPT_TOOL_MULTIPLANE_SCRAPE:
1775       overlap = (1.0f + overlap) / 2.0f;
1776       return alpha * flip * pressure * overlap * feather;
1777
1778     case SCULPT_TOOL_FILL:
1779     case SCULPT_TOOL_SCRAPE:
1780     case SCULPT_TOOL_FLATTEN:
1781       if (flip > 0) {
1782         overlap = (1 + overlap) / 2;
1783         return alpha * flip * pressure * overlap * feather;
1784       }
1785       else {
1786         /* reduce strength for DEEPEN, PEAKS, and CONTRAST */
1787         return 0.5f * alpha * flip * pressure * overlap * feather;
1788       }
1789
1790     case SCULPT_TOOL_SMOOTH:
1791       return alpha * pressure * feather;
1792
1793     case SCULPT_TOOL_PINCH:
1794       if (flip > 0) {
1795         return alpha * flip * pressure * overlap * feather;
1796       }
1797       else {
1798         return 0.25f * alpha * flip * pressure * overlap * feather;
1799       }
1800
1801     case SCULPT_TOOL_NUDGE:
1802       overlap = (1 + overlap) / 2;
1803       return alpha * pressure * overlap * feather;
1804
1805     case SCULPT_TOOL_THUMB:
1806       return alpha * pressure * feather;
1807
1808     case SCULPT_TOOL_SNAKE_HOOK:
1809       return root_alpha * feather;
1810
1811     case SCULPT_TOOL_GRAB:
1812       return root_alpha * feather;
1813
1814     case SCULPT_TOOL_ROTATE:
1815       return alpha * pressure * feather;
1816
1817     case SCULPT_TOOL_ELASTIC_DEFORM:
1818     case SCULPT_TOOL_POSE:
1819       return root_alpha * feather;
1820
1821     default:
1822       return 0;
1823   }
1824 }
1825
1826 /* Return a multiplier for brush strength on a particular vertex. */
1827 float tex_strength(SculptSession *ss,
1828                    const Brush *br,
1829                    const float brush_point[3],
1830                    const float len,
1831                    const short vno[3],
1832                    const float fno[3],
1833                    const float mask,
1834                    const int vertex_index,
1835                    const int thread_id)
1836 {
1837   StrokeCache *cache = ss->cache;
1838   const Scene *scene = cache->vc->scene;
1839   const MTex *mtex = &br->mtex;
1840   float avg = 1;
1841   float rgba[4];
1842   float point[3];
1843
1844   sub_v3_v3v3(point, brush_point, cache->plane_offset);
1845
1846   if (!mtex->tex) {
1847     avg = 1;
1848   }
1849   else if (mtex->brush_map_mode == MTEX_MAP_MODE_3D) {
1850     /* Get strength by feeding the vertex
1851      * location directly into a texture */
1852     avg = BKE_brush_sample_tex_3d(scene, br, point, rgba, 0, ss->tex_pool);
1853   }
1854   else if (ss->texcache) {
1855     float symm_point[3], point_2d[2];
1856     float x = 0.0f, y = 0.0f; /* Quite warnings */
1857
1858     /* if the active area is being applied for symmetry, flip it
1859      * across the symmetry axis and rotate it back to the original
1860      * position in order to project it. This insures that the
1861      * brush texture will be oriented correctly. */
1862
1863     flip_v3_v3(symm_point, point, cache->mirror_symmetry_pass);
1864
1865     if (cache->radial_symmetry_pass) {
1866       mul_m4_v3(cache->symm_rot_mat_inv, symm_point);
1867     }
1868
1869     ED_view3d_project_float_v2_m4(cache->vc->ar, symm_point, point_2d, cache->projection_mat);
1870
1871     /* still no symmetry supported for other paint modes.
1872      * Sculpt does it DIY */
1873     if (mtex->brush_map_mode == MTEX_MAP_MODE_AREA) {
1874       /* Similar to fixed mode, but projects from brush angle
1875        * rather than view direction */
1876
1877       mul_m4_v3(cache->brush_local_mat, symm_point);
1878
1879       x = symm_point[0];
1880       y = symm_point[1];
1881
1882       x *= br->mtex.size[0];
1883       y *= br->mtex.size[1];
1884
1885       x += br->mtex.ofs[0];
1886       y += br->mtex.ofs[1];
1887
1888       avg = paint_get_tex_pixel(&br->mtex, x, y, ss->tex_pool, thread_id);
1889
1890       avg += br->texture_sample_bias;
1891     }
1892     else {
1893       const float point_3d[3] = {point_2d[0], point_2d[1], 0.0f};
1894       avg = BKE_brush_sample_tex_3d(scene, br, point_3d, rgba, 0, ss->tex_pool);
1895     }
1896   }
1897
1898   /* Falloff curve */
1899   avg *= BKE_brush_curve_strength(br, len, cache->radius);
1900   avg *= frontface(br, cache->view_normal, vno, fno);
1901
1902   /* Paint mask */
1903   avg *= 1.0f - mask;
1904
1905   /* Automasking */
1906   avg *= sculpt_automasking_factor_get(ss, vertex_index);
1907
1908   return avg;
1909 }
1910
1911 /* Test AABB against sphere */
1912 bool sculpt_search_sphere_cb(PBVHNode *node, void *data_v)
1913 {
1914   SculptSearchSphereData *data = data_v;
1915   float *center, nearest[3];
1916   if (data->center) {
1917     center = data->center;
1918   }
1919   else {
1920     center = data->ss->cache ? data->ss->cache->location : data->ss->cursor_location;
1921   }
1922   float t[3], bb_min[3], bb_max[3];
1923   int i;
1924
1925   if (data->ignore_fully_masked) {
1926     if (BKE_pbvh_node_fully_masked_get(node)) {
1927       return false;
1928     }
1929   }
1930
1931   if (data->original) {
1932     BKE_pbvh_node_get_original_BB(node, bb_min, bb_max);
1933   }
1934   else {
1935     BKE_pbvh_node_get_BB(node, bb_min, bb_max);
1936   }
1937
1938   for (i = 0; i < 3; i++) {
1939     if (bb_min[i] > center[i]) {
1940       nearest[i] = bb_min[i];
1941     }
1942     else if (bb_max[i] < center[i]) {
1943       nearest[i] = bb_max[i];
1944     }
1945     else {
1946       nearest[i] = center[i];
1947     }
1948   }
1949
1950   sub_v3_v3v3(t, center, nearest);
1951
1952   return len_squared_v3(t) < data->radius_squared;
1953 }
1954
1955 /* 2D projection (distance to line). */
1956 bool sculpt_search_circle_cb(PBVHNode *node, void *data_v)
1957 {
1958   SculptSearchCircleData *data = data_v;
1959   float bb_min[3], bb_max[3];
1960
1961   if (data->ignore_fully_masked) {
1962     if (BKE_pbvh_node_fully_masked_get(node)) {
1963       return false;
1964     }
1965   }
1966
1967   if (data->original) {
1968     BKE_pbvh_node_get_original_BB(node, bb_min, bb_max);
1969   }
1970   else {
1971     BKE_pbvh_node_get_BB(node, bb_min, bb_min);
1972   }
1973
1974   float dummy_co[3], dummy_depth;
1975   const float dist_sq = dist_squared_ray_to_aabb_v3(
1976       data->dist_ray_to_aabb_precalc, bb_min, bb_max, dummy_co, &dummy_depth);
1977
1978   return dist_sq < data->radius_squared || 1;
1979 }
1980
1981 /* Handles clipping against a mirror modifier and SCULPT_LOCK axis flags */
1982 static void sculpt_clip(Sculpt *sd, SculptSession *ss, float co[3], const float val[3])
1983 {
1984   int i;
1985
1986   for (i = 0; i < 3; i++) {
1987     if (sd->flags & (SCULPT_LOCK_X << i)) {
1988       continue;
1989     }
1990
1991     if ((ss->cache->flag & (CLIP_X << i)) && (fabsf(co[i]) <= ss->cache->clip_tolerance[i])) {
1992       co[i] = 0.0f;
1993     }
1994     else {
1995       co[i] = val[i];
1996     }
1997   }
1998 }
1999
2000 static PBVHNode **sculpt_pbvh_gather_cursor_update(Object *ob,
2001                                                    Sculpt *sd,
2002                                                    bool use_original,
2003                                                    int *r_totnode)
2004 {
2005   SculptSession *ss = ob->sculpt;
2006   PBVHNode **nodes = NULL;
2007   SculptSearchSphereData data = {
2008       .ss = ss,
2009       .sd = sd,
2010       .radius_squared = ss->cursor_radius,
2011       .original = use_original,
2012       .ignore_fully_masked = false,
2013       .center = NULL,
2014   };
2015   BKE_pbvh_search_gather(ss->pbvh, sculpt_search_sphere_cb, &data, &nodes, r_totnode);
2016   return nodes;
2017 }
2018
2019 static PBVHNode **sculpt_pbvh_gather_generic(Object *ob,
2020                                              Sculpt *sd,
2021                                              const Brush *brush,
2022                                              bool use_original,
2023                                              float radius_scale,
2024                                              int *r_totnode)
2025 {
2026   SculptSession *ss = ob->sculpt;
2027   PBVHNode **nodes = NULL;
2028
2029   /* Build a list of all nodes that are potentially within the cursor or brush's area of influence
2030    */
2031   if (brush->falloff_shape == PAINT_FALLOFF_SHAPE_SPHERE) {
2032     SculptSearchSphereData data = {
2033         .ss = ss,
2034         .sd = sd,
2035         .radius_squared = SQUARE(ss->cache->radius * radius_scale),
2036         .original = use_original,
2037         .ignore_fully_masked = brush->sculpt_tool != SCULPT_TOOL_MASK,
2038         .center = NULL,
2039     };
2040     BKE_pbvh_search_gather(ss->pbvh, sculpt_search_sphere_cb, &data, &nodes, r_totnode);
2041   }
2042   else {
2043     struct DistRayAABB_Precalc dist_ray_to_aabb_precalc;
2044     dist_squared_ray_to_aabb_v3_precalc(
2045         &dist_ray_to_aabb_precalc, ss->cache->location, ss->cache->view_normal);
2046     SculptSearchCircleData data = {
2047         .ss = ss,
2048         .sd = sd,
2049         .radius_squared = ss->cache ? SQUARE(ss->cache->radius * radius_scale) : ss->cursor_radius,
2050         .original = use_original,
2051         .dist_ray_to_aabb_precalc = &dist_ray_to_aabb_precalc,
2052         .ignore_fully_masked = brush->sculpt_tool != SCULPT_TOOL_MASK,
2053     };
2054     BKE_pbvh_search_gather(ss->pbvh, sculpt_search_circle_cb, &data, &nodes, r_totnode);
2055   }
2056   return nodes;
2057 }
2058
2059 /* Calculate primary direction of movement for many brushes */
2060 static void calc_sculpt_normal(
2061     Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode, float r_area_no[3])
2062 {
2063   const Brush *brush = BKE_paint_brush(&sd->paint);
2064   const SculptSession *ss = ob->sculpt;
2065
2066   switch (brush->sculpt_plane) {
2067     case SCULPT_DISP_DIR_VIEW:
2068       copy_v3_v3(r_area_no, ss->cache->true_view_normal);
2069       break;
2070
2071     case SCULPT_DISP_DIR_X:
2072       ARRAY_SET_ITEMS(r_area_no, 1, 0, 0);
2073       break;
2074
2075     case SCULPT_DISP_DIR_Y:
2076       ARRAY_SET_ITEMS(r_area_no, 0, 1, 0);
2077       break;
2078
2079     case SCULPT_DISP_DIR_Z:
2080       ARRAY_SET_ITEMS(r_area_no, 0, 0, 1);
2081       break;
2082
2083     case SCULPT_DISP_DIR_AREA:
2084       calc_area_normal(sd, ob, nodes, totnode, r_area_no);
2085       break;
2086
2087     default:
2088       break;
2089   }
2090 }
2091
2092 static void update_sculpt_normal(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2093 {
2094   const Brush *brush = BKE_paint_brush(&sd->paint);
2095   StrokeCache *cache = ob->sculpt->cache;
2096   /* Grab brush does not update the sculpt normal during a stroke */
2097   const bool update_normal = !(brush->flag & BRUSH_ORIGINAL_NORMAL) &&
2098                              !(brush->sculpt_tool == SCULPT_TOOL_GRAB) &&
2099                              !(brush->sculpt_tool == SCULPT_TOOL_ELASTIC_DEFORM) &&
2100                              !(brush->sculpt_tool == SCULPT_TOOL_SNAKE_HOOK &&
2101                                cache->normal_weight > 0.0f);
2102
2103   if (cache->mirror_symmetry_pass == 0 && cache->radial_symmetry_pass == 0 &&
2104       (cache->first_time || update_normal)) {
2105     calc_sculpt_normal(sd, ob, nodes, totnode, cache->sculpt_normal);
2106     if (brush->falloff_shape == PAINT_FALLOFF_SHAPE_TUBE) {
2107       project_plane_v3_v3v3(cache->sculpt_normal, cache->sculpt_normal, cache->view_normal);
2108       normalize_v3(cache->sculpt_normal);
2109     }
2110     copy_v3_v3(cache->sculpt_normal_symm, cache->sculpt_normal);
2111   }
2112   else {
2113     copy_v3_v3(cache->sculpt_normal_symm, cache->sculpt_normal);
2114     flip_v3(cache->sculpt_normal_symm, cache->mirror_symmetry_pass);
2115     mul_m4_v3(cache->symm_rot_mat, cache->sculpt_normal_symm);
2116   }
2117 }
2118
2119 static void calc_local_y(ViewContext *vc, const float center[3], float y[3])
2120 {
2121   Object *ob = vc->obact;
2122   float loc[3], mval_f[2] = {0.0f, 1.0f};
2123   float zfac;
2124
2125   mul_v3_m4v3(loc, ob->imat, center);
2126   zfac = ED_view3d_calc_zfac(vc->rv3d, loc, NULL);
2127
2128   ED_view3d_win_to_delta(vc->ar, mval_f, y, zfac);
2129   normalize_v3(y);
2130
2131   add_v3_v3(y, ob->loc);
2132   mul_m4_v3(ob->imat, y);
2133 }
2134
2135 static void calc_brush_local_mat(const Brush *brush, Object *ob, float local_mat[4][4])
2136 {
2137   const StrokeCache *cache = ob->sculpt->cache;
2138   float tmat[4][4];
2139   float mat[4][4];
2140   float scale[4][4];
2141   float angle, v[3];
2142   float up[3];
2143
2144   /* Ensure ob->imat is up to date */
2145   invert_m4_m4(ob->imat, ob->obmat);
2146
2147   /* Initialize last column of matrix */
2148   mat[0][3] = 0;
2149   mat[1][3] = 0;
2150   mat[2][3] = 0;
2151   mat[3][3] = 1;
2152
2153   /* Get view's up vector in object-space */
2154   calc_local_y(cache->vc, cache->location, up);
2155
2156   /* Calculate the X axis of the local matrix */
2157   cross_v3_v3v3(v, up, cache->sculpt_normal);
2158   /* Apply rotation (user angle, rake, etc.) to X axis */
2159   angle = brush->mtex.rot - cache->special_rotation;
2160   rotate_v3_v3v3fl(mat[0], v, cache->sculpt_normal, angle);
2161
2162   /* Get other axes */
2163   cross_v3_v3v3(mat[1], cache->sculpt_normal, mat[0]);
2164   copy_v3_v3(mat[2], cache->sculpt_normal);
2165
2166   /* Set location */
2167   copy_v3_v3(mat[3], cache->location);
2168
2169   /* Scale by brush radius */
2170   normalize_m4(mat);
2171   scale_m4_fl(scale, cache->radius);
2172   mul_m4_m4m4(tmat, mat, scale);
2173
2174   /* Return inverse (for converting from modelspace coords to local
2175    * area coords) */
2176   invert_m4_m4(local_mat, tmat);
2177 }
2178
2179 static void update_brush_local_mat(Sculpt *sd, Object *ob)
2180 {
2181   StrokeCache *cache = ob->sculpt->cache;
2182
2183   if (cache->mirror_symmetry_pass == 0 && cache->radial_symmetry_pass == 0) {
2184     calc_brush_local_mat(BKE_paint_brush(&sd->paint), ob, cache->brush_local_mat);
2185   }
2186 }
2187
2188 /* For the smooth brush, uses the neighboring vertices around vert to calculate
2189  * a smoothed location for vert. Skips corner vertices (used by only one
2190  * polygon.) */
2191 static void neighbor_average(SculptSession *ss, float avg[3], unsigned vert)
2192 {
2193   const MeshElemMap *vert_map = &ss->pmap[vert];
2194   const MVert *mvert = ss->mvert;
2195   float(*deform_co)[3] = ss->deform_cos;
2196
2197   /* Don't modify corner vertices */
2198   if (vert_map->count > 1) {
2199     int i, total = 0;
2200
2201     zero_v3(avg);
2202
2203     for (i = 0; i < vert_map->count; i++) {
2204       const MPoly *p = &ss->mpoly[vert_map->indices[i]];
2205       unsigned f_adj_v[2];
2206
2207       if (poly_get_adj_loops_from_vert(p, ss->mloop, vert, f_adj_v) != -1) {
2208         int j;
2209         for (j = 0; j < ARRAY_SIZE(f_adj_v); j += 1) {
2210           if (vert_map->count != 2 || ss->pmap[f_adj_v[j]].count <= 2) {
2211             add_v3_v3(avg, deform_co ? deform_co[f_adj_v[j]] : mvert[f_adj_v[j]].co);
2212
2213             total++;
2214           }
2215         }
2216       }
2217     }
2218
2219     if (total > 0) {
2220       mul_v3_fl(avg, 1.0f / total);
2221       return;
2222     }
2223   }
2224
2225   copy_v3_v3(avg, deform_co ? deform_co[vert] : mvert[vert].co);
2226 }
2227
2228 /* Similar to neighbor_average(), but returns an averaged mask value
2229  * instead of coordinate. Also does not restrict based on border or
2230  * corner vertices. */
2231 static float neighbor_average_mask(SculptSession *ss, unsigned vert)
2232 {
2233   const float *vmask = ss->vmask;
2234   float avg = 0;
2235   int i, total = 0;
2236
2237   for (i = 0; i < ss->pmap[vert].count; i++) {
2238     const MPoly *p = &ss->mpoly[ss->pmap[vert].indices[i]];
2239     unsigned f_adj_v[2];
2240
2241     if (poly_get_adj_loops_from_vert(p, ss->mloop, vert, f_adj_v) != -1) {
2242       int j;
2243       for (j = 0; j < ARRAY_SIZE(f_adj_v); j += 1) {
2244         avg += vmask[f_adj_v[j]];
2245         total++;
2246       }
2247     }
2248   }
2249
2250   if (total > 0) {
2251     return avg / (float)total;
2252   }
2253   else {
2254     return vmask[vert];
2255   }
2256 }
2257
2258 /* Same logic as neighbor_average(), but for bmesh rather than mesh */
2259 static void bmesh_neighbor_average(float avg[3], BMVert *v)
2260 {
2261   /* logic for 3 or more is identical */
2262   const int vfcount = BM_vert_face_count_at_most(v, 3);
2263
2264   /* Don't modify corner vertices */
2265   if (vfcount > 1) {
2266     BMIter liter;
2267     BMLoop *l;
2268     int i, total = 0;
2269
2270     zero_v3(avg);
2271
2272     BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
2273       const BMVert *adj_v[2] = {l->prev->v, l->next->v};
2274
2275       for (i = 0; i < ARRAY_SIZE(adj_v); i++) {
2276         const BMVert *v_other = adj_v[i];
2277         if (vfcount != 2 || BM_vert_face_count_at_most(v_other, 2) <= 2) {
2278           add_v3_v3(avg, v_other->co);
2279           total++;
2280         }
2281       }
2282     }
2283
2284     if (total > 0) {
2285       mul_v3_fl(avg, 1.0f / total);
2286       return;
2287     }
2288   }
2289
2290   copy_v3_v3(avg, v->co);
2291 }
2292
2293 /* For bmesh: Average surrounding verts based on an orthogonality measure.
2294  * Naturally converges to a quad-like structure. */
2295 static void bmesh_four_neighbor_average(float avg[3], float direction[3], BMVert *v)
2296 {
2297
2298   float avg_co[3] = {0, 0, 0};
2299   float tot_co = 0;
2300
2301   BMIter eiter;
2302   BMEdge *e;
2303
2304   BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
2305     if (BM_edge_is_boundary(e)) {
2306       copy_v3_v3(avg, v->co);
2307       return;
2308     }
2309     BMVert *v_other = (e->v1 == v) ? e->v2 : e->v1;
2310     float vec[3];
2311     sub_v3_v3v3(vec, v_other->co, v->co);
2312     madd_v3_v3fl(vec, v->no, -dot_v3v3(vec, v->no));
2313     normalize_v3(vec);
2314
2315     /* fac is a measure of how orthogonal or parallel the edge is
2316      * relative to the direction */
2317     float fac = dot_v3v3(vec, direction);
2318     fac = fac * fac - 0.5f;
2319     fac *= fac;
2320     madd_v3_v3fl(avg_co, v_other->co, fac);
2321     tot_co += fac;
2322   }
2323
2324   /* In case vert has no Edge s */
2325   if (tot_co > 0) {
2326     mul_v3_v3fl(avg, avg_co, 1.0f / tot_co);
2327
2328     /* Preserve volume. */
2329     float vec[3];
2330     sub_v3_v3(avg, v->co);
2331     mul_v3_v3fl(vec, v->no, dot_v3v3(avg, v->no));
2332     sub_v3_v3(avg, vec);
2333     add_v3_v3(avg, v->co);
2334   }
2335   else {
2336     zero_v3(avg);
2337   }
2338 }
2339
2340 /* Same logic as neighbor_average_mask(), but for bmesh rather than mesh */
2341 static float bmesh_neighbor_average_mask(BMVert *v, const int cd_vert_mask_offset)
2342 {
2343   BMIter liter;
2344   BMLoop *l;
2345   float avg = 0;
2346   int i, total = 0;
2347
2348   BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
2349     /* skip this vertex */
2350     const BMVert *adj_v[2] = {l->prev->v, l->next->v};
2351
2352     for (i = 0; i < ARRAY_SIZE(adj_v); i++) {
2353       const BMVert *v_other = adj_v[i];
2354       const float *vmask = BM_ELEM_CD_GET_VOID_P(v_other, cd_vert_mask_offset);
2355       avg += (*vmask);
2356       total++;
2357     }
2358   }
2359
2360   if (total > 0) {
2361     return avg / (float)total;
2362   }
2363   else {
2364     const float *vmask = BM_ELEM_CD_GET_VOID_P(v, cd_vert_mask_offset);
2365     return (*vmask);
2366   }
2367 }
2368
2369 static void grids_neighbor_average(SculptSession *ss, float result[3], int index)
2370 {
2371   float avg[3] = {0.0f, 0.0f, 0.0f};
2372   int total = 0;
2373
2374   SculptVertexNeighborIter ni;
2375   sculpt_vertex_neighbors_iter_begin(ss, index, ni)
2376   {
2377     add_v3_v3(avg, sculpt_vertex_co_get(ss, ni.index));
2378     total++;
2379   }
2380   sculpt_vertex_neighbors_iter_end(ni);
2381
2382   if (total > 0) {
2383     mul_v3_v3fl(result, avg, 1.0f / (float)total);
2384   }
2385   else {
2386     copy_v3_v3(result, sculpt_vertex_co_get(ss, index));
2387   }
2388 }
2389
2390 static float grids_neighbor_average_mask(SculptSession *ss, int index)
2391 {
2392   float avg = 0.0f;
2393   int total = 0;
2394
2395   SculptVertexNeighborIter ni;
2396   sculpt_vertex_neighbors_iter_begin(ss, index, ni)
2397   {
2398     avg += sculpt_vertex_mask_get(ss, ni.index);
2399     total++;
2400   }
2401   sculpt_vertex_neighbors_iter_end(ni);
2402
2403   if (total > 0) {
2404     return avg / (float)total;
2405   }
2406   else {
2407     return sculpt_vertex_mask_get(ss, index);
2408   }
2409 }
2410
2411 /* Note: uses after-struct allocated mem to store actual cache... */
2412 typedef struct SculptDoBrushSmoothGridDataChunk {
2413   size_t tmpgrid_size;
2414 } SculptDoBrushSmoothGridDataChunk;
2415
2416 typedef struct {
2417   SculptSession *ss;
2418   const float *ray_start;
2419   const float *ray_normal;
2420   bool hit;
2421   float depth;
2422   bool original;
2423
2424   int active_vertex_index;
2425   float *face_normal;
2426
2427   struct IsectRayPrecalc isect_precalc;
2428 } SculptRaycastData;
2429
2430 typedef struct {
2431   const float *ray_start;
2432   bool hit;
2433   float depth;
2434   float edge_length;
2435
2436   struct IsectRayPrecalc isect_precalc;
2437 } SculptDetailRaycastData;
2438
2439 typedef struct {
2440   SculptSession *ss;
2441   const float *ray_start, *ray_normal;
2442   bool hit;
2443   float depth;
2444   float dist_sq_to_ray;
2445   bool original;
2446 } SculptFindNearestToRayData;
2447
2448 static void do_smooth_brush_mesh_task_cb_ex(void *__restrict userdata,
2449                                             const int n,
2450                                             const TaskParallelTLS *__restrict tls)
2451 {
2452   SculptThreadedTaskData *data = userdata;
2453   SculptSession *ss = data->ob->sculpt;
2454   Sculpt *sd = data->sd;
2455   const Brush *brush = data->brush;
2456   const bool smooth_mask = data->smooth_mask;
2457   float bstrength = data->strength;
2458
2459   PBVHVertexIter vd;
2460
2461   CLAMP(bstrength, 0.0f, 1.0f);
2462
2463   SculptBrushTest test;
2464   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
2465       ss, &test, data->brush->falloff_shape);
2466
2467   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
2468   {
2469     if (sculpt_brush_test_sq_fn(&test, vd.co)) {
2470       const float fade = bstrength * tex_strength(ss,
2471                                                   brush,
2472                                                   vd.co,
2473                                                   sqrtf(test.dist),
2474                                                   vd.no,
2475                                                   vd.fno,
2476                                                   smooth_mask ? 0.0f : (vd.mask ? *vd.mask : 0.0f),
2477                                                   vd.index,
2478                                                   tls->thread_id);
2479       if (smooth_mask) {
2480         float val = neighbor_average_mask(ss, vd.vert_indices[vd.i]) - *vd.mask;
2481         val *= fade * bstrength;
2482         *vd.mask += val;
2483         CLAMP(*vd.mask, 0.0f, 1.0f);
2484       }
2485       else {
2486         float avg[3], val[3];
2487
2488         neighbor_average(ss, avg, vd.vert_indices[vd.i]);
2489         sub_v3_v3v3(val, avg, vd.co);
2490
2491         madd_v3_v3v3fl(val, vd.co, val, fade);
2492
2493         sculpt_clip(sd, ss, vd.co, val);
2494       }
2495
2496       if (vd.mvert) {
2497         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2498       }
2499     }
2500   }
2501   BKE_pbvh_vertex_iter_end;
2502 }
2503
2504 static void do_smooth_brush_bmesh_task_cb_ex(void *__restrict userdata,
2505                                              const int n,
2506                                              const TaskParallelTLS *__restrict tls)
2507 {
2508   SculptThreadedTaskData *data = userdata;
2509   SculptSession *ss = data->ob->sculpt;
2510   Sculpt *sd = data->sd;
2511   const Brush *brush = data->brush;
2512   const bool smooth_mask = data->smooth_mask;
2513   float bstrength = data->strength;
2514
2515   PBVHVertexIter vd;
2516
2517   CLAMP(bstrength, 0.0f, 1.0f);
2518
2519   SculptBrushTest test;
2520   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
2521       ss, &test, data->brush->falloff_shape);
2522
2523   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
2524   {
2525     if (sculpt_brush_test_sq_fn(&test, vd.co)) {
2526       const float fade = bstrength * tex_strength(ss,
2527                                                   brush,
2528                                                   vd.co,
2529                                                   sqrtf(test.dist),
2530                                                   vd.no,
2531                                                   vd.fno,
2532                                                   smooth_mask ? 0.0f : *vd.mask,
2533                                                   vd.index,
2534                                                   tls->thread_id);
2535       if (smooth_mask) {
2536         float val = bmesh_neighbor_average_mask(vd.bm_vert, vd.cd_vert_mask_offset) - *vd.mask;
2537         val *= fade * bstrength;
2538         *vd.mask += val;
2539         CLAMP(*vd.mask, 0.0f, 1.0f);
2540       }
2541       else {
2542         float avg[3], val[3];
2543
2544         bmesh_neighbor_average(avg, vd.bm_vert);
2545         sub_v3_v3v3(val, avg, vd.co);
2546
2547         madd_v3_v3v3fl(val, vd.co, val, fade);
2548
2549         sculpt_clip(sd, ss, vd.co, val);
2550       }
2551
2552       if (vd.mvert) {
2553         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2554       }
2555     }
2556   }
2557   BKE_pbvh_vertex_iter_end;
2558 }
2559
2560 static void do_topology_rake_bmesh_task_cb_ex(void *__restrict userdata,
2561                                               const int n,
2562                                               const TaskParallelTLS *__restrict tls)
2563 {
2564   SculptThreadedTaskData *data = userdata;
2565   SculptSession *ss = data->ob->sculpt;
2566   Sculpt *sd = data->sd;
2567   const Brush *brush = data->brush;
2568
2569   float direction[3];
2570   copy_v3_v3(direction, ss->cache->grab_delta_symmetry);
2571
2572   float tmp[3];
2573   mul_v3_v3fl(
2574       tmp, ss->cache->sculpt_normal_symm, dot_v3v3(ss->cache->sculpt_normal_symm, direction));
2575   sub_v3_v3(direction, tmp);
2576   normalize_v3(direction);
2577
2578   /* Cancel if there's no grab data. */
2579   if (is_zero_v3(direction)) {
2580     return;
2581   }
2582
2583   float bstrength = data->strength;
2584   CLAMP(bstrength, 0.0f, 1.0f);
2585
2586   SculptBrushTest test;
2587   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
2588       ss, &test, data->brush->falloff_shape);
2589
2590   PBVHVertexIter vd;
2591   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
2592   {
2593     if (sculpt_brush_test_sq_fn(&test, vd.co)) {
2594       const float fade = bstrength *
2595                          tex_strength(ss,
2596                                       brush,
2597                                       vd.co,
2598                                       sqrtf(test.dist),
2599                                       vd.no,
2600                                       vd.fno,
2601                                       *vd.mask,
2602                                       vd.index,
2603                                       tls->thread_id) *
2604                          ss->cache->pressure;
2605
2606       float avg[3], val[3];
2607
2608       bmesh_four_neighbor_average(avg, direction, vd.bm_vert);
2609
2610       sub_v3_v3v3(val, avg, vd.co);
2611
2612       madd_v3_v3v3fl(val, vd.co, val, fade);
2613
2614       sculpt_clip(sd, ss, vd.co, val);
2615
2616       if (vd.mvert) {
2617         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2618       }
2619     }
2620   }
2621   BKE_pbvh_vertex_iter_end;
2622 }
2623
2624 static void do_smooth_brush_multires_task_cb_ex(void *__restrict userdata,
2625                                                 const int n,
2626                                                 const TaskParallelTLS *__restrict tls)
2627 {
2628   SculptThreadedTaskData *data = userdata;
2629   SculptDoBrushSmoothGridDataChunk *data_chunk = tls->userdata_chunk;
2630   SculptSession *ss = data->ob->sculpt;
2631   Sculpt *sd = data->sd;
2632   const Brush *brush = data->brush;
2633   const bool smooth_mask = data->smooth_mask;
2634   float bstrength = data->strength;
2635
2636   CCGElem **griddata, *gddata;
2637
2638   float(*tmpgrid_co)[3] = NULL;
2639   float tmprow_co[2][3];
2640   float *tmpgrid_mask = NULL;
2641   float tmprow_mask[2];
2642
2643   BLI_bitmap *const *grid_hidden;
2644   int *grid_indices, totgrid, gridsize;
2645   int i, x, y;
2646
2647   SculptBrushTest test;
2648   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
2649       ss, &test, data->brush->falloff_shape);
2650
2651   CLAMP(bstrength, 0.0f, 1.0f);
2652
2653   BKE_pbvh_node_get_grids(
2654       ss->pbvh, data->nodes[n], &grid_indices, &totgrid, NULL, &gridsize, &griddata);
2655   CCGKey key = *BKE_pbvh_get_grid_key(ss->pbvh);
2656
2657   grid_hidden = BKE_pbvh_grid_hidden(ss->pbvh);
2658
2659   if (smooth_mask) {
2660     tmpgrid_mask = (void *)(data_chunk + 1);
2661   }
2662   else {
2663     tmpgrid_co = (void *)(data_chunk + 1);
2664   }
2665
2666   for (i = 0; i < totgrid; i++) {
2667     int gi = grid_indices[i];
2668     const BLI_bitmap *gh = grid_hidden[gi];
2669     gddata = griddata[gi];
2670
2671     if (smooth_mask) {
2672       memset(tmpgrid_mask, 0, data_chunk->tmpgrid_size);
2673     }
2674     else {
2675       memset(tmpgrid_co, 0, data_chunk->tmpgrid_size);
2676     }
2677
2678     for (y = 0; y < gridsize - 1; y++) {
2679       const int v = y * gridsize;
2680       if (smooth_mask) {
2681         tmprow_mask[0] = (*CCG_elem_offset_mask(&key, gddata, v) +
2682                           *CCG_elem_offset_mask(&key, gddata, v + gridsize));
2683       }
2684       else {
2685         add_v3_v3v3(tmprow_co[0],
2686                     CCG_elem_offset_co(&key, gddata, v),
2687                     CCG_elem_offset_co(&key, gddata, v + gridsize));
2688       }
2689
2690       for (x = 0; x < gridsize - 1; x++) {
2691         const int v1 = x + y * gridsize;
2692         const int v2 = v1 + 1;
2693         const int v3 = v1 + gridsize;
2694         const int v4 = v3 + 1;
2695
2696         if (smooth_mask) {
2697           float tmp;
2698
2699           tmprow_mask[(x + 1) % 2] = (*CCG_elem_offset_mask(&key, gddata, v2) +
2700                                       *CCG_elem_offset_mask(&key, gddata, v4));
2701           tmp = tmprow_mask[(x + 1) % 2] + tmprow_mask[x % 2];
2702
2703           tmpgrid_mask[v1] += tmp;
2704           tmpgrid_mask[v2] += tmp;
2705           tmpgrid_mask[v3] += tmp;
2706           tmpgrid_mask[v4] += tmp;
2707         }
2708         else {
2709           float tmp[3];
2710
2711           add_v3_v3v3(tmprow_co[(x + 1) % 2],
2712                       CCG_elem_offset_co(&key, gddata, v2),
2713                       CCG_elem_offset_co(&key, gddata, v4));
2714           add_v3_v3v3(tmp, tmprow_co[(x + 1) % 2], tmprow_co[x % 2]);
2715
2716           add_v3_v3(tmpgrid_co[v1], tmp);
2717           add_v3_v3(tmpgrid_co[v2], tmp);
2718           add_v3_v3(tmpgrid_co[v3], tmp);
2719           add_v3_v3(tmpgrid_co[v4], tmp);
2720         }
2721       }
2722     }
2723
2724     /* blend with existing coordinates */
2725     for (y = 0; y < gridsize; y++) {
2726       for (x = 0; x < gridsize; x++) {
2727         float *co;
2728         const float *fno;
2729         float *mask;
2730         const int index = y * gridsize + x;
2731
2732         if (gh) {
2733           if (BLI_BITMAP_TEST(gh, index)) {
2734             continue;
2735           }
2736         }
2737
2738         co = CCG_elem_offset_co(&key, gddata, index);
2739         fno = CCG_elem_offset_no(&key, gddata, index);
2740         mask = CCG_elem_offset_mask(&key, gddata, index);
2741
2742         if (sculpt_brush_test_sq_fn(&test, co)) {
2743           const float strength_mask = (smooth_mask ? 0.0f : *mask);
2744           const float fade =
2745               bstrength *
2746               tex_strength(
2747                   ss, brush, co, sqrtf(test.dist), NULL, fno, strength_mask, 0, tls->thread_id);
2748           float f = 1.0f / 16.0f;
2749
2750           if (x == 0 || x == gridsize - 1) {
2751             f *= 2.0f;
2752           }
2753
2754           if (y == 0 || y == gridsize - 1) {
2755             f *= 2.0f;
2756           }
2757
2758           if (smooth_mask) {
2759             *mask += ((tmpgrid_mask[index] * f) - *mask) * fade;
2760           }
2761           else {
2762             float *avg = tmpgrid_co[index];
2763             float val[3];
2764
2765             mul_v3_fl(avg, f);
2766             sub_v3_v3v3(val, avg, co);
2767             madd_v3_v3v3fl(val, co, val, fade);
2768
2769             sculpt_clip(sd, ss, co, val);
2770           }
2771         }
2772       }
2773     }
2774   }
2775 }
2776
2777 static void smooth(Sculpt *sd,
2778                    Object *ob,
2779                    PBVHNode **nodes,
2780                    const int totnode,
2781                    float bstrength,
2782                    const bool smooth_mask)
2783 {
2784   SculptSession *ss = ob->sculpt;
2785   Brush *brush = BKE_paint_brush(&sd->paint);
2786
2787   const int max_iterations = 4;
2788   const float fract = 1.0f / max_iterations;
2789   PBVHType type = BKE_pbvh_type(ss->pbvh);
2790   int iteration, count;
2791   float last;
2792
2793   CLAMP(bstrength, 0.0f, 1.0f);
2794
2795   count = (int)(bstrength * max_iterations);
2796   last = max_iterations * (bstrength - count * fract);
2797
2798   if (type == PBVH_FACES && !ss->pmap) {
2799     BLI_assert(!"sculpt smooth: pmap missing");
2800     return;
2801   }
2802
2803   for (iteration = 0; iteration <= count; iteration++) {
2804     const float strength = (iteration != count) ? 1.0f : last;
2805
2806     SculptThreadedTaskData data = {
2807         .sd = sd,
2808         .ob = ob,
2809         .brush = brush,
2810         .nodes = nodes,
2811         .smooth_mask = smooth_mask,
2812         .strength = strength,
2813     };
2814
2815     PBVHParallelSettings settings;
2816     BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
2817
2818     switch (type) {
2819       case PBVH_GRIDS: {
2820         int gridsize;
2821         size_t size;
2822         SculptDoBrushSmoothGridDataChunk *data_chunk;
2823
2824         BKE_pbvh_node_get_grids(ss->pbvh, NULL, NULL, NULL, NULL, &gridsize, NULL);
2825         size = (size_t)gridsize;
2826         size = sizeof(float) * size * size * (smooth_mask ? 1 : 3);
2827         data_chunk = MEM_mallocN(sizeof(*data_chunk) + size, __func__);
2828         data_chunk->tmpgrid_size = size;
2829         size += sizeof(*data_chunk);
2830
2831         settings.userdata_chunk = data_chunk;
2832         settings.userdata_chunk_size = size;
2833         BKE_pbvh_parallel_range(0, totnode, &data, do_smooth_brush_multires_task_cb_ex, &settings);
2834
2835         MEM_freeN(data_chunk);
2836         break;
2837       }
2838       case PBVH_FACES:
2839         BKE_pbvh_parallel_range(0, totnode, &data, do_smooth_brush_mesh_task_cb_ex, &settings);
2840         break;
2841       case PBVH_BMESH:
2842         BKE_pbvh_parallel_range(0, totnode, &data, do_smooth_brush_bmesh_task_cb_ex, &settings);
2843         break;
2844     }
2845
2846     if (ss->multires) {
2847       multires_stitch_grids(ob);
2848     }
2849   }
2850 }
2851
2852 static void bmesh_topology_rake(
2853     Sculpt *sd, Object *ob, PBVHNode **nodes, const int totnode, float bstrength)
2854 {
2855   Brush *brush = BKE_paint_brush(&sd->paint);
2856   CLAMP(bstrength, 0.0f, 1.0f);
2857
2858   /* Interactions increase both strength and quality. */
2859   const int iterations = 3;
2860
2861   int iteration;
2862   const int count = iterations * bstrength + 1;
2863   const float factor = iterations * bstrength / count;
2864
2865   for (iteration = 0; iteration <= count; iteration++) {
2866
2867     SculptThreadedTaskData data = {
2868         .sd = sd,
2869         .ob = ob,
2870         .brush = brush,
2871         .nodes = nodes,
2872         .strength = factor,
2873     };
2874     PBVHParallelSettings settings;
2875     BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
2876
2877     BKE_pbvh_parallel_range(0, totnode, &data, do_topology_rake_bmesh_task_cb_ex, &settings);
2878   }
2879 }
2880
2881 static void do_smooth_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2882 {
2883   SculptSession *ss = ob->sculpt;
2884   smooth(sd, ob, nodes, totnode, ss->cache->bstrength, false);
2885 }
2886
2887 static void do_mask_brush_draw_task_cb_ex(void *__restrict userdata,
2888                                           const int n,
2889                                           const TaskParallelTLS *__restrict tls)
2890 {
2891   SculptThreadedTaskData *data = userdata;
2892   SculptSession *ss = data->ob->sculpt;
2893   const Brush *brush = data->brush;
2894   const float bstrength = ss->cache->bstrength;
2895
2896   PBVHVertexIter vd;
2897
2898   SculptBrushTest test;
2899   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
2900       ss, &test, data->brush->falloff_shape);
2901
2902   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
2903   {
2904     if (sculpt_brush_test_sq_fn(&test, vd.co)) {
2905       const float fade = tex_strength(
2906           ss, brush, vd.co, sqrtf(test.dist), vd.no, vd.fno, 0.0f, vd.index, tls->thread_id);
2907
2908       (*vd.mask) += fade * bstrength;
2909       CLAMP(*vd.mask, 0, 1);
2910
2911       if (vd.mvert) {
2912         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2913       }
2914     }
2915     BKE_pbvh_vertex_iter_end;
2916   }
2917 }
2918
2919 static void do_mask_brush_draw(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2920 {
2921   Brush *brush = BKE_paint_brush(&sd->paint);
2922
2923   /* threaded loop over nodes */
2924   SculptThreadedTaskData data = {
2925       .sd = sd,
2926       .ob = ob,
2927       .brush = brush,
2928       .nodes = nodes,
2929   };
2930
2931   PBVHParallelSettings settings;
2932   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
2933   BKE_pbvh_parallel_range(0, totnode, &data, do_mask_brush_draw_task_cb_ex, &settings);
2934 }
2935
2936 static void do_mask_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2937 {
2938   SculptSession *ss = ob->sculpt;
2939   Brush *brush = BKE_paint_brush(&sd->paint);
2940
2941   switch ((BrushMaskTool)brush->mask_tool) {
2942     case BRUSH_MASK_DRAW:
2943       do_mask_brush_draw(sd, ob, nodes, totnode);
2944       break;
2945     case BRUSH_MASK_SMOOTH:
2946       smooth(sd, ob, nodes, totnode, ss->cache->bstrength, true);
2947       break;
2948   }
2949 }
2950
2951 static void do_draw_brush_task_cb_ex(void *__restrict userdata,
2952                                      const int n,
2953                                      const TaskParallelTLS *__restrict tls)
2954 {
2955   SculptThreadedTaskData *data = userdata;
2956   SculptSession *ss = data->ob->sculpt;
2957   const Brush *brush = data->brush;
2958   const float *offset = data->offset;
2959
2960   PBVHVertexIter vd;
2961   float(*proxy)[3];
2962
2963   proxy = BKE_pbvh_node_add_proxy(ss->pbvh, data->nodes[n])->co;
2964
2965   SculptBrushTest test;
2966   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
2967       ss, &test, data->brush->falloff_shape);
2968
2969   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
2970   {
2971     if (sculpt_brush_test_sq_fn(&test, vd.co)) {
2972       /* offset vertex */
2973       const float fade = tex_strength(ss,
2974                                       brush,
2975                                       vd.co,
2976                                       sqrtf(test.dist),
2977                                       vd.no,
2978                                       vd.fno,
2979                                       vd.mask ? *vd.mask : 0.0f,
2980                                       vd.index,
2981                                       tls->thread_id);
2982
2983       mul_v3_v3fl(proxy[vd.i], offset, fade);
2984
2985       if (vd.mvert) {
2986         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2987       }
2988     }
2989   }
2990   BKE_pbvh_vertex_iter_end;
2991 }
2992
2993 static void do_draw_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2994 {
2995   SculptSession *ss = ob->sculpt;
2996   Brush *brush = BKE_paint_brush(&sd->paint);
2997   float offset[3];
2998   const float bstrength = ss->cache->bstrength;
2999
3000   /* offset with as much as possible factored in already */
3001   mul_v3_v3fl(offset, ss->cache->sculpt_normal_symm, ss->cache->radius);
3002   mul_v3_v3(offset, ss->cache->scale);
3003   mul_v3_fl(offset, bstrength);
3004
3005   /* XXX - this shouldn't be necessary, but sculpting crashes in blender2.8 otherwise
3006    * initialize before threads so they can do curve mapping */
3007   BKE_curvemapping_initialize(brush->curve);
3008
3009   /* threaded loop over nodes */
3010   SculptThreadedTaskData data = {
3011       .sd = sd,
3012       .ob = ob,
3013       .brush = brush,
3014       .nodes = nodes,
3015       .offset = offset,
3016   };
3017
3018   PBVHParallelSettings settings;
3019   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
3020   BKE_pbvh_parallel_range(0, totnode, &data, do_draw_brush_task_cb_ex, &settings);
3021 }
3022
3023 static void do_draw_sharp_brush_task_cb_ex(void *__restrict userdata,
3024                                            const int n,
3025                                            const TaskParallelTLS *__restrict tls)
3026 {
3027   SculptThreadedTaskData *data = userdata;
3028   SculptSession *ss = data->ob->sculpt;
3029   const Brush *brush = data->brush;
3030   const float *offset = data->offset;
3031
3032   PBVHVertexIter vd;
3033   SculptOrigVertData orig_data;
3034   float(*proxy)[3];
3035
3036   sculpt_orig_vert_data_init(&orig_data, data->ob, data->nodes[n]);
3037
3038   proxy = BKE_pbvh_node_add_proxy(ss->pbvh, data->nodes[n])->co;
3039
3040   SculptBrushTest test;
3041   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
3042       ss, &test, data->brush->falloff_shape);
3043
3044   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
3045   {
3046     sculpt_orig_vert_data_update(&orig_data, &vd);
3047     if (sculpt_brush_test_sq_fn(&test, orig_data.co)) {
3048       /* offset vertex */
3049       const float fade = tex_strength(ss,
3050                                       brush,
3051                                       orig_data.co,
3052                                       sqrtf(test.dist),
3053                                       orig_data.no,
3054                                       NULL,
3055                                       vd.mask ? *vd.mask : 0.0f,
3056                                       vd.index,
3057                                       tls->thread_id);
3058
3059       mul_v3_v3fl(proxy[vd.i], offset, fade);
3060
3061       if (vd.mvert) {
3062         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
3063       }
3064     }
3065   }
3066   BKE_pbvh_vertex_iter_end;
3067 }
3068
3069 static void do_draw_sharp_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
3070 {
3071   SculptSession *ss = ob->sculpt;
3072   Brush *brush = BKE_paint_brush(&sd->paint);
3073   float offset[3];
3074   const float bstrength = ss->cache->bstrength;
3075
3076   /* offset with as much as possible factored in already */
3077   mul_v3_v3fl(offset, ss->cache->sculpt_normal_symm, ss->cache->radius);
3078   mul_v3_v3(offset, ss->cache->scale);
3079   mul_v3_fl(offset, bstrength);
3080
3081   /* XXX - this shouldn't be necessary, but sculpting crashes in blender2.8 otherwise
3082    * initialize before threads so they can do curve mapping */
3083   BKE_curvemapping_initialize(brush->curve);
3084
3085   /* threaded loop over nodes */
3086   SculptThreadedTaskData data = {
3087       .sd = sd,
3088       .ob = ob,
3089       .brush = brush,
3090       .nodes = nodes,
3091       .offset = offset,
3092   };
3093
3094   PBVHParallelSettings settings;
3095   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
3096   BKE_pbvh_parallel_range(0, totnode, &data, do_draw_sharp_brush_task_cb_ex, &settings);
3097 }
3098
3099 /**
3100  * Used for 'SCULPT_TOOL_CREASE' and 'SCULPT_TOOL_BLOB'
3101  */
3102 static void do_crease_brush_task_cb_ex(void *__restrict userdata,
3103                                        const int n,
3104                                        const TaskParallelTLS *__restrict tls)
3105 {
3106   SculptThreadedTaskData *data = userdata;
3107   SculptSession *ss = data->ob->sculpt;
3108   const Brush *brush = data->brush;
3109   SculptProjectVector *spvc = data->spvc;
3110   const float flippedbstrength = data->flippedbstrength;
3111   const float *offset = data->offset;
3112
3113   PBVHVertexIter vd;
3114   float(*proxy)[3];
3115
3116   proxy = BKE_pbvh_node_add_proxy(ss->pbvh, data->nodes[n])->co;
3117
3118   SculptBrushTest test;
3119   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
3120       ss, &test, data->brush->falloff_shape);
3121
3122   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
3123   {
3124     if (sculpt_brush_test_sq_fn(&test, vd.co)) {
3125       /* offset vertex */
3126       const float fade = tex_strength(ss,
3127                                       brush,
3128                                       vd.co,
3129                                       sqrtf(test.dist),
3130                                       vd.no,
3131                                       vd.fno,
3132                                       vd.mask ? *vd.mask : 0.0f,
3133                                       vd.index,
3134                                       tls->thread_id);
3135       float val1[3];
3136       float val2[3];
3137
3138       /* first we pinch */
3139       sub_v3_v3v3(val1, test.location, vd.co);
3140       if (brush->falloff_shape == PAINT_FALLOFF_SHAPE_TUBE) {
3141         project_plane_v3_v3v3(val1, val1, ss->cache->view_normal);
3142       }
3143
3144       mul_v3_fl(val1, fade * flippedbstrength);
3145
3146       sculpt_project_v3(spvc, val1, val1);
3147
3148       /* then we draw */
3149       mul_v3_v3fl(val2, offset, fade);
3150
3151       add_v3_v3v3(proxy[vd.i], val1, val2);
3152
3153       if (vd.mvert) {
3154         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
3155       }
3156     }
3157   }
3158   BKE_pbvh_vertex_iter_end;
3159 }
3160
3161 static void do_crease_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
3162 {
3163   SculptSession *ss = ob->sculpt;
3164   const Scene *scene = ss->cache->vc->scene;
3165   Brush *brush = BKE_paint_brush(&sd->paint);
3166   float offset[3];
3167   float bstrength = ss->cache->bstrength;
3168   float flippedbstrength, crease_correction;
3169   float brush_alpha;
3170
3171   SculptProjectVector spvc;
3172
3173   /* offset with as much as possible factored in already */
3174   mul_v3_v3fl(offset, ss->cache->sculpt_normal_symm, ss->cache->radius);
3175   mul_v3_v3(offset, ss->cache->scale);
3176   mul_v3_fl(offset, bstrength);
3177
3178   /* We divide out the squared alpha and multiply by the squared crease
3179    * to give us the pinch strength. */
3180   crease_correction = brush->crease_pinch_factor * brush->crease_pinch_factor;
3181   brush_alpha = BKE_brush_alpha_get(scene, brush);
3182   if (brush_alpha > 0.0f) {
3183     crease_correction /= brush_alpha * brush_alpha;
3184   }
3185
3186   /* we always want crease to pinch or blob to relax even when draw is negative */
3187   flippedbstrength = (bstrength < 0) ? -crease_correction * bstrength :
3188                                        crease_correction * bstrength;
3189
3190   if (brush->sculpt_tool == SCULPT_TOOL_BLOB) {
3191     flippedbstrength *= -1.0f;
3192   }
3193
3194   /* Use surface normal for 'spvc',
3195    * so the vertices are pinched towards a line instead of a single point.
3196    * Without this we get a 'flat' surface surrounding the pinch */
3197   sculpt_project_v3_cache_init(&spvc, ss->cache->sculpt_normal_symm);
3198
3199   /* threaded loop over nodes */
3200   SculptThreadedTaskData data = {
3201       .sd = sd,
3202       .ob = ob,
3203       .brush = brush,
3204       .nodes = nodes,
3205       .spvc = &spvc,
3206       .offset = offset,
3207       .flippedbstrength = flippedbstrength,
3208   };
3209
3210   PBVHParallelSettings settings;
3211   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
3212   BKE_pbvh_parallel_range(0, totnode, &data, do_crease_brush_task_cb_ex, &settings);
3213 }
3214
3215 static void do_pinch_brush_task_cb_ex(void *__restrict userdata,
3216                                       const int n,
3217                                       const TaskParallelTLS *__restrict tls)
3218 {
3219   SculptThreadedTaskData *data = userdata;
3220   SculptSession *ss = data->ob->sculpt;
3221   const Brush *brush = data->brush;
3222
3223   PBVHVertexIter vd;
3224   float(*proxy)[3];
3225   const float bstrength = ss->cache->bstrength;
3226
3227   proxy = BKE_pbvh_node_add_proxy(ss->pbvh, data->nodes[n])->co;
3228
3229   SculptBrushTest test;
3230   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
3231       ss, &test, data->brush->falloff_shape);
3232
3233   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
3234   {
3235     if (sculpt_brush_test_sq_fn(&test, vd.co)) {
3236       const float fade = bstrength * tex_strength(ss,
3237                                                   brush,
3238                                                   vd.co,
3239                                                   sqrtf(test.dist),
3240                                                   vd.no,
3241                                                   vd.fno,
3242                                                   vd.mask ? *vd.mask : 0.0f,
3243                                                   vd.index,
3244                                                   tls->thread_id);
3245       float val[3];
3246
3247       sub_v3_v3v3(val, test.location, vd.co);
3248       if (brush->falloff_shape == PAINT_FALLOFF_SHAPE_TUBE) {
3249         project_plane_v3_v3v3(val, val, ss->cache->view_normal);
3250       }
3251       mul_v3_v3fl(proxy[vd.i], val, fade);
3252
3253       if (vd.mvert) {
3254         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
3255       }
3256     }
3257   }
3258   BKE_pbvh_vertex_iter_end;
3259 }
3260
3261 static void do_pinch_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
3262 {
3263   Brush *brush = BKE_paint_brush(&sd->paint);
3264
3265   SculptThreadedTaskData data = {
3266       .sd = sd,
3267       .ob = ob,
3268       .brush = brush,
3269       .nodes = nodes,
3270   };
3271
3272   PBVHParallelSettings settings;
3273   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
3274   BKE_pbvh_parallel_range(0, totnode, &data, do_pinch_brush_task_cb_ex, &settings);
3275 }
3276
3277 static void do_grab_brush_task_cb_ex(void *__restrict userdata,
3278                                      const int n,
3279                                      const TaskParallelTLS *__restrict tls)
3280 {
3281   SculptThreadedTaskData *data = userdata;
3282   SculptSession *ss = data->ob->sculpt;
3283   const Brush *brush = data->brush;
3284   const float *grab_delta = data->grab_delta;
3285
3286   PBVHVertexIter vd;
3287   SculptOrigVertData orig_data;
3288   float(*proxy)[3];
3289   const float bstrength = ss->cache->bstrength;
3290
3291   sculpt_orig_vert_data_init(&orig_data, data->ob, data->nodes[n]);
3292
3293   proxy = BKE_pbvh_node_add_proxy(ss->pbvh, data->nodes[n])->co;
3294
3295   SculptBrushTest test;
3296   SculptBrushTestFn sculpt_brush_test_sq_fn = sculpt_brush_test_init_with_falloff_shape(
3297       ss, &test, data->brush->falloff_shape);
3298
3299   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
3300   {
3301     sculpt_orig_vert_data_update(&orig_data, &vd);
3302
3303     if (sculpt_brush_test_sq_fn(&test, orig_data.co)) {
3304       const float fade = bstrength * tex_strength(ss,
3305                                                   brush,
3306                                                   orig_data.co,
3307                                                   sqrtf(test.dist),
3308                                                   orig_data.no,
3309                                                   NULL,
3310                                                   vd.mask ? *vd.mask : 0.0f,
3311                                                   vd.index,
3312                                                   tls->thread_id);
3313
3314       mul_v3_v3fl(proxy[vd.i], grab_delta, fade);
3315
3316       if (vd.mvert) {
3317         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
3318       }
3319     }
3320   }
3321   BKE_pbvh_vertex_iter_end;
3322 }
3323
3324 static void do_grab_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
3325 {
3326   SculptSession *ss = ob->sculpt;
3327   Brush *brush = BKE_paint_brush(&sd->paint);
3328   float grab_delta[3];
3329
3330   copy_v3_v3(grab_delta, ss->cache->grab_delta_symmetry);
3331
3332   if (ss->cache->normal_weight > 0.0f) {
3333     sculpt_project_v3_normal_align(ss, ss->cache->normal_weight, grab_delta);
3334   }
3335
3336   SculptThreadedTaskData data = {
3337       .sd = sd,
3338       .ob = ob,
3339       .brush = brush,
3340       .nodes = nodes,
3341       .grab_delta = grab_delta,
3342   };
3343
3344   PBVHParallelSettings settings;
3345   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
3346   BKE_pbvh_parallel_range(0, totnode, &data, do_grab_brush_task_cb_ex, &settings);
3347 }
3348
3349 /* Regularized Kelvinlets: Sculpting Brushes based on Fundamental Solutions of Elasticity
3350  * Pixar Technical Memo #17-03 */
3351
3352 typedef struct KelvinletParams {
3353   float f;
3354   float a;
3355   float b;
3356   float c;
3357   float radius_scaled;
3358 } KelvinletParams;
3359
3360 static int sculpt_kelvinlet_get_scale_iteration_count(eBrushElasticDeformType type)
3361 {
3362   if (type == BRUSH_ELASTIC_DEFORM_GRAB) {
3363     return 1;
3364   }
3365   if (type == BRUSH_ELASTIC_DEFORM_GRAB_BISCALE) {
3366     return 2;
3367   }
3368   if (type == BRUSH_ELASTIC_DEFORM_GRAB_TRISCALE) {
3369     return 3;
3370   }
3371   return 0;
3372 }
3373
3374 static void sculpt_kelvinet_integrate(void (*kelvinlet)(float disp[3],
3375                                                         const float vertex_co[3],
3376                                                         const float location[3],
3377                                                         float normal[3],
3378                                                         KelvinletParams *p),
3379                                       float r_disp[3],
3380                                       const float vertex_co[3],
3381                                       const float location[3],
3382                                       float normal[3],
3383                                       KelvinletParams *p)
3384 {
3385   float k[4][3], k_it[4][3];
3386   kelvinlet(k[0], vertex_co, location, normal, p);
3387   copy_v3_v3(k_it[0], k[0]);
3388   mul_v3_fl(k_it[0], 0.5f);
3389   add_v3_v3v3(k_it[0], vertex_co, k_it[0]);
3390   kelvinlet(k[1], k_it[0], location, normal, p);
3391   copy_v3_v3(k_it[1], k[1]);
3392   mul_v3_fl(k_it[1], 0.5f);
3393   add_v3_v3v3(k_it[1], vertex_co, k_it[1]);
3394   kelvinlet(k[2], k_it[1], location, normal, p);
3395   copy_v3_v3(k_it[2], k[2]);
3396   add_v3_v3v3(k_it[2], vertex_co, k_it[2]);
3397   sub_v3_v3v3(k_it[2], k_it[2], location);
3398   kelvinlet(k[3], k_it[2], location, normal, p);
3399   copy_v3_v3(r_disp, k[0]);
3400   madd_v3_v3fl(r_disp, k[1], 2);
3401   madd_v3_v3fl(r_disp, k[2], 2);
3402   add_v3_v3(r_disp, k[3]);
3403   mul_v3_fl(r_disp, 1.0f / 6.0f);
3404 }
3405
3406 /* Regularized Kelvinlets: Formula (16) */
3407 static void sculpt_kelvinlet_scale(float disp[3],
3408                                    const float vertex_co[3],
3409                                    const float location[3],
3410                                    float UNUSED(normal[3]),
3411                                    KelvinletParams *p)
3412 {
3413   float r_v[3];
3414   sub_v3_v3v3(r_v, vertex_co, location);
3415   float r = len_v3(r_v);
3416   float r_e = sqrtf(r * r + p->radius_scaled * p->radius_scaled);
3417   float u = (2.0f * p->b - p->a) * ((1.0f / (r_e * r_e * r_e))) +
3418             ((3.0f * p->radius_scaled * p->radius_scaled) / (2.0f * r_e * r_e * r_e * r_e * r_e));
3419   float fade = u * p->c;
3420   mul_v3_v3fl(disp, r_v, fade * p->f);
3421 }
3422
3423 /* Regularized Kelvinlets: Formula (15) */
3424 static void sculpt_kelvinlet_twist(float disp[3],
3425                                    const float vertex_co[3],
3426                                    const float location[3],
3427                                    float normal[3],
3428                                    KelvinletParams *p)
3429 {
3430   float r_v[3], q_r[3];
3431   sub_v3_v3v3(r_v, vertex_co, location);
3432   float r = len_v3(r_v);
3433   float r_e = sqrtf(r * r + p->radius_scaled * p->radius_scaled);
3434   float u = -p->a * ((1.0f / (r_e * r_e * r_e))) +
3435             ((3.0f * p->radius_scaled * p->radius_scaled) / (2.0f * r_e * r_e * r_e * r_e * r_e));
3436   float fade = u * p->c;
3437   cross_v3_v3v3(q_r, normal, r_v);
3438   mul_v3_v3fl(disp, q_r, fade * p->f);
3439 }
3440
3441 static void do_elastic_deform_brush_task_cb_ex(void *__restrict userdata,
3442                                                const int n,
3443                                                const TaskParallelTLS *__restrict UNUSED(tls))
3444 {
3445   SculptThreadedTaskData *data = userdata;
3446   SculptSession *ss = data->ob->sculpt;
3447   const Brush *brush = data->brush;
3448   const float *grab_delta = data->grab_delta;
3449   const float *location = ss->cache->location;
3450
3451   PBVHVertexIter vd;
3452   SculptOrigVertData orig_data;
3453   float(*proxy)[3];
3454
3455   const float bstrength = ss->cache->bstrength;
3456
3457   sculpt_orig_vert_data_init(&orig_data, data->ob, data->nodes[n]);
3458
3459   proxy = BKE_pbvh_node_add_proxy(ss->pbvh, data->nodes[n])->co;
3460
3461   /* Maybe this can be exposed to the user */
3462   float radius_e[3] = {1.0f, 2.0f, 2.0f};
3463   float r_e[3];
3464   float kvl[3];
3465   float radius_scaled[3];
3466
3467   radius_scaled[0] = ss->cache->radius * radius_e[0];
3468   radius_scaled[1] = radius_scaled[0] * radius_e[1];
3469   radius_scaled[2] = radius_scaled[1] * radius_e[2];
3470
3471   float shear_modulus = 1.0f;
3472   float poisson_ratio = brush->elastic_deform_volume_preservation;
3473
3474   float a = 1.0f / (4.0f * (float)M_PI * shear_modulus);
3475   float b = a / (4.0f * (1.0f - poisson_ratio));
3476   float c = 2 * (3.0f * a - 2.0f * b);
3477
3478   float dir;
3479   if (ss->cache->mouse[0] > ss->cache->initial_mouse[0]) {
3480     dir = 1.0f;
3481   }
3482   else {
3483     dir = -1.0f;
3484   }
3485
3486   if (brush->elastic_deform_type == BRUSH_ELASTIC_DEFORM_TWIST) {
3487     int symm = ss->cache->mirror_symmetry_pass;
3488     if (symm == 1 || symm == 2 || symm == 4 || symm == 7) {
3489       dir = -dir;
3490     }
3491   }
3492   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
3493   {
3494     sculpt_orig_vert_data_update(&orig_data, &vd);
3495     float fade, final_disp[3], weights[3];
3496     float r = len_v3v3(location, orig_data.co);
3497     KelvinletParams params;
3498     params.a = a;
3499     params.b = b;
3500     params.c = c;
3501     params.radius_scaled = radius_scaled[0];
3502
3503     int multi_scale_it = sculpt_kelvinlet_get_scale_iteration_count(brush->elastic_deform_type);
3504     for (int it = 0; it < max_ii(1, multi_scale_it); it++) {
3505       r_e[it] = sqrtf(r * r + radius_scaled[it] * radius_scaled[it]);
3506     }
3507
3508     /* Regularized Kelvinlets: Formula (6) */
3509     for (int s_it = 0; s_it < multi_scale_it; s_it++) {
3510       kvl[s_it] = ((a - b) / r_e[s_it]) + ((b * r * r) / (r_e[s_it] * r_e[s_it] * r_e[s_it])) +
3511                   ((a * radius_scaled[s_it] * radius_scaled[s_it]) /
3512                    (2.0f * r_e[s_it] * r_e[s_it] * r_e[s_it]));
3513     }
3514
3515     switch (brush->elastic_deform_type) {
3516       /* Regularized Kelvinlets: Multi-scale extrapolation. Formula (11) */
3517       case BRUSH_ELASTIC_DEFORM_GRAB:
3518         fade = kvl[0] * c;
3519         mul_v3_v3fl(final_disp, grab_delta, fade * bstrength * 20.f);
3520         break;
3521       case BRUSH_ELASTIC_DEFORM_GRAB_BISCALE: {
3522         const float u = kvl[0] - kvl[1];
3523         fade = u * c / ((1.0f / radius_scaled[0]) - (1.0f / radius_scaled[1]));
3524         mul_v3_v3fl(final_disp, grab_delta, fade * bstrength * 20.0f);
3525         break;
3526       }
3527       case BRUSH_ELASTIC_DEFORM_GRAB_TRISCALE: {
3528         weights[0] = 1.0f;
3529         weights[1] = -(
3530             (radius_scaled[2] * radius_scaled[2] - radius_scaled[0] * radius_scaled[0]) /
3531             (radius_scaled[2] * radius_scaled[2] - radius_scaled[1] * radius_scaled[1]));
3532         weights[2] = ((radius_scaled[1] * radius_scaled[1] - radius_scaled[0] * radius_scaled[0]) /
3533                       (radius_scaled[2] * radius_scaled[2] - radius_scaled[1] * radius_scaled[1]));
3534
3535         const float u = weights[0] * kvl[0] + weights[1] * kvl[1] + weights[2] * kvl[2];
3536         fade = u * c /
3537                (weights[0] / radius_scaled[0] + weights[1] / radius_scaled[1] +
3538                 weights[2] / radius_scaled[2]);
3539         mul_v3_v3fl(final_disp, grab_delta, fade * bstrength * 20.0f);
3540         break;
3541       }
3542       case BRUSH_ELASTIC_DEFORM_SCALE:
3543         params.f = len_v3(grab_delta) * dir * bstrength;
3544         sculpt_kelvinet_integrate(sculpt_kelvinlet_scale,
3545                                   final_disp,
3546                                   orig_data.co,
3547                                   location,
3548                                   ss->cache->sculpt_normal_symm,
3549                                   &params);
3550         break;
3551       case BRUSH_ELASTIC_DEFORM_TWIST:
3552         params.f = len_v3(grab_delta) * dir * bstrength;
3553         sculpt_kelvinet_integrate(sculpt_kelvinlet_twist,
3554                                   final_disp,
3555                                   orig_data.co,
3556                                   location,
3557                                   ss->cache->sculpt_normal_symm,
3558                                   &params);
3559         break;
3560     }
3561
3562     if (vd.mask) {
3563       mul_v3_fl(final_disp, 1.0f - *vd.mask);
3564     }
3565
3566     mul_v3_fl(final_disp, sculpt_automasking_factor_get(ss, vd.index));
3567
3568     copy_v3_v3(proxy[vd.i], final_disp);
3569
3570     if (vd.mvert) {
3571       vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
3572     }
3573   }
3574   BKE_pbvh_vertex_iter_end;
3575 }
3576
3577 static void do_elastic_deform_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
3578 {
3579   SculptSession *ss = ob->sculpt;
3580   Brush *brush = BKE_paint_brush(&sd->paint);
3581   float grab_delta[3];
3582
3583   copy_v3_v3(grab_delta, ss->cache->grab_delta_symmetry);
3584
3585   if (ss->cache->normal_weight > 0.0f) {
3586     sculpt_project_v3_normal_align(ss, ss->cache->normal_weight, grab_delta);
3587   }
3588
3589   SculptThreadedTaskData data = {
3590       .sd = sd,
3591       .ob = ob,
3592       .brush = brush,
3593       .nodes = nodes,
3594       .grab_delta = grab_delta,
3595   };
3596
3597   PBVHParallelSettings settings;
3598   BKE_pbvh_parallel_range_settings(&settings, (sd->flags & SCULPT_USE_OPENMP), totnode);
3599   BKE_pbvh_parallel_range(0, totnode, &data, do_elastic_deform_brush_task_cb_ex, &settings);
3600 }
3601
3602 static void do_pose_brush_task_cb_ex(void *__restrict userdata,
3603                                      const int n,
3604                                      const TaskParallelTLS *__restrict UNUSED(tls))
3605 {
3606   SculptThreadedTaskData *data = userdata;
3607   SculptSession *ss = data->ob->sculpt;
3608
3609   PBVHVertexIter vd;
3610   float disp[3], val[3];
3611   float final_pos[3];
3612
3613   SculptOrigVertData orig_data;
3614   sculpt_orig_vert_data_init(&orig_data, data->ob, data->nodes[n]);
3615
3616   BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
3617   {
3618
3619     sculpt_orig_vert_data_update(&orig_data, &vd);
3620     if (check_vertex_pivot_symmetry(
3621             orig_data.co, data->pose_initial_co, ss->cache->mirror_symmetry_pass)) {
3622       copy_v3_v3(val, orig_data.co);
3623       mul_m4_v3(data->transform_trans_inv, val);
3624       mul_m4_v3(data->transform_rot, val);
3625       mul_m4_v3(data->transform_trans, val);
3626       sub_v3_v3v3(disp, val, orig_data.co);
3627
3628       mul_v3_fl(disp, ss->cache->pose_factor[vd.index]);
3629       float mask = vd.mask ? *vd.mask : 0.0f;
3630       mul_v3_fl(disp, 1.0f - mask);
3631       add_v3_v3v3(final_pos, orig_data.co, disp);
3632       copy_v3_v3(vd.co, final_pos);
3633
3634       if (vd.mvert) {
3635         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
3636       }
3637     }
3638   }
3639   BKE_pbvh_vertex_iter_end;
3640 }
3641
3642 static void do_pose_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
3643 {
3644   SculptSession *ss = ob->sculpt;
3645   Brush *brush = BKE_paint_brush(&sd->paint);
3646   float grab_delta[3], rot_quat[4], initial_v[3], current_v[3], temp[3];
3647   float pose_origin[3];
3648   float pose_initial_co[3];
3649   float transform_rot[4][4], transform_trans[4][4], transform_trans_inv[4][4];
3650
3651   copy_v3_v3(grab_delta, ss->cache->grab_delta_symmetry);
3652