Dev:Source/Modeling/BMesh/Design

Introduction

BMesh is a non-manifold boundary representation. It was designed to replace the current, limited EditMesh structure, solving many of the design limitations and maintainance issues of EditMesh. It is comparable to the Radial Edge Structure [1].

The BMesh Structure

Entities

At the most basic level, BMesh stores topology in four main element structures:

• Faces
• Loops (stores per-face-vertex data, uvs, vcols, etc)
• Edges
• Verts

Vertices

Vertices store a coordinate and link to an edge in the disk cycle of the vertex (covered below).

Edges

Edges represent a connection between two vertices, but also store a link to a loop in the radial cycle of the edge (covered below).

Loops

Loops define the boundary loop of a face. Each loop logically corresponds to an edge, though the loop is local to a single face so there will usually be more than one loop per edge (except at boundary edges of the surface).

Loops store several handy pointers:

• e - pointer to the loop's edge
• v - pointer to the vertex at the start of the edge (where "start" is defined by CCW order)
• f - pointer to the face associated with this loop.

Loops store per-face-vertex data (amongst other things outlined later in this document).

Faces

Faces link to a loop in the loop cycle, the circular linked list of loops defining the boundary of the face.

Persistent Flags

Each element (vertex/edge/loop/face) in a mesh has an associated persistent bitfield, these flags store information such as the visibility of the entity, or its selection state.

Connectivity Cycles

BMesh structure has the following features:

• Persistent adjacency information
• Locally modifiable topology
• Faces of arbitrary length (N-Gons)
• Trivially represents any non-manifold condition including wire edges.

The second through fourth features all depend upon the first, and as such the system which provides this facility is the foundation of the bmesh data structure. Persistent adjacency information is stored using a system of double linked circular lists which maintain the relationships among topological entities. These lists are conceptually the same as those found in other boundary representations such as half-edge, radial edge and partial entity and like these other representations each topological entity is itself a node in the cycles to which it belongs so the memory requirements for storing adjacency information remains minimal.

The connections between the elements are defined by loops around topological entities, referred to as cycles. The base of each cycle is the entity which the cycle is designed to answer adjacency queries for. For instance a cycle designed to answer the question, “what edges share this vertex” would have the vertex itself as the base and its edges as the nodes of the cycle. Note that it is not required to explicitly store all possible adjacency relationships and full connectivity information can be quickly derived from using two or more cycles in conjunction.

The three cycles stored explicitly within the bmesh structure are the Disk Cycle, the Radial Cycle and the Loop Cycle. Outlined below are the properties of each cycle and a list of functions for dealing with them. It is important to note that functions marked with an asterisk (*) are not part of the Mesh Tools API and only used by the modelling kernel. Furthermore when structure definitions are listed they have had certain members omitted for the sake of clarity.

The Disk Cycle: A circle of edges around a vertex

BASE: BM_EDGE_DISK_LINK_GET(BMEdge *, BMVert *)

The Disk Cycle

This cycle is the most complicated in terms of its structure. Each BMEdge contains two BMDiskLink structures for keeping track of that edge’s membership in the disk cycle of each of its vertices (v1_disk_link for vertex v1, and v2_disk_link2 for vertex v2). However for any given vertex it may be represented by the v1 pointer in some edges in its disk cycle and the v2 pointer for others. The bmesh_disk_ family of functions contains some nice utilities for navigating disk cycles and hides this detail from mesh tool authors. Note that unlike half edge, the disk cycle is completely independent from face data. One advantage of this is that wire edges are fully integrated into the topology database. Another is that the disk cycle has no problems dealing with non-manifold conditions involving faces.

Functions relating to this cycle:

• bmesh_disk_edge_append
• bmesh_disk_edge_remove
• bmesh_disk_edge_next

The Loop Cycle: A circle of face edges around a polygon.

BASE: BM_FACE_FIRST_LOOP(BMFace *)

To understand the loop cycle one must understand the way that polygons are stored in the bmesh modeler. Every face is represented by the following two structures:

typedef struct BMFace {
    BMHeader head;
    struct BMFlagLayer *oflags; /* an array of flags, mostly used by the operator stack */

    int len; /*includes all boundary loops*/

    BMLoop *l_first;

    float no[3];
    short mat_nr;
} BMFace;

typedef struct BMLoop {
    BMHeader head;
    /* notice no flags layer */

    struct BMVert *v;
    struct BMEdge *e; /* edge, using verts (v, next->v) */
    struct BMFace *f;
    /* --- snip --- */
} BMLoop;

The Bmesh face structure

The BMFace structure is part of a ListBase stored in the BMesh structure. It does not store the vertices or edges associated with it explicitly. Instead it simply stores a pointer to the first BMLoop in the face’s loop cycle. The following diagram shows the arrangement of BMLoops in a clockwise winding face.

As can be seen from the diagram, the BMLoop structure is similar to the half-edge, in that it is directed according to face winding and only stores references to one vertex. Since each loop is also associated with an BMEdge, a property of loops that must hold true is that loop->v and loop->next->v must be both contained within loop->e. Regardless of this the vertex pointers of loops are aligned to the face, not edges and the first vertex in a polygon will always be face->loopbase->v while the second one will be face->loopbase->next->v and so on.

Functions relating to this cycle:

• bmesh_cycle_* family of functions.

The Radial Cycle: A circle of faces around an edge

BASE: BMEdge->loop->radial structure

The Bmesh radial cycle

The radial cycle is similar to the radial cycle in the radial edge data structure. Unlike the radial edge however, the radial cycle in bmesh does not require a large amount of memory to represent non-manifold conditions since bmesh does not keep track of region or shell information.

Figure two illustrates the construction of the radial cycle. Although any number of faces, and therefore loops, may be associated with any given edge, each BMEdge stores a pointer to only one of it’s BMLoops. This BMLoop is considered to be the base for this BMEdge’s radial cycle, and by following the next and prev pointers in the radial member of each BMLoop structure we are able to visit every face associated with a particular edge.

Functions relating to this cycle:

• bmesh_radial_append*
• bmesh_radial_loop_remove*
• bmesh_radial_loop_next
• bmesh_radial_face_find

Order of Elements in Cycles

Note that the order of edges in the disk cycles and the order of faces in the radial cycle is undefined. This leads to slightly increased seek time for deriving some adjacency relations. However, the advantage is that no intrinsic properties of the mesh are dependent upon the cycle order and all non-manifold conditions are represented trivially.

All of the Cycles

This picture shows all of the cycles in one picture, summarizing the above sections.

Mesh Editing API

The mesh editing API can be informally broken up into three layers:

• The low-level API for traversing BMesh cycles and making primitive local edits
• The mid-level API builds on this, to provide iterators, walkers, and higher-level mesh editing functions
• The top-level API builds on these layers, and consists of operators and editing tools

Low-level API

Mesh Structure API

At the lowest level, BMesh provides an API for traversing the disk, loop, and radial cycles, and also a set of Euler operators for making local changes to the mesh.

Euler Operators

The functions listed below represent the ‘primitive’ or ‘atomic’ operators that mesh tools use to manipulate the topology of the structure.* The purpose of these functions is to provide a trusted set of operators to manipulate the mesh topology and which can also be combined together like building blocks to create more sophisticated tools.

In the BMesh system, each euler is named by an acronym which describes what it actually does. Furthermore each Euler has a logical inverse.

• BM_vert_create/kill: Make Vert and Kill Vert
• BM_edge_create/kill: Make Edge and Kill Edge
• BM_face_create/kill: Make Face and Kill Face
• bmesh_semv/jekv: Split Edge, Make Vert and Join Edge, Kill Vert
• bmesh_sfme/jfke: Split Face, Make Edge and Join Face, Kill Edge
• bmesh_loop_reverse: Reverse the loop of a BMFace. Its own inverse

The goals is that using a combination of only these Euler Operators, any non-manifold modelling operation can be achieved. Furthermore, each operator exploits the persistent adjacency information stored in the BMesh structure to make modifications to only local topology. This means that the running time of each operator is constrained only by the complexity of local detail and not overall mesh density. Finally every operator ensures that the data structure that it produces as output is fully valid and therefore frees the tool author from having to manipulate and validate the mesh directly.

Euler Function Reference

BMVert *bmesh_semv(BMesh *bm, BMEdge *e, BMEdge **r_e) Split Edge Make Vert SPLIT EDGE MAKE VERT: Takes a given edge and splits it into two, creating a new vert. The original edge, OE, is relinked to be between V1 and NV. OE is then moved from V2's disk cycle to NV's. The new edge, NE, is linked to be between NV and V2 and added to both vertices disk cycles. Finally the radial cycle of OE is traversed, splitting faceloop it encounters. Returns - Pointer to a new BMVert

BMEdge *bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv, const short check_edge_double) Join Edge Kill Vert JOIN EDGE KILL VERT: Takes a pointer to an edge (ke) and pointer to one of its vertices (kv) and collapses the edge on that vertex. First ke is removed from the disk cycle of both kv and tv. Then the edge oe is relinked to run between ov and tv and is added to the disk cycle of ov. Finally the radial cycle of oe is traversed and all of its face loops are updated. Note that in order for this euler to work, kv must have exactly only two edges coincident upon it (valance of 2). A more generalized edge collapse function can be built using a combination of bmesh_sfme, bmesh_jfke and bmesh_jekv. Returns - 1 for success, 0 for failure

BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **rl, BMEdge *example) Split Face Make Edge SPLIT FACE MAKE EDGE: Takes as input two vertices in a single face. An edge is created which divides the original face into two distinct regions. One of the regions is assigned to the original face and it is closed off. The second region has a new face assigned to it. Note that if the input vertices share an edge this will create a face with only two edges. Returns - Pointer to a new BMFace

BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e) Join Face Kill Edge JOIN FACE KILL EDGE: Takes two faces joined by a single 2-manifold edge and fuses them together. The edge shared by the faces must not be connected to any other edges which have Both faces in its radial cycle. An illustration of this appears in the figure on the right. In this diagram, situation A is the only one in which JFKE will return with a value indicating success. If the tool author wants to join two seperate faces which have multiple edges joining them as in situation B they should run JEKV on the excess edge(s) first. In the case of situation none of the edges joining the two faces can be safely removed because it would cause a face that loops back on itself. Also note that the order of arguments decides whether or not certain per-face attributes are present in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited from f1, not f2. Returns - 1 for success, 0 for failure

Example: Splitting a Face

Splitting a face using Eulers

In the figure above we are shown how euler operators can be combined together simply to create more sophisticated effects. We start with a 4 sided quadrilateral labelled F1. By running the Euler SEMV first on edges E1 then E2 we turn F1 into a polygon with six sides. Finally we run SFME to connect the two new vertices and split the face down the middle. Here is the source code for accomplishing this:

	BMVert *v1, *v2;
	BMFace *f2;

	v1 = bmesh_semv(e1);
	v2 = bmesh_semv(e2);
	f2 = bmesh_sfme(f1, v1, v2);

The remarkable thing about this is that with just three lines of code the tools writer can now accomplish what would have taken dozens if not a hundred or more lines to accomplish using the old EditMesh system. Furthermore the tool writer is not modifying the mesh directly and the complexity of maintaining a consistent data structure is cleanly handled by the Eulers internal code.

Important Note about Edges and Faces

Tool authors should be made aware that the Bmesh data structures can behave in unexpected ways with regards to edges and faces. For instance, a face with only two edges is perfectly valid. From this it logically follows that between any two vertices an arbitrary number of edges can exist.

While these unique properties can be exploited to create advanced modelling functions, tool authors should be very careful to clean up both faces with 2 edges and vertex pairs with multiple edges by the time their tool finishes execution. Although failure to do this won't be harmful at all to the stability of the modelling system, it is not considered a good thing to leave the structure in a state that is not intuitively understandable by the average end user.

<NOTE: I am considering removing 2 edged faces from the modelling system alltogather>

Mid-Level Mesh Editing API

BMesh Operators

BMesh Operators ("bmops") are an integral part of BMesh. They build on the foundations of the low-level API, usually performing certain fundamental kinds of mesh edits on areas of the mesh specified by input parameters (though a few operators just return outputs without affecting the mesh), thus providing building blocks for the editing tools.

Examples of mesh operators include (see bmesh_opdefines.c for a full listing):

• mirror
• bevel
• similarfaces

Most editing tools will compose one or more operators to get a job done. Unlike normal blender operators, BMesh operators can be nested (i.e. call other operators), so an operator will also often compose one or more other operators to get a job done.

Operator Restrictions

Operators are used for editing the mesh, but should never touch header flags (visibility, selection, etc). This privelege is afforded only to the high-level mesh editing tools.

Private Flag Layers

The BMesh API provides a set of flags for faces, edges and vertices, which are private to an operator. These flags may be used by the client operator code as needed (a common example is flagging elements for use in another operator). Each call to an operator allocates a new flag layer and pushes it on to the layer stack, and when the operator finishes, its flag layer is then popped off the stack. This avoids flag conflicts between operators executed sequentially and nested operator executions as well.

Slots

Operators receive input and return output through the use of "operators slots". These slots are essentially named, typed parameters. Slots also make parameters optional: simply don't fill a slot if you don't have a meaningful value for it (though the operator may fail if a slot that should contain necessary input is left empty).

The following slot types are available:

• Integer
• Float
• Pointer - do not store arrays corrusponding to elements with this
• Element Buffer - a list of verts/edges/faces
• Map - simple hash map

The slot API allows for easy copying from one operator's output to another operator's input, allowing for chaining the flow of data during the execution of sequential or nested operators.

Top-Level Mesh Editing API

Mesh Editing Tools

Tools connect the mesh editor with the Blender interface, and can be directly run by users or called by scripts. Examples include extrude, loopcut, edgering select, etc.

Tools are the only part of the API that can touch the header flags, allowing tools to affect selection, seams or other user-visible properties of the mesh.

As a best practice, tools should not contain any complex logic for traversing the mesh and should never edit the mesh directly. For mesh traversal, they should rely on walkers and iterators. For mesh edits, they should call out to BMesh operators.

Tool initialization and cleanup

Unlike the EditMesh system, the Bmesh kernel has a very strict API for tool authors to interface with. Editing of a mesh is 'locked' under normal circumstances and any calls to the modeling API will fail unless they appear between a pair of calls to bmesh_begin_edit() and bmesh_end_edit(). These functions are intended to perform several ' House Keeping' functions, such as clearing flags, statistic handling, interfacing with the undo system, tessellating N-Gons and doing intermediate level mesh validation.

Changes to Mesh / DerivedMesh

Existing Mesh structures such as MFace assumed everything was a triangle or a quad. While BMesh could have taken the approach of combining adjacent planar faces to form polygons, allowing the user to edit the mesh using polygons, and then converting everything back to a triangles and quads when exiting edit mode, this approach is suboptimal. Instead, Mesh has been upgraded to store polygon data.

New Mesh Structures

Similar to BMFace and BMLoop, there are new mesh structures MPoly and MLoop respectively. Note that these don't replace MFace: MFaces are built by the tessellator for use by the renderer.

Similarly, data which was stored in sets of 4 on structures linked with MFaces (e.g. MCol for vertex colors, MTFace for UVs) are now stored on the loops, in MLoopCol and MLoopUV structures. Again, these don't replace MCol and MTFace, as those are created via tessellation.

Impact on Modifiers

The degree of changes necessary to get modifiers working on BMesh depends a lot on the modifier:

Some modifiers such as dynamic paint only reuqired changes to walk the corners in MLoopCol to apply paint instead of walking the 3 or 4 corners per face in MCol.

Other modifiers such as subsurface need to consider polygon input, but can get away with producing only quad output (using utility functions to promote quads up to polygons after constructing the quads), others such as solidify need to consider and produce polygons.

Finally, special cases like multires have required sweeping changes to get working.

Impact on Renderers

Renderers will have tessellated faces (MFace) and linked data (MTFace, MCol) available, so for the most part renderer should not be affected by the Mesh structure changes for BMesh. This was proven by the Cycles merge: other than the actual merge from trunk, the only extra work necessary to get the Cycles renderer in BMesh was to expose a few extra RNA properties describing tessellated faces (which had actually already existed at some point, and had been removed while we didn't have any external renderers and didn't need those properties).

Impact on Drawing

3D View drawing did require some extra care to get right: though the drawers also primarily use tessellated faces, the renderer does need to be aware of polygons in some cases (for example, to highlight selected polygons while drawing in editmode). For this, the drawer can reference the CD_POLYINDEX layer to find the corresponding MPoly in the final mesh for an MFace in the final mesh, or the CD_ORIGINDEX layer to find the corresponding MPoly from the original mesh (the Mesh as it was before modifiers were applied).

Impact on Other Features

As a general rule, if your feature reads and/or writes the mesh structures, it will probably need some attention to convert it to BMesh. I'll be compiling a quick porting guide that covers basic traversal of the new Mesh structures, with examples, coming soon.

Future Work

No Direct Mesh Edits: Use Only Euler Operators

As a best practice, all manipulation of a mesh structure should be done using these functions. This would be beneficial because the Euler functions would benefit from more extensive testing, becoming very stable, and thus increasing the stability of the BMesh tools that rely on them.

However, currently many of the BMesh operators edit mesh structure directly instead of using these Euler Operators. It should be a post-merge goal to convert all BMesh operators to use Euler functions, potentially adding extra Euler functions if necessary.

Holes in Faces

As part of the original design, BMesh would be capable of handling multiple boundaries for a single face, which would allow for holes in faces. This has become a non-goal of the first BMesh feature merge, as we have chosen instead to stabilize the existing BMesh feature setto prepare for the first BMesh merge.

Efficient Undo

Current undo is achieved by making a copy of the mesh structures, and overwriting the current mesh with old copies when an undo operation is requested. This has the downsides of potentially consuming a lot of memory, and also slowing things down due to the massive number of allocations involved in making copies of detailed meshes.

As part of the original design, BMesh intended to achieve a more effecient undo, by storing a list of what eulers were called, in what order. To undo the effects of the last tool executed, all that would need to be done is to traverse this list backwards and execute the inverse of each command.

This has become a non-goal of the first BMesh feature merge, mainly because many of the BMesh operators no longer exclusively use Euler Operators to modify the mesh.

Note: in-progress implementation: BMLog

References

1. Weiler, K.J. : The Radial Edge Structure: A Topological Representation for Non-Manifold Geometric Modeling. in Geometric Modeling for CAD Applications, Springer Verlag, May 1986.