Sculpt Branch:
[blender.git] / source / blender / editors / sculpt_paint / sculpt.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software  Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2006 by Nicholas Bishop
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  *
29  * Implements the Sculpt Mode tools
30  *
31  */
32
33 #include "MEM_guardedalloc.h"
34
35 #include "BLI_math.h"
36 #include "BLI_blenlib.h"
37 #include "BLI_dynstr.h"
38 #include "BLI_ghash.h"
39 #include "BLI_pbvh.h"
40 #include "BLI_threads.h"
41
42 #include "DNA_armature_types.h"
43 #include "DNA_brush_types.h"
44 #include "DNA_image_types.h"
45 #include "DNA_key_types.h"
46 #include "DNA_mesh_types.h"
47 #include "DNA_meshdata_types.h"
48 #include "DNA_modifier_types.h"
49 #include "DNA_object_types.h"
50 #include "DNA_screen_types.h"
51 #include "DNA_scene_types.h"
52 #include "DNA_texture_types.h"
53 #include "DNA_view3d_types.h"
54 #include "DNA_userdef_types.h"
55 #include "DNA_color_types.h"
56
57 #include "BKE_brush.h"
58 #include "BKE_cdderivedmesh.h"
59 #include "BKE_context.h"
60 #include "BKE_customdata.h"
61 #include "BKE_DerivedMesh.h"
62 #include "BKE_depsgraph.h"
63 #include "BKE_global.h"
64 #include "BKE_image.h"
65 #include "BKE_key.h"
66 #include "BKE_library.h"
67 #include "BKE_main.h"
68 #include "BKE_mesh.h"
69 #include "BKE_modifier.h"
70 #include "BKE_multires.h"
71 #include "BKE_paint.h"
72 #include "BKE_report.h"
73 #include "BKE_texture.h"
74 #include "BKE_utildefines.h"
75 #include "BKE_colortools.h"
76
77 #include "BIF_gl.h"
78 #include "BIF_glutil.h"
79
80 #include "WM_api.h"
81 #include "WM_types.h"
82 #include "ED_object.h"
83 #include "ED_screen.h"
84 #include "ED_sculpt.h"
85 #include "ED_space_api.h"
86 #include "ED_util.h"
87 #include "ED_view3d.h"
88 #include "paint_intern.h"
89 #include "sculpt_intern.h"
90
91 #include "RNA_access.h"
92 #include "RNA_define.h"
93
94 #include "IMB_imbuf_types.h"
95
96 #include "RE_render_ext.h"
97 #include "RE_shader_ext.h" /*for multitex_ext*/
98
99 #include "GPU_draw.h"
100 #include "gpu_buffers.h"
101
102 #include <math.h>
103 #include <stdlib.h>
104 #include <string.h>
105
106 /* Number of vertices to average in order to determine the flatten distance */
107 #define FLATTEN_SAMPLE_SIZE 10
108
109 /* ===== STRUCTS =====
110  *
111  */
112
113 typedef enum StrokeFlags {
114         CLIP_X = 1,
115         CLIP_Y = 2,
116         CLIP_Z = 4
117 } StrokeFlags;
118
119 /* Cache stroke properties. Used because
120    RNA property lookup isn't particularly fast.
121
122    For descriptions of these settings, check the operator properties.
123 */
124 typedef struct StrokeCache {
125         /* Invariants */
126         float initial_radius;
127         float scale[3];
128         int flag;
129         float clip_tolerance[3];
130         float initial_mouse[2];
131
132         /* Variants */
133         float radius;
134         float true_location[3];
135         float location[3];
136         float flip;
137         float pressure;
138         float mouse[2];
139         float bstrength;
140         float tex_mouse[2];
141
142         /* The rest is temporary storage that isn't saved as a property */
143
144         int first_time; /* Beginning of stroke may do some things special */
145
146         bglMats *mats;
147
148         /* Clean this up! */
149         ViewContext *vc;
150         Brush *brush;
151
152         float (*face_norms)[3]; /* Copy of the mesh faces' normals */
153         float rotation; /* Texture rotation (radians) for anchored and rake modes */
154         int pixel_radius, previous_pixel_radius;
155         PBVHNode **grab_active_nodes[8]; /* The same list of nodes is used throught grab stroke */
156         int grab_active_totnode[8];
157         float grab_active_location[8][3];
158         float grab_delta[3], grab_delta_symmetry[3];
159         float old_grab_location[3], orig_grab_location[3];
160         int symmetry; /* Symmetry index between 0 and 7 */
161         float view_normal[3], view_normal_symmetry[3];
162         int last_rake[2]; /* Last location of updating rake rotation */
163         int original;
164 } StrokeCache;
165
166 /* ===== OPENGL =====
167  *
168  * Simple functions to get data from the GL
169  */
170
171 /* Convert a point in model coordinates to 2D screen coordinates. */
172 static void projectf(bglMats *mats, const float v[3], float p[2])
173 {
174         double ux, uy, uz;
175
176         gluProject(v[0],v[1],v[2], mats->modelview, mats->projection,
177                    (GLint *)mats->viewport, &ux, &uy, &uz);
178         p[0]= ux;
179         p[1]= uy;
180 }
181
182 /*XXX: static void project(bglMats *mats, const float v[3], short p[2])
183 {
184         float f[2];
185         projectf(mats, v, f);
186
187         p[0]= f[0];
188         p[1]= f[1];
189 }
190 */
191
192 /*** BVH Tree ***/
193
194 /* Get a screen-space rectangle of the modified area */
195 int sculpt_get_redraw_rect(ARegion *ar, RegionView3D *rv3d,
196                             Object *ob, rcti *rect)
197 {
198         float bb_min[3], bb_max[3], pmat[4][4];
199         int i, j, k;
200
201         view3d_get_object_project_mat(rv3d, ob, pmat);
202
203         BLI_pbvh_redraw_BB(ob->sculpt->tree, bb_min, bb_max);
204
205         rect->xmin = rect->ymin = INT_MAX;
206         rect->xmax = rect->ymax = INT_MIN;
207
208         if(bb_min[0] > bb_max[0] || bb_min[1] > bb_max[1] || bb_min[2] > bb_max[2])
209                 return 0;
210
211         for(i = 0; i < 2; ++i) {
212                 for(j = 0; j < 2; ++j) {
213                         for(k = 0; k < 2; ++k) {
214                                 float vec[3], proj[2];
215                                 vec[0] = i ? bb_min[0] : bb_max[0];
216                                 vec[1] = j ? bb_min[1] : bb_max[1];
217                                 vec[2] = k ? bb_min[2] : bb_max[2];
218                                 view3d_project_float(ar, vec, proj, pmat);
219                                 rect->xmin = MIN2(rect->xmin, proj[0]);
220                                 rect->xmax = MAX2(rect->xmax, proj[0]);
221                                 rect->ymin = MIN2(rect->ymin, proj[1]);
222                                 rect->ymax = MAX2(rect->ymax, proj[1]);
223                         }
224                 }
225         }
226         
227         return rect->xmin < rect->xmax && rect->ymin < rect->ymax;
228 }
229
230 void sculpt_get_redraw_planes(float planes[4][4], ARegion *ar,
231                               RegionView3D *rv3d, Object *ob)
232 {
233         BoundBox *bb = MEM_callocN(sizeof(BoundBox), "sculpt boundbox");
234         bglMats mats;
235         int i;
236         rcti rect;
237
238         view3d_get_transformation(ar, rv3d, ob, &mats);
239         sculpt_get_redraw_rect(ar, rv3d,ob, &rect);
240
241 #if 1
242         /* use some extra space just in case */
243         rect.xmin -= 2;
244         rect.xmax += 2;
245         rect.ymin -= 2;
246         rect.ymax += 2;
247 #else
248         /* it was doing this before, allows to redraw a smaller
249            part of the screen but also gives artifaces .. */
250         rect.xmin += 2;
251         rect.xmax -= 2;
252         rect.ymin += 2;
253         rect.ymax -= 2;
254 #endif
255
256         view3d_calculate_clipping(bb, planes, &mats, &rect);
257
258         for(i = 0; i < 16; ++i)
259                 ((float*)planes)[i] = -((float*)planes)[i];
260
261         MEM_freeN(bb);
262
263         /* clear redraw flag from nodes */
264         BLI_pbvh_update(ob->sculpt->tree, PBVH_UpdateRedraw, NULL);
265 }
266
267 /************************** Undo *************************/
268
269 typedef struct SculptUndoNode {
270         struct SculptUndoNode *next, *prev;
271
272         char idname[MAX_ID_NAME];       /* name instead of pointer*/
273         void *node;                                     /* only during push, not valid afterwards! */
274
275         float (*co)[3];
276         short (*no)[3];
277         int totvert;
278
279         /* non-multires */
280         int maxvert;                            /* to verify if totvert it still the same */
281         int *index;                                     /* to restore into right location */
282
283         /* multires */
284         int maxgrid;                            /* same for grid */
285         int gridsize;                           /* same for grid */
286         int totgrid;                            /* to restore into right location */
287         int *grids;                                     /* to restore into right location */
288 } SculptUndoNode;
289
290 static void update_cb(PBVHNode *node, void *data)
291 {
292         BLI_pbvh_node_mark_update(node);
293 }
294
295 static void sculpt_undo_restore(bContext *C, ListBase *lb)
296 {
297         Object *ob = CTX_data_active_object(C);
298         DerivedMesh *dm = mesh_get_derived_final(CTX_data_scene(C), ob, 0);
299         SculptSession *ss = ob->sculpt;
300         SculptUndoNode *unode;
301         MVert *mvert;
302         MultiresModifierData *mmd;
303         int *index;
304         int i, j, update= 0;
305
306         sculpt_update_mesh_elements(C, 0);
307
308         for(unode=lb->first; unode; unode=unode->next) {
309                 if(!(strcmp(unode->idname, ob->id.name)==0))
310                         continue;
311
312                 if(unode->maxvert) {
313                         /* regular mesh restore */
314                         if(ss->totvert != unode->maxvert)
315                                 continue;
316
317                         index= unode->index;
318                         mvert= ss->mvert;
319
320                         for(i=0; i<unode->totvert; i++) {
321                                 swap_v3_v3(mvert[index[i]].co, unode->co[i]);
322                                 mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
323                         }
324                 }
325                 else if(unode->maxgrid) {
326                         /* multires restore */
327                         DMGridData **grids, *grid;
328                         float (*co)[3];
329                         int gridsize;
330
331                         if(dm->getNumGrids(dm) != unode->maxgrid)
332                                 continue;
333                         if(dm->getGridSize(dm) != unode->gridsize)
334                                 continue;
335
336                         grids= dm->getGridData(dm);
337                         gridsize= dm->getGridSize(dm);
338
339                         co = unode->co;
340                         for(j=0; j<unode->totgrid; j++) {
341                                 grid= grids[unode->grids[j]];
342
343                                 for(i=0; i<gridsize*gridsize; i++, co++)
344                                         swap_v3_v3(grid[i].co, co[0]);
345                         }
346                 }
347
348                 update= 1;
349         }
350
351         if(update) {
352                 /* we update all nodes still, should be more clever, but also
353                    needs to work correct when exiting/entering sculpt mode and
354                    the nodes get recreated, though in that case it could do all */
355                 BLI_pbvh_search_callback(ss->tree, NULL, NULL, update_cb, NULL);
356                 BLI_pbvh_update(ss->tree, PBVH_UpdateBB|PBVH_UpdateOriginalBB|PBVH_UpdateRedraw, NULL);
357
358                 if((mmd=sculpt_multires_active(ob)))
359                         multires_mark_as_modified(ob);
360         }
361 }
362
363 static void sculpt_undo_free(ListBase *lb)
364 {
365         SculptUndoNode *unode;
366
367         for(unode=lb->first; unode; unode=unode->next) {
368                 if(unode->co)
369                         MEM_freeN(unode->co);
370                 if(unode->no)
371                         MEM_freeN(unode->no);
372                 if(unode->index)
373                         MEM_freeN(unode->index);
374                 if(unode->grids)
375                         MEM_freeN(unode->grids);
376         }
377 }
378
379 static SculptUndoNode *sculpt_undo_get_node(SculptSession *ss, PBVHNode *node)
380 {
381         ListBase *lb= undo_paint_push_get_list(UNDO_PAINT_MESH);
382         SculptUndoNode *unode;
383
384         if(!lb)
385                 return NULL;
386
387         for(unode=lb->first; unode; unode=unode->next)
388                 if(unode->node == node)
389                         return unode;
390
391         return NULL;
392 }
393
394 static SculptUndoNode *sculpt_undo_push_node(SculptSession *ss, PBVHNode *node)
395 {
396         ListBase *lb= undo_paint_push_get_list(UNDO_PAINT_MESH);
397         Object *ob= ss->ob;
398         SculptUndoNode *unode;
399         int totvert, allvert, totgrid, maxgrid, gridsize, *grids;
400
401         /* list is manipulated by multiple threads, so we lock */
402         BLI_lock_thread(LOCK_CUSTOM1);
403
404         if((unode= sculpt_undo_get_node(ss, node))) {
405                 BLI_unlock_thread(LOCK_CUSTOM1);
406                 return unode;
407         }
408
409         unode= MEM_callocN(sizeof(SculptUndoNode), "SculptUndoNode");
410         strcpy(unode->idname, ob->id.name);
411         unode->node= node;
412
413         BLI_pbvh_node_num_verts(ss->tree, node, &totvert, &allvert);
414         BLI_pbvh_node_get_grids(ss->tree, node, &grids, &totgrid, &maxgrid, &gridsize);
415
416         unode->totvert= totvert;
417         /* we will use this while sculpting, is mapalloc slow to access then? */
418         unode->co= MEM_mapallocN(sizeof(float)*3*allvert, "SculptUndoNode.co");
419         unode->no= MEM_mapallocN(sizeof(short)*3*allvert, "SculptUndoNode.no");
420         undo_paint_push_count_alloc(UNDO_PAINT_MESH, (sizeof(float)*3 + sizeof(short)*3 + sizeof(int))*allvert);
421         BLI_addtail(lb, unode);
422
423         if(maxgrid) {
424                 /* multires */
425                 unode->maxgrid= maxgrid;
426                 unode->totgrid= totgrid;
427                 unode->gridsize= gridsize;
428                 unode->grids= MEM_mapallocN(sizeof(int)*totgrid, "SculptUndoNode.grids");
429         }
430         else {
431                 /* regular mesh */
432                 unode->maxvert= ss->totvert;
433                 unode->index= MEM_mapallocN(sizeof(int)*allvert, "SculptUndoNode.index");
434         }
435
436         BLI_unlock_thread(LOCK_CUSTOM1);
437
438         /* copy threaded, hopefully this is the performance critical part */
439         {
440                 PBVHVertexIter vd;
441
442                 BLI_pbvh_vertex_iter_begin(ss->tree, node, vd, PBVH_ITER_ALL) {
443                         copy_v3_v3(unode->co[vd.i], vd.co);
444                         if(vd.no) VECCOPY(unode->no[vd.i], vd.no)
445                         else normal_float_to_short_v3(unode->no[vd.i], vd.fno);
446                         if(vd.vert_indices) unode->index[vd.i]= vd.vert_indices[vd.i];
447                 }
448                 BLI_pbvh_vertex_iter_end;
449         }
450
451         if(unode->grids)
452                 memcpy(unode->grids, grids, sizeof(int)*totgrid);
453         
454         return unode;
455 }
456
457 static void sculpt_undo_push_begin(SculptSession *ss, char *name)
458 {
459         undo_paint_push_begin(UNDO_PAINT_MESH, name,
460                 sculpt_undo_restore, sculpt_undo_free);
461 }
462
463 static void sculpt_undo_push_end(SculptSession *ss)
464 {
465         ListBase *lb= undo_paint_push_get_list(UNDO_PAINT_MESH);
466         SculptUndoNode *unode;
467
468         /* we don't need normals in the undo stack */
469         for(unode=lb->first; unode; unode=unode->next) {
470                 if(unode->no) {
471                         MEM_freeN(unode->no);
472                         unode->no= NULL;
473                 }
474         }
475
476         undo_paint_push_end(UNDO_PAINT_MESH);
477 }
478
479 void ED_sculpt_force_update(bContext *C)
480 {
481         Object *ob= CTX_data_active_object(C);
482
483         if(ob && (ob->mode & OB_MODE_SCULPT))
484                 multires_force_update(ob);
485 }
486
487 /************************ Brush Testing *******************/
488
489 typedef struct SculptBrushTest {
490         float radius_squared;
491         float location[3];
492
493         float dist;
494 } SculptBrushTest;
495
496 static void sculpt_brush_test_init(SculptSession *ss, SculptBrushTest *test)
497 {
498         test->radius_squared= ss->cache->radius*ss->cache->radius;
499         copy_v3_v3(test->location, ss->cache->location);
500 }
501
502 static int sculpt_brush_test(SculptBrushTest *test, float co[3])
503 {
504         float distsq, delta[3];
505
506         sub_v3_v3v3(delta, co, test->location);
507         distsq = INPR(delta, delta);
508
509         if(distsq < test->radius_squared) {
510                 test->dist = sqrt(distsq);
511                 return 1;
512         }
513
514         return 0;
515 }
516
517 /* ===== Sculpting =====
518  *
519  */
520
521 /* Return modified brush strength. Includes the direction of the brush, positive
522    values pull vertices, negative values push. Uses tablet pressure and a
523    special multiplier found experimentally to scale the strength factor. */
524 static float brush_strength(Sculpt *sd, StrokeCache *cache)
525 {
526         Brush *brush = paint_brush(&sd->paint);
527         /* Primary strength input; square it to make lower values more sensitive */
528         float alpha = brush->alpha * brush->alpha;
529
530         float dir= brush->flag & BRUSH_DIR_IN ? -1 : 1;
531         float pressure= 1;
532         float flip= cache->flip ? -1:1;
533
534         if(brush->flag & BRUSH_ALPHA_PRESSURE)
535                 pressure *= cache->pressure;
536         
537         switch(brush->sculpt_tool){
538         case SCULPT_TOOL_DRAW:
539         case SCULPT_TOOL_INFLATE:
540         case SCULPT_TOOL_CLAY:
541         case SCULPT_TOOL_FLATTEN:
542         case SCULPT_TOOL_LAYER:
543                 return alpha * dir * pressure * flip; /*XXX: not sure why? was multiplied by G.vd->grid */;
544         case SCULPT_TOOL_SMOOTH:
545                 return alpha * 4 * pressure;
546         case SCULPT_TOOL_PINCH:
547                 return alpha / 2 * dir * pressure * flip;
548         case SCULPT_TOOL_GRAB:
549                 return 1;
550         default:
551                 return 0;
552         }
553 }
554
555 /* Uses symm to selectively flip any axis of a coordinate. */
556 static void flip_coord(float out[3], float in[3], const char symm)
557 {
558         if(symm & SCULPT_SYMM_X)
559                 out[0]= -in[0];
560         else
561                 out[0]= in[0];
562         if(symm & SCULPT_SYMM_Y)
563                 out[1]= -in[1];
564         else
565                 out[1]= in[1];
566         if(symm & SCULPT_SYMM_Z)
567                 out[2]= -in[2];
568         else
569                 out[2]= in[2];
570 }
571
572 /* Get a pixel from the texcache at (px, py) */
573 static unsigned char get_texcache_pixel(const SculptSession *ss, int px, int py)
574 {
575         unsigned *p;
576         p = ss->texcache + py * ss->texcache_side + px;
577         return ((unsigned char*)(p))[0];
578 }
579
580 static float get_texcache_pixel_bilinear(const SculptSession *ss, float u, float v)
581 {
582         int x, y, x2, y2;
583         const int tc_max = ss->texcache_side - 1;
584         float urat, vrat, uopp;
585
586         if(u < 0) u = 0;
587         else if(u >= ss->texcache_side) u = tc_max;
588         if(v < 0) v = 0;
589         else if(v >= ss->texcache_side) v = tc_max;
590
591         x = floor(u);
592         y = floor(v);
593         x2 = x + 1;
594         y2 = y + 1;
595
596         if(x2 > ss->texcache_side) x2 = tc_max;
597         if(y2 > ss->texcache_side) y2 = tc_max;
598         
599         urat = u - x;
600         vrat = v - y;
601         uopp = 1 - urat;
602                 
603         return ((get_texcache_pixel(ss, x, y) * uopp +
604                  get_texcache_pixel(ss, x2, y) * urat) * (1 - vrat) + 
605                 (get_texcache_pixel(ss, x, y2) * uopp +
606                  get_texcache_pixel(ss, x2, y2) * urat) * vrat) / 255.0;
607 }
608
609 /* Return a multiplier for brush strength on a particular vertex. */
610 static float tex_strength(SculptSession *ss, Brush *br, float *point, const float len)
611 {
612         MTex *tex = NULL;
613         float avg= 1;
614
615         if(br->texact >= 0)
616                 tex = br->mtex[br->texact];
617
618         if(!tex) {
619                 avg= 1;
620         }
621         else if(tex->brush_map_mode == MTEX_MAP_MODE_3D) {
622                 float jnk;
623
624                 /* Get strength by feeding the vertex 
625                    location directly into a texture */
626                 externtex(tex, point, &avg,
627                           &jnk, &jnk, &jnk, &jnk);
628         }
629         else if(ss->texcache) {
630                 const float bsize= ss->cache->pixel_radius * 2;
631                 const float rot= tex->rot + ss->cache->rotation;
632                 int px, py;
633                 float flip[3], point_2d[2];
634
635                 /* If the active area is being applied for symmetry, flip it
636                    across the symmetry axis in order to project it. This insures
637                    that the brush texture will be oriented correctly. */
638                 copy_v3_v3(flip, point);
639                 flip_coord(flip, flip, ss->cache->symmetry);
640                 projectf(ss->cache->mats, flip, point_2d);
641
642                 /* For Tile and Drag modes, get the 2D screen coordinates of the
643                    and scale them up or down to the texture size. */
644                 if(tex->brush_map_mode == MTEX_MAP_MODE_TILED) {
645                         const int sx= (const int)tex->size[0];
646                         const int sy= (const int)tex->size[1];
647                         
648                         float fx= point_2d[0];
649                         float fy= point_2d[1];
650                         
651                         float angle= atan2(fy, fx) - rot;
652                         float flen= sqrtf(fx*fx + fy*fy);
653                         
654                         if(rot<0.001 && rot>-0.001) {
655                                 px= point_2d[0];
656                                 py= point_2d[1];
657                         } else {
658                                 px= flen * cos(angle) + 2000;
659                                 py= flen * sin(angle) + 2000;
660                         }
661                         if(sx != 1)
662                                 px %= sx-1;
663                         if(sy != 1)
664                                 py %= sy-1;
665                         avg= get_texcache_pixel_bilinear(ss, ss->texcache_side*px/sx, ss->texcache_side*py/sy);
666                 }
667                 else if(tex->brush_map_mode == MTEX_MAP_MODE_FIXED) {
668                         float fx= (point_2d[0] - ss->cache->tex_mouse[0]) / bsize;
669                         float fy= (point_2d[1] - ss->cache->tex_mouse[1]) / bsize;
670
671                         float angle= atan2(fy, fx) - rot;
672                         float flen= sqrtf(fx*fx + fy*fy);
673                         
674                         fx = flen * cos(angle) + 0.5;
675                         fy = flen * sin(angle) + 0.5;
676
677                         avg= get_texcache_pixel_bilinear(ss, fx * ss->texcache_side, fy * ss->texcache_side);
678                 }
679         }
680
681         avg*= brush_curve_strength(br, len, ss->cache->radius); /* Falloff curve */
682
683         return avg;
684 }
685
686 typedef struct {
687         Sculpt *sd;
688         SculptSession *ss;
689         float radius_squared;
690         ListBase *active_verts;
691         float area_normal[3];
692 } SculptSearchSphereData;
693
694 /* Test AABB against sphere */
695 static int sculpt_search_sphere_cb(PBVHNode *node, void *data_v)
696 {
697         SculptSearchSphereData *data = data_v;
698         float *center = data->ss->cache->location, nearest[3];
699         float t[3], bb_min[3], bb_max[3];
700         int i;
701
702         BLI_pbvh_node_get_BB(node, bb_min, bb_max);
703
704         for(i = 0; i < 3; ++i) {
705                 if(bb_min[i] > center[i])
706                         nearest[i] = bb_min[i];
707                 else if(bb_max[i] < center[i])
708                         nearest[i] = bb_max[i];
709                 else
710                         nearest[i] = center[i]; 
711         }
712         
713         sub_v3_v3v3(t, center, nearest);
714
715         return t[0] * t[0] + t[1] * t[1] + t[2] * t[2] < data->radius_squared;
716 }
717
718 /* Handles clipping against a mirror modifier and SCULPT_LOCK axis flags */
719 static void sculpt_clip(Sculpt *sd, SculptSession *ss, float *co, const float val[3])
720 {
721         int i;
722
723         for(i=0; i<3; ++i) {
724                 if(sd->flags & (SCULPT_LOCK_X << i))
725                         continue;
726
727                 if((ss->cache->flag & (CLIP_X << i)) && (fabs(co[i]) <= ss->cache->clip_tolerance[i]))
728                         co[i]= 0.0f;
729                 else
730                         co[i]= val[i];
731         }               
732 }
733
734 static void add_norm_if(float view_vec[3], float out[3], float out_flip[3], float fno[3])
735 {
736         if((dot_v3v3(view_vec, fno)) > 0) {
737                 add_v3_v3v3(out, out, fno);
738         } else {
739                 add_v3_v3v3(out_flip, out_flip, fno); /* out_flip is used when out is {0,0,0} */
740         }
741 }
742
743 /* For draw/layer/flatten; finds average normal for all active vertices */
744 static void calc_area_normal(Sculpt *sd, SculptSession *ss, float area_normal[3], PBVHNode **nodes, int totnode)
745 {
746         PBVH *bvh= ss->tree;
747         StrokeCache *cache = ss->cache;
748         const int view = 0; /* XXX: should probably be a flag, not number: brush_type==SCULPT_TOOL_DRAW ? sculptmode_brush()->view : 0; */
749         float out[3] = {0.0f, 0.0f, 0.0f};
750         float out_flip[3] = {0.0f, 0.0f, 0.0f};
751         float out_dir[3];
752         int n;
753
754         copy_v3_v3(out_dir, cache->view_normal_symmetry);
755
756         /* threaded loop over nodes */
757         #pragma omp parallel for private(n) schedule(static)
758         for(n=0; n<totnode; n++) {
759                 PBVHVertexIter vd;
760                 SculptBrushTest test;
761                 SculptUndoNode *unode;
762                 float fno[3];
763                 float nout[3] = {0.0f, 0.0f, 0.0f};
764                 float nout_flip[3] = {0.0f, 0.0f, 0.0f};
765                 
766                 // XXX push instead of get for thread safety in draw
767                 // brush .. lame, but also not harmful really
768                 unode= sculpt_undo_push_node(ss, nodes[n]);
769                 sculpt_brush_test_init(ss, &test);
770
771                 if(ss->cache->original) {
772                         BLI_pbvh_vertex_iter_begin(bvh, nodes[n], vd, PBVH_ITER_UNIQUE) {
773                                 if(sculpt_brush_test(&test, unode->co[vd.i])) {
774                                         normal_short_to_float_v3(fno, unode->no[vd.i]);
775                                         add_norm_if(out_dir, nout, nout_flip, fno);
776                                 }
777                         }
778                         BLI_pbvh_vertex_iter_end;
779                 }
780                 else {
781                         BLI_pbvh_vertex_iter_begin(bvh, nodes[n], vd, PBVH_ITER_UNIQUE) {
782                                 if(sculpt_brush_test(&test, vd.co)) {
783                                         if(vd.no) {
784                                                 normal_short_to_float_v3(fno, vd.no);
785                                                 add_norm_if(out_dir, nout, nout_flip, fno);
786                                         }
787                                         else
788                                                 add_norm_if(out_dir, nout, nout_flip, vd.fno);
789                                 }
790                         }
791                         BLI_pbvh_vertex_iter_end;
792                 }
793
794                 {
795                         /* we sum per node and add together later for threads */
796                         #pragma omp critical
797                         add_v3_v3v3(out, out, nout);
798                         add_v3_v3v3(out_flip, out_flip, nout_flip);
799                 }
800         }
801
802         if (out[0]==0.0 && out[1]==0.0 && out[2]==0.0) {
803                 copy_v3_v3(out, out_flip);
804         }
805         
806         normalize_v3(out);
807
808         out[0] = out_dir[0] * view + out[0] * (10-view);
809         out[1] = out_dir[1] * view + out[1] * (10-view);
810         out[2] = out_dir[2] * view + out[2] * (10-view);
811         
812         normalize_v3(out);
813         copy_v3_v3(area_normal, out);
814 }
815
816 static void do_draw_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
817 {
818         Brush *brush = paint_brush(&sd->paint);
819         float offset[3], area_normal[3];
820         float bstrength= ss->cache->bstrength;
821         int n;
822
823         /* area normal */
824         calc_area_normal(sd, ss, area_normal, nodes, totnode);
825
826         /* offset with as much as possible factored in already */
827         offset[0]= area_normal[0]*ss->cache->radius*ss->cache->scale[0]*bstrength;
828         offset[1]= area_normal[1]*ss->cache->radius*ss->cache->scale[1]*bstrength;
829         offset[2]= area_normal[2]*ss->cache->radius*ss->cache->scale[2]*bstrength;
830
831         /* threaded loop over nodes */
832         #pragma omp parallel for private(n) schedule(static)
833         for(n=0; n<totnode; n++) {
834                 PBVHVertexIter vd;
835                 SculptBrushTest test;
836                 
837                 sculpt_undo_push_node(ss, nodes[n]);
838                 sculpt_brush_test_init(ss, &test);
839
840                 BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
841                         if(sculpt_brush_test(&test, vd.co)) {
842                                 /* offset vertex */
843                                 float fade = tex_strength(ss, brush, vd.co, test.dist);
844                                 float val[3]= {vd.co[0] + offset[0]*fade,
845                                                            vd.co[1] + offset[1]*fade,
846                                                            vd.co[2] + offset[2]*fade};
847
848                                 sculpt_clip(sd, ss, vd.co, val);
849                                 if(vd.mvert) vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
850                         }
851                 }
852                 BLI_pbvh_vertex_iter_end;
853
854                 BLI_pbvh_node_mark_update(nodes[n]);
855         }
856 }
857
858 /* For the smooth brush, uses the neighboring vertices around vert to calculate
859    a smoothed location for vert. Skips corner vertices (used by only one
860    polygon.) */
861 static void neighbor_average(SculptSession *ss, float avg[3], const int vert)
862 {
863         int i, skip= -1, total=0;
864         IndexNode *node= ss->fmap[vert].first;
865         char ncount= BLI_countlist(&ss->fmap[vert]);
866         MFace *f;
867
868         avg[0] = avg[1] = avg[2] = 0;
869                 
870         /* Don't modify corner vertices */
871         if(ncount==1) {
872                 copy_v3_v3(avg, ss->mvert[vert].co);
873                 return;
874         }
875
876         while(node){
877                 f= &ss->mface[node->index];
878                 
879                 if(f->v4) {
880                         skip= (f->v1==vert?2:
881                                f->v2==vert?3:
882                                f->v3==vert?0:
883                                f->v4==vert?1:-1);
884                 }
885
886                 for(i=0; i<(f->v4?4:3); ++i) {
887                         if(i != skip && (ncount!=2 || BLI_countlist(&ss->fmap[(&f->v1)[i]]) <= 2)) {
888                                 add_v3_v3v3(avg, avg, ss->mvert[(&f->v1)[i]].co);
889                                 ++total;
890                         }
891                 }
892
893                 node= node->next;
894         }
895
896         if(total>0)
897                 mul_v3_fl(avg, 1.0f / total);
898         else
899                 copy_v3_v3(avg, ss->mvert[vert].co);
900 }
901
902 static void do_smooth_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
903 {
904         Brush *brush = paint_brush(&sd->paint);
905         float bstrength= ss->cache->bstrength;
906         int iteration, n;
907
908         for(iteration = 0; iteration < 2; ++iteration) {
909                 #pragma omp parallel for private(n) schedule(static)
910                 for(n=0; n<totnode; n++) {
911                         PBVHVertexIter vd;
912                         SculptBrushTest test;
913                         
914                         sculpt_undo_push_node(ss, nodes[n]);
915                         sculpt_brush_test_init(ss, &test);
916
917                         BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
918                                 if(sculpt_brush_test(&test, vd.co)) {
919                                         float fade = tex_strength(ss, brush, vd.co, test.dist)*bstrength;
920                                         float avg[3], val[3];
921                                         
922                                         neighbor_average(ss, avg, vd.vert_indices[vd.i]);
923                                         val[0] = vd.co[0]+(avg[0]-vd.co[0])*fade;
924                                         val[1] = vd.co[1]+(avg[1]-vd.co[1])*fade;
925                                         val[2] = vd.co[2]+(avg[2]-vd.co[2])*fade;
926                                         
927                                         sculpt_clip(sd, ss, vd.co, val);                        
928                                         if(vd.mvert) vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
929                                 }
930                         }
931                         BLI_pbvh_vertex_iter_end;
932
933                         BLI_pbvh_node_mark_update(nodes[n]);
934                 }
935         }
936 }
937
938 static void do_pinch_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
939 {
940         Brush *brush = paint_brush(&sd->paint);
941         float bstrength= ss->cache->bstrength;
942         int n;
943
944         #pragma omp parallel for private(n) schedule(static)
945         for(n=0; n<totnode; n++) {
946                 PBVHVertexIter vd;
947                 SculptBrushTest test;
948                 
949                 sculpt_undo_push_node(ss, nodes[n]);
950                 sculpt_brush_test_init(ss, &test);
951
952                 BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
953                         if(sculpt_brush_test(&test, vd.co)) {
954                                 float fade = tex_strength(ss, brush, vd.co, test.dist)*bstrength;
955                                 float val[3]= {vd.co[0]+(test.location[0]-vd.co[0])*fade,
956                                                            vd.co[1]+(test.location[1]-vd.co[1])*fade,
957                                                            vd.co[2]+(test.location[2]-vd.co[2])*fade};
958                                 
959                                 sculpt_clip(sd, ss, vd.co, val);                        
960                                 if(vd.mvert) vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
961                         }
962                 }
963                 BLI_pbvh_vertex_iter_end;
964
965                 BLI_pbvh_node_mark_update(nodes[n]);
966         }
967 }
968
969 static void do_grab_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
970 {
971         Brush *brush = paint_brush(&sd->paint);
972         float bstrength= ss->cache->bstrength;
973         float grab_delta[3];
974         int n;
975         
976         copy_v3_v3(grab_delta, ss->cache->grab_delta_symmetry);
977
978         #pragma omp parallel for private(n) schedule(static)
979         for(n=0; n<totnode; n++) {
980                 PBVHVertexIter vd;
981                 SculptBrushTest test;
982                 float (*origco)[3];
983                 
984                 origco= sculpt_undo_push_node(ss, nodes[n])->co;
985                 sculpt_brush_test_init(ss, &test);
986
987                 BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
988                         if(sculpt_brush_test(&test, origco[vd.i])) {
989                                 float fade = tex_strength(ss, brush, origco[vd.i], test.dist)*bstrength;
990                                 float add[3]= {vd.co[0]+fade*grab_delta[0],
991                                                            vd.co[1]+fade*grab_delta[1],
992                                                            vd.co[2]+fade*grab_delta[2]};
993
994                                 sculpt_clip(sd, ss, vd.co, add);                        
995                                 if(vd.mvert) vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
996                         }
997                 }
998                 BLI_pbvh_vertex_iter_end;
999
1000                 BLI_pbvh_node_mark_update(nodes[n]);
1001         }
1002
1003 }
1004
1005 static void do_layer_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
1006 {
1007         Brush *brush = paint_brush(&sd->paint);
1008         float bstrength= ss->cache->bstrength;
1009         float area_normal[3], offset[3];
1010         float lim= ss->cache->radius / 4;
1011         int n;
1012
1013         if(ss->cache->flip)
1014                 lim = -lim;
1015
1016         calc_area_normal(sd, ss, area_normal, nodes, totnode);
1017
1018         offset[0]= ss->cache->scale[0]*area_normal[0];
1019         offset[1]= ss->cache->scale[1]*area_normal[1];
1020         offset[2]= ss->cache->scale[2]*area_normal[2];
1021
1022         #pragma omp parallel for private(n) schedule(static)
1023         for(n=0; n<totnode; n++) {
1024                 PBVHVertexIter vd;
1025                 SculptBrushTest test;
1026                 float (*origco)[3];
1027                 
1028                 origco= sculpt_undo_push_node(ss, nodes[n])->co;
1029                 sculpt_brush_test_init(ss, &test);
1030
1031                 BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
1032                         if(sculpt_brush_test(&test, vd.co)) {
1033                                 float fade = tex_strength(ss, brush, vd.co, test.dist)*bstrength;
1034                                 int index= vd.vert_indices[vd.i];
1035                                 float *disp= &ss->layer_disps[index];
1036                                 float val[3];
1037                                 
1038                                 *disp+= fade;
1039                                 
1040                                 /* Don't let the displacement go past the limit */
1041                                 if((lim < 0 && *disp < lim) || (lim > 0 && *disp > lim))
1042                                         *disp = lim;
1043                                 
1044                                 if(ss->layer_co && (brush->flag & BRUSH_PERSISTENT)) {
1045                                         /* persistent base */
1046                                         val[0] = ss->layer_co[index][0] + (*disp)*offset[0];
1047                                         val[1] = ss->layer_co[index][1] + (*disp)*offset[1];
1048                                         val[2] = ss->layer_co[index][2] + (*disp)*offset[2];
1049                                 }
1050                                 else {
1051                                         val[0] = origco[vd.i][0] + (*disp)*offset[0];
1052                                         val[1] = origco[vd.i][1] + (*disp)*offset[1];
1053                                         val[2] = origco[vd.i][2] + (*disp)*offset[2];
1054                                 }
1055
1056                                 sculpt_clip(sd, ss, vd.co, val);
1057                                 if(vd.mvert) vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
1058                         }
1059                 }
1060                 BLI_pbvh_vertex_iter_end;
1061
1062                 BLI_pbvh_node_mark_update(nodes[n]);
1063         }
1064 }
1065
1066 static void do_inflate_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
1067 {
1068         Brush *brush = paint_brush(&sd->paint);
1069         float bstrength= ss->cache->bstrength;
1070         int n;
1071
1072         #pragma omp parallel for private(n) schedule(static)
1073         for(n=0; n<totnode; n++) {
1074                 PBVHVertexIter vd;
1075                 SculptBrushTest test;
1076                 
1077                 sculpt_undo_push_node(ss, nodes[n]);
1078                 sculpt_brush_test_init(ss, &test);
1079
1080                 BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
1081                         if(sculpt_brush_test(&test, vd.co)) {
1082                                 float fade = tex_strength(ss, brush, vd.co, test.dist)*bstrength;
1083                                 float add[3];
1084                                 
1085                                 add[0]= vd.no[0]/32767.0f;
1086                                 add[1]= vd.no[1]/32767.0f;
1087                                 add[2]= vd.no[2]/32767.0f;
1088                                 mul_v3_fl(add, fade * ss->cache->radius);
1089                                 add[0]*= ss->cache->scale[0];
1090                                 add[1]*= ss->cache->scale[1];
1091                                 add[2]*= ss->cache->scale[2];
1092                                 add_v3_v3v3(add, add, vd.co);
1093                                 
1094                                 sculpt_clip(sd, ss, vd.co, add);
1095                                 if(vd.mvert) vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
1096                         }
1097                 }
1098                 BLI_pbvh_vertex_iter_end;
1099
1100                 BLI_pbvh_node_mark_update(nodes[n]);
1101         }
1102 }
1103
1104 static void calc_flatten_center(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode, float co[3])
1105 {
1106         float outer_dist[FLATTEN_SAMPLE_SIZE];
1107         float outer_co[FLATTEN_SAMPLE_SIZE][3];
1108         int i, n;
1109         
1110         for(i = 0; i < FLATTEN_SAMPLE_SIZE; ++i) {
1111                 zero_v3(outer_co[i]);
1112                 outer_dist[i]= -1.0f;
1113         }
1114                 
1115         #pragma omp parallel for private(n) schedule(static)
1116         for(n=0; n<totnode; n++) {
1117                 PBVHVertexIter vd;
1118                 SculptBrushTest test;
1119                 
1120                 sculpt_undo_push_node(ss, nodes[n]);
1121                 sculpt_brush_test_init(ss, &test);
1122
1123                 BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
1124                         if(sculpt_brush_test(&test, vd.co)) {
1125                                 for(i = 0; i < FLATTEN_SAMPLE_SIZE; ++i) {
1126                                         if(test.dist > outer_dist[i]) {
1127                                                 copy_v3_v3(outer_co[i], vd.co);
1128                                                 outer_dist[i] = test.dist;
1129                                                 break;
1130                                         }
1131                                 }
1132                         }
1133                 }
1134                 BLI_pbvh_vertex_iter_end;
1135
1136                 BLI_pbvh_node_mark_update(nodes[n]);
1137         }
1138         
1139         co[0] = co[1] = co[2] = 0.0f;
1140         for(i = 0; i < FLATTEN_SAMPLE_SIZE; ++i)
1141                 if(outer_dist[i] >= 0.0f)
1142                         add_v3_v3v3(co, co, outer_co[i]);
1143         mul_v3_fl(co, 1.0f / FLATTEN_SAMPLE_SIZE);
1144 }
1145
1146 /* Projects a point onto a plane along the plane's normal */
1147 static void point_plane_project(float intr[3], float co[3], float plane_normal[3], float plane_center[3])
1148 {
1149         float p1[3], sub1[3], sub2[3];
1150
1151         /* Find the intersection between squash-plane and vertex (along the area normal) */
1152         sub_v3_v3v3(p1, co, plane_normal);
1153         sub_v3_v3v3(sub1, plane_center, p1);
1154         sub_v3_v3v3(sub2, co, p1);
1155         sub_v3_v3v3(intr, co, p1);
1156         mul_v3_fl(intr, dot_v3v3(plane_normal, sub1) / dot_v3v3(plane_normal, sub2));
1157         add_v3_v3v3(intr, intr, p1);
1158 }
1159
1160 static int plane_point_side(float co[3], float plane_normal[3], float plane_center[3], int flip)
1161 {
1162         float delta[3];
1163         float d;
1164
1165         sub_v3_v3v3(delta, co, plane_center);
1166         d = dot_v3v3(plane_normal, delta);
1167
1168         if(flip)
1169                 d = -d;
1170
1171         return d <= 0.0f;
1172 }
1173
1174 static void do_flatten_clay_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode, int clay)
1175 {
1176         /* area_normal and cntr define the plane towards which vertices are squashed */
1177         Brush *brush = paint_brush(&sd->paint);
1178         float bstrength= ss->cache->bstrength;
1179         float area_normal[3];
1180         float cntr[3], cntr2[3], bstr = 0;
1181         int n, flip = 0;
1182
1183         calc_area_normal(sd, ss, area_normal, nodes, totnode);
1184         calc_flatten_center(sd, ss, nodes, totnode, cntr);
1185
1186         if(clay) {
1187                 bstr= brush_strength(sd, ss->cache);
1188                 /* Limit clay application to here */
1189                 cntr2[0]=cntr[0]+area_normal[0]*bstr*ss->cache->scale[0];
1190                 cntr2[1]=cntr[1]+area_normal[1]*bstr*ss->cache->scale[1];
1191                 cntr2[2]=cntr[2]+area_normal[2]*bstr*ss->cache->scale[2];
1192                 flip = bstr < 0;
1193         }
1194
1195         #pragma omp parallel for private(n) schedule(static)
1196         for(n=0; n<totnode; n++) {
1197                 PBVHVertexIter vd;
1198                 SculptBrushTest test;
1199                 
1200                 sculpt_undo_push_node(ss, nodes[n]);
1201                 sculpt_brush_test_init(ss, &test);
1202
1203                 BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
1204                         if(sculpt_brush_test(&test, vd.co)) {
1205                                 float intr[3], val[3];
1206                                 
1207                                 if(!clay || plane_point_side(vd.co, area_normal, cntr2, flip)) {
1208                                         const float fade = tex_strength(ss, brush, vd.co, test.dist)*bstrength;
1209
1210                                         /* Find the intersection between squash-plane and vertex (along the area normal) */             
1211                                         point_plane_project(intr, vd.co, area_normal, cntr);
1212
1213                                         sub_v3_v3v3(val, intr, vd.co);
1214
1215                                         if(clay) {
1216                                                 if(bstr > FLT_EPSILON)
1217                                                         mul_v3_fl(val, fade / bstr);
1218                                                 else
1219                                                         mul_v3_fl(val, fade);
1220                                                 /* Clay displacement */
1221                                                 val[0]+=area_normal[0] * ss->cache->scale[0]*fade;
1222                                                 val[1]+=area_normal[1] * ss->cache->scale[1]*fade;
1223                                                 val[2]+=area_normal[2] * ss->cache->scale[2]*fade;
1224                                         }
1225                                         else
1226                                                 mul_v3_fl(val, fabs(fade));
1227
1228                                         add_v3_v3v3(val, val, vd.co);
1229
1230                                         sculpt_clip(sd, ss, vd.co, val);
1231                                         if(vd.mvert) vd.mvert->flag |= ME_VERT_PBVH_UPDATE;
1232                                 }
1233                         }
1234                 }
1235                 BLI_pbvh_vertex_iter_end;
1236
1237                 BLI_pbvh_node_mark_update(nodes[n]);
1238         }
1239 }
1240
1241 static void do_brush_action(Sculpt *sd, SculptSession *ss, StrokeCache *cache)
1242 {
1243         SculptSearchSphereData data;
1244         Brush *brush = paint_brush(&sd->paint);
1245         //KeyBlock *keyblock= NULL; /*XXX: ob_get_keyblock(OBACT); */
1246         PBVHNode **nodes= NULL;
1247         int totnode;
1248
1249         data.ss = ss;
1250         data.sd = sd;
1251         data.radius_squared = ss->cache->radius * ss->cache->radius;
1252
1253         /* Build a list of all nodes that are potentially within the brush's
1254            area of influence */
1255         if(brush->sculpt_tool == SCULPT_TOOL_GRAB) {
1256                 if(cache->first_time) {
1257                         /* For the grab tool we store these nodes once in the beginning
1258                            and then reuse them. */
1259                         BLI_pbvh_search_gather(ss->tree, sculpt_search_sphere_cb, &data,
1260                                 &nodes, &totnode);
1261                         
1262                         ss->cache->grab_active_nodes[ss->cache->symmetry]= nodes;
1263                         ss->cache->grab_active_totnode[ss->cache->symmetry]= totnode;
1264                         copy_v3_v3(ss->cache->grab_active_location[ss->cache->symmetry], ss->cache->location);
1265                 }
1266                 else {
1267                         nodes= ss->cache->grab_active_nodes[ss->cache->symmetry];
1268                         totnode= ss->cache->grab_active_totnode[ss->cache->symmetry];
1269                         copy_v3_v3(ss->cache->location, ss->cache->grab_active_location[ss->cache->symmetry]);
1270                 }
1271         }
1272         else {
1273                 BLI_pbvh_search_gather(ss->tree, sculpt_search_sphere_cb, &data,
1274                         &nodes, &totnode);
1275         }
1276
1277         /* Only act if some verts are inside the brush area */
1278         if(totnode) {
1279                 /* Apply one type of brush action */
1280                 switch(brush->sculpt_tool){
1281                 case SCULPT_TOOL_DRAW:
1282                         do_draw_brush(sd, ss, nodes, totnode);
1283                         break;
1284                 case SCULPT_TOOL_SMOOTH:
1285                         do_smooth_brush(sd, ss, nodes, totnode);
1286                         break;
1287                 case SCULPT_TOOL_PINCH:
1288                         do_pinch_brush(sd, ss, nodes, totnode);
1289                         break;
1290                 case SCULPT_TOOL_INFLATE:
1291                         do_inflate_brush(sd, ss, nodes, totnode);
1292                         break;
1293                 case SCULPT_TOOL_GRAB:
1294                         do_grab_brush(sd, ss, nodes, totnode);
1295                         break;
1296                 case SCULPT_TOOL_LAYER:
1297                         do_layer_brush(sd, ss, nodes, totnode);
1298                         break;
1299                 case SCULPT_TOOL_FLATTEN:
1300                         do_flatten_clay_brush(sd, ss, nodes, totnode, 0);
1301                         break;
1302                 case SCULPT_TOOL_CLAY:
1303                         do_flatten_clay_brush(sd, ss, nodes, totnode, 1);
1304                         break;
1305                 }
1306         
1307 #if 0
1308                 /* Copy the modified vertices from mesh to the active key */
1309                 if(ss->kb) mesh_to_key(ss->ob->data, ss->kb);
1310
1311                                 for(; adata; adata= adata->next)
1312                                         if(adata->Index < keyblock->totelem)
1313                                                 copy_v3_v3(&co[adata->Index*3], me->mvert[adata->Index].co);
1314                         }
1315                 }
1316
1317                 if(ss->vertexcosnos && !ss->multires)
1318                         BLI_freelistN(&active_verts);
1319                 else {
1320                         if(b->sculpt_tool != SCULPT_TOOL_GRAB)
1321                                 addlisttolist(&ss->modified_verts, &active_verts);
1322                 }
1323 #endif
1324                 
1325                 if((brush->sculpt_tool != SCULPT_TOOL_GRAB) && nodes)
1326                         MEM_freeN(nodes);
1327         }       
1328 }
1329
1330 /* Flip all the editdata across the axis/axes specified by symm. Used to
1331    calculate multiple modifications to the mesh when symmetry is enabled. */
1332 static void calc_brushdata_symm(StrokeCache *cache, const char symm)
1333 {
1334         flip_coord(cache->location, cache->true_location, symm);
1335         flip_coord(cache->view_normal_symmetry, cache->view_normal, symm);
1336         flip_coord(cache->grab_delta_symmetry, cache->grab_delta, symm);
1337         cache->symmetry= symm;
1338 }
1339
1340 static void do_symmetrical_brush_actions(Sculpt *sd, SculptSession *ss)
1341 {
1342         StrokeCache *cache = ss->cache;
1343         const char symm = sd->flags & 7;
1344         int i;
1345
1346         copy_v3_v3(cache->location, cache->true_location);
1347         copy_v3_v3(cache->grab_delta_symmetry, cache->grab_delta);
1348         cache->symmetry = 0;
1349         cache->bstrength = brush_strength(sd, cache);
1350         do_brush_action(sd, ss, cache);
1351
1352         for(i = 1; i <= symm; ++i) {
1353                 if(symm & i && (symm != 5 || i != 3) && (symm != 6 || (i != 3 && i != 5))) {
1354                         calc_brushdata_symm(cache, i);
1355                         do_brush_action(sd, ss, cache);
1356                 }
1357         }
1358
1359         cache->first_time = 0;
1360 }
1361
1362 static void sculpt_update_tex(Sculpt *sd, SculptSession *ss)
1363 {
1364         Brush *brush = paint_brush(&sd->paint);
1365
1366         if(ss->texcache) {
1367                 MEM_freeN(ss->texcache);
1368                 ss->texcache= NULL;
1369         }
1370
1371         /* Need to allocate a bigger buffer for bigger brush size */
1372         ss->texcache_side = brush->size * 2;
1373         if(!ss->texcache || ss->texcache_side > ss->texcache_actual) {
1374                 ss->texcache = brush_gen_texture_cache(brush, brush->size);
1375                 ss->texcache_actual = ss->texcache_side;
1376         }
1377 }
1378
1379 /* Checks whether full update mode (slower) needs to be used to work with modifiers */
1380 char sculpt_modifiers_active(Object *ob)
1381 {
1382         ModifierData *md;
1383         
1384         for(md= modifiers_getVirtualModifierList(ob); md; md= md->next) {
1385                 if(modifier_isEnabled(md, eModifierMode_Realtime) && md->type != eModifierType_Multires)
1386                         return 1;
1387         }
1388         
1389         return 0;
1390 }
1391
1392 /* Sculpt mode handles multires differently from regular meshes, but only if
1393    it's the last modifier on the stack and it is not on the first level */
1394 struct MultiresModifierData *sculpt_multires_active(Object *ob)
1395 {
1396         ModifierData *md, *nmd;
1397         
1398         for(md= modifiers_getVirtualModifierList(ob); md; md= md->next) {
1399                 if(md->type == eModifierType_Multires) {
1400                         MultiresModifierData *mmd= (MultiresModifierData*)md;
1401
1402                         /* Check if any of the modifiers after multires are active
1403                          * if not it can use the multires struct */
1404                         for (nmd= md->next; nmd; nmd= nmd->next)
1405                                 if(nmd->mode & eModifierMode_Realtime)
1406                                         break;
1407
1408                         if(!nmd && mmd->lvl != 1)
1409                                 return mmd;
1410                 }
1411         }
1412
1413         return NULL;
1414 }
1415
1416 void sculpt_update_mesh_elements(bContext *C, int need_fmap)
1417 {
1418         Object *ob = CTX_data_active_object(C);
1419         DerivedMesh *dm = mesh_get_derived_final(CTX_data_scene(C), ob, 0);
1420         SculptSession *ss = ob->sculpt;
1421         
1422         ss->ob= ob;
1423
1424         if((ss->multires = sculpt_multires_active(ob))) {
1425                 ss->totvert = dm->getNumVerts(dm);
1426                 ss->totface = dm->getNumFaces(dm);
1427                 ss->mvert = dm->getVertDataArray(dm, CD_MVERT);
1428                 ss->mface = dm->getFaceDataArray(dm, CD_MFACE);
1429                 ss->face_normals = dm->getFaceDataArray(dm, CD_NORMAL);
1430         }
1431         else {
1432                 Mesh *me = get_mesh(ob);
1433                 ss->totvert = me->totvert;
1434                 ss->totface = me->totface;
1435                 ss->mvert = me->mvert;
1436                 ss->mface = me->mface;
1437                 ss->face_normals = NULL;
1438         }
1439
1440         ss->ob = ob;
1441         ss->tree = dm->getPBVH(ob, dm);
1442         ss->fmap = (need_fmap)? dm->getFaceMap(dm): NULL;
1443
1444         if((ob->shapeflag & OB_SHAPE_LOCK) && !sculpt_multires_active(ob)) {
1445                 ss->kb= ob_get_keyblock(ob);
1446                 ss->refkb= ob_get_reference_keyblock(ob);
1447         }
1448         else {
1449                 ss->kb= NULL;
1450                 ss->refkb= NULL;
1451         }
1452 }
1453
1454 static int sculpt_mode_poll(bContext *C)
1455 {
1456         Object *ob = CTX_data_active_object(C);
1457         return ob && ob->mode & OB_MODE_SCULPT;
1458 }
1459
1460 int sculpt_poll(bContext *C)
1461 {
1462         return sculpt_mode_poll(C) && paint_poll(C);
1463 }
1464
1465 static char *sculpt_tool_name(Sculpt *sd)
1466 {
1467         Brush *brush = paint_brush(&sd->paint);
1468
1469         switch(brush->sculpt_tool) {
1470         case SCULPT_TOOL_DRAW:
1471                 return "Draw Brush"; break;
1472         case SCULPT_TOOL_SMOOTH:
1473                 return "Smooth Brush"; break;
1474         case SCULPT_TOOL_PINCH:
1475                 return "Pinch Brush"; break;
1476         case SCULPT_TOOL_INFLATE:
1477                 return "Inflate Brush"; break;
1478         case SCULPT_TOOL_GRAB:
1479                 return "Grab Brush"; break;
1480         case SCULPT_TOOL_LAYER:
1481                 return "Layer Brush"; break;
1482         case SCULPT_TOOL_FLATTEN:
1483                 return "Flatten Brush"; break;
1484         default:
1485                 return "Sculpting"; break;
1486         }
1487 }
1488
1489 /**** Radial control ****/
1490 static int sculpt_radial_control_invoke(bContext *C, wmOperator *op, wmEvent *event)
1491 {
1492         Paint *p = paint_get_active(CTX_data_scene(C));
1493         Brush *brush = paint_brush(p);
1494
1495         WM_paint_cursor_end(CTX_wm_manager(C), p->paint_cursor);
1496         p->paint_cursor = NULL;
1497         brush_radial_control_invoke(op, brush, 1);
1498         return WM_radial_control_invoke(C, op, event);
1499 }
1500
1501 static int sculpt_radial_control_modal(bContext *C, wmOperator *op, wmEvent *event)
1502 {
1503         int ret = WM_radial_control_modal(C, op, event);
1504         if(ret != OPERATOR_RUNNING_MODAL)
1505                 paint_cursor_start(C, sculpt_poll);
1506         return ret;
1507 }
1508
1509 static int sculpt_radial_control_exec(bContext *C, wmOperator *op)
1510 {
1511         Brush *brush = paint_brush(&CTX_data_tool_settings(C)->sculpt->paint);
1512         int ret = brush_radial_control_exec(op, brush, 1);
1513
1514         WM_event_add_notifier(C, NC_BRUSH|NA_EDITED, brush);
1515
1516         return ret;
1517 }
1518
1519 static void SCULPT_OT_radial_control(wmOperatorType *ot)
1520 {
1521         WM_OT_radial_control_partial(ot);
1522
1523         ot->name= "Sculpt Radial Control";
1524         ot->idname= "SCULPT_OT_radial_control";
1525
1526         ot->invoke= sculpt_radial_control_invoke;
1527         ot->modal= sculpt_radial_control_modal;
1528         ot->exec= sculpt_radial_control_exec;
1529         ot->poll= sculpt_poll;
1530
1531         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO|OPTYPE_BLOCKING;
1532 }
1533
1534 /**** Operator for applying a stroke (various attributes including mouse path)
1535       using the current brush. ****/
1536
1537 static float unproject_brush_radius(ViewContext *vc, float center[3], float offset)
1538 {
1539         float delta[3];
1540
1541         initgrabz(vc->rv3d, center[0], center[1], center[2]);
1542         window_to_3d_delta(vc->ar, delta, offset, 0);
1543         return len_v3(delta);
1544 }
1545
1546 static void sculpt_cache_free(StrokeCache *cache)
1547 {
1548         int i;
1549         if(cache->face_norms)
1550                 MEM_freeN(cache->face_norms);
1551         if(cache->mats)
1552                 MEM_freeN(cache->mats);
1553         for(i = 0; i < 8; ++i) {
1554                 if(cache->grab_active_nodes[i])
1555                         MEM_freeN(cache->grab_active_nodes[i]);
1556         }
1557         MEM_freeN(cache);
1558 }
1559
1560 /* Initialize the stroke cache invariants from operator properties */
1561 static void sculpt_update_cache_invariants(Sculpt *sd, SculptSession *ss, bContext *C, wmOperator *op)
1562 {
1563         StrokeCache *cache = MEM_callocN(sizeof(StrokeCache), "stroke cache");
1564         Brush *brush = paint_brush(&sd->paint);
1565         ViewContext *vc = paint_stroke_view_context(op->customdata);
1566         int i;
1567
1568         ss->cache = cache;
1569
1570         RNA_float_get_array(op->ptr, "scale", cache->scale);
1571         cache->flag = RNA_int_get(op->ptr, "flag");
1572         RNA_float_get_array(op->ptr, "clip_tolerance", cache->clip_tolerance);
1573         RNA_float_get_array(op->ptr, "initial_mouse", cache->initial_mouse);
1574
1575         copy_v2_v2(cache->mouse, cache->initial_mouse);
1576         copy_v2_v2(cache->tex_mouse, cache->initial_mouse);
1577
1578         /* Truly temporary data that isn't stored in properties */
1579
1580         cache->vc = vc;
1581         cache->brush = brush;
1582
1583         cache->mats = MEM_callocN(sizeof(bglMats), "sculpt bglMats");
1584         view3d_get_transformation(vc->ar, vc->rv3d, vc->obact, cache->mats);
1585
1586         /* Initialize layer brush displacements and persistent coords */
1587         if(brush->sculpt_tool == SCULPT_TOOL_LAYER) {
1588                 if(!ss->layer_disps || !(brush->flag & BRUSH_PERSISTENT)) {
1589                         if(ss->layer_disps)
1590                                 MEM_freeN(ss->layer_disps);
1591                         ss->layer_disps = MEM_callocN(sizeof(float) * ss->totvert, "layer brush displacements");
1592                 }
1593                 if(!ss->layer_co && (brush->flag & BRUSH_PERSISTENT)) {
1594                         if(!ss->layer_co)
1595                                 ss->layer_co= MEM_mallocN(sizeof(float) * 3 * ss->totvert,
1596                                                                        "sculpt mesh vertices copy");
1597                         for(i = 0; i < ss->totvert; ++i)
1598                                 copy_v3_v3(ss->layer_co[i], ss->mvert[i].co);
1599                 }
1600         }
1601
1602         /* Make copies of the mesh vertex locations and normals for some tools */
1603         if(brush->flag & BRUSH_ANCHORED) {
1604                 if(ss->face_normals) {
1605                         float *fn = ss->face_normals;
1606                         cache->face_norms= MEM_mallocN(sizeof(float) * 3 * ss->totface, "Sculpt face norms");
1607                         for(i = 0; i < ss->totface; ++i, fn += 3)
1608                                 copy_v3_v3(cache->face_norms[i], fn);
1609                 }
1610
1611                 cache->original = 1;
1612         }
1613
1614         if(ELEM3(brush->sculpt_tool, SCULPT_TOOL_DRAW, SCULPT_TOOL_LAYER, SCULPT_TOOL_INFLATE))
1615                 if(!(brush->flag & BRUSH_ACCUMULATE))
1616                         cache->original = 1;
1617
1618         cache->rotation = 0;
1619         cache->first_time = 1;
1620 }
1621
1622 /* Initialize the stroke cache variants from operator properties */
1623 static void sculpt_update_cache_variants(Sculpt *sd, SculptSession *ss, struct PaintStroke *stroke, PointerRNA *ptr)
1624 {
1625         StrokeCache *cache = ss->cache;
1626         Brush *brush = paint_brush(&sd->paint);
1627         
1628         int dx, dy;
1629
1630         if(!(brush->flag & BRUSH_ANCHORED) || cache->first_time)
1631                 RNA_float_get_array(ptr, "location", cache->true_location);
1632         cache->flip = RNA_boolean_get(ptr, "flip");
1633         RNA_float_get_array(ptr, "mouse", cache->mouse);
1634         cache->pressure = RNA_float_get(ptr, "pressure");
1635         
1636         /* Truly temporary data that isn't stored in properties */
1637
1638         cache->previous_pixel_radius = cache->pixel_radius;
1639         cache->pixel_radius = brush->size;
1640
1641         if(cache->first_time)
1642                 cache->initial_radius = unproject_brush_radius(cache->vc, cache->true_location, brush->size);
1643
1644         if(brush->flag & BRUSH_SIZE_PRESSURE) {
1645                 cache->pixel_radius *= cache->pressure;
1646                 cache->radius = cache->initial_radius * cache->pressure;
1647         }
1648         else
1649                 cache->radius = cache->initial_radius;
1650
1651         if(!(brush->flag & BRUSH_ANCHORED))
1652                 copy_v2_v2(cache->tex_mouse, cache->mouse);
1653
1654         if(brush->flag & BRUSH_ANCHORED) {
1655                 dx = cache->mouse[0] - cache->initial_mouse[0];
1656                 dy = cache->mouse[1] - cache->initial_mouse[1];
1657                 cache->pixel_radius = sqrt(dx*dx + dy*dy);
1658                 cache->radius = unproject_brush_radius(paint_stroke_view_context(stroke),
1659                                                        cache->true_location, cache->pixel_radius);
1660                 cache->rotation = atan2(dy, dx);
1661         }
1662         else if(brush->flag & BRUSH_RAKE) {
1663                 int update;
1664
1665                 dx = cache->last_rake[0] - cache->mouse[0];
1666                 dy = cache->last_rake[1] - cache->mouse[1];
1667
1668                 update = dx*dx + dy*dy > 100;
1669
1670                 /* To prevent jitter, only update the angle if the mouse has moved over 10 pixels */
1671                 if(update && !cache->first_time)
1672                         cache->rotation = M_PI_2 + atan2(dy, dx);
1673
1674                 if(update || cache->first_time) {
1675                         cache->last_rake[0] = cache->mouse[0];
1676                         cache->last_rake[1] = cache->mouse[1];
1677                 }
1678         }
1679
1680         /* Find the grab delta */
1681         if(brush->sculpt_tool == SCULPT_TOOL_GRAB) {
1682                 float grab_location[3];
1683
1684                 if(cache->first_time)
1685                         copy_v3_v3(cache->orig_grab_location, cache->true_location);
1686
1687                 initgrabz(cache->vc->rv3d, cache->orig_grab_location[0], cache->orig_grab_location[1], cache->orig_grab_location[2]);
1688                 window_to_3d_delta(cache->vc->ar, grab_location, cache->mouse[0], cache->mouse[1]);
1689
1690                 if(!cache->first_time)
1691                         sub_v3_v3v3(cache->grab_delta, grab_location, cache->old_grab_location);
1692                 copy_v3_v3(cache->old_grab_location, grab_location);
1693         }
1694 }
1695
1696 typedef struct {
1697         SculptSession *ss;
1698         float *ray_start, *ray_normal;
1699         int hit;
1700         float dist;
1701         int original;
1702 } SculptRaycastData;
1703
1704 void sculpt_raycast_cb(PBVHNode *node, void *data_v)
1705 {
1706         SculptRaycastData *srd = data_v;
1707         float (*origco)[3]= NULL;
1708
1709         if(srd->original && srd->ss->cache) {
1710                 /* intersect with coordinates from before we started stroke */
1711                 SculptUndoNode *unode= sculpt_undo_get_node(srd->ss, node);
1712                 origco= (unode)? unode->co: NULL;
1713         }
1714
1715         srd->hit |= BLI_pbvh_node_raycast(srd->ss->tree, node, origco,
1716                 srd->ray_start, srd->ray_normal, &srd->dist);
1717 }
1718
1719 /* Do a raycast in the tree to find the 3d brush location
1720    (This allows us to ignore the GL depth buffer)
1721    Returns 0 if the ray doesn't hit the mesh, non-zero otherwise
1722  */
1723 int sculpt_stroke_get_location(bContext *C, struct PaintStroke *stroke, float out[3], float mouse[2])
1724 {
1725         ViewContext *vc = paint_stroke_view_context(stroke);
1726         SculptSession *ss= vc->obact->sculpt;
1727         StrokeCache *cache= ss->cache;
1728         float ray_start[3], ray_normal[3];
1729         float obimat[4][4];
1730         float mval[2] = {mouse[0] - vc->ar->winrct.xmin,
1731                          mouse[1] - vc->ar->winrct.ymin};
1732         SculptRaycastData srd;
1733
1734         viewray(vc->ar, vc->v3d, mval, ray_start, ray_normal);
1735
1736         invert_m4_m4(obimat, ss->ob->obmat);
1737         mul_m4_v3(obimat, ray_start);
1738         mul_mat3_m4_v3(obimat, ray_normal);
1739
1740         srd.ss = vc->obact->sculpt;
1741         srd.ray_start = ray_start;
1742         srd.ray_normal = ray_normal;
1743         srd.dist = FLT_MAX;
1744         srd.hit = 0;
1745         srd.original = (cache)? cache->original: 0;
1746         BLI_pbvh_raycast(ss->tree, sculpt_raycast_cb, &srd,
1747                      ray_start, ray_normal, srd.original);
1748         
1749         copy_v3_v3(out, ray_normal);
1750         mul_v3_fl(out, srd.dist);
1751         add_v3_v3v3(out, out, ray_start);
1752
1753         return srd.hit;
1754 }
1755
1756 /* Initialize stroke operator properties */
1757 static void sculpt_brush_stroke_init_properties(bContext *C, wmOperator *op, wmEvent *event, SculptSession *ss)
1758 {
1759         Object *ob= CTX_data_active_object(C);
1760         ModifierData *md;
1761         float scale[3], clip_tolerance[3] = {0,0,0};
1762         float mouse[2];
1763         int flag = 0;
1764
1765         /* Set scaling adjustment */
1766         scale[0] = 1.0f / ob->size[0];
1767         scale[1] = 1.0f / ob->size[1];
1768         scale[2] = 1.0f / ob->size[2];
1769         RNA_float_set_array(op->ptr, "scale", scale);
1770
1771         /* Initialize mirror modifier clipping */
1772         for(md= ob->modifiers.first; md; md= md->next) {
1773                 if(md->type==eModifierType_Mirror && (md->mode & eModifierMode_Realtime)) {
1774                         const MirrorModifierData *mmd = (MirrorModifierData*) md;
1775                         
1776                         /* Mark each axis that needs clipping along with its tolerance */
1777                         if(mmd->flag & MOD_MIR_CLIPPING) {
1778                                 flag |= CLIP_X << mmd->axis;
1779                                 if(mmd->tolerance > clip_tolerance[mmd->axis])
1780                                         clip_tolerance[mmd->axis] = mmd->tolerance;
1781                         }
1782                 }
1783         }
1784         RNA_int_set(op->ptr, "flag", flag);
1785         RNA_float_set_array(op->ptr, "clip_tolerance", clip_tolerance);
1786
1787         /* Initial mouse location */
1788         mouse[0] = event->x;
1789         mouse[1] = event->y;
1790         RNA_float_set_array(op->ptr, "initial_mouse", mouse);
1791 }
1792
1793 static int sculpt_brush_stroke_init(bContext *C, ReportList *reports)
1794 {
1795         Object *ob= CTX_data_active_object(C);
1796         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
1797         SculptSession *ss = CTX_data_active_object(C)->sculpt;
1798         Brush *brush = paint_brush(&sd->paint);
1799
1800         if(ob_get_key(ob) && !(ob->shapeflag & OB_SHAPE_LOCK)) {
1801                 BKE_report(reports, RPT_ERROR, "Shape key sculpting requires a locked shape.");
1802                 return 0;
1803         }
1804
1805         view3d_operator_needs_opengl(C);
1806
1807         /* TODO: Shouldn't really have to do this at the start of every
1808            stroke, but sculpt would need some sort of notification when
1809            changes are made to the texture. */
1810         sculpt_update_tex(sd, ss);
1811
1812         sculpt_update_mesh_elements(C, brush->sculpt_tool == SCULPT_TOOL_SMOOTH);
1813
1814         if(ss->kb) key_to_mesh(ss->kb, ss->ob->data);
1815
1816         return 1;
1817 }
1818
1819 static void sculpt_restore_mesh(Sculpt *sd, SculptSession *ss)
1820 {
1821         StrokeCache *cache = ss->cache;
1822         Brush *brush = paint_brush(&sd->paint);
1823         int i;
1824
1825         /* Restore the mesh before continuing with anchored stroke */
1826         if(brush->flag & BRUSH_ANCHORED) {
1827                 PBVHNode **nodes;
1828                 int n, totnode;
1829
1830                 BLI_pbvh_search_gather(ss->tree, NULL, NULL, &nodes, &totnode);
1831
1832                 #pragma omp parallel for private(n) schedule(static)
1833                 for(n=0; n<totnode; n++) {
1834                         SculptUndoNode *unode;
1835                         
1836                         unode= sculpt_undo_get_node(ss, nodes[n]);
1837                         if(unode) {
1838                                 PBVHVertexIter vd;
1839
1840                                 BLI_pbvh_vertex_iter_begin(ss->tree, nodes[n], vd, PBVH_ITER_UNIQUE) {
1841                                         copy_v3_v3(vd.co, unode->co[vd.i]);
1842                                         if(vd.no) VECCOPY(vd.no, unode->no[vd.i])
1843                                         else normal_short_to_float_v3(vd.fno, unode->no[vd.i]);
1844                                 }
1845                                 BLI_pbvh_vertex_iter_end;
1846                         }
1847                 }
1848
1849                 if(ss->face_normals) {
1850                         float *fn = ss->face_normals;
1851                         for(i = 0; i < ss->totface; ++i, fn += 3)
1852                                 copy_v3_v3(fn, cache->face_norms[i]);
1853                 }
1854
1855                 if(brush->sculpt_tool == SCULPT_TOOL_LAYER)
1856                         memset(ss->layer_disps, 0, sizeof(float) * ss->totvert);
1857         }
1858 }
1859
1860 static void sculpt_flush_update(bContext *C)
1861 {
1862         Object *ob = CTX_data_active_object(C);
1863         SculptSession *ss = ob->sculpt;
1864         ARegion *ar = CTX_wm_region(C);
1865         MultiresModifierData *mmd = ss->multires;
1866         rcti r;
1867         int redraw = 0;
1868
1869         if(mmd)
1870                 multires_mark_as_modified(ob);
1871
1872         BLI_pbvh_update(ss->tree, PBVH_UpdateBB, NULL);
1873         redraw = sculpt_get_redraw_rect(ar, CTX_wm_region_view3d(C), ob, &r);
1874
1875         if(redraw) {
1876                 r.xmin += ar->winrct.xmin + 1;
1877                 r.xmax += ar->winrct.xmin - 1;
1878                 r.ymin += ar->winrct.ymin + 1;
1879                 r.ymax += ar->winrct.ymin - 1;
1880                 
1881                 ss->partial_redraw = 1;
1882                 ED_region_tag_redraw_partial(ar, &r);
1883         }
1884 }
1885
1886 static int sculpt_stroke_test_start(bContext *C, struct wmOperator *op, wmEvent *event)
1887 {
1888         float mouse[2] = {event->x, event->y}, location[3];
1889         int over_mesh;
1890         
1891         over_mesh = sculpt_stroke_get_location(C, op->customdata, location, mouse);
1892         
1893         /* Don't start the stroke until mouse goes over the mesh */
1894         if(over_mesh) {
1895                 Object *ob = CTX_data_active_object(C);
1896                 SculptSession *ss = ob->sculpt;
1897                 Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
1898
1899                 ED_view3d_init_mats_rv3d(ob, CTX_wm_region_view3d(C));
1900
1901                 sculpt_brush_stroke_init_properties(C, op, event, ss);
1902
1903                 sculpt_update_cache_invariants(sd, ss, C, op);
1904
1905                 sculpt_undo_push_begin(ss, sculpt_tool_name(sd));
1906
1907                 return 1;
1908         }
1909         else
1910                 return 0;
1911 }
1912
1913 static void sculpt_stroke_update_step(bContext *C, struct PaintStroke *stroke, PointerRNA *itemptr)
1914 {
1915         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
1916         SculptSession *ss = CTX_data_active_object(C)->sculpt;
1917
1918         sculpt_update_cache_variants(sd, ss, stroke, itemptr);
1919         sculpt_restore_mesh(sd, ss);
1920         do_symmetrical_brush_actions(sd, ss);
1921
1922         /* Cleanup */
1923         sculpt_flush_update(C);
1924 }
1925
1926 static void sculpt_stroke_done(bContext *C, struct PaintStroke *stroke)
1927 {
1928         Object *ob= CTX_data_active_object(C);
1929         SculptSession *ss = ob->sculpt;
1930
1931         /* Finished */
1932         if(ss->cache) {
1933                 sculpt_cache_free(ss->cache);
1934                 ss->cache = NULL;
1935
1936                 sculpt_undo_push_end(ss);
1937
1938                 BLI_pbvh_update(ss->tree, PBVH_UpdateOriginalBB, NULL);
1939         }
1940 }
1941
1942 static int sculpt_brush_stroke_invoke(bContext *C, wmOperator *op, wmEvent *event)
1943 {
1944         if(!sculpt_brush_stroke_init(C, op->reports))
1945                 return OPERATOR_CANCELLED;
1946
1947         op->customdata = paint_stroke_new(C, sculpt_stroke_get_location,
1948                                           sculpt_stroke_test_start,
1949                                           sculpt_stroke_update_step,
1950                                           sculpt_stroke_done);
1951
1952         /* add modal handler */
1953         WM_event_add_modal_handler(C, op);
1954
1955         op->type->modal(C, op, event);
1956         
1957         return OPERATOR_RUNNING_MODAL;
1958 }
1959
1960 static int sculpt_brush_stroke_exec(bContext *C, wmOperator *op)
1961 {
1962         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
1963         SculptSession *ss = CTX_data_active_object(C)->sculpt;
1964
1965         if(!sculpt_brush_stroke_init(C, op->reports))
1966                 return OPERATOR_CANCELLED;
1967
1968         op->customdata = paint_stroke_new(C, sculpt_stroke_get_location, sculpt_stroke_test_start,
1969                                           sculpt_stroke_update_step, sculpt_stroke_done);
1970
1971         sculpt_update_cache_invariants(sd, ss, C, op);
1972
1973         paint_stroke_exec(C, op);
1974
1975         sculpt_flush_update(C);
1976         sculpt_cache_free(ss->cache);
1977
1978         return OPERATOR_FINISHED;
1979 }
1980
1981 static void SCULPT_OT_brush_stroke(wmOperatorType *ot)
1982 {
1983         ot->flag |= OPTYPE_REGISTER;
1984
1985         /* identifiers */
1986         ot->name= "Sculpt Mode";
1987         ot->idname= "SCULPT_OT_brush_stroke";
1988         
1989         /* api callbacks */
1990         ot->invoke= sculpt_brush_stroke_invoke;
1991         ot->modal= paint_stroke_modal;
1992         ot->exec= sculpt_brush_stroke_exec;
1993         ot->poll= sculpt_poll;
1994         
1995         /* flags (sculpt does own undo? (ton) */
1996         ot->flag= OPTYPE_REGISTER|OPTYPE_BLOCKING;
1997
1998         /* properties */
1999         RNA_def_collection_runtime(ot->srna, "stroke", &RNA_OperatorStrokeElement, "Stroke", "");
2000
2001         /* If the object has a scaling factor, brushes also need to be scaled
2002            to work as expected. */
2003         RNA_def_float_vector(ot->srna, "scale", 3, NULL, 0.0f, FLT_MAX, "Scale", "", 0.0f, 1000.0f);
2004
2005         RNA_def_int(ot->srna, "flag", 0, 0, INT_MAX, "flag", "", 0, INT_MAX);
2006
2007         /* For mirror modifiers */
2008         RNA_def_float_vector(ot->srna, "clip_tolerance", 3, NULL, 0.0f, FLT_MAX, "clip_tolerance", "", 0.0f, 1000.0f);
2009
2010         /* The initial 2D location of the mouse */
2011         RNA_def_float_vector(ot->srna, "initial_mouse", 2, NULL, INT_MIN, INT_MAX, "initial_mouse", "", INT_MIN, INT_MAX);
2012 }
2013
2014 /**** Reset the copy of the mesh that is being sculpted on (currently just for the layer brush) ****/
2015
2016 static int sculpt_set_persistent_base(bContext *C, wmOperator *op)
2017 {
2018         SculptSession *ss = CTX_data_active_object(C)->sculpt;
2019
2020         if(ss) {
2021                 if(ss->layer_disps)
2022                         MEM_freeN(ss->layer_disps);
2023                 ss->layer_disps = NULL;
2024
2025                 if(ss->layer_co)
2026                         MEM_freeN(ss->layer_co);
2027                 ss->layer_co = NULL;
2028         }
2029
2030         return OPERATOR_FINISHED;
2031 }
2032
2033 static void SCULPT_OT_set_persistent_base(wmOperatorType *ot)
2034 {
2035         /* identifiers */
2036         ot->name= "Set Persistent Base";
2037         ot->idname= "SCULPT_OT_set_persistent_base";
2038         
2039         /* api callbacks */
2040         ot->exec= sculpt_set_persistent_base;
2041         ot->poll= sculpt_mode_poll;
2042         
2043         ot->flag= OPTYPE_REGISTER;
2044 }
2045
2046 /**** Toggle operator for turning sculpt mode on or off ****/
2047
2048 static void sculpt_init_session(bContext *C, Object *ob)
2049 {
2050         ob->sculpt = MEM_callocN(sizeof(SculptSession), "sculpt session");
2051         
2052         sculpt_update_mesh_elements(C, 0);
2053 }
2054
2055 static int sculpt_toggle_mode(bContext *C, wmOperator *op)
2056 {
2057         ToolSettings *ts = CTX_data_tool_settings(C);
2058         Object *ob = CTX_data_active_object(C);
2059         MultiresModifierData *mmd = sculpt_multires_active(ob);
2060
2061         if(ob->mode & OB_MODE_SCULPT) {
2062                 if(sculpt_multires_active(ob))
2063                         multires_force_update(ob);
2064
2065                 if(mmd && mmd->sculptlvl != mmd->lvl)
2066                         DAG_id_flush_update(&ob->id, OB_RECALC_DATA);
2067
2068                 /* Leave sculptmode */
2069                 ob->mode &= ~OB_MODE_SCULPT;
2070
2071                 free_sculptsession(&ob->sculpt);
2072         }
2073         else {
2074                 /* Enter sculptmode */
2075                 ob->mode |= OB_MODE_SCULPT;
2076
2077                 if(mmd && mmd->sculptlvl != mmd->lvl)
2078                         DAG_id_flush_update(&ob->id, OB_RECALC_DATA);
2079                 
2080                 /* Create persistent sculpt mode data */
2081                 if(!ts->sculpt)
2082                         ts->sculpt = MEM_callocN(sizeof(Sculpt), "sculpt mode data");
2083
2084                 /* Create sculpt mode session data */
2085                 if(ob->sculpt)
2086                         free_sculptsession(&ob->sculpt);
2087
2088                 sculpt_init_session(C, ob);
2089
2090                 paint_init(&ts->sculpt->paint, PAINT_CURSOR_SCULPT);
2091                 
2092                 paint_cursor_start(C, sculpt_poll);
2093         }
2094
2095         WM_event_add_notifier(C, NC_SCENE|ND_MODE, CTX_data_scene(C));
2096
2097         return OPERATOR_FINISHED;
2098 }
2099
2100 static void SCULPT_OT_sculptmode_toggle(wmOperatorType *ot)
2101 {
2102         /* identifiers */
2103         ot->name= "Sculpt Mode";
2104         ot->idname= "SCULPT_OT_sculptmode_toggle";
2105         
2106         /* api callbacks */
2107         ot->exec= sculpt_toggle_mode;
2108         ot->poll= ED_operator_object_active;
2109         
2110         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2111 }
2112
2113 void ED_operatortypes_sculpt()
2114 {
2115         WM_operatortype_append(SCULPT_OT_radial_control);
2116         WM_operatortype_append(SCULPT_OT_brush_stroke);
2117         WM_operatortype_append(SCULPT_OT_sculptmode_toggle);
2118         WM_operatortype_append(SCULPT_OT_set_persistent_base);
2119 }
2120