Bmesh

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 *)

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 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 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, low level operations use the prefix bmesh_kernel_, 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_kernel_split_edge_make_vert/join_edge_kill_vert
• bmesh_kernel_split_face_make_edge/join_face_kill_edge: 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_split_edge_make_vert(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e) 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_kernel_join_edge_kill_vert(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool check_edge_double, const bool kill_degenerate_faces) 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_kernel_split_face_make_edge,bmesh_kernel_join_face_kill_edge and bmesh_kernel_join_edge_kill_vert. Returns - 1 for success, 0 for failure

BMFace *bmesh_kernel_split_face_make_edge(BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2, BMLoop **r_l, BMEdge *e_example, const bool no_double) 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_kernel_join_face_kill_edge(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e) 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 join_face_kill_edge 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 split_edge_make_vert first on edges E1 then E2 we turn F1 into a polygon with six sides. Finally we run split_face_make_edge 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_kernel_split_edge_make_vert(e1);
    v2 = bmesh_kernel_split_edge_make_vert(e2);
    f2 = bmesh_kernel_split_face_make_edge(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 altogether.

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

Future Work

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 set to prepare for the first BMesh merge.

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.