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