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