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