Change Details

== Introduction == I recently added support for unique IDs to BMesh in temp_multires_bmesh. I did this to fix a class of bugs related to DynTopo undo. == Why Its Needed - DynTopo == DynTopo's undo system (`BMLog`) assigns unique IDs to verts and faces. It does this by maintaining a hash of element->ids and ids->elements. This has proven prone to bugs and memory corruption. = Basic Design = IDs are stored in CustomData layers (`CD_MESH_ID`) marked with `CD_FLAG_TEMPORARY` and a new flag I added--`CD_FLAG_ELEM_NOCOPY`--to tell BMesh not to copy data (BMesh ignores `CD_FLAG_NOELEM` and changing that struck me as too big of a change). These ID layers are optional and can be restricted to certain element types. When creating or destroying elements BMesh internally checks if a given layer is enabled and acts accordingly. Elements share a common ID space and ids are reused. There is an optional id to element map; if enabled, a simple lookup table from IDs to elements will be maintained. A simple lookup table is possible because IDs are reused; if they were not we'd have to use a GHash. == Enabling IDs == `BMeshCreateParams` has the follow new parameters: # `create_unique_ids` - create ID layers # `id_elem_mask` - Bitmask controlling which element types to create id layers for # `id_map` - Maintain an element to ID map. # `temporary_ids` - Mark id layers as temporary `BMeshToMeshParams` has these new parameters: # `ignore_mesh_id_layers` - Do not load id layers into Mesh. `eBMCreateFlag` also has a new BM_CREATE_SKIP_ID flag for skipping ID assignment. == How IDs Are Stored == IDs are stored in a new `CD_MESH_ID` customdata layer (which is just a copy of `CD_PROP_INT32` with modified copy/interpolation behavior). In addition BMesh has the following new substructure: ``` struct { int flag; //bitmask of [BM_VERT, BM_EDGE, BM_LOOP, BM_FACE, BM_HAS_IDS,BM_HAS_ID_MAP] struct RangeTreeUInt *idtree; //range tree to reuse ids uint maxid; //maximum allocated id struct BMElem **map; //element to id map, if enabled in BM_HAS_ID_MAP int map_size; int cd_id_off[15]; //offsets to CD_MESH_ID customdata layers, maintained by BM_AddDataLayer } idmap; ``` The internal API for assigning IDs is: ``` /* assign an id to elem. does not check if elem has an existing id. */ void bm_assign_id(BMesh *bm, BMElem *elem, uint id); /* allocate a new ID for elem. */ void bm_alloc_id(BMesh *bm, BMElem *elem); /* free the id associated with elem */ void bm_free_id(BMesh *bm, BMElem *elem); ``` = Reuse or Not Reuse IDs? = The benefit of reusing IDs is that it lets us use a simple lookup table for the id-to-element map. It does come at a cost however, as the following use cases are no longer possible: # You can't use IDs for simple history tracking. For example without ID reuse you can find all elements created between id position T and T+N by simply iterating over the range and checking the element-to-id map. # IDs are no longer guaranteed to always belong to elements of one type (or nothing at all) after being assigned. == Update == CD_MESH_ID attribute layers are no longer flagged as temporary. So once they're created (e.g. by the sculpt code) they stick around inside the mesh. Note that BMesh validates the IDs when loading from Mesh (if the idmap is enabled when creating the bmesh). The number one source of bugs in the sculpt undo code (as well as a major performance hit) was having to cache IDs in the undo stack on exiting sculpt mode. This totally breaks if a memfile step is pushed while sculpt mode is active (e.g. adding a modifier). == ToDo == * Write a Mesh API for allocating IDs. * Test loop IDs. The sculpt code doesn't use them.

== Introduction == The number one source of bugs in the sculpt undo code (as well as a major performance hit) was having to cache IDs in the undo stack on exiting sculpt mode. This totally breaks if a memfile step is pushed while sculpt mode is active (e.g. adding a modifier). == Why Its Needed - DynTopo == DynTopo's undo system (`BMLog`) assigns unique IDs to verts and faces. It does this by maintaining a hash of element->ids and ids->elements. This has proven prone to bugs and memory corruption. = Basic Design = IDs are stored in CustomData layers (`CD_MESH_ID`) marked with `CD_FLAG_TEMPORARY` and a new flag I added--`CD_FLAG_ELEM_NOCOPY`--to tell BMesh not to copy data (BMesh ignores `CD_FLAG_NOELEM` and changing that struck me as too big of a change). These ID layers are optional and can be restricted to certain element types. When creating or destroying elements BMesh internally checks if a given layer is enabled and acts accordingly. Elements share a common ID space and ids are reused. There is an optional id to element map; if enabled, a simple lookup table from IDs to elements will be maintained. A simple lookup table is possible because IDs are reused; if they were not we'd have to use a GHash. == Enabling IDs == `BMeshCreateParams` has the follow new parameters: # `create_unique_ids` - create ID layers # `id_elem_mask` - Bitmask controlling which element types to create id layers for # `id_map` - Maintain an element to ID map. # `temporary_ids` - Mark id layers as temporary `BMeshToMeshParams` has these new parameters: # `ignore_mesh_id_layers` - Do not load id layers into Mesh. `eBMCreateFlag` also has a new BM_CREATE_SKIP_ID flag for skipping ID assignment. == How IDs Are Stored == IDs are stored in a new `CD_MESH_ID` customdata layer (which is just a copy of `CD_PROP_INT32` with modified copy/interpolation behavior). In addition BMesh has the following new substructure: ``` struct { int flag; //bitmask of [BM_VERT, BM_EDGE, BM_LOOP, BM_FACE, BM_HAS_IDS,BM_HAS_ID_MAP] struct RangeTreeUInt *idtree; //range tree to reuse ids uint maxid; //maximum allocated id struct BMElem **map; //element to id map, if enabled in BM_HAS_ID_MAP int map_size; int cd_id_off[15]; //offsets to CD_MESH_ID customdata layers, maintained by BM_AddDataLayer } idmap; ``` The internal API for assigning IDs is: ``` /* assign an id to elem. does not check if elem has an existing id. */ void bm_assign_id(BMesh *bm, BMElem *elem, uint id); /* allocate a new ID for elem. */ void bm_alloc_id(BMesh *bm, BMElem *elem); /* free the id associated with elem */ void bm_free_id(BMesh *bm, BMElem *elem); ``` = Reuse or Not Reuse IDs? = The benefit of reusing IDs is that it lets us use a simple lookup table for the id-to-element map. It does come at a cost however, as the following use cases are no longer possible: # You can't use IDs for simple history tracking. For example without ID reuse you can find all elements created between id position T and T+N by simply iterating over the range and checking the element-to-id map. # IDs are no longer guaranteed to always belong to elements of one type (or nothing at all) after being assigned. == Update == CD_MESH_ID attribute layers are no longer flagged as temporary. So once they're created (e.g. by the sculpt code) they stick around inside the mesh. Note that BMesh validates the IDs when loading from Mesh (if the idmap is enabled when creating the bmesh). == ToDo == * Write a Mesh API for allocating IDs. * Test loop IDs. The sculpt code doesn't use them.

== Introduction == I recently added support for unique IDs to BMeshThe number one source of bugs in temp_multires_bmesh. I did this to fixthe sculpt undo a class of bugs related to DynTopo undocode (as well as a major performance hit) was having to cache IDs in the undo stack on exiting sculpt mode. This totally breaks if a memfile step is pushed while sculpt mode is active (e.g. adding a modifier). == Why Its Needed - DynTopo == DynTopo's undo system (`BMLog`) assigns unique IDs to verts and faces. It does this by maintaining a hash of element->ids and ids->elements. This has proven prone to bugs and memory corruption. = Basic Design = IDs are stored in CustomData layers (`CD_MESH_ID`) marked with `CD_FLAG_TEMPORARY` and a new flag I added--`CD_FLAG_ELEM_NOCOPY`--to tell BMesh not to copy data (BMesh ignores `CD_FLAG_NOELEM` and changing that struck me as too big of a change). These ID layers are optional and can be restricted to certain element types. When creating or destroying elements BMesh internally checks if a given layer is enabled and acts accordingly. Elements share a common ID space and ids are reused. There is an optional id to element map; if enabled, a simple lookup table from IDs to elements will be maintained. A simple lookup table is possible because IDs are reused; if they were not we'd have to use a GHash. == Enabling IDs == `BMeshCreateParams` has the follow new parameters: # `create_unique_ids` - create ID layers # `id_elem_mask` - Bitmask controlling which element types to create id layers for # `id_map` - Maintain an element to ID map. # `temporary_ids` - Mark id layers as temporary `BMeshToMeshParams` has these new parameters: # `ignore_mesh_id_layers` - Do not load id layers into Mesh. `eBMCreateFlag` also has a new BM_CREATE_SKIP_ID flag for skipping ID assignment. == How IDs Are Stored == IDs are stored in a new `CD_MESH_ID` customdata layer (which is just a copy of `CD_PROP_INT32` with modified copy/interpolation behavior). In addition BMesh has the following new substructure: ``` struct { int flag; //bitmask of [BM_VERT, BM_EDGE, BM_LOOP, BM_FACE, BM_HAS_IDS,BM_HAS_ID_MAP] struct RangeTreeUInt *idtree; //range tree to reuse ids uint maxid; //maximum allocated id struct BMElem **map; //element to id map, if enabled in BM_HAS_ID_MAP int map_size; int cd_id_off[15]; //offsets to CD_MESH_ID customdata layers, maintained by BM_AddDataLayer } idmap; ``` The internal API for assigning IDs is: ``` /* assign an id to elem. does not check if elem has an existing id. */ void bm_assign_id(BMesh *bm, BMElem *elem, uint id); /* allocate a new ID for elem. */ void bm_alloc_id(BMesh *bm, BMElem *elem); /* free the id associated with elem */ void bm_free_id(BMesh *bm, BMElem *elem); ``` = Reuse or Not Reuse IDs? = The benefit of reusing IDs is that it lets us use a simple lookup table for the id-to-element map. It does come at a cost however, as the following use cases are no longer possible: # You can't use IDs for simple history tracking. For example without ID reuse you can find all elements created between id position T and T+N by simply iterating over the range and checking the element-to-id map. # IDs are no longer guaranteed to always belong to elements of one type (or nothing at all) after being assigned. == Update == CD_MESH_ID attribute layers are no longer flagged as temporary. So once they're created (e.g. by the sculpt code) they stick around inside the mesh. Note that BMesh validates the IDs when loading from Mesh (if the idmap is enabled when creating the bmesh). The number one source of bugs in the sculpt undo code (as well as a major performance hit) was having to cache IDs in the undo stack on exiting sculpt mode. This totally breaks if a memfile step is pushed while sculpt mode is active (e.g. adding a modifier). == ToDo == * Write a Mesh API for allocating IDs. * Test loop IDs. The sculpt code doesn't use them.