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