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 }