Dev:Source/Modeling/PBVH

PBVH is the Paint BVH (bounding volume hierarchy) currently used to accelerate drawing and brush interaction in sculpt mode. It will eventually be used to accelerate other paint modes too.

Its header is in blenlib/BLI_pbvh.h [1], and its implementation is in blenlib/intern/pbvh.c [2].

BVH

The PBVH is pretty much a standard bounding volume hierarchy. A BVH is a tree where each node is a bounding volume, which is to say that its volume is large enough to contain all of its children. There's plenty of references [3] [4] online for BVH's, so I won't go into too much detail about them here.

Our BVH is binary (two child nodes for each internal node), and the bounding volumes used are all axis-aligned bounding boxes (AABBs.)

Our implementation is a little different from a BVH you might see in a rendering context though. Because we need to build the tree quickly, we intentionally don't build a particularly good tree, or even a very fine-grained tree.

Building

The PBVH has the usual functions to create and free it, BLI_pbvh_new() and BLI_pbvh_free(). The actual building however is done through BLI_pbvh_build_mesh and BLI_pbvh_build_grids. The former is used to build the PBVH from a mesh (or CDDerivedMesh), the later is used to build from a CCGDerivedMesh (i.e. the output of the Subsurf and Multiresolution modifiers.)

These two build functions are used to input "primitives" into the PBVH. Primitives are the fundamental unit of the PBVH, in that they can't be subdivided any further. When building from a Mesh, MFaces are the primitives. When building from a CCGDM, grids are the primitives. (Grids are essentially an array of coordinate/normal pairs; subsurf outputs one grid for each corner of each input face.)

The first step of building the PBVH is to create an array of bounding boxes, one bounding box for each primitive. Also included in the bounding box data is the centroid of each primitive. At the same time, the "cb" value is calculated. "cb" is the centroid bounding box; it surrounds all of the primitives' centroids.

Once this initial work is done, the rest of building the PBVH is the same for faces and grids until we get to the leaves of the tree.

At the end of BLI_pbvh_build_mesh() and BLI_pbvh_build_grids(), the internal function pbvh_build() is called. Think of this function as setting up a BVH that contains only one node. This big root node contains all of the primitives, both in the sense that its bounding box surrounds all of the primitives' bounding boxes, and that all the primitives are accessible through this big root node.

It initializes PBVH.prim_indices to be an array sized to the number of primitives, and initially containing the integer values zero through one minus the number of primitives. More on the prim_indices shortly.

The last thing this function does is call build_sub() to start building the tree recursively.

Internal nodes

build_sub() builds one node of the tree. It decides if the node should be a leaf or not, and if it's not a leaf, calls itself recursively. The first call to build_sub() gives it the "big root node" created in pbvh_build().

build_sub() checks if the number of primitives in the node is greater exceeds PBVH.leaf_limit, and if so, this node is marked as an internal node. Since this is a binary tree, it creates two empty child nodes and links the current node to them. We set the current node's bounding box (PBVHNode.vb) to surround all of the primitives' bounding boxes.

In order to build the child nodes, we need to spatially partition the current nodes primitives, sending some primitives to the left child and some to the right. We do this with a simple heuristic: what axis (X, Y, or Z) are the primitives spread out furthest on? We find this with a call to BB_widest_axis(cb). The middle of the "cb" bounding box on its widest axis is the spatial split.

We use the spatial split to define the left child node to contain all of the primitives whose centroid is to the left of the spatial split (on the widest axis), and the right child node contains all the primitives with centroid to the right of the spatial split. (Incidentally, this explains why we've been keeping track of a centroid bounding box: if we split based on primitives' bounding boxes, rather than their centroids, it wouldn't be clear what to do with a primitive that goes inside both the left and right child nodes. By using the centroid, it's always in one or the other (or it sits right on the spatial split, and we just put it in the right child node.)

When splitting the primitives up, we don't actually change the order of the faces array or the grids array, we only modify PBVH.prim_indices. This array is a map between the primitives contained in the node and the actual indices of the primitives in the array their data is stored in (either an MFace array or a DMGridData array.) This means that build_sub() can just partition indices in the prim_indices array, which is done with a call to partition_indices(). Now it's ready to continue building recursively with two more calls to build_sub(), one for the left child and one for the right child.

Leaf nodes

All leaf nodes contain a pointer into the prim_indices array, and a count of the number of primitives in the node. They also have a bounding box that surrounds all of those primitives, used for searching the tree. Other details of the leaf nodes are different depending on whether the PBVH is being built from faces or grids.

Face nodes

Face nodes need to provide access to vertices for sculpting purposes. This requires a little extra work because so far, all we've done is put faces into the node, nothing with vertices has been done. Also, we sometimes want to know all of the vertices used by all the faces in each node, but sometimes we want to exactly partition vertices so that each vertex exists in only one node. (Note that we can't do that last part just by seeing if the vertex is in the node's bounding box, because there can be overlap between the bounding boxes of leaf nodes.) Finally, we want to be able to index into the array of vertices in the node by inputing a face and one of its corners.

So in order to do all this, we use a couple extra data structures, a BLI_bitmap created way back in BLI_pbvh_build_mesh, and a GHash temporarily created in each leaf node as we build it.

The bitmap is sized to contain one bit for each vertex in the original MVert array. This bitmap is used to indicate, for each vertex, whether the vertex has been "taken" by a leaf node or not. Each bit is initially set to zero.

In build_mesh_leaf_node(), we initialize PBVHNode.face_vert_indices to contain one index for every corner of every face, and PBVHNode.vert_indices to contain the indices of each vertex used by the node.

Next we initialize the GHash with map_insert_vert(). map_insert_vert() is called once for every corner of every face, with the index of that corner's vertex as input. The vertex is checked against the bitmap to see if it's been used in this or another node. If not, we say it's a "unique vertex", that is, the vertex has been claimed by this node. The bit in the bitmap representing this vertex is set to one to indicate that the vertex is taken. The vertex is inserted into the GHash with its index as a key and the value as the number unique vertices found so far for this node. If it's not a unique vertex, it's inserted into the GHash with its index as a key and the value as the number of non-unique vertices found so far for this node. (Actually, the value is negated and has one subtracted from it so that we can identify these values by checking to see if they're negative.)

Once that's done, PBVHNode.vert_indices is filled in by iterating through the GHash and putting all the "unique vertex" indices at the beginning of the vert_indices array, followed by any non-unique-vertex indices.

Lastly, PBVHNode.face_vert_indices is modified so that any negative values (indicating a non-unique vertex) are updated to point to their actual index in PBVHNode.vert_indices.

Finishing touches

The last thing done after building a node is a call to update its GPU data. Each node carries data used to draw the node quickly, using VBOs if possible.

For building grid nodes, updating the GPU data is the only thing that's done, no special vertex handling is needed.

Partial Redraw

When editing a mesh in sculpt mode, often only a small part is changed. This means the area that needs to be redrawn can often be small too. In this section I'll outline the components of partial redraw.

Mark modified nodes

After making a change to a node that will require redrawing, the redraw flag must be set (PBVH_UpdateRedraw).

Redraw bounding box

To get an object-space bounding box containing all the nodes that have been modified, call BLI_pbvh_redraw_BB. This just expands a bounding box to contain all the nodes that were marked earlier.

Convert to screen space

To redraw properly, we need to redraw an area in screen-space (2D). This is important because a modified node could be occluded by other polygons in the model; if only the modified nodes were redrawn, they would appear to jump on top of the occluding features. To avoid this, object-space bounding box is transformed to a 2D screen-space bounding box.

Currently this is done by sculpt_get_redraw_rect(); it'll probably be changed into a generic view3d function eventually so that other modes can use it.

Tag the redraw

To mark the 2D bounding box for redrawing, call ED_region_tag_redraw_partial. (Be sure the rectangle is offset properly for the region its in.) It's also necessary to set a partial redraw flag, currently SculptSession.partial_redraw (this too will be moved so other modes can use it.)

Drawing

Multiple redraws can be tagged, and they'll all be combined and dealt with during the normal redraw phase.

Get the 3D area

As mentioned earlier, we have to be sure that modified areas don't get redrawn in front of other parts of the mesh that are in front. We avoid this by converting the 2D bounding box into four clipping planes.

In draw_mesh_fancy(), it checks to see if partial_redraw is set. If so, it gets the clipping planes and passes them into the regular DM draw functions (currently just drawFacesSolid.)

Calculating the clipping planes is currently done by sculpt_get_redraw_planes(), but again this will probably change to a generic view3D function.

Drawing the nodes

BLI_pbvh_draw is used to redraw, whether it's partial redraw or regular. For partial redraw, a PBVH search is used to find all leaf nodes that fall at least partially in the interior space defined by the clipping planes. Each of these nodes is passed to BLI_pbvh_node_draw(), and drawing proceeds as usual.

Contact

Questions can be sent to nicholasbishop@gmail.com.