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