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