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 be restricted to certain element types. When creating or destroying elements BMesh internally checks if a given layer is enabled and acts accordingly. Since these layers are marked with CD_FLAG_TEMPORARY they are not loaded into or from a Mesh (unless you specifically request it, see next section). In the future we could choose to always create IDs and keep them around but that's not a decision I can make on my own. 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: # `use_unique_ids` - enable unique IDs # `use_id_elem_mask` - Bitmask controlling element types to keep track of IDs for (DynTopo uses `BM_VERT|BM_FACE`). # `use_id_map` - Maintain an element to ID map. `BMeshToMeshParams` has these new parameters: # `copy_mesh_id_layers` - 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.

== 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. Since these layers are marked with CD_FLAG_TEMPORARY they are not loaded into or from a Mesh (unless you specifically request it, see next section). In the future we could choose to always create IDs and keep them around but that's not a decision I can make on my own. 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: # `use_unique_ids` - enable unique IDs # `use_id_elem_mask` - Bitmask controlling element types to keep track of IDs for (DynTopo uses `BM_VERT|BM_FACE`). # `use_id_map` - Maintain an element to ID map. `BMeshToMeshParams` has these new parameters: # `copy_mesh_id_layers` - 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.

== 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. Since these layers are marked with CD_FLAG_TEMPORARY they are not loaded into or from a Mesh (unless you specifically request it, see next section). In the future we could choose to always create IDs and keep them around but that's not a decision I can make on my own. 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: # `use_unique_ids` - enable unique IDs # `use_id_elem_mask` - Bitmask controlling element types to keep track of IDs for (DynTopo uses `BM_VERT|BM_FACE`). # `use_id_map` - Maintain an element to ID map. `BMeshToMeshParams` has these new parameters: # `copy_mesh_id_layers` - 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.