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