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