Merge branch 'master' into blender2.8
[blender.git] / source / blender / editors / sculpt_paint / sculpt_undo.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2006 by Nicholas Bishop
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  *
27  * Implements the Sculpt Mode tools
28  *
29  */
30
31 /** \file blender/editors/sculpt_paint/sculpt_undo.c
32  *  \ingroup edsculpt
33  */
34
35 #include <stddef.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_math.h"
40 #include "BLI_utildefines.h"
41 #include "BLI_string.h"
42 #include "BLI_listbase.h"
43 #include "BLI_ghash.h"
44 #include "BLI_task.h"
45 #include "BLI_threads.h"
46
47 #include "DNA_meshdata_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_scene_types.h"
50 #include "DNA_mesh_types.h"
51 #include "DNA_screen_types.h"
52 #include "DNA_space_types.h"
53 #include "DNA_workspace_types.h"
54
55 #include "BKE_ccg.h"
56 #include "BKE_context.h"
57 #include "BKE_multires.h"
58 #include "BKE_paint.h"
59 #include "BKE_key.h"
60 #include "BKE_mesh.h"
61 #include "BKE_subsurf.h"
62 #include "BKE_undo_system.h"
63
64 #include "DEG_depsgraph.h"
65
66 #include "WM_api.h"
67 #include "WM_types.h"
68
69 #include "ED_paint.h"
70 #include "ED_object.h"
71 #include "ED_sculpt.h"
72 #include "ED_undo.h"
73
74 #include "bmesh.h"
75 #include "paint_intern.h"
76 #include "sculpt_intern.h"
77
78
79 typedef struct UndoSculpt {
80         ListBase nodes;
81
82         size_t undo_size;
83 } UndoSculpt;
84
85 static UndoSculpt *sculpt_undo_get_nodes(void);
86
87 static void update_cb(PBVHNode *node, void *rebuild)
88 {
89         BKE_pbvh_node_mark_update(node);
90         if (*((bool *)rebuild))
91                 BKE_pbvh_node_mark_rebuild_draw(node);
92         BKE_pbvh_node_fully_hidden_set(node, 0);
93 }
94
95 struct PartialUpdateData {
96         PBVH *pbvh;
97         bool rebuild;
98 };
99
100 /**
101  * A version of #update_cb that tests for 'ME_VERT_PBVH_UPDATE'
102  */
103 static void update_cb_partial(PBVHNode *node, void *userdata)
104 {
105         struct PartialUpdateData *data = userdata;
106         if (BKE_pbvh_node_vert_update_check_any(data->pbvh, node)) {
107                 update_cb(node, &(data->rebuild));
108         }
109 }
110
111 static bool test_swap_v3_v3(float a[3], float b[3])
112 {
113         /* no need for float comparison here (memory is exactly equal or not) */
114         if (memcmp(a, b, sizeof(float[3])) != 0) {
115                 swap_v3_v3(a, b);
116                 return true;
117         }
118         else {
119                 return false;
120         }
121 }
122
123 static bool sculpt_undo_restore_deformed(
124         const SculptSession *ss,
125         SculptUndoNode *unode,
126         int uindex, int oindex,
127         float coord[3])
128 {
129         if (test_swap_v3_v3(coord, unode->orig_co[uindex])) {
130                 copy_v3_v3(unode->co[uindex], ss->deform_cos[oindex]);
131                 return true;
132         }
133         else {
134                 return false;
135         }
136 }
137
138 static bool sculpt_undo_restore_coords(bContext *C, DerivedMesh *dm, SculptUndoNode *unode)
139 {
140         Scene *scene = CTX_data_scene(C);
141         Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
142         Object *ob = CTX_data_active_object(C);
143         Depsgraph *depsgraph = CTX_data_depsgraph(C);
144         SculptSession *ss = ob->sculpt;
145         MVert *mvert;
146         int *index;
147
148         if (unode->maxvert) {
149                 /* regular mesh restore */
150
151                 if (ss->kb && !STREQ(ss->kb->name, unode->shapeName)) {
152                         /* shape key has been changed before calling undo operator */
153
154                         Key *key = BKE_key_from_object(ob);
155                         KeyBlock *kb = key ? BKE_keyblock_find_name(key, unode->shapeName) : NULL;
156
157                         if (kb) {
158                                 ob->shapenr = BLI_findindex(&key->block, kb) + 1;
159
160                                 BKE_sculpt_update_mesh_elements(depsgraph, scene, sd, ob, 0, false);
161                                 WM_event_add_notifier(C, NC_OBJECT | ND_DATA, ob);
162                         }
163                         else {
164                                 /* key has been removed -- skip this undo node */
165                                 return 0;
166                         }
167                 }
168
169                 /* no need for float comparison here (memory is exactly equal or not) */
170                 index = unode->index;
171                 mvert = ss->mvert;
172
173                 if (ss->kb) {
174                         float (*vertCos)[3];
175                         vertCos = BKE_keyblock_convert_to_vertcos(ob, ss->kb);
176
177                         if (unode->orig_co) {
178                                 if (ss->modifiers_active) {
179                                         for (int i = 0; i < unode->totvert; i++) {
180                                                 sculpt_undo_restore_deformed(ss, unode, i, index[i], vertCos[index[i]]);
181                                         }
182                                 }
183                                 else {
184                                         for (int i = 0; i < unode->totvert; i++) {
185                                                 swap_v3_v3(vertCos[index[i]], unode->orig_co[i]);
186                                         }
187                                 }
188                         }
189                         else {
190                                 for (int i = 0; i < unode->totvert; i++) {
191                                         swap_v3_v3(vertCos[index[i]], unode->co[i]);
192                                 }
193                         }
194
195                         /* propagate new coords to keyblock */
196                         sculpt_vertcos_to_key(ob, ss->kb, vertCos);
197
198                         /* pbvh uses it's own mvert array, so coords should be */
199                         /* propagated to pbvh here */
200                         BKE_pbvh_apply_vertCos(ss->pbvh, vertCos);
201
202                         MEM_freeN(vertCos);
203                 }
204                 else {
205                         if (unode->orig_co) {
206                                 if (ss->modifiers_active) {
207                                         for (int i = 0; i < unode->totvert; i++) {
208                                                 if (sculpt_undo_restore_deformed(ss, unode, i, index[i], mvert[index[i]].co)) {
209                                                         mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
210                                                 }
211                                         }
212                                 }
213                                 else {
214                                         for (int i = 0; i < unode->totvert; i++) {
215                                                 if (test_swap_v3_v3(mvert[index[i]].co, unode->orig_co[i])) {
216                                                         mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
217                                                 }
218                                         }
219                                 }
220                         }
221                         else {
222                                 for (int i = 0; i < unode->totvert; i++) {
223                                         if (test_swap_v3_v3(mvert[index[i]].co, unode->co[i])) {
224                                                 mvert[index[i]].flag |= ME_VERT_PBVH_UPDATE;
225                                         }
226                                 }
227                         }
228                 }
229         }
230         else if (unode->maxgrid && dm->getGridData) {
231                 /* multires restore */
232                 CCGElem **grids, *grid;
233                 CCGKey key;
234                 float (*co)[3];
235                 int gridsize;
236
237                 grids = dm->getGridData(dm);
238                 gridsize = dm->getGridSize(dm);
239                 dm->getGridKey(dm, &key);
240
241                 co = unode->co;
242                 for (int j = 0; j < unode->totgrid; j++) {
243                         grid = grids[unode->grids[j]];
244
245                         for (int i = 0; i < gridsize * gridsize; i++, co++) {
246                                 swap_v3_v3(CCG_elem_offset_co(&key, grid, i), co[0]);
247                         }
248                 }
249         }
250
251         return 1;
252 }
253
254 static bool sculpt_undo_restore_hidden(
255         bContext *C, DerivedMesh *dm,
256         SculptUndoNode *unode)
257 {
258         Object *ob = CTX_data_active_object(C);
259         SculptSession *ss = ob->sculpt;
260         int i;
261
262         if (unode->maxvert) {
263                 MVert *mvert = ss->mvert;
264
265                 for (i = 0; i < unode->totvert; i++) {
266                         MVert *v = &mvert[unode->index[i]];
267                         if ((BLI_BITMAP_TEST(unode->vert_hidden, i) != 0) != ((v->flag & ME_HIDE) != 0)) {
268                                 BLI_BITMAP_FLIP(unode->vert_hidden, i);
269                                 v->flag ^= ME_HIDE;
270                                 v->flag |= ME_VERT_PBVH_UPDATE;
271                         }
272                 }
273         }
274         else if (unode->maxgrid && dm->getGridData) {
275                 BLI_bitmap **grid_hidden = dm->getGridHidden(dm);
276
277                 for (i = 0; i < unode->totgrid; i++) {
278                         SWAP(BLI_bitmap *,
279                              unode->grid_hidden[i],
280                              grid_hidden[unode->grids[i]]);
281
282                 }
283         }
284
285         return 1;
286 }
287
288 static bool sculpt_undo_restore_mask(bContext *C, DerivedMesh *dm, SculptUndoNode *unode)
289 {
290         Object *ob = CTX_data_active_object(C);
291         SculptSession *ss = ob->sculpt;
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 && dm->getGridData) {
311                 /* multires restore */
312                 CCGElem **grids, *grid;
313                 CCGKey key;
314                 float *mask;
315                 int gridsize;
316
317                 grids = dm->getGridData(dm);
318                 gridsize = dm->getGridSize(dm);
319                 dm->getGridKey(dm, &key);
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         Object *ob = CTX_data_active_object(C);
476         Depsgraph *depsgraph = CTX_data_depsgraph(C);
477         DerivedMesh *dm;
478         SculptSession *ss = ob->sculpt;
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         BKE_sculpt_update_mesh_elements(depsgraph, scene, sd, ob, 0, need_mask);
496
497         /* call _after_ sculpt_update_mesh_elements() which may update 'ob->derivedFinal' */
498         dm = mesh_get_derived_final(depsgraph, scene, ob, 0);
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 && dm->getGridData) {
514                         if ((dm->getNumGrids(dm) != unode->maxgrid) ||
515                             (dm->getGridSize(dm) != 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, dm, unode))
527                                         update = true;
528                                 break;
529                         case SCULPT_UNDO_HIDDEN:
530                                 if (sculpt_undo_restore_hidden(C, dm, unode))
531                                         rebuild = true;
532                                 break;
533                         case SCULPT_UNDO_MASK:
534                                 if (sculpt_undo_restore_mask(C, dm, 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, 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, OB_RECALC_DATA);
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;
592         int i;
593
594         for (unode = lb->first; unode; unode = unode->next) {
595                 if (unode->co)
596                         MEM_freeN(unode->co);
597                 if (unode->no)
598                         MEM_freeN(unode->no);
599                 if (unode->index)
600                         MEM_freeN(unode->index);
601                 if (unode->grids)
602                         MEM_freeN(unode->grids);
603                 if (unode->orig_co)
604                         MEM_freeN(unode->orig_co);
605                 if (unode->vert_hidden)
606                         MEM_freeN(unode->vert_hidden);
607                 if (unode->grid_hidden) {
608                         for (i = 0; i < unode->totgrid; i++) {
609                                 if (unode->grid_hidden[i])
610                                         MEM_freeN(unode->grid_hidden[i]);
611                         }
612                         MEM_freeN(unode->grid_hidden);
613                 }
614                 if (unode->mask)
615                         MEM_freeN(unode->mask);
616
617                 if (unode->bm_entry) {
618                         BM_log_entry_drop(unode->bm_entry);
619                 }
620
621                 if (unode->bm_enter_totvert)
622                         CustomData_free(&unode->bm_enter_vdata, unode->bm_enter_totvert);
623                 if (unode->bm_enter_totedge)
624                         CustomData_free(&unode->bm_enter_edata, unode->bm_enter_totedge);
625                 if (unode->bm_enter_totloop)
626                         CustomData_free(&unode->bm_enter_ldata, unode->bm_enter_totloop);
627                 if (unode->bm_enter_totpoly)
628                         CustomData_free(&unode->bm_enter_pdata, unode->bm_enter_totpoly);
629         }
630 }
631
632 /* Most likely we don't need this. */
633 #if 0
634 static bool sculpt_undo_cleanup(bContext *C, ListBase *lb)
635 {
636         Object *ob = CTX_data_active_object(C);
637         SculptUndoNode *unode;
638
639         unode = lb->first;
640
641         if (unode && !STREQ(unode->idname, ob->id.name)) {
642                 if (unode->bm_entry)
643                         BM_log_cleanup_entry(unode->bm_entry);
644
645                 return true;
646         }
647
648         return false;
649 }
650 #endif
651
652 SculptUndoNode *sculpt_undo_get_node(PBVHNode *node)
653 {
654         UndoSculpt *usculpt = sculpt_undo_get_nodes();
655
656         if (usculpt == NULL) {
657                 return NULL;
658         }
659
660         return BLI_findptr(&usculpt->nodes, node, offsetof(SculptUndoNode, node));
661 }
662
663 static void sculpt_undo_alloc_and_store_hidden(PBVH *pbvh,
664                                                SculptUndoNode *unode)
665 {
666         PBVHNode *node = unode->node;
667         BLI_bitmap **grid_hidden;
668         int i, *grid_indices, totgrid;
669
670         grid_hidden = BKE_pbvh_grid_hidden(pbvh);
671
672         BKE_pbvh_node_get_grids(pbvh, node, &grid_indices, &totgrid,
673                                 NULL, NULL, NULL);
674
675         unode->grid_hidden = MEM_mapallocN(sizeof(*unode->grid_hidden) * totgrid,
676                                            "unode->grid_hidden");
677
678         for (i = 0; i < totgrid; i++) {
679                 if (grid_hidden[grid_indices[i]])
680                         unode->grid_hidden[i] = MEM_dupallocN(grid_hidden[grid_indices[i]]);
681                 else
682                         unode->grid_hidden[i] = NULL;
683         }
684 }
685
686 static SculptUndoNode *sculpt_undo_alloc_node(
687         Object *ob, PBVHNode *node,
688         SculptUndoType type)
689 {
690         UndoSculpt *usculpt = sculpt_undo_get_nodes();
691         SculptUndoNode *unode;
692         SculptSession *ss = ob->sculpt;
693         int totvert, allvert, totgrid, maxgrid, gridsize, *grids;
694
695         unode = MEM_callocN(sizeof(SculptUndoNode), "SculptUndoNode");
696         BLI_strncpy(unode->idname, ob->id.name, sizeof(unode->idname));
697         unode->type = type;
698         unode->node = node;
699
700         if (node) {
701                 BKE_pbvh_node_num_verts(ss->pbvh, node, &totvert, &allvert);
702                 BKE_pbvh_node_get_grids(ss->pbvh, node, &grids, &totgrid,
703                                         &maxgrid, &gridsize, NULL);
704
705                 unode->totvert = totvert;
706         }
707         else
708                 maxgrid = 0;
709
710         /* we will use this while sculpting, is mapalloc slow to access then? */
711
712         /* general TODO, fix count_alloc */
713         switch (type) {
714                 case SCULPT_UNDO_COORDS:
715                         unode->co = MEM_mapallocN(sizeof(float[3]) * allvert, "SculptUndoNode.co");
716                         unode->no = MEM_mapallocN(sizeof(short[3]) * allvert, "SculptUndoNode.no");
717
718                         usculpt->undo_size = (sizeof(float[3]) + sizeof(short[3]) + sizeof(int)) * allvert;
719                         break;
720                 case SCULPT_UNDO_HIDDEN:
721                         if (maxgrid)
722                                 sculpt_undo_alloc_and_store_hidden(ss->pbvh, unode);
723                         else
724                                 unode->vert_hidden = BLI_BITMAP_NEW(allvert, "SculptUndoNode.vert_hidden");
725
726                         break;
727                 case SCULPT_UNDO_MASK:
728                         unode->mask = MEM_mapallocN(sizeof(float) * allvert, "SculptUndoNode.mask");
729
730                         usculpt->undo_size += (sizeof(float) * sizeof(int)) * allvert;
731
732                         break;
733                 case SCULPT_UNDO_DYNTOPO_BEGIN:
734                 case SCULPT_UNDO_DYNTOPO_END:
735                 case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
736                         BLI_assert(!"Dynamic topology should've already been handled");
737                         break;
738         }
739
740         BLI_addtail(&usculpt->nodes, unode);
741
742         if (maxgrid) {
743                 /* multires */
744                 unode->maxgrid = maxgrid;
745                 unode->totgrid = totgrid;
746                 unode->gridsize = gridsize;
747                 unode->grids = MEM_mapallocN(sizeof(int) * totgrid, "SculptUndoNode.grids");
748         }
749         else {
750                 /* regular mesh */
751                 unode->maxvert = ss->totvert;
752                 unode->index = MEM_mapallocN(sizeof(int) * allvert, "SculptUndoNode.index");
753         }
754
755         if (ss->modifiers_active)
756                 unode->orig_co = MEM_callocN(allvert * sizeof(*unode->orig_co), "undoSculpt orig_cos");
757
758         return unode;
759 }
760
761 static void sculpt_undo_store_coords(Object *ob, SculptUndoNode *unode)
762 {
763         SculptSession *ss = ob->sculpt;
764         PBVHVertexIter vd;
765
766         BKE_pbvh_vertex_iter_begin(ss->pbvh, unode->node, vd, PBVH_ITER_ALL)
767         {
768                 copy_v3_v3(unode->co[vd.i], vd.co);
769                 if (vd.no) copy_v3_v3_short(unode->no[vd.i], vd.no);
770                 else normal_float_to_short_v3(unode->no[vd.i], vd.fno);
771
772                 if (ss->modifiers_active)
773                         copy_v3_v3(unode->orig_co[vd.i], ss->orig_cos[unode->index[vd.i]]);
774         }
775         BKE_pbvh_vertex_iter_end;
776 }
777
778 static void sculpt_undo_store_hidden(Object *ob, SculptUndoNode *unode)
779 {
780         PBVH *pbvh = ob->sculpt->pbvh;
781         PBVHNode *node = unode->node;
782
783         if (unode->grids) {
784                 /* already stored during allocation */
785         }
786         else {
787                 MVert *mvert;
788                 const int *vert_indices;
789                 int allvert;
790                 int i;
791
792                 BKE_pbvh_node_num_verts(pbvh, node, NULL, &allvert);
793                 BKE_pbvh_node_get_verts(pbvh, node, &vert_indices, &mvert);
794                 for (i = 0; i < allvert; i++) {
795                         BLI_BITMAP_SET(unode->vert_hidden, i,
796                                           mvert[vert_indices[i]].flag & ME_HIDE);
797                 }
798         }
799 }
800
801 static void sculpt_undo_store_mask(Object *ob, SculptUndoNode *unode)
802 {
803         SculptSession *ss = ob->sculpt;
804         PBVHVertexIter vd;
805
806         BKE_pbvh_vertex_iter_begin(ss->pbvh, unode->node, vd, PBVH_ITER_ALL)
807         {
808                 unode->mask[vd.i] = *vd.mask;
809         }
810         BKE_pbvh_vertex_iter_end;
811 }
812
813 static SculptUndoNode *sculpt_undo_bmesh_push(Object *ob,
814                                               PBVHNode *node,
815                                               SculptUndoType type)
816 {
817         UndoSculpt *usculpt = sculpt_undo_get_nodes();
818         SculptSession *ss = ob->sculpt;
819         PBVHVertexIter vd;
820
821         SculptUndoNode *unode = usculpt->nodes.first;
822
823         if (unode == NULL) {
824                 unode = MEM_callocN(sizeof(*unode), __func__);
825
826                 BLI_strncpy(unode->idname, ob->id.name, sizeof(unode->idname));
827                 unode->type = type;
828                 unode->applied = true;
829
830                 if (type == SCULPT_UNDO_DYNTOPO_END) {
831                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
832                         BM_log_before_all_removed(ss->bm, ss->bm_log);
833                 }
834                 else if (type == SCULPT_UNDO_DYNTOPO_BEGIN) {
835                         Mesh *me = ob->data;
836
837                         /* Store a copy of the mesh's current vertices, loops, and
838                          * polys. A full copy like this is needed because entering
839                          * dynamic-topology immediately does topological edits
840                          * (converting polys to triangles) that the BMLog can't
841                          * fully restore from */
842                         CustomData_copy(&me->vdata, &unode->bm_enter_vdata, CD_MASK_MESH,
843                                         CD_DUPLICATE, me->totvert);
844                         CustomData_copy(&me->edata, &unode->bm_enter_edata, CD_MASK_MESH,
845                                         CD_DUPLICATE, me->totedge);
846                         CustomData_copy(&me->ldata, &unode->bm_enter_ldata, CD_MASK_MESH,
847                                         CD_DUPLICATE, me->totloop);
848                         CustomData_copy(&me->pdata, &unode->bm_enter_pdata, CD_MASK_MESH,
849                                         CD_DUPLICATE, me->totpoly);
850                         unode->bm_enter_totvert = me->totvert;
851                         unode->bm_enter_totedge = me->totedge;
852                         unode->bm_enter_totloop = me->totloop;
853                         unode->bm_enter_totpoly = me->totpoly;
854
855                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
856                         BM_log_all_added(ss->bm, ss->bm_log);
857                 }
858                 else {
859                         unode->bm_entry = BM_log_entry_add(ss->bm_log);
860                 }
861
862                 BLI_addtail(&usculpt->nodes, unode);
863         }
864
865         if (node) {
866                 switch (type) {
867                         case SCULPT_UNDO_COORDS:
868                         case SCULPT_UNDO_MASK:
869                                 /* Before any vertex values get modified, ensure their
870                                  * original positions are logged */
871                                 BKE_pbvh_vertex_iter_begin(ss->pbvh, node, vd, PBVH_ITER_ALL) {
872                                         BM_log_vert_before_modified(ss->bm_log, vd.bm_vert, vd.cd_vert_mask_offset);
873                                 }
874                                 BKE_pbvh_vertex_iter_end;
875                                 break;
876
877                         case SCULPT_UNDO_HIDDEN:
878                         {
879                                 GSetIterator gs_iter;
880                                 GSet *faces = BKE_pbvh_bmesh_node_faces(node);
881                                 BKE_pbvh_vertex_iter_begin(ss->pbvh, node, vd, PBVH_ITER_ALL) {
882                                         BM_log_vert_before_modified(ss->bm_log, vd.bm_vert, vd.cd_vert_mask_offset);
883                                 }
884                                 BKE_pbvh_vertex_iter_end;
885
886                                 GSET_ITER (gs_iter, faces) {
887                                         BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
888                                         BM_log_face_modified(ss->bm_log, f);
889                                 }
890                                 break;
891                         }
892
893                         case SCULPT_UNDO_DYNTOPO_BEGIN:
894                         case SCULPT_UNDO_DYNTOPO_END:
895                         case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
896                                 break;
897                 }
898         }
899
900         return unode;
901 }
902
903 SculptUndoNode *sculpt_undo_push_node(
904         Object *ob, PBVHNode *node,
905         SculptUndoType type)
906 {
907         SculptSession *ss = ob->sculpt;
908         SculptUndoNode *unode;
909
910         /* list is manipulated by multiple threads, so we lock */
911         BLI_thread_lock(LOCK_CUSTOM1);
912
913         if (ss->bm ||
914             ELEM(type,
915                  SCULPT_UNDO_DYNTOPO_BEGIN,
916                  SCULPT_UNDO_DYNTOPO_END))
917         {
918                 /* Dynamic topology stores only one undo node per stroke,
919                  * regardless of the number of PBVH nodes modified */
920                 unode = sculpt_undo_bmesh_push(ob, node, type);
921                 BLI_thread_unlock(LOCK_CUSTOM1);
922                 return unode;
923         }
924         else if ((unode = sculpt_undo_get_node(node))) {
925                 BLI_thread_unlock(LOCK_CUSTOM1);
926                 return unode;
927         }
928
929         unode = sculpt_undo_alloc_node(ob, node, type);
930
931         BLI_thread_unlock(LOCK_CUSTOM1);
932
933         /* copy threaded, hopefully this is the performance critical part */
934
935         if (unode->grids) {
936                 int totgrid, *grids;
937                 BKE_pbvh_node_get_grids(ss->pbvh, node, &grids, &totgrid,
938                                         NULL, NULL, NULL);
939                 memcpy(unode->grids, grids, sizeof(int) * totgrid);
940         }
941         else {
942                 const int *vert_indices;
943                 int allvert;
944                 BKE_pbvh_node_num_verts(ss->pbvh, node, NULL, &allvert);
945                 BKE_pbvh_node_get_verts(ss->pbvh, node, &vert_indices, NULL);
946                 memcpy(unode->index, vert_indices, sizeof(int) * unode->totvert);
947         }
948
949         switch (type) {
950                 case SCULPT_UNDO_COORDS:
951                         sculpt_undo_store_coords(ob, unode);
952                         break;
953                 case SCULPT_UNDO_HIDDEN:
954                         sculpt_undo_store_hidden(ob, unode);
955                         break;
956                 case SCULPT_UNDO_MASK:
957                         sculpt_undo_store_mask(ob, unode);
958                         break;
959                 case SCULPT_UNDO_DYNTOPO_BEGIN:
960                 case SCULPT_UNDO_DYNTOPO_END:
961                 case SCULPT_UNDO_DYNTOPO_SYMMETRIZE:
962                         BLI_assert(!"Dynamic topology should've already been handled");
963                         break;
964         }
965
966         /* store active shape key */
967         if (ss->kb) BLI_strncpy(unode->shapeName, ss->kb->name, sizeof(ss->kb->name));
968         else unode->shapeName[0] = '\0';
969
970         return unode;
971 }
972
973 void sculpt_undo_push_begin(const char *name)
974 {
975         UndoStack *ustack = ED_undo_stack_get();
976         bContext *C = NULL; /* special case, we never read from this. */
977         BKE_undosys_step_push_init_with_type(ustack, C, name, BKE_UNDOSYS_TYPE_SCULPT);
978 }
979
980 void sculpt_undo_push_end(void)
981 {
982         UndoSculpt *usculpt = sculpt_undo_get_nodes();
983         SculptUndoNode *unode;
984
985         /* we don't need normals in the undo stack */
986         for (unode = usculpt->nodes.first; unode; unode = unode->next) {
987                 if (unode->no) {
988                         MEM_freeN(unode->no);
989                         unode->no = NULL;
990                 }
991
992                 if (unode->node)
993                         BKE_pbvh_node_layer_disp_free(unode->node);
994         }
995
996         UndoStack *ustack = ED_undo_stack_get();
997         BKE_undosys_step_push(ustack, NULL, NULL);
998 }
999
1000 /* -------------------------------------------------------------------- */
1001 /** \name Implements ED Undo System
1002  * \{ */
1003
1004 typedef struct SculptUndoStep {
1005         UndoStep step;
1006         /* note: will split out into list for multi-object-sculpt-mode. */
1007         UndoSculpt data;
1008 } SculptUndoStep;
1009
1010 static bool sculpt_undosys_poll(bContext *C)
1011 {
1012         ScrArea *sa = CTX_wm_area(C);
1013         if (sa && (sa->spacetype == SPACE_VIEW3D)) {
1014                 Object *obact = CTX_data_active_object(C);
1015                 if (obact && (obact->mode & OB_MODE_SCULPT)) {
1016                         return true;
1017                 }
1018         }
1019         return false;
1020 }
1021
1022 static void sculpt_undosys_step_encode_init(struct bContext *UNUSED(C), UndoStep *us_p)
1023 {
1024         SculptUndoStep *us = (SculptUndoStep *)us_p;
1025         /* dummy, memory is cleared anyway. */
1026         BLI_listbase_clear(&us->data.nodes);
1027 }
1028
1029 static bool sculpt_undosys_step_encode(struct bContext *UNUSED(C), UndoStep *us_p)
1030 {
1031         /* dummy, encoding is done along the way by adding tiles
1032          * to the current 'SculptUndoStep' added by encode_init. */
1033         SculptUndoStep *us = (SculptUndoStep *)us_p;
1034         us->step.data_size = us->data.undo_size;
1035         return true;
1036 }
1037
1038 static void sculpt_undosys_step_decode(struct bContext *C, UndoStep *us_p, int UNUSED(dir))
1039 {
1040         /* TODO(campbell): undo_system: use low-level API to set mode. */
1041         ED_object_mode_set(C, OB_MODE_SCULPT);
1042         BLI_assert(sculpt_undosys_poll(C));
1043
1044         SculptUndoStep *us = (SculptUndoStep *)us_p;
1045         sculpt_undo_restore_list(C, &us->data.nodes);
1046 }
1047
1048 static void sculpt_undosys_step_free(UndoStep *us_p)
1049 {
1050         SculptUndoStep *us = (SculptUndoStep *)us_p;
1051         sculpt_undo_free_list(&us->data.nodes);
1052 }
1053
1054 /* Export for ED_undo_sys. */
1055 void ED_sculpt_undosys_type(UndoType *ut)
1056 {
1057         ut->name = "Sculpt";
1058         ut->poll = sculpt_undosys_poll;
1059         ut->step_encode_init = sculpt_undosys_step_encode_init;
1060         ut->step_encode = sculpt_undosys_step_encode;
1061         ut->step_decode = sculpt_undosys_step_decode;
1062         ut->step_free = sculpt_undosys_step_free;
1063
1064         ut->mode = BKE_UNDOTYPE_MODE_ACCUMULATE;
1065         ut->use_context = true;
1066
1067         ut->step_size = sizeof(SculptUndoStep);
1068 }
1069
1070 /** \} */
1071
1072 /* -------------------------------------------------------------------- */
1073 /** \name Utilities
1074  * \{ */
1075
1076 static UndoSculpt *sculpt_undosys_step_get_nodes(UndoStep *us_p)
1077 {
1078         SculptUndoStep *us = (SculptUndoStep *)us_p;
1079         return &us->data;
1080 }
1081
1082 static UndoSculpt *sculpt_undo_get_nodes(void)
1083 {
1084         UndoStack *ustack = ED_undo_stack_get();
1085         UndoStep *us = BKE_undosys_stack_init_or_active_with_type(ustack, BKE_UNDOSYS_TYPE_SCULPT);
1086         return sculpt_undosys_step_get_nodes(us);
1087 }
1088
1089 /** \} */