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