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