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