Hi all,

Past couple months I’ve been working on implementing dynamic-topology sculpting for Blender. The implementation is based off the paper Freestyle: Sculpting meshes with self-adaptive topology by Lucian Stãnculescua, Raphaëlle Chainea, and Marie-Paule Canic. It’s getting stable enough to where people might find it fun to play with, so I thought I’d talk a bit about the tool and its current status.

Quick demonstration videos: https://www.youtube.com/watch?v=GFFtR8wBtZ8, https://www.youtube.com/watch?v=F0X51O4RgWs

High-level Overview

The dynamic topology tool allows sculpt mode to change the topology of the mesh as you sculpt. It operates on triangles, so you have to convert quads to triangles before using it. The mesh is updated as you sculpt (during the stroke, not just at the end of a stroke.) The tool places restrictions on the lengths of triangle edges to ensure that the topology stays “nice” for sculpting (no long skinny triangles.) The triangle density is constant across the mesh; there’s no way currently to make the tool give more triangles in a particular area.

The paper uses three basic operations to update the mesh: collapsing long edges, subdividing short edges, and merging close vertices. All three of these operations are implemented, but vertex-merge is currently disabled, as it’s too crashy to use right now. These operations require adjacency data that is not normally present in Blender’s mesh representation. The paper recommends storing the three triangles adjacent to each triangle, as well as a single adjacent face for each vertex. This is enough to quickly calculate the 1-ring for vertices as needed. To make adding and removing vertices/faces easy, they’re stored in linked lists rather than the usual mesh arrays.

Implementation Notes

Most of the code lives in blenlib/dyntopo.c and blenlib/pbvh.c.

The linked-list representation is a bit similar to EditMesh, but smaller, simpler, and easier to integrate with the PBVH. The PBVH is the spatial data structure used in sculpt mode for making fast searches for which vertices to update and partial redraw. Ordinarily the PBVH contains arrays of mesh-element indices; these arrays are built just once when you enter sculpt mode. For dynamic topology sculpt, list bases for the vertices and faces were added to the PBVH nodes. At the end of each stroke, any modified nodes are checked to see if the number of faces they contain has grown too large, and if so they are split. (Empty nodes should also be collapsed, but I haven’t gotten around to that yet.)

Testing

Code is available from Gitorious, in the “adaptive” branch:

https://gitorious.org/~nicholasbishop/blenderprojects/nicholasbishop-blender

git clone git://gitorious.org/~nicholasbishop/blenderprojects/nicholasbishop-blender.git
git checkout adaptive

Only CMake build system has been updated, but you could easily update scons too if you prefer that.

Usage is pretty simple: create a mesh, convert to all-triangles, enter sculpt mode, and click the “Dynamic Topology” button. Note that only the “simple” brushes work right now. Fancy things like smooth and grab will crash. Sculpting on a non-dynamic topology mesh will crash. Undo is disabled. Lots of other things I’ve forgotten about will also probably crash. Have fun! :)