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