diff options
author | Nicholas Bishop <nicholasbishop@gmail.com> | 2012-12-30 22:24:08 +0400 |
---|---|---|
committer | Nicholas Bishop <nicholasbishop@gmail.com> | 2012-12-30 22:24:08 +0400 |
commit | 2e9cb31c02378fd5b9b3f26f6f26501d1aa999a2 (patch) | |
tree | 0721978f5d0649841e4c817edf16791e8e2fe8da /source/blender | |
parent | 1b4b5f98cb2f568c55d00ca546878b1a6959dad9 (diff) |
Add BMLog for efficiently storing changes to vertices and faces
The BMLog is an interface for storing undo/redo steps as a BMesh is
modified. It only stores changes to the BMesh, not full copies.
Currently it supports the following types of changes:
- Adding and removing vertices
- Adding and removing faces
- Moving vertices
- Setting vertex paint-mask values
- Setting vertex hflags
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/bmesh/CMakeLists.txt | 3 | ||||
-rw-r--r-- | source/blender/bmesh/SConscript | 4 | ||||
-rw-r--r-- | source/blender/bmesh/bmesh.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_log.c | 962 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_log.h | 102 |
5 files changed, 1071 insertions, 1 deletions
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index c41b0703240..955b18c3db7 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -31,6 +31,7 @@ set(INC ../makesdna ../../../intern/guardedalloc ../../../extern/bullet2/src + ../../../extern/rangetree ../../../intern/opennl/extern ) @@ -74,6 +75,8 @@ set(SRC intern/bmesh_iterators.c intern/bmesh_iterators.h intern/bmesh_iterators_inline.h + intern/bmesh_log.c + intern/bmesh_log.h intern/bmesh_marking.c intern/bmesh_marking.h intern/bmesh_mesh.c diff --git a/source/blender/bmesh/SConscript b/source/blender/bmesh/SConscript index 722b7518630..a8ca514297e 100644 --- a/source/blender/bmesh/SConscript +++ b/source/blender/bmesh/SConscript @@ -41,7 +41,9 @@ incs = [ '../blenkernel', '#/intern/guardedalloc', '#/extern/bullet2/src', - '#/intern/opennl/extern', ] + '#/extern/rangetree', + '#/intern/opennl/extern' + ] defs = [] diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h index 6257aa4bf3e..60d38719ddb 100644 --- a/source/blender/bmesh/bmesh.h +++ b/source/blender/bmesh/bmesh.h @@ -254,6 +254,7 @@ extern "C" { #include "intern/bmesh_core.h" #include "intern/bmesh_interp.h" #include "intern/bmesh_iterators.h" +#include "intern/bmesh_log.h" #include "intern/bmesh_marking.h" #include "intern/bmesh_mesh.h" #include "intern/bmesh_mesh_conv.h" diff --git a/source/blender/bmesh/intern/bmesh_log.c b/source/blender/bmesh/intern/bmesh_log.c new file mode 100644 index 00000000000..1e94e81e6d7 --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_log.c @@ -0,0 +1,962 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_ghash.h" +#include "BLI_listbase.h" +#include "BLI_math.h" +#include "BLI_mempool.h" +#include "BLI_utildefines.h" + +#include "BKE_customdata.h" + +#include "bmesh.h" +#include "bmesh_log.h" +#include "range_tree_c_api.h" + +struct BMLogEntry { + struct BMLogEntry *next, *prev; + + /* The following GHashes map from an element ID to one of the log + * types above */ + + /* Elements that were in the previous entry, but have been + * deleted */ + GHash *deleted_verts; + GHash *deleted_faces; + /* Elements that were not in the previous entry, but are in the + * result of this entry */ + GHash *added_verts; + GHash *added_faces; + + /* Vertices whose coordinates, mask value, or hflag have changed */ + GHash *modified_verts; + + BLI_mempool *pool_verts; + BLI_mempool *pool_faces; + + /* This is only needed for dropping BMLogEntries while still in + * dynamic-topology mode, as that should release vert/face IDs + * back to the BMLog but no BMLog pointer is available at that + * time. + * + * This field is not guaranteed to be valid, any use of it should + * check for NULL. */ + BMLog *log; +}; + +struct BMLog { + /* Tree of free IDs */ + struct RangeTreeUInt *unused_ids; + + /* Mapping from unique IDs to vertices and faces + * + * Each vertex and face in the log gets a unique unsigned integer + * assigned. That ID is taken from the set managed by the + * unused_ids range tree. + * + * The ID is needed because element pointers will change as they + * are created and deleted. + */ + GHash *id_to_elem; + GHash *elem_to_id; + + /* All BMLogEntrys, ordered from earliest to most recent */ + ListBase entries; + + /* The current log entry from entries list + * + * If null, then the original mesh from before any of the log + * entries is current (i.e. there is nothing left to undo.) + * + * If equal to the last entry in the entries list, then all log + * entries have been applied (i.e. there is nothing left to redo.) + */ + BMLogEntry *current_entry; +}; + +typedef struct { + float co[3]; + float mask; + char hflag; +} BMLogVert; + +typedef struct { + unsigned int v_ids[3]; +} BMLogFace; + +/************************* Get/set element IDs ************************/ + +/* Get the vertex's unique ID from the log */ +static unsigned int bm_log_vert_id_get(BMLog *log, BMVert *v) +{ + BLI_assert(BLI_ghash_haskey(log->elem_to_id, v)); + return GET_INT_FROM_POINTER(BLI_ghash_lookup(log->elem_to_id, v)); +} + +/* Set the vertex's unique ID in the log */ +static void bm_log_vert_id_set(BMLog *log, BMVert *v, unsigned int id) +{ + void *vid = SET_INT_IN_POINTER(id); + + BLI_ghash_remove(log->id_to_elem, vid, NULL, NULL); + BLI_ghash_insert(log->id_to_elem, vid, v); + BLI_ghash_remove(log->elem_to_id, v, NULL, NULL); + BLI_ghash_insert(log->elem_to_id, v, vid); +} + +/* Get a vertex from its unique ID */ +static BMVert *bm_log_vert_from_id(BMLog *log, unsigned int id) +{ + void *key = SET_INT_IN_POINTER(id); + BLI_assert(BLI_ghash_haskey(log->id_to_elem, key)); + return BLI_ghash_lookup(log->id_to_elem, key); +} + +/* Get the face's unique ID from the log */ +static unsigned int bm_log_face_id_get(BMLog *log, BMFace *f) +{ + BLI_assert(BLI_ghash_haskey(log->elem_to_id, f)); + return GET_INT_FROM_POINTER(BLI_ghash_lookup(log->elem_to_id, f)); +} + +/* Set the face's unique ID in the log */ +static void bm_log_face_id_set(BMLog *log, BMFace *f, unsigned int id) +{ + void *fid = SET_INT_IN_POINTER(id); + + BLI_ghash_remove(log->id_to_elem, fid, NULL, NULL); + BLI_ghash_insert(log->id_to_elem, fid, f); + BLI_ghash_remove(log->elem_to_id, f, NULL, NULL); + BLI_ghash_insert(log->elem_to_id, f, fid); +} + +/* Get a face from its unique ID */ +static BMFace *bm_log_face_from_id(BMLog *log, unsigned int id) +{ + void *key = SET_INT_IN_POINTER(id); + BLI_assert(BLI_ghash_haskey(log->id_to_elem, key)); + return BLI_ghash_lookup(log->id_to_elem, key); +} + + +/************************ BMLogVert / BMLogFace ***********************/ + +/* Get a vertex's paint-mask value + * + * Returns zero if no paint-mask layer is present */ +static float vert_mask_get(BMesh *bm, BMVert *v) +{ + CustomData *cd = &bm->vdata; + if (CustomData_has_layer(&bm->vdata, CD_PAINT_MASK)) { + float *mask = CustomData_bmesh_get(cd, v->head.data, CD_PAINT_MASK); + return *mask; + } + else { + return 0; + } +} + +/* Set a vertex's paint-mask value + * + * Has no effect is no paint-mask layer is present */ +static void vert_mask_set(BMesh *bm, BMVert *v, float new_mask) +{ + CustomData *cd = &bm->vdata; + if (CustomData_has_layer(cd, CD_PAINT_MASK)) { + float *mask = CustomData_bmesh_get(cd, v->head.data, CD_PAINT_MASK); + (*mask) = new_mask; + } +} + +/* Update a BMLogVert with data from a BMVert */ +static void bm_log_vert_bmvert_copy(BMesh *bm, BMLogVert *lv, BMVert *v) +{ + copy_v3_v3(lv->co, v->co); + lv->mask = vert_mask_get(bm, v); + lv->hflag = v->head.hflag; +} + +/* Allocate and initialize a BMLogVert */ +static BMLogVert *bm_log_vert_alloc(BMesh *bm, BMLog *log, BMVert *v) +{ + BMLogEntry *entry = log->current_entry; + BMLogVert *lv = BLI_mempool_alloc(entry->pool_verts); + + bm_log_vert_bmvert_copy(bm, lv, v); + + return lv; +} + +/* Allocate and initialize a BMLogFace */ +static BMLogFace *bm_log_face_alloc(BMLog *log, BMFace *f) +{ + BMLogEntry *entry = log->current_entry; + BMLogFace *lf = BLI_mempool_alloc(entry->pool_faces); + BMVert *v[3]; + + BLI_assert(f->len == 3); + + BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v, 3); + + lf->v_ids[0] = bm_log_vert_id_get(log, v[0]); + lf->v_ids[1] = bm_log_vert_id_get(log, v[1]); + lf->v_ids[2] = bm_log_vert_id_get(log, v[2]); + + return lf; +} + + +/************************ Helpers for undo/redo ***********************/ + +static void bm_log_verts_unmake(BMesh *bm, BMLog *log, GHash *verts) +{ + GHashIterator gh_iter; + GHASH_ITER (gh_iter, verts) { + void *key = BLI_ghashIterator_getKey(&gh_iter); + BMLogVert *lv = BLI_ghashIterator_getValue(&gh_iter); + unsigned int id = GET_INT_FROM_POINTER(key); + BMVert *v = bm_log_vert_from_id(log, id); + + /* Ensure the log has the final values of the vertex before + * deleting it */ + bm_log_vert_bmvert_copy(bm, lv, v); + + BM_vert_kill(bm, v); + } +} + +static void bm_log_faces_unmake(BMesh *bm, BMLog *log, GHash *faces) +{ + GHashIterator gh_iter; + GHASH_ITER (gh_iter, faces) { + void *key = BLI_ghashIterator_getKey(&gh_iter); + unsigned int id = GET_INT_FROM_POINTER(key); + BMFace *f = bm_log_face_from_id(log, id); + + BM_face_kill(bm, f); + } +} + +static void bm_log_verts_restore(BMesh *bm, BMLog *log, GHash *verts) +{ + GHashIterator gh_iter; + GHASH_ITER (gh_iter, verts) { + void *key = BLI_ghashIterator_getKey(&gh_iter); + BMLogVert *lv = BLI_ghashIterator_getValue(&gh_iter); + BMVert *v = BM_vert_create(bm, lv->co, NULL, 0); + v->head.hflag = lv->hflag; + vert_mask_set(bm, v, lv->mask); + bm_log_vert_id_set(log, v, GET_INT_FROM_POINTER(key)); + } +} + +static void bm_log_faces_restore(BMesh *bm, BMLog *log, GHash *faces) +{ + GHashIterator gh_iter; + GHASH_ITER (gh_iter, faces) { + void *key = BLI_ghashIterator_getKey(&gh_iter); + BMLogFace *lf = BLI_ghashIterator_getValue(&gh_iter); + BMVert *v[3] = {bm_log_vert_from_id(log, lf->v_ids[0]), + bm_log_vert_from_id(log, lf->v_ids[1]), + bm_log_vert_from_id(log, lf->v_ids[2])}; + BMFace *f; + + f = BM_face_create_quad_tri_v(bm, v, 3, NULL, FALSE); + bm_log_face_id_set(log, f, GET_INT_FROM_POINTER(key)); + } +} + +static void bm_log_vert_values_swap(BMesh *bm, BMLog *log, GHash *verts) +{ + GHashIterator gh_iter; + GHASH_ITER (gh_iter, verts) { + void *key = BLI_ghashIterator_getKey(&gh_iter); + BMLogVert *lv = BLI_ghashIterator_getValue(&gh_iter); + unsigned int id = GET_INT_FROM_POINTER(key); + BMVert *v = bm_log_vert_from_id(log, id); + float mask; + + swap_v3_v3(v->co, lv->co); + SWAP(char, v->head.hflag, lv->hflag); + mask = lv->mask; + lv->mask = vert_mask_get(bm, v); + vert_mask_set(bm, v, mask); + } +} + + +/**********************************************************************/ + +/* Assign unique IDs to all vertices and faces already in the BMesh */ +static void bm_log_assign_ids(BMesh *bm, BMLog *log) +{ + BMIter iter; + BMVert *v; + BMFace *f; + + /* Generate vertex IDs */ + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + unsigned int id = range_tree_uint_take_any(log->unused_ids); + bm_log_vert_id_set(log, v, id); + } + + /* Generate face IDs */ + BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { + unsigned int id = range_tree_uint_take_any(log->unused_ids); + bm_log_face_id_set(log, f, id); + } +} + +/* Allocate an empty log entry */ +static BMLogEntry *bm_log_entry_create(void) +{ + BMLogEntry *entry = MEM_callocN(sizeof(BMLogEntry), AT); + + entry->deleted_verts = BLI_ghash_ptr_new(AT); + entry->deleted_faces = BLI_ghash_ptr_new(AT); + entry->added_verts = BLI_ghash_ptr_new(AT); + entry->added_faces = BLI_ghash_ptr_new(AT); + entry->modified_verts = BLI_ghash_ptr_new(AT); + + entry->pool_verts = BLI_mempool_create(sizeof(BMLogVert), 1, 64, 0); + entry->pool_faces = BLI_mempool_create(sizeof(BMLogFace), 1, 64, 0); + + return entry; +} + +/* Free the data in a log entry + * + * Note: does not free the log entry itself */ +static void bm_log_entry_free(BMLogEntry *entry) +{ + BLI_ghash_free(entry->deleted_verts, NULL, NULL); + BLI_ghash_free(entry->deleted_faces, NULL, NULL); + BLI_ghash_free(entry->added_verts, NULL, NULL); + BLI_ghash_free(entry->added_faces, NULL, NULL); + BLI_ghash_free(entry->modified_verts, NULL, NULL); + + BLI_mempool_destroy(entry->pool_verts); + BLI_mempool_destroy(entry->pool_faces); +} + +static void bm_log_id_ghash_retake(RangeTreeUInt *unused_ids, GHash *id_ghash) +{ + GHashIterator gh_iter; + + GHASH_ITER (gh_iter, id_ghash) { + void *key = BLI_ghashIterator_getKey(&gh_iter); + unsigned int id = GET_INT_FROM_POINTER(key); + + if (range_tree_uint_has(unused_ids, id)) { + range_tree_uint_take(unused_ids, id); + } + } +} + +static int uint_compare(const void *a_v, const void *b_v) +{ + const unsigned int *a = a_v; + const unsigned int *b = b_v; + return (*a) < (*b); +} + +/* Remap IDs to contiguous indices + * + * E.g. if the vertex IDs are (4, 1, 10, 3), the mapping will be: + * 4 -> 2 + * 1 -> 0 + * 10 -> 3 + * 3 -> 1 + */ +static GHash *bm_log_compress_ids_to_indices(unsigned int *ids, int totid) +{ + GHash *map = BLI_ghash_int_new(AT); + int i; + + qsort(ids, totid, sizeof(*ids), uint_compare); + + for (i = 0; i < totid; i++) { + void *key = SET_INT_IN_POINTER(ids[i]); + void *val = SET_INT_IN_POINTER(i); + BLI_ghash_insert(map, key, val); + } + + return map; +} + +/* Release all ID keys in id_ghash */ +static void bm_log_id_ghash_release(BMLog *log, GHash *id_ghash) +{ + GHashIterator gh_iter; + + GHASH_ITER (gh_iter, id_ghash) { + void *key = BLI_ghashIterator_getKey(&gh_iter); + unsigned int id = GET_INT_FROM_POINTER(key); + range_tree_uint_release(log->unused_ids, id); + } +} + +/***************************** Public API *****************************/ + +/* Allocate, initialize, and assign a new BMLog */ +BMLog *BM_log_create(BMesh *bm) +{ + BMLog *log = MEM_callocN(sizeof(*log), AT); + + log->unused_ids = range_tree_uint_alloc(0, (unsigned)-1); + log->id_to_elem = BLI_ghash_ptr_new(AT); + log->elem_to_id = BLI_ghash_ptr_new(AT); + + /* Assign IDs to all existing vertices and faces */ + bm_log_assign_ids(bm, log); + + return log; +} + +/* Allocate and initialize a new BMLog using existing BMLogEntries + * + * The 'entry' should be the last entry in the BMLog. Its prev pointer + * will be followed back to find the first entry. + * + * The unused IDs field of the log will be initialized by taking all + * keys from all GHashes in the log entry. + */ +BMLog *BM_log_from_existing_entries_create(BMesh *bm, BMLogEntry *entry) +{ + BMLog *log = BM_log_create(bm); + + if (entry->prev) + log->current_entry = entry; + else + log->current_entry = NULL; + + /* Let BMLog manage the entry list again */ + log->entries.first = log->entries.last = entry; + if (entry) { + while (entry->prev) { + entry = entry->prev; + log->entries.first = entry; + } + entry = log->entries.last; + while (entry->next) { + entry = entry->next; + log->entries.last = entry; + } + } + + for (entry = log->entries.first; entry; entry = entry->next) { + entry->log = log; + + /* Take all used IDs */ + bm_log_id_ghash_retake(log->unused_ids, entry->deleted_verts); + bm_log_id_ghash_retake(log->unused_ids, entry->deleted_faces); + bm_log_id_ghash_retake(log->unused_ids, entry->added_verts); + bm_log_id_ghash_retake(log->unused_ids, entry->added_faces); + bm_log_id_ghash_retake(log->unused_ids, entry->modified_verts); + } + + return log; +} + +/* Free all the data in a BMLog including the log itself */ +void BM_log_free(BMLog *log) +{ + BMLogEntry *entry; + + if (log->unused_ids) + range_tree_uint_free(log->unused_ids); + + if (log->id_to_elem) + BLI_ghash_free(log->id_to_elem, NULL, NULL); + + if (log->elem_to_id) + BLI_ghash_free(log->elem_to_id, NULL, NULL); + + /* Clear the BMLog references within each entry, but do not free + * the entries themselves */ + for (entry = log->entries.first; entry; entry = entry->next) + entry->log = NULL; + + MEM_freeN(log); +} + +/* Get the number of log entries */ +int BM_log_length(const BMLog *log) +{ + return BLI_countlist(&log->entries); +} + +/* Apply a consistent ordering to BMesh vertices */ +void BM_log_mesh_elems_reorder(BMesh *bm, BMLog *log) +{ + void *varr; + void *farr; + + GHash *id_to_idx; + + BMIter bm_iter; + BMVert *v; + BMFace *f; + + int i; + + /* Put all vertex IDs into an array */ + i = 0; + varr = MEM_mallocN(sizeof(int) * bm->totvert, AT); + BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) { + ((unsigned int*)varr)[i++] = bm_log_vert_id_get(log, v); + } + + /* Put all face IDs into an array */ + i = 0; + farr = MEM_mallocN(sizeof(int) * bm->totface, AT); + BM_ITER_MESH (f, &bm_iter, bm, BM_FACES_OF_MESH) { + ((unsigned int*)farr)[i++] = bm_log_face_id_get(log, f); + } + + /* Create BMVert index remap array */ + id_to_idx = bm_log_compress_ids_to_indices(varr, bm->totvert); + i = 0; + BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) { + const unsigned id = bm_log_vert_id_get(log, v); + const void *key = SET_INT_IN_POINTER(id); + const void *val = BLI_ghash_lookup(id_to_idx, key); + ((int*)varr)[i++] = GET_INT_FROM_POINTER(val); + } + BLI_ghash_free(id_to_idx, NULL, NULL); + + /* Create BMFace index remap array */ + id_to_idx = bm_log_compress_ids_to_indices(farr, bm->totface); + i = 0; + BM_ITER_MESH (f, &bm_iter, bm, BM_FACES_OF_MESH) { + const unsigned id = bm_log_face_id_get(log, f); + const void *key = SET_INT_IN_POINTER(id); + const void *val = BLI_ghash_lookup(id_to_idx, key); + ((int*)farr)[i++] = GET_INT_FROM_POINTER(val); + } + BLI_ghash_free(id_to_idx, NULL, NULL); + + BM_mesh_remap(bm, varr, NULL, farr); + + MEM_freeN(varr); + MEM_freeN(farr); +} + +/* Start a new log entry and update the log entry list + * + * If the log entry list is empty, or if the current log entry is the + * last entry, the new entry is simply appended to the end. + * + * Otherwise, the new entry is added after the current entry and all + * following entries are deleted. + * + * In either case, the new entry is set as the current log entry. + */ +BMLogEntry *BM_log_entry_add(BMLog *log) +{ + BMLogEntry *entry, *next; + + /* Delete any entries after the current one */ + entry = log->current_entry; + if (entry) { + for (entry = entry->next; entry; entry = next) { + next = entry->next; + bm_log_entry_free(entry); + BLI_freelinkN(&log->entries, entry); + } + } + + /* Create and append the new entry */ + entry = bm_log_entry_create(); + BLI_addtail(&log->entries, entry); + entry->log = log; + log->current_entry = entry; + + return entry; +} + +/* Remove an entry from the log + * + * Uses entry->log as the log. If the log is NULL, the entry will be + * free'd but not removed from any list, nor shall its IDs be + * released. + * + * This operation is only valid on the first and last entries in the + * log. Deleting from the middle will assert. + */ +void BM_log_entry_drop(BMLogEntry *entry) +{ + BMLog *log = entry->log; + + if (!log) { + /* Unlink */ + BLI_assert(!(entry->prev && entry->next)); + if (entry->prev) + entry->prev->next = NULL; + else if (entry->next) + entry->next->prev = NULL; + + bm_log_entry_free(entry); + MEM_freeN(entry); + return; + } + + if (!entry->prev) { + /* Release IDs of elements that are deleted by this + * entry. Since the entry is at the beginning of the undo + * stack, and it's being deleted, those elements can never be + * restored. Their IDs can go back into the pool. */ + bm_log_id_ghash_release(log, entry->deleted_faces); + bm_log_id_ghash_release(log, entry->deleted_verts); + } + else if (!entry->next) { + /* Release IDs of elements that are added by this entry. Since + * the entry is at the end of the undo stack, and it's being + * deleted, those elements can never be restored. Their IDs + * can go back into the pool. */ + bm_log_id_ghash_release(log, entry->added_faces); + bm_log_id_ghash_release(log, entry->added_verts); + } + else { + BLI_assert(!"Cannot drop BMLogEntry from middle"); + } + + if (log->current_entry == entry) + log->current_entry = entry->prev; + + bm_log_entry_free(entry); + BLI_freelinkN(&log->entries, entry); +} + +/* Undo one BMLogEntry + * + * Has no effect if there's nothing left to undo */ +void BM_log_undo(BMesh *bm, BMLog *log) +{ + BMLogEntry *entry = log->current_entry; + + if (entry) { + log->current_entry = entry->prev; + + /* Delete added faces and verts */ + bm_log_faces_unmake(bm, log, entry->added_faces); + bm_log_verts_unmake(bm, log, entry->added_verts); + + /* Restore deleted verts and faces */ + bm_log_verts_restore(bm, log, entry->deleted_verts); + bm_log_faces_restore(bm, log, entry->deleted_faces); + + /* Restore vertex coordinates, mask, and hflag */ + bm_log_vert_values_swap(bm, log, entry->modified_verts); + } +} + +/* Redo one BMLogEntry + * + * Has no effect if there's nothing left to redo */ +void BM_log_redo(BMesh *bm, BMLog *log) +{ + BMLogEntry *entry = log->current_entry; + + if (!entry) { + /* Currently at the beginning of the undo stack, move to first entry */ + entry = log->entries.first; + } + else if (entry && entry->next) { + /* Move to next undo entry */ + entry = entry->next; + } + else { + /* Currently at the end of the undo stack, nothing left to redo */ + return; + } + + log->current_entry = entry; + + if (entry) { + /* Re-delete previously deleted faces and verts */ + bm_log_faces_unmake(bm, log, entry->deleted_faces); + bm_log_verts_unmake(bm, log, entry->deleted_verts); + + /* Restore previously added verts and faces */ + bm_log_verts_restore(bm, log, entry->added_verts); + bm_log_faces_restore(bm, log, entry->added_faces); + + /* Restore vertex coordinates, mask, and hflag */ + bm_log_vert_values_swap(bm, log, entry->modified_verts); + } +} + +/* Log a vertex before it is modified + * + * Before modifying vertex coordinates, masks, or hflags, call this + * function to log it's current values. This is better than logging + * after the coordinates have been modified, because only those + * vertices that are modified need to have their original values + * stored. + * + * Handles two separate cases: + * + * If the vertex was added in the current log entry, update the + * vertex in the map of added vertices. + * + * If the vertex already existed prior to the current log entry, a + * seperate key/value map of modified vertices is used (using the + * vertex's ID as the key). The values stored in that case are + * the vertex's original state so that an undo can restore the + * previous state. + * + * On undo, the current vertex state will be swapped with the stored + * state so that a subsequent redo operation will restore the newer + * vertex state. + */ +void BM_log_vert_before_modified(BMesh *bm, BMLog *log, BMVert *v) +{ + BMLogEntry *entry = log->current_entry; + BMLogVert *lv; + unsigned int v_id = bm_log_vert_id_get(log, v); + void *key = SET_INT_IN_POINTER(v_id); + + /* Find or create the BMLogVert entry */ + if ((lv = BLI_ghash_lookup(entry->added_verts, key))) { + bm_log_vert_bmvert_copy(bm, lv, v); + } + else if (!BLI_ghash_haskey(entry->modified_verts, key)) { + lv = bm_log_vert_alloc(bm, log, v); + BLI_ghash_insert(entry->modified_verts, key, lv); + } +} + +/* Log a new vertex as added to the BMesh + * + * The new vertex gets a unique ID assigned. It is then added to a map + * of added vertices, with the key being its ID and the value + * containing everything needed to reconstruct that vertex. + */ +void BM_log_vert_added(BMesh *bm, BMLog *log, BMVert *v) +{ + BMLogVert *lv; + unsigned int v_id = range_tree_uint_take_any(log->unused_ids); + void *key = SET_INT_IN_POINTER(v_id); + + bm_log_vert_id_set(log, v, v_id); + lv = bm_log_vert_alloc(bm, log, v); + BLI_ghash_insert(log->current_entry->added_verts, key, lv); +} + +/* Log a new face as added to the BMesh + * + * The new face gets a unique ID assigned. It is then added to a map + * of added faces, with the key being its ID and the value containing + * everything needed to reconstruct that face. + */ +void BM_log_face_added(BMLog *log, BMFace *f) +{ + BMLogFace *lf; + unsigned int f_id = range_tree_uint_take_any(log->unused_ids); + void *key = SET_INT_IN_POINTER(f_id); + + /* Only triangles are supported for now */ + BLI_assert(f->len == 3); + + bm_log_face_id_set(log, f, f_id); + lf = bm_log_face_alloc(log, f); + BLI_ghash_insert(log->current_entry->added_faces, key, lf); +} + +/* Log a vertex as removed from the BMesh + * + * A couple things can happen here: + * + * If the vertex was added as part of the current log entry, then it's + * deleted and forgotten about entirely. Its unique ID is returned to + * the unused pool. + * + * If the vertex was already part of the BMesh before the current log + * entry, it is added to a map of deleted vertices, with the key being + * its ID and the value containing everything needed to reconstruct + * that vertex. + * + * If there's a move record for the vertex, that's used as the + * vertices original location, then the move record is deleted. + */ +void BM_log_vert_removed(BMesh *bm, BMLog *log, BMVert *v) +{ + BMLogEntry *entry = log->current_entry; + unsigned int v_id = bm_log_vert_id_get(log, v); + void *key = SET_INT_IN_POINTER(v_id); + + if (BLI_ghash_lookup(entry->added_verts, key)) { + BLI_ghash_remove(entry->added_verts, key, NULL, NULL); + range_tree_uint_release(log->unused_ids, v_id); + } + else { + BMLogVert *lv, *lv_mod; + + lv = bm_log_vert_alloc(bm, log, v); + BLI_ghash_insert(entry->deleted_verts, key, lv); + + /* If the vertex was modified before deletion, ensure that the + * original vertex values are stored */ + if ((lv_mod = BLI_ghash_lookup(entry->modified_verts, key))) { + (*lv) = (*lv_mod); + BLI_ghash_remove(entry->modified_verts, key, NULL, NULL); + } + } +} + +/* Log a face as removed from the BMesh + * + * A couple things can happen here: + * + * If the face was added as part of the current log entry, then it's + * deleted and forgotten about entirely. Its unique ID is returned to + * the unused pool. + * + * If the face was already part of the BMesh before the current log + * entry, it is added to a map of deleted faces, with the key being + * its ID and the value containing everything needed to reconstruct + * that face. + */ +void BM_log_face_removed(BMLog *log, BMFace *f) +{ + BMLogEntry *entry = log->current_entry; + unsigned int f_id = bm_log_face_id_get(log, f); + void *key = SET_INT_IN_POINTER(f_id); + + if (BLI_ghash_lookup(entry->added_faces, key)) { + BLI_ghash_remove(entry->added_faces, key, NULL, NULL); + range_tree_uint_release(log->unused_ids, f_id); + } + else { + BMLogFace *lf; + + lf = bm_log_face_alloc(log, f); + BLI_ghash_insert(entry->deleted_faces, key, lf); + } +} + +/* Log all vertices/faces in the BMesh as added */ +void BM_log_all_added(BMesh *bm, BMLog *log) +{ + BMIter bm_iter; + BMVert *v; + BMFace *f; + + /* Log all vertices as newly created */ + BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) { + BM_log_vert_added(bm, log, v); + } + + /* Log all faces as newly created */ + BM_ITER_MESH (f, &bm_iter, bm, BM_FACES_OF_MESH) { + BM_log_face_added(log, f); + } +} + +/* Log all vertices/faces in the BMesh as removed */ +void BM_log_before_all_removed(BMesh *bm, BMLog *log) +{ + BMIter bm_iter; + BMVert *v; + BMFace *f; + + /* Log deletion of all faces */ + BM_ITER_MESH (f, &bm_iter, bm, BM_FACES_OF_MESH) { + BM_log_face_removed(log, f); + } + + /* Log deletion of all vertices */ + BM_ITER_MESH (v, &bm_iter, bm, BM_VERTS_OF_MESH) { + BM_log_vert_removed(bm, log, v); + } +} + +/* Get the logged coordinates of a vertex + * + * Does not modify the log or the vertex */ +const float *BM_log_original_vert_co(BMLog *log, BMVert *v) +{ + BMLogEntry *entry = log->current_entry; + const BMLogVert *lv; + unsigned v_id = bm_log_vert_id_get(log, v); + void *key = SET_INT_IN_POINTER(v_id); + + BLI_assert(entry); + + BLI_assert(BLI_ghash_haskey(entry->modified_verts, key)); + + lv = BLI_ghash_lookup(entry->modified_verts, key); + return lv->co; +} + +/* Get the logged mask of a vertex + * + * Does not modify the log or the vertex */ +float BM_log_original_mask(BMLog *log, BMVert *v) +{ + BMLogEntry *entry = log->current_entry; + const BMLogVert *lv; + unsigned v_id = bm_log_vert_id_get(log, v); + void *key = SET_INT_IN_POINTER(v_id); + + BLI_assert(entry); + + BLI_assert(BLI_ghash_haskey(entry->modified_verts, key)); + + lv = BLI_ghash_lookup(entry->modified_verts, key); + return lv->mask; +} + +/************************ Debugging and Testing ***********************/ + +/* For internal use only (unit testing) */ +BMLogEntry *BM_log_current_entry(BMLog *log) +{ + return log->current_entry; +} + +/* For internal use only (unit testing) */ +RangeTreeUInt *BM_log_unused_ids(BMLog *log) +{ + return log->unused_ids; +} + +#if 0 +/* Print the list of entries, marking the current one + * + * Keep around for debugging */ +void bm_log_print(const BMLog *log, const char *description) +{ + const BMLogEntry *entry; + const char *current = " <-- current"; + int i; + + printf("%s:\n", description); + printf(" % 2d: [ initial ]%s\n", 0, + (!log->current_entry) ? current : ""); + for (entry = log->entries.first, i = 1; entry; entry = entry->next, i++) { + printf(" % 2d: [%p]%s\n", i, entry, + (entry == log->current_entry) ? current : ""); + } +} +#endif diff --git a/source/blender/bmesh/intern/bmesh_log.h b/source/blender/bmesh/intern/bmesh_log.h new file mode 100644 index 00000000000..958ff340b43 --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_log.h @@ -0,0 +1,102 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BMESH_LOG_H__ +#define __BMESH_LOG_H__ + +/* The BMLog is an interface for storing undo/redo steps as a BMesh is + * modified. It only stores changes to the BMesh, not full copies. + * + * Currently it supports the following types of changes: + * + * - Adding and removing vertices + * - Adding and removing faces + * - Moving vertices + * - Setting vertex paint-mask values + * - Setting vertex hflags + */ + +struct BMFace; +struct BMVert; +struct BMesh; +struct RangeTreeUInt; + +typedef struct BMLog BMLog; +typedef struct BMLogEntry BMLogEntry; + +/* Allocate and initialize a new BMLog */ +BMLog *BM_log_create(BMesh *bm); + +/* Allocate and initialize a new BMLog using existing BMLogEntries */ +BMLog *BM_log_from_existing_entries_create(BMesh *bm, BMLogEntry *entry); + +/* Free all the data in a BMLog including the log itself */ +void BM_log_free(BMLog *log); + +/* Get the number of log entries */ +int BM_log_length(const BMLog *log); + +/* Apply a consistent ordering to BMesh vertices and faces */ +void BM_log_mesh_elems_reorder(BMesh *bm, BMLog *log); + +/* Start a new log entry and update the log entry list */ +BMLogEntry *BM_log_entry_add(BMLog *log); + +/* Remove an entry from the log */ +void BM_log_entry_drop(BMLogEntry *entry); + +/* Undo one BMLogEntry */ +void BM_log_undo(BMesh *bm, BMLog *log); + +/* Redo one BMLogEntry */ +void BM_log_redo(BMesh *bm, BMLog *log); + +/* Log a vertex before it is modified */ +void BM_log_vert_before_modified(BMesh *bm, BMLog *log, struct BMVert *v); + +/* Log a new vertex as added to the BMesh */ +void BM_log_vert_added(BMesh *bm, BMLog *log, struct BMVert *v); + +/* Log a new face as added to the BMesh */ +void BM_log_face_added(BMLog *log, struct BMFace *f); + +/* Log a vertex as removed from the BMesh */ +void BM_log_vert_removed(BMesh *bm, BMLog *log, struct BMVert *v); + +/* Log a face as removed from the BMesh */ +void BM_log_face_removed(BMLog *log, struct BMFace *f); + +/* Log all vertices/faces in the BMesh as added */ +void BM_log_all_added(BMesh *bm, BMLog *log); + +/* Log all vertices/faces in the BMesh as removed */ +void BM_log_before_all_removed(BMesh *bm, BMLog *log); + +/* Get the logged coordinates of a vertex */ +const float *BM_log_original_vert_co(BMLog *log, BMVert *v); + +/* Get the logged mask of a vertex */ +float BM_log_original_mask(BMLog *log, BMVert *v); + +/* For internal use only (unit testing) */ +BMLogEntry *BM_log_current_entry(BMLog *log); +struct RangeTreeUInt *BM_log_unused_ids(BMLog *log); + +#endif |