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