But vertex editing just makes some things much easier to do, esp. if it doesn't create invalid brushes like WorldCraft does. 

I just find it pretty harsh to label it _useless_ for making level geometry. I've already produced a lot of geometry with it just fine. 

Apologies. I used hyperbole to make a point. 

Just released a new version, with the "drag facing planes" mode finally implemented (key F): http://shrinker.beyond-veils.de/projects/IterationX/Microbrush3/

And SleepwalkR made a case about proper undo/redo to me, so I'm now pondering about how I could implement proper undo/redo. 

I've always wondered, what IS a good way to implement undo/redo?

Maya, for example, has a class for every action you can perform, instantiated and stacked every time you perform one, and each one contains full information for reversing itself and maintaining references/indices in the process.

Effective, but kind of overkill? You're essentially writing all your functionality twice (backwards and forwards), wrapped in a shitload of cpp glue. 

Aka the command pattern. Even though it is a pest to implement, it has a number of advantages. Mostly because you can easily extend it to support macros in your app. And with command collation you can keep memory requirements low. 

Yeah, that's the really, really nice thing about Maya - a python window that'll let you do damn near anything (like write a .mdl exporter!)

That's for a very complex environment, though. Quake maps only contain two fairly simple kinds of data, one a pile of keyvalues and the other a pile of planes. 

a dumb way is to just make a copy of the document after every action, and store that in a stack. 

metl - Which for some apps, is great. It's brain dead but it's 100% perfect and failsafe. :) 

The only trouble is, of course, memory. If ZBrush did that it would be problematic... 

would consume way too much memory and also be quite slow on large maps. The command pattern uses the minimal amount of memory. For easily invertible operations such as transformations, you don't need to store anything but the transform matrix. For other operations such as vertex edits, you do have to store a snapshot, but only of the brushes you were editing.

Also, taking snapshots is far from being 100% perfect and failsafe. There are plenty of opportunities for bugs in that scenario, too. 

People seem to assume you need to copy the whole data structure if you want to make a copy of it. This isn't true if the data structure is designed in a particular way.

If the data structure is immutable and has a tree-like structure, you can easily share parts of it between multiple versions. Updating such a data structure requires only modifying the branch of the tree that contains the updated data.

These kinds of data structures that you can update while sharing data are called persistent data structures in the literature, as opposed to the ephemeral kind with which all slightly experienced programmers are familiar. Persistence here means simply that if you modify the data structure in state s_n to state s_n+1, you continue to have access to both states in the future. Persistent data structures can of course be implemented in multiple ways, with immutability and sharing being just one of them.

Don't confuse this use of persistent with that in persistent data, which means saving the data between program invocations in another place.

I don't know if anyone has made a non-trivial 3D modeler using immutable persistent data structures. It would certainly be an interesting experiment.

For more information, I refer you to the literature. If you want a brief intro, this might work.

http://bartoszmilewski.com/2013/11/13/functional-data-structures-in-c-lists/

It uses C++ to work through a simple example of a persistent list. 

Functional stuff! I've done a lot of stuff in Haskell and sometimes I wonder if I should remake it all in Haskell. :X

So far I've sketched out working on creating and destroying brushes as a whole all the time, with extra memory only required for otherwise deleted versions. I think I already got the undo steps done cleanly on paper, but the redo I still have to ponder about a bit.
Since I basically create everything from my plugin scripts, I'll make it so that you can define the borders of the undo steps in those.
One interesting realization I had so far is that if _within_ the borders of an undo step I create and then destroy a brush, it doesn't need to be saved, because duh, after the undo step is used, there's no brush either.

Microbrush uses a spatial data structure to store all of its geometry in clusters. If you edit neighboring brushes, only those will be rerendered. I've done it this way with good performance when editing 100k brushes per scene in mind.
Now when I want to do a brush transformation, for instance, I first remove the brush from that data structure, edit its data, and add it back in. While removing and re-adding stuff, the spatial data structure rebalances itself, merging or splitting nodes as necessary. It has lower and upper thresholds for inner nodes per inner node and objects per leaf node.

For an undo step, I'll store the old version of a brush (before a transformation, before deleting it, etc.), and the new version will be linked with the step so it can be tracked down and deleted again. It all comes down to a bit of fiddly bookkeeping of pointers forth and back and then a bunch of testing to make sure it doesn't explode. So far, I am a bit proud about how stable Microbrush runs. If you manage to make one of its plugins crash (e.g. the grid or the camera), the plugin is unloaded and you can usually still save your work. :D 

One interesting realization I had so far is that if _within_ the borders of an undo step I create and then destroy a brush, it doesn't need to be saved, because duh, after the undo step is used, there's no brush either.

Why would that happen though? I make something I like, accidentally delete it, hit undo, and instead of getting it back I undo whatever I last did before I made it. That's a table flip.


Snapshots of the entire document might be wasteful, but that seems easy to pare down. If the interface is requesting changes from the data, the interface already has (theoretically) perfect knowledge about what bits of the document have changed and therefore belong in or out of a snapshot.

Looks like this morning's coffee reading will be the command pattern. 

It's not as easy as it sounds though. Assume that your data structure is a tree, and you modify a node. If you modify a node, you basically add a new view to that data structure that sees all the other nodes, plus the new (modified) copy instead of the old node before it was modified. So what you really have is a new view onto the structure of the tree. To implement this, you also need to copy the parent of the modified node so that the new node can replace the old node in the children of the (new) parent node. And so on until you reach the root node.

So what's really happening is that you keep making new views on part of the structural information in your data structure. For trees, this might be easy to track. For graphs, it sounds like a nightmare and I'll wager that quite often you'll run into situations where you change one node, but have to copy a lot of structural information.

There's another problem though. Let's assume you have mastered this problem and you have a nice data structure that internally handles all this very well. What about references to nodes from the outside? Let's say your editor keeps a list of selected nodes and one of these nodes is changed and thereby copied. You have to update the node reference in the list of selected nodes too because now it points to the old version of the node. Okay, so maybe you can manage this too. But then you realize that keeping references to nodes is kinda handy (and also kinda the point of OO design), and so you are kind of designing against the core features of your language of choice (given that it is an OO language).

Anyways - I suppose that it is possible to write a data structure this way, and if you avoid references from the outside into the data structure, then this approach will work. But I don't think it's better than using the command pattern for undo. In fact, since it forbids a key feature of OO, I think it's quite a bit worse.

Or maybe I'm missing some things? 

 

Haskell mostly works with immutable data structures conceptually. Some of those have an operation to "refresh" the data, e.g. to chop off data that's not referenced from a view anymore.
This system is very awesome in practice, but it comes at a cost: They had to put a lot of brain into bookkeeping it all properly behind the scenes. If you just store updates upon updates all the time, there ultimately comes a point where you must start consolidating the data at the bottom. I think that's difficult.

Lunaran: You are talking about the tools the editor offers. I am talking about the functions used to create those tools. If I give the plugin programmer the ability to determine when a new undo step starts, what I said is a consequence. In practice, my tools will behave as expected: A deletion will be undoable, and I will look into making a plugin to support table-flipping so the editor is even more useful. :3 

Data types and implementation is important but maybe the way a tool shapes and interacts with the user should be the most important question?

Is undo/redo of every operation beneficial or does it slow down the creative process to have a huge amount of discrete steps that can optionally be back-tracked or not? Of course it's easier for the developer to just implement the standard features instead of pondering the philosophical implications of every feature.

Sometimes you do want to be able to flip back and forth between your latest action(s), sometimes deliberate snapshots(or commits � la git) might be better and sometimes it could be best to just move forward and never look back! 

Even if a plugin does create a brush and deletes it all within the same transaction, is that really a problem? That sounds like something you could live with, and if it does become a problem, it should be easily fixable. Since the only operation you allow on your tree is adding and removing nodes, it should be easy to identify such sequences.

One problem that you might have to prepare for is that there may be nested transactions. It will happen if you allow operations to be composed of other operations that might also be used in isolation. It's easy to solve though, the simplest solution is just to track the number of active transactions, and ignore the start / end of any nested transaction altogether. 

bear - Good undo/redo support that's well thought out is pretty important for the user.

Jackhammer, for example, doesn't do undo/redo of selections. That's really a pain when you're selecting a bunch of stuff, make a slip, and by habit try to undo it. Well, none of your selections change BUT the last edit you did before you started selecting things goes away.

That way lies madness... 

Undoing selection and other, similar actions that don't modify the map is a bit counter intuitive at first, because well, it doesn't modify the map! Also, other programs such as a word processor don't undo selection either. But in those programs, selection is a simple operation, whereas in a 3D tool, selection is not so simple. Sometimes you have to click a lot of times to select a number of objects, or you have to move the camera around a bit to select everything you wanted. So it can be a costly operation in terms of user effort, and that's why I think that it has to be undoable.

On top of that, I find it coherent that modifications only happen to selected things in all situations. In TB, the rule is that nothing changes unless it is selected. This is not only beneficial for optimizing the renderer (you only need to take care of updating the selected things in the renderer), but it also gives a simple, consistent rule for the user. 

@SleepwalkR: Creating and deleting a brush in the same transaction is not necessarily a problem, it's just a thing I have to consider. You know, when I sit there and sketch out all the implications of all the things that can happen. :)
Nested transactions... that sounds scary. I don't have that yet, but your heads up on that is quite correct.

@WarrenM: I don't plan on making selections undoable at the moment. 

I don't know how you sleep at night. 

 

You should reconsider that for the reasons outlined above. And as I said, it's easy to detect and dismiss nested transactions. Only the topmost transaction must be undoable anyway.