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