CGAL users discussion list

["Shi Yan" <>]

thanks Ben.


i guess it is not easy to implement. i think the most practical way is
to maintain a hash table and give each geometry primitive (vertex,
half-edge, facet) an unique id.

each Euler operation will be recorded by the undo stack as an operator
and the unique id it was applied on.


i also thought about an another option. how about i write a memory
pool by implementing my own new and delete operators.
the memory pool holds the entire geometry.
 and i can maintain a command system onto the memory pool. in this
way, no matter how complicated a half-edge Euler operator is,
eventually it is a set of modify/allocate/release operations on the
memory pool. therefore i can only try to restore the memory pool with
commands like allocate, release and modify.


i'm just wondering how do those commercial software solve undo and
redo problems. this should be a very common issue facing by any
sophisticated program. but i really can't find any article on this.


On Tue, Jul 1, 2008 at 6:42 AM, Ben Supnik 
<>
 wrote:
> 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: 
> 
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>



-- 
Dept. of Computer Science
University of California, Davis
Homepage:http://wwwcsif.cs.ucdavis.edu/~yans/