Fix sculpt undo steps not enabling dyntopo
[blender.git] / source / blender / editors / sculpt_paint / sculpt_undo.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software  Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2006 by Nicholas Bishop
17  * All rights reserved.
18  * Implements the Sculpt Mode tools
19  */
20
21 /** \file \ingroup edsculpt
22  */
23
24 #include <stddef.h>
25
26 #include "MEM_guardedalloc.h"
27
28 #include "BLI_math.h"
29 #include "BLI_utildefines.h"
30 #include "BLI_string.h"
31 #include "BLI_listbase.h"
32 #include "BLI_ghash.h"
33 #include "BLI_task.h"
34 #include "BLI_threads.h"
35
36 #include "DNA_meshdata_types.h"
37 #include "DNA_object_types.h"
38 #include "DNA_scene_types.h"
39 #include "DNA_mesh_types.h"
40 #include "DNA_screen_types.h"
41 #include "DNA_space_types.h"
42 #include "DNA_workspace_types.h"
43
44 #include "BKE_ccg.h"
45 #include "BKE_context.h"
46 #include "BKE_multires.h"
47 #include "BKE_paint.h"
48 #include "BKE_key.h"
49 #include "BKE_mesh.h"
50 #include "BKE_mesh_runtime.h"
51 #include "BKE_scene.h"
52 #include "BKE_subsurf.h"
53 #include "BKE_subdiv_ccg.h"
54 #include "BKE_undo_system.h"
55 #include "BKE_global.h"
56 #include "BKE_main.h"
57
58 #include "DEG_depsgraph.h"
59
60 #include "WM_api.h"
61 #include "WM_types.h"
62
63 #include "ED_paint.h"
64 #include "ED_object.h"
65 #include "ED_sculpt.h"
66 #include "ED_undo.h"
67
68 #include "bmesh.h"
69 #include "paint_intern.h"
70 #include "sculpt_intern.h"
71
72
73 typedef struct UndoSculpt {
74         ListBase nodes;
75
76         size_t undo_size;
77 } UndoSculpt;
78
79 static UndoSculpt *sculpt_undo_get_nodes(void);
80
81 static void update_cb(PBVHNode *node, void *rebuild)
82 {
83         BKE_pbvh_node_mark_update(node);
84         if (*((bool *)rebuild))
85                 BKE_pbvh_node_mark_rebuild_draw(node);
86         BKE_pbvh_node_fully_hidden_set(node, 0);
87 }
88
89 struct PartialUpdateData {
90         PBVH *pbvh;
91         bool rebuild;
92 };
93
94 /**
95  * A version of #update_cb that tests for 'ME_VERT_PBVH_UPDATE'
96  */
97 static void update_cb_partial(PBVHNode *node, void *userdata)
98 {
99         struct PartialUpdateData *data = userdata;
100         if (BKE_pbvh_node_vert_update_check_any(data->pbvh, node)) {
101                 update_cb(node, &(data->rebuild));
102         }
103 }
104
105 static bool test_swap_v3_v3(float a[3], float b[3])
106 {
107         /* no need for float comparison here (memory is exactly equal or not) */
108         if (memcmp(a, b, sizeof(float[3])) != 0) {
109                 swap_v3_v3(a, b);
110                 return true;
111         }
112         else {
113                 return false;
114         }
115 }
116
117 static bool sculpt_undo_restore_deformed(
118         const SculptSession *ss,
119         SculptUndoNode *unode,
120         int uindex, int oindex,
121         float coord[3])
122 {
123         if (test_swap_v3_v3(coord, unode->orig_co[uindex])) {
124                 copy_v3_v3(unode->co[uindex], ss->deform_cos[oindex]);
125                 return true;
126         }
127         else {
128                 return false;
129         }
130 }
131
132 static bool sculpt_undo_restore_coords(bContext *C, SculptUndoNode *unode)
133 {
134         Scene *scene = CTX_data_scene(C);
135         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
136         ViewLayer *view_layer = CTX_data_view_layer(C);
137         Object *ob = OBACT(view_layer);
138         Depsgraph *depsgraph = CTX_data_depsgraph(C);
139         SculptSession *ss = ob->sculpt;
140         SubdivCCG *subdiv_ccg = ss->subdiv_ccg;
141         MVert *mvert;
142         int *index;
143
144         if (unode->maxvert) {
145                 /* regular mesh restore */
146
147                 if (ss->kb && !STREQ(ss->kb->name, unode->shapeName)) {
148                         /* shape key has been changed before calling undo operator */
149
150                         Key *key = BKE_key_from_object(ob);
151                         KeyBlock *kb = key ? BKE_keyblock_find_name(key, unode->shapeName) : NULL;
152
153                         if (kb) {
154                                 ob->shapenr = BLI_findindex(&key->block, kb) + 1;
155
156                                 BKE_sculpt_update_mesh_elements(depsgraph, scene, sd, ob, false, false);
157                                 WM_event_add_notifier(C, NC_OBJECT | ND_DATA, ob);
158                         }
159                         else {
160                                 /* key has been removed -- skip this undo node */
161                                 return 0;
162                         }
163                 }
164
165                 /* no need for float comparison here (memory is exactly equal or not) */
166                 index = unode->index;
167                 mvert = ss->mvert;
168
169                 if (ss->kb) {
170                         float (*vertCos)[3];
171                         vertCos = BKE_keyblock_convert_to_vertcos(ob, ss->kb);
172
173                         if (unode->orig_co) {
174                                 if (ss->modifiers_active) {
175                                         for (int i = 0; i < unode->totvert; i++) {
176                                                 sculpt_undo_restore_deformed(ss, unode, i, index[i], vertCos[index[i]]);
177                                         }
178                                 }
179                                 else {
180                                         for (int i = 0; i < unode->totvert; i++) {
181                                                 swap_v3_v3(vertCos[index[i]], unode->orig_co[i]);
182                                         }
183                                 }
184                         }
185                         else {
186                                 for (int i = 0; i < unode->totvert; i++) {
187                                         swap_v3_v3(vertCos[index[i]], unode->co[i]);
188                                 }
189                         }
190
191                         /* propagate new coords to keyblock */
192                         sculpt_vertcos_to_key(ob, ss->kb, vertCos);
193
194                         /* pbvh uses it's own mvert array, so coords should be */
195                         /* propagated to pbvh here */
196                         BKE_pbvh_apply_vertCos(ss->pbvh, vertCos, unode->totvert);
197
198                         MEM_freeN(vertCos);
199                 }
200                 else {
201                         if (unode->orig_co) {
202                                 if (ss->modifiers_active) {
203                                         for (int i = 0; i < unode->totvert; i++) {
204                                                 if (sculpt_undo_restore_deformed(ss, unode, i, index[i], mvert[index[i]].co)) {
205                                                         mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
206                                                 }
207                                         }
208                                 }
209                                 else {
210                                         for (int i = 0; i < unode->totvert; i++) {
211                                                 if (test_swap_v3_v3(mvert[index[i]].co, unode->orig_co[i])) {
212                                                         mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
213                                                 }
214                                         }
215                                 }
216                         }
217                         else {
218                                 for (int i = 0; i < unode->totvert; i++) {
219                                         if (test_swap_v3_v3(mvert[index[i]].co, unode->co[i])) {
220                                                 mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
221                                         }
222                                 }
223                         }
224                 }
225         }
226         else if (unode->maxgrid && subdiv_ccg != NULL) {
227                 /* multires restore */
228                 CCGElem **grids, *grid;
229                 CCGKey key;
230                 float (*co)[3];
231                 int gridsize;
232
233                 grids = subdiv_ccg->grids;
234                 gridsize = subdiv_ccg->grid_size;
235                 BKE_subdiv_ccg_key_top_level(&key, subdiv_ccg);
236
237                 co = unode->co;
238                 for (int j = 0; j < unode->totgrid; j++) {
239                         grid = grids[unode->grids[j]];
240
241                         for (int i = 0; i < gridsize * gridsize; i++, co++) {
242                                 swap_v3_v3(CCG_elem_offset_co(&key, grid, i), co[0]);
243                         }
244                 }
245         }
246
247         return 1;
248 }
249
250 static bool sculpt_undo_restore_hidden(
251         bContext *C,
252         SculptUndoNode *unode)
253 {
254         ViewLayer *view_layer = CTX_data_view_layer(C);
255         Object *ob = OBACT(view_layer);
256         SculptSession *ss = ob->sculpt;
257         SubdivCCG *subdiv_ccg = ss->subdiv_ccg;
258         int i;
259
260         if (unode->maxvert) {
261                 MVert *mvert = ss->mvert;
262
263                 for (i = 0; i < unode->totvert; i++) {
264                         MVert *v = &mvert[unode->index[i]];
265                         if ((BLI_BITMAP_TEST(unode->vert_hidden, i) != 0) != ((v->flag & ME_HIDE) != 0)) {
266                                 BLI_BITMAP_FLIP(unode->vert_hidden, i);
267                                 v->flag ^= ME_HIDE;
268                                 v->flag |= ME_VERT_PBVH_UPDATE;
269                         }
270                 }
271         }
272         else if (unode->maxgrid && subdiv_ccg != NULL) {
273                 BLI_bitmap **grid_hidden = subdiv_ccg->grid_hidden;
274
275                 for (i = 0; i < unode->totgrid; i++) {
276                         SWAP(BLI_bitmap *,
277                              unode->grid_hidden[i],
278                              grid_hidden[unode->grids[i]]);
279
280                 }
281         }
282
283         return 1;
284 }
285
286 static bool sculpt_undo_restore_mask(bContext *C, SculptUndoNode *unode)
287 {
288         ViewLayer *view_layer = CTX_data_view_layer(C);
289         Object *ob = OBACT(view_layer);
290         SculptSession *ss = ob->sculpt;
291         SubdivCCG *subdiv_ccg = ss->subdiv_ccg;
292         MVert *mvert;
293         float *vmask;
294         int *index, i, j;
295
296         if (unode->maxvert) {
297                 /* regular mesh restore */
298
299                 index = unode->index;
300                 mvert = ss->mvert;
301                 vmask = ss->vmask;
302
303                 for (i = 0; i < unode->totvert; i++) {
304                         if (vmask[index[i]] != unode->mask[i]) {
305                                 SWAP(float, vmask[index[i]], unode->mask[i]);
306                                 mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
307                         }
308                 }
309         }
310         else if (unode->maxgrid && subdiv_ccg != NULL) {
311                 /* multires restore */
312                 CCGElem **grids, *grid;
313                 CCGKey key;
314                 float *mask;
315                 int gridsize;
316
317                 grids = subdiv_ccg->grids;
318                 gridsize = subdiv_ccg->grid_size;
319                 BKE_subdiv_ccg_key_top_level(&key, subdiv_ccg);
320
321                 mask = unode->mask;
322                 for (j = 0; j < unode->totgrid; j++) {
323                         grid = grids[unode->grids[j]];
324
325                         for (i = 0; i < gridsize * gridsize; i++, mask++)
326                                 SWAP(float, *CCG_elem_offset_mask(&key, grid, i), *mask);
327                 }
328         }
329
330         return 1;
331 }
332
333 static void sculpt_undo_bmesh_restore_generic_task_cb(
334         void *__restrict userdata,
335         const int n,
336         const ParallelRangeTLS *__restrict UNUSED(tls))
337 {
338         PBVHNode **nodes = userdata;
339
340         BKE_pbvh_node_mark_redraw(nodes[n]);
341 }
342
343 static void sculpt_undo_bmesh_restore_generic(bContext *C,
344                                               SculptUndoNode *unode,
345                                               Object *ob,
346                                               SculptSession *ss)
347 {
348         if (unode->applied) {
349                 BM_log_undo(ss->bm, ss->bm_log);
350                 unode->applied = false;
351         }
352         else {
353                 BM_log_redo(ss->bm, ss->bm_log);
354                 unode->applied = true;
355         }
356
357         if (unode->type == SCULPT_UNDO_MASK) {
358                 int totnode;
359                 PBVHNode **nodes;
360                 Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
361
362                 BKE_pbvh_search_gather(ss->pbvh, NULL, NULL, &nodes, &totnode);
363
364                 ParallelRangeSettings settings;
365                 BLI_parallel_range_settings_defaults(&settings);
366                 settings.use_threading = ((sd->flags & SCULPT_USE_OPENMP) && totnode > SCULPT_THREADED_LIMIT);
367                 BLI_task_parallel_range(
368                             0, totnode,
369                             nodes,
370                             sculpt_undo_bmesh_restore_generic_task_cb,
371                             &settings);
372
373                 if (nodes)
374                         MEM_freeN(nodes);
375         }
376         else {
377                 sculpt_pbvh_clear(ob);
378         }
379 }
380
381 /* Create empty sculpt BMesh and enable logging */
382 static void sculpt_undo_bmesh_enable(
383         Object *ob, SculptUndoNode *unode)
384 {
385         SculptSession *ss = ob->sculpt;
386         Mesh *me = ob->data;
387
388         sculpt_pbvh_clear(ob);
389
390         /* Create empty BMesh and enable logging */
391         ss->bm = BM_mesh_create(
392                 &bm_mesh_allocsize_default,
393                 &((struct BMeshCreateParams){.use_toolflags = false,}));
394         BM_data_layer_add(ss->bm, &ss->bm->vdata, CD_PAINT_MASK);
395         sculpt_dyntopo_node_layers_add(ss);
396         me->flag |= ME_SCULPT_DYNAMIC_TOPOLOGY;
397
398         /* Restore the BMLog using saved entries */
399         ss->bm_log = BM_log_from_existing_entries_create(ss->bm,
400                                                          unode->bm_entry);
401 }
402
403 static void sculpt_undo_bmesh_restore_begin(bContext *C,
404                                             SculptUndoNode *unode,
405                                             Object *ob,
406                                             SculptSession *ss)
407 {
408         if (unode->applied) {
409                 sculpt_dynamic_topology_disable(C, unode);
410                 unode->applied = false;
411         }
412         else {
413                 sculpt_undo_bmesh_enable(ob, unode);
414
415                 /* Restore the mesh from the first log entry */
416                 BM_log_redo(ss->bm, ss->bm_log);
417
418                 unode->applied = true;
419         }
420 }
421
422 static void sculpt_undo_bmesh_restore_end(bContext *C,
423                                           SculptUndoNode *unode,
424                                           Object *ob,
425                                           SculptSession *ss)
426 {
427         if (unode->applied) {
428                 sculpt_undo_bmesh_enable(ob, unode);
429
430                 /* Restore the mesh from the last log entry */
431                 BM_log_undo(ss->bm, ss->bm_log);
432
433                 unode->applied = false;
434         }
435         else {
436                 /* Disable dynamic topology sculpting */
437                 sculpt_dynamic_topology_disable(C, NULL);
438                 unode->applied = true;
439         }
440 }
441
442 /* Handle all dynamic-topology updates
443  *
444  * Returns true if this was a dynamic-topology undo step, otherwise
445  * returns false to indicate the non-dyntopo code should run. */
446 static int sculpt_undo_bmesh_restore(bContext *C,
447                                      SculptUndoNode *unode,
448                                      Object *ob,
449                                      SculptSession *ss)
450 {
451         switch (unode->type) {
452                 case SCULPT_UNDO_DYNTOPO_BEGIN:
453                         sculpt_undo_bmesh_restore_begin(C, unode, ob, ss);
454                         return true;
455
456                 case SCULPT_UNDO_DYNTOPO_END:
457                         sculpt_undo_bmesh_restore_end(C, unode, ob, ss);
458                         return true;
459
460                 default:
461                         if (ss->bm_log) {
462                                 sculpt_undo_bmesh_restore_generic(C, unode, ob, ss);
463                                 return true;
464                         }
465                         break;
466         }
467
468         return false;
469 }
470
471 static void sculpt_undo_restore_list(bContext *C, ListBase *lb)
472 {
473         Scene *scene = CTX_data_scene(C);
474         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
475         ViewLayer *view_layer = CTX_data_view_layer(C);
476         Object *ob = OBACT(view_layer);
477         Depsgraph *depsgraph = CTX_data_depsgraph(C);
478         SculptSession *ss = ob->sculpt;
479         SubdivCCG *subdiv_ccg = ss->subdiv_ccg;
480         SculptUndoNode *unode;
481         bool update = false, rebuild = false;
482         bool need_mask = false;
483         bool partial_update = true;
484
485         for (unode = lb->first; unode; unode = unode->next) {
486                 if (STREQ(unode->idname, ob->id.name)) {
487                         if (unode->type == SCULPT_UNDO_MASK) {
488                                 /* is possible that we can't do the mask undo (below)
489                                  * because of the vertex count */
490                                 need_mask = true;
491                                 break;
492                         }
493                 }
494         }
495
496         DEG_id_tag_update(&ob->id, ID_RECALC_SHADING);
497
498         BKE_sculpt_update_mesh_elements(depsgraph, scene, sd, ob, false, need_mask);
499
500         if (lb->first && sculpt_undo_bmesh_restore(C, lb->first, ob, ss))
501                 return;
502
503         for (unode = lb->first; unode; unode = unode->next) {
504                 if (!STREQ(unode->idname, ob->id.name))
505                         continue;
506
507                 /* check if undo data matches current data well enough to
508                  * continue */
509                 if (unode->maxvert) {
510                         if (ss->totvert != unode->maxvert)
511                                 continue;
512                 }
513                 else if (unode->maxgrid && subdiv_ccg != NULL) {
514                         if ((subdiv_ccg->num_grids != unode->maxgrid) ||
515                             (subdiv_ccg->grid_size != unode->gridsize))
516                         {
517                                 continue;
518                         }
519
520                         /* multi-res can't do partial updates since it doesn't flag edited vertices */
521                         partial_update = false;
522                 }
523
524                 switch (unode->type) {
525                         case SCULPT_UNDO_COORDS:
526                                 if (sculpt_undo_restore_coords(C, unode))
527                                         update = true;
528                                 break;
529                         case SCULPT_UNDO_HIDDEN:
530                                 if (sculpt_undo_restore_hidden(C, unode))
531                                         rebuild = true;
532                                 break;
533                         case SCULPT_UNDO_MASK:
534                                 if (sculpt_undo_restore_mask(C, unode))
535                                         update = true;
536                                 break;
537
538                         case SCULPT_UNDO_DYNTOPO_BEGIN:
539                         case SCULPT_UNDO_DYNTOPO_END:
540                         case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
541                                 BLI_assert(!"Dynamic topology should've already been handled");
542                                 break;
543                 }
544         }
545
546         if (update || rebuild) {
547                 bool tag_update = false;
548                 /* we update all nodes still, should be more clever, but also
549                  * needs to work correct when exiting/entering sculpt mode and
550                  * the nodes get recreated, though in that case it could do all */
551                 if (partial_update) {
552                         struct PartialUpdateData data = {
553                                 .rebuild = rebuild,
554                                 .pbvh = ss->pbvh,
555                         };
556                         BKE_pbvh_search_callback(ss->pbvh, NULL, NULL, update_cb_partial, &data);
557                 }
558                 else {
559                         BKE_pbvh_search_callback(ss->pbvh, NULL, NULL, update_cb, &rebuild);
560                 }
561                 BKE_pbvh_update(ss->pbvh, PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw | PBVH_UpdateNormals, NULL);
562
563                 if (BKE_sculpt_multires_active(scene, ob)) {
564                         if (rebuild)
565                                 multires_mark_as_modified(ob, MULTIRES_HIDDEN_MODIFIED);
566                         else
567                                 multires_mark_as_modified(ob, MULTIRES_COORDS_MODIFIED);
568                 }
569
570                 tag_update |= ((Mesh *)ob->data)->id.us > 1;
571
572                 if (ss->kb || ss->modifiers_active) {
573                         Mesh *mesh = ob->data;
574                         BKE_mesh_calc_normals(mesh);
575
576                         BKE_sculptsession_free_deformMats(ss);
577                         tag_update |= true;
578                 }
579
580                 if (tag_update) {
581                         DEG_id_tag_update(&ob->id, ID_RECALC_GEOMETRY);
582                 }
583                 else {
584                         sculpt_update_object_bounding_box(ob);
585                 }
586         }
587 }
588
589 static void sculpt_undo_free_list(ListBase *lb)
590 {
591         SculptUndoNode *unode = lb->first;
592         while (unode != NULL) {
593                 SculptUndoNode *unode_next = unode->next;
594                 if (unode->co)
595                         MEM_freeN(unode->co);
596                 if (unode->no)
597                         MEM_freeN(unode->no);
598                 if (unode->index)
599                         MEM_freeN(unode->index);
600                 if (unode->grids)
601                         MEM_freeN(unode->grids);
602                 if (unode->orig_co)
603                         MEM_freeN(unode->orig_co);
604                 if (unode->vert_hidden)
605                         MEM_freeN(unode->vert_hidden);
606                 if (unode->grid_hidden) {
607                         for (int i = 0; i < unode->totgrid; i++) {
608                                 if (unode->grid_hidden[i])
609                                         MEM_freeN(unode->grid_hidden[i]);
610                         }
611                         MEM_freeN(unode->grid_hidden);
612                 }
613                 if (unode->mask)
614                         MEM_freeN(unode->mask);
615
616                 if (unode->bm_entry) {
617                         BM_log_entry_drop(unode->bm_entry);
618                 }
619
620                 if (unode->bm_enter_totvert)
621                         CustomData_free(&unode->bm_enter_vdata, unode->bm_enter_totvert);
622                 if (unode->bm_enter_totedge)
623                         CustomData_free(&unode->bm_enter_edata, unode->bm_enter_totedge);
624                 if (unode->bm_enter_totloop)
625                         CustomData_free(&unode->bm_enter_ldata, unode->bm_enter_totloop);
626                 if (unode->bm_enter_totpoly)
627                         CustomData_free(&unode->bm_enter_pdata, unode->bm_enter_totpoly);
628
629                 MEM_freeN(unode);
630
631                 unode = unode_next;
632         }
633 }
634
635 /* Most likely we don't need this. */
636 #if 0
637 static bool sculpt_undo_cleanup(bContext *C, ListBase *lb)
638 {
639         Scene *scene = CTX_data_scene(C);
640         ViewLayer *view_layer = CTX_data_view_layer(C);
641         Object *ob = OBACT(view_layer);
642         SculptUndoNode *unode;
643
644         unode = lb->first;
645
646         if (unode && !STREQ(unode->idname, ob->id.name)) {
647                 if (unode->bm_entry)
648                         BM_log_cleanup_entry(unode->bm_entry);
649
650                 return true;
651         }
652
653         return false;
654 }
655 #endif
656
657 SculptUndoNode *sculpt_undo_get_node(PBVHNode *node)
658 {
659         UndoSculpt *usculpt = sculpt_undo_get_nodes();
660
661         if (usculpt == NULL) {
662                 return NULL;
663         }
664
665         return BLI_findptr(&usculpt->nodes, node, offsetof(SculptUndoNode, node));
666 }
667
668 static void sculpt_undo_alloc_and_store_hidden(PBVH *pbvh,
669                                                SculptUndoNode *unode)
670 {
671         PBVHNode *node = unode->node;
672         BLI_bitmap **grid_hidden;
673         int i, *grid_indices, totgrid;
674
675         grid_hidden = BKE_pbvh_grid_hidden(pbvh);
676
677         BKE_pbvh_node_get_grids(pbvh, node, &grid_indices, &totgrid,
678                                 NULL, NULL, NULL);
679
680         unode->grid_hidden = MEM_mapallocN(sizeof(*unode->grid_hidden) * totgrid,
681                                            "unode->grid_hidden");
682
683         for (i = 0; i < totgrid; i++) {
684                 if (grid_hidden[grid_indices[i]])
685                         unode->grid_hidden[i] = MEM_dupallocN(grid_hidden[grid_indices[i]]);
686                 else
687                         unode->grid_hidden[i] = NULL;
688         }
689 }
690
691 static SculptUndoNode *sculpt_undo_alloc_node(
692         Object *ob, PBVHNode *node,
693         SculptUndoType type)
694 {
695         UndoSculpt *usculpt = sculpt_undo_get_nodes();
696         SculptUndoNode *unode;
697         SculptSession *ss = ob->sculpt;
698         int totvert, allvert, totgrid, maxgrid, gridsize, *grids;
699
700         unode = MEM_callocN(sizeof(SculptUndoNode), "SculptUndoNode");
701         BLI_strncpy(unode->idname, ob->id.name, sizeof(unode->idname));
702         unode->type = type;
703         unode->node = node;
704
705         if (node) {
706                 BKE_pbvh_node_num_verts(ss->pbvh, node, &totvert, &allvert);
707                 BKE_pbvh_node_get_grids(ss->pbvh, node, &grids, &totgrid,
708                                         &maxgrid, &gridsize, NULL);
709
710                 unode->totvert = totvert;
711         }
712         else
713                 maxgrid = 0;
714
715         /* we will use this while sculpting, is mapalloc slow to access then? */
716
717         /* general TODO, fix count_alloc */
718         switch (type) {
719                 case SCULPT_UNDO_COORDS:
720                         unode->co = MEM_mapallocN(sizeof(float[3]) * allvert, "SculptUndoNode.co");
721                         unode->no = MEM_mapallocN(sizeof(short[3]) * allvert, "SculptUndoNode.no");
722
723                         usculpt->undo_size = (sizeof(float[3]) + sizeof(short[3]) + sizeof(int)) * allvert;
724                         break;
725                 case SCULPT_UNDO_HIDDEN:
726                         if (maxgrid)
727                                 sculpt_undo_alloc_and_store_hidden(ss->pbvh, unode);
728                         else
729                                 unode->vert_hidden = BLI_BITMAP_NEW(allvert, "SculptUndoNode.vert_hidden");
730
731                         break;
732                 case SCULPT_UNDO_MASK:
733                         unode->mask = MEM_mapallocN(sizeof(float) * allvert, "SculptUndoNode.mask");
734
735                         usculpt->undo_size += (sizeof(float) * sizeof(int)) * allvert;
736
737                         break;
738                 case SCULPT_UNDO_DYNTOPO_BEGIN:
739                 case SCULPT_UNDO_DYNTOPO_END:
740                 case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
741                         BLI_assert(!"Dynamic topology should've already been handled");
742                         break;
743         }
744
745         BLI_addtail(&usculpt->nodes, unode);
746
747         if (maxgrid) {
748                 /* multires */
749                 unode->maxgrid = maxgrid;
750                 unode->totgrid = totgrid;
751                 unode->gridsize = gridsize;
752                 unode->grids = MEM_mapallocN(sizeof(int) * totgrid, "SculptUndoNode.grids");
753         }
754         else {
755                 /* regular mesh */
756                 unode->maxvert = ss->totvert;
757                 unode->index = MEM_mapallocN(sizeof(int) * allvert, "SculptUndoNode.index");
758         }
759
760         if (ss->modifiers_active)
761                 unode->orig_co = MEM_callocN(allvert * sizeof(*unode->orig_co), "undoSculpt orig_cos");
762
763         return unode;
764 }
765
766 static void sculpt_undo_store_coords(Object *ob, SculptUndoNode *unode)
767 {
768         SculptSession *ss = ob->sculpt;
769         PBVHVertexIter vd;
770
771         BKE_pbvh_vertex_iter_begin(ss->pbvh, unode->node, vd, PBVH_ITER_ALL)
772         {
773                 copy_v3_v3(unode->co[vd.i], vd.co);
774                 if (vd.no) copy_v3_v3_short(unode->no[vd.i], vd.no);
775                 else normal_float_to_short_v3(unode->no[vd.i], vd.fno);
776
777                 if (ss->modifiers_active)
778                         copy_v3_v3(unode->orig_co[vd.i], ss->orig_cos[unode->index[vd.i]]);
779         }
780         BKE_pbvh_vertex_iter_end;
781 }
782
783 static void sculpt_undo_store_hidden(Object *ob, SculptUndoNode *unode)
784 {
785         PBVH *pbvh = ob->sculpt->pbvh;
786         PBVHNode *node = unode->node;
787
788         if (unode->grids) {
789                 /* already stored during allocation */
790         }
791         else {
792                 MVert *mvert;
793                 const int *vert_indices;
794                 int allvert;
795                 int i;
796
797                 BKE_pbvh_node_num_verts(pbvh, node, NULL, &allvert);
798                 BKE_pbvh_node_get_verts(pbvh, node, &vert_indices, &mvert);
799                 for (i = 0; i < allvert; i++) {
800                         BLI_BITMAP_SET(unode->vert_hidden, i,
801                                           mvert[vert_indices[i]].flag & ME_HIDE);
802                 }
803         }
804 }
805
806 static void sculpt_undo_store_mask(Object *ob, SculptUndoNode *unode)
807 {
808         SculptSession *ss = ob->sculpt;
809         PBVHVertexIter vd;
810
811         BKE_pbvh_vertex_iter_begin(ss->pbvh, unode->node, vd, PBVH_ITER_ALL)
812         {
813                 unode->mask[vd.i] = *vd.mask;
814         }
815         BKE_pbvh_vertex_iter_end;
816 }
817
818 static SculptUndoNode *sculpt_undo_bmesh_push(Object *ob,
819                                               PBVHNode *node,
820                                               SculptUndoType type)
821 {
822         UndoSculpt *usculpt = sculpt_undo_get_nodes();
823         SculptSession *ss = ob->sculpt;
824         PBVHVertexIter vd;
825
826         SculptUndoNode *unode = usculpt->nodes.first;
827
828         if (unode == NULL) {
829                 unode = MEM_callocN(sizeof(*unode), __func__);
830
831                 BLI_strncpy(unode->idname, ob->id.name, sizeof(unode->idname));
832                 unode->type = type;
833                 unode->applied = true;
834
835                 if (type == SCULPT_UNDO_DYNTOPO_END) {
836                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
837                         BM_log_before_all_removed(ss->bm, ss->bm_log);
838                 }
839                 else if (type == SCULPT_UNDO_DYNTOPO_BEGIN) {
840                         Mesh *me = ob->data;
841
842                         /* Store a copy of the mesh's current vertices, loops, and
843                          * polys. A full copy like this is needed because entering
844                          * dynamic-topology immediately does topological edits
845                          * (converting polys to triangles) that the BMLog can't
846                          * fully restore from */
847                         CustomData_copy(&me->vdata, &unode->bm_enter_vdata, CD_MASK_MESH,
848                                         CD_DUPLICATE, me->totvert);
849                         CustomData_copy(&me->edata, &unode->bm_enter_edata, CD_MASK_MESH,
850                                         CD_DUPLICATE, me->totedge);
851                         CustomData_copy(&me->ldata, &unode->bm_enter_ldata, CD_MASK_MESH,
852                                         CD_DUPLICATE, me->totloop);
853                         CustomData_copy(&me->pdata, &unode->bm_enter_pdata, CD_MASK_MESH,
854                                         CD_DUPLICATE, me->totpoly);
855                         unode->bm_enter_totvert = me->totvert;
856                         unode->bm_enter_totedge = me->totedge;
857                         unode->bm_enter_totloop = me->totloop;
858                         unode->bm_enter_totpoly = me->totpoly;
859
860                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
861                         BM_log_all_added(ss->bm, ss->bm_log);
862                 }
863                 else {
864                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
865                 }
866
867                 BLI_addtail(&usculpt->nodes, unode);
868         }
869
870         if (node) {
871                 switch (type) {
872                         case SCULPT_UNDO_COORDS:
873                         case SCULPT_UNDO_MASK:
874                                 /* Before any vertex values get modified, ensure their
875                                  * original positions are logged */
876                                 BKE_pbvh_vertex_iter_begin(ss->pbvh, node, vd, PBVH_ITER_ALL) {
877                                         BM_log_vert_before_modified(ss->bm_log, vd.bm_vert, vd.cd_vert_mask_offset);
878                                 }
879                                 BKE_pbvh_vertex_iter_end;
880                                 break;
881
882                         case SCULPT_UNDO_HIDDEN:
883                         {
884                                 GSetIterator gs_iter;
885                                 GSet *faces = BKE_pbvh_bmesh_node_faces(node);
886                                 BKE_pbvh_vertex_iter_begin(ss->pbvh, node, vd, PBVH_ITER_ALL) {
887                                         BM_log_vert_before_modified(ss->bm_log, vd.bm_vert, vd.cd_vert_mask_offset);
888                                 }
889                                 BKE_pbvh_vertex_iter_end;
890
891                                 GSET_ITER (gs_iter, faces) {
892                                         BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
893                                         BM_log_face_modified(ss->bm_log, f);
894                                 }
895                                 break;
896                         }
897
898                         case SCULPT_UNDO_DYNTOPO_BEGIN:
899                         case SCULPT_UNDO_DYNTOPO_END:
900                         case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
901                                 break;
902                 }
903         }
904
905         return unode;
906 }
907
908 SculptUndoNode *sculpt_undo_push_node(
909         Object *ob, PBVHNode *node,
910         SculptUndoType type)
911 {
912         SculptSession *ss = ob->sculpt;
913         SculptUndoNode *unode;
914
915         /* list is manipulated by multiple threads, so we lock */
916         BLI_thread_lock(LOCK_CUSTOM1);
917
918         if (ss->bm ||
919             ELEM(type,
920                  SCULPT_UNDO_DYNTOPO_BEGIN,
921                  SCULPT_UNDO_DYNTOPO_END))
922         {
923                 /* Dynamic topology stores only one undo node per stroke,
924                  * regardless of the number of PBVH nodes modified */
925                 unode = sculpt_undo_bmesh_push(ob, node, type);
926                 BLI_thread_unlock(LOCK_CUSTOM1);
927                 return unode;
928         }
929         else if ((unode = sculpt_undo_get_node(node))) {
930                 BLI_thread_unlock(LOCK_CUSTOM1);
931                 return unode;
932         }
933
934         unode = sculpt_undo_alloc_node(ob, node, type);
935
936         /* NOTE: If this ever becomes a bottleneck, make a lock inside of the node.
937          * so we release global lock sooner, but keep data locked for until it is
938          * fully initialized.
939          */
940
941         if (unode->grids) {
942                 int totgrid, *grids;
943                 BKE_pbvh_node_get_grids(ss->pbvh, node, &grids, &totgrid,
944                                         NULL, NULL, NULL);
945                 memcpy(unode->grids, grids, sizeof(int) * totgrid);
946         }
947         else {
948                 const int *vert_indices;
949                 int allvert;
950                 BKE_pbvh_node_num_verts(ss->pbvh, node, NULL, &allvert);
951                 BKE_pbvh_node_get_verts(ss->pbvh, node, &vert_indices, NULL);
952                 memcpy(unode->index, vert_indices, sizeof(int) * unode->totvert);
953         }
954
955         switch (type) {
956                 case SCULPT_UNDO_COORDS:
957                         sculpt_undo_store_coords(ob, unode);
958                         break;
959                 case SCULPT_UNDO_HIDDEN:
960                         sculpt_undo_store_hidden(ob, unode);
961                         break;
962                 case SCULPT_UNDO_MASK:
963                         sculpt_undo_store_mask(ob, unode);
964                         break;
965                 case SCULPT_UNDO_DYNTOPO_BEGIN:
966                 case SCULPT_UNDO_DYNTOPO_END:
967                 case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
968                         BLI_assert(!"Dynamic topology should've already been handled");
969                         break;
970         }
971
972         /* store active shape key */
973         if (ss->kb) BLI_strncpy(unode->shapeName, ss->kb->name, sizeof(ss->kb->name));
974         else unode->shapeName[0] = '\0';
975
976         BLI_thread_unlock(LOCK_CUSTOM1);
977
978         return unode;
979 }
980
981 void sculpt_undo_push_begin(const char *name)
982 {
983         UndoStack *ustack = ED_undo_stack_get();
984         bContext *C = NULL; /* special case, we never read from this. */
985         BKE_undosys_step_push_init_with_type(ustack, C, name, BKE_UNDOSYS_TYPE_SCULPT);
986 }
987
988 void sculpt_undo_push_end(void)
989 {
990         UndoSculpt *usculpt = sculpt_undo_get_nodes();
991         SculptUndoNode *unode;
992
993         /* we don't need normals in the undo stack */
994         for (unode = usculpt->nodes.first; unode; unode = unode->next) {
995                 if (unode->no) {
996                         MEM_freeN(unode->no);
997                         unode->no = NULL;
998                 }
999
1000                 if (unode->node)
1001                         BKE_pbvh_node_layer_disp_free(unode->node);
1002         }
1003
1004         /* We could remove this and enforce all callers run in an operator using 'OPTYPE_UNDO'. */
1005         wmWindowManager *wm = G_MAIN->wm.first;
1006         if (wm->op_undo_depth == 0) {
1007                 UndoStack *ustack = ED_undo_stack_get();
1008                 BKE_undosys_step_push(ustack, NULL, NULL);
1009         }
1010 }
1011
1012 /* -------------------------------------------------------------------- */
1013 /** \name Implements ED Undo System
1014  * \{ */
1015
1016 typedef struct SculptUndoStep {
1017         UndoStep step;
1018         /* note: will split out into list for multi-object-sculpt-mode. */
1019         UndoSculpt data;
1020 } SculptUndoStep;
1021
1022 static bool sculpt_undosys_poll(bContext *C)
1023 {
1024         Object *obact = CTX_data_active_object(C);
1025         if (obact && obact->type == OB_MESH) {
1026                 if (obact && (obact->mode & OB_MODE_SCULPT)) {
1027                         return true;
1028                 }
1029         }
1030         return false;
1031 }
1032
1033 static void sculpt_undosys_step_encode_init(struct bContext *UNUSED(C), UndoStep *us_p)
1034 {
1035         SculptUndoStep *us = (SculptUndoStep *)us_p;
1036         /* dummy, memory is cleared anyway. */
1037         BLI_listbase_clear(&us->data.nodes);
1038 }
1039
1040 static bool sculpt_undosys_step_encode(struct bContext *UNUSED(C), struct Main *UNUSED(bmain), UndoStep *us_p)
1041 {
1042         /* dummy, encoding is done along the way by adding tiles
1043          * to the current 'SculptUndoStep' added by encode_init. */
1044         SculptUndoStep *us = (SculptUndoStep *)us_p;
1045         us->step.data_size = us->data.undo_size;
1046
1047         SculptUndoNode *unode = us->data.nodes.last;
1048         if (unode && unode->type == SCULPT_UNDO_DYNTOPO_END) {
1049                 us->step.use_memfile_step = true;
1050         }
1051         us->step.is_applied = true;
1052         return true;
1053 }
1054
1055 static void sculpt_undosys_step_decode_undo_impl(struct bContext *C, SculptUndoStep *us)
1056 {
1057         BLI_assert(us->step.is_applied == true);
1058         sculpt_undo_restore_list(C, &us->data.nodes);
1059         us->step.is_applied = false;
1060 }
1061
1062 static void sculpt_undosys_step_decode_redo_impl(struct bContext *C, SculptUndoStep *us)
1063 {
1064         BLI_assert(us->step.is_applied == false);
1065         sculpt_undo_restore_list(C, &us->data.nodes);
1066         us->step.is_applied = true;
1067 }
1068
1069 static void sculpt_undosys_step_decode_undo(struct bContext *C, SculptUndoStep *us)
1070 {
1071         SculptUndoStep *us_iter = us;
1072         while (us_iter->step.next && (us_iter->step.next->type == us_iter->step.type)) {
1073                 if (us_iter->step.next->is_applied == false) {
1074                         break;
1075                 }
1076                 us_iter = (SculptUndoStep *)us_iter->step.next;
1077         }
1078         while (us_iter != us) {
1079                 sculpt_undosys_step_decode_undo_impl(C, us_iter);
1080                 us_iter = (SculptUndoStep *)us_iter->step.prev;
1081         }
1082 }
1083
1084 static void sculpt_undosys_step_decode_redo(struct bContext *C, SculptUndoStep *us)
1085 {
1086         SculptUndoStep *us_iter = us;
1087         while (us_iter->step.prev && (us_iter->step.prev->type == us_iter->step.type)) {
1088                 if (us_iter->step.prev->is_applied == true) {
1089                         break;
1090                 }
1091                 us_iter = (SculptUndoStep *)us_iter->step.prev;
1092         }
1093         while (us_iter && (us_iter->step.is_applied == false)) {
1094                 sculpt_undosys_step_decode_redo_impl(C, us_iter);
1095                 if (us_iter == us) {
1096                         break;
1097                 }
1098                 us_iter = (SculptUndoStep *)us_iter->step.next;
1099         }
1100 }
1101
1102 static void sculpt_undosys_step_decode(struct bContext *C, struct Main *bmain, UndoStep *us_p, int dir)
1103 {
1104         /* Ensure sculpt mode. */
1105         {
1106                 Scene *scene = CTX_data_scene(C);
1107                 ViewLayer *view_layer = CTX_data_view_layer(C);
1108                 /* Sculpt needs evaluated state. */
1109                 BKE_scene_view_layer_graph_evaluated_ensure(bmain, scene, view_layer);
1110                 Object *ob = OBACT(view_layer);
1111                 if (ob && (ob->type == OB_MESH)) {
1112                         Depsgraph *depsgraph = CTX_data_depsgraph(C);
1113                         if (ob->mode & OB_MODE_SCULPT) {
1114                                 /* pass */
1115                         }
1116                         else {
1117                                 ED_object_mode_generic_exit(bmain, depsgraph, scene, ob);
1118                                 Mesh *me = ob->data;
1119                                 /* Don't add sculpt topology undo steps when reading back undo state.
1120                                  * The undo steps must enter/exit for us. */
1121                                 me->flag &= ~ME_SCULPT_DYNAMIC_TOPOLOGY;
1122                                 ED_object_sculptmode_enter_ex(bmain, depsgraph, scene, ob, true, NULL);
1123                         }
1124                         BLI_assert(sculpt_undosys_poll(C));
1125                 }
1126                 else {
1127                         BLI_assert(0);
1128                         return;
1129                 }
1130         }
1131
1132         SculptUndoStep *us = (SculptUndoStep *)us_p;
1133         if (dir < 0) {
1134                 sculpt_undosys_step_decode_undo(C, us);
1135         }
1136         else {
1137                 sculpt_undosys_step_decode_redo(C, us);
1138         }
1139 }
1140
1141 static void sculpt_undosys_step_free(UndoStep *us_p)
1142 {
1143         SculptUndoStep *us = (SculptUndoStep *)us_p;
1144         sculpt_undo_free_list(&us->data.nodes);
1145 }
1146
1147 /* Export for ED_undo_sys. */
1148 void ED_sculpt_undosys_type(UndoType *ut)
1149 {
1150         ut->name = "Sculpt";
1151         ut->poll = sculpt_undosys_poll;
1152         ut->step_encode_init = sculpt_undosys_step_encode_init;
1153         ut->step_encode = sculpt_undosys_step_encode;
1154         ut->step_decode = sculpt_undosys_step_decode;
1155         ut->step_free = sculpt_undosys_step_free;
1156
1157         ut->use_context = true;
1158
1159         ut->step_size = sizeof(SculptUndoStep);
1160 }
1161
1162 /** \} */
1163
1164 /* -------------------------------------------------------------------- */
1165 /** \name Utilities
1166  * \{ */
1167
1168 static UndoSculpt *sculpt_undosys_step_get_nodes(UndoStep *us_p)
1169 {
1170         SculptUndoStep *us = (SculptUndoStep *)us_p;
1171         return &us->data;
1172 }
1173
1174 static UndoSculpt *sculpt_undo_get_nodes(void)
1175 {
1176         UndoStack *ustack = ED_undo_stack_get();
1177         UndoStep *us = BKE_undosys_stack_init_or_active_with_type(ustack, BKE_UNDOSYS_TYPE_SCULPT);
1178         return sculpt_undosys_step_get_nodes(us);
1179 }
1180
1181 /** \} */