Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / bmesh / intern / bmesh_log.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file \ingroup bmesh
18  *
19  * The BMLog is an interface for storing undo/redo steps as a BMesh is
20  * modified. It only stores changes to the BMesh, not full copies.
21  *
22  * Currently it supports the following types of changes:
23  *
24  * - Adding and removing vertices
25  * - Adding and removing faces
26  * - Moving vertices
27  * - Setting vertex paint-mask values
28  * - Setting vertex hflags
29  */
30
31 #include "MEM_guardedalloc.h"
32
33 #include "BLI_utildefines.h"
34 #include "BLI_ghash.h"
35 #include "BLI_listbase.h"
36 #include "BLI_math.h"
37 #include "BLI_mempool.h"
38
39 #include "BKE_customdata.h"
40
41 #include "bmesh.h"
42 #include "bmesh_log.h"
43 #include "range_tree.h"
44
45 #include "BLI_strict_flags.h"
46
47
48 struct BMLogEntry {
49         struct BMLogEntry *next, *prev;
50
51         /* The following GHashes map from an element ID to one of the log
52          * types above */
53
54         /* Elements that were in the previous entry, but have been
55          * deleted */
56         GHash *deleted_verts;
57         GHash *deleted_faces;
58         /* Elements that were not in the previous entry, but are in the
59          * result of this entry */
60         GHash *added_verts;
61         GHash *added_faces;
62
63         /* Vertices whose coordinates, mask value, or hflag have changed */
64         GHash *modified_verts;
65         GHash *modified_faces;
66
67         BLI_mempool *pool_verts;
68         BLI_mempool *pool_faces;
69
70         /* This is only needed for dropping BMLogEntries while still in
71          * dynamic-topology mode, as that should release vert/face IDs
72          * back to the BMLog but no BMLog pointer is available at that
73          * time.
74          *
75          * This field is not guaranteed to be valid, any use of it should
76          * check for NULL. */
77         BMLog *log;
78 };
79
80 struct BMLog {
81         /* Tree of free IDs */
82         struct RangeTreeUInt *unused_ids;
83
84         /* Mapping from unique IDs to vertices and faces
85          *
86          * Each vertex and face in the log gets a unique uinteger
87          * assigned. That ID is taken from the set managed by the
88          * unused_ids range tree.
89          *
90          * The ID is needed because element pointers will change as they
91          * are created and deleted.
92          */
93         GHash *id_to_elem;
94         GHash *elem_to_id;
95
96         /* All BMLogEntrys, ordered from earliest to most recent */
97         ListBase entries;
98
99         /* The current log entry from entries list
100          *
101          * If null, then the original mesh from before any of the log
102          * entries is current (i.e. there is nothing left to undo.)
103          *
104          * If equal to the last entry in the entries list, then all log
105          * entries have been applied (i.e. there is nothing left to redo.)
106          */
107         BMLogEntry *current_entry;
108 };
109
110 typedef struct {
111         float co[3];
112         short no[3];
113         char hflag;
114         float mask;
115 } BMLogVert;
116
117 typedef struct {
118         uint v_ids[3];
119         char hflag;
120 } BMLogFace;
121
122 /************************* Get/set element IDs ************************/
123
124 /* bypass actual hashing, the keys don't overlap */
125 #define logkey_hash BLI_ghashutil_inthash_p_simple
126 #define logkey_cmp BLI_ghashutil_intcmp
127
128 /* Get the vertex's unique ID from the log */
129 static uint bm_log_vert_id_get(BMLog *log, BMVert *v)
130 {
131         BLI_assert(BLI_ghash_haskey(log->elem_to_id, v));
132         return POINTER_AS_UINT(BLI_ghash_lookup(log->elem_to_id, v));
133 }
134
135 /* Set the vertex's unique ID in the log */
136 static void bm_log_vert_id_set(BMLog *log, BMVert *v, uint id)
137 {
138         void *vid = POINTER_FROM_UINT(id);
139
140         BLI_ghash_reinsert(log->id_to_elem, vid, v, NULL, NULL);
141         BLI_ghash_reinsert(log->elem_to_id, v, vid, NULL, NULL);
142 }
143
144 /* Get a vertex from its unique ID */
145 static BMVert *bm_log_vert_from_id(BMLog *log, uint id)
146 {
147         void *key = POINTER_FROM_UINT(id);
148         BLI_assert(BLI_ghash_haskey(log->id_to_elem, key));
149         return BLI_ghash_lookup(log->id_to_elem, key);
150 }
151
152 /* Get the face's unique ID from the log */
153 static uint bm_log_face_id_get(BMLog *log, BMFace *f)
154 {
155         BLI_assert(BLI_ghash_haskey(log->elem_to_id, f));
156         return POINTER_AS_UINT(BLI_ghash_lookup(log->elem_to_id, f));
157 }
158
159 /* Set the face's unique ID in the log */
160 static void bm_log_face_id_set(BMLog *log, BMFace *f, uint id)
161 {
162         void *fid = POINTER_FROM_UINT(id);
163
164         BLI_ghash_reinsert(log->id_to_elem, fid, f, NULL, NULL);
165         BLI_ghash_reinsert(log->elem_to_id, f, fid, NULL, NULL);
166 }
167
168 /* Get a face from its unique ID */
169 static BMFace *bm_log_face_from_id(BMLog *log, uint id)
170 {
171         void *key = POINTER_FROM_UINT(id);
172         BLI_assert(BLI_ghash_haskey(log->id_to_elem, key));
173         return BLI_ghash_lookup(log->id_to_elem, key);
174 }
175
176
177 /************************ BMLogVert / BMLogFace ***********************/
178
179 /* Get a vertex's paint-mask value
180  *
181  * Returns zero if no paint-mask layer is present */
182 static float vert_mask_get(BMVert *v, const int cd_vert_mask_offset)
183 {
184         if (cd_vert_mask_offset != -1) {
185                 return BM_ELEM_CD_GET_FLOAT(v, cd_vert_mask_offset);
186         }
187         else {
188                 return 0.0f;
189         }
190 }
191
192 /* Set a vertex's paint-mask value
193  *
194  * Has no effect is no paint-mask layer is present */
195 static void vert_mask_set(BMVert *v, const float new_mask, const int cd_vert_mask_offset)
196 {
197         if (cd_vert_mask_offset != -1) {
198                 BM_ELEM_CD_SET_FLOAT(v, cd_vert_mask_offset, new_mask);
199         }
200 }
201
202 /* Update a BMLogVert with data from a BMVert */
203 static void bm_log_vert_bmvert_copy(BMLogVert *lv, BMVert *v, const int cd_vert_mask_offset)
204 {
205         copy_v3_v3(lv->co, v->co);
206         normal_float_to_short_v3(lv->no, v->no);
207         lv->mask = vert_mask_get(v, cd_vert_mask_offset);
208         lv->hflag = v->head.hflag;
209 }
210
211 /* Allocate and initialize a BMLogVert */
212 static BMLogVert *bm_log_vert_alloc(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
213 {
214         BMLogEntry *entry = log->current_entry;
215         BMLogVert *lv = BLI_mempool_alloc(entry->pool_verts);
216
217         bm_log_vert_bmvert_copy(lv, v, cd_vert_mask_offset);
218
219         return lv;
220 }
221
222 /* Allocate and initialize a BMLogFace */
223 static BMLogFace *bm_log_face_alloc(BMLog *log, BMFace *f)
224 {
225         BMLogEntry *entry = log->current_entry;
226         BMLogFace *lf = BLI_mempool_alloc(entry->pool_faces);
227         BMVert *v[3];
228
229         BLI_assert(f->len == 3);
230
231         // BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v, 3);
232         BM_face_as_array_vert_tri(f, v);
233
234         lf->v_ids[0] = bm_log_vert_id_get(log, v[0]);
235         lf->v_ids[1] = bm_log_vert_id_get(log, v[1]);
236         lf->v_ids[2] = bm_log_vert_id_get(log, v[2]);
237
238         lf->hflag = f->head.hflag;
239         return lf;
240 }
241
242
243 /************************ Helpers for undo/redo ***********************/
244
245 static void bm_log_verts_unmake(BMesh *bm, BMLog *log, GHash *verts)
246 {
247         const int cd_vert_mask_offset = CustomData_get_offset(&bm->vdata, CD_PAINT_MASK);
248
249         GHashIterator gh_iter;
250         GHASH_ITER (gh_iter, verts) {
251                 void *key = BLI_ghashIterator_getKey(&gh_iter);
252                 BMLogVert *lv = BLI_ghashIterator_getValue(&gh_iter);
253                 uint id = POINTER_AS_UINT(key);
254                 BMVert *v = bm_log_vert_from_id(log, id);
255
256                 /* Ensure the log has the final values of the vertex before
257                  * deleting it */
258                 bm_log_vert_bmvert_copy(lv, v, cd_vert_mask_offset);
259
260                 BM_vert_kill(bm, v);
261         }
262 }
263
264 static void bm_log_faces_unmake(BMesh *bm, BMLog *log, GHash *faces)
265 {
266         GHashIterator gh_iter;
267         GHASH_ITER (gh_iter, faces) {
268                 void *key = BLI_ghashIterator_getKey(&gh_iter);
269                 uint id = POINTER_AS_UINT(key);
270                 BMFace *f = bm_log_face_from_id(log, id);
271                 BMEdge *e_tri[3];
272                 BMLoop *l_iter;
273                 int i;
274
275                 l_iter = BM_FACE_FIRST_LOOP(f);
276                 for (i = 0; i < 3; i++, l_iter = l_iter->next) {
277                         e_tri[i] = l_iter->e;
278                 }
279
280                 /* Remove any unused edges */
281                 BM_face_kill(bm, f);
282                 for (i = 0; i < 3; i++) {
283                         if (BM_edge_is_wire(e_tri[i])) {
284                                 BM_edge_kill(bm, e_tri[i]);
285                         }
286                 }
287         }
288 }
289
290 static void bm_log_verts_restore(BMesh *bm, BMLog *log, GHash *verts)
291 {
292         const int cd_vert_mask_offset = CustomData_get_offset(&bm->vdata, CD_PAINT_MASK);
293
294         GHashIterator gh_iter;
295         GHASH_ITER (gh_iter, verts) {
296                 void *key = BLI_ghashIterator_getKey(&gh_iter);
297                 BMLogVert *lv = BLI_ghashIterator_getValue(&gh_iter);
298                 BMVert *v = BM_vert_create(bm, lv->co, NULL, BM_CREATE_NOP);
299                 vert_mask_set(v, lv->mask, cd_vert_mask_offset);
300                 v->head.hflag = lv->hflag;
301                 normal_short_to_float_v3(v->no, lv->no);
302                 bm_log_vert_id_set(log, v, POINTER_AS_UINT(key));
303         }
304 }
305
306 static void bm_log_faces_restore(BMesh *bm, BMLog *log, GHash *faces)
307 {
308         GHashIterator gh_iter;
309         GHASH_ITER (gh_iter, faces) {
310                 void *key = BLI_ghashIterator_getKey(&gh_iter);
311                 BMLogFace *lf = BLI_ghashIterator_getValue(&gh_iter);
312                 BMVert *v[3] = {bm_log_vert_from_id(log, lf->v_ids[0]),
313                                 bm_log_vert_from_id(log, lf->v_ids[1]),
314                                 bm_log_vert_from_id(log, lf->v_ids[2])};
315                 BMFace *f;
316
317                 f = BM_face_create_verts(bm, v, 3, NULL, BM_CREATE_NOP, true);
318                 f->head.hflag = lf->hflag;
319                 bm_log_face_id_set(log, f, POINTER_AS_UINT(key));
320         }
321 }
322
323 static void bm_log_vert_values_swap(BMesh *bm, BMLog *log, GHash *verts)
324 {
325         const int cd_vert_mask_offset = CustomData_get_offset(&bm->vdata, CD_PAINT_MASK);
326
327         GHashIterator gh_iter;
328         GHASH_ITER (gh_iter, verts) {
329                 void *key = BLI_ghashIterator_getKey(&gh_iter);
330                 BMLogVert *lv = BLI_ghashIterator_getValue(&gh_iter);
331                 uint id = POINTER_AS_UINT(key);
332                 BMVert *v = bm_log_vert_from_id(log, id);
333                 float mask;
334                 short normal[3];
335
336                 swap_v3_v3(v->co, lv->co);
337                 copy_v3_v3_short(normal, lv->no);
338                 normal_float_to_short_v3(lv->no, v->no);
339                 normal_short_to_float_v3(v->no, normal);
340                 SWAP(char, v->head.hflag, lv->hflag);
341                 mask = lv->mask;
342                 lv->mask = vert_mask_get(v, cd_vert_mask_offset);
343                 vert_mask_set(v, mask, cd_vert_mask_offset);
344         }
345 }
346
347 static void bm_log_face_values_swap(BMLog *log, GHash *faces)
348 {
349         GHashIterator gh_iter;
350         GHASH_ITER (gh_iter, faces) {
351                 void *key = BLI_ghashIterator_getKey(&gh_iter);
352                 BMLogFace *lf = BLI_ghashIterator_getValue(&gh_iter);
353                 uint id = POINTER_AS_UINT(key);
354                 BMFace *f = bm_log_face_from_id(log, id);
355
356                 SWAP(char, f->head.hflag, lf->hflag);
357         }
358 }
359
360
361 /**********************************************************************/
362
363 /* Assign unique IDs to all vertices and faces already in the BMesh */
364 static void bm_log_assign_ids(BMesh *bm, BMLog *log)
365 {
366         BMIter iter;
367         BMVert *v;
368         BMFace *f;
369
370         /* Generate vertex IDs */
371         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
372                 uint id = range_tree_uint_take_any(log->unused_ids);
373                 bm_log_vert_id_set(log, v, id);
374         }
375
376         /* Generate face IDs */
377         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
378                 uint id = range_tree_uint_take_any(log->unused_ids);
379                 bm_log_face_id_set(log, f, id);
380         }
381 }
382
383 /* Allocate an empty log entry */
384 static BMLogEntry *bm_log_entry_create(void)
385 {
386         BMLogEntry *entry = MEM_callocN(sizeof(BMLogEntry), __func__);
387
388         entry->deleted_verts = BLI_ghash_new(logkey_hash, logkey_cmp, __func__);
389         entry->deleted_faces = BLI_ghash_new(logkey_hash, logkey_cmp, __func__);
390         entry->added_verts = BLI_ghash_new(logkey_hash, logkey_cmp, __func__);
391         entry->added_faces = BLI_ghash_new(logkey_hash, logkey_cmp, __func__);
392         entry->modified_verts = BLI_ghash_new(logkey_hash, logkey_cmp, __func__);
393         entry->modified_faces = BLI_ghash_new(logkey_hash, logkey_cmp, __func__);
394
395         entry->pool_verts = BLI_mempool_create(sizeof(BMLogVert), 0, 64, BLI_MEMPOOL_NOP);
396         entry->pool_faces = BLI_mempool_create(sizeof(BMLogFace), 0, 64, BLI_MEMPOOL_NOP);
397
398         return entry;
399 }
400
401 /* Free the data in a log entry
402  *
403  * Note: does not free the log entry itself */
404 static void bm_log_entry_free(BMLogEntry *entry)
405 {
406         BLI_ghash_free(entry->deleted_verts, NULL, NULL);
407         BLI_ghash_free(entry->deleted_faces, NULL, NULL);
408         BLI_ghash_free(entry->added_verts, NULL, NULL);
409         BLI_ghash_free(entry->added_faces, NULL, NULL);
410         BLI_ghash_free(entry->modified_verts, NULL, NULL);
411         BLI_ghash_free(entry->modified_faces, NULL, NULL);
412
413         BLI_mempool_destroy(entry->pool_verts);
414         BLI_mempool_destroy(entry->pool_faces);
415 }
416
417 static void bm_log_id_ghash_retake(RangeTreeUInt *unused_ids, GHash *id_ghash)
418 {
419         GHashIterator gh_iter;
420
421         GHASH_ITER (gh_iter, id_ghash) {
422                 void *key = BLI_ghashIterator_getKey(&gh_iter);
423                 uint id = POINTER_AS_UINT(key);
424
425                 range_tree_uint_retake(unused_ids, id);
426         }
427 }
428
429 static int uint_compare(const void *a_v, const void *b_v)
430 {
431         const uint *a = a_v;
432         const uint *b = b_v;
433         return (*a) < (*b);
434 }
435
436 /* Remap IDs to contiguous indices
437  *
438  * E.g. if the vertex IDs are (4, 1, 10, 3), the mapping will be:
439  *    4 -> 2
440  *    1 -> 0
441  *   10 -> 3
442  *    3 -> 1
443  */
444 static GHash *bm_log_compress_ids_to_indices(uint *ids, uint totid)
445 {
446         GHash *map = BLI_ghash_int_new_ex(__func__, totid);
447         uint i;
448
449         qsort(ids, totid, sizeof(*ids), uint_compare);
450
451         for (i = 0; i < totid; i++) {
452                 void *key = POINTER_FROM_UINT(ids[i]);
453                 void *val = POINTER_FROM_UINT(i);
454                 BLI_ghash_insert(map, key, val);
455         }
456
457         return map;
458 }
459
460 /* Release all ID keys in id_ghash */
461 static void bm_log_id_ghash_release(BMLog *log, GHash *id_ghash)
462 {
463         GHashIterator gh_iter;
464
465         GHASH_ITER (gh_iter, id_ghash) {
466                 void *key = BLI_ghashIterator_getKey(&gh_iter);
467                 uint id = POINTER_AS_UINT(key);
468                 range_tree_uint_release(log->unused_ids, id);
469         }
470 }
471
472 /***************************** Public API *****************************/
473
474 /* Allocate, initialize, and assign a new BMLog */
475 BMLog *BM_log_create(BMesh *bm)
476 {
477         BMLog *log = MEM_callocN(sizeof(*log), __func__);
478         const uint reserve_num = (uint)(bm->totvert + bm->totface);
479
480         log->unused_ids = range_tree_uint_alloc(0, (unsigned)-1);
481         log->id_to_elem = BLI_ghash_new_ex(logkey_hash, logkey_cmp, __func__, reserve_num);
482         log->elem_to_id = BLI_ghash_ptr_new_ex(__func__, reserve_num);
483
484         /* Assign IDs to all existing vertices and faces */
485         bm_log_assign_ids(bm, log);
486
487         return log;
488 }
489
490 void BM_log_cleanup_entry(BMLogEntry *entry)
491 {
492         BMLog *log = entry->log;
493
494         if (log) {
495                 /* Take all used IDs */
496                 bm_log_id_ghash_retake(log->unused_ids, entry->deleted_verts);
497                 bm_log_id_ghash_retake(log->unused_ids, entry->deleted_faces);
498                 bm_log_id_ghash_retake(log->unused_ids, entry->added_verts);
499                 bm_log_id_ghash_retake(log->unused_ids, entry->added_faces);
500                 bm_log_id_ghash_retake(log->unused_ids, entry->modified_verts);
501                 bm_log_id_ghash_retake(log->unused_ids, entry->modified_faces);
502
503                 /* delete entries to avoid releasing ids in node cleanup */
504                 BLI_ghash_clear(entry->deleted_verts, NULL, NULL);
505                 BLI_ghash_clear(entry->deleted_faces, NULL, NULL);
506                 BLI_ghash_clear(entry->added_verts, NULL, NULL);
507                 BLI_ghash_clear(entry->added_faces, NULL, NULL);
508                 BLI_ghash_clear(entry->modified_verts, NULL, NULL);
509         }
510 }
511
512
513 /* Allocate and initialize a new BMLog using existing BMLogEntries
514  *
515  * The 'entry' should be the last entry in the BMLog. Its prev pointer
516  * will be followed back to find the first entry.
517  *
518  * The unused IDs field of the log will be initialized by taking all
519  * keys from all GHashes in the log entry.
520  */
521 BMLog *BM_log_from_existing_entries_create(BMesh *bm, BMLogEntry *entry)
522 {
523         BMLog *log = BM_log_create(bm);
524
525         if (entry->prev)
526                 log->current_entry = entry;
527         else
528                 log->current_entry = NULL;
529
530         /* Let BMLog manage the entry list again */
531         log->entries.first = log->entries.last = entry;
532
533         {
534                 while (entry->prev) {
535                         entry = entry->prev;
536                         log->entries.first = entry;
537                 }
538                 entry = log->entries.last;
539                 while (entry->next) {
540                         entry = entry->next;
541                         log->entries.last = entry;
542                 }
543         }
544
545         for (entry = log->entries.first; entry; entry = entry->next) {
546                 entry->log = log;
547
548                 /* Take all used IDs */
549                 bm_log_id_ghash_retake(log->unused_ids, entry->deleted_verts);
550                 bm_log_id_ghash_retake(log->unused_ids, entry->deleted_faces);
551                 bm_log_id_ghash_retake(log->unused_ids, entry->added_verts);
552                 bm_log_id_ghash_retake(log->unused_ids, entry->added_faces);
553                 bm_log_id_ghash_retake(log->unused_ids, entry->modified_verts);
554                 bm_log_id_ghash_retake(log->unused_ids, entry->modified_faces);
555         }
556
557         return log;
558 }
559
560 /* Free all the data in a BMLog including the log itself */
561 void BM_log_free(BMLog *log)
562 {
563         BMLogEntry *entry;
564
565         if (log->unused_ids)
566                 range_tree_uint_free(log->unused_ids);
567
568         if (log->id_to_elem)
569                 BLI_ghash_free(log->id_to_elem, NULL, NULL);
570
571         if (log->elem_to_id)
572                 BLI_ghash_free(log->elem_to_id, NULL, NULL);
573
574         /* Clear the BMLog references within each entry, but do not free
575          * the entries themselves */
576         for (entry = log->entries.first; entry; entry = entry->next)
577                 entry->log = NULL;
578
579         MEM_freeN(log);
580 }
581
582 /* Get the number of log entries */
583 int BM_log_length(const BMLog *log)
584 {
585         return BLI_listbase_count(&log->entries);
586 }
587
588 /* Apply a consistent ordering to BMesh vertices */
589 void BM_log_mesh_elems_reorder(BMesh *bm, BMLog *log)
590 {
591         uint *varr;
592         uint *farr;
593
594         GHash *id_to_idx;
595
596         BMIter bm_iter;
597         BMVert *v;
598         BMFace *f;
599
600         uint i;
601
602         /* Put all vertex IDs into an array */
603         varr = MEM_mallocN(sizeof(int) * (size_t)bm->totvert, __func__);
604         BM_ITER_MESH_INDEX (v, &bm_iter, bm, BM_VERTS_OF_MESH, i) {
605                 varr[i] = bm_log_vert_id_get(log, v);
606         }
607
608         /* Put all face IDs into an array */
609         farr = MEM_mallocN(sizeof(int) * (size_t)bm->totface, __func__);
610         BM_ITER_MESH_INDEX (f, &bm_iter, bm, BM_FACES_OF_MESH, i) {
611                 farr[i] = bm_log_face_id_get(log, f);
612         }
613
614         /* Create BMVert index remap array */
615         id_to_idx = bm_log_compress_ids_to_indices(varr, (uint)bm->totvert);
616         BM_ITER_MESH_INDEX (v, &bm_iter, bm, BM_VERTS_OF_MESH, i) {
617                 const unsigned id = bm_log_vert_id_get(log, v);
618                 const void *key = POINTER_FROM_UINT(id);
619                 const void *val = BLI_ghash_lookup(id_to_idx, key);
620                 varr[i] = POINTER_AS_UINT(val);
621         }
622         BLI_ghash_free(id_to_idx, NULL, NULL);
623
624         /* Create BMFace index remap array */
625         id_to_idx = bm_log_compress_ids_to_indices(farr, (uint)bm->totface);
626         BM_ITER_MESH_INDEX (f, &bm_iter, bm, BM_FACES_OF_MESH, i) {
627                 const unsigned id = bm_log_face_id_get(log, f);
628                 const void *key = POINTER_FROM_UINT(id);
629                 const void *val = BLI_ghash_lookup(id_to_idx, key);
630                 farr[i] = POINTER_AS_UINT(val);
631         }
632         BLI_ghash_free(id_to_idx, NULL, NULL);
633
634         BM_mesh_remap(bm, varr, NULL, farr);
635
636         MEM_freeN(varr);
637         MEM_freeN(farr);
638 }
639
640 /* Start a new log entry and update the log entry list
641  *
642  * If the log entry list is empty, or if the current log entry is the
643  * last entry, the new entry is simply appended to the end.
644  *
645  * Otherwise, the new entry is added after the current entry and all
646  * following entries are deleted.
647  *
648  * In either case, the new entry is set as the current log entry.
649  */
650 BMLogEntry *BM_log_entry_add(BMLog *log)
651 {
652         /* WARNING: this is now handled by the UndoSystem: BKE_UNDOSYS_TYPE_SCULPT
653          * freeing here causes unnecessary complications. */
654         BMLogEntry *entry;
655 #if 0
656         /* Delete any entries after the current one */
657         entry = log->current_entry;
658         if (entry) {
659                 BMLogEntry *next;
660                 for (entry = entry->next; entry; entry = next) {
661                         next = entry->next;
662                         bm_log_entry_free(entry);
663                         BLI_freelinkN(&log->entries, entry);
664                 }
665         }
666 #endif
667
668         /* Create and append the new entry */
669         entry = bm_log_entry_create();
670         BLI_addtail(&log->entries, entry);
671         entry->log = log;
672         log->current_entry = entry;
673
674         return entry;
675 }
676
677 /* Remove an entry from the log
678  *
679  * Uses entry->log as the log. If the log is NULL, the entry will be
680  * free'd but not removed from any list, nor shall its IDs be
681  * released.
682  *
683  * This operation is only valid on the first and last entries in the
684  * log. Deleting from the middle will assert.
685  */
686 void BM_log_entry_drop(BMLogEntry *entry)
687 {
688         BMLog *log = entry->log;
689
690         if (!log) {
691                 /* Unlink */
692                 BLI_assert(!(entry->prev && entry->next));
693                 if (entry->prev)
694                         entry->prev->next = NULL;
695                 else if (entry->next)
696                         entry->next->prev = NULL;
697
698                 bm_log_entry_free(entry);
699                 MEM_freeN(entry);
700                 return;
701         }
702
703         if (!entry->prev) {
704                 /* Release IDs of elements that are deleted by this
705                  * entry. Since the entry is at the beginning of the undo
706                  * stack, and it's being deleted, those elements can never be
707                  * restored. Their IDs can go back into the pool. */
708
709                 /* This would never happen usually since first entry of log is
710                  * usually dyntopo enable, which, when reverted will free the log
711                  * completely. However, it is possible have a stroke instead of
712                  * dyntopo enable as first entry if nodes have been cleaned up
713                  * after sculpting on a different object than A, B.
714                  *
715                  * The steps are:
716                  * A dyntopo enable - sculpt
717                  * B dyntopo enable - sculpt - undo (A objects operators get cleaned up)
718                  * A sculpt (now A's log has a sculpt operator as first entry)
719                  *
720                  * Causing a cleanup at this point will call the code below, however
721                  * this will invalidate the state of the log since the deleted vertices
722                  * have been reclaimed already on step 2 (see BM_log_cleanup_entry)
723                  *
724                  * Also, design wise, a first entry should not have any deleted vertices since it
725                  * should not have anything to delete them -from-
726                  */
727                 //bm_log_id_ghash_release(log, entry->deleted_faces);
728                 //bm_log_id_ghash_release(log, entry->deleted_verts);
729         }
730         else if (!entry->next) {
731                 /* Release IDs of elements that are added by this entry. Since
732                  * the entry is at the end of the undo stack, and it's being
733                  * deleted, those elements can never be restored. Their IDs
734                  * can go back into the pool. */
735                 bm_log_id_ghash_release(log, entry->added_faces);
736                 bm_log_id_ghash_release(log, entry->added_verts);
737         }
738         else {
739                 BLI_assert(!"Cannot drop BMLogEntry from middle");
740         }
741
742         if (log->current_entry == entry)
743                 log->current_entry = entry->prev;
744
745         bm_log_entry_free(entry);
746         BLI_freelinkN(&log->entries, entry);
747 }
748
749 /* Undo one BMLogEntry
750  *
751  * Has no effect if there's nothing left to undo */
752 void BM_log_undo(BMesh *bm, BMLog *log)
753 {
754         BMLogEntry *entry = log->current_entry;
755
756         if (entry) {
757                 log->current_entry = entry->prev;
758
759                 /* Delete added faces and verts */
760                 bm_log_faces_unmake(bm, log, entry->added_faces);
761                 bm_log_verts_unmake(bm, log, entry->added_verts);
762
763                 /* Restore deleted verts and faces */
764                 bm_log_verts_restore(bm, log, entry->deleted_verts);
765                 bm_log_faces_restore(bm, log, entry->deleted_faces);
766
767                 /* Restore vertex coordinates, mask, and hflag */
768                 bm_log_vert_values_swap(bm, log, entry->modified_verts);
769                 bm_log_face_values_swap(log, entry->modified_faces);
770         }
771 }
772
773 /* Redo one BMLogEntry
774  *
775  * Has no effect if there's nothing left to redo */
776 void BM_log_redo(BMesh *bm, BMLog *log)
777 {
778         BMLogEntry *entry = log->current_entry;
779
780         if (!entry) {
781                 /* Currently at the beginning of the undo stack, move to first entry */
782                 entry = log->entries.first;
783         }
784         else if (entry && entry->next) {
785                 /* Move to next undo entry */
786                 entry = entry->next;
787         }
788         else {
789                 /* Currently at the end of the undo stack, nothing left to redo */
790                 return;
791         }
792
793         log->current_entry = entry;
794
795         if (entry) {
796                 /* Re-delete previously deleted faces and verts */
797                 bm_log_faces_unmake(bm, log, entry->deleted_faces);
798                 bm_log_verts_unmake(bm, log, entry->deleted_verts);
799
800                 /* Restore previously added verts and faces */
801                 bm_log_verts_restore(bm, log, entry->added_verts);
802                 bm_log_faces_restore(bm, log, entry->added_faces);
803
804                 /* Restore vertex coordinates, mask, and hflag */
805                 bm_log_vert_values_swap(bm, log, entry->modified_verts);
806                 bm_log_face_values_swap(log, entry->modified_faces);
807         }
808 }
809
810 /* Log a vertex before it is modified
811  *
812  * Before modifying vertex coordinates, masks, or hflags, call this
813  * function to log it's current values. This is better than logging
814  * after the coordinates have been modified, because only those
815  * vertices that are modified need to have their original values
816  * stored.
817  *
818  * Handles two separate cases:
819  *
820  * If the vertex was added in the current log entry, update the
821  * vertex in the map of added vertices.
822  *
823  * If the vertex already existed prior to the current log entry, a
824  * separate key/value map of modified vertices is used (using the
825  * vertex's ID as the key). The values stored in that case are
826  * the vertex's original state so that an undo can restore the
827  * previous state.
828  *
829  * On undo, the current vertex state will be swapped with the stored
830  * state so that a subsequent redo operation will restore the newer
831  * vertex state.
832  */
833 void BM_log_vert_before_modified(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
834 {
835         BMLogEntry *entry = log->current_entry;
836         BMLogVert *lv;
837         uint v_id = bm_log_vert_id_get(log, v);
838         void *key = POINTER_FROM_UINT(v_id);
839         void **val_p;
840
841         /* Find or create the BMLogVert entry */
842         if ((lv = BLI_ghash_lookup(entry->added_verts, key))) {
843                 bm_log_vert_bmvert_copy(lv, v, cd_vert_mask_offset);
844         }
845         else if (!BLI_ghash_ensure_p(entry->modified_verts, key, &val_p)) {
846                 lv = bm_log_vert_alloc(log, v, cd_vert_mask_offset);
847                 *val_p = lv;
848         }
849 }
850
851
852 /* Log a new vertex as added to the BMesh
853  *
854  * The new vertex gets a unique ID assigned. It is then added to a map
855  * of added vertices, with the key being its ID and the value
856  * containing everything needed to reconstruct that vertex.
857  */
858 void BM_log_vert_added(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
859 {
860         BMLogVert *lv;
861         uint v_id = range_tree_uint_take_any(log->unused_ids);
862         void *key = POINTER_FROM_UINT(v_id);
863
864         bm_log_vert_id_set(log, v, v_id);
865         lv = bm_log_vert_alloc(log, v, cd_vert_mask_offset);
866         BLI_ghash_insert(log->current_entry->added_verts, key, lv);
867 }
868
869
870 /* Log a face before it is modified
871  *
872  * This is intended to handle only header flags and we always
873  * assume face has been added before
874  */
875 void BM_log_face_modified(BMLog *log, BMFace *f)
876 {
877         BMLogFace *lf;
878         uint f_id = bm_log_face_id_get(log, f);
879         void *key = POINTER_FROM_UINT(f_id);
880
881         lf = bm_log_face_alloc(log, f);
882         BLI_ghash_insert(log->current_entry->modified_faces, key, lf);
883 }
884
885 /* Log a new face as added to the BMesh
886  *
887  * The new face gets a unique ID assigned. It is then added to a map
888  * of added faces, with the key being its ID and the value containing
889  * everything needed to reconstruct that face.
890  */
891 void BM_log_face_added(BMLog *log, BMFace *f)
892 {
893         BMLogFace *lf;
894         uint f_id = range_tree_uint_take_any(log->unused_ids);
895         void *key = POINTER_FROM_UINT(f_id);
896
897         /* Only triangles are supported for now */
898         BLI_assert(f->len == 3);
899
900         bm_log_face_id_set(log, f, f_id);
901         lf = bm_log_face_alloc(log, f);
902         BLI_ghash_insert(log->current_entry->added_faces, key, lf);
903 }
904
905 /* Log a vertex as removed from the BMesh
906  *
907  * A couple things can happen here:
908  *
909  * If the vertex was added as part of the current log entry, then it's
910  * deleted and forgotten about entirely. Its unique ID is returned to
911  * the unused pool.
912  *
913  * If the vertex was already part of the BMesh before the current log
914  * entry, it is added to a map of deleted vertices, with the key being
915  * its ID and the value containing everything needed to reconstruct
916  * that vertex.
917  *
918  * If there's a move record for the vertex, that's used as the
919  * vertices original location, then the move record is deleted.
920  */
921 void BM_log_vert_removed(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
922 {
923         BMLogEntry *entry = log->current_entry;
924         uint v_id = bm_log_vert_id_get(log, v);
925         void *key = POINTER_FROM_UINT(v_id);
926
927         /* if it has a key, it shouldn't be NULL */
928         BLI_assert(!!BLI_ghash_lookup(entry->added_verts, key) ==
929                    !!BLI_ghash_haskey(entry->added_verts, key));
930
931         if (BLI_ghash_remove(entry->added_verts, key, NULL, NULL)) {
932                 range_tree_uint_release(log->unused_ids, v_id);
933         }
934         else {
935                 BMLogVert *lv, *lv_mod;
936
937                 lv = bm_log_vert_alloc(log, v, cd_vert_mask_offset);
938                 BLI_ghash_insert(entry->deleted_verts, key, lv);
939
940                 /* If the vertex was modified before deletion, ensure that the
941                  * original vertex values are stored */
942                 if ((lv_mod = BLI_ghash_lookup(entry->modified_verts, key))) {
943                         (*lv) = (*lv_mod);
944                         BLI_ghash_remove(entry->modified_verts, key, NULL, NULL);
945                 }
946         }
947 }
948
949 /* Log a face as removed from the BMesh
950  *
951  * A couple things can happen here:
952  *
953  * If the face was added as part of the current log entry, then it's
954  * deleted and forgotten about entirely. Its unique ID is returned to
955  * the unused pool.
956  *
957  * If the face was already part of the BMesh before the current log
958  * entry, it is added to a map of deleted faces, with the key being
959  * its ID and the value containing everything needed to reconstruct
960  * that face.
961  */
962 void BM_log_face_removed(BMLog *log, BMFace *f)
963 {
964         BMLogEntry *entry = log->current_entry;
965         uint f_id = bm_log_face_id_get(log, f);
966         void *key = POINTER_FROM_UINT(f_id);
967
968         /* if it has a key, it shouldn't be NULL */
969         BLI_assert(!!BLI_ghash_lookup(entry->added_faces, key) ==
970                    !!BLI_ghash_haskey(entry->added_faces, key));
971
972         if (BLI_ghash_remove(entry->added_faces, key, NULL, NULL)) {
973                 range_tree_uint_release(log->unused_ids, f_id);
974         }
975         else {
976                 BMLogFace *lf;
977
978                 lf = bm_log_face_alloc(log, f);
979                 BLI_ghash_insert(entry->deleted_faces, key, lf);
980         }
981 }
982
983 /* Log all vertices/faces in the BMesh as added */
984 void BM_log_all_added(BMesh *bm, BMLog *log)
985 {
986         const int cd_vert_mask_offset = CustomData_get_offset(&bm->vdata, CD_PAINT_MASK);
987         BMIter bm_iter;
988         BMVert *v;
989         BMFace *f;
990
991         /* avoid unnecessary resizing on initialization */
992         if (BLI_ghash_len(log->current_entry->added_verts) == 0) {
993                 BLI_ghash_reserve(log->current_entry->added_verts, (uint)bm->totvert);
994         }
995
996         if (BLI_ghash_len(log->current_entry->added_faces) == 0) {
997                 BLI_ghash_reserve(log->current_entry->added_faces, (uint)bm->totface);
998         }
999
1000         /* Log all vertices as newly created */
1001         BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) {
1002                 BM_log_vert_added(log, v, cd_vert_mask_offset);
1003         }
1004
1005         /* Log all faces as newly created */
1006         BM_ITER_MESH (f, &bm_iter, bm, BM_FACES_OF_MESH) {
1007                 BM_log_face_added(log, f);
1008         }
1009 }
1010
1011 /* Log all vertices/faces in the BMesh as removed */
1012 void BM_log_before_all_removed(BMesh *bm, BMLog *log)
1013 {
1014         const int cd_vert_mask_offset = CustomData_get_offset(&bm->vdata, CD_PAINT_MASK);
1015         BMIter bm_iter;
1016         BMVert *v;
1017         BMFace *f;
1018
1019         /* Log deletion of all faces */
1020         BM_ITER_MESH (f, &bm_iter, bm, BM_FACES_OF_MESH) {
1021                 BM_log_face_removed(log, f);
1022         }
1023
1024         /* Log deletion of all vertices */
1025         BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) {
1026                 BM_log_vert_removed(log, v, cd_vert_mask_offset);
1027         }
1028 }
1029
1030 /* Get the logged coordinates of a vertex
1031  *
1032  * Does not modify the log or the vertex */
1033 const float *BM_log_original_vert_co(BMLog *log, BMVert *v)
1034 {
1035         BMLogEntry *entry = log->current_entry;
1036         const BMLogVert *lv;
1037         unsigned v_id = bm_log_vert_id_get(log, v);
1038         void *key = POINTER_FROM_UINT(v_id);
1039
1040         BLI_assert(entry);
1041
1042         BLI_assert(BLI_ghash_haskey(entry->modified_verts, key));
1043
1044         lv = BLI_ghash_lookup(entry->modified_verts, key);
1045         return lv->co;
1046 }
1047
1048 /* Get the logged normal of a vertex
1049  *
1050  * Does not modify the log or the vertex */
1051 const short *BM_log_original_vert_no(BMLog *log, BMVert *v)
1052 {
1053         BMLogEntry *entry = log->current_entry;
1054         const BMLogVert *lv;
1055         unsigned v_id = bm_log_vert_id_get(log, v);
1056         void *key = POINTER_FROM_UINT(v_id);
1057
1058         BLI_assert(entry);
1059
1060         BLI_assert(BLI_ghash_haskey(entry->modified_verts, key));
1061
1062         lv = BLI_ghash_lookup(entry->modified_verts, key);
1063         return lv->no;
1064 }
1065
1066 /* Get the logged mask of a vertex
1067  *
1068  * Does not modify the log or the vertex */
1069 float BM_log_original_mask(BMLog *log, BMVert *v)
1070 {
1071         BMLogEntry *entry = log->current_entry;
1072         const BMLogVert *lv;
1073         unsigned v_id = bm_log_vert_id_get(log, v);
1074         void *key = POINTER_FROM_UINT(v_id);
1075
1076         BLI_assert(entry);
1077
1078         BLI_assert(BLI_ghash_haskey(entry->modified_verts, key));
1079
1080         lv = BLI_ghash_lookup(entry->modified_verts, key);
1081         return lv->mask;
1082 }
1083
1084 void BM_log_original_vert_data(
1085         BMLog *log, BMVert *v,
1086         const float **r_co, const short **r_no)
1087 {
1088         BMLogEntry *entry = log->current_entry;
1089         const BMLogVert *lv;
1090         unsigned v_id = bm_log_vert_id_get(log, v);
1091         void *key = POINTER_FROM_UINT(v_id);
1092
1093         BLI_assert(entry);
1094
1095         BLI_assert(BLI_ghash_haskey(entry->modified_verts, key));
1096
1097         lv = BLI_ghash_lookup(entry->modified_verts, key);
1098         *r_co = lv->co;
1099         *r_no = lv->no;
1100 }
1101
1102 /************************ Debugging and Testing ***********************/
1103
1104 /* For internal use only (unit testing) */
1105 BMLogEntry *BM_log_current_entry(BMLog *log)
1106 {
1107         return log->current_entry;
1108 }
1109
1110 /* For internal use only (unit testing) */
1111 RangeTreeUInt *BM_log_unused_ids(BMLog *log)
1112 {
1113         return log->unused_ids;
1114 }
1115
1116 #if 0
1117 /* Print the list of entries, marking the current one
1118  *
1119  * Keep around for debugging */
1120 void bm_log_print(const BMLog *log, const char *description)
1121 {
1122         const BMLogEntry *entry;
1123         const char *current = " <-- current";
1124         int i;
1125
1126         printf("%s:\n", description);
1127         printf("    % 2d: [ initial ]%s\n", 0,
1128                    (!log->current_entry) ? current : "");
1129         for (entry = log->entries.first, i = 1; entry; entry = entry->next, i++) {
1130                 printf("    % 2d: [%p]%s\n", i, entry,
1131                            (entry == log->current_entry) ? current : "");
1132         }
1133 }
1134 #endif