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