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