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