406756f419742ddeb36c6114def7cd3331e4431d
[blender.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 "bmesh.h"
69 #include "paint_intern.h"
70 #include "sculpt_intern.h"
71
72 /************************** Undo *************************/
73
74 static void update_cb(PBVHNode *node, void *rebuild)
75 {
76         BKE_pbvh_node_mark_update(node);
77         if (*((int *)rebuild))
78                 BKE_pbvh_node_mark_rebuild_draw(node);
79         BKE_pbvh_node_fully_hidden_set(node, 0);
80 }
81
82 static void sculpt_undo_restore_deformed(const SculptSession *ss,
83                                          SculptUndoNode *unode,
84                                          int uindex, int oindex,
85                                          float coord[3])
86 {
87         if (unode->orig_co) {
88                 swap_v3_v3(coord, unode->orig_co[uindex]);
89                 copy_v3_v3(unode->co[uindex], ss->deform_cos[oindex]);
90         }
91         else {
92                 swap_v3_v3(coord, unode->co[uindex]);
93         }
94 }
95
96 static int sculpt_undo_restore_coords(bContext *C, DerivedMesh *dm, SculptUndoNode *unode)
97 {
98         Scene *scene = CTX_data_scene(C);
99         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
100         Object *ob = CTX_data_active_object(C);
101         SculptSession *ss = ob->sculpt;
102         MVert *mvert;
103         int *index, i, j;
104         
105         if (unode->maxvert) {
106                 /* regular mesh restore */
107
108                 if (ss->kb && strcmp(ss->kb->name, unode->shapeName)) {
109                         /* shape key has been changed before calling undo operator */
110
111                         Key *key = BKE_key_from_object(ob);
112                         KeyBlock *kb = key ? BKE_keyblock_find_name(key, unode->shapeName) : NULL;
113
114                         if (kb) {
115                                 ob->shapenr = BLI_findindex(&key->block, kb) + 1;
116
117                                 sculpt_update_mesh_elements(scene, sd, ob, 0, FALSE);
118                                 WM_event_add_notifier(C, NC_OBJECT | ND_DATA, ob);
119                         }
120                         else {
121                                 /* key has been removed -- skip this undo node */
122                                 return 0;
123                         }
124                 }
125
126                 index = unode->index;
127                 mvert = ss->mvert;
128
129                 if (ss->kb) {
130                         float (*vertCos)[3];
131                         vertCos = BKE_key_convert_to_vertcos(ob, ss->kb);
132
133                         for (i = 0; i < unode->totvert; i++) {
134                                 if (ss->modifiers_active) sculpt_undo_restore_deformed(ss, unode, i, index[i], vertCos[index[i]]);
135                                 else {
136                                         if (unode->orig_co) swap_v3_v3(vertCos[index[i]], unode->orig_co[i]);
137                                         else swap_v3_v3(vertCos[index[i]], unode->co[i]);
138                                 }
139                         }
140
141                         /* propagate new coords to keyblock */
142                         sculpt_vertcos_to_key(ob, ss->kb, vertCos);
143
144                         /* pbvh uses it's own mvert array, so coords should be */
145                         /* propagated to pbvh here */
146                         BKE_pbvh_apply_vertCos(ss->pbvh, vertCos);
147
148                         MEM_freeN(vertCos);
149                 }
150                 else {
151                         for (i = 0; i < unode->totvert; i++) {
152                                 if (ss->modifiers_active) sculpt_undo_restore_deformed(ss, unode, i, index[i], mvert[index[i]].co);
153                                 else {
154                                         if (unode->orig_co) swap_v3_v3(mvert[index[i]].co, unode->orig_co[i]);
155                                         else swap_v3_v3(mvert[index[i]].co, unode->co[i]);
156                                 }
157                                 mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
158                         }
159                 }
160         }
161         else if (unode->maxgrid && dm->getGridData) {
162                 /* multires restore */
163                 CCGElem **grids, *grid;
164                 CCGKey key;
165                 float (*co)[3];
166                 int gridsize;
167
168                 grids = dm->getGridData(dm);
169                 gridsize = dm->getGridSize(dm);
170                 dm->getGridKey(dm, &key);
171
172                 co = unode->co;
173                 for (j = 0; j < unode->totgrid; j++) {
174                         grid = grids[unode->grids[j]];
175
176                         for (i = 0; i < gridsize * gridsize; i++, co++)
177                                 swap_v3_v3(CCG_elem_offset_co(&key, grid, i), co[0]);
178                 }
179         }
180
181         return 1;
182 }
183
184 static int sculpt_undo_restore_hidden(bContext *C, DerivedMesh *dm,
185                                       SculptUndoNode *unode)
186 {
187         Object *ob = CTX_data_active_object(C);
188         SculptSession *ss = ob->sculpt;
189         int i;
190
191         if (unode->maxvert) {
192                 MVert *mvert = ss->mvert;
193                 
194                 for (i = 0; i < unode->totvert; i++) {
195                         MVert *v = &mvert[unode->index[i]];
196                         int uval = BLI_BITMAP_GET(unode->vert_hidden, i);
197
198                         BLI_BITMAP_MODIFY(unode->vert_hidden, i,
199                                           v->flag & ME_HIDE);
200                         if (uval)
201                                 v->flag |= ME_HIDE;
202                         else
203                                 v->flag &= ~ME_HIDE;
204                         
205                         v->flag |= ME_VERT_PBVH_UPDATE;
206                 }
207         }
208         else if (unode->maxgrid && dm->getGridData) {
209                 BLI_bitmap *grid_hidden = dm->getGridHidden(dm);
210                 
211                 for (i = 0; i < unode->totgrid; i++) {
212                         SWAP(BLI_bitmap,
213                              unode->grid_hidden[i],
214                              grid_hidden[unode->grids[i]]);
215                         
216                 }
217         }
218
219         return 1;
220 }
221
222 static int sculpt_undo_restore_mask(bContext *C, DerivedMesh *dm, SculptUndoNode *unode)
223 {
224         Object *ob = CTX_data_active_object(C);
225         SculptSession *ss = ob->sculpt;
226         MVert *mvert;
227         float *vmask;
228         int *index, i, j;
229         
230         if (unode->maxvert) {
231                 /* regular mesh restore */
232
233                 index = unode->index;
234                 mvert = ss->mvert;
235                 vmask = ss->vmask;
236
237                 for (i = 0; i < unode->totvert; i++) {
238                         SWAP(float, vmask[index[i]], unode->mask[i]);
239                         mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
240                 }
241         }
242         else if (unode->maxgrid && dm->getGridData) {
243                 /* multires restore */
244                 CCGElem **grids, *grid;
245                 CCGKey key;
246                 float *mask;
247                 int gridsize;
248
249                 grids = dm->getGridData(dm);
250                 gridsize = dm->getGridSize(dm);
251                 dm->getGridKey(dm, &key);
252
253                 mask = unode->mask;
254                 for (j = 0; j < unode->totgrid; j++) {
255                         grid = grids[unode->grids[j]];
256
257                         for (i = 0; i < gridsize * gridsize; i++, mask++)
258                                 SWAP(float, *CCG_elem_offset_mask(&key, grid, i), *mask);
259                 }
260         }
261
262         return 1;
263 }
264
265 static void sculpt_undo_bmesh_restore_generic(SculptUndoNode *unode,
266                                                                                           Object *ob,
267                                                                                           SculptSession *ss)
268 {
269         if (unode->applied) {
270                 BM_log_undo(ss->bm, ss->bm_log);
271                 unode->applied = FALSE;
272         }
273         else {
274                 BM_log_redo(ss->bm, ss->bm_log);
275                 unode->applied = TRUE;
276         }
277
278         /* A bit lame, but for now just recreate the PBVH. The alternative
279          * is to store changes to the PBVH in the undo stack. */
280         sculpt_pbvh_clear(ob);
281 }
282
283 /* Create empty sculpt BMesh and enable logging */
284 static void sculpt_undo_bmesh_enable(Object *ob,
285                                                                          SculptUndoNode *unode)
286 {
287         SculptSession *ss = ob->sculpt;
288         Mesh *me = ob->data;
289
290         sculpt_pbvh_clear(ob);
291
292         /* Create empty BMesh and enable logging */
293         ss->bm = BM_mesh_create(&bm_mesh_allocsize_default);
294         BM_data_layer_add(ss->bm, &ss->bm->vdata, CD_PAINT_MASK);
295         me->flag |= ME_SCULPT_DYNAMIC_TOPOLOGY;
296
297         /* Restore the BMLog using saved entries */
298         ss->bm_log = BM_log_from_existing_entries_create(ss->bm,
299                                                                                                          unode->bm_entry);
300 }
301
302 static void sculpt_undo_bmesh_restore_begin(bContext *C,
303                                                                                         SculptUndoNode *unode,
304                                                                                         Object *ob,
305                                                                                         SculptSession *ss)
306 {
307         if (unode->applied) {
308                 sculpt_dynamic_topology_disable(C, unode);
309                 unode->applied = FALSE;
310         }
311         else {
312                 sculpt_undo_bmesh_enable(ob, unode);
313
314                 /* Restore the mesh from the first log entry */
315                 BM_log_redo(ss->bm, ss->bm_log);
316
317                 unode->applied = TRUE;
318         }
319 }
320
321 static void sculpt_undo_bmesh_restore_end(bContext *C,
322                                                                                   SculptUndoNode *unode,
323                                                                                   Object *ob,
324                                                                                   SculptSession *ss)
325 {
326         if (unode->applied) {
327                 sculpt_undo_bmesh_enable(ob, unode);
328
329                 /* Restore the mesh from the last log entry */
330                 BM_log_undo(ss->bm, ss->bm_log);
331
332                 unode->applied = FALSE;
333         }
334         else {
335                 /* Disable dynamic topology sculpting */
336                 sculpt_dynamic_topology_disable(C, NULL);
337                 unode->applied = TRUE;
338         }
339 }
340
341 /* Handle all dynamic-topology updates
342  *
343  * Returns TRUE if this was a dynamic-topology undo step, otherwise
344  * returns FALSE to indicate the non-dyntopo code should run. */
345 static int sculpt_undo_bmesh_restore(bContext *C,
346                                                                          SculptUndoNode *unode,
347                                                                          Object *ob,
348                                                                          SculptSession *ss)
349 {
350         switch (unode->type) {
351                 case SCULPT_UNDO_DYNTOPO_BEGIN:
352                         sculpt_undo_bmesh_restore_begin(C, unode, ob, ss);
353                         return TRUE;
354
355                 case SCULPT_UNDO_DYNTOPO_END:
356                         sculpt_undo_bmesh_restore_end(C, unode, ob, ss);
357                         return TRUE;
358
359                 default:
360                         if (ss->bm_log) {
361                                 sculpt_undo_bmesh_restore_generic(unode, ob, ss);
362                                 return TRUE;
363                         }
364                         break;
365         }
366
367         return FALSE;
368 }
369
370 static void sculpt_undo_restore(bContext *C, ListBase *lb)
371 {
372         Scene *scene = CTX_data_scene(C);
373         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
374         Object *ob = CTX_data_active_object(C);
375         DerivedMesh *dm;
376         SculptSession *ss = ob->sculpt;
377         SculptUndoNode *unode;
378         MultiresModifierData *mmd;
379         int update = FALSE, rebuild = FALSE;
380         int need_mask = FALSE;
381
382         for (unode = lb->first; unode; unode = unode->next) {
383                 if (strcmp(unode->idname, ob->id.name) == 0) {
384                         if (unode->type == SCULPT_UNDO_MASK) {
385                                 /* is possible that we can't do the mask undo (below)
386                                  * because of the vertex count */
387                                 need_mask = TRUE;
388                                 break;
389                         }
390                 }
391         }
392
393         sculpt_update_mesh_elements(scene, sd, ob, 0, need_mask);
394
395         /* call _after_ sculpt_update_mesh_elements() which may update 'ob->derivedFinal' */
396         dm = mesh_get_derived_final(scene, ob, 0);
397
398         if (lb->first && sculpt_undo_bmesh_restore(C, lb->first, ob, ss))
399                 return;
400
401         for (unode = lb->first; unode; unode = unode->next) {
402                 if (!(strcmp(unode->idname, ob->id.name) == 0))
403                         continue;
404
405                 /* check if undo data matches current data well enough to
406                  * continue */
407                 if (unode->maxvert) {
408                         if (ss->totvert != unode->maxvert)
409                                 continue;
410                 }
411                 else if (unode->maxgrid && dm->getGridData) {
412                         if ((dm->getNumGrids(dm) != unode->maxgrid) ||
413                             (dm->getGridSize(dm) != unode->gridsize))
414                         {
415                                 continue;
416                         }
417                 }
418
419                 switch (unode->type) {
420                         case SCULPT_UNDO_COORDS:
421                                 if (sculpt_undo_restore_coords(C, dm, unode))
422                                         update = TRUE;
423                                 break;
424                         case SCULPT_UNDO_HIDDEN:
425                                 if (sculpt_undo_restore_hidden(C, dm, unode))
426                                         rebuild = TRUE;
427                                 break;
428                         case SCULPT_UNDO_MASK:
429                                 if (sculpt_undo_restore_mask(C, dm, unode))
430                                         update = TRUE;
431                                 break;
432
433                         case SCULPT_UNDO_DYNTOPO_BEGIN:
434                         case SCULPT_UNDO_DYNTOPO_END:
435                         case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
436                                 BLI_assert(!"Dynamic topology should've already been handled");
437                                 break;
438                 }
439         }
440
441         if (update || rebuild) {
442                 int tag_update = 0;
443                 /* we update all nodes still, should be more clever, but also
444                  * needs to work correct when exiting/entering sculpt mode and
445                  * the nodes get recreated, though in that case it could do all */
446                 BKE_pbvh_search_callback(ss->pbvh, NULL, NULL, update_cb, &rebuild);
447                 BKE_pbvh_update(ss->pbvh, PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw, NULL);
448
449                 if ((mmd = sculpt_multires_active(scene, ob))) {
450                         if (rebuild)
451                                 multires_mark_as_modified(ob, MULTIRES_HIDDEN_MODIFIED);
452                         else
453                                 multires_mark_as_modified(ob, MULTIRES_COORDS_MODIFIED);
454                 }
455
456                 tag_update = ((Mesh *)ob->data)->id.us > 1;
457
458                 if (ss->modifiers_active) {
459                         Mesh *mesh = ob->data;
460                         BKE_mesh_calc_normals_tessface(mesh->mvert, mesh->totvert,
461                                                        mesh->mface, mesh->totface, NULL);
462
463                         free_sculptsession_deformMats(ss);
464                         tag_update |= 1;
465                 }
466
467                 if (tag_update)
468                         DAG_id_tag_update(&ob->id, OB_RECALC_DATA);
469
470                 /* for non-PBVH drawing, need to recreate VBOs */
471                 GPU_drawobject_free(ob->derivedFinal);
472         }
473 }
474
475 static void sculpt_undo_free(ListBase *lb)
476 {
477         SculptUndoNode *unode;
478         int i;
479
480         for (unode = lb->first; unode; unode = unode->next) {
481                 if (unode->co)
482                         MEM_freeN(unode->co);
483                 if (unode->no)
484                         MEM_freeN(unode->no);
485                 if (unode->index)
486                         MEM_freeN(unode->index);
487                 if (unode->grids)
488                         MEM_freeN(unode->grids);
489                 if (unode->orig_co)
490                         MEM_freeN(unode->orig_co);
491                 if (unode->vert_hidden)
492                         MEM_freeN(unode->vert_hidden);
493                 if (unode->grid_hidden) {
494                         for (i = 0; i < unode->totgrid; i++) {
495                                 if (unode->grid_hidden[i])
496                                         MEM_freeN(unode->grid_hidden[i]);
497                         }
498                         MEM_freeN(unode->grid_hidden);
499                 }
500                 if (unode->mask)
501                         MEM_freeN(unode->mask);
502                 if (unode->bm_entry) {
503                         BM_log_entry_drop(unode->bm_entry);
504                 }
505                 if (unode->bm_enter_totvert)
506                         CustomData_free(&unode->bm_enter_vdata, unode->bm_enter_totvert);
507                 if (unode->bm_enter_totedge)
508                         CustomData_free(&unode->bm_enter_edata, unode->bm_enter_totedge);
509                 if (unode->bm_enter_totloop)
510                         CustomData_free(&unode->bm_enter_ldata, unode->bm_enter_totloop);
511                 if (unode->bm_enter_totpoly)
512                         CustomData_free(&unode->bm_enter_pdata, unode->bm_enter_totpoly);
513         }
514 }
515
516 SculptUndoNode *sculpt_undo_get_node(PBVHNode *node)
517 {
518         ListBase *lb = undo_paint_push_get_list(UNDO_PAINT_MESH);
519
520         if (!lb) {
521                 return NULL;
522         }
523
524         return BLI_findptr(lb, node, offsetof(SculptUndoNode, node));
525 }
526
527 static void sculpt_undo_alloc_and_store_hidden(PBVH *pbvh,
528                                                SculptUndoNode *unode)
529 {
530         PBVHNode *node = unode->node;
531         BLI_bitmap *grid_hidden;
532         int i, *grid_indices, totgrid;
533
534         grid_hidden = BKE_pbvh_grid_hidden(pbvh);
535
536         BKE_pbvh_node_get_grids(pbvh, node, &grid_indices, &totgrid,
537                                 NULL, NULL, NULL, NULL);
538                         
539         unode->grid_hidden = MEM_mapallocN(sizeof(BLI_bitmap) * totgrid,
540                                            "unode->grid_hidden");
541                 
542         for (i = 0; i < totgrid; i++) {
543                 if (grid_hidden[grid_indices[i]])
544                         unode->grid_hidden[i] = MEM_dupallocN(grid_hidden[grid_indices[i]]);
545                 else
546                         unode->grid_hidden[i] = NULL;
547         }
548 }
549
550 static SculptUndoNode *sculpt_undo_alloc_node(Object *ob, PBVHNode *node,
551                                               SculptUndoType type)
552 {
553         ListBase *lb = undo_paint_push_get_list(UNDO_PAINT_MESH);
554         SculptUndoNode *unode;
555         SculptSession *ss = ob->sculpt;
556         int totvert, allvert, totgrid, maxgrid, gridsize, *grids;
557         
558         unode = MEM_callocN(sizeof(SculptUndoNode), "SculptUndoNode");
559         BLI_strncpy(unode->idname, ob->id.name, sizeof(unode->idname));
560         unode->type = type;
561         unode->node = node;
562
563         if (node) {
564                 BKE_pbvh_node_num_verts(ss->pbvh, node, &totvert, &allvert);
565                 BKE_pbvh_node_get_grids(ss->pbvh, node, &grids, &totgrid,
566                                                                 &maxgrid, &gridsize, NULL, NULL);
567
568                 unode->totvert = totvert;
569         }
570         else
571                 maxgrid = 0;
572         
573         /* we will use this while sculpting, is mapalloc slow to access then? */
574
575         /* general TODO, fix count_alloc */
576         switch (type) {
577                 case SCULPT_UNDO_COORDS:
578                         unode->co = MEM_mapallocN(sizeof(float) * 3 * allvert, "SculptUndoNode.co");
579                         unode->no = MEM_mapallocN(sizeof(short) * 3 * allvert, "SculptUndoNode.no");
580                         undo_paint_push_count_alloc(UNDO_PAINT_MESH,
581                                                     (sizeof(float) * 3 +
582                                                      sizeof(short) * 3 +
583                                                      sizeof(int)) * allvert);
584                         break;
585                 case SCULPT_UNDO_HIDDEN:
586                         if (maxgrid)
587                                 sculpt_undo_alloc_and_store_hidden(ss->pbvh, unode);
588                         else
589                                 unode->vert_hidden = BLI_BITMAP_NEW(allvert, "SculptUndoNode.vert_hidden");
590                 
591                         break;
592                 case SCULPT_UNDO_MASK:
593                         unode->mask = MEM_mapallocN(sizeof(float) * allvert, "SculptUndoNode.mask");
594                         undo_paint_push_count_alloc(UNDO_PAINT_MESH, (sizeof(float) * sizeof(int)) * allvert);
595                         break;
596                 case SCULPT_UNDO_DYNTOPO_BEGIN:
597                 case SCULPT_UNDO_DYNTOPO_END:
598                 case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
599                         BLI_assert(!"Dynamic topology should've already been handled");
600                         break;
601         }
602         
603         BLI_addtail(lb, unode);
604
605         if (maxgrid) {
606                 /* multires */
607                 unode->maxgrid = maxgrid;
608                 unode->totgrid = totgrid;
609                 unode->gridsize = gridsize;
610                 unode->grids = MEM_mapallocN(sizeof(int) * totgrid, "SculptUndoNode.grids");
611         }
612         else {
613                 /* regular mesh */
614                 unode->maxvert = ss->totvert;
615                 unode->index = MEM_mapallocN(sizeof(int) * allvert, "SculptUndoNode.index");
616         }
617
618         if (ss->modifiers_active)
619                 unode->orig_co = MEM_callocN(allvert * sizeof(*unode->orig_co), "undoSculpt orig_cos");
620
621         return unode;
622 }
623
624 static void sculpt_undo_store_coords(Object *ob, SculptUndoNode *unode)
625 {
626         SculptSession *ss = ob->sculpt;
627         PBVHVertexIter vd;
628
629         BKE_pbvh_vertex_iter_begin(ss->pbvh, unode->node, vd, PBVH_ITER_ALL)
630         {
631                 copy_v3_v3(unode->co[vd.i], vd.co);
632                 if (vd.no) copy_v3_v3_short(unode->no[vd.i], vd.no);
633                 else normal_float_to_short_v3(unode->no[vd.i], vd.fno);
634
635                 if (ss->modifiers_active)
636                         copy_v3_v3(unode->orig_co[vd.i], ss->orig_cos[unode->index[vd.i]]);
637         }
638         BKE_pbvh_vertex_iter_end;
639 }
640
641 static void sculpt_undo_store_hidden(Object *ob, SculptUndoNode *unode)
642 {
643         PBVH *pbvh = ob->sculpt->pbvh;
644         PBVHNode *node = unode->node;
645
646         if (unode->grids) {
647                 /* already stored during allocation */
648         }
649         else {
650                 MVert *mvert;
651                 int *vert_indices, allvert;
652                 int i;
653                 
654                 BKE_pbvh_node_num_verts(pbvh, node, NULL, &allvert);
655                 BKE_pbvh_node_get_verts(pbvh, node, &vert_indices, &mvert);
656                 for (i = 0; i < allvert; i++) {
657                         BLI_BITMAP_MODIFY(unode->vert_hidden, i,
658                                           mvert[vert_indices[i]].flag & ME_HIDE);
659                 }
660         }
661 }
662
663 static void sculpt_undo_store_mask(Object *ob, SculptUndoNode *unode)
664 {
665         SculptSession *ss = ob->sculpt;
666         PBVHVertexIter vd;
667
668         BKE_pbvh_vertex_iter_begin(ss->pbvh, unode->node, vd, PBVH_ITER_ALL)
669         {
670                 unode->mask[vd.i] = *vd.mask;
671         }
672         BKE_pbvh_vertex_iter_end;
673 }
674
675 static SculptUndoNode *sculpt_undo_bmesh_push(Object *ob,
676                                                                                           PBVHNode *node,
677                                                                                           SculptUndoType type)
678 {
679         ListBase *lb = undo_paint_push_get_list(UNDO_PAINT_MESH);
680         SculptUndoNode *unode = lb->first;
681         SculptSession *ss = ob->sculpt;
682         PBVHVertexIter vd;
683
684         if (!lb->first) {
685                 unode = MEM_callocN(sizeof(*unode), AT);
686
687                 BLI_strncpy(unode->idname, ob->id.name, sizeof(unode->idname));
688                 unode->type = type;
689                 unode->applied = TRUE;
690
691                 if (type == SCULPT_UNDO_DYNTOPO_END) {
692                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
693                         BM_log_before_all_removed(ss->bm, ss->bm_log);
694                 }
695                 else if (type == SCULPT_UNDO_DYNTOPO_BEGIN) {
696                         Mesh *me = ob->data;
697
698                         /* Store a copy of the mesh's current vertices, loops, and
699                          * polys. A full copy like this is needed because entering
700                          * dynamic-topology immediately does topological edits
701                          * (converting polys to triangles) that the BMLog can't
702                          * fully restore from */
703                         CustomData_copy(&me->vdata, &unode->bm_enter_vdata, CD_MASK_MESH,
704                                                         CD_DUPLICATE, me->totvert);
705                         CustomData_copy(&me->edata, &unode->bm_enter_edata, CD_MASK_MESH,
706                                                         CD_DUPLICATE, me->totedge);
707                         CustomData_copy(&me->ldata, &unode->bm_enter_ldata, CD_MASK_MESH,
708                                                         CD_DUPLICATE, me->totloop);
709                         CustomData_copy(&me->pdata, &unode->bm_enter_pdata, CD_MASK_MESH,
710                                                         CD_DUPLICATE, me->totpoly);
711                         unode->bm_enter_totvert = me->totvert;
712                         unode->bm_enter_totedge = me->totedge;
713                         unode->bm_enter_totloop = me->totloop;
714                         unode->bm_enter_totpoly = me->totpoly;
715
716                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
717                         BM_log_all_added(ss->bm, ss->bm_log);
718                 }
719                 else {
720                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
721                 }
722
723                 BLI_addtail(lb, unode);
724         }
725
726         if (node) {
727                 switch (type) {
728                         case SCULPT_UNDO_COORDS:
729                         case SCULPT_UNDO_HIDDEN:
730                         case SCULPT_UNDO_MASK:
731                                 /* Before any vertex values get modified, ensure their
732                                  * original positions are logged */
733                                 BKE_pbvh_vertex_iter_begin(ss->pbvh, node, vd, PBVH_ITER_ALL) {
734                                         BM_log_vert_before_modified(ss->bm, ss->bm_log, vd.bm_vert);
735                                 }
736                                 BKE_pbvh_vertex_iter_end;
737                                 break;
738
739                         case SCULPT_UNDO_DYNTOPO_BEGIN:
740                         case SCULPT_UNDO_DYNTOPO_END:
741                         case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
742                                 break;
743                 }
744         }
745
746         return unode;
747 }
748
749 SculptUndoNode *sculpt_undo_push_node(Object *ob, PBVHNode *node,
750                                       SculptUndoType type)
751 {
752         SculptSession *ss = ob->sculpt;
753         SculptUndoNode *unode;
754
755         /* list is manipulated by multiple threads, so we lock */
756         BLI_lock_thread(LOCK_CUSTOM1);
757
758         if (ss->bm ||
759                 ELEM(type,
760                          SCULPT_UNDO_DYNTOPO_BEGIN,
761                          SCULPT_UNDO_DYNTOPO_END))
762         {
763                 /* Dynamic topology stores only one undo node per stroke,
764                  * regardless of the number of PBVH nodes modified */
765                 unode = sculpt_undo_bmesh_push(ob, node, type);
766                 BLI_unlock_thread(LOCK_CUSTOM1);
767                 return unode;
768         }
769         else if ((unode = sculpt_undo_get_node(node))) {
770                 BLI_unlock_thread(LOCK_CUSTOM1);
771                 return unode;
772         }
773
774         unode = sculpt_undo_alloc_node(ob, node, type);
775         
776         BLI_unlock_thread(LOCK_CUSTOM1);
777
778         /* copy threaded, hopefully this is the performance critical part */
779
780         if (unode->grids) {
781                 int totgrid, *grids;
782                 BKE_pbvh_node_get_grids(ss->pbvh, node, &grids, &totgrid,
783                                         NULL, NULL, NULL, NULL);
784                 memcpy(unode->grids, grids, sizeof(int) * totgrid);
785         }
786         else {
787                 int *vert_indices, allvert;
788                 BKE_pbvh_node_num_verts(ss->pbvh, node, NULL, &allvert);
789                 BKE_pbvh_node_get_verts(ss->pbvh, node, &vert_indices, NULL);
790                 memcpy(unode->index, vert_indices, sizeof(int) * unode->totvert);
791         }
792
793         switch (type) {
794                 case SCULPT_UNDO_COORDS:
795                         sculpt_undo_store_coords(ob, unode);
796                         break;
797                 case SCULPT_UNDO_HIDDEN:
798                         sculpt_undo_store_hidden(ob, unode);
799                         break;
800                 case SCULPT_UNDO_MASK:
801                         sculpt_undo_store_mask(ob, unode);
802                         break;
803                 case SCULPT_UNDO_DYNTOPO_BEGIN:
804                 case SCULPT_UNDO_DYNTOPO_END:
805                 case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
806                         BLI_assert(!"Dynamic topology should've already been handled");
807                         break;
808         }
809
810         /* store active shape key */
811         if (ss->kb) BLI_strncpy(unode->shapeName, ss->kb->name, sizeof(ss->kb->name));
812         else unode->shapeName[0] = '\0';
813
814         return unode;
815 }
816
817 void sculpt_undo_push_begin(const char *name)
818 {
819         undo_paint_push_begin(UNDO_PAINT_MESH, name,
820                               sculpt_undo_restore, sculpt_undo_free);
821 }
822
823 void sculpt_undo_push_end(void)
824 {
825         ListBase *lb = undo_paint_push_get_list(UNDO_PAINT_MESH);
826         SculptUndoNode *unode;
827
828         /* we don't need normals in the undo stack */
829         for (unode = lb->first; unode; unode = unode->next) {
830                 if (unode->no) {
831                         MEM_freeN(unode->no);
832                         unode->no = NULL;
833                 }
834
835                 if (unode->node)
836                         BKE_pbvh_node_layer_disp_free(unode->node);
837         }
838
839         undo_paint_push_end(UNDO_PAINT_MESH);
840 }