CGAL users discussion list

[Ben Supnik <>]

Hi,

Shi Yan wrote:
> did you have any experience of writing a half-edge data structure with
> undo/redo feature?
>
> i'm wondering if the command pattern is the only way to achieve undo and redo.

It is not.  Another design that can be used is a copy-on-write model for 
data.  I haven't used this with DCELs, but I have used it with a 
hierarchial geometry model (e.g. polygon is points, area is polygon set, 
etc.).

The naive alternative to commands is to copy the entire data model every 
time you push an operation onto the undo stack - the limiting factor is 
that it's really slow and really memory hungry.

The copy-on-write goes like this:

1. All objects in the system need GUIDs.

2. All links between objects must work in some persistent form - either 
by using GUIDs instead of ptrs, or by being able to patch pointers after 
an undo/redo.

3. Any operation that modifies an object first tells it to copy itself 
to the current undo.  (This includes creation and destruction...for 
creation we only need to note that we were created, since we can call 
the default ctor.)

4. There are some rules for object lifetime:

- If we persist the creation of an object and the destruction in one 
buffer, we can delete both.

- If we modify and then destroy (or modify twice) an object, we can 
remember only the first change (since we don't have to save intermediate 
state within an undo).

- If we destroy, then create an object, we can change this to a single 
"modify".

There are a few big wins of working this way:

- No need to write per-operation undo code.  This can be a huge win if 
the data model is simple but you do a lot of operations on it...this is 
the scenario where I usually deploy the pattern.  The right, simplest 
subset of your data is persisted automatically as you do operations code.

- If the operations code is asymetric, writing an undo for something 
simple can get complex (for example, undo a remove-vertex).  But since 
this is based on restoring the underlying data structure directly, it's 
just a question of putting objects back together.

And the problems:

- Heavy cost of infrastructure between objects, since we need persistent 
pointers.

For something like a DCEL half-edge (which has at least four pointers I 
think) that's potentially a lot of overhead.

> however after some operations, the half-edge handle could be invalid.

Yes - this can be a problem for ANY undo-redo system if the reference to 
the data model (from outside the data model) uses references that aren't 
persistence-safe, like pointers or iterators. :-(

The copy-on-write system has the side effect of giving you persistent 
handles, because it needs them internally to operate.  Typically 
observers of this data model would use persistent references too so that 
other code wouldn't become confused by an undo-redo.

> and now i need to move point A back to the original position, but i
> cannot do it, because i lost the half-edge handle E.

> so how i'm suppose to do this?

For what it's worth, if you had persistent references to the elements of 
your DCEL, this case would "just work" because structurally the DCEL is 
right, even if the handles are wrong.

One way to implement persistent handles on top of a ptr-based structure 
would be:

- The "archive" (container of your entire data structure) contains a 
hash table of GUID->CGAL handles.

- All persisted forms of the data for the purpose of undo write GUIDs.

- During an undo, restore the objects in two parts: first execute any 
creation/destruction of objects needed for the undo, so that you have 
the real final handles for all needed objects.  Then restore the 
contents, looking up CGAL handles by GUID.

For CGAL's DCEL you might have to be careful to ensure that edges are 
always persisted in pairs.  However I suspect that the "stream of 
creates and destroys" that you observe as you run will match these 
required semantics...CGAL won't do (via code that modifies the DCEL) 
anything that proves to be illegal later.

cheers
bEn


--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: