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