Fix: solved BGE compiler error on Linux/gcc
[blender.git] / source / blender / editors / sculpt_paint / sculpt.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2006 by Nicholas Bishop
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Jason Wilkins, Tom Musgrove.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  *
27  * Implements the Sculpt Mode tools
28  *
29  */
30
31 /** \file blender/editors/sculpt_paint/sculpt.c
32  *  \ingroup edsculpt
33  */
34
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_math.h"
39 #include "BLI_blenlib.h"
40 #include "BLI_dial.h"
41 #include "BLI_utildefines.h"
42 #include "BLI_ghash.h"
43
44 #include "BLF_translation.h"
45
46 #include "DNA_customdata_types.h"
47 #include "DNA_mesh_types.h"
48 #include "DNA_meshdata_types.h"
49 #include "DNA_node_types.h"
50 #include "DNA_object_types.h"
51 #include "DNA_scene_types.h"
52 #include "DNA_brush_types.h"
53
54 #include "BKE_pbvh.h"
55 #include "BKE_brush.h"
56 #include "BKE_ccg.h"
57 #include "BKE_context.h"
58 #include "BKE_depsgraph.h"
59 #include "BKE_global.h"
60 #include "BKE_image.h"
61 #include "BKE_key.h"
62 #include "BKE_library.h"
63 #include "BKE_mesh.h"
64 #include "BKE_mesh_mapping.h"
65 #include "BKE_modifier.h"
66 #include "BKE_multires.h"
67 #include "BKE_paint.h"
68 #include "BKE_report.h"
69 #include "BKE_node.h"
70 #include "BKE_object.h"
71 #include "BKE_subsurf.h"
72 #include "BKE_colortools.h"
73
74 #include "WM_api.h"
75 #include "WM_types.h"
76
77 #include "ED_sculpt.h"
78 #include "ED_object.h"
79 #include "ED_screen.h"
80 #include "ED_view3d.h"
81 #include "paint_intern.h"
82 #include "sculpt_intern.h"
83
84 #include "RNA_access.h"
85 #include "RNA_define.h"
86
87 #include "GPU_buffers.h"
88 #include "GPU_extensions.h"
89
90 #include "UI_interface.h"
91 #include "UI_resources.h"
92
93 #include "bmesh.h"
94 #include "bmesh_tools.h"
95
96 #include <math.h>
97 #include <stdlib.h>
98 #include <string.h>
99
100 #ifdef _OPENMP
101 #include <omp.h>
102 #endif
103
104 #if defined(__APPLE__) && defined _OPENMP
105 #include <sys/sysctl.h>
106
107 #include "BLI_threads.h"
108
109 /* Query how many cores not counting HT aka physical cores we've got. */
110 static int system_physical_thread_count(void)
111 {
112         int pcount;
113         size_t pcount_len = sizeof(pcount);
114         sysctlbyname("hw.physicalcpu", &pcount, &pcount_len, NULL, 0);
115         return pcount;
116 }
117 #endif  /* __APPLE__ */
118
119 /* Check if there are any active modifiers in stack (used for flushing updates at enter/exit sculpt mode) */
120 static bool sculpt_has_active_modifiers(Scene *scene, Object *ob)
121 {
122         ModifierData *md;
123         VirtualModifierData virtualModifierData;
124
125         md = modifiers_getVirtualModifierList(ob, &virtualModifierData);
126
127         /* exception for shape keys because we can edit those */
128         for (; md; md = md->next) {
129                 if (modifier_isEnabled(scene, md, eModifierMode_Realtime))
130                         return 1;
131         }
132
133         return 0;
134 }
135
136
137
138 typedef enum StrokeFlags {
139         CLIP_X = 1,
140         CLIP_Y = 2,
141         CLIP_Z = 4
142 } StrokeFlags;
143
144 /* Cache stroke properties. Used because
145  * RNA property lookup isn't particularly fast.
146  *
147  * For descriptions of these settings, check the operator properties.
148  */
149 typedef struct StrokeCache {
150         /* Invariants */
151         float initial_radius;
152         float scale[3];
153         int flag;
154         float clip_tolerance[3];
155         float initial_mouse[2];
156
157         /* Pre-allocated temporary storage used during smoothing */
158         int num_threads, init_num_threads;
159         float (**tmpgrid_co)[3], (**tmprow_co)[3];
160         float **tmpgrid_mask, **tmprow_mask;
161
162         /* Variants */
163         float radius;
164         float radius_squared;
165         float true_location[3];
166         float location[3];
167
168         bool pen_flip;
169         bool invert;
170         float pressure;
171         float mouse[2];
172         float bstrength;
173
174         /* The rest is temporary storage that isn't saved as a property */
175
176         bool first_time; /* Beginning of stroke may do some things special */
177
178         /* from ED_view3d_ob_project_mat_get() */
179         float projection_mat[4][4];
180
181         /* Clean this up! */
182         ViewContext *vc;
183         Brush *brush;
184
185         float special_rotation;
186         float grab_delta[3], grab_delta_symmetry[3];
187         float old_grab_location[3], orig_grab_location[3];
188
189         int symmetry; /* Symmetry index between 0 and 7 bit combo 0 is Brush only;
190                        * 1 is X mirror; 2 is Y mirror; 3 is XY; 4 is Z; 5 is XZ; 6 is YZ; 7 is XYZ */
191         int mirror_symmetry_pass; /* the symmetry pass we are currently on between 0 and 7*/
192         float true_view_normal[3];
193         float view_normal[3];
194
195         /* sculpt_normal gets calculated by calc_sculpt_normal(), then the
196          * sculpt_normal_symm gets updated quickly with the usual symmetry
197          * transforms */
198         float sculpt_normal[3];
199         float sculpt_normal_symm[3];
200
201         /* Used for area texture mode, local_mat gets calculated by
202          * calc_brush_local_mat() and used in tex_strength(). */
203         float brush_local_mat[4][4];
204         
205         float last_center[3];
206         int radial_symmetry_pass;
207         float symm_rot_mat[4][4];
208         float symm_rot_mat_inv[4][4];
209         bool original;
210         float anchored_location[3];
211
212         float vertex_rotation; /* amount to rotate the vertices when using rotate brush */
213         Dial *dial;
214         
215         char saved_active_brush_name[MAX_ID_NAME];
216         char saved_mask_brush_tool;
217         int saved_smooth_size; /* smooth tool copies the size of the current tool */
218         bool alt_smooth;
219
220         float plane_trim_squared;
221
222         bool supports_gravity;
223         float true_gravity_direction[3];
224         float gravity_direction[3];
225
226         rcti previous_r; /* previous redraw rectangle */
227         rcti current_r; /* current redraw rectangle */
228 } StrokeCache;
229
230 /************** Access to original unmodified vertex data *************/
231
232 typedef struct {
233         BMLog *bm_log;
234
235         SculptUndoNode *unode;
236         float (*coords)[3];
237         short (*normals)[3];
238         const float *vmasks;
239
240         /* Original coordinate, normal, and mask */
241         const float *co;
242         const short *no;
243         float mask;
244 } SculptOrigVertData;
245
246
247 /* Initialize a SculptOrigVertData for accessing original vertex data;
248  * handles BMesh, mesh, and multires */
249 static void sculpt_orig_vert_data_unode_init(SculptOrigVertData *data,
250                                              Object *ob,
251                                              SculptUndoNode *unode)
252 {
253         SculptSession *ss = ob->sculpt;
254         BMesh *bm = ss->bm;
255
256         memset(data, 0, sizeof(*data));
257         data->unode = unode;
258
259         if (bm) {
260                 data->bm_log = ss->bm_log;
261         }
262         else {
263                 data->coords = data->unode->co;
264                 data->normals = data->unode->no;
265                 data->vmasks = data->unode->mask;
266         }
267 }
268
269 /* Initialize a SculptOrigVertData for accessing original vertex data;
270  * handles BMesh, mesh, and multires */
271 static void sculpt_orig_vert_data_init(SculptOrigVertData *data,
272                                        Object *ob,
273                                        PBVHNode *node)
274 {
275         SculptUndoNode *unode;
276         unode = sculpt_undo_push_node(ob, node, SCULPT_UNDO_COORDS);
277         sculpt_orig_vert_data_unode_init(data, ob, unode);
278 }
279
280 /* Update a SculptOrigVertData for a particular vertex from the PBVH
281  * iterator */
282 static void sculpt_orig_vert_data_update(SculptOrigVertData *orig_data,
283                                          PBVHVertexIter *iter)
284 {
285         if (orig_data->unode->type == SCULPT_UNDO_COORDS) {
286                 if (orig_data->bm_log) {
287                         BM_log_original_vert_data(
288                                 orig_data->bm_log, iter->bm_vert,
289                                 &orig_data->co, &orig_data->no);
290                 }
291                 else {
292                         orig_data->co = orig_data->coords[iter->i];
293                         orig_data->no = orig_data->normals[iter->i];
294                 }
295         }
296         else if (orig_data->unode->type == SCULPT_UNDO_MASK) {
297                 if (orig_data->bm_log) {
298                         orig_data->mask = BM_log_original_mask(orig_data->bm_log, iter->bm_vert);
299                 }
300                 else {
301                         orig_data->mask = orig_data->vmasks[iter->i];
302                 }
303         }
304 }
305
306 /** \name SculptProjectVector
307  *
308  * Fast-path for #project_plane_v3_v3v3
309  *
310  * \{ */
311
312 typedef struct SculptProjectVector {
313         float plane[3];
314         float len_sq;
315         float len_sq_inv_neg;
316         bool  is_valid;
317
318 } SculptProjectVector;
319
320 /**
321  * \param plane  Direction, can be any length.
322  */
323 static void sculpt_project_v3_cache_init(
324         SculptProjectVector *spvc, const float plane[3])
325 {
326         copy_v3_v3(spvc->plane, plane);
327         spvc->len_sq = len_squared_v3(spvc->plane);
328         spvc->is_valid = (spvc->len_sq > FLT_EPSILON);
329         spvc->len_sq_inv_neg = (spvc->is_valid) ? -1.0f / spvc->len_sq : 0.0f;
330 }
331
332 static void sculpt_project_v3(
333         const SculptProjectVector *spvc, const float vec[3],
334         float r_vec[3])
335 {
336 #if 0
337         project_plane_v3_v3v3(r_vec, vec, spvc->plane);
338 #else
339         /* inline the projection, cache `-1.0 / dot_v3_v3(v_proj, v_proj)` */
340         madd_v3_v3fl(r_vec, spvc->plane, dot_v3v3(vec, spvc->plane) * spvc->len_sq_inv_neg);
341 #endif
342 }
343
344 /** \} */
345
346
347 /**********************************************************************/
348
349 /* Returns true if the stroke will use dynamic topology, false
350  * otherwise.
351  *
352  * Factors: some brushes like grab cannot do dynamic topology.
353  * Others, like smooth, are better without. Same goes for alt-
354  * key smoothing. */
355 static int sculpt_stroke_dynamic_topology(const SculptSession *ss,
356                                           const Brush *brush)
357 {
358         return ((BKE_pbvh_type(ss->pbvh) == PBVH_BMESH) &&
359
360                 (!ss->cache || (!ss->cache->alt_smooth)) &&
361
362                 /* Requires mesh restore, which doesn't work with
363                  * dynamic-topology */
364                 !(brush->flag & BRUSH_ANCHORED) &&
365                 !(brush->flag & BRUSH_DRAG_DOT) &&
366
367                 (!ELEM(brush->sculpt_tool,
368                        /* These brushes, as currently coded, cannot
369                         * support dynamic topology */
370                        SCULPT_TOOL_GRAB,
371                        SCULPT_TOOL_ROTATE,
372                        SCULPT_TOOL_THUMB,
373                        SCULPT_TOOL_LAYER,
374
375                        /* These brushes could handle dynamic topology,
376                         * but user feedback indicates it's better not
377                         * to */
378                        SCULPT_TOOL_SMOOTH,
379                        SCULPT_TOOL_MASK)));
380 }
381
382 /*** paint mesh ***/
383
384 static void paint_mesh_restore_co(Sculpt *sd, Object *ob)
385 {
386         SculptSession *ss = ob->sculpt;
387         const Brush *brush = BKE_paint_brush(&sd->paint);
388
389         PBVHNode **nodes;
390         int n, totnode;
391
392         BKE_pbvh_search_gather(ss->pbvh, NULL, NULL, &nodes, &totnode);
393
394         /* Disable OpenMP when dynamic-topology is enabled. Otherwise, new
395          * entries might be inserted by sculpt_undo_push_node() into the
396          * GHash used internally by BM_log_original_vert_co() by a
397          * different thread. [#33787] */
398 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && !ss->bm && totnode > SCULPT_OMP_LIMIT)
399         for (n = 0; n < totnode; n++) {
400                 SculptUndoNode *unode;
401                 SculptUndoType type = (brush->sculpt_tool == SCULPT_TOOL_MASK ?
402                                        SCULPT_UNDO_MASK : SCULPT_UNDO_COORDS);
403
404                 if (ss->bm) {
405                         unode = sculpt_undo_push_node(ob, nodes[n], type);
406                 }
407                 else {
408                         unode = sculpt_undo_get_node(nodes[n]);
409                 }
410                 if (unode) {
411                         PBVHVertexIter vd;
412                         SculptOrigVertData orig_data;
413
414                         sculpt_orig_vert_data_unode_init(&orig_data, ob, unode);
415                 
416                         BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
417                         {
418                                 sculpt_orig_vert_data_update(&orig_data, &vd);
419
420                                 if (orig_data.unode->type == SCULPT_UNDO_COORDS) {
421                                         copy_v3_v3(vd.co, orig_data.co);
422                                         if (vd.no) copy_v3_v3_short(vd.no, orig_data.no);
423                                         else normal_short_to_float_v3(vd.fno, orig_data.no);
424                                 }
425                                 else if (orig_data.unode->type == SCULPT_UNDO_MASK) {
426                                         *vd.mask = orig_data.mask;
427                                 }
428                                 if (vd.mvert) vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
429                         }
430                         BKE_pbvh_vertex_iter_end;
431
432                         BKE_pbvh_node_mark_update(nodes[n]);
433                 }
434         }
435
436         if (nodes)
437                 MEM_freeN(nodes);
438 }
439
440 /*** BVH Tree ***/
441
442 static void sculpt_extend_redraw_rect_previous(Object *ob, rcti *rect)
443 {
444         /* expand redraw rect with redraw rect from previous step to
445          * prevent partial-redraw issues caused by fast strokes. This is
446          * needed here (not in sculpt_flush_update) as it was before
447          * because redraw rectangle should be the same in both of
448          * optimized PBVH draw function and 3d view redraw (if not -- some
449          * mesh parts could disappear from screen (sergey) */
450         SculptSession *ss = ob->sculpt;
451
452         if (ss->cache) {
453                 if (!BLI_rcti_is_empty(&ss->cache->previous_r))
454                         BLI_rcti_union(rect, &ss->cache->previous_r);
455         }
456 }
457
458 /* Get a screen-space rectangle of the modified area */
459 static bool sculpt_get_redraw_rect(ARegion *ar, RegionView3D *rv3d,
460                                    Object *ob, rcti *rect)
461 {
462         PBVH *pbvh = ob->sculpt->pbvh;
463         float bb_min[3], bb_max[3];
464
465         if (!pbvh)
466                 return 0;
467
468         BKE_pbvh_redraw_BB(pbvh, bb_min, bb_max);
469
470         /* convert 3D bounding box to screen space */
471         if (!paint_convert_bb_to_rect(rect,
472                                       bb_min,
473                                       bb_max,
474                                       ar,
475                                       rv3d,
476                                       ob))
477         {
478                 return 0;
479         }
480
481
482         return 1;
483 }
484
485 void ED_sculpt_redraw_planes_get(float planes[4][4], ARegion *ar,
486                                  RegionView3D *rv3d, Object *ob)
487 {
488         PBVH *pbvh = ob->sculpt->pbvh;
489         /* copy here, original will be used below */
490         rcti rect = ob->sculpt->cache->current_r;
491
492         sculpt_extend_redraw_rect_previous(ob, &rect);
493
494         paint_calc_redraw_planes(planes, ar, rv3d, ob, &rect);
495
496         /* we will draw this rect, so now we can set it as the previous partial rect.
497          * Note that we don't update with the union of previous/current (rect), only with
498          * the current. Thus we avoid the rectangle needlessly growing to include
499          * all the stroke area */
500         ob->sculpt->cache->previous_r = ob->sculpt->cache->current_r;
501
502         /* clear redraw flag from nodes */
503         if (pbvh)
504                 BKE_pbvh_update(pbvh, PBVH_UpdateRedraw, NULL);
505 }
506
507 /************************ Brush Testing *******************/
508
509 typedef struct SculptBrushTest {
510         float radius_squared;
511         float location[3];
512         float dist;
513
514         /* View3d clipping - only set rv3d for clipping */
515         RegionView3D *clip_rv3d;
516 } SculptBrushTest;
517
518 static void sculpt_brush_test_init(SculptSession *ss, SculptBrushTest *test)
519 {
520         RegionView3D *rv3d = ss->cache->vc->rv3d;
521
522         test->radius_squared = ss->cache->radius_squared;
523         copy_v3_v3(test->location, ss->cache->location);
524         test->dist = 0.0f;   /* just for initialize */
525
526
527         if (rv3d->rflag & RV3D_CLIPPING) {
528                 test->clip_rv3d = rv3d;
529         }
530         else {
531                 test->clip_rv3d = NULL;
532         }
533 }
534
535 BLI_INLINE bool sculpt_brush_test_clipping(const SculptBrushTest *test, const float co[3])
536 {
537         RegionView3D *rv3d = test->clip_rv3d;
538         return (rv3d && (ED_view3d_clipping_test(rv3d, co, true)));
539 }
540
541 static bool sculpt_brush_test(SculptBrushTest *test, const float co[3])
542 {
543         float distsq = len_squared_v3v3(co, test->location);
544
545         if (distsq <= test->radius_squared) {
546                 if (sculpt_brush_test_clipping(test, co)) {
547                         return 0;
548                 }
549                 test->dist = sqrtf(distsq);
550                 return 1;
551         }
552         else {
553                 return 0;
554         }
555 }
556
557 static bool sculpt_brush_test_sq(SculptBrushTest *test, const float co[3])
558 {
559         float distsq = len_squared_v3v3(co, test->location);
560
561         if (distsq <= test->radius_squared) {
562                 if (sculpt_brush_test_clipping(test, co)) {
563                         return 0;
564                 }
565                 test->dist = distsq;
566                 return 1;
567         }
568         else {
569                 return 0;
570         }
571 }
572
573 static bool sculpt_brush_test_fast(const SculptBrushTest *test, const float co[3])
574 {
575         if (sculpt_brush_test_clipping(test, co)) {
576                 return 0;
577         }
578         return len_squared_v3v3(co, test->location) <= test->radius_squared;
579 }
580
581 static bool sculpt_brush_test_cube(SculptBrushTest *test, const float co[3], float local[4][4])
582 {
583         float side = M_SQRT1_2;
584         float local_co[3];
585
586         if (sculpt_brush_test_clipping(test, co)) {
587                 return 0;
588         }
589
590         mul_v3_m4v3(local_co, local, co);
591
592         local_co[0] = fabsf(local_co[0]);
593         local_co[1] = fabsf(local_co[1]);
594         local_co[2] = fabsf(local_co[2]);
595
596         if (local_co[0] <= side && local_co[1] <= side && local_co[2] <= side) {
597                 float p = 4.0f;
598                 
599                 test->dist = ((powf(local_co[0], p) +
600                                powf(local_co[1], p) +
601                                powf(local_co[2], p)) / powf(side, p));
602
603                 return 1;
604         }
605         else {
606                 return 0;
607         }
608 }
609
610 static float frontface(Brush *br, const float sculpt_normal[3],
611                        const short no[3], const float fno[3])
612 {
613         if (br->flag & BRUSH_FRONTFACE) {
614                 float dot;
615
616                 if (no) {
617                         float tmp[3];
618
619                         normal_short_to_float_v3(tmp, no);
620                         dot = dot_v3v3(tmp, sculpt_normal);
621                 }
622                 else {
623                         dot = dot_v3v3(fno, sculpt_normal);
624                 }
625                 return dot > 0 ? dot : 0;
626         }
627         else {
628                 return 1;
629         }
630 }
631
632 #if 0
633
634 static bool sculpt_brush_test_cyl(SculptBrushTest *test, float co[3], float location[3], const float area_no[3])
635 {
636         if (sculpt_brush_test_fast(test, co)) {
637                 float t1[3], t2[3], t3[3], dist;
638
639                 sub_v3_v3v3(t1, location, co);
640                 sub_v3_v3v3(t2, x2, location);
641
642                 cross_v3_v3v3(t3, area_no, t1);
643
644                 dist = len_v3(t3) / len_v3(t2);
645
646                 test->dist = dist;
647
648                 return 1;
649         }
650
651         return 0;
652 }
653
654 #endif
655
656 /* ===== Sculpting =====
657  *
658  */
659 static void flip_v3(float v[3], const char symm)
660 {
661         flip_v3_v3(v, v, symm);
662 }
663
664 static float calc_overlap(StrokeCache *cache, const char symm, const char axis, const float angle)
665 {
666         float mirror[3];
667         float distsq;
668         
669         /* flip_v3_v3(mirror, cache->traced_location, symm); */
670         flip_v3_v3(mirror, cache->true_location, symm);
671
672         if (axis != 0) {
673                 float mat[4][4];
674                 unit_m4(mat);
675                 rotate_m4(mat, axis, angle);
676                 mul_m4_v3(mat, mirror);
677         }
678
679         /* distsq = len_squared_v3v3(mirror, cache->traced_location); */
680         distsq = len_squared_v3v3(mirror, cache->true_location);
681
682         if (distsq <= 4.0f * (cache->radius_squared))
683                 return (2.0f * (cache->radius) - sqrtf(distsq)) / (2.0f * (cache->radius));
684         else
685                 return 0;
686 }
687
688 static float calc_radial_symmetry_feather(Sculpt *sd, StrokeCache *cache, const char symm, const char axis)
689 {
690         int i;
691         float overlap;
692
693         overlap = 0;
694         for (i = 1; i < sd->radial_symm[axis - 'X']; ++i) {
695                 const float angle = 2 * M_PI * i / sd->radial_symm[axis - 'X'];
696                 overlap += calc_overlap(cache, symm, axis, angle);
697         }
698
699         return overlap;
700 }
701
702 static float calc_symmetry_feather(Sculpt *sd, StrokeCache *cache)
703 {
704         if (sd->paint.symmetry_flags & PAINT_SYMMETRY_FEATHER) {
705                 float overlap;
706                 int symm = cache->symmetry;
707                 int i;
708
709                 overlap = 0;
710                 for (i = 0; i <= symm; i++) {
711                         if (i == 0 || (symm & i && (symm != 5 || i != 3) && (symm != 6 || (i != 3 && i != 5)))) {
712
713                                 overlap += calc_overlap(cache, i, 0, 0);
714
715                                 overlap += calc_radial_symmetry_feather(sd, cache, i, 'X');
716                                 overlap += calc_radial_symmetry_feather(sd, cache, i, 'Y');
717                                 overlap += calc_radial_symmetry_feather(sd, cache, i, 'Z');
718                         }
719                 }
720
721                 return 1 / overlap;
722         }
723         else {
724                 return 1;
725         }
726 }
727
728 /** \name Calculate Normal and Center
729  *
730  * Calculate geometry surrounding the brush center.
731  * (optionally using original coordinates).
732  *
733  * Functions are:
734  * - #calc_area_center
735  * - #calc_area_normal
736  * - #calc_area_normal_and_center
737  *
738  * \note These are all _very_ similar, when changing one, check others.
739  * \{ */
740
741 static void calc_area_center(
742         Sculpt *sd, Object *ob,
743         PBVHNode **nodes, int totnode,
744         float r_area_co[3])
745 {
746         const Brush *brush = BKE_paint_brush(&sd->paint);
747         SculptSession *ss = ob->sculpt;
748         const bool has_bm_orco = ss->bm && sculpt_stroke_dynamic_topology(ss, brush);
749         int n;
750
751         /* 0=towards view, 1=flipped */
752         float area_co[2][3] = {{0.0f}};
753
754         int count[2] = {0};
755
756 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
757         for (n = 0; n < totnode; n++) {
758                 PBVHVertexIter vd;
759                 SculptBrushTest test;
760                 SculptUndoNode *unode;
761                 float private_co[2][3] = {{0.0f}};
762                 int   private_count[2] = {0};
763                 bool use_original;
764
765                 unode = sculpt_undo_push_node(ob, nodes[n], SCULPT_UNDO_COORDS);
766                 sculpt_brush_test_init(ss, &test);
767
768                 use_original = (ss->cache->original && (unode->co || unode->bm_entry));
769
770                 /* when the mesh is edited we can't rely on original coords
771                  * (original mesh may not even have verts in brush radius) */
772                 if (use_original && has_bm_orco) {
773                         float (*orco_coords)[3];
774                         int   (*orco_tris)[3];
775                         int     orco_tris_num;
776                         int i;
777
778                         BKE_pbvh_node_get_bm_orco_data(
779                                 nodes[n],
780                                 &orco_tris, &orco_tris_num, &orco_coords);
781
782                         for (i = 0; i < orco_tris_num; i++) {
783                                 const float *co_tri[3] = {
784                                     orco_coords[orco_tris[i][0]],
785                                     orco_coords[orco_tris[i][1]],
786                                     orco_coords[orco_tris[i][2]],
787                                 };
788                                 float co[3];
789
790                                 closest_on_tri_to_point_v3(co, test.location, UNPACK3(co_tri));
791
792                                 if (sculpt_brush_test_fast(&test, co)) {
793                                         float no[3];
794                                         int flip_index;
795
796                                         cross_tri_v3(no, UNPACK3(co_tri));
797
798                                         flip_index = (dot_v3v3(ss->cache->view_normal, no) <= 0.0f);
799                                         add_v3_v3(private_co[flip_index], co);
800                                         private_count[flip_index] += 1;
801                                 }
802                         }
803                 }
804                 else {
805                         BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
806                         {
807                                 const float *co;
808                                 const short *no_s;  /* bm_vert only */
809
810                                 if (use_original) {
811                                         if (unode->bm_entry) {
812                                                 BM_log_original_vert_data(ss->bm_log, vd.bm_vert, &co, &no_s);
813                                         }
814                                         else {
815                                                 co = unode->co[vd.i];
816                                                 no_s = unode->no[vd.i];
817                                         }
818                                 }
819                                 else {
820                                         co = vd.co;
821                                 }
822
823                                 if (sculpt_brush_test_fast(&test, co)) {
824                                         float no_buf[3];
825                                         const float *no;
826                                         int flip_index;
827
828                                         if (use_original) {
829                                                 normal_short_to_float_v3(no_buf, no_s);
830                                                 no = no_buf;
831                                         }
832                                         else {
833                                                 if (vd.no) {
834                                                         normal_short_to_float_v3(no_buf, vd.no);
835                                                         no = no_buf;
836                                                 }
837                                                 else {
838                                                         no = vd.fno;
839                                                 }
840                                         }
841
842                                         flip_index = (dot_v3v3(ss->cache->view_normal, no) <= 0.0f);
843                                         add_v3_v3(private_co[flip_index], co);
844                                         private_count[flip_index] += 1;
845                                 }
846                         }
847                         BKE_pbvh_vertex_iter_end;
848                 }
849
850 #pragma omp critical
851                 {
852                         /* for flatten center */
853                         add_v3_v3(area_co[0], private_co[0]);
854                         add_v3_v3(area_co[1], private_co[1]);
855
856                         /* weights */
857                         count[0] += private_count[0];
858                         count[1] += private_count[1];
859                 }
860         }
861
862         /* for flatten center */
863         for (n = 0; n < ARRAY_SIZE(area_co); n++) {
864                 if (count[n] != 0) {
865                         mul_v3_v3fl(r_area_co, area_co[n], 1.0f / count[n]);
866                         break;
867                 }
868         }
869         if (n == 2) {
870                 zero_v3(r_area_co);
871         }
872 }
873
874
875 static void calc_area_normal(
876         Sculpt *sd, Object *ob,
877         PBVHNode **nodes, int totnode,
878         float r_area_no[3])
879 {
880         const Brush *brush = BKE_paint_brush(&sd->paint);
881         SculptSession *ss = ob->sculpt;
882         const bool has_bm_orco = ss->bm && sculpt_stroke_dynamic_topology(ss, brush);
883         int n;
884
885         /* 0=towards view, 1=flipped */
886         float area_no[2][3] = {{0.0f}};
887
888         int count[2] = {0};
889
890         /* Grab brush requires to test on original data (see T25371) */
891         bool original;
892
893         original = (brush->sculpt_tool == SCULPT_TOOL_GRAB) ? true : ss->cache->original;
894         /* In general the original coords are not available with dynamic
895          * topology
896          *
897          * Mask tool could not use undo nodes to get coordinates from
898          * since the coordinates are not stored in those nodes.
899          * And mask tool is not gonna to modify vertex coordinates,
900          * so we don't actually need to use modified coords.
901          */
902         if (brush->sculpt_tool == SCULPT_TOOL_MASK) {
903                 original = false;
904         }
905
906 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
907         for (n = 0; n < totnode; n++) {
908                 PBVHVertexIter vd;
909                 SculptBrushTest test;
910                 SculptUndoNode *unode;
911                 float private_no[2][3] = {{0.0f}};
912                 int   private_count[2] = {0};
913                 bool use_original;
914
915                 unode = sculpt_undo_push_node(ob, nodes[n], SCULPT_UNDO_COORDS);
916                 sculpt_brush_test_init(ss, &test);
917
918                 use_original = (original && (unode->co || unode->bm_entry));
919
920                 /* when the mesh is edited we can't rely on original coords
921                  * (original mesh may not even have verts in brush radius) */
922                 if (use_original && has_bm_orco) {
923                         float (*orco_coords)[3];
924                         int   (*orco_tris)[3];
925                         int     orco_tris_num;
926                         int i;
927
928                         BKE_pbvh_node_get_bm_orco_data(
929                                 nodes[n],
930                                 &orco_tris, &orco_tris_num, &orco_coords);
931
932                         for (i = 0; i < orco_tris_num; i++) {
933                                 const float *co_tri[3] = {
934                                     orco_coords[orco_tris[i][0]],
935                                     orco_coords[orco_tris[i][1]],
936                                     orco_coords[orco_tris[i][2]],
937                                 };
938                                 float co[3];
939
940                                 closest_on_tri_to_point_v3(co, test.location, UNPACK3(co_tri));
941
942                                 if (sculpt_brush_test_fast(&test, co)) {
943                                         float no[3];
944                                         int flip_index;
945
946                                         normal_tri_v3(no, UNPACK3(co_tri));
947
948                                         flip_index = (dot_v3v3(ss->cache->view_normal, no) <= 0.0f);
949                                         add_v3_v3(private_no[flip_index], no);
950                                         private_count[flip_index] += 1;
951                                 }
952                         }
953                 }
954                 else {
955                         BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
956                         {
957                                 const float *co;
958                                 const short *no_s;  /* bm_vert only */
959
960                                 if (use_original) {
961                                         if (unode->bm_entry) {
962                                                 BM_log_original_vert_data(ss->bm_log, vd.bm_vert, &co, &no_s);
963                                         }
964                                         else {
965                                                 co = unode->co[vd.i];
966                                                 no_s = unode->no[vd.i];
967                                         }
968                                 }
969                                 else {
970                                         co = vd.co;
971                                 }
972
973                                 if (sculpt_brush_test_fast(&test, co)) {
974                                         float no_buf[3];
975                                         const float *no;
976                                         int flip_index;
977
978                                         if (use_original) {
979                                                 normal_short_to_float_v3(no_buf, no_s);
980                                                 no = no_buf;
981                                         }
982                                         else {
983                                                 if (vd.no) {
984                                                         normal_short_to_float_v3(no_buf, vd.no);
985                                                         no = no_buf;
986                                                 }
987                                                 else {
988                                                         no = vd.fno;
989                                                 }
990                                         }
991
992                                         flip_index = (dot_v3v3(ss->cache->view_normal, no) <= 0.0f);
993                                         add_v3_v3(private_no[flip_index], no);
994                                         private_count[flip_index] += 1;
995                                 }
996                         }
997                         BKE_pbvh_vertex_iter_end;
998                 }
999
1000 #pragma omp critical
1001                 {
1002                         /* for area normal */
1003                         add_v3_v3(area_no[0], private_no[0]);
1004                         add_v3_v3(area_no[1], private_no[1]);
1005
1006                         /* weights */
1007                         count[0] += private_count[0];
1008                         count[1] += private_count[1];
1009                 }
1010         }
1011
1012         /* for area normal */
1013         for (n = 0; n < ARRAY_SIZE(area_no); n++) {
1014                 if (normalize_v3_v3(r_area_no, area_no[n]) != 0.0f) {
1015                         break;
1016                 }
1017         }
1018 }
1019
1020 /* this calculates flatten center and area normal together,
1021  * amortizing the memory bandwidth and loop overhead to calculate both at the same time */
1022 static void calc_area_normal_and_center(
1023         Sculpt *sd, Object *ob,
1024         PBVHNode **nodes, int totnode,
1025         float r_area_no[3], float r_area_co[3])
1026 {
1027         const Brush *brush = BKE_paint_brush(&sd->paint);
1028         SculptSession *ss = ob->sculpt;
1029         const bool has_bm_orco = ss->bm && sculpt_stroke_dynamic_topology(ss, brush);
1030         int n;
1031
1032         /* 0=towards view, 1=flipped */
1033         float area_co[2][3] = {{0.0f}};
1034         float area_no[2][3] = {{0.0f}};
1035
1036         int count[2] = {0};
1037
1038 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
1039         for (n = 0; n < totnode; n++) {
1040                 PBVHVertexIter vd;
1041                 SculptBrushTest test;
1042                 SculptUndoNode *unode;
1043                 float private_co[2][3] = {{0.0f}};
1044                 float private_no[2][3] = {{0.0f}};
1045                 int   private_count[2] = {0};
1046                 bool use_original;
1047
1048                 unode = sculpt_undo_push_node(ob, nodes[n], SCULPT_UNDO_COORDS);
1049                 sculpt_brush_test_init(ss, &test);
1050
1051                 use_original = (ss->cache->original && (unode->co || unode->bm_entry));
1052
1053                 /* when the mesh is edited we can't rely on original coords
1054                  * (original mesh may not even have verts in brush radius) */
1055                 if (use_original && has_bm_orco) {
1056                         float (*orco_coords)[3];
1057                         int   (*orco_tris)[3];
1058                         int     orco_tris_num;
1059                         int i;
1060
1061                         BKE_pbvh_node_get_bm_orco_data(
1062                                 nodes[n],
1063                                 &orco_tris, &orco_tris_num, &orco_coords);
1064
1065                         for (i = 0; i < orco_tris_num; i++) {
1066                                 const float *co_tri[3] = {
1067                                     orco_coords[orco_tris[i][0]],
1068                                     orco_coords[orco_tris[i][1]],
1069                                     orco_coords[orco_tris[i][2]],
1070                                 };
1071                                 float co[3];
1072
1073                                 closest_on_tri_to_point_v3(co, test.location, UNPACK3(co_tri));
1074
1075                                 if (sculpt_brush_test_fast(&test, co)) {
1076                                         float no[3];
1077                                         int flip_index;
1078
1079                                         normal_tri_v3(no, UNPACK3(co_tri));
1080
1081                                         flip_index = (dot_v3v3(ss->cache->view_normal, no) <= 0.0f);
1082                                         add_v3_v3(private_co[flip_index], co);
1083                                         add_v3_v3(private_no[flip_index], no);
1084                                         private_count[flip_index] += 1;
1085                                 }
1086                         }
1087                 }
1088                 else {
1089                         BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
1090                         {
1091                                 const float *co;
1092                                 const short *no_s;  /* bm_vert only */
1093
1094                                 if (use_original) {
1095                                         if (unode->bm_entry) {
1096                                                 BM_log_original_vert_data(ss->bm_log, vd.bm_vert, &co, &no_s);
1097                                         }
1098                                         else {
1099                                                 co = unode->co[vd.i];
1100                                                 no_s = unode->no[vd.i];
1101                                         }
1102                                 }
1103                                 else {
1104                                         co = vd.co;
1105                                 }
1106
1107                                 if (sculpt_brush_test_fast(&test, co)) {
1108                                         float no_buf[3];
1109                                         const float *no;
1110                                         int flip_index;
1111
1112                                         if (use_original) {
1113                                                 normal_short_to_float_v3(no_buf, no_s);
1114                                                 no = no_buf;
1115                                         }
1116                                         else {
1117                                                 if (vd.no) {
1118                                                         normal_short_to_float_v3(no_buf, vd.no);
1119                                                         no = no_buf;
1120                                                 }
1121                                                 else {
1122                                                         no = vd.fno;
1123                                                 }
1124                                         }
1125
1126                                         flip_index = (dot_v3v3(ss->cache->view_normal, no) <= 0.0f);
1127                                         add_v3_v3(private_co[flip_index], co);
1128                                         add_v3_v3(private_no[flip_index], no);
1129                                         private_count[flip_index] += 1;
1130                                 }
1131                         }
1132                         BKE_pbvh_vertex_iter_end;
1133                 }
1134
1135 #pragma omp critical
1136                 {
1137                         /* for flatten center */
1138                         add_v3_v3(area_co[0], private_co[0]);
1139                         add_v3_v3(area_co[1], private_co[1]);
1140
1141                         /* for area normal */
1142                         add_v3_v3(area_no[0], private_no[0]);
1143                         add_v3_v3(area_no[1], private_no[1]);
1144
1145                         /* weights */
1146                         count[0] += private_count[0];
1147                         count[1] += private_count[1];
1148                 }
1149         }
1150
1151         /* for flatten center */
1152         for (n = 0; n < ARRAY_SIZE(area_co); n++) {
1153                 if (count[n] != 0) {
1154                         mul_v3_v3fl(r_area_co, area_co[n], 1.0f / count[n]);
1155                         break;
1156                 }
1157         }
1158         if (n == 2) {
1159                 zero_v3(r_area_co);
1160         }
1161
1162         /* for area normal */
1163         for (n = 0; n < ARRAY_SIZE(area_no); n++) {
1164                 if (normalize_v3_v3(r_area_no, area_no[n]) != 0.0f) {
1165                         break;
1166                 }
1167         }
1168 }
1169
1170 /** \} */
1171
1172
1173 /* Return modified brush strength. Includes the direction of the brush, positive
1174  * values pull vertices, negative values push. Uses tablet pressure and a
1175  * special multiplier found experimentally to scale the strength factor. */
1176 static float brush_strength(const Sculpt *sd, const StrokeCache *cache, const float feather, const UnifiedPaintSettings *ups)
1177 {
1178         const Scene *scene = cache->vc->scene;
1179         const Brush *brush = BKE_paint_brush((Paint *)&sd->paint);
1180
1181         /* Primary strength input; square it to make lower values more sensitive */
1182         const float root_alpha = BKE_brush_alpha_get(scene, brush);
1183         float alpha        = root_alpha * root_alpha;
1184         float dir          = brush->flag & BRUSH_DIR_IN ? -1 : 1;
1185         float pressure     = BKE_brush_use_alpha_pressure(scene, brush) ? cache->pressure : 1;
1186         float pen_flip     = cache->pen_flip ? -1 : 1;
1187         float invert       = cache->invert ? -1 : 1;
1188         float overlap       = ups->overlap_factor;
1189         /* spacing is integer percentage of radius, divide by 50 to get
1190          * normalized diameter */
1191
1192         float flip         = dir * invert * pen_flip;
1193
1194         switch (brush->sculpt_tool) {
1195                 case SCULPT_TOOL_CLAY:
1196                 case SCULPT_TOOL_CLAY_STRIPS:
1197                 case SCULPT_TOOL_DRAW:
1198                 case SCULPT_TOOL_LAYER:
1199                         return alpha * flip * pressure * overlap * feather;
1200                         
1201                 case SCULPT_TOOL_MASK:
1202                         overlap = (1 + overlap) / 2;
1203                         switch ((BrushMaskTool)brush->mask_tool) {
1204                                 case BRUSH_MASK_DRAW:
1205                                         return alpha * flip * pressure * overlap * feather;
1206                                 case BRUSH_MASK_SMOOTH:
1207                                         return alpha * pressure * feather;
1208                         }
1209
1210                 case SCULPT_TOOL_CREASE:
1211                 case SCULPT_TOOL_BLOB:
1212                         return alpha * flip * pressure * overlap * feather;
1213
1214                 case SCULPT_TOOL_INFLATE:
1215                         if (flip > 0) {
1216                                 return 0.250f * alpha * flip * pressure * overlap * feather;
1217                         }
1218                         else {
1219                                 return 0.125f * alpha * flip * pressure * overlap * feather;
1220                         }
1221
1222                 case SCULPT_TOOL_FILL:
1223                 case SCULPT_TOOL_SCRAPE:
1224                 case SCULPT_TOOL_FLATTEN:
1225                         if (flip > 0) {
1226                                 overlap = (1 + overlap) / 2;
1227                                 return alpha * flip * pressure * overlap * feather;
1228                         }
1229                         else {
1230                                 /* reduce strength for DEEPEN, PEAKS, and CONTRAST */
1231                                 return 0.5f * alpha * flip * pressure * overlap * feather; 
1232                         }
1233
1234                 case SCULPT_TOOL_SMOOTH:
1235                         return alpha * pressure * feather;
1236
1237                 case SCULPT_TOOL_PINCH:
1238                         if (flip > 0) {
1239                                 return alpha * flip * pressure * overlap * feather;
1240                         }
1241                         else {
1242                                 return 0.25f * alpha * flip * pressure * overlap * feather;
1243                         }
1244
1245                 case SCULPT_TOOL_NUDGE:
1246                         overlap = (1 + overlap) / 2;
1247                         return alpha * pressure * overlap * feather;
1248
1249                 case SCULPT_TOOL_THUMB:
1250                         return alpha * pressure * feather;
1251
1252                 case SCULPT_TOOL_SNAKE_HOOK:
1253                         return root_alpha * feather;
1254
1255                 case SCULPT_TOOL_GRAB:
1256                         return root_alpha * feather;
1257
1258                 case SCULPT_TOOL_ROTATE:
1259                         return alpha * pressure * feather;
1260
1261                 default:
1262                         return 0;
1263         }
1264 }
1265
1266 /* Return a multiplier for brush strength on a particular vertex. */
1267 static float tex_strength(SculptSession *ss, Brush *br,
1268                           const float point[3],
1269                           const float len,
1270                           const short vno[3],
1271                           const float fno[3],
1272                           const float mask)
1273 {
1274         StrokeCache *cache = ss->cache;
1275         const Scene *scene = cache->vc->scene;
1276         MTex *mtex = &br->mtex;
1277         float avg = 1;
1278         float rgba[4];
1279         int thread_num;
1280
1281         if (!mtex->tex) {
1282                 avg = 1;
1283         }
1284         else if (mtex->brush_map_mode == MTEX_MAP_MODE_3D) {
1285                 /* Get strength by feeding the vertex 
1286                  * location directly into a texture */
1287                 avg = BKE_brush_sample_tex_3D(scene, br, point, rgba, 0, ss->tex_pool);
1288         }
1289         else if (ss->texcache) {
1290                 float symm_point[3], point_2d[2];
1291                 float x = 0.0f, y = 0.0f; /* Quite warnings */
1292
1293                 /* if the active area is being applied for symmetry, flip it
1294                  * across the symmetry axis and rotate it back to the original
1295                  * position in order to project it. This insures that the 
1296                  * brush texture will be oriented correctly. */
1297
1298                 flip_v3_v3(symm_point, point, cache->mirror_symmetry_pass);
1299
1300                 if (cache->radial_symmetry_pass)
1301                         mul_m4_v3(cache->symm_rot_mat_inv, symm_point);
1302
1303                 ED_view3d_project_float_v2_m4(cache->vc->ar, symm_point, point_2d, cache->projection_mat);
1304
1305                 /* still no symmetry supported for other paint modes.
1306                  * Sculpt does it DIY */
1307                 if (mtex->brush_map_mode == MTEX_MAP_MODE_AREA) {
1308                         /* Similar to fixed mode, but projects from brush angle
1309                          * rather than view direction */
1310
1311                         mul_m4_v3(cache->brush_local_mat, symm_point);
1312
1313                         x = symm_point[0];
1314                         y = symm_point[1];
1315
1316                         x *= br->mtex.size[0];
1317                         y *= br->mtex.size[1];
1318
1319                         x += br->mtex.ofs[0];
1320                         y += br->mtex.ofs[1];
1321
1322 #ifdef _OPENMP
1323                         thread_num = omp_get_thread_num();
1324 #else
1325                         thread_num = 0;
1326 #endif
1327                         avg = paint_get_tex_pixel(&br->mtex, x, y, ss->tex_pool, thread_num);
1328
1329                         avg += br->texture_sample_bias;
1330                 }
1331                 else {
1332                         const float point_3d[3] = {point_2d[0], point_2d[1], 0.0f};
1333                         avg = BKE_brush_sample_tex_3D(scene, br, point_3d, rgba, 0, ss->tex_pool);
1334                 }
1335         }
1336
1337         /* Falloff curve */
1338         avg *= BKE_brush_curve_strength(br, len, cache->radius);
1339
1340         avg *= frontface(br, cache->view_normal, vno, fno);
1341
1342         /* Paint mask */
1343         avg *= 1.0f - mask;
1344
1345         return avg;
1346 }
1347
1348 typedef struct {
1349         Sculpt *sd;
1350         SculptSession *ss;
1351         float radius_squared;
1352         bool original;
1353 } SculptSearchSphereData;
1354
1355 /* Test AABB against sphere */
1356 static bool sculpt_search_sphere_cb(PBVHNode *node, void *data_v)
1357 {
1358         SculptSearchSphereData *data = data_v;
1359         float *center = data->ss->cache->location, nearest[3];
1360         float t[3], bb_min[3], bb_max[3];
1361         int i;
1362
1363         if (data->original)
1364                 BKE_pbvh_node_get_original_BB(node, bb_min, bb_max);
1365         else
1366                 BKE_pbvh_node_get_BB(node, bb_min, bb_max);
1367         
1368         for (i = 0; i < 3; ++i) {
1369                 if (bb_min[i] > center[i])
1370                         nearest[i] = bb_min[i];
1371                 else if (bb_max[i] < center[i])
1372                         nearest[i] = bb_max[i];
1373                 else
1374                         nearest[i] = center[i]; 
1375         }
1376         
1377         sub_v3_v3v3(t, center, nearest);
1378
1379         return len_squared_v3(t) < data->radius_squared;
1380 }
1381
1382 /* Handles clipping against a mirror modifier and SCULPT_LOCK axis flags */
1383 static void sculpt_clip(Sculpt *sd, SculptSession *ss, float co[3], const float val[3])
1384 {
1385         int i;
1386
1387         for (i = 0; i < 3; ++i) {
1388                 if (sd->flags & (SCULPT_LOCK_X << i))
1389                         continue;
1390
1391                 if ((ss->cache->flag & (CLIP_X << i)) && (fabsf(co[i]) <= ss->cache->clip_tolerance[i]))
1392                         co[i] = 0.0f;
1393                 else
1394                         co[i] = val[i];
1395         }
1396 }
1397
1398 /* Calculate primary direction of movement for many brushes */
1399 static void calc_sculpt_normal(
1400         Sculpt *sd, Object *ob,
1401         PBVHNode **nodes, int totnode,
1402         float r_area_no[3])
1403 {
1404         const Brush *brush = BKE_paint_brush(&sd->paint);
1405         const SculptSession *ss = ob->sculpt;
1406
1407         switch (brush->sculpt_plane) {
1408                 case SCULPT_DISP_DIR_VIEW:
1409                         copy_v3_v3(r_area_no, ss->cache->true_view_normal);
1410                         break;
1411
1412                 case SCULPT_DISP_DIR_X:
1413                         ARRAY_SET_ITEMS(r_area_no, 1, 0, 0);
1414                         break;
1415
1416                 case SCULPT_DISP_DIR_Y:
1417                         ARRAY_SET_ITEMS(r_area_no, 0, 1, 0);
1418                         break;
1419
1420                 case SCULPT_DISP_DIR_Z:
1421                         ARRAY_SET_ITEMS(r_area_no, 0, 0, 1);
1422                         break;
1423
1424                 case SCULPT_DISP_DIR_AREA:
1425                         calc_area_normal(sd, ob, nodes, totnode, r_area_no);
1426                         break;
1427
1428                 default:
1429                         break;
1430         }
1431 }
1432
1433 static void update_sculpt_normal(Sculpt *sd, Object *ob,
1434                                  PBVHNode **nodes, int totnode)
1435 {
1436         const Brush *brush = BKE_paint_brush(&sd->paint);
1437         StrokeCache *cache = ob->sculpt->cache;
1438         
1439         if (cache->mirror_symmetry_pass == 0 &&
1440             cache->radial_symmetry_pass == 0 &&
1441             (cache->first_time || !(brush->flag & BRUSH_ORIGINAL_NORMAL)))
1442         {
1443                 calc_sculpt_normal(sd, ob, nodes, totnode, cache->sculpt_normal);
1444                 copy_v3_v3(cache->sculpt_normal_symm, cache->sculpt_normal);
1445         }
1446         else {
1447                 copy_v3_v3(cache->sculpt_normal_symm, cache->sculpt_normal);
1448                 flip_v3(cache->sculpt_normal_symm, cache->mirror_symmetry_pass);
1449                 mul_m4_v3(cache->symm_rot_mat, cache->sculpt_normal_symm);
1450         }
1451 }
1452
1453 static void calc_local_y(ViewContext *vc, const float center[3], float y[3])
1454 {
1455         Object *ob = vc->obact;
1456         float loc[3], mval_f[2] = {0.0f, 1.0f};
1457         float zfac;
1458
1459         mul_v3_m4v3(loc, ob->imat, center);
1460         zfac = ED_view3d_calc_zfac(vc->rv3d, loc, NULL);
1461
1462         ED_view3d_win_to_delta(vc->ar, mval_f, y, zfac);
1463         normalize_v3(y);
1464
1465         add_v3_v3(y, ob->loc);
1466         mul_m4_v3(ob->imat, y);
1467 }
1468
1469 static void calc_brush_local_mat(const Brush *brush, Object *ob,
1470                                  float local_mat[4][4])
1471 {
1472         const StrokeCache *cache = ob->sculpt->cache;
1473         float tmat[4][4];
1474         float mat[4][4];
1475         float scale[4][4];
1476         float angle, v[3];
1477         float up[3];
1478
1479         /* Ensure ob->imat is up to date */
1480         invert_m4_m4(ob->imat, ob->obmat);
1481
1482         /* Initialize last column of matrix */
1483         mat[0][3] = 0;
1484         mat[1][3] = 0;
1485         mat[2][3] = 0;
1486         mat[3][3] = 1;
1487
1488         /* Get view's up vector in object-space */
1489         calc_local_y(cache->vc, cache->location, up);
1490
1491         /* Calculate the X axis of the local matrix */
1492         cross_v3_v3v3(v, up, cache->sculpt_normal);
1493         /* Apply rotation (user angle, rake, etc.) to X axis */
1494         angle = brush->mtex.rot - cache->special_rotation;
1495         rotate_v3_v3v3fl(mat[0], v, cache->sculpt_normal, angle);
1496
1497         /* Get other axes */
1498         cross_v3_v3v3(mat[1], cache->sculpt_normal, mat[0]);
1499         copy_v3_v3(mat[2], cache->sculpt_normal);
1500
1501         /* Set location */
1502         copy_v3_v3(mat[3], cache->location);
1503
1504         /* Scale by brush radius */
1505         normalize_m4(mat);
1506         scale_m4_fl(scale, cache->radius);
1507         mul_m4_m4m4(tmat, mat, scale);
1508
1509         /* Return inverse (for converting from modelspace coords to local
1510          * area coords) */
1511         invert_m4_m4(local_mat, tmat);
1512 }
1513
1514 static void update_brush_local_mat(Sculpt *sd, Object *ob)
1515 {
1516         StrokeCache *cache = ob->sculpt->cache;
1517
1518         if (cache->mirror_symmetry_pass == 0 &&
1519             cache->radial_symmetry_pass == 0)
1520         {
1521                 calc_brush_local_mat(BKE_paint_brush(&sd->paint), ob,
1522                                      cache->brush_local_mat);
1523         }
1524 }
1525
1526 /* Test whether the StrokeCache.sculpt_normal needs update in
1527  * do_brush_action() */
1528 static int brush_needs_sculpt_normal(const Brush *brush)
1529 {
1530         return ((ELEM(brush->sculpt_tool,
1531                       SCULPT_TOOL_GRAB,
1532                       SCULPT_TOOL_SNAKE_HOOK) &&
1533                  (brush->normal_weight > 0)) ||
1534
1535                 ELEM(brush->sculpt_tool,
1536                      SCULPT_TOOL_BLOB,
1537                      SCULPT_TOOL_CREASE,
1538                      SCULPT_TOOL_DRAW,
1539                      SCULPT_TOOL_LAYER,
1540                      SCULPT_TOOL_NUDGE,
1541                      SCULPT_TOOL_ROTATE,
1542                      SCULPT_TOOL_THUMB) ||
1543
1544                 (brush->mtex.brush_map_mode == MTEX_MAP_MODE_AREA));
1545 }
1546
1547 /* For the smooth brush, uses the neighboring vertices around vert to calculate
1548  * a smoothed location for vert. Skips corner vertices (used by only one
1549  * polygon.) */
1550 static void neighbor_average(SculptSession *ss, float avg[3], unsigned vert)
1551 {
1552         const MeshElemMap *vert_map = &ss->pmap[vert];
1553         const MVert *mvert = ss->mvert;
1554         float (*deform_co)[3] = ss->deform_cos;
1555
1556         /* Don't modify corner vertices */
1557         if (vert_map->count > 1) {
1558                 int i, total = 0;
1559
1560                 zero_v3(avg);
1561
1562                 for (i = 0; i < vert_map->count; i++) {
1563                         const MPoly *p = &ss->mpoly[vert_map->indices[i]];
1564                         unsigned f_adj_v[2];
1565
1566                         if (poly_get_adj_loops_from_vert(f_adj_v, p, ss->mloop, vert) != -1) {
1567                                 int j;
1568                                 for (j = 0; j < ARRAY_SIZE(f_adj_v); j += 1) {
1569                                         if (vert_map->count != 2 || ss->pmap[f_adj_v[j]].count <= 2) {
1570                                                 add_v3_v3(avg, deform_co ? deform_co[f_adj_v[j]] :
1571                                                           mvert[f_adj_v[j]].co);
1572
1573                                                 total++;
1574                                         }
1575                                 }
1576                         }
1577                 }
1578
1579                 if (total > 0) {
1580                         mul_v3_fl(avg, 1.0f / total);
1581                         return;
1582                 }
1583         }
1584
1585         copy_v3_v3(avg, deform_co ? deform_co[vert] : mvert[vert].co);
1586 }
1587
1588 /* Similar to neighbor_average(), but returns an averaged mask value
1589  * instead of coordinate. Also does not restrict based on border or
1590  * corner vertices. */
1591 static float neighbor_average_mask(SculptSession *ss, unsigned vert)
1592 {
1593         const float *vmask = ss->vmask;
1594         float avg = 0;
1595         int i, total = 0;
1596
1597         for (i = 0; i < ss->pmap[vert].count; i++) {
1598                 const MPoly *p = &ss->mpoly[ss->pmap[vert].indices[i]];
1599                 unsigned f_adj_v[2];
1600
1601                 if (poly_get_adj_loops_from_vert(f_adj_v, p, ss->mloop, vert) != -1) {
1602                         int j;
1603                         for (j = 0; j < ARRAY_SIZE(f_adj_v); j += 1) {
1604                                 avg += vmask[f_adj_v[j]];
1605                                 total++;
1606                         }
1607                 }
1608         }
1609
1610         if (total > 0)
1611                 return avg / (float)total;
1612         else
1613                 return vmask[vert];
1614 }
1615
1616 /* Same logic as neighbor_average(), but for bmesh rather than mesh */
1617 static void bmesh_neighbor_average(float avg[3], BMVert *v)
1618 {
1619         /* logic for 3 or more is identical */
1620         const int vfcount = BM_vert_face_count_ex(v, 3);
1621
1622         /* Don't modify corner vertices */
1623         if (vfcount > 1) {
1624                 BMIter liter;
1625                 BMLoop *l;
1626                 int i, total = 0;
1627
1628                 zero_v3(avg);
1629
1630                 BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
1631                         const BMVert *adj_v[2] = {l->prev->v, l->next->v};
1632
1633                         for (i = 0; i < ARRAY_SIZE(adj_v); i++) {
1634                                 const BMVert *v_other = adj_v[i];
1635                                 if (vfcount != 2 || BM_vert_face_count_ex(v_other, 2) <= 2) {
1636                                         add_v3_v3(avg, v_other->co);
1637                                         total++;
1638                                 }
1639                         }
1640                 }
1641
1642                 if (total > 0) {
1643                         mul_v3_fl(avg, 1.0f / total);
1644                         return;
1645                 }
1646         }
1647
1648         copy_v3_v3(avg, v->co);
1649 }
1650
1651 /* Same logic as neighbor_average_mask(), but for bmesh rather than mesh */
1652 static float bmesh_neighbor_average_mask(BMVert *v, const int cd_vert_mask_offset)
1653 {
1654         BMIter liter;
1655         BMLoop *l;
1656         float avg = 0;
1657         int i, total = 0;
1658
1659         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
1660                 /* skip this vertex */
1661                 const BMVert *adj_v[2] = {l->prev->v, l->next->v};
1662
1663                 for (i = 0; i < ARRAY_SIZE(adj_v); i++) {
1664                         const BMVert *v_other = adj_v[i];
1665                         const float *vmask = BM_ELEM_CD_GET_VOID_P(v_other, cd_vert_mask_offset);
1666                         avg += (*vmask);
1667                         total++;
1668                 }
1669         }
1670
1671         if (total > 0) {
1672                 return avg / (float)total;
1673         }
1674         else {
1675                 const float *vmask = BM_ELEM_CD_GET_VOID_P(v, cd_vert_mask_offset);
1676                 return (*vmask);
1677         }
1678 }
1679
1680 static void do_mesh_smooth_brush(Sculpt *sd, SculptSession *ss, PBVHNode *node, float bstrength, int smooth_mask)
1681 {
1682         Brush *brush = BKE_paint_brush(&sd->paint);
1683         PBVHVertexIter vd;
1684         SculptBrushTest test;
1685         
1686         CLAMP(bstrength, 0.0f, 1.0f);
1687
1688         sculpt_brush_test_init(ss, &test);
1689
1690         BKE_pbvh_vertex_iter_begin(ss->pbvh, node, vd, PBVH_ITER_UNIQUE)
1691         {
1692                 if (sculpt_brush_test(&test, vd.co)) {
1693                         const float fade = bstrength * tex_strength(ss, brush, vd.co, test.dist,
1694                                                                     vd.no, vd.fno,
1695                                                                     smooth_mask ? 0 : (vd.mask ? *vd.mask : 0.0f));
1696                         if (smooth_mask) {
1697                                 float val = neighbor_average_mask(ss, vd.vert_indices[vd.i]) - *vd.mask;
1698                                 val *= fade * bstrength;
1699                                 *vd.mask += val;
1700                                 CLAMP(*vd.mask, 0, 1);
1701                         }
1702                         else {
1703                                 float avg[3], val[3];
1704
1705                                 neighbor_average(ss, avg, vd.vert_indices[vd.i]);
1706                                 sub_v3_v3v3(val, avg, vd.co);
1707                                 mul_v3_fl(val, fade);
1708
1709                                 add_v3_v3(val, vd.co);
1710
1711                                 sculpt_clip(sd, ss, vd.co, val);
1712                         }
1713
1714                         if (vd.mvert)
1715                                 vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
1716                 }
1717         }
1718         BKE_pbvh_vertex_iter_end;
1719 }
1720
1721 static void do_bmesh_smooth_brush(Sculpt *sd, SculptSession *ss, PBVHNode *node, float bstrength, int smooth_mask)
1722 {
1723         Brush *brush = BKE_paint_brush(&sd->paint);
1724         PBVHVertexIter vd;
1725         SculptBrushTest test;
1726         
1727         CLAMP(bstrength, 0.0f, 1.0f);
1728
1729         sculpt_brush_test_init(ss, &test);
1730
1731         BKE_pbvh_vertex_iter_begin(ss->pbvh, node, vd, PBVH_ITER_UNIQUE)
1732         {
1733                 if (sculpt_brush_test(&test, vd.co)) {
1734                         const float fade = bstrength * tex_strength(ss, brush, vd.co, test.dist,
1735                                                                     vd.no, vd.fno,
1736                                                                     smooth_mask ? 0 : *vd.mask);
1737                         if (smooth_mask) {
1738                                 float val = bmesh_neighbor_average_mask(vd.bm_vert, vd.cd_vert_mask_offset) - *vd.mask;
1739                                 val *= fade * bstrength;
1740                                 *vd.mask += val;
1741                                 CLAMP(*vd.mask, 0, 1);
1742                         }
1743                         else {
1744                                 float avg[3], val[3];
1745
1746                                 bmesh_neighbor_average(avg, vd.bm_vert);
1747                                 sub_v3_v3v3(val, avg, vd.co);
1748                                 mul_v3_fl(val, fade);
1749
1750                                 add_v3_v3(val, vd.co);
1751
1752                                 sculpt_clip(sd, ss, vd.co, val);
1753                         }
1754
1755                         if (vd.mvert)
1756                                 vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
1757                 }
1758         }
1759         BKE_pbvh_vertex_iter_end;
1760 }
1761
1762 static void do_multires_smooth_brush(Sculpt *sd, SculptSession *ss, PBVHNode *node,
1763                                      float bstrength, int smooth_mask)
1764 {
1765         Brush *brush = BKE_paint_brush(&sd->paint);
1766         SculptBrushTest test;
1767         CCGElem **griddata, *data;
1768         CCGKey key;
1769         DMGridAdjacency *gridadj, *adj;
1770         float (*tmpgrid_co)[3], (*tmprow_co)[3];
1771         float *tmpgrid_mask, *tmprow_mask;
1772         int v1, v2, v3, v4;
1773         int thread_num;
1774         BLI_bitmap * const *grid_hidden;
1775         int *grid_indices, totgrid, gridsize, i, x, y;
1776
1777         sculpt_brush_test_init(ss, &test);
1778
1779         CLAMP(bstrength, 0.0f, 1.0f);
1780
1781         BKE_pbvh_node_get_grids(ss->pbvh, node, &grid_indices, &totgrid,
1782                                 NULL, &gridsize, &griddata, &gridadj);
1783         BKE_pbvh_get_grid_key(ss->pbvh, &key);
1784
1785         grid_hidden = BKE_pbvh_grid_hidden(ss->pbvh);
1786
1787 #ifdef _OPENMP
1788         thread_num = omp_get_thread_num();
1789 #else
1790         thread_num = 0;
1791 #endif
1792         tmpgrid_co = ss->cache->tmpgrid_co[thread_num];
1793         tmprow_co = ss->cache->tmprow_co[thread_num];
1794         tmpgrid_mask = ss->cache->tmpgrid_mask[thread_num];
1795         tmprow_mask = ss->cache->tmprow_mask[thread_num];
1796
1797         for (i = 0; i < totgrid; ++i) {
1798                 int gi = grid_indices[i];
1799                 const BLI_bitmap *gh = grid_hidden[gi];
1800                 data = griddata[gi];
1801                 adj = &gridadj[gi];
1802
1803                 if (smooth_mask)
1804                         memset(tmpgrid_mask, 0, sizeof(float) * gridsize * gridsize);
1805                 else
1806                         memset(tmpgrid_co, 0, sizeof(float) * 3 * gridsize * gridsize);
1807
1808                 for (y = 0; y < gridsize - 1; y++) {
1809                         v1 = y * gridsize;
1810                         if (smooth_mask) {
1811                                 tmprow_mask[0] = (*CCG_elem_offset_mask(&key, data, v1) +
1812                                                   *CCG_elem_offset_mask(&key, data, v1 + gridsize));
1813                         }
1814                         else {
1815                                 add_v3_v3v3(tmprow_co[0],
1816                                             CCG_elem_offset_co(&key, data, v1),
1817                                             CCG_elem_offset_co(&key, data, v1 + gridsize));
1818                         }
1819
1820                         for (x = 0; x < gridsize - 1; x++) {
1821                                 v1 = x + y * gridsize;
1822                                 v2 = v1 + 1;
1823                                 v3 = v1 + gridsize;
1824                                 v4 = v3 + 1;
1825
1826                                 if (smooth_mask) {
1827                                         float tmp;
1828
1829                                         tmprow_mask[x + 1] = (*CCG_elem_offset_mask(&key, data, v2) +
1830                                                               *CCG_elem_offset_mask(&key, data, v4));
1831                                         tmp = tmprow_mask[x + 1] + tmprow_mask[x];
1832
1833                                         tmpgrid_mask[v1] += tmp;
1834                                         tmpgrid_mask[v2] += tmp;
1835                                         tmpgrid_mask[v3] += tmp;
1836                                         tmpgrid_mask[v4] += tmp;
1837                                 }
1838                                 else {
1839                                         float tmp[3];
1840
1841                                         add_v3_v3v3(tmprow_co[x + 1],
1842                                                     CCG_elem_offset_co(&key, data, v2),
1843                                                     CCG_elem_offset_co(&key, data, v4));
1844                                         add_v3_v3v3(tmp, tmprow_co[x + 1], tmprow_co[x]);
1845
1846                                         add_v3_v3(tmpgrid_co[v1], tmp);
1847                                         add_v3_v3(tmpgrid_co[v2], tmp);
1848                                         add_v3_v3(tmpgrid_co[v3], tmp);
1849                                         add_v3_v3(tmpgrid_co[v4], tmp);
1850                                 }
1851                         }
1852                 }
1853
1854                 /* blend with existing coordinates */
1855                 for (y = 0; y < gridsize; ++y) {
1856                         for (x = 0; x < gridsize; ++x) {
1857                                 float *co;
1858                                 const float *fno;
1859                                 float *mask;
1860                                 int index;
1861
1862                                 if (gh) {
1863                                         if (BLI_BITMAP_TEST(gh, y * gridsize + x))
1864                                                 continue;
1865                                 }
1866
1867                                 if (x == 0 && adj->index[0] == -1)
1868                                         continue;
1869
1870                                 if (x == gridsize - 1 && adj->index[2] == -1)
1871                                         continue;
1872
1873                                 if (y == 0 && adj->index[3] == -1)
1874                                         continue;
1875
1876                                 if (y == gridsize - 1 && adj->index[1] == -1)
1877                                         continue;
1878
1879                                 index = x + y * gridsize;
1880                                 co = CCG_elem_offset_co(&key, data, index);
1881                                 fno = CCG_elem_offset_no(&key, data, index);
1882                                 mask = CCG_elem_offset_mask(&key, data, index);
1883
1884                                 if (sculpt_brush_test(&test, co)) {
1885                                         const float strength_mask = (smooth_mask ? 0 : *mask);
1886                                         const float fade = bstrength * tex_strength(ss, brush, co, test.dist,
1887                                                                                     NULL, fno, strength_mask);
1888                                         float n = 1.0f / 16.0f;
1889                                         
1890                                         if (x == 0 || x == gridsize - 1)
1891                                                 n *= 2;
1892                                         
1893                                         if (y == 0 || y == gridsize - 1)
1894                                                 n *= 2;
1895                                         
1896                                         if (smooth_mask) {
1897                                                 *mask += ((tmpgrid_mask[x + y * gridsize] * n) - *mask) * fade;
1898                                         }
1899                                         else {
1900                                                 float *avg, val[3];
1901
1902                                                 avg = tmpgrid_co[x + y * gridsize];
1903
1904                                                 mul_v3_fl(avg, n);
1905
1906                                                 sub_v3_v3v3(val, avg, co);
1907                                                 mul_v3_fl(val, fade);
1908
1909                                                 add_v3_v3(val, co);
1910
1911                                                 sculpt_clip(sd, ss, co, val);
1912                                         }
1913                                 }
1914                         }
1915                 }
1916         }
1917 }
1918
1919 static void smooth(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode,
1920                    float bstrength, int smooth_mask)
1921 {
1922         SculptSession *ss = ob->sculpt;
1923         const int max_iterations = 4;
1924         const float fract = 1.0f / max_iterations;
1925         PBVHType type = BKE_pbvh_type(ss->pbvh);
1926         int iteration, n, count;
1927         float last;
1928
1929         CLAMP(bstrength, 0, 1);
1930
1931         count = (int)(bstrength * max_iterations);
1932         last  = max_iterations * (bstrength - count * fract);
1933
1934         if (type == PBVH_FACES && !ss->pmap) {
1935                 BLI_assert(!"sculpt smooth: pmap missing");
1936                 return;
1937         }
1938
1939         for (iteration = 0; iteration <= count; ++iteration) {
1940                 float strength = (iteration != count) ? 1.0f : last;
1941
1942 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
1943                 for (n = 0; n < totnode; n++) {
1944                         switch (type) {
1945                                 case PBVH_GRIDS:
1946                                         do_multires_smooth_brush(sd, ss, nodes[n], strength,
1947                                                                  smooth_mask);
1948                                         break;
1949                                 case PBVH_FACES:
1950                                         do_mesh_smooth_brush(sd, ss, nodes[n], strength,
1951                                                              smooth_mask);
1952                                         break;
1953                                 case PBVH_BMESH:
1954                                         do_bmesh_smooth_brush(sd, ss, nodes[n], strength, smooth_mask);
1955                                         break;
1956                         }
1957                 }
1958
1959                 if (ss->multires)
1960                         multires_stitch_grids(ob);
1961         }
1962 }
1963
1964 static void do_smooth_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
1965 {
1966         SculptSession *ss = ob->sculpt;
1967         smooth(sd, ob, nodes, totnode, ss->cache->bstrength, false);
1968 }
1969
1970 static void do_mask_brush_draw(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
1971 {
1972         SculptSession *ss = ob->sculpt;
1973         Brush *brush = BKE_paint_brush(&sd->paint);
1974         float bstrength = ss->cache->bstrength;
1975         int n;
1976
1977         /* threaded loop over nodes */
1978 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
1979         for (n = 0; n < totnode; n++) {
1980                 PBVHVertexIter vd;
1981                 SculptBrushTest test;
1982
1983                 sculpt_brush_test_init(ss, &test);
1984
1985                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
1986                 {
1987                         if (sculpt_brush_test(&test, vd.co)) {
1988                                 float fade = tex_strength(ss, brush, vd.co, test.dist,
1989                                                           vd.no, vd.fno, 0);
1990
1991                                 (*vd.mask) += fade * bstrength;
1992                                 CLAMP(*vd.mask, 0, 1);
1993
1994                                 if (vd.mvert)
1995                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
1996                         }
1997                         BKE_pbvh_vertex_iter_end;
1998                 }
1999         }
2000 }
2001
2002 static void do_mask_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2003 {
2004         SculptSession *ss = ob->sculpt;
2005         Brush *brush = BKE_paint_brush(&sd->paint);
2006         
2007         switch ((BrushMaskTool)brush->mask_tool) {
2008                 case BRUSH_MASK_DRAW:
2009                         do_mask_brush_draw(sd, ob, nodes, totnode);
2010                         break;
2011                 case BRUSH_MASK_SMOOTH:
2012                         smooth(sd, ob, nodes, totnode, ss->cache->bstrength, true);
2013                         break;
2014         }
2015 }
2016
2017 static void do_draw_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2018 {
2019         SculptSession *ss = ob->sculpt;
2020         Brush *brush = BKE_paint_brush(&sd->paint);
2021         float offset[3];
2022         float bstrength = ss->cache->bstrength;
2023         int n;
2024
2025         /* offset with as much as possible factored in already */
2026         mul_v3_v3fl(offset, ss->cache->sculpt_normal_symm, ss->cache->radius);
2027         mul_v3_v3(offset, ss->cache->scale);
2028         mul_v3_fl(offset, bstrength);
2029
2030         /* threaded loop over nodes */
2031 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2032         for (n = 0; n < totnode; n++) {
2033                 PBVHVertexIter vd;
2034                 SculptBrushTest test;
2035                 float (*proxy)[3];
2036
2037                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2038
2039                 sculpt_brush_test_init(ss, &test);
2040
2041                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2042                 {
2043                         if (sculpt_brush_test(&test, vd.co)) {
2044                                 /* offset vertex */
2045                                 float fade = tex_strength(ss, brush, vd.co, test.dist, vd.no,
2046                                                           vd.fno, vd.mask ? *vd.mask : 0.0f);
2047
2048                                 mul_v3_v3fl(proxy[vd.i], offset, fade);
2049
2050                                 if (vd.mvert)
2051                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2052                         }
2053                 }
2054                 BKE_pbvh_vertex_iter_end;
2055         }
2056 }
2057
2058 static void do_crease_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2059 {
2060         SculptSession *ss = ob->sculpt;
2061         const Scene *scene = ss->cache->vc->scene;
2062         Brush *brush = BKE_paint_brush(&sd->paint);
2063         float offset[3];
2064         float bstrength = ss->cache->bstrength;
2065         float flippedbstrength, crease_correction;
2066         float brush_alpha;
2067         int n;
2068
2069         SculptProjectVector spvc;
2070
2071         /* offset with as much as possible factored in already */
2072         mul_v3_v3fl(offset, ss->cache->sculpt_normal_symm, ss->cache->radius);
2073         mul_v3_v3(offset, ss->cache->scale);
2074         mul_v3_fl(offset, bstrength);
2075         
2076         /* we divide out the squared alpha and multiply by the squared crease to give us the pinch strength */
2077         crease_correction = brush->crease_pinch_factor * brush->crease_pinch_factor;
2078         brush_alpha = BKE_brush_alpha_get(scene, brush);
2079         if (brush_alpha > 0.0f)
2080                 crease_correction /= brush_alpha * brush_alpha;
2081
2082         /* we always want crease to pinch or blob to relax even when draw is negative */
2083         flippedbstrength = (bstrength < 0) ? -crease_correction * bstrength : crease_correction * bstrength;
2084
2085         if (brush->sculpt_tool == SCULPT_TOOL_BLOB) flippedbstrength *= -1.0f;
2086
2087         /* Use surface normal for 'spvc', so the vertices are pinched towards a line instead of a single point.
2088          * Without this we get a 'flat' surface surrounding the pinch */
2089         sculpt_project_v3_cache_init(&spvc, ss->cache->sculpt_normal_symm);
2090
2091         /* threaded loop over nodes */
2092 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2093         for (n = 0; n < totnode; n++) {
2094                 PBVHVertexIter vd;
2095                 SculptBrushTest test;
2096                 float (*proxy)[3];
2097
2098                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2099
2100                 sculpt_brush_test_init(ss, &test);
2101
2102                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2103                 {
2104                         if (sculpt_brush_test(&test, vd.co)) {
2105                                 /* offset vertex */
2106                                 const float fade = tex_strength(ss, brush, vd.co, test.dist,
2107                                                                 vd.no, vd.fno, vd.mask ? *vd.mask : 0.0f);
2108                                 float val1[3];
2109                                 float val2[3];
2110
2111                                 /* first we pinch */
2112                                 sub_v3_v3v3(val1, test.location, vd.co);
2113                                 mul_v3_fl(val1, fade * flippedbstrength);
2114
2115                                 sculpt_project_v3(&spvc, val1, val1);
2116
2117                                 /* then we draw */
2118                                 mul_v3_v3fl(val2, offset, fade);
2119
2120                                 add_v3_v3v3(proxy[vd.i], val1, val2);
2121
2122                                 if (vd.mvert)
2123                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2124                         }
2125                 }
2126                 BKE_pbvh_vertex_iter_end;
2127         }
2128 }
2129
2130 static void do_pinch_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2131 {
2132         SculptSession *ss = ob->sculpt;
2133         Brush *brush = BKE_paint_brush(&sd->paint);
2134         float bstrength = ss->cache->bstrength;
2135         int n;
2136
2137 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2138         for (n = 0; n < totnode; n++) {
2139                 PBVHVertexIter vd;
2140                 SculptBrushTest test;
2141                 float (*proxy)[3];
2142
2143                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2144
2145                 sculpt_brush_test_init(ss, &test);
2146
2147                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2148                 {
2149                         if (sculpt_brush_test(&test, vd.co)) {
2150                                 float fade = bstrength * tex_strength(ss, brush, vd.co, test.dist, vd.no,
2151                                                                       vd.fno, vd.mask ? *vd.mask : 0.0f);
2152                                 float val[3];
2153
2154                                 sub_v3_v3v3(val, test.location, vd.co);
2155                                 mul_v3_v3fl(proxy[vd.i], val, fade);
2156
2157                                 if (vd.mvert)
2158                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2159                         }
2160                 }
2161                 BKE_pbvh_vertex_iter_end;
2162         }
2163 }
2164
2165 static void do_grab_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2166 {
2167         SculptSession *ss = ob->sculpt;
2168         Brush *brush = BKE_paint_brush(&sd->paint);
2169         float bstrength = ss->cache->bstrength;
2170         float grab_delta[3];
2171         int n;
2172         float len;
2173
2174         copy_v3_v3(grab_delta, ss->cache->grab_delta_symmetry);
2175
2176         len = len_v3(grab_delta);
2177
2178         if (brush->normal_weight > 0) {
2179                 mul_v3_fl(ss->cache->sculpt_normal_symm, len * brush->normal_weight);
2180                 mul_v3_fl(grab_delta, 1.0f - brush->normal_weight);
2181                 add_v3_v3(grab_delta, ss->cache->sculpt_normal_symm);
2182         }
2183
2184 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2185         for (n = 0; n < totnode; n++) {
2186                 PBVHVertexIter vd;
2187                 SculptBrushTest test;
2188                 SculptOrigVertData orig_data;
2189                 float (*proxy)[3];
2190
2191                 sculpt_orig_vert_data_init(&orig_data, ob, nodes[n]);
2192
2193                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2194
2195                 sculpt_brush_test_init(ss, &test);
2196
2197                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2198                 {
2199                         sculpt_orig_vert_data_update(&orig_data, &vd);
2200
2201                         if (sculpt_brush_test(&test, orig_data.co)) {
2202                                 const float fade = bstrength * tex_strength(ss, brush,
2203                                                                             orig_data.co,
2204                                                                             test.dist,
2205                                                                             orig_data.no,
2206                                                                             NULL, vd.mask ? *vd.mask : 0.0f);
2207
2208                                 mul_v3_v3fl(proxy[vd.i], grab_delta, fade);
2209
2210                                 if (vd.mvert)
2211                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2212                         }
2213                 }
2214                 BKE_pbvh_vertex_iter_end;
2215         }
2216 }
2217
2218 static void do_nudge_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2219 {
2220         SculptSession *ss = ob->sculpt;
2221         Brush *brush = BKE_paint_brush(&sd->paint);
2222         float bstrength = ss->cache->bstrength;
2223         float grab_delta[3];
2224         float tmp[3], cono[3];
2225         int n;
2226
2227         copy_v3_v3(grab_delta, ss->cache->grab_delta_symmetry);
2228
2229         cross_v3_v3v3(tmp, ss->cache->sculpt_normal_symm, grab_delta);
2230         cross_v3_v3v3(cono, tmp, ss->cache->sculpt_normal_symm);
2231
2232 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2233         for (n = 0; n < totnode; n++) {
2234                 PBVHVertexIter vd;
2235                 SculptBrushTest test;
2236                 float (*proxy)[3];
2237
2238                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2239
2240                 sculpt_brush_test_init(ss, &test);
2241
2242                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2243                 {
2244                         if (sculpt_brush_test(&test, vd.co)) {
2245                                 const float fade = bstrength * tex_strength(ss, brush, vd.co, test.dist,
2246                                                                             vd.no, vd.fno, vd.mask ? *vd.mask : 0.0f);
2247
2248                                 mul_v3_v3fl(proxy[vd.i], cono, fade);
2249
2250                                 if (vd.mvert)
2251                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2252                         }
2253                 }
2254                 BKE_pbvh_vertex_iter_end;
2255         }
2256 }
2257
2258 static void do_snake_hook_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2259 {
2260         SculptSession *ss = ob->sculpt;
2261         Brush *brush = BKE_paint_brush(&sd->paint);
2262         float bstrength = ss->cache->bstrength;
2263         float grab_delta[3];
2264         int n;
2265         float len;
2266
2267         copy_v3_v3(grab_delta, ss->cache->grab_delta_symmetry);
2268
2269         len = len_v3(grab_delta);
2270
2271         if (bstrength < 0)
2272                 negate_v3(grab_delta);
2273
2274         if (brush->normal_weight > 0) {
2275                 mul_v3_fl(ss->cache->sculpt_normal_symm, len * brush->normal_weight);
2276                 mul_v3_fl(grab_delta, 1.0f - brush->normal_weight);
2277                 add_v3_v3(grab_delta, ss->cache->sculpt_normal_symm);
2278         }
2279
2280 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2281         for (n = 0; n < totnode; n++) {
2282                 PBVHVertexIter vd;
2283                 SculptBrushTest test;
2284                 float (*proxy)[3];
2285
2286                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2287
2288                 sculpt_brush_test_init(ss, &test);
2289
2290                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2291                 {
2292                         if (sculpt_brush_test(&test, vd.co)) {
2293                                 const float fade = bstrength * tex_strength(ss, brush, vd.co, test.dist,
2294                                                                             vd.no, vd.fno, vd.mask ? *vd.mask : 0.0f);
2295
2296                                 mul_v3_v3fl(proxy[vd.i], grab_delta, fade);
2297
2298                                 if (vd.mvert)
2299                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2300                         }
2301                 }
2302                 BKE_pbvh_vertex_iter_end;
2303         }
2304 }
2305
2306 static void do_thumb_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2307 {
2308         SculptSession *ss = ob->sculpt;
2309         Brush *brush = BKE_paint_brush(&sd->paint);
2310         float bstrength = ss->cache->bstrength;
2311         float grab_delta[3];
2312         float tmp[3], cono[3];
2313         int n;
2314
2315         copy_v3_v3(grab_delta, ss->cache->grab_delta_symmetry);
2316
2317         cross_v3_v3v3(tmp, ss->cache->sculpt_normal_symm, grab_delta);
2318         cross_v3_v3v3(cono, tmp, ss->cache->sculpt_normal_symm);
2319
2320 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2321         for (n = 0; n < totnode; n++) {
2322                 PBVHVertexIter vd;
2323                 SculptBrushTest test;
2324                 SculptOrigVertData orig_data;
2325                 float (*proxy)[3];
2326
2327                 sculpt_orig_vert_data_init(&orig_data, ob, nodes[n]);
2328
2329                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2330
2331                 sculpt_brush_test_init(ss, &test);
2332
2333                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2334                 {
2335                         sculpt_orig_vert_data_update(&orig_data, &vd);
2336
2337                         if (sculpt_brush_test(&test, orig_data.co)) {
2338                                 const float fade = bstrength * tex_strength(ss, brush,
2339                                                                             orig_data.co,
2340                                                                             test.dist,
2341                                                                             orig_data.no,
2342                                                                             NULL, vd.mask ? *vd.mask : 0.0f);
2343
2344                                 mul_v3_v3fl(proxy[vd.i], cono, fade);
2345
2346                                 if (vd.mvert)
2347                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2348                         }
2349                 }
2350                 BKE_pbvh_vertex_iter_end;
2351         }
2352 }
2353
2354 static void do_rotate_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2355 {
2356         SculptSession *ss = ob->sculpt;
2357         Brush *brush = BKE_paint_brush(&sd->paint);
2358         float bstrength = ss->cache->bstrength;
2359         int n;
2360         static const int flip[8] = { 1, -1, -1, 1, -1, 1, 1, -1 };
2361         float angle = ss->cache->vertex_rotation * flip[ss->cache->mirror_symmetry_pass];
2362
2363 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2364         for (n = 0; n < totnode; n++) {
2365                 PBVHVertexIter vd;
2366                 SculptBrushTest test;
2367                 SculptOrigVertData orig_data;
2368                 float (*proxy)[3];
2369
2370                 sculpt_orig_vert_data_init(&orig_data, ob, nodes[n]);
2371
2372                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2373
2374                 sculpt_brush_test_init(ss, &test);
2375
2376                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2377                 {
2378                         sculpt_orig_vert_data_update(&orig_data, &vd);
2379
2380                         if (sculpt_brush_test(&test, orig_data.co)) {
2381                                 float vec[3], rot[3][3];
2382                                 const float fade = bstrength * tex_strength(ss, brush,
2383                                                                             orig_data.co,
2384                                                                             test.dist,
2385                                                                             orig_data.no,
2386                                                                             NULL, vd.mask ? *vd.mask : 0.0f);
2387
2388                                 sub_v3_v3v3(vec, orig_data.co, ss->cache->location);
2389                                 axis_angle_normalized_to_mat3(rot, ss->cache->sculpt_normal_symm, angle * fade);
2390                                 mul_v3_m3v3(proxy[vd.i], rot, vec);
2391                                 add_v3_v3(proxy[vd.i], ss->cache->location);
2392                                 sub_v3_v3(proxy[vd.i], orig_data.co);
2393
2394                                 if (vd.mvert)
2395                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2396                         }
2397                 }
2398                 BKE_pbvh_vertex_iter_end;
2399         }
2400 }
2401
2402 static void do_layer_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2403 {
2404         SculptSession *ss = ob->sculpt;
2405         Brush *brush = BKE_paint_brush(&sd->paint);
2406         float bstrength = ss->cache->bstrength;
2407         float offset[3];
2408         float lim = brush->height;
2409         int n;
2410
2411         if (bstrength < 0)
2412                 lim = -lim;
2413
2414         mul_v3_v3v3(offset, ss->cache->scale, ss->cache->sculpt_normal_symm);
2415
2416 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2417         for (n = 0; n < totnode; n++) {
2418                 PBVHVertexIter vd;
2419                 SculptBrushTest test;
2420                 SculptOrigVertData orig_data;
2421                 float *layer_disp;
2422                 /* XXX: layer brush needs conversion to proxy but its more complicated */
2423                 /* proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co; */
2424                 
2425                 sculpt_orig_vert_data_init(&orig_data, ob, nodes[n]);
2426
2427 #pragma omp critical
2428                 {
2429                         layer_disp = BKE_pbvh_node_layer_disp_get(ss->pbvh, nodes[n]);
2430                 }
2431                 
2432                 sculpt_brush_test_init(ss, &test);
2433
2434                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2435                 {
2436                         sculpt_orig_vert_data_update(&orig_data, &vd);
2437
2438                         if (sculpt_brush_test(&test, orig_data.co)) {
2439                                 const float fade = bstrength * tex_strength(ss, brush, vd.co, test.dist,
2440                                                                             vd.no, vd.fno, vd.mask ? *vd.mask : 0.0f);
2441                                 float *disp = &layer_disp[vd.i];
2442                                 float val[3];
2443
2444                                 *disp += fade;
2445
2446                                 /* Don't let the displacement go past the limit */
2447                                 if ((lim < 0 && *disp < lim) || (lim >= 0 && *disp > lim))
2448                                         *disp = lim;
2449
2450                                 mul_v3_v3fl(val, offset, *disp);
2451
2452                                 if (!ss->multires && !ss->bm && ss->layer_co && (brush->flag & BRUSH_PERSISTENT)) {
2453                                         int index = vd.vert_indices[vd.i];
2454
2455                                         /* persistent base */
2456                                         add_v3_v3(val, ss->layer_co[index]);
2457                                 }
2458                                 else {
2459                                         add_v3_v3(val, orig_data.co);
2460                                 }
2461
2462                                 sculpt_clip(sd, ss, vd.co, val);
2463
2464                                 if (vd.mvert)
2465                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2466                         }
2467                 }
2468                 BKE_pbvh_vertex_iter_end;
2469         }
2470 }
2471
2472 static void do_inflate_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2473 {
2474         SculptSession *ss = ob->sculpt;
2475         Brush *brush = BKE_paint_brush(&sd->paint);
2476         float bstrength = ss->cache->bstrength;
2477         int n;
2478
2479 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2480         for (n = 0; n < totnode; n++) {
2481                 PBVHVertexIter vd;
2482                 SculptBrushTest test;
2483                 float (*proxy)[3];
2484
2485                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2486
2487                 sculpt_brush_test_init(ss, &test);
2488
2489                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2490                 {
2491                         if (sculpt_brush_test(&test, vd.co)) {
2492                                 const float fade = bstrength * tex_strength(ss, brush, vd.co, test.dist,
2493                                                                             vd.no, vd.fno, vd.mask ? *vd.mask : 0.0f);
2494                                 float val[3];
2495
2496                                 if (vd.fno) copy_v3_v3(val, vd.fno);
2497                                 else normal_short_to_float_v3(val, vd.no);
2498                                 
2499                                 mul_v3_fl(val, fade * ss->cache->radius);
2500                                 mul_v3_v3v3(proxy[vd.i], val, ss->cache->scale);
2501
2502                                 if (vd.mvert)
2503                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2504                         }
2505                 }
2506                 BKE_pbvh_vertex_iter_end;
2507         }
2508 }
2509
2510 static void calc_sculpt_plane(
2511         Sculpt *sd, Object *ob,
2512         PBVHNode **nodes, int totnode,
2513         float r_area_no[3], float r_area_co[3])
2514 {
2515         SculptSession *ss = ob->sculpt;
2516         Brush *brush = BKE_paint_brush(&sd->paint);
2517
2518         if (ss->cache->mirror_symmetry_pass == 0 &&
2519             ss->cache->radial_symmetry_pass == 0 &&
2520             (ss->cache->first_time || !(brush->flag & BRUSH_ORIGINAL_NORMAL)))
2521         {
2522                 switch (brush->sculpt_plane) {
2523                         case SCULPT_DISP_DIR_VIEW:
2524                                 copy_v3_v3(r_area_no, ss->cache->true_view_normal);
2525                                 break;
2526
2527                         case SCULPT_DISP_DIR_X:
2528                                 ARRAY_SET_ITEMS(r_area_no, 1, 0, 0);
2529                                 break;
2530
2531                         case SCULPT_DISP_DIR_Y:
2532                                 ARRAY_SET_ITEMS(r_area_no, 0, 1, 0);
2533                                 break;
2534
2535                         case SCULPT_DISP_DIR_Z:
2536                                 ARRAY_SET_ITEMS(r_area_no, 0, 0, 1);
2537                                 break;
2538
2539                         case SCULPT_DISP_DIR_AREA:
2540                                 calc_area_normal_and_center(sd, ob, nodes, totnode, r_area_no, r_area_co);
2541                                 break;
2542
2543                         default:
2544                                 break;
2545                 }
2546
2547                 /* for flatten center */
2548                 /* flatten center has not been calculated yet if we are not using the area normal */
2549                 if (brush->sculpt_plane != SCULPT_DISP_DIR_AREA)
2550                         calc_area_center(sd, ob, nodes, totnode, r_area_co);
2551
2552                 /* for area normal */
2553                 copy_v3_v3(ss->cache->sculpt_normal, r_area_no);
2554
2555                 /* for flatten center */
2556                 copy_v3_v3(ss->cache->last_center, r_area_co);
2557         }
2558         else {
2559                 /* for area normal */
2560                 copy_v3_v3(r_area_no, ss->cache->sculpt_normal);
2561
2562                 /* for flatten center */
2563                 copy_v3_v3(r_area_co, ss->cache->last_center);
2564
2565                 /* for area normal */
2566                 flip_v3(r_area_no, ss->cache->mirror_symmetry_pass);
2567
2568                 /* for flatten center */
2569                 flip_v3(r_area_co, ss->cache->mirror_symmetry_pass);
2570
2571                 /* for area normal */
2572                 mul_m4_v3(ss->cache->symm_rot_mat, r_area_no);
2573
2574                 /* for flatten center */
2575                 mul_m4_v3(ss->cache->symm_rot_mat, r_area_co);
2576         }
2577 }
2578
2579 /* Projects a point onto a plane along the plane's normal */
2580 static void point_plane_project(
2581         float intr[3],
2582         const float co[3], const float plane_normal[3], const float plane_center[3])
2583 {
2584         sub_v3_v3v3(intr, co, plane_center);
2585         mul_v3_v3fl(intr, plane_normal, dot_v3v3(plane_normal, intr));
2586         sub_v3_v3v3(intr, co, intr);
2587 }
2588
2589 static int plane_trim(const StrokeCache *cache, const Brush *brush, const float val[3])
2590 {
2591         return (!(brush->flag & BRUSH_PLANE_TRIM) ||
2592                 ((dot_v3v3(val, val) <= cache->radius_squared * cache->plane_trim_squared)));
2593 }
2594
2595 static bool plane_point_side_flip(
2596         const float co[3], const float plane_normal[3], const float plane_center[3],
2597         const bool flip)
2598 {
2599         float delta[3];
2600         float d;
2601
2602         sub_v3_v3v3(delta, co, plane_center);
2603         d = dot_v3v3(plane_normal, delta);
2604
2605         if (flip) d = -d;
2606
2607         return d <= 0.0f;
2608 }
2609
2610 static int plane_point_side(const float co[3], const float plane_normal[3], const float plane_center[3])
2611 {
2612         float delta[3];
2613
2614         sub_v3_v3v3(delta, co, plane_center);
2615         return dot_v3v3(plane_normal, delta) <= 0.0f;
2616 }
2617
2618 static float get_offset(Sculpt *sd, SculptSession *ss)
2619 {
2620         Brush *brush = BKE_paint_brush(&sd->paint);
2621
2622         float rv = brush->plane_offset;
2623
2624         if (brush->flag & BRUSH_OFFSET_PRESSURE) {
2625                 rv *= ss->cache->pressure;
2626         }
2627
2628         return rv;
2629 }
2630
2631 static void do_flatten_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2632 {
2633         SculptSession *ss = ob->sculpt;
2634         Brush *brush = BKE_paint_brush(&sd->paint);
2635
2636         float bstrength = ss->cache->bstrength;
2637         const float radius = ss->cache->radius;
2638
2639         float area_no[3];
2640         float area_co[3];
2641
2642         float offset = get_offset(sd, ss);
2643
2644         float displace;
2645
2646         int n;
2647
2648         float temp[3];
2649
2650         calc_sculpt_plane(sd, ob, nodes, totnode, area_no, area_co);
2651
2652         displace = radius * offset;
2653
2654         mul_v3_v3v3(temp, area_no, ss->cache->scale);
2655         mul_v3_fl(temp, displace);
2656         add_v3_v3(area_co, temp);
2657
2658 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2659         for (n = 0; n < totnode; n++) {
2660                 PBVHVertexIter vd;
2661                 SculptBrushTest test;
2662                 float (*proxy)[3];
2663
2664                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2665
2666                 sculpt_brush_test_init(ss, &test);
2667
2668                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2669                 {
2670                         if (sculpt_brush_test_sq(&test, vd.co)) {
2671                                 float intr[3];
2672                                 float val[3];
2673
2674                                 point_plane_project(intr, vd.co, area_no, area_co);
2675
2676                                 sub_v3_v3v3(val, intr, vd.co);
2677
2678                                 if (plane_trim(ss->cache, brush, val)) {
2679                                         const float fade = bstrength * tex_strength(ss, brush, vd.co, sqrtf(test.dist),
2680                                                                                     vd.no, vd.fno, vd.mask ? *vd.mask : 0.0f);
2681
2682                                         mul_v3_v3fl(proxy[vd.i], val, fade);
2683
2684                                         if (vd.mvert)
2685                                                 vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2686                                 }
2687                         }
2688                 }
2689                 BKE_pbvh_vertex_iter_end;
2690         }
2691 }
2692
2693 static void do_clay_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2694 {
2695         SculptSession *ss = ob->sculpt;
2696         Brush *brush = BKE_paint_brush(&sd->paint);
2697
2698         float bstrength = ss->cache->bstrength;
2699         float radius    = ss->cache->radius;
2700         float offset    = get_offset(sd, ss);
2701         
2702         float displace;
2703
2704         float area_no[3];
2705         float area_co[3];
2706
2707         int n;
2708
2709         float temp[3];
2710
2711         bool flip;
2712
2713         calc_sculpt_plane(sd, ob, nodes, totnode, area_no, area_co);
2714
2715         flip = bstrength < 0;
2716
2717         if (flip) {
2718                 bstrength = -bstrength;
2719                 radius    = -radius;
2720         }
2721
2722         displace = radius * (0.25f + offset);
2723
2724         mul_v3_v3v3(temp, area_no, ss->cache->scale);
2725         mul_v3_fl(temp, displace);
2726         add_v3_v3(area_co, temp);
2727
2728         /* add_v3_v3v3(p, ss->cache->location, area_no); */
2729
2730 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2731         for (n = 0; n < totnode; n++) {
2732                 PBVHVertexIter vd;
2733                 SculptBrushTest test;
2734                 float (*proxy)[3];
2735
2736                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2737
2738                 sculpt_brush_test_init(ss, &test);
2739
2740                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2741                 {
2742                         if (sculpt_brush_test_sq(&test, vd.co)) {
2743                                 if (plane_point_side_flip(vd.co, area_no, area_co, flip)) {
2744                                         float intr[3];
2745                                         float val[3];
2746
2747                                         point_plane_project(intr, vd.co, area_no, area_co);
2748
2749                                         sub_v3_v3v3(val, intr, vd.co);
2750
2751                                         if (plane_trim(ss->cache, brush, val)) {
2752                                                 /* note, the normal from the vertices is ignored,
2753                                                  * causes glitch with planes, see: T44390 */
2754                                                 const float fade = bstrength * tex_strength(ss, brush, vd.co, sqrtf(test.dist),
2755                                                                                             NULL, area_no, vd.mask ? *vd.mask : 0.0f);
2756
2757                                                 mul_v3_v3fl(proxy[vd.i], val, fade);
2758
2759                                                 if (vd.mvert)
2760                                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2761                                         }
2762                                 }
2763                         }
2764                 }
2765                 BKE_pbvh_vertex_iter_end;
2766         }
2767 }
2768
2769 static void do_clay_strips_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2770 {
2771         SculptSession *ss = ob->sculpt;
2772         Brush *brush = BKE_paint_brush(&sd->paint);
2773
2774         float bstrength = ss->cache->bstrength;
2775         float radius    = ss->cache->radius;
2776         float offset    = get_offset(sd, ss);
2777         
2778         float displace;
2779
2780         float area_no_sp[3];  /* the sculpt-plane normal (whatever its set to) */
2781         float area_no[3];     /* geometry normal */
2782         float area_co[3];
2783
2784         int n;
2785
2786         float temp[3];
2787         float mat[4][4];
2788         float scale[4][4];
2789         float tmat[4][4];
2790
2791         bool flip;
2792
2793         calc_sculpt_plane(sd, ob, nodes, totnode, area_no_sp, area_co);
2794
2795         if (brush->sculpt_plane != SCULPT_DISP_DIR_AREA || (brush->flag & BRUSH_ORIGINAL_NORMAL))
2796                 calc_area_normal(sd, ob, nodes, totnode, area_no);
2797         else
2798                 copy_v3_v3(area_no, area_no_sp);
2799
2800         /* delay the first daub because grab delta is not setup */
2801         if (ss->cache->first_time)
2802                 return;
2803
2804         flip = bstrength < 0;
2805
2806         if (flip) {
2807                 bstrength = -bstrength;
2808                 radius    = -radius;
2809         }
2810
2811         displace = radius * (0.25f + offset);
2812
2813         mul_v3_v3v3(temp, area_no_sp, ss->cache->scale);
2814         mul_v3_fl(temp, displace);
2815         add_v3_v3(area_co, temp);
2816
2817         /* init mat */
2818         cross_v3_v3v3(mat[0], area_no, ss->cache->grab_delta_symmetry);
2819         mat[0][3] = 0;
2820         cross_v3_v3v3(mat[1], area_no, mat[0]);
2821         mat[1][3] = 0;
2822         copy_v3_v3(mat[2], area_no);
2823         mat[2][3] = 0;
2824         copy_v3_v3(mat[3], ss->cache->location);
2825         mat[3][3] = 1;
2826         normalize_m4(mat);
2827
2828         /* scale mat */
2829         scale_m4_fl(scale, ss->cache->radius);
2830         mul_m4_m4m4(tmat, mat, scale);
2831         invert_m4_m4(mat, tmat);
2832
2833 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2834         for (n = 0; n < totnode; n++) {
2835                 PBVHVertexIter vd;
2836                 SculptBrushTest test;
2837                 float (*proxy)[3];
2838
2839                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2840
2841                 sculpt_brush_test_init(ss, &test);
2842
2843                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2844                 {
2845                         if (sculpt_brush_test_cube(&test, vd.co, mat)) {
2846                                 if (plane_point_side_flip(vd.co, area_no_sp, area_co, flip)) {
2847                                         float intr[3];
2848                                         float val[3];
2849
2850                                         point_plane_project(intr, vd.co, area_no_sp, area_co);
2851
2852                                         sub_v3_v3v3(val, intr, vd.co);
2853
2854                                         if (plane_trim(ss->cache, brush, val)) {
2855                                                 /* note, the normal from the vertices is ignored,
2856                                                  * causes glitch with planes, see: T44390 */
2857                                                 const float fade = bstrength * tex_strength(ss, brush, vd.co,
2858                                                                                             ss->cache->radius * test.dist,
2859                                                                                             NULL, area_no, vd.mask ? *vd.mask : 0.0f);
2860
2861                                                 mul_v3_v3fl(proxy[vd.i], val, fade);
2862
2863                                                 if (vd.mvert)
2864                                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2865                                         }
2866                                 }
2867                         }
2868                 }
2869                 BKE_pbvh_vertex_iter_end;
2870         }
2871 }
2872
2873 static void do_fill_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2874 {
2875         SculptSession *ss = ob->sculpt;
2876         Brush *brush = BKE_paint_brush(&sd->paint);
2877
2878         float bstrength = ss->cache->bstrength;
2879         const float radius = ss->cache->radius;
2880
2881         float area_no[3];
2882         float area_co[3];
2883         float offset = get_offset(sd, ss);
2884
2885         float displace;
2886
2887         int n;
2888
2889         float temp[3];
2890
2891         calc_sculpt_plane(sd, ob, nodes, totnode, area_no, area_co);
2892
2893         displace = radius * offset;
2894
2895         mul_v3_v3v3(temp, area_no, ss->cache->scale);
2896         mul_v3_fl(temp, displace);
2897         add_v3_v3(area_co, temp);
2898
2899 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2900         for (n = 0; n < totnode; n++) {
2901                 PBVHVertexIter vd;
2902                 SculptBrushTest test;
2903                 float (*proxy)[3];
2904
2905                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2906
2907                 sculpt_brush_test_init(ss, &test);
2908
2909                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2910                 {
2911                         if (sculpt_brush_test_sq(&test, vd.co)) {
2912                                 if (plane_point_side(vd.co, area_no, area_co)) {
2913                                         float intr[3];
2914                                         float val[3];
2915
2916                                         point_plane_project(intr, vd.co, area_no, area_co);
2917
2918                                         sub_v3_v3v3(val, intr, vd.co);
2919
2920                                         if (plane_trim(ss->cache, brush, val)) {
2921                                                 const float fade = bstrength * tex_strength(ss, brush, vd.co,
2922                                                                                             sqrtf(test.dist),
2923                                                                                             vd.no, vd.fno, vd.mask ? *vd.mask : 0.0f);
2924
2925                                                 mul_v3_v3fl(proxy[vd.i], val, fade);
2926
2927                                                 if (vd.mvert)
2928                                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2929                                         }
2930                                 }
2931                         }
2932                 }
2933                 BKE_pbvh_vertex_iter_end;
2934         }
2935 }
2936
2937 static void do_scrape_brush(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode)
2938 {
2939         SculptSession *ss = ob->sculpt;
2940         Brush *brush = BKE_paint_brush(&sd->paint);
2941
2942         float bstrength = ss->cache->bstrength;
2943         const float radius = ss->cache->radius;
2944
2945         float area_no[3];
2946         float area_co[3];
2947         float offset = get_offset(sd, ss);
2948
2949         float displace;
2950
2951         int n;
2952
2953         float temp[3];
2954
2955         calc_sculpt_plane(sd, ob, nodes, totnode, area_no, area_co);
2956
2957         displace = -radius * offset;
2958
2959         mul_v3_v3v3(temp, area_no, ss->cache->scale);
2960         mul_v3_fl(temp, displace);
2961         add_v3_v3(area_co, temp);
2962
2963 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
2964         for (n = 0; n < totnode; n++) {
2965                 PBVHVertexIter vd;
2966                 SculptBrushTest test;
2967                 float (*proxy)[3];
2968
2969                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
2970
2971                 sculpt_brush_test_init(ss, &test);
2972
2973                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE)
2974                 {
2975                         if (sculpt_brush_test_sq(&test, vd.co)) {
2976                                 if (!plane_point_side(vd.co, area_no, area_co)) {
2977                                         float intr[3];
2978                                         float val[3];
2979
2980                                         point_plane_project(intr, vd.co, area_no, area_co);
2981
2982                                         sub_v3_v3v3(val, intr, vd.co);
2983
2984                                         if (plane_trim(ss->cache, brush, val)) {
2985                                                 const float fade = bstrength * tex_strength(ss, brush, vd.co,
2986                                                                                             sqrtf(test.dist),
2987                                                                                             vd.no, vd.fno, vd.mask ? *vd.mask : 0.0f);
2988
2989                                                 mul_v3_v3fl(proxy[vd.i], val, fade);
2990
2991                                                 if (vd.mvert)
2992                                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
2993                                         }
2994                                 }
2995                         }
2996                 }
2997                 BKE_pbvh_vertex_iter_end;
2998         }
2999 }
3000
3001 static void do_gravity(Sculpt *sd, Object *ob, PBVHNode **nodes, int totnode, float bstrength)
3002 {
3003         SculptSession *ss = ob->sculpt;
3004         Brush *brush = BKE_paint_brush(&sd->paint);
3005
3006         float offset[3]/*, area_no[3]*/;
3007         int n;
3008         float gravity_vector[3];
3009
3010         mul_v3_v3fl(gravity_vector, ss->cache->gravity_direction, -ss->cache->radius_squared);
3011
3012         /* offset with as much as possible factored in already */
3013         mul_v3_v3v3(offset, gravity_vector, ss->cache->scale);
3014         mul_v3_fl(offset, bstrength);
3015
3016         /* threaded loop over nodes */
3017 #pragma omp parallel for schedule(guided) if ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_OMP_LIMIT)
3018         for (n = 0; n < totnode; n++) {
3019                 PBVHVertexIter vd;
3020                 SculptBrushTest test;
3021                 float (*proxy)[3];
3022
3023                 proxy = BKE_pbvh_node_add_proxy(ss->pbvh, nodes[n])->co;
3024
3025                 sculpt_brush_test_init(ss, &test);
3026
3027                 BKE_pbvh_vertex_iter_begin(ss->pbvh, nodes[n], vd, PBVH_ITER_UNIQUE) {
3028                         if (sculpt_brush_test_sq(&test, vd.co)) {
3029                                 const float fade = tex_strength(ss, brush, vd.co, sqrtf(test.dist), vd.no,
3030                                                                 vd.fno, vd.mask ? *vd.mask : 0.0f);
3031
3032                                 mul_v3_v3fl(proxy[vd.i], offset, fade);
3033
3034                                 if (vd.mvert)
3035                                         vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
3036                         }
3037                 }
3038                 BKE_pbvh_vertex_iter_end;
3039         }
3040 }
3041
3042
3043 void sculpt_vertcos_to_key(Object *ob, KeyBlock *kb, float (*vertCos)[3])
3044 {
3045         Mesh *me = (Mesh *)ob->data;
3046         float (*ofs)[3] = NULL;
3047         int a;
3048         const int kb_act_idx = ob->shapenr - 1;
3049         KeyBlock *currkey;
3050
3051         /* for relative keys editing of base should update other keys */
3052         if (BKE_keyblock_is_basis(me->key, kb_act_idx)) {
3053                 ofs = BKE_keyblock_convert_to_vertcos(ob, kb);
3054
3055                 /* calculate key coord offsets (from previous location) */
3056                 for (a = 0; a < me->totvert; a++) {
3057                         sub_v3_v3v3(ofs[a], vertCos[a], ofs[a]);
3058                 }
3059
3060                 /* apply offsets on other keys */
3061                 for (currkey = me->key->block.first; currkey; currkey = currkey->next) {
3062                         if ((currkey != kb) && (currkey->relative == kb_act_idx)) {
3063                                 BKE_keyblock_update_from_offset(ob, currkey, ofs);
3064                         }
3065                 }
3066
3067                 MEM_freeN(ofs);
3068         }
3069
3070         /* modifying of basis key should update mesh */
3071         if (kb == me->key->refkey) {
3072                 MVert *mvert = me->mvert;
3073
3074                 for (a = 0; a < me->totvert; a++, mvert++)
3075                         copy_v3_v3(mvert->co, vertCos[a]);
3076
3077                 BKE_mesh_calc_normals(me);
3078         }
3079
3080         /* apply new coords on active key block, no need to re-allocate kb->data here! */
3081         BKE_keyblock_update_from_vertcos(ob, kb, vertCos);
3082 }
3083
3084 /* Note: we do the topology update before any brush actions to avoid
3085  * issues with the proxies. The size of the proxy can't change, so
3086  * topology must be updated first. */
3087 static void sculpt_topology_update(Sculpt *sd, Object *ob, Brush *brush, UnifiedPaintSettings *UNUSED(ups))
3088 {
3089         SculptSession *ss = ob->sculpt;
3090         SculptSearchSphereData data;
3091         PBVHNode **nodes = NULL;
3092         float radius;
3093         int n, totnode;
3094
3095         /* Build a list of all nodes that are potentially within the
3096          * brush's area of influence */
3097         data.ss = ss;
3098         data.sd = sd;
3099
3100         radius = ss->cache->radius * 1.25f;
3101
3102         data.radius_squared = radius * radius;
3103         data.original = ELEM(brush->sculpt_tool,
3104                              SCULPT_TOOL_GRAB,
3105                              SCULPT_TOOL_ROTATE,