BMesh undo and RangeTree

I’m continuing to work on the BMesh logging system that will provide undo/redo for dynamic-topology sculpting. One aspect of this logging system is assigning unique IDs to elements. In order to do this efficiently, I wrote a small C++ library to efficiently store and query non-overlapping ranges. This code is now used in the bmesh-undo branch to keep track of unused IDs. Since the code is fairly generic and might be useful elsewhere, I’ve pushed the RangeTree code into its own repository on Github.

Another recent change in the bmesh-undo branch is an easier way to examine the BMesh log. I added a new view to the outliner which shows changes to the mesh while in edit mode:

This is of course just a temporary debugging tool, not something that would be released. Note that low-level actions like mesh-element deletion and flag setting are now nicely grouped into high-level actions like “Translate” and “Extrude Region and Move”. Pressing CTRL+A/CTRL+SHIFT+A while in edit mode will now step back by high-level actions, and seems to work fairly well. (Again, the CTRL+A hotkey is just a temporary debugging tool.)

Back on the dynamic topology side, I am continuing to make updates to integrate the BMesh logging system with sculpt’s undo system. It is starting to work a bit, but still lots of glitches and crashes to deal with yet. I’m hoping that by improving the testing tools in the bmesh-undo branch I can work out a lot of these issues separately from dynamic-topology sculpting.

Gallium OpenCL on Radeon

Not strictly Blender-related, but it seems that the open-source Radeon drivers are getting closer to supporting OpenCL. Following these instructions got me some basic OpenCL on Ubuntu 12.04 with very little effort. The only issue I had was that libclc failed to link, had to add an extra “-ldl” to the Makefile. (Also, the list of dev packages I installed: xutils-dev x11proto-gl-dev x11proto-dri2-dev libx11-xcb-dev libxcb-glx0-dev libxcb-dri2-0-dev libxcb-xfixes0-dev libudev-dev bison).

This implementation of OpenCL is in the early stages and definitely won’t run Cycles yet (I tried, of course. The list of OpenCL devices does show my “AMD CAYMAN”, but attempting to render crashes with various OpenCL errors.) Still, very cool to see this progress being made.

Tips for bug reports

Today: some friendly advice for filing a good Blender bug report!

  • Submit the bug to the Blender bug tracker. I know it’s not the greatest bug tracker in the world (and has a bad habit of showing blank screens and errors), but it’s still better than posting on where it might never be seen by a developer (or having been seen, might be forgotten.)
  • Attach a file! It says this in big letters when you click the submit button, but people ignore it all the time. If the bug exists even on the default scene, check that it’s really the default by clicking Load Factory Settings in the File menu.
  • Make that file as minimal and easy to test as possible. Delete unnecessary objects, scenes, and screen areas. For example, if your bug report says to reproduce by adding a wave modifier to an object, save the file with that object selected and the modifier properties panel showing.
  • Give the file a good specific name. Examples of bad names: “test.blend”, “error.blend”, “flower.blend”. Better to give a short description of the error, and maybe even prefix it with your username to make it unique: “nicholasbishop-sculpt-grab-explosion.blend”.
  • Give steps to reproduce the bug in that file. If possible, also give steps to reproduce from the default scene. If you are unable to reproduce it from the default scene, say why.
  • Always say which version you tested with. Be specific (e.g. “2.63a” rather than “latest release”). If you’re testing something newer than the latest release, indicate the SVN revision. Say where the build came from; (give link!), official release, build bot, compiled yourself, etc.
  • Test something recent. It’s fine if you are staying with 2.62 for production work, but if you find a bug check that it’s in 2.63a too.
  • Give your operating system (plus 32-bit/64-bit) and other relevant system info like graphics card and drivers. If you’re not sure what’s relevant, it never hurts to attach the system info file that Blender can generate from the Help menu.
  • One bug per report! If you find more than one bug, even if it’s related to the same tool, file multiple bug reports.
  • No feature requests in the bug tracker. Often these sneak in as part of a real bug report, but these requests should go to or an email to the module owner.
  • Write as clearly as possible. I know many users are not native English speakers, but it helps to use punctuation and keep your descriptions as concise as possible. For those that are native English speakers, no excuses for not paying attention to the red squiggly beneath misspelled words! ;)

It may sound annoying to follow all these steps, but remember that if you don’t, the developers waste time figuring it all out themselves or trying to coax the information out of the user for each bug. Some developers like Sergey, Campbell, and Brecht handle a huge number of bug reports; you can really help them out by filing good ones.

Things that didn’t work

Or at least, things that haven’t worked yet. As a more concrete follow up to yesterday’s post, these are a few things I’ve spent time on recently and that I don’t have much expectation of being ready any time soon.

Small Polygon Reconnection (SPR)

I’ve discussed SPR a couple times before. Essentially it is a way of improving local connectivity to reduce the number of irregular vertices in a quad mesh.

Although the basic SPR algorithm is simple enough, getting it to work quickly enough to be practical is quite challenging. There is a huge space of possibilities to search, so it needs aggressive pruning to get the times down. I wasn’t able to find a solution that gave both good and quick results.

My primary interest in SPR was to improve the output of the remesh modifier. Consider this example:

The remesh modifier often gives results like those on the left with curves surfaces. The mesh at right was hand-edited to encourage a more regular grid. In theory SPR should be able to do this, but given its speed problems a better solution might be to hard-code fixes for some common patterns in remesh’s output. Even a simple collapose on the diamond pattern that shows up a lot could be very helpful.

Projection Quad Coverage (PQC)

After I decided that SPR wasn’t going to work, I spent some time on an alternative idea called Projection Quad Coverage. This experiment was a bit of a departure for me because it wasn’t based on any particular research paper (although the general concept of parameterization has been well studied). Of course, it wouldn’t surprise me much if their is a paper describing this idea, but I have not found one — so I just came up with a nice TLA (three-letter acronym) and carried on.

The basic algorithm for PQC is:

  1. Partition the mesh’s polygons into groups (called charts in this context) such that the chart is connected (i.e. not a collection of islands), and all polygons’ normals are within X degrees of some common vector.
  2. For each chart, project its component vertices onto the plane whose normal is the chart’s “common vector” mentioned earlier.
  3. Overlay a 2D quadrilateral grid onto that plane, with grid squares having some user-defined side length.
  4. Assign Z values to each grid vertex by finding the mesh polygon that vertex lies within, and interpolating between the mesh polygon’s projected coordinates. If a grid vertex does not lie within a mesh polygon (note that this a 2D test), just mark the vertex.
  5. For each grid square, test if its vertices are unmarked (i.e. have valid Z coordinates). If so, unproject the grid square’s corners back into the mesh’s 3D coordinate space and add the square as a quadrilateral in the output mesh.
  6. Connect the boundary edges of charts to adjacent charts.

I’ve glossed over some things in that description… where the common vector comes from, how to efficiently calculate the grid projection, etc. The real trick though is my incredibly unspecific step six. The rest I got working pretty well, and that’s what is shown in the screenshot below. Note how large contiguous sections of the remeshed Suzanne have really nice regular quad distribution, with precisely zero irregular vertices (other than the borders).

Filling in those cracks between charts turns out to be quite hard. A couple “obvious” approaches are apparent: merging close boundary vertices or filling in the cracks with new quads and triangles. The devil is of course in the details though, and I didn’t find a good way to implement either of these high-level ideas. Unfortunately I only have that one screenshot of PQC handy, or I’d demonstrate better the issues that came up.

I had one more involved concept for filling cracks: build an edge network between all adjacent charts using the same projection/division/interpolation approach. When remeshing each chart, it could then greedily fill in quads between the chart edge and the global edge network (though using just those portions of the edge net that it borders). I still think this idea could work, but at that point I’d already spent a week or more on PQC and felt it was time to get back to more “practical” projects.

Unlimited clay’s concepts for dynamic topology

I noted recently that I would be looking into Farthary’s unlimited clay paper to see if it could be used for the dynamic topology project. Unfortunately, the paper is not quite detailed enough for me to reproduce his results. I had to make some guesses about the intended implementation, and quite likely I got some things wrong. I should note also that I probably need to code up a better version of local mesh relaxation to really test his algorithm properly.

On a more positive note, most of the work needed for dynamic topology sculpting is fairly generic. If I get it working well, and if at some future point Farsthary regains Internet access and is still interested in working on Blender, it should be much easier for him to work on this code. Recall that his original attempt at putting unlimited clay into Blender was pre-BMesh, so it used a somewhat slow hack for integrating EditMesh into the PBVH. That whole issue is now nicely avoidable.

And now…

So that’s three recent examples of things that haven’t worked yet. There are others, for example I’ve experimented a bit with getting MyPaint brushes in Blender, but not much of interest to say there. For now I will continue to focus on dynamic topology and the related BMesh-undo project, as well as some general bug fixing for 2.64.

Mind the gap

It’s interesting to reflect on how long it takes some features to go from the idea stage to being a finished feature you can use in released software. It has been frequently noted that building software is not like building bridges. You often don’t know upfront what the implementation will look like, or what unexpected issues will derail the project, or what nasty bugs will appear that take a long time to work around.

In between the idea stage and the complete stage you often have an intermediate step: a test or preview of the feature where you can see it doing whatever cool thing it does. In my experience, that intermediate step usually sits much closer to the idea stage than the completion stage. I think that this is often confusing for users of the software though; they saw a video of the feature “working”, so why didn’t that feature go into the next release? Sometimes years go by and the feature is still not released. What the user doesn’t often see is the work that goes into making a feature stable and making the code maintainable.

To make maintainable code requires writing code that fits nicely with the existing software’s architecture. If that architecture can’t accommodate the new feature nicely, it’s best to make intermediate changes the build up groundwork needed for the new feature. Incidentally, this is one thing I find very helpful about my rebasing workflow in git. You might notice that the first few commits I make for larger features such as sculpt masking are often code cleanups and other non-sculpt-related changes.

Many of the features that I’ve worked on for Blender have gone through a number of re-implementations. For example, I first coded sculpt masking while working on SharpConstruct. I think I tried at least once or twice to implement masking in Blender 2.4x. I later rewrote it for Blender 2.5 during one of my GSoC projects, but I didn’t feel that code was quite good enough to go into trunk — it just didn’t have that feeling of being “obviously correct”. So I rewrote it again this year, and this time the code felt right. Even that final rewrite took months though. There is a huge benefit to getting the code right, and that’s fewer bugs to deal with. I think only a few bugs have been reported about sculpt masking so far, and all were pretty simple fixes (knock on wood.)

I include that example because after every GSoC, there’s inevitably a certain amount of disappointment from users about “failed” projects. Some express derision for GSoC as a whole, noting that so many projects never seem to make it into trunk. While it’s true that some projects really do completely fail (student disappears, or simply doesn’t have the necessary coding chops), I think it’s good to give them the benefit of the doubt. They might yet figure out how to make the project work. Even if not, they’ve probably learned a lot about Blender’s code and might contribute other features if they see the Blender community as a welcoming and forgiving environment. And indeed, I think that Blender’s users are overall nice about delays and flaws in the development process, so thanks for that :)

This has gotten a bit too long and rambly! So: next up I’ll discuss a bit more the state of SPR and some other features that are in that nebulous gap between idea and completion.

Undo for dynamic topology

I’ve been working the past couple days on the issue of undo/redo for dynamic-topology sculpting. The approach I’m looking into is one that should have general applicability outside of sculpting too.

Currently, changes made to the mesh while in edit mode create a full copy of the mesh. This is the simplest and least error-prone way to do it, but certainly not the most efficient. As noted in the BMesh wiki doc, a potentially better way to do it is to take advantage of the so-called Euler operators used to manipulate the mesh topology.

Euler operators are a set of functions that make small changes to a localized area of a mesh. They also have inverses, so they can be cleanly undone. The BMesh doc gives more info, but a simple example is vertex creation. The function BM_vert_create() is an operator that creates a new vertex in the mesh; it’s inverse is BM_vert_kill(), which deletes the vertex.

These operators can be used to create an efficient undo system by logging each operator as it is called, as well as its inputs. (There’s actually some extra indirection there because the inputs are pointers which might change after undoing and redoing an edit, so we assign each mesh element a unique ID and store that in the log.) These logs form a list that essentially records the history of the mesh (linear history, that is, not including any undo/redo steps themselves.) Additional log entries must be created for non-topological operations such as selection and transform operations.

I’ve written up some more technical information in a proposal on the wiki, and there’s test code in the bmesh-undo branch of my github repo. I’ve sent the proposal to bf-committers; hopefully there are no major issues with this idea, but we’ll see.

Next goal is to continue working on logging for more of BMesh’s operators, then I’ll rebase the dynamic-topology branch on top of bmesh-undo and try to integrate the new undo system in sculpt mode. So much work just to make CTRL+Z do something! :)

Dynamic topology: smoothing, VBO, stability

Dynamic topology sculpting test, ~75k-triangle result from created from a 12-triangle cube.

I’ve made a lot of updates to the dyntopo branch on Github during the past few days.

Some of the changes include:

  • Working smooth brush
  • VBO drawing (this is enabled regardless of the VBO setting in the user preferences)
  • Removal of loose vertices
  • Much more robust topological edits
  • Masks display correctly
  • Hiding works, still some bugs though
  • Builds with scons

A general outline of the work that yet remains:

  • Undo/redo
  • UI
  • Brushes that require original coordinates (grab & co.)
  • Stability fixes
  • Limit topological edits to the areas directly around the brush
  • Performance improvements
  • Surface relaxation (to fix blocky appearance after subdivision)
  • Surface merging (maybe as a separate brush?)

One side note: switching between sculpt and object mode is very unstable right now; when testing, recommend you switch in and out of sculpt mode from/to edit mode.

Some implementation notes on dynamic topology

The following is in response to a question asked on Google+ about dyntopo’s relation to unlimited clay. This question comes up a lot, so I’ll answer here as a general reference.

Neither the new dyntopo branch nor my older adaptive-sculpt branch on Gitorious share any code or algorithms with Farsthary’s unlimited clay, but that might not be the end of the story.

There are two somewhat separate components at play here. The first is the underlying modifications to sculpt needed to support dynamic topology. This includes adding BMesh support to the PBVH, updating the drawing code to handle topology updates, and eventually undo support.

With just those changes in place though, you wouldn’t really see any difference from regular sculpting except worse performance and more memory usage. You need the second component: topological operators that change the mesh structure. This is what Farsthary’s unlimited clay was really about, an algorithm for adaptive topological updates.

At present, the dyntopo branch contains two of the three topological operators defined in the paper “Freestyle: Sculpting meshes with self-adaptive topology”. Specifically, long edges are subdivided and short edges are collapsed. (Surface merging is not implemented.) This is a quite simplistic model, and we might well want something better.  Farsthary wrote about his algorithm here; I will be examining it soon to see about using those ideas.

Dynamic topology branch available

Quick test of dynamic topology. The original mesh was a cube (12 triangles.)

I’ve pushed the dyntopo branch to my github repository, so you can give it a try if you’d like. The code is only about two days old now, so be warned that it’s at a very incomplete stage.

There’s no UI for dynamic topology yet, so as soon as you go into sculpt mode (on a non-multires mesh) it’s active. At some point of course, a switch will be added so you can choose between regular sculpting and dynamic topology.

The detail size is hardcoded at 0.1 BU right now, so you can increase or decrease the mesh density by scaling up or down in edit mode.

Note also that plenty of brushes and features don’t work yet, notably the smooth and grab brushes, as well as undo.

Supporting undo will likely be the biggest challenge for dynamic topology; it’s not at all clear how to store undo data without copying the entire mesh (which would cripple performance.)