Unique Mesh IDs #89540

New Issue

Joseph Eagar · 2021-06-30T00:36:02+02:00

Joseph Eagar commented

2021-06-30 00:36:02 +02:00

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 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.

Joseph Eagar commented

2021-06-30 00:36:02 +02:00

Added subscriber: @JosephEagar

Paul Larson commented

2021-06-30 02:55:19 +02:00

Added subscriber: @GeorgiaPacific

Joseph Eagar changed title from ~~Unique IDs For BMesh~~ to Unique IDs For BMesh (and Mesh?)

2021-09-15 11:03:10 +02:00

Joseph Eagar changed title from ~~Unique IDs For BMesh (and Mesh?)~~ to Unique Mesh IDs

2021-12-08 00:40:27 +01:00

Philipp Oeser commented

2022-02-16 12:04:29 +01:00

Added subscriber: @lichtwerk

Philipp Oeser commented

2022-02-16 12:04:29 +01:00

Changed status from 'Needs Triage' to: 'Needs Developer To Reproduce'

Philipp Oeser commented

2022-02-16 12:04:29 +01:00

Not sure what the status should be here if it is "Under Discussion"?
Will set to Needs Info from Developers for now, feel free to set to anything but Needs Triage (since the triaging team cannot do much here afaict)

Not sure what the status should be here if it is "Under Discussion"? Will set to `Needs Info from Developers` for now, feel free to set to anything but `Needs Triage` (since the triaging team cannot do much here afaict)

Philipp Oeser removed the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Unique Mesh IDs #89540

Introduction

Why Its Needed - DynTopo

Basic Design

Enabling IDs

ignore_mesh_id_layers - Do not load id layers into Mesh.

How IDs Are Stored

Reuse or Not Reuse IDs?

You can't use IDs for simple history tracking. For example without ID reuse you can find all elements

IDs are no longer guaranteed to always belong to elements of one type (or nothing at all) after being

Update

ToDo

`ignore_mesh_id_layers` - Do not load id layers into Mesh.