Merging r50625 through r51896 from trunk into soc-2011-tomato
[blender-staging.git] / source / blender / editors / sculpt_paint / sculpt_undo.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): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  *
27  * Implements the Sculpt Mode tools
28  *
29  */
30
31 /** \file blender/editors/sculpt_paint/sculpt_undo.c
32  *  \ingroup edsculpt
33  */
34
35 #include <stddef.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_math.h"
40 #include "BLI_utildefines.h"
41 #include "BLI_string.h"
42 #include "BLI_listbase.h"
43 #include "BLI_ghash.h"
44 #include "BLI_threads.h"
45
46 #include "DNA_meshdata_types.h"
47 #include "DNA_object_types.h"
48 #include "DNA_scene_types.h"
49 #include "DNA_mesh_types.h"
50
51 #include "BKE_ccg.h"
52 #include "BKE_cdderivedmesh.h"
53 #include "BKE_context.h"
54 #include "BKE_depsgraph.h"
55 #include "BKE_modifier.h"
56 #include "BKE_multires.h"
57 #include "BKE_paint.h"
58 #include "BKE_key.h"
59 #include "BKE_mesh.h"
60 #include "BKE_subsurf.h"
61
62 #include "WM_api.h"
63 #include "WM_types.h"
64
65 #include "GPU_buffers.h"
66
67 #include "ED_sculpt.h"
68 #include "paint_intern.h"
69 #include "sculpt_intern.h"
70
71 /************************** Undo *************************/
72
73 static void update_cb(PBVHNode *node, void *rebuild)
74 {
75         BLI_pbvh_node_mark_update(node);
76         if (*((int *)rebuild))
77                 BLI_pbvh_node_mark_rebuild_draw(node);
78         BLI_pbvh_node_fully_hidden_set(node, 0);
79 }
80
81 static void sculpt_undo_restore_deformed(const SculptSession *ss,
82                                          SculptUndoNode *unode,
83                                          int uindex, int oindex,
84                                          float coord[3])
85 {
86         if (unode->orig_co) {
87                 swap_v3_v3(coord, unode->orig_co[uindex]);
88                 copy_v3_v3(unode->co[uindex], ss->deform_cos[oindex]);
89         }
90         else {
91                 swap_v3_v3(coord, unode->co[uindex]);
92         }
93 }
94
95 static int sculpt_undo_restore_coords(bContext *C, DerivedMesh *dm, SculptUndoNode *unode)
96 {
97         Scene *scene = CTX_data_scene(C);
98         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
99         Object *ob = CTX_data_active_object(C);
100         SculptSession *ss = ob->sculpt;
101         MVert *mvert;
102         int *index, i, j;
103         
104         if (unode->maxvert) {
105                 /* regular mesh restore */
106
107                 if (ss->kb && strcmp(ss->kb->name, unode->shapeName)) {
108                         /* shape key has been changed before calling undo operator */
109
110                         Key *key = BKE_key_from_object(ob);
111                         KeyBlock *kb = key ? BKE_keyblock_find_name(key, unode->shapeName) : NULL;
112
113                         if (kb) {
114                                 ob->shapenr = BLI_findindex(&key->block, kb) + 1;
115
116                                 sculpt_update_mesh_elements(scene, sd, ob, 0, FALSE);
117                                 WM_event_add_notifier(C, NC_OBJECT | ND_DATA, ob);
118                         }
119                         else {
120                                 /* key has been removed -- skip this undo node */
121                                 return 0;
122                         }
123                 }
124
125                 index = unode->index;
126                 mvert = ss->mvert;
127
128                 if (ss->kb) {
129                         float (*vertCos)[3];
130                         vertCos = BKE_key_convert_to_vertcos(ob, ss->kb);
131
132                         for (i = 0; i < unode->totvert; i++) {
133                                 if (ss->modifiers_active) sculpt_undo_restore_deformed(ss, unode, i, index[i], vertCos[index[i]]);
134                                 else {
135                                         if (unode->orig_co) swap_v3_v3(vertCos[index[i]], unode->orig_co[i]);
136                                         else swap_v3_v3(vertCos[index[i]], unode->co[i]);
137                                 }
138                         }
139
140                         /* propagate new coords to keyblock */
141                         sculpt_vertcos_to_key(ob, ss->kb, vertCos);
142
143                         /* pbvh uses it's own mvert array, so coords should be */
144                         /* propagated to pbvh here */
145                         BLI_pbvh_apply_vertCos(ss->pbvh, vertCos);
146
147                         MEM_freeN(vertCos);
148                 }
149                 else {
150                         for (i = 0; i < unode->totvert; i++) {
151                                 if (ss->modifiers_active) sculpt_undo_restore_deformed(ss, unode, i, index[i], mvert[index[i]].co);
152                                 else {
153                                         if (unode->orig_co) swap_v3_v3(mvert[index[i]].co, unode->orig_co[i]);
154                                         else swap_v3_v3(mvert[index[i]].co, unode->co[i]);
155                                 }
156                                 mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
157                         }
158                 }
159         }
160         else if (unode->maxgrid && dm->getGridData) {
161                 /* multires restore */
162                 CCGElem **grids, *grid;
163                 CCGKey key;
164                 float (*co)[3];
165                 int gridsize;
166
167                 grids = dm->getGridData(dm);
168                 gridsize = dm->getGridSize(dm);
169                 dm->getGridKey(dm, &key);
170
171                 co = unode->co;
172                 for (j = 0; j < unode->totgrid; j++) {
173                         grid = grids[unode->grids[j]];
174
175                         for (i = 0; i < gridsize * gridsize; i++, co++)
176                                 swap_v3_v3(CCG_elem_offset_co(&key, grid, i), co[0]);
177                 }
178         }
179
180         return 1;
181 }
182
183 static int sculpt_undo_restore_hidden(bContext *C, DerivedMesh *dm,
184                                       SculptUndoNode *unode)
185 {
186         Object *ob = CTX_data_active_object(C);
187         SculptSession *ss = ob->sculpt;
188         int i;
189
190         if (unode->maxvert) {
191                 MVert *mvert = ss->mvert;
192                 
193                 for (i = 0; i < unode->totvert; i++) {
194                         MVert *v = &mvert[unode->index[i]];
195                         int uval = BLI_BITMAP_GET(unode->vert_hidden, i);
196
197                         BLI_BITMAP_MODIFY(unode->vert_hidden, i,
198                                           v->flag & ME_HIDE);
199                         if (uval)
200                                 v->flag |= ME_HIDE;
201                         else
202                                 v->flag &= ~ME_HIDE;
203                         
204                         v->flag |= ME_VERT_PBVH_UPDATE;
205                 }
206         }
207         else if (unode->maxgrid && dm->getGridData) {
208                 BLI_bitmap *grid_hidden = dm->getGridHidden(dm);
209                 
210                 for (i = 0; i < unode->totgrid; i++) {
211                         SWAP(BLI_bitmap,
212                              unode->grid_hidden[i],
213                              grid_hidden[unode->grids[i]]);
214                         
215                 }
216         }
217
218         return 1;
219 }
220
221 static int sculpt_undo_restore_mask(bContext *C, DerivedMesh *dm, SculptUndoNode *unode)
222 {
223         Object *ob = CTX_data_active_object(C);
224         SculptSession *ss = ob->sculpt;
225         MVert *mvert;
226         float *vmask;
227         int *index, i, j;
228         
229         if (unode->maxvert) {
230                 /* regular mesh restore */
231
232                 index = unode->index;
233                 mvert = ss->mvert;
234                 vmask = ss->vmask;
235
236                 for (i = 0; i < unode->totvert; i++) {
237                         SWAP(float, vmask[index[i]], unode->mask[i]);
238                         mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
239                 }
240         }
241         else if (unode->maxgrid && dm->getGridData) {
242                 /* multires restore */
243                 CCGElem **grids, *grid;
244                 CCGKey key;
245                 float *mask;
246                 int gridsize;
247
248                 grids = dm->getGridData(dm);
249                 gridsize = dm->getGridSize(dm);
250                 dm->getGridKey(dm, &key);
251
252                 mask = unode->mask;
253                 for (j = 0; j < unode->totgrid; j++) {
254                         grid = grids[unode->grids[j]];
255
256                         for (i = 0; i < gridsize * gridsize; i++, mask++)
257                                 SWAP(float, *CCG_elem_offset_mask(&key, grid, i), *mask);
258                 }
259         }
260
261         return 1;
262 }
263
264 static void sculpt_undo_restore(bContext *C, ListBase *lb)
265 {
266         Scene *scene = CTX_data_scene(C);
267         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
268         Object *ob = CTX_data_active_object(C);
269         DerivedMesh *dm;
270         SculptSession *ss = ob->sculpt;
271         SculptUndoNode *unode;
272         MultiresModifierData *mmd;
273         int update = FALSE, rebuild = FALSE;
274         int need_mask = FALSE;
275
276         for (unode = lb->first; unode; unode = unode->next) {
277                 if (strcmp(unode->idname, ob->id.name) == 0) {
278                         if (unode->type == SCULPT_UNDO_MASK) {
279                                 /* is possible that we can't do the mask undo (below)
280                                  * because of the vertex count */
281                                 need_mask = TRUE;
282                                 break;
283                         }
284                 }
285         }
286
287         sculpt_update_mesh_elements(scene, sd, ob, 0, need_mask);
288
289         /* call _after_ sculpt_update_mesh_elements() which may update 'ob->derivedFinal' */
290         dm = mesh_get_derived_final(scene, ob, 0);
291
292         for (unode = lb->first; unode; unode = unode->next) {
293                 if (!(strcmp(unode->idname, ob->id.name) == 0))
294                         continue;
295
296                 /* check if undo data matches current data well enough to
297                  * continue */
298                 if (unode->maxvert) {
299                         if (ss->totvert != unode->maxvert)
300                                 continue;
301                 }
302                 else if (unode->maxgrid && dm->getGridData) {
303                         if ((dm->getNumGrids(dm) != unode->maxgrid) ||
304                             (dm->getGridSize(dm) != unode->gridsize))
305                         {
306                                 continue;
307                         }
308                 }
309                 else {
310                         continue;
311                 }
312
313                 switch (unode->type) {
314                         case SCULPT_UNDO_COORDS:
315                                 if (sculpt_undo_restore_coords(C, dm, unode))
316                                         update = TRUE;
317                                 break;
318                         case SCULPT_UNDO_HIDDEN:
319                                 if (sculpt_undo_restore_hidden(C, dm, unode))
320                                         rebuild = TRUE;
321                                 break;
322                         case SCULPT_UNDO_MASK:
323                                 if (sculpt_undo_restore_mask(C, dm, unode))
324                                         update = TRUE;
325                                 break;
326                 }
327         }
328
329         if (update || rebuild) {
330                 int tag_update = 0;
331                 /* we update all nodes still, should be more clever, but also
332                  * needs to work correct when exiting/entering sculpt mode and
333                  * the nodes get recreated, though in that case it could do all */
334                 BLI_pbvh_search_callback(ss->pbvh, NULL, NULL, update_cb, &rebuild);
335                 BLI_pbvh_update(ss->pbvh, PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw, NULL);
336
337                 if ((mmd = sculpt_multires_active(scene, ob))) {
338                         if (rebuild)
339                                 multires_mark_as_modified(ob, MULTIRES_HIDDEN_MODIFIED);
340                         else
341                                 multires_mark_as_modified(ob, MULTIRES_COORDS_MODIFIED);
342                 }
343
344                 tag_update = ((Mesh *)ob->data)->id.us > 1;
345
346                 if (ss->modifiers_active) {
347                         Mesh *mesh = ob->data;
348                         BKE_mesh_calc_normals_tessface(mesh->mvert, mesh->totvert,
349                                                        mesh->mface, mesh->totface, NULL);
350
351                         free_sculptsession_deformMats(ss);
352                         tag_update |= 1;
353                 }
354
355                 if (tag_update)
356                         DAG_id_tag_update(&ob->id, OB_RECALC_DATA);
357
358                 /* for non-PBVH drawing, need to recreate VBOs */
359                 GPU_drawobject_free(ob->derivedFinal);
360         }
361 }
362
363 static void sculpt_undo_free(ListBase *lb)
364 {
365         SculptUndoNode *unode;
366         int i;
367
368         for (unode = lb->first; unode; unode = unode->next) {
369                 if (unode->co)
370                         MEM_freeN(unode->co);
371                 if (unode->no)
372                         MEM_freeN(unode->no);
373                 if (unode->index)
374                         MEM_freeN(unode->index);
375                 if (unode->grids)
376                         MEM_freeN(unode->grids);
377                 if (unode->layer_disp)
378                         MEM_freeN(unode->layer_disp);
379                 if (unode->orig_co)
380                         MEM_freeN(unode->orig_co);
381                 if (unode->vert_hidden)
382                         MEM_freeN(unode->vert_hidden);
383                 if (unode->grid_hidden) {
384                         for (i = 0; i < unode->totgrid; i++) {
385                                 if (unode->grid_hidden[i])
386                                         MEM_freeN(unode->grid_hidden[i]);
387                         }
388                         MEM_freeN(unode->grid_hidden);
389                 }
390                 if (unode->mask)
391                         MEM_freeN(unode->mask);
392         }
393 }
394
395 SculptUndoNode *sculpt_undo_get_node(PBVHNode *node)
396 {
397         ListBase *lb = undo_paint_push_get_list(UNDO_PAINT_MESH);
398
399         if (!lb) {
400                 return NULL;
401         }
402
403         return BLI_findptr(lb, node, offsetof(SculptUndoNode, node));
404 }
405
406 static void sculpt_undo_alloc_and_store_hidden(PBVH *pbvh,
407                                                SculptUndoNode *unode)
408 {
409         PBVHNode *node = unode->node;
410         BLI_bitmap *grid_hidden;
411         int i, *grid_indices, totgrid;
412
413         grid_hidden = BLI_pbvh_grid_hidden(pbvh);
414
415         BLI_pbvh_node_get_grids(pbvh, node, &grid_indices, &totgrid,
416                                 NULL, NULL, NULL, NULL);
417                         
418         unode->grid_hidden = MEM_mapallocN(sizeof(BLI_bitmap) * totgrid,
419                                            "unode->grid_hidden");
420                 
421         for (i = 0; i < totgrid; i++) {
422                 if (grid_hidden[grid_indices[i]])
423                         unode->grid_hidden[i] = MEM_dupallocN(grid_hidden[grid_indices[i]]);
424                 else
425                         unode->grid_hidden[i] = NULL;
426         }
427 }
428
429 static SculptUndoNode *sculpt_undo_alloc_node(Object *ob, PBVHNode *node,
430                                               SculptUndoType type)
431 {
432         ListBase *lb = undo_paint_push_get_list(UNDO_PAINT_MESH);
433         SculptUndoNode *unode;
434         SculptSession *ss = ob->sculpt;
435         int totvert, allvert, totgrid, maxgrid, gridsize, *grids;
436         
437         unode = MEM_callocN(sizeof(SculptUndoNode), "SculptUndoNode");
438         BLI_strncpy(unode->idname, ob->id.name, sizeof(unode->idname));
439         unode->type = type;
440         unode->node = node;
441
442         BLI_pbvh_node_num_verts(ss->pbvh, node, &totvert, &allvert);
443         BLI_pbvh_node_get_grids(ss->pbvh, node, &grids, &totgrid,
444                                 &maxgrid, &gridsize, NULL, NULL);
445
446         unode->totvert = totvert;
447         
448         /* we will use this while sculpting, is mapalloc slow to access then? */
449
450         /* general TODO, fix count_alloc */
451         switch (type) {
452                 case SCULPT_UNDO_COORDS:
453                         unode->co = MEM_mapallocN(sizeof(float) * 3 * allvert, "SculptUndoNode.co");
454                         unode->no = MEM_mapallocN(sizeof(short) * 3 * allvert, "SculptUndoNode.no");
455                         undo_paint_push_count_alloc(UNDO_PAINT_MESH,
456                                                     (sizeof(float) * 3 +
457                                                      sizeof(short) * 3 +
458                                                      sizeof(int)) * allvert);
459                         break;
460                 case SCULPT_UNDO_HIDDEN:
461                         if (maxgrid)
462                                 sculpt_undo_alloc_and_store_hidden(ss->pbvh, unode);
463                         else
464                                 unode->vert_hidden = BLI_BITMAP_NEW(allvert, "SculptUndoNode.vert_hidden");
465                 
466                         break;
467                 case SCULPT_UNDO_MASK:
468                         unode->mask = MEM_mapallocN(sizeof(float) * allvert, "SculptUndoNode.mask");
469                         undo_paint_push_count_alloc(UNDO_PAINT_MESH, (sizeof(float) * sizeof(int)) * allvert);
470                         break;
471         }
472         
473         BLI_addtail(lb, unode);
474
475         if (maxgrid) {
476                 /* multires */
477                 unode->maxgrid = maxgrid;
478                 unode->totgrid = totgrid;
479                 unode->gridsize = gridsize;
480                 unode->grids = MEM_mapallocN(sizeof(int) * totgrid, "SculptUndoNode.grids");
481         }
482         else {
483                 /* regular mesh */
484                 unode->maxvert = ss->totvert;
485                 unode->index = MEM_mapallocN(sizeof(int) * allvert, "SculptUndoNode.index");
486         }
487
488         if (ss->modifiers_active)
489                 unode->orig_co = MEM_callocN(allvert * sizeof(*unode->orig_co), "undoSculpt orig_cos");
490
491         return unode;
492 }
493
494 static void sculpt_undo_store_coords(Object *ob, SculptUndoNode *unode)
495 {
496         SculptSession *ss = ob->sculpt;
497         PBVHVertexIter vd;
498
499         BLI_pbvh_vertex_iter_begin(ss->pbvh, unode->node, vd, PBVH_ITER_ALL)
500         {
501                 copy_v3_v3(unode->co[vd.i], vd.co);
502                 if (vd.no) copy_v3_v3_short(unode->no[vd.i], vd.no);
503                 else normal_float_to_short_v3(unode->no[vd.i], vd.fno);
504
505                 if (ss->modifiers_active)
506                         copy_v3_v3(unode->orig_co[vd.i], ss->orig_cos[unode->index[vd.i]]);
507         }
508         BLI_pbvh_vertex_iter_end;
509 }
510
511 static void sculpt_undo_store_hidden(Object *ob, SculptUndoNode *unode)
512 {
513         PBVH *pbvh = ob->sculpt->pbvh;
514         PBVHNode *node = unode->node;
515
516         if (unode->grids) {
517                 /* already stored during allocation */
518         }
519         else {
520                 MVert *mvert;
521                 int *vert_indices, allvert;
522                 int i;
523                 
524                 BLI_pbvh_node_num_verts(pbvh, node, NULL, &allvert);
525                 BLI_pbvh_node_get_verts(pbvh, node, &vert_indices, &mvert);
526                 for (i = 0; i < allvert; i++) {
527                         BLI_BITMAP_MODIFY(unode->vert_hidden, i,
528                                           mvert[vert_indices[i]].flag & ME_HIDE);
529                 }
530         }
531 }
532
533 static void sculpt_undo_store_mask(Object *ob, SculptUndoNode *unode)
534 {
535         SculptSession *ss = ob->sculpt;
536         PBVHVertexIter vd;
537
538         BLI_pbvh_vertex_iter_begin(ss->pbvh, unode->node, vd, PBVH_ITER_ALL)
539         {
540                 unode->mask[vd.i] = *vd.mask;
541         }
542         BLI_pbvh_vertex_iter_end;
543 }
544
545 SculptUndoNode *sculpt_undo_push_node(Object *ob, PBVHNode *node,
546                                       SculptUndoType type)
547 {
548         SculptSession *ss = ob->sculpt;
549         SculptUndoNode *unode;
550
551         /* list is manipulated by multiple threads, so we lock */
552         BLI_lock_thread(LOCK_CUSTOM1);
553
554         if ((unode = sculpt_undo_get_node(node))) {
555                 BLI_unlock_thread(LOCK_CUSTOM1);
556                 return unode;
557         }
558
559         unode = sculpt_undo_alloc_node(ob, node, type);
560         
561         BLI_unlock_thread(LOCK_CUSTOM1);
562
563         /* copy threaded, hopefully this is the performance critical part */
564
565         if (unode->grids) {
566                 int totgrid, *grids;
567                 BLI_pbvh_node_get_grids(ss->pbvh, node, &grids, &totgrid,
568                                         NULL, NULL, NULL, NULL);
569                 memcpy(unode->grids, grids, sizeof(int) * totgrid);
570         }
571         else {
572                 int *vert_indices, allvert;
573                 BLI_pbvh_node_num_verts(ss->pbvh, node, NULL, &allvert);
574                 BLI_pbvh_node_get_verts(ss->pbvh, node, &vert_indices, NULL);
575                 memcpy(unode->index, vert_indices, sizeof(int) * unode->totvert);
576         }
577
578         switch (type) {
579                 case SCULPT_UNDO_COORDS:
580                         sculpt_undo_store_coords(ob, unode);
581                         break;
582                 case SCULPT_UNDO_HIDDEN:
583                         sculpt_undo_store_hidden(ob, unode);
584                         break;
585                 case SCULPT_UNDO_MASK:
586                         sculpt_undo_store_mask(ob, unode);
587                         break;
588         }
589
590         /* store active shape key */
591         if (ss->kb) BLI_strncpy(unode->shapeName, ss->kb->name, sizeof(ss->kb->name));
592         else unode->shapeName[0] = '\0';
593
594         return unode;
595 }
596
597 void sculpt_undo_push_begin(const char *name)
598 {
599         undo_paint_push_begin(UNDO_PAINT_MESH, name,
600                               sculpt_undo_restore, sculpt_undo_free);
601 }
602
603 void sculpt_undo_push_end(void)
604 {
605         ListBase *lb = undo_paint_push_get_list(UNDO_PAINT_MESH);
606         SculptUndoNode *unode;
607
608         /* we don't need normals in the undo stack */
609         for (unode = lb->first; unode; unode = unode->next) {
610                 if (unode->no) {
611                         MEM_freeN(unode->no);
612                         unode->no = NULL;
613                 }
614
615                 if (unode->layer_disp) {
616                         MEM_freeN(unode->layer_disp);
617                         unode->layer_disp = NULL;
618                 }
619         }
620
621         undo_paint_push_end(UNDO_PAINT_MESH);
622 }